//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//

//

// 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 transformation analyzes and transforms the induction variables (and

// computations derived from them) into simpler forms suitable for subsequent

// analysis and transformation.

//

// If the trip count of a loop is computable, this pass also makes the following

// changes:

//   1. The exit condition for the loop is canonicalized to compare the

//      induction value against the exit value.  This turns loops like:

//        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'

//   2. Any use outside of the loop of an expression derived from the indvar

//      is changed to compute the derived value outside of the loop, eliminating

//      the dependence on the exit value of the induction variable.  If the only

//      purpose of the loop is to compute the exit value of some derived

//      expression, this transformation will make the loop dead.

//

//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/IndVarSimplify.h"

#include "llvm/ADT/APFloat.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/Statistic.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/Analysis/LoopPass.h"

#include "llvm/Analysis/MemorySSA.h"

#include "llvm/Analysis/MemorySSAUpdater.h"

#include "llvm/Analysis/ScalarEvolution.h"

#include "llvm/Analysis/ScalarEvolutionExpressions.h"

#include "llvm/Analysis/TargetLibraryInfo.h"

#include "llvm/Analysis/TargetTransformInfo.h"

#include "llvm/Analysis/ValueTracking.h"

#include "llvm/IR/BasicBlock.h"

#include "llvm/IR/Constant.h"

#include "llvm/IR/ConstantRange.h"

#include "llvm/IR/Constants.h"

#include "llvm/IR/DataLayout.h"

#include "llvm/IR/DerivedTypes.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/Function.h"

#include "llvm/IR/IRBuilder.h"

#include "llvm/IR/InstrTypes.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/IntrinsicInst.h"

#include "llvm/IR/Intrinsics.h"

#include "llvm/IR/Module.h"

#include "llvm/IR/Operator.h"

#include "llvm/IR/PassManager.h"

#include "llvm/IR/PatternMatch.h"

#include "llvm/IR/Type.h"

#include "llvm/IR/Use.h"

#include "llvm/IR/User.h"

#include "llvm/IR/Value.h"

#include "llvm/IR/ValueHandle.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/MathExtras.h"

#include "llvm/Support/raw_ostream.h"

#include "llvm/Transforms/Utils/BasicBlockUtils.h"

#include "llvm/Transforms/Utils/Local.h"

#include "llvm/Transforms/Utils/LoopUtils.h"

#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

#include "llvm/Transforms/Utils/SimplifyIndVar.h"

#include <cassert>

#include <cstdint>

#include <utility>

using namespace llvm;

using namespace PatternMatch;

#define DEBUG_TYPE "indvars"

STATISTIC(NumWidened     , "Number of indvars widened");

STATISTIC(NumReplaced    , "Number of exit values replaced");

STATISTIC(NumLFTR        , "Number of loop exit tests replaced");

STATISTIC(NumElimExt     , "Number of IV sign/zero extends eliminated");

STATISTIC(NumElimIV      , "Number of congruent IVs eliminated");

static cl::opt<ReplaceExitVal> ReplaceExitValue(

    "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),

    cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),

    cl::values(

        clEnumValN(NeverRepl, "never", "never replace exit value"),

        clEnumValN(OnlyCheapRepl, "cheap",

                   "only replace exit value when the cost is cheap"),

        clEnumValN(

            UnusedIndVarInLoop, "unusedindvarinloop",

            "only replace exit value when it is an unused "

            "induction variable in the loop and has cheap replacement cost"),

        clEnumValN(NoHardUse, "noharduse",

                   "only replace exit values when loop def likely dead"),

        clEnumValN(AlwaysRepl, "always",

                   "always replace exit value whenever possible")));

static cl::opt<bool> UsePostIncrementRanges(

  "indvars-post-increment-ranges", cl::Hidden,

  cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),

  cl::init(true));

static cl::opt<bool>

DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),

            cl::desc("Disable Linear Function Test Replace optimization"));

static cl::opt<bool>

LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true),

                cl::desc("Predicate conditions in read only loops"));

static cl::opt<bool>

AllowIVWidening("indvars-widen-indvars", cl::Hidden, cl::init(true),

                cl::desc("Allow widening of indvars to eliminate s/zext"));

namespace {

class IndVarSimplify {

  LoopInfo *LI;

  ScalarEvolution *SE;

  DominatorTree *DT;

  const DataLayout &DL;

  TargetLibraryInfo *TLI;

  const TargetTransformInfo *TTI;

  std::unique_ptr<MemorySSAUpdater> MSSAU;

  SmallVector<WeakTrackingVH, 16> DeadInsts;

  bool WidenIndVars;

  bool handleFloatingPointIV(Loop *L, PHINode *PH);

  bool rewriteNonIntegerIVs(Loop *L);

  bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);

  /// Try to improve our exit conditions by converting condition from signed

  /// to unsigned or rotating computation out of the loop.

  /// (See inline comment about why this is duplicated from simplifyAndExtend)

  bool canonicalizeExitCondition(Loop *L);

  /// Try to eliminate loop exits based on analyzeable exit counts

  bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter);

  /// Try to form loop invariant tests for loop exits by changing how many

  /// iterations of the loop run when that is unobservable.

  bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);

  bool rewriteFirstIterationLoopExitValues(Loop *L);

  bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,

                                 const SCEV *ExitCount,

                                 PHINode *IndVar, SCEVExpander &Rewriter);

  bool sinkUnusedInvariants(Loop *L);

public:

  IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,

                 const DataLayout &DL, TargetLibraryInfo *TLI,

                 TargetTransformInfo *TTI, MemorySSA *MSSA, bool WidenIndVars)

      : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI),

        WidenIndVars(WidenIndVars) {

    if (MSSA)

      MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);

  }

  bool run(Loop *L);

};

} // end anonymous namespace

//===----------------------------------------------------------------------===//

// rewriteNonIntegerIVs and helpers. Prefer integer IVs.

//===----------------------------------------------------------------------===//

/// Convert APF to an integer, if possible.

static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {

  bool isExact = false;

  // See if we can convert this to an int64_t

  uint64_t UIntVal;

  if (APF.convertToInteger(MutableArrayRef(UIntVal), 64, true,

                           APFloat::rmTowardZero, &isExact) != APFloat::opOK ||

      !isExact)

    return false;

  IntVal = UIntVal;

  return true;

}

/// If the loop has floating induction variable then insert corresponding

/// integer induction variable if possible.

/// For example,

/// for(double i = 0; i < 10000; ++i)

///   bar(i)

/// is converted into

/// for(int i = 0; i < 10000; ++i)

///   bar((double)i);

bool IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {

  unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));

  unsigned BackEdge     = IncomingEdge^1;

  // Check incoming value.

  auto *InitValueVal = dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge));

  int64_t InitValue;

  if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue))

    return false;

  // Check IV increment. Reject this PN if increment operation is not

  // an add or increment value can not be represented by an integer.

  auto *Incr = dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge));

  if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return false;

  // If this is not an add of the PHI with a constantfp, or if the constant fp

  // is not an integer, bail out.

  ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));

  int64_t IncValue;

  if (IncValueVal == nullptr || Incr->getOperand(0) != PN ||

      !ConvertToSInt(IncValueVal->getValueAPF(), IncValue))

    return false;

  // Check Incr uses. One user is PN and the other user is an exit condition

  // used by the conditional terminator.

  Value::user_iterator IncrUse = Incr->user_begin();

  Instruction *U1 = cast<Instruction>(*IncrUse++);

  if (IncrUse == Incr->user_end()) return false;

  Instruction *U2 = cast<Instruction>(*IncrUse++);

  if (IncrUse != Incr->user_end()) return false;

  // Find exit condition, which is an fcmp.  If it doesn't exist, or if it isn't

  // only used by a branch, we can't transform it.

  FCmpInst *Compare = dyn_cast<FCmpInst>(U1);

  if (!Compare)

    Compare = dyn_cast<FCmpInst>(U2);

  if (!Compare || !Compare->hasOneUse() ||

      !isa<BranchInst>(Compare->user_back()))

    return false;

  BranchInst *TheBr = cast<BranchInst>(Compare->user_back());

  // We need to verify that the branch actually controls the iteration count

  // of the loop.  If not, the new IV can overflow and no one will notice.

  // The branch block must be in the loop and one of the successors must be out

  // of the loop.

  assert(TheBr->isConditional() && "Can't use fcmp if not conditional");

  if (!L->contains(TheBr->getParent()) ||

      (L->contains(TheBr->getSuccessor(0)) &&

       L->contains(TheBr->getSuccessor(1))))

    return false;

  // If it isn't a comparison with an integer-as-fp (the exit value), we can't

  // transform it.

  ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));

  int64_t ExitValue;

  if (ExitValueVal == nullptr ||

      !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue))

    return false;

  // Find new predicate for integer comparison.

  CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;

  switch (Compare->getPredicate()) {

  default: return false;  // Unknown comparison.

  case CmpInst::FCMP_OEQ:

  case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break;

  case CmpInst::FCMP_ONE:

  case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break;

  case CmpInst::FCMP_OGT:

  case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break;

  case CmpInst::FCMP_OGE:

  case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break;

  case CmpInst::FCMP_OLT:

  case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break;

  case CmpInst::FCMP_OLE:

  case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break;

  }

  // We convert the floating point induction variable to a signed i32 value if

  // we can.  This is only safe if the comparison will not overflow in a way

  // that won't be trapped by the integer equivalent operations.  Check for this

  // now.

  // TODO: We could use i64 if it is native and the range requires it.

  // The start/stride/exit values must all fit in signed i32.

  if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))

    return false;

  // If not actually striding (add x, 0.0), avoid touching the code.

  if (IncValue == 0)

    return false;

  // Positive and negative strides have different safety conditions.

  if (IncValue > 0) {

    // If we have a positive stride, we require the init to be less than the

    // exit value.

    if (InitValue >= ExitValue)

      return false;

    uint32_t Range = uint32_t(ExitValue-InitValue);

    // Check for infinite loop, either:

    // while (i <= Exit) or until (i > Exit)

    if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) {

      if (++Range == 0) return false;  // Range overflows.

    }

    unsigned Leftover = Range % uint32_t(IncValue);

    // If this is an equality comparison, we require that the strided value

    // exactly land on the exit value, otherwise the IV condition will wrap

    // around and do things the fp IV wouldn't.

    if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&

        Leftover != 0)

      return false;

    // If the stride would wrap around the i32 before exiting, we can't

    // transform the IV.

    if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)

      return false;

  } else {

    // If we have a negative stride, we require the init to be greater than the

    // exit value.

    if (InitValue <= ExitValue)

      return false;

    uint32_t Range = uint32_t(InitValue-ExitValue);

    // Check for infinite loop, either:

    // while (i >= Exit) or until (i < Exit)

    if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) {

      if (++Range == 0) return false;  // Range overflows.

    }

    unsigned Leftover = Range % uint32_t(-IncValue);

    // If this is an equality comparison, we require that the strided value

    // exactly land on the exit value, otherwise the IV condition will wrap

    // around and do things the fp IV wouldn't.

    if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&

        Leftover != 0)

      return false;

    // If the stride would wrap around the i32 before exiting, we can't

    // transform the IV.

    if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)

      return false;

  }

  IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext());

  // Insert new integer induction variable.

  PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN);

  NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue),

                      PN->getIncomingBlock(IncomingEdge));

  Value *NewAdd =

    BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue),

                              Incr->getName()+".int", Incr);

  NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge));

  ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd,

                                      ConstantInt::get(Int32Ty, ExitValue),

                                      Compare->getName());

  // In the following deletions, PN may become dead and may be deleted.

  // Use a WeakTrackingVH to observe whether this happens.

  WeakTrackingVH WeakPH = PN;

  // Delete the old floating point exit comparison.  The branch starts using the

  // new comparison.

  NewCompare->takeName(Compare);

  Compare->replaceAllUsesWith(NewCompare);

  RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI, MSSAU.get());

  // Delete the old floating point increment.

  Incr->replaceAllUsesWith(PoisonValue::get(Incr->getType()));

  RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI, MSSAU.get());

  // If the FP induction variable still has uses, this is because something else

  // in the loop uses its value.  In order to canonicalize the induction

  // variable, we chose to eliminate the IV and rewrite it in terms of an

  // int->fp cast.

  //

  // We give preference to sitofp over uitofp because it is faster on most

  // platforms.

  if (WeakPH) {

    Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",

                                 &*PN->getParent()->getFirstInsertionPt());

    PN->replaceAllUsesWith(Conv);

    RecursivelyDeleteTriviallyDeadInstructions(PN, TLI, MSSAU.get());

  }

  return true;

}

bool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {

  // First step.  Check to see if there are any floating-point recurrences.

  // If there are, change them into integer recurrences, permitting analysis by

  // the SCEV routines.

  BasicBlock *Header = L->getHeader();

  SmallVector<WeakTrackingVH, 8> PHIs;

  for (PHINode &PN : Header->phis())

    PHIs.push_back(&PN);

  bool Changed = false;

  for (WeakTrackingVH &PHI : PHIs)

    if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHI))

      Changed |= handleFloatingPointIV(L, PN);

  // If the loop previously had floating-point IV, ScalarEvolution

  // may not have been able to compute a trip count. Now that we've done some

  // re-writing, the trip count may be computable.

  if (Changed)

    SE->forgetLoop(L);

  return Changed;

}

//===---------------------------------------------------------------------===//

// rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know

// they will exit at the first iteration.

//===---------------------------------------------------------------------===//

/// Check to see if this loop has loop invariant conditions which lead to loop

/// exits. If so, we know that if the exit path is taken, it is at the first

/// loop iteration. This lets us predict exit values of PHI nodes that live in

/// loop header.

bool IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {

  // Verify the input to the pass is already in LCSSA form.

  assert(L->isLCSSAForm(*DT));

  SmallVector<BasicBlock *, 8> ExitBlocks;

  L->getUniqueExitBlocks(ExitBlocks);

  bool MadeAnyChanges = false;

  for (auto *ExitBB : ExitBlocks) {

    // If there are no more PHI nodes in this exit block, then no more

    // values defined inside the loop are used on this path.

    for (PHINode &PN : ExitBB->phis()) {

      for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues();

           IncomingValIdx != E; ++IncomingValIdx) {

        auto *IncomingBB = PN.getIncomingBlock(IncomingValIdx);

        // Can we prove that the exit must run on the first iteration if it

        // runs at all?  (i.e. early exits are fine for our purposes, but

        // traces which lead to this exit being taken on the 2nd iteration

        // aren't.)  Note that this is about whether the exit branch is

        // executed, not about whether it is taken.

        if (!L->getLoopLatch() ||

            !DT->dominates(IncomingBB, L->getLoopLatch()))

          continue;

        // Get condition that leads to the exit path.

        auto *TermInst = IncomingBB->getTerminator();

        Value *Cond = nullptr;

        if (auto *BI = dyn_cast<BranchInst>(TermInst)) {

          // Must be a conditional branch, otherwise the block

          // should not be in the loop.

          Cond = BI->getCondition();

        } else if (auto *SI = dyn_cast<SwitchInst>(TermInst))

          Cond = SI->getCondition();

        else

          continue;

        if (!L->isLoopInvariant(Cond))

          continue;

        auto *ExitVal = dyn_cast<PHINode>(PN.getIncomingValue(IncomingValIdx));

        // Only deal with PHIs in the loop header.

        if (!ExitVal || ExitVal->getParent() != L->getHeader())

          continue;

        // If ExitVal is a PHI on the loop header, then we know its

        // value along this exit because the exit can only be taken

        // on the first iteration.

        auto *LoopPreheader = L->getLoopPreheader();

        assert(LoopPreheader && "Invalid loop");

        int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);

        if (PreheaderIdx != -1) {

          assert(ExitVal->getParent() == L->getHeader() &&

                 "ExitVal must be in loop header");

          MadeAnyChanges = true;

          PN.setIncomingValue(IncomingValIdx,

                              ExitVal->getIncomingValue(PreheaderIdx));

          SE->forgetValue(&PN);

        }

      }

    }

  }

  return MadeAnyChanges;

}

//===----------------------------------------------------------------------===//

//  IV Widening - Extend the width of an IV to cover its widest uses.

//===----------------------------------------------------------------------===//

/// Update information about the induction variable that is extended by this

/// sign or zero extend operation. This is used to determine the final width of

/// the IV before actually widening it.

static void visitIVCast(CastInst *Cast, WideIVInfo &WI,

                        ScalarEvolution *SE,

                        const TargetTransformInfo *TTI) {

  bool IsSigned = Cast->getOpcode() == Instruction::SExt;

  if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)

    return;

  Type *Ty = Cast->getType();

  uint64_t Width = SE->getTypeSizeInBits(Ty);

  if (!Cast->getModule()->getDataLayout().isLegalInteger(Width))

    return;

  // Check that `Cast` actually extends the induction variable (we rely on this

  // later).  This takes care of cases where `Cast` is extending a truncation of

  // the narrow induction variable, and thus can end up being narrower than the

  // "narrow" induction variable.

  uint64_t NarrowIVWidth = SE->getTypeSizeInBits(WI.NarrowIV->getType());

  if (NarrowIVWidth >= Width)

    return;

  // Cast is either an sext or zext up to this point.

  // We should not widen an indvar if arithmetics on the wider indvar are more

  // expensive than those on the narrower indvar. We check only the cost of ADD

  // because at least an ADD is required to increment the induction variable. We

  // could compute more comprehensively the cost of all instructions on the

  // induction variable when necessary.

  if (TTI &&

      TTI->getArithmeticInstrCost(Instruction::Add, Ty) >

          TTI->getArithmeticInstrCost(Instruction::Add,

                                      Cast->getOperand(0)->getType())) {

    return;

  }

  if (!WI.WidestNativeType ||

      Width > SE->getTypeSizeInBits(WI.WidestNativeType)) {

    WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);

    WI.IsSigned = IsSigned;

    return;

  }

  // We extend the IV to satisfy the sign of its user(s), or 'signed'

  // if there are multiple users with both sign- and zero extensions,

  // in order not to introduce nondeterministic behaviour based on the

  // unspecified order of a PHI nodes' users-iterator.

  WI.IsSigned |= IsSigned;

}

//===----------------------------------------------------------------------===//

//  Live IV Reduction - Minimize IVs live across the loop.

//===----------------------------------------------------------------------===//

//===----------------------------------------------------------------------===//

//  Simplification of IV users based on SCEV evaluation.

//===----------------------------------------------------------------------===//

namespace {

class IndVarSimplifyVisitor : public IVVisitor {

  ScalarEvolution *SE;

  const TargetTransformInfo *TTI;

  PHINode *IVPhi;

public:

  WideIVInfo WI;

  IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,

                        const TargetTransformInfo *TTI,

                        const DominatorTree *DTree)

    : SE(SCEV), TTI(TTI), IVPhi(IV) {

    DT = DTree;

    WI.NarrowIV = IVPhi;

  }

  // Implement the interface used by simplifyUsersOfIV.

  void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }

};

} // end anonymous namespace

/// Iteratively perform simplification on a worklist of IV users. Each

/// successive simplification may push more users which may themselves be

/// candidates for simplification.

///

/// Sign/Zero extend elimination is interleaved with IV simplification.

bool IndVarSimplify::simplifyAndExtend(Loop *L,

                                       SCEVExpander &Rewriter,

                                       LoopInfo *LI) {

  SmallVector<WideIVInfo, 8> WideIVs;

  auto *GuardDecl = L->getBlocks()[0]->getModule()->getFunction(

          Intrinsic::getName(Intrinsic::experimental_guard));

  bool HasGuards = GuardDecl && !GuardDecl->use_empty();

  SmallVector<PHINode *, 8> LoopPhis;

  for (PHINode &PN : L->getHeader()->phis())

    LoopPhis.push_back(&PN);

  // Each round of simplification iterates through the SimplifyIVUsers worklist

  // for all current phis, then determines whether any IVs can be

  // widened. Widening adds new phis to LoopPhis, inducing another round of

  // simplification on the wide IVs.

  bool Changed = false;

  while (!LoopPhis.empty()) {

    // Evaluate as many IV expressions as possible before widening any IVs. This

    // forces SCEV to set no-wrap flags before evaluating sign/zero

    // extension. The first time SCEV attempts to normalize sign/zero extension,

    // the result becomes final. So for the most predictable results, we delay

    // evaluation of sign/zero extend evaluation until needed, and avoid running

    // other SCEV based analysis prior to simplifyAndExtend.

    do {

      PHINode *CurrIV = LoopPhis.pop_back_val();

      // Information about sign/zero extensions of CurrIV.

      IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);

      Changed |= simplifyUsersOfIV(CurrIV, SE, DT, LI, TTI, DeadInsts, Rewriter,

                                   &Visitor);

      if (Visitor.WI.WidestNativeType) {

        WideIVs.push_back(Visitor.WI);

      }

    } while(!LoopPhis.empty());

    // Continue if we disallowed widening.

    if (!WidenIndVars)

      continue;

    for (; !WideIVs.empty(); WideIVs.pop_back()) {

      unsigned ElimExt;

      unsigned Widened;

      if (PHINode *WidePhi = createWideIV(WideIVs.back(), LI, SE, Rewriter,

                                          DT, DeadInsts, ElimExt, Widened,

                                          HasGuards, UsePostIncrementRanges)) {

        NumElimExt += ElimExt;

        NumWidened += Widened;

        Changed = true;

        LoopPhis.push_back(WidePhi);

      }

    }

  }

  return Changed;

}

//===----------------------------------------------------------------------===//

//  linearFunctionTestReplace and its kin. Rewrite the loop exit condition.

//===----------------------------------------------------------------------===//

/// Given an Value which is hoped to be part of an add recurance in the given

/// loop, return the associated Phi node if so.  Otherwise, return null.  Note

/// that this is less general than SCEVs AddRec checking.

static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L) {

  Instruction *IncI = dyn_cast<Instruction>(IncV);

  if (!IncI)

    return nullptr;

  switch (IncI->getOpcode()) {

  case Instruction::Add:

  case Instruction::Sub:

    break;

  case Instruction::GetElementPtr:

    // An IV counter must preserve its type.

    if (IncI->getNumOperands() == 2)

      break;

    [[fallthrough]];

  default:

    return nullptr;

  }

  PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0));

  if (Phi && Phi->getParent() == L->getHeader()) {

    if (L->isLoopInvariant(IncI->getOperand(1)))

      return Phi;

    return nullptr;

  }

  if (IncI->getOpcode() == Instruction::GetElementPtr)

    return nullptr;

  // Allow add/sub to be commuted.

  Phi = dyn_cast<PHINode>(IncI->getOperand(1));

  if (Phi && Phi->getParent() == L->getHeader()) {

    if (L->isLoopInvariant(IncI->getOperand(0)))

      return Phi;

  }

  return nullptr;

}

/// Whether the current loop exit test is based on this value.  Currently this

/// is limited to a direct use in the loop condition.

static bool isLoopExitTestBasedOn(Value *V, BasicBlock *ExitingBB) {

  BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());

  ICmpInst *ICmp = dyn_cast<ICmpInst>(BI->getCondition());

  // TODO: Allow non-icmp loop test.

  if (!ICmp)

    return false;

  // TODO: Allow indirect use.

  return ICmp->getOperand(0) == V || ICmp->getOperand(1) == V;

}

/// linearFunctionTestReplace policy. Return true unless we can show that the

/// current exit test is already sufficiently canonical.

static bool needsLFTR(Loop *L, BasicBlock *ExitingBB) {

  assert(L->getLoopLatch() && "Must be in simplified form");

  // Avoid converting a constant or loop invariant test back to a runtime

  // test.  This is critical for when SCEV's cached ExitCount is less precise

  // than the current IR (such as after we've proven a particular exit is

  // actually dead and thus the BE count never reaches our ExitCount.)

  BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());

  if (L->isLoopInvariant(BI->getCondition()))

    return false;

  // Do LFTR to simplify the exit condition to an ICMP.

  ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition());

  if (!Cond)

    return true;

  // Do LFTR to simplify the exit ICMP to EQ/NE

  ICmpInst::Predicate Pred = Cond->getPredicate();

  if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)

    return true;

  // Look for a loop invariant RHS

  Value *LHS = Cond->getOperand(0);

  Value *RHS = Cond->getOperand(1);

  if (!L->isLoopInvariant(RHS)) {

    if (!L->isLoopInvariant(LHS))

      return true;

    std::swap(LHS, RHS);

  }

  // Look for a simple IV counter LHS

  PHINode *Phi = dyn_cast<PHINode>(LHS);

  if (!Phi)

    Phi = getLoopPhiForCounter(LHS, L);

  if (!Phi)

    return true;

  // Do LFTR if PHI node is defined in the loop, but is *not* a counter.

  int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());

  if (Idx < 0)

    return true;

  // Do LFTR if the exit condition's IV is *not* a simple counter.

  Value *IncV = Phi->getIncomingValue(Idx);

  return Phi != getLoopPhiForCounter(IncV, L);

}

/// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils

/// down to checking that all operands are constant and listing instructions

/// that may hide undef.

static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited,

                               unsigned Depth) {

  if (isa<Constant>(V))

    return !isa<UndefValue>(V);

  if (Depth >= 6)

    return false;

  // Conservatively handle non-constant non-instructions. For example, Arguments

  // may be undef.

  Instruction *I = dyn_cast<Instruction>(V);

  if (!I)

    return false;

  // Load and return values may be undef.

  if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I))

    return false;

  // Optimistically handle other instructions.

  for (Value *Op : I->operands()) {

    if (!Visited.insert(Op).second)

      continue;

    if (!hasConcreteDefImpl(Op, Visited, Depth+1))

      return false;

  }

  return true;

}

/// Return true if the given value is concrete. We must prove that undef can

/// never reach it.

///

/// TODO: If we decide that this is a good approach to checking for undef, we

/// may factor it into a common location.

static bool hasConcreteDef(Value *V) {

  SmallPtrSet<Value*, 8> Visited;

  Visited.insert(V);

  return hasConcreteDefImpl(V, Visited, 0);

}

/// Return true if the given phi is a "counter" in L.  A counter is an

/// add recurance (of integer or pointer type) with an arbitrary start, and a

/// step of 1.  Note that L must have exactly one latch.

static bool isLoopCounter(PHINode* Phi, Loop *L,

                          ScalarEvolution *SE) {

  assert(Phi->getParent() == L->getHeader());

  assert(L->getLoopLatch());

  if (!SE->isSCEVable(Phi->getType()))

    return false;

  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));

  if (!AR || AR->getLoop() != L || !AR->isAffine())

    return false;

  const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));

  if (!Step || !Step->isOne())

    return false;

  int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());

  Value *IncV = Phi->getIncomingValue(LatchIdx);

  return (getLoopPhiForCounter(IncV, L) == Phi &&

          isa<SCEVAddRecExpr>(SE->getSCEV(IncV)));

}

/// Search the loop header for a loop counter (anadd rec w/step of one)

/// suitable for use by LFTR.  If multiple counters are available, select the

/// "best" one based profitable heuristics.

///

/// BECount may be an i8* pointer type. The pointer difference is already

/// valid count without scaling the address stride, so it remains a pointer

/// expression as far as SCEV is concerned.

static PHINode *FindLoopCounter(Loop *L, BasicBlock *ExitingBB,

                                const SCEV *BECount,

                                ScalarEvolution *SE, DominatorTree *DT) {

  uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());

  Value *Cond = cast<BranchInst>(ExitingBB->getTerminator())->getCondition();

  // Loop over all of the PHI nodes, looking for a simple counter.

  PHINode *BestPhi = nullptr;

  const SCEV *BestInit = nullptr;

  BasicBlock *LatchBlock = L->getLoopLatch();

  assert(LatchBlock && "Must be in simplified form");

  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();

  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {

    PHINode *Phi = cast<PHINode>(I);

    if (!isLoopCounter(Phi, L, SE))

      continue;

    const auto *AR = cast<SCEVAddRecExpr>(SE->getSCEV(Phi));

    // AR may be a pointer type, while BECount is an integer type.

    // AR may be wider than BECount. With eq/ne tests overflow is immaterial.

    // AR may not be a narrower type, or we may never exit.

    uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());

    if (PhiWidth < BCWidth || !DL.isLegalInteger(PhiWidth))

      continue;

    // Avoid reusing a potentially undef value to compute other values that may

    // have originally had a concrete definition.

    if (!hasConcreteDef(Phi)) {

      // We explicitly allow unknown phis as long as they are already used by

      // the loop exit test.  This is legal since performing LFTR could not

      // increase the number of undef users.

      Value *IncPhi = Phi->getIncomingValueForBlock(LatchBlock);

      if (!isLoopExitTestBasedOn(Phi, ExitingBB) &&

          !isLoopExitTestBasedOn(IncPhi, ExitingBB))

        continue;

    }

    // Avoid introducing undefined behavior due to poison which didn't exist in

    // the original program.  (Annoyingly, the rules for poison and undef

    // propagation are distinct, so this does NOT cover the undef case above.)

    // We have to ensure that we don't introduce UB by introducing a use on an

    // iteration where said IV produces poison.  Our strategy here differs for

    // pointers and integer IVs.  For integers, we strip and reinfer as needed,

    // see code in linearFunctionTestReplace.  For pointers, we restrict

    // transforms as there is no good way to reinfer inbounds once lost.

    if (!Phi->getType()->isIntegerTy() &&

        !mustExecuteUBIfPoisonOnPathTo(Phi, ExitingBB->getTerminator(), DT))

      continue;

    const SCEV *Init = AR->getStart();

    if (BestPhi && !isAlmostDeadIV(BestPhi, LatchBlock, Cond)) {

      // Don't force a live loop counter if another IV can be used.

      if (isAlmostDeadIV(Phi, LatchBlock, Cond))

        continue;

      // Prefer to count-from-zero. This is a more "canonical" counter form. It

      // also prefers integer to pointer IVs.

      if (BestInit->isZero() != Init->isZero()) {

        if (BestInit->isZero())

          continue;

      }

      // If two IVs both count from zero or both count from nonzero then the

      // narrower is likely a dead phi that has been widened. Use the wider phi

      // to allow the other to be eliminated.

      else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))

        continue;

    }

    BestPhi = Phi;

    BestInit = Init;

  }

  return BestPhi;

}

/// Insert an IR expression which computes the value held by the IV IndVar

/// (which must be an loop counter w/unit stride) after the backedge of loop L

/// is taken ExitCount times.

static Value *genLoopLimit(PHINode *IndVar, BasicBlock *ExitingBB,

                           const SCEV *ExitCount, bool UsePostInc, Loop *L,

                           SCEVExpander &Rewriter, ScalarEvolution *SE) {

  assert(isLoopCounter(IndVar, L, SE));

  assert(ExitCount->getType()->isIntegerTy() && "exit count must be integer");

  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));

  assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride");

  // For integer IVs, truncate the IV before computing the limit unless we

  // know apriori that the limit must be a constant when evaluated in the

  // bitwidth of the IV.  We prefer (potentially) keeping a truncate of the

  // IV in the loop over a (potentially) expensive expansion of the widened

  // exit count add(zext(add)) expression.

  if (IndVar->getType()->isIntegerTy() &&

      SE->getTypeSizeInBits(AR->getType()) >

      SE->getTypeSizeInBits(ExitCount->getType())) {

    const SCEV *IVInit = AR->getStart();

    if (!isa<SCEVConstant>(IVInit) || !isa<SCEVConstant>(ExitCount))

      AR = cast<SCEVAddRecExpr>(SE->getTruncateExpr(AR, ExitCount->getType()));

  }

  const SCEVAddRecExpr *ARBase = UsePostInc ? AR->getPostIncExpr(*SE) : AR;

  const SCEV *IVLimit = ARBase->evaluateAtIteration(ExitCount, *SE);

  assert(SE->isLoopInvariant(IVLimit, L) &&

         "Computed iteration count is not loop invariant!");

  return Rewriter.expandCodeFor(IVLimit, ARBase->getType(),

                                ExitingBB->getTerminator());

}

/// This method rewrites the exit condition of the loop to be a canonical !=

/// comparison against the incremented loop induction variable.  This pass is

/// able to rewrite the exit tests of any loop where the SCEV analysis can

/// determine a loop-invariant trip count of the loop, which is actually a much

/// broader range than just linear tests.

bool IndVarSimplify::

linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,

                          const SCEV *ExitCount,

                          PHINode *IndVar, SCEVExpander &Rewriter) {

  assert(L->getLoopLatch() && "Loop no longer in simplified form?");

  assert(isLoopCounter(IndVar, L, SE));

  Instruction * const IncVar =

    cast<Instruction>(IndVar->getIncomingValueForBlock(L->getLoopLatch()));

  // Initialize CmpIndVar to the preincremented IV.

  Value *CmpIndVar = IndVar;

  bool UsePostInc = false;

  // If the exiting block is the same as the backedge block, we prefer to

  // compare against the post-incremented value, otherwise we must compare

  // against the preincremented value.

  if (ExitingBB == L->getLoopLatch()) {

    // For pointer IVs, we chose to not strip inbounds which requires us not

    // to add a potentially UB introducing use.  We need to either a) show

    // the loop test we're modifying is already in post-inc form, or b) show

    // that adding a use must not introduce UB.

    bool SafeToPostInc =

        IndVar->getType()->isIntegerTy() ||

        isLoopExitTestBasedOn(IncVar, ExitingBB) ||

        mustExecuteUBIfPoisonOnPathTo(IncVar, ExitingBB->getTerminator(), DT);

    if (SafeToPostInc) {

      UsePostInc = true;

      CmpIndVar = IncVar;

    }

  }

  // It may be necessary to drop nowrap flags on the incrementing instruction

  // if either LFTR moves from a pre-inc check to a post-inc check (in which

  // case the increment might have previously been poison on the last iteration

  // only) or if LFTR switches to a different IV that was previously dynamically

  // dead (and as such may be arbitrarily poison). We remove any nowrap flags

  // that SCEV didn't infer for the post-inc addrec (even if we use a pre-inc

  // check), because the pre-inc addrec flags may be adopted from the original

  // instruction, while SCEV has to explicitly prove the post-inc nowrap flags.

  // TODO: This handling is inaccurate for one case: If we switch to a

  // dynamically dead IV that wraps on the first loop iteration only, which is

  // not covered by the post-inc addrec. (If the new IV was not dynamically

  // dead, it could not be poison on the first iteration in the first place.)

  if (auto *BO = dyn_cast<BinaryOperator>(IncVar)) {

    const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IncVar));

    if (BO->hasNoUnsignedWrap())

      BO->setHasNoUnsignedWrap(AR->hasNoUnsignedWrap());

    if (BO->hasNoSignedWrap())

      BO->setHasNoSignedWrap(AR->hasNoSignedWrap());

  }

  Value *ExitCnt = genLoopLimit(

      IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);

  assert(ExitCnt->getType()->isPointerTy() ==

             IndVar->getType()->isPointerTy() &&

         "genLoopLimit missed a cast");

  // Insert a new icmp_ne or icmp_eq instruction before the branch.

  BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());

  ICmpInst::Predicate P;

  if (L->contains(BI->getSuccessor(0)))

    P = ICmpInst::ICMP_NE;

  else

    P = ICmpInst::ICMP_EQ;

  IRBuilder<> Builder(BI);

  // The new loop exit condition should reuse the debug location of the

  // original loop exit condition.

  if (auto *Cond = dyn_cast<Instruction>(BI->getCondition()))

    Builder.SetCurrentDebugLocation(Cond->getDebugLoc());

  // For integer IVs, if we evaluated the limit in the narrower bitwidth to

  // avoid the expensive expansion of the limit expression in the wider type,

  // emit a truncate to narrow the IV to the ExitCount type.  This is safe

  // since we know (from the exit count bitwidth), that we can't self-wrap in

  // the narrower type.

  unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType());

  unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType());

  if (CmpIndVarSize > ExitCntSize) {

    assert(!CmpIndVar->getType()->isPointerTy() &&

           !ExitCnt->getType()->isPointerTy());

    // Before resorting to actually inserting the truncate, use the same

    // reasoning as from SimplifyIndvar::eliminateTrunc to see if we can extend

    // the other side of the comparison instead.  We still evaluate the limit

    // in the narrower bitwidth, we just prefer a zext/sext outside the loop to

    // a truncate within in.

    bool Extended = false;

    const SCEV *IV = SE->getSCEV(CmpIndVar);

    const SCEV *TruncatedIV = SE->getTruncateExpr(IV, ExitCnt->getType());

    const SCEV *ZExtTrunc =

      SE->getZeroExtendExpr(TruncatedIV, CmpIndVar->getType());

    if (ZExtTrunc == IV) {

      Extended = true;

      ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->getType(),

                                   "wide.trip.count");

    } else {

      const SCEV *SExtTrunc =

        SE->getSignExtendExpr(TruncatedIV, CmpIndVar->getType());