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;
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
321 // Set dominator.
322 block.setDominator(dominator);
323
324 // Keep dominated linked list sorted by block ID such that predecessor blocks are always
325 // before successor blocks.
326 Block currentDominated = dominator.getFirstDominated();
327 if (currentDominated != null && currentDominated.getId() < block.getId()) {
328 while (currentDominated.getDominatedSibling() != null && currentDominated.getDominatedSibling().getId() < block.getId()) {
329 currentDominated = currentDominated.getDominatedSibling();
330 }
331 block.setDominatedSibling(currentDominated.getDominatedSibling());
332 currentDominated.setDominatedSibling(block);
333 } else {
334 block.setDominatedSibling(dominator.getFirstDominated());
335 dominator.setFirstDominated(block);
336 }
337
338 curMaxDominatorDepth = Math.max(curMaxDominatorDepth, block.getDominatorDepth());
339 }
340 this.maxDominatorDepth = curMaxDominatorDepth;
341 calcDominatorRanges(getStartBlock(), reversePostOrder.length);
342 }
343
344 private static void calcDominatorRanges(Block block, int size) {
345 Block[] stack = new Block[size];
346 stack[0] = block;
347 int tos = 0;
348 int myNumber = 0;
349
350 do {
351 Block cur = stack[tos];
352 Block dominated = cur.getFirstDominated();
353
354 if (cur.getDominatorNumber() == -1) {
355 cur.setDominatorNumber(myNumber);
356 if (dominated != null) {
357 // Push children onto stack.
358 do {
359 stack[++tos] = dominated;
360 dominated = dominated.getDominatedSibling();
361 } while (dominated != null);
362 } else {
363 cur.setMaxChildDomNumber(myNumber);
364 --tos;
365 }
366 ++myNumber;
367 } else {
368 cur.setMaxChildDomNumber(dominated.getMaxChildDominatorNumber());
369 --tos;
370 }
371 } while (tos >= 0);
372 }
373
374 private static Block commonDominatorRaw(Block a, Block b) {
375 int aDomDepth = a.getDominatorDepth();
376 int bDomDepth = b.getDominatorDepth();
377 if (aDomDepth > bDomDepth) {
378 return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
379 } else {
380 return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
381 }
382 }
383
384 private static Block commonDominatorRawSameDepth(Block a, Block b) {
385 Block iterA = a;
386 Block iterB = b;
387 while (iterA != iterB) {
388 iterA = iterA.getDominator();
389 iterB = iterB.getDominator();
390 }
391 return iterA;
392 }
393
394 @Override
395 public Block[] getBlocks() {
396 return reversePostOrder;
397 }
398
399 @Override
400 public Block getStartBlock() {
401 return reversePostOrder[0];
402 }
403
404 public Block[] reversePostOrder() {
405 return reversePostOrder;
406 }
407
408 public NodeMap<Block> getNodeToBlock() {
409 return nodeToBlock;
410 }
411
412 public Block blockFor(Node node) {
413 return nodeToBlock.get(node);
414 }
415
416 @Override
417 public List<Loop<Block>> getLoops() {
418 return loops;
419 }
420
421 public int getMaxDominatorDepth() {
422 return maxDominatorDepth;
423 }
424
425 private void identifyBlock(Block block) {
426 FixedWithNextNode cur = block.getBeginNode();
427 while (true) {
428 assert cur.isAlive() : cur;
429 assert nodeToBlock.get(cur) == null;
430 nodeToBlock.set(cur, block);
431 FixedNode next = cur.next();
432 if (next instanceof AbstractBeginNode) {
433 block.endNode = cur;
434 return;
435 } else if (next instanceof FixedWithNextNode) {
436 cur = (FixedWithNextNode) next;
437 } else {
438 nodeToBlock.set(next, block);
439 block.endNode = next;
440 return;
441 }
442 }
443 }
444
445 /**
446 * Identify and connect blocks (including loop backward edges). Predecessors need to be in the
447 * order expected when iterating phi inputs.
448 */
449 private void identifyBlocks() {
450 // Find all block headers.
451 int numBlocks = 0;
452 for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) {
453 Block block = new Block(begin);
454 identifyBlock(block);
455 numBlocks++;
456 }
457
458 // Compute reverse post order.
459 int count = 0;
460 NodeMap<Block> nodeMap = this.nodeToBlock;
461 Block[] stack = new Block[numBlocks];
462 int tos = 0;
463 Block startBlock = blockFor(graph.start());
464 stack[0] = startBlock;
465 startBlock.setPredecessors(Block.EMPTY_ARRAY);
466 do {
467 Block block = stack[tos];
468 int id = block.getId();
469 if (id == BLOCK_ID_INITIAL) {
470 // First time we see this block: push all successors.
471 FixedNode last = block.getEndNode();
472 if (last instanceof EndNode) {
473 EndNode endNode = (EndNode) last;
474 Block suxBlock = nodeMap.get(endNode.merge());
475 if (suxBlock.getId() == BLOCK_ID_INITIAL) {
476 stack[++tos] = suxBlock;
477 }
478 block.setSuccessors(new Block[]{suxBlock});
479 } else if (last instanceof IfNode) {
480 IfNode ifNode = (IfNode) last;
481 Block trueSucc = nodeMap.get(ifNode.trueSuccessor());
482 stack[++tos] = trueSucc;
483 Block falseSucc = nodeMap.get(ifNode.falseSuccessor());
484 stack[++tos] = falseSucc;
485 block.setSuccessors(new Block[]{trueSucc, falseSucc});
486 Block[] ifPred = new Block[]{block};
487 trueSucc.setPredecessors(ifPred);
488 falseSucc.setPredecessors(ifPred);
489 } else if (last instanceof LoopEndNode) {
490 LoopEndNode loopEndNode = (LoopEndNode) last;
491 block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())});
492 // Nothing to do push onto the stack.
493 } else if (last instanceof ControlSinkNode) {
494 block.setSuccessors(Block.EMPTY_ARRAY);
495 } else {
496 assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode.";
497 int startTos = tos;
498 Block[] ifPred = new Block[]{block};
499 for (Node suxNode : last.successors()) {
500 Block sux = nodeMap.get(suxNode);
501 stack[++tos] = sux;
502 sux.setPredecessors(ifPred);
503 }
504 int suxCount = tos - startTos;
505 Block[] successors = new Block[suxCount];
506 System.arraycopy(stack, startTos + 1, successors, 0, suxCount);
507 block.setSuccessors(successors);
508 }
509 block.setId(BLOCK_ID_VISITED);
510 AbstractBeginNode beginNode = block.getBeginNode();
511 if (beginNode instanceof LoopBeginNode) {
512 computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode);
513 } else if (beginNode instanceof MergeNode) {
514 MergeNode mergeNode = (MergeNode) beginNode;
515 int forwardEndCount = mergeNode.forwardEndCount();
516 Block[] predecessors = new Block[forwardEndCount];
517 for (int i = 0; i < forwardEndCount; ++i) {
518 predecessors[i] = nodeMap.get(mergeNode.forwardEndAt(i));
519 }
520 block.setPredecessors(predecessors);
521 }
522
523 } else if (id == BLOCK_ID_VISITED) {
524 // Second time we see this block: All successors have been processed, so add block
525 // to result list. Can safely reuse the stack for this.
526 --tos;
527 count++;
528 int index = numBlocks - count;
529 stack[index] = block;
530 block.setId(index);
531 } else {
532 throw GraalError.shouldNotReachHere();
533 }
534 } while (tos >= 0);
535
536 // Compute reverse postorder and number blocks.
537 assert count == numBlocks : "all blocks must be reachable";
538 this.reversePostOrder = stack;
539 }
540
541 private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) {
542 int forwardEndCount = loopBeginNode.forwardEndCount();
543 LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds();
544 Block[] predecessors = new Block[forwardEndCount + loopEnds.length];
545 for (int i = 0; i < forwardEndCount; ++i) {
546 predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i));
547 }
548 for (int i = 0; i < loopEnds.length; ++i) {
549 predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
550 }
551 block.setPredecessors(predecessors);
552 }
553
554 /**
555 * Computes the frequencies of all blocks relative to the start block. It uses the probability
556 * information attached to control flow splits to calculate the frequency of a block based on
557 * the frequency of its predecessor and the probability of its incoming control flow branch.
558 */
559 private void computeFrequencies() {
560
561 for (Block block : reversePostOrder) {
562 Block[] predecessors = block.getPredecessors();
563
564 double relativeFrequency;
565 if (predecessors.length == 0) {
566 relativeFrequency = 1D;
567 } else if (predecessors.length == 1) {
568 Block pred = predecessors[0];
569 relativeFrequency = pred.relativeFrequency;
570 if (pred.getSuccessorCount() > 1) {
571 assert pred.getEndNode() instanceof ControlSplitNode;
572 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
573 relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, controlSplit.probability(block.getBeginNode()));
574 }
575 } else {
576 relativeFrequency = predecessors[0].relativeFrequency;
577 for (int i = 1; i < predecessors.length; ++i) {
578 relativeFrequency += predecessors[i].relativeFrequency;
579 }
580
581 if (block.getBeginNode() instanceof LoopBeginNode) {
582 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
583 relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, loopBegin.loopFrequency());
584 }
585 }
586 if (relativeFrequency < MIN_RELATIVE_FREQUENCY) {
587 relativeFrequency = MIN_RELATIVE_FREQUENCY;
588 } else if (relativeFrequency > MAX_RELATIVE_FREQUENCY) {
589 relativeFrequency = MAX_RELATIVE_FREQUENCY;
590 }
591 block.setRelativeFrequency(relativeFrequency);
592 }
593
594 }
595
596 private void computeLoopInformation() {
597 loops = new ArrayList<>();
598 if (graph.hasLoops()) {
599 Block[] stack = new Block[this.reversePostOrder.length];
600 for (Block block : reversePostOrder) {
601 AbstractBeginNode beginNode = block.getBeginNode();
602 if (beginNode instanceof LoopBeginNode) {
603 Loop<Block> parent = block.getLoop();
604 Loop<Block> loop = new HIRLoop(parent, loops.size(), block);
605 if (parent != null) {
606 parent.getChildren().add(loop);
607 }
608 loops.add(loop);
609 block.setLoop(loop);
610 loop.getBlocks().add(block);
611
612 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
613 for (LoopEndNode end : loopBegin.loopEnds()) {
614 Block endBlock = nodeToBlock.get(end);
615 computeLoopBlocks(endBlock, loop, stack, true);
616 }
617
618 // Note that at this point, due to traversal order, child loops of `loop` have
619 // not been discovered yet.
620 for (Block b : loop.getBlocks()) {
621 for (Block sux : b.getSuccessors()) {
622 if (sux.getLoop() != loop) {
623 assert sux.getLoopDepth() < loop.getDepth();
624 loop.getNaturalExits().add(sux);
625 }
626 }
627 }
628 loop.getNaturalExits().sort(BLOCK_ID_COMPARATOR);
629
630 if (!graph.getGuardsStage().areFrameStatesAtDeopts()) {
631 for (LoopExitNode exit : loopBegin.loopExits()) {
632 Block exitBlock = nodeToBlock.get(exit);
633 assert exitBlock.getPredecessorCount() == 1;
634 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true);
635 loop.getLoopExits().add(exitBlock);
636 }
637 loop.getLoopExits().sort(BLOCK_ID_COMPARATOR);
638
639 // The following loop can add new blocks to the end of the loop's block
640 // list.
641 int size = loop.getBlocks().size();
642 for (int i = 0; i < size; ++i) {
643 Block b = loop.getBlocks().get(i);
644 for (Block sux : b.getSuccessors()) {
645 if (sux.getLoop() != loop) {
646 AbstractBeginNode begin = sux.getBeginNode();
647 if (!loopBegin.isLoopExit(begin)) {
648 assert !(begin instanceof LoopBeginNode);
649 assert sux.getLoopDepth() < loop.getDepth();
650 graph.getDebug().log(DebugContext.VERBOSE_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux);
651 computeLoopBlocks(sux, loop, stack, false);
652 }
653 }
654 }
655 }
656 } else {
657 loop.getLoopExits().addAll(loop.getNaturalExits());
658 }
659 }
660 }
661 }
662 }
663
664 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) {
665 if (start.getLoop() != loop) {
666 start.setLoop(loop);
667 stack[0] = start;
668 loop.getBlocks().add(start);
669 int tos = 0;
670 do {
671 Block block = stack[tos--];
672
673 // Add predecessors or successors to the loop.
674 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
675 if (b.getLoop() != loop) {
676 stack[++tos] = b;
677 b.setLoop(loop);
678 loop.getBlocks().add(b);
679 }
680 }
681 } while (tos >= 0);
682 }
683 }
684
685 public void computePostdominators() {
686
687 Block[] reversePostOrderTmp = this.reversePostOrder;
688 outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) {
689 Block block = reversePostOrderTmp[j];
690 if (block.isLoopEnd()) {
691 // We do not want the loop header registered as the postdominator of the loop end.
692 continue;
693 }
694 if (block.getSuccessorCount() == 0) {
695 // No successors => no postdominator.
696 continue;
697 }
698 Block firstSucc = block.getSuccessors()[0];
699 if (block.getSuccessorCount() == 1) {
700 block.postdominator = firstSucc;
701 continue;
702 }
703 Block postdominator = firstSucc;
704 for (Block sux : block.getSuccessors()) {
705 postdominator = commonPostdominator(postdominator, sux);
706 if (postdominator == null) {
707 // There is a dead end => no postdominator available.
708 continue outer;
709 }
710 }
711 assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
712 block.setPostDominator(postdominator);
713 }
714 }
715
716 private static Block commonPostdominator(Block a, Block b) {
717 Block iterA = a;
718 Block iterB = b;
719 while (iterA != iterB) {
720 if (iterA.getId() < iterB.getId()) {
721 iterA = iterA.getPostdominator();
722 if (iterA == null) {
723 return null;
724 }
725 } else {
726 assert iterB.getId() < iterA.getId();
727 iterB = iterB.getPostdominator();
728 if (iterB == null) {
729 return null;
730 }
731 }
732 }
733 return iterA;
734 }
735
736 public void setNodeToBlock(NodeMap<Block> nodeMap) {
737 this.nodeToBlock = nodeMap;
738 }
739
740 /**
741 * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_RELATIVE_FREQUENCY} and
742 * {@link ControlFlowGraph#MAX_RELATIVE_FREQUENCY}.
743 */
744 public static double multiplyRelativeFrequencies(double a, double b) {
745 assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b;
746 double r = a * b;
747 if (r > MAX_RELATIVE_FREQUENCY) {
748 return MAX_RELATIVE_FREQUENCY;
749 }
750 if (r < MIN_RELATIVE_FREQUENCY) {
751 return MIN_RELATIVE_FREQUENCY;
752 }
753 return r;
754 }
755 }