/* * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package org.graalvm.compiler.nodes.cfg; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph; import org.graalvm.compiler.core.common.cfg.CFGVerifier; import org.graalvm.compiler.core.common.cfg.Loop; import org.graalvm.compiler.debug.Debug; import org.graalvm.compiler.debug.GraalError; import org.graalvm.compiler.graph.Node; import org.graalvm.compiler.graph.NodeMap; import org.graalvm.compiler.nodes.AbstractBeginNode; import org.graalvm.compiler.nodes.AbstractEndNode; import org.graalvm.compiler.nodes.ControlSplitNode; import org.graalvm.compiler.nodes.EndNode; import org.graalvm.compiler.nodes.FixedNode; import org.graalvm.compiler.nodes.FixedWithNextNode; import org.graalvm.compiler.nodes.IfNode; import org.graalvm.compiler.nodes.LoopBeginNode; import org.graalvm.compiler.nodes.LoopEndNode; import org.graalvm.compiler.nodes.LoopExitNode; import org.graalvm.compiler.nodes.MergeNode; import org.graalvm.compiler.nodes.StructuredGraph; import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage; public final class ControlFlowGraph implements AbstractControlFlowGraph { /** * Don't allow probability values to be become too small or too high as this makes frequency * calculations over- or underflow the range of a double. This commonly happens with infinite * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent * supported by double. That way we can never overflow to infinity when multiplying two * probability values. */ public static final double MIN_PROBABILITY = 0x1.0p-500; public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY; public final StructuredGraph graph; private NodeMap nodeToBlock; private Block[] reversePostOrder; private List> loops; public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) { ControlFlowGraph cfg = new ControlFlowGraph(graph); cfg.identifyBlocks(); cfg.computeProbabilities(); if (computeLoops) { cfg.computeLoopInformation(); } if (computeDominators) { cfg.computeDominators(); } if (computePostdominators) { cfg.computePostdominators(); } // there's not much to verify when connectBlocks == false assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg); return cfg; } private ControlFlowGraph(StructuredGraph graph) { this.graph = graph; this.nodeToBlock = graph.createNodeMap(); } private void computeDominators() { assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator"; Block[] blocks = reversePostOrder; for (int i = 1; i < blocks.length; i++) { Block block = blocks[i]; assert block.getPredecessorCount() > 0; Block dominator = null; for (Block pred : block.getPredecessors()) { if (!pred.isLoopEnd()) { dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred)); } } // set dominator block.setDominator(dominator); if (dominator.getDominated().equals(Collections.emptyList())) { dominator.setDominated(new ArrayList<>()); } dominator.getDominated().add(block); } calcDominatorRanges(getStartBlock(), reversePostOrder.length); } private static void calcDominatorRanges(Block block, int size) { Block[] stack = new Block[size]; stack[0] = block; int tos = 0; int myNumber = 0; do { Block cur = stack[tos]; List dominated = cur.getDominated(); if (cur.getDominatorNumber() == -1) { cur.setDominatorNumber(myNumber); if (dominated.size() > 0) { // Push children onto stack. for (Block b : dominated) { stack[++tos] = b; } } else { cur.setMaxChildDomNumber(myNumber); --tos; } ++myNumber; } else { cur.setMaxChildDomNumber(dominated.get(0).getMaxChildDominatorNumber()); --tos; } } while (tos >= 0); } private static Block commonDominatorRaw(Block a, Block b) { int aDomDepth = a.getDominatorDepth(); int bDomDepth = b.getDominatorDepth(); if (aDomDepth > bDomDepth) { return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b); } else { return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth)); } } private static Block commonDominatorRawSameDepth(Block a, Block b) { Block iterA = a; Block iterB = b; while (iterA != iterB) { iterA = iterA.getDominator(); iterB = iterB.getDominator(); } return iterA; } @Override public Block[] getBlocks() { return reversePostOrder; } @Override public Block getStartBlock() { return reversePostOrder[0]; } public Block[] reversePostOrder() { return reversePostOrder; } public NodeMap getNodeToBlock() { return nodeToBlock; } public Block blockFor(Node node) { return nodeToBlock.get(node); } @Override public List> getLoops() { return loops; } private void identifyBlock(Block block) { FixedWithNextNode cur = block.getBeginNode(); while (true) { assert !cur.isDeleted(); assert nodeToBlock.get(cur) == null; nodeToBlock.set(cur, block); FixedNode next = cur.next(); if (next instanceof AbstractBeginNode) { block.endNode = cur; return; } else if (next instanceof FixedWithNextNode) { cur = (FixedWithNextNode) next; } else { nodeToBlock.set(next, block); block.endNode = next; return; } } } /** * Identify and connect blocks (including loop backward edges). Predecessors need to be in the * order expected when iterating phi inputs. */ private void identifyBlocks() { // Find all block headers. int numBlocks = 0; for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) { Block block = new Block(begin); identifyBlock(block); numBlocks++; } // Compute reverse post order. int count = 0; NodeMap nodeMap = this.nodeToBlock; Block[] stack = new Block[numBlocks]; int tos = 0; Block startBlock = blockFor(graph.start()); stack[0] = startBlock; startBlock.setPredecessors(Block.EMPTY_ARRAY); do { Block block = stack[tos]; int id = block.getId(); if (id == BLOCK_ID_INITIAL) { // First time we see this block: push all successors. FixedNode last = block.getEndNode(); if (last instanceof EndNode) { EndNode endNode = (EndNode) last; Block suxBlock = nodeMap.get(endNode.merge()); if (suxBlock.getId() == BLOCK_ID_INITIAL) { stack[++tos] = suxBlock; } block.setSuccessors(new Block[]{suxBlock}); } else if (last instanceof IfNode) { IfNode ifNode = (IfNode) last; Block trueSucc = nodeMap.get(ifNode.trueSuccessor()); stack[++tos] = trueSucc; Block falseSucc = nodeMap.get(ifNode.falseSuccessor()); stack[++tos] = falseSucc; block.setSuccessors(new Block[]{trueSucc, falseSucc}); Block[] ifPred = new Block[]{block}; trueSucc.setPredecessors(ifPred); falseSucc.setPredecessors(ifPred); } else if (last instanceof LoopEndNode) { LoopEndNode loopEndNode = (LoopEndNode) last; block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())}); // Nothing to do push onto the stack. } else { assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode."; int startTos = tos; Block[] ifPred = new Block[]{block}; for (Node suxNode : last.successors()) { Block sux = nodeMap.get(suxNode); stack[++tos] = sux; sux.setPredecessors(ifPred); } int suxCount = tos - startTos; Block[] successors = new Block[suxCount]; System.arraycopy(stack, startTos + 1, successors, 0, suxCount); block.setSuccessors(successors); } block.setId(BLOCK_ID_VISITED); AbstractBeginNode beginNode = block.getBeginNode(); if (beginNode instanceof LoopBeginNode) { computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode); } else if (beginNode instanceof MergeNode) { MergeNode mergeNode = (MergeNode) beginNode; int forwardEndCount = mergeNode.forwardEndCount(); Block[] predecessors = new Block[forwardEndCount]; for (int i = 0; i < forwardEndCount; ++i) { predecessors[i] = nodeMap.get(mergeNode.forwardEndAt(i)); } block.setPredecessors(predecessors); } } else if (id == BLOCK_ID_VISITED) { // Second time we see this block: All successors have been processed, so add block // to result list. Can safely reuse the stack for this. --tos; count++; int index = numBlocks - count; stack[index] = block; block.setId(index); } else { throw GraalError.shouldNotReachHere(); } } while (tos >= 0); // Compute reverse postorder and number blocks. assert count == numBlocks : "all blocks must be reachable"; this.reversePostOrder = stack; } private static void computeLoopPredecessors(NodeMap nodeMap, Block block, LoopBeginNode loopBeginNode) { int forwardEndCount = loopBeginNode.forwardEndCount(); LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds(); Block[] predecessors = new Block[forwardEndCount + loopEnds.length]; for (int i = 0; i < forwardEndCount; ++i) { predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i)); } for (int i = 0; i < loopEnds.length; ++i) { predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]); } block.setPredecessors(predecessors); } private void computeProbabilities() { for (Block block : reversePostOrder) { Block[] predecessors = block.getPredecessors(); double probability; if (predecessors.length == 0) { probability = 1D; } else if (predecessors.length == 1) { Block pred = predecessors[0]; probability = pred.probability; if (pred.getSuccessorCount() > 1) { assert pred.getEndNode() instanceof ControlSplitNode; ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode(); probability *= controlSplit.probability(block.getBeginNode()); } } else { probability = predecessors[0].probability; for (int i = 1; i < predecessors.length; ++i) { probability += predecessors[i].probability; } if (block.getBeginNode() instanceof LoopBeginNode) { LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode(); probability *= loopBegin.loopFrequency(); } } if (probability < MIN_PROBABILITY) { block.setProbability(MIN_PROBABILITY); } else if (probability > MAX_PROBABILITY) { block.setProbability(MAX_PROBABILITY); } else { block.setProbability(probability); } } } private void computeLoopInformation() { loops = new ArrayList<>(); if (graph.hasLoops()) { Block[] stack = new Block[this.reversePostOrder.length]; for (Block block : reversePostOrder) { AbstractBeginNode beginNode = block.getBeginNode(); if (beginNode instanceof LoopBeginNode) { Loop loop = new HIRLoop(block.getLoop(), loops.size(), block); loops.add(loop); block.loop = loop; loop.getBlocks().add(block); LoopBeginNode loopBegin = (LoopBeginNode) beginNode; for (LoopEndNode end : loopBegin.loopEnds()) { Block endBlock = nodeToBlock.get(end); computeLoopBlocks(endBlock, loop, stack, true); } if (graph.getGuardsStage() != GuardsStage.AFTER_FSA) { for (LoopExitNode exit : loopBegin.loopExits()) { Block exitBlock = nodeToBlock.get(exit); assert exitBlock.getPredecessorCount() == 1; computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true); loop.getExits().add(exitBlock); } // The following loop can add new blocks to the end of the loop's block // list. int size = loop.getBlocks().size(); for (int i = 0; i < size; ++i) { Block b = loop.getBlocks().get(i); for (Block sux : b.getSuccessors()) { if (sux.loop != loop) { AbstractBeginNode begin = sux.getBeginNode(); if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) { Debug.log(Debug.VERBOSE_LOG_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux); computeLoopBlocks(sux, loop, stack, false); } } } } } } } } /* * Compute the loop exit blocks after FSA. */ if (graph.getGuardsStage() == GuardsStage.AFTER_FSA) { for (Block b : reversePostOrder) { if (b.getLoop() != null) { for (Block succ : b.getSuccessors()) { // if the loop of the succ is a different one (or none) if (b.getLoop() != succ.getLoop()) { // and the succ loop is not a child loop of the curr one if (succ.getLoop() == null) { // we might exit multiple loops if b.loops is not a loop at depth 0 Loop curr = b.getLoop(); while (curr != null) { curr.getExits().add(succ); curr = curr.getParent(); } } else { /* * succ also has a loop, might be a child loop * * if it is a child loop we do not exit a loop. if it is a loop * different than b.loop and not a child loop it must be a parent * loop, thus we exit all loops between b.loop and succ.loop * * if we exit multiple loops immediately after each other the * bytecode parser might generate loop exit nodes after another and * the CFG will identify them as separate blocks, we just take the * first one and exit all loops at this one */ if (succ.getLoop().getParent() != b.getLoop()) { assert succ.getLoop().getDepth() < b.getLoop().getDepth(); // b.loop must not be a transitive parent of succ.loop assert !Loop.transitiveParentLoop(succ.getLoop(), b.getLoop()); Loop curr = b.getLoop(); while (curr != null && curr != succ.getLoop()) { curr.getExits().add(succ); curr = curr.getParent(); } } } } } } } } } private static void computeLoopBlocks(Block start, Loop loop, Block[] stack, boolean usePred) { if (start.loop != loop) { start.loop = loop; stack[0] = start; loop.getBlocks().add(start); int tos = 0; do { Block block = stack[tos--]; // Add predecessors or successors to the loop. for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) { if (b.loop != loop) { stack[++tos] = b; b.loop = loop; loop.getBlocks().add(b); } } } while (tos >= 0); } } public void computePostdominators() { Block[] reversePostOrderTmp = this.reversePostOrder; outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) { Block block = reversePostOrderTmp[j]; if (block.isLoopEnd()) { // We do not want the loop header registered as the postdominator of the loop end. continue; } if (block.getSuccessorCount() == 0) { // No successors => no postdominator. continue; } Block firstSucc = block.getSuccessors()[0]; if (block.getSuccessorCount() == 1) { block.postdominator = firstSucc; continue; } Block postdominator = firstSucc; for (Block sux : block.getSuccessors()) { postdominator = commonPostdominator(postdominator, sux); if (postdominator == null) { // There is a dead end => no postdominator available. continue outer; } } assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator; block.postdominator = postdominator; } } private static Block commonPostdominator(Block a, Block b) { Block iterA = a; Block iterB = b; while (iterA != iterB) { if (iterA.getId() < iterB.getId()) { iterA = iterA.getPostdominator(); if (iterA == null) { return null; } } else { assert iterB.getId() < iterA.getId(); iterB = iterB.getPostdominator(); if (iterB == null) { return null; } } } return iterA; } public void setNodeToBlock(NodeMap nodeMap) { this.nodeToBlock = nodeMap; } }