Mercurial > hg > truffle

changeset 19679:87d5316e171b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge
author Stefan Anzinger <stefan.anzinger@oracle.com>
date Tue, 03 Mar 2015 13:19:35 +0100
parents 96ab2078eeaf (current diff) 9669f6a5624b (diff)
children d01c26301c28
files graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotLIRFrameState.java
diffstat 26 files changed, 412 insertions(+), 246 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/BytecodeFrame.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/BytecodeFrame.java	Tue Mar 03 13:19:35 2015 +0100
@@ -66,7 +66,7 @@
      * Note that the number of locals and the number of stack slots may be smaller than the maximum
      * number of locals and stack slots as specified in the compiled method.
      */
-    public final JavaValue[] values;
+    public final Value[] values;
 
     /**
      * The number of locals in the values array.
@@ -144,7 +144,7 @@
      * @param numStack the depth of the stack
      * @param numLocks the number of locked objects
      */
-    public BytecodeFrame(BytecodeFrame caller, ResolvedJavaMethod method, int bci, boolean rethrowException, boolean duringCall, JavaValue[] values, int numLocals, int numStack, int numLocks) {
+    public BytecodeFrame(BytecodeFrame caller, ResolvedJavaMethod method, int bci, boolean rethrowException, boolean duringCall, Value[] values, int numLocals, int numStack, int numLocks) {
         super(caller, method, bci);
         assert values != null;
         this.rethrowException = rethrowException;
@@ -183,7 +183,7 @@
      * @param i the local variable index
      * @return the value that can be used to reconstruct the local's current value
      */
-    public JavaValue getLocalValue(int i) {
+    public Value getLocalValue(int i) {
         return values[i];
     }
 
@@ -193,7 +193,7 @@
      * @param i the stack index
      * @return the value that can be used to reconstruct the stack slot's current value
      */
-    public JavaValue getStackValue(int i) {
+    public Value getStackValue(int i) {
         return values[i + numLocals];
     }
 
@@ -203,7 +203,7 @@
      * @param i the lock index
      * @return the value that can be used to reconstruct the lock's current value
      */
-    public JavaValue getLockValue(int i) {
+    public Value getLockValue(int i) {
         return values[i + numLocals + numStack];
     }
 
--- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/StackLockValue.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/StackLockValue.java	Tue Mar 03 13:19:35 2015 +0100
@@ -33,22 +33,22 @@
 
     private static final long serialVersionUID = 8241681800464483691L;
 
-    private JavaValue owner;
+    private Value owner;
     private StackSlotValue slot;
     private final boolean eliminated;
 
-    public StackLockValue(JavaValue owner, StackSlotValue slot, boolean eliminated) {
+    public StackLockValue(Value object, StackSlotValue slot, boolean eliminated) {
         super(LIRKind.Illegal);
-        this.owner = owner;
+        this.owner = object;
         this.slot = slot;
         this.eliminated = eliminated;
     }
 
-    public JavaValue getOwner() {
+    public Value getOwner() {
         return owner;
     }
 
-    public void setOwner(JavaValue newOwner) {
+    public void setOwner(Value newOwner) {
         this.owner = newOwner;
     }
 
--- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualObject.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualObject.java	Tue Mar 03 13:19:35 2015 +0100
@@ -36,7 +36,7 @@
     private static final long serialVersionUID = -2907197776426346021L;
 
     private final ResolvedJavaType type;
-    private JavaValue[] values;
+    private Value[] values;
     private final int id;
 
     /**
@@ -54,18 +54,18 @@
      *            position in the compiled code.
      * @return a new {@link VirtualObject} instance.
      */
-    public static VirtualObject get(ResolvedJavaType type, JavaValue[] values, int id) {
+    public static VirtualObject get(ResolvedJavaType type, Value[] values, int id) {
         return new VirtualObject(type, values, id);
     }
 
-    private VirtualObject(ResolvedJavaType type, JavaValue[] values, int id) {
+    private VirtualObject(ResolvedJavaType type, Value[] values, int id) {
         super(LIRKind.reference(Kind.Object));
         this.type = type;
         this.values = values;
         this.id = id;
     }
 
-    private static StringBuilder appendValue(StringBuilder buf, JavaValue value, Set<VirtualObject> visited) {
+    private static StringBuilder appendValue(StringBuilder buf, Value value, Set<VirtualObject> visited) {
         if (value instanceof VirtualObject) {
             VirtualObject vo = (VirtualObject) value;
             buf.append("vobject:").append(vo.type.toJavaName(false)).append(':').append(vo.id);
@@ -120,7 +120,7 @@
     /**
      * Returns an array containing all the values to be stored into the object when it is recreated.
      */
-    public JavaValue[] getValues() {
+    public Value[] getValues() {
         return values;
     }
 
@@ -132,7 +132,7 @@
         return id;
     }
 
-    private static boolean checkValues(ResolvedJavaType type, JavaValue[] values) {
+    private static boolean checkValues(ResolvedJavaType type, Value[] values) {
         if (values != null) {
             if (!type.isArray()) {
                 ResolvedJavaField[] fields = type.getInstanceFields(true);
@@ -140,8 +140,8 @@
                 for (int i = 0; i < values.length; i++) {
                     ResolvedJavaField field = fields[fieldIndex++];
                     Kind valKind = values[i].getKind().getStackKind();
-                    if (field.getKind() == Kind.Object && values[i] instanceof Value) {
-                        assert ((Value) values[i]).getLIRKind().isReference(0) : field + ": " + valKind + " != " + field.getKind();
+                    if (field.getKind() == Kind.Object) {
+                        assert values[i].getLIRKind().isReference(0) : field + ": " + valKind + " != " + field.getKind();
                     } else {
                         if ((valKind == Kind.Double || valKind == Kind.Long) && field.getKind() == Kind.Int) {
                             assert fields[fieldIndex].getKind() == Kind.Int;
@@ -156,9 +156,7 @@
                 Kind componentKind = type.getComponentType().getKind().getStackKind();
                 if (componentKind == Kind.Object) {
                     for (int i = 0; i < values.length; i++) {
-                        if (values[i] instanceof Value) {
-                            assert ((Value) values[i]).getLIRKind().isReference(0) : values[i].getKind() + " != " + componentKind;
-                        }
+                        assert values[i].getLIRKind().isReference(0) : values[i].getKind() + " != " + componentKind;
                     }
                 } else {
                     for (int i = 0; i < values.length; i++) {
@@ -177,7 +175,7 @@
      * @param values an array containing all the values to be stored into the object when it is
      *            recreated.
      */
-    public void setValues(JavaValue[] values) {
+    public void setValues(Value[] values) {
         assert checkValues(type, values);
         this.values = values;
     }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java	Tue Mar 03 13:19:35 2015 +0100
@@ -34,6 +34,8 @@
 
     private T dominator;
     private List<T> dominated;
+    private int domNumber;
+    private int maxChildDomNumber;
 
     private boolean align;
     private int linearScanNumber;
@@ -43,6 +45,19 @@
         this.linearScanNumber = -1;
     }
 
+    public void setDominatorNumbers(int domNumber, int maxChildDomNumber) {
+        this.domNumber = domNumber;
+        this.maxChildDomNumber = maxChildDomNumber;
+    }
+
+    public int getDominatorNumber() {
+        return domNumber;
+    }
+
+    public int getMaxChildDominatorNumber() {
+        return this.maxChildDomNumber;
+    }
+
     public int getId() {
         return id;
     }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Tue Mar 03 13:19:35 2015 +0100
@@ -46,6 +46,7 @@
     /**
      * Computes the dominators of control flow graph.
      */
+    @SuppressWarnings("unchecked")
     static <T extends AbstractBlockBase<T>> void computeDominators(AbstractControlFlowGraph<T> cfg) {
         List<T> reversePostOrder = cfg.getBlocks();
         assert reversePostOrder.get(0).getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
@@ -55,7 +56,7 @@
             T dominator = null;
             for (T pred : block.getPredecessors()) {
                 if (!pred.isLoopEnd()) {
-                    dominator = commonDominatorTyped(dominator, pred);
+                    dominator = (T) ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
                 }
             }
             // set dominator
@@ -65,21 +66,26 @@
             }
             dominator.getDominated().add(block);
         }
+        calcDominatorRanges(cfg.getStartBlock(), 0);
+    }
+
+    static <T extends AbstractBlockBase<T>> int calcDominatorRanges(T block, int next) {
+        int myNumber = next;
+        int maxNumber = myNumber;
+        for (T dominated : block.getDominated()) {
+            maxNumber = calcDominatorRanges(dominated, maxNumber + 1);
+        }
+        block.setDominatorNumbers(myNumber, maxNumber);
+        return maxNumber;
     }
 
     /**
      * True if block {@code a} is dominated by block {@code b}.
      */
     static boolean isDominatedBy(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
-        assert a != null && b != null;
-        if (a == b) {
-            return true;
-        }
-        if (a.getDominatorDepth() < b.getDominatorDepth()) {
-            return false;
-        }
-
-        return b == (AbstractBlockBase<?>) a.getDominator(a.getDominatorDepth() - b.getDominatorDepth());
+        int domNumberA = a.getDominatorNumber();
+        int domNumberB = b.getDominatorNumber();
+        return domNumberA >= domNumberB && domNumberA <= b.getMaxChildDominatorNumber();
     }
 
     /**
@@ -101,21 +107,49 @@
     static AbstractBlockBase<?> commonDominator(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
         if (a == null) {
             return b;
-        }
-        if (b == null) {
+        } else if (b == null) {
             return a;
+        } else {
+            int aDomDepth = a.getDominatorDepth();
+            int bDomDepth = b.getDominatorDepth();
+            AbstractBlockBase<?> aTemp;
+            AbstractBlockBase<?> bTemp;
+            if (aDomDepth > bDomDepth) {
+                aTemp = a;
+                bTemp = b;
+            } else {
+                aTemp = b;
+                bTemp = a;
+            }
+            return commonDominatorHelper(aTemp, bTemp);
         }
+    }
 
-        AbstractBlockBase<?> iterA = a;
-        AbstractBlockBase<?> iterB = b;
+    static AbstractBlockBase<?> commonDominatorHelper(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        int domNumberA = a.getDominatorNumber();
+        AbstractBlockBase<?> result = b;
+        while (domNumberA < result.getDominatorNumber()) {
+            result = result.getDominator();
+        }
+        while (domNumberA > result.getMaxChildDominatorNumber()) {
+            result = result.getDominator();
+        }
+        return result;
+    }
+
+    static AbstractBlockBase<?> commonDominatorRaw(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
         int aDomDepth = a.getDominatorDepth();
         int bDomDepth = b.getDominatorDepth();
         if (aDomDepth > bDomDepth) {
-            iterA = a.getDominator(aDomDepth - bDomDepth);
+            return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
         } else {
-            iterB = b.getDominator(bDomDepth - aDomDepth);
+            return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
         }
+    }
 
+    static AbstractBlockBase<?> commonDominatorRawSameDepth(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        AbstractBlockBase<?> iterA = a;
+        AbstractBlockBase<?> iterB = b;
         while (iterA != iterB) {
             iterA = iterA.getDominator();
             iterB = iterB.getDominator();
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Tue Mar 03 13:19:35 2015 +0100
@@ -60,6 +60,7 @@
 import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.common.*;
 import com.oracle.graal.phases.schedule.*;
+import com.oracle.graal.phases.schedule.SchedulePhase.*;
 import com.oracle.graal.phases.tiers.*;
 import com.oracle.graal.phases.util.*;
 import com.oracle.graal.printer.*;
@@ -302,7 +303,8 @@
     }
 
     protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) {
-        SchedulePhase schedule = new SchedulePhase();
+        SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST);
+        schedule.setScheduleConstants(true);
         schedule.apply(graph);
 
         NodeMap<Integer> canonicalId = graph.createNodeMap();
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java	Tue Mar 03 13:19:35 2015 +0100
@@ -28,6 +28,7 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
 import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.debug.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.common.*;
 import com.oracle.graal.phases.schedule.*;
@@ -36,9 +37,10 @@
 
 public class LongNodeChainTest extends GraalCompilerTest {
 
-    public static final int N = 100000;
+    public static final int N = 10000;
 
-    @Ignore
+    private static final SchedulingStrategy[] Strategies = new SchedulingStrategy[]{SchedulingStrategy.EARLIEST};
+
     @Test
     public void testLongAddChain() {
         longAddChain(true);
@@ -51,6 +53,9 @@
         ValueNode constant = graph.unique(ConstantNode.forPrimitive(JavaConstant.INT_1));
         ValueNode value = null;
         if (reverse) {
+            // Make sure the constant's stamp is not used to infer the add node's stamp.
+            OpaqueNode opaque = graph.unique(new OpaqueNode(constant));
+            constant = opaque;
             AddNode addNode = graph.unique(new AddNode(constant, constant));
             value = addNode;
             for (int i = 1; i < N; ++i) {
@@ -58,6 +63,7 @@
                 addNode.setY(newAddNode);
                 addNode = newAddNode;
             }
+            opaque.replaceAndDelete(opaque.getValue());
         } else {
             value = constant;
             for (int i = 0; i < N; ++i) {
@@ -67,7 +73,7 @@
         ReturnNode returnNode = graph.add(new ReturnNode(value));
         graph.start().setNext(returnNode);
 
-        for (SchedulingStrategy s : SchedulingStrategy.values()) {
+        for (SchedulingStrategy s : Strategies) {
             new SchedulePhase(s).apply(graph);
         }
 
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Tue Mar 03 13:19:35 2015 +0100
@@ -43,10 +43,10 @@
 import com.oracle.graal.lir.asm.*;
 import com.oracle.graal.lir.framemap.*;
 import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
 import com.oracle.graal.lir.phases.*;
+import com.oracle.graal.lir.phases.PostAllocationOptimizationPhase.PostAllocationOptimizationContext;
 import com.oracle.graal.lir.phases.PreAllocationOptimizationPhase.PreAllocationOptimizationContext;
-import com.oracle.graal.lir.phases.PostAllocationOptimizationPhase.PostAllocationOptimizationContext;
-import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.spi.*;
@@ -64,6 +64,8 @@
 
     private static final DebugTimer FrontEnd = Debug.timer("FrontEnd");
     private static final DebugTimer BackEnd = Debug.timer("BackEnd");
+    private static final DebugTimer EmitLIR = Debug.timer("EmitLIR");
+    private static final DebugTimer EmitCode = Debug.timer("EmitCode");
 
     /**
      * The set of positive filters specified by the {@code -G:IntrinsificationsEnabled} option. To
@@ -93,6 +95,9 @@
         @Option(help = "Pattern for method(s) to which intrinsification will not be applied. " +
                        "See MethodFilter class for pattern syntax.", type = OptionType.Debug)
         public static final OptionValue<String> IntrinsificationsDisabled = new OptionValue<>(null);
+
+        @Option(help = "Repeatedly run the LIR code generation pass to improve statistical profiling results.", type = OptionType.Debug)
+        public static final OptionValue<Integer> EmitLIRRepeatCount = new OptionValue<>(0);
         // @formatter:on
 
     }
@@ -276,10 +281,18 @@
 
     public static <T extends CompilationResult> void emitBackEnd(StructuredGraph graph, Object stub, CallingConvention cc, ResolvedJavaMethod installedCodeOwner, Backend backend,
                     TargetDescription target, T compilationResult, CompilationResultBuilderFactory factory, SchedulePhase schedule, RegisterConfig registerConfig, LIRSuites lirSuites) {
-        try (TimerCloseable a = BackEnd.start()) {
+        try (Scope s = Debug.scope("BackEnd"); TimerCloseable a = BackEnd.start()) {
+            // Repeatedly run the LIR code generation pass to improve statistical profiling results.
+            for (int i = 0; i < EmitLIRRepeatCount.getValue(); i++) {
+                SchedulePhase dummySchedule = new SchedulePhase();
+                dummySchedule.setScheduleConstants(true);
+                dummySchedule.apply(graph);
+                emitLIR(backend, target, dummySchedule, graph, stub, cc, registerConfig, lirSuites);
+            }
+
             LIRGenerationResult lirGen = null;
             lirGen = emitLIR(backend, target, schedule, graph, stub, cc, registerConfig, lirSuites);
-            try (Scope s = Debug.scope("CodeGen", lirGen, lirGen.getLIR())) {
+            try (Scope s2 = Debug.scope("CodeGen", lirGen, lirGen.getLIR())) {
                 emitCode(backend, graph.getAssumptions(), graph.method(), graph.getInlinedMethods(), lirGen, compilationResult, installedCodeOwner, factory);
             } catch (Throwable e) {
                 throw Debug.handle(e);
@@ -300,18 +313,21 @@
         }
     }
 
+    private static final DebugTimer lirGenTimeTracker = Debug.timer("LIRGenTime");
+    private static final DebugMemUseTracker lirGenMemUseTracker = Debug.memUseTracker("LIRGenMemUse");
+
     public static LIRGenerationResult emitLIR(Backend backend, TargetDescription target, SchedulePhase schedule, StructuredGraph graph, Object stub, CallingConvention cc,
                     RegisterConfig registerConfig, LIRSuites lirSuites) {
-        List<Block> blocks = schedule.getCFG().getBlocks();
-        Block startBlock = schedule.getCFG().getStartBlock();
-        assert startBlock != null;
-        assert startBlock.getPredecessorCount() == 0;
+        try (Scope ds = Debug.scope("EmitLIR"); TimerCloseable a = EmitLIR.start()) {
+            List<Block> blocks = schedule.getCFG().getBlocks();
+            Block startBlock = schedule.getCFG().getStartBlock();
+            assert startBlock != null;
+            assert startBlock.getPredecessorCount() == 0;
 
-        LIR lir = null;
-        List<Block> codeEmittingOrder = null;
-        List<Block> linearScanOrder = null;
-        try (Scope ds = Debug.scope("MidEnd")) {
-            try (Scope s = Debug.scope("ComputeLinearScanOrder")) {
+            LIR lir = null;
+            List<Block> codeEmittingOrder = null;
+            List<Block> linearScanOrder = null;
+            try (Scope s = Debug.scope("ComputeLinearScanOrder", lir)) {
                 codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.size(), startBlock);
                 linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.size(), startBlock);
 
@@ -320,16 +336,12 @@
             } catch (Throwable e) {
                 throw Debug.handle(e);
             }
-        } catch (Throwable e) {
-            throw Debug.handle(e);
-        }
-        try (Scope ds = Debug.scope("BackEnd", lir)) {
             FrameMapBuilder frameMapBuilder = backend.newFrameMapBuilder(registerConfig);
             LIRGenerationResult lirGenRes = backend.newLIRGenerationResult(lir, frameMapBuilder, graph.method(), stub);
             LIRGeneratorTool lirGen = backend.newLIRGenerator(cc, lirGenRes);
             NodeLIRBuilderTool nodeLirGen = backend.newNodeLIRBuilder(graph, lirGen);
 
-            try (Scope s = Debug.scope("LIRGen", lirGen)) {
+            try (Scope s = Debug.scope("LIRGen", lir, lirGen); AutoCloseable c = lirGenMemUseTracker.start(); AutoCloseable t = lirGenTimeTracker.start()) {
                 for (Block b : linearScanOrder) {
                     emitBlock(nodeLirGen, lirGenRes, b, graph, schedule.getBlockToNodesMap());
                 }
@@ -366,45 +378,49 @@
 
     public static void emitCode(Backend backend, Assumptions assumptions, ResolvedJavaMethod rootMethod, Set<ResolvedJavaMethod> inlinedMethods, LIRGenerationResult lirGenRes,
                     CompilationResult compilationResult, ResolvedJavaMethod installedCodeOwner, CompilationResultBuilderFactory factory) {
-        FrameMap frameMap = lirGenRes.getFrameMap();
-        CompilationResultBuilder crb = backend.newCompilationResultBuilder(lirGenRes, frameMap, compilationResult, factory);
-        backend.emitCode(crb, lirGenRes.getLIR(), installedCodeOwner);
-        crb.finish();
-        if (assumptions != null && !assumptions.isEmpty()) {
-            compilationResult.setAssumptions(assumptions.toArray());
-        }
-        if (inlinedMethods != null) {
-            compilationResult.setMethods(rootMethod, inlinedMethods);
-        }
-
-        if (Debug.isMeterEnabled()) {
-            List<DataPatch> ldp = compilationResult.getDataPatches();
-            Kind[] kindValues = Kind.values();
-            DebugMetric[] dms = new DebugMetric[kindValues.length];
-            for (int i = 0; i < dms.length; i++) {
-                dms[i] = Debug.metric("DataPatches-%s", kindValues[i]);
+        try (TimerCloseable a = EmitCode.start()) {
+            FrameMap frameMap = lirGenRes.getFrameMap();
+            CompilationResultBuilder crb = backend.newCompilationResultBuilder(lirGenRes, frameMap, compilationResult, factory);
+            backend.emitCode(crb, lirGenRes.getLIR(), installedCodeOwner);
+            crb.finish();
+            if (assumptions != null && !assumptions.isEmpty()) {
+                compilationResult.setAssumptions(assumptions.toArray());
+            }
+            if (inlinedMethods != null) {
+                compilationResult.setMethods(rootMethod, inlinedMethods);
             }
 
-            for (DataPatch dp : ldp) {
-                Kind kind = Kind.Illegal;
-                if (dp.reference instanceof ConstantReference) {
-                    VMConstant constant = ((ConstantReference) dp.reference).getConstant();
-                    kind = ((JavaConstant) constant).getKind();
+            if (Debug.isMeterEnabled()) {
+                List<DataPatch> ldp = compilationResult.getDataPatches();
+                Kind[] kindValues = Kind.values();
+                DebugMetric[] dms = new DebugMetric[kindValues.length];
+                for (int i = 0; i < dms.length; i++) {
+                    dms[i] = Debug.metric("DataPatches-%s", kindValues[i]);
                 }
-                dms[kind.ordinal()].add(1);
+
+                for (DataPatch dp : ldp) {
+                    Kind kind = Kind.Illegal;
+                    if (dp.reference instanceof ConstantReference) {
+                        VMConstant constant = ((ConstantReference) dp.reference).getConstant();
+                        kind = ((JavaConstant) constant).getKind();
+                    }
+                    dms[kind.ordinal()].add(1);
+                }
+
+                Debug.metric("CompilationResults").increment();
+                Debug.metric("CodeBytesEmitted").add(compilationResult.getTargetCodeSize());
+                Debug.metric("InfopointsEmitted").add(compilationResult.getInfopoints().size());
+                Debug.metric("DataPatches").add(ldp.size());
+                Debug.metric("ExceptionHandlersEmitted").add(compilationResult.getExceptionHandlers().size());
             }
 
-            Debug.metric("CompilationResults").increment();
-            Debug.metric("CodeBytesEmitted").add(compilationResult.getTargetCodeSize());
-            Debug.metric("InfopointsEmitted").add(compilationResult.getInfopoints().size());
-            Debug.metric("DataPatches").add(ldp.size());
-            Debug.metric("ExceptionHandlersEmitted").add(compilationResult.getExceptionHandlers().size());
+            if (Debug.isLogEnabled()) {
+                Debug.log("%s", backend.getProviders().getCodeCache().disassemble(compilationResult, null));
+            }
+
+            Debug.dump(compilationResult, "After code generation");
+        } catch (Throwable e) {
+            throw Debug.handle(e);
         }
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("%s", backend.getProviders().getCodeCache().disassemble(compilationResult, null));
-        }
-
-        Debug.dump(compilationResult, "After code generation");
     }
 }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Tue Mar 03 13:19:35 2015 +0100
@@ -83,7 +83,7 @@
                 for (Entry<VirtualObjectNode, VirtualObject> entry : virtualObjectsCopy.entrySet()) {
                     if (entry.getValue().getValues() == null) {
                         VirtualObjectNode vobj = entry.getKey();
-                        JavaValue[] values = new JavaValue[vobj.entryCount()];
+                        Value[] values = new Value[vobj.entryCount()];
                         if (values.length > 0) {
                             changed = true;
                             VirtualObjectState currentField = (VirtualObjectState) objectStates.get(vobj);
@@ -98,7 +98,7 @@
                                 }
                             }
                             if (pos != vobj.entryCount()) {
-                                JavaValue[] newValues = new JavaValue[pos];
+                                Value[] newValues = new Value[pos];
                                 System.arraycopy(values, 0, newValues, 0, pos);
                                 values = newValues;
                             }
@@ -136,7 +136,7 @@
             int numStack = state.stackSize();
             int numLocks = state.locksSize();
 
-            JavaValue[] values = new JavaValue[numLocals + numStack + numLocks];
+            Value[] values = new Value[numLocals + numStack + numLocks];
             computeLocals(state, numLocals, values);
             computeStack(state, numLocals, numStack, values);
             computeLocks(state, values);
@@ -151,33 +151,33 @@
         }
     }
 
-    protected void computeLocals(FrameState state, int numLocals, JavaValue[] values) {
+    protected void computeLocals(FrameState state, int numLocals, Value[] values) {
         for (int i = 0; i < numLocals; i++) {
             values[i] = computeLocalValue(state, i);
         }
     }
 
-    protected JavaValue computeLocalValue(FrameState state, int i) {
+    protected Value computeLocalValue(FrameState state, int i) {
         return toValue(state.localAt(i));
     }
 
-    protected void computeStack(FrameState state, int numLocals, int numStack, JavaValue[] values) {
+    protected void computeStack(FrameState state, int numLocals, int numStack, Value[] values) {
         for (int i = 0; i < numStack; i++) {
             values[numLocals + i] = computeStackValue(state, i);
         }
     }
 
-    protected JavaValue computeStackValue(FrameState state, int i) {
+    protected Value computeStackValue(FrameState state, int i) {
         return toValue(state.stackAt(i));
     }
 
-    protected void computeLocks(FrameState state, JavaValue[] values) {
+    protected void computeLocks(FrameState state, Value[] values) {
         for (int i = 0; i < state.locksSize(); i++) {
             values[state.localsSize() + state.stackSize() + i] = computeLockValue(state, i);
         }
     }
 
-    protected JavaValue computeLockValue(FrameState state, int i) {
+    protected Value computeLockValue(FrameState state, int i) {
         return toValue(state.lockAt(i));
     }
 
@@ -186,7 +186,7 @@
     private static final DebugMetric STATE_VARIABLES = Debug.metric("StateVariables");
     private static final DebugMetric STATE_CONSTANTS = Debug.metric("StateConstants");
 
-    protected JavaValue toValue(ValueNode value) {
+    protected Value toValue(ValueNode value) {
         try {
             if (value instanceof VirtualObjectNode) {
                 VirtualObjectNode obj = (VirtualObjectNode) value;
@@ -218,7 +218,7 @@
                     STATE_VARIABLES.increment();
                     Value operand = nodeOperands.get(value);
                     assert operand != null && (operand instanceof Variable || operand instanceof JavaConstant) : operand + " for " + value;
-                    return (JavaValue) operand;
+                    return operand;
 
                 } else {
                     // return a dummy value because real value not needed
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Tue Mar 03 13:19:35 2015 +0100
@@ -32,6 +32,7 @@
     private long[] bits;
     private int nodeCount;
     private final NodeIdAccessor nodeIdAccessor;
+    private int counter;
 
     public NodeBitMap(Graph graph) {
         nodeCount = graph.nodeIdCount();
@@ -43,6 +44,10 @@
         return (nodeCount + Long.SIZE - 1) >> SHIFT;
     }
 
+    public int getCounter() {
+        return counter;
+    }
+
     private NodeBitMap(NodeBitMap other) {
         this.bits = other.bits.clone();
         this.nodeCount = other.nodeCount;
@@ -63,6 +68,16 @@
         return isMarked(id);
     }
 
+    public boolean checkAndMarkInc(Node node) {
+        if (!isMarked(node)) {
+            this.counter++;
+            this.mark(node);
+            return true;
+        } else {
+            return false;
+        }
+    }
+
     public boolean isMarked(int id) {
         return (bits[id >> SHIFT] & (1L << id)) != 0;
     }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotDebugInfoBuilder.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotDebugInfoBuilder.java	Tue Mar 03 13:19:35 2015 +0100
@@ -26,7 +26,6 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.gen.*;
 import com.oracle.graal.graph.*;
-import com.oracle.graal.lir.*;
 import com.oracle.graal.nodes.*;
 
 /**
@@ -46,25 +45,20 @@
     }
 
     @Override
-    protected JavaValue computeLockValue(FrameState state, int lockIndex) {
+    protected Value computeLockValue(FrameState state, int lockIndex) {
         int lockDepth = lockIndex;
         if (state.outerFrameState() != null) {
             lockDepth += state.outerFrameState().nestedLockDepth();
         }
         StackSlotValue slot = lockStack.makeLockSlot(lockDepth);
         ValueNode lock = state.lockAt(lockIndex);
-        JavaValue object = toValue(lock);
+        Value object = toValue(lock);
         boolean eliminated = object instanceof VirtualObject && state.monitorIdAt(lockIndex) != null;
         assert state.monitorIdAt(lockIndex) == null || state.monitorIdAt(lockIndex).getLockDepth() == lockDepth;
         return new StackLockValue(object, slot, eliminated);
     }
 
     @Override
-    protected LIRFrameState newLIRFrameState(LabelRef exceptionEdge, BytecodeFrame frame, VirtualObject[] virtualObjectsArray) {
-        return new HotSpotLIRFrameState(frame, virtualObjectsArray, exceptionEdge);
-    }
-
-    @Override
     protected BytecodeFrame computeFrameForState(FrameState state) {
         assert state.bci >= 0 || state.bci == BytecodeFrame.BEFORE_BCI : state.bci;
         return super.computeFrameForState(state);
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotLIRFrameState.java	Mon Mar 02 19:11:22 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,60 +0,0 @@
-/*
- * Copyright (c) 2013, 2014, 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.graal.hotspot;
-
-import static com.oracle.graal.api.code.ValueUtil.*;
-
-import com.oracle.graal.api.code.*;
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.LIRInstruction.OperandMode;
-
-/**
- * Extends {@link LIRFrameState} to handle {@link StackLockValue}s correctly.
- */
-class HotSpotLIRFrameState extends LIRFrameState {
-
-    public HotSpotLIRFrameState(BytecodeFrame topFrame, VirtualObject[] virtualObjects, LabelRef exceptionEdge) {
-        super(topFrame, virtualObjects, exceptionEdge);
-    }
-
-    @Override
-    protected Value processValue(LIRInstruction inst, InstructionValueProcedure proc, Value value) {
-        if (value instanceof StackLockValue) {
-            StackLockValue monitor = (StackLockValue) value;
-            if (monitor.getOwner() instanceof Value) {
-                Value owner = (Value) monitor.getOwner();
-                if (processed(owner)) {
-                    monitor.setOwner((JavaValue) proc.doValue(inst, owner, OperandMode.ALIVE, STATE_FLAGS));
-                }
-            }
-            Value slot = monitor.getSlot();
-            if (isVirtualStackSlot(slot) && processed(slot)) {
-                monitor.setSlot(asStackSlotValue(proc.doValue(inst, slot, OperandMode.ALIVE, STATE_FLAGS)));
-            }
-            return value;
-        } else {
-            return super.processValue(inst, proc, value);
-        }
-    }
-}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java	Tue Mar 03 13:19:35 2015 +0100
@@ -80,39 +80,51 @@
      */
     protected static final EnumSet<OperandFlag> STATE_FLAGS = EnumSet.of(OperandFlag.REG, OperandFlag.STACK);
 
-    protected void processValues(LIRInstruction inst, JavaValue[] values, InstructionValueProcedure proc) {
+    protected void processValues(LIRInstruction inst, Value[] values, InstructionValueProcedure proc) {
         for (int i = 0; i < values.length; i++) {
-            if (values[i] instanceof Value) {
-                Value value = (Value) values[i];
-                values[i] = (JavaValue) processValue(inst, proc, value);
-            }
+            Value value = values[i];
+            values[i] = processValue(inst, proc, value);
         }
     }
 
     protected Value processValue(LIRInstruction inst, InstructionValueProcedure proc, Value value) {
-        if (processed(value)) {
-            return proc.doValue(inst, value, OperandMode.ALIVE, STATE_FLAGS);
+        if (value instanceof StackLockValue) {
+            StackLockValue monitor = (StackLockValue) value;
+            Value owner = monitor.getOwner();
+            if (owner instanceof AllocatableValue) {
+                monitor.setOwner(proc.doValue(inst, owner, OperandMode.ALIVE, STATE_FLAGS));
+            }
+            Value slot = monitor.getSlot();
+            if (isVirtualStackSlot(slot)) {
+                monitor.setSlot(asStackSlotValue(proc.doValue(inst, slot, OperandMode.ALIVE, STATE_FLAGS)));
+            }
+        } else {
+            if (!isIllegal(value) && value instanceof AllocatableValue) {
+                return proc.doValue(inst, value, OperandMode.ALIVE, STATE_FLAGS);
+            } else {
+                assert unprocessed(value);
+            }
         }
         return value;
     }
 
-    protected boolean processed(Value value) {
+    private boolean unprocessed(Value value) {
         if (isIllegal(value)) {
             // Ignore dead local variables.
-            return false;
+            return true;
         } else if (isConstant(value)) {
             // Ignore constants, the register allocator does not need to see them.
-            return false;
+            return true;
         } else if (isVirtualObject(value)) {
             assert Arrays.asList(virtualObjects).contains(value);
-            return false;
+            return true;
         } else {
-            return true;
+            return false;
         }
     }
 
     /**
-     * Called by the register allocator before {@link #markLocation} to initialize the frame state.
+     * Called by the register allocator before {@link #updateUnion} to initialize the frame state.
      *
      * @param frameMap The frame map.
      * @param canHaveRegisters True if there can be any register map entries.
@@ -122,18 +134,6 @@
     }
 
     /**
-     * Called by the register allocator to mark the specified location as a reference in the
-     * reference map of the debug information. The tracked location can be a {@link RegisterValue}
-     * or a {@link StackSlot}. Note that a {@link JavaConstant} is automatically tracked.
-     *
-     * @param location The location to be added to the reference map.
-     * @param frameMap The frame map.
-     */
-    public void markLocation(Value location, FrameMap frameMap) {
-        frameMap.setReference(location, debugInfo.getReferenceMap());
-    }
-
-    /**
      * Updates this reference map with all references that are marked in {@code refMap}.
      */
     public void updateUnion(ReferenceMap refMap) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Tue Mar 03 13:19:35 2015 +0100
@@ -39,4 +39,12 @@
     }
 
     public abstract double probability(AbstractBeginNode successor);
+
+    /**
+     * Primary successor of the control split. Data dependencies on the node have to be scheduled in
+     * the primary successor.
+     *
+     * @return the primary successor
+     */
+    public abstract AbstractBeginNode getPrimarySuccessor();
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Tue Mar 03 13:19:35 2015 +0100
@@ -1128,4 +1128,9 @@
 
         return null;
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.trueSuccessor();
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Tue Mar 03 13:19:35 2015 +0100
@@ -232,4 +232,9 @@
         updateUsagesInterface(this.guard, guard);
         this.guard = guard;
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.next();
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Tue Mar 03 13:19:35 2015 +0100
@@ -30,7 +30,6 @@
 
 public final class Block extends AbstractBlockBase<Block> {
 
-    public static final int DISTANCED_DOMINATOR_CACHE = 5;
     protected final AbstractBeginNode beginNode;
 
     protected FixedNode endNode;
@@ -177,28 +176,10 @@
         this.probability = probability;
     }
 
-    public Block getDistancedDominatorCache() {
-        Block result = this.distancedDominatorCache;
-        if (result == null) {
-            Block current = this;
-            for (int i = 0; i < DISTANCED_DOMINATOR_CACHE; ++i) {
-                current = current.getDominator();
-            }
-            distancedDominatorCache = current;
-            return current;
-        } else {
-            return result;
-        }
-    }
-
     @Override
     public Block getDominator(int distance) {
         Block result = this;
-        int i = 0;
-        for (; i < distance - (DISTANCED_DOMINATOR_CACHE - 1); i += DISTANCED_DOMINATOR_CACHE) {
-            result = result.getDistancedDominatorCache();
-        }
-        for (; i < distance; ++i) {
+        for (int i = 0; i < distance; ++i) {
             result = result.getDominator();
         }
         return result;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Tue Mar 03 13:19:35 2015 +0100
@@ -78,6 +78,10 @@
         return reversePostOrder.get(0);
     }
 
+    public Iterable<Block> reversePostOrder() {
+        return reversePostOrder;
+    }
+
     public Iterable<Block> postOrder() {
         return new Iterable<Block>() {
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java	Tue Mar 03 13:19:35 2015 +0100
@@ -32,13 +32,17 @@
 public final class OpaqueNode extends FloatingNode implements LIRLowerable {
 
     public static final NodeClass<OpaqueNode> TYPE = NodeClass.create(OpaqueNode.class);
-    @Input ValueNode value;
+    @Input protected ValueNode value;
 
     public OpaqueNode(ValueNode value) {
         super(TYPE, value.stamp().unrestricted());
         this.value = value;
     }
 
+    public ValueNode getValue() {
+        return value;
+    }
+
     @Override
     public void generate(NodeLIRBuilderTool gen) {
         gen.setResult(this, gen.operand(value));
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Tue Mar 03 13:19:35 2015 +0100
@@ -159,4 +159,9 @@
         }
         return successors.get(defaultSuccessorIndex());
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.defaultSuccessor();
+    }
 }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Mar 03 13:19:35 2015 +0100
@@ -42,7 +42,6 @@
 import com.oracle.graal.phases.graph.*;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
-import com.oracle.graal.phases.util.*;
 
 public final class SchedulePhase extends Phase {
 
@@ -321,7 +320,7 @@
 
     @Override
     protected void run(StructuredGraph graph) {
-        assert GraphOrder.assertNonCyclicGraph(graph);
+        // assert GraphOrder.assertNonCyclicGraph(graph);
         cfg = ControlFlowGraph.compute(graph, true, true, true, false);
         earliestCache = graph.createNodeMap();
         blockToNodesMap = new BlockMap<>(cfg);
@@ -330,6 +329,11 @@
             blockToKillSet = new BlockMap<>(cfg);
         }
 
+        if (selectedStrategy == SchedulingStrategy.EARLIEST) {
+            scheduleEarliestIterative(blockToNodesMap, graph);
+            return;
+        }
+
         assignBlockToNodes(graph, selectedStrategy);
         printSchedule("after assign nodes to blocks");
 
@@ -337,6 +341,146 @@
         printSchedule("after sorting nodes within blocks");
     }
 
+    private void scheduleEarliestIterative(BlockMap<List<ValueNode>> blockToNodes, StructuredGraph graph) {
+        NodeMap<Block> nodeToBlock = graph.createNodeMap();
+        NodeBitMap visited = graph.createNodeBitMap();
+
+        // Add begin nodes as the first entry and set the block for phi nodes.
+        for (Block b : cfg.getBlocks()) {
+            AbstractBeginNode beginNode = b.getBeginNode();
+            ArrayList<ValueNode> nodes = new ArrayList<>();
+            nodeToBlock.set(beginNode, b);
+            nodes.add(beginNode);
+            blockToNodes.put(b, nodes);
+
+            if (beginNode instanceof AbstractMergeNode) {
+                AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode;
+                for (PhiNode phi : mergeNode.phis()) {
+                    nodeToBlock.set(phi, b);
+                }
+            }
+        }
+
+        Stack<Node> stack = new Stack<>();
+
+        // Start analysis with control flow ends.
+        for (Block b : cfg.postOrder()) {
+            FixedNode endNode = b.getEndNode();
+            stack.push(endNode);
+            nodeToBlock.set(endNode, b);
+        }
+
+        processStack(blockToNodes, nodeToBlock, visited, stack);
+
+        // Visit back input edges of loop phis.
+        for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
+            for (PhiNode phi : loopBegin.phis()) {
+                if (visited.isMarked(phi)) {
+                    for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) {
+                        Node node = phi.valueAt(i + loopBegin.forwardEndCount());
+                        if (!visited.isMarked(node)) {
+                            stack.push(node);
+                            processStack(blockToNodes, nodeToBlock, visited, stack);
+                        }
+                    }
+                }
+            }
+        }
+
+        // Check for dead nodes.
+        if (visited.getCounter() < graph.getNodeCount()) {
+            for (Node n : graph.getNodes()) {
+                if (!visited.isMarked(n)) {
+                    n.clearInputs();
+                    n.markDeleted();
+                }
+            }
+        }
+
+        // Add end nodes as the last nodes in each block.
+        for (Block b : cfg.getBlocks()) {
+            FixedNode endNode = b.getEndNode();
+            if (endNode != b.getBeginNode()) {
+                addNode(blockToNodes, b, endNode);
+            }
+        }
+
+        this.blockToNodesMap = blockToNodes;
+    }
+
+    private static void addNode(BlockMap<List<ValueNode>> blockToNodes, Block b, ValueNode endNode) {
+        assert !blockToNodes.get(b).contains(endNode) : endNode;
+        blockToNodes.get(b).add(endNode);
+    }
+
+    private void processStack(BlockMap<List<ValueNode>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, Stack<Node> stack) {
+        Block startBlock = cfg.getStartBlock();
+        while (!stack.isEmpty()) {
+            Node current = stack.peek();
+            if (visited.checkAndMarkInc(current)) {
+
+                // Push inputs and predecessor.
+                Node predecessor = current.predecessor();
+                if (predecessor != null) {
+                    stack.push(predecessor);
+                }
+
+                if (current instanceof PhiNode) {
+                    PhiNode phiNode = (PhiNode) current;
+                    AbstractMergeNode merge = phiNode.merge();
+                    for (int i = 0; i < merge.forwardEndCount(); ++i) {
+                        Node input = phiNode.valueAt(i);
+                        stack.push(input);
+                    }
+                } else {
+                    for (Node input : current.inputs()) {
+                        if (current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) {
+                            // Ignore the cycle.
+                        } else {
+                            stack.push(input);
+                        }
+                    }
+                }
+            } else {
+
+                stack.pop();
+
+                if (nodeToBlock.get(current) == null) {
+                    Node predecessor = current.predecessor();
+                    Block curBlock;
+                    if (predecessor != null) {
+                        // Predecessor determines block.
+                        curBlock = nodeToBlock.get(predecessor);
+                    } else {
+                        Block earliest = startBlock;
+                        for (Node input : current.inputs()) {
+                            if (current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) {
+                                // ignore
+                            } else {
+                                Block inputEarliest;
+                                if (input instanceof ControlSplitNode) {
+                                    inputEarliest = nodeToBlock.get(((ControlSplitNode) input).getPrimarySuccessor());
+                                } else {
+                                    inputEarliest = nodeToBlock.get(input);
+                                }
+                                assert inputEarliest != null : current + " / " + input;
+                                if (earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) {
+                                    earliest = inputEarliest;
+                                }
+                            }
+                        }
+                        curBlock = earliest;
+                    }
+                    assert curBlock != null;
+                    if (current instanceof ValueNode) {
+                        addNode(blockToNodes, curBlock, (ValueNode) current);
+                    }
+                    nodeToBlock.set(current, curBlock);
+                }
+            }
+        }
+    }
+
     private Block blockForMemoryNode(MemoryNode memory) {
         MemoryNode current = memory;
         while (current instanceof MemoryProxy) {
@@ -982,25 +1126,8 @@
         List<ValueNode> sortedInstructions = state.getSortedInstructions();
         Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
         if (lastSorted != b.getEndNode()) {
-            int idx = sortedInstructions.indexOf(b.getEndNode());
-            boolean canNotMove = false;
-            for (int i = idx + 1; i < sortedInstructions.size(); i++) {
-                if (sortedInstructions.get(i).inputs().contains(b.getEndNode())) {
-                    canNotMove = true;
-                    break;
-                }
-            }
-            if (canNotMove) {
-                if (b.getEndNode() instanceof ControlSplitNode) {
-                    throw new GraalGraphInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move").addContext(lastSorted).addContext(
-                                    b.getEndNode());
-                }
-
-                // b.setLastNode(lastSorted);
-            } else {
-                sortedInstructions.remove(b.getEndNode());
-                sortedInstructions.add(b.getEndNode());
-            }
+            sortedInstructions.remove(b.getEndNode());
+            sortedInstructions.add(b.getEndNode());
         }
         return sortedInstructions;
     }
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java	Tue Mar 03 13:19:35 2015 +0100
@@ -182,7 +182,7 @@
         return sb.toString();
     }
 
-    protected String valueToString(JavaValue value, List<VirtualObject> virtualObjects) {
+    protected String valueToString(Value value, List<VirtualObject> virtualObjects) {
         if (value == null) {
             return "-";
         }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java	Tue Mar 03 13:19:35 2015 +0100
@@ -259,6 +259,7 @@
         memoryRead.setStateAfter(n.stateAfter());
 
         ValueNode readValue = implicitLoadConvert(graph, valueKind, memoryRead);
+        n.stateAfter().replaceFirstInput(n, memoryRead);
         n.replaceAtUsages(readValue);
         graph.replaceFixedWithFixed(n, memoryRead);
     }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java	Mon Mar 02 19:11:22 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java	Tue Mar 03 13:19:35 2015 +0100
@@ -34,8 +34,8 @@
 public abstract class IntegerExactArithmeticSplitNode extends ControlSplitNode implements LIRLowerable {
     public static final NodeClass<IntegerExactArithmeticSplitNode> TYPE = NodeClass.create(IntegerExactArithmeticSplitNode.class);
 
+    @Successor AbstractBeginNode next;
     @Successor AbstractBeginNode overflowSuccessor;
-    @Successor AbstractBeginNode next;
     @Input ValueNode x;
     @Input ValueNode y;
 
@@ -48,6 +48,11 @@
     }
 
     @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return next;
+    }
+
+    @Override
     public double probability(AbstractBeginNode successor) {
         return successor == next ? 1 : 0;
     }
--- a/src/share/vm/graal/graalJavaAccess.hpp	Mon Mar 02 19:11:22 2015 +0100
+++ b/src/share/vm/graal/graalJavaAccess.hpp	Tue Mar 03 13:19:35 2015 +0100
@@ -169,7 +169,7 @@
     typeArrayOop_field(BitSet, words, "[J")                                                                                                                    \
   end_class                                                                                                                                                    \
   start_class(BytecodeFrame)                                                                                                                                   \
-    objArrayOop_field(BytecodeFrame, values, "[Lcom/oracle/graal/api/meta/JavaValue;")                                                                         \
+    objArrayOop_field(BytecodeFrame, values, "[Lcom/oracle/graal/api/meta/Value;")                                                                             \
     int_field(BytecodeFrame, numLocals)                                                                                                                        \
     int_field(BytecodeFrame, numStack)                                                                                                                         \
     int_field(BytecodeFrame, numLocks)                                                                                                                         \
@@ -241,10 +241,10 @@
   start_class(VirtualObject)                                                                                                                                   \
     int_field(VirtualObject, id)                                                                                                                               \
     oop_field(VirtualObject, type, "Lcom/oracle/graal/api/meta/ResolvedJavaType;")                                                                             \
-    objArrayOop_field(VirtualObject, values, "[Lcom/oracle/graal/api/meta/JavaValue;")                                                                         \
+    objArrayOop_field(VirtualObject, values, "[Lcom/oracle/graal/api/meta/Value;")                                                                             \
   end_class                                                                                                                                                    \
-  start_class(StackLockValue)                                                                                                                                 \
-    oop_field(StackLockValue, owner, "Lcom/oracle/graal/api/meta/JavaValue;")                                                                                  \
+  start_class(StackLockValue)                                                                                                                                  \
+    oop_field(StackLockValue, owner, "Lcom/oracle/graal/api/meta/Value;")                                                                                      \
     oop_field(StackLockValue, slot, "Lcom/oracle/graal/api/code/StackSlotValue;")                                                                              \
     boolean_field(StackLockValue, eliminated)                                                                                                                  \
   end_class                                                                                                                                                    \
--- a/src/share/vm/runtime/deoptimization.cpp	Mon Mar 02 19:11:22 2015 +0100
+++ b/src/share/vm/runtime/deoptimization.cpp	Tue Mar 03 13:19:35 2015 +0100
@@ -1405,6 +1405,7 @@
     ScopeDesc*      trap_scope  = cvf->scope();
     
     if (TraceDeoptimization) {
+      ttyLocker ttyl;
       tty->print_cr("  bci=%d pc=" INTPTR_FORMAT ", relative_pc=%d, method=%s" GRAAL_ONLY(", debug_id=%d"), trap_scope->bci(), fr.pc(), fr.pc() - nm->code_begin(), trap_scope->method()->name_and_sig_as_C_string()
 #ifdef GRAAL
           , debug_id