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 auto *PN = dyn_cast<PHINode>(IVOperand);
197 auto LIP = SE->getLoopInvariantPredicate(Pred, S, X, L);
200 ICmpInst::Predicate InvariantPredicate = LIP->Pred;
201 const SCEV *InvariantLHS = LIP->LHS;
202 const SCEV *InvariantRHS = LIP->RHS;
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();
484 bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
485 const SCEV *LHS = SE->getSCEV(SI->getLHS());
486 const SCEV *RHS = SE->getSCEV(SI->getRHS());
487 if (!willNotOverflow(SE, SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
490 BinaryOperator *BO = BinaryOperator::Create(
491 SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
493 BO->setHasNoSignedWrap();
495 BO->setHasNoUnsignedWrap();
497 SI->replaceAllUsesWith(BO);
498 DeadInsts.emplace_back(SI);
503 bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
504 // It is always legal to replace
505 // icmp <pred> i32 trunc(iv), n
507 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
509 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
510 // Or with either of these if pred is an equality predicate.
512 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
513 // every comparison which uses trunc, it means that we can replace each of
514 // them with comparison of iv against sext/zext(n). We no longer need trunc
517 // TODO: Should we do this if we can widen *some* comparisons, but not all
518 // of them? Sometimes it is enough to enable other optimizations, but the
519 // trunc instruction will stay in the loop.
520 Value *IV = TI->getOperand(0);
521 Type *IVTy = IV->getType();
522 const SCEV *IVSCEV = SE->getSCEV(IV);
523 const SCEV *TISCEV = SE->getSCEV(TI);
525 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
527 bool DoesSExtCollapse = false;
528 bool DoesZExtCollapse = false;
529 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
530 DoesSExtCollapse = true;
531 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
532 DoesZExtCollapse = true;
534 // If neither sext nor zext does collapse, it is not profitable to do any
536 if (!DoesSExtCollapse && !DoesZExtCollapse)
539 // Collect users of the trunc that look like comparisons against invariants.
540 // Bail if we find something different.
541 SmallVector<ICmpInst *, 4> ICmpUsers;
542 for (auto *U : TI->users()) {
543 // We don't care about users in unreachable blocks.
544 if (isa<Instruction>(U) &&
545 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
547 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
548 if (!ICI) return false;
549 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
550 if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&
551 !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))
553 // If we cannot get rid of trunc, bail.
554 if (ICI->isSigned() && !DoesSExtCollapse)
556 if (ICI->isUnsigned() && !DoesZExtCollapse)
558 // For equality, either signed or unsigned works.
559 ICmpUsers.push_back(ICI);
562 auto CanUseZExt = [&](ICmpInst *ICI) {
563 // Unsigned comparison can be widened as unsigned.
564 if (ICI->isUnsigned())
566 // Is it profitable to do zext?
567 if (!DoesZExtCollapse)
569 // For equality, we can safely zext both parts.
570 if (ICI->isEquality())
572 // Otherwise we can only use zext when comparing two non-negative or two
573 // negative values. But in practice, we will never pass DoesZExtCollapse
574 // check for a negative value, because zext(trunc(x)) is non-negative. So
575 // it only make sense to check for non-negativity here.
576 const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
577 const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
578 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
580 // Replace all comparisons against trunc with comparisons against IV.
581 for (auto *ICI : ICmpUsers) {
582 bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
583 auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);
584 Instruction *Ext = nullptr;
585 // For signed/unsigned predicate, replace the old comparison with comparison
586 // of immediate IV against sext/zext of the invariant argument. If we can
587 // use either sext or zext (i.e. we are dealing with equality predicate),
588 // then prefer zext as a more canonical form.
589 // TODO: If we see a signed comparison which can be turned into unsigned,
590 // we can do it here for canonicalization purposes.
591 ICmpInst::Predicate Pred = ICI->getPredicate();
592 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
593 if (CanUseZExt(ICI)) {
594 assert(DoesZExtCollapse && "Unprofitable zext?");
595 Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
596 Pred = ICmpInst::getUnsignedPredicate(Pred);
598 assert(DoesSExtCollapse && "Unprofitable sext?");
599 Ext = new SExtInst(Op1, IVTy, "sext", ICI);
600 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
603 L->makeLoopInvariant(Ext, Changed);
605 ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
606 ICI->replaceAllUsesWith(NewICI);
607 DeadInsts.emplace_back(ICI);
610 // Trunc no longer needed.
611 TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
612 DeadInsts.emplace_back(TI);
616 /// Eliminate an operation that consumes a simple IV and has no observable
617 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
618 /// but UseInst may not be.
619 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
620 Instruction *IVOperand) {
621 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
622 eliminateIVComparison(ICmp, IVOperand);
625 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
626 bool IsSRem = Bin->getOpcode() == Instruction::SRem;
627 if (IsSRem || Bin->getOpcode() == Instruction::URem) {
628 simplifyIVRemainder(Bin, IVOperand, IsSRem);
632 if (Bin->getOpcode() == Instruction::SDiv)
633 return eliminateSDiv(Bin);
636 if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
637 if (eliminateOverflowIntrinsic(WO))
640 if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
641 if (eliminateSaturatingIntrinsic(SI))
644 if (auto *TI = dyn_cast<TruncInst>(UseInst))
645 if (eliminateTrunc(TI))
648 if (eliminateIdentitySCEV(UseInst, IVOperand))
654 static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
655 if (auto *BB = L->getLoopPreheader())
656 return BB->getTerminator();
661 /// Replace the UseInst with a loop invariant expression if it is safe.
662 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
663 if (!SE->isSCEVable(I->getType()))
666 // Get the symbolic expression for this instruction.
667 const SCEV *S = SE->getSCEV(I);
669 if (!SE->isLoopInvariant(S, L))
672 // Do not generate something ridiculous even if S is loop invariant.
673 if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
676 auto *IP = GetLoopInvariantInsertPosition(L, I);
678 if (!isSafeToExpandAt(S, IP, *SE)) {
679 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
680 << " with non-speculable loop invariant: " << *S << '\n');
684 auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
686 I->replaceAllUsesWith(Invariant);
687 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
688 << " with loop invariant: " << *S << '\n');
691 DeadInsts.emplace_back(I);
695 /// Eliminate any operation that SCEV can prove is an identity function.
696 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
697 Instruction *IVOperand) {
698 if (!SE->isSCEVable(UseInst->getType()) ||
699 (UseInst->getType() != IVOperand->getType()) ||
700 (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
703 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
704 // dominator tree, even if X is an operand to Y. For instance, in
706 // %iv = phi i32 {0,+,1}
707 // br %cond, label %left, label %merge
710 // %X = add i32 %iv, 0
714 // %M = phi (%X, %iv)
716 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
717 // %M.replaceAllUsesWith(%X) would be incorrect.
719 if (isa<PHINode>(UseInst))
720 // If UseInst is not a PHI node then we know that IVOperand dominates
721 // UseInst directly from the legality of SSA.
722 if (!DT || !DT->dominates(IVOperand, UseInst))
725 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
728 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
730 UseInst->replaceAllUsesWith(IVOperand);
733 DeadInsts.emplace_back(UseInst);
737 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
738 /// unsigned-overflow. Returns true if anything changed, false otherwise.
739 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
741 // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
742 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
745 if (BO->getOpcode() != Instruction::Add &&
746 BO->getOpcode() != Instruction::Sub &&
747 BO->getOpcode() != Instruction::Mul)
750 const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
751 const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
752 bool Changed = false;
754 if (!BO->hasNoUnsignedWrap() &&
755 willNotOverflow(SE, BO->getOpcode(), /* Signed */ false, LHS, RHS)) {
756 BO->setHasNoUnsignedWrap();
761 if (!BO->hasNoSignedWrap() &&
762 willNotOverflow(SE, BO->getOpcode(), /* Signed */ true, LHS, RHS)) {
763 BO->setHasNoSignedWrap();
771 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
772 /// information from the IV's range. Returns true if anything changed, false
774 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
776 using namespace llvm::PatternMatch;
778 if (BO->getOpcode() == Instruction::Shl) {
779 bool Changed = false;
780 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
781 for (auto *U : BO->users()) {
784 m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
786 m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
787 BinaryOperator *Shr = cast<BinaryOperator>(U);
788 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
789 Shr->setIsExact(true);
800 /// Add all uses of Def to the current IV's worklist.
801 static void pushIVUsers(
802 Instruction *Def, Loop *L,
803 SmallPtrSet<Instruction*,16> &Simplified,
804 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
806 for (User *U : Def->users()) {
807 Instruction *UI = cast<Instruction>(U);
809 // Avoid infinite or exponential worklist processing.
810 // Also ensure unique worklist users.
811 // If Def is a LoopPhi, it may not be in the Simplified set, so check for
816 // Only change the current Loop, do not change the other parts (e.g. other
818 if (!L->contains(UI))
821 // Do not push the same instruction more than once.
822 if (!Simplified.insert(UI).second)
825 SimpleIVUsers.push_back(std::make_pair(UI, Def));
829 /// Return true if this instruction generates a simple SCEV
830 /// expression in terms of that IV.
832 /// This is similar to IVUsers' isInteresting() but processes each instruction
833 /// non-recursively when the operand is already known to be a simpleIVUser.
835 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
836 if (!SE->isSCEVable(I->getType()))
839 // Get the symbolic expression for this instruction.
840 const SCEV *S = SE->getSCEV(I);
842 // Only consider affine recurrences.
843 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
844 if (AR && AR->getLoop() == L)
850 /// Iteratively perform simplification on a worklist of users
851 /// of the specified induction variable. Each successive simplification may push
852 /// more users which may themselves be candidates for simplification.
854 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
855 /// instructions in-place during analysis. Rather than rewriting induction
856 /// variables bottom-up from their users, it transforms a chain of IVUsers
857 /// top-down, updating the IR only when it encounters a clear optimization
860 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
862 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
863 if (!SE->isSCEVable(CurrIV->getType()))
866 // Instructions processed by SimplifyIndvar for CurrIV.
867 SmallPtrSet<Instruction*,16> Simplified;
869 // Use-def pairs if IV users waiting to be processed for CurrIV.
870 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
872 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
873 // called multiple times for the same LoopPhi. This is the proper thing to
874 // do for loop header phis that use each other.
875 pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
877 while (!SimpleIVUsers.empty()) {
878 std::pair<Instruction*, Instruction*> UseOper =
879 SimpleIVUsers.pop_back_val();
880 Instruction *UseInst = UseOper.first;
882 // If a user of the IndVar is trivially dead, we prefer just to mark it dead
883 // rather than try to do some complex analysis or transformation (such as
884 // widening) basing on it.
885 // TODO: Propagate TLI and pass it here to handle more cases.
886 if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
887 DeadInsts.emplace_back(UseInst);
891 // Bypass back edges to avoid extra work.
892 if (UseInst == CurrIV) continue;
894 // Try to replace UseInst with a loop invariant before any other
896 if (replaceIVUserWithLoopInvariant(UseInst))
899 Instruction *IVOperand = UseOper.second;
900 for (unsigned N = 0; IVOperand; ++N) {
901 assert(N <= Simplified.size() && "runaway iteration");
903 Value *NewOper = foldIVUser(UseInst, IVOperand);
905 break; // done folding
906 IVOperand = dyn_cast<Instruction>(NewOper);
911 if (eliminateIVUser(UseInst, IVOperand)) {
912 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
916 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
917 if ((isa<OverflowingBinaryOperator>(BO) &&
918 strengthenOverflowingOperation(BO, IVOperand)) ||
919 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
920 // re-queue uses of the now modified binary operator and fall
921 // through to the checks that remain.
922 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
926 CastInst *Cast = dyn_cast<CastInst>(UseInst);
931 if (isSimpleIVUser(UseInst, L, SE)) {
932 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
939 void IVVisitor::anchor() { }
941 /// Simplify instructions that use this induction variable
942 /// by using ScalarEvolution to analyze the IV's recurrence.
943 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
944 LoopInfo *LI, const TargetTransformInfo *TTI,
945 SmallVectorImpl<WeakTrackingVH> &Dead,
946 SCEVExpander &Rewriter, IVVisitor *V) {
947 SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,
949 SIV.simplifyUsers(CurrIV, V);
950 return SIV.hasChanged();
953 /// Simplify users of induction variables within this
954 /// loop. This does not actually change or add IVs.
955 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
956 LoopInfo *LI, const TargetTransformInfo *TTI,
957 SmallVectorImpl<WeakTrackingVH> &Dead) {
958 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
960 Rewriter.setDebugType(DEBUG_TYPE);
962 bool Changed = false;
963 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
965 simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);
972 //===----------------------------------------------------------------------===//
973 // Widen Induction Variables - Extend the width of an IV to cover its
975 //===----------------------------------------------------------------------===//
988 // Does the module have any calls to the llvm.experimental.guard intrinsic
989 // at all? If not we can avoid scanning instructions looking for guards.
992 bool UsePostIncrementRanges;
995 unsigned NumElimExt = 0;
996 unsigned NumWidened = 0;
999 PHINode *WidePhi = nullptr;
1000 Instruction *WideInc = nullptr;
1001 const SCEV *WideIncExpr = nullptr;
1002 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
1004 SmallPtrSet<Instruction *,16> Widened;
1006 enum ExtendKind { ZeroExtended, SignExtended, Unknown };
1008 // A map tracking the kind of extension used to widen each narrow IV
1009 // and narrow IV user.
1010 // Key: pointer to a narrow IV or IV user.
1011 // Value: the kind of extension used to widen this Instruction.
1012 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
1014 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
1016 // A map with control-dependent ranges for post increment IV uses. The key is
1017 // a pair of IV def and a use of this def denoting the context. The value is
1018 // a ConstantRange representing possible values of the def at the given
1020 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
1022 Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
1023 Instruction *UseI) {
1024 DefUserPair Key(Def, UseI);
1025 auto It = PostIncRangeInfos.find(Key);
1026 return It == PostIncRangeInfos.end()
1027 ? Optional<ConstantRange>(None)
1028 : Optional<ConstantRange>(It->second);
1031 void calculatePostIncRanges(PHINode *OrigPhi);
1032 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
1034 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
1035 DefUserPair Key(Def, UseI);
1036 auto It = PostIncRangeInfos.find(Key);
1037 if (It == PostIncRangeInfos.end())
1038 PostIncRangeInfos.insert({Key, R});
1040 It->second = R.intersectWith(It->second);
1044 /// Record a link in the Narrow IV def-use chain along with the WideIV that
1045 /// computes the same value as the Narrow IV def. This avoids caching Use*
1047 struct NarrowIVDefUse {
1048 Instruction *NarrowDef = nullptr;
1049 Instruction *NarrowUse = nullptr;
1050 Instruction *WideDef = nullptr;
1052 // True if the narrow def is never negative. Tracking this information lets
1053 // us use a sign extension instead of a zero extension or vice versa, when
1054 // profitable and legal.
1055 bool NeverNegative = false;
1057 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
1059 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1060 NeverNegative(NeverNegative) {}
1063 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1064 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
1065 bool HasGuards, bool UsePostIncrementRanges = true);
1067 PHINode *createWideIV(SCEVExpander &Rewriter);
1069 unsigned getNumElimExt() { return NumElimExt; };
1070 unsigned getNumWidened() { return NumWidened; };
1073 Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
1076 Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
1077 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1078 const SCEVAddRecExpr *WideAR);
1079 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1081 ExtendKind getExtendKind(Instruction *I);
1083 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1085 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1087 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1089 const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1090 unsigned OpCode) const;
1092 Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);
1094 bool widenLoopCompare(NarrowIVDefUse DU);
1095 bool widenWithVariantUse(NarrowIVDefUse DU);
1097 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1100 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
1104 /// Determine the insertion point for this user. By default, insert immediately
1105 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
1106 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
1107 /// common dominator for the incoming blocks. A nullptr can be returned if no
1108 /// viable location is found: it may happen if User is a PHI and Def only comes
1109 /// to this PHI from unreachable blocks.
1110 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
1111 DominatorTree *DT, LoopInfo *LI) {
1112 PHINode *PHI = dyn_cast<PHINode>(User);
1116 Instruction *InsertPt = nullptr;
1117 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
1118 if (PHI->getIncomingValue(i) != Def)
1121 BasicBlock *InsertBB = PHI->getIncomingBlock(i);
1123 if (!DT->isReachableFromEntry(InsertBB))
1127 InsertPt = InsertBB->getTerminator();
1130 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
1131 InsertPt = InsertBB->getTerminator();
1134 // If we have skipped all inputs, it means that Def only comes to Phi from
1135 // unreachable blocks.
1139 auto *DefI = dyn_cast<Instruction>(Def);
1143 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
1145 auto *L = LI->getLoopFor(DefI->getParent());
1146 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
1148 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
1149 if (LI->getLoopFor(DTN->getBlock()) == L)
1150 return DTN->getBlock()->getTerminator();
1152 llvm_unreachable("DefI dominates InsertPt!");
1155 WidenIV::WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1156 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
1157 bool HasGuards, bool UsePostIncrementRanges)
1158 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1159 L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
1160 HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),
1162 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
1163 ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
1166 Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1167 bool IsSigned, Instruction *Use) {
1168 // Set the debug location and conservative insertion point.
1169 IRBuilder<> Builder(Use);
1170 // Hoist the insertion point into loop preheaders as far as possible.
1171 for (const Loop *L = LI->getLoopFor(Use->getParent());
1172 L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
1173 L = L->getParentLoop())
1174 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
1176 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1177 Builder.CreateZExt(NarrowOper, WideType);
1180 /// Instantiate a wide operation to replace a narrow operation. This only needs
1181 /// to handle operations that can evaluation to SCEVAddRec. It can safely return
1182 /// 0 for any operation we decide not to clone.
1183 Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1184 const SCEVAddRecExpr *WideAR) {
1185 unsigned Opcode = DU.NarrowUse->getOpcode();
1189 case Instruction::Add:
1190 case Instruction::Mul:
1191 case Instruction::UDiv:
1192 case Instruction::Sub:
1193 return cloneArithmeticIVUser(DU, WideAR);
1195 case Instruction::And:
1196 case Instruction::Or:
1197 case Instruction::Xor:
1198 case Instruction::Shl:
1199 case Instruction::LShr:
1200 case Instruction::AShr:
1201 return cloneBitwiseIVUser(DU);
1205 Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1206 Instruction *NarrowUse = DU.NarrowUse;
1207 Instruction *NarrowDef = DU.NarrowDef;
1208 Instruction *WideDef = DU.WideDef;
1210 LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1212 // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1213 // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1214 // invariant and will be folded or hoisted. If it actually comes from a
1215 // widened IV, it should be removed during a future call to widenIVUse.
1216 bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
1217 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1219 : createExtendInst(NarrowUse->getOperand(0), WideType,
1220 IsSigned, NarrowUse);
1221 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1223 : createExtendInst(NarrowUse->getOperand(1), WideType,
1224 IsSigned, NarrowUse);
1226 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1227 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1228 NarrowBO->getName());
1229 IRBuilder<> Builder(NarrowUse);
1230 Builder.Insert(WideBO);
1231 WideBO->copyIRFlags(NarrowBO);
1235 Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1236 const SCEVAddRecExpr *WideAR) {
1237 Instruction *NarrowUse = DU.NarrowUse;
1238 Instruction *NarrowDef = DU.NarrowDef;
1239 Instruction *WideDef = DU.WideDef;
1241 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1243 unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1245 // We're trying to find X such that
1247 // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1249 // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1250 // and check using SCEV if any of them are correct.
1252 // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1253 // correct solution to X.
1254 auto GuessNonIVOperand = [&](bool SignExt) {
1255 const SCEV *WideLHS;
1256 const SCEV *WideRHS;
1258 auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1260 return SE->getSignExtendExpr(S, Ty);
1261 return SE->getZeroExtendExpr(S, Ty);
1265 WideLHS = SE->getSCEV(WideDef);
1266 const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1267 WideRHS = GetExtend(NarrowRHS, WideType);
1269 const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1270 WideLHS = GetExtend(NarrowLHS, WideType);
1271 WideRHS = SE->getSCEV(WideDef);
1274 // WideUse is "WideDef `op.wide` X" as described in the comment.
1275 const SCEV *WideUse =
1276 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());
1278 return WideUse == WideAR;
1281 bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
1282 if (!GuessNonIVOperand(SignExtend)) {
1283 SignExtend = !SignExtend;
1284 if (!GuessNonIVOperand(SignExtend))
1288 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1290 : createExtendInst(NarrowUse->getOperand(0), WideType,
1291 SignExtend, NarrowUse);
1292 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1294 : createExtendInst(NarrowUse->getOperand(1), WideType,
1295 SignExtend, NarrowUse);
1297 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1298 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1299 NarrowBO->getName());
1301 IRBuilder<> Builder(NarrowUse);
1302 Builder.Insert(WideBO);
1303 WideBO->copyIRFlags(NarrowBO);
1307 WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1308 auto It = ExtendKindMap.find(I);
1309 assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1313 const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1314 unsigned OpCode) const {
1316 case Instruction::Add:
1317 return SE->getAddExpr(LHS, RHS);
1318 case Instruction::Sub:
1319 return SE->getMinusSCEV(LHS, RHS);
1320 case Instruction::Mul:
1321 return SE->getMulExpr(LHS, RHS);
1322 case Instruction::UDiv:
1323 return SE->getUDivExpr(LHS, RHS);
1325 llvm_unreachable("Unsupported opcode.");
1329 /// No-wrap operations can transfer sign extension of their result to their
1330 /// operands. Generate the SCEV value for the widened operation without
1331 /// actually modifying the IR yet. If the expression after extending the
1332 /// operands is an AddRec for this loop, return the AddRec and the kind of
1334 WidenIV::WidenedRecTy
1335 WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1336 // Handle the common case of add<nsw/nuw>
1337 const unsigned OpCode = DU.NarrowUse->getOpcode();
1338 // Only Add/Sub/Mul instructions supported yet.
1339 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1340 OpCode != Instruction::Mul)
1341 return {nullptr, Unknown};
1343 // One operand (NarrowDef) has already been extended to WideDef. Now determine
1344 // if extending the other will lead to a recurrence.
1345 const unsigned ExtendOperIdx =
1346 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1347 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
1349 const SCEV *ExtendOperExpr = nullptr;
1350 const OverflowingBinaryOperator *OBO =
1351 cast<OverflowingBinaryOperator>(DU.NarrowUse);
1352 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1353 if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1354 ExtendOperExpr = SE->getSignExtendExpr(
1355 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1356 else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1357 ExtendOperExpr = SE->getZeroExtendExpr(
1358 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1360 return {nullptr, Unknown};
1362 // When creating this SCEV expr, don't apply the current operations NSW or NUW
1363 // flags. This instruction may be guarded by control flow that the no-wrap
1364 // behavior depends on. Non-control-equivalent instructions can be mapped to
1365 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1366 // semantics to those operations.
1367 const SCEV *lhs = SE->getSCEV(DU.WideDef);
1368 const SCEV *rhs = ExtendOperExpr;
1370 // Let's swap operands to the initial order for the case of non-commutative
1371 // operations, like SUB. See PR21014.
1372 if (ExtendOperIdx == 0)
1373 std::swap(lhs, rhs);
1374 const SCEVAddRecExpr *AddRec =
1375 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1377 if (!AddRec || AddRec->getLoop() != L)
1378 return {nullptr, Unknown};
1380 return {AddRec, ExtKind};
1383 /// Is this instruction potentially interesting for further simplification after
1384 /// widening it's type? In other words, can the extend be safely hoisted out of
1385 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1386 /// so, return the extended recurrence and the kind of extension used. Otherwise
1387 /// return {nullptr, Unknown}.
1388 WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1389 if (!SE->isSCEVable(DU.NarrowUse->getType()))
1390 return {nullptr, Unknown};
1392 const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1393 if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1394 SE->getTypeSizeInBits(WideType)) {
1395 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1396 // index. So don't follow this use.
1397 return {nullptr, Unknown};
1400 const SCEV *WideExpr;
1402 if (DU.NeverNegative) {
1403 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1404 if (isa<SCEVAddRecExpr>(WideExpr))
1405 ExtKind = SignExtended;
1407 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1408 ExtKind = ZeroExtended;
1410 } else if (getExtendKind(DU.NarrowDef) == SignExtended) {
1411 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1412 ExtKind = SignExtended;
1414 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1415 ExtKind = ZeroExtended;
1417 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1418 if (!AddRec || AddRec->getLoop() != L)
1419 return {nullptr, Unknown};
1420 return {AddRec, ExtKind};
1423 /// This IV user cannot be widened. Replace this use of the original narrow IV
1424 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1425 static void truncateIVUse(WidenIV::NarrowIVDefUse DU, DominatorTree *DT,
1427 auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1430 LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1431 << *DU.NarrowUse << "\n");
1432 IRBuilder<> Builder(InsertPt);
1433 Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1434 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1437 /// If the narrow use is a compare instruction, then widen the compare
1438 // (and possibly the other operand). The extend operation is hoisted into the
1439 // loop preheader as far as possible.
1440 bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1441 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
1445 // We can legally widen the comparison in the following two cases:
1447 // - The signedness of the IV extension and comparison match
1449 // - The narrow IV is always positive (and thus its sign extension is equal
1450 // to its zero extension). For instance, let's say we're zero extending
1451 // %narrow for the following use
1453 // icmp slt i32 %narrow, %val ... (A)
1455 // and %narrow is always positive. Then
1457 // (A) == icmp slt i32 sext(%narrow), sext(%val)
1458 // == icmp slt i32 zext(%narrow), sext(%val)
1459 bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
1460 if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1463 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1464 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1465 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1466 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1468 // Widen the compare instruction.
1469 auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1472 IRBuilder<> Builder(InsertPt);
1473 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1475 // Widen the other operand of the compare, if necessary.
1476 if (CastWidth < IVWidth) {
1477 Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1478 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1483 // The widenIVUse avoids generating trunc by evaluating the use as AddRec, this
1484 // will not work when:
1485 // 1) SCEV traces back to an instruction inside the loop that SCEV can not
1486 // expand, eg. add %indvar, (load %addr)
1487 // 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant
1488 // While SCEV fails to avoid trunc, we can still try to use instruction
1489 // combining approach to prove trunc is not required. This can be further
1490 // extended with other instruction combining checks, but for now we handle the
1491 // following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")
1494 // %c = sub nsw %b, %indvar
1495 // %d = sext %c to i64
1497 // %indvar.ext1 = sext %indvar to i64
1498 // %m = sext %b to i64
1499 // %d = sub nsw i64 %m, %indvar.ext1
1500 // Therefore, as long as the result of add/sub/mul is extended to wide type, no
1501 // trunc is required regardless of how %b is generated. This pattern is common
1502 // when calculating address in 64 bit architecture
1503 bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1504 Instruction *NarrowUse = DU.NarrowUse;
1505 Instruction *NarrowDef = DU.NarrowDef;
1506 Instruction *WideDef = DU.WideDef;
1508 // Handle the common case of add<nsw/nuw>
1509 const unsigned OpCode = NarrowUse->getOpcode();
1510 // Only Add/Sub/Mul instructions are supported.
1511 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1512 OpCode != Instruction::Mul)
1515 // The operand that is not defined by NarrowDef of DU. Let's call it the
1517 assert((NarrowUse->getOperand(0) == NarrowDef ||
1518 NarrowUse->getOperand(1) == NarrowDef) &&
1521 const OverflowingBinaryOperator *OBO =
1522 cast<OverflowingBinaryOperator>(NarrowUse);
1523 ExtendKind ExtKind = getExtendKind(NarrowDef);
1524 bool CanSignExtend = ExtKind == SignExtended && OBO->hasNoSignedWrap();
1525 bool CanZeroExtend = ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap();
1526 auto AnotherOpExtKind = ExtKind;
1528 // Check that all uses are either:
1529 // - narrow def (in case of we are widening the IV increment);
1530 // - single-input LCSSA Phis;
1531 // - comparison of the chosen type;
1532 // - extend of the chosen type (raison d'etre).
1533 SmallVector<Instruction *, 4> ExtUsers;
1534 SmallVector<PHINode *, 4> LCSSAPhiUsers;
1535 SmallVector<ICmpInst *, 4> ICmpUsers;
1536 for (Use &U : NarrowUse->uses()) {
1537 Instruction *User = cast<Instruction>(U.getUser());
1538 if (User == NarrowDef)
1540 if (!L->contains(User)) {
1541 auto *LCSSAPhi = cast<PHINode>(User);
1542 // Make sure there is only 1 input, so that we don't have to split
1544 if (LCSSAPhi->getNumOperands() != 1)
1546 LCSSAPhiUsers.push_back(LCSSAPhi);
1549 if (auto *ICmp = dyn_cast<ICmpInst>(User)) {
1550 auto Pred = ICmp->getPredicate();
1551 // We have 3 types of predicates: signed, unsigned and equality
1552 // predicates. For equality, it's legal to widen icmp for either sign and
1553 // zero extend. For sign extend, we can also do so for signed predicates,
1554 // likeweise for zero extend we can widen icmp for unsigned predicates.
1555 if (ExtKind == ZeroExtended && ICmpInst::isSigned(Pred))
1557 if (ExtKind == SignExtended && ICmpInst::isUnsigned(Pred))
1559 ICmpUsers.push_back(ICmp);
1562 if (ExtKind == SignExtended)
1563 User = dyn_cast<SExtInst>(User);
1565 User = dyn_cast<ZExtInst>(User);
1566 if (!User || User->getType() != WideType)
1568 ExtUsers.push_back(User);
1570 if (ExtUsers.empty()) {
1571 DeadInsts.emplace_back(NarrowUse);
1575 // We'll prove some facts that should be true in the context of ext users. If
1576 // there is no users, we are done now. If there are some, pick their common
1577 // dominator as context.
1578 Instruction *Context = nullptr;
1579 for (auto *Ext : ExtUsers) {
1580 if (!Context || DT->dominates(Ext, Context))
1582 else if (!DT->dominates(Context, Ext))
1583 // For users that don't have dominance relation, use common dominator.
1585 DT->findNearestCommonDominator(Context->getParent(), Ext->getParent())
1588 assert(Context && "Context not found?");
1590 if (!CanSignExtend && !CanZeroExtend) {
1591 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
1592 // will most likely not see it. Let's try to prove it.
1593 if (OpCode != Instruction::Add)
1595 if (ExtKind != ZeroExtended)
1597 const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));
1598 const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));
1599 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
1600 if (NarrowUse->getOperand(0) != NarrowDef)
1602 if (!SE->isKnownNegative(RHS))
1604 bool ProvedSubNUW = SE->isKnownPredicateAt(
1605 ICmpInst::ICMP_UGE, LHS, SE->getNegativeSCEV(RHS), Context);
1608 // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as
1609 // neg(zext(neg(op))), which is basically sext(op).
1610 AnotherOpExtKind = SignExtended;
1613 // Verifying that Defining operand is an AddRec
1614 const SCEV *Op1 = SE->getSCEV(WideDef);
1615 const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
1616 if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1619 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1621 // Generating a widening use instruction.
1622 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1624 : createExtendInst(NarrowUse->getOperand(0), WideType,
1625 AnotherOpExtKind, NarrowUse);
1626 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1628 : createExtendInst(NarrowUse->getOperand(1), WideType,
1629 AnotherOpExtKind, NarrowUse);
1631 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1632 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1633 NarrowBO->getName());
1634 IRBuilder<> Builder(NarrowUse);
1635 Builder.Insert(WideBO);
1636 WideBO->copyIRFlags(NarrowBO);
1637 ExtendKindMap[NarrowUse] = ExtKind;
1639 for (Instruction *User : ExtUsers) {
1640 assert(User->getType() == WideType && "Checked before!");
1641 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1642 << *WideBO << "\n");
1644 User->replaceAllUsesWith(WideBO);
1645 DeadInsts.emplace_back(User);
1648 for (PHINode *User : LCSSAPhiUsers) {
1649 assert(User->getNumOperands() == 1 && "Checked before!");
1650 Builder.SetInsertPoint(User);
1652 Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");
1653 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
1654 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
1655 "Not a LCSSA Phi?");
1656 WidePN->addIncoming(WideBO, LoopExitingBlock);
1657 Builder.SetInsertPoint(&*User->getParent()->getFirstInsertionPt());
1658 auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());
1659 User->replaceAllUsesWith(TruncPN);
1660 DeadInsts.emplace_back(User);
1663 for (ICmpInst *User : ICmpUsers) {
1664 Builder.SetInsertPoint(User);
1665 auto ExtendedOp = [&](Value * V)->Value * {
1668 if (ExtKind == ZeroExtended)
1669 return Builder.CreateZExt(V, WideBO->getType());
1671 return Builder.CreateSExt(V, WideBO->getType());
1673 auto Pred = User->getPredicate();
1674 auto *LHS = ExtendedOp(User->getOperand(0));
1675 auto *RHS = ExtendedOp(User->getOperand(1));
1677 Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");
1678 User->replaceAllUsesWith(WideCmp);
1679 DeadInsts.emplace_back(User);
1685 /// Determine whether an individual user of the narrow IV can be widened. If so,
1686 /// return the wide clone of the user.
1687 Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU, SCEVExpander &Rewriter) {
1688 assert(ExtendKindMap.count(DU.NarrowDef) &&
1689 "Should already know the kind of extension used to widen NarrowDef");
1691 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1692 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1693 if (LI->getLoopFor(UsePhi->getParent()) != L) {
1694 // For LCSSA phis, sink the truncate outside the loop.
1695 // After SimplifyCFG most loop exit targets have a single predecessor.
1696 // Otherwise fall back to a truncate within the loop.
1697 if (UsePhi->getNumOperands() != 1)
1698 truncateIVUse(DU, DT, LI);
1700 // Widening the PHI requires us to insert a trunc. The logical place
1701 // for this trunc is in the same BB as the PHI. This is not possible if
1702 // the BB is terminated by a catchswitch.
1703 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1707 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1709 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1710 IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
1711 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1712 UsePhi->replaceAllUsesWith(Trunc);
1713 DeadInsts.emplace_back(UsePhi);
1714 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1715 << *WidePhi << "\n");
1721 // This narrow use can be widened by a sext if it's non-negative or its narrow
1722 // def was widended by a sext. Same for zext.
1723 auto canWidenBySExt = [&]() {
1724 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
1726 auto canWidenByZExt = [&]() {
1727 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
1730 // Our raison d'etre! Eliminate sign and zero extension.
1731 if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1732 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1733 Value *NewDef = DU.WideDef;
1734 if (DU.NarrowUse->getType() != WideType) {
1735 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1736 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1737 if (CastWidth < IVWidth) {
1738 // The cast isn't as wide as the IV, so insert a Trunc.
1739 IRBuilder<> Builder(DU.NarrowUse);
1740 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1743 // A wider extend was hidden behind a narrower one. This may induce
1744 // another round of IV widening in which the intermediate IV becomes
1745 // dead. It should be very rare.
1746 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1747 << " not wide enough to subsume " << *DU.NarrowUse
1749 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1750 NewDef = DU.NarrowUse;
1753 if (NewDef != DU.NarrowUse) {
1754 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1755 << " replaced by " << *DU.WideDef << "\n");
1757 DU.NarrowUse->replaceAllUsesWith(NewDef);
1758 DeadInsts.emplace_back(DU.NarrowUse);
1760 // Now that the extend is gone, we want to expose it's uses for potential
1761 // further simplification. We don't need to directly inform SimplifyIVUsers
1762 // of the new users, because their parent IV will be processed later as a
1763 // new loop phi. If we preserved IVUsers analysis, we would also want to
1764 // push the uses of WideDef here.
1766 // No further widening is needed. The deceased [sz]ext had done it for us.
1770 // Does this user itself evaluate to a recurrence after widening?
1771 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1772 if (!WideAddRec.first)
1773 WideAddRec = getWideRecurrence(DU);
1775 assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
1776 if (!WideAddRec.first) {
1777 // If use is a loop condition, try to promote the condition instead of
1778 // truncating the IV first.
1779 if (widenLoopCompare(DU))
1782 // We are here about to generate a truncate instruction that may hurt
1783 // performance because the scalar evolution expression computed earlier
1784 // in WideAddRec.first does not indicate a polynomial induction expression.
1785 // In that case, look at the operands of the use instruction to determine
1786 // if we can still widen the use instead of truncating its operand.
1787 if (widenWithVariantUse(DU))
1790 // This user does not evaluate to a recurrence after widening, so don't
1791 // follow it. Instead insert a Trunc to kill off the original use,
1792 // eventually isolating the original narrow IV so it can be removed.
1793 truncateIVUse(DU, DT, LI);
1796 // Assume block terminators cannot evaluate to a recurrence. We can't to
1797 // insert a Trunc after a terminator if there happens to be a critical edge.
1798 assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
1799 "SCEV is not expected to evaluate a block terminator");
1801 // Reuse the IV increment that SCEVExpander created as long as it dominates
1803 Instruction *WideUse = nullptr;
1804 if (WideAddRec.first == WideIncExpr &&
1805 Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1808 WideUse = cloneIVUser(DU, WideAddRec.first);
1812 // Evaluation of WideAddRec ensured that the narrow expression could be
1813 // extended outside the loop without overflow. This suggests that the wide use
1814 // evaluates to the same expression as the extended narrow use, but doesn't
1815 // absolutely guarantee it. Hence the following failsafe check. In rare cases
1816 // where it fails, we simply throw away the newly created wide use.
1817 if (WideAddRec.first != SE->getSCEV(WideUse)) {
1818 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1819 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1821 DeadInsts.emplace_back(WideUse);
1825 // if we reached this point then we are going to replace
1826 // DU.NarrowUse with WideUse. Reattach DbgValue then.
1827 replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);
1829 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1830 // Returning WideUse pushes it on the worklist.
1834 /// Add eligible users of NarrowDef to NarrowIVUsers.
1835 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
1836 const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
1837 bool NonNegativeDef =
1838 SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
1839 SE->getZero(NarrowSCEV->getType()));
1840 for (User *U : NarrowDef->users()) {
1841 Instruction *NarrowUser = cast<Instruction>(U);
1843 // Handle data flow merges and bizarre phi cycles.
1844 if (!Widened.insert(NarrowUser).second)
1847 bool NonNegativeUse = false;
1848 if (!NonNegativeDef) {
1849 // We might have a control-dependent range information for this context.
1850 if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1851 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1854 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1855 NonNegativeDef || NonNegativeUse);
1859 /// Process a single induction variable. First use the SCEVExpander to create a
1860 /// wide induction variable that evaluates to the same recurrence as the
1861 /// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1862 /// def-use chain. After widenIVUse has processed all interesting IV users, the
1863 /// narrow IV will be isolated for removal by DeleteDeadPHIs.
1865 /// It would be simpler to delete uses as they are processed, but we must avoid
1866 /// invalidating SCEV expressions.
1867 PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
1868 // Is this phi an induction variable?
1869 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1873 // Widen the induction variable expression.
1874 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
1875 ? SE->getSignExtendExpr(AddRec, WideType)
1876 : SE->getZeroExtendExpr(AddRec, WideType);
1878 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1879 "Expect the new IV expression to preserve its type");
1881 // Can the IV be extended outside the loop without overflow?
1882 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1883 if (!AddRec || AddRec->getLoop() != L)
1886 // An AddRec must have loop-invariant operands. Since this AddRec is
1887 // materialized by a loop header phi, the expression cannot have any post-loop
1888 // operands, so they must dominate the loop header.
1890 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1891 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
1892 "Loop header phi recurrence inputs do not dominate the loop");
1894 // Iterate over IV uses (including transitive ones) looking for IV increments
1895 // of the form 'add nsw %iv, <const>'. For each increment and each use of
1896 // the increment calculate control-dependent range information basing on
1897 // dominating conditions inside of the loop (e.g. a range check inside of the
1898 // loop). Calculated ranges are stored in PostIncRangeInfos map.
1900 // Control-dependent range information is later used to prove that a narrow
1901 // definition is not negative (see pushNarrowIVUsers). It's difficult to do
1902 // this on demand because when pushNarrowIVUsers needs this information some
1903 // of the dominating conditions might be already widened.
1904 if (UsePostIncrementRanges)
1905 calculatePostIncRanges(OrigPhi);
1907 // The rewriter provides a value for the desired IV expression. This may
1908 // either find an existing phi or materialize a new one. Either way, we
1909 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1910 // of the phi-SCC dominates the loop entry.
1911 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
1912 Value *ExpandInst = Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
1913 // If the wide phi is not a phi node, for example a cast node, like bitcast,
1914 // inttoptr, ptrtoint, just skip for now.
1915 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
1916 // if the cast node is an inserted instruction without any user, we should
1917 // remove it to make sure the pass don't touch the function as we can not
1919 if (ExpandInst->hasNUses(0) &&
1920 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
1921 DeadInsts.emplace_back(ExpandInst);
1925 // Remembering the WideIV increment generated by SCEVExpander allows
1926 // widenIVUse to reuse it when widening the narrow IV's increment. We don't
1927 // employ a general reuse mechanism because the call above is the only call to
1928 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1929 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1931 cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1932 WideIncExpr = SE->getSCEV(WideInc);
1933 // Propagate the debug location associated with the original loop increment
1934 // to the new (widened) increment.
1936 cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1937 WideInc->setDebugLoc(OrigInc->getDebugLoc());
1940 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1943 // Traverse the def-use chain using a worklist starting at the original IV.
1944 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1946 Widened.insert(OrigPhi);
1947 pushNarrowIVUsers(OrigPhi, WidePhi);
1949 while (!NarrowIVUsers.empty()) {
1950 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1952 // Process a def-use edge. This may replace the use, so don't hold a
1953 // use_iterator across it.
1954 Instruction *WideUse = widenIVUse(DU, Rewriter);
1956 // Follow all def-use edges from the previous narrow use.
1958 pushNarrowIVUsers(DU.NarrowUse, WideUse);
1960 // widenIVUse may have removed the def-use edge.
1961 if (DU.NarrowDef->use_empty())
1962 DeadInsts.emplace_back(DU.NarrowDef);
1965 // Attach any debug information to the new PHI.
1966 replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);
1971 /// Calculates control-dependent range for the given def at the given context
1972 /// by looking at dominating conditions inside of the loop
1973 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
1974 Instruction *NarrowUser) {
1975 using namespace llvm::PatternMatch;
1977 Value *NarrowDefLHS;
1978 const APInt *NarrowDefRHS;
1979 if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
1980 m_APInt(NarrowDefRHS))) ||
1981 !NarrowDefRHS->isNonNegative())
1984 auto UpdateRangeFromCondition = [&] (Value *Condition,
1986 CmpInst::Predicate Pred;
1988 if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
1992 CmpInst::Predicate P =
1993 TrueDest ? Pred : CmpInst::getInversePredicate(Pred);
1995 auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
1996 auto CmpConstrainedLHSRange =
1997 ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
1998 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
1999 *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);
2001 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2004 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
2008 for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
2009 Ctx->getParent()->rend())) {
2011 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
2012 UpdateRangeFromCondition(C, /*TrueDest=*/true);
2016 UpdateRangeFromGuards(NarrowUser);
2018 BasicBlock *NarrowUserBB = NarrowUser->getParent();
2019 // If NarrowUserBB is statically unreachable asking dominator queries may
2020 // yield surprising results. (e.g. the block may not have a dom tree node)
2021 if (!DT->isReachableFromEntry(NarrowUserBB))
2024 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2025 L->contains(DTB->getBlock());
2026 DTB = DTB->getIDom()) {
2027 auto *BB = DTB->getBlock();
2028 auto *TI = BB->getTerminator();
2029 UpdateRangeFromGuards(TI);
2031 auto *BI = dyn_cast<BranchInst>(TI);
2032 if (!BI || !BI->isConditional())
2035 auto *TrueSuccessor = BI->getSuccessor(0);
2036 auto *FalseSuccessor = BI->getSuccessor(1);
2038 auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
2039 return BBE.isSingleEdge() &&
2040 DT->dominates(BBE, NarrowUser->getParent());
2043 if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
2044 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
2046 if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
2047 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
2051 /// Calculates PostIncRangeInfos map for the given IV
2052 void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
2053 SmallPtrSet<Instruction *, 16> Visited;
2054 SmallVector<Instruction *, 6> Worklist;
2055 Worklist.push_back(OrigPhi);
2056 Visited.insert(OrigPhi);
2058 while (!Worklist.empty()) {
2059 Instruction *NarrowDef = Worklist.pop_back_val();
2061 for (Use &U : NarrowDef->uses()) {
2062 auto *NarrowUser = cast<Instruction>(U.getUser());
2064 // Don't go looking outside the current loop.
2065 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
2066 if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
2069 if (!Visited.insert(NarrowUser).second)
2072 Worklist.push_back(NarrowUser);
2074 calculatePostIncRange(NarrowDef, NarrowUser);
2079 PHINode *llvm::createWideIV(const WideIVInfo &WI,
2080 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,
2081 DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,
2082 unsigned &NumElimExt, unsigned &NumWidened,
2083 bool HasGuards, bool UsePostIncrementRanges) {
2084 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);
2085 PHINode *WidePHI = Widener.createWideIV(Rewriter);
2086 NumElimExt = Widener.getNumElimExt();
2087 NumWidened = Widener.getNumWidened();