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 }