LLVM API Documentation
00001 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the LoopInfo class that is used to identify natural loops 00011 // and determine the loop depth of various nodes of the CFG. Note that the 00012 // loops identified may actually be several natural loops that share the same 00013 // header node... not just a single natural loop. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/LoopInfo.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/Instructions.h" 00020 #include "llvm/Analysis/Dominators.h" 00021 #include "llvm/Assembly/Writer.h" 00022 #include "llvm/Support/CFG.h" 00023 #include "llvm/Support/Streams.h" 00024 #include "llvm/ADT/DepthFirstIterator.h" 00025 #include "llvm/ADT/SmallPtrSet.h" 00026 #include <algorithm> 00027 using namespace llvm; 00028 00029 char LoopInfo::ID = 0; 00030 static RegisterPass<LoopInfo> 00031 X("loops", "Natural Loop Information", true, true); 00032 00033 //===----------------------------------------------------------------------===// 00034 // Loop implementation 00035 // 00036 00037 /// isLoopInvariant - Return true if the specified value is loop invariant 00038 /// 00039 bool Loop::isLoopInvariant(Value *V) const { 00040 if (Instruction *I = dyn_cast<Instruction>(V)) 00041 return isLoopInvariant(I); 00042 return true; // All non-instructions are loop invariant 00043 } 00044 00045 /// isLoopInvariant - Return true if the specified instruction is 00046 /// loop-invariant. 00047 /// 00048 bool Loop::isLoopInvariant(Instruction *I) const { 00049 return !contains(I->getParent()); 00050 } 00051 00052 /// makeLoopInvariant - If the given value is an instruciton inside of the 00053 /// loop and it can be hoisted, do so to make it trivially loop-invariant. 00054 /// Return true if the value after any hoisting is loop invariant. This 00055 /// function can be used as a slightly more aggressive replacement for 00056 /// isLoopInvariant. 00057 /// 00058 /// If InsertPt is specified, it is the point to hoist instructions to. 00059 /// If null, the terminator of the loop preheader is used. 00060 /// 00061 bool Loop::makeLoopInvariant(Value *V, bool &Changed, 00062 Instruction *InsertPt) const { 00063 if (Instruction *I = dyn_cast<Instruction>(V)) 00064 return makeLoopInvariant(I, Changed, InsertPt); 00065 return true; // All non-instructions are loop-invariant. 00066 } 00067 00068 /// makeLoopInvariant - If the given instruction is inside of the 00069 /// loop and it can be hoisted, do so to make it trivially loop-invariant. 00070 /// Return true if the instruction after any hoisting is loop invariant. This 00071 /// function can be used as a slightly more aggressive replacement for 00072 /// isLoopInvariant. 00073 /// 00074 /// If InsertPt is specified, it is the point to hoist instructions to. 00075 /// If null, the terminator of the loop preheader is used. 00076 /// 00077 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 00078 Instruction *InsertPt) const { 00079 // Test if the value is already loop-invariant. 00080 if (isLoopInvariant(I)) 00081 return true; 00082 if (!I->isSafeToSpeculativelyExecute()) 00083 return false; 00084 if (I->mayReadFromMemory()) 00085 return false; 00086 // Determine the insertion point, unless one was given. 00087 if (!InsertPt) { 00088 BasicBlock *Preheader = getLoopPreheader(); 00089 // Without a preheader, hoisting is not feasible. 00090 if (!Preheader) 00091 return false; 00092 InsertPt = Preheader->getTerminator(); 00093 } 00094 // Don't hoist instructions with loop-variant operands. 00095 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00096 if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 00097 return false; 00098 // Hoist. 00099 I->moveBefore(InsertPt); 00100 Changed = true; 00101 return true; 00102 } 00103 00104 /// getCanonicalInductionVariable - Check to see if the loop has a canonical 00105 /// induction variable: an integer recurrence that starts at 0 and increments 00106 /// by one each time through the loop. If so, return the phi node that 00107 /// corresponds to it. 00108 /// 00109 /// The IndVarSimplify pass transforms loops to have a canonical induction 00110 /// variable. 00111 /// 00112 PHINode *Loop::getCanonicalInductionVariable() const { 00113 BasicBlock *H = getHeader(); 00114 00115 BasicBlock *Incoming = 0, *Backedge = 0; 00116 typedef GraphTraits<Inverse<BasicBlock*> > InvBlockTraits; 00117 InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(H); 00118 assert(PI != InvBlockTraits::child_end(H) && 00119 "Loop must have at least one backedge!"); 00120 Backedge = *PI++; 00121 if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop 00122 Incoming = *PI++; 00123 if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? 00124 00125 if (contains(Incoming)) { 00126 if (contains(Backedge)) 00127 return 0; 00128 std::swap(Incoming, Backedge); 00129 } else if (!contains(Backedge)) 00130 return 0; 00131 00132 // Loop over all of the PHI nodes, looking for a canonical indvar. 00133 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 00134 PHINode *PN = cast<PHINode>(I); 00135 if (ConstantInt *CI = 00136 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 00137 if (CI->isNullValue()) 00138 if (Instruction *Inc = 00139 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 00140 if (Inc->getOpcode() == Instruction::Add && 00141 Inc->getOperand(0) == PN) 00142 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 00143 if (CI->equalsInt(1)) 00144 return PN; 00145 } 00146 return 0; 00147 } 00148 00149 /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds 00150 /// the canonical induction variable value for the "next" iteration of the 00151 /// loop. This always succeeds if getCanonicalInductionVariable succeeds. 00152 /// 00153 Instruction *Loop::getCanonicalInductionVariableIncrement() const { 00154 if (PHINode *PN = getCanonicalInductionVariable()) { 00155 bool P1InLoop = contains(PN->getIncomingBlock(1)); 00156 return cast<Instruction>(PN->getIncomingValue(P1InLoop)); 00157 } 00158 return 0; 00159 } 00160 00161 /// getTripCount - Return a loop-invariant LLVM value indicating the number of 00162 /// times the loop will be executed. Note that this means that the backedge 00163 /// of the loop executes N-1 times. If the trip-count cannot be determined, 00164 /// this returns null. 00165 /// 00166 /// The IndVarSimplify pass transforms loops to have a form that this 00167 /// function easily understands. 00168 /// 00169 Value *Loop::getTripCount() const { 00170 // Canonical loops will end with a 'cmp ne I, V', where I is the incremented 00171 // canonical induction variable and V is the trip count of the loop. 00172 Instruction *Inc = getCanonicalInductionVariableIncrement(); 00173 if (Inc == 0) return 0; 00174 PHINode *IV = cast<PHINode>(Inc->getOperand(0)); 00175 00176 BasicBlock *BackedgeBlock = 00177 IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); 00178 00179 if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator())) 00180 if (BI->isConditional()) { 00181 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 00182 if (ICI->getOperand(0) == Inc) { 00183 if (BI->getSuccessor(0) == getHeader()) { 00184 if (ICI->getPredicate() == ICmpInst::ICMP_NE) 00185 return ICI->getOperand(1); 00186 } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { 00187 return ICI->getOperand(1); 00188 } 00189 } 00190 } 00191 } 00192 00193 return 0; 00194 } 00195 00196 /// getSmallConstantTripCount - Returns the trip count of this loop as a 00197 /// normal unsigned value, if possible. Returns 0 if the trip count is unknown 00198 /// of not constant. Will also return 0 if the trip count is very large 00199 /// (>= 2^32) 00200 unsigned Loop::getSmallConstantTripCount() const { 00201 Value* TripCount = this->getTripCount(); 00202 if (TripCount) { 00203 if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) { 00204 // Guard against huge trip counts. 00205 if (TripCountC->getValue().getActiveBits() <= 32) { 00206 return (unsigned)TripCountC->getZExtValue(); 00207 } 00208 } 00209 } 00210 return 0; 00211 } 00212 00213 /// getSmallConstantTripMultiple - Returns the largest constant divisor of the 00214 /// trip count of this loop as a normal unsigned value, if possible. This 00215 /// means that the actual trip count is always a multiple of the returned 00216 /// value (don't forget the trip count could very well be zero as well!). 00217 /// 00218 /// Returns 1 if the trip count is unknown or not guaranteed to be the 00219 /// multiple of a constant (which is also the case if the trip count is simply 00220 /// constant, use getSmallConstantTripCount for that case), Will also return 1 00221 /// if the trip count is very large (>= 2^32). 00222 unsigned Loop::getSmallConstantTripMultiple() const { 00223 Value* TripCount = this->getTripCount(); 00224 // This will hold the ConstantInt result, if any 00225 ConstantInt *Result = NULL; 00226 if (TripCount) { 00227 // See if the trip count is constant itself 00228 Result = dyn_cast<ConstantInt>(TripCount); 00229 // if not, see if it is a multiplication 00230 if (!Result) 00231 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) { 00232 switch (BO->getOpcode()) { 00233 case BinaryOperator::Mul: 00234 Result = dyn_cast<ConstantInt>(BO->getOperand(1)); 00235 break; 00236 default: 00237 break; 00238 } 00239 } 00240 } 00241 // Guard against huge trip counts. 00242 if (Result && Result->getValue().getActiveBits() <= 32) { 00243 return (unsigned)Result->getZExtValue(); 00244 } else { 00245 return 1; 00246 } 00247 } 00248 00249 /// isLCSSAForm - Return true if the Loop is in LCSSA form 00250 bool Loop::isLCSSAForm() const { 00251 // Sort the blocks vector so that we can use binary search to do quick 00252 // lookups. 00253 SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 00254 00255 for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 00256 BasicBlock *BB = *BI; 00257 for (BasicBlock ::iterator I = BB->begin(), E = BB->end(); I != E;++I) 00258 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 00259 ++UI) { 00260 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 00261 if (PHINode *P = dyn_cast<PHINode>(*UI)) { 00262 UserBB = P->getIncomingBlock(UI); 00263 } 00264 00265 // Check the current block, as a fast-path. Most values are used in 00266 // the same block they are defined in. 00267 if (UserBB != BB && !LoopBBs.count(UserBB)) 00268 return false; 00269 } 00270 } 00271 00272 return true; 00273 } 00274 00275 /// isLoopSimplifyForm - Return true if the Loop is in the form that 00276 /// the LoopSimplify form transforms loops to, which is sometimes called 00277 /// normal form. 00278 bool Loop::isLoopSimplifyForm() const { 00279 // Normal-form loops have a preheader. 00280 if (!getLoopPreheader()) 00281 return false; 00282 // Normal-form loops have a single backedge. 00283 if (!getLoopLatch()) 00284 return false; 00285 // Each predecessor of each exit block of a normal loop is contained 00286 // within the loop. 00287 SmallVector<BasicBlock *, 4> ExitBlocks; 00288 getExitBlocks(ExitBlocks); 00289 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 00290 for (pred_iterator PI = pred_begin(ExitBlocks[i]), 00291 PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 00292 if (!contains(*PI)) 00293 return false; 00294 // All the requirements are met. 00295 return true; 00296 } 00297 00298 //===----------------------------------------------------------------------===// 00299 // LoopInfo implementation 00300 // 00301 bool LoopInfo::runOnFunction(Function &) { 00302 releaseMemory(); 00303 LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update 00304 return false; 00305 } 00306 00307 void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 00308 AU.setPreservesAll(); 00309 AU.addRequired<DominatorTree>(); 00310 }