LoopSimplify.cpp revision 0906a7c46cfc71e7c09dd6362df4310e72fdbc6b
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 404a60b932a279b3f5934a274f7fe4535026c5aed1Cameron Zwarich#define DEBUG_TYPE "loop-simplify" 4138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h" 423cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner#include "llvm/Constants.h" 4347b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 44689fac02268929b756086753b4656d6dabc5cf2dDevang Patel#include "llvm/IntrinsicInst.h" 452ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Function.h" 460a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h" 472ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Type.h" 48cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 49301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich#include "llvm/Analysis/Dominators.h" 50cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/InstructionSimplify.h" 51d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman#include "llvm/Analysis/LoopPass.h" 52cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/ScalarEvolution.h" 5354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 544b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman#include "llvm/Transforms/Utils/Local.h" 5538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 56c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman#include "llvm/Support/Debug.h" 57551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 58551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetVector.h" 59551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 60551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 6166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerusing namespace llvm; 62d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 63d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 64d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumNested , "Number of nested loops split out"); 6538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 66d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 676726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct LoopSimplify : public LoopPass { 68ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 69081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LoopSimplify() : LoopPass(ID) { 70081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLoopSimplifyPass(*PassRegistry::getPassRegistry()); 71081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 72794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 73cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // AA - If we have an alias analysis object to update, this is it, otherwise 74cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // this is null. 75cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner AliasAnalysis *AA; 76c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LoopInfo *LI; 770e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominatorTree *DT; 78ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman ScalarEvolution *SE; 79d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Loop *L; 80d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 81fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 8238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 8338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 84052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<DominatorTree>(); 8538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 861e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman 87052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<LoopInfo>(); 881e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<LoopInfo>(); 891e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman 904c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel AU.addPreserved<AliasAnalysis>(); 91ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman AU.addPreserved<ScalarEvolution>(); 9294f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 9338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 9458e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 95f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 96f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman void verifyAnalysis() const; 9758e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 9838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 99d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman bool ProcessLoop(Loop *L, LPPassManager &LPM); 10059fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 1010df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman BasicBlock *InsertPreheaderForLoop(Loop *L); 102d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); 103f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 104120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner void PlaceSplitBlockCarefully(BasicBlock *NewBB, 10554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVectorImpl<BasicBlock*> &SplitPreds, 106120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L); 10738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 110844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopSimplify::ID = 0; 1114a60b932a279b3f5934a274f7fe4535026c5aed1Cameron ZwarichINITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", 1122ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Canonicalize natural loops", true, false) 1132ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1142ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1154a60b932a279b3f5934a274f7fe4535026c5aed1Cameron ZwarichINITIALIZE_PASS_END(LoopSimplify, "loop-simplify", 116ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Canonicalize natural loops", true, false) 117844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1187a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 11990c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LoopSimplifyID = LoopSimplify::ID; 120d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 12138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 12234d2b90d09226ebf6189775acfd2801e127b10ecDan Gohman/// runOnLoop - Run down all loops in the CFG (recursively, but we could do 12338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 12438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 125d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 126d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman L = l; 12738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 128c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI = &getAnalysis<LoopInfo>(); 1291465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands AA = getAnalysisIfAvailable<AliasAnalysis>(); 1300e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT = &getAnalysis<DominatorTree>(); 131ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman SE = getAnalysisIfAvailable<ScalarEvolution>(); 13238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 133d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed |= ProcessLoop(L, LPM); 13438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 13638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 13738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 13938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 14038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 141d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 14238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 1433bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop: 144d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 1452d0a91cd6c3df32014d547255d6a615bd1bc84fbDan Gohman // Check to see that no blocks (other than the header) in this loop have 146d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // predecessors that are not in the loop. This is not valid for natural 147d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // loops, but can occur if the blocks are unreachable. Since they are 148d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // unreachable we can just shamelessly delete those CFG edges! 149d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 150d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman BB != E; ++BB) { 151d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (*BB == L->getHeader()) continue; 152d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 153481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif SmallPtrSet<BasicBlock*, 4> BadPreds; 154481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif for (pred_iterator PI = pred_begin(*BB), 155481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif PE = pred_end(*BB); PI != PE; ++PI) { 1569672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 1579672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (!L->contains(P)) 1589672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BadPreds.insert(P); 1599672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 160d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 161d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Delete each unique out-of-loop (and thus dead) predecessor. 162481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(), 163d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman E = BadPreds.end(); I != E; ++I) { 164c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 1659fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " 1669fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << (*I)->getName() << "\n"); 167c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 168d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Inform each successor of each dead pred. 169d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 170d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*SI)->removePredecessor(*I); 171d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Zap the dead pred's terminator and replace it with unreachable. 172d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TerminatorInst *TI = (*I)->getTerminator(); 173d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 174d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*I)->getTerminator()->eraseFromParent(); 175d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman new UnreachableInst((*I)->getContext(), *I); 176d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed = true; 177d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 178d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 1792ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 18085669637139089eaed8def1583ac04266c9654e2Dan Gohman // If there are exiting blocks with branches on undef, resolve the undef in 18185669637139089eaed8def1583ac04266c9654e2Dan Gohman // the direction which will exit the loop. This will help simplify loop 18285669637139089eaed8def1583ac04266c9654e2Dan Gohman // trip count computations. 18385669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 18485669637139089eaed8def1583ac04266c9654e2Dan Gohman L->getExitingBlocks(ExitingBlocks); 18585669637139089eaed8def1583ac04266c9654e2Dan Gohman for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(), 18685669637139089eaed8def1583ac04266c9654e2Dan Gohman E = ExitingBlocks.end(); I != E; ++I) 18785669637139089eaed8def1583ac04266c9654e2Dan Gohman if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator())) 18885669637139089eaed8def1583ac04266c9654e2Dan Gohman if (BI->isConditional()) { 18985669637139089eaed8def1583ac04266c9654e2Dan Gohman if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) { 190c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 1919fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in " 1929fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << (*I)->getName() << "\n"); 193c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 19485669637139089eaed8def1583ac04266c9654e2Dan Gohman BI->setCondition(ConstantInt::get(Cond->getType(), 19585669637139089eaed8def1583ac04266c9654e2Dan Gohman !L->contains(BI->getSuccessor(0)))); 19685669637139089eaed8def1583ac04266c9654e2Dan Gohman Changed = true; 19785669637139089eaed8def1583ac04266c9654e2Dan Gohman } 19885669637139089eaed8def1583ac04266c9654e2Dan Gohman } 19985669637139089eaed8def1583ac04266c9654e2Dan Gohman 200fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Does the loop already have a preheader? If so, don't insert one. 2010df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 2020df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman if (!Preheader) { 2030df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman Preheader = InsertPreheaderForLoop(L); 204f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (Preheader) { 205fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 206f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 207f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 20838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 20938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 21066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 21166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 21266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 213ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner // predecessors from outside of the loop, split the edge now. 214b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 215ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner L->getExitBlocks(ExitBlocks); 2161c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 21717146baef5b79114f05e0f99fcba389f2764b65dDan Gohman SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), 21817146baef5b79114f05e0f99fcba389f2764b65dDan Gohman ExitBlocks.end()); 21917146baef5b79114f05e0f99fcba389f2764b65dDan Gohman for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(), 220fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 221fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 222de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 223de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 2248587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // Must be exactly this loop: no subloops, parent loops, or non-loop preds 2258587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // allowed. 226ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner if (!L->contains(*PI)) { 227f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (RewriteLoopExitBlock(L, ExitBlock)) { 228fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 229f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 230f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 231de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 232de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 233fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 234dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 235529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 236529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 237f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *LoopLatch = L->getLoopLatch(); 238f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!LoopLatch) { 2393bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If this is really a nested loop, rip it out into a child loop. Don't do 2403bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // this for loops with a giant number of backedges, just factor them into a 2413bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // common backedge instead. 242f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (L->getNumBackEdges() < 8) { 243d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (SeparateNestedLoop(L, LPM)) { 2443bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ++NumNested; 2453bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // This is a big restructuring change, reprocess the whole loop. 2463bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner Changed = true; 2473bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // GCC doesn't tail recursion eliminate this. 2483bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner goto ReprocessLoop; 2493bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner } 250529b28da455a703d226a31a03400e6662ff569feChris Lattner } 251529b28da455a703d226a31a03400e6662ff569feChris Lattner 2523bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If we either couldn't, or didn't want to, identify nesting of the loops, 2533bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // insert a new block that all backedges target, then make it jump to the 2543bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // loop header. 255f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 256f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (LoopLatch) { 257fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 258f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 259f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 2602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 2612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 26294f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // Scan over the PHI nodes in the loop header. Since they now have only two 26394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // incoming values (the loop is canonicalized), we may have simplified the PHI 26494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 26594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PHINode *PN; 26694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner for (BasicBlock::iterator I = L->getHeader()->begin(); 26794f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner (PN = dyn_cast<PHINode>(I++)); ) 26867fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (Value *V = SimplifyInstruction(PN, 0, DT)) { 26967fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (AA) AA->deleteValue(PN); 270f73b99ab43c36b026a03430a30c329a343cdd77bChris Lattner if (SE) SE->forgetValue(PN); 27167fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->replaceAllUsesWith(V); 27267fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->eraseFromParent(); 27367fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands } 27494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner 2755cd8770412f98f6e6416c439e01222b3643b9e22Bob Wilson // If this loop has multiple exits and the exits all go to the same 2764b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // block, attempt to merge the exits. This helps several passes, such 2774b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // as LoopRotation, which do not support loops with multiple exits. 2784b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // SimplifyCFG also does this (and this code uses the same utility 2794b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // function), however this code is loop-aware, where SimplifyCFG is 2804b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // not. That gives it the advantage of being able to hoist 2814b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // loop-invariant instructions out of the way to open up more 2824b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // opportunities, and the disadvantage of having the responsibility 2834b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to preserve dominator information. 284b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman bool UniqueExit = true; 285b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (!ExitBlocks.empty()) 286b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 287b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (ExitBlocks[i] != ExitBlocks[0]) { 288b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman UniqueExit = false; 289b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman break; 290b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman } 291b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (UniqueExit) { 2924b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 2934b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BasicBlock *ExitingBlock = ExitingBlocks[i]; 2944b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!ExitingBlock->getSinglePredecessor()) continue; 2954b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2964b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!BI || !BI->isConditional()) continue; 2974b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 2984b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!CI || CI->getParent() != ExitingBlock) continue; 2994b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3004b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Attempt to hoist out all instructions except for the 3014b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // comparison and the branch. 3024b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman bool AllInvariant = true; 3032aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 3044b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Instruction *Inst = I++; 305689fac02268929b756086753b4656d6dabc5cf2dDevang Patel // Skip debug info intrinsics. 306689fac02268929b756086753b4656d6dabc5cf2dDevang Patel if (isa<DbgInfoIntrinsic>(Inst)) 307689fac02268929b756086753b4656d6dabc5cf2dDevang Patel continue; 3082aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman if (Inst == CI) 3094b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman continue; 310f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->makeLoopInvariant(Inst, Changed, 311f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Preheader ? Preheader->getTerminator() : 0)) { 3124b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman AllInvariant = false; 3134b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman break; 3144b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3154b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3164b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!AllInvariant) continue; 3174b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3184b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // The block has now been cleared of all instructions except for 3194b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // a comparison and a conditional branch. SimplifyCFG may be able 3204b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to fold it now. 3214b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!FoldBranchToCommonDest(BI)) continue; 3224b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3234b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Success. The block is now dead, so remove it from the loop, 324301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich // update the dominator tree and delete it. 3259fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " 3269fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << ExitingBlock->getName() << "\n"); 327c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 3281009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // If any reachable control flow within this loop has changed, notify 3291009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // ScalarEvolution. Currently assume the parent loop doesn't change 3301009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // (spliting edges doesn't count). If blocks, CFG edges, or other values 3311009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // in the parent loop change, then we need call to forgetLoop() for the 3321009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // parent instead. 3331009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick if (SE) 3341009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick SE->forgetLoop(L); 3351009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick 3364b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 3374b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Changed = true; 338a1baee20c4b042eca1f182fc003f38ab52efc7a9Dan Gohman LI->removeBlock(ExitingBlock); 3394b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3404b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DomTreeNode *Node = DT->getNode(ExitingBlock); 3414b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 3424b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Node->getChildren(); 3435184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman while (!Children.empty()) { 3445184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DomTreeNode *Child = Children.front(); 3455184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DT->changeImmediateDominator(Child, Node->getIDom()); 3464b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3474b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DT->eraseNode(ExitingBlock); 3484b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3494b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(0)->removePredecessor(ExitingBlock); 3504b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(1)->removePredecessor(ExitingBlock); 3514b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman ExitingBlock->eraseFromParent(); 3524b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3534b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3544b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 35538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 35638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 35738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 358dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 359dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 360dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 361dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 3620df6e09d43d6d733555a10d22572ddb0006e7d23Dan GohmanBasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { 363dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 364dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 365dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 36654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OutsideBlocks; 367dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 3689672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif PI != PE; ++PI) { 3699672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 3709672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (!L->contains(P)) { // Coming in from outside the loop? 371f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // If the loop is branched to from an indirect branch, we won't 372f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // be able to fully transform the loop, because it prohibits 373f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // edge splitting. 3749672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (isa<IndirectBrInst>(P->getTerminator())) return 0; 375f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 376f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Keep track of it. 3779672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif OutsideBlocks.push_back(P); 378f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 3799672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 380fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 381c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner // Split out the loop pre-header. 382dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 38354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 38454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner ".preheader", this); 3859f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 386c0136990274d5842f3f389362826e614454c0201Devang Patel NewBB->getTerminator()->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc()); 3879fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Creating pre-header " << NewBB->getName() 3889fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << "\n"); 389c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 390120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 391120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 392120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 3930df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman 3940df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman return NewBB; 395dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 396dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 397529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 398529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks. This method is used to split exit blocks that have predecessors 399529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop. 40059fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 4010906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling // Don't split a landing pad block. 4020906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling if (Exit->isLandingPad()) return 0; 4030906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling 40454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> LoopBlocks; 4059672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { 4069672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *I; 4079672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (L->contains(P)) { 408f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Don't do this if the loop is exited via an indirect branch. 4099672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (isa<IndirectBrInst>(P->getTerminator())) return 0; 410f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 4119672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif LoopBlocks.push_back(P); 412f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 4139672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 414dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 4157e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 4161c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 41754b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner LoopBlocks.size(), ".loopexit", 41854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner this); 4197e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 4209fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " 4219fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << NewBB->getName() << "\n"); 42259fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner return NewBB; 4232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 425529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 426529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 427529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 42858d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 429529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 43058d7fbf250659246fcca9417a91170a681b1850aDevang Patel std::vector<BasicBlock *> WorkList; 43158d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(InputBB); 43258d7fbf250659246fcca9417a91170a681b1850aDevang Patel do { 43358d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 43458d7fbf250659246fcca9417a91170a681b1850aDevang Patel if (Blocks.insert(BB).second && BB != StopBlock) 43558d7fbf250659246fcca9417a91170a681b1850aDevang Patel // If BB is not already processed and it is not a stop block then 43658d7fbf250659246fcca9417a91170a681b1850aDevang Patel // insert its predecessor in the work list 43758d7fbf250659246fcca9417a91170a681b1850aDevang Patel for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 43858d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *WBB = *I; 43958d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(WBB); 44058d7fbf250659246fcca9417a91170a681b1850aDevang Patel } 44158d7fbf250659246fcca9417a91170a681b1850aDevang Patel } while(!WorkList.empty()); 442529b28da455a703d226a31a03400e6662ff569feChris Lattner} 443529b28da455a703d226a31a03400e6662ff569feChris Lattner 4441f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 4451f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops. 446dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 447d0c6f3dafd7c3e9137d4e6415014c94137fcd3fcDuncan Sands AliasAnalysis *AA, LoopInfo *LI) { 448200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 449200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 4501f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 45167fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (Value *V = SimplifyInstruction(PN, 0, DT)) { 45267fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands // This is a degenerate PHI already, don't modify it! 45367fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->replaceAllUsesWith(V); 45467fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (AA) AA->deleteValue(PN); 45567fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->eraseFromParent(); 45667fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands continue; 45767fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands } 458c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 459c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 460c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 461c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 462c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 463c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 464c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4651f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4661f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4671f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4681f62f82b05563df9c83094608de24ea581014d1eChris Lattner 469120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 470120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block. This prevents the preheader from 471120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated. 472120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattnervoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 47354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVectorImpl<BasicBlock*> &SplitPreds, 474120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L) { 475120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Check to see if NewBB is already well placed. 476120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = NewBB; --BBI; 477120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 478120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (&*BBI == SplitPreds[i]) 479120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner return; 480120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 4811c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 482120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If it isn't already after an outside block, move it after one. This is 483120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // always good as it makes the uncond branch from the outside block into a 484120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // fall-through. 4851c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 486120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Figure out *which* outside block to put this after. Prefer an outside 487120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // block that neighbors a BB actually in the loop. 488120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner BasicBlock *FoundBB = 0; 489120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 490120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = SplitPreds[i]; 4911c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick if (++BBI != NewBB->getParent()->end() && 492120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner L->contains(BBI)) { 493120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[i]; 494120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner break; 495120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 496120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 4971c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 498120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If our heuristic for a *good* bb to place this after doesn't find 499120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // anything, just pick something. It's likely better than leaving it within 500120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // the loop. 501120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (!FoundBB) 502120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[0]; 503120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner NewBB->moveAfter(FoundBB); 504120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner} 505120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 506120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 507529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 508529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 509529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 510529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 511529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 512529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 513529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 514529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 515529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 516529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 517529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 518529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 519529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 520529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 521529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 522529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 523529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 524d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanLoop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { 525d0c6f3dafd7c3e9137d4e6415014c94137fcd3fcDuncan Sands PHINode *PN = FindPHIToPartitionLoops(L, DT, AA, LI); 5261f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 527529b28da455a703d226a31a03400e6662ff569feChris Lattner 5281f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 5291f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 5301f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 53154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OuterLoopPreds; 5321f62f82b05563df9c83094608de24ea581014d1eChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 5331f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 534a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman !L->contains(PN->getIncomingBlock(i))) { 535a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman // We can't split indirectbr edges. 536a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator())) 537a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman return 0; 538a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman 5391f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 540a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman } 541529b28da455a703d226a31a03400e6662ff569feChris Lattner 542c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); 543c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 544ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // If ScalarEvolution is around and knows anything about values in 545ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // this loop, tell it to forget them, because we're about to 546ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // substantially change it. 547ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman if (SE) 548ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman SE->forgetLoop(L); 549ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman 5504b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 55154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 55254b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner OuterLoopPreds.size(), 55354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner ".outer", this); 554529b28da455a703d226a31a03400e6662ff569feChris Lattner 555120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 556120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 557120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 5581c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 559529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 560529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 561529b28da455a703d226a31a03400e6662ff569feChris Lattner 562529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 563529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 564529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 565529b28da455a703d226a31a03400e6662ff569feChris Lattner else 566c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeTopLevelLoop(L, NewOuter); 567529b28da455a703d226a31a03400e6662ff569feChris Lattner 568529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 569529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 570529b28da455a703d226a31a03400e6662ff569feChris Lattner 571d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Add the new loop to the pass manager queue. 572d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman LPM.insertLoopIntoQueue(NewOuter); 573d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 5749b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 5759b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) 5769b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman NewOuter->addBlockEntry(*I); 577529b28da455a703d226a31a03400e6662ff569feChris Lattner 5785c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Now reset the header in L, which had been moved by 5795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // SplitBlockPredecessors for the outer loop. 5805c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman L->moveToHeader(Header); 5815c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 582529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 583529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 584529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 5859672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { 5869672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 5879672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (DT->dominates(Header, P)) 5889672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif AddBlockAndPredsToSet(P, Header, BlocksInL); 5899672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 590529b28da455a703d226a31a03400e6662ff569feChris Lattner 591529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 592529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 593c08fa28897356be54fba724056c3aa91da8b3e39David Greene const std::vector<Loop*> &SubLoops = L->getSubLoops(); 594c08fa28897356be54fba724056c3aa91da8b3e39David Greene for (size_t I = 0; I != SubLoops.size(); ) 595c08fa28897356be54fba724056c3aa91da8b3e39David Greene if (BlocksInL.count(SubLoops[I]->getHeader())) 596529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 597529b28da455a703d226a31a03400e6662ff569feChris Lattner else 598c08fa28897356be54fba724056c3aa91da8b3e39David Greene NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 599529b28da455a703d226a31a03400e6662ff569feChris Lattner 600529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 601529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 602529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 603529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 604529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 605529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 606529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 607c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if ((*LI)[BB] == L) 608c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeLoopFor(BB, NewOuter); 609529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 610529b28da455a703d226a31a03400e6662ff569feChris Lattner } 611529b28da455a703d226a31a03400e6662ff569feChris Lattner } 612529b28da455a703d226a31a03400e6662ff569feChris Lattner 613529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 614529b28da455a703d226a31a03400e6662ff569feChris Lattner} 615529b28da455a703d226a31a03400e6662ff569feChris Lattner 616529b28da455a703d226a31a03400e6662ff569feChris Lattner 617529b28da455a703d226a31a03400e6662ff569feChris Lattner 6182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 6192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 6202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 6212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 6222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 623f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanBasicBlock * 624f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanLoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 6252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 6262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 6282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 6292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 6302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 631f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Unique backedge insertion currently depends on having a preheader. 632f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!Preheader) 633f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return 0; 634f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 6352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 6362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 637bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ 638bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif BasicBlock *P = *I; 639c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman 640c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman // Indirectbr edges cannot be split, so we must fail if we find one. 641c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman if (isa<IndirectBrInst>(P->getTerminator())) 642c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman return 0; 643c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman 644bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif if (P != Preheader) BackedgeBlocks.push_back(P); 645bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif } 6462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 6481d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 6491d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Header->getName()+".backedge", F); 650051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 6512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6529fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block " 6539fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << BEBlock->getName() << "\n"); 654c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 6552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 6562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 658fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 6602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 661200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 662200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 6633ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(), 6643ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PN->getName()+".be", BETerminator); 665cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPN); 6662ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 6682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 6692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 6702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 6712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 6722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 6732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 6742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 6752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 6762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 6772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 6782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 6792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 6812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 6822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 6832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 6842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 687fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 6892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 6902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 6912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 6922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 6932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6945551706b0f8e970720deea0bf6aa34116030d6beChris Lattner // Nuke all entries except the zero'th. 6955551706b0f8e970720deea0bf6aa34116030d6beChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 6965551706b0f8e970720deea0bf6aa34116030d6beChris Lattner PN->removeIncomingValue(e-i, false); 6972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 6992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 7002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 7022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 7032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 7042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 7052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 706cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(NewPN); 7072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 7082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 712280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky // backedge blocks to just to the BEBlock instead of the header. 7132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 7142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 7152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 7162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 7172ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 7182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 7212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 7232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 724d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson L->addBasicBlockToLoop(BEBlock, LI->getBase()); 7252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7260e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update dominator information 7270e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(BEBlock); 728f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 729f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return BEBlock; 730f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman} 731f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 732f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohmanvoid LoopSimplify::verifyAnalysis() const { 733f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // It used to be possible to just assert L->isLoopSimplifyForm(), however 734f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // with the introduction of indirectbr, there are now cases where it's 735f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // not possible to transform a loop as necessary. We can at least check 736f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // that there is an indirectbr near any time there's trouble. 737f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 738f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Indirectbr can interfere with preheader and unique backedge insertion. 739f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->getLoopPreheader() || !L->getLoopLatch()) { 740f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrPred = false; 741f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman for (pred_iterator PI = pred_begin(L->getHeader()), 742f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman PE = pred_end(L->getHeader()); PI != PE; ++PI) 743f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((*PI)->getTerminator())) { 744f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrPred = true; 745f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 746f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 747f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman assert(HasIndBrPred && 748f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing loop header info!"); 7491f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)HasIndBrPred; 750f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 751f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 7520906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling // Indirectbr and LandingPad can interfere with exit block canonicalization. 753f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->hasDedicatedExits()) { 754f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrExiting = false; 7550906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling bool HasLPadExiting = false; 756f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 757f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman L->getExitingBlocks(ExitingBlocks); 7580906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 759f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 760f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrExiting = true; 761f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 762f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 7630906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling if (const InvokeInst *II = 7640906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling dyn_cast<InvokeInst>(ExitingBlocks[i]->getTerminator())) { 7650906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling if (L->contains(II->getNormalDest()) && 7660906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling !L->contains(II->getUnwindDest())) { 7670906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling HasLPadExiting = true; 7680906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling break; 7690906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling } 7700906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling } 7710906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling } 7720906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling 7730906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling assert((HasIndBrExiting || HasLPadExiting) && 774f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing exit block info!"); 7750906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling (void)HasIndBrExiting; (void)HasLPadExiting; 776f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 77738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 778