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