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/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/IntrinsicInst.h"
23 #include "llvm/IR/PatternMatch.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Transforms/Utils/Local.h"
27 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
31 #define DEBUG_TYPE "indvars"
33 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
34 STATISTIC(NumElimOperand, "Number of IV operands folded into a use");
35 STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
36 STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");
39 "Number of IV signed division operations converted to unsigned division");
42 "Number of IV signed remainder operations converted to unsigned remainder");
43 STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");
46 /// This is a utility for simplifying induction variables
47 /// based on ScalarEvolution. It is the primary instrument of the
48 /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
49 /// other loop passes that preserve SCEV.
50 class SimplifyIndvar {
55 const TargetTransformInfo *TTI;
56 SCEVExpander &Rewriter;
57 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
62 SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
63 LoopInfo *LI, const TargetTransformInfo *TTI,
64 SCEVExpander &Rewriter,
65 SmallVectorImpl<WeakTrackingVH> &Dead)
66 : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),
68 assert(LI && "IV simplification requires LoopInfo");
71 bool hasChanged() const { return Changed; }
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);
78 Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
80 bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
81 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
82 bool replaceFloatIVWithIntegerIV(Instruction *UseInst);
84 bool eliminateOverflowIntrinsic(WithOverflowInst *WO);
85 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);
86 bool eliminateTrunc(TruncInst *TI);
87 bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
88 bool makeIVComparisonInvariant(ICmpInst *ICmp, Instruction *IVOperand);
89 void eliminateIVComparison(ICmpInst *ICmp, Instruction *IVOperand);
90 void simplifyIVRemainder(BinaryOperator *Rem, Instruction *IVOperand,
92 void replaceRemWithNumerator(BinaryOperator *Rem);
93 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
94 void replaceSRemWithURem(BinaryOperator *Rem);
95 bool eliminateSDiv(BinaryOperator *SDiv);
96 bool strengthenOverflowingOperation(BinaryOperator *OBO,
97 Instruction *IVOperand);
98 bool strengthenRightShift(BinaryOperator *BO, Instruction *IVOperand);
102 /// Find a point in code which dominates all given instructions. We can safely
103 /// assume that, whatever fact we can prove at the found point, this fact is
104 /// also true for each of the given instructions.
105 static Instruction *findCommonDominator(ArrayRef<Instruction *> Instructions,
107 Instruction *CommonDom = nullptr;
108 for (auto *Insn : Instructions)
109 if (!CommonDom || DT.dominates(Insn, CommonDom))
111 else if (!DT.dominates(CommonDom, Insn))
112 // If there is no dominance relation, use common dominator.
114 DT.findNearestCommonDominator(CommonDom->getParent(),
115 Insn->getParent())->getTerminator();
116 assert(CommonDom && "Common dominator not found?");
120 /// Fold an IV operand into its use. This removes increments of an
121 /// aligned IV when used by a instruction that ignores the low bits.
123 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
125 /// Return the operand of IVOperand for this induction variable if IVOperand can
126 /// be folded (in case more folding opportunities have been exposed).
127 /// Otherwise return null.
128 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
129 Value *IVSrc = nullptr;
130 const unsigned OperIdx = 0;
131 const SCEV *FoldedExpr = nullptr;
132 bool MustDropExactFlag = false;
133 switch (UseInst->getOpcode()) {
136 case Instruction::UDiv:
137 case Instruction::LShr:
138 // We're only interested in the case where we know something about
139 // the numerator and have a constant denominator.
140 if (IVOperand != UseInst->getOperand(OperIdx) ||
141 !isa<ConstantInt>(UseInst->getOperand(1)))
144 // Attempt to fold a binary operator with constant operand.
145 // e.g. ((I + 1) >> 2) => I >> 2
146 if (!isa<BinaryOperator>(IVOperand)
147 || !isa<ConstantInt>(IVOperand->getOperand(1)))
150 IVSrc = IVOperand->getOperand(0);
151 // IVSrc must be the (SCEVable) IV, since the other operand is const.
152 assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
154 ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
155 if (UseInst->getOpcode() == Instruction::LShr) {
156 // Get a constant for the divisor. See createSCEV.
157 uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
158 if (D->getValue().uge(BitWidth))
161 D = ConstantInt::get(UseInst->getContext(),
162 APInt::getOneBitSet(BitWidth, D->getZExtValue()));
164 const auto *LHS = SE->getSCEV(IVSrc);
165 const auto *RHS = SE->getSCEV(D);
166 FoldedExpr = SE->getUDivExpr(LHS, RHS);
167 // We might have 'exact' flag set at this point which will no longer be
168 // correct after we make the replacement.
169 if (UseInst->isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))
170 MustDropExactFlag = true;
172 // We have something that might fold it's operand. Compare SCEVs.
173 if (!SE->isSCEVable(UseInst->getType()))
176 // Bypass the operand if SCEV can prove it has no effect.
177 if (SE->getSCEV(UseInst) != FoldedExpr)
180 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
181 << " -> " << *UseInst << '\n');
183 UseInst->setOperand(OperIdx, IVSrc);
184 assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
186 if (MustDropExactFlag)
187 UseInst->dropPoisonGeneratingFlags();
191 if (IVOperand->use_empty())
192 DeadInsts.emplace_back(IVOperand);
196 bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
197 Instruction *IVOperand) {
198 unsigned IVOperIdx = 0;
199 ICmpInst::Predicate Pred = ICmp->getPredicate();
200 if (IVOperand != ICmp->getOperand(0)) {
202 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
204 Pred = ICmpInst::getSwappedPredicate(Pred);
207 // Get the SCEVs for the ICmp operands (in the specific context of the
209 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
210 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
211 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
213 auto *PN = dyn_cast<PHINode>(IVOperand);
216 auto LIP = SE->getLoopInvariantPredicate(Pred, S, X, L);
219 ICmpInst::Predicate InvariantPredicate = LIP->Pred;
220 const SCEV *InvariantLHS = LIP->LHS;
221 const SCEV *InvariantRHS = LIP->RHS;
223 // Rewrite the comparison to a loop invariant comparison if it can be done
224 // cheaply, where cheaply means "we don't need to emit any new
227 SmallDenseMap<const SCEV*, Value*> CheapExpansions;
228 CheapExpansions[S] = ICmp->getOperand(IVOperIdx);
229 CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx);
231 // TODO: Support multiple entry loops? (We currently bail out of these in
232 // the IndVarSimplify pass)
233 if (auto *BB = L->getLoopPredecessor()) {
234 const int Idx = PN->getBasicBlockIndex(BB);
236 Value *Incoming = PN->getIncomingValue(Idx);
237 const SCEV *IncomingS = SE->getSCEV(Incoming);
238 CheapExpansions[IncomingS] = Incoming;
241 Value *NewLHS = CheapExpansions[InvariantLHS];
242 Value *NewRHS = CheapExpansions[InvariantRHS];
245 if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
246 NewLHS = ConstLHS->getValue();
248 if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
249 NewRHS = ConstRHS->getValue();
251 if (!NewLHS || !NewRHS)
252 // We could not find an existing value to replace either LHS or RHS.
253 // Generating new instructions has subtler tradeoffs, so avoid doing that
257 LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
258 ICmp->setPredicate(InvariantPredicate);
259 ICmp->setOperand(0, NewLHS);
260 ICmp->setOperand(1, NewRHS);
264 /// SimplifyIVUsers helper for eliminating useless
265 /// comparisons against an induction variable.
266 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp,
267 Instruction *IVOperand) {
268 unsigned IVOperIdx = 0;
269 ICmpInst::Predicate Pred = ICmp->getPredicate();
270 ICmpInst::Predicate OriginalPred = Pred;
271 if (IVOperand != ICmp->getOperand(0)) {
273 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
275 Pred = ICmpInst::getSwappedPredicate(Pred);
278 // Get the SCEVs for the ICmp operands (in the specific context of the
280 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
281 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
282 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
284 // If the condition is always true or always false in the given context,
285 // replace it with a constant value.
286 SmallVector<Instruction *, 4> Users;
287 for (auto *U : ICmp->users())
288 Users.push_back(cast<Instruction>(U));
289 const Instruction *CtxI = findCommonDominator(Users, *DT);
290 if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {
291 ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));
292 DeadInsts.emplace_back(ICmp);
293 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
294 } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
295 // fallthrough to end of function
296 } else if (ICmpInst::isSigned(OriginalPred) &&
297 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
298 // If we were unable to make anything above, all we can is to canonicalize
299 // the comparison hoping that it will open the doors for other
300 // optimizations. If we find out that we compare two non-negative values,
301 // we turn the instruction's predicate to its unsigned version. Note that
302 // we cannot rely on Pred here unless we check if we have swapped it.
303 assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
304 LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp
306 ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
314 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
315 // Get the SCEVs for the ICmp operands.
316 auto *N = SE->getSCEV(SDiv->getOperand(0));
317 auto *D = SE->getSCEV(SDiv->getOperand(1));
319 // Simplify unnecessary loops away.
320 const Loop *L = LI->getLoopFor(SDiv->getParent());
321 N = SE->getSCEVAtScope(N, L);
322 D = SE->getSCEVAtScope(D, L);
324 // Replace sdiv by udiv if both of the operands are non-negative
325 if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
326 auto *UDiv = BinaryOperator::Create(
327 BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
328 SDiv->getName() + ".udiv", SDiv);
329 UDiv->setIsExact(SDiv->isExact());
330 SDiv->replaceAllUsesWith(UDiv);
331 LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
334 DeadInsts.push_back(SDiv);
341 // i %s n -> i %u n if i >= 0 and n >= 0
342 void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
343 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
344 auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
345 Rem->getName() + ".urem", Rem);
346 Rem->replaceAllUsesWith(URem);
347 LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
350 DeadInsts.emplace_back(Rem);
353 // i % n --> i if i is in [0,n).
354 void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
355 Rem->replaceAllUsesWith(Rem->getOperand(0));
356 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
359 DeadInsts.emplace_back(Rem);
362 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
363 void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
364 auto *T = Rem->getType();
365 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
366 ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
368 SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
369 Rem->replaceAllUsesWith(Sel);
370 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
373 DeadInsts.emplace_back(Rem);
376 /// SimplifyIVUsers helper for eliminating useless remainder operations
377 /// operating on an induction variable or replacing srem by urem.
378 void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,
379 Instruction *IVOperand,
381 auto *NValue = Rem->getOperand(0);
382 auto *DValue = Rem->getOperand(1);
383 // We're only interested in the case where we know something about
384 // the numerator, unless it is a srem, because we want to replace srem by urem
386 bool UsedAsNumerator = IVOperand == NValue;
387 if (!UsedAsNumerator && !IsSigned)
390 const SCEV *N = SE->getSCEV(NValue);
392 // Simplify unnecessary loops away.
393 const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
394 N = SE->getSCEVAtScope(N, ICmpLoop);
396 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);
398 // Do not proceed if the Numerator may be negative
399 if (!IsNumeratorNonNegative)
402 const SCEV *D = SE->getSCEV(DValue);
403 D = SE->getSCEVAtScope(D, ICmpLoop);
405 if (UsedAsNumerator) {
406 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
407 if (SE->isKnownPredicate(LT, N, D)) {
408 replaceRemWithNumerator(Rem);
412 auto *T = Rem->getType();
413 const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
414 if (SE->isKnownPredicate(LT, NLessOne, D)) {
415 replaceRemWithNumeratorOrZero(Rem);
420 // Try to replace SRem with URem, if both N and D are known non-negative.
421 // Since we had already check N, we only need to check D now
422 if (!IsSigned || !SE->isKnownNonNegative(D))
425 replaceSRemWithURem(Rem);
428 bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
429 const SCEV *LHS = SE->getSCEV(WO->getLHS());
430 const SCEV *RHS = SE->getSCEV(WO->getRHS());
431 if (!SE->willNotOverflow(WO->getBinaryOp(), WO->isSigned(), LHS, RHS))
434 // Proved no overflow, nuke the overflow check and, if possible, the overflow
435 // intrinsic as well.
437 BinaryOperator *NewResult = BinaryOperator::Create(
438 WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO);
441 NewResult->setHasNoSignedWrap(true);
443 NewResult->setHasNoUnsignedWrap(true);
445 SmallVector<ExtractValueInst *, 4> ToDelete;
447 for (auto *U : WO->users()) {
448 if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
449 if (EVI->getIndices()[0] == 1)
450 EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));
452 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
453 EVI->replaceAllUsesWith(NewResult);
455 ToDelete.push_back(EVI);
459 for (auto *EVI : ToDelete)
460 EVI->eraseFromParent();
463 WO->eraseFromParent();
469 bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
470 const SCEV *LHS = SE->getSCEV(SI->getLHS());
471 const SCEV *RHS = SE->getSCEV(SI->getRHS());
472 if (!SE->willNotOverflow(SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
475 BinaryOperator *BO = BinaryOperator::Create(
476 SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
478 BO->setHasNoSignedWrap();
480 BO->setHasNoUnsignedWrap();
482 SI->replaceAllUsesWith(BO);
483 DeadInsts.emplace_back(SI);
488 bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
489 // It is always legal to replace
490 // icmp <pred> i32 trunc(iv), n
492 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
494 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
495 // Or with either of these if pred is an equality predicate.
497 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
498 // every comparison which uses trunc, it means that we can replace each of
499 // them with comparison of iv against sext/zext(n). We no longer need trunc
502 // TODO: Should we do this if we can widen *some* comparisons, but not all
503 // of them? Sometimes it is enough to enable other optimizations, but the
504 // trunc instruction will stay in the loop.
505 Value *IV = TI->getOperand(0);
506 Type *IVTy = IV->getType();
507 const SCEV *IVSCEV = SE->getSCEV(IV);
508 const SCEV *TISCEV = SE->getSCEV(TI);
510 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
512 bool DoesSExtCollapse = false;
513 bool DoesZExtCollapse = false;
514 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
515 DoesSExtCollapse = true;
516 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
517 DoesZExtCollapse = true;
519 // If neither sext nor zext does collapse, it is not profitable to do any
521 if (!DoesSExtCollapse && !DoesZExtCollapse)
524 // Collect users of the trunc that look like comparisons against invariants.
525 // Bail if we find something different.
526 SmallVector<ICmpInst *, 4> ICmpUsers;
527 for (auto *U : TI->users()) {
528 // We don't care about users in unreachable blocks.
529 if (isa<Instruction>(U) &&
530 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
532 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
533 if (!ICI) return false;
534 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
535 if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&
536 !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))
538 // If we cannot get rid of trunc, bail.
539 if (ICI->isSigned() && !DoesSExtCollapse)
541 if (ICI->isUnsigned() && !DoesZExtCollapse)
543 // For equality, either signed or unsigned works.
544 ICmpUsers.push_back(ICI);
547 auto CanUseZExt = [&](ICmpInst *ICI) {
548 // Unsigned comparison can be widened as unsigned.
549 if (ICI->isUnsigned())
551 // Is it profitable to do zext?
552 if (!DoesZExtCollapse)
554 // For equality, we can safely zext both parts.
555 if (ICI->isEquality())
557 // Otherwise we can only use zext when comparing two non-negative or two
558 // negative values. But in practice, we will never pass DoesZExtCollapse
559 // check for a negative value, because zext(trunc(x)) is non-negative. So
560 // it only make sense to check for non-negativity here.
561 const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
562 const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
563 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
565 // Replace all comparisons against trunc with comparisons against IV.
566 for (auto *ICI : ICmpUsers) {
567 bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
568 auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);
569 Instruction *Ext = nullptr;
570 // For signed/unsigned predicate, replace the old comparison with comparison
571 // of immediate IV against sext/zext of the invariant argument. If we can
572 // use either sext or zext (i.e. we are dealing with equality predicate),
573 // then prefer zext as a more canonical form.
574 // TODO: If we see a signed comparison which can be turned into unsigned,
575 // we can do it here for canonicalization purposes.
576 ICmpInst::Predicate Pred = ICI->getPredicate();
577 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
578 if (CanUseZExt(ICI)) {
579 assert(DoesZExtCollapse && "Unprofitable zext?");
580 Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
581 Pred = ICmpInst::getUnsignedPredicate(Pred);
583 assert(DoesSExtCollapse && "Unprofitable sext?");
584 Ext = new SExtInst(Op1, IVTy, "sext", ICI);
585 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
588 L->makeLoopInvariant(Ext, Changed);
590 ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
591 ICI->replaceAllUsesWith(NewICI);
592 DeadInsts.emplace_back(ICI);
595 // Trunc no longer needed.
596 TI->replaceAllUsesWith(PoisonValue::get(TI->getType()));
597 DeadInsts.emplace_back(TI);
601 /// Eliminate an operation that consumes a simple IV and has no observable
602 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
603 /// but UseInst may not be.
604 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
605 Instruction *IVOperand) {
606 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
607 eliminateIVComparison(ICmp, IVOperand);
610 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
611 bool IsSRem = Bin->getOpcode() == Instruction::SRem;
612 if (IsSRem || Bin->getOpcode() == Instruction::URem) {
613 simplifyIVRemainder(Bin, IVOperand, IsSRem);
617 if (Bin->getOpcode() == Instruction::SDiv)
618 return eliminateSDiv(Bin);
621 if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
622 if (eliminateOverflowIntrinsic(WO))
625 if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
626 if (eliminateSaturatingIntrinsic(SI))
629 if (auto *TI = dyn_cast<TruncInst>(UseInst))
630 if (eliminateTrunc(TI))
633 if (eliminateIdentitySCEV(UseInst, IVOperand))
639 static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
640 if (auto *BB = L->getLoopPreheader())
641 return BB->getTerminator();
646 /// Replace the UseInst with a loop invariant expression if it is safe.
647 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
648 if (!SE->isSCEVable(I->getType()))
651 // Get the symbolic expression for this instruction.
652 const SCEV *S = SE->getSCEV(I);
654 if (!SE->isLoopInvariant(S, L))
657 // Do not generate something ridiculous even if S is loop invariant.
658 if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
661 auto *IP = GetLoopInvariantInsertPosition(L, I);
663 if (!Rewriter.isSafeToExpandAt(S, IP)) {
664 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
665 << " with non-speculable loop invariant: " << *S << '\n');
669 auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
671 I->replaceAllUsesWith(Invariant);
672 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
673 << " with loop invariant: " << *S << '\n');
676 DeadInsts.emplace_back(I);
680 /// Eliminate redundant type cast between integer and float.
681 bool SimplifyIndvar::replaceFloatIVWithIntegerIV(Instruction *UseInst) {
682 if (UseInst->getOpcode() != CastInst::SIToFP &&
683 UseInst->getOpcode() != CastInst::UIToFP)
686 Value *IVOperand = UseInst->getOperand(0);
687 // Get the symbolic expression for this instruction.
688 const SCEV *IV = SE->getSCEV(IVOperand);
690 if (UseInst->getOpcode() == CastInst::SIToFP)
691 MaskBits = SE->getSignedRange(IV).getMinSignedBits();
693 MaskBits = SE->getUnsignedRange(IV).getActiveBits();
694 unsigned DestNumSigBits = UseInst->getType()->getFPMantissaWidth();
695 if (MaskBits <= DestNumSigBits) {
696 for (User *U : UseInst->users()) {
697 // Match for fptosi/fptoui of sitofp and with same type.
698 auto *CI = dyn_cast<CastInst>(U);
699 if (!CI || IVOperand->getType() != CI->getType())
702 CastInst::CastOps Opcode = CI->getOpcode();
703 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
706 CI->replaceAllUsesWith(IVOperand);
707 DeadInsts.push_back(CI);
708 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *CI
709 << " with: " << *IVOperand << '\n');
719 /// Eliminate any operation that SCEV can prove is an identity function.
720 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
721 Instruction *IVOperand) {
722 if (!SE->isSCEVable(UseInst->getType()) ||
723 (UseInst->getType() != IVOperand->getType()) ||
724 (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
727 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
728 // dominator tree, even if X is an operand to Y. For instance, in
730 // %iv = phi i32 {0,+,1}
731 // br %cond, label %left, label %merge
734 // %X = add i32 %iv, 0
738 // %M = phi (%X, %iv)
740 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
741 // %M.replaceAllUsesWith(%X) would be incorrect.
743 if (isa<PHINode>(UseInst))
744 // If UseInst is not a PHI node then we know that IVOperand dominates
745 // UseInst directly from the legality of SSA.
746 if (!DT || !DT->dominates(IVOperand, UseInst))
749 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
752 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
754 UseInst->replaceAllUsesWith(IVOperand);
757 DeadInsts.emplace_back(UseInst);
761 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
762 /// unsigned-overflow. Returns true if anything changed, false otherwise.
763 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
764 Instruction *IVOperand) {
765 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
766 cast<OverflowingBinaryOperator>(BO));
771 BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNUW) ==
773 BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNSW) ==
776 // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap
777 // flags on addrecs while performing zero/sign extensions. We could call
778 // forgetValue() here to make sure those flags also propagate to any other
779 // SCEV expressions based on the addrec. However, this can have pathological
780 // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.
784 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
785 /// information from the IV's range. Returns true if anything changed, false
787 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
788 Instruction *IVOperand) {
789 using namespace llvm::PatternMatch;
791 if (BO->getOpcode() == Instruction::Shl) {
792 bool Changed = false;
793 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
794 for (auto *U : BO->users()) {
797 m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
799 m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
800 BinaryOperator *Shr = cast<BinaryOperator>(U);
801 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
802 Shr->setIsExact(true);
813 /// Add all uses of Def to the current IV's worklist.
814 static void pushIVUsers(
815 Instruction *Def, Loop *L,
816 SmallPtrSet<Instruction*,16> &Simplified,
817 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
819 for (User *U : Def->users()) {
820 Instruction *UI = cast<Instruction>(U);
822 // Avoid infinite or exponential worklist processing.
823 // Also ensure unique worklist users.
824 // If Def is a LoopPhi, it may not be in the Simplified set, so check for
829 // Only change the current Loop, do not change the other parts (e.g. other
831 if (!L->contains(UI))
834 // Do not push the same instruction more than once.
835 if (!Simplified.insert(UI).second)
838 SimpleIVUsers.push_back(std::make_pair(UI, Def));
842 /// Return true if this instruction generates a simple SCEV
843 /// expression in terms of that IV.
845 /// This is similar to IVUsers' isInteresting() but processes each instruction
846 /// non-recursively when the operand is already known to be a simpleIVUser.
848 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
849 if (!SE->isSCEVable(I->getType()))
852 // Get the symbolic expression for this instruction.
853 const SCEV *S = SE->getSCEV(I);
855 // Only consider affine recurrences.
856 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
857 if (AR && AR->getLoop() == L)
863 /// Iteratively perform simplification on a worklist of users
864 /// of the specified induction variable. Each successive simplification may push
865 /// more users which may themselves be candidates for simplification.
867 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
868 /// instructions in-place during analysis. Rather than rewriting induction
869 /// variables bottom-up from their users, it transforms a chain of IVUsers
870 /// top-down, updating the IR only when it encounters a clear optimization
873 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
875 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
876 if (!SE->isSCEVable(CurrIV->getType()))
879 // Instructions processed by SimplifyIndvar for CurrIV.
880 SmallPtrSet<Instruction*,16> Simplified;
882 // Use-def pairs if IV users waiting to be processed for CurrIV.
883 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
885 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
886 // called multiple times for the same LoopPhi. This is the proper thing to
887 // do for loop header phis that use each other.
888 pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
890 while (!SimpleIVUsers.empty()) {
891 std::pair<Instruction*, Instruction*> UseOper =
892 SimpleIVUsers.pop_back_val();
893 Instruction *UseInst = UseOper.first;
895 // If a user of the IndVar is trivially dead, we prefer just to mark it dead
896 // rather than try to do some complex analysis or transformation (such as
897 // widening) basing on it.
898 // TODO: Propagate TLI and pass it here to handle more cases.
899 if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
900 DeadInsts.emplace_back(UseInst);
904 // Bypass back edges to avoid extra work.
905 if (UseInst == CurrIV) continue;
907 // Try to replace UseInst with a loop invariant before any other
909 if (replaceIVUserWithLoopInvariant(UseInst))
912 Instruction *IVOperand = UseOper.second;
913 for (unsigned N = 0; IVOperand; ++N) {
914 assert(N <= Simplified.size() && "runaway iteration");
917 Value *NewOper = foldIVUser(UseInst, IVOperand);
919 break; // done folding
920 IVOperand = dyn_cast<Instruction>(NewOper);
925 if (eliminateIVUser(UseInst, IVOperand)) {
926 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
930 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
931 if ((isa<OverflowingBinaryOperator>(BO) &&
932 strengthenOverflowingOperation(BO, IVOperand)) ||
933 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
934 // re-queue uses of the now modified binary operator and fall
935 // through to the checks that remain.
936 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
940 // Try to use integer induction for FPToSI of float induction directly.
941 if (replaceFloatIVWithIntegerIV(UseInst)) {
942 // Re-queue the potentially new direct uses of IVOperand.
943 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
947 CastInst *Cast = dyn_cast<CastInst>(UseInst);
952 if (isSimpleIVUser(UseInst, L, SE)) {
953 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
960 void IVVisitor::anchor() { }
962 /// Simplify instructions that use this induction variable
963 /// by using ScalarEvolution to analyze the IV's recurrence.
964 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
965 LoopInfo *LI, const TargetTransformInfo *TTI,
966 SmallVectorImpl<WeakTrackingVH> &Dead,
967 SCEVExpander &Rewriter, IVVisitor *V) {
968 SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,
970 SIV.simplifyUsers(CurrIV, V);
971 return SIV.hasChanged();
974 /// Simplify users of induction variables within this
975 /// loop. This does not actually change or add IVs.
976 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
977 LoopInfo *LI, const TargetTransformInfo *TTI,
978 SmallVectorImpl<WeakTrackingVH> &Dead) {
979 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
981 Rewriter.setDebugType(DEBUG_TYPE);
983 bool Changed = false;
984 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
986 simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);
994 //===----------------------------------------------------------------------===//
995 // Widen Induction Variables - Extend the width of an IV to cover its
997 //===----------------------------------------------------------------------===//
1007 ScalarEvolution *SE;
1010 // Does the module have any calls to the llvm.experimental.guard intrinsic
1011 // at all? If not we can avoid scanning instructions looking for guards.
1014 bool UsePostIncrementRanges;
1017 unsigned NumElimExt = 0;
1018 unsigned NumWidened = 0;
1021 PHINode *WidePhi = nullptr;
1022 Instruction *WideInc = nullptr;
1023 const SCEV *WideIncExpr = nullptr;
1024 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
1026 SmallPtrSet<Instruction *,16> Widened;
1028 enum class ExtendKind { Zero, Sign, Unknown };
1030 // A map tracking the kind of extension used to widen each narrow IV
1031 // and narrow IV user.
1032 // Key: pointer to a narrow IV or IV user.
1033 // Value: the kind of extension used to widen this Instruction.
1034 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
1036 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
1038 // A map with control-dependent ranges for post increment IV uses. The key is
1039 // a pair of IV def and a use of this def denoting the context. The value is
1040 // a ConstantRange representing possible values of the def at the given
1042 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
1044 Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
1045 Instruction *UseI) {
1046 DefUserPair Key(Def, UseI);
1047 auto It = PostIncRangeInfos.find(Key);
1048 return It == PostIncRangeInfos.end()
1049 ? Optional<ConstantRange>(None)
1050 : Optional<ConstantRange>(It->second);
1053 void calculatePostIncRanges(PHINode *OrigPhi);
1054 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
1056 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
1057 DefUserPair Key(Def, UseI);
1058 auto It = PostIncRangeInfos.find(Key);
1059 if (It == PostIncRangeInfos.end())
1060 PostIncRangeInfos.insert({Key, R});
1062 It->second = R.intersectWith(It->second);
1066 /// Record a link in the Narrow IV def-use chain along with the WideIV that
1067 /// computes the same value as the Narrow IV def. This avoids caching Use*
1069 struct NarrowIVDefUse {
1070 Instruction *NarrowDef = nullptr;
1071 Instruction *NarrowUse = nullptr;
1072 Instruction *WideDef = nullptr;
1074 // True if the narrow def is never negative. Tracking this information lets
1075 // us use a sign extension instead of a zero extension or vice versa, when
1076 // profitable and legal.
1077 bool NeverNegative = false;
1079 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
1081 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1082 NeverNegative(NeverNegative) {}
1085 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1086 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
1087 bool HasGuards, bool UsePostIncrementRanges = true);
1089 PHINode *createWideIV(SCEVExpander &Rewriter);
1091 unsigned getNumElimExt() { return NumElimExt; };
1092 unsigned getNumWidened() { return NumWidened; };
1095 Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
1098 Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
1099 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1100 const SCEVAddRecExpr *WideAR);
1101 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1103 ExtendKind getExtendKind(Instruction *I);
1105 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1107 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1109 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1111 const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1112 unsigned OpCode) const;
1114 Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);
1116 bool widenLoopCompare(NarrowIVDefUse DU);
1117 bool widenWithVariantUse(NarrowIVDefUse DU);
1119 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1122 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
1126 /// Determine the insertion point for this user. By default, insert immediately
1127 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
1128 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
1129 /// common dominator for the incoming blocks. A nullptr can be returned if no
1130 /// viable location is found: it may happen if User is a PHI and Def only comes
1131 /// to this PHI from unreachable blocks.
1132 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
1133 DominatorTree *DT, LoopInfo *LI) {
1134 PHINode *PHI = dyn_cast<PHINode>(User);
1138 Instruction *InsertPt = nullptr;
1139 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
1140 if (PHI->getIncomingValue(i) != Def)
1143 BasicBlock *InsertBB = PHI->getIncomingBlock(i);
1145 if (!DT->isReachableFromEntry(InsertBB))
1149 InsertPt = InsertBB->getTerminator();
1152 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
1153 InsertPt = InsertBB->getTerminator();
1156 // If we have skipped all inputs, it means that Def only comes to Phi from
1157 // unreachable blocks.
1161 auto *DefI = dyn_cast<Instruction>(Def);
1165 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
1167 auto *L = LI->getLoopFor(DefI->getParent());
1168 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
1170 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
1171 if (LI->getLoopFor(DTN->getBlock()) == L)
1172 return DTN->getBlock()->getTerminator();
1174 llvm_unreachable("DefI dominates InsertPt!");
1177 WidenIV::WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1178 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
1179 bool HasGuards, bool UsePostIncrementRanges)
1180 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1181 L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
1182 HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),
1184 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
1185 ExtendKindMap[OrigPhi] = WI.IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1188 Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1189 bool IsSigned, Instruction *Use) {
1190 // Set the debug location and conservative insertion point.
1191 IRBuilder<> Builder(Use);
1192 // Hoist the insertion point into loop preheaders as far as possible.
1193 for (const Loop *L = LI->getLoopFor(Use->getParent());
1194 L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
1195 L = L->getParentLoop())
1196 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
1198 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1199 Builder.CreateZExt(NarrowOper, WideType);
1202 /// Instantiate a wide operation to replace a narrow operation. This only needs
1203 /// to handle operations that can evaluation to SCEVAddRec. It can safely return
1204 /// 0 for any operation we decide not to clone.
1205 Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1206 const SCEVAddRecExpr *WideAR) {
1207 unsigned Opcode = DU.NarrowUse->getOpcode();
1211 case Instruction::Add:
1212 case Instruction::Mul:
1213 case Instruction::UDiv:
1214 case Instruction::Sub:
1215 return cloneArithmeticIVUser(DU, WideAR);
1217 case Instruction::And:
1218 case Instruction::Or:
1219 case Instruction::Xor:
1220 case Instruction::Shl:
1221 case Instruction::LShr:
1222 case Instruction::AShr:
1223 return cloneBitwiseIVUser(DU);
1227 Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1228 Instruction *NarrowUse = DU.NarrowUse;
1229 Instruction *NarrowDef = DU.NarrowDef;
1230 Instruction *WideDef = DU.WideDef;
1232 LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1234 // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1235 // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1236 // invariant and will be folded or hoisted. If it actually comes from a
1237 // widened IV, it should be removed during a future call to widenIVUse.
1238 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;
1239 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1241 : createExtendInst(NarrowUse->getOperand(0), WideType,
1242 IsSigned, NarrowUse);
1243 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1245 : createExtendInst(NarrowUse->getOperand(1), WideType,
1246 IsSigned, NarrowUse);
1248 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1249 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1250 NarrowBO->getName());
1251 IRBuilder<> Builder(NarrowUse);
1252 Builder.Insert(WideBO);
1253 WideBO->copyIRFlags(NarrowBO);
1257 Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1258 const SCEVAddRecExpr *WideAR) {
1259 Instruction *NarrowUse = DU.NarrowUse;
1260 Instruction *NarrowDef = DU.NarrowDef;
1261 Instruction *WideDef = DU.WideDef;
1263 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1265 unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1267 // We're trying to find X such that
1269 // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1271 // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1272 // and check using SCEV if any of them are correct.
1274 // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1275 // correct solution to X.
1276 auto GuessNonIVOperand = [&](bool SignExt) {
1277 const SCEV *WideLHS;
1278 const SCEV *WideRHS;
1280 auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1282 return SE->getSignExtendExpr(S, Ty);
1283 return SE->getZeroExtendExpr(S, Ty);
1287 WideLHS = SE->getSCEV(WideDef);
1288 const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1289 WideRHS = GetExtend(NarrowRHS, WideType);
1291 const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1292 WideLHS = GetExtend(NarrowLHS, WideType);
1293 WideRHS = SE->getSCEV(WideDef);
1296 // WideUse is "WideDef `op.wide` X" as described in the comment.
1297 const SCEV *WideUse =
1298 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());
1300 return WideUse == WideAR;
1303 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;
1304 if (!GuessNonIVOperand(SignExtend)) {
1305 SignExtend = !SignExtend;
1306 if (!GuessNonIVOperand(SignExtend))
1310 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1312 : createExtendInst(NarrowUse->getOperand(0), WideType,
1313 SignExtend, NarrowUse);
1314 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1316 : createExtendInst(NarrowUse->getOperand(1), WideType,
1317 SignExtend, NarrowUse);
1319 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1320 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1321 NarrowBO->getName());
1323 IRBuilder<> Builder(NarrowUse);
1324 Builder.Insert(WideBO);
1325 WideBO->copyIRFlags(NarrowBO);
1329 WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1330 auto It = ExtendKindMap.find(I);
1331 assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1335 const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1336 unsigned OpCode) const {
1338 case Instruction::Add:
1339 return SE->getAddExpr(LHS, RHS);
1340 case Instruction::Sub:
1341 return SE->getMinusSCEV(LHS, RHS);
1342 case Instruction::Mul:
1343 return SE->getMulExpr(LHS, RHS);
1344 case Instruction::UDiv:
1345 return SE->getUDivExpr(LHS, RHS);
1347 llvm_unreachable("Unsupported opcode.");
1351 /// No-wrap operations can transfer sign extension of their result to their
1352 /// operands. Generate the SCEV value for the widened operation without
1353 /// actually modifying the IR yet. If the expression after extending the
1354 /// operands is an AddRec for this loop, return the AddRec and the kind of
1356 WidenIV::WidenedRecTy
1357 WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1358 // Handle the common case of add<nsw/nuw>
1359 const unsigned OpCode = DU.NarrowUse->getOpcode();
1360 // Only Add/Sub/Mul instructions supported yet.
1361 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1362 OpCode != Instruction::Mul)
1363 return {nullptr, ExtendKind::Unknown};
1365 // One operand (NarrowDef) has already been extended to WideDef. Now determine
1366 // if extending the other will lead to a recurrence.
1367 const unsigned ExtendOperIdx =
1368 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1369 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
1371 const SCEV *ExtendOperExpr = nullptr;
1372 const OverflowingBinaryOperator *OBO =
1373 cast<OverflowingBinaryOperator>(DU.NarrowUse);
1374 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1375 if (ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap())
1376 ExtendOperExpr = SE->getSignExtendExpr(
1377 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1378 else if (ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap())
1379 ExtendOperExpr = SE->getZeroExtendExpr(
1380 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1382 return {nullptr, ExtendKind::Unknown};
1384 // When creating this SCEV expr, don't apply the current operations NSW or NUW
1385 // flags. This instruction may be guarded by control flow that the no-wrap
1386 // behavior depends on. Non-control-equivalent instructions can be mapped to
1387 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1388 // semantics to those operations.
1389 const SCEV *lhs = SE->getSCEV(DU.WideDef);
1390 const SCEV *rhs = ExtendOperExpr;
1392 // Let's swap operands to the initial order for the case of non-commutative
1393 // operations, like SUB. See PR21014.
1394 if (ExtendOperIdx == 0)
1395 std::swap(lhs, rhs);
1396 const SCEVAddRecExpr *AddRec =
1397 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1399 if (!AddRec || AddRec->getLoop() != L)
1400 return {nullptr, ExtendKind::Unknown};
1402 return {AddRec, ExtKind};
1405 /// Is this instruction potentially interesting for further simplification after
1406 /// widening it's type? In other words, can the extend be safely hoisted out of
1407 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1408 /// so, return the extended recurrence and the kind of extension used. Otherwise
1409 /// return {nullptr, ExtendKind::Unknown}.
1410 WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1411 if (!DU.NarrowUse->getType()->isIntegerTy())
1412 return {nullptr, ExtendKind::Unknown};
1414 const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1415 if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1416 SE->getTypeSizeInBits(WideType)) {
1417 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1418 // index. So don't follow this use.
1419 return {nullptr, ExtendKind::Unknown};
1422 const SCEV *WideExpr;
1424 if (DU.NeverNegative) {
1425 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1426 if (isa<SCEVAddRecExpr>(WideExpr))
1427 ExtKind = ExtendKind::Sign;
1429 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1430 ExtKind = ExtendKind::Zero;
1432 } else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {
1433 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1434 ExtKind = ExtendKind::Sign;
1436 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1437 ExtKind = ExtendKind::Zero;
1439 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1440 if (!AddRec || AddRec->getLoop() != L)
1441 return {nullptr, ExtendKind::Unknown};
1442 return {AddRec, ExtKind};
1445 /// This IV user cannot be widened. Replace this use of the original narrow IV
1446 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1447 static void truncateIVUse(WidenIV::NarrowIVDefUse DU, DominatorTree *DT,
1449 auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1452 LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1453 << *DU.NarrowUse << "\n");
1454 IRBuilder<> Builder(InsertPt);
1455 Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1456 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1459 /// If the narrow use is a compare instruction, then widen the compare
1460 // (and possibly the other operand). The extend operation is hoisted into the
1461 // loop preheader as far as possible.
1462 bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1463 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
1467 // We can legally widen the comparison in the following two cases:
1469 // - The signedness of the IV extension and comparison match
1471 // - The narrow IV is always positive (and thus its sign extension is equal
1472 // to its zero extension). For instance, let's say we're zero extending
1473 // %narrow for the following use
1475 // icmp slt i32 %narrow, %val ... (A)
1477 // and %narrow is always positive. Then
1479 // (A) == icmp slt i32 sext(%narrow), sext(%val)
1480 // == icmp slt i32 zext(%narrow), sext(%val)
1481 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1482 if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1485 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1486 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1487 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1488 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1490 // Widen the compare instruction.
1491 auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1494 IRBuilder<> Builder(InsertPt);
1495 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1497 // Widen the other operand of the compare, if necessary.
1498 if (CastWidth < IVWidth) {
1499 Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1500 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1505 // The widenIVUse avoids generating trunc by evaluating the use as AddRec, this
1506 // will not work when:
1507 // 1) SCEV traces back to an instruction inside the loop that SCEV can not
1508 // expand, eg. add %indvar, (load %addr)
1509 // 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant
1510 // While SCEV fails to avoid trunc, we can still try to use instruction
1511 // combining approach to prove trunc is not required. This can be further
1512 // extended with other instruction combining checks, but for now we handle the
1513 // following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")
1516 // %c = sub nsw %b, %indvar
1517 // %d = sext %c to i64
1519 // %indvar.ext1 = sext %indvar to i64
1520 // %m = sext %b to i64
1521 // %d = sub nsw i64 %m, %indvar.ext1
1522 // Therefore, as long as the result of add/sub/mul is extended to wide type, no
1523 // trunc is required regardless of how %b is generated. This pattern is common
1524 // when calculating address in 64 bit architecture
1525 bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1526 Instruction *NarrowUse = DU.NarrowUse;
1527 Instruction *NarrowDef = DU.NarrowDef;
1528 Instruction *WideDef = DU.WideDef;
1530 // Handle the common case of add<nsw/nuw>
1531 const unsigned OpCode = NarrowUse->getOpcode();
1532 // Only Add/Sub/Mul instructions are supported.
1533 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1534 OpCode != Instruction::Mul)
1537 // The operand that is not defined by NarrowDef of DU. Let's call it the
1539 assert((NarrowUse->getOperand(0) == NarrowDef ||
1540 NarrowUse->getOperand(1) == NarrowDef) &&
1543 const OverflowingBinaryOperator *OBO =
1544 cast<OverflowingBinaryOperator>(NarrowUse);
1545 ExtendKind ExtKind = getExtendKind(NarrowDef);
1546 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap();
1547 bool CanZeroExtend = ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap();
1548 auto AnotherOpExtKind = ExtKind;
1550 // Check that all uses are either:
1551 // - narrow def (in case of we are widening the IV increment);
1552 // - single-input LCSSA Phis;
1553 // - comparison of the chosen type;
1554 // - extend of the chosen type (raison d'etre).
1555 SmallVector<Instruction *, 4> ExtUsers;
1556 SmallVector<PHINode *, 4> LCSSAPhiUsers;
1557 SmallVector<ICmpInst *, 4> ICmpUsers;
1558 for (Use &U : NarrowUse->uses()) {
1559 Instruction *User = cast<Instruction>(U.getUser());
1560 if (User == NarrowDef)
1562 if (!L->contains(User)) {
1563 auto *LCSSAPhi = cast<PHINode>(User);
1564 // Make sure there is only 1 input, so that we don't have to split
1566 if (LCSSAPhi->getNumOperands() != 1)
1568 LCSSAPhiUsers.push_back(LCSSAPhi);
1571 if (auto *ICmp = dyn_cast<ICmpInst>(User)) {
1572 auto Pred = ICmp->getPredicate();
1573 // We have 3 types of predicates: signed, unsigned and equality
1574 // predicates. For equality, it's legal to widen icmp for either sign and
1575 // zero extend. For sign extend, we can also do so for signed predicates,
1576 // likeweise for zero extend we can widen icmp for unsigned predicates.
1577 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1579 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1581 ICmpUsers.push_back(ICmp);
1584 if (ExtKind == ExtendKind::Sign)
1585 User = dyn_cast<SExtInst>(User);
1587 User = dyn_cast<ZExtInst>(User);
1588 if (!User || User->getType() != WideType)
1590 ExtUsers.push_back(User);
1592 if (ExtUsers.empty()) {
1593 DeadInsts.emplace_back(NarrowUse);
1597 // We'll prove some facts that should be true in the context of ext users. If
1598 // there is no users, we are done now. If there are some, pick their common
1599 // dominator as context.
1600 const Instruction *CtxI = findCommonDominator(ExtUsers, *DT);
1602 if (!CanSignExtend && !CanZeroExtend) {
1603 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
1604 // will most likely not see it. Let's try to prove it.
1605 if (OpCode != Instruction::Add)
1607 if (ExtKind != ExtendKind::Zero)
1609 const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));
1610 const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));
1611 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
1612 if (NarrowUse->getOperand(0) != NarrowDef)
1614 if (!SE->isKnownNegative(RHS))
1616 bool ProvedSubNUW = SE->isKnownPredicateAt(ICmpInst::ICMP_UGE, LHS,
1617 SE->getNegativeSCEV(RHS), CtxI);
1620 // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as
1621 // neg(zext(neg(op))), which is basically sext(op).
1622 AnotherOpExtKind = ExtendKind::Sign;
1625 // Verifying that Defining operand is an AddRec
1626 const SCEV *Op1 = SE->getSCEV(WideDef);
1627 const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
1628 if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1631 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1633 // Generating a widening use instruction.
1635 (NarrowUse->getOperand(0) == NarrowDef)
1637 : createExtendInst(NarrowUse->getOperand(0), WideType,
1638 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1640 (NarrowUse->getOperand(1) == NarrowDef)
1642 : createExtendInst(NarrowUse->getOperand(1), WideType,
1643 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1645 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1646 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1647 NarrowBO->getName());
1648 IRBuilder<> Builder(NarrowUse);
1649 Builder.Insert(WideBO);
1650 WideBO->copyIRFlags(NarrowBO);
1651 ExtendKindMap[NarrowUse] = ExtKind;
1653 for (Instruction *User : ExtUsers) {
1654 assert(User->getType() == WideType && "Checked before!");
1655 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1656 << *WideBO << "\n");
1658 User->replaceAllUsesWith(WideBO);
1659 DeadInsts.emplace_back(User);
1662 for (PHINode *User : LCSSAPhiUsers) {
1663 assert(User->getNumOperands() == 1 && "Checked before!");
1664 Builder.SetInsertPoint(User);
1666 Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");
1667 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
1668 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
1669 "Not a LCSSA Phi?");
1670 WidePN->addIncoming(WideBO, LoopExitingBlock);
1671 Builder.SetInsertPoint(&*User->getParent()->getFirstInsertionPt());
1672 auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());
1673 User->replaceAllUsesWith(TruncPN);
1674 DeadInsts.emplace_back(User);
1677 for (ICmpInst *User : ICmpUsers) {
1678 Builder.SetInsertPoint(User);
1679 auto ExtendedOp = [&](Value * V)->Value * {
1682 if (ExtKind == ExtendKind::Zero)
1683 return Builder.CreateZExt(V, WideBO->getType());
1685 return Builder.CreateSExt(V, WideBO->getType());
1687 auto Pred = User->getPredicate();
1688 auto *LHS = ExtendedOp(User->getOperand(0));
1689 auto *RHS = ExtendedOp(User->getOperand(1));
1691 Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");
1692 User->replaceAllUsesWith(WideCmp);
1693 DeadInsts.emplace_back(User);
1699 /// Determine whether an individual user of the narrow IV can be widened. If so,
1700 /// return the wide clone of the user.
1701 Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU, SCEVExpander &Rewriter) {
1702 assert(ExtendKindMap.count(DU.NarrowDef) &&
1703 "Should already know the kind of extension used to widen NarrowDef");
1705 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1706 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1707 if (LI->getLoopFor(UsePhi->getParent()) != L) {
1708 // For LCSSA phis, sink the truncate outside the loop.
1709 // After SimplifyCFG most loop exit targets have a single predecessor.
1710 // Otherwise fall back to a truncate within the loop.
1711 if (UsePhi->getNumOperands() != 1)
1712 truncateIVUse(DU, DT, LI);
1714 // Widening the PHI requires us to insert a trunc. The logical place
1715 // for this trunc is in the same BB as the PHI. This is not possible if
1716 // the BB is terminated by a catchswitch.
1717 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1721 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1723 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1724 IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
1725 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1726 UsePhi->replaceAllUsesWith(Trunc);
1727 DeadInsts.emplace_back(UsePhi);
1728 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1729 << *WidePhi << "\n");
1735 // This narrow use can be widened by a sext if it's non-negative or its narrow
1736 // def was widended by a sext. Same for zext.
1737 auto canWidenBySExt = [&]() {
1738 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1740 auto canWidenByZExt = [&]() {
1741 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;
1744 // Our raison d'etre! Eliminate sign and zero extension.
1745 if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1746 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1747 Value *NewDef = DU.WideDef;
1748 if (DU.NarrowUse->getType() != WideType) {
1749 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1750 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1751 if (CastWidth < IVWidth) {
1752 // The cast isn't as wide as the IV, so insert a Trunc.
1753 IRBuilder<> Builder(DU.NarrowUse);
1754 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1757 // A wider extend was hidden behind a narrower one. This may induce
1758 // another round of IV widening in which the intermediate IV becomes
1759 // dead. It should be very rare.
1760 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1761 << " not wide enough to subsume " << *DU.NarrowUse
1763 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1764 NewDef = DU.NarrowUse;
1767 if (NewDef != DU.NarrowUse) {
1768 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1769 << " replaced by " << *DU.WideDef << "\n");
1771 DU.NarrowUse->replaceAllUsesWith(NewDef);
1772 DeadInsts.emplace_back(DU.NarrowUse);
1774 // Now that the extend is gone, we want to expose it's uses for potential
1775 // further simplification. We don't need to directly inform SimplifyIVUsers
1776 // of the new users, because their parent IV will be processed later as a
1777 // new loop phi. If we preserved IVUsers analysis, we would also want to
1778 // push the uses of WideDef here.
1780 // No further widening is needed. The deceased [sz]ext had done it for us.
1784 // Does this user itself evaluate to a recurrence after widening?
1785 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1786 if (!WideAddRec.first)
1787 WideAddRec = getWideRecurrence(DU);
1789 assert((WideAddRec.first == nullptr) ==
1790 (WideAddRec.second == ExtendKind::Unknown));
1791 if (!WideAddRec.first) {
1792 // If use is a loop condition, try to promote the condition instead of
1793 // truncating the IV first.
1794 if (widenLoopCompare(DU))
1797 // We are here about to generate a truncate instruction that may hurt
1798 // performance because the scalar evolution expression computed earlier
1799 // in WideAddRec.first does not indicate a polynomial induction expression.
1800 // In that case, look at the operands of the use instruction to determine
1801 // if we can still widen the use instead of truncating its operand.
1802 if (widenWithVariantUse(DU))
1805 // This user does not evaluate to a recurrence after widening, so don't
1806 // follow it. Instead insert a Trunc to kill off the original use,
1807 // eventually isolating the original narrow IV so it can be removed.
1808 truncateIVUse(DU, DT, LI);
1812 // Reuse the IV increment that SCEVExpander created as long as it dominates
1814 Instruction *WideUse = nullptr;
1815 if (WideAddRec.first == WideIncExpr &&
1816 Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1819 WideUse = cloneIVUser(DU, WideAddRec.first);
1823 // Evaluation of WideAddRec ensured that the narrow expression could be
1824 // extended outside the loop without overflow. This suggests that the wide use
1825 // evaluates to the same expression as the extended narrow use, but doesn't
1826 // absolutely guarantee it. Hence the following failsafe check. In rare cases
1827 // where it fails, we simply throw away the newly created wide use.
1828 if (WideAddRec.first != SE->getSCEV(WideUse)) {
1829 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1830 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1832 DeadInsts.emplace_back(WideUse);
1836 // if we reached this point then we are going to replace
1837 // DU.NarrowUse with WideUse. Reattach DbgValue then.
1838 replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);
1840 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1841 // Returning WideUse pushes it on the worklist.
1845 /// Add eligible users of NarrowDef to NarrowIVUsers.
1846 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
1847 const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
1848 bool NonNegativeDef =
1849 SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
1850 SE->getZero(NarrowSCEV->getType()));
1851 for (User *U : NarrowDef->users()) {
1852 Instruction *NarrowUser = cast<Instruction>(U);
1854 // Handle data flow merges and bizarre phi cycles.
1855 if (!Widened.insert(NarrowUser).second)
1858 bool NonNegativeUse = false;
1859 if (!NonNegativeDef) {
1860 // We might have a control-dependent range information for this context.
1861 if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1862 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1865 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1866 NonNegativeDef || NonNegativeUse);
1870 /// Process a single induction variable. First use the SCEVExpander to create a
1871 /// wide induction variable that evaluates to the same recurrence as the
1872 /// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1873 /// def-use chain. After widenIVUse has processed all interesting IV users, the
1874 /// narrow IV will be isolated for removal by DeleteDeadPHIs.
1876 /// It would be simpler to delete uses as they are processed, but we must avoid
1877 /// invalidating SCEV expressions.
1878 PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
1879 // Is this phi an induction variable?
1880 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1884 // Widen the induction variable expression.
1885 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign
1886 ? SE->getSignExtendExpr(AddRec, WideType)
1887 : SE->getZeroExtendExpr(AddRec, WideType);
1889 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1890 "Expect the new IV expression to preserve its type");
1892 // Can the IV be extended outside the loop without overflow?
1893 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1894 if (!AddRec || AddRec->getLoop() != L)
1897 // An AddRec must have loop-invariant operands. Since this AddRec is
1898 // materialized by a loop header phi, the expression cannot have any post-loop
1899 // operands, so they must dominate the loop header.
1901 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1902 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
1903 "Loop header phi recurrence inputs do not dominate the loop");
1905 // Iterate over IV uses (including transitive ones) looking for IV increments
1906 // of the form 'add nsw %iv, <const>'. For each increment and each use of
1907 // the increment calculate control-dependent range information basing on
1908 // dominating conditions inside of the loop (e.g. a range check inside of the
1909 // loop). Calculated ranges are stored in PostIncRangeInfos map.
1911 // Control-dependent range information is later used to prove that a narrow
1912 // definition is not negative (see pushNarrowIVUsers). It's difficult to do
1913 // this on demand because when pushNarrowIVUsers needs this information some
1914 // of the dominating conditions might be already widened.
1915 if (UsePostIncrementRanges)
1916 calculatePostIncRanges(OrigPhi);
1918 // The rewriter provides a value for the desired IV expression. This may
1919 // either find an existing phi or materialize a new one. Either way, we
1920 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1921 // of the phi-SCC dominates the loop entry.
1922 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
1923 Value *ExpandInst = Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
1924 // If the wide phi is not a phi node, for example a cast node, like bitcast,
1925 // inttoptr, ptrtoint, just skip for now.
1926 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
1927 // if the cast node is an inserted instruction without any user, we should
1928 // remove it to make sure the pass don't touch the function as we can not
1930 if (ExpandInst->hasNUses(0) &&
1931 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
1932 DeadInsts.emplace_back(ExpandInst);
1936 // Remembering the WideIV increment generated by SCEVExpander allows
1937 // widenIVUse to reuse it when widening the narrow IV's increment. We don't
1938 // employ a general reuse mechanism because the call above is the only call to
1939 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1940 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1942 cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1943 WideIncExpr = SE->getSCEV(WideInc);
1944 // Propagate the debug location associated with the original loop increment
1945 // to the new (widened) increment.
1947 cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1948 WideInc->setDebugLoc(OrigInc->getDebugLoc());
1951 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1954 // Traverse the def-use chain using a worklist starting at the original IV.
1955 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1957 Widened.insert(OrigPhi);
1958 pushNarrowIVUsers(OrigPhi, WidePhi);
1960 while (!NarrowIVUsers.empty()) {
1961 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1963 // Process a def-use edge. This may replace the use, so don't hold a
1964 // use_iterator across it.
1965 Instruction *WideUse = widenIVUse(DU, Rewriter);
1967 // Follow all def-use edges from the previous narrow use.
1969 pushNarrowIVUsers(DU.NarrowUse, WideUse);
1971 // widenIVUse may have removed the def-use edge.
1972 if (DU.NarrowDef->use_empty())
1973 DeadInsts.emplace_back(DU.NarrowDef);
1976 // Attach any debug information to the new PHI.
1977 replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);
1982 /// Calculates control-dependent range for the given def at the given context
1983 /// by looking at dominating conditions inside of the loop
1984 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
1985 Instruction *NarrowUser) {
1986 using namespace llvm::PatternMatch;
1988 Value *NarrowDefLHS;
1989 const APInt *NarrowDefRHS;
1990 if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
1991 m_APInt(NarrowDefRHS))) ||
1992 !NarrowDefRHS->isNonNegative())
1995 auto UpdateRangeFromCondition = [&] (Value *Condition,
1997 CmpInst::Predicate Pred;
1999 if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
2003 CmpInst::Predicate P =
2004 TrueDest ? Pred : CmpInst::getInversePredicate(Pred);
2006 auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
2007 auto CmpConstrainedLHSRange =
2008 ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
2009 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2010 *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);
2012 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2015 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
2019 for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
2020 Ctx->getParent()->rend())) {
2022 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
2023 UpdateRangeFromCondition(C, /*TrueDest=*/true);
2027 UpdateRangeFromGuards(NarrowUser);
2029 BasicBlock *NarrowUserBB = NarrowUser->getParent();
2030 // If NarrowUserBB is statically unreachable asking dominator queries may
2031 // yield surprising results. (e.g. the block may not have a dom tree node)
2032 if (!DT->isReachableFromEntry(NarrowUserBB))
2035 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2036 L->contains(DTB->getBlock());
2037 DTB = DTB->getIDom()) {
2038 auto *BB = DTB->getBlock();
2039 auto *TI = BB->getTerminator();
2040 UpdateRangeFromGuards(TI);
2042 auto *BI = dyn_cast<BranchInst>(TI);
2043 if (!BI || !BI->isConditional())
2046 auto *TrueSuccessor = BI->getSuccessor(0);
2047 auto *FalseSuccessor = BI->getSuccessor(1);
2049 auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
2050 return BBE.isSingleEdge() &&
2051 DT->dominates(BBE, NarrowUser->getParent());
2054 if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
2055 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
2057 if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
2058 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
2062 /// Calculates PostIncRangeInfos map for the given IV
2063 void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
2064 SmallPtrSet<Instruction *, 16> Visited;
2065 SmallVector<Instruction *, 6> Worklist;
2066 Worklist.push_back(OrigPhi);
2067 Visited.insert(OrigPhi);
2069 while (!Worklist.empty()) {
2070 Instruction *NarrowDef = Worklist.pop_back_val();
2072 for (Use &U : NarrowDef->uses()) {
2073 auto *NarrowUser = cast<Instruction>(U.getUser());
2075 // Don't go looking outside the current loop.
2076 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
2077 if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
2080 if (!Visited.insert(NarrowUser).second)
2083 Worklist.push_back(NarrowUser);
2085 calculatePostIncRange(NarrowDef, NarrowUser);
2090 PHINode *llvm::createWideIV(const WideIVInfo &WI,
2091 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,
2092 DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,
2093 unsigned &NumElimExt, unsigned &NumWidened,
2094 bool HasGuards, bool UsePostIncrementRanges) {
2095 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);
2096 PHINode *WidePHI = Widener.createWideIV(Rewriter);
2097 NumElimExt = Widener.getNumElimExt();
2098 NumWidened = Widener.getNumWidened();