LLVM 24.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 "ScalarOptions.h"
16#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/StringRef.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"
42#include "llvm/IR/Dominators.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Metadata.h"
47#include "llvm/IR/PassManager.h"
49#include "llvm/Pass.h"
52#include "llvm/Support/Debug.h"
64#include <algorithm>
65#include <cassert>
66#include <cstdint>
67#include <limits>
68#include <optional>
69#include <string>
70#include <tuple>
71#include <utility>
72
73using namespace llvm;
74
75#define DEBUG_TYPE "loop-unroll"
76
78 const cl::LibraryOptionsContext &LibraryOptions) {
79 return LibraryOptions.get<ScalarOptions>().forget_scev_loop_unroll;
80}
81
82/// A magic value for use with the Threshold parameter to indicate
83/// that the loop unroll should be performed regardless of how much
84/// code expansion would result.
85static const unsigned NoThreshold = std::numeric_limits<unsigned>::max();
86
87/// Gather the various unrolling parameters based on the defaults, compiler
88/// flags, TTI overrides and user specified parameters.
92 OptimizationRemarkEmitter &ORE, int OptLevel,
93 std::optional<unsigned> UserThreshold, std::optional<bool> UserAllowPartial,
94 std::optional<bool> UserRuntime, std::optional<bool> UserUpperBound,
95 std::optional<unsigned> UserFullUnrollMaxCount) {
96 const ScalarOptions &Opts = getScalarOptions(*L);
98
99 // Set up the defaults that depend on options. All other fields use the
100 // default member initializers of UnrollingPreferences.
101 UP.Threshold = OptLevel > 2 ? Opts.unroll_threshold_aggressive
102 : Opts.unroll_threshold_default;
103 UP.OptSizeThreshold = Opts.unroll_optsize_threshold;
104 UP.PartialOptSizeThreshold = Opts.unroll_optsize_threshold;
106
107 // Override with any target specific settings
108 TTI.getUnrollingPreferences(L, SE, UP, &ORE);
109
110 // Apply size attributes
111 bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
112 // Let unroll hints / pragmas take precedence over PGSO.
114 llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI,
116 if (OptForSize) {
120 }
121
122 // Apply any user values specified by cl::opt
123 if (Opts.unroll_threshold)
124 UP.Threshold = *Opts.unroll_threshold;
125 if (Opts.unroll_partial_threshold)
126 UP.PartialThreshold = *Opts.unroll_partial_threshold;
127 if (Opts.unroll_max_percent_threshold_boost)
128 UP.MaxPercentThresholdBoost = *Opts.unroll_max_percent_threshold_boost;
129 if (Opts.unroll_max_count)
130 UP.MaxCount = *Opts.unroll_max_count;
131 if (Opts.unroll_max_upperbound)
132 UP.MaxUpperBound = *Opts.unroll_max_upperbound;
133 if (Opts.unroll_full_max_count)
134 UP.FullUnrollMaxCount = *Opts.unroll_full_max_count;
135 UP.Partial = valueOr(Opts.unroll_allow_partial, UP.Partial);
136 UP.AllowRemainder = valueOr(Opts.unroll_allow_remainder, UP.AllowRemainder);
137 UP.Runtime = valueOr(Opts.unroll_runtime, UP.Runtime);
138 if (Opts.unroll_max_upperbound == 0)
139 UP.UpperBound = false;
140 UP.UnrollRemainder = valueOr(Opts.unroll_remainder, UP.UnrollRemainder);
141 if (Opts.unroll_max_iteration_count_to_analyze)
143 *Opts.unroll_max_iteration_count_to_analyze;
144
145 // Apply user values provided by argument
146 if (UserThreshold) {
147 UP.Threshold = *UserThreshold;
148 UP.PartialThreshold = *UserThreshold;
149 }
150 if (UserAllowPartial)
151 UP.Partial = *UserAllowPartial;
152 if (UserRuntime)
153 UP.Runtime = *UserRuntime;
154 if (UserUpperBound)
155 UP.UpperBound = *UserUpperBound;
156 if (UserFullUnrollMaxCount)
157 UP.FullUnrollMaxCount = *UserFullUnrollMaxCount;
158
159 return UP;
160}
161
162namespace {
163
164/// A struct to densely store the state of an instruction after unrolling at
165/// each iteration.
166///
167/// This is designed to work like a tuple of <Instruction *, int> for the
168/// purposes of hashing and lookup, but to be able to associate two boolean
169/// states with each key.
170struct UnrolledInstState {
171 Instruction *I;
172 int Iteration : 30;
173 unsigned IsFree : 1;
174 unsigned IsCounted : 1;
175};
176
177/// Hashing and equality testing for a set of the instruction states.
178struct UnrolledInstStateKeyInfo {
179 using PairInfo = DenseMapInfo<std::pair<Instruction *, int>>;
180
181 static inline unsigned getHashValue(const UnrolledInstState &S) {
182 return PairInfo::getHashValue({S.I, S.Iteration});
183 }
184
185 static inline bool isEqual(const UnrolledInstState &LHS,
186 const UnrolledInstState &RHS) {
187 return PairInfo::isEqual({LHS.I, LHS.Iteration}, {RHS.I, RHS.Iteration});
188 }
189};
190
191struct EstimatedUnrollCost {
192 /// The estimated cost after unrolling.
193 unsigned UnrolledCost;
194
195 /// The estimated dynamic cost of executing the instructions in the
196 /// rolled form.
197 unsigned RolledDynamicCost;
198};
199
200} // end anonymous namespace
201
202/// Figure out if the loop is worth full unrolling.
203///
204/// Complete loop unrolling can make some loads constant, and we need to know
205/// if that would expose any further optimization opportunities. This routine
206/// estimates this optimization. It computes cost of unrolled loop
207/// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
208/// dynamic cost we mean that we won't count costs of blocks that are known not
209/// to be executed (i.e. if we have a branch in the loop and we know that at the
210/// given iteration its condition would be resolved to true, we won't add up the
211/// cost of the 'false'-block).
212/// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
213/// the analysis failed (no benefits expected from the unrolling, or the loop is
214/// too big to analyze), the returned value is std::nullopt.
215static std::optional<EstimatedUnrollCost> analyzeLoopUnrollCost(
216 const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE,
217 const SmallPtrSetImpl<const Value *> &EphValues,
218 const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize,
219 unsigned MaxIterationsCountToAnalyze) {
220 // We want to be able to scale offsets by the trip count and add more offsets
221 // to them without checking for overflows, and we already don't want to
222 // analyze *massive* trip counts, so we force the max to be reasonably small.
223 assert(MaxIterationsCountToAnalyze <
224 (unsigned)(std::numeric_limits<int>::max() / 2) &&
225 "The unroll iterations max is too large!");
226
227 // Only analyze inner loops. We can't properly estimate cost of nested loops
228 // and we won't visit inner loops again anyway.
229 if (!L->isInnermost()) {
231 << "Not analyzing loop cost: not an innermost loop.\n");
232 return std::nullopt;
233 }
234
235 // Don't simulate loops with a big or unknown tripcount
236 if (!TripCount || TripCount > MaxIterationsCountToAnalyze) {
238 << "Not analyzing loop cost: trip count "
239 << (TripCount ? "too large" : "unknown") << ".\n");
240 return std::nullopt;
241 }
242
245 DenseMap<Value *, Value *> SimplifiedValues;
246 SmallVector<std::pair<Value *, Value *>, 4> SimplifiedInputValues;
247
248 // The estimated cost of the unrolled form of the loop. We try to estimate
249 // this by simplifying as much as we can while computing the estimate.
250 InstructionCost UnrolledCost = 0;
251
252 // We also track the estimated dynamic (that is, actually executed) cost in
253 // the rolled form. This helps identify cases when the savings from unrolling
254 // aren't just exposing dead control flows, but actual reduced dynamic
255 // instructions due to the simplifications which we expect to occur after
256 // unrolling.
257 InstructionCost RolledDynamicCost = 0;
258
259 // We track the simplification of each instruction in each iteration. We use
260 // this to recursively merge costs into the unrolled cost on-demand so that
261 // we don't count the cost of any dead code. This is essentially a map from
262 // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
264
265 // A small worklist used to accumulate cost of instructions from each
266 // observable and reached root in the loop.
268
269 // PHI-used worklist used between iterations while accumulating cost.
271
272 // Helper function to accumulate cost for instructions in the loop.
273 auto AddCostRecursively = [&](Instruction &RootI, int Iteration) {
274 assert(Iteration >= 0 && "Cannot have a negative iteration!");
275 assert(CostWorklist.empty() && "Must start with an empty cost list");
276 assert(PHIUsedList.empty() && "Must start with an empty phi used list");
277 CostWorklist.push_back(&RootI);
279 RootI.getFunction()->hasMinSize() ?
282 for (;; --Iteration) {
283 do {
284 Instruction *I = CostWorklist.pop_back_val();
285
286 // InstCostMap only uses I and Iteration as a key, the other two values
287 // don't matter here.
288 auto CostIter = InstCostMap.find({I, Iteration, 0, 0});
289 if (CostIter == InstCostMap.end())
290 // If an input to a PHI node comes from a dead path through the loop
291 // we may have no cost data for it here. What that actually means is
292 // that it is free.
293 continue;
294 auto &Cost = *CostIter;
295 if (Cost.IsCounted)
296 // Already counted this instruction.
297 continue;
298
299 // Mark that we are counting the cost of this instruction now.
300 Cost.IsCounted = true;
301
302 // If this is a PHI node in the loop header, just add it to the PHI set.
303 if (auto *PhiI = dyn_cast<PHINode>(I))
304 if (PhiI->getParent() == L->getHeader()) {
305 assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
306 "inherently simplify during unrolling.");
307 if (Iteration == 0)
308 continue;
309
310 // Push the incoming value from the backedge into the PHI used list
311 // if it is an in-loop instruction. We'll use this to populate the
312 // cost worklist for the next iteration (as we count backwards).
313 if (auto *OpI = dyn_cast<Instruction>(
314 PhiI->getIncomingValueForBlock(L->getLoopLatch())))
315 if (L->contains(OpI))
316 PHIUsedList.push_back(OpI);
317 continue;
318 }
319
320 // First accumulate the cost of this instruction.
321 if (!Cost.IsFree) {
322 // Consider simplified operands in instruction cost.
324 transform(I->operands(), std::back_inserter(Operands),
325 [&](Value *Op) {
326 if (auto Res = SimplifiedValues.lookup(Op))
327 return Res;
328 return Op;
329 });
330 UnrolledCost += TTI.getInstructionCost(I, Operands, CostKind);
332 << "Adding cost of instruction (iteration " << Iteration
333 << "): ");
334 LLVM_DEBUG(I->dump());
335 }
336
337 // We must count the cost of every operand which is not free,
338 // recursively. If we reach a loop PHI node, simply add it to the set
339 // to be considered on the next iteration (backwards!).
340 for (Value *Op : I->operands()) {
341 // Check whether this operand is free due to being a constant or
342 // outside the loop.
343 auto *OpI = dyn_cast<Instruction>(Op);
344 if (!OpI || !L->contains(OpI))
345 continue;
346
347 // Otherwise accumulate its cost.
348 CostWorklist.push_back(OpI);
349 }
350 } while (!CostWorklist.empty());
351
352 if (PHIUsedList.empty())
353 // We've exhausted the search.
354 break;
355
356 assert(Iteration > 0 &&
357 "Cannot track PHI-used values past the first iteration!");
358 CostWorklist.append(PHIUsedList.begin(), PHIUsedList.end());
359 PHIUsedList.clear();
360 }
361 };
362
363 // Ensure that we don't violate the loop structure invariants relied on by
364 // this analysis.
365 assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
366 assert(L->isLCSSAForm(DT) &&
367 "Must have loops in LCSSA form to track live-out values.");
368
370 << "Starting LoopUnroll profitability analysis...\n");
371
373 L->getHeader()->getParent()->hasMinSize() ?
375 // Simulate execution of each iteration of the loop counting instructions,
376 // which would be simplified.
377 // Since the same load will take different values on different iterations,
378 // we literally have to go through all loop's iterations.
379 for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
380 LLVM_DEBUG(dbgs().indent(3) << "Analyzing iteration " << Iteration << "\n");
381
382 // Prepare for the iteration by collecting any simplified entry or backedge
383 // inputs.
384 for (Instruction &I : *L->getHeader()) {
385 auto *PHI = dyn_cast<PHINode>(&I);
386 if (!PHI)
387 break;
388
389 // The loop header PHI nodes must have exactly two input: one from the
390 // loop preheader and one from the loop latch.
391 assert(
392 PHI->getNumIncomingValues() == 2 &&
393 "Must have an incoming value only for the preheader and the latch.");
394
395 Value *V = PHI->getIncomingValueForBlock(
396 Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
397 if (Iteration != 0 && SimplifiedValues.contains(V))
398 V = SimplifiedValues.lookup(V);
399 SimplifiedInputValues.push_back({PHI, V});
400 }
401
402 // Now clear and re-populate the map for the next iteration.
403 SimplifiedValues.clear();
404 while (!SimplifiedInputValues.empty())
405 SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
406
407 UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
408
409 BBWorklist.clear();
410 BBWorklist.insert(L->getHeader());
411 // Note that we *must not* cache the size, this loop grows the worklist.
412 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
413 BasicBlock *BB = BBWorklist[Idx];
414
415 // Visit all instructions in the given basic block and try to simplify
416 // it. We don't change the actual IR, just count optimization
417 // opportunities.
418 for (Instruction &I : *BB) {
419 // These won't get into the final code - don't even try calculating the
420 // cost for them.
421 if (EphValues.contains(&I))
422 continue;
423
424 // Track this instruction's expected baseline cost when executing the
425 // rolled loop form.
426 RolledDynamicCost += TTI.getInstructionCost(&I, CostKind);
427
428 // Visit the instruction to analyze its loop cost after unrolling,
429 // and if the visitor returns true, mark the instruction as free after
430 // unrolling and continue.
431 bool IsFree = Analyzer.visit(I);
432 bool Inserted = InstCostMap.insert({&I, (int)Iteration,
433 (unsigned)IsFree,
434 /*IsCounted*/ false}).second;
435 (void)Inserted;
436 assert(Inserted && "Cannot have a state for an unvisited instruction!");
437
438 if (IsFree)
439 continue;
440
441 // Can't properly model a cost of a call.
442 // FIXME: With a proper cost model we should be able to do it.
443 if (auto *CI = dyn_cast<CallInst>(&I)) {
444 const Function *Callee = CI->getCalledFunction();
445 if (!Callee || TTI.isLoweredToCall(Callee)) {
447 << "Can't analyze cost of loop with call\n");
448 return std::nullopt;
449 }
450 }
451
452 // If the instruction might have a side-effect recursively account for
453 // the cost of it and all the instructions leading up to it.
454 if (I.mayHaveSideEffects())
455 AddCostRecursively(I, Iteration);
456
457 // If unrolled body turns out to be too big, bail out.
458 if (UnrolledCost > MaxUnrolledLoopSize) {
459 LLVM_DEBUG({
460 dbgs().indent(3) << "Exceeded threshold.. exiting.\n";
461 dbgs().indent(3)
462 << "UnrolledCost: " << UnrolledCost
463 << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize << "\n";
464 });
465 return std::nullopt;
466 }
467 }
468
469 Instruction *TI = BB->getTerminator();
470
471 auto getSimplifiedConstant = [&](Value *V) -> Constant * {
472 if (SimplifiedValues.contains(V))
473 V = SimplifiedValues.lookup(V);
474 return dyn_cast<Constant>(V);
475 };
476
477 // Add in the live successors by first checking whether we have terminator
478 // that may be simplified based on the values simplified by this call.
479 BasicBlock *KnownSucc = nullptr;
480 if (CondBrInst *BI = dyn_cast<CondBrInst>(TI)) {
481 if (auto *SimpleCond = getSimplifiedConstant(BI->getCondition())) {
482 // Just take the first successor if condition is undef
483 if (isa<UndefValue>(SimpleCond))
484 KnownSucc = BI->getSuccessor(0);
485 else if (ConstantInt *SimpleCondVal =
486 dyn_cast<ConstantInt>(SimpleCond))
487 KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
488 }
489 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
490 if (auto *SimpleCond = getSimplifiedConstant(SI->getCondition())) {
491 // Just take the first successor if condition is undef
492 if (isa<UndefValue>(SimpleCond))
493 KnownSucc = SI->getSuccessor(0);
494 else if (ConstantInt *SimpleCondVal =
495 dyn_cast<ConstantInt>(SimpleCond))
496 KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
497 }
498 }
499 if (KnownSucc) {
500 if (L->contains(KnownSucc))
501 BBWorklist.insert(KnownSucc);
502 else
503 ExitWorklist.insert({BB, KnownSucc});
504 continue;
505 }
506
507 // Add BB's successors to the worklist.
508 for (BasicBlock *Succ : successors(BB))
509 if (L->contains(Succ))
510 BBWorklist.insert(Succ);
511 else
512 ExitWorklist.insert({BB, Succ});
513 AddCostRecursively(*TI, Iteration);
514 }
515
516 // If we found no optimization opportunities on the first iteration, we
517 // won't find them on later ones too.
518 if (UnrolledCost == RolledDynamicCost) {
519 LLVM_DEBUG({
520 dbgs().indent(3) << "No opportunities found.. exiting.\n";
521 dbgs().indent(3) << "UnrolledCost: " << UnrolledCost << "\n";
522 });
523 return std::nullopt;
524 }
525 }
526
527 while (!ExitWorklist.empty()) {
528 BasicBlock *ExitingBB, *ExitBB;
529 std::tie(ExitingBB, ExitBB) = ExitWorklist.pop_back_val();
530
531 for (Instruction &I : *ExitBB) {
532 auto *PN = dyn_cast<PHINode>(&I);
533 if (!PN)
534 break;
535
536 Value *Op = PN->getIncomingValueForBlock(ExitingBB);
537 if (auto *OpI = dyn_cast<Instruction>(Op))
538 if (L->contains(OpI))
539 AddCostRecursively(*OpI, TripCount - 1);
540 }
541 }
542
543 assert(UnrolledCost.isValid() && RolledDynamicCost.isValid() &&
544 "All instructions must have a valid cost, whether the "
545 "loop is rolled or unrolled.");
546
547 LLVM_DEBUG({
548 dbgs().indent(3) << "Analysis finished:\n";
549 dbgs().indent(3) << "UnrolledCost: " << UnrolledCost
550 << ", RolledDynamicCost: " << RolledDynamicCost << "\n";
551 });
552 return {{unsigned(UnrolledCost.getValue()),
553 unsigned(RolledDynamicCost.getValue())}};
554}
555
557 const Loop *L, const TargetTransformInfo &TTI,
558 const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns,
559 bool PrepareForLTO, bool TripCountIsUniform) {
561 for (BasicBlock *BB : L->blocks())
562 Metrics.analyzeBasicBlock(BB, TTI, EphValues, PrepareForLTO, L);
563 NumInlineCandidates = Metrics.NumInlineCandidates;
564 NotDuplicatable = Metrics.notDuplicatable;
565 Convergence = Metrics.Convergence;
566 LoopSize = Metrics.NumInsts;
567 // Convergent operations make the remainder prelude unsafe by adding a
568 // control-flow dependency, unless the trip count is uniform per
569 // UniformityInfo, in which case all paths agree and the remainder is safe.
571 (Metrics.Convergence != ConvergenceKind::Uncontrolled &&
573 TripCountIsUniform;
574
575 // Don't allow an estimate of size zero. This would allows unrolling of loops
576 // with huge iteration counts, which is a compile time problem even if it's
577 // not a problem for code quality. Also, the code using this size may assume
578 // that each loop has at least three instructions (likely a conditional
579 // branch, a comparison feeding that branch, and some kind of loop increment
580 // feeding that comparison instruction).
581 if (LoopSize.isValid() && LoopSize < BEInsns + 1)
582 // This is an open coded max() on InstructionCost
583 LoopSize = BEInsns + 1;
584}
585
587 const Loop *L) const {
588 auto ReportCannotUnroll = [&](StringRef Reason) {
589 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: " << Reason << ".\n");
590 if (ORE && L)
591 ORE->emit([&]() {
592 return OptimizationRemarkMissed(DEBUG_TYPE, "CannotUnrollLoop",
593 L->getStartLoc(), L->getHeader())
594 << "unable to unroll loop: " << Reason;
595 });
596 };
597
599 ReportCannotUnroll("contains convergent operations");
600 return false;
601 }
602 if (!LoopSize.isValid()) {
603 ReportCannotUnroll("loop size could not be computed");
604 return false;
605 }
606 if (NotDuplicatable) {
607 ReportCannotUnroll("contains non-duplicatable instructions");
608 return false;
609 }
610 return true;
611}
612
614 const TargetTransformInfo::UnrollingPreferences &UP, unsigned Count) const {
615 unsigned LS = LoopSize.getValue();
616 assert(LS >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
617 return static_cast<uint64_t>(LS - UP.BEInsns) * Count + UP.BEInsns;
618}
619
620// Returns true if the loop has an unroll(full) pragma.
621static bool hasUnrollFullPragma(const Loop *L) {
622 return getUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
623}
624
625// Returns true if the loop has an unroll(enable) pragma. This metadata is used
626// for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
627static bool hasUnrollEnablePragma(const Loop *L) {
628 return getUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
629}
630
631// Returns true if the loop has a runtime unroll(disable) pragma.
632static bool hasRuntimeUnrollDisablePragma(const Loop *L) {
633 return getUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
634}
635
636/// Returns true if the SCEV expression is uniform, i.e., all threads in a
637/// convergent execution agree on its value. Recursively checks operands.
638/// Returns false if the SCEV could not be computed.
639static bool isSCEVUniform(const SCEV *S, UniformityInfo &UI) {
641 return false;
642 if (isa<SCEVConstant>(S))
643 return true;
644 if (auto *U = dyn_cast<SCEVUnknown>(S))
645 return UI.isUniformAtDef(U->getValue());
646 for (const SCEV *Op : S->operands()) {
647 if (!isSCEVUniform(Op, UI))
648 return false;
649 }
650 return true;
651}
652
653// If loop has an unroll_count pragma return the (necessarily
654// positive) value from the pragma. Otherwise return 0.
655static unsigned unrollCountPragmaValue(const Loop *L) {
656 MDNode *MD = getUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
657 if (MD) {
658 assert(MD->getNumOperands() == 2 &&
659 "Unroll count hint metadata should have two operands.");
660 unsigned Count =
661 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
662 assert(Count >= 1 && "Unroll count must be positive.");
663 return Count;
664 }
665 return 0;
666}
667
676
677// Computes the boosting factor for complete unrolling.
678// If fully unrolling the loop would save a lot of RolledDynamicCost, it would
679// be beneficial to fully unroll the loop even if unrolledcost is large. We
680// use (RolledDynamicCost / UnrolledCost) to model the unroll benefits to adjust
681// the unroll threshold.
682static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost,
683 unsigned MaxPercentThresholdBoost) {
684 if (Cost.RolledDynamicCost >= std::numeric_limits<unsigned>::max() / 100)
685 return 100;
686 else if (Cost.UnrolledCost != 0)
687 // The boosting factor is RolledDynamicCost / UnrolledCost
688 return std::min(100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
689 MaxPercentThresholdBoost);
690 else
691 return MaxPercentThresholdBoost;
692}
693
694static std::optional<unsigned>
695shouldPragmaUnroll(const ScalarOptions &Opts, Loop *L,
696 const UnrollPragmaInfo &PInfo, const unsigned TripMultiple,
697 const unsigned TripCount, unsigned MaxTripCount,
698 const UnrollCostEstimator UCE,
701
702 // Using unroll pragma
703 // 1st priority is unroll count set by "unroll-count" option.
704
705 if (PInfo.UserUnrollCount) {
706 if (UP.AllowRemainder &&
707 UCE.getUnrolledLoopSize(UP, *Opts.unroll_count) < UP.Threshold) {
708 LLVM_DEBUG(dbgs().indent(2) << "Unrolling with user-specified count: "
709 << *Opts.unroll_count << ".\n");
710 return *Opts.unroll_count;
711 }
713 << "Not unrolling with user count " << *Opts.unroll_count << ": "
714 << (UP.AllowRemainder ? "exceeds threshold"
715 : "remainder not allowed")
716 << ".\n");
717 }
718
719 // 2nd priority is unroll count set by pragma.
720 if (PInfo.PragmaCount > 0) {
721 if ((UP.AllowRemainder || (TripMultiple % PInfo.PragmaCount == 0))) {
722 LLVM_DEBUG(dbgs().indent(2) << "Unrolling with pragma count: "
723 << PInfo.PragmaCount << ".\n");
724 return PInfo.PragmaCount;
725 }
727 << "Not unrolling with pragma count " << PInfo.PragmaCount
728 << ": remainder not allowed, count does not divide trip "
729 << "multiple " << TripMultiple << ".\n");
730 ORE->emit([&]() {
731 return OptimizationRemarkAnalysis(DEBUG_TYPE, "PragmaUnrollCountRejected",
732 L->getStartLoc(), L->getHeader())
733 << "may be unable to unroll loop with count "
734 << ore::NV("PragmaCount", PInfo.PragmaCount)
735 << ": remainder loop is not allowed and count does not divide "
736 "trip multiple "
737 << ore::NV("TripMultiple", TripMultiple);
738 });
739 }
740
741 if (PInfo.PragmaFullUnroll) {
742 if (TripCount != 0) {
743 // Certain cases with UBSAN can cause trip count to be calculated as
744 // INT_MAX, Block full unrolling at a reasonable limit so that the
745 // compiler doesn't hang trying to unroll the loop. See PR77842
746 if (TripCount > Opts.pragma_unroll_full_max_iterations) {
748 << "Won't unroll; trip count is too large.\n");
749 ORE->emit([&]() {
751 "PragmaFullUnrollTripCountTooLarge",
752 L->getStartLoc(), L->getHeader())
753 << "may be unable to fully unroll loop: trip count "
754 << ore::NV("TripCount", TripCount) << " exceeds limit "
755 << ore::NV("Limit", Opts.pragma_unroll_full_max_iterations);
756 });
757 return std::nullopt;
758 }
759
761 << "Fully unrolling with trip count: " << TripCount << ".\n");
762 return TripCount;
763 }
765 << "Not fully unrolling: unknown trip count.\n");
766 ORE->emit([&]() {
768 "PragmaFullUnrollUnknownTripCount",
769 L->getStartLoc(), L->getHeader())
770 << "may be unable to fully unroll loop: trip count is unknown";
771 });
772 }
773
774 if (PInfo.PragmaEnableUnroll && !TripCount && MaxTripCount &&
775 MaxTripCount <= UP.MaxUpperBound) {
777 << "Unrolling with max trip count: " << MaxTripCount << ".\n");
778 return MaxTripCount;
779 }
780
781 return std::nullopt;
782}
783
784static std::optional<unsigned> shouldFullUnroll(
787 const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE,
789 assert(FullUnrollTripCount && "should be non-zero!");
790
791 if (FullUnrollTripCount > UP.FullUnrollMaxCount) {
793 << "Not unrolling: trip count " << FullUnrollTripCount
794 << " exceeds max count " << UP.FullUnrollMaxCount << ".\n");
795 return std::nullopt;
796 }
797
798 // When computing the unrolled size, note that BEInsns are not replicated
799 // like the rest of the loop body.
800 uint64_t UnrolledSize = UCE.getUnrolledLoopSize(UP, FullUnrollTripCount);
801 if (UnrolledSize < UP.Threshold) {
802 LLVM_DEBUG(dbgs().indent(2) << "Unrolling: size " << UnrolledSize
803 << " < threshold " << UP.Threshold << ".\n");
804 return FullUnrollTripCount;
805 }
806
808 << "Unrolled size " << UnrolledSize << " exceeds threshold "
809 << UP.Threshold << "; checking for cost benefit.\n");
810
811 // The loop isn't that small, but we still can fully unroll it if that
812 // helps to remove a significant number of instructions.
813 // To check that, run additional analysis on the loop.
814 if (std::optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
815 L, FullUnrollTripCount, DT, SE, EphValues, TTI,
818 unsigned Boost =
820 unsigned BoostedThreshold = UP.Threshold * Boost / 100;
821 if (Cost->UnrolledCost < BoostedThreshold) {
822 LLVM_DEBUG(dbgs().indent(2) << "Profitable after cost analysis.\n");
823 return FullUnrollTripCount;
824 }
826 << "Not unrolling: cost " << Cost->UnrolledCost
827 << " >= boosted threshold " << BoostedThreshold << ".\n");
828 }
829
830 return std::nullopt;
831}
832
833static std::optional<unsigned>
834shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount,
835 const UnrollCostEstimator UCE,
837
838 if (!TripCount)
839 return std::nullopt;
840
841 if (!UP.Partial) {
842 LLVM_DEBUG(dbgs().indent(2) << "Will not try to unroll partially because "
843 << "-unroll-allow-partial not given\n");
844 return 0;
845 }
846 unsigned Count = TripCount;
847 if (UP.PartialThreshold != NoThreshold) {
848 // Reduce unroll count to be modulo of TripCount for partial unrolling.
849 if (UCE.getUnrolledLoopSize(UP, Count) > UP.PartialThreshold) {
850 unsigned NewCount =
851 (std::max(UP.PartialThreshold, UP.BEInsns + 1) - UP.BEInsns) /
852 (LoopSize - UP.BEInsns);
854 << "Unrolled size exceeds threshold; reducing count "
855 << "from " << Count << " to " << NewCount << ".\n");
856 Count = NewCount;
857 }
858 if (Count > UP.MaxCount)
859 Count = UP.MaxCount;
860 while (Count != 0 && TripCount % Count != 0)
861 Count--;
862 if (UP.AllowRemainder && Count <= 1) {
863 // If there is no Count that is modulo of TripCount, set Count to
864 // largest power-of-two factor that satisfies the threshold limit.
865 // As we'll create fixup loop, do the type of unrolling only if
866 // remainder loop is allowed.
867 // Note: DefaultUnrollRuntimeCount is used as a reasonable starting point
868 // even though this is partial unrolling (not runtime unrolling).
870 while (Count != 0 &&
872 Count >>= 1;
873 }
874 if (Count < 2) {
876 << "Will not partially unroll: no profitable count.\n");
877 Count = 0;
878 }
879 } else {
880 Count = TripCount;
881 }
882 if (Count > UP.MaxCount)
883 Count = UP.MaxCount;
884
886 << "Partially unrolling with count: " << Count << "\n");
887
888 return Count;
889}
890
891static unsigned
892shouldRuntimeUnroll(Loop *L, unsigned MaxTripCount, unsigned TripMultiple,
893 const UnrollCostEstimator &UCE,
894 const UnrollPragmaInfo &PInfo, const ScalarOptions &Opts,
896 // Don't unroll a runtime trip count loop when it is disabled.
897 if (PInfo.PragmaRuntimeUnrollDisable) {
899 << "Not runtime unrolling: disabled by pragma.\n");
900 return 0;
901 }
902
903 // Don't unroll a small upper bound loop unless user or TTI asked to do so.
904 if (MaxTripCount && !UP.Force && MaxTripCount <= UP.MaxUpperBound) {
905 LLVM_DEBUG(dbgs().indent(2) << "Not runtime unrolling: max trip count "
906 << MaxTripCount << " is small (<= "
907 << UP.MaxUpperBound << ") and not forced.\n");
908 return 0;
909 }
910
911 // Check if the runtime trip count is too small when profile is available.
912 if (L->getHeader()->getParent()->hasProfileData()) {
913 if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
914 if (*ProfileTripCount < Opts.flat_loop_tripcount_threshold)
915 return 0;
916 else
917 UP.AllowExpensiveTripCount = true;
918 }
919 }
920 if (!UP.Runtime) {
922 << "Will not try to unroll loop with runtime trip count "
923 << "because -unroll-runtime not given\n");
924 return 0;
925 }
926
927 unsigned Count = UP.DefaultUnrollRuntimeCount;
928
929 // Reduce unroll count to be the largest power-of-two factor of
930 // the original count which satisfies the threshold limit.
931 while (Count != 0 && UCE.getUnrolledLoopSize(UP, Count) > UP.PartialThreshold)
932 Count >>= 1;
933
934#ifndef NDEBUG
935 unsigned OrigCount = Count;
936#endif
937
938 if (!UP.AllowRemainder && Count != 0 && (TripMultiple % Count) != 0) {
939 while (Count != 0 && TripMultiple % Count != 0)
940 Count >>= 1;
942 << "Remainder loop is restricted (that could be architecture "
943 "specific or because the loop contains a convergent "
944 "instruction), so unroll count must divide the trip "
945 "multiple, "
946 << TripMultiple << ". Reducing unroll count from " << OrigCount
947 << " to " << Count << ".\n");
948 }
949
950 if (Count > UP.MaxCount)
951 Count = UP.MaxCount;
952
953 if (MaxTripCount && Count > MaxTripCount)
954 Count = MaxTripCount;
955
956 if (Count < 2)
957 Count = 0;
958 else
960 << "Runtime unrolling with count: " << Count << "\n");
961 return Count;
962}
963
964// Calculates and returns the unroll count, using metadata and command-line
965// options that are specific to the LoopUnroll pass (which, for instance, are
966// irrelevant for the LoopUnrollAndJam pass).
967// FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
968// many LoopUnroll-specific options. The shared functionality should be
969// refactored into it own function.
973 const SmallPtrSetImpl<const Value *> &EphValues,
974 OptimizationRemarkEmitter *ORE, const unsigned TripCount,
975 const unsigned MaxTripCount, const bool MaxOrZero,
976 const unsigned TripMultiple, const UnrollCostEstimator &UCE,
979 const ScalarOptions &Opts = getScalarOptions(*L);
980
981 unsigned LoopSize = UCE.getRolledLoopSize();
982
983 LLVM_DEBUG(dbgs().indent(1) << "Computing unroll count: TripCount="
984 << TripCount << ", MaxTripCount=" << MaxTripCount
985 << (MaxOrZero ? " (MaxOrZero)" : "")
986 << ", TripMultiple=" << TripMultiple << "\n");
987
988 UnrollPragmaInfo PInfo(L);
989 LLVM_DEBUG({
990 if (PInfo.ExplicitUnroll) {
991 dbgs().indent(1) << "Explicit unroll requested:";
992 if (PInfo.UserUnrollCount)
993 dbgs() << " user-count";
994 if (PInfo.PragmaFullUnroll)
995 dbgs() << " pragma-full";
996 if (PInfo.PragmaCount > 0)
997 dbgs() << " pragma-count(" << PInfo.PragmaCount << ")";
998 if (PInfo.PragmaEnableUnroll)
999 dbgs() << " pragma-enable";
1000 dbgs() << "\n";
1001 }
1002 });
1003
1004 // Use an explicit peel count that has been specified for testing. In this
1005 // case it's not permitted to also specify an explicit unroll count.
1006 if (PP.PeelCount) {
1007 if (Opts.unroll_count) {
1008 reportFatalUsageError("Cannot specify both explicit peel count and "
1009 "explicit unroll count");
1010 }
1012 << "Using explicit peel count: " << PP.PeelCount << ".\n");
1013 UP.Runtime = false;
1014 return 1;
1015 }
1016
1017 // If a user provided an explicit unroll pragma (with or without count),
1018 // enable runtime unrolling and override expensive trip count checks.
1019 if (PInfo.PragmaEnableUnroll || PInfo.PragmaCount > 0) {
1020 UP.AllowExpensiveTripCount = true;
1021 UP.Runtime = true;
1022 }
1023
1024 // Check for an explicit unroll count.
1025 // 1st priority is unroll count set by "unroll-count" option.
1026 // 2nd priority is unroll count set by pragma.
1027 LLVM_DEBUG(dbgs().indent(1) << "Trying pragma unroll...\n");
1028 if (auto UnrollFactor =
1029 shouldPragmaUnroll(Opts, L, PInfo, TripMultiple, TripCount,
1030 MaxTripCount, UCE, UP, ORE)) {
1031 if (PInfo.UserUnrollCount || (PInfo.PragmaCount > 0)) {
1032 UP.AllowExpensiveTripCount = true;
1033 UP.Force = true;
1034 }
1035 return *UnrollFactor;
1036 } else {
1037 if (PInfo.ExplicitUnroll && TripCount != 0) {
1038 // If the loop has an unrolling pragma, we want to be more aggressive with
1039 // unrolling limits. Set thresholds to at least the PragmaUnrollThreshold
1040 // value which is larger than the default limits.
1041 UP.Threshold = std::max(UP.Threshold, Opts.pragma_unroll_threshold);
1042 UP.PartialThreshold =
1043 std::max(UP.PartialThreshold, Opts.pragma_unroll_threshold);
1044 }
1045 }
1046
1047 // 3rd priority is exact full unrolling. This will eliminate all copies
1048 // of some exit test.
1049 LLVM_DEBUG(dbgs().indent(1) << "Trying full unroll...\n");
1050 if (TripCount) {
1051 if (auto UnrollFactor =
1052 shouldFullUnroll(L, TTI, DT, SE, EphValues, TripCount, UCE, UP))
1053 return *UnrollFactor;
1054 }
1055
1056 // 4th priority is bounded unrolling.
1057 // We can unroll by the upper bound amount if it's generally allowed or if
1058 // we know that the loop is executed either the upper bound or zero times.
1059 // (MaxOrZero unrolling keeps only the first loop test, so the number of
1060 // loop tests remains the same compared to the non-unrolled version, whereas
1061 // the generic upper bound unrolling keeps all but the last loop test so the
1062 // number of loop tests goes up which may end up being worse on targets with
1063 // constrained branch predictor resources so is controlled by an option.)
1064 // In addition we only unroll small upper bounds.
1065 // Note that the cost of bounded unrolling is always strictly greater than
1066 // cost of exact full unrolling. As such, if we have an exact count and
1067 // found it unprofitable, we'll never chose to bounded unroll.
1068 LLVM_DEBUG(dbgs().indent(1) << "Trying upper-bound unroll...\n");
1069 if (!TripCount && MaxTripCount && (UP.UpperBound || MaxOrZero) &&
1070 MaxTripCount <= UP.MaxUpperBound) {
1071 if (auto UnrollFactor =
1072 shouldFullUnroll(L, TTI, DT, SE, EphValues, MaxTripCount, UCE, UP))
1073 return *UnrollFactor;
1074 }
1075
1076 // 5th priority is loop peeling.
1077 LLVM_DEBUG(dbgs().indent(1) << "Trying loop peeling...\n");
1078 computePeelCount(L, LoopSize, PP, TripCount, DT, SE, TTI, AC, UP.Threshold);
1079 if (PP.PeelCount) {
1081 << "Peeling with count: " << PP.PeelCount << ".\n");
1082 UP.Runtime = false;
1083 return 1;
1084 }
1085
1086 // Before starting partial unrolling, set UP.Partial to true,
1087 // if user explicitly asked for unrolling.
1088 if (TripCount)
1089 UP.Partial |= PInfo.ExplicitUnroll;
1090
1091 // 6th priority is partial unrolling.
1092 // Try partial unroll only when TripCount could be statically calculated.
1093 LLVM_DEBUG(dbgs().indent(1) << "Trying partial unroll...\n");
1094 if (auto UnrollFactor = shouldPartialUnroll(LoopSize, TripCount, UCE, UP))
1095 return *UnrollFactor;
1096 assert(TripCount == 0 &&
1097 "All cases when TripCount is constant should be covered here.");
1098
1099 // 7th priority is runtime unrolling.
1100 LLVM_DEBUG(dbgs().indent(1) << "Trying runtime unroll...\n");
1101 return shouldRuntimeUnroll(L, MaxTripCount, TripMultiple, UCE, PInfo, Opts,
1102 UP);
1103}
1104
1105static LoopUnrollResult
1109 ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel,
1110 bool OnlyFullUnroll, bool OnlyWhenForced, bool ForgetAllSCEV,
1111 bool PrepareForLTO, std::optional<unsigned> ProvidedThreshold,
1112 std::optional<bool> ProvidedAllowPartial,
1113 std::optional<bool> ProvidedRuntime,
1114 std::optional<bool> ProvidedUpperBound,
1115 std::optional<bool> ProvidedAllowPeeling,
1116 std::optional<bool> ProvidedAllowProfileBasedPeeling,
1117 std::optional<unsigned> ProvidedFullUnrollMaxCount,
1118 UniformityInfo *UI = nullptr, AAResults *AA = nullptr) {
1119
1120 LLVM_DEBUG(dbgs() << "Loop Unroll: F["
1121 << L->getHeader()->getParent()->getName() << "] Loop %"
1122 << L->getHeader()->getName()
1123 << " (depth=" << L->getLoopDepth() << ")\n");
1125 if (TM & TM_Disable) {
1126 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: transformation disabled by "
1127 << "metadata.\n");
1129 }
1130
1131 // If this loop isn't forced to be unrolled, avoid unrolling it when the
1132 // parent loop has an explicit unroll-and-jam pragma. This is to prevent
1133 // automatic unrolling from interfering with the user requested
1134 // transformation.
1135 Loop *ParentL = L->getParentLoop();
1136 if (ParentL != nullptr &&
1139 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling loop since parent loop has"
1140 << " llvm.loop.unroll_and_jam.\n");
1142 }
1143
1144 // If this loop isn't forced to be unrolled, avoid unrolling it when the
1145 // loop has an explicit unroll-and-jam pragma. This is to prevent automatic
1146 // unrolling from interfering with the user requested transformation.
1149 LLVM_DEBUG(
1150 dbgs().indent(1)
1151 << "Not unrolling loop since it has llvm.loop.unroll_and_jam.\n");
1153 }
1154
1155 if (!L->isLoopSimplifyForm()) {
1157 << "Not unrolling loop which is not in loop-simplify form.\n");
1158 if (TM & TM_ForcedByUser) {
1159 ORE.emit([&]() {
1160 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInLoopSimplifyForm",
1161 L->getStartLoc(), L->getHeader())
1162 << "unable to unroll loop: not in loop-simplify form";
1163 });
1164 }
1166 }
1167
1168 // When automatic unrolling is disabled, do not unroll unless overridden for
1169 // this loop.
1170 if (OnlyWhenForced && !(TM & TM_Enable)) {
1171 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: automatic unrolling "
1172 << "disabled and loop not explicitly "
1173 << "enabled.\n");
1175 }
1176
1177 bool OptForSize = L->getHeader()->getParent()->hasOptSize();
1179 L, SE, TTI, BFI, PSI, ORE, OptLevel, ProvidedThreshold,
1180 ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1181 ProvidedFullUnrollMaxCount);
1183 L, SE, TTI, ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling, true);
1184
1185 // Exit early if unrolling is disabled. For OptForSize, we pick the loop size
1186 // as threshold later on.
1187 if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0) &&
1188 !OptForSize) {
1189 LLVM_DEBUG(dbgs().indent(1) << "Not unrolling: all thresholds are zero.\n");
1190 if (TM & TM_ForcedByUser) {
1191 ORE.emit([&]() {
1192 return OptimizationRemarkMissed(DEBUG_TYPE, "UnrollThresholdsZero",
1193 L->getStartLoc(), L->getHeader())
1194 << "unable to unroll loop: unroll threshold is zero";
1195 });
1196 }
1198 }
1199
1201 CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
1202
1203 // Check if the backedge-taken count is uniform before constructing UCE.
1204 // This is used to allow runtime unrolling with a remainder for convergent
1205 // loops when all threads agree on the trip count.
1206 const SCEV *BTC = SE.getBackedgeTakenCount(L);
1207 bool TripCountIsUniform = UI && isSCEVUniform(BTC, *UI);
1208 UnrollCostEstimator UCE(L, TTI, EphValues, UP.BEInsns, PrepareForLTO,
1209 TripCountIsUniform);
1210 if (!UCE.canUnroll((TM & TM_ForcedByUser) ? &ORE : nullptr, L))
1212
1213 unsigned LoopSize = UCE.getRolledLoopSize();
1214 LLVM_DEBUG(dbgs() << "Loop Size = " << LoopSize << "\n");
1215
1216 // When optimizing for size, use LoopSize + 1 as threshold (we use < Threshold
1217 // later), to (fully) unroll loops, if it does not increase code size.
1218 if (OptForSize)
1219 UP.Threshold = std::max(UP.Threshold, LoopSize + 1);
1220
1221 if (UCE.NumInlineCandidates != 0) {
1223 << "Not unrolling loop with inlinable calls.\n");
1224 if (TM & TM_ForcedByUser) {
1225 ORE.emit([&]() {
1227 "InlineCandidatesPreventUnroll",
1228 L->getStartLoc(), L->getHeader())
1229 << "unable to unroll loop: contains inlinable calls";
1230 });
1231 }
1233 }
1234
1235 // Find the smallest exact trip count for any exit. This is an upper bound
1236 // on the loop trip count, but an exit at an earlier iteration is still
1237 // possible. An unroll by the smallest exact trip count guarantees that all
1238 // branches relating to at least one exit can be eliminated. This is unlike
1239 // the max trip count, which only guarantees that the backedge can be broken.
1240 unsigned TripCount = 0;
1241 unsigned TripMultiple = 1;
1242 SmallVector<BasicBlock *, 8> ExitingBlocks;
1243 L->getExitingBlocks(ExitingBlocks);
1244 for (BasicBlock *ExitingBlock : ExitingBlocks)
1245 if (unsigned TC = SE.getSmallConstantTripCount(L, ExitingBlock))
1246 if (!TripCount || TC < TripCount)
1247 TripCount = TripMultiple = TC;
1248
1249 if (!TripCount) {
1250 // If no exact trip count is known, determine the trip multiple of either
1251 // the loop latch or the single exiting block.
1252 // TODO: Relax for multiple exits.
1253 BasicBlock *ExitingBlock = L->getLoopLatch();
1254 if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
1255 ExitingBlock = L->getExitingBlock();
1256 if (ExitingBlock)
1257 TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
1258 }
1259
1260 // If the loop contains a convergent operation, the prelude we'd add
1261 // to do the first few instructions before we hit the unrolled loop
1262 // is unsafe -- it adds a control-flow dependency to the convergent
1263 // operation. Therefore restrict remainder loop (try unrolling without).
1265
1266 // Try to find the trip count upper bound if we cannot find the exact trip
1267 // count.
1268 unsigned MaxTripCount = 0;
1269 bool MaxOrZero = false;
1270 if (!TripCount) {
1271 MaxTripCount = SE.getSmallConstantMaxTripCount(L);
1272 MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
1273 }
1274
1275 // computeUnrollCount() decides whether it is beneficial to use upper bound to
1276 // fully unroll the loop.
1277 unsigned Count =
1278 computeUnrollCount(L, TTI, DT, LI, &AC, SE, EphValues, &ORE, TripCount,
1279 MaxTripCount, MaxOrZero, TripMultiple, UCE, UP, PP);
1280 if (!Count) {
1282 << "Not unrolling: no viable strategy found.\n");
1283 if (TM & TM_ForcedByUser) {
1284 ORE.emit([&]() {
1285 return OptimizationRemarkMissed(DEBUG_TYPE, "NoUnrollStrategy",
1286 L->getStartLoc(), L->getHeader())
1287 << "unable to unroll loop: no viable unroll count found";
1288 });
1289 }
1291 }
1292
1294
1295 if (PP.PeelCount) {
1296 assert(Count == 1 && "Cannot perform peel and unroll in the same step");
1297 LLVM_DEBUG(dbgs() << "PEELING loop %" << L->getHeader()->getName()
1298 << " with iteration count " << PP.PeelCount << "!\n");
1299 ORE.emit([&]() {
1300 return OptimizationRemark(DEBUG_TYPE, "Peeled", L->getStartLoc(),
1301 L->getHeader())
1302 << "peeled loop by " << ore::NV("PeelCount", PP.PeelCount)
1303 << " iterations";
1304 });
1305
1306 ValueToValueMapTy VMap;
1307 peelLoop(L, PP.PeelCount, PP.PeelLast, LI, &SE, DT, &AC, PreserveLCSSA,
1308 VMap);
1309 simplifyLoopAfterUnroll(L, true, LI, &SE, &DT, &AC, &TTI, L->getBlocks(),
1310 nullptr);
1311 // If the loop was peeled, we already "used up" the profile information
1312 // we had, so we don't want to unroll or peel again.
1314 L->setLoopAlreadyUnrolled();
1316 }
1317
1318 // Do not attempt partial/runtime unrolling in FullLoopUnrolling
1319 if (OnlyFullUnroll && ((!TripCount && !MaxTripCount) || Count < TripCount ||
1320 Count < MaxTripCount)) {
1322 << "Not attempting partial/runtime unroll in FullLoopUnroll.\n");
1324 }
1325
1326 // At this point, UP.Runtime indicates that run-time unrolling is allowed.
1327 // However, we only want to actually perform it if we don't know the trip
1328 // count and the unroll count doesn't divide the known trip multiple.
1329 // TODO: This decision should probably be pushed up into
1330 // computeUnrollCount().
1331 UP.Runtime &= TripCount == 0 && TripMultiple % Count != 0;
1332
1333 // Save loop properties before it is transformed.
1334 MDNode *OrigLoopID = L->getLoopID();
1335 UnrollPragmaInfo PInfo(L);
1336 DebugLoc LoopStartLoc = L->getStartLoc();
1337 BasicBlock *LoopHeader = L->getHeader();
1338
1339 // Unroll the loop.
1340 Loop *RemainderLoop = nullptr;
1342 ULO.Count = Count;
1343 ULO.Force = UP.Force;
1346 ULO.Runtime = UP.Runtime;
1347 ULO.ForgetAllSCEV = ForgetAllSCEV;
1352 LoopUnrollResult UnrollResult = UnrollLoop(
1353 L, ULO, LI, &SE, &DT, &AC, &TTI, &ORE, PreserveLCSSA, &RemainderLoop, AA);
1354 if (UnrollResult == LoopUnrollResult::Unmodified) {
1355 if (PInfo.ExplicitUnroll) {
1357 << "Failed to unroll loop as explicitly requested.\n");
1358 ORE.emit([&]() {
1359 return OptimizationRemarkMissed(DEBUG_TYPE, "FailedToUnrollAsRequested",
1360 LoopStartLoc, LoopHeader)
1361 << "failed to unroll loop as explicitly requested";
1362 });
1363 }
1365 }
1366
1367 if (PInfo.PragmaFullUnroll && ULO.Count != TripCount) {
1368 ORE.emit([&]() {
1369 return OptimizationRemarkMissed(DEBUG_TYPE, "FullUnrollAsDirectedFailed",
1370 LoopStartLoc, LoopHeader)
1371 << "unable to fully unroll loop as directed; "
1372 << "unrolled by factor " << ore::NV("UnrollCount", ULO.Count);
1373 });
1374 }
1375 if (PInfo.PragmaCount > 0 && ULO.Count != PInfo.PragmaCount) {
1376 ORE.emit([&]() {
1377 return OptimizationRemarkMissed(DEBUG_TYPE, "UnrollCountDiffers",
1378 LoopStartLoc, LoopHeader)
1379 << "unable to unroll loop with requested count "
1380 << ore::NV("RequestedCount", PInfo.PragmaCount)
1381 << "; unrolled by factor " << ore::NV("UnrollCount", ULO.Count);
1382 });
1383 }
1384
1385 if (RemainderLoop) {
1386 std::optional<MDNode *> RemainderLoopID =
1389 if (RemainderLoopID)
1390 RemainderLoop->setLoopID(*RemainderLoopID);
1391 }
1392
1393 if (UnrollResult != LoopUnrollResult::FullyUnrolled) {
1394 std::optional<MDNode *> NewLoopID =
1397 if (NewLoopID) {
1398 L->setLoopID(*NewLoopID);
1399
1400 // Do not setLoopAlreadyUnrolled if loop attributes have been specified
1401 // explicitly.
1402 return UnrollResult;
1403 }
1404 }
1405
1406 // If loop has an unroll count pragma or unrolled by explicitly set count
1407 // mark loop as unrolled to prevent unrolling beyond that requested.
1408 if (UnrollResult != LoopUnrollResult::FullyUnrolled && PInfo.ExplicitUnroll)
1409 L->setLoopAlreadyUnrolled();
1410
1411 return UnrollResult;
1412}
1413
1414namespace {
1415
1416class LoopUnroll : public LoopPass {
1417public:
1418 static char ID; // Pass ID, replacement for typeid
1419
1420 int OptLevel;
1421
1422 /// If false, use a cost model to determine whether unrolling of a loop is
1423 /// profitable. If true, only loops that explicitly request unrolling via
1424 /// metadata are considered. All other loops are skipped.
1425 bool OnlyWhenForced;
1426
1427 /// If false, when SCEV is invalidated, only forget everything in the
1428 /// top-most loop (call forgetTopMostLoop), of the loop being processed.
1429 /// Otherwise, forgetAllLoops and rebuild when needed next.
1430 bool ForgetAllSCEV;
1431
1432 std::optional<unsigned> ProvidedThreshold;
1433 std::optional<bool> ProvidedAllowPartial;
1434 std::optional<bool> ProvidedRuntime;
1435 std::optional<bool> ProvidedUpperBound;
1436 std::optional<bool> ProvidedAllowPeeling;
1437 std::optional<bool> ProvidedAllowProfileBasedPeeling;
1438 std::optional<unsigned> ProvidedFullUnrollMaxCount;
1439
1440 LoopUnroll(int OptLevel = 2, bool OnlyWhenForced = false,
1441 bool ForgetAllSCEV = false,
1442 std::optional<unsigned> Threshold = std::nullopt,
1443 std::optional<bool> AllowPartial = std::nullopt,
1444 std::optional<bool> Runtime = std::nullopt,
1445 std::optional<bool> UpperBound = std::nullopt,
1446 std::optional<bool> AllowPeeling = std::nullopt,
1447 std::optional<bool> AllowProfileBasedPeeling = std::nullopt,
1448 std::optional<unsigned> ProvidedFullUnrollMaxCount = std::nullopt)
1449 : LoopPass(ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
1450 ForgetAllSCEV(ForgetAllSCEV), ProvidedThreshold(Threshold),
1451 ProvidedAllowPartial(AllowPartial), ProvidedRuntime(Runtime),
1452 ProvidedUpperBound(UpperBound), ProvidedAllowPeeling(AllowPeeling),
1453 ProvidedAllowProfileBasedPeeling(AllowProfileBasedPeeling),
1454 ProvidedFullUnrollMaxCount(ProvidedFullUnrollMaxCount) {
1456 }
1457
1458 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1459 if (skipLoop(L))
1460 return false;
1461
1462 Function &F = *L->getHeader()->getParent();
1463
1464 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1465 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1466 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1467 const TargetTransformInfo &TTI =
1468 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1469 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1470 UniformityInfo *UI =
1472 ? &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo()
1473 : nullptr;
1474 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
1475 // pass. Function analyses need to be preserved across loop transformations
1476 // but ORE cannot be preserved (see comment before the pass definition).
1477 OptimizationRemarkEmitter ORE(&F);
1478 bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1479
1481 L, DT, LI, SE, TTI, AC, ORE, nullptr, nullptr, PreserveLCSSA, OptLevel,
1482 /*OnlyFullUnroll*/ false, OnlyWhenForced, ForgetAllSCEV,
1483 /*PrepareForLTO*/ false, ProvidedThreshold, ProvidedAllowPartial,
1484 ProvidedRuntime, ProvidedUpperBound, ProvidedAllowPeeling,
1485 ProvidedAllowProfileBasedPeeling, ProvidedFullUnrollMaxCount, UI);
1486
1487 if (Result == LoopUnrollResult::FullyUnrolled)
1488 LPM.markLoopAsDeleted(*L);
1489
1490 return Result != LoopUnrollResult::Unmodified;
1491 }
1492
1493 /// This transformation requires natural loop information & requires that
1494 /// loop preheaders be inserted into the CFG...
1495 void getAnalysisUsage(AnalysisUsage &AU) const override {
1496 AU.addRequired<AssumptionCacheTracker>();
1497 AU.addRequired<TargetTransformInfoWrapperPass>();
1498 AU.addRequired<UniformityInfoWrapperPass>();
1499 // FIXME: Loop passes are required to preserve domtree, and for now we just
1500 // recreate dom info if anything gets unrolled.
1502 }
1503};
1504
1505} // end anonymous namespace
1506
1507char LoopUnroll::ID = 0;
1508
1509INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1514INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1515
1516Pass *llvm::createLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
1517 bool ForgetAllSCEV, int Threshold,
1518 int AllowPartial, int Runtime, int UpperBound,
1519 int AllowPeeling) {
1520 // TODO: It would make more sense for this function to take the optionals
1521 // directly, but that's dangerous since it would silently break out of tree
1522 // callers.
1523 return new LoopUnroll(
1524 OptLevel, OnlyWhenForced, ForgetAllSCEV,
1525 Threshold == -1 ? std::nullopt : std::optional<unsigned>(Threshold),
1526 AllowPartial == -1 ? std::nullopt : std::optional<bool>(AllowPartial),
1527 Runtime == -1 ? std::nullopt : std::optional<bool>(Runtime),
1528 UpperBound == -1 ? std::nullopt : std::optional<bool>(UpperBound),
1529 AllowPeeling == -1 ? std::nullopt : std::optional<bool>(AllowPeeling));
1530}
1531
1534 LPMUpdater &Updater) {
1535 // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
1536 // pass. Function analyses need to be preserved across loop transformations
1537 // but ORE cannot be preserved (see comment before the pass definition).
1538 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
1539 const ScalarOptions &Opts = getScalarOptions(L);
1540
1541 // Keep track of the previous loop structure so we can identify new loops
1542 // created by unrolling.
1543 Loop *ParentL = L.getParentLoop();
1544 SmallPtrSet<Loop *, 4> OldLoops;
1545 if (ParentL)
1546 OldLoops.insert_range(*ParentL);
1547 else
1548 OldLoops.insert_range(AR.LI);
1549
1550 std::string LoopName = std::string(L.getName());
1551
1552 bool Changed =
1553 tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, ORE,
1554 /*BFI*/ nullptr, /*PSI*/ nullptr,
1555 /*PreserveLCSSA*/ true, OptLevel, /*OnlyFullUnroll*/ true,
1556 OnlyWhenForced, ForgetSCEV, PrepareForLTO,
1557 /*Threshold*/ std::nullopt, /*AllowPartial*/ false,
1558 /*Runtime*/ false, /*UpperBound*/ false,
1559 /*AllowPeeling*/ true,
1560 /*AllowProfileBasedPeeling*/ false,
1561 /*FullUnrollMaxCount*/ std::nullopt) !=
1563 if (!Changed)
1564 return PreservedAnalyses::all();
1565
1566 // The parent must not be damaged by unrolling!
1567#ifndef NDEBUG
1568 if (ParentL)
1569 ParentL->verifyLoop();
1570#endif
1571
1572 // Unrolling can do several things to introduce new loops into a loop nest:
1573 // - Full unrolling clones child loops within the current loop but then
1574 // removes the current loop making all of the children appear to be new
1575 // sibling loops.
1576 //
1577 // When a new loop appears as a sibling loop after fully unrolling,
1578 // its nesting structure has fundamentally changed and we want to revisit
1579 // it to reflect that.
1580 //
1581 // When unrolling has removed the current loop, we need to tell the
1582 // infrastructure that it is gone.
1583 //
1584 // Finally, we support a debugging/testing mode where we revisit child loops
1585 // as well. These are not expected to require further optimizations as either
1586 // they or the loop they were cloned from have been directly visited already.
1587 // But the debugging mode allows us to check this assumption.
1588 bool IsCurrentLoopValid = false;
1589 SmallVector<Loop *, 4> SibLoops;
1590 if (ParentL)
1591 SibLoops.append(ParentL->begin(), ParentL->end());
1592 else
1593 SibLoops.append(AR.LI.begin(), AR.LI.end());
1594 erase_if(SibLoops, [&](Loop *SibLoop) {
1595 if (SibLoop == &L) {
1596 IsCurrentLoopValid = true;
1597 return true;
1598 }
1599
1600 // Otherwise erase the loop from the list if it was in the old loops.
1601 return OldLoops.contains(SibLoop);
1602 });
1603 Updater.addSiblingLoops(SibLoops);
1604
1605 if (!IsCurrentLoopValid) {
1606 Updater.markLoopAsDeleted(L, LoopName);
1607 } else {
1608 // We can only walk child loops if the current loop remained valid.
1609 if (Opts.unroll_revisit_child_loops) {
1610 // Walk *all* of the child loops.
1611 SmallVector<Loop *, 4> ChildLoops(L.begin(), L.end());
1612 Updater.addChildLoops(ChildLoops);
1613 }
1614 }
1615
1617}
1618
1621 auto &LI = AM.getResult<LoopAnalysis>(F);
1622 // There are no loops in the function. Return before computing other expensive
1623 // analyses.
1624 if (LI.empty())
1625 return PreservedAnalyses::all();
1626 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1627 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1628 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1629 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1632
1633 UniformityInfo *UI = TTI.hasBranchDivergence(&F)
1635 : nullptr;
1636
1637 LoopAnalysisManager *LAM = nullptr;
1638 if (auto *LAMProxy = AM.getCachedResult<LoopAnalysisManagerFunctionProxy>(F))
1639 LAM = &LAMProxy->getManager();
1640
1641 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1642 ProfileSummaryInfo *PSI =
1643 MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
1644 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
1645 &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
1646
1647 bool Changed = false;
1648
1649 // The unroller requires loops to be in simplified form, and also needs LCSSA.
1650 // Since simplification may add new inner loops, it has to run before the
1651 // legality and profitability checks. This means running the loop unroller
1652 // will simplify all loops, regardless of whether anything end up being
1653 // unrolled.
1654 for (const auto &L : LI) {
1655 Changed |= simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr,
1656 false /* PreserveLCSSA */, &TTI);
1657 Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
1658 }
1659
1660 // Add the loop nests in the reverse order of LoopInfo. See method
1661 // declaration.
1663 appendLoopsToWorklist(LI, Worklist);
1664
1665 // Cache the number of loops in each top-level nest. The gated transforms
1666 // never add loops to the worklist, so the counts stay a safe upper bound.
1667 const unsigned MaxNestLoops = getScalarOptions(F).unroll_max_nest_loops;
1668 DenseMap<const Loop *, unsigned> TopLevelNestSize;
1669 if (MaxNestLoops)
1670 for (const Loop *TopL : LI)
1671 TopLevelNestSize[TopL] = TopL->getLoopsInPreorder().size();
1672
1673 while (!Worklist.empty()) {
1674 // Because the LoopInfo stores the loops in RPO, we walk the worklist
1675 // from back to front so that we work forward across the CFG, which
1676 // for unrolling is only needed to get optimization remarks emitted in
1677 // a forward order.
1678 Loop &L = *Worklist.pop_back_val();
1679#ifndef NDEBUG
1680 Loop *ParentL = L.getParentLoop();
1681#endif
1682
1683 // Check if the profile summary indicates that the profiled application
1684 // has a huge working set size, in which case we disable peeling to avoid
1685 // bloating it further.
1686 std::optional<bool> LocalAllowPeeling = UnrollOpts.AllowPeeling;
1687 if (PSI && PSI->hasHugeWorkingSetSize())
1688 LocalAllowPeeling = false;
1689
1690 // Suppress heuristic runtime/partial unrolling and peeling for loops in a
1691 // pathologically large nest, where each such transform forces a whole-nest
1692 // SCEV invalidation (quadratic compile time). Explicit unroll pragmas still
1693 // win: gatherUnrollingPreferences applies these overrides before
1694 // computeUnrollCount re-enables unrolling for pragma-marked loops.
1695 std::optional<bool> LocalAllowRuntime = UnrollOpts.AllowRuntime;
1696 std::optional<bool> LocalAllowPartial = UnrollOpts.AllowPartial;
1697 if (MaxNestLoops) {
1698 unsigned NestSize = TopLevelNestSize.lookup(L.getOutermostLoop());
1699 if (NestSize > MaxNestLoops) {
1700 LocalAllowRuntime = false;
1701 LocalAllowPartial = false;
1702 LocalAllowPeeling = false;
1704 << "Disabling runtime/partial unroll and peeling: "
1705 "outermost nest has "
1706 << NestSize << " loops (> " << MaxNestLoops << ").\n");
1707 }
1708 }
1709
1710 std::string LoopName = std::string(L.getName());
1711 // The API here is quite complex to call and we allow to select some
1712 // flavors of unrolling during construction time (by setting UnrollOpts).
1713 LoopUnrollResult Result =
1714 tryToUnrollLoop(&L, DT, &LI, SE, TTI, AC, ORE, BFI, PSI,
1715 /*PreserveLCSSA*/ true, UnrollOpts.OptLevel,
1716 /*OnlyFullUnroll*/ false, UnrollOpts.OnlyWhenForced,
1717 UnrollOpts.ForgetSCEV, UnrollOpts.PrepareForLTO,
1718 /*Threshold*/ std::nullopt, LocalAllowPartial,
1719 LocalAllowRuntime, UnrollOpts.AllowUpperBound,
1720 LocalAllowPeeling, UnrollOpts.AllowProfileBasedPeeling,
1721 UnrollOpts.FullUnrollMaxCount, UI, &AA);
1723
1724 // The parent must not be damaged by unrolling!
1725#ifndef NDEBUG
1726 if (Result != LoopUnrollResult::Unmodified && ParentL)
1727 ParentL->verifyLoop();
1728#endif
1729
1730 // Clear any cached analysis results for L if we removed it completely.
1731 if (LAM && Result == LoopUnrollResult::FullyUnrolled)
1732 LAM->clear(L, LoopName);
1733 }
1734
1735 if (!Changed)
1736 return PreservedAnalyses::all();
1737
1739}
1740
1742 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1743 static_cast<PassInfoMixin<LoopUnrollPass> *>(this)->printPipeline(
1744 OS, MapClassName2PassName);
1745 OS << '<';
1746 if (UnrollOpts.AllowPartial != std::nullopt)
1747 OS << (*UnrollOpts.AllowPartial ? "" : "no-") << "partial;";
1748 if (UnrollOpts.AllowPeeling != std::nullopt)
1749 OS << (*UnrollOpts.AllowPeeling ? "" : "no-") << "peeling;";
1750 if (UnrollOpts.AllowRuntime != std::nullopt)
1751 OS << (*UnrollOpts.AllowRuntime ? "" : "no-") << "runtime;";
1752 if (UnrollOpts.AllowUpperBound != std::nullopt)
1753 OS << (*UnrollOpts.AllowUpperBound ? "" : "no-") << "upperbound;";
1754 if (UnrollOpts.AllowProfileBasedPeeling != std::nullopt)
1755 OS << (*UnrollOpts.AllowProfileBasedPeeling ? "" : "no-")
1756 << "profile-peeling;";
1757 if (UnrollOpts.FullUnrollMaxCount != std::nullopt)
1758 OS << "full-unroll-max=" << UnrollOpts.FullUnrollMaxCount << ';';
1759 if (UnrollOpts.PrepareForLTO)
1760 OS << "prepare-for-lto;";
1761 OS << 'O' << UnrollOpts.OptLevel;
1762 OS << '>';
1763}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
Rewrite undef for PHI
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define DEBUG_TYPE
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header defines various interfaces for pass management in LLVM.
This header provides classes for managing per-loop analyses.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
static LoopUnrollResult tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache &AC, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel, bool OnlyFullUnroll, bool OnlyWhenForced, bool ForgetAllSCEV, bool PrepareForLTO, std::optional< unsigned > ProvidedThreshold, std::optional< bool > ProvidedAllowPartial, std::optional< bool > ProvidedRuntime, std::optional< bool > ProvidedUpperBound, std::optional< bool > ProvidedAllowPeeling, std::optional< bool > ProvidedAllowProfileBasedPeeling, std::optional< unsigned > ProvidedFullUnrollMaxCount, UniformityInfo *UI=nullptr, AAResults *AA=nullptr)
static bool hasUnrollFullPragma(const Loop *L)
static bool isSCEVUniform(const SCEV *S, UniformityInfo &UI)
Returns true if the SCEV expression is uniform, i.e., all threads in a convergent execution agree on ...
static unsigned unrollCountPragmaValue(const Loop *L)
static bool hasUnrollEnablePragma(const Loop *L)
static std::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)
static std::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.
static std::optional< unsigned > shouldPragmaUnroll(const ScalarOptions &Opts, Loop *L, const UnrollPragmaInfo &PInfo, const unsigned TripMultiple, const unsigned TripCount, unsigned MaxTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP, OptimizationRemarkEmitter *ORE)
static std::optional< unsigned > shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static const unsigned NoThreshold
A magic value for use with the Threshold parameter to indicate that the loop unroll should be perform...
static unsigned shouldRuntimeUnroll(Loop *L, unsigned MaxTripCount, unsigned TripMultiple, const UnrollCostEstimator &UCE, const UnrollPragmaInfo &PInfo, const ScalarOptions &Opts, TargetTransformInfo::UnrollingPreferences &UP)
static bool hasRuntimeUnrollDisablePragma(const Loop *L)
static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost, unsigned MaxPercentThresholdBoost)
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
Machine Trace Metrics
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This file contains the declarations for metadata subclasses.
LoopAnalysisManager LAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
SI Fold Operands
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
This pass exposes codegen information to IR-level passes.
LLVM IR instance of the generic uniformity analysis.
Value * RHS
Value * LHS
A manager for alias analyses.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional Branch instruction.
This is the shared class of boolean and integer constants.
Definition Constants.h:87
This is an important base class in LLVM.
Definition Constant.h:44
A debug info location.
Definition DebugLoc.h:126
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition DenseMap.h:757
unsigned size() const
Definition DenseMap.h:717
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:827
Implements a dense probed hash-table based set.
Definition DenseSet.h:283
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition Function.h:705
bool isUniformAtDef(ConstValueRefT V) const
Whether V is uniform/non-divergent at its definition.
CostType getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void addChildLoops(ArrayRef< Loop * > NewChildLoops)
Loop passes should use this method to indicate they have added new child loops of the current loop.
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
void addSiblingLoops(ArrayRef< Loop * > NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop.
void markLoopAsDeleted(Loop &L)
Definition LoopPass.cpp:124
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:598
void verifyLoop() const
Verify loop structure.
iterator end() const
iterator begin() const
LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
iterator end() const
iterator begin() const
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
LLVM_ABI void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition LoopInfo.cpp:577
Metadata node.
Definition Metadata.h:1087
const MDOperand & getOperand(unsigned I) const
Definition Metadata.h:1443
unsigned getNumOperands() const
Return number of MDNode operands.
Definition Metadata.h:1449
Diagnostic information for optimization analysis remarks.
The optimization diagnostic interface.
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition Pass.h:97
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
bool empty() const
Determine if the PriorityWorklist is empty or not.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
This class represents an analyzed expression in the program.
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI 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.
size_type size() const
Determine the number of elements in the SetVector.
Definition SetVector.h:103
void clear()
Completely clear the SetVector.
Definition SetVector.h:273
bool empty() const
Determine if the SetVector is empty or not.
Definition SetVector.h:100
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:157
value_type pop_back_val()
Definition SetVector.h:285
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
void insert_range(Range &&R)
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:346
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Multiway switch.
Analysis pass providing the TargetTransformInfo.
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM_ABI bool hasBranchDivergence(const Function *F=nullptr) const
Return true if branch divergence exists.
TargetCostKind
The kind of cost model.
@ TCK_CodeSize
Instruction code size.
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Analysis pass which computes UniformityInfo.
Legacy analysis pass which computes a CycleInfo.
Produce an estimate of the unrolled cost of the specified loop.
Definition UnrollLoop.h:150
ConvergenceKind Convergence
Definition UnrollLoop.h:156
LLVM_ABI bool canUnroll(OptimizationRemarkEmitter *ORE=nullptr, const Loop *L=nullptr) const
Whether it is legal to unroll this loop.
LLVM_ABI uint64_t getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, unsigned Count) const
Returns loop size estimation for an unrolled loop with the given unroll count and the unrolling confi...
LLVM_ABI UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, unsigned BEInsns, bool PrepareForLTO=false, bool TripCountIsUniform=false)
uint64_t getRolledLoopSize() const
Definition UnrollLoop.h:174
void visit(Iterator Start, Iterator End)
Definition InstVisitor.h:87
LLVM Value Representation.
Definition Value.h:75
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
iterator find(const_arg_type_t< ValueT > V)
Definition DenseSet.h:175
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Abstract Attribute helper functions.
Definition Attributor.h:166
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)
Extract a Value from Metadata.
Definition Metadata.h:680
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
GenericUniformityInfo< SSAContext > UniformityInfo
LLVM_ABI Pass * createLoopUnrollPass(int OptLevel=2, bool OnlyWhenForced=false, bool ForgetAllSCEV=false, int Threshold=-1, int AllowPartial=-1, int Runtime=-1, int UpperBound=-1, int AllowPeeling=-1)
LLVM_ABI std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Return either:
LLVM_ABI unsigned computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, OptimizationRemarkEmitter *ORE, unsigned TripCount, unsigned MaxTripCount, bool MaxOrZero, unsigned TripMultiple, const UnrollCostEstimator &UCE, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP)
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
@ Runtime
Detect stack use after return if not disabled runtime with (ASAN_OPTIONS=detect_stack_use_after_retur...
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition LCSSA.cpp:469
LLVM_ABI std::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.
LLVM_ABI 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.
LLVM_ABI TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, llvm::OptimizationRemarkEmitter &ORE, int OptLevel, std::optional< unsigned > UserThreshold, std::optional< bool > UserAllowPartial, std::optional< bool > UserRuntime, std::optional< bool > UserUpperBound, std::optional< unsigned > UserFullUnrollMaxCount)
Gather the various unrolling parameters based on the defaults, compiler flags, TTI overrides and user...
LLVM_ABI char & LCSSAID
Definition LCSSA.cpp:545
LLVM_ABI void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, ArrayRef< BasicBlock * > Blocks, AAResults *AA=nullptr)
Perform some cleanup and simplifications on loops after unrolling.
const ScalarOptions & getScalarOptions(const LLVMContext &C)
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
LLVM_ABI bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, const TargetTransformInfo *TTI=nullptr)
Simplify each loop in a loop nest recursively.
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition STLExtras.h:2042
LLVM_ABI void initializeLoopUnrollPass(PassRegistry &)
LLVM_ABI TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
LLVM_ABI CallBase * getLoopConvergenceHeart(const Loop *TheLoop)
Find the convergence heart of the loop.
LLVM_ABI bool getForgetSCEVInLoopUnroll(const cl::LibraryOptionsContext &LibraryOptions)
Return -forget-scev-loop-unroll.
LLVM_ABI TransformationMode hasUnrollAndJamTransformation(const Loop *L)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)
Definition LoopPeel.cpp:749
LLVM_TEMPLATE_ABI void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget
LLVM_ABI TransformationMode hasUnrollTransformation(const Loop *L)
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition UnrollLoop.h:58
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
Definition UnrollLoop.h:65
@ Unmodified
The loop was not modified.
Definition UnrollLoop.h:60
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
Definition UnrollLoop.h:69
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
LLVM_ABI void peelLoop(Loop *L, unsigned PeelCount, bool PeelLast, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)
VMap is the value-map that maps instructions from the original loop to instructions in the last peele...
const char *const LLVMLoopUnrollFollowupAll
Definition UnrollLoop.h:45
TargetTransformInfo TTI
TransformationMode
The mode sets how eager a transformation should be applied.
Definition LoopUtils.h:292
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition LoopUtils.h:309
@ TM_Disable
The transformation should not be applied.
Definition LoopUtils.h:301
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition LoopUtils.h:298
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
LLVM_ABI MDNode * getUnrollMetadataForLoop(const Loop *L, StringRef Name)
DWARFExpression::Operation Op
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
const char *const LLVMLoopUnrollFollowupRemainder
Definition UnrollLoop.h:48
LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
const char *const LLVMLoopUnrollFollowupUnrolled
Definition UnrollLoop.h:46
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:2210
constexpr bool valueOr(BoolOrDefault X, bool Default)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI 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, AAResults *AA=nullptr)
Unroll the given loop by Count.
LLVM_ABI void reportFatalUsageError(Error Err)
Report a fatal error that does not indicate a bug in LLVM.
Definition Error.cpp:177
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition CodeMetrics.h:34
static LLVM_ABI 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).
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
bool PeelLast
Peel off the last PeelCount loop iterations.
bool PeelProfiledIterations
Allow peeling basing on profile.
unsigned PeelCount
A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...
Parameters that control the generic loop unrolling transformation.
bool UpperBound
Allow using trip count upper bound to unroll loops.
unsigned Threshold
The cost threshold for the unrolled loop.
bool Force
Apply loop unroll on any kind of loop (mainly to loops that fail runtime unrolling).
unsigned PartialOptSizeThreshold
The cost threshold for the unrolled loop when optimizing for size, like OptSizeThreshold,...
unsigned DefaultUnrollRuntimeCount
Default unroll count for loops with run-time trip count.
unsigned MaxPercentThresholdBoost
If complete unrolling will reduce the cost of the loop, we will boost the Threshold by a certain perc...
bool RuntimeUnrollMultiExit
Allow runtime unrolling multi-exit loops.
unsigned SCEVExpansionBudget
Don't allow runtime unrolling if expanding the trip count takes more than SCEVExpansionBudget.
bool AddAdditionalAccumulators
Allow unrolling to add parallel reduction phis.
unsigned MaxIterationsCountToAnalyze
Don't allow loop unrolling to simulate more than this number of iterations when checking full unroll ...
bool AllowRemainder
Allow generation of a loop remainder (extra iterations after unroll).
bool UnrollRemainder
Allow unrolling of all the iterations of the runtime loop remainder.
unsigned FullUnrollMaxCount
Set the maximum unrolling factor for full unrolling.
unsigned PartialThreshold
The cost threshold for the unrolled loop, like Threshold, but used for partial/runtime unrolling (set...
bool Runtime
Allow runtime unrolling (unrolling of loops to expand the size of the loop body even when the number ...
bool Partial
Allow partial unrolling (unrolling of loops to expand the size of the loop body, not only to eliminat...
unsigned OptSizeThreshold
The cost threshold for the unrolled loop when optimizing for size (set to UINT_MAX to disable).
bool AllowExpensiveTripCount
Allow emitting expensive instructions (such as divisions) when computing the trip count of a loop for...
unsigned MaxUpperBound
Set the maximum upper bound of trip count.
const Instruction * Heart
Definition UnrollLoop.h:79
const bool PragmaFullUnroll
Definition UnrollLoop.h:131
LLVM_ABI UnrollPragmaInfo(const Loop *L)
const unsigned PragmaCount
Definition UnrollLoop.h:132
const bool ExplicitUnroll
Definition UnrollLoop.h:135
const bool PragmaRuntimeUnrollDisable
Definition UnrollLoop.h:134
const bool UserUnrollCount
Definition UnrollLoop.h:130
const bool PragmaEnableUnroll
Definition UnrollLoop.h:133