LLVM API Documentation

LoopInfo.cpp

Go to the documentation of this file.
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 }