--- a/.hgignore	Wed Feb 08 21:13:35 2012 -0800
+++ b/.hgignore	Wed Feb 08 21:15:00 2012 -0800
@@ -23,8 +23,8 @@
 \.pdf$
 \.dot$
 \.pyc$
-build.xml
-nbproject
+^graal/.*/build.xml
+^graal/.*/nbproject/
 dist
 ^doc/.*/dot_temp_
 ^doc/doxygen/.*$
@@ -36,6 +36,7 @@
 /nbproject/private/
 ^graal/hotspot/java$
 ^scratch/
+^test-output/
 scratch/
 bin/
 ^local/
@@ -43,5 +44,9 @@
 ^src/share/tools/IdealGraphVisualizer/[a-zA-Z0-9]*/build/
 ^src/share/tools/IdealGraphVisualizer/build/
 ^src/share/tools/IdealGraphVisualizer/dist/
+^visualizer/[a-zA-Z0-9]*/build/
+^visualizer/build/
+^visualizer/dist/
+^visualizer/nbplatform/
 ^.hgtip
 .DS_Store

--- a/graal/com.oracle.max.asm/src/com/oracle/max/asm/AbstractAssembler.java	Wed Feb 08 21:13:35 2012 -0800
+++ b/graal/com.oracle.max.asm/src/com/oracle/max/asm/AbstractAssembler.java	Wed Feb 08 21:15:00 2012 -0800
@@ -48,6 +48,10 @@
         l.patchInstructions(this);
     }
 
+    public abstract void align(int modulus);
+
+    public abstract void jmp(Label l);
+
     protected abstract void patchJumpTarget(int branch, int jumpTarget);
 
     protected final void emitByte(int x) {

--- a/graal/com.oracle.max.asm/src/com/oracle/max/asm/NumUtil.java	Wed Feb 08 21:13:35 2012 -0800
+++ b/graal/com.oracle.max.asm/src/com/oracle/max/asm/NumUtil.java	Wed Feb 08 21:15:00 2012 -0800
@@ -98,4 +98,8 @@
         assert isShort(v);
         return (short) v;
     }
+
+    public static int roundUp(int number, int mod) {
+        return ((number + mod - 1) / mod) * mod;
+    }
 }

--- a/graal/com.oracle.max.asm/src/com/oracle/max/asm/target/amd64/AMD64Assembler.java	Wed Feb 08 21:13:35 2012 -0800
+++ b/graal/com.oracle.max.asm/src/com/oracle/max/asm/target/amd64/AMD64Assembler.java	Wed Feb 08 21:15:00 2012 -0800
@@ -759,6 +759,7 @@
         }
     }
 
+    @Override
     public final void jmp(Label l) {
         if (l.isBound()) {
             jmp(l.position(), false);
@@ -2876,6 +2877,7 @@
         testl(AMD64.rax, new CiAddress(Word, r.asValue(Word), 0));
     }
 
+    @Override
     public void align(int modulus) {
         if (codeBuffer.position() % modulus != 0) {
             nop(modulus - (codeBuffer.position() % modulus));

--- a/graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiUtil.java	Wed Feb 08 21:13:35 2012 -0800
+++ b/graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiUtil.java	Wed Feb 08 21:15:00 2012 -0800
@@ -728,11 +728,11 @@
         return result;
     }
 
-    public static Class<?>[] signatureToTypes(RiSignature signature, RiType accessingClass) {
+    public static Class<?>[] signatureToTypes(RiSignature signature, RiResolvedType accessingClass) {
         int count = signature.argumentCount(false);
         Class<?>[] result = new Class<?>[count];
         for (int i = 0; i < result.length; ++i) {
-            result[i] = ((RiResolvedType) signature.argumentTypeAt(i, accessingClass)).toJava();
+            result[i] = signature.argumentTypeAt(i, accessingClass).resolve(accessingClass).toJava();
         }
         return result;
     }

--- a/graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiSignature.java	Wed Feb 08 21:13:35 2012 -0800
+++ b/graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiSignature.java	Wed Feb 08 21:15:00 2012 -0800
@@ -49,7 +49,7 @@
      *        not care for a resolved type.
      * @return the {@code index}'th argument type
      */
-    RiType argumentTypeAt(int index, RiType accessingClass);
+    RiType argumentTypeAt(int index, RiResolvedType accessingClass);
 
     /**
      * Gets the argument kind at the specified position.

--- a/graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiType.java	Wed Feb 08 21:13:35 2012 -0800
+++ b/graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiType.java	Wed Feb 08 21:15:00 2012 -0800
@@ -97,4 +97,6 @@
      * @return the kind of constants for the specified part of the type
      */
     CiKind getRepresentationKind(Representation r);
+
+    RiResolvedType resolve(RiResolvedType accessingClass);
 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.alloc/src/com/oracle/max/graal/alloc/simple/AssignRegisters.java	Wed Feb 08 21:15:00 2012 -0800
@@ -0,0 +1,123 @@
+/*
+ * Copyright (c) 2011, 2012, 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.LocationUtil.*;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.lir.*;
+import com.oracle.max.graal.lir.LIRInstruction.*;
+import com.oracle.max.graal.lir.cfg.*;
+
+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); } };
+
+        Debug.log("==== start assign registers ====");
+        for (int i = lir.linearScanOrder().size() - 1; i >= 0; i--) {
+            Block block = lir.linearScanOrder().get(i);
+            Debug.log("start block %s", block);
+
+            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);
+                Debug.log("  op %d %s", op.id(), op);
+
+                op.forEachOutput(defProc);
+                op.forEachTemp(defProc);
+                op.forEachState(useProc);
+                op.forEachAlive(useProc);
+
+                if (op.info != null) {
+                    Debug.log("    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(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);
+            }
+            Debug.log("end block %s", block);
+        }
+        Debug.log("==== end assign registers ====");
+    }
+
+    private CiValue use(CiValue value) {
+        Debug.log("    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) {
+        Debug.log("    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) {
+        Debug.log("    setReference %s", value);
+        frameMap.setReference(asLocation(value).location, curRegisterRefMap, curFrameRefMap);
+        return value;
+    }
+
+    protected abstract LocationMap locationsForBlockEnd(Block block);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.alloc/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java	Wed Feb 08 21:15:00 2012 -0800
@@ -0,0 +1,303 @@
+/*
+ * Copyright (c) 2011, 2012, 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.cri.ci.CiValueUtil.*;
+import static com.oracle.max.graal.lir.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.lir.*;
+import com.oracle.max.graal.lir.LIRInstruction.*;
+import com.oracle.max.graal.lir.cfg.*;
+
+public class DataFlowAnalysis {
+    private final LIR lir;
+    private final RiRegisterConfig registerConfig;
+
+    public DataFlowAnalysis(LIR lir, RiRegisterConfig registerConfig) {
+        this.lir = lir;
+        this.registerConfig = registerConfig;
+    }
+
+    public void execute() {
+        numberInstructions();
+        backwardDataFlow();
+    }
+
+
+    private List<Block> blocks() {
+        return lir.linearScanOrder();
+    }
+
+    private int numVariables() {
+        return lir.numVariables();
+    }
+
+    private boolean isAllocatableRegister(CiValue value) {
+        return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+
+    private int[] definitions;
+    private BitSet[] blockLiveIn;
+    private Block[] opIdBlock;
+    private Object[] opIdKilledValues;
+
+
+    public BitSet liveIn(Block block) {
+        return blockLiveIn[block.getId()];
+    }
+    private void setLiveIn(Block block, BitSet liveIn) {
+        blockLiveIn[block.getId()] = liveIn;
+    }
+
+    private Block blockOf(int opId) {
+        return opIdBlock[opId >> 1];
+    }
+    private void setBlockOf(int opId, Block 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, null, null);
+            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], null, null);
+                    assert newValue == values[i] : "procedure does not allow to change values";
+                }
+            }
+        }
+    }
+
+    public int definition(Variable value) {
+        return definitions[value.index];
+    }
+
+    /**
+     * 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 (Block block : blocks()) {
+            numInstructions += block.lir.size();
+        }
+        opIdBlock = new Block[numInstructions];
+        opIdKilledValues = new Object[numInstructions << 1];
+        definitions = new int[numVariables()];
+
+        curOpId = 0;
+        for (Block block : blocks()) {
+            for (LIRInstruction op : block.lir) {
+                op.setId(curOpId);
+                setBlockOf(curOpId, block);
+
+                op.forEachTemp(defProc);
+                op.forEachOutput(defProc);
+
+                curOpId += 2; // numbering of lirOps by two
+            }
+        }
+        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 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();
+
+        Debug.log("==== start backward data flow analysis ====");
+        for (int i = blocks().size() - 1; i >= 0; i--) {
+            Block block = blocks().get(i);
+            Debug.log("start block %s  loop %s", block, block.getLoop());
+
+            variableLive = new BitSet();
+            for (Block sux : block.getSuccessors()) {
+                BitSet suxLive = liveIn(sux);
+                if (suxLive != null) {
+                    Debug.log("  sux %s  suxLive: %s", sux, suxLive);
+                    variableLive.or(suxLive);
+                }
+            }
+
+            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();
+                Debug.log("  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);
+            }
+
+            assert registerLive.isEmpty() : "no fixed register must be alive after processing a block";
+            assert liveIn(block) == null;
+            setLiveIn(block, variableLive);
+
+            if (block.isLoopHeader()) {
+                Debug.log("  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.getLoop().blocks) {
+                    BitSet loopLiveIn = liveIn(loop);
+                    assert loopLiveIn != null : "All loop blocks must have been processed before the loop header";
+                    loopLiveIn.or(variableLive);
+                    Debug.log("    block %s  loopLiveIn %s", loop, loopLiveIn);
+                }
+            }
+
+            Debug.log("end block %s  variableLive: %s", block, variableLive);
+        }
+        Debug.log("==== end backward data flow analysis ====");
+    }
+
+    private CiValue use(CiValue value, int killOpId) {
+        Debug.log("    use %s", value);
+        if (isVariable(value)) {
+            int variableIdx = asVariable(value).index;
+            assert definitions[variableIdx] < curOpId;
+            if (!variableLive.get(variableIdx)) {
+                Debug.log("      set live variable %d", variableIdx);
+                variableLive.set(variableIdx);
+                kill(value, killOpId);
+            }
+
+        } else if (isAllocatableRegister(value)) {
+            int regNum = asRegister(value).number;
+            if (!registerLive.get(regNum)) {
+                Debug.log("      set live register %d", regNum);
+                registerLive.set(regNum);
+                kill(value, killOpId);
+            }
+        }
+        return value;
+    }
+
+    private CiValue def(CiValue value, boolean isTemp) {
+        Debug.log("    def %s", value);
+        if (isVariable(value)) {
+            int variableIdx = asVariable(value).index;
+            assert definitions[variableIdx] == curOpId;
+            if (variableLive.get(variableIdx)) {
+                Debug.log("      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)) {
+                Debug.log("      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;
+
+            Block defBlock = blockOf(defOpId);
+            Block useBlock = blockOf(opId);
+
+            if (useBlock.getLoop() != null && useBlock.getLoop() != defBlock.getLoop()) {
+                // 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.
+                Debug.log("      no kill because use in %s, definition in %s", useBlock.getLoop(), defBlock.getLoop());
+                return;
+            }
+        }
+        Debug.log("      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;
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.alloc/src/com/oracle/max/graal/alloc/simple/LinearScanAllocator.java	Wed Feb 08 21:15:00 2012 -0800
@@ -0,0 +1,573 @@
+/*
+ * Copyright (c) 2011, 2012, 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.cri.ci.CiValueUtil.*;
+import static com.oracle.max.graal.alloc.util.LocationUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ci.CiRegister.RegisterFlag;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.lir.*;
+import com.oracle.max.graal.lir.LIRInstruction.*;
+import com.oracle.max.graal.lir.cfg.*;
+
+public class LinearScanAllocator {
+    private final LIR lir;
+    private final FrameMap frameMap;
+
+    private final DataFlowAnalysis dataFlow;
+
+    public LinearScanAllocator(LIR lir, FrameMap frameMap) {
+        this.lir = lir;
+        this.frameMap = frameMap;
+
+        this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig);
+        this.blockBeginLocations = new LocationMap[lir.linearScanOrder().size()];
+        this.blockEndLocations = new LocationMap[lir.linearScanOrder().size()];
+        this.moveResolver = new MoveResolverImpl(lir, frameMap);
+
+        this.variableLastUse = new int[lir.numVariables()];
+    }
+
+    private class MoveResolverImpl extends MoveResolver {
+        public MoveResolverImpl(LIR lir, FrameMap frameMap) {
+            super(lir, frameMap);
+        }
+
+        @Override
+        protected CiValue scratchRegister(Variable spilled) {
+            GraalInternalError.shouldNotReachHere("needs working implementation");
+
+            EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters();
+            CiRegister[] availableRegs = categorizedRegs.get(spilled.flag);
+            for (CiRegister reg : availableRegs) {
+                if (curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null) {
+                    return reg.asValue(spilled.kind);
+                }
+            }
+            throw new CiBailout("No register found");
+        }
+    }
+
+    private class ResolveDataFlowImpl extends ResolveDataFlow {
+        public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) {
+            super(lir, moveResolver, dataFlow);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockBegin(Block block) {
+            return beginLocationsFor(block);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockEnd(Block block) {
+            return endLocationsFor(block);
+        }
+    }
+
+    private class AssignRegistersImpl extends AssignRegisters {
+        public AssignRegistersImpl(LIR lir, FrameMap frameMap) {
+            super(lir, frameMap);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockEnd(Block block) {
+            return endLocationsFor(block);
+        }
+    }
+
+
+    private int maxRegisterNum() {
+        return frameMap.target.arch.registers.length;
+    }
+
+    private boolean isAllocatableRegister(CiValue value) {
+        return isRegister(value) && frameMap.registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+
+    private final LocationMap[] blockBeginLocations;
+
+    private LocationMap beginLocationsFor(Block block) {
+        return blockBeginLocations[block.getId()];
+    }
+    private void setBeginLocationsFor(Block block, LocationMap locations) {
+        blockBeginLocations[block.getId()] = locations;
+    }
+
+    private final LocationMap[] blockEndLocations;
+
+    private LocationMap endLocationsFor(Block block) {
+        return blockEndLocations[block.getId()];
+    }
+    private void setEndLocationsFor(Block block, LocationMap locations) {
+        blockEndLocations[block.getId()] = locations;
+    }
+
+    private final int[] variableLastUse;
+
+    private int lastUseFor(Variable variable) {
+        return variableLastUse[variable.index];
+    }
+
+    private void setLastUseFor(Variable variable, int lastUse) {
+        variableLastUse[variable.index] = lastUse;
+    }
+
+    private MoveResolver moveResolver;
+    private LocationMap curLocations;
+    private CiValue[] curInRegisterState;
+    private CiValue[] curOutRegisterState;
+    private BitSet curLiveIn;
+    private int curOpId;
+    private boolean curPhiDefs;
+
+    private LocationMap canonicalSpillLocations;
+
+    public void execute() {
+        assert LIRVerifier.verify(true, lir, frameMap);
+
+        dataFlow.execute();
+        IntervalPrinter.printBeforeAllocation("Before register allocation", lir, frameMap.registerConfig, dataFlow);
+
+        allocate();
+
+        IntervalPrinter.printAfterAllocation("After linear scan allocation", lir, frameMap.registerConfig, dataFlow, blockEndLocations);
+
+        ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow);
+        resolveDataFlow.execute();
+        frameMap.finish();
+
+        IntervalPrinter.printAfterAllocation("After resolve data flow", lir, frameMap.registerConfig, dataFlow, blockEndLocations);
+        assert RegisterVerifier.verify(lir, frameMap);
+
+        AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap);
+        assignRegisters.execute();
+
+        Debug.dump(lir, "After register asignment");
+        assert LIRVerifier.verify(false, lir, frameMap);
+    }
+
+    private void allocate() {
+        ValueProcedure recordUseProc =    new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return recordUse(value); } };
+        ValueProcedure killNonLiveProc =  new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return killNonLive(value); } };
+        ValueProcedure unblockProc =      new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return unblock(value); } };
+        ValueProcedure killProc =         new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return kill(value); } };
+        ValueProcedure blockProc =        new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return block(value); } };
+        ValueProcedure useProc =          new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return use(value, mode, flags); } };
+        ValueProcedure defProc =          new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return def(value, mode, flags); } };
+
+        Debug.log("==== start linear scan allocation ====");
+        canonicalSpillLocations = new LocationMap(lir.numVariables());
+        curInRegisterState = new CiValue[maxRegisterNum()];
+        curOutRegisterState = new CiValue[maxRegisterNum()];
+        for (Block block : lir.linearScanOrder()) {
+            Debug.log("start block %s %s", block, block.getLoop());
+
+            Arrays.fill(curOutRegisterState, null);
+            if (block.getDominator() != null) {
+                LocationMap dominatorState = endLocationsFor(block.getDominator());
+                curLocations = new LocationMap(dominatorState);
+                // Clear out all variables that are not live at the begin of this block
+                curLiveIn = dataFlow.liveIn(block);
+                curLocations.forEachLocation(killNonLiveProc);
+                assert checkInputState(block);
+            } else {
+                curLocations = new LocationMap(lir.numVariables());
+            }
+            Debug.log(logCurrentState());
+
+            for (int opIdx = 0; opIdx < block.lir.size(); opIdx++) {
+                LIRInstruction op = block.lir.get(opIdx);
+                curOpId = op.id();
+                curPhiDefs = opIdx == 0;
+
+                Debug.log("  op %d %s", op.id(), op);
+
+                System.arraycopy(curOutRegisterState, 0, curInRegisterState, 0, curOutRegisterState.length);
+
+                // Unblock fixed registers that are only used for inputs in curOutRegisterState.
+                dataFlow.forEachKilled(op, false, unblockProc);
+                // Block fixed registers defined by this instruction in curOutRegisterState.
+                op.forEachTemp(blockProc);
+                op.forEachOutput(blockProc);
+
+                op.forEachInput(recordUseProc);
+                op.forEachAlive(recordUseProc);
+
+                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(useProc);
+                op.forEachInput(useProc);
+
+                dataFlow.forEachKilled(op, false, killProc);
+
+                if (op.hasCall()) {
+                    spillCallerSaveRegisters();
+                }
+
+                op.forEachTemp(defProc);
+                op.forEachOutput(defProc);
+
+                // Fixed temp and output registers can evict variables from their assigned register, allocate new location for them.
+                fixupEvicted();
+                // State values are the least critical and can get the leftover registers (or stack slots if no more register available).
+                op.forEachState(useProc);
+
+                if (opIdx == 0) {
+                    assert !moveResolver.hasMappings() : "cannot insert spill moves before label";
+                    setBeginLocationsFor(block, new LocationMap(curLocations));
+                }
+                moveResolver.resolve();
+
+                dataFlow.forEachKilled(op, true, unblockProc);
+                dataFlow.forEachKilled(op, true, killProc);
+
+                curOpId = -1;
+            }
+
+            assert endLocationsFor(block) == null;
+            setEndLocationsFor(block, curLocations);
+
+            logCurrentState();
+            Debug.log("end block %s", block);
+        }
+
+        moveResolver.finish();
+        Debug.log("==== end linear scan allocation ====");
+    }
+
+    private CiValue killNonLive(CiValue value) {
+        assert isLocation(value);
+        if (!curLiveIn.get(asLocation(value).variable.index)) {
+            return null;
+
+        } else if (isAllocatableRegister(asLocation(value).location)) {
+            int regNum = asRegister(asLocation(value).location).number;
+            assert curOutRegisterState[regNum] == null;
+            curOutRegisterState[regNum] = value;
+        }
+        return value;
+    }
+
+    private CiValue unblock(CiValue value) {
+        if (isAllocatableRegister(value)) {
+            Debug.log("    unblock register %s", value);
+            int regNum = asRegister(value).number;
+            assert curOutRegisterState[regNum] == value;
+            curOutRegisterState[regNum] = null;
+        }
+        return value;
+    }
+
+    private CiValue kill(CiValue value) {
+        if (isVariable(value)) {
+            Location location = curLocations.get(asVariable(value));
+            Debug.log("    kill location %s", location);
+            if (isRegister(location.location)) {
+                int regNum = asRegister(location.location).number;
+                if (curOutRegisterState[regNum] == location) {
+                    curOutRegisterState[regNum] = null;
+                }
+            }
+            curLocations.clear(asVariable(value));
+        }
+        return value;
+    }
+
+
+    private CiValue block(CiValue value) {
+        if (isAllocatableRegister(value)) {
+            Debug.log("    block %s", value);
+            int regNum = asRegister(value).number;
+            assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof Location;
+            curOutRegisterState[regNum] = value;
+        }
+        return value;
+    }
+
+    private void spillCallerSaveRegisters() {
+        Debug.log("    spill caller save registers in curInRegisterState %s", Arrays.toString(curInRegisterState));
+        for (CiRegister reg : frameMap.registerConfig.getCallerSaveRegisters()) {
+            CiValue in = curInRegisterState[reg.number];
+            if (in != null && isLocation(in)) {
+                spill(asLocation(in));
+            }
+        }
+    }
+
+    private CiValue recordUse(CiValue value) {
+        if (isVariable(value)) {
+            assert lastUseFor(asVariable(value)) <= curOpId;
+            setLastUseFor(asVariable(value), curOpId);
+
+        }
+        return value;
+    }
+
+    private CiValue use(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) {
+        assert mode == OperandMode.Input || mode == OperandMode.Alive;
+        if (isVariable(value)) {
+            // State values are not recorded beforehand because it does not matter if they are spilled. Still, it is necessary to record them as used now.
+            recordUse(value);
+
+            Location curLoc = curLocations.get(asVariable(value));
+            if (isStackSlot(curLoc.location) && flags.contains(OperandFlag.Stack)) {
+                Debug.log("    use %s %s: use current stack slot %s", mode, value, curLoc.location);
+                return curLoc;
+            }
+            if (isRegister(curLoc.location)) {
+                int regNum = asRegister(curLoc.location).number;
+                assert curInRegisterState[regNum] == curLoc;
+                if (mode == OperandMode.Input || curOutRegisterState[regNum] == curLoc) {
+                    Debug.log("    use %s %s: use current register %s", mode, value, curLoc.location);
+                    return curLoc;
+                }
+            }
+
+            Debug.log("    use %s %s", mode, value);
+
+            Location newLoc = allocateRegister(asVariable(value), mode, flags);
+            if (newLoc != curLoc) {
+                moveResolver.add(curLoc, newLoc);
+            }
+            return newLoc;
+        } else {
+            assert !isAllocatableRegister(value) || curInRegisterState[asRegister(value).number] == value;
+        }
+        return value;
+    }
+
+    private static final EnumSet<OperandFlag> SPILL_FLAGS = EnumSet.of(OperandFlag.Register, OperandFlag.Stack);
+
+    private CiValue def(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) {
+        assert mode == OperandMode.Temp || mode == OperandMode.Output;
+        if (isVariable(value)) {
+            Debug.log("    def %s %s", mode, value);
+            assert curLocations.get(asVariable(value)) == null;
+
+            Location newLoc = allocateRegister(asVariable(value), mode, flags);
+            return newLoc;
+        }
+        return value;
+    }
+
+
+    private void fixupEvicted() {
+        for (int i = 0; i < curInRegisterState.length; i++) {
+            CiValue in = curInRegisterState[i];
+            CiValue out = curOutRegisterState[i];
+
+            if (in != null && in != out && isLocation(in) && curLocations.get(asLocation(in).variable) == in) {
+                Debug.log("    %s was evicted by %s, need to allocate new location", in, out);
+                Location oldLoc = asLocation(in);
+                Location newLoc = allocateRegister(oldLoc.variable, OperandMode.Alive, SPILL_FLAGS);
+                assert oldLoc != newLoc;
+                moveResolver.add(oldLoc, newLoc);
+            }
+
+
+        }
+    }
+
+
+    private Location allocateRegister(final Variable variable, OperandMode mode, EnumSet<OperandFlag> flags) {
+//        if (flags.contains(OperandFlag.RegisterHint)) {
+//            CiValue result = curInstruction.forEachRegisterHint(variable, mode, new ValueProcedure() {
+//                @Override
+//                public CiValue doValue(CiValue registerHint) {
+//                    Debug.log("      registerHint %s", registerHint);
+//                    CiRegister hint = null;
+//                    if (isRegister(registerHint)) {
+//                        hint = asRegister(registerHint);
+//                    } else if (isLocation(registerHint) && isRegister(asLocation(registerHint).location)) {
+//                        hint = asRegister(asLocation(registerHint).location);
+//                    }
+//                    if (hint != null && hint.isSet(variable.flag) && isFree(hint, inRegisterState, outRegisterState)) {
+//                        return selectRegister(hint, variable, inRegisterState, outRegisterState);
+//                    }
+//                    return null;
+//                }
+//            });
+//
+//            if (result != null) {
+//                return asLocation(result);
+//            }
+//        }
+//
+        EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters();
+        CiRegister[] availableRegs = categorizedRegs.get(variable.flag);
+
+        Location bestSpillCandidate = null;
+        for (CiRegister reg : availableRegs) {
+            if (isFree(reg, mode)) {
+                return selectRegister(reg, variable, mode);
+            } else {
+                Location spillCandidate = spillCandidate(reg);
+                if (betterSpillCandidate(spillCandidate, bestSpillCandidate)) {
+                    bestSpillCandidate = spillCandidate;
+                }
+            }
+        }
+
+        if (flags.contains(OperandFlag.Stack) && betterSpillCandidate(curLocations.get(variable), bestSpillCandidate)) {
+            return selectSpillSlot(variable);
+        }
+
+        if (bestSpillCandidate == null) {
+            if (curPhiDefs) {
+                return selectSpillSlot(variable);
+            }
+
+            // This should not happen as long as all LIR instructions have fulfillable register constraints. But be safe in product mode and bail out.
+            assert false;
+            throw new CiBailout("No register available");
+        }
+
+        spill(bestSpillCandidate);
+
+        return selectRegister(asRegister(bestSpillCandidate.location), variable, mode);
+    }
+
+    private void spill(Location value) {
+        Location newLoc = spillLocation(value.variable);
+        Debug.log("      spill %s to %s", value, newLoc);
+        if (!curPhiDefs) {
+            moveResolver.add(value, newLoc);
+        }
+        curLocations.put(newLoc);
+
+        CiRegister reg = asRegister(value.location);
+        assert curInRegisterState[reg.number] == value;
+        curInRegisterState[reg.number] = null;
+        if (curOutRegisterState[reg.number] == value) {
+            curOutRegisterState[reg.number] = null;
+        }
+    }
+
+    private boolean isFree(CiRegister reg, OperandMode mode) {
+        switch (mode) {
+            case Input:  return curInRegisterState[reg.number] == null;
+            case Alive:  return curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null;
+            case Temp:   return curOutRegisterState[reg.number] == null;
+            case Output: return curOutRegisterState[reg.number] == null;
+            default:     throw GraalInternalError.shouldNotReachHere();
+        }
+    }
+
+    private Location spillCandidate(CiRegister reg) {
+        CiValue in = curInRegisterState[reg.number];
+        CiValue out = curOutRegisterState[reg.number];
+        if (in == out && in != null && isLocation(in) && lastUseFor(asLocation(in).variable) < curOpId) {
+            return asLocation(in);
+        }
+        return null;
+    }
+
+    private boolean betterSpillCandidate(Location loc, Location compare) {
+        if (loc == null) {
+            return false;
+        }
+        if (compare == null) {
+            return true;
+        }
+        if (canonicalSpillLocations.get(loc.variable) != null && canonicalSpillLocations.get(compare.variable) == null) {
+            return true;
+        }
+        return dataFlow.definition(loc.variable) < dataFlow.definition(compare.variable);
+    }
+
+    private Location spillLocation(Variable variable) {
+        Location result = canonicalSpillLocations.get(variable);
+        if (result == null) {
+            result = new Location(variable, frameMap.allocateSpillSlot(variable.kind));
+            canonicalSpillLocations.put(result);
+        }
+        return result;
+    }
+
+    private Location selectRegister(CiRegister reg, Variable variable, OperandMode mode) {
+        assert isFree(reg, mode);
+
+        Location loc = new Location(variable, reg.asValue(variable.kind));
+        if (mode == OperandMode.Input || mode == OperandMode.Alive) {
+            curInRegisterState[reg.number] = loc;
+        }
+        curOutRegisterState[reg.number] = loc;
+        curLocations.put(loc);
+        recordUse(variable);
+
+        Debug.log("      selected register %s", loc);
+        return loc;
+    }
+
+    private Location selectSpillSlot(Variable variable) {
+        Location loc = spillLocation(variable);
+        curLocations.put(loc);
+        recordUse(variable);
+
+        Debug.log("      selected spill slot %s", loc);
+        return loc;
+    }
+
+    private boolean checkInputState(final Block block) {
+        final BitSet liveState = new BitSet();
+        curLocations.forEachLocation(new ValueProcedure() {
+            @Override
+            public CiValue doValue(CiValue value) {
+                liveState.set(asLocation(value).variable.index);
+
+                for (Block pred : block.getPredecessors()) {
+                    LocationMap predState = endLocationsFor(pred);
+                    if (predState != null) {
+                        assert predState.get(asLocation(value).variable) != null;
+                    } else {
+                        assert block.isLoopHeader();
+                    }
+                }
+                return value;
+            }
+        });
+        assert liveState.equals(curLiveIn);
+        return true;
+    }
+
+
+    private String logCurrentState() {
+        final StringBuilder sb = new StringBuilder();
+        sb.append("  current lcoations: ");
+        curLocations.forEachLocation(new ValueProcedure() {
+            @Override
+            public CiValue doValue(CiValue value) {
+                sb.append(value).append(" ");
+                return value;
+            }
+        });
+        return sb.toString();
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.alloc/src/com/oracle/max/graal/alloc/simple/ResolveDataFlow.java	Wed Feb 08 21:15:00 2012 -0800
@@ -0,0 +1,129 @@
+/*
+ * Copyright (c) 2011, 2012, 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.LocationUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.lir.*;
+import com.oracle.max.graal.lir.LIRInstruction.*;
+import com.oracle.max.graal.lir.StandardOp.*;
+import com.oracle.max.graal.lir.cfg.*;
+
+public abstract class ResolveDataFlow {
+    public final LIR lir;
+    public final MoveResolver moveResolver;
+    public final DataFlowAnalysis dataFlow;
+
+    public ResolveDataFlow(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) {
+        this.lir = lir;
+        this.moveResolver = moveResolver;
+        this.dataFlow = dataFlow;
+    }
+
+    private LocationMap curFromLocations;
+
+    public void execute() {
+        ValueProcedure locMappingProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return locMapping(value); } };
+
+        Debug.log("==== start resolve data flow ====");
+        for (Block toBlock : lir.linearScanOrder()) {
+            PhiLabelOp phiDefs = null;
+            if (toBlock.lir.get(0) instanceof PhiLabelOp) {
+                phiDefs = (PhiLabelOp) toBlock.lir.get(0);
+            }
+
+            for (Block fromBlock : toBlock.getPredecessors()) {
+                Debug.log("start edge %s -> %s", fromBlock, toBlock);
+                findInsertPos(fromBlock, toBlock);
+
+                LocationMap toLocations = locationsForBlockBegin(toBlock);
+                curFromLocations = locationsForBlockEnd(fromBlock);
+                if (toLocations != curFromLocations) {
+                    toLocations.forEachLocation(locMappingProc);
+                }
+
+                if (phiDefs != null) {
+                    PhiJumpOp phiInputs = (PhiJumpOp) fromBlock.lir.get(fromBlock.lir.size() - 1);
+                    phiMapping(phiInputs.getPhiInputs(), phiDefs.getPhiDefinitions());
+                    phiInputs.markResolved();
+                }
+
+                moveResolver.resolve();
+                Debug.log("end edge %s -> %s", fromBlock, toBlock);
+            }
+
+            if (phiDefs != null) {
+                // Phi functions are resolved with moves now, so delete them.
+                phiDefs.markResolved();
+            }
+        }
+        moveResolver.finish();
+        Debug.log("==== end resolve data flow ====");
+    }
+
+    private CiValue locMapping(CiValue value) {
+        Location to = asLocation(value);
+        Location from = curFromLocations.get(to.variable);
+        if (value != from && from != null) {
+            moveResolver.add(from, to);
+        }
+        return value;
+    }
+
+    private void phiMapping(CiValue[] inputs, CiValue[] outputs) {
+        assert inputs.length == outputs.length;
+        for (int i = 0; i < inputs.length; i++) {
+            if (inputs[i] != outputs[i]) {
+                moveResolver.add(inputs[i], asLocation(outputs[i]));
+            }
+        }
+    }
+
+    private void findInsertPos(Block fromBlock, Block 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 StandardOp.JumpOp : "block does not end with an unconditional jump";
+            moveResolver.init(instructions, instructions.size() - 1);
+            Debug.log("  insert at end of %s before %d", fromBlock, instructions.size() - 1);
+
+        } else if (toBlock.numberOfPreds() == 1) {
+            moveResolver.init(toBlock.lir, 1);
+            Debug.log("  insert at beginning of %s before %d", toBlock, 1);
+
+        } else {
+            GraalInternalError.shouldNotReachHere("Critical edge not split");
+        }
+    }
+
+    protected abstract LocationMap locationsForBlockBegin(Block block);
+    protected abstract LocationMap locationsForBlockEnd(Block block);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.alloc/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java	Wed Feb 08 21:15:00 2012 -0800
@@ -0,0 +1,466 @@
+/*
+ * Copyright (c) 2011, 2012, 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.cri.ci.CiValueUtil.*;
+import static com.oracle.max.graal.alloc.util.LocationUtil.*;
+
+import java.util.*;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ci.CiRegister.RegisterFlag;
+import com.oracle.max.graal.alloc.util.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.lir.*;
+import com.oracle.max.graal.lir.LIRInstruction.*;
+import com.oracle.max.graal.lir.cfg.*;
+
+public class SpillAllAllocator {
+    private final LIR lir;
+    private final FrameMap frameMap;
+
+    private final DataFlowAnalysis dataFlow;
+
+    public SpillAllAllocator(LIR lir, FrameMap frameMap) {
+        this.lir = lir;
+        this.frameMap = frameMap;
+
+        this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig);
+        this.blockLocations = new LocationMap[lir.linearScanOrder().size()];
+        this.moveResolver = new MoveResolverImpl(lir, frameMap);
+    }
+
+    private class MoveResolverImpl extends MoveResolver {
+        public MoveResolverImpl(LIR lir, FrameMap frameMap) {
+            super(lir, frameMap);
+        }
+
+        @Override
+        protected CiValue scratchRegister(Variable spilled) {
+            EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters();
+            CiRegister[] availableRegs = categorizedRegs.get(spilled.flag);
+            for (CiRegister reg : availableRegs) {
+                if (curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null) {
+                    return reg.asValue(spilled.kind);
+                }
+            }
+            throw new CiBailout("No register found");
+        }
+    }
+
+    private class ResolveDataFlowImpl extends ResolveDataFlow {
+        public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) {
+            super(lir, moveResolver, dataFlow);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockBegin(Block block) {
+            assert block.numberOfPreds() > 0 && block.getDominator() != null;
+            return locationsFor(block.getDominator());
+        }
+
+        @Override
+        protected LocationMap locationsForBlockEnd(Block block) {
+            return locationsFor(block);
+        }
+    }
+
+    private class AssignRegistersImpl extends AssignRegisters {
+        public AssignRegistersImpl(LIR lir, FrameMap frameMap) {
+            super(lir, frameMap);
+        }
+
+        @Override
+        protected LocationMap locationsForBlockEnd(Block block) {
+            return locationsFor(block);
+        }
+    }
+
+
+    private int maxRegisterNum() {
+        return frameMap.target.arch.registers.length;
+    }
+
+    private boolean isAllocatableRegister(CiValue value) {
+        return isRegister(value) && frameMap.registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
+    }
+
+
+    private final LocationMap[] blockLocations;
+
+    private LocationMap locationsFor(Block block) {
+        return blockLocations[block.getId()];
+    }
+    private void setLocationsFor(Block block, LocationMap locations) {
+        blockLocations[block.getId()] = 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);
+
+        dataFlow.execute();
+        IntervalPrinter.printBeforeAllocation("Before register allocation", lir, frameMap.registerConfig, dataFlow);
+
+        allocate();
+
+        IntervalPrinter.printAfterAllocation("After spill all allocation", lir, frameMap.registerConfig, dataFlow, blockLocations);
+
+        ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow);
+        resolveDataFlow.execute();
+        frameMap.finish();
+
+        IntervalPrinter.printAfterAllocation("After resolve data flow", lir, frameMap.registerConfig, dataFlow, blockLocations);
+        assert RegisterVerifier.verify(lir, frameMap);
+
+        AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap);
+        assignRegisters.execute();
+
+        Debug.dump(lir, "After register asignment");
+        assert LIRVerifier.verify(false, lir, frameMap);
+    }
+
+    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 loadProc =         new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return load(value, mode, flags); } };
+        ValueProcedure spillProc =        new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return spill(value, mode, flags); } };
+        ValueProcedure useSlotProc =      new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return useSlot(value); } };
+
+        Debug.log("==== start spill all allocation ====");
+        curInRegisterState = new Object[maxRegisterNum()];
+        curOutRegisterState = new Object[maxRegisterNum()];
+        curRegisterLocations = new LocationMap(lir.numVariables());
+        for (Block block : lir.linearScanOrder()) {
+            Debug.log("start block %s %s", block, block.getLoop());
+            assert checkEmpty(curOutRegisterState);
+
+            if (block.getDominator() != null) {
+                LocationMap dominatorState = locationsFor(block.getDominator());
+                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);
+            } else {
+                curStackLocations = new LocationMap(lir.numVariables());
+            }
+            Debug.log(logCurrentState());
+
+            for (int opIdx = 0; opIdx < block.lir.size(); opIdx++) {
+                LIRInstruction op = block.lir.get(opIdx);
+                curInstruction = op;
+                Debug.log("  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(loadProc);
+                op.forEachInput(loadProc);
+                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(spillProc);
+                op.forEachOutput(spillProc);
+                moveResolver.resolve();
+
+                dataFlow.forEachKilled(op, true, killEndProc);
+                curRegisterLocations.forEachLocation(killLocationProc);
+
+                assert curRegisterLocations.checkEmpty();
+                curInstruction = null;
+            }
+            assert checkEmpty(curOutRegisterState);
+            assert locationsFor(block) == null;
+            setLocationsFor(block, curStackLocations);
+
+            logCurrentState();
+            Debug.log("end block %s", block);
+        }
+
+        moveResolver.finish();
+        Debug.log("==== 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)) {
+            Debug.log("    kill variable %s", value);
+
+            Variable variable = asVariable(value);
+            curStackLocations.clear(variable);
+
+            Location loc = curRegisterLocations.get(variable);
+            if (loc != null) {
+                killLocation(loc);
+                curRegisterLocations.clear(variable);
+
+                Debug.log("      location %s", loc);
+                assert isAllocatableRegister(loc.location);
+
+                int regNum = asRegister(loc.location).number;
+                if (curOutRegisterState[regNum] == loc) {
+                    curOutRegisterState[regNum] = null;
+                }
+            }
+
+        } else if (isAllocatableRegister(value)) {
+            Debug.log("    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 GraalInternalError.shouldNotReachHere();
+        }
+        return value;
+    }
+
+    private CiValue killLocation(CiValue value) {
+        Debug.log("    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)) {
+            Debug.log("    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, OperandMode mode, EnumSet<OperandFlag> flags) {
+        assert mode == OperandMode.Input || mode == OperandMode.Alive;
+        if (flags.contains(OperandFlag.Stack)) {
+            return useSlot(value);
+        }
+        if (isVariable(value)) {
+            Debug.log("    load %s", value);
+            Location regLoc = curRegisterLocations.get(asVariable(value));
+            if (regLoc != null) {
+                // This variable has already been processed before.
+                Debug.log("      found location %s", regLoc);
+            } else {
+                regLoc = allocateRegister(asVariable(value), curInRegisterState, mode == OperandMode.Alive ? curOutRegisterState : null, mode, flags);
+                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, OperandMode mode, EnumSet<OperandFlag> flags) {
+        assert mode == OperandMode.Temp || mode == OperandMode.Output;
+        if (flags.contains(OperandFlag.Stack)) {
+            return defSlot(value);
+        }
+        if (isVariable(value)) {
+            Debug.log("    spill %s", value);
+            assert curStackLocations.get(asVariable(value)) == null;
+            Location regLoc = allocateRegister(asVariable(value), null, curOutRegisterState, mode, flags);
+            if (mode == OperandMode.Output) {
+                Location stackLoc = new Location(asVariable(value), frameMap.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)) {
+            Debug.log("    useSlot %s", value);
+            Location stackLoc = curStackLocations.get(asVariable(value));
+            assert stackLoc != null;
+            Debug.log("      slot %s", stackLoc);
+            return stackLoc;
+        } else {
+            return value;
+        }
+    }
+
+    private CiValue defSlot(CiValue value) {
+        if (isVariable(value)) {
+            Debug.log("    assignSlot %s", value);
+            Location stackLoc = new Location(asVariable(value), frameMap.allocateSpillSlot(value.kind));
+            assert curStackLocations.get(asVariable(value)) == null;
+            curStackLocations.put(stackLoc);
+            Debug.log("      slot %s", stackLoc);
+            return stackLoc;
+        } else {
+            return value;
+        }
+    }
+
+    private Location allocateRegister(final Variable variable, final Object[] inRegisterState, final Object[] outRegisterState, OperandMode mode, EnumSet<OperandFlag> flags) {
+        if (flags.contains(OperandFlag.RegisterHint)) {
+            CiValue result = curInstruction.forEachRegisterHint(variable, mode, new ValueProcedure() {
+                @Override
+                public CiValue doValue(CiValue registerHint) {
+                    Debug.log("      registerHint %s", registerHint);
+                    CiRegister hint = null;
+                    if (isRegister(registerHint)) {
+                        hint = asRegister(registerHint);
+                    } else if (isLocation(registerHint) && isRegister(asLocation(registerHint).location)) {
+                        hint = asRegister(asLocation(registerHint).location);
+                    }
+                    if (hint != null && hint.isSet(variable.flag) && isFree(hint, inRegisterState, outRegisterState)) {
+                        return selectRegister(hint, variable, inRegisterState, outRegisterState);
+                    }
+                    return null;
+                }
+            });
+
+            if (result != null) {
+                return asLocation(result);
+            }
+        }
+
+        EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters();
+        CiRegister[] availableRegs = categorizedRegs.get(variable.flag);
+
+        for (CiRegister reg : availableRegs) {
+            if (isFree(reg, inRegisterState, outRegisterState)) {
+                return selectRegister(reg, variable, inRegisterState, outRegisterState);
+            }
+
+        }
+        throw new CiBailout("No register found");
+    }
+
+    private static boolean isFree(CiRegister reg, Object[] inRegisterState, Object[] outRegisterState) {
+        return (inRegisterState == null || inRegisterState[reg.number] == null) && (outRegisterState == null || outRegisterState[reg.number] == null);
+    }
+
+    private Location selectRegister(CiRegister reg, Variable variable, Object[] inRegisterState, Object[] outRegisterState) {
+        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);
+        Debug.log("      selected register %s", loc);
+        return loc;
+    }
+
+    private boolean checkInputState(final Block 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 checkNoCallerSavedRegister() {
+        for (CiRegister reg : frameMap.registerConfig.getCallerSaveRegisters()) {
+            assert curOutRegisterState[reg.number] == null || curOutRegisterState[reg.number] == curInstruction : "caller saved register in use accross call site";
+        }
+        return true;
+    }
+
+    private static boolean checkEmpty(Object[] array) {
+        for (Object o : array) {
+            assert o == null;
+        }
+        return true;
+    }
+
+
+    private String logCurrentState() {
+        final StringBuilder sb = new StringBuilder();
+        sb.append("  curVariableLocations: ");
+        curStackLocations.forEachLocation(new ValueProcedure() {
+            @Override
+            public CiValue doValue(CiValue value) {
+                sb.append(value).append(" ");
+                return value;
+            }
+        });
+        return sb.toString();
+    }
+}