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/STLExtras.h"
19#include "llvm/ADT/SetVector.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/StringRef.h"
23#include "llvm/Analysis/AssumptionCache.h"
24#include "llvm/Analysis/BlockFrequencyInfo.h"
25#include "llvm/Analysis/CodeMetrics.h"
26#include "llvm/Analysis/LoopAnalysisManager.h"
27#include "llvm/Analysis/LoopInfo.h"
28#include "llvm/Analysis/LoopPass.h"
29#include "llvm/Analysis/LoopUnrollAnalyzer.h"
30#include "llvm/Analysis/MemorySSA.h"
31#include "llvm/Analysis/OptimizationRemarkEmitter.h"
32#include "llvm/Analysis/ProfileSummaryInfo.h"
33#include "llvm/Analysis/ScalarEvolution.h"
34#include "llvm/Analysis/TargetTransformInfo.h"
35#include "llvm/Analysis/UniformityAnalysis.h"
36#include "llvm/IR/BasicBlock.h"
37#include "llvm/IR/CFG.h"
38#include "llvm/IR/Constant.h"
39#include "llvm/IR/Constants.h"
40#include "llvm/IR/DiagnosticInfo.h"
41#include "llvm/IR/Dominators.h"
42#include "llvm/IR/Function.h"
43#include "llvm/IR/Instruction.h"
44#include "llvm/IR/Instructions.h"
45#include "llvm/IR/Metadata.h"
46#include "llvm/IR/PassManager.h"
47#include "llvm/InitializePasses.h"
48#include "llvm/Pass.h"
49#include "llvm/Support/Casting.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/Debug.h"
52#include "llvm/Support/ErrorHandling.h"
53#include "llvm/Support/raw_ostream.h"
54#include "llvm/Transforms/Scalar.h"
55#include "llvm/Transforms/Scalar/LoopPassManager.h"
56#include "llvm/Transforms/Utils.h"
57#include "llvm/Transforms/Utils/LoopPeel.h"
58#include "llvm/Transforms/Utils/LoopSimplify.h"
59#include "llvm/Transforms/Utils/LoopUtils.h"
60#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
61#include "llvm/Transforms/Utils/SizeOpts.h"
62#include "llvm/Transforms/Utils/UnrollLoop.h"
63#include <algorithm>
64#include <cassert>
65#include <cstdint>
66#include <limits>
67#include <optional>
68#include <string>
69#include <tuple>
70#include <utility>
71
72using namespace llvm;
73
74#define DEBUG_TYPE "loop-unroll"
75
76cl::opt<bool> llvm::ForgetSCEVInLoopUnroll(
77 "forget-scev-loop-unroll", cl::init(Val: 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
82static cl::opt<unsigned>
83 UnrollThreshold("unroll-threshold", cl::Hidden,
84 cl::desc("The cost threshold for loop unrolling"));
85
86static cl::opt<unsigned>
87 UnrollOptSizeThreshold(
88 "unroll-optsize-threshold", cl::init(Val: 0), cl::Hidden,
89 cl::desc("The cost threshold for loop unrolling when optimizing for "
90 "size"));
91
92static cl::opt<unsigned> UnrollPartialThreshold(
93 "unroll-partial-threshold", cl::Hidden,
94 cl::desc("The cost threshold for partial loop unrolling"));
95
96static cl::opt<unsigned> UnrollMaxPercentThresholdBoost(
97 "unroll-max-percent-threshold-boost", cl::init(Val: 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
105static cl::opt<unsigned> UnrollMaxIterationsCountToAnalyze(
106 "unroll-max-iteration-count-to-analyze", cl::init(Val: 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
110static 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
115static 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
120static 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
125static 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
130static 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
135static cl::opt<bool>
136 UnrollRuntime("unroll-runtime", cl::Hidden,
137 cl::desc("Unroll loops with run-time trip counts"));
138
139static cl::opt<unsigned> UnrollMaxUpperBound(
140 "unroll-max-upperbound", cl::init(Val: 8), cl::Hidden,
141 cl::desc(
142 "The max of trip count upper bound that is considered in unrolling"));
143
144static cl::opt<unsigned> PragmaUnrollThreshold(
145 "pragma-unroll-threshold", cl::init(Val: 16 * 1024), cl::Hidden,
146 cl::desc("Unrolled size limit for loops with unroll metadata "
147 "(full, enable, or count)."));
148
149static cl::opt<unsigned> FlatLoopTripCountThreshold(
150 "flat-loop-tripcount-threshold", cl::init(Val: 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
155static 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.
162static 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
168static cl::opt<unsigned> UnrollThresholdAggressive(
169 "unroll-threshold-aggressive", cl::init(Val: 300), cl::Hidden,
170 cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) "
171 "optimizations"));
172static cl::opt<unsigned>
173 UnrollThresholdDefault("unroll-threshold-default", cl::init(Val: 150),
174 cl::Hidden,
175 cl::desc("Default threshold (max size of unrolled "
176 "loop), used in all but O3 optimizations"));
177
178static cl::opt<unsigned> PragmaUnrollFullMaxIterations(
179 "pragma-unroll-full-max-iterations", cl::init(Val: 1'000'000), cl::Hidden,
180 cl::desc("Maximum allowed iterations to unroll under pragma unroll full."));
181
182/// A magic value for use with the Threshold parameter to indicate
183/// that the loop unroll should be performed regardless of how much
184/// code expansion would result.
185static const unsigned NoThreshold = std::numeric_limits<unsigned>::max();
186
187/// Gather the various unrolling parameters based on the defaults, compiler
188/// flags, TTI overrides and user specified parameters.
189TargetTransformInfo::UnrollingPreferences llvm::gatherUnrollingPreferences(
190 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
191 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
192 OptimizationRemarkEmitter &ORE, int OptLevel,
193 std::optional<unsigned> UserThreshold, std::optional<bool> UserAllowPartial,
194 std::optional<bool> UserRuntime, std::optional<bool> UserUpperBound,
195 std::optional<unsigned> UserFullUnrollMaxCount) {
196 TargetTransformInfo::UnrollingPreferences UP;
197
198 // Set up the defaults
199 UP.Threshold =
200 OptLevel > 2 ? UnrollThresholdAggressive : UnrollThresholdDefault;
201 UP.MaxPercentThresholdBoost = 400;
202 UP.OptSizeThreshold = UnrollOptSizeThreshold;
203 UP.PartialThreshold = 150;
204 UP.PartialOptSizeThreshold = UnrollOptSizeThreshold;
205 UP.DefaultUnrollRuntimeCount = 8;
206 UP.MaxCount = std::numeric_limits<unsigned>::max();
207 UP.MaxUpperBound = UnrollMaxUpperBound;
208 UP.FullUnrollMaxCount = std::numeric_limits<unsigned>::max();
209 UP.BEInsns = 2;
210 UP.Partial = false;
211 UP.Runtime = false;
212 UP.AllowRemainder = true;
213 UP.UnrollRemainder = false;
214 UP.AllowExpensiveTripCount = false;
215 UP.Force = false;
216 UP.UpperBound = false;
217 UP.UnrollAndJam = false;
218 UP.UnrollAndJamInnerLoopThreshold = 60;
219 UP.MaxIterationsCountToAnalyze = UnrollMaxIterationsCountToAnalyze;
220 UP.SCEVExpansionBudget = SCEVCheapExpansionBudget;
221 UP.RuntimeUnrollMultiExit = false;
222 UP.AddAdditionalAccumulators = false;
223
224 // Override with any target specific settings
225 TTI.getUnrollingPreferences(L, SE, UP, ORE: &ORE);
226
227 // Apply size attributes
228 bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
229 // Let unroll hints / pragmas take precedence over PGSO.
230 (hasUnrollTransformation(L) != TM_ForcedByUser &&
231 llvm::shouldOptimizeForSize(BB: L->getHeader(), PSI, BFI,
232 QueryType: PGSOQueryType::IRPass));
233 if (OptForSize) {
234 UP.Threshold = UP.OptSizeThreshold;
235 UP.PartialThreshold = UP.PartialOptSizeThreshold;
236 UP.MaxPercentThresholdBoost = 100;
237 }
238
239 // Apply any user values specified by cl::opt
240 if (UnrollThreshold.getNumOccurrences() > 0)
241 UP.Threshold = UnrollThreshold;
242 if (UnrollPartialThreshold.getNumOccurrences() > 0)
243 UP.PartialThreshold = UnrollPartialThreshold;
244 if (UnrollMaxPercentThresholdBoost.getNumOccurrences() > 0)
245 UP.MaxPercentThresholdBoost = UnrollMaxPercentThresholdBoost;
246 if (UnrollMaxCount.getNumOccurrences() > 0)
247 UP.MaxCount = UnrollMaxCount;
248 if (UnrollMaxUpperBound.getNumOccurrences() > 0)
249 UP.MaxUpperBound = UnrollMaxUpperBound;
250 if (UnrollFullMaxCount.getNumOccurrences() > 0)
251 UP.FullUnrollMaxCount = UnrollFullMaxCount;
252 if (UnrollAllowPartial.getNumOccurrences() > 0)
253 UP.Partial = UnrollAllowPartial;
254 if (UnrollAllowRemainder.getNumOccurrences() > 0)
255 UP.AllowRemainder = UnrollAllowRemainder;
256 if (UnrollRuntime.getNumOccurrences() > 0)
257 UP.Runtime = UnrollRuntime;
258 if (UnrollMaxUpperBound == 0)
259 UP.UpperBound = false;
260 if (UnrollUnrollRemainder.getNumOccurrences() > 0)
261 UP.UnrollRemainder = UnrollUnrollRemainder;
262 if (UnrollMaxIterationsCountToAnalyze.getNumOccurrences() > 0)
263 UP.MaxIterationsCountToAnalyze = UnrollMaxIterationsCountToAnalyze;
264
265 // Apply user values provided by argument
266 if (UserThreshold) {
267 UP.Threshold = *UserThreshold;
268 UP.PartialThreshold = *UserThreshold;
269 }
270 if (UserAllowPartial)
271 UP.Partial = *UserAllowPartial;
272 if (UserRuntime)
273 UP.Runtime = *UserRuntime;
274 if (UserUpperBound)
275 UP.UpperBound = *UserUpperBound;
276 if (UserFullUnrollMaxCount)
277 UP.FullUnrollMaxCount = *UserFullUnrollMaxCount;
278
279 return UP;
280}
281
282namespace {
283
284/// A struct to densely store the state of an instruction after unrolling at
285/// each iteration.
286///
287/// This is designed to work like a tuple of <Instruction *, int> for the
288/// purposes of hashing and lookup, but to be able to associate two boolean
289/// states with each key.
290struct UnrolledInstState {
291 Instruction *I;
292 int Iteration : 30;
293 unsigned IsFree : 1;
294 unsigned IsCounted : 1;
295};
296
297/// Hashing and equality testing for a set of the instruction states.
298struct UnrolledInstStateKeyInfo {
299 using PtrInfo = DenseMapInfo<Instruction *>;
300 using PairInfo = DenseMapInfo<std::pair<Instruction *, int>>;
301
302 static inline unsigned getHashValue(const UnrolledInstState &S) {
303 return PairInfo::getHashValue(PairVal: {S.I, S.Iteration});
304 }
305
306 static inline bool isEqual(const UnrolledInstState &LHS,
307 const UnrolledInstState &RHS) {
308 return PairInfo::isEqual(LHS: {LHS.I, LHS.Iteration}, RHS: {RHS.I, RHS.Iteration});
309 }
310};
311
312struct 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 std::nullopt.
336static std::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 LLVM_DEBUG(dbgs().indent(3)
352 << "Not analyzing loop cost: not an innermost loop.\n");
353 return std::nullopt;
354 }
355
356 // Don't simulate loops with a big or unknown tripcount
357 if (!TripCount || TripCount > MaxIterationsCountToAnalyze) {
358 LLVM_DEBUG(dbgs().indent(3)
359 << "Not analyzing loop cost: trip count "
360 << (TripCount ? "too large" : "unknown") << ".\n");
361 return std::nullopt;
362 }
363
364 SmallSetVector<BasicBlock *, 16> BBWorklist;
365 SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
366 DenseMap<Value *, Value *> SimplifiedValues;
367 SmallVector<std::pair<Value *, Value *>, 4> SimplifiedInputValues;
368
369 // The estimated cost of the unrolled form of the loop. We try to estimate
370 // this by simplifying as much as we can while computing the estimate.
371 InstructionCost UnrolledCost = 0;
372
373 // We also track the estimated dynamic (that is, actually executed) cost in
374 // the rolled form. This helps identify cases when the savings from unrolling
375 // aren't just exposing dead control flows, but actual reduced dynamic
376 // instructions due to the simplifications which we expect to occur after
377 // unrolling.
378 InstructionCost RolledDynamicCost = 0;
379
380 // We track the simplification of each instruction in each iteration. We use
381 // this to recursively merge costs into the unrolled cost on-demand so that
382 // we don't count the cost of any dead code. This is essentially a map from
383 // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
384 DenseSet<UnrolledInstState, UnrolledInstStateKeyInfo> InstCostMap;
385
386 // A small worklist used to accumulate cost of instructions from each
387 // observable and reached root in the loop.
388 SmallVector<Instruction *, 16> CostWorklist;
389
390 // PHI-used worklist used between iterations while accumulating cost.
391 SmallVector<Instruction *, 4> PHIUsedList;
392
393 // Helper function to accumulate cost for instructions in the loop.
394 auto AddCostRecursively = [&](Instruction &RootI, int Iteration) {
395 assert(Iteration >= 0 && "Cannot have a negative iteration!");
396 assert(CostWorklist.empty() && "Must start with an empty cost list");
397 assert(PHIUsedList.empty() && "Must start with an empty phi used list");
398 CostWorklist.push_back(Elt: &RootI);
399 TargetTransformInfo::TargetCostKind CostKind =
400 RootI.getFunction()->hasMinSize() ?
401 TargetTransformInfo::TCK_CodeSize :
402 TargetTransformInfo::TCK_SizeAndLatency;
403 for (;; --Iteration) {
404 do {
405 Instruction *I = CostWorklist.pop_back_val();
406
407 // InstCostMap only uses I and Iteration as a key, the other two values
408 // don't matter here.
409 auto CostIter = InstCostMap.find(V: {.I: I, .Iteration: Iteration, .IsFree: 0, .IsCounted: 0});
410 if (CostIter == InstCostMap.end())
411 // If an input to a PHI node comes from a dead path through the loop
412 // we may have no cost data for it here. What that actually means is
413 // that it is free.
414 continue;
415 auto &Cost = *CostIter;
416 if (Cost.IsCounted)
417 // Already counted this instruction.
418 continue;
419
420 // Mark that we are counting the cost of this instruction now.
421 Cost.IsCounted = true;
422
423 // If this is a PHI node in the loop header, just add it to the PHI set.
424 if (auto *PhiI = dyn_cast<PHINode>(Val: I))
425 if (PhiI->getParent() == L->getHeader()) {
426 assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
427 "inherently simplify during unrolling.");
428 if (Iteration == 0)
429 continue;
430
431 // Push the incoming value from the backedge into the PHI used list
432 // if it is an in-loop instruction. We'll use this to populate the
433 // cost worklist for the next iteration (as we count backwards).
434 if (auto *OpI = dyn_cast<Instruction>(
435 Val: PhiI->getIncomingValueForBlock(BB: L->getLoopLatch())))
436 if (L->contains(Inst: OpI))
437 PHIUsedList.push_back(Elt: OpI);
438 continue;
439 }
440
441 // First accumulate the cost of this instruction.
442 if (!Cost.IsFree) {
443 // Consider simplified operands in instruction cost.
444 SmallVector<Value *, 4> Operands;
445 transform(Range: I->operands(), d_first: std::back_inserter(x&: Operands),
446 F: [&](Value *Op) {
447 if (auto Res = SimplifiedValues.lookup(Val: Op))
448 return Res;
449 return Op;
450 });
451 UnrolledCost += TTI.getInstructionCost(U: I, Operands, CostKind);
452 LLVM_DEBUG(dbgs().indent(3)
453 << "Adding cost of instruction (iteration " << Iteration
454 << "): ");
455 LLVM_DEBUG(I->dump());
456 }
457
458 // We must count the cost of every operand which is not free,
459 // recursively. If we reach a loop PHI node, simply add it to the set
460 // to be considered on the next iteration (backwards!).
461 for (Value *Op : I->operands()) {
462 // Check whether this operand is free due to being a constant or
463 // outside the loop.
464 auto *OpI = dyn_cast<Instruction>(Val: Op);
465 if (!OpI || !L->contains(Inst: OpI))
466 continue;
467
468 // Otherwise accumulate its cost.
469 CostWorklist.push_back(Elt: OpI);
470 }
471 } while (!CostWorklist.empty());
472
473 if (PHIUsedList.empty())
474 // We've exhausted the search.
475 break;
476
477 assert(Iteration > 0 &&
478 "Cannot track PHI-used values past the first iteration!");
479 CostWorklist.append(in_start: PHIUsedList.begin(), in_end: PHIUsedList.end());
480 PHIUsedList.clear();
481 }
482 };
483
484 // Ensure that we don't violate the loop structure invariants relied on by
485 // this analysis.
486 assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
487 assert(L->isLCSSAForm(DT) &&
488 "Must have loops in LCSSA form to track live-out values.");
489
490 LLVM_DEBUG(dbgs().indent(3)
491 << "Starting LoopUnroll profitability analysis...\n");
492
493 TargetTransformInfo::TargetCostKind CostKind =
494 L->getHeader()->getParent()->hasMinSize() ?
495 TargetTransformInfo::TCK_CodeSize : TargetTransformInfo::TCK_SizeAndLatency;
496 // Simulate execution of each iteration of the loop counting instructions,
497 // which would be simplified.
498 // Since the same load will take different values on different iterations,
499 // we literally have to go through all loop's iterations.
500 for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
501 LLVM_DEBUG(dbgs().indent(3) << "Analyzing iteration " << Iteration << "\n");
502
503 // Prepare for the iteration by collecting any simplified entry or backedge
504 // inputs.
505 for (Instruction &I : *L->getHeader()) {
506 auto *PHI = dyn_cast<PHINode>(Val: &I);
507 if (!PHI)
508 break;
509
510 // The loop header PHI nodes must have exactly two input: one from the
511 // loop preheader and one from the loop latch.
512 assert(
513 PHI->getNumIncomingValues() == 2 &&
514 "Must have an incoming value only for the preheader and the latch.");
515
516 Value *V = PHI->getIncomingValueForBlock(
517 BB: Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
518 if (Iteration != 0 && SimplifiedValues.count(Val: V))
519 V = SimplifiedValues.lookup(Val: V);
520 SimplifiedInputValues.push_back(Elt: {PHI, V});
521 }
522
523 // Now clear and re-populate the map for the next iteration.
524 SimplifiedValues.clear();
525 while (!SimplifiedInputValues.empty())
526 SimplifiedValues.insert(KV: SimplifiedInputValues.pop_back_val());
527
528 UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
529
530 BBWorklist.clear();
531 BBWorklist.insert(X: L->getHeader());
532 // Note that we *must not* cache the size, this loop grows the worklist.
533 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
534 BasicBlock *BB = BBWorklist[Idx];
535
536 // Visit all instructions in the given basic block and try to simplify
537 // it. We don't change the actual IR, just count optimization
538 // opportunities.
539 for (Instruction &I : *BB) {
540 // These won't get into the final code - don't even try calculating the
541 // cost for them.
542 if (EphValues.count(Ptr: &I))
543 continue;
544
545 // Track this instruction's expected baseline cost when executing the
546 // rolled loop form.
547 RolledDynamicCost += TTI.getInstructionCost(U: &I, CostKind);
548
549 // Visit the instruction to analyze its loop cost after unrolling,
550 // and if the visitor returns true, mark the instruction as free after
551 // unrolling and continue.
552 bool IsFree = Analyzer.visit(I);
553 bool Inserted = InstCostMap.insert(V: {.I: &I, .Iteration: (int)Iteration,
554 .IsFree: (unsigned)IsFree,
555 /*IsCounted*/ false}).second;
556 (void)Inserted;
557 assert(Inserted && "Cannot have a state for an unvisited instruction!");
558
559 if (IsFree)
560 continue;
561
562 // Can't properly model a cost of a call.
563 // FIXME: With a proper cost model we should be able to do it.
564 if (auto *CI = dyn_cast<CallInst>(Val: &I)) {
565 const Function *Callee = CI->getCalledFunction();
566 if (!Callee || TTI.isLoweredToCall(F: Callee)) {
567 LLVM_DEBUG(dbgs().indent(3)
568 << "Can't analyze cost of loop with call\n");
569 return std::nullopt;
570 }
571 }
572
573 // If the instruction might have a side-effect recursively account for
574 // the cost of it and all the instructions leading up to it.
575 if (I.mayHaveSideEffects())
576 AddCostRecursively(I, Iteration);
577
578 // If unrolled body turns out to be too big, bail out.
579 if (UnrolledCost > MaxUnrolledLoopSize) {
580 LLVM_DEBUG({
581 dbgs().indent(3) << "Exceeded threshold.. exiting.\n";
582 dbgs().indent(3)
583 << "UnrolledCost: " << UnrolledCost
584 << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize << "\n";
585 });
586 return std::nullopt;
587 }
588 }
589
590 Instruction *TI = BB->getTerminator();
591
592 auto getSimplifiedConstant = [&](Value *V) -> Constant * {
593 if (SimplifiedValues.count(Val: V))
594 V = SimplifiedValues.lookup(Val: V);
595 return dyn_cast<Constant>(Val: V);
596 };
597
598 // Add in the live successors by first checking whether we have terminator
599 // that may be simplified based on the values simplified by this call.
600 BasicBlock *KnownSucc = nullptr;
601 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: TI)) {
602 if (auto *SimpleCond = getSimplifiedConstant(BI->getCondition())) {
603 // Just take the first successor if condition is undef
604 if (isa<UndefValue>(Val: SimpleCond))
605 KnownSucc = BI->getSuccessor(i: 0);
606 else if (ConstantInt *SimpleCondVal =
607 dyn_cast<ConstantInt>(Val: SimpleCond))
608 KnownSucc = BI->getSuccessor(i: SimpleCondVal->isZero() ? 1 : 0);
609 }
610 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: TI)) {
611 if (auto *SimpleCond = getSimplifiedConstant(SI->getCondition())) {
612 // Just take the first successor if condition is undef
613 if (isa<UndefValue>(Val: SimpleCond))
614 KnownSucc = SI->getSuccessor(idx: 0);
615 else if (ConstantInt *SimpleCondVal =
616 dyn_cast<ConstantInt>(Val: SimpleCond))
617 KnownSucc = SI->findCaseValue(C: SimpleCondVal)->getCaseSuccessor();
618 }
619 }
620 if (KnownSucc) {
621 if (L->contains(BB: KnownSucc))
622 BBWorklist.insert(X: KnownSucc);
623 else
624 ExitWorklist.insert(X: {BB, KnownSucc});
625 continue;
626 }
627
628 // Add BB's successors to the worklist.
629 for (BasicBlock *Succ : successors(BB))
630 if (L->contains(BB: Succ))
631 BBWorklist.insert(X: Succ);
632 else
633 ExitWorklist.insert(X: {BB, Succ});
634 AddCostRecursively(*TI, Iteration);
635 }
636
637 // If we found no optimization opportunities on the first iteration, we
638 // won't find them on later ones too.
639 if (UnrolledCost == RolledDynamicCost) {
640 LLVM_DEBUG({
641 dbgs().indent(3) << "No opportunities found.. exiting.\n";
642 dbgs().indent(3) << "UnrolledCost: " << UnrolledCost << "\n";
643 });
644 return std::nullopt;
645 }
646 }
647
648 while (!ExitWorklist.empty()) {
649 BasicBlock *ExitingBB, *ExitBB;
650 std::tie(args&: ExitingBB, args&: ExitBB) = ExitWorklist.pop_back_val();
651
652 for (Instruction &I : *ExitBB) {
653 auto *PN = dyn_cast<PHINode>(Val: &I);
654 if (!PN)
655 break;
656
657 Value *Op = PN->getIncomingValueForBlock(BB: ExitingBB);
658 if (auto *OpI = dyn_cast<Instruction>(Val: Op))
659 if (L->contains(Inst: OpI))
660 AddCostRecursively(*OpI, TripCount - 1);
661 }
662 }
663
664 assert(UnrolledCost.isValid() && RolledDynamicCost.isValid() &&
665 "All instructions must have a valid cost, whether the "
666 "loop is rolled or unrolled.");
667
668 LLVM_DEBUG({
669 dbgs().indent(3) << "Analysis finished:\n";
670 dbgs().indent(3) << "UnrolledCost: " << UnrolledCost
671 << ", RolledDynamicCost: " << RolledDynamicCost << "\n";
672 });
673 return {{.UnrolledCost: unsigned(UnrolledCost.getValue()),
674 .RolledDynamicCost: unsigned(RolledDynamicCost.getValue())}};
675}
676
677UnrollCostEstimator::UnrollCostEstimator(
678 const Loop *L, const TargetTransformInfo &TTI,
679 const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns,
680 bool PrepareForLTO, bool TripCountIsUniform) {
681 CodeMetrics Metrics;
682 for (BasicBlock *BB : L->blocks())
683 Metrics.analyzeBasicBlock(BB, TTI, EphValues, PrepareForLTO, L);
684 NumInlineCandidates = Metrics.NumInlineCandidates;
685 NotDuplicatable = Metrics.notDuplicatable;
686 Convergence = Metrics.Convergence;
687 LoopSize = Metrics.NumInsts;
688 // Convergent operations make the remainder prelude unsafe by adding a
689 // control-flow dependency, unless the trip count is uniform per
690 // UniformityInfo, in which case all paths agree and the remainder is safe.
691 ConvergenceAllowsRuntime =
692 (Metrics.Convergence != ConvergenceKind::Uncontrolled &&
693 !getLoopConvergenceHeart(TheLoop: L)) ||
694 TripCountIsUniform;
695
696 // Don't allow an estimate of size zero. This would allows unrolling of loops
697 // with huge iteration counts, which is a compile time problem even if it's
698 // not a problem for code quality. Also, the code using this size may assume
699 // that each loop has at least three instructions (likely a conditional
700 // branch, a comparison feeding that branch, and some kind of loop increment
701 // feeding that comparison instruction).
702 if (LoopSize.isValid() && LoopSize < BEInsns + 1)
703 // This is an open coded max() on InstructionCost
704 LoopSize = BEInsns + 1;
705}
706
707bool UnrollCostEstimator::canUnroll(OptimizationRemarkEmitter *ORE,
708 const Loop *L) const {
709 auto ReportCannotUnroll = [&](StringRef Reason) {
710 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: " << Reason << ".\n");
711 if (ORE && L)
712 ORE->emit(RemarkBuilder: [&]() {
713 return OptimizationRemarkMissed(DEBUG_TYPE, "CannotUnrollLoop",
714 L->getStartLoc(), L->getHeader())
715 << "unable to unroll loop: " << Reason;
716 });
717 };
718
719 if (Convergence == ConvergenceKind::ExtendedLoop) {
720 ReportCannotUnroll("contains convergent operations");
721 return false;
722 }
723 if (!LoopSize.isValid()) {
724 ReportCannotUnroll("loop size could not be computed");
725 return false;
726 }
727 if (NotDuplicatable) {
728 ReportCannotUnroll("contains non-duplicatable instructions");
729 return false;
730 }
731 return true;
732}
733
734uint64_t UnrollCostEstimator::getUnrolledLoopSize(
735 const TargetTransformInfo::UnrollingPreferences &UP, unsigned Count) const {
736 unsigned LS = LoopSize.getValue();
737 assert(LS >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
738 return static_cast<uint64_t>(LS - UP.BEInsns) * Count + UP.BEInsns;
739}
740
741// Returns true if the loop has an unroll(full) pragma.
742static bool hasUnrollFullPragma(const Loop *L) {
743 return getUnrollMetadataForLoop(L, Name: "llvm.loop.unroll.full");
744}
745
746// Returns true if the loop has an unroll(enable) pragma. This metadata is used
747// for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
748static bool hasUnrollEnablePragma(const Loop *L) {
749 return getUnrollMetadataForLoop(L, Name: "llvm.loop.unroll.enable");
750}
751
752// Returns true if the loop has a runtime unroll(disable) pragma.
753static bool hasRuntimeUnrollDisablePragma(const Loop *L) {
754 return getUnrollMetadataForLoop(L, Name: "llvm.loop.unroll.runtime.disable");
755}
756
757/// Returns true if the SCEV expression is uniform, i.e., all threads in a
758/// convergent execution agree on its value. Recursively checks operands.
759/// Returns false if the SCEV could not be computed.
760static bool isSCEVUniform(const SCEV *S, UniformityInfo &UI) {
761 if (isa<SCEVCouldNotCompute>(Val: S))
762 return false;
763 if (isa<SCEVConstant>(Val: S))
764 return true;
765 if (auto *U = dyn_cast<SCEVUnknown>(Val: S))
766 return UI.isUniformAtDef(V: U->getValue());
767 for (const SCEV *Op : S->operands()) {
768 if (!isSCEVUniform(S: Op, UI))
769 return false;
770 }
771 return true;
772}
773
774// If loop has an unroll_count pragma return the (necessarily
775// positive) value from the pragma. Otherwise return 0.
776static unsigned unrollCountPragmaValue(const Loop *L) {
777 MDNode *MD = getUnrollMetadataForLoop(L, Name: "llvm.loop.unroll.count");
778 if (MD) {
779 assert(MD->getNumOperands() == 2 &&
780 "Unroll count hint metadata should have two operands.");
781 unsigned Count =
782 mdconst::extract<ConstantInt>(MD: MD->getOperand(I: 1))->getZExtValue();
783 assert(Count >= 1 && "Unroll count must be positive.");
784 return Count;
785 }
786 return 0;
787}
788
789UnrollPragmaInfo::UnrollPragmaInfo(const Loop *L)
790 : UserUnrollCount(UnrollCount.getNumOccurrences() > 0),
791 PragmaFullUnroll(hasUnrollFullPragma(L)),
792 PragmaCount(unrollCountPragmaValue(L)),
793 PragmaEnableUnroll(hasUnrollEnablePragma(L)),
794 PragmaRuntimeUnrollDisable(hasRuntimeUnrollDisablePragma(L)),
795 ExplicitUnroll(PragmaCount > 0 || PragmaFullUnroll ||
796 PragmaEnableUnroll || UserUnrollCount) {}
797
798// Computes the boosting factor for complete unrolling.
799// If fully unrolling the loop would save a lot of RolledDynamicCost, it would
800// be beneficial to fully unroll the loop even if unrolledcost is large. We
801// use (RolledDynamicCost / UnrolledCost) to model the unroll benefits to adjust
802// the unroll threshold.
803static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost,
804 unsigned MaxPercentThresholdBoost) {
805 if (Cost.RolledDynamicCost >= std::numeric_limits<unsigned>::max() / 100)
806 return 100;
807 else if (Cost.UnrolledCost != 0)
808 // The boosting factor is RolledDynamicCost / UnrolledCost
809 return std::min(a: 100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
810 b: MaxPercentThresholdBoost);
811 else
812 return MaxPercentThresholdBoost;
813}
814
815static std::optional<unsigned>
816shouldPragmaUnroll(Loop *L, const UnrollPragmaInfo &PInfo,
817 const unsigned TripMultiple, const unsigned TripCount,
818 unsigned MaxTripCount, const UnrollCostEstimator UCE,
819 const TargetTransformInfo::UnrollingPreferences &UP,
820 OptimizationRemarkEmitter *ORE) {
821
822 // Using unroll pragma
823 // 1st priority is unroll count set by "unroll-count" option.
824
825 if (PInfo.UserUnrollCount) {
826 if (UP.AllowRemainder &&
827 UCE.getUnrolledLoopSize(UP, Count: (unsigned)UnrollCount) < UP.Threshold) {
828 LLVM_DEBUG(dbgs().indent(2) << "Unrolling with user-specified count: "
829 << UnrollCount << ".\n");
830 return (unsigned)UnrollCount;
831 }
832 LLVM_DEBUG(dbgs().indent(2)
833 << "Not unrolling with user count " << UnrollCount << ": "
834 << (UP.AllowRemainder ? "exceeds threshold"
835 : "remainder not allowed")
836 << ".\n");
837 }
838
839 // 2nd priority is unroll count set by pragma.
840 if (PInfo.PragmaCount > 0) {
841 if ((UP.AllowRemainder || (TripMultiple % PInfo.PragmaCount == 0))) {
842 LLVM_DEBUG(dbgs().indent(2) << "Unrolling with pragma count: "
843 << PInfo.PragmaCount << ".\n");
844 return PInfo.PragmaCount;
845 }
846 LLVM_DEBUG(dbgs().indent(2)
847 << "Not unrolling with pragma count " << PInfo.PragmaCount
848 << ": remainder not allowed, count does not divide trip "
849 << "multiple " << TripMultiple << ".\n");
850 ORE->emit(RemarkBuilder: [&]() {
851 return OptimizationRemarkAnalysis(DEBUG_TYPE, "PragmaUnrollCountRejected",
852 L->getStartLoc(), L->getHeader())
853 << "may be unable to unroll loop with count "
854 << ore::NV("PragmaCount", PInfo.PragmaCount)
855 << ": remainder loop is not allowed and count does not divide "
856 "trip multiple "
857 << ore::NV("TripMultiple", TripMultiple);
858 });
859 }
860
861 if (PInfo.PragmaFullUnroll) {
862 if (TripCount != 0) {
863 // Certain cases with UBSAN can cause trip count to be calculated as
864 // INT_MAX, Block full unrolling at a reasonable limit so that the
865 // compiler doesn't hang trying to unroll the loop. See PR77842
866 if (TripCount > PragmaUnrollFullMaxIterations) {
867 LLVM_DEBUG(dbgs().indent(2)
868 << "Won't unroll; trip count is too large.\n");
869 ORE->emit(RemarkBuilder: [&]() {
870 return OptimizationRemarkAnalysis(DEBUG_TYPE,
871 "PragmaFullUnrollTripCountTooLarge",
872 L->getStartLoc(), L->getHeader())
873 << "may be unable to fully unroll loop: trip count "
874 << ore::NV("TripCount", TripCount) << " exceeds limit "
875 << ore::NV("Limit", PragmaUnrollFullMaxIterations);
876 });
877 return std::nullopt;
878 }
879
880 LLVM_DEBUG(dbgs().indent(2)
881 << "Fully unrolling with trip count: " << TripCount << ".\n");
882 return TripCount;
883 }
884 LLVM_DEBUG(dbgs().indent(2)
885 << "Not fully unrolling: unknown trip count.\n");
886 ORE->emit(RemarkBuilder: [&]() {
887 return OptimizationRemarkAnalysis(DEBUG_TYPE,
888 "PragmaFullUnrollUnknownTripCount",
889 L->getStartLoc(), L->getHeader())
890 << "may be unable to fully unroll loop: trip count is unknown";
891 });
892 }
893
894 if (PInfo.PragmaEnableUnroll && !TripCount && MaxTripCount &&
895 MaxTripCount <= UP.MaxUpperBound) {
896 LLVM_DEBUG(dbgs().indent(2)
897 << "Unrolling with max trip count: " << MaxTripCount << ".\n");
898 return MaxTripCount;
899 }
900
901 return std::nullopt;
902}
903
904static std::optional<unsigned> shouldFullUnroll(
905 Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT,
906 ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
907 const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE,
908 const TargetTransformInfo::UnrollingPreferences &UP) {
909 assert(FullUnrollTripCount && "should be non-zero!");
910
911 if (FullUnrollTripCount > UP.FullUnrollMaxCount) {
912 LLVM_DEBUG(dbgs().indent(2)
913 << "Not unrolling: trip count " << FullUnrollTripCount
914 << " exceeds max count " << UP.FullUnrollMaxCount << ".\n");
915 return std::nullopt;
916 }
917
918 // When computing the unrolled size, note that BEInsns are not replicated
919 // like the rest of the loop body.
920 uint64_t UnrolledSize = UCE.getUnrolledLoopSize(UP, Count: FullUnrollTripCount);
921 if (UnrolledSize < UP.Threshold) {
922 LLVM_DEBUG(dbgs().indent(2) << "Unrolling: size " << UnrolledSize
923 << " < threshold " << UP.Threshold << ".\n");
924 return FullUnrollTripCount;
925 }
926
927 LLVM_DEBUG(dbgs().indent(2)
928 << "Unrolled size " << UnrolledSize << " exceeds threshold "
929 << UP.Threshold << "; checking for cost benefit.\n");
930
931 // The loop isn't that small, but we still can fully unroll it if that
932 // helps to remove a significant number of instructions.
933 // To check that, run additional analysis on the loop.
934 if (std::optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
935 L, TripCount: FullUnrollTripCount, DT, SE, EphValues, TTI,
936 MaxUnrolledLoopSize: UP.Threshold * UP.MaxPercentThresholdBoost / 100,
937 MaxIterationsCountToAnalyze: UP.MaxIterationsCountToAnalyze)) {
938 unsigned Boost =
939 getFullUnrollBoostingFactor(Cost: *Cost, MaxPercentThresholdBoost: UP.MaxPercentThresholdBoost);
940 unsigned BoostedThreshold = UP.Threshold * Boost / 100;
941 if (Cost->UnrolledCost < BoostedThreshold) {
942 LLVM_DEBUG(dbgs().indent(2) << "Profitable after cost analysis.\n");
943 return FullUnrollTripCount;
944 }
945 LLVM_DEBUG(dbgs().indent(2)
946 << "Not unrolling: cost " << Cost->UnrolledCost
947 << " >= boosted threshold " << BoostedThreshold << ".\n");
948 }
949
950 return std::nullopt;
951}
952
953static std::optional<unsigned>
954shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount,
955 const UnrollCostEstimator UCE,
956 const TargetTransformInfo::UnrollingPreferences &UP) {
957
958 if (!TripCount)
959 return std::nullopt;
960
961 if (!UP.Partial) {
962 LLVM_DEBUG(dbgs().indent(2) << "Will not try to unroll partially because "
963 << "-unroll-allow-partial not given\n");
964 return 0;
965 }
966 unsigned Count = TripCount;
967 if (UP.PartialThreshold != NoThreshold) {
968 // Reduce unroll count to be modulo of TripCount for partial unrolling.
969 if (UCE.getUnrolledLoopSize(UP, Count) > UP.PartialThreshold) {
970 unsigned NewCount =
971 (std::max(a: UP.PartialThreshold, b: UP.BEInsns + 1) - UP.BEInsns) /
972 (LoopSize - UP.BEInsns);
973 LLVM_DEBUG(dbgs().indent(2)
974 << "Unrolled size exceeds threshold; reducing count "
975 << "from " << Count << " to " << NewCount << ".\n");
976 Count = NewCount;
977 }
978 if (Count > UP.MaxCount)
979 Count = UP.MaxCount;
980 while (Count != 0 && TripCount % Count != 0)
981 Count--;
982 if (UP.AllowRemainder && Count <= 1) {
983 // If there is no Count that is modulo of TripCount, set Count to
984 // largest power-of-two factor that satisfies the threshold limit.
985 // As we'll create fixup loop, do the type of unrolling only if
986 // remainder loop is allowed.
987 // Note: DefaultUnrollRuntimeCount is used as a reasonable starting point
988 // even though this is partial unrolling (not runtime unrolling).
989 Count = UP.DefaultUnrollRuntimeCount;
990 while (Count != 0 &&
991 UCE.getUnrolledLoopSize(UP, Count) > UP.PartialThreshold)
992 Count >>= 1;
993 }
994 if (Count < 2) {
995 LLVM_DEBUG(dbgs().indent(2)
996 << "Will not partially unroll: no profitable count.\n");
997 Count = 0;
998 }
999 } else {
1000 Count = TripCount;
1001 }
1002 if (Count > UP.MaxCount)
1003 Count = UP.MaxCount;
1004
1005 LLVM_DEBUG(dbgs().indent(2)
1006 << "Partially unrolling with count: " << Count << "\n");
1007
1008 return Count;
1009}
1010// Calculates and returns the unroll count, using metadata and command-line
1011// options that are specific to the LoopUnroll pass (which, for instance, are
1012// irrelevant for the LoopUnrollAndJam pass).
1013// FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
1014// many LoopUnroll-specific options. The shared functionality should be
1015// refactored into it own function.
1016unsigned llvm::computeUnrollCount(
1017 Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
1018 AssumptionCache *AC, ScalarEvolution &SE,
1019 const SmallPtrSetImpl<const Value *> &EphValues,
1020 OptimizationRemarkEmitter *ORE, const unsigned TripCount,
1021 const unsigned MaxTripCount, const bool MaxOrZero,
1022 const unsigned TripMultiple, const UnrollCostEstimator &UCE,
1023 TargetTransformInfo::UnrollingPreferences &UP,
1024 TargetTransformInfo::PeelingPreferences &PP) {
1025
1026 unsigned LoopSize = UCE.getRolledLoopSize();
1027
1028 LLVM_DEBUG(dbgs().indent(1) << "Computing unroll count: TripCount="
1029 << TripCount << ", MaxTripCount=" << MaxTripCount
1030 << (MaxOrZero ? " (MaxOrZero)" : "")
1031 << ", TripMultiple=" << TripMultiple << "\n");
1032
1033 UnrollPragmaInfo PInfo(L);
1034 LLVM_DEBUG({
1035 if (PInfo.ExplicitUnroll) {
1036 dbgs().indent(1) << "Explicit unroll requested:";
1037 if (PInfo.UserUnrollCount)
1038 dbgs() << " user-count";
1039 if (PInfo.PragmaFullUnroll)
1040 dbgs() << " pragma-full";
1041 if (PInfo.PragmaCount > 0)
1042 dbgs() << " pragma-count(" << PInfo.PragmaCount << ")";
1043 if (PInfo.PragmaEnableUnroll)
1044 dbgs() << " pragma-enable";
1045 dbgs() << "\n";
1046 }
1047 });
1048
1049 // Use an explicit peel count that has been specified for testing. In this
1050 // case it's not permitted to also specify an explicit unroll count.
1051 if (PP.PeelCount) {
1052 if (UnrollCount.getNumOccurrences() > 0) {
1053 reportFatalUsageError(reason: "Cannot specify both explicit peel count and "
1054 "explicit unroll count");
1055 }
1056 LLVM_DEBUG(dbgs().indent(2)
1057 << "Using explicit peel count: " << PP.PeelCount << ".\n");
1058 UP.Runtime = false;
1059 return 1;
1060 }
1061
1062 // If a user provided an explicit unroll pragma (with or without count),
1063 // enable runtime unrolling and override expensive trip count checks.
1064 if (PInfo.PragmaEnableUnroll || PInfo.PragmaCount > 0) {
1065 UP.AllowExpensiveTripCount = true;
1066 UP.Runtime = true;
1067 }
1068
1069 // Check for an explicit unroll count.
1070 // 1st priority is unroll count set by "unroll-count" option.
1071 // 2nd priority is unroll count set by pragma.
1072 LLVM_DEBUG(dbgs().indent(1) << "Trying pragma unroll...\n");
1073 if (auto UnrollFactor = shouldPragmaUnroll(L, PInfo, TripMultiple, TripCount,
1074 MaxTripCount, UCE, UP, ORE)) {
1075 if (PInfo.UserUnrollCount || (PInfo.PragmaCount > 0)) {
1076 UP.AllowExpensiveTripCount = true;
1077 UP.Force = true;
1078 }
1079 return *UnrollFactor;
1080 } else {
1081 if (PInfo.ExplicitUnroll && TripCount != 0) {
1082 // If the loop has an unrolling pragma, we want to be more aggressive with
1083 // unrolling limits. Set thresholds to at least the PragmaUnrollThreshold
1084 // value which is larger than the default limits.
1085 UP.Threshold = std::max<unsigned>(a: UP.Threshold, b: PragmaUnrollThreshold);
1086 UP.PartialThreshold =
1087 std::max<unsigned>(a: UP.PartialThreshold, b: PragmaUnrollThreshold);
1088 }
1089 }
1090
1091 // 3rd priority is exact full unrolling. This will eliminate all copies
1092 // of some exit test.
1093 LLVM_DEBUG(dbgs().indent(1) << "Trying full unroll...\n");
1094 if (TripCount) {
1095 if (auto UnrollFactor =
1096 shouldFullUnroll(L, TTI, DT, SE, EphValues, FullUnrollTripCount: TripCount, UCE, UP))
1097 return *UnrollFactor;
1098 }
1099
1100 // 4th priority is bounded unrolling.
1101 // We can unroll by the upper bound amount if it's generally allowed or if
1102 // we know that the loop is executed either the upper bound or zero times.
1103 // (MaxOrZero unrolling keeps only the first loop test, so the number of
1104 // loop tests remains the same compared to the non-unrolled version, whereas
1105 // the generic upper bound unrolling keeps all but the last loop test so the
1106 // number of loop tests goes up which may end up being worse on targets with
1107 // constrained branch predictor resources so is controlled by an option.)
1108 // In addition we only unroll small upper bounds.
1109 // Note that the cost of bounded unrolling is always strictly greater than
1110 // cost of exact full unrolling. As such, if we have an exact count and
1111 // found it unprofitable, we'll never chose to bounded unroll.
1112 LLVM_DEBUG(dbgs().indent(1) << "Trying upper-bound unroll...\n");
1113 if (!TripCount && MaxTripCount && (UP.UpperBound || MaxOrZero) &&
1114 MaxTripCount <= UP.MaxUpperBound) {
1115 if (auto UnrollFactor =
1116 shouldFullUnroll(L, TTI, DT, SE, EphValues, FullUnrollTripCount: MaxTripCount, UCE, UP))
1117 return *UnrollFactor;
1118 }
1119
1120 // 5th priority is loop peeling.
1121 LLVM_DEBUG(dbgs().indent(1) << "Trying loop peeling...\n");
1122 computePeelCount(L, LoopSize, PP, TripCount, DT, SE, TTI, AC, Threshold: UP.Threshold);
1123 if (PP.PeelCount) {
1124 LLVM_DEBUG(dbgs().indent(2)
1125 << "Peeling with count: " << PP.PeelCount << ".\n");
1126 UP.Runtime = false;
1127 return 1;
1128 }
1129
1130 // Before starting partial unrolling, set UP.Partial to true,
1131 // if user explicitly asked for unrolling.
1132 if (TripCount)
1133 UP.Partial |= PInfo.ExplicitUnroll;
1134
1135 // 6th priority is partial unrolling.
1136 // Try partial unroll only when TripCount could be statically calculated.
1137 LLVM_DEBUG(dbgs().indent(1) << "Trying partial unroll...\n");
1138 if (auto UnrollFactor = shouldPartialUnroll(LoopSize, TripCount, UCE, UP))
1139 return *UnrollFactor;
1140 assert(TripCount == 0 &&
1141 "All cases when TripCount is constant should be covered here.");
1142
1143 // 7th priority is runtime unrolling.
1144 LLVM_DEBUG(dbgs().indent(1) << "Trying runtime unroll...\n");
1145 // Don't unroll a runtime trip count loop when it is disabled.
1146 if (PInfo.PragmaRuntimeUnrollDisable) {
1147 LLVM_DEBUG(dbgs().indent(2)
1148 << "Not runtime unrolling: disabled by pragma.\n");
1149 return 0;
1150 }
1151
1152 // Don't unroll a small upper bound loop unless user or TTI asked to do so.
1153 if (MaxTripCount && !UP.Force && MaxTripCount <= UP.MaxUpperBound) {
1154 LLVM_DEBUG(dbgs().indent(2) << "Not runtime unrolling: max trip count "
1155 << MaxTripCount << " is small (<= "
1156 << UP.MaxUpperBound << ") and not forced.\n");
1157 return 0;
1158 }
1159
1160 // Check if the runtime trip count is too small when profile is available.
1161 if (L->getHeader()->getParent()->hasProfileData()) {
1162 if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
1163 if (*ProfileTripCount < FlatLoopTripCountThreshold)
1164 return 0;
1165 else
1166 UP.AllowExpensiveTripCount = true;
1167 }
1168 }
1169 if (!UP.Runtime) {
1170 LLVM_DEBUG(dbgs().indent(2)
1171 << "Will not try to unroll loop with runtime trip count "
1172 << "because -unroll-runtime not given\n");
1173 return 0;
1174 }
1175
1176 unsigned Count = UP.DefaultUnrollRuntimeCount;
1177
1178 // Reduce unroll count to be the largest power-of-two factor of
1179 // the original count which satisfies the threshold limit.
1180 while (Count != 0 && UCE.getUnrolledLoopSize(UP, Count) > UP.PartialThreshold)
1181 Count >>= 1;
1182
1183#ifndef NDEBUG
1184 unsigned OrigCount = Count;
1185#endif
1186
1187 if (!UP.AllowRemainder && Count != 0 && (TripMultiple % Count) != 0) {
1188 while (Count != 0 && TripMultiple % Count != 0)
1189 Count >>= 1;
1190 LLVM_DEBUG(dbgs().indent(2)
1191 << "Remainder loop is restricted (that could be architecture "
1192 "specific or because the loop contains a convergent "
1193 "instruction), so unroll count must divide the trip "
1194 "multiple, "
1195 << TripMultiple << ". Reducing unroll count from " << OrigCount
1196 << " to " << Count << ".\n");
1197 }
1198
1199 if (Count > UP.MaxCount)
1200 Count = UP.MaxCount;
1201
1202 if (MaxTripCount && Count > MaxTripCount)
1203 Count = MaxTripCount;
1204
1205 if (Count < 2)
1206 Count = 0;
1207 else
1208 LLVM_DEBUG(dbgs().indent(2)
1209 << "Runtime unrolling with count: " << Count << "\n");
1210 return Count;
1211}
1212
1213static LoopUnrollResult
1214tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
1215 const TargetTransformInfo &TTI, AssumptionCache &AC,
1216 OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
1217 ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel,
1218 bool OnlyFullUnroll, bool OnlyWhenForced, bool ForgetAllSCEV,
1219 bool PrepareForLTO, std::optional<unsigned> ProvidedThreshold,
1220 std::optional<bool> ProvidedAllowPartial,
1221 std::optional<bool> ProvidedRuntime,
1222 std::optional<bool> ProvidedUpperBound,
1223 std::optional<bool> ProvidedAllowPeeling,
1224 std::optional<bool> ProvidedAllowProfileBasedPeeling,
1225 std::optional<unsigned> ProvidedFullUnrollMaxCount,
1226 UniformityInfo *UI = nullptr, AAResults *AA = nullptr) {
1227
1228 LLVM_DEBUG(dbgs() << "Loop Unroll: F["
1229 << L->getHeader()->getParent()->getName() << "] Loop %"
1230 << L->getHeader()->getName()
1231 << " (depth=" << L->getLoopDepth() << ")\n");
1232 TransformationMode TM = hasUnrollTransformation(L);
1233 if (TM & TM_Disable) {
1234 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: transformation disabled by "
1235 << "metadata.\n");
1236 return LoopUnrollResult::Unmodified;
1237 }
1238
1239 // If this loop isn't forced to be unrolled, avoid unrolling it when the
1240 // parent loop has an explicit unroll-and-jam pragma. This is to prevent
1241 // automatic unrolling from interfering with the user requested
1242 // transformation.
1243 Loop *ParentL = L->getParentLoop();
1244 if (ParentL != nullptr &&
1245 hasUnrollAndJamTransformation(L: ParentL) == TM_ForcedByUser &&
1246 hasUnrollTransformation(L) != TM_ForcedByUser) {
1247 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling loop since parent loop has"
1248 << " llvm.loop.unroll_and_jam.\n");
1249 return LoopUnrollResult::Unmodified;
1250 }
1251
1252 // If this loop isn't forced to be unrolled, avoid unrolling it when the
1253 // loop has an explicit unroll-and-jam pragma. This is to prevent automatic
1254 // unrolling from interfering with the user requested transformation.
1255 if (hasUnrollAndJamTransformation(L) == TM_ForcedByUser &&
1256 hasUnrollTransformation(L) != TM_ForcedByUser) {
1257 LLVM_DEBUG(
1258 dbgs().indent(1)
1259 << "Not unrolling loop since it has llvm.loop.unroll_and_jam.\n");
1260 return LoopUnrollResult::Unmodified;
1261 }
1262
1263 if (!L->isLoopSimplifyForm()) {
1264 LLVM_DEBUG(dbgs().indent(1)
1265 << "Not unrolling loop which is not in loop-simplify form.\n");
1266 if (TM & TM_ForcedByUser) {
1267 ORE.emit(RemarkBuilder: [&]() {
1268 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInLoopSimplifyForm",
1269 L->getStartLoc(), L->getHeader())
1270 << "unable to unroll loop: not in loop-simplify form";
1271 });
1272 }
1273 return LoopUnrollResult::Unmodified;
1274 }
1275
1276 // When automatic unrolling is disabled, do not unroll unless overridden for
1277 // this loop.
1278 if (OnlyWhenForced && !(TM & TM_Enable)) {
1279 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: automatic unrolling "
1280 << "disabled and loop not explicitly "
1281 << "enabled.\n");
1282 return LoopUnrollResult::Unmodified;
1283 }
1284
1285 bool OptForSize = L->getHeader()->getParent()->hasOptSize();
1286 TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
1287 L, SE, TTI, BFI, PSI, ORE, OptLevel, UserThreshold: ProvidedThreshold,
1288 UserAllowPartial: ProvidedAllowPartial, UserRuntime: ProvidedRuntime, UserUpperBound: ProvidedUpperBound,
1289 UserFullUnrollMaxCount: ProvidedFullUnrollMaxCount);
1290 TargetTransformInfo::PeelingPreferences PP = gatherPeelingPreferences(
1291 L, SE, TTI, UserAllowPeeling: ProvidedAllowPeeling, UserAllowProfileBasedPeeling: ProvidedAllowProfileBasedPeeling, UnrollingSpecficValues: true);
1292
1293 // Exit early if unrolling is disabled. For OptForSize, we pick the loop size
1294 // as threshold later on.
1295 if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0) &&
1296 !OptForSize) {
1297 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: all thresholds are zero.\n");
1298 if (TM & TM_ForcedByUser) {
1299 ORE.emit(RemarkBuilder: [&]() {
1300 return OptimizationRemarkMissed(DEBUG_TYPE, "UnrollThresholdsZero",
1301 L->getStartLoc(), L->getHeader())
1302 << "unable to unroll loop: unroll threshold is zero";
1303 });
1304 }
1305 return LoopUnrollResult::Unmodified;
1306 }
1307
1308 SmallPtrSet<const Value *, 32> EphValues;
1309 CodeMetrics::collectEphemeralValues(L, AC: &AC, EphValues);
1310
1311 // Check if the backedge-taken count is uniform before constructing UCE.
1312 // This is used to allow runtime unrolling with a remainder for convergent
1313 // loops when all threads agree on the trip count.
1314 const SCEV *BTC = SE.getBackedgeTakenCount(L);
1315 bool TripCountIsUniform = UI && isSCEVUniform(S: BTC, UI&: *UI);
1316 UnrollCostEstimator UCE(L, TTI, EphValues, UP.BEInsns, PrepareForLTO,
1317 TripCountIsUniform);
1318 if (!UCE.canUnroll(ORE: (TM & TM_ForcedByUser) ? &ORE : nullptr, L))
1319 return LoopUnrollResult::Unmodified;
1320
1321 unsigned LoopSize = UCE.getRolledLoopSize();
1322 LLVM_DEBUG(dbgs() << "Loop Size = " << LoopSize << "\n");
1323
1324 // When optimizing for size, use LoopSize + 1 as threshold (we use < Threshold
1325 // later), to (fully) unroll loops, if it does not increase code size.
1326 if (OptForSize)
1327 UP.Threshold = std::max(a: UP.Threshold, b: LoopSize + 1);
1328
1329 if (UCE.NumInlineCandidates != 0) {
1330 LLVM_DEBUG(dbgs().indent(1)
1331 << "Not unrolling loop with inlinable calls.\n");
1332 if (TM & TM_ForcedByUser) {
1333 ORE.emit(RemarkBuilder: [&]() {
1334 return OptimizationRemarkMissed(DEBUG_TYPE,
1335 "InlineCandidatesPreventUnroll",
1336 L->getStartLoc(), L->getHeader())
1337 << "unable to unroll loop: contains inlinable calls";
1338 });
1339 }
1340 return LoopUnrollResult::Unmodified;
1341 }
1342
1343 // Find the smallest exact trip count for any exit. This is an upper bound
1344 // on the loop trip count, but an exit at an earlier iteration is still
1345 // possible. An unroll by the smallest exact trip count guarantees that all
1346 // branches relating to at least one exit can be eliminated. This is unlike
1347 // the max trip count, which only guarantees that the backedge can be broken.
1348 unsigned TripCount = 0;
1349 unsigned TripMultiple = 1;
1350 SmallVector<BasicBlock *, 8> ExitingBlocks;
1351 L->getExitingBlocks(ExitingBlocks);
1352 for (BasicBlock *ExitingBlock : ExitingBlocks)
1353 if (unsigned TC = SE.getSmallConstantTripCount(L, ExitingBlock))
1354 if (!TripCount || TC < TripCount)
1355 TripCount = TripMultiple = TC;
1356
1357 if (!TripCount) {
1358 // If no exact trip count is known, determine the trip multiple of either
1359 // the loop latch or the single exiting block.
1360 // TODO: Relax for multiple exits.
1361 BasicBlock *ExitingBlock = L->getLoopLatch();
1362 if (!ExitingBlock || !L->isLoopExiting(BB: ExitingBlock))
1363 ExitingBlock = L->getExitingBlock();
1364 if (ExitingBlock)
1365 TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
1366 }
1367
1368 // If the loop contains a convergent operation, the prelude we'd add
1369 // to do the first few instructions before we hit the unrolled loop
1370 // is unsafe -- it adds a control-flow dependency to the convergent
1371 // operation. Therefore restrict remainder loop (try unrolling without).
1372 UP.AllowRemainder &= UCE.ConvergenceAllowsRuntime;
1373
1374 // Try to find the trip count upper bound if we cannot find the exact trip
1375 // count.
1376 unsigned MaxTripCount = 0;
1377 bool MaxOrZero = false;
1378 if (!TripCount) {
1379 MaxTripCount = SE.getSmallConstantMaxTripCount(L);
1380 MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
1381 }
1382
1383 // computeUnrollCount() decides whether it is beneficial to use upper bound to
1384 // fully unroll the loop.
1385 unsigned Count =
1386 computeUnrollCount(L, TTI, DT, LI, AC: &AC, SE, EphValues, ORE: &ORE, TripCount,
1387 MaxTripCount, MaxOrZero, TripMultiple, UCE, UP, PP);
1388 if (!Count) {
1389 LLVM_DEBUG(dbgs().indent(1)
1390 << "Not unrolling: no viable strategy found.\n");
1391 if (TM & TM_ForcedByUser) {
1392 ORE.emit(RemarkBuilder: [&]() {
1393 return OptimizationRemarkMissed(DEBUG_TYPE, "NoUnrollStrategy",
1394 L->getStartLoc(), L->getHeader())
1395 << "unable to unroll loop: no viable unroll count found";
1396 });
1397 }
1398 return LoopUnrollResult::Unmodified;
1399 }
1400
1401 UP.Runtime &= UCE.ConvergenceAllowsRuntime;
1402
1403 if (PP.PeelCount) {
1404 assert(Count == 1 && "Cannot perform peel and unroll in the same step");
1405 LLVM_DEBUG(dbgs() << "PEELING loop %" << L->getHeader()->getName()
1406 << " with iteration count " << PP.PeelCount << "!\n");
1407 ORE.emit(RemarkBuilder: [&]() {
1408 return OptimizationRemark(DEBUG_TYPE, "Peeled", L->getStartLoc(),
1409 L->getHeader())
1410 << "peeled loop by " << ore::NV("PeelCount", PP.PeelCount)
1411 << " iterations";
1412 });
1413
1414 ValueToValueMapTy VMap;
1415 peelLoop(L, PeelCount: PP.PeelCount, PeelLast: PP.PeelLast, LI, SE: &SE, DT, AC: &AC, PreserveLCSSA,
1416 VMap);
1417 simplifyLoopAfterUnroll(L, SimplifyIVs: true, LI, SE: &SE, DT: &DT, AC: &AC, TTI: &TTI, Blocks: L->getBlocks(),
1418 AA: nullptr);
1419 // If the loop was peeled, we already "used up" the profile information
1420 // we had, so we don't want to unroll or peel again.
1421 if (PP.PeelProfiledIterations)
1422 L->setLoopAlreadyUnrolled();
1423 return LoopUnrollResult::PartiallyUnrolled;
1424 }
1425
1426 // Do not attempt partial/runtime unrolling in FullLoopUnrolling
1427 if (OnlyFullUnroll && ((!TripCount && !MaxTripCount) || Count < TripCount ||
1428 Count < MaxTripCount)) {
1429 LLVM_DEBUG(dbgs().indent(1)
1430 << "Not attempting partial/runtime unroll in FullLoopUnroll.\n");
1431 return LoopUnrollResult::Unmodified;
1432 }
1433
1434 // At this point, UP.Runtime indicates that run-time unrolling is allowed.
1435 // However, we only want to actually perform it if we don't know the trip
1436 // count and the unroll count doesn't divide the known trip multiple.
1437 // TODO: This decision should probably be pushed up into
1438 // computeUnrollCount().
1439 UP.Runtime &= TripCount == 0 && TripMultiple % Count != 0;
1440
1441 // Save loop properties before it is transformed.
1442 MDNode *OrigLoopID = L->getLoopID();
1443 UnrollPragmaInfo PInfo(L);
1444 DebugLoc LoopStartLoc = L->getStartLoc();
1445 BasicBlock *LoopHeader = L->getHeader();
1446
1447 // Unroll the loop.
1448 Loop *RemainderLoop = nullptr;
1449 UnrollLoopOptions ULO;
1450 ULO.Count = Count;
1451 ULO.Force = UP.Force;
1452 ULO.AllowExpensiveTripCount = UP.AllowExpensiveTripCount;
1453 ULO.UnrollRemainder = UP.UnrollRemainder;
1454 ULO.Runtime = UP.Runtime;
1455 ULO.ForgetAllSCEV = ForgetAllSCEV;
1456 ULO.Heart = getLoopConvergenceHeart(TheLoop: L);
1457 ULO.SCEVExpansionBudget = UP.SCEVExpansionBudget;
1458 ULO.RuntimeUnrollMultiExit = UP.RuntimeUnrollMultiExit;
1459 ULO.AddAdditionalAccumulators = UP.AddAdditionalAccumulators;
1460 LoopUnrollResult UnrollResult = UnrollLoop(
1461 L, ULO, LI, SE: &SE, DT: &DT, AC: &AC, TTI: &TTI, ORE: &ORE, PreserveLCSSA, RemainderLoop: &RemainderLoop, AA);
1462 if (UnrollResult == LoopUnrollResult::Unmodified) {
1463 if (PInfo.ExplicitUnroll) {
1464 LLVM_DEBUG(dbgs().indent(1)
1465 << "Failed to unroll loop as explicitly requested.\n");
1466 ORE.emit(RemarkBuilder: [&]() {
1467 return OptimizationRemarkMissed(DEBUG_TYPE, "FailedToUnrollAsRequested",
1468 LoopStartLoc, LoopHeader)
1469 << "failed to unroll loop as explicitly requested";
1470 });
1471 }
1472 return LoopUnrollResult::Unmodified;
1473 }
1474
1475 if (PInfo.PragmaFullUnroll && ULO.Count != TripCount) {
1476 ORE.emit(RemarkBuilder: [&]() {
1477 return OptimizationRemarkMissed(DEBUG_TYPE, "FullUnrollAsDirectedFailed",
1478 LoopStartLoc, LoopHeader)
1479 << "unable to fully unroll loop as directed; "
1480 << "unrolled by factor " << ore::NV("UnrollCount", ULO.Count);
1481 });
1482 }
1483 if (PInfo.PragmaCount > 0 && ULO.Count != PInfo.PragmaCount) {
1484 ORE.emit(RemarkBuilder: [&]() {
1485 return OptimizationRemarkMissed(DEBUG_TYPE, "UnrollCountDiffers",
1486 LoopStartLoc, LoopHeader)
1487 << "unable to unroll loop with requested count "
1488 << ore::NV("RequestedCount", PInfo.PragmaCount)
1489 << "; unrolled by factor " << ore::NV("UnrollCount", ULO.Count);
1490 });
1491 }
1492
1493 if (RemainderLoop) {
1494 std::optional<MDNode *> RemainderLoopID =
1495 makeFollowupLoopID(OrigLoopID, FollowupAttrs: {LLVMLoopUnrollFollowupAll,
1496 LLVMLoopUnrollFollowupRemainder});
1497 if (RemainderLoopID)
1498 RemainderLoop->setLoopID(*RemainderLoopID);
1499 }
1500
1501 if (UnrollResult != LoopUnrollResult::FullyUnrolled) {
1502 std::optional<MDNode *> NewLoopID =
1503 makeFollowupLoopID(OrigLoopID, FollowupAttrs: {LLVMLoopUnrollFollowupAll,
1504 LLVMLoopUnrollFollowupUnrolled});
1505 if (NewLoopID) {
1506 L->setLoopID(*NewLoopID);
1507
1508 // Do not setLoopAlreadyUnrolled if loop attributes have been specified
1509 // explicitly.
1510 return UnrollResult;
1511 }
1512 }
1513
1514 // If loop has an unroll count pragma or unrolled by explicitly set count
1515 // mark loop as unrolled to prevent unrolling beyond that requested.
1516 if (UnrollResult != LoopUnrollResult::FullyUnrolled && PInfo.ExplicitUnroll)
1517 L->setLoopAlreadyUnrolled();
1518
1519 return UnrollResult;
1520}
1521
1522namespace {
1523
1524class LoopUnroll : public LoopPass {
1525public:
1526 static char ID; // Pass ID, replacement for typeid
1527
1528 int OptLevel;
1529
1530 /// If false, use a cost model to determine whether unrolling of a loop is
1531 /// profitable. If true, only loops that explicitly request unrolling via
1532 /// metadata are considered. All other loops are skipped.
1533 bool OnlyWhenForced;
1534
1535 /// If false, when SCEV is invalidated, only forget everything in the
1536 /// top-most loop (call forgetTopMostLoop), of the loop being processed.
1537 /// Otherwise, forgetAllLoops and rebuild when needed next.
1538 bool ForgetAllSCEV;
1539
1540 std::optional<unsigned> ProvidedThreshold;
1541 std::optional<bool> ProvidedAllowPartial;
1542 std::optional<bool> ProvidedRuntime;
1543 std::optional<bool> ProvidedUpperBound;
1544 std::optional<bool> ProvidedAllowPeeling;
1545 std::optional<bool> ProvidedAllowProfileBasedPeeling;
1546 std::optional<unsigned> ProvidedFullUnrollMaxCount;
1547
1548 LoopUnroll(int OptLevel = 2, bool OnlyWhenForced = false,
1549 bool ForgetAllSCEV = false,
1550 std::optional<unsigned> Threshold = std::nullopt,
1551 std::optional<bool> AllowPartial = std::nullopt,
1552 std::optional<bool> Runtime = std::nullopt,
1553 std::optional<bool> UpperBound = std::nullopt,
1554 std::optional<bool> AllowPeeling = std::nullopt,
1555 std::optional<bool> AllowProfileBasedPeeling = std::nullopt,
1556 std::optional<unsigned> ProvidedFullUnrollMaxCount = std::nullopt)
1557 : LoopPass(ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
1558 ForgetAllSCEV(ForgetAllSCEV), ProvidedThreshold(Threshold),
1559 ProvidedAllowPartial(AllowPartial), ProvidedRuntime(Runtime),
1560 ProvidedUpperBound(UpperBound), ProvidedAllowPeeling(AllowPeeling),
1561 ProvidedAllowProfileBasedPeeling(AllowProfileBasedPeeling),
1562 ProvidedFullUnrollMaxCount(ProvidedFullUnrollMaxCount) {
1563 initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
1564 }
1565
1566 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1567 if (skipLoop(L))
1568 return false;
1569
1570 Function &F = *L->getHeader()->getParent();
1571
1572 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1573 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1574 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1575 const TargetTransformInfo &TTI =
1576 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1577 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1578 UniformityInfo *UI =
1579 TTI.hasBranchDivergence(F: &F)
1580 ? &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo()
1581 : nullptr;
1582 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
1583 // pass. Function analyses need to be preserved across loop transformations
1584 // but ORE cannot be preserved (see comment before the pass definition).
1585 OptimizationRemarkEmitter ORE(&F);
1586 bool PreserveLCSSA = mustPreserveAnalysisID(AID&: LCSSAID);
1587
1588 LoopUnrollResult Result = tryToUnrollLoop(
1589 L, DT, LI, SE, TTI, AC, ORE, BFI: nullptr, PSI: nullptr, PreserveLCSSA, OptLevel,
1590 /*OnlyFullUnroll*/ false, OnlyWhenForced, ForgetAllSCEV,
1591 /*PrepareForLTO*/ false, ProvidedThreshold, ProvidedAllowPartial,
1592 ProvidedRuntime, ProvidedUpperBound, ProvidedAllowPeeling,
1593 ProvidedAllowProfileBasedPeeling, ProvidedFullUnrollMaxCount, UI);
1594
1595 if (Result == LoopUnrollResult::FullyUnrolled)
1596 LPM.markLoopAsDeleted(L&: *L);
1597
1598 return Result != LoopUnrollResult::Unmodified;
1599 }
1600
1601 /// This transformation requires natural loop information & requires that
1602 /// loop preheaders be inserted into the CFG...
1603 void getAnalysisUsage(AnalysisUsage &AU) const override {
1604 AU.addRequired<AssumptionCacheTracker>();
1605 AU.addRequired<TargetTransformInfoWrapperPass>();
1606 AU.addRequired<UniformityInfoWrapperPass>();
1607 // FIXME: Loop passes are required to preserve domtree, and for now we just
1608 // recreate dom info if anything gets unrolled.
1609 getLoopAnalysisUsage(AU);
1610 }
1611};
1612
1613} // end anonymous namespace
1614
1615char LoopUnroll::ID = 0;
1616
1617INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1618INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1619INITIALIZE_PASS_DEPENDENCY(LoopPass)
1620INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1621INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass)
1622INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1623
1624Pass *llvm::createLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
1625 bool ForgetAllSCEV, int Threshold,
1626 int AllowPartial, int Runtime, int UpperBound,
1627 int AllowPeeling) {
1628 // TODO: It would make more sense for this function to take the optionals
1629 // directly, but that's dangerous since it would silently break out of tree
1630 // callers.
1631 return new LoopUnroll(
1632 OptLevel, OnlyWhenForced, ForgetAllSCEV,
1633 Threshold == -1 ? std::nullopt : std::optional<unsigned>(Threshold),
1634 AllowPartial == -1 ? std::nullopt : std::optional<bool>(AllowPartial),
1635 Runtime == -1 ? std::nullopt : std::optional<bool>(Runtime),
1636 UpperBound == -1 ? std::nullopt : std::optional<bool>(UpperBound),
1637 AllowPeeling == -1 ? std::nullopt : std::optional<bool>(AllowPeeling));
1638}
1639
1640PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
1641 LoopStandardAnalysisResults &AR,
1642 LPMUpdater &Updater) {
1643 // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
1644 // pass. Function analyses need to be preserved across loop transformations
1645 // but ORE cannot be preserved (see comment before the pass definition).
1646 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
1647
1648 // Keep track of the previous loop structure so we can identify new loops
1649 // created by unrolling.
1650 Loop *ParentL = L.getParentLoop();
1651 SmallPtrSet<Loop *, 4> OldLoops;
1652 if (ParentL)
1653 OldLoops.insert_range(R&: *ParentL);
1654 else
1655 OldLoops.insert_range(R&: AR.LI);
1656
1657 std::string LoopName = std::string(L.getName());
1658
1659 bool Changed =
1660 tryToUnrollLoop(L: &L, DT&: AR.DT, LI: &AR.LI, SE&: AR.SE, TTI: AR.TTI, AC&: AR.AC, ORE,
1661 /*BFI*/ nullptr, /*PSI*/ nullptr,
1662 /*PreserveLCSSA*/ true, OptLevel, /*OnlyFullUnroll*/ true,
1663 OnlyWhenForced, ForgetAllSCEV: ForgetSCEV, PrepareForLTO,
1664 /*Threshold*/ ProvidedThreshold: std::nullopt, /*AllowPartial*/ ProvidedAllowPartial: false,
1665 /*Runtime*/ ProvidedRuntime: false, /*UpperBound*/ ProvidedUpperBound: false,
1666 /*AllowPeeling*/ ProvidedAllowPeeling: true,
1667 /*AllowProfileBasedPeeling*/ ProvidedAllowProfileBasedPeeling: false,
1668 /*FullUnrollMaxCount*/ ProvidedFullUnrollMaxCount: std::nullopt) !=
1669 LoopUnrollResult::Unmodified;
1670 if (!Changed)
1671 return PreservedAnalyses::all();
1672
1673 // The parent must not be damaged by unrolling!
1674#ifndef NDEBUG
1675 if (ParentL)
1676 ParentL->verifyLoop();
1677#endif
1678
1679 // Unrolling can do several things to introduce new loops into a loop nest:
1680 // - Full unrolling clones child loops within the current loop but then
1681 // removes the current loop making all of the children appear to be new
1682 // sibling loops.
1683 //
1684 // When a new loop appears as a sibling loop after fully unrolling,
1685 // its nesting structure has fundamentally changed and we want to revisit
1686 // it to reflect that.
1687 //
1688 // When unrolling has removed the current loop, we need to tell the
1689 // infrastructure that it is gone.
1690 //
1691 // Finally, we support a debugging/testing mode where we revisit child loops
1692 // as well. These are not expected to require further optimizations as either
1693 // they or the loop they were cloned from have been directly visited already.
1694 // But the debugging mode allows us to check this assumption.
1695 bool IsCurrentLoopValid = false;
1696 SmallVector<Loop *, 4> SibLoops;
1697 if (ParentL)
1698 SibLoops.append(in_start: ParentL->begin(), in_end: ParentL->end());
1699 else
1700 SibLoops.append(in_start: AR.LI.begin(), in_end: AR.LI.end());
1701 erase_if(C&: SibLoops, P: [&](Loop *SibLoop) {
1702 if (SibLoop == &L) {
1703 IsCurrentLoopValid = true;
1704 return true;
1705 }
1706
1707 // Otherwise erase the loop from the list if it was in the old loops.
1708 return OldLoops.contains(Ptr: SibLoop);
1709 });
1710 Updater.addSiblingLoops(NewSibLoops: SibLoops);
1711
1712 if (!IsCurrentLoopValid) {
1713 Updater.markLoopAsDeleted(L, Name: LoopName);
1714 } else {
1715 // We can only walk child loops if the current loop remained valid.
1716 if (UnrollRevisitChildLoops) {
1717 // Walk *all* of the child loops.
1718 SmallVector<Loop *, 4> ChildLoops(L.begin(), L.end());
1719 Updater.addChildLoops(NewChildLoops: ChildLoops);
1720 }
1721 }
1722
1723 return getLoopPassPreservedAnalyses();
1724}
1725
1726PreservedAnalyses LoopUnrollPass::run(Function &F,
1727 FunctionAnalysisManager &AM) {
1728 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
1729 // There are no loops in the function. Return before computing other expensive
1730 // analyses.
1731 if (LI.empty())
1732 return PreservedAnalyses::all();
1733 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
1734 auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1735 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
1736 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
1737 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
1738 AAResults &AA = AM.getResult<AAManager>(IR&: F);
1739
1740 UniformityInfo *UI = TTI.hasBranchDivergence(F: &F)
1741 ? &AM.getResult<UniformityInfoAnalysis>(IR&: F)
1742 : nullptr;
1743
1744 LoopAnalysisManager *LAM = nullptr;
1745 if (auto *LAMProxy = AM.getCachedResult<LoopAnalysisManagerFunctionProxy>(IR&: F))
1746 LAM = &LAMProxy->getManager();
1747
1748 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
1749 ProfileSummaryInfo *PSI =
1750 MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
1751 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
1752 &AM.getResult<BlockFrequencyAnalysis>(IR&: F) : nullptr;
1753
1754 bool Changed = false;
1755
1756 // The unroller requires loops to be in simplified form, and also needs LCSSA.
1757 // Since simplification may add new inner loops, it has to run before the
1758 // legality and profitability checks. This means running the loop unroller
1759 // will simplify all loops, regardless of whether anything end up being
1760 // unrolled.
1761 for (const auto &L : LI) {
1762 Changed |=
1763 simplifyLoop(L, DT: &DT, LI: &LI, SE: &SE, AC: &AC, MSSAU: nullptr, PreserveLCSSA: false /* PreserveLCSSA */);
1764 Changed |= formLCSSARecursively(L&: *L, DT, LI: &LI, SE: &SE);
1765 }
1766
1767 // Add the loop nests in the reverse order of LoopInfo. See method
1768 // declaration.
1769 SmallPriorityWorklist<Loop *, 4> Worklist;
1770 appendLoopsToWorklist(LI, Worklist);
1771
1772 while (!Worklist.empty()) {
1773 // Because the LoopInfo stores the loops in RPO, we walk the worklist
1774 // from back to front so that we work forward across the CFG, which
1775 // for unrolling is only needed to get optimization remarks emitted in
1776 // a forward order.
1777 Loop &L = *Worklist.pop_back_val();
1778#ifndef NDEBUG
1779 Loop *ParentL = L.getParentLoop();
1780#endif
1781
1782 // Check if the profile summary indicates that the profiled application
1783 // has a huge working set size, in which case we disable peeling to avoid
1784 // bloating it further.
1785 std::optional<bool> LocalAllowPeeling = UnrollOpts.AllowPeeling;
1786 if (PSI && PSI->hasHugeWorkingSetSize())
1787 LocalAllowPeeling = false;
1788 std::string LoopName = std::string(L.getName());
1789 // The API here is quite complex to call and we allow to select some
1790 // flavors of unrolling during construction time (by setting UnrollOpts).
1791 LoopUnrollResult Result =
1792 tryToUnrollLoop(L: &L, DT, LI: &LI, SE, TTI, AC, ORE, BFI, PSI,
1793 /*PreserveLCSSA*/ true, OptLevel: UnrollOpts.OptLevel,
1794 /*OnlyFullUnroll*/ false, OnlyWhenForced: UnrollOpts.OnlyWhenForced,
1795 ForgetAllSCEV: UnrollOpts.ForgetSCEV, PrepareForLTO: UnrollOpts.PrepareForLTO,
1796 /*Threshold*/ ProvidedThreshold: std::nullopt, ProvidedAllowPartial: UnrollOpts.AllowPartial,
1797 ProvidedRuntime: UnrollOpts.AllowRuntime, ProvidedUpperBound: UnrollOpts.AllowUpperBound,
1798 ProvidedAllowPeeling: LocalAllowPeeling, ProvidedAllowProfileBasedPeeling: UnrollOpts.AllowProfileBasedPeeling,
1799 ProvidedFullUnrollMaxCount: UnrollOpts.FullUnrollMaxCount, UI, AA: &AA);
1800 Changed |= Result != LoopUnrollResult::Unmodified;
1801
1802 // The parent must not be damaged by unrolling!
1803#ifndef NDEBUG
1804 if (Result != LoopUnrollResult::Unmodified && ParentL)
1805 ParentL->verifyLoop();
1806#endif
1807
1808 // Clear any cached analysis results for L if we removed it completely.
1809 if (LAM && Result == LoopUnrollResult::FullyUnrolled)
1810 LAM->clear(IR&: L, Name: LoopName);
1811 }
1812
1813 if (!Changed)
1814 return PreservedAnalyses::all();
1815
1816 return getLoopPassPreservedAnalyses();
1817}
1818
1819void LoopUnrollPass::printPipeline(
1820 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1821 static_cast<PassInfoMixin<LoopUnrollPass> *>(this)->printPipeline(
1822 OS, MapClassName2PassName);
1823 OS << '<';
1824 if (UnrollOpts.AllowPartial != std::nullopt)
1825 OS << (*UnrollOpts.AllowPartial ? "" : "no-") << "partial;";
1826 if (UnrollOpts.AllowPeeling != std::nullopt)
1827 OS << (*UnrollOpts.AllowPeeling ? "" : "no-") << "peeling;";
1828 if (UnrollOpts.AllowRuntime != std::nullopt)
1829 OS << (*UnrollOpts.AllowRuntime ? "" : "no-") << "runtime;";
1830 if (UnrollOpts.AllowUpperBound != std::nullopt)
1831 OS << (*UnrollOpts.AllowUpperBound ? "" : "no-") << "upperbound;";
1832 if (UnrollOpts.AllowProfileBasedPeeling != std::nullopt)
1833 OS << (*UnrollOpts.AllowProfileBasedPeeling ? "" : "no-")
1834 << "profile-peeling;";
1835 if (UnrollOpts.FullUnrollMaxCount != std::nullopt)
1836 OS << "full-unroll-max=" << UnrollOpts.FullUnrollMaxCount << ';';
1837 if (UnrollOpts.PrepareForLTO)
1838 OS << "prepare-for-lto;";
1839 OS << 'O' << UnrollOpts.OptLevel;
1840 OS << '>';
1841}
1842