//===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements induction variable simplification. It does
// not define any actual pass or policy, but provides a single function to
// simplify a loop's induction variables based on ScalarEvolution.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

using namespace llvm;

#define DEBUG_TYPE "indvars"

STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
STATISTIC(
    NumSimplifiedSDiv,
    "Number of IV signed division operations converted to unsigned division");
STATISTIC(
    NumSimplifiedSRem,
    "Number of IV signed remainder operations converted to unsigned remainder");
STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");

namespace {
  /// This is a utility for simplifying induction variables
  /// based on ScalarEvolution. It is the primary instrument of the
  /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
  /// other loop passes that preserve SCEV.
  class SimplifyIndvar {
    Loop             *L;
    LoopInfo         *LI;
    ScalarEvolution  *SE;
    DominatorTree    *DT;
    const TargetTransformInfo *TTI;
    SCEVExpander     &Rewriter;
    SmallVectorImpl<WeakTrackingVH> &DeadInsts;

    bool Changed;

  public:
    SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
                   LoopInfo *LI, const TargetTransformInfo *TTI,
                   SCEVExpander &Rewriter,
                   SmallVectorImpl<WeakTrackingVH> &Dead)
        : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),
          DeadInsts(Dead), Changed(false) {
      assert(LI && "IV simplification requires LoopInfo");
    }

    bool hasChanged() const { return Changed; }

    /// Iteratively perform simplification on a worklist of users of the
    /// specified induction variable. This is the top-level driver that applies
    /// all simplifications to users of an IV.
    void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);

    Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);

    bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
    bool replaceIVUserWithLoopInvariant(Instruction *UseInst);

    bool eliminateOverflowIntrinsic(WithOverflowInst *WO);
    bool eliminateSaturatingIntrinsic(SaturatingInst *SI);
    bool eliminateTrunc(TruncInst *TI);
    bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
    bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
    void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
    void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                             bool IsSigned);
    void replaceRemWithNumerator(BinaryOperator *Rem);
    void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
    void replaceSRemWithURem(BinaryOperator *Rem);
    bool eliminateSDiv(BinaryOperator *SDiv);
    bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
    bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
  };
}

/// Find a point in code which dominates all given instructions. We can safely
/// assume that, whatever fact we can prove at the found point, this fact is
/// also true for each of the given instructions.
static Instruction *findCommonDominator(ArrayRef<Instruction *> Instructions,
                                        DominatorTree &DT) {
  Instruction *CommonDom = nullptr;
  for (auto *Insn : Instructions)
    if (!CommonDom || DT.dominates(Insn, CommonDom))
      CommonDom = Insn;
    else if (!DT.dominates(CommonDom, Insn))
      // If there is no dominance relation, use common dominator.
      CommonDom =
          DT.findNearestCommonDominator(CommonDom->getParent(),
                                        Insn->getParent())->getTerminator();
  assert(CommonDom && "Common dominator not found?");
  return CommonDom;
}

/// Fold an IV operand into its use.  This removes increments of an
/// aligned IV when used by a instruction that ignores the low bits.
///
/// IVOperand is guaranteed SCEVable, but UseInst may not be.
///
/// Return the operand of IVOperand for this induction variable if IVOperand can
/// be folded (in case more folding opportunities have been exposed).
/// Otherwise return null.
Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
  Value *IVSrc = nullptr;
  const unsigned OperIdx = 0;
  const SCEV *FoldedExpr = nullptr;
  bool MustDropExactFlag = false;
  switch (UseInst->getOpcode()) {
  default:
    return nullptr;
  case Instruction::UDiv:
  case Instruction::LShr:
    // We're only interested in the case where we know something about
    // the numerator and have a constant denominator.
    if (IVOperand != UseInst->getOperand(OperIdx) ||
        !isa<ConstantInt>(UseInst->getOperand(1)))
      return nullptr;

    // Attempt to fold a binary operator with constant operand.
    // e.g. ((I + 1) >> 2) => I >> 2
    if (!isa<BinaryOperator>(IVOperand)
        || !isa<ConstantInt>(IVOperand->getOperand(1)))
      return nullptr;

    IVSrc = IVOperand->getOperand(0);
    // IVSrc must be the (SCEVable) IV, since the other operand is const.
    assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");

    ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
    if (UseInst->getOpcode() == Instruction::LShr) {
      // Get a constant for the divisor. See createSCEV.
      uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
      if (D->getValue().uge(BitWidth))
        return nullptr;

      D = ConstantInt::get(UseInst->getContext(),
                           APInt::getOneBitSet(BitWidth, D->getZExtValue()));
    }
    FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
    // We might have 'exact' flag set at this point which will no longer be
    // correct after we make the replacement.
    if (UseInst->isExact() &&
        SE->getSCEV(IVSrc) != SE->getMulExpr(FoldedExpr, SE->getSCEV(D)))
      MustDropExactFlag = true;
  }
  // We have something that might fold it's operand. Compare SCEVs.
  if (!SE->isSCEVable(UseInst->getType()))
    return nullptr;

  // Bypass the operand if SCEV can prove it has no effect.
  if (SE->getSCEV(UseInst) != FoldedExpr)
    return nullptr;

  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
                    << " -> " << *UseInst << '\n');

  UseInst->setOperand(OperIdx, IVSrc);
  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");

  if (MustDropExactFlag)
    UseInst->dropPoisonGeneratingFlags();

  ++NumElimOperand;
  Changed = true;
  if (IVOperand->use_empty())
    DeadInsts.emplace_back(IVOperand);
  return IVSrc;
}

bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
                                               Value *IVOperand) {
  unsigned IVOperIdx = 0;
  ICmpInst::Predicate Pred = ICmp->getPredicate();
  if (IVOperand != ICmp->getOperand(0)) {
    // Swapped
    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
    IVOperIdx = 1;
    Pred = ICmpInst::getSwappedPredicate(Pred);
  }

  // Get the SCEVs for the ICmp operands (in the specific context of the
  // current loop)
  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);

  auto *PN = dyn_cast<PHINode>(IVOperand);
  if (!PN)
    return false;
  auto LIP = SE->getLoopInvariantPredicate(Pred, S, X, L);
  if (!LIP)
    return false;
  ICmpInst::Predicate InvariantPredicate = LIP->Pred;
  const SCEV *InvariantLHS = LIP->LHS;
  const SCEV *InvariantRHS = LIP->RHS;

  // Rewrite the comparison to a loop invariant comparison if it can be done
  // cheaply, where cheaply means "we don't need to emit any new
  // instructions".

  SmallDenseMap<const SCEV*, Value*> CheapExpansions;
  CheapExpansions[S] = ICmp->getOperand(IVOperIdx);
  CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx);

  // TODO: Support multiple entry loops?  (We currently bail out of these in
  // the IndVarSimplify pass)
  if (auto *BB = L->getLoopPredecessor()) {
    const int Idx = PN->getBasicBlockIndex(BB);
    if (Idx >= 0) {
      Value *Incoming = PN->getIncomingValue(Idx);
      const SCEV *IncomingS = SE->getSCEV(Incoming);
      CheapExpansions[IncomingS] = Incoming;
    }
  }
  Value *NewLHS = CheapExpansions[InvariantLHS];
  Value *NewRHS = CheapExpansions[InvariantRHS];

  if (!NewLHS)
    if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
      NewLHS = ConstLHS->getValue();
  if (!NewRHS)
    if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
      NewRHS = ConstRHS->getValue();

  if (!NewLHS || !NewRHS)
    // We could not find an existing value to replace either LHS or RHS.
    // Generating new instructions has subtler tradeoffs, so avoid doing that
    // for now.
    return false;

  LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
  ICmp->setPredicate(InvariantPredicate);
  ICmp->setOperand(0, NewLHS);
  ICmp->setOperand(1, NewRHS);
  return true;
}

/// SimplifyIVUsers helper for eliminating useless
/// comparisons against an induction variable.
void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
  unsigned IVOperIdx = 0;
  ICmpInst::Predicate Pred = ICmp->getPredicate();
  ICmpInst::Predicate OriginalPred = Pred;
  if (IVOperand != ICmp->getOperand(0)) {
    // Swapped
    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
    IVOperIdx = 1;
    Pred = ICmpInst::getSwappedPredicate(Pred);
  }

  // Get the SCEVs for the ICmp operands (in the specific context of the
  // current loop)
  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);

  // If the condition is always true or always false in the given context,
  // replace it with a constant value.
  SmallVector<Instruction *, 4> Users;
  for (auto *U : ICmp->users())
    Users.push_back(cast<Instruction>(U));
  const Instruction *CtxI = findCommonDominator(Users, *DT);
  if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {
    ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));
    DeadInsts.emplace_back(ICmp);
    LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
  } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
    // fallthrough to end of function
  } else if (ICmpInst::isSigned(OriginalPred) &&
             SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
    // If we were unable to make anything above, all we can is to canonicalize
    // the comparison hoping that it will open the doors for other
    // optimizations. If we find out that we compare two non-negative values,
    // we turn the instruction's predicate to its unsigned version. Note that
    // we cannot rely on Pred here unless we check if we have swapped it.
    assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
    LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp
                      << '\n');
    ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
  } else
    return;

  ++NumElimCmp;
  Changed = true;
}

bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
  // Get the SCEVs for the ICmp operands.
  auto *N = SE->getSCEV(SDiv->getOperand(0));
  auto *D = SE->getSCEV(SDiv->getOperand(1));

  // Simplify unnecessary loops away.
  const Loop *L = LI->getLoopFor(SDiv->getParent());
  N = SE->getSCEVAtScope(N, L);
  D = SE->getSCEVAtScope(D, L);

  // Replace sdiv by udiv if both of the operands are non-negative
  if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
    auto *UDiv = BinaryOperator::Create(
        BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
        SDiv->getName() + ".udiv", SDiv);
    UDiv->setIsExact(SDiv->isExact());
    SDiv->replaceAllUsesWith(UDiv);
    LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
    ++NumSimplifiedSDiv;
    Changed = true;
    DeadInsts.push_back(SDiv);
    return true;
  }

  return false;
}

// i %s n -> i %u n if i >= 0 and n >= 0
void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
  auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
                                      Rem->getName() + ".urem", Rem);
  Rem->replaceAllUsesWith(URem);
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
  ++NumSimplifiedSRem;
  Changed = true;
  DeadInsts.emplace_back(Rem);
}

// i % n  -->  i  if i is in [0,n).
void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
  Rem->replaceAllUsesWith(Rem->getOperand(0));
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
  ++NumElimRem;
  Changed = true;
  DeadInsts.emplace_back(Rem);
}

// (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
  auto *T = Rem->getType();
  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
  ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
  SelectInst *Sel =
      SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
  Rem->replaceAllUsesWith(Sel);
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
  ++NumElimRem;
  Changed = true;
  DeadInsts.emplace_back(Rem);
}

/// SimplifyIVUsers helper for eliminating useless remainder operations
/// operating on an induction variable or replacing srem by urem.
void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                                         bool IsSigned) {
  auto *NValue = Rem->getOperand(0);
  auto *DValue = Rem->getOperand(1);
  // We're only interested in the case where we know something about
  // the numerator, unless it is a srem, because we want to replace srem by urem
  // in general.
  bool UsedAsNumerator = IVOperand == NValue;
  if (!UsedAsNumerator && !IsSigned)
    return;

  const SCEV *N = SE->getSCEV(NValue);

  // Simplify unnecessary loops away.
  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
  N = SE->getSCEVAtScope(N, ICmpLoop);

  bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);

  // Do not proceed if the Numerator may be negative
  if (!IsNumeratorNonNegative)
    return;

  const SCEV *D = SE->getSCEV(DValue);
  D = SE->getSCEVAtScope(D, ICmpLoop);

  if (UsedAsNumerator) {
    auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
    if (SE->isKnownPredicate(LT, N, D)) {
      replaceRemWithNumerator(Rem);
      return;
    }

    auto *T = Rem->getType();
    const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
    if (SE->isKnownPredicate(LT, NLessOne, D)) {
      replaceRemWithNumeratorOrZero(Rem);
      return;
    }
  }

  // Try to replace SRem with URem, if both N and D are known non-negative.
  // Since we had already check N, we only need to check D now
  if (!IsSigned || !SE->isKnownNonNegative(D))
    return;

  replaceSRemWithURem(Rem);
}

bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
  const SCEV *LHS = SE->getSCEV(WO->getLHS());
  const SCEV *RHS = SE->getSCEV(WO->getRHS());
  if (!SE->willNotOverflow(WO->getBinaryOp(), WO->isSigned(), LHS, RHS))
    return false;

  // Proved no overflow, nuke the overflow check and, if possible, the overflow
  // intrinsic as well.

  BinaryOperator *NewResult = BinaryOperator::Create(
      WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO);

  if (WO->isSigned())
    NewResult->setHasNoSignedWrap(true);
  else
    NewResult->setHasNoUnsignedWrap(true);

  SmallVector<ExtractValueInst *, 4> ToDelete;

  for (auto *U : WO->users()) {
    if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
      if (EVI->getIndices()[0] == 1)
        EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));
      else {
        assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
        EVI->replaceAllUsesWith(NewResult);
      }
      ToDelete.push_back(EVI);
    }
  }

  for (auto *EVI : ToDelete)
    EVI->eraseFromParent();

  if (WO->use_empty())
    WO->eraseFromParent();

  Changed = true;
  return true;
}

bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
  const SCEV *LHS = SE->getSCEV(SI->getLHS());
  const SCEV *RHS = SE->getSCEV(SI->getRHS());
  if (!SE->willNotOverflow(SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
    return false;

  BinaryOperator *BO = BinaryOperator::Create(
      SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
  if (SI->isSigned())
    BO->setHasNoSignedWrap();
  else
    BO->setHasNoUnsignedWrap();

  SI->replaceAllUsesWith(BO);
  DeadInsts.emplace_back(SI);
  Changed = true;
  return true;
}

bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
  // It is always legal to replace
  //   icmp <pred> i32 trunc(iv), n
  // with
  //   icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
  // Or with
  //   icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
  // Or with either of these if pred is an equality predicate.
  //
  // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
  // every comparison which uses trunc, it means that we can replace each of
  // them with comparison of iv against sext/zext(n). We no longer need trunc
  // after that.
  //
  // TODO: Should we do this if we can widen *some* comparisons, but not all
  // of them? Sometimes it is enough to enable other optimizations, but the
  // trunc instruction will stay in the loop.
  Value *IV = TI->getOperand(0);
  Type *IVTy = IV->getType();
  const SCEV *IVSCEV = SE->getSCEV(IV);
  const SCEV *TISCEV = SE->getSCEV(TI);

  // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
  // get rid of trunc
  bool DoesSExtCollapse = false;
  bool DoesZExtCollapse = false;
  if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
    DoesSExtCollapse = true;
  if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
    DoesZExtCollapse = true;

  // If neither sext nor zext does collapse, it is not profitable to do any
  // transform. Bail.
  if (!DoesSExtCollapse && !DoesZExtCollapse)
    return false;

  // Collect users of the trunc that look like comparisons against invariants.
  // Bail if we find something different.
  SmallVector<ICmpInst *, 4> ICmpUsers;
  for (auto *U : TI->users()) {
    // We don't care about users in unreachable blocks.
    if (isa<Instruction>(U) &&
        !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
      continue;
    ICmpInst *ICI = dyn_cast<ICmpInst>(U);
    if (!ICI) return false;
    assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
    if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&
        !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))
      return false;
    // If we cannot get rid of trunc, bail.
    if (ICI->isSigned() && !DoesSExtCollapse)
      return false;
    if (ICI->isUnsigned() && !DoesZExtCollapse)
      return false;
    // For equality, either signed or unsigned works.
    ICmpUsers.push_back(ICI);
  }

  auto CanUseZExt = [&](ICmpInst *ICI) {
    // Unsigned comparison can be widened as unsigned.
    if (ICI->isUnsigned())
      return true;
    // Is it profitable to do zext?
    if (!DoesZExtCollapse)
      return false;
    // For equality, we can safely zext both parts.
    if (ICI->isEquality())
      return true;
    // Otherwise we can only use zext when comparing two non-negative or two
    // negative values. But in practice, we will never pass DoesZExtCollapse
    // check for a negative value, because zext(trunc(x)) is non-negative. So
    // it only make sense to check for non-negativity here.
    const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
    const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
    return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
  };
  // Replace all comparisons against trunc with comparisons against IV.
  for (auto *ICI : ICmpUsers) {
    bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
    auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);
    Instruction *Ext = nullptr;
    // For signed/unsigned predicate, replace the old comparison with comparison
    // of immediate IV against sext/zext of the invariant argument. If we can
    // use either sext or zext (i.e. we are dealing with equality predicate),
    // then prefer zext as a more canonical form.
    // TODO: If we see a signed comparison which can be turned into unsigned,
    // we can do it here for canonicalization purposes.
    ICmpInst::Predicate Pred = ICI->getPredicate();
    if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
    if (CanUseZExt(ICI)) {
      assert(DoesZExtCollapse && "Unprofitable zext?");
      Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
      Pred = ICmpInst::getUnsignedPredicate(Pred);
    } else {
      assert(DoesSExtCollapse && "Unprofitable sext?");
      Ext = new SExtInst(Op1, IVTy, "sext", ICI);
      assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
    }
    bool Changed;
    L->makeLoopInvariant(Ext, Changed);
    (void)Changed;
    ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
    ICI->replaceAllUsesWith(NewICI);
    DeadInsts.emplace_back(ICI);
  }

  // Trunc no longer needed.
  TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
  DeadInsts.emplace_back(TI);
  return true;
}

/// Eliminate an operation that consumes a simple IV and has no observable
/// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
/// but UseInst may not be.
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
                                     Instruction *IVOperand) {
  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
    eliminateIVComparison(ICmp, IVOperand);
    return true;
  }
  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
    bool IsSRem = Bin->getOpcode() == Instruction::SRem;
    if (IsSRem || Bin->getOpcode() == Instruction::URem) {
      simplifyIVRemainder(Bin, IVOperand, IsSRem);
      return true;
    }

    if (Bin->getOpcode() == Instruction::SDiv)
      return eliminateSDiv(Bin);
  }

  if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
    if (eliminateOverflowIntrinsic(WO))
      return true;

  if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
    if (eliminateSaturatingIntrinsic(SI))
      return true;

  if (auto *TI = dyn_cast<TruncInst>(UseInst))
    if (eliminateTrunc(TI))
      return true;

  if (eliminateIdentitySCEV(UseInst, IVOperand))
    return true;

  return false;
}

static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
  if (auto *BB = L->getLoopPreheader())
    return BB->getTerminator();

  return Hint;
}

/// Replace the UseInst with a loop invariant expression if it is safe.
bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
  if (!SE->isSCEVable(I->getType()))
    return false;

  // Get the symbolic expression for this instruction.
  const SCEV *S = SE->getSCEV(I);

  if (!SE->isLoopInvariant(S, L))
    return false;

  // Do not generate something ridiculous even if S is loop invariant.
  if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
    return false;

  auto *IP = GetLoopInvariantInsertPosition(L, I);

  if (!isSafeToExpandAt(S, IP, *SE)) {
    LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
                      << " with non-speculable loop invariant: " << *S << '\n');
    return false;
  }

  auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);

  I->replaceAllUsesWith(Invariant);
  LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
                    << " with loop invariant: " << *S << '\n');
  ++NumFoldedUser;
  Changed = true;
  DeadInsts.emplace_back(I);
  return true;
}

/// Eliminate any operation that SCEV can prove is an identity function.
bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
                                           Instruction *IVOperand) {
  if (!SE->isSCEVable(UseInst->getType()) ||
      (UseInst->getType() != IVOperand->getType()) ||
      (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
    return false;

  // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
  // dominator tree, even if X is an operand to Y.  For instance, in
  //
  //     %iv = phi i32 {0,+,1}
  //     br %cond, label %left, label %merge
  //
  //   left:
  //     %X = add i32 %iv, 0
  //     br label %merge
  //
  //   merge:
  //     %M = phi (%X, %iv)
  //
  // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
  // %M.replaceAllUsesWith(%X) would be incorrect.

  if (isa<PHINode>(UseInst))
    // If UseInst is not a PHI node then we know that IVOperand dominates
    // UseInst directly from the legality of SSA.
    if (!DT || !DT->dominates(IVOperand, UseInst))
      return false;

  if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
    return false;

  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');

  UseInst->replaceAllUsesWith(IVOperand);
  ++NumElimIdentity;
  Changed = true;
  DeadInsts.emplace_back(UseInst);
  return true;
}

/// Annotate BO with nsw / nuw if it provably does not signed-overflow /
/// unsigned-overflow.  Returns true if anything changed, false otherwise.
bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
                                                    Value *IVOperand) {
  SCEV::NoWrapFlags Flags;
  bool Deduced;
  std::tie(Flags, Deduced) = SE->getStrengthenedNoWrapFlagsFromBinOp(
      cast<OverflowingBinaryOperator>(BO));

  if (!Deduced)
    return Deduced;

  BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(Flags, SCEV::FlagNUW) ==
                           SCEV::FlagNUW);
  BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(Flags, SCEV::FlagNSW) ==
                         SCEV::FlagNSW);

  // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap
  // flags on addrecs while performing zero/sign extensions. We could call
  // forgetValue() here to make sure those flags also propagate to any other
  // SCEV expressions based on the addrec. However, this can have pathological
  // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.
  return Deduced;
}

/// Annotate the Shr in (X << IVOperand) >> C as exact using the
/// information from the IV's range. Returns true if anything changed, false
/// otherwise.
bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
                                          Value *IVOperand) {
  using namespace llvm::PatternMatch;

  if (BO->getOpcode() == Instruction::Shl) {
    bool Changed = false;
    ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
    for (auto *U : BO->users()) {
      const APInt *C;
      if (match(U,
                m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
          match(U,
                m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
        BinaryOperator *Shr = cast<BinaryOperator>(U);
        if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
          Shr->setIsExact(true);
          Changed = true;
        }
      }
    }
    return Changed;
  }

  return false;
}

/// Add all uses of Def to the current IV's worklist.
static void pushIVUsers(
  Instruction *Def, Loop *L,
  SmallPtrSet<Instruction*,16> &Simplified,
  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {

  for (User *U : Def->users()) {
    Instruction *UI = cast<Instruction>(U);

    // Avoid infinite or exponential worklist processing.
    // Also ensure unique worklist users.
    // If Def is a LoopPhi, it may not be in the Simplified set, so check for
    // self edges first.
    if (UI == Def)
      continue;

    // Only change the current Loop, do not change the other parts (e.g. other
    // Loops).
    if (!L->contains(UI))
      continue;

    // Do not push the same instruction more than once.
    if (!Simplified.insert(UI).second)
      continue;

    SimpleIVUsers.push_back(std::make_pair(UI, Def));
  }
}

/// Return true if this instruction generates a simple SCEV
/// expression in terms of that IV.
///
/// This is similar to IVUsers' isInteresting() but processes each instruction
/// non-recursively when the operand is already known to be a simpleIVUser.
///
static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
  if (!SE->isSCEVable(I->getType()))
    return false;

  // Get the symbolic expression for this instruction.
  const SCEV *S = SE->getSCEV(I);

  // Only consider affine recurrences.
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
  if (AR && AR->getLoop() == L)
    return true;

  return false;
}

/// Iteratively perform simplification on a worklist of users
/// of the specified induction variable. Each successive simplification may push
/// more users which may themselves be candidates for simplification.
///
/// This algorithm does not require IVUsers analysis. Instead, it simplifies
/// instructions in-place during analysis. Rather than rewriting induction
/// variables bottom-up from their users, it transforms a chain of IVUsers
/// top-down, updating the IR only when it encounters a clear optimization
/// opportunity.
///
/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
///
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
  if (!SE->isSCEVable(CurrIV->getType()))
    return;

  // Instructions processed by SimplifyIndvar for CurrIV.
  SmallPtrSet<Instruction*,16> Simplified;

  // Use-def pairs if IV users waiting to be processed for CurrIV.
  SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;

  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
  // called multiple times for the same LoopPhi. This is the proper thing to
  // do for loop header phis that use each other.
  pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);

  while (!SimpleIVUsers.empty()) {
    std::pair<Instruction*, Instruction*> UseOper =
      SimpleIVUsers.pop_back_val();
    Instruction *UseInst = UseOper.first;

    // If a user of the IndVar is trivially dead, we prefer just to mark it dead
    // rather than try to do some complex analysis or transformation (such as
    // widening) basing on it.
    // TODO: Propagate TLI and pass it here to handle more cases.
    if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
      DeadInsts.emplace_back(UseInst);
      continue;
    }

    // Bypass back edges to avoid extra work.
    if (UseInst == CurrIV) continue;

    // Try to replace UseInst with a loop invariant before any other
    // simplifications.
    if (replaceIVUserWithLoopInvariant(UseInst))
      continue;

    Instruction *IVOperand = UseOper.second;
    for (unsigned N = 0; IVOperand; ++N) {
      assert(N <= Simplified.size() && "runaway iteration");

      Value *NewOper = foldIVUser(UseInst, IVOperand);
      if (!NewOper)
        break; // done folding
      IVOperand = dyn_cast<Instruction>(NewOper);
    }
    if (!IVOperand)
      continue;

    if (eliminateIVUser(UseInst, IVOperand)) {
      pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
      continue;
    }

    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
      if ((isa<OverflowingBinaryOperator>(BO) &&
           strengthenOverflowingOperation(BO, IVOperand)) ||
          (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
        // re-queue uses of the now modified binary operator and fall
        // through to the checks that remain.
        pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
      }
    }

    CastInst *Cast = dyn_cast<CastInst>(UseInst);
    if (V && Cast) {
      V->visitCast(Cast);
      continue;
    }
    if (isSimpleIVUser(UseInst, L, SE)) {
      pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
    }
  }
}

namespace llvm {

void IVVisitor::anchor() { }

/// Simplify instructions that use this induction variable
/// by using ScalarEvolution to analyze the IV's recurrence.
bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
                       LoopInfo *LI, const TargetTransformInfo *TTI,
                       SmallVectorImpl<WeakTrackingVH> &Dead,
                       SCEVExpander &Rewriter, IVVisitor *V) {
  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,
                     Rewriter, Dead);
  SIV.simplifyUsers(CurrIV, V);
  return SIV.hasChanged();
}

/// Simplify users of induction variables within this
/// loop. This does not actually change or add IVs.
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
                     LoopInfo *LI, const TargetTransformInfo *TTI,
                     SmallVectorImpl<WeakTrackingVH> &Dead) {
  SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
#ifndef NDEBUG
  Rewriter.setDebugType(DEBUG_TYPE);
#endif
  bool Changed = false;
  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
    Changed |=
        simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);
  }
  return Changed;
}

} // namespace llvm

namespace {
//===----------------------------------------------------------------------===//
// Widen Induction Variables - Extend the width of an IV to cover its
// widest uses.
//===----------------------------------------------------------------------===//

class WidenIV {
  // Parameters
  PHINode *OrigPhi;
  Type *WideType;

  // Context
  LoopInfo        *LI;
  Loop            *L;
  ScalarEvolution *SE;
  DominatorTree   *DT;

  // Does the module have any calls to the llvm.experimental.guard intrinsic
  // at all? If not we can avoid scanning instructions looking for guards.
  bool HasGuards;

  bool UsePostIncrementRanges;

  // Statistics
  unsigned NumElimExt = 0;
  unsigned NumWidened = 0;

  // Result
  PHINode *WidePhi = nullptr;
  Instruction *WideInc = nullptr;
  const SCEV *WideIncExpr = nullptr;
  SmallVectorImpl<WeakTrackingVH> &DeadInsts;

  SmallPtrSet<Instruction *,16> Widened;

  enum ExtendKind { ZeroExtended, SignExtended, Unknown };

  // A map tracking the kind of extension used to widen each narrow IV
  // and narrow IV user.
  // Key: pointer to a narrow IV or IV user.
  // Value: the kind of extension used to widen this Instruction.
  DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;

  using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;

  // A map with control-dependent ranges for post increment IV uses. The key is
  // a pair of IV def and a use of this def denoting the context. The value is
  // a ConstantRange representing possible values of the def at the given
  // context.
  DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;

  Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
                                              Instruction *UseI) {
    DefUserPair Key(Def, UseI);
    auto It = PostIncRangeInfos.find(Key);
    return It == PostIncRangeInfos.end()
               ? Optional<ConstantRange>(None)
               : Optional<ConstantRange>(It->second);
  }

  void calculatePostIncRanges(PHINode *OrigPhi);
  void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);

  void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
    DefUserPair Key(Def, UseI);
    auto It = PostIncRangeInfos.find(Key);
    if (It == PostIncRangeInfos.end())
      PostIncRangeInfos.insert({Key, R});
    else
      It->second = R.intersectWith(It->second);
  }

public:
  /// Record a link in the Narrow IV def-use chain along with the WideIV that
  /// computes the same value as the Narrow IV def.  This avoids caching Use*
  /// pointers.
  struct NarrowIVDefUse {
    Instruction *NarrowDef = nullptr;
    Instruction *NarrowUse = nullptr;
    Instruction *WideDef = nullptr;

    // True if the narrow def is never negative.  Tracking this information lets
    // us use a sign extension instead of a zero extension or vice versa, when
    // profitable and legal.
    bool NeverNegative = false;

    NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
                   bool NeverNegative)
        : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
          NeverNegative(NeverNegative) {}
  };

  WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
          DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
          bool HasGuards, bool UsePostIncrementRanges = true);

  PHINode *createWideIV(SCEVExpander &Rewriter);

  unsigned getNumElimExt() { return NumElimExt; };
  unsigned getNumWidened() { return NumWidened; };

protected:
  Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
                          Instruction *Use);

  Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
  Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
                                     const SCEVAddRecExpr *WideAR);
  Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);

  ExtendKind getExtendKind(Instruction *I);

  using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;

  WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);

  WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);

  const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
                              unsigned OpCode) const;

  Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);

  bool widenLoopCompare(NarrowIVDefUse DU);
  bool widenWithVariantUse(NarrowIVDefUse DU);

  void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);

private:
  SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
};
} // namespace

/// Determine the insertion point for this user. By default, insert immediately
/// before the user. SCEVExpander or LICM will hoist loop invariants out of the
/// loop. For PHI nodes, there may be multiple uses, so compute the nearest
/// common dominator for the incoming blocks. A nullptr can be returned if no
/// viable location is found: it may happen if User is a PHI and Def only comes
/// to this PHI from unreachable blocks.
static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
                                          DominatorTree *DT, LoopInfo *LI) {
  PHINode *PHI = dyn_cast<PHINode>(User);
  if (!PHI)
    return User;

  Instruction *InsertPt = nullptr;
  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
    if (PHI->getIncomingValue(i) != Def)
      continue;

    BasicBlock *InsertBB = PHI->getIncomingBlock(i);

    if (!DT->isReachableFromEntry(InsertBB))
      continue;

    if (!InsertPt) {
      InsertPt = InsertBB->getTerminator();
      continue;
    }
    InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
    InsertPt = InsertBB->getTerminator();
  }

  // If we have skipped all inputs, it means that Def only comes to Phi from
  // unreachable blocks.
  if (!InsertPt)
    return nullptr;

  auto *DefI = dyn_cast<Instruction>(Def);
  if (!DefI)
    return InsertPt;

  assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");

  auto *L = LI->getLoopFor(DefI->getParent());
  assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));

  for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
    if (LI->getLoopFor(DTN->getBlock()) == L)
      return DTN->getBlock()->getTerminator();

  llvm_unreachable("DefI dominates InsertPt!");
}

WidenIV::WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
          DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
          bool HasGuards, bool UsePostIncrementRanges)
      : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
        L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
        HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),
        DeadInsts(DI) {
    assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
    ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
}

Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
                                 bool IsSigned, Instruction *Use) {
  // Set the debug location and conservative insertion point.
  IRBuilder<> Builder(Use);
  // Hoist the insertion point into loop preheaders as far as possible.
  for (const Loop *L = LI->getLoopFor(Use->getParent());
       L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
       L = L->getParentLoop())
    Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());

  return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
                    Builder.CreateZExt(NarrowOper, WideType);
}

/// Instantiate a wide operation to replace a narrow operation. This only needs
/// to handle operations that can evaluation to SCEVAddRec. It can safely return
/// 0 for any operation we decide not to clone.
Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
                                  const SCEVAddRecExpr *WideAR) {
  unsigned Opcode = DU.NarrowUse->getOpcode();
  switch (Opcode) {
  default:
    return nullptr;
  case Instruction::Add:
  case Instruction::Mul:
  case Instruction::UDiv:
  case Instruction::Sub:
    return cloneArithmeticIVUser(DU, WideAR);

  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
  case Instruction::Shl:
  case Instruction::LShr:
  case Instruction::AShr:
    return cloneBitwiseIVUser(DU);
  }
}

Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
  Instruction *NarrowUse = DU.NarrowUse;
  Instruction *NarrowDef = DU.NarrowDef;
  Instruction *WideDef = DU.WideDef;

  LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");

  // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
  // about the narrow operand yet so must insert a [sz]ext. It is probably loop
  // invariant and will be folded or hoisted. If it actually comes from a
  // widened IV, it should be removed during a future call to widenIVUse.
  bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
                   ? WideDef
                   : createExtendInst(NarrowUse->getOperand(0), WideType,
                                      IsSigned, NarrowUse);
  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
                   ? WideDef
                   : createExtendInst(NarrowUse->getOperand(1), WideType,
                                      IsSigned, NarrowUse);

  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
                                        NarrowBO->getName());
  IRBuilder<> Builder(NarrowUse);
  Builder.Insert(WideBO);
  WideBO->copyIRFlags(NarrowBO);
  return WideBO;
}

Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
                                            const SCEVAddRecExpr *WideAR) {
  Instruction *NarrowUse = DU.NarrowUse;
  Instruction *NarrowDef = DU.NarrowDef;
  Instruction *WideDef = DU.WideDef;

  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");

  unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;

  // We're trying to find X such that
  //
  //  Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
  //
  // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
  // and check using SCEV if any of them are correct.

  // Returns true if extending NonIVNarrowDef according to `SignExt` is a
  // correct solution to X.
  auto GuessNonIVOperand = [&](bool SignExt) {
    const SCEV *WideLHS;
    const SCEV *WideRHS;

    auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
      if (SignExt)
        return SE->getSignExtendExpr(S, Ty);
      return SE->getZeroExtendExpr(S, Ty);
    };

    if (IVOpIdx == 0) {
      WideLHS = SE->getSCEV(WideDef);
      const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
      WideRHS = GetExtend(NarrowRHS, WideType);
    } else {
      const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
      WideLHS = GetExtend(NarrowLHS, WideType);
      WideRHS = SE->getSCEV(WideDef);
    }

    // WideUse is "WideDef `op.wide` X" as described in the comment.
    const SCEV *WideUse =
      getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());

    return WideUse == WideAR;
  };

  bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
  if (!GuessNonIVOperand(SignExtend)) {
    SignExtend = !SignExtend;
    if (!GuessNonIVOperand(SignExtend))
      return nullptr;
  }

  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
                   ? WideDef
                   : createExtendInst(NarrowUse->getOperand(0), WideType,
                                      SignExtend, NarrowUse);
  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
                   ? WideDef
                   : createExtendInst(NarrowUse->getOperand(1), WideType,
                                      SignExtend, NarrowUse);

  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
                                        NarrowBO->getName());

  IRBuilder<> Builder(NarrowUse);
  Builder.Insert(WideBO);
  WideBO->copyIRFlags(NarrowBO);
  return WideBO;
}

WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
  auto It = ExtendKindMap.find(I);
  assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
  return It->second;
}

const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
                                     unsigned OpCode) const {
  switch (OpCode) {
  case Instruction::Add:
    return SE->getAddExpr(LHS, RHS);
  case Instruction::Sub:
    return SE->getMinusSCEV(LHS, RHS);
  case Instruction::Mul:
    return SE->getMulExpr(LHS, RHS);
  case Instruction::UDiv:
    return SE->getUDivExpr(LHS, RHS);
  default:
    llvm_unreachable("Unsupported opcode.");
  };
}

/// No-wrap operations can transfer sign extension of their result to their
/// operands. Generate the SCEV value for the widened operation without
/// actually modifying the IR yet. If the expression after extending the
/// operands is an AddRec for this loop, return the AddRec and the kind of
/// extension used.
WidenIV::WidenedRecTy
WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
  // Handle the common case of add<nsw/nuw>
  const unsigned OpCode = DU.NarrowUse->getOpcode();
  // Only Add/Sub/Mul instructions supported yet.
  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
      OpCode != Instruction::Mul)
    return {nullptr, Unknown};

  // One operand (NarrowDef) has already been extended to WideDef. Now determine
  // if extending the other will lead to a recurrence.
  const unsigned ExtendOperIdx =
      DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
  assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");

  const SCEV *ExtendOperExpr = nullptr;
  const OverflowingBinaryOperator *OBO =
    cast<OverflowingBinaryOperator>(DU.NarrowUse);
  ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
    ExtendOperExpr = SE->getSignExtendExpr(
      SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
  else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
    ExtendOperExpr = SE->getZeroExtendExpr(
      SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
  else
    return {nullptr, Unknown};

  // When creating this SCEV expr, don't apply the current operations NSW or NUW
  // flags. This instruction may be guarded by control flow that the no-wrap
  // behavior depends on. Non-control-equivalent instructions can be mapped to
  // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
  // semantics to those operations.
  const SCEV *lhs = SE->getSCEV(DU.WideDef);
  const SCEV *rhs = ExtendOperExpr;

  // Let's swap operands to the initial order for the case of non-commutative
  // operations, like SUB. See PR21014.
  if (ExtendOperIdx == 0)
    std::swap(lhs, rhs);
  const SCEVAddRecExpr *AddRec =
      dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));

  if (!AddRec || AddRec->getLoop() != L)
    return {nullptr, Unknown};

  return {AddRec, ExtKind};
}

/// Is this instruction potentially interesting for further simplification after
/// widening it's type? In other words, can the extend be safely hoisted out of
/// the loop with SCEV reducing the value to a recurrence on the same loop. If
/// so, return the extended recurrence and the kind of extension used. Otherwise
/// return {nullptr, Unknown}.
WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
  if (!DU.NarrowUse->getType()->isIntegerTy())
    return {nullptr, Unknown};

  const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
  if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
      SE->getTypeSizeInBits(WideType)) {
    // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
    // index. So don't follow this use.
    return {nullptr, Unknown};
  }

  const SCEV *WideExpr;
  ExtendKind ExtKind;
  if (DU.NeverNegative) {
    WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
    if (isa<SCEVAddRecExpr>(WideExpr))
      ExtKind = SignExtended;
    else {
      WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
      ExtKind = ZeroExtended;
    }
  } else if (getExtendKind(DU.NarrowDef) == SignExtended) {
    WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
    ExtKind = SignExtended;
  } else {
    WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
    ExtKind = ZeroExtended;
  }
  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
  if (!AddRec || AddRec->getLoop() != L)
    return {nullptr, Unknown};
  return {AddRec, ExtKind};
}

/// This IV user cannot be widened. Replace this use of the original narrow IV
/// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
static void truncateIVUse(WidenIV::NarrowIVDefUse DU, DominatorTree *DT,
                          LoopInfo *LI) {
  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
  if (!InsertPt)
    return;
  LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
                    << *DU.NarrowUse << "\n");
  IRBuilder<> Builder(InsertPt);
  Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
}

/// If the narrow use is a compare instruction, then widen the compare
//  (and possibly the other operand).  The extend operation is hoisted into the
// loop preheader as far as possible.
bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
  ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
  if (!Cmp)
    return false;

  // We can legally widen the comparison in the following two cases:
  //
  //  - The signedness of the IV extension and comparison match
  //
  //  - The narrow IV is always positive (and thus its sign extension is equal
  //    to its zero extension).  For instance, let's say we're zero extending
  //    %narrow for the following use
  //
  //      icmp slt i32 %narrow, %val   ... (A)
  //
  //    and %narrow is always positive.  Then
  //
  //      (A) == icmp slt i32 sext(%narrow), sext(%val)
  //          == icmp slt i32 zext(%narrow), sext(%val)
  bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
  if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
    return false;

  Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
  unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
  assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");

  // Widen the compare instruction.
  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
  if (!InsertPt)
    return false;
  IRBuilder<> Builder(InsertPt);
  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);

  // Widen the other operand of the compare, if necessary.
  if (CastWidth < IVWidth) {
    Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
    DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
  }
  return true;
}

// The widenIVUse avoids generating trunc by evaluating the use as AddRec, this
// will not work when:
//    1) SCEV traces back to an instruction inside the loop that SCEV can not
// expand, eg. add %indvar, (load %addr)
//    2) SCEV finds a loop variant, eg. add %indvar, %loopvariant
// While SCEV fails to avoid trunc, we can still try to use instruction
// combining approach to prove trunc is not required. This can be further
// extended with other instruction combining checks, but for now we handle the
// following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")
//
// Src:
//   %c = sub nsw %b, %indvar
//   %d = sext %c to i64
// Dst:
//   %indvar.ext1 = sext %indvar to i64
//   %m = sext %b to i64
//   %d = sub nsw i64 %m, %indvar.ext1
// Therefore, as long as the result of add/sub/mul is extended to wide type, no
// trunc is required regardless of how %b is generated. This pattern is common
// when calculating address in 64 bit architecture
bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
  Instruction *NarrowUse = DU.NarrowUse;
  Instruction *NarrowDef = DU.NarrowDef;
  Instruction *WideDef = DU.WideDef;

  // Handle the common case of add<nsw/nuw>
  const unsigned OpCode = NarrowUse->getOpcode();
  // Only Add/Sub/Mul instructions are supported.
  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
      OpCode != Instruction::Mul)
    return false;

  // The operand that is not defined by NarrowDef of DU. Let's call it the
  // other operand.
  assert((NarrowUse->getOperand(0) == NarrowDef ||
          NarrowUse->getOperand(1) == NarrowDef) &&
         "bad DU");

  const OverflowingBinaryOperator *OBO =
    cast<OverflowingBinaryOperator>(NarrowUse);
  ExtendKind ExtKind = getExtendKind(NarrowDef);
  bool CanSignExtend = ExtKind == SignExtended && OBO->hasNoSignedWrap();
  bool CanZeroExtend = ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap();
  auto AnotherOpExtKind = ExtKind;

  // Check that all uses are either:
  // - narrow def (in case of we are widening the IV increment);
  // - single-input LCSSA Phis;
  // - comparison of the chosen type;
  // - extend of the chosen type (raison d'etre).
  SmallVector<Instruction *, 4> ExtUsers;
  SmallVector<PHINode *, 4> LCSSAPhiUsers;
  SmallVector<ICmpInst *, 4> ICmpUsers;
  for (Use &U : NarrowUse->uses()) {
    Instruction *User = cast<Instruction>(U.getUser());
    if (User == NarrowDef)
      continue;
    if (!L->contains(User)) {
      auto *LCSSAPhi = cast<PHINode>(User);
      // Make sure there is only 1 input, so that we don't have to split
      // critical edges.
      if (LCSSAPhi->getNumOperands() != 1)
        return false;
      LCSSAPhiUsers.push_back(LCSSAPhi);
      continue;
    }
    if (auto *ICmp = dyn_cast<ICmpInst>(User)) {
      auto Pred = ICmp->getPredicate();
      // We have 3 types of predicates: signed, unsigned and equality
      // predicates. For equality, it's legal to widen icmp for either sign and
      // zero extend. For sign extend, we can also do so for signed predicates,
      // likeweise for zero extend we can widen icmp for unsigned predicates.
      if (ExtKind == ZeroExtended && ICmpInst::isSigned(Pred))
        return false;
      if (ExtKind == SignExtended && ICmpInst::isUnsigned(Pred))
        return false;
      ICmpUsers.push_back(ICmp);
      continue;
    }
    if (ExtKind == SignExtended)
      User = dyn_cast<SExtInst>(User);
    else
      User = dyn_cast<ZExtInst>(User);
    if (!User || User->getType() != WideType)
      return false;
    ExtUsers.push_back(User);
  }
  if (ExtUsers.empty()) {
    DeadInsts.emplace_back(NarrowUse);
    return true;
  }

  // We'll prove some facts that should be true in the context of ext users. If
  // there is no users, we are done now. If there are some, pick their common
  // dominator as context.
  const Instruction *CtxI = findCommonDominator(ExtUsers, *DT);

  if (!CanSignExtend && !CanZeroExtend) {
    // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
    // will most likely not see it. Let's try to prove it.
    if (OpCode != Instruction::Add)
      return false;
    if (ExtKind != ZeroExtended)
      return false;
    const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));
    const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));
    // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
    if (NarrowUse->getOperand(0) != NarrowDef)
      return false;
    if (!SE->isKnownNegative(RHS))
      return false;
    bool ProvedSubNUW = SE->isKnownPredicateAt(ICmpInst::ICMP_UGE, LHS,
                                               SE->getNegativeSCEV(RHS), CtxI);
    if (!ProvedSubNUW)
      return false;
    // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as
    // neg(zext(neg(op))), which is basically sext(op).
    AnotherOpExtKind = SignExtended;
  }

  // Verifying that Defining operand is an AddRec
  const SCEV *Op1 = SE->getSCEV(WideDef);
  const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
  if (!AddRecOp1 || AddRecOp1->getLoop() != L)
    return false;

  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");

  // Generating a widening use instruction.
  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
                   ? WideDef
                   : createExtendInst(NarrowUse->getOperand(0), WideType,
                                      AnotherOpExtKind, NarrowUse);
  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
                   ? WideDef
                   : createExtendInst(NarrowUse->getOperand(1), WideType,
                                      AnotherOpExtKind, NarrowUse);

  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
                                        NarrowBO->getName());
  IRBuilder<> Builder(NarrowUse);
  Builder.Insert(WideBO);
  WideBO->copyIRFlags(NarrowBO);
  ExtendKindMap[NarrowUse] = ExtKind;

  for (Instruction *User : ExtUsers) {
    assert(User->getType() == WideType && "Checked before!");
    LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
                      << *WideBO << "\n");
    ++NumElimExt;
    User->replaceAllUsesWith(WideBO);
    DeadInsts.emplace_back(User);
  }

  for (PHINode *User : LCSSAPhiUsers) {
    assert(User->getNumOperands() == 1 && "Checked before!");
    Builder.SetInsertPoint(User);
    auto *WidePN =
        Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");
    BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
    assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
           "Not a LCSSA Phi?");
    WidePN->addIncoming(WideBO, LoopExitingBlock);
    Builder.SetInsertPoint(&*User->getParent()->getFirstInsertionPt());
    auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());
    User->replaceAllUsesWith(TruncPN);
    DeadInsts.emplace_back(User);
  }

  for (ICmpInst *User : ICmpUsers) {
    Builder.SetInsertPoint(User);
    auto ExtendedOp = [&](Value * V)->Value * {
      if (V == NarrowUse)
        return WideBO;
      if (ExtKind == ZeroExtended)
        return Builder.CreateZExt(V, WideBO->getType());
      else
        return Builder.CreateSExt(V, WideBO->getType());
    };
    auto Pred = User->getPredicate();
    auto *LHS = ExtendedOp(User->getOperand(0));
    auto *RHS = ExtendedOp(User->getOperand(1));
    auto *WideCmp =
        Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");
    User->replaceAllUsesWith(WideCmp);
    DeadInsts.emplace_back(User);
  }

  return true;
}

/// Determine whether an individual user of the narrow IV can be widened. If so,
/// return the wide clone of the user.
Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU, SCEVExpander &Rewriter) {
  assert(ExtendKindMap.count(DU.NarrowDef) &&
         "Should already know the kind of extension used to widen NarrowDef");

  // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
  if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
    if (LI->getLoopFor(UsePhi->getParent()) != L) {
      // For LCSSA phis, sink the truncate outside the loop.
      // After SimplifyCFG most loop exit targets have a single predecessor.
      // Otherwise fall back to a truncate within the loop.
      if (UsePhi->getNumOperands() != 1)
        truncateIVUse(DU, DT, LI);
      else {
        // Widening the PHI requires us to insert a trunc.  The logical place
        // for this trunc is in the same BB as the PHI.  This is not possible if
        // the BB is terminated by a catchswitch.
        if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
          return nullptr;

        PHINode *WidePhi =
          PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
                          UsePhi);
        WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
        IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
        Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
        UsePhi->replaceAllUsesWith(Trunc);
        DeadInsts.emplace_back(UsePhi);
        LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
                          << *WidePhi << "\n");
      }
      return nullptr;
    }
  }

  // This narrow use can be widened by a sext if it's non-negative or its narrow
  // def was widended by a sext. Same for zext.
  auto canWidenBySExt = [&]() {
    return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
  };
  auto canWidenByZExt = [&]() {
    return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
  };

  // Our raison d'etre! Eliminate sign and zero extension.
  if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
      (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
    Value *NewDef = DU.WideDef;
    if (DU.NarrowUse->getType() != WideType) {
      unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
      unsigned IVWidth = SE->getTypeSizeInBits(WideType);
      if (CastWidth < IVWidth) {
        // The cast isn't as wide as the IV, so insert a Trunc.
        IRBuilder<> Builder(DU.NarrowUse);
        NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
      }
      else {
        // A wider extend was hidden behind a narrower one. This may induce
        // another round of IV widening in which the intermediate IV becomes
        // dead. It should be very rare.
        LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
                          << " not wide enough to subsume " << *DU.NarrowUse
                          << "\n");
        DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
        NewDef = DU.NarrowUse;
      }
    }
    if (NewDef != DU.NarrowUse) {
      LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
                        << " replaced by " << *DU.WideDef << "\n");
      ++NumElimExt;
      DU.NarrowUse->replaceAllUsesWith(NewDef);
      DeadInsts.emplace_back(DU.NarrowUse);
    }
    // Now that the extend is gone, we want to expose it's uses for potential
    // further simplification. We don't need to directly inform SimplifyIVUsers
    // of the new users, because their parent IV will be processed later as a
    // new loop phi. If we preserved IVUsers analysis, we would also want to
    // push the uses of WideDef here.

    // No further widening is needed. The deceased [sz]ext had done it for us.
    return nullptr;
  }

  // Does this user itself evaluate to a recurrence after widening?
  WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
  if (!WideAddRec.first)
    WideAddRec = getWideRecurrence(DU);

  assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
  if (!WideAddRec.first) {
    // If use is a loop condition, try to promote the condition instead of
    // truncating the IV first.
    if (widenLoopCompare(DU))
      return nullptr;

    // We are here about to generate a truncate instruction that may hurt
    // performance because the scalar evolution expression computed earlier
    // in WideAddRec.first does not indicate a polynomial induction expression.
    // In that case, look at the operands of the use instruction to determine
    // if we can still widen the use instead of truncating its operand.
    if (widenWithVariantUse(DU))
      return nullptr;

    // This user does not evaluate to a recurrence after widening, so don't
    // follow it. Instead insert a Trunc to kill off the original use,
    // eventually isolating the original narrow IV so it can be removed.
    truncateIVUse(DU, DT, LI);
    return nullptr;
  }
  // Assume block terminators cannot evaluate to a recurrence. We can't to
  // insert a Trunc after a terminator if there happens to be a critical edge.
  assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
         "SCEV is not expected to evaluate a block terminator");

  // Reuse the IV increment that SCEVExpander created as long as it dominates
  // NarrowUse.
  Instruction *WideUse = nullptr;
  if (WideAddRec.first == WideIncExpr &&
      Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
    WideUse = WideInc;
  else {
    WideUse = cloneIVUser(DU, WideAddRec.first);
    if (!WideUse)
      return nullptr;
  }
  // Evaluation of WideAddRec ensured that the narrow expression could be
  // extended outside the loop without overflow. This suggests that the wide use
  // evaluates to the same expression as the extended narrow use, but doesn't
  // absolutely guarantee it. Hence the following failsafe check. In rare cases
  // where it fails, we simply throw away the newly created wide use.
  if (WideAddRec.first != SE->getSCEV(WideUse)) {
    LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
                      << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
                      << "\n");
    DeadInsts.emplace_back(WideUse);
    return nullptr;
  }

  // if we reached this point then we are going to replace
  // DU.NarrowUse with WideUse. Reattach DbgValue then.
  replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);

  ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
  // Returning WideUse pushes it on the worklist.
  return WideUse;
}

/// Add eligible users of NarrowDef to NarrowIVUsers.
void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
  const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
  bool NonNegativeDef =
      SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
                           SE->getZero(NarrowSCEV->getType()));
  for (User *U : NarrowDef->users()) {
    Instruction *NarrowUser = cast<Instruction>(U);

    // Handle data flow merges and bizarre phi cycles.
    if (!Widened.insert(NarrowUser).second)
      continue;

    bool NonNegativeUse = false;
    if (!NonNegativeDef) {
      // We might have a control-dependent range information for this context.
      if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
        NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
    }

    NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
                               NonNegativeDef || NonNegativeUse);
  }
}

/// Process a single induction variable. First use the SCEVExpander to create a
/// wide induction variable that evaluates to the same recurrence as the
/// original narrow IV. Then use a worklist to forward traverse the narrow IV's
/// def-use chain. After widenIVUse has processed all interesting IV users, the
/// narrow IV will be isolated for removal by DeleteDeadPHIs.
///
/// It would be simpler to delete uses as they are processed, but we must avoid
/// invalidating SCEV expressions.
PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
  // Is this phi an induction variable?
  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
  if (!AddRec)
    return nullptr;

  // Widen the induction variable expression.
  const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
                               ? SE->getSignExtendExpr(AddRec, WideType)
                               : SE->getZeroExtendExpr(AddRec, WideType);

  assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
         "Expect the new IV expression to preserve its type");

  // Can the IV be extended outside the loop without overflow?
  AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
  if (!AddRec || AddRec->getLoop() != L)
    return nullptr;

  // An AddRec must have loop-invariant operands. Since this AddRec is
  // materialized by a loop header phi, the expression cannot have any post-loop
  // operands, so they must dominate the loop header.
  assert(
      SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
      SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
      "Loop header phi recurrence inputs do not dominate the loop");

  // Iterate over IV uses (including transitive ones) looking for IV increments
  // of the form 'add nsw %iv, <const>'. For each increment and each use of
  // the increment calculate control-dependent range information basing on
  // dominating conditions inside of the loop (e.g. a range check inside of the
  // loop). Calculated ranges are stored in PostIncRangeInfos map.
  //
  // Control-dependent range information is later used to prove that a narrow
  // definition is not negative (see pushNarrowIVUsers). It's difficult to do
  // this on demand because when pushNarrowIVUsers needs this information some
  // of the dominating conditions might be already widened.
  if (UsePostIncrementRanges)
    calculatePostIncRanges(OrigPhi);

  // The rewriter provides a value for the desired IV expression. This may
  // either find an existing phi or materialize a new one. Either way, we
  // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
  // of the phi-SCC dominates the loop entry.
  Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
  Value *ExpandInst = Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
  // If the wide phi is not a phi node, for example a cast node, like bitcast,
  // inttoptr, ptrtoint, just skip for now.
  if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
    // if the cast node is an inserted instruction without any user, we should
    // remove it to make sure the pass don't touch the function as we can not
    // wide the phi.
    if (ExpandInst->hasNUses(0) &&
        Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
      DeadInsts.emplace_back(ExpandInst);
    return nullptr;
  }

  // Remembering the WideIV increment generated by SCEVExpander allows
  // widenIVUse to reuse it when widening the narrow IV's increment. We don't
  // employ a general reuse mechanism because the call above is the only call to
  // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
  if (BasicBlock *LatchBlock = L->getLoopLatch()) {
    WideInc =
      cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
    WideIncExpr = SE->getSCEV(WideInc);
    // Propagate the debug location associated with the original loop increment
    // to the new (widened) increment.
    auto *OrigInc =
      cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
    WideInc->setDebugLoc(OrigInc->getDebugLoc());
  }

  LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
  ++NumWidened;

  // Traverse the def-use chain using a worklist starting at the original IV.
  assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );

  Widened.insert(OrigPhi);
  pushNarrowIVUsers(OrigPhi, WidePhi);

  while (!NarrowIVUsers.empty()) {
    WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();

    // Process a def-use edge. This may replace the use, so don't hold a
    // use_iterator across it.
    Instruction *WideUse = widenIVUse(DU, Rewriter);

    // Follow all def-use edges from the previous narrow use.
    if (WideUse)
      pushNarrowIVUsers(DU.NarrowUse, WideUse);

    // widenIVUse may have removed the def-use edge.
    if (DU.NarrowDef->use_empty())
      DeadInsts.emplace_back(DU.NarrowDef);
  }

  // Attach any debug information to the new PHI.
  replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);

  return WidePhi;
}

/// Calculates control-dependent range for the given def at the given context
/// by looking at dominating conditions inside of the loop
void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
                                    Instruction *NarrowUser) {
  using namespace llvm::PatternMatch;

  Value *NarrowDefLHS;
  const APInt *NarrowDefRHS;
  if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
                                 m_APInt(NarrowDefRHS))) ||
      !NarrowDefRHS->isNonNegative())
    return;

  auto UpdateRangeFromCondition = [&] (Value *Condition,
                                       bool TrueDest) {
    CmpInst::Predicate Pred;
    Value *CmpRHS;
    if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
                                 m_Value(CmpRHS))))
      return;

    CmpInst::Predicate P =
            TrueDest ? Pred : CmpInst::getInversePredicate(Pred);

    auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
    auto CmpConstrainedLHSRange =
            ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
    auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
        *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);

    updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
  };

  auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
    if (!HasGuards)
      return;

    for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
                                     Ctx->getParent()->rend())) {
      Value *C = nullptr;
      if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
        UpdateRangeFromCondition(C, /*TrueDest=*/true);
    }
  };

  UpdateRangeFromGuards(NarrowUser);

  BasicBlock *NarrowUserBB = NarrowUser->getParent();
  // If NarrowUserBB is statically unreachable asking dominator queries may
  // yield surprising results. (e.g. the block may not have a dom tree node)
  if (!DT->isReachableFromEntry(NarrowUserBB))
    return;

  for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
       L->contains(DTB->getBlock());
       DTB = DTB->getIDom()) {
    auto *BB = DTB->getBlock();
    auto *TI = BB->getTerminator();
    UpdateRangeFromGuards(TI);

    auto *BI = dyn_cast<BranchInst>(TI);
    if (!BI || !BI->isConditional())
      continue;

    auto *TrueSuccessor = BI->getSuccessor(0);
    auto *FalseSuccessor = BI->getSuccessor(1);

    auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
      return BBE.isSingleEdge() &&
             DT->dominates(BBE, NarrowUser->getParent());
    };

    if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
      UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);

    if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
      UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
  }
}

/// Calculates PostIncRangeInfos map for the given IV
void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
  SmallPtrSet<Instruction *, 16> Visited;
  SmallVector<Instruction *, 6> Worklist;
  Worklist.push_back(OrigPhi);
  Visited.insert(OrigPhi);

  while (!Worklist.empty()) {
    Instruction *NarrowDef = Worklist.pop_back_val();

    for (Use &U : NarrowDef->uses()) {
      auto *NarrowUser = cast<Instruction>(U.getUser());

      // Don't go looking outside the current loop.
      auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
      if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
        continue;

      if (!Visited.insert(NarrowUser).second)
        continue;

      Worklist.push_back(NarrowUser);

      calculatePostIncRange(NarrowDef, NarrowUser);
    }
  }
}

PHINode *llvm::createWideIV(const WideIVInfo &WI,
    LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,
    DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,
    unsigned &NumElimExt, unsigned &NumWidened,
    bool HasGuards, bool UsePostIncrementRanges) {
  WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);
  PHINode *WidePHI = Widener.createWideIV(Rewriter);
  NumElimExt = Widener.getNumElimExt();
  NumWidened = Widener.getNumWidened();
  return WidePHI;
}