Bug Summary

File:llvm/lib/Transforms/Scalar/LoopFlatten.cpp
Warning:line 619, column 3
Branch condition evaluates to a garbage value

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