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