1/* 2 * Copyright (c) 2011, 2016, 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 */ 23package org.graalvm.compiler.nodes.cfg; 24 25import java.util.ArrayList; 26import java.util.Arrays; 27import java.util.Collections; 28import java.util.List; 29 30import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph; 31import org.graalvm.compiler.core.common.cfg.CFGVerifier; 32import org.graalvm.compiler.core.common.cfg.Loop; 33import org.graalvm.compiler.debug.Debug; 34import org.graalvm.compiler.debug.GraalError; 35import org.graalvm.compiler.graph.Node; 36import org.graalvm.compiler.graph.NodeMap; 37import org.graalvm.compiler.nodes.AbstractBeginNode; 38import org.graalvm.compiler.nodes.AbstractEndNode; 39import org.graalvm.compiler.nodes.ControlSplitNode; 40import org.graalvm.compiler.nodes.EndNode; 41import org.graalvm.compiler.nodes.FixedNode; 42import org.graalvm.compiler.nodes.FixedWithNextNode; 43import org.graalvm.compiler.nodes.IfNode; 44import org.graalvm.compiler.nodes.LoopBeginNode; 45import org.graalvm.compiler.nodes.LoopEndNode; 46import org.graalvm.compiler.nodes.LoopExitNode; 47import org.graalvm.compiler.nodes.MergeNode; 48import org.graalvm.compiler.nodes.StructuredGraph; 49import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage; 50 51public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> { 52 /** 53 * Don't allow probability values to be become too small or too high as this makes frequency 54 * calculations over- or underflow the range of a double. This commonly happens with infinite 55 * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent 56 * supported by double. That way we can never overflow to infinity when multiplying two 57 * probability values. 58 */ 59 public static final double MIN_PROBABILITY = 0x1.0p-500; 60 public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY; 61 62 public final StructuredGraph graph; 63 64 private NodeMap<Block> nodeToBlock; 65 private Block[] reversePostOrder; 66 private List<Loop<Block>> loops; 67 68 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) { 69 ControlFlowGraph cfg = new ControlFlowGraph(graph); 70 cfg.identifyBlocks(); 71 cfg.computeProbabilities(); 72 73 if (computeLoops) { 74 cfg.computeLoopInformation(); 75 } 76 if (computeDominators) { 77 cfg.computeDominators(); 78 } 79 if (computePostdominators) { 80 cfg.computePostdominators(); 81 } 82 // there's not much to verify when connectBlocks == false 83 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg); 84 return cfg; 85 } 86 87 private ControlFlowGraph(StructuredGraph graph) { 88 this.graph = graph; 89 this.nodeToBlock = graph.createNodeMap(); 90 } 91 92 private void computeDominators() { 93 assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator"; 94 Block[] blocks = reversePostOrder; 95 for (int i = 1; i < blocks.length; i++) { 96 Block block = blocks[i]; 97 assert block.getPredecessorCount() > 0; 98 Block dominator = null; 99 for (Block pred : block.getPredecessors()) { 100 if (!pred.isLoopEnd()) { 101 dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred)); 102 } 103 } 104 // set dominator 105 block.setDominator(dominator); 106 if (dominator.getDominated().equals(Collections.emptyList())) { 107 dominator.setDominated(new ArrayList<>()); 108 } 109 dominator.getDominated().add(block); 110 } 111 calcDominatorRanges(getStartBlock(), reversePostOrder.length); 112 } 113 114 private static void calcDominatorRanges(Block block, int size) { 115 Block[] stack = new Block[size]; 116 stack[0] = block; 117 int tos = 0; 118 int myNumber = 0; 119 120 do { 121 Block cur = stack[tos]; 122 List<Block> dominated = cur.getDominated(); 123 124 if (cur.getDominatorNumber() == -1) { 125 cur.setDominatorNumber(myNumber); 126 if (dominated.size() > 0) { 127 // Push children onto stack. 128 for (Block b : dominated) { 129 stack[++tos] = b; 130 } 131 } else { 132 cur.setMaxChildDomNumber(myNumber); 133 --tos; 134 } 135 ++myNumber; 136 } else { 137 cur.setMaxChildDomNumber(dominated.get(0).getMaxChildDominatorNumber()); 138 --tos; 139 } 140 } while (tos >= 0); 141 } 142 143 private static Block commonDominatorRaw(Block a, Block b) { 144 int aDomDepth = a.getDominatorDepth(); 145 int bDomDepth = b.getDominatorDepth(); 146 if (aDomDepth > bDomDepth) { 147 return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b); 148 } else { 149 return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth)); 150 } 151 } 152 153 private static Block commonDominatorRawSameDepth(Block a, Block b) { 154 Block iterA = a; 155 Block iterB = b; 156 while (iterA != iterB) { 157 iterA = iterA.getDominator(); 158 iterB = iterB.getDominator(); 159 } 160 return iterA; 161 } 162 163 @Override 164 public Block[] getBlocks() { 165 return reversePostOrder; 166 } 167 168 @Override 169 public Block getStartBlock() { 170 return reversePostOrder[0]; 171 } 172 173 public Block[] reversePostOrder() { 174 return reversePostOrder; 175 } 176 177 public NodeMap<Block> getNodeToBlock() { 178 return nodeToBlock; 179 } 180 181 public Block blockFor(Node node) { 182 return nodeToBlock.get(node); 183 } 184 185 @Override 186 public List<Loop<Block>> getLoops() { 187 return loops; 188 } 189 190 private void identifyBlock(Block block) { 191 FixedWithNextNode cur = block.getBeginNode(); 192 while (true) { 193 assert !cur.isDeleted(); 194 assert nodeToBlock.get(cur) == null; 195 nodeToBlock.set(cur, block); 196 FixedNode next = cur.next(); 197 if (next instanceof AbstractBeginNode) { 198 block.endNode = cur; 199 return; 200 } else if (next instanceof FixedWithNextNode) { 201 cur = (FixedWithNextNode) next; 202 } else { 203 nodeToBlock.set(next, block); 204 block.endNode = next; 205 return; 206 } 207 } 208 } 209 210 /** 211 * Identify and connect blocks (including loop backward edges). Predecessors need to be in the 212 * order expected when iterating phi inputs. 213 */ 214 private void identifyBlocks() { 215 // Find all block headers. 216 int numBlocks = 0; 217 for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) { 218 Block block = new Block(begin); 219 identifyBlock(block); 220 numBlocks++; 221 } 222 223 // Compute reverse post order. 224 int count = 0; 225 NodeMap<Block> nodeMap = this.nodeToBlock; 226 Block[] stack = new Block[numBlocks]; 227 int tos = 0; 228 Block startBlock = blockFor(graph.start()); 229 stack[0] = startBlock; 230 startBlock.setPredecessors(Block.EMPTY_ARRAY); 231 do { 232 Block block = stack[tos]; 233 int id = block.getId(); 234 if (id == BLOCK_ID_INITIAL) { 235 // First time we see this block: push all successors. 236 FixedNode last = block.getEndNode(); 237 if (last instanceof EndNode) { 238 EndNode endNode = (EndNode) last; 239 Block suxBlock = nodeMap.get(endNode.merge()); 240 if (suxBlock.getId() == BLOCK_ID_INITIAL) { 241 stack[++tos] = suxBlock; 242 } 243 block.setSuccessors(new Block[]{suxBlock}); 244 } else if (last instanceof IfNode) { 245 IfNode ifNode = (IfNode) last; 246 Block trueSucc = nodeMap.get(ifNode.trueSuccessor()); 247 stack[++tos] = trueSucc; 248 Block falseSucc = nodeMap.get(ifNode.falseSuccessor()); 249 stack[++tos] = falseSucc; 250 block.setSuccessors(new Block[]{trueSucc, falseSucc}); 251 Block[] ifPred = new Block[]{block}; 252 trueSucc.setPredecessors(ifPred); 253 falseSucc.setPredecessors(ifPred); 254 } else if (last instanceof LoopEndNode) { 255 LoopEndNode loopEndNode = (LoopEndNode) last; 256 block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())}); 257 // Nothing to do push onto the stack. 258 } else { 259 assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode."; 260 int startTos = tos; 261 Block[] ifPred = new Block[]{block}; 262 for (Node suxNode : last.successors()) { 263 Block sux = nodeMap.get(suxNode); 264 stack[++tos] = sux; 265 sux.setPredecessors(ifPred); 266 } 267 int suxCount = tos - startTos; 268 Block[] successors = new Block[suxCount]; 269 System.arraycopy(stack, startTos + 1, successors, 0, suxCount); 270 block.setSuccessors(successors); 271 } 272 block.setId(BLOCK_ID_VISITED); 273 AbstractBeginNode beginNode = block.getBeginNode(); 274 if (beginNode instanceof LoopBeginNode) { 275 computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode); 276 } else if (beginNode instanceof MergeNode) { 277 MergeNode mergeNode = (MergeNode) beginNode; 278 int forwardEndCount = mergeNode.forwardEndCount(); 279 Block[] predecessors = new Block[forwardEndCount]; 280 for (int i = 0; i < forwardEndCount; ++i) { 281 predecessors[i] = nodeMap.get(mergeNode.forwardEndAt(i)); 282 } 283 block.setPredecessors(predecessors); 284 } 285 286 } else if (id == BLOCK_ID_VISITED) { 287 // Second time we see this block: All successors have been processed, so add block 288 // to result list. Can safely reuse the stack for this. 289 --tos; 290 count++; 291 int index = numBlocks - count; 292 stack[index] = block; 293 block.setId(index); 294 } else { 295 throw GraalError.shouldNotReachHere(); 296 } 297 } while (tos >= 0); 298 299 // Compute reverse postorder and number blocks. 300 assert count == numBlocks : "all blocks must be reachable"; 301 this.reversePostOrder = stack; 302 } 303 304 private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) { 305 int forwardEndCount = loopBeginNode.forwardEndCount(); 306 LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds(); 307 Block[] predecessors = new Block[forwardEndCount + loopEnds.length]; 308 for (int i = 0; i < forwardEndCount; ++i) { 309 predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i)); 310 } 311 for (int i = 0; i < loopEnds.length; ++i) { 312 predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]); 313 } 314 block.setPredecessors(predecessors); 315 } 316 317 private void computeProbabilities() { 318 319 for (Block block : reversePostOrder) { 320 Block[] predecessors = block.getPredecessors(); 321 322 double probability; 323 if (predecessors.length == 0) { 324 probability = 1D; 325 } else if (predecessors.length == 1) { 326 Block pred = predecessors[0]; 327 probability = pred.probability; 328 if (pred.getSuccessorCount() > 1) { 329 assert pred.getEndNode() instanceof ControlSplitNode; 330 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode(); 331 probability *= controlSplit.probability(block.getBeginNode()); 332 } 333 } else { 334 probability = predecessors[0].probability; 335 for (int i = 1; i < predecessors.length; ++i) { 336 probability += predecessors[i].probability; 337 } 338 339 if (block.getBeginNode() instanceof LoopBeginNode) { 340 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode(); 341 probability *= loopBegin.loopFrequency(); 342 } 343 } 344 if (probability < MIN_PROBABILITY) { 345 block.setProbability(MIN_PROBABILITY); 346 } else if (probability > MAX_PROBABILITY) { 347 block.setProbability(MAX_PROBABILITY); 348 } else { 349 block.setProbability(probability); 350 } 351 } 352 353 } 354 355 private void computeLoopInformation() { 356 loops = new ArrayList<>(); 357 if (graph.hasLoops()) { 358 Block[] stack = new Block[this.reversePostOrder.length]; 359 for (Block block : reversePostOrder) { 360 AbstractBeginNode beginNode = block.getBeginNode(); 361 if (beginNode instanceof LoopBeginNode) { 362 Loop<Block> loop = new HIRLoop(block.getLoop(), loops.size(), block); 363 loops.add(loop); 364 block.loop = loop; 365 loop.getBlocks().add(block); 366 367 LoopBeginNode loopBegin = (LoopBeginNode) beginNode; 368 for (LoopEndNode end : loopBegin.loopEnds()) { 369 Block endBlock = nodeToBlock.get(end); 370 computeLoopBlocks(endBlock, loop, stack, true); 371 } 372 373 if (graph.getGuardsStage() != GuardsStage.AFTER_FSA) { 374 for (LoopExitNode exit : loopBegin.loopExits()) { 375 Block exitBlock = nodeToBlock.get(exit); 376 assert exitBlock.getPredecessorCount() == 1; 377 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true); 378 loop.getExits().add(exitBlock); 379 } 380 381 // The following loop can add new blocks to the end of the loop's block 382 // list. 383 int size = loop.getBlocks().size(); 384 for (int i = 0; i < size; ++i) { 385 Block b = loop.getBlocks().get(i); 386 for (Block sux : b.getSuccessors()) { 387 if (sux.loop != loop) { 388 AbstractBeginNode begin = sux.getBeginNode(); 389 if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) { 390 Debug.log(Debug.VERBOSE_LOG_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux); 391 computeLoopBlocks(sux, loop, stack, false); 392 } 393 } 394 } 395 } 396 } 397 } 398 } 399 } 400 401 /* 402 * Compute the loop exit blocks after FSA. 403 */ 404 if (graph.getGuardsStage() == GuardsStage.AFTER_FSA) { 405 for (Block b : reversePostOrder) { 406 if (b.getLoop() != null) { 407 for (Block succ : b.getSuccessors()) { 408 // if the loop of the succ is a different one (or none) 409 if (b.getLoop() != succ.getLoop()) { 410 // and the succ loop is not a child loop of the curr one 411 if (succ.getLoop() == null) { 412 // we might exit multiple loops if b.loops is not a loop at depth 0 413 Loop<Block> curr = b.getLoop(); 414 while (curr != null) { 415 curr.getExits().add(succ); 416 curr = curr.getParent(); 417 } 418 } else { 419 /* 420 * succ also has a loop, might be a child loop 421 * 422 * if it is a child loop we do not exit a loop. if it is a loop 423 * different than b.loop and not a child loop it must be a parent 424 * loop, thus we exit all loops between b.loop and succ.loop 425 * 426 * if we exit multiple loops immediately after each other the 427 * bytecode parser might generate loop exit nodes after another and 428 * the CFG will identify them as separate blocks, we just take the 429 * first one and exit all loops at this one 430 */ 431 if (succ.getLoop().getParent() != b.getLoop()) { 432 assert succ.getLoop().getDepth() < b.getLoop().getDepth(); 433 // b.loop must not be a transitive parent of succ.loop 434 assert !Loop.transitiveParentLoop(succ.getLoop(), b.getLoop()); 435 Loop<Block> curr = b.getLoop(); 436 while (curr != null && curr != succ.getLoop()) { 437 curr.getExits().add(succ); 438 curr = curr.getParent(); 439 } 440 } 441 } 442 } 443 } 444 } 445 } 446 } 447 448 } 449 450 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) { 451 if (start.loop != loop) { 452 start.loop = loop; 453 stack[0] = start; 454 loop.getBlocks().add(start); 455 int tos = 0; 456 do { 457 Block block = stack[tos--]; 458 459 // Add predecessors or successors to the loop. 460 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) { 461 if (b.loop != loop) { 462 stack[++tos] = b; 463 b.loop = loop; 464 loop.getBlocks().add(b); 465 } 466 } 467 } while (tos >= 0); 468 } 469 } 470 471 public void computePostdominators() { 472 473 Block[] reversePostOrderTmp = this.reversePostOrder; 474 475 outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) { 476 Block block = reversePostOrderTmp[j]; 477 if (block.isLoopEnd()) { 478 // We do not want the loop header registered as the postdominator of the loop end. 479 continue; 480 } 481 if (block.getSuccessorCount() == 0) { 482 // No successors => no postdominator. 483 continue; 484 } 485 Block firstSucc = block.getSuccessors()[0]; 486 if (block.getSuccessorCount() == 1) { 487 block.postdominator = firstSucc; 488 continue; 489 } 490 Block postdominator = firstSucc; 491 for (Block sux : block.getSuccessors()) { 492 postdominator = commonPostdominator(postdominator, sux); 493 if (postdominator == null) { 494 // There is a dead end => no postdominator available. 495 continue outer; 496 } 497 } 498 assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator; 499 block.postdominator = postdominator; 500 } 501 } 502 503 private static Block commonPostdominator(Block a, Block b) { 504 Block iterA = a; 505 Block iterB = b; 506 while (iterA != iterB) { 507 if (iterA.getId() < iterB.getId()) { 508 iterA = iterA.getPostdominator(); 509 if (iterA == null) { 510 return null; 511 } 512 } else { 513 assert iterB.getId() < iterA.getId(); 514 iterB = iterB.getPostdominator(); 515 if (iterB == null) { 516 return null; 517 } 518 } 519 } 520 return iterA; 521 } 522 523 public void setNodeToBlock(NodeMap<Block> nodeMap) { 524 this.nodeToBlock = nodeMap; 525 } 526} 527