LoopSimplify.cpp revision cd1142ef7f9ed5a570da8b332ba481061eb6fcb6
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); 1027d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM, 1037d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman BasicBlock *Preheader); 104f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 105120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner void PlaceSplitBlockCarefully(BasicBlock *NewBB, 10654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVectorImpl<BasicBlock*> &SplitPreds, 107120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L); 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 11038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 111844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopSimplify::ID = 0; 1124a60b932a279b3f5934a274f7fe4535026c5aed1Cameron ZwarichINITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", 1132ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Canonicalize natural loops", true, false) 1142ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1152ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1164a60b932a279b3f5934a274f7fe4535026c5aed1Cameron ZwarichINITIALIZE_PASS_END(LoopSimplify, "loop-simplify", 117ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Canonicalize natural loops", true, false) 118844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1197a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 12090c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LoopSimplifyID = LoopSimplify::ID; 121d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 12238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 12334d2b90d09226ebf6189775acfd2801e127b10ecDan Gohman/// runOnLoop - Run down all loops in the CFG (recursively, but we could do 12438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 12538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 126d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 127d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman L = l; 12838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 129c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI = &getAnalysis<LoopInfo>(); 1301465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands AA = getAnalysisIfAvailable<AliasAnalysis>(); 1310e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT = &getAnalysis<DominatorTree>(); 132ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman SE = getAnalysisIfAvailable<ScalarEvolution>(); 13338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 134d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed |= ProcessLoop(L, LPM); 13538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 13738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 13838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 14038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 14138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 142d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 14338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 1443bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop: 145d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 1462d0a91cd6c3df32014d547255d6a615bd1bc84fbDan Gohman // Check to see that no blocks (other than the header) in this loop have 147d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // predecessors that are not in the loop. This is not valid for natural 148d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // loops, but can occur if the blocks are unreachable. Since they are 149d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // unreachable we can just shamelessly delete those CFG edges! 150d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 151d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman BB != E; ++BB) { 152d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (*BB == L->getHeader()) continue; 153d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 154481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif SmallPtrSet<BasicBlock*, 4> BadPreds; 155481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif for (pred_iterator PI = pred_begin(*BB), 156481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif PE = pred_end(*BB); PI != PE; ++PI) { 1579672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 1589672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (!L->contains(P)) 1599672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BadPreds.insert(P); 1609672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 161d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 162d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Delete each unique out-of-loop (and thus dead) predecessor. 163481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(), 164d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman E = BadPreds.end(); I != E; ++I) { 165c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 1669fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " 1679fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << (*I)->getName() << "\n"); 168c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 169d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Inform each successor of each dead pred. 170d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 171d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*SI)->removePredecessor(*I); 172d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Zap the dead pred's terminator and replace it with unreachable. 173d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TerminatorInst *TI = (*I)->getTerminator(); 174d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 175d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*I)->getTerminator()->eraseFromParent(); 176d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman new UnreachableInst((*I)->getContext(), *I); 177d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed = true; 178d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 179d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 1802ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 18185669637139089eaed8def1583ac04266c9654e2Dan Gohman // If there are exiting blocks with branches on undef, resolve the undef in 18285669637139089eaed8def1583ac04266c9654e2Dan Gohman // the direction which will exit the loop. This will help simplify loop 18385669637139089eaed8def1583ac04266c9654e2Dan Gohman // trip count computations. 18485669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 18585669637139089eaed8def1583ac04266c9654e2Dan Gohman L->getExitingBlocks(ExitingBlocks); 18685669637139089eaed8def1583ac04266c9654e2Dan Gohman for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(), 18785669637139089eaed8def1583ac04266c9654e2Dan Gohman E = ExitingBlocks.end(); I != E; ++I) 18885669637139089eaed8def1583ac04266c9654e2Dan Gohman if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator())) 18985669637139089eaed8def1583ac04266c9654e2Dan Gohman if (BI->isConditional()) { 19085669637139089eaed8def1583ac04266c9654e2Dan Gohman if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) { 191c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 1929fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in " 1939fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << (*I)->getName() << "\n"); 194c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 19585669637139089eaed8def1583ac04266c9654e2Dan Gohman BI->setCondition(ConstantInt::get(Cond->getType(), 19685669637139089eaed8def1583ac04266c9654e2Dan Gohman !L->contains(BI->getSuccessor(0)))); 19785669637139089eaed8def1583ac04266c9654e2Dan Gohman Changed = true; 19885669637139089eaed8def1583ac04266c9654e2Dan Gohman } 19985669637139089eaed8def1583ac04266c9654e2Dan Gohman } 20085669637139089eaed8def1583ac04266c9654e2Dan Gohman 201fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Does the loop already have a preheader? If so, don't insert one. 2020df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 2030df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman if (!Preheader) { 2040df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman Preheader = InsertPreheaderForLoop(L); 205f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (Preheader) { 206fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 207f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 208f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 20938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 21038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 21166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 21266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 21366ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 214ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner // predecessors from outside of the loop, split the edge now. 215b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 216ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner L->getExitBlocks(ExitBlocks); 2171c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 21817146baef5b79114f05e0f99fcba389f2764b65dDan Gohman SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), 21917146baef5b79114f05e0f99fcba389f2764b65dDan Gohman ExitBlocks.end()); 22017146baef5b79114f05e0f99fcba389f2764b65dDan Gohman for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(), 221fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 222fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 223de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 224de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 2258587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // Must be exactly this loop: no subloops, parent loops, or non-loop preds 2268587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // allowed. 227ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner if (!L->contains(*PI)) { 228f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (RewriteLoopExitBlock(L, ExitBlock)) { 229fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 230f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 231f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 232de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 233de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 234fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 235dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 236529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 237529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 238f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *LoopLatch = L->getLoopLatch(); 239f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!LoopLatch) { 2403bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If this is really a nested loop, rip it out into a child loop. Don't do 2413bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // this for loops with a giant number of backedges, just factor them into a 2423bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // common backedge instead. 243f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (L->getNumBackEdges() < 8) { 2447d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman if (SeparateNestedLoop(L, LPM, Preheader)) { 2453bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ++NumNested; 2463bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // This is a big restructuring change, reprocess the whole loop. 2473bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner Changed = true; 2483bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // GCC doesn't tail recursion eliminate this. 2493bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner goto ReprocessLoop; 2503bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner } 251529b28da455a703d226a31a03400e6662ff569feChris Lattner } 252529b28da455a703d226a31a03400e6662ff569feChris Lattner 2533bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If we either couldn't, or didn't want to, identify nesting of the loops, 2543bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // insert a new block that all backedges target, then make it jump to the 2553bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // loop header. 256f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 257f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (LoopLatch) { 258fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 259f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 260f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 2612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 2622ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 26394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // Scan over the PHI nodes in the loop header. Since they now have only two 26494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // incoming values (the loop is canonicalized), we may have simplified the PHI 26594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 26694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PHINode *PN; 26794f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner for (BasicBlock::iterator I = L->getHeader()->begin(); 26894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner (PN = dyn_cast<PHINode>(I++)); ) 269618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier if (Value *V = SimplifyInstruction(PN, 0, 0, DT)) { 27067fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (AA) AA->deleteValue(PN); 271f73b99ab43c36b026a03430a30c329a343cdd77bChris Lattner if (SE) SE->forgetValue(PN); 27267fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->replaceAllUsesWith(V); 27367fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->eraseFromParent(); 27467fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands } 27594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner 2765cd8770412f98f6e6416c439e01222b3643b9e22Bob Wilson // If this loop has multiple exits and the exits all go to the same 2774b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // block, attempt to merge the exits. This helps several passes, such 2784b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // as LoopRotation, which do not support loops with multiple exits. 2794b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // SimplifyCFG also does this (and this code uses the same utility 2804b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // function), however this code is loop-aware, where SimplifyCFG is 2814b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // not. That gives it the advantage of being able to hoist 2824b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // loop-invariant instructions out of the way to open up more 2834b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // opportunities, and the disadvantage of having the responsibility 2844b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to preserve dominator information. 285b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman bool UniqueExit = true; 286b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (!ExitBlocks.empty()) 287b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 288b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (ExitBlocks[i] != ExitBlocks[0]) { 289b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman UniqueExit = false; 290b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman break; 291b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman } 292b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (UniqueExit) { 2934b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 2944b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BasicBlock *ExitingBlock = ExitingBlocks[i]; 2954b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!ExitingBlock->getSinglePredecessor()) continue; 2964b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2974b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!BI || !BI->isConditional()) continue; 2984b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 2994b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!CI || CI->getParent() != ExitingBlock) continue; 3004b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3014b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Attempt to hoist out all instructions except for the 3024b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // comparison and the branch. 3034b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman bool AllInvariant = true; 3042aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 3054b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Instruction *Inst = I++; 306689fac02268929b756086753b4656d6dabc5cf2dDevang Patel // Skip debug info intrinsics. 307689fac02268929b756086753b4656d6dabc5cf2dDevang Patel if (isa<DbgInfoIntrinsic>(Inst)) 308689fac02268929b756086753b4656d6dabc5cf2dDevang Patel continue; 3092aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman if (Inst == CI) 3104b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman continue; 311f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->makeLoopInvariant(Inst, Changed, 312f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Preheader ? Preheader->getTerminator() : 0)) { 3134b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman AllInvariant = false; 3144b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman break; 3154b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3164b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3174b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!AllInvariant) continue; 3184b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3194b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // The block has now been cleared of all instructions except for 3204b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // a comparison and a conditional branch. SimplifyCFG may be able 3214b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to fold it now. 3224b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!FoldBranchToCommonDest(BI)) continue; 3234b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3244b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Success. The block is now dead, so remove it from the loop, 325301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich // update the dominator tree and delete it. 3269fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " 3279fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << ExitingBlock->getName() << "\n"); 328c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 3291009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // If any reachable control flow within this loop has changed, notify 3301009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // ScalarEvolution. Currently assume the parent loop doesn't change 3311009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // (spliting edges doesn't count). If blocks, CFG edges, or other values 3321009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // in the parent loop change, then we need call to forgetLoop() for the 3331009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // parent instead. 3341009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick if (SE) 3351009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick SE->forgetLoop(L); 3361009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick 3374b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 3384b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Changed = true; 339a1baee20c4b042eca1f182fc003f38ab52efc7a9Dan Gohman LI->removeBlock(ExitingBlock); 3404b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3414b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DomTreeNode *Node = DT->getNode(ExitingBlock); 3424b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 3434b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Node->getChildren(); 3445184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman while (!Children.empty()) { 3455184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DomTreeNode *Child = Children.front(); 3465184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DT->changeImmediateDominator(Child, Node->getIDom()); 3474b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3484b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DT->eraseNode(ExitingBlock); 3494b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3504b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(0)->removePredecessor(ExitingBlock); 3514b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(1)->removePredecessor(ExitingBlock); 3524b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman ExitingBlock->eraseFromParent(); 3534b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3544b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3554b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 35638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 35738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 35838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 359dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 360dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 361dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 362dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 3630df6e09d43d6d733555a10d22572ddb0006e7d23Dan GohmanBasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { 364dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 365dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 366dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 36754b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OutsideBlocks; 368dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 3699672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif PI != PE; ++PI) { 3709672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 3719672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (!L->contains(P)) { // Coming in from outside the loop? 372f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // If the loop is branched to from an indirect branch, we won't 373f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // be able to fully transform the loop, because it prohibits 374f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // edge splitting. 3759672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (isa<IndirectBrInst>(P->getTerminator())) return 0; 376f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 377f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Keep track of it. 3789672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif OutsideBlocks.push_back(P); 379f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 3809672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 381fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 382c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner // Split out the loop pre-header. 3837d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman BasicBlock *PreheaderBB; 3847d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman if (!Header->isLandingPad()) { 3857d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", 3867d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman this); 3877d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman } else { 3887d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman SmallVector<BasicBlock*, 2> NewBBs; 389cd1142ef7f9ed5a570da8b332ba481061eb6fcb6Andrew Trick SplitLandingPadPredecessors(Header, OutsideBlocks, ".preheader", 3907d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman ".split-lp", this, NewBBs); 3917d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PreheaderBB = NewBBs[0]; 3927d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman } 3939f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 3947d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PreheaderBB->getTerminator()->setDebugLoc( 3957d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman Header->getFirstNonPHI()->getDebugLoc()); 3967d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman DEBUG(dbgs() << "LoopSimplify: Creating pre-header " 3977d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman << PreheaderBB->getName() << "\n"); 398c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 399120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 400120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 4017d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PlaceSplitBlockCarefully(PreheaderBB, OutsideBlocks, L); 4020df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman 4037d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman return PreheaderBB; 404dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 405dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 406529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 407529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks. This method is used to split exit blocks that have predecessors 408529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop. 40959fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 41054b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> LoopBlocks; 4119672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { 4129672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *I; 4139672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (L->contains(P)) { 414f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Don't do this if the loop is exited via an indirect branch. 4159672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (isa<IndirectBrInst>(P->getTerminator())) return 0; 416f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 4179672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif LoopBlocks.push_back(P); 418f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 4199672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 420dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 4217e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 422b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling BasicBlock *NewExitBB = 0; 423b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling 424b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling if (Exit->isLandingPad()) { 425b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling SmallVector<BasicBlock*, 2> NewBBs; 426b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling SplitLandingPadPredecessors(Exit, ArrayRef<BasicBlock*>(&LoopBlocks[0], 427b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling LoopBlocks.size()), 428b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling ".loopexit", ".nonloopexit", 429b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling this, NewBBs); 430b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling NewExitBB = NewBBs[0]; 431b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling } else { 4322fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", this); 433b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling } 4347e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 4359fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " 436b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling << NewExitBB->getName() << "\n"); 437b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling return NewExitBB; 4382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 440529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 441529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 442529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 44358d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 444529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 44558d7fbf250659246fcca9417a91170a681b1850aDevang Patel std::vector<BasicBlock *> WorkList; 44658d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(InputBB); 44758d7fbf250659246fcca9417a91170a681b1850aDevang Patel do { 44858d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 44958d7fbf250659246fcca9417a91170a681b1850aDevang Patel if (Blocks.insert(BB).second && BB != StopBlock) 45058d7fbf250659246fcca9417a91170a681b1850aDevang Patel // If BB is not already processed and it is not a stop block then 45158d7fbf250659246fcca9417a91170a681b1850aDevang Patel // insert its predecessor in the work list 45258d7fbf250659246fcca9417a91170a681b1850aDevang Patel for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 45358d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *WBB = *I; 45458d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(WBB); 45558d7fbf250659246fcca9417a91170a681b1850aDevang Patel } 45658d7fbf250659246fcca9417a91170a681b1850aDevang Patel } while(!WorkList.empty()); 457529b28da455a703d226a31a03400e6662ff569feChris Lattner} 458529b28da455a703d226a31a03400e6662ff569feChris Lattner 4591f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 4601f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops. 461dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 462d0c6f3dafd7c3e9137d4e6415014c94137fcd3fcDuncan Sands AliasAnalysis *AA, LoopInfo *LI) { 463200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 464200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 4651f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 466618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier if (Value *V = SimplifyInstruction(PN, 0, 0, DT)) { 46767fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands // This is a degenerate PHI already, don't modify it! 46867fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->replaceAllUsesWith(V); 46967fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (AA) AA->deleteValue(PN); 47067fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->eraseFromParent(); 47167fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands continue; 47267fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands } 473c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 474c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 475c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 476c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 477c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 478c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 479c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4801f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4811f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4821f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4831f62f82b05563df9c83094608de24ea581014d1eChris Lattner 484120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 485120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block. This prevents the preheader from 486120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated. 487120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattnervoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 48854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVectorImpl<BasicBlock*> &SplitPreds, 489120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L) { 490120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Check to see if NewBB is already well placed. 491120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = NewBB; --BBI; 492120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 493120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (&*BBI == SplitPreds[i]) 494120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner return; 495120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 4961c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 497120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If it isn't already after an outside block, move it after one. This is 498120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // always good as it makes the uncond branch from the outside block into a 499120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // fall-through. 5001c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 501120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Figure out *which* outside block to put this after. Prefer an outside 502120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // block that neighbors a BB actually in the loop. 503120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner BasicBlock *FoundBB = 0; 504120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 505120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = SplitPreds[i]; 5061c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick if (++BBI != NewBB->getParent()->end() && 507120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner L->contains(BBI)) { 508120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[i]; 509120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner break; 510120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 511120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 5121c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 513120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If our heuristic for a *good* bb to place this after doesn't find 514120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // anything, just pick something. It's likely better than leaving it within 515120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // the loop. 516120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (!FoundBB) 517120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[0]; 518120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner NewBB->moveAfter(FoundBB); 519120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner} 520120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 521120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 522529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 523529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 524529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 525529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 526529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 527529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 528529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 529529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 530529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 531529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 532529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 533529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 534529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 535529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 536529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 537529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 538529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 5397d1ff37118d5b3febae818676d9dd9513057fed7Eli FriedmanLoop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM, 5407d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman BasicBlock *Preheader) { 541cd1142ef7f9ed5a570da8b332ba481061eb6fcb6Andrew Trick // Don't try to separate loops without a preheader (this excludes 5427d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman // loop headers which are targeted by an indirectbr). 5437d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman if (!Preheader) 5447d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman return 0; 5457d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman 5467d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman // The header is not a landing pad; preheader insertion should ensure this. 5477d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman assert(!L->getHeader()->isLandingPad() && 5487d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman "Can't insert backedge to landing pad"); 5497d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman 550d0c6f3dafd7c3e9137d4e6415014c94137fcd3fcDuncan Sands PHINode *PN = FindPHIToPartitionLoops(L, DT, AA, LI); 5511f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 552529b28da455a703d226a31a03400e6662ff569feChris Lattner 5531f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 5541f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 5551f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 55654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OuterLoopPreds; 5571f62f82b05563df9c83094608de24ea581014d1eChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 5581f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 5597d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman !L->contains(PN->getIncomingBlock(i))) 5601f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 561529b28da455a703d226a31a03400e6662ff569feChris Lattner 562c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); 563c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 564ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // If ScalarEvolution is around and knows anything about values in 565ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // this loop, tell it to forget them, because we're about to 566ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // substantially change it. 567ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman if (SE) 568ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman SE->forgetLoop(L); 569ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman 5704b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 5712fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak BasicBlock *NewBB = 5722fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", this); 573529b28da455a703d226a31a03400e6662ff569feChris Lattner 574120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 575120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 576120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 5771c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 578529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 579529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 580529b28da455a703d226a31a03400e6662ff569feChris Lattner 581529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 582529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 583529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 584529b28da455a703d226a31a03400e6662ff569feChris Lattner else 585c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeTopLevelLoop(L, NewOuter); 586529b28da455a703d226a31a03400e6662ff569feChris Lattner 587529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 588529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 589529b28da455a703d226a31a03400e6662ff569feChris Lattner 590d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Add the new loop to the pass manager queue. 591d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman LPM.insertLoopIntoQueue(NewOuter); 592d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 5939b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 5949b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) 5959b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman NewOuter->addBlockEntry(*I); 596529b28da455a703d226a31a03400e6662ff569feChris Lattner 5975c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Now reset the header in L, which had been moved by 5985c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // SplitBlockPredecessors for the outer loop. 5995c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman L->moveToHeader(Header); 6005c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 601529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 602529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 603529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 6049672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { 6059672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 6069672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (DT->dominates(Header, P)) 6079672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif AddBlockAndPredsToSet(P, Header, BlocksInL); 6089672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 609529b28da455a703d226a31a03400e6662ff569feChris Lattner 610529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 611529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 612c08fa28897356be54fba724056c3aa91da8b3e39David Greene const std::vector<Loop*> &SubLoops = L->getSubLoops(); 613c08fa28897356be54fba724056c3aa91da8b3e39David Greene for (size_t I = 0; I != SubLoops.size(); ) 614c08fa28897356be54fba724056c3aa91da8b3e39David Greene if (BlocksInL.count(SubLoops[I]->getHeader())) 615529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 616529b28da455a703d226a31a03400e6662ff569feChris Lattner else 617c08fa28897356be54fba724056c3aa91da8b3e39David Greene NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 618529b28da455a703d226a31a03400e6662ff569feChris Lattner 619529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 620529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 621529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 622529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 623529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 624529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 625529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 626c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if ((*LI)[BB] == L) 627c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeLoopFor(BB, NewOuter); 628529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 629529b28da455a703d226a31a03400e6662ff569feChris Lattner } 630529b28da455a703d226a31a03400e6662ff569feChris Lattner } 631529b28da455a703d226a31a03400e6662ff569feChris Lattner 632529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 633529b28da455a703d226a31a03400e6662ff569feChris Lattner} 634529b28da455a703d226a31a03400e6662ff569feChris Lattner 635529b28da455a703d226a31a03400e6662ff569feChris Lattner 636529b28da455a703d226a31a03400e6662ff569feChris Lattner 6372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 6382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 6392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 6402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 6412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 642f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanBasicBlock * 643f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanLoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 6442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 6452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 6472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 6482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 6492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 650f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Unique backedge insertion currently depends on having a preheader. 651f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!Preheader) 652f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return 0; 653f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 6547d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman // The header is not a landing pad; preheader insertion should ensure this. 6557d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman assert(!Header->isLandingPad() && "Can't insert backedge to landing pad"); 6567d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman 6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 6582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 659bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ 660bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif BasicBlock *P = *I; 661c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman 662c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman // Indirectbr edges cannot be split, so we must fail if we find one. 663c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman if (isa<IndirectBrInst>(P->getTerminator())) 664c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman return 0; 665c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman 666bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif if (P != Preheader) BackedgeBlocks.push_back(P); 667bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif } 6682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 6701d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 6711d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Header->getName()+".backedge", F); 672051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 6732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6749fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block " 6759fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << BEBlock->getName() << "\n"); 676c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 6772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 6782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 6792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 680fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 6822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 683200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 684200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 6853ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(), 6863ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PN->getName()+".be", BETerminator); 687cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPN); 6882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 6902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 6912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 6922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 6932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 6942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 6952ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 6962ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 6972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 6982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 6992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 7002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 7012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 7022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 7032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 7042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 7052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 7062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 709fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 7102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 7112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 7122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 7132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 7142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 7152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7165551706b0f8e970720deea0bf6aa34116030d6beChris Lattner // Nuke all entries except the zero'th. 7175551706b0f8e970720deea0bf6aa34116030d6beChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 7185551706b0f8e970720deea0bf6aa34116030d6beChris Lattner PN->removeIncomingValue(e-i, false); 7192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 7212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 7222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 7242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 7252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 7262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 7272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 728cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(NewPN); 7292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 7302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 734280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky // backedge blocks to just to the BEBlock instead of the header. 7352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 7362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 7372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 7382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 7392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 7402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 7432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 7452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 746d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson L->addBasicBlockToLoop(BEBlock, LI->getBase()); 7472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7480e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update dominator information 7490e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(BEBlock); 750f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 751f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return BEBlock; 752f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman} 753f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 754f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohmanvoid LoopSimplify::verifyAnalysis() const { 755f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // It used to be possible to just assert L->isLoopSimplifyForm(), however 756f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // with the introduction of indirectbr, there are now cases where it's 757f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // not possible to transform a loop as necessary. We can at least check 758f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // that there is an indirectbr near any time there's trouble. 759f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 760f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Indirectbr can interfere with preheader and unique backedge insertion. 761f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->getLoopPreheader() || !L->getLoopLatch()) { 762f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrPred = false; 763f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman for (pred_iterator PI = pred_begin(L->getHeader()), 764f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman PE = pred_end(L->getHeader()); PI != PE; ++PI) 765f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((*PI)->getTerminator())) { 766f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrPred = true; 767f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 768f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 769f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman assert(HasIndBrPred && 770f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing loop header info!"); 7711f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)HasIndBrPred; 772f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 773f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 77466af89f642628c0d52138e86f9e4a0b9f5994474Bill Wendling // Indirectbr can interfere with exit block canonicalization. 775f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->hasDedicatedExits()) { 776f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrExiting = false; 777f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 778f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman L->getExitingBlocks(ExitingBlocks); 7790906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 780f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 781f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrExiting = true; 782f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 783f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 7840906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling } 7850906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling 78666af89f642628c0d52138e86f9e4a0b9f5994474Bill Wendling assert(HasIndBrExiting && 787f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing exit block info!"); 78866af89f642628c0d52138e86f9e4a0b9f5994474Bill Wendling (void)HasIndBrExiting; 789f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 79038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 791