Home | History | Annotate | Download | only in Scalar 
      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/LoopPass.h"
     19 #include "llvm/Analysis/CodeMetrics.h"
     20 #include "llvm/Analysis/ScalarEvolution.h"
     21 #include "llvm/Support/CommandLine.h"
     22 #include "llvm/Support/Debug.h"
     23 #include "llvm/Support/raw_ostream.h"
     24 #include "llvm/Transforms/Utils/UnrollLoop.h"
     25 #include "llvm/Target/TargetData.h"
     26 #include <climits>
     27 
     28 using namespace llvm;
     29 
     30 static cl::opt<unsigned>
     31 UnrollThreshold("unroll-threshold", cl::init(150), cl::Hidden,
     32   cl::desc("The cut-off point for automatic loop unrolling"));
     33 
     34 static cl::opt<unsigned>
     35 UnrollCount("unroll-count", cl::init(0), cl::Hidden,
     36   cl::desc("Use this unroll count for all loops, for testing purposes"));
     37 
     38 static cl::opt<bool>
     39 UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden,
     40   cl::desc("Allows loops to be partially unrolled until "
     41            "-unroll-threshold loop size is reached."));
     42 
     43 static cl::opt<bool>
     44 UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::init(false), cl::Hidden,
     45   cl::desc("Unroll loops with run-time trip counts"));
     46 
     47 namespace {
     48   class LoopUnroll : public LoopPass {
     49   public:
     50     static char ID; // Pass ID, replacement for typeid
     51     LoopUnroll(int T = -1, int C = -1,  int P = -1) : LoopPass(ID) {
     52       CurrentThreshold = (T == -1) ? UnrollThreshold : unsigned(T);
     53       CurrentCount = (C == -1) ? UnrollCount : unsigned(C);
     54       CurrentAllowPartial = (P == -1) ? UnrollAllowPartial : (bool)P;
     55 
     56       UserThreshold = (T != -1) || (UnrollThreshold.getNumOccurrences() > 0);
     57 
     58       initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
     59     }
     60 
     61     /// A magic value for use with the Threshold parameter to indicate
     62     /// that the loop unroll should be performed regardless of how much
     63     /// code expansion would result.
     64     static const unsigned NoThreshold = UINT_MAX;
     65 
     66     // Threshold to use when optsize is specified (and there is no
     67     // explicit -unroll-threshold).
     68     static const unsigned OptSizeUnrollThreshold = 50;
     69 
     70     // Default unroll count for loops with run-time trip count if
     71     // -unroll-count is not set
     72     static const unsigned UnrollRuntimeCount = 8;
     73 
     74     unsigned CurrentCount;
     75     unsigned CurrentThreshold;
     76     bool     CurrentAllowPartial;
     77     bool     UserThreshold;        // CurrentThreshold is user-specified.
     78 
     79     bool runOnLoop(Loop *L, LPPassManager &LPM);
     80 
     81     /// This transformation requires natural loop information & requires that
     82     /// loop preheaders be inserted into the CFG...
     83     ///
     84     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     85       AU.addRequired<LoopInfo>();
     86       AU.addPreserved<LoopInfo>();
     87       AU.addRequiredID(LoopSimplifyID);
     88       AU.addPreservedID(LoopSimplifyID);
     89       AU.addRequiredID(LCSSAID);
     90       AU.addPreservedID(LCSSAID);
     91       AU.addRequired<ScalarEvolution>();
     92       AU.addPreserved<ScalarEvolution>();
     93       // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info.
     94       // If loop unroll does not preserve dom info then LCSSA pass on next
     95       // loop will receive invalid dom info.
     96       // For now, recreate dom info, if loop is unrolled.
     97       AU.addPreserved<DominatorTree>();
     98     }
     99   };
    100 }
    101 
    102 char LoopUnroll::ID = 0;
    103 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
    104 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
    105 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
    106 INITIALIZE_PASS_DEPENDENCY(LCSSA)
    107 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
    108 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
    109 
    110 Pass *llvm::createLoopUnrollPass(int Threshold, int Count, int AllowPartial) {
    111   return new LoopUnroll(Threshold, Count, AllowPartial);
    112 }
    113 
    114 /// ApproximateLoopSize - Approximate the size of the loop.
    115 static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
    116                                     const TargetData *TD) {
    117   CodeMetrics Metrics;
    118   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
    119        I != E; ++I)
    120     Metrics.analyzeBasicBlock(*I, TD);
    121   NumCalls = Metrics.NumInlineCandidates;
    122 
    123   unsigned LoopSize = Metrics.NumInsts;
    124 
    125   // Don't allow an estimate of size zero.  This would allows unrolling of loops
    126   // with huge iteration counts, which is a compile time problem even if it's
    127   // not a problem for code quality.
    128   if (LoopSize == 0) LoopSize = 1;
    129 
    130   return LoopSize;
    131 }
    132 
    133 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
    134   LoopInfo *LI = &getAnalysis<LoopInfo>();
    135   ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
    136 
    137   BasicBlock *Header = L->getHeader();
    138   DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName()
    139         << "] Loop %" << Header->getName() << "\n");
    140   (void)Header;
    141 
    142   // Determine the current unrolling threshold.  While this is normally set
    143   // from UnrollThreshold, it is overridden to a smaller value if the current
    144   // function is marked as optimize-for-size, and the unroll threshold was
    145   // not user specified.
    146   unsigned Threshold = CurrentThreshold;
    147   if (!UserThreshold &&
    148       Header->getParent()->hasFnAttr(Attribute::OptimizeForSize))
    149     Threshold = OptSizeUnrollThreshold;
    150 
    151   // Find trip count and trip multiple if count is not available
    152   unsigned TripCount = 0;
    153   unsigned TripMultiple = 1;
    154   // Find "latch trip count". UnrollLoop assumes that control cannot exit
    155   // via the loop latch on any iteration prior to TripCount. The loop may exit
    156   // early via an earlier branch.
    157   BasicBlock *LatchBlock = L->getLoopLatch();
    158   if (LatchBlock) {
    159     TripCount = SE->getSmallConstantTripCount(L, LatchBlock);
    160     TripMultiple = SE->getSmallConstantTripMultiple(L, LatchBlock);
    161   }
    162   // Use a default unroll-count if the user doesn't specify a value
    163   // and the trip count is a run-time value.  The default is different
    164   // for run-time or compile-time trip count loops.
    165   unsigned Count = CurrentCount;
    166   if (UnrollRuntime && CurrentCount == 0 && TripCount == 0)
    167     Count = UnrollRuntimeCount;
    168 
    169   if (Count == 0) {
    170     // Conservative heuristic: if we know the trip count, see if we can
    171     // completely unroll (subject to the threshold, checked below); otherwise
    172     // try to find greatest modulo of the trip count which is still under
    173     // threshold value.
    174     if (TripCount == 0)
    175       return false;
    176     Count = TripCount;
    177   }
    178 
    179   // Enforce the threshold.
    180   if (Threshold != NoThreshold) {
    181     const TargetData *TD = getAnalysisIfAvailable<TargetData>();
    182     unsigned NumInlineCandidates;
    183     unsigned LoopSize = ApproximateLoopSize(L, NumInlineCandidates, TD);
    184     DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
    185     if (NumInlineCandidates != 0) {
    186       DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
    187       return false;
    188     }
    189     uint64_t Size = (uint64_t)LoopSize*Count;
    190     if (TripCount != 1 && Size > Threshold) {
    191       DEBUG(dbgs() << "  Too large to fully unroll with count: " << Count
    192             << " because size: " << Size << ">" << Threshold << "\n");
    193       if (!CurrentAllowPartial && !(UnrollRuntime && TripCount == 0)) {
    194         DEBUG(dbgs() << "  will not try to unroll partially because "
    195               << "-unroll-allow-partial not given\n");
    196         return false;
    197       }
    198       if (TripCount) {
    199         // Reduce unroll count to be modulo of TripCount for partial unrolling
    200         Count = Threshold / LoopSize;
    201         while (Count != 0 && TripCount%Count != 0)
    202           Count--;
    203       }
    204       else if (UnrollRuntime) {
    205         // Reduce unroll count to be a lower power-of-two value
    206         while (Count != 0 && Size > Threshold) {
    207           Count >>= 1;
    208           Size = LoopSize*Count;
    209         }
    210       }
    211       if (Count < 2) {
    212         DEBUG(dbgs() << "  could not unroll partially\n");
    213         return false;
    214       }
    215       DEBUG(dbgs() << "  partially unrolling with count: " << Count << "\n");
    216     }
    217   }
    218 
    219   // Unroll the loop.
    220   if (!UnrollLoop(L, Count, TripCount, UnrollRuntime, TripMultiple, LI, &LPM))
    221     return false;
    222 
    223   return true;
    224 }
    225