1 /*
2 * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.phases.schedule;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.OptScheduleOutOfLoops;
26 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
27
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.BitSet;
31 import java.util.Formatter;
32 import java.util.List;
33
34 import org.graalvm.compiler.core.common.LocationIdentity;
35 import org.graalvm.compiler.core.common.SuppressFBWarnings;
36 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
37 import org.graalvm.compiler.core.common.cfg.BlockMap;
38 import org.graalvm.compiler.debug.Debug;
39 import org.graalvm.compiler.graph.Graph.NodeEvent;
40 import org.graalvm.compiler.graph.Graph.NodeEventListener;
41 import org.graalvm.compiler.graph.Graph.NodeEventScope;
42 import org.graalvm.compiler.graph.Node;
43 import org.graalvm.compiler.graph.NodeBitMap;
44 import org.graalvm.compiler.graph.NodeMap;
45 import org.graalvm.compiler.graph.NodeStack;
46 import org.graalvm.compiler.nodes.AbstractBeginNode;
47 import org.graalvm.compiler.nodes.AbstractEndNode;
48 import org.graalvm.compiler.nodes.AbstractMergeNode;
49 import org.graalvm.compiler.nodes.ControlSinkNode;
50 import org.graalvm.compiler.nodes.ControlSplitNode;
51 import org.graalvm.compiler.nodes.DeoptimizeNode;
52 import org.graalvm.compiler.nodes.FixedNode;
53 import org.graalvm.compiler.nodes.FrameState;
54 import org.graalvm.compiler.nodes.GuardNode;
55 import org.graalvm.compiler.nodes.LoopBeginNode;
56 import org.graalvm.compiler.nodes.LoopExitNode;
57 import org.graalvm.compiler.nodes.PhiNode;
58 import org.graalvm.compiler.nodes.ProxyNode;
59 import org.graalvm.compiler.nodes.StartNode;
60 import org.graalvm.compiler.nodes.StateSplit;
61 import org.graalvm.compiler.nodes.StructuredGraph;
62 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
63 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
64 import org.graalvm.compiler.nodes.ValueNode;
65 import org.graalvm.compiler.nodes.VirtualState;
66 import org.graalvm.compiler.nodes.cfg.Block;
67 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
68 import org.graalvm.compiler.nodes.cfg.HIRLoop;
69 import org.graalvm.compiler.nodes.cfg.LocationSet;
70 import org.graalvm.compiler.nodes.memory.FloatingReadNode;
71 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
72 import org.graalvm.compiler.nodes.memory.MemoryNode;
73 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
74 import org.graalvm.compiler.phases.Phase;
75
76 public final class SchedulePhase extends Phase {
77
78 public enum SchedulingStrategy {
79 EARLIEST,
80 LATEST,
81 LATEST_OUT_OF_LOOPS,
82 FINAL_SCHEDULE
83 }
84
85 private final SchedulingStrategy selectedStrategy;
86
87 private final boolean immutableGraph;
88
89 public SchedulePhase() {
90 this(false);
91 }
92
93 public SchedulePhase(boolean immutableGraph) {
94 this(OptScheduleOutOfLoops.getValue() ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST, immutableGraph);
95 }
96
97 public SchedulePhase(SchedulingStrategy strategy) {
98 this(strategy, false);
99 }
100
101 public SchedulePhase(SchedulingStrategy strategy, boolean immutableGraph) {
102 this.selectedStrategy = strategy;
103 this.immutableGraph = immutableGraph;
104 }
105
106 private NodeEventScope verifyImmutableGraph(StructuredGraph graph) {
107 boolean assertionsEnabled = false;
108 assert (assertionsEnabled = true) == true;
109 if (immutableGraph && assertionsEnabled) {
110 return graph.trackNodeEvents(new NodeEventListener() {
111 @Override
112 public void event(NodeEvent e, Node node) {
113 assert false : "graph changed: " + e + " on node " + node;
114 }
115 });
116 } else {
117 return null;
118 }
119 }
120
121 @Override
122 @SuppressWarnings("try")
123 protected void run(StructuredGraph graph) {
124 try (NodeEventScope scope = verifyImmutableGraph(graph)) {
125 Instance inst = new Instance();
126 inst.run(graph, selectedStrategy, immutableGraph);
127 }
128 }
129
130 public static class Instance {
131
132 /**
133 * Map from blocks to the nodes in each block.
134 */
135 protected ControlFlowGraph cfg;
136 protected BlockMap<List<Node>> blockToNodesMap;
137 protected NodeMap<Block> nodeToBlockMap;
138
139 @SuppressWarnings("try")
140 public void run(StructuredGraph graph, SchedulingStrategy selectedStrategy, boolean immutableGraph) {
141 // assert GraphOrder.assertNonCyclicGraph(graph);
142 cfg = ControlFlowGraph.compute(graph, true, true, true, false);
143
144 NodeMap<Block> currentNodeMap = graph.createNodeMap();
145 NodeBitMap visited = graph.createNodeBitMap();
146 BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
147 this.nodeToBlockMap = currentNodeMap;
148 this.blockToNodesMap = earliestBlockToNodesMap;
149
150 scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph);
151
152 if (selectedStrategy != SchedulingStrategy.EARLIEST) {
153 // For non-earliest schedules, we need to do a second pass.
154 BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
155 for (Block b : cfg.getBlocks()) {
156 latestBlockToNodesMap.put(b, new ArrayList<Node>());
157 }
158
159 BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(selectedStrategy, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap, immutableGraph);
160 sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
161
162 assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
163 assert MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);
164
165 this.blockToNodesMap = latestBlockToNodesMap;
166
167 cfg.setNodeToBlock(currentNodeMap);
168 }
169
170 graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));
171 }
172
173 @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")
174 private BlockMap<ArrayList<FloatingReadNode>> calcLatestBlocks(SchedulingStrategy strategy, NodeMap<Block> currentNodeMap, BlockMap<List<Node>> earliestBlockToNodesMap, NodeBitMap visited,
175 BlockMap<List<Node>> latestBlockToNodesMap, boolean immutableGraph) {
176 BlockMap<ArrayList<FloatingReadNode>> watchListMap = new BlockMap<>(cfg);
177 Block[] reversePostOrder = cfg.reversePostOrder();
178 for (int j = reversePostOrder.length - 1; j >= 0; --j) {
179 Block currentBlock = reversePostOrder[j];
180 List<Node> blockToNodes = earliestBlockToNodesMap.get(currentBlock);
181 LocationSet killed = null;
182 int previousIndex = blockToNodes.size();
183 for (int i = blockToNodes.size() - 1; i >= 0; --i) {
184 Node currentNode = blockToNodes.get(i);
185 assert currentNodeMap.get(currentNode) == currentBlock;
186 assert !(currentNode instanceof PhiNode) && !(currentNode instanceof ProxyNode);
187 assert visited.isMarked(currentNode);
188 if (currentNode instanceof FixedNode) {
189 // For these nodes, the earliest is at the same time the latest block.
190 } else {
191 Block latestBlock = null;
192
193 LocationIdentity constrainingLocation = null;
194 if (currentNode instanceof FloatingReadNode) {
195 // We are scheduling a floating read node => check memory
196 // anti-dependencies.
197 FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;
198 LocationIdentity location = floatingReadNode.getLocationIdentity();
199 if (location.isMutable()) {
200 // Location can be killed.
201 constrainingLocation = location;
202 if (currentBlock.canKill(location)) {
203 if (killed == null) {
204 killed = new LocationSet();
205 }
206 fillKillSet(killed, blockToNodes.subList(i + 1, previousIndex));
207 previousIndex = i;
208 if (killed.contains(location)) {
209 // Earliest block kills location => we need to stay within
210 // earliest block.
211 latestBlock = currentBlock;
212 }
213 }
214 }
215 }
216
217 if (latestBlock == null) {
218 // We are not constraint within earliest block => calculate optimized
219 // schedule.
220 calcLatestBlock(currentBlock, strategy, currentNode, currentNodeMap, constrainingLocation, watchListMap, latestBlockToNodesMap, visited, immutableGraph);
221 } else {
222 selectLatestBlock(currentNode, currentBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);
223 }
224 }
225 }
226 }
227 return watchListMap;
228 }
229
230 protected static void selectLatestBlock(Node currentNode, Block currentBlock, Block latestBlock, NodeMap<Block> currentNodeMap, BlockMap<ArrayList<FloatingReadNode>> watchListMap,
231 LocationIdentity constrainingLocation, BlockMap<List<Node>> latestBlockToNodesMap) {
232
233 assert checkLatestEarliestRelation(currentNode, currentBlock, latestBlock);
234 if (currentBlock != latestBlock) {
235 currentNodeMap.setAndGrow(currentNode, latestBlock);
236
237 if (constrainingLocation != null && latestBlock.canKill(constrainingLocation)) {
238 if (watchListMap.get(latestBlock) == null) {
239 watchListMap.put(latestBlock, new ArrayList<>());
240 }
241 watchListMap.get(latestBlock).add((FloatingReadNode) currentNode);
242 }
243 }
244
245 latestBlockToNodesMap.get(latestBlock).add(currentNode);
246 }
247
248 private static boolean checkLatestEarliestRelation(Node currentNode, Block earliestBlock, Block latestBlock) {
249 assert AbstractControlFlowGraph.dominates(earliestBlock, latestBlock) || (currentNode instanceof VirtualState && latestBlock == earliestBlock.getDominator()) : String.format(
250 "%s %s (%s) %s (%s)", currentNode, earliestBlock, earliestBlock.getBeginNode(), latestBlock, latestBlock.getBeginNode());
251 return true;
252 }
253
254 private static boolean verifySchedule(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) {
255 for (Block b : cfg.getBlocks()) {
256 List<Node> nodes = blockToNodesMap.get(b);
257 for (Node n : nodes) {
258 assert n.isAlive();
259 assert nodeMap.get(n) == b;
260 StructuredGraph g = (StructuredGraph) n.graph();
261 if (g.hasLoops() && g.getGuardsStage() == GuardsStage.AFTER_FSA && n instanceof DeoptimizeNode) {
262 assert b.getLoopDepth() == 0 : n;
263 }
264 }
265 }
266 return true;
267 }
268
269 public static Block checkKillsBetween(Block earliestBlock, Block latestBlock, LocationIdentity location) {
270 assert strictlyDominates(earliestBlock, latestBlock);
271 Block current = latestBlock.getDominator();
272
273 // Collect dominator chain that needs checking.
274 List<Block> dominatorChain = new ArrayList<>();
275 dominatorChain.add(latestBlock);
276 while (current != earliestBlock) {
277 // Current is an intermediate dominator between earliestBlock and latestBlock.
278 assert strictlyDominates(earliestBlock, current) && strictlyDominates(current, latestBlock);
279 if (current.canKill(location)) {
280 dominatorChain.clear();
281 }
282 dominatorChain.add(current);
283 current = current.getDominator();
284 }
285
286 // The first element of dominatorChain now contains the latest possible block.
287 assert dominatorChain.size() >= 1;
288 assert dominatorChain.get(dominatorChain.size() - 1).getDominator() == earliestBlock;
289
290 Block lastBlock = earliestBlock;
291 for (int i = dominatorChain.size() - 1; i >= 0; --i) {
292 Block currentBlock = dominatorChain.get(i);
293 if (currentBlock.getLoopDepth() > lastBlock.getLoopDepth()) {
294 // We are entering a loop boundary. The new loops must not kill the location for
295 // the crossing to be safe.
296 if (currentBlock.getLoop() != null && ((HIRLoop) currentBlock.getLoop()).canKill(location)) {
297 break;
298 }
299 }
300
301 if (currentBlock.canKillBetweenThisAndDominator(location)) {
302 break;
303 }
304 lastBlock = currentBlock;
305 }
306
307 return lastBlock;
308 }
309
310 private static void fillKillSet(LocationSet killed, List<Node> subList) {
311 if (!killed.isAny()) {
312 for (Node n : subList) {
313 // Check if this node kills a node in the watch list.
314 if (n instanceof MemoryCheckpoint.Single) {
315 LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
316 killed.add(identity);
317 if (killed.isAny()) {
318 return;
319 }
320 } else if (n instanceof MemoryCheckpoint.Multi) {
321 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
322 killed.add(identity);
323 if (killed.isAny()) {
324 return;
325 }
326 }
327 }
328 }
329 }
330 }
331
332 private static void sortNodesLatestWithinBlock(ControlFlowGraph cfg, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> currentNodeMap,
333 BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap visited) {
334 for (Block b : cfg.getBlocks()) {
335 sortNodesLatestWithinBlock(b, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
336 }
337 }
338
339 private static void sortNodesLatestWithinBlock(Block b, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> nodeMap,
340 BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap unprocessed) {
341 List<Node> earliestSorting = earliestBlockToNodesMap.get(b);
342 ArrayList<Node> result = new ArrayList<>(earliestSorting.size());
343 ArrayList<FloatingReadNode> watchList = null;
344 if (watchListMap != null) {
345 watchList = watchListMap.get(b);
346 assert watchList == null || !b.getKillLocations().isEmpty();
347 }
348 AbstractBeginNode beginNode = b.getBeginNode();
349 if (beginNode instanceof LoopExitNode) {
350 LoopExitNode loopExitNode = (LoopExitNode) beginNode;
351 for (ProxyNode proxy : loopExitNode.proxies()) {
352 unprocessed.clear(proxy);
353 ValueNode value = proxy.value();
354 // if multiple proxies reference the same value, schedule the value of a
355 // proxy once
356 if (value != null && nodeMap.get(value) == b && unprocessed.isMarked(value)) {
357 sortIntoList(value, b, result, nodeMap, unprocessed, null);
358 }
359 }
360 }
361 FixedNode endNode = b.getEndNode();
362 FixedNode fixedEndNode = null;
363 if (isFixedEnd(endNode)) {
364 // Only if the end node is either a control split or an end node, we need to force
365 // it to be the last node in the schedule.
366 fixedEndNode = endNode;
367 }
368 for (Node n : earliestSorting) {
369 if (n != fixedEndNode) {
370 if (n instanceof FixedNode) {
371 assert nodeMap.get(n) == b;
372 checkWatchList(b, nodeMap, unprocessed, result, watchList, n);
373 sortIntoList(n, b, result, nodeMap, unprocessed, null);
374 } else if (nodeMap.get(n) == b && n instanceof FloatingReadNode) {
375 FloatingReadNode floatingReadNode = (FloatingReadNode) n;
376 LocationIdentity location = floatingReadNode.getLocationIdentity();
377 if (b.canKill(location)) {
378 // This read can be killed in this block, add to watch list.
379 if (watchList == null) {
380 watchList = new ArrayList<>();
381 }
382 watchList.add(floatingReadNode);
383 }
384 }
385 }
386 }
387
388 for (Node n : latestBlockToNodesMap.get(b)) {
389 assert nodeMap.get(n) == b : n;
390 assert !(n instanceof FixedNode);
391 if (unprocessed.isMarked(n)) {
392 sortIntoList(n, b, result, nodeMap, unprocessed, fixedEndNode);
393 }
394 }
395
396 if (endNode != null && unprocessed.isMarked(endNode)) {
397 sortIntoList(endNode, b, result, nodeMap, unprocessed, null);
398 }
399
400 latestBlockToNodesMap.put(b, result);
401 }
402
403 private static void checkWatchList(Block b, NodeMap<Block> nodeMap, NodeBitMap unprocessed, ArrayList<Node> result, ArrayList<FloatingReadNode> watchList, Node n) {
404 if (watchList != null && !watchList.isEmpty()) {
405 // Check if this node kills a node in the watch list.
406 if (n instanceof MemoryCheckpoint.Single) {
407 LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
408 checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
409 } else if (n instanceof MemoryCheckpoint.Multi) {
410 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
411 checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
412 }
413 }
414 }
415 }
416
417 private static void checkWatchList(ArrayList<FloatingReadNode> watchList, LocationIdentity identity, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed) {
418 assert identity.isMutable();
419 if (identity.isAny()) {
420 for (FloatingReadNode r : watchList) {
421 if (unprocessed.isMarked(r)) {
422 sortIntoList(r, b, result, nodeMap, unprocessed, null);
423 }
424 }
425 watchList.clear();
426 } else {
427 int index = 0;
428 while (index < watchList.size()) {
429 FloatingReadNode r = watchList.get(index);
430 LocationIdentity locationIdentity = r.getLocationIdentity();
431 assert locationIdentity.isMutable();
432 if (unprocessed.isMarked(r)) {
433 if (identity.overlaps(locationIdentity)) {
434 sortIntoList(r, b, result, nodeMap, unprocessed, null);
435 } else {
436 ++index;
437 continue;
438 }
439 }
440 int lastIndex = watchList.size() - 1;
441 watchList.set(index, watchList.get(lastIndex));
442 watchList.remove(lastIndex);
443 }
444 }
445 }
446
447 private static void sortIntoList(Node n, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed, Node excludeNode) {
448 assert unprocessed.isMarked(n) : n;
449 assert nodeMap.get(n) == b;
450
451 if (n instanceof PhiNode) {
452 return;
453 }
454
455 unprocessed.clear(n);
456
457 for (Node input : n.inputs()) {
458 if (nodeMap.get(input) == b && unprocessed.isMarked(input) && input != excludeNode) {
459 sortIntoList(input, b, result, nodeMap, unprocessed, excludeNode);
460 }
461 }
462
463 if (n instanceof ProxyNode) {
464 // Skip proxy nodes.
465 } else {
466 result.add(n);
467 }
468
469 }
470
471 protected void calcLatestBlock(Block earliestBlock, SchedulingStrategy strategy, Node currentNode, NodeMap<Block> currentNodeMap, LocationIdentity constrainingLocation,
472 BlockMap<ArrayList<FloatingReadNode>> watchListMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeBitMap visited, boolean immutableGraph) {
473 Block latestBlock = null;
474 assert currentNode.hasUsages();
475 for (Node usage : currentNode.usages()) {
476 if (immutableGraph && !visited.contains(usage)) {
477 /*
478 * Normally, dead nodes are deleted by the scheduler before we reach this point.
479 * Only when the scheduler is asked to not modify a graph, we can see dead nodes
480 * here.
481 */
482 continue;
483 }
484 latestBlock = calcBlockForUsage(currentNode, usage, latestBlock, currentNodeMap);
485 }
486
487 if (strategy == SchedulingStrategy.FINAL_SCHEDULE || strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS) {
488 assert latestBlock != null;
489 while (latestBlock.getLoopDepth() > earliestBlock.getLoopDepth() && latestBlock != earliestBlock.getDominator()) {
490 latestBlock = latestBlock.getDominator();
491 }
492 }
493
494 if (latestBlock != earliestBlock && latestBlock != earliestBlock.getDominator() && constrainingLocation != null) {
495 latestBlock = checkKillsBetween(earliestBlock, latestBlock, constrainingLocation);
496 }
497
498 selectLatestBlock(currentNode, earliestBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);
499 }
500
501 private static Block calcBlockForUsage(Node node, Node usage, Block startBlock, NodeMap<Block> currentNodeMap) {
502 assert !(node instanceof PhiNode);
503 Block currentBlock = startBlock;
504 if (usage instanceof PhiNode) {
505 // An input to a PhiNode is used at the end of the predecessor block that
506 // corresponds to the PhiNode input. One PhiNode can use an input multiple times.
507 PhiNode phi = (PhiNode) usage;
508 AbstractMergeNode merge = phi.merge();
509 Block mergeBlock = currentNodeMap.get(merge);
510 for (int i = 0; i < phi.valueCount(); ++i) {
511 if (phi.valueAt(i) == node) {
512 Block otherBlock = mergeBlock.getPredecessors()[i];
513 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
514 }
515 }
516 } else if (usage instanceof AbstractBeginNode) {
517 AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage;
518 if (abstractBeginNode instanceof StartNode) {
519 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode));
520 } else {
521 Block otherBlock = currentNodeMap.get(abstractBeginNode).getDominator();
522 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
523 }
524 } else {
525 // All other types of usages: Put the input into the same block as the usage.
526 Block otherBlock = currentNodeMap.get(usage);
527 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
528 }
529 return currentBlock;
530 }
531
532 private void scheduleEarliestIterative(BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph, boolean immutableGraph) {
533
534 BitSet floatingReads = new BitSet(cfg.getBlocks().length);
535
536 // Add begin nodes as the first entry and set the block for phi nodes.
537 for (Block b : cfg.getBlocks()) {
538 AbstractBeginNode beginNode = b.getBeginNode();
539 ArrayList<Node> nodes = new ArrayList<>();
540 nodeToBlock.set(beginNode, b);
541 nodes.add(beginNode);
542 blockToNodes.put(b, nodes);
543
544 if (beginNode instanceof AbstractMergeNode) {
545 AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode;
546 for (PhiNode phi : mergeNode.phis()) {
547 nodeToBlock.set(phi, b);
548 }
549 } else if (beginNode instanceof LoopExitNode) {
550 LoopExitNode loopExitNode = (LoopExitNode) beginNode;
551 for (ProxyNode proxy : loopExitNode.proxies()) {
552 nodeToBlock.set(proxy, b);
553 }
554 }
555 }
556
557 NodeStack stack = new NodeStack();
558
559 // Start analysis with control flow ends.
560 Block[] reversePostOrder = cfg.reversePostOrder();
561 for (int j = reversePostOrder.length - 1; j >= 0; --j) {
562 Block b = reversePostOrder[j];
563 FixedNode endNode = b.getEndNode();
564 if (isFixedEnd(endNode)) {
565 stack.push(endNode);
566 nodeToBlock.set(endNode, b);
567 }
568 }
569
570 processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
571
572 // Visit back input edges of loop phis.
573 boolean changed;
574 boolean unmarkedPhi;
575 do {
576 changed = false;
577 unmarkedPhi = false;
578 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
579 for (PhiNode phi : loopBegin.phis()) {
580 if (visited.isMarked(phi)) {
581 for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) {
582 Node node = phi.valueAt(i + loopBegin.forwardEndCount());
583 if (node != null && !visited.isMarked(node)) {
584 changed = true;
585 stack.push(node);
586 processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
587 }
588 }
589 } else {
590 unmarkedPhi = true;
591 }
592 }
593 }
594
595 /*
596 * the processing of one loop phi could have marked a previously checked loop phi,
597 * therefore this needs to be iterative.
598 */
599 } while (unmarkedPhi && changed);
600
601 // Check for dead nodes.
602 if (!immutableGraph && visited.getCounter() < graph.getNodeCount()) {
603 for (Node n : graph.getNodes()) {
604 if (!visited.isMarked(n)) {
605 n.clearInputs();
606 n.markDeleted();
607 }
608 }
609 }
610
611 // Add end nodes as the last nodes in each block.
612 for (Block b : cfg.getBlocks()) {
613 FixedNode endNode = b.getEndNode();
614 if (isFixedEnd(endNode)) {
615 if (endNode != b.getBeginNode()) {
616 addNode(blockToNodes, b, endNode);
617 }
618 }
619 }
620
621 if (!floatingReads.isEmpty()) {
622 for (Block b : cfg.getBlocks()) {
623 if (floatingReads.get(b.getId())) {
624 resortEarliestWithinBlock(b, blockToNodes, nodeToBlock, visited);
625 }
626 }
627 }
628
629 assert MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
630 }
631
632 private static boolean isFixedEnd(FixedNode endNode) {
633 return endNode instanceof ControlSplitNode || endNode instanceof ControlSinkNode || endNode instanceof AbstractEndNode;
634 }
635
636 private static void resortEarliestWithinBlock(Block b, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap unprocessed) {
637 ArrayList<FloatingReadNode> watchList = new ArrayList<>();
638 List<Node> oldList = blockToNodes.get(b);
639 AbstractBeginNode beginNode = b.getBeginNode();
640 for (Node n : oldList) {
641 if (n instanceof FloatingReadNode) {
642 FloatingReadNode floatingReadNode = (FloatingReadNode) n;
643 LocationIdentity locationIdentity = floatingReadNode.getLocationIdentity();
644 MemoryNode lastLocationAccess = floatingReadNode.getLastLocationAccess();
645 if (locationIdentity.isMutable() && lastLocationAccess != null) {
646 ValueNode lastAccessLocation = lastLocationAccess.asNode();
647 if (nodeToBlock.get(lastAccessLocation) == b && lastAccessLocation != beginNode && !(lastAccessLocation instanceof MemoryPhiNode)) {
648 // This node's last access location is within this block. Add to watch
649 // list when processing the last access location.
650 } else {
651 watchList.add(floatingReadNode);
652 }
653 }
654 }
655 }
656
657 ArrayList<Node> newList = new ArrayList<>(oldList.size());
658 assert oldList.get(0) == beginNode;
659 unprocessed.clear(beginNode);
660 newList.add(beginNode);
661 for (int i = 1; i < oldList.size(); ++i) {
662 Node n = oldList.get(i);
663 if (unprocessed.isMarked(n)) {
664 if (n instanceof MemoryNode) {
665 if (n instanceof MemoryCheckpoint) {
666 assert n instanceof FixedNode;
667 if (watchList.size() > 0) {
668 // Check whether we need to commit reads from the watch list.
669 checkWatchList(b, nodeToBlock, unprocessed, newList, watchList, n);
670 }
671 }
672 // Add potential dependent reads to the watch list.
673 for (Node usage : n.usages()) {
674 if (usage instanceof FloatingReadNode) {
675 FloatingReadNode floatingReadNode = (FloatingReadNode) usage;
676 if (nodeToBlock.get(floatingReadNode) == b && floatingReadNode.getLastLocationAccess() == n && !(n instanceof MemoryPhiNode)) {
677 watchList.add(floatingReadNode);
678 }
679 }
680 }
681 }
682 assert unprocessed.isMarked(n);
683 unprocessed.clear(n);
684 newList.add(n);
685 } else {
686 // This node was pulled up.
687 assert !(n instanceof FixedNode) : n;
688 }
689 }
690
691 for (Node n : newList) {
692 unprocessed.mark(n);
693 }
694
695 assert newList.size() == oldList.size();
696 blockToNodes.put(b, newList);
697 }
698
699 private static void addNode(BlockMap<List<Node>> blockToNodes, Block b, Node endNode) {
700 assert !blockToNodes.get(b).contains(endNode) : endNode;
701 blockToNodes.get(b).add(endNode);
702 }
703
704 private static void processStack(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, BitSet floatingReads, NodeStack stack) {
705 Block startBlock = cfg.getStartBlock();
706 while (!stack.isEmpty()) {
707 Node current = stack.peek();
708 if (visited.checkAndMarkInc(current)) {
709
710 // Push inputs and predecessor.
711 Node predecessor = current.predecessor();
712 if (predecessor != null) {
713 stack.push(predecessor);
714 }
715
716 if (current instanceof PhiNode) {
717 processStackPhi(stack, (PhiNode) current);
718 } else if (current instanceof ProxyNode) {
719 processStackProxy(stack, (ProxyNode) current);
720 } else if (current instanceof FrameState) {
721 processStackFrameState(stack, current);
722 } else {
723 current.pushInputs(stack);
724 }
725 } else {
726 stack.pop();
727 if (nodeToBlock.get(current) == null) {
728 Block curBlock = cfg.blockFor(current);
729 if (curBlock == null) {
730 assert current.predecessor() == null && !(current instanceof FixedNode) : "The assignment of blocks to fixed nodes is already done when constructing the cfg.";
731 Block earliest = startBlock;
732 for (Node input : current.inputs()) {
733 Block inputEarliest = nodeToBlock.get(input);
734 if (inputEarliest == null) {
735 assert current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current : current;
736 } else {
737 assert inputEarliest != null;
738 if (inputEarliest.getEndNode() == input) {
739 // This is the last node of the block.
740 if (current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) {
741 // Keep regular inputEarliest.
742 } else if (input instanceof ControlSplitNode) {
743 inputEarliest = nodeToBlock.get(((ControlSplitNode) input).getPrimarySuccessor());
744 } else {
745 assert inputEarliest.getSuccessorCount() == 1;
746 assert !(input instanceof AbstractEndNode);
747 // Keep regular inputEarliest
748 }
749 }
750 if (earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) {
751 earliest = inputEarliest;
752 }
753 }
754 }
755 curBlock = earliest;
756 }
757 assert curBlock != null;
758 addNode(blockToNodes, curBlock, current);
759 nodeToBlock.set(current, curBlock);
760 if (current instanceof FloatingReadNode) {
761 FloatingReadNode floatingReadNode = (FloatingReadNode) current;
762 if (curBlock.canKill(floatingReadNode.getLocationIdentity())) {
763 floatingReads.set(curBlock.getId());
764 }
765 }
766 }
767 }
768 }
769 }
770
771 private static void processStackFrameState(NodeStack stack, Node current) {
772 for (Node input : current.inputs()) {
773 if (input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) {
774 // Ignore the cycle.
775 } else {
776 stack.push(input);
777 }
778 }
779 }
780
781 private static void processStackProxy(NodeStack stack, ProxyNode proxyNode) {
782 LoopExitNode proxyPoint = proxyNode.proxyPoint();
783 for (Node input : proxyNode.inputs()) {
784 if (input != proxyPoint) {
785 stack.push(input);
786 }
787 }
788 }
789
790 private static void processStackPhi(NodeStack stack, PhiNode phiNode) {
791 AbstractMergeNode merge = phiNode.merge();
792 for (int i = 0; i < merge.forwardEndCount(); ++i) {
793 Node input = phiNode.valueAt(i);
794 if (input != null) {
795 stack.push(input);
796 }
797 }
798 }
799
800 public String printScheduleHelper(String desc) {
801 Formatter buf = new Formatter();
802 buf.format("=== %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), desc);
803 for (Block b : getCFG().getBlocks()) {
804 buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
805 buf.format("dom: %s. ", b.getDominator());
806 buf.format("preds: %s. ", Arrays.toString(b.getPredecessors()));
807 buf.format("succs: %s ====%n", Arrays.toString(b.getSuccessors()));
808
809 if (blockToNodesMap.get(b) != null) {
810 for (Node n : nodesFor(b)) {
811 printNode(n);
812 }
813 } else {
814 for (Node n : b.getNodes()) {
815 printNode(n);
816 }
817 }
818 }
819 buf.format("%n");
820 return buf.toString();
821 }
822
823 private static void printNode(Node n) {
824 Formatter buf = new Formatter();
825 buf.format("%s", n);
826 if (n instanceof MemoryCheckpoint.Single) {
827 buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
828 } else if (n instanceof MemoryCheckpoint.Multi) {
829 buf.format(" // kills ");
830 for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
831 buf.format("%s, ", locid);
832 }
833 } else if (n instanceof FloatingReadNode) {
834 FloatingReadNode frn = (FloatingReadNode) n;
835 buf.format(" // from %s", frn.getLocationIdentity());
836 buf.format(", lastAccess: %s", frn.getLastLocationAccess());
837 buf.format(", address: %s", frn.getAddress());
838 } else if (n instanceof GuardNode) {
839 buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
840 }
841 Debug.log("%s", buf);
842 }
843
844 public ControlFlowGraph getCFG() {
845 return cfg;
846 }
847
848 /**
849 * Gets the nodes in a given block.
850 */
851 public List<Node> nodesFor(Block block) {
852 return blockToNodesMap.get(block);
853 }
854 }
855
856 }