LLVM  14.0.0git
LoopUnrollPass.cpp
Go to the documentation of this file.
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 
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"
30 #include "llvm/Analysis/LoopInfo.h"
31 #include "llvm/Analysis/LoopPass.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"
53 #include "llvm/Support/Debug.h"
56 #include "llvm/Transforms/Scalar.h"
58 #include "llvm/Transforms/Utils.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 
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>
88  "unroll-optsize-threshold", cl::init(0), cl::Hidden,
89  cl::desc("The cost threshold for loop unrolling when optimizing for "
90  "size"));
91 
93  "unroll-partial-threshold", cl::Hidden,
94  cl::desc("The cost threshold for partial loop unrolling"));
95 
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 
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 
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 
116  "unroll-max-count", cl::Hidden,
117  cl::desc("Set the max unroll count for partial and runtime unrolling, for"
118  "testing purposes"));
119 
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 
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 
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 
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 
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 
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.
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 
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.
182 
183 /// Gather the various unrolling parameters based on the defaults, compiler
184 /// flags, TTI overrides and user specified parameters.
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) {
193 
194  // Set up the defaults
195  UP.Threshold =
197  UP.MaxPercentThresholdBoost = 400;
199  UP.PartialThreshold = 150;
201  UP.Count = 0;
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;
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.
226  if (OptForSize) {
227  UP.Threshold = UP.OptSizeThreshold;
229  UP.MaxPercentThresholdBoost = 100;
230  }
231 
232  // Apply any user values specified by cl::opt
233  if (UnrollThreshold.getNumOccurrences() > 0)
235  if (UnrollPartialThreshold.getNumOccurrences() > 0)
237  if (UnrollMaxPercentThresholdBoost.getNumOccurrences() > 0)
239  if (UnrollMaxCount.getNumOccurrences() > 0)
241  if (UnrollFullMaxCount.getNumOccurrences() > 0)
248  UP.Runtime = UnrollRuntime;
249  if (UnrollMaxUpperBound == 0)
250  UP.UpperBound = false;
253  if (UnrollMaxIterationsCountToAnalyze.getNumOccurrences() > 0)
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 *>;
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 struct PragmaInfo {
323  PragmaInfo(bool UUC, bool PFU, unsigned PC, bool PEU)
324  : UserUnrollCount(UUC), PragmaFullUnroll(PFU), PragmaCount(PC),
325  PragmaEnableUnroll(PEU) {}
326  const bool UserUnrollCount;
327  const bool PragmaFullUnroll;
328  const unsigned PragmaCount;
329  const bool PragmaEnableUnroll;
330 };
331 
332 } // end anonymous namespace
333 
334 /// Figure out if the loop is worth full unrolling.
335 ///
336 /// Complete loop unrolling can make some loads constant, and we need to know
337 /// if that would expose any further optimization opportunities. This routine
338 /// estimates this optimization. It computes cost of unrolled loop
339 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
340 /// dynamic cost we mean that we won't count costs of blocks that are known not
341 /// to be executed (i.e. if we have a branch in the loop and we know that at the
342 /// given iteration its condition would be resolved to true, we won't add up the
343 /// cost of the 'false'-block).
344 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
345 /// the analysis failed (no benefits expected from the unrolling, or the loop is
346 /// too big to analyze), the returned value is None.
348  const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE,
349  const SmallPtrSetImpl<const Value *> &EphValues,
350  const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize,
351  unsigned MaxIterationsCountToAnalyze) {
352  // We want to be able to scale offsets by the trip count and add more offsets
353  // to them without checking for overflows, and we already don't want to
354  // analyze *massive* trip counts, so we force the max to be reasonably small.
355  assert(MaxIterationsCountToAnalyze <
356  (unsigned)(std::numeric_limits<int>::max() / 2) &&
357  "The unroll iterations max is too large!");
358 
359  // Only analyze inner loops. We can't properly estimate cost of nested loops
360  // and we won't visit inner loops again anyway.
361  if (!L->isInnermost())
362  return None;
363 
364  // Don't simulate loops with a big or unknown tripcount
365  if (!TripCount || TripCount > MaxIterationsCountToAnalyze)
366  return None;
367 
370  DenseMap<Value *, Value *> SimplifiedValues;
371  SmallVector<std::pair<Value *, Value *>, 4> SimplifiedInputValues;
372 
373  // The estimated cost of the unrolled form of the loop. We try to estimate
374  // this by simplifying as much as we can while computing the estimate.
375  InstructionCost UnrolledCost = 0;
376 
377  // We also track the estimated dynamic (that is, actually executed) cost in
378  // the rolled form. This helps identify cases when the savings from unrolling
379  // aren't just exposing dead control flows, but actual reduced dynamic
380  // instructions due to the simplifications which we expect to occur after
381  // unrolling.
382  InstructionCost RolledDynamicCost = 0;
383 
384  // We track the simplification of each instruction in each iteration. We use
385  // this to recursively merge costs into the unrolled cost on-demand so that
386  // we don't count the cost of any dead code. This is essentially a map from
387  // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
389 
390  // A small worklist used to accumulate cost of instructions from each
391  // observable and reached root in the loop.
392  SmallVector<Instruction *, 16> CostWorklist;
393 
394  // PHI-used worklist used between iterations while accumulating cost.
395  SmallVector<Instruction *, 4> PHIUsedList;
396 
397  // Helper function to accumulate cost for instructions in the loop.
398  auto AddCostRecursively = [&](Instruction &RootI, int Iteration) {
399  assert(Iteration >= 0 && "Cannot have a negative iteration!");
400  assert(CostWorklist.empty() && "Must start with an empty cost list");
401  assert(PHIUsedList.empty() && "Must start with an empty phi used list");
402  CostWorklist.push_back(&RootI);
404  RootI.getFunction()->hasMinSize() ?
407  for (;; --Iteration) {
408  do {
409  Instruction *I = CostWorklist.pop_back_val();
410 
411  // InstCostMap only uses I and Iteration as a key, the other two values
412  // don't matter here.
413  auto CostIter = InstCostMap.find({I, Iteration, 0, 0});
414  if (CostIter == InstCostMap.end())
415  // If an input to a PHI node comes from a dead path through the loop
416  // we may have no cost data for it here. What that actually means is
417  // that it is free.
418  continue;
419  auto &Cost = *CostIter;
420  if (Cost.IsCounted)
421  // Already counted this instruction.
422  continue;
423 
424  // Mark that we are counting the cost of this instruction now.
425  Cost.IsCounted = true;
426 
427  // If this is a PHI node in the loop header, just add it to the PHI set.
428  if (auto *PhiI = dyn_cast<PHINode>(I))
429  if (PhiI->getParent() == L->getHeader()) {
430  assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
431  "inherently simplify during unrolling.");
432  if (Iteration == 0)
433  continue;
434 
435  // Push the incoming value from the backedge into the PHI used list
436  // if it is an in-loop instruction. We'll use this to populate the
437  // cost worklist for the next iteration (as we count backwards).
438  if (auto *OpI = dyn_cast<Instruction>(
439  PhiI->getIncomingValueForBlock(L->getLoopLatch())))
440  if (L->contains(OpI))
441  PHIUsedList.push_back(OpI);
442  continue;
443  }
444 
445  // First accumulate the cost of this instruction.
446  if (!Cost.IsFree) {
447  UnrolledCost += TTI.getUserCost(I, CostKind);
448  LLVM_DEBUG(dbgs() << "Adding cost of instruction (iteration "
449  << Iteration << "): ");
450  LLVM_DEBUG(I->dump());
451  }
452 
453  // We must count the cost of every operand which is not free,
454  // recursively. If we reach a loop PHI node, simply add it to the set
455  // to be considered on the next iteration (backwards!).
456  for (Value *Op : I->operands()) {
457  // Check whether this operand is free due to being a constant or
458  // outside the loop.
459  auto *OpI = dyn_cast<Instruction>(Op);
460  if (!OpI || !L->contains(OpI))
461  continue;
462 
463  // Otherwise accumulate its cost.
464  CostWorklist.push_back(OpI);
465  }
466  } while (!CostWorklist.empty());
467 
468  if (PHIUsedList.empty())
469  // We've exhausted the search.
470  break;
471 
472  assert(Iteration > 0 &&
473  "Cannot track PHI-used values past the first iteration!");
474  CostWorklist.append(PHIUsedList.begin(), PHIUsedList.end());
475  PHIUsedList.clear();
476  }
477  };
478 
479  // Ensure that we don't violate the loop structure invariants relied on by
480  // this analysis.
481  assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
482  assert(L->isLCSSAForm(DT) &&
483  "Must have loops in LCSSA form to track live-out values.");
484 
485  LLVM_DEBUG(dbgs() << "Starting LoopUnroll profitability analysis...\n");
486 
488  L->getHeader()->getParent()->hasMinSize() ?
490  // Simulate execution of each iteration of the loop counting instructions,
491  // which would be simplified.
492  // Since the same load will take different values on different iterations,
493  // we literally have to go through all loop's iterations.
494  for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
495  LLVM_DEBUG(dbgs() << " Analyzing iteration " << Iteration << "\n");
496 
497  // Prepare for the iteration by collecting any simplified entry or backedge
498  // inputs.
499  for (Instruction &I : *L->getHeader()) {
500  auto *PHI = dyn_cast<PHINode>(&I);
501  if (!PHI)
502  break;
503 
504  // The loop header PHI nodes must have exactly two input: one from the
505  // loop preheader and one from the loop latch.
506  assert(
507  PHI->getNumIncomingValues() == 2 &&
508  "Must have an incoming value only for the preheader and the latch.");
509 
510  Value *V = PHI->getIncomingValueForBlock(
511  Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
512  if (Iteration != 0 && SimplifiedValues.count(V))
513  V = SimplifiedValues.lookup(V);
514  SimplifiedInputValues.push_back({PHI, V});
515  }
516 
517  // Now clear and re-populate the map for the next iteration.
518  SimplifiedValues.clear();
519  while (!SimplifiedInputValues.empty())
520  SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
521 
522  UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
523 
524  BBWorklist.clear();
525  BBWorklist.insert(L->getHeader());
526  // Note that we *must not* cache the size, this loop grows the worklist.
527  for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
528  BasicBlock *BB = BBWorklist[Idx];
529 
530  // Visit all instructions in the given basic block and try to simplify
531  // it. We don't change the actual IR, just count optimization
532  // opportunities.
533  for (Instruction &I : *BB) {
534  // These won't get into the final code - don't even try calculating the
535  // cost for them.
536  if (isa<DbgInfoIntrinsic>(I) || EphValues.count(&I))
537  continue;
538 
539  // Track this instruction's expected baseline cost when executing the
540  // rolled loop form.
541  RolledDynamicCost += TTI.getUserCost(&I, CostKind);
542 
543  // Visit the instruction to analyze its loop cost after unrolling,
544  // and if the visitor returns true, mark the instruction as free after
545  // unrolling and continue.
546  bool IsFree = Analyzer.visit(I);
547  bool Inserted = InstCostMap.insert({&I, (int)Iteration,
548  (unsigned)IsFree,
549  /*IsCounted*/ false}).second;
550  (void)Inserted;
551  assert(Inserted && "Cannot have a state for an unvisited instruction!");
552 
553  if (IsFree)
554  continue;
555 
556  // Can't properly model a cost of a call.
557  // FIXME: With a proper cost model we should be able to do it.
558  if (auto *CI = dyn_cast<CallInst>(&I)) {
559  const Function *Callee = CI->getCalledFunction();
560  if (!Callee || TTI.isLoweredToCall(Callee)) {
561  LLVM_DEBUG(dbgs() << "Can't analyze cost of loop with call\n");
562  return None;
563  }
564  }
565 
566  // If the instruction might have a side-effect recursively account for
567  // the cost of it and all the instructions leading up to it.
568  if (I.mayHaveSideEffects())
569  AddCostRecursively(I, Iteration);
570 
571  // If unrolled body turns out to be too big, bail out.
572  if (UnrolledCost > MaxUnrolledLoopSize) {
573  LLVM_DEBUG(dbgs() << " Exceeded threshold.. exiting.\n"
574  << " UnrolledCost: " << UnrolledCost
575  << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
576  << "\n");
577  return None;
578  }
579  }
580 
581  Instruction *TI = BB->getTerminator();
582 
583  auto getSimplifiedConstant = [&](Value *V) -> Constant * {
584  if (SimplifiedValues.count(V))
585  V = SimplifiedValues.lookup(V);
586  return dyn_cast<Constant>(V);
587  };
588 
589  // Add in the live successors by first checking whether we have terminator
590  // that may be simplified based on the values simplified by this call.
591  BasicBlock *KnownSucc = nullptr;
592  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
593  if (BI->isConditional()) {
594  if (auto *SimpleCond = getSimplifiedConstant(BI->getCondition())) {
595  // Just take the first successor if condition is undef
596  if (isa<UndefValue>(SimpleCond))
597  KnownSucc = BI->getSuccessor(0);
598  else if (ConstantInt *SimpleCondVal =
599  dyn_cast<ConstantInt>(SimpleCond))
600  KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
601  }
602  }
603  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
604  if (auto *SimpleCond = getSimplifiedConstant(SI->getCondition())) {
605  // Just take the first successor if condition is undef
606  if (isa<UndefValue>(SimpleCond))
607  KnownSucc = SI->getSuccessor(0);
608  else if (ConstantInt *SimpleCondVal =
609  dyn_cast<ConstantInt>(SimpleCond))
610  KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
611  }
612  }
613  if (KnownSucc) {
614  if (L->contains(KnownSucc))
615  BBWorklist.insert(KnownSucc);
616  else
617  ExitWorklist.insert({BB, KnownSucc});
618  continue;
619  }
620 
621  // Add BB's successors to the worklist.
622  for (BasicBlock *Succ : successors(BB))
623  if (L->contains(Succ))
624  BBWorklist.insert(Succ);
625  else
626  ExitWorklist.insert({BB, Succ});
627  AddCostRecursively(*TI, Iteration);
628  }
629 
630  // If we found no optimization opportunities on the first iteration, we
631  // won't find them on later ones too.
632  if (UnrolledCost == RolledDynamicCost) {
633  LLVM_DEBUG(dbgs() << " No opportunities found.. exiting.\n"
634  << " UnrolledCost: " << UnrolledCost << "\n");
635  return None;
636  }
637  }
638 
639  while (!ExitWorklist.empty()) {
640  BasicBlock *ExitingBB, *ExitBB;
641  std::tie(ExitingBB, ExitBB) = ExitWorklist.pop_back_val();
642 
643  for (Instruction &I : *ExitBB) {
644  auto *PN = dyn_cast<PHINode>(&I);
645  if (!PN)
646  break;
647 
648  Value *Op = PN->getIncomingValueForBlock(ExitingBB);
649  if (auto *OpI = dyn_cast<Instruction>(Op))
650  if (L->contains(OpI))
651  AddCostRecursively(*OpI, TripCount - 1);
652  }
653  }
654 
655  assert(UnrolledCost.isValid() && RolledDynamicCost.isValid() &&
656  "All instructions must have a valid cost, whether the "
657  "loop is rolled or unrolled.");
658 
659  LLVM_DEBUG(dbgs() << "Analysis finished:\n"
660  << "UnrolledCost: " << UnrolledCost << ", "
661  << "RolledDynamicCost: " << RolledDynamicCost << "\n");
662  return {{unsigned(*UnrolledCost.getValue()),
663  unsigned(*RolledDynamicCost.getValue())}};
664 }
665 
666 /// ApproximateLoopSize - Approximate the size of the loop.
668  const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent,
669  const TargetTransformInfo &TTI,
670  const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns) {
672  for (BasicBlock *BB : L->blocks())
673  Metrics.analyzeBasicBlock(BB, TTI, EphValues);
674  NumCalls = Metrics.NumInlineCandidates;
675  NotDuplicatable = Metrics.notDuplicatable;
676  Convergent = Metrics.convergent;
677 
678  unsigned LoopSize = Metrics.NumInsts;
679 
680  // Don't allow an estimate of size zero. This would allows unrolling of loops
681  // with huge iteration counts, which is a compile time problem even if it's
682  // not a problem for code quality. Also, the code using this size may assume
683  // that each loop has at least three instructions (likely a conditional
684  // branch, a comparison feeding that branch, and some kind of loop increment
685  // feeding that comparison instruction).
686  LoopSize = std::max(LoopSize, BEInsns + 1);
687 
688  return LoopSize;
689 }
690 
691 // Returns the loop hint metadata node with the given name (for example,
692 // "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
693 // returned.
695  if (MDNode *LoopID = L->getLoopID())
696  return GetUnrollMetadata(LoopID, Name);
697  return nullptr;
698 }
699 
700 // Returns true if the loop has an unroll(full) pragma.
701 static bool hasUnrollFullPragma(const Loop *L) {
702  return getUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
703 }
704 
705 // Returns true if the loop has an unroll(enable) pragma. This metadata is used
706 // for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
707 static bool hasUnrollEnablePragma(const Loop *L) {
708  return getUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
709 }
710 
711 // Returns true if the loop has an runtime unroll(disable) pragma.
712 static bool hasRuntimeUnrollDisablePragma(const Loop *L) {
713  return getUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
714 }
715 
716 // If loop has an unroll_count pragma return the (necessarily
717 // positive) value from the pragma. Otherwise return 0.
718 static unsigned unrollCountPragmaValue(const Loop *L) {
719  MDNode *MD = getUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
720  if (MD) {
721  assert(MD->getNumOperands() == 2 &&
722  "Unroll count hint metadata should have two operands.");
723  unsigned Count =
724  mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
725  assert(Count >= 1 && "Unroll count must be positive.");
726  return Count;
727  }
728  return 0;
729 }
730 
731 // Computes the boosting factor for complete unrolling.
732 // If fully unrolling the loop would save a lot of RolledDynamicCost, it would
733 // be beneficial to fully unroll the loop even if unrolledcost is large. We
734 // use (RolledDynamicCost / UnrolledCost) to model the unroll benefits to adjust
735 // the unroll threshold.
736 static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost,
737  unsigned MaxPercentThresholdBoost) {
738  if (Cost.RolledDynamicCost >= std::numeric_limits<unsigned>::max() / 100)
739  return 100;
740  else if (Cost.UnrolledCost != 0)
741  // The boosting factor is RolledDynamicCost / UnrolledCost
742  return std::min(100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
743  MaxPercentThresholdBoost);
744  else
745  return MaxPercentThresholdBoost;
746 }
747 
748 // Produce an estimate of the unrolled cost of the specified loop. This
749 // is used to a) produce a cost estimate for partial unrolling and b) to
750 // cheaply estimate cost for full unrolling when we don't want to symbolically
751 // evaluate all iterations.
753  const unsigned LoopSize;
754 
755 public:
756  UnrollCostEstimator(Loop &L, unsigned LoopSize) : LoopSize(LoopSize) {}
757 
758  // Returns loop size estimation for unrolled loop, given the unrolling
759  // configuration specified by UP.
760  uint64_t
762  const unsigned CountOverwrite = 0) const {
763  assert(LoopSize >= UP.BEInsns &&
764  "LoopSize should not be less than BEInsns!");
765  if (CountOverwrite)
766  return static_cast<uint64_t>(LoopSize - UP.BEInsns) * CountOverwrite +
767  UP.BEInsns;
768  else
769  return static_cast<uint64_t>(LoopSize - UP.BEInsns) * UP.Count +
770  UP.BEInsns;
771  }
772 };
773 
774 static Optional<unsigned>
775 shouldPragmaUnroll(Loop *L, const PragmaInfo &PInfo,
776  const unsigned TripMultiple, const unsigned TripCount,
777  const UnrollCostEstimator UCE,
779 
780  // Using unroll pragma
781  // 1st priority is unroll count set by "unroll-count" option.
782 
783  if (PInfo.UserUnrollCount) {
784  if (UP.AllowRemainder &&
785  UCE.getUnrolledLoopSize(UP, (unsigned)UnrollCount) < UP.Threshold)
786  return (unsigned)UnrollCount;
787  }
788 
789  // 2nd priority is unroll count set by pragma.
790  if (PInfo.PragmaCount > 0) {
791  if ((UP.AllowRemainder || (TripMultiple % PInfo.PragmaCount == 0)) &&
792  UCE.getUnrolledLoopSize(UP, PInfo.PragmaCount) < PragmaUnrollThreshold)
793  return PInfo.PragmaCount;
794  }
795 
796  if (PInfo.PragmaFullUnroll && TripCount != 0) {
797  if (UCE.getUnrolledLoopSize(UP, TripCount) < PragmaUnrollThreshold)
798  return TripCount;
799  }
800  // if didn't return until here, should continue to other priorties
801  return None;
802 }
803 
805  Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT,
806  ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
807  const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE,
809  assert(FullUnrollTripCount && "should be non-zero!");
810 
811  if (FullUnrollTripCount > UP.FullUnrollMaxCount)
812  return None;
813 
814  // When computing the unrolled size, note that BEInsns are not replicated
815  // like the rest of the loop body.
816  if (UCE.getUnrolledLoopSize(UP) < UP.Threshold)
817  return FullUnrollTripCount;
818 
819  // The loop isn't that small, but we still can fully unroll it if that
820  // helps to remove a significant number of instructions.
821  // To check that, run additional analysis on the loop.
823  L, FullUnrollTripCount, DT, SE, EphValues, TTI,
824  UP.Threshold * UP.MaxPercentThresholdBoost / 100,
826  unsigned Boost =
828  if (Cost->UnrolledCost < UP.Threshold * Boost / 100)
829  return FullUnrollTripCount;
830  }
831  return None;
832 }
833 
834 static Optional<unsigned>
835 shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount,
836  const UnrollCostEstimator UCE,
838 
839  if (!TripCount)
840  return None;
841 
842  if (!UP.Partial) {
843  LLVM_DEBUG(dbgs() << " will not try to unroll partially because "
844  << "-unroll-allow-partial not given\n");
845  return 0;
846  }
847  unsigned count = UP.Count;
848  if (count == 0)
849  count = TripCount;
850  if (UP.PartialThreshold != NoThreshold) {
851  // Reduce unroll count to be modulo of TripCount for partial unrolling.
852  if (UCE.getUnrolledLoopSize(UP, count) > UP.PartialThreshold)
853  count = (std::max(UP.PartialThreshold, UP.BEInsns + 1) - UP.BEInsns) /
854  (LoopSize - UP.BEInsns);
855  if (count > UP.MaxCount)
856  count = UP.MaxCount;
857  while (count != 0 && TripCount % count != 0)
858  count--;
859  if (UP.AllowRemainder && count <= 1) {
860  // If there is no Count that is modulo of TripCount, set Count to
861  // largest power-of-two factor that satisfies the threshold limit.
862  // As we'll create fixup loop, do the type of unrolling only if
863  // remainder loop is allowed.
865  while (count != 0 &&
867  count >>= 1;
868  }
869  if (count < 2) {
870  count = 0;
871  }
872  } else {
873  count = TripCount;
874  }
875  if (count > UP.MaxCount)
876  count = UP.MaxCount;
877 
878  LLVM_DEBUG(dbgs() << " partially unrolling with count: " << count << "\n");
879 
880  return count;
881 }
882 // Returns true if unroll count was set explicitly.
883 // Calculates unroll count and writes it to UP.Count.
884 // Unless IgnoreUser is true, will also use metadata and command-line options
885 // that are specific to to the LoopUnroll pass (which, for instance, are
886 // irrelevant for the LoopUnrollAndJam pass).
887 // FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
888 // many LoopUnroll-specific options. The shared functionality should be
889 // refactored into it own function.
891  Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
892  ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
893  OptimizationRemarkEmitter *ORE, unsigned TripCount, unsigned MaxTripCount,
894  bool MaxOrZero, unsigned TripMultiple, unsigned LoopSize,
896  TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound) {
897 
898  UnrollCostEstimator UCE(*L, LoopSize);
899 
900  const bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
901  const bool PragmaFullUnroll = hasUnrollFullPragma(L);
902  const unsigned PragmaCount = unrollCountPragmaValue(L);
903  const bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
904 
905  const bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
906  PragmaEnableUnroll || UserUnrollCount;
907 
908  PragmaInfo PInfo(UserUnrollCount, PragmaFullUnroll, PragmaCount,
909  PragmaEnableUnroll);
910  // Use an explicit peel count that has been specified for testing. In this
911  // case it's not permitted to also specify an explicit unroll count.
912  if (PP.PeelCount) {
913  if (UnrollCount.getNumOccurrences() > 0) {
914  report_fatal_error("Cannot specify both explicit peel count and "
915  "explicit unroll count");
916  }
917  UP.Count = 1;
918  UP.Runtime = false;
919  return true;
920  }
921  // Check for explicit Count.
922  // 1st priority is unroll count set by "unroll-count" option.
923  // 2nd priority is unroll count set by pragma.
924  if (auto UnrollFactor = shouldPragmaUnroll(L, PInfo, TripMultiple, TripCount,
925  UCE, UP)) {
926  UP.Count = *UnrollFactor;
927 
928  if (UserUnrollCount || (PragmaCount > 0)) {
929  UP.AllowExpensiveTripCount = true;
930  UP.Force = true;
931  }
932  UP.Runtime |= (PragmaCount > 0);
933  return ExplicitUnroll;
934  } else {
935  if (ExplicitUnroll && TripCount != 0) {
936  // If the loop has an unrolling pragma, we want to be more aggressive with
937  // unrolling limits. Set thresholds to at least the PragmaUnrollThreshold
938  // value which is larger than the default limits.
939  UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
940  UP.PartialThreshold =
941  std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
942  }
943  }
944 
945  // 3rd priority is exact full unrolling. This will eliminate all copies
946  // of some exit test.
947  UP.Count = 0;
948  if (TripCount) {
949  UP.Count = TripCount;
950  if (auto UnrollFactor = shouldFullUnroll(L, TTI, DT, SE, EphValues,
951  TripCount, UCE, UP)) {
952  UP.Count = *UnrollFactor;
953  UseUpperBound = false;
954  return ExplicitUnroll;
955  }
956  }
957 
958  // 4th priority is bounded unrolling.
959  // We can unroll by the upper bound amount if it's generally allowed or if
960  // we know that the loop is executed either the upper bound or zero times.
961  // (MaxOrZero unrolling keeps only the first loop test, so the number of
962  // loop tests remains the same compared to the non-unrolled version, whereas
963  // the generic upper bound unrolling keeps all but the last loop test so the
964  // number of loop tests goes up which may end up being worse on targets with
965  // constrained branch predictor resources so is controlled by an option.)
966  // In addition we only unroll small upper bounds.
967  // Note that the cost of bounded unrolling is always strictly greater than
968  // cost of exact full unrolling. As such, if we have an exact count and
969  // found it unprofitable, we'll never chose to bounded unroll.
970  if (!TripCount && MaxTripCount && (UP.UpperBound || MaxOrZero) &&
971  MaxTripCount <= UnrollMaxUpperBound) {
972  UP.Count = MaxTripCount;
973  if (auto UnrollFactor = shouldFullUnroll(L, TTI, DT, SE, EphValues,
974  MaxTripCount, UCE, UP)) {
975  UP.Count = *UnrollFactor;
976  UseUpperBound = true;
977  return ExplicitUnroll;
978  }
979  }
980 
981  // 5th priority is loop peeling.
982  computePeelCount(L, LoopSize, PP, TripCount, DT, SE, UP.Threshold);
983  if (PP.PeelCount) {
984  UP.Runtime = false;
985  UP.Count = 1;
986  return ExplicitUnroll;
987  }
988 
989  // Before starting partial unrolling, set up.partial to true,
990  // if user explicitly asked for unrolling
991  if (TripCount)
992  UP.Partial |= ExplicitUnroll;
993 
994  // 6th priority is partial unrolling.
995  // Try partial unroll only when TripCount could be statically calculated.
996  if (auto UnrollFactor = shouldPartialUnroll(LoopSize, TripCount, UCE, UP)) {
997  UP.Count = *UnrollFactor;
998 
999  if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
1000  UP.Count != TripCount)
1001  ORE->emit([&]() {
1003  "FullUnrollAsDirectedTooLarge",
1004  L->getStartLoc(), L->getHeader())
1005  << "Unable to fully unroll loop as directed by unroll pragma "
1006  "because "
1007  "unrolled size is too large.";
1008  });
1009 
1010  if (UP.PartialThreshold != NoThreshold) {
1011  if (UP.Count == 0) {
1012  if (PragmaEnableUnroll)
1013  ORE->emit([&]() {
1015  "UnrollAsDirectedTooLarge",
1016  L->getStartLoc(), L->getHeader())
1017  << "Unable to unroll loop as directed by unroll(enable) "
1018  "pragma "
1019  "because unrolled size is too large.";
1020  });
1021  }
1022  }
1023  return ExplicitUnroll;
1024  }
1025  assert(TripCount == 0 &&
1026  "All cases when TripCount is constant should be covered here.");
1027  if (PragmaFullUnroll)
1028  ORE->emit([&]() {
1029  return OptimizationRemarkMissed(
1030  DEBUG_TYPE, "CantFullUnrollAsDirectedRuntimeTripCount",
1031  L->getStartLoc(), L->getHeader())
1032  << "Unable to fully unroll loop as directed by unroll(full) "
1033  "pragma "
1034  "because loop has a runtime trip count.";
1035  });
1036 
1037  // 7th priority is runtime unrolling.
1038  // Don't unroll a runtime trip count loop when it is disabled.
1040  UP.Count = 0;
1041  return false;
1042  }
1043 
1044  // Don't unroll a small upper bound loop unless user or TTI asked to do so.
1045  if (MaxTripCount && !UP.Force && MaxTripCount < UnrollMaxUpperBound) {
1046  UP.Count = 0;
1047  return false;
1048  }
1049 
1050  // Check if the runtime trip count is too small when profile is available.
1051  if (L->getHeader()->getParent()->hasProfileData()) {
1052  if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
1053  if (*ProfileTripCount < FlatLoopTripCountThreshold)
1054  return false;
1055  else
1056  UP.AllowExpensiveTripCount = true;
1057  }
1058  }
1059  UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
1060  if (!UP.Runtime) {
1061  LLVM_DEBUG(
1062  dbgs() << " will not try to unroll loop with runtime trip count "
1063  << "-unroll-runtime not given\n");
1064  UP.Count = 0;
1065  return false;
1066  }
1067  if (UP.Count == 0)
1069 
1070  // Reduce unroll count to be the largest power-of-two factor of
1071  // the original count which satisfies the threshold limit.
1072  while (UP.Count != 0 &&
1074  UP.Count >>= 1;
1075 
1076 #ifndef NDEBUG
1077  unsigned OrigCount = UP.Count;
1078 #endif
1079 
1080  if (!UP.AllowRemainder && UP.Count != 0 && (TripMultiple % UP.Count) != 0) {
1081  while (UP.Count != 0 && TripMultiple % UP.Count != 0)
1082  UP.Count >>= 1;
1083  LLVM_DEBUG(
1084  dbgs() << "Remainder loop is restricted (that could architecture "
1085  "specific or because the loop contains a convergent "
1086  "instruction), so unroll count must divide the trip "
1087  "multiple, "
1088  << TripMultiple << ". Reducing unroll count from " << OrigCount
1089  << " to " << UP.Count << ".\n");
1090 
1091  using namespace ore;
1092 
1093  if (unrollCountPragmaValue(L) > 0 && !UP.AllowRemainder)
1094  ORE->emit([&]() {
1096  "DifferentUnrollCountFromDirected",
1097  L->getStartLoc(), L->getHeader())
1098  << "Unable to unroll loop the number of times directed by "
1099  "unroll_count pragma because remainder loop is restricted "
1100  "(that could architecture specific or because the loop "
1101  "contains a convergent instruction) and so must have an "
1102  "unroll "
1103  "count that divides the loop trip multiple of "
1104  << NV("TripMultiple", TripMultiple) << ". Unrolling instead "
1105  << NV("UnrollCount", UP.Count) << " time(s).";
1106  });
1107  }
1108 
1109  if (UP.Count > UP.MaxCount)
1110  UP.Count = UP.MaxCount;
1111 
1112  if (MaxTripCount && UP.Count > MaxTripCount)
1113  UP.Count = MaxTripCount;
1114 
1115  LLVM_DEBUG(dbgs() << " runtime unrolling with count: " << UP.Count
1116  << "\n");
1117  if (UP.Count < 2)
1118  UP.Count = 0;
1119  return ExplicitUnroll;
1120 }
1121 
1123  Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
1126  ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel,
1127  bool OnlyWhenForced, bool ForgetAllSCEV, Optional<unsigned> ProvidedCount,
1128  Optional<unsigned> ProvidedThreshold, Optional<bool> ProvidedAllowPartial,
1129  Optional<bool> ProvidedRuntime, Optional<bool> ProvidedUpperBound,
1130  Optional<bool> ProvidedAllowPeeling,
1131  Optional<bool> ProvidedAllowProfileBasedPeeling,
1132  Optional<unsigned> ProvidedFullUnrollMaxCount) {
1133  LLVM_DEBUG(dbgs() << "Loop Unroll: F["
1134  << L->getHeader()->getParent()->getName() << "] Loop %"
1135  << L->getHeader()->getName() << "\n");
1137  if (TM & TM_Disable)
1139 
1140  // If this loop isn't forced to be unrolled, avoid unrolling it when the
1141  // parent loop has an explicit unroll-and-jam pragma. This is to prevent
1142  // automatic unrolling from interfering with the user requested
1143  // transformation.
1144  Loop *ParentL = L->getParentLoop();
1145  if (ParentL != nullptr &&
1148  LLVM_DEBUG(dbgs() << "Not unrolling loop since parent loop has"
1149  << " llvm.loop.unroll_and_jam.\n");
1151  }
1152 
1153  // If this loop isn't forced to be unrolled, avoid unrolling it when the
1154  // loop has an explicit unroll-and-jam pragma. This is to prevent automatic
1155  // unrolling from interfering with the user requested transformation.
1158  LLVM_DEBUG(
1159  dbgs()
1160  << " Not unrolling loop since it has llvm.loop.unroll_and_jam.\n");
1162  }
1163 
1164  if (!L->isLoopSimplifyForm()) {
1165  LLVM_DEBUG(
1166  dbgs() << " Not unrolling loop which is not in loop-simplify form.\n");
1168  }
1169 
1170  // When automatic unrolling is disabled, do not unroll unless overridden for
1171  // this loop.
1172  if (OnlyWhenForced && !(TM & TM_Enable))
1174 
1175  bool OptForSize = L->getHeader()->getParent()->hasOptSize();
1176  unsigned NumInlineCandidates;
1177  bool NotDuplicatable;
1178  bool Convergent;
1180  L, SE, TTI, BFI, PSI, ORE, OptLevel, ProvidedThreshold, ProvidedCount,
1181  ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1182  ProvidedFullUnrollMaxCount);
1184  L, SE, TTI, ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling, true);
1185 
1186  // Exit early if unrolling is disabled. For OptForSize, we pick the loop size
1187  // as threshold later on.
1188  if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0) &&
1189  !OptForSize)
1191 
1193  CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
1194 
1195  unsigned LoopSize =
1196  ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
1197  TTI, EphValues, UP.BEInsns);
1198  LLVM_DEBUG(dbgs() << " Loop Size = " << LoopSize << "\n");
1199  if (NotDuplicatable) {
1200  LLVM_DEBUG(dbgs() << " Not unrolling loop which contains non-duplicatable"
1201  << " instructions.\n");
1203  }
1204 
1205  // When optimizing for size, use LoopSize + 1 as threshold (we use < Threshold
1206  // later), to (fully) unroll loops, if it does not increase code size.
1207  if (OptForSize)
1208  UP.Threshold = std::max(UP.Threshold, LoopSize + 1);
1209 
1210  if (NumInlineCandidates != 0) {
1211  LLVM_DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n");
1213  }
1214 
1215  // Find the smallest exact trip count for any exit. This is an upper bound
1216  // on the loop trip count, but an exit at an earlier iteration is still
1217  // possible. An unroll by the smallest exact trip count guarantees that all
1218  // brnaches relating to at least one exit can be eliminated. This is unlike
1219  // the max trip count, which only guarantees that the backedge can be broken.
1220  unsigned TripCount = 0;
1221  unsigned TripMultiple = 1;
1222  SmallVector<BasicBlock *, 8> ExitingBlocks;
1223  L->getExitingBlocks(ExitingBlocks);
1224  for (BasicBlock *ExitingBlock : ExitingBlocks)
1225  if (unsigned TC = SE.getSmallConstantTripCount(L, ExitingBlock))
1226  if (!TripCount || TC < TripCount)
1227  TripCount = TripMultiple = TC;
1228 
1229  if (!TripCount) {
1230  // If no exact trip count is known, determine the trip multiple of either
1231  // the loop latch or the single exiting block.
1232  // TODO: Relax for multiple exits.
1233  BasicBlock *ExitingBlock = L->getLoopLatch();
1234  if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
1235  ExitingBlock = L->getExitingBlock();
1236  if (ExitingBlock)
1237  TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
1238  }
1239 
1240  // If the loop contains a convergent operation, the prelude we'd add
1241  // to do the first few instructions before we hit the unrolled loop
1242  // is unsafe -- it adds a control-flow dependency to the convergent
1243  // operation. Therefore restrict remainder loop (try unrolling without).
1244  //
1245  // TODO: This is quite conservative. In practice, convergent_op()
1246  // is likely to be called unconditionally in the loop. In this
1247  // case, the program would be ill-formed (on most architectures)
1248  // unless n were the same on all threads in a thread group.
1249  // Assuming n is the same on all threads, any kind of unrolling is
1250  // safe. But currently llvm's notion of convergence isn't powerful
1251  // enough to express this.
1252  if (Convergent)
1253  UP.AllowRemainder = false;
1254 
1255  // Try to find the trip count upper bound if we cannot find the exact trip
1256  // count.
1257  unsigned MaxTripCount = 0;
1258  bool MaxOrZero = false;
1259  if (!TripCount) {
1260  MaxTripCount = SE.getSmallConstantMaxTripCount(L);
1261  MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
1262  }
1263 
1264  // computeUnrollCount() decides whether it is beneficial to use upper bound to
1265  // fully unroll the loop.
1266  bool UseUpperBound = false;
1267  bool IsCountSetExplicitly = computeUnrollCount(
1268  L, TTI, DT, LI, SE, EphValues, &ORE, TripCount, MaxTripCount, MaxOrZero,
1269  TripMultiple, LoopSize, UP, PP, UseUpperBound);
1270  if (!UP.Count)
1272 
1273  if (PP.PeelCount) {
1274  assert(UP.Count == 1 && "Cannot perform peel and unroll in the same step");
1275  LLVM_DEBUG(dbgs() << "PEELING loop %" << L->getHeader()->getName()
1276  << " with iteration count " << PP.PeelCount << "!\n");
1277  ORE.emit([&]() {
1278  return OptimizationRemark(DEBUG_TYPE, "Peeled", L->getStartLoc(),
1279  L->getHeader())
1280  << " peeled loop by " << ore::NV("PeelCount", PP.PeelCount)
1281  << " iterations";
1282  });
1283 
1284  if (peelLoop(L, PP.PeelCount, LI, &SE, &DT, &AC, PreserveLCSSA)) {
1285  simplifyLoopAfterUnroll(L, true, LI, &SE, &DT, &AC, &TTI);
1286  // If the loop was peeled, we already "used up" the profile information
1287  // we had, so we don't want to unroll or peel again.
1288  if (PP.PeelProfiledIterations)
1291  }
1293  }
1294 
1295  // At this point, UP.Runtime indicates that run-time unrolling is allowed.
1296  // However, we only want to actually perform it if we don't know the trip
1297  // count and the unroll count doesn't divide the known trip multiple.
1298  // TODO: This decision should probably be pushed up into
1299  // computeUnrollCount().
1300  UP.Runtime &= TripCount == 0 && TripMultiple % UP.Count != 0;
1301 
1302  // Save loop properties before it is transformed.
1303  MDNode *OrigLoopID = L->getLoopID();
1304 
1305  // Unroll the loop.
1306  Loop *RemainderLoop = nullptr;
1307  LoopUnrollResult UnrollResult = UnrollLoop(
1308  L,
1309  {UP.Count, UP.Force, UP.Runtime, UP.AllowExpensiveTripCount,
1310  UP.UnrollRemainder, ForgetAllSCEV},
1311  LI, &SE, &DT, &AC, &TTI, &ORE, PreserveLCSSA, &RemainderLoop);
1312  if (UnrollResult == LoopUnrollResult::Unmodified)
1314 
1315  if (RemainderLoop) {
1316  Optional<MDNode *> RemainderLoopID =
1319  if (RemainderLoopID.hasValue())
1320  RemainderLoop->setLoopID(RemainderLoopID.getValue());
1321  }
1322 
1323  if (UnrollResult != LoopUnrollResult::FullyUnrolled) {
1324  Optional<MDNode *> NewLoopID =
1327  if (NewLoopID.hasValue()) {
1328  L->setLoopID(NewLoopID.getValue());
1329 
1330  // Do not setLoopAlreadyUnrolled if loop attributes have been specified
1331  // explicitly.
1332  return UnrollResult;
1333  }
1334  }
1335 
1336  // If loop has an unroll count pragma or unrolled by explicitly set count
1337  // mark loop as unrolled to prevent unrolling beyond that requested.
1338  if (UnrollResult != LoopUnrollResult::FullyUnrolled && IsCountSetExplicitly)
1340 
1341  return UnrollResult;
1342 }
1343 
1344 namespace {
1345 
1346 class LoopUnroll : public LoopPass {
1347 public:
1348  static char ID; // Pass ID, replacement for typeid
1349 
1350  int OptLevel;
1351 
1352  /// If false, use a cost model to determine whether unrolling of a loop is
1353  /// profitable. If true, only loops that explicitly request unrolling via
1354  /// metadata are considered. All other loops are skipped.
1355  bool OnlyWhenForced;
1356 
1357  /// If false, when SCEV is invalidated, only forget everything in the
1358  /// top-most loop (call forgetTopMostLoop), of the loop being processed.
1359  /// Otherwise, forgetAllLoops and rebuild when needed next.
1360  bool ForgetAllSCEV;
1361 
1362  Optional<unsigned> ProvidedCount;
1363  Optional<unsigned> ProvidedThreshold;
1364  Optional<bool> ProvidedAllowPartial;
1365  Optional<bool> ProvidedRuntime;
1366  Optional<bool> ProvidedUpperBound;
1367  Optional<bool> ProvidedAllowPeeling;
1368  Optional<bool> ProvidedAllowProfileBasedPeeling;
1369  Optional<unsigned> ProvidedFullUnrollMaxCount;
1370 
1371  LoopUnroll(int OptLevel = 2, bool OnlyWhenForced = false,
1372  bool ForgetAllSCEV = false, Optional<unsigned> Threshold = None,
1373  Optional<unsigned> Count = None,
1374  Optional<bool> AllowPartial = None, Optional<bool> Runtime = None,
1375  Optional<bool> UpperBound = None,
1376  Optional<bool> AllowPeeling = None,
1377  Optional<bool> AllowProfileBasedPeeling = None,
1378  Optional<unsigned> ProvidedFullUnrollMaxCount = None)
1379  : LoopPass(ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
1380  ForgetAllSCEV(ForgetAllSCEV), ProvidedCount(std::move(Count)),
1381  ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
1382  ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound),
1383  ProvidedAllowPeeling(AllowPeeling),
1384  ProvidedAllowProfileBasedPeeling(AllowProfileBasedPeeling),
1385  ProvidedFullUnrollMaxCount(ProvidedFullUnrollMaxCount) {
1387  }
1388 
1389  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1390  if (skipLoop(L))
1391  return false;
1392 
1393  Function &F = *L->getHeader()->getParent();
1394 
1395  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1396  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1397  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1398  const TargetTransformInfo &TTI =
1399  getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1400  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1401  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
1402  // pass. Function analyses need to be preserved across loop transformations
1403  // but ORE cannot be preserved (see comment before the pass definition).
1405  bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1406 
1408  L, DT, LI, SE, TTI, AC, ORE, nullptr, nullptr, PreserveLCSSA, OptLevel,
1409  OnlyWhenForced, ForgetAllSCEV, ProvidedCount, ProvidedThreshold,
1410  ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1411  ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling,
1412  ProvidedFullUnrollMaxCount);
1413 
1414  if (Result == LoopUnrollResult::FullyUnrolled)
1415  LPM.markLoopAsDeleted(*L);
1416 
1418  }
1419 
1420  /// This transformation requires natural loop information & requires that
1421  /// loop preheaders be inserted into the CFG...
1422  void getAnalysisUsage(AnalysisUsage &AU) const override {
1425  // FIXME: Loop passes are required to preserve domtree, and for now we just
1426  // recreate dom info if anything gets unrolled.
1428  }
1429 };
1430 
1431 } // end anonymous namespace
1432 
1433 char LoopUnroll::ID = 0;
1434 
1435 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1439 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1440 
1441 Pass *llvm::createLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
1442  bool ForgetAllSCEV, int Threshold, int Count,
1443  int AllowPartial, int Runtime, int UpperBound,
1444  int AllowPeeling) {
1445  // TODO: It would make more sense for this function to take the optionals
1446  // directly, but that's dangerous since it would silently break out of tree
1447  // callers.
1448  return new LoopUnroll(
1449  OptLevel, OnlyWhenForced, ForgetAllSCEV,
1451  Count == -1 ? None : Optional<unsigned>(Count),
1452  AllowPartial == -1 ? None : Optional<bool>(AllowPartial),
1453  Runtime == -1 ? None : Optional<bool>(Runtime),
1454  UpperBound == -1 ? None : Optional<bool>(UpperBound),
1455  AllowPeeling == -1 ? None : Optional<bool>(AllowPeeling));
1456 }
1457 
1458 Pass *llvm::createSimpleLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
1459  bool ForgetAllSCEV) {
1460  return createLoopUnrollPass(OptLevel, OnlyWhenForced, ForgetAllSCEV, -1, -1,
1461  0, 0, 0, 1);
1462 }
1463 
1466  LPMUpdater &Updater) {
1467  // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
1468  // pass. Function analyses need to be preserved across loop transformations
1469  // but ORE cannot be preserved (see comment before the pass definition).
1471 
1472  // Keep track of the previous loop structure so we can identify new loops
1473  // created by unrolling.
1474  Loop *ParentL = L.getParentLoop();
1475  SmallPtrSet<Loop *, 4> OldLoops;
1476  if (ParentL)
1477  OldLoops.insert(ParentL->begin(), ParentL->end());
1478  else
1479  OldLoops.insert(AR.LI.begin(), AR.LI.end());
1480 
1481  std::string LoopName = std::string(L.getName());
1482 
1483  bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, ORE,
1484  /*BFI*/ nullptr, /*PSI*/ nullptr,
1485  /*PreserveLCSSA*/ true, OptLevel,
1486  OnlyWhenForced, ForgetSCEV, /*Count*/ None,
1487  /*Threshold*/ None, /*AllowPartial*/ false,
1488  /*Runtime*/ false, /*UpperBound*/ false,
1489  /*AllowPeeling*/ true,
1490  /*AllowProfileBasedPeeling*/ false,
1491  /*FullUnrollMaxCount*/ None) !=
1493  if (!Changed)
1494  return PreservedAnalyses::all();
1495 
1496  // The parent must not be damaged by unrolling!
1497 #ifndef NDEBUG
1498  if (ParentL)
1499  ParentL->verifyLoop();
1500 #endif
1501 
1502  // Unrolling can do several things to introduce new loops into a loop nest:
1503  // - Full unrolling clones child loops within the current loop but then
1504  // removes the current loop making all of the children appear to be new
1505  // sibling loops.
1506  //
1507  // When a new loop appears as a sibling loop after fully unrolling,
1508  // its nesting structure has fundamentally changed and we want to revisit
1509  // it to reflect that.
1510  //
1511  // When unrolling has removed the current loop, we need to tell the
1512  // infrastructure that it is gone.
1513  //
1514  // Finally, we support a debugging/testing mode where we revisit child loops
1515  // as well. These are not expected to require further optimizations as either
1516  // they or the loop they were cloned from have been directly visited already.
1517  // But the debugging mode allows us to check this assumption.
1518  bool IsCurrentLoopValid = false;
1519  SmallVector<Loop *, 4> SibLoops;
1520  if (ParentL)
1521  SibLoops.append(ParentL->begin(), ParentL->end());
1522  else
1523  SibLoops.append(AR.LI.begin(), AR.LI.end());
1524  erase_if(SibLoops, [&](Loop *SibLoop) {
1525  if (SibLoop == &L) {
1526  IsCurrentLoopValid = true;
1527  return true;
1528  }
1529 
1530  // Otherwise erase the loop from the list if it was in the old loops.
1531  return OldLoops.contains(SibLoop);
1532  });
1533  Updater.addSiblingLoops(SibLoops);
1534 
1535  if (!IsCurrentLoopValid) {
1536  Updater.markLoopAsDeleted(L, LoopName);
1537  } else {
1538  // We can only walk child loops if the current loop remained valid.
1540  // Walk *all* of the child loops.
1541  SmallVector<Loop *, 4> ChildLoops(L.begin(), L.end());
1542  Updater.addChildLoops(ChildLoops);
1543  }
1544  }
1545 
1547 }
1548 
1551  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1552  auto &LI = AM.getResult<LoopAnalysis>(F);
1553  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1554  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1555  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1557 
1558  LoopAnalysisManager *LAM = nullptr;
1559  if (auto *LAMProxy = AM.getCachedResult<LoopAnalysisManagerFunctionProxy>(F))
1560  LAM = &LAMProxy->getManager();
1561 
1562  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1563  ProfileSummaryInfo *PSI =
1564  MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
1565  auto *BFI = (PSI && PSI->hasProfileSummary()) ?
1566  &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
1567 
1568  bool Changed = false;
1569 
1570  // The unroller requires loops to be in simplified form, and also needs LCSSA.
1571  // Since simplification may add new inner loops, it has to run before the
1572  // legality and profitability checks. This means running the loop unroller
1573  // will simplify all loops, regardless of whether anything end up being
1574  // unrolled.
1575  for (auto &L : LI) {
1576  Changed |=
1577  simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);
1578  Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
1579  }
1580 
1581  // Add the loop nests in the reverse order of LoopInfo. See method
1582  // declaration.
1584  appendLoopsToWorklist(LI, Worklist);
1585 
1586  while (!Worklist.empty()) {
1587  // Because the LoopInfo stores the loops in RPO, we walk the worklist
1588  // from back to front so that we work forward across the CFG, which
1589  // for unrolling is only needed to get optimization remarks emitted in
1590  // a forward order.
1591  Loop &L = *Worklist.pop_back_val();
1592 #ifndef NDEBUG
1593  Loop *ParentL = L.getParentLoop();
1594 #endif
1595 
1596  // Check if the profile summary indicates that the profiled application
1597  // has a huge working set size, in which case we disable peeling to avoid
1598  // bloating it further.
1599  Optional<bool> LocalAllowPeeling = UnrollOpts.AllowPeeling;
1600  if (PSI && PSI->hasHugeWorkingSetSize())
1601  LocalAllowPeeling = false;
1602  std::string LoopName = std::string(L.getName());
1603  // The API here is quite complex to call and we allow to select some
1604  // flavors of unrolling during construction time (by setting UnrollOpts).
1606  &L, DT, &LI, SE, TTI, AC, ORE, BFI, PSI,
1607  /*PreserveLCSSA*/ true, UnrollOpts.OptLevel, UnrollOpts.OnlyWhenForced,
1608  UnrollOpts.ForgetSCEV, /*Count*/ None,
1609  /*Threshold*/ None, UnrollOpts.AllowPartial, UnrollOpts.AllowRuntime,
1610  UnrollOpts.AllowUpperBound, LocalAllowPeeling,
1611  UnrollOpts.AllowProfileBasedPeeling, UnrollOpts.FullUnrollMaxCount);
1612  Changed |= Result != LoopUnrollResult::Unmodified;
1613 
1614  // The parent must not be damaged by unrolling!
1615 #ifndef NDEBUG
1616  if (Result != LoopUnrollResult::Unmodified && ParentL)
1617  ParentL->verifyLoop();
1618 #endif
1619 
1620  // Clear any cached analysis results for L if we removed it completely.
1621  if (LAM && Result == LoopUnrollResult::FullyUnrolled)
1622  LAM->clear(L, LoopName);
1623  }
1624 
1625  if (!Changed)
1626  return PreservedAnalyses::all();
1627 
1629 }
1630 
1632  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1633  static_cast<PassInfoMixin<LoopUnrollPass> *>(this)->printPipeline(
1634  OS, MapClassName2PassName);
1635  OS << "<";
1636  if (UnrollOpts.AllowPartial != None)
1637  OS << (UnrollOpts.AllowPartial.getValue() ? "" : "no-") << "partial;";
1638  if (UnrollOpts.AllowPeeling != None)
1639  OS << (UnrollOpts.AllowPeeling.getValue() ? "" : "no-") << "peeling;";
1640  if (UnrollOpts.AllowRuntime != None)
1641  OS << (UnrollOpts.AllowRuntime.getValue() ? "" : "no-") << "runtime;";
1642  if (UnrollOpts.AllowUpperBound != None)
1643  OS << (UnrollOpts.AllowUpperBound.getValue() ? "" : "no-") << "upperbound;";
1644  if (UnrollOpts.AllowProfileBasedPeeling != None)
1645  OS << (UnrollOpts.AllowProfileBasedPeeling.getValue() ? "" : "no-")
1646  << "profile-peeling;";
1647  if (UnrollOpts.FullUnrollMaxCount != None)
1648  OS << "full-unroll-max=" << UnrollOpts.FullUnrollMaxCount << ";";
1649  OS << "O" << UnrollOpts.OptLevel;
1650  OS << ">";
1651 }
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
shouldFullUnroll
static Optional< unsigned > shouldFullUnroll(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
Definition: LoopUnrollPass.cpp:804
FlatLoopTripCountThreshold
static cl::opt< unsigned > FlatLoopTripCountThreshold("flat-loop-tripcount-threshold", cl::init(5), cl::Hidden, cl::desc("If the runtime tripcount for the loop is lower than the " "threshold, the loop is considered as flat and will be less " "aggressively unrolled."))
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1065
llvm::TargetTransformInfo::UnrollingPreferences::BEInsns
unsigned BEInsns
Definition: TargetTransformInfo.h:481
AssumptionCache.h
llvm::TargetTransformInfo::UnrollingPreferences::PartialOptSizeThreshold
unsigned PartialOptSizeThreshold
The cost threshold for the unrolled loop when optimizing for size, like OptSizeThreshold,...
Definition: TargetTransformInfo.h:460
llvm::hasUnrollTransformation
TransformationMode hasUnrollTransformation(const Loop *L)
Definition: LoopUtils.cpp:361
unrollCountPragmaValue
static unsigned unrollCountPragmaValue(const Loop *L)
Definition: LoopUnrollPass.cpp:718
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2418
llvm::TargetTransformInfo::UnrollingPreferences::Runtime
bool Runtime
Allow runtime unrolling (unrolling of loops to expand the size of the loop body even when the number ...
Definition: TargetTransformInfo.h:488
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:730
llvm::TargetTransformInfo::TargetCostKind
TargetCostKind
The kind of cost model.
Definition: TargetTransformInfo.h:211
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2109
llvm::TargetTransformInfo::UnrollingPreferences::PartialThreshold
unsigned PartialThreshold
The cost threshold for the unrolled loop, like Threshold, but used for partial/runtime unrolling (set...
Definition: TargetTransformInfo.h:456
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
LoopSimplify.h
llvm::LoopStandardAnalysisResults::AC
AssumptionCache & AC
Definition: LoopAnalysisManager.h:54
analyzeLoopUnrollCost
static Optional< EstimatedUnrollCost > analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize, unsigned MaxIterationsCountToAnalyze)
Figure out if the loop is worth full unrolling.
Definition: LoopUnrollPass.cpp:347
llvm::UnrolledInstAnalyzer
Definition: LoopUnrollAnalyzer.h:39
Optional.h
llvm::InstructionCost::getValue
Optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
Definition: InstructionCost.h:87
llvm::peelLoop
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA)
Peel off the first PeelCount iterations of loop L.
Definition: LoopPeel.cpp:739
Metadata.h
UnrollFullMaxCount
static cl::opt< unsigned > UnrollFullMaxCount("unroll-full-max-count", cl::Hidden, cl::desc("Set the max unroll count for full unrolling, for testing purposes"))
UnrollPartialThreshold
static cl::opt< unsigned > UnrollPartialThreshold("unroll-partial-threshold", cl::Hidden, cl::desc("The cost threshold for partial loop unrolling"))
llvm::TargetTransformInfo::UnrollingPreferences::MaxCount
unsigned MaxCount
Definition: TargetTransformInfo.h:472
getUnrollMetadataForLoop
static MDNode * getUnrollMetadataForLoop(const Loop *L, StringRef Name)
Definition: LoopUnrollPass.cpp:694
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
Scalar.h
llvm::PassInfoMixin< LoopUnrollPass >
llvm::ScalarEvolution::getSmallConstantTripMultiple
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
Definition: ScalarEvolution.cpp:7651
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
StringRef.h
llvm::LoopUnrollPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: LoopUnrollPass.cpp:1631
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1177
llvm::CodeMetrics
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:30
UnrollRevisitChildLoops
static cl::opt< bool > UnrollRevisitChildLoops("unroll-revisit-child-loops", cl::Hidden, cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. " "This shouldn't typically be needed as child loops (or their " "clones) were already visited."))
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::find
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
UnrollCostEstimator::getUnrolledLoopSize
uint64_t getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, const unsigned CountOverwrite=0) const
Definition: LoopUnrollPass.cpp:761
SizeOpts.h
llvm::LLVMLoopUnrollFollowupRemainder
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:44
ErrorHandling.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
LazyBlockFrequencyInfo.h
llvm::computePeelCount
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned &TripCount, DominatorTree &DT, ScalarEvolution &SE, unsigned Threshold=UINT_MAX)
Definition: LoopPeel.cpp:360
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:634
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1830
shouldPartialUnroll
static Optional< unsigned > shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
Definition: LoopUnrollPass.cpp:835
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
hasUnrollFullPragma
static bool hasUnrollFullPragma(const Loop *L)
Definition: LoopUnrollPass.cpp:701
llvm::makeFollowupLoopID
Optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:272
llvm::TargetTransformInfo::UnrollingPreferences::UnrollAndJamInnerLoopThreshold
unsigned UnrollAndJamInnerLoopThreshold
Threshold for unroll and jam, for inner loop size.
Definition: TargetTransformInfo.h:507
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::TargetTransformInfo::UnrollingPreferences::UnrollRemainder
bool UnrollRemainder
Allow unrolling of all the iterations of the runtime loop remainder.
Definition: TargetTransformInfo.h:500
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:150
UnrollRuntime
static cl::opt< bool > UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden, cl::desc("Unroll loops with run-time trip counts"))
llvm::TargetTransformInfo::UnrollingPreferences::Count
unsigned Count
A forced unrolling factor (the number of concatenated bodies of the original loop in the unrolled loo...
Definition: TargetTransformInfo.h:465
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:214
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::initializeLoopUnrollPass
void initializeLoopUnrollPass(PassRegistry &)
ScalarEvolution.h
llvm::TargetTransformInfo::UnrollingPreferences::Partial
bool Partial
Allow partial unrolling (unrolling of loops to expand the size of the loop body, not only to eliminat...
Definition: TargetTransformInfo.h:484
llvm::LoopUnrollOptions::ForgetSCEV
const bool ForgetSCEV
If true, forget all loops when unrolling.
Definition: LoopUnrollPass.h:78
DenseMap.h
llvm::TargetTransformInfo::PeelingPreferences
Definition: TargetTransformInfo.h:538
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::TargetTransformInfo::UnrollingPreferences::FullUnrollMaxCount
unsigned FullUnrollMaxCount
Set the maximum unrolling factor for full unrolling.
Definition: TargetTransformInfo.h:476
llvm::ApproximateLoopSize
unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, unsigned BEInsns)
ApproximateLoopSize - Approximate the size of the loop.
Definition: LoopUnrollPass.cpp:667
llvm::Optional< unsigned >
llvm::formLCSSARecursively
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:405
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:154
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::MCID::Convergent
@ Convergent
Definition: MCInstrDesc.h:182
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
llvm::computeUnrollCount
bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, OptimizationRemarkEmitter *ORE, unsigned TripCount, unsigned MaxTripCount, bool MaxOrZero, unsigned TripMultiple, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound)
Definition: LoopUnrollPass.cpp:890
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:644
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
UnrollMaxPercentThresholdBoost
static cl::opt< unsigned > UnrollMaxPercentThresholdBoost("unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden, cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied " "to the threshold when aggressively unrolling a loop due to the " "dynamic cost savings. If completely unrolling a loop will reduce " "the total runtime from X to Y, we boost the loop unroll " "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, " "X/Y). This limit avoids excessive code bloat."))
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
UnrollThresholdDefault
static cl::opt< unsigned > UnrollThresholdDefault("unroll-threshold-default", cl::init(150), cl::Hidden, cl::desc("Default threshold (max size of unrolled " "loop), used in all but O3 optimizations"))
loops
loops
Definition: LoopInfo.cpp:1176
llvm::TargetTransformInfo::UnrollingPreferences::AllowExpensiveTripCount
bool AllowExpensiveTripCount
Allow emitting expensive instructions (such as divisions) when computing the trip count of a loop for...
Definition: TargetTransformInfo.h:493
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1143
llvm::gatherUnrollingPreferences
TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, llvm::OptimizationRemarkEmitter &ORE, int OptLevel, Optional< unsigned > UserThreshold, Optional< unsigned > UserCount, Optional< bool > UserAllowPartial, Optional< bool > UserRuntime, Optional< bool > UserUpperBound, Optional< unsigned > UserFullUnrollMaxCount)
Gather the various unrolling parameters based on the defaults, compiler flags, TTI overrides and user...
Definition: LoopUnrollPass.cpp:185
LoopAnalysisManager.h
UnrollCount
static cl::opt< unsigned > UnrollCount("unroll-count", cl::Hidden, cl::desc("Use this unroll count for all loops including those with " "unroll_count pragma values, for testing purposes"))
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
llvm::TargetTransformInfo::getUnrollingPreferences
void getUnrollingPreferences(Loop *L, ScalarEvolution &, UnrollingPreferences &UP, OptimizationRemarkEmitter *ORE) const
Get target-customized preferences for the generic loop unrolling transformation.
Definition: TargetTransformInfo.cpp:325
UnrollThreshold
static cl::opt< unsigned > UnrollThreshold("unroll-threshold", cl::Hidden, cl::desc("The cost threshold for loop unrolling"))
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::LoopUnrollOptions::OnlyWhenForced
bool OnlyWhenForced
If false, use a cost model to determine whether unrolling of a loop is profitable.
Definition: LoopUnrollPass.h:73
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
Instruction.h
CommandLine.h
CodeMetrics.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::TM_Enable
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:271
llvm::DenseMapInfo< Instruction * >
llvm::TargetTransformInfo::PeelingPreferences::PeelProfiledIterations
bool PeelProfiledIterations
Allow peeling basing on profile.
Definition: TargetTransformInfo.h:551
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::shouldOptimizeForSize
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
Definition: MachineSizeOpts.cpp:183
llvm::Loop::setLoopAlreadyUnrolled
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:540
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::GetUnrollMetadata
MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)
Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...
Definition: LoopUnroll.cpp:848
Constants.h
UnrollMaxUpperBound
static cl::opt< unsigned > UnrollMaxUpperBound("unroll-max-upperbound", cl::init(8), cl::Hidden, cl::desc("The max of trip count upper bound that is considered in unrolling"))
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:657
llvm::TargetTransformInfo::UnrollingPreferences::Force
bool Force
Apply loop unroll on any kind of loop (mainly to loops that fail runtime unrolling).
Definition: TargetTransformInfo.h:496
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::AnalysisManager::clear
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
Definition: PassManagerImpl.h:36
llvm::LLVMLoopUnrollFollowupUnrolled
const char *const LLVMLoopUnrollFollowupUnrolled
Definition: UnrollLoop.h:42
UnrollAllowRemainder
static cl::opt< bool > UnrollAllowRemainder("unroll-allow-remainder", cl::Hidden, cl::desc("Allow generation of a loop remainder (extra iterations) " "when unrolling a loop."))
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: PriorityWorklist.h:154
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:155
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
DenseSet.h
llvm::TargetTransformInfo::UnrollingPreferences::MaxIterationsCountToAnalyze
unsigned MaxIterationsCountToAnalyze
Don't allow loop unrolling to simulate more than this number of iterations when checking full unroll ...
Definition: TargetTransformInfo.h:510
false
Definition: StackSlotColoring.cpp:142
llvm::simplifyLoopAfterUnroll
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI)
Perform some cleanup and simplifications on loops after unrolling.
Definition: LoopUnroll.cpp:215
llvm::TargetTransformInfo::UnrollingPreferences::UnrollAndJam
bool UnrollAndJam
Allow unroll and jam. Used to enable unroll and jam for the target.
Definition: TargetTransformInfo.h:502
llvm::LoopUnrollOptions::FullUnrollMaxCount
Optional< unsigned > FullUnrollMaxCount
Definition: LoopUnrollPass.h:67
llvm::Instruction
Definition: Instruction.h:45
llvm::LoopBase::verifyLoop
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:286
llvm::PGSOQueryType::IRPass
@ IRPass
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:143
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:402
LoopUtils.h
llvm::CodeMetrics::collectEphemeralValues
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:71
llvm::LPPassManager
Definition: LoopPass.h:75
SmallPtrSet.h
llvm::LoopUnrollOptions::AllowPeeling
Optional< bool > AllowPeeling
Definition: LoopUnrollPass.h:63
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
Utils.h
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:869
llvm::None
const NoneType None
Definition: None.h:23
llvm::LoopUnrollResult::FullyUnrolled
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::createSimpleLoopUnrollPass
Pass * createSimpleLoopUnrollPass(int OptLevel=2, bool OnlyWhenForced=false, bool ForgetAllSCEV=false)
Definition: LoopUnrollPass.cpp:1458
CFG.h
LoopInfo.h
llvm::LoopUnrollOptions::AllowUpperBound
Optional< bool > AllowUpperBound
Definition: LoopUnrollPass.h:65
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::cl::ZeroOrMore
@ ZeroOrMore
Definition: CommandLine.h:120
llvm::LLVMLoopUnrollFollowupAll
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:41
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:223
UnrollMaxCount
static cl::opt< unsigned > UnrollMaxCount("unroll-max-count", cl::Hidden, cl::desc("Set the max unroll count for partial and runtime unrolling, for" "testing purposes"))
llvm::ScalarEvolution::getSmallConstantTripCount
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
Definition: ScalarEvolution.cpp:7490
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1137
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
BasicBlock.h
llvm::cl::opt< bool >
hasUnrollEnablePragma
static bool hasUnrollEnablePragma(const Loop *L)
Definition: LoopUnrollPass.cpp:707
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::UnrollLoop
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:269
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1732
uint64_t
ProfileSummaryInfo.h
tryToUnrollLoop
static LoopUnrollResult tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache &AC, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel, bool OnlyWhenForced, bool ForgetAllSCEV, Optional< unsigned > ProvidedCount, Optional< unsigned > ProvidedThreshold, Optional< bool > ProvidedAllowPartial, Optional< bool > ProvidedRuntime, Optional< bool > ProvidedUpperBound, Optional< bool > ProvidedAllowPeeling, Optional< bool > ProvidedAllowProfileBasedPeeling, Optional< unsigned > ProvidedFullUnrollMaxCount)
Definition: LoopUnrollPass.cpp:1122
llvm::LoopPass
Definition: LoopPass.h:27
llvm::hasUnrollAndJamTransformation
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
Definition: LoopUtils.cpp:382
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2474
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition: PriorityWorklist.h:256
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ScalarEvolution::getSmallConstantMaxTripCount
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
Definition: ScalarEvolution.cpp:7506
llvm::TargetTransformInfo::UnrollingPreferences
Parameters that control the generic loop unrolling transformation.
Definition: TargetTransformInfo.h:431
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LoopUnrollResult::PartiallyUnrolled
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
Metrics
Machine Trace Metrics
Definition: MachineTraceMetrics.cpp:53
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::LoopUnrollResult
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:53
llvm::LoopUnrollOptions::OptLevel
int OptLevel
Definition: LoopUnrollPass.h:68
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::empty
bool empty() const
Determine if the PriorityWorklist is empty or not.
Definition: PriorityWorklist.h:68
UnrollThresholdAggressive
static cl::opt< unsigned > UnrollThresholdAggressive("unroll-threshold-aggressive", cl::init(300), cl::Hidden, cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) " "optimizations"))
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::TM_Disable
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:274
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
UnrollCostEstimator::UnrollCostEstimator
UnrollCostEstimator(Loop &L, unsigned LoopSize)
Definition: LoopUnrollPass.cpp:756
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1707
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
NoThreshold
static const unsigned NoThreshold
A magic value for use with the Threshold parameter to indicate that the loop unroll should be perform...
Definition: LoopUnrollPass.cpp:181
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::TargetTransformInfo::isLoweredToCall
bool isLoweredToCall(const Function *F) const
Test whether calls to a function lower to actual program function calls.
Definition: TargetTransformInfo.cpp:281
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:945
llvm::LPMUpdater::markLoopAsDeleted
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
Definition: LoopPassManager.h:283
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
LoopPassManager.h
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
UnrollAllowPartial
static cl::opt< bool > UnrollAllowPartial("unroll-allow-partial", cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached."))
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
PragmaUnrollThreshold
static cl::opt< unsigned > PragmaUnrollThreshold("pragma-unroll-threshold", cl::init(16 *1024), cl::Hidden, cl::desc("Unrolled size limit for loops with an unroll(full) or " "unroll_count pragma."))
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:211
llvm::TargetTransformInfo::PeelingPreferences::PeelCount
unsigned PeelCount
A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...
Definition: TargetTransformInfo.h:542
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::LoopInfo
Definition: LoopInfo.h:1086
None.h
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::TargetTransformInfo::TCK_SizeAndLatency
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Definition: TargetTransformInfo.h:215
llvm::TM_ForcedByUser
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:282
LoopPass.h
llvm::appendLoopsToWorklist
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1478
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::TargetTransformInfo::getUserCost
InstructionCost getUserCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:219
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
CostKind
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
llvm::TargetTransformInfo::UnrollingPreferences::DefaultUnrollRuntimeCount
unsigned DefaultUnrollRuntimeCount
Default unroll count for loops with run-time trip count.
Definition: TargetTransformInfo.h:467
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
UnrollOptSizeThreshold
static cl::opt< unsigned > UnrollOptSizeThreshold("unroll-optsize-threshold", cl::init(0), cl::Hidden, cl::desc("The cost threshold for loop unrolling when optimizing for " "size"))
llvm::InstructionCost::isValid
bool isValid() const
Definition: InstructionCost.h:79
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:431
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::LoopUnrollOptions::AllowProfileBasedPeeling
Optional< bool > AllowProfileBasedPeeling
Definition: LoopUnrollPass.h:66
UnrollUnrollRemainder
static cl::opt< bool > UnrollUnrollRemainder("unroll-remainder", cl::Hidden, cl::desc("Allow the loop remainder to be unrolled."))
LoopUnrollAnalyzer.h
LAM
LoopAnalysisManager LAM
Definition: PassBuilderBindings.cpp:58
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:661
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:185
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
UnrollCostEstimator
Definition: LoopUnrollPass.cpp:752
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:487
llvm::ForgetSCEVInLoopUnroll
cl::opt< bool > ForgetSCEVInLoopUnroll
Constant.h
llvm::LoopUnrollPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopUnrollPass.cpp:1549
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:838
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:528
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
llvm::LPPassManager::markLoopAsDeleted
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:112
llvm::LoopStandardAnalysisResults::TTI
TargetTransformInfo & TTI
Definition: LoopAnalysisManager.h:59
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::TargetTransformInfo::UnrollingPreferences::UpperBound
bool UpperBound
Allow using trip count upper bound to unroll loops.
Definition: TargetTransformInfo.h:498
LoopUnrollPass.h
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:504
llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
Definition: ScalarEvolution.cpp:7733
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:802
llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder
bool AllowRemainder
Allow generation of a loop remainder (extra iterations after unroll).
Definition: TargetTransformInfo.h:490
Casting.h
DiagnosticInfo.h
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
shouldPragmaUnroll
static Optional< unsigned > shouldPragmaUnroll(Loop *L, const PragmaInfo &PInfo, const unsigned TripMultiple, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
Definition: LoopUnrollPass.cpp:775
PassManager.h
UnrollMaxIterationsCountToAnalyze
static cl::opt< unsigned > UnrollMaxIterationsCountToAnalyze("unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden, cl::desc("Don't allow loop unrolling to simulate more than this number of" "iterations when checking full unroll profitability"))
llvm::simplifyLoop
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
Definition: LoopSimplify.cpp:718
llvm::Function::hasProfileData
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:292
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:581
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1863
llvm::LPMUpdater::addChildLoops
void addChildLoops(ArrayRef< Loop * > NewChildLoops)
Loop passes should use this method to indicate they have added new child loops of the current loop.
Definition: LoopPassManager.h:304
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::LoopUnrollOptions::AllowPartial
Optional< bool > AllowPartial
Definition: LoopUnrollPass.h:62
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:946
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:685
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
SmallVector.h
hasRuntimeUnrollDisablePragma
static bool hasRuntimeUnrollDisablePragma(const Loop *L)
Definition: LoopUnrollPass.cpp:712
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopUnrollPass.cpp:74
Dominators.h
llvm::TargetTransformInfo::UnrollingPreferences::Threshold
unsigned Threshold
The cost threshold for the unrolled loop.
Definition: TargetTransformInfo.h:439
UnrollLoop.h
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
TargetTransformInfo.h
Threshold
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
DenseMapInfo.h
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:658
llvm::SmallPtrSetImpl< const Value * >
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:940
llvm::TargetTransformInfo::UnrollingPreferences::OptSizeThreshold
unsigned OptSizeThreshold
The cost threshold for the unrolled loop when optimizing for size (set to UINT_MAX to disable).
Definition: TargetTransformInfo.h:453
llvm::LoopBase::isLoopExiting
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Definition: LoopInfo.h:225
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3236
llvm::cl::desc
Definition: CommandLine.h:412
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3092
llvm::LoopUnrollResult::Unmodified
@ Unmodified
The loop was not modified.
raw_ostream.h
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
llvm::LPMUpdater::addSiblingLoops
void addSiblingLoops(ArrayRef< Loop * > NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop.
Definition: LoopPassManager.h:331
LoopPeel.h
llvm::getLoopEstimatedTripCount
Optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:825
InitializePasses.h
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:164
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
getFullUnrollBoostingFactor
static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost, unsigned MaxPercentThresholdBoost)
Definition: LoopUnrollPass.cpp:736
llvm::TransformationMode
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:265
Debug.h
llvm::gatherPeelingPreferences
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, Optional< bool > UserAllowPeeling, Optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
Definition: LoopPeel.cpp:696
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:282
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1246
SetVector.h
llvm::TargetTransformInfo::UnrollingPreferences::MaxPercentThresholdBoost
unsigned MaxPercentThresholdBoost
If complete unrolling will reduce the cost of the loop, we will boost the Threshold by a certain perc...
Definition: TargetTransformInfo.h:450
llvm::createLoopUnrollPass
Pass * createLoopUnrollPass(int OptLevel=2, bool OnlyWhenForced=false, bool ForgetAllSCEV=false, int Threshold=-1, int Count=-1, int AllowPartial=-1, int Runtime=-1, int UpperBound=-1, int AllowPeeling=-1)
Definition: LoopUnrollPass.cpp:1441
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::LoopUnrollOptions::AllowRuntime
Optional< bool > AllowRuntime
Definition: LoopUnrollPass.h:64
llvm::LoopFullUnrollPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopUnrollPass.cpp:1464
llvm::omp::OMPScheduleType::Runtime
@ Runtime