1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This pass performs several transformations to transform natural loops into a 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// simpler form, which makes subsequent analyses and transformations simpler and 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// more effective. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Loop pre-header insertion guarantees that there is a single, non-critical 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// entry edge from outside of the loop to the loop header. This simplifies a 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// number of analyses and transformations, such as LICM. 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Loop exit-block insertion guarantees that all exit blocks from the loop 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// (blocks which are outside of the loop that have predecessors inside of the 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// loop) only have predecessors from inside of the loop (and are thus dominated 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// by the loop header). This simplifies transformations such as store-sinking 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// that are built into LICM. 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This pass also guarantees that loops will have exactly one backedge. 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Indirectbr instructions introduce several complications. If the loop 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// contains or is entered by an indirectbr instruction, it may not be possible 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// to transform the loop and make these guarantees. Client code should check 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// that these conditions are true before relying on them. 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Note that the simplifycfg pass will clean up blocks which are split out but 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// end up being unnecessary, so usage of this pass should not pessimize 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// generated code. 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This pass obviously modifies the CFG, but updates loop information and 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// dominator information. 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "loop-simplify" 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Scalar.h" 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Constants.h" 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/IntrinsicInst.h" 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/LLVMContext.h" 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Type.h" 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/AliasAnalysis.h" 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/Dominators.h" 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/InstructionSimplify.h" 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/LoopPass.h" 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/ScalarEvolution.h" 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/Local.h" 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CFG.h" 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SetOperations.h" 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SetVector.h" 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/Statistic.h" 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DepthFirstIterator.h" 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumNested , "Number of nested loops split out"); 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct LoopSimplify : public LoopPass { 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopSimplify() : LoopPass(ID) { 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeLoopSimplifyPass(*PassRegistry::getPassRegistry()); 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // AA - If we have an alias analysis object to update, this is it, otherwise 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this is null. 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasAnalysis *AA; 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopInfo *LI; 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominatorTree *DT; 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ScalarEvolution *SE; 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *L; 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We need loop information to identify the loops... 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<DominatorTree>(); 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<DominatorTree>(); 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<LoopInfo>(); 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<LoopInfo>(); 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<AliasAnalysis>(); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<ScalarEvolution>(); 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void verifyAnalysis() const; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool ProcessLoop(Loop *L, LPPassManager &LPM); 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *InsertPreheaderForLoop(Loop *L); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void PlaceSplitBlockCarefully(BasicBlock *NewBB, 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<BasicBlock*> &SplitPreds, 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *L); 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar LoopSimplify::ID = 0; 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Canonicalize natural loops", true, false) 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(DominatorTree) 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(LoopInfo) 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(LoopSimplify, "loop-simplify", 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Canonicalize natural loops", true, false) 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Publicly exposed interface to pass... 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar &llvm::LoopSimplifyID = LoopSimplify::ID; 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// runOnLoop - Run down all loops in the CFG (recursively, but we could do 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// it in any convenient order) inserting preheaders... 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L = l; 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LI = &getAnalysis<LoopInfo>(); 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AA = getAnalysisIfAvailable<AliasAnalysis>(); 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DT = &getAnalysis<DominatorTree>(); 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE = getAnalysisIfAvailable<ScalarEvolution>(); 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed |= ProcessLoop(L, LPM); 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// all loops have preheaders. 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanReprocessLoop: 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see that no blocks (other than the header) in this loop have 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // predecessors that are not in the loop. This is not valid for natural 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // loops, but can occur if the blocks are unreachable. Since they are 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // unreachable we can just shamelessly delete those CFG edges! 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB != E; ++BB) { 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*BB == L->getHeader()) continue; 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<BasicBlock*, 4> BadPreds; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI = pred_begin(*BB), 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PE = pred_end(*BB); PI != PE; ++PI) { 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *P = *PI; 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->contains(P)) 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BadPreds.insert(P); 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete each unique out-of-loop (and thus dead) predecessor. 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(), 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = BadPreds.end(); I != E; ++I) { 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << (*I)->getName() << "\n"); 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Inform each successor of each dead pred. 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (*SI)->removePredecessor(*I); 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Zap the dead pred's terminator and replace it with unreachable. 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TerminatorInst *TI = (*I)->getTerminator(); 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (*I)->getTerminator()->eraseFromParent(); 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new UnreachableInst((*I)->getContext(), *I); 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there are exiting blocks with branches on undef, resolve the undef in 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the direction which will exit the loop. This will help simplify loop 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // trip count computations. 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> ExitingBlocks; 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->getExitingBlocks(ExitingBlocks); 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(), 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = ExitingBlocks.end(); I != E; ++I) 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator())) 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BI->isConditional()) { 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) { 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in " 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << (*I)->getName() << "\n"); 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BI->setCondition(ConstantInt::get(Cond->getType(), 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !L->contains(BI->getSuccessor(0)))); 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Does the loop already have a preheader? If so, don't insert one. 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Preheader = L->getLoopPreheader(); 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Preheader) { 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Preheader = InsertPreheaderForLoop(L); 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Preheader) { 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumInserted; 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Next, check to make sure that all exit nodes of the loop only have 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // predecessors that are inside of the loop. This check guarantees that the 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // loop preheader/header will dominate the exit blocks. If the exit block has 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // predecessors from outside of the loop, split the edge now. 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> ExitBlocks; 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->getExitBlocks(ExitBlocks); 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExitBlocks.end()); 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(), 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = ExitBlockSet.end(); I != E; ++I) { 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *ExitBlock = *I; 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI != PE; ++PI) 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Must be exactly this loop: no subloops, parent loops, or non-loop preds 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // allowed. 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->contains(*PI)) { 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (RewriteLoopExitBlock(L, ExitBlock)) { 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumInserted; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the header has more than two predecessors at this point (from the 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // preheader and from multiple backedges), we must adjust the loop. 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *LoopLatch = L->getLoopLatch(); 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LoopLatch) { 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is really a nested loop, rip it out into a child loop. Don't do 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this for loops with a giant number of backedges, just factor them into a 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // common backedge instead. 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (L->getNumBackEdges() < 8) { 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SeparateNestedLoop(L, LPM)) { 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumNested; 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is a big restructuring change, reprocess the whole loop. 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // GCC doesn't tail recursion eliminate this. 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto ReprocessLoop; 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we either couldn't, or didn't want to, identify nesting of the loops, 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // insert a new block that all backedges target, then make it jump to the 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // loop header. 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LoopLatch) { 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumInserted; 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan over the PHI nodes in the loop header. Since they now have only two 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // incoming values (the loop is canonicalized), we may have simplified the PHI 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN; 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = L->getHeader()->begin(); 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (PN = dyn_cast<PHINode>(I++)); ) 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = SimplifyInstruction(PN, 0, DT)) { 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AA) AA->deleteValue(PN); 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SE) SE->forgetValue(PN); 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->replaceAllUsesWith(V); 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->eraseFromParent(); 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this loop has multiple exits and the exits all go to the same 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block, attempt to merge the exits. This helps several passes, such 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // as LoopRotation, which do not support loops with multiple exits. 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // SimplifyCFG also does this (and this code uses the same utility 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // function), however this code is loop-aware, where SimplifyCFG is 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not. That gives it the advantage of being able to hoist 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // loop-invariant instructions out of the way to open up more 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // opportunities, and the disadvantage of having the responsibility 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to preserve dominator information. 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool UniqueExit = true; 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!ExitBlocks.empty()) 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ExitBlocks[i] != ExitBlocks[0]) { 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UniqueExit = false; 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UniqueExit) { 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *ExitingBlock = ExitingBlocks[i]; 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!ExitingBlock->getSinglePredecessor()) continue; 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BI || !BI->isConditional()) continue; 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!CI || CI->getParent() != ExitingBlock) continue; 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Attempt to hoist out all instructions except for the 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // comparison and the branch. 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool AllInvariant = true; 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *Inst = I++; 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Skip debug info intrinsics. 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<DbgInfoIntrinsic>(Inst)) 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Inst == CI) 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->makeLoopInvariant(Inst, Changed, 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Preheader ? Preheader->getTerminator() : 0)) { 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllInvariant = false; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!AllInvariant) continue; 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The block has now been cleared of all instructions except for 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // a comparison and a conditional branch. SimplifyCFG may be able 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to fold it now. 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!FoldBranchToCommonDest(BI)) continue; 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Success. The block is now dead, so remove it from the loop, 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // update the dominator tree and delete it. 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << ExitingBlock->getName() << "\n"); 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If any reachable control flow within this loop has changed, notify 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ScalarEvolution. Currently assume the parent loop doesn't change 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // (spliting edges doesn't count). If blocks, CFG edges, or other values 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // in the parent loop change, then we need call to forgetLoop() for the 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // parent instead. 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SE) 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE->forgetLoop(L); 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LI->removeBlock(ExitingBlock); 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DomTreeNode *Node = DT->getNode(ExitingBlock); 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node->getChildren(); 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!Children.empty()) { 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DomTreeNode *Child = Children.front(); 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DT->changeImmediateDominator(Child, Node->getIDom()); 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DT->eraseNode(ExitingBlock); 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BI->getSuccessor(0)->removePredecessor(ExitingBlock); 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BI->getSuccessor(1)->removePredecessor(ExitingBlock); 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExitingBlock->eraseFromParent(); 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// preheader, this method is called to insert one. This method has two phases: 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// preheader insertion and analysis updating. 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Header = L->getHeader(); 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute the set of predecessors of the loop that are not in the loop. 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> OutsideBlocks; 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI != PE; ++PI) { 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *P = *PI; 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->contains(P)) { // Coming in from outside the loop? 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the loop is branched to from an indirect branch, we won't 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // be able to fully transform the loop, because it prohibits 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // edge splitting. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<IndirectBrInst>(P->getTerminator())) return 0; 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Keep track of it. 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OutsideBlocks.push_back(P); 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Split out the loop pre-header. 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *NewBB = 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ".preheader", this); 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewBB->getTerminator()->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc()); 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "LoopSimplify: Creating pre-header " << NewBB->getName() 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << "\n"); 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make sure that NewBB is put someplace intelligent, which doesn't mess up 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // code layout too horribly. 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NewBB; 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// blocks. This method is used to split exit blocks that have predecessors 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// outside of the loop. 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> LoopBlocks; 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *P = *I; 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (L->contains(P)) { 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't do this if the loop is exited via an indirect branch. 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<IndirectBrInst>(P->getTerminator())) return 0; 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopBlocks.push_back(P); 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *NewExitBB = 0; 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Exit->isLandingPad()) { 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<BasicBlock*, 2> NewBBs; 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitLandingPadPredecessors(Exit, ArrayRef<BasicBlock*>(&LoopBlocks[0], 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopBlocks.size()), 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ".loopexit", ".nonloopexit", 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this, NewBBs); 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewExitBB = NewBBs[0]; 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewExitBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopBlocks.size(), ".loopexit", 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this); 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << NewExitBB->getName() << "\n"); 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NewExitBB; 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// AddBlockAndPredsToSet - Add the specified block, and all of its 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// predecessors, to the specified set, if it's not already in there. Stop 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// predecessor traversal when we reach StopBlock. 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::set<BasicBlock*> &Blocks) { 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<BasicBlock *> WorkList; 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WorkList.push_back(InputBB); 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Blocks.insert(BB).second && BB != StopBlock) 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If BB is not already processed and it is not a stop block then 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // insert its predecessor in the work list 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *WBB = *I; 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WorkList.push_back(WBB); 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while(!WorkList.empty()); 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PHI node that tells us how to partition the loops. 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasAnalysis *AA, LoopInfo *LI) { 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN = cast<PHINode>(I); 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++I; 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = SimplifyInstruction(PN, 0, DT)) { 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is a degenerate PHI already, don't modify it! 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->replaceAllUsesWith(V); 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AA) AA->deleteValue(PN); 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->eraseFromParent(); 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan this PHI node looking for a use of the PHI node by itself. 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PN->getIncomingValue(i) == PN && 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->contains(PN->getIncomingBlock(i))) 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We found something tasty to remove. 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return PN; 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// right after some 'outside block' block. This prevents the preheader from 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// being placed inside the loop body, e.g. when the loop hasn't been rotated. 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<BasicBlock*> &SplitPreds, 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *L) { 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if NewBB is already well placed. 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function::iterator BBI = NewBB; --BBI; 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (&*BBI == SplitPreds[i]) 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 48919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it isn't already after an outside block, move it after one. This is 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // always good as it makes the uncond branch from the outside block into a 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // fall-through. 49319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out *which* outside block to put this after. Prefer an outside 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block that neighbors a BB actually in the loop. 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *FoundBB = 0; 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function::iterator BBI = SplitPreds[i]; 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (++BBI != NewBB->getParent()->end() && 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->contains(BBI)) { 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundBB = SplitPreds[i]; 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If our heuristic for a *good* bb to place this after doesn't find 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // anything, just pick something. It's likely better than leaving it within 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the loop. 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!FoundBB) 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundBB = SplitPreds[0]; 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewBB->moveAfter(FoundBB); 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// them out into a nested loop. This is important for code that looks like 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// this: 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Loop: 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ... 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// br cond, Loop, Next 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ... 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// br cond2, Loop, Out 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// To identify this common case, we look at the PHI nodes in the header of the 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// loop. PHI nodes with unchanging values on one backedge correspond to values 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// that change in the "outer" loop, but not in the "inner" loop. 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// If we are able to separate out a loop, return the new outer loop that was 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// created. 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanLoop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { 53319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PHINode *PN = FindPHIToPartitionLoops(L, DT, AA, LI); 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PN == 0) return 0; // No known way to partition. 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Pull out all predecessors that have varying values in the loop. This 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // handles the case when a PHI node has multiple instances of itself as 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // arguments. 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> OuterLoopPreds; 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PN->getIncomingValue(i) != PN || 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !L->contains(PN->getIncomingBlock(i))) { 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We can't split indirectbr edges. 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator())) 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If ScalarEvolution is around and knows anything about values in 55319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // this loop, tell it to forget them, because we're about to 55419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // substantially change it. 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SE) 55619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE->forgetLoop(L); 55719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Header = L->getHeader(); 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OuterLoopPreds.size(), 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ".outer", this); 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make sure that NewBB is put someplace intelligent, which doesn't mess up 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // code layout too horribly. 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 56619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create the new outer loop. 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *NewOuter = new Loop(); 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Change the parent loop to use the outer loop as its child now. 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Loop *Parent = L->getParentLoop()) 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Parent->replaceChildLoopWith(L, NewOuter); 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LI->changeTopLevelLoop(L, NewOuter); 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // L is now a subloop of our outer loop. 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewOuter->addChildLoop(L); 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add the new loop to the pass manager queue. 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LPM.insertLoopIntoQueue(NewOuter); 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I != E; ++I) 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewOuter->addBlockEntry(*I); 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now reset the header in L, which had been moved by 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // SplitBlockPredecessors for the outer loop. 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->moveToHeader(Header); 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Determine which blocks should stay in L and which should be moved out to 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the Outer loop now. 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::set<BasicBlock*> BlocksInL; 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *P = *PI; 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DT->dominates(Header, P)) 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddBlockAndPredsToSet(P, Header, BlocksInL); 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan all of the loop children of L, moving them to OuterLoop if they are 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not part of the inner loop. 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const std::vector<Loop*> &SubLoops = L->getSubLoops(); 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (size_t I = 0; I != SubLoops.size(); ) 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BlocksInL.count(SubLoops[I]->getHeader())) 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++I; // Loop remains in L 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we know which blocks are in L and which need to be moved to 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // OuterLoop, move any blocks that need it. 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BB = L->getBlocks()[i]; 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BlocksInL.count(BB)) { 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move this block to the parent, updating the exit blocks sets 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->removeBlockFromLoop(BB); 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((*LI)[BB] == L) 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LI->changeLoopFor(BB, NewOuter); 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --i; 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NewOuter; 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// InsertUniqueBackedgeBlock - This method is called when the specified loop 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// has more than one backedge in it. If this occurs, revector all of these 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// backedges to target a new basic block and have that block branch to the loop 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// header. This ensures that loops have exactly one backedge. 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicBlock * 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanLoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Get information about the loop 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Header = L->getHeader(); 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = Header->getParent(); 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Unique backedge insertion currently depends on having a preheader. 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Preheader) 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which basic blocks contain back-edges to the loop header. 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<BasicBlock*> BackedgeBlocks; 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *P = *I; 64719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Indirectbr edges cannot be split, so we must fail if we find one. 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<IndirectBrInst>(P->getTerminator())) 65019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 65119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (P != Preheader) BackedgeBlocks.push_back(P); 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create and insert the new backedge block... 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header->getName()+".backedge", F); 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block " 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << BEBlock->getName() << "\n"); 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move the new backedge block to right after the last backedge block. 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that the block has been inserted into the function, create PHI nodes in 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the backedge block which correspond to any PHI nodes in the header block. 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN = cast<PHINode>(I); 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(), 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PN->getName()+".be", BETerminator); 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AA) AA->copyValue(PN, NewPN); 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Loop over the PHI node, moving all entries except the one for the 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // preheader over to the new PHI node. 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned PreheaderIdx = ~0U; 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool HasUniqueIncomingValue = true; 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *UniqueValue = 0; 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *IBB = PN->getIncomingBlock(i); 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *IV = PN->getIncomingValue(i); 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IBB == Preheader) { 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PreheaderIdx = i; 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewPN->addIncoming(IV, IBB); 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HasUniqueIncomingValue) { 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UniqueValue == 0) 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UniqueValue = IV; 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (UniqueValue != IV) 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HasUniqueIncomingValue = false; 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete all of the incoming values from the old PN except the preheader's 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PreheaderIdx != 0) { 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Nuke all entries except the zero'th. 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->removeIncomingValue(e-i, false); 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Finally, add the newly constructed PHI node as the entry for the BEBlock. 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->addIncoming(NewPN, BEBlock); 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // As an optimization, if all incoming values in the new PhiNode (which is a 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // subset of the incoming values of the old PHI node) have the same value, 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // eliminate the PHI Node. 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HasUniqueIncomingValue) { 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewPN->replaceAllUsesWith(UniqueValue); 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AA) AA->deleteValue(NewPN); 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BEBlock->getInstList().erase(NewPN); 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 717894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 718894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 719894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that all of the PHI nodes have been inserted and adjusted, modify the 720894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // backedge blocks to just to the BEBlock instead of the header. 721894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TI->getSuccessor(Op) == Header) 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TI->setSuccessor(Op, BEBlock); 726894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 727894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 728894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //===--- Update all analyses which we must preserve now -----------------===// 729894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 730894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update Loop Information - we know that this block is now in the current 731894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // loop and all parent loops. 732894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->addBasicBlockToLoop(BEBlock, LI->getBase()); 733894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 734894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update dominator information 735894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DT->splitBlock(BEBlock); 736894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 737894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BEBlock; 738894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 739894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 740894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LoopSimplify::verifyAnalysis() const { 741894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It used to be possible to just assert L->isLoopSimplifyForm(), however 742894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // with the introduction of indirectbr, there are now cases where it's 743894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not possible to transform a loop as necessary. We can at least check 744894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that there is an indirectbr near any time there's trouble. 745894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 746894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Indirectbr can interfere with preheader and unique backedge insertion. 747894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->getLoopPreheader() || !L->getLoopLatch()) { 748894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool HasIndBrPred = false; 749894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI = pred_begin(L->getHeader()), 750894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PE = pred_end(L->getHeader()); PI != PE; ++PI) 751894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<IndirectBrInst>((*PI)->getTerminator())) { 752894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HasIndBrPred = true; 753894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 754894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 755894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(HasIndBrPred && 756894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "LoopSimplify has no excuse for missing loop header info!"); 75719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)HasIndBrPred; 758894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 759894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 760894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Indirectbr can interfere with exit block canonicalization. 761894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->hasDedicatedExits()) { 762894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool HasIndBrExiting = false; 763894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> ExitingBlocks; 764894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->getExitingBlocks(ExitingBlocks); 76519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 766894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 767894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HasIndBrExiting = true; 768894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 769894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 77019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 772894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(HasIndBrExiting && 773894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "LoopSimplify has no excuse for missing exit block info!"); 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)HasIndBrExiting; 775894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 776894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 777