1 //===- LoopUnroll.cpp - Loop unroller pass --------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass implements a simple loop unroller. It works best when loops have
10 // been canonicalized by the -indvars pass, allowing it to determine the trip
11 // counts of loops easily.
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Transforms/Scalar/LoopUnrollPass.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/DenseMapInfo.h"
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/Analysis/AssumptionCache.h"
26 #include "llvm/Analysis/BlockFrequencyInfo.h"
27 #include "llvm/Analysis/CodeMetrics.h"
28 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
29 #include "llvm/Analysis/LoopAnalysisManager.h"
30 #include "llvm/Analysis/LoopInfo.h"
31 #include "llvm/Analysis/LoopPass.h"
32 #include "llvm/Analysis/LoopUnrollAnalyzer.h"
33 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
34 #include "llvm/Analysis/ProfileSummaryInfo.h"
35 #include "llvm/Analysis/ScalarEvolution.h"
36 #include "llvm/Analysis/TargetTransformInfo.h"
37 #include "llvm/IR/BasicBlock.h"
38 #include "llvm/IR/CFG.h"
39 #include "llvm/IR/Constant.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/DiagnosticInfo.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Metadata.h"
48 #include "llvm/IR/PassManager.h"
49 #include "llvm/InitializePasses.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/Casting.h"
52 #include "llvm/Support/CommandLine.h"
53 #include "llvm/Support/Debug.h"
54 #include "llvm/Support/ErrorHandling.h"
55 #include "llvm/Support/raw_ostream.h"
56 #include "llvm/Transforms/Scalar.h"
57 #include "llvm/Transforms/Scalar/LoopPassManager.h"
58 #include "llvm/Transforms/Utils.h"
59 #include "llvm/Transforms/Utils/LoopPeel.h"
60 #include "llvm/Transforms/Utils/LoopSimplify.h"
61 #include "llvm/Transforms/Utils/LoopUtils.h"
62 #include "llvm/Transforms/Utils/SizeOpts.h"
63 #include "llvm/Transforms/Utils/UnrollLoop.h"
64 #include <algorithm>
65 #include <cassert>
66 #include <cstdint>
67 #include <limits>
68 #include <string>
69 #include <tuple>
70 #include <utility>
71
72 using namespace llvm;
73
74 #define DEBUG_TYPE "loop-unroll"
75
76 cl::opt<bool> llvm::ForgetSCEVInLoopUnroll(
77 "forget-scev-loop-unroll", cl::init(false), cl::Hidden,
78 cl::desc("Forget everything in SCEV when doing LoopUnroll, instead of just"
79 " the current top-most loop. This is sometimes preferred to reduce"
80 " compile time."));
81
82 static cl::opt<unsigned>
83 UnrollThreshold("unroll-threshold", cl::Hidden,
84 cl::desc("The cost threshold for loop unrolling"));
85
86 static cl::opt<unsigned>
87 UnrollOptSizeThreshold(
88 "unroll-optsize-threshold", cl::init(0), cl::Hidden,
89 cl::desc("The cost threshold for loop unrolling when optimizing for "
90 "size"));
91
92 static cl::opt<unsigned> UnrollPartialThreshold(
93 "unroll-partial-threshold", cl::Hidden,
94 cl::desc("The cost threshold for partial loop unrolling"));
95
96 static cl::opt<unsigned> UnrollMaxPercentThresholdBoost(
97 "unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden,
98 cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied "
99 "to the threshold when aggressively unrolling a loop due to the "
100 "dynamic cost savings. If completely unrolling a loop will reduce "
101 "the total runtime from X to Y, we boost the loop unroll "
102 "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, "
103 "X/Y). This limit avoids excessive code bloat."));
104
105 static cl::opt<unsigned> UnrollMaxIterationsCountToAnalyze(
106 "unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden,
107 cl::desc("Don't allow loop unrolling to simulate more than this number of"
108 "iterations when checking full unroll profitability"));
109
110 static cl::opt<unsigned> UnrollCount(
111 "unroll-count", cl::Hidden,
112 cl::desc("Use this unroll count for all loops including those with "
113 "unroll_count pragma values, for testing purposes"));
114
115 static cl::opt<unsigned> UnrollMaxCount(
116 "unroll-max-count", cl::Hidden,
117 cl::desc("Set the max unroll count for partial and runtime unrolling, for"
118 "testing purposes"));
119
120 static cl::opt<unsigned> UnrollFullMaxCount(
121 "unroll-full-max-count", cl::Hidden,
122 cl::desc(
123 "Set the max unroll count for full unrolling, for testing purposes"));
124
125 static cl::opt<bool>
126 UnrollAllowPartial("unroll-allow-partial", cl::Hidden,
127 cl::desc("Allows loops to be partially unrolled until "
128 "-unroll-threshold loop size is reached."));
129
130 static cl::opt<bool> UnrollAllowRemainder(
131 "unroll-allow-remainder", cl::Hidden,
132 cl::desc("Allow generation of a loop remainder (extra iterations) "
133 "when unrolling a loop."));
134
135 static cl::opt<bool>
136 UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden,
137 cl::desc("Unroll loops with run-time trip counts"));
138
139 static cl::opt<unsigned> UnrollMaxUpperBound(
140 "unroll-max-upperbound", cl::init(8), cl::Hidden,
141 cl::desc(
142 "The max of trip count upper bound that is considered in unrolling"));
143
144 static cl::opt<unsigned> PragmaUnrollThreshold(
145 "pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden,
146 cl::desc("Unrolled size limit for loops with an unroll(full) or "
147 "unroll_count pragma."));
148
149 static cl::opt<unsigned> FlatLoopTripCountThreshold(
150 "flat-loop-tripcount-threshold", cl::init(5), cl::Hidden,
151 cl::desc("If the runtime tripcount for the loop is lower than the "
152 "threshold, the loop is considered as flat and will be less "
153 "aggressively unrolled."));
154
155 static cl::opt<bool> UnrollUnrollRemainder(
156 "unroll-remainder", cl::Hidden,
157 cl::desc("Allow the loop remainder to be unrolled."));
158
159 // This option isn't ever intended to be enabled, it serves to allow
160 // experiments to check the assumptions about when this kind of revisit is
161 // necessary.
162 static cl::opt<bool> UnrollRevisitChildLoops(
163 "unroll-revisit-child-loops", cl::Hidden,
164 cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. "
165 "This shouldn't typically be needed as child loops (or their "
166 "clones) were already visited."));
167
168 static cl::opt<unsigned> UnrollThresholdAggressive(
169 "unroll-threshold-aggressive", cl::init(300), cl::Hidden,
170 cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) "
171 "optimizations"));
172 static cl::opt<unsigned>
173 UnrollThresholdDefault("unroll-threshold-default", cl::init(150),
174 cl::Hidden,
175 cl::desc("Default threshold (max size of unrolled "
176 "loop), used in all but O3 optimizations"));
177
178 /// A magic value for use with the Threshold parameter to indicate
179 /// that the loop unroll should be performed regardless of how much
180 /// code expansion would result.
181 static const unsigned NoThreshold = std::numeric_limits<unsigned>::max();
182
183 /// Gather the various unrolling parameters based on the defaults, compiler
184 /// flags, TTI overrides and user specified parameters.
gatherUnrollingPreferences(Loop * L,ScalarEvolution & SE,const TargetTransformInfo & TTI,BlockFrequencyInfo * BFI,ProfileSummaryInfo * PSI,int OptLevel,Optional<unsigned> UserThreshold,Optional<unsigned> UserCount,Optional<bool> UserAllowPartial,Optional<bool> UserRuntime,Optional<bool> UserUpperBound,Optional<unsigned> UserFullUnrollMaxCount)185 TargetTransformInfo::UnrollingPreferences llvm::gatherUnrollingPreferences(
186 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
187 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel,
188 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
189 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
190 Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount) {
191 TargetTransformInfo::UnrollingPreferences UP;
192
193 // Set up the defaults
194 UP.Threshold =
195 OptLevel > 2 ? UnrollThresholdAggressive : UnrollThresholdDefault;
196 UP.MaxPercentThresholdBoost = 400;
197 UP.OptSizeThreshold = UnrollOptSizeThreshold;
198 UP.PartialThreshold = 150;
199 UP.PartialOptSizeThreshold = UnrollOptSizeThreshold;
200 UP.Count = 0;
201 UP.DefaultUnrollRuntimeCount = 8;
202 UP.MaxCount = std::numeric_limits<unsigned>::max();
203 UP.FullUnrollMaxCount = std::numeric_limits<unsigned>::max();
204 UP.BEInsns = 2;
205 UP.Partial = false;
206 UP.Runtime = false;
207 UP.AllowRemainder = true;
208 UP.UnrollRemainder = false;
209 UP.AllowExpensiveTripCount = false;
210 UP.Force = false;
211 UP.UpperBound = false;
212 UP.UnrollAndJam = false;
213 UP.UnrollAndJamInnerLoopThreshold = 60;
214 UP.MaxIterationsCountToAnalyze = UnrollMaxIterationsCountToAnalyze;
215
216 // Override with any target specific settings
217 TTI.getUnrollingPreferences(L, SE, UP);
218
219 // Apply size attributes
220 bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
221 // Let unroll hints / pragmas take precedence over PGSO.
222 (hasUnrollTransformation(L) != TM_ForcedByUser &&
223 llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI,
224 PGSOQueryType::IRPass));
225 if (OptForSize) {
226 UP.Threshold = UP.OptSizeThreshold;
227 UP.PartialThreshold = UP.PartialOptSizeThreshold;
228 UP.MaxPercentThresholdBoost = 100;
229 }
230
231 // Apply any user values specified by cl::opt
232 if (UnrollThreshold.getNumOccurrences() > 0)
233 UP.Threshold = UnrollThreshold;
234 if (UnrollPartialThreshold.getNumOccurrences() > 0)
235 UP.PartialThreshold = UnrollPartialThreshold;
236 if (UnrollMaxPercentThresholdBoost.getNumOccurrences() > 0)
237 UP.MaxPercentThresholdBoost = UnrollMaxPercentThresholdBoost;
238 if (UnrollMaxCount.getNumOccurrences() > 0)
239 UP.MaxCount = UnrollMaxCount;
240 if (UnrollFullMaxCount.getNumOccurrences() > 0)
241 UP.FullUnrollMaxCount = UnrollFullMaxCount;
242 if (UnrollAllowPartial.getNumOccurrences() > 0)
243 UP.Partial = UnrollAllowPartial;
244 if (UnrollAllowRemainder.getNumOccurrences() > 0)
245 UP.AllowRemainder = UnrollAllowRemainder;
246 if (UnrollRuntime.getNumOccurrences() > 0)
247 UP.Runtime = UnrollRuntime;
248 if (UnrollMaxUpperBound == 0)
249 UP.UpperBound = false;
250 if (UnrollUnrollRemainder.getNumOccurrences() > 0)
251 UP.UnrollRemainder = UnrollUnrollRemainder;
252 if (UnrollMaxIterationsCountToAnalyze.getNumOccurrences() > 0)
253 UP.MaxIterationsCountToAnalyze = UnrollMaxIterationsCountToAnalyze;
254
255 // Apply user values provided by argument
256 if (UserThreshold.hasValue()) {
257 UP.Threshold = *UserThreshold;
258 UP.PartialThreshold = *UserThreshold;
259 }
260 if (UserCount.hasValue())
261 UP.Count = *UserCount;
262 if (UserAllowPartial.hasValue())
263 UP.Partial = *UserAllowPartial;
264 if (UserRuntime.hasValue())
265 UP.Runtime = *UserRuntime;
266 if (UserUpperBound.hasValue())
267 UP.UpperBound = *UserUpperBound;
268 if (UserFullUnrollMaxCount.hasValue())
269 UP.FullUnrollMaxCount = *UserFullUnrollMaxCount;
270
271 return UP;
272 }
273
274 namespace {
275
276 /// A struct to densely store the state of an instruction after unrolling at
277 /// each iteration.
278 ///
279 /// This is designed to work like a tuple of <Instruction *, int> for the
280 /// purposes of hashing and lookup, but to be able to associate two boolean
281 /// states with each key.
282 struct UnrolledInstState {
283 Instruction *I;
284 int Iteration : 30;
285 unsigned IsFree : 1;
286 unsigned IsCounted : 1;
287 };
288
289 /// Hashing and equality testing for a set of the instruction states.
290 struct UnrolledInstStateKeyInfo {
291 using PtrInfo = DenseMapInfo<Instruction *>;
292 using PairInfo = DenseMapInfo<std::pair<Instruction *, int>>;
293
getEmptyKey__anon43c653410111::UnrolledInstStateKeyInfo294 static inline UnrolledInstState getEmptyKey() {
295 return {PtrInfo::getEmptyKey(), 0, 0, 0};
296 }
297
getTombstoneKey__anon43c653410111::UnrolledInstStateKeyInfo298 static inline UnrolledInstState getTombstoneKey() {
299 return {PtrInfo::getTombstoneKey(), 0, 0, 0};
300 }
301
getHashValue__anon43c653410111::UnrolledInstStateKeyInfo302 static inline unsigned getHashValue(const UnrolledInstState &S) {
303 return PairInfo::getHashValue({S.I, S.Iteration});
304 }
305
isEqual__anon43c653410111::UnrolledInstStateKeyInfo306 static inline bool isEqual(const UnrolledInstState &LHS,
307 const UnrolledInstState &RHS) {
308 return PairInfo::isEqual({LHS.I, LHS.Iteration}, {RHS.I, RHS.Iteration});
309 }
310 };
311
312 struct EstimatedUnrollCost {
313 /// The estimated cost after unrolling.
314 unsigned UnrolledCost;
315
316 /// The estimated dynamic cost of executing the instructions in the
317 /// rolled form.
318 unsigned RolledDynamicCost;
319 };
320
321 } // end anonymous namespace
322
323 /// Figure out if the loop is worth full unrolling.
324 ///
325 /// Complete loop unrolling can make some loads constant, and we need to know
326 /// if that would expose any further optimization opportunities. This routine
327 /// estimates this optimization. It computes cost of unrolled loop
328 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
329 /// dynamic cost we mean that we won't count costs of blocks that are known not
330 /// to be executed (i.e. if we have a branch in the loop and we know that at the
331 /// given iteration its condition would be resolved to true, we won't add up the
332 /// cost of the 'false'-block).
333 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
334 /// the analysis failed (no benefits expected from the unrolling, or the loop is
335 /// too big to analyze), the returned value is None.
analyzeLoopUnrollCost(const Loop * L,unsigned TripCount,DominatorTree & DT,ScalarEvolution & SE,const SmallPtrSetImpl<const Value * > & EphValues,const TargetTransformInfo & TTI,unsigned MaxUnrolledLoopSize,unsigned MaxIterationsCountToAnalyze)336 static Optional<EstimatedUnrollCost> analyzeLoopUnrollCost(
337 const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE,
338 const SmallPtrSetImpl<const Value *> &EphValues,
339 const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize,
340 unsigned MaxIterationsCountToAnalyze) {
341 // We want to be able to scale offsets by the trip count and add more offsets
342 // to them without checking for overflows, and we already don't want to
343 // analyze *massive* trip counts, so we force the max to be reasonably small.
344 assert(MaxIterationsCountToAnalyze <
345 (unsigned)(std::numeric_limits<int>::max() / 2) &&
346 "The unroll iterations max is too large!");
347
348 // Only analyze inner loops. We can't properly estimate cost of nested loops
349 // and we won't visit inner loops again anyway.
350 if (!L->isInnermost())
351 return None;
352
353 // Don't simulate loops with a big or unknown tripcount
354 if (!TripCount || TripCount > MaxIterationsCountToAnalyze)
355 return None;
356
357 SmallSetVector<BasicBlock *, 16> BBWorklist;
358 SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
359 DenseMap<Value *, Constant *> SimplifiedValues;
360 SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
361
362 // The estimated cost of the unrolled form of the loop. We try to estimate
363 // this by simplifying as much as we can while computing the estimate.
364 InstructionCost UnrolledCost = 0;
365
366 // We also track the estimated dynamic (that is, actually executed) cost in
367 // the rolled form. This helps identify cases when the savings from unrolling
368 // aren't just exposing dead control flows, but actual reduced dynamic
369 // instructions due to the simplifications which we expect to occur after
370 // unrolling.
371 InstructionCost RolledDynamicCost = 0;
372
373 // We track the simplification of each instruction in each iteration. We use
374 // this to recursively merge costs into the unrolled cost on-demand so that
375 // we don't count the cost of any dead code. This is essentially a map from
376 // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
377 DenseSet<UnrolledInstState, UnrolledInstStateKeyInfo> InstCostMap;
378
379 // A small worklist used to accumulate cost of instructions from each
380 // observable and reached root in the loop.
381 SmallVector<Instruction *, 16> CostWorklist;
382
383 // PHI-used worklist used between iterations while accumulating cost.
384 SmallVector<Instruction *, 4> PHIUsedList;
385
386 // Helper function to accumulate cost for instructions in the loop.
387 auto AddCostRecursively = [&](Instruction &RootI, int Iteration) {
388 assert(Iteration >= 0 && "Cannot have a negative iteration!");
389 assert(CostWorklist.empty() && "Must start with an empty cost list");
390 assert(PHIUsedList.empty() && "Must start with an empty phi used list");
391 CostWorklist.push_back(&RootI);
392 TargetTransformInfo::TargetCostKind CostKind =
393 RootI.getFunction()->hasMinSize() ?
394 TargetTransformInfo::TCK_CodeSize :
395 TargetTransformInfo::TCK_SizeAndLatency;
396 for (;; --Iteration) {
397 do {
398 Instruction *I = CostWorklist.pop_back_val();
399
400 // InstCostMap only uses I and Iteration as a key, the other two values
401 // don't matter here.
402 auto CostIter = InstCostMap.find({I, Iteration, 0, 0});
403 if (CostIter == InstCostMap.end())
404 // If an input to a PHI node comes from a dead path through the loop
405 // we may have no cost data for it here. What that actually means is
406 // that it is free.
407 continue;
408 auto &Cost = *CostIter;
409 if (Cost.IsCounted)
410 // Already counted this instruction.
411 continue;
412
413 // Mark that we are counting the cost of this instruction now.
414 Cost.IsCounted = true;
415
416 // If this is a PHI node in the loop header, just add it to the PHI set.
417 if (auto *PhiI = dyn_cast<PHINode>(I))
418 if (PhiI->getParent() == L->getHeader()) {
419 assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
420 "inherently simplify during unrolling.");
421 if (Iteration == 0)
422 continue;
423
424 // Push the incoming value from the backedge into the PHI used list
425 // if it is an in-loop instruction. We'll use this to populate the
426 // cost worklist for the next iteration (as we count backwards).
427 if (auto *OpI = dyn_cast<Instruction>(
428 PhiI->getIncomingValueForBlock(L->getLoopLatch())))
429 if (L->contains(OpI))
430 PHIUsedList.push_back(OpI);
431 continue;
432 }
433
434 // First accumulate the cost of this instruction.
435 if (!Cost.IsFree) {
436 UnrolledCost += TTI.getUserCost(I, CostKind);
437 LLVM_DEBUG(dbgs() << "Adding cost of instruction (iteration "
438 << Iteration << "): ");
439 LLVM_DEBUG(I->dump());
440 }
441
442 // We must count the cost of every operand which is not free,
443 // recursively. If we reach a loop PHI node, simply add it to the set
444 // to be considered on the next iteration (backwards!).
445 for (Value *Op : I->operands()) {
446 // Check whether this operand is free due to being a constant or
447 // outside the loop.
448 auto *OpI = dyn_cast<Instruction>(Op);
449 if (!OpI || !L->contains(OpI))
450 continue;
451
452 // Otherwise accumulate its cost.
453 CostWorklist.push_back(OpI);
454 }
455 } while (!CostWorklist.empty());
456
457 if (PHIUsedList.empty())
458 // We've exhausted the search.
459 break;
460
461 assert(Iteration > 0 &&
462 "Cannot track PHI-used values past the first iteration!");
463 CostWorklist.append(PHIUsedList.begin(), PHIUsedList.end());
464 PHIUsedList.clear();
465 }
466 };
467
468 // Ensure that we don't violate the loop structure invariants relied on by
469 // this analysis.
470 assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
471 assert(L->isLCSSAForm(DT) &&
472 "Must have loops in LCSSA form to track live-out values.");
473
474 LLVM_DEBUG(dbgs() << "Starting LoopUnroll profitability analysis...\n");
475
476 TargetTransformInfo::TargetCostKind CostKind =
477 L->getHeader()->getParent()->hasMinSize() ?
478 TargetTransformInfo::TCK_CodeSize : TargetTransformInfo::TCK_SizeAndLatency;
479 // Simulate execution of each iteration of the loop counting instructions,
480 // which would be simplified.
481 // Since the same load will take different values on different iterations,
482 // we literally have to go through all loop's iterations.
483 for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
484 LLVM_DEBUG(dbgs() << " Analyzing iteration " << Iteration << "\n");
485
486 // Prepare for the iteration by collecting any simplified entry or backedge
487 // inputs.
488 for (Instruction &I : *L->getHeader()) {
489 auto *PHI = dyn_cast<PHINode>(&I);
490 if (!PHI)
491 break;
492
493 // The loop header PHI nodes must have exactly two input: one from the
494 // loop preheader and one from the loop latch.
495 assert(
496 PHI->getNumIncomingValues() == 2 &&
497 "Must have an incoming value only for the preheader and the latch.");
498
499 Value *V = PHI->getIncomingValueForBlock(
500 Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
501 Constant *C = dyn_cast<Constant>(V);
502 if (Iteration != 0 && !C)
503 C = SimplifiedValues.lookup(V);
504 if (C)
505 SimplifiedInputValues.push_back({PHI, C});
506 }
507
508 // Now clear and re-populate the map for the next iteration.
509 SimplifiedValues.clear();
510 while (!SimplifiedInputValues.empty())
511 SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
512
513 UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
514
515 BBWorklist.clear();
516 BBWorklist.insert(L->getHeader());
517 // Note that we *must not* cache the size, this loop grows the worklist.
518 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
519 BasicBlock *BB = BBWorklist[Idx];
520
521 // Visit all instructions in the given basic block and try to simplify
522 // it. We don't change the actual IR, just count optimization
523 // opportunities.
524 for (Instruction &I : *BB) {
525 // These won't get into the final code - don't even try calculating the
526 // cost for them.
527 if (isa<DbgInfoIntrinsic>(I) || EphValues.count(&I))
528 continue;
529
530 // Track this instruction's expected baseline cost when executing the
531 // rolled loop form.
532 RolledDynamicCost += TTI.getUserCost(&I, CostKind);
533
534 // Visit the instruction to analyze its loop cost after unrolling,
535 // and if the visitor returns true, mark the instruction as free after
536 // unrolling and continue.
537 bool IsFree = Analyzer.visit(I);
538 bool Inserted = InstCostMap.insert({&I, (int)Iteration,
539 (unsigned)IsFree,
540 /*IsCounted*/ false}).second;
541 (void)Inserted;
542 assert(Inserted && "Cannot have a state for an unvisited instruction!");
543
544 if (IsFree)
545 continue;
546
547 // Can't properly model a cost of a call.
548 // FIXME: With a proper cost model we should be able to do it.
549 if (auto *CI = dyn_cast<CallInst>(&I)) {
550 const Function *Callee = CI->getCalledFunction();
551 if (!Callee || TTI.isLoweredToCall(Callee)) {
552 LLVM_DEBUG(dbgs() << "Can't analyze cost of loop with call\n");
553 return None;
554 }
555 }
556
557 // If the instruction might have a side-effect recursively account for
558 // the cost of it and all the instructions leading up to it.
559 if (I.mayHaveSideEffects())
560 AddCostRecursively(I, Iteration);
561
562 // If unrolled body turns out to be too big, bail out.
563 if (UnrolledCost > MaxUnrolledLoopSize) {
564 LLVM_DEBUG(dbgs() << " Exceeded threshold.. exiting.\n"
565 << " UnrolledCost: " << UnrolledCost
566 << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
567 << "\n");
568 return None;
569 }
570 }
571
572 Instruction *TI = BB->getTerminator();
573
574 // Add in the live successors by first checking whether we have terminator
575 // that may be simplified based on the values simplified by this call.
576 BasicBlock *KnownSucc = nullptr;
577 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
578 if (BI->isConditional()) {
579 if (Constant *SimpleCond =
580 SimplifiedValues.lookup(BI->getCondition())) {
581 // Just take the first successor if condition is undef
582 if (isa<UndefValue>(SimpleCond))
583 KnownSucc = BI->getSuccessor(0);
584 else if (ConstantInt *SimpleCondVal =
585 dyn_cast<ConstantInt>(SimpleCond))
586 KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
587 }
588 }
589 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
590 if (Constant *SimpleCond =
591 SimplifiedValues.lookup(SI->getCondition())) {
592 // Just take the first successor if condition is undef
593 if (isa<UndefValue>(SimpleCond))
594 KnownSucc = SI->getSuccessor(0);
595 else if (ConstantInt *SimpleCondVal =
596 dyn_cast<ConstantInt>(SimpleCond))
597 KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
598 }
599 }
600 if (KnownSucc) {
601 if (L->contains(KnownSucc))
602 BBWorklist.insert(KnownSucc);
603 else
604 ExitWorklist.insert({BB, KnownSucc});
605 continue;
606 }
607
608 // Add BB's successors to the worklist.
609 for (BasicBlock *Succ : successors(BB))
610 if (L->contains(Succ))
611 BBWorklist.insert(Succ);
612 else
613 ExitWorklist.insert({BB, Succ});
614 AddCostRecursively(*TI, Iteration);
615 }
616
617 // If we found no optimization opportunities on the first iteration, we
618 // won't find them on later ones too.
619 if (UnrolledCost == RolledDynamicCost) {
620 LLVM_DEBUG(dbgs() << " No opportunities found.. exiting.\n"
621 << " UnrolledCost: " << UnrolledCost << "\n");
622 return None;
623 }
624 }
625
626 while (!ExitWorklist.empty()) {
627 BasicBlock *ExitingBB, *ExitBB;
628 std::tie(ExitingBB, ExitBB) = ExitWorklist.pop_back_val();
629
630 for (Instruction &I : *ExitBB) {
631 auto *PN = dyn_cast<PHINode>(&I);
632 if (!PN)
633 break;
634
635 Value *Op = PN->getIncomingValueForBlock(ExitingBB);
636 if (auto *OpI = dyn_cast<Instruction>(Op))
637 if (L->contains(OpI))
638 AddCostRecursively(*OpI, TripCount - 1);
639 }
640 }
641
642 assert(UnrolledCost.isValid() && RolledDynamicCost.isValid() &&
643 "All instructions must have a valid cost, whether the "
644 "loop is rolled or unrolled.");
645
646 LLVM_DEBUG(dbgs() << "Analysis finished:\n"
647 << "UnrolledCost: " << UnrolledCost << ", "
648 << "RolledDynamicCost: " << RolledDynamicCost << "\n");
649 return {{unsigned(*UnrolledCost.getValue()),
650 unsigned(*RolledDynamicCost.getValue())}};
651 }
652
653 /// ApproximateLoopSize - Approximate the size of the loop.
ApproximateLoopSize(const Loop * L,unsigned & NumCalls,bool & NotDuplicatable,bool & Convergent,const TargetTransformInfo & TTI,const SmallPtrSetImpl<const Value * > & EphValues,unsigned BEInsns)654 unsigned llvm::ApproximateLoopSize(
655 const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent,
656 const TargetTransformInfo &TTI,
657 const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns) {
658 CodeMetrics Metrics;
659 for (BasicBlock *BB : L->blocks())
660 Metrics.analyzeBasicBlock(BB, TTI, EphValues);
661 NumCalls = Metrics.NumInlineCandidates;
662 NotDuplicatable = Metrics.notDuplicatable;
663 Convergent = Metrics.convergent;
664
665 unsigned LoopSize = Metrics.NumInsts;
666
667 // Don't allow an estimate of size zero. This would allows unrolling of loops
668 // with huge iteration counts, which is a compile time problem even if it's
669 // not a problem for code quality. Also, the code using this size may assume
670 // that each loop has at least three instructions (likely a conditional
671 // branch, a comparison feeding that branch, and some kind of loop increment
672 // feeding that comparison instruction).
673 LoopSize = std::max(LoopSize, BEInsns + 1);
674
675 return LoopSize;
676 }
677
678 // Returns the loop hint metadata node with the given name (for example,
679 // "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
680 // returned.
getUnrollMetadataForLoop(const Loop * L,StringRef Name)681 static MDNode *getUnrollMetadataForLoop(const Loop *L, StringRef Name) {
682 if (MDNode *LoopID = L->getLoopID())
683 return GetUnrollMetadata(LoopID, Name);
684 return nullptr;
685 }
686
687 // Returns true if the loop has an unroll(full) pragma.
hasUnrollFullPragma(const Loop * L)688 static bool hasUnrollFullPragma(const Loop *L) {
689 return getUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
690 }
691
692 // Returns true if the loop has an unroll(enable) pragma. This metadata is used
693 // for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
hasUnrollEnablePragma(const Loop * L)694 static bool hasUnrollEnablePragma(const Loop *L) {
695 return getUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
696 }
697
698 // Returns true if the loop has an runtime unroll(disable) pragma.
hasRuntimeUnrollDisablePragma(const Loop * L)699 static bool hasRuntimeUnrollDisablePragma(const Loop *L) {
700 return getUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
701 }
702
703 // If loop has an unroll_count pragma return the (necessarily
704 // positive) value from the pragma. Otherwise return 0.
unrollCountPragmaValue(const Loop * L)705 static unsigned unrollCountPragmaValue(const Loop *L) {
706 MDNode *MD = getUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
707 if (MD) {
708 assert(MD->getNumOperands() == 2 &&
709 "Unroll count hint metadata should have two operands.");
710 unsigned Count =
711 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
712 assert(Count >= 1 && "Unroll count must be positive.");
713 return Count;
714 }
715 return 0;
716 }
717
718 // Computes the boosting factor for complete unrolling.
719 // If fully unrolling the loop would save a lot of RolledDynamicCost, it would
720 // be beneficial to fully unroll the loop even if unrolledcost is large. We
721 // use (RolledDynamicCost / UnrolledCost) to model the unroll benefits to adjust
722 // the unroll threshold.
getFullUnrollBoostingFactor(const EstimatedUnrollCost & Cost,unsigned MaxPercentThresholdBoost)723 static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost,
724 unsigned MaxPercentThresholdBoost) {
725 if (Cost.RolledDynamicCost >= std::numeric_limits<unsigned>::max() / 100)
726 return 100;
727 else if (Cost.UnrolledCost != 0)
728 // The boosting factor is RolledDynamicCost / UnrolledCost
729 return std::min(100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
730 MaxPercentThresholdBoost);
731 else
732 return MaxPercentThresholdBoost;
733 }
734
735 // Produce an estimate of the unrolled cost of the specified loop. This
736 // is used to a) produce a cost estimate for partial unrolling and b) to
737 // cheaply estimate cost for full unrolling when we don't want to symbolically
738 // evaluate all iterations.
739 class UnrollCostEstimator {
740 const unsigned LoopSize;
741
742 public:
UnrollCostEstimator(Loop & L,unsigned LoopSize)743 UnrollCostEstimator(Loop &L, unsigned LoopSize) : LoopSize(LoopSize) {}
744
745 // Returns loop size estimation for unrolled loop, given the unrolling
746 // configuration specified by UP.
getUnrolledLoopSize(TargetTransformInfo::UnrollingPreferences & UP)747 uint64_t getUnrolledLoopSize(TargetTransformInfo::UnrollingPreferences &UP) {
748 assert(LoopSize >= UP.BEInsns &&
749 "LoopSize should not be less than BEInsns!");
750 return (uint64_t)(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
751 }
752 };
753
754 // Returns true if unroll count was set explicitly.
755 // Calculates unroll count and writes it to UP.Count.
756 // Unless IgnoreUser is true, will also use metadata and command-line options
757 // that are specific to to the LoopUnroll pass (which, for instance, are
758 // irrelevant for the LoopUnrollAndJam pass).
759 // FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
760 // many LoopUnroll-specific options. The shared functionality should be
761 // refactored into it own function.
computeUnrollCount(Loop * L,const TargetTransformInfo & TTI,DominatorTree & DT,LoopInfo * LI,ScalarEvolution & SE,const SmallPtrSetImpl<const Value * > & EphValues,OptimizationRemarkEmitter * ORE,unsigned & TripCount,unsigned MaxTripCount,bool MaxOrZero,unsigned & TripMultiple,unsigned LoopSize,TargetTransformInfo::UnrollingPreferences & UP,TargetTransformInfo::PeelingPreferences & PP,bool & UseUpperBound)762 bool llvm::computeUnrollCount(
763 Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
764 ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
765 OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount,
766 bool MaxOrZero, unsigned &TripMultiple, unsigned LoopSize,
767 TargetTransformInfo::UnrollingPreferences &UP,
768 TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound) {
769
770 UnrollCostEstimator UCE(*L, LoopSize);
771
772 // Check for explicit Count.
773 // 1st priority is unroll count set by "unroll-count" option.
774 bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
775 if (UserUnrollCount) {
776 UP.Count = UnrollCount;
777 UP.AllowExpensiveTripCount = true;
778 UP.Force = true;
779 if (UP.AllowRemainder && UCE.getUnrolledLoopSize(UP) < UP.Threshold)
780 return true;
781 }
782
783 // 2nd priority is unroll count set by pragma.
784 unsigned PragmaCount = unrollCountPragmaValue(L);
785 if (PragmaCount > 0) {
786 UP.Count = PragmaCount;
787 UP.Runtime = true;
788 UP.AllowExpensiveTripCount = true;
789 UP.Force = true;
790 if ((UP.AllowRemainder || (TripMultiple % PragmaCount == 0)) &&
791 UCE.getUnrolledLoopSize(UP) < PragmaUnrollThreshold)
792 return true;
793 }
794 bool PragmaFullUnroll = hasUnrollFullPragma(L);
795 if (PragmaFullUnroll && TripCount != 0) {
796 UP.Count = TripCount;
797 if (UCE.getUnrolledLoopSize(UP) < PragmaUnrollThreshold)
798 return false;
799 }
800
801 bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
802 bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
803 PragmaEnableUnroll || UserUnrollCount;
804
805 if (ExplicitUnroll && TripCount != 0) {
806 // If the loop has an unrolling pragma, we want to be more aggressive with
807 // unrolling limits. Set thresholds to at least the PragmaUnrollThreshold
808 // value which is larger than the default limits.
809 UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
810 UP.PartialThreshold =
811 std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
812 }
813
814 // 3rd priority is full unroll count.
815 // Full unroll makes sense only when TripCount or its upper bound could be
816 // statically calculated.
817 // Also we need to check if we exceed FullUnrollMaxCount.
818 // If using the upper bound to unroll, TripMultiple should be set to 1 because
819 // we do not know when loop may exit.
820
821 // We can unroll by the upper bound amount if it's generally allowed or if
822 // we know that the loop is executed either the upper bound or zero times.
823 // (MaxOrZero unrolling keeps only the first loop test, so the number of
824 // loop tests remains the same compared to the non-unrolled version, whereas
825 // the generic upper bound unrolling keeps all but the last loop test so the
826 // number of loop tests goes up which may end up being worse on targets with
827 // constrained branch predictor resources so is controlled by an option.)
828 // In addition we only unroll small upper bounds.
829 unsigned FullUnrollMaxTripCount = MaxTripCount;
830 if (!(UP.UpperBound || MaxOrZero) ||
831 FullUnrollMaxTripCount > UnrollMaxUpperBound)
832 FullUnrollMaxTripCount = 0;
833
834 // UnrollByMaxCount and ExactTripCount cannot both be non zero since we only
835 // compute the former when the latter is zero.
836 unsigned ExactTripCount = TripCount;
837 assert((ExactTripCount == 0 || FullUnrollMaxTripCount == 0) &&
838 "ExtractTripCount and UnrollByMaxCount cannot both be non zero.");
839
840 unsigned FullUnrollTripCount =
841 ExactTripCount ? ExactTripCount : FullUnrollMaxTripCount;
842 UP.Count = FullUnrollTripCount;
843 if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
844 // When computing the unrolled size, note that BEInsns are not replicated
845 // like the rest of the loop body.
846 if (UCE.getUnrolledLoopSize(UP) < UP.Threshold) {
847 UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
848 TripCount = FullUnrollTripCount;
849 TripMultiple = UP.UpperBound ? 1 : TripMultiple;
850 return ExplicitUnroll;
851 } else {
852 // The loop isn't that small, but we still can fully unroll it if that
853 // helps to remove a significant number of instructions.
854 // To check that, run additional analysis on the loop.
855 if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
856 L, FullUnrollTripCount, DT, SE, EphValues, TTI,
857 UP.Threshold * UP.MaxPercentThresholdBoost / 100,
858 UP.MaxIterationsCountToAnalyze)) {
859 unsigned Boost =
860 getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
861 if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
862 UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
863 TripCount = FullUnrollTripCount;
864 TripMultiple = UP.UpperBound ? 1 : TripMultiple;
865 return ExplicitUnroll;
866 }
867 }
868 }
869 }
870
871 // 4th priority is loop peeling.
872 computePeelCount(L, LoopSize, PP, TripCount, SE, UP.Threshold);
873 if (PP.PeelCount) {
874 UP.Runtime = false;
875 UP.Count = 1;
876 return ExplicitUnroll;
877 }
878
879 // 5th priority is partial unrolling.
880 // Try partial unroll only when TripCount could be statically calculated.
881 if (TripCount) {
882 UP.Partial |= ExplicitUnroll;
883 if (!UP.Partial) {
884 LLVM_DEBUG(dbgs() << " will not try to unroll partially because "
885 << "-unroll-allow-partial not given\n");
886 UP.Count = 0;
887 return false;
888 }
889 if (UP.Count == 0)
890 UP.Count = TripCount;
891 if (UP.PartialThreshold != NoThreshold) {
892 // Reduce unroll count to be modulo of TripCount for partial unrolling.
893 if (UCE.getUnrolledLoopSize(UP) > UP.PartialThreshold)
894 UP.Count =
895 (std::max(UP.PartialThreshold, UP.BEInsns + 1) - UP.BEInsns) /
896 (LoopSize - UP.BEInsns);
897 if (UP.Count > UP.MaxCount)
898 UP.Count = UP.MaxCount;
899 while (UP.Count != 0 && TripCount % UP.Count != 0)
900 UP.Count--;
901 if (UP.AllowRemainder && UP.Count <= 1) {
902 // If there is no Count that is modulo of TripCount, set Count to
903 // largest power-of-two factor that satisfies the threshold limit.
904 // As we'll create fixup loop, do the type of unrolling only if
905 // remainder loop is allowed.
906 UP.Count = UP.DefaultUnrollRuntimeCount;
907 while (UP.Count != 0 &&
908 UCE.getUnrolledLoopSize(UP) > UP.PartialThreshold)
909 UP.Count >>= 1;
910 }
911 if (UP.Count < 2) {
912 if (PragmaEnableUnroll)
913 ORE->emit([&]() {
914 return OptimizationRemarkMissed(DEBUG_TYPE,
915 "UnrollAsDirectedTooLarge",
916 L->getStartLoc(), L->getHeader())
917 << "Unable to unroll loop as directed by unroll(enable) "
918 "pragma "
919 "because unrolled size is too large.";
920 });
921 UP.Count = 0;
922 }
923 } else {
924 UP.Count = TripCount;
925 }
926 if (UP.Count > UP.MaxCount)
927 UP.Count = UP.MaxCount;
928 if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
929 UP.Count != TripCount)
930 ORE->emit([&]() {
931 return OptimizationRemarkMissed(DEBUG_TYPE,
932 "FullUnrollAsDirectedTooLarge",
933 L->getStartLoc(), L->getHeader())
934 << "Unable to fully unroll loop as directed by unroll pragma "
935 "because "
936 "unrolled size is too large.";
937 });
938 LLVM_DEBUG(dbgs() << " partially unrolling with count: " << UP.Count
939 << "\n");
940 return ExplicitUnroll;
941 }
942 assert(TripCount == 0 &&
943 "All cases when TripCount is constant should be covered here.");
944 if (PragmaFullUnroll)
945 ORE->emit([&]() {
946 return OptimizationRemarkMissed(
947 DEBUG_TYPE, "CantFullUnrollAsDirectedRuntimeTripCount",
948 L->getStartLoc(), L->getHeader())
949 << "Unable to fully unroll loop as directed by unroll(full) "
950 "pragma "
951 "because loop has a runtime trip count.";
952 });
953
954 // 6th priority is runtime unrolling.
955 // Don't unroll a runtime trip count loop when it is disabled.
956 if (hasRuntimeUnrollDisablePragma(L)) {
957 UP.Count = 0;
958 return false;
959 }
960
961 // Don't unroll a small upper bound loop unless user or TTI asked to do so.
962 if (MaxTripCount && !UP.Force && MaxTripCount < UnrollMaxUpperBound) {
963 UP.Count = 0;
964 return false;
965 }
966
967 // Check if the runtime trip count is too small when profile is available.
968 if (L->getHeader()->getParent()->hasProfileData()) {
969 if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
970 if (*ProfileTripCount < FlatLoopTripCountThreshold)
971 return false;
972 else
973 UP.AllowExpensiveTripCount = true;
974 }
975 }
976
977 // Reduce count based on the type of unrolling and the threshold values.
978 UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
979 if (!UP.Runtime) {
980 LLVM_DEBUG(
981 dbgs() << " will not try to unroll loop with runtime trip count "
982 << "-unroll-runtime not given\n");
983 UP.Count = 0;
984 return false;
985 }
986 if (UP.Count == 0)
987 UP.Count = UP.DefaultUnrollRuntimeCount;
988
989 // Reduce unroll count to be the largest power-of-two factor of
990 // the original count which satisfies the threshold limit.
991 while (UP.Count != 0 &&
992 UCE.getUnrolledLoopSize(UP) > UP.PartialThreshold)
993 UP.Count >>= 1;
994
995 #ifndef NDEBUG
996 unsigned OrigCount = UP.Count;
997 #endif
998
999 if (!UP.AllowRemainder && UP.Count != 0 && (TripMultiple % UP.Count) != 0) {
1000 while (UP.Count != 0 && TripMultiple % UP.Count != 0)
1001 UP.Count >>= 1;
1002 LLVM_DEBUG(
1003 dbgs() << "Remainder loop is restricted (that could architecture "
1004 "specific or because the loop contains a convergent "
1005 "instruction), so unroll count must divide the trip "
1006 "multiple, "
1007 << TripMultiple << ". Reducing unroll count from " << OrigCount
1008 << " to " << UP.Count << ".\n");
1009
1010 using namespace ore;
1011
1012 if (PragmaCount > 0 && !UP.AllowRemainder)
1013 ORE->emit([&]() {
1014 return OptimizationRemarkMissed(DEBUG_TYPE,
1015 "DifferentUnrollCountFromDirected",
1016 L->getStartLoc(), L->getHeader())
1017 << "Unable to unroll loop the number of times directed by "
1018 "unroll_count pragma because remainder loop is restricted "
1019 "(that could architecture specific or because the loop "
1020 "contains a convergent instruction) and so must have an "
1021 "unroll "
1022 "count that divides the loop trip multiple of "
1023 << NV("TripMultiple", TripMultiple) << ". Unrolling instead "
1024 << NV("UnrollCount", UP.Count) << " time(s).";
1025 });
1026 }
1027
1028 if (UP.Count > UP.MaxCount)
1029 UP.Count = UP.MaxCount;
1030
1031 if (MaxTripCount && UP.Count > MaxTripCount)
1032 UP.Count = MaxTripCount;
1033
1034 LLVM_DEBUG(dbgs() << " runtime unrolling with count: " << UP.Count
1035 << "\n");
1036 if (UP.Count < 2)
1037 UP.Count = 0;
1038 return ExplicitUnroll;
1039 }
1040
tryToUnrollLoop(Loop * L,DominatorTree & DT,LoopInfo * LI,ScalarEvolution & SE,const TargetTransformInfo & TTI,AssumptionCache & AC,OptimizationRemarkEmitter & ORE,BlockFrequencyInfo * BFI,ProfileSummaryInfo * PSI,bool PreserveLCSSA,int OptLevel,bool OnlyWhenForced,bool ForgetAllSCEV,Optional<unsigned> ProvidedCount,Optional<unsigned> ProvidedThreshold,Optional<bool> ProvidedAllowPartial,Optional<bool> ProvidedRuntime,Optional<bool> ProvidedUpperBound,Optional<bool> ProvidedAllowPeeling,Optional<bool> ProvidedAllowProfileBasedPeeling,Optional<unsigned> ProvidedFullUnrollMaxCount)1041 static LoopUnrollResult tryToUnrollLoop(
1042 Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
1043 const TargetTransformInfo &TTI, AssumptionCache &AC,
1044 OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
1045 ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel,
1046 bool OnlyWhenForced, bool ForgetAllSCEV, Optional<unsigned> ProvidedCount,
1047 Optional<unsigned> ProvidedThreshold, Optional<bool> ProvidedAllowPartial,
1048 Optional<bool> ProvidedRuntime, Optional<bool> ProvidedUpperBound,
1049 Optional<bool> ProvidedAllowPeeling,
1050 Optional<bool> ProvidedAllowProfileBasedPeeling,
1051 Optional<unsigned> ProvidedFullUnrollMaxCount) {
1052 LLVM_DEBUG(dbgs() << "Loop Unroll: F["
1053 << L->getHeader()->getParent()->getName() << "] Loop %"
1054 << L->getHeader()->getName() << "\n");
1055 TransformationMode TM = hasUnrollTransformation(L);
1056 if (TM & TM_Disable)
1057 return LoopUnrollResult::Unmodified;
1058 if (!L->isLoopSimplifyForm()) {
1059 LLVM_DEBUG(
1060 dbgs() << " Not unrolling loop which is not in loop-simplify form.\n");
1061 return LoopUnrollResult::Unmodified;
1062 }
1063
1064 // When automatic unrolling is disabled, do not unroll unless overridden for
1065 // this loop.
1066 if (OnlyWhenForced && !(TM & TM_Enable))
1067 return LoopUnrollResult::Unmodified;
1068
1069 bool OptForSize = L->getHeader()->getParent()->hasOptSize();
1070 unsigned NumInlineCandidates;
1071 bool NotDuplicatable;
1072 bool Convergent;
1073 TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
1074 L, SE, TTI, BFI, PSI, OptLevel, ProvidedThreshold, ProvidedCount,
1075 ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1076 ProvidedFullUnrollMaxCount);
1077 TargetTransformInfo::PeelingPreferences PP = gatherPeelingPreferences(
1078 L, SE, TTI, ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling, true);
1079
1080 // Exit early if unrolling is disabled. For OptForSize, we pick the loop size
1081 // as threshold later on.
1082 if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0) &&
1083 !OptForSize)
1084 return LoopUnrollResult::Unmodified;
1085
1086 SmallPtrSet<const Value *, 32> EphValues;
1087 CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
1088
1089 unsigned LoopSize =
1090 ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
1091 TTI, EphValues, UP.BEInsns);
1092 LLVM_DEBUG(dbgs() << " Loop Size = " << LoopSize << "\n");
1093 if (NotDuplicatable) {
1094 LLVM_DEBUG(dbgs() << " Not unrolling loop which contains non-duplicatable"
1095 << " instructions.\n");
1096 return LoopUnrollResult::Unmodified;
1097 }
1098
1099 // When optimizing for size, use LoopSize + 1 as threshold (we use < Threshold
1100 // later), to (fully) unroll loops, if it does not increase code size.
1101 if (OptForSize)
1102 UP.Threshold = std::max(UP.Threshold, LoopSize + 1);
1103
1104 if (NumInlineCandidates != 0) {
1105 LLVM_DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n");
1106 return LoopUnrollResult::Unmodified;
1107 }
1108
1109 // Find trip count and trip multiple if count is not available
1110 unsigned TripCount = 0;
1111 unsigned TripMultiple = 1;
1112 // If there are multiple exiting blocks but one of them is the latch, use the
1113 // latch for the trip count estimation. Otherwise insist on a single exiting
1114 // block for the trip count estimation.
1115 BasicBlock *ExitingBlock = L->getLoopLatch();
1116 if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
1117 ExitingBlock = L->getExitingBlock();
1118 if (ExitingBlock) {
1119 TripCount = SE.getSmallConstantTripCount(L, ExitingBlock);
1120 TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
1121 }
1122
1123 // If the loop contains a convergent operation, the prelude we'd add
1124 // to do the first few instructions before we hit the unrolled loop
1125 // is unsafe -- it adds a control-flow dependency to the convergent
1126 // operation. Therefore restrict remainder loop (try unrolling without).
1127 //
1128 // TODO: This is quite conservative. In practice, convergent_op()
1129 // is likely to be called unconditionally in the loop. In this
1130 // case, the program would be ill-formed (on most architectures)
1131 // unless n were the same on all threads in a thread group.
1132 // Assuming n is the same on all threads, any kind of unrolling is
1133 // safe. But currently llvm's notion of convergence isn't powerful
1134 // enough to express this.
1135 if (Convergent)
1136 UP.AllowRemainder = false;
1137
1138 // Try to find the trip count upper bound if we cannot find the exact trip
1139 // count.
1140 unsigned MaxTripCount = 0;
1141 bool MaxOrZero = false;
1142 if (!TripCount) {
1143 MaxTripCount = SE.getSmallConstantMaxTripCount(L);
1144 MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
1145 }
1146
1147 // computeUnrollCount() decides whether it is beneficial to use upper bound to
1148 // fully unroll the loop.
1149 bool UseUpperBound = false;
1150 bool IsCountSetExplicitly = computeUnrollCount(
1151 L, TTI, DT, LI, SE, EphValues, &ORE, TripCount, MaxTripCount, MaxOrZero,
1152 TripMultiple, LoopSize, UP, PP, UseUpperBound);
1153 if (!UP.Count)
1154 return LoopUnrollResult::Unmodified;
1155 // Unroll factor (Count) must be less or equal to TripCount.
1156 if (TripCount && UP.Count > TripCount)
1157 UP.Count = TripCount;
1158
1159 // Save loop properties before it is transformed.
1160 MDNode *OrigLoopID = L->getLoopID();
1161
1162 // Unroll the loop.
1163 Loop *RemainderLoop = nullptr;
1164 LoopUnrollResult UnrollResult = UnrollLoop(
1165 L,
1166 {UP.Count, TripCount, UP.Force, UP.Runtime, UP.AllowExpensiveTripCount,
1167 UseUpperBound, MaxOrZero, TripMultiple, PP.PeelCount, UP.UnrollRemainder,
1168 ForgetAllSCEV},
1169 LI, &SE, &DT, &AC, &TTI, &ORE, PreserveLCSSA, &RemainderLoop);
1170 if (UnrollResult == LoopUnrollResult::Unmodified)
1171 return LoopUnrollResult::Unmodified;
1172
1173 if (RemainderLoop) {
1174 Optional<MDNode *> RemainderLoopID =
1175 makeFollowupLoopID(OrigLoopID, {LLVMLoopUnrollFollowupAll,
1176 LLVMLoopUnrollFollowupRemainder});
1177 if (RemainderLoopID.hasValue())
1178 RemainderLoop->setLoopID(RemainderLoopID.getValue());
1179 }
1180
1181 if (UnrollResult != LoopUnrollResult::FullyUnrolled) {
1182 Optional<MDNode *> NewLoopID =
1183 makeFollowupLoopID(OrigLoopID, {LLVMLoopUnrollFollowupAll,
1184 LLVMLoopUnrollFollowupUnrolled});
1185 if (NewLoopID.hasValue()) {
1186 L->setLoopID(NewLoopID.getValue());
1187
1188 // Do not setLoopAlreadyUnrolled if loop attributes have been specified
1189 // explicitly.
1190 return UnrollResult;
1191 }
1192 }
1193
1194 // If loop has an unroll count pragma or unrolled by explicitly set count
1195 // mark loop as unrolled to prevent unrolling beyond that requested.
1196 // If the loop was peeled, we already "used up" the profile information
1197 // we had, so we don't want to unroll or peel again.
1198 if (UnrollResult != LoopUnrollResult::FullyUnrolled &&
1199 (IsCountSetExplicitly || (PP.PeelProfiledIterations && PP.PeelCount)))
1200 L->setLoopAlreadyUnrolled();
1201
1202 return UnrollResult;
1203 }
1204
1205 namespace {
1206
1207 class LoopUnroll : public LoopPass {
1208 public:
1209 static char ID; // Pass ID, replacement for typeid
1210
1211 int OptLevel;
1212
1213 /// If false, use a cost model to determine whether unrolling of a loop is
1214 /// profitable. If true, only loops that explicitly request unrolling via
1215 /// metadata are considered. All other loops are skipped.
1216 bool OnlyWhenForced;
1217
1218 /// If false, when SCEV is invalidated, only forget everything in the
1219 /// top-most loop (call forgetTopMostLoop), of the loop being processed.
1220 /// Otherwise, forgetAllLoops and rebuild when needed next.
1221 bool ForgetAllSCEV;
1222
1223 Optional<unsigned> ProvidedCount;
1224 Optional<unsigned> ProvidedThreshold;
1225 Optional<bool> ProvidedAllowPartial;
1226 Optional<bool> ProvidedRuntime;
1227 Optional<bool> ProvidedUpperBound;
1228 Optional<bool> ProvidedAllowPeeling;
1229 Optional<bool> ProvidedAllowProfileBasedPeeling;
1230 Optional<unsigned> ProvidedFullUnrollMaxCount;
1231
LoopUnroll(int OptLevel=2,bool OnlyWhenForced=false,bool ForgetAllSCEV=false,Optional<unsigned> Threshold=None,Optional<unsigned> Count=None,Optional<bool> AllowPartial=None,Optional<bool> Runtime=None,Optional<bool> UpperBound=None,Optional<bool> AllowPeeling=None,Optional<bool> AllowProfileBasedPeeling=None,Optional<unsigned> ProvidedFullUnrollMaxCount=None)1232 LoopUnroll(int OptLevel = 2, bool OnlyWhenForced = false,
1233 bool ForgetAllSCEV = false, Optional<unsigned> Threshold = None,
1234 Optional<unsigned> Count = None,
1235 Optional<bool> AllowPartial = None, Optional<bool> Runtime = None,
1236 Optional<bool> UpperBound = None,
1237 Optional<bool> AllowPeeling = None,
1238 Optional<bool> AllowProfileBasedPeeling = None,
1239 Optional<unsigned> ProvidedFullUnrollMaxCount = None)
1240 : LoopPass(ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
1241 ForgetAllSCEV(ForgetAllSCEV), ProvidedCount(std::move(Count)),
1242 ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
1243 ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound),
1244 ProvidedAllowPeeling(AllowPeeling),
1245 ProvidedAllowProfileBasedPeeling(AllowProfileBasedPeeling),
1246 ProvidedFullUnrollMaxCount(ProvidedFullUnrollMaxCount) {
1247 initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
1248 }
1249
runOnLoop(Loop * L,LPPassManager & LPM)1250 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1251 if (skipLoop(L))
1252 return false;
1253
1254 Function &F = *L->getHeader()->getParent();
1255
1256 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1257 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1258 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1259 const TargetTransformInfo &TTI =
1260 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1261 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1262 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
1263 // pass. Function analyses need to be preserved across loop transformations
1264 // but ORE cannot be preserved (see comment before the pass definition).
1265 OptimizationRemarkEmitter ORE(&F);
1266 bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1267
1268 LoopUnrollResult Result = tryToUnrollLoop(
1269 L, DT, LI, SE, TTI, AC, ORE, nullptr, nullptr, PreserveLCSSA, OptLevel,
1270 OnlyWhenForced, ForgetAllSCEV, ProvidedCount, ProvidedThreshold,
1271 ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1272 ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling,
1273 ProvidedFullUnrollMaxCount);
1274
1275 if (Result == LoopUnrollResult::FullyUnrolled)
1276 LPM.markLoopAsDeleted(*L);
1277
1278 return Result != LoopUnrollResult::Unmodified;
1279 }
1280
1281 /// This transformation requires natural loop information & requires that
1282 /// loop preheaders be inserted into the CFG...
getAnalysisUsage(AnalysisUsage & AU) const1283 void getAnalysisUsage(AnalysisUsage &AU) const override {
1284 AU.addRequired<AssumptionCacheTracker>();
1285 AU.addRequired<TargetTransformInfoWrapperPass>();
1286 // FIXME: Loop passes are required to preserve domtree, and for now we just
1287 // recreate dom info if anything gets unrolled.
1288 getLoopAnalysisUsage(AU);
1289 }
1290 };
1291
1292 } // end anonymous namespace
1293
1294 char LoopUnroll::ID = 0;
1295
1296 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)1297 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1298 INITIALIZE_PASS_DEPENDENCY(LoopPass)
1299 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1300 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1301
1302 Pass *llvm::createLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
1303 bool ForgetAllSCEV, int Threshold, int Count,
1304 int AllowPartial, int Runtime, int UpperBound,
1305 int AllowPeeling) {
1306 // TODO: It would make more sense for this function to take the optionals
1307 // directly, but that's dangerous since it would silently break out of tree
1308 // callers.
1309 return new LoopUnroll(
1310 OptLevel, OnlyWhenForced, ForgetAllSCEV,
1311 Threshold == -1 ? None : Optional<unsigned>(Threshold),
1312 Count == -1 ? None : Optional<unsigned>(Count),
1313 AllowPartial == -1 ? None : Optional<bool>(AllowPartial),
1314 Runtime == -1 ? None : Optional<bool>(Runtime),
1315 UpperBound == -1 ? None : Optional<bool>(UpperBound),
1316 AllowPeeling == -1 ? None : Optional<bool>(AllowPeeling));
1317 }
1318
createSimpleLoopUnrollPass(int OptLevel,bool OnlyWhenForced,bool ForgetAllSCEV)1319 Pass *llvm::createSimpleLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
1320 bool ForgetAllSCEV) {
1321 return createLoopUnrollPass(OptLevel, OnlyWhenForced, ForgetAllSCEV, -1, -1,
1322 0, 0, 0, 1);
1323 }
1324
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & Updater)1325 PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
1326 LoopStandardAnalysisResults &AR,
1327 LPMUpdater &Updater) {
1328 // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
1329 // pass. Function analyses need to be preserved across loop transformations
1330 // but ORE cannot be preserved (see comment before the pass definition).
1331 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
1332
1333 // Keep track of the previous loop structure so we can identify new loops
1334 // created by unrolling.
1335 Loop *ParentL = L.getParentLoop();
1336 SmallPtrSet<Loop *, 4> OldLoops;
1337 if (ParentL)
1338 OldLoops.insert(ParentL->begin(), ParentL->end());
1339 else
1340 OldLoops.insert(AR.LI.begin(), AR.LI.end());
1341
1342 std::string LoopName = std::string(L.getName());
1343
1344 bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, ORE,
1345 /*BFI*/ nullptr, /*PSI*/ nullptr,
1346 /*PreserveLCSSA*/ true, OptLevel,
1347 OnlyWhenForced, ForgetSCEV, /*Count*/ None,
1348 /*Threshold*/ None, /*AllowPartial*/ false,
1349 /*Runtime*/ false, /*UpperBound*/ false,
1350 /*AllowPeeling*/ true,
1351 /*AllowProfileBasedPeeling*/ false,
1352 /*FullUnrollMaxCount*/ None) !=
1353 LoopUnrollResult::Unmodified;
1354 if (!Changed)
1355 return PreservedAnalyses::all();
1356
1357 // The parent must not be damaged by unrolling!
1358 #ifndef NDEBUG
1359 if (ParentL)
1360 ParentL->verifyLoop();
1361 #endif
1362
1363 // Unrolling can do several things to introduce new loops into a loop nest:
1364 // - Full unrolling clones child loops within the current loop but then
1365 // removes the current loop making all of the children appear to be new
1366 // sibling loops.
1367 //
1368 // When a new loop appears as a sibling loop after fully unrolling,
1369 // its nesting structure has fundamentally changed and we want to revisit
1370 // it to reflect that.
1371 //
1372 // When unrolling has removed the current loop, we need to tell the
1373 // infrastructure that it is gone.
1374 //
1375 // Finally, we support a debugging/testing mode where we revisit child loops
1376 // as well. These are not expected to require further optimizations as either
1377 // they or the loop they were cloned from have been directly visited already.
1378 // But the debugging mode allows us to check this assumption.
1379 bool IsCurrentLoopValid = false;
1380 SmallVector<Loop *, 4> SibLoops;
1381 if (ParentL)
1382 SibLoops.append(ParentL->begin(), ParentL->end());
1383 else
1384 SibLoops.append(AR.LI.begin(), AR.LI.end());
1385 erase_if(SibLoops, [&](Loop *SibLoop) {
1386 if (SibLoop == &L) {
1387 IsCurrentLoopValid = true;
1388 return true;
1389 }
1390
1391 // Otherwise erase the loop from the list if it was in the old loops.
1392 return OldLoops.contains(SibLoop);
1393 });
1394 Updater.addSiblingLoops(SibLoops);
1395
1396 if (!IsCurrentLoopValid) {
1397 Updater.markLoopAsDeleted(L, LoopName);
1398 } else {
1399 // We can only walk child loops if the current loop remained valid.
1400 if (UnrollRevisitChildLoops) {
1401 // Walk *all* of the child loops.
1402 SmallVector<Loop *, 4> ChildLoops(L.begin(), L.end());
1403 Updater.addChildLoops(ChildLoops);
1404 }
1405 }
1406
1407 return getLoopPassPreservedAnalyses();
1408 }
1409
run(Function & F,FunctionAnalysisManager & AM)1410 PreservedAnalyses LoopUnrollPass::run(Function &F,
1411 FunctionAnalysisManager &AM) {
1412 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1413 auto &LI = AM.getResult<LoopAnalysis>(F);
1414 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1415 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1416 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1417 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
1418
1419 LoopAnalysisManager *LAM = nullptr;
1420 if (auto *LAMProxy = AM.getCachedResult<LoopAnalysisManagerFunctionProxy>(F))
1421 LAM = &LAMProxy->getManager();
1422
1423 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1424 ProfileSummaryInfo *PSI =
1425 MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
1426 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
1427 &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
1428
1429 bool Changed = false;
1430
1431 // The unroller requires loops to be in simplified form, and also needs LCSSA.
1432 // Since simplification may add new inner loops, it has to run before the
1433 // legality and profitability checks. This means running the loop unroller
1434 // will simplify all loops, regardless of whether anything end up being
1435 // unrolled.
1436 for (auto &L : LI) {
1437 Changed |=
1438 simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);
1439 Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
1440 }
1441
1442 // Add the loop nests in the reverse order of LoopInfo. See method
1443 // declaration.
1444 SmallPriorityWorklist<Loop *, 4> Worklist;
1445 appendLoopsToWorklist(LI, Worklist);
1446
1447 while (!Worklist.empty()) {
1448 // Because the LoopInfo stores the loops in RPO, we walk the worklist
1449 // from back to front so that we work forward across the CFG, which
1450 // for unrolling is only needed to get optimization remarks emitted in
1451 // a forward order.
1452 Loop &L = *Worklist.pop_back_val();
1453 #ifndef NDEBUG
1454 Loop *ParentL = L.getParentLoop();
1455 #endif
1456
1457 // Check if the profile summary indicates that the profiled application
1458 // has a huge working set size, in which case we disable peeling to avoid
1459 // bloating it further.
1460 Optional<bool> LocalAllowPeeling = UnrollOpts.AllowPeeling;
1461 if (PSI && PSI->hasHugeWorkingSetSize())
1462 LocalAllowPeeling = false;
1463 std::string LoopName = std::string(L.getName());
1464 // The API here is quite complex to call and we allow to select some
1465 // flavors of unrolling during construction time (by setting UnrollOpts).
1466 LoopUnrollResult Result = tryToUnrollLoop(
1467 &L, DT, &LI, SE, TTI, AC, ORE, BFI, PSI,
1468 /*PreserveLCSSA*/ true, UnrollOpts.OptLevel, UnrollOpts.OnlyWhenForced,
1469 UnrollOpts.ForgetSCEV, /*Count*/ None,
1470 /*Threshold*/ None, UnrollOpts.AllowPartial, UnrollOpts.AllowRuntime,
1471 UnrollOpts.AllowUpperBound, LocalAllowPeeling,
1472 UnrollOpts.AllowProfileBasedPeeling, UnrollOpts.FullUnrollMaxCount);
1473 Changed |= Result != LoopUnrollResult::Unmodified;
1474
1475 // The parent must not be damaged by unrolling!
1476 #ifndef NDEBUG
1477 if (Result != LoopUnrollResult::Unmodified && ParentL)
1478 ParentL->verifyLoop();
1479 #endif
1480
1481 // Clear any cached analysis results for L if we removed it completely.
1482 if (LAM && Result == LoopUnrollResult::FullyUnrolled)
1483 LAM->clear(L, LoopName);
1484 }
1485
1486 if (!Changed)
1487 return PreservedAnalyses::all();
1488
1489 return getLoopPassPreservedAnalyses();
1490 }
1491