1 | //===- LoopConstrainer.h ----------------------------------------*- 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 | #ifndef LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H |
10 | #define LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H |
11 | |
12 | #include "llvm/Support/Casting.h" |
13 | #include "llvm/Transforms/Utils/ValueMapper.h" |
14 | #include <optional> |
15 | |
16 | namespace llvm { |
17 | |
18 | class BasicBlock; |
19 | class BranchInst; |
20 | class DominatorTree; |
21 | class IntegerType; |
22 | class Loop; |
23 | class LoopInfo; |
24 | class PHINode; |
25 | class ScalarEvolution; |
26 | class SCEV; |
27 | class Value; |
28 | |
29 | // Keeps track of the structure of a loop. This is similar to llvm::Loop, |
30 | // except that it is more lightweight and can track the state of a loop through |
31 | // changing and potentially invalid IR. This structure also formalizes the |
32 | // kinds of loops we can deal with -- ones that have a single latch that is also |
33 | // an exiting block *and* have a canonical induction variable. |
34 | struct LoopStructure { |
35 | const char *Tag = "" ; |
36 | |
37 | BasicBlock * = nullptr; |
38 | BasicBlock *Latch = nullptr; |
39 | |
40 | // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th |
41 | // successor is `LatchExit', the exit block of the loop. |
42 | BranchInst *LatchBr = nullptr; |
43 | BasicBlock *LatchExit = nullptr; |
44 | unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max(); |
45 | |
46 | // The loop represented by this instance of LoopStructure is semantically |
47 | // equivalent to: |
48 | // |
49 | // intN_ty inc = IndVarIncreasing ? 1 : -1; |
50 | // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT; |
51 | // |
52 | // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase) |
53 | // ... body ... |
54 | |
55 | Value *IndVarBase = nullptr; |
56 | Value *IndVarStart = nullptr; |
57 | Value *IndVarStep = nullptr; |
58 | Value *LoopExitAt = nullptr; |
59 | bool IndVarIncreasing = false; |
60 | bool IsSignedPredicate = true; |
61 | IntegerType *ExitCountTy = nullptr; |
62 | |
63 | LoopStructure() = default; |
64 | |
65 | template <typename M> LoopStructure map(M Map) const { |
66 | LoopStructure Result; |
67 | Result.Tag = Tag; |
68 | Result.Header = cast<BasicBlock>(Map(Header)); |
69 | Result.Latch = cast<BasicBlock>(Map(Latch)); |
70 | Result.LatchBr = cast<BranchInst>(Map(LatchBr)); |
71 | Result.LatchExit = cast<BasicBlock>(Map(LatchExit)); |
72 | Result.LatchBrExitIdx = LatchBrExitIdx; |
73 | Result.IndVarBase = Map(IndVarBase); |
74 | Result.IndVarStart = Map(IndVarStart); |
75 | Result.IndVarStep = Map(IndVarStep); |
76 | Result.LoopExitAt = Map(LoopExitAt); |
77 | Result.IndVarIncreasing = IndVarIncreasing; |
78 | Result.IsSignedPredicate = IsSignedPredicate; |
79 | Result.ExitCountTy = ExitCountTy; |
80 | return Result; |
81 | } |
82 | |
83 | static std::optional<LoopStructure> |
84 | parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&); |
85 | }; |
86 | |
87 | /// This class is used to constrain loops to run within a given iteration space. |
88 | /// The algorithm this class implements is given a Loop and a range [Begin, |
89 | /// End). The algorithm then tries to break out a "main loop" out of the loop |
90 | /// it is given in a way that the "main loop" runs with the induction variable |
91 | /// in a subset of [Begin, End). The algorithm emits appropriate pre and post |
92 | /// loops to run any remaining iterations. The pre loop runs any iterations in |
93 | /// which the induction variable is < Begin, and the post loop runs any |
94 | /// iterations in which the induction variable is >= End. |
95 | class LoopConstrainer { |
96 | public: |
97 | // Calculated subranges we restrict the iteration space of the main loop to. |
98 | // See the implementation of `calculateSubRanges' for more details on how |
99 | // these fields are computed. `LowLimit` is std::nullopt if there is no |
100 | // restriction on low end of the restricted iteration space of the main loop. |
101 | // `HighLimit` is std::nullopt if there is no restriction on high end of the |
102 | // restricted iteration space of the main loop. |
103 | |
104 | struct SubRanges { |
105 | std::optional<const SCEV *> LowLimit; |
106 | std::optional<const SCEV *> HighLimit; |
107 | }; |
108 | |
109 | private: |
110 | // The representation of a clone of the original loop we started out with. |
111 | struct ClonedLoop { |
112 | // The cloned blocks |
113 | std::vector<BasicBlock *> Blocks; |
114 | |
115 | // `Map` maps values in the clonee into values in the cloned version |
116 | ValueToValueMapTy Map; |
117 | |
118 | // An instance of `LoopStructure` for the cloned loop |
119 | LoopStructure Structure; |
120 | }; |
121 | |
122 | // Result of rewriting the range of a loop. See changeIterationSpaceEnd for |
123 | // more details on what these fields mean. |
124 | struct RewrittenRangeInfo { |
125 | BasicBlock *PseudoExit = nullptr; |
126 | BasicBlock *ExitSelector = nullptr; |
127 | std::vector<PHINode *> PHIValuesAtPseudoExit; |
128 | PHINode *IndVarEnd = nullptr; |
129 | |
130 | RewrittenRangeInfo() = default; |
131 | }; |
132 | |
133 | // Clone `OriginalLoop' and return the result in CLResult. The IR after |
134 | // running `cloneLoop' is well formed except for the PHI nodes in CLResult -- |
135 | // the PHI nodes say that there is an incoming edge from `OriginalPreheader` |
136 | // but there is no such edge. |
137 | void cloneLoop(ClonedLoop &CLResult, const char *Tag) const; |
138 | |
139 | // Create the appropriate loop structure needed to describe a cloned copy of |
140 | // `Original`. The clone is described by `VM`. |
141 | Loop *createClonedLoopStructure(Loop *Original, Loop *Parent, |
142 | ValueToValueMapTy &VM, bool IsSubloop); |
143 | |
144 | // Rewrite the iteration space of the loop denoted by (LS, Preheader). The |
145 | // iteration space of the rewritten loop ends at ExitLoopAt. The start of the |
146 | // iteration space is not changed. `ExitLoopAt' is assumed to be slt |
147 | // `OriginalHeaderCount'. |
148 | // |
149 | // If there are iterations left to execute, control is made to jump to |
150 | // `ContinuationBlock', otherwise they take the normal loop exit. The |
151 | // returned `RewrittenRangeInfo' object is populated as follows: |
152 | // |
153 | // .PseudoExit is a basic block that unconditionally branches to |
154 | // `ContinuationBlock'. |
155 | // |
156 | // .ExitSelector is a basic block that decides, on exit from the loop, |
157 | // whether to branch to the "true" exit or to `PseudoExit'. |
158 | // |
159 | // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value |
160 | // for each PHINode in the loop header on taking the pseudo exit. |
161 | // |
162 | // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate |
163 | // preheader because it is made to branch to the loop header only |
164 | // conditionally. |
165 | RewrittenRangeInfo |
166 | changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *, |
167 | Value *ExitLoopAt, |
168 | BasicBlock *ContinuationBlock) const; |
169 | |
170 | // The loop denoted by `LS' has `OldPreheader' as its preheader. This |
171 | // function creates a new preheader for `LS' and returns it. |
172 | BasicBlock *(const LoopStructure &LS, BasicBlock *, |
173 | const char *Tag) const; |
174 | |
175 | // `ContinuationBlockAndPreheader' was the continuation block for some call to |
176 | // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'. |
177 | // This function rewrites the PHI nodes in `LS.Header' to start with the |
178 | // correct value. |
179 | void rewriteIncomingValuesForPHIs( |
180 | LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader, |
181 | const LoopConstrainer::RewrittenRangeInfo &RRI) const; |
182 | |
183 | // Even though we do not preserve any passes at this time, we at least need to |
184 | // keep the parent loop structure consistent. The `LPPassManager' seems to |
185 | // verify this after running a loop pass. This function adds the list of |
186 | // blocks denoted by BBs to this loops parent loop if required. |
187 | void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs); |
188 | |
189 | // Some global state. |
190 | Function &F; |
191 | LLVMContext &Ctx; |
192 | ScalarEvolution &SE; |
193 | DominatorTree &DT; |
194 | LoopInfo &LI; |
195 | function_ref<void(Loop *, bool)> LPMAddNewLoop; |
196 | |
197 | // Information about the original loop we started out with. |
198 | Loop &OriginalLoop; |
199 | |
200 | BasicBlock * = nullptr; |
201 | |
202 | // The preheader of the main loop. This may or may not be different from |
203 | // `OriginalPreheader'. |
204 | BasicBlock *MainLoopPreheader = nullptr; |
205 | |
206 | // Type of the range we need to run the main loop in. |
207 | Type *RangeTy; |
208 | |
209 | // The structure of the main loop (see comment at the beginning of this class |
210 | // for a definition) |
211 | LoopStructure MainLoopStructure; |
212 | |
213 | SubRanges SR; |
214 | |
215 | public: |
216 | LoopConstrainer(Loop &L, LoopInfo &LI, |
217 | function_ref<void(Loop *, bool)> LPMAddNewLoop, |
218 | const LoopStructure &LS, ScalarEvolution &SE, |
219 | DominatorTree &DT, Type *T, SubRanges SR); |
220 | |
221 | // Entry point for the algorithm. Returns true on success. |
222 | bool run(); |
223 | }; |
224 | } // namespace llvm |
225 | |
226 | #endif // LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H |
227 | |