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
28using namespace llvm;
29
30static cl::opt<unsigned>
31UnrollThreshold("unroll-threshold", cl::init(150), cl::Hidden,
32  cl::desc("The cut-off point for automatic loop unrolling"));
33
34static cl::opt<unsigned>
35UnrollCount("unroll-count", cl::init(0), cl::Hidden,
36  cl::desc("Use this unroll count for all loops, for testing purposes"));
37
38static cl::opt<bool>
39UnrollAllowPartial("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
43static cl::opt<bool>
44UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::init(false), cl::Hidden,
45  cl::desc("Unroll loops with run-time trip counts"));
46
47namespace {
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
102char LoopUnroll::ID = 0;
103INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
104INITIALIZE_PASS_DEPENDENCY(LoopInfo)
105INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
106INITIALIZE_PASS_DEPENDENCY(LCSSA)
107INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
108INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
109
110Pass *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.
115static 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
133bool 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