1198892Srdivacky//===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===// 2198892Srdivacky// 3198892Srdivacky// The LLVM Compiler Infrastructure 4198892Srdivacky// 5198892Srdivacky// This file is distributed under the University of Illinois Open Source 6198892Srdivacky// License. See LICENSE.TXT for details. 7198892Srdivacky// 8198892Srdivacky//===----------------------------------------------------------------------===// 9198892Srdivacky// 10198892Srdivacky// This file implements some loop unrolling utilities. It does not define any 11198892Srdivacky// actual pass or policy, but provides a single function to perform loop 12198892Srdivacky// unrolling. 13198892Srdivacky// 14198892Srdivacky// The process of unrolling can produce extraneous basic blocks linked with 15198892Srdivacky// unconditional branches. This will be corrected in the future. 16218893Sdim// 17198892Srdivacky//===----------------------------------------------------------------------===// 18198892Srdivacky 19198892Srdivacky#define DEBUG_TYPE "loop-unroll" 20198892Srdivacky#include "llvm/Transforms/Utils/UnrollLoop.h" 21198892Srdivacky#include "llvm/ADT/Statistic.h" 22218893Sdim#include "llvm/Analysis/InstructionSimplify.h" 23226633Sdim#include "llvm/Analysis/LoopIterator.h" 24198892Srdivacky#include "llvm/Analysis/LoopPass.h" 25212904Sdim#include "llvm/Analysis/ScalarEvolution.h" 26249423Sdim#include "llvm/IR/BasicBlock.h" 27198892Srdivacky#include "llvm/Support/Debug.h" 28198892Srdivacky#include "llvm/Support/raw_ostream.h" 29198892Srdivacky#include "llvm/Transforms/Utils/BasicBlockUtils.h" 30198892Srdivacky#include "llvm/Transforms/Utils/Cloning.h" 31198892Srdivacky#include "llvm/Transforms/Utils/Local.h" 32226633Sdim#include "llvm/Transforms/Utils/SimplifyIndVar.h" 33198892Srdivackyusing namespace llvm; 34198892Srdivacky 35198892Srdivacky// TODO: Should these be here or in LoopUnroll? 36198892SrdivackySTATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled"); 37218893SdimSTATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)"); 38198892Srdivacky 39198892Srdivacky/// RemapInstruction - Convert the instruction operands from referencing the 40210299Sed/// current values into those specified by VMap. 41198892Srdivackystatic inline void RemapInstruction(Instruction *I, 42218893Sdim ValueToValueMapTy &VMap) { 43198892Srdivacky for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { 44198892Srdivacky Value *Op = I->getOperand(op); 45218893Sdim ValueToValueMapTy::iterator It = VMap.find(Op); 46210299Sed if (It != VMap.end()) 47198892Srdivacky I->setOperand(op, It->second); 48198892Srdivacky } 49224145Sdim 50224145Sdim if (PHINode *PN = dyn_cast<PHINode>(I)) { 51224145Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 52224145Sdim ValueToValueMapTy::iterator It = VMap.find(PN->getIncomingBlock(i)); 53224145Sdim if (It != VMap.end()) 54224145Sdim PN->setIncomingBlock(i, cast<BasicBlock>(It->second)); 55224145Sdim } 56224145Sdim } 57198892Srdivacky} 58198892Srdivacky 59198892Srdivacky/// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it 60198892Srdivacky/// only has one predecessor, and that predecessor only has one successor. 61198892Srdivacky/// The LoopInfo Analysis that is passed will be kept consistent. 62198892Srdivacky/// Returns the new combined block. 63226633Sdimstatic BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, 64226633Sdim LPPassManager *LPM) { 65198892Srdivacky // Merge basic blocks into their predecessor if there is only one distinct 66198892Srdivacky // pred, and if there is only one distinct successor of the predecessor, and 67198892Srdivacky // if there are no PHI nodes. 68198892Srdivacky BasicBlock *OnlyPred = BB->getSinglePredecessor(); 69198892Srdivacky if (!OnlyPred) return 0; 70198892Srdivacky 71198892Srdivacky if (OnlyPred->getTerminator()->getNumSuccessors() != 1) 72198892Srdivacky return 0; 73198892Srdivacky 74202375Srdivacky DEBUG(dbgs() << "Merging: " << *BB << "into: " << *OnlyPred); 75198892Srdivacky 76198892Srdivacky // Resolve any PHI nodes at the start of the block. They are all 77198892Srdivacky // guaranteed to have exactly one entry if they exist, unless there are 78198892Srdivacky // multiple duplicate (but guaranteed to be equal) entries for the 79198892Srdivacky // incoming edges. This occurs when there are multiple edges from 80198892Srdivacky // OnlyPred to OnlySucc. 81198892Srdivacky FoldSingleEntryPHINodes(BB); 82198892Srdivacky 83198892Srdivacky // Delete the unconditional branch from the predecessor... 84198892Srdivacky OnlyPred->getInstList().pop_back(); 85198892Srdivacky 86198892Srdivacky // Make all PHI nodes that referred to BB now refer to Pred as their 87198892Srdivacky // source... 88198892Srdivacky BB->replaceAllUsesWith(OnlyPred); 89198892Srdivacky 90224145Sdim // Move all definitions in the successor to the predecessor... 91224145Sdim OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 92224145Sdim 93263508Sdim // OldName will be valid until erased. 94263508Sdim StringRef OldName = BB->getName(); 95198892Srdivacky 96198892Srdivacky // Erase basic block from the function... 97226633Sdim 98226633Sdim // ScalarEvolution holds references to loop exit blocks. 99239462Sdim if (LPM) { 100239462Sdim if (ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>()) { 101239462Sdim if (Loop *L = LI->getLoopFor(BB)) 102239462Sdim SE->forgetLoop(L); 103239462Sdim } 104226633Sdim } 105198892Srdivacky LI->removeBlock(BB); 106198892Srdivacky 107198892Srdivacky // Inherit predecessor's name if it exists... 108198892Srdivacky if (!OldName.empty() && !OnlyPred->hasName()) 109198892Srdivacky OnlyPred->setName(OldName); 110198892Srdivacky 111263508Sdim BB->eraseFromParent(); 112263508Sdim 113198892Srdivacky return OnlyPred; 114198892Srdivacky} 115198892Srdivacky 116198892Srdivacky/// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true 117218893Sdim/// if unrolling was successful, or false if the loop was unmodified. Unrolling 118198892Srdivacky/// can only fail when the loop's latch block is not terminated by a conditional 119198892Srdivacky/// branch instruction. However, if the trip count (and multiple) are not known, 120198892Srdivacky/// loop unrolling will mostly produce more code that is no faster. 121198892Srdivacky/// 122226633Sdim/// TripCount is generally defined as the number of times the loop header 123226633Sdim/// executes. UnrollLoop relaxes the definition to permit early exits: here 124226633Sdim/// TripCount is the iteration on which control exits LatchBlock if no early 125226633Sdim/// exits were taken. Note that UnrollLoop assumes that the loop counter test 126226633Sdim/// terminates LatchBlock in order to remove unnecesssary instances of the 127226633Sdim/// test. In other words, control may exit the loop prior to TripCount 128226633Sdim/// iterations via an early branch, but control may not exit the loop from the 129226633Sdim/// LatchBlock's terminator prior to TripCount iterations. 130226633Sdim/// 131226633Sdim/// Similarly, TripMultiple divides the number of times that the LatchBlock may 132226633Sdim/// execute without exiting the loop. 133226633Sdim/// 134198892Srdivacky/// The LoopInfo Analysis that is passed will be kept consistent. 135198892Srdivacky/// 136198892Srdivacky/// If a LoopPassManager is passed in, and the loop is fully removed, it will be 137198892Srdivacky/// removed from the LoopPassManager as well. LPM can also be NULL. 138226633Sdim/// 139226633Sdim/// This utility preserves LoopInfo. If DominatorTree or ScalarEvolution are 140226633Sdim/// available it must also preserve those analyses. 141226633Sdimbool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, 142234353Sdim bool AllowRuntime, unsigned TripMultiple, 143234353Sdim LoopInfo *LI, LPPassManager *LPM) { 144199481Srdivacky BasicBlock *Preheader = L->getLoopPreheader(); 145199481Srdivacky if (!Preheader) { 146202375Srdivacky DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n"); 147199481Srdivacky return false; 148199481Srdivacky } 149199481Srdivacky 150199481Srdivacky BasicBlock *LatchBlock = L->getLoopLatch(); 151199481Srdivacky if (!LatchBlock) { 152202375Srdivacky DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n"); 153199481Srdivacky return false; 154199481Srdivacky } 155199481Srdivacky 156234353Sdim // Loops with indirectbr cannot be cloned. 157234353Sdim if (!L->isSafeToClone()) { 158234353Sdim DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n"); 159234353Sdim return false; 160234353Sdim } 161234353Sdim 162198892Srdivacky BasicBlock *Header = L->getHeader(); 163198892Srdivacky BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator()); 164226633Sdim 165198892Srdivacky if (!BI || BI->isUnconditional()) { 166198892Srdivacky // The loop-rotate pass can be helpful to avoid this in many cases. 167202375Srdivacky DEBUG(dbgs() << 168198892Srdivacky " Can't unroll; loop not terminated by a conditional branch.\n"); 169198892Srdivacky return false; 170198892Srdivacky } 171226633Sdim 172218893Sdim if (Header->hasAddressTaken()) { 173218893Sdim // The loop-rotate pass can be helpful to avoid this in many cases. 174218893Sdim DEBUG(dbgs() << 175218893Sdim " Won't unroll loop: address of header block is taken.\n"); 176218893Sdim return false; 177218893Sdim } 178198892Srdivacky 179198892Srdivacky if (TripCount != 0) 180202375Srdivacky DEBUG(dbgs() << " Trip Count = " << TripCount << "\n"); 181198892Srdivacky if (TripMultiple != 1) 182202375Srdivacky DEBUG(dbgs() << " Trip Multiple = " << TripMultiple << "\n"); 183198892Srdivacky 184198892Srdivacky // Effectively "DCE" unrolled iterations that are beyond the tripcount 185198892Srdivacky // and will never be executed. 186198892Srdivacky if (TripCount != 0 && Count > TripCount) 187198892Srdivacky Count = TripCount; 188198892Srdivacky 189234353Sdim // Don't enter the unroll code if there is nothing to do. This way we don't 190234353Sdim // need to support "partial unrolling by 1". 191234353Sdim if (TripCount == 0 && Count < 2) 192234353Sdim return false; 193234353Sdim 194198892Srdivacky assert(Count > 0); 195198892Srdivacky assert(TripMultiple > 0); 196198892Srdivacky assert(TripCount == 0 || TripCount % TripMultiple == 0); 197198892Srdivacky 198198892Srdivacky // Are we eliminating the loop control altogether? 199198892Srdivacky bool CompletelyUnroll = Count == TripCount; 200198892Srdivacky 201234353Sdim // We assume a run-time trip count if the compiler cannot 202234353Sdim // figure out the loop trip count and the unroll-runtime 203234353Sdim // flag is specified. 204234353Sdim bool RuntimeTripCount = (TripCount == 0 && Count > 0 && AllowRuntime); 205234353Sdim 206234353Sdim if (RuntimeTripCount && !UnrollRuntimeLoopProlog(L, Count, LI, LPM)) 207234353Sdim return false; 208234353Sdim 209234353Sdim // Notify ScalarEvolution that the loop will be substantially changed, 210234353Sdim // if not outright eliminated. 211239462Sdim if (LPM) { 212239462Sdim ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>(); 213239462Sdim if (SE) 214239462Sdim SE->forgetLoop(L); 215239462Sdim } 216234353Sdim 217198892Srdivacky // If we know the trip count, we know the multiple... 218198892Srdivacky unsigned BreakoutTrip = 0; 219198892Srdivacky if (TripCount != 0) { 220198892Srdivacky BreakoutTrip = TripCount % Count; 221198892Srdivacky TripMultiple = 0; 222198892Srdivacky } else { 223198892Srdivacky // Figure out what multiple to use. 224198892Srdivacky BreakoutTrip = TripMultiple = 225198892Srdivacky (unsigned)GreatestCommonDivisor64(Count, TripMultiple); 226198892Srdivacky } 227198892Srdivacky 228198892Srdivacky if (CompletelyUnroll) { 229202375Srdivacky DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName() 230198892Srdivacky << " with trip count " << TripCount << "!\n"); 231198892Srdivacky } else { 232202375Srdivacky DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() 233198892Srdivacky << " by " << Count); 234198892Srdivacky if (TripMultiple == 0 || BreakoutTrip != TripMultiple) { 235202375Srdivacky DEBUG(dbgs() << " with a breakout at trip " << BreakoutTrip); 236198892Srdivacky } else if (TripMultiple != 1) { 237202375Srdivacky DEBUG(dbgs() << " with " << TripMultiple << " trips per branch"); 238234353Sdim } else if (RuntimeTripCount) { 239234353Sdim DEBUG(dbgs() << " with run-time trip count"); 240198892Srdivacky } 241202375Srdivacky DEBUG(dbgs() << "!\n"); 242198892Srdivacky } 243198892Srdivacky 244198892Srdivacky bool ContinueOnTrue = L->contains(BI->getSuccessor(0)); 245198892Srdivacky BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue); 246198892Srdivacky 247198892Srdivacky // For the first iteration of the loop, we should use the precloned values for 248198892Srdivacky // PHI nodes. Insert associations now. 249207618Srdivacky ValueToValueMapTy LastValueMap; 250198892Srdivacky std::vector<PHINode*> OrigPHINode; 251198892Srdivacky for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 252226633Sdim OrigPHINode.push_back(cast<PHINode>(I)); 253198892Srdivacky } 254198892Srdivacky 255198892Srdivacky std::vector<BasicBlock*> Headers; 256198892Srdivacky std::vector<BasicBlock*> Latches; 257198892Srdivacky Headers.push_back(Header); 258198892Srdivacky Latches.push_back(LatchBlock); 259198892Srdivacky 260226633Sdim // The current on-the-fly SSA update requires blocks to be processed in 261226633Sdim // reverse postorder so that LastValueMap contains the correct value at each 262226633Sdim // exit. 263226633Sdim LoopBlocksDFS DFS(L); 264226633Sdim DFS.perform(LI); 265226633Sdim 266226633Sdim // Stash the DFS iterators before adding blocks to the loop. 267226633Sdim LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO(); 268226633Sdim LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO(); 269226633Sdim 270198892Srdivacky for (unsigned It = 1; It != Count; ++It) { 271198892Srdivacky std::vector<BasicBlock*> NewBlocks; 272226633Sdim 273226633Sdim for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { 274210299Sed ValueToValueMapTy VMap; 275210299Sed BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It)); 276198892Srdivacky Header->getParent()->getBasicBlockList().push_back(New); 277198892Srdivacky 278198892Srdivacky // Loop over all of the PHI nodes in the block, changing them to use the 279198892Srdivacky // incoming values from the previous block. 280198892Srdivacky if (*BB == Header) 281198892Srdivacky for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { 282210299Sed PHINode *NewPHI = cast<PHINode>(VMap[OrigPHINode[i]]); 283198892Srdivacky Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock); 284198892Srdivacky if (Instruction *InValI = dyn_cast<Instruction>(InVal)) 285201360Srdivacky if (It > 1 && L->contains(InValI)) 286198892Srdivacky InVal = LastValueMap[InValI]; 287210299Sed VMap[OrigPHINode[i]] = InVal; 288198892Srdivacky New->getInstList().erase(NewPHI); 289198892Srdivacky } 290198892Srdivacky 291198892Srdivacky // Update our running map of newest clones 292198892Srdivacky LastValueMap[*BB] = New; 293210299Sed for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end(); 294198892Srdivacky VI != VE; ++VI) 295198892Srdivacky LastValueMap[VI->first] = VI->second; 296198892Srdivacky 297198892Srdivacky L->addBasicBlockToLoop(New, LI->getBase()); 298198892Srdivacky 299226633Sdim // Add phi entries for newly created values to all exit blocks. 300226633Sdim for (succ_iterator SI = succ_begin(*BB), SE = succ_end(*BB); 301226633Sdim SI != SE; ++SI) { 302226633Sdim if (L->contains(*SI)) 303226633Sdim continue; 304226633Sdim for (BasicBlock::iterator BBI = (*SI)->begin(); 305226633Sdim PHINode *phi = dyn_cast<PHINode>(BBI); ++BBI) { 306226633Sdim Value *Incoming = phi->getIncomingValueForBlock(*BB); 307226633Sdim ValueToValueMapTy::iterator It = LastValueMap.find(Incoming); 308226633Sdim if (It != LastValueMap.end()) 309226633Sdim Incoming = It->second; 310226633Sdim phi->addIncoming(Incoming, New); 311226633Sdim } 312226633Sdim } 313198892Srdivacky // Keep track of new headers and latches as we create them, so that 314198892Srdivacky // we can insert the proper branches later. 315198892Srdivacky if (*BB == Header) 316198892Srdivacky Headers.push_back(New); 317226633Sdim if (*BB == LatchBlock) 318198892Srdivacky Latches.push_back(New); 319198892Srdivacky 320198892Srdivacky NewBlocks.push_back(New); 321198892Srdivacky } 322226633Sdim 323198892Srdivacky // Remap all instructions in the most recent iteration 324198892Srdivacky for (unsigned i = 0; i < NewBlocks.size(); ++i) 325198892Srdivacky for (BasicBlock::iterator I = NewBlocks[i]->begin(), 326198892Srdivacky E = NewBlocks[i]->end(); I != E; ++I) 327218893Sdim ::RemapInstruction(I, LastValueMap); 328198892Srdivacky } 329198892Srdivacky 330226633Sdim // Loop over the PHI nodes in the original block, setting incoming values. 331226633Sdim for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { 332226633Sdim PHINode *PN = OrigPHINode[i]; 333226633Sdim if (CompletelyUnroll) { 334198892Srdivacky PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader)); 335198892Srdivacky Header->getInstList().erase(PN); 336198892Srdivacky } 337226633Sdim else if (Count > 1) { 338226633Sdim Value *InVal = PN->removeIncomingValue(LatchBlock, false); 339226633Sdim // If this value was defined in the loop, take the value defined by the 340226633Sdim // last iteration of the loop. 341226633Sdim if (Instruction *InValI = dyn_cast<Instruction>(InVal)) { 342226633Sdim if (L->contains(InValI)) 343226633Sdim InVal = LastValueMap[InVal]; 344226633Sdim } 345226633Sdim assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch"); 346226633Sdim PN->addIncoming(InVal, Latches.back()); 347226633Sdim } 348198892Srdivacky } 349198892Srdivacky 350198892Srdivacky // Now that all the basic blocks for the unrolled iterations are in place, 351198892Srdivacky // set up the branches to connect them. 352198892Srdivacky for (unsigned i = 0, e = Latches.size(); i != e; ++i) { 353198892Srdivacky // The original branch was replicated in each unrolled iteration. 354198892Srdivacky BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator()); 355198892Srdivacky 356198892Srdivacky // The branch destination. 357198892Srdivacky unsigned j = (i + 1) % e; 358198892Srdivacky BasicBlock *Dest = Headers[j]; 359198892Srdivacky bool NeedConditional = true; 360198892Srdivacky 361234353Sdim if (RuntimeTripCount && j != 0) { 362234353Sdim NeedConditional = false; 363234353Sdim } 364234353Sdim 365198892Srdivacky // For a complete unroll, make the last iteration end with a branch 366198892Srdivacky // to the exit block. 367198892Srdivacky if (CompletelyUnroll && j == 0) { 368198892Srdivacky Dest = LoopExit; 369198892Srdivacky NeedConditional = false; 370198892Srdivacky } 371198892Srdivacky 372198892Srdivacky // If we know the trip count or a multiple of it, we can safely use an 373198892Srdivacky // unconditional branch for some iterations. 374198892Srdivacky if (j != BreakoutTrip && (TripMultiple == 0 || j % TripMultiple != 0)) { 375198892Srdivacky NeedConditional = false; 376198892Srdivacky } 377198892Srdivacky 378198892Srdivacky if (NeedConditional) { 379198892Srdivacky // Update the conditional branch's successor for the following 380198892Srdivacky // iteration. 381198892Srdivacky Term->setSuccessor(!ContinueOnTrue, Dest); 382198892Srdivacky } else { 383226633Sdim // Remove phi operands at this loop exit 384226633Sdim if (Dest != LoopExit) { 385226633Sdim BasicBlock *BB = Latches[i]; 386226633Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 387226633Sdim SI != SE; ++SI) { 388226633Sdim if (*SI == Headers[i]) 389226633Sdim continue; 390226633Sdim for (BasicBlock::iterator BBI = (*SI)->begin(); 391226633Sdim PHINode *Phi = dyn_cast<PHINode>(BBI); ++BBI) { 392226633Sdim Phi->removeIncomingValue(BB, false); 393226633Sdim } 394226633Sdim } 395226633Sdim } 396218893Sdim // Replace the conditional branch with an unconditional one. 397218893Sdim BranchInst::Create(Dest, Term); 398218893Sdim Term->eraseFromParent(); 399224145Sdim } 400224145Sdim } 401224145Sdim 402224145Sdim // Merge adjacent basic blocks, if possible. 403224145Sdim for (unsigned i = 0, e = Latches.size(); i != e; ++i) { 404224145Sdim BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator()); 405224145Sdim if (Term->isUnconditional()) { 406224145Sdim BasicBlock *Dest = Term->getSuccessor(0); 407226633Sdim if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM)) 408198892Srdivacky std::replace(Latches.begin(), Latches.end(), Dest, Fold); 409198892Srdivacky } 410198892Srdivacky } 411226633Sdim 412239462Sdim if (LPM) { 413239462Sdim // FIXME: Reconstruct dom info, because it is not preserved properly. 414239462Sdim // Incrementally updating domtree after loop unrolling would be easy. 415239462Sdim if (DominatorTree *DT = LPM->getAnalysisIfAvailable<DominatorTree>()) 416239462Sdim DT->runOnFunction(*L->getHeader()->getParent()); 417226633Sdim 418239462Sdim // Simplify any new induction variables in the partially unrolled loop. 419239462Sdim ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>(); 420239462Sdim if (SE && !CompletelyUnroll) { 421239462Sdim SmallVector<WeakVH, 16> DeadInsts; 422239462Sdim simplifyLoopIVs(L, SE, LPM, DeadInsts); 423226633Sdim 424239462Sdim // Aggressively clean up dead instructions that simplifyLoopIVs already 425239462Sdim // identified. Any remaining should be cleaned up below. 426239462Sdim while (!DeadInsts.empty()) 427239462Sdim if (Instruction *Inst = 428239462Sdim dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 429239462Sdim RecursivelyDeleteTriviallyDeadInstructions(Inst); 430239462Sdim } 431226633Sdim } 432198892Srdivacky // At this point, the code is well formed. We now do a quick sweep over the 433198892Srdivacky // inserted code, doing constant propagation and dead code elimination as we 434198892Srdivacky // go. 435198892Srdivacky const std::vector<BasicBlock*> &NewLoopBlocks = L->getBlocks(); 436198892Srdivacky for (std::vector<BasicBlock*>::const_iterator BB = NewLoopBlocks.begin(), 437198892Srdivacky BBE = NewLoopBlocks.end(); BB != BBE; ++BB) 438198892Srdivacky for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) { 439198892Srdivacky Instruction *Inst = I++; 440198892Srdivacky 441198892Srdivacky if (isInstructionTriviallyDead(Inst)) 442198892Srdivacky (*BB)->getInstList().erase(Inst); 443218893Sdim else if (Value *V = SimplifyInstruction(Inst)) 444218893Sdim if (LI->replacementPreservesLCSSAForm(Inst, V)) { 445218893Sdim Inst->replaceAllUsesWith(V); 446218893Sdim (*BB)->getInstList().erase(Inst); 447218893Sdim } 448198892Srdivacky } 449198892Srdivacky 450198892Srdivacky NumCompletelyUnrolled += CompletelyUnroll; 451198892Srdivacky ++NumUnrolled; 452198892Srdivacky // Remove the loop from the LoopPassManager if it's completely removed. 453198892Srdivacky if (CompletelyUnroll && LPM != NULL) 454198892Srdivacky LPM->deleteLoopFromQueue(L); 455198892Srdivacky 456198892Srdivacky return true; 457198892Srdivacky} 458