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