LoopInfo.cpp revision 212904
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; 41INITIALIZE_PASS(LoopInfo, "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); 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 pred_iterator PI = pred_begin(H); 127 assert(PI != pred_end(H) && 128 "Loop must have at least one backedge!"); 129 Backedge = *PI++; 130 if (PI == pred_end(H)) return 0; // dead loop 131 Incoming = *PI++; 132 if (PI != pred_end(H)) return 0; // multiple backedges? 133 134 if (contains(Incoming)) { 135 if (contains(Backedge)) 136 return 0; 137 std::swap(Incoming, Backedge); 138 } else if (!contains(Backedge)) 139 return 0; 140 141 // Loop over all of the PHI nodes, looking for a canonical indvar. 142 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 143 PHINode *PN = cast<PHINode>(I); 144 if (ConstantInt *CI = 145 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 146 if (CI->isNullValue()) 147 if (Instruction *Inc = 148 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 149 if (Inc->getOpcode() == Instruction::Add && 150 Inc->getOperand(0) == PN) 151 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 152 if (CI->equalsInt(1)) 153 return PN; 154 } 155 return 0; 156} 157 158/// getTripCount - Return a loop-invariant LLVM value indicating the number of 159/// times the loop will be executed. Note that this means that the backedge 160/// of the loop executes N-1 times. If the trip-count cannot be determined, 161/// this returns null. 162/// 163/// The IndVarSimplify pass transforms loops to have a form that this 164/// function easily understands. 165/// 166Value *Loop::getTripCount() const { 167 // Canonical loops will end with a 'cmp ne I, V', where I is the incremented 168 // canonical induction variable and V is the trip count of the loop. 169 PHINode *IV = getCanonicalInductionVariable(); 170 if (IV == 0 || IV->getNumIncomingValues() != 2) return 0; 171 172 bool P0InLoop = contains(IV->getIncomingBlock(0)); 173 Value *Inc = IV->getIncomingValue(!P0InLoop); 174 BasicBlock *BackedgeBlock = IV->getIncomingBlock(!P0InLoop); 175 176 if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator())) 177 if (BI->isConditional()) { 178 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 179 if (ICI->getOperand(0) == Inc) { 180 if (BI->getSuccessor(0) == getHeader()) { 181 if (ICI->getPredicate() == ICmpInst::ICMP_NE) 182 return ICI->getOperand(1); 183 } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { 184 return ICI->getOperand(1); 185 } 186 } 187 } 188 } 189 190 return 0; 191} 192 193/// getSmallConstantTripCount - Returns the trip count of this loop as a 194/// normal unsigned value, if possible. Returns 0 if the trip count is unknown 195/// of not constant. Will also return 0 if the trip count is very large 196/// (>= 2^32) 197unsigned Loop::getSmallConstantTripCount() const { 198 Value* TripCount = this->getTripCount(); 199 if (TripCount) { 200 if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) { 201 // Guard against huge trip counts. 202 if (TripCountC->getValue().getActiveBits() <= 32) { 203 return (unsigned)TripCountC->getZExtValue(); 204 } 205 } 206 } 207 return 0; 208} 209 210/// getSmallConstantTripMultiple - Returns the largest constant divisor of the 211/// trip count of this loop as a normal unsigned value, if possible. This 212/// means that the actual trip count is always a multiple of the returned 213/// value (don't forget the trip count could very well be zero as well!). 214/// 215/// Returns 1 if the trip count is unknown or not guaranteed to be the 216/// multiple of a constant (which is also the case if the trip count is simply 217/// constant, use getSmallConstantTripCount for that case), Will also return 1 218/// if the trip count is very large (>= 2^32). 219unsigned Loop::getSmallConstantTripMultiple() const { 220 Value* TripCount = this->getTripCount(); 221 // This will hold the ConstantInt result, if any 222 ConstantInt *Result = NULL; 223 if (TripCount) { 224 // See if the trip count is constant itself 225 Result = dyn_cast<ConstantInt>(TripCount); 226 // if not, see if it is a multiplication 227 if (!Result) 228 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) { 229 switch (BO->getOpcode()) { 230 case BinaryOperator::Mul: 231 Result = dyn_cast<ConstantInt>(BO->getOperand(1)); 232 break; 233 case BinaryOperator::Shl: 234 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) 235 if (CI->getValue().getActiveBits() <= 5) 236 return 1u << CI->getZExtValue(); 237 break; 238 default: 239 break; 240 } 241 } 242 } 243 // Guard against huge trip counts. 244 if (Result && Result->getValue().getActiveBits() <= 32) { 245 return (unsigned)Result->getZExtValue(); 246 } else { 247 return 1; 248 } 249} 250 251/// isLCSSAForm - Return true if the Loop is in LCSSA form 252bool Loop::isLCSSAForm(DominatorTree &DT) const { 253 // Sort the blocks vector so that we can use binary search to do quick 254 // lookups. 255 SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end()); 256 257 for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 258 BasicBlock *BB = *BI; 259 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 260 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 261 ++UI) { 262 User *U = *UI; 263 BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 264 if (PHINode *P = dyn_cast<PHINode>(U)) 265 UserBB = P->getIncomingBlock(UI); 266 267 // Check the current block, as a fast-path, before checking whether 268 // the use is anywhere in the loop. Most values are used in the same 269 // block they are defined in. Also, blocks not reachable from the 270 // entry are special; uses in them don't need to go through PHIs. 271 if (UserBB != BB && 272 !LoopBBs.count(UserBB) && 273 DT.isReachableFromEntry(UserBB)) 274 return false; 275 } 276 } 277 278 return true; 279} 280 281/// isLoopSimplifyForm - Return true if the Loop is in the form that 282/// the LoopSimplify form transforms loops to, which is sometimes called 283/// normal form. 284bool Loop::isLoopSimplifyForm() const { 285 // Normal-form loops have a preheader, a single backedge, and all of their 286 // exits have all their predecessors inside the loop. 287 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 288} 289 290/// hasDedicatedExits - Return true if no exit block for the loop 291/// has a predecessor that is outside the loop. 292bool Loop::hasDedicatedExits() const { 293 // Sort the blocks vector so that we can use binary search to do quick 294 // lookups. 295 SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 296 // Each predecessor of each exit block of a normal loop is contained 297 // within the loop. 298 SmallVector<BasicBlock *, 4> ExitBlocks; 299 getExitBlocks(ExitBlocks); 300 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 301 for (pred_iterator PI = pred_begin(ExitBlocks[i]), 302 PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 303 if (!LoopBBs.count(*PI)) 304 return false; 305 // All the requirements are met. 306 return true; 307} 308 309/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 310/// These are the blocks _outside of the current loop_ which are branched to. 311/// This assumes that loop exits are in canonical form. 312/// 313void 314Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 315 assert(hasDedicatedExits() && 316 "getUniqueExitBlocks assumes the loop has canonical form exits!"); 317 318 // Sort the blocks vector so that we can use binary search to do quick 319 // lookups. 320 SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end()); 321 std::sort(LoopBBs.begin(), LoopBBs.end()); 322 323 SmallVector<BasicBlock *, 32> switchExitBlocks; 324 325 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 326 327 BasicBlock *current = *BI; 328 switchExitBlocks.clear(); 329 330 for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { 331 // If block is inside the loop then it is not a exit block. 332 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 333 continue; 334 335 pred_iterator PI = pred_begin(*I); 336 BasicBlock *firstPred = *PI; 337 338 // If current basic block is this exit block's first predecessor 339 // then only insert exit block in to the output ExitBlocks vector. 340 // This ensures that same exit block is not inserted twice into 341 // ExitBlocks vector. 342 if (current != firstPred) 343 continue; 344 345 // If a terminator has more then two successors, for example SwitchInst, 346 // then it is possible that there are multiple edges from current block 347 // to one exit block. 348 if (std::distance(succ_begin(current), succ_end(current)) <= 2) { 349 ExitBlocks.push_back(*I); 350 continue; 351 } 352 353 // In case of multiple edges from current block to exit block, collect 354 // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 355 // duplicate edges. 356 if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 357 == switchExitBlocks.end()) { 358 switchExitBlocks.push_back(*I); 359 ExitBlocks.push_back(*I); 360 } 361 } 362 } 363} 364 365/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 366/// block, return that block. Otherwise return null. 367BasicBlock *Loop::getUniqueExitBlock() const { 368 SmallVector<BasicBlock *, 8> UniqueExitBlocks; 369 getUniqueExitBlocks(UniqueExitBlocks); 370 if (UniqueExitBlocks.size() == 1) 371 return UniqueExitBlocks[0]; 372 return 0; 373} 374 375void Loop::dump() const { 376 print(dbgs()); 377} 378 379//===----------------------------------------------------------------------===// 380// LoopInfo implementation 381// 382bool LoopInfo::runOnFunction(Function &) { 383 releaseMemory(); 384 LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update 385 return false; 386} 387 388void LoopInfo::verifyAnalysis() const { 389 // LoopInfo is a FunctionPass, but verifying every loop in the function 390 // each time verifyAnalysis is called is very expensive. The 391 // -verify-loop-info option can enable this. In order to perform some 392 // checking by default, LoopPass has been taught to call verifyLoop 393 // manually during loop pass sequences. 394 395 if (!VerifyLoopInfo) return; 396 397 for (iterator I = begin(), E = end(); I != E; ++I) { 398 assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 399 (*I)->verifyLoopNest(); 400 } 401 402 // TODO: check BBMap consistency. 403} 404 405void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 406 AU.setPreservesAll(); 407 AU.addRequired<DominatorTree>(); 408} 409 410void LoopInfo::print(raw_ostream &OS, const Module*) const { 411 LI.print(OS); 412} 413 414