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 }