Bug Summary

File:llvm/lib/Transforms/Scalar/LoopFlatten.cpp
Warning:line 178, column 5
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);
1
Assuming 'DebugFlag' is true
→
2
←
Assuming the condition is false
→
3
←
Taking false branch
→
4
←
Loop condition is false. Exiting loop
→
101
102 if (!L->isLoopSimplifyForm()) {
5
←
Assuming the condition is false
→
6
←
Taking false branch
→
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) {
7
←
Assuming the condition is false
→
8
←
Taking false branch
→
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) {
9
←
Assuming 'InductionPHI' is non-null
→
10
←
Taking false branch
→
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);
11
←
Assuming 'DebugFlag' is true
→
12
←
Assuming the condition is true
→
13
←
Taking true branch
→
14
←
Loop condition is false. Exiting loop
→
124
125 bool ContinueOnTrue = L->contains(Latch->getTerminator()->getSuccessor(0));
126 auto IsValidPredicate = [&](ICmpInst::Predicate Pred) {
127 if (ContinueOnTrue)
17
←
Assuming 'ContinueOnTrue' is false
→
18
←
Taking false branch
→
128 return Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_ULT;
129 else
130 return Pred == CmpInst::ICMP_EQ;
19
←
Assuming 'Pred' is equal to ICMP_EQ
→
20
←
Returning the value 1, which participates in a condition later
→
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()) ||
15
←
Assuming 'Compare' is non-null
→
16
←
Calling 'operator()'
→
21
←
Returning from 'operator()'
→
23
←
Taking false branch
→
137 Compare->hasNUsesOrMore(2)) {
22
←
Assuming the condition is false
→
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());
24
←
The object is a 'BranchInst'
→
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);
25
←
Assuming 'DebugFlag' is false
→
26
←
Loop condition is false. Exiting loop
→
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);
27
←
Assuming 'DebugFlag' is false
→
28
←
Loop condition is false. Exiting loop
→
146
147 // Find increment and limit from the compare
148 Increment = nullptr;
149 if (match(Compare->getOperand(0),
29
←
Assuming the condition is true
→
30
←
Taking true branch
→
150 m_c_Add(m_Specific(InductionPHI), m_ConstantInt<1>()))) {
151 Increment = dyn_cast<BinaryOperator>(Compare->getOperand(0));
31
←
Assuming the object is a 'BinaryOperator'
→
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
31.1
'Increment' is non-null
 || Increment->hasNUsesOrMore(3)) {
32
←
Assuming the condition is false
→
33
←
Taking false branch
→
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);
34
←
Assuming 'DebugFlag' is false
→
35
←
Loop condition is false. Exiting loop
→
165 LLVM_DEBUG(dbgs() << "Found limit: "; Limit->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-flatten")) { dbgs() << "Found limit: "; Limit->
dump(); } } while (false);
36
←
Loop condition is false. Exiting loop
→
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__));
37
←
Assuming the condition is true
→
38
←
'?' condition is true
→
168
169 if (InductionPHI->getIncomingValueForBlock(Latch) != Increment) {
39
←
Assuming the condition is false
→
40
←
Taking false branch
→
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>(
41
←
Assuming the object is not a 'ConstantInt'
→
42
←
'CI' initialized to a null pointer value
→
176 InductionPHI->getIncomingValueForBlock(L->getLoopPreheader()));
177 if (!CI
42.1
'CI' is null
 || !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);
43
←
Assuming 'DebugFlag' is true
→
44
←
Assuming the condition is true
→
45
←
Taking true branch
→
46
←
Called C++ object pointer is null
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);
263 return true;
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()) {
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)
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) {
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);
322 return true;
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 &&
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)
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;
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,
465 FI.InnerLimit, FI.InnerIncrement, FI.InnerBranch, SE))
466 return false;
467 if (!findLoopComponents(FI.OuterLoop, IterationInstructions, FI.OuterInductionPHI,
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)) {
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)) {
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))
483 return false;
484
485 // FIXME: it should be possible to handle different types correctly.
486 if (FI.InnerInductionPHI->getType() != FI.OuterInductionPHI->getType())
487 return false;
488
489 if (!checkOuterLoopInsts(FI, IterationInstructions, TTI))
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))
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);
501 return true;
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);
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)
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);
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());
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) {
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);
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 != OuterType ||
586 InnerType->getScalarSizeInBits() >= MaxLegalSize ||
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);
589 return false;
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
)
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))
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))
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 == OverflowResult::AlwaysOverflowsHigh ||
638 OR == 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 == OverflowResult::MayOverflow) {
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);
647 return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
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()) {
654 auto *OuterLoop = InnerLoop->getParentLoop();
655 if (!OuterLoop)
656 continue;
657 FlattenInfo FI(OuterLoop, InnerLoop);
658 Changed |= FlattenLoopPair(FI, DT, LI, SE, AC, TTI);
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;
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);
724 }
725 return Changed;
726}