BreakCriticalEdges.cpp revision 92329c7fbe572892c17aa2d2542a10e3ea16132f
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 14363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// forward dominator (set, immediate dominators, tree, and frontier) 15363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// information. 16d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 17d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===----------------------------------------------------------------------===// 18d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 19d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "break-crit-edges" 20d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 21d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 22d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Analysis/Dominators.h" 230ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner#include "llvm/Analysis/LoopInfo.h" 24ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 25d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Function.h" 2647b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 275b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 28eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/Support/CFG.h" 29c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 3086f7b2100c7b6b426869178327e352d122056f73Chris Lattner#include "llvm/ADT/SmallVector.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.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 39ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman BreakCriticalEdges() : FunctionPass(&ID) {} 40794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 416de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual bool runOnFunction(Function &F); 42fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 436de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 44a3ca0b648cd03cb3c003e09f2079f570ce2ac600Owen Anderson AU.addPreserved<DominatorTree>(); 456918c079a1393be8ae551d699479fbfa39b99277Chris Lattner AU.addPreserved<DominanceFrontier>(); 460ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner AU.addPreserved<LoopInfo>(); 47ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter AU.addPreserved<ProfileInfo>(); 4898bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner 4998bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner // No loop canonicalization guarantees are broken by this pass. 5098bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addPreservedID(LoopSimplifyID); 516de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 526de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 536de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 54d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 55844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BreakCriticalEdges::ID = 0; 56844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<BreakCriticalEdges> 57844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("break-crit-edges", "Break critical edges in CFG"); 58844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 59eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Publically exposed interface to pass... 606ddba2b933645d308428201e942abe1274fa5085Dan Gohmanconst PassInfo *const llvm::BreakCriticalEdgesID = &X; 611e5fdf8ba0453baafe062525dc8472846da3ec1fChris LattnerFunctionPass *llvm::createBreakCriticalEdgesPass() { 621e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner return new BreakCriticalEdges(); 631e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner} 64d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 65363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 66363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// edges as they are found. 67363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// 68363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 69363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner bool Changed = false; 70363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 71363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner TerminatorInst *TI = I->getTerminator(); 721b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI)) 73363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 74363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (SplitCriticalEdge(TI, i, this)) { 75363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner ++NumBroken; 76363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner Changed = true; 77363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 78363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 79363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 80363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner return Changed; 81363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner} 82363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 83363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 84363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// Implementation of the external critical edge manipulation functions 85363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 86eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 87eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// isCriticalEdge - Return true if the specified edge is a critical edge. 88eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Critical edges are edges from a block with multiple successors to a block 89eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// with multiple predecessors. 90eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 91b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattnerbool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 92b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner bool AllowIdenticalEdges) { 93eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 94e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (TI->getNumSuccessors() == 1) return false; 95eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 96eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner const BasicBlock *Dest = TI->getSuccessor(SuccNum); 97eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 98eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 99eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there is more than one predecessor, this is a critical edge... 100eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(I != E && "No preds, but we have an edge to the block?"); 101b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner const BasicBlock *FirstPred = *I; 102eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++I; // Skip one edge due to the incoming arc from TI. 103b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner if (!AllowIdenticalEdges) 104b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner return I != E; 105b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner 106b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner // If AllowIdenticalEdges is true, then we allow this edge to be considered 107b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner // non-critical iff all preds come from TI's block. 1084bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel while (I != E) { 1094bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel if (*I != FirstPred) 1104bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel return true; 1114bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel // Note: leave this as is until no one ever compiles with either gcc 4.0.1 1124bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207 1134bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel E = pred_end(*I); 1144bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel ++I; 1154bf393a13e779d7a8eac3647df1781068a6dc732Scott Michel } 116b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner return false; 117eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 118eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 119c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// CreatePHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form 120c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// may require new PHIs in the new exit block. This function inserts the 121c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB 122c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// is the new loop exit block, and DestBB is the old loop exit, now the 123c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman/// successor of SplitBB. 124c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohmanstatic void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds, 125c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *SplitBB, 126c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *DestBB) { 127c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // SplitBB shouldn't have anything non-trivial in it yet. 128c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman assert(SplitBB->getFirstNonPHI() == SplitBB->getTerminator() && 129c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman "SplitBB has non-PHI nodes!"); 130c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 131c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // For each PHI in the destination block... 132c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman for (BasicBlock::iterator I = DestBB->begin(); 133c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) { 134c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman unsigned Idx = PN->getBasicBlockIndex(SplitBB); 135c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman Value *V = PN->getIncomingValue(Idx); 136c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // If the input is a PHI which already satisfies LCSSA, don't create 137c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // a new one. 138c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (const PHINode *VP = dyn_cast<PHINode>(V)) 139c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (VP->getParent() == SplitBB) 140c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman continue; 141c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Otherwise a new PHI is needed. Create one and populate it. 142c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PHINode *NewPN = PHINode::Create(PN->getType(), "split", 143c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman SplitBB->getTerminator()); 144c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman for (unsigned i = 0, e = Preds.size(); i != e; ++i) 145c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman NewPN->addIncoming(V, Preds[i]); 146c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Update the original PHI. 147c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman PN->setIncomingValue(Idx, NewPN); 148c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 149c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman} 150c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 151862f27ebab52aa93784462fbeaa93dacdc6a4c78Chris Lattner/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 152862f27ebab52aa93784462fbeaa93dacdc6a4c78Chris Lattner/// split the critical edge. This will update DominatorTree and 1531b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// DominatorFrontier information if it is available, thus calling this pass 1541b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// will not invalidate either of them. This returns the new block if the edge 1551b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// was split, null otherwise. 1561b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// 1571b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the 1581b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// specified successor will be merged into the same critical edge block. 1591b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// This is most commonly interesting with switch instructions, which may 1601b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// have many edges to any one destination. This ensures that all edges to that 1611b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// dest go to one block instead of each going to a different block, but isn't 1621b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// the standard definition of a "critical edge". 1631b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// 1641b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// It is invalid to call this function on a critical edge that starts at an 1651b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// IndirectBrInst. Splitting these edges will almost always create an invalid 166280f3fedbfc8d76014dbb25aecfd57a847fd6183Chris Lattner/// program because the address of the new block won't be the one that is jumped 1671b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// to. 1681b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner/// 1695c89b5240c90eb8171f999e5f06f815502d0321cDan GohmanBasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, 1705c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman Pass *P, bool MergeIdenticalEdges) { 1715c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0; 1721b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner 1731b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner assert(!isa<IndirectBrInst>(TI) && 1741b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner "Cannot split critical edge from IndirectBrInst"); 1751b98ff3e4fb81f83a9c8d04f6b063cbb2114af65Chris Lattner 176eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 1776918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 178eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 179eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 1801d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), 1811d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); 182eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create our unconditional branch... 183051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(DestBB, NewBB); 184fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Branch to the new block, breaking the edge. 186eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 187eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 188eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 189eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 190261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FBBI = TIBB; 191261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F.getBasicBlockList().insert(++FBBI, NewBB); 19227e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 193eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 194eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 195eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 1962da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 1972da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 19806887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // We no longer enter through TIBB, now we come in through NewBB. Revector 19906887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // exactly one entry in the PHI node that used to come from TIBB to come 20006887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // from NewBB. 201b01bfd49c3353085e9ebb01d7b257f70583ee8c8Chris Lattner int BBIdx = PN->getBasicBlockIndex(TIBB); 202b01bfd49c3353085e9ebb01d7b257f70583ee8c8Chris Lattner PN->setIncomingBlock(BBIdx, NewBB); 203eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 20427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 20527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // If there are any other edges from TIBB to DestBB, update those to go 20627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // through the split block, making those edges non-critical as well (and 20727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // reducing the number of phi entries in the DestBB if relevant). 20827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (MergeIdenticalEdges) { 20927e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 21027e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (TI->getSuccessor(i) != DestBB) continue; 21127e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 21227e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Remove an entry for TIBB from DestBB phi nodes. 21327e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner DestBB->removePredecessor(TIBB); 21427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 21527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // We found another edge to DestBB, go to NewBB instead. 21627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner TI->setSuccessor(i, NewBB); 21727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 21827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 21927e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 22027e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 221eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 222e802a023d98b06307831cd122e61da86431e8dacChris Lattner // If we don't have a pass object, we can't update anything... 2235c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (P == 0) return NewBB; 224e802a023d98b06307831cd122e61da86431e8dacChris Lattner 22586f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Now update analysis information. Since the only predecessor of NewBB is 22686f7b2100c7b6b426869178327e352d122056f73Chris Lattner // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate 22786f7b2100c7b6b426869178327e352d122056f73Chris Lattner // anything, as there are other successors of DestBB. However, if all other 22886f7b2100c7b6b426869178327e352d122056f73Chris Lattner // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a 22986f7b2100c7b6b426869178327e352d122056f73Chris Lattner // loop header) then NewBB dominates DestBB. 23086f7b2100c7b6b426869178327e352d122056f73Chris Lattner SmallVector<BasicBlock*, 8> OtherPreds; 231eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 23286f7b2100c7b6b426869178327e352d122056f73Chris Lattner for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; ++I) 23386f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (*I != NewBB) 23486f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.push_back(*I); 23586f7b2100c7b6b426869178327e352d122056f73Chris Lattner 23686f7b2100c7b6b426869178327e352d122056f73Chris Lattner bool NewBBDominatesDestBB = true; 23786f7b2100c7b6b426869178327e352d122056f73Chris Lattner 238c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 2391465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>()) { 24026042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *TINode = DT->getNode(TIBB); 241fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 242c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 243c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 244c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 24586f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (TINode) { // Don't break unreachable code! 24683beaee227dad622a7e378897c6f29b511388fa0Devang Patel DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); 24726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *DestBBNode = 0; 24886f7b2100c7b6b426869178327e352d122056f73Chris Lattner 24986f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. 25086f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!OtherPreds.empty()) { 25186f7b2100c7b6b426869178327e352d122056f73Chris Lattner DestBBNode = DT->getNode(DestBB); 25286f7b2100c7b6b426869178327e352d122056f73Chris Lattner while (!OtherPreds.empty() && NewBBDominatesDestBB) { 25326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) 2549a51157db555395f7a6ad89faec40b3afa121091Devang Patel NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); 25586f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.pop_back(); 25686f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 25786f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.clear(); 25886f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 25986f7b2100c7b6b426869178327e352d122056f73Chris Lattner 26086f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 26186f7b2100c7b6b426869178327e352d122056f73Chris Lattner // doesn't dominate anything. 26286f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (NewBBDominatesDestBB) { 26386f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!DestBBNode) DestBBNode = DT->getNode(DestBB); 26486f7b2100c7b6b426869178327e352d122056f73Chris Lattner DT->changeImmediateDominator(DestBBNode, NewBBNode); 26586f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 26686f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 267eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 2686918c079a1393be8ae551d699479fbfa39b99277Chris Lattner 2696918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Should we update DominanceFrontier information? 2701465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominanceFrontier *DF = P->getAnalysisIfAvailable<DominanceFrontier>()) { 27186f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with DF. 27286f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!OtherPreds.empty()) { 27386f7b2100c7b6b426869178327e352d122056f73Chris Lattner // FIXME: IMPLEMENT THIS! 274c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Requiring domfrontiers but not idom/domtree/domset." 275c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin " not implemented yet!"); 27686f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 27786f7b2100c7b6b426869178327e352d122056f73Chris Lattner 2786918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Since the new block is dominated by its only predecessor TIBB, 27986f7b2100c7b6b426869178327e352d122056f73Chris Lattner // it cannot be in any block's dominance frontier. If NewBB dominates 28086f7b2100c7b6b426869178327e352d122056f73Chris Lattner // DestBB, its dominance frontier is the same as DestBB's, otherwise it is 28186f7b2100c7b6b426869178327e352d122056f73Chris Lattner // just {DestBB}. 2826918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DominanceFrontier::DomSetType NewDFSet; 28386f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (NewBBDominatesDestBB) { 28486f7b2100c7b6b426869178327e352d122056f73Chris Lattner DominanceFrontier::iterator I = DF->find(DestBB); 2856acc9e6b7bc5cc5b45a69988b2805674da62a820Devang Patel if (I != DF->end()) { 28686f7b2100c7b6b426869178327e352d122056f73Chris Lattner DF->addBasicBlock(NewBB, I->second); 287269db29bdbd5d3264a859e7d3763a4c501fb9ee4Owen Anderson 288269db29bdbd5d3264a859e7d3763a4c501fb9ee4Owen Anderson if (I->second.count(DestBB)) { 289269db29bdbd5d3264a859e7d3763a4c501fb9ee4Owen Anderson // However NewBB's frontier does not include DestBB. 290269db29bdbd5d3264a859e7d3763a4c501fb9ee4Owen Anderson DominanceFrontier::iterator NF = DF->find(NewBB); 291269db29bdbd5d3264a859e7d3763a4c501fb9ee4Owen Anderson DF->removeFromFrontier(NF, DestBB); 292269db29bdbd5d3264a859e7d3763a4c501fb9ee4Owen Anderson } 2936acc9e6b7bc5cc5b45a69988b2805674da62a820Devang Patel } 29486f7b2100c7b6b426869178327e352d122056f73Chris Lattner else 29586f7b2100c7b6b426869178327e352d122056f73Chris Lattner DF->addBasicBlock(NewBB, DominanceFrontier::DomSetType()); 29686f7b2100c7b6b426869178327e352d122056f73Chris Lattner } else { 29786f7b2100c7b6b426869178327e352d122056f73Chris Lattner DominanceFrontier::DomSetType NewDFSet; 29886f7b2100c7b6b426869178327e352d122056f73Chris Lattner NewDFSet.insert(DestBB); 29986f7b2100c7b6b426869178327e352d122056f73Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 30086f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 3016918c079a1393be8ae551d699479fbfa39b99277Chris Lattner } 3020ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner 3030ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Update LoopInfo if it is around. 3041465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) { 3055c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (Loop *TIL = LI->getLoopFor(TIBB)) { 3065c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If one or the other blocks were not in a loop, the new block is not 3075c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // either, and thus LI doesn't need to be updated. 3080ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 3090ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (TIL == DestLoop) { 3100ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Both in the same loop, the NewBB joins loop. 311d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 31292329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (TIL->contains(DestLoop)) { 31386f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an outer loop to an inner loop. Add to the outer loop. 314d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson TIL->addBasicBlockToLoop(NewBB, LI->getBase()); 31592329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (DestLoop->contains(TIL)) { 31686f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an inner loop to an outer loop. Add to the outer loop. 317d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 3180ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else { 3190ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from two loops with no containment relation. Because these 3200ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // are natural loops, we know that the destination block must be the 3210ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // header of its loop (adding a branch into a loop elsewhere would 3220ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // create an irreducible loop). 3230ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner assert(DestLoop->getHeader() == DestBB && 3240ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner "Should not create irreducible loops!"); 3250ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *P = DestLoop->getParentLoop()) 326d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson P->addBasicBlockToLoop(NewBB, LI->getBase()); 3270ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3280ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3295c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If TIBB is in a loop and DestBB is outside of that loop, split the 3305c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // other exit blocks of the loop that also have predecessors outside 3315c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // the loop, to maintain a LoopSimplify guarantee. 3325c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (!TIL->contains(DestBB) && 3335c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman P->mustPreserveAnalysisID(LoopSimplifyID)) { 334c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman assert(!TIL->contains(NewBB) && 335c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman "Split point for loop exit is contained in loop!"); 336c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 337c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman // Update LCSSA form in the newly created exit block. 338c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (P->mustPreserveAnalysisID(LCSSAID)) { 339c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman SmallVector<BasicBlock *, 1> OrigPred; 340c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman OrigPred.push_back(TIBB); 341c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman CreatePHIsForSplitLoopExit(OrigPred, NewBB, DestBB); 342c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 343c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman 3445c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // For each unique exit block... 3455c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman SmallVector<BasicBlock *, 4> ExitBlocks; 3465c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman TIL->getExitBlocks(ExitBlocks); 3475c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 3485c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Collect all the preds that are inside the loop, and note 3495c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // whether there are any preds outside the loop. 3505c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman SmallVector<BasicBlock *, 4> Preds; 351c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman bool HasPredOutsideOfLoop = false; 3525c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman BasicBlock *Exit = ExitBlocks[i]; 3535c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); 3545c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman I != E; ++I) 3555c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman if (TIL->contains(*I)) 3565c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman Preds.push_back(*I); 3575c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman else 358c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman HasPredOutsideOfLoop = true; 3595c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // If there are any preds not in the loop, we'll need to split 3605c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // the edges. The Preds.empty() check is needed because a block 3615c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // may appear multiple times in the list. We can't use 3625c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // getUniqueExitBlocks above because that depends on LoopSimplify 3635c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // form, which we're in the process of restoring! 364c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (!Preds.empty() && HasPredOutsideOfLoop) { 365c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman BasicBlock *NewExitBB = 366c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman SplitBlockPredecessors(Exit, Preds.data(), Preds.size(), 367c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman "split", P); 368c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman if (P->mustPreserveAnalysisID(LCSSAID)) 369c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman CreatePHIsForSplitLoopExit(Preds, NewExitBB, Exit); 370c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman } 3715c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3725c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3735c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // LCSSA form was updated above for the case where LoopSimplify is 3745c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // available, which means that all predecessors of loop exit blocks 3755c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // are within the loop. Without LoopSimplify form, it would be 3765c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // necessary to insert a new phi. 3775c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman assert((!P->mustPreserveAnalysisID(LCSSAID) || 3785c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman P->mustPreserveAnalysisID(LoopSimplifyID)) && 3795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman "SplitCriticalEdge doesn't know how to update LCCSA form " 3805c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman "without LoopSimplify!"); 3815c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 3820ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3835c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 384ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter // Update ProfileInfo if it is around. 385ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter if (ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>()) { 386ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter PI->splitEdge(TIBB,DestBB,NewBB,MergeIdenticalEdges); 387ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter } 388ff5dfdff56dc2355a6c4740623dddd5fab40d885Andreas Neustifter 3895c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman return NewBB; 390eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 391