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