org.jikesrvm.compilers.opt.ssa
Class GlobalValueNumberState

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

public final class GlobalValueNumberState
extends Object

This class holds the results of global value numbering. ala Alpern, Wegman and Zadeck, PoPL 88. See Muchnick p.348 for a discussion (which is quite buggy, should have stuck to the dragon book, which gives a high-level description of the correct algorithm on page 143).

UNKNOWN

public static final int UNKNOWN

Constant used to flag "unknown" value numbers

See Also:

Constant Field Values

DEBUG

private static final boolean DEBUG

Print verbose debugging output?

See Also:

Constant Field Values

NO_PARAM_ALIAS

private static final boolean NO_PARAM_ALIAS

Assume parameters are not aliased?

See Also:

Constant Field Values

B

private final ArrayList<GVCongruenceClass> B

ArrayList of GVCongruenceClass, indexed by value number.

valueGraph

final ValueGraph valueGraph

The value graph.

workList

private final Stack<GVCongruenceClass> workList

Stack used for a work list.

GlobalValueNumberState

GlobalValueNumberState(IR ir)

Construct a structure to hold global value number results for an IR.

Parameters:

ir - governing IR

globalValueNumber

private void globalValueNumber()

Compute node congruence over the value number graph.

Algorithm: Muchnick pp. 348-355

Note: the Muchnick algorithm is buggy. In particular, it does not put all needed congruence classes on the worklist.

Two nodes in the value graph are congruent if one of the following holds:

• they are the same node
• their labels are identical constants
• they have the same operators and their operands are congruent

Optimistic algorithm:

• Initially assume all nodes with the same label are congruent
• start a work list with all congruence classes that have multiple operands
• choose a congruence class from the worklist. partition its elements into new congruence classes if we can discover that they are not congruent.
• Add any newly created congruence classes to the work list.
• (Here's the step Muchnick omits:) For each class C which has a dependence on any of the newly created congruence classes, add C to the work list
• repeat until work list is empty

The following method breaks Muchnick's algorithm, which will assign m and n the same value number. Muchnick's problem is that it does not put the congruence class for 'int_mul' back on the worklist when we discover, for example, that i is not congruent to k

   public int foo(int a, int b, int c, int d, int e, int f, int g, int h) {
      int i = a+b;
      int j = c+d;
      int k = e+f;
      int l = g+h;
      int m = i * j;
      int n = k * l;
      int o = m/n;
      return o;
   }
  

mergeClasses

void mergeClasses(ValueGraphVertex v1,
                  ValueGraphVertex v2)

Merge the congruence classes containing vertices v1 and v2.;

DS

boolean DS(Object name1,
           Object name2)

Definitely-same relation.

Parameters:

name1 - first variable

name2 - second variable

Returns:

true iff the value numbers for two variables are equal

DD

boolean DD(int v1,
           int v2)

Definitely-different relation for two value numbers. Returns true for the following cases:

• v1 and v2 are both constants, but don't match
• v1 and v2 both result from NEW statements, but don't match
• one of v1 and v2 is a parameter, and the other results from a new statement

TODO: add more smarts

Parameters:

v1 - first value number

v2 - second value number

Returns:

true iff the value numbers for two variables are definitely different

DD

boolean DD(Object name1,
           Object name2)

Definitely-different relation. Returns true for the following cases:

• name1 and name2 are both constants, but don't match
• name1 and name2 both result from NEW statements, but don't match
• one of name1 and name2 is a parameter, and the other results from a new statement

TODO: add more smarts

Parameters:

name1 - name of first object to compare

name2 - name of second object to compare

Returns:

true iff the value numbers for two variables are definitely different

congruenceClass

GVCongruenceClass congruenceClass(Object name)

getValueNumber

int getValueNumber(Object name)

Return the (integer) value number for a given variable

Parameters:

name - name of the variable to look up

Returns:

its value number

printValueNumbers

void printValueNumbers()

Print the value numbers for each node in the value graph.

initialize

private void initialize()

Initialize the congruence classes, assuming that all nodes with the same label are congruent.

findOrCreateCongruenceClass

private GVCongruenceClass findOrCreateCongruenceClass(Object label,
                                                      HashMap<Object,GVCongruenceClass> labelMap)

Given a label, return the congruence class for that label. Create one if needed.

Parameters:

label - the label of a congruence class

labelMap - a mapping from labels to congruence class

Returns:

the congruence class for the label.

createCongruenceClass

private GVCongruenceClass createCongruenceClass(Object label)

Given a label, return a new congruence class for that label.

Parameters:

label - the label of a congruence class

Returns:

the congruence class for the label.

initializeWorkList

private void initializeWorkList()

Initialize the work list. A congruence class gets put on the work list if any two nodes in the class point to corresponding targets in separate partitions.

partitionClass

private void partitionClass(GVCongruenceClass partition)

Partition a congruence class.

Parameters:

partition - the class to partition

addDependentClassesToWorklist

private void addDependentClassesToWorklist(GVCongruenceClass c)

Assuming congruence class c has changed: find all other classes that might be affected, and add them to the worklist

Parameters:

c - the congruence class that has changed

findCongruenceMatch

private int findCongruenceMatch(ArrayList<GVCongruenceClass> vector,
                                ValueGraphVertex v)

Does vertex v belong to any congruence class in a vector? If so, returns the value number of the matching congruence class. If none found, returns -1.

Parameters:

vector - a vector of congruence classes

v - the vertex to search for

Returns:

the value number corresponding to the congruence class containing v. -1 iff no such class is found.

checkCongruence

private boolean checkCongruence(ValueGraphVertex v,
                                GVCongruenceClass c)

Does the current state of the algorithm optimistically assume that a vertex v is congruent to the vertices in a congruence class? Note: this can return true even if if the value numbers don't currently match.

Parameters:

v - the vertex in question

c - the congurence class to check

Returns:

true or false

checkCongruence

private boolean checkCongruence(ValueGraphVertex v1,
                                ValueGraphVertex v2)

Does the current state of the algorithm optimistically assume that two nodes are congruent? Note: this can return false even if the value numbers are currently the same.

Parameters:

v1 - first vertex

v2 - second vertex

isConstant

private static boolean isConstant(Object label)

Does a given label indicate that the object has a constant value?

isBornAtAllocation

private static boolean isBornAtAllocation(Object label)

Does a given label indicate that the object is created at an allocation site?