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 18d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "break-crit-edges" 19d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 23301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich#include "llvm/Analysis/Dominators.h" 240ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner#include "llvm/Analysis/LoopInfo.h" 25ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 29eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/Support/CFG.h" 30c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/BasicBlockUtils.h" 32f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 33d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 34d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumBroken, "Number of blocks inserted"); 356de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 36d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 376726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct BreakCriticalEdges : public FunctionPass { 38ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson BreakCriticalEdges() : FunctionPass(ID) { 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 42794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 436de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual bool runOnFunction(Function &F); 44fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 456de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 46a3ca0b648cd03cb3c003e09f2079f570ce2ac600Owen Anderson AU.addPreserved<DominatorTree>(); 470ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner AU.addPreserved<LoopInfo>(); 48ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter AU.addPreserved<ProfileInfo>(); 4998bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner 5098bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner // No loop canonicalization guarantees are broken by this pass. 5198bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addPreservedID(LoopSimplifyID); 526de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 536de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 546de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 55d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 56844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BreakCriticalEdges::ID = 0; 5702dd53e1c5b941ca5f60fca1b95ebcaf9ccd1dfcOwen AndersonINITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", 58ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Break critical edges in CFG", false, false) 59844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 607a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 6190c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; 621e5fdf8ba0453baafe062525dc8472846da3ec1fChris LattnerFunctionPass *llvm::createBreakCriticalEdgesPass() { 631e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner return new BreakCriticalEdges(); 641e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner} 65d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 66363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 67363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// edges as they are found. 68363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// 69363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 70363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner bool Changed = false; 71363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 72363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner TerminatorInst *TI = I->getTerminator(); 731b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI)) 74363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 75363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (SplitCriticalEdge(TI, i, this)) { 76363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner ++NumBroken; 77363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner Changed = true; 78363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 79363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 80363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 81363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner return Changed; 82363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner} 83363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 84363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 85363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// Implementation of the external critical edge manipulation functions 86363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 87eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 8838da2a8cc1a41147efac423cb97caf3db90f73e7Bill Wendling/// createPHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form 89c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// may require new PHIs in the new exit block. This function inserts the 90bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling/// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB 91c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// is the new loop exit block, and DestBB is the old loop exit, now the 92c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// successor of SplitBB. 9338da2a8cc1a41147efac423cb97caf3db90f73e7Bill Wendlingstatic void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 94c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *SplitBB, 95c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *DestBB) { 96c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // SplitBB shouldn't have anything non-trivial in it yet. 97bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || 98bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); 99c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 100bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling // For each PHI in the destination block. 101c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman for (BasicBlock::iterator I = DestBB->begin(); 102c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) { 103c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman unsigned Idx = PN->getBasicBlockIndex(SplitBB); 104c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman Value *V = PN->getIncomingValue(Idx); 105bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling 106c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // If the input is a PHI which already satisfies LCSSA, don't create 107c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // a new one. 108c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (const PHINode *VP = dyn_cast<PHINode>(V)) 109c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (VP->getParent() == SplitBB) 110c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman continue; 111bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling 112c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Otherwise a new PHI is needed. Create one and populate it. 113bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling PHINode *NewPN = 114bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling PHINode::Create(PN->getType(), Preds.size(), "split", 115bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SplitBB->isLandingPad() ? 116bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SplitBB->begin() : SplitBB->getTerminator()); 117c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman for (unsigned i = 0, e = Preds.size(); i != e; ++i) 118c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman NewPN->addIncoming(V, Preds[i]); 119bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling 120c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Update the original PHI. 121c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PN->setIncomingValue(Idx, NewPN); 122c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 123c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman} 124c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 125862f27ebab52aa93784462fbeaa93dacdc6a4c78Chris Lattner/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 126301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich/// split the critical edge. This will update DominatorTree information if it 127301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich/// is available, thus calling this pass will not invalidate either of them. 128301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich/// This returns the new block if the edge was split, null otherwise. 1291b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// 1301b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the 1312aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick/// specified successor will be merged into the same critical edge block. 1322aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick/// This is most commonly interesting with switch instructions, which may 1331b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// have many edges to any one destination. This ensures that all edges to that 1342aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick/// dest go to one block instead of each going to a different block, but isn't 1351b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// the standard definition of a "critical edge". 1361b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// 1371b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// It is invalid to call this function on a critical edge that starts at an 1381b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// IndirectBrInst. Splitting these edges will almost always create an invalid 139280f3fedbfc8d76014dbb25aecfd57a847fd6183Chris Lattner/// program because the address of the new block won't be the one that is jumped 1401b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// to. 1411b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// 1425c89b5240c90eb8171f999e5f06f815502d0321cDan GohmanBasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, 143f143b79b78d1d244809fa59320f2af2edf4e1a86Andrew Trick Pass *P, bool MergeIdenticalEdges, 144bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling bool DontDeleteUselessPhis, 145bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling bool SplitLandingPads) { 1465c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0; 1472aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 1481b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner assert(!isa<IndirectBrInst>(TI) && 1491b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner "Cannot split critical edge from IndirectBrInst"); 1502aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 151eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 1526918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 153eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 154490606e613566d1c7d49d2544c76c207a2555915Bill Wendling // Splitting the critical edge to a landing pad block is non-trivial. Don't do 155490606e613566d1c7d49d2544c76c207a2555915Bill Wendling // it in this generic function. 156f0dc257a8fe1325f2226d1c274c4d10c614b9e8bBill Wendling if (DestBB->isLandingPad()) return 0; 157490606e613566d1c7d49d2544c76c207a2555915Bill Wendling 158eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 1591d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), 1601d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); 161277cccc58fcbc6da6c83b5ccdb2c0ec0ab46bbc1Chris Lattner // Create our unconditional branch. 162c9ea771cb89567ba0df4a0dac58d707429e3fd31Devang Patel BranchInst *NewBI = BranchInst::Create(DestBB, NewBB); 163c9ea771cb89567ba0df4a0dac58d707429e3fd31Devang Patel NewBI->setDebugLoc(TI->getDebugLoc()); 164fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Branch to the new block, breaking the edge. 166eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 167eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 168eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 169eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 170261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FBBI = TIBB; 171261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F.getBasicBlockList().insert(++FBBI, NewBB); 1722aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 173eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 174eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 17595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad { 17695c3e48f9557adb6064d580684bb14cacec2f826Jay Foad unsigned BBIdx = 0; 17795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 17895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // We no longer enter through TIBB, now we come in through NewBB. 17995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Revector exactly one entry in the PHI node that used to come from 18095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // TIBB to come from NewBB. 18195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PHINode *PN = cast<PHINode>(I); 18295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad 18395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Reuse the previous value of BBIdx if it lines up. In cases where we 18495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // have multiple phi nodes with *lots* of predecessors, this is a speed 18595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // win because we don't have to scan the PHI looking for TIBB. This 18695c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // happens because the BB list of PHI nodes are usually in the same 18795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // order. 18895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad if (PN->getIncomingBlock(BBIdx) != TIBB) 1892aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick BBIdx = PN->getBasicBlockIndex(TIBB); 19095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PN->setIncomingBlock(BBIdx, NewBB); 1916686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner } 192eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 1932aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 19427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // If there are any other edges from TIBB to DestBB, update those to go 19527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // through the split block, making those edges non-critical as well (and 19627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // reducing the number of phi entries in the DestBB if relevant). 19727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (MergeIdenticalEdges) { 19827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 19927e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (TI->getSuccessor(i) != DestBB) continue; 2002aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 20127e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Remove an entry for TIBB from DestBB phi nodes. 202f143b79b78d1d244809fa59320f2af2edf4e1a86Andrew Trick DestBB->removePredecessor(TIBB, DontDeleteUselessPhis); 2032aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 20427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // We found another edge to DestBB, go to NewBB instead. 20527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner TI->setSuccessor(i, NewBB); 20627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 20727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 2082aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 2092aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 210eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 211e802a023d98b06307831cd122e61da86431e8dacChris Lattner // If we don't have a pass object, we can't update anything... 2125c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (P == 0) return NewBB; 2132aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 2146686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 2156686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>(); 2166686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 2172aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 2186686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner // If we have nothing to update, just return. 219301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich if (DT == 0 && LI == 0 && PI == 0) 2206686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner return NewBB; 221e802a023d98b06307831cd122e61da86431e8dacChris Lattner 22286f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Now update analysis information. Since the only predecessor of NewBB is 22386f7b2100c7b6b426869178327e352d122056f73Chris Lattner // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate 22486f7b2100c7b6b426869178327e352d122056f73Chris Lattner // anything, as there are other successors of DestBB. However, if all other 22586f7b2100c7b6b426869178327e352d122056f73Chris Lattner // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a 22686f7b2100c7b6b426869178327e352d122056f73Chris Lattner // loop header) then NewBB dominates DestBB. 22786f7b2100c7b6b426869178327e352d122056f73Chris Lattner SmallVector<BasicBlock*, 8> OtherPreds; 228eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 2292f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner // If there is a PHI in the block, loop over predecessors with it, which is 2302f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner // faster than iterating pred_begin/end. 2312f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner if (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 2322f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 2332f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner if (PN->getIncomingBlock(i) != NewBB) 2342f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner OtherPreds.push_back(PN->getIncomingBlock(i)); 2352f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner } else { 2362f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); 2377556cf541bd91247127f1552fbd36c979777f70cGabor Greif I != E; ++I) { 2387556cf541bd91247127f1552fbd36c979777f70cGabor Greif BasicBlock *P = *I; 2397556cf541bd91247127f1552fbd36c979777f70cGabor Greif if (P != NewBB) 24070e5e222dbae95cd75ae0610aa6740f886a7907eChris Lattner OtherPreds.push_back(P); 2417556cf541bd91247127f1552fbd36c979777f70cGabor Greif } 2422f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner } 2437556cf541bd91247127f1552fbd36c979777f70cGabor Greif 24486f7b2100c7b6b426869178327e352d122056f73Chris Lattner bool NewBBDominatesDestBB = true; 2452aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 246c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 2476686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner if (DT) { 24826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *TINode = DT->getNode(TIBB); 249fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 250c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 251c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 252c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 25386f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (TINode) { // Don't break unreachable code! 25483beaee227dad622a7e378897c6f29b511388fa0Devang Patel DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); 25526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *DestBBNode = 0; 2562aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 25786f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. 25886f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!OtherPreds.empty()) { 25986f7b2100c7b6b426869178327e352d122056f73Chris Lattner DestBBNode = DT->getNode(DestBB); 26086f7b2100c7b6b426869178327e352d122056f73Chris Lattner while (!OtherPreds.empty() && NewBBDominatesDestBB) { 26126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) 2629a51157db555395f7a6ad89faec40b3afa121091Devang Patel NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); 26386f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.pop_back(); 26486f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 26586f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.clear(); 26686f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 2672aeb8027d649320d5ad3a30d9bbeb71c783b50d4Andrew Trick 26886f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 26986f7b2100c7b6b426869178327e352d122056f73Chris Lattner // doesn't dominate anything. 27086f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (NewBBDominatesDestBB) { 27186f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!DestBBNode) DestBBNode = DT->getNode(DestBB); 27286f7b2100c7b6b426869178327e352d122056f73Chris Lattner DT->changeImmediateDominator(DestBBNode, NewBBNode); 27386f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 27486f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 275eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 2766918c079a1393be8ae551d699479fbfa39b99277Chris Lattner 2770ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Update LoopInfo if it is around. 2786686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner if (LI) { 2795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (Loop *TIL = LI->getLoopFor(TIBB)) { 2805c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If one or the other blocks were not in a loop, the new block is not 2815c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // either, and thus LI doesn't need to be updated. 2820ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 2830ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (TIL == DestLoop) { 2840ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Both in the same loop, the NewBB joins loop. 285d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 28692329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (TIL->contains(DestLoop)) { 28786f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an outer loop to an inner loop. Add to the outer loop. 288d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson TIL->addBasicBlockToLoop(NewBB, LI->getBase()); 28992329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (DestLoop->contains(TIL)) { 29086f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an inner loop to an outer loop. Add to the outer loop. 291d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 2920ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else { 2930ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from two loops with no containment relation. Because these 2940ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // are natural loops, we know that the destination block must be the 2950ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // header of its loop (adding a branch into a loop elsewhere would 2960ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // create an irreducible loop). 2970ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner assert(DestLoop->getHeader() == DestBB && 2980ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner "Should not create irreducible loops!"); 2990ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *P = DestLoop->getParentLoop()) 300d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson P->addBasicBlockToLoop(NewBB, LI->getBase()); 3010ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3020ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3035c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If TIBB is in a loop and DestBB is outside of that loop, split the 3045c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // other exit blocks of the loop that also have predecessors outside 3055c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // the loop, to maintain a LoopSimplify guarantee. 3065c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (!TIL->contains(DestBB) && 3075c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman P->mustPreserveAnalysisID(LoopSimplifyID)) { 308c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman assert(!TIL->contains(NewBB) && 309c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman "Split point for loop exit is contained in loop!"); 310c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 311c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Update LCSSA form in the newly created exit block. 31238da2a8cc1a41147efac423cb97caf3db90f73e7Bill Wendling if (P->mustPreserveAnalysisID(LCSSAID)) 31338da2a8cc1a41147efac423cb97caf3db90f73e7Bill Wendling createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); 314c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 3155c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // For each unique exit block... 31636106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman // FIXME: This code is functionally equivalent to the corresponding 31736106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman // loop in LoopSimplify. 3185c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman SmallVector<BasicBlock *, 4> ExitBlocks; 3195c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman TIL->getExitBlocks(ExitBlocks); 3205c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 3215c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Collect all the preds that are inside the loop, and note 3225c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // whether there are any preds outside the loop. 3235c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman SmallVector<BasicBlock *, 4> Preds; 324c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman bool HasPredOutsideOfLoop = false; 3255c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman BasicBlock *Exit = ExitBlocks[i]; 3265c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); 3279085fcab8276a8aaba33dc78bec2cdb0845351baGabor Greif I != E; ++I) { 3289085fcab8276a8aaba33dc78bec2cdb0845351baGabor Greif BasicBlock *P = *I; 32936106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman if (TIL->contains(P)) { 33036106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman if (isa<IndirectBrInst>(P->getTerminator())) { 33136106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman Preds.clear(); 33236106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman break; 33336106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman } 3349085fcab8276a8aaba33dc78bec2cdb0845351baGabor Greif Preds.push_back(P); 33536106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman } else { 336c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman HasPredOutsideOfLoop = true; 33736106040862e876a53a56f5765d6d3cd1181dd04Eli Friedman } 3389085fcab8276a8aaba33dc78bec2cdb0845351baGabor Greif } 3395c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If there are any preds not in the loop, we'll need to split 3405c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // the edges. The Preds.empty() check is needed because a block 3415c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // may appear multiple times in the list. We can't use 3425c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // getUniqueExitBlocks above because that depends on LoopSimplify 3435c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // form, which we're in the process of restoring! 344c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (!Preds.empty() && HasPredOutsideOfLoop) { 345bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling if (!Exit->isLandingPad()) { 346bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling BasicBlock *NewExitBB = 347bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SplitBlockPredecessors(Exit, Preds, "split", P); 348bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling if (P->mustPreserveAnalysisID(LCSSAID)) 349bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling createPHIsForSplitLoopExit(Preds, NewExitBB, Exit); 350bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling } else if (SplitLandingPads) { 351bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SmallVector<BasicBlock*, 8> NewBBs; 352bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling SplitLandingPadPredecessors(Exit, Preds, 353bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling ".split1", ".split2", 354bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling P, NewBBs); 355bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling if (P->mustPreserveAnalysisID(LCSSAID)) 356bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling createPHIsForSplitLoopExit(Preds, NewBBs[0], Exit); 357bfbab99b58aa530d5d6aa886ef66be42a047c756Bill Wendling } 358c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 3595c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3605c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3615c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // LCSSA form was updated above for the case where LoopSimplify is 3625c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // available, which means that all predecessors of loop exit blocks 3635c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // are within the loop. Without LoopSimplify form, it would be 3645c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // necessary to insert a new phi. 3655c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman assert((!P->mustPreserveAnalysisID(LCSSAID) || 3665c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman P->mustPreserveAnalysisID(LoopSimplifyID)) && 3675c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman "SplitCriticalEdge doesn't know how to update LCCSA form " 3685c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman "without LoopSimplify!"); 3695c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3700ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3715c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 372ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter // Update ProfileInfo if it is around. 3736686c6bf68148190309451aa9a79d2efd38ce698Chris Lattner if (PI) 3742f36ea8b74f2d81b0d14cbaf11f2158c97355dfdChris Lattner PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges); 375ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter 3765c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman return NewBB; 377eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 378