File: | llvm/lib/Transforms/Utils/LoopPeel.cpp |
Warning: | line 852, column 3 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- LoopPeel.cpp -------------------------------------------------------===// | |||
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 | // Loop Peeling Utilities. | |||
10 | //===----------------------------------------------------------------------===// | |||
11 | ||||
12 | #include "llvm/Transforms/Utils/LoopPeel.h" | |||
13 | #include "llvm/ADT/DenseMap.h" | |||
14 | #include "llvm/ADT/Optional.h" | |||
15 | #include "llvm/ADT/SmallVector.h" | |||
16 | #include "llvm/ADT/Statistic.h" | |||
17 | #include "llvm/Analysis/LoopInfo.h" | |||
18 | #include "llvm/Analysis/LoopIterator.h" | |||
19 | #include "llvm/Analysis/ScalarEvolution.h" | |||
20 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" | |||
21 | #include "llvm/Analysis/TargetTransformInfo.h" | |||
22 | #include "llvm/IR/BasicBlock.h" | |||
23 | #include "llvm/IR/Dominators.h" | |||
24 | #include "llvm/IR/Function.h" | |||
25 | #include "llvm/IR/InstrTypes.h" | |||
26 | #include "llvm/IR/Instruction.h" | |||
27 | #include "llvm/IR/Instructions.h" | |||
28 | #include "llvm/IR/LLVMContext.h" | |||
29 | #include "llvm/IR/MDBuilder.h" | |||
30 | #include "llvm/IR/Metadata.h" | |||
31 | #include "llvm/IR/PatternMatch.h" | |||
32 | #include "llvm/Support/Casting.h" | |||
33 | #include "llvm/Support/CommandLine.h" | |||
34 | #include "llvm/Support/Debug.h" | |||
35 | #include "llvm/Support/raw_ostream.h" | |||
36 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
37 | #include "llvm/Transforms/Utils/Cloning.h" | |||
38 | #include "llvm/Transforms/Utils/LoopSimplify.h" | |||
39 | #include "llvm/Transforms/Utils/LoopUtils.h" | |||
40 | #include "llvm/Transforms/Utils/UnrollLoop.h" | |||
41 | #include "llvm/Transforms/Utils/ValueMapper.h" | |||
42 | #include <algorithm> | |||
43 | #include <cassert> | |||
44 | #include <cstdint> | |||
45 | #include <limits> | |||
46 | ||||
47 | using namespace llvm; | |||
48 | using namespace llvm::PatternMatch; | |||
49 | ||||
50 | #define DEBUG_TYPE"loop-peel" "loop-peel" | |||
51 | ||||
52 | STATISTIC(NumPeeled, "Number of loops peeled")static llvm::Statistic NumPeeled = {"loop-peel", "NumPeeled", "Number of loops peeled"}; | |||
53 | ||||
54 | static cl::opt<unsigned> UnrollPeelCount( | |||
55 | "unroll-peel-count", cl::Hidden, | |||
56 | cl::desc("Set the unroll peeling count, for testing purposes")); | |||
57 | ||||
58 | static cl::opt<bool> | |||
59 | UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, | |||
60 | cl::desc("Allows loops to be peeled when the dynamic " | |||
61 | "trip count is known to be low.")); | |||
62 | ||||
63 | static cl::opt<bool> | |||
64 | UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", | |||
65 | cl::init(false), cl::Hidden, | |||
66 | cl::desc("Allows loop nests to be peeled.")); | |||
67 | ||||
68 | static cl::opt<unsigned> UnrollPeelMaxCount( | |||
69 | "unroll-peel-max-count", cl::init(7), cl::Hidden, | |||
70 | cl::desc("Max average trip count which will cause loop peeling.")); | |||
71 | ||||
72 | static cl::opt<unsigned> UnrollForcePeelCount( | |||
73 | "unroll-force-peel-count", cl::init(0), cl::Hidden, | |||
74 | cl::desc("Force a peel count regardless of profiling information.")); | |||
75 | ||||
76 | static cl::opt<bool> UnrollPeelMultiDeoptExit( | |||
77 | "unroll-peel-multi-deopt-exit", cl::init(true), cl::Hidden, | |||
78 | cl::desc("Allow peeling of loops with multiple deopt exits.")); | |||
79 | ||||
80 | static const char *PeeledCountMetaData = "llvm.loop.peeled.count"; | |||
81 | ||||
82 | // Designates that a Phi is estimated to become invariant after an "infinite" | |||
83 | // number of loop iterations (i.e. only may become an invariant if the loop is | |||
84 | // fully unrolled). | |||
85 | static const unsigned InfiniteIterationsToInvariance = | |||
86 | std::numeric_limits<unsigned>::max(); | |||
87 | ||||
88 | // Check whether we are capable of peeling this loop. | |||
89 | bool llvm::canPeel(Loop *L) { | |||
90 | // Make sure the loop is in simplified form | |||
91 | if (!L->isLoopSimplifyForm()) | |||
92 | return false; | |||
93 | ||||
94 | if (UnrollPeelMultiDeoptExit) { | |||
95 | SmallVector<BasicBlock *, 4> Exits; | |||
96 | L->getUniqueNonLatchExitBlocks(Exits); | |||
97 | ||||
98 | if (!Exits.empty()) { | |||
99 | // Latch's terminator is a conditional branch, Latch is exiting and | |||
100 | // all non Latch exits ends up with deoptimize. | |||
101 | const BasicBlock *Latch = L->getLoopLatch(); | |||
102 | const BranchInst *T = dyn_cast<BranchInst>(Latch->getTerminator()); | |||
103 | return T && T->isConditional() && L->isLoopExiting(Latch) && | |||
104 | all_of(Exits, [](const BasicBlock *BB) { | |||
105 | return BB->getTerminatingDeoptimizeCall(); | |||
106 | }); | |||
107 | } | |||
108 | } | |||
109 | ||||
110 | // Only peel loops that contain a single exit | |||
111 | if (!L->getExitingBlock() || !L->getUniqueExitBlock()) | |||
112 | return false; | |||
113 | ||||
114 | // Don't try to peel loops where the latch is not the exiting block. | |||
115 | // This can be an indication of two different things: | |||
116 | // 1) The loop is not rotated. | |||
117 | // 2) The loop contains irreducible control flow that involves the latch. | |||
118 | const BasicBlock *Latch = L->getLoopLatch(); | |||
119 | if (Latch != L->getExitingBlock()) | |||
120 | return false; | |||
121 | ||||
122 | // Peeling is only supported if the latch is a branch. | |||
123 | if (!isa<BranchInst>(Latch->getTerminator())) | |||
124 | return false; | |||
125 | ||||
126 | return true; | |||
127 | } | |||
128 | ||||
129 | // This function calculates the number of iterations after which the given Phi | |||
130 | // becomes an invariant. The pre-calculated values are memorized in the map. The | |||
131 | // function (shortcut is I) is calculated according to the following definition: | |||
132 | // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge]. | |||
133 | // If %y is a loop invariant, then I(%x) = 1. | |||
134 | // If %y is a Phi from the loop header, I(%x) = I(%y) + 1. | |||
135 | // Otherwise, I(%x) is infinite. | |||
136 | // TODO: Actually if %y is an expression that depends only on Phi %z and some | |||
137 | // loop invariants, we can estimate I(%x) = I(%z) + 1. The example | |||
138 | // looks like: | |||
139 | // %x = phi(0, %a), <-- becomes invariant starting from 3rd iteration. | |||
140 | // %y = phi(0, 5), | |||
141 | // %a = %y + 1. | |||
142 | static unsigned calculateIterationsToInvariance( | |||
143 | PHINode *Phi, Loop *L, BasicBlock *BackEdge, | |||
144 | SmallDenseMap<PHINode *, unsigned> &IterationsToInvariance) { | |||
145 | assert(Phi->getParent() == L->getHeader() &&(static_cast <bool> (Phi->getParent() == L->getHeader () && "Non-loop Phi should not be checked for turning into invariant." ) ? void (0) : __assert_fail ("Phi->getParent() == L->getHeader() && \"Non-loop Phi should not be checked for turning into invariant.\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 146, __extension__ __PRETTY_FUNCTION__)) | |||
146 | "Non-loop Phi should not be checked for turning into invariant.")(static_cast <bool> (Phi->getParent() == L->getHeader () && "Non-loop Phi should not be checked for turning into invariant." ) ? void (0) : __assert_fail ("Phi->getParent() == L->getHeader() && \"Non-loop Phi should not be checked for turning into invariant.\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 146, __extension__ __PRETTY_FUNCTION__)); | |||
147 | assert(BackEdge == L->getLoopLatch() && "Wrong latch?")(static_cast <bool> (BackEdge == L->getLoopLatch() && "Wrong latch?") ? void (0) : __assert_fail ("BackEdge == L->getLoopLatch() && \"Wrong latch?\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 147, __extension__ __PRETTY_FUNCTION__)); | |||
148 | // If we already know the answer, take it from the map. | |||
149 | auto I = IterationsToInvariance.find(Phi); | |||
150 | if (I != IterationsToInvariance.end()) | |||
151 | return I->second; | |||
152 | ||||
153 | // Otherwise we need to analyze the input from the back edge. | |||
154 | Value *Input = Phi->getIncomingValueForBlock(BackEdge); | |||
155 | // Place infinity to map to avoid infinite recursion for cycled Phis. Such | |||
156 | // cycles can never stop on an invariant. | |||
157 | IterationsToInvariance[Phi] = InfiniteIterationsToInvariance; | |||
158 | unsigned ToInvariance = InfiniteIterationsToInvariance; | |||
159 | ||||
160 | if (L->isLoopInvariant(Input)) | |||
161 | ToInvariance = 1u; | |||
162 | else if (PHINode *IncPhi = dyn_cast<PHINode>(Input)) { | |||
163 | // Only consider Phis in header block. | |||
164 | if (IncPhi->getParent() != L->getHeader()) | |||
165 | return InfiniteIterationsToInvariance; | |||
166 | // If the input becomes an invariant after X iterations, then our Phi | |||
167 | // becomes an invariant after X + 1 iterations. | |||
168 | unsigned InputToInvariance = calculateIterationsToInvariance( | |||
169 | IncPhi, L, BackEdge, IterationsToInvariance); | |||
170 | if (InputToInvariance != InfiniteIterationsToInvariance) | |||
171 | ToInvariance = InputToInvariance + 1u; | |||
172 | } | |||
173 | ||||
174 | // If we found that this Phi lies in an invariant chain, update the map. | |||
175 | if (ToInvariance != InfiniteIterationsToInvariance) | |||
176 | IterationsToInvariance[Phi] = ToInvariance; | |||
177 | return ToInvariance; | |||
178 | } | |||
179 | ||||
180 | // Return the number of iterations to peel off that make conditions in the | |||
181 | // body true/false. For example, if we peel 2 iterations off the loop below, | |||
182 | // the condition i < 2 can be evaluated at compile time. | |||
183 | // for (i = 0; i < n; i++) | |||
184 | // if (i < 2) | |||
185 | // .. | |||
186 | // else | |||
187 | // .. | |||
188 | // } | |||
189 | static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, | |||
190 | ScalarEvolution &SE) { | |||
191 | assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form")(static_cast <bool> (L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form" ) ? void (0) : __assert_fail ("L.isLoopSimplifyForm() && \"Loop needs to be in loop simplify form\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 191, __extension__ __PRETTY_FUNCTION__)); | |||
192 | unsigned DesiredPeelCount = 0; | |||
193 | ||||
194 | for (auto *BB : L.blocks()) { | |||
195 | auto *BI = dyn_cast<BranchInst>(BB->getTerminator()); | |||
196 | if (!BI || BI->isUnconditional()) | |||
197 | continue; | |||
198 | ||||
199 | // Ignore loop exit condition. | |||
200 | if (L.getLoopLatch() == BB) | |||
201 | continue; | |||
202 | ||||
203 | Value *Condition = BI->getCondition(); | |||
204 | Value *LeftVal, *RightVal; | |||
205 | CmpInst::Predicate Pred; | |||
206 | if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal)))) | |||
207 | continue; | |||
208 | ||||
209 | const SCEV *LeftSCEV = SE.getSCEV(LeftVal); | |||
210 | const SCEV *RightSCEV = SE.getSCEV(RightVal); | |||
211 | ||||
212 | // Do not consider predicates that are known to be true or false | |||
213 | // independently of the loop iteration. | |||
214 | if (SE.evaluatePredicate(Pred, LeftSCEV, RightSCEV)) | |||
215 | continue; | |||
216 | ||||
217 | // Check if we have a condition with one AddRec and one non AddRec | |||
218 | // expression. Normalize LeftSCEV to be the AddRec. | |||
219 | if (!isa<SCEVAddRecExpr>(LeftSCEV)) { | |||
220 | if (isa<SCEVAddRecExpr>(RightSCEV)) { | |||
221 | std::swap(LeftSCEV, RightSCEV); | |||
222 | Pred = ICmpInst::getSwappedPredicate(Pred); | |||
223 | } else | |||
224 | continue; | |||
225 | } | |||
226 | ||||
227 | const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV); | |||
228 | ||||
229 | // Avoid huge SCEV computations in the loop below, make sure we only | |||
230 | // consider AddRecs of the loop we are trying to peel. | |||
231 | if (!LeftAR->isAffine() || LeftAR->getLoop() != &L) | |||
232 | continue; | |||
233 | if (!(ICmpInst::isEquality(Pred) && LeftAR->hasNoSelfWrap()) && | |||
234 | !SE.getMonotonicPredicateType(LeftAR, Pred)) | |||
235 | continue; | |||
236 | ||||
237 | // Check if extending the current DesiredPeelCount lets us evaluate Pred | |||
238 | // or !Pred in the loop body statically. | |||
239 | unsigned NewPeelCount = DesiredPeelCount; | |||
240 | ||||
241 | const SCEV *IterVal = LeftAR->evaluateAtIteration( | |||
242 | SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE); | |||
243 | ||||
244 | // If the original condition is not known, get the negated predicate | |||
245 | // (which holds on the else branch) and check if it is known. This allows | |||
246 | // us to peel of iterations that make the original condition false. | |||
247 | if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV)) | |||
248 | Pred = ICmpInst::getInversePredicate(Pred); | |||
249 | ||||
250 | const SCEV *Step = LeftAR->getStepRecurrence(SE); | |||
251 | const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step); | |||
252 | auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step, | |||
253 | &NewPeelCount]() { | |||
254 | IterVal = NextIterVal; | |||
255 | NextIterVal = SE.getAddExpr(IterVal, Step); | |||
256 | NewPeelCount++; | |||
257 | }; | |||
258 | ||||
259 | auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() { | |||
260 | return NewPeelCount < MaxPeelCount; | |||
261 | }; | |||
262 | ||||
263 | while (CanPeelOneMoreIteration() && | |||
264 | SE.isKnownPredicate(Pred, IterVal, RightSCEV)) | |||
265 | PeelOneMoreIteration(); | |||
266 | ||||
267 | // With *that* peel count, does the predicate !Pred become known in the | |||
268 | // first iteration of the loop body after peeling? | |||
269 | if (!SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal, | |||
270 | RightSCEV)) | |||
271 | continue; // If not, give up. | |||
272 | ||||
273 | // However, for equality comparisons, that isn't always sufficient to | |||
274 | // eliminate the comparsion in loop body, we may need to peel one more | |||
275 | // iteration. See if that makes !Pred become unknown again. | |||
276 | if (ICmpInst::isEquality(Pred) && | |||
277 | !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal, | |||
278 | RightSCEV) && | |||
279 | !SE.isKnownPredicate(Pred, IterVal, RightSCEV) && | |||
280 | SE.isKnownPredicate(Pred, NextIterVal, RightSCEV)) { | |||
281 | if (!CanPeelOneMoreIteration()) | |||
282 | continue; // Need to peel one more iteration, but can't. Give up. | |||
283 | PeelOneMoreIteration(); // Great! | |||
284 | } | |||
285 | ||||
286 | DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount); | |||
287 | } | |||
288 | ||||
289 | return DesiredPeelCount; | |||
290 | } | |||
291 | ||||
292 | // Return the number of iterations we want to peel off. | |||
293 | void llvm::computePeelCount(Loop *L, unsigned LoopSize, | |||
294 | TargetTransformInfo::PeelingPreferences &PP, | |||
295 | unsigned &TripCount, ScalarEvolution &SE, | |||
296 | unsigned Threshold) { | |||
297 | assert(LoopSize > 0 && "Zero loop size is not allowed!")(static_cast <bool> (LoopSize > 0 && "Zero loop size is not allowed!" ) ? void (0) : __assert_fail ("LoopSize > 0 && \"Zero loop size is not allowed!\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 297, __extension__ __PRETTY_FUNCTION__)); | |||
298 | // Save the PP.PeelCount value set by the target in | |||
299 | // TTI.getPeelingPreferences or by the flag -unroll-peel-count. | |||
300 | unsigned TargetPeelCount = PP.PeelCount; | |||
301 | PP.PeelCount = 0; | |||
302 | if (!canPeel(L)) | |||
303 | return; | |||
304 | ||||
305 | // Only try to peel innermost loops by default. | |||
306 | // The constraint can be relaxed by the target in TTI.getUnrollingPreferences | |||
307 | // or by the flag -unroll-allow-loop-nests-peeling. | |||
308 | if (!PP.AllowLoopNestsPeeling && !L->isInnermost()) | |||
309 | return; | |||
310 | ||||
311 | // If the user provided a peel count, use that. | |||
312 | bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0; | |||
313 | if (UserPeelCount) { | |||
314 | LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCountdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Force-peeling first " << UnrollForcePeelCount << " iterations.\n"; } } while (false ) | |||
315 | << " iterations.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Force-peeling first " << UnrollForcePeelCount << " iterations.\n"; } } while (false ); | |||
316 | PP.PeelCount = UnrollForcePeelCount; | |||
317 | PP.PeelProfiledIterations = true; | |||
318 | return; | |||
319 | } | |||
320 | ||||
321 | // Skip peeling if it's disabled. | |||
322 | if (!PP.AllowPeeling) | |||
323 | return; | |||
324 | ||||
325 | unsigned AlreadyPeeled = 0; | |||
326 | if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData)) | |||
327 | AlreadyPeeled = *Peeled; | |||
328 | // Stop if we already peeled off the maximum number of iterations. | |||
329 | if (AlreadyPeeled >= UnrollPeelMaxCount) | |||
330 | return; | |||
331 | ||||
332 | // Here we try to get rid of Phis which become invariants after 1, 2, ..., N | |||
333 | // iterations of the loop. For this we compute the number for iterations after | |||
334 | // which every Phi is guaranteed to become an invariant, and try to peel the | |||
335 | // maximum number of iterations among these values, thus turning all those | |||
336 | // Phis into invariants. | |||
337 | // First, check that we can peel at least one iteration. | |||
338 | if (2 * LoopSize <= Threshold && UnrollPeelMaxCount > 0) { | |||
339 | // Store the pre-calculated values here. | |||
340 | SmallDenseMap<PHINode *, unsigned> IterationsToInvariance; | |||
341 | // Now go through all Phis to calculate their the number of iterations they | |||
342 | // need to become invariants. | |||
343 | // Start the max computation with the UP.PeelCount value set by the target | |||
344 | // in TTI.getUnrollingPreferences or by the flag -unroll-peel-count. | |||
345 | unsigned DesiredPeelCount = TargetPeelCount; | |||
346 | BasicBlock *BackEdge = L->getLoopLatch(); | |||
347 | assert(BackEdge && "Loop is not in simplified form?")(static_cast <bool> (BackEdge && "Loop is not in simplified form?" ) ? void (0) : __assert_fail ("BackEdge && \"Loop is not in simplified form?\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 347, __extension__ __PRETTY_FUNCTION__)); | |||
348 | for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) { | |||
349 | PHINode *Phi = cast<PHINode>(&*BI); | |||
350 | unsigned ToInvariance = calculateIterationsToInvariance( | |||
351 | Phi, L, BackEdge, IterationsToInvariance); | |||
352 | if (ToInvariance != InfiniteIterationsToInvariance) | |||
353 | DesiredPeelCount = std::max(DesiredPeelCount, ToInvariance); | |||
354 | } | |||
355 | ||||
356 | // Pay respect to limitations implied by loop size and the max peel count. | |||
357 | unsigned MaxPeelCount = UnrollPeelMaxCount; | |||
358 | MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1); | |||
359 | ||||
360 | DesiredPeelCount = std::max(DesiredPeelCount, | |||
361 | countToEliminateCompares(*L, MaxPeelCount, SE)); | |||
362 | ||||
363 | if (DesiredPeelCount > 0) { | |||
364 | DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount); | |||
365 | // Consider max peel count limitation. | |||
366 | assert(DesiredPeelCount > 0 && "Wrong loop size estimation?")(static_cast <bool> (DesiredPeelCount > 0 && "Wrong loop size estimation?") ? void (0) : __assert_fail ("DesiredPeelCount > 0 && \"Wrong loop size estimation?\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 366, __extension__ __PRETTY_FUNCTION__)); | |||
367 | if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) { | |||
368 | LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCountdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peel " << DesiredPeelCount << " iteration(s) to turn" << " some Phis into invariants.\n" ; } } while (false) | |||
369 | << " iteration(s) to turn"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peel " << DesiredPeelCount << " iteration(s) to turn" << " some Phis into invariants.\n" ; } } while (false) | |||
370 | << " some Phis into invariants.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peel " << DesiredPeelCount << " iteration(s) to turn" << " some Phis into invariants.\n" ; } } while (false); | |||
371 | PP.PeelCount = DesiredPeelCount; | |||
372 | PP.PeelProfiledIterations = false; | |||
373 | return; | |||
374 | } | |||
375 | } | |||
376 | } | |||
377 | ||||
378 | // Bail if we know the statically calculated trip count. | |||
379 | // In this case we rather prefer partial unrolling. | |||
380 | if (TripCount) | |||
381 | return; | |||
382 | ||||
383 | // Do not apply profile base peeling if it is disabled. | |||
384 | if (!PP.PeelProfiledIterations) | |||
385 | return; | |||
386 | // If we don't know the trip count, but have reason to believe the average | |||
387 | // trip count is low, peeling should be beneficial, since we will usually | |||
388 | // hit the peeled section. | |||
389 | // We only do this in the presence of profile information, since otherwise | |||
390 | // our estimates of the trip count are not reliable enough. | |||
391 | if (L->getHeader()->getParent()->hasProfileData()) { | |||
392 | Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L); | |||
393 | if (!PeelCount) | |||
394 | return; | |||
395 | ||||
396 | LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCountdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Profile-based estimated trip count is " << *PeelCount << "\n"; } } while (false) | |||
397 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Profile-based estimated trip count is " << *PeelCount << "\n"; } } while (false); | |||
398 | ||||
399 | if (*PeelCount) { | |||
400 | if ((*PeelCount + AlreadyPeeled <= UnrollPeelMaxCount) && | |||
401 | (LoopSize * (*PeelCount + 1) <= Threshold)) { | |||
402 | LLVM_DEBUG(dbgs() << "Peeling first " << *PeelCountdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peeling first " << *PeelCount << " iterations.\n"; } } while (false) | |||
403 | << " iterations.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peeling first " << *PeelCount << " iterations.\n"; } } while (false); | |||
404 | PP.PeelCount = *PeelCount; | |||
405 | return; | |||
406 | } | |||
407 | LLVM_DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Requested peel count: " << *PeelCount << "\n"; } } while (false); | |||
408 | LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Already peel count: " << AlreadyPeeled << "\n"; } } while (false); | |||
409 | LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n"; } } while (false); | |||
410 | LLVM_DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1) << "\n"; } } while (false) | |||
411 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1) << "\n"; } } while (false); | |||
412 | LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-peel")) { dbgs() << "Max peel cost: " << Threshold << "\n"; } } while (false); | |||
413 | } | |||
414 | } | |||
415 | } | |||
416 | ||||
417 | /// Update the branch weights of the latch of a peeled-off loop | |||
418 | /// iteration. | |||
419 | /// This sets the branch weights for the latch of the recently peeled off loop | |||
420 | /// iteration correctly. | |||
421 | /// Let F is a weight of the edge from latch to header. | |||
422 | /// Let E is a weight of the edge from latch to exit. | |||
423 | /// F/(F+E) is a probability to go to loop and E/(F+E) is a probability to | |||
424 | /// go to exit. | |||
425 | /// Then, Estimated TripCount = F / E. | |||
426 | /// For I-th (counting from 0) peeled off iteration we set the the weights for | |||
427 | /// the peeled latch as (TC - I, 1). It gives us reasonable distribution, | |||
428 | /// The probability to go to exit 1/(TC-I) increases. At the same time | |||
429 | /// the estimated trip count of remaining loop reduces by I. | |||
430 | /// To avoid dealing with division rounding we can just multiple both part | |||
431 | /// of weights to E and use weight as (F - I * E, E). | |||
432 | /// | |||
433 | /// \param Header The copy of the header block that belongs to next iteration. | |||
434 | /// \param LatchBR The copy of the latch branch that belongs to this iteration. | |||
435 | /// \param[in,out] FallThroughWeight The weight of the edge from latch to | |||
436 | /// header before peeling (in) and after peeled off one iteration (out). | |||
437 | static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR, | |||
438 | uint64_t ExitWeight, | |||
439 | uint64_t &FallThroughWeight) { | |||
440 | // FallThroughWeight is 0 means that there is no branch weights on original | |||
441 | // latch block or estimated trip count is zero. | |||
442 | if (!FallThroughWeight) | |||
443 | return; | |||
444 | ||||
445 | unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1); | |||
446 | MDBuilder MDB(LatchBR->getContext()); | |||
447 | MDNode *WeightNode = | |||
448 | HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThroughWeight) | |||
449 | : MDB.createBranchWeights(FallThroughWeight, ExitWeight); | |||
450 | LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode); | |||
451 | FallThroughWeight = | |||
452 | FallThroughWeight > ExitWeight ? FallThroughWeight - ExitWeight : 1; | |||
453 | } | |||
454 | ||||
455 | /// Initialize the weights. | |||
456 | /// | |||
457 | /// \param Header The header block. | |||
458 | /// \param LatchBR The latch branch. | |||
459 | /// \param[out] ExitWeight The weight of the edge from Latch to Exit. | |||
460 | /// \param[out] FallThroughWeight The weight of the edge from Latch to Header. | |||
461 | static void initBranchWeights(BasicBlock *Header, BranchInst *LatchBR, | |||
462 | uint64_t &ExitWeight, | |||
463 | uint64_t &FallThroughWeight) { | |||
464 | uint64_t TrueWeight, FalseWeight; | |||
465 | if (!LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) | |||
466 | return; | |||
467 | unsigned HeaderIdx = LatchBR->getSuccessor(0) == Header ? 0 : 1; | |||
468 | ExitWeight = HeaderIdx ? TrueWeight : FalseWeight; | |||
469 | FallThroughWeight = HeaderIdx ? FalseWeight : TrueWeight; | |||
470 | } | |||
471 | ||||
472 | /// Update the weights of original Latch block after peeling off all iterations. | |||
473 | /// | |||
474 | /// \param Header The header block. | |||
475 | /// \param LatchBR The latch branch. | |||
476 | /// \param ExitWeight The weight of the edge from Latch to Exit. | |||
477 | /// \param FallThroughWeight The weight of the edge from Latch to Header. | |||
478 | static void fixupBranchWeights(BasicBlock *Header, BranchInst *LatchBR, | |||
479 | uint64_t ExitWeight, | |||
480 | uint64_t FallThroughWeight) { | |||
481 | // FallThroughWeight is 0 means that there is no branch weights on original | |||
482 | // latch block or estimated trip count is zero. | |||
483 | if (!FallThroughWeight) | |||
484 | return; | |||
485 | ||||
486 | // Sets the branch weights on the loop exit. | |||
487 | MDBuilder MDB(LatchBR->getContext()); | |||
488 | unsigned HeaderIdx = LatchBR->getSuccessor(0) == Header ? 0 : 1; | |||
489 | MDNode *WeightNode = | |||
490 | HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThroughWeight) | |||
491 | : MDB.createBranchWeights(FallThroughWeight, ExitWeight); | |||
492 | LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode); | |||
493 | } | |||
494 | ||||
495 | /// Clones the body of the loop L, putting it between \p InsertTop and \p | |||
496 | /// InsertBot. | |||
497 | /// \param IterNumber The serial number of the iteration currently being | |||
498 | /// peeled off. | |||
499 | /// \param ExitEdges The exit edges of the original loop. | |||
500 | /// \param[out] NewBlocks A list of the blocks in the newly created clone | |||
501 | /// \param[out] VMap The value map between the loop and the new clone. | |||
502 | /// \param LoopBlocks A helper for DFS-traversal of the loop. | |||
503 | /// \param LVMap A value-map that maps instructions from the original loop to | |||
504 | /// instructions in the last peeled-off iteration. | |||
505 | static void cloneLoopBlocks( | |||
506 | Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, | |||
507 | SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges, | |||
508 | SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks, | |||
509 | ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, | |||
510 | LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes) { | |||
511 | BasicBlock *Header = L->getHeader(); | |||
512 | BasicBlock *Latch = L->getLoopLatch(); | |||
513 | BasicBlock *PreHeader = L->getLoopPreheader(); | |||
514 | ||||
515 | Function *F = Header->getParent(); | |||
516 | LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO(); | |||
517 | LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO(); | |||
518 | Loop *ParentLoop = L->getParentLoop(); | |||
519 | ||||
520 | // For each block in the original loop, create a new copy, | |||
521 | // and update the value map with the newly created values. | |||
522 | for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { | |||
523 | BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F); | |||
524 | NewBlocks.push_back(NewBB); | |||
525 | ||||
526 | // If an original block is an immediate child of the loop L, its copy | |||
527 | // is a child of a ParentLoop after peeling. If a block is a child of | |||
528 | // a nested loop, it is handled in the cloneLoop() call below. | |||
529 | if (ParentLoop && LI->getLoopFor(*BB) == L) | |||
530 | ParentLoop->addBasicBlockToLoop(NewBB, *LI); | |||
531 | ||||
532 | VMap[*BB] = NewBB; | |||
533 | ||||
534 | // If dominator tree is available, insert nodes to represent cloned blocks. | |||
535 | if (DT) { | |||
536 | if (Header == *BB) | |||
537 | DT->addNewBlock(NewBB, InsertTop); | |||
538 | else { | |||
539 | DomTreeNode *IDom = DT->getNode(*BB)->getIDom(); | |||
540 | // VMap must contain entry for IDom, as the iteration order is RPO. | |||
541 | DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()])); | |||
542 | } | |||
543 | } | |||
544 | } | |||
545 | ||||
546 | { | |||
547 | // Identify what other metadata depends on the cloned version. After | |||
548 | // cloning, replace the metadata with the corrected version for both | |||
549 | // memory instructions and noalias intrinsics. | |||
550 | std::string Ext = (Twine("Peel") + Twine(IterNumber)).str(); | |||
551 | cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks, | |||
552 | Header->getContext(), Ext); | |||
553 | } | |||
554 | ||||
555 | // Recursively create the new Loop objects for nested loops, if any, | |||
556 | // to preserve LoopInfo. | |||
557 | for (Loop *ChildLoop : *L) { | |||
558 | cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr); | |||
559 | } | |||
560 | ||||
561 | // Hook-up the control flow for the newly inserted blocks. | |||
562 | // The new header is hooked up directly to the "top", which is either | |||
563 | // the original loop preheader (for the first iteration) or the previous | |||
564 | // iteration's exiting block (for every other iteration) | |||
565 | InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header])); | |||
566 | ||||
567 | // Similarly, for the latch: | |||
568 | // The original exiting edge is still hooked up to the loop exit. | |||
569 | // The backedge now goes to the "bottom", which is either the loop's real | |||
570 | // header (for the last peeled iteration) or the copied header of the next | |||
571 | // iteration (for every other iteration) | |||
572 | BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]); | |||
573 | BranchInst *LatchBR = cast<BranchInst>(NewLatch->getTerminator()); | |||
574 | for (unsigned idx = 0, e = LatchBR->getNumSuccessors(); idx < e; ++idx) | |||
575 | if (LatchBR->getSuccessor(idx) == Header) { | |||
576 | LatchBR->setSuccessor(idx, InsertBot); | |||
577 | break; | |||
578 | } | |||
579 | if (DT) | |||
580 | DT->changeImmediateDominator(InsertBot, NewLatch); | |||
581 | ||||
582 | // The new copy of the loop body starts with a bunch of PHI nodes | |||
583 | // that pick an incoming value from either the preheader, or the previous | |||
584 | // loop iteration. Since this copy is no longer part of the loop, we | |||
585 | // resolve this statically: | |||
586 | // For the first iteration, we use the value from the preheader directly. | |||
587 | // For any other iteration, we replace the phi with the value generated by | |||
588 | // the immediately preceding clone of the loop body (which represents | |||
589 | // the previous iteration). | |||
590 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { | |||
591 | PHINode *NewPHI = cast<PHINode>(VMap[&*I]); | |||
592 | if (IterNumber == 0) { | |||
593 | VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader); | |||
594 | } else { | |||
595 | Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch); | |||
596 | Instruction *LatchInst = dyn_cast<Instruction>(LatchVal); | |||
597 | if (LatchInst && L->contains(LatchInst)) | |||
598 | VMap[&*I] = LVMap[LatchInst]; | |||
599 | else | |||
600 | VMap[&*I] = LatchVal; | |||
601 | } | |||
602 | cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI); | |||
603 | } | |||
604 | ||||
605 | // Fix up the outgoing values - we need to add a value for the iteration | |||
606 | // we've just created. Note that this must happen *after* the incoming | |||
607 | // values are adjusted, since the value going out of the latch may also be | |||
608 | // a value coming into the header. | |||
609 | for (auto Edge : ExitEdges) | |||
610 | for (PHINode &PHI : Edge.second->phis()) { | |||
611 | Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first); | |||
612 | Instruction *LatchInst = dyn_cast<Instruction>(LatchVal); | |||
613 | if (LatchInst && L->contains(LatchInst)) | |||
614 | LatchVal = VMap[LatchVal]; | |||
615 | PHI.addIncoming(LatchVal, cast<BasicBlock>(VMap[Edge.first])); | |||
616 | } | |||
617 | ||||
618 | // LastValueMap is updated with the values for the current loop | |||
619 | // which are used the next time this function is called. | |||
620 | for (auto KV : VMap) | |||
621 | LVMap[KV.first] = KV.second; | |||
622 | } | |||
623 | ||||
624 | TargetTransformInfo::PeelingPreferences llvm::gatherPeelingPreferences( | |||
625 | Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, | |||
626 | Optional<bool> UserAllowPeeling, | |||
627 | Optional<bool> UserAllowProfileBasedPeeling, bool UnrollingSpecficValues) { | |||
628 | TargetTransformInfo::PeelingPreferences PP; | |||
629 | ||||
630 | // Set the default values. | |||
631 | PP.PeelCount = 0; | |||
632 | PP.AllowPeeling = true; | |||
633 | PP.AllowLoopNestsPeeling = false; | |||
634 | PP.PeelProfiledIterations = true; | |||
635 | ||||
636 | // Get the target specifc values. | |||
637 | TTI.getPeelingPreferences(L, SE, PP); | |||
638 | ||||
639 | // User specified values using cl::opt. | |||
640 | if (UnrollingSpecficValues) { | |||
641 | if (UnrollPeelCount.getNumOccurrences() > 0) | |||
642 | PP.PeelCount = UnrollPeelCount; | |||
643 | if (UnrollAllowPeeling.getNumOccurrences() > 0) | |||
644 | PP.AllowPeeling = UnrollAllowPeeling; | |||
645 | if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0) | |||
646 | PP.AllowLoopNestsPeeling = UnrollAllowLoopNestsPeeling; | |||
647 | } | |||
648 | ||||
649 | // User specifed values provided by argument. | |||
650 | if (UserAllowPeeling.hasValue()) | |||
651 | PP.AllowPeeling = *UserAllowPeeling; | |||
652 | if (UserAllowProfileBasedPeeling.hasValue()) | |||
653 | PP.PeelProfiledIterations = *UserAllowProfileBasedPeeling; | |||
654 | ||||
655 | return PP; | |||
656 | } | |||
657 | ||||
658 | /// Peel off the first \p PeelCount iterations of loop \p L. | |||
659 | /// | |||
660 | /// Note that this does not peel them off as a single straight-line block. | |||
661 | /// Rather, each iteration is peeled off separately, and needs to check the | |||
662 | /// exit condition. | |||
663 | /// For loops that dynamically execute \p PeelCount iterations or less | |||
664 | /// this provides a benefit, since the peeled off iterations, which account | |||
665 | /// for the bulk of dynamic execution, can be further simplified by scalar | |||
666 | /// optimizations. | |||
667 | bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, | |||
668 | ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, | |||
669 | bool PreserveLCSSA) { | |||
670 | assert(PeelCount > 0 && "Attempt to peel out zero iterations?")(static_cast <bool> (PeelCount > 0 && "Attempt to peel out zero iterations?" ) ? void (0) : __assert_fail ("PeelCount > 0 && \"Attempt to peel out zero iterations?\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 670, __extension__ __PRETTY_FUNCTION__)); | |||
| ||||
671 | assert(canPeel(L) && "Attempt to peel a loop which is not peelable?")(static_cast <bool> (canPeel(L) && "Attempt to peel a loop which is not peelable?" ) ? void (0) : __assert_fail ("canPeel(L) && \"Attempt to peel a loop which is not peelable?\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 671, __extension__ __PRETTY_FUNCTION__)); | |||
672 | ||||
673 | LoopBlocksDFS LoopBlocks(L); | |||
674 | LoopBlocks.perform(LI); | |||
675 | ||||
676 | BasicBlock *Header = L->getHeader(); | |||
677 | BasicBlock *PreHeader = L->getLoopPreheader(); | |||
678 | BasicBlock *Latch = L->getLoopLatch(); | |||
679 | SmallVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitEdges; | |||
680 | L->getExitEdges(ExitEdges); | |||
681 | ||||
682 | DenseMap<BasicBlock *, BasicBlock *> ExitIDom; | |||
683 | if (DT) { | |||
684 | // We'd like to determine the idom of exit block after peeling one | |||
685 | // iteration. | |||
686 | // Let Exit is exit block. | |||
687 | // Let ExitingSet - is a set of predecessors of Exit block. They are exiting | |||
688 | // blocks. | |||
689 | // Let Latch' and ExitingSet' are copies after a peeling. | |||
690 | // We'd like to find an idom'(Exit) - idom of Exit after peeling. | |||
691 | // It is an evident that idom'(Exit) will be the nearest common dominator | |||
692 | // of ExitingSet and ExitingSet'. | |||
693 | // idom(Exit) is a nearest common dominator of ExitingSet. | |||
694 | // idom(Exit)' is a nearest common dominator of ExitingSet'. | |||
695 | // Taking into account that we have a single Latch, Latch' will dominate | |||
696 | // Header and idom(Exit). | |||
697 | // So the idom'(Exit) is nearest common dominator of idom(Exit)' and Latch'. | |||
698 | // All these basic blocks are in the same loop, so what we find is | |||
699 | // (nearest common dominator of idom(Exit) and Latch)'. | |||
700 | // In the loop below we remember nearest common dominator of idom(Exit) and | |||
701 | // Latch to update idom of Exit later. | |||
702 | assert(L->hasDedicatedExits() && "No dedicated exits?")(static_cast <bool> (L->hasDedicatedExits() && "No dedicated exits?") ? void (0) : __assert_fail ("L->hasDedicatedExits() && \"No dedicated exits?\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 702, __extension__ __PRETTY_FUNCTION__)); | |||
703 | for (auto Edge : ExitEdges) { | |||
704 | if (ExitIDom.count(Edge.second)) | |||
705 | continue; | |||
706 | BasicBlock *BB = DT->findNearestCommonDominator( | |||
707 | DT->getNode(Edge.second)->getIDom()->getBlock(), Latch); | |||
708 | assert(L->contains(BB) && "IDom is not in a loop")(static_cast <bool> (L->contains(BB) && "IDom is not in a loop" ) ? void (0) : __assert_fail ("L->contains(BB) && \"IDom is not in a loop\"" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 708, __extension__ __PRETTY_FUNCTION__)); | |||
709 | ExitIDom[Edge.second] = BB; | |||
710 | } | |||
711 | } | |||
712 | ||||
713 | Function *F = Header->getParent(); | |||
714 | ||||
715 | // Set up all the necessary basic blocks. It is convenient to split the | |||
716 | // preheader into 3 parts - two blocks to anchor the peeled copy of the loop | |||
717 | // body, and a new preheader for the "real" loop. | |||
718 | ||||
719 | // Peeling the first iteration transforms. | |||
720 | // | |||
721 | // PreHeader: | |||
722 | // ... | |||
723 | // Header: | |||
724 | // LoopBody | |||
725 | // If (cond) goto Header | |||
726 | // Exit: | |||
727 | // | |||
728 | // into | |||
729 | // | |||
730 | // InsertTop: | |||
731 | // LoopBody | |||
732 | // If (!cond) goto Exit | |||
733 | // InsertBot: | |||
734 | // NewPreHeader: | |||
735 | // ... | |||
736 | // Header: | |||
737 | // LoopBody | |||
738 | // If (cond) goto Header | |||
739 | // Exit: | |||
740 | // | |||
741 | // Each following iteration will split the current bottom anchor in two, | |||
742 | // and put the new copy of the loop body between these two blocks. That is, | |||
743 | // after peeling another iteration from the example above, we'll split | |||
744 | // InsertBot, and get: | |||
745 | // | |||
746 | // InsertTop: | |||
747 | // LoopBody | |||
748 | // If (!cond) goto Exit | |||
749 | // InsertBot: | |||
750 | // LoopBody | |||
751 | // If (!cond) goto Exit | |||
752 | // InsertBot.next: | |||
753 | // NewPreHeader: | |||
754 | // ... | |||
755 | // Header: | |||
756 | // LoopBody | |||
757 | // If (cond) goto Header | |||
758 | // Exit: | |||
759 | ||||
760 | BasicBlock *InsertTop = SplitEdge(PreHeader, Header, DT, LI); | |||
761 | BasicBlock *InsertBot = | |||
762 | SplitBlock(InsertTop, InsertTop->getTerminator(), DT, LI); | |||
763 | BasicBlock *NewPreHeader = | |||
764 | SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI); | |||
765 | ||||
766 | InsertTop->setName(Header->getName() + ".peel.begin"); | |||
767 | InsertBot->setName(Header->getName() + ".peel.next"); | |||
768 | NewPreHeader->setName(PreHeader->getName() + ".peel.newph"); | |||
769 | ||||
770 | ValueToValueMapTy LVMap; | |||
771 | ||||
772 | // If we have branch weight information, we'll want to update it for the | |||
773 | // newly created branches. | |||
774 | BranchInst *LatchBR = | |||
775 | cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator()); | |||
776 | uint64_t ExitWeight = 0, FallThroughWeight = 0; | |||
777 | initBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight); | |||
778 | ||||
779 | // Identify what noalias metadata is inside the loop: if it is inside the | |||
780 | // loop, the associated metadata must be cloned for each iteration. | |||
781 | SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes; | |||
782 | identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes); | |||
783 | ||||
784 | // For each peeled-off iteration, make a copy of the loop. | |||
785 | for (unsigned Iter = 0; Iter
| |||
786 | SmallVector<BasicBlock *, 8> NewBlocks; | |||
787 | ValueToValueMapTy VMap; | |||
788 | ||||
789 | cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks, | |||
790 | LoopBlocks, VMap, LVMap, DT, LI, | |||
791 | LoopLocalNoAliasDeclScopes); | |||
792 | ||||
793 | // Remap to use values from the current iteration instead of the | |||
794 | // previous one. | |||
795 | remapInstructionsInBlocks(NewBlocks, VMap); | |||
796 | ||||
797 | if (DT
| |||
798 | // Latches of the cloned loops dominate over the loop exit, so idom of the | |||
799 | // latter is the first cloned loop body, as original PreHeader dominates | |||
800 | // the original loop body. | |||
801 | if (Iter == 0) | |||
802 | for (auto Exit : ExitIDom) | |||
803 | DT->changeImmediateDominator(Exit.first, | |||
804 | cast<BasicBlock>(LVMap[Exit.second])); | |||
805 | #ifdef EXPENSIVE_CHECKS | |||
806 | assert(DT->verify(DominatorTree::VerificationLevel::Fast))(static_cast <bool> (DT->verify(DominatorTree::VerificationLevel ::Fast)) ? void (0) : __assert_fail ("DT->verify(DominatorTree::VerificationLevel::Fast)" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 806, __extension__ __PRETTY_FUNCTION__)); | |||
807 | #endif | |||
808 | } | |||
809 | ||||
810 | auto *LatchBRCopy = cast<BranchInst>(VMap[LatchBR]); | |||
811 | updateBranchWeights(InsertBot, LatchBRCopy, ExitWeight, FallThroughWeight); | |||
812 | // Remove Loop metadata from the latch branch instruction | |||
813 | // because it is not the Loop's latch branch anymore. | |||
814 | LatchBRCopy->setMetadata(LLVMContext::MD_loop, nullptr); | |||
815 | ||||
816 | InsertTop = InsertBot; | |||
817 | InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI); | |||
818 | InsertBot->setName(Header->getName() + ".peel.next"); | |||
819 | ||||
820 | F->getBasicBlockList().splice(InsertTop->getIterator(), | |||
821 | F->getBasicBlockList(), | |||
822 | NewBlocks[0]->getIterator(), F->end()); | |||
823 | } | |||
824 | ||||
825 | // Now adjust the phi nodes in the loop header to get their initial values | |||
826 | // from the last peeled-off iteration instead of the preheader. | |||
827 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { | |||
828 | PHINode *PHI = cast<PHINode>(I); | |||
829 | Value *NewVal = PHI->getIncomingValueForBlock(Latch); | |||
830 | Instruction *LatchInst = dyn_cast<Instruction>(NewVal); | |||
831 | if (LatchInst && L->contains(LatchInst)) | |||
832 | NewVal = LVMap[LatchInst]; | |||
833 | ||||
834 | PHI->setIncomingValueForBlock(NewPreHeader, NewVal); | |||
835 | } | |||
836 | ||||
837 | fixupBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight); | |||
838 | ||||
839 | // Update Metadata for count of peeled off iterations. | |||
840 | unsigned AlreadyPeeled = 0; | |||
841 | if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData)) | |||
842 | AlreadyPeeled = *Peeled; | |||
843 | addStringMetadataToLoop(L, PeeledCountMetaData, AlreadyPeeled + PeelCount); | |||
844 | ||||
845 | if (Loop *ParentLoop = L->getParentLoop()) | |||
846 | L = ParentLoop; | |||
847 | ||||
848 | // We modified the loop, update SE. | |||
849 | SE->forgetTopmostLoop(L); | |||
850 | ||||
851 | // Finally DomtTree must be correct. | |||
852 | assert(DT->verify(DominatorTree::VerificationLevel::Fast))(static_cast <bool> (DT->verify(DominatorTree::VerificationLevel ::Fast)) ? void (0) : __assert_fail ("DT->verify(DominatorTree::VerificationLevel::Fast)" , "/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp" , 852, __extension__ __PRETTY_FUNCTION__)); | |||
| ||||
853 | ||||
854 | // FIXME: Incrementally update loop-simplify | |||
855 | simplifyLoop(L, DT, LI, SE, AC, nullptr, PreserveLCSSA); | |||
856 | ||||
857 | NumPeeled++; | |||
858 | ||||
859 | return true; | |||
860 | } |