# HG changeset patch
# User Christian Wimmer <Christian.Wimmer@Oracle.com>
# Date 1325124805 28800
# Node ID f5328dda971440ab3d5feaa72febb6beeb40900e
# Parent  0bc4815d2069f14749b3e073cb88a09a6fac087e
Initial commit of SSA-based spill-all register assignment

diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiAddress.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiAddress.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiAddress.java	Wed Dec 28 18:13:25 2011 -0800
@@ -230,13 +230,13 @@
     }
 
     @Override
-    public String name() {
+    public String toString() {
         // Checkstyle: stop
         switch (format()) {
-            case BASE            : return "[" + s(base) + "]";
-            case BASE_DISP       : return "[" + s(base) + signed(displacement) + "]";
-            case BASE_INDEX      : return "[" + s(base) + "+" + s(index) + "]";
-            case BASE_INDEX_DISP : return "[" + s(base) + "+(" + s(index) + "*" + scale.value + ")" + signed(displacement) + "]";
+            case BASE            : return "[" + s(base) + kindSuffix() + "]";
+            case BASE_DISP       : return "[" + s(base) + signed(displacement) + kindSuffix() + "]";
+            case BASE_INDEX      : return "[" + s(base) + "+" + s(index) + kindSuffix() + "]";
+            case BASE_INDEX_DISP : return "[" + s(base) + "+(" + s(index) + "*" + scale.value + ")" + signed(displacement) + kindSuffix() + "]";
             case PLACEHOLDER     : return "[<placeholder>]";
             default              : throw new IllegalArgumentException("unknown format: " + format());
         }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java	Wed Dec 28 18:13:25 2011 -0800
@@ -62,6 +62,19 @@
     }
 
     /**
+     * Constructs a copy of the given bit map.
+     *
+     * @param bitmap the bit map to copy.
+     */
+    public CiBitMap(CiBitMap bitmap) {
+        this.size = bitmap.size;
+        this.low = bitmap.low;
+        if (bitmap.extra != null) {
+            this.extra = Arrays.copyOf(bitmap.extra, bitmap.extra.length);
+        }
+    }
+
+    /**
      * Constructs a new bit map from a byte array encoded bit map.
      *
      * @param arr the byte array containing the bit map to convert
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiConstant.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiConstant.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiConstant.java	Wed Dec 28 18:13:25 2011 -0800
@@ -30,7 +30,7 @@
 public final class CiConstant extends CiValue {
 
     /**
-     * 
+     *
      */
     private static final long serialVersionUID = -6355452536852663986L;
     private static final CiConstant[] INT_CONSTANT_CACHE = new CiConstant[100];
@@ -129,8 +129,8 @@
     }
 
     @Override
-    public String name() {
-        return "const[" + kind.format(boxedValue()) + (kind != CiKind.Object ? "|0x" + Long.toHexString(primitive) : "") + "]";
+    public String toString() {
+        return kind.javaName + "[" + kind.format(boxedValue()) + (kind != CiKind.Object ? "|0x" + Long.toHexString(primitive) : "") + "]";
     }
 
     /**
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiMonitorValue.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiMonitorValue.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiMonitorValue.java	Wed Dec 28 18:13:25 2011 -0800
@@ -23,13 +23,11 @@
 package com.sun.cri.ci;
 
 public final class CiMonitorValue extends CiValue {
-    /**
-     * 
-     */
     private static final long serialVersionUID = 8241681800464483691L;
-    public final CiValue owner;
-    public final CiValue lockData;
-    public final boolean eliminated;
+
+    public CiValue owner;
+    public CiValue lockData;
+    public boolean eliminated;
 
     public CiMonitorValue(CiValue owner, CiValue lockData, boolean eliminated) {
         super(CiKind.Illegal);
@@ -40,22 +38,7 @@
     }
 
     @Override
-    public String name() {
-        return "monitor";
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-        return this == obj;
-    }
-
-    @Override
-    public boolean equalsIgnoringKind(CiValue other) {
-        return this == other;
-    }
-
-    @Override
-    public int hashCode() {
-        return 0;
+    public String toString() {
+        return "monitor[" + owner + (lockData != null ? ", " + lockData : "") + (eliminated ? ", eliminated" : "") + "]";
     }
 }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiRegisterValue.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiRegisterValue.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiRegisterValue.java	Wed Dec 28 18:13:25 2011 -0800
@@ -28,12 +28,9 @@
  * retrieve the canonical {@link CiRegisterValue} instance for a given (register,kind) pair.
  */
 public final class CiRegisterValue extends CiValue {
+    private static final long serialVersionUID = 7999341472196897163L;
 
     /**
-     * 
-     */
-    private static final long serialVersionUID = 7999341472196897163L;
-    /**
      * The register.
      */
     public final CiRegister reg;
@@ -41,14 +38,14 @@
     /**
      * Should only be called from {@link CiRegister#CiRegister} to ensure canonicalization.
      */
-    CiRegisterValue(CiKind kind, CiRegister register) {
+    protected CiRegisterValue(CiKind kind, CiRegister register) {
         super(kind);
         this.reg = register;
     }
 
     @Override
     public int hashCode() {
-        return kind.ordinal() ^ reg.number;
+        return (reg.number << 4) ^ kind.ordinal();
     }
 
     @Override
@@ -65,8 +62,8 @@
     }
 
     @Override
-    public String name() {
-        return reg.name;
+    public String toString() {
+        return reg.name + kindSuffix();
     }
 
     @Override
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiStackSlot.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiStackSlot.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiStackSlot.java	Wed Dec 28 18:13:25 2011 -0800
@@ -29,7 +29,7 @@
 public final class CiStackSlot extends CiValue {
 
     /**
-     * 
+     *
      */
     private static final long serialVersionUID = -7725071921307318433L;
 
@@ -122,8 +122,8 @@
     }
 
     @Override
-    public String name() {
-        return (inCallerFrame() ? "caller-stack" : "stack:") + index();
+    public String toString() {
+        return (inCallerFrame() ? "caller-stack" : "stack:") + index() + kindSuffix();
     }
 
     /**
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiValue.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiValue.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiValue.java	Wed Dec 28 18:13:25 2011 -0800
@@ -24,8 +24,6 @@
 
 import java.io.*;
 
-
-
 /**
  * Abstract base class for values manipulated by the compiler. All values have a {@linkplain CiKind kind} and are immutable.
  */
@@ -35,25 +33,13 @@
     @SuppressWarnings("serial")
     public static CiValue IllegalValue = new CiValue(CiKind.Illegal) {
         @Override
-        public String name() {
-            return "<illegal>";
+        public String toString() {
+            return "-";
         }
         @Override
         public CiRegister asRegister() {
             return CiRegister.None;
         }
-        @Override
-        public int hashCode() {
-            return -1;
-        }
-        @Override
-        public boolean equals(Object obj) {
-            return obj == this;
-        }
-        @Override
-        public boolean equalsIgnoringKind(CiValue other) {
-            return other == this;
-        }
     };
 
     /**
@@ -110,52 +96,19 @@
         return this instanceof CiConstant;
     }
 
-    /**
-     * Gets a string name for this value without indicating its {@linkplain #kind kind}.
-     */
-    public abstract String name();
-
-    @Override
-    public abstract boolean equals(Object obj);
-
-    public abstract boolean equalsIgnoringKind(CiValue other);
+    public boolean equalsIgnoringKind(CiValue other) {
+        // This is a suitable default implementation for several subclasses
+        return equals(other);
+    }
 
     @Override
-    public abstract int hashCode();
+    public abstract String toString();
 
-    @Override
-    public final String toString() {
-        return name() + kindSuffix();
-    }
-
-    public final String kindSuffix() {
-        if (kind == CiKind.Illegal) {
-            return "";
-        }
-        return ":" + kind.typeChar;
+    protected final String kindSuffix() {
+        return "|" + kind.typeChar;
     }
 
     public final boolean isConstant0() {
         return isConstant() && ((CiConstant) this).asInt() == 0;
     }
-
-    /**
-     * Utility for specializing how a {@linkplain CiValue LIR operand} is formatted to a string.
-     * The {@linkplain Formatter#DEFAULT default formatter} returns the value of
-     * {@link CiValue#toString()}.
-     */
-    public static class Formatter {
-        public static final Formatter DEFAULT = new Formatter();
-
-        /**
-         * Formats a given operand as a string.
-         *
-         * @param operand the operand to format
-         * @return {@code operand} as a string
-         */
-        public String format(CiValue operand) {
-            return operand.toString();
-        }
-    }
-
 }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVariable.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVariable.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVariable.java	Wed Dec 28 18:13:25 2011 -0800
@@ -30,7 +30,7 @@
 public final class CiVariable extends CiValue {
 
     /**
-     * 
+     *
      */
     private static final long serialVersionUID = 4507578431686109809L;
 
@@ -116,7 +116,7 @@
     }
 
     @Override
-    public String name() {
-        return "v" + index;
+    public String toString() {
+        return "v" + index + kindSuffix();
     }
 }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVirtualObject.java
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVirtualObject.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVirtualObject.java	Wed Dec 28 18:13:25 2011 -0800
@@ -29,11 +29,8 @@
  * deoptimization to recreate the object.
  */
 public final class CiVirtualObject extends CiValue {
+    private static final long serialVersionUID = -2907197776426346021L;
 
-    /**
-     * 
-     */
-    private static final long serialVersionUID = -2907197776426346021L;
     private final RiType type;
     private CiValue[] values;
     private final int id;
@@ -58,8 +55,8 @@
     }
 
     @Override
-    public String name() {
-        return "vobject";
+    public String toString() {
+        return "vobject:" + id;
     }
 
     /**
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.criutils/src/com/oracle/max/criutils/CompilationPrinter.java
--- a/graal/com.oracle.max.criutils/src/com/oracle/max/criutils/CompilationPrinter.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.criutils/src/com/oracle/max/criutils/CompilationPrinter.java	Wed Dec 28 18:13:25 2011 -0800
@@ -25,8 +25,6 @@
 import java.io.*;
 
 import com.sun.cri.ci.*;
-import com.sun.cri.ci.CiAddress.Scale;
-import com.sun.cri.ci.CiValue.Formatter;
 import com.sun.cri.ri.*;
 
 /**
@@ -105,7 +103,7 @@
     /**
      * Formats a given {@linkplain FrameState JVM frame state} as a multi line string.
      */
-    protected String debugInfoToString(CiCodePos codePos, CiBitMap registerRefMap, CiBitMap frameRefMap, OperandFormatter fmt, CiArchitecture arch) {
+    protected String debugInfoToString(CiCodePos codePos, CiBitMap registerRefMap, CiBitMap frameRefMap, CiArchitecture arch) {
         StringBuilder sb = new StringBuilder();
 
         if (registerRefMap != null) {
@@ -134,7 +132,7 @@
                     if (frame.numStack > 0) {
                         sb.append("stack: ");
                         for (int i = 0; i < frame.numStack; i++) {
-                            sb.append(valueToString(frame.getStackValue(i), fmt)).append(' ');
+                            sb.append(valueToString(frame.getStackValue(i))).append(' ');
                         }
                         sb.append("\n");
                     }
@@ -142,14 +140,14 @@
                     if (frame.numLocks > 0) {
                         sb.append("locks: ");
                         for (int i = 0; i < frame.numLocks; ++i) {
-                            sb.append(valueToString(frame.getLockValue(i), fmt)).append(' ');
+                            sb.append(valueToString(frame.getLockValue(i))).append(' ');
                         }
                         sb.append("\n");
                     }
 
                     sb.append("locals: ");
                     for (int i = 0; i < frame.numLocals; i++) {
-                        sb.append(valueToString(frame.getLocalValue(i), fmt)).append(' ');
+                        sb.append(valueToString(frame.getLocalValue(i))).append(' ');
                     }
                     sb.append("\n");
                 }
@@ -159,63 +157,11 @@
         return sb.toString();
     }
 
-
-    protected String valueToString(CiValue value, Formatter operandFmt) {
+    protected String valueToString(CiValue value) {
         if (value == null) {
             return "-";
         }
-        return operandFmt.format(value);
-    }
-
-
-    /**
-     * Formats LIR operands as expected by the C1 Visualizer.
-     */
-    public static class OperandFormatter extends Formatter {
-        /**
-         * The textual delimiters used for an operand depend on the context in which it is being
-         * printed. When printed as part of a frame state or as the result operand in a HIR node listing,
-         * it is enclosed in double-quotes (i.e. {@code "}'s).
-         */
-        public final boolean asStateOrHIROperandResult;
-
-        public OperandFormatter(boolean asStateOrHIROperandResult) {
-            this.asStateOrHIROperandResult = asStateOrHIROperandResult;
-        }
-
-        @Override
-        public String format(CiValue operand) {
-            if (operand.isLegal()) {
-                String op;
-                if (operand.isVariableOrRegister() || operand.isStackSlot()) {
-                    op = operand.name();
-                } else if (operand.isConstant()) {
-                    CiConstant constant = (CiConstant) operand;
-                    op = operand.kind.javaName + ":" + operand.kind.format(constant.boxedValue());
-                } else if (operand.isAddress()) {
-                    CiAddress address = (CiAddress) operand;
-                    op = "Base:" + format(address.base);
-                    if (!address.index.isIllegal()) {
-                        op += " Index:" + format(address.index);
-                    }
-                    if (address.scale != Scale.Times1) {
-                        op += " * " + address.scale.value;
-                    }
-                    op += " Disp:" + address.displacement;
-                } else {
-                    assert operand.isIllegal();
-                    op = "-";
-                }
-                if (operand.kind != CiKind.Illegal) {
-                    op += "|" + operand.kind.typeChar;
-                }
-                if (asStateOrHIROperandResult) {
-                    op = " \"" + op.replace('"', '\'') + "\" ";
-                }
-                return op;
-            }
-            return "";
-        }
+        return value.toString();
     }
 
     public void printMachineCode(String code, String label) {
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/AssignRegisters.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/AssignRegisters.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,130 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.simple;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.sun.cri.ci.*;
+
+public abstract class AssignRegisters {
+    public final LIR lir;
+    public final FrameMap frameMap;
+
+    public AssignRegisters(LIR lir, FrameMap frameMap) {
+        this.lir = lir;
+        this.frameMap = frameMap;
+    }
+
+    private CiBitMap curRegisterRefMap;
+    private CiBitMap curFrameRefMap;
+
+    public void execute() {
+        ValueProcedure useProc =          new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value); } };
+        ValueProcedure defProc =          new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value); } };
+        ValueProcedure setReferenceProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return setReference(value); } };
+
+        trace(1, "==== start assign registers ====");
+        for (int i = lir.linearScanOrder().size() - 1; i >= 0; i--) {
+            LIRBlock block = lir.linearScanOrder().get(i);
+            trace(1, "start block %s", block);
+            assert block.phis == null : "Register assignment must run after phi functions have been replaced by moves";
+
+            curRegisterRefMap = frameMap.initRegisterRefMap();
+            curFrameRefMap = frameMap.initFrameRefMap();
+
+            // Put all values live at the end of the block into the reference map.
+            locationsForBlockEnd(block).forEachLocation(setReferenceProc);
+
+            for (int j = block.lir().size() - 1; j >= 0; j--) {
+                LIRInstruction op = block.lir().get(j);
+                trace(1, "  op %d %s", op.id(), op);
+
+                op.forEachOutput(defProc);
+                op.forEachTemp(defProc);
+                op.forEachState(useProc);
+                op.forEachAlive(useProc);
+
+                if (op.info != null) {
+                    trace(3, "    registerRefMap: %s  frameRefMap: %s", curRegisterRefMap, curFrameRefMap);
+                    op.info.finish(new CiBitMap(curRegisterRefMap), new CiBitMap(curFrameRefMap), frameMap);
+
+                    if (op instanceof LIRXirInstruction) {
+                        LIRXirInstruction xir = (LIRXirInstruction) op;
+                        if (xir.infoAfter != null) {
+                            xir.infoAfter.finish(op.hasCall() ? null : new CiBitMap(curRegisterRefMap), new CiBitMap(curFrameRefMap), frameMap);
+                        }
+                    }
+                }
+
+                // Process input operands after assigning the reference map, so that input operands that are used
+                // for the last time at this instruction are not part of the reference map.
+                op.forEachInput(useProc);
+            }
+            trace(1, "end block %s", block);
+        }
+        trace(1, "==== end assign registers ====");
+    }
+
+    private CiValue use(CiValue value) {
+        trace(3, "    use %s", value);
+        if (isLocation(value)) {
+            CiValue location = asLocation(value).location;
+            frameMap.setReference(location, curRegisterRefMap, curFrameRefMap);
+            return location;
+        } else {
+            frameMap.setReference(value, curRegisterRefMap, curFrameRefMap);
+            return value;
+        }
+    }
+
+    private CiValue def(CiValue value) {
+        trace(3, "    def %s", value);
+        if (isLocation(value)) {
+            CiValue location = asLocation(value).location;
+            frameMap.clearReference(location, curRegisterRefMap, curFrameRefMap);
+            return location;
+        } else {
+            frameMap.clearReference(value, curRegisterRefMap, curFrameRefMap);
+            return value;
+        }
+    }
+
+    private CiValue setReference(CiValue value) {
+        trace(3, "    setReference %s", value);
+        frameMap.setReference(asLocation(value).location, curRegisterRefMap, curFrameRefMap);
+        return value;
+    }
+
+    protected abstract LocationMap locationsForBlockEnd(LIRBlock block);
+
+    private static void trace(int level, String format, Object...args) {
+        if (GraalOptions.TraceRegisterAllocationLevel >= level) {
+            TTY.println(format, args);
+        }
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,342 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.simple;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.alloc.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.oracle.max.graal.compiler.schedule.*;
+import com.sun.cri.ci.*;
+import com.sun.cri.ri.*;
+
+public class DataFlowAnalysis {
+    private final GraalContext context;
+    private final LIR lir;
+    private final OperandPool operands;
+    private final RiRegisterConfig registerConfig;
+    private final CiCallingConvention incomingArguments;
+
+    public DataFlowAnalysis(GraalContext context, LIR lir, OperandPool operands, RiRegisterConfig registerConfig, CiCallingConvention incomingArguments) {
+        this.context = context;
+        this.lir = lir;
+        this.operands = operands;
+        this.registerConfig = registerConfig;
+        this.incomingArguments = incomingArguments;
+    }
+
+    public void execute() {
+        numberInstructions();
+        context.observable.fireCompilationEvent("After instruction numbering", lir);
+        backwardDataFlow();
+    }
+
+
+    private List<LIRBlock> blocks() {
+        return lir.linearScanOrder();
+    }
+
+    private int numVariables() {
+        return operands.numVariables();
+    }
+
+    private boolean isAllocatableRegister(CiValue value) {
+        return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+
+    private int[] definitions;
+    private BitSet[] blockLiveIn;
+    private LIRBlock[] opIdBlock;
+    private Object[] opIdKilledValues;
+
+
+    public BitSet liveIn(Block block) {
+        return blockLiveIn[block.blockID()];
+    }
+    private void setLiveIn(Block block, BitSet liveIn) {
+        blockLiveIn[block.blockID()] = liveIn;
+    }
+
+    private LIRBlock blockOf(int opId) {
+        return opIdBlock[opId >> 1];
+    }
+    private void setBlockOf(int opId, LIRBlock block) {
+        opIdBlock[opId >> 1] = block;
+    }
+
+    private Object killedValues(int opId) {
+        return opIdKilledValues[opId];
+    }
+    private void setKilledValues(int opId, Object killedValues) {
+        opIdKilledValues[opId] = killedValues;
+    }
+
+    public void forEachKilled(LIRInstruction op, boolean end, ValueProcedure proc) {
+        Object entry = killedValues(op.id() + (end ? 1 : 0));
+        if (entry == null) {
+            // Nothing to do
+        } else if (entry instanceof CiValue) {
+            CiValue newValue = proc.doValue((CiValue) entry);
+            assert newValue == entry : "procedure does not allow to change values";
+        } else {
+            CiValue[] values = (CiValue[]) entry;
+            for (int i = 0; i < values.length; i++) {
+                if (values[i] != null) {
+                    CiValue newValue = proc.doValue(values[i]);
+                    assert newValue == values[i] : "procedure does not allow to change values";
+                }
+            }
+        }
+    }
+
+    /**
+     * Numbers all instructions in all blocks. The numbering follows the {@linkplain ComputeLinearScanOrder linear scan order}.
+     */
+    private void numberInstructions() {
+        ValueProcedure defProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return setDef(value); } };
+
+        int numInstructions = 0;
+        for (LIRBlock block : blocks()) {
+            numInstructions += block.lir().size();
+        }
+        opIdBlock = new LIRBlock[numInstructions];
+        opIdKilledValues = new Object[numInstructions << 1];
+        definitions = new int[numVariables()];
+
+        curOpId = 0;
+        for (LIRBlock block : blocks()) {
+            block.setFirstLirInstructionId(curOpId);
+
+            if (block.phis != null) {
+                block.phis.forEachOutput(defProc);
+            }
+
+            for (LIRInstruction op : block.lir()) {
+                op.setId(curOpId);
+                setBlockOf(curOpId, block);
+
+                op.forEachTemp(defProc);
+                op.forEachOutput(defProc);
+
+                curOpId += 2; // numbering of lirOps by two
+            }
+            block.setLastLirInstructionId(curOpId - 2);
+        }
+        assert curOpId == numInstructions << 1;
+    }
+
+    private CiValue setDef(CiValue value) {
+        if (isVariable(value)) {
+            assert definitions[asVariable(value).index] == 0 : "Variable defined twice";
+            definitions[asVariable(value).index] = curOpId;
+        }
+        return value;
+    }
+
+
+    private BitSet variableLive;
+    private BitSet registerLive;
+    private int curOpId;
+
+    private void backwardDataFlow() {
+        ValueProcedure inputProc =    new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value, curOpId); } };
+        ValueProcedure aliveProc =    new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value, curOpId + 1); } };
+        ValueProcedure phiInputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value, -1); } };
+        ValueProcedure tempProc =     new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, true); } };
+        ValueProcedure outputProc =   new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, false); } };
+
+        blockLiveIn = new BitSet[blocks().size()];
+        registerLive = new BitSet();
+
+        trace(1, "==== start backward data flow analysis ====");
+        for (int i = blocks().size() - 1; i >= 0; i--) {
+            LIRBlock block = blocks().get(i);
+            trace(1, "start block %s  loop %d depth %d", block, block.loopIndex(), block.loopDepth());
+
+            variableLive = new BitSet();
+            for (LIRBlock sux : block.getLIRSuccessors()) {
+                BitSet suxLive = liveIn(sux);
+                if (suxLive != null) {
+                    trace(1, "  sux %s  suxLive: %s", sux, suxLive);
+                    variableLive.or(suxLive);
+                }
+
+                if (sux.phis != null) {
+                    curOpId = block.lastLirInstructionId();
+                    trace(1, "  phis %d  variableLive: %s", curOpId, variableLive);
+                    sux.phis.forEachInput(block, phiInputProc);
+                }
+            }
+
+            assert registerLive.isEmpty() : "no fixed register must be alive before processing a block";
+
+            for (int j = block.lir().size() - 1; j >= 0; j--) {
+                LIRInstruction op = block.lir().get(j);
+                curOpId = op.id();
+                trace(1, "  op %d %s  variableLive: %s  registerLive: %s", curOpId, op, variableLive, registerLive);
+
+                op.forEachOutput(outputProc);
+                op.forEachTemp(tempProc);
+                op.forEachState(aliveProc);
+                op.forEachAlive(aliveProc);
+                op.forEachInput(inputProc);
+            }
+
+            if (block.phis != null) {
+                curOpId = block.firstLirInstructionId();
+                trace(1, "  phis %d  variableLive: %s  registerLive: %s", curOpId, variableLive, registerLive);
+                block.phis.forEachOutput(outputProc);
+            }
+
+            if (block.numberOfPreds() == 0) {
+                curOpId = block.firstLirInstructionId();
+                trace(1, "  arguments %d  variableLive: %s  registerLive: %s", curOpId, variableLive, registerLive);
+                for (CiValue value : incomingArguments.locations) {
+                    def(value, false);
+                }
+                assert variableLive.isEmpty() : "no variables must be live at method entry";
+            }
+
+            assert registerLive.isEmpty() : "no fixed register must be alive after processing a block";
+            assert liveIn(block) == null;
+            setLiveIn(block, variableLive);
+
+            if (block.isLoopHeader()) {
+                trace(1, "  loop header, propagating live set to loop blocks  variableLive: %s", variableLive);
+                // All variables that are live at the beginning of a loop are also live the whole loop.
+                // This is guaranteed by the SSA form.
+                for (Block loop : block.loopBlocks) {
+                    BitSet loopLiveIn = liveIn(loop);
+                    assert loopLiveIn != null : "All loop blocks must have been processed before the loop header";
+                    loopLiveIn.or(variableLive);
+                    trace(3, "    block %s  loopLiveIn %s", loop, loopLiveIn);
+                }
+            }
+
+            trace(1, "end block %s  variableLive: %s", block, variableLive);
+        }
+        trace(1, "==== end backward data flow analysis ====");
+    }
+
+    private CiValue use(CiValue value, int killOpId) {
+        trace(3, "    use %s", value);
+        if (isVariable(value)) {
+            int variableIdx = asVariable(value).index;
+            assert definitions[variableIdx] < curOpId;
+            if (!variableLive.get(variableIdx)) {
+                trace(3, "      set live variable %d", variableIdx);
+                variableLive.set(variableIdx);
+                kill(value, killOpId);
+            }
+
+        } else if (isAllocatableRegister(value)) {
+            int regNum = asRegister(value).number;
+            if (!registerLive.get(regNum)) {
+                trace(3, "      set live register %d", regNum);
+                registerLive.set(regNum);
+                kill(value, killOpId);
+            }
+        }
+        return value;
+    }
+
+    private CiValue def(CiValue value, boolean isTemp) {
+        trace(3, "    def %s", value);
+        if (isVariable(value)) {
+            int variableIdx = asVariable(value).index;
+            assert definitions[variableIdx] == curOpId;
+            if (variableLive.get(variableIdx)) {
+                trace(3, "      clear live variable %d", variableIdx);
+                assert !isTemp : "temp variable cannot be used after the operation";
+                variableLive.clear(variableIdx);
+            } else {
+                // Variable has never been used, so kill it immediately after the definition.
+                kill(value, curOpId + 1);
+            }
+
+        } else if (isAllocatableRegister(value)) {
+            int regNum = asRegister(value).number;
+            if (registerLive.get(regNum)) {
+                trace(3, "      clear live register %d", regNum);
+                assert !isTemp : "temp variable cannot be used after the operation";
+                registerLive.clear(regNum);
+            } else {
+                // Register has never been used, so kill it immediately after the definition.
+                kill(value, curOpId + 1);
+            }
+        }
+        return value;
+    }
+
+    private void kill(CiValue value, int opId) {
+        if (opId < 0) {
+            return;
+        }
+        if (isVariable(value)) {
+            int defOpId = definitions[asVariable(value).index];
+            assert defOpId > 0 && defOpId <= opId;
+
+            LIRBlock defBlock = blockOf(defOpId);
+            LIRBlock useBlock = blockOf(opId);
+
+            if (useBlock.loopDepth() > 0 && useBlock.loopIndex() != defBlock.loopIndex()) {
+                // This is a value defined outside of the loop it is currently used in.  Therefore, it is live the whole loop
+                // and is not killed by the current instruction.
+                trace(3, "      no kill because use in loop %d, definition in loop %d", useBlock.loopIndex(), defBlock.loopIndex());
+                return;
+            }
+        }
+        trace(3, "      kill %s at %d", value, opId);
+
+        Object entry = killedValues(opId);
+        if (entry == null) {
+            setKilledValues(opId, value);
+        } else if (entry instanceof CiValue) {
+            setKilledValues(opId, new CiValue[] {(CiValue) entry, value});
+        } else {
+            CiValue[] killed = (CiValue[]) entry;
+            for (int i = 0; i < killed.length; i++) {
+                if (killed[i] == null) {
+                    killed[i] = value;
+                    return;
+                }
+            }
+            int oldLen = killed.length;
+            killed = Arrays.copyOf(killed, oldLen * 2);
+            setKilledValues(opId, killed);
+            killed[oldLen] = value;
+        }
+    }
+
+    private static void trace(int level, String format, Object...args) {
+        if (GraalOptions.TraceRegisterAllocationLevel >= level) {
+            TTY.println(format, args);
+        }
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/ResolveDataFlow.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/ResolveDataFlow.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,124 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.simple;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.oracle.max.graal.compiler.lir.LIRPhiMapping.PhiValueProcedure;
+import com.oracle.max.graal.compiler.util.*;
+import com.sun.cri.ci.*;
+
+public abstract class ResolveDataFlow {
+    public final LIR lir;
+    public final MoveResolver moveResolver;
+
+    public ResolveDataFlow(LIR lir, MoveResolver moveResolver) {
+        this.lir = lir;
+        this.moveResolver = moveResolver;
+    }
+
+    private LocationMap curFromLocations;
+
+    public void execute() {
+        ValueProcedure locMappingProc =    new ValueProcedure() {    @Override public CiValue doValue(CiValue value) { return locMapping(value); } };
+        PhiValueProcedure phiMappingProc = new PhiValueProcedure() { @Override public void doValue(CiValue input, CiValue output) { phiMapping(input, output); } };
+
+        trace(1, "==== start resolve data flow ====");
+        for (LIRBlock toBlock : lir.linearScanOrder()) {
+
+            for (LIRBlock fromBlock : toBlock.getLIRPredecessors()) {
+                trace(1, "start edge %s -> %s", fromBlock, toBlock);
+                findInsertPos(fromBlock, toBlock);
+
+                LocationMap toLocations = locationsForBlockBegin(toBlock);
+                curFromLocations = locationsForBlockEnd(fromBlock);
+                if (toLocations != curFromLocations) {
+                    toLocations.forEachLocation(locMappingProc);
+                }
+
+                if (toBlock.phis != null) {
+                    toBlock.phis.forEachInput(fromBlock, phiMappingProc);
+                }
+
+                moveResolver.resolve();
+                trace(1, "end edge %s -> %s", fromBlock, toBlock);
+            }
+
+            // Phi functions are resolved with moves now, so delete them.
+            toBlock.phis = null;
+        }
+        moveResolver.finish();
+        trace(1, "==== end resolve data flow ====");
+    }
+
+    private CiValue locMapping(CiValue value) {
+        Location to = curFromLocations.get(asLocation(value).variable);
+        if (value != to && to != null) {
+            moveResolver.add(value, to);
+        }
+        return value;
+    }
+
+    private void phiMapping(CiValue input, CiValue output) {
+        Location to = asLocation(output);
+        if (input != to) {
+            moveResolver.add(input, to);
+        }
+    }
+
+    private void findInsertPos(LIRBlock fromBlock, LIRBlock toBlock) {
+        assert fromBlock.getSuccessors().contains(toBlock) && toBlock.getPredecessors().contains(fromBlock);
+
+        if (fromBlock.numberOfSux() == 1) {
+            List<LIRInstruction> instructions = fromBlock.lir();
+            LIRInstruction instr = instructions.get(instructions.size() - 1);
+            assert instr instanceof LIRBranch && instr.code == StandardOpcode.JUMP : "block does not end with an unconditional jump";
+            moveResolver.init(instructions, instructions.size() - 1);
+            trace(1, "  insert at end of %s before %d", fromBlock, instructions.size() - 1);
+
+        } else if (toBlock.numberOfPreds() == 1) {
+            moveResolver.init(toBlock.lir(), 1);
+            trace(1, "  insert at beginning of %s before %d", toBlock, 1);
+
+        } else {
+            Util.shouldNotReachHere("Critical edge not split");
+        }
+    }
+
+    protected abstract LocationMap locationsForBlockBegin(LIRBlock block);
+    protected abstract LocationMap locationsForBlockEnd(LIRBlock block);
+
+
+    private static void trace(int level, String format, Object...args) {
+        if (GraalOptions.TraceRegisterAllocationLevel >= level) {
+            TTY.println(format, args);
+        }
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,472 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.simple;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.alloc.util.MoveResolver;
+import com.oracle.max.graal.alloc.util.RegisterVerifier;
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.alloc.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.oracle.max.graal.compiler.schedule.*;
+import com.oracle.max.graal.compiler.util.*;
+import com.sun.cri.ci.*;
+import com.sun.cri.ci.CiRegister.RegisterFlag;
+import com.sun.cri.ri.*;
+
+public class SpillAllAllocator {
+    private final GraalContext context;
+    private final LIR lir;
+    private final FrameMap frameMap;
+    private final OperandPool operands;
+    private final RiRegisterConfig registerConfig;
+
+    private final DataFlowAnalysis dataFlow;
+
+    private final SpillSlots spillSlots;
+
+    public SpillAllAllocator(GraalContext context, LIR lir, GraalCompilation compilation, OperandPool pool, RiRegisterConfig registerConfig) {
+        this.context = context;
+        this.lir = lir;
+        this.operands = pool;
+        this.registerConfig = registerConfig;
+        this.frameMap = compilation.frameMap();
+
+        this.spillSlots = new SpillSlots(compilation.compiler.context, frameMap);
+        this.dataFlow = new DataFlowAnalysis(context, lir, pool, registerConfig, frameMap.incomingArguments());
+        this.blockLocations = new LocationMap[lir.linearScanOrder().size()];
+        this.moveResolver = new MoveResolver(frameMap.target, spillSlots);
+    }
+
+
+    private class ResolveDataFlowImpl extends ResolveDataFlow {
+        public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver) {
+            super(lir, moveResolver);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockBegin(LIRBlock block) {
+            assert block.numberOfPreds() > 0 && block.dominator() != null;
+            return locationsFor(block.dominator());
+        }
+
+        @Override
+        protected LocationMap locationsForBlockEnd(LIRBlock block) {
+            return locationsFor(block);
+        }
+    }
+
+    private class AssignRegistersImpl extends AssignRegisters {
+        public AssignRegistersImpl(LIR lir, FrameMap frameMap) {
+            super(lir, frameMap);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockEnd(LIRBlock block) {
+            return locationsFor(block);
+        }
+    }
+
+
+    private int maxRegisterNum() {
+        return frameMap.target.arch.registers.length;
+    }
+
+    private boolean isAllocatableRegister(CiValue value) {
+        return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+
+    private final LocationMap[] blockLocations;
+
+    private LocationMap locationsFor(Block block) {
+        return blockLocations[block.blockID()];
+    }
+    private void setLocationsFor(Block block, LocationMap locations) {
+        blockLocations[block.blockID()] = locations;
+    }
+
+    private MoveResolver moveResolver;
+    private LocationMap curStackLocations;
+    private LocationMap curRegisterLocations;
+    private Object[] curInRegisterState;
+    private Object[] curOutRegisterState;
+    private BitSet curLiveIn;
+    private LIRInstruction curInstruction;
+
+    public void execute() {
+        assert LIRVerifier.verify(true, lir, frameMap.incomingArguments(), frameMap, registerConfig, operands);
+
+        dataFlow.execute();
+
+        allocate();
+
+        context.observable.fireCompilationEvent("After spill all allocation", lir);
+
+        spillSlots.finish();
+
+        ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver);
+        resolveDataFlow.execute();
+
+        context.observable.fireCompilationEvent("After resolve data flow", lir);
+
+        assert RegisterVerifier.verify(lir, frameMap.incomingArguments(), frameMap, registerConfig);
+
+        AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap);
+        assignRegisters.execute();
+
+        context.observable.fireCompilationEvent("After register asignment", lir);
+
+        assert LIRVerifier.verify(true, lir, frameMap.incomingArguments(), frameMap, registerConfig, operands);
+    }
+
+    private void allocate() {
+        ValueProcedure killNonLiveProc =  new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return killNonLive(value); } };
+        ValueProcedure killBeginProc =    new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return kill(value, false); } };
+        ValueProcedure killEndProc =      new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return kill(value, true); } };
+        ValueProcedure killLocationProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return killLocation(value); } };
+        ValueProcedure blockProc =        new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return block(value); } };
+        ValueProcedure inputProc =        new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return load(value, false); } };
+        ValueProcedure aliveProc =        new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return load(value, true); } };
+        ValueProcedure tempProc =         new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return spill(value, true); } };
+        ValueProcedure outputProc =       new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return spill(value, false); } };
+        ValueProcedure useSlotProc =      new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return useSlot(value); } };
+        ValueProcedure defSlotProc =      new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return defSlot(value); } };
+
+        trace(1, "==== start spill all allocation ====");
+        curInRegisterState = new Object[maxRegisterNum()];
+        curOutRegisterState = new Object[maxRegisterNum()];
+        curRegisterLocations = new LocationMap(operands.numVariables());
+        for (LIRBlock block : lir.linearScanOrder()) {
+            trace(1, "start block %s  loop %d depth %d", block, block.loopIndex(), block.loopDepth());
+            assert checkEmpty(curOutRegisterState);
+
+            if (block.numberOfPreds() == 0) {
+                curStackLocations = new LocationMap(operands.numVariables());
+                trace(1, "  arguments");
+                curInstruction = lir.startBlock().lir().get(0);
+                for (CiValue value : frameMap.incomingArguments().locations) {
+                    block(value);
+                }
+            } else {
+                LocationMap dominatorState = locationsFor(block.dominator());
+                curStackLocations = new LocationMap(dominatorState);
+                // Clear out all variables that are not live at the begin of this block
+                curLiveIn = dataFlow.liveIn(block);
+                curStackLocations.forEachLocation(killNonLiveProc);
+                assert checkInputState(block);
+            }
+            traceState();
+
+            if (block.phis != null) {
+                trace(1, "  phis");
+                block.phis.forEachOutput(defSlotProc);
+            }
+
+            for (int opIdx = 0; opIdx < block.lir().size(); opIdx++) {
+                LIRInstruction op = block.lir().get(opIdx);
+                curInstruction = op;
+                trace(1, "  op %d %s", op.id(), op);
+
+                assert curRegisterLocations.checkEmpty();
+
+                System.arraycopy(curOutRegisterState, 0, curInRegisterState, 0, curOutRegisterState.length);
+
+                // Block fixed registers that are defined by this instruction, so that they are no longer available for normal allocation.
+                op.forEachTemp(blockProc);
+                op.forEachOutput(blockProc);
+
+                moveResolver.init(block.lir(), opIdx);
+                // Process Alive before Input because they are more restricted and the same variable can be Alive and Input.
+                op.forEachAlive(aliveProc);
+                op.forEachInput(inputProc);
+                moveResolver.resolve();
+                op.forEachState(useSlotProc);
+
+                dataFlow.forEachKilled(op, false, killBeginProc);
+                assert !op.hasCall() || checkNoCallerSavedRegister() : "caller saved register in use accross call site";
+
+                moveResolver.init(block.lir(), opIdx + 1);
+                op.forEachTemp(tempProc);
+                op.forEachOutput(outputProc);
+                moveResolver.resolve();
+
+                dataFlow.forEachKilled(op, true, killEndProc);
+                curRegisterLocations.forEachLocation(killLocationProc);
+
+                assert curRegisterLocations.checkEmpty();
+                curInstruction = null;
+            }
+            assert checkEmpty(curOutRegisterState);
+
+            for (LIRBlock sux : block.getLIRSuccessors()) {
+                if (sux.phis != null) {
+                    trace(1, "  phis of successor %s", sux);
+                    sux.phis.forEachInput(block, useSlotProc);
+                }
+            }
+
+            assert checkEmpty(curOutRegisterState);
+            assert locationsFor(block) == null;
+            setLocationsFor(block, curStackLocations);
+
+            traceState();
+            trace(1, "end block %s", block);
+        }
+
+        moveResolver.finish();
+        trace(1, "==== end spill all allocation ====");
+    }
+
+    private CiValue killNonLive(CiValue value) {
+        assert isLocation(value);
+        if (!curLiveIn.get(asLocation(value).variable.index)) {
+            return null;
+        }
+        return value;
+    }
+
+    private CiValue kill(CiValue value, boolean end) {
+        if (isVariable(value)) {
+            trace(3, "    kill variable %s", value);
+
+            CiVariable variable = asVariable(value);
+            curStackLocations.clear(variable);
+
+            Location loc = curRegisterLocations.get(variable);
+            if (loc != null) {
+                killLocation(loc);
+                curRegisterLocations.clear(variable);
+
+                trace(3, "      location %s", loc);
+                assert isAllocatableRegister(loc.location);
+
+                int regNum = asRegister(loc.location).number;
+                if (curOutRegisterState[regNum] == loc) {
+                    curOutRegisterState[regNum] = null;
+                }
+            }
+
+        } else if (isAllocatableRegister(value)) {
+            trace(3, "    kill register %s", value);
+            int regNum = asRegister(value).number;
+            assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof LIRInstruction && curInstruction != null;
+
+            if (end || curOutRegisterState[regNum] != curInstruction) {
+                curOutRegisterState[regNum] = null;
+            }
+
+        } else {
+            throw Util.shouldNotReachHere();
+        }
+        return value;
+    }
+
+    private CiValue killLocation(CiValue value) {
+        trace(3, "    kill location %s", value);
+        assert isAllocatableRegister(asLocation(value).location);
+
+        int regNum = asRegister(asLocation(value).location).number;
+        if (curOutRegisterState[regNum] == value) {
+            curOutRegisterState[regNum] = null;
+        }
+        return null;
+    }
+
+    private CiValue block(CiValue value) {
+        if (isAllocatableRegister(value)) {
+            trace(3, "    block %s", value);
+            int regNum = asRegister(value).number;
+            assert curInstruction != null;
+            assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof LIRInstruction;
+            curOutRegisterState[regNum] = curInstruction;
+        }
+        return value;
+    }
+
+    private CiValue load(CiValue value, boolean isAlive) {
+        if (isVariable(value)) {
+            trace(3, "    load %s", value);
+            Location regLoc = curRegisterLocations.get(asVariable(value));
+            if (regLoc != null) {
+                // This variable has already been processed before.
+                trace(3, "      found location %s", regLoc);
+            } else {
+                regLoc = allocateRegister(asVariable(value), curInRegisterState, isAlive ? curOutRegisterState : null);
+                Location stackLoc = curStackLocations.get(asVariable(value));
+                assert stackLoc != null;
+                moveResolver.add(stackLoc, regLoc);
+            }
+            return regLoc;
+        } else {
+            assert !isAllocatableRegister(value) || curInRegisterState[asRegister(value).number] instanceof LIRInstruction;
+            return value;
+        }
+    }
+
+    private CiValue spill(CiValue value, boolean isTemp) {
+        if (isVariable(value)) {
+            trace(3, "    spill %s", value);
+            assert curStackLocations.get(asVariable(value)) == null;
+            Location regLoc = allocateRegister(asVariable(value), null, curOutRegisterState);
+            if (!isTemp) {
+                Location stackLoc = new Location(asVariable(value), spillSlots.allocateSpillSlot(value.kind));
+                curStackLocations.put(stackLoc);
+                moveResolver.add(regLoc, stackLoc);
+            }
+            return regLoc;
+        } else {
+            assert !isAllocatableRegister(value) || curOutRegisterState[asRegister(value).number] == curInstruction && curInstruction != null;
+            return value;
+        }
+    }
+
+    private CiValue useSlot(CiValue value) {
+        if (isVariable(value)) {
+            trace(3, "    useSlot %s", value);
+            Location stackLoc = curStackLocations.get(asVariable(value));
+            assert stackLoc != null;
+            trace(3, "      slot %s", stackLoc);
+            return stackLoc;
+        } else {
+            return value;
+        }
+    }
+
+    private CiValue defSlot(CiValue value) {
+        if (isVariable(value)) {
+            trace(3, "    assignSlot %s", value);
+            Location stackLoc = new Location(asVariable(value), spillSlots.allocateSpillSlot(value.kind));
+            assert curStackLocations.get(asVariable(value)) == null;
+            curStackLocations.put(stackLoc);
+            trace(3, "      slot %s", stackLoc);
+            return stackLoc;
+        } else {
+            return value;
+        }
+    }
+
+    private Location allocateRegister(CiVariable variable, Object[] inRegisterState, Object[] outRegisterState) {
+        EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = registerConfig.getCategorizedAllocatableRegisters();
+        CiRegister[] availableRegs;
+        if (operands.mustBeByteRegister(variable)) {
+            assert variable.kind != CiKind.Float && variable.kind != CiKind.Double : "cpu regs only";
+            availableRegs = categorizedRegs.get(RegisterFlag.Byte);
+        } else if (variable.kind == CiKind.Float || variable.kind == CiKind.Double) {
+            availableRegs = categorizedRegs.get(RegisterFlag.FPU);
+        } else {
+            availableRegs = categorizedRegs.get(RegisterFlag.CPU);
+        }
+
+        for (CiRegister reg : availableRegs) {
+            if ((inRegisterState == null || inRegisterState[reg.number] == null) && (outRegisterState == null || outRegisterState[reg.number] == null)) {
+                Location loc = new Location(variable, reg.asValue(variable.kind));
+                if (inRegisterState != null) {
+                    inRegisterState[reg.number] = loc;
+                }
+                if (outRegisterState != null) {
+                    outRegisterState[reg.number] = loc;
+                }
+                assert curRegisterLocations.get(variable) == null;
+                curRegisterLocations.put(loc);
+                trace(3, "      selected register %s", loc);
+                return loc;
+            }
+        }
+        throw new CiBailout("No register found");
+    }
+
+
+    private boolean checkInputState(final LIRBlock block) {
+        final BitSet liveState = new BitSet();
+        curStackLocations.forEachLocation(new ValueProcedure() {
+            @Override
+            public CiValue doValue(CiValue value) {
+                liveState.set(asLocation(value).variable.index);
+
+                for (Block pred : block.getPredecessors()) {
+                    LocationMap predState = locationsFor(pred);
+                    if (predState != null) {
+                        assert predState.get(asLocation(value).variable) == value;
+                    } else {
+                        assert block.isLoopHeader();
+                    }
+                }
+                return value;
+            }
+        });
+        assert liveState.equals(curLiveIn);
+        return true;
+    }
+
+//    private boolean checkBlocked(CiValue value, Object[] inRegisterState, Object[] outRegisterState) {
+//        if (isAllocatableRegister(value)) {
+//            int regNum = asRegister(value).number;
+//            assert inRegisterState == null || inRegisterState[regNum] instanceof LIRInstruction;
+//        }
+//        return !isAllocatableRegister(value) || asRegister(curRegisterState[asRegister(value).number]) == asRegister(value);
+//    }
+//
+    private boolean checkNoCallerSavedRegister() {
+        for (CiRegister reg : registerConfig.getCallerSaveRegisters()) {
+            assert curOutRegisterState[reg.number] == null || curOutRegisterState[reg.number] == curInstruction : "caller saved register in use accross call site";
+            // TODO check if that assertion holds, otherwise the code below is necessary (outside of an assertion!)
+            // curRegisterState[reg.number] = null;
+        }
+        return true;
+    }
+
+    private static boolean checkEmpty(Object[] array) {
+        for (Object o : array) {
+            assert o == null;
+        }
+        return true;
+    }
+
+
+    private void traceState() {
+        if (GraalOptions.TraceRegisterAllocationLevel >= 3) {
+            TTY.print("  curVariableLocations: ");
+            curStackLocations.forEachLocation(new ValueProcedure() {
+                @Override
+                public CiValue doValue(CiValue value) {
+                    TTY.print("%s ", value);
+                    return value;
+                }
+            });
+            TTY.println();
+        }
+    }
+
+    private static void trace(int level, String format, Object...args) {
+        if (GraalOptions.TraceRegisterAllocationLevel >= level) {
+            TTY.println(format, args);
+        }
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LIRVerifier.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LIRVerifier.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,206 @@
+/*
+ * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.util;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.compiler.alloc.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.oracle.max.graal.compiler.schedule.*;
+import com.oracle.max.graal.compiler.util.*;
+import com.sun.cri.ci.*;
+import com.sun.cri.ri.*;
+
+public final class LIRVerifier {
+    private final LIR lir;
+    private final FrameMap frameMap;
+    private final RiRegisterConfig registerConfig;
+
+    private final boolean beforeRegisterAllocation;
+
+    private final BitSet[] blockLiveOut;
+    private final Object[] variableDefinitions;
+
+    private BitSet liveOutFor(Block block) {
+        return blockLiveOut[block.blockID()];
+    }
+    private void setLiveOutFor(Block block, BitSet liveOut) {
+        blockLiveOut[block.blockID()] = liveOut;
+    }
+
+    private int maxRegisterNum() {
+        return frameMap.target.arch.registers.length;
+    }
+
+    private boolean isAllocatableRegister(CiValue value) {
+        return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+
+    public static boolean verify(boolean beforeRegisterAllocation, LIR lir, CiCallingConvention incomingArguments, FrameMap frameMap, RiRegisterConfig registerConfig, OperandPool operands) {
+        LIRVerifier verifier = new LIRVerifier(beforeRegisterAllocation, lir, frameMap, registerConfig, operands);
+        verifier.verify(incomingArguments);
+        return true;
+    }
+
+    private LIRVerifier(boolean beforeRegisterAllocation, LIR lir, FrameMap frameMap, RiRegisterConfig registerConfig, OperandPool operands) {
+        this.beforeRegisterAllocation = beforeRegisterAllocation;
+        this.lir = lir;
+        this.frameMap = frameMap;
+        this.registerConfig = registerConfig;
+        this.blockLiveOut = new BitSet[lir.linearScanOrder().size()];
+        this.variableDefinitions = new Object[operands.numVariables()];
+    }
+
+    private BitSet curVariablesLive;
+    private CiValue[] curRegistersLive;
+
+    private LIRBlock curBlock;
+    private Object curInstruction;
+
+    private void verify(CiCallingConvention incomingArguments) {
+        ValueProcedure useProc =    new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value); } };
+        ValueProcedure tempProc =   new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, true); } };
+        ValueProcedure outputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, false); } };
+
+        for (LIRBlock block : lir.linearScanOrder()) {
+            curBlock = block;
+            curVariablesLive = new BitSet();
+            curRegistersLive = new CiValue[maxRegisterNum()];
+
+            if (block.numberOfPreds() == 0) {
+                curInstruction = "Argument";
+                for (CiValue value : incomingArguments.locations) {
+                    def(value, false);
+                }
+            } else {
+                curVariablesLive.or(liveOutFor(block.dominator()));
+            }
+
+            if (beforeRegisterAllocation) {
+                if (block.phis != null) {
+                    curInstruction = block.phis;
+                    block.phis.forEachOutput(outputProc);
+                }
+            } else {
+                assert block.phis == null;
+            }
+
+            for (LIRInstruction op : block.lir()) {
+                curInstruction = op;
+
+                op.forEachInput(useProc);
+                if (op.hasCall()) {
+                    for (CiRegister register : registerConfig.getCallerSaveRegisters()) {
+                        curRegistersLive[register.number] = null;
+                    }
+                }
+                op.forEachAlive(useProc);
+                op.forEachState(useProc);
+                op.forEachTemp(tempProc);
+                op.forEachOutput(outputProc);
+
+                curInstruction = null;
+            }
+
+            setLiveOutFor(block, curVariablesLive);
+        }
+    }
+
+    private CiValue use(CiValue value) {
+        if (beforeRegisterAllocation && isVariable(value)) {
+            int variableIdx = asVariable(value).index;
+            if (!curVariablesLive.get(variableIdx)) {
+                TTY.println("block %s  instruction %s", curBlock, curInstruction);
+                TTY.println("live variables: %s", curVariablesLive);
+                if (variableDefinitions[variableIdx] != null) {
+                    TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]);
+                }
+                TTY.println("ERROR: Use of variable %s that is not defined in dominator", value);
+                throw Util.shouldNotReachHere();
+            }
+
+        } else if (beforeRegisterAllocation && isAllocatableRegister(value)) {
+            int regNum = asRegister(value).number;
+            if (curRegistersLive[regNum] != value) {
+                TTY.println("block %s  instruction %s", curBlock, curInstruction);
+                TTY.println("live registers: %s", Arrays.toString(curRegistersLive));
+                TTY.println("ERROR: Use of fixed register %s that is not defined in this block", value);
+                throw Util.shouldNotReachHere();
+            }
+        } else if (isRegister(value)) {
+            // Register usage cannot be checked.
+        } else if (isStackSlot(value)) {
+            // TODO check if stack slot is allowed for this operand.
+        } else if (isConstant(value)) {
+            // TODO check if constant is allowed for this operand.
+        } else if (value == CiValue.IllegalValue) {
+            // TODO check if illegal is allowed for this operand.
+        } else {
+            TTY.println("block %s  instruction %s", curBlock, curInstruction);
+            TTY.println("Unexpected value: %s %s", value.getClass().getSimpleName(), value);
+            throw Util.shouldNotReachHere();
+        }
+        return value;
+    }
+
+    private CiValue def(CiValue value, boolean isTemp) {
+        if (beforeRegisterAllocation && isVariable(value)) {
+            int variableIdx = asVariable(value).index;
+            if (variableDefinitions[variableIdx] != null) {
+                TTY.println("block %s  instruction %s", curBlock, curInstruction);
+                TTY.println("live variables: %s", curVariablesLive);
+                TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]);
+                TTY.println("ERROR: Variable %s defined multiple times", value);
+                throw Util.shouldNotReachHere();
+            }
+            assert curInstruction != null;
+            variableDefinitions[variableIdx] = curInstruction;
+            assert !curVariablesLive.get(variableIdx);
+            if (!isTemp) {
+                curVariablesLive.set(variableIdx);
+            }
+
+        } else if (beforeRegisterAllocation && isAllocatableRegister(value)) {
+            int regNum = asRegister(value).number;
+            if (isTemp) {
+                curRegistersLive[regNum] = null;
+            } else {
+                curRegistersLive[regNum] = value;
+            }
+        } else if (isRegister(value)) {
+            // Register definition cannot be checked.
+        } else if (isStackSlot(value)) {
+            // TODO check if stack slot is allowed for this operand.
+        } else {
+            TTY.println("block %s  instruction %s", curBlock, curInstruction);
+            TTY.println("Unexpected value: %s %s", value.getClass().getSimpleName(), value);
+            throw Util.shouldNotReachHere();
+        }
+        return value;
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/Location.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/Location.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,45 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.util;
+
+import com.sun.cri.ci.*;
+
+public class Location extends CiValue {
+    private static final long serialVersionUID = -1786677729152726126L;
+
+    public final CiVariable variable;
+    public final CiValue location;
+
+    public Location(CiVariable variable, CiValue location) {
+        super(variable.kind);
+        this.variable = variable;
+        this.location = location;
+
+        assert variable.kind == location.kind;
+    }
+
+    @Override
+    public String toString() {
+        return variable + "[" + location + "]";
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LocationMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LocationMap.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.util;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.sun.cri.ci.*;
+
+public class LocationMap {
+    private final Location[] locations;
+
+    public LocationMap(int numVariables) {
+        locations = new Location[numVariables];
+    }
+
+    public LocationMap(LocationMap template) {
+        locations = Arrays.copyOf(template.locations, template.locations.length);
+    }
+
+    public Location get(CiVariable variable) {
+        assert locations[variable.index] == null || locations[variable.index].variable == variable;
+        return locations[variable.index];
+    }
+
+    public void put(Location location) {
+        locations[location.variable.index] = location;
+    }
+
+    public void clear(CiVariable variable) {
+        locations[variable.index] = null;
+    }
+
+    public void forEachLocation(ValueProcedure proc) {
+        for (int i = 0; i < locations.length; i++) {
+            if (locations[i] != null) {
+                CiValue newValue = proc.doValue(locations[i]);
+                assert newValue == null || asLocation(newValue).variable == locations[i].variable;
+                locations[i] = (Location) newValue;
+            }
+        }
+    }
+
+    public boolean checkEmpty() {
+        for (int i = 0; i < locations.length; i++) {
+            assert locations[i] == null;
+        }
+        return true;
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/MoveResolver.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/MoveResolver.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,312 @@
+/*
+ * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.util;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.alloc.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.util.*;
+import com.sun.cri.ci.*;
+
+public final class MoveResolver {
+    private final SpillSlots spillSlots;
+    private final int[] registersBlocked;
+    private final Map<CiValue, Integer> valuesBlocked;
+    private final List<CiValue> mappingFrom;
+    private final List<Location> mappingTo;
+    private final LIRInsertionBuffer insertionBuffer;
+    private int insertPos;
+
+    public MoveResolver(CiTarget target, SpillSlots spillSlots) {
+        this.spillSlots = spillSlots;
+
+        registersBlocked = new int[target.arch.registers.length];
+        valuesBlocked = new HashMap<>();
+
+        mappingFrom = new ArrayList<>();
+        mappingTo = new ArrayList<>();
+        insertionBuffer = new LIRInsertionBuffer();
+        insertPos = -1;
+
+        assert checkEmpty();
+    }
+
+    public void init(List<LIRInstruction> newInsertList, int newInsertPos) {
+        assert checkEmpty();
+
+        if (insertionBuffer.lirList() != newInsertList) {
+            // Block changed, so append insertionBuffer because it is bound to a specific block
+            finish();
+            insertionBuffer.init(newInsertList);
+        }
+        insertPos = newInsertPos;
+
+        assert checkValid();
+    }
+
+    public void add(CiValue from, Location to) {
+        assert checkValid();
+        assert isLocation(from) || isConstant(from);
+        assert from != to;
+
+        trace(3, "mr    add mapping from %s to %s", from, to);
+        mappingFrom.add(from);
+        mappingTo.add(to);
+
+        assert checkValid();
+    }
+
+    public void resolve() {
+        assert checkValid();
+
+        if (mappingFrom.size() == 1) {
+            // If there is only one mapping, it is trivial that this mapping is safe to resolve.
+            trace(3, "mr    resolve  mappings: %d", mappingFrom.size());
+            insertMove(mappingFrom.get(0), mappingTo.get(0));
+            mappingFrom.remove(0);
+            mappingTo.remove(0);
+        } else if (mappingFrom.size() > 1) {
+            trace(3, "mr    resolve  mappings: %d", mappingFrom.size());
+            doResolve();
+        }
+        insertPos = -1;
+
+        assert checkEmpty();
+    }
+
+    public void finish() {
+        assert checkEmpty();
+
+        if (insertionBuffer.initialized()) {
+            insertionBuffer.finish();
+        }
+
+        assert !insertionBuffer.initialized() : "must be uninitialized now";
+        assert checkEmpty();
+    }
+
+
+    private void doResolve() {
+        // Block all registers and stack slots that are used as inputs of a move.
+        // When a register is blocked, no move to this register is emitted.
+        // This is necessary for detecting cycles in moves.
+        for (CiValue from : mappingFrom) {
+            block(from);
+        }
+
+        while (mappingFrom.size() > 0) {
+            boolean processed = false;
+            for (int i = mappingFrom.size() - 1; i >= 0; i--) {
+                CiValue from = mappingFrom.get(i);
+                Location to = mappingTo.get(i);
+
+                if (safeToProcessMove(from, to)) {
+                    insertMove(from, to);
+                    unblock(from);
+                    mappingFrom.remove(i);
+                    mappingTo.remove(i);
+                    processed = true;
+                }
+            }
+
+            if (!processed) {
+                // No move could be processed because there is a cycle in the move list
+                // (e.g., r1 -> r2, r2 -> r1), so one location must be spilled.
+                spill();
+            }
+        }
+    }
+
+    private void spill() {
+        Location spillCandidate = null;
+        int exchangeCandidate = -1;
+        int exchangeOther = -1;
+
+        for (int i = mappingFrom.size(); i >= 0; i--) {
+            CiValue from = mappingFrom.get(i);
+            Location to = mappingTo.get(i);
+            assert !safeToProcessMove(from, to) : "would not be in this code otherwise";
+
+            if (isConstant(from)) {
+                continue;
+            }
+            CiValue fromLoc = asLocation(from).location;
+
+            // Check if we can insert an exchange to save us from spilling.
+            if (isRegister(fromLoc) && isRegister(to) && asRegister(fromLoc) != asRegister(to) && blockedCount(to) == 1) {
+                for (int j = mappingFrom.size() - 1; j >= 0; j--) {
+                    CiValue possibleOther = mappingFrom.get(j);
+                    if (isLocation(possibleOther)) {
+                        if (asLocation(possibleOther).location == to.location) {
+                            assert exchangeCandidate == -1 : "must not find twice because of blocked check above";
+                            exchangeCandidate = i;
+                            exchangeOther = j;
+                        } else if (i != j && asLocation(possibleOther).location == fromLoc) {
+                            // From is read multiple times, so exchange would be too complicated.
+                            exchangeCandidate = -1;
+                            break;
+                        }
+                    }
+                }
+            }
+
+            if (exchangeCandidate != -1) {
+                // Already found a result, no need to search further
+                break;
+            }
+            if (spillCandidate == null || isStackSlot(spillCandidate.location)) {
+                // this interval cannot be processed now because target is not free
+                spillCandidate = asLocation(from);
+            }
+        }
+
+        if (exchangeCandidate != -1) {
+            Location from = asLocation(mappingFrom.get(exchangeCandidate));
+            Location to = mappingTo.get(exchangeCandidate);
+            Location other = asLocation(mappingFrom.get(exchangeOther));
+
+            Location newOther = new Location(other.variable, from.variable);
+            mappingFrom.set(exchangeOther, newOther);
+
+            insertExchange(newOther, to);
+            unblock(to);
+            mappingFrom.remove(exchangeCandidate);
+            mappingTo.remove(exchangeCandidate);
+
+        } else {
+            assert spillCandidate != null : "no location for spilling found";
+
+            Location spillLocation = new Location(spillCandidate.variable, spillSlots.allocateSpillSlot(spillCandidate.kind));
+            insertMove(spillCandidate, spillLocation);
+
+            for (int i = mappingFrom.size() - 1; i >= 0; i--) {
+                if (mappingFrom.get(i) == spillCandidate) {
+                    mappingFrom.set(i, spillLocation);
+                    unblock(spillCandidate);
+                    block(spillLocation);
+                }
+            }
+            assert blockedCount(spillCandidate) == 0 : "register must be unblocked after spilling";
+        }
+    }
+
+    private void block(CiValue value) {
+        if (isLocation(value)) {
+            CiValue location = asLocation(value).location;
+            if (isRegister(location)) {
+                registersBlocked[asRegister(location).number]++;
+            } else {
+                Integer count = valuesBlocked.get(location);
+                valuesBlocked.put(location, count == null ? 1 : count + 1);
+            }
+        }
+    }
+
+    private void unblock(CiValue value) {
+        if (isLocation(value)) {
+            assert blockedCount(asLocation(value)) > 0;
+            CiValue location = asLocation(value).location;
+            if (isRegister(location)) {
+                registersBlocked[asRegister(location).number]--;
+            } else {
+                Integer count = valuesBlocked.remove(location);
+                if (count > 1) {
+                    valuesBlocked.put(location, count - 1);
+                }
+            }
+        }
+    }
+
+    private int blockedCount(Location value) {
+        CiValue location = asLocation(value).location;
+        if (isRegister(location)) {
+            return registersBlocked[asRegister(location).number];
+        } else {
+            Integer count = valuesBlocked.get(location);
+            return count == null ? 0 : count;
+        }
+    }
+
+    private boolean safeToProcessMove(CiValue from, Location to) {
+        int count = blockedCount(to);
+        return count == 0 || (count == 1 && isLocation(from) && asLocation(from).location == to.location);
+    }
+
+    private void insertExchange(Location from, Location to) {
+        trace(3, "mr      XCHG %s, %s", from, to);
+        throw Util.unimplemented();
+        // TODO create XCHG instruction and use it here
+        // insertionBuffer.append(StandardOp.XCHG.create(from, to));
+    }
+
+    private void insertMove(CiValue src, Location dst) {
+        trace(3, "mr      MOV %s -> %s", src, dst);
+        insertionBuffer.append(insertPos, StandardOpcode.MOVE.create(dst,  src));
+    }
+
+
+    private boolean checkEmpty() {
+        assert insertPos == -1;
+        assert mappingFrom.size() == 0 && mappingTo.size() == 0;
+        for (int registerBlocked : registersBlocked) {
+            assert registerBlocked == 0;
+        }
+        assert valuesBlocked.size() == 0;
+        return true;
+    }
+
+    private boolean checkValid() {
+        assert insertPos != -1;
+        for (int registerBlocked : registersBlocked) {
+            assert registerBlocked == 0;
+        }
+        assert mappingFrom.size() == mappingTo.size();
+        assert insertionBuffer.initialized() && insertPos != -1;
+
+        for (int i = 0; i < mappingTo.size(); i++) {
+            CiValue from = mappingFrom.get(i);
+            Location to = mappingTo.get(i);
+
+            assert from.kind.stackKind() == to.kind;
+            assert !isLocation(from) || asLocation(from).location != to.location;
+
+            for (int j = i + 1; j < mappingTo.size(); j++) {
+                Location otherTo = mappingTo.get(j);
+                assert to != otherTo && to.variable != otherTo.variable && to.location != otherTo.location : "Cannot write to same location twice";
+            }
+        }
+        return true;
+    }
+
+
+    private static void trace(int level, String format, Object...args) {
+        if (GraalOptions.TraceRegisterAllocationLevel >= level) {
+            TTY.println(format, args);
+        }
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/RegisterVerifier.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/RegisterVerifier.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,256 @@
+/*
+ * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.util;
+
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.criutils.*;
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.lir.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
+import com.oracle.max.graal.compiler.util.*;
+import com.sun.cri.ci.*;
+import com.sun.cri.ri.*;
+
+public final class RegisterVerifier {
+    private final FrameMap frameMap;
+    private final RiRegisterConfig registerConfig;
+
+    /**
+     * All blocks that must be processed.
+     */
+    private final List<LIRBlock> workList;
+
+    /**
+     * Saved information of previous check.
+     * <br>
+     * State mapping: mapping from registers and stack slots ({@link CiRegister} and {@link Integer} stack slot offsets) to the
+     * value that is currently contained in there ({@link Location} for operands that were variables; {@link CiRegisterValue} or
+     * {@link CiStackSlot} for operands that used fixed registers or stack slots).
+     */
+    private final Map<Object, CiValue>[] blockStates;
+
+    private void addToWorkList(LIRBlock block) {
+        if (!workList.contains(block)) {
+            workList.add(block);
+        }
+    }
+
+    private Map<Object, CiValue> stateFor(LIRBlock block) {
+        return blockStates[block.blockID()];
+    }
+
+    private void setStateFor(LIRBlock block, Map<Object, CiValue> savedState) {
+        blockStates[block.blockID()] = savedState;
+    }
+
+    private static Map<Object, CiValue> copy(Map<Object, CiValue> inputState) {
+        return new HashMap<>(inputState);
+    }
+
+    public static boolean verify(LIR lir, CiCallingConvention incomingArguments, FrameMap frameMap, RiRegisterConfig registerConfig) {
+        RegisterVerifier verifier = new RegisterVerifier(lir, frameMap, registerConfig);
+        verifier.verify(lir.startBlock(), incomingArguments);
+        return true;
+    }
+
+    @SuppressWarnings("unchecked")
+    private RegisterVerifier(LIR lir, FrameMap frameMap, RiRegisterConfig registerConfig) {
+        this.frameMap = frameMap;
+        this.registerConfig = registerConfig;
+        this.workList = new LinkedList<>();
+        this.blockStates = new Map[lir.linearScanOrder().size()];
+    }
+
+    private Map<Object, CiValue> curInputState;
+
+    private void verify(LIRBlock startBlock, CiCallingConvention incomingArguments) {
+        ValueProcedure useProc =    new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value); } };
+        ValueProcedure tempProc =   new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return temp(value); } };
+        ValueProcedure outputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return output(value); } };
+
+        curInputState = new HashMap<>();
+        for (CiValue value : incomingArguments.locations) {
+            curInputState.put(key(value), value);
+        }
+        setStateFor(startBlock, curInputState);
+        addToWorkList(startBlock);
+
+        trace(1, "==== start verify register allocation ====");
+        do {
+            LIRBlock block = workList.remove(0);
+            assert block.phis == null : "phi functions must have been resolved with moves";
+
+            // Must copy state because it is modified.
+            curInputState = copy(stateFor(block));
+            trace(1, "start block %s  loop %d depth %d", block, block.loopIndex(), block.loopDepth());
+            traceState();
+
+            for (LIRInstruction op : block.lir()) {
+                trace(2, "  op %d %s", op.id(), op);
+
+                op.forEachInput(useProc);
+                if (op.hasCall()) {
+                    invalidateRegisters();
+                }
+                op.forEachAlive(useProc);
+                op.forEachState(useProc);
+                op.forEachTemp(tempProc);
+                op.forEachOutput(outputProc);
+            }
+
+            for (LIRBlock succ : block.getLIRSuccessors()) {
+                processSuccessor(succ);
+            }
+
+            trace(1, "end block %s", block);
+        } while (!workList.isEmpty());
+        trace(1, "==== end verify register allocation ====");
+    }
+
+    private void processSuccessor(LIRBlock succ) {
+        Map<Object, CiValue> savedState = stateFor(succ);
+        if (savedState == null) {
+            // Block was not processed before, so set initial inputState.
+            trace(2, "  successor %s: initial visit", succ);
+            setStateFor(succ, copy(curInputState));
+            addToWorkList(succ);
+
+        } else {
+            // This block was already processed before.
+            // Check if new inputState is consistent with savedState.
+            trace(2, "  successor %s: state present", succ);
+            Iterator<Map.Entry<Object, CiValue>> iter = savedState.entrySet().iterator();
+            while (iter.hasNext()) {
+                Map.Entry<Object, CiValue> entry = iter.next();
+                CiValue savedValue = entry.getValue();
+                CiValue inputValue = curInputState.get(entry.getKey());
+
+                if (savedValue != inputValue) {
+                    // Current inputState and previous savedState assume a different value in this register.
+                    // Assume that this register is invalid and remove it from the saved state.
+                    trace(2, "    invalididating %s because it is inconsistent with %s", savedValue, inputValue);
+                    iter.remove();
+                    // Must re-visit this block.
+                    addToWorkList(succ);
+                }
+            }
+        }
+    }
+
+    private void invalidateRegisters() {
+        // Invalidate all caller save registers at calls.
+        Iterator<Object> iter = curInputState.keySet().iterator();
+        while (iter.hasNext()) {
+            Object value1 = iter.next();
+            if (value1 instanceof CiRegister && registerConfig.getAttributesMap()[((CiRegister) value1).number].isCallerSave) {
+                trace(2, "    remove caller save register %s", value1);
+                iter.remove();
+            }
+        }
+    }
+
+    /**
+     * Gets the mapping key for a value. The key should be as narrow as possible, e.g., it should not
+     * include the kind of the value because we do not want to distinguish between the same register with
+     * different kinds.
+     */
+    private Object key(CiValue value) {
+        if (isLocation(value)) {
+            return key(asLocation(value).location);
+        } else if (isRegister(value)) {
+            return asRegister(value);
+        } else if (isStackSlot(value)) {
+            return Integer.valueOf(frameMap.offsetForStackSlot(asStackSlot(value)));
+        } else {
+            throw Util.shouldNotReachHere();
+        }
+    }
+
+    private boolean isIgnoredRegister(CiValue value) {
+        return isRegister(value) && !registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+    private CiValue use(CiValue value) {
+        if (!isConstant(value) && value != CiValue.IllegalValue && !isIgnoredRegister(value)) {
+            CiValue actual = curInputState.get(key(value));
+            if (value != actual) {
+                TTY.println("!! Error in register allocation: %s != %s for key %s", value, actual, key(value));
+                traceState();
+                throw Util.shouldNotReachHere();
+            }
+        }
+        return value;
+    }
+
+    private CiValue temp(CiValue value) {
+        trace(2, "    temp %s -> remove key %s", value, key(value));
+        curInputState.remove(key(value));
+        return value;
+    }
+
+    private CiValue output(CiValue value) {
+        trace(2, "    output %s -> set key %s", value, key(value));
+        curInputState.put(key(value), value);
+        return value;
+    }
+
+
+    private void traceState() {
+        if (GraalOptions.TraceRegisterAllocationLevel >= 2) {
+            ArrayList<Object> keys = new ArrayList<>(curInputState.keySet());
+            Collections.sort(keys, new Comparator<Object>() {
+                @Override
+                public int compare(Object o1, Object o2) {
+                    if (o1 instanceof CiRegister) {
+                        if (o2 instanceof CiRegister) {
+                            return ((CiRegister) o1).number - ((CiRegister) o2).number;
+                        } else {
+                            return -1;
+                        }
+                    } else {
+                        if (o2 instanceof CiRegister) {
+                            return 1;
+                        } else {
+                            return ((Integer) o1).intValue() - ((Integer) o2).intValue();
+                        }
+                    }
+                }
+            });
+
+            TTY.print("    state: ");
+            for (Object key : keys) {
+                TTY.print("%s=%s  ", key, curInputState.get(key));
+            }
+            TTY.println();
+        }
+    }
+
+    private static void trace(int level, String format, Object...args) {
+        if (GraalOptions.TraceRegisterAllocationLevel >= level) {
+            TTY.println(format, args);
+        }
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/SpillSlots.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/SpillSlots.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/SpillSlots.java	Wed Dec 28 18:13:25 2011 -0800
@@ -61,6 +61,7 @@
      */
     public CiStackSlot allocateSpillSlot(CiKind kind) {
         assert maxSpills >= 0 : "cannot allocate new spill slots after finish() has been called";
+        assert numberOfSpillSlots(kind) <= 2 : "larger values not supported yet";
 
         CiStackSlot spillSlot;
         if (numberOfSpillSlots(kind) == 2) {
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/ValueUtil.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/ValueUtil.java	Wed Dec 28 18:13:25 2011 -0800
@@ -0,0 +1,114 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.alloc.util;
+
+import com.sun.cri.ci.*;
+
+
+public class ValueUtil {
+
+    public static boolean isIllegal(CiValue value) {
+        assert value != null;
+        assert (value == CiValue.IllegalValue) == (value.kind == CiKind.Illegal);
+        return value == CiValue.IllegalValue;
+    }
+
+    public static boolean isVirtualObject(CiValue value) {
+        assert value != null;
+        return value instanceof CiVirtualObject;
+    }
+
+    public static boolean isLocation(CiValue value) {
+        assert value != null;
+        return value instanceof Location;
+    }
+
+    public static Location asLocation(CiValue value) {
+        assert value != null;
+        return (Location) value;
+    }
+
+
+    public static boolean isVariable(CiValue value) {
+        assert value != null;
+        return value instanceof CiVariable;
+    }
+
+    public static CiVariable asVariable(CiValue value) {
+        assert value != null;
+        return (CiVariable) value;
+    }
+
+    public static boolean isConstant(CiValue value) {
+        assert value != null;
+        return value instanceof CiConstant;
+    }
+
+    public static boolean isStackSlot(CiValue value) {
+        assert value != null;
+        return value instanceof CiStackSlot;
+    }
+
+    public static CiStackSlot asStackSlot(CiValue value) {
+        assert value != null;
+        return (CiStackSlot) value;
+    }
+
+
+
+    public static boolean isRegister(CiValue value) {
+        assert value != null;
+        return value instanceof CiRegisterValue;
+    }
+
+    public static CiRegister asRegister(CiValue value) {
+        assert value != null;
+        return ((CiRegisterValue) value).reg;
+    }
+
+
+    public static CiRegister asIntReg(CiValue value) {
+        assert value.kind == CiKind.Int || value.kind == CiKind.Jsr;
+        return asRegister(value);
+    }
+
+    public static CiRegister asLongReg(CiValue value) {
+        assert value.kind == CiKind.Long : value.kind;
+        return asRegister(value);
+    }
+
+    public static CiRegister asObjectReg(CiValue value) {
+        assert value.kind == CiKind.Object;
+        return asRegister(value);
+    }
+
+    public static CiRegister asFloatReg(CiValue value) {
+        assert value.kind == CiKind.Float;
+        return asRegister(value);
+    }
+
+    public static CiRegister asDoubleReg(CiValue value) {
+        assert value.kind == CiKind.Double;
+        return asRegister(value);
+    }
+}
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java	Wed Dec 28 18:13:25 2011 -0800
@@ -27,6 +27,7 @@
 
 import com.oracle.max.asm.*;
 import com.oracle.max.criutils.*;
+import com.oracle.max.graal.alloc.simple.*;
 import com.oracle.max.graal.compiler.alloc.*;
 import com.oracle.max.graal.compiler.asm.*;
 import com.oracle.max.graal.compiler.gen.*;
@@ -299,7 +300,7 @@
                 lir = new LIR(startBlock, linearScanOrder, codeEmittingOrder, valueToBlock);
 
                 if (context().isObserved()) {
-                    context().observable.fireCompilationEvent("After linear scan order", this, graph);
+                    context().observable.fireCompilationEvent("After linear scan order", this, graph, lir);
                 }
             } catch (AssertionError t) {
                     context().observable.fireCompilationEvent("AssertionError in ComputeLinearScanOrder", CompilationEvent.ERROR, this, graph);
@@ -334,15 +335,28 @@
                     for (LIRBlock b : lir.linearScanOrder()) {
                         lirGenerator.doBlock(b);
                     }
+
+                    for (LIRBlock b : lir.linearScanOrder()) {
+                        if (b.phis != null) {
+                            b.phis.fillInputs(lirGenerator);
+                        }
+                    }
                 } finally {
                     context().timers.endScope();
                 }
 
+                if (context().isObserved()) {
+                    context().observable.fireCompilationEvent("After LIR generation", this, graph, lir);
+                }
                 if (GraalOptions.PrintLIR && !TTY.isSuppressed()) {
                     LIR.printLIR(lir.linearScanOrder());
                 }
 
-                new LinearScan(this, lir, lirGenerator, frameMap()).allocate();
+                if (GraalOptions.AllocSSA) {
+                    new SpillAllAllocator(context(), lir, this, lirGenerator.operands, registerConfig).execute();
+                } else {
+                    new LinearScan(this, lir, lirGenerator, frameMap()).allocate();
+                }
             }
         } catch (Error e) {
             if (context().isObserved() && GraalOptions.PlotOnError) {
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Wed Dec 28 18:13:25 2011 -0800
@@ -105,6 +105,7 @@
     public static boolean PrintCodeBytes                     = ____;
     public static int     PrintAssemblyBytesPerLine          = 16;
     public static int     TraceLinearScanLevel               = 0;
+    public static int     TraceRegisterAllocationLevel       = 0;
     public static int     TraceLIRGeneratorLevel             = 0;
     public static boolean TraceRelocation                    = ____;
     public static boolean TraceLIRVisit                      = ____;
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/Interval.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/Interval.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/Interval.java	Wed Dec 28 18:13:25 2011 -0800
@@ -1113,7 +1113,7 @@
             from = String.valueOf(from());
             to = String.valueOf(to());
         }
-        String locationString = this.location == null ? "" : "@" + this.location.name();
+        String locationString = this.location == null ? "" : "@" + this.location;
         return operandNumber + ":" + operand + (operand.isRegister() ? "" : locationString) + "[" + from + "," + to + "]";
     }
 
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java	Wed Dec 28 18:13:25 2011 -0800
@@ -35,7 +35,7 @@
 import com.oracle.max.graal.compiler.alloc.Interval.SpillState;
 import com.oracle.max.graal.compiler.gen.*;
 import com.oracle.max.graal.compiler.lir.*;
-import com.oracle.max.graal.compiler.lir.LIRDebugInfo.ValueProcedure;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
 import com.oracle.max.graal.compiler.lir.LIRInstruction.OperandMode;
 import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.graph.*;
@@ -613,7 +613,7 @@
                 // Add uses of live locals from interpreter's point of view for proper debug information generation
                 LIRDebugInfo info = op.info;
                 if (info != null) {
-                    info.forEachLiveStateValue(new ValueProcedure() {
+                    info.forEachState(new ValueProcedure() {
                         @Override
                         public CiValue doValue(CiValue operand) {
                             int operandNum = operandNumber(operand);
@@ -623,7 +623,7 @@
                                     TTY.println("  Setting liveGen for LIR opId %d, operand %d because of state for %s", op.id(), operandNum, op);
                                 }
                             }
-                            return null;
+                            return operand;
                         }
                     });
                 }
@@ -824,10 +824,10 @@
                             TTY.println(ins.id() + ": " + ins.result() + " " + ins.toString());
                             LIRDebugInfo info = ins.info;
                             if (info != null) {
-                                info.forEachLiveStateValue(new ValueProcedure() {
+                                info.forEachState(new ValueProcedure() {
                                     public CiValue doValue(CiValue liveStateOperand) {
                                         TTY.println("   operand=" + liveStateOperand);
-                                        return null;
+                                        return liveStateOperand;
                                     }
                                 });
                             }
@@ -1178,10 +1178,10 @@
                 // to a call site, the value would be in a register at the call otherwise)
                 LIRDebugInfo info = op.info;
                 if (info != null) {
-                    info.forEachLiveStateValue(new ValueProcedure() {
+                    info.forEachState(new ValueProcedure() {
                         public CiValue doValue(CiValue operand) {
                             addUse(operand, blockFrom, (opId + 1), RegisterPriority.None, operand.kind.stackKind());
-                            return null;
+                            return operand;
                         }
                     });
                 }
@@ -1638,7 +1638,7 @@
         return new IntervalWalker(this, oopIntervals, nonOopIntervals);
     }
 
-    void computeOopMap(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info) {
+    void computeOopMap(IntervalWalker iw, LIRInstruction op, CiBitMap registerRefMap, CiBitMap frameRefMap) {
         if (GraalOptions.TraceLinearScanLevel >= 3) {
             TTY.println("creating oop map at opId %d", op.id());
         }
@@ -1665,7 +1665,7 @@
                 // caller-save registers must not be included into oop-maps at calls
                 assert !op.hasCall() || !operand.isRegister() || !isCallerSave(operand) : "interval is in a caller-save register at a call . register will be overwritten";
 
-                info.setReference(interval.location(), frameMap);
+                frameMap.setReference(interval.location(), registerRefMap, frameRefMap);
 
                 // Spill optimization: when the stack value is guaranteed to be always correct,
                 // then it must be added to the oop map even if the interval is currently in a register
@@ -1673,7 +1673,7 @@
                     assert interval.spillDefinitionPos() > 0 : "position not set correctly";
                     assert interval.spillSlot() != null : "no spill slot assigned";
                     assert !interval.operand.isRegister() : "interval is on stack :  so stack slot is registered twice";
-                    info.setReference(interval.spillSlot(), frameMap);
+                    frameMap.setReference(interval.spillSlot(), registerRefMap, frameRefMap);
                 }
             }
         }
@@ -1698,10 +1698,11 @@
 
 
     private void computeDebugInfo(IntervalWalker iw, final LIRInstruction op, LIRDebugInfo info) {
-        info.initDebugInfo(op, frameMap);
-        computeOopMap(iw, op, info);
+        CiBitMap registerRefMap = op.hasCall() ? null : frameMap.initRegisterRefMap();
+        CiBitMap frameRefMap = frameMap.initFrameRefMap();
+        computeOopMap(iw, op, registerRefMap, frameRefMap);
 
-        info.forEachLiveStateValue(new ValueProcedure() {
+        info.forEachState(new ValueProcedure() {
             @Override
             public CiValue doValue(CiValue operand) {
                 int tempOpId = op.id();
@@ -1730,6 +1731,8 @@
                 return result;
             }
         });
+
+        info.finish(registerRefMap, frameRefMap, frameMap);
     }
 
     private void assignLocations(List<LIRInstruction> instructions, IntervalWalker iw) {
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/CFGPrinter.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/CFGPrinter.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/CFGPrinter.java	Wed Dec 28 18:13:25 2011 -0800
@@ -231,7 +231,7 @@
         if (compilation.nodeOperands != null && node instanceof ValueNode) {
             CiValue operand = compilation.operand((ValueNode) node);
             if (operand != null) {
-                out.print("result ").print(new OperandFormatter(false).format(operand)).println(COLUMN_END);
+                out.print("result ").print(operand.toString()).println(COLUMN_END);
             }
         }
         out.print("tid ").print(nodeToString(node)).println(COLUMN_END);
@@ -239,7 +239,7 @@
         if (node instanceof StateSplit) {
             StateSplit stateSplit = (StateSplit) node;
             if (stateSplit.stateAfter() != null) {
-                String state = stateToString(stateSplit.stateAfter(), null);
+                String state = stateToString(stateSplit.stateAfter());
                 out.print("st ").print(HOVER_START).print("st").print(HOVER_SEP).print(state).print(HOVER_END).println(COLUMN_END);
             }
         }
@@ -300,7 +300,7 @@
         }
     }
 
-    private String stateToString(FrameState state, OperandFormatter operandFmt) {
+    private String stateToString(FrameState state) {
         StringBuilder buf = new StringBuilder();
         FrameState curState = state;
         do {
@@ -309,7 +309,7 @@
             if (curState.stackSize() > 0) {
                 buf.append("stack: ");
                 for (int i = 0; i < curState.stackSize(); i++) {
-                    buf.append(stateValueToString(curState.stackAt(i), operandFmt)).append(' ');
+                    buf.append(stateValueToString(curState.stackAt(i))).append(' ');
                 }
                 buf.append("\n");
             }
@@ -317,14 +317,14 @@
             if (curState.locksSize() > 0) {
                 buf.append("locks: ");
                 for (int i = 0; i < curState.locksSize(); ++i) {
-                    buf.append(stateValueToString(curState.lockAt(i), operandFmt)).append(' ');
+                    buf.append(stateValueToString(curState.lockAt(i))).append(' ');
                 }
                 buf.append("\n");
             }
 
             buf.append("locals: ");
             for (int i = 0; i < curState.localsSize(); i++) {
-                buf.append(stateValueToString(curState.localAt(i), operandFmt)).append(' ');
+                buf.append(stateValueToString(curState.localAt(i))).append(' ');
             }
             buf.append("\n");
 
@@ -334,14 +334,15 @@
         return buf.toString();
     }
 
-    private String stateValueToString(ValueNode value, OperandFormatter operandFmt) {
-        if (operandFmt == null) {
-            return nodeToString(value);
+    private String stateValueToString(ValueNode value) {
+        String result = nodeToString(value);
+        if (value != null) {
+            CiValue operand = compilation.operand(value);
+            if (operand != null) {
+                result += ": " + operand;
+            }
         }
-        if (value == null) {
-            return "-";
-        }
-        return operandFmt.format(compilation.operand(value));
+        return result;
     }
 
     /**
@@ -357,6 +358,20 @@
 
         begin("IR");
         out.println("LIR");
+
+        if (block.phis != null) {
+            CiValue[] results = block.phis.results();
+            for (int i = 0; i < results.length; i++) {
+                out.print("instruction PHI ").print(results[i].toString()).print(" = (");
+                String sep = "";
+                for (LIRBlock pred : block.getLIRPredecessors()) {
+                    out.print(sep).print(block.phis.inputs(pred)[i].toString());
+                    sep = ", ";
+                }
+                out.print(")").print(COLUMN_END).println(COLUMN_END);
+            }
+        }
+
         for (int i = 0; i < lir.size(); i++) {
             LIRInstruction inst = lir.get(i);
             out.printf("nr %4d ", inst.id()).print(COLUMN_END);
@@ -366,9 +381,9 @@
                 out.adjustIndentation(-level);
                 String state;
                 if (inst.info.hasDebugInfo()) {
-                    state = debugInfoToString(inst.info.debugInfo().codePos, inst.info.debugInfo().registerRefMap, inst.info.debugInfo().frameRefMap, new OperandFormatter(false), target.arch);
+                    state = debugInfoToString(inst.info.debugInfo().codePos, inst.info.debugInfo().registerRefMap, inst.info.debugInfo().frameRefMap, target.arch);
                 } else {
-                    state = debugInfoToString(inst.info.topFrame, null, null, new OperandFormatter(false), target.arch);
+                    state = debugInfoToString(inst.info.topFrame, null, null, target.arch);
                 }
                 if (state != null) {
                     out.print(" st ").print(HOVER_START).print("st").print(HOVER_SEP).print(state).print(HOVER_END).print(COLUMN_END);
@@ -376,7 +391,7 @@
                 out.adjustIndentation(level);
             }
 
-            out.print(" instruction ").print(inst.toString(new OperandFormatter(false))).print(COLUMN_END);
+            out.print(" instruction ").print(inst.toString()).print(COLUMN_END);
             out.println(COLUMN_END);
         }
         end("IR");
@@ -428,17 +443,17 @@
     }
 
     private void printInterval(Interval interval) {
-        out.printf("%s %s ", interval.operand.name(), (interval.operand.isRegister() ? "fixed" : interval.kind().name()));
+        out.printf("%s %s ", interval.operand, (interval.operand.isRegister() ? "fixed" : interval.kind().name()));
         if (interval.operand.isRegister()) {
-            out.printf("\"[%s|%c]\"", interval.operand.name(), interval.operand.kind.typeChar);
+            out.printf("\"[%s|%c]\"", interval.operand, interval.operand.kind.typeChar);
         } else {
             if (interval.location() != null) {
-                out.printf("\"[%s|%c]\"", interval.location().name(), interval.location().kind.typeChar);
+                out.printf("\"[%s|%c]\"", interval.location(), interval.location().kind.typeChar);
             }
         }
 
         Interval hint = interval.locationHint(false);
-        out.printf("%s %s ", interval.splitParent().operand.name(), hint != null ? hint.operand.name() : -1);
+        out.printf("%s %s ", interval.splitParent().operand, hint != null ? hint.operand : -1);
 
         // print ranges
         Range cur = interval.first();
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Dec 28 18:13:25 2011 -0800
@@ -22,6 +22,7 @@
  */
 package com.oracle.max.graal.compiler.gen;
 
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
 import static com.oracle.max.cri.intrinsics.MemoryBarriers.*;
 import static com.sun.cri.ci.CiCallingConvention.Type.*;
 import static com.sun.cri.ci.CiValue.*;
@@ -384,6 +385,8 @@
     public void visitCheckCast(CheckCastNode x) {
         XirSnippet snippet = xir.genCheckCast(site(x), toXirArgument(x.object()), toXirArgument(x.targetClassInstruction()), x.targetClass());
         emitXir(snippet, x, state(), null, true);
+        // The result of a checkcast is the unmodified object, so no need to allocate a new variable for it.
+        setResult(x, operand(x.object()));
     }
 
     @Override
@@ -780,19 +783,31 @@
         for (ValueNode arg : arguments) {
             if (arg != null) {
                 CiValue operand = cc.locations[j++];
-                if (operand.isRegister()) {
-                    emitMove(operand(arg), operand.asRegister().asValue(operand.kind.stackKind()));
-                } else {
-                    assert !((CiStackSlot) operand).inCallerFrame();
-                    CiValue param = loadForStore(operand(arg), operand.kind);
-                    emitMove(param, operand);
+                if (isRegister(operand)) {
+                    if (operand.kind.stackKind() != operand.kind) {
+                        // We only have stack-kinds in the LIR, so convert the operand kind.
+                        operand = asRegister(operand).asValue(operand.kind.stackKind());
+                    }
 
-                    if (arg.kind() == CiKind.Object && pointerSlots != null) {
+                } else if (isStackSlot(operand)) {
+                    assert !asStackSlot(operand).inCallerFrame();
+                    if (operand.kind == CiKind.Object && pointerSlots != null) {
                         // This slot must be marked explicitly in the pointer map.
-                        pointerSlots.add((CiStackSlot) operand);
+                        pointerSlots.add(asStackSlot(operand));
+                    }
+                    if (operand.kind.stackKind() != operand.kind) {
+                        // We only have stack-kinds in the LIR, so convert the operand kind.
+                        operand = CiStackSlot.get(operand.kind.stackKind(), asStackSlot(operand).index());
                     }
+                } else {
+                    throw Util.shouldNotReachHere();
                 }
+
+                emitMove(operand(arg), operand);
                 argList.add(operand);
+
+            } else {
+                throw Util.shouldNotReachHere("I thought we no longer have null entries for two-slot types...");
             }
         }
         return argList;
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/FrameMap.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/FrameMap.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/FrameMap.java	Wed Dec 28 18:13:25 2011 -0800
@@ -22,6 +22,7 @@
  */
 package com.oracle.max.graal.compiler.lir;
 
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
 import static com.sun.cri.ci.CiCallingConvention.Type.*;
 
 import com.oracle.max.graal.compiler.*;
@@ -275,9 +276,6 @@
      * Encapsulates the details of a stack block reserved by a call to {@link FrameMap#reserveStackBlock(int, boolean)}.
      */
     public static final class StackBlock extends CiValue {
-        /**
-         * 
-         */
         private static final long serialVersionUID = -5260976274149772987L;
 
         /**
@@ -300,22 +298,9 @@
         }
 
         @Override
-        public String name() {
+        public String toString() {
             return "StackBlock " + offset;
         }
-
-        @Override
-        public boolean equals(Object obj) {
-            return this == obj;
-        }
-        @Override
-        public boolean equalsIgnoringKind(CiValue other) {
-            return this == other;
-        }
-        @Override
-        public int hashCode() {
-            return offset;
-        }
     }
 
     /**
@@ -391,12 +376,39 @@
         return (outgoingSize + customAreaSize()) / target.spillSlotSize;
     }
 
+
+
+
+    private int registerRefMapSize() {
+        return target.arch.registerReferenceMapBitCount;
+    }
+
+    private int frameRefMapSize() {
+        if (incomingArguments.stackSize > 0) {
+            return (frameSize() + target.arch.returnAddressSize + customAreaSize() + incomingArguments.stackSize) / target.wordSize;
+        } else {
+            return frameSize() / target.wordSize;
+        }
+    }
+
+    private int frameRefMapIndex(CiStackSlot slot) {
+        int offset = offsetForStackSlot(slot);
+        assert offset % target.wordSize == 0 && offset / target.wordSize < frameRefMapSize();
+        return offset / target.wordSize;
+    }
+
     /**
-     * Initializes a ref map that covers all the slots in the frame.
+     * Initializes a reference map that covers all registers of the target architecture.
+     */
+    public CiBitMap initRegisterRefMap() {
+        return new CiBitMap(registerRefMapSize());
+    }
+
+    /**
+     * Initializes a reference map that covers all the slots in the frame.
      */
     public CiBitMap initFrameRefMap() {
-        int frameWords = frameSize() / target.spillSlotSize;
-        CiBitMap frameRefMap = new CiBitMap(frameWords);
+        CiBitMap frameRefMap = new CiBitMap(frameRefMapSize());
         for (StackBlock sb = stackBlocks; sb != null; sb = sb.next) {
             if (sb.kind == CiKind.Object) {
                 int firstSlot = offsetForStackBlock(sb) / target.wordSize;
@@ -408,4 +420,48 @@
         }
         return frameRefMap;
     }
+
+    /**
+     * Marks the specified location as a reference in the reference map of the debug information.
+     * The tracked location can be a {@link CiRegisterValue} or a {@link CiStackSlot}. Note that a
+     * {@link CiConstant} is automatically tracked.
+     *
+     * @param location The location to be added to the reference map.
+     * @param registerRefMap A register reference map, as created by {@link #initRegisterRefMap()}.
+     * @param frameRefMap A frame reference map, as created by {@link #initFrameRefMap()}.
+     */
+    public void setReference(CiValue location, CiBitMap registerRefMap, CiBitMap frameRefMap) {
+//        assert registerRefMap.size() == registerRefMapSize() && frameRefMap.size() == frameRefMapSize();
+        if (location.kind == CiKind.Object) {
+            if (isRegister(location)) {
+                registerRefMap.set(asRegister(location).number);
+            } else if (isStackSlot(location)) {
+                frameRefMap.set(frameRefMapIndex(asStackSlot(location)));
+            } else {
+                assert isConstant(location);
+            }
+        }
+    }
+
+    /**
+     * Clears the specified location as a reference in the reference map of the debug information.
+     * The tracked location can be a {@link CiRegisterValue} or a {@link CiStackSlot}. Note that a
+     * {@link CiConstant} is automatically tracked.
+     *
+     * @param location The location to be removed from the reference map.
+     * @param registerRefMap A register reference map, as created by {@link #initRegisterRefMap()}.
+     * @param frameRefMap A frame reference map, as created by {@link #initFrameRefMap()}.
+     */
+    public void clearReference(CiValue location, CiBitMap registerRefMap, CiBitMap frameRefMap) {
+//        assert registerRefMap.size() == registerRefMapSize() && frameRefMap.size() == frameRefMapSize();
+        if (location.kind == CiKind.Object) {
+            if (location instanceof CiRegisterValue) {
+                registerRefMap.clear(asRegister(location).number);
+            } else if (isStackSlot(location)) {
+                frameRefMap.clear(frameRefMapIndex(asStackSlot(location)));
+            } else {
+                assert isConstant(location);
+            }
+        }
+    }
 }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java	Wed Dec 28 18:13:25 2011 -0800
@@ -149,6 +149,17 @@
         return (LIRBlock) successors.get(i);
     }
 
+    @SuppressWarnings({"unchecked", "cast"})
+    public List<LIRBlock> getLIRSuccessors() {
+        return (List<LIRBlock>) (List) super.getSuccessors();
+    }
+
+    @SuppressWarnings({"unchecked", "cast"})
+    public List<LIRBlock> getLIRPredecessors() {
+        return (List<LIRBlock>) (List) super.getPredecessors();
+    }
+
+
     @Override
     public String toString() {
         return "B" + blockID();
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRCall.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRCall.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRCall.java	Wed Dec 28 18:13:25 2011 -0800
@@ -26,7 +26,6 @@
 
 import com.sun.cri.ci.*;
 import com.sun.cri.ci.CiTargetMethod.Mark;
-import com.sun.cri.ci.CiValue.Formatter;
 import com.sun.cri.ri.*;
 import com.sun.cri.xir.CiXirAssembler.XirMark;
 
@@ -92,13 +91,13 @@
     }
 
     @Override
-    public String operationString(Formatter operandFmt) {
+    public String operationString() {
         StringBuilder buf = new StringBuilder();
         if (result.isLegal()) {
-            buf.append(operandFmt.format(result)).append(" = ");
+            buf.append(result).append(" = ");
         }
         if (targetAddressIndex >= 0) {
-            buf.append(operandFmt.format(targetAddress()));
+            buf.append(targetAddress());
         }
         if (inputs.length + alives.length > 1) {
             buf.append("(");
@@ -106,13 +105,13 @@
         String sep = "";
         for (CiValue input : inputs) {
             if (input != targetAddress()) {
-                buf.append(sep).append(operandFmt.format(input));
+                buf.append(sep).append(input);
                 sep = ", ";
             }
         }
         for (CiValue input : alives) {
             if (input != targetAddress()) {
-                buf.append(sep).append(operandFmt.format(input)).append(" ~");
+                buf.append(sep).append(input).append(" ~");
                 sep = ", ";
             }
         }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRDebugInfo.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRDebugInfo.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRDebugInfo.java	Wed Dec 28 18:13:25 2011 -0800
@@ -22,14 +22,16 @@
  */
 package com.oracle.max.graal.compiler.lir;
 
+import static com.oracle.max.graal.alloc.util.ValueUtil.*;
+
 import java.util.*;
 
 import com.oracle.max.graal.compiler.lir.FrameMap.StackBlock;
-import com.oracle.max.graal.compiler.util.*;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
 import com.sun.cri.ci.*;
 
 /**
- * This class represents debugging and deoptimization information attached to a LIR instruction.
+ * This class represents garbage collection and deoptimization information attached to a LIR instruction.
  */
 public class LIRDebugInfo {
     public final CiFrame topFrame;
@@ -45,36 +47,21 @@
         this.exceptionEdge = exceptionEdge;
     }
 
-    public CiDebugInfo debugInfo() {
-        assert debugInfo != null : "debug info not allocated yet";
-        return debugInfo;
-    }
-
     public boolean hasDebugInfo() {
         return debugInfo != null;
     }
 
-
-    /**
-     * Iterator interface for iterating all variables of a frame state.
-     */
-    public interface ValueProcedure {
-        /**
-         * The iterator method.
-         *
-         * @param value The variable that is iterated.
-         * @return The new value that should replace variable, or {@code null} if the variable should remain unchanged.
-         */
-        CiValue doValue(CiValue value);
+    public CiDebugInfo debugInfo() {
+        assert debugInfo != null : "debug info not allocated yet";
+        return debugInfo;
     }
 
-
     /**
      * Iterates the frame state and calls the {@link ValueProcedure} for every variable.
      *
      * @param proc The procedure called for variables.
      */
-    public void forEachLiveStateValue(ValueProcedure proc) {
+    public void forEachState(ValueProcedure proc) {
         for (CiFrame cur = topFrame; cur != null; cur = cur.caller()) {
             processValues(cur.values, proc);
         }
@@ -90,48 +77,41 @@
             CiValue value = values[i];
             if (value instanceof CiMonitorValue) {
                 CiMonitorValue monitor = (CiMonitorValue) value;
-
-                if (monitor.owner instanceof CiVariable) {
-                    CiValue newValue = proc.doValue(monitor.owner);
-                    if (newValue != null) {
-                        values[i] = new CiMonitorValue(newValue, monitor.lockData, monitor.eliminated);
-                    }
+                if (processed(monitor.owner)) {
+                    monitor.owner = proc.doValue(monitor.owner);
                 }
 
-            } else {
-                if (value instanceof CiVariable) {
-                    CiValue newValue = proc.doValue(value);
-                    if (newValue != null) {
-                        values[i] = newValue;
-                    }
-                } else {
-                    // Nothing to do for these types.
-                    assert value == CiValue.IllegalValue || value instanceof CiConstant || value instanceof CiStackSlot || (value instanceof CiVirtualObject && Arrays.asList(virtualObjects).contains(value));
-                }
+            } else if (processed(value)) {
+                values[i] = proc.doValue(value);
             }
         }
     }
 
-    /**
-     * Create the initial {@link CiDebugInfo} object. This initializes the reference maps.
-     * This method requires the size of the stack frame to be known, i.e., this method must be called
-     * after the register allocator has allocated all spill slots and finalized the frame.
-     *
-     * @param op The instruction that contains this debug info.
-     * @param frameMap The frame map used for the compilation.
-     */
-    public void initDebugInfo(LIRInstruction op, FrameMap frameMap) {
-        CiBitMap frameRefMap = frameMap.initFrameRefMap();
-        CiBitMap regRefMap = op.hasCall() ? null : new CiBitMap(frameMap.target.arch.registerReferenceMapBitCount);
+    private boolean processed(CiValue value) {
+        if (isIllegal(value)) {
+            // Ignore dead local variables.
+            return false;
+        } else if (isConstant(value)) {
+            // Ignore constants, the register allocator does not need to see them.
+            return false;
+        } else if (isVirtualObject(value)) {
+            assert Arrays.asList(virtualObjects).contains(value);
+            return false;
+        } else {
+            return true;
+        }
+    }
 
-        debugInfo = new CiDebugInfo(topFrame, regRefMap, frameRefMap);
+
+    public void finish(CiBitMap registerRefMap, CiBitMap frameRefMap, FrameMap frameMap) {
+        debugInfo = new CiDebugInfo(topFrame, registerRefMap, frameRefMap);
 
         // Add locks that are in the designated frame area.
         for (CiFrame cur = topFrame; cur != null; cur = cur.caller()) {
             for (int i = 0; i < cur.numLocks; i++) {
-                CiMonitorValue lock = (CiMonitorValue) cur.values[i + cur.numLocals + cur.numStack];
+                CiMonitorValue lock = (CiMonitorValue) cur.getLockValue(i);
                 if (lock.lockData != null) {
-                    cur.values[i + cur.numLocals + cur.numStack] = new CiMonitorValue(lock.owner, frameMap.toStackSlot((StackBlock) lock.lockData), lock.eliminated);
+                    lock.lockData = frameMap.toStackSlot((StackBlock) lock.lockData);
                 }
             }
         }
@@ -139,41 +119,11 @@
         // Add additional stack slots for outgoing method parameters.
         if (pointerSlots != null) {
             for (CiStackSlot v : pointerSlots) {
-                setReference(v, frameMap);
+                frameMap.setReference(v, registerRefMap, frameRefMap);
             }
         }
     }
 
-    /**
-     * Marks the specified location as a reference in the reference map of the debug information.
-     * The location must be a {@link CiRegisterValue} or a {@link CiStackSlot}. Note that a {@link CiAddress}
-     * cannot be tracked by reference maps, and that a {@link CiConstant} does not have to be added
-     * manually because it is automatically tracked.
-     *
-     * @param location The stack slot or register to be added to the reference map.
-     * @param frameMap The frame map used for the compilation.
-     */
-    public void setReference(CiValue location, FrameMap frameMap) {
-        if (location instanceof CiStackSlot) {
-            CiStackSlot stackSlot = (CiStackSlot) location;
-            int offset = frameMap.offsetForStackSlot(stackSlot);
-            assert offset % frameMap.target.wordSize == 0 : "must be aligned";
-            setBit(debugInfo.frameRefMap, offset / frameMap.target.wordSize);
-
-        } else if (location instanceof CiRegisterValue) {
-            CiRegister register = ((CiRegisterValue) location).reg;
-            setBit(debugInfo.registerRefMap, register.number);
-
-        } else {
-            throw Util.shouldNotReachHere();
-        }
-    }
-
-    private static void setBit(CiBitMap refMap, int bit) {
-        assert bit >= 0 && bit < refMap.size() : "register out of range";
-        assert !refMap.get(bit) : "Ref map entry already set";
-        refMap.set(bit);
-    }
 
     @Override
     public String toString() {
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRInstruction.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRInstruction.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRInstruction.java	Wed Dec 28 18:13:25 2011 -0800
@@ -23,10 +23,8 @@
 package com.oracle.max.graal.compiler.lir;
 
 import com.oracle.max.graal.compiler.asm.*;
-import com.oracle.max.graal.compiler.lir.LIRDebugInfo.ValueProcedure;
 import com.oracle.max.graal.compiler.util.*;
 import com.sun.cri.ci.*;
-import com.sun.cri.ci.CiValue.Formatter;
 
 /**
  * The {@code LIRInstruction} class definition.
@@ -38,6 +36,20 @@
     public static final OperandMode[] OPERAND_MODES = OperandMode.values();
 
     /**
+     * Iterator interface for iterating over a list of values.
+     */
+    public interface ValueProcedure {
+        /**
+         * The iterator method.
+         *
+         * @param value The value that is iterated.
+         * @return The new value to replace the value that was passed in.
+         */
+        CiValue doValue(CiValue value);
+    }
+
+
+    /**
      * Constants denoting how a LIR instruction uses an operand.
      */
     public enum OperandMode {
@@ -209,7 +221,7 @@
     public final void setOperandAt(OperandMode mode, int index, CiValue location) {
         assert index < operandCount(mode);
         assert location.kind != CiKind.Illegal;
-        assert operandAt(mode, index).isVariable() && operandAt(mode, index).kind == location.kind;
+        assert operandAt(mode, index).kind == location.kind;
         switch (mode) {
             case Output: result = location; break;
             case Input:  inputs[index] = location; break;
@@ -219,11 +231,39 @@
         }
     }
 
-    public final void forEachOperand(OperandMode mode, ValueProcedure proc) {
-        for (int i = 0; i < operandCount(mode); i++) {
-            CiValue newValue = proc.doValue(operandAt(mode, i));
-            if (newValue != null) {
-                setOperandAt(mode, i, newValue);
+    public final void forEachInput(ValueProcedure proc) {
+        for (int i = 0; i < inputs.length; i++) {
+            inputs[i] = proc.doValue(inputs[i]);
+        }
+    }
+
+    public final void forEachAlive(ValueProcedure proc) {
+        for (int i = 0; i < alives.length; i++) {
+            alives[i] = proc.doValue(alives[i]);
+        }
+    }
+
+    public final void forEachTemp(ValueProcedure proc) {
+        for (int i = 0; i < temps.length; i++) {
+            temps[i] = proc.doValue(temps[i]);
+        }
+    }
+
+    public final void forEachOutput(ValueProcedure proc) {
+        if (result != CiValue.IllegalValue) {
+            result = proc.doValue(result);
+        }
+    }
+
+    public final void forEachState(ValueProcedure proc) {
+        if (info != null) {
+            info.forEachState(proc);
+
+            if (this instanceof LIRXirInstruction) {
+                LIRXirInstruction xir = (LIRXirInstruction) this;
+                if (xir.infoAfter != null) {
+                    xir.infoAfter.forEachState(proc);
+                }
             }
         }
     }
@@ -255,11 +295,6 @@
     }
 
 
-    @Override
-    public String toString() {
-        return toString(Formatter.DEFAULT);
-    }
-
     public final String toStringWithIdPrefix() {
         if (id != -1) {
             return String.format("%4d %s", id, toString());
@@ -270,21 +305,21 @@
     /**
      * Gets the operation performed by this instruction in terms of its operands as a string.
      */
-    public String operationString(Formatter operandFmt) {
+    public String operationString() {
         StringBuilder buf = new StringBuilder();
         if (result.isLegal()) {
-            buf.append(operandFmt.format(result)).append(" = ");
+            buf.append(result).append(" = ");
         }
         if (inputs.length + alives.length > 1) {
             buf.append("(");
         }
         String sep = "";
         for (CiValue input : inputs) {
-            buf.append(sep).append(operandFmt.format(input));
+            buf.append(sep).append(input);
             sep = ", ";
         }
         for (CiValue input : alives) {
-            buf.append(sep).append(operandFmt.format(input)).append(" ~");
+            buf.append(sep).append(input).append(" ~");
             sep = ", ";
         }
         if (inputs.length + alives.length > 1) {
@@ -296,7 +331,7 @@
         }
         sep = "";
         for (CiValue temp : temps) {
-            buf.append(sep).append(operandFmt.format(temp));
+            buf.append(sep).append(temp);
             sep = ", ";
         }
         if (temps.length > 0) {
@@ -305,7 +340,7 @@
         return buf.toString();
     }
 
-    protected static String refMapToString(CiDebugInfo debugInfo, Formatter operandFmt) {
+    protected static String refMapToString(CiDebugInfo debugInfo) {
         StringBuilder buf = new StringBuilder();
         if (debugInfo.hasStackRefMap()) {
             CiBitMap bm = debugInfo.frameRefMap;
@@ -313,7 +348,7 @@
                 if (buf.length() != 0) {
                     buf.append(", ");
                 }
-                buf.append(operandFmt.format(CiStackSlot.get(CiKind.Object, slot)));
+                buf.append(CiStackSlot.get(CiKind.Object, slot));
             }
         }
         if (debugInfo.hasRegisterRefMap()) {
@@ -328,12 +363,12 @@
         return buf.toString();
     }
 
-    protected void appendDebugInfo(StringBuilder buf, Formatter operandFmt) {
+    protected void appendDebugInfo(StringBuilder buf) {
         if (info != null) {
             buf.append(" [bci:").append(info.topFrame.bci);
             if (info.hasDebugInfo()) {
                 CiDebugInfo debugInfo = info.debugInfo();
-                String refmap = refMapToString(debugInfo, operandFmt);
+                String refmap = refMapToString(debugInfo);
                 if (refmap.length() != 0) {
                     buf.append(", refmap(").append(refmap.trim()).append(')');
                 }
@@ -342,9 +377,10 @@
         }
     }
 
-    public String toString(Formatter operandFmt) {
-        StringBuilder buf = new StringBuilder(name()).append(' ').append(operationString(operandFmt));
-        appendDebugInfo(buf, operandFmt);
+    @Override
+    public String toString() {
+        StringBuilder buf = new StringBuilder(name()).append(' ').append(operationString());
+        appendDebugInfo(buf);
         return buf.toString();
     }
 }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRPhiMapping.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRPhiMapping.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRPhiMapping.java	Wed Dec 28 18:13:25 2011 -0800
@@ -25,15 +25,16 @@
 import java.util.*;
 
 import com.oracle.max.graal.compiler.gen.*;
-import com.oracle.max.graal.compiler.lir.LIRDebugInfo.ValueProcedure;
+import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure;
 import com.oracle.max.graal.nodes.*;
+import com.oracle.max.graal.nodes.PhiNode.*;
 import com.sun.cri.ci.*;
 
 public class LIRPhiMapping {
     private final LIRBlock block;
 
-    private final CiValue[][] inputs;
-    private final CiValue[] results;
+    private CiValue[][] inputs;
+    private CiValue[] results;
 
     public LIRPhiMapping(LIRBlock block, LIRGenerator gen) {
         this.block = block;
@@ -42,23 +43,43 @@
         MergeNode mergeNode = (MergeNode) block.firstNode();
         List<PhiNode> phis = mergeNode.phis().snapshot();
 
-        int numPhis = phis.size();
+        for (int i = 0; i < phis.size(); i++) {
+            PhiNode phi = phis.get(i);
+            if (phi.type() == PhiType.Value) {
+                gen.setResult(phi, gen.newVariable(phi.kind()));
+            }
+        }
+    }
+
+    public void fillInputs(LIRGenerator gen) {
+        assert block.firstNode() instanceof MergeNode : "phi functions are only present at control flow merges";
+        MergeNode mergeNode = (MergeNode) block.firstNode();
+        List<PhiNode> phis = mergeNode.phis().snapshot();
+
+        int numPhis = 0;
+        for (int i = 0; i < phis.size(); i++) {
+            if (phis.get(i).type() == PhiType.Value) {
+                numPhis++;
+            }
+        }
         int numPreds = block.numberOfPreds();
 
         results = new CiValue[numPhis];
-        for (int i = 0; i < numPhis; i++) {
-            CiVariable opd = gen.newVariable(phis.get(i).kind());
-            gen.setResult(phis.get(i), opd);
-            results[i] = opd;
-        }
+        inputs = new CiValue[numPreds][numPhis];
 
-        inputs = new CiValue[numPreds][numPhis];
-        for (int i = 0; i < numPreds; i++) {
-            assert i == mergeNode.phiPredecessorIndex((FixedNode) block.predAt(i).lastNode()) : "block predecessors and node predecessors must have same order";
-            for (int j = 0; j < numPhis; j++) {
-                inputs[i][j] = gen.operand(phis.get(j).valueAt(i));
+        int phiIdx = 0;
+        for (int i = 0; i < phis.size(); i++) {
+            PhiNode phi = phis.get(i);
+            if (phi.type() == PhiType.Value) {
+                results[phiIdx] = gen.operand(phi);
+                for (int j = 0; j < numPreds; j++) {
+                    assert j == mergeNode.phiPredecessorIndex((FixedNode) block.predAt(j).lastNode()) : "block predecessors and node predecessors must have same order";
+                    inputs[j][phiIdx] = gen.operand(phi.valueAt(j));
+                }
+                phiIdx++;
             }
         }
+        assert phiIdx == numPhis;
     }
 
     public CiValue[] results() {
@@ -73,19 +94,29 @@
     public void forEachInput(LIRBlock pred, ValueProcedure proc) {
         CiValue[] predInputs = inputs(pred);
         for (int i = 0; i < predInputs.length; i++) {
-            CiValue newValue = proc.doValue(predInputs[i]);
-            if (newValue != null) {
-                predInputs[i] = newValue;
-            }
+            predInputs[i] = proc.doValue(predInputs[i]);
         }
     }
 
     public void forEachOutput(ValueProcedure proc) {
         for (int i = 0; i < results.length; i++) {
-            CiValue newValue = proc.doValue(results[i]);
-            if (newValue != null) {
-                results[i] = newValue;
-            }
+            results[i] = proc.doValue(results[i]);
+        }
+    }
+
+    public void forEachInput(LIRBlock pred, PhiValueProcedure proc) {
+        CiValue[] predInputs = inputs(pred);
+        for (int i = 0; i < predInputs.length; i++) {
+            proc.doValue(predInputs[i], results[i]);
         }
     }
+
+    public interface PhiValueProcedure {
+        void doValue(CiValue input, CiValue output);
+    }
+
+    @Override
+    public String toString() {
+        return "PhiMapping for " + block + ": " + Arrays.toString(results);
+    }
 }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRXirInstruction.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRXirInstruction.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRXirInstruction.java	Wed Dec 28 18:13:25 2011 -0800
@@ -25,7 +25,6 @@
 import java.util.*;
 
 import com.sun.cri.ci.*;
-import com.sun.cri.ci.CiValue.Formatter;
 import com.sun.cri.ri.*;
 import com.sun.cri.xir.*;
 
@@ -98,17 +97,17 @@
      * Prints this instruction.
      */
     @Override
-    public String operationString(Formatter operandFmt) {
-        return toString(operandFmt);
+    public String operationString() {
+        return toString();
     }
 
     @Override
-    public String toString(Formatter operandFmt) {
+    public String toString() {
         StringBuilder sb = new StringBuilder();
         sb.append("XIR: ");
 
         if (result().isLegal()) {
-            sb.append(operandFmt.format(result()) + " = ");
+            sb.append(result() + " = ");
         }
 
         sb.append(snippet.template);
@@ -119,14 +118,9 @@
                 sb.append(", ");
             }
             if (a.constant != null) {
-                sb.append(operandFmt.format(a.constant));
+                sb.append(a.constant);
             } else {
-                Object o = a.object;
-                if (o instanceof CiValue) {
-                    sb.append(operandFmt.format((CiValue) o));
-                } else {
-                    sb.append(o);
-                }
+                sb.append(a.object);
             }
         }
         sb.append(')');
@@ -147,7 +141,7 @@
                 sb.append(' ').append(mode.name().toLowerCase()).append("=(");
                 HashSet<String> operands = new HashSet<>();
                 for (int i = 0; i < n; i++) {
-                    String operand = operandFmt.format(operandAt(mode, i));
+                    String operand = operandAt(mode, i).toString();
                     if (!operands.contains(operand)) {
                         if (!operands.isEmpty()) {
                             sb.append(", ");
@@ -160,7 +154,7 @@
             }
         }
 
-        appendDebugInfo(sb, operandFmt);
+        appendDebugInfo(sb);
 
         return sb.toString();
     }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Wed Dec 28 18:13:25 2011 -0800
@@ -43,6 +43,11 @@
     private int loopIndex = -1;
     private double probability;
 
+    /**
+     * For loop headers only: The list of all blocks in this loop.
+     */
+    public List<Block> loopBlocks;
+
     private Node firstNode;
     private Node lastNode;
 
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Dec 28 18:13:25 2011 -0800
@@ -283,34 +283,36 @@
                 Block loopBeginBlock = nodeToBlock.get(loopEnd.loopBegin());
                 block.addSuccessor(loopBeginBlock);
                 BitMap map = new BitMap(blocks.size());
+                loopBeginBlock.loopBlocks = new ArrayList<>();
                 markBlocks(block, loopBeginBlock, map, loopCount++, block.loopDepth());
                 assert loopBeginBlock.loopDepth() == block.loopDepth() && loopBeginBlock.loopIndex() == block.loopIndex();
             }
         }
     }
 
-    private void markBlocks(Block block, Block endBlock, BitMap map, int loopIndex, int initialDepth) {
+    private void markBlocks(Block block, Block loopBeginBlock, BitMap map, int loopIndex, int initialDepth) {
         if (map.get(block.blockID())) {
             return;
         }
 
         map.set(block.blockID());
+        loopBeginBlock.loopBlocks.add(block);
         if (block.loopDepth() <= initialDepth) {
             assert block.loopDepth() == initialDepth;
             block.setLoopIndex(loopIndex);
         }
         block.setLoopDepth(block.loopDepth() + 1);
 
-        if (block == endBlock) {
+        if (block == loopBeginBlock) {
             return;
         }
 
         for (Block pred : block.getPredecessors()) {
-            markBlocks(pred, endBlock, map, loopIndex, initialDepth);
+            markBlocks(pred, loopBeginBlock, map, loopIndex, initialDepth);
         }
 
         if (block.isLoopHeader()) {
-            markBlocks(nodeToBlock.get(((LoopBeginNode) block.firstNode()).loopEnd()), endBlock, map, loopIndex, initialDepth);
+            markBlocks(nodeToBlock.get(((LoopBeginNode) block.firstNode()).loopEnd()), loopBeginBlock, map, loopIndex, initialDepth);
         }
     }
 
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ControlFlowOpcode.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ControlFlowOpcode.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ControlFlowOpcode.java	Wed Dec 28 18:13:25 2011 -0800
@@ -32,7 +32,6 @@
 import com.sun.cri.ci.*;
 import com.sun.cri.ci.CiAddress.Scale;
 import com.sun.cri.ci.CiTargetMethod.JumpTable;
-import com.sun.cri.ci.CiValue.Formatter;
 
 public class AMD64ControlFlowOpcode {
 
@@ -50,7 +49,7 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
+                public String operationString() {
                     return label.toString();
                 }
             };
@@ -86,7 +85,7 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
+                public String operationString() {
                     return  "[" + destination + "]";
                 }
             };
@@ -106,7 +105,7 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
+                public String operationString() {
                     return cond.operator + " [" + destination + "]";
                 }
             };
@@ -125,7 +124,7 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
+                public String operationString() {
                     return cond.operator + " [" + destination + "]" + (unorderedIsTrue ? " unorderedIsTrue" : " unorderedIsFalse");
                 }
             };
@@ -147,8 +146,8 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
-                    StringBuilder buf = new StringBuilder(super.operationString(operandFmt));
+                public String operationString() {
+                    StringBuilder buf = new StringBuilder(super.operationString());
                     buf.append("\ndefault: [").append(defaultTarget).append(']');
                     int key = lowKey;
                     for (LabelRef l : targets) {
@@ -181,8 +180,8 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
-                    return condition.toString() + " " + super.operationString(operandFmt);
+                public String operationString() {
+                    return condition.toString() + " " + super.operationString();
                 }
             };
         }
@@ -202,8 +201,8 @@
                 }
 
                 @Override
-                public String operationString(Formatter operandFmt) {
-                    return condition.toString() + " unordered=" + unorderedIsTrue + " " + super.operationString(operandFmt);
+                public String operationString() {
+                    return condition.toString() + " unordered=" + unorderedIsTrue + " " + super.operationString();
                 }
             };
         }
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64DivOpcode.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64DivOpcode.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64DivOpcode.java	Wed Dec 28 18:13:25 2011 -0800
@@ -37,7 +37,7 @@
     public LIRInstruction create(CiRegisterValue result, LIRDebugInfo info, CiRegisterValue left, CiVariable right) {
         CiValue[] inputs = new CiValue[] {left};
         CiValue[] alives = new CiValue[] {right};
-        CiValue[] temps = new CiValue[] {AMD64.rdx.asValue()};
+        CiValue[] temps = new CiValue[] {result.reg == AMD64.rax ? AMD64.rdx.asValue(result.kind) : AMD64.rax.asValue(result.kind)};
 
         return new AMD64LIRInstruction(this, result, info, inputs, alives, temps) {
             @Override
diff -r 0bc4815d2069 -r f5328dda9714 graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/HotSpotXirGenerator.java
--- a/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/HotSpotXirGenerator.java	Wed Dec 28 18:12:08 2011 -0800
+++ b/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/HotSpotXirGenerator.java	Wed Dec 28 18:13:25 2011 -0800
@@ -119,7 +119,7 @@
                 XirOperand cache = asm.createRegisterTemp("cache (rax)", target.wordKind, AMD64.rax);
 
                 CiCallingConvention conventions = registerConfig.getCallingConvention(JavaCallee, new CiKind[] {CiKind.Object}, target, false);
-                XirOperand receiver = asm.createRegisterTemp("receiver", target.wordKind, conventions.locations[0].asRegister());
+                XirOperand receiver = asm.createRegister("receiver", target.wordKind, conventions.locations[0].asRegister());
 
                 asm.pload(target.wordKind, temp, receiver, asm.i(config.hubOffset), false);
                 asm.jneq(unverifiedStub, cache, temp);
@@ -639,7 +639,7 @@
 
         @Override
         protected XirTemplate create(CiXirAssembler asm, long flags) {
-            asm.restart();
+            asm.restart(CiKind.Void);
             XirParameter object = asm.createInputParameter("object", CiKind.Object);
             final XirOperand hub;
             hub = asm.createConstantInputParameter("hub", CiKind.Object);
@@ -669,7 +669,7 @@
             asm.callRuntime(CiRuntimeCall.Deoptimize, null);
             asm.shouldNotReachHere();
 
-            return asm.finishTemplate(object, "checkcast");
+            return asm.finishTemplate("checkcast");
         }
     };