Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.jikesrvm.compilers.opt.depgraph
Class DepGraph

java.lang.Object
  extended by org.jikesrvm.compilers.opt.util.SpaceEffGraph
      extended by org.jikesrvm.compilers.opt.depgraph.DepGraph
All Implemented Interfaces:
Graph, TopSortInterface
public final class DepGraph
extends SpaceEffGraph

Dependence Graph for a single basic block in the program.

Field Summary
private  BasicBlock currentBlock
          The basic block we are processing
private  LiveSet handlerLiveSet
          Set of variables that are live on entry to at least one catch block that is reachable via a PEI in currentBlock.
private  IR ir
          The IR we are processing
 
Fields inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraph
_firstNode, _lastNode, backwardTopSorted, forwardTopSorted, numberOfNodes
 
Constructor Summary
DepGraph(IR ir, Instruction start, Instruction end, BasicBlock currentBlock)
          Constructor (computes the dependence graph!).
 
Method Summary
private  void clearRegisters(Instruction start, Instruction end)
          Initialize (clear) the dNode field in Register for all registers in this basic block by setting them to null.
private  void computeBackwardDependences(Instruction start, Instruction end)
          Compute anti dependences by doing a backwards traversal of the instructions from start to end.
private  void computeBackwardDependencesDef(Operand op, DepGraphNode destNode, DepGraphNode lastExceptionNode)
          Compute backward dependences from a given def to a given node.
private  void computeBackwardDependencesUse(Operand op, DepGraphNode destNode, DepGraphNode lastExceptionNode)
          Compute backward dependences from a given use to a given node.
private  void computeControlAndBarrierDependences(Instruction start, Instruction end)
          Compute control and barrier (acquire/release) dependences in two passes (one forward, one reverse over the instructions from start to end.
private  void computeForwardDependences(Instruction start, Instruction end)
          Compute flow and output dependences by doing a forward traversal of the instructions from start to end.
private  void computeForwardDependencesDef(Operand op, DepGraphNode destNode, DepGraphNode lastExceptionNode)
          Compute forward dependences from a given def to a given node.
private  void computeForwardDependencesUse(Operand op, DepGraphNode destNode, DepGraphNode lastExceptionNode)
          Compute forward dependences from a given use to a given node.
private  void computeHandlerLiveSet()
          Determine the set of variables live on entry to any handler block that is reachable from currentBlock
private  void computeImplicitBackwardDependencesDef(Register r, DepGraphNode destNode)
          Compute implicit backward dependences from a given register def to a given node.
private  void computeImplicitBackwardDependencesUse(Register r, DepGraphNode destNode)
          Compute implicit backward dependences from a given register use to a given node.
private  void computeImplicitForwardDependencesDef(Register r, DepGraphNode destNode)
          Compute implicit forward dependences from a given register def to a given node.
private  void computeImplicitForwardDependencesUse(Register r, DepGraphNode destNode)
          Compute implicit forward dependences from a given register use to a given node.
private  void createNodes(Instruction start, Instruction end)
          Create the dependency graph nodes for instructions start to end
private  LocationOperand getLocation(Instruction s)
          Get the location of a given load or store instruction.
 void printDepGraph()
          Print the dependence graph to standard out.
 
Methods inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraph
addGraphEdge, addGraphEdge, addGraphNode, addRootNode, addTopSortNode, allocateNodeNumber, buildRevTopSort, buildTopSort, clearDFS, compactNodeNumbering, enumerateNodes, firstNode, initTopSort, isTopSorted, lastNode, numberOfNodes, printDepthFirst, removeGraphNode, resetTopSorted, rootNodes, setFirstNode, setLastNode, setNumberOfNodes, setTopSorted, startNode, topSort, topSortOrder, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

handlerLiveSet

private final LiveSet handlerLiveSet
Set of variables that are live on entry to at least one catch block that is reachable via a PEI in currentBlock. This is an approximation of the more precise set, but can be done in linear time; doing the most precise thing (computing the set for every PEI and using each individual set to create the necessary dependences) is quadratic, and probably doesn't help very much anyways.

currentBlock

private final BasicBlock currentBlock
The basic block we are processing

ir

private final IR ir
The IR we are processing

Constructor Detail

DepGraph

public DepGraph(IR ir,
                Instruction start,
                Instruction end,
                BasicBlock currentBlock)
Constructor (computes the dependence graph!).

Parameters:
ir - the IR to compute the dependence graph for
start - instruction to start computation from
end - instruction to end computation at
currentBlock - the basic block that the instructions are living in
Method Detail

computeHandlerLiveSet

private void computeHandlerLiveSet()
Determine the set of variables live on entry to any handler block that is reachable from currentBlock

createNodes

private void createNodes(Instruction start,
                         Instruction end)
Create the dependency graph nodes for instructions start to end

computeForwardDependences

private void computeForwardDependences(Instruction start,
                                       Instruction end)
Compute flow and output dependences by doing a forward traversal of the instructions from start to end.

computeBackwardDependences

private void computeBackwardDependences(Instruction start,
                                        Instruction end)
Compute anti dependences by doing a backwards traversal of the instructions from start to end.

computeControlAndBarrierDependences

private void computeControlAndBarrierDependences(Instruction start,
                                                 Instruction end)
Compute control and barrier (acquire/release) dependences in two passes (one forward, one reverse over the instructions from start to end.

computeForwardDependencesUse

private void computeForwardDependencesUse(Operand op,
                                          DepGraphNode destNode,
                                          DepGraphNode lastExceptionNode)
Compute forward dependences from a given use to a given node.

Parameters:
op - source operand
destNode - destination node
lastExceptionNode - node representing the last PEI

computeForwardDependencesDef

private void computeForwardDependencesDef(Operand op,
                                          DepGraphNode destNode,
                                          DepGraphNode lastExceptionNode)
Compute forward dependences from a given def to a given node.

Parameters:
op - source operand
destNode - destination node
lastExceptionNode - node representing the last PEI

computeBackwardDependencesUse

private void computeBackwardDependencesUse(Operand op,
                                           DepGraphNode destNode,
                                           DepGraphNode lastExceptionNode)
Compute backward dependences from a given use to a given node.

Parameters:
op - source operand
destNode - destination node
lastExceptionNode - node representing the last PEI

computeBackwardDependencesDef

private void computeBackwardDependencesDef(Operand op,
                                           DepGraphNode destNode,
                                           DepGraphNode lastExceptionNode)
Compute backward dependences from a given def to a given node.

Parameters:
op - source operand
destNode - destination node
lastExceptionNode - node representing the last PEI

computeImplicitForwardDependencesUse

private void computeImplicitForwardDependencesUse(Register r,
                                                  DepGraphNode destNode)
Compute implicit forward dependences from a given register use to a given node.

Parameters:
r - source register
destNode - destination node

computeImplicitForwardDependencesDef

private void computeImplicitForwardDependencesDef(Register r,
                                                  DepGraphNode destNode)
Compute implicit forward dependences from a given register def to a given node.

Parameters:
r - source register
destNode - destination node

computeImplicitBackwardDependencesUse

private void computeImplicitBackwardDependencesUse(Register r,
                                                   DepGraphNode destNode)
Compute implicit backward dependences from a given register use to a given node.

Parameters:
r - source register
destNode - destination node

computeImplicitBackwardDependencesDef

private void computeImplicitBackwardDependencesDef(Register r,
                                                   DepGraphNode destNode)
Compute implicit backward dependences from a given register def to a given node.

Parameters:
r - source register
destNode - destination node

getLocation

private LocationOperand getLocation(Instruction s)
Get the location of a given load or store instruction.

Parameters:
s - the instruction to get the location from.

clearRegisters

private void clearRegisters(Instruction start,
                            Instruction end)
Initialize (clear) the dNode field in Register for all registers in this basic block by setting them to null. Handles both explicit and implict use/defs.

Parameters:
start - the first opt instruction in the region
end - the last opt instruction in the region

printDepGraph

public void printDepGraph()
Print the dependence graph to standard out.

Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD