1193323Sed//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the LoopInfo class that is used to identify natural loops 11193323Sed// and determine the loop depth of various nodes of the CFG. Note that the 12193323Sed// loops identified may actually be several natural loops that share the same 13193323Sed// header node... not just a single natural loop. 14193323Sed// 15193323Sed//===----------------------------------------------------------------------===// 16193323Sed 17193323Sed#include "llvm/Analysis/LoopInfo.h" 18249423Sdim#include "llvm/ADT/DepthFirstIterator.h" 19249423Sdim#include "llvm/ADT/SmallPtrSet.h" 20193323Sed#include "llvm/Analysis/Dominators.h" 21239462Sdim#include "llvm/Analysis/LoopInfoImpl.h" 22226633Sdim#include "llvm/Analysis/LoopIterator.h" 23234353Sdim#include "llvm/Analysis/ValueTracking.h" 24193323Sed#include "llvm/Assembly/Writer.h" 25249423Sdim#include "llvm/IR/Constants.h" 26249423Sdim#include "llvm/IR/Instructions.h" 27249423Sdim#include "llvm/IR/Metadata.h" 28193323Sed#include "llvm/Support/CFG.h" 29198090Srdivacky#include "llvm/Support/CommandLine.h" 30202375Srdivacky#include "llvm/Support/Debug.h" 31193323Sed#include <algorithm> 32193323Sedusing namespace llvm; 33193323Sed 34239462Sdim// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. 35239462Sdimtemplate class llvm::LoopBase<BasicBlock, Loop>; 36239462Sdimtemplate class llvm::LoopInfoBase<BasicBlock, Loop>; 37239462Sdim 38198090Srdivacky// Always verify loopinfo if expensive checking is enabled. 39198090Srdivacky#ifdef XDEBUG 40207618Srdivackystatic bool VerifyLoopInfo = true; 41198090Srdivacky#else 42207618Srdivackystatic bool VerifyLoopInfo = false; 43198090Srdivacky#endif 44198090Srdivackystatic cl::opt<bool,true> 45198090SrdivackyVerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), 46198090Srdivacky cl::desc("Verify loop info (time consuming)")); 47198090Srdivacky 48193323Sedchar LoopInfo::ID = 0; 49218893SdimINITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) 50218893SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 51218893SdimINITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true) 52193323Sed 53193323Sed//===----------------------------------------------------------------------===// 54193323Sed// Loop implementation 55193323Sed// 56193323Sed 57198090Srdivacky/// isLoopInvariant - Return true if the specified value is loop invariant 58198090Srdivacky/// 59198090Srdivackybool Loop::isLoopInvariant(Value *V) const { 60198090Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 61218893Sdim return !contains(I); 62198090Srdivacky return true; // All non-instructions are loop invariant 63198090Srdivacky} 64198090Srdivacky 65218893Sdim/// hasLoopInvariantOperands - Return true if all the operands of the 66226633Sdim/// specified instruction are loop invariant. 67218893Sdimbool Loop::hasLoopInvariantOperands(Instruction *I) const { 68218893Sdim for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 69218893Sdim if (!isLoopInvariant(I->getOperand(i))) 70218893Sdim return false; 71226633Sdim 72218893Sdim return true; 73198090Srdivacky} 74198090Srdivacky 75198090Srdivacky/// makeLoopInvariant - If the given value is an instruciton inside of the 76198090Srdivacky/// loop and it can be hoisted, do so to make it trivially loop-invariant. 77198090Srdivacky/// Return true if the value after any hoisting is loop invariant. This 78198090Srdivacky/// function can be used as a slightly more aggressive replacement for 79198090Srdivacky/// isLoopInvariant. 80198090Srdivacky/// 81198090Srdivacky/// If InsertPt is specified, it is the point to hoist instructions to. 82198090Srdivacky/// If null, the terminator of the loop preheader is used. 83198090Srdivacky/// 84198090Srdivackybool Loop::makeLoopInvariant(Value *V, bool &Changed, 85198090Srdivacky Instruction *InsertPt) const { 86198090Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 87198090Srdivacky return makeLoopInvariant(I, Changed, InsertPt); 88198090Srdivacky return true; // All non-instructions are loop-invariant. 89198090Srdivacky} 90198090Srdivacky 91198090Srdivacky/// makeLoopInvariant - If the given instruction is inside of the 92198090Srdivacky/// loop and it can be hoisted, do so to make it trivially loop-invariant. 93198090Srdivacky/// Return true if the instruction after any hoisting is loop invariant. This 94198090Srdivacky/// function can be used as a slightly more aggressive replacement for 95198090Srdivacky/// isLoopInvariant. 96198090Srdivacky/// 97198090Srdivacky/// If InsertPt is specified, it is the point to hoist instructions to. 98198090Srdivacky/// If null, the terminator of the loop preheader is used. 99198090Srdivacky/// 100198090Srdivackybool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 101198090Srdivacky Instruction *InsertPt) const { 102198090Srdivacky // Test if the value is already loop-invariant. 103198090Srdivacky if (isLoopInvariant(I)) 104198090Srdivacky return true; 105234353Sdim if (!isSafeToSpeculativelyExecute(I)) 106198090Srdivacky return false; 107198090Srdivacky if (I->mayReadFromMemory()) 108198090Srdivacky return false; 109226633Sdim // The landingpad instruction is immobile. 110226633Sdim if (isa<LandingPadInst>(I)) 111226633Sdim return false; 112198090Srdivacky // Determine the insertion point, unless one was given. 113198090Srdivacky if (!InsertPt) { 114198090Srdivacky BasicBlock *Preheader = getLoopPreheader(); 115198090Srdivacky // Without a preheader, hoisting is not feasible. 116198090Srdivacky if (!Preheader) 117198090Srdivacky return false; 118198090Srdivacky InsertPt = Preheader->getTerminator(); 119198090Srdivacky } 120198090Srdivacky // Don't hoist instructions with loop-variant operands. 121198090Srdivacky for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 122198090Srdivacky if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 123198090Srdivacky return false; 124226633Sdim 125198090Srdivacky // Hoist. 126198090Srdivacky I->moveBefore(InsertPt); 127198090Srdivacky Changed = true; 128198090Srdivacky return true; 129198090Srdivacky} 130198090Srdivacky 131198090Srdivacky/// getCanonicalInductionVariable - Check to see if the loop has a canonical 132198090Srdivacky/// induction variable: an integer recurrence that starts at 0 and increments 133198090Srdivacky/// by one each time through the loop. If so, return the phi node that 134198090Srdivacky/// corresponds to it. 135198090Srdivacky/// 136198090Srdivacky/// The IndVarSimplify pass transforms loops to have a canonical induction 137198090Srdivacky/// variable. 138198090Srdivacky/// 139198090SrdivackyPHINode *Loop::getCanonicalInductionVariable() const { 140198090Srdivacky BasicBlock *H = getHeader(); 141198090Srdivacky 142198090Srdivacky BasicBlock *Incoming = 0, *Backedge = 0; 143212904Sdim pred_iterator PI = pred_begin(H); 144212904Sdim assert(PI != pred_end(H) && 145198090Srdivacky "Loop must have at least one backedge!"); 146198090Srdivacky Backedge = *PI++; 147212904Sdim if (PI == pred_end(H)) return 0; // dead loop 148198090Srdivacky Incoming = *PI++; 149212904Sdim if (PI != pred_end(H)) return 0; // multiple backedges? 150198090Srdivacky 151198090Srdivacky if (contains(Incoming)) { 152198090Srdivacky if (contains(Backedge)) 153198090Srdivacky return 0; 154198090Srdivacky std::swap(Incoming, Backedge); 155198090Srdivacky } else if (!contains(Backedge)) 156198090Srdivacky return 0; 157198090Srdivacky 158198090Srdivacky // Loop over all of the PHI nodes, looking for a canonical indvar. 159198090Srdivacky for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 160198090Srdivacky PHINode *PN = cast<PHINode>(I); 161198090Srdivacky if (ConstantInt *CI = 162198090Srdivacky dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 163198090Srdivacky if (CI->isNullValue()) 164198090Srdivacky if (Instruction *Inc = 165198090Srdivacky dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 166198090Srdivacky if (Inc->getOpcode() == Instruction::Add && 167198090Srdivacky Inc->getOperand(0) == PN) 168198090Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 169198090Srdivacky if (CI->equalsInt(1)) 170198090Srdivacky return PN; 171198090Srdivacky } 172198090Srdivacky return 0; 173198090Srdivacky} 174198090Srdivacky 175198090Srdivacky/// isLCSSAForm - Return true if the Loop is in LCSSA form 176205218Srdivackybool Loop::isLCSSAForm(DominatorTree &DT) const { 177198090Srdivacky // Sort the blocks vector so that we can use binary search to do quick 178198090Srdivacky // lookups. 179210299Sed SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end()); 180198090Srdivacky 181198090Srdivacky for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 182199481Srdivacky BasicBlock *BB = *BI; 183199481Srdivacky for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 184198090Srdivacky for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 185198090Srdivacky ++UI) { 186210299Sed User *U = *UI; 187210299Sed BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 188210299Sed if (PHINode *P = dyn_cast<PHINode>(U)) 189198090Srdivacky UserBB = P->getIncomingBlock(UI); 190198090Srdivacky 191204961Srdivacky // Check the current block, as a fast-path, before checking whether 192204961Srdivacky // the use is anywhere in the loop. Most values are used in the same 193204961Srdivacky // block they are defined in. Also, blocks not reachable from the 194204961Srdivacky // entry are special; uses in them don't need to go through PHIs. 195204961Srdivacky if (UserBB != BB && 196204961Srdivacky !LoopBBs.count(UserBB) && 197205218Srdivacky DT.isReachableFromEntry(UserBB)) 198198090Srdivacky return false; 199198090Srdivacky } 200198090Srdivacky } 201198090Srdivacky 202198090Srdivacky return true; 203198090Srdivacky} 204198090Srdivacky 205198090Srdivacky/// isLoopSimplifyForm - Return true if the Loop is in the form that 206198090Srdivacky/// the LoopSimplify form transforms loops to, which is sometimes called 207198090Srdivacky/// normal form. 208198090Srdivackybool Loop::isLoopSimplifyForm() const { 209199481Srdivacky // Normal-form loops have a preheader, a single backedge, and all of their 210199481Srdivacky // exits have all their predecessors inside the loop. 211199481Srdivacky return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 212199481Srdivacky} 213199481Srdivacky 214234353Sdim/// isSafeToClone - Return true if the loop body is safe to clone in practice. 215234353Sdim/// Routines that reform the loop CFG and split edges often fail on indirectbr. 216234353Sdimbool Loop::isSafeToClone() const { 217249423Sdim // Return false if any loop blocks contain indirectbrs, or there are any calls 218249423Sdim // to noduplicate functions. 219234353Sdim for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) { 220249423Sdim if (isa<IndirectBrInst>((*I)->getTerminator())) { 221234353Sdim return false; 222249423Sdim } else if (const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator())) { 223249423Sdim if (II->hasFnAttr(Attribute::NoDuplicate)) 224249423Sdim return false; 225249423Sdim } 226249423Sdim 227249423Sdim for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { 228249423Sdim if (const CallInst *CI = dyn_cast<CallInst>(BI)) { 229249423Sdim if (CI->hasFnAttr(Attribute::NoDuplicate)) 230249423Sdim return false; 231249423Sdim } 232249423Sdim } 233234353Sdim } 234234353Sdim return true; 235234353Sdim} 236234353Sdim 237249423Sdimbool Loop::isAnnotatedParallel() const { 238249423Sdim 239249423Sdim BasicBlock *latch = getLoopLatch(); 240249423Sdim if (latch == NULL) 241249423Sdim return false; 242249423Sdim 243249423Sdim MDNode *desiredLoopIdMetadata = 244249423Sdim latch->getTerminator()->getMetadata("llvm.loop.parallel"); 245249423Sdim 246249423Sdim if (!desiredLoopIdMetadata) 247249423Sdim return false; 248249423Sdim 249249423Sdim // The loop branch contains the parallel loop metadata. In order to ensure 250249423Sdim // that any parallel-loop-unaware optimization pass hasn't added loop-carried 251249423Sdim // dependencies (thus converted the loop back to a sequential loop), check 252249423Sdim // that all the memory instructions in the loop contain parallelism metadata 253249423Sdim // that point to the same unique "loop id metadata" the loop branch does. 254249423Sdim for (block_iterator BB = block_begin(), BE = block_end(); BB != BE; ++BB) { 255249423Sdim for (BasicBlock::iterator II = (*BB)->begin(), EE = (*BB)->end(); 256249423Sdim II != EE; II++) { 257249423Sdim 258249423Sdim if (!II->mayReadOrWriteMemory()) 259249423Sdim continue; 260249423Sdim 261249423Sdim if (!II->getMetadata("llvm.mem.parallel_loop_access")) 262249423Sdim return false; 263249423Sdim 264249423Sdim // The memory instruction can refer to the loop identifier metadata 265249423Sdim // directly or indirectly through another list metadata (in case of 266249423Sdim // nested parallel loops). The loop identifier metadata refers to 267249423Sdim // itself so we can check both cases with the same routine. 268249423Sdim MDNode *loopIdMD = 269249423Sdim dyn_cast<MDNode>(II->getMetadata("llvm.mem.parallel_loop_access")); 270249423Sdim bool loopIdMDFound = false; 271249423Sdim for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) { 272249423Sdim if (loopIdMD->getOperand(i) == desiredLoopIdMetadata) { 273249423Sdim loopIdMDFound = true; 274249423Sdim break; 275249423Sdim } 276249423Sdim } 277249423Sdim 278249423Sdim if (!loopIdMDFound) 279249423Sdim return false; 280249423Sdim } 281249423Sdim } 282249423Sdim return true; 283249423Sdim} 284249423Sdim 285249423Sdim 286199481Srdivacky/// hasDedicatedExits - Return true if no exit block for the loop 287199481Srdivacky/// has a predecessor that is outside the loop. 288199481Srdivackybool Loop::hasDedicatedExits() const { 289198396Srdivacky // Sort the blocks vector so that we can use binary search to do quick 290198396Srdivacky // lookups. 291198396Srdivacky SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 292198090Srdivacky // Each predecessor of each exit block of a normal loop is contained 293198090Srdivacky // within the loop. 294198090Srdivacky SmallVector<BasicBlock *, 4> ExitBlocks; 295198090Srdivacky getExitBlocks(ExitBlocks); 296198090Srdivacky for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 297198090Srdivacky for (pred_iterator PI = pred_begin(ExitBlocks[i]), 298198090Srdivacky PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 299198396Srdivacky if (!LoopBBs.count(*PI)) 300198090Srdivacky return false; 301198090Srdivacky // All the requirements are met. 302198090Srdivacky return true; 303198090Srdivacky} 304198090Srdivacky 305198090Srdivacky/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 306198090Srdivacky/// These are the blocks _outside of the current loop_ which are branched to. 307200581Srdivacky/// This assumes that loop exits are in canonical form. 308198090Srdivacky/// 309198090Srdivackyvoid 310198090SrdivackyLoop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 311200581Srdivacky assert(hasDedicatedExits() && 312200581Srdivacky "getUniqueExitBlocks assumes the loop has canonical form exits!"); 313198090Srdivacky 314198090Srdivacky // Sort the blocks vector so that we can use binary search to do quick 315198090Srdivacky // lookups. 316198090Srdivacky SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end()); 317198090Srdivacky std::sort(LoopBBs.begin(), LoopBBs.end()); 318198090Srdivacky 319198090Srdivacky SmallVector<BasicBlock *, 32> switchExitBlocks; 320198090Srdivacky 321198090Srdivacky for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 322198090Srdivacky 323198090Srdivacky BasicBlock *current = *BI; 324198090Srdivacky switchExitBlocks.clear(); 325198090Srdivacky 326212904Sdim for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { 327198090Srdivacky // If block is inside the loop then it is not a exit block. 328198090Srdivacky if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 329198090Srdivacky continue; 330198090Srdivacky 331212904Sdim pred_iterator PI = pred_begin(*I); 332198090Srdivacky BasicBlock *firstPred = *PI; 333198090Srdivacky 334198090Srdivacky // If current basic block is this exit block's first predecessor 335198090Srdivacky // then only insert exit block in to the output ExitBlocks vector. 336198090Srdivacky // This ensures that same exit block is not inserted twice into 337198090Srdivacky // ExitBlocks vector. 338198090Srdivacky if (current != firstPred) 339198090Srdivacky continue; 340198090Srdivacky 341198090Srdivacky // If a terminator has more then two successors, for example SwitchInst, 342198090Srdivacky // then it is possible that there are multiple edges from current block 343198090Srdivacky // to one exit block. 344212904Sdim if (std::distance(succ_begin(current), succ_end(current)) <= 2) { 345198090Srdivacky ExitBlocks.push_back(*I); 346198090Srdivacky continue; 347198090Srdivacky } 348198090Srdivacky 349198090Srdivacky // In case of multiple edges from current block to exit block, collect 350198090Srdivacky // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 351198090Srdivacky // duplicate edges. 352198090Srdivacky if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 353198090Srdivacky == switchExitBlocks.end()) { 354198090Srdivacky switchExitBlocks.push_back(*I); 355198090Srdivacky ExitBlocks.push_back(*I); 356198090Srdivacky } 357198090Srdivacky } 358198090Srdivacky } 359198090Srdivacky} 360198090Srdivacky 361198090Srdivacky/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 362198090Srdivacky/// block, return that block. Otherwise return null. 363198090SrdivackyBasicBlock *Loop::getUniqueExitBlock() const { 364198090Srdivacky SmallVector<BasicBlock *, 8> UniqueExitBlocks; 365198090Srdivacky getUniqueExitBlocks(UniqueExitBlocks); 366198090Srdivacky if (UniqueExitBlocks.size() == 1) 367198090Srdivacky return UniqueExitBlocks[0]; 368198090Srdivacky return 0; 369198090Srdivacky} 370198090Srdivacky 371243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 372202375Srdivackyvoid Loop::dump() const { 373202375Srdivacky print(dbgs()); 374202375Srdivacky} 375243830Sdim#endif 376202375Srdivacky 377193323Sed//===----------------------------------------------------------------------===// 378226633Sdim// UnloopUpdater implementation 379226633Sdim// 380226633Sdim 381226633Sdimnamespace { 382226633Sdim/// Find the new parent loop for all blocks within the "unloop" whose last 383226633Sdim/// backedges has just been removed. 384226633Sdimclass UnloopUpdater { 385226633Sdim Loop *Unloop; 386226633Sdim LoopInfo *LI; 387226633Sdim 388226633Sdim LoopBlocksDFS DFS; 389226633Sdim 390226633Sdim // Map unloop's immediate subloops to their nearest reachable parents. Nested 391226633Sdim // loops within these subloops will not change parents. However, an immediate 392226633Sdim // subloop's new parent will be the nearest loop reachable from either its own 393226633Sdim // exits *or* any of its nested loop's exits. 394226633Sdim DenseMap<Loop*, Loop*> SubloopParents; 395226633Sdim 396226633Sdim // Flag the presence of an irreducible backedge whose destination is a block 397226633Sdim // directly contained by the original unloop. 398226633Sdim bool FoundIB; 399226633Sdim 400226633Sdimpublic: 401226633Sdim UnloopUpdater(Loop *UL, LoopInfo *LInfo) : 402226633Sdim Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {} 403226633Sdim 404226633Sdim void updateBlockParents(); 405226633Sdim 406226633Sdim void removeBlocksFromAncestors(); 407226633Sdim 408226633Sdim void updateSubloopParents(); 409226633Sdim 410226633Sdimprotected: 411226633Sdim Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); 412226633Sdim}; 413226633Sdim} // end anonymous namespace 414226633Sdim 415226633Sdim/// updateBlockParents - Update the parent loop for all blocks that are directly 416226633Sdim/// contained within the original "unloop". 417226633Sdimvoid UnloopUpdater::updateBlockParents() { 418226633Sdim if (Unloop->getNumBlocks()) { 419226633Sdim // Perform a post order CFG traversal of all blocks within this loop, 420226633Sdim // propagating the nearest loop from sucessors to predecessors. 421226633Sdim LoopBlocksTraversal Traversal(DFS, LI); 422226633Sdim for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 423226633Sdim POE = Traversal.end(); POI != POE; ++POI) { 424226633Sdim 425226633Sdim Loop *L = LI->getLoopFor(*POI); 426226633Sdim Loop *NL = getNearestLoop(*POI, L); 427226633Sdim 428226633Sdim if (NL != L) { 429226633Sdim // For reducible loops, NL is now an ancestor of Unloop. 430226633Sdim assert((NL != Unloop && (!NL || NL->contains(Unloop))) && 431226633Sdim "uninitialized successor"); 432226633Sdim LI->changeLoopFor(*POI, NL); 433226633Sdim } 434226633Sdim else { 435226633Sdim // Or the current block is part of a subloop, in which case its parent 436226633Sdim // is unchanged. 437226633Sdim assert((FoundIB || Unloop->contains(L)) && "uninitialized successor"); 438226633Sdim } 439226633Sdim } 440226633Sdim } 441226633Sdim // Each irreducible loop within the unloop induces a round of iteration using 442226633Sdim // the DFS result cached by Traversal. 443226633Sdim bool Changed = FoundIB; 444226633Sdim for (unsigned NIters = 0; Changed; ++NIters) { 445226633Sdim assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"); 446226633Sdim 447226633Sdim // Iterate over the postorder list of blocks, propagating the nearest loop 448226633Sdim // from successors to predecessors as before. 449226633Sdim Changed = false; 450226633Sdim for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), 451226633Sdim POE = DFS.endPostorder(); POI != POE; ++POI) { 452226633Sdim 453226633Sdim Loop *L = LI->getLoopFor(*POI); 454226633Sdim Loop *NL = getNearestLoop(*POI, L); 455226633Sdim if (NL != L) { 456226633Sdim assert(NL != Unloop && (!NL || NL->contains(Unloop)) && 457226633Sdim "uninitialized successor"); 458226633Sdim LI->changeLoopFor(*POI, NL); 459226633Sdim Changed = true; 460226633Sdim } 461226633Sdim } 462226633Sdim } 463226633Sdim} 464226633Sdim 465226633Sdim/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below 466226633Sdim/// their new parents. 467226633Sdimvoid UnloopUpdater::removeBlocksFromAncestors() { 468234353Sdim // Remove all unloop's blocks (including those in nested subloops) from 469234353Sdim // ancestors below the new parent loop. 470226633Sdim for (Loop::block_iterator BI = Unloop->block_begin(), 471226633Sdim BE = Unloop->block_end(); BI != BE; ++BI) { 472234353Sdim Loop *OuterParent = LI->getLoopFor(*BI); 473234353Sdim if (Unloop->contains(OuterParent)) { 474234353Sdim while (OuterParent->getParentLoop() != Unloop) 475234353Sdim OuterParent = OuterParent->getParentLoop(); 476234353Sdim OuterParent = SubloopParents[OuterParent]; 477234353Sdim } 478226633Sdim // Remove blocks from former Ancestors except Unloop itself which will be 479226633Sdim // deleted. 480234353Sdim for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent; 481226633Sdim OldParent = OldParent->getParentLoop()) { 482226633Sdim assert(OldParent && "new loop is not an ancestor of the original"); 483226633Sdim OldParent->removeBlockFromLoop(*BI); 484226633Sdim } 485226633Sdim } 486226633Sdim} 487226633Sdim 488226633Sdim/// updateSubloopParents - Update the parent loop for all subloops directly 489226633Sdim/// nested within unloop. 490226633Sdimvoid UnloopUpdater::updateSubloopParents() { 491226633Sdim while (!Unloop->empty()) { 492226633Sdim Loop *Subloop = *llvm::prior(Unloop->end()); 493226633Sdim Unloop->removeChildLoop(llvm::prior(Unloop->end())); 494226633Sdim 495226633Sdim assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); 496243830Sdim if (Loop *Parent = SubloopParents[Subloop]) 497243830Sdim Parent->addChildLoop(Subloop); 498226633Sdim else 499226633Sdim LI->addTopLevelLoop(Subloop); 500226633Sdim } 501226633Sdim} 502226633Sdim 503226633Sdim/// getNearestLoop - Return the nearest parent loop among this block's 504226633Sdim/// successors. If a successor is a subloop header, consider its parent to be 505226633Sdim/// the nearest parent of the subloop's exits. 506226633Sdim/// 507226633Sdim/// For subloop blocks, simply update SubloopParents and return NULL. 508226633SdimLoop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { 509226633Sdim 510226633Sdim // Initially for blocks directly contained by Unloop, NearLoop == Unloop and 511226633Sdim // is considered uninitialized. 512226633Sdim Loop *NearLoop = BBLoop; 513226633Sdim 514226633Sdim Loop *Subloop = 0; 515226633Sdim if (NearLoop != Unloop && Unloop->contains(NearLoop)) { 516226633Sdim Subloop = NearLoop; 517226633Sdim // Find the subloop ancestor that is directly contained within Unloop. 518226633Sdim while (Subloop->getParentLoop() != Unloop) { 519226633Sdim Subloop = Subloop->getParentLoop(); 520226633Sdim assert(Subloop && "subloop is not an ancestor of the original loop"); 521226633Sdim } 522226633Sdim // Get the current nearest parent of the Subloop exits, initially Unloop. 523243830Sdim NearLoop = 524243830Sdim SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second; 525226633Sdim } 526226633Sdim 527226633Sdim succ_iterator I = succ_begin(BB), E = succ_end(BB); 528226633Sdim if (I == E) { 529226633Sdim assert(!Subloop && "subloop blocks must have a successor"); 530226633Sdim NearLoop = 0; // unloop blocks may now exit the function. 531226633Sdim } 532226633Sdim for (; I != E; ++I) { 533226633Sdim if (*I == BB) 534226633Sdim continue; // self loops are uninteresting 535226633Sdim 536226633Sdim Loop *L = LI->getLoopFor(*I); 537226633Sdim if (L == Unloop) { 538226633Sdim // This successor has not been processed. This path must lead to an 539226633Sdim // irreducible backedge. 540226633Sdim assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); 541226633Sdim FoundIB = true; 542226633Sdim } 543226633Sdim if (L != Unloop && Unloop->contains(L)) { 544226633Sdim // Successor is in a subloop. 545226633Sdim if (Subloop) 546226633Sdim continue; // Branching within subloops. Ignore it. 547226633Sdim 548226633Sdim // BB branches from the original into a subloop header. 549226633Sdim assert(L->getParentLoop() == Unloop && "cannot skip into nested loops"); 550226633Sdim 551226633Sdim // Get the current nearest parent of the Subloop's exits. 552226633Sdim L = SubloopParents[L]; 553226633Sdim // L could be Unloop if the only exit was an irreducible backedge. 554226633Sdim } 555226633Sdim if (L == Unloop) { 556226633Sdim continue; 557226633Sdim } 558226633Sdim // Handle critical edges from Unloop into a sibling loop. 559226633Sdim if (L && !L->contains(Unloop)) { 560226633Sdim L = L->getParentLoop(); 561226633Sdim } 562226633Sdim // Remember the nearest parent loop among successors or subloop exits. 563226633Sdim if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L)) 564226633Sdim NearLoop = L; 565226633Sdim } 566226633Sdim if (Subloop) { 567226633Sdim SubloopParents[Subloop] = NearLoop; 568226633Sdim return BBLoop; 569226633Sdim } 570226633Sdim return NearLoop; 571226633Sdim} 572226633Sdim 573226633Sdim//===----------------------------------------------------------------------===// 574193323Sed// LoopInfo implementation 575193323Sed// 576193323Sedbool LoopInfo::runOnFunction(Function &) { 577193323Sed releaseMemory(); 578239462Sdim LI.Analyze(getAnalysis<DominatorTree>().getBase()); 579193323Sed return false; 580193323Sed} 581193323Sed 582226633Sdim/// updateUnloop - The last backedge has been removed from a loop--now the 583226633Sdim/// "unloop". Find a new parent for the blocks contained within unloop and 584226633Sdim/// update the loop tree. We don't necessarily have valid dominators at this 585226633Sdim/// point, but LoopInfo is still valid except for the removal of this loop. 586226633Sdim/// 587226633Sdim/// Note that Unloop may now be an empty loop. Calling Loop::getHeader without 588226633Sdim/// checking first is illegal. 589226633Sdimvoid LoopInfo::updateUnloop(Loop *Unloop) { 590226633Sdim 591226633Sdim // First handle the special case of no parent loop to simplify the algorithm. 592226633Sdim if (!Unloop->getParentLoop()) { 593226633Sdim // Since BBLoop had no parent, Unloop blocks are no longer in a loop. 594226633Sdim for (Loop::block_iterator I = Unloop->block_begin(), 595226633Sdim E = Unloop->block_end(); I != E; ++I) { 596226633Sdim 597226633Sdim // Don't reparent blocks in subloops. 598226633Sdim if (getLoopFor(*I) != Unloop) 599226633Sdim continue; 600226633Sdim 601226633Sdim // Blocks no longer have a parent but are still referenced by Unloop until 602226633Sdim // the Unloop object is deleted. 603226633Sdim LI.changeLoopFor(*I, 0); 604226633Sdim } 605226633Sdim 606226633Sdim // Remove the loop from the top-level LoopInfo object. 607226633Sdim for (LoopInfo::iterator I = LI.begin();; ++I) { 608226633Sdim assert(I != LI.end() && "Couldn't find loop"); 609226633Sdim if (*I == Unloop) { 610226633Sdim LI.removeLoop(I); 611226633Sdim break; 612226633Sdim } 613226633Sdim } 614226633Sdim 615226633Sdim // Move all of the subloops to the top-level. 616226633Sdim while (!Unloop->empty()) 617226633Sdim LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end()))); 618226633Sdim 619226633Sdim return; 620226633Sdim } 621226633Sdim 622226633Sdim // Update the parent loop for all blocks within the loop. Blocks within 623226633Sdim // subloops will not change parents. 624226633Sdim UnloopUpdater Updater(Unloop, this); 625226633Sdim Updater.updateBlockParents(); 626226633Sdim 627226633Sdim // Remove blocks from former ancestor loops. 628226633Sdim Updater.removeBlocksFromAncestors(); 629226633Sdim 630226633Sdim // Add direct subloops as children in their new parent loop. 631226633Sdim Updater.updateSubloopParents(); 632226633Sdim 633226633Sdim // Remove unloop from its parent loop. 634226633Sdim Loop *ParentLoop = Unloop->getParentLoop(); 635226633Sdim for (Loop::iterator I = ParentLoop->begin();; ++I) { 636226633Sdim assert(I != ParentLoop->end() && "Couldn't find loop"); 637226633Sdim if (*I == Unloop) { 638226633Sdim ParentLoop->removeChildLoop(I); 639226633Sdim break; 640226633Sdim } 641226633Sdim } 642226633Sdim} 643226633Sdim 644198090Srdivackyvoid LoopInfo::verifyAnalysis() const { 645198090Srdivacky // LoopInfo is a FunctionPass, but verifying every loop in the function 646198090Srdivacky // each time verifyAnalysis is called is very expensive. The 647198090Srdivacky // -verify-loop-info option can enable this. In order to perform some 648198090Srdivacky // checking by default, LoopPass has been taught to call verifyLoop 649198090Srdivacky // manually during loop pass sequences. 650198090Srdivacky 651198090Srdivacky if (!VerifyLoopInfo) return; 652198090Srdivacky 653226633Sdim DenseSet<const Loop*> Loops; 654198090Srdivacky for (iterator I = begin(), E = end(); I != E; ++I) { 655198090Srdivacky assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 656226633Sdim (*I)->verifyLoopNest(&Loops); 657198090Srdivacky } 658198090Srdivacky 659226633Sdim // Verify that blocks are mapped to valid loops. 660226633Sdim for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(), 661226633Sdim E = LI.BBMap.end(); I != E; ++I) { 662226633Sdim assert(Loops.count(I->second) && "orphaned loop"); 663226633Sdim assert(I->second->contains(I->first) && "orphaned block"); 664226633Sdim } 665198090Srdivacky} 666198090Srdivacky 667193323Sedvoid LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 668193323Sed AU.setPreservesAll(); 669193323Sed AU.addRequired<DominatorTree>(); 670193323Sed} 671198090Srdivacky 672198090Srdivackyvoid LoopInfo::print(raw_ostream &OS, const Module*) const { 673198090Srdivacky LI.print(OS); 674198090Srdivacky} 675198090Srdivacky 676226633Sdim//===----------------------------------------------------------------------===// 677226633Sdim// LoopBlocksDFS implementation 678226633Sdim// 679226633Sdim 680226633Sdim/// Traverse the loop blocks and store the DFS result. 681226633Sdim/// Useful for clients that just want the final DFS result and don't need to 682226633Sdim/// visit blocks during the initial traversal. 683226633Sdimvoid LoopBlocksDFS::perform(LoopInfo *LI) { 684226633Sdim LoopBlocksTraversal Traversal(*this, LI); 685226633Sdim for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 686226633Sdim POE = Traversal.end(); POI != POE; ++POI) ; 687226633Sdim} 688