# HG changeset patch # User Lukas Stadler # Date 1361894657 -3600 # Node ID 886990f21773d576fc925dc73456487bdcfd7370 # Parent 7418844542534c268e619a6fb229f07ac7201bdb memory-aware scheduling phase diff -r 741884454253 -r 886990f21773 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java --- /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 17:04:17 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() { + + @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; + } + }); + } +} diff -r 741884454253 -r 886990f21773 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java Wed Feb 13 18:06:19 2013 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java Tue Feb 26 17:04:17 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> entries() { return new Iterable>() { diff -r 741884454253 -r 886990f21773 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Wed Feb 13 18:06:19 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Tue Feb 26 17:04:17 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); } } diff -r 741884454253 -r 886990f21773 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Wed Feb 13 18:06:19 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Tue Feb 26 17:04:17 2013 +0100 @@ -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; diff -r 741884454253 -r 886990f21773 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Wed Feb 13 18:06:19 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Tue Feb 26 17:04:17 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> { + + @Override + protected void processBlock(Block block, HashSet 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 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 usageList = phantomUsages.get(read); + if (usageList == null) { + phantomUsages.put(read, usageList = new ArrayList<>()); + } + usageList.add(fixed); + List inputList = phantomInputs.get(fixed); + if (inputList == null) { + phantomInputs.put(fixed, inputList = new ArrayList<>()); + } + inputList.add(read); + } + + @Override + protected HashSet merge(MergeNode merge, List> states) { + HashSet state = new HashSet<>(states.get(0)); + for (int i = 1; i < states.size(); i++) { + state.retainAll(states.get(i)); + } + return state; + } + + @Override + protected HashSet afterSplit(FixedNode node, HashSet oldState) { + return new HashSet<>(oldState); + } + + @Override + protected List> processLoop(Loop loop, HashSet state) { + LoopInfo> info = ReentrantBlockIterator.processLoop(this, loop, new HashSet<>(state)); + + List> loopEndStates = info.endStates; + + // collect all reads that were killed in some branch within the loop + Set killedReads = new HashSet<>(state); + Set 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 exitState : info.exitStates) { + exitState.removeAll(killedReads); + } + return info.exitStates; + } + } private ControlFlowGraph cfg; private NodeMap earliestCache; @@ -42,6 +132,8 @@ * Map from blocks to the nodes in each block. */ private BlockMap> blockToNodesMap; + private final Map> phantomUsages = new IdentityHashMap<>(); + private final Map> 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(), 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 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 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 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 sortNodesWithinBlockLatest(Block b, NodeBitMap visited) { List instructions = blockToNodesMap.get(b); - List 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 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 sortedInstructions, NodeBitMap visited) { + private void addUnscheduledToLatestSorting(Block b, VirtualState state, List 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 sortedInstructions, NodeBitMap visited) { + private void addToLatestSorting(Block b, ScheduledNode i, List 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 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 sortNodesWithinBlockEarliest(Block b, NodeBitMap visited) { + List 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 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 proxies = (i instanceof LoopExitNode) ? new ArrayList() : 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); + } + } }