1 | //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===// |
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 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. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H |
16 | #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H |
17 | |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/Analysis/TargetTransformInfo.h" |
20 | #include "llvm/Support/InstructionCost.h" |
21 | |
22 | namespace llvm { |
23 | |
24 | class AssumptionCache; |
25 | class BasicBlock; |
26 | class BlockFrequencyInfo; |
27 | class DependenceInfo; |
28 | class DominatorTree; |
29 | class Loop; |
30 | class LoopInfo; |
31 | class MDNode; |
32 | class ProfileSummaryInfo; |
33 | class ; |
34 | class ScalarEvolution; |
35 | class StringRef; |
36 | class Value; |
37 | |
38 | using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; |
39 | |
40 | /// @{ |
41 | /// Metadata attribute names |
42 | const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all" ; |
43 | const char *const LLVMLoopUnrollFollowupUnrolled = |
44 | "llvm.loop.unroll.followup_unrolled" ; |
45 | const char *const LLVMLoopUnrollFollowupRemainder = |
46 | "llvm.loop.unroll.followup_remainder" ; |
47 | /// @} |
48 | |
49 | const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB, |
50 | BasicBlock *ClonedBB, LoopInfo *LI, |
51 | NewLoopsMap &NewLoops); |
52 | |
53 | /// Represents the result of a \c UnrollLoop invocation. |
54 | enum class LoopUnrollResult { |
55 | /// The loop was not modified. |
56 | Unmodified, |
57 | |
58 | /// The loop was partially unrolled -- we still have a loop, but with a |
59 | /// smaller trip count. We may also have emitted epilogue loop if the loop |
60 | /// had a non-constant trip count. |
61 | PartiallyUnrolled, |
62 | |
63 | /// The loop was fully unrolled into straight-line code. We no longer have |
64 | /// any back-edges. |
65 | FullyUnrolled |
66 | }; |
67 | |
68 | struct UnrollLoopOptions { |
69 | unsigned Count; |
70 | bool Force; |
71 | bool Runtime; |
72 | bool AllowExpensiveTripCount; |
73 | bool UnrollRemainder; |
74 | bool ForgetAllSCEV; |
75 | }; |
76 | |
77 | LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, |
78 | ScalarEvolution *SE, DominatorTree *DT, |
79 | AssumptionCache *AC, |
80 | const llvm::TargetTransformInfo *TTI, |
81 | OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, |
82 | Loop **RemainderLoop = nullptr); |
83 | |
84 | bool UnrollRuntimeLoopRemainder( |
85 | Loop *L, unsigned Count, bool AllowExpensiveTripCount, |
86 | bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, |
87 | LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, |
88 | const TargetTransformInfo *TTI, bool PreserveLCSSA, |
89 | Loop **ResultLoop = nullptr); |
90 | |
91 | LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, |
92 | unsigned TripMultiple, bool UnrollRemainder, |
93 | LoopInfo *LI, ScalarEvolution *SE, |
94 | DominatorTree *DT, AssumptionCache *AC, |
95 | const TargetTransformInfo *TTI, |
96 | OptimizationRemarkEmitter *ORE, |
97 | Loop **EpilogueLoop = nullptr); |
98 | |
99 | bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, |
100 | DependenceInfo &DI, LoopInfo &LI); |
101 | |
102 | void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, |
103 | ScalarEvolution *SE, DominatorTree *DT, |
104 | AssumptionCache *AC, |
105 | const TargetTransformInfo *TTI); |
106 | |
107 | MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); |
108 | |
109 | TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( |
110 | Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, |
111 | BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, |
112 | llvm::OptimizationRemarkEmitter &ORE, int OptLevel, |
113 | std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount, |
114 | std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime, |
115 | std::optional<bool> UserUpperBound, |
116 | std::optional<unsigned> UserFullUnrollMaxCount); |
117 | |
118 | /// Produce an estimate of the unrolled cost of the specified loop. This |
119 | /// is used to a) produce a cost estimate for partial unrolling and b) to |
120 | /// cheaply estimate cost for full unrolling when we don't want to symbolically |
121 | /// evaluate all iterations. |
122 | class UnrollCostEstimator { |
123 | InstructionCost LoopSize; |
124 | bool NotDuplicatable; |
125 | |
126 | public: |
127 | unsigned NumInlineCandidates; |
128 | bool Convergent; |
129 | |
130 | UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, |
131 | const SmallPtrSetImpl<const Value *> &EphValues, |
132 | unsigned BEInsns); |
133 | |
134 | /// Whether it is legal to unroll this loop. |
135 | bool canUnroll() const { return LoopSize.isValid() && !NotDuplicatable; } |
136 | |
137 | uint64_t getRolledLoopSize() const { return *LoopSize.getValue(); } |
138 | |
139 | /// Returns loop size estimation for unrolled loop, given the unrolling |
140 | /// configuration specified by UP. |
141 | uint64_t |
142 | getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, |
143 | unsigned CountOverwrite = 0) const; |
144 | }; |
145 | |
146 | bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, |
147 | DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC, |
148 | ScalarEvolution &SE, |
149 | const SmallPtrSetImpl<const Value *> &EphValues, |
150 | OptimizationRemarkEmitter *ORE, unsigned TripCount, |
151 | unsigned MaxTripCount, bool MaxOrZero, |
152 | unsigned TripMultiple, const UnrollCostEstimator &UCE, |
153 | TargetTransformInfo::UnrollingPreferences &UP, |
154 | TargetTransformInfo::PeelingPreferences &PP, |
155 | bool &UseUpperBound); |
156 | |
157 | } // end namespace llvm |
158 | |
159 | #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H |
160 | |