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