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 |
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 | "trip counts 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 | // 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) {}; | |||
94 | }; | |||
95 | ||||
96 | // Finds the induction variable, increment and trip count for a simple loop that | |||
97 | // we can flatten. | |||
98 | static 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); | |||
103 | ||||
104 | if (!L->isLoopSimplifyForm()) { | |||
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)) { | |||
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) { | |||
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) { | |||
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); | |||
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()) || | |||
146 | Compare->hasNUsesOrMore(2)) { | |||
147 | LLVM_DEBUG(dbgs() << "Could not find valid comparison\n")do { } while (false); | |||
148 | return false; | |||
149 | } | |||
150 | BackBranch = cast<BranchInst>(Latch->getTerminator()); | |||
151 | IterationInstructions.insert(BackBranch); | |||
152 | LLVM_DEBUG(dbgs() << "Found back branch: "; BackBranch->dump())do { } while (false); | |||
153 | IterationInstructions.insert(Compare); | |||
154 | LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump())do { } while (false); | |||
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 = | |||
161 | dyn_cast<BinaryOperator>(InductionPHI->getIncomingValueForBlock(Latch)); | |||
162 | if (Increment->hasNUsesOrMore(3)) { | |||
| ||||
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 | ||||
199 | static 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 | ||||
279 | static bool | |||
280 | checkOuterLoopInsts(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 | ||||
338 | static 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. | |||
434 | static 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 | ||||
473 | static 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, | |||
478 | FI.InnerInductionPHI, FI.InnerTripCount, | |||
479 | FI.InnerIncrement, FI.InnerBranch, SE, FI.Widened)) | |||
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 | ||||
519 | static 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 | ||||
581 | static 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 | ||||
631 | static bool FlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, | |||
632 | ScalarEvolution *SE, AssumptionCache *AC, | |||
633 | const TargetTransformInfo *TTI) { | |||
634 | LLVM_DEBUG(do { } while (false) | |||
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)) | |||
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 | ||||
665 | bool Flatten(LoopNest &LN, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, | |||
666 | AssumptionCache *AC, TargetTransformInfo *TTI) { | |||
667 | bool Changed = false; | |||
668 | for (Loop *InnerLoop : LN.getLoops()) { | |||
669 | auto *OuterLoop = InnerLoop->getParentLoop(); | |||
670 | if (!OuterLoop) | |||
671 | continue; | |||
672 | FlattenInfo FI(OuterLoop, InnerLoop); | |||
673 | Changed |= FlattenLoopPair(FI, DT, LI, SE, AC, TTI); | |||
674 | } | |||
675 | return Changed; | |||
676 | } | |||
677 | ||||
678 | PreservedAnalyses 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 | ||||
696 | namespace { | |||
697 | class LoopFlattenLegacyPass : public FunctionPass { | |||
698 | public: | |||
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 | ||||
717 | char LoopFlattenLegacyPass::ID = 0; | |||
718 | INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",static void *initializeLoopFlattenLegacyPassPassOnce(PassRegistry &Registry) { | |||
719 | false, false)static void *initializeLoopFlattenLegacyPassPassOnce(PassRegistry &Registry) { | |||
720 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry); | |||
721 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
722 | 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) ); } | |||
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 | ||||
725 | FunctionPass *llvm::createLoopFlattenPass() { return new LoopFlattenLegacyPass(); } | |||
726 | ||||
727 | bool 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; | |||
| ||||
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); | |||
739 | } | |||
740 | return Changed; | |||
741 | } |