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