Mercurial > hg > truffle
changeset 15868:e626b112aa3d
consume less memory in ReentrantBlockIterator and ReentrantNodeIterator
| author | Lukas Stadler <lukas.stadler@oracle.com> |
|---|---|
| date | Fri, 23 May 2014 17:47:15 +0200 |
| parents | 23f45bae453a |
| children | 387b15da0f68 |
| files | graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java |
| diffstat | 2 files changed, 65 insertions(+), 59 deletions(-) [+] |
line wrap: on
line diff
--- 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()); } } }
--- 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);