LoopSimplify.cpp revision 5cd8770412f98f6e6416c439e01222b3643b9e22
167a9801bc510ff2c28068361fb30ae397fd1e026Chris Lattner//===- LoopSimplify.cpp - Loop Canonicalization 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//===----------------------------------------------------------------------===// 938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 10ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass performs several transformations to transform natural loops into a 11ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// simpler form, which makes subsequent analyses and transformations simpler and 12ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// more effective. 13dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 14dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop pre-header insertion guarantees that there is a single, non-critical 15dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// entry edge from outside of the loop to the loop header. This simplifies a 16dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// number of analyses and transformations, such as LICM. 17dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 18dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop exit-block insertion guarantees that all exit blocks from the loop 19dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// (blocks which are outside of the loop that have predecessors inside of the 2066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// loop) only have predecessors from inside of the loop (and are thus dominated 2166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// by the loop header). This simplifies transformations such as store-sinking 2266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// that are built into LICM. 23dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// This pass also guarantees that loops will have exactly one backedge. 252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// 26f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// Indirectbr instructions introduce several complications. If the loop 27f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// contains or is entered by an indirectbr instruction, it may not be possible 28f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// to transform the loop and make these guarantees. Client code should check 29f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// that these conditions are true before relying on them. 30f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// 31dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Note that the simplifycfg pass will clean up blocks which are split out but 32ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// end up being unnecessary, so usage of this pass should not pessimize 33ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// generated code. 34ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// 35ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass obviously modifies the CFG, but updates loop information and 36ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// dominator information. 3738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 3838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//===----------------------------------------------------------------------===// 3938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 40d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "loopsimplify" 4138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h" 423cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner#include "llvm/Constants.h" 4347b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 442ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Function.h" 450a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h" 462ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Type.h" 47cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 480f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner#include "llvm/Analysis/Dominators.h" 49d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman#include "llvm/Analysis/LoopPass.h" 50d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman#include "llvm/Analysis/ScalarEvolution.h" 5154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 524b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman#include "llvm/Transforms/Utils/Local.h" 5338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 54551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 55551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetVector.h" 56551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 57551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 5866ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerusing namespace llvm; 59d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 60d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 61d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumNested , "Number of nested loops split out"); 6238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 63d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 646726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct LoopSimplify : public LoopPass { 65ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 66d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman LoopSimplify() : LoopPass(&ID) {} 67794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 68cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // AA - If we have an alias analysis object to update, this is it, otherwise 69cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // this is null. 70cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner AliasAnalysis *AA; 71c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LoopInfo *LI; 720e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominatorTree *DT; 73d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Loop *L; 74d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 75fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 7638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 7738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 785c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman AU.addRequiredTransitive<LoopInfo>(); 795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman AU.addRequiredTransitive<DominatorTree>(); 8038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 8138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<LoopInfo>(); 8238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 83dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addPreserved<DominanceFrontier>(); 844c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel AU.addPreserved<AliasAnalysis>(); 85d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman AU.addPreserved<ScalarEvolution>(); 8694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 8738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 8858e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 89f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 90f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman void verifyAnalysis() const; 9158e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 9238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 93d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman bool ProcessLoop(Loop *L, LPPassManager &LPM); 9459fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 950df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman BasicBlock *InsertPreheaderForLoop(Loop *L); 96d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); 97f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 98120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner void PlaceSplitBlockCarefully(BasicBlock *NewBB, 9954b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVectorImpl<BasicBlock*> &SplitPreds, 100120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L); 10138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 10238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 10338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 104844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopSimplify::ID = 0; 105844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LoopSimplify> 106844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("loopsimplify", "Canonicalize natural loops", true); 107844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass... 1096ddba2b933645d308428201e942abe1274fa5085Dan Gohmanconst PassInfo *const llvm::LoopSimplifyID = &X; 110d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 11138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 11234d2b90d09226ebf6189775acfd2801e127b10ecDan Gohman/// runOnLoop - Run down all loops in the CFG (recursively, but we could do 11338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 11438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 115d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 116d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman L = l; 11738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 118c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI = &getAnalysis<LoopInfo>(); 1191465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands AA = getAnalysisIfAvailable<AliasAnalysis>(); 1200e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT = &getAnalysis<DominatorTree>(); 12138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 122d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed |= ProcessLoop(L, LPM); 12338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 12438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 12538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 12638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 12738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 12838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 12938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 130d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 13138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 1323bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop: 133d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 134d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Check to see that no blocks (other than the header) in this loop that has 135d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // predecessors that are not in the loop. This is not valid for natural 136d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // loops, but can occur if the blocks are unreachable. Since they are 137d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // unreachable we can just shamelessly delete those CFG edges! 138d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 139d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman BB != E; ++BB) { 140d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (*BB == L->getHeader()) continue; 141d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 142d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman SmallPtrSet<BasicBlock *, 4> BadPreds; 143d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (pred_iterator PI = pred_begin(*BB), PE = pred_end(*BB); PI != PE; ++PI) 144d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (!L->contains(*PI)) 145d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman BadPreds.insert(*PI); 146d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 147d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Delete each unique out-of-loop (and thus dead) predecessor. 148d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (SmallPtrSet<BasicBlock *, 4>::iterator I = BadPreds.begin(), 149d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman E = BadPreds.end(); I != E; ++I) { 150d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Inform each successor of each dead pred. 151d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 152d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*SI)->removePredecessor(*I); 153d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Zap the dead pred's terminator and replace it with unreachable. 154d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TerminatorInst *TI = (*I)->getTerminator(); 155d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 156d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*I)->getTerminator()->eraseFromParent(); 157d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman new UnreachableInst((*I)->getContext(), *I); 158d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed = true; 159d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 160d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 1612ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 162fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Does the loop already have a preheader? If so, don't insert one. 1630df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 1640df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman if (!Preheader) { 1650df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman Preheader = InsertPreheaderForLoop(L); 166f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (Preheader) { 167f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman NumInserted++; 168f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 169f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 17038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 17138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 17266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 17366ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 17466ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 175ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner // predecessors from outside of the loop, split the edge now. 176b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 177ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner L->getExitBlocks(ExitBlocks); 178c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner 179ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 180fed22aac4337c589841c443be70fe05559693f6aChris Lattner for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 181fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 182fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 183de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 184de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 1858587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // Must be exactly this loop: no subloops, parent loops, or non-loop preds 1868587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // allowed. 187ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner if (!L->contains(*PI)) { 188f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (RewriteLoopExitBlock(L, ExitBlock)) { 189f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman NumInserted++; 190f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 191f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 192de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 193de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 194fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 195dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 196529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 197529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 198f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *LoopLatch = L->getLoopLatch(); 199f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!LoopLatch) { 2003bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If this is really a nested loop, rip it out into a child loop. Don't do 2013bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // this for loops with a giant number of backedges, just factor them into a 2023bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // common backedge instead. 203f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (L->getNumBackEdges() < 8) { 204d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (SeparateNestedLoop(L, LPM)) { 2053bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ++NumNested; 2063bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // This is a big restructuring change, reprocess the whole loop. 2073bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner Changed = true; 2083bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // GCC doesn't tail recursion eliminate this. 2093bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner goto ReprocessLoop; 2103bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner } 211529b28da455a703d226a31a03400e6662ff569feChris Lattner } 212529b28da455a703d226a31a03400e6662ff569feChris Lattner 2133bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If we either couldn't, or didn't want to, identify nesting of the loops, 2143bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // insert a new block that all backedges target, then make it jump to the 2153bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // loop header. 216f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 217f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (LoopLatch) { 218f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman NumInserted++; 219f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 220f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 2212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 2222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 22394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // Scan over the PHI nodes in the loop header. Since they now have only two 22494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // incoming values (the loop is canonicalized), we may have simplified the PHI 22594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 22694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PHINode *PN; 22794f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner for (BasicBlock::iterator I = L->getHeader()->begin(); 22894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner (PN = dyn_cast<PHINode>(I++)); ) 229bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman if (Value *V = PN->hasConstantValue(DT)) { 2304c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel if (AA) AA->deleteValue(PN); 2314c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel PN->replaceAllUsesWith(V); 2324c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel PN->eraseFromParent(); 2334c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel } 23494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner 2355cd8770412f98f6e6416c439e01222b3643b9e22Bob Wilson // If this loop has multiple exits and the exits all go to the same 2364b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // block, attempt to merge the exits. This helps several passes, such 2374b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // as LoopRotation, which do not support loops with multiple exits. 2384b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // SimplifyCFG also does this (and this code uses the same utility 2394b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // function), however this code is loop-aware, where SimplifyCFG is 2404b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // not. That gives it the advantage of being able to hoist 2414b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // loop-invariant instructions out of the way to open up more 2424b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // opportunities, and the disadvantage of having the responsibility 2434b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to preserve dominator information. 244b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman bool UniqueExit = true; 245b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (!ExitBlocks.empty()) 246b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 247b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (ExitBlocks[i] != ExitBlocks[0]) { 248b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman UniqueExit = false; 249b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman break; 250b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman } 251b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (UniqueExit) { 2524b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 2534b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman L->getExitingBlocks(ExitingBlocks); 2544b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 2554b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BasicBlock *ExitingBlock = ExitingBlocks[i]; 2564b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!ExitingBlock->getSinglePredecessor()) continue; 2574b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2584b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!BI || !BI->isConditional()) continue; 2594b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 2604b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!CI || CI->getParent() != ExitingBlock) continue; 2614b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 2624b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Attempt to hoist out all instructions except for the 2634b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // comparison and the branch. 2644b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman bool AllInvariant = true; 2652aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 2664b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Instruction *Inst = I++; 2672aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman if (Inst == CI) 2684b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman continue; 269f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->makeLoopInvariant(Inst, Changed, 270f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Preheader ? Preheader->getTerminator() : 0)) { 2714b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman AllInvariant = false; 2724b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman break; 2734b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 2744b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 2754b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!AllInvariant) continue; 2764b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 2774b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // The block has now been cleared of all instructions except for 2784b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // a comparison and a conditional branch. SimplifyCFG may be able 2794b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to fold it now. 2804b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!FoldBranchToCommonDest(BI)) continue; 2814b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 2824b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Success. The block is now dead, so remove it from the loop, 2834b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // update the dominator tree and dominance frontier, and delete it. 2844b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 2854b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Changed = true; 286a1baee20c4b042eca1f182fc003f38ab52efc7a9Dan Gohman LI->removeBlock(ExitingBlock); 2874b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 2884b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>(); 2894b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DomTreeNode *Node = DT->getNode(ExitingBlock); 2904b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 2914b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Node->getChildren(); 2925184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman while (!Children.empty()) { 2935184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DomTreeNode *Child = Children.front(); 2945184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DT->changeImmediateDominator(Child, Node->getIDom()); 2955184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman if (DF) DF->changeImmediateDominator(Child->getBlock(), 2964b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Node->getIDom()->getBlock(), 2974b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DT); 2984b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 2994b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DT->eraseNode(ExitingBlock); 3004b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (DF) DF->removeBlock(ExitingBlock); 3014b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3024b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(0)->removePredecessor(ExitingBlock); 3034b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(1)->removePredecessor(ExitingBlock); 3044b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman ExitingBlock->eraseFromParent(); 3054b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3064b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3074b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 30838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 30938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 31038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 311dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 312dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 313dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 314dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 3150df6e09d43d6d733555a10d22572ddb0006e7d23Dan GohmanBasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { 316dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 317dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 318dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 31954b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OutsideBlocks; 320dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 321dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PI != PE; ++PI) 322f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->contains(*PI)) { // Coming in from outside the loop? 323f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // If the loop is branched to from an indirect branch, we won't 324f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // be able to fully transform the loop, because it prohibits 325f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // edge splitting. 326f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((*PI)->getTerminator())) return 0; 327f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 328f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Keep track of it. 329f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman OutsideBlocks.push_back(*PI); 330f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 331fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 332c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner // Split out the loop pre-header. 333dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 33454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 33554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner ".preheader", this); 3369f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 337120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 338120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 339120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 3400df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman 3410df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman return NewBB; 342dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 343dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 344529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 345529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks. This method is used to split exit blocks that have predecessors 346529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop. 34759fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 34854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> LoopBlocks; 349dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 350f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (L->contains(*I)) { 351f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Don't do this if the loop is exited via an indirect branch. 352f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((*I)->getTerminator())) return 0; 353f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 354dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner LoopBlocks.push_back(*I); 355f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 356dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 3577e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 35854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 35954b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner LoopBlocks.size(), ".loopexit", 36054b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner this); 3617e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 36259fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner return NewBB; 3632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 3642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 365529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 366529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 367529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 36858d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 369529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 37058d7fbf250659246fcca9417a91170a681b1850aDevang Patel std::vector<BasicBlock *> WorkList; 37158d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(InputBB); 37258d7fbf250659246fcca9417a91170a681b1850aDevang Patel do { 37358d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 37458d7fbf250659246fcca9417a91170a681b1850aDevang Patel if (Blocks.insert(BB).second && BB != StopBlock) 37558d7fbf250659246fcca9417a91170a681b1850aDevang Patel // If BB is not already processed and it is not a stop block then 37658d7fbf250659246fcca9417a91170a681b1850aDevang Patel // insert its predecessor in the work list 37758d7fbf250659246fcca9417a91170a681b1850aDevang Patel for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 37858d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *WBB = *I; 37958d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(WBB); 38058d7fbf250659246fcca9417a91170a681b1850aDevang Patel } 38158d7fbf250659246fcca9417a91170a681b1850aDevang Patel } while(!WorkList.empty()); 382529b28da455a703d226a31a03400e6662ff569feChris Lattner} 383529b28da455a703d226a31a03400e6662ff569feChris Lattner 3841f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 3851f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops. 386dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 387ad190145912facc6fbf2fbe58023bb238fbf2365Owen Anderson AliasAnalysis *AA) { 388200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 389200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 3901f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 391bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman if (Value *V = PN->hasConstantValue(DT)) { 392bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman // This is a degenerate PHI already, don't modify it! 393bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman PN->replaceAllUsesWith(V); 394bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman if (AA) AA->deleteValue(PN); 395bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman PN->eraseFromParent(); 396bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman continue; 397bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman } 398c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 399c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 400c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 401c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 402c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 403c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 404c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4051f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4061f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4071f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4081f62f82b05563df9c83094608de24ea581014d1eChris Lattner 409120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 410120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block. This prevents the preheader from 411120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated. 412120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattnervoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 41354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVectorImpl<BasicBlock*> &SplitPreds, 414120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L) { 415120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Check to see if NewBB is already well placed. 416120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = NewBB; --BBI; 417120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 418120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (&*BBI == SplitPreds[i]) 419120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner return; 420120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 421120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 422120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If it isn't already after an outside block, move it after one. This is 423120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // always good as it makes the uncond branch from the outside block into a 424120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // fall-through. 425120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 426120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Figure out *which* outside block to put this after. Prefer an outside 427120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // block that neighbors a BB actually in the loop. 428120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner BasicBlock *FoundBB = 0; 429120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 430120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = SplitPreds[i]; 431120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (++BBI != NewBB->getParent()->end() && 432120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner L->contains(BBI)) { 433120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[i]; 434120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner break; 435120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 436120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 437120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 438120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If our heuristic for a *good* bb to place this after doesn't find 439120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // anything, just pick something. It's likely better than leaving it within 440120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // the loop. 441120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (!FoundBB) 442120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[0]; 443120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner NewBB->moveAfter(FoundBB); 444120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner} 445120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 446120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 447529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 448529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 449529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 450529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 451529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 452529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 453529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 454529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 455529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 456529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 457529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 458529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 459529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 460529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 461529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 462529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 463529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 464d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanLoop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { 465dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); 4661f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 467529b28da455a703d226a31a03400e6662ff569feChris Lattner 4681f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 4691f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 4701f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 47154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OuterLoopPreds; 4721f62f82b05563df9c83094608de24ea581014d1eChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 4731f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 474a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman !L->contains(PN->getIncomingBlock(i))) { 475a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman // We can't split indirectbr edges. 476a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator())) 477a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman return 0; 478a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman 4791f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 480a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman } 481529b28da455a703d226a31a03400e6662ff569feChris Lattner 4824b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 48354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 48454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner OuterLoopPreds.size(), 48554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner ".outer", this); 486529b28da455a703d226a31a03400e6662ff569feChris Lattner 487120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 488120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 489120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 490120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 491529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 492529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 493529b28da455a703d226a31a03400e6662ff569feChris Lattner 494529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 495529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 496529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 497529b28da455a703d226a31a03400e6662ff569feChris Lattner else 498c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeTopLevelLoop(L, NewOuter); 499529b28da455a703d226a31a03400e6662ff569feChris Lattner 500529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 501529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 502529b28da455a703d226a31a03400e6662ff569feChris Lattner 503d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Add the new loop to the pass manager queue. 504d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman LPM.insertLoopIntoQueue(NewOuter); 505d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 5069b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 5079b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) 5089b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman NewOuter->addBlockEntry(*I); 509529b28da455a703d226a31a03400e6662ff569feChris Lattner 5105c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Now reset the header in L, which had been moved by 5115c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // SplitBlockPredecessors for the outer loop. 5125c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman L->moveToHeader(Header); 5135c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 514529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 515529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 516529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 517529b28da455a703d226a31a03400e6662ff569feChris Lattner for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 518dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel if (DT->dominates(Header, *PI)) 519529b28da455a703d226a31a03400e6662ff569feChris Lattner AddBlockAndPredsToSet(*PI, Header, BlocksInL); 520529b28da455a703d226a31a03400e6662ff569feChris Lattner 521529b28da455a703d226a31a03400e6662ff569feChris Lattner 522529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 523529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 524c08fa28897356be54fba724056c3aa91da8b3e39David Greene const std::vector<Loop*> &SubLoops = L->getSubLoops(); 525c08fa28897356be54fba724056c3aa91da8b3e39David Greene for (size_t I = 0; I != SubLoops.size(); ) 526c08fa28897356be54fba724056c3aa91da8b3e39David Greene if (BlocksInL.count(SubLoops[I]->getHeader())) 527529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 528529b28da455a703d226a31a03400e6662ff569feChris Lattner else 529c08fa28897356be54fba724056c3aa91da8b3e39David Greene NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 530529b28da455a703d226a31a03400e6662ff569feChris Lattner 531529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 532529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 533529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 534529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 535529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 536529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 537529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 538c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if ((*LI)[BB] == L) 539c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeLoopFor(BB, NewOuter); 540529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 541529b28da455a703d226a31a03400e6662ff569feChris Lattner } 542529b28da455a703d226a31a03400e6662ff569feChris Lattner } 543529b28da455a703d226a31a03400e6662ff569feChris Lattner 544529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 545529b28da455a703d226a31a03400e6662ff569feChris Lattner} 546529b28da455a703d226a31a03400e6662ff569feChris Lattner 547529b28da455a703d226a31a03400e6662ff569feChris Lattner 548529b28da455a703d226a31a03400e6662ff569feChris Lattner 5492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 5502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 5512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 5522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 5532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 554f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanBasicBlock * 555f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanLoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 5562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 5572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 5592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 5602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 5612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 562f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Unique backedge insertion currently depends on having a preheader. 563f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!Preheader) 564f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return 0; 565f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 5662ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 5672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 5682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 5692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (*I != Preheader) BackedgeBlocks.push_back(*I); 5702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 5721d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 5731d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Header->getName()+".backedge", F); 574051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 5752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 5772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 5782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 579fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 5802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 5812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 582200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 583200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 584051a950000e21935165db56695e35bade668193bGabor Greif PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be", 585051a950000e21935165db56695e35bade668193bGabor Greif BETerminator); 5865551706b0f8e970720deea0bf6aa34116030d6beChris Lattner NewPN->reserveOperandSpace(BackedgeBlocks.size()); 587cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPN); 5882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 5902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 5912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 5922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 5932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 5942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 5952ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 5962ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 5972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 5982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 5992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 6002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 6012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 6032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 6042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 6052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 6062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 609fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 6112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 6122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 6132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 6142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 6152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6165551706b0f8e970720deea0bf6aa34116030d6beChris Lattner // Nuke all entries except the zero'th. 6175551706b0f8e970720deea0bf6aa34116030d6beChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 6185551706b0f8e970720deea0bf6aa34116030d6beChris Lattner PN->removeIncomingValue(e-i, false); 6192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 6212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 6222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 6242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 6252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 6262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 628cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(NewPN); 6292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 6302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 634280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky // backedge blocks to just to the BEBlock instead of the header. 6352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 6362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 6372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 6382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 6392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 6402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 6432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 6452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 646d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson L->addBasicBlockToLoop(BEBlock, LI->getBase()); 6472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6480e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update dominator information 6490e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(BEBlock); 6501465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) 6510e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DF->splitBlock(BEBlock); 652f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 653f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return BEBlock; 654f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman} 655f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 656f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohmanvoid LoopSimplify::verifyAnalysis() const { 657f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // It used to be possible to just assert L->isLoopSimplifyForm(), however 658f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // with the introduction of indirectbr, there are now cases where it's 659f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // not possible to transform a loop as necessary. We can at least check 660f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // that there is an indirectbr near any time there's trouble. 661f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 662f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Indirectbr can interfere with preheader and unique backedge insertion. 663f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->getLoopPreheader() || !L->getLoopLatch()) { 664f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrPred = false; 665f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman for (pred_iterator PI = pred_begin(L->getHeader()), 666f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman PE = pred_end(L->getHeader()); PI != PE; ++PI) 667f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((*PI)->getTerminator())) { 668f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrPred = true; 669f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 670f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 671f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman assert(HasIndBrPred && 672f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing loop header info!"); 673f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 674f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 675f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Indirectbr can interfere with exit block canonicalization. 676f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->hasDedicatedExits()) { 677f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrExiting = false; 678f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 679f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman L->getExitingBlocks(ExitingBlocks); 680f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) 681f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 682f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrExiting = true; 683f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 684f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 685f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman assert(HasIndBrExiting && 686f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing exit block info!"); 687f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 68838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 689