org.jikesrvm.compilers.opt.lir2mir

Class NormalBURS

java.lang.Object

org.jikesrvm.compilers.opt.lir2mir.BURS

org.jikesrvm.compilers.opt.lir2mir.NormalBURS

final class NormalBURS
extends BURS

This class contains methods for invoking BURS tree-pattern matching from the OPT Compiler. BURS is invoked on trees obtained from the dependence graph of a basic block.

See Also:

DepGraph, BURS_StateCoder, AbstractBURS_TreeNode

Field Summary

Fields

Modifier and Type	Field and Description
private AbstractBURS_TreeNode[]	heap A priority queue of ready tree nodes.
private int	numElements
private int	numProblemEdges Number of problem edges
private int	numTreeRoots
private SpaceEffGraphEdge[]	problemEdges track problem nodes (nodes with outgoing non-reg-true edges)
private AbstractBURS_TreeNode[]	treeRoots Set of all tree roots.

Fields inherited from class org.jikesrvm.compilers.opt.lir2mir.BURS

AddressConstant, BranchTarget, DEBUG, ir, lastInstr, LongConstant, NullTreeNode, Register

Constructor Summary

Constructors

Constructor and Description
NormalBURS(IR ir) Create a BURS object for the given IR.

Method Summary

Modifier and Type	Method and Description
private void	buildTrees(DepGraph dg) Stage 1: Complete the expression trees and identify tree roots.
private NormalBURS_DepGraphNode	castNode(SpaceEffGraphNode node)
private void	generateTree(AbstractBURS_TreeNode k, BURS_StateCoder burs)
private void	generateTrees(BURS_StateCoder burs) Stage 4: Visit the tree roots in topological order and emit MIR instructions by calling BURS_StateCoder.code on each supernode in the tree.
private void	handleProblemEdges() Stage 1c: Mark src node of some problem edges as tree roots to avoid cyclic dependencies.
private boolean	haveProblemEdges()
private void	heapify(int p)
private void	initTreeRootNode(AbstractBURS_TreeNode t, SpaceEffGraphNode treeRoot) Initialize nextSorted for nodes in tree rooted at t i.e.
void	invoke(NormalBURS_DepGraph dg) Build BURS trees for dependence graph dg, label the trees, and then generate MIR instructions based on the labelling.
private void	labelTrees() Stage 3: Label the trees with their min cost cover.
private void	makeTreeRoot(AbstractBURS_TreeNode n)
private boolean	mustBeTreeRoot(DepGraphNode n) Checks if the given node needs to be a tree rode.
private void	orderTrees(DepGraph dg) Stage 2: Construct topological ordering of tree roots based on the dependencies between nodes in the tree.
private void	problemEdgePrep() Stage 1b: Do bookkeeping to make it easier to identify harmless problem edges.
private void	problemEdgePrep(AbstractBURS_TreeNode n, SpaceEffGraphNode root)
private boolean	reachableChild(AbstractBURS_TreeNode n, SpaceEffGraphNode goal, int searchnum)
private boolean	reachableRoot(SpaceEffGraphNode current, SpaceEffGraphNode goal, int searchnum)
private void	readySetInsert(AbstractBURS_TreeNode node)
private boolean	readySetNotEmpty()
private AbstractBURS_TreeNode	readySetRemove()
private SpaceEffGraphNode	regTrueParent(SpaceEffGraphNode n)
(package private) void	rememberAsProblemEdge(SpaceEffGraphEdge e)
private void	swap(int x, int y)
private boolean	trueEdgeRedundant(SpaceEffGraphNode current, SpaceEffGraphNode goal, SpaceEffGraphNode root)

Methods inherited from class org.jikesrvm.compilers.opt.lir2mir.BURS

action, append, debug, dumpTree, finalizeBlock, label, makeCoder, mark, prepareForBlock

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

numTreeRoots

private int numTreeRoots

problemEdges

private SpaceEffGraphEdge[] problemEdges

track problem nodes (nodes with outgoing non-reg-true edges)

numProblemEdges

private int numProblemEdges

Number of problem edges

treeRoots

private AbstractBURS_TreeNode[] treeRoots

Set of all tree roots.

heap

private AbstractBURS_TreeNode[] heap

A priority queue of ready tree nodes. Used to keep track of the tree roots that are ready to be emitted during code generation (since all of their predecessors have been emitted already). readySetRemove returns the node that uses the maximum number of registers. This is a heuristic that tends to reduce register pressure and enable coalescing by the register allocator. (Goal is to end live ranges 'early').

numElements

private int numElements

Constructor Detail

NormalBURS

NormalBURS(IR ir)

Create a BURS object for the given IR.

Parameters:

ir - the IR to translate from LIR to MIR.

Method Detail

invoke

public void invoke(NormalBURS_DepGraph dg)

Build BURS trees for dependence graph dg, label the trees, and then generate MIR instructions based on the labelling.

Parameters:

dg - the dependence graph.

castNode

private NormalBURS_DepGraphNode castNode(SpaceEffGraphNode node)

buildTrees

private void buildTrees(DepGraph dg)

Stage 1: Complete the expression trees and identify tree roots. Complete BURS trees by adding leaf nodes as needed, and creating tree edges by calling insertChild1() or insertChild2() This step is also where we introduce intermediate tree nodes for any LIR instruction that has > 2 "real" operands e.g., a CALL. We also mark nodes that must be tree roots.

Parameters:

dg - The dependence graph.

problemEdgePrep

private void problemEdgePrep()

Stage 1b: Do bookkeeping to make it easier to identify harmless problem edges.

problemEdgePrep

private void problemEdgePrep(AbstractBURS_TreeNode n,
                             SpaceEffGraphNode root)

handleProblemEdges

private void handleProblemEdges()

Stage 1c: Mark src node of some problem edges as tree roots to avoid cyclic dependencies.

trueEdgeRedundant

private boolean trueEdgeRedundant(SpaceEffGraphNode current,
                                  SpaceEffGraphNode goal,
                                  SpaceEffGraphNode root)

reachableRoot

private boolean reachableRoot(SpaceEffGraphNode current,
                              SpaceEffGraphNode goal,
                              int searchnum)

reachableChild

private boolean reachableChild(AbstractBURS_TreeNode n,
                               SpaceEffGraphNode goal,
                               int searchnum)

orderTrees

private void orderTrees(DepGraph dg)

Stage 2: Construct topological ordering of tree roots based on the dependencies between nodes in the tree.

Parameters:

dg - The dependence graph.

labelTrees

private void labelTrees()

Stage 3: Label the trees with their min cost cover.

generateTrees

private void generateTrees(BURS_StateCoder burs)

Stage 4: Visit the tree roots in topological order and emit MIR instructions by calling BURS_StateCoder.code on each supernode in the tree.

Parameters:

burs - the BURS_StateCoder object.

generateTree

private void generateTree(AbstractBURS_TreeNode k,
                          BURS_StateCoder burs)

mustBeTreeRoot

private boolean mustBeTreeRoot(DepGraphNode n)

Checks if the given node needs to be a tree rode. If the node does not need to be a tree root right now but might later have to be marked as a tree root, then include in a set of problem nodes.

Parameters:

n - the dep graph node in question.

Returns:

true if node n must be a root of a BURS tree based only on its register true dependencies.

regTrueParent

private SpaceEffGraphNode regTrueParent(SpaceEffGraphNode n)

initTreeRootNode

private void initTreeRootNode(AbstractBURS_TreeNode t,
                              SpaceEffGraphNode treeRoot)

Initialize nextSorted for nodes in tree rooted at t i.e. for all register true descendants of t up to but not including any new tree roots.

Parameters:

t - the BURS node

treeRoot - the dependence graph node that belongs to the BURS node

makeTreeRoot

private void makeTreeRoot(AbstractBURS_TreeNode n)

readySetInsert

private void readySetInsert(AbstractBURS_TreeNode node)

readySetNotEmpty

private boolean readySetNotEmpty()

readySetRemove

private AbstractBURS_TreeNode readySetRemove()

heapify

private void heapify(int p)

swap

private void swap(int x,
                  int y)

rememberAsProblemEdge

void rememberAsProblemEdge(SpaceEffGraphEdge e)

haveProblemEdges

private boolean haveProblemEdges()