contrib/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

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