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/SmallVector.h" |
15 | #include "llvm/ADT/Statistic.h" |
16 | #include "llvm/Analysis/Loads.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/PatternMatch.h" |
31 | #include "llvm/IR/ProfDataUtils.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/ValueMapper.h" |
41 | #include <algorithm> |
42 | #include <cassert> |
43 | #include <cstdint> |
44 | #include <optional> |
45 | |
46 | using namespace llvm; |
47 | using namespace llvm::PatternMatch; |
48 | |
49 | #define DEBUG_TYPE "loop-peel" |
50 | |
51 | STATISTIC(NumPeeled, "Number of loops peeled" ); |
52 | |
53 | static cl::opt<unsigned> UnrollPeelCount( |
54 | "unroll-peel-count" , cl::Hidden, |
55 | cl::desc("Set the unroll peeling count, for testing purposes" )); |
56 | |
57 | static cl::opt<bool> |
58 | UnrollAllowPeeling("unroll-allow-peeling" , cl::init(Val: true), cl::Hidden, |
59 | cl::desc("Allows loops to be peeled when the dynamic " |
60 | "trip count is known to be low." )); |
61 | |
62 | static cl::opt<bool> |
63 | UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling" , |
64 | cl::init(Val: false), cl::Hidden, |
65 | cl::desc("Allows loop nests to be peeled." )); |
66 | |
67 | static cl::opt<unsigned> UnrollPeelMaxCount( |
68 | "unroll-peel-max-count" , cl::init(Val: 7), cl::Hidden, |
69 | cl::desc("Max average trip count which will cause loop peeling." )); |
70 | |
71 | static cl::opt<unsigned> UnrollForcePeelCount( |
72 | "unroll-force-peel-count" , cl::init(Val: 0), cl::Hidden, |
73 | cl::desc("Force a peel count regardless of profiling information." )); |
74 | |
75 | static cl::opt<bool> DisableAdvancedPeeling( |
76 | "disable-advanced-peeling" , cl::init(Val: false), cl::Hidden, |
77 | cl::desc( |
78 | "Disable advance peeling. Issues for convergent targets (D134803)." )); |
79 | |
80 | static const char *PeeledCountMetaData = "llvm.loop.peeled.count" ; |
81 | |
82 | // Check whether we are capable of peeling this loop. |
83 | bool llvm::canPeel(const Loop *L) { |
84 | // Make sure the loop is in simplified form |
85 | if (!L->isLoopSimplifyForm()) |
86 | return false; |
87 | if (!DisableAdvancedPeeling) |
88 | return true; |
89 | |
90 | SmallVector<BasicBlock *, 4> Exits; |
91 | L->getUniqueNonLatchExitBlocks(ExitBlocks&: Exits); |
92 | // The latch must either be the only exiting block or all non-latch exit |
93 | // blocks have either a deopt or unreachable terminator or compose a chain of |
94 | // blocks where the last one is either deopt or unreachable terminated. Both |
95 | // deopt and unreachable terminators are a strong indication they are not |
96 | // taken. Note that this is a profitability check, not a legality check. Also |
97 | // note that LoopPeeling currently can only update the branch weights of latch |
98 | // blocks and branch weights to blocks with deopt or unreachable do not need |
99 | // updating. |
100 | return llvm::all_of(Range&: Exits, P: IsBlockFollowedByDeoptOrUnreachable); |
101 | } |
102 | |
103 | namespace { |
104 | |
105 | // As a loop is peeled, it may be the case that Phi nodes become |
106 | // loop-invariant (ie, known because there is only one choice). |
107 | // For example, consider the following function: |
108 | // void g(int); |
109 | // void binary() { |
110 | // int x = 0; |
111 | // int y = 0; |
112 | // int a = 0; |
113 | // for(int i = 0; i <100000; ++i) { |
114 | // g(x); |
115 | // x = y; |
116 | // g(a); |
117 | // y = a + 1; |
118 | // a = 5; |
119 | // } |
120 | // } |
121 | // Peeling 3 iterations is beneficial because the values for x, y and a |
122 | // become known. The IR for this loop looks something like the following: |
123 | // |
124 | // %i = phi i32 [ 0, %entry ], [ %inc, %if.end ] |
125 | // %a = phi i32 [ 0, %entry ], [ 5, %if.end ] |
126 | // %y = phi i32 [ 0, %entry ], [ %add, %if.end ] |
127 | // %x = phi i32 [ 0, %entry ], [ %y, %if.end ] |
128 | // ... |
129 | // tail call void @_Z1gi(i32 signext %x) |
130 | // tail call void @_Z1gi(i32 signext %a) |
131 | // %add = add nuw nsw i32 %a, 1 |
132 | // %inc = add nuw nsw i32 %i, 1 |
133 | // %exitcond = icmp eq i32 %inc, 100000 |
134 | // br i1 %exitcond, label %for.cond.cleanup, label %for.body |
135 | // |
136 | // The arguments for the calls to g will become known after 3 iterations |
137 | // of the loop, because the phi nodes values become known after 3 iterations |
138 | // of the loop (ie, they are known on the 4th iteration, so peel 3 iterations). |
139 | // The first iteration has g(0), g(0); the second has g(0), g(5); the |
140 | // third has g(1), g(5) and the fourth (and all subsequent) have g(6), g(5). |
141 | // Now consider the phi nodes: |
142 | // %a is a phi with constants so it is determined after iteration 1. |
143 | // %y is a phi based on a constant and %a so it is determined on |
144 | // the iteration after %a is determined, so iteration 2. |
145 | // %x is a phi based on a constant and %y so it is determined on |
146 | // the iteration after %y, so iteration 3. |
147 | // %i is based on itself (and is an induction variable) so it is |
148 | // never determined. |
149 | // This means that peeling off 3 iterations will result in being able to |
150 | // remove the phi nodes for %a, %y, and %x. The arguments for the |
151 | // corresponding calls to g are determined and the code for computing |
152 | // x, y, and a can be removed. |
153 | // |
154 | // The PhiAnalyzer class calculates how many times a loop should be |
155 | // peeled based on the above analysis of the phi nodes in the loop while |
156 | // respecting the maximum specified. |
157 | class PhiAnalyzer { |
158 | public: |
159 | PhiAnalyzer(const Loop &L, unsigned MaxIterations); |
160 | |
161 | // Calculate the sufficient minimum number of iterations of the loop to peel |
162 | // such that phi instructions become determined (subject to allowable limits) |
163 | std::optional<unsigned> calculateIterationsToPeel(); |
164 | |
165 | protected: |
166 | using PeelCounter = std::optional<unsigned>; |
167 | const PeelCounter Unknown = std::nullopt; |
168 | |
169 | // Add 1 respecting Unknown and return Unknown if result over MaxIterations |
170 | PeelCounter addOne(PeelCounter PC) const { |
171 | if (PC == Unknown) |
172 | return Unknown; |
173 | return (*PC + 1 <= MaxIterations) ? PeelCounter{*PC + 1} : Unknown; |
174 | } |
175 | |
176 | // Calculate the number of iterations after which the given value |
177 | // becomes an invariant. |
178 | PeelCounter calculate(const Value &); |
179 | |
180 | const Loop &L; |
181 | const unsigned MaxIterations; |
182 | |
183 | // Map of Values to number of iterations to invariance |
184 | SmallDenseMap<const Value *, PeelCounter> IterationsToInvariance; |
185 | }; |
186 | |
187 | PhiAnalyzer::PhiAnalyzer(const Loop &L, unsigned MaxIterations) |
188 | : L(L), MaxIterations(MaxIterations) { |
189 | assert(canPeel(&L) && "loop is not suitable for peeling" ); |
190 | assert(MaxIterations > 0 && "no peeling is allowed?" ); |
191 | } |
192 | |
193 | // This function calculates the number of iterations after which the value |
194 | // becomes an invariant. The pre-calculated values are memorized in a map. |
195 | // N.B. This number will be Unknown or <= MaxIterations. |
196 | // The function is calculated according to the following definition: |
197 | // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge]. |
198 | // F(%x) = G(%y) + 1 (N.B. [MaxIterations | Unknown] + 1 => Unknown) |
199 | // G(%y) = 0 if %y is a loop invariant |
200 | // G(%y) = G(%BackEdgeValue) if %y is a phi in the header block |
201 | // G(%y) = TODO: if %y is an expression based on phis and loop invariants |
202 | // The example looks like: |
203 | // %x = phi(0, %a) <-- becomes invariant starting from 3rd iteration. |
204 | // %y = phi(0, 5) |
205 | // %a = %y + 1 |
206 | // G(%y) = Unknown otherwise (including phi not in header block) |
207 | PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(const Value &V) { |
208 | // If we already know the answer, take it from the map. |
209 | auto I = IterationsToInvariance.find(Val: &V); |
210 | if (I != IterationsToInvariance.end()) |
211 | return I->second; |
212 | |
213 | // Place Unknown to map to avoid infinite recursion. Such |
214 | // cycles can never stop on an invariant. |
215 | IterationsToInvariance[&V] = Unknown; |
216 | |
217 | if (L.isLoopInvariant(V: &V)) |
218 | // Loop invariant so known at start. |
219 | return (IterationsToInvariance[&V] = 0); |
220 | if (const PHINode *Phi = dyn_cast<PHINode>(Val: &V)) { |
221 | if (Phi->getParent() != L.getHeader()) { |
222 | // Phi is not in header block so Unknown. |
223 | assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved" ); |
224 | return Unknown; |
225 | } |
226 | // We need to analyze the input from the back edge and add 1. |
227 | Value *Input = Phi->getIncomingValueForBlock(BB: L.getLoopLatch()); |
228 | PeelCounter Iterations = calculate(V: *Input); |
229 | assert(IterationsToInvariance[Input] == Iterations && |
230 | "unexpected value saved" ); |
231 | return (IterationsToInvariance[Phi] = addOne(PC: Iterations)); |
232 | } |
233 | if (const Instruction *I = dyn_cast<Instruction>(Val: &V)) { |
234 | if (isa<CmpInst>(Val: I) || I->isBinaryOp()) { |
235 | // Binary instructions get the max of the operands. |
236 | PeelCounter LHS = calculate(V: *I->getOperand(i: 0)); |
237 | if (LHS == Unknown) |
238 | return Unknown; |
239 | PeelCounter RHS = calculate(V: *I->getOperand(i: 1)); |
240 | if (RHS == Unknown) |
241 | return Unknown; |
242 | return (IterationsToInvariance[I] = {std::max(a: *LHS, b: *RHS)}); |
243 | } |
244 | if (I->isCast()) |
245 | // Cast instructions get the value of the operand. |
246 | return (IterationsToInvariance[I] = calculate(V: *I->getOperand(i: 0))); |
247 | } |
248 | // TODO: handle more expressions |
249 | |
250 | // Everything else is Unknown. |
251 | assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved" ); |
252 | return Unknown; |
253 | } |
254 | |
255 | std::optional<unsigned> PhiAnalyzer::calculateIterationsToPeel() { |
256 | unsigned Iterations = 0; |
257 | for (auto &PHI : L.getHeader()->phis()) { |
258 | PeelCounter ToInvariance = calculate(V: PHI); |
259 | if (ToInvariance != Unknown) { |
260 | assert(*ToInvariance <= MaxIterations && "bad result in phi analysis" ); |
261 | Iterations = std::max(a: Iterations, b: *ToInvariance); |
262 | if (Iterations == MaxIterations) |
263 | break; |
264 | } |
265 | } |
266 | assert((Iterations <= MaxIterations) && "bad result in phi analysis" ); |
267 | return Iterations ? std::optional<unsigned>(Iterations) : std::nullopt; |
268 | } |
269 | |
270 | } // unnamed namespace |
271 | |
272 | // Try to find any invariant memory reads that will become dereferenceable in |
273 | // the remainder loop after peeling. The load must also be used (transitively) |
274 | // by an exit condition. Returns the number of iterations to peel off (at the |
275 | // moment either 0 or 1). |
276 | static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, |
277 | DominatorTree &DT, |
278 | AssumptionCache *AC) { |
279 | // Skip loops with a single exiting block, because there should be no benefit |
280 | // for the heuristic below. |
281 | if (L.getExitingBlock()) |
282 | return 0; |
283 | |
284 | // All non-latch exit blocks must have an UnreachableInst terminator. |
285 | // Otherwise the heuristic below may not be profitable. |
286 | SmallVector<BasicBlock *, 4> Exits; |
287 | L.getUniqueNonLatchExitBlocks(ExitBlocks&: Exits); |
288 | if (any_of(Range&: Exits, P: [](const BasicBlock *BB) { |
289 | return !isa<UnreachableInst>(Val: BB->getTerminator()); |
290 | })) |
291 | return 0; |
292 | |
293 | // Now look for invariant loads that dominate the latch and are not known to |
294 | // be dereferenceable. If there are such loads and no writes, they will become |
295 | // dereferenceable in the loop if the first iteration is peeled off. Also |
296 | // collect the set of instructions controlled by such loads. Only peel if an |
297 | // exit condition uses (transitively) such a load. |
298 | BasicBlock * = L.getHeader(); |
299 | BasicBlock *Latch = L.getLoopLatch(); |
300 | SmallPtrSet<Value *, 8> LoadUsers; |
301 | const DataLayout &DL = L.getHeader()->getModule()->getDataLayout(); |
302 | for (BasicBlock *BB : L.blocks()) { |
303 | for (Instruction &I : *BB) { |
304 | if (I.mayWriteToMemory()) |
305 | return 0; |
306 | |
307 | auto Iter = LoadUsers.find(Ptr: &I); |
308 | if (Iter != LoadUsers.end()) { |
309 | for (Value *U : I.users()) |
310 | LoadUsers.insert(Ptr: U); |
311 | } |
312 | // Do not look for reads in the header; they can already be hoisted |
313 | // without peeling. |
314 | if (BB == Header) |
315 | continue; |
316 | if (auto *LI = dyn_cast<LoadInst>(Val: &I)) { |
317 | Value *Ptr = LI->getPointerOperand(); |
318 | if (DT.dominates(A: BB, B: Latch) && L.isLoopInvariant(V: Ptr) && |
319 | !isDereferenceablePointer(V: Ptr, Ty: LI->getType(), DL, CtxI: LI, AC, DT: &DT)) |
320 | for (Value *U : I.users()) |
321 | LoadUsers.insert(Ptr: U); |
322 | } |
323 | } |
324 | } |
325 | SmallVector<BasicBlock *> ExitingBlocks; |
326 | L.getExitingBlocks(ExitingBlocks); |
327 | if (any_of(Range&: ExitingBlocks, P: [&LoadUsers](BasicBlock *Exiting) { |
328 | return LoadUsers.contains(Ptr: Exiting->getTerminator()); |
329 | })) |
330 | return 1; |
331 | return 0; |
332 | } |
333 | |
334 | // Return the number of iterations to peel off that make conditions in the |
335 | // body true/false. For example, if we peel 2 iterations off the loop below, |
336 | // the condition i < 2 can be evaluated at compile time. |
337 | // for (i = 0; i < n; i++) |
338 | // if (i < 2) |
339 | // .. |
340 | // else |
341 | // .. |
342 | // } |
343 | static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, |
344 | ScalarEvolution &SE) { |
345 | assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form" ); |
346 | unsigned DesiredPeelCount = 0; |
347 | |
348 | // Do not peel the entire loop. |
349 | const SCEV *BE = SE.getConstantMaxBackedgeTakenCount(L: &L); |
350 | if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Val: BE)) |
351 | MaxPeelCount = |
352 | std::min(a: (unsigned)SC->getAPInt().getLimitedValue() - 1, b: MaxPeelCount); |
353 | |
354 | const unsigned MaxDepth = 4; |
355 | std::function<void(Value *, unsigned)> ComputePeelCount = |
356 | [&](Value *Condition, unsigned Depth) -> void { |
357 | if (!Condition->getType()->isIntegerTy() || Depth >= MaxDepth) |
358 | return; |
359 | |
360 | Value *LeftVal, *RightVal; |
361 | if (match(V: Condition, P: m_And(L: m_Value(V&: LeftVal), R: m_Value(V&: RightVal))) || |
362 | match(V: Condition, P: m_Or(L: m_Value(V&: LeftVal), R: m_Value(V&: RightVal)))) { |
363 | ComputePeelCount(LeftVal, Depth + 1); |
364 | ComputePeelCount(RightVal, Depth + 1); |
365 | return; |
366 | } |
367 | |
368 | CmpInst::Predicate Pred; |
369 | if (!match(V: Condition, P: m_ICmp(Pred, L: m_Value(V&: LeftVal), R: m_Value(V&: RightVal)))) |
370 | return; |
371 | |
372 | const SCEV *LeftSCEV = SE.getSCEV(V: LeftVal); |
373 | const SCEV *RightSCEV = SE.getSCEV(V: RightVal); |
374 | |
375 | // Do not consider predicates that are known to be true or false |
376 | // independently of the loop iteration. |
377 | if (SE.evaluatePredicate(Pred, LHS: LeftSCEV, RHS: RightSCEV)) |
378 | return; |
379 | |
380 | // Check if we have a condition with one AddRec and one non AddRec |
381 | // expression. Normalize LeftSCEV to be the AddRec. |
382 | if (!isa<SCEVAddRecExpr>(Val: LeftSCEV)) { |
383 | if (isa<SCEVAddRecExpr>(Val: RightSCEV)) { |
384 | std::swap(a&: LeftSCEV, b&: RightSCEV); |
385 | Pred = ICmpInst::getSwappedPredicate(pred: Pred); |
386 | } else |
387 | return; |
388 | } |
389 | |
390 | const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(Val: LeftSCEV); |
391 | |
392 | // Avoid huge SCEV computations in the loop below, make sure we only |
393 | // consider AddRecs of the loop we are trying to peel. |
394 | if (!LeftAR->isAffine() || LeftAR->getLoop() != &L) |
395 | return; |
396 | if (!(ICmpInst::isEquality(P: Pred) && LeftAR->hasNoSelfWrap()) && |
397 | !SE.getMonotonicPredicateType(LHS: LeftAR, Pred)) |
398 | return; |
399 | |
400 | // Check if extending the current DesiredPeelCount lets us evaluate Pred |
401 | // or !Pred in the loop body statically. |
402 | unsigned NewPeelCount = DesiredPeelCount; |
403 | |
404 | const SCEV *IterVal = LeftAR->evaluateAtIteration( |
405 | It: SE.getConstant(Ty: LeftSCEV->getType(), V: NewPeelCount), SE); |
406 | |
407 | // If the original condition is not known, get the negated predicate |
408 | // (which holds on the else branch) and check if it is known. This allows |
409 | // us to peel of iterations that make the original condition false. |
410 | if (!SE.isKnownPredicate(Pred, LHS: IterVal, RHS: RightSCEV)) |
411 | Pred = ICmpInst::getInversePredicate(pred: Pred); |
412 | |
413 | const SCEV *Step = LeftAR->getStepRecurrence(SE); |
414 | const SCEV *NextIterVal = SE.getAddExpr(LHS: IterVal, RHS: Step); |
415 | auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step, |
416 | &NewPeelCount]() { |
417 | IterVal = NextIterVal; |
418 | NextIterVal = SE.getAddExpr(LHS: IterVal, RHS: Step); |
419 | NewPeelCount++; |
420 | }; |
421 | |
422 | auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() { |
423 | return NewPeelCount < MaxPeelCount; |
424 | }; |
425 | |
426 | while (CanPeelOneMoreIteration() && |
427 | SE.isKnownPredicate(Pred, LHS: IterVal, RHS: RightSCEV)) |
428 | PeelOneMoreIteration(); |
429 | |
430 | // With *that* peel count, does the predicate !Pred become known in the |
431 | // first iteration of the loop body after peeling? |
432 | if (!SE.isKnownPredicate(Pred: ICmpInst::getInversePredicate(pred: Pred), LHS: IterVal, |
433 | RHS: RightSCEV)) |
434 | return; // If not, give up. |
435 | |
436 | // However, for equality comparisons, that isn't always sufficient to |
437 | // eliminate the comparsion in loop body, we may need to peel one more |
438 | // iteration. See if that makes !Pred become unknown again. |
439 | if (ICmpInst::isEquality(P: Pred) && |
440 | !SE.isKnownPredicate(Pred: ICmpInst::getInversePredicate(pred: Pred), LHS: NextIterVal, |
441 | RHS: RightSCEV) && |
442 | !SE.isKnownPredicate(Pred, LHS: IterVal, RHS: RightSCEV) && |
443 | SE.isKnownPredicate(Pred, LHS: NextIterVal, RHS: RightSCEV)) { |
444 | if (!CanPeelOneMoreIteration()) |
445 | return; // Need to peel one more iteration, but can't. Give up. |
446 | PeelOneMoreIteration(); // Great! |
447 | } |
448 | |
449 | DesiredPeelCount = std::max(a: DesiredPeelCount, b: NewPeelCount); |
450 | }; |
451 | |
452 | for (BasicBlock *BB : L.blocks()) { |
453 | for (Instruction &I : *BB) { |
454 | if (SelectInst *SI = dyn_cast<SelectInst>(Val: &I)) |
455 | ComputePeelCount(SI->getCondition(), 0); |
456 | } |
457 | |
458 | auto *BI = dyn_cast<BranchInst>(Val: BB->getTerminator()); |
459 | if (!BI || BI->isUnconditional()) |
460 | continue; |
461 | |
462 | // Ignore loop exit condition. |
463 | if (L.getLoopLatch() == BB) |
464 | continue; |
465 | |
466 | ComputePeelCount(BI->getCondition(), 0); |
467 | } |
468 | |
469 | return DesiredPeelCount; |
470 | } |
471 | |
472 | /// This "heuristic" exactly matches implicit behavior which used to exist |
473 | /// inside getLoopEstimatedTripCount. It was added here to keep an |
474 | /// improvement inside that API from causing peeling to become more aggressive. |
475 | /// This should probably be removed. |
476 | static bool violatesLegacyMultiExitLoopCheck(Loop *L) { |
477 | BasicBlock *Latch = L->getLoopLatch(); |
478 | if (!Latch) |
479 | return true; |
480 | |
481 | BranchInst *LatchBR = dyn_cast<BranchInst>(Val: Latch->getTerminator()); |
482 | if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(BB: Latch)) |
483 | return true; |
484 | |
485 | assert((LatchBR->getSuccessor(0) == L->getHeader() || |
486 | LatchBR->getSuccessor(1) == L->getHeader()) && |
487 | "At least one edge out of the latch must go to the header" ); |
488 | |
489 | SmallVector<BasicBlock *, 4> ExitBlocks; |
490 | L->getUniqueNonLatchExitBlocks(ExitBlocks); |
491 | return any_of(Range&: ExitBlocks, P: [](const BasicBlock *EB) { |
492 | return !EB->getTerminatingDeoptimizeCall(); |
493 | }); |
494 | } |
495 | |
496 | |
497 | // Return the number of iterations we want to peel off. |
498 | void llvm::computePeelCount(Loop *L, unsigned LoopSize, |
499 | TargetTransformInfo::PeelingPreferences &PP, |
500 | unsigned TripCount, DominatorTree &DT, |
501 | ScalarEvolution &SE, AssumptionCache *AC, |
502 | unsigned Threshold) { |
503 | assert(LoopSize > 0 && "Zero loop size is not allowed!" ); |
504 | // Save the PP.PeelCount value set by the target in |
505 | // TTI.getPeelingPreferences or by the flag -unroll-peel-count. |
506 | unsigned TargetPeelCount = PP.PeelCount; |
507 | PP.PeelCount = 0; |
508 | if (!canPeel(L)) |
509 | return; |
510 | |
511 | // Only try to peel innermost loops by default. |
512 | // The constraint can be relaxed by the target in TTI.getPeelingPreferences |
513 | // or by the flag -unroll-allow-loop-nests-peeling. |
514 | if (!PP.AllowLoopNestsPeeling && !L->isInnermost()) |
515 | return; |
516 | |
517 | // If the user provided a peel count, use that. |
518 | bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0; |
519 | if (UserPeelCount) { |
520 | LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount |
521 | << " iterations.\n" ); |
522 | PP.PeelCount = UnrollForcePeelCount; |
523 | PP.PeelProfiledIterations = true; |
524 | return; |
525 | } |
526 | |
527 | // Skip peeling if it's disabled. |
528 | if (!PP.AllowPeeling) |
529 | return; |
530 | |
531 | // Check that we can peel at least one iteration. |
532 | if (2 * LoopSize > Threshold) |
533 | return; |
534 | |
535 | unsigned AlreadyPeeled = 0; |
536 | if (auto Peeled = getOptionalIntLoopAttribute(TheLoop: L, Name: PeeledCountMetaData)) |
537 | AlreadyPeeled = *Peeled; |
538 | // Stop if we already peeled off the maximum number of iterations. |
539 | if (AlreadyPeeled >= UnrollPeelMaxCount) |
540 | return; |
541 | |
542 | // Pay respect to limitations implied by loop size and the max peel count. |
543 | unsigned MaxPeelCount = UnrollPeelMaxCount; |
544 | MaxPeelCount = std::min(a: MaxPeelCount, b: Threshold / LoopSize - 1); |
545 | |
546 | // Start the max computation with the PP.PeelCount value set by the target |
547 | // in TTI.getPeelingPreferences or by the flag -unroll-peel-count. |
548 | unsigned DesiredPeelCount = TargetPeelCount; |
549 | |
550 | // Here we try to get rid of Phis which become invariants after 1, 2, ..., N |
551 | // iterations of the loop. For this we compute the number for iterations after |
552 | // which every Phi is guaranteed to become an invariant, and try to peel the |
553 | // maximum number of iterations among these values, thus turning all those |
554 | // Phis into invariants. |
555 | if (MaxPeelCount > DesiredPeelCount) { |
556 | // Check how many iterations are useful for resolving Phis |
557 | auto NumPeels = PhiAnalyzer(*L, MaxPeelCount).calculateIterationsToPeel(); |
558 | if (NumPeels) |
559 | DesiredPeelCount = std::max(a: DesiredPeelCount, b: *NumPeels); |
560 | } |
561 | |
562 | DesiredPeelCount = std::max(a: DesiredPeelCount, |
563 | b: countToEliminateCompares(L&: *L, MaxPeelCount, SE)); |
564 | |
565 | if (DesiredPeelCount == 0) |
566 | DesiredPeelCount = peelToTurnInvariantLoadsDerefencebale(L&: *L, DT, AC); |
567 | |
568 | if (DesiredPeelCount > 0) { |
569 | DesiredPeelCount = std::min(a: DesiredPeelCount, b: MaxPeelCount); |
570 | // Consider max peel count limitation. |
571 | assert(DesiredPeelCount > 0 && "Wrong loop size estimation?" ); |
572 | if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) { |
573 | LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount |
574 | << " iteration(s) to turn" |
575 | << " some Phis into invariants.\n" ); |
576 | PP.PeelCount = DesiredPeelCount; |
577 | PP.PeelProfiledIterations = false; |
578 | return; |
579 | } |
580 | } |
581 | |
582 | // Bail if we know the statically calculated trip count. |
583 | // In this case we rather prefer partial unrolling. |
584 | if (TripCount) |
585 | return; |
586 | |
587 | // Do not apply profile base peeling if it is disabled. |
588 | if (!PP.PeelProfiledIterations) |
589 | return; |
590 | // If we don't know the trip count, but have reason to believe the average |
591 | // trip count is low, peeling should be beneficial, since we will usually |
592 | // hit the peeled section. |
593 | // We only do this in the presence of profile information, since otherwise |
594 | // our estimates of the trip count are not reliable enough. |
595 | if (L->getHeader()->getParent()->hasProfileData()) { |
596 | if (violatesLegacyMultiExitLoopCheck(L)) |
597 | return; |
598 | std::optional<unsigned> EstimatedTripCount = getLoopEstimatedTripCount(L); |
599 | if (!EstimatedTripCount) |
600 | return; |
601 | |
602 | LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " |
603 | << *EstimatedTripCount << "\n" ); |
604 | |
605 | if (*EstimatedTripCount) { |
606 | if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) { |
607 | unsigned PeelCount = *EstimatedTripCount; |
608 | LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n" ); |
609 | PP.PeelCount = PeelCount; |
610 | return; |
611 | } |
612 | LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n" ); |
613 | LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n" ); |
614 | LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n" ); |
615 | LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n" ); |
616 | LLVM_DEBUG(dbgs() << "Max peel count by cost: " |
617 | << (Threshold / LoopSize - 1) << "\n" ); |
618 | } |
619 | } |
620 | } |
621 | |
622 | struct WeightInfo { |
623 | // Weights for current iteration. |
624 | SmallVector<uint32_t> Weights; |
625 | // Weights to subtract after each iteration. |
626 | const SmallVector<uint32_t> SubWeights; |
627 | }; |
628 | |
629 | /// Update the branch weights of an exiting block of a peeled-off loop |
630 | /// iteration. |
631 | /// Let F is a weight of the edge to continue (fallthrough) into the loop. |
632 | /// Let E is a weight of the edge to an exit. |
633 | /// F/(F+E) is a probability to go to loop and E/(F+E) is a probability to |
634 | /// go to exit. |
635 | /// Then, Estimated ExitCount = F / E. |
636 | /// For I-th (counting from 0) peeled off iteration we set the weights for |
637 | /// the peeled exit as (EC - I, 1). It gives us reasonable distribution, |
638 | /// The probability to go to exit 1/(EC-I) increases. At the same time |
639 | /// the estimated exit count in the remainder loop reduces by I. |
640 | /// To avoid dealing with division rounding we can just multiple both part |
641 | /// of weights to E and use weight as (F - I * E, E). |
642 | static void updateBranchWeights(Instruction *Term, WeightInfo &Info) { |
643 | setBranchWeights(I&: *Term, Weights: Info.Weights); |
644 | for (auto [Idx, SubWeight] : enumerate(First: Info.SubWeights)) |
645 | if (SubWeight != 0) |
646 | // Don't set the probability of taking the edge from latch to loop header |
647 | // to less than 1:1 ratio (meaning Weight should not be lower than |
648 | // SubWeight), as this could significantly reduce the loop's hotness, |
649 | // which would be incorrect in the case of underestimating the trip count. |
650 | Info.Weights[Idx] = |
651 | Info.Weights[Idx] > SubWeight |
652 | ? std::max(a: Info.Weights[Idx] - SubWeight, b: SubWeight) |
653 | : SubWeight; |
654 | } |
655 | |
656 | /// Initialize the weights for all exiting blocks. |
657 | static void initBranchWeights(DenseMap<Instruction *, WeightInfo> &WeightInfos, |
658 | Loop *L) { |
659 | SmallVector<BasicBlock *> ExitingBlocks; |
660 | L->getExitingBlocks(ExitingBlocks); |
661 | for (BasicBlock *ExitingBlock : ExitingBlocks) { |
662 | Instruction *Term = ExitingBlock->getTerminator(); |
663 | SmallVector<uint32_t> Weights; |
664 | if (!extractBranchWeights(I: *Term, Weights)) |
665 | continue; |
666 | |
667 | // See the comment on updateBranchWeights() for an explanation of what we |
668 | // do here. |
669 | uint32_t FallThroughWeights = 0; |
670 | uint32_t ExitWeights = 0; |
671 | for (auto [Succ, Weight] : zip(t: successors(I: Term), u&: Weights)) { |
672 | if (L->contains(BB: Succ)) |
673 | FallThroughWeights += Weight; |
674 | else |
675 | ExitWeights += Weight; |
676 | } |
677 | |
678 | // Don't try to update weights for degenerate case. |
679 | if (FallThroughWeights == 0) |
680 | continue; |
681 | |
682 | SmallVector<uint32_t> SubWeights; |
683 | for (auto [Succ, Weight] : zip(t: successors(I: Term), u&: Weights)) { |
684 | if (!L->contains(BB: Succ)) { |
685 | // Exit weights stay the same. |
686 | SubWeights.push_back(Elt: 0); |
687 | continue; |
688 | } |
689 | |
690 | // Subtract exit weights on each iteration, distributed across all |
691 | // fallthrough edges. |
692 | double W = (double)Weight / (double)FallThroughWeights; |
693 | SubWeights.push_back(Elt: (uint32_t)(ExitWeights * W)); |
694 | } |
695 | |
696 | WeightInfos.insert(KV: {Term, {.Weights: std::move(Weights), .SubWeights: std::move(SubWeights)}}); |
697 | } |
698 | } |
699 | |
700 | /// Clones the body of the loop L, putting it between \p InsertTop and \p |
701 | /// InsertBot. |
702 | /// \param IterNumber The serial number of the iteration currently being |
703 | /// peeled off. |
704 | /// \param ExitEdges The exit edges of the original loop. |
705 | /// \param[out] NewBlocks A list of the blocks in the newly created clone |
706 | /// \param[out] VMap The value map between the loop and the new clone. |
707 | /// \param LoopBlocks A helper for DFS-traversal of the loop. |
708 | /// \param LVMap A value-map that maps instructions from the original loop to |
709 | /// instructions in the last peeled-off iteration. |
710 | static void cloneLoopBlocks( |
711 | Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, |
712 | SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges, |
713 | SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks, |
714 | ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, |
715 | LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes, |
716 | ScalarEvolution &SE) { |
717 | BasicBlock * = L->getHeader(); |
718 | BasicBlock *Latch = L->getLoopLatch(); |
719 | BasicBlock * = L->getLoopPreheader(); |
720 | |
721 | Function *F = Header->getParent(); |
722 | LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO(); |
723 | LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO(); |
724 | Loop *ParentLoop = L->getParentLoop(); |
725 | |
726 | // For each block in the original loop, create a new copy, |
727 | // and update the value map with the newly created values. |
728 | for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { |
729 | BasicBlock *NewBB = CloneBasicBlock(BB: *BB, VMap, NameSuffix: ".peel" , F); |
730 | NewBlocks.push_back(Elt: NewBB); |
731 | |
732 | // If an original block is an immediate child of the loop L, its copy |
733 | // is a child of a ParentLoop after peeling. If a block is a child of |
734 | // a nested loop, it is handled in the cloneLoop() call below. |
735 | if (ParentLoop && LI->getLoopFor(BB: *BB) == L) |
736 | ParentLoop->addBasicBlockToLoop(NewBB, LI&: *LI); |
737 | |
738 | VMap[*BB] = NewBB; |
739 | |
740 | // If dominator tree is available, insert nodes to represent cloned blocks. |
741 | if (DT) { |
742 | if (Header == *BB) |
743 | DT->addNewBlock(BB: NewBB, DomBB: InsertTop); |
744 | else { |
745 | DomTreeNode *IDom = DT->getNode(BB: *BB)->getIDom(); |
746 | // VMap must contain entry for IDom, as the iteration order is RPO. |
747 | DT->addNewBlock(BB: NewBB, DomBB: cast<BasicBlock>(Val&: VMap[IDom->getBlock()])); |
748 | } |
749 | } |
750 | } |
751 | |
752 | { |
753 | // Identify what other metadata depends on the cloned version. After |
754 | // cloning, replace the metadata with the corrected version for both |
755 | // memory instructions and noalias intrinsics. |
756 | std::string Ext = (Twine("Peel" ) + Twine(IterNumber)).str(); |
757 | cloneAndAdaptNoAliasScopes(NoAliasDeclScopes: LoopLocalNoAliasDeclScopes, NewBlocks, |
758 | Context&: Header->getContext(), Ext); |
759 | } |
760 | |
761 | // Recursively create the new Loop objects for nested loops, if any, |
762 | // to preserve LoopInfo. |
763 | for (Loop *ChildLoop : *L) { |
764 | cloneLoop(L: ChildLoop, PL: ParentLoop, VM&: VMap, LI, LPM: nullptr); |
765 | } |
766 | |
767 | // Hook-up the control flow for the newly inserted blocks. |
768 | // The new header is hooked up directly to the "top", which is either |
769 | // the original loop preheader (for the first iteration) or the previous |
770 | // iteration's exiting block (for every other iteration) |
771 | InsertTop->getTerminator()->setSuccessor(Idx: 0, BB: cast<BasicBlock>(Val&: VMap[Header])); |
772 | |
773 | // Similarly, for the latch: |
774 | // The original exiting edge is still hooked up to the loop exit. |
775 | // The backedge now goes to the "bottom", which is either the loop's real |
776 | // header (for the last peeled iteration) or the copied header of the next |
777 | // iteration (for every other iteration) |
778 | BasicBlock *NewLatch = cast<BasicBlock>(Val&: VMap[Latch]); |
779 | auto *LatchTerm = cast<Instruction>(Val: NewLatch->getTerminator()); |
780 | for (unsigned idx = 0, e = LatchTerm->getNumSuccessors(); idx < e; ++idx) |
781 | if (LatchTerm->getSuccessor(Idx: idx) == Header) { |
782 | LatchTerm->setSuccessor(Idx: idx, BB: InsertBot); |
783 | break; |
784 | } |
785 | if (DT) |
786 | DT->changeImmediateDominator(BB: InsertBot, NewBB: NewLatch); |
787 | |
788 | // The new copy of the loop body starts with a bunch of PHI nodes |
789 | // that pick an incoming value from either the preheader, or the previous |
790 | // loop iteration. Since this copy is no longer part of the loop, we |
791 | // resolve this statically: |
792 | // For the first iteration, we use the value from the preheader directly. |
793 | // For any other iteration, we replace the phi with the value generated by |
794 | // the immediately preceding clone of the loop body (which represents |
795 | // the previous iteration). |
796 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) { |
797 | PHINode *NewPHI = cast<PHINode>(Val&: VMap[&*I]); |
798 | if (IterNumber == 0) { |
799 | VMap[&*I] = NewPHI->getIncomingValueForBlock(BB: PreHeader); |
800 | } else { |
801 | Value *LatchVal = NewPHI->getIncomingValueForBlock(BB: Latch); |
802 | Instruction *LatchInst = dyn_cast<Instruction>(Val: LatchVal); |
803 | if (LatchInst && L->contains(Inst: LatchInst)) |
804 | VMap[&*I] = LVMap[LatchInst]; |
805 | else |
806 | VMap[&*I] = LatchVal; |
807 | } |
808 | NewPHI->eraseFromParent(); |
809 | } |
810 | |
811 | // Fix up the outgoing values - we need to add a value for the iteration |
812 | // we've just created. Note that this must happen *after* the incoming |
813 | // values are adjusted, since the value going out of the latch may also be |
814 | // a value coming into the header. |
815 | for (auto Edge : ExitEdges) |
816 | for (PHINode &PHI : Edge.second->phis()) { |
817 | Value *LatchVal = PHI.getIncomingValueForBlock(BB: Edge.first); |
818 | Instruction *LatchInst = dyn_cast<Instruction>(Val: LatchVal); |
819 | if (LatchInst && L->contains(Inst: LatchInst)) |
820 | LatchVal = VMap[LatchVal]; |
821 | PHI.addIncoming(V: LatchVal, BB: cast<BasicBlock>(Val&: VMap[Edge.first])); |
822 | SE.forgetValue(V: &PHI); |
823 | } |
824 | |
825 | // LastValueMap is updated with the values for the current loop |
826 | // which are used the next time this function is called. |
827 | for (auto KV : VMap) |
828 | LVMap[KV.first] = KV.second; |
829 | } |
830 | |
831 | TargetTransformInfo::PeelingPreferences |
832 | llvm::gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, |
833 | const TargetTransformInfo &TTI, |
834 | std::optional<bool> UserAllowPeeling, |
835 | std::optional<bool> UserAllowProfileBasedPeeling, |
836 | bool UnrollingSpecficValues) { |
837 | TargetTransformInfo::PeelingPreferences PP; |
838 | |
839 | // Set the default values. |
840 | PP.PeelCount = 0; |
841 | PP.AllowPeeling = true; |
842 | PP.AllowLoopNestsPeeling = false; |
843 | PP.PeelProfiledIterations = true; |
844 | |
845 | // Get the target specifc values. |
846 | TTI.getPeelingPreferences(L, SE, PP); |
847 | |
848 | // User specified values using cl::opt. |
849 | if (UnrollingSpecficValues) { |
850 | if (UnrollPeelCount.getNumOccurrences() > 0) |
851 | PP.PeelCount = UnrollPeelCount; |
852 | if (UnrollAllowPeeling.getNumOccurrences() > 0) |
853 | PP.AllowPeeling = UnrollAllowPeeling; |
854 | if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0) |
855 | PP.AllowLoopNestsPeeling = UnrollAllowLoopNestsPeeling; |
856 | } |
857 | |
858 | // User specifed values provided by argument. |
859 | if (UserAllowPeeling) |
860 | PP.AllowPeeling = *UserAllowPeeling; |
861 | if (UserAllowProfileBasedPeeling) |
862 | PP.PeelProfiledIterations = *UserAllowProfileBasedPeeling; |
863 | |
864 | return PP; |
865 | } |
866 | |
867 | /// Peel off the first \p PeelCount iterations of loop \p L. |
868 | /// |
869 | /// Note that this does not peel them off as a single straight-line block. |
870 | /// Rather, each iteration is peeled off separately, and needs to check the |
871 | /// exit condition. |
872 | /// For loops that dynamically execute \p PeelCount iterations or less |
873 | /// this provides a benefit, since the peeled off iterations, which account |
874 | /// for the bulk of dynamic execution, can be further simplified by scalar |
875 | /// optimizations. |
876 | bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, |
877 | ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, |
878 | bool PreserveLCSSA, ValueToValueMapTy &LVMap) { |
879 | assert(PeelCount > 0 && "Attempt to peel out zero iterations?" ); |
880 | assert(canPeel(L) && "Attempt to peel a loop which is not peelable?" ); |
881 | |
882 | LoopBlocksDFS LoopBlocks(L); |
883 | LoopBlocks.perform(LI); |
884 | |
885 | BasicBlock * = L->getHeader(); |
886 | BasicBlock * = L->getLoopPreheader(); |
887 | BasicBlock *Latch = L->getLoopLatch(); |
888 | SmallVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitEdges; |
889 | L->getExitEdges(ExitEdges); |
890 | |
891 | // Remember dominators of blocks we might reach through exits to change them |
892 | // later. Immediate dominator of such block might change, because we add more |
893 | // routes which can lead to the exit: we can reach it from the peeled |
894 | // iterations too. |
895 | DenseMap<BasicBlock *, BasicBlock *> NonLoopBlocksIDom; |
896 | for (auto *BB : L->blocks()) { |
897 | auto *BBDomNode = DT.getNode(BB); |
898 | SmallVector<BasicBlock *, 16> ChildrenToUpdate; |
899 | for (auto *ChildDomNode : BBDomNode->children()) { |
900 | auto *ChildBB = ChildDomNode->getBlock(); |
901 | if (!L->contains(BB: ChildBB)) |
902 | ChildrenToUpdate.push_back(Elt: ChildBB); |
903 | } |
904 | // The new idom of the block will be the nearest common dominator |
905 | // of all copies of the previous idom. This is equivalent to the |
906 | // nearest common dominator of the previous idom and the first latch, |
907 | // which dominates all copies of the previous idom. |
908 | BasicBlock *NewIDom = DT.findNearestCommonDominator(A: BB, B: Latch); |
909 | for (auto *ChildBB : ChildrenToUpdate) |
910 | NonLoopBlocksIDom[ChildBB] = NewIDom; |
911 | } |
912 | |
913 | Function *F = Header->getParent(); |
914 | |
915 | // Set up all the necessary basic blocks. It is convenient to split the |
916 | // preheader into 3 parts - two blocks to anchor the peeled copy of the loop |
917 | // body, and a new preheader for the "real" loop. |
918 | |
919 | // Peeling the first iteration transforms. |
920 | // |
921 | // PreHeader: |
922 | // ... |
923 | // Header: |
924 | // LoopBody |
925 | // If (cond) goto Header |
926 | // Exit: |
927 | // |
928 | // into |
929 | // |
930 | // InsertTop: |
931 | // LoopBody |
932 | // If (!cond) goto Exit |
933 | // InsertBot: |
934 | // NewPreHeader: |
935 | // ... |
936 | // Header: |
937 | // LoopBody |
938 | // If (cond) goto Header |
939 | // Exit: |
940 | // |
941 | // Each following iteration will split the current bottom anchor in two, |
942 | // and put the new copy of the loop body between these two blocks. That is, |
943 | // after peeling another iteration from the example above, we'll split |
944 | // InsertBot, and get: |
945 | // |
946 | // InsertTop: |
947 | // LoopBody |
948 | // If (!cond) goto Exit |
949 | // InsertBot: |
950 | // LoopBody |
951 | // If (!cond) goto Exit |
952 | // InsertBot.next: |
953 | // NewPreHeader: |
954 | // ... |
955 | // Header: |
956 | // LoopBody |
957 | // If (cond) goto Header |
958 | // Exit: |
959 | |
960 | BasicBlock *InsertTop = SplitEdge(From: PreHeader, To: Header, DT: &DT, LI); |
961 | BasicBlock *InsertBot = |
962 | SplitBlock(Old: InsertTop, SplitPt: InsertTop->getTerminator(), DT: &DT, LI); |
963 | BasicBlock * = |
964 | SplitBlock(Old: InsertBot, SplitPt: InsertBot->getTerminator(), DT: &DT, LI); |
965 | |
966 | InsertTop->setName(Header->getName() + ".peel.begin" ); |
967 | InsertBot->setName(Header->getName() + ".peel.next" ); |
968 | NewPreHeader->setName(PreHeader->getName() + ".peel.newph" ); |
969 | |
970 | Instruction *LatchTerm = |
971 | cast<Instruction>(Val: cast<BasicBlock>(Val: Latch)->getTerminator()); |
972 | |
973 | // If we have branch weight information, we'll want to update it for the |
974 | // newly created branches. |
975 | DenseMap<Instruction *, WeightInfo> Weights; |
976 | initBranchWeights(WeightInfos&: Weights, L); |
977 | |
978 | // Identify what noalias metadata is inside the loop: if it is inside the |
979 | // loop, the associated metadata must be cloned for each iteration. |
980 | SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes; |
981 | identifyNoAliasScopesToClone(BBs: L->getBlocks(), NoAliasDeclScopes&: LoopLocalNoAliasDeclScopes); |
982 | |
983 | // For each peeled-off iteration, make a copy of the loop. |
984 | for (unsigned Iter = 0; Iter < PeelCount; ++Iter) { |
985 | SmallVector<BasicBlock *, 8> NewBlocks; |
986 | ValueToValueMapTy VMap; |
987 | |
988 | cloneLoopBlocks(L, IterNumber: Iter, InsertTop, InsertBot, ExitEdges, NewBlocks, |
989 | LoopBlocks, VMap, LVMap, DT: &DT, LI, |
990 | LoopLocalNoAliasDeclScopes, SE&: *SE); |
991 | |
992 | // Remap to use values from the current iteration instead of the |
993 | // previous one. |
994 | remapInstructionsInBlocks(Blocks: NewBlocks, VMap); |
995 | |
996 | // Update IDoms of the blocks reachable through exits. |
997 | if (Iter == 0) |
998 | for (auto BBIDom : NonLoopBlocksIDom) |
999 | DT.changeImmediateDominator(BB: BBIDom.first, |
1000 | NewBB: cast<BasicBlock>(Val&: LVMap[BBIDom.second])); |
1001 | #ifdef EXPENSIVE_CHECKS |
1002 | assert(DT.verify(DominatorTree::VerificationLevel::Fast)); |
1003 | #endif |
1004 | |
1005 | for (auto &[Term, Info] : Weights) { |
1006 | auto *TermCopy = cast<Instruction>(Val&: VMap[Term]); |
1007 | updateBranchWeights(Term: TermCopy, Info); |
1008 | } |
1009 | |
1010 | // Remove Loop metadata from the latch branch instruction |
1011 | // because it is not the Loop's latch branch anymore. |
1012 | auto *LatchTermCopy = cast<Instruction>(Val&: VMap[LatchTerm]); |
1013 | LatchTermCopy->setMetadata(KindID: LLVMContext::MD_loop, Node: nullptr); |
1014 | |
1015 | InsertTop = InsertBot; |
1016 | InsertBot = SplitBlock(Old: InsertBot, SplitPt: InsertBot->getTerminator(), DT: &DT, LI); |
1017 | InsertBot->setName(Header->getName() + ".peel.next" ); |
1018 | |
1019 | F->splice(ToIt: InsertTop->getIterator(), FromF: F, FromBeginIt: NewBlocks[0]->getIterator(), |
1020 | FromEndIt: F->end()); |
1021 | } |
1022 | |
1023 | // Now adjust the phi nodes in the loop header to get their initial values |
1024 | // from the last peeled-off iteration instead of the preheader. |
1025 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) { |
1026 | PHINode *PHI = cast<PHINode>(Val&: I); |
1027 | Value *NewVal = PHI->getIncomingValueForBlock(BB: Latch); |
1028 | Instruction *LatchInst = dyn_cast<Instruction>(Val: NewVal); |
1029 | if (LatchInst && L->contains(Inst: LatchInst)) |
1030 | NewVal = LVMap[LatchInst]; |
1031 | |
1032 | PHI->setIncomingValueForBlock(BB: NewPreHeader, V: NewVal); |
1033 | } |
1034 | |
1035 | for (const auto &[Term, Info] : Weights) { |
1036 | setBranchWeights(I&: *Term, Weights: Info.Weights); |
1037 | } |
1038 | |
1039 | // Update Metadata for count of peeled off iterations. |
1040 | unsigned AlreadyPeeled = 0; |
1041 | if (auto Peeled = getOptionalIntLoopAttribute(TheLoop: L, Name: PeeledCountMetaData)) |
1042 | AlreadyPeeled = *Peeled; |
1043 | addStringMetadataToLoop(TheLoop: L, MDString: PeeledCountMetaData, V: AlreadyPeeled + PeelCount); |
1044 | |
1045 | if (Loop *ParentLoop = L->getParentLoop()) |
1046 | L = ParentLoop; |
1047 | |
1048 | // We modified the loop, update SE. |
1049 | SE->forgetTopmostLoop(L); |
1050 | SE->forgetBlockAndLoopDispositions(); |
1051 | |
1052 | #ifdef EXPENSIVE_CHECKS |
1053 | // Finally DomtTree must be correct. |
1054 | assert(DT.verify(DominatorTree::VerificationLevel::Fast)); |
1055 | #endif |
1056 | |
1057 | // FIXME: Incrementally update loop-simplify |
1058 | simplifyLoop(L, DT: &DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA); |
1059 | |
1060 | NumPeeled++; |
1061 | |
1062 | return true; |
1063 | } |
1064 | |