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