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/LoopPass.h"
  22 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/IR/IRBuilder.h"
  26 #include "llvm/IR/Instructions.h"
  27 #include "llvm/IR/IntrinsicInst.h"
  28 #include "llvm/IR/PatternMatch.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/raw_ostream.h"
  31
  32 using namespace llvm;
  33
  34 #define DEBUG_TYPE "indvars"
  35
  36 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
  37 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
  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(NumElimCmp     , "Number of IV comparisons eliminated");
  43
  44 namespace {
  45   /// This is a utility for simplifying induction variables
  46   /// based on ScalarEvolution. It is the primary instrument of the
  47   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
  48   /// other loop passes that preserve SCEV.
  49   class SimplifyIndvar {
  50     Loop             *L;
  51     LoopInfo         *LI;
  52     ScalarEvolution  *SE;
  53     DominatorTree    *DT;
  54
  55     SmallVectorImpl<WeakTrackingVH> &DeadInsts;
  56
  57     bool Changed;
  58
  59   public:
  60     SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
  61                    LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead)
  62         : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
  63       assert(LI && "IV simplification requires LoopInfo");
  64     }
  65
  66     bool hasChanged() const { return Changed; }
  67
  68     /// Iteratively perform simplification on a worklist of users of the
  69     /// specified induction variable. This is the top-level driver that applies
  70     /// all simplifications to users of an IV.
  71     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
  72
  73     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
  74
  75     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
  76
  77     bool eliminateOverflowIntrinsic(CallInst *CI);
  78     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
  79     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
  80     void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
  81                               bool IsSigned);
  82     bool eliminateSDiv(BinaryOperator *SDiv);
  83     bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
  84     bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
  85   };
  86 }
  87
  88 /// Fold an IV operand into its use.  This removes increments of an
  89 /// aligned IV when used by a instruction that ignores the low bits.
  90 ///
  91 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
  92 ///
  93 /// Return the operand of IVOperand for this induction variable if IVOperand can
  94 /// be folded (in case more folding opportunities have been exposed).
  95 /// Otherwise return null.
  96 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
  97   Value *IVSrc = nullptr;
  98   unsigned OperIdx = 0;
  99   const SCEV *FoldedExpr = nullptr;
 100   switch (UseInst->getOpcode()) {
 101   default:
 102     return nullptr;
 103   case Instruction::UDiv:
 104   case Instruction::LShr:
 105     // We're only interested in the case where we know something about
 106     // the numerator and have a constant denominator.
 107     if (IVOperand != UseInst->getOperand(OperIdx) ||
 108         !isa<ConstantInt>(UseInst->getOperand(1)))
 109       return nullptr;
 110
 111     // Attempt to fold a binary operator with constant operand.
 112     // e.g. ((I + 1) >> 2) => I >> 2
 113     if (!isa<BinaryOperator>(IVOperand)
 114         || !isa<ConstantInt>(IVOperand->getOperand(1)))
 115       return nullptr;
 116
 117     IVSrc = IVOperand->getOperand(0);
 118     // IVSrc must be the (SCEVable) IV, since the other operand is const.
 119     assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
 120
 121     ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
 122     if (UseInst->getOpcode() == Instruction::LShr) {
 123       // Get a constant for the divisor. See createSCEV.
 124       uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
 125       if (D->getValue().uge(BitWidth))
 126         return nullptr;
 127
 128       D = ConstantInt::get(UseInst->getContext(),
 129                            APInt::getOneBitSet(BitWidth, D->getZExtValue()));
 130     }
 131     FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
 132   }
 133   // We have something that might fold it's operand. Compare SCEVs.
 134   if (!SE->isSCEVable(UseInst->getType()))
 135     return nullptr;
 136
 137   // Bypass the operand if SCEV can prove it has no effect.
 138   if (SE->getSCEV(UseInst) != FoldedExpr)
 139     return nullptr;
 140
 141   DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
 142         << " -> " << *UseInst << '\n');
 143
 144   UseInst->setOperand(OperIdx, IVSrc);
 145   assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
 146
 147   ++NumElimOperand;
 148   Changed = true;
 149   if (IVOperand->use_empty())
 150     DeadInsts.emplace_back(IVOperand);
 151   return IVSrc;
 152 }
 153
 154 /// SimplifyIVUsers helper for eliminating useless
 155 /// comparisons against an induction variable.
 156 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
 157   unsigned IVOperIdx = 0;
 158   ICmpInst::Predicate Pred = ICmp->getPredicate();
 159   ICmpInst::Predicate OriginalPred = Pred;
 160   if (IVOperand != ICmp->getOperand(0)) {
 161     // Swapped
 162     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
 163     IVOperIdx = 1;
 164     Pred = ICmpInst::getSwappedPredicate(Pred);
 165   }
 166
 167   // Get the SCEVs for the ICmp operands.
 168   const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
 169   const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
 170
 171   // Simplify unnecessary loops away.
 172   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
 173   S = SE->getSCEVAtScope(S, ICmpLoop);
 174   X = SE->getSCEVAtScope(X, ICmpLoop);
 175
 176   ICmpInst::Predicate InvariantPredicate;
 177   const SCEV *InvariantLHS, *InvariantRHS;
 178
 179   // If the condition is always true or always false, replace it with
 180   // a constant value.
 181   if (SE->isKnownPredicate(Pred, S, X)) {
 182     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
 183     DeadInsts.emplace_back(ICmp);
 184     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
 185   } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
 186     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
 187     DeadInsts.emplace_back(ICmp);
 188     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
 189   } else if (isa<PHINode>(IVOperand) &&
 190              SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
 191                                           InvariantLHS, InvariantRHS)) {
 192
 193     // Rewrite the comparison to a loop invariant comparison if it can be done
 194     // cheaply, where cheaply means "we don't need to emit any new
 195     // instructions".
 196
 197     Value *NewLHS = nullptr, *NewRHS = nullptr;
 198
 199     if (S == InvariantLHS || X == InvariantLHS)
 200       NewLHS =
 201           ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
 202
 203     if (S == InvariantRHS || X == InvariantRHS)
 204       NewRHS =
 205           ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
 206
 207     auto *PN = cast<PHINode>(IVOperand);
 208     for (unsigned i = 0, e = PN->getNumIncomingValues();
 209          i != e && (!NewLHS || !NewRHS);
 210          ++i) {
 211
 212       // If this is a value incoming from the backedge, then it cannot be a loop
 213       // invariant value (since we know that IVOperand is an induction variable).
 214       if (L->contains(PN->getIncomingBlock(i)))
 215         continue;
 216
 217       // NB! This following assert does not fundamentally have to be true, but
 218       // it is true today given how SCEV analyzes induction variables.
 219       // Specifically, today SCEV will *not* recognize %iv as an induction
 220       // variable in the following case:
 221       //
 222       // define void @f(i32 %k) {
 223       // entry:
 224       //   br i1 undef, label %r, label %l
 225       //
 226       // l:
 227       //   %k.inc.l = add i32 %k, 1
 228       //   br label %loop
 229       //
 230       // r:
 231       //   %k.inc.r = add i32 %k, 1
 232       //   br label %loop
 233       //
 234       // loop:
 235       //   %iv = phi i32 [ %k.inc.l, %l ], [ %k.inc.r, %r ], [ %iv.inc, %loop ]
 236       //   %iv.inc = add i32 %iv, 1
 237       //   br label %loop
 238       // }
 239       //
 240       // but if it starts to, at some point, then the assertion below will have
 241       // to be changed to a runtime check.
 242
 243       Value *Incoming = PN->getIncomingValue(i);
 244
 245 #ifndef NDEBUG
 246       if (auto *I = dyn_cast<Instruction>(Incoming))
 247         assert(DT->dominates(I, ICmp) && "Should be a unique loop dominating value!");
 248 #endif
 249
 250       const SCEV *IncomingS = SE->getSCEV(Incoming);
 251
 252       if (!NewLHS && IncomingS == InvariantLHS)
 253         NewLHS = Incoming;
 254       if (!NewRHS && IncomingS == InvariantRHS)
 255         NewRHS = Incoming;
 256     }
 257
 258     if (!NewLHS || !NewRHS)
 259       // We could not find an existing value to replace either LHS or RHS.
 260       // Generating new instructions has subtler tradeoffs, so avoid doing that
 261       // for now.
 262       return;
 263
 264     DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
 265     ICmp->setPredicate(InvariantPredicate);
 266     ICmp->setOperand(0, NewLHS);
 267     ICmp->setOperand(1, NewRHS);
 268   } else if (ICmpInst::isSigned(OriginalPred) &&
 269              SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
 270     // If we were unable to make anything above, all we can is to canonicalize
 271     // the comparison hoping that it will open the doors for other
 272     // optimizations. If we find out that we compare two non-negative values,
 273     // we turn the instruction's predicate to its unsigned version. Note that
 274     // we cannot rely on Pred here unless we check if we have swapped it.
 275     assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
 276     DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp << '\n');
 277     ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
 278   } else
 279     return;
 280
 281   ++NumElimCmp;
 282   Changed = true;
 283 }
 284
 285 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
 286   // Get the SCEVs for the ICmp operands.
 287   auto *N = SE->getSCEV(SDiv->getOperand(0));
 288   auto *D = SE->getSCEV(SDiv->getOperand(1));
 289
 290   // Simplify unnecessary loops away.
 291   const Loop *L = LI->getLoopFor(SDiv->getParent());
 292   N = SE->getSCEVAtScope(N, L);
 293   D = SE->getSCEVAtScope(D, L);
 294
 295   // Replace sdiv by udiv if both of the operands are non-negative
 296   if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
 297     auto *UDiv = BinaryOperator::Create(
 298         BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
 299         SDiv->getName() + ".udiv", SDiv);
 300     UDiv->setIsExact(SDiv->isExact());
 301     SDiv->replaceAllUsesWith(UDiv);
 302     DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
 303     ++NumSimplifiedSDiv;
 304     Changed = true;
 305     DeadInsts.push_back(SDiv);
 306     return true;
 307   }
 308
 309   return false;
 310 }
 311
 312 /// SimplifyIVUsers helper for eliminating useless
 313 /// remainder operations operating on an induction variable.
 314 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
 315                                       Value *IVOperand,
 316                                       bool IsSigned) {
 317   // We're only interested in the case where we know something about
 318   // the numerator.
 319   if (IVOperand != Rem->getOperand(0))
 320     return;
 321
 322   // Get the SCEVs for the ICmp operands.
 323   const SCEV *S = SE->getSCEV(Rem->getOperand(0));
 324   const SCEV *X = SE->getSCEV(Rem->getOperand(1));
 325
 326   // Simplify unnecessary loops away.
 327   const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
 328   S = SE->getSCEVAtScope(S, ICmpLoop);
 329   X = SE->getSCEVAtScope(X, ICmpLoop);
 330
 331   // i % n  -->  i  if i is in [0,n).
 332   if ((!IsSigned || SE->isKnownNonNegative(S)) &&
 333       SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 334                            S, X))
 335     Rem->replaceAllUsesWith(Rem->getOperand(0));
 336   else {
 337     // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
 338     const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType()));
 339     if (IsSigned && !SE->isKnownNonNegative(LessOne))
 340       return;
 341
 342     if (!SE->isKnownPredicate(IsSigned ?
 343                               ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 344                               LessOne, X))
 345       return;
 346
 347     ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
 348                                   Rem->getOperand(0), Rem->getOperand(1));
 349     SelectInst *Sel =
 350       SelectInst::Create(ICmp,
 351                          ConstantInt::get(Rem->getType(), 0),
 352                          Rem->getOperand(0), "tmp", Rem);
 353     Rem->replaceAllUsesWith(Sel);
 354   }
 355
 356   DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
 357   ++NumElimRem;
 358   Changed = true;
 359   DeadInsts.emplace_back(Rem);
 360 }
 361
 362 bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
 363   auto *F = CI->getCalledFunction();
 364   if (!F)
 365     return false;
 366
 367   typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
 368       const SCEV *, const SCEV *, SCEV::NoWrapFlags, unsigned);
 369   typedef const SCEV *(ScalarEvolution::*ExtensionFunctionTy)(
 370       const SCEV *, Type *, unsigned);
 371
 372   OperationFunctionTy Operation;
 373   ExtensionFunctionTy Extension;
 374
 375   Instruction::BinaryOps RawOp;
 376
 377   // We always have exactly one of nsw or nuw.  If NoSignedOverflow is false, we
 378   // have nuw.
 379   bool NoSignedOverflow;
 380
 381   switch (F->getIntrinsicID()) {
 382   default:
 383     return false;
 384
 385   case Intrinsic::sadd_with_overflow:
 386     Operation = &ScalarEvolution::getAddExpr;
 387     Extension = &ScalarEvolution::getSignExtendExpr;
 388     RawOp = Instruction::Add;
 389     NoSignedOverflow = true;
 390     break;
 391
 392   case Intrinsic::uadd_with_overflow:
 393     Operation = &ScalarEvolution::getAddExpr;
 394     Extension = &ScalarEvolution::getZeroExtendExpr;
 395     RawOp = Instruction::Add;
 396     NoSignedOverflow = false;
 397     break;
 398
 399   case Intrinsic::ssub_with_overflow:
 400     Operation = &ScalarEvolution::getMinusSCEV;
 401     Extension = &ScalarEvolution::getSignExtendExpr;
 402     RawOp = Instruction::Sub;
 403     NoSignedOverflow = true;
 404     break;
 405
 406   case Intrinsic::usub_with_overflow:
 407     Operation = &ScalarEvolution::getMinusSCEV;
 408     Extension = &ScalarEvolution::getZeroExtendExpr;
 409     RawOp = Instruction::Sub;
 410     NoSignedOverflow = false;
 411     break;
 412   }
 413
 414   const SCEV *LHS = SE->getSCEV(CI->getArgOperand(0));
 415   const SCEV *RHS = SE->getSCEV(CI->getArgOperand(1));
 416
 417   auto *NarrowTy = cast<IntegerType>(LHS->getType());
 418   auto *WideTy =
 419     IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
 420
 421   const SCEV *A =
 422       (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0),
 423                        WideTy, 0);
 424   const SCEV *B =
 425       (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0),
 426                        (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0);
 427
 428   if (A != B)
 429     return false;
 430
 431   // Proved no overflow, nuke the overflow check and, if possible, the overflow
 432   // intrinsic as well.
 433
 434   BinaryOperator *NewResult = BinaryOperator::Create(
 435       RawOp, CI->getArgOperand(0), CI->getArgOperand(1), "", CI);
 436
 437   if (NoSignedOverflow)
 438     NewResult->setHasNoSignedWrap(true);
 439   else
 440     NewResult->setHasNoUnsignedWrap(true);
 441
 442   SmallVector<ExtractValueInst *, 4> ToDelete;
 443
 444   for (auto *U : CI->users()) {
 445     if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
 446       if (EVI->getIndices()[0] == 1)
 447         EVI->replaceAllUsesWith(ConstantInt::getFalse(CI->getContext()));
 448       else {
 449         assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
 450         EVI->replaceAllUsesWith(NewResult);
 451       }
 452       ToDelete.push_back(EVI);
 453     }
 454   }
 455
 456   for (auto *EVI : ToDelete)
 457     EVI->eraseFromParent();
 458
 459   if (CI->use_empty())
 460     CI->eraseFromParent();
 461
 462   return true;
 463 }
 464
 465 /// Eliminate an operation that consumes a simple IV and has no observable
 466 /// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
 467 /// but UseInst may not be.
 468 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
 469                                      Instruction *IVOperand) {
 470   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
 471     eliminateIVComparison(ICmp, IVOperand);
 472     return true;
 473   }
 474   if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
 475     bool IsSRem = Bin->getOpcode() == Instruction::SRem;
 476     if (IsSRem || Bin->getOpcode() == Instruction::URem) {
 477       eliminateIVRemainder(Bin, IVOperand, IsSRem);
 478       return true;
 479     }
 480
 481     if (Bin->getOpcode() == Instruction::SDiv)
 482       return eliminateSDiv(Bin);
 483   }
 484
 485   if (auto *CI = dyn_cast<CallInst>(UseInst))
 486     if (eliminateOverflowIntrinsic(CI))
 487       return true;
 488
 489   if (eliminateIdentitySCEV(UseInst, IVOperand))
 490     return true;
 491
 492   return false;
 493 }
 494
 495 /// Eliminate any operation that SCEV can prove is an identity function.
 496 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
 497                                            Instruction *IVOperand) {
 498   if (!SE->isSCEVable(UseInst->getType()) ||
 499       (UseInst->getType() != IVOperand->getType()) ||
 500       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
 501     return false;
 502
 503   // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
 504   // dominator tree, even if X is an operand to Y.  For instance, in
 505   //
 506   //     %iv = phi i32 {0,+,1}
 507   //     br %cond, label %left, label %merge
 508   //
 509   //   left:
 510   //     %X = add i32 %iv, 0
 511   //     br label %merge
 512   //
 513   //   merge:
 514   //     %M = phi (%X, %iv)
 515   //
 516   // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
 517   // %M.replaceAllUsesWith(%X) would be incorrect.
 518
 519   if (isa<PHINode>(UseInst))
 520     // If UseInst is not a PHI node then we know that IVOperand dominates
 521     // UseInst directly from the legality of SSA.
 522     if (!DT || !DT->dominates(IVOperand, UseInst))
 523       return false;
 524
 525   if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
 526     return false;
 527
 528   DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
 529
 530   UseInst->replaceAllUsesWith(IVOperand);
 531   ++NumElimIdentity;
 532   Changed = true;
 533   DeadInsts.emplace_back(UseInst);
 534   return true;
 535 }
 536
 537 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
 538 /// unsigned-overflow.  Returns true if anything changed, false otherwise.
 539 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
 540                                                     Value *IVOperand) {
 541
 542   // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
 543   if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
 544     return false;
 545
 546   const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
 547                                                SCEV::NoWrapFlags, unsigned);
 548   switch (BO->getOpcode()) {
 549   default:
 550     return false;
 551
 552   case Instruction::Add:
 553     GetExprForBO = &ScalarEvolution::getAddExpr;
 554     break;
 555
 556   case Instruction::Sub:
 557     GetExprForBO = &ScalarEvolution::getMinusSCEV;
 558     break;
 559
 560   case Instruction::Mul:
 561     GetExprForBO = &ScalarEvolution::getMulExpr;
 562     break;
 563   }
 564
 565   unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
 566   Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
 567   const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
 568   const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
 569
 570   bool Changed = false;
 571
 572   if (!BO->hasNoUnsignedWrap()) {
 573     const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
 574     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
 575       SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
 576       SCEV::FlagAnyWrap, 0u);
 577     if (ExtendAfterOp == OpAfterExtend) {
 578       BO->setHasNoUnsignedWrap();
 579       SE->forgetValue(BO);
 580       Changed = true;
 581     }
 582   }
 583
 584   if (!BO->hasNoSignedWrap()) {
 585     const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
 586     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
 587       SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
 588       SCEV::FlagAnyWrap, 0u);
 589     if (ExtendAfterOp == OpAfterExtend) {
 590       BO->setHasNoSignedWrap();
 591       SE->forgetValue(BO);
 592       Changed = true;
 593     }
 594   }
 595
 596   return Changed;
 597 }
 598
 599 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
 600 /// information from the IV's range. Returns true if anything changed, false
 601 /// otherwise.
 602 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
 603                                           Value *IVOperand) {
 604   using namespace llvm::PatternMatch;
 605
 606   if (BO->getOpcode() == Instruction::Shl) {
 607     bool Changed = false;
 608     ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
 609     for (auto *U : BO->users()) {
 610       const APInt *C;
 611       if (match(U,
 612                 m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
 613           match(U,
 614                 m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
 615         BinaryOperator *Shr = cast<BinaryOperator>(U);
 616         if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
 617           Shr->setIsExact(true);
 618           Changed = true;
 619         }
 620       }
 621     }
 622     return Changed;
 623   }
 624
 625   return false;
 626 }
 627
 628 /// Add all uses of Def to the current IV's worklist.
 629 static void pushIVUsers(
 630   Instruction *Def,
 631   SmallPtrSet<Instruction*,16> &Simplified,
 632   SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
 633
 634   for (User *U : Def->users()) {
 635     Instruction *UI = cast<Instruction>(U);
 636
 637     // Avoid infinite or exponential worklist processing.
 638     // Also ensure unique worklist users.
 639     // If Def is a LoopPhi, it may not be in the Simplified set, so check for
 640     // self edges first.
 641     if (UI != Def && Simplified.insert(UI).second)
 642       SimpleIVUsers.push_back(std::make_pair(UI, Def));
 643   }
 644 }
 645
 646 /// Return true if this instruction generates a simple SCEV
 647 /// expression in terms of that IV.
 648 ///
 649 /// This is similar to IVUsers' isInteresting() but processes each instruction
 650 /// non-recursively when the operand is already known to be a simpleIVUser.
 651 ///
 652 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
 653   if (!SE->isSCEVable(I->getType()))
 654     return false;
 655
 656   // Get the symbolic expression for this instruction.
 657   const SCEV *S = SE->getSCEV(I);
 658
 659   // Only consider affine recurrences.
 660   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
 661   if (AR && AR->getLoop() == L)
 662     return true;
 663
 664   return false;
 665 }
 666
 667 /// Iteratively perform simplification on a worklist of users
 668 /// of the specified induction variable. Each successive simplification may push
 669 /// more users which may themselves be candidates for simplification.
 670 ///
 671 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
 672 /// instructions in-place during analysis. Rather than rewriting induction
 673 /// variables bottom-up from their users, it transforms a chain of IVUsers
 674 /// top-down, updating the IR only when it encounters a clear optimization
 675 /// opportunity.
 676 ///
 677 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
 678 ///
 679 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
 680   if (!SE->isSCEVable(CurrIV->getType()))
 681     return;
 682
 683   // Instructions processed by SimplifyIndvar for CurrIV.
 684   SmallPtrSet<Instruction*,16> Simplified;
 685
 686   // Use-def pairs if IV users waiting to be processed for CurrIV.
 687   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
 688
 689   // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
 690   // called multiple times for the same LoopPhi. This is the proper thing to
 691   // do for loop header phis that use each other.
 692   pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
 693
 694   while (!SimpleIVUsers.empty()) {
 695     std::pair<Instruction*, Instruction*> UseOper =
 696       SimpleIVUsers.pop_back_val();
 697     Instruction *UseInst = UseOper.first;
 698
 699     // Bypass back edges to avoid extra work.
 700     if (UseInst == CurrIV) continue;
 701
 702     Instruction *IVOperand = UseOper.second;
 703     for (unsigned N = 0; IVOperand; ++N) {
 704       assert(N <= Simplified.size() && "runaway iteration");
 705
 706       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
 707       if (!NewOper)
 708         break; // done folding
 709       IVOperand = dyn_cast<Instruction>(NewOper);
 710     }
 711     if (!IVOperand)
 712       continue;
 713
 714     if (eliminateIVUser(UseOper.first, IVOperand)) {
 715       pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
 716       continue;
 717     }
 718
 719     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
 720       if ((isa<OverflowingBinaryOperator>(BO) &&
 721            strengthenOverflowingOperation(BO, IVOperand)) ||
 722           (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
 723         // re-queue uses of the now modified binary operator and fall
 724         // through to the checks that remain.
 725         pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
 726       }
 727     }
 728
 729     CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
 730     if (V && Cast) {
 731       V->visitCast(Cast);
 732       continue;
 733     }
 734     if (isSimpleIVUser(UseOper.first, L, SE)) {
 735       pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
 736     }
 737   }
 738 }
 739
 740 namespace llvm {
 741
 742 void IVVisitor::anchor() { }
 743
 744 /// Simplify instructions that use this induction variable
 745 /// by using ScalarEvolution to analyze the IV's recurrence.
 746 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
 747                        LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead,
 748                        IVVisitor *V) {
 749   SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
 750   SIV.simplifyUsers(CurrIV, V);
 751   return SIV.hasChanged();
 752 }
 753
 754 /// Simplify users of induction variables within this
 755 /// loop. This does not actually change or add IVs.
 756 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
 757                      LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead) {
 758   bool Changed = false;
 759   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
 760     Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead);
 761   }
 762   return Changed;
 763 }
 764
 765 } // namespace llvm