File: | llvm/lib/Transforms/Scalar/LoopFlatten.cpp |
Warning: | line 542, column 3 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 | ||||
54 | using namespace llvm; | |||
55 | using namespace llvm::PatternMatch; | |||
56 | ||||
57 | static 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 | ||||
62 | static 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 | ||||
68 | static 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 | ||||
74 | struct 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. | |||
96 | static bool findLoopComponents( | |||
97 | Loop *L, SmallPtrSetImpl<Instruction *> &IterationInstructions, | |||
98 | PHINode *&InductionPHI, Value *&Limit, BinaryOperator *&Increment, | |||
99 | BranchInst *&BackBranch, ScalarEvolution *SE) { | |||
100 | LLVM_DEBUG(dbgs() << "Finding components of loop: " << L->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Finding components of loop: " << L->getName() << "\n"; } } while (false); | |||
101 | ||||
102 | if (!L->isLoopSimplifyForm()) { | |||
103 | LLVM_DEBUG(dbgs() << "Loop is not in normal form\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Loop is not in normal form\n" ; } } while (false); | |||
104 | return false; | |||
105 | } | |||
106 | ||||
107 | // There must be exactly one exiting block, and it must be the same at the | |||
108 | // latch. | |||
109 | BasicBlock *Latch = L->getLoopLatch(); | |||
110 | if (L->getExitingBlock() != Latch) { | |||
111 | LLVM_DEBUG(dbgs() << "Exiting and latch block are different\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Exiting and latch block are different\n" ; } } while (false); | |||
112 | return false; | |||
113 | } | |||
114 | ||||
115 | // Find the induction PHI. If there is no induction PHI, we can't do the | |||
116 | // transformation. TODO: could other variables trigger this? Do we have to | |||
117 | // search for the best one? | |||
118 | InductionPHI = L->getInductionVariable(*SE); | |||
119 | if (!InductionPHI) { | |||
120 | LLVM_DEBUG(dbgs() << "Could not find induction PHI\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Could not find induction PHI\n" ; } } while (false); | |||
121 | return false; | |||
122 | } | |||
123 | LLVM_DEBUG(dbgs() << "Found induction PHI: "; InductionPHI->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Found induction PHI: "; InductionPHI ->dump(); } } while (false); | |||
124 | ||||
125 | bool ContinueOnTrue = L->contains(Latch->getTerminator()->getSuccessor(0)); | |||
126 | auto IsValidPredicate = [&](ICmpInst::Predicate Pred) { | |||
127 | if (ContinueOnTrue) | |||
128 | return Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_ULT; | |||
129 | else | |||
130 | return Pred == CmpInst::ICMP_EQ; | |||
131 | }; | |||
132 | ||||
133 | // Find Compare and make sure it is valid. getLatchCmpInst checks that the | |||
134 | // back branch of the latch is conditional. | |||
135 | ICmpInst *Compare = L->getLatchCmpInst(); | |||
136 | if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) || | |||
137 | Compare->hasNUsesOrMore(2)) { | |||
138 | LLVM_DEBUG(dbgs() << "Could not find valid comparison\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Could not find valid comparison\n" ; } } while (false); | |||
139 | return false; | |||
140 | } | |||
141 | BackBranch = cast<BranchInst>(Latch->getTerminator()); | |||
142 | IterationInstructions.insert(BackBranch); | |||
143 | LLVM_DEBUG(dbgs() << "Found back branch: "; BackBranch->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Found back branch: "; BackBranch ->dump(); } } while (false); | |||
144 | IterationInstructions.insert(Compare); | |||
145 | LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Found comparison: "; Compare ->dump(); } } while (false); | |||
146 | ||||
147 | // Find increment and limit from the compare | |||
148 | Increment = nullptr; | |||
149 | if (match(Compare->getOperand(0), | |||
150 | m_c_Add(m_Specific(InductionPHI), m_ConstantInt<1>()))) { | |||
151 | Increment = dyn_cast<BinaryOperator>(Compare->getOperand(0)); | |||
152 | Limit = Compare->getOperand(1); | |||
153 | } else if (Compare->getUnsignedPredicate() == CmpInst::ICMP_NE && | |||
154 | match(Compare->getOperand(1), | |||
155 | m_c_Add(m_Specific(InductionPHI), m_ConstantInt<1>()))) { | |||
156 | Increment = dyn_cast<BinaryOperator>(Compare->getOperand(1)); | |||
157 | Limit = Compare->getOperand(0); | |||
158 | } | |||
159 | if (!Increment || Increment->hasNUsesOrMore(3)) { | |||
160 | LLVM_DEBUG(dbgs() << "Cound not find valid increment\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Cound not find valid increment\n" ; } } while (false); | |||
161 | return false; | |||
162 | } | |||
163 | IterationInstructions.insert(Increment); | |||
164 | LLVM_DEBUG(dbgs() << "Found increment: "; Increment->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Found increment: "; Increment ->dump(); } } while (false); | |||
165 | LLVM_DEBUG(dbgs() << "Found limit: "; Limit->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Found limit: "; Limit-> dump(); } } while (false); | |||
166 | ||||
167 | assert(InductionPHI->getNumIncomingValues() == 2)(static_cast <bool> (InductionPHI->getNumIncomingValues () == 2) ? void (0) : __assert_fail ("InductionPHI->getNumIncomingValues() == 2" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/LoopFlatten.cpp" , 167, __extension__ __PRETTY_FUNCTION__)); | |||
168 | ||||
169 | if (InductionPHI->getIncomingValueForBlock(Latch) != Increment) { | |||
170 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Incoming value from latch is not the increment inst\n" ; } } while (false) | |||
171 | dbgs() << "Incoming value from latch is not the increment inst\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Incoming value from latch is not the increment inst\n" ; } } while (false); | |||
172 | return false; | |||
173 | } | |||
174 | ||||
175 | auto *CI = dyn_cast<ConstantInt>( | |||
176 | InductionPHI->getIncomingValueForBlock(L->getLoopPreheader())); | |||
177 | if (!CI || !CI->isZero()) { | |||
178 | LLVM_DEBUG(dbgs() << "PHI value is not zero: "; CI->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "PHI value is not zero: " ; CI->dump(); } } while (false); | |||
179 | return false; | |||
180 | } | |||
181 | ||||
182 | LLVM_DEBUG(dbgs() << "Successfully found all loop components\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-flatten")) { dbgs() << "Successfully found all loop components\n" ; } } while (false); | |||
183 | return true; | |||
184 | } | |||
185 | ||||
186 | static 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 | ||||
266 | static bool | |||
267 | checkOuterLoopInsts(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 | ||||
325 | static 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. | |||
421 | static 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 | ||||
460 | static 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 | ||||
504 | static 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 | ||||
566 | static 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
| |||
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 | ||||
616 | static 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
| |||
638 | OR
| |||
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
| |||
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 | ||||
650 | bool 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 | ||||
663 | PreservedAnalyses 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 | ||||
681 | namespace { | |||
682 | class LoopFlattenLegacyPass : public FunctionPass { | |||
683 | public: | |||
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 | ||||
702 | char LoopFlattenLegacyPass::ID = 0; | |||
703 | INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",static void *initializeLoopFlattenLegacyPassPassOnce(PassRegistry &Registry) { | |||
704 | false, false)static void *initializeLoopFlattenLegacyPassPassOnce(PassRegistry &Registry) { | |||
705 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry); | |||
706 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
707 | INITIALIZE_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 | ||||
710 | FunctionPass *llvm::createLoopFlattenPass() { return new LoopFlattenLegacyPass(); } | |||
711 | ||||
712 | bool 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 | } |