# HG changeset patch
# User Lukas Stadler <lukas.stadler@oracle.com>
# Date 1400860035 -7200
# Node ID e626b112aa3da6e24cd34706b781ce46dd4240d4
# Parent  23f45bae453a9e4e314defc3fca2090a3a10d83f
consume less memory in ReentrantBlockIterator and ReentrantNodeIterator

diff -r 23f45bae453a -r e626b112aa3d graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java	Fri May 23 17:43:07 2014 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java	Fri May 23 17:47:15 2014 +0200
@@ -34,8 +34,13 @@
 
     public static class LoopInfo<StateT> {
 
-        public final List<StateT> endStates = new ArrayList<>();
-        public final List<StateT> exitStates = new ArrayList<>();
+        public final List<StateT> endStates;
+        public final List<StateT> exitStates;
+
+        public LoopInfo(int endCount, int exitCount) {
+            endStates = new ArrayList<>(endCount);
+            exitStates = new ArrayList<>(exitCount);
+        }
     }
 
     public abstract static class BlockIteratorClosure<StateT> {
@@ -58,8 +63,8 @@
     public static <StateT> LoopInfo<StateT> processLoop(BlockIteratorClosure<StateT> closure, Loop<Block> loop, StateT initialState) {
         Map<FixedNode, StateT> blockEndStates = apply(closure, loop.getHeader(), initialState, new HashSet<>(loop.getBlocks()));
 
-        LoopInfo<StateT> info = new LoopInfo<>();
         List<Block> predecessors = loop.getHeader().getPredecessors();
+        LoopInfo<StateT> info = new LoopInfo<>(predecessors.size() - 1, loop.getExits().size());
         for (int i = 1; i < predecessors.size(); i++) {
             StateT endState = blockEndStates.get(predecessors.get(i).getEndNode());
             // make sure all end states are unique objects
@@ -67,7 +72,7 @@
         }
         for (Block loopExit : loop.getExits()) {
             assert loopExit.getPredecessorCount() == 1;
-            assert blockEndStates.containsKey(loopExit.getBeginNode());
+            assert blockEndStates.containsKey(loopExit.getBeginNode()) : loopExit.getBeginNode() + " " + blockEndStates;
             StateT exitState = blockEndStates.get(loopExit.getBeginNode());
             // make sure all exit states are unique objects
             info.exitStates.add(closure.cloneState(exitState));
@@ -90,7 +95,9 @@
         Block current = start;
 
         while (true) {
-            if (boundary == null || boundary.contains(current)) {
+            if (boundary != null && !boundary.contains(current)) {
+                states.put(current.getBeginNode(), state);
+            } else {
                 state = closure.processBlock(current, state);
 
                 if (current.getSuccessors().isEmpty()) {
@@ -117,45 +124,47 @@
                                 blockQueue.addFirst(exit);
                             }
                         }
-                    } else {
-                        if (successor.getBeginNode() instanceof LoopExitNode) {
-                            assert successor.getPredecessors().size() == 1;
-                            states.put(successor.getBeginNode(), state);
+                    } else if (current.getEndNode() instanceof AbstractEndNode) {
+                        assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode();
+                        AbstractEndNode end = (AbstractEndNode) current.getEndNode();
+
+                        // add the end node and see if the merge is ready for processing
+                        MergeNode merge = end.merge();
+                        boolean endsVisited = true;
+                        for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
+                            if (forwardEnd != current.getEndNode() && !states.containsKey(forwardEnd)) {
+                                endsVisited = false;
+                                break;
+                            }
+                        }
+                        if (endsVisited) {
+                            ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount());
+                            for (Block predecessor : successor.getPredecessors()) {
+                                assert predecessor == current || states.containsKey(predecessor.getEndNode());
+                                StateT endState = predecessor == current ? state : states.remove(predecessor.getEndNode());
+                                mergedStates.add(endState);
+                            }
+                            state = closure.merge(successor, mergedStates);
                             current = successor;
                             continue;
                         } else {
-                            if (current.getEndNode() instanceof AbstractEndNode) {
-                                assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode();
-                                AbstractEndNode end = (AbstractEndNode) current.getEndNode();
-
-                                // add the end node and see if the merge is ready for processing
-                                assert !states.containsKey(end);
-                                states.put(end, state);
-                                MergeNode merge = end.merge();
-                                boolean endsVisited = true;
-                                for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
-                                    if (!states.containsKey(forwardEnd)) {
-                                        endsVisited = false;
-                                        break;
-                                    }
-                                }
-                                if (endsVisited) {
-                                    blockQueue.addFirst(successor);
-                                }
-                            } else {
-                                assert successor.getPredecessors().size() == 1 : "invalid block schedule at " + successor.getBeginNode();
-                                current = successor;
-                                continue;
-                            }
+                            assert !states.containsKey(end);
+                            states.put(end, state);
                         }
+                    } else {
+                        assert successor.getPredecessors().size() == 1 : "invalid block schedule at " + successor.getBeginNode();
+                        current = successor;
+                        continue;
                     }
                 } else {
                     assert current.getSuccessors().size() > 1;
-                    for (int i = 0; i < current.getSuccessors().size(); i++) {
+                    for (int i = 1; i < current.getSuccessors().size(); i++) {
                         Block successor = current.getSuccessors().get(i);
                         blockQueue.addFirst(successor);
-                        states.put(successor.getBeginNode(), i == 0 ? state : closure.cloneState(state));
+                        states.put(successor.getBeginNode(), closure.cloneState(state));
                     }
+                    current = current.getSuccessors().get(0);
+                    continue;
                 }
             }
 
@@ -164,20 +173,9 @@
                 return states;
             } else {
                 current = blockQueue.removeFirst();
-                if (current.getPredecessors().size() == 1) {
-                    assert states.containsKey(current.getBeginNode());
-                    state = states.get(current.getBeginNode());
-                } else {
-                    assert current.getPredecessors().size() > 1;
-                    MergeNode merge = (MergeNode) current.getBeginNode();
-                    ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount());
-                    for (Block predecessor : current.getPredecessors()) {
-                        AbstractEndNode end = (AbstractEndNode) predecessor.getEndNode();
-                        mergedStates.add(states.get(end));
-                    }
-                    state = closure.merge(current, mergedStates);
-                    states.put(merge, state);
-                }
+                assert current.getPredecessorCount() == 1;
+                assert states.containsKey(current.getBeginNode());
+                state = states.remove(current.getBeginNode());
             }
         }
     }
diff -r 23f45bae453a -r e626b112aa3d graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java	Fri May 23 17:43:07 2014 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java	Fri May 23 17:47:15 2014 +0200
@@ -33,8 +33,13 @@
 
     public static class LoopInfo<StateT> {
 
-        public final Map<LoopEndNode, StateT> endStates = newNodeIdentityMap(4);
-        public final Map<LoopExitNode, StateT> exitStates = newNodeIdentityMap(2);
+        public final Map<LoopEndNode, StateT> endStates;
+        public final Map<LoopExitNode, StateT> exitStates;
+
+        public LoopInfo(int endCount, int exitCount) {
+            endStates = newNodeIdentityMap(endCount);
+            exitStates = newNodeIdentityMap(exitCount);
+        }
     }
 
     public abstract static class NodeIteratorClosure<StateT> {
@@ -64,7 +69,7 @@
     public static <StateT> LoopInfo<StateT> processLoop(NodeIteratorClosure<StateT> closure, LoopBeginNode loop, StateT initialState) {
         Map<FixedNode, StateT> blockEndStates = apply(closure, loop, initialState, loop);
 
-        LoopInfo<StateT> info = new LoopInfo<>();
+        LoopInfo<StateT> info = new LoopInfo<>(loop.loopEnds().count(), loop.loopExits().count());
         for (LoopEndNode end : loop.loopEnds()) {
             if (blockEndStates.containsKey(end)) {
                 info.endStates.put(end, blockEndStates.get(end));
@@ -119,11 +124,9 @@
                                     nodeQueue.add(entry.getKey());
                                 }
                             } else {
-                                assert !blockEndStates.containsKey(current);
-                                blockEndStates.put(current, state);
                                 boolean endsVisited = true;
                                 for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
-                                    if (!blockEndStates.containsKey(forwardEnd)) {
+                                    if (forwardEnd != current && !blockEndStates.containsKey(forwardEnd)) {
                                         endsVisited = false;
                                         break;
                                     }
@@ -132,13 +135,16 @@
                                     ArrayList<StateT> states = new ArrayList<>(merge.forwardEndCount());
                                     for (int i = 0; i < merge.forwardEndCount(); i++) {
                                         AbstractEndNode forwardEnd = merge.forwardEndAt(i);
-                                        assert blockEndStates.containsKey(forwardEnd);
-                                        StateT other = blockEndStates.get(forwardEnd);
+                                        assert forwardEnd == current || blockEndStates.containsKey(forwardEnd);
+                                        StateT other = forwardEnd == current ? state : blockEndStates.remove(forwardEnd);
                                         states.add(other);
                                     }
                                     state = closure.merge(merge, states);
                                     current = closure.continueIteration(state) ? merge : null;
                                     continue;
+                                } else {
+                                    assert !blockEndStates.containsKey(current);
+                                    blockEndStates.put(current, state);
                                 }
                             }
                         }
@@ -148,14 +154,15 @@
                             current = firstSuccessor;
                             continue;
                         } else {
-                            while (successors.hasNext()) {
+                            do {
                                 BeginNode successor = (BeginNode) successors.next();
                                 StateT successorState = closure.afterSplit(successor, state);
                                 if (closure.continueIteration(successorState)) {
                                     blockEndStates.put(successor, successorState);
                                     nodeQueue.add(successor);
                                 }
-                            }
+                            } while (successors.hasNext());
+
                             state = closure.afterSplit((BeginNode) firstSuccessor, state);
                             current = closure.continueIteration(state) ? firstSuccessor : null;
                             continue;
@@ -169,7 +176,8 @@
                 return blockEndStates;
             } else {
                 current = nodeQueue.removeFirst();
-                state = blockEndStates.get(current);
+                assert blockEndStates.containsKey(current);
+                state = blockEndStates.remove(current);
                 assert !(current instanceof MergeNode) && current instanceof BeginNode;
             }
         } while (true);