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