# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1425295589 -3600
# Node ID f25111ca1225bf4ccf5c2d5d3fd753b0664d3a99
# Parent  aed19d655de9f61515120c398e1ce9fa2a0380ca
Make earliest possible schedule iterative.

diff -r aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Mon Mar 02 12:26:29 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 aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Mon Mar 02 12:26:29 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 aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Mon Mar 02 12:26:29 2015 +0100
@@ -1128,4 +1128,9 @@
 
         return null;
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.trueSuccessor();
+    }
 }
diff -r aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Mon Mar 02 12:26:29 2015 +0100
@@ -232,4 +232,9 @@
         updateUsagesInterface(this.guard, guard);
         this.guard = guard;
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.next();
+    }
 }
diff -r aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Mon Mar 02 12:26:29 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 aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Mon Mar 02 12:26:29 2015 +0100
@@ -159,4 +159,9 @@
         }
         return successors.get(defaultSuccessorIndex());
     }
+
+    @Override
+    public AbstractBeginNode getPrimarySuccessor() {
+        return this.defaultSuccessor();
+    }
 }
diff -r aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Mon Mar 02 12:26:29 2015 +0100
@@ -330,6 +330,11 @@
             blockToKillSet = new BlockMap<>(cfg);
         }
 
+        if (selectedStrategy == SchedulingStrategy.EARLIEST) {
+            scheduleEarliestIterative(blockToNodesMap, graph);
+            return;
+        }
+
         assignBlockToNodes(graph, selectedStrategy);
         printSchedule("after assign nodes to blocks");
 
@@ -337,6 +342,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) {
diff -r aed19d655de9 -r f25111ca1225 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	Sun Mar 01 13:36:23 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java	Mon Mar 02 12:26:29 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;
     }