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