BreakCriticalEdges.cpp revision 9525528a7dc5462b6374d38c81ba5c07b11741fe
1d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source 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 19d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 20d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 21d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Analysis/Dominators.h" 220ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner#include "llvm/Analysis/LoopInfo.h" 23d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Function.h" 2447b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 255b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 26eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/Support/CFG.h" 279525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Visibility.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 29f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 316de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattnernamespace { 32a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); 336de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 349525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { 356de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual bool runOnFunction(Function &F); 36fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 376de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 38dd9e9566052d02c9fa053756bb0136eb25e9018bChris Lattner AU.addPreserved<ETForest>(); 396de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<DominatorSet>(); 406de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<ImmediateDominators>(); 416de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<DominatorTree>(); 426918c079a1393be8ae551d699479fbfa39b99277Chris Lattner AU.addPreserved<DominanceFrontier>(); 430ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner AU.addPreserved<LoopInfo>(); 4498bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner 4598bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner // No loop canonicalization guarantees are broken by this pass. 4698bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addPreservedID(LoopSimplifyID); 476de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 486de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 496de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 506de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner RegisterOpt<BreakCriticalEdges> X("break-crit-edges", 516de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner "Break critical edges in CFG"); 526de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 53d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 54eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Publically exposed interface to pass... 55f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerconst PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); 561e5fdf8ba0453baafe062525dc8472846da3ec1fChris LattnerFunctionPass *llvm::createBreakCriticalEdgesPass() { 571e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner return new BreakCriticalEdges(); 581e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner} 59d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 60363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 61363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// edges as they are found. 62363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// 63363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 64363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner bool Changed = false; 65363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 66363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner TerminatorInst *TI = I->getTerminator(); 67363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (TI->getNumSuccessors() > 1) 68363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 69363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (SplitCriticalEdge(TI, i, this)) { 70363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner ++NumBroken; 71363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner Changed = true; 72363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 73363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 74363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 75363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner return Changed; 76363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner} 77363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 78363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 79363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// Implementation of the external critical edge manipulation functions 80363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 81eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 82eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// isCriticalEdge - Return true if the specified edge is a critical edge. 83eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Critical edges are edges from a block with multiple successors to a block 84eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// with multiple predecessors. 85eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 86f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { 87eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 88e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (TI->getNumSuccessors() == 1) return false; 89eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 90eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner const BasicBlock *Dest = TI->getSuccessor(SuccNum); 91eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 92eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 93eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there is more than one predecessor, this is a critical edge... 94eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(I != E && "No preds, but we have an edge to the block?"); 95eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++I; // Skip one edge due to the incoming arc from TI. 96eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner return I != E; 97eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 98eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 99d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 100d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// split the critical edge. This will update DominatorSet, ImmediateDominator, 101d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// DominatorTree, and DominatorFrontier information if it is available, thus 102d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// calling this pass will not invalidate either of them. This returns true if 103d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// the edge was split, false otherwise. 104eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 105f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 106d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner if (!isCriticalEdge(TI, SuccNum)) return false; 107eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 1086918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 109eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 110eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 1116918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + 1126918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DestBB->getName() + "_crit_edge"); 113eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create our unconditional branch... 114108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(DestBB, NewBB); 115fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 116eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Branch to the new block, breaking the edge... 117eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 118eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 119eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 120eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 121eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner F.getBasicBlockList().insert(TIBB->getNext(), NewBB); 122eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 123eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 124eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 125eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 1262da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 1272da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 12806887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // We no longer enter through TIBB, now we come in through NewBB. Revector 12906887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // exactly one entry in the PHI node that used to come from TIBB to come 13006887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // from NewBB. 131b01bfd49c3353085e9ebb01d7b257f70583ee8c8Chris Lattner int BBIdx = PN->getBasicBlockIndex(TIBB); 132b01bfd49c3353085e9ebb01d7b257f70583ee8c8Chris Lattner PN->setIncomingBlock(BBIdx, NewBB); 133eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 134eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 135e802a023d98b06307831cd122e61da86431e8dacChris Lattner // If we don't have a pass object, we can't update anything... 136d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner if (P == 0) return true; 137e802a023d98b06307831cd122e61da86431e8dacChris Lattner 138c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Now update analysis information. These are the analyses that we are 139c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // currently capable of updating... 140eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 141eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 142c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorSet information? 143e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) { 144c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The blocks that dominate the new one are the blocks that dominate TIBB 145c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // plus the new block itself. 146c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); 147c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DomSet.insert(NewBB); // A block always dominates itself. 148c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DS->addBasicBlock(NewBB, DomSet); 149c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 150eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 151cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Should we update ImmediateDominator information? 152e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) { 153c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate 154c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // anything. 155c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner ID->addNewBlock(NewBB, TIBB); 156c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 157fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 158dd9e9566052d02c9fa053756bb0136eb25e9018bChris Lattner // Update the forest? 159dd9e9566052d02c9fa053756bb0136eb25e9018bChris Lattner if (ETForest *EF = P->getAnalysisToUpdate<ETForest>()) 160dd9e9566052d02c9fa053756bb0136eb25e9018bChris Lattner EF->addNewBlock(NewBB, TIBB); 161dd9e9566052d02c9fa053756bb0136eb25e9018bChris Lattner 162c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 163e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { 164c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorTree::Node *TINode = DT->getNode(TIBB); 165fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 166c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 167c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 168c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 169d3d06a5cd80a718a640e26350954197fb133800aChris Lattner if (TINode) // Don't break unreachable code! 170d3d06a5cd80a718a640e26350954197fb133800aChris Lattner DT->createNewNode(NewBB, TINode); 171eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 1726918c079a1393be8ae551d699479fbfa39b99277Chris Lattner 1736918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Should we update DominanceFrontier information? 1746918c079a1393be8ae551d699479fbfa39b99277Chris Lattner if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { 1756918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Since the new block is dominated by its only predecessor TIBB, 1766918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // it cannot be in any block's dominance frontier. Its dominance 1776918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // frontier is {DestBB}. 1786918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DominanceFrontier::DomSetType NewDFSet; 1796918c079a1393be8ae551d699479fbfa39b99277Chris Lattner NewDFSet.insert(DestBB); 1806918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 1816918c079a1393be8ae551d699479fbfa39b99277Chris Lattner } 1820ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner 1830ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Update LoopInfo if it is around. 1840ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) { 1850ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // If one or the other blocks were not in a loop, the new block is not 1860ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // either, and thus LI doesn't need to be updated. 1870ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *TIL = LI->getLoopFor(TIBB)) 1880ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 1890ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (TIL == DestLoop) { 1900ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Both in the same loop, the NewBB joins loop. 1910ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner DestLoop->addBasicBlockToLoop(NewBB, *LI); 1920ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else if (TIL->contains(DestLoop->getHeader())) { 1930ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from an outer loop to an inner loop. Add to the outer lopo. 1940ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner TIL->addBasicBlockToLoop(NewBB, *LI); 1950ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else if (DestLoop->contains(TIL->getHeader())) { 1960ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from an inner loop to an outer loop. Add to the outer lopo. 1970ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner DestLoop->addBasicBlockToLoop(NewBB, *LI); 1980ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else { 1990ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from two loops with no containment relation. Because these 2000ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // are natural loops, we know that the destination block must be the 2010ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // header of its loop (adding a branch into a loop elsewhere would 2020ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // create an irreducible loop). 2030ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner assert(DestLoop->getHeader() == DestBB && 2040ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner "Should not create irreducible loops!"); 2050ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *P = DestLoop->getParentLoop()) 2060ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner P->addBasicBlockToLoop(NewBB, *LI); 2070ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 2080ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 2090ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner 2100ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 211d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner return true; 212eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 213