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