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" 42d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DepthFirstIterator.h" 43d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetOperations.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 45d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 46cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 478999f4777b920ab144a15a6f54a865a07f9c4a7fBenjamin Kramer#include "llvm/Analysis/DependenceAnalysis.h" 48301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich#include "llvm/Analysis/Dominators.h" 49cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/InstructionSimplify.h" 50d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman#include "llvm/Analysis/LoopPass.h" 51cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/ScalarEvolution.h" 520b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 530b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 540b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 550b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 560b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 570b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 5838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 59c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman#include "llvm/Support/Debug.h" 60d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/BasicBlockUtils.h" 61d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 624e6b24ffcfafbc0c5eda1bb89163ccd56f394fdfHal Finkel#include "llvm/Transforms/Utils/LoopUtils.h" 6366ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerusing namespace llvm; 64d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 65d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 66d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumNested , "Number of nested loops split out"); 6738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 68d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 696726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct LoopSimplify : public LoopPass { 70ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 71081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LoopSimplify() : LoopPass(ID) { 72081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLoopSimplifyPass(*PassRegistry::getPassRegistry()); 73081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 74794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 75cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // AA - If we have an alias analysis object to update, this is it, otherwise 76cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // this is null. 77cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner AliasAnalysis *AA; 78c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LoopInfo *LI; 790e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominatorTree *DT; 80ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman ScalarEvolution *SE; 81d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Loop *L; 82d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 83fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 8438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 8538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 86052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<DominatorTree>(); 8738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 881e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman 89052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<LoopInfo>(); 901e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<LoopInfo>(); 911e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman 924c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel AU.addPreserved<AliasAnalysis>(); 93ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman AU.addPreserved<ScalarEvolution>(); 948999f4777b920ab144a15a6f54a865a07f9c4a7fBenjamin Kramer AU.addPreserved<DependenceAnalysis>(); 9594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 9638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 9758e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 98f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 99f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman void verifyAnalysis() const; 10058e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 10138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 102d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman bool ProcessLoop(Loop *L, LPPassManager &LPM); 10359fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 1047d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM, 1057d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman BasicBlock *Preheader); 106f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 10738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 110fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkelstatic void PlaceSplitBlockCarefully(BasicBlock *NewBB, 111fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel SmallVectorImpl<BasicBlock*> &SplitPreds, 112fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel Loop *L); 113fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel 114844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopSimplify::ID = 0; 1154a60b932a279b3f5934a274f7fe4535026c5aed1Cameron ZwarichINITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", 1162ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Canonicalize natural loops", true, false) 1172ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1182ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1194a60b932a279b3f5934a274f7fe4535026c5aed1Cameron ZwarichINITIALIZE_PASS_END(LoopSimplify, "loop-simplify", 120ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Canonicalize natural loops", true, false) 121844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1227a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 12390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LoopSimplifyID = LoopSimplify::ID; 124d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 12538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 12634d2b90d09226ebf6189775acfd2801e127b10ecDan Gohman/// runOnLoop - Run down all loops in the CFG (recursively, but we could do 12738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 12838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 129d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 130d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman L = l; 13138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 132c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI = &getAnalysis<LoopInfo>(); 1331465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands AA = getAnalysisIfAvailable<AliasAnalysis>(); 1340e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT = &getAnalysis<DominatorTree>(); 135ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman SE = getAnalysisIfAvailable<ScalarEvolution>(); 13638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 137d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed |= ProcessLoop(L, LPM); 13838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 14038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 14138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 14238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 14338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 14438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 145d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 14638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 1473bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop: 148d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 1492d0a91cd6c3df32014d547255d6a615bd1bc84fbDan Gohman // Check to see that no blocks (other than the header) in this loop have 150d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // predecessors that are not in the loop. This is not valid for natural 151d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // loops, but can occur if the blocks are unreachable. Since they are 152d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // unreachable we can just shamelessly delete those CFG edges! 153d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 154d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman BB != E; ++BB) { 155d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (*BB == L->getHeader()) continue; 156d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 157481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif SmallPtrSet<BasicBlock*, 4> BadPreds; 158481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif for (pred_iterator PI = pred_begin(*BB), 159481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif PE = pred_end(*BB); PI != PE; ++PI) { 1609672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 1619672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (!L->contains(P)) 1629672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BadPreds.insert(P); 1639672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 164d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 165d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Delete each unique out-of-loop (and thus dead) predecessor. 166481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(), 167d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman E = BadPreds.end(); I != E; ++I) { 168c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 1699fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " 1709fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << (*I)->getName() << "\n"); 171c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 172d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Inform each successor of each dead pred. 173d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 174d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*SI)->removePredecessor(*I); 175d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Zap the dead pred's terminator and replace it with unreachable. 176d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TerminatorInst *TI = (*I)->getTerminator(); 177d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 178d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman (*I)->getTerminator()->eraseFromParent(); 179d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman new UnreachableInst((*I)->getContext(), *I); 180d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed = true; 181d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 182d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 1832ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 18485669637139089eaed8def1583ac04266c9654e2Dan Gohman // If there are exiting blocks with branches on undef, resolve the undef in 18585669637139089eaed8def1583ac04266c9654e2Dan Gohman // the direction which will exit the loop. This will help simplify loop 18685669637139089eaed8def1583ac04266c9654e2Dan Gohman // trip count computations. 18785669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 18885669637139089eaed8def1583ac04266c9654e2Dan Gohman L->getExitingBlocks(ExitingBlocks); 18985669637139089eaed8def1583ac04266c9654e2Dan Gohman for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(), 19085669637139089eaed8def1583ac04266c9654e2Dan Gohman E = ExitingBlocks.end(); I != E; ++I) 19185669637139089eaed8def1583ac04266c9654e2Dan Gohman if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator())) 19285669637139089eaed8def1583ac04266c9654e2Dan Gohman if (BI->isConditional()) { 19385669637139089eaed8def1583ac04266c9654e2Dan Gohman if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) { 194c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 1959fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in " 1969fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << (*I)->getName() << "\n"); 197c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 19885669637139089eaed8def1583ac04266c9654e2Dan Gohman BI->setCondition(ConstantInt::get(Cond->getType(), 19985669637139089eaed8def1583ac04266c9654e2Dan Gohman !L->contains(BI->getSuccessor(0)))); 200b2b2273ef4b67b7da4c05472095b8b96cc04ca8dBenjamin Kramer 201b2b2273ef4b67b7da4c05472095b8b96cc04ca8dBenjamin Kramer // This may make the loop analyzable, force SCEV recomputation. 202b2b2273ef4b67b7da4c05472095b8b96cc04ca8dBenjamin Kramer if (SE) 203b2b2273ef4b67b7da4c05472095b8b96cc04ca8dBenjamin Kramer SE->forgetLoop(L); 204b2b2273ef4b67b7da4c05472095b8b96cc04ca8dBenjamin Kramer 20585669637139089eaed8def1583ac04266c9654e2Dan Gohman Changed = true; 20685669637139089eaed8def1583ac04266c9654e2Dan Gohman } 20785669637139089eaed8def1583ac04266c9654e2Dan Gohman } 20885669637139089eaed8def1583ac04266c9654e2Dan Gohman 209fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Does the loop already have a preheader? If so, don't insert one. 2100df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 2110df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman if (!Preheader) { 212fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel Preheader = InsertPreheaderForLoop(L, this); 213f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (Preheader) { 214fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 215f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 216f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 21738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 21838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 21966ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 22066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 22166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 222ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner // predecessors from outside of the loop, split the edge now. 223b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 224ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner L->getExitBlocks(ExitBlocks); 2251c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 22617146baef5b79114f05e0f99fcba389f2764b65dDan Gohman SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), 22717146baef5b79114f05e0f99fcba389f2764b65dDan Gohman ExitBlocks.end()); 22817146baef5b79114f05e0f99fcba389f2764b65dDan Gohman for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(), 229fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 230fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 231de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 232de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 2338587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // Must be exactly this loop: no subloops, parent loops, or non-loop preds 2348587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // allowed. 235ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner if (!L->contains(*PI)) { 236f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (RewriteLoopExitBlock(L, ExitBlock)) { 237fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 238f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 239f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 240de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 241de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 242fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 243dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 244529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 245529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 246f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman BasicBlock *LoopLatch = L->getLoopLatch(); 247f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!LoopLatch) { 2483bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If this is really a nested loop, rip it out into a child loop. Don't do 2493bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // this for loops with a giant number of backedges, just factor them into a 2503bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // common backedge instead. 251f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (L->getNumBackEdges() < 8) { 2527d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman if (SeparateNestedLoop(L, LPM, Preheader)) { 2533bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ++NumNested; 2543bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // This is a big restructuring change, reprocess the whole loop. 2553bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner Changed = true; 2563bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // GCC doesn't tail recursion eliminate this. 2573bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner goto ReprocessLoop; 2583bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner } 259529b28da455a703d226a31a03400e6662ff569feChris Lattner } 260529b28da455a703d226a31a03400e6662ff569feChris Lattner 2613bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If we either couldn't, or didn't want to, identify nesting of the loops, 2623bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // insert a new block that all backedges target, then make it jump to the 2633bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // loop header. 264f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 265f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (LoopLatch) { 266fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumInserted; 267f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Changed = true; 268f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 2692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 2702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 27194f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // Scan over the PHI nodes in the loop header. Since they now have only two 27294f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // incoming values (the loop is canonicalized), we may have simplified the PHI 27394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 27494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PHINode *PN; 27594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner for (BasicBlock::iterator I = L->getHeader()->begin(); 27694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner (PN = dyn_cast<PHINode>(I++)); ) 277618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier if (Value *V = SimplifyInstruction(PN, 0, 0, DT)) { 27867fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (AA) AA->deleteValue(PN); 279f73b99ab43c36b026a03430a30c329a343cdd77bChris Lattner if (SE) SE->forgetValue(PN); 28067fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->replaceAllUsesWith(V); 28167fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->eraseFromParent(); 28267fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands } 28394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner 2845cd8770412f98f6e6416c439e01222b3643b9e22Bob Wilson // If this loop has multiple exits and the exits all go to the same 2854b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // block, attempt to merge the exits. This helps several passes, such 2864b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // as LoopRotation, which do not support loops with multiple exits. 2874b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // SimplifyCFG also does this (and this code uses the same utility 2884b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // function), however this code is loop-aware, where SimplifyCFG is 2894b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // not. That gives it the advantage of being able to hoist 2904b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // loop-invariant instructions out of the way to open up more 2914b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // opportunities, and the disadvantage of having the responsibility 2924b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to preserve dominator information. 293b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman bool UniqueExit = true; 294b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (!ExitBlocks.empty()) 295b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 296b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (ExitBlocks[i] != ExitBlocks[0]) { 297b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman UniqueExit = false; 298b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman break; 299b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman } 300b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman if (UniqueExit) { 3014b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 3024b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BasicBlock *ExitingBlock = ExitingBlocks[i]; 3034b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!ExitingBlock->getSinglePredecessor()) continue; 3044b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 3054b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!BI || !BI->isConditional()) continue; 3064b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 3074b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!CI || CI->getParent() != ExitingBlock) continue; 3084b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3094b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Attempt to hoist out all instructions except for the 3104b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // comparison and the branch. 3114b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman bool AllInvariant = true; 3122aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 3134b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Instruction *Inst = I++; 314689fac02268929b756086753b4656d6dabc5cf2dDevang Patel // Skip debug info intrinsics. 315689fac02268929b756086753b4656d6dabc5cf2dDevang Patel if (isa<DbgInfoIntrinsic>(Inst)) 316689fac02268929b756086753b4656d6dabc5cf2dDevang Patel continue; 3172aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman if (Inst == CI) 3184b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman continue; 319f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->makeLoopInvariant(Inst, Changed, 320f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman Preheader ? Preheader->getTerminator() : 0)) { 3214b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman AllInvariant = false; 3224b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman break; 3234b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3244b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3254b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!AllInvariant) continue; 3264b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3274b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // The block has now been cleared of all instructions except for 3284b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // a comparison and a conditional branch. SimplifyCFG may be able 3294b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // to fold it now. 3304b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman if (!FoldBranchToCommonDest(BI)) continue; 3314b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3324b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman // Success. The block is now dead, so remove it from the loop, 333301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich // update the dominator tree and delete it. 3349fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " 3359fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << ExitingBlock->getName() << "\n"); 336c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 3371009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // If any reachable control flow within this loop has changed, notify 3381009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // ScalarEvolution. Currently assume the parent loop doesn't change 3391009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // (spliting edges doesn't count). If blocks, CFG edges, or other values 3401009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // in the parent loop change, then we need call to forgetLoop() for the 3411009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick // parent instead. 3421009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick if (SE) 3431009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick SE->forgetLoop(L); 3441009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick 3454b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 3464b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Changed = true; 347a1baee20c4b042eca1f182fc003f38ab52efc7a9Dan Gohman LI->removeBlock(ExitingBlock); 3484b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3494b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DomTreeNode *Node = DT->getNode(ExitingBlock); 3504b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 3514b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman Node->getChildren(); 3525184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman while (!Children.empty()) { 3535184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DomTreeNode *Child = Children.front(); 3545184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman DT->changeImmediateDominator(Child, Node->getIDom()); 3554b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3564b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman DT->eraseNode(ExitingBlock); 3574b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 3584b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(0)->removePredecessor(ExitingBlock); 3594b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman BI->getSuccessor(1)->removePredecessor(ExitingBlock); 3604b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman ExitingBlock->eraseFromParent(); 3614b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3624b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman } 3634b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 36438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 36538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 36638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 367dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 368dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 369dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 370dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 371fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal FinkelBasicBlock *llvm::InsertPreheaderForLoop(Loop *L, Pass *PP) { 372dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 373dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 374dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 37554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OutsideBlocks; 376dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 3779672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif PI != PE; ++PI) { 3789672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 3799672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (!L->contains(P)) { // Coming in from outside the loop? 380f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // If the loop is branched to from an indirect branch, we won't 381f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // be able to fully transform the loop, because it prohibits 382f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // edge splitting. 3839672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (isa<IndirectBrInst>(P->getTerminator())) return 0; 384f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 385f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Keep track of it. 3869672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif OutsideBlocks.push_back(P); 387f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 3889672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 389fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 390c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner // Split out the loop pre-header. 3917d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman BasicBlock *PreheaderBB; 3927d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman if (!Header->isLandingPad()) { 3937d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", 394fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel PP); 3957d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman } else { 3967d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman SmallVector<BasicBlock*, 2> NewBBs; 397cd1142ef7f9ed5a570da8b332ba481061eb6fcb6Andrew Trick SplitLandingPadPredecessors(Header, OutsideBlocks, ".preheader", 398fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel ".split-lp", PP, NewBBs); 3997d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PreheaderBB = NewBBs[0]; 4007d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman } 4019f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 4027d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PreheaderBB->getTerminator()->setDebugLoc( 4037d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman Header->getFirstNonPHI()->getDebugLoc()); 4047d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman DEBUG(dbgs() << "LoopSimplify: Creating pre-header " 4057d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman << PreheaderBB->getName() << "\n"); 406c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 407120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 408120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 4097d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman PlaceSplitBlockCarefully(PreheaderBB, OutsideBlocks, L); 4100df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman 4117d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman return PreheaderBB; 412dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 413dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 414529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 415529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks. This method is used to split exit blocks that have predecessors 416529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop. 41759fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 41854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> LoopBlocks; 4199672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { 4209672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *I; 4219672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (L->contains(P)) { 422f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Don't do this if the loop is exited via an indirect branch. 4239672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (isa<IndirectBrInst>(P->getTerminator())) return 0; 424f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 4259672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif LoopBlocks.push_back(P); 426f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 4279672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 428dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 4297e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 430b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling BasicBlock *NewExitBB = 0; 431b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling 432b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling if (Exit->isLandingPad()) { 433b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling SmallVector<BasicBlock*, 2> NewBBs; 434b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling SplitLandingPadPredecessors(Exit, ArrayRef<BasicBlock*>(&LoopBlocks[0], 435b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling LoopBlocks.size()), 436b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling ".loopexit", ".nonloopexit", 437b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling this, NewBBs); 438b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling NewExitBB = NewBBs[0]; 439b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling } else { 4402fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", this); 441b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling } 4427e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 4439fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " 444b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling << NewExitBB->getName() << "\n"); 445b29ec0642153c4b820d3814d30ddd33e763076f2Bill Wendling return NewExitBB; 4462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 448529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 449529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 450529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 45158d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 452529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 45358d7fbf250659246fcca9417a91170a681b1850aDevang Patel std::vector<BasicBlock *> WorkList; 45458d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(InputBB); 45558d7fbf250659246fcca9417a91170a681b1850aDevang Patel do { 45658d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 45758d7fbf250659246fcca9417a91170a681b1850aDevang Patel if (Blocks.insert(BB).second && BB != StopBlock) 45858d7fbf250659246fcca9417a91170a681b1850aDevang Patel // If BB is not already processed and it is not a stop block then 45958d7fbf250659246fcca9417a91170a681b1850aDevang Patel // insert its predecessor in the work list 46058d7fbf250659246fcca9417a91170a681b1850aDevang Patel for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 46158d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *WBB = *I; 46258d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(WBB); 46358d7fbf250659246fcca9417a91170a681b1850aDevang Patel } 46458d7fbf250659246fcca9417a91170a681b1850aDevang Patel } while(!WorkList.empty()); 465529b28da455a703d226a31a03400e6662ff569feChris Lattner} 466529b28da455a703d226a31a03400e6662ff569feChris Lattner 4671f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 4681f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops. 469dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 470d0c6f3dafd7c3e9137d4e6415014c94137fcd3fcDuncan Sands AliasAnalysis *AA, LoopInfo *LI) { 471200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 472200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 4731f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 474618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier if (Value *V = SimplifyInstruction(PN, 0, 0, DT)) { 47567fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands // This is a degenerate PHI already, don't modify it! 47667fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->replaceAllUsesWith(V); 47767fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands if (AA) AA->deleteValue(PN); 47867fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands PN->eraseFromParent(); 47967fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands continue; 48067fb341f8b0a72ca0da8ce53baa3f335c1310a85Duncan Sands } 481c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 482c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 483c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 484c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 485c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 486c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 487c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4881f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4891f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4901f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4911f62f82b05563df9c83094608de24ea581014d1eChris Lattner 492120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 493120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block. This prevents the preheader from 494120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated. 495fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkelvoid PlaceSplitBlockCarefully(BasicBlock *NewBB, 496fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel SmallVectorImpl<BasicBlock*> &SplitPreds, 497fc32605ff3a2a922362d2fb5cd31b47ce47e3fb8Hal Finkel Loop *L) { 498120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Check to see if NewBB is already well placed. 499120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = NewBB; --BBI; 500120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 501120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (&*BBI == SplitPreds[i]) 502120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner return; 503120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 5041c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 505120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If it isn't already after an outside block, move it after one. This is 506120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // always good as it makes the uncond branch from the outside block into a 507120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // fall-through. 5081c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 509120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Figure out *which* outside block to put this after. Prefer an outside 510120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // block that neighbors a BB actually in the loop. 511120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner BasicBlock *FoundBB = 0; 512120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 513120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = SplitPreds[i]; 5141c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick if (++BBI != NewBB->getParent()->end() && 515120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner L->contains(BBI)) { 516120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[i]; 517120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner break; 518120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 519120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 5201c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 521120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If our heuristic for a *good* bb to place this after doesn't find 522120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // anything, just pick something. It's likely better than leaving it within 523120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // the loop. 524120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (!FoundBB) 525120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[0]; 526120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner NewBB->moveAfter(FoundBB); 527120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner} 528120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 529120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 530529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 531529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 532529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 533529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 534529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 535529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 536529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 537529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 538529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 539529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 540529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 541529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 542529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 543529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 544529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 545529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 546529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 5477d1ff37118d5b3febae818676d9dd9513057fed7Eli FriedmanLoop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM, 5487d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman BasicBlock *Preheader) { 5497edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick // Don't try to separate loops without a preheader. 5507d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman if (!Preheader) 5517d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman return 0; 5527d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman 5537d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman // The header is not a landing pad; preheader insertion should ensure this. 5547d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman assert(!L->getHeader()->isLandingPad() && 5557d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman "Can't insert backedge to landing pad"); 5567d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman 557d0c6f3dafd7c3e9137d4e6415014c94137fcd3fcDuncan Sands PHINode *PN = FindPHIToPartitionLoops(L, DT, AA, LI); 5581f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 559529b28da455a703d226a31a03400e6662ff569feChris Lattner 5601f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 5611f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 5621f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 56354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner SmallVector<BasicBlock*, 8> OuterLoopPreds; 5647edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 5651f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 5667edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick !L->contains(PN->getIncomingBlock(i))) { 5677edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick // We can't split indirectbr edges. 5687edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator())) 5697edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick return 0; 5701f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 5717edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick } 5727edc277f7214837d3b7cc382350ea1eb968d09aaAndrew Trick } 573c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); 574c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 575ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // If ScalarEvolution is around and knows anything about values in 576ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // this loop, tell it to forget them, because we're about to 577ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman // substantially change it. 578ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman if (SE) 579ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman SE->forgetLoop(L); 580ffa75cdcf82ef2034249a313b9276eaa1bee6c43Dan Gohman 5814b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 5822fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak BasicBlock *NewBB = 5832fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", this); 584529b28da455a703d226a31a03400e6662ff569feChris Lattner 585120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 586120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 587120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 5881c3ff6595f944c2c9b834895e41c78c9c922f4afAndrew Trick 589529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 590529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 591529b28da455a703d226a31a03400e6662ff569feChris Lattner 592529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 593529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 594529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 595529b28da455a703d226a31a03400e6662ff569feChris Lattner else 596c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeTopLevelLoop(L, NewOuter); 597529b28da455a703d226a31a03400e6662ff569feChris Lattner 598529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 599529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 600529b28da455a703d226a31a03400e6662ff569feChris Lattner 601d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Add the new loop to the pass manager queue. 602d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman LPM.insertLoopIntoQueue(NewOuter); 603d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 6049b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 6059b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) 6069b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman NewOuter->addBlockEntry(*I); 607529b28da455a703d226a31a03400e6662ff569feChris Lattner 6085c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Now reset the header in L, which had been moved by 6095c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // SplitBlockPredecessors for the outer loop. 6105c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman L->moveToHeader(Header); 6115c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 612529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 613529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 614529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 6159672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { 6169672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif BasicBlock *P = *PI; 6179672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif if (DT->dominates(Header, P)) 6189672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif AddBlockAndPredsToSet(P, Header, BlocksInL); 6199672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif } 620529b28da455a703d226a31a03400e6662ff569feChris Lattner 621529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 622529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 623c08fa28897356be54fba724056c3aa91da8b3e39David Greene const std::vector<Loop*> &SubLoops = L->getSubLoops(); 624c08fa28897356be54fba724056c3aa91da8b3e39David Greene for (size_t I = 0; I != SubLoops.size(); ) 625c08fa28897356be54fba724056c3aa91da8b3e39David Greene if (BlocksInL.count(SubLoops[I]->getHeader())) 626529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 627529b28da455a703d226a31a03400e6662ff569feChris Lattner else 628c08fa28897356be54fba724056c3aa91da8b3e39David Greene NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 629529b28da455a703d226a31a03400e6662ff569feChris Lattner 630529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 631529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 632529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 633529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 634529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 635529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 636529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 637c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if ((*LI)[BB] == L) 638c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeLoopFor(BB, NewOuter); 639529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 640529b28da455a703d226a31a03400e6662ff569feChris Lattner } 641529b28da455a703d226a31a03400e6662ff569feChris Lattner } 642529b28da455a703d226a31a03400e6662ff569feChris Lattner 643529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 644529b28da455a703d226a31a03400e6662ff569feChris Lattner} 645529b28da455a703d226a31a03400e6662ff569feChris Lattner 646529b28da455a703d226a31a03400e6662ff569feChris Lattner 647529b28da455a703d226a31a03400e6662ff569feChris Lattner 6482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 6492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 6502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 6512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 6522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 653f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanBasicBlock * 654f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanLoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 6552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 6562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 6582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 6592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 6602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 661f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Unique backedge insertion currently depends on having a preheader. 662f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!Preheader) 663f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return 0; 664f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 6657d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman // The header is not a landing pad; preheader insertion should ensure this. 6667d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman assert(!Header->isLandingPad() && "Can't insert backedge to landing pad"); 6677d1ff37118d5b3febae818676d9dd9513057fed7Eli Friedman 6682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 6692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 670bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ 671bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif BasicBlock *P = *I; 672c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman 673c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman // Indirectbr edges cannot be split, so we must fail if we find one. 674c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman if (isa<IndirectBrInst>(P->getTerminator())) 675c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman return 0; 676c2f40066bbceb15e73e5c4df97d2d115f8a36e58Dan Gohman 677bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif if (P != Preheader) BackedgeBlocks.push_back(P); 678bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif } 6792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 6811d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 6821d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Header->getName()+".backedge", F); 683051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 6842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6859fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block " 6869fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner << BEBlock->getName() << "\n"); 687c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman 6882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 6892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 6902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 691fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 6932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 694200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 695200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 6963ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(), 6973ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PN->getName()+".be", BETerminator); 698cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPN); 6992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 7012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 7022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 7032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 7042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 7052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 7062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 7072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 7082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 7092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 7102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 7112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 7122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 7132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 7142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 7152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 7162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 7172ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 720fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 7212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 7222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 7232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 7242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 7252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 7262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7275551706b0f8e970720deea0bf6aa34116030d6beChris Lattner // Nuke all entries except the zero'th. 7285551706b0f8e970720deea0bf6aa34116030d6beChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 7295551706b0f8e970720deea0bf6aa34116030d6beChris Lattner PN->removeIncomingValue(e-i, false); 7302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 7322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 7332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 7352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 7362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 7372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 7382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 739cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(NewPN); 7402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 7412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 745280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky // backedge blocks to just to the BEBlock instead of the header. 7462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 7472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 7482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 7492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 7502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 7512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 7522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 7542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 7562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 757d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson L->addBasicBlockToLoop(BEBlock, LI->getBase()); 7582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 7590e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update dominator information 7600e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(BEBlock); 761f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 762f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman return BEBlock; 763f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman} 764f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 765f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohmanvoid LoopSimplify::verifyAnalysis() const { 766f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // It used to be possible to just assert L->isLoopSimplifyForm(), however 767f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // with the introduction of indirectbr, there are now cases where it's 768f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // not possible to transform a loop as necessary. We can at least check 769f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // that there is an indirectbr near any time there's trouble. 770f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 771f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman // Indirectbr can interfere with preheader and unique backedge insertion. 772f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->getLoopPreheader() || !L->getLoopLatch()) { 773f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrPred = false; 774f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman for (pred_iterator PI = pred_begin(L->getHeader()), 775f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman PE = pred_end(L->getHeader()); PI != PE; ++PI) 776f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((*PI)->getTerminator())) { 777f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrPred = true; 778f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 779f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 780f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman assert(HasIndBrPred && 781f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing loop header info!"); 7821f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)HasIndBrPred; 783f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 784f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman 78566af89f642628c0d52138e86f9e4a0b9f5994474Bill Wendling // Indirectbr can interfere with exit block canonicalization. 786f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (!L->hasDedicatedExits()) { 787f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman bool HasIndBrExiting = false; 788f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman SmallVector<BasicBlock*, 8> ExitingBlocks; 789f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman L->getExitingBlocks(ExitingBlocks); 7900906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 791f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 792f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman HasIndBrExiting = true; 793f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman break; 794f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 7950906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling } 7960906a7c46cfc71e7c09dd6362df4310e72fdbc6bBill Wendling 79766af89f642628c0d52138e86f9e4a0b9f5994474Bill Wendling assert(HasIndBrExiting && 798f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman "LoopSimplify has no excuse for missing exit block info!"); 79966af89f642628c0d52138e86f9e4a0b9f5994474Bill Wendling (void)HasIndBrExiting; 800f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman } 80138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 802