Bug Summary

File:llvm/lib/Transforms/Scalar/LoopFlatten.cpp
Warning:line 177, column 7
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 LoopFlatten.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~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D 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~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -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-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Scalar/LoopFlatten.cpp
1//===- LoopFlatten.cpp - Loop flattening pass------------------------------===//
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 pass flattens pairs nested loops into a single loop.
10//
11// The intention is to optimise loop nests like this, which together access an
12// array linearly:
13// for (int i = 0; i < N; ++i)
14// for (int j = 0; j < M; ++j)
15// f(A[i*M+j]);
16// into one loop:
17// for (int i = 0; i < (N*M); ++i)
18// f(A[i]);
19//
20// It can also flatten loops where the induction variables are not used in the
21// loop. This is only worth doing if the induction variables are only used in an
22// expression like i*M+j. If they had any other uses, we would have to insert a
23// div/mod to reconstruct the original values, so this wouldn't be profitable.
24//
25// We also need to prove that N*M will not overflow.
26//
27//===----------------------------------------------------------------------===//
28
29#include "llvm/Transforms/Scalar/LoopFlatten.h"
30
31#include "llvm/ADT/Statistic.h"
32#include "llvm/Analysis/AssumptionCache.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/Analysis/OptimizationRemarkEmitter.h"
35#include "llvm/Analysis/ScalarEvolution.h"
36#include "llvm/Analysis/TargetTransformInfo.h"
37#include "llvm/Analysis/ValueTracking.h"
38#include "llvm/IR/Dominators.h"
39#include "llvm/IR/Function.h"
40#include "llvm/IR/IRBuilder.h"
41#include "llvm/IR/Module.h"
42#include "llvm/IR/PatternMatch.h"
43#include "llvm/IR/Verifier.h"
44#include "llvm/InitializePasses.h"
45#include "llvm/Pass.h"
46#include "llvm/Support/Debug.h"
47#include "llvm/Support/raw_ostream.h"
48#include "llvm/Transforms/Scalar.h"
49#include "llvm/Transforms/Utils/Local.h"
50#include "llvm/Transforms/Utils/LoopUtils.h"
51#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
52#include "llvm/Transforms/Utils/SimplifyIndVar.h"
53
54using namespace llvm;
55using namespace llvm::PatternMatch;
56
57#define DEBUG_TYPE"loop-flatten" "loop-flatten"
58
59STATISTIC(NumFlattened, "Number of loops flattened")static llvm::Statistic NumFlattened = {"loop-flatten", "NumFlattened"
, "Number of loops flattened"}
;
60
61static cl::opt<unsigned> RepeatedInstructionThreshold(
62 "loop-flatten-cost-threshold", cl::Hidden, cl::init(2),
63 cl::desc("Limit on the cost of instructions that can be repeated due to "
64 "loop flattening"));
65
66static cl::opt<bool>
67 AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden,
68 cl::init(false),
69 cl::desc("Assume that the product of the two iteration "
70 "trip counts will never overflow"));
71
72static cl::opt<bool>
73 WidenIV("loop-flatten-widen-iv", cl::Hidden,
74 cl::init(true),
75 cl::desc("Widen the loop induction variables, if possible, so "
76 "overflow checks won't reject flattening"));
77
78struct FlattenInfo {
79 Loop *OuterLoop = nullptr;
80 Loop *InnerLoop = nullptr;
81 // These PHINodes correspond to loop induction variables, which are expected
82 // to start at zero and increment by one on each loop.
83 PHINode *InnerInductionPHI = nullptr;
84 PHINode *OuterInductionPHI = nullptr;
85 Value *InnerTripCount = nullptr;
86 Value *OuterTripCount = nullptr;
87 BinaryOperator *InnerIncrement = nullptr;
88 BinaryOperator *OuterIncrement = nullptr;
89 BranchInst *InnerBranch = nullptr;
90 BranchInst *OuterBranch = nullptr;
91 SmallPtrSet<Value *, 4> LinearIVUses;
92 SmallPtrSet<PHINode *, 4> InnerPHIsToTransform;
93
94 // Whether this holds the flatten info before or after widening.
95 bool Widened = false;
96
97 FlattenInfo(Loop *OL, Loop *IL) : OuterLoop(OL), InnerLoop(IL) {};
8
Value assigned to 'FI.InnerIncrement'
98};
99
100static bool
101setLoopComponents(Value *&TC, Value *&TripCount, BinaryOperator *&Increment,
102 SmallPtrSetImpl<Instruction *> &IterationInstructions) {
103 TripCount = TC;
104 IterationInstructions.insert(Increment);
105 LLVM_DEBUG(dbgs() << "Found Increment: "; Increment->dump())do { } while (false);
106 LLVM_DEBUG(dbgs() << "Found trip count: "; TripCount->dump())do { } while (false);
107 LLVM_DEBUG(dbgs() << "Successfully found all loop components\n")do { } while (false);
108 return true;
109}
110
111// Finds the induction variable, increment and trip count for a simple loop that
112// we can flatten.
113static bool findLoopComponents(
114 Loop *L, SmallPtrSetImpl<Instruction *> &IterationInstructions,
115 PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment,
116 BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened) {
117 LLVM_DEBUG(dbgs() << "Finding components of loop: " << L->getName() << "\n")do { } while (false);
15
Loop condition is false. Exiting loop
118
119 if (!L->isLoopSimplifyForm()) {
16
Assuming the condition is false
17
Taking false branch
120 LLVM_DEBUG(dbgs() << "Loop is not in normal form\n")do { } while (false);
121 return false;
122 }
123
124 // Currently, to simplify the implementation, the Loop induction variable must
125 // start at zero and increment with a step size of one.
126 if (!L->isCanonical(*SE)) {
18
Assuming the condition is false
19
Taking false branch
127 LLVM_DEBUG(dbgs() << "Loop is not canonical\n")do { } while (false);
128 return false;
129 }
130
131 // There must be exactly one exiting block, and it must be the same at the
132 // latch.
133 BasicBlock *Latch = L->getLoopLatch();
134 if (L->getExitingBlock() != Latch) {
20
Assuming the condition is false
21
Taking false branch
135 LLVM_DEBUG(dbgs() << "Exiting and latch block are different\n")do { } while (false);
136 return false;
137 }
138
139 // Find the induction PHI. If there is no induction PHI, we can't do the
140 // transformation. TODO: could other variables trigger this? Do we have to
141 // search for the best one?
142 InductionPHI = L->getInductionVariable(*SE);
143 if (!InductionPHI) {
22
Assuming 'InductionPHI' is non-null
23
Taking false branch
144 LLVM_DEBUG(dbgs() << "Could not find induction PHI\n")do { } while (false);
145 return false;
146 }
147 LLVM_DEBUG(dbgs() << "Found induction PHI: "; InductionPHI->dump())do { } while (false);
24
Loop condition is false. Exiting loop
148
149 bool ContinueOnTrue = L->contains(Latch->getTerminator()->getSuccessor(0));
150 auto IsValidPredicate = [&](ICmpInst::Predicate Pred) {
151 if (ContinueOnTrue)
152 return Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_ULT;
153 else
154 return Pred == CmpInst::ICMP_EQ;
155 };
156
157 // Find Compare and make sure it is valid. getLatchCmpInst checks that the
158 // back branch of the latch is conditional.
159 ICmpInst *Compare = L->getLatchCmpInst();
160 if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) ||
25
Assuming 'Compare' is non-null
26
Assuming the condition is false
28
Taking false branch
161 Compare->hasNUsesOrMore(2)) {
27
Assuming the condition is false
162 LLVM_DEBUG(dbgs() << "Could not find valid comparison\n")do { } while (false);
163 return false;
164 }
165 BackBranch = cast<BranchInst>(Latch->getTerminator());
29
The object is a 'BranchInst'
166 IterationInstructions.insert(BackBranch);
167 LLVM_DEBUG(dbgs() << "Found back branch: "; BackBranch->dump())do { } while (false);
30
Loop condition is false. Exiting loop
168 IterationInstructions.insert(Compare);
169 LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump())do { } while (false);
31
Loop condition is false. Exiting loop
170
171 // Find increment and trip count.
172 // There are exactly 2 incoming values to the induction phi; one from the
173 // pre-header and one from the latch. The incoming latch value is the
174 // increment variable.
175 Increment =
33
Null pointer value stored to 'FI.InnerIncrement'
176 dyn_cast<BinaryOperator>(InductionPHI->getIncomingValueForBlock(Latch));
32
Assuming the object is not a 'BinaryOperator'
177 if (Increment->hasNUsesOrMore(3)) {
34
Called C++ object pointer is null
178 LLVM_DEBUG(dbgs() << "Could not find valid increment\n")do { } while (false);
179 return false;
180 }
181 // The trip count is the RHS of the compare. If this doesn't match the trip
182 // count computed by SCEV then this is because the trip count variable
183 // has been widened so the types don't match, or because it is a constant and
184 // another transformation has changed the compare (e.g. icmp ult %inc,
185 // tripcount -> icmp ult %j, tripcount-1), or both.
186 Value *RHS = Compare->getOperand(1);
187 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
188 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
189 LLVM_DEBUG(dbgs() << "Backedge-taken count is not predictable\n")do { } while (false);
190 return false;
191 }
192 const SCEV *SCEVTripCount = SE->getTripCountFromExitCount(BackedgeTakenCount);
193 const SCEV *SCEVRHS = SE->getSCEV(RHS);
194 if (SCEVRHS == SCEVTripCount)
195 return setLoopComponents(RHS, TripCount, Increment, IterationInstructions);
196 ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(RHS);
197 if (ConstantRHS) {
198 const SCEV *BackedgeTCExt = nullptr;
199 if (IsWidened) {
200 const SCEV *SCEVTripCountExt;
201 // Find the extended backedge taken count and extended trip count using
202 // SCEV. One of these should now match the RHS of the compare.
203 BackedgeTCExt = SE->getZeroExtendExpr(BackedgeTakenCount, RHS->getType());
204 SCEVTripCountExt = SE->getTripCountFromExitCount(BackedgeTCExt);
205 if (SCEVRHS != BackedgeTCExt && SCEVRHS != SCEVTripCountExt) {
206 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n")do { } while (false);
207 return false;
208 }
209 }
210 // If the RHS of the compare is equal to the backedge taken count we need
211 // to add one to get the trip count.
212 if (SCEVRHS == BackedgeTCExt || SCEVRHS == BackedgeTakenCount) {
213 ConstantInt *One = ConstantInt::get(ConstantRHS->getType(), 1);
214 Value *NewRHS = ConstantInt::get(
215 ConstantRHS->getContext(), ConstantRHS->getValue() + One->getValue());
216 return setLoopComponents(NewRHS, TripCount, Increment,
217 IterationInstructions);
218 }
219 return setLoopComponents(RHS, TripCount, Increment, IterationInstructions);
220 }
221 // If the RHS isn't a constant then check that the reason it doesn't match
222 // the SCEV trip count is because the RHS is a ZExt or SExt instruction
223 // (and take the trip count to be the RHS).
224 if (!IsWidened) {
225 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n")do { } while (false);
226 return false;
227 }
228 auto *TripCountInst = dyn_cast<Instruction>(RHS);
229 if (!TripCountInst) {
230 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n")do { } while (false);
231 return false;
232 }
233 if ((!isa<ZExtInst>(TripCountInst) && !isa<SExtInst>(TripCountInst)) ||
234 SE->getSCEV(TripCountInst->getOperand(0)) != SCEVTripCount) {
235 LLVM_DEBUG(dbgs() << "Could not find valid extended trip count\n")do { } while (false);
236 return false;
237 }
238 return setLoopComponents(RHS, TripCount, Increment, IterationInstructions);
239}
240
241static bool checkPHIs(FlattenInfo &FI, const TargetTransformInfo *TTI) {
242 // All PHIs in the inner and outer headers must either be:
243 // - The induction PHI, which we are going to rewrite as one induction in
244 // the new loop. This is already checked by findLoopComponents.
245 // - An outer header PHI with all incoming values from outside the loop.
246 // LoopSimplify guarantees we have a pre-header, so we don't need to
247 // worry about that here.
248 // - Pairs of PHIs in the inner and outer headers, which implement a
249 // loop-carried dependency that will still be valid in the new loop. To
250 // be valid, this variable must be modified only in the inner loop.
251
252 // The set of PHI nodes in the outer loop header that we know will still be
253 // valid after the transformation. These will not need to be modified (with
254 // the exception of the induction variable), but we do need to check that
255 // there are no unsafe PHI nodes.
256 SmallPtrSet<PHINode *, 4> SafeOuterPHIs;
257 SafeOuterPHIs.insert(FI.OuterInductionPHI);
258
259 // Check that all PHI nodes in the inner loop header match one of the valid
260 // patterns.
261 for (PHINode &InnerPHI : FI.InnerLoop->getHeader()->phis()) {
262 // The induction PHIs break these rules, and that's OK because we treat
263 // them specially when doing the transformation.
264 if (&InnerPHI == FI.InnerInductionPHI)
265 continue;
266
267 // Each inner loop PHI node must have two incoming values/blocks - one
268 // from the pre-header, and one from the latch.
269 assert(InnerPHI.getNumIncomingValues() == 2)(static_cast<void> (0));
270 Value *PreHeaderValue =
271 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopPreheader());
272 Value *LatchValue =
273 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopLatch());
274
275 // The incoming value from the outer loop must be the PHI node in the
276 // outer loop header, with no modifications made in the top of the outer
277 // loop.
278 PHINode *OuterPHI = dyn_cast<PHINode>(PreHeaderValue);
279 if (!OuterPHI || OuterPHI->getParent() != FI.OuterLoop->getHeader()) {
280 LLVM_DEBUG(dbgs() << "value modified in top of outer loop\n")do { } while (false);
281 return false;
282 }
283
284 // The other incoming value must come from the inner loop, without any
285 // modifications in the tail end of the outer loop. We are in LCSSA form,
286 // so this will actually be a PHI in the inner loop's exit block, which
287 // only uses values from inside the inner loop.
288 PHINode *LCSSAPHI = dyn_cast<PHINode>(
289 OuterPHI->getIncomingValueForBlock(FI.OuterLoop->getLoopLatch()));
290 if (!LCSSAPHI) {
291 LLVM_DEBUG(dbgs() << "could not find LCSSA PHI\n")do { } while (false);
292 return false;
293 }
294
295 // The value used by the LCSSA PHI must be the same one that the inner
296 // loop's PHI uses.
297 if (LCSSAPHI->hasConstantValue() != LatchValue) {
298 LLVM_DEBUG(do { } while (false)
299 dbgs() << "LCSSA PHI incoming value does not match latch value\n")do { } while (false);
300 return false;
301 }
302
303 LLVM_DEBUG(dbgs() << "PHI pair is safe:\n")do { } while (false);
304 LLVM_DEBUG(dbgs() << " Inner: "; InnerPHI.dump())do { } while (false);
305 LLVM_DEBUG(dbgs() << " Outer: "; OuterPHI->dump())do { } while (false);
306 SafeOuterPHIs.insert(OuterPHI);
307 FI.InnerPHIsToTransform.insert(&InnerPHI);
308 }
309
310 for (PHINode &OuterPHI : FI.OuterLoop->getHeader()->phis()) {
311 if (!SafeOuterPHIs.count(&OuterPHI)) {
312 LLVM_DEBUG(dbgs() << "found unsafe PHI in outer loop: "; OuterPHI.dump())do { } while (false);
313 return false;
314 }
315 }
316
317 LLVM_DEBUG(dbgs() << "checkPHIs: OK\n")do { } while (false);
318 return true;
319}
320
321static bool
322checkOuterLoopInsts(FlattenInfo &FI,
323 SmallPtrSetImpl<Instruction *> &IterationInstructions,
324 const TargetTransformInfo *TTI) {
325 // Check for instructions in the outer but not inner loop. If any of these
326 // have side-effects then this transformation is not legal, and if there is
327 // a significant amount of code here which can't be optimised out that it's
328 // not profitable (as these instructions would get executed for each
329 // iteration of the inner loop).
330 InstructionCost RepeatedInstrCost = 0;
331 for (auto *B : FI.OuterLoop->getBlocks()) {
332 if (FI.InnerLoop->contains(B))
333 continue;
334
335 for (auto &I : *B) {
336 if (!isa<PHINode>(&I) && !I.isTerminator() &&
337 !isSafeToSpeculativelyExecute(&I)) {
338 LLVM_DEBUG(dbgs() << "Cannot flatten because instruction may have "do { } while (false)
339 "side effects: ";do { } while (false)
340 I.dump())do { } while (false);
341 return false;
342 }
343 // The execution count of the outer loop's iteration instructions
344 // (increment, compare and branch) will be increased, but the
345 // equivalent instructions will be removed from the inner loop, so
346 // they make a net difference of zero.
347 if (IterationInstructions.count(&I))
348 continue;
349 // The uncoditional branch to the inner loop's header will turn into
350 // a fall-through, so adds no cost.
351 BranchInst *Br = dyn_cast<BranchInst>(&I);
352 if (Br && Br->isUnconditional() &&
353 Br->getSuccessor(0) == FI.InnerLoop->getHeader())
354 continue;
355 // Multiplies of the outer iteration variable and inner iteration
356 // count will be optimised out.
357 if (match(&I, m_c_Mul(m_Specific(FI.OuterInductionPHI),
358 m_Specific(FI.InnerTripCount))))
359 continue;
360 InstructionCost Cost =
361 TTI->getUserCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
362 LLVM_DEBUG(dbgs() << "Cost " << Cost << ": "; I.dump())do { } while (false);
363 RepeatedInstrCost += Cost;
364 }
365 }
366
367 LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "do { } while (false)
368 << RepeatedInstrCost << "\n")do { } while (false);
369 // Bail out if flattening the loops would cause instructions in the outer
370 // loop but not in the inner loop to be executed extra times.
371 if (RepeatedInstrCost > RepeatedInstructionThreshold) {
372 LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n")do { } while (false);
373 return false;
374 }
375
376 LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: OK\n")do { } while (false);
377 return true;
378}
379
380static bool checkIVUsers(FlattenInfo &FI) {
381 // We require all uses of both induction variables to match this pattern:
382 //
383 // (OuterPHI * InnerTripCount) + InnerPHI
384 //
385 // Any uses of the induction variables not matching that pattern would
386 // require a div/mod to reconstruct in the flattened loop, so the
387 // transformation wouldn't be profitable.
388
389 Value *InnerTripCount = FI.InnerTripCount;
390 if (FI.Widened &&
391 (isa<SExtInst>(InnerTripCount) || isa<ZExtInst>(InnerTripCount)))
392 InnerTripCount = cast<Instruction>(InnerTripCount)->getOperand(0);
393
394 // Check that all uses of the inner loop's induction variable match the
395 // expected pattern, recording the uses of the outer IV.
396 SmallPtrSet<Value *, 4> ValidOuterPHIUses;
397 for (User *U : FI.InnerInductionPHI->users()) {
398 if (U == FI.InnerIncrement)
399 continue;
400
401 // After widening the IVs, a trunc instruction might have been introduced, so
402 // look through truncs.
403 if (isa<TruncInst>(U)) {
404 if (!U->hasOneUse())
405 return false;
406 U = *U->user_begin();
407 }
408
409 // If the use is in the compare (which is also the condition of the inner
410 // branch) then the compare has been altered by another transformation e.g
411 // icmp ult %inc, tripcount -> icmp ult %j, tripcount-1, where tripcount is
412 // a constant. Ignore this use as the compare gets removed later anyway.
413 if (U == FI.InnerBranch->getCondition())
414 continue;
415
416 LLVM_DEBUG(dbgs() << "Found use of inner induction variable: "; U->dump())do { } while (false);
417
418 Value *MatchedMul;
419 Value *MatchedItCount;
420 bool IsAdd = match(U, m_c_Add(m_Specific(FI.InnerInductionPHI),
421 m_Value(MatchedMul))) &&
422 match(MatchedMul, m_c_Mul(m_Specific(FI.OuterInductionPHI),
423 m_Value(MatchedItCount)));
424
425 // Matches the same pattern as above, except it also looks for truncs
426 // on the phi, which can be the result of widening the induction variables.
427 bool IsAddTrunc = match(U, m_c_Add(m_Trunc(m_Specific(FI.InnerInductionPHI)),
428 m_Value(MatchedMul))) &&
429 match(MatchedMul,
430 m_c_Mul(m_Trunc(m_Specific(FI.OuterInductionPHI)),
431 m_Value(MatchedItCount)));
432
433 if ((IsAdd || IsAddTrunc) && MatchedItCount == InnerTripCount) {
434 LLVM_DEBUG(dbgs() << "Use is optimisable\n")do { } while (false);
435 ValidOuterPHIUses.insert(MatchedMul);
436 FI.LinearIVUses.insert(U);
437 } else {
438 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n")do { } while (false);
439 return false;
440 }
441 }
442
443 // Check that there are no uses of the outer IV other than the ones found
444 // as part of the pattern above.
445 for (User *U : FI.OuterInductionPHI->users()) {
446 if (U == FI.OuterIncrement)
447 continue;
448
449 auto IsValidOuterPHIUses = [&] (User *U) -> bool {
450 LLVM_DEBUG(dbgs() << "Found use of outer induction variable: "; U->dump())do { } while (false);
451 if (!ValidOuterPHIUses.count(U)) {
452 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n")do { } while (false);
453 return false;
454 }
455 LLVM_DEBUG(dbgs() << "Use is optimisable\n")do { } while (false);
456 return true;
457 };
458
459 if (auto *V = dyn_cast<TruncInst>(U)) {
460 for (auto *K : V->users()) {
461 if (!IsValidOuterPHIUses(K))
462 return false;
463 }
464 continue;
465 }
466
467 if (!IsValidOuterPHIUses(U))
468 return false;
469 }
470
471 LLVM_DEBUG(dbgs() << "checkIVUsers: OK\n";do { } while (false)
472 dbgs() << "Found " << FI.LinearIVUses.size()do { } while (false)
473 << " value(s) that can be replaced:\n";do { } while (false)
474 for (Value *V : FI.LinearIVUses) {do { } while (false)
475 dbgs() << " ";do { } while (false)
476 V->dump();do { } while (false)
477 })do { } while (false);
478 return true;
479}
480
481// Return an OverflowResult dependant on if overflow of the multiplication of
482// InnerTripCount and OuterTripCount can be assumed not to happen.
483static OverflowResult checkOverflow(FlattenInfo &FI, DominatorTree *DT,
484 AssumptionCache *AC) {
485 Function *F = FI.OuterLoop->getHeader()->getParent();
486 const DataLayout &DL = F->getParent()->getDataLayout();
487
488 // For debugging/testing.
489 if (AssumeNoOverflow)
490 return OverflowResult::NeverOverflows;
491
492 // Check if the multiply could not overflow due to known ranges of the
493 // input values.
494 OverflowResult OR = computeOverflowForUnsignedMul(
495 FI.InnerTripCount, FI.OuterTripCount, DL, AC,
496 FI.OuterLoop->getLoopPreheader()->getTerminator(), DT);
497 if (OR != OverflowResult::MayOverflow)
498 return OR;
499
500 for (Value *V : FI.LinearIVUses) {
501 for (Value *U : V->users()) {
502 if (auto *GEP = dyn_cast<GetElementPtrInst>(U)) {
503 for (Value *GEPUser : U->users()) {
504 Instruction *GEPUserInst = dyn_cast<Instruction>(GEPUser);
505 if (!isa<LoadInst>(GEPUserInst) &&
506 !(isa<StoreInst>(GEPUserInst) &&
507 GEP == GEPUserInst->getOperand(1)))
508 continue;
509 if (!isGuaranteedToExecuteForEveryIteration(GEPUserInst,
510 FI.InnerLoop))
511 continue;
512 // The IV is used as the operand of a GEP which dominates the loop
513 // latch, and the IV is at least as wide as the address space of the
514 // GEP. In this case, the GEP would wrap around the address space
515 // before the IV increment wraps, which would be UB.
516 if (GEP->isInBounds() &&
517 V->getType()->getIntegerBitWidth() >=
518 DL.getPointerTypeSizeInBits(GEP->getType())) {
519 LLVM_DEBUG(do { } while (false)
520 dbgs() << "use of linear IV would be UB if overflow occurred: ";do { } while (false)
521 GEP->dump())do { } while (false);
522 return OverflowResult::NeverOverflows;
523 }
524 }
525 }
526 }
527 }
528
529 return OverflowResult::MayOverflow;
530}
531
532static bool CanFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
533 ScalarEvolution *SE, AssumptionCache *AC,
534 const TargetTransformInfo *TTI) {
535 SmallPtrSet<Instruction *, 8> IterationInstructions;
536 if (!findLoopComponents(FI.InnerLoop, IterationInstructions,
14
Calling 'findLoopComponents'
537 FI.InnerInductionPHI, FI.InnerTripCount,
538 FI.InnerIncrement, FI.InnerBranch, SE, FI.Widened))
13
Passing value via 5th parameter 'Increment'
539 return false;
540 if (!findLoopComponents(FI.OuterLoop, IterationInstructions,
541 FI.OuterInductionPHI, FI.OuterTripCount,
542 FI.OuterIncrement, FI.OuterBranch, SE, FI.Widened))
543 return false;
544
545 // Both of the loop trip count values must be invariant in the outer loop
546 // (non-instructions are all inherently invariant).
547 if (!FI.OuterLoop->isLoopInvariant(FI.InnerTripCount)) {
548 LLVM_DEBUG(dbgs() << "inner loop trip count not invariant\n")do { } while (false);
549 return false;
550 }
551 if (!FI.OuterLoop->isLoopInvariant(FI.OuterTripCount)) {
552 LLVM_DEBUG(dbgs() << "outer loop trip count not invariant\n")do { } while (false);
553 return false;
554 }
555
556 if (!checkPHIs(FI, TTI))
557 return false;
558
559 // FIXME: it should be possible to handle different types correctly.
560 if (FI.InnerInductionPHI->getType() != FI.OuterInductionPHI->getType())
561 return false;
562
563 if (!checkOuterLoopInsts(FI, IterationInstructions, TTI))
564 return false;
565
566 // Find the values in the loop that can be replaced with the linearized
567 // induction variable, and check that there are no other uses of the inner
568 // or outer induction variable. If there were, we could still do this
569 // transformation, but we'd have to insert a div/mod to calculate the
570 // original IVs, so it wouldn't be profitable.
571 if (!checkIVUsers(FI))
572 return false;
573
574 LLVM_DEBUG(dbgs() << "CanFlattenLoopPair: OK\n")do { } while (false);
575 return true;
576}
577
578static bool DoFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
579 ScalarEvolution *SE, AssumptionCache *AC,
580 const TargetTransformInfo *TTI) {
581 Function *F = FI.OuterLoop->getHeader()->getParent();
582 LLVM_DEBUG(dbgs() << "Checks all passed, doing the transformation\n")do { } while (false);
583 {
584 using namespace ore;
585 OptimizationRemark Remark(DEBUG_TYPE"loop-flatten", "Flattened", FI.InnerLoop->getStartLoc(),
586 FI.InnerLoop->getHeader());
587 OptimizationRemarkEmitter ORE(F);
588 Remark << "Flattened into outer loop";
589 ORE.emit(Remark);
590 }
591
592 Value *NewTripCount = BinaryOperator::CreateMul(
593 FI.InnerTripCount, FI.OuterTripCount, "flatten.tripcount",
594 FI.OuterLoop->getLoopPreheader()->getTerminator());
595 LLVM_DEBUG(dbgs() << "Created new trip count in preheader: ";do { } while (false)
596 NewTripCount->dump())do { } while (false);
597
598 // Fix up PHI nodes that take values from the inner loop back-edge, which
599 // we are about to remove.
600 FI.InnerInductionPHI->removeIncomingValue(FI.InnerLoop->getLoopLatch());
601
602 // The old Phi will be optimised away later, but for now we can't leave
603 // leave it in an invalid state, so are updating them too.
604 for (PHINode *PHI : FI.InnerPHIsToTransform)
605 PHI->removeIncomingValue(FI.InnerLoop->getLoopLatch());
606
607 // Modify the trip count of the outer loop to be the product of the two
608 // trip counts.
609 cast<User>(FI.OuterBranch->getCondition())->setOperand(1, NewTripCount);
610
611 // Replace the inner loop backedge with an unconditional branch to the exit.
612 BasicBlock *InnerExitBlock = FI.InnerLoop->getExitBlock();
613 BasicBlock *InnerExitingBlock = FI.InnerLoop->getExitingBlock();
614 InnerExitingBlock->getTerminator()->eraseFromParent();
615 BranchInst::Create(InnerExitBlock, InnerExitingBlock);
616 DT->deleteEdge(InnerExitingBlock, FI.InnerLoop->getHeader());
617
618 // Replace all uses of the polynomial calculated from the two induction
619 // variables with the one new one.
620 IRBuilder<> Builder(FI.OuterInductionPHI->getParent()->getTerminator());
621 for (Value *V : FI.LinearIVUses) {
622 Value *OuterValue = FI.OuterInductionPHI;
623 if (FI.Widened)
624 OuterValue = Builder.CreateTrunc(FI.OuterInductionPHI, V->getType(),
625 "flatten.trunciv");
626
627 LLVM_DEBUG(dbgs() << "Replacing: "; V->dump();do { } while (false)
628 dbgs() << "with: "; OuterValue->dump())do { } while (false);
629 V->replaceAllUsesWith(OuterValue);
630 }
631
632 // Tell LoopInfo, SCEV and the pass manager that the inner loop has been
633 // deleted, and any information that have about the outer loop invalidated.
634 SE->forgetLoop(FI.OuterLoop);
635 SE->forgetLoop(FI.InnerLoop);
636 LI->erase(FI.InnerLoop);
637
638 // Increment statistic value.
639 NumFlattened++;
640
641 return true;
642}
643
644static bool CanWidenIV(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
645 ScalarEvolution *SE, AssumptionCache *AC,
646 const TargetTransformInfo *TTI) {
647 if (!WidenIV) {
648 LLVM_DEBUG(dbgs() << "Widening the IVs is disabled\n")do { } while (false);
649 return false;
650 }
651
652 LLVM_DEBUG(dbgs() << "Try widening the IVs\n")do { } while (false);
653 Module *M = FI.InnerLoop->getHeader()->getParent()->getParent();
654 auto &DL = M->getDataLayout();
655 auto *InnerType = FI.InnerInductionPHI->getType();
656 auto *OuterType = FI.OuterInductionPHI->getType();
657 unsigned MaxLegalSize = DL.getLargestLegalIntTypeSizeInBits();
658 auto *MaxLegalType = DL.getLargestLegalIntType(M->getContext());
659
660 // If both induction types are less than the maximum legal integer width,
661 // promote both to the widest type available so we know calculating
662 // (OuterTripCount * InnerTripCount) as the new trip count is safe.
663 if (InnerType != OuterType ||
664 InnerType->getScalarSizeInBits() >= MaxLegalSize ||
665 MaxLegalType->getScalarSizeInBits() < InnerType->getScalarSizeInBits() * 2) {
666 LLVM_DEBUG(dbgs() << "Can't widen the IV\n")do { } while (false);
667 return false;
668 }
669
670 SCEVExpander Rewriter(*SE, DL, "loopflatten");
671 SmallVector<WideIVInfo, 2> WideIVs;
672 SmallVector<WeakTrackingVH, 4> DeadInsts;
673 WideIVs.push_back( {FI.InnerInductionPHI, MaxLegalType, false });
674 WideIVs.push_back( {FI.OuterInductionPHI, MaxLegalType, false });
675 unsigned ElimExt = 0;
676 unsigned Widened = 0;
677
678 for (const auto &WideIV : WideIVs) {
679 PHINode *WidePhi = createWideIV(WideIV, LI, SE, Rewriter, DT, DeadInsts,
680 ElimExt, Widened, true /* HasGuards */,
681 true /* UsePostIncrementRanges */);
682 if (!WidePhi)
683 return false;
684 LLVM_DEBUG(dbgs() << "Created wide phi: "; WidePhi->dump())do { } while (false);
685 LLVM_DEBUG(dbgs() << "Deleting old phi: "; WideIV.NarrowIV->dump())do { } while (false);
686 RecursivelyDeleteDeadPHINode(WideIV.NarrowIV);
687 }
688 // After widening, rediscover all the loop components.
689 assert(Widened && "Widened IV expected")(static_cast<void> (0));
690 FI.Widened = true;
691 return CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
692}
693
694static bool FlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
695 ScalarEvolution *SE, AssumptionCache *AC,
696 const TargetTransformInfo *TTI) {
697 LLVM_DEBUG(do { } while (false)
11
Loop condition is false. Exiting loop
698 dbgs() << "Loop flattening running on outer loop "do { } while (false)
699 << FI.OuterLoop->getHeader()->getName() << " and inner loop "do { } while (false)
700 << FI.InnerLoop->getHeader()->getName() << " in "do { } while (false)
701 << FI.OuterLoop->getHeader()->getParent()->getName() << "\n")do { } while (false);
702
703 if (!CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI))
12
Calling 'CanFlattenLoopPair'
704 return false;
705
706 // Check if we can widen the induction variables to avoid overflow checks.
707 if (CanWidenIV(FI, DT, LI, SE, AC, TTI))
708 return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
709
710 // Check if the new iteration variable might overflow. In this case, we
711 // need to version the loop, and select the original version at runtime if
712 // the iteration space is too large.
713 // TODO: We currently don't version the loop.
714 OverflowResult OR = checkOverflow(FI, DT, AC);
715 if (OR == OverflowResult::AlwaysOverflowsHigh ||
716 OR == OverflowResult::AlwaysOverflowsLow) {
717 LLVM_DEBUG(dbgs() << "Multiply would always overflow, so not profitable\n")do { } while (false);
718 return false;
719 } else if (OR == OverflowResult::MayOverflow) {
720 LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n")do { } while (false);
721 return false;
722 }
723
724 LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n")do { } while (false);
725 return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
726}
727
728bool Flatten(LoopNest &LN, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
729 AssumptionCache *AC, TargetTransformInfo *TTI) {
730 bool Changed = false;
731 for (Loop *InnerLoop : LN.getLoops()) {
4
Assuming '__begin1' is not equal to '__end1'
732 auto *OuterLoop = InnerLoop->getParentLoop();
733 if (!OuterLoop)
5
Assuming 'OuterLoop' is non-null
6
Taking false branch
734 continue;
735 FlattenInfo FI(OuterLoop, InnerLoop);
7
Calling constructor for 'FlattenInfo'
9
Returning from constructor for 'FlattenInfo'
736 Changed |= FlattenLoopPair(FI, DT, LI, SE, AC, TTI);
10
Calling 'FlattenLoopPair'
737 }
738 return Changed;
739}
740
741PreservedAnalyses LoopFlattenPass::run(LoopNest &LN, LoopAnalysisManager &LAM,
742 LoopStandardAnalysisResults &AR,
743 LPMUpdater &U) {
744
745 bool Changed = false;
746
747 // The loop flattening pass requires loops to be
748 // in simplified form, and also needs LCSSA. Running
749 // this pass will simplify all loops that contain inner loops,
750 // regardless of whether anything ends up being flattened.
751 Changed |= Flatten(LN, &AR.DT, &AR.LI, &AR.SE, &AR.AC, &AR.TTI);
752
753 if (!Changed)
754 return PreservedAnalyses::all();
755
756 return PreservedAnalyses::none();
757}
758
759namespace {
760class LoopFlattenLegacyPass : public FunctionPass {
761public:
762 static char ID; // Pass ID, replacement for typeid
763 LoopFlattenLegacyPass() : FunctionPass(ID) {
764 initializeLoopFlattenLegacyPassPass(*PassRegistry::getPassRegistry());
765 }
766
767 // Possibly flatten loop L into its child.
768 bool runOnFunction(Function &F) override;
769
770 void getAnalysisUsage(AnalysisUsage &AU) const override {
771 getLoopAnalysisUsage(AU);
772 AU.addRequired<TargetTransformInfoWrapperPass>();
773 AU.addPreserved<TargetTransformInfoWrapperPass>();
774 AU.addRequired<AssumptionCacheTracker>();
775 AU.addPreserved<AssumptionCacheTracker>();
776 }
777};
778} // namespace
779
780char LoopFlattenLegacyPass::ID = 0;
781INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",static void *initializeLoopFlattenLegacyPassPassOnce(PassRegistry
&Registry) {
782 false, false)static void *initializeLoopFlattenLegacyPassPassOnce(PassRegistry
&Registry) {
783INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
784INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
785INITIALIZE_PASS_END(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",PassInfo *PI = new PassInfo( "Flattens loops", "loop-flatten"
, &LoopFlattenLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopFlattenLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopFlattenLegacyPassPassFlag
; void llvm::initializeLoopFlattenLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoopFlattenLegacyPassPassFlag
, initializeLoopFlattenLegacyPassPassOnce, std::ref(Registry)
); }
786 false, false)PassInfo *PI = new PassInfo( "Flattens loops", "loop-flatten"
, &LoopFlattenLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopFlattenLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopFlattenLegacyPassPassFlag
; void llvm::initializeLoopFlattenLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoopFlattenLegacyPassPassFlag
, initializeLoopFlattenLegacyPassPassOnce, std::ref(Registry)
); }
787
788FunctionPass *llvm::createLoopFlattenPass() { return new LoopFlattenLegacyPass(); }
789
790bool LoopFlattenLegacyPass::runOnFunction(Function &F) {
791 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
792 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
793 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
794 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
1
Assuming 'DTWP' is null
2
'?' condition is false
795 auto &TTIP = getAnalysis<TargetTransformInfoWrapperPass>();
796 auto *TTI = &TTIP.getTTI(F);
797 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
798 bool Changed = false;
799 for (Loop *L : *LI) {
800 auto LN = LoopNest::getLoopNest(*L, *SE);
801 Changed |= Flatten(*LN, DT, LI, SE, AC, TTI);
3
Calling 'Flatten'
802 }
803 return Changed;
804}