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" 18252723Sdim#include "llvm/ADT/DepthFirstIterator.h" 19252723Sdim#include "llvm/ADT/SmallPtrSet.h" 20193323Sed#include "llvm/Analysis/Dominators.h" 21245431Sdim#include "llvm/Analysis/LoopInfoImpl.h" 22226890Sdim#include "llvm/Analysis/LoopIterator.h" 23235633Sdim#include "llvm/Analysis/ValueTracking.h" 24193323Sed#include "llvm/Assembly/Writer.h" 25252723Sdim#include "llvm/IR/Constants.h" 26252723Sdim#include "llvm/IR/Instructions.h" 27252723Sdim#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 34245431Sdim// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. 35245431Sdimtemplate class llvm::LoopBase<BasicBlock, Loop>; 36245431Sdimtemplate class llvm::LoopInfoBase<BasicBlock, Loop>; 37245431Sdim 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 53263509Sdim// Loop identifier metadata name. 54263509Sdimstatic const char *const LoopMDName = "llvm.loop"; 55263509Sdim 56193323Sed//===----------------------------------------------------------------------===// 57193323Sed// Loop implementation 58193323Sed// 59193323Sed 60198090Srdivacky/// isLoopInvariant - Return true if the specified value is loop invariant 61198090Srdivacky/// 62198090Srdivackybool Loop::isLoopInvariant(Value *V) const { 63198090Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 64218893Sdim return !contains(I); 65198090Srdivacky return true; // All non-instructions are loop invariant 66198090Srdivacky} 67198090Srdivacky 68218893Sdim/// hasLoopInvariantOperands - Return true if all the operands of the 69226890Sdim/// specified instruction are loop invariant. 70218893Sdimbool Loop::hasLoopInvariantOperands(Instruction *I) const { 71218893Sdim for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 72218893Sdim if (!isLoopInvariant(I->getOperand(i))) 73218893Sdim return false; 74226890Sdim 75218893Sdim return true; 76198090Srdivacky} 77198090Srdivacky 78198090Srdivacky/// makeLoopInvariant - If the given value is an instruciton inside of the 79198090Srdivacky/// loop and it can be hoisted, do so to make it trivially loop-invariant. 80198090Srdivacky/// Return true if the value after any hoisting is loop invariant. This 81198090Srdivacky/// function can be used as a slightly more aggressive replacement for 82198090Srdivacky/// isLoopInvariant. 83198090Srdivacky/// 84198090Srdivacky/// If InsertPt is specified, it is the point to hoist instructions to. 85198090Srdivacky/// If null, the terminator of the loop preheader is used. 86198090Srdivacky/// 87198090Srdivackybool Loop::makeLoopInvariant(Value *V, bool &Changed, 88198090Srdivacky Instruction *InsertPt) const { 89198090Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 90198090Srdivacky return makeLoopInvariant(I, Changed, InsertPt); 91198090Srdivacky return true; // All non-instructions are loop-invariant. 92198090Srdivacky} 93198090Srdivacky 94198090Srdivacky/// makeLoopInvariant - If the given instruction is inside of the 95198090Srdivacky/// loop and it can be hoisted, do so to make it trivially loop-invariant. 96198090Srdivacky/// Return true if the instruction after any hoisting is loop invariant. This 97198090Srdivacky/// function can be used as a slightly more aggressive replacement for 98198090Srdivacky/// isLoopInvariant. 99198090Srdivacky/// 100198090Srdivacky/// If InsertPt is specified, it is the point to hoist instructions to. 101198090Srdivacky/// If null, the terminator of the loop preheader is used. 102198090Srdivacky/// 103198090Srdivackybool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 104198090Srdivacky Instruction *InsertPt) const { 105198090Srdivacky // Test if the value is already loop-invariant. 106198090Srdivacky if (isLoopInvariant(I)) 107198090Srdivacky return true; 108235633Sdim if (!isSafeToSpeculativelyExecute(I)) 109198090Srdivacky return false; 110198090Srdivacky if (I->mayReadFromMemory()) 111198090Srdivacky return false; 112226890Sdim // The landingpad instruction is immobile. 113226890Sdim if (isa<LandingPadInst>(I)) 114226890Sdim return false; 115198090Srdivacky // Determine the insertion point, unless one was given. 116198090Srdivacky if (!InsertPt) { 117198090Srdivacky BasicBlock *Preheader = getLoopPreheader(); 118198090Srdivacky // Without a preheader, hoisting is not feasible. 119198090Srdivacky if (!Preheader) 120198090Srdivacky return false; 121198090Srdivacky InsertPt = Preheader->getTerminator(); 122198090Srdivacky } 123198090Srdivacky // Don't hoist instructions with loop-variant operands. 124198090Srdivacky for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 125198090Srdivacky if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 126198090Srdivacky return false; 127226890Sdim 128198090Srdivacky // Hoist. 129198090Srdivacky I->moveBefore(InsertPt); 130198090Srdivacky Changed = true; 131198090Srdivacky return true; 132198090Srdivacky} 133198090Srdivacky 134198090Srdivacky/// getCanonicalInductionVariable - Check to see if the loop has a canonical 135198090Srdivacky/// induction variable: an integer recurrence that starts at 0 and increments 136198090Srdivacky/// by one each time through the loop. If so, return the phi node that 137198090Srdivacky/// corresponds to it. 138198090Srdivacky/// 139198090Srdivacky/// The IndVarSimplify pass transforms loops to have a canonical induction 140198090Srdivacky/// variable. 141198090Srdivacky/// 142198090SrdivackyPHINode *Loop::getCanonicalInductionVariable() const { 143198090Srdivacky BasicBlock *H = getHeader(); 144198090Srdivacky 145198090Srdivacky BasicBlock *Incoming = 0, *Backedge = 0; 146212904Sdim pred_iterator PI = pred_begin(H); 147212904Sdim assert(PI != pred_end(H) && 148198090Srdivacky "Loop must have at least one backedge!"); 149198090Srdivacky Backedge = *PI++; 150212904Sdim if (PI == pred_end(H)) return 0; // dead loop 151198090Srdivacky Incoming = *PI++; 152212904Sdim if (PI != pred_end(H)) return 0; // multiple backedges? 153198090Srdivacky 154198090Srdivacky if (contains(Incoming)) { 155198090Srdivacky if (contains(Backedge)) 156198090Srdivacky return 0; 157198090Srdivacky std::swap(Incoming, Backedge); 158198090Srdivacky } else if (!contains(Backedge)) 159198090Srdivacky return 0; 160198090Srdivacky 161198090Srdivacky // Loop over all of the PHI nodes, looking for a canonical indvar. 162198090Srdivacky for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 163198090Srdivacky PHINode *PN = cast<PHINode>(I); 164198090Srdivacky if (ConstantInt *CI = 165198090Srdivacky dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 166198090Srdivacky if (CI->isNullValue()) 167198090Srdivacky if (Instruction *Inc = 168198090Srdivacky dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 169198090Srdivacky if (Inc->getOpcode() == Instruction::Add && 170198090Srdivacky Inc->getOperand(0) == PN) 171198090Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 172198090Srdivacky if (CI->equalsInt(1)) 173198090Srdivacky return PN; 174198090Srdivacky } 175198090Srdivacky return 0; 176198090Srdivacky} 177198090Srdivacky 178198090Srdivacky/// isLCSSAForm - Return true if the Loop is in LCSSA form 179205218Srdivackybool Loop::isLCSSAForm(DominatorTree &DT) const { 180198090Srdivacky for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 181199481Srdivacky BasicBlock *BB = *BI; 182199481Srdivacky for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 183198090Srdivacky for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 184198090Srdivacky ++UI) { 185210299Sed User *U = *UI; 186210299Sed BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 187210299Sed if (PHINode *P = dyn_cast<PHINode>(U)) 188198090Srdivacky UserBB = P->getIncomingBlock(UI); 189198090Srdivacky 190204961Srdivacky // Check the current block, as a fast-path, before checking whether 191204961Srdivacky // the use is anywhere in the loop. Most values are used in the same 192204961Srdivacky // block they are defined in. Also, blocks not reachable from the 193204961Srdivacky // entry are special; uses in them don't need to go through PHIs. 194204961Srdivacky if (UserBB != BB && 195263509Sdim !contains(UserBB) && 196205218Srdivacky DT.isReachableFromEntry(UserBB)) 197198090Srdivacky return false; 198198090Srdivacky } 199198090Srdivacky } 200198090Srdivacky 201198090Srdivacky return true; 202198090Srdivacky} 203198090Srdivacky 204198090Srdivacky/// isLoopSimplifyForm - Return true if the Loop is in the form that 205198090Srdivacky/// the LoopSimplify form transforms loops to, which is sometimes called 206198090Srdivacky/// normal form. 207198090Srdivackybool Loop::isLoopSimplifyForm() const { 208199481Srdivacky // Normal-form loops have a preheader, a single backedge, and all of their 209199481Srdivacky // exits have all their predecessors inside the loop. 210199481Srdivacky return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 211199481Srdivacky} 212199481Srdivacky 213235633Sdim/// isSafeToClone - Return true if the loop body is safe to clone in practice. 214235633Sdim/// Routines that reform the loop CFG and split edges often fail on indirectbr. 215235633Sdimbool Loop::isSafeToClone() const { 216252723Sdim // Return false if any loop blocks contain indirectbrs, or there are any calls 217252723Sdim // to noduplicate functions. 218235633Sdim for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) { 219263509Sdim if (isa<IndirectBrInst>((*I)->getTerminator())) 220235633Sdim return false; 221263509Sdim 222263509Sdim if (const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator())) 223252723Sdim if (II->hasFnAttr(Attribute::NoDuplicate)) 224252723Sdim return false; 225252723Sdim 226252723Sdim for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { 227252723Sdim if (const CallInst *CI = dyn_cast<CallInst>(BI)) { 228252723Sdim if (CI->hasFnAttr(Attribute::NoDuplicate)) 229252723Sdim return false; 230252723Sdim } 231252723Sdim } 232235633Sdim } 233235633Sdim return true; 234235633Sdim} 235235633Sdim 236263509SdimMDNode *Loop::getLoopID() const { 237263509Sdim MDNode *LoopID = 0; 238263509Sdim if (isLoopSimplifyForm()) { 239263509Sdim LoopID = getLoopLatch()->getTerminator()->getMetadata(LoopMDName); 240263509Sdim } else { 241263509Sdim // Go through each predecessor of the loop header and check the 242263509Sdim // terminator for the metadata. 243263509Sdim BasicBlock *H = getHeader(); 244263509Sdim for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { 245263509Sdim TerminatorInst *TI = (*I)->getTerminator(); 246263509Sdim MDNode *MD = 0; 247252723Sdim 248263509Sdim // Check if this terminator branches to the loop header. 249263509Sdim for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { 250263509Sdim if (TI->getSuccessor(i) == H) { 251263509Sdim MD = TI->getMetadata(LoopMDName); 252263509Sdim break; 253263509Sdim } 254263509Sdim } 255263509Sdim if (!MD) 256263509Sdim return 0; 257252723Sdim 258263509Sdim if (!LoopID) 259263509Sdim LoopID = MD; 260263509Sdim else if (MD != LoopID) 261263509Sdim return 0; 262263509Sdim } 263263509Sdim } 264263509Sdim if (!LoopID || LoopID->getNumOperands() == 0 || 265263509Sdim LoopID->getOperand(0) != LoopID) 266263509Sdim return 0; 267263509Sdim return LoopID; 268263509Sdim} 269252723Sdim 270263509Sdimvoid Loop::setLoopID(MDNode *LoopID) const { 271263509Sdim assert(LoopID && "Loop ID should not be null"); 272263509Sdim assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand"); 273263509Sdim assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself"); 274263509Sdim 275263509Sdim if (isLoopSimplifyForm()) { 276263509Sdim getLoopLatch()->getTerminator()->setMetadata(LoopMDName, LoopID); 277263509Sdim return; 278263509Sdim } 279263509Sdim 280263509Sdim BasicBlock *H = getHeader(); 281263509Sdim for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { 282263509Sdim TerminatorInst *TI = (*I)->getTerminator(); 283263509Sdim for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { 284263509Sdim if (TI->getSuccessor(i) == H) 285263509Sdim TI->setMetadata(LoopMDName, LoopID); 286263509Sdim } 287263509Sdim } 288263509Sdim} 289263509Sdim 290263509Sdimbool Loop::isAnnotatedParallel() const { 291263509Sdim MDNode *desiredLoopIdMetadata = getLoopID(); 292263509Sdim 293252723Sdim if (!desiredLoopIdMetadata) 294252723Sdim return false; 295252723Sdim 296252723Sdim // The loop branch contains the parallel loop metadata. In order to ensure 297252723Sdim // that any parallel-loop-unaware optimization pass hasn't added loop-carried 298252723Sdim // dependencies (thus converted the loop back to a sequential loop), check 299252723Sdim // that all the memory instructions in the loop contain parallelism metadata 300252723Sdim // that point to the same unique "loop id metadata" the loop branch does. 301252723Sdim for (block_iterator BB = block_begin(), BE = block_end(); BB != BE; ++BB) { 302252723Sdim for (BasicBlock::iterator II = (*BB)->begin(), EE = (*BB)->end(); 303252723Sdim II != EE; II++) { 304252723Sdim 305252723Sdim if (!II->mayReadOrWriteMemory()) 306252723Sdim continue; 307252723Sdim 308252723Sdim // The memory instruction can refer to the loop identifier metadata 309252723Sdim // directly or indirectly through another list metadata (in case of 310252723Sdim // nested parallel loops). The loop identifier metadata refers to 311252723Sdim // itself so we can check both cases with the same routine. 312263509Sdim MDNode *loopIdMD = II->getMetadata("llvm.mem.parallel_loop_access"); 313263509Sdim 314263509Sdim if (!loopIdMD) 315263509Sdim return false; 316263509Sdim 317252723Sdim bool loopIdMDFound = false; 318252723Sdim for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) { 319252723Sdim if (loopIdMD->getOperand(i) == desiredLoopIdMetadata) { 320252723Sdim loopIdMDFound = true; 321252723Sdim break; 322252723Sdim } 323252723Sdim } 324252723Sdim 325252723Sdim if (!loopIdMDFound) 326252723Sdim return false; 327252723Sdim } 328252723Sdim } 329252723Sdim return true; 330252723Sdim} 331252723Sdim 332252723Sdim 333199481Srdivacky/// hasDedicatedExits - Return true if no exit block for the loop 334199481Srdivacky/// has a predecessor that is outside the loop. 335199481Srdivackybool Loop::hasDedicatedExits() const { 336198090Srdivacky // Each predecessor of each exit block of a normal loop is contained 337198090Srdivacky // within the loop. 338198090Srdivacky SmallVector<BasicBlock *, 4> ExitBlocks; 339198090Srdivacky getExitBlocks(ExitBlocks); 340198090Srdivacky for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 341198090Srdivacky for (pred_iterator PI = pred_begin(ExitBlocks[i]), 342198090Srdivacky PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 343263509Sdim if (!contains(*PI)) 344198090Srdivacky return false; 345198090Srdivacky // All the requirements are met. 346198090Srdivacky return true; 347198090Srdivacky} 348198090Srdivacky 349198090Srdivacky/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 350198090Srdivacky/// These are the blocks _outside of the current loop_ which are branched to. 351200581Srdivacky/// This assumes that loop exits are in canonical form. 352198090Srdivacky/// 353198090Srdivackyvoid 354198090SrdivackyLoop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 355200581Srdivacky assert(hasDedicatedExits() && 356200581Srdivacky "getUniqueExitBlocks assumes the loop has canonical form exits!"); 357198090Srdivacky 358198090Srdivacky SmallVector<BasicBlock *, 32> switchExitBlocks; 359198090Srdivacky 360198090Srdivacky for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 361198090Srdivacky 362198090Srdivacky BasicBlock *current = *BI; 363198090Srdivacky switchExitBlocks.clear(); 364198090Srdivacky 365212904Sdim for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { 366198090Srdivacky // If block is inside the loop then it is not a exit block. 367263509Sdim if (contains(*I)) 368198090Srdivacky continue; 369198090Srdivacky 370212904Sdim pred_iterator PI = pred_begin(*I); 371198090Srdivacky BasicBlock *firstPred = *PI; 372198090Srdivacky 373198090Srdivacky // If current basic block is this exit block's first predecessor 374198090Srdivacky // then only insert exit block in to the output ExitBlocks vector. 375198090Srdivacky // This ensures that same exit block is not inserted twice into 376198090Srdivacky // ExitBlocks vector. 377198090Srdivacky if (current != firstPred) 378198090Srdivacky continue; 379198090Srdivacky 380198090Srdivacky // If a terminator has more then two successors, for example SwitchInst, 381198090Srdivacky // then it is possible that there are multiple edges from current block 382198090Srdivacky // to one exit block. 383212904Sdim if (std::distance(succ_begin(current), succ_end(current)) <= 2) { 384198090Srdivacky ExitBlocks.push_back(*I); 385198090Srdivacky continue; 386198090Srdivacky } 387198090Srdivacky 388198090Srdivacky // In case of multiple edges from current block to exit block, collect 389198090Srdivacky // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 390198090Srdivacky // duplicate edges. 391198090Srdivacky if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 392198090Srdivacky == switchExitBlocks.end()) { 393198090Srdivacky switchExitBlocks.push_back(*I); 394198090Srdivacky ExitBlocks.push_back(*I); 395198090Srdivacky } 396198090Srdivacky } 397198090Srdivacky } 398198090Srdivacky} 399198090Srdivacky 400198090Srdivacky/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 401198090Srdivacky/// block, return that block. Otherwise return null. 402198090SrdivackyBasicBlock *Loop::getUniqueExitBlock() const { 403198090Srdivacky SmallVector<BasicBlock *, 8> UniqueExitBlocks; 404198090Srdivacky getUniqueExitBlocks(UniqueExitBlocks); 405198090Srdivacky if (UniqueExitBlocks.size() == 1) 406198090Srdivacky return UniqueExitBlocks[0]; 407198090Srdivacky return 0; 408198090Srdivacky} 409198090Srdivacky 410245431Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 411202375Srdivackyvoid Loop::dump() const { 412202375Srdivacky print(dbgs()); 413202375Srdivacky} 414245431Sdim#endif 415202375Srdivacky 416193323Sed//===----------------------------------------------------------------------===// 417226890Sdim// UnloopUpdater implementation 418226890Sdim// 419226890Sdim 420226890Sdimnamespace { 421226890Sdim/// Find the new parent loop for all blocks within the "unloop" whose last 422226890Sdim/// backedges has just been removed. 423226890Sdimclass UnloopUpdater { 424226890Sdim Loop *Unloop; 425226890Sdim LoopInfo *LI; 426226890Sdim 427226890Sdim LoopBlocksDFS DFS; 428226890Sdim 429226890Sdim // Map unloop's immediate subloops to their nearest reachable parents. Nested 430226890Sdim // loops within these subloops will not change parents. However, an immediate 431226890Sdim // subloop's new parent will be the nearest loop reachable from either its own 432226890Sdim // exits *or* any of its nested loop's exits. 433226890Sdim DenseMap<Loop*, Loop*> SubloopParents; 434226890Sdim 435226890Sdim // Flag the presence of an irreducible backedge whose destination is a block 436226890Sdim // directly contained by the original unloop. 437226890Sdim bool FoundIB; 438226890Sdim 439226890Sdimpublic: 440226890Sdim UnloopUpdater(Loop *UL, LoopInfo *LInfo) : 441226890Sdim Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {} 442226890Sdim 443226890Sdim void updateBlockParents(); 444226890Sdim 445226890Sdim void removeBlocksFromAncestors(); 446226890Sdim 447226890Sdim void updateSubloopParents(); 448226890Sdim 449226890Sdimprotected: 450226890Sdim Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); 451226890Sdim}; 452226890Sdim} // end anonymous namespace 453226890Sdim 454226890Sdim/// updateBlockParents - Update the parent loop for all blocks that are directly 455226890Sdim/// contained within the original "unloop". 456226890Sdimvoid UnloopUpdater::updateBlockParents() { 457226890Sdim if (Unloop->getNumBlocks()) { 458226890Sdim // Perform a post order CFG traversal of all blocks within this loop, 459226890Sdim // propagating the nearest loop from sucessors to predecessors. 460226890Sdim LoopBlocksTraversal Traversal(DFS, LI); 461226890Sdim for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 462226890Sdim POE = Traversal.end(); POI != POE; ++POI) { 463226890Sdim 464226890Sdim Loop *L = LI->getLoopFor(*POI); 465226890Sdim Loop *NL = getNearestLoop(*POI, L); 466226890Sdim 467226890Sdim if (NL != L) { 468226890Sdim // For reducible loops, NL is now an ancestor of Unloop. 469226890Sdim assert((NL != Unloop && (!NL || NL->contains(Unloop))) && 470226890Sdim "uninitialized successor"); 471226890Sdim LI->changeLoopFor(*POI, NL); 472226890Sdim } 473226890Sdim else { 474226890Sdim // Or the current block is part of a subloop, in which case its parent 475226890Sdim // is unchanged. 476226890Sdim assert((FoundIB || Unloop->contains(L)) && "uninitialized successor"); 477226890Sdim } 478226890Sdim } 479226890Sdim } 480226890Sdim // Each irreducible loop within the unloop induces a round of iteration using 481226890Sdim // the DFS result cached by Traversal. 482226890Sdim bool Changed = FoundIB; 483226890Sdim for (unsigned NIters = 0; Changed; ++NIters) { 484226890Sdim assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"); 485226890Sdim 486226890Sdim // Iterate over the postorder list of blocks, propagating the nearest loop 487226890Sdim // from successors to predecessors as before. 488226890Sdim Changed = false; 489226890Sdim for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), 490226890Sdim POE = DFS.endPostorder(); POI != POE; ++POI) { 491226890Sdim 492226890Sdim Loop *L = LI->getLoopFor(*POI); 493226890Sdim Loop *NL = getNearestLoop(*POI, L); 494226890Sdim if (NL != L) { 495226890Sdim assert(NL != Unloop && (!NL || NL->contains(Unloop)) && 496226890Sdim "uninitialized successor"); 497226890Sdim LI->changeLoopFor(*POI, NL); 498226890Sdim Changed = true; 499226890Sdim } 500226890Sdim } 501226890Sdim } 502226890Sdim} 503226890Sdim 504226890Sdim/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below 505226890Sdim/// their new parents. 506226890Sdimvoid UnloopUpdater::removeBlocksFromAncestors() { 507235633Sdim // Remove all unloop's blocks (including those in nested subloops) from 508235633Sdim // ancestors below the new parent loop. 509226890Sdim for (Loop::block_iterator BI = Unloop->block_begin(), 510226890Sdim BE = Unloop->block_end(); BI != BE; ++BI) { 511235633Sdim Loop *OuterParent = LI->getLoopFor(*BI); 512235633Sdim if (Unloop->contains(OuterParent)) { 513235633Sdim while (OuterParent->getParentLoop() != Unloop) 514235633Sdim OuterParent = OuterParent->getParentLoop(); 515235633Sdim OuterParent = SubloopParents[OuterParent]; 516235633Sdim } 517226890Sdim // Remove blocks from former Ancestors except Unloop itself which will be 518226890Sdim // deleted. 519235633Sdim for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent; 520226890Sdim OldParent = OldParent->getParentLoop()) { 521226890Sdim assert(OldParent && "new loop is not an ancestor of the original"); 522226890Sdim OldParent->removeBlockFromLoop(*BI); 523226890Sdim } 524226890Sdim } 525226890Sdim} 526226890Sdim 527226890Sdim/// updateSubloopParents - Update the parent loop for all subloops directly 528226890Sdim/// nested within unloop. 529226890Sdimvoid UnloopUpdater::updateSubloopParents() { 530226890Sdim while (!Unloop->empty()) { 531226890Sdim Loop *Subloop = *llvm::prior(Unloop->end()); 532226890Sdim Unloop->removeChildLoop(llvm::prior(Unloop->end())); 533226890Sdim 534226890Sdim assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); 535245431Sdim if (Loop *Parent = SubloopParents[Subloop]) 536245431Sdim Parent->addChildLoop(Subloop); 537226890Sdim else 538226890Sdim LI->addTopLevelLoop(Subloop); 539226890Sdim } 540226890Sdim} 541226890Sdim 542226890Sdim/// getNearestLoop - Return the nearest parent loop among this block's 543226890Sdim/// successors. If a successor is a subloop header, consider its parent to be 544226890Sdim/// the nearest parent of the subloop's exits. 545226890Sdim/// 546226890Sdim/// For subloop blocks, simply update SubloopParents and return NULL. 547226890SdimLoop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { 548226890Sdim 549226890Sdim // Initially for blocks directly contained by Unloop, NearLoop == Unloop and 550226890Sdim // is considered uninitialized. 551226890Sdim Loop *NearLoop = BBLoop; 552226890Sdim 553226890Sdim Loop *Subloop = 0; 554226890Sdim if (NearLoop != Unloop && Unloop->contains(NearLoop)) { 555226890Sdim Subloop = NearLoop; 556226890Sdim // Find the subloop ancestor that is directly contained within Unloop. 557226890Sdim while (Subloop->getParentLoop() != Unloop) { 558226890Sdim Subloop = Subloop->getParentLoop(); 559226890Sdim assert(Subloop && "subloop is not an ancestor of the original loop"); 560226890Sdim } 561226890Sdim // Get the current nearest parent of the Subloop exits, initially Unloop. 562245431Sdim NearLoop = 563245431Sdim SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second; 564226890Sdim } 565226890Sdim 566226890Sdim succ_iterator I = succ_begin(BB), E = succ_end(BB); 567226890Sdim if (I == E) { 568226890Sdim assert(!Subloop && "subloop blocks must have a successor"); 569226890Sdim NearLoop = 0; // unloop blocks may now exit the function. 570226890Sdim } 571226890Sdim for (; I != E; ++I) { 572226890Sdim if (*I == BB) 573226890Sdim continue; // self loops are uninteresting 574226890Sdim 575226890Sdim Loop *L = LI->getLoopFor(*I); 576226890Sdim if (L == Unloop) { 577226890Sdim // This successor has not been processed. This path must lead to an 578226890Sdim // irreducible backedge. 579226890Sdim assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); 580226890Sdim FoundIB = true; 581226890Sdim } 582226890Sdim if (L != Unloop && Unloop->contains(L)) { 583226890Sdim // Successor is in a subloop. 584226890Sdim if (Subloop) 585226890Sdim continue; // Branching within subloops. Ignore it. 586226890Sdim 587226890Sdim // BB branches from the original into a subloop header. 588226890Sdim assert(L->getParentLoop() == Unloop && "cannot skip into nested loops"); 589226890Sdim 590226890Sdim // Get the current nearest parent of the Subloop's exits. 591226890Sdim L = SubloopParents[L]; 592226890Sdim // L could be Unloop if the only exit was an irreducible backedge. 593226890Sdim } 594226890Sdim if (L == Unloop) { 595226890Sdim continue; 596226890Sdim } 597226890Sdim // Handle critical edges from Unloop into a sibling loop. 598226890Sdim if (L && !L->contains(Unloop)) { 599226890Sdim L = L->getParentLoop(); 600226890Sdim } 601226890Sdim // Remember the nearest parent loop among successors or subloop exits. 602226890Sdim if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L)) 603226890Sdim NearLoop = L; 604226890Sdim } 605226890Sdim if (Subloop) { 606226890Sdim SubloopParents[Subloop] = NearLoop; 607226890Sdim return BBLoop; 608226890Sdim } 609226890Sdim return NearLoop; 610226890Sdim} 611226890Sdim 612226890Sdim//===----------------------------------------------------------------------===// 613193323Sed// LoopInfo implementation 614193323Sed// 615193323Sedbool LoopInfo::runOnFunction(Function &) { 616193323Sed releaseMemory(); 617245431Sdim LI.Analyze(getAnalysis<DominatorTree>().getBase()); 618193323Sed return false; 619193323Sed} 620193323Sed 621226890Sdim/// updateUnloop - The last backedge has been removed from a loop--now the 622226890Sdim/// "unloop". Find a new parent for the blocks contained within unloop and 623226890Sdim/// update the loop tree. We don't necessarily have valid dominators at this 624226890Sdim/// point, but LoopInfo is still valid except for the removal of this loop. 625226890Sdim/// 626226890Sdim/// Note that Unloop may now be an empty loop. Calling Loop::getHeader without 627226890Sdim/// checking first is illegal. 628226890Sdimvoid LoopInfo::updateUnloop(Loop *Unloop) { 629226890Sdim 630226890Sdim // First handle the special case of no parent loop to simplify the algorithm. 631226890Sdim if (!Unloop->getParentLoop()) { 632226890Sdim // Since BBLoop had no parent, Unloop blocks are no longer in a loop. 633226890Sdim for (Loop::block_iterator I = Unloop->block_begin(), 634226890Sdim E = Unloop->block_end(); I != E; ++I) { 635226890Sdim 636226890Sdim // Don't reparent blocks in subloops. 637226890Sdim if (getLoopFor(*I) != Unloop) 638226890Sdim continue; 639226890Sdim 640226890Sdim // Blocks no longer have a parent but are still referenced by Unloop until 641226890Sdim // the Unloop object is deleted. 642226890Sdim LI.changeLoopFor(*I, 0); 643226890Sdim } 644226890Sdim 645226890Sdim // Remove the loop from the top-level LoopInfo object. 646226890Sdim for (LoopInfo::iterator I = LI.begin();; ++I) { 647226890Sdim assert(I != LI.end() && "Couldn't find loop"); 648226890Sdim if (*I == Unloop) { 649226890Sdim LI.removeLoop(I); 650226890Sdim break; 651226890Sdim } 652226890Sdim } 653226890Sdim 654226890Sdim // Move all of the subloops to the top-level. 655226890Sdim while (!Unloop->empty()) 656226890Sdim LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end()))); 657226890Sdim 658226890Sdim return; 659226890Sdim } 660226890Sdim 661226890Sdim // Update the parent loop for all blocks within the loop. Blocks within 662226890Sdim // subloops will not change parents. 663226890Sdim UnloopUpdater Updater(Unloop, this); 664226890Sdim Updater.updateBlockParents(); 665226890Sdim 666226890Sdim // Remove blocks from former ancestor loops. 667226890Sdim Updater.removeBlocksFromAncestors(); 668226890Sdim 669226890Sdim // Add direct subloops as children in their new parent loop. 670226890Sdim Updater.updateSubloopParents(); 671226890Sdim 672226890Sdim // Remove unloop from its parent loop. 673226890Sdim Loop *ParentLoop = Unloop->getParentLoop(); 674226890Sdim for (Loop::iterator I = ParentLoop->begin();; ++I) { 675226890Sdim assert(I != ParentLoop->end() && "Couldn't find loop"); 676226890Sdim if (*I == Unloop) { 677226890Sdim ParentLoop->removeChildLoop(I); 678226890Sdim break; 679226890Sdim } 680226890Sdim } 681226890Sdim} 682226890Sdim 683198090Srdivackyvoid LoopInfo::verifyAnalysis() const { 684198090Srdivacky // LoopInfo is a FunctionPass, but verifying every loop in the function 685198090Srdivacky // each time verifyAnalysis is called is very expensive. The 686198090Srdivacky // -verify-loop-info option can enable this. In order to perform some 687198090Srdivacky // checking by default, LoopPass has been taught to call verifyLoop 688198090Srdivacky // manually during loop pass sequences. 689198090Srdivacky 690198090Srdivacky if (!VerifyLoopInfo) return; 691198090Srdivacky 692226890Sdim DenseSet<const Loop*> Loops; 693198090Srdivacky for (iterator I = begin(), E = end(); I != E; ++I) { 694198090Srdivacky assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 695226890Sdim (*I)->verifyLoopNest(&Loops); 696198090Srdivacky } 697198090Srdivacky 698226890Sdim // Verify that blocks are mapped to valid loops. 699226890Sdim for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(), 700226890Sdim E = LI.BBMap.end(); I != E; ++I) { 701226890Sdim assert(Loops.count(I->second) && "orphaned loop"); 702226890Sdim assert(I->second->contains(I->first) && "orphaned block"); 703226890Sdim } 704198090Srdivacky} 705198090Srdivacky 706193323Sedvoid LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 707193323Sed AU.setPreservesAll(); 708193323Sed AU.addRequired<DominatorTree>(); 709193323Sed} 710198090Srdivacky 711198090Srdivackyvoid LoopInfo::print(raw_ostream &OS, const Module*) const { 712198090Srdivacky LI.print(OS); 713198090Srdivacky} 714198090Srdivacky 715226890Sdim//===----------------------------------------------------------------------===// 716226890Sdim// LoopBlocksDFS implementation 717226890Sdim// 718226890Sdim 719226890Sdim/// Traverse the loop blocks and store the DFS result. 720226890Sdim/// Useful for clients that just want the final DFS result and don't need to 721226890Sdim/// visit blocks during the initial traversal. 722226890Sdimvoid LoopBlocksDFS::perform(LoopInfo *LI) { 723226890Sdim LoopBlocksTraversal Traversal(*this, LI); 724226890Sdim for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 725226890Sdim POE = Traversal.end(); POI != POE; ++POI) ; 726226890Sdim} 727