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 event(NodeEvent e, Node node) {
113 assert false : "graph changed: " + e + " on node " + node;
114 }
115 });
116 } else {
117 return null;
118 }
119 }
120
121 @Override
122 @SuppressWarnings("try")
123 protected void run(StructuredGraph graph) {
124 try (NodeEventScope scope = verifyImmutableGraph(graph)) {
125 Instance inst = new Instance();
126 inst.run(graph, selectedStrategy, immutableGraph);
127 }
128 }
129
130 public static 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 }