org.jikesrvm.compilers.opt.ssa
Class ValueGraph

java.lang.Object
  org.jikesrvm.compilers.opt.ssa.ValueGraph

final class ValueGraph
extends Object

This class implements the value graph used in global value numbering a la Alpern, Wegman and Zadeck. See Muchnick p.348 for a nice discussion.

From Muchnick, "the value graph of a procedure is a labeled directed graph whose nodes are labeled with operators, function symbols, or constants, and whose edges represent generating assignments and point from an operator or function to its operands; the edges are labeled with natural numbers that indicate the operand position that each operand has with respect to the given operator or function."

graph

private final SpaceEffGraph graph

Internal graph structure of the value graph.

nameMap

private final HashMap<Object,ValueGraphVertex> nameMap

A mapping from name to value graph vertex.

ValueGraph

ValueGraph(IR ir)

Construct a value graph from an IR.

PRECONDITION: The IR must be in SSA form.

Parameters:

ir - the IR

computeClosure

private void computeClosure()

Due to PI nodes and Moves, the initial label for a register may be another register. Fix up the value graph for cases where the initial register label was not removed.

enumerateVertices

public Enumeration<GraphNode> enumerateVertices()

Enumerate the vertices in the value graph.

Returns:

an enumeration of the vertices in the value graph

getVertex

public ValueGraphVertex getVertex(Object name)

Return the vertex which has a given name.

Parameters:

name - the name of the vertex

Returns:

the vertex with the name. null if none found.

toString

public String toString()

Return a String representation of the value graph.

Overrides:

toString in class Object

Returns:

a String representation of the value graph.

addRegisterNodes

private void addRegisterNodes(IR ir)

Add a node to the value graph for every symbolic register.

PRECONDITION: register lists are computed and valid

Parameters:

ir - the governing IR

processInstruction

private void processInstruction(Instruction s)

Update the value graph to account for a given instruction.

Parameters:

s - the instruction in question

processMove

private void processMove(Instruction s)

Update the value graph to account for a given MOVE instruction.

PRECONDITION: Move.conforms(s);

Parameters:

s - the instruction in question

processPi

private void processPi(Instruction s)

Update the value graph to account for a given PI instruction.

PRECONDITION: s.operator == PI

Parameters:

s - the instruction in question

processNew

private void processNew(Instruction s)

Update the value graph to account for a given NEW instruction.

PRECONDITION: New.conforms(s); For a new instruction, we always create a new vertex.

Parameters:

s - the instruction in question

processNewArray

private void processNewArray(Instruction s)

Update the value graph to account for a given NEWARRAY instruction.

PRECONDITION: NewArray.conforms(s); For a newarray instruction, we always create a new vertex.

Parameters:

s - the instruction in question

processPutField

private void processPutField(Instruction s)

Update the value graph to account for a given PUTFIELD instruction.

PRECONDITION: PutField.conforms(s); Make sure we have value graph nodes for a constant value

Parameters:

s - the instruction in question

processPutStatic

private void processPutStatic(Instruction s)

Update the value graph to account for a given PUTSTATIC instruction.

PRECONDITION: PutStatic.conforms(s); Make sure we have value graph nodes for a constant value

Parameters:

s - the instruction in question

processAStore

private void processAStore(Instruction s)

Update the value graph to account for a given ASTORE instruction.

PRECONDITION: AStore.conforms(s); Make sure we have value graph nodes for a constant value

Parameters:

s - the instruction in question

processALoad

private void processALoad(Instruction s)

Update the value graph to account for a given ALOAD instruction.

PRECONDITION: ALoad.conforms(s); Make sure we have value graph nodes for a constant value

Parameters:

s - the instruction in question

processUnary

private void processUnary(Instruction s)

Update the value graph to account for a given Unary instruction.

PRECONDITION: Unary.conforms(s);

Parameters:

s - the instruction in question

processGuardedUnary

private void processGuardedUnary(Instruction s)

Update the value graph to account for a given GuardedUnary instruction.

PRECONDITION: GuardedUnary.conforms(s); Careful: we define two Guarded Unaries to be equivalent regardless of whether the guards are equivalent!

Parameters:

s - the instruction in question

processNullCheck

private void processNullCheck(Instruction s)

Update the value graph to account for a given NullCheck instruction.

PRECONDITION: NullCheck.conforms(s);

Parameters:

s - the instruction in question

processZeroCheck

private void processZeroCheck(Instruction s)

Update the value graph to account for a given NullCheck instruction.

PRECONDITION: ZeroCheck.conforms(s);

Parameters:

s - the instruction in question

processBinary

private void processBinary(Instruction s)

Update the value graph to account for a given Binary instruction.

PRECONDITION: Binary.conforms(s);

Parameters:

s - the instruction in question

processGuardedBinary

private void processGuardedBinary(Instruction s)

Update the value graph to account for a given GuardedBinary instruction.

PRECONDITION: GuardedBinary.conforms(s); Careful: we define two Guarded Binaries to be equivalent regardless of whether the guards are equivalent!

Parameters:

s - the instruction in question

processInlineGuard

private void processInlineGuard(Instruction s)

Update the value graph to account for a given InlineGuard instruction.

PRECONDITION: InlineGuard.conforms(s);

Parameters:

s - the instruction in question

processIfCmp

private void processIfCmp(Instruction s)

Update the value graph to account for a given IfCmp instruction.

PRECONDITION: IfCmp.conforms(s);

Parameters:

s - the instruction in question

processPhi

private void processPhi(Instruction s)

Update the value graph to account for a given Phi instruction.

PRECONDITION: Phi.conforms(s);

Parameters:

s - the instruction in question

processPrologue

private void processPrologue(Instruction s)

Update the value graph to account for an IR_PROLOGUE instruction

PRECONDITION: Prologue.conforms(s);

Parameters:

s - the instruction in question

processCall

private void processCall(Instruction s)

Update the value graph to account for a given Call instruction.

PRECONDITION: Call.conforms(s);

Parameters:

s - the instruction in question

findOrCreateVertex

private ValueGraphVertex findOrCreateVertex(Object var)

Find or create an ValueGraphVertex corresponding to a given variable.

Parameters:

var - The variable

Returns:

A value graph vertex corresponding to this variable

findOrCreateVertex

private ValueGraphVertex findOrCreateVertex(Register r)

Find or create an ValueGraphVertex corresponding to a given register

Parameters:

r - the register

Returns:

a value graph vertex corresponding to this variable

findOrCreateVertex

private ValueGraphVertex findOrCreateVertex(ConstantOperand op)

Find or create an ValueGraphVertex corresponding to a given constant operand

Parameters:

op - the constant operand

Returns:

a value graph vertex corresponding to this variable

findOrCreateVertex

private ValueGraphVertex findOrCreateVertex(TypeOperand op)

Find or create an ValueGraphVertex corresponding to a given type operand

Parameters:

op - the operand in question

Returns:

a value graph vertex corresponding to this type

findOrCreateVertex

private ValueGraphVertex findOrCreateVertex(MethodOperand op)

Find or create an ValueGraphVertex corresponding to a given method operand

Parameters:

op - the operand in question

Returns:

a value graph vertex corresponding to this type

findOrCreateVertex

private ValueGraphVertex findOrCreateVertex(ConditionOperand op)

Find or create an ValueGraphVertex corresponding to a given method operand

Parameters:

op - the operand in question

Returns:

a value graph vertex corresponding to this type

link

private void link(ValueGraphVertex src,
                  ValueGraphVertex target,
                  int pos)

Link two vertices in the value graph

Parameters:

src - the def

target - the use

pos - the position of target in the set of uses

bypassMoves

private Operand bypassMoves(Operand op)

Bypass MOVE instructions that def an operand: return the first def in the chain that is not the result of a MOVE instruction.

Note: treat PI instructions like MOVES

Parameters:

op - the RegisterOperand