GlobalValueNumberState (Jikes RVM API)

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.

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

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
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

Class GlobalValueNumberState

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

UNKNOWN

DEBUG

NO_PARAM_ALIAS

B

valueGraph

workList

Constructor Detail

GlobalValueNumberState

Method Detail

globalValueNumber

mergeClasses

DS

DD

DD

congruenceClass

getValueNumber

printValueNumbers

initialize

findOrCreateCongruenceClass

createCongruenceClass

initializeWorkList

partitionClass

addDependentClassesToWorklist

findCongruenceMatch

checkCongruence

checkCongruence

isConstant

isBornAtAllocation