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