lib/Transforms/Scalar/LoopUnroll.cpp

   1 //===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
   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 pass implements a simple loop unroller.  It works best when loops have
  11 // been canonicalized by the -indvars pass, allowing it to determine the trip
  12 // counts of loops easily.
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "loop-unroll"
  16 #include "llvm/IntrinsicInst.h"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Analysis/LoopPass.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Transforms/Utils/UnrollLoop.h"
  24 #include <climits>
  25
  26 using namespace llvm;
  27
  28 static cl::opt<unsigned>
  29 UnrollThreshold("unroll-threshold", cl::init(100), cl::Hidden,
  30   cl::desc("The cut-off point for automatic loop unrolling"));
  31
  32 static cl::opt<unsigned>
  33 UnrollCount("unroll-count", cl::init(0), cl::Hidden,
  34   cl::desc("Use this unroll count for all loops, for testing purposes"));
  35
  36 namespace {
  37   class VISIBILITY_HIDDEN LoopUnroll : public LoopPass {
  38   public:
  39     static char ID; // Pass ID, replacement for typeid
  40     LoopUnroll() : LoopPass((intptr_t)&ID) {}
  41
  42     /// A magic value for use with the Threshold parameter to indicate
  43     /// that the loop unroll should be performed regardless of how much
  44     /// code expansion would result.
  45     static const unsigned NoThreshold = UINT_MAX;
  46
  47     bool runOnLoop(Loop *L, LPPassManager &LPM);
  48
  49     /// This transformation requires natural loop information & requires that
  50     /// loop preheaders be inserted into the CFG...
  51     ///
  52     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  53       AU.addRequiredID(LoopSimplifyID);
  54       AU.addRequiredID(LCSSAID);
  55       AU.addRequired<LoopInfo>();
  56       AU.addPreservedID(LCSSAID);
  57       AU.addPreserved<LoopInfo>();
  58     }
  59   };
  60 }
  61
  62 char LoopUnroll::ID = 0;
  63 static RegisterPass<LoopUnroll> X("loop-unroll", "Unroll loops");
  64
  65 LoopPass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
  66
  67 /// ApproximateLoopSize - Approximate the size of the loop.
  68 static unsigned ApproximateLoopSize(const Loop *L) {
  69   unsigned Size = 0;
  70   for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) {
  71     BasicBlock *BB = L->getBlocks()[i];
  72     Instruction *Term = BB->getTerminator();
  73     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
  74       if (isa<PHINode>(I) && BB == L->getHeader()) {
  75         // Ignore PHI nodes in the header.
  76       } else if (I->hasOneUse() && I->use_back() == Term) {
  77         // Ignore instructions only used by the loop terminator.
  78       } else if (isa<DbgInfoIntrinsic>(I)) {
  79         // Ignore debug instructions
  80       } else if (isa<CallInst>(I)) {
  81         // Estimate size overhead introduced by call instructions which
  82         // is higher than other instructions. Here 3 and 10 are magic
  83         // numbers that help one isolated test case from PR2067 without
  84         // negatively impacting measured benchmarks.
  85         if (isa<IntrinsicInst>(I))
  86           Size = Size + 3;
  87         else
  88           Size = Size + 10;
  89       } else {
  90         ++Size;
  91       }
  92
  93       // TODO: Ignore expressions derived from PHI and constants if inval of phi
  94       // is a constant, or if operation is associative.  This will get induction
  95       // variables.
  96     }
  97   }
  98
  99   return Size;
 100 }
 101
 102 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
 103   assert(L->isLCSSAForm());
 104   LoopInfo *LI = &getAnalysis<LoopInfo>();
 105
 106   BasicBlock *Header = L->getHeader();
 107   DOUT << "Loop Unroll: F[" << Header->getParent()->getName()
 108        << "] Loop %" << Header->getName() << "\n";
 109
 110   // Find trip count
 111   unsigned TripCount = L->getSmallConstantTripCount();
 112   unsigned Count = UnrollCount;
 113
 114   // Automatically select an unroll count.
 115   if (Count == 0) {
 116     // Conservative heuristic: if we know the trip count, see if we can
 117     // completely unroll (subject to the threshold, checked below); otherwise
 118     // don't unroll.
 119     if (TripCount != 0) {
 120       Count = TripCount;
 121     } else {
 122       return false;
 123     }
 124   }
 125
 126   // Enforce the threshold.
 127   if (UnrollThreshold != NoThreshold) {
 128     unsigned LoopSize = ApproximateLoopSize(L);
 129     DOUT << "  Loop Size = " << LoopSize << "\n";
 130     uint64_t Size = (uint64_t)LoopSize*Count;
 131     if (TripCount != 1 && Size > UnrollThreshold) {
 132       DOUT << "  TOO LARGE TO UNROLL: "
 133            << Size << ">" << UnrollThreshold << "\n";
 134       return false;
 135     }
 136   }
 137
 138   // Unroll the loop.
 139   if (!UnrollLoop(L, Count, LI, &LPM))
 140     return false;
 141
 142   return true;
 143 }