Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Scalar/LoopFlatten.cpp
Warning:line 162, column 7
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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