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