1 /* 2 * Copyright (c) 2011, 2017, 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 probability values to be become too small or too high as this makes frequency 57 * calculations over- or underflow the range of a double. This commonly happens with infinite 58 * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent 59 * supported by double. That way we can never overflow to infinity when multiplying two 60 * probability values. 61 */ 62 public static final double MIN_PROBABILITY = 0x1.0p-500; 63 public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY; 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.computeProbabilities(); 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.isDeleted(); 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 private void computeProbabilities() { 554 555 for (Block block : reversePostOrder) { 556 Block[] predecessors = block.getPredecessors(); 557 558 double probability; 559 if (predecessors.length == 0) { 560 probability = 1D; 561 } else if (predecessors.length == 1) { 562 Block pred = predecessors[0]; 563 probability = pred.probability; 564 if (pred.getSuccessorCount() > 1) { 565 assert pred.getEndNode() instanceof ControlSplitNode; 566 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode(); 567 probability = multiplyProbabilities(probability, controlSplit.probability(block.getBeginNode())); 568 } 569 } else { 570 probability = predecessors[0].probability; 571 for (int i = 1; i < predecessors.length; ++i) { 572 probability += predecessors[i].probability; 573 } 574 575 if (block.getBeginNode() instanceof LoopBeginNode) { 576 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode(); 577 probability = multiplyProbabilities(probability, loopBegin.loopFrequency()); 578 } 579 } 580 if (probability < MIN_PROBABILITY) { 581 probability = MIN_PROBABILITY; 582 } else if (probability > MAX_PROBABILITY) { 583 probability = MAX_PROBABILITY; 584 } 585 block.setProbability(probability); 586 } 587 588 } 589 590 private void computeLoopInformation() { 591 loops = new ArrayList<>(); 592 if (graph.hasLoops()) { 593 Block[] stack = new Block[this.reversePostOrder.length]; 594 for (Block block : reversePostOrder) { 595 AbstractBeginNode beginNode = block.getBeginNode(); 596 if (beginNode instanceof LoopBeginNode) { 597 Loop<Block> parent = block.getLoop(); 598 Loop<Block> loop = new HIRLoop(parent, loops.size(), block); 599 if (parent != null) { 600 parent.getChildren().add(loop); 601 } 602 loops.add(loop); 603 block.setLoop(loop); 604 loop.getBlocks().add(block); 605 606 LoopBeginNode loopBegin = (LoopBeginNode) beginNode; 607 for (LoopEndNode end : loopBegin.loopEnds()) { 608 Block endBlock = nodeToBlock.get(end); 609 computeLoopBlocks(endBlock, loop, stack, true); 610 } 611 612 if (graph.getGuardsStage() != GuardsStage.AFTER_FSA) { 613 for (LoopExitNode exit : loopBegin.loopExits()) { 614 Block exitBlock = nodeToBlock.get(exit); 615 assert exitBlock.getPredecessorCount() == 1; 616 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true); 617 loop.addExit(exitBlock); 618 } 619 620 // The following loop can add new blocks to the end of the loop's block 621 // list. 622 int size = loop.getBlocks().size(); 623 for (int i = 0; i < size; ++i) { 624 Block b = loop.getBlocks().get(i); 625 for (Block sux : b.getSuccessors()) { 626 if (sux.getLoop() != loop) { 627 AbstractBeginNode begin = sux.getBeginNode(); 628 if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) { 629 graph.getDebug().log(DebugContext.VERBOSE_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux); 630 computeLoopBlocks(sux, loop, stack, false); 631 } 632 } 633 } 634 } 635 } 636 } 637 } 638 } 639 640 /* 641 * Compute the loop exit blocks after FSA. 642 */ 643 if (graph.getGuardsStage() == GuardsStage.AFTER_FSA) { 644 for (Block b : reversePostOrder) { 645 if (b.getLoop() != null) { 646 for (Block succ : b.getSuccessors()) { 647 // if the loop of the succ is a different one (or none) 648 if (b.getLoop() != succ.getLoop()) { 649 // and the succ loop is not a child loop of the curr one 650 if (succ.getLoop() == null) { 651 // we might exit multiple loops if b.loops is not a loop at depth 0 652 Loop<Block> curr = b.getLoop(); 653 while (curr != null) { 654 curr.addExit(succ); 655 curr = curr.getParent(); 656 } 657 } else { 658 /* 659 * succ also has a loop, might be a child loop 660 * 661 * if it is a child loop we do not exit a loop. if it is a loop 662 * different than b.loop and not a child loop it must be a parent 663 * loop, thus we exit all loops between b.loop and succ.loop 664 * 665 * if we exit multiple loops immediately after each other the 666 * bytecode parser might generate loop exit nodes after another and 667 * the CFG will identify them as separate blocks, we just take the 668 * first one and exit all loops at this one 669 */ 670 if (succ.getLoop().getParent() != b.getLoop()) { 671 assert succ.getLoop().getDepth() < b.getLoop().getDepth(); 672 // b.loop must not be a transitive parent of succ.loop 673 assert !Loop.transitiveParentLoop(succ.getLoop(), b.getLoop()); 674 Loop<Block> curr = b.getLoop(); 675 while (curr != null && curr != succ.getLoop()) { 676 curr.addExit(succ); 677 curr = curr.getParent(); 678 } 679 } 680 } 681 } 682 } 683 } 684 } 685 } 686 687 } 688 689 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) { 690 if (start.getLoop() != loop) { 691 start.setLoop(loop); 692 stack[0] = start; 693 loop.getBlocks().add(start); 694 int tos = 0; 695 do { 696 Block block = stack[tos--]; 697 698 // Add predecessors or successors to the loop. 699 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) { 700 if (b.getLoop() != loop) { 701 stack[++tos] = b; 702 b.setLoop(loop); 703 loop.getBlocks().add(b); 704 } 705 } 706 } while (tos >= 0); 707 } 708 } 709 710 public void computePostdominators() { 711 712 Block[] reversePostOrderTmp = this.reversePostOrder; 713 outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) { 714 Block block = reversePostOrderTmp[j]; 715 if (block.isLoopEnd()) { 716 // We do not want the loop header registered as the postdominator of the loop end. 717 continue; 718 } 719 if (block.getSuccessorCount() == 0) { 720 // No successors => no postdominator. 721 continue; 722 } 723 Block firstSucc = block.getSuccessors()[0]; 724 if (block.getSuccessorCount() == 1) { 725 block.postdominator = firstSucc; 726 continue; 727 } 728 Block postdominator = firstSucc; 729 for (Block sux : block.getSuccessors()) { 730 postdominator = commonPostdominator(postdominator, sux); 731 if (postdominator == null) { 732 // There is a dead end => no postdominator available. 733 continue outer; 734 } 735 } 736 assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator; 737 block.setPostDominator(postdominator); 738 } 739 } 740 741 private static Block commonPostdominator(Block a, Block b) { 742 Block iterA = a; 743 Block iterB = b; 744 while (iterA != iterB) { 745 if (iterA.getId() < iterB.getId()) { 746 iterA = iterA.getPostdominator(); 747 if (iterA == null) { 748 return null; 749 } 750 } else { 751 assert iterB.getId() < iterA.getId(); 752 iterB = iterB.getPostdominator(); 753 if (iterB == null) { 754 return null; 755 } 756 } 757 } 758 return iterA; 759 } 760 761 public void setNodeToBlock(NodeMap<Block> nodeMap) { 762 this.nodeToBlock = nodeMap; 763 } 764 765 /** 766 * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_PROBABILITY} and 767 * {@link ControlFlowGraph#MAX_PROBABILITY}. 768 */ 769 public static double multiplyProbabilities(double a, double b) { 770 assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b; 771 double r = a * b; 772 if (r > MAX_PROBABILITY) { 773 return MAX_PROBABILITY; 774 } 775 if (r < MIN_PROBABILITY) { 776 return MIN_PROBABILITY; 777 } 778 return r; 779 } 780 }