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."

Field Summary

Fields

Modifier and Type	Field and Description
private SpaceEffGraph	graph Internal graph structure of the value graph.
private HashMap<Object,ValueGraphVertex>	nameMap A mapping from name to value graph vertex.

Constructor Summary

Constructors

Constructor and Description
ValueGraph(IR ir) Construct a value graph from an IR.

Method Summary

Modifier and Type	Method and Description
private void	addRegisterNodes(IR ir) Add a node to the value graph for every symbolic register.
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.
private void	computeClosure() Due to PI nodes and Moves, the initial label for a register may be another register.
Enumeration<GraphNode>	enumerateVertices() Enumerate the vertices in the value graph.
private ValueGraphVertex	findOrCreateVertex(ConditionOperand op) Find or create an ValueGraphVertex corresponding to a given method operand
private ValueGraphVertex	findOrCreateVertex(ConstantOperand op) Find or create an ValueGraphVertex corresponding to a given constant operand
private ValueGraphVertex	findOrCreateVertex(MethodOperand op) Find or create an ValueGraphVertex corresponding to a given method operand
private ValueGraphVertex	findOrCreateVertex(Object var) Find or create an ValueGraphVertex corresponding to a given variable.
private ValueGraphVertex	findOrCreateVertex(Register r) Find or create an ValueGraphVertex corresponding to a given register
private ValueGraphVertex	findOrCreateVertex(TypeOperand op) Find or create an ValueGraphVertex corresponding to a given type operand
ValueGraphVertex	getVertex(Object name) Return the vertex which has a given name.
private void	link(ValueGraphVertex src, ValueGraphVertex target, int pos) Link two vertices in the value graph
private void	processALoad(Instruction s) Update the value graph to account for a given ALOAD instruction.
private void	processAStore(Instruction s) Update the value graph to account for a given ASTORE instruction.
private void	processBinary(Instruction s) Update the value graph to account for a given Binary instruction.
private void	processCall(Instruction s) Update the value graph to account for a given Call instruction.
private void	processGuardedBinary(Instruction s) Update the value graph to account for a given GuardedBinary instruction.
private void	processGuardedUnary(Instruction s) Update the value graph to account for a given GuardedUnary instruction.
private void	processIfCmp(Instruction s) Update the value graph to account for a given IfCmp instruction.
private void	processInlineGuard(Instruction s) Update the value graph to account for a given InlineGuard instruction.
private void	processInstruction(Instruction s) Update the value graph to account for a given instruction.
private void	processMove(Instruction s) Update the value graph to account for a given MOVE instruction.
private void	processNew(Instruction s) Update the value graph to account for a given NEW instruction.
private void	processNewArray(Instruction s) Update the value graph to account for a given NEWARRAY instruction.
private void	processNullCheck(Instruction s) Update the value graph to account for a given NullCheck instruction.
private void	processPhi(Instruction s) Update the value graph to account for a given Phi instruction.
private void	processPi(Instruction s) Update the value graph to account for a given PI instruction.
private void	processPrologue(Instruction s) Update the value graph to account for an IR_PROLOGUE instruction PRECONDITION: Prologue.conforms(s);
private void	processPutField(Instruction s) Update the value graph to account for a given PUTFIELD instruction.
private void	processPutStatic(Instruction s) Update the value graph to account for a given PUTSTATIC instruction.
private void	processUnary(Instruction s) Update the value graph to account for a given Unary instruction.
private void	processZeroCheck(Instruction s) Update the value graph to account for a given NullCheck instruction.
String	toString() Return a String representation of the value graph.

Methods inherited from class java.lang.Object

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

Field Detail

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.

Constructor Detail

ValueGraph

ValueGraph(IR ir)

Construct a value graph from an IR.

PRECONDITION: The IR must be in SSA form.

Parameters:

ir - the IR

Method Detail

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

Returns:

the first def in the chain that is not the result of move if it can be found, the original operand otherwise