Jikes RVM

Update of /cvsroot/jikesrvm/rvm/src/vm/utility
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv4412/src/vm/utility

Modified Files:
	VM_HashSet.java 
Log Message:
real implementation of VM_HashMap.  Not very fancy, but seems to get the job done.

Index: VM_HashSet.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/utility/VM_HashSet.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** VM_HashSet.java	22 May 2006 12:05:46 -0000	1.1
--- VM_HashSet.java	29 May 2006 02:29:30 -0000	1.2
***************
*** 5,31 ****
  package com.ibm.JikesRVM.util;
  
  
  /**
!  * Stripped down implementation of HashMap data structure for use
   * by core parts of the JikesRVM runtime.
   *
!  * While developing; have a bogus impl by simply subclassing java.util.HashSet
!  * This won't actually fix anything, but enables me to see how widely used this
!  * data structure is going to need to be and what API I have to support on it.
!  *
!  * TODO: This should be a final class; rewrite subclasses to let us do that.
!  * 
   * @author Dave Grove
   */
! public class VM_HashSet extends java.util.HashSet {
  
    public VM_HashSet() {
!     super();
    }
  
    public VM_HashSet(int size) {
!     super(size);
    }
-   
  }
  
--- 5,47 ----
  package com.ibm.JikesRVM.util;
  
+ import java.util.Iterator;
  
  /**
!  * Stripped down implementation of HashSet for use
   * by core parts of the JikesRVM runtime.
   *
!  * TODO: Make this more space efficient by implementing it directly
!  *       instead of creating a silly HashMap to back it.
   * @author Dave Grove
   */
! public final class VM_HashSet {
  
+   private final VM_HashMap map;
+   
    public VM_HashSet() {
!     map = new VM_HashMap();
    }
  
    public VM_HashSet(int size) {
!     map = new VM_HashMap(size);
!   }
! 
!   public void add(Object o) {
!     map.put(o, null);
!   }
! 
!   public void remove(Object o) {
!     map.remove(o);
!   }
! 
!   public Iterator iterator() {
!     return map.keyIterator();
!   }
! 
!   public void addAll(VM_HashSet c) {
!     for (Iterator it = c.iterator(); it.hasNext(); ) {
!       add(it.next());
!     }
    }
  }

Update of /cvsroot/jikesrvm/rvm/src/vm/utility
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv4392/src/vm/utility

Modified Files:
	VM_HashMap.java 
Log Message:
real implementation of VM_HashMap.  Not very fancy, but seems to get the job done.

Index: VM_HashMap.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/utility/VM_HashMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** VM_HashMap.java	22 May 2006 12:05:46 -0000	1.2
--- VM_HashMap.java	29 May 2006 02:29:26 -0000	1.3
***************
*** 5,34 ****
  package com.ibm.JikesRVM.util;
  
! 
  /**
   * Stripped down implementation of HashMap data structure for use
   * by core parts of the JikesRVM runtime.
   *
!  * While developing; have a bogus impl by simply subclassing java.util.HashMap
   * This won't actually fix anything, but enables me to see how widely used this
   * data structure is going to need to be and what API I have to support on it.
   *
   * TODO: This should be a final class; rewrite subclasses to let us do that.
!  * 
   * @author Dave Grove
   */
! public class VM_HashMap extends java.util.HashMap {
  
    public VM_HashMap() {
!     super();
    }
        
    
    public VM_HashMap(int size) {
!     super(size);
    }
    
! }
  
  
      
--- 5,201 ----
  package com.ibm.JikesRVM.util;
  
! import java.util.Iterator;
! import java.util.NoSuchElementException;
!   
  /**
   * Stripped down implementation of HashMap data structure for use
   * by core parts of the JikesRVM runtime.
   *
!  * While developing; have a bogus impl by forwarding to java.util.HashMap
   * This won't actually fix anything, but enables me to see how widely used this
   * data structure is going to need to be and what API I have to support on it.
   *
   * TODO: This should be a final class; rewrite subclasses to let us do that.
!  *
   * @author Dave Grove
   */
! public class VM_HashMap {
!   private static final boolean STAGING = false;
!   private static final int DEFAULT_SIZE = 7;
!   private static final float LOAD = 3; /* bias to save space by default */
  
+     /* if STAGING */
+   private final java.util.HashMap map;
+   /* if !STAGING */
+   private Bucket[] buckets;
+   private int numElems = 0;
+   
    public VM_HashMap() {
!     this(DEFAULT_SIZE);
    }
        
    
    public VM_HashMap(int size) {
!     if (STAGING) {
!       map = new java.util.HashMap(size);
!     } else {
!       map = null;
!       buckets = new Bucket[size];
!     }
!   }
! 
!   public final Object get(Object key) {
!     if (STAGING) {
!       return map.get(key);
!     } else {
!       int bucketIdx = bucketIndex(key, buckets.length);
!       Bucket cur = buckets[bucketIdx];
!       while (cur != null && !cur.key.equals(key)) {
!         cur = cur.next;
!       }
!       if (cur == null) {
!         return null;
!       } else {
!         return cur.value;
!       }
!     }
!   }
! 
!   public final Object put(Object key, Object value) {
!     if (STAGING) {
!       return map.put(key, value);
!     } else {
!       if (numElems > (buckets.length * LOAD)) {
!         growMap();
!       }
! 
!       int bucketIdx = bucketIndex(key, buckets.length);
!       Bucket cur = buckets[bucketIdx];
!       while (cur != null && !cur.key.equals(key)) {
!         cur = cur.next;
!       }
!       if (cur != null) {
!         // replacing existing <key,value> pair
!         Object tmp = cur.value;
!         cur.value = value;
!         return tmp;
!       } else {
!         Bucket newBucket = new Bucket(key, value);
!         newBucket.next = buckets[bucketIdx];
!         buckets[bucketIdx] = newBucket;
!         numElems++;
!         return null;
!       }
!     }
!   }
! 
!   private final void growMap() {
!     Bucket[] newBuckets = new Bucket[buckets.length*2+1];
!     for (int i=0; i<buckets.length; i++) {
!       Bucket cur = buckets[i];
!       while (cur != null) {
!         Bucket next = cur.next;
!         int newIdx = bucketIndex(cur.key, newBuckets.length);
!         cur.next = newBuckets[newIdx];
!         newBuckets[newIdx] = cur;
!         cur = next;
!       }
!     }
!     buckets = newBuckets;
    }
    
!   public final Object remove(Object key) {
!     if (STAGING) {
!       return map.remove(key);
!     } else {
!       int bucketIdx = bucketIndex(key, buckets.length);
!       Bucket cur = buckets[bucketIdx];
!       Bucket prev = null;
!       while (cur != null && !cur.key.equals(key)) {
!         prev = cur;
!         cur = cur.next;
!       }
!       if (cur != null) {
!         if (prev == null) {
!           // removing first bucket in chain.
!           buckets[bucketIdx] = cur.next;
!         } else {
!           prev.next = cur.next;
!         }
!         numElems--;
!         return cur.value;
!       } else {
!         return null;
!       }
!     }
!   }
! 
!   public final Iterator valueIterator() {
!     if (STAGING) {
!       return map.values().iterator();
!     } else {
!       return new MapIterator(false);
!     }
!   }
!     
!   public final Iterator keyIterator() {
!     if (STAGING) {
!       return map.keySet().iterator();
!     } else {
!       return new MapIterator(true);
!     }
!   }
! 
!   private final int bucketIndex(Object key, int divisor) {
!     return (key.hashCode() & 0x7fffffff) % divisor;
!   }
!   
!   private static final class Bucket {
!     final Object key;
!     Object value;
!     Bucket next;
  
+     Bucket(Object k, Object v) {
+       key = k;
+       value = v;
+     }
+   }
  
+   private final class MapIterator implements Iterator {
+     private final boolean key;
+     private int bucketIndex = 0;
+     private Bucket next = null;
+     private Bucket last = null;
+     private int numVisited = 0;
+ 
+     MapIterator(boolean k) {
+       key = k;
+     }
      
+     public Object next() {
+       if (!hasNext()) {
+         throw new NoSuchElementException();
+       }
+         
+       while (next == null) {
+         next = buckets[bucketIndex++];
+       }
+       Bucket ans = next;
+       next = ans.next;
+       numVisited++;
+       return key ? ans.key : ans.value;
+     }
+ 
+     public boolean hasNext() {
+       return numVisited < numElems;
+     }
+ 
+     public void remove() {
+       if (last == null) {
+         throw new IllegalStateException();
+       }
+       VM_HashMap.this.remove(last.key);
+       last = null;
+     }
+   }
+ }

Update of /cvsroot/jikesrvm/rvm/src/vm/runtime
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv4366/src/vm/runtime

Modified Files:
	VM_DynamicLibrary.java 
Log Message:
real implementation of VM_HashMap.  Not very fancy, but seems to get the job done.

Index: VM_DynamicLibrary.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/runtime/VM_DynamicLibrary.java,v
retrieving revision 1.20
retrieving revision 1.21
diff -C2 -d -r1.20 -r1.21
*** VM_DynamicLibrary.java	22 May 2006 12:05:46 -0000	1.20
--- VM_DynamicLibrary.java	29 May 2006 02:29:22 -0000	1.21
***************
*** 133,137 ****
     */
    public static synchronized Address resolveSymbol(String symbol) {
!     for (Iterator i = dynamicLibraries.values().iterator(); i.hasNext();) {
        VM_DynamicLibrary lib = (VM_DynamicLibrary)i.next();
        Address symbolAddress = lib.getSymbol(symbol);
--- 133,137 ----
     */
    public static synchronized Address resolveSymbol(String symbol) {
!     for (Iterator i = dynamicLibraries.valueIterator(); i.hasNext();) {
        VM_DynamicLibrary lib = (VM_DynamicLibrary)i.next();
        Address symbolAddress = lib.getSymbol(symbol);

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/ipa/summaries
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv4348/src/vm/compilers/optimizing/optimizations/ipa/summaries

Modified Files:
	OPT_FieldDatabase.java 
Log Message:
real implementation of VM_HashMap.  Not very fancy, but seems to get the job done.

Index: OPT_FieldDatabase.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/ipa/summaries/OPT_FieldDatabase.java,v
retrieving revision 1.12
retrieving revision 1.13
diff -C2 -d -r1.12 -r1.13
*** OPT_FieldDatabase.java	22 May 2006 12:05:46 -0000	1.12
--- OPT_FieldDatabase.java	29 May 2006 02:29:17 -0000	1.13
***************
*** 57,61 ****
        
        if (cachedAllAnalyzed) return true;
!       for (java.util.Iterator i = summaries.values().iterator(); i.hasNext(); ) {
          FieldWriterInfo info = (FieldWriterInfo)i.next();
          if (!info.isAnalyzed()) return false;
--- 57,61 ----
        
        if (cachedAllAnalyzed) return true;
!       for (java.util.Iterator i = summaries.valueIterator(); i.hasNext(); ) {
          FieldWriterInfo info = (FieldWriterInfo)i.next();
          if (!info.isAnalyzed()) return false;
***************
*** 70,74 ****
        if (cachedConcreteType != null) return cachedConcreteType;
        VM_TypeReference result = null;
!       for (java.util.Iterator i = summaries.values().iterator(); i.hasNext(); ) {
          FieldWriterInfo info = (FieldWriterInfo)i.next();
          if (!info.isAnalyzed()) return null;
--- 70,74 ----
        if (cachedConcreteType != null) return cachedConcreteType;
        VM_TypeReference result = null;
!       for (java.util.Iterator i = summaries.valueIterator(); i.hasNext(); ) {
          FieldWriterInfo info = (FieldWriterInfo)i.next();
          if (!info.isAnalyzed()) return null;

Update of /cvsroot/jikesrvm/rvm/src/vm/adaptive/controller
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv4326/src/vm/adaptive/controller

Modified Files:
	VM_ControllerMemory.java 
Log Message:
real implementation of VM_HashMap.  Not very fancy, but seems to get the job done.

Index: VM_ControllerMemory.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/adaptive/controller/VM_ControllerMemory.java,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** VM_ControllerMemory.java	22 May 2006 12:05:45 -0000	1.16
--- VM_ControllerMemory.java	29 May 2006 02:29:13 -0000	1.17
***************
*** 334,338 ****
  
      // traverse table and give a summary of all actions that have occurred
!     for (Iterator it = table.keySet().iterator(); it.hasNext();) {
        VM_Method meth = (VM_Method) it.next();
        LinkedList planList = (LinkedList) table.get(meth);
--- 334,338 ----
  
      // traverse table and give a summary of all actions that have occurred
!     for (Iterator it = table.keyIterator(); it.hasNext();) {
        VM_Method meth = (VM_Method) it.next();
        LinkedList planList = (LinkedList) table.get(meth);

Update of /cvsroot/jikesrvm/rvm/bin
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv4306/bin

Modified Files:
	jconfigure 
Log Message:
real implementation of VM_HashMap.  Not very fancy, but seems to get the job done.

Index: jconfigure
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/bin/jconfigure,v
retrieving revision 1.499
retrieving revision 1.500
diff -C2 -d -r1.499 -r1.500
*** jconfigure	22 May 2006 19:56:37 -0000	1.499
--- jconfigure	29 May 2006 02:29:08 -0000	1.500
***************
*** 3787,3790 ****
--- 3787,3792 ----
  	[Lcom/ibm/JikesRVM/VM_DynamicLibrary;
  
+ 	[Lcom/ibm/JikesRVM/util/VM_HashMap\$Bucket;
+ 
  	[Lcom/ibm/JikesRVM/classloader/VM_InterfaceMethodSignature; # For fast interface method invoker
  
***************
*** 3792,3795 ****
--- 3794,3798 ----
  	EOF
      if (( RVM_WITH_OPT_COMPILER )); then
+ 
  	cat <<- EOF
  		[[C

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/codePlacement
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv1529/global/ssa/codePlacement

Modified Files:
	OPT_GlobalCSE.java OPT_LICM.java 
Log Message:
Improve javadoc

Index: OPT_LICM.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/codePlacement/OPT_LICM.java,v
retrieving revision 1.38
retrieving revision 1.39
diff -C2 -d -r1.38 -r1.39
*** OPT_LICM.java	22 Apr 2006 18:44:29 -0000	1.38
--- OPT_LICM.java	25 May 2006 11:12:28 -0000	1.39
***************
*** 6,10 ****
  import com.ibm.JikesRVM.*;
  
! import  java.util.*;
  import  com.ibm.JikesRVM.opt.ir.*;
  
--- 6,12 ----
  import com.ibm.JikesRVM.*;
  
! import  java.util.Enumeration;
! import  java.util.HashSet;
! import  java.util.Iterator;
  import  com.ibm.JikesRVM.opt.ir.*;
  
***************
*** 16,19 ****
--- 18,25 ----
   */
  class OPT_LICM extends OPT_CompilerPhase implements OPT_Operators {
+   /** Generate debug output? */
+   private static boolean DEBUG = false;
+   /** Generate verbose debug output? */
+   private static boolean verbose = false;
  
    /**
***************
*** 95,102 ****
     * @param reason
     */
!   static void BARF(String reason) {
!     throw  new OPT_OptimizingCompilerException(reason);
    }
!   
    //------------------------- Implementation -------------------------
    
--- 101,108 ----
     * @param reason
     */
!   private static void BARF(String reason) {
!     throw new OPT_OptimizingCompilerException(reason);
    }
! 
    //------------------------- Implementation -------------------------
    
***************
*** 262,266 ****
      return false;
    }
! 
    /**
     * Schedule this instruction as early as possible
--- 268,272 ----
      return false;
    }
! 
    /**
     * Schedule this instruction as early as possible
***************
*** 376,381 ****
    }
  
- 
- 
    /**
     * return `a's successor on the path from `a' to `b' in the dominator
--- 382,385 ----
***************
*** 439,443 ****
    }
  
-   
    /**
     * Schedule me as early as possible,
--- 443,446 ----
***************
*** 550,555 ****
      return  lateBlock;
    }
!   
! 
    /**
     * Return the instruction that defines the operand.
--- 553,557 ----
      return  lateBlock;
    }
! 
    /**
     * Return the instruction that defines the operand.
***************
*** 605,609 ****
      return  null;
    }
!   
    /**
     * Visit the blocks between the late and the early position along
--- 607,611 ----
      return  null;
    }
! 
    /**
     * Visit the blocks between the late and the early position along
***************
*** 709,713 ****
      cand.insertAfter(inst);
    }
!   
    //------------------------------------------------------------
    // some helper methods
--- 711,715 ----
      cand.insertAfter(inst);
    }
! 
    //------------------------------------------------------------
    // some helper methods
***************
*** 797,801 ****
      state[inst.scratch] = s;
    }
! 
    //------------------------------------------------------------
    // initialization
--- 799,803 ----
      state[inst.scratch] = s;
    }
! 
    //------------------------------------------------------------
    // initialization
***************
*** 883,887 ****
    private OPT_IR ir;
    //  private OPT_FI_EscapeSummary escapeSummary; - unused
!   private static java.util.HashSet moved = new java.util.HashSet();
    
    private boolean simplify(OPT_Instruction inst, OPT_BasicBlock block)
--- 885,889 ----
    private OPT_IR ir;
    //  private OPT_FI_EscapeSummary escapeSummary; - unused
!   private final HashSet moved = new HashSet();
    
    private boolean simplify(OPT_Instruction inst, OPT_BasicBlock block)
***************
*** 1134,1139 ****
      while (e.hasMoreElements()) e.next().clearLandingPad();
    }
-   
-   private static boolean DEBUG = false;
-   static boolean verbose = false;
  }
--- 1136,1138 ----

Index: OPT_GlobalCSE.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/codePlacement/OPT_GlobalCSE.java,v
retrieving revision 1.28
retrieving revision 1.29
diff -C2 -d -r1.28 -r1.29
*** OPT_GlobalCSE.java	24 May 2006 12:10:24 -0000	1.28
--- OPT_GlobalCSE.java	25 May 2006 11:12:28 -0000	1.29
***************
*** 21,24 ****
--- 21,26 ----
    /** Cache of IR being processed by this phase */
    private OPT_IR ir;
+   /** Cache of the value numbers from the IR  */
+   private OPT_GlobalValueNumberState valueNumbers;
    /**
     * Cache of dominator tree that should be computed prior to this
***************
*** 27,36 ****
    private OPT_DominatorTree dominator;
    /**
     */
    private final HashMap avail;
-   /**
-    */
-   private OPT_GlobalValueNumberState valueNumbers;
- 
  
    /**
--- 29,42 ----
    private OPT_DominatorTree dominator;
    /**
+    * Available expressions. From Muchnick, "an expression
+    * <em>exp</em>is said to be </em>available</em> at the entry to a
+    * basic block if along every control-flow path from the entry block
+    * to this block there is an evaluation of exp that is not
+    * subsequently killed by having one or more of its operands
+    * assigned a new value." Our available expressions are a mapping
+    * from a value number to the first instruction to define it as we
+    * traverse the dominator tree.
     */
    private final HashMap avail;
  
    /**
***************
*** 56,72 ****
    }
    
! 
    public void perform (OPT_IR ir) {
!     if (ir.hasReachableExceptionHandlers() || OPT_GCP.tooBig(ir)) return;
!     verbose = OPT_LICM.verbose;
      this.ir = ir;
      dominator = ir.HIRInfo.dominatorTree;
      (new OPT_GlobalValueNumber()).perform(ir);
      valueNumbers = ir.HIRInfo.valueNumbers;
      if (verbose) VM.sysWrite ("in GCSE for "+ir.method+"\n");
      OPT_DefUse.computeDU(ir);
      OPT_Simple.copyPropagation(ir);
      OPT_DefUse.computeDU(ir);
!     GlobalCSE(ir.firstBasicBlockInCodeOrder());
      if (VM.VerifyAssertions) {
        VM._assert(avail.size() == 0, avail.toString());
--- 62,91 ----
    }
    
!   /**
!    * Perform the GlobalCSE compiler phase
!    */
    public void perform (OPT_IR ir) {
!     // conditions to leave early
!     if (ir.hasReachableExceptionHandlers() || OPT_GCP.tooBig(ir))
!       return;
!     // cache useful values
!     verbose = ir.options.VERBOSE_GCP;
      this.ir = ir;
      dominator = ir.HIRInfo.dominatorTree;
+ 
+     // perform GVN
      (new OPT_GlobalValueNumber()).perform(ir);
      valueNumbers = ir.HIRInfo.valueNumbers;
+ 
      if (verbose) VM.sysWrite ("in GCSE for "+ir.method+"\n");
+ 
+     // compute DU and perform copy propagation
      OPT_DefUse.computeDU(ir);
      OPT_Simple.copyPropagation(ir);
      OPT_DefUse.computeDU(ir);
! 
!     // perform GCSE starting at the entry block
!     globalCSE(ir.firstBasicBlockInCodeOrder());
! 
      if (VM.VerifyAssertions) {
        VM._assert(avail.size() == 0, avail.toString());
***************
*** 76,93 ****
    
    /**
!    * Do a global CSE for all instructions of block b using the given
!    * value numbers 
!    * @param b
     */
!   private void GlobalCSE (OPT_BasicBlock b) {
      OPT_Instruction next, inst;
!     //VM.sysWrite ("Entering Block "+b+"\n");
      inst = b.firstInstruction();
      while (!BBend.conforms(inst)) {
        next = inst.nextInstructionInCodeOrder();
        if (!shouldCSE(inst)) {
          inst = next;
          continue;
        }
        OPT_RegisterOperand result = getResult(inst);
        if (result == null) {
--- 95,118 ----
    
    /**
!    * Recursively descend over all blocks dominated by b. For each
!    * instruction in the block, if it defines a GVN then record it in
!    * the available expressions. If the GVN already exists in the
!    * available expressions then eliminate the instruction and change
!    * all uses of the result of the instruction to be uses of the first
!    * instruction to define the result of this expression.
!    * @param b the current block to process
     */
!   private void globalCSE (OPT_BasicBlock b) {
      OPT_Instruction next, inst;
!     // Iterate over instructions in b
      inst = b.firstInstruction();
      while (!BBend.conforms(inst)) {
        next = inst.nextInstructionInCodeOrder();
+       // check instruction is safe for GCSE, {@see shouldCSE}
        if (!shouldCSE(inst)) {
          inst = next;
          continue;
        }
+       // check the instruction defines a result
        OPT_RegisterOperand result = getResult(inst);
        if (result == null) {
***************
*** 95,98 ****
--- 120,127 ----
          continue;
        }
+       // get the value number for this result. The value number for
+       // the same sub-expression is shared by all results showing they
+       // can be eliminated. If the value number is UNKNOWN the result
+       // is negative.
        int vn = valueNumbers.getValueNumber(result);
        if (vn < 0) {
***************
*** 100,109 ****
          continue;
        }
        Integer Vn = new Integer(vn);
        OPT_Instruction former = (OPT_Instruction)avail.get(Vn);
!       if (former != null) {
!         // instead of trying to repair Heap SSA, we rebuild it after CSE 
          
!         // relink scalar dependencies
          OPT_RegisterOperand formerDef = getResult(former);
          OPT_Register reg = result.register;
--- 129,148 ----
          continue;
        }
+       // was this the first definition of the value number?
        Integer Vn = new Integer(vn);
        OPT_Instruction former = (OPT_Instruction)avail.get(Vn);
!       if (former == null) {
!         // first occurance of value number, record it in the available
!         // expressions
!         avail.put(Vn, inst);
!       } else {
!         // this value number has been seen before so we can use the
!         // earlier version
!         // NB instead of trying to repair Heap SSA, we rebuild it
!         // after CSE
          
!         // relink scalar dependencies - make all uses of the current
!         // instructions result use the first definition of the result
!         // by the earlier expression
          OPT_RegisterOperand formerDef = getResult(former);
          OPT_Register reg = result.register;
***************
*** 118,136 ****
                        inst + "\n");
          }
          inst.remove();
        } 
-       else {
-         //if (verbose) VM.sysWrite ("adding ("+b+") ["+vn+"]"+inst+"\n");
-         avail.put(Vn, inst);
-       }
        inst = next;
!     }
      Enumeration e = dominator.getChildren(b);
      while (e.hasMoreElements()) {
        OPT_DominatorTreeNode n = (OPT_DominatorTreeNode)e.nextElement();
        OPT_BasicBlock bl = n.getBlock();
        if (ir.options.FREQ_FOCUS_EFFORT && bl.getInfrequent()) continue;
!       GlobalCSE(bl);
      }
      inst = b.firstInstruction();
      while (!BBend.conforms(inst)) {
--- 157,176 ----
                        inst + "\n");
          }
+         // remove the redundant instruction
          inst.remove();
        } 
        inst = next;
!     } // end of instruction iteration
!     // Recurse over all blocks that this block dominates
      Enumeration e = dominator.getChildren(b);
      while (e.hasMoreElements()) {
        OPT_DominatorTreeNode n = (OPT_DominatorTreeNode)e.nextElement();
        OPT_BasicBlock bl = n.getBlock();
+       // don't process infrequently executed basic blocks
        if (ir.options.FREQ_FOCUS_EFFORT && bl.getInfrequent()) continue;
!       globalCSE(bl);
      }
+     // Iterate over instructions in this basic block removing
+     // available expressions that had been created for this block
      inst = b.firstInstruction();
      while (!BBend.conforms(inst)) {
***************
*** 154,162 ****
        if (former == inst) {
          avail.remove(Vn);
-         //if (verbose) VM.sysWrite ("removing ("+b+"): "+inst+"\n");
        }
        inst = next;
      }
-     //VM.sysWrite ("Leaving Block "+b+"\n");
    }
    
--- 194,200 ----
***************
*** 180,184 ****
    private boolean shouldCSE (OPT_Instruction inst) {
      
!     if ((  inst.isAllocation())
          || inst.isDynamicLinkingPoint()
          || inst.isImplicitLoad()
--- 218,222 ----
    private boolean shouldCSE (OPT_Instruction inst) {
      
!     if ((inst.isAllocation())
          || inst.isDynamicLinkingPoint()
          || inst.isImplicitLoad()
***************
*** 190,197 ****
      case INT_MOVE_opcode:
      case LONG_MOVE_opcode:
-       //  OPT_Operand ival = Move.getVal(inst);
-       //if (ival instanceof OPT_ConstantOperand)
-       //        return  false;
-       // fall through
      case GET_CLASS_OBJECT_opcode:
      case CHECKCAST_opcode:
--- 228,231 ----

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv1189/global/ssa/gvn

Modified Files:
	OPT_ValueNumberPair.java 
Log Message:
Modified setsDiffer to use Arrays

Index: OPT_ValueNumberPair.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/OPT_ValueNumberPair.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** OPT_ValueNumberPair.java	24 May 2006 12:09:21 -0000	1.7
--- OPT_ValueNumberPair.java	25 May 2006 11:11:58 -0000	1.8
***************
*** 10,14 ****
   * @author Stephen Fink
   */
! class OPT_ValueNumberPair {
    /** the value number of an array pointer */
    final int v1;
--- 10,14 ----
   * @author Stephen Fink
   */
! class OPT_ValueNumberPair implements Comparable {
    /** the value number of an array pointer */
    final int v1;
***************
*** 44,54 ****
  
    // total order over OPT_ValueNumberPairs
!   public boolean greaterThan(OPT_ValueNumberPair p) {
      if (v1 > p.v1)
!       return  true;
!     if (v1 < p.v1)
!       return  false;
      // v1 == p.v1
!     return  (v2 > p.v2);
    }
  }
--- 44,61 ----
  
    // total order over OPT_ValueNumberPairs
!   public int compareTo(Object o) {
!     OPT_ValueNumberPair p = (OPT_ValueNumberPair)o;
      if (v1 > p.v1)
!       return  1;
!     else if (v1 < p.v1)
!       return  -1;
      // v1 == p.v1
!     else if(v2 > p.v2)
!       return 1;
!     else if(v2 < p.v2)
!       return -1;
!     // v2 == p.v2
!     else
!       return 0;
    }
  }

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/loadElimination
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv1189/global/ssa/loadElimination

Modified Files:
	OPT_IndexPropagation.java 
Log Message:
Modified setsDiffer to use Arrays

Index: OPT_IndexPropagation.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/loadElimination/OPT_IndexPropagation.java,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -d -r1.15 -r1.16
*** OPT_IndexPropagation.java	24 May 2006 12:12:23 -0000	1.15
--- OPT_IndexPropagation.java	25 May 2006 11:11:58 -0000	1.16
***************
*** 266,270 ****
       */
      public static boolean setsDiffer(int[] set1, int[] set2) {
!       return !Arrays.equals(set1, set2);
      }
    }
--- 266,277 ----
       */
      public static boolean setsDiffer(int[] set1, int[] set2) {
!       if ((set1 != null) && (set2 != null)) {
!         Arrays.sort(set1);      
!         Arrays.sort(set2);
!         return !Arrays.equals(set1, set2);
!       }
!       else {
!         return set1 == set2;
!       }
      }
    }
***************
*** 476,480 ****
      public static boolean setsDiffer(OPT_ValueNumberPair[] set1, 
                                        OPT_ValueNumberPair[] set2) {
!       return !Arrays.equals(set1, set2);
      }
    }
--- 483,494 ----
      public static boolean setsDiffer(OPT_ValueNumberPair[] set1, 
                                        OPT_ValueNumberPair[] set2) {
!       if ((set1 != null) && (set2 != null)) {
!         Arrays.sort(set1);      
!         Arrays.sort(set2);
!         return !Arrays.equals(set1, set2);
!       }
!       else {
!         return set1 == set2;
!       }
      }
    }

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv12879

Removed Files:
	OPT_ValueNumberPairSetCell.java OPT_ValueNumberSetCell.java 
Log Message:
Remove unused classes

--- OPT_ValueNumberPairSetCell.java DELETED ---

--- OPT_ValueNumberSetCell.java DELETED ---

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/liveness
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv32181

Modified Files:
	OPT_LiveSet.java 
Log Message:
alter remove to make it package protected

Index: OPT_LiveSet.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/liveness/OPT_LiveSet.java,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -d -r1.8 -r1.9
*** OPT_LiveSet.java	12 May 2005 15:56:15 -0000	1.8
--- OPT_LiveSet.java	24 May 2006 12:14:23 -0000	1.9
***************
*** 274,278 ****
     * @param item the registerOperand holding the register of interest
     */
!   public void remove(OPT_RegisterOperand item) {
      if (debug) {
        System.out.println("\tOPT_LiveSet.remove (item) called with reg "
--- 274,278 ----
     * @param item the registerOperand holding the register of interest
     */
!   void remove(OPT_RegisterOperand item) {
      if (debug) {
        System.out.println("\tOPT_LiveSet.remove (item) called with reg "

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/redundantBranchElimination
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv31790

Modified Files:
	OPT_RedundantBranchElimination.java 
Log Message:
Changes to RBE, use accessor method for value graph vertex key

Index: OPT_RedundantBranchElimination.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/redundantBranchElimination/OPT_RedundantBranchElimination.java,v
retrieving revision 1.12
retrieving revision 1.13
diff -C2 -d -r1.12 -r1.13
*** OPT_RedundantBranchElimination.java	11 Oct 2005 12:00:37 -0000	1.12
--- OPT_RedundantBranchElimination.java	24 May 2006 12:13:13 -0000	1.13
***************
*** 95,99 ****
          if (cc.size() > 1) {
            for (Iterator e = cc.iterator(); e.hasNext();) {
!             OPT_Instruction poss = (OPT_Instruction)((OPT_ValueGraphVertex)e.next()).name;
              if (poss != candTest) {
                OPT_BasicBlock notTaken = getNotTakenBlock(poss);
--- 95,99 ----
          if (cc.size() > 1) {
            for (Iterator e = cc.iterator(); e.hasNext();) {
!             OPT_Instruction poss = (OPT_Instruction)((OPT_ValueGraphVertex)e.next()).getName();
              if (poss != candTest) {
                OPT_BasicBlock notTaken = getNotTakenBlock(poss);

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/loadElimination
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv31421

Modified Files:
	OPT_IndexPropagation.java OPT_IndexPropagationSystem.java 
Log Message:
Changes to load elimination, make fields private and final where possible

Index: OPT_IndexPropagation.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/loadElimination/OPT_IndexPropagation.java,v
retrieving revision 1.14
retrieving revision 1.15
diff -C2 -d -r1.14 -r1.15
*** OPT_IndexPropagation.java	5 Dec 2003 23:48:28 -0000	1.14
--- OPT_IndexPropagation.java	24 May 2006 12:12:23 -0000	1.15
***************
*** 5,9 ****
  package com.ibm.JikesRVM.opt;
  
! import  java.util.*;
  import com.ibm.JikesRVM.opt.ir.*;
  
--- 5,9 ----
  package com.ibm.JikesRVM.opt;
  
! import  java.util.Arrays;
  import com.ibm.JikesRVM.opt.ir.*;
  
***************
*** 89,109 ****
       * a bound on the size of a lattice cell.
       */
!     final static int CAPACITY = 10; 
      /**
       * a set of value numbers comparising this lattice cell.
       */
!     int[] numbers = null;
      /**
       * The number of value numbers in this cell.
       */
!     int size = 0;
      /**
       * The heap variable this lattice cell tracks information for.
       */
!     OPT_HeapVariable key;
      /**
       * Does this lattice cell represent TOP?
       */
!     boolean TOP = true;
  
      /**
--- 89,109 ----
       * a bound on the size of a lattice cell.
       */
!     private final static int CAPACITY = 10; 
      /**
       * a set of value numbers comparising this lattice cell.
       */
!     private int[] numbers = null;
      /**
       * The number of value numbers in this cell.
       */
!     private int size = 0;
      /**
       * The heap variable this lattice cell tracks information for.
       */
!     private final OPT_HeapVariable key;
      /**
       * Does this lattice cell represent TOP?
       */
!     private boolean TOP = true;
  
      /**
***************
*** 116,119 ****
--- 116,126 ----
  
      /**
+      * Return the key
+      */
+     OPT_HeapVariable getKey() {
+       return key;
+     }
+ 
+     /**
       * Does this cell represent the TOP element in the dataflow lattice?
       * @return true or false.
***************
*** 259,305 ****
       */
      public static boolean setsDiffer(int[] set1, int[] set2) {
! 
!       if (set1 == null) {
!         return (set2 != null);
!       } else if (set2 == null) {
!         return true;
!       }
! 
!       if (set1.length != set2.length) return  true;
! 
!       sort(set1);
!       sort(set2);
! 
!       for (int i = 0; i < set1.length; i++) {
!         if (set1[i] != set2[i])
!           return  true;
!       }
!       return  false;
!     }
! 
!     /** 
!      * Sort an array of value numbers with bubble sort. 
!      * Note that these sets
!      * will be small  (< CAPACITY), so bubble sort
!      * should be ok.
!      * @param set the set to sort
!      */
!     public static void sort(int[] set) {
! 
!       if (set == null) return;
! 
!       for (int i = set.length - 1; i >= 0; i--) {
!         for (int j = 0; j < i; j++) {
!           if (set[j] > set[j + 1]) {
!             int temp = set[j + 1];
!             set[j + 1] = set[j];
!             set[j] = temp;
!           }
!         }
!       }
      }
    }
  
- 
    /**
     * An ArrayCell is a lattice cell for the index propagation 
--- 266,273 ----
       */
      public static boolean setsDiffer(int[] set1, int[] set2) {
!       return !Arrays.equals(set1, set2);
      }
    }
  
    /**
     * An ArrayCell is a lattice cell for the index propagation 
***************
*** 323,343 ****
       * a bound on the size of a lattice cell.
       */
!     final static int CAPACITY = 10;      
      /**
       * a set of value number pairs comparising this lattice cell.
       */
!     OPT_ValueNumberPair[] numbers = null;
      /**
       * The number of value number pairs in this cell.
       */
!     int size = 0;
      /**
       * The heap variable this lattice cell tracks information for.
       */
!     OPT_HeapVariable key;
      /**
       * Does this lattice cell represent TOP?
       */
!     boolean TOP = true;
  
      /**
--- 291,311 ----
       * a bound on the size of a lattice cell.
       */
!     private final static int CAPACITY = 10;      
      /**
       * a set of value number pairs comparising this lattice cell.
       */
!     private OPT_ValueNumberPair[] numbers = null;
      /**
       * The number of value number pairs in this cell.
       */
!     private int size = 0;
      /**
       * The heap variable this lattice cell tracks information for.
       */
!     private final OPT_HeapVariable key;
      /**
       * Does this lattice cell represent TOP?
       */
!     private boolean TOP = true;
  
      /**
***************
*** 350,353 ****
--- 318,328 ----
  
      /**
+      * Return the key
+      */
+     OPT_HeapVariable getKey() {
+       return key;
+     }
+ 
+     /**
       * Does this cell represent the TOP element in the dataflow lattice?
       * @return true or false.
***************
*** 501,542 ****
      public static boolean setsDiffer(OPT_ValueNumberPair[] set1, 
                                        OPT_ValueNumberPair[] set2) {
!       if (set1 == null) {
!         return (set2 != null);
!       } else if (set2 == null) {
!         return true;
!       }
! 
!       if (set1.length != set2.length) return  true;
! 
!       sort(set1);
!       sort(set2);
! 
!       for (int i = 0; i < set1.length; i++) {
!         if (!set1[i].equals(set2[i]))
!           return  true;
!       }
!       return  false;
!     }
! 
!     /**
!      * Sort an array of value number pairs with bubble sort. 
!      * Note that these sets
!      * will be small  (< CAPACITY), so bubble sort
!      * should be ok.
!      * @param set the set to sort
!      */
!     public static void sort(OPT_ValueNumberPair[] set) {
! 
!       if (set == null) return;
! 
!       for (int i = set.length - 1; i >= 0; i--) {
!         for (int j = 0; j < i; j++) {
!           if (set[j].greaterThan(set[j + 1])) {
!             OPT_ValueNumberPair temp = set[j + 1];
!             set[j + 1] = set[j];
!             set[j] = temp;
!           }
!         }
!       }
      }
    }
--- 476,480 ----
      public static boolean setsDiffer(OPT_ValueNumberPair[] set1, 
                                        OPT_ValueNumberPair[] set2) {
!       return !Arrays.equals(set1, set2);
      }
    }

Index: OPT_IndexPropagationSystem.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/loadElimination/OPT_IndexPropagationSystem.java,v
retrieving revision 1.11
retrieving revision 1.12
diff -C2 -d -r1.11 -r1.12
*** OPT_IndexPropagationSystem.java	19 Dec 2004 01:06:15 -0000	1.11
--- OPT_IndexPropagationSystem.java	24 May 2006 12:12:23 -0000	1.12
***************
*** 20,50 ****
  implements OPT_Operators {
  
-   /** 
-    * Set up the system of dataflow equations.
-    * @param _ir the IR
-    */
-   public OPT_IndexPropagationSystem(OPT_IR _ir) {
-     ir = _ir;
-     ssa = ir.HIRInfo.SSADictionary;
-     valueNumbers = ir.HIRInfo.valueNumbers;
-     setupEquations();
-   }
- 
    /**
     * The governing IR.
     */
!   OPT_IR ir;
    /**
     * Heap Array SSA lookaside information for the IR.
     */
!   OPT_SSADictionary ssa;
    /**
     * Results of global value numbering
     */
!   OPT_GlobalValueNumberState valueNumbers;
    /**
     * object representing the MEET operator
     */
!   MeetOperator MEET = new MeetOperator();
  
    /**
--- 20,50 ----
  implements OPT_Operators {
  
    /**
     * The governing IR.
     */
!   private final OPT_IR ir;
    /**
     * Heap Array SSA lookaside information for the IR.
     */
!   private final OPT_SSADictionary ssa;
    /**
     * Results of global value numbering
     */
!   private final OPT_GlobalValueNumberState valueNumbers;
    /**
     * object representing the MEET operator
     */
!   private final static MeetOperator MEET = new MeetOperator();
! 
!   /** 
!    * Set up the system of dataflow equations.
!    * @param _ir the IR
!    */
!   public OPT_IndexPropagationSystem(OPT_IR _ir) {
!     ir = _ir;
!     ssa = ir.HIRInfo.SSADictionary;
!     valueNumbers = ir.HIRInfo.valueNumbers;
!     setupEquations();
!   }
  
    /**
***************
*** 77,81 ****
        if (c instanceof ObjectCell) {
          ObjectCell c1 = (ObjectCell)c;
!         OPT_HeapVariable key = c1.key;
          if (key.isExposedOnEntry()) {
            c1.setBOTTOM();
--- 77,81 ----
        if (c instanceof ObjectCell) {
          ObjectCell c1 = (ObjectCell)c;
!         OPT_HeapVariable key = c1.getKey();
          if (key.isExposedOnEntry()) {
            c1.setBOTTOM();
***************
*** 84,88 ****
        else {
          ArrayCell c1 = (ArrayCell)c;
!         OPT_HeapVariable key = c1.key;
          if (key.isExposedOnEntry()) {
            c1.setBOTTOM();
--- 84,88 ----
        else {
          ArrayCell c1 = (ArrayCell)c;
!         OPT_HeapVariable key = c1.getKey();
          if (key.isExposedOnEntry()) {
            c1.setBOTTOM();
***************
*** 455,459 ****
     * Represents a MEET function (intersection) over Cells.
     */
!   class MeetOperator extends OPT_DF_Operator {
  
      /**
--- 455,459 ----
     * Represents a MEET function (intersection) over Cells.
     */
!   static class MeetOperator extends OPT_DF_Operator {
  
      /**
***************
*** 633,637 ****
       * The value number used in the dataflow equation.
       */
!     int valueNumber;
  
      /**
--- 633,637 ----
       * The value number used in the dataflow equation.
       */
!     private final int valueNumber;
  
      /**
***************
*** 696,704 ****
     * available, and doesn't kill any available indices
     */
!   class UpdateUseObjectOperator extends OPT_DF_Operator {
      /**
       * The value number used in the dataflow equation.
       */
!     int valueNumber;
  
      /**
--- 696,704 ----
     * available, and doesn't kill any available indices
     */
!   static class UpdateUseObjectOperator extends OPT_DF_Operator {
      /**
       * The value number used in the dataflow equation.
       */
!     private final int valueNumber;
  
      /**
***************
*** 763,767 ****
       * The value number pair used in the dataflow equation.
       */
!     OPT_ValueNumberPair v = new OPT_ValueNumberPair();
  
      /**
--- 763,767 ----
       * The value number pair used in the dataflow equation.
       */
!     private final OPT_ValueNumberPair v;
  
      /**
***************
*** 777,782 ****
       */
      UpdateDefArrayOperator(int v1, int v2) {
!       v.v1 = v1;
!       v.v2 = v2;
      }
  
--- 777,781 ----
       */
      UpdateDefArrayOperator(int v1, int v2) {
!       v = new OPT_ValueNumberPair(v1, v2);
      }
  
***************
*** 831,839 ****
     * available, and doesn't kill any available indices
     */
!   class UpdateUseArrayOperator extends OPT_DF_Operator {
      /**
       * The value number pair used in the dataflow equation.
       */
!     OPT_ValueNumberPair v = new OPT_ValueNumberPair();
  
      /**
--- 830,838 ----
     * available, and doesn't kill any available indices
     */
!   static class UpdateUseArrayOperator extends OPT_DF_Operator {
      /**
       * The value number pair used in the dataflow equation.
       */
!     private final OPT_ValueNumberPair v;
  
      /**
***************
*** 848,853 ****
       */
      UpdateUseArrayOperator(int v1, int v2) {
!       v.v1 = v1;
!       v.v2 = v2;
      }
  
--- 847,851 ----
       */
      UpdateUseArrayOperator(int v1, int v2) {
!       v = new OPT_ValueNumberPair(v1, v2);
      }

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/expressionFolding
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv31036

Modified Files:
	OPT_ExpressionFolding.java 
Log Message:
Changes to expression folding, make fields private where possible

Index: OPT_ExpressionFolding.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/expressionFolding/OPT_ExpressionFolding.java,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** OPT_ExpressionFolding.java	22 Apr 2006 18:44:32 -0000	1.16
--- OPT_ExpressionFolding.java	24 May 2006 12:11:19 -0000	1.17
***************
*** 19,25 ****
   */
  class OPT_ExpressionFolding implements OPT_Operators {
!   static final boolean DEBUG = false;
  
!   static final boolean RESTRICT_TO_DEAD_EXPRESSIONS = true;
  
    /** 
--- 19,26 ----
   */
  class OPT_ExpressionFolding implements OPT_Operators {
!   /** Generate verbose debug output? */
!   private static final boolean DEBUG = false;
  
!   private static final boolean RESTRICT_TO_DEAD_EXPRESSIONS = true;
  
    /**

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/codePlacement
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv30689

Modified Files:
	OPT_GlobalCSE.java 
Log Message:
Changes to GlobalCSE, make fields private and final where possible

Index: OPT_GlobalCSE.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/codePlacement/OPT_GlobalCSE.java,v
retrieving revision 1.27
retrieving revision 1.28
diff -C2 -d -r1.27 -r1.28
*** OPT_GlobalCSE.java	16 Aug 2005 02:38:42 -0000	1.27
--- OPT_GlobalCSE.java	24 May 2006 12:10:24 -0000	1.28
***************
*** 5,10 ****
  package com.ibm.JikesRVM.opt;
  import com.ibm.JikesRVM.*;
! 
! import  java.util.*;
  import  com.ibm.JikesRVM.opt.ir.*;
  
--- 5,10 ----
  package com.ibm.JikesRVM.opt;
  import com.ibm.JikesRVM.*;
! import  java.util.HashMap;
! import  java.util.Enumeration;
  import  com.ibm.JikesRVM.opt.ir.*;
  
***************
*** 15,21 ****
   * @modified Stephen Fink
   */
! class OPT_GlobalCSE extends OPT_CompilerPhase implements OPT_Operators {
  
!   public boolean verbose = false;
  
    /**
--- 15,43 ----
   * @modified Stephen Fink
   */
! final class OPT_GlobalCSE extends OPT_CompilerPhase implements OPT_Operators {
  
!   /** Output debug messages */
!   public boolean verbose = true;
!   /** Cache of IR being processed by this phase */
!   private OPT_IR ir;
!   /**
!    * Cache of dominator tree that should be computed prior to this
!    * phase
!    */
!   private OPT_DominatorTree dominator;
!   /**
!    */
!   private final HashMap avail;
!   /**
!    */
!   private OPT_GlobalValueNumberState valueNumbers;
! 
! 
!   /**
!    * Constructor
!    */
!   OPT_GlobalCSE() {
!     avail = new HashMap();
!   }
  
    /**
***************
*** 42,62 ****
      (new OPT_GlobalValueNumber()).perform(ir);
      valueNumbers = ir.HIRInfo.valueNumbers;
!     if (true || ir.IRStage == OPT_IR.LIR) {
!       if (verbose) VM.sysWrite ("in GCSE for "+ir.method+"\n");
!       OPT_DefUse.computeDU(ir);
!       OPT_Simple.copyPropagation(ir);
!       OPT_DefUse.computeDU(ir);
!       GlobalCSE(ir.firstBasicBlockInCodeOrder());
!       if (VM.VerifyAssertions) {
!         VM._assert(avail.size() == 0, avail.toString());
!       }
!       ir.actualSSAOptions.setScalarValid(false);
      }
    }
    
-   private OPT_IR ir;
-   private static java.util.HashMap avail = new java.util.HashMap();
-   private OPT_GlobalValueNumberState valueNumbers;
- 
    /**
     * Do a global CSE for all instructions of block b using the given
--- 64,78 ----
      (new OPT_GlobalValueNumber()).perform(ir);
      valueNumbers = ir.HIRInfo.valueNumbers;
!     if (verbose) VM.sysWrite ("in GCSE for "+ir.method+"\n");
!     OPT_DefUse.computeDU(ir);
!     OPT_Simple.copyPropagation(ir);
!     OPT_DefUse.computeDU(ir);
!     GlobalCSE(ir.firstBasicBlockInCodeOrder());
!     if (VM.VerifyAssertions) {
!       VM._assert(avail.size() == 0, avail.toString());
      }
+     ir.actualSSAOptions.setScalarValid(false);
    }
    
    /**
     * Do a global CSE for all instructions of block b using the given
***************
*** 149,153 ****
     * @param inst
     */
!   OPT_RegisterOperand getResult (OPT_Instruction inst) {
      if (ResultCarrier.conforms(inst))
        return  ResultCarrier.getResult(inst);
--- 165,169 ----
     * @param inst
     */
!   private OPT_RegisterOperand getResult (OPT_Instruction inst) {
      if (ResultCarrier.conforms(inst))
        return  ResultCarrier.getResult(inst);
***************
*** 162,166 ****
     * @param inst
     */
!   boolean shouldCSE (OPT_Instruction inst) {
      
      if ((  inst.isAllocation())
--- 178,182 ----
     * @param inst
     */
!   private boolean shouldCSE (OPT_Instruction inst) {
      
      if ((  inst.isAllocation())
***************
*** 291,295 ****
      return false;
    }
- 
-   private OPT_DominatorTree dominator;
  }
--- 307,309 ----

Update of /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/indexEquivalence
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv30248/indexEquivalence

Modified Files:
	OPT_UniformlyGeneratedGVN.java 
Log Message:
Changes to GVN, make fields private and final where possible

Index: OPT_UniformlyGeneratedGVN.java
===================================================================
RCS file: /cvsroot/jikesrvm/rvm/src/vm/compilers/optimizing/optimizations/global/ssa/gvn/indexEquivalence/OPT_UniformlyGeneratedGVN.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** OPT_UniformlyGeneratedGVN.java	15 Oct 2004 20:39:21 -0000	1.7
--- OPT_UniformlyGeneratedGVN.java	24 May 2006 12:09:21 -0000	1.8
***************
*** 36,40 ****
      OPT_GlobalValueNumberState gvn = null;
      gvn = new OPT_GlobalValueNumberState(ir);
-     gvn.globalValueNumber();
  
      // Merge classes related by a constant
--- 36,39 ----

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

Update of /cvsroot/jikesrvm/MMTk/ext/vm/JikesRVM/org/mmtk/vm
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/MMTk/ext/vm/JikesRVM/org/mmtk/vm

Modified Files:
	ObjectModel.java ReferenceGlue.java 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



Index: ReferenceGlue.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/ext/vm/JikesRVM/org/mmtk/vm/ReferenceGlue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** ReferenceGlue.java	24 Apr 2006 13:48:14 -0000	1.3
--- ReferenceGlue.java	24 May 2006 03:40:04 -0000	1.4
***************
*** 116,119 ****
--- 116,157 ----
      lock.release();
    }
+   
+   /**
+    * Scan through all references and forward. Only called when references
+    * are objects.
+    */
+   public void forward() {
+     
+     if (TRACE) {
+       VM.sysWrite("Starting ReferenceProcessor.traverse(");
+       VM.sysWrite(ReferenceProcessor.semanticStrings[semantics]);
+       VM.sysWriteln(")");
+     }
+     
+     Address reference = waitingListHead;
+     Address prevReference = Address.zero();
+     if (!waitingListHead.isZero()) {
+       waitingListHead = ReferenceProcessor.forwardReference(reference);
+       prevReference = reference;
+       reference = getNextReferenceAsAddress(reference);
+     }
+     while (!reference.isZero()) {
+       Address newReference = ReferenceProcessor.forwardReference(reference);
+       if (!prevReference.isZero()) {
+         setNextReferenceAsAddress(prevReference, newReference);
+       }
+       prevReference = reference;
+       reference = getNextReferenceAsAddress(reference);
+     }
+     if (!prevReference.isZero()) {
+       setNextReferenceAsAddress(prevReference, Address.zero());
+     }
+     
+     if (TRACE) {
+       VM.sysWrite("Ending ReferenceProcessor.traverse(");
+       VM.sysWrite(ReferenceProcessor.semanticStrings[semantics]);
+       VM.sysWriteln(")");
+     }
+   }
  
    /**
***************
*** 322,324 ****
--- 360,372 ----
      return -1;
    }
+   
+   /**
+    * Scan through all references and forward. Only called when references
+    * are objects.
+    */
+   public static void forwardReferences() {
+     softReferenceProcessor.forward();
+     weakReferenceProcessor.forward();
+     phantomReferenceProcessor.forward();
+   }
  }

Index: ObjectModel.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/ext/vm/JikesRVM/org/mmtk/vm/ObjectModel.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** ObjectModel.java	22 Sep 2005 00:55:52 -0000	1.3
--- ObjectModel.java	24 May 2006 03:40:04 -0000	1.4
***************
*** 9,12 ****
--- 9,13 ----
  import org.mmtk.utility.scan.MMType;
  import org.mmtk.utility.Constants;
+ import org.mmtk.utility.alloc.Allocator;
  
  import com.ibm.JikesRVM.VM;
***************
*** 100,114 ****
    }
  
!   /*
!   public static Object addressAsObject(ObjectReference object)
      throws InlinePragma {
!     return ObjectReference.toObject(object);
    }
  
!   public static Address objectAsRef(Object object) throws InlinePragma {
!     return ObjectReference.fromObject(object);
    }
!   */
! 
    /**
     * Return the size required to copy an object
--- 101,167 ----
    }
  
!   /**
!    * Copy an object to be pointer to by the to address. This is required 
!    * for delayed-copy collectors such as compacting collectors. During the 
!    * collection, MMTk reserves a region in the heap for an object as per
!    * requirements found from ObjectModel and then asks ObjectModel to 
!    * determine what the object's reference will be post-copy.
!    * 
!    * @param from the address of the object to be copied
!    * @param to The target location.
!    * @param region The start (or an address less than) the region that was reserved for this object.
!    * @return Address The address past the end of the copied object
!    */
!   public static Address copyTo(ObjectReference from, ObjectReference to, Address region)
      throws InlinePragma {
!     Object[] tib = VM_ObjectModel.getTIB(from);
!     VM_Type type = VM_Magic.objectAsType(tib[TIB_TYPE_INDEX]);
!     int bytes;
!     
!     boolean copy = (from != to);
!     
!     if (copy) {
!       if (type.isClassType()) {
!         VM_Class classType = type.asClass();
!         bytes = VM_ObjectModel.bytesRequiredWhenCopied(from, classType);
!         VM_ObjectModel.moveObject(from, to, bytes, false, classType);
!       } else {
!       VM_Array arrayType = type.asArray();
!         int elements = VM_Magic.getArrayLength(from);
!         bytes = VM_ObjectModel.bytesRequiredWhenCopied(from, arrayType, elements);
!         VM_ObjectModel.moveObject(from, to, bytes, false, arrayType);
!       }
!     } else {
!       bytes = getCurrentSize(to);
!     }
!     
!     Address start = VM_ObjectModel.objectStartRef(to);
!     Allocator.fillAlignmentGap(region, start);
!     
!     return start.add(bytes);
    }
  
!   /**
!    * Return the reference that an object will be refered to after it is copied
!    * to the specified region. Used in delayed-copy collectors such as compacting
!    * collectors.
!    *
!    * @param from The object to be copied.
!    * @param to The region to be copied to.
!    * @return The resulting reference.
!    */
!   public static ObjectReference getReferenceWhenCopiedTo(ObjectReference from, Address to) {
!     return ObjectReference.fromObject(VM_ObjectModel.getReferenceWhenCopiedTo(from, to));
    }
!   
!   /**
!    * Gets a pointer to the address just past the end of the object.
!    * 
!    * @param object The objecty.
!    */
!   public static Address getObjectEndAddress(ObjectReference object) {
!     return VM_ObjectModel.getObjectEndAddress(object);
!   }
!   
    /**
     * Return the size required to copy an object
***************
*** 120,124 ****
      return VM_ObjectModel.bytesRequiredWhenCopied(object);
    }
!     
    /**
     * Return the size used by an object
--- 173,209 ----
      return VM_ObjectModel.bytesRequiredWhenCopied(object);
    }
!   
!   /**
!    * Return the alignment requirement for a copy of this object
!    *
!    * @param object The object whose size is to be queried
!    * @return The alignment required for a copy of <code>obj</code>
!    */
!   public static int getAlignWhenCopied(ObjectReference object) {
!     Object[] tib = VM_ObjectModel.getTIB(object);
!     VM_Type type = VM_Magic.objectAsType(tib[TIB_TYPE_INDEX]);
!     if (type.isArrayType()) {
!       return VM_ObjectModel.getAlignment(type.asArray(), object);
!     } else {
!       return VM_ObjectModel.getAlignment(type.asClass(), object);
!     }
!   }
!   
!   /**
!    * Return the alignment offset requirements for a copy of this object
!    *
!    * @param object The object whose size is to be queried
!    * @return The alignment offset required for a copy of <code>obj</code>
!    */
!   public static int getAlignOffsetWhenCopied(ObjectReference object) {
!     Object[] tib = VM_ObjectModel.getTIB(object);
!     VM_Type type = VM_Magic.objectAsType(tib[TIB_TYPE_INDEX]);
!     if (type.isArrayType()) {
!       return VM_ObjectModel.getOffsetForAlignment(type.asArray(), object);
!     } else {
!       return VM_ObjectModel.getOffsetForAlignment(type.asClass(), object);
!     }
!   }
!   
    /**
     * Return the size used by an object
***************
*** 315,316 ****
--- 400,402 ----
    }
  }
+

Update of /cvsroot/jikesrvm/MMTk/src/org/mmtk/policy
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/MMTk/src/org/mmtk/policy

Added Files:
	MarkCompactLocal.java MarkCompactSpace.java 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



--- NEW FILE: MarkCompactLocal.java ---
/*
 * (C) Copyright Department of Computer Science,
 * Australian National University. 2004
 */
package org.mmtk.policy;

import org.mmtk.plan.markcompact.MC;
import org.mmtk.utility.Conversions;
import org.mmtk.utility.Log;
import org.mmtk.utility.Memory;
import org.mmtk.utility.alloc.Allocator;
import org.mmtk.utility.alloc.BumpPointer;
import org.mmtk.utility.statistics.Stats;
import org.mmtk.vm.ActivePlan;
import org.mmtk.vm.Assert;
import org.mmtk.vm.ObjectModel;

import org.vmmagic.pragma.*;
import org.vmmagic.unboxed.Address;
import org.vmmagic.unboxed.Extent;
import org.vmmagic.unboxed.ObjectReference;
import org.vmmagic.unboxed.Word;

/**
 * This class implements unsynchronized (local) elements of a
 * sliding mark-compact collector. Allocation is via the bump pointer 
 * (@see BumpPointer). 
 *
 * @see BumpPointer
 * @see MarkCompactSpace 
 *
 * @author Daniel Frampton
 * @version $Revision: 1.1 $
 * @date $Date: 2006/05/24 03:40:04 $
 */
public final class MarkCompactLocal extends BumpPointer implements Uninterruptible {
  public final static String Id = "$Id: MarkCompactLocal.java,v 1.1 2006/05/24 03:40:04 dframpton-oss Exp $"; 

  /**
   * Constructor
   *
   * @param space The space to bump point into.
   */
  public MarkCompactLocal(MarkCompactSpace space) {
    super(space, true);
  }
  
  /**
   * Perform the compacting phase of the collection.
   */
  public void compact() {
    /* Has this allocator ever allocated anything? */
    if (initialRegion.isZero()) return;

    /* Loop through active regions or until the last region */
    Address start = initialRegion;
    Address allocStart = initialRegion;
    Address allocEnd = initialRegion.add(REGION_LIMIT_OFFSET).loadAddress();
    Address allocCursor = allocStart.add(DATA_START_OFFSET);

    /* Keep track of which regions are being used */
    int oldPages = 0;
    int newPages = 0;

    while(!start.isZero()) {      
      /* Get the end of this region */
      Address end = start.add(REGION_LIMIT_OFFSET).loadAddress();
      Address dataEnd = start.add(DATA_END_OFFSET).loadAddress();
      Address nextRegion = start.add(NEXT_REGION_OFFSET).loadAddress();
      oldPages += Conversions.bytesToPages(end.diff(start).add(BYTES_IN_ADDRESS));

      /* dataEnd = zero represents the current region. */
      Address currentLimit = (dataEnd.isZero() ? cursor : dataEnd);
      ObjectReference current =
        ObjectModel.getObjectFromStartAddress(start.add(DATA_START_OFFSET));
      
      while (ObjectModel.refToAddress(current).LT(currentLimit) && !current.isNull()) {
        ObjectReference next = ObjectModel.getNextObject(current);

        ObjectReference copyTo = MarkCompactSpace.getForwardingPointer(current);
        
        if (!copyTo.isNull() && Space.isInSpace(MC.MARK_COMPACT, copyTo)) {
          if (Assert.VERIFY_ASSERTIONS) Assert._assert(!MarkCompactSpace.isMarked(current));
          // To be copied.
          if (copyTo.toAddress().GT(allocEnd) || copyTo.toAddress().LT(allocStart)) {
            // changed regions.
            
            Memory.zero(allocCursor, allocEnd.diff(allocCursor).toWord().toExtent().add(BYTES_IN_ADDRESS));
             
            allocStart.store(allocCursor, DATA_END_OFFSET);
            allocStart = allocStart.add(NEXT_REGION_OFFSET).loadAddress();
            allocEnd = allocStart.add(REGION_LIMIT_OFFSET).loadAddress();
            allocCursor = allocStart.add(DATA_START_OFFSET);
            
            newPages += Conversions.bytesToPages(allocEnd.diff(allocStart).add(BYTES_IN_ADDRESS));
            
            if (Assert.VERIFY_ASSERTIONS) {
              Assert._assert(allocCursor.LT(allocEnd) && allocCursor.GE(allocStart));
            }
          }
          Address newAllocCursor = ObjectModel.copyTo(current, copyTo, allocCursor);
          allocCursor = newAllocCursor;
          MarkCompactSpace.setForwardingPointer(copyTo, ObjectReference.nullReference());
        }
        current = next;
      }
      if (dataEnd.isZero()) {
        break;
      }
      start = nextRegion;
    }
    Extent zeroBytes = allocEnd.diff(allocCursor).toWord().toExtent().add(BYTES_IN_ADDRESS);
    Memory.zero(allocCursor, zeroBytes);
    
    allocStart.store(Address.zero(), DATA_END_OFFSET);
    region = allocStart;
    cursor = allocCursor;
    limit = allocEnd;
    if (oldPages > newPages) {
      ((MarkCompactSpace)space).unusePages((oldPages - newPages));
    }
    
    // Zero during GC to help debugging.
    allocStart = allocStart.loadAddress(NEXT_REGION_OFFSET);
    while(!allocStart.isZero()) {
      allocStart.store(Address.zero(), DATA_END_OFFSET);
      if (Assert.VERIFY_ASSERTIONS) {
        Address low = allocStart.add(DATA_START_OFFSET);
        Extent size = allocStart.loadAddress(REGION_LIMIT_OFFSET).diff(allocStart).toWord().toExtent().sub(2 * BYTES_IN_ADDRESS);
        Memory.zero(low, size);
      }
      allocStart = allocStart.loadAddress(NEXT_REGION_OFFSET);
    }
  }
  
  /**
   * Perform a linear scan through the objects allocated by this bump pointer,
   * calculating where each live object will be post collection. 
   */
  public void calculateForwardingPointers() {
    /* Has this allocator ever allocated anything? */
    if (initialRegion.isZero()) return;

    /* Loop through active regions or until the last region */
    Address start = initialRegion;
    Address allocStart = initialRegion;
    Address allocDataEnd = initialRegion.add(DATA_END_OFFSET).loadAddress();
    Address allocLimit = (allocDataEnd.isZero() ? cursor : allocDataEnd);
    Address allocCursor = start.add(DATA_START_OFFSET);
    
    while(!start.isZero()) {      
      /* Get the end of this region */
      Address dataEnd = start.add(DATA_END_OFFSET).loadAddress();

      /* dataEnd = zero represents the current region. */
      Address currentLimit = (dataEnd.isZero() ? cursor : dataEnd);
      ObjectReference current =
        ObjectModel.getObjectFromStartAddress(start.add(DATA_START_OFFSET));
      
      while (ObjectModel.refToAddress(current).LT(currentLimit) && !current.isNull()) {
        ObjectReference next = ObjectModel.getNextObject(current);

        if (MarkCompactSpace.toBeCompacted(current)) {
          if (Assert.VERIFY_ASSERTIONS) {
            Assert._assert(MarkCompactSpace.getForwardingPointer(current).isNull());
          }

          // Fake - allocate it.
          int size = ObjectModel.getSizeWhenCopied(current);
          int align = ObjectModel.getAlignWhenCopied(current);
          int offset = ObjectModel.getAlignOffsetWhenCopied(current);
          allocCursor = Allocator.alignAllocationNoFill(allocCursor, align, offset);
          
          boolean sameRegion = allocStart.EQ(start);
          
          if (!sameRegion && allocCursor.add(size).GT(allocLimit)) {
            allocStart = allocStart.add(NEXT_REGION_OFFSET).loadAddress();
            allocDataEnd = allocStart.add(DATA_END_OFFSET).loadAddress();
            allocLimit = (allocDataEnd.isZero() ? cursor : allocDataEnd);
            allocCursor = Allocator.alignAllocationNoFill(allocStart.add(DATA_START_OFFSET), align, offset);
          }
          
          ObjectReference target = ObjectModel.getReferenceWhenCopiedTo(current, allocCursor);
          if (sameRegion && target.toAddress().GE(current.toAddress())) {
            MarkCompactSpace.setForwardingPointer(current, current);
            allocCursor = ObjectModel.getObjectEndAddress(current);
          } else {
            MarkCompactSpace.setForwardingPointer(current, target);
            allocCursor = allocCursor.add(size);
          }
        }
        current = next;
      }
      if (dataEnd.isZero()) {
        break;
      }
      start = start.add(NEXT_REGION_OFFSET).loadAddress(); // Move on to next
    }
  }
  
  /**
   * Maximum size of a single region. Important for children that implement
   * load balancing or increments based on region size.
   * @return the maximum region size
   */
  protected Extent maximumRegionSize() { return Extent.fromInt(4 << LOG_CHUNK_SIZE) ; }
}

--- NEW FILE: MarkCompactSpace.java ---
/*
 * (C) Copyright Department of Computer Science,
 *     Australian National University. 2002
 */
package org.mmtk.policy;

import org.mmtk.plan.TraceLocal;
import org.mmtk.utility.heap.*;
import org.mmtk.utility.Constants;
import org.mmtk.utility.Log;

import org.mmtk.vm.Assert;
import org.mmtk.vm.ObjectModel;

import org.vmmagic.unboxed.*;
import org.vmmagic.pragma.*;

/**
 * This class implements functionality for a simple sliding mark-compact
 * space.
 *
 * $Id: MarkCompactSpace.java,v 1.1 2006/05/24 03:40:04 dframpton-oss Exp $
 *
 * @author Daniel Frampton
 * @version $Revision: 1.1 $
 * @date $Date: 2006/05/24 03:40:04 $
 */
public final class MarkCompactSpace extends Space
  implements Constants, Uninterruptible {

  /****************************************************************************
   *
   * Class variables
   */
  public static final int LOCAL_GC_BITS_REQUIRED = 1;
  public static final int GLOBAL_GC_BITS_REQUIRED = 0;
  public static final int GC_HEADER_WORDS_REQUIRED = 1;

  private static final Word GC_MARK_BIT_MASK = Word.one();
  private static final Offset FORWARDING_POINTER_OFFSET = ObjectModel.GC_HEADER_OFFSET();

  /****************************************************************************
   *
   * Instance variables
   */
  
  /****************************************************************************
   *
   * Initialization
   */
  
  /**
   * Construct a space that consumes a given fraction of the available
   * virtual memory.<p>
   *
   * The caller specifies the amount virtual memory to be used for
   * this space <i>as a fraction of the total available</i>.  If there
   * is insufficient address space, then the constructor will fail.
   *
   * @param name The name of this space (used when printing error messages etc)
   * @param pageBudget The number of pages this space may consume
   * before consulting the plan
   * @param frac The size of the space in virtual memory, as a
   * fraction of all available virtual memory
   * @param fromSpace The does this instance start life as from-space
   * (or to-space)?
   */
  public MarkCompactSpace(String name, int pageBudget, float frac) {
    super(name, true, false, frac);
    pr = new MonotonePageResource(pageBudget, this, start, extent);
  }
 
  /**
   * Prepare for a collection
   */
  public void prepare() {
    // nothing to do
  }
  
  /**
   * Release after a collection
   */
  public void release() {
    // nothing to do
  }
  
  
  /**
   * Notify that several pages are no longer in use.
   *
   * @param pages The number of pages
   */
  public void unusePages(int pages) {
    ((MonotonePageResource)pr).unusePages(pages);
  }
  
  /**
   * Notify that several pages are no longer in use.
   *
   * @param pages The number of pages
   */
  public void reusePages(int pages) {
    ((MonotonePageResource)pr).reusePages(pages);
  }

  /**
   * Release an allocated page or pages.  In this case we do nothing
   * because we only release pages enmasse.
   *
   * @param start The address of the start of the page or pages
   */
  public final void release(Address start) throws InlinePragma {
    Assert._assert(false);  // this policy only releases pages enmasse
  }

  /**
   * Trace an object under a copying collection policy.
   * If the object is already copied, the copy is returned.
   * Otherwise, a copy is created and returned.
   * In either case, the object will be marked on return.
   *
   * @param trace The trace being conducted.
   * @param object The object to be forwarded.
   * @return The forwarded object.
   */
  public ObjectReference traceObject(TraceLocal trace, ObjectReference object)
    throws InlinePragma {
    if (Assert.VERIFY_ASSERTIONS) {
      Assert._assert(false);
    }
    return null;
  }
  
  /**
   * Trace an object under a copying collection policy.
   * If the object is already copied, the copy is returned.
   * Otherwise, a copy is created and returned.
   * In either case, the object will be marked on return.
   *
   * @param trace The trace being conducted.
   * @param object The object to be forwarded.
   * @return The forwarded object.
   */
  public ObjectReference traceMarkObject(TraceLocal trace, ObjectReference object)
    throws InlinePragma {
    if (testAndMark(object)) {
      trace.enqueue(object);
    } else if (!getForwardingPointer(object).isNull()) {
      return getForwardingPointer(object);
    }
    return object;
  }

  /**
   * Trace an object under a copying collection policy.
   * If the object is already copied, the copy is returned.
   * Otherwise, a copy is created and returned.
   * In either case, the object will be marked on return.
   *
   * @param trace The trace being conducted.
   * @param object The object to be forwarded.
   * @return The forwarded object.
   */
  public ObjectReference traceForwardObject(TraceLocal trace, ObjectReference object)
    throws InlinePragma {
    if (testAndClearMark(object)) {
      trace.enqueue(object);
    }
    ObjectReference newObject = getForwardingPointer(object);
    if (Assert.VERIFY_ASSERTIONS) Assert._assert(!newObject.isNull());
    return getForwardingPointer(object);
  }

  /**
   * Is this object live?
   * 
   * @param object The object
   * @return True if the object is live
   */
  public final boolean isLive(ObjectReference object) {
    return isMarked(object);
  }
  
  /**
   * Has the object in this space been reached during the current collection.
   * This is used for GC Tracing.
   * 
   * @param object The object reference.
   * @return True if the object is reachable.
   */
  public final boolean isReachable(ObjectReference object) {
    return isMarked(object);
  }


  /****************************************************************************
   *
   * Header manipulation
   */
  
  /**
   * Perform any required post-allocation initialization
   * 
   * <i>Nothing to be done in this case</i> 
   * 
   * @param object the object ref to the storage to be initialized
   */
   public final void postAlloc(ObjectReference object) throws InlinePragma {
   }

  /**
   * Non-atomic read of forwarding pointer
   *
   * @param object The object whose forwarding pointer is to be read
   * @return The forwarding pointer stored in <code>object</code>'s
   * header.
   */
  public static ObjectReference getForwardingPointer(ObjectReference object) 
    throws InlinePragma {
    return object.toAddress().loadObjectReference(FORWARDING_POINTER_OFFSET);
  }
  
  /**
   * Initialise the header of the object.
   * 
   * @param object The object to initialise
   */
  public void initializeHeader(ObjectReference object)
    throws InlinePragma {
    // nothing to do
  }

  /**
   * Used to mark boot image objects during a parallel scan of objects
   * during GC Returns true if marking was done.
   *
   * @param object The object to be marked
   * @param value The value to store in the mark bit
   */
  public static boolean testAndMark(ObjectReference object) 
    throws InlinePragma {
    Word oldValue;
    do {
      oldValue = ObjectModel.prepareAvailableBits(object);
      Word markBit = oldValue.and(GC_MARK_BIT_MASK);
      if (!markBit.isZero()) return false;
    } while (!ObjectModel.attemptAvailableBits(object, oldValue, 
                                                oldValue.or(GC_MARK_BIT_MASK)));
    return true;
  }
  
  /**
   * Used to mark boot image objects during a parallel scan of objects
   * during GC Returns true if marking was done.
   *
   * @param object The object to be marked
   * @param value The value to store in the mark bit
   */
  public static boolean isMarked(ObjectReference object) 
    throws InlinePragma {
    Word oldValue = ObjectModel.readAvailableBitsWord(object);
    Word markBit = oldValue.and(GC_MARK_BIT_MASK);
    return (!markBit.isZero());
  }
  
  /**
   * Used to mark boot image objects during a parallel scan of objects
   * during GC Returns true if marking was done.
   *
   * @param object The object to be marked
   * @param value The value to store in the mark bit
   */
  private static boolean testAndClearMark(ObjectReference object) 
    throws InlinePragma {
    Word oldValue;
    do {
      oldValue = ObjectModel.prepareAvailableBits(object);
      Word markBit = oldValue.and(GC_MARK_BIT_MASK);
      if (markBit.isZero()) return false;
    } while (!ObjectModel.attemptAvailableBits(object, oldValue, 
                                                oldValue.and(GC_MARK_BIT_MASK.not())));
    return true;
  }
  
  
  /**
   * Used to mark boot image objects during a parallel scan of objects
   * during GC Returns true if marking was done.
   *
   * @param object The object to be marked
   * @param value The value to store in the mark bit
   */
  public static boolean toBeCompacted(ObjectReference object) 
    throws InlinePragma {
    Word oldValue= ObjectModel.readAvailableBitsWord(object);
    Word markBit = oldValue.and(GC_MARK_BIT_MASK);
    return !markBit.isZero() && getForwardingPointer(object).isNull();
  }
  
  /**
   * Used to mark boot image objects during a parallel scan of objects
   * during GC Returns true if marking was done.
   *
   * @param object The object to be marked
   * @param value The value to store in the mark bit
   */
  public static void clearMark(ObjectReference object) 
    throws InlinePragma {
    Word oldValue = ObjectModel.readAvailableBitsWord(object);
    ObjectModel.writeAvailableBitsWord(object, oldValue.and(GC_MARK_BIT_MASK.not()));
  }

  /**
   * Non-atomic write of forwarding pointer word (assumption, thread
   * doing the set has done attempt to forward and owns the right to
   * copy the object)
   *
   * @param object The object whose forwarding pointer is to be set
   * @param ptr The forwarding pointer to be stored in the object's
   * forwarding word
   */
  public static void setForwardingPointer(ObjectReference object, 
                                           ObjectReference ptr)
    throws InlinePragma {
    object.toAddress().store(ptr.toAddress(), FORWARDING_POINTER_OFFSET);
  }
  
  /**
   * Non-atomic clear of forwarding pointer word (assumption, thread
   * doing the set has done attempt to forward and owns the right to
   * copy the object)
   *
   * @param object The object whose forwarding pointer is to be set
   */
  public static void clearForwardingPointer(ObjectReference object)
    throws InlinePragma {
    object.toAddress().store(Address.zero(), FORWARDING_POINTER_OFFSET);
  }
}

Update of /cvsroot/jikesrvm/MMTk/ext/vm/stub/org/mmtk/vm
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/MMTk/ext/vm/stub/org/mmtk/vm

Modified Files:
	ObjectModel.java ReferenceGlue.java 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



Index: ReferenceGlue.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/ext/vm/stub/org/mmtk/vm/ReferenceGlue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** ReferenceGlue.java	22 Sep 2005 00:55:52 -0000	1.3
--- ReferenceGlue.java	24 May 2006 03:40:04 -0000	1.4
***************
*** 37,40 ****
--- 37,46 ----
  
    /**
+    * Scan through all references and forward. Only called when references
+    * are objects.
+    */
+   public static void forwardReferences() {}
+ 
+   /**
     * Put this Reference object on its ReferenceQueue (if it has one)
     * when its referent is no longer sufficiently reachable. The

Index: ObjectModel.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/ext/vm/stub/org/mmtk/vm/ObjectModel.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** ObjectModel.java	22 Sep 2005 00:55:52 -0000	1.3
--- ObjectModel.java	24 May 2006 03:40:04 -0000	1.4
***************
*** 37,42 ****
--- 37,72 ----
      return null;
    }
+   
+   /**
+    * Copy an object to be pointer to by the to address. This is required 
+    * for delayed-copy collectors such as compacting collectors. During the 
+    * collection, MMTk reserves a region in the heap for an object as per
+    * requirements found from ObjectModel and then asks ObjectModel to 
+    * determine what the object's reference will be post-copy.
+    * 
+    * @param from the address of the object to be copied
+    * @param to The target location.
+    * @param region The start of the region that was reserved for this object
+    * @return Address The address past the end of the copied object
+    */
+   public static Address copyTo(ObjectReference from, ObjectReference to, Address region) {
+     return null;
+   }
  
    /**
+    * Return the reference that an object will be refered to after it is copied
+    * to the specified region. Used in delayed-copy collectors such as compacting
+    * collectors.
+    *
+    * @param from The object to be copied.
+    * @param to The region to be copied to.
+    * @return The resulting reference.
+    */
+   public static ObjectReference getReferenceWhenCopiedTo(ObjectReference from, Address to) {
+     return null;
+   }
+   
+   
+   /**
     * Return the size required to copy an object
     *
***************
*** 47,50 ****
--- 77,101 ----
      return 0;
    }
+   
+   /**
+    * Return the alignment requirement for a copy of this object
+    *
+    * @param object The object whose size is to be queried
+    * @return The alignment required for a copy of <code>obj</code>
+    */
+   public static int getAlignWhenCopied(ObjectReference object) {
+     return 0;
+   }
+   
+   /**
+    * Return the alignment offset requirements for a copy of this object
+    *
+    * @param object The object whose size is to be queried
+    * @return The alignment offset required for a copy of <code>obj</code>
+    */
+   public static int getAlignOffsetWhenCopied(ObjectReference object) {
+     return 0;
+   }
+   
      
    /**
***************
*** 73,76 ****
--- 124,137 ----
    
    /**
+    * Gets a pointer to the address just past the end of the object.
+    * 
+    * @param object The objecty.
+    */
+   public static Address getObjectEndAddress(ObjectReference object) {
+     return null;
+   }
+   
+   
+   /**
     * Get the type descriptor for an object.
     *
***************
*** 214,216 ****
--- 275,281 ----
      return null;
    }
+   
+   public static void dumpRef(ObjectReference object) {
+     
+   }
  }

Update of /cvsroot/jikesrvm/rvm/config/build/gc
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/rvm/config/build/gc

Added Files:
	MarkCompact 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



--- NEW FILE: MarkCompact ---
   export RVM_WITH_JMTK_INLINE_PLAN=1
   export RVM_WITH_JMTK_PLAN="org.mmtk.plan.markcompact.MC"

Update of /cvsroot/jikesrvm/MMTk/src/org/mmtk/utility/sanitychecker
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/MMTk/src/org/mmtk/utility/sanitychecker

Modified Files:
	SanityChecker.java 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



Index: SanityChecker.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/src/org/mmtk/utility/sanitychecker/SanityChecker.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** SanityChecker.java	26 Nov 2005 21:00:32 -0000	1.1
--- SanityChecker.java	24 May 2006 03:40:05 -0000	1.2
***************
*** 109,116 ****
        sanityTable.releaseTable();
     
!       Log.writeln("roots\tobjects\tdangling");
        Log.write(rootReferenceCount);Log.write("\t");
        Log.write(liveObjectCount);Log.write("\t");
!       Log.writeln(danglingReferenceCount);
        
        Log.write("========================================");
--- 109,117 ----
        sanityTable.releaseTable();
     
!       Log.writeln("roots\tobjects\trefs\tnull");
        Log.write(rootReferenceCount);Log.write("\t");
        Log.write(liveObjectCount);Log.write("\t");
!       Log.write(referenceCount);Log.write("\t");
!       Log.writeln(nullReferenceCount);
        
        Log.write("========================================");

Update of /cvsroot/jikesrvm/rvm/config/build
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/rvm/config/build

Added Files:
	BaseBaseMarkCompact FastAdaptiveMarkCompact 
	FullAdaptiveMarkCompact 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



--- NEW FILE: FastAdaptiveMarkCompact ---
. $1/gc/MarkCompact
. $1/compilers/FastAdaptive

--- NEW FILE: BaseBaseMarkCompact ---
. $1/gc/MarkCompact
. $1/compilers/BaseBase

--- NEW FILE: FullAdaptiveMarkCompact ---
. $1/gc/MarkCompact
. $1/compilers/FullAdaptive

Update of /cvsroot/jikesrvm/MMTk/src/org/mmtk/plan
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/MMTk/src/org/mmtk/plan

Modified Files:
	PlanConstraints.java StopTheWorld.java 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



Index: PlanConstraints.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/src/org/mmtk/plan/PlanConstraints.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** PlanConstraints.java	20 Jul 2005 14:32:06 -0000	1.1
--- PlanConstraints.java	24 May 2006 03:40:04 -0000	1.2
***************
*** 61,63 ****
--- 61,65 ----
    public boolean generateGCTrace() { return false; }
   
+   /** @return True if type information must be immortal */
+   public boolean needsImmortalTypeInfo() { return false; }
  }

Index: StopTheWorld.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/src/org/mmtk/plan/StopTheWorld.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** StopTheWorld.java	26 Nov 2005 21:00:33 -0000	1.2
--- StopTheWorld.java	24 May 2006 03:40:04 -0000	1.3
***************
*** 99,119 ****
     * Start the collection, including preparation for any collected spaces.
     */
!   private static final int initPhase = new ComplexPhase("init", new int[] {
        INITIATE,
        SANITY_PLACEHOLDER,
!       PREPARE,
!       PRECOPY}).getId();
  
    /**
     * Perform the initial determination of liveness from the roots.
     */
!   private static final int rootClosurePhase = new ComplexPhase("initial-closure", null, new int[] {
        ROOTS,
        START_CLOSURE}).getId();
  
    /**
!    *  Complete closure including referece types and finalizable objects.
     */
!   private static final int refTypeClosurePhase = new ComplexPhase("refType-closure", null, new int[] {
        SOFT_REFS,    COMPLETE_CLOSURE,
        WEAK_REFS,
--- 99,120 ----
     * Start the collection, including preparation for any collected spaces.
     */
!   protected static final int initPhase = new ComplexPhase("init", new int[] {
        INITIATE,
        SANITY_PLACEHOLDER,
!       }).getId();
  
    /**
     * Perform the initial determination of liveness from the roots.
     */
!   protected static final int rootClosurePhase = new ComplexPhase("initial-closure", null, new int[] {
!       PREPARE,
!       PRECOPY,
        ROOTS,
        START_CLOSURE}).getId();
  
    /**
!    *  Complete closure including reference types and finalizable objects.
     */
!   protected static final int refTypeClosurePhase = new ComplexPhase("refType-closure", null, new int[] {
        SOFT_REFS,    COMPLETE_CLOSURE,
        WEAK_REFS,
***************
*** 121,129 ****
        WEAK_TRACK_REFS,
        PHANTOM_REFS}).getId();
! 
!   /**
     * Ensure that all references in the system are correct.
     */
!   private static final int forwardPhase = new ComplexPhase("forward-all", null, new int[] {
        /* Finish up */
        FORWARD,
--- 122,130 ----
        WEAK_TRACK_REFS,
        PHANTOM_REFS}).getId();
!   
!     /**
     * Ensure that all references in the system are correct.
     */
!   protected static final int forwardPhase = new ComplexPhase("forward-all", null, new int[] {
        /* Finish up */
        FORWARD,
***************
*** 132,139 ****
  
    /**
!    * The collection scheme - this is a small tree of complex phases.
     */
!   private static final int finishPhase = new ComplexPhase("finish", new int[] {
        RELEASE,
        SANITY_PLACEHOLDER,
        COMPLETE}).getId();
--- 133,147 ----
  
    /**
!    *  Complete closure including reference types and finalizable objects.
     */
!   protected static final int completeClosurePhase = new ComplexPhase("refType-closure", null, new int[] {
        RELEASE,
+       }).getId();
+ 
+ 
+   /**
+    * The collection scheme - this is a small tree of complex phases.
+    */
+   protected static final int finishPhase = new ComplexPhase("finish", new int[] {
        SANITY_PLACEHOLDER,
        COMPLETE}).getId();
***************
*** 147,150 ****
--- 155,159 ----
        refTypeClosurePhase,
        forwardPhase,
+       completeClosurePhase,
        finishPhase});

Update of /cvsroot/jikesrvm/MMTk/src/org/mmtk/utility
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv8141/MMTk/src/org/mmtk/utility

Modified Files:
	Finalizer.java ReferenceProcessor.java 
Log Message:
Added initial version of the full heap Sliding Mark Compact collector. Will be added to regressions asap.



Index: Finalizer.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/src/org/mmtk/utility/Finalizer.java,v
retrieving revision 1.18
retrieving revision 1.19
diff -C2 -d -r1.18 -r1.19
*** Finalizer.java	28 Jul 2005 00:04:00 -0000	1.18
--- Finalizer.java	24 May 2006 03:40:04 -0000	1.19
***************
*** 10,13 ****
--- 10,14 ----
  import org.mmtk.vm.Assert;
  import org.mmtk.vm.Lock;
+ import org.mmtk.vm.ObjectModel;
  
  import org.vmmagic.unboxed.*;
***************
*** 198,203 ****
      while (cursor < candidateEnd) {
        Address cand = candidate.get(cursor);
!       candidate.set(cursor,
!         trace.getForwardedFinalizable(cand.toObjectReference()).toAddress());
        cursor++;
      }
--- 199,204 ----
      while (cursor < candidateEnd) {
        Address cand = candidate.get(cursor);
!       ObjectReference newCandidate = trace.getForwardedFinalizable(cand.toObjectReference()); 
!       candidate.set(cursor, newCandidate.toAddress());
        cursor++;
      }

Index: ReferenceProcessor.java
===================================================================
RCS file: /cvsroot/jikesrvm/MMTk/src/org/mmtk/utility/ReferenceProcessor.java,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** ReferenceProcessor.java	20 Jul 2005 14:32:12 -0000	1.16
--- ReferenceProcessor.java	24 May 2006 03:40:04 -0000	1.17
***************
*** 77,80 ****
--- 77,118 ----
      }
    }
+   
+   /**
+    * Forward a reference object.
+    * 
+    * @param reference The reference to forward
+    * @return The forwarded reference
+    */
+   public static Address forwardReference(Address reference) {
+     if (Assert.VERIFY_ASSERTIONS) {
+       Assert._assert(!reference.isZero());
+       Assert._assert(ReferenceGlue.REFERENCES_ARE_OBJECTS);
+     }
+     
+     TraceLocal trace = ActivePlan.local().getCurrentTrace();
+     
+     ObjectReference referent = ReferenceGlue.getReferent(reference);
+     
+     if (TRACE) {
+       Log.write("+++ old reference: "); Log.writeln(reference);
+       Log.write("    old referent:  "); Log.writeln(referent);
+     }
+     
+     referent = trace.getForwardedReferent(referent);
+     ReferenceGlue.setReferent(reference, referent);
+ 
+ 
+     
+     if (ReferenceGlue.REFERENCES_ARE_OBJECTS) {
+       reference = trace.getForwardedReference(reference.toObjectReference()).toAddress();
+     }
+ 
+     if (TRACE) {
+       Log.write("    new reference: "); Log.writeln(reference);
+       Log.write("    new referent:  "); Log.writeln(referent);
+     }
+ 
+     return reference;
+   }
  
    /**
***************
*** 105,109 ****
        /* Otherwise... */
        if (ReferenceGlue.REFERENCES_ARE_OBJECTS)
!         newReference = trace.getForwardedReferent(reference.toObjectReference()).toAddress();
        else
          newReference = reference;
--- 143,147 ----
        /* Otherwise... */
        if (ReferenceGlue.REFERENCES_ARE_OBJECTS)
!         newReference = trace.getForwardedReference(reference.toObjectReference()).toAddress();
        else
          newReference = reference;
***************
*** 251,256 ****
     */
    public static void forwardReferences() {
!     //  TODO: ReferenceGlue.forwardReferences(trace);
!     Assert._assert(false);
    }
  }
--- 289,299 ----
     */
    public static void forwardReferences() {
!     if (TRACE) {
!       Log.writeln("Starting ReferenceProcessor.forwardReferences()");
!     }
!     ReferenceGlue.forwardReferences();
!     if (TRACE) {
!       Log.writeln("Ending ReferenceProcessor.forwardReferences()");
!     }
    }
  }