1d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 10d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// BreakCriticalEdges pass - Break all of the critical edges in the CFG by 11d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// inserting a dummy basic block. This pass may be "required" by passes that 12d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// cannot deal with critical edges. For this usage, the structure type is 13d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// forward declared. This pass obviously invalidates the CFG, but can update 14301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich// dominator trees. 15d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 16d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===----------------------------------------------------------------------===// 17d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 18d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 21ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/AliasAnalysis.h" 2281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 230ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner#include "llvm/Analysis/LoopInfo.h" 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 29c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/BasicBlockUtils.h" 31f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "break-crit-edges" 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 35d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumBroken, "Number of blocks inserted"); 366de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 37d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 386726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct BreakCriticalEdges : public FunctionPass { 39ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson BreakCriticalEdges() : FunctionPass(ID) { 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 43794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 4437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool runOnFunction(Function &F) override { 45ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 46ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 47ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 48ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; 49ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned N = 50ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI)); 5137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines NumBroken += N; 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return N > 0; 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 54fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<DominatorTreeWrapperPass>(); 57ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addPreserved<LoopInfoWrapperPass>(); 5898bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner 5998bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner // No loop canonicalization guarantees are broken by this pass. 6098bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addPreservedID(LoopSimplifyID); 616de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 626de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 636de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 64d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 65844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BreakCriticalEdges::ID = 0; 6602dd53e1c5b941ca5f60fca1b95ebcaf9ccd1dfcOwen AndersonINITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", 67ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Break critical edges in CFG", false, false) 68844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 697a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 7090c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; 711e5fdf8ba0453baafe062525dc8472846da3ec1fChris LattnerFunctionPass *llvm::createBreakCriticalEdgesPass() { 721e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner return new BreakCriticalEdges(); 731e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner} 74d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 75363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 76363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// Implementation of the external critical edge manipulation functions 77363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 78eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// When a loop exit edge is split, LCSSA form may require new PHIs in the new 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// exit block. This function inserts the new PHIs, as needed. Preds is a list 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// the old loop exit, now the successor of SplitBB. 8338da2a8cc1a41147efac423cb97caf3db90f73e7Bill Wendlingstatic void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 84c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *SplitBB, 85c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *DestBB) { 86c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // SplitBB shouldn't have anything non-trivial in it yet. 87bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || 88bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); 89c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 90bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling // For each PHI in the destination block. 91c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman for (BasicBlock::iterator I = DestBB->begin(); 92c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) { 93c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman unsigned Idx = PN->getBasicBlockIndex(SplitBB); 94c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman Value *V = PN->getIncomingValue(Idx); 95bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling 96c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // If the input is a PHI which already satisfies LCSSA, don't create 97c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // a new one. 98c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (const PHINode *VP = dyn_cast<PHINode>(V)) 99c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (VP->getParent() == SplitBB) 100c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman continue; 101bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling 102c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Otherwise a new PHI is needed. Create one and populate it. 103f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PHINode *NewPN = PHINode::Create( 104f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PN->getType(), Preds.size(), "split", 105f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); 106c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman for (unsigned i = 0, e = Preds.size(); i != e; ++i) 107c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman NewPN->addIncoming(V, Preds[i]); 108bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling 109c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Update the original PHI. 110c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PN->setIncomingValue(Idx, NewPN); 111c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 112c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman} 113c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarBasicBlock * 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarllvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const CriticalEdgeSplittingOptions &Options) { 117ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges)) 118ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 1192aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 1201b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner assert(!isa<IndirectBrInst>(TI) && 1211b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner "Cannot split critical edge from IndirectBrInst"); 1222aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 123eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 1246918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 125eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 126f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Splitting the critical edge to a pad block is non-trivial. Don't do 127490606e613566d1c7d49d2544c76c207a2555915Bill Wendling // it in this generic function. 128f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DestBB->isEHPad()) return nullptr; 129490606e613566d1c7d49d2544c76c207a2555915Bill Wendling 130eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 1311d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), 1321d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); 133277cccc58fcbc6da6c83b5ccdb2c0ec0ab46bbc1Chris Lattner // Create our unconditional branch. 134c9ea771cb89567ba0df4a0dac58d707429e3fd31Devang Patel BranchInst *NewBI = BranchInst::Create(DestBB, NewBB); 135c9ea771cb89567ba0df4a0dac58d707429e3fd31Devang Patel NewBI->setDebugLoc(TI->getDebugLoc()); 136fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 13727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Branch to the new block, breaking the edge. 138eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 139eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 140eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 141eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 142f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Function::iterator FBBI = TIBB->getIterator(); 143261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F.getBasicBlockList().insert(++FBBI, NewBB); 1442aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 145eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 146eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 14795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad { 14895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad unsigned BBIdx = 0; 14995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 15095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // We no longer enter through TIBB, now we come in through NewBB. 15195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Revector exactly one entry in the PHI node that used to come from 15295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // TIBB to come from NewBB. 15395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PHINode *PN = cast<PHINode>(I); 15495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad 15595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Reuse the previous value of BBIdx if it lines up. In cases where we 15695c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // have multiple phi nodes with *lots* of predecessors, this is a speed 15795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // win because we don't have to scan the PHI looking for TIBB. This 15895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // happens because the BB list of PHI nodes are usually in the same 15995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // order. 16095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad if (PN->getIncomingBlock(BBIdx) != TIBB) 1612aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick BBIdx = PN->getBasicBlockIndex(TIBB); 16295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PN->setIncomingBlock(BBIdx, NewBB); 1636686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner } 164eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 1652aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 16627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // If there are any other edges from TIBB to DestBB, update those to go 16727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // through the split block, making those edges non-critical as well (and 16827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // reducing the number of phi entries in the DestBB if relevant). 169ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Options.MergeIdenticalEdges) { 17027e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 17127e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (TI->getSuccessor(i) != DestBB) continue; 1722aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 17327e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Remove an entry for TIBB from DestBB phi nodes. 174ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DestBB->removePredecessor(TIBB, Options.DontDeleteUselessPHIs); 1752aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 17627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // We found another edge to DestBB, go to NewBB instead. 17727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner TI->setSuccessor(i, NewBB); 17827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 17927e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 1802aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 1816686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner // If we have nothing to update, just return. 182ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *DT = Options.DT; 183ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *LI = Options.LI; 184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!DT && !LI) 1856686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner return NewBB; 186e802a023d98b06307831cd122e61da86431e8dacChris Lattner 18786f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Now update analysis information. Since the only predecessor of NewBB is 18886f7b2100c7b6b426869178327e352d122056f73Chris Lattner // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate 18986f7b2100c7b6b426869178327e352d122056f73Chris Lattner // anything, as there are other successors of DestBB. However, if all other 19086f7b2100c7b6b426869178327e352d122056f73Chris Lattner // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a 19186f7b2100c7b6b426869178327e352d122056f73Chris Lattner // loop header) then NewBB dominates DestBB. 19286f7b2100c7b6b426869178327e352d122056f73Chris Lattner SmallVector<BasicBlock*, 8> OtherPreds; 193eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 1942f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner // If there is a PHI in the block, loop over predecessors with it, which is 1952f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner // faster than iterating pred_begin/end. 1962f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner if (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 1972f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1982f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner if (PN->getIncomingBlock(i) != NewBB) 1992f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner OtherPreds.push_back(PN->getIncomingBlock(i)); 2002f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner } else { 2012f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); 2027556cf541bd91247127f1552fbd36c979777f70cGabor Greif I != E; ++I) { 2037556cf541bd91247127f1552fbd36c979777f70cGabor Greif BasicBlock *P = *I; 2047556cf541bd91247127f1552fbd36c979777f70cGabor Greif if (P != NewBB) 20570e5e222dbae95cd75ae0610aa6740f886a7907eChris Lattner OtherPreds.push_back(P); 2067556cf541bd91247127f1552fbd36c979777f70cGabor Greif } 2072f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner } 2087556cf541bd91247127f1552fbd36c979777f70cGabor Greif 20986f7b2100c7b6b426869178327e352d122056f73Chris Lattner bool NewBBDominatesDestBB = true; 2102aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 211c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 2126686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner if (DT) { 21326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *TINode = DT->getNode(TIBB); 214fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 215c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 216c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 217c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 21886f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (TINode) { // Don't break unreachable code! 21983beaee227dad622a7e378897c6f29b511388fa0Devang Patel DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DomTreeNode *DestBBNode = nullptr; 2212aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 22286f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. 22386f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!OtherPreds.empty()) { 22486f7b2100c7b6b426869178327e352d122056f73Chris Lattner DestBBNode = DT->getNode(DestBB); 22586f7b2100c7b6b426869178327e352d122056f73Chris Lattner while (!OtherPreds.empty() && NewBBDominatesDestBB) { 22626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) 2279a51157db555395f7a6ad89faec40b3afa121091Devang Patel NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); 22886f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.pop_back(); 22986f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 23086f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.clear(); 23186f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 2322aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 23386f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 23486f7b2100c7b6b426869178327e352d122056f73Chris Lattner // doesn't dominate anything. 23586f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (NewBBDominatesDestBB) { 23686f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!DestBBNode) DestBBNode = DT->getNode(DestBB); 23786f7b2100c7b6b426869178327e352d122056f73Chris Lattner DT->changeImmediateDominator(DestBBNode, NewBBNode); 23886f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 23986f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 240eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 2416918c079a1393be8ae551d699479fbfa39b99277Chris Lattner 2420ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Update LoopInfo if it is around. 2436686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner if (LI) { 2445c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (Loop *TIL = LI->getLoopFor(TIBB)) { 2455c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If one or the other blocks were not in a loop, the new block is not 2465c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // either, and thus LI doesn't need to be updated. 2470ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 2480ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (TIL == DestLoop) { 2490ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Both in the same loop, the NewBB joins loop. 250ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DestLoop->addBasicBlockToLoop(NewBB, *LI); 25192329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (TIL->contains(DestLoop)) { 25286f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an outer loop to an inner loop. Add to the outer loop. 253ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TIL->addBasicBlockToLoop(NewBB, *LI); 25492329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (DestLoop->contains(TIL)) { 25586f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an inner loop to an outer loop. Add to the outer loop. 256ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DestLoop->addBasicBlockToLoop(NewBB, *LI); 2570ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else { 2580ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from two loops with no containment relation. Because these 2590ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // are natural loops, we know that the destination block must be the 2600ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // header of its loop (adding a branch into a loop elsewhere would 2610ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // create an irreducible loop). 2620ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner assert(DestLoop->getHeader() == DestBB && 2630ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner "Should not create irreducible loops!"); 2640ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *P = DestLoop->getParentLoop()) 265ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines P->addBasicBlockToLoop(NewBB, *LI); 2660ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 2670ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 268ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If TIBB is in a loop and DestBB is outside of that loop, we may need 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // to update LoopSimplify form and LCSSA form. 271ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!TIL->contains(DestBB)) { 272c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman assert(!TIL->contains(NewBB) && 273c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman "Split point for loop exit is contained in loop!"); 274c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 275c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Update LCSSA form in the newly created exit block. 276ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Options.PreserveLCSSA) { 27738da2a8cc1a41147efac423cb97caf3db90f73e7Bill Wendling createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); 278ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 279c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The only that we can break LoopSimplify form by splitting a critical 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // edge is if after the split there exists some edge from TIL to DestBB 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // *and* the only edge into DestBB from outside of TIL is that of 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // is the new exit block and it has no non-loop predecessors. If the 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // second isn't true, then DestBB was not in LoopSimplify form prior to 28636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the split as it had a non-loop predecessor. In both of these cases, 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the predecessor must be directly in TIL, not in a subloop, or again 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // LoopSimplify doesn't hold. 28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<BasicBlock *, 4> LoopPreds; 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++I) { 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *P = *I; 29336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (P == NewBB) 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; // The new block is known. 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (LI->getLoopFor(P) != TIL) { 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // No need to re-simplify, it wasn't to start with. 29736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopPreds.clear(); 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 299c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopPreds.push_back(P); 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!LoopPreds.empty()) { 303f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); 304ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *NewExitBB = SplitBlockPredecessors( 305f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA); 306ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Options.PreserveLCSSA) 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); 3085c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3095c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3105c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3110ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3125c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 3135c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman return NewBB; 314eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 315