blob: add18f3a0bf2ca92c4468ef93d8ce7f55fbfafe0 [file] [log] [blame]
Chris Lattner946b2552004-04-18 05:20:17 +00001//===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
Chris Lattner946b2552004-04-18 05:20:17 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanb1c93172005-04-21 23:48:37 +00007//
Chris Lattner946b2552004-04-18 05:20:17 +00008//===----------------------------------------------------------------------===//
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.
Chris Lattner946b2552004-04-18 05:20:17 +000013//===----------------------------------------------------------------------===//
14
Sean Silvae3c18a52016-07-19 23:54:23 +000015#include "llvm/Transforms/Scalar/LoopUnrollPass.h"
Chandler Carruth3b057b32015-02-13 03:57:40 +000016#include "llvm/ADT/SetVector.h"
Daniel Jasperaec2fa32016-12-19 08:22:17 +000017#include "llvm/Analysis/AssumptionCache.h"
Chris Lattner679572e2011-01-02 07:35:53 +000018#include "llvm/Analysis/CodeMetrics.h"
Dehao Chend55bc4c2016-05-05 00:54:54 +000019#include "llvm/Analysis/GlobalsModRef.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000020#include "llvm/Analysis/InstructionSimplify.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000021#include "llvm/Analysis/LoopPass.h"
Michael Zolotukhin1da4afd2016-02-08 23:03:59 +000022#include "llvm/Analysis/LoopUnrollAnalyzer.h"
Adam Nemet12937c32016-07-29 19:29:47 +000023#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
Teresa Johnson8482e562017-08-03 23:42:58 +000024#include "llvm/Analysis/ProfileSummaryInfo.h"
Dan Gohman0141c132010-07-26 18:11:16 +000025#include "llvm/Analysis/ScalarEvolution.h"
Michael Zolotukhina9aadd22015-02-05 02:34:00 +000026#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000027#include "llvm/IR/DataLayout.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000028#include "llvm/IR/Dominators.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000029#include "llvm/IR/InstVisitor.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000030#include "llvm/IR/IntrinsicInst.h"
Eli Benderskyff903242014-06-16 23:53:02 +000031#include "llvm/IR/Metadata.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000032#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/Debug.h"
Daniel Dunbar0dd5e1e2009-07-25 00:23:56 +000034#include "llvm/Support/raw_ostream.h"
Dehao Chend55bc4c2016-05-05 00:54:54 +000035#include "llvm/Transforms/Scalar.h"
Chandler Carruth3bab7e12017-01-11 09:43:56 +000036#include "llvm/Transforms/Scalar/LoopPassManager.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000037#include "llvm/Transforms/Utils/LoopUtils.h"
Dan Gohman3dc2d922008-05-14 00:24:14 +000038#include "llvm/Transforms/Utils/UnrollLoop.h"
Duncan Sands67933e62008-05-16 09:30:00 +000039#include <climits>
Benjamin Kramer82de7d32016-05-27 14:27:24 +000040#include <utility>
Chris Lattner946b2552004-04-18 05:20:17 +000041
Dan Gohman3dc2d922008-05-14 00:24:14 +000042using namespace llvm;
Chris Lattner946b2552004-04-18 05:20:17 +000043
Chandler Carruth964daaa2014-04-22 02:55:47 +000044#define DEBUG_TYPE "loop-unroll"
45
Dan Gohmand78c4002008-05-13 00:00:25 +000046static cl::opt<unsigned>
Justin Bognera1dd4932016-01-12 00:55:26 +000047 UnrollThreshold("unroll-threshold", cl::Hidden,
Dehao Chenc3f87f02017-01-17 23:39:33 +000048 cl::desc("The cost threshold for loop unrolling"));
49
50static cl::opt<unsigned> UnrollPartialThreshold(
51 "unroll-partial-threshold", cl::Hidden,
52 cl::desc("The cost threshold for partial loop unrolling"));
Chandler Carruth9dabd142015-06-05 17:01:43 +000053
Dehao Chencc763442016-12-30 00:50:28 +000054static cl::opt<unsigned> UnrollMaxPercentThresholdBoost(
55 "unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden,
56 cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied "
57 "to the threshold when aggressively unrolling a loop due to the "
58 "dynamic cost savings. If completely unrolling a loop will reduce "
59 "the total runtime from X to Y, we boost the loop unroll "
60 "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, "
61 "X/Y). This limit avoids excessive code bloat."));
Dan Gohmand78c4002008-05-13 00:00:25 +000062
Michael Zolotukhina9aadd22015-02-05 02:34:00 +000063static cl::opt<unsigned> UnrollMaxIterationsCountToAnalyze(
Michael Zolotukhin8f7a2422016-05-24 23:00:05 +000064 "unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden,
Michael Zolotukhina9aadd22015-02-05 02:34:00 +000065 cl::desc("Don't allow loop unrolling to simulate more than this number of"
66 "iterations when checking full unroll profitability"));
67
Dehao Chend55bc4c2016-05-05 00:54:54 +000068static cl::opt<unsigned> UnrollCount(
69 "unroll-count", cl::Hidden,
70 cl::desc("Use this unroll count for all loops including those with "
71 "unroll_count pragma values, for testing purposes"));
Dan Gohmand78c4002008-05-13 00:00:25 +000072
Dehao Chend55bc4c2016-05-05 00:54:54 +000073static cl::opt<unsigned> UnrollMaxCount(
74 "unroll-max-count", cl::Hidden,
75 cl::desc("Set the max unroll count for partial and runtime unrolling, for"
76 "testing purposes"));
Fiona Glaser045afc42016-04-06 16:57:25 +000077
Dehao Chend55bc4c2016-05-05 00:54:54 +000078static cl::opt<unsigned> UnrollFullMaxCount(
79 "unroll-full-max-count", cl::Hidden,
80 cl::desc(
81 "Set the max unroll count for full unrolling, for testing purposes"));
Fiona Glaser045afc42016-04-06 16:57:25 +000082
Davide Italiano9a09ae42017-08-28 19:50:55 +000083static cl::opt<unsigned> UnrollPeelCount(
84 "unroll-peel-count", cl::Hidden,
85 cl::desc("Set the unroll peeling count, for testing purposes"));
86
Matthijs Kooijman98b5c162008-07-29 13:21:23 +000087static cl::opt<bool>
Dehao Chend55bc4c2016-05-05 00:54:54 +000088 UnrollAllowPartial("unroll-allow-partial", cl::Hidden,
89 cl::desc("Allows loops to be partially unrolled until "
90 "-unroll-threshold loop size is reached."));
Matthijs Kooijman98b5c162008-07-29 13:21:23 +000091
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +000092static cl::opt<bool> UnrollAllowRemainder(
93 "unroll-allow-remainder", cl::Hidden,
94 cl::desc("Allow generation of a loop remainder (extra iterations) "
95 "when unrolling a loop."));
96
Andrew Trickd04d15292011-12-09 06:19:40 +000097static cl::opt<bool>
Dehao Chend55bc4c2016-05-05 00:54:54 +000098 UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden,
99 cl::desc("Unroll loops with run-time trip counts"));
Andrew Trickd04d15292011-12-09 06:19:40 +0000100
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000101static cl::opt<unsigned> UnrollMaxUpperBound(
102 "unroll-max-upperbound", cl::init(8), cl::Hidden,
103 cl::desc(
104 "The max of trip count upper bound that is considered in unrolling"));
105
Dehao Chend55bc4c2016-05-05 00:54:54 +0000106static cl::opt<unsigned> PragmaUnrollThreshold(
107 "pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden,
108 cl::desc("Unrolled size limit for loops with an unroll(full) or "
109 "unroll_count pragma."));
Justin Bognera1dd4932016-01-12 00:55:26 +0000110
Dehao Chen41d72a82016-11-17 01:17:02 +0000111static cl::opt<unsigned> FlatLoopTripCountThreshold(
112 "flat-loop-tripcount-threshold", cl::init(5), cl::Hidden,
113 cl::desc("If the runtime tripcount for the loop is lower than the "
114 "threshold, the loop is considered as flat and will be less "
115 "aggressively unrolled."));
116
Michael Kupersteinb151a642016-11-30 21:13:57 +0000117static cl::opt<bool>
Michael Kupersteinc2af82b2017-02-22 00:27:34 +0000118 UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden,
Michael Kupersteinb151a642016-11-30 21:13:57 +0000119 cl::desc("Allows loops to be peeled when the dynamic "
120 "trip count is known to be low."));
121
Sam Parker718c8a62017-08-14 09:25:26 +0000122static cl::opt<bool> UnrollUnrollRemainder(
123 "unroll-remainder", cl::Hidden,
124 cl::desc("Allow the loop remainder to be unrolled."));
125
Chandler Carruthce40fa12017-01-25 02:49:01 +0000126// This option isn't ever intended to be enabled, it serves to allow
127// experiments to check the assumptions about when this kind of revisit is
128// necessary.
129static cl::opt<bool> UnrollRevisitChildLoops(
130 "unroll-revisit-child-loops", cl::Hidden,
131 cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. "
132 "This shouldn't typically be needed as child loops (or their "
133 "clones) were already visited."));
134
Justin Bognera1dd4932016-01-12 00:55:26 +0000135/// A magic value for use with the Threshold parameter to indicate
136/// that the loop unroll should be performed regardless of how much
137/// code expansion would result.
138static const unsigned NoThreshold = UINT_MAX;
139
Justin Bognera1dd4932016-01-12 00:55:26 +0000140/// Gather the various unrolling parameters based on the defaults, compiler
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000141/// flags, TTI overrides and user specified parameters.
Justin Bognera1dd4932016-01-12 00:55:26 +0000142static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
Geoff Berry66d9bdb2017-06-28 15:53:17 +0000143 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
Dehao Chen7d230322017-02-18 03:46:51 +0000144 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
145 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
Teresa Johnson9a18a6f2017-08-03 17:52:38 +0000146 Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling) {
Justin Bognera1dd4932016-01-12 00:55:26 +0000147 TargetTransformInfo::UnrollingPreferences UP;
148
149 // Set up the defaults
Dehao Chen7d230322017-02-18 03:46:51 +0000150 UP.Threshold = OptLevel > 2 ? 300 : 150;
Dehao Chencc763442016-12-30 00:50:28 +0000151 UP.MaxPercentThresholdBoost = 400;
Hans Wennborg719b26b2016-05-10 21:45:55 +0000152 UP.OptSizeThreshold = 0;
Dehao Chenc3f87f02017-01-17 23:39:33 +0000153 UP.PartialThreshold = 150;
Hans Wennborg719b26b2016-05-10 21:45:55 +0000154 UP.PartialOptSizeThreshold = 0;
Justin Bognera1dd4932016-01-12 00:55:26 +0000155 UP.Count = 0;
Michael Kupersteinb151a642016-11-30 21:13:57 +0000156 UP.PeelCount = 0;
Jonas Paulsson58c5a7f2016-09-28 09:41:38 +0000157 UP.DefaultUnrollRuntimeCount = 8;
Justin Bognera1dd4932016-01-12 00:55:26 +0000158 UP.MaxCount = UINT_MAX;
Fiona Glaser045afc42016-04-06 16:57:25 +0000159 UP.FullUnrollMaxCount = UINT_MAX;
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000160 UP.BEInsns = 2;
Justin Bognera1dd4932016-01-12 00:55:26 +0000161 UP.Partial = false;
162 UP.Runtime = false;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000163 UP.AllowRemainder = true;
Sam Parker718c8a62017-08-14 09:25:26 +0000164 UP.UnrollRemainder = false;
Justin Bognera1dd4932016-01-12 00:55:26 +0000165 UP.AllowExpensiveTripCount = false;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000166 UP.Force = false;
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000167 UP.UpperBound = false;
Michael Kupersteinc2af82b2017-02-22 00:27:34 +0000168 UP.AllowPeeling = true;
Justin Bognera1dd4932016-01-12 00:55:26 +0000169
170 // Override with any target specific settings
Geoff Berry66d9bdb2017-06-28 15:53:17 +0000171 TTI.getUnrollingPreferences(L, SE, UP);
Justin Bognera1dd4932016-01-12 00:55:26 +0000172
173 // Apply size attributes
174 if (L->getHeader()->getParent()->optForSize()) {
175 UP.Threshold = UP.OptSizeThreshold;
176 UP.PartialThreshold = UP.PartialOptSizeThreshold;
177 }
178
Justin Bognera1dd4932016-01-12 00:55:26 +0000179 // Apply any user values specified by cl::opt
Dehao Chenc3f87f02017-01-17 23:39:33 +0000180 if (UnrollThreshold.getNumOccurrences() > 0)
Justin Bognera1dd4932016-01-12 00:55:26 +0000181 UP.Threshold = UnrollThreshold;
Dehao Chenc3f87f02017-01-17 23:39:33 +0000182 if (UnrollPartialThreshold.getNumOccurrences() > 0)
183 UP.PartialThreshold = UnrollPartialThreshold;
Dehao Chencc763442016-12-30 00:50:28 +0000184 if (UnrollMaxPercentThresholdBoost.getNumOccurrences() > 0)
185 UP.MaxPercentThresholdBoost = UnrollMaxPercentThresholdBoost;
Fiona Glaser045afc42016-04-06 16:57:25 +0000186 if (UnrollMaxCount.getNumOccurrences() > 0)
187 UP.MaxCount = UnrollMaxCount;
188 if (UnrollFullMaxCount.getNumOccurrences() > 0)
189 UP.FullUnrollMaxCount = UnrollFullMaxCount;
Davide Italiano9a09ae42017-08-28 19:50:55 +0000190 if (UnrollPeelCount.getNumOccurrences() > 0)
191 UP.PeelCount = UnrollPeelCount;
Justin Bognera1dd4932016-01-12 00:55:26 +0000192 if (UnrollAllowPartial.getNumOccurrences() > 0)
193 UP.Partial = UnrollAllowPartial;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000194 if (UnrollAllowRemainder.getNumOccurrences() > 0)
195 UP.AllowRemainder = UnrollAllowRemainder;
Justin Bognera1dd4932016-01-12 00:55:26 +0000196 if (UnrollRuntime.getNumOccurrences() > 0)
197 UP.Runtime = UnrollRuntime;
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000198 if (UnrollMaxUpperBound == 0)
199 UP.UpperBound = false;
Michael Kupersteinb151a642016-11-30 21:13:57 +0000200 if (UnrollAllowPeeling.getNumOccurrences() > 0)
201 UP.AllowPeeling = UnrollAllowPeeling;
Sam Parker718c8a62017-08-14 09:25:26 +0000202 if (UnrollUnrollRemainder.getNumOccurrences() > 0)
203 UP.UnrollRemainder = UnrollUnrollRemainder;
Justin Bognera1dd4932016-01-12 00:55:26 +0000204
205 // Apply user values provided by argument
206 if (UserThreshold.hasValue()) {
207 UP.Threshold = *UserThreshold;
208 UP.PartialThreshold = *UserThreshold;
209 }
210 if (UserCount.hasValue())
211 UP.Count = *UserCount;
212 if (UserAllowPartial.hasValue())
213 UP.Partial = *UserAllowPartial;
214 if (UserRuntime.hasValue())
215 UP.Runtime = *UserRuntime;
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000216 if (UserUpperBound.hasValue())
217 UP.UpperBound = *UserUpperBound;
Teresa Johnson9a18a6f2017-08-03 17:52:38 +0000218 if (UserAllowPeeling.hasValue())
219 UP.AllowPeeling = *UserAllowPeeling;
Justin Bognera1dd4932016-01-12 00:55:26 +0000220
Justin Bognera1dd4932016-01-12 00:55:26 +0000221 return UP;
222}
223
Chris Lattner79a42ac2006-12-19 21:40:18 +0000224namespace {
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000225/// A struct to densely store the state of an instruction after unrolling at
226/// each iteration.
227///
228/// This is designed to work like a tuple of <Instruction *, int> for the
229/// purposes of hashing and lookup, but to be able to associate two boolean
230/// states with each key.
231struct UnrolledInstState {
232 Instruction *I;
233 int Iteration : 30;
234 unsigned IsFree : 1;
235 unsigned IsCounted : 1;
236};
237
238/// Hashing and equality testing for a set of the instruction states.
239struct UnrolledInstStateKeyInfo {
240 typedef DenseMapInfo<Instruction *> PtrInfo;
241 typedef DenseMapInfo<std::pair<Instruction *, int>> PairInfo;
242 static inline UnrolledInstState getEmptyKey() {
243 return {PtrInfo::getEmptyKey(), 0, 0, 0};
244 }
245 static inline UnrolledInstState getTombstoneKey() {
246 return {PtrInfo::getTombstoneKey(), 0, 0, 0};
247 }
248 static inline unsigned getHashValue(const UnrolledInstState &S) {
249 return PairInfo::getHashValue({S.I, S.Iteration});
250 }
251 static inline bool isEqual(const UnrolledInstState &LHS,
252 const UnrolledInstState &RHS) {
253 return PairInfo::isEqual({LHS.I, LHS.Iteration}, {RHS.I, RHS.Iteration});
254 }
255};
256}
257
258namespace {
Chandler Carruth02156082015-05-22 17:41:35 +0000259struct EstimatedUnrollCost {
Chandler Carruth9dabd142015-06-05 17:01:43 +0000260 /// \brief The estimated cost after unrolling.
Dehao Chenc3be2252016-12-02 03:17:07 +0000261 unsigned UnrolledCost;
Chandler Carruth302a1332015-02-13 02:10:56 +0000262
Chandler Carruth9dabd142015-06-05 17:01:43 +0000263 /// \brief The estimated dynamic cost of executing the instructions in the
264 /// rolled form.
Dehao Chenc3be2252016-12-02 03:17:07 +0000265 unsigned RolledDynamicCost;
Chandler Carruth02156082015-05-22 17:41:35 +0000266};
267}
Michael Zolotukhina9aadd22015-02-05 02:34:00 +0000268
Chandler Carruth02156082015-05-22 17:41:35 +0000269/// \brief Figure out if the loop is worth full unrolling.
270///
271/// Complete loop unrolling can make some loads constant, and we need to know
272/// if that would expose any further optimization opportunities. This routine
Michael Zolotukhinc4e4f332015-06-11 22:17:39 +0000273/// estimates this optimization. It computes cost of unrolled loop
274/// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
275/// dynamic cost we mean that we won't count costs of blocks that are known not
276/// to be executed (i.e. if we have a branch in the loop and we know that at the
277/// given iteration its condition would be resolved to true, we won't add up the
278/// cost of the 'false'-block).
279/// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
280/// the analysis failed (no benefits expected from the unrolling, or the loop is
281/// too big to analyze), the returned value is None.
Benjamin Kramerfcdb1c12015-08-20 09:57:22 +0000282static Optional<EstimatedUnrollCost>
Chandler Carruth87adb7a2015-08-03 20:32:27 +0000283analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT,
284 ScalarEvolution &SE, const TargetTransformInfo &TTI,
Dehao Chenc3be2252016-12-02 03:17:07 +0000285 unsigned MaxUnrolledLoopSize) {
Chandler Carruth02156082015-05-22 17:41:35 +0000286 // We want to be able to scale offsets by the trip count and add more offsets
287 // to them without checking for overflows, and we already don't want to
288 // analyze *massive* trip counts, so we force the max to be reasonably small.
289 assert(UnrollMaxIterationsCountToAnalyze < (INT_MAX / 2) &&
290 "The unroll iterations max is too large!");
Michael Zolotukhina9aadd22015-02-05 02:34:00 +0000291
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000292 // Only analyze inner loops. We can't properly estimate cost of nested loops
293 // and we won't visit inner loops again anyway.
294 if (!L->empty())
295 return None;
296
Chandler Carruth02156082015-05-22 17:41:35 +0000297 // Don't simulate loops with a big or unknown tripcount
298 if (!UnrollMaxIterationsCountToAnalyze || !TripCount ||
299 TripCount > UnrollMaxIterationsCountToAnalyze)
300 return None;
Chandler Carrutha6ae8772015-05-12 23:32:56 +0000301
Chandler Carruth02156082015-05-22 17:41:35 +0000302 SmallSetVector<BasicBlock *, 16> BBWorklist;
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000303 SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
Chandler Carruth02156082015-05-22 17:41:35 +0000304 DenseMap<Value *, Constant *> SimplifiedValues;
Chandler Carruth87adb7a2015-08-03 20:32:27 +0000305 SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
Chandler Carruth3b057b32015-02-13 03:57:40 +0000306
Chandler Carruth9dabd142015-06-05 17:01:43 +0000307 // The estimated cost of the unrolled form of the loop. We try to estimate
308 // this by simplifying as much as we can while computing the estimate.
Dehao Chenc3be2252016-12-02 03:17:07 +0000309 unsigned UnrolledCost = 0;
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000310
Chandler Carruth9dabd142015-06-05 17:01:43 +0000311 // We also track the estimated dynamic (that is, actually executed) cost in
312 // the rolled form. This helps identify cases when the savings from unrolling
313 // aren't just exposing dead control flows, but actual reduced dynamic
314 // instructions due to the simplifications which we expect to occur after
315 // unrolling.
Dehao Chenc3be2252016-12-02 03:17:07 +0000316 unsigned RolledDynamicCost = 0;
Chandler Carruth8c863752015-02-13 03:48:38 +0000317
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000318 // We track the simplification of each instruction in each iteration. We use
319 // this to recursively merge costs into the unrolled cost on-demand so that
320 // we don't count the cost of any dead code. This is essentially a map from
321 // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
322 DenseSet<UnrolledInstState, UnrolledInstStateKeyInfo> InstCostMap;
323
324 // A small worklist used to accumulate cost of instructions from each
325 // observable and reached root in the loop.
326 SmallVector<Instruction *, 16> CostWorklist;
327
328 // PHI-used worklist used between iterations while accumulating cost.
329 SmallVector<Instruction *, 4> PHIUsedList;
330
331 // Helper function to accumulate cost for instructions in the loop.
332 auto AddCostRecursively = [&](Instruction &RootI, int Iteration) {
333 assert(Iteration >= 0 && "Cannot have a negative iteration!");
334 assert(CostWorklist.empty() && "Must start with an empty cost list");
335 assert(PHIUsedList.empty() && "Must start with an empty phi used list");
336 CostWorklist.push_back(&RootI);
337 for (;; --Iteration) {
338 do {
339 Instruction *I = CostWorklist.pop_back_val();
340
341 // InstCostMap only uses I and Iteration as a key, the other two values
342 // don't matter here.
343 auto CostIter = InstCostMap.find({I, Iteration, 0, 0});
344 if (CostIter == InstCostMap.end())
345 // If an input to a PHI node comes from a dead path through the loop
346 // we may have no cost data for it here. What that actually means is
347 // that it is free.
348 continue;
349 auto &Cost = *CostIter;
350 if (Cost.IsCounted)
351 // Already counted this instruction.
352 continue;
353
354 // Mark that we are counting the cost of this instruction now.
355 Cost.IsCounted = true;
356
357 // If this is a PHI node in the loop header, just add it to the PHI set.
358 if (auto *PhiI = dyn_cast<PHINode>(I))
359 if (PhiI->getParent() == L->getHeader()) {
360 assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
361 "inherently simplify during unrolling.");
362 if (Iteration == 0)
363 continue;
364
365 // Push the incoming value from the backedge into the PHI used list
366 // if it is an in-loop instruction. We'll use this to populate the
367 // cost worklist for the next iteration (as we count backwards).
368 if (auto *OpI = dyn_cast<Instruction>(
369 PhiI->getIncomingValueForBlock(L->getLoopLatch())))
370 if (L->contains(OpI))
371 PHIUsedList.push_back(OpI);
372 continue;
373 }
374
375 // First accumulate the cost of this instruction.
376 if (!Cost.IsFree) {
377 UnrolledCost += TTI.getUserCost(I);
378 DEBUG(dbgs() << "Adding cost of instruction (iteration " << Iteration
379 << "): ");
380 DEBUG(I->dump());
381 }
382
383 // We must count the cost of every operand which is not free,
384 // recursively. If we reach a loop PHI node, simply add it to the set
385 // to be considered on the next iteration (backwards!).
386 for (Value *Op : I->operands()) {
387 // Check whether this operand is free due to being a constant or
388 // outside the loop.
389 auto *OpI = dyn_cast<Instruction>(Op);
390 if (!OpI || !L->contains(OpI))
391 continue;
392
393 // Otherwise accumulate its cost.
394 CostWorklist.push_back(OpI);
395 }
396 } while (!CostWorklist.empty());
397
398 if (PHIUsedList.empty())
399 // We've exhausted the search.
400 break;
401
402 assert(Iteration > 0 &&
403 "Cannot track PHI-used values past the first iteration!");
404 CostWorklist.append(PHIUsedList.begin(), PHIUsedList.end());
405 PHIUsedList.clear();
406 }
407 };
408
Chandler Carruth87adb7a2015-08-03 20:32:27 +0000409 // Ensure that we don't violate the loop structure invariants relied on by
410 // this analysis.
411 assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
412 assert(L->isLCSSAForm(DT) &&
413 "Must have loops in LCSSA form to track live-out values.");
414
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000415 DEBUG(dbgs() << "Starting LoopUnroll profitability analysis...\n");
416
Chandler Carruth02156082015-05-22 17:41:35 +0000417 // Simulate execution of each iteration of the loop counting instructions,
418 // which would be simplified.
419 // Since the same load will take different values on different iterations,
420 // we literally have to go through all loop's iterations.
421 for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000422 DEBUG(dbgs() << " Analyzing iteration " << Iteration << "\n");
Chandler Carruth87adb7a2015-08-03 20:32:27 +0000423
424 // Prepare for the iteration by collecting any simplified entry or backedge
425 // inputs.
426 for (Instruction &I : *L->getHeader()) {
427 auto *PHI = dyn_cast<PHINode>(&I);
428 if (!PHI)
429 break;
430
431 // The loop header PHI nodes must have exactly two input: one from the
432 // loop preheader and one from the loop latch.
433 assert(
434 PHI->getNumIncomingValues() == 2 &&
435 "Must have an incoming value only for the preheader and the latch.");
436
437 Value *V = PHI->getIncomingValueForBlock(
438 Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
439 Constant *C = dyn_cast<Constant>(V);
440 if (Iteration != 0 && !C)
441 C = SimplifiedValues.lookup(V);
442 if (C)
443 SimplifiedInputValues.push_back({PHI, C});
444 }
445
446 // Now clear and re-populate the map for the next iteration.
Chandler Carruth02156082015-05-22 17:41:35 +0000447 SimplifiedValues.clear();
Chandler Carruth87adb7a2015-08-03 20:32:27 +0000448 while (!SimplifiedInputValues.empty())
449 SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
450
Michael Zolotukhin9f520eb2016-02-26 02:57:05 +0000451 UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
Chandler Carruthf174a152015-05-22 02:47:29 +0000452
Chandler Carruth02156082015-05-22 17:41:35 +0000453 BBWorklist.clear();
454 BBWorklist.insert(L->getHeader());
455 // Note that we *must not* cache the size, this loop grows the worklist.
456 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
457 BasicBlock *BB = BBWorklist[Idx];
Chandler Carruthf174a152015-05-22 02:47:29 +0000458
Chandler Carruth02156082015-05-22 17:41:35 +0000459 // Visit all instructions in the given basic block and try to simplify
460 // it. We don't change the actual IR, just count optimization
461 // opportunities.
462 for (Instruction &I : *BB) {
Dehao Chen977853b2016-09-30 18:30:04 +0000463 if (isa<DbgInfoIntrinsic>(I))
464 continue;
465
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000466 // Track this instruction's expected baseline cost when executing the
467 // rolled loop form.
468 RolledDynamicCost += TTI.getUserCost(&I);
Chandler Carruth17a04962015-02-13 03:49:41 +0000469
Chandler Carruth02156082015-05-22 17:41:35 +0000470 // Visit the instruction to analyze its loop cost after unrolling,
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000471 // and if the visitor returns true, mark the instruction as free after
472 // unrolling and continue.
473 bool IsFree = Analyzer.visit(I);
474 bool Inserted = InstCostMap.insert({&I, (int)Iteration,
475 (unsigned)IsFree,
476 /*IsCounted*/ false}).second;
477 (void)Inserted;
478 assert(Inserted && "Cannot have a state for an unvisited instruction!");
Chandler Carruth9dabd142015-06-05 17:01:43 +0000479
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000480 if (IsFree)
481 continue;
482
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000483 // Can't properly model a cost of a call.
484 // FIXME: With a proper cost model we should be able to do it.
485 if(isa<CallInst>(&I))
486 return None;
Chandler Carruth02156082015-05-22 17:41:35 +0000487
Haicheng Wue7877632016-08-17 22:42:58 +0000488 // If the instruction might have a side-effect recursively account for
489 // the cost of it and all the instructions leading up to it.
490 if (I.mayHaveSideEffects())
491 AddCostRecursively(I, Iteration);
492
Chandler Carruth02156082015-05-22 17:41:35 +0000493 // If unrolled body turns out to be too big, bail out.
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000494 if (UnrolledCost > MaxUnrolledLoopSize) {
495 DEBUG(dbgs() << " Exceeded threshold.. exiting.\n"
496 << " UnrolledCost: " << UnrolledCost
497 << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
498 << "\n");
Chandler Carruth02156082015-05-22 17:41:35 +0000499 return None;
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000500 }
Michael Zolotukhina9aadd22015-02-05 02:34:00 +0000501 }
Chandler Carruth415f4122015-02-13 02:17:39 +0000502
Michael Zolotukhin57776b82015-07-24 01:53:04 +0000503 TerminatorInst *TI = BB->getTerminator();
504
505 // Add in the live successors by first checking whether we have terminator
506 // that may be simplified based on the values simplified by this call.
Michael Zolotukhin1ecdeda2016-05-26 21:42:51 +0000507 BasicBlock *KnownSucc = nullptr;
Michael Zolotukhin57776b82015-07-24 01:53:04 +0000508 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
509 if (BI->isConditional()) {
510 if (Constant *SimpleCond =
511 SimplifiedValues.lookup(BI->getCondition())) {
Michael Zolotukhin3a7d55b2015-07-29 18:10:29 +0000512 // Just take the first successor if condition is undef
513 if (isa<UndefValue>(SimpleCond))
Michael Zolotukhin1ecdeda2016-05-26 21:42:51 +0000514 KnownSucc = BI->getSuccessor(0);
515 else if (ConstantInt *SimpleCondVal =
516 dyn_cast<ConstantInt>(SimpleCond))
517 KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
Michael Zolotukhin57776b82015-07-24 01:53:04 +0000518 }
519 }
520 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
521 if (Constant *SimpleCond =
522 SimplifiedValues.lookup(SI->getCondition())) {
Michael Zolotukhin3a7d55b2015-07-29 18:10:29 +0000523 // Just take the first successor if condition is undef
524 if (isa<UndefValue>(SimpleCond))
Michael Zolotukhin1ecdeda2016-05-26 21:42:51 +0000525 KnownSucc = SI->getSuccessor(0);
526 else if (ConstantInt *SimpleCondVal =
527 dyn_cast<ConstantInt>(SimpleCond))
Chandler Carruth927d8e62017-04-12 07:27:28 +0000528 KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
Michael Zolotukhin57776b82015-07-24 01:53:04 +0000529 }
530 }
Michael Zolotukhin1ecdeda2016-05-26 21:42:51 +0000531 if (KnownSucc) {
532 if (L->contains(KnownSucc))
533 BBWorklist.insert(KnownSucc);
534 else
535 ExitWorklist.insert({BB, KnownSucc});
536 continue;
537 }
Michael Zolotukhin57776b82015-07-24 01:53:04 +0000538
Chandler Carruth02156082015-05-22 17:41:35 +0000539 // Add BB's successors to the worklist.
540 for (BasicBlock *Succ : successors(BB))
541 if (L->contains(Succ))
542 BBWorklist.insert(Succ);
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000543 else
544 ExitWorklist.insert({BB, Succ});
Michael Zolotukhind2268a72016-05-18 21:20:12 +0000545 AddCostRecursively(*TI, Iteration);
Michael Zolotukhina9aadd22015-02-05 02:34:00 +0000546 }
Chandler Carruth02156082015-05-22 17:41:35 +0000547
548 // If we found no optimization opportunities on the first iteration, we
549 // won't find them on later ones too.
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000550 if (UnrolledCost == RolledDynamicCost) {
551 DEBUG(dbgs() << " No opportunities found.. exiting.\n"
552 << " UnrolledCost: " << UnrolledCost << "\n");
Chandler Carruth02156082015-05-22 17:41:35 +0000553 return None;
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000554 }
Michael Zolotukhina9aadd22015-02-05 02:34:00 +0000555 }
Michael Zolotukhin963a6d92016-05-13 21:23:25 +0000556
557 while (!ExitWorklist.empty()) {
558 BasicBlock *ExitingBB, *ExitBB;
559 std::tie(ExitingBB, ExitBB) = ExitWorklist.pop_back_val();
560
561 for (Instruction &I : *ExitBB) {
562 auto *PN = dyn_cast<PHINode>(&I);
563 if (!PN)
564 break;
565
566 Value *Op = PN->getIncomingValueForBlock(ExitingBB);
567 if (auto *OpI = dyn_cast<Instruction>(Op))
568 if (L->contains(OpI))
569 AddCostRecursively(*OpI, TripCount - 1);
570 }
571 }
572
Michael Zolotukhin80d13ba2015-07-28 20:07:29 +0000573 DEBUG(dbgs() << "Analysis finished:\n"
574 << "UnrolledCost: " << UnrolledCost << ", "
575 << "RolledDynamicCost: " << RolledDynamicCost << "\n");
Chandler Carruth9dabd142015-06-05 17:01:43 +0000576 return {{UnrolledCost, RolledDynamicCost}};
Chandler Carruth02156082015-05-22 17:41:35 +0000577}
Michael Zolotukhina9aadd22015-02-05 02:34:00 +0000578
Dan Gohman49d08a52007-05-08 15:14:19 +0000579/// ApproximateLoopSize - Approximate the size of the loop.
Andrew Trickf7656012011-10-01 01:39:05 +0000580static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
Justin Lebar6827de12016-03-14 23:15:34 +0000581 bool &NotDuplicatable, bool &Convergent,
Hal Finkel57f03dd2014-09-07 13:49:57 +0000582 const TargetTransformInfo &TTI,
Daniel Jasperaec2fa32016-12-19 08:22:17 +0000583 AssumptionCache *AC, unsigned BEInsns) {
Hal Finkel57f03dd2014-09-07 13:49:57 +0000584 SmallPtrSet<const Value *, 32> EphValues;
Daniel Jasperaec2fa32016-12-19 08:22:17 +0000585 CodeMetrics::collectEphemeralValues(L, AC, EphValues);
Hal Finkel57f03dd2014-09-07 13:49:57 +0000586
Dan Gohman969e83a2009-10-31 14:54:17 +0000587 CodeMetrics Metrics;
Sanjay Patel5c967232016-03-08 19:06:12 +0000588 for (BasicBlock *BB : L->blocks())
589 Metrics.analyzeBasicBlock(BB, TTI, EphValues);
Owen Anderson04cf3fd2010-09-09 20:32:23 +0000590 NumCalls = Metrics.NumInlineCandidates;
James Molloy4f6fb952012-12-20 16:04:27 +0000591 NotDuplicatable = Metrics.notDuplicatable;
Justin Lebar6827de12016-03-14 23:15:34 +0000592 Convergent = Metrics.convergent;
Andrew Trick279e7a62011-07-23 00:29:16 +0000593
Owen Anderson62ea1b72010-09-09 19:07:31 +0000594 unsigned LoopSize = Metrics.NumInsts;
Andrew Trick279e7a62011-07-23 00:29:16 +0000595
Owen Anderson62ea1b72010-09-09 19:07:31 +0000596 // Don't allow an estimate of size zero. This would allows unrolling of loops
597 // with huge iteration counts, which is a compile time problem even if it's
Hal Finkel38dd5902015-01-10 00:30:55 +0000598 // not a problem for code quality. Also, the code using this size may assume
599 // that each loop has at least three instructions (likely a conditional
600 // branch, a comparison feeding that branch, and some kind of loop increment
601 // feeding that comparison instruction).
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000602 LoopSize = std::max(LoopSize, BEInsns + 1);
Andrew Trick279e7a62011-07-23 00:29:16 +0000603
Owen Anderson62ea1b72010-09-09 19:07:31 +0000604 return LoopSize;
Chris Lattner946b2552004-04-18 05:20:17 +0000605}
606
Mark Heffernane6b4ba12014-07-23 17:31:37 +0000607// Returns the loop hint metadata node with the given name (for example,
608// "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
609// returned.
Jingyue Wu49a766e2015-02-02 20:41:11 +0000610static MDNode *GetUnrollMetadataForLoop(const Loop *L, StringRef Name) {
611 if (MDNode *LoopID = L->getLoopID())
612 return GetUnrollMetadata(LoopID, Name);
613 return nullptr;
Eli Benderskyff903242014-06-16 23:53:02 +0000614}
615
Mark Heffernane6b4ba12014-07-23 17:31:37 +0000616// Returns true if the loop has an unroll(full) pragma.
617static bool HasUnrollFullPragma(const Loop *L) {
Jingyue Wu0220df02015-02-01 02:27:45 +0000618 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
Eli Benderskyff903242014-06-16 23:53:02 +0000619}
620
Mark Heffernan89391542015-08-10 17:28:08 +0000621// Returns true if the loop has an unroll(enable) pragma. This metadata is used
622// for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
623static bool HasUnrollEnablePragma(const Loop *L) {
624 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
625}
626
Eli Benderskyff903242014-06-16 23:53:02 +0000627// Returns true if the loop has an unroll(disable) pragma.
628static bool HasUnrollDisablePragma(const Loop *L) {
Jingyue Wu0220df02015-02-01 02:27:45 +0000629 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.disable");
Eli Benderskyff903242014-06-16 23:53:02 +0000630}
631
Kevin Qin715b01e2015-03-09 06:14:18 +0000632// Returns true if the loop has an runtime unroll(disable) pragma.
633static bool HasRuntimeUnrollDisablePragma(const Loop *L) {
634 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
635}
636
Eli Benderskyff903242014-06-16 23:53:02 +0000637// If loop has an unroll_count pragma return the (necessarily
638// positive) value from the pragma. Otherwise return 0.
639static unsigned UnrollCountPragmaValue(const Loop *L) {
Jingyue Wu49a766e2015-02-02 20:41:11 +0000640 MDNode *MD = GetUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
Mark Heffernane6b4ba12014-07-23 17:31:37 +0000641 if (MD) {
642 assert(MD->getNumOperands() == 2 &&
643 "Unroll count hint metadata should have two operands.");
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000644 unsigned Count =
645 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
Eli Benderskyff903242014-06-16 23:53:02 +0000646 assert(Count >= 1 && "Unroll count must be positive.");
647 return Count;
648 }
649 return 0;
650}
651
Mark Heffernan053a6862014-07-18 21:04:33 +0000652// Remove existing unroll metadata and add unroll disable metadata to
653// indicate the loop has already been unrolled. This prevents a loop
654// from being unrolled more than is directed by a pragma if the loop
655// unrolling pass is run more than once (which it generally is).
656static void SetLoopAlreadyUnrolled(Loop *L) {
657 MDNode *LoopID = L->getLoopID();
Mark Heffernan053a6862014-07-18 21:04:33 +0000658 // First remove any existing loop unrolling metadata.
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000659 SmallVector<Metadata *, 4> MDs;
Mark Heffernan053a6862014-07-18 21:04:33 +0000660 // Reserve first location for self reference to the LoopID metadata node.
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000661 MDs.push_back(nullptr);
Evgeny Stupachenko3e2f3892016-06-08 20:21:24 +0000662
663 if (LoopID) {
664 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
665 bool IsUnrollMetadata = false;
666 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
667 if (MD) {
668 const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
669 IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
670 }
671 if (!IsUnrollMetadata)
672 MDs.push_back(LoopID->getOperand(i));
Mark Heffernan053a6862014-07-18 21:04:33 +0000673 }
Mark Heffernan053a6862014-07-18 21:04:33 +0000674 }
675
676 // Add unroll(disable) metadata to disable future unrolling.
677 LLVMContext &Context = L->getHeader()->getContext();
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000678 SmallVector<Metadata *, 1> DisableOperands;
Mark Heffernane6b4ba12014-07-23 17:31:37 +0000679 DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
Mark Heffernanf3764da2014-07-18 21:29:41 +0000680 MDNode *DisableNode = MDNode::get(Context, DisableOperands);
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000681 MDs.push_back(DisableNode);
Mark Heffernan053a6862014-07-18 21:04:33 +0000682
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000683 MDNode *NewLoopID = MDNode::get(Context, MDs);
Mark Heffernan053a6862014-07-18 21:04:33 +0000684 // Set operand 0 to refer to the loop id itself.
685 NewLoopID->replaceOperandWith(0, NewLoopID);
686 L->setLoopID(NewLoopID);
Mark Heffernan053a6862014-07-18 21:04:33 +0000687}
688
Dehao Chencc763442016-12-30 00:50:28 +0000689// Computes the boosting factor for complete unrolling.
690// If fully unrolling the loop would save a lot of RolledDynamicCost, it would
691// be beneficial to fully unroll the loop even if unrolledcost is large. We
692// use (RolledDynamicCost / UnrolledCost) to model the unroll benefits to adjust
693// the unroll threshold.
694static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost,
695 unsigned MaxPercentThresholdBoost) {
696 if (Cost.RolledDynamicCost >= UINT_MAX / 100)
697 return 100;
698 else if (Cost.UnrolledCost != 0)
699 // The boosting factor is RolledDynamicCost / UnrolledCost
700 return std::min(100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
701 MaxPercentThresholdBoost);
702 else
703 return MaxPercentThresholdBoost;
Michael Zolotukhin8c681712015-05-12 17:20:03 +0000704}
705
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000706// Returns loop size estimation for unrolled loop.
707static uint64_t getUnrolledLoopSize(
708 unsigned LoopSize,
709 TargetTransformInfo::UnrollingPreferences &UP) {
710 assert(LoopSize >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
711 return (uint64_t)(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
712}
713
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000714// Returns true if unroll count was set explicitly.
715// Calculates unroll count and writes it to UP.Count.
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000716static bool computeUnrollCount(
717 Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
Geoff Berry66d9bdb2017-06-28 15:53:17 +0000718 ScalarEvolution &SE, OptimizationRemarkEmitter *ORE, unsigned &TripCount,
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000719 unsigned MaxTripCount, unsigned &TripMultiple, unsigned LoopSize,
720 TargetTransformInfo::UnrollingPreferences &UP, bool &UseUpperBound) {
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000721 // Check for explicit Count.
722 // 1st priority is unroll count set by "unroll-count" option.
723 bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
724 if (UserUnrollCount) {
725 UP.Count = UnrollCount;
726 UP.AllowExpensiveTripCount = true;
727 UP.Force = true;
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000728 if (UP.AllowRemainder && getUnrolledLoopSize(LoopSize, UP) < UP.Threshold)
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000729 return true;
730 }
731
732 // 2nd priority is unroll count set by pragma.
733 unsigned PragmaCount = UnrollCountPragmaValue(L);
734 if (PragmaCount > 0) {
735 UP.Count = PragmaCount;
736 UP.Runtime = true;
737 UP.AllowExpensiveTripCount = true;
738 UP.Force = true;
739 if (UP.AllowRemainder &&
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000740 getUnrolledLoopSize(LoopSize, UP) < PragmaUnrollThreshold)
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000741 return true;
742 }
743 bool PragmaFullUnroll = HasUnrollFullPragma(L);
744 if (PragmaFullUnroll && TripCount != 0) {
745 UP.Count = TripCount;
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000746 if (getUnrolledLoopSize(LoopSize, UP) < PragmaUnrollThreshold)
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000747 return false;
748 }
749
750 bool PragmaEnableUnroll = HasUnrollEnablePragma(L);
751 bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
752 PragmaEnableUnroll || UserUnrollCount;
753
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000754 if (ExplicitUnroll && TripCount != 0) {
755 // If the loop has an unrolling pragma, we want to be more aggressive with
756 // unrolling limits. Set thresholds to at least the PragmaThreshold value
757 // which is larger than the default limits.
758 UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
759 UP.PartialThreshold =
760 std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
761 }
762
763 // 3rd priority is full unroll count.
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000764 // Full unroll makes sense only when TripCount or its upper bound could be
765 // statically calculated.
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000766 // Also we need to check if we exceed FullUnrollMaxCount.
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000767 // If using the upper bound to unroll, TripMultiple should be set to 1 because
768 // we do not know when loop may exit.
769 // MaxTripCount and ExactTripCount cannot both be non zero since we only
770 // compute the former when the latter is zero.
771 unsigned ExactTripCount = TripCount;
772 assert((ExactTripCount == 0 || MaxTripCount == 0) &&
773 "ExtractTripCound and MaxTripCount cannot both be non zero.");
774 unsigned FullUnrollTripCount = ExactTripCount ? ExactTripCount : MaxTripCount;
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000775 UP.Count = FullUnrollTripCount;
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000776 if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000777 // When computing the unrolled size, note that BEInsns are not replicated
778 // like the rest of the loop body.
Dehao Chencc763442016-12-30 00:50:28 +0000779 if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000780 UseUpperBound = (MaxTripCount == FullUnrollTripCount);
781 TripCount = FullUnrollTripCount;
782 TripMultiple = UP.UpperBound ? 1 : TripMultiple;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000783 return ExplicitUnroll;
784 } else {
785 // The loop isn't that small, but we still can fully unroll it if that
786 // helps to remove a significant number of instructions.
787 // To check that, run additional analysis on the loop.
788 if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
Geoff Berry66d9bdb2017-06-28 15:53:17 +0000789 L, FullUnrollTripCount, DT, SE, TTI,
Dehao Chencc763442016-12-30 00:50:28 +0000790 UP.Threshold * UP.MaxPercentThresholdBoost / 100)) {
791 unsigned Boost =
792 getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
793 if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000794 UseUpperBound = (MaxTripCount == FullUnrollTripCount);
795 TripCount = FullUnrollTripCount;
796 TripMultiple = UP.UpperBound ? 1 : TripMultiple;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000797 return ExplicitUnroll;
798 }
Dehao Chencc763442016-12-30 00:50:28 +0000799 }
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000800 }
801 }
802
Sanjoy Daseed71b92017-03-03 18:19:10 +0000803 // 4th priority is loop peeling
804 computePeelCount(L, LoopSize, UP, TripCount);
805 if (UP.PeelCount) {
806 UP.Runtime = false;
807 UP.Count = 1;
808 return ExplicitUnroll;
809 }
810
811 // 5th priority is partial unrolling.
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000812 // Try partial unroll only when TripCount could be staticaly calculated.
813 if (TripCount) {
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000814 UP.Partial |= ExplicitUnroll;
815 if (!UP.Partial) {
816 DEBUG(dbgs() << " will not try to unroll partially because "
817 << "-unroll-allow-partial not given\n");
818 UP.Count = 0;
819 return false;
820 }
Haicheng Wu430b3e42016-10-27 18:40:02 +0000821 if (UP.Count == 0)
822 UP.Count = TripCount;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000823 if (UP.PartialThreshold != NoThreshold) {
824 // Reduce unroll count to be modulo of TripCount for partial unrolling.
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000825 if (getUnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
826 UP.Count =
827 (std::max(UP.PartialThreshold, UP.BEInsns + 1) - UP.BEInsns) /
828 (LoopSize - UP.BEInsns);
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000829 if (UP.Count > UP.MaxCount)
830 UP.Count = UP.MaxCount;
831 while (UP.Count != 0 && TripCount % UP.Count != 0)
832 UP.Count--;
833 if (UP.AllowRemainder && UP.Count <= 1) {
834 // If there is no Count that is modulo of TripCount, set Count to
835 // largest power-of-two factor that satisfies the threshold limit.
836 // As we'll create fixup loop, do the type of unrolling only if
837 // remainder loop is allowed.
Jonas Paulsson58c5a7f2016-09-28 09:41:38 +0000838 UP.Count = UP.DefaultUnrollRuntimeCount;
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000839 while (UP.Count != 0 &&
840 getUnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000841 UP.Count >>= 1;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000842 }
843 if (UP.Count < 2) {
844 if (PragmaEnableUnroll)
Adam Nemetf57cc622016-09-30 03:44:16 +0000845 ORE->emit(
846 OptimizationRemarkMissed(DEBUG_TYPE, "UnrollAsDirectedTooLarge",
847 L->getStartLoc(), L->getHeader())
848 << "Unable to unroll loop as directed by unroll(enable) pragma "
849 "because unrolled size is too large.");
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000850 UP.Count = 0;
851 }
852 } else {
853 UP.Count = TripCount;
854 }
Geoff Berryb0573542017-06-28 17:01:15 +0000855 if (UP.Count > UP.MaxCount)
856 UP.Count = UP.MaxCount;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000857 if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
858 UP.Count != TripCount)
Adam Nemetf57cc622016-09-30 03:44:16 +0000859 ORE->emit(
860 OptimizationRemarkMissed(DEBUG_TYPE, "FullUnrollAsDirectedTooLarge",
861 L->getStartLoc(), L->getHeader())
862 << "Unable to fully unroll loop as directed by unroll pragma because "
863 "unrolled size is too large.");
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000864 return ExplicitUnroll;
865 }
866 assert(TripCount == 0 &&
867 "All cases when TripCount is constant should be covered here.");
868 if (PragmaFullUnroll)
Adam Nemetf57cc622016-09-30 03:44:16 +0000869 ORE->emit(
870 OptimizationRemarkMissed(DEBUG_TYPE,
871 "CantFullUnrollAsDirectedRuntimeTripCount",
872 L->getStartLoc(), L->getHeader())
873 << "Unable to fully unroll loop as directed by unroll(full) pragma "
874 "because loop has a runtime trip count.");
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000875
Michael Kupersteinb151a642016-11-30 21:13:57 +0000876 // 6th priority is runtime unrolling.
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000877 // Don't unroll a runtime trip count loop when it is disabled.
878 if (HasRuntimeUnrollDisablePragma(L)) {
879 UP.Count = 0;
880 return false;
881 }
Michael Kupersteinb151a642016-11-30 21:13:57 +0000882
883 // Check if the runtime trip count is too small when profile is available.
884 if (L->getHeader()->getParent()->getEntryCount()) {
885 if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
886 if (*ProfileTripCount < FlatLoopTripCountThreshold)
887 return false;
888 else
889 UP.AllowExpensiveTripCount = true;
890 }
891 }
892
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000893 // Reduce count based on the type of unrolling and the threshold values.
894 UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
895 if (!UP.Runtime) {
896 DEBUG(dbgs() << " will not try to unroll loop with runtime trip count "
897 << "-unroll-runtime not given\n");
898 UP.Count = 0;
899 return false;
900 }
901 if (UP.Count == 0)
Jonas Paulsson58c5a7f2016-09-28 09:41:38 +0000902 UP.Count = UP.DefaultUnrollRuntimeCount;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000903
904 // Reduce unroll count to be the largest power-of-two factor of
905 // the original count which satisfies the threshold limit.
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000906 while (UP.Count != 0 &&
907 getUnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000908 UP.Count >>= 1;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000909
Evgeny Stupachenkob7875222016-05-28 00:14:58 +0000910#ifndef NDEBUG
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000911 unsigned OrigCount = UP.Count;
Evgeny Stupachenkob7875222016-05-28 00:14:58 +0000912#endif
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000913
914 if (!UP.AllowRemainder && UP.Count != 0 && (TripMultiple % UP.Count) != 0) {
915 while (UP.Count != 0 && TripMultiple % UP.Count != 0)
916 UP.Count >>= 1;
917 DEBUG(dbgs() << "Remainder loop is restricted (that could architecture "
918 "specific or because the loop contains a convergent "
919 "instruction), so unroll count must divide the trip "
920 "multiple, "
921 << TripMultiple << ". Reducing unroll count from "
922 << OrigCount << " to " << UP.Count << ".\n");
Adam Nemetf57cc622016-09-30 03:44:16 +0000923 using namespace ore;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000924 if (PragmaCount > 0 && !UP.AllowRemainder)
Adam Nemetf57cc622016-09-30 03:44:16 +0000925 ORE->emit(
926 OptimizationRemarkMissed(DEBUG_TYPE,
927 "DifferentUnrollCountFromDirected",
928 L->getStartLoc(), L->getHeader())
929 << "Unable to unroll loop the number of times directed by "
930 "unroll_count pragma because remainder loop is restricted "
931 "(that could architecture specific or because the loop "
932 "contains a convergent instruction) and so must have an unroll "
933 "count that divides the loop trip multiple of "
934 << NV("TripMultiple", TripMultiple) << ". Unrolling instead "
935 << NV("UnrollCount", UP.Count) << " time(s).");
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000936 }
937
938 if (UP.Count > UP.MaxCount)
939 UP.Count = UP.MaxCount;
940 DEBUG(dbgs() << " partially unrolling with count: " << UP.Count << "\n");
941 if (UP.Count < 2)
942 UP.Count = 0;
943 return ExplicitUnroll;
944}
945
Sanjoy Das4f3ebd52017-09-27 21:45:22 +0000946static LoopUnrollResult tryToUnrollLoop(
Teresa Johnson9a18a6f2017-08-03 17:52:38 +0000947 Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
948 const TargetTransformInfo &TTI, AssumptionCache &AC,
949 OptimizationRemarkEmitter &ORE, bool PreserveLCSSA, int OptLevel,
950 Optional<unsigned> ProvidedCount, Optional<unsigned> ProvidedThreshold,
951 Optional<bool> ProvidedAllowPartial, Optional<bool> ProvidedRuntime,
952 Optional<bool> ProvidedUpperBound, Optional<bool> ProvidedAllowPeeling) {
Evgeny Stupachenkob7875222016-05-28 00:14:58 +0000953 DEBUG(dbgs() << "Loop Unroll: F[" << L->getHeader()->getParent()->getName()
954 << "] Loop %" << L->getHeader()->getName() << "\n");
Sanjoy Das4f3ebd52017-09-27 21:45:22 +0000955 if (HasUnrollDisablePragma(L))
956 return LoopUnrollResult::Unmodified;
Haicheng Wu731b04c2016-11-23 19:39:26 +0000957 if (!L->isLoopSimplifyForm()) {
958 DEBUG(
959 dbgs() << " Not unrolling loop which is not in loop-simplify form.\n");
Sanjoy Das4f3ebd52017-09-27 21:45:22 +0000960 return LoopUnrollResult::Unmodified;
Eli Benderskyff903242014-06-16 23:53:02 +0000961 }
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000962
963 unsigned NumInlineCandidates;
964 bool NotDuplicatable;
965 bool Convergent;
Evgeny Stupachenkoc2698cd2016-11-09 19:56:39 +0000966 TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
Geoff Berry66d9bdb2017-06-28 15:53:17 +0000967 L, SE, TTI, OptLevel, ProvidedThreshold, ProvidedCount,
Teresa Johnson9a18a6f2017-08-03 17:52:38 +0000968 ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
969 ProvidedAllowPeeling);
Haicheng Wu731b04c2016-11-23 19:39:26 +0000970 // Exit early if unrolling is disabled.
971 if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0))
Sanjoy Das4f3ebd52017-09-27 21:45:22 +0000972 return LoopUnrollResult::Unmodified;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000973 unsigned LoopSize = ApproximateLoopSize(
Daniel Jasperaec2fa32016-12-19 08:22:17 +0000974 L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC, UP.BEInsns);
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000975 DEBUG(dbgs() << " Loop Size = " << LoopSize << "\n");
976 if (NotDuplicatable) {
977 DEBUG(dbgs() << " Not unrolling loop which contains non-duplicatable"
978 << " instructions.\n");
Sanjoy Das4f3ebd52017-09-27 21:45:22 +0000979 return LoopUnrollResult::Unmodified;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000980 }
981 if (NumInlineCandidates != 0) {
982 DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n");
Sanjoy Das4f3ebd52017-09-27 21:45:22 +0000983 return LoopUnrollResult::Unmodified;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +0000984 }
Andrew Trick279e7a62011-07-23 00:29:16 +0000985
Andrew Trick2b6860f2011-08-11 23:36:16 +0000986 // Find trip count and trip multiple if count is not available
987 unsigned TripCount = 0;
Haicheng Wu1ef17e92016-10-12 21:29:38 +0000988 unsigned MaxTripCount = 0;
Andrew Trick1cabe542011-07-23 00:33:05 +0000989 unsigned TripMultiple = 1;
Chandler Carruth6666c272014-10-11 00:12:11 +0000990 // If there are multiple exiting blocks but one of them is the latch, use the
991 // latch for the trip count estimation. Otherwise insist on a single exiting
992 // block for the trip count estimation.
993 BasicBlock *ExitingBlock = L->getLoopLatch();
994 if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
995 ExitingBlock = L->getExitingBlock();
996 if (ExitingBlock) {
Geoff Berry66d9bdb2017-06-28 15:53:17 +0000997 TripCount = SE.getSmallConstantTripCount(L, ExitingBlock);
998 TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
Andrew Trick2b6860f2011-08-11 23:36:16 +0000999 }
Hal Finkel8f2e7002013-09-11 19:25:43 +00001000
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +00001001 // If the loop contains a convergent operation, the prelude we'd add
1002 // to do the first few instructions before we hit the unrolled loop
1003 // is unsafe -- it adds a control-flow dependency to the convergent
1004 // operation. Therefore restrict remainder loop (try unrollig without).
1005 //
1006 // TODO: This is quite conservative. In practice, convergent_op()
1007 // is likely to be called unconditionally in the loop. In this
1008 // case, the program would be ill-formed (on most architectures)
1009 // unless n were the same on all threads in a thread group.
1010 // Assuming n is the same on all threads, any kind of unrolling is
1011 // safe. But currently llvm's notion of convergence isn't powerful
1012 // enough to express this.
1013 if (Convergent)
1014 UP.AllowRemainder = false;
Eli Benderskydc6de2c2014-06-12 18:05:39 +00001015
John Brawn84b21832016-10-21 11:08:48 +00001016 // Try to find the trip count upper bound if we cannot find the exact trip
1017 // count.
1018 bool MaxOrZero = false;
1019 if (!TripCount) {
Geoff Berry66d9bdb2017-06-28 15:53:17 +00001020 MaxTripCount = SE.getSmallConstantMaxTripCount(L);
1021 MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
John Brawn84b21832016-10-21 11:08:48 +00001022 // We can unroll by the upper bound amount if it's generally allowed or if
1023 // we know that the loop is executed either the upper bound or zero times.
1024 // (MaxOrZero unrolling keeps only the first loop test, so the number of
1025 // loop tests remains the same compared to the non-unrolled version, whereas
1026 // the generic upper bound unrolling keeps all but the last loop test so the
1027 // number of loop tests goes up which may end up being worse on targets with
1028 // constriained branch predictor resources so is controlled by an option.)
1029 // In addition we only unroll small upper bounds.
1030 if (!(UP.UpperBound || MaxOrZero) || MaxTripCount > UnrollMaxUpperBound) {
1031 MaxTripCount = 0;
Haicheng Wu1ef17e92016-10-12 21:29:38 +00001032 }
1033 }
1034
1035 // computeUnrollCount() decides whether it is beneficial to use upper bound to
1036 // fully unroll the loop.
1037 bool UseUpperBound = false;
1038 bool IsCountSetExplicitly =
1039 computeUnrollCount(L, TTI, DT, LI, SE, &ORE, TripCount, MaxTripCount,
1040 TripMultiple, LoopSize, UP, UseUpperBound);
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +00001041 if (!UP.Count)
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001042 return LoopUnrollResult::Unmodified;
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +00001043 // Unroll factor (Count) must be less or equal to TripCount.
1044 if (TripCount && UP.Count > TripCount)
1045 UP.Count = TripCount;
Dan Gohman2980d9d2007-05-11 20:53:41 +00001046
Dan Gohman3dc2d922008-05-14 00:24:14 +00001047 // Unroll the loop.
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001048 LoopUnrollResult UnrollResult = UnrollLoop(
Sanjoy Das09613b12017-09-20 02:31:57 +00001049 L, UP.Count, TripCount, UP.Force, UP.Runtime, UP.AllowExpensiveTripCount,
1050 UseUpperBound, MaxOrZero, TripMultiple, UP.PeelCount, UP.UnrollRemainder,
1051 LI, &SE, &DT, &AC, &ORE, PreserveLCSSA);
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001052 if (UnrollResult == LoopUnrollResult::Unmodified)
1053 return LoopUnrollResult::Unmodified;
Dan Gohman2980d9d2007-05-11 20:53:41 +00001054
Evgeny Stupachenkoea2aef42016-05-27 23:15:06 +00001055 // If loop has an unroll count pragma or unrolled by explicitly set count
1056 // mark loop as unrolled to prevent unrolling beyond that requested.
Michael Kupersteinb151a642016-11-30 21:13:57 +00001057 // If the loop was peeled, we already "used up" the profile information
1058 // we had, so we don't want to unroll or peel again.
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001059 if (UnrollResult != LoopUnrollResult::FullyUnrolled &&
Sanjoy Das09613b12017-09-20 02:31:57 +00001060 (IsCountSetExplicitly || UP.PeelCount))
David L Kreitzer8d441eb2016-03-25 14:24:52 +00001061 SetLoopAlreadyUnrolled(L);
Michael Kupersteinb151a642016-11-30 21:13:57 +00001062
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001063 return UnrollResult;
Chris Lattner946b2552004-04-18 05:20:17 +00001064}
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001065
1066namespace {
1067class LoopUnroll : public LoopPass {
1068public:
1069 static char ID; // Pass ID, replacement for typeid
Dehao Chen7d230322017-02-18 03:46:51 +00001070 LoopUnroll(int OptLevel = 2, Optional<unsigned> Threshold = None,
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001071 Optional<unsigned> Count = None,
Haicheng Wu1ef17e92016-10-12 21:29:38 +00001072 Optional<bool> AllowPartial = None, Optional<bool> Runtime = None,
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001073 Optional<bool> UpperBound = None,
1074 Optional<bool> AllowPeeling = None)
Dehao Chen7d230322017-02-18 03:46:51 +00001075 : LoopPass(ID), OptLevel(OptLevel), ProvidedCount(std::move(Count)),
Benjamin Kramer82de7d32016-05-27 14:27:24 +00001076 ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001077 ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound),
1078 ProvidedAllowPeeling(AllowPeeling) {
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001079 initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
1080 }
1081
Dehao Chen7d230322017-02-18 03:46:51 +00001082 int OptLevel;
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001083 Optional<unsigned> ProvidedCount;
1084 Optional<unsigned> ProvidedThreshold;
1085 Optional<bool> ProvidedAllowPartial;
1086 Optional<bool> ProvidedRuntime;
Haicheng Wu1ef17e92016-10-12 21:29:38 +00001087 Optional<bool> ProvidedUpperBound;
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001088 Optional<bool> ProvidedAllowPeeling;
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001089
Sanjoy Dasdef17292017-09-28 02:45:42 +00001090 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
Andrew Kayloraa641a52016-04-22 22:06:11 +00001091 if (skipLoop(L))
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001092 return false;
1093
1094 Function &F = *L->getHeader()->getParent();
1095
1096 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1097 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
Geoff Berry66d9bdb2017-06-28 15:53:17 +00001098 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001099 const TargetTransformInfo &TTI =
1100 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
Daniel Jasperaec2fa32016-12-19 08:22:17 +00001101 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
Adam Nemet4f155b62016-08-26 15:58:34 +00001102 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
1103 // pass. Function analyses need to be preserved across loop transformations
1104 // but ORE cannot be preserved (see comment before the pass definition).
1105 OptimizationRemarkEmitter ORE(&F);
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001106 bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1107
Sanjoy Dasdef17292017-09-28 02:45:42 +00001108 LoopUnrollResult Result = tryToUnrollLoop(
1109 L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel, ProvidedCount,
1110 ProvidedThreshold, ProvidedAllowPartial, ProvidedRuntime,
1111 ProvidedUpperBound, ProvidedAllowPeeling);
1112
1113 if (Result == LoopUnrollResult::FullyUnrolled)
1114 LPM.markLoopAsDeleted(*L);
1115
1116 return Result != LoopUnrollResult::Unmodified;
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001117 }
1118
1119 /// This transformation requires natural loop information & requires that
1120 /// loop preheaders be inserted into the CFG...
1121 ///
1122 void getAnalysisUsage(AnalysisUsage &AU) const override {
Daniel Jasperaec2fa32016-12-19 08:22:17 +00001123 AU.addRequired<AssumptionCacheTracker>();
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001124 AU.addRequired<TargetTransformInfoWrapperPass>();
Chandler Carruth31088a92016-02-19 10:45:18 +00001125 // FIXME: Loop passes are required to preserve domtree, and for now we just
1126 // recreate dom info if anything gets unrolled.
1127 getLoopAnalysisUsage(AU);
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001128 }
1129};
1130}
1131
1132char LoopUnroll::ID = 0;
1133INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
Daniel Jasperaec2fa32016-12-19 08:22:17 +00001134INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
Chandler Carruth31088a92016-02-19 10:45:18 +00001135INITIALIZE_PASS_DEPENDENCY(LoopPass)
1136INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001137INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1138
Dehao Chen7d230322017-02-18 03:46:51 +00001139Pass *llvm::createLoopUnrollPass(int OptLevel, int Threshold, int Count,
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001140 int AllowPartial, int Runtime, int UpperBound,
1141 int AllowPeeling) {
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001142 // TODO: It would make more sense for this function to take the optionals
1143 // directly, but that's dangerous since it would silently break out of tree
1144 // callers.
Dehao Chen7d230322017-02-18 03:46:51 +00001145 return new LoopUnroll(
1146 OptLevel, Threshold == -1 ? None : Optional<unsigned>(Threshold),
1147 Count == -1 ? None : Optional<unsigned>(Count),
1148 AllowPartial == -1 ? None : Optional<bool>(AllowPartial),
1149 Runtime == -1 ? None : Optional<bool>(Runtime),
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001150 UpperBound == -1 ? None : Optional<bool>(UpperBound),
1151 AllowPeeling == -1 ? None : Optional<bool>(AllowPeeling));
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001152}
1153
Dehao Chen7d230322017-02-18 03:46:51 +00001154Pass *llvm::createSimpleLoopUnrollPass(int OptLevel) {
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001155 return llvm::createLoopUnrollPass(OptLevel, -1, -1, 0, 0, 0, 0);
Justin Bognerb8d82ab2016-01-12 05:21:37 +00001156}
Sean Silvae3c18a52016-07-19 23:54:23 +00001157
Teresa Johnsonecd90132017-08-02 20:35:29 +00001158PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
1159 LoopStandardAnalysisResults &AR,
1160 LPMUpdater &Updater) {
Sean Silvae3c18a52016-07-19 23:54:23 +00001161 const auto &FAM =
Chandler Carruth410eaeb2017-01-11 06:23:21 +00001162 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
Sean Silvae3c18a52016-07-19 23:54:23 +00001163 Function *F = L.getHeader()->getParent();
1164
Adam Nemet12937c32016-07-29 19:29:47 +00001165 auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
Chandler Carruth410eaeb2017-01-11 06:23:21 +00001166 // FIXME: This should probably be optional rather than required.
Adam Nemet12937c32016-07-29 19:29:47 +00001167 if (!ORE)
Teresa Johnsonecd90132017-08-02 20:35:29 +00001168 report_fatal_error(
1169 "LoopFullUnrollPass: OptimizationRemarkEmitterAnalysis not "
1170 "cached at a higher level");
Sean Silvae3c18a52016-07-19 23:54:23 +00001171
Chandler Carruthce40fa12017-01-25 02:49:01 +00001172 // Keep track of the previous loop structure so we can identify new loops
1173 // created by unrolling.
1174 Loop *ParentL = L.getParentLoop();
1175 SmallPtrSet<Loop *, 4> OldLoops;
1176 if (ParentL)
1177 OldLoops.insert(ParentL->begin(), ParentL->end());
1178 else
1179 OldLoops.insert(AR.LI.begin(), AR.LI.end());
1180
Sanjoy Dasdef17292017-09-28 02:45:42 +00001181 std::string LoopName = L.getName();
1182
Teresa Johnsonecd90132017-08-02 20:35:29 +00001183 bool Changed =
1184 tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, *ORE,
1185 /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None,
1186 /*Threshold*/ None, /*AllowPartial*/ false,
Teresa Johnson9a18a6f2017-08-03 17:52:38 +00001187 /*Runtime*/ false, /*UpperBound*/ false,
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001188 /*AllowPeeling*/ false) != LoopUnrollResult::Unmodified;
Sean Silvae3c18a52016-07-19 23:54:23 +00001189 if (!Changed)
1190 return PreservedAnalyses::all();
Chandler Carruthca68a3e2017-01-15 06:32:49 +00001191
Chandler Carruthce40fa12017-01-25 02:49:01 +00001192 // The parent must not be damaged by unrolling!
1193#ifndef NDEBUG
1194 if (ParentL)
1195 ParentL->verifyLoop();
1196#endif
1197
1198 // Unrolling can do several things to introduce new loops into a loop nest:
Chandler Carruthce40fa12017-01-25 02:49:01 +00001199 // - Full unrolling clones child loops within the current loop but then
1200 // removes the current loop making all of the children appear to be new
1201 // sibling loops.
Chandler Carruthce40fa12017-01-25 02:49:01 +00001202 //
Teresa Johnsonecd90132017-08-02 20:35:29 +00001203 // When a new loop appears as a sibling loop after fully unrolling,
1204 // its nesting structure has fundamentally changed and we want to revisit
1205 // it to reflect that.
Chandler Carruthce40fa12017-01-25 02:49:01 +00001206 //
1207 // When unrolling has removed the current loop, we need to tell the
1208 // infrastructure that it is gone.
1209 //
1210 // Finally, we support a debugging/testing mode where we revisit child loops
1211 // as well. These are not expected to require further optimizations as either
1212 // they or the loop they were cloned from have been directly visited already.
1213 // But the debugging mode allows us to check this assumption.
1214 bool IsCurrentLoopValid = false;
1215 SmallVector<Loop *, 4> SibLoops;
1216 if (ParentL)
1217 SibLoops.append(ParentL->begin(), ParentL->end());
1218 else
1219 SibLoops.append(AR.LI.begin(), AR.LI.end());
1220 erase_if(SibLoops, [&](Loop *SibLoop) {
1221 if (SibLoop == &L) {
1222 IsCurrentLoopValid = true;
1223 return true;
1224 }
1225
1226 // Otherwise erase the loop from the list if it was in the old loops.
1227 return OldLoops.count(SibLoop) != 0;
1228 });
1229 Updater.addSiblingLoops(SibLoops);
1230
1231 if (!IsCurrentLoopValid) {
Sanjoy Dasdef17292017-09-28 02:45:42 +00001232 Updater.markLoopAsDeleted(L, LoopName);
Chandler Carruthce40fa12017-01-25 02:49:01 +00001233 } else {
1234 // We can only walk child loops if the current loop remained valid.
1235 if (UnrollRevisitChildLoops) {
Teresa Johnsonecd90132017-08-02 20:35:29 +00001236 // Walk *all* of the child loops.
Chandler Carruthce40fa12017-01-25 02:49:01 +00001237 SmallVector<Loop *, 4> ChildLoops(L.begin(), L.end());
1238 Updater.addChildLoops(ChildLoops);
1239 }
1240 }
1241
Sean Silvae3c18a52016-07-19 23:54:23 +00001242 return getLoopPassPreservedAnalyses();
1243}
Teresa Johnsonecd90132017-08-02 20:35:29 +00001244
1245template <typename RangeT>
1246static SmallVector<Loop *, 8> appendLoopsToWorklist(RangeT &&Loops) {
1247 SmallVector<Loop *, 8> Worklist;
1248 // We use an internal worklist to build up the preorder traversal without
1249 // recursion.
1250 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
1251
1252 for (Loop *RootL : Loops) {
1253 assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
1254 assert(PreOrderWorklist.empty() &&
1255 "Must start with an empty preorder walk worklist.");
1256 PreOrderWorklist.push_back(RootL);
1257 do {
1258 Loop *L = PreOrderWorklist.pop_back_val();
1259 PreOrderWorklist.append(L->begin(), L->end());
1260 PreOrderLoops.push_back(L);
1261 } while (!PreOrderWorklist.empty());
1262
1263 Worklist.append(PreOrderLoops.begin(), PreOrderLoops.end());
1264 PreOrderLoops.clear();
1265 }
1266 return Worklist;
1267}
1268
1269PreservedAnalyses LoopUnrollPass::run(Function &F,
1270 FunctionAnalysisManager &AM) {
1271 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1272 auto &LI = AM.getResult<LoopAnalysis>(F);
1273 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1274 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1275 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1276 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
1277
Chandler Carruth7c888dc2017-08-08 02:24:20 +00001278 LoopAnalysisManager *LAM = nullptr;
1279 if (auto *LAMProxy = AM.getCachedResult<LoopAnalysisManagerFunctionProxy>(F))
1280 LAM = &LAMProxy->getManager();
1281
Teresa Johnson8482e562017-08-03 23:42:58 +00001282 const ModuleAnalysisManager &MAM =
1283 AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
1284 ProfileSummaryInfo *PSI =
1285 MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
1286
Teresa Johnsonecd90132017-08-02 20:35:29 +00001287 bool Changed = false;
1288
1289 // The unroller requires loops to be in simplified form, and also needs LCSSA.
1290 // Since simplification may add new inner loops, it has to run before the
1291 // legality and profitability checks. This means running the loop unroller
1292 // will simplify all loops, regardless of whether anything end up being
1293 // unrolled.
1294 for (auto &L : LI) {
1295 Changed |= simplifyLoop(L, &DT, &LI, &SE, &AC, false /* PreserveLCSSA */);
1296 Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
1297 }
1298
1299 SmallVector<Loop *, 8> Worklist = appendLoopsToWorklist(LI);
1300
1301 while (!Worklist.empty()) {
1302 // Because the LoopInfo stores the loops in RPO, we walk the worklist
1303 // from back to front so that we work forward across the CFG, which
1304 // for unrolling is only needed to get optimization remarks emitted in
1305 // a forward order.
1306 Loop &L = *Worklist.pop_back_val();
Benjamin Kramerc965b302017-09-28 14:47:39 +00001307#ifndef NDEBUG
1308 Loop *ParentL = L.getParentLoop();
1309#endif
Teresa Johnsonecd90132017-08-02 20:35:29 +00001310
1311 // The API here is quite complex to call, but there are only two interesting
1312 // states we support: partial and full (or "simple") unrolling. However, to
1313 // enable these things we actually pass "None" in for the optional to avoid
1314 // providing an explicit choice.
Teresa Johnson8482e562017-08-03 23:42:58 +00001315 Optional<bool> AllowPartialParam, RuntimeParam, UpperBoundParam,
1316 AllowPeeling;
1317 // Check if the profile summary indicates that the profiled application
1318 // has a huge working set size, in which case we disable peeling to avoid
1319 // bloating it further.
1320 if (PSI && PSI->hasHugeWorkingSetSize())
1321 AllowPeeling = false;
Sanjoy Dasdef17292017-09-28 02:45:42 +00001322 std::string LoopName = L.getName();
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001323 LoopUnrollResult Result =
Teresa Johnson8482e562017-08-03 23:42:58 +00001324 tryToUnrollLoop(&L, DT, &LI, SE, TTI, AC, ORE,
1325 /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None,
1326 /*Threshold*/ None, AllowPartialParam, RuntimeParam,
1327 UpperBoundParam, AllowPeeling);
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001328 Changed |= Result != LoopUnrollResult::Unmodified;
Teresa Johnsonecd90132017-08-02 20:35:29 +00001329
1330 // The parent must not be damaged by unrolling!
1331#ifndef NDEBUG
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001332 if (Result != LoopUnrollResult::Unmodified && ParentL)
Teresa Johnsonecd90132017-08-02 20:35:29 +00001333 ParentL->verifyLoop();
1334#endif
Chandler Carruth7c888dc2017-08-08 02:24:20 +00001335
Sanjoy Das4f3ebd52017-09-27 21:45:22 +00001336 // Clear any cached analysis results for L if we removed it completely.
1337 if (LAM && Result == LoopUnrollResult::FullyUnrolled)
Sanjoy Dasdef17292017-09-28 02:45:42 +00001338 LAM->clear(L, LoopName);
Teresa Johnsonecd90132017-08-02 20:35:29 +00001339 }
1340
1341 if (!Changed)
1342 return PreservedAnalyses::all();
1343
1344 return getLoopPassPreservedAnalyses();
1345}