Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv30248
Modified Files:
OPT_GVCongruenceClass.java OPT_GlobalValueNumber.java
OPT_GlobalValueNumberState.java OPT_ValueGraph.java
OPT_ValueGraphEdge.java OPT_ValueGraphParamLabel.java
OPT_ValueGraphVertex.java OPT_ValueNumberPair.java
Log Message:
Changes to GVN, make fields private and final where possible
Index: OPT_GVCongruenceClass.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_GVCongruenceClass.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** OPT_GVCongruenceClass.java 5 Dec 2003 23:48:27 -0000 1.5
--- OPT_GVCongruenceClass.java 24 May 2006 12:09:21 -0000 1.6
***************
*** 16,32 ****
* A label representing a property of this congruence class.
*/
! Object label;
/**
* A value number representing this congruence class.
*/
! int valueNumber;
/**
* How many vertices in this congruence class represent parameters?
*/
! int nParameter;
/**
* The set of vertices in this congruence class
*/
! HashSet vertices = new HashSet(1);
/**
--- 16,32 ----
* A label representing a property of this congruence class.
*/
! private final Object label;
/**
* A value number representing this congruence class.
*/
! private final int valueNumber;
/**
* How many vertices in this congruence class represent parameters?
*/
! private int nParameter;
/**
* The set of vertices in this congruence class
*/
! private final HashSet vertices;
/**
***************
*** 34,38 ****
* - saves having to find one
*/
! OPT_ValueGraphVertex representativeV;
/**
--- 34,38 ----
* - saves having to find one
*/
! private OPT_ValueGraphVertex representativeV;
/**
***************
*** 45,48 ****
--- 45,49 ----
this.valueNumber = valueNumber;
this.label = label;
+ vertices = new HashSet(1);
}
Index: OPT_GlobalValueNumber.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_GlobalValueNumber.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** OPT_GlobalValueNumber.java 23 Aug 2002 11:34:17 -0000 1.7
--- OPT_GlobalValueNumber.java 24 May 2006 12:09:21 -0000 1.8
***************
*** 16,20 ****
*/
class OPT_GlobalValueNumber extends OPT_CompilerPhase {
! static final boolean DEBUG = false;
/**
--- 16,21 ----
*/
class OPT_GlobalValueNumber extends OPT_CompilerPhase {
! /** Print verbose debugging output? */
! private static final boolean DEBUG = false;
/**
***************
*** 50,54 ****
// compute global value numbers
OPT_GlobalValueNumberState gvn = new OPT_GlobalValueNumberState(ir);
! gvn.globalValueNumber();
if (DEBUG)
gvn.printValueNumbers();
--- 51,55 ----
// compute global value numbers
OPT_GlobalValueNumberState gvn = new OPT_GlobalValueNumberState(ir);
!
if (DEBUG)
gvn.printValueNumbers();
Index: OPT_ValueNumberPair.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_ValueNumberPair.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** OPT_ValueNumberPair.java 22 Aug 2002 15:01:29 -0000 1.6
--- OPT_ValueNumberPair.java 24 May 2006 12:09:21 -0000 1.7
***************
*** 11,20 ****
*/
class OPT_ValueNumberPair {
! int v1; // the value number of an array pointer
! int v2; // the value number of an array index
!
! OPT_ValueNumberPair() {
! }
!
OPT_ValueNumberPair(int v1, int v2) {
this.v1 = v1;
--- 11,20 ----
*/
class OPT_ValueNumberPair {
! /** the value number of an array pointer */
! final int v1;
! /** the value number of an array index */
! final int v2;
!
! /** Construct a pair from the given arguments */
OPT_ValueNumberPair(int v1, int v2) {
this.v1 = v1;
***************
*** 22,25 ****
--- 22,26 ----
}
+ /** Copy a pair */
OPT_ValueNumberPair(OPT_ValueNumberPair p) {
this.v1 = p.v1;
Index: OPT_ValueGraphParamLabel.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_ValueGraphParamLabel.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** OPT_ValueGraphParamLabel.java 20 Aug 2002 21:35:18 -0000 1.3
--- OPT_ValueGraphParamLabel.java 24 May 2006 12:09:21 -0000 1.4
***************
*** 10,15 ****
* @author Dave Grove
*/
! class OPT_ValueGraphParamLabel {
! int paramNum;
OPT_ValueGraphParamLabel(int pn) {
--- 10,15 ----
* @author Dave Grove
*/
! final class OPT_ValueGraphParamLabel {
! private final int paramNum;
OPT_ValueGraphParamLabel(int pn) {
Index: OPT_ValueGraphEdge.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_ValueGraphEdge.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** OPT_ValueGraphEdge.java 20 Aug 2002 21:35:16 -0000 1.5
--- OPT_ValueGraphEdge.java 24 May 2006 12:09:21 -0000 1.6
***************
*** 5,10 ****
package com.ibm.JikesRVM.opt;
- import java.util.*;
-
/**
* This class implements an edge in the value graph used in global value
--- 5,8 ----
***************
*** 15,19 ****
* @author Stephen Fink
*/
! class OPT_ValueGraphEdge extends OPT_SpaceEffGraphEdge {
OPT_ValueGraphEdge (OPT_ValueGraphVertex src, OPT_ValueGraphVertex target) {
--- 13,17 ----
* @author Stephen Fink
*/
! final class OPT_ValueGraphEdge extends OPT_SpaceEffGraphEdge {
OPT_ValueGraphEdge (OPT_ValueGraphVertex src, OPT_ValueGraphVertex target) {
***************
*** 24,28 ****
OPT_ValueGraphVertex src = (OPT_ValueGraphVertex)fromNode();
OPT_ValueGraphVertex dest = (OPT_ValueGraphVertex)toNode();
! return src.name + " --> " + dest.name;
}
}
--- 22,26 ----
OPT_ValueGraphVertex src = (OPT_ValueGraphVertex)fromNode();
OPT_ValueGraphVertex dest = (OPT_ValueGraphVertex)toNode();
! return src.getName() + " --> " + dest.getName();
}
}
Index: OPT_GlobalValueNumberState.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_GlobalValueNumberState.java,v
retrieving revision 1.11
retrieving revision 1.12
diff -C2 -d -r1.11 -r1.12
*** OPT_GlobalValueNumberState.java 5 Jan 2005 03:14:48 -0000 1.11
--- OPT_GlobalValueNumberState.java 24 May 2006 12:09:21 -0000 1.12
***************
*** 8,13 ****
import com.ibm.JikesRVM.opt.ir.*;
! import java.util.*;
! /*
* This class holds the results of global value numbering.
* ala Alpern, Wegman and Zadeck, PoPL 88.
--- 8,17 ----
import com.ibm.JikesRVM.opt.ir.*;
! import java.util.ArrayList;
! import java.util.Enumeration;
! import java.util.HashMap;
! import java.util.Iterator;
! import java.util.Stack;
! /**
* This class holds the results of global value numbering.
* ala Alpern, Wegman and Zadeck, PoPL 88.
***************
*** 26,34 ****
* Print verbose debugging output?
*/
! final static boolean DEBUG = false;
/**
* Assume parameters are not aliased?
*/
! private final static boolean NO_PARAM_ALIAS = false;
/**
--- 30,55 ----
* Print verbose debugging output?
*/
! final private static boolean DEBUG = false;
/**
* Assume parameters are not aliased?
*/
! final private static boolean NO_PARAM_ALIAS = false;
!
! /**
! * Governing IR
! */
! private final OPT_IR ir;
! /**
! * ArrayList of OPT_GVCongruenceClass, indexed by value number.
! */
! private final ArrayList B;
! /**
! * The value graph.
! */
! final OPT_ValueGraph valueGraph;
! /**
! * Stack used for a work list.
! */
! private final Stack workList;
/**
***************
*** 39,42 ****
--- 60,67 ----
OPT_GlobalValueNumberState (OPT_IR ir) {
this.ir = ir;
+ B = new ArrayList();
+ workList = new Stack();
+ valueGraph = new OPT_ValueGraph(ir);
+ globalValueNumber();
}
***************
*** 89,94 ****
* </pre>
*/
! public void globalValueNumber () {
! valueGraph = new OPT_ValueGraph(ir);
if (DEBUG)
VM.sysWrite(valueGraph.toString());
--- 114,118 ----
* </pre>
*/
! private void globalValueNumber () {
if (DEBUG)
VM.sysWrite(valueGraph.toString());
***************
*** 109,113 ****
* Merge the congruence classes containing vertices v1 and v2.;
*/
! public void mergeClasses(OPT_ValueGraphVertex v1, OPT_ValueGraphVertex v2) {
if (DEBUG) {
System.out.println("@@@@ mergeClasses called with v1 = " + v1 +
--- 133,137 ----
* Merge the congruence classes containing vertices v1 and v2.;
*/
! void mergeClasses(OPT_ValueGraphVertex v1, OPT_ValueGraphVertex v2) {
if (DEBUG) {
System.out.println("@@@@ mergeClasses called with v1 = " + v1 +
***************
*** 145,149 ****
* @return true iff the value numbers for two variables are equal
*/
! public boolean DS (Object name1, Object name2) {
OPT_ValueGraphVertex v1 = valueGraph.getVertex(name1);
OPT_ValueGraphVertex v2 = valueGraph.getVertex(name2);
--- 169,173 ----
* @return true iff the value numbers for two variables are equal
*/
! boolean DS (Object name1, Object name2) {
OPT_ValueGraphVertex v1 = valueGraph.getVertex(name1);
OPT_ValueGraphVertex v2 = valueGraph.getVertex(name2);
***************
*** 169,173 ****
* different
*/
! public boolean DD (int v1, int v2) {
if ((v1 == -1) || (v2 == -1))
return false;
--- 193,197 ----
* different
*/
! boolean DD (int v1, int v2) {
if ((v1 == -1) || (v2 == -1))
return false;
***************
*** 232,236 ****
* different
*/
! public boolean DD (Object name1, Object name2) {
OPT_ValueGraphVertex v1 = valueGraph.getVertex(name1);
OPT_ValueGraphVertex v2 = valueGraph.getVertex(name2);
--- 256,260 ----
* different
*/
! boolean DD (Object name1, Object name2) {
OPT_ValueGraphVertex v1 = valueGraph.getVertex(name1);
OPT_ValueGraphVertex v2 = valueGraph.getVertex(name2);
***************
*** 238,242 ****
}
! public OPT_GVCongruenceClass congruenceClass(Object name) {
OPT_ValueGraphVertex v = valueGraph.getVertex(name);
return ((OPT_GVCongruenceClass)B.get(v.getValueNumber()));
--- 262,266 ----
}
! OPT_GVCongruenceClass congruenceClass(Object name) {
OPT_ValueGraphVertex v = valueGraph.getVertex(name);
return ((OPT_GVCongruenceClass)B.get(v.getValueNumber()));
***************
*** 249,253 ****
* @return its value number
*/
! public int getValueNumber (Object name) {
OPT_ValueGraphVertex v = valueGraph.getVertex(name);
if (v == null)
--- 273,277 ----
* @return its value number
*/
! int getValueNumber (Object name) {
OPT_ValueGraphVertex v = valueGraph.getVertex(name);
if (v == null)
***************
*** 259,288 ****
* Print the value numbers for each node in the value graph.
*/
! public void printValueNumbers () {
for (Enumeration e = valueGraph.enumerateVertices(); e.hasMoreElements();) {
OPT_ValueGraphVertex v = (OPT_ValueGraphVertex)e.nextElement();
int valueNumber = v.getValueNumber();
OPT_GVCongruenceClass c = (OPT_GVCongruenceClass)B.get(valueNumber);
! System.out.println(v.name + " " + valueNumber + " " + c.getLabel());
}
}
- /**
- * Governing IR
- */
- OPT_IR ir;
- /**
- * ArrayList of OPT_GVCongruenceClass, indexed by value number.
- */
- ArrayList B = new ArrayList(); // ArrayList of OPT_GVCongruenceClass,
- /**
- * The value graph.
- */
- OPT_ValueGraph valueGraph;
- /**
- * Stack used for a work list.
- */
- Stack workList = new Stack();
-
/**
* Initialize the congruence classes, assuming that all nodes
--- 283,295 ----
* Print the value numbers for each node in the value graph.
*/
! void printValueNumbers () {
for (Enumeration e = valueGraph.enumerateVertices(); e.hasMoreElements();) {
OPT_ValueGraphVertex v = (OPT_ValueGraphVertex)e.nextElement();
int valueNumber = v.getValueNumber();
OPT_GVCongruenceClass c = (OPT_GVCongruenceClass)B.get(valueNumber);
! System.out.println(v.getName() + " " + valueNumber + " " + c.getLabel());
}
}
/**
* Initialize the congruence classes, assuming that all nodes
Index: OPT_ValueGraph.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_ValueGraph.java,v
retrieving revision 1.22
retrieving revision 1.23
diff -C2 -d -r1.22 -r1.23
*** OPT_ValueGraph.java 18 May 2006 12:58:46 -0000 1.22
--- OPT_ValueGraph.java 24 May 2006 12:09:21 -0000 1.23
***************
*** 6,10 ****
import com.ibm.JikesRVM.*;
! import java.util.*;
import com.ibm.JikesRVM.opt.ir.*;
--- 6,11 ----
import com.ibm.JikesRVM.*;
! import java.util.Enumeration;
! import java.util.HashMap;
import com.ibm.JikesRVM.opt.ir.*;
***************
*** 14,28 ****
* discussion.
*
* @author Stephen Fink
*/
! class OPT_ValueGraph implements OPT_Operators {
/**
* Construct a value graph from an IR.
*
! * <p> <b> PRECONDITION:</b> The IR <em> must </em> be in SSA form.
* @param ir the IR
*/
OPT_ValueGraph(OPT_IR ir) {
// TODO!!: compute register lists incrementally
// we need register lists in order to call OPT_Register.getFirstDef()
--- 15,48 ----
* discussion.
*
+ * From Muchnick, "the <em>value graph</em> 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 postion that each operand has with repsect to
+ * the given operator or function."
+ *
* @author Stephen Fink
*/
! final class OPT_ValueGraph implements OPT_Operators {
!
! /**
! * Internal graph structure of the value graph.
! */
! private final OPT_SpaceEffGraph graph;
! /**
! * A mapping from name to value graph vertex.
! */
! private final HashMap nameMap;
/**
* Construct a value graph from an IR.
*
! * <p><b> PRECONDITION:</b> The IR <em> must </em> be in SSA form.
* @param ir the IR
*/
OPT_ValueGraph(OPT_IR ir) {
+ graph = new OPT_SpaceEffGraph();
+ nameMap = new HashMap();
// TODO!!: compute register lists incrementally
// we need register lists in order to call OPT_Register.getFirstDef()
***************
*** 45,59 ****
* register label was not removed.
*/
! void computeClosure() {
for (Enumeration e = enumerateVertices(); e.hasMoreElements(); ) {
OPT_ValueGraphVertex v = (OPT_ValueGraphVertex)e.nextElement();
! if (v.name instanceof OPT_Register){
! if (v.label instanceof OPT_Register) {
! if (v.name != v.label) {
! OPT_ValueGraphVertex v2 = getVertex(v.label);
if (VM.VerifyAssertions) {
! if (v2.name instanceof OPT_Register &&
! v2.label instanceof OPT_Register &&
! v2.label != v2.name) {
VM._assert(false);
}
--- 65,79 ----
* register label was not removed.
*/
! private void computeClosure() {
for (Enumeration e = enumerateVertices(); e.hasMoreElements(); ) {
OPT_ValueGraphVertex v = (OPT_ValueGraphVertex)e.nextElement();
! if (v.getName() instanceof OPT_Register){
! if (v.getLabel() instanceof OPT_Register) {
! if (v.getName() != v.getLabel()) {
! OPT_ValueGraphVertex v2 = getVertex(v.getLabel());
if (VM.VerifyAssertions) {
! if (v2.getName() instanceof OPT_Register &&
! v2.getLabel() instanceof OPT_Register &&
! v2.getLabel() != v2.getName()) {
VM._assert(false);
}
***************
*** 113,125 ****
}
- /**
- * Internal graph structure of the value graph.
- */
- private OPT_SpaceEffGraph graph = new OPT_SpaceEffGraph();
- /**
- * A mapping from name to value graph vertex.
- */
- private HashMap nameMap = new HashMap();
-
/**
* Add a node to the value graph for every symbolic register.
--- 133,136 ----
***************
*** 235,239 ****
* <p><b>PRECONDITION:</b> <code> New.conforms(s); </code>
*
! * <p>For a new instruction, we always create a new vertex.
*
* @param s the instruction in question
--- 246,250 ----
* <p><b>PRECONDITION:</b> <code> New.conforms(s); </code>
*
! * For a new instruction, we always create a new vertex.
*
* @param s the instruction in question
***************
*** 269,273 ****
* <p><b>PRECONDITION:</b> <code> PutField.conforms(s); </code>
*
! * <p> Make sure we have value graph nodes for a constant value
*
* @param s the instruction in question
--- 280,284 ----
* <p><b>PRECONDITION:</b> <code> PutField.conforms(s); </code>
*
! * Make sure we have value graph nodes for a constant value
*
* @param s the instruction in question
***************
*** 301,305 ****
* <p><b>PRECONDITION:</b> <code> AStore.conforms(s); </code>
*
! * <p>Make sure we have value graph nodes for a constant value
*
* @param s the instruction in question
--- 312,316 ----
* <p><b>PRECONDITION:</b> <code> AStore.conforms(s); </code>
*
! * Make sure we have value graph nodes for a constant value
*
* @param s the instruction in question
***************
*** 321,325 ****
* <p><b>PRECONDITION:</b> <code> ALoad.conforms(s); </code>
*
! * <p>Make sure we have value graph nodes for a constant value
*
* @param s the instruction in question
--- 332,336 ----
* <p><b>PRECONDITION:</b> <code> ALoad.conforms(s); </code>
*
! * Make sure we have value graph nodes for a constant value
*
* @param s the instruction in question
***************
*** 724,728 ****
* in the chain that is not the result of a MOVE instruction.
*
! * <p>Note: treat PI instructions like MOVES
*
* @param op the OPT_RegisterOperand
--- 735,739 ----
* in the chain that is not the result of a MOVE instruction.
*
! * Note: treat PI instructions like MOVES
*
* @param op the OPT_RegisterOperand
Index: OPT_ValueGraphVertex.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_ValueGraphVertex.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** OPT_ValueGraphVertex.java 23 Aug 2002 11:34:22 -0000 1.6
--- OPT_ValueGraphVertex.java 24 May 2006 12:09:21 -0000 1.7
***************
*** 16,25 ****
* @author Stephen Fink
*/
! class OPT_ValueGraphVertex extends OPT_SpaceEffGraphNode {
! Object name; // the name of the variable defined by this node
! Object label; // the name of the operator that does the definition
! int valueNumber; // integer value number
! OPT_ValueGraphVertex[] targets; // operand vertices, in order
! int arity; // number of operands needed
OPT_ValueGraphVertex (Object name) {
--- 16,25 ----
* @author Stephen Fink
*/
! final class OPT_ValueGraphVertex extends OPT_SpaceEffGraphNode {
! private final Object name; // the name of the variable defined by this node
! private Object label; // the name of the operator that does the definition
! private int valueNumber; // integer value number
! private OPT_ValueGraphVertex[] targets; // operand vertices, in order
! private int arity; // number of operands needed
OPT_ValueGraphVertex (Object name) {
|