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