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.probability() < latestBlock.probability() || ((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) && earliestBlock.probability() < latestBlock.probability() * IMPLICIT_NULL_CHECK_OPPORTUNITY_PROBABILITY_FACTOR) {
571 latestBlock = earliestBlock;
572 }
573 }
574
575 selectLatestBlock(currentNode, earliestBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);
576 }
577
578 private static boolean isImplicitNullOpportunity(FloatingReadNode floatingReadNode, Block block) {
579
580 Node pred = block.getBeginNode().predecessor();
581 if (pred instanceof IfNode) {
582 IfNode ifNode = (IfNode) pred;
583 if (ifNode.condition() instanceof IsNullNode) {
584 IsNullNode isNullNode = (IsNullNode) ifNode.condition();
585 if (getUnproxifiedUncompressed(floatingReadNode.getAddress().getBase()) == getUnproxifiedUncompressed(isNullNode.getValue())) {
586 return true;
587 }
588 }
589 }
590 return false;
591 }
592
593 private static Node getUnproxifiedUncompressed(Node node) {
594 Node result = node;
595 while (true) {
596 if (result instanceof ValueProxy) {
597 ValueProxy valueProxy = (ValueProxy) result;
598 result = valueProxy.getOriginalNode();
599 } else if (result instanceof ConvertNode) {
600 ConvertNode convertNode = (ConvertNode) result;
601 if (convertNode.mayNullCheckSkipConversion()) {
602 result = convertNode.getValue();
603 } else {
604 break;
605 }
606 } else {
607 break;
608 }
609 }
610 return result;
611 }
612
613 private static Block calcBlockForUsage(Node node, Node usage, Block startBlock, NodeMap<Block> currentNodeMap) {
614 assert !(node instanceof PhiNode);
615 Block currentBlock = startBlock;
616 if (usage instanceof PhiNode) {
617 // An input to a PhiNode is used at the end of the predecessor block that
618 // corresponds to the PhiNode input. One PhiNode can use an input multiple times.
619 PhiNode phi = (PhiNode) usage;
620 AbstractMergeNode merge = phi.merge();
621 Block mergeBlock = currentNodeMap.get(merge);
622 for (int i = 0; i < phi.valueCount(); ++i) {
623 if (phi.valueAt(i) == node) {
624 Block otherBlock = mergeBlock.getPredecessors()[i];
625 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
626 }
627 }
628 } else if (usage instanceof AbstractBeginNode) {
629 AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage;
630 if (abstractBeginNode instanceof StartNode) {
631 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode));
632 } else {
633 Block otherBlock = currentNodeMap.get(abstractBeginNode).getDominator();
634 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
635 }
636 } else {
637 // All other types of usages: Put the input into the same block as the usage.
638 Block otherBlock = currentNodeMap.get(usage);
639 if (usage instanceof ProxyNode) {
640 ProxyNode proxyNode = (ProxyNode) usage;
641 otherBlock = currentNodeMap.get(proxyNode.proxyPoint());
642
643 }
644 currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
645 }
646 return currentBlock;
647 }
648
649 /**
650 * Micro block that is allocated for each fixed node and captures all floating nodes that
651 * need to be scheduled immediately after the corresponding fixed node.
652 */
653 private static class MicroBlock {
654 private final int id;
655 private int nodeCount;
656 private NodeEntry head;
657 private NodeEntry tail;
658
659 MicroBlock(int id) {
660 this.id = id;
661 }
662
663 /**
664 * Adds a new floating node into the micro block.
665 */
666 public void add(Node node) {
667 assert !(node instanceof FixedNode) : node;
668 NodeEntry newTail = new NodeEntry(node);
669 if (tail == null) {
670 tail = head = newTail;
671 } else {
672 tail.next = newTail;
673 tail = newTail;
674 }
675 nodeCount++;
676 }
677
678 /**
679 * Number of nodes in this micro block.
680 */
681 public int getNodeCount() {
682 assert getActualNodeCount() == nodeCount : getActualNodeCount() + " != " + nodeCount;
683 return nodeCount;
684 }
685
686 private int getActualNodeCount() {
687 int count = 0;
688 for (NodeEntry e = head; e != null; e = e.next) {
689 count++;
690 }
691 return count;
692 }
693
694 /**
695 * The id of the micro block, with a block always associated with a lower id than its
696 * successors.
697 */
698 public int getId() {
699 return id;
700 }
701
702 /**
703 * First node of the linked list of nodes of this micro block.
704 */
705 public NodeEntry getFirstNode() {
706 return head;
707 }
708
709 /**
710 * Takes all nodes in this micro blocks and prepends them to the nodes of the given
711 * parameter.
712 *
713 * @param newBlock the new block for the nodes
714 */
715 public void prependChildrenTo(MicroBlock newBlock) {
716 if (tail != null) {
717 assert head != null;
718 tail.next = newBlock.head;
719 newBlock.head = head;
720 head = tail = null;
721 newBlock.nodeCount += nodeCount;
722 nodeCount = 0;
723 }
724 }
725
726 @Override
727 public String toString() {
728 return String.format("MicroBlock[id=%d]", id);
729 }
730
731 @Override
732 public int hashCode() {
733 return id;
734 }
735 }
736
737 /**
738 * Entry in the linked list of nodes.
739 */
740 private static class NodeEntry {
741 private final Node node;
742 private NodeEntry next;
743
744 NodeEntry(Node node) {
745 this.node = node;
746 this.next = null;
747 }
748
749 public NodeEntry getNext() {
750 return next;
751 }
752
753 public Node getNode() {
754 return node;
755 }
756 }
757
758 private void scheduleEarliestIterative(BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph, boolean immutableGraph,
759 boolean withGuardOrder) {
760
761 NodeMap<MicroBlock> entries = graph.createNodeMap();
762 NodeStack stack = new NodeStack();
763
764 // Initialize with fixed nodes.
765 MicroBlock startBlock = null;
766 int nextId = 1;
767 for (Block b : cfg.reversePostOrder()) {
768 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
769 MicroBlock microBlock = new MicroBlock(nextId++);
770 entries.set(current, microBlock);
771 boolean isNew = visited.checkAndMarkInc(current);
772 assert isNew;
773 if (startBlock == null) {
774 startBlock = microBlock;
775 }
776 }
777 }
778
779 if (graph.getGuardsStage().allowsFloatingGuards() && graph.getNodes(GuardNode.TYPE).isNotEmpty()) {
780 // Now process guards.
781 if (GuardPriorities.getValue(graph.getOptions()) && withGuardOrder) {
782 EnumMap<GuardPriority, List<GuardNode>> guardsByPriority = new EnumMap<>(GuardPriority.class);
783 for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
784 guardsByPriority.computeIfAbsent(guard.computePriority(), p -> new ArrayList<>()).add(guard);
785 }
786 // `EnumMap.values` returns values in "natural" key order
787 for (List<GuardNode> guards : guardsByPriority.values()) {
788 processNodes(visited, entries, stack, startBlock, guards);
789 }
790 GuardOrder.resortGuards(graph, entries, stack);
791 } else {
792 processNodes(visited, entries, stack, startBlock, graph.getNodes(GuardNode.TYPE));
793 }
794 } else {
795 assert graph.getNodes(GuardNode.TYPE).isEmpty();
796 }
797
798 // Now process inputs of fixed nodes.
799 for (Block b : cfg.reversePostOrder()) {
800 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
801 processNodes(visited, entries, stack, startBlock, current.inputs());
802 }
803 }
804
805 if (visited.getCounter() < graph.getNodeCount()) {
806 // Visit back input edges of loop phis.
807 boolean changed;
808 boolean unmarkedPhi;
809 do {
810 changed = false;
811 unmarkedPhi = false;
812 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
813 for (PhiNode phi : loopBegin.phis()) {
814 if (visited.isMarked(phi)) {
815 for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) {
816 Node node = phi.valueAt(i + loopBegin.forwardEndCount());
817 if (node != null && entries.get(node) == null) {
818 changed = true;
819 processStack(node, startBlock, entries, visited, stack);
820 }
821 }
822 } else {
823 unmarkedPhi = true;
824 }
825 }
826 }
827
828 /*
829 * the processing of one loop phi could have marked a previously checked loop
830 * phi, therefore this needs to be iterative.
831 */
832 } while (unmarkedPhi && changed);
833 }
834
835 // Check for dead nodes.
836 if (!immutableGraph && visited.getCounter() < graph.getNodeCount()) {
837 for (Node n : graph.getNodes()) {
838 if (!visited.isMarked(n)) {
839 n.clearInputs();
840 n.markDeleted();
841 }
842 }
843 }
844
845 for (Block b : cfg.reversePostOrder()) {
846 FixedNode fixedNode = b.getEndNode();
847 if (fixedNode instanceof ControlSplitNode) {
848 ControlSplitNode controlSplitNode = (ControlSplitNode) fixedNode;
849 MicroBlock endBlock = entries.get(fixedNode);
850 AbstractBeginNode primarySuccessor = controlSplitNode.getPrimarySuccessor();
851 if (primarySuccessor != null) {
852 endBlock.prependChildrenTo(entries.get(primarySuccessor));
853 } else {
854 assert endBlock.tail == null;
855 }
856 }
857 }
858
859 // Create lists for each block
860 for (Block b : cfg.reversePostOrder()) {
861 // Count nodes in block
862 int totalCount = 0;
863 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
864 MicroBlock microBlock = entries.get(current);
865 totalCount += microBlock.getNodeCount() + 1;
866 }
867
868 // Initialize with begin node, it is always the first node.
869 ArrayList<Node> nodes = new ArrayList<>(totalCount);
870 blockToNodes.put(b, nodes);
871
872 for (FixedNode current : b.getBeginNode().getBlockNodes()) {
873 MicroBlock microBlock = entries.get(current);
874 nodeToBlock.set(current, b);
875 nodes.add(current);
876 NodeEntry next = microBlock.getFirstNode();
877 while (next != null) {
878 Node nextNode = next.getNode();
879 nodeToBlock.set(nextNode, b);
880 nodes.add(nextNode);
881 next = next.getNext();
882 }
883 }
884 }
885
886 assert (!Assertions.detailedAssertionsEnabled(cfg.graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
887 }
888
889 private static void processNodes(NodeBitMap visited, NodeMap<MicroBlock> entries, NodeStack stack, MicroBlock startBlock, Iterable<? extends Node> nodes) {
890 for (Node node : nodes) {
891 if (entries.get(node) == null) {
892 processStack(node, startBlock, entries, visited, stack);
893 }
894 }
895 }
896
897 private static void processStackPhi(NodeStack stack, PhiNode phiNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
898 stack.pop();
899 if (visited.checkAndMarkInc(phiNode)) {
900 MicroBlock mergeBlock = nodeToBlock.get(phiNode.merge());
901 assert mergeBlock != null : phiNode;
902 nodeToBlock.set(phiNode, mergeBlock);
903 AbstractMergeNode merge = phiNode.merge();
904 for (int i = 0; i < merge.forwardEndCount(); ++i) {
905 Node input = phiNode.valueAt(i);
906 if (input != null && nodeToBlock.get(input) == null) {
907 stack.push(input);
908 }
909 }
910 }
911 }
912
913 private static void processStackProxy(NodeStack stack, ProxyNode proxyNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
914 stack.pop();
915 if (visited.checkAndMarkInc(proxyNode)) {
916 nodeToBlock.set(proxyNode, nodeToBlock.get(proxyNode.proxyPoint()));
917 Node input = proxyNode.value();
918 if (input != null && nodeToBlock.get(input) == null) {
919 stack.push(input);
920 }
921 }
922 }
923
924 private static void processStack(Node first, MicroBlock startBlock, NodeMap<MicroBlock> nodeToMicroBlock, NodeBitMap visited, NodeStack stack) {
925 assert stack.isEmpty();
926 assert !visited.isMarked(first);
927 stack.push(first);
928 Node current = first;
929 while (true) {
930 if (current instanceof PhiNode) {
931 processStackPhi(stack, (PhiNode) current, nodeToMicroBlock, visited);
932 } else if (current instanceof ProxyNode) {
933 processStackProxy(stack, (ProxyNode) current, nodeToMicroBlock, visited);
934 } else {
935 MicroBlock currentBlock = nodeToMicroBlock.get(current);
936 if (currentBlock == null) {
937 MicroBlock earliestBlock = processInputs(nodeToMicroBlock, stack, startBlock, current);
938 if (earliestBlock == null) {
939 // We need to delay until inputs are processed.
940 } else {
941 // Can immediately process and pop.
942 stack.pop();
943 visited.checkAndMarkInc(current);
944 nodeToMicroBlock.set(current, earliestBlock);
945 earliestBlock.add(current);
946 }
947 } else {
948 stack.pop();
949 }
950 }
951
952 if (stack.isEmpty()) {
953 break;
954 }
955 current = stack.peek();
956 }
957 }
958
959 private static class GuardOrder {
960 /**
961 * After an earliest schedule, this will re-sort guards to honor their
962 * {@linkplain StaticDeoptimizingNode#computePriority() priority}.
963 *
964 * Note that this only changes the order of nodes within {@linkplain MicroBlock
965 * micro-blocks}, nodes will not be moved from one micro-block to another.
966 */
967 private static void resortGuards(StructuredGraph graph, NodeMap<MicroBlock> entries, NodeStack stack) {
968 assert stack.isEmpty();
969 EconomicSet<MicroBlock> blocksWithGuards = EconomicSet.create(IDENTITY);
970 for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
971 MicroBlock block = entries.get(guard);
972 assert block != null : guard + "should already be scheduled to a micro-block";
973 blocksWithGuards.add(block);
974 }
975 assert !blocksWithGuards.isEmpty();
976 NodeMap<GuardPriority> priorities = graph.createNodeMap();
977 NodeBitMap blockNodes = graph.createNodeBitMap();
978 for (MicroBlock block : blocksWithGuards) {
979 MicroBlock newBlock = resortGuards(block, stack, blockNodes, priorities);
980 assert stack.isEmpty();
981 assert blockNodes.isEmpty();
982 if (newBlock != null) {
983 assert block.getNodeCount() == newBlock.getNodeCount();
984 block.head = newBlock.head;
985 block.tail = newBlock.tail;
986 }
987 }
988 }
989
990 /**
991 * This resorts guards within one micro-block.
992 *
993 * {@code stack}, {@code blockNodes} and {@code priorities} are just temporary
994 * data-structures which are allocated once by the callers of this method. They should
995 * be in their "initial"/"empty" state when calling this method and when it returns.
996 */
997 private static MicroBlock resortGuards(MicroBlock block, NodeStack stack, NodeBitMap blockNodes, NodeMap<GuardPriority> priorities) {
998 if (!propagatePriority(block, stack, priorities, blockNodes)) {
999 return null;
1000 }
1001
1002 Function<GuardNode, GuardPriority> transitiveGuardPriorityGetter = priorities::get;
1003 Comparator<GuardNode> globalGuardPriorityComparator = Comparator.comparing(transitiveGuardPriorityGetter).thenComparing(GuardNode::computePriority).thenComparingInt(Node::hashCode);
1004
1005 SortedSet<GuardNode> availableGuards = new TreeSet<>(globalGuardPriorityComparator);
1006 MicroBlock newBlock = new MicroBlock(block.getId());
1007
1008 NodeBitMap sorted = blockNodes;
1009 sorted.invert();
1010
1011 for (NodeEntry e = block.head; e != null; e = e.next) {
1012 checkIfAvailable(e.node, stack, sorted, newBlock, availableGuards, false);
1013 }
1014 do {
1015 while (!stack.isEmpty()) {
1016 checkIfAvailable(stack.pop(), stack, sorted, newBlock, availableGuards, true);
1017 }
1018 Iterator<GuardNode> iterator = availableGuards.iterator();
1019 if (iterator.hasNext()) {
1020 addNodeToResort(iterator.next(), stack, sorted, newBlock, true);
1021 iterator.remove();
1022 }
1023 } while (!stack.isEmpty() || !availableGuards.isEmpty());
1024
1025 blockNodes.clearAll();
1026 return newBlock;
1027 }
1028
1029 /**
1030 * This checks if {@code n} can be scheduled, if it is the case, it schedules it now by
1031 * calling {@link #addNodeToResort(Node, NodeStack, NodeBitMap, MicroBlock, boolean)}.
1032 */
1033 private static void checkIfAvailable(Node n, NodeStack stack, NodeBitMap sorted, Instance.MicroBlock newBlock, SortedSet<GuardNode> availableGuardNodes, boolean pushUsages) {
1034 if (sorted.isMarked(n)) {
1035 return;
1036 }
1037 for (Node in : n.inputs()) {
1038 if (!sorted.isMarked(in)) {
1039 return;
1040 }
1041 }
1042 if (n instanceof GuardNode) {
1043 availableGuardNodes.add((GuardNode) n);
1044 } else {
1045 addNodeToResort(n, stack, sorted, newBlock, pushUsages);
1046 }
1047 }
1048
1049 /**
1050 * Add a node to the re-sorted micro-block. This also pushes nodes that need to be
1051 * (re-)examined on the stack.
1052 */
1053 private static void addNodeToResort(Node n, NodeStack stack, NodeBitMap sorted, MicroBlock newBlock, boolean pushUsages) {
1054 sorted.mark(n);
1055 newBlock.add(n);
1056 if (pushUsages) {
1057 for (Node u : n.usages()) {
1058 if (!sorted.isMarked(u)) {
1059 stack.push(u);
1060 }
1061 }
1062 }
1063 }
1064
1065 /**
1066 * This fills in a map of transitive priorities ({@code priorities}). It also marks the
1067 * nodes from this micro-block in {@code blockNodes}.
1068 *
1069 * The transitive priority of a guard is the highest of its priority and the priority of
1070 * the guards that depend on it (transitively).
1071 *
1072 * This method returns {@code false} if no re-ordering is necessary in this micro-block.
1073 */
1074 private static boolean propagatePriority(MicroBlock block, NodeStack stack, NodeMap<GuardPriority> priorities, NodeBitMap blockNodes) {
1075 assert stack.isEmpty();
1076 assert blockNodes.isEmpty();
1077 GuardPriority lowestPriority = GuardPriority.highest();
1078 for (NodeEntry e = block.head; e != null; e = e.next) {
1079 blockNodes.mark(e.node);
1080 if (e.node instanceof GuardNode) {
1081 GuardNode guard = (GuardNode) e.node;
1082 GuardPriority priority = guard.computePriority();
1083 if (lowestPriority != null) {
1084 if (priority.isLowerPriorityThan(lowestPriority)) {
1085 lowestPriority = priority;
1086 } else if (priority.isHigherPriorityThan(lowestPriority)) {
1087 lowestPriority = null;
1088 }
1089 }
1090 stack.push(guard);
1091 priorities.set(guard, priority);
1092 }
1093 }
1094 if (lowestPriority != null) {
1095 stack.clear();
1096 blockNodes.clearAll();
1097 return false;
1098 }
1099
1100 do {
1101 Node current = stack.pop();
1102 assert blockNodes.isMarked(current);
1103 GuardPriority priority = priorities.get(current);
1104 for (Node input : current.inputs()) {
1105 if (!blockNodes.isMarked(input)) {
1106 continue;
1107 }
1108 GuardPriority inputPriority = priorities.get(input);
1109 if (inputPriority == null || inputPriority.isLowerPriorityThan(priority)) {
1110 priorities.set(input, priority);
1111 stack.push(input);
1112 }
1113 }
1114 } while (!stack.isEmpty());
1115 return true;
1116 }
1117 }
1118
1119 /**
1120 * Processes the inputs of given block. Pushes unprocessed inputs onto the stack. Returns
1121 * null if there were still unprocessed inputs, otherwise returns the earliest block given
1122 * node can be scheduled in.
1123 */
1124 private static MicroBlock processInputs(NodeMap<MicroBlock> nodeToBlock, NodeStack stack, MicroBlock startBlock, Node current) {
1125 if (current.getNodeClass().isLeafNode()) {
1126 return startBlock;
1127 }
1128
1129 MicroBlock earliestBlock = startBlock;
1130 for (Node input : current.inputs()) {
1131 MicroBlock inputBlock = nodeToBlock.get(input);
1132 if (inputBlock == null) {
1133 earliestBlock = null;
1134 stack.push(input);
1135 } else if (earliestBlock != null && inputBlock.getId() > earliestBlock.getId()) {
1136 earliestBlock = inputBlock;
1137 }
1138 }
1139 return earliestBlock;
1140 }
1141
1142 private static boolean isFixedEnd(FixedNode endNode) {
1143 return endNode instanceof ControlSplitNode || endNode instanceof ControlSinkNode || endNode instanceof AbstractEndNode;
1144 }
1145
1146 public String printScheduleHelper(String desc) {
1147 Formatter buf = new Formatter();
1148 buf.format("=== %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), desc);
1149 for (Block b : getCFG().getBlocks()) {
1150 buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
1151 buf.format("dom: %s. ", b.getDominator());
1152 buf.format("preds: %s. ", Arrays.toString(b.getPredecessors()));
1153 buf.format("succs: %s ====%n", Arrays.toString(b.getSuccessors()));
1154
1155 if (blockToNodesMap.get(b) != null) {
1156 for (Node n : nodesFor(b)) {
1157 printNode(n);
1158 }
1159 } else {
1160 for (Node n : b.getNodes()) {
1161 printNode(n);
1162 }
1163 }
1164 }
1165 buf.format("%n");
1166 return buf.toString();
1167 }
1168
1169 private static void printNode(Node n) {
1170 Formatter buf = new Formatter();
1171 buf.format("%s", n);
1172 if (n instanceof MemoryCheckpoint.Single) {
1173 buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
1174 } else if (n instanceof MemoryCheckpoint.Multi) {
1175 buf.format(" // kills ");
1176 for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
1177 buf.format("%s, ", locid);
1178 }
1179 } else if (n instanceof FloatingReadNode) {
1180 FloatingReadNode frn = (FloatingReadNode) n;
1181 buf.format(" // from %s", frn.getLocationIdentity());
1182 buf.format(", lastAccess: %s", frn.getLastLocationAccess());
1183 buf.format(", address: %s", frn.getAddress());
1184 } else if (n instanceof GuardNode) {
1185 buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
1186 }
1187 n.getDebug().log("%s", buf);
1188 }
1189
1190 public ControlFlowGraph getCFG() {
1191 return cfg;
1192 }
1193
1194 /**
1195 * Gets the nodes in a given block.
1196 */
1197 public List<Node> nodesFor(Block block) {
1198 return blockToNodesMap.get(block);
1199 }
1200 }
1201
1202 }