# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1329744519 -3600
# Node ID b32ccf2376d2b91c3a67957ae4013a94820f075e
# Parent  75dcf829cfdc5e82e1329dd0eabc8c26a7f775b9
experimental: scheduling and unscheduling of the whole graph

diff -r 75dcf829cfdc -r b32ccf2376d2 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java	Mon Feb 20 14:27:35 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java	Mon Feb 20 14:28:39 2012 +0100
@@ -54,6 +54,21 @@
         sortNodesWithinBlocks(graph);
     }
 
+    public void scheduleGraph() {
+        for (Block block : cfg.getBlocks()) {
+            List<Node> nodeList = nodesFor.get(block);
+            ScheduledNode last = null;
+            for (Node node : nodeList) {
+                if (!(node instanceof FrameState)) {
+                    if (last != null) {
+                        last.setScheduledNext((ScheduledNode) node);
+                    }
+                    last = (ScheduledNode) node;
+                }
+            }
+        }
+    }
+
     public ControlFlowGraph getCFG() {
         return cfg;
     }
@@ -273,9 +288,9 @@
             if (canNotMove) {
                 // (cwi) this was the assertion commented out below.  However, it is failing frequently when the
                 // scheduler is used for debug printing in early compiler phases. This was annoying during debugging
-                // when an excpetion breakpoint is set for assertion errors, so I changed it to a bailout.
+                // when an exception breakpoint is set for assertion errors, so I changed it to a bailout.
                 if (b.getEndNode() instanceof ControlSplitNode) {
-                    throw new GraalInternalError("Schedule is not possible : needs to move a node after the last node of the block whcih can not be move").
+                    throw new GraalInternalError("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());
                 }
diff -r 75dcf829cfdc -r b32ccf2376d2 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/UnscheduleNodes.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/UnscheduleNodes.java	Mon Feb 20 14:28:39 2012 +0100
@@ -0,0 +1,81 @@
+/*
+ * Copyright (c) 2012, 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.compiler.schedule;
+
+import java.util.*;
+
+import com.oracle.max.graal.compiler.graph.*;
+import com.oracle.max.graal.compiler.types.*;
+import com.oracle.max.graal.nodes.*;
+
+class UnscheduleState implements MergeableState<UnscheduleState> {
+
+    public FixedWithNextNode last;
+
+    @Override
+    public boolean merge(MergeNode merge, Collection<UnscheduleState> withStates) {
+        last = null;
+        return true;
+    }
+
+    @Override
+    public void loopBegin(LoopBeginNode loop) {
+        last = null;
+    }
+
+    @Override
+    public void loopEnds(LoopBeginNode loop, Collection<UnscheduleState> loopEndStates) {
+        last = null;
+    }
+
+    @Override
+    public void afterSplit(FixedNode node) {
+        last = null;
+    }
+
+    @Override
+    public UnscheduleState clone() {
+        return new UnscheduleState();
+    }
+}
+
+public class UnscheduleNodes extends ScheduledNodeIterator<UnscheduleState> {
+
+    public UnscheduleNodes(FixedNode start) {
+        super(start, new UnscheduleState());
+    }
+
+    @Override
+    protected void node(ScheduledNode node) {
+        if (node instanceof FixedNode) {
+            if (state.last != null) {
+                state.last.setNext((FixedNode) node);
+            }
+            if (node instanceof FixedWithNextNode) {
+                state.last = (FixedWithNextNode) node;
+            }
+        } else {
+            node.setScheduledNext(null);
+        }
+    }
+}
diff -r 75dcf829cfdc -r b32ccf2376d2 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/ScheduledNodeIterator.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/ScheduledNodeIterator.java	Mon Feb 20 14:28:39 2012 +0100
@@ -0,0 +1,189 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.compiler.types;
+
+import java.util.*;
+
+import com.oracle.max.graal.compiler.graph.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.nodes.*;
+
+public abstract class ScheduledNodeIterator<T extends MergeableState<T>> {
+
+    private final NodeBitMap visitedEnds;
+    private final Deque<ScheduledNode> nodeQueue;
+    private final IdentityHashMap<ScheduledNode, T> nodeStates;
+    private final FixedNode start;
+
+    protected T state;
+
+    public ScheduledNodeIterator(FixedNode start, T initialState) {
+        visitedEnds = start.graph().createNodeBitMap();
+        nodeQueue = new ArrayDeque<>();
+        nodeStates = new IdentityHashMap<>();
+        this.start = start;
+        this.state = initialState;
+    }
+
+    public void apply() {
+        ScheduledNode current = start;
+
+        do {
+            if (current instanceof LoopBeginNode) {
+                state.loopBegin((LoopBeginNode) current);
+                nodeStates.put(current, state);
+                state = state.clone();
+                loopBegin((LoopBeginNode) current);
+                current = current.scheduledNext();
+                assert current != null;
+            } else if (current instanceof LoopEndNode) {
+                loopEnd((LoopEndNode) current);
+                finishLoopEnds((LoopEndNode) current);
+                current = nextQueuedNode();
+            } else if (current instanceof MergeNode) {
+                merge((MergeNode) current);
+                current = current.scheduledNext();
+                assert current != null;
+            } else if (current instanceof EndNode) {
+                end((EndNode) current);
+                queueMerge((EndNode) current);
+                current = nextQueuedNode();
+            } else if (current instanceof ControlSplitNode) {
+                controlSplit((ControlSplitNode) current);
+                queueSuccessors(current);
+                current = nextQueuedNode();
+            } else {
+                ScheduledNode next = current.scheduledNext();
+                node(current);
+                if (next == null) {
+                    current = nextQueuedNode();
+                } else {
+                    current = next;
+                }
+            }
+        } while(current != null);
+    }
+
+    private void queueSuccessors(ScheduledNode x) {
+        nodeStates.put(x, state);
+        for (Node node : x.successors()) {
+            if (node != null) {
+                nodeQueue.addFirst((FixedNode) node);
+            }
+        }
+    }
+
+    private ScheduledNode nextQueuedNode() {
+        int maxIterations = nodeQueue.size();
+        while (maxIterations-- > 0) {
+            ScheduledNode node = nodeQueue.removeFirst();
+            if (node instanceof MergeNode) {
+                MergeNode merge = (MergeNode) node;
+                state = nodeStates.get(merge.forwardEndAt(0)).clone();
+                ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1);
+                for (int i = 1; i < merge.forwardEndCount(); i++) {
+                    T other = nodeStates.get(merge.forwardEndAt(i));
+                    assert other != null;
+                    states.add(other);
+                }
+                boolean ready = state.merge(merge, states);
+                if (ready) {
+                    return merge;
+                } else {
+                    nodeQueue.addLast(merge);
+                }
+            } else {
+                assert node.predecessor() != null;
+                state = nodeStates.get(node.predecessor()).clone();
+                state.afterSplit((FixedNode) node);
+                return node;
+            }
+        }
+        return null;
+    }
+
+    private void queueMerge(EndNode end) {
+        assert !visitedEnds.isMarked(end);
+        assert !nodeStates.containsKey(end);
+        nodeStates.put(end, state);
+        visitedEnds.mark(end);
+        MergeNode merge = end.merge();
+        boolean endsVisited = true;
+        for (int i = 0; i < merge.forwardEndCount(); i++) {
+            if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
+                endsVisited = false;
+                break;
+            }
+        }
+        if (endsVisited) {
+            nodeQueue.add(merge);
+        }
+    }
+
+    private void finishLoopEnds(LoopEndNode end) {
+        assert !visitedEnds.isMarked(end);
+        assert !nodeStates.containsKey(end);
+        nodeStates.put(end, state);
+        visitedEnds.mark(end);
+        LoopBeginNode begin = end.loopBegin();
+        boolean endsVisited = true;
+        for (LoopEndNode le : begin.loopEnds()) {
+            if (!visitedEnds.isMarked(le)) {
+                endsVisited = false;
+                break;
+            }
+        }
+        if (endsVisited) {
+            ArrayList<T> states = new ArrayList<>(begin.loopEnds().count());
+            for (LoopEndNode le : begin.orderedLoopEnds()) {
+                states.add(nodeStates.get(le));
+            }
+            T loopBeginState = nodeStates.get(begin);
+            if (loopBeginState != null) {
+                loopBeginState.loopEnds(begin, states);
+            }
+        }
+    }
+
+    protected abstract void node(ScheduledNode node);
+
+    protected void end(EndNode endNode) {
+        node(endNode);
+    }
+
+    protected void merge(MergeNode merge) {
+        node(merge);
+    }
+
+    protected void loopBegin(LoopBeginNode loopBegin) {
+        node(loopBegin);
+    }
+
+    protected void loopEnd(LoopEndNode loopEnd) {
+        node(loopEnd);
+    }
+
+    protected void controlSplit(ControlSplitNode controlSplit) {
+        node(controlSplit);
+    }
+}
diff -r 75dcf829cfdc -r b32ccf2376d2 graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Mon Feb 20 14:27:35 2012 +0100
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Mon Feb 20 14:28:39 2012 +0100
@@ -86,7 +86,7 @@
     @Target(ElementType.METHOD)
     public static @interface NodeIntrinsic {
         /**
-         * Gets the {@link Node} subclass instantiated when intrinsifyng a call to the annotated method.
+         * Gets the {@link Node} subclass instantiated when intrinsifying a call to the annotated method.
          * If not specified, then the class in which the annotated method is declared is used
          * (and is assumed to be a {@link Node} subclass).
          */