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
24
25 package org.graalvm.compiler.phases.schedule;
26
27 import static jdk.internal.vm.compiler.collections.Equivalence.IDENTITY;
28 import static org.graalvm.compiler.core.common.GraalOptions.GuardPriorities;
29 import static org.graalvm.compiler.core.common.GraalOptions.OptScheduleOutOfLoops;
30 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
31
32 import java.util.ArrayList;
33 import java.util.Arrays;
34 import java.util.Comparator;
35 import java.util.EnumMap;
36 import java.util.Formatter;
37 import java.util.Iterator;
38 import java.util.List;
39 import java.util.SortedSet;
40 import java.util.TreeSet;
41 import java.util.function.Function;
42
43 import jdk.internal.vm.compiler.collections.EconomicSet;
44 import org.graalvm.compiler.core.common.SuppressFBWarnings;
45 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
46 import org.graalvm.compiler.core.common.cfg.BlockMap;
47 import org.graalvm.compiler.debug.Assertions;
48 import org.graalvm.compiler.graph.Graph.NodeEvent;
49 import org.graalvm.compiler.graph.Graph.NodeEventListener;
50 import org.graalvm.compiler.graph.Graph.NodeEventScope;
51 import org.graalvm.compiler.graph.Node;
52 import org.graalvm.compiler.graph.NodeBitMap;
53 import org.graalvm.compiler.graph.NodeMap;
54 import org.graalvm.compiler.graph.NodeStack;
55 import org.graalvm.compiler.nodes.AbstractBeginNode;
56 import org.graalvm.compiler.nodes.AbstractEndNode;
57 import org.graalvm.compiler.nodes.AbstractMergeNode;
58 import org.graalvm.compiler.nodes.ControlSinkNode;
59 import org.graalvm.compiler.nodes.ControlSplitNode;
60 import org.graalvm.compiler.nodes.DeoptimizeNode;
61 import org.graalvm.compiler.nodes.FixedNode;
62 import org.graalvm.compiler.nodes.GuardNode;
63 import org.graalvm.compiler.nodes.IfNode;
64 import org.graalvm.compiler.nodes.KillingBeginNode;
65 import org.graalvm.compiler.nodes.LoopBeginNode;
66 import org.graalvm.compiler.nodes.LoopExitNode;
67 import org.graalvm.compiler.nodes.PhiNode;
68 import org.graalvm.compiler.nodes.ProxyNode;
69 import org.graalvm.compiler.nodes.StartNode;
70 import org.graalvm.compiler.nodes.StaticDeoptimizingNode;
71 import org.graalvm.compiler.nodes.StaticDeoptimizingNode.GuardPriority;
72 import org.graalvm.compiler.nodes.StructuredGraph;
73 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
74 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
75 import org.graalvm.compiler.nodes.ValueNode;
76 import org.graalvm.compiler.nodes.VirtualState;
77 import org.graalvm.compiler.nodes.calc.ConvertNode;
78 import org.graalvm.compiler.nodes.calc.IsNullNode;
79 import org.graalvm.compiler.nodes.cfg.Block;
80 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
81 import org.graalvm.compiler.nodes.cfg.HIRLoop;
82 import org.graalvm.compiler.nodes.cfg.LocationSet;
83 import org.graalvm.compiler.nodes.memory.FloatingReadNode;
84 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
85 import org.graalvm.compiler.nodes.spi.ValueProxy;
86 import org.graalvm.compiler.options.OptionValues;
87 import org.graalvm.compiler.phases.Phase;
88 import jdk.internal.vm.compiler.word.LocationIdentity;
89
90 public final class SchedulePhase extends Phase {
91
92 public enum SchedulingStrategy {
93 EARLIEST_WITH_GUARD_ORDER,
94 EARLIEST,
95 LATEST,
96 LATEST_OUT_OF_LOOPS,
97 FINAL_SCHEDULE;
98
99 public boolean isEarliest() {
100 return this == EARLIEST || this == EARLIEST_WITH_GUARD_ORDER;
101 }
102
103 public boolean isLatest() {
104 return !isEarliest();
105 }
106 }
107
108 private final SchedulingStrategy selectedStrategy;
109
110 private final boolean immutableGraph;
111
112 public SchedulePhase(OptionValues options) {
113 this(false, options);
114 }
115
116 public SchedulePhase(boolean immutableGraph, OptionValues options) {
117 this(OptScheduleOutOfLoops.getValue(options) ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST, immutableGraph);
118 }
119
120 public SchedulePhase(SchedulingStrategy strategy) {
121 this(strategy, false);
122 }
123
124 public SchedulePhase(SchedulingStrategy strategy, boolean immutableGraph) {
125 this.selectedStrategy = strategy;
126 this.immutableGraph = immutableGraph;
127 }
128
129 private NodeEventScope verifyImmutableGraph(StructuredGraph graph) {
130 if (immutableGraph && Assertions.assertionsEnabled()) {
131 return graph.trackNodeEvents(new NodeEventListener() {
132 @Override
133 public void changed(NodeEvent e, Node node) {
134 assert false : "graph changed: " + e + " on node " + node;
135 }
136 });
137 } else {
138 return null;
139 }
140 }
141
142 @Override
143 @SuppressWarnings("try")
144 protected void run(StructuredGraph graph) {
145 try (NodeEventScope scope = verifyImmutableGraph(graph)) {
146 Instance inst = new Instance();
147 inst.run(graph, selectedStrategy, immutableGraph);
148 }
149 }
150
151 public static void run(StructuredGraph graph, SchedulingStrategy strategy, ControlFlowGraph cfg) {
152 Instance inst = new Instance(cfg);
153 inst.run(graph, strategy, false);
154 }
155
156 public static class Instance {
157
158 private static final double IMPLICIT_NULL_CHECK_OPPORTUNITY_PROBABILITY_FACTOR = 2;
159 /**
160 * Map from blocks to the nodes in each block.
161 */
162 protected ControlFlowGraph cfg;
163 protected BlockMap<List<Node>> blockToNodesMap;
164 protected NodeMap<Block> nodeToBlockMap;
165
166 public Instance() {
167 this(null);
168 }
169
170 public Instance(ControlFlowGraph cfg) {
171 this.cfg = cfg;
172 }
173
174 @SuppressWarnings("try")
175 public void run(StructuredGraph graph, SchedulingStrategy selectedStrategy, boolean immutableGraph) {
176 // assert GraphOrder.assertNonCyclicGraph(graph);
177
178 if (this.cfg == null) {
179 this.cfg = ControlFlowGraph.compute(graph, true, true, true, false);
180 }
181
182 NodeMap<Block> currentNodeMap = graph.createNodeMap();
183 NodeBitMap visited = graph.createNodeBitMap();
184 BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
185 this.nodeToBlockMap = currentNodeMap;
186 this.blockToNodesMap = earliestBlockToNodesMap;
187
188 scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph, selectedStrategy == SchedulingStrategy.EARLIEST_WITH_GUARD_ORDER);
189
190 if (!selectedStrategy.isEarliest()) {
191 // For non-earliest schedules, we need to do a second pass.
192 BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
193 for (Block b : cfg.getBlocks()) {
194 latestBlockToNodesMap.put(b, new ArrayList<>());
195 }
196
197 BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(selectedStrategy, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap, immutableGraph);
198 sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
199
200 assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
201 assert (!Assertions.detailedAssertionsEnabled(graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);
202
203 this.blockToNodesMap = latestBlockToNodesMap;
204
205 }
206 cfg.setNodeToBlock(currentNodeMap);
207
208 graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));
209 }
210
211 @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")
212 private BlockMap<ArrayList<FloatingReadNode>> calcLatestBlocks(SchedulingStrategy strategy, NodeMap<Block> currentNodeMap, BlockMap<List<Node>> earliestBlockToNodesMap, NodeBitMap visited,
213 BlockMap<List<Node>> latestBlockToNodesMap, boolean immutableGraph) {
214 BlockMap<ArrayList<FloatingReadNode>> watchListMap = new BlockMap<>(cfg);
215 Block[] reversePostOrder = cfg.reversePostOrder();
216 for (int j = reversePostOrder.length - 1; j >= 0; --j) {
217 Block currentBlock = reversePostOrder[j];
218 List<Node> blockToNodes = earliestBlockToNodesMap.get(currentBlock);
219 LocationSet killed = null;
220 int previousIndex = blockToNodes.size();
221 for (int i = blockToNodes.size() - 1; i >= 0; --i) {
222 Node currentNode = blockToNodes.get(i);
223 assert currentNodeMap.get(currentNode) == currentBlock;
224 assert !(currentNode instanceof PhiNode) && !(currentNode instanceof ProxyNode);
225 assert visited.isMarked(currentNode);
226 if (currentNode instanceof FixedNode) {
227 // For these nodes, the earliest is at the same time the latest block.
228 } else {
229 Block latestBlock = null;
230
231 LocationIdentity constrainingLocation = null;
232 if (currentNode instanceof FloatingReadNode) {
233 // We are scheduling a floating read node => check memory
234 // anti-dependencies.
235 FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;
236 LocationIdentity location = floatingReadNode.getLocationIdentity();
237 if (location.isMutable()) {
238 // Location can be killed.
239 constrainingLocation = location;
240 if (currentBlock.canKill(location)) {
241 if (killed == null) {
242 killed = new LocationSet();
243 }
244 fillKillSet(killed, blockToNodes.subList(i + 1, previousIndex));
245 previousIndex = i;
246 if (killed.contains(location)) {
247 // Earliest block kills location => we need to stay within
248 // earliest block.
249 latestBlock = currentBlock;
250 }
251 }
252 }
253 }
254
255 if (latestBlock == null) {
256 // We are not constraint within earliest block => calculate optimized
257 // schedule.
258 calcLatestBlock(currentBlock, strategy, currentNode, currentNodeMap, constrainingLocation, watchListMap, latestBlockToNodesMap, visited, immutableGraph);
259 } else {
260 selectLatestBlock(currentNode, currentBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);
261 }
262 }
263 }
264 }
265 return watchListMap;
266 }
267
268 protected static void selectLatestBlock(Node currentNode, Block currentBlock, Block latestBlock, NodeMap<Block> currentNodeMap, BlockMap<ArrayList<FloatingReadNode>> watchListMap,
269 LocationIdentity constrainingLocation, BlockMap<List<Node>> latestBlockToNodesMap) {
270
271 assert checkLatestEarliestRelation(currentNode, currentBlock, latestBlock);
272 if (currentBlock != latestBlock) {
273
274 currentNodeMap.setAndGrow(currentNode, latestBlock);
275
276 if (constrainingLocation != null && latestBlock.canKill(constrainingLocation)) {
277 if (watchListMap.get(latestBlock) == null) {
278 watchListMap.put(latestBlock, new ArrayList<>());
279 }
280 watchListMap.get(latestBlock).add((FloatingReadNode) currentNode);
281 }
282 }
283
284 latestBlockToNodesMap.get(latestBlock).add(currentNode);
285 }
286
287 private static boolean checkLatestEarliestRelation(Node currentNode, Block earliestBlock, Block latestBlock) {
288 assert AbstractControlFlowGraph.dominates(earliestBlock, latestBlock) || (currentNode instanceof VirtualState && latestBlock == earliestBlock.getDominator()) : String.format(
289 "%s %s (%s) %s (%s)", currentNode, earliestBlock, earliestBlock.getBeginNode(), latestBlock, latestBlock.getBeginNode());
290 return true;
291 }
292
293 private static boolean verifySchedule(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) {
294 for (Block b : cfg.getBlocks()) {
295 List<Node> nodes = blockToNodesMap.get(b);
296 for (Node n : nodes) {
297 assert n.isAlive();
298 assert nodeMap.get(n) == b;
299 StructuredGraph g = (StructuredGraph) n.graph();
300 if (g.hasLoops() && g.getGuardsStage() == GuardsStage.AFTER_FSA && n instanceof DeoptimizeNode) {
301 assert b.getLoopDepth() == 0 : n;
302 }
303 }
304 }
305 return true;
306 }
307
308 public static Block checkKillsBetween(Block earliestBlock, Block latestBlock, LocationIdentity location) {
309 assert strictlyDominates(earliestBlock, latestBlock);
310 Block current = latestBlock.getDominator();
311
312 // Collect dominator chain that needs checking.
313 List<Block> dominatorChain = new ArrayList<>();
314 dominatorChain.add(latestBlock);
315 while (current != earliestBlock) {
316 // Current is an intermediate dominator between earliestBlock and latestBlock.
317 assert strictlyDominates(earliestBlock, current) && strictlyDominates(current, latestBlock);
318 if (current.canKill(location)) {
319 dominatorChain.clear();
320 }
321 dominatorChain.add(current);
322 current = current.getDominator();
323 }
324
325 // The first element of dominatorChain now contains the latest possible block.
326 assert dominatorChain.size() >= 1;
327 assert dominatorChain.get(dominatorChain.size() - 1).getDominator() == earliestBlock;
328
329 Block lastBlock = earliestBlock;
330 for (int i = dominatorChain.size() - 1; i >= 0; --i) {
331 Block currentBlock = dominatorChain.get(i);
332 if (currentBlock.getLoopDepth() > lastBlock.getLoopDepth()) {
333 // We are entering a loop boundary. The new loops must not kill the location for
334 // the crossing to be safe.
335 if (currentBlock.getLoop() != null && ((HIRLoop) currentBlock.getLoop()).canKill(location)) {
336 break;
337 }
338 }
339
340 if (currentBlock.canKillBetweenThisAndDominator(location)) {
341 break;
342 }
343 lastBlock = currentBlock;
344 }
345
346 if (lastBlock.getBeginNode() instanceof KillingBeginNode) {
347 LocationIdentity locationIdentity = ((KillingBeginNode) lastBlock.getBeginNode()).getLocationIdentity();
348 if ((locationIdentity.isAny() || locationIdentity.equals(location)) && lastBlock != earliestBlock) {
349 // The begin of this block kills the location, so we *have* to schedule the node
350 // in the dominating block.
351 lastBlock = lastBlock.getDominator();
352 }
353 }
354
355 return lastBlock;
356 }
357
358 private static void fillKillSet(LocationSet killed, List<Node> subList) {
359 if (!killed.isAny()) {
360 for (Node n : subList) {
361 // Check if this node kills a node in the watch list.
362 if (n instanceof MemoryCheckpoint.Single) {
363 LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
364 killed.add(identity);
365 if (killed.isAny()) {
366 return;
367 }
368 } else if (n instanceof MemoryCheckpoint.Multi) {
369 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
370 killed.add(identity);
371 if (killed.isAny()) {
372 return;
373 }
374 }
375 }
376 }
377 }
378 }
379
380 private static void sortNodesLatestWithinBlock(ControlFlowGraph cfg, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> currentNodeMap,
381 BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap visited) {
382 for (Block b : cfg.getBlocks()) {
383 sortNodesLatestWithinBlock(b, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
384 }
385 }
386
387 private static void sortNodesLatestWithinBlock(Block b, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> nodeMap,
388 BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap unprocessed) {
389 List<Node> earliestSorting = earliestBlockToNodesMap.get(b);
390 ArrayList<Node> result = new ArrayList<>(earliestSorting.size());
391 ArrayList<FloatingReadNode> watchList = null;
392 if (watchListMap != null) {
393 watchList = watchListMap.get(b);
394 assert watchList == null || !b.getKillLocations().isEmpty();
395 }
396 AbstractBeginNode beginNode = b.getBeginNode();
397 if (beginNode instanceof LoopExitNode) {
398 LoopExitNode loopExitNode = (LoopExitNode) beginNode;
399 for (ProxyNode proxy : loopExitNode.proxies()) {
400 unprocessed.clear(proxy);
401 ValueNode value = proxy.value();
402 // if multiple proxies reference the same value, schedule the value of a
403 // proxy once
404 if (value != null && nodeMap.get(value) == b && unprocessed.isMarked(value)) {
405 sortIntoList(value, b, result, nodeMap, unprocessed, null);
406 }
407 }
408 }
409 FixedNode endNode = b.getEndNode();
410 FixedNode fixedEndNode = null;
411 if (isFixedEnd(endNode)) {
412 // Only if the end node is either a control split or an end node, we need to force
413 // it to be the last node in the schedule.
414 fixedEndNode = endNode;
415 }
416 for (Node n : earliestSorting) {
417 if (n != fixedEndNode) {
418 if (n instanceof FixedNode) {
419 assert nodeMap.get(n) == b;
420 checkWatchList(b, nodeMap, unprocessed, result, watchList, n);
421 sortIntoList(n, b, result, nodeMap, unprocessed, null);
422 } else if (nodeMap.get(n) == b && n instanceof FloatingReadNode) {
423 FloatingReadNode floatingReadNode = (FloatingReadNode) n;
424 if (isImplicitNullOpportunity(floatingReadNode, b)) {
425 // Schedule at the beginning of the block.
426 sortIntoList(floatingReadNode, b, result, nodeMap, unprocessed, null);
427 } else {
428 LocationIdentity location = floatingReadNode.getLocationIdentity();
429 if (b.canKill(location)) {
430 // This read can be killed in this block, add to watch list.
431 if (watchList == null) {
432 watchList = new ArrayList<>();
433 }
434 watchList.add(floatingReadNode);
435 }
436 }
437 }
438 }
439 }
440
441 for (Node n : latestBlockToNodesMap.get(b)) {
442 assert nodeMap.get(n) == b : n;
443 assert !(n instanceof FixedNode);
444 if (unprocessed.isMarked(n)) {
445 sortIntoList(n, b, result, nodeMap, unprocessed, fixedEndNode);
446 }
447 }
448
449 if (endNode != null && unprocessed.isMarked(endNode)) {
450 sortIntoList(endNode, b, result, nodeMap, unprocessed, null);
451 }
452
453 latestBlockToNodesMap.put(b, result);
454 }
455
456 private static void checkWatchList(Block b, NodeMap<Block> nodeMap, NodeBitMap unprocessed, ArrayList<Node> result, ArrayList<FloatingReadNode> watchList, Node n) {
457 if (watchList != null && !watchList.isEmpty()) {
458 // Check if this node kills a node in the watch list.
459 if (n instanceof MemoryCheckpoint.Single) {
460 LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
461 checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
462 } else if (n instanceof MemoryCheckpoint.Multi) {
463 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
464 checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
465 }
466 }
467 }
468 }
469
470 private static void checkWatchList(ArrayList<FloatingReadNode> watchList, LocationIdentity identity, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed) {
471 if (identity.isImmutable()) {
472 // Nothing to do. This can happen for an initialization write.
473 } else if (identity.isAny()) {
474 for (FloatingReadNode r : watchList) {
475 if (unprocessed.isMarked(r)) {
476 sortIntoList(r, b, result, nodeMap, unprocessed, null);
477 }
478 }
479 watchList.clear();
480 } else {
481 int index = 0;
482 while (index < watchList.size()) {
483 FloatingReadNode r = watchList.get(index);
484 LocationIdentity locationIdentity = r.getLocationIdentity();
485 assert locationIdentity.isMutable();
486 if (unprocessed.isMarked(r)) {
487 if (identity.overlaps(locationIdentity)) {
488 sortIntoList(r, b, result, nodeMap, unprocessed, null);
489 } else {
490 ++index;
491 continue;
492 }
493 }
494 int lastIndex = watchList.size() - 1;
495 watchList.set(index, watchList.get(lastIndex));
496 watchList.remove(lastIndex);
497 }
498 }
499 }
500
501 private static void sortIntoList(Node n, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed, Node excludeNode) {
502 assert unprocessed.isMarked(n) : n;
503 assert nodeMap.get(n) == b;
504
505 if (n instanceof PhiNode) {
506 return;
507 }
508
509 unprocessed.clear(n);
510
511 for (Node input : n.inputs()) {
512 if (nodeMap.get(input) == b && unprocessed.isMarked(input) && input != excludeNode) {
513 sortIntoList(input, b, result, nodeMap, unprocessed, excludeNode);
514 }
515 }
516
517 if (n instanceof ProxyNode) {
518 // Skip proxy nodes.
519 } else {
520 result.add(n);
521 }
522
523 }
524
525 protected void calcLatestBlock(Block earliestBlock, SchedulingStrategy strategy, Node currentNode, NodeMap<Block> currentNodeMap, LocationIdentity constrainingLocation,
526 BlockMap<ArrayList<FloatingReadNode>> watchListMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeBitMap visited, boolean immutableGraph) {
527 Block latestBlock = null;
528 if (!currentNode.hasUsages()) {
529 assert currentNode instanceof GuardNode;
530 latestBlock = earliestBlock;
531 } else {
532 assert currentNode.hasUsages();
533 for (Node usage : currentNode.usages()) {
534 if (immutableGraph && !visited.contains(usage)) {
535 /*
536 * Normally, dead nodes are deleted by the scheduler before we reach this
537 * point. Only when the scheduler is asked to not modify a graph, we can see
538 * dead nodes here.
539 */
540 continue;
541 }
542 latestBlock = calcBlockForUsage(currentNode, usage, latestBlock, currentNodeMap);
543 }
544
545 assert latestBlock != null : currentNode;
546
547 if (strategy == SchedulingStrategy.FINAL_SCHEDULE || strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS) {
548 Block currentBlock = latestBlock;
549 while (currentBlock.getLoopDepth() > earliestBlock.getLoopDepth() && currentBlock != earliestBlock.getDominator()) {
550 Block previousCurrentBlock = currentBlock;
551 currentBlock = currentBlock.getDominator();
552 if (previousCurrentBlock.isLoopHeader()) {
553 if (currentBlock.getRelativeFrequency() < latestBlock.getRelativeFrequency() || ((StructuredGraph) currentNode.graph()).hasValueProxies()) {
554 // Only assign new latest block if frequency is actually lower or if
555 // loop proxies would be required otherwise.
556 latestBlock = currentBlock;
557 }
558 }
559 }
560 }
561
562 if (latestBlock != earliestBlock && latestBlock != earliestBlock.getDominator() && constrainingLocation != null) {
563 latestBlock = checkKillsBetween(earliestBlock, latestBlock, constrainingLocation);
564 }
565 }
566
567 if (latestBlock != earliestBlock && currentNode instanceof FloatingReadNode) {
568
569 FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;
570 if (isImplicitNullOpportunity(floatingReadNode, earliestBlock) &&
571 earliestBlock.getRelativeFrequency() < latestBlock.getRelativeFrequency() * IMPLICIT_NULL_CHECK_OPPORTUNITY_PROBABILITY_FACTOR) {
572 latestBlock = earliestBlock;
573 }
574 }
575
576 selectLatestBlock(currentNode, earliestBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);
577 }
578
579 private static boolean isImplicitNullOpportunity(FloatingReadNode floatingReadNode, Block block) {
580
581 Node pred = block.getBeginNode().predecessor();
582 if (pred instanceof IfNode) {
583 IfNode ifNode = (IfNode) pred;
584 if (ifNode.condition() instanceof IsNullNode) {
585 IsNullNode isNullNode = (IsNullNode) ifNode.condition();
586 if (getUnproxifiedUncompressed(floatingReadNode.getAddress().getBase()) == getUnproxifiedUncompressed(isNullNode.getValue())) {
587 return true;
588 }
589 }
590 }
591 return false;
592 }
593
594 private static Node getUnproxifiedUncompressed(Node node) {
595 Node result = node;
596 while (true) {
597 if (result instanceof ValueProxy) {
598 ValueProxy valueProxy = (ValueProxy) result;
599 result = valueProxy.getOriginalNode();
600 } else if (result instanceof ConvertNode) {
601 ConvertNode convertNode = (ConvertNode) result;
602 if (convertNode.mayNullCheckSkipConversion()) {
603 result = convertNode.getValue();
604 } else {
605 break;
606 }
607 } else {
608 break;
609 }
610 }
611 return result;
612 }
613
614 private static Block calcBlockForUsage(Node node, Node usage, Block startBlock, NodeMap<Block> currentNodeMap) {
615 assert !(node instanceof PhiNode);
616 Block currentBlock = startBlock;
617 if (usage instanceof PhiNode) {
618 // An input to a PhiNode is used at the end of the predecessor block that
619 // corresponds to the PhiNode input. One PhiNode can use an input multiple times.
620 PhiNode phi = (PhiNode) usage;
621 AbstractMergeNode merge = phi.merge();
622 Block mergeBlock = currentNodeMap.get(merge);
623 for (int i = 0; i < phi.valueCount(); ++i) {
624 if (phi.valueAt(i) == node) {
625 Block otherBlock = mergeBlock.getPredecessors()[i];
626 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
627 }
628 }
629 } else if (usage instanceof AbstractBeginNode) {
630 AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage;
631 if (abstractBeginNode instanceof StartNode) {
632 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode));
633 } else {
634 Block otherBlock = currentNodeMap.get(abstractBeginNode).getDominator();
635 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
636 }
637 } else {
638 // All other types of usages: Put the input into the same block as the usage.
639 Block otherBlock = currentNodeMap.get(usage);
640 if (usage instanceof ProxyNode) {
641 ProxyNode proxyNode = (ProxyNode) usage;
642 otherBlock = currentNodeMap.get(proxyNode.proxyPoint());
643
644 }
645 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
646 }
647 return currentBlock;
648 }
649
650 /**
651 * Micro block that is allocated for each fixed node and captures all floating nodes that
652 * need to be scheduled immediately after the corresponding fixed node.
653 */
654 private static class MicroBlock {
655 private final int id;
656 private int nodeCount;
657 private NodeEntry head;
658 private NodeEntry tail;
659
660 MicroBlock(int id) {
661 this.id = id;
662 }
663
664 /**
665 * Adds a new floating node into the micro block.
666 */
667 public void add(Node node) {
668 assert !(node instanceof FixedNode) : node;
669 NodeEntry newTail = new NodeEntry(node);
670 if (tail == null) {
671 tail = head = newTail;
672 } else {
673 tail.next = newTail;
674 tail = newTail;
675 }
676 nodeCount++;
677 }
678
679 /**
680 * Number of nodes in this micro block.
681 */
682 public int getNodeCount() {
683 assert getActualNodeCount() == nodeCount : getActualNodeCount() + " != " + nodeCount;
684 return nodeCount;
685 }
686
687 private int getActualNodeCount() {
688 int count = 0;
689 for (NodeEntry e = head; e != null; e = e.next) {
690 count++;
691 }
692 return count;
693 }
694
695 /**
696 * The id of the micro block, with a block always associated with a lower id than its
697 * successors.
698 */
699 public int getId() {
700 return id;
701 }
702
703 /**
704 * First node of the linked list of nodes of this micro block.
705 */
706 public NodeEntry getFirstNode() {
707 return head;
708 }
709
710 /**
711 * Takes all nodes in this micro blocks and prepends them to the nodes of the given
712 * parameter.
713 *
714 * @param newBlock the new block for the nodes
715 */
716 public void prependChildrenTo(MicroBlock newBlock) {
717 if (tail != null) {
718 assert head != null;
719 tail.next = newBlock.head;
720 newBlock.head = head;
721 head = tail = null;
722 newBlock.nodeCount += nodeCount;
723 nodeCount = 0;
724 }
725 }
726
727 @Override
728 public String toString() {
729 return String.format("MicroBlock[id=%d]", id);
730 }
731
732 @Override
733 public int hashCode() {
734 return id;
735 }
736 }
737
738 /**
739 * Entry in the linked list of nodes.
740 */
741 private static class NodeEntry {
742 private final Node node;
743 private NodeEntry next;
744
745 NodeEntry(Node node) {
746 this.node = node;
747 this.next = null;
748 }
749
750 public NodeEntry getNext() {
751 return next;
752 }
753
754 public Node getNode() {
755 return node;
756 }
757 }
758
759 private void scheduleEarliestIterative(BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph, boolean immutableGraph,
760 boolean withGuardOrder) {
761
762 NodeMap<MicroBlock> entries = graph.createNodeMap();
763 NodeStack stack = new NodeStack();
764
765 // Initialize with fixed nodes.
766 MicroBlock startBlock = null;
767 int nextId = 1;
768 for (Block b : cfg.reversePostOrder()) {
769 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
770 MicroBlock microBlock = new MicroBlock(nextId++);
771 entries.set(current, microBlock);
772 boolean isNew = visited.checkAndMarkInc(current);
773 assert isNew;
774 if (startBlock == null) {
775 startBlock = microBlock;
776 }
777 }
778 }
779
780 if (graph.getGuardsStage().allowsFloatingGuards() && graph.getNodes(GuardNode.TYPE).isNotEmpty()) {
781 // Now process guards.
782 if (GuardPriorities.getValue(graph.getOptions()) && withGuardOrder) {
783 EnumMap<GuardPriority, List<GuardNode>> guardsByPriority = new EnumMap<>(GuardPriority.class);
784 for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
785 guardsByPriority.computeIfAbsent(guard.computePriority(), p -> new ArrayList<>()).add(guard);
786 }
787 // `EnumMap.values` returns values in "natural" key order
788 for (List<GuardNode> guards : guardsByPriority.values()) {
789 processNodes(visited, entries, stack, startBlock, guards);
790 }
791 GuardOrder.resortGuards(graph, entries, stack);
792 } else {
793 processNodes(visited, entries, stack, startBlock, graph.getNodes(GuardNode.TYPE));
794 }
795 } else {
796 assert graph.getNodes(GuardNode.TYPE).isEmpty();
797 }
798
799 // Now process inputs of fixed nodes.
800 for (Block b : cfg.reversePostOrder()) {
801 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
802 processNodes(visited, entries, stack, startBlock, current.inputs());
803 }
804 }
805
806 if (visited.getCounter() < graph.getNodeCount()) {
807 // Visit back input edges of loop phis.
808 boolean changed;
809 boolean unmarkedPhi;
810 do {
811 changed = false;
812 unmarkedPhi = false;
813 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
814 for (PhiNode phi : loopBegin.phis()) {
815 if (visited.isMarked(phi)) {
816 for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) {
817 Node node = phi.valueAt(i + loopBegin.forwardEndCount());
818 if (node != null && entries.get(node) == null) {
819 changed = true;
820 processStack(node, startBlock, entries, visited, stack);
821 }
822 }
823 } else {
824 unmarkedPhi = true;
825 }
826 }
827 }
828
829 /*
830 * the processing of one loop phi could have marked a previously checked loop
831 * phi, therefore this needs to be iterative.
832 */
833 } while (unmarkedPhi && changed);
834 }
835
836 // Check for dead nodes.
837 if (!immutableGraph && visited.getCounter() < graph.getNodeCount()) {
838 for (Node n : graph.getNodes()) {
839 if (!visited.isMarked(n)) {
840 n.clearInputs();
841 n.markDeleted();
842 }
843 }
844 }
845
846 for (Block b : cfg.reversePostOrder()) {
847 FixedNode fixedNode = b.getEndNode();
848 if (fixedNode instanceof ControlSplitNode) {
849 ControlSplitNode controlSplitNode = (ControlSplitNode) fixedNode;
850 MicroBlock endBlock = entries.get(fixedNode);
851 AbstractBeginNode primarySuccessor = controlSplitNode.getPrimarySuccessor();
852 if (primarySuccessor != null) {
853 endBlock.prependChildrenTo(entries.get(primarySuccessor));
854 } else {
855 assert endBlock.tail == null;
856 }
857 }
858 }
859
860 // Create lists for each block
861 for (Block b : cfg.reversePostOrder()) {
862 // Count nodes in block
863 int totalCount = 0;
864 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
865 MicroBlock microBlock = entries.get(current);
866 totalCount += microBlock.getNodeCount() + 1;
867 }
868
869 // Initialize with begin node, it is always the first node.
870 ArrayList<Node> nodes = new ArrayList<>(totalCount);
871 blockToNodes.put(b, nodes);
872
873 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
874 MicroBlock microBlock = entries.get(current);
875 nodeToBlock.set(current, b);
876 nodes.add(current);
877 NodeEntry next = microBlock.getFirstNode();
878 while (next != null) {
879 Node nextNode = next.getNode();
880 nodeToBlock.set(nextNode, b);
881 nodes.add(nextNode);
882 next = next.getNext();
883 }
884 }
885 }
886
887 assert (!Assertions.detailedAssertionsEnabled(cfg.graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
888 }
889
890 private static void processNodes(NodeBitMap visited, NodeMap<MicroBlock> entries, NodeStack stack, MicroBlock startBlock, Iterable<? extends Node> nodes) {
891 for (Node node : nodes) {
892 if (entries.get(node) == null) {
893 processStack(node, startBlock, entries, visited, stack);
894 }
895 }
896 }
897
898 private static void processStackPhi(NodeStack stack, PhiNode phiNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
899 stack.pop();
900 if (visited.checkAndMarkInc(phiNode)) {
901 MicroBlock mergeBlock = nodeToBlock.get(phiNode.merge());
902 assert mergeBlock != null : phiNode;
903 nodeToBlock.set(phiNode, mergeBlock);
904 AbstractMergeNode merge = phiNode.merge();
905 for (int i = 0; i < merge.forwardEndCount(); ++i) {
906 Node input = phiNode.valueAt(i);
907 if (input != null && nodeToBlock.get(input) == null) {
908 stack.push(input);
909 }
910 }
911 }
912 }
913
914 private static void processStackProxy(NodeStack stack, ProxyNode proxyNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
915 stack.pop();
916 if (visited.checkAndMarkInc(proxyNode)) {
917 nodeToBlock.set(proxyNode, nodeToBlock.get(proxyNode.proxyPoint()));
918 Node input = proxyNode.value();
919 if (input != null && nodeToBlock.get(input) == null) {
920 stack.push(input);
921 }
922 }
923 }
924
925 private static void processStack(Node first, MicroBlock startBlock, NodeMap<MicroBlock> nodeToMicroBlock, NodeBitMap visited, NodeStack stack) {
926 assert stack.isEmpty();
927 assert !visited.isMarked(first);
928 stack.push(first);
929 Node current = first;
930 while (true) {
931 if (current instanceof PhiNode) {
932 processStackPhi(stack, (PhiNode) current, nodeToMicroBlock, visited);
933 } else if (current instanceof ProxyNode) {
934 processStackProxy(stack, (ProxyNode) current, nodeToMicroBlock, visited);
935 } else {
936 MicroBlock currentBlock = nodeToMicroBlock.get(current);
937 if (currentBlock == null) {
938 MicroBlock earliestBlock = processInputs(nodeToMicroBlock, stack, startBlock, current);
939 if (earliestBlock == null) {
940 // We need to delay until inputs are processed.
941 } else {
942 // Can immediately process and pop.
943 stack.pop();
944 visited.checkAndMarkInc(current);
945 nodeToMicroBlock.set(current, earliestBlock);
946 earliestBlock.add(current);
947 }
948 } else {
949 stack.pop();
950 }
951 }
952
953 if (stack.isEmpty()) {
954 break;
955 }
956 current = stack.peek();
957 }
958 }
959
960 private static class GuardOrder {
961 /**
962 * After an earliest schedule, this will re-sort guards to honor their
963 * {@linkplain StaticDeoptimizingNode#computePriority() priority}.
964 *
965 * Note that this only changes the order of nodes within {@linkplain MicroBlock
966 * micro-blocks}, nodes will not be moved from one micro-block to another.
967 */
968 private static void resortGuards(StructuredGraph graph, NodeMap<MicroBlock> entries, NodeStack stack) {
969 assert stack.isEmpty();
970 EconomicSet<MicroBlock> blocksWithGuards = EconomicSet.create(IDENTITY);
971 for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
972 MicroBlock block = entries.get(guard);
973 assert block != null : guard + "should already be scheduled to a micro-block";
974 blocksWithGuards.add(block);
975 }
976 assert !blocksWithGuards.isEmpty();
977 NodeMap<GuardPriority> priorities = graph.createNodeMap();
978 NodeBitMap blockNodes = graph.createNodeBitMap();
979 for (MicroBlock block : blocksWithGuards) {
980 MicroBlock newBlock = resortGuards(block, stack, blockNodes, priorities);
981 assert stack.isEmpty();
982 assert blockNodes.isEmpty();
983 if (newBlock != null) {
984 assert block.getNodeCount() == newBlock.getNodeCount();
985 block.head = newBlock.head;
986 block.tail = newBlock.tail;
987 }
988 }
989 }
990
991 /**
992 * This resorts guards within one micro-block.
993 *
994 * {@code stack}, {@code blockNodes} and {@code priorities} are just temporary
995 * data-structures which are allocated once by the callers of this method. They should
996 * be in their "initial"/"empty" state when calling this method and when it returns.
997 */
998 private static MicroBlock resortGuards(MicroBlock block, NodeStack stack, NodeBitMap blockNodes, NodeMap<GuardPriority> priorities) {
999 if (!propagatePriority(block, stack, priorities, blockNodes)) {
1000 return null;
1001 }
1002
1003 Function<GuardNode, GuardPriority> transitiveGuardPriorityGetter = priorities::get;
1004 Comparator<GuardNode> globalGuardPriorityComparator = Comparator.comparing(transitiveGuardPriorityGetter).thenComparing(GuardNode::computePriority).thenComparingInt(Node::hashCode);
1005
1006 SortedSet<GuardNode> availableGuards = new TreeSet<>(globalGuardPriorityComparator);
1007 MicroBlock newBlock = new MicroBlock(block.getId());
1008
1009 NodeBitMap sorted = blockNodes;
1010 sorted.invert();
1011
1012 for (NodeEntry e = block.head; e != null; e = e.next) {
1013 checkIfAvailable(e.node, stack, sorted, newBlock, availableGuards, false);
1014 }
1015 do {
1016 while (!stack.isEmpty()) {
1017 checkIfAvailable(stack.pop(), stack, sorted, newBlock, availableGuards, true);
1018 }
1019 Iterator<GuardNode> iterator = availableGuards.iterator();
1020 if (iterator.hasNext()) {
1021 addNodeToResort(iterator.next(), stack, sorted, newBlock, true);
1022 iterator.remove();
1023 }
1024 } while (!stack.isEmpty() || !availableGuards.isEmpty());
1025
1026 blockNodes.clearAll();
1027 return newBlock;
1028 }
1029
1030 /**
1031 * This checks if {@code n} can be scheduled, if it is the case, it schedules it now by
1032 * calling {@link #addNodeToResort(Node, NodeStack, NodeBitMap, MicroBlock, boolean)}.
1033 */
1034 private static void checkIfAvailable(Node n, NodeStack stack, NodeBitMap sorted, Instance.MicroBlock newBlock, SortedSet<GuardNode> availableGuardNodes, boolean pushUsages) {
1035 if (sorted.isMarked(n)) {
1036 return;
1037 }
1038 for (Node in : n.inputs()) {
1039 if (!sorted.isMarked(in)) {
1040 return;
1041 }
1042 }
1043 if (n instanceof GuardNode) {
1044 availableGuardNodes.add((GuardNode) n);
1045 } else {
1046 addNodeToResort(n, stack, sorted, newBlock, pushUsages);
1047 }
1048 }
1049
1050 /**
1051 * Add a node to the re-sorted micro-block. This also pushes nodes that need to be
1052 * (re-)examined on the stack.
1053 */
1054 private static void addNodeToResort(Node n, NodeStack stack, NodeBitMap sorted, MicroBlock newBlock, boolean pushUsages) {
1055 sorted.mark(n);
1056 newBlock.add(n);
1057 if (pushUsages) {
1058 for (Node u : n.usages()) {
1059 if (!sorted.isMarked(u)) {
1060 stack.push(u);
1061 }
1062 }
1063 }
1064 }
1065
1066 /**
1067 * This fills in a map of transitive priorities ({@code priorities}). It also marks the
1068 * nodes from this micro-block in {@code blockNodes}.
1069 *
1070 * The transitive priority of a guard is the highest of its priority and the priority of
1071 * the guards that depend on it (transitively).
1072 *
1073 * This method returns {@code false} if no re-ordering is necessary in this micro-block.
1074 */
1075 private static boolean propagatePriority(MicroBlock block, NodeStack stack, NodeMap<GuardPriority> priorities, NodeBitMap blockNodes) {
1076 assert stack.isEmpty();
1077 assert blockNodes.isEmpty();
1078 GuardPriority lowestPriority = GuardPriority.highest();
1079 for (NodeEntry e = block.head; e != null; e = e.next) {
1080 blockNodes.mark(e.node);
1081 if (e.node instanceof GuardNode) {
1082 GuardNode guard = (GuardNode) e.node;
1083 GuardPriority priority = guard.computePriority();
1084 if (lowestPriority != null) {
1085 if (priority.isLowerPriorityThan(lowestPriority)) {
1086 lowestPriority = priority;
1087 } else if (priority.isHigherPriorityThan(lowestPriority)) {
1088 lowestPriority = null;
1089 }
1090 }
1091 stack.push(guard);
1092 priorities.set(guard, priority);
1093 }
1094 }
1095 if (lowestPriority != null) {
1096 stack.clear();
1097 blockNodes.clearAll();
1098 return false;
1099 }
1100
1101 do {
1102 Node current = stack.pop();
1103 assert blockNodes.isMarked(current);
1104 GuardPriority priority = priorities.get(current);
1105 for (Node input : current.inputs()) {
1106 if (!blockNodes.isMarked(input)) {
1107 continue;
1108 }
1109 GuardPriority inputPriority = priorities.get(input);
1110 if (inputPriority == null || inputPriority.isLowerPriorityThan(priority)) {
1111 priorities.set(input, priority);
1112 stack.push(input);
1113 }
1114 }
1115 } while (!stack.isEmpty());
1116 return true;
1117 }
1118 }
1119
1120 /**
1121 * Processes the inputs of given block. Pushes unprocessed inputs onto the stack. Returns
1122 * null if there were still unprocessed inputs, otherwise returns the earliest block given
1123 * node can be scheduled in.
1124 */
1125 private static MicroBlock processInputs(NodeMap<MicroBlock> nodeToBlock, NodeStack stack, MicroBlock startBlock, Node current) {
1126 if (current.getNodeClass().isLeafNode()) {
1127 return startBlock;
1128 }
1129
1130 MicroBlock earliestBlock = startBlock;
1131 for (Node input : current.inputs()) {
1132 MicroBlock inputBlock = nodeToBlock.get(input);
1133 if (inputBlock == null) {
1134 earliestBlock = null;
1135 stack.push(input);
1136 } else if (earliestBlock != null && inputBlock.getId() > earliestBlock.getId()) {
1137 earliestBlock = inputBlock;
1138 }
1139 }
1140 return earliestBlock;
1141 }
1142
1143 private static boolean isFixedEnd(FixedNode endNode) {
1144 return endNode instanceof ControlSplitNode || endNode instanceof ControlSinkNode || endNode instanceof AbstractEndNode;
1145 }
1146
1147 public String printScheduleHelper(String desc) {
1148 Formatter buf = new Formatter();
1149 buf.format("=== %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), desc);
1150 for (Block b : getCFG().getBlocks()) {
1151 buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
1152 buf.format("dom: %s. ", b.getDominator());
1153 buf.format("preds: %s. ", Arrays.toString(b.getPredecessors()));
1154 buf.format("succs: %s ====%n", Arrays.toString(b.getSuccessors()));
1155
1156 if (blockToNodesMap.get(b) != null) {
1157 for (Node n : nodesFor(b)) {
1158 printNode(n);
1159 }
1160 } else {
1161 for (Node n : b.getNodes()) {
1162 printNode(n);
1163 }
1164 }
1165 }
1166 buf.format("%n");
1167 return buf.toString();
1168 }
1169
1170 private static void printNode(Node n) {
1171 Formatter buf = new Formatter();
1172 buf.format("%s", n);
1173 if (n instanceof MemoryCheckpoint.Single) {
1174 buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
1175 } else if (n instanceof MemoryCheckpoint.Multi) {
1176 buf.format(" // kills ");
1177 for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
1178 buf.format("%s, ", locid);
1179 }
1180 } else if (n instanceof FloatingReadNode) {
1181 FloatingReadNode frn = (FloatingReadNode) n;
1182 buf.format(" // from %s", frn.getLocationIdentity());
1183 buf.format(", lastAccess: %s", frn.getLastLocationAccess());
1184 buf.format(", address: %s", frn.getAddress());
1185 } else if (n instanceof GuardNode) {
1186 buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
1187 }
1188 n.getDebug().log("%s", buf);
1189 }
1190
1191 public ControlFlowGraph getCFG() {
1192 return cfg;
1193 }
1194
1195 /**
1196 * Gets the nodes in a given block.
1197 */
1198 public List<Node> nodesFor(Block block) {
1199 return blockToNodesMap.get(block);
1200 }
1201 }
1202
1203 }