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