Mercurial > hg > graal-compiler

changeset 13370:3e67710a6d08

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SchedulePhase: remove old memory aware scheudling
author Bernhard Urban <bernhard.urban@jku.at>
date Tue, 17 Dec 2013 21:39:01 +0100
parents c3ecad078114
children 4db09b7304da
files graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java
diffstat 3 files changed, 29 insertions(+), 169 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java	Tue Dec 17 16:38:51 2013 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java	Tue Dec 17 21:39:01 2013 +0100
@@ -87,7 +87,7 @@
     @Test
     public void testSimple() {
         for (TestMode mode : TestMode.values()) {
-            SchedulePhase schedule = getFinalSchedule("testSimpleSnippet", mode, MemoryScheduling.OPTIMAL);
+            SchedulePhase schedule = getFinalSchedule("testSimpleSnippet", mode);
             StructuredGraph graph = schedule.getCFG().graph;
             assertReadAndWriteInSameBlock(schedule, true);
             assertOrderedAfterSchedule(schedule, graph.getNodes().filter(FloatingReadNode.class).first(), graph.getNodes().filter(WriteNode.class).first());
@@ -112,7 +112,7 @@
     @Test
     public void testSplit1() {
         for (TestMode mode : TestMode.values()) {
-            SchedulePhase schedule = getFinalSchedule("testSplit1Snippet", mode, MemoryScheduling.OPTIMAL);
+            SchedulePhase schedule = getFinalSchedule("testSplit1Snippet", mode);
             assertReadWithinStartBlock(schedule, true);
             assertReadWithinReturnBlock(schedule, false);
         }
@@ -135,7 +135,7 @@
 
     @Test
     public void testSplit2() {
-        SchedulePhase schedule = getFinalSchedule("testSplit2Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testSplit2Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, true);
     }
@@ -159,7 +159,7 @@
 
     @Test
     public void testLoop1() {
-        SchedulePhase schedule = getFinalSchedule("testLoop1Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testLoop1Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(6, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, true);
         assertReadWithinReturnBlock(schedule, false);
@@ -184,7 +184,7 @@
 
     @Test
     public void testLoop2() {
-        SchedulePhase schedule = getFinalSchedule("testLoop2Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testLoop2Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(6, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, true);
@@ -206,7 +206,7 @@
 
     @Test
     public void testLoop3() {
-        SchedulePhase schedule = getFinalSchedule("testLoop3Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testLoop3Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(7, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, true);
         assertReadWithinReturnBlock(schedule, false);
@@ -218,7 +218,7 @@
 
     @Test
     public void testStringReplace() {
-        getFinalSchedule("testStringReplaceSnippet", TestMode.INLINED_WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        getFinalSchedule("testStringReplaceSnippet", TestMode.INLINED_WITHOUT_FRAMESTATES);
         test("testStringReplaceSnippet", "acbaaa");
     }
 
@@ -242,7 +242,7 @@
 
     @Test
     public void testLoop5() {
-        SchedulePhase schedule = getFinalSchedule("testLoop5Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testLoop5Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(7, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, false);
@@ -258,7 +258,7 @@
 
     @Test
     public void testArrayCopy() {
-        SchedulePhase schedule = getFinalSchedule("testArrayCopySnippet", TestMode.INLINED_WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testArrayCopySnippet", TestMode.INLINED_WITHOUT_FRAMESTATES);
         StructuredGraph graph = schedule.getCFG().getStartBlock().getBeginNode().graph();
         ReturnNode ret = graph.getNodes().filter(ReturnNode.class).first();
         assertTrue(ret.result() instanceof FloatingReadNode);
@@ -279,7 +279,7 @@
 
     @Test
     public void testIfRead1() {
-        SchedulePhase schedule = getFinalSchedule("testIfRead1Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testIfRead1Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(4, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, true);
         assertReadAndWriteInSameBlock(schedule, false);
@@ -300,7 +300,7 @@
 
     @Test
     public void testIfRead2() {
-        SchedulePhase schedule = getFinalSchedule("testIfRead2Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testIfRead2Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(4, schedule.getCFG().getBlocks().length);
         assertEquals(1, schedule.getCFG().graph.getNodes().filter(FloatingReadNode.class).count());
         assertReadWithinStartBlock(schedule, false);
@@ -322,7 +322,7 @@
 
     @Test
     public void testIfRead3() {
-        SchedulePhase schedule = getFinalSchedule("testIfRead3Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testIfRead3Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(4, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, true);
@@ -343,7 +343,7 @@
 
     @Test
     public void testIfRead4() {
-        SchedulePhase schedule = getFinalSchedule("testIfRead4Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testIfRead4Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(4, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, false);
@@ -362,7 +362,7 @@
 
     @Test
     public void testIfRead5() {
-        SchedulePhase schedule = getFinalSchedule("testIfRead5Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testIfRead5Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertEquals(4, schedule.getCFG().getBlocks().length);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, true);
@@ -388,7 +388,7 @@
 
     @Test
     public void testBlockSchedule() {
-        SchedulePhase schedule = getFinalSchedule("testBlockScheduleSnippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testBlockScheduleSnippet", TestMode.WITHOUT_FRAMESTATES);
         StructuredGraph graph = schedule.getCFG().graph;
         NodeIterable<WriteNode> writeNodes = graph.getNodes().filter(WriteNode.class);
 
@@ -447,7 +447,7 @@
 
     @Test
     public void testProxy1() {
-        SchedulePhase schedule = getFinalSchedule("testProxy1Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testProxy1Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertReadWithinStartBlock(schedule, true); // read of container.a should be in start block
         /*
          * read of container.b for increment operation should be in return block. TODO: not sure
@@ -473,7 +473,7 @@
 
     @Test
     public void testProxy2() {
-        SchedulePhase schedule = getFinalSchedule("testProxy2Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testProxy2Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, false);
     }
@@ -496,7 +496,7 @@
 
     @Test
     public void testStringHashCode() {
-        SchedulePhase schedule = getFinalSchedule("testStringHashCodeSnippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testStringHashCodeSnippet", TestMode.WITHOUT_FRAMESTATES);
         assertReadWithinStartBlock(schedule, true);
         assertReadWithinReturnBlock(schedule, false);
 
@@ -528,7 +528,7 @@
 
     @Test
     public void testLoop4() {
-        SchedulePhase schedule = getFinalSchedule("testLoop4Snippet", TestMode.WITHOUT_FRAMESTATES, MemoryScheduling.OPTIMAL);
+        SchedulePhase schedule = getFinalSchedule("testLoop4Snippet", TestMode.WITHOUT_FRAMESTATES);
         assertReadWithinStartBlock(schedule, false);
         assertReadWithinReturnBlock(schedule, false);
     }
@@ -573,6 +573,10 @@
         assertTrue(!(inSame ^ schedule.getCFG().blockFor(read) == schedule.getCFG().blockFor(write)));
     }
 
+    private SchedulePhase getFinalSchedule(final String snippet, final TestMode mode) {
+        return getFinalSchedule(snippet, mode, MemoryScheduling.OPTIMAL);
+    }
+
     private SchedulePhase getFinalSchedule(final String snippet, final TestMode mode, final MemoryScheduling memsched) {
         return getFinalSchedule(snippet, mode, memsched, SchedulingStrategy.LATEST_OUT_OF_LOOPS);
     }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Tue Dec 17 16:38:51 2013 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Tue Dec 17 21:39:01 2013 +0100
@@ -218,9 +218,7 @@
     public static final OptionValue<Boolean> CanOmitFrame = new OptionValue<>(true);
 
     @Option(help = "")
-    public static final OptionValue<Boolean> MemoryAwareScheduling = new OptionValue<>(false);
-    @Option(help = "")
-    public static final OptionValue<Boolean> NewMemoryAwareScheduling = new OptionValue<>(true);
+    public static final OptionValue<Boolean> MemoryAwareScheduling = new OptionValue<>(true);
 
     // Translating tableswitch instructions
     @Option(help = "")
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Dec 17 16:38:51 2013 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Dec 17 21:39:01 2013 +0100
@@ -33,7 +33,6 @@
 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.spi.*;
@@ -75,104 +74,7 @@
     }
 
     public static enum MemoryScheduling {
-        NONE, CONSERVATIVE, OPTIMAL
-    }
-
-    /**
-     * This closure iterates over all nodes of a scheduled graph (it expects a
-     * {@link SchedulingStrategy#EARLIEST} schedule) and keeps a list of "active" 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 HashSet<FloatingReadNode> getInitialState() {
-            return new HashSet<>();
-        }
-
-        @Override
-        protected HashSet<FloatingReadNode> processBlock(Block block, HashSet<FloatingReadNode> currentState) {
-            for (Node node : blockToNodesMap.get(block)) {
-                if (node instanceof FloatingReadNode) {
-                    currentState.add((FloatingReadNode) node);
-                } else if (node instanceof MemoryCheckpoint.Single) {
-                    LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
-                    processIdentity(currentState, (FixedNode) node, identity);
-                } else if (node instanceof MemoryCheckpoint.Multi) {
-                    for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
-                        processIdentity(currentState, (FixedNode) node, identity);
-                    }
-                }
-                assert MemoryCheckpoint.TypeAssertion.correctType(node);
-            }
-            return currentState;
-        }
-
-        private void processIdentity(HashSet<FloatingReadNode> currentState, FixedNode fixed, LocationIdentity identity) {
-            for (Iterator<FloatingReadNode> iter = currentState.iterator(); iter.hasNext();) {
-                FloatingReadNode read = iter.next();
-                if (identity == ANY_LOCATION || read.location().getLocationIdentity() == identity) {
-                    addPhantomReference(read, fixed);
-                    iter.remove();
-                }
-            }
-        }
-
-        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(Block 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> cloneState(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;
-        }
+        NONE, OPTIMAL
     }
 
     private class KillSet implements Iterable<LocationIdentity> {
@@ -341,8 +243,6 @@
      */
     private BlockMap<List<ScheduledNode>> blockToNodesMap;
     private BlockMap<KillSet> blockToKillSet;
-    private final Map<FloatingNode, List<FixedNode>> phantomUsages = new IdentityHashMap<>();
-    private final Map<FixedNode, List<FloatingNode>> phantomInputs = new IdentityHashMap<>();
     private final SchedulingStrategy selectedStrategy;
     private final MemoryScheduling memsched;
 
@@ -351,16 +251,7 @@
     }
 
     public SchedulePhase(SchedulingStrategy strategy) {
-        if (MemoryAwareScheduling.getValue() && NewMemoryAwareScheduling.getValue()) {
-            throw new SchedulingError("cannot enable both: MemoryAware- and NewMemoryAwareScheduling");
-        }
-        if (MemoryAwareScheduling.getValue()) {
-            this.memsched = MemoryScheduling.CONSERVATIVE;
-        } else if (NewMemoryAwareScheduling.getValue()) {
-            this.memsched = MemoryScheduling.OPTIMAL;
-        } else {
-            this.memsched = MemoryScheduling.NONE;
-        }
+        this.memsched = MemoryAwareScheduling.getValue() ? MemoryScheduling.OPTIMAL : MemoryScheduling.NONE;
         this.selectedStrategy = strategy;
     }
 
@@ -375,19 +266,7 @@
         earliestCache = graph.createNodeMap();
         blockToNodesMap = new BlockMap<>(cfg);
 
-        if (memsched == MemoryScheduling.CONSERVATIVE && selectedStrategy != SchedulingStrategy.EARLIEST && graph.getNodes(FloatingReadNode.class).isNotEmpty()) {
-            assignBlockToNodes(graph, SchedulingStrategy.EARLIEST);
-            sortNodesWithinBlocks(graph, SchedulingStrategy.EARLIEST);
-
-            ReentrantBlockIterator.apply(new MemoryScheduleClosure(), getCFG().getStartBlock());
-
-            cfg.clearNodeToBlock();
-            blockToNodesMap = new BlockMap<>(cfg);
-
-            assignBlockToNodes(graph, selectedStrategy);
-            sortNodesWithinBlocks(graph, selectedStrategy);
-            printSchedule("after sorting nodes within blocks");
-        } else if (memsched == MemoryScheduling.OPTIMAL && selectedStrategy != SchedulingStrategy.EARLIEST && graph.getNodes(FloatingReadNode.class).isNotEmpty()) {
+        if (memsched == MemoryScheduling.OPTIMAL && selectedStrategy != SchedulingStrategy.EARLIEST && graph.getNodes(FloatingReadNode.class).isNotEmpty()) {
             blockToKillSet = new BlockMap<>(cfg);
 
             assignBlockToNodes(graph, selectedStrategy);
@@ -655,8 +534,7 @@
                 }
             }
         }
-        assert false : "should have found a block for " + n;
-        return null;
+        throw new SchedulingError("should have found a block for " + n);
     }
 
     /**
@@ -720,15 +598,6 @@
                 blocksForUsage(node, usage, cdbc, strategy);
             }
         }
-        List<FixedNode> usages = phantomUsages.get(node);
-        if (usages != null) {
-            for (FixedNode usage : usages) {
-                if (cfg.getNodeToBlock().get(usage) == null) {
-                    throw new SchedulingError();
-                }
-                cdbc.apply(cfg.getNodeToBlock().get(usage));
-            }
-        }
 
         if (assertionEnabled()) {
             if (cdbc.block != null && !earliestBlock(node).dominates(cdbc.block)) {
@@ -1010,10 +879,6 @@
         List<FloatingReadNode> reads = new ArrayList<>();
 
         if (memsched == MemoryScheduling.OPTIMAL) {
-            /*
-             * TODO: add assert for invariant
-             * "floatingreads occur always after memory checkpoints in unsorted list"
-             */
             for (ScheduledNode i : instructions) {
                 if (i instanceof FloatingReadNode) {
                     FloatingReadNode frn = (FloatingReadNode) i;
@@ -1067,8 +932,7 @@
             if (frn.getLastLocationAccess() == node) {
                 assert identity == ANY_LOCATION || readLocation == identity : "location doesn't match: " + readLocation + ", " + identity;
                 beforeLastLocation.clear(frn);
-            } else if (!beforeLastLocation.isMarked(frn) && (readLocation == identity || (!(node instanceof StartNode) && ANY_LOCATION == identity))) {
-                // TODO: replace instanceof check with object identity check
+            } else if (!beforeLastLocation.isMarked(frn) && (readLocation == identity || (node != getCFG().graph.start() && ANY_LOCATION == identity))) {
                 reads.remove(frn);
                 addToLatestSorting(b, frn, sortedInstructions, visited, reads, beforeLastLocation);
             }
@@ -1107,12 +971,6 @@
 
             }
         }
-        List<FloatingNode> inputs = phantomInputs.get(i);
-        if (inputs != null) {
-            for (FloatingNode input : inputs) {
-                addToLatestSorting(b, input, sortedInstructions, visited, reads, beforeLastLocation);
-            }
-        }
 
         if (memsched == MemoryScheduling.OPTIMAL && reads.size() != 0) {
             if (i instanceof MemoryCheckpoint.Single) {