001/*
002 * Copyright (c) 2011, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.schedule;
024
025import static com.oracle.graal.compiler.common.GraalOptions.*;
026import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
027
028import java.util.*;
029
030import com.oracle.graal.debug.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.compiler.common.*;
034import com.oracle.graal.compiler.common.cfg.*;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.nodes.*;
037import com.oracle.graal.nodes.cfg.*;
038import com.oracle.graal.nodes.memory.*;
039import com.oracle.graal.phases.*;
040
041public final class SchedulePhase extends Phase {
042
043    /**
044     * Error thrown when a graph cannot be scheduled.
045     */
046    public static class SchedulingError extends Error {
047
048        private static final long serialVersionUID = 1621001069476473145L;
049
050        public SchedulingError() {
051            super();
052        }
053
054        /**
055         * This constructor creates a {@link SchedulingError} with a message assembled via
056         * {@link String#format(String, Object...)}.
057         *
058         * @param format a {@linkplain Formatter format} string
059         * @param args parameters to {@link String#format(String, Object...)}
060         */
061        public SchedulingError(String format, Object... args) {
062            super(String.format(format, args));
063        }
064
065    }
066
067    public static enum SchedulingStrategy {
068        EARLIEST,
069        LATEST,
070        LATEST_OUT_OF_LOOPS
071    }
072
073    private ControlFlowGraph cfg;
074
075    /**
076     * Map from blocks to the nodes in each block.
077     */
078    private BlockMap<List<Node>> blockToNodesMap;
079    private BlockMap<LocationSet> blockToKillSet;
080    private final SchedulingStrategy selectedStrategy;
081    private NodeMap<Block> nodeToBlockMap;
082
083    public SchedulePhase() {
084        this(OptScheduleOutOfLoops.getValue() ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST);
085    }
086
087    public SchedulePhase(SchedulingStrategy strategy) {
088        this.selectedStrategy = strategy;
089    }
090
091    @Override
092    protected void run(StructuredGraph graph) {
093        // assert GraphOrder.assertNonCyclicGraph(graph);
094        cfg = ControlFlowGraph.compute(graph, true, true, true, false);
095
096        if (selectedStrategy == SchedulingStrategy.EARLIEST) {
097            // Assign early so we are getting a context in case of an exception.
098            this.nodeToBlockMap = graph.createNodeMap();
099            this.blockToNodesMap = new BlockMap<>(cfg);
100            NodeBitMap visited = graph.createNodeBitMap();
101            scheduleEarliestIterative(cfg, blockToNodesMap, nodeToBlockMap, visited, graph);
102            return;
103        } else {
104            boolean isOutOfLoops = selectedStrategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS;
105            if (selectedStrategy == SchedulingStrategy.LATEST || isOutOfLoops) {
106                NodeMap<Block> currentNodeMap = graph.createNodeMap();
107                BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
108                NodeBitMap visited = graph.createNodeBitMap();
109
110                // Assign early so we are getting a context in case of an exception.
111                this.blockToNodesMap = earliestBlockToNodesMap;
112                this.nodeToBlockMap = currentNodeMap;
113
114                scheduleEarliestIterative(cfg, earliestBlockToNodesMap, currentNodeMap, visited, graph);
115                BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
116
117                for (Block b : cfg.getBlocks()) {
118                    latestBlockToNodesMap.put(b, new ArrayList<Node>());
119                }
120
121                BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(isOutOfLoops, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap);
122                sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
123
124                assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
125                assert MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);
126
127                this.blockToNodesMap = latestBlockToNodesMap;
128                this.nodeToBlockMap = currentNodeMap;
129
130                cfg.setNodeToBlock(currentNodeMap);
131            }
132        }
133    }
134
135    @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")
136    private BlockMap<ArrayList<FloatingReadNode>> calcLatestBlocks(boolean isOutOfLoops, NodeMap<Block> currentNodeMap, BlockMap<List<Node>> earliestBlockToNodesMap, NodeBitMap visited,
137                    BlockMap<List<Node>> latestBlockToNodesMap) {
138        BlockMap<ArrayList<FloatingReadNode>> watchListMap = null;
139        for (Block b : cfg.postOrder()) {
140            List<Node> blockToNodes = earliestBlockToNodesMap.get(b);
141            LocationSet killed = null;
142            int previousIndex = blockToNodes.size();
143            for (int i = blockToNodes.size() - 1; i >= 0; --i) {
144                Node currentNode = blockToNodes.get(i);
145                assert currentNodeMap.get(currentNode) == b;
146                assert !(currentNode instanceof PhiNode) && !(currentNode instanceof ProxyNode);
147                assert visited.isMarked(currentNode);
148                if (currentNode instanceof FixedNode) {
149                    // For these nodes, the earliest is at the same time the latest block.
150                } else {
151                    Block currentBlock = b;
152                    assert currentBlock != null;
153
154                    Block latestBlock = calcLatestBlock(b, isOutOfLoops, currentNode, currentNodeMap);
155                    assert checkLatestEarliestRelation(currentNode, currentBlock, latestBlock);
156                    if (latestBlock != currentBlock) {
157                        if (currentNode instanceof FloatingReadNode) {
158
159                            FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;
160                            LocationIdentity location = floatingReadNode.getLocationIdentity();
161                            if (location.isMutable()) {
162                                if (currentBlock.canKill(location)) {
163                                    if (killed == null) {
164                                        killed = new LocationSet();
165                                    }
166                                    fillKillSet(killed, blockToNodes.subList(i + 1, previousIndex));
167                                    previousIndex = i;
168                                    if (killed.contains(location)) {
169                                        latestBlock = currentBlock;
170                                    }
171                                }
172
173                                if (latestBlock != currentBlock) {
174                                    // We are not constraint within currentBlock. Check if
175                                    // we are contraint while walking down the dominator
176                                    // line.
177                                    Block newLatestBlock = adjustLatestForRead(floatingReadNode, currentBlock, latestBlock, location);
178                                    assert dominates(newLatestBlock, latestBlock);
179                                    assert dominates(currentBlock, newLatestBlock);
180                                    latestBlock = newLatestBlock;
181
182                                    if (newLatestBlock != currentBlock && latestBlock.canKill(location)) {
183                                        if (watchListMap == null) {
184                                            watchListMap = new BlockMap<>(cfg);
185                                        }
186                                        if (watchListMap.get(latestBlock) == null) {
187                                            watchListMap.put(latestBlock, new ArrayList<>());
188                                        }
189                                        watchListMap.get(latestBlock).add(floatingReadNode);
190                                    }
191                                }
192                            }
193                        }
194                        currentNodeMap.set(currentNode, latestBlock);
195                        currentBlock = latestBlock;
196                    }
197                    latestBlockToNodesMap.get(currentBlock).add(currentNode);
198                }
199            }
200        }
201        return watchListMap;
202    }
203
204    private static boolean checkLatestEarliestRelation(Node currentNode, Block earliestBlock, Block latestBlock) {
205        assert AbstractControlFlowGraph.dominates(earliestBlock, latestBlock) || (currentNode instanceof VirtualState && latestBlock == earliestBlock.getDominator()) : String.format(
206                        "%s %s (%s) %s (%s)", currentNode, earliestBlock, earliestBlock.getBeginNode(), latestBlock, latestBlock.getBeginNode());
207        return true;
208    }
209
210    private static boolean verifySchedule(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) {
211        for (Block b : cfg.getBlocks()) {
212            List<Node> nodes = blockToNodesMap.get(b);
213            for (Node n : nodes) {
214                assert n.isAlive();
215                assert nodeMap.get(n) == b;
216            }
217        }
218        return true;
219    }
220
221    private static Block adjustLatestForRead(FloatingReadNode floatingReadNode, Block earliestBlock, Block latestBlock, LocationIdentity location) {
222        assert strictlyDominates(earliestBlock, latestBlock);
223        Block current = latestBlock.getDominator();
224
225        // Collect dominator chain that needs checking.
226        List<Block> dominatorChain = new ArrayList<>();
227        dominatorChain.add(latestBlock);
228        while (current != earliestBlock) {
229            // Current is an intermediate dominator between earliestBlock and latestBlock.
230            assert strictlyDominates(earliestBlock, current) && strictlyDominates(current, latestBlock);
231            if (current.canKill(location)) {
232                dominatorChain.clear();
233            }
234            dominatorChain.add(current);
235            current = current.getDominator();
236            assert current != null : floatingReadNode;
237        }
238
239        // The first element of dominatorChain now contains the latest possible block.
240        assert dominatorChain.size() >= 1;
241        assert dominatorChain.get(dominatorChain.size() - 1).getDominator() == earliestBlock;
242
243        Block lastBlock = earliestBlock;
244        for (int i = dominatorChain.size() - 1; i >= 0; --i) {
245            Block currentBlock = dominatorChain.get(i);
246            if (currentBlock.getLoopDepth() > lastBlock.getLoopDepth()) {
247                // We are entering a loop boundary. The new loops must not kill the location for the
248                // crossing to be safe.
249                if (currentBlock.getLoop() != null && ((HIRLoop) currentBlock.getLoop()).canKill(location)) {
250                    break;
251                }
252            }
253
254            if (currentBlock.canKillBetweenThisAndDominator(location)) {
255                break;
256            }
257            lastBlock = currentBlock;
258        }
259
260        return lastBlock;
261    }
262
263    private static void fillKillSet(LocationSet killed, List<Node> subList) {
264        if (!killed.isAny()) {
265            for (Node n : subList) {
266                // Check if this node kills a node in the watch list.
267                if (n instanceof MemoryCheckpoint.Single) {
268                    LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
269                    killed.add(identity);
270                    if (killed.isAny()) {
271                        return;
272                    }
273                } else if (n instanceof MemoryCheckpoint.Multi) {
274                    for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
275                        killed.add(identity);
276                        if (killed.isAny()) {
277                            return;
278                        }
279                    }
280                }
281            }
282        }
283    }
284
285    private static void sortNodesLatestWithinBlock(ControlFlowGraph cfg, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> currentNodeMap,
286                    BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap visited) {
287        for (Block b : cfg.getBlocks()) {
288            sortNodesLatestWithinBlock(b, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
289        }
290    }
291
292    private static void sortNodesLatestWithinBlock(Block b, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> nodeMap,
293                    BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap unprocessed) {
294        List<Node> earliestSorting = earliestBlockToNodesMap.get(b);
295        ArrayList<Node> result = new ArrayList<>(earliestSorting.size());
296        ArrayList<FloatingReadNode> watchList = null;
297        if (watchListMap != null) {
298            watchList = watchListMap.get(b);
299            assert watchList == null || !b.getKillLocations().isEmpty();
300        }
301        AbstractBeginNode beginNode = b.getBeginNode();
302        if (beginNode instanceof LoopExitNode) {
303            LoopExitNode loopExitNode = (LoopExitNode) beginNode;
304            for (ProxyNode proxy : loopExitNode.proxies()) {
305                unprocessed.clear(proxy);
306                ValueNode value = proxy.value();
307                if (value != null && nodeMap.get(value) == b) {
308                    sortIntoList(value, b, result, nodeMap, unprocessed, null);
309                }
310            }
311        }
312        FixedNode endNode = b.getEndNode();
313        FixedNode fixedEndNode = null;
314        if (isFixedEnd(endNode)) {
315            // Only if the end node is either a control split or an end node, we need to force it to
316            // be the last node in the schedule.
317            fixedEndNode = endNode;
318        }
319        for (Node n : earliestSorting) {
320            if (n != fixedEndNode) {
321                if (n instanceof FixedNode) {
322                    assert nodeMap.get(n) == b;
323                    checkWatchList(b, nodeMap, unprocessed, result, watchList, n);
324                    sortIntoList(n, b, result, nodeMap, unprocessed, null);
325                } else if (nodeMap.get(n) == b && n instanceof FloatingReadNode) {
326                    FloatingReadNode floatingReadNode = (FloatingReadNode) n;
327                    LocationIdentity location = floatingReadNode.getLocationIdentity();
328                    if (b.canKill(location)) {
329                        // This read can be killed in this block, add to watch list.
330                        if (watchList == null) {
331                            watchList = new ArrayList<>();
332                        }
333                        watchList.add(floatingReadNode);
334                    }
335                }
336            }
337        }
338
339        for (Node n : latestBlockToNodesMap.get(b)) {
340            assert nodeMap.get(n) == b;
341            assert !(n instanceof FixedNode);
342            if (unprocessed.isMarked(n)) {
343                sortIntoList(n, b, result, nodeMap, unprocessed, fixedEndNode);
344            }
345        }
346
347        if (endNode != null && unprocessed.isMarked(endNode)) {
348            sortIntoList(endNode, b, result, nodeMap, unprocessed, null);
349        }
350
351        latestBlockToNodesMap.put(b, result);
352    }
353
354    private static void checkWatchList(Block b, NodeMap<Block> nodeMap, NodeBitMap unprocessed, ArrayList<Node> result, ArrayList<FloatingReadNode> watchList, Node n) {
355        if (watchList != null && !watchList.isEmpty()) {
356            // Check if this node kills a node in the watch list.
357            if (n instanceof MemoryCheckpoint.Single) {
358                LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
359                checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
360            } else if (n instanceof MemoryCheckpoint.Multi) {
361                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
362                    checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
363                }
364            }
365        }
366    }
367
368    private static void checkWatchList(ArrayList<FloatingReadNode> watchList, LocationIdentity identity, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed) {
369        assert identity.isMutable();
370        if (identity.isAny()) {
371            for (FloatingReadNode r : watchList) {
372                if (unprocessed.isMarked(r)) {
373                    sortIntoList(r, b, result, nodeMap, unprocessed, null);
374                }
375            }
376            watchList.clear();
377        } else {
378            int index = 0;
379            while (index < watchList.size()) {
380                FloatingReadNode r = watchList.get(index);
381                LocationIdentity locationIdentity = r.getLocationIdentity();
382                assert locationIdentity.isMutable();
383                if (unprocessed.isMarked(r)) {
384                    if (identity.overlaps(locationIdentity)) {
385                        sortIntoList(r, b, result, nodeMap, unprocessed, null);
386                    } else {
387                        ++index;
388                        continue;
389                    }
390                }
391                int lastIndex = watchList.size() - 1;
392                watchList.set(index, watchList.get(lastIndex));
393                watchList.remove(lastIndex);
394            }
395        }
396    }
397
398    private static void sortIntoList(Node n, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed, Node excludeNode) {
399        assert unprocessed.isMarked(n) : n;
400        unprocessed.clear(n);
401
402        assert nodeMap.get(n) == b;
403
404        if (n instanceof PhiNode) {
405            return;
406        }
407
408        for (Node input : n.inputs()) {
409            if (nodeMap.get(input) == b && unprocessed.isMarked(input) && input != excludeNode) {
410                sortIntoList(input, b, result, nodeMap, unprocessed, excludeNode);
411            }
412        }
413
414        if (n instanceof ProxyNode) {
415            // Skip proxy nodes.
416        } else {
417            result.add(n);
418        }
419
420    }
421
422    private static Block calcLatestBlock(Block earliestBlock, boolean scheduleOutOfLoops, Node currentNode, NodeMap<Block> currentNodeMap) {
423        Block block = null;
424        assert currentNode.hasUsages();
425        for (Node usage : currentNode.usages()) {
426            block = calcBlockForUsage(currentNode, usage, block, currentNodeMap);
427            assert checkLatestEarliestRelation(currentNode, earliestBlock, block);
428            if (scheduleOutOfLoops) {
429                while (block.getLoopDepth() > earliestBlock.getLoopDepth() && block != earliestBlock.getDominator()) {
430                    block = block.getDominator();
431                    assert checkLatestEarliestRelation(currentNode, earliestBlock, block);
432                }
433            }
434        }
435        assert block != null : currentNode;
436        return block;
437    }
438
439    private static Block calcBlockForUsage(Node node, Node usage, Block startCurrentBlock, NodeMap<Block> currentNodeMap) {
440        assert !(node instanceof PhiNode);
441        Block currentBlock = startCurrentBlock;
442        if (usage instanceof PhiNode) {
443            // An input to a PhiNode is used at the end of the predecessor block that corresponds to
444            // the PhiNode input. One PhiNode can use an input multiple times.
445            PhiNode phi = (PhiNode) usage;
446            AbstractMergeNode merge = phi.merge();
447            Block mergeBlock = currentNodeMap.get(merge);
448            for (int i = 0; i < phi.valueCount(); ++i) {
449                if (phi.valueAt(i) == node) {
450                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i));
451                }
452            }
453        } else if (usage instanceof AbstractBeginNode) {
454            AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage;
455            if (abstractBeginNode instanceof StartNode) {
456                currentBlock = currentNodeMap.get(abstractBeginNode);
457            } else {
458                currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode).getDominator());
459            }
460        } else {
461            // All other types of usages: Put the input into the same block as the usage.
462            currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(usage));
463        }
464        return currentBlock;
465    }
466
467    private static void scheduleEarliestIterative(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph) {
468
469        BitSet floatingReads = new BitSet(cfg.getBlocks().size());
470
471        // Add begin nodes as the first entry and set the block for phi nodes.
472        for (Block b : cfg.getBlocks()) {
473            AbstractBeginNode beginNode = b.getBeginNode();
474            ArrayList<Node> nodes = new ArrayList<>();
475            nodeToBlock.set(beginNode, b);
476            nodes.add(beginNode);
477            blockToNodes.put(b, nodes);
478
479            if (beginNode instanceof AbstractMergeNode) {
480                AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode;
481                for (PhiNode phi : mergeNode.phis()) {
482                    nodeToBlock.set(phi, b);
483                }
484            } else if (beginNode instanceof LoopExitNode) {
485                LoopExitNode loopExitNode = (LoopExitNode) beginNode;
486                for (ProxyNode proxy : loopExitNode.proxies()) {
487                    nodeToBlock.set(proxy, b);
488                }
489            }
490        }
491
492        NodeStack stack = new NodeStack();
493
494        // Start analysis with control flow ends.
495        for (Block b : cfg.postOrder()) {
496            FixedNode endNode = b.getEndNode();
497            if (isFixedEnd(endNode)) {
498                stack.push(endNode);
499                nodeToBlock.set(endNode, b);
500            }
501        }
502
503        processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
504
505        // Visit back input edges of loop phis.
506        boolean changed;
507        boolean unmarkedPhi;
508        do {
509            changed = false;
510            unmarkedPhi = false;
511            for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
512                for (PhiNode phi : loopBegin.phis()) {
513                    if (visited.isMarked(phi)) {
514                        for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) {
515                            Node node = phi.valueAt(i + loopBegin.forwardEndCount());
516                            if (node != null && !visited.isMarked(node)) {
517                                changed = true;
518                                stack.push(node);
519                                processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
520                            }
521                        }
522                    } else {
523                        unmarkedPhi = true;
524                    }
525                }
526            }
527
528            /*
529             * the processing of one loop phi could have marked a previously checked loop phi,
530             * therefore this needs to be iterative.
531             */
532        } while (unmarkedPhi && changed);
533
534        // Check for dead nodes.
535        if (visited.getCounter() < graph.getNodeCount()) {
536            for (Node n : graph.getNodes()) {
537                if (!visited.isMarked(n)) {
538                    n.clearInputs();
539                    n.markDeleted();
540                }
541            }
542        }
543
544        // Add end nodes as the last nodes in each block.
545        for (Block b : cfg.getBlocks()) {
546            FixedNode endNode = b.getEndNode();
547            if (isFixedEnd(endNode)) {
548                if (endNode != b.getBeginNode()) {
549                    addNode(blockToNodes, b, endNode);
550                }
551            }
552        }
553
554        if (!floatingReads.isEmpty()) {
555            for (Block b : cfg.getBlocks()) {
556                if (floatingReads.get(b.getId())) {
557                    resortEarliestWithinBlock(b, blockToNodes, nodeToBlock, visited);
558                }
559            }
560        }
561
562        assert MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
563    }
564
565    private static boolean isFixedEnd(FixedNode endNode) {
566        return endNode instanceof ControlSplitNode || endNode instanceof ControlSinkNode || endNode instanceof AbstractEndNode;
567    }
568
569    private static void resortEarliestWithinBlock(Block b, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap unprocessed) {
570        ArrayList<FloatingReadNode> watchList = new ArrayList<>();
571        List<Node> oldList = blockToNodes.get(b);
572        AbstractBeginNode beginNode = b.getBeginNode();
573        for (Node n : oldList) {
574            if (n instanceof FloatingReadNode) {
575                FloatingReadNode floatingReadNode = (FloatingReadNode) n;
576                LocationIdentity locationIdentity = floatingReadNode.getLocationIdentity();
577                MemoryNode lastLocationAccess = floatingReadNode.getLastLocationAccess();
578                if (locationIdentity.isMutable() && lastLocationAccess != null) {
579                    ValueNode lastAccessLocation = lastLocationAccess.asNode();
580                    if (nodeToBlock.get(lastAccessLocation) == b && lastAccessLocation != beginNode && !(lastAccessLocation instanceof MemoryPhiNode)) {
581                        // This node's last access location is within this block. Add to watch list
582                        // when processing the last access location.
583                    } else {
584                        watchList.add(floatingReadNode);
585                    }
586                }
587            }
588        }
589
590        ArrayList<Node> newList = new ArrayList<>(oldList.size());
591        assert oldList.get(0) == beginNode;
592        unprocessed.clear(beginNode);
593        newList.add(beginNode);
594        for (int i = 1; i < oldList.size(); ++i) {
595            Node n = oldList.get(i);
596            if (unprocessed.isMarked(n)) {
597                if (n instanceof MemoryNode) {
598                    if (n instanceof MemoryCheckpoint) {
599                        assert n instanceof FixedNode;
600                        if (watchList.size() > 0) {
601                            // Check whether we need to commit reads from the watch list.
602                            checkWatchList(b, nodeToBlock, unprocessed, newList, watchList, n);
603                        }
604                    }
605                    // Add potential dependent reads to the watch list.
606                    for (Node usage : n.usages()) {
607                        if (usage instanceof FloatingReadNode) {
608                            FloatingReadNode floatingReadNode = (FloatingReadNode) usage;
609                            if (nodeToBlock.get(floatingReadNode) == b && floatingReadNode.getLastLocationAccess() == n && !(n instanceof MemoryPhiNode)) {
610                                watchList.add(floatingReadNode);
611                            }
612                        }
613                    }
614                }
615                assert unprocessed.isMarked(n);
616                unprocessed.clear(n);
617                newList.add(n);
618            } else {
619                // This node was pulled up.
620                assert !(n instanceof FixedNode) : n;
621            }
622        }
623
624        for (Node n : newList) {
625            unprocessed.mark(n);
626        }
627
628        assert newList.size() == oldList.size();
629        blockToNodes.put(b, newList);
630    }
631
632    private static void addNode(BlockMap<List<Node>> blockToNodes, Block b, Node endNode) {
633        assert !blockToNodes.get(b).contains(endNode) : endNode;
634        blockToNodes.get(b).add(endNode);
635    }
636
637    private static void processStack(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, BitSet floatingReads, NodeStack stack) {
638        Block startBlock = cfg.getStartBlock();
639        while (!stack.isEmpty()) {
640            Node current = stack.peek();
641            if (visited.checkAndMarkInc(current)) {
642
643                // Push inputs and predecessor.
644                Node predecessor = current.predecessor();
645                if (predecessor != null) {
646                    stack.push(predecessor);
647                }
648
649                if (current instanceof PhiNode) {
650                    PhiNode phiNode = (PhiNode) current;
651                    AbstractMergeNode merge = phiNode.merge();
652                    for (int i = 0; i < merge.forwardEndCount(); ++i) {
653                        Node input = phiNode.valueAt(i);
654                        if (input != null) {
655                            stack.push(input);
656                        }
657                    }
658                } else if (current instanceof ProxyNode) {
659                    ProxyNode proxyNode = (ProxyNode) current;
660                    for (Node input : proxyNode.inputs()) {
661                        if (input != proxyNode.proxyPoint()) {
662                            stack.push(input);
663                        }
664                    }
665                } else if (current instanceof FrameState) {
666                    for (Node input : current.inputs()) {
667                        if (input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) {
668                            // Ignore the cycle.
669                        } else {
670                            stack.push(input);
671                        }
672                    }
673                } else {
674                    current.pushInputs(stack);
675                }
676            } else {
677
678                stack.pop();
679
680                if (nodeToBlock.get(current) == null) {
681                    Block curBlock = cfg.blockFor(current);
682                    if (curBlock == null) {
683                        assert current.predecessor() == null && !(current instanceof FixedNode) : "The assignment of blocks to fixed nodes is already done when constructing the cfg.";
684                        Block earliest = startBlock;
685                        for (Node input : current.inputs()) {
686                            Block inputEarliest = nodeToBlock.get(input);
687                            if (inputEarliest == null) {
688                                assert current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current : current;
689                            } else {
690                                assert inputEarliest != null;
691                                if (inputEarliest.getEndNode() == input) {
692                                    // This is the last node of the block.
693                                    if (current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) {
694                                        // Keep regular inputEarliest.
695                                    } else if (input instanceof ControlSplitNode) {
696                                        inputEarliest = nodeToBlock.get(((ControlSplitNode) input).getPrimarySuccessor());
697                                    } else {
698                                        assert inputEarliest.getSuccessorCount() == 1;
699                                        assert !(input instanceof AbstractEndNode);
700                                        // Keep regular inputEarliest
701                                    }
702                                }
703                                if (earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) {
704                                    earliest = inputEarliest;
705                                }
706                            }
707                        }
708                        curBlock = earliest;
709                    }
710                    assert curBlock != null;
711                    addNode(blockToNodes, curBlock, current);
712                    nodeToBlock.set(current, curBlock);
713                    if (current instanceof FloatingReadNode) {
714                        FloatingReadNode floatingReadNode = (FloatingReadNode) current;
715                        if (curBlock.canKill(floatingReadNode.getLocationIdentity())) {
716                            floatingReads.set(curBlock.getId());
717                        }
718                    }
719                }
720            }
721        }
722    }
723
724    public String printScheduleHelper(String desc) {
725        Formatter buf = new Formatter();
726        buf.format("=== %s / %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, desc);
727        for (Block b : getCFG().getBlocks()) {
728            buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
729            buf.format("dom: %s. ", b.getDominator());
730            buf.format("preds: %s. ", b.getPredecessors());
731            buf.format("succs: %s ====%n", b.getSuccessors());
732            BlockMap<LocationSet> killSets = blockToKillSet;
733            if (killSets != null) {
734                buf.format("X block kills: %n");
735                if (killSets.get(b) != null) {
736                    for (LocationIdentity locId : killSets.get(b).getCopyAsList()) {
737                        buf.format("X %s killed by %s%n", locId, "dunno anymore");
738                    }
739                }
740            }
741
742            if (blockToNodesMap.get(b) != null) {
743                for (Node n : nodesFor(b)) {
744                    printNode(n);
745                }
746            } else {
747                for (Node n : b.getNodes()) {
748                    printNode(n);
749                }
750            }
751        }
752        buf.format("%n");
753        return buf.toString();
754    }
755
756    private static void printNode(Node n) {
757        Formatter buf = new Formatter();
758        buf.format("%s", n);
759        if (n instanceof MemoryCheckpoint.Single) {
760            buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
761        } else if (n instanceof MemoryCheckpoint.Multi) {
762            buf.format(" // kills ");
763            for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
764                buf.format("%s, ", locid);
765            }
766        } else if (n instanceof FloatingReadNode) {
767            FloatingReadNode frn = (FloatingReadNode) n;
768            buf.format(" // from %s", frn.getLocationIdentity());
769            buf.format(", lastAccess: %s", frn.getLastLocationAccess());
770            buf.format(", address: %s", frn.getAddress());
771        } else if (n instanceof GuardNode) {
772            buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
773        }
774        Debug.log("%s", buf);
775    }
776
777    public ControlFlowGraph getCFG() {
778        return cfg;
779    }
780
781    /**
782     * Gets the map from each block to the nodes in the block.
783     */
784    public BlockMap<List<Node>> getBlockToNodesMap() {
785        return blockToNodesMap;
786    }
787
788    public NodeMap<Block> getNodeToBlockMap() {
789        return this.nodeToBlockMap;
790    }
791
792    /**
793     * Gets the nodes in a given block.
794     */
795    public List<Node> nodesFor(Block block) {
796        return blockToNodesMap.get(block);
797    }
798}