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, ArchitectureSpecificOpt.BURS_STATE, ArchitectureSpecificOpt.BURS_TreeNode

numTreeRoots

private int numTreeRoots

treeRoots

private ArchitectureSpecificOpt.BURS_TreeNode[] treeRoots

Set of all tree roots.

heap

private ArchitectureSpecificOpt.BURS_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

problemEdges

private SpaceEffGraphEdge[] problemEdges

numProblemEdges

private int numProblemEdges

NormalBURS

NormalBURS(IR ir)

Create a BURS object for the given IR.

Parameters:

ir - the IR to translate from LIR to MIR.

invoke

public void invoke(DepGraph dg)

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

Parameters:

dg - the dependence graph.

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(ArchitectureSpecificOpt.BURS_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(ArchitectureSpecificOpt.BURS_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(ArchitectureSpecificOpt.BURS_STATE burs)

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

Parameters:

burs - the BURS_STATE object.

generateTrees

private void generateTrees(ArchitectureSpecificOpt.BURS_STATE burs)

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

Parameters:

burs - the BURS_STATE object.

generateTree

private void generateTree(ArchitectureSpecificOpt.BURS_TreeNode k,
                          ArchitectureSpecificOpt.BURS_STATE burs)

mustBeTreeRoot

private boolean mustBeTreeRoot(DepGraphNode n)

Return true if node n must be a root of a BURS tree based only on its register true dependencies. If the node 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.

regTrueParent

private SpaceEffGraphNode regTrueParent(SpaceEffGraphNode n)

initTreeRootNode

private void initTreeRootNode(ArchitectureSpecificOpt.BURS_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.

makeTreeRoot

private void makeTreeRoot(ArchitectureSpecificOpt.BURS_TreeNode n)

readySetInsert

private void readySetInsert(ArchitectureSpecificOpt.BURS_TreeNode node)

Add a node to the ready set.

readySetNotEmpty

private boolean readySetNotEmpty()

Are there nodes to process on the stack?

readySetRemove

private ArchitectureSpecificOpt.BURS_TreeNode readySetRemove()

Remove a node from the ready set

heapify

private void heapify(int p)

swap

private void swap(int x,
                  int y)

rememberAsProblemEdge

void rememberAsProblemEdge(SpaceEffGraphEdge e)

haveProblemEdges

private boolean haveProblemEdges()