Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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