Mercurial > hg > truffle
changeset 7892:7f3fc1210e8c
Merge.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Tue, 26 Feb 2013 20:07:29 +0100 |
| parents | b8f387456757 (current diff) 1474fe91323c (diff) |
| children | d81109e2d7be |
| files | |
| diffstat | 15 files changed, 890 insertions(+), 333 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java Tue Feb 26 20:07:29 2013 +0100 @@ -0,0 +1,218 @@ +/* + * Copyright (c) 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.test; + +import java.util.concurrent.*; + +import org.junit.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.nodes.util.*; +import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.schedule.*; + +/** + * In these test the FrameStates are explicitly cleared out, so that the scheduling of + * FloatingReadNodes depends solely on the scheduling algorithm. The FrameStates normally keep the + * FloatingReadNodes above a certain point, so that they (most of the time...) magically do the + * right thing. + * + * The scheduling shouldn't depend on FrameStates, which is tested by this class. + */ +public class MemoryScheduleTest extends GraphScheduleTest { + + private static enum TestMode { + WITH_FRAMESTATES, WITHOUT_FRAMESTATES + } + + public static class Container { + + public int a; + public int b; + public int c; + } + + private static final Container container = new Container(); + + public static int testSimpleSnippet() { + // in this test the read should be scheduled before the write + try { + return container.a; + } finally { + container.a = 15; + } + } + + @Test + public void testSimple() { + for (TestMode mode : TestMode.values()) { + SchedulePhase schedule = getFinalSchedule("testSimpleSnippet", mode); + assertReadAfterWrite(schedule, false); + } + } + + /** + * In this case the read should be scheduled in the first block. + */ + public static int testSplitSnippet1(int a) { + try { + return container.a; + } finally { + if (a < 0) { + container.a = 15; + } else { + container.b = 15; + } + } + } + + @Test + public void testSplit1() { + for (TestMode mode : TestMode.values()) { + SchedulePhase schedule = getFinalSchedule("testSplitSnippet1", mode); + assertReadWithinStartBlock(schedule, true); + } + } + + /** + * Here the read should float to the end. + */ + public static int testSplit2Snippet(int a) { + try { + return container.a; + } finally { + if (a < 0) { + container.c = 15; + } else { + container.b = 15; + } + } + } + + @Test + public void testSplit2() { + SchedulePhase schedule = getFinalSchedule("testSplit2Snippet", TestMode.WITHOUT_FRAMESTATES); + assertReadWithinStartBlock(schedule, false); + } + + /** + * Here the read should not float to the end. + */ + public static int testLoop1Snippet(int a, int b) { + try { + return container.a; + } finally { + for (int i = 0; i < a; i++) { + if (b < 0) { + container.b = 10; + } else { + container.a = 15; + } + } + } + } + + @Test + public void testLoop1() { + SchedulePhase schedule = getFinalSchedule("testLoop1Snippet", TestMode.WITHOUT_FRAMESTATES); + assertEquals(7, schedule.getCFG().getBlocks().length); + assertReadWithinStartBlock(schedule, true); + } + + /** + * Here the read should float to the end. + */ + public static int testLoop2Snippet(int a, int b) { + try { + return container.a; + } finally { + for (int i = 0; i < a; i++) { + if (b < 0) { + container.b = 10; + } else { + container.c = 15; + } + } + } + } + + @Test + public void testLoop2() { + SchedulePhase schedule = getFinalSchedule("testLoop2Snippet", TestMode.WITHOUT_FRAMESTATES); + assertEquals(7, schedule.getCFG().getBlocks().length); + assertReadWithinStartBlock(schedule, false); + } + + private void assertReadAfterWrite(SchedulePhase schedule, boolean readAfterWrite) { + boolean writeEncountered = false; + assertEquals(1, schedule.getCFG().getBlocks().length); + for (Node node : schedule.getBlockToNodesMap().get(schedule.getCFG().getStartBlock())) { + if (node instanceof WriteNode) { + writeEncountered = true; + } else if (node instanceof FloatingReadNode) { + assertEquals(readAfterWrite, writeEncountered); + } + } + } + + private void assertReadWithinStartBlock(SchedulePhase schedule, boolean withinStartBlock) { + boolean readEncountered = false; + for (Node node : schedule.getBlockToNodesMap().get(schedule.getCFG().getStartBlock())) { + if (node instanceof FloatingReadNode) { + readEncountered = true; + } + } + assertEquals(withinStartBlock, readEncountered); + } + + private SchedulePhase getFinalSchedule(final String snippet, final TestMode mode) { + return Debug.scope("FloatingReadTest", new DebugDumpScope(snippet), new Callable<SchedulePhase>() { + + @Override + public SchedulePhase call() throws Exception { + StructuredGraph graph = parse(snippet); + if (mode == TestMode.WITHOUT_FRAMESTATES) { + for (Node node : graph.getNodes()) { + if (node instanceof StateSplit) { + FrameState stateAfter = ((StateSplit) node).stateAfter(); + if (stateAfter != null) { + ((StateSplit) node).setStateAfter(null); + GraphUtil.killWithUnusedFloatingInputs(stateAfter); + } + } + } + } + new LoweringPhase(null, runtime(), new Assumptions(false)).apply(graph); + new FloatingReadPhase().apply(graph); + + SchedulePhase schedule = new SchedulePhase(); + schedule.apply(graph); + return schedule; + } + }); + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Feb 26 20:07:29 2013 +0100 @@ -117,7 +117,7 @@ new InliningPhase(runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph); new DeadCodeEliminationPhase().apply(graph); - if (GraalOptions.CheckCastElimination && GraalOptions.OptCanonicalizer) { + if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(runtime, assumptions).apply(graph); new IterativeConditionalEliminationPhase(runtime, assumptions).apply(graph); } @@ -181,7 +181,7 @@ new EliminatePartiallyRedundantGuardsPhase(false, true).apply(graph); } - if (GraalOptions.CheckCastElimination && GraalOptions.OptCanonicalizer) { + if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) { new IterativeConditionalEliminationPhase(runtime, assumptions).apply(graph); }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java Tue Feb 26 20:07:29 2013 +0100 @@ -72,6 +72,10 @@ assert !isNew(node) : "this node was added to the graph after creating the node map : " + node; } + public void clear() { + Arrays.fill(values, null); + } + public Iterable<Entry<Node, T>> entries() { return new Iterable<Entry<Node, T>>() {
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/OnStackReplacementPhase.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/OnStackReplacementPhase.java Tue Feb 26 20:07:29 2013 +0100 @@ -26,11 +26,11 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.code.RuntimeCallTarget.*; -import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.*; import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.java.*; import com.oracle.graal.loop.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; @@ -131,12 +131,13 @@ start.setStateAfter(null); GraphUtil.killWithUnusedFloatingInputs(oldStartState); + // mirroring the calculations in c1_GraphBuilder.cpp (setup_osr_entry_block) int localsOffset = (graph.method().getMaxLocals() - 1) * 8; for (int i = 0; i < osrState.localsSize(); i++) { ValueNode value = osrState.localAt(i); if (value != null) { ValueProxyNode proxy = (ValueProxyNode) value; - int size = (value.kind() == Kind.Long || value.kind() == Kind.Double) ? 2 : 1; + int size = FrameStateBuilder.stackSlots(value.kind()); int offset = localsOffset - (i + size - 1) * 8; UnsafeLoadNode load = graph.add(new UnsafeLoadNode(buffer, offset, ConstantNode.forInt(0, graph), value.kind())); OSREntryProxyNode newProxy = graph.add(new OSREntryProxyNode(load, migrationEnd));
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/ObjectCloneNode.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/ObjectCloneNode.java Tue Feb 26 20:07:29 2013 +0100 @@ -86,7 +86,7 @@ } private static ResolvedJavaType getConcreteType(ObjectStamp stamp, Assumptions assumptions) { - if (stamp.isExactType()) { + if (stamp.isExactType() || stamp.type() == null) { return stamp.type(); } else { ResolvedJavaType type = stamp.type().findUniqueConcreteSubtype();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Tue Feb 26 20:07:29 2013 +0100 @@ -108,9 +108,38 @@ return loops; } + public void clearNodeToBlock() { + nodeToBlock.clear(); + for (Block block : reversePostOrder) { + identifyBlock(block, block.beginNode); + } + } + protected static final int BLOCK_ID_INITIAL = -1; protected static final int BLOCK_ID_VISITED = -2; + private void identifyBlock(Block block, BeginNode begin) { + block.beginNode = begin; + Node cur = begin; + Node last; + do { + assert !cur.isDeleted(); + + assert nodeToBlock.get(cur) == null; + nodeToBlock.set(cur, block); + if (cur instanceof MergeNode) { + for (PhiNode phi : ((MergeNode) cur).phis()) { + nodeToBlock.set(phi, block); + } + } + + last = cur; + cur = cur.successors().first(); + } while (cur != null && !(cur instanceof BeginNode)); + + block.endNode = (FixedNode) last; + } + private void identifyBlocks() { // Find all block headers int numBlocks = 0; @@ -118,26 +147,7 @@ if (node instanceof BeginNode) { Block block = new Block(); numBlocks++; - - block.beginNode = (BeginNode) node; - Node cur = node; - Node last; - do { - assert !cur.isDeleted(); - - assert nodeToBlock.get(cur) == null; - nodeToBlock.set(cur, block); - if (cur instanceof MergeNode) { - for (PhiNode phi : ((MergeNode) cur).phis()) { - nodeToBlock.set(phi, block); - } - } - - last = cur; - cur = cur.successors().first(); - } while (cur != null && !(cur instanceof BeginNode)); - - block.endNode = (FixedNode) last; + identifyBlock(block, (BeginNode) node); } }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CullFrameStatesPhase.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CullFrameStatesPhase.java Tue Feb 26 20:07:29 2013 +0100 @@ -37,11 +37,14 @@ public class CullFrameStatesPhase extends Phase { private static final DebugMetric metricFrameStatesCulled = Debug.metric("FrameStatesCulled"); + private static final DebugMetric metricNodesRemoved = Debug.metric("NodesRemoved"); private static final DebugMetric metricMergesTraversed = Debug.metric("MergesTraversed"); @Override protected void run(StructuredGraph graph) { + int initialNodes = graph.getNodeCount(); new CullFrameStates(graph.start(), new State(null)).apply(); + metricNodesRemoved.add(initialNodes - graph.getNodeCount()); } public static class State implements MergeableState<State> {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java Tue Feb 26 20:07:29 2013 +0100 @@ -29,262 +29,208 @@ import com.oracle.graal.nodes.extended.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.graph.*; +import com.oracle.graal.phases.graph.ReentrantNodeIterator.LoopInfo; +import com.oracle.graal.phases.graph.ReentrantNodeIterator.NodeIteratorClosure; public class FloatingReadPhase extends Phase { - private IdentityHashMap<LoopBeginNode, List<MemoryMap>> loopEndStatesMap; - - private static class LoopState { - - public LoopBeginNode loopBegin; - public MemoryMap state; - public IdentityHashMap<PhiNode, Object> loopPhiLocations = new IdentityHashMap<>(); - public ValueNode loopEntryAnyLocation; - - public LoopState(LoopBeginNode loopBegin, MemoryMap state, ValueNode loopEntryAnyLocation) { - this.loopBegin = loopBegin; - this.state = state; - this.loopEntryAnyLocation = loopEntryAnyLocation; - } - - @Override - public String toString() { - return "State@" + loopBegin; - } - } - - private class MemoryMap implements MergeableState<MemoryMap> { + private static class MemoryMap { private IdentityHashMap<Object, ValueNode> lastMemorySnapshot; - private LinkedList<LoopState> loops; public MemoryMap(MemoryMap memoryMap) { lastMemorySnapshot = new IdentityHashMap<>(memoryMap.lastMemorySnapshot); - loops = new LinkedList<>(memoryMap.loops); + } + + public MemoryMap(StartNode start) { + this(); + lastMemorySnapshot.put(LocationNode.ANY_LOCATION, start); } public MemoryMap() { lastMemorySnapshot = new IdentityHashMap<>(); - loops = new LinkedList<>(); + } + + private ValueNode getLastLocationAccess(Object locationIdentity) { + ValueNode lastLocationAccess; + if (locationIdentity == LocationNode.FINAL_LOCATION) { + return null; + } else { + lastLocationAccess = lastMemorySnapshot.get(locationIdentity); + if (lastLocationAccess == null) { + lastLocationAccess = lastMemorySnapshot.get(LocationNode.ANY_LOCATION); + assert lastLocationAccess != null; + } + return lastLocationAccess; + } } @Override public String toString() { - return "Map=" + lastMemorySnapshot.toString() + " Loops=" + loops.toString(); - } - - @SuppressWarnings("unchecked") - @Override - public boolean merge(MergeNode merge, List<MemoryMap> withStates) { - if (withStates.size() == 0) { - return true; - } - - int minLoops = loops.size(); - for (MemoryMap other : withStates) { - int otherLoops = other.loops.size(); - if (otherLoops < minLoops) { - minLoops = otherLoops; - } - } - while (loops.size() > minLoops) { - loops.pop(); - } - for (MemoryMap other : withStates) { - while (other.loops.size() > minLoops) { - other.loops.pop(); - } - } - - Set<Object> keys = new HashSet<>(); - for (Object key : lastMemorySnapshot.keySet()) { - keys.add(key); - } - for (MemoryMap other : withStates) { - assert other.loops.size() == loops.size(); - assert other.loops.size() < 1 || other.loops.peek().loopBegin == loops.peek().loopBegin; - for (Object key : other.lastMemorySnapshot.keySet()) { - keys.add(key); - } - } - IdentityHashMap<Object, ValueNode> newMemorySnapshot = (IdentityHashMap<Object, ValueNode>) lastMemorySnapshot.clone(); - - for (Object key : keys) { - ValueNode merged = lastMemorySnapshot.get(key); - if (merged == null) { - merged = lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } - int mergedStatesCount = 1; - boolean isPhi = false; - for (MemoryMap other : withStates) { - ValueNode otherValue = other.lastMemorySnapshot.get(key); - if (otherValue == null) { - otherValue = other.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } - if (isPhi) { - ((PhiNode) merged).addInput(otherValue); - } else if (merged != otherValue) { - PhiNode phi = merge.graph().add(new PhiNode(PhiType.Memory, merge)); - for (int j = 0; j < mergedStatesCount; j++) { - phi.addInput(merged); - } - phi.addInput(otherValue); - merged = phi; - isPhi = true; - newMemorySnapshot.put(key, phi); - } - mergedStatesCount++; - } - } - - lastMemorySnapshot = newMemorySnapshot; - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - LoopState loopState = new LoopState(loopBegin, this, lastMemorySnapshot.get(LocationNode.ANY_LOCATION)); - for (Map.Entry<Object, ValueNode> entry : lastMemorySnapshot.entrySet()) { - PhiNode phi = loopBegin.graph().add(new PhiNode(PhiType.Memory, loopBegin)); - phi.addInput(entry.getValue()); - entry.setValue(phi); - loopState.loopPhiLocations.put(phi, entry.getKey()); - } - loops.push(loopState); - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List<MemoryMap> loopEndStates) { - loopEndStatesMap.put(loopBegin, loopEndStates); - tryFinishLoopPhis(this, loopBegin); - } - - @Override - public void afterSplit(BeginNode node) { - // nothing - } - - @Override - public MemoryMap clone() { - return new MemoryMap(this); + return "Map=" + lastMemorySnapshot.toString(); } } + private final Map<LoopBeginNode, Set<Object>> modifiedInLoops = new IdentityHashMap<>(); + @Override protected void run(StructuredGraph graph) { - loopEndStatesMap = new IdentityHashMap<>(); - new PostOrderNodeIterator<MemoryMap>(graph.start(), new MemoryMap()) { - - @Override - protected void node(FixedNode node) { - processNode(node, state); - } - }.apply(); - } - - private void processNode(FixedNode node, MemoryMap state) { - if (node instanceof ReadNode) { - processRead((ReadNode) node, state); - } else if (node instanceof MemoryCheckpoint) { - processCheckpoint((MemoryCheckpoint) node, state); - } else if (node instanceof LoopExitNode) { - processLoopExit((LoopExitNode) node, state); - } + ReentrantNodeIterator.apply(new CollectMemoryCheckpointsClosure(), graph.start(), new HashSet<>(), null); + ReentrantNodeIterator.apply(new FloatingReadClosure(), graph.start(), new MemoryMap(graph.start()), null); } - private static void processCheckpoint(MemoryCheckpoint checkpoint, MemoryMap state) { - if (checkpoint.getLocationIdentity() == LocationNode.ANY_LOCATION) { - for (Map.Entry<Object, ValueNode> entry : state.lastMemorySnapshot.entrySet()) { - entry.setValue((ValueNode) checkpoint); + private class CollectMemoryCheckpointsClosure extends NodeIteratorClosure<Set<Object>> { + + @Override + protected void processNode(FixedNode node, Set<Object> currentState) { + if (node instanceof MemoryCheckpoint) { + currentState.add(((MemoryCheckpoint) node).getLocationIdentity()); } - state.loops.clear(); } - state.lastMemorySnapshot.put(checkpoint.getLocationIdentity(), (ValueNode) checkpoint); - } + + @Override + protected Set<Object> merge(MergeNode merge, List<Set<Object>> states) { + Set<Object> result = new HashSet<>(); + for (Set<Object> other : states) { + result.addAll(other); + } + return result; + } - private void processRead(ReadNode readNode, MemoryMap state) { - StructuredGraph graph = (StructuredGraph) readNode.graph(); - assert readNode.getNullCheck() == false; - Object locationIdentity = readNode.location().locationIdentity(); - if (locationIdentity != LocationNode.UNKNOWN_LOCATION) { - ValueNode lastLocationAccess = getLastLocationAccessForRead(state, locationIdentity); - FloatingReadNode floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), lastLocationAccess, readNode.stamp(), readNode.dependencies())); - floatingRead.setNullCheck(readNode.getNullCheck()); - ValueAnchorNode anchor = null; - for (GuardNode guard : readNode.dependencies().filter(GuardNode.class)) { - if (anchor == null) { - anchor = graph.add(new ValueAnchorNode()); - } - anchor.addAnchoredNode(guard); + @Override + protected Set<Object> afterSplit(BeginNode node, Set<Object> oldState) { + return new HashSet<>(oldState); + } + + @Override + protected Map<LoopExitNode, Set<Object>> processLoop(LoopBeginNode loop, Set<Object> initialState) { + LoopInfo<Set<Object>> loopInfo = ReentrantNodeIterator.processLoop(this, loop, new HashSet<>()); + Set<Object> modifiedLocations = new HashSet<>(); + for (Set<Object> end : loopInfo.endStates.values()) { + modifiedLocations.addAll(end); } - if (anchor != null) { - graph.addAfterFixed(readNode, anchor); + for (Set<Object> exit : loopInfo.exitStates.values()) { + exit.addAll(modifiedLocations); + exit.addAll(initialState); } - graph.replaceFixedWithFloating(readNode, floatingRead); + assert !modifiedLocations.contains(LocationNode.FINAL_LOCATION); + modifiedInLoops.put(loop, modifiedLocations); + return loopInfo.exitStates; } + } - private ValueNode getLastLocationAccessForRead(MemoryMap state, Object locationIdentity) { - ValueNode lastLocationAccess; - if (locationIdentity == LocationNode.FINAL_LOCATION) { - lastLocationAccess = null; - } else { - lastLocationAccess = state.lastMemorySnapshot.get(locationIdentity); - if (lastLocationAccess == null) { - LoopState lastLoop = state.loops.peek(); - if (lastLoop == null) { - lastLocationAccess = state.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } else { - ValueNode phiInit; - if (state.loops.size() > 1) { - phiInit = getLastLocationAccessForRead(state.loops.get(1).state, locationIdentity); - } else { - phiInit = lastLoop.loopEntryAnyLocation; + private class FloatingReadClosure extends NodeIteratorClosure<MemoryMap> { + + @Override + protected void processNode(FixedNode node, MemoryMap state) { + if (node instanceof ReadNode) { + processRead((ReadNode) node, state); + } else if (node instanceof MemoryCheckpoint) { + processCheckpoint((MemoryCheckpoint) node, state); + } + } + + private void processCheckpoint(MemoryCheckpoint checkpoint, MemoryMap state) { + if (checkpoint.getLocationIdentity() == LocationNode.ANY_LOCATION) { + state.lastMemorySnapshot.clear(); + } + state.lastMemorySnapshot.put(checkpoint.getLocationIdentity(), (ValueNode) checkpoint); + } + + private void processRead(ReadNode readNode, MemoryMap state) { + StructuredGraph graph = (StructuredGraph) readNode.graph(); + assert readNode.getNullCheck() == false; + Object locationIdentity = readNode.location().locationIdentity(); + if (locationIdentity != LocationNode.UNKNOWN_LOCATION) { + ValueNode lastLocationAccess = state.getLastLocationAccess(locationIdentity); + FloatingReadNode floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), lastLocationAccess, readNode.stamp(), readNode.dependencies())); + floatingRead.setNullCheck(readNode.getNullCheck()); + ValueAnchorNode anchor = null; + for (GuardNode guard : readNode.dependencies().filter(GuardNode.class)) { + if (anchor == null) { + anchor = graph.add(new ValueAnchorNode()); + graph.addAfterFixed(readNode, anchor); } - PhiNode phi = lastLoop.loopBegin.graph().add(new PhiNode(PhiType.Memory, lastLoop.loopBegin)); - phi.addInput(phiInit); - lastLoop.state.lastMemorySnapshot.put(locationIdentity, phi); - lastLoop.loopPhiLocations.put(phi, locationIdentity); - tryFinishLoopPhis(lastLoop.state, lastLoop.loopBegin); - lastLocationAccess = phi; + anchor.addAnchoredNode(guard); } - state.lastMemorySnapshot.put(locationIdentity, lastLocationAccess); + graph.replaceFixedWithFloating(readNode, floatingRead); } } - return lastLocationAccess; - } + + @Override + protected MemoryMap merge(MergeNode merge, List<MemoryMap> states) { + MemoryMap newState = new MemoryMap(); - private static void processLoopExit(LoopExitNode exit, MemoryMap state) { - for (Map.Entry<Object, ValueNode> entry : state.lastMemorySnapshot.entrySet()) { - entry.setValue(exit.graph().unique(new ValueProxyNode(entry.getValue(), exit, PhiType.Memory))); - } - if (!state.loops.isEmpty()) { - state.loops.pop(); - } - } + Set<Object> keys = new HashSet<>(); + for (MemoryMap other : states) { + keys.addAll(other.lastMemorySnapshot.keySet()); + } + assert !keys.contains(LocationNode.FINAL_LOCATION); - private void tryFinishLoopPhis(MemoryMap loopMemory, LoopBeginNode loopBegin) { - List<MemoryMap> loopEndStates = loopEndStatesMap.get(loopBegin); - if (loopEndStates == null) { - return; - } - LoopState loopState = loopMemory.loops.get(0); - int i = 0; - while (loopState.loopBegin != loopBegin) { - loopState = loopMemory.loops.get(++i); + for (Object key : keys) { + int mergedStatesCount = 0; + boolean isPhi = false; + ValueNode merged = null; + for (MemoryMap state : states) { + ValueNode last = state.getLastLocationAccess(key); + if (isPhi) { + ((PhiNode) merged).addInput(last); + } else { + if (merged == last) { + // nothing to do + } else if (merged == null) { + merged = last; + } else { + PhiNode phi = merge.graph().add(new PhiNode(PhiType.Memory, merge)); + for (int j = 0; j < mergedStatesCount; j++) { + phi.addInput(merged); + } + phi.addInput(last); + merged = phi; + isPhi = true; + } + } + mergedStatesCount++; + } + newState.lastMemorySnapshot.put(key, merged); + } + return newState; } - for (PhiNode phi : loopBegin.phis()) { - if (phi.type() == PhiType.Memory && phi.valueCount() == 1) { - Object location = loopState.loopPhiLocations.get(phi); - assert location != null : "unknown location for " + phi; - for (MemoryMap endState : loopEndStates) { - ValueNode otherNode = endState.lastMemorySnapshot.get(location); - if (otherNode == null) { - otherNode = endState.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } - phi.addInput(otherNode); + + @Override + protected MemoryMap afterSplit(BeginNode node, MemoryMap oldState) { + return new MemoryMap(oldState); + } + + @Override + protected Map<LoopExitNode, MemoryMap> processLoop(LoopBeginNode loop, MemoryMap initialState) { + Set<Object> modifiedLocations = modifiedInLoops.get(loop); + if (modifiedLocations.contains(LocationNode.ANY_LOCATION)) { + // create phis for all locations if ANY is modified in the loop + modifiedLocations = new HashSet<>(modifiedLocations); + modifiedLocations.addAll(initialState.lastMemorySnapshot.keySet()); + } + + Map<Object, PhiNode> phis = new HashMap<>(); + for (Object location : modifiedLocations) { + PhiNode phi = loop.graph().add(new PhiNode(PhiType.Memory, loop)); + phi.addInput(initialState.getLastLocationAccess(location)); + phis.put(location, phi); + initialState.lastMemorySnapshot.put(location, phi); + } + + LoopInfo<MemoryMap> loopInfo = ReentrantNodeIterator.processLoop(this, loop, initialState); + + for (Map.Entry<LoopEndNode, MemoryMap> entry : loopInfo.endStates.entrySet()) { + int endIndex = loop.phiPredecessorIndex(entry.getKey()); + for (Map.Entry<Object, PhiNode> phiEntry : phis.entrySet()) { + Object key = phiEntry.getKey(); + PhiNode phi = phiEntry.getValue(); + phi.initializeValueAt(endIndex, entry.getValue().getLastLocationAccess(key)); } } + return loopInfo.exitStates; } } }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Tue Feb 26 20:07:29 2013 +0100 @@ -24,6 +24,7 @@ import java.lang.reflect.*; import java.util.*; +import java.util.concurrent.*; import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; @@ -127,26 +128,32 @@ return cachedGraph; } } - StructuredGraph newGraph = new StructuredGraph(method); - if (plan != null) { - plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); - } - assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; + final StructuredGraph newGraph = new StructuredGraph(method); + return Debug.scope("InlineGraph", newGraph, new Callable<StructuredGraph>() { + + @Override + public StructuredGraph call() throws Exception { + if (plan != null) { + plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); + } + assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; - if (GraalOptions.ProbabilityAnalysis) { - new DeadCodeEliminationPhase().apply(newGraph); - new ComputeProbabilityPhase().apply(newGraph); - } - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(runtime, assumptions).apply(newGraph); - } - if (GraalOptions.CullFrameStates) { - new CullFrameStatesPhase().apply(newGraph); - } - if (GraalOptions.CacheGraphs && cache != null) { - cache.put(newGraph); - } - return newGraph; + if (GraalOptions.ProbabilityAnalysis) { + new DeadCodeEliminationPhase().apply(newGraph); + new ComputeProbabilityPhase().apply(newGraph); + } + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(runtime, assumptions).apply(newGraph); + } + if (GraalOptions.CullFrameStates) { + new CullFrameStatesPhase().apply(newGraph); + } + if (GraalOptions.CacheGraphs && cache != null) { + cache.put(newGraph); + } + return newGraph; + } + }); } private interface InliningDecision {
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Tue Feb 26 20:07:29 2013 +0100 @@ -150,7 +150,7 @@ public static boolean ExitVMOnException = true; // Code generator settings - public static boolean CheckCastElimination = true; + public static boolean ConditionalElimination = true; public static boolean CullFrameStates = ____; public static boolean UseProfilingInformation = true; static boolean RemoveNeverExecutedCode = true; @@ -168,6 +168,8 @@ public static boolean CanOmitFrame = true; public static int SafepointPollOffset = 256; + public static boolean MemoryAwareScheduling = true; + // Translating tableswitch instructions public static int MinimumJumpTableSize = 5; public static int RangeTestsSwitchDensity = 5;
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Tue Feb 26 20:07:29 2013 +0100 @@ -29,54 +29,49 @@ public final class ReentrantBlockIterator { - public abstract static class MergeableBlockState<T> { + public static class LoopInfo<StateT> { - public abstract T cloneState(); + public final List<StateT> endStates = new ArrayList<>(); + public final List<StateT> exitStates = new ArrayList<>(); } - public static class LoopInfo<T extends MergeableBlockState<T>> { + public abstract static class BlockIteratorClosure<StateT> { - public final List<T> endStates = new ArrayList<>(); - public final List<T> exitStates = new ArrayList<>(); - } - - public abstract static class BlockIteratorClosure<T extends MergeableBlockState<T>> { + protected abstract void processBlock(Block block, StateT currentState); - protected abstract void processBlock(Block block, T currentState); - - protected abstract T merge(MergeNode merge, List<T> states); + protected abstract StateT merge(MergeNode merge, List<StateT> states); - protected abstract T afterSplit(FixedNode node, T oldState); + protected abstract StateT afterSplit(FixedNode node, StateT oldState); - protected abstract List<T> processLoop(Loop loop, T initialState); + protected abstract List<StateT> processLoop(Loop loop, StateT initialState); } private ReentrantBlockIterator() { // no instances allowed } - public static <T extends MergeableBlockState<T>> LoopInfo<T> processLoop(BlockIteratorClosure<T> closure, Loop loop, T initialState) { - IdentityHashMap<FixedNode, T> blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks)); + public static <StateT> LoopInfo<StateT> processLoop(BlockIteratorClosure<StateT> closure, Loop loop, StateT initialState) { + IdentityHashMap<FixedNode, StateT> blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks)); - LoopInfo<T> info = new LoopInfo<>(); + LoopInfo<StateT> info = new LoopInfo<>(); List<Block> predecessors = loop.header.getPredecessors(); for (int i = 1; i < predecessors.size(); i++) { info.endStates.add(blockEndStates.get(predecessors.get(i).getEndNode())); } for (Block loopExit : loop.exits) { assert loopExit.getPredecessorCount() == 1; - T exitState = blockEndStates.get(loopExit.getFirstPredecessor().getEndNode()); + StateT exitState = blockEndStates.get(loopExit.getFirstPredecessor().getEndNode()); assert exitState != null; info.exitStates.add(exitState); } return info; } - public static <T extends MergeableBlockState<T>> IdentityHashMap<FixedNode, T> apply(BlockIteratorClosure<T> closure, Block start, T initialState, Set<Block> boundary) { + public static <StateT> IdentityHashMap<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Set<Block> boundary) { Deque<Block> blockQueue = new ArrayDeque<>(); - IdentityHashMap<FixedNode, T> blockEndStates = new IdentityHashMap<>(); + IdentityHashMap<FixedNode, StateT> blockEndStates = new IdentityHashMap<>(); - T state = initialState; + StateT state = initialState; Block current = start; do { @@ -98,7 +93,7 @@ LoopBeginNode loopBegin = loop.loopBegin(); assert successor.getBeginNode() == loopBegin; - List<T> exitStates = closure.processLoop(loop, state); + List<StateT> exitStates = closure.processLoop(loop, state); int i = 0; assert loop.exits.size() == exitStates.size(); @@ -123,8 +118,8 @@ blockEndStates.put(end, state); MergeNode merge = end.merge(); boolean endsVisited = true; - for (int i = 0; i < merge.forwardEndCount(); i++) { - if (!blockEndStates.containsKey(merge.forwardEndAt(i))) { + for (EndNode forwardEnd : merge.forwardEnds()) { + if (!blockEndStates.containsKey(forwardEnd)) { endsVisited = false; break; } @@ -157,9 +152,9 @@ current = blockQueue.removeFirst(); if (current.getPredecessors().size() > 1) { MergeNode merge = (MergeNode) current.getBeginNode(); - ArrayList<T> states = new ArrayList<>(merge.forwardEndCount()); + ArrayList<StateT> states = new ArrayList<>(merge.forwardEndCount()); for (int i = 0; i < merge.forwardEndCount(); i++) { - T other = blockEndStates.get(merge.forwardEndAt(i)); + StateT other = blockEndStates.get(merge.forwardEndAt(i)); assert other != null; states.add(other); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java Tue Feb 26 20:07:29 2013 +0100 @@ -0,0 +1,158 @@ +/* + * 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.phases.graph; + +import java.util.*; + +import com.oracle.graal.graph.NodeClass.NodeClassIterator; +import com.oracle.graal.nodes.*; + +public final class ReentrantNodeIterator { + + public static class LoopInfo<StateT> { + + public final Map<LoopEndNode, StateT> endStates = new IdentityHashMap<>(4); + public final Map<LoopExitNode, StateT> exitStates = new IdentityHashMap<>(2); + } + + public abstract static class NodeIteratorClosure<StateT> { + + protected abstract void processNode(FixedNode node, StateT currentState); + + protected abstract StateT merge(MergeNode merge, List<StateT> states); + + protected abstract StateT afterSplit(BeginNode node, StateT oldState); + + protected abstract Map<LoopExitNode, StateT> processLoop(LoopBeginNode loop, StateT initialState); + } + + private ReentrantNodeIterator() { + // no instances allowed + } + + public static <StateT> LoopInfo<StateT> processLoop(NodeIteratorClosure<StateT> closure, LoopBeginNode loop, StateT initialState) { + HashSet<FixedNode> boundary = new HashSet<>(); + for (LoopExitNode exit : loop.loopExits()) { + boundary.add(exit); + } + Map<FixedNode, StateT> blockEndStates = apply(closure, loop, initialState, boundary); + + LoopInfo<StateT> info = new LoopInfo<>(); + for (LoopEndNode end : loop.loopEnds()) { + assert blockEndStates.containsKey(end) : "no end state for " + end; + info.endStates.put(end, blockEndStates.get(end)); + } + for (LoopExitNode exit : loop.loopExits()) { + assert blockEndStates.containsKey(exit) : "no exit state for " + exit; + info.exitStates.put(exit, blockEndStates.get(exit)); + } + return info; + } + + public static <StateT> Map<FixedNode, StateT> apply(NodeIteratorClosure<StateT> closure, FixedNode start, StateT initialState, Set<FixedNode> boundary) { + Deque<BeginNode> nodeQueue = new ArrayDeque<>(); + IdentityHashMap<FixedNode, StateT> blockEndStates = new IdentityHashMap<>(); + + StateT state = initialState; + FixedNode current = start; + do { + while (current instanceof FixedWithNextNode) { + if (boundary != null && boundary.contains(current)) { + blockEndStates.put(current, state); + current = null; + } else { + FixedNode next = ((FixedWithNextNode) current).next(); + closure.processNode(current, state); + current = next; + } + } + + if (current != null) { + closure.processNode(current, state); + + NodeClassIterator successors = current.successors().iterator(); + if (!successors.hasNext()) { + if (current instanceof LoopEndNode) { + blockEndStates.put(current, state); + } else if (current instanceof EndNode) { + // add the end node and see if the merge is ready for processing + MergeNode merge = ((EndNode) current).merge(); + if (merge instanceof LoopBeginNode) { + Map<LoopExitNode, StateT> loopExitState = closure.processLoop((LoopBeginNode) merge, state); + for (Map.Entry<LoopExitNode, StateT> entry : loopExitState.entrySet()) { + blockEndStates.put(entry.getKey(), entry.getValue()); + nodeQueue.add(entry.getKey()); + } + } else { + assert !blockEndStates.containsKey(current); + blockEndStates.put(current, state); + boolean endsVisited = true; + for (EndNode forwardEnd : merge.forwardEnds()) { + if (!blockEndStates.containsKey(forwardEnd)) { + endsVisited = false; + break; + } + } + if (endsVisited) { + ArrayList<StateT> states = new ArrayList<>(merge.forwardEndCount()); + for (int i = 0; i < merge.forwardEndCount(); i++) { + EndNode forwardEnd = merge.forwardEndAt(i); + assert blockEndStates.containsKey(forwardEnd); + StateT other = blockEndStates.get(forwardEnd); + states.add(other); + } + state = closure.merge(merge, states); + current = merge; + continue; + } + } + } + } else { + FixedNode firstSuccessor = (FixedNode) successors.next(); + if (!successors.hasNext()) { + current = firstSuccessor; + continue; + } else { + while (successors.hasNext()) { + BeginNode successor = (BeginNode) successors.next(); + blockEndStates.put(successor, closure.afterSplit(successor, state)); + nodeQueue.add(successor); + } + state = closure.afterSplit((BeginNode) firstSuccessor, state); + current = firstSuccessor; + continue; + } + } + } + + // get next queued block + if (nodeQueue.isEmpty()) { + return blockEndStates; + } else { + current = nodeQueue.removeFirst(); + state = blockEndStates.get(current); + assert !(current instanceof MergeNode) && current instanceof BeginNode; + } + } while (true); + } +}
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Tue Feb 26 20:07:29 2013 +0100 @@ -28,12 +28,102 @@ import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.virtual.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.graph.*; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo; -public class SchedulePhase extends Phase { +public final class SchedulePhase extends Phase { + + public static enum SchedulingStrategy { + EARLIEST, LATEST, LATEST_OUT_OF_LOOPS + } + + /** + * This closure iterates over all nodes of a scheduled graph (it expects a + * {@link SchedulingStrategy#EARLIEST} schedule) and keeps a list of "actuve" reads. Whenever it + * encounters a read, it adds it to the active reads. Whenever it encounters a memory + * checkpoint, it adds all reads that need to be committed before this checkpoint to the + * "phantom" usages and inputs, so that the read is scheduled before the checkpoint afterwards. + * + * At merges, the intersection of all sets of active reads is calculated. A read that was + * committed within one predecessor branch cannot be scheduled after the merge anyway. + * + * Similarly for loops, all reads that are killed somewhere within the loop are removed from the + * exits' active reads, since they cannot be scheduled after the exit anyway. + */ + private class MemoryScheduleClosure extends BlockIteratorClosure<HashSet<FloatingReadNode>> { + + @Override + protected void processBlock(Block block, HashSet<FloatingReadNode> currentState) { + for (Node node : getBlockToNodesMap().get(block)) { + if (node instanceof FloatingReadNode) { + currentState.add((FloatingReadNode) node); + } else if (node instanceof MemoryCheckpoint) { + Object identity = ((MemoryCheckpoint) node).getLocationIdentity(); + for (Iterator<FloatingReadNode> iter = currentState.iterator(); iter.hasNext();) { + FloatingReadNode read = iter.next(); + FixedNode fixed = (FixedNode) node; + if (identity == LocationNode.ANY_LOCATION || read.location().locationIdentity() == identity) { + addPhantomReference(read, fixed); + } + } + } + } + } + + public void addPhantomReference(FloatingReadNode read, FixedNode fixed) { + List<FixedNode> usageList = phantomUsages.get(read); + if (usageList == null) { + phantomUsages.put(read, usageList = new ArrayList<>()); + } + usageList.add(fixed); + List<FloatingNode> inputList = phantomInputs.get(fixed); + if (inputList == null) { + phantomInputs.put(fixed, inputList = new ArrayList<>()); + } + inputList.add(read); + } + + @Override + protected HashSet<FloatingReadNode> merge(MergeNode merge, List<HashSet<FloatingReadNode>> states) { + HashSet<FloatingReadNode> state = new HashSet<>(states.get(0)); + for (int i = 1; i < states.size(); i++) { + state.retainAll(states.get(i)); + } + return state; + } + + @Override + protected HashSet<FloatingReadNode> afterSplit(FixedNode node, HashSet<FloatingReadNode> oldState) { + return new HashSet<>(oldState); + } + + @Override + protected List<HashSet<FloatingReadNode>> processLoop(Loop loop, HashSet<FloatingReadNode> state) { + LoopInfo<HashSet<FloatingReadNode>> info = ReentrantBlockIterator.processLoop(this, loop, new HashSet<>(state)); + + List<HashSet<FloatingReadNode>> loopEndStates = info.endStates; + + // collect all reads that were killed in some branch within the loop + Set<FloatingReadNode> killedReads = new HashSet<>(state); + Set<FloatingReadNode> survivingReads = new HashSet<>(loopEndStates.get(0)); + for (int i = 1; i < loopEndStates.size(); i++) { + survivingReads.retainAll(loopEndStates.get(i)); + } + killedReads.removeAll(survivingReads); + + // reads that were killed within the loop cannot be scheduled after the loop anyway + for (HashSet<FloatingReadNode> exitState : info.exitStates) { + exitState.removeAll(killedReads); + } + return info.exitStates; + } + } private ControlFlowGraph cfg; private NodeMap<Block> earliestCache; @@ -42,6 +132,8 @@ * Map from blocks to the nodes in each block. */ private BlockMap<List<ScheduledNode>> blockToNodesMap; + private final Map<FloatingNode, List<FixedNode>> phantomUsages = new IdentityHashMap<>(); + private final Map<FixedNode, List<FloatingNode>> phantomInputs = new IdentityHashMap<>(); public SchedulePhase() { super("Schedule"); @@ -49,12 +141,26 @@ @Override protected void run(StructuredGraph graph) { + SchedulingStrategy strategy = GraalOptions.OptScheduleOutOfLoops ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST; + cfg = ControlFlowGraph.compute(graph, true, true, true, false); earliestCache = graph.createNodeMap(); blockToNodesMap = new BlockMap<>(cfg); - assignBlockToNodes(graph); - sortNodesWithinBlocks(graph); + if (GraalOptions.MemoryAwareScheduling && graph.getNodes(FloatingReadNode.class).isNotEmpty()) { + + assignBlockToNodes(graph, SchedulingStrategy.EARLIEST); + sortNodesWithinBlocks(graph, SchedulingStrategy.EARLIEST); + + MemoryScheduleClosure closure = new MemoryScheduleClosure(); + ReentrantBlockIterator.apply(closure, getCFG().getStartBlock(), new HashSet<FloatingReadNode>(), null); + + cfg.clearNodeToBlock(); + blockToNodesMap = new BlockMap<>(cfg); + } + + assignBlockToNodes(graph, strategy); + sortNodesWithinBlocks(graph, strategy); } /** @@ -94,7 +200,7 @@ return blockToNodesMap.get(block); } - private void assignBlockToNodes(StructuredGraph graph) { + private void assignBlockToNodes(StructuredGraph graph, SchedulingStrategy strategy) { for (Block block : cfg.getBlocks()) { List<ScheduledNode> nodes = new ArrayList<>(); assert blockToNodesMap.get(block) == null; @@ -106,7 +212,7 @@ for (Node n : graph.getNodes()) { if (n instanceof ScheduledNode) { - assignBlockToNode((ScheduledNode) n); + assignBlockToNode((ScheduledNode) n, strategy); } } } @@ -115,7 +221,7 @@ * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are * already assigned to a block. */ - private void assignBlockToNode(ScheduledNode node) { + private void assignBlockToNode(ScheduledNode node, SchedulingStrategy strategy) { assert !node.isDeleted(); Block prevBlock = cfg.getNodeToBlock().get(node); @@ -126,17 +232,26 @@ // ControlFlowGraph.identifyBlocks assert !(node instanceof PhiNode) : node; assert !(node instanceof FixedNode) : node; - // if in CFG, schedule at the latest position possible in the outermost loop possible - Block latestBlock = latestBlock(node); + Block block; - if (latestBlock == null) { - block = earliestBlock(node); - } else if (GraalOptions.OptScheduleOutOfLoops && !(node instanceof VirtualObjectNode)) { - Block earliestBlock = earliestBlock(node); - block = scheduleOutOfLoops(node, latestBlock, earliestBlock); - assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + node + " (" + earliestBlock + " needs to dominate " + block + ")"; - } else { - block = latestBlock; + switch (strategy) { + case EARLIEST: + block = earliestBlock(node); + break; + case LATEST: + case LATEST_OUT_OF_LOOPS: + block = latestBlock(node, strategy); + if (block == null) { + block = earliestBlock(node); + } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) { + // schedule at the latest position possible in the outermost loop possible + Block earliestBlock = earliestBlock(node); + block = scheduleOutOfLoops(node, block, earliestBlock); + assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + node + " (" + earliestBlock + " needs to dominate " + block + ")"; + } + break; + default: + throw new GraalInternalError("unknown scheduling strategy"); } cfg.getNodeToBlock().set(node, block); blockToNodesMap.get(block).add(node); @@ -145,17 +260,27 @@ /** * Calculates the last block that the given node could be scheduled in, i.e., the common * dominator of all usages. To do so all usages are also assigned to blocks. + * + * @param strategy */ - private Block latestBlock(ScheduledNode node) { + private Block latestBlock(ScheduledNode node, SchedulingStrategy strategy) { CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null); for (Node succ : node.successors().nonNull()) { assert cfg.getNodeToBlock().get(succ) != null; cdbc.apply(cfg.getNodeToBlock().get(succ)); } - ensureScheduledUsages(node); + ensureScheduledUsages(node, strategy); for (Node usage : node.usages()) { - blocksForUsage(node, usage, cdbc); + blocksForUsage(node, usage, cdbc, strategy); } + List<FixedNode> usages = phantomUsages.get(node); + if (usages != null) { + for (FixedNode usage : usages) { + assert cfg.getNodeToBlock().get(usage) != null; + cdbc.apply(cfg.getNodeToBlock().get(usage)); + } + } + return cdbc.block; } @@ -204,7 +329,12 @@ assert node.predecessor() == null; for (Node input : node.inputs().nonNull()) { assert input instanceof ValueNode; - Block inputEarliest = earliestBlock(input); + Block inputEarliest; + if (input instanceof InvokeWithExceptionNode) { + inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next()); + } else { + inputEarliest = earliestBlock(input); + } if (!dominators.get(inputEarliest.getId())) { earliest = inputEarliest; do { @@ -242,7 +372,7 @@ * @param usage the usage whose blocks need to be considered * @param closure the closure that will be called for each block */ - private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure) { + private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure, SchedulingStrategy strategy) { assert !(node instanceof PhiNode); if (usage instanceof PhiNode) { @@ -274,7 +404,7 @@ if (unscheduledUsage instanceof VirtualState) { // If a FrameState is an outer FrameState this method behaves as if the inner // FrameState was the actual usage, by recursing. - blocksForUsage(node, unscheduledUsage, closure); + blocksForUsage(node, unscheduledUsage, closure, strategy); } else if (unscheduledUsage instanceof MergeNode) { // Only FrameStates can be connected to MergeNodes. assert usage instanceof FrameState; @@ -288,20 +418,20 @@ assert usage instanceof FrameState; assert unscheduledUsage instanceof StateSplit; // Otherwise: Put the input into the same block as the usage. - assignBlockToNode((ScheduledNode) unscheduledUsage); + assignBlockToNode((ScheduledNode) unscheduledUsage, strategy); closure.apply(cfg.getNodeToBlock().get(unscheduledUsage)); } } } else { // All other types of usages: Put the input into the same block as the usage. - assignBlockToNode((ScheduledNode) usage); + assignBlockToNode((ScheduledNode) usage, strategy); closure.apply(cfg.getNodeToBlock().get(usage)); } } - private void ensureScheduledUsages(Node node) { + private void ensureScheduledUsages(Node node, SchedulingStrategy strategy) { for (Node usage : node.usages().filter(ScheduledNode.class)) { - assignBlockToNode((ScheduledNode) usage); + assignBlockToNode((ScheduledNode) usage, strategy); } // now true usages are ready } @@ -316,27 +446,43 @@ return ControlFlowGraph.commonDominator(a, b); } - private void sortNodesWithinBlocks(StructuredGraph graph) { + private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) { NodeBitMap visited = graph.createNodeBitMap(); for (Block b : cfg.getBlocks()) { - sortNodesWithinBlock(b, visited); + sortNodesWithinBlock(b, visited, strategy); } } + private void sortNodesWithinBlock(Block b, NodeBitMap visited, SchedulingStrategy strategy) { + assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b; + assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b; + + List<ScheduledNode> sortedInstructions; + switch (strategy) { + case EARLIEST: + sortedInstructions = sortNodesWithinBlockEarliest(b, visited); + break; + case LATEST: + case LATEST_OUT_OF_LOOPS: + sortedInstructions = sortNodesWithinBlockLatest(b, visited); + break; + default: + throw new GraalInternalError("unknown scheduling strategy"); + } + blockToNodesMap.put(b, sortedInstructions); + } + /** * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over * all inputs. This means that a node is added to the list after all its inputs have been * processed. */ - private void sortNodesWithinBlock(Block b, NodeBitMap visited) { + private List<ScheduledNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited) { List<ScheduledNode> instructions = blockToNodesMap.get(b); - List<ScheduledNode> sortedInstructions = new ArrayList<>(instructions.size() + 2); - - assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b; - assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b; + List<ScheduledNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2); for (ScheduledNode i : instructions) { - addToSorting(b, i, sortedInstructions, visited); + addToLatestSorting(b, i, sortedInstructions, visited); } // Make sure that last node gets really last (i.e. when a frame state successor hangs off @@ -363,25 +509,25 @@ sortedInstructions.add(b.getEndNode()); } } - blockToNodesMap.put(b, sortedInstructions); + return sortedInstructions; } - private void addUnscheduledToSorting(Block b, VirtualState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited) { + private void addUnscheduledToLatestSorting(Block b, VirtualState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited) { if (state != null) { // UnscheduledNodes should never be marked as visited. assert !visited.isMarked(state); for (Node input : state.inputs()) { if (input instanceof VirtualState) { - addUnscheduledToSorting(b, (VirtualState) input, sortedInstructions, visited); + addUnscheduledToLatestSorting(b, (VirtualState) input, sortedInstructions, visited); } else { - addToSorting(b, (ScheduledNode) input, sortedInstructions, visited); + addToLatestSorting(b, (ScheduledNode) input, sortedInstructions, visited); } } } } - private void addToSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) { + private void addToLatestSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) { if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) { return; } @@ -396,17 +542,74 @@ assert state == null; state = (FrameState) input; } else { - addToSorting(b, (ScheduledNode) input, sortedInstructions, visited); + addToLatestSorting(b, (ScheduledNode) input, sortedInstructions, visited); + } + } + List<FloatingNode> inputs = phantomInputs.get(i); + if (inputs != null) { + for (FloatingNode input : inputs) { + addToLatestSorting(b, input, sortedInstructions, visited); } } - addToSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited); + addToLatestSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited); visited.mark(i); - addUnscheduledToSorting(b, state, sortedInstructions, visited); + addUnscheduledToLatestSorting(b, state, sortedInstructions, visited); assert write == null || !visited.isMarked(write); - addToSorting(b, write, sortedInstructions, visited); + addToLatestSorting(b, write, sortedInstructions, visited); // Now predecessors and inputs are scheduled => we can add this node. sortedInstructions.add(i); } + + /** + * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over + * all usages. The resulting list is reversed to create an earliest-possible scheduling of + * nodes. + */ + private List<ScheduledNode> sortNodesWithinBlockEarliest(Block b, NodeBitMap visited) { + List<ScheduledNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2); + addToEarliestSorting(b, b.getEndNode(), sortedInstructions, visited); + Collections.reverse(sortedInstructions); + return sortedInstructions; + } + + private void addToEarliestSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) { + if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) { + return; + } + + visited.mark(i); + for (Node usage : i.usages()) { + if (usage instanceof VirtualState) { + // only fixed nodes can have VirtualState -> no need to schedule them + } else { + if (i instanceof LoopExitNode && usage instanceof ValueProxyNode) { + // value proxies should be scheduled before the loopexit, not after + } else { + addToEarliestSorting(b, (ScheduledNode) usage, sortedInstructions, visited); + } + } + } + + if (i instanceof BeginNode) { + ArrayList<ValueProxyNode> proxies = (i instanceof LoopExitNode) ? new ArrayList<ValueProxyNode>() : null; + for (ScheduledNode inBlock : blockToNodesMap.get(b)) { + if (!visited.isMarked(inBlock)) { + if (inBlock instanceof ValueProxyNode) { + proxies.add((ValueProxyNode) inBlock); + } else { + addToEarliestSorting(b, inBlock, sortedInstructions, visited); + } + } + } + sortedInstructions.add(i); + if (proxies != null) { + sortedInstructions.addAll(proxies); + } + } else { + sortedInstructions.add(i); + addToEarliestSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited); + } + } }
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/GraphPrinterDumpHandler.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/GraphPrinterDumpHandler.java Tue Feb 26 20:07:29 2013 +0100 @@ -33,6 +33,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.schedule.*; /** * Observes compilation events and uses {@link IdealGraphPrinter} to generate a graph representation @@ -153,13 +154,14 @@ // Save inline context for next dump. previousInlineContext = inlineContext; + final SchedulePhase predefinedSchedule = getPredefinedSchedule(); Debug.sandbox("PrintingGraph", new Runnable() { @Override public void run() { // Finally, output the graph. try { - printer.print(graph, message, null); + printer.print(graph, message, predefinedSchedule); } catch (IOException e) { failuresCount++; printer = null; @@ -191,6 +193,16 @@ return result; } + private static SchedulePhase getPredefinedSchedule() { + SchedulePhase result = null; + for (Object o : Debug.context()) { + if (o instanceof SchedulePhase) { + result = (SchedulePhase) o; + } + } + return result; + } + private void openScope(String name, boolean showThread) { String prefix = showThread ? Thread.currentThread().getName() + ":" : ""; try {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Tue Feb 26 17:25:14 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Tue Feb 26 20:07:29 2013 +0100 @@ -32,10 +32,9 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.Virtualizable.EscapeState; import com.oracle.graal.nodes.virtual.*; -import com.oracle.graal.phases.graph.ReentrantBlockIterator.MergeableBlockState; import com.oracle.graal.virtual.nodes.*; -class BlockState extends MergeableBlockState<BlockState> { +class BlockState { private final HashMap<VirtualObjectNode, ObjectState> objectStates = new HashMap<>(); private final HashMap<ValueNode, VirtualObjectNode> objectAliases = new HashMap<>(); @@ -70,7 +69,6 @@ return object == null ? null : getObjectState(object); } - @Override public BlockState cloneState() { return new BlockState(this); }