org.jikesrvm.compilers.opt.depgraph

Class DepGraph

java.lang.Object

org.jikesrvm.compilers.opt.util.SpaceEffGraph

org.jikesrvm.compilers.opt.depgraph.DepGraph

All Implemented Interfaces:

Graph, TopSortInterface

Direct Known Subclasses:

NormalBURS_DepGraph

public class DepGraph
extends SpaceEffGraph

Dependence Graph for a single basic block in the program.

Field Summary

Fields

Modifier and Type	Field and Description
private BasicBlock	currentBlock The basic block we are processing
private DepGraphNode[]	depGraphNodes
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

Constructors

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

Method Summary

Modifier and Type	Method and Description
private void	clearDepGraphNodeForRegister(Register r)
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) Computes 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) Computes 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.
protected DepGraphNode	createDepGraphNode(Instruction p)
private void	createNodes(Instruction start, Instruction end)
private DepGraphNode	getDepGraphNode(Register r)
private LocationOperand	getLocation(Instruction s) Get the location of a given load or store instruction.
void	printDepGraph() Print the dependence graph to standard out.
private void	setDepGraphNodeForRegister(DepGraphNode dNode, Register r)

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

depGraphNodes

private final DepGraphNode[] depGraphNodes

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

getDepGraphNode

private DepGraphNode getDepGraphNode(Register r)

setDepGraphNodeForRegister

private void setDepGraphNodeForRegister(DepGraphNode dNode,
                                        Register r)

clearDepGraphNodeForRegister

private void clearDepGraphNodeForRegister(Register r)

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)

createDepGraphNode

protected DepGraphNode createDepGraphNode(Instruction p)

computeForwardDependences

private void computeForwardDependences(Instruction start,
                                       Instruction end)

Computes flow and output dependences by doing a forward traversal of the instructions from start to end.

Parameters:

start - start instruction

end - end instruction

computeBackwardDependences

private void computeBackwardDependences(Instruction start,
                                        Instruction end)

Computes anti dependences by doing a backwards traversal of the instructions from start to end.

Parameters:

start - start instruction

end - end instruction

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.

Parameters:

start - start instruction

end - end instruction

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.

Returns:

a location or null

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.