LoopInfo.cpp revision 204961
1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the LoopInfo class that is used to identify natural loops 11// and determine the loop depth of various nodes of the CFG. Note that the 12// loops identified may actually be several natural loops that share the same 13// header node... not just a single natural loop. 14// 15//===----------------------------------------------------------------------===// 16 17#include "llvm/Analysis/LoopInfo.h" 18#include "llvm/Constants.h" 19#include "llvm/Instructions.h" 20#include "llvm/Analysis/Dominators.h" 21#include "llvm/Assembly/Writer.h" 22#include "llvm/Support/CFG.h" 23#include "llvm/Support/CommandLine.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/ADT/DepthFirstIterator.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include <algorithm> 28using namespace llvm; 29 30// Always verify loopinfo if expensive checking is enabled. 31#ifdef XDEBUG 32bool VerifyLoopInfo = true; 33#else 34bool VerifyLoopInfo = false; 35#endif 36static cl::opt<bool,true> 37VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), 38 cl::desc("Verify loop info (time consuming)")); 39 40char LoopInfo::ID = 0; 41static RegisterPass<LoopInfo> 42X("loops", "Natural Loop Information", true, true); 43 44//===----------------------------------------------------------------------===// 45// Loop implementation 46// 47 48/// isLoopInvariant - Return true if the specified value is loop invariant 49/// 50bool Loop::isLoopInvariant(Value *V) const { 51 if (Instruction *I = dyn_cast<Instruction>(V)) 52 return isLoopInvariant(I); 53 return true; // All non-instructions are loop invariant 54} 55 56/// isLoopInvariant - Return true if the specified instruction is 57/// loop-invariant. 58/// 59bool Loop::isLoopInvariant(Instruction *I) const { 60 return !contains(I); 61} 62 63/// makeLoopInvariant - If the given value is an instruciton inside of the 64/// loop and it can be hoisted, do so to make it trivially loop-invariant. 65/// Return true if the value after any hoisting is loop invariant. This 66/// function can be used as a slightly more aggressive replacement for 67/// isLoopInvariant. 68/// 69/// If InsertPt is specified, it is the point to hoist instructions to. 70/// If null, the terminator of the loop preheader is used. 71/// 72bool Loop::makeLoopInvariant(Value *V, bool &Changed, 73 Instruction *InsertPt) const { 74 if (Instruction *I = dyn_cast<Instruction>(V)) 75 return makeLoopInvariant(I, Changed, InsertPt); 76 return true; // All non-instructions are loop-invariant. 77} 78 79/// makeLoopInvariant - If the given instruction is inside of the 80/// loop and it can be hoisted, do so to make it trivially loop-invariant. 81/// Return true if the instruction after any hoisting is loop invariant. This 82/// function can be used as a slightly more aggressive replacement for 83/// isLoopInvariant. 84/// 85/// If InsertPt is specified, it is the point to hoist instructions to. 86/// If null, the terminator of the loop preheader is used. 87/// 88bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 89 Instruction *InsertPt) const { 90 // Test if the value is already loop-invariant. 91 if (isLoopInvariant(I)) 92 return true; 93 if (!I->isSafeToSpeculativelyExecute()) 94 return false; 95 if (I->mayReadFromMemory()) 96 return false; 97 // Determine the insertion point, unless one was given. 98 if (!InsertPt) { 99 BasicBlock *Preheader = getLoopPreheader(); 100 // Without a preheader, hoisting is not feasible. 101 if (!Preheader) 102 return false; 103 InsertPt = Preheader->getTerminator(); 104 } 105 // Don't hoist instructions with loop-variant operands. 106 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 107 if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 108 return false; 109 // Hoist. 110 I->moveBefore(InsertPt); 111 Changed = true; 112 return true; 113} 114 115/// getCanonicalInductionVariable - Check to see if the loop has a canonical 116/// induction variable: an integer recurrence that starts at 0 and increments 117/// by one each time through the loop. If so, return the phi node that 118/// corresponds to it. 119/// 120/// The IndVarSimplify pass transforms loops to have a canonical induction 121/// variable. 122/// 123PHINode *Loop::getCanonicalInductionVariable() const { 124 BasicBlock *H = getHeader(); 125 126 BasicBlock *Incoming = 0, *Backedge = 0; 127 typedef GraphTraits<Inverse<BasicBlock*> > InvBlockTraits; 128 InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(H); 129 assert(PI != InvBlockTraits::child_end(H) && 130 "Loop must have at least one backedge!"); 131 Backedge = *PI++; 132 if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop 133 Incoming = *PI++; 134 if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? 135 136 if (contains(Incoming)) { 137 if (contains(Backedge)) 138 return 0; 139 std::swap(Incoming, Backedge); 140 } else if (!contains(Backedge)) 141 return 0; 142 143 // Loop over all of the PHI nodes, looking for a canonical indvar. 144 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 145 PHINode *PN = cast<PHINode>(I); 146 if (ConstantInt *CI = 147 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 148 if (CI->isNullValue()) 149 if (Instruction *Inc = 150 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 151 if (Inc->getOpcode() == Instruction::Add && 152 Inc->getOperand(0) == PN) 153 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 154 if (CI->equalsInt(1)) 155 return PN; 156 } 157 return 0; 158} 159 160/// getCanonicalInductionVariableIncrement - Return the LLVM value that holds 161/// the canonical induction variable value for the "next" iteration of the 162/// loop. This always succeeds if getCanonicalInductionVariable succeeds. 163/// 164Instruction *Loop::getCanonicalInductionVariableIncrement() const { 165 if (PHINode *PN = getCanonicalInductionVariable()) { 166 bool P1InLoop = contains(PN->getIncomingBlock(1)); 167 return cast<Instruction>(PN->getIncomingValue(P1InLoop)); 168 } 169 return 0; 170} 171 172/// getTripCount - Return a loop-invariant LLVM value indicating the number of 173/// times the loop will be executed. Note that this means that the backedge 174/// of the loop executes N-1 times. If the trip-count cannot be determined, 175/// this returns null. 176/// 177/// The IndVarSimplify pass transforms loops to have a form that this 178/// function easily understands. 179/// 180Value *Loop::getTripCount() const { 181 // Canonical loops will end with a 'cmp ne I, V', where I is the incremented 182 // canonical induction variable and V is the trip count of the loop. 183 Instruction *Inc = getCanonicalInductionVariableIncrement(); 184 if (Inc == 0) return 0; 185 PHINode *IV = cast<PHINode>(Inc->getOperand(0)); 186 187 BasicBlock *BackedgeBlock = 188 IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); 189 190 if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator())) 191 if (BI->isConditional()) { 192 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 193 if (ICI->getOperand(0) == Inc) { 194 if (BI->getSuccessor(0) == getHeader()) { 195 if (ICI->getPredicate() == ICmpInst::ICMP_NE) 196 return ICI->getOperand(1); 197 } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { 198 return ICI->getOperand(1); 199 } 200 } 201 } 202 } 203 204 return 0; 205} 206 207/// getSmallConstantTripCount - Returns the trip count of this loop as a 208/// normal unsigned value, if possible. Returns 0 if the trip count is unknown 209/// of not constant. Will also return 0 if the trip count is very large 210/// (>= 2^32) 211unsigned Loop::getSmallConstantTripCount() const { 212 Value* TripCount = this->getTripCount(); 213 if (TripCount) { 214 if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) { 215 // Guard against huge trip counts. 216 if (TripCountC->getValue().getActiveBits() <= 32) { 217 return (unsigned)TripCountC->getZExtValue(); 218 } 219 } 220 } 221 return 0; 222} 223 224/// getSmallConstantTripMultiple - Returns the largest constant divisor of the 225/// trip count of this loop as a normal unsigned value, if possible. This 226/// means that the actual trip count is always a multiple of the returned 227/// value (don't forget the trip count could very well be zero as well!). 228/// 229/// Returns 1 if the trip count is unknown or not guaranteed to be the 230/// multiple of a constant (which is also the case if the trip count is simply 231/// constant, use getSmallConstantTripCount for that case), Will also return 1 232/// if the trip count is very large (>= 2^32). 233unsigned Loop::getSmallConstantTripMultiple() const { 234 Value* TripCount = this->getTripCount(); 235 // This will hold the ConstantInt result, if any 236 ConstantInt *Result = NULL; 237 if (TripCount) { 238 // See if the trip count is constant itself 239 Result = dyn_cast<ConstantInt>(TripCount); 240 // if not, see if it is a multiplication 241 if (!Result) 242 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) { 243 switch (BO->getOpcode()) { 244 case BinaryOperator::Mul: 245 Result = dyn_cast<ConstantInt>(BO->getOperand(1)); 246 break; 247 case BinaryOperator::Shl: 248 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) 249 if (CI->getValue().getActiveBits() <= 5) 250 return 1u << CI->getZExtValue(); 251 break; 252 default: 253 break; 254 } 255 } 256 } 257 // Guard against huge trip counts. 258 if (Result && Result->getValue().getActiveBits() <= 32) { 259 return (unsigned)Result->getZExtValue(); 260 } else { 261 return 1; 262 } 263} 264 265/// isLCSSAForm - Return true if the Loop is in LCSSA form 266bool Loop::isLCSSAForm() const { 267 // Collect all the reachable blocks in the function, for fast lookups. 268 SmallPtrSet<BasicBlock *, 32> ReachableBBs; 269 BasicBlock *EntryBB = getHeader()->getParent()->begin(); 270 for (df_iterator<BasicBlock *> NI = df_begin(EntryBB), 271 NE = df_end(EntryBB); NI != NE; ++NI) 272 ReachableBBs.insert(*NI); 273 274 // Sort the blocks vector so that we can use binary search to do quick 275 // lookups. 276 SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 277 278 for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 279 BasicBlock *BB = *BI; 280 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 281 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 282 ++UI) { 283 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 284 if (PHINode *P = dyn_cast<PHINode>(*UI)) 285 UserBB = P->getIncomingBlock(UI); 286 287 // Check the current block, as a fast-path, before checking whether 288 // the use is anywhere in the loop. Most values are used in the same 289 // block they are defined in. Also, blocks not reachable from the 290 // entry are special; uses in them don't need to go through PHIs. 291 if (UserBB != BB && 292 !LoopBBs.count(UserBB) && 293 ReachableBBs.count(UserBB)) 294 return false; 295 } 296 } 297 298 return true; 299} 300 301/// isLoopSimplifyForm - Return true if the Loop is in the form that 302/// the LoopSimplify form transforms loops to, which is sometimes called 303/// normal form. 304bool Loop::isLoopSimplifyForm() const { 305 // Normal-form loops have a preheader, a single backedge, and all of their 306 // exits have all their predecessors inside the loop. 307 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 308} 309 310/// hasDedicatedExits - Return true if no exit block for the loop 311/// has a predecessor that is outside the loop. 312bool Loop::hasDedicatedExits() const { 313 // Sort the blocks vector so that we can use binary search to do quick 314 // lookups. 315 SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 316 // Each predecessor of each exit block of a normal loop is contained 317 // within the loop. 318 SmallVector<BasicBlock *, 4> ExitBlocks; 319 getExitBlocks(ExitBlocks); 320 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 321 for (pred_iterator PI = pred_begin(ExitBlocks[i]), 322 PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 323 if (!LoopBBs.count(*PI)) 324 return false; 325 // All the requirements are met. 326 return true; 327} 328 329/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 330/// These are the blocks _outside of the current loop_ which are branched to. 331/// This assumes that loop exits are in canonical form. 332/// 333void 334Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 335 assert(hasDedicatedExits() && 336 "getUniqueExitBlocks assumes the loop has canonical form exits!"); 337 338 // Sort the blocks vector so that we can use binary search to do quick 339 // lookups. 340 SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end()); 341 std::sort(LoopBBs.begin(), LoopBBs.end()); 342 343 SmallVector<BasicBlock *, 32> switchExitBlocks; 344 345 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 346 347 BasicBlock *current = *BI; 348 switchExitBlocks.clear(); 349 350 typedef GraphTraits<BasicBlock *> BlockTraits; 351 typedef GraphTraits<Inverse<BasicBlock *> > InvBlockTraits; 352 for (BlockTraits::ChildIteratorType I = 353 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 354 I != E; ++I) { 355 // If block is inside the loop then it is not a exit block. 356 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 357 continue; 358 359 InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(*I); 360 BasicBlock *firstPred = *PI; 361 362 // If current basic block is this exit block's first predecessor 363 // then only insert exit block in to the output ExitBlocks vector. 364 // This ensures that same exit block is not inserted twice into 365 // ExitBlocks vector. 366 if (current != firstPred) 367 continue; 368 369 // If a terminator has more then two successors, for example SwitchInst, 370 // then it is possible that there are multiple edges from current block 371 // to one exit block. 372 if (std::distance(BlockTraits::child_begin(current), 373 BlockTraits::child_end(current)) <= 2) { 374 ExitBlocks.push_back(*I); 375 continue; 376 } 377 378 // In case of multiple edges from current block to exit block, collect 379 // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 380 // duplicate edges. 381 if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 382 == switchExitBlocks.end()) { 383 switchExitBlocks.push_back(*I); 384 ExitBlocks.push_back(*I); 385 } 386 } 387 } 388} 389 390/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 391/// block, return that block. Otherwise return null. 392BasicBlock *Loop::getUniqueExitBlock() const { 393 SmallVector<BasicBlock *, 8> UniqueExitBlocks; 394 getUniqueExitBlocks(UniqueExitBlocks); 395 if (UniqueExitBlocks.size() == 1) 396 return UniqueExitBlocks[0]; 397 return 0; 398} 399 400void Loop::dump() const { 401 print(dbgs()); 402} 403 404//===----------------------------------------------------------------------===// 405// LoopInfo implementation 406// 407bool LoopInfo::runOnFunction(Function &) { 408 releaseMemory(); 409 LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update 410 return false; 411} 412 413void LoopInfo::verifyAnalysis() const { 414 // LoopInfo is a FunctionPass, but verifying every loop in the function 415 // each time verifyAnalysis is called is very expensive. The 416 // -verify-loop-info option can enable this. In order to perform some 417 // checking by default, LoopPass has been taught to call verifyLoop 418 // manually during loop pass sequences. 419 420 if (!VerifyLoopInfo) return; 421 422 for (iterator I = begin(), E = end(); I != E; ++I) { 423 assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 424 (*I)->verifyLoopNest(); 425 } 426 427 // TODO: check BBMap consistency. 428} 429 430void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 431 AU.setPreservesAll(); 432 AU.addRequired<DominatorTree>(); 433} 434 435void LoopInfo::print(raw_ostream &OS, const Module*) const { 436 LI.print(OS); 437} 438 439