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

Field Summary

Fields

Modifier and Type	Field and Description
private ArrayList<GVCongruenceClass>	B ArrayList of GVCongruenceClass, indexed by value number.
private static boolean	DEBUG Print verbose debugging output?
private static boolean	NO_PARAM_ALIAS Assume parameters are not aliased?
static int	UNKNOWN Constant used to flag "unknown" value numbers
(package private) ValueGraph	valueGraph The value graph.
private Stack<GVCongruenceClass>	workList Stack used for a work list.

Constructor Summary

Constructors

Constructor and Description
GlobalValueNumberState(IR ir) Construct a structure to hold global value number results for an IR.

Method Summary

Modifier and Type	Method and Description
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
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?
private boolean	checkCongruence(ValueGraphVertex v1, ValueGraphVertex v2) Does the current state of the algorithm optimistically assume that two nodes are congruent?
(package private) GVCongruenceClass	congruenceClass(Object name)
private GVCongruenceClass	createCongruenceClass(Object label) Given a label, return a new congruence class for that label.
(package private) boolean	DD(int v1, int v2) Definitely-different relation for two value numbers.
(package private) boolean	DD(Object name1, Object name2) Definitely-different relation.
(package private) boolean	DS(Object name1, Object name2) Definitely-same relation.
private int	findCongruenceMatch(ArrayList<GVCongruenceClass> vector, ValueGraphVertex v) Does vertex v belong to any congruence class in a vector?
private GVCongruenceClass	findOrCreateCongruenceClass(Object label, HashMap<Object,GVCongruenceClass> labelMap) Given a label, return the congruence class for that label.
(package private) int	getValueNumber(Object name) Return the (integer) value number for a given variable
private void	globalValueNumber() Compute node congruence over the value number graph.
private void	initialize() Initialize the congruence classes, assuming that all nodes with the same label are congruent.
private void	initializeWorkList() Initialize the work list.
private static boolean	isBornAtAllocation(Object label)
private static boolean	isConstant(Object label)
(package private) void	mergeClasses(ValueGraphVertex v1, ValueGraphVertex v2)
private void	partitionClass(GVCongruenceClass partition) Partition a congruence class.
(package private) void	printValueNumbers() Print the value numbers for each node in the value graph.

Methods inherited from class java.lang.Object

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

Field Detail

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.

Constructor Detail

GlobalValueNumberState

GlobalValueNumberState(IR ir)

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

Parameters:

ir - governing IR

Method Detail

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)

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

Returns:

whether the notes are assumed to be congruent

isConstant

private static boolean isConstant(Object label)

Parameters:

label - a label

Returns:

whether a given label indicates that the object has a constant value

isBornAtAllocation

private static boolean isBornAtAllocation(Object label)

Parameters:

label - a label

Returns:

whether a given label indicates that the object is created at an allocation site