LoopInfo.cpp revision 210299
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 32static bool VerifyLoopInfo = true; 33#else 34static bool 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(DominatorTree &DT) const { 267 // Sort the blocks vector so that we can use binary search to do quick 268 // lookups. 269 SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end()); 270 271 for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 272 BasicBlock *BB = *BI; 273 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 274 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 275 ++UI) { 276 User *U = *UI; 277 BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 278 if (PHINode *P = dyn_cast<PHINode>(U)) 279 UserBB = P->getIncomingBlock(UI); 280 281 // Check the current block, as a fast-path, before checking whether 282 // the use is anywhere in the loop. Most values are used in the same 283 // block they are defined in. Also, blocks not reachable from the 284 // entry are special; uses in them don't need to go through PHIs. 285 if (UserBB != BB && 286 !LoopBBs.count(UserBB) && 287 DT.isReachableFromEntry(UserBB)) 288 return false; 289 } 290 } 291 292 return true; 293} 294 295/// isLoopSimplifyForm - Return true if the Loop is in the form that 296/// the LoopSimplify form transforms loops to, which is sometimes called 297/// normal form. 298bool Loop::isLoopSimplifyForm() const { 299 // Normal-form loops have a preheader, a single backedge, and all of their 300 // exits have all their predecessors inside the loop. 301 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 302} 303 304/// hasDedicatedExits - Return true if no exit block for the loop 305/// has a predecessor that is outside the loop. 306bool Loop::hasDedicatedExits() const { 307 // Sort the blocks vector so that we can use binary search to do quick 308 // lookups. 309 SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 310 // Each predecessor of each exit block of a normal loop is contained 311 // within the loop. 312 SmallVector<BasicBlock *, 4> ExitBlocks; 313 getExitBlocks(ExitBlocks); 314 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 315 for (pred_iterator PI = pred_begin(ExitBlocks[i]), 316 PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 317 if (!LoopBBs.count(*PI)) 318 return false; 319 // All the requirements are met. 320 return true; 321} 322 323/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 324/// These are the blocks _outside of the current loop_ which are branched to. 325/// This assumes that loop exits are in canonical form. 326/// 327void 328Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 329 assert(hasDedicatedExits() && 330 "getUniqueExitBlocks assumes the loop has canonical form exits!"); 331 332 // Sort the blocks vector so that we can use binary search to do quick 333 // lookups. 334 SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end()); 335 std::sort(LoopBBs.begin(), LoopBBs.end()); 336 337 SmallVector<BasicBlock *, 32> switchExitBlocks; 338 339 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 340 341 BasicBlock *current = *BI; 342 switchExitBlocks.clear(); 343 344 typedef GraphTraits<BasicBlock *> BlockTraits; 345 typedef GraphTraits<Inverse<BasicBlock *> > InvBlockTraits; 346 for (BlockTraits::ChildIteratorType I = 347 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 348 I != E; ++I) { 349 // If block is inside the loop then it is not a exit block. 350 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 351 continue; 352 353 InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(*I); 354 BasicBlock *firstPred = *PI; 355 356 // If current basic block is this exit block's first predecessor 357 // then only insert exit block in to the output ExitBlocks vector. 358 // This ensures that same exit block is not inserted twice into 359 // ExitBlocks vector. 360 if (current != firstPred) 361 continue; 362 363 // If a terminator has more then two successors, for example SwitchInst, 364 // then it is possible that there are multiple edges from current block 365 // to one exit block. 366 if (std::distance(BlockTraits::child_begin(current), 367 BlockTraits::child_end(current)) <= 2) { 368 ExitBlocks.push_back(*I); 369 continue; 370 } 371 372 // In case of multiple edges from current block to exit block, collect 373 // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 374 // duplicate edges. 375 if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 376 == switchExitBlocks.end()) { 377 switchExitBlocks.push_back(*I); 378 ExitBlocks.push_back(*I); 379 } 380 } 381 } 382} 383 384/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 385/// block, return that block. Otherwise return null. 386BasicBlock *Loop::getUniqueExitBlock() const { 387 SmallVector<BasicBlock *, 8> UniqueExitBlocks; 388 getUniqueExitBlocks(UniqueExitBlocks); 389 if (UniqueExitBlocks.size() == 1) 390 return UniqueExitBlocks[0]; 391 return 0; 392} 393 394void Loop::dump() const { 395 print(dbgs()); 396} 397 398//===----------------------------------------------------------------------===// 399// LoopInfo implementation 400// 401bool LoopInfo::runOnFunction(Function &) { 402 releaseMemory(); 403 LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update 404 return false; 405} 406 407void LoopInfo::verifyAnalysis() const { 408 // LoopInfo is a FunctionPass, but verifying every loop in the function 409 // each time verifyAnalysis is called is very expensive. The 410 // -verify-loop-info option can enable this. In order to perform some 411 // checking by default, LoopPass has been taught to call verifyLoop 412 // manually during loop pass sequences. 413 414 if (!VerifyLoopInfo) return; 415 416 for (iterator I = begin(), E = end(); I != E; ++I) { 417 assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 418 (*I)->verifyLoopNest(); 419 } 420 421 // TODO: check BBMap consistency. 422} 423 424void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 425 AU.setPreservesAll(); 426 AU.addRequired<DominatorTree>(); 427} 428 429void LoopInfo::print(raw_ostream &OS, const Module*) const { 430 LI.print(OS); 431} 432 433