/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===// |
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 file implements induction variable simplification. It does |
10 | | // not define any actual pass or policy, but provides a single function to |
11 | | // simplify a loop's induction variables based on ScalarEvolution. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "llvm/Transforms/Utils/SimplifyIndVar.h" |
16 | | #include "llvm/ADT/STLExtras.h" |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/ADT/Statistic.h" |
19 | | #include "llvm/Analysis/LoopInfo.h" |
20 | | #include "llvm/Analysis/ScalarEvolutionExpander.h" |
21 | | #include "llvm/IR/DataLayout.h" |
22 | | #include "llvm/IR/Dominators.h" |
23 | | #include "llvm/IR/IRBuilder.h" |
24 | | #include "llvm/IR/Instructions.h" |
25 | | #include "llvm/IR/IntrinsicInst.h" |
26 | | #include "llvm/IR/PatternMatch.h" |
27 | | #include "llvm/Support/Debug.h" |
28 | | #include "llvm/Support/raw_ostream.h" |
29 | | #include "llvm/Transforms/Utils/Local.h" |
30 | | |
31 | | using namespace llvm; |
32 | | |
33 | | #define DEBUG_TYPE "indvars" |
34 | | |
35 | | STATISTIC(NumElimIdentity, "Number of IV identities eliminated"); |
36 | | STATISTIC(NumElimOperand, "Number of IV operands folded into a use"); |
37 | | STATISTIC(NumFoldedUser, "Number of IV users folded into a constant"); |
38 | | STATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); |
39 | | STATISTIC( |
40 | | NumSimplifiedSDiv, |
41 | | "Number of IV signed division operations converted to unsigned division"); |
42 | | STATISTIC( |
43 | | NumSimplifiedSRem, |
44 | | "Number of IV signed remainder operations converted to unsigned remainder"); |
45 | | STATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); |
46 | | |
47 | | namespace { |
48 | | /// This is a utility for simplifying induction variables |
49 | | /// based on ScalarEvolution. It is the primary instrument of the |
50 | | /// IndvarSimplify pass, but it may also be directly invoked to cleanup after |
51 | | /// other loop passes that preserve SCEV. |
52 | | class SimplifyIndvar { |
53 | | Loop *L; |
54 | | LoopInfo *LI; |
55 | | ScalarEvolution *SE; |
56 | | DominatorTree *DT; |
57 | | SCEVExpander &Rewriter; |
58 | | SmallVectorImpl<WeakTrackingVH> &DeadInsts; |
59 | | |
60 | | bool Changed; |
61 | | |
62 | | public: |
63 | | SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT, |
64 | | LoopInfo *LI, SCEVExpander &Rewriter, |
65 | | SmallVectorImpl<WeakTrackingVH> &Dead) |
66 | | : L(Loop), LI(LI), SE(SE), DT(DT), Rewriter(Rewriter), DeadInsts(Dead), |
67 | 326k | Changed(false) { |
68 | 326k | assert(LI && "IV simplification requires LoopInfo"); |
69 | 326k | } |
70 | | |
71 | 326k | bool hasChanged() const { return Changed; } |
72 | | |
73 | | /// Iteratively perform simplification on a worklist of users of the |
74 | | /// specified induction variable. This is the top-level driver that applies |
75 | | /// all simplifications to users of an IV. |
76 | | void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr); |
77 | | |
78 | | Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand); |
79 | | |
80 | | bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand); |
81 | | bool replaceIVUserWithLoopInvariant(Instruction *UseInst); |
82 | | |
83 | | bool eliminateOverflowIntrinsic(WithOverflowInst *WO); |
84 | | bool eliminateSaturatingIntrinsic(SaturatingInst *SI); |
85 | | bool eliminateTrunc(TruncInst *TI); |
86 | | bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand); |
87 | | bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand); |
88 | | void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand); |
89 | | void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand, |
90 | | bool IsSigned); |
91 | | void replaceRemWithNumerator(BinaryOperator *Rem); |
92 | | void replaceRemWithNumeratorOrZero(BinaryOperator *Rem); |
93 | | void replaceSRemWithURem(BinaryOperator *Rem); |
94 | | bool eliminateSDiv(BinaryOperator *SDiv); |
95 | | bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand); |
96 | | bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand); |
97 | | }; |
98 | | } |
99 | | |
100 | | /// Fold an IV operand into its use. This removes increments of an |
101 | | /// aligned IV when used by a instruction that ignores the low bits. |
102 | | /// |
103 | | /// IVOperand is guaranteed SCEVable, but UseInst may not be. |
104 | | /// |
105 | | /// Return the operand of IVOperand for this induction variable if IVOperand can |
106 | | /// be folded (in case more folding opportunities have been exposed). |
107 | | /// Otherwise return null. |
108 | 1.33M | Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) { |
109 | 1.33M | Value *IVSrc = nullptr; |
110 | 1.33M | const unsigned OperIdx = 0; |
111 | 1.33M | const SCEV *FoldedExpr = nullptr; |
112 | 1.33M | bool MustDropExactFlag = false; |
113 | 1.33M | switch (UseInst->getOpcode()) { |
114 | 1.33M | default: |
115 | 1.32M | return nullptr; |
116 | 1.33M | case Instruction::UDiv: |
117 | 5.17k | case Instruction::LShr: |
118 | 5.17k | // We're only interested in the case where we know something about |
119 | 5.17k | // the numerator and have a constant denominator. |
120 | 5.17k | if (IVOperand != UseInst->getOperand(OperIdx) || |
121 | 5.17k | !isa<ConstantInt>(UseInst->getOperand(1))5.03k ) |
122 | 373 | return nullptr; |
123 | 4.80k | |
124 | 4.80k | // Attempt to fold a binary operator with constant operand. |
125 | 4.80k | // e.g. ((I + 1) >> 2) => I >> 2 |
126 | 4.80k | if (!isa<BinaryOperator>(IVOperand) |
127 | 4.80k | || !isa<ConstantInt>(IVOperand->getOperand(1))283 ) |
128 | 4.55k | return nullptr; |
129 | 244 | |
130 | 244 | IVSrc = IVOperand->getOperand(0); |
131 | 244 | // IVSrc must be the (SCEVable) IV, since the other operand is const. |
132 | 244 | assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand"); |
133 | 244 | |
134 | 244 | ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1)); |
135 | 244 | if (UseInst->getOpcode() == Instruction::LShr) { |
136 | 240 | // Get a constant for the divisor. See createSCEV. |
137 | 240 | uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth(); |
138 | 240 | if (D->getValue().uge(BitWidth)) |
139 | 0 | return nullptr; |
140 | 240 | |
141 | 240 | D = ConstantInt::get(UseInst->getContext(), |
142 | 240 | APInt::getOneBitSet(BitWidth, D->getZExtValue())); |
143 | 240 | } |
144 | 244 | FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D)); |
145 | 244 | // We might have 'exact' flag set at this point which will no longer be |
146 | 244 | // correct after we make the replacement. |
147 | 244 | if (UseInst->isExact() && |
148 | 244 | SE->getSCEV(IVSrc) != SE->getMulExpr(FoldedExpr, SE->getSCEV(D))7 ) |
149 | 7 | MustDropExactFlag = true; |
150 | 1.33M | } |
151 | 1.33M | // We have something that might fold it's operand. Compare SCEVs. |
152 | 1.33M | if (244 !SE->isSCEVable(UseInst->getType())244 ) |
153 | 0 | return nullptr; |
154 | 244 | |
155 | 244 | // Bypass the operand if SCEV can prove it has no effect. |
156 | 244 | if (SE->getSCEV(UseInst) != FoldedExpr) |
157 | 231 | return nullptr; |
158 | 13 | |
159 | 13 | LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand |
160 | 13 | << " -> " << *UseInst << '\n'); |
161 | 13 | |
162 | 13 | UseInst->setOperand(OperIdx, IVSrc); |
163 | 13 | assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper"); |
164 | 13 | |
165 | 13 | if (MustDropExactFlag) |
166 | 1 | UseInst->dropPoisonGeneratingFlags(); |
167 | 13 | |
168 | 13 | ++NumElimOperand; |
169 | 13 | Changed = true; |
170 | 13 | if (IVOperand->use_empty()) |
171 | 1 | DeadInsts.emplace_back(IVOperand); |
172 | 13 | return IVSrc; |
173 | 13 | } |
174 | | |
175 | | bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp, |
176 | 206k | Value *IVOperand) { |
177 | 206k | unsigned IVOperIdx = 0; |
178 | 206k | ICmpInst::Predicate Pred = ICmp->getPredicate(); |
179 | 206k | if (IVOperand != ICmp->getOperand(0)) { |
180 | 14.0k | // Swapped |
181 | 14.0k | assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); |
182 | 14.0k | IVOperIdx = 1; |
183 | 14.0k | Pred = ICmpInst::getSwappedPredicate(Pred); |
184 | 14.0k | } |
185 | 206k | |
186 | 206k | // Get the SCEVs for the ICmp operands (in the specific context of the |
187 | 206k | // current loop) |
188 | 206k | const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); |
189 | 206k | const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop); |
190 | 206k | const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop); |
191 | 206k | |
192 | 206k | ICmpInst::Predicate InvariantPredicate; |
193 | 206k | const SCEV *InvariantLHS, *InvariantRHS; |
194 | 206k | |
195 | 206k | auto *PN = dyn_cast<PHINode>(IVOperand); |
196 | 206k | if (!PN) |
197 | 156k | return false; |
198 | 50.3k | if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate, |
199 | 50.3k | InvariantLHS, InvariantRHS)) |
200 | 50.2k | return false; |
201 | 20 | |
202 | 20 | // Rewrite the comparison to a loop invariant comparison if it can be done |
203 | 20 | // cheaply, where cheaply means "we don't need to emit any new |
204 | 20 | // instructions". |
205 | 20 | |
206 | 20 | SmallDenseMap<const SCEV*, Value*> CheapExpansions; |
207 | 20 | CheapExpansions[S] = ICmp->getOperand(IVOperIdx); |
208 | 20 | CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx); |
209 | 20 | |
210 | 20 | // TODO: Support multiple entry loops? (We currently bail out of these in |
211 | 20 | // the IndVarSimplify pass) |
212 | 20 | if (auto *BB = L->getLoopPredecessor()) { |
213 | 20 | const int Idx = PN->getBasicBlockIndex(BB); |
214 | 20 | if (Idx >= 0) { |
215 | 19 | Value *Incoming = PN->getIncomingValue(Idx); |
216 | 19 | const SCEV *IncomingS = SE->getSCEV(Incoming); |
217 | 19 | CheapExpansions[IncomingS] = Incoming; |
218 | 19 | } |
219 | 20 | } |
220 | 20 | Value *NewLHS = CheapExpansions[InvariantLHS]; |
221 | 20 | Value *NewRHS = CheapExpansions[InvariantRHS]; |
222 | 20 | |
223 | 20 | if (!NewLHS) |
224 | 1 | if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS)) |
225 | 1 | NewLHS = ConstLHS->getValue(); |
226 | 20 | if (!NewRHS) |
227 | 0 | if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS)) |
228 | 0 | NewRHS = ConstRHS->getValue(); |
229 | 20 | |
230 | 20 | if (!NewLHS || !NewRHS) |
231 | 0 | // We could not find an existing value to replace either LHS or RHS. |
232 | 0 | // Generating new instructions has subtler tradeoffs, so avoid doing that |
233 | 0 | // for now. |
234 | 0 | return false; |
235 | 20 | |
236 | 20 | LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n'); |
237 | 20 | ICmp->setPredicate(InvariantPredicate); |
238 | 20 | ICmp->setOperand(0, NewLHS); |
239 | 20 | ICmp->setOperand(1, NewRHS); |
240 | 20 | return true; |
241 | 20 | } |
242 | | |
243 | | /// SimplifyIVUsers helper for eliminating useless |
244 | | /// comparisons against an induction variable. |
245 | 207k | void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { |
246 | 207k | unsigned IVOperIdx = 0; |
247 | 207k | ICmpInst::Predicate Pred = ICmp->getPredicate(); |
248 | 207k | ICmpInst::Predicate OriginalPred = Pred; |
249 | 207k | if (IVOperand != ICmp->getOperand(0)) { |
250 | 14.1k | // Swapped |
251 | 14.1k | assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); |
252 | 14.1k | IVOperIdx = 1; |
253 | 14.1k | Pred = ICmpInst::getSwappedPredicate(Pred); |
254 | 14.1k | } |
255 | 207k | |
256 | 207k | // Get the SCEVs for the ICmp operands (in the specific context of the |
257 | 207k | // current loop) |
258 | 207k | const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); |
259 | 207k | const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop); |
260 | 207k | const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop); |
261 | 207k | |
262 | 207k | // If the condition is always true or always false, replace it with |
263 | 207k | // a constant value. |
264 | 207k | if (SE->isKnownPredicate(Pred, S, X)) { |
265 | 397 | ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); |
266 | 397 | DeadInsts.emplace_back(ICmp); |
267 | 397 | LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); |
268 | 207k | } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) { |
269 | 518 | ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); |
270 | 518 | DeadInsts.emplace_back(ICmp); |
271 | 518 | LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); |
272 | 206k | } else if (makeIVComparisonInvariant(ICmp, IVOperand)) { |
273 | 20 | // fallthrough to end of function |
274 | 206k | } else if (ICmpInst::isSigned(OriginalPred) && |
275 | 206k | SE->isKnownNonNegative(S)56.6k && SE->isKnownNonNegative(X)40.7k ) { |
276 | 6.10k | // If we were unable to make anything above, all we can is to canonicalize |
277 | 6.10k | // the comparison hoping that it will open the doors for other |
278 | 6.10k | // optimizations. If we find out that we compare two non-negative values, |
279 | 6.10k | // we turn the instruction's predicate to its unsigned version. Note that |
280 | 6.10k | // we cannot rely on Pred here unless we check if we have swapped it. |
281 | 6.10k | assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?"); |
282 | 6.10k | LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp |
283 | 6.10k | << '\n'); |
284 | 6.10k | ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred)); |
285 | 6.10k | } else |
286 | 200k | return; |
287 | 7.03k | |
288 | 7.03k | ++NumElimCmp; |
289 | 7.03k | Changed = true; |
290 | 7.03k | } |
291 | | |
292 | 304 | bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) { |
293 | 304 | // Get the SCEVs for the ICmp operands. |
294 | 304 | auto *N = SE->getSCEV(SDiv->getOperand(0)); |
295 | 304 | auto *D = SE->getSCEV(SDiv->getOperand(1)); |
296 | 304 | |
297 | 304 | // Simplify unnecessary loops away. |
298 | 304 | const Loop *L = LI->getLoopFor(SDiv->getParent()); |
299 | 304 | N = SE->getSCEVAtScope(N, L); |
300 | 304 | D = SE->getSCEVAtScope(D, L); |
301 | 304 | |
302 | 304 | // Replace sdiv by udiv if both of the operands are non-negative |
303 | 304 | if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)16 ) { |
304 | 9 | auto *UDiv = BinaryOperator::Create( |
305 | 9 | BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1), |
306 | 9 | SDiv->getName() + ".udiv", SDiv); |
307 | 9 | UDiv->setIsExact(SDiv->isExact()); |
308 | 9 | SDiv->replaceAllUsesWith(UDiv); |
309 | 9 | LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n'); |
310 | 9 | ++NumSimplifiedSDiv; |
311 | 9 | Changed = true; |
312 | 9 | DeadInsts.push_back(SDiv); |
313 | 9 | return true; |
314 | 9 | } |
315 | 295 | |
316 | 295 | return false; |
317 | 295 | } |
318 | | |
319 | | // i %s n -> i %u n if i >= 0 and n >= 0 |
320 | 6 | void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) { |
321 | 6 | auto *N = Rem->getOperand(0), *D = Rem->getOperand(1); |
322 | 6 | auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D, |
323 | 6 | Rem->getName() + ".urem", Rem); |
324 | 6 | Rem->replaceAllUsesWith(URem); |
325 | 6 | LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n'); |
326 | 6 | ++NumSimplifiedSRem; |
327 | 6 | Changed = true; |
328 | 6 | DeadInsts.emplace_back(Rem); |
329 | 6 | } |
330 | | |
331 | | // i % n --> i if i is in [0,n). |
332 | 1 | void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) { |
333 | 1 | Rem->replaceAllUsesWith(Rem->getOperand(0)); |
334 | 1 | LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); |
335 | 1 | ++NumElimRem; |
336 | 1 | Changed = true; |
337 | 1 | DeadInsts.emplace_back(Rem); |
338 | 1 | } |
339 | | |
340 | | // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). |
341 | 26 | void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) { |
342 | 26 | auto *T = Rem->getType(); |
343 | 26 | auto *N = Rem->getOperand(0), *D = Rem->getOperand(1); |
344 | 26 | ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D); |
345 | 26 | SelectInst *Sel = |
346 | 26 | SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem); |
347 | 26 | Rem->replaceAllUsesWith(Sel); |
348 | 26 | LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); |
349 | 26 | ++NumElimRem; |
350 | 26 | Changed = true; |
351 | 26 | DeadInsts.emplace_back(Rem); |
352 | 26 | } |
353 | | |
354 | | /// SimplifyIVUsers helper for eliminating useless remainder operations |
355 | | /// operating on an induction variable or replacing srem by urem. |
356 | | void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand, |
357 | 593 | bool IsSigned) { |
358 | 593 | auto *NValue = Rem->getOperand(0); |
359 | 593 | auto *DValue = Rem->getOperand(1); |
360 | 593 | // We're only interested in the case where we know something about |
361 | 593 | // the numerator, unless it is a srem, because we want to replace srem by urem |
362 | 593 | // in general. |
363 | 593 | bool UsedAsNumerator = IVOperand == NValue; |
364 | 593 | if (!UsedAsNumerator && !IsSigned74 ) |
365 | 11 | return; |
366 | 582 | |
367 | 582 | const SCEV *N = SE->getSCEV(NValue); |
368 | 582 | |
369 | 582 | // Simplify unnecessary loops away. |
370 | 582 | const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); |
371 | 582 | N = SE->getSCEVAtScope(N, ICmpLoop); |
372 | 582 | |
373 | 582 | bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N)232 ; |
374 | 582 | |
375 | 582 | // Do not proceed if the Numerator may be negative |
376 | 582 | if (!IsNumeratorNonNegative) |
377 | 217 | return; |
378 | 365 | |
379 | 365 | const SCEV *D = SE->getSCEV(DValue); |
380 | 365 | D = SE->getSCEVAtScope(D, ICmpLoop); |
381 | 365 | |
382 | 365 | if (UsedAsNumerator) { |
383 | 364 | auto LT = IsSigned ? ICmpInst::ICMP_SLT14 : ICmpInst::ICMP_ULT350 ; |
384 | 364 | if (SE->isKnownPredicate(LT, N, D)) { |
385 | 1 | replaceRemWithNumerator(Rem); |
386 | 1 | return; |
387 | 1 | } |
388 | 363 | |
389 | 363 | auto *T = Rem->getType(); |
390 | 363 | const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T)); |
391 | 363 | if (SE->isKnownPredicate(LT, NLessOne, D)) { |
392 | 26 | replaceRemWithNumeratorOrZero(Rem); |
393 | 26 | return; |
394 | 26 | } |
395 | 338 | } |
396 | 338 | |
397 | 338 | // Try to replace SRem with URem, if both N and D are known non-negative. |
398 | 338 | // Since we had already check N, we only need to check D now |
399 | 338 | if (!IsSigned || !SE->isKnownNonNegative(D)13 ) |
400 | 332 | return; |
401 | 6 | |
402 | 6 | replaceSRemWithURem(Rem); |
403 | 6 | } |
404 | | |
405 | | static bool willNotOverflow(ScalarEvolution *SE, Instruction::BinaryOps BinOp, |
406 | 154k | bool Signed, const SCEV *LHS, const SCEV *RHS) { |
407 | 154k | const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *, |
408 | 154k | SCEV::NoWrapFlags, unsigned); |
409 | 154k | switch (BinOp) { |
410 | 154k | default: |
411 | 0 | llvm_unreachable("Unsupported binary op"); |
412 | 154k | case Instruction::Add: |
413 | 125k | Operation = &ScalarEvolution::getAddExpr; |
414 | 125k | break; |
415 | 154k | case Instruction::Sub: |
416 | 20.2k | Operation = &ScalarEvolution::getMinusSCEV; |
417 | 20.2k | break; |
418 | 154k | case Instruction::Mul: |
419 | 8.66k | Operation = &ScalarEvolution::getMulExpr; |
420 | 8.66k | break; |
421 | 154k | } |
422 | 154k | |
423 | 154k | const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) = |
424 | 154k | Signed ? &ScalarEvolution::getSignExtendExpr63.8k |
425 | 154k | : &ScalarEvolution::getZeroExtendExpr90.7k ; |
426 | 154k | |
427 | 154k | // Check ext(LHS op RHS) == ext(LHS) op ext(RHS) |
428 | 154k | auto *NarrowTy = cast<IntegerType>(LHS->getType()); |
429 | 154k | auto *WideTy = |
430 | 154k | IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2); |
431 | 154k | |
432 | 154k | const SCEV *A = |
433 | 154k | (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), |
434 | 154k | WideTy, 0); |
435 | 154k | const SCEV *B = |
436 | 154k | (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0), |
437 | 154k | (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0); |
438 | 154k | return A == B; |
439 | 154k | } |
440 | | |
441 | 6 | bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) { |
442 | 6 | const SCEV *LHS = SE->getSCEV(WO->getLHS()); |
443 | 6 | const SCEV *RHS = SE->getSCEV(WO->getRHS()); |
444 | 6 | if (!willNotOverflow(SE, WO->getBinaryOp(), WO->isSigned(), LHS, RHS)) |
445 | 3 | return false; |
446 | 3 | |
447 | 3 | // Proved no overflow, nuke the overflow check and, if possible, the overflow |
448 | 3 | // intrinsic as well. |
449 | 3 | |
450 | 3 | BinaryOperator *NewResult = BinaryOperator::Create( |
451 | 3 | WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO); |
452 | 3 | |
453 | 3 | if (WO->isSigned()) |
454 | 2 | NewResult->setHasNoSignedWrap(true); |
455 | 1 | else |
456 | 1 | NewResult->setHasNoUnsignedWrap(true); |
457 | 3 | |
458 | 3 | SmallVector<ExtractValueInst *, 4> ToDelete; |
459 | 3 | |
460 | 6 | for (auto *U : WO->users()) { |
461 | 6 | if (auto *EVI = dyn_cast<ExtractValueInst>(U)) { |
462 | 6 | if (EVI->getIndices()[0] == 1) |
463 | 3 | EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext())); |
464 | 3 | else { |
465 | 3 | assert(EVI->getIndices()[0] == 0 && "Only two possibilities!"); |
466 | 3 | EVI->replaceAllUsesWith(NewResult); |
467 | 3 | } |
468 | 6 | ToDelete.push_back(EVI); |
469 | 6 | } |
470 | 6 | } |
471 | 3 | |
472 | 3 | for (auto *EVI : ToDelete) |
473 | 6 | EVI->eraseFromParent(); |
474 | 3 | |
475 | 3 | if (WO->use_empty()) |
476 | 3 | WO->eraseFromParent(); |
477 | 3 | |
478 | 3 | return true; |
479 | 3 | } |
480 | | |
481 | 7 | bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) { |
482 | 7 | const SCEV *LHS = SE->getSCEV(SI->getLHS()); |
483 | 7 | const SCEV *RHS = SE->getSCEV(SI->getRHS()); |
484 | 7 | if (!willNotOverflow(SE, SI->getBinaryOp(), SI->isSigned(), LHS, RHS)) |
485 | 3 | return false; |
486 | 4 | |
487 | 4 | BinaryOperator *BO = BinaryOperator::Create( |
488 | 4 | SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI); |
489 | 4 | if (SI->isSigned()) |
490 | 2 | BO->setHasNoSignedWrap(); |
491 | 2 | else |
492 | 2 | BO->setHasNoUnsignedWrap(); |
493 | 4 | |
494 | 4 | SI->replaceAllUsesWith(BO); |
495 | 4 | DeadInsts.emplace_back(SI); |
496 | 4 | Changed = true; |
497 | 4 | return true; |
498 | 4 | } |
499 | | |
500 | 37.7k | bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) { |
501 | 37.7k | // It is always legal to replace |
502 | 37.7k | // icmp <pred> i32 trunc(iv), n |
503 | 37.7k | // with |
504 | 37.7k | // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate. |
505 | 37.7k | // Or with |
506 | 37.7k | // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate. |
507 | 37.7k | // Or with either of these if pred is an equality predicate. |
508 | 37.7k | // |
509 | 37.7k | // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for |
510 | 37.7k | // every comparison which uses trunc, it means that we can replace each of |
511 | 37.7k | // them with comparison of iv against sext/zext(n). We no longer need trunc |
512 | 37.7k | // after that. |
513 | 37.7k | // |
514 | 37.7k | // TODO: Should we do this if we can widen *some* comparisons, but not all |
515 | 37.7k | // of them? Sometimes it is enough to enable other optimizations, but the |
516 | 37.7k | // trunc instruction will stay in the loop. |
517 | 37.7k | Value *IV = TI->getOperand(0); |
518 | 37.7k | Type *IVTy = IV->getType(); |
519 | 37.7k | const SCEV *IVSCEV = SE->getSCEV(IV); |
520 | 37.7k | const SCEV *TISCEV = SE->getSCEV(TI); |
521 | 37.7k | |
522 | 37.7k | // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can |
523 | 37.7k | // get rid of trunc |
524 | 37.7k | bool DoesSExtCollapse = false; |
525 | 37.7k | bool DoesZExtCollapse = false; |
526 | 37.7k | if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy)) |
527 | 20.7k | DoesSExtCollapse = true; |
528 | 37.7k | if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy)) |
529 | 32.5k | DoesZExtCollapse = true; |
530 | 37.7k | |
531 | 37.7k | // If neither sext nor zext does collapse, it is not profitable to do any |
532 | 37.7k | // transform. Bail. |
533 | 37.7k | if (!DoesSExtCollapse && !DoesZExtCollapse17.0k ) |
534 | 3.64k | return false; |
535 | 34.1k | |
536 | 34.1k | // Collect users of the trunc that look like comparisons against invariants. |
537 | 34.1k | // Bail if we find something different. |
538 | 34.1k | SmallVector<ICmpInst *, 4> ICmpUsers; |
539 | 34.1k | for (auto *U : TI->users()) { |
540 | 34.1k | // We don't care about users in unreachable blocks. |
541 | 34.1k | if (isa<Instruction>(U) && |
542 | 34.1k | !DT->isReachableFromEntry(cast<Instruction>(U)->getParent())) |
543 | 1 | continue; |
544 | 34.1k | ICmpInst *ICI = dyn_cast<ICmpInst>(U); |
545 | 34.1k | if (!ICI) return false20.8k ; |
546 | 13.2k | assert(L->contains(ICI->getParent()) && "LCSSA form broken?"); |
547 | 13.2k | if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))13.2k ) && |
548 | 13.2k | !(64 ICI->getOperand(1) == TI64 && L->isLoopInvariant(ICI->getOperand(0))27 )) |
549 | 46 | return false; |
550 | 13.2k | // If we cannot get rid of trunc, bail. |
551 | 13.2k | if (ICI->isSigned() && !DoesSExtCollapse231 ) |
552 | 193 | return false; |
553 | 13.0k | if (ICI->isUnsigned() && !DoesZExtCollapse15 ) |
554 | 5 | return false; |
555 | 13.0k | // For equality, either signed or unsigned works. |
556 | 13.0k | ICmpUsers.push_back(ICI); |
557 | 13.0k | } |
558 | 34.1k | |
559 | 34.1k | auto CanUseZExt = [&](ICmpInst *ICI) 13.0k { |
560 | 13.0k | // Unsigned comparison can be widened as unsigned. |
561 | 13.0k | if (ICI->isUnsigned()) |
562 | 9 | return true; |
563 | 12.9k | // Is it profitable to do zext? |
564 | 12.9k | if (!DoesZExtCollapse) |
565 | 512 | return false; |
566 | 12.4k | // For equality, we can safely zext both parts. |
567 | 12.4k | if (ICI->isEquality()) |
568 | 12.4k | return true; |
569 | 34 | // Otherwise we can only use zext when comparing two non-negative or two |
570 | 34 | // negative values. But in practice, we will never pass DoesZExtCollapse |
571 | 34 | // check for a negative value, because zext(trunc(x)) is non-negative. So |
572 | 34 | // it only make sense to check for non-negativity here. |
573 | 34 | const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0)); |
574 | 34 | const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1)); |
575 | 34 | return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2)7 ; |
576 | 34 | }; |
577 | 13.0k | // Replace all comparisons against trunc with comparisons against IV. |
578 | 13.0k | for (auto *ICI : ICmpUsers) { |
579 | 13.0k | bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0)); |
580 | 13.0k | auto *Op1 = IsSwapped ? ICI->getOperand(0)16 : ICI->getOperand(1)12.9k ; |
581 | 13.0k | Instruction *Ext = nullptr; |
582 | 13.0k | // For signed/unsigned predicate, replace the old comparison with comparison |
583 | 13.0k | // of immediate IV against sext/zext of the invariant argument. If we can |
584 | 13.0k | // use either sext or zext (i.e. we are dealing with equality predicate), |
585 | 13.0k | // then prefer zext as a more canonical form. |
586 | 13.0k | // TODO: If we see a signed comparison which can be turned into unsigned, |
587 | 13.0k | // we can do it here for canonicalization purposes. |
588 | 13.0k | ICmpInst::Predicate Pred = ICI->getPredicate(); |
589 | 13.0k | if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred)16 ; |
590 | 13.0k | if (CanUseZExt(ICI)) { |
591 | 12.4k | assert(DoesZExtCollapse && "Unprofitable zext?"); |
592 | 12.4k | Ext = new ZExtInst(Op1, IVTy, "zext", ICI); |
593 | 12.4k | Pred = ICmpInst::getUnsignedPredicate(Pred); |
594 | 12.4k | } else { |
595 | 543 | assert(DoesSExtCollapse && "Unprofitable sext?"); |
596 | 543 | Ext = new SExtInst(Op1, IVTy, "sext", ICI); |
597 | 543 | assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!"); |
598 | 543 | } |
599 | 13.0k | bool Changed; |
600 | 13.0k | L->makeLoopInvariant(Ext, Changed); |
601 | 13.0k | (void)Changed; |
602 | 13.0k | ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext); |
603 | 13.0k | ICI->replaceAllUsesWith(NewICI); |
604 | 13.0k | DeadInsts.emplace_back(ICI); |
605 | 13.0k | } |
606 | 13.0k | |
607 | 13.0k | // Trunc no longer needed. |
608 | 13.0k | TI->replaceAllUsesWith(UndefValue::get(TI->getType())); |
609 | 13.0k | DeadInsts.emplace_back(TI); |
610 | 13.0k | return true; |
611 | 34.1k | } |
612 | | |
613 | | /// Eliminate an operation that consumes a simple IV and has no observable |
614 | | /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable, |
615 | | /// but UseInst may not be. |
616 | | bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst, |
617 | 1.33M | Instruction *IVOperand) { |
618 | 1.33M | if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { |
619 | 207k | eliminateIVComparison(ICmp, IVOperand); |
620 | 207k | return true; |
621 | 207k | } |
622 | 1.12M | if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) { |
623 | 255k | bool IsSRem = Bin->getOpcode() == Instruction::SRem; |
624 | 255k | if (IsSRem || Bin->getOpcode() == Instruction::URem255k ) { |
625 | 593 | simplifyIVRemainder(Bin, IVOperand, IsSRem); |
626 | 593 | return true; |
627 | 593 | } |
628 | 255k | |
629 | 255k | if (Bin->getOpcode() == Instruction::SDiv) |
630 | 304 | return eliminateSDiv(Bin); |
631 | 1.12M | } |
632 | 1.12M | |
633 | 1.12M | if (auto *WO = dyn_cast<WithOverflowInst>(UseInst)) |
634 | 6 | if (eliminateOverflowIntrinsic(WO)) |
635 | 3 | return true; |
636 | 1.12M | |
637 | 1.12M | if (auto *SI = dyn_cast<SaturatingInst>(UseInst)) |
638 | 7 | if (eliminateSaturatingIntrinsic(SI)) |
639 | 4 | return true; |
640 | 1.12M | |
641 | 1.12M | if (auto *TI = dyn_cast<TruncInst>(UseInst)) |
642 | 37.7k | if (eliminateTrunc(TI)) |
643 | 13.0k | return true; |
644 | 1.11M | |
645 | 1.11M | if (eliminateIdentitySCEV(UseInst, IVOperand)) |
646 | 317 | return true; |
647 | 1.10M | |
648 | 1.10M | return false; |
649 | 1.10M | } |
650 | | |
651 | 177 | static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) { |
652 | 177 | if (auto *BB = L->getLoopPreheader()) |
653 | 177 | return BB->getTerminator(); |
654 | 0 | |
655 | 0 | return Hint; |
656 | 0 | } |
657 | | |
658 | | /// Replace the UseInst with a constant if possible. |
659 | 1.33M | bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) { |
660 | 1.33M | if (!SE->isSCEVable(I->getType())) |
661 | 126k | return false; |
662 | 1.20M | |
663 | 1.20M | // Get the symbolic expression for this instruction. |
664 | 1.20M | const SCEV *S = SE->getSCEV(I); |
665 | 1.20M | |
666 | 1.20M | if (!SE->isLoopInvariant(S, L)) |
667 | 1.20M | return false; |
668 | 177 | |
669 | 177 | // Do not generate something ridiculous even if S is loop invariant. |
670 | 177 | if (Rewriter.isHighCostExpansion(S, L, I)) |
671 | 0 | return false; |
672 | 177 | |
673 | 177 | auto *IP = GetLoopInvariantInsertPosition(L, I); |
674 | 177 | auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP); |
675 | 177 | |
676 | 177 | I->replaceAllUsesWith(Invariant); |
677 | 177 | LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I |
678 | 177 | << " with loop invariant: " << *S << '\n'); |
679 | 177 | ++NumFoldedUser; |
680 | 177 | Changed = true; |
681 | 177 | DeadInsts.emplace_back(I); |
682 | 177 | return true; |
683 | 177 | } |
684 | | |
685 | | /// Eliminate any operation that SCEV can prove is an identity function. |
686 | | bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst, |
687 | 1.11M | Instruction *IVOperand) { |
688 | 1.11M | if (!SE->isSCEVable(UseInst->getType()) || |
689 | 1.11M | (UseInst->getType() != IVOperand->getType())983k || |
690 | 1.11M | (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))406k ) |
691 | 1.10M | return false; |
692 | 317 | |
693 | 317 | // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the |
694 | 317 | // dominator tree, even if X is an operand to Y. For instance, in |
695 | 317 | // |
696 | 317 | // %iv = phi i32 {0,+,1} |
697 | 317 | // br %cond, label %left, label %merge |
698 | 317 | // |
699 | 317 | // left: |
700 | 317 | // %X = add i32 %iv, 0 |
701 | 317 | // br label %merge |
702 | 317 | // |
703 | 317 | // merge: |
704 | 317 | // %M = phi (%X, %iv) |
705 | 317 | // |
706 | 317 | // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and |
707 | 317 | // %M.replaceAllUsesWith(%X) would be incorrect. |
708 | 317 | |
709 | 317 | if (isa<PHINode>(UseInst)) |
710 | 15 | // If UseInst is not a PHI node then we know that IVOperand dominates |
711 | 15 | // UseInst directly from the legality of SSA. |
712 | 15 | if (!DT || !DT->dominates(IVOperand, UseInst)) |
713 | 0 | return false; |
714 | 317 | |
715 | 317 | if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand)) |
716 | 0 | return false; |
717 | 317 | |
718 | 317 | LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); |
719 | 317 | |
720 | 317 | UseInst->replaceAllUsesWith(IVOperand); |
721 | 317 | ++NumElimIdentity; |
722 | 317 | Changed = true; |
723 | 317 | DeadInsts.emplace_back(UseInst); |
724 | 317 | return true; |
725 | 317 | } |
726 | | |
727 | | /// Annotate BO with nsw / nuw if it provably does not signed-overflow / |
728 | | /// unsigned-overflow. Returns true if anything changed, false otherwise. |
729 | | bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO, |
730 | 240k | Value *IVOperand) { |
731 | 240k | // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`. |
732 | 240k | if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap()141k ) |
733 | 123k | return false; |
734 | 116k | |
735 | 116k | if (BO->getOpcode() != Instruction::Add && |
736 | 116k | BO->getOpcode() != Instruction::Sub25.7k && |
737 | 116k | BO->getOpcode() != Instruction::Mul14.2k ) |
738 | 7.97k | return false; |
739 | 108k | |
740 | 108k | const SCEV *LHS = SE->getSCEV(BO->getOperand(0)); |
741 | 108k | const SCEV *RHS = SE->getSCEV(BO->getOperand(1)); |
742 | 108k | bool Changed = false; |
743 | 108k | |
744 | 108k | if (!BO->hasNoUnsignedWrap() && |
745 | 108k | willNotOverflow(SE, BO->getOpcode(), /* Signed */ false, LHS, RHS)90.7k ) { |
746 | 5.03k | BO->setHasNoUnsignedWrap(); |
747 | 5.03k | SE->forgetValue(BO); |
748 | 5.03k | Changed = true; |
749 | 5.03k | } |
750 | 108k | |
751 | 108k | if (!BO->hasNoSignedWrap() && |
752 | 108k | willNotOverflow(SE, BO->getOpcode(), /* Signed */ true, LHS, RHS)63.8k ) { |
753 | 6.96k | BO->setHasNoSignedWrap(); |
754 | 6.96k | SE->forgetValue(BO); |
755 | 6.96k | Changed = true; |
756 | 6.96k | } |
757 | 108k | |
758 | 108k | return Changed; |
759 | 108k | } |
760 | | |
761 | | /// Annotate the Shr in (X << IVOperand) >> C as exact using the |
762 | | /// information from the IV's range. Returns true if anything changed, false |
763 | | /// otherwise. |
764 | | bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO, |
765 | 8.56k | Value *IVOperand) { |
766 | 8.56k | using namespace llvm::PatternMatch; |
767 | 8.56k | |
768 | 8.56k | if (BO->getOpcode() == Instruction::Shl) { |
769 | 8.56k | bool Changed = false; |
770 | 8.56k | ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand)); |
771 | 10.4k | for (auto *U : BO->users()) { |
772 | 10.4k | const APInt *C; |
773 | 10.4k | if (match(U, |
774 | 10.4k | m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) || |
775 | 10.4k | match(U, |
776 | 10.4k | m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) { |
777 | 9 | BinaryOperator *Shr = cast<BinaryOperator>(U); |
778 | 9 | if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) { |
779 | 7 | Shr->setIsExact(true); |
780 | 7 | Changed = true; |
781 | 7 | } |
782 | 9 | } |
783 | 10.4k | } |
784 | 8.56k | return Changed; |
785 | 8.56k | } |
786 | 0 | |
787 | 0 | return false; |
788 | 0 | } |
789 | | |
790 | | /// Add all uses of Def to the current IV's worklist. |
791 | | static void pushIVUsers( |
792 | | Instruction *Def, Loop *L, |
793 | | SmallPtrSet<Instruction*,16> &Simplified, |
794 | 1.00M | SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) { |
795 | 1.00M | |
796 | 2.37M | for (User *U : Def->users()) { |
797 | 2.37M | Instruction *UI = cast<Instruction>(U); |
798 | 2.37M | |
799 | 2.37M | // Avoid infinite or exponential worklist processing. |
800 | 2.37M | // Also ensure unique worklist users. |
801 | 2.37M | // If Def is a LoopPhi, it may not be in the Simplified set, so check for |
802 | 2.37M | // self edges first. |
803 | 2.37M | if (UI == Def) |
804 | 12 | continue; |
805 | 2.37M | |
806 | 2.37M | // Only change the current Loop, do not change the other parts (e.g. other |
807 | 2.37M | // Loops). |
808 | 2.37M | if (!L->contains(UI)) |
809 | 74.8k | continue; |
810 | 2.30M | |
811 | 2.30M | // Do not push the same instruction more than once. |
812 | 2.30M | if (!Simplified.insert(UI).second) |
813 | 755k | continue; |
814 | 1.54M | |
815 | 1.54M | SimpleIVUsers.push_back(std::make_pair(UI, Def)); |
816 | 1.54M | } |
817 | 1.00M | } |
818 | | |
819 | | /// Return true if this instruction generates a simple SCEV |
820 | | /// expression in terms of that IV. |
821 | | /// |
822 | | /// This is similar to IVUsers' isInteresting() but processes each instruction |
823 | | /// non-recursively when the operand is already known to be a simpleIVUser. |
824 | | /// |
825 | 983k | static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) { |
826 | 983k | if (!SE->isSCEVable(I->getType())) |
827 | 125k | return false; |
828 | 858k | |
829 | 858k | // Get the symbolic expression for this instruction. |
830 | 858k | const SCEV *S = SE->getSCEV(I); |
831 | 858k | |
832 | 858k | // Only consider affine recurrences. |
833 | 858k | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S); |
834 | 858k | if (AR && AR->getLoop() == L471k ) |
835 | 459k | return true; |
836 | 399k | |
837 | 399k | return false; |
838 | 399k | } |
839 | | |
840 | | /// Iteratively perform simplification on a worklist of users |
841 | | /// of the specified induction variable. Each successive simplification may push |
842 | | /// more users which may themselves be candidates for simplification. |
843 | | /// |
844 | | /// This algorithm does not require IVUsers analysis. Instead, it simplifies |
845 | | /// instructions in-place during analysis. Rather than rewriting induction |
846 | | /// variables bottom-up from their users, it transforms a chain of IVUsers |
847 | | /// top-down, updating the IR only when it encounters a clear optimization |
848 | | /// opportunity. |
849 | | /// |
850 | | /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers. |
851 | | /// |
852 | 326k | void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) { |
853 | 326k | if (!SE->isSCEVable(CurrIV->getType())) |
854 | 8.60k | return; |
855 | 317k | |
856 | 317k | // Instructions processed by SimplifyIndvar for CurrIV. |
857 | 317k | SmallPtrSet<Instruction*,16> Simplified; |
858 | 317k | |
859 | 317k | // Use-def pairs if IV users waiting to be processed for CurrIV. |
860 | 317k | SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers; |
861 | 317k | |
862 | 317k | // Push users of the current LoopPhi. In rare cases, pushIVUsers may be |
863 | 317k | // called multiple times for the same LoopPhi. This is the proper thing to |
864 | 317k | // do for loop header phis that use each other. |
865 | 317k | pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers); |
866 | 317k | |
867 | 1.86M | while (!SimpleIVUsers.empty()) { |
868 | 1.54M | std::pair<Instruction*, Instruction*> UseOper = |
869 | 1.54M | SimpleIVUsers.pop_back_val(); |
870 | 1.54M | Instruction *UseInst = UseOper.first; |
871 | 1.54M | |
872 | 1.54M | // If a user of the IndVar is trivially dead, we prefer just to mark it dead |
873 | 1.54M | // rather than try to do some complex analysis or transformation (such as |
874 | 1.54M | // widening) basing on it. |
875 | 1.54M | // TODO: Propagate TLI and pass it here to handle more cases. |
876 | 1.54M | if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) { |
877 | 11.1k | DeadInsts.emplace_back(UseInst); |
878 | 11.1k | continue; |
879 | 11.1k | } |
880 | 1.53M | |
881 | 1.53M | // Bypass back edges to avoid extra work. |
882 | 1.53M | if (UseInst == CurrIV) continue202k ; |
883 | 1.33M | |
884 | 1.33M | // Try to replace UseInst with a loop invariant before any other |
885 | 1.33M | // simplifications. |
886 | 1.33M | if (replaceIVUserWithLoopInvariant(UseInst)) |
887 | 177 | continue; |
888 | 1.33M | |
889 | 1.33M | Instruction *IVOperand = UseOper.second; |
890 | 1.33M | for (unsigned N = 0; IVOperand; ++N13 ) { |
891 | 1.33M | assert(N <= Simplified.size() && "runaway iteration"); |
892 | 1.33M | |
893 | 1.33M | Value *NewOper = foldIVUser(UseInst, IVOperand); |
894 | 1.33M | if (!NewOper) |
895 | 1.33M | break; // done folding |
896 | 13 | IVOperand = dyn_cast<Instruction>(NewOper); |
897 | 13 | } |
898 | 1.33M | if (!IVOperand) |
899 | 0 | continue; |
900 | 1.33M | |
901 | 1.33M | if (eliminateIVUser(UseInst, IVOperand)) { |
902 | 221k | pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers); |
903 | 221k | continue; |
904 | 221k | } |
905 | 1.11M | |
906 | 1.11M | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) { |
907 | 255k | if ((isa<OverflowingBinaryOperator>(BO) && |
908 | 255k | strengthenOverflowingOperation(BO, IVOperand)240k ) || |
909 | 255k | (246k isa<ShlOperator>(BO)246k && strengthenRightShift(BO, IVOperand)8.56k )) { |
910 | 8.71k | // re-queue uses of the now modified binary operator and fall |
911 | 8.71k | // through to the checks that remain. |
912 | 8.71k | pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers); |
913 | 8.71k | } |
914 | 255k | } |
915 | 1.11M | |
916 | 1.11M | CastInst *Cast = dyn_cast<CastInst>(UseInst); |
917 | 1.11M | if (V && Cast1.04M ) { |
918 | 126k | V->visitCast(Cast); |
919 | 126k | continue; |
920 | 126k | } |
921 | 983k | if (isSimpleIVUser(UseInst, L, SE)) { |
922 | 459k | pushIVUsers(UseInst, L, Simplified, SimpleIVUsers); |
923 | 459k | } |
924 | 983k | } |
925 | 317k | } |
926 | | |
927 | | namespace llvm { |
928 | | |
929 | 0 | void IVVisitor::anchor() { } |
930 | | |
931 | | /// Simplify instructions that use this induction variable |
932 | | /// by using ScalarEvolution to analyze the IV's recurrence. |
933 | | bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, |
934 | | LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead, |
935 | 326k | SCEVExpander &Rewriter, IVVisitor *V) { |
936 | 326k | SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Rewriter, |
937 | 326k | Dead); |
938 | 326k | SIV.simplifyUsers(CurrIV, V); |
939 | 326k | return SIV.hasChanged(); |
940 | 326k | } |
941 | | |
942 | | /// Simplify users of induction variables within this |
943 | | /// loop. This does not actually change or add IVs. |
944 | | bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, |
945 | 1.82k | LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead) { |
946 | 1.82k | SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars"); |
947 | | #ifndef NDEBUG |
948 | | Rewriter.setDebugType(DEBUG_TYPE); |
949 | | #endif |
950 | | bool Changed = false; |
951 | 5.84k | for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I4.01k ) { |
952 | 4.01k | Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead, Rewriter); |
953 | 4.01k | } |
954 | 1.82k | return Changed; |
955 | 1.82k | } |
956 | | |
957 | | } // namespace llvm |