# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1347368226 -7200
# Node ID 31966e3f42d24f5ceab1aba18770f41ee2973e1f
# Parent  2d902712a3f3278c9d34ab3c1ab249118adab724
add new PostOrderBlockIterator for escape analysis

diff -r 2d902712a3f3 -r 31966e3f42d2 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ea/MergeableBlockState.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ea/MergeableBlockState.java	Tue Sep 11 14:57:06 2012 +0200
@@ -0,0 +1,29 @@
+/*
+ * 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.graal.compiler.phases.ea;
+
+
+public interface MergeableBlockState<T> {
+
+    T clone();
+}
diff -r 2d902712a3f3 -r 31966e3f42d2 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ea/PostOrderBlockIterator.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ea/PostOrderBlockIterator.java	Tue Sep 11 14:57:06 2012 +0200
@@ -0,0 +1,177 @@
+/*
+ * 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.graal.compiler.phases.ea;
+
+import java.util.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.lir.cfg.*;
+import com.oracle.graal.nodes.*;
+
+public abstract class PostOrderBlockIterator<T extends MergeableBlockState<T>> {
+
+    private final NodeBitMap visitedEnds;
+    private final Deque<Block> blockQueue;
+    private final IdentityHashMap<FixedNode, T> blockEndStates;
+    private final IdentityHashMap<LoopBeginNode, T> loopBeginStates;
+    private final Block start;
+
+    private T state;
+
+    public PostOrderBlockIterator(StructuredGraph graph, Block start, T initialState) {
+        visitedEnds = graph.createNodeBitMap();
+        blockQueue = new ArrayDeque<>();
+        blockEndStates = new IdentityHashMap<>();
+        loopBeginStates = new IdentityHashMap<>();
+        this.start = start;
+        this.state = initialState;
+    }
+
+    public void apply() {
+        Block current = start;
+
+        do {
+            processBlock(current, state);
+
+            if (current.getSuccessors().isEmpty()) {
+                // nothing to do...
+            } else if (current.getSuccessors().size() == 1) {
+                Block successor = current.getSuccessors().get(0);
+                if (successor.isLoopHeader()) {
+                    if (current.getEndNode() instanceof LoopEndNode) {
+                        finishLoopEnds((LoopEndNode) current.getEndNode());
+                    } else {
+                        LoopBeginNode loopBegin = (LoopBeginNode) successor.getBeginNode();
+                        state = loopBegin(loopBegin, state);
+                        loopBeginStates.put(loopBegin, state);
+                        state = state.clone();
+                        current = successor;
+                        continue;
+                    }
+                } else {
+                    if (successor.getBeginNode() instanceof LoopExitNode) {
+                        assert successor.getPredecessors().size() == 1;
+                        current = successor;
+                        continue;
+                    } else {
+                        assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode();
+                        queueMerge((EndNode) current.getEndNode(), successor);
+                    }
+                }
+            } else {
+                assert current.getSuccessors().size() > 1;
+                queueSuccessors(current);
+            }
+            current = nextQueuedBlock();
+        } while (current != null);
+    }
+
+    protected abstract void processBlock(Block block, T currentState);
+
+    protected abstract T merge(MergeNode merge, List<T> states);
+
+    protected abstract T loopBegin(LoopBeginNode loopBegin, T beforeLoopState);
+
+    protected abstract T loopEnds(LoopBeginNode loopBegin, T loopBeginState, List<T> loopEndStates);
+
+    protected abstract T afterSplit(FixedNode node, T oldState);
+
+
+    private void queueSuccessors(Block current) {
+        blockEndStates.put(current.getEndNode(), state);
+        for (Block block : current.getSuccessors()) {
+            blockQueue.addFirst(block);
+        }
+    }
+
+    private Block nextQueuedBlock() {
+        int maxIterations = blockQueue.size();
+        while (maxIterations-- > 0) {
+            Block block = blockQueue.removeFirst();
+            if (block.getPredecessors().size() > 1) {
+                MergeNode merge = (MergeNode) block.getBeginNode();
+                ArrayList<T> states = new ArrayList<>(merge.forwardEndCount());
+                for (int i = 0; i < merge.forwardEndCount(); i++) {
+                    T other = blockEndStates.get(merge.forwardEndAt(i));
+                    assert other != null;
+                    states.add(other);
+                }
+                state = merge(merge, states);
+                if (state != null) {
+                    return block;
+                } else {
+                    blockQueue.addLast(block);
+                }
+            } else {
+                assert block.getPredecessors().size() == 1;
+                assert block.getBeginNode().predecessor() != null;
+                state = afterSplit(block.getBeginNode(), blockEndStates.get(block.getBeginNode().predecessor()));
+                return block;
+            }
+        }
+        return null;
+    }
+
+    private void queueMerge(EndNode end, Block mergeBlock) {
+        assert !visitedEnds.isMarked(end);
+        assert !blockEndStates.containsKey(end);
+        blockEndStates.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) {
+            blockQueue.addFirst(mergeBlock);
+        }
+    }
+
+    private void finishLoopEnds(LoopEndNode end) {
+        assert !visitedEnds.isMarked(end);
+        assert !blockEndStates.containsKey(end);
+        blockEndStates.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(blockEndStates.get(le));
+            }
+            T loopBeginState = loopBeginStates.get(begin);
+            if (loopBeginState != null) {
+                loopEnds(begin, loopBeginState, states);
+            }
+        }
+    }
+}
diff -r 2d902712a3f3 -r 31966e3f42d2 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PostOrderBlockIterator.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PostOrderBlockIterator.java	Tue Sep 11 14:50:35 2012 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,108 +0,0 @@
-/*
- * 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.graal.compiler.types;
-
-import java.util.*;
-
-import com.oracle.graal.lir.cfg.*;
-
-public abstract class PostOrderBlockIterator {
-
-    private static class MergeInfo {
-        int endsVisited;
-        int loopVisited;
-    }
-
-    private final Deque<Block> blockQueue = new ArrayDeque<>();
-    private final Deque<Block> epochs = new ArrayDeque<>();
-    private final HashMap<Block, MergeInfo> mergeInfo = new HashMap<>();
-
-    public void apply(Block start) {
-        blockQueue.add(start);
-        while (true) {
-            while (!blockQueue.isEmpty()) {
-                Block current = blockQueue.removeLast();
-                boolean queueSuccessors = true;
-                if (current.isLoopHeader()) {
-                    MergeInfo info = mergeInfo.get(current);
-//                    System.out.println("loop header: " + info.loopVisited + " " + info.endsVisited + "-" + info.epoch + " " + epoch);
-                    if (info.endsVisited == 1) {
-                        loopHeaderInitial(current);
-                    } else {
-                        info.loopVisited++;
-                        if (loopHeader(current, info.loopVisited)) {
-                            epochs.addFirst(current);
-                        }
-                        queueSuccessors = false;
-                    }
-                } else {
-                    block(current);
-                }
-
-                if (queueSuccessors) {
-                    for (int i = 0; i < current.getSuccessors().size(); i++) {
-                        Block successor = current.getSuccessors().get(i);
-                        if (successor.getPredecessors().size() > 1) {
-                            queueMerge(successor);
-                        } else {
-                            blockQueue.addLast(successor);
-                        }
-                    }
-                }
-            }
-            if (epochs.isEmpty()) {
-                return;
-            } else {
-                Block nextEpoch = epochs.removeLast();
-
-                for (int i = 0; i < nextEpoch.getSuccessors().size(); i++) {
-                    Block successor = nextEpoch.getSuccessors().get(i);
-                    if (successor.getPredecessors().size() > 1) {
-                        queueMerge(successor);
-                    } else {
-                        blockQueue.addLast(successor);
-                    }
-                }
-            }
-        }
-    }
-
-    protected abstract void loopHeaderInitial(Block block);
-
-    protected abstract boolean loopHeader(Block block, int loopVisitedCount);
-
-    protected abstract void block(Block block);
-
-    private void queueMerge(Block merge) {
-        if (!mergeInfo.containsKey(merge)) {
-            mergeInfo.put(merge, new MergeInfo());
-        }
-        MergeInfo info = mergeInfo.get(merge);
-        info.endsVisited++;
-        if (merge.isLoopHeader() && info.endsVisited == 1) {
-            blockQueue.addFirst(merge);
-        } else if (info.endsVisited == merge.getPredecessors().size()) {
-            blockQueue.addFirst(merge);
-        }
-    }
-}
diff -r 2d902712a3f3 -r 31966e3f42d2 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/ScheduledNodeIterator.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/ScheduledNodeIterator.java	Tue Sep 11 14:50:35 2012 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,189 +0,0 @@
-/*
- * 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.graal.compiler.types;
-
-import java.util.*;
-
-import com.oracle.graal.compiler.graph.*;
-import com.oracle.graal.graph.*;
-import com.oracle.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);
-    }
-}