lib/Transforms/Utils/SimplifyIndVar.cpp

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