LLVM 19.0.0git
Go to the documentation of this file.
1//===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===//
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
9// This file defines some loop unrolling utilities. It does not define any
10// actual pass or policy, but provides a single function to perform loop
11// unrolling.
18#include "llvm/ADT/DenseMap.h"
23namespace llvm {
25class AssumptionCache;
26class AAResults;
27class BasicBlock;
28class BlockFrequencyInfo;
29class DependenceInfo;
30class DominatorTree;
31class Loop;
32class LoopInfo;
33class MDNode;
34class ProfileSummaryInfo;
35class OptimizationRemarkEmitter;
36class ScalarEvolution;
37class StringRef;
38class Value;
42/// @{
43/// Metadata attribute names
44const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
46 "llvm.loop.unroll.followup_unrolled";
48 "llvm.loop.unroll.followup_remainder";
49/// @}
52 BasicBlock *ClonedBB, LoopInfo *LI,
53 NewLoopsMap &NewLoops);
55/// Represents the result of a \c UnrollLoop invocation.
56enum class LoopUnrollResult {
57 /// The loop was not modified.
60 /// The loop was partially unrolled -- we still have a loop, but with a
61 /// smaller trip count. We may also have emitted epilogue loop if the loop
62 /// had a non-constant trip count.
65 /// The loop was fully unrolled into straight-line code. We no longer have
66 /// any back-edges.
71 unsigned Count;
72 bool Force;
73 bool Runtime;
77 const Instruction *Heart = nullptr;
84 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
85 Loop **RemainderLoop = nullptr,
86 AAResults *AA = nullptr);
89 Loop *L, unsigned Count, bool AllowExpensiveTripCount,
90 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
92 const TargetTransformInfo *TTI, bool PreserveLCSSA,
93 Loop **ResultLoop = nullptr);
95LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
96 unsigned TripMultiple, bool UnrollRemainder,
101 Loop **EpilogueLoop = nullptr);
104 DependenceInfo &DI, LoopInfo &LI);
106void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
108 AssumptionCache *AC,
110 AAResults *AA = nullptr);
117 llvm::OptimizationRemarkEmitter &ORE, int OptLevel,
118 std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount,
119 std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime,
120 std::optional<bool> UserUpperBound,
121 std::optional<unsigned> UserFullUnrollMaxCount);
123/// Produce an estimate of the unrolled cost of the specified loop. This
124/// is used to a) produce a cost estimate for partial unrolling and b) to
125/// cheaply estimate cost for full unrolling when we don't want to symbolically
126/// evaluate all iterations.
128 InstructionCost LoopSize;
129 bool NotDuplicatable;
137 const SmallPtrSetImpl<const Value *> &EphValues,
138 unsigned BEInsns);
140 /// Whether it is legal to unroll this loop.
141 bool canUnroll() const;
143 uint64_t getRolledLoopSize() const { return *LoopSize.getValue(); }
145 /// Returns loop size estimation for unrolled loop, given the unrolling
146 /// configuration specified by UP.
149 unsigned CountOverwrite = 0) const;
152bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
153 DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC,
154 ScalarEvolution &SE,
155 const SmallPtrSetImpl<const Value *> &EphValues,
156 OptimizationRemarkEmitter *ORE, unsigned TripCount,
157 unsigned MaxTripCount, bool MaxOrZero,
158 unsigned TripMultiple, const UnrollCostEstimator &UCE,
159 TargetTransformInfo::UnrollingPreferences &UP,
160 TargetTransformInfo::PeelingPreferences &PP,
161 bool &UseUpperBound);
163} // end namespace llvm
This file defines the DenseMap class.
std::string Name
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
This pass exposes codegen information to IR-level passes.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
DependenceInfo - This class is the main dependence-analysis driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
std::optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
Metadata node.
Definition: Metadata.h:1067
The optimization diagnostic interface.
Analysis providing profile information.
The main scalar evolution driver.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:323
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Produce an estimate of the unrolled cost of the specified loop.
Definition: UnrollLoop.h:127
ConvergenceKind Convergence
Definition: UnrollLoop.h:133
uint64_t getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, unsigned CountOverwrite=0) const
Returns loop size estimation for unrolled loop, given the unrolling configuration specified by UP.
bool canUnroll() const
Whether it is legal to unroll this loop.
uint64_t getRolledLoopSize() const
Definition: UnrollLoop.h:143
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, DependenceInfo &DI, LoopInfo &LI)
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, AAResults *AA=nullptr)
Perform some cleanup and simplifications on loops after unrolling.
Definition: LoopUnroll.cpp:344
Definition: CodeMetrics.h:30
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:56
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
@ Unmodified
The loop was not modified.
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
bool 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 &UseUpperBound)
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:44
TargetTransformInfo TTI
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< unsigned > UserCount, 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...
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:47
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
Definition: LoopUnroll.cpp:150
const char *const LLVMLoopUnrollFollowupUnrolled
Definition: UnrollLoop.h:45
LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop=nullptr)
MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)
Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
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.
Definition: LoopUnroll.cpp:460
Parameters that control the generic loop unrolling transformation.
const Instruction * Heart
Definition: UnrollLoop.h:77