1 /*
2 * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.nodes.cfg;
26
27 import static org.graalvm.compiler.core.common.cfg.AbstractBlockBase.BLOCK_ID_COMPARATOR;
28
29 import java.util.ArrayList;
30 import java.util.Arrays;
31 import java.util.BitSet;
32 import java.util.List;
33
34 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
35 import org.graalvm.compiler.core.common.cfg.CFGVerifier;
36 import org.graalvm.compiler.core.common.cfg.Loop;
37 import org.graalvm.compiler.debug.DebugContext;
38 import org.graalvm.compiler.debug.GraalError;
39 import org.graalvm.compiler.graph.Node;
40 import org.graalvm.compiler.graph.NodeMap;
41 import org.graalvm.compiler.nodes.AbstractBeginNode;
42 import org.graalvm.compiler.nodes.AbstractEndNode;
43 import org.graalvm.compiler.nodes.ControlSinkNode;
44 import org.graalvm.compiler.nodes.ControlSplitNode;
45 import org.graalvm.compiler.nodes.EndNode;
46 import org.graalvm.compiler.nodes.FixedNode;
47 import org.graalvm.compiler.nodes.FixedWithNextNode;
48 import org.graalvm.compiler.nodes.IfNode;
49 import org.graalvm.compiler.nodes.LoopBeginNode;
50 import org.graalvm.compiler.nodes.LoopEndNode;
51 import org.graalvm.compiler.nodes.LoopExitNode;
52 import org.graalvm.compiler.nodes.MergeNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54
55 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
56 /**
57 * Don't allow relative frequency values to be become too small or too high as this makes
58 * frequency calculations over- or underflow the range of a double. This commonly happens with
59 * infinite loops within infinite loops. The value is chosen a bit lower than half the maximum
60 * exponent supported by double. That way we can never overflow to infinity when multiplying two
61 * relative frequency values.
62 */
63 public static final double MIN_RELATIVE_FREQUENCY = 0x1.0p-500;
64 public static final double MAX_RELATIVE_FREQUENCY = 1 / MIN_RELATIVE_FREQUENCY;
65
66 public final StructuredGraph graph;
67
68 private NodeMap<Block> nodeToBlock;
69 private Block[] reversePostOrder;
70 private List<Loop<Block>> loops;
71 private int maxDominatorDepth;
72
73 public interface RecursiveVisitor<V> {
74 V enter(Block b);
75
76 void exit(Block b, V value);
77 }
78
79 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
80 ControlFlowGraph cfg = new ControlFlowGraph(graph);
81 cfg.identifyBlocks();
82 cfg.computeFrequencies();
83
84 if (computeLoops) {
85 cfg.computeLoopInformation();
86 }
87 if (computeDominators) {
88 cfg.computeDominators();
89 }
90 if (computePostdominators) {
91 cfg.computePostdominators();
92 }
93
94 // there's not much to verify when connectBlocks == false
95 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
96 return cfg;
97 }
98
99 public String dominatorTreeString() {
100 return dominatorTreeString(getStartBlock());
101 }
102
103 private static String dominatorTreeString(Block b) {
104 StringBuilder sb = new StringBuilder();
105 sb.append(b);
106 sb.append("(");
107 Block firstDominated = b.getFirstDominated();
108 while (firstDominated != null) {
109 if (firstDominated.getDominator().getPostdominator() == firstDominated) {
110 sb.append("!");
111 }
112 sb.append(dominatorTreeString(firstDominated));
113 firstDominated = firstDominated.getDominatedSibling();
114 }
115 sb.append(") ");
116 return sb.toString();
117 }
118
119 @SuppressWarnings("unchecked")
120 public <V> void visitDominatorTreeDefault(RecursiveVisitor<V> visitor) {
121
122 Block[] stack = new Block[maxDominatorDepth + 1];
123 Block current = getStartBlock();
124 int tos = 0;
125 Object[] values = null;
126 int valuesTOS = 0;
127
128 while (tos >= 0) {
129 Block state = stack[tos];
130 if (state == null || state.getDominator() == null || state.getDominator().getPostdominator() != state) {
131 if (state == null) {
132 // We enter this block for the first time.
133 V value = visitor.enter(current);
134 if (value != null || values != null) {
135 if (values == null) {
136 values = new Object[maxDominatorDepth + 1];
137 }
138 values[valuesTOS++] = value;
139 }
140
141 Block dominated = skipPostDom(current.getFirstDominated());
142 if (dominated != null) {
143 // Descend into dominated.
144 stack[tos] = dominated;
145 current = dominated;
146 stack[++tos] = null;
147 continue;
148 }
149 } else {
150 Block next = skipPostDom(state.getDominatedSibling());
151 if (next != null) {
152 // Descend into dominated.
153 stack[tos] = next;
154 current = next;
155 stack[++tos] = null;
156 continue;
157 }
158 }
159
160 // Finished processing all normal dominators.
161 Block postDom = current.getPostdominator();
162 if (postDom != null && postDom.getDominator() == current) {
163 // Descend into post dominator.
164 stack[tos] = postDom;
165 current = postDom;
166 stack[++tos] = null;
167 continue;
168 }
169 }
170
171 // Finished processing this node, exit and pop from stack.
172 V value = null;
173 if (values != null && valuesTOS > 0) {
174 value = (V) values[--valuesTOS];
175 }
176 visitor.exit(current, value);
177 current = current.getDominator();
178 --tos;
179 }
180 }
181
182 private static Block skipPostDom(Block block) {
183 if (block != null && block.getDominator().getPostdominator() == block) {
184 // This is an always reached block.
185 return block.getDominatedSibling();
186 }
187 return block;
188 }
189
190 public static final class DeferredExit {
191
192 public DeferredExit(Block block, DeferredExit next) {
193 this.block = block;
194 this.next = next;
195 }
196
197 private final Block block;
198 private final DeferredExit next;
199
200 public Block getBlock() {
201 return block;
202 }
203
204 public DeferredExit getNext() {
205 return next;
206 }
207
208 }
209
210 public static void addDeferredExit(DeferredExit[] deferredExits, Block b) {
211 Loop<Block> outermostExited = b.getDominator().getLoop();
212 Loop<Block> exitBlockLoop = b.getLoop();
213 assert outermostExited != null : "Dominator must be in a loop. Possible cause is a missing loop exit node.";
214 while (outermostExited.getParent() != null && outermostExited.getParent() != exitBlockLoop) {
215 outermostExited = outermostExited.getParent();
216 }
217 int loopIndex = outermostExited.getIndex();
218 deferredExits[loopIndex] = new DeferredExit(b, deferredExits[loopIndex]);
219 }
220
221 @SuppressWarnings({"unchecked"})
222 public <V> void visitDominatorTreeDeferLoopExits(RecursiveVisitor<V> visitor) {
223 Block[] stack = new Block[getBlocks().length];
224 int tos = 0;
225 BitSet visited = new BitSet(getBlocks().length);
226 int loopCount = getLoops().size();
227 DeferredExit[] deferredExits = new DeferredExit[loopCount];
228 Object[] values = null;
229 int valuesTOS = 0;
230 stack[0] = getStartBlock();
231
232 while (tos >= 0) {
233 Block cur = stack[tos];
234 int curId = cur.getId();
235 if (visited.get(curId)) {
236 V value = null;
237 if (values != null && valuesTOS > 0) {
238 value = (V) values[--valuesTOS];
239 }
240 visitor.exit(cur, value);
241 --tos;
242 if (cur.isLoopHeader()) {
243 int loopIndex = cur.getLoop().getIndex();
244 DeferredExit deferredExit = deferredExits[loopIndex];
245 if (deferredExit != null) {
246 while (deferredExit != null) {
247 stack[++tos] = deferredExit.block;
248 deferredExit = deferredExit.next;
249 }
250 deferredExits[loopIndex] = null;
251 }
252 }
253 } else {
254 visited.set(curId);
255 V value = visitor.enter(cur);
256 if (value != null || values != null) {
257 if (values == null) {
258 values = new Object[maxDominatorDepth + 1];
259 }
260 values[valuesTOS++] = value;
261 }
262
263 Block alwaysReached = cur.getPostdominator();
264 if (alwaysReached != null) {
265 if (alwaysReached.getDominator() != cur) {
266 alwaysReached = null;
267 } else if (isDominatorTreeLoopExit(alwaysReached)) {
268 addDeferredExit(deferredExits, alwaysReached);
269 } else {
270 stack[++tos] = alwaysReached;
271 }
272 }
273
274 Block b = cur.getFirstDominated();
275 while (b != null) {
276 if (b != alwaysReached) {
277 if (isDominatorTreeLoopExit(b)) {
278 addDeferredExit(deferredExits, b);
279 } else {
280 stack[++tos] = b;
281 }
282 }
283 b = b.getDominatedSibling();
284 }
285 }
286 }
287 }
288
289 public <V> void visitDominatorTree(RecursiveVisitor<V> visitor, boolean deferLoopExits) {
290 if (deferLoopExits && this.getLoops().size() > 0) {
291 visitDominatorTreeDeferLoopExits(visitor);
292 } else {
293 visitDominatorTreeDefault(visitor);
294 }
295 }
296
297 public static boolean isDominatorTreeLoopExit(Block b) {
298 Block dominator = b.getDominator();
299 return dominator != null && b.getLoop() != dominator.getLoop() && (!b.isLoopHeader() || dominator.getLoopDepth() >= b.getLoopDepth());
300 }
301
302 private ControlFlowGraph(StructuredGraph graph) {
303 this.graph = graph;
304 this.nodeToBlock = graph.createNodeMap();
305 }
306
307 private void computeDominators() {
308 assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
309 Block[] blocks = reversePostOrder;
310 int curMaxDominatorDepth = 0;
311 for (int i = 1; i < blocks.length; i++) {
312 Block block = blocks[i];
313 assert block.getPredecessorCount() > 0;
314 Block dominator = null;
315 for (Block pred : block.getPredecessors()) {
316 if (!pred.isLoopEnd()) {
317 dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
318 }
319 }
320 // Fortify: Suppress Null Dereference false positive (every block apart from the first
321 // is guaranteed to have a predecessor)
322 assert dominator != null;
323
324 // Set dominator.
325 block.setDominator(dominator);
326
327 // Keep dominated linked list sorted by block ID such that predecessor blocks are always
328 // before successor blocks.
329 Block currentDominated = dominator.getFirstDominated();
330 if (currentDominated != null && currentDominated.getId() < block.getId()) {
331 while (currentDominated.getDominatedSibling() != null && currentDominated.getDominatedSibling().getId() < block.getId()) {
332 currentDominated = currentDominated.getDominatedSibling();
333 }
334 block.setDominatedSibling(currentDominated.getDominatedSibling());
335 currentDominated.setDominatedSibling(block);
336 } else {
337 block.setDominatedSibling(dominator.getFirstDominated());
338 dominator.setFirstDominated(block);
339 }
340
341 curMaxDominatorDepth = Math.max(curMaxDominatorDepth, block.getDominatorDepth());
342 }
343 this.maxDominatorDepth = curMaxDominatorDepth;
344 calcDominatorRanges(getStartBlock(), reversePostOrder.length);
345 }
346
347 private static void calcDominatorRanges(Block block, int size) {
348 Block[] stack = new Block[size];
349 stack[0] = block;
350 int tos = 0;
351 int myNumber = 0;
352
353 do {
354 Block cur = stack[tos];
355 Block dominated = cur.getFirstDominated();
356
357 if (cur.getDominatorNumber() == -1) {
358 cur.setDominatorNumber(myNumber);
359 if (dominated != null) {
360 // Push children onto stack.
361 do {
362 stack[++tos] = dominated;
363 dominated = dominated.getDominatedSibling();
364 } while (dominated != null);
365 } else {
366 cur.setMaxChildDomNumber(myNumber);
367 --tos;
368 }
369 ++myNumber;
370 } else {
371 cur.setMaxChildDomNumber(dominated.getMaxChildDominatorNumber());
372 --tos;
373 }
374 } while (tos >= 0);
375 }
376
377 private static Block commonDominatorRaw(Block a, Block b) {
378 int aDomDepth = a.getDominatorDepth();
379 int bDomDepth = b.getDominatorDepth();
380 if (aDomDepth > bDomDepth) {
381 return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
382 } else {
383 return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
384 }
385 }
386
387 private static Block commonDominatorRawSameDepth(Block a, Block b) {
388 Block iterA = a;
389 Block iterB = b;
390 while (iterA != iterB) {
391 iterA = iterA.getDominator();
392 iterB = iterB.getDominator();
393 }
394 return iterA;
395 }
396
397 @Override
398 public Block[] getBlocks() {
399 return reversePostOrder;
400 }
401
402 @Override
403 public Block getStartBlock() {
404 return reversePostOrder[0];
405 }
406
407 public Block[] reversePostOrder() {
408 return reversePostOrder;
409 }
410
411 public NodeMap<Block> getNodeToBlock() {
412 return nodeToBlock;
413 }
414
415 public Block blockFor(Node node) {
416 return nodeToBlock.get(node);
417 }
418
419 @Override
420 public List<Loop<Block>> getLoops() {
421 return loops;
422 }
423
424 public int getMaxDominatorDepth() {
425 return maxDominatorDepth;
426 }
427
428 private void identifyBlock(Block block) {
429 FixedWithNextNode cur = block.getBeginNode();
430 while (true) {
431 assert cur.isAlive() : cur;
432 assert nodeToBlock.get(cur) == null;
433 nodeToBlock.set(cur, block);
434 FixedNode next = cur.next();
435 if (next instanceof AbstractBeginNode) {
436 block.endNode = cur;
437 return;
438 } else if (next instanceof FixedWithNextNode) {
439 cur = (FixedWithNextNode) next;
440 } else {
441 nodeToBlock.set(next, block);
442 block.endNode = next;
443 return;
444 }
445 }
446 }
447
448 /**
449 * Identify and connect blocks (including loop backward edges). Predecessors need to be in the
450 * order expected when iterating phi inputs.
451 */
452 private void identifyBlocks() {
453 // Find all block headers.
454 int numBlocks = 0;
455 for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) {
456 Block block = new Block(begin);
457 identifyBlock(block);
458 numBlocks++;
459 }
460
461 // Compute reverse post order.
462 int count = 0;
463 NodeMap<Block> nodeMap = this.nodeToBlock;
464 Block[] stack = new Block[numBlocks];
465 int tos = 0;
466 Block startBlock = blockFor(graph.start());
467 stack[0] = startBlock;
468 startBlock.setPredecessors(Block.EMPTY_ARRAY);
469 do {
470 Block block = stack[tos];
471 int id = block.getId();
472 if (id == BLOCK_ID_INITIAL) {
473 // First time we see this block: push all successors.
474 FixedNode last = block.getEndNode();
475 if (last instanceof EndNode) {
476 EndNode endNode = (EndNode) last;
477 Block suxBlock = nodeMap.get(endNode.merge());
478 if (suxBlock.getId() == BLOCK_ID_INITIAL) {
479 stack[++tos] = suxBlock;
480 }
481 block.setSuccessors(new Block[]{suxBlock});
482 } else if (last instanceof IfNode) {
483 IfNode ifNode = (IfNode) last;
484 Block trueSucc = nodeMap.get(ifNode.trueSuccessor());
485 stack[++tos] = trueSucc;
486 Block falseSucc = nodeMap.get(ifNode.falseSuccessor());
487 stack[++tos] = falseSucc;
488 block.setSuccessors(new Block[]{trueSucc, falseSucc});
489 Block[] ifPred = new Block[]{block};
490 trueSucc.setPredecessors(ifPred);
491 falseSucc.setPredecessors(ifPred);
492 } else if (last instanceof LoopEndNode) {
493 LoopEndNode loopEndNode = (LoopEndNode) last;
494 block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())});
495 // Nothing to do push onto the stack.
496 } else if (last instanceof ControlSinkNode) {
497 block.setSuccessors(Block.EMPTY_ARRAY);
498 } else {
499 assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode.";
500 int startTos = tos;
501 Block[] ifPred = new Block[]{block};
502 for (Node suxNode : last.successors()) {
503 Block sux = nodeMap.get(suxNode);
504 stack[++tos] = sux;
505 sux.setPredecessors(ifPred);
506 }
507 int suxCount = tos - startTos;
508 Block[] successors = new Block[suxCount];
509 System.arraycopy(stack, startTos + 1, successors, 0, suxCount);
510 block.setSuccessors(successors);
511 }
512 block.setId(BLOCK_ID_VISITED);
513 AbstractBeginNode beginNode = block.getBeginNode();
514 if (beginNode instanceof LoopBeginNode) {
515 computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode);
516 } else if (beginNode instanceof MergeNode) {
517 MergeNode mergeNode = (MergeNode) beginNode;
518 int forwardEndCount = mergeNode.forwardEndCount();
519 Block[] predecessors = new Block[forwardEndCount];
520 for (int i = 0; i < forwardEndCount; ++i) {
521 predecessors[i] = nodeMap.get(mergeNode.forwardEndAt(i));
522 }
523 block.setPredecessors(predecessors);
524 }
525
526 } else if (id == BLOCK_ID_VISITED) {
527 // Second time we see this block: All successors have been processed, so add block
528 // to result list. Can safely reuse the stack for this.
529 --tos;
530 count++;
531 int index = numBlocks - count;
532 stack[index] = block;
533 block.setId(index);
534 } else {
535 throw GraalError.shouldNotReachHere();
536 }
537 } while (tos >= 0);
538
539 // Compute reverse postorder and number blocks.
540 assert count == numBlocks : "all blocks must be reachable";
541 this.reversePostOrder = stack;
542 }
543
544 private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) {
545 int forwardEndCount = loopBeginNode.forwardEndCount();
546 LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds();
547 Block[] predecessors = new Block[forwardEndCount + loopEnds.length];
548 for (int i = 0; i < forwardEndCount; ++i) {
549 predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i));
550 }
551 for (int i = 0; i < loopEnds.length; ++i) {
552 predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
553 }
554 block.setPredecessors(predecessors);
555 }
556
557 /**
558 * Computes the frequencies of all blocks relative to the start block. It uses the probability
559 * information attached to control flow splits to calculate the frequency of a block based on
560 * the frequency of its predecessor and the probability of its incoming control flow branch.
561 */
562 private void computeFrequencies() {
563
564 for (Block block : reversePostOrder) {
565 Block[] predecessors = block.getPredecessors();
566
567 double relativeFrequency;
568 if (predecessors.length == 0) {
569 relativeFrequency = 1D;
570 } else if (predecessors.length == 1) {
571 Block pred = predecessors[0];
572 relativeFrequency = pred.relativeFrequency;
573 if (pred.getSuccessorCount() > 1) {
574 assert pred.getEndNode() instanceof ControlSplitNode;
575 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
576 relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, controlSplit.probability(block.getBeginNode()));
577 }
578 } else {
579 relativeFrequency = predecessors[0].relativeFrequency;
580 for (int i = 1; i < predecessors.length; ++i) {
581 relativeFrequency += predecessors[i].relativeFrequency;
582 }
583
584 if (block.getBeginNode() instanceof LoopBeginNode) {
585 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
586 relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, loopBegin.loopFrequency());
587 }
588 }
589 if (relativeFrequency < MIN_RELATIVE_FREQUENCY) {
590 relativeFrequency = MIN_RELATIVE_FREQUENCY;
591 } else if (relativeFrequency > MAX_RELATIVE_FREQUENCY) {
592 relativeFrequency = MAX_RELATIVE_FREQUENCY;
593 }
594 block.setRelativeFrequency(relativeFrequency);
595 }
596
597 }
598
599 private void computeLoopInformation() {
600 loops = new ArrayList<>();
601 if (graph.hasLoops()) {
602 Block[] stack = new Block[this.reversePostOrder.length];
603 for (Block block : reversePostOrder) {
604 AbstractBeginNode beginNode = block.getBeginNode();
605 if (beginNode instanceof LoopBeginNode) {
606 Loop<Block> parent = block.getLoop();
607 Loop<Block> loop = new HIRLoop(parent, loops.size(), block);
608 if (parent != null) {
609 parent.getChildren().add(loop);
610 }
611 loops.add(loop);
612 block.setLoop(loop);
613 loop.getBlocks().add(block);
614
615 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
616 for (LoopEndNode end : loopBegin.loopEnds()) {
617 Block endBlock = nodeToBlock.get(end);
618 computeLoopBlocks(endBlock, loop, stack, true);
619 }
620
621 // Note that at this point, due to traversal order, child loops of `loop` have
622 // not been discovered yet.
623 for (Block b : loop.getBlocks()) {
624 for (Block sux : b.getSuccessors()) {
625 if (sux.getLoop() != loop) {
626 assert sux.getLoopDepth() < loop.getDepth();
627 loop.getNaturalExits().add(sux);
628 }
629 }
630 }
631 loop.getNaturalExits().sort(BLOCK_ID_COMPARATOR);
632
633 if (!graph.getGuardsStage().areFrameStatesAtDeopts()) {
634 for (LoopExitNode exit : loopBegin.loopExits()) {
635 Block exitBlock = nodeToBlock.get(exit);
636 assert exitBlock.getPredecessorCount() == 1;
637 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true);
638 loop.getLoopExits().add(exitBlock);
639 }
640 loop.getLoopExits().sort(BLOCK_ID_COMPARATOR);
641
642 // The following loop can add new blocks to the end of the loop's block
643 // list.
644 int size = loop.getBlocks().size();
645 for (int i = 0; i < size; ++i) {
646 Block b = loop.getBlocks().get(i);
647 for (Block sux : b.getSuccessors()) {
648 if (sux.getLoop() != loop) {
649 AbstractBeginNode begin = sux.getBeginNode();
650 if (!loopBegin.isLoopExit(begin)) {
651 assert !(begin instanceof LoopBeginNode);
652 assert sux.getLoopDepth() < loop.getDepth();
653 graph.getDebug().log(DebugContext.VERBOSE_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux);
654 computeLoopBlocks(sux, loop, stack, false);
655 }
656 }
657 }
658 }
659 } else {
660 loop.getLoopExits().addAll(loop.getNaturalExits());
661 }
662 }
663 }
664 }
665 }
666
667 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) {
668 if (start.getLoop() != loop) {
669 start.setLoop(loop);
670 stack[0] = start;
671 loop.getBlocks().add(start);
672 int tos = 0;
673 do {
674 Block block = stack[tos--];
675
676 // Add predecessors or successors to the loop.
677 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
678 if (b.getLoop() != loop) {
679 stack[++tos] = b;
680 b.setLoop(loop);
681 loop.getBlocks().add(b);
682 }
683 }
684 } while (tos >= 0);
685 }
686 }
687
688 public void computePostdominators() {
689
690 Block[] reversePostOrderTmp = this.reversePostOrder;
691 outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) {
692 Block block = reversePostOrderTmp[j];
693 if (block.isLoopEnd()) {
694 // We do not want the loop header registered as the postdominator of the loop end.
695 continue;
696 }
697 if (block.getSuccessorCount() == 0) {
698 // No successors => no postdominator.
699 continue;
700 }
701 Block firstSucc = block.getSuccessors()[0];
702 if (block.getSuccessorCount() == 1) {
703 block.postdominator = firstSucc;
704 continue;
705 }
706 Block postdominator = firstSucc;
707 for (Block sux : block.getSuccessors()) {
708 postdominator = commonPostdominator(postdominator, sux);
709 if (postdominator == null) {
710 // There is a dead end => no postdominator available.
711 continue outer;
712 }
713 }
714 assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
715 block.setPostDominator(postdominator);
716 }
717 }
718
719 private static Block commonPostdominator(Block a, Block b) {
720 Block iterA = a;
721 Block iterB = b;
722 while (iterA != iterB) {
723 if (iterA.getId() < iterB.getId()) {
724 iterA = iterA.getPostdominator();
725 if (iterA == null) {
726 return null;
727 }
728 } else {
729 assert iterB.getId() < iterA.getId();
730 iterB = iterB.getPostdominator();
731 if (iterB == null) {
732 return null;
733 }
734 }
735 }
736 return iterA;
737 }
738
739 public void setNodeToBlock(NodeMap<Block> nodeMap) {
740 this.nodeToBlock = nodeMap;
741 }
742
743 /**
744 * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_RELATIVE_FREQUENCY} and
745 * {@link ControlFlowGraph#MAX_RELATIVE_FREQUENCY}.
746 */
747 public static double multiplyRelativeFrequencies(double a, double b) {
748 assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b;
749 double r = a * b;
750 if (r > MAX_RELATIVE_FREQUENCY) {
751 return MAX_RELATIVE_FREQUENCY;
752 }
753 if (r < MIN_RELATIVE_FREQUENCY) {
754 return MIN_RELATIVE_FREQUENCY;
755 }
756 return r;
757 }
758 }