contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

   1 //===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass implements a simple loop unroller.  It works best when loops have
  11 // been canonicalized by the -indvars pass, allowing it to determine the trip
  12 // counts of loops easily.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Scalar/LoopUnrollPass.h"
  16 #include "llvm/ADT/SetVector.h"
  17 #include "llvm/Analysis/AssumptionCache.h"
  18 #include "llvm/Analysis/CodeMetrics.h"
  19 #include "llvm/Analysis/GlobalsModRef.h"
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/Analysis/LoopPass.h"
  22 #include "llvm/Analysis/LoopUnrollAnalyzer.h"
  23 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
  24 #include "llvm/Analysis/ScalarEvolution.h"
  25 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  26 #include "llvm/IR/DataLayout.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/InstVisitor.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/IR/Metadata.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/Transforms/Scalar.h"
  35 #include "llvm/Transforms/Scalar/LoopPassManager.h"
  36 #include "llvm/Transforms/Utils/LoopUtils.h"
  37 #include "llvm/Transforms/Utils/UnrollLoop.h"
  38 #include <climits>
  39 #include <utility>
  40
  41 using namespace llvm;
  42
  43 #define DEBUG_TYPE "loop-unroll"
  44
  45 static cl::opt<unsigned>
  46     UnrollThreshold("unroll-threshold", cl::Hidden,
  47                     cl::desc("The cost threshold for loop unrolling"));
  48
  49 static cl::opt<unsigned> UnrollPartialThreshold(
  50     "unroll-partial-threshold", cl::Hidden,
  51     cl::desc("The cost threshold for partial loop unrolling"));
  52
  53 static cl::opt<unsigned> UnrollMaxPercentThresholdBoost(
  54     "unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden,
  55     cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied "
  56              "to the threshold when aggressively unrolling a loop due to the "
  57              "dynamic cost savings. If completely unrolling a loop will reduce "
  58              "the total runtime from X to Y, we boost the loop unroll "
  59              "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, "
  60              "X/Y). This limit avoids excessive code bloat."));
  61
  62 static cl::opt<unsigned> UnrollMaxIterationsCountToAnalyze(
  63     "unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden,
  64     cl::desc("Don't allow loop unrolling to simulate more than this number of"
  65              "iterations when checking full unroll profitability"));
  66
  67 static cl::opt<unsigned> UnrollCount(
  68     "unroll-count", cl::Hidden,
  69     cl::desc("Use this unroll count for all loops including those with "
  70              "unroll_count pragma values, for testing purposes"));
  71
  72 static cl::opt<unsigned> UnrollMaxCount(
  73     "unroll-max-count", cl::Hidden,
  74     cl::desc("Set the max unroll count for partial and runtime unrolling, for"
  75              "testing purposes"));
  76
  77 static cl::opt<unsigned> UnrollFullMaxCount(
  78     "unroll-full-max-count", cl::Hidden,
  79     cl::desc(
  80         "Set the max unroll count for full unrolling, for testing purposes"));
  81
  82 static cl::opt<bool>
  83     UnrollAllowPartial("unroll-allow-partial", cl::Hidden,
  84                        cl::desc("Allows loops to be partially unrolled until "
  85                                 "-unroll-threshold loop size is reached."));
  86
  87 static cl::opt<bool> UnrollAllowRemainder(
  88     "unroll-allow-remainder", cl::Hidden,
  89     cl::desc("Allow generation of a loop remainder (extra iterations) "
  90              "when unrolling a loop."));
  91
  92 static cl::opt<bool>
  93     UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden,
  94                   cl::desc("Unroll loops with run-time trip counts"));
  95
  96 static cl::opt<unsigned> UnrollMaxUpperBound(
  97     "unroll-max-upperbound", cl::init(8), cl::Hidden,
  98     cl::desc(
  99         "The max of trip count upper bound that is considered in unrolling"));
 100
 101 static cl::opt<unsigned> PragmaUnrollThreshold(
 102     "pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden,
 103     cl::desc("Unrolled size limit for loops with an unroll(full) or "
 104              "unroll_count pragma."));
 105
 106 static cl::opt<unsigned> FlatLoopTripCountThreshold(
 107     "flat-loop-tripcount-threshold", cl::init(5), cl::Hidden,
 108     cl::desc("If the runtime tripcount for the loop is lower than the "
 109              "threshold, the loop is considered as flat and will be less "
 110              "aggressively unrolled."));
 111
 112 static cl::opt<bool>
 113     UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden,
 114                        cl::desc("Allows loops to be peeled when the dynamic "
 115                                 "trip count is known to be low."));
 116
 117 // This option isn't ever intended to be enabled, it serves to allow
 118 // experiments to check the assumptions about when this kind of revisit is
 119 // necessary.
 120 static cl::opt<bool> UnrollRevisitChildLoops(
 121     "unroll-revisit-child-loops", cl::Hidden,
 122     cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. "
 123              "This shouldn't typically be needed as child loops (or their "
 124              "clones) were already visited."));
 125
 126 /// A magic value for use with the Threshold parameter to indicate
 127 /// that the loop unroll should be performed regardless of how much
 128 /// code expansion would result.
 129 static const unsigned NoThreshold = UINT_MAX;
 130
 131 /// Gather the various unrolling parameters based on the defaults, compiler
 132 /// flags, TTI overrides and user specified parameters.
 133 static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
 134     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
 135     Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
 136     Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
 137     Optional<bool> UserUpperBound) {
 138   TargetTransformInfo::UnrollingPreferences UP;
 139
 140   // Set up the defaults
 141   UP.Threshold = OptLevel > 2 ? 300 : 150;
 142   UP.MaxPercentThresholdBoost = 400;
 143   UP.OptSizeThreshold = 0;
 144   UP.PartialThreshold = 150;
 145   UP.PartialOptSizeThreshold = 0;
 146   UP.Count = 0;
 147   UP.PeelCount = 0;
 148   UP.DefaultUnrollRuntimeCount = 8;
 149   UP.MaxCount = UINT_MAX;
 150   UP.FullUnrollMaxCount = UINT_MAX;
 151   UP.BEInsns = 2;
 152   UP.Partial = false;
 153   UP.Runtime = false;
 154   UP.AllowRemainder = true;
 155   UP.AllowExpensiveTripCount = false;
 156   UP.Force = false;
 157   UP.UpperBound = false;
 158   UP.AllowPeeling = true;
 159
 160   // Override with any target specific settings
 161   TTI.getUnrollingPreferences(L, SE, UP);
 162
 163   // Apply size attributes
 164   if (L->getHeader()->getParent()->optForSize()) {
 165     UP.Threshold = UP.OptSizeThreshold;
 166     UP.PartialThreshold = UP.PartialOptSizeThreshold;
 167   }
 168
 169   // Apply any user values specified by cl::opt
 170   if (UnrollThreshold.getNumOccurrences() > 0)
 171     UP.Threshold = UnrollThreshold;
 172   if (UnrollPartialThreshold.getNumOccurrences() > 0)
 173     UP.PartialThreshold = UnrollPartialThreshold;
 174   if (UnrollMaxPercentThresholdBoost.getNumOccurrences() > 0)
 175     UP.MaxPercentThresholdBoost = UnrollMaxPercentThresholdBoost;
 176   if (UnrollMaxCount.getNumOccurrences() > 0)
 177     UP.MaxCount = UnrollMaxCount;
 178   if (UnrollFullMaxCount.getNumOccurrences() > 0)
 179     UP.FullUnrollMaxCount = UnrollFullMaxCount;
 180   if (UnrollAllowPartial.getNumOccurrences() > 0)
 181     UP.Partial = UnrollAllowPartial;
 182   if (UnrollAllowRemainder.getNumOccurrences() > 0)
 183     UP.AllowRemainder = UnrollAllowRemainder;
 184   if (UnrollRuntime.getNumOccurrences() > 0)
 185     UP.Runtime = UnrollRuntime;
 186   if (UnrollMaxUpperBound == 0)
 187     UP.UpperBound = false;
 188   if (UnrollAllowPeeling.getNumOccurrences() > 0)
 189     UP.AllowPeeling = UnrollAllowPeeling;
 190
 191   // Apply user values provided by argument
 192   if (UserThreshold.hasValue()) {
 193     UP.Threshold = *UserThreshold;
 194     UP.PartialThreshold = *UserThreshold;
 195   }
 196   if (UserCount.hasValue())
 197     UP.Count = *UserCount;
 198   if (UserAllowPartial.hasValue())
 199     UP.Partial = *UserAllowPartial;
 200   if (UserRuntime.hasValue())
 201     UP.Runtime = *UserRuntime;
 202   if (UserUpperBound.hasValue())
 203     UP.UpperBound = *UserUpperBound;
 204
 205   return UP;
 206 }
 207
 208 namespace {
 209 /// A struct to densely store the state of an instruction after unrolling at
 210 /// each iteration.
 211 ///
 212 /// This is designed to work like a tuple of <Instruction *, int> for the
 213 /// purposes of hashing and lookup, but to be able to associate two boolean
 214 /// states with each key.
 215 struct UnrolledInstState {
 216   Instruction *I;
 217   int Iteration : 30;
 218   unsigned IsFree : 1;
 219   unsigned IsCounted : 1;
 220 };
 221
 222 /// Hashing and equality testing for a set of the instruction states.
 223 struct UnrolledInstStateKeyInfo {
 224   typedef DenseMapInfo<Instruction *> PtrInfo;
 225   typedef DenseMapInfo<std::pair<Instruction *, int>> PairInfo;
 226   static inline UnrolledInstState getEmptyKey() {
 227     return {PtrInfo::getEmptyKey(), 0, 0, 0};
 228   }
 229   static inline UnrolledInstState getTombstoneKey() {
 230     return {PtrInfo::getTombstoneKey(), 0, 0, 0};
 231   }
 232   static inline unsigned getHashValue(const UnrolledInstState &S) {
 233     return PairInfo::getHashValue({S.I, S.Iteration});
 234   }
 235   static inline bool isEqual(const UnrolledInstState &LHS,
 236                              const UnrolledInstState &RHS) {
 237     return PairInfo::isEqual({LHS.I, LHS.Iteration}, {RHS.I, RHS.Iteration});
 238   }
 239 };
 240 }
 241
 242 namespace {
 243 struct EstimatedUnrollCost {
 244   /// \brief The estimated cost after unrolling.
 245   unsigned UnrolledCost;
 246
 247   /// \brief The estimated dynamic cost of executing the instructions in the
 248   /// rolled form.
 249   unsigned RolledDynamicCost;
 250 };
 251 }
 252
 253 /// \brief Figure out if the loop is worth full unrolling.
 254 ///
 255 /// Complete loop unrolling can make some loads constant, and we need to know
 256 /// if that would expose any further optimization opportunities.  This routine
 257 /// estimates this optimization.  It computes cost of unrolled loop
 258 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
 259 /// dynamic cost we mean that we won't count costs of blocks that are known not
 260 /// to be executed (i.e. if we have a branch in the loop and we know that at the
 261 /// given iteration its condition would be resolved to true, we won't add up the
 262 /// cost of the 'false'-block).
 263 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
 264 /// the analysis failed (no benefits expected from the unrolling, or the loop is
 265 /// too big to analyze), the returned value is None.
 266 static Optional<EstimatedUnrollCost>
 267 analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT,
 268                       ScalarEvolution &SE, const TargetTransformInfo &TTI,
 269                       unsigned MaxUnrolledLoopSize) {
 270   // We want to be able to scale offsets by the trip count and add more offsets
 271   // to them without checking for overflows, and we already don't want to
 272   // analyze *massive* trip counts, so we force the max to be reasonably small.
 273   assert(UnrollMaxIterationsCountToAnalyze < (INT_MAX / 2) &&
 274          "The unroll iterations max is too large!");
 275
 276   // Only analyze inner loops. We can't properly estimate cost of nested loops
 277   // and we won't visit inner loops again anyway.
 278   if (!L->empty())
 279     return None;
 280
 281   // Don't simulate loops with a big or unknown tripcount
 282   if (!UnrollMaxIterationsCountToAnalyze || !TripCount ||
 283       TripCount > UnrollMaxIterationsCountToAnalyze)
 284     return None;
 285
 286   SmallSetVector<BasicBlock *, 16> BBWorklist;
 287   SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
 288   DenseMap<Value *, Constant *> SimplifiedValues;
 289   SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
 290
 291   // The estimated cost of the unrolled form of the loop. We try to estimate
 292   // this by simplifying as much as we can while computing the estimate.
 293   unsigned UnrolledCost = 0;
 294
 295   // We also track the estimated dynamic (that is, actually executed) cost in
 296   // the rolled form. This helps identify cases when the savings from unrolling
 297   // aren't just exposing dead control flows, but actual reduced dynamic
 298   // instructions due to the simplifications which we expect to occur after
 299   // unrolling.
 300   unsigned RolledDynamicCost = 0;
 301
 302   // We track the simplification of each instruction in each iteration. We use
 303   // this to recursively merge costs into the unrolled cost on-demand so that
 304   // we don't count the cost of any dead code. This is essentially a map from
 305   // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
 306   DenseSet<UnrolledInstState, UnrolledInstStateKeyInfo> InstCostMap;
 307
 308   // A small worklist used to accumulate cost of instructions from each
 309   // observable and reached root in the loop.
 310   SmallVector<Instruction *, 16> CostWorklist;
 311
 312   // PHI-used worklist used between iterations while accumulating cost.
 313   SmallVector<Instruction *, 4> PHIUsedList;
 314
 315   // Helper function to accumulate cost for instructions in the loop.
 316   auto AddCostRecursively = [&](Instruction &RootI, int Iteration) {
 317     assert(Iteration >= 0 && "Cannot have a negative iteration!");
 318     assert(CostWorklist.empty() && "Must start with an empty cost list");
 319     assert(PHIUsedList.empty() && "Must start with an empty phi used list");
 320     CostWorklist.push_back(&RootI);
 321     for (;; --Iteration) {
 322       do {
 323         Instruction *I = CostWorklist.pop_back_val();
 324
 325         // InstCostMap only uses I and Iteration as a key, the other two values
 326         // don't matter here.
 327         auto CostIter = InstCostMap.find({I, Iteration, 0, 0});
 328         if (CostIter == InstCostMap.end())
 329           // If an input to a PHI node comes from a dead path through the loop
 330           // we may have no cost data for it here. What that actually means is
 331           // that it is free.
 332           continue;
 333         auto &Cost = *CostIter;
 334         if (Cost.IsCounted)
 335           // Already counted this instruction.
 336           continue;
 337
 338         // Mark that we are counting the cost of this instruction now.
 339         Cost.IsCounted = true;
 340
 341         // If this is a PHI node in the loop header, just add it to the PHI set.
 342         if (auto *PhiI = dyn_cast<PHINode>(I))
 343           if (PhiI->getParent() == L->getHeader()) {
 344             assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
 345                                   "inherently simplify during unrolling.");
 346             if (Iteration == 0)
 347               continue;
 348
 349             // Push the incoming value from the backedge into the PHI used list
 350             // if it is an in-loop instruction. We'll use this to populate the
 351             // cost worklist for the next iteration (as we count backwards).
 352             if (auto *OpI = dyn_cast<Instruction>(
 353                     PhiI->getIncomingValueForBlock(L->getLoopLatch())))
 354               if (L->contains(OpI))
 355                 PHIUsedList.push_back(OpI);
 356             continue;
 357           }
 358
 359         // First accumulate the cost of this instruction.
 360         if (!Cost.IsFree) {
 361           UnrolledCost += TTI.getUserCost(I);
 362           DEBUG(dbgs() << "Adding cost of instruction (iteration " << Iteration
 363                        << "): ");
 364           DEBUG(I->dump());
 365         }
 366
 367         // We must count the cost of every operand which is not free,
 368         // recursively. If we reach a loop PHI node, simply add it to the set
 369         // to be considered on the next iteration (backwards!).
 370         for (Value *Op : I->operands()) {
 371           // Check whether this operand is free due to being a constant or
 372           // outside the loop.
 373           auto *OpI = dyn_cast<Instruction>(Op);
 374           if (!OpI || !L->contains(OpI))
 375             continue;
 376
 377           // Otherwise accumulate its cost.
 378           CostWorklist.push_back(OpI);
 379         }
 380       } while (!CostWorklist.empty());
 381
 382       if (PHIUsedList.empty())
 383         // We've exhausted the search.
 384         break;
 385
 386       assert(Iteration > 0 &&
 387              "Cannot track PHI-used values past the first iteration!");
 388       CostWorklist.append(PHIUsedList.begin(), PHIUsedList.end());
 389       PHIUsedList.clear();
 390     }
 391   };
 392
 393   // Ensure that we don't violate the loop structure invariants relied on by
 394   // this analysis.
 395   assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
 396   assert(L->isLCSSAForm(DT) &&
 397          "Must have loops in LCSSA form to track live-out values.");
 398
 399   DEBUG(dbgs() << "Starting LoopUnroll profitability analysis...\n");
 400
 401   // Simulate execution of each iteration of the loop counting instructions,
 402   // which would be simplified.
 403   // Since the same load will take different values on different iterations,
 404   // we literally have to go through all loop's iterations.
 405   for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
 406     DEBUG(dbgs() << " Analyzing iteration " << Iteration << "\n");
 407
 408     // Prepare for the iteration by collecting any simplified entry or backedge
 409     // inputs.
 410     for (Instruction &I : *L->getHeader()) {
 411       auto *PHI = dyn_cast<PHINode>(&I);
 412       if (!PHI)
 413         break;
 414
 415       // The loop header PHI nodes must have exactly two input: one from the
 416       // loop preheader and one from the loop latch.
 417       assert(
 418           PHI->getNumIncomingValues() == 2 &&
 419           "Must have an incoming value only for the preheader and the latch.");
 420
 421       Value *V = PHI->getIncomingValueForBlock(
 422           Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
 423       Constant *C = dyn_cast<Constant>(V);
 424       if (Iteration != 0 && !C)
 425         C = SimplifiedValues.lookup(V);
 426       if (C)
 427         SimplifiedInputValues.push_back({PHI, C});
 428     }
 429
 430     // Now clear and re-populate the map for the next iteration.
 431     SimplifiedValues.clear();
 432     while (!SimplifiedInputValues.empty())
 433       SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
 434
 435     UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
 436
 437     BBWorklist.clear();
 438     BBWorklist.insert(L->getHeader());
 439     // Note that we *must not* cache the size, this loop grows the worklist.
 440     for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
 441       BasicBlock *BB = BBWorklist[Idx];
 442
 443       // Visit all instructions in the given basic block and try to simplify
 444       // it.  We don't change the actual IR, just count optimization
 445       // opportunities.
 446       for (Instruction &I : *BB) {
 447         if (isa<DbgInfoIntrinsic>(I))
 448           continue;
 449
 450         // Track this instruction's expected baseline cost when executing the
 451         // rolled loop form.
 452         RolledDynamicCost += TTI.getUserCost(&I);
 453
 454         // Visit the instruction to analyze its loop cost after unrolling,
 455         // and if the visitor returns true, mark the instruction as free after
 456         // unrolling and continue.
 457         bool IsFree = Analyzer.visit(I);
 458         bool Inserted = InstCostMap.insert({&I, (int)Iteration,
 459                                            (unsigned)IsFree,
 460                                            /*IsCounted*/ false}).second;
 461         (void)Inserted;
 462         assert(Inserted && "Cannot have a state for an unvisited instruction!");
 463
 464         if (IsFree)
 465           continue;
 466
 467         // Can't properly model a cost of a call.
 468         // FIXME: With a proper cost model we should be able to do it.
 469         if(isa<CallInst>(&I))
 470           return None;
 471
 472         // If the instruction might have a side-effect recursively account for
 473         // the cost of it and all the instructions leading up to it.
 474         if (I.mayHaveSideEffects())
 475           AddCostRecursively(I, Iteration);
 476
 477         // If unrolled body turns out to be too big, bail out.
 478         if (UnrolledCost > MaxUnrolledLoopSize) {
 479           DEBUG(dbgs() << "  Exceeded threshold.. exiting.\n"
 480                        << "  UnrolledCost: " << UnrolledCost
 481                        << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
 482                        << "\n");
 483           return None;
 484         }
 485       }
 486
 487       TerminatorInst *TI = BB->getTerminator();
 488
 489       // Add in the live successors by first checking whether we have terminator
 490       // that may be simplified based on the values simplified by this call.
 491       BasicBlock *KnownSucc = nullptr;
 492       if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 493         if (BI->isConditional()) {
 494           if (Constant *SimpleCond =
 495                   SimplifiedValues.lookup(BI->getCondition())) {
 496             // Just take the first successor if condition is undef
 497             if (isa<UndefValue>(SimpleCond))
 498               KnownSucc = BI->getSuccessor(0);
 499             else if (ConstantInt *SimpleCondVal =
 500                          dyn_cast<ConstantInt>(SimpleCond))
 501               KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
 502           }
 503         }
 504       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 505         if (Constant *SimpleCond =
 506                 SimplifiedValues.lookup(SI->getCondition())) {
 507           // Just take the first successor if condition is undef
 508           if (isa<UndefValue>(SimpleCond))
 509             KnownSucc = SI->getSuccessor(0);
 510           else if (ConstantInt *SimpleCondVal =
 511                        dyn_cast<ConstantInt>(SimpleCond))
 512             KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
 513         }
 514       }
 515       if (KnownSucc) {
 516         if (L->contains(KnownSucc))
 517           BBWorklist.insert(KnownSucc);
 518         else
 519           ExitWorklist.insert({BB, KnownSucc});
 520         continue;
 521       }
 522
 523       // Add BB's successors to the worklist.
 524       for (BasicBlock *Succ : successors(BB))
 525         if (L->contains(Succ))
 526           BBWorklist.insert(Succ);
 527         else
 528           ExitWorklist.insert({BB, Succ});
 529       AddCostRecursively(*TI, Iteration);
 530     }
 531
 532     // If we found no optimization opportunities on the first iteration, we
 533     // won't find them on later ones too.
 534     if (UnrolledCost == RolledDynamicCost) {
 535       DEBUG(dbgs() << "  No opportunities found.. exiting.\n"
 536                    << "  UnrolledCost: " << UnrolledCost << "\n");
 537       return None;
 538     }
 539   }
 540
 541   while (!ExitWorklist.empty()) {
 542     BasicBlock *ExitingBB, *ExitBB;
 543     std::tie(ExitingBB, ExitBB) = ExitWorklist.pop_back_val();
 544
 545     for (Instruction &I : *ExitBB) {
 546       auto *PN = dyn_cast<PHINode>(&I);
 547       if (!PN)
 548         break;
 549
 550       Value *Op = PN->getIncomingValueForBlock(ExitingBB);
 551       if (auto *OpI = dyn_cast<Instruction>(Op))
 552         if (L->contains(OpI))
 553           AddCostRecursively(*OpI, TripCount - 1);
 554     }
 555   }
 556
 557   DEBUG(dbgs() << "Analysis finished:\n"
 558                << "UnrolledCost: " << UnrolledCost << ", "
 559                << "RolledDynamicCost: " << RolledDynamicCost << "\n");
 560   return {{UnrolledCost, RolledDynamicCost}};
 561 }
 562
 563 /// ApproximateLoopSize - Approximate the size of the loop.
 564 static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
 565                                     bool &NotDuplicatable, bool &Convergent,
 566                                     const TargetTransformInfo &TTI,
 567                                     AssumptionCache *AC, unsigned BEInsns) {
 568   SmallPtrSet<const Value *, 32> EphValues;
 569   CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 570
 571   CodeMetrics Metrics;
 572   for (BasicBlock *BB : L->blocks())
 573     Metrics.analyzeBasicBlock(BB, TTI, EphValues);
 574   NumCalls = Metrics.NumInlineCandidates;
 575   NotDuplicatable = Metrics.notDuplicatable;
 576   Convergent = Metrics.convergent;
 577
 578   unsigned LoopSize = Metrics.NumInsts;
 579
 580   // Don't allow an estimate of size zero.  This would allows unrolling of loops
 581   // with huge iteration counts, which is a compile time problem even if it's
 582   // not a problem for code quality. Also, the code using this size may assume
 583   // that each loop has at least three instructions (likely a conditional
 584   // branch, a comparison feeding that branch, and some kind of loop increment
 585   // feeding that comparison instruction).
 586   LoopSize = std::max(LoopSize, BEInsns + 1);
 587
 588   return LoopSize;
 589 }
 590
 591 // Returns the loop hint metadata node with the given name (for example,
 592 // "llvm.loop.unroll.count").  If no such metadata node exists, then nullptr is
 593 // returned.
 594 static MDNode *GetUnrollMetadataForLoop(const Loop *L, StringRef Name) {
 595   if (MDNode *LoopID = L->getLoopID())
 596     return GetUnrollMetadata(LoopID, Name);
 597   return nullptr;
 598 }
 599
 600 // Returns true if the loop has an unroll(full) pragma.
 601 static bool HasUnrollFullPragma(const Loop *L) {
 602   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
 603 }
 604
 605 // Returns true if the loop has an unroll(enable) pragma. This metadata is used
 606 // for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
 607 static bool HasUnrollEnablePragma(const Loop *L) {
 608   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
 609 }
 610
 611 // Returns true if the loop has an unroll(disable) pragma.
 612 static bool HasUnrollDisablePragma(const Loop *L) {
 613   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.disable");
 614 }
 615
 616 // Returns true if the loop has an runtime unroll(disable) pragma.
 617 static bool HasRuntimeUnrollDisablePragma(const Loop *L) {
 618   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
 619 }
 620
 621 // If loop has an unroll_count pragma return the (necessarily
 622 // positive) value from the pragma.  Otherwise return 0.
 623 static unsigned UnrollCountPragmaValue(const Loop *L) {
 624   MDNode *MD = GetUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
 625   if (MD) {
 626     assert(MD->getNumOperands() == 2 &&
 627            "Unroll count hint metadata should have two operands.");
 628     unsigned Count =
 629         mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
 630     assert(Count >= 1 && "Unroll count must be positive.");
 631     return Count;
 632   }
 633   return 0;
 634 }
 635
 636 // Remove existing unroll metadata and add unroll disable metadata to
 637 // indicate the loop has already been unrolled.  This prevents a loop
 638 // from being unrolled more than is directed by a pragma if the loop
 639 // unrolling pass is run more than once (which it generally is).
 640 static void SetLoopAlreadyUnrolled(Loop *L) {
 641   MDNode *LoopID = L->getLoopID();
 642   // First remove any existing loop unrolling metadata.
 643   SmallVector<Metadata *, 4> MDs;
 644   // Reserve first location for self reference to the LoopID metadata node.
 645   MDs.push_back(nullptr);
 646
 647   if (LoopID) {
 648     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 649       bool IsUnrollMetadata = false;
 650       MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
 651       if (MD) {
 652         const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
 653         IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
 654       }
 655       if (!IsUnrollMetadata)
 656         MDs.push_back(LoopID->getOperand(i));
 657     }
 658   }
 659
 660   // Add unroll(disable) metadata to disable future unrolling.
 661   LLVMContext &Context = L->getHeader()->getContext();
 662   SmallVector<Metadata *, 1> DisableOperands;
 663   DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
 664   MDNode *DisableNode = MDNode::get(Context, DisableOperands);
 665   MDs.push_back(DisableNode);
 666
 667   MDNode *NewLoopID = MDNode::get(Context, MDs);
 668   // Set operand 0 to refer to the loop id itself.
 669   NewLoopID->replaceOperandWith(0, NewLoopID);
 670   L->setLoopID(NewLoopID);
 671 }
 672
 673 // Computes the boosting factor for complete unrolling.
 674 // If fully unrolling the loop would save a lot of RolledDynamicCost, it would
 675 // be beneficial to fully unroll the loop even if unrolledcost is large. We
 676 // use (RolledDynamicCost / UnrolledCost) to model the unroll benefits to adjust
 677 // the unroll threshold.
 678 static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost,
 679                                             unsigned MaxPercentThresholdBoost) {
 680   if (Cost.RolledDynamicCost >= UINT_MAX / 100)
 681     return 100;
 682   else if (Cost.UnrolledCost != 0)
 683     // The boosting factor is RolledDynamicCost / UnrolledCost
 684     return std::min(100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
 685                     MaxPercentThresholdBoost);
 686   else
 687     return MaxPercentThresholdBoost;
 688 }
 689
 690 // Returns loop size estimation for unrolled loop.
 691 static uint64_t getUnrolledLoopSize(
 692     unsigned LoopSize,
 693     TargetTransformInfo::UnrollingPreferences &UP) {
 694   assert(LoopSize >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
 695   return (uint64_t)(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
 696 }
 697
 698 // Returns true if unroll count was set explicitly.
 699 // Calculates unroll count and writes it to UP.Count.
 700 static bool computeUnrollCount(
 701     Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
 702     ScalarEvolution &SE, OptimizationRemarkEmitter *ORE, unsigned &TripCount,
 703     unsigned MaxTripCount, unsigned &TripMultiple, unsigned LoopSize,
 704     TargetTransformInfo::UnrollingPreferences &UP, bool &UseUpperBound) {
 705   // Check for explicit Count.
 706   // 1st priority is unroll count set by "unroll-count" option.
 707   bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
 708   if (UserUnrollCount) {
 709     UP.Count = UnrollCount;
 710     UP.AllowExpensiveTripCount = true;
 711     UP.Force = true;
 712     if (UP.AllowRemainder && getUnrolledLoopSize(LoopSize, UP) < UP.Threshold)
 713       return true;
 714   }
 715
 716   // 2nd priority is unroll count set by pragma.
 717   unsigned PragmaCount = UnrollCountPragmaValue(L);
 718   if (PragmaCount > 0) {
 719     UP.Count = PragmaCount;
 720     UP.Runtime = true;
 721     UP.AllowExpensiveTripCount = true;
 722     UP.Force = true;
 723     if (UP.AllowRemainder &&
 724         getUnrolledLoopSize(LoopSize, UP) < PragmaUnrollThreshold)
 725       return true;
 726   }
 727   bool PragmaFullUnroll = HasUnrollFullPragma(L);
 728   if (PragmaFullUnroll && TripCount != 0) {
 729     UP.Count = TripCount;
 730     if (getUnrolledLoopSize(LoopSize, UP) < PragmaUnrollThreshold)
 731       return false;
 732   }
 733
 734   bool PragmaEnableUnroll = HasUnrollEnablePragma(L);
 735   bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
 736                         PragmaEnableUnroll || UserUnrollCount;
 737
 738   if (ExplicitUnroll && TripCount != 0) {
 739     // If the loop has an unrolling pragma, we want to be more aggressive with
 740     // unrolling limits. Set thresholds to at least the PragmaThreshold value
 741     // which is larger than the default limits.
 742     UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
 743     UP.PartialThreshold =
 744         std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
 745   }
 746
 747   // 3rd priority is full unroll count.
 748   // Full unroll makes sense only when TripCount or its upper bound could be
 749   // statically calculated.
 750   // Also we need to check if we exceed FullUnrollMaxCount.
 751   // If using the upper bound to unroll, TripMultiple should be set to 1 because
 752   // we do not know when loop may exit.
 753   // MaxTripCount and ExactTripCount cannot both be non zero since we only
 754   // compute the former when the latter is zero.
 755   unsigned ExactTripCount = TripCount;
 756   assert((ExactTripCount == 0 || MaxTripCount == 0) &&
 757          "ExtractTripCound and MaxTripCount cannot both be non zero.");
 758   unsigned FullUnrollTripCount = ExactTripCount ? ExactTripCount : MaxTripCount;
 759   UP.Count = FullUnrollTripCount;
 760   if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
 761     // When computing the unrolled size, note that BEInsns are not replicated
 762     // like the rest of the loop body.
 763     if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
 764       UseUpperBound = (MaxTripCount == FullUnrollTripCount);
 765       TripCount = FullUnrollTripCount;
 766       TripMultiple = UP.UpperBound ? 1 : TripMultiple;
 767       return ExplicitUnroll;
 768     } else {
 769       // The loop isn't that small, but we still can fully unroll it if that
 770       // helps to remove a significant number of instructions.
 771       // To check that, run additional analysis on the loop.
 772       if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
 773               L, FullUnrollTripCount, DT, SE, TTI,
 774               UP.Threshold * UP.MaxPercentThresholdBoost / 100)) {
 775         unsigned Boost =
 776             getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
 777         if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
 778           UseUpperBound = (MaxTripCount == FullUnrollTripCount);
 779           TripCount = FullUnrollTripCount;
 780           TripMultiple = UP.UpperBound ? 1 : TripMultiple;
 781           return ExplicitUnroll;
 782         }
 783       }
 784     }
 785   }
 786
 787   // 4th priority is loop peeling
 788   computePeelCount(L, LoopSize, UP, TripCount);
 789   if (UP.PeelCount) {
 790     UP.Runtime = false;
 791     UP.Count = 1;
 792     return ExplicitUnroll;
 793   }
 794
 795   // 5th priority is partial unrolling.
 796   // Try partial unroll only when TripCount could be staticaly calculated.
 797   if (TripCount) {
 798     UP.Partial |= ExplicitUnroll;
 799     if (!UP.Partial) {
 800       DEBUG(dbgs() << "  will not try to unroll partially because "
 801                    << "-unroll-allow-partial not given\n");
 802       UP.Count = 0;
 803       return false;
 804     }
 805     if (UP.Count == 0)
 806       UP.Count = TripCount;
 807     if (UP.PartialThreshold != NoThreshold) {
 808       // Reduce unroll count to be modulo of TripCount for partial unrolling.
 809       if (getUnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
 810         UP.Count =
 811             (std::max(UP.PartialThreshold, UP.BEInsns + 1) - UP.BEInsns) /
 812             (LoopSize - UP.BEInsns);
 813       if (UP.Count > UP.MaxCount)
 814         UP.Count = UP.MaxCount;
 815       while (UP.Count != 0 && TripCount % UP.Count != 0)
 816         UP.Count--;
 817       if (UP.AllowRemainder && UP.Count <= 1) {
 818         // If there is no Count that is modulo of TripCount, set Count to
 819         // largest power-of-two factor that satisfies the threshold limit.
 820         // As we'll create fixup loop, do the type of unrolling only if
 821         // remainder loop is allowed.
 822         UP.Count = UP.DefaultUnrollRuntimeCount;
 823         while (UP.Count != 0 &&
 824                getUnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
 825           UP.Count >>= 1;
 826       }
 827       if (UP.Count < 2) {
 828         if (PragmaEnableUnroll)
 829           ORE->emit(
 830               OptimizationRemarkMissed(DEBUG_TYPE, "UnrollAsDirectedTooLarge",
 831                                        L->getStartLoc(), L->getHeader())
 832               << "Unable to unroll loop as directed by unroll(enable) pragma "
 833                  "because unrolled size is too large.");
 834         UP.Count = 0;
 835       }
 836     } else {
 837       UP.Count = TripCount;
 838     }
 839     if (UP.Count > UP.MaxCount)
 840       UP.Count = UP.MaxCount;
 841     if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
 842         UP.Count != TripCount)
 843       ORE->emit(
 844           OptimizationRemarkMissed(DEBUG_TYPE, "FullUnrollAsDirectedTooLarge",
 845                                    L->getStartLoc(), L->getHeader())
 846           << "Unable to fully unroll loop as directed by unroll pragma because "
 847              "unrolled size is too large.");
 848     return ExplicitUnroll;
 849   }
 850   assert(TripCount == 0 &&
 851          "All cases when TripCount is constant should be covered here.");
 852   if (PragmaFullUnroll)
 853     ORE->emit(
 854         OptimizationRemarkMissed(DEBUG_TYPE,
 855                                  "CantFullUnrollAsDirectedRuntimeTripCount",
 856                                  L->getStartLoc(), L->getHeader())
 857         << "Unable to fully unroll loop as directed by unroll(full) pragma "
 858            "because loop has a runtime trip count.");
 859
 860   // 6th priority is runtime unrolling.
 861   // Don't unroll a runtime trip count loop when it is disabled.
 862   if (HasRuntimeUnrollDisablePragma(L)) {
 863     UP.Count = 0;
 864     return false;
 865   }
 866
 867   // Check if the runtime trip count is too small when profile is available.
 868   if (L->getHeader()->getParent()->getEntryCount()) {
 869     if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
 870       if (*ProfileTripCount < FlatLoopTripCountThreshold)
 871         return false;
 872       else
 873         UP.AllowExpensiveTripCount = true;
 874     }
 875   }
 876
 877   // Reduce count based on the type of unrolling and the threshold values.
 878   UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
 879   if (!UP.Runtime) {
 880     DEBUG(dbgs() << "  will not try to unroll loop with runtime trip count "
 881                  << "-unroll-runtime not given\n");
 882     UP.Count = 0;
 883     return false;
 884   }
 885   if (UP.Count == 0)
 886     UP.Count = UP.DefaultUnrollRuntimeCount;
 887
 888   // Reduce unroll count to be the largest power-of-two factor of
 889   // the original count which satisfies the threshold limit.
 890   while (UP.Count != 0 &&
 891          getUnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
 892     UP.Count >>= 1;
 893
 894 #ifndef NDEBUG
 895   unsigned OrigCount = UP.Count;
 896 #endif
 897
 898   if (!UP.AllowRemainder && UP.Count != 0 && (TripMultiple % UP.Count) != 0) {
 899     while (UP.Count != 0 && TripMultiple % UP.Count != 0)
 900       UP.Count >>= 1;
 901     DEBUG(dbgs() << "Remainder loop is restricted (that could architecture "
 902                     "specific or because the loop contains a convergent "
 903                     "instruction), so unroll count must divide the trip "
 904                     "multiple, "
 905                  << TripMultiple << ".  Reducing unroll count from "
 906                  << OrigCount << " to " << UP.Count << ".\n");
 907     using namespace ore;
 908     if (PragmaCount > 0 && !UP.AllowRemainder)
 909       ORE->emit(
 910           OptimizationRemarkMissed(DEBUG_TYPE,
 911                                    "DifferentUnrollCountFromDirected",
 912                                    L->getStartLoc(), L->getHeader())
 913           << "Unable to unroll loop the number of times directed by "
 914              "unroll_count pragma because remainder loop is restricted "
 915              "(that could architecture specific or because the loop "
 916              "contains a convergent instruction) and so must have an unroll "
 917              "count that divides the loop trip multiple of "
 918           << NV("TripMultiple", TripMultiple) << ".  Unrolling instead "
 919           << NV("UnrollCount", UP.Count) << " time(s).");
 920   }
 921
 922   if (UP.Count > UP.MaxCount)
 923     UP.Count = UP.MaxCount;
 924   DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count << "\n");
 925   if (UP.Count < 2)
 926     UP.Count = 0;
 927   return ExplicitUnroll;
 928 }
 929
 930 static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
 931                             ScalarEvolution &SE, const TargetTransformInfo &TTI,
 932                             AssumptionCache &AC, OptimizationRemarkEmitter &ORE,
 933                             bool PreserveLCSSA, int OptLevel,
 934                             Optional<unsigned> ProvidedCount,
 935                             Optional<unsigned> ProvidedThreshold,
 936                             Optional<bool> ProvidedAllowPartial,
 937                             Optional<bool> ProvidedRuntime,
 938                             Optional<bool> ProvidedUpperBound) {
 939   DEBUG(dbgs() << "Loop Unroll: F[" << L->getHeader()->getParent()->getName()
 940                << "] Loop %" << L->getHeader()->getName() << "\n");
 941   if (HasUnrollDisablePragma(L))
 942     return false;
 943   if (!L->isLoopSimplifyForm()) {
 944     DEBUG(
 945         dbgs() << "  Not unrolling loop which is not in loop-simplify form.\n");
 946     return false;
 947   }
 948
 949   unsigned NumInlineCandidates;
 950   bool NotDuplicatable;
 951   bool Convergent;
 952   TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
 953       L, SE, TTI, OptLevel, ProvidedThreshold, ProvidedCount,
 954       ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound);
 955   // Exit early if unrolling is disabled.
 956   if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0))
 957     return false;
 958   unsigned LoopSize = ApproximateLoopSize(
 959       L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC, UP.BEInsns);
 960   DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
 961   if (NotDuplicatable) {
 962     DEBUG(dbgs() << "  Not unrolling loop which contains non-duplicatable"
 963                  << " instructions.\n");
 964     return false;
 965   }
 966   if (NumInlineCandidates != 0) {
 967     DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
 968     return false;
 969   }
 970
 971   // Find trip count and trip multiple if count is not available
 972   unsigned TripCount = 0;
 973   unsigned MaxTripCount = 0;
 974   unsigned TripMultiple = 1;
 975   // If there are multiple exiting blocks but one of them is the latch, use the
 976   // latch for the trip count estimation. Otherwise insist on a single exiting
 977   // block for the trip count estimation.
 978   BasicBlock *ExitingBlock = L->getLoopLatch();
 979   if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
 980     ExitingBlock = L->getExitingBlock();
 981   if (ExitingBlock) {
 982     TripCount = SE.getSmallConstantTripCount(L, ExitingBlock);
 983     TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
 984   }
 985
 986   // If the loop contains a convergent operation, the prelude we'd add
 987   // to do the first few instructions before we hit the unrolled loop
 988   // is unsafe -- it adds a control-flow dependency to the convergent
 989   // operation.  Therefore restrict remainder loop (try unrollig without).
 990   //
 991   // TODO: This is quite conservative.  In practice, convergent_op()
 992   // is likely to be called unconditionally in the loop.  In this
 993   // case, the program would be ill-formed (on most architectures)
 994   // unless n were the same on all threads in a thread group.
 995   // Assuming n is the same on all threads, any kind of unrolling is
 996   // safe.  But currently llvm's notion of convergence isn't powerful
 997   // enough to express this.
 998   if (Convergent)
 999     UP.AllowRemainder = false;
1000
1001   // Try to find the trip count upper bound if we cannot find the exact trip
1002   // count.
1003   bool MaxOrZero = false;
1004   if (!TripCount) {
1005     MaxTripCount = SE.getSmallConstantMaxTripCount(L);
1006     MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
1007     // We can unroll by the upper bound amount if it's generally allowed or if
1008     // we know that the loop is executed either the upper bound or zero times.
1009     // (MaxOrZero unrolling keeps only the first loop test, so the number of
1010     // loop tests remains the same compared to the non-unrolled version, whereas
1011     // the generic upper bound unrolling keeps all but the last loop test so the
1012     // number of loop tests goes up which may end up being worse on targets with
1013     // constriained branch predictor resources so is controlled by an option.)
1014     // In addition we only unroll small upper bounds.
1015     if (!(UP.UpperBound || MaxOrZero) || MaxTripCount > UnrollMaxUpperBound) {
1016       MaxTripCount = 0;
1017     }
1018   }
1019
1020   // computeUnrollCount() decides whether it is beneficial to use upper bound to
1021   // fully unroll the loop.
1022   bool UseUpperBound = false;
1023   bool IsCountSetExplicitly =
1024       computeUnrollCount(L, TTI, DT, LI, SE, &ORE, TripCount, MaxTripCount,
1025                          TripMultiple, LoopSize, UP, UseUpperBound);
1026   if (!UP.Count)
1027     return false;
1028   // Unroll factor (Count) must be less or equal to TripCount.
1029   if (TripCount && UP.Count > TripCount)
1030     UP.Count = TripCount;
1031
1032   // Unroll the loop.
1033   if (!UnrollLoop(L, UP.Count, TripCount, UP.Force, UP.Runtime,
1034                   UP.AllowExpensiveTripCount, UseUpperBound, MaxOrZero,
1035                   TripMultiple, UP.PeelCount, LI, &SE, &DT, &AC, &ORE,
1036                   PreserveLCSSA))
1037     return false;
1038
1039   // If loop has an unroll count pragma or unrolled by explicitly set count
1040   // mark loop as unrolled to prevent unrolling beyond that requested.
1041   // If the loop was peeled, we already "used up" the profile information
1042   // we had, so we don't want to unroll or peel again.
1043   if (IsCountSetExplicitly || UP.PeelCount)
1044     SetLoopAlreadyUnrolled(L);
1045
1046   return true;
1047 }
1048
1049 namespace {
1050 class LoopUnroll : public LoopPass {
1051 public:
1052   static char ID; // Pass ID, replacement for typeid
1053   LoopUnroll(int OptLevel = 2, Optional<unsigned> Threshold = None,
1054              Optional<unsigned> Count = None,
1055              Optional<bool> AllowPartial = None, Optional<bool> Runtime = None,
1056              Optional<bool> UpperBound = None)
1057       : LoopPass(ID), OptLevel(OptLevel), ProvidedCount(std::move(Count)),
1058         ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
1059         ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound) {
1060     initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
1061   }
1062
1063   int OptLevel;
1064   Optional<unsigned> ProvidedCount;
1065   Optional<unsigned> ProvidedThreshold;
1066   Optional<bool> ProvidedAllowPartial;
1067   Optional<bool> ProvidedRuntime;
1068   Optional<bool> ProvidedUpperBound;
1069
1070   bool runOnLoop(Loop *L, LPPassManager &) override {
1071     if (skipLoop(L))
1072       return false;
1073
1074     Function &F = *L->getHeader()->getParent();
1075
1076     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1077     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1078     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1079     const TargetTransformInfo &TTI =
1080         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1081     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1082     // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
1083     // pass.  Function analyses need to be preserved across loop transformations
1084     // but ORE cannot be preserved (see comment before the pass definition).
1085     OptimizationRemarkEmitter ORE(&F);
1086     bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1087
1088     return tryToUnrollLoop(L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel,
1089                            ProvidedCount, ProvidedThreshold,
1090                            ProvidedAllowPartial, ProvidedRuntime,
1091                            ProvidedUpperBound);
1092   }
1093
1094   /// This transformation requires natural loop information & requires that
1095   /// loop preheaders be inserted into the CFG...
1096   ///
1097   void getAnalysisUsage(AnalysisUsage &AU) const override {
1098     AU.addRequired<AssumptionCacheTracker>();
1099     AU.addRequired<TargetTransformInfoWrapperPass>();
1100     // FIXME: Loop passes are required to preserve domtree, and for now we just
1101     // recreate dom info if anything gets unrolled.
1102     getLoopAnalysisUsage(AU);
1103   }
1104 };
1105 }
1106
1107 char LoopUnroll::ID = 0;
1108 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1109 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1110 INITIALIZE_PASS_DEPENDENCY(LoopPass)
1111 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1112 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1113
1114 Pass *llvm::createLoopUnrollPass(int OptLevel, int Threshold, int Count,
1115                                  int AllowPartial, int Runtime,
1116                                  int UpperBound) {
1117   // TODO: It would make more sense for this function to take the optionals
1118   // directly, but that's dangerous since it would silently break out of tree
1119   // callers.
1120   return new LoopUnroll(
1121       OptLevel, Threshold == -1 ? None : Optional<unsigned>(Threshold),
1122       Count == -1 ? None : Optional<unsigned>(Count),
1123       AllowPartial == -1 ? None : Optional<bool>(AllowPartial),
1124       Runtime == -1 ? None : Optional<bool>(Runtime),
1125       UpperBound == -1 ? None : Optional<bool>(UpperBound));
1126 }
1127
1128 Pass *llvm::createSimpleLoopUnrollPass(int OptLevel) {
1129   return llvm::createLoopUnrollPass(OptLevel, -1, -1, 0, 0, 0);
1130 }
1131
1132 PreservedAnalyses LoopUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
1133                                       LoopStandardAnalysisResults &AR,
1134                                       LPMUpdater &Updater) {
1135   const auto &FAM =
1136       AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
1137   Function *F = L.getHeader()->getParent();
1138
1139   auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
1140   // FIXME: This should probably be optional rather than required.
1141   if (!ORE)
1142     report_fatal_error("LoopUnrollPass: OptimizationRemarkEmitterAnalysis not "
1143                        "cached at a higher level");
1144
1145   // Keep track of the previous loop structure so we can identify new loops
1146   // created by unrolling.
1147   Loop *ParentL = L.getParentLoop();
1148   SmallPtrSet<Loop *, 4> OldLoops;
1149   if (ParentL)
1150     OldLoops.insert(ParentL->begin(), ParentL->end());
1151   else
1152     OldLoops.insert(AR.LI.begin(), AR.LI.end());
1153
1154   // The API here is quite complex to call, but there are only two interesting
1155   // states we support: partial and full (or "simple") unrolling. However, to
1156   // enable these things we actually pass "None" in for the optional to avoid
1157   // providing an explicit choice.
1158   Optional<bool> AllowPartialParam, RuntimeParam, UpperBoundParam;
1159   if (!AllowPartialUnrolling)
1160     AllowPartialParam = RuntimeParam = UpperBoundParam = false;
1161   bool Changed = tryToUnrollLoop(
1162       &L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, *ORE,
1163       /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None,
1164       /*Threshold*/ None, AllowPartialParam, RuntimeParam, UpperBoundParam);
1165   if (!Changed)
1166     return PreservedAnalyses::all();
1167
1168   // The parent must not be damaged by unrolling!
1169 #ifndef NDEBUG
1170   if (ParentL)
1171     ParentL->verifyLoop();
1172 #endif
1173
1174   // Unrolling can do several things to introduce new loops into a loop nest:
1175   // - Partial unrolling clones child loops within the current loop. If it
1176   //   uses a remainder, then it can also create any number of sibling loops.
1177   // - Full unrolling clones child loops within the current loop but then
1178   //   removes the current loop making all of the children appear to be new
1179   //   sibling loops.
1180   // - Loop peeling can directly introduce new sibling loops by peeling one
1181   //   iteration.
1182   //
1183   // When a new loop appears as a sibling loop, either from peeling an
1184   // iteration or fully unrolling, its nesting structure has fundamentally
1185   // changed and we want to revisit it to reflect that.
1186   //
1187   // When unrolling has removed the current loop, we need to tell the
1188   // infrastructure that it is gone.
1189   //
1190   // Finally, we support a debugging/testing mode where we revisit child loops
1191   // as well. These are not expected to require further optimizations as either
1192   // they or the loop they were cloned from have been directly visited already.
1193   // But the debugging mode allows us to check this assumption.
1194   bool IsCurrentLoopValid = false;
1195   SmallVector<Loop *, 4> SibLoops;
1196   if (ParentL)
1197     SibLoops.append(ParentL->begin(), ParentL->end());
1198   else
1199     SibLoops.append(AR.LI.begin(), AR.LI.end());
1200   erase_if(SibLoops, [&](Loop *SibLoop) {
1201     if (SibLoop == &L) {
1202       IsCurrentLoopValid = true;
1203       return true;
1204     }
1205
1206     // Otherwise erase the loop from the list if it was in the old loops.
1207     return OldLoops.count(SibLoop) != 0;
1208   });
1209   Updater.addSiblingLoops(SibLoops);
1210
1211   if (!IsCurrentLoopValid) {
1212     Updater.markLoopAsDeleted(L);
1213   } else {
1214     // We can only walk child loops if the current loop remained valid.
1215     if (UnrollRevisitChildLoops) {
1216       // Walk *all* of the child loops. This is a highly speculative mode
1217       // anyways so look for any simplifications that arose from partial
1218       // unrolling or peeling off of iterations.
1219       SmallVector<Loop *, 4> ChildLoops(L.begin(), L.end());
1220       Updater.addChildLoops(ChildLoops);
1221     }
1222   }
1223
1224   return getLoopPassPreservedAnalyses();
1225 }