Bug Summary

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