# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1390400851 -3600
# Node ID 9a6faa08bffed13787d69724dcb95439d024e8ef
# Parent  1541666f4cd71a394a7bc3f464c15b4e72338600
cyclic graph verification

diff -r 1541666f4cd7 -r 9a6faa08bffe graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/MergeableState.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/MergeableState.java	Wed Jan 22 14:03:47 2014 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/MergeableState.java	Wed Jan 22 15:27:31 2014 +0100
@@ -61,4 +61,17 @@
     public void afterSplit(AbstractBeginNode node) {
         // empty default implementation
     }
+
+    public static final class EmptyState extends MergeableState<EmptyState> {
+
+        @Override
+        public EmptyState clone() {
+            return this;
+        }
+
+        @Override
+        public boolean merge(MergeNode merge, List<EmptyState> withStates) {
+            return true;
+        }
+    }
 }
diff -r 1541666f4cd7 -r 9a6faa08bffe 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	Wed Jan 22 14:03:47 2014 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Wed Jan 22 15:27:31 2014 +0100
@@ -262,6 +262,7 @@
 
     @Override
     protected void run(StructuredGraph graph) {
+        assert GraphOrder.assertNonCyclicGraph(graph);
         cfg = ControlFlowGraph.compute(graph, true, true, true, true);
         earliestCache = graph.createNodeMap();
         blockToNodesMap = new BlockMap<>(cfg);
diff -r 1541666f4cd7 -r 9a6faa08bffe graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Wed Jan 22 14:03:47 2014 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Wed Jan 22 15:27:31 2014 +0100
@@ -26,102 +26,88 @@
 
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.phases.graph.*;
 
-public final class GraphOrder implements Iterable<Node> {
-
-    private final ArrayList<Node> nodes = new ArrayList<>();
+public final class GraphOrder {
 
     private GraphOrder() {
     }
 
-    public static GraphOrder forwardGraph(Graph graph) {
-        GraphOrder result = new GraphOrder();
-
+    /**
+     * Asserts that there are no (invalid) cycles in the given graph. First, an ordered list of all
+     * nodes in the graph (a total ordering) is created. A second run over this list checks whether
+     * inputs are scheduled before their usages.
+     * 
+     * @param graph the graph to be checked.
+     * @throws AssertionError if a cycle was detected.
+     */
+    public static boolean assertNonCyclicGraph(StructuredGraph graph) {
+        List<Node> order = createOrder(graph);
         NodeBitMap visited = graph.createNodeBitMap();
+        visited.clearAll();
+        for (Node node : order) {
+            if (node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode) {
+                assert visited.isMarked(((PhiNode) node).valueAt(0));
+                // nothing to do
+            } else {
+                for (Node input : node.inputs()) {
+                    if (!visited.isMarked(input)) {
+                        if (input instanceof FrameState && node instanceof StateSplit && input == ((StateSplit) node).stateAfter()) {
+                            // nothing to do - after frame states are known, allowed cycles
+                        } else {
+                            assert false : "cycle detected: " + node + " -> " + input;
+                        }
+                    }
+                }
+            }
+            visited.mark(node);
+        }
 
-        for (ControlSinkNode node : graph.getNodes().filter(ControlSinkNode.class)) {
-            result.visitForward(visited, node);
-        }
-        return result;
+        return true;
     }
 
-    public static GraphOrder backwardGraph(Graph graph) {
-        GraphOrder result = new GraphOrder();
-
-        NodeBitMap visited = graph.createNodeBitMap();
+    private static List<Node> createOrder(StructuredGraph graph) {
+        final ArrayList<Node> nodes = new ArrayList<>();
+        final NodeBitMap visited = graph.createNodeBitMap();
 
-        for (Node node : forwardGraph(graph)) {
-            result.visitBackward(visited, node);
-        }
-        return result;
+        new PostOrderNodeIterator<MergeableState.EmptyState>(graph.start(), new MergeableState.EmptyState()) {
+            @Override
+            protected void node(FixedNode node) {
+                visitForward(nodes, visited, node, false);
+            }
+        }.apply();
+        return nodes;
     }
 
-    private void visitForward(NodeBitMap visited, Node node) {
+    private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) {
         if (node != null && !visited.isMarked(node)) {
+            assert !floatingOnly || !(node instanceof FixedNode) : "unexpected reference to fixed node: " + node;
             visited.mark(node);
-            if (node.predecessor() != null) {
-                visitForward(visited, node.predecessor());
+            FrameState stateAfter = null;
+            if (node instanceof StateSplit) {
+                stateAfter = ((StateSplit) node).stateAfter();
             }
-            if (node instanceof MergeNode) {
-                // make sure that the cfg predecessors of a MergeNode are processed first
-                MergeNode merge = (MergeNode) node;
-                for (int i = 0; i < merge.forwardEndCount(); i++) {
-                    visitForward(visited, merge.forwardEndAt(i));
+            for (Node input : node.inputs()) {
+                if (input != stateAfter) {
+                    visitForward(nodes, visited, input, true);
                 }
             }
-            for (Node input : node.inputs()) {
-                visitForward(visited, input);
-            }
-            if (node instanceof LoopBeginNode) {
-                LoopBeginNode loopBegin = (LoopBeginNode) node;
-                for (LoopEndNode loopEnd : loopBegin.loopEnds()) {
-                    visitForward(visited, loopEnd);
+            if (node instanceof EndNode) {
+                EndNode end = (EndNode) node;
+                for (PhiNode phi : end.merge().phis()) {
+                    visitForward(nodes, visited, phi.valueAt(end), true);
                 }
             }
             nodes.add(node);
-        }
-    }
-
-    private void visitBackward(NodeBitMap visited, Node node) {
-        if (node != null && !visited.isMarked(node)) {
-            visited.mark(node);
-            for (Node successor : node.successors()) {
-                visitBackward(visited, successor);
+            if (node instanceof MergeNode) {
+                for (PhiNode phi : ((MergeNode) node).phis()) {
+                    visited.mark(phi);
+                    nodes.add(phi);
+                }
             }
-            for (Node usage : node.usages()) {
-                visitBackward(visited, usage);
+            if (stateAfter != null) {
+                visitForward(nodes, visited, stateAfter, true);
             }
-            nodes.add(node);
         }
     }
-
-    @Override
-    public Iterator<Node> iterator() {
-        return new Iterator<Node>() {
-
-            private int pos = 0;
-
-            private void removeDeleted() {
-                while (pos < nodes.size() && nodes.get(pos).isDeleted()) {
-                    pos++;
-                }
-            }
-
-            @Override
-            public boolean hasNext() {
-                removeDeleted();
-                return pos < nodes.size();
-            }
-
-            @Override
-            public Node next() {
-                return nodes.get(pos++);
-            }
-
-            @Override
-            public void remove() {
-                throw new UnsupportedOperationException();
-            }
-        };
-    }
 }