# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1425312471 -3600
# Node ID 84776a6314d741709e6228db63b29bba7bf675a9
# Parent  165244576c9e90a5bf93941edb8f8b1b6bb32c20# Parent  a0284c1724e6ab3923979f2ee6fa233289cfffc7
Merge.

diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Mon Mar 02 17:07:51 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();
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java	Mon Mar 02 17:07:51 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);
         }
 
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Mon Mar 02 17:07:51 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;
     }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Mon Mar 02 17:07:51 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();
 }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Mon Mar 02 17:07:51 2015 +0100
@@ -1128,4 +1128,9 @@
 
         return null;
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.trueSuccessor();
+    }
 }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Mon Mar 02 17:07:51 2015 +0100
@@ -232,4 +232,9 @@
         updateUsagesInterface(this.guard, guard);
         this.guard = guard;
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.next();
+    }
 }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Mon Mar 02 17:07:51 2015 +0100
@@ -78,6 +78,10 @@
         return reversePostOrder.get(0);
     }
 
+    public Iterable<Block> reversePostOrder() {
+        return reversePostOrder;
+    }
+
     public Iterable<Block> postOrder() {
         return new Iterable<Block>() {
 
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java	Mon Mar 02 17:07:51 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));
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Mon Mar 02 17:07:51 2015 +0100
@@ -159,4 +159,9 @@
         }
         return successors.get(defaultSuccessorIndex());
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.defaultSuccessor();
+    }
 }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Mon Mar 02 17:07:51 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,139 @@
         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();
+            nodeToBlock.set(beginNode, b);
+            ArrayList<ValueNode> nodes = new ArrayList<>();
+            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()) {
+            blockToNodes.get(b).add(b.getEndNode());
+        }
+
+        this.blockToNodesMap = blockToNodes;
+    }
+
+    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();
+                    if (nodeToBlock.get(current) == null) {
+                        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;
+                        }
+                        if (current instanceof ValueNode) {
+                            blockToNodes.get(curBlock).add((ValueNode) current);
+                        }
+                        nodeToBlock.set(current, curBlock);
+                    }
+                }
+            }
+        }
+    }
+
     private Block blockForMemoryNode(MemoryNode memory) {
         MemoryNode current = memory;
         while (current instanceof MemoryProxy) {
@@ -982,25 +1119,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;
     }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java	Mon Mar 02 17:07:51 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);
     }
diff -r a0284c1724e6 -r 84776a6314d7 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java	Thu Feb 26 17:39:00 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java	Mon Mar 02 17:07:51 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;
     }