# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1329744028 -3600
# Node ID 9f781aae247053e56f13241c351768cc21150722
# Parent  5d9013afbffffd4eceea7864e927d66d8239ce28
separate GraphOrder from EscapeAnalysisPhase

diff -r 5d9013afbfff -r 9f781aae2470 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java	Mon Feb 20 14:18:38 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java	Mon Feb 20 14:20:28 2012 +0100
@@ -28,6 +28,7 @@
 import com.oracle.max.criutils.*;
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.compiler.graph.*;
+import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.cri.*;
 import com.oracle.max.graal.debug.*;
 import com.oracle.max.graal.graph.*;
@@ -40,67 +41,6 @@
 
 
 public class EscapeAnalysisPhase extends Phase {
-    public static class GraphOrder implements Iterable<Node> {
-
-        private final ArrayList<Node> nodes = new ArrayList<>();
-
-        public GraphOrder(Graph graph) {
-            NodeBitMap visited = graph.createNodeBitMap();
-
-            for (ReturnNode node : graph.getNodes(ReturnNode.class)) {
-                visit(visited, node);
-            }
-            for (UnwindNode node : graph.getNodes(UnwindNode.class)) {
-                visit(visited, node);
-            }
-            for (DeoptimizeNode node : graph.getNodes(DeoptimizeNode.class)) {
-                visit(visited, node);
-            }
-        }
-
-        private void visit(NodeBitMap visited, Node node) {
-            if (node != null && !visited.isMarked(node)) {
-                visited.mark(node);
-                for (Node input : node.inputs()) {
-                    visit(visited, input);
-                }
-                if (node.predecessor() != null) {
-                    visit(visited, node.predecessor());
-                }
-                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();
-                }
-            };
-        }
-    }
 
     public static class BlockExitState implements MergeableState<BlockExitState> {
         public final ValueNode[] fieldState;
diff -r 5d9013afbfff -r 9f781aae2470 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphOrder.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphOrder.java	Mon Feb 20 14:20:28 2012 +0100
@@ -0,0 +1,141 @@
+/*
+ * Copyright (c) 2011, 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.util;
+
+import java.util.*;
+
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.nodes.*;
+
+public class GraphOrder implements Iterable<Node> {
+
+    private final ArrayList<Node> nodes = new ArrayList<>();
+
+    private GraphOrder() {
+    }
+
+    public GraphOrder(Graph graph) {
+        NodeBitMap visited = graph.createNodeBitMap();
+
+        for (ReturnNode node : graph.getNodes(ReturnNode.class)) {
+            visitForward(visited, node);
+        }
+        for (UnwindNode node : graph.getNodes(UnwindNode.class)) {
+            visitForward(visited, node);
+        }
+        for (DeoptimizeNode node : graph.getNodes(DeoptimizeNode.class)) {
+            visitForward(visited, node);
+        }
+    }
+
+    public static GraphOrder forwardGraph(Graph graph) {
+        GraphOrder result = new GraphOrder();
+
+        NodeBitMap visited = graph.createNodeBitMap();
+
+        for (ReturnNode node : graph.getNodes(ReturnNode.class)) {
+            result.visitForward(visited, node);
+        }
+        for (UnwindNode node : graph.getNodes(UnwindNode.class)) {
+            result.visitForward(visited, node);
+        }
+        for (DeoptimizeNode node : graph.getNodes(DeoptimizeNode.class)) {
+            result.visitForward(visited, node);
+        }
+        return result;
+    }
+
+    public static GraphOrder backwardGraph(Graph graph) {
+        GraphOrder result = new GraphOrder();
+
+        NodeBitMap visited = graph.createNodeBitMap();
+
+        for (Node node : forwardGraph(graph)) {
+            result.visitBackward(visited, node);
+        }
+        return result;
+    }
+
+    private void visitForward(NodeBitMap visited, Node node) {
+        if (node != null && !visited.isMarked(node)) {
+            visited.mark(node);
+            if (node.predecessor() != null) {
+                visitForward(visited, node.predecessor());
+            }
+            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()) {
+                visitForward(visited, input);
+            }
+            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);
+            }
+            for (Node usage : node.usages()) {
+                visitBackward(visited, usage);
+            }
+            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();
+            }
+        };
+    }
+}