LoopInfo.cpp revision 199481
1210284Sjmallett//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 2215990Sjmallett// 3215990Sjmallett// The LLVM Compiler Infrastructure 4210284Sjmallett// 5210284Sjmallett// This file is distributed under the University of Illinois Open Source 6215990Sjmallett// License. See LICENSE.TXT for details. 7215990Sjmallett// 8215990Sjmallett//===----------------------------------------------------------------------===// 9210284Sjmallett// 10215990Sjmallett// This file defines the LoopInfo class that is used to identify natural loops 11215990Sjmallett// and determine the loop depth of various nodes of the CFG. Note that the 12210284Sjmallett// loops identified may actually be several natural loops that share the same 13215990Sjmallett// header node... not just a single natural loop. 14215990Sjmallett// 15215990Sjmallett//===----------------------------------------------------------------------===// 16215990Sjmallett 17215990Sjmallett#include "llvm/Analysis/LoopInfo.h" 18215990Sjmallett#include "llvm/Constants.h" 19215990Sjmallett#include "llvm/Instructions.h" 20215990Sjmallett#include "llvm/Analysis/Dominators.h" 21215990Sjmallett#include "llvm/Assembly/Writer.h" 22215990Sjmallett#include "llvm/Support/CFG.h" 23215990Sjmallett#include "llvm/Support/CommandLine.h" 24215990Sjmallett#include "llvm/ADT/DepthFirstIterator.h" 25215990Sjmallett#include "llvm/ADT/SmallPtrSet.h" 26215990Sjmallett#include <algorithm> 27215990Sjmallettusing namespace llvm; 28215990Sjmallett 29215990Sjmallett// Always verify loopinfo if expensive checking is enabled. 30215990Sjmallett#ifdef XDEBUG 31215990Sjmallettbool VerifyLoopInfo = true; 32215990Sjmallett#else 33215990Sjmallettbool VerifyLoopInfo = false; 34215990Sjmallett#endif 35215990Sjmallettstatic cl::opt<bool,true> 36215990SjmallettVerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), 37215990Sjmallett cl::desc("Verify loop info (time consuming)")); 38210284Sjmallett 39210284Sjmallettchar LoopInfo::ID = 0; 40210284Sjmallettstatic RegisterPass<LoopInfo> 41215990SjmallettX("loops", "Natural Loop Information", true, true); 42210284Sjmallett 43210284Sjmallett//===----------------------------------------------------------------------===// 44210284Sjmallett// Loop implementation 45210284Sjmallett// 46210284Sjmallett 47210284Sjmallett/// isLoopInvariant - Return true if the specified value is loop invariant 48210284Sjmallett/// 49210284Sjmallettbool Loop::isLoopInvariant(Value *V) const { 50210284Sjmallett if (Instruction *I = dyn_cast<Instruction>(V)) 51210284Sjmallett return isLoopInvariant(I); 52210284Sjmallett return true; // All non-instructions are loop invariant 53210284Sjmallett} 54215990Sjmallett 55215990Sjmallett/// isLoopInvariant - Return true if the specified instruction is 56210284Sjmallett/// loop-invariant. 57210284Sjmallett/// 58210284Sjmallettbool Loop::isLoopInvariant(Instruction *I) const { 59210284Sjmallett return !contains(I->getParent()); 60210284Sjmallett} 61210284Sjmallett 62215990Sjmallett/// makeLoopInvariant - If the given value is an instruciton inside of the 63215990Sjmallett/// loop and it can be hoisted, do so to make it trivially loop-invariant. 64210284Sjmallett/// Return true if the value after any hoisting is loop invariant. This 65210284Sjmallett/// function can be used as a slightly more aggressive replacement for 66210284Sjmallett/// isLoopInvariant. 67215990Sjmallett/// 68210284Sjmallett/// If InsertPt is specified, it is the point to hoist instructions to. 69210284Sjmallett/// If null, the terminator of the loop preheader is used. 70210284Sjmallett/// 71210284Sjmallettbool Loop::makeLoopInvariant(Value *V, bool &Changed, 72210284Sjmallett Instruction *InsertPt) const { 73210284Sjmallett if (Instruction *I = dyn_cast<Instruction>(V)) 74210284Sjmallett return makeLoopInvariant(I, Changed, InsertPt); 75210284Sjmallett return true; // All non-instructions are loop-invariant. 76210284Sjmallett} 77210284Sjmallett 78210284Sjmallett/// makeLoopInvariant - If the given instruction is inside of the 79210284Sjmallett/// loop and it can be hoisted, do so to make it trivially loop-invariant. 80210284Sjmallett/// Return true if the instruction after any hoisting is loop invariant. This 81210284Sjmallett/// function can be used as a slightly more aggressive replacement for 82210284Sjmallett/// isLoopInvariant. 83210284Sjmallett/// 84210284Sjmallett/// If InsertPt is specified, it is the point to hoist instructions to. 85210284Sjmallett/// If null, the terminator of the loop preheader is used. 86210284Sjmallett/// 87210284Sjmallettbool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 88210284Sjmallett Instruction *InsertPt) const { 89210284Sjmallett // Test if the value is already loop-invariant. 90210284Sjmallett if (isLoopInvariant(I)) 91215990Sjmallett return true; 92210284Sjmallett if (!I->isSafeToSpeculativelyExecute()) 93210284Sjmallett return false; 94210284Sjmallett if (I->mayReadFromMemory()) 95210284Sjmallett return false; 96210284Sjmallett // Determine the insertion point, unless one was given. 97210284Sjmallett if (!InsertPt) { 98210284Sjmallett BasicBlock *Preheader = getLoopPreheader(); 99210284Sjmallett // Without a preheader, hoisting is not feasible. 100210284Sjmallett if (!Preheader) 101210284Sjmallett return false; 102210284Sjmallett InsertPt = Preheader->getTerminator(); 103210284Sjmallett } 104210284Sjmallett // Don't hoist instructions with loop-variant operands. 105210284Sjmallett for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 106210284Sjmallett if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 107210284Sjmallett return false; 108210284Sjmallett // Hoist. 109210284Sjmallett I->moveBefore(InsertPt); 110210284Sjmallett Changed = true; 111210284Sjmallett return true; 112210284Sjmallett} 113210284Sjmallett 114210284Sjmallett/// getCanonicalInductionVariable - Check to see if the loop has a canonical 115210284Sjmallett/// induction variable: an integer recurrence that starts at 0 and increments 116210284Sjmallett/// by one each time through the loop. If so, return the phi node that 117210284Sjmallett/// corresponds to it. 118210284Sjmallett/// 119210284Sjmallett/// The IndVarSimplify pass transforms loops to have a canonical induction 120210284Sjmallett/// variable. 121210284Sjmallett/// 122210284SjmallettPHINode *Loop::getCanonicalInductionVariable() const { 123210284Sjmallett BasicBlock *H = getHeader(); 124210284Sjmallett 125210284Sjmallett BasicBlock *Incoming = 0, *Backedge = 0; 126210284Sjmallett typedef GraphTraits<Inverse<BasicBlock*> > InvBlockTraits; 127210284Sjmallett InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(H); 128210284Sjmallett assert(PI != InvBlockTraits::child_end(H) && 129210284Sjmallett "Loop must have at least one backedge!"); 130210284Sjmallett Backedge = *PI++; 131210284Sjmallett if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop 132210284Sjmallett Incoming = *PI++; 133210284Sjmallett if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? 134210284Sjmallett 135210284Sjmallett if (contains(Incoming)) { 136210284Sjmallett if (contains(Backedge)) 137210284Sjmallett return 0; 138210284Sjmallett std::swap(Incoming, Backedge); 139210284Sjmallett } else if (!contains(Backedge)) 140210284Sjmallett return 0; 141210284Sjmallett 142210284Sjmallett // Loop over all of the PHI nodes, looking for a canonical indvar. 143210284Sjmallett for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 144210284Sjmallett PHINode *PN = cast<PHINode>(I); 145210284Sjmallett if (ConstantInt *CI = 146210284Sjmallett dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 147210284Sjmallett if (CI->isNullValue()) 148210284Sjmallett if (Instruction *Inc = 149210284Sjmallett dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 150210284Sjmallett if (Inc->getOpcode() == Instruction::Add && 151215990Sjmallett Inc->getOperand(0) == PN) 152210284Sjmallett if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 153210284Sjmallett if (CI->equalsInt(1)) 154215990Sjmallett return PN; 155210284Sjmallett } 156210284Sjmallett return 0; 157210284Sjmallett} 158215990Sjmallett 159210284Sjmallett/// getCanonicalInductionVariableIncrement - Return the LLVM value that holds 160215990Sjmallett/// the canonical induction variable value for the "next" iteration of the 161210284Sjmallett/// loop. This always succeeds if getCanonicalInductionVariable succeeds. 162210284Sjmallett/// 163210284SjmallettInstruction *Loop::getCanonicalInductionVariableIncrement() const { 164210284Sjmallett if (PHINode *PN = getCanonicalInductionVariable()) { 165210284Sjmallett bool P1InLoop = contains(PN->getIncomingBlock(1)); 166215990Sjmallett return cast<Instruction>(PN->getIncomingValue(P1InLoop)); 167210284Sjmallett } 168210284Sjmallett return 0; 169215990Sjmallett} 170210284Sjmallett 171210284Sjmallett/// getTripCount - Return a loop-invariant LLVM value indicating the number of 172210284Sjmallett/// times the loop will be executed. Note that this means that the backedge 173215990Sjmallett/// of the loop executes N-1 times. If the trip-count cannot be determined, 174210284Sjmallett/// this returns null. 175215990Sjmallett/// 176210284Sjmallett/// The IndVarSimplify pass transforms loops to have a form that this 177210284Sjmallett/// function easily understands. 178210284Sjmallett/// 179210284SjmallettValue *Loop::getTripCount() const { 180210284Sjmallett // Canonical loops will end with a 'cmp ne I, V', where I is the incremented 181210284Sjmallett // canonical induction variable and V is the trip count of the loop. 182210284Sjmallett Instruction *Inc = getCanonicalInductionVariableIncrement(); 183210284Sjmallett if (Inc == 0) return 0; 184210284Sjmallett PHINode *IV = cast<PHINode>(Inc->getOperand(0)); 185210284Sjmallett 186210284Sjmallett BasicBlock *BackedgeBlock = 187210284Sjmallett IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); 188210284Sjmallett 189210284Sjmallett if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator())) 190210284Sjmallett if (BI->isConditional()) { 191210284Sjmallett if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 192210284Sjmallett if (ICI->getOperand(0) == Inc) { 193210284Sjmallett if (BI->getSuccessor(0) == getHeader()) { 194210284Sjmallett if (ICI->getPredicate() == ICmpInst::ICMP_NE) 195215990Sjmallett return ICI->getOperand(1); 196210284Sjmallett } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { 197215990Sjmallett return ICI->getOperand(1); 198210284Sjmallett } 199215990Sjmallett } 200210284Sjmallett } 201210284Sjmallett } 202210284Sjmallett 203210284Sjmallett return 0; 204210284Sjmallett} 205210284Sjmallett 206210284Sjmallett/// getSmallConstantTripCount - Returns the trip count of this loop as a 207210284Sjmallett/// normal unsigned value, if possible. Returns 0 if the trip count is unknown 208210284Sjmallett/// of not constant. Will also return 0 if the trip count is very large 209210284Sjmallett/// (>= 2^32) 210210284Sjmallettunsigned Loop::getSmallConstantTripCount() const { 211215990Sjmallett Value* TripCount = this->getTripCount(); 212210284Sjmallett if (TripCount) { 213215990Sjmallett if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) { 214210284Sjmallett // Guard against huge trip counts. 215210284Sjmallett if (TripCountC->getValue().getActiveBits() <= 32) { 216215990Sjmallett return (unsigned)TripCountC->getZExtValue(); 217210284Sjmallett } 218215990Sjmallett } 219215990Sjmallett } 220210284Sjmallett return 0; 221210284Sjmallett} 222215990Sjmallett 223210284Sjmallett/// getSmallConstantTripMultiple - Returns the largest constant divisor of the 224215990Sjmallett/// trip count of this loop as a normal unsigned value, if possible. This 225210284Sjmallett/// means that the actual trip count is always a multiple of the returned 226210284Sjmallett/// value (don't forget the trip count could very well be zero as well!). 227210284Sjmallett/// 228215990Sjmallett/// Returns 1 if the trip count is unknown or not guaranteed to be the 229210284Sjmallett/// multiple of a constant (which is also the case if the trip count is simply 230210284Sjmallett/// constant, use getSmallConstantTripCount for that case), Will also return 1 231210284Sjmallett/// if the trip count is very large (>= 2^32). 232210284Sjmallettunsigned Loop::getSmallConstantTripMultiple() const { 233210284Sjmallett Value* TripCount = this->getTripCount(); 234210284Sjmallett // This will hold the ConstantInt result, if any 235210284Sjmallett ConstantInt *Result = NULL; 236210284Sjmallett if (TripCount) { 237210284Sjmallett // See if the trip count is constant itself 238210284Sjmallett Result = dyn_cast<ConstantInt>(TripCount); 239210284Sjmallett // if not, see if it is a multiplication 240210284Sjmallett if (!Result) 241210284Sjmallett if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) { 242210284Sjmallett switch (BO->getOpcode()) { 243210284Sjmallett case BinaryOperator::Mul: 244210284Sjmallett Result = dyn_cast<ConstantInt>(BO->getOperand(1)); 245210284Sjmallett break; 246210284Sjmallett default: 247210284Sjmallett break; 248210284Sjmallett } 249210284Sjmallett } 250210284Sjmallett } 251210284Sjmallett // Guard against huge trip counts. 252210284Sjmallett if (Result && Result->getValue().getActiveBits() <= 32) { 253210284Sjmallett return (unsigned)Result->getZExtValue(); 254210284Sjmallett } else { 255210284Sjmallett return 1; 256210284Sjmallett } 257210284Sjmallett} 258210284Sjmallett 259210284Sjmallett/// isLCSSAForm - Return true if the Loop is in LCSSA form 260210284Sjmallettbool Loop::isLCSSAForm() const { 261210284Sjmallett // Sort the blocks vector so that we can use binary search to do quick 262210284Sjmallett // lookups. 263210284Sjmallett SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 264210284Sjmallett 265210284Sjmallett for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 266210284Sjmallett BasicBlock *BB = *BI; 267210284Sjmallett for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 268210284Sjmallett for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 269210284Sjmallett ++UI) { 270210284Sjmallett BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 271210284Sjmallett if (PHINode *P = dyn_cast<PHINode>(*UI)) 272210284Sjmallett UserBB = P->getIncomingBlock(UI); 273210284Sjmallett 274210284Sjmallett // Check the current block, as a fast-path. Most values are used in 275210284Sjmallett // the same block they are defined in. 276210284Sjmallett if (UserBB != BB && !LoopBBs.count(UserBB)) 277210284Sjmallett return false; 278210284Sjmallett } 279210284Sjmallett } 280210284Sjmallett 281210284Sjmallett return true; 282210284Sjmallett} 283210284Sjmallett 284210284Sjmallett/// isLoopSimplifyForm - Return true if the Loop is in the form that 285210284Sjmallett/// the LoopSimplify form transforms loops to, which is sometimes called 286210284Sjmallett/// normal form. 287210284Sjmallettbool Loop::isLoopSimplifyForm() const { 288210284Sjmallett // Normal-form loops have a preheader, a single backedge, and all of their 289210284Sjmallett // exits have all their predecessors inside the loop. 290210284Sjmallett return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 291210284Sjmallett} 292210284Sjmallett 293210284Sjmallett/// hasDedicatedExits - Return true if no exit block for the loop 294210284Sjmallett/// has a predecessor that is outside the loop. 295210284Sjmallettbool Loop::hasDedicatedExits() const { 296210284Sjmallett // Sort the blocks vector so that we can use binary search to do quick 297210284Sjmallett // lookups. 298210284Sjmallett SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 299210284Sjmallett // Each predecessor of each exit block of a normal loop is contained 300210284Sjmallett // within the loop. 301210284Sjmallett SmallVector<BasicBlock *, 4> ExitBlocks; 302210284Sjmallett getExitBlocks(ExitBlocks); 303210284Sjmallett for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 304210284Sjmallett for (pred_iterator PI = pred_begin(ExitBlocks[i]), 305210284Sjmallett PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 306210284Sjmallett if (!LoopBBs.count(*PI)) 307210284Sjmallett return false; 308210284Sjmallett // All the requirements are met. 309210284Sjmallett return true; 310210284Sjmallett} 311210284Sjmallett 312210284Sjmallett/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 313210284Sjmallett/// These are the blocks _outside of the current loop_ which are branched to. 314210284Sjmallett/// This assumes that loop is in canonical form. 315210284Sjmallett/// 316210284Sjmallettvoid 317210284SjmallettLoop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 318210284Sjmallett assert(isLoopSimplifyForm() && 319210284Sjmallett "getUniqueExitBlocks assumes the loop is in canonical form!"); 320210284Sjmallett 321210284Sjmallett // Sort the blocks vector so that we can use binary search to do quick 322210284Sjmallett // lookups. 323210284Sjmallett SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end()); 324210284Sjmallett std::sort(LoopBBs.begin(), LoopBBs.end()); 325210284Sjmallett 326210284Sjmallett SmallVector<BasicBlock *, 32> switchExitBlocks; 327210284Sjmallett 328210284Sjmallett for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 329210284Sjmallett 330210284Sjmallett BasicBlock *current = *BI; 331210284Sjmallett switchExitBlocks.clear(); 332210284Sjmallett 333210284Sjmallett typedef GraphTraits<BasicBlock *> BlockTraits; 334210284Sjmallett typedef GraphTraits<Inverse<BasicBlock *> > InvBlockTraits; 335210284Sjmallett for (BlockTraits::ChildIteratorType I = 336210284Sjmallett BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 337210284Sjmallett I != E; ++I) { 338210284Sjmallett // If block is inside the loop then it is not a exit block. 339210284Sjmallett if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 340215990Sjmallett continue; 341210284Sjmallett 342210284Sjmallett InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(*I); 343210284Sjmallett BasicBlock *firstPred = *PI; 344210284Sjmallett 345210284Sjmallett // If current basic block is this exit block's first predecessor 346210284Sjmallett // then only insert exit block in to the output ExitBlocks vector. 347210284Sjmallett // This ensures that same exit block is not inserted twice into 348210284Sjmallett // ExitBlocks vector. 349210284Sjmallett if (current != firstPred) 350210284Sjmallett continue; 351210284Sjmallett 352210284Sjmallett // If a terminator has more then two successors, for example SwitchInst, 353210284Sjmallett // then it is possible that there are multiple edges from current block 354210284Sjmallett // to one exit block. 355210284Sjmallett if (std::distance(BlockTraits::child_begin(current), 356210284Sjmallett BlockTraits::child_end(current)) <= 2) { 357210284Sjmallett ExitBlocks.push_back(*I); 358210284Sjmallett continue; 359210284Sjmallett } 360210284Sjmallett 361210284Sjmallett // In case of multiple edges from current block to exit block, collect 362210284Sjmallett // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 363210284Sjmallett // duplicate edges. 364210284Sjmallett if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 365210284Sjmallett == switchExitBlocks.end()) { 366210284Sjmallett switchExitBlocks.push_back(*I); 367210284Sjmallett ExitBlocks.push_back(*I); 368210284Sjmallett } 369210284Sjmallett } 370210284Sjmallett } 371210284Sjmallett} 372210284Sjmallett 373210284Sjmallett/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 374210284Sjmallett/// block, return that block. Otherwise return null. 375210284SjmallettBasicBlock *Loop::getUniqueExitBlock() const { 376210284Sjmallett SmallVector<BasicBlock *, 8> UniqueExitBlocks; 377210284Sjmallett getUniqueExitBlocks(UniqueExitBlocks); 378210284Sjmallett if (UniqueExitBlocks.size() == 1) 379210284Sjmallett return UniqueExitBlocks[0]; 380210284Sjmallett return 0; 381210284Sjmallett} 382210284Sjmallett 383210284Sjmallett//===----------------------------------------------------------------------===// 384210284Sjmallett// LoopInfo implementation 385210284Sjmallett// 386210284Sjmallettbool LoopInfo::runOnFunction(Function &) { 387210284Sjmallett releaseMemory(); 388210284Sjmallett LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update 389210284Sjmallett return false; 390210284Sjmallett} 391210284Sjmallett 392210284Sjmallettvoid LoopInfo::verifyAnalysis() const { 393210284Sjmallett // LoopInfo is a FunctionPass, but verifying every loop in the function 394210284Sjmallett // each time verifyAnalysis is called is very expensive. The 395210284Sjmallett // -verify-loop-info option can enable this. In order to perform some 396210284Sjmallett // checking by default, LoopPass has been taught to call verifyLoop 397210284Sjmallett // manually during loop pass sequences. 398210284Sjmallett 399210284Sjmallett if (!VerifyLoopInfo) return; 400210284Sjmallett 401210284Sjmallett for (iterator I = begin(), E = end(); I != E; ++I) { 402210284Sjmallett assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 403210284Sjmallett (*I)->verifyLoopNest(); 404210284Sjmallett } 405210284Sjmallett 406210284Sjmallett // TODO: check BBMap consistency. 407210284Sjmallett} 408210284Sjmallett 409210284Sjmallettvoid LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 410210284Sjmallett AU.setPreservesAll(); 411210284Sjmallett AU.addRequired<DominatorTree>(); 412210284Sjmallett} 413210284Sjmallett 414210284Sjmallettvoid LoopInfo::print(raw_ostream &OS, const Module*) const { 415210284Sjmallett LI.print(OS); 416210284Sjmallett} 417210284Sjmallett 418210284Sjmallett