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 (Loop::block_iterator I = L->block_begin(), E = L->block_end();
  71        I != E; ++I) {
  72     BasicBlock *BB = *I;
  73     Instruction *Term = BB->getTerminator();
  74     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
  75       if (isa<PHINode>(I) && BB == L->getHeader()) {
  76         // Ignore PHI nodes in the header.
  77       } else if (I->hasOneUse() && I->use_back() == Term) {
  78         // Ignore instructions only used by the loop terminator.
  79       } else if (isa<DbgInfoIntrinsic>(I)) {
  80         // Ignore debug instructions
  81       } else if (isa<CallInst>(I)) {
  82         // Estimate size overhead introduced by call instructions which
  83         // is higher than other instructions. Here 3 and 10 are magic
  84         // numbers that help one isolated test case from PR2067 without
  85         // negatively impacting measured benchmarks.
  86         if (isa<IntrinsicInst>(I))
  87           Size = Size + 3;
  88         else
  89           Size = Size + 10;
  90       } else {
  91         ++Size;
  92       }
  93
  94       // TODO: Ignore expressions derived from PHI and constants if inval of phi
  95       // is a constant, or if operation is associative.  This will get induction
  96       // variables.
  97     }
  98   }
  99
 100   return Size;
 101 }
 102
 103 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
 104   assert(L->isLCSSAForm());
 105   LoopInfo *LI = &getAnalysis<LoopInfo>();
 106
 107   BasicBlock *Header = L->getHeader();
 108   DOUT << "Loop Unroll: F[" << Header->getParent()->getName()
 109        << "] Loop %" << Header->getName() << "\n";
 110
 111   // Find trip count
 112   unsigned TripCount = L->getSmallConstantTripCount();
 113   unsigned Count = UnrollCount;
 114
 115   // Automatically select an unroll count.
 116   if (Count == 0) {
 117     // Conservative heuristic: if we know the trip count, see if we can
 118     // completely unroll (subject to the threshold, checked below); otherwise
 119     // don't unroll.
 120     if (TripCount != 0) {
 121       Count = TripCount;
 122     } else {
 123       return false;
 124     }
 125   }
 126
 127   // Enforce the threshold.
 128   if (UnrollThreshold != NoThreshold) {
 129     unsigned LoopSize = ApproximateLoopSize(L);
 130     DOUT << "  Loop Size = " << LoopSize << "\n";
 131     uint64_t Size = (uint64_t)LoopSize*Count;
 132     if (TripCount != 1 && Size > UnrollThreshold) {
 133       DOUT << "  TOO LARGE TO UNROLL: "
 134            << Size << ">" << UnrollThreshold << "\n";
 135       return false;
 136     }
 137   }
 138
 139   // Unroll the loop.
 140   if (!UnrollLoop(L, Count, LI, &LPM))
 141     return false;
 142
 143   return true;
 144 }