1 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
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
7 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
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/IR/DataLayout.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/IRBuilder.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/PatternMatch.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Transforms/Utils/Local.h"
29 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
33 #define DEBUG_TYPE "indvars"
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");
41 "Number of IV signed division operations converted to unsigned division");
44 "Number of IV signed remainder operations converted to unsigned remainder");
45 STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");
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 {
57 const TargetTransformInfo *TTI;
58 SCEVExpander &Rewriter;
59 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
64 SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
65 LoopInfo *LI, const TargetTransformInfo *TTI,
66 SCEVExpander &Rewriter,
67 SmallVectorImpl<WeakTrackingVH> &Dead)
68 : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),
69 DeadInsts(Dead), Changed(false) {
70 assert(LI && "IV simplification requires LoopInfo");
73 bool hasChanged() const { return Changed; }
75 /// Iteratively perform simplification on a worklist of users of the
76 /// specified induction variable. This is the top-level driver that applies
77 /// all simplifications to users of an IV.
78 void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
80 Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
82 bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
83 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
85 bool eliminateOverflowIntrinsic(WithOverflowInst *WO);
86 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);
87 bool eliminateTrunc(TruncInst *TI);
88 bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
89 bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
90 void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
91 void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
93 void replaceRemWithNumerator(BinaryOperator *Rem);
94 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
95 void replaceSRemWithURem(BinaryOperator *Rem);
96 bool eliminateSDiv(BinaryOperator *SDiv);
97 bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
98 bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
102 /// Fold an IV operand into its use. This removes increments of an
103 /// aligned IV when used by a instruction that ignores the low bits.
105 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
107 /// Return the operand of IVOperand for this induction variable if IVOperand can
108 /// be folded (in case more folding opportunities have been exposed).
109 /// Otherwise return null.
110 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
111 Value *IVSrc = nullptr;
112 const unsigned OperIdx = 0;
113 const SCEV *FoldedExpr = nullptr;
114 bool MustDropExactFlag = false;
115 switch (UseInst->getOpcode()) {
118 case Instruction::UDiv:
119 case Instruction::LShr:
120 // We're only interested in the case where we know something about
121 // the numerator and have a constant denominator.
122 if (IVOperand != UseInst->getOperand(OperIdx) ||
123 !isa<ConstantInt>(UseInst->getOperand(1)))
126 // Attempt to fold a binary operator with constant operand.
127 // e.g. ((I + 1) >> 2) => I >> 2
128 if (!isa<BinaryOperator>(IVOperand)
129 || !isa<ConstantInt>(IVOperand->getOperand(1)))
132 IVSrc = IVOperand->getOperand(0);
133 // IVSrc must be the (SCEVable) IV, since the other operand is const.
134 assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
136 ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
137 if (UseInst->getOpcode() == Instruction::LShr) {
138 // Get a constant for the divisor. See createSCEV.
139 uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
140 if (D->getValue().uge(BitWidth))
143 D = ConstantInt::get(UseInst->getContext(),
144 APInt::getOneBitSet(BitWidth, D->getZExtValue()));
146 FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
147 // We might have 'exact' flag set at this point which will no longer be
148 // correct after we make the replacement.
149 if (UseInst->isExact() &&
150 SE->getSCEV(IVSrc) != SE->getMulExpr(FoldedExpr, SE->getSCEV(D)))
151 MustDropExactFlag = true;
153 // We have something that might fold it's operand. Compare SCEVs.
154 if (!SE->isSCEVable(UseInst->getType()))
157 // Bypass the operand if SCEV can prove it has no effect.
158 if (SE->getSCEV(UseInst) != FoldedExpr)
161 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
162 << " -> " << *UseInst << '\n');
164 UseInst->setOperand(OperIdx, IVSrc);
165 assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
167 if (MustDropExactFlag)
168 UseInst->dropPoisonGeneratingFlags();
172 if (IVOperand->use_empty())
173 DeadInsts.emplace_back(IVOperand);
177 bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
179 unsigned IVOperIdx = 0;
180 ICmpInst::Predicate Pred = ICmp->getPredicate();
181 if (IVOperand != ICmp->getOperand(0)) {
183 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
185 Pred = ICmpInst::getSwappedPredicate(Pred);
188 // Get the SCEVs for the ICmp operands (in the specific context of the
190 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
191 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
192 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
194 ICmpInst::Predicate InvariantPredicate;
195 const SCEV *InvariantLHS, *InvariantRHS;
197 auto *PN = dyn_cast<PHINode>(IVOperand);
200 if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
201 InvariantLHS, InvariantRHS))
204 // Rewrite the comparison to a loop invariant comparison if it can be done
205 // cheaply, where cheaply means "we don't need to emit any new
208 SmallDenseMap<const SCEV*, Value*> CheapExpansions;
209 CheapExpansions[S] = ICmp->getOperand(IVOperIdx);
210 CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx);
212 // TODO: Support multiple entry loops? (We currently bail out of these in
213 // the IndVarSimplify pass)
214 if (auto *BB = L->getLoopPredecessor()) {
215 const int Idx = PN->getBasicBlockIndex(BB);
217 Value *Incoming = PN->getIncomingValue(Idx);
218 const SCEV *IncomingS = SE->getSCEV(Incoming);
219 CheapExpansions[IncomingS] = Incoming;
222 Value *NewLHS = CheapExpansions[InvariantLHS];
223 Value *NewRHS = CheapExpansions[InvariantRHS];
226 if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
227 NewLHS = ConstLHS->getValue();
229 if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
230 NewRHS = ConstRHS->getValue();
232 if (!NewLHS || !NewRHS)
233 // We could not find an existing value to replace either LHS or RHS.
234 // Generating new instructions has subtler tradeoffs, so avoid doing that
238 LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
239 ICmp->setPredicate(InvariantPredicate);
240 ICmp->setOperand(0, NewLHS);
241 ICmp->setOperand(1, NewRHS);
245 /// SimplifyIVUsers helper for eliminating useless
246 /// comparisons against an induction variable.
247 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
248 unsigned IVOperIdx = 0;
249 ICmpInst::Predicate Pred = ICmp->getPredicate();
250 ICmpInst::Predicate OriginalPred = Pred;
251 if (IVOperand != ICmp->getOperand(0)) {
253 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
255 Pred = ICmpInst::getSwappedPredicate(Pred);
258 // Get the SCEVs for the ICmp operands (in the specific context of the
260 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
261 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
262 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
264 // If the condition is always true or always false, replace it with
266 if (SE->isKnownPredicate(Pred, S, X)) {
267 ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
268 DeadInsts.emplace_back(ICmp);
269 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
270 } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
271 ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
272 DeadInsts.emplace_back(ICmp);
273 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
274 } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
275 // fallthrough to end of function
276 } else if (ICmpInst::isSigned(OriginalPred) &&
277 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
278 // If we were unable to make anything above, all we can is to canonicalize
279 // the comparison hoping that it will open the doors for other
280 // optimizations. If we find out that we compare two non-negative values,
281 // we turn the instruction's predicate to its unsigned version. Note that
282 // we cannot rely on Pred here unless we check if we have swapped it.
283 assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
284 LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp
286 ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
294 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
295 // Get the SCEVs for the ICmp operands.
296 auto *N = SE->getSCEV(SDiv->getOperand(0));
297 auto *D = SE->getSCEV(SDiv->getOperand(1));
299 // Simplify unnecessary loops away.
300 const Loop *L = LI->getLoopFor(SDiv->getParent());
301 N = SE->getSCEVAtScope(N, L);
302 D = SE->getSCEVAtScope(D, L);
304 // Replace sdiv by udiv if both of the operands are non-negative
305 if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
306 auto *UDiv = BinaryOperator::Create(
307 BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
308 SDiv->getName() + ".udiv", SDiv);
309 UDiv->setIsExact(SDiv->isExact());
310 SDiv->replaceAllUsesWith(UDiv);
311 LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
314 DeadInsts.push_back(SDiv);
321 // i %s n -> i %u n if i >= 0 and n >= 0
322 void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
323 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
324 auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
325 Rem->getName() + ".urem", Rem);
326 Rem->replaceAllUsesWith(URem);
327 LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
330 DeadInsts.emplace_back(Rem);
333 // i % n --> i if i is in [0,n).
334 void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
335 Rem->replaceAllUsesWith(Rem->getOperand(0));
336 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
339 DeadInsts.emplace_back(Rem);
342 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
343 void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
344 auto *T = Rem->getType();
345 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
346 ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
348 SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
349 Rem->replaceAllUsesWith(Sel);
350 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
353 DeadInsts.emplace_back(Rem);
356 /// SimplifyIVUsers helper for eliminating useless remainder operations
357 /// operating on an induction variable or replacing srem by urem.
358 void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
360 auto *NValue = Rem->getOperand(0);
361 auto *DValue = Rem->getOperand(1);
362 // We're only interested in the case where we know something about
363 // the numerator, unless it is a srem, because we want to replace srem by urem
365 bool UsedAsNumerator = IVOperand == NValue;
366 if (!UsedAsNumerator && !IsSigned)
369 const SCEV *N = SE->getSCEV(NValue);
371 // Simplify unnecessary loops away.
372 const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
373 N = SE->getSCEVAtScope(N, ICmpLoop);
375 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);
377 // Do not proceed if the Numerator may be negative
378 if (!IsNumeratorNonNegative)
381 const SCEV *D = SE->getSCEV(DValue);
382 D = SE->getSCEVAtScope(D, ICmpLoop);
384 if (UsedAsNumerator) {
385 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
386 if (SE->isKnownPredicate(LT, N, D)) {
387 replaceRemWithNumerator(Rem);
391 auto *T = Rem->getType();
392 const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
393 if (SE->isKnownPredicate(LT, NLessOne, D)) {
394 replaceRemWithNumeratorOrZero(Rem);
399 // Try to replace SRem with URem, if both N and D are known non-negative.
400 // Since we had already check N, we only need to check D now
401 if (!IsSigned || !SE->isKnownNonNegative(D))
404 replaceSRemWithURem(Rem);
407 static bool willNotOverflow(ScalarEvolution *SE, Instruction::BinaryOps BinOp,
408 bool Signed, const SCEV *LHS, const SCEV *RHS) {
409 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
410 SCEV::NoWrapFlags, unsigned);
413 llvm_unreachable("Unsupported binary op");
414 case Instruction::Add:
415 Operation = &ScalarEvolution::getAddExpr;
417 case Instruction::Sub:
418 Operation = &ScalarEvolution::getMinusSCEV;
420 case Instruction::Mul:
421 Operation = &ScalarEvolution::getMulExpr;
425 const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) =
426 Signed ? &ScalarEvolution::getSignExtendExpr
427 : &ScalarEvolution::getZeroExtendExpr;
429 // Check ext(LHS op RHS) == ext(LHS) op ext(RHS)
430 auto *NarrowTy = cast<IntegerType>(LHS->getType());
432 IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
435 (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0),
438 (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0),
439 (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0);
443 bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
444 const SCEV *LHS = SE->getSCEV(WO->getLHS());
445 const SCEV *RHS = SE->getSCEV(WO->getRHS());
446 if (!willNotOverflow(SE, WO->getBinaryOp(), WO->isSigned(), LHS, RHS))
449 // Proved no overflow, nuke the overflow check and, if possible, the overflow
450 // intrinsic as well.
452 BinaryOperator *NewResult = BinaryOperator::Create(
453 WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO);
456 NewResult->setHasNoSignedWrap(true);
458 NewResult->setHasNoUnsignedWrap(true);
460 SmallVector<ExtractValueInst *, 4> ToDelete;
462 for (auto *U : WO->users()) {
463 if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
464 if (EVI->getIndices()[0] == 1)
465 EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));
467 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
468 EVI->replaceAllUsesWith(NewResult);
470 ToDelete.push_back(EVI);
474 for (auto *EVI : ToDelete)
475 EVI->eraseFromParent();
478 WO->eraseFromParent();
483 bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
484 const SCEV *LHS = SE->getSCEV(SI->getLHS());
485 const SCEV *RHS = SE->getSCEV(SI->getRHS());
486 if (!willNotOverflow(SE, SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
489 BinaryOperator *BO = BinaryOperator::Create(
490 SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
492 BO->setHasNoSignedWrap();
494 BO->setHasNoUnsignedWrap();
496 SI->replaceAllUsesWith(BO);
497 DeadInsts.emplace_back(SI);
502 bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
503 // It is always legal to replace
504 // icmp <pred> i32 trunc(iv), n
506 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
508 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
509 // Or with either of these if pred is an equality predicate.
511 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
512 // every comparison which uses trunc, it means that we can replace each of
513 // them with comparison of iv against sext/zext(n). We no longer need trunc
516 // TODO: Should we do this if we can widen *some* comparisons, but not all
517 // of them? Sometimes it is enough to enable other optimizations, but the
518 // trunc instruction will stay in the loop.
519 Value *IV = TI->getOperand(0);
520 Type *IVTy = IV->getType();
521 const SCEV *IVSCEV = SE->getSCEV(IV);
522 const SCEV *TISCEV = SE->getSCEV(TI);
524 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
526 bool DoesSExtCollapse = false;
527 bool DoesZExtCollapse = false;
528 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
529 DoesSExtCollapse = true;
530 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
531 DoesZExtCollapse = true;
533 // If neither sext nor zext does collapse, it is not profitable to do any
535 if (!DoesSExtCollapse && !DoesZExtCollapse)
538 // Collect users of the trunc that look like comparisons against invariants.
539 // Bail if we find something different.
540 SmallVector<ICmpInst *, 4> ICmpUsers;
541 for (auto *U : TI->users()) {
542 // We don't care about users in unreachable blocks.
543 if (isa<Instruction>(U) &&
544 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
546 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
547 if (!ICI) return false;
548 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
549 if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&
550 !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))
552 // If we cannot get rid of trunc, bail.
553 if (ICI->isSigned() && !DoesSExtCollapse)
555 if (ICI->isUnsigned() && !DoesZExtCollapse)
557 // For equality, either signed or unsigned works.
558 ICmpUsers.push_back(ICI);
561 auto CanUseZExt = [&](ICmpInst *ICI) {
562 // Unsigned comparison can be widened as unsigned.
563 if (ICI->isUnsigned())
565 // Is it profitable to do zext?
566 if (!DoesZExtCollapse)
568 // For equality, we can safely zext both parts.
569 if (ICI->isEquality())
571 // Otherwise we can only use zext when comparing two non-negative or two
572 // negative values. But in practice, we will never pass DoesZExtCollapse
573 // check for a negative value, because zext(trunc(x)) is non-negative. So
574 // it only make sense to check for non-negativity here.
575 const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
576 const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
577 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
579 // Replace all comparisons against trunc with comparisons against IV.
580 for (auto *ICI : ICmpUsers) {
581 bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
582 auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);
583 Instruction *Ext = nullptr;
584 // For signed/unsigned predicate, replace the old comparison with comparison
585 // of immediate IV against sext/zext of the invariant argument. If we can
586 // use either sext or zext (i.e. we are dealing with equality predicate),
587 // then prefer zext as a more canonical form.
588 // TODO: If we see a signed comparison which can be turned into unsigned,
589 // we can do it here for canonicalization purposes.
590 ICmpInst::Predicate Pred = ICI->getPredicate();
591 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
592 if (CanUseZExt(ICI)) {
593 assert(DoesZExtCollapse && "Unprofitable zext?");
594 Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
595 Pred = ICmpInst::getUnsignedPredicate(Pred);
597 assert(DoesSExtCollapse && "Unprofitable sext?");
598 Ext = new SExtInst(Op1, IVTy, "sext", ICI);
599 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
602 L->makeLoopInvariant(Ext, Changed);
604 ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
605 ICI->replaceAllUsesWith(NewICI);
606 DeadInsts.emplace_back(ICI);
609 // Trunc no longer needed.
610 TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
611 DeadInsts.emplace_back(TI);
615 /// Eliminate an operation that consumes a simple IV and has no observable
616 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
617 /// but UseInst may not be.
618 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
619 Instruction *IVOperand) {
620 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
621 eliminateIVComparison(ICmp, IVOperand);
624 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
625 bool IsSRem = Bin->getOpcode() == Instruction::SRem;
626 if (IsSRem || Bin->getOpcode() == Instruction::URem) {
627 simplifyIVRemainder(Bin, IVOperand, IsSRem);
631 if (Bin->getOpcode() == Instruction::SDiv)
632 return eliminateSDiv(Bin);
635 if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
636 if (eliminateOverflowIntrinsic(WO))
639 if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
640 if (eliminateSaturatingIntrinsic(SI))
643 if (auto *TI = dyn_cast<TruncInst>(UseInst))
644 if (eliminateTrunc(TI))
647 if (eliminateIdentitySCEV(UseInst, IVOperand))
653 static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
654 if (auto *BB = L->getLoopPreheader())
655 return BB->getTerminator();
660 /// Replace the UseInst with a loop invariant expression if it is safe.
661 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
662 if (!SE->isSCEVable(I->getType()))
665 // Get the symbolic expression for this instruction.
666 const SCEV *S = SE->getSCEV(I);
668 if (!SE->isLoopInvariant(S, L))
671 // Do not generate something ridiculous even if S is loop invariant.
672 if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
675 auto *IP = GetLoopInvariantInsertPosition(L, I);
677 if (!isSafeToExpandAt(S, IP, *SE)) {
678 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
679 << " with non-speculable loop invariant: " << *S << '\n');
683 auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
685 I->replaceAllUsesWith(Invariant);
686 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
687 << " with loop invariant: " << *S << '\n');
690 DeadInsts.emplace_back(I);
694 /// Eliminate any operation that SCEV can prove is an identity function.
695 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
696 Instruction *IVOperand) {
697 if (!SE->isSCEVable(UseInst->getType()) ||
698 (UseInst->getType() != IVOperand->getType()) ||
699 (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
702 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
703 // dominator tree, even if X is an operand to Y. For instance, in
705 // %iv = phi i32 {0,+,1}
706 // br %cond, label %left, label %merge
709 // %X = add i32 %iv, 0
713 // %M = phi (%X, %iv)
715 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
716 // %M.replaceAllUsesWith(%X) would be incorrect.
718 if (isa<PHINode>(UseInst))
719 // If UseInst is not a PHI node then we know that IVOperand dominates
720 // UseInst directly from the legality of SSA.
721 if (!DT || !DT->dominates(IVOperand, UseInst))
724 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
727 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
729 UseInst->replaceAllUsesWith(IVOperand);
732 DeadInsts.emplace_back(UseInst);
736 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
737 /// unsigned-overflow. Returns true if anything changed, false otherwise.
738 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
740 // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
741 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
744 if (BO->getOpcode() != Instruction::Add &&
745 BO->getOpcode() != Instruction::Sub &&
746 BO->getOpcode() != Instruction::Mul)
749 const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
750 const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
751 bool Changed = false;
753 if (!BO->hasNoUnsignedWrap() &&
754 willNotOverflow(SE, BO->getOpcode(), /* Signed */ false, LHS, RHS)) {
755 BO->setHasNoUnsignedWrap();
760 if (!BO->hasNoSignedWrap() &&
761 willNotOverflow(SE, BO->getOpcode(), /* Signed */ true, LHS, RHS)) {
762 BO->setHasNoSignedWrap();
770 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
771 /// information from the IV's range. Returns true if anything changed, false
773 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
775 using namespace llvm::PatternMatch;
777 if (BO->getOpcode() == Instruction::Shl) {
778 bool Changed = false;
779 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
780 for (auto *U : BO->users()) {
783 m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
785 m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
786 BinaryOperator *Shr = cast<BinaryOperator>(U);
787 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
788 Shr->setIsExact(true);
799 /// Add all uses of Def to the current IV's worklist.
800 static void pushIVUsers(
801 Instruction *Def, Loop *L,
802 SmallPtrSet<Instruction*,16> &Simplified,
803 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
805 for (User *U : Def->users()) {
806 Instruction *UI = cast<Instruction>(U);
808 // Avoid infinite or exponential worklist processing.
809 // Also ensure unique worklist users.
810 // If Def is a LoopPhi, it may not be in the Simplified set, so check for
815 // Only change the current Loop, do not change the other parts (e.g. other
817 if (!L->contains(UI))
820 // Do not push the same instruction more than once.
821 if (!Simplified.insert(UI).second)
824 SimpleIVUsers.push_back(std::make_pair(UI, Def));
828 /// Return true if this instruction generates a simple SCEV
829 /// expression in terms of that IV.
831 /// This is similar to IVUsers' isInteresting() but processes each instruction
832 /// non-recursively when the operand is already known to be a simpleIVUser.
834 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
835 if (!SE->isSCEVable(I->getType()))
838 // Get the symbolic expression for this instruction.
839 const SCEV *S = SE->getSCEV(I);
841 // Only consider affine recurrences.
842 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
843 if (AR && AR->getLoop() == L)
849 /// Iteratively perform simplification on a worklist of users
850 /// of the specified induction variable. Each successive simplification may push
851 /// more users which may themselves be candidates for simplification.
853 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
854 /// instructions in-place during analysis. Rather than rewriting induction
855 /// variables bottom-up from their users, it transforms a chain of IVUsers
856 /// top-down, updating the IR only when it encounters a clear optimization
859 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
861 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
862 if (!SE->isSCEVable(CurrIV->getType()))
865 // Instructions processed by SimplifyIndvar for CurrIV.
866 SmallPtrSet<Instruction*,16> Simplified;
868 // Use-def pairs if IV users waiting to be processed for CurrIV.
869 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
871 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
872 // called multiple times for the same LoopPhi. This is the proper thing to
873 // do for loop header phis that use each other.
874 pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
876 while (!SimpleIVUsers.empty()) {
877 std::pair<Instruction*, Instruction*> UseOper =
878 SimpleIVUsers.pop_back_val();
879 Instruction *UseInst = UseOper.first;
881 // If a user of the IndVar is trivially dead, we prefer just to mark it dead
882 // rather than try to do some complex analysis or transformation (such as
883 // widening) basing on it.
884 // TODO: Propagate TLI and pass it here to handle more cases.
885 if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
886 DeadInsts.emplace_back(UseInst);
890 // Bypass back edges to avoid extra work.
891 if (UseInst == CurrIV) continue;
893 // Try to replace UseInst with a loop invariant before any other
895 if (replaceIVUserWithLoopInvariant(UseInst))
898 Instruction *IVOperand = UseOper.second;
899 for (unsigned N = 0; IVOperand; ++N) {
900 assert(N <= Simplified.size() && "runaway iteration");
902 Value *NewOper = foldIVUser(UseInst, IVOperand);
904 break; // done folding
905 IVOperand = dyn_cast<Instruction>(NewOper);
910 if (eliminateIVUser(UseInst, IVOperand)) {
911 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
915 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
916 if ((isa<OverflowingBinaryOperator>(BO) &&
917 strengthenOverflowingOperation(BO, IVOperand)) ||
918 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
919 // re-queue uses of the now modified binary operator and fall
920 // through to the checks that remain.
921 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
925 CastInst *Cast = dyn_cast<CastInst>(UseInst);
930 if (isSimpleIVUser(UseInst, L, SE)) {
931 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
938 void IVVisitor::anchor() { }
940 /// Simplify instructions that use this induction variable
941 /// by using ScalarEvolution to analyze the IV's recurrence.
942 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
943 LoopInfo *LI, const TargetTransformInfo *TTI,
944 SmallVectorImpl<WeakTrackingVH> &Dead,
945 SCEVExpander &Rewriter, IVVisitor *V) {
946 SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,
948 SIV.simplifyUsers(CurrIV, V);
949 return SIV.hasChanged();
952 /// Simplify users of induction variables within this
953 /// loop. This does not actually change or add IVs.
954 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
955 LoopInfo *LI, const TargetTransformInfo *TTI,
956 SmallVectorImpl<WeakTrackingVH> &Dead) {
957 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
959 Rewriter.setDebugType(DEBUG_TYPE);
961 bool Changed = false;
962 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
964 simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);