LoopUnrollPass.cpp revision 6765834754cbb3cb0f15b4b15e98c5e73fa50066 
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/DataLayout.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 DataLayout *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()->getFnAttributes().
149        hasAttribute(Attributes::OptimizeForSize))
150    Threshold = OptSizeUnrollThreshold;
151
152  // Find trip count and trip multiple if count is not available
153  unsigned TripCount = 0;
154  unsigned TripMultiple = 1;
155  // Find "latch trip count". UnrollLoop assumes that control cannot exit
156  // via the loop latch on any iteration prior to TripCount. The loop may exit
157  // early via an earlier branch.
158  BasicBlock *LatchBlock = L->getLoopLatch();
159  if (LatchBlock) {
160    TripCount = SE->getSmallConstantTripCount(L, LatchBlock);
161    TripMultiple = SE->getSmallConstantTripMultiple(L, LatchBlock);
162  }
163  // Use a default unroll-count if the user doesn't specify a value
164  // and the trip count is a run-time value.  The default is different
165  // for run-time or compile-time trip count loops.
166  unsigned Count = CurrentCount;
167  if (UnrollRuntime && CurrentCount == 0 && TripCount == 0)
168    Count = UnrollRuntimeCount;
169
170  if (Count == 0) {
171    // Conservative heuristic: if we know the trip count, see if we can
172    // completely unroll (subject to the threshold, checked below); otherwise
173    // try to find greatest modulo of the trip count which is still under
174    // threshold value.
175    if (TripCount == 0)
176      return false;
177    Count = TripCount;
178  }
179
180  // Enforce the threshold.
181  if (Threshold != NoThreshold) {
182    const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
183    unsigned NumInlineCandidates;
184    unsigned LoopSize = ApproximateLoopSize(L, NumInlineCandidates, TD);
185    DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
186    if (NumInlineCandidates != 0) {
187      DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
188      return false;
189    }
190    uint64_t Size = (uint64_t)LoopSize*Count;
191    if (TripCount != 1 && Size > Threshold) {
192      DEBUG(dbgs() << "  Too large to fully unroll with count: " << Count
193            << " because size: " << Size << ">" << Threshold << "\n");
194      if (!CurrentAllowPartial && !(UnrollRuntime && TripCount == 0)) {
195        DEBUG(dbgs() << "  will not try to unroll partially because "
196              << "-unroll-allow-partial not given\n");
197        return false;
198      }
199      if (TripCount) {
200        // Reduce unroll count to be modulo of TripCount for partial unrolling
201        Count = Threshold / LoopSize;
202        while (Count != 0 && TripCount%Count != 0)
203          Count--;
204      }
205      else if (UnrollRuntime) {
206        // Reduce unroll count to be a lower power-of-two value
207        while (Count != 0 && Size > Threshold) {
208          Count >>= 1;
209          Size = LoopSize*Count;
210        }
211      }
212      if (Count < 2) {
213        DEBUG(dbgs() << "  could not unroll partially\n");
214        return false;
215      }
216      DEBUG(dbgs() << "  partially unrolling with count: " << Count << "\n");
217    }
218  }
219
220  // Unroll the loop.
221  if (!UnrollLoop(L, Count, TripCount, UnrollRuntime, TripMultiple, LI, &LPM))
222    return false;
223
224  return true;
225}
226