Bug Summary

File:llvm/lib/Transforms/Utils/LoopPeel.cpp
Warning:line 852, column 3
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopPeel.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/build-llvm/lib/Transforms/Utils -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/build-llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/build-llvm/lib/Transforms/Utils -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-08-25-171901-26424-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210825111122+868bd9938db1/llvm/lib/Transforms/Utils/LoopPeel.cpp
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
47using namespace llvm;
48using namespace llvm::PatternMatch;
49
50#define DEBUG_TYPE"loop-peel" "loop-peel"
51
52STATISTIC(NumPeeled, "Number of loops peeled")static llvm::Statistic NumPeeled = {"loop-peel", "NumPeeled",
"Number of loops peeled"};
53
54static cl::opt<unsigned> UnrollPeelCount(
55 "unroll-peel-count", cl::Hidden,
56 cl::desc("Set the unroll peeling count, for testing purposes"));
57
58static 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
63static 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
68static 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
72static 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
76static 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
80static 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).
85static const unsigned InfiniteIterationsToInvariance =
86 std::numeric_limits<unsigned>::max();
87
88// Check whether we are capable of peeling this loop.
89bool 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.
142static 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// }
189static 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.
293void 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).
437static 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.
461static 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.
478static 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.
505static 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
624TargetTransformInfo::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.
667bool 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__));
1
Assuming 'PeelCount' is > 0
→
2
←
'?' condition is true
→
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__));
3
←
'?' condition is true
→
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) {
4
←
Assuming 'DT' is null
→
5
←
Taking false branch
→
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());
6
←
'Latch' is a 'BasicBlock'
→
7
←
The object is a 'BranchInst'
→
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
7.1
'Iter' is < 'PeelCount'
 < PeelCount; ++Iter) {
8
←
Loop condition is true. Entering loop body
→
10
←
Assuming 'Iter' is >= 'PeelCount'
→
11
←
Loop condition is false. Execution continues on line 827
→
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
8.1
'DT' is null
) {
9
←
Taking false branch
→
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) {
12
←
Assuming 'I' is not a 'PHINode'
→
13
←
Loop condition is false. Execution continues on line 837
→
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))
14
←
Assuming the condition is false
→
15
←
Taking false branch
→
842 AlreadyPeeled = *Peeled;
843 addStringMetadataToLoop(L, PeeledCountMetaData, AlreadyPeeled + PeelCount);
844
845 if (Loop *ParentLoop = L->getParentLoop())
16
←
Assuming 'ParentLoop' is null
→
17
←
Taking false branch
→
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__));
18
←
Called C++ object pointer is null
853
854 // FIXME: Incrementally update loop-simplify
855 simplifyLoop(L, DT, LI, SE, AC, nullptr, PreserveLCSSA);
856
857 NumPeeled++;
858
859 return true;
860}