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