1218893Sdim//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10193326Sed// This file defines the LoopInfo class that is used to identify natural loops 11193326Sed// and determine the loop depth of various nodes of the CFG. Note that the 12193326Sed// loops identified may actually be several natural loops that share the same 13193326Sed// header node... not just a single natural loop. 14193326Sed// 15198893Srdivacky//===----------------------------------------------------------------------===// 16198893Srdivacky 17193326Sed#include "llvm/Analysis/LoopInfo.h" 18193326Sed#include "llvm/ADT/DepthFirstIterator.h" 19193326Sed#include "llvm/ADT/SmallPtrSet.h" 20199512Srdivacky#include "llvm/Analysis/Dominators.h" 21193326Sed#include "llvm/Analysis/LoopInfoImpl.h" 22193326Sed#include "llvm/Analysis/LoopIterator.h" 23239462Sdim#include "llvm/Analysis/ValueTracking.h" 24193326Sed#include "llvm/Assembly/Writer.h" 25198092Srdivacky#include "llvm/IR/Constants.h" 26198893Srdivacky#include "llvm/IR/Instructions.h" 27198092Srdivacky#include "llvm/IR/Metadata.h" 28218893Sdim#include "llvm/Support/CFG.h" 29193326Sed#include "llvm/Support/CommandLine.h" 30193326Sed#include "llvm/Support/Debug.h" 31218893Sdim#include <algorithm> 32218893Sdimusing namespace llvm; 33224145Sdim 34193326Sed// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. 35193326Sedtemplate class llvm::LoopBase<BasicBlock, Loop>; 36243830Sdimtemplate class llvm::LoopInfoBase<BasicBlock, Loop>; 37193326Sed 38193326Sed// Always verify loopinfo if expensive checking is enabled. 39193326Sed#ifdef XDEBUG 40193326Sedstatic bool VerifyLoopInfo = true; 41226633Sdim#else 42193326Sedstatic bool VerifyLoopInfo = false; 43198092Srdivacky#endif 44198092Srdivackystatic cl::opt<bool,true> 45198092SrdivackyVerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), 46198092Srdivacky cl::desc("Verify loop info (time consuming)")); 47221345Sdim 48226633Sdimchar LoopInfo::ID = 0; 49198092SrdivackyINITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) 50198092SrdivackyINITIALIZE_PASS_DEPENDENCY(DominatorTree) 51198092SrdivackyINITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true) 52198092Srdivacky 53198092Srdivacky// Loop identifier metadata name. 54198092Srdivackystatic const char *const LoopMDName = "llvm.loop"; 55198092Srdivacky 56198092Srdivacky//===----------------------------------------------------------------------===// 57198092Srdivacky// Loop implementation 58198092Srdivacky// 59226633Sdim 60198092Srdivacky/// isLoopInvariant - Return true if the specified value is loop invariant 61198092Srdivacky/// 62198092Srdivackybool Loop::isLoopInvariant(Value *V) const { 63206084Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 64206084Srdivacky return !contains(I); 65226633Sdim return true; // All non-instructions are loop invariant 66226633Sdim} 67206084Srdivacky 68206084Srdivacky/// hasLoopInvariantOperands - Return true if all the operands of the 69206084Srdivacky/// specified instruction are loop invariant. 70206084Srdivackybool Loop::hasLoopInvariantOperands(Instruction *I) const { 71206084Srdivacky for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 72206084Srdivacky if (!isLoopInvariant(I->getOperand(i))) 73206084Srdivacky return false; 74206084Srdivacky 75206084Srdivacky return true; 76206084Srdivacky} 77206084Srdivacky 78206084Srdivacky/// makeLoopInvariant - If the given value is an instruciton inside of the 79206084Srdivacky/// loop and it can be hoisted, do so to make it trivially loop-invariant. 80206084Srdivacky/// Return true if the value after any hoisting is loop invariant. This 81206084Srdivacky/// function can be used as a slightly more aggressive replacement for 82206084Srdivacky/// isLoopInvariant. 83206084Srdivacky/// 84206084Srdivacky/// If InsertPt is specified, it is the point to hoist instructions to. 85206084Srdivacky/// If null, the terminator of the loop preheader is used. 86206084Srdivacky/// 87206084Srdivackybool Loop::makeLoopInvariant(Value *V, bool &Changed, 88206084Srdivacky Instruction *InsertPt) const { 89206084Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 90206084Srdivacky return makeLoopInvariant(I, Changed, InsertPt); 91206084Srdivacky return true; // All non-instructions are loop-invariant. 92234353Sdim} 93234353Sdim 94234353Sdim/// makeLoopInvariant - If the given instruction is inside of the 95234353Sdim/// loop and it can be hoisted, do so to make it trivially loop-invariant. 96234353Sdim/// Return true if the instruction after any hoisting is loop invariant. This 97243830Sdim/// function can be used as a slightly more aggressive replacement for 98243830Sdim/// isLoopInvariant. 99234353Sdim/// 100234353Sdim/// If InsertPt is specified, it is the point to hoist instructions to. 101234353Sdim/// If null, the terminator of the loop preheader is used. 102243830Sdim/// 103243830Sdimbool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 104243830Sdim Instruction *InsertPt) const { 105243830Sdim // Test if the value is already loop-invariant. 106234353Sdim if (isLoopInvariant(I)) 107234353Sdim return true; 108234353Sdim if (!isSafeToSpeculativelyExecute(I)) 109234353Sdim return false; 110234353Sdim if (I->mayReadFromMemory()) 111234353Sdim return false; 112234353Sdim // The landingpad instruction is immobile. 113243830Sdim if (isa<LandingPadInst>(I)) 114243830Sdim return false; 115243830Sdim // Determine the insertion point, unless one was given. 116243830Sdim if (!InsertPt) { 117243830Sdim BasicBlock *Preheader = getLoopPreheader(); 118243830Sdim // Without a preheader, hoisting is not feasible. 119234353Sdim if (!Preheader) 120243830Sdim return false; 121243830Sdim InsertPt = Preheader->getTerminator(); 122243830Sdim } 123243830Sdim // Don't hoist instructions with loop-variant operands. 124243830Sdim for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 125243830Sdim if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 126234353Sdim return false; 127234353Sdim 128234353Sdim // Hoist. 129234353Sdim I->moveBefore(InsertPt); 130234353Sdim Changed = true; 131243830Sdim return true; 132243830Sdim} 133243830Sdim 134243830Sdim/// getCanonicalInductionVariable - Check to see if the loop has a canonical 135243830Sdim/// induction variable: an integer recurrence that starts at 0 and increments 136243830Sdim/// by one each time through the loop. If so, return the phi node that 137234353Sdim/// corresponds to it. 138243830Sdim/// 139243830Sdim/// The IndVarSimplify pass transforms loops to have a canonical induction 140243830Sdim/// variable. 141243830Sdim/// 142243830SdimPHINode *Loop::getCanonicalInductionVariable() const { 143243830Sdim BasicBlock *H = getHeader(); 144234353Sdim 145234353Sdim BasicBlock *Incoming = 0, *Backedge = 0; 146234353Sdim pred_iterator PI = pred_begin(H); 147218893Sdim assert(PI != pred_end(H) && 148218893Sdim "Loop must have at least one backedge!"); 149218893Sdim Backedge = *PI++; 150218893Sdim if (PI == pred_end(H)) return 0; // dead loop 151218893Sdim Incoming = *PI++; 152218893Sdim if (PI != pred_end(H)) return 0; // multiple backedges? 153218893Sdim 154218893Sdim if (contains(Incoming)) { 155218893Sdim if (contains(Backedge)) 156218893Sdim return 0; 157218893Sdim std::swap(Incoming, Backedge); 158218893Sdim } else if (!contains(Backedge)) 159218893Sdim return 0; 160218893Sdim 161218893Sdim // Loop over all of the PHI nodes, looking for a canonical indvar. 162218893Sdim for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 163218893Sdim PHINode *PN = cast<PHINode>(I); 164218893Sdim if (ConstantInt *CI = 165218893Sdim dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 166226633Sdim if (CI->isNullValue()) 167218893Sdim if (Instruction *Inc = 168218893Sdim dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 169218893Sdim if (Inc->getOpcode() == Instruction::Add && 170218893Sdim Inc->getOperand(0) == PN) 171218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 172218893Sdim if (CI->equalsInt(1)) 173218893Sdim return PN; 174218893Sdim } 175218893Sdim return 0; 176218893Sdim} 177218893Sdim 178218893Sdim/// isLCSSAForm - Return true if the Loop is in LCSSA form 179218893Sdimbool Loop::isLCSSAForm(DominatorTree &DT) const { 180218893Sdim for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 181218893Sdim BasicBlock *BB = *BI; 182218893Sdim for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 183218893Sdim for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 184218893Sdim ++UI) { 185218893Sdim User *U = *UI; 186218893Sdim BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 187234353Sdim if (PHINode *P = dyn_cast<PHINode>(U)) 188234353Sdim UserBB = P->getIncomingBlock(UI); 189234353Sdim 190218893Sdim // Check the current block, as a fast-path, before checking whether 191218893Sdim // the use is anywhere in the loop. Most values are used in the same 192224145Sdim // block they are defined in. Also, blocks not reachable from the 193224145Sdim // entry are special; uses in them don't need to go through PHIs. 194224145Sdim if (UserBB != BB && 195224145Sdim !contains(UserBB) && 196224145Sdim DT.isReachableFromEntry(UserBB)) 197224145Sdim return false; 198234353Sdim } 199234353Sdim } 200239462Sdim 201239462Sdim return true; 202234353Sdim} 203239462Sdim 204234353Sdim/// isLoopSimplifyForm - Return true if the Loop is in the form that 205234353Sdim/// the LoopSimplify form transforms loops to, which is sometimes called 206234353Sdim/// normal form. 207223017Sdimbool Loop::isLoopSimplifyForm() const { 208224145Sdim // Normal-form loops have a preheader, a single backedge, and all of their 209224145Sdim // exits have all their predecessors inside the loop. 210224145Sdim return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 211224145Sdim} 212224145Sdim 213224145Sdim/// isSafeToClone - Return true if the loop body is safe to clone in practice. 214224145Sdim/// Routines that reform the loop CFG and split edges often fail on indirectbr. 215224145Sdimbool Loop::isSafeToClone() const { 216224145Sdim // Return false if any loop blocks contain indirectbrs, or there are any calls 217224145Sdim // to noduplicate functions. 218224145Sdim for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) { 219224145Sdim if (isa<IndirectBrInst>((*I)->getTerminator())) 220234353Sdim return false; 221234353Sdim 222224145Sdim if (const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator())) 223224145Sdim if (II->hasFnAttr(Attribute::NoDuplicate)) 224223017Sdim return false; 225223017Sdim 226243830Sdim for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { 227243830Sdim if (const CallInst *CI = dyn_cast<CallInst>(BI)) { 228243830Sdim if (CI->hasFnAttr(Attribute::NoDuplicate)) 229243830Sdim return false; 230243830Sdim } 231243830Sdim } 232234353Sdim } 233234353Sdim return true; 234193326Sed} 235193326Sed 236193326SedMDNode *Loop::getLoopID() const { 237193326Sed MDNode *LoopID = 0; 238194179Sed if (isLoopSimplifyForm()) { 239194179Sed LoopID = getLoopLatch()->getTerminator()->getMetadata(LoopMDName); 240198092Srdivacky } else { 241194179Sed // Go through each predecessor of the loop header and check the 242198092Srdivacky // terminator for the metadata. 243198092Srdivacky BasicBlock *H = getHeader(); 244198092Srdivacky for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { 245193326Sed TerminatorInst *TI = (*I)->getTerminator(); 246218893Sdim MDNode *MD = 0; 247193326Sed 248193326Sed // Check if this terminator branches to the loop header. 249193326Sed for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { 250193326Sed if (TI->getSuccessor(i) == H) { 251241163Sdim MD = TI->getMetadata(LoopMDName); 252243830Sdim break; 253234353Sdim } 254241163Sdim } 255241163Sdim if (!MD) 256199512Srdivacky return 0; 257199512Srdivacky 258193326Sed if (!LoopID) 259193326Sed LoopID = MD; 260193326Sed else if (MD != LoopID) 261234353Sdim return 0; 262193326Sed } 263193326Sed } 264193326Sed if (!LoopID || LoopID->getNumOperands() == 0 || 265193326Sed LoopID->getOperand(0) != LoopID) 266206084Srdivacky return 0; 267193326Sed return LoopID; 268193326Sed} 269193326Sed 270193326Sedvoid Loop::setLoopID(MDNode *LoopID) const { 271193326Sed assert(LoopID && "Loop ID should not be null"); 272193326Sed assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand"); 273193326Sed assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself"); 274243830Sdim 275193326Sed if (isLoopSimplifyForm()) { 276193326Sed getLoopLatch()->getTerminator()->setMetadata(LoopMDName, LoopID); 277193326Sed return; 278193326Sed } 279234353Sdim 280218893Sdim BasicBlock *H = getHeader(); 281218893Sdim for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { 282193326Sed TerminatorInst *TI = (*I)->getTerminator(); 283193326Sed for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { 284193326Sed if (TI->getSuccessor(i) == H) 285234353Sdim TI->setMetadata(LoopMDName, LoopID); 286206084Srdivacky } 287206084Srdivacky } 288193326Sed} 289193326Sed 290199512Srdivackybool Loop::isAnnotatedParallel() const { 291199512Srdivacky MDNode *desiredLoopIdMetadata = getLoopID(); 292193326Sed 293193326Sed if (!desiredLoopIdMetadata) 294193326Sed return false; 295224145Sdim 296224145Sdim // The loop branch contains the parallel loop metadata. In order to ensure 297224145Sdim // that any parallel-loop-unaware optimization pass hasn't added loop-carried 298226633Sdim // dependencies (thus converted the loop back to a sequential loop), check 299224145Sdim // that all the memory instructions in the loop contain parallelism metadata 300224145Sdim // that point to the same unique "loop id metadata" the loop branch does. 301224145Sdim for (block_iterator BB = block_begin(), BE = block_end(); BB != BE; ++BB) { 302193326Sed for (BasicBlock::iterator II = (*BB)->begin(), EE = (*BB)->end(); 303193326Sed II != EE; II++) { 304206084Srdivacky 305206084Srdivacky if (!II->mayReadOrWriteMemory()) 306206084Srdivacky continue; 307206084Srdivacky 308210299Sed // The memory instruction can refer to the loop identifier metadata 309210299Sed // directly or indirectly through another list metadata (in case of 310206084Srdivacky // nested parallel loops). The loop identifier metadata refers to 311210299Sed // itself so we can check both cases with the same routine. 312206084Srdivacky MDNode *loopIdMD = II->getMetadata("llvm.mem.parallel_loop_access"); 313234353Sdim 314243830Sdim if (!loopIdMD) 315206084Srdivacky return false; 316206084Srdivacky 317206084Srdivacky bool loopIdMDFound = false; 318206084Srdivacky for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) { 319210299Sed if (loopIdMD->getOperand(i) == desiredLoopIdMetadata) { 320206084Srdivacky loopIdMDFound = true; 321206084Srdivacky break; 322206084Srdivacky } 323193326Sed } 324193326Sed 325193326Sed if (!loopIdMDFound) 326193326Sed return false; 327193326Sed } 328218893Sdim } 329199990Srdivacky return true; 330199990Srdivacky} 331199990Srdivacky 332193326Sed 333193326Sed/// hasDedicatedExits - Return true if no exit block for the loop 334218893Sdim/// has a predecessor that is outside the loop. 335218893Sdimbool Loop::hasDedicatedExits() const { 336218893Sdim // Each predecessor of each exit block of a normal loop is contained 337212904Sdim // within the loop. 338198398Srdivacky SmallVector<BasicBlock *, 4> ExitBlocks; 339198398Srdivacky getExitBlocks(ExitBlocks); 340193326Sed for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 341193326Sed for (pred_iterator PI = pred_begin(ExitBlocks[i]), 342243830Sdim PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 343218893Sdim if (!contains(*PI)) 344198398Srdivacky return false; 345193326Sed // All the requirements are met. 346218893Sdim return true; 347193326Sed} 348198092Srdivacky 349193326Sed/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 350193326Sed/// These are the blocks _outside of the current loop_ which are branched to. 351193326Sed/// This assumes that loop exits are in canonical form. 352193326Sed/// 353193326Sedvoid 354218893SdimLoop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 355193326Sed assert(hasDedicatedExits() && 356193326Sed "getUniqueExitBlocks assumes the loop has canonical form exits!"); 357193326Sed 358198092Srdivacky SmallVector<BasicBlock *, 32> switchExitBlocks; 359198092Srdivacky 360193326Sed for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 361193326Sed 362218893Sdim BasicBlock *current = *BI; 363198398Srdivacky switchExitBlocks.clear(); 364198398Srdivacky 365193326Sed for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { 366198092Srdivacky // If block is inside the loop then it is not a exit block. 367193326Sed if (contains(*I)) 368193326Sed continue; 369193326Sed 370193326Sed pred_iterator PI = pred_begin(*I); 371218893Sdim BasicBlock *firstPred = *PI; 372218893Sdim 373218893Sdim // If current basic block is this exit block's first predecessor 374218893Sdim // then only insert exit block in to the output ExitBlocks vector. 375218893Sdim // This ensures that same exit block is not inserted twice into 376218893Sdim // ExitBlocks vector. 377218893Sdim if (current != firstPred) 378218893Sdim continue; 379218893Sdim 380218893Sdim // If a terminator has more then two successors, for example SwitchInst, 381226633Sdim // then it is possible that there are multiple edges from current block 382218893Sdim // to one exit block. 383218893Sdim if (std::distance(succ_begin(current), succ_end(current)) <= 2) { 384193326Sed ExitBlocks.push_back(*I); 385193326Sed continue; 386193326Sed } 387193326Sed 388193326Sed // In case of multiple edges from current block to exit block, collect 389193326Sed // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 390193326Sed // duplicate edges. 391193326Sed if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 392193326Sed == switchExitBlocks.end()) { 393226633Sdim switchExitBlocks.push_back(*I); 394226633Sdim ExitBlocks.push_back(*I); 395193326Sed } 396193326Sed } 397193326Sed } 398193326Sed} 399193326Sed 400193326Sed/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 401193326Sed/// block, return that block. Otherwise return null. 402193326SedBasicBlock *Loop::getUniqueExitBlock() const { 403193326Sed SmallVector<BasicBlock *, 8> UniqueExitBlocks; 404198893Srdivacky getUniqueExitBlocks(UniqueExitBlocks); 405198893Srdivacky if (UniqueExitBlocks.size() == 1) 406198893Srdivacky return UniqueExitBlocks[0]; 407226633Sdim return 0; 408218893Sdim} 409218893Sdim 410218893Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 411234982Sdimvoid Loop::dump() const { 412234982Sdim print(dbgs()); 413218893Sdim} 414218893Sdim#endif 415234982Sdim 416218893Sdim//===----------------------------------------------------------------------===// 417218893Sdim// UnloopUpdater implementation 418226633Sdim// 419226633Sdim 420226633Sdimnamespace { 421226633Sdim/// Find the new parent loop for all blocks within the "unloop" whose last 422226633Sdim/// backedges has just been removed. 423226633Sdimclass UnloopUpdater { 424226633Sdim Loop *Unloop; 425234353Sdim LoopInfo *LI; 426226633Sdim 427226633Sdim LoopBlocksDFS DFS; 428226633Sdim 429226633Sdim // Map unloop's immediate subloops to their nearest reachable parents. Nested 430226633Sdim // loops within these subloops will not change parents. However, an immediate 431226633Sdim // subloop's new parent will be the nearest loop reachable from either its own 432226633Sdim // exits *or* any of its nested loop's exits. 433226633Sdim DenseMap<Loop*, Loop*> SubloopParents; 434234353Sdim 435234353Sdim // Flag the presence of an irreducible backedge whose destination is a block 436226633Sdim // directly contained by the original unloop. 437226633Sdim bool FoundIB; 438234353Sdim 439226633Sdimpublic: 440234353Sdim UnloopUpdater(Loop *UL, LoopInfo *LInfo) : 441226633Sdim Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {} 442234353Sdim 443226633Sdim void updateBlockParents(); 444234353Sdim 445226633Sdim void removeBlocksFromAncestors(); 446234353Sdim 447228379Sdim void updateSubloopParents(); 448228379Sdim 449228379Sdimprotected: 450228379Sdim Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); 451228379Sdim}; 452228379Sdim} // end anonymous namespace 453228379Sdim 454193326Sed/// updateBlockParents - Update the parent loop for all blocks that are directly 455193326Sed/// contained within the original "unloop". 456239462Sdimvoid UnloopUpdater::updateBlockParents() { 457239462Sdim if (Unloop->getNumBlocks()) { 458239462Sdim // Perform a post order CFG traversal of all blocks within this loop, 459239462Sdim // propagating the nearest loop from sucessors to predecessors. 460239462Sdim LoopBlocksTraversal Traversal(DFS, LI); 461239462Sdim for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 462239462Sdim POE = Traversal.end(); POI != POE; ++POI) { 463239462Sdim 464239462Sdim Loop *L = LI->getLoopFor(*POI); 465239462Sdim Loop *NL = getNearestLoop(*POI, L); 466239462Sdim 467239462Sdim if (NL != L) { 468239462Sdim // For reducible loops, NL is now an ancestor of Unloop. 469239462Sdim assert((NL != Unloop && (!NL || NL->contains(Unloop))) && 470239462Sdim "uninitialized successor"); 471239462Sdim LI->changeLoopFor(*POI, NL); 472239462Sdim } 473239462Sdim else { 474243830Sdim // Or the current block is part of a subloop, in which case its parent 475239462Sdim // is unchanged. 476239462Sdim assert((FoundIB || Unloop->contains(L)) && "uninitialized successor"); 477239462Sdim } 478243830Sdim } 479243830Sdim } 480239462Sdim // Each irreducible loop within the unloop induces a round of iteration using 481239462Sdim // the DFS result cached by Traversal. 482239462Sdim bool Changed = FoundIB; 483221345Sdim for (unsigned NIters = 0; Changed; ++NIters) { 484198092Srdivacky assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"); 485198092Srdivacky 486239462Sdim // Iterate over the postorder list of blocks, propagating the nearest loop 487210299Sed // from successors to predecessors as before. 488198092Srdivacky Changed = false; 489198092Srdivacky for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), 490198092Srdivacky POE = DFS.endPostorder(); POI != POE; ++POI) { 491239462Sdim 492243830Sdim Loop *L = LI->getLoopFor(*POI); 493239462Sdim Loop *NL = getNearestLoop(*POI, L); 494239462Sdim if (NL != L) { 495239462Sdim assert(NL != Unloop && (!NL || NL->contains(Unloop)) && 496239462Sdim "uninitialized successor"); 497239462Sdim LI->changeLoopFor(*POI, NL); 498239462Sdim Changed = true; 499198092Srdivacky } 500226633Sdim } 501198092Srdivacky } 502210299Sed} 503243830Sdim 504210299Sed/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below 505210299Sed/// their new parents. 506210299Sedvoid UnloopUpdater::removeBlocksFromAncestors() { 507198092Srdivacky // Remove all unloop's blocks (including those in nested subloops) from 508198092Srdivacky // ancestors below the new parent loop. 509239462Sdim for (Loop::block_iterator BI = Unloop->block_begin(), 510239462Sdim BE = Unloop->block_end(); BI != BE; ++BI) { 511239462Sdim Loop *OuterParent = LI->getLoopFor(*BI); 512239462Sdim if (Unloop->contains(OuterParent)) { 513239462Sdim while (OuterParent->getParentLoop() != Unloop) 514239462Sdim OuterParent = OuterParent->getParentLoop(); 515239462Sdim OuterParent = SubloopParents[OuterParent]; 516239462Sdim } 517239462Sdim // Remove blocks from former Ancestors except Unloop itself which will be 518239462Sdim // deleted. 519239462Sdim for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent; 520239462Sdim OldParent = OldParent->getParentLoop()) { 521226633Sdim assert(OldParent && "new loop is not an ancestor of the original"); 522226633Sdim OldParent->removeBlockFromLoop(*BI); 523226633Sdim } 524226633Sdim } 525226633Sdim} 526226633Sdim 527239462Sdim/// updateSubloopParents - Update the parent loop for all subloops directly 528226633Sdim/// nested within unloop. 529226633Sdimvoid UnloopUpdater::updateSubloopParents() { 530226633Sdim while (!Unloop->empty()) { 531226633Sdim Loop *Subloop = *llvm::prior(Unloop->end()); 532226633Sdim Unloop->removeChildLoop(llvm::prior(Unloop->end())); 533226633Sdim 534243830Sdim assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); 535243830Sdim if (Loop *Parent = SubloopParents[Subloop]) 536226633Sdim Parent->addChildLoop(Subloop); 537226633Sdim else 538226633Sdim LI->addTopLevelLoop(Subloop); 539226633Sdim } 540226633Sdim} 541226633Sdim 542226633Sdim/// getNearestLoop - Return the nearest parent loop among this block's 543226633Sdim/// successors. If a successor is a subloop header, consider its parent to be 544198092Srdivacky/// the nearest parent of the subloop's exits. 545198092Srdivacky/// 546199482Srdivacky/// For subloop blocks, simply update SubloopParents and return NULL. 547199482SrdivackyLoop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { 548199482Srdivacky 549199482Srdivacky // Initially for blocks directly contained by Unloop, NearLoop == Unloop and 550199482Srdivacky // is considered uninitialized. 551199482Srdivacky Loop *NearLoop = BBLoop; 552223017Sdim 553199482Srdivacky Loop *Subloop = 0; 554199482Srdivacky if (NearLoop != Unloop && Unloop->contains(NearLoop)) { 555226633Sdim Subloop = NearLoop; 556199482Srdivacky // Find the subloop ancestor that is directly contained within Unloop. 557199482Srdivacky while (Subloop->getParentLoop() != Unloop) { 558199482Srdivacky Subloop = Subloop->getParentLoop(); 559199482Srdivacky assert(Subloop && "subloop is not an ancestor of the original loop"); 560199482Srdivacky } 561234353Sdim // Get the current nearest parent of the Subloop exits, initially Unloop. 562234353Sdim NearLoop = 563234353Sdim SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second; 564234353Sdim } 565234353Sdim 566234353Sdim succ_iterator I = succ_begin(BB), E = succ_end(BB); 567243830Sdim if (I == E) { 568198092Srdivacky assert(!Subloop && "subloop blocks must have a successor"); 569234353Sdim NearLoop = 0; // unloop blocks may now exit the function. 570234353Sdim } 571234353Sdim for (; I != E; ++I) { 572234353Sdim if (*I == BB) 573234353Sdim continue; // self loops are uninteresting 574234353Sdim 575234353Sdim Loop *L = LI->getLoopFor(*I); 576234353Sdim if (L == Unloop) { 577234353Sdim // This successor has not been processed. This path must lead to an 578234353Sdim // irreducible backedge. 579234353Sdim assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); 580234353Sdim FoundIB = true; 581234353Sdim } 582234353Sdim if (L != Unloop && Unloop->contains(L)) { 583234353Sdim // Successor is in a subloop. 584234353Sdim if (Subloop) 585234353Sdim continue; // Branching within subloops. Ignore it. 586234353Sdim 587234353Sdim // BB branches from the original into a subloop header. 588234353Sdim assert(L->getParentLoop() == Unloop && "cannot skip into nested loops"); 589234353Sdim 590234353Sdim // Get the current nearest parent of the Subloop's exits. 591234353Sdim L = SubloopParents[L]; 592234353Sdim // L could be Unloop if the only exit was an irreducible backedge. 593234353Sdim } 594234353Sdim if (L == Unloop) { 595234353Sdim continue; 596234353Sdim } 597234353Sdim // Handle critical edges from Unloop into a sibling loop. 598234353Sdim if (L && !L->contains(Unloop)) { 599234353Sdim L = L->getParentLoop(); 600234353Sdim } 601198092Srdivacky // Remember the nearest parent loop among successors or subloop exits. 602234353Sdim if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L)) 603234353Sdim NearLoop = L; 604234353Sdim } 605243830Sdim if (Subloop) { 606234353Sdim SubloopParents[Subloop] = NearLoop; 607234353Sdim return BBLoop; 608234353Sdim } 609234353Sdim return NearLoop; 610234353Sdim} 611234353Sdim 612243830Sdim//===----------------------------------------------------------------------===// 613243830Sdim// LoopInfo implementation 614234353Sdim// 615234353Sdimbool LoopInfo::runOnFunction(Function &) { 616234353Sdim releaseMemory(); 617234353Sdim LI.Analyze(getAnalysis<DominatorTree>().getBase()); 618234353Sdim return false; 619234353Sdim} 620198092Srdivacky 621234353Sdim/// updateUnloop - The last backedge has been removed from a loop--now the 622234353Sdim/// "unloop". Find a new parent for the blocks contained within unloop and 623234353Sdim/// update the loop tree. We don't necessarily have valid dominators at this 624234353Sdim/// point, but LoopInfo is still valid except for the removal of this loop. 625234353Sdim/// 626234353Sdim/// Note that Unloop may now be an empty loop. Calling Loop::getHeader without 627234353Sdim/// checking first is illegal. 628234353Sdimvoid LoopInfo::updateUnloop(Loop *Unloop) { 629234353Sdim 630234353Sdim // First handle the special case of no parent loop to simplify the algorithm. 631226633Sdim if (!Unloop->getParentLoop()) { 632198092Srdivacky // Since BBLoop had no parent, Unloop blocks are no longer in a loop. 633198092Srdivacky for (Loop::block_iterator I = Unloop->block_begin(), 634198092Srdivacky E = Unloop->block_end(); I != E; ++I) { 635198092Srdivacky 636198092Srdivacky // Don't reparent blocks in subloops. 637198092Srdivacky if (getLoopFor(*I) != Unloop) 638198092Srdivacky continue; 639198092Srdivacky 640243830Sdim // Blocks no longer have a parent but are still referenced by Unloop until 641198092Srdivacky // the Unloop object is deleted. 642226633Sdim LI.changeLoopFor(*I, 0); 643198092Srdivacky } 644198092Srdivacky 645198092Srdivacky // Remove the loop from the top-level LoopInfo object. 646198092Srdivacky for (LoopInfo::iterator I = LI.begin();; ++I) { 647198092Srdivacky assert(I != LI.end() && "Couldn't find loop"); 648198092Srdivacky if (*I == Unloop) { 649198092Srdivacky LI.removeLoop(I); 650198092Srdivacky break; 651210299Sed } 652226633Sdim } 653226633Sdim 654226633Sdim // Move all of the subloops to the top-level. 655198092Srdivacky while (!Unloop->empty()) 656198092Srdivacky LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end()))); 657198092Srdivacky 658239462Sdim return; 659210299Sed } 660239462Sdim 661239462Sdim // Update the parent loop for all blocks within the loop. Blocks within 662198092Srdivacky // subloops will not change parents. 663198092Srdivacky UnloopUpdater Updater(Unloop, this); 664198092Srdivacky Updater.updateBlockParents(); 665198092Srdivacky 666198092Srdivacky // Remove blocks from former ancestor loops. 667198092Srdivacky Updater.removeBlocksFromAncestors(); 668244640Sandrew 669244640Sandrew // Add direct subloops as children in their new parent loop. 670244640Sandrew Updater.updateSubloopParents(); 671244640Sandrew 672244640Sandrew // Remove unloop from its parent loop. 673198092Srdivacky Loop *ParentLoop = Unloop->getParentLoop(); 674218893Sdim for (Loop::iterator I = ParentLoop->begin();; ++I) { 675239462Sdim assert(I != ParentLoop->end() && "Couldn't find loop"); 676239462Sdim if (*I == Unloop) { 677239462Sdim ParentLoop->removeChildLoop(I); 678218893Sdim break; 679218893Sdim } 680218893Sdim } 681218893Sdim} 682218893Sdim 683218893Sdimvoid LoopInfo::verifyAnalysis() const { 684218893Sdim // LoopInfo is a FunctionPass, but verifying every loop in the function 685243830Sdim // each time verifyAnalysis is called is very expensive. The 686239462Sdim // -verify-loop-info option can enable this. In order to perform some 687234353Sdim // checking by default, LoopPass has been taught to call verifyLoop 688239462Sdim // manually during loop pass sequences. 689234353Sdim 690234353Sdim if (!VerifyLoopInfo) return; 691234353Sdim 692234353Sdim DenseSet<const Loop*> Loops; 693234353Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 694218893Sdim assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 695218893Sdim (*I)->verifyLoopNest(&Loops); 696218893Sdim } 697226633Sdim 698218893Sdim // Verify that blocks are mapped to valid loops. 699218893Sdim for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(), 700198092Srdivacky E = LI.BBMap.end(); I != E; ++I) { 701198092Srdivacky assert(Loops.count(I->second) && "orphaned loop"); 702198092Srdivacky assert(I->second->contains(I->first) && "orphaned block"); 703234353Sdim } 704234353Sdim} 705234353Sdim 706234353Sdimvoid LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 707234353Sdim AU.setPreservesAll(); 708234353Sdim AU.addRequired<DominatorTree>(); 709234353Sdim} 710234353Sdim 711243830Sdimvoid LoopInfo::print(raw_ostream &OS, const Module*) const { 712243830Sdim LI.print(OS); 713243830Sdim} 714243830Sdim 715234353Sdim//===----------------------------------------------------------------------===// 716234353Sdim// LoopBlocksDFS implementation 717234353Sdim// 718234353Sdim 719234353Sdim/// Traverse the loop blocks and store the DFS result. 720234353Sdim/// Useful for clients that just want the final DFS result and don't need to 721243830Sdim/// visit blocks during the initial traversal. 722243830Sdimvoid LoopBlocksDFS::perform(LoopInfo *LI) { 723243830Sdim LoopBlocksTraversal Traversal(*this, LI); 724243830Sdim for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 725243830Sdim POE = Traversal.end(); POI != POE; ++POI) ; 726243830Sdim} 727243830Sdim