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