lib/Analysis/LoopInfo.cpp

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