llvm/lib/Analysis/IVDescriptors.cpp

//===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
//
// 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 "describes" induction and recurrence variables.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h"

using namespace llvm;
using namespace llvm::PatternMatch;
using namespace llvm::SCEVPatternMatch;

#define DEBUG_TYPE "iv-descriptors"

bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
                                        SmallPtrSetImpl<Instruction *> &Set) {
  for (const Use &Use : I->operands())
    if (!Set.count(dyn_cast<Instruction>(Use)))
      return false;
  return true;
}

bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
  switch (Kind) {
  default:
    break;
  case RecurKind::AddChainWithSubs:
  case RecurKind::Sub:
  case RecurKind::Add:
  case RecurKind::Mul:
  case RecurKind::Or:
  case RecurKind::And:
  case RecurKind::Xor:
  case RecurKind::SMax:
  case RecurKind::SMin:
  case RecurKind::UMax:
  case RecurKind::UMin:
  case RecurKind::AnyOf:
  case RecurKind::FindIV:
  case RecurKind::FindLast:
    return true;
  }
  return false;
}

bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
  return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
}

/// Determines if Phi may have been type-promoted. If Phi has a single user
/// that ANDs the Phi with a type mask, return the user. RT is updated to
/// account for the narrower bit width represented by the mask, and the AND
/// instruction is added to CI.
static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
                                   SmallPtrSetImpl<Instruction *> &Visited,
                                   SmallPtrSetImpl<Instruction *> &CI) {
  if (!Phi->hasOneUse())
    return Phi;

  const APInt *M = nullptr;
  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());

  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
  // with a new integer type of the corresponding bit width.
  if (match(J, m_And(m_Instruction(I), m_APInt(M)))) {
    int32_t Bits = (*M + 1).exactLogBase2();
    if (Bits > 0) {
      RT = IntegerType::get(Phi->getContext(), Bits);
      Visited.insert(Phi);
      CI.insert(J);
      return J;
    }
  }
  return Phi;
}

bool RecurrenceDescriptor::isSubRecurrenceKind(RecurKind Kind) {
  return Kind == RecurKind::Sub || Kind == RecurKind::FSub;
}

/// Compute the minimal bit width needed to represent a reduction whose exit
/// instruction is given by Exit.
static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
                                                     DemandedBits *DB,
                                                     AssumptionCache *AC,
                                                     DominatorTree *DT) {
  bool IsSigned = false;
  const DataLayout &DL = Exit->getDataLayout();
  uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());

  if (DB) {
    // Use the demanded bits analysis to determine the bits that are live out
    // of the exit instruction, rounding up to the nearest power of two. If the
    // use of demanded bits results in a smaller bit width, we know the value
    // must be positive (i.e., IsSigned = false), because if this were not the
    // case, the sign bit would have been demanded.
    auto Mask = DB->getDemandedBits(Exit);
    MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();
  }

  if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
    // If demanded bits wasn't able to limit the bit width, we can try to use
    // value tracking instead. This can be the case, for example, if the value
    // may be negative.
    auto NumSignBits = ComputeNumSignBits(Exit, DL, AC, nullptr, DT);
    auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
    MaxBitWidth = NumTypeBits - NumSignBits;
    KnownBits Bits = computeKnownBits(Exit, DL);
    if (!Bits.isNonNegative()) {
      // If the value is not known to be non-negative, we set IsSigned to true,
      // meaning that we will use sext instructions instead of zext
      // instructions to restore the original type.
      IsSigned = true;
      // Make sure at least one sign bit is included in the result, so it
      // will get properly sign-extended.
      ++MaxBitWidth;
    }
  }
  MaxBitWidth = llvm::bit_ceil(MaxBitWidth);

  return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
                        IsSigned);
}

/// Collect cast instructions that can be ignored in the vectorizer's cost
/// model, given a reduction exit value and the minimal type in which the
// reduction can be represented. Also search casts to the recurrence type
// to find the minimum width used by the recurrence.
static void collectCastInstrs(Loop *TheLoop, Instruction *Exit,
                              Type *RecurrenceType,
                              SmallPtrSetImpl<Instruction *> &Casts,
                              unsigned &MinWidthCastToRecurTy) {

  SmallVector<Instruction *, 8> Worklist;
  SmallPtrSet<Instruction *, 8> Visited;
  Worklist.push_back(Exit);
  MinWidthCastToRecurTy = -1U;

  while (!Worklist.empty()) {
    Instruction *Val = Worklist.pop_back_val();
    Visited.insert(Val);
    if (auto *Cast = dyn_cast<CastInst>(Val)) {
      if (Cast->getSrcTy() == RecurrenceType) {
        // If the source type of a cast instruction is equal to the recurrence
        // type, it will be eliminated, and should be ignored in the vectorizer
        // cost model.
        Casts.insert(Cast);
        continue;
      }
      if (Cast->getDestTy() == RecurrenceType) {
        // The minimum width used by the recurrence is found by checking for
        // casts on its operands. The minimum width is used by the vectorizer
        // when finding the widest type for in-loop reductions without any
        // loads/stores.
        MinWidthCastToRecurTy = std::min<unsigned>(
            MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());
        continue;
      }
    }
    // Add all operands to the work list if they are loop-varying values that
    // we haven't yet visited.
    for (Value *O : cast<User>(Val)->operands())
      if (auto *I = dyn_cast<Instruction>(O))
        if (TheLoop->contains(I) && !Visited.count(I))
          Worklist.push_back(I);
  }
}

// Check if a given Phi node can be recognized as an ordered reduction for
// vectorizing floating point operations without unsafe math.
static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
                                  Instruction *Exit, PHINode *Phi) {
  // Currently only FAdd and FMulAdd are supported.
  if (Kind != RecurKind::FAdd && Kind != RecurKind::FMulAdd)
    return false;

  if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)
    return false;

  if (Kind == RecurKind::FMulAdd &&
      !RecurrenceDescriptor::isFMulAddIntrinsic(Exit))
    return false;

  // Ensure the exit instruction has only one user other than the reduction PHI
  if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))
    return false;

  // The only pattern accepted is the one in which the reduction PHI
  // is used as one of the operands of the exit instruction
  auto *Op0 = Exit->getOperand(0);
  auto *Op1 = Exit->getOperand(1);
  if (Kind == RecurKind::FAdd && Op0 != Phi && Op1 != Phi)
    return false;
  if (Kind == RecurKind::FMulAdd && Exit->getOperand(2) != Phi)
    return false;

  LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi
                    << ", ExitInst: " << *Exit << "\n");

  return true;
}

// Collect FMF from a value and its associated fcmp in select patterns
static FastMathFlags collectMinMaxFMF(Value *V) {
  FastMathFlags FMF = cast<FPMathOperator>(V)->getFastMathFlags();
  if (auto *Sel = dyn_cast<SelectInst>(V)) {
    // Accept FMF from either fcmp or select in a min/max idiom.
    // TODO: Remove this when FMF propagation is fixed or we standardize on
    // intrinsics.
    if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
      FMF |= FCmp->getFastMathFlags();
  }
  return FMF;
}

static std::optional<FastMathFlags>
hasRequiredFastMathFlags(FPMathOperator *FPOp, RecurKind &RK) {
  bool HasRequiredFMF = FPOp && FPOp->hasNoNaNs() && FPOp->hasNoSignedZeros();
  if (HasRequiredFMF)
    return collectMinMaxFMF(FPOp);

  switch (RK) {
  case RecurKind::FMinimum:
  case RecurKind::FMaximum:
  case RecurKind::FMinimumNum:
  case RecurKind::FMaximumNum:
    break;

  case RecurKind::FMax:
    if (!match(FPOp, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value())))
      return std::nullopt;
    RK = RecurKind::FMaxNum;
    break;
  case RecurKind::FMin:
    if (!match(FPOp, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value())))
      return std::nullopt;
    RK = RecurKind::FMinNum;
    break;
  default:
    return std::nullopt;
  }
  return collectMinMaxFMF(FPOp);
}

static RecurrenceDescriptor getMinMaxRecurrence(PHINode *Phi, Loop *TheLoop,
                                                ScalarEvolution *SE) {
  Type *Ty = Phi->getType()->getScalarType();
  BasicBlock *Latch = TheLoop->getLoopLatch();
  if (Phi->getNumIncomingValues() != 2 ||
      Phi->getParent() != TheLoop->getHeader() ||
      (!Ty->isIntegerTy() && !Ty->isFloatingPointTy()) || !Latch)
    return {};

  auto GetMinMaxRK = [](Value *V, Value *&A, Value *&B) -> RecurKind {
    if (match(V, m_UMin(m_Value(A), m_Value(B))))
      return RecurKind::UMin;
    if (match(V, m_UMax(m_Value(A), m_Value(B))))
      return RecurKind::UMax;
    if (match(V, m_SMax(m_Value(A), m_Value(B))))
      return RecurKind::SMax;
    if (match(V, m_SMin(m_Value(A), m_Value(B))))
      return RecurKind::SMin;
    if (match(V, m_OrdOrUnordFMin(m_Value(A), m_Value(B))) ||
        match(V, m_Intrinsic<Intrinsic::minnum>(m_Value(A), m_Value(B))))
      return RecurKind::FMin;
    if (match(V, m_OrdOrUnordFMax(m_Value(A), m_Value(B))) ||
        match(V, m_Intrinsic<Intrinsic::maxnum>(m_Value(A), m_Value(B))))
      return RecurKind::FMax;
    if (match(V, m_FMinimum(m_Value(A), m_Value(B))))
      return RecurKind::FMinimum;
    if (match(V, m_FMaximum(m_Value(A), m_Value(B))))
      return RecurKind::FMaximum;
    if (match(V, m_Intrinsic<Intrinsic::minimumnum>(m_Value(A), m_Value(B))))
      return RecurKind::FMinimumNum;
    if (match(V, m_Intrinsic<Intrinsic::maximumnum>(m_Value(A), m_Value(B))))
      return RecurKind::FMaximumNum;
    return RecurKind::None;
  };

  FastMathFlags FMF = FastMathFlags::getFast();
  Value *BackedgeValue = Phi->getIncomingValueForBlock(Latch);
  RecurKind RK = RecurKind::None;
  // Walk def-use chains upwards from BackedgeValue to identify min/max
  // recurrences.
  SmallVector<Value *> WorkList({BackedgeValue});
  SmallPtrSet<Value *, 8> Chain({Phi});
  while (!WorkList.empty()) {
    Value *Cur = WorkList.pop_back_val();
    if (!Chain.insert(Cur).second)
      continue;
    auto *I = dyn_cast<Instruction>(Cur);
    if (!I || !TheLoop->contains(I))
      return {};
    if (auto *PN = dyn_cast<PHINode>(I)) {
      append_range(WorkList, PN->operands());
      continue;
    }
    Value *A, *B;
    RecurKind CurRK = GetMinMaxRK(Cur, A, B);
    if (CurRK == RecurKind::None || (RK != RecurKind::None && CurRK != RK))
      return {};

    RK = CurRK;
    // Check required fast-math flags for FP recurrences.
    if (RecurrenceDescriptor::isFPMinMaxRecurrenceKind(CurRK)) {
      auto CurFMF = hasRequiredFastMathFlags(cast<FPMathOperator>(Cur), RK);
      if (!CurFMF)
        return {};
      FMF &= *CurFMF;
    }

    if (auto *SI = dyn_cast<SelectInst>(I))
      Chain.insert(SI->getCondition());

    if (A == Phi || B == Phi)
      continue;

    // Add operand to worklist if it matches the pattern (exactly one must
    // match)
    Value *X, *Y;
    auto *IA = dyn_cast<Instruction>(A);
    auto *IB = dyn_cast<Instruction>(B);
    bool AMatches = IA && TheLoop->contains(IA) && GetMinMaxRK(A, X, Y) == RK;
    bool BMatches = IB && TheLoop->contains(IB) && GetMinMaxRK(B, X, Y) == RK;
    if (AMatches == BMatches) // Both or neither match
      return {};
    WorkList.push_back(AMatches ? A : B);
  }

  // Handle argmin/argmax pattern: PHI has uses outside the reduction chain
  // that are not intermediate min/max operations (which are handled below).
  // Requires integer min/max, and the PHI must be the only in-loop user of
  // BackedgeValue (so vectorizer can handle both PHIs together).
  bool PhiHasInvalidUses = any_of(Phi->users(), [&](Instruction *U) {
    Value *A, *B;
    return !Chain.contains(U) && TheLoop->contains(U) &&
           GetMinMaxRK(U, A, B) == RecurKind::None;
  });
  if (PhiHasInvalidUses) {
    if (!RecurrenceDescriptor::isMinMaxRecurrenceKind(RK) ||
        any_of(BackedgeValue->users(), [&](User *U) {
          auto *UI = cast<Instruction>(U);
          return UI != Phi && TheLoop->contains(UI);
        }))
      return {};
    return RecurrenceDescriptor(
        Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()),
        /*Exit=*/nullptr, /*Store=*/nullptr, RK, FastMathFlags(),
        /*ExactFP=*/nullptr, Phi->getType(), /*IsMultiUse=*/true);
  }

  // Validate chain entries and collect stores from chain entries and
  // intermediate ops.
  SmallVector<StoreInst *> Stores;
  for (Value *V : Chain) {
    for (User *U : V->users()) {
      if (Chain.contains(U))
        continue;
      auto *I = dyn_cast<Instruction>(U);
      if (!I || (!TheLoop->contains(I) && V != BackedgeValue))
        return {};
      if (!TheLoop->contains(I))
        continue;
      if (auto *SI = dyn_cast<StoreInst>(I)) {
        Stores.push_back(SI);
        continue;
      }
      // Must be intermediate min/max of the same kind.
      Value *A, *B;
      if (GetMinMaxRK(I, A, B) != RK)
        return {};
      for (User *IU : I->users()) {
        if (auto *SI = dyn_cast<StoreInst>(IU))
          Stores.push_back(SI);
        else if (!Chain.contains(IU))
          return {};
      }
    }
  }

  // Validate all stores go to same invariant address and are in the same block.
  StoreInst *IntermediateStore = nullptr;
  const SCEV *StorePtrSCEV = nullptr;
  for (StoreInst *SI : Stores) {
    if (!SE)
      return {};
    const SCEV *Ptr = SE->getSCEV(SI->getPointerOperand());
    if (!SE->isLoopInvariant(Ptr, TheLoop) ||
        (StorePtrSCEV && StorePtrSCEV != Ptr))
      return {};
    StorePtrSCEV = Ptr;
    if (!IntermediateStore)
      IntermediateStore = SI;
    else if (IntermediateStore->getParent() != SI->getParent())
      return {};
    else if (IntermediateStore->comesBefore(SI))
      IntermediateStore = SI;
  }

  return RecurrenceDescriptor(
      Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()),
      cast<Instruction>(BackedgeValue), IntermediateStore, RK, FMF, nullptr,
      Phi->getType());
}

// This matches a phi that selects between the original value (HeaderPhi) and an
// arbitrary non-reduction value.
static bool isFindLastLikePhi(PHINode *Phi, PHINode *HeaderPhi,
                              SmallPtrSetImpl<Instruction *> &ReductionInstrs) {
  unsigned NumNonReduxInputs = 0;
  for (const Value *Op : Phi->operands()) {
    if (!ReductionInstrs.contains(dyn_cast<Instruction>(Op))) {
      if (++NumNonReduxInputs > 1)
        return false;
    } else if (Op != HeaderPhi) {
      // TODO: Remove this restriction once chained phis are supported.
      return false;
    }
  }
  return NumNonReduxInputs == 1;
}

bool RecurrenceDescriptor::AddReductionVar(
    PHINode *Phi, RecurKind Kind, Loop *TheLoop, RecurrenceDescriptor &RedDes,
    DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT,
    ScalarEvolution *SE) {
  if (Phi->getNumIncomingValues() != 2)
    return false;

  // Reduction variables are only found in the loop header block.
  if (Phi->getParent() != TheLoop->getHeader())
    return false;

  // Obtain the reduction start value from the value that comes from the loop
  // preheader.
  if (!TheLoop->getLoopPreheader())
    return false;

  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
  // ExitInstruction is the single value which is used outside the loop.
  // We only allow for a single reduction value to be used outside the loop.
  // This includes users of the reduction, variables (which form a cycle
  // which ends in the phi node).
  Instruction *ExitInstruction = nullptr;

  // Variable to keep last visited store instruction. By the end of the
  // algorithm this variable will be either empty or having intermediate
  // reduction value stored in invariant address.
  StoreInst *IntermediateStore = nullptr;

  // Indicates that we found a reduction operation in our scan.
  bool FoundReduxOp = false;

  // We start with the PHI node and scan for all of the users of this
  // instruction. All users must be instructions that can be used as reduction
  // variables (such as ADD). We must have a single out-of-block user. The cycle
  // must include the original PHI.
  bool FoundStartPHI = false;

  // To recognize AnyOf patterns formed by a icmp select sequence, we store
  // the number of instruction we saw to make sure we only see one.
  unsigned NumCmpSelectPatternInst = 0;
  InstDesc ReduxDesc(false, nullptr);

  // To recognize find-lasts of conditional operations (such as loads or
  // divides), that need masking, we track non-phi users and if we've found a
  // "find-last-like" phi (see isFindLastLikePhi). We currently only support
  // find-last reduction chains with a single "find-last-like" phi and do not
  // allow any other operations.
  [[maybe_unused]] unsigned NumNonPHIUsers = 0;
  bool FoundFindLastLikePhi = false;

  // Data used for determining if the recurrence has been type-promoted.
  Type *RecurrenceType = Phi->getType();
  SmallPtrSet<Instruction *, 4> CastInsts;
  unsigned MinWidthCastToRecurrenceType;
  Instruction *Start = Phi;
  bool IsSigned = false;

  SmallPtrSet<Instruction *, 8> VisitedInsts;
  SmallVector<Instruction *, 8> Worklist;

  // Return early if the recurrence kind does not match the type of Phi. If the
  // recurrence kind is arithmetic, we attempt to look through AND operations
  // resulting from the type promotion performed by InstCombine.  Vector
  // operations are not limited to the legal integer widths, so we may be able
  // to evaluate the reduction in the narrower width.
  // Check the scalar type to handle both scalar and vector types.
  Type *ScalarTy = RecurrenceType->getScalarType();
  if (Kind == RecurKind::FindLast) {
    // FindLast supports all primitive scalar types.
    if (!ScalarTy->isFloatingPointTy() && !ScalarTy->isIntegerTy() &&
        !ScalarTy->isPointerTy())
      return false;
  } else if (ScalarTy->isFloatingPointTy()) {
    if (!isFloatingPointRecurrenceKind(Kind))
      return false;
  } else if (ScalarTy->isIntegerTy()) {
    if (!isIntegerRecurrenceKind(Kind))
      return false;
    Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
  } else {
    // Pointer min/max may exist, but it is not supported as a reduction op.
    return false;
  }

  Worklist.push_back(Start);
  VisitedInsts.insert(Start);

  // Start with all flags set because we will intersect this with the reduction
  // flags from all the reduction operations.
  FastMathFlags FMF = FastMathFlags::getFast();

  // The first instruction in the use-def chain of the Phi node that requires
  // exact floating point operations.
  Instruction *ExactFPMathInst = nullptr;

  // A value in the reduction can be used:
  //  - By the reduction:
  //      - Reduction operation:
  //        - One use of reduction value (safe).
  //        - Multiple use of reduction value (not safe).
  //      - PHI:
  //        - All uses of the PHI must be the reduction (safe).
  //        - Otherwise, not safe.
  //  - By instructions outside of the loop (safe).
  //      * One value may have several outside users, but all outside
  //        uses must be of the same value.
  //  - By store instructions with a loop invariant address (safe with
  //    the following restrictions):
  //      * If there are several stores, all must have the same address.
  //      * Final value should be stored in that loop invariant address.
  //  - By an instruction that is not part of the reduction (not safe).
  //    This is either:
  //      * An instruction type other than PHI or the reduction operation.
  //      * A PHI in the header other than the initial PHI.
  while (!Worklist.empty()) {
    Instruction *Cur = Worklist.pop_back_val();

    // Store instructions are allowed iff it is the store of the reduction
    // value to the same loop invariant memory location.
    if (auto *SI = dyn_cast<StoreInst>(Cur)) {
      if (!SE) {
        LLVM_DEBUG(dbgs() << "Store instructions are not processed without "
                          << "Scalar Evolution Analysis\n");
        return false;
      }

      const SCEV *PtrScev = SE->getSCEV(SI->getPointerOperand());
      // Check it is the same address as previous stores
      if (IntermediateStore) {
        const SCEV *OtherScev =
            SE->getSCEV(IntermediateStore->getPointerOperand());

        if (OtherScev != PtrScev) {
          LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "
                            << "inside the loop: " << *SI->getPointerOperand()
                            << " and "
                            << *IntermediateStore->getPointerOperand() << '\n');
          return false;
        }
      }

      // Check the pointer is loop invariant
      if (!SE->isLoopInvariant(PtrScev, TheLoop)) {
        LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "
                          << "inside the loop: " << *SI->getPointerOperand()
                          << '\n');
        return false;
      }

      // IntermediateStore is always the last store in the loop.
      IntermediateStore = SI;
      continue;
    }

    // No Users.
    // If the instruction has no users then this is a broken chain and can't be
    // a reduction variable.
    if (Cur->use_empty())
      return false;

    bool IsAPhi = isa<PHINode>(Cur);
    if (!IsAPhi)
      ++NumNonPHIUsers;

    // A header PHI use other than the original PHI.
    if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
      return false;

    // Reductions of instructions such as Div, and Sub is only possible if the
    // LHS is the reduction variable.
    if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
        !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
        !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
      return false;

    // Any reduction instruction must be of one of the allowed kinds. We ignore
    // the starting value (the Phi or an AND instruction if the Phi has been
    // type-promoted).
    if (Cur != Start) {
      ReduxDesc = isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, SE);
      ExactFPMathInst = ExactFPMathInst == nullptr
                            ? ReduxDesc.getExactFPMathInst()
                            : ExactFPMathInst;
      if (!ReduxDesc.isRecurrence())
        return false;
      // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
      if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi)
        FMF &= collectMinMaxFMF(ReduxDesc.getPatternInst());
      // Update this reduction kind if we matched a new instruction.
      // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
      //       state accurate while processing the worklist?
      if (ReduxDesc.getRecKind() != RecurKind::None)
        Kind = ReduxDesc.getRecKind();
    }

    bool IsASelect = isa<SelectInst>(Cur);

    // A conditional reduction operation must only have 2 or less uses in
    // VisitedInsts.
    if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
        hasMultipleUsesOf(Cur, VisitedInsts, 2))
      return false;

    // A reduction operation must only have one use of the reduction value.
    if (!IsAPhi && !IsASelect && !isAnyOfRecurrenceKind(Kind) &&
        hasMultipleUsesOf(Cur, VisitedInsts, 1))
      return false;

    // All inputs to a PHI node must be a reduction value, unless the phi is a
    // "FindLast-like" phi (described below).
    if (IsAPhi && Cur != Phi) {
      if (!areAllUsesIn(Cur, VisitedInsts)) {
        // A "FindLast-like" phi acts like a conditional select between the
        // previous reduction value, and an arbitrary value. Note: Multiple
        // "FindLast-like" phis are not supported see:
        // IVDescriptorsTest.UnsupportedFindLastPhi.
        FoundFindLastLikePhi =
            Kind == RecurKind::FindLast && !FoundFindLastLikePhi &&
            isFindLastLikePhi(cast<PHINode>(Cur), Phi, VisitedInsts);
        if (!FoundFindLastLikePhi)
          return false;
      }
    }

    if (isAnyOfRecurrenceKind(Kind) && IsASelect)
      ++NumCmpSelectPatternInst;

    // Check  whether we found a reduction operator.
    FoundReduxOp |= (!IsAPhi || FoundFindLastLikePhi) && Cur != Start;

    // Process users of current instruction. Push non-PHI nodes after PHI nodes
    // onto the stack. This way we are going to have seen all inputs to PHI
    // nodes once we get to them.
    SmallVector<Instruction *, 8> NonPHIs;
    SmallVector<Instruction *, 8> PHIs;
    for (User *U : Cur->users()) {
      Instruction *UI = cast<Instruction>(U);

      // If the user is a call to llvm.fmuladd then the instruction can only be
      // the final operand.
      if (isFMulAddIntrinsic(UI))
        if (Cur == UI->getOperand(0) || Cur == UI->getOperand(1))
          return false;

      // Check if we found the exit user.
      BasicBlock *Parent = UI->getParent();
      if (!TheLoop->contains(Parent)) {
        // If we already know this instruction is used externally, move on to
        // the next user.
        if (ExitInstruction == Cur)
          continue;

        // Exit if you find multiple values used outside or if the header phi
        // node is being used. In this case the user uses the value of the
        // previous iteration, in which case we would loose "VF-1" iterations of
        // the reduction operation if we vectorize.
        if (ExitInstruction != nullptr || Cur == Phi)
          return false;

        // The instruction used by an outside user must be the last instruction
        // before we feed back to the reduction phi. Otherwise, we loose VF-1
        // operations on the value.
        if (!is_contained(Phi->operands(), Cur))
          return false;

        ExitInstruction = Cur;
        continue;
      }

      // Process instructions only once (termination). Each reduction cycle
      // value must only be used once, except by phi nodes and conditional
      // reductions which are represented as a cmp followed by a select.
      InstDesc IgnoredVal(false, nullptr);
      if (VisitedInsts.insert(UI).second) {
        if (isa<PHINode>(UI)) {
          PHIs.push_back(UI);
        } else {
          StoreInst *SI = dyn_cast<StoreInst>(UI);
          if (SI && SI->getPointerOperand() == Cur) {
            // Reduction variable chain can only be stored somewhere but it
            // can't be used as an address.
            return false;
          }
          NonPHIs.push_back(UI);
        }
      } else if (!isa<PHINode>(UI) &&
                 ((!isConditionalRdxPattern(UI).isRecurrence() &&
                   !isAnyOfPattern(TheLoop, Phi, UI, IgnoredVal)
                        .isRecurrence())))
        return false;

      // Remember that we completed the cycle.
      if (UI == Phi)
        FoundStartPHI = true;
    }
    Worklist.append(PHIs.begin(), PHIs.end());
    Worklist.append(NonPHIs.begin(), NonPHIs.end());
  }

  // We only expect to match a single "find-last-like" phi per find-last
  // reduction, with no non-phi operations in the reduction use chain.
  assert((!FoundFindLastLikePhi ||
          (Kind == RecurKind::FindLast && NumNonPHIUsers == 0)) &&
         "Unexpectedly matched a 'find-last-like' phi");

  if (isAnyOfRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
    return false;

  if (IntermediateStore) {
    // Check that stored value goes to the phi node again. This way we make sure
    // that the value stored in IntermediateStore is indeed the final reduction
    // value.
    if (!is_contained(Phi->operands(), IntermediateStore->getValueOperand())) {
      LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "
                        << *IntermediateStore << '\n');
      return false;
    }

    // If there is an exit instruction it's value should be stored in
    // IntermediateStore
    if (ExitInstruction &&
        IntermediateStore->getValueOperand() != ExitInstruction) {
      LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "
                           "store last calculated value of the reduction: "
                        << *IntermediateStore << '\n');
      return false;
    }

    // If all uses are inside the loop (intermediate stores), then the
    // reduction value after the loop will be the one used in the last store.
    if (!ExitInstruction)
      ExitInstruction = cast<Instruction>(IntermediateStore->getValueOperand());
  }

  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
    return false;

  const bool IsOrdered =
      checkOrderedReduction(Kind, ExactFPMathInst, ExitInstruction, Phi);

  if (Start != Phi) {
    // If the starting value is not the same as the phi node, we speculatively
    // looked through an 'and' instruction when evaluating a potential
    // arithmetic reduction to determine if it may have been type-promoted.
    //
    // We now compute the minimal bit width that is required to represent the
    // reduction. If this is the same width that was indicated by the 'and', we
    // can represent the reduction in the smaller type. The 'and' instruction
    // will be eliminated since it will essentially be a cast instruction that
    // can be ignore in the cost model. If we compute a different type than we
    // did when evaluating the 'and', the 'and' will not be eliminated, and we
    // will end up with different kinds of operations in the recurrence
    // expression (e.g., IntegerAND, IntegerADD). We give up if this is
    // the case.
    //
    // The vectorizer relies on InstCombine to perform the actual
    // type-shrinking. It does this by inserting instructions to truncate the
    // exit value of the reduction to the width indicated by RecurrenceType and
    // then extend this value back to the original width. If IsSigned is false,
    // a 'zext' instruction will be generated; otherwise, a 'sext' will be
    // used.
    //
    // TODO: We should not rely on InstCombine to rewrite the reduction in the
    //       smaller type. We should just generate a correctly typed expression
    //       to begin with.
    Type *ComputedType;
    std::tie(ComputedType, IsSigned) =
        computeRecurrenceType(ExitInstruction, DB, AC, DT);
    if (ComputedType != RecurrenceType)
      return false;
  }

  // Collect cast instructions and the minimum width used by the recurrence.
  // If the starting value is not the same as the phi node and the computed
  // recurrence type is equal to the recurrence type, the recurrence expression
  // will be represented in a narrower or wider type. If there are any cast
  // instructions that will be unnecessary, collect them in CastsFromRecurTy.
  // Note that the 'and' instruction was already included in this list.
  //
  // TODO: A better way to represent this may be to tag in some way all the
  //       instructions that are a part of the reduction. The vectorizer cost
  //       model could then apply the recurrence type to these instructions,
  //       without needing a white list of instructions to ignore.
  //       This may also be useful for the inloop reductions, if it can be
  //       kept simple enough.
  collectCastInstrs(TheLoop, ExitInstruction, RecurrenceType, CastInsts,
                    MinWidthCastToRecurrenceType);

  // We found a reduction var if we have reached the original phi node and we
  // only have a single instruction with out-of-loop users.

  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
  // is saved as part of the RecurrenceDescriptor.

  // Save the description of this reduction variable.
  RedDes =
      RecurrenceDescriptor(RdxStart, ExitInstruction, IntermediateStore, Kind,
                           FMF, ExactFPMathInst, RecurrenceType, IsSigned,
                           IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
  return true;
}

// We are looking for loops that do something like this:
//   int r = 0;
//   for (int i = 0; i < n; i++) {
//     if (src[i] > 3)
//       r = 3;
//   }
// where the reduction value (r) only has two states, in this example 0 or 3.
// The generated LLVM IR for this type of loop will be like this:
//   for.body:
//     %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
//     ...
//     %cmp = icmp sgt i32 %5, 3
//     %spec.select = select i1 %cmp, i32 3, i32 %r
//     ...
// In general we can support vectorization of loops where 'r' flips between
// any two non-constants, provided they are loop invariant. The only thing
// we actually care about at the end of the loop is whether or not any lane
// in the selected vector is different from the start value. The final
// across-vector reduction after the loop simply involves choosing the start
// value if nothing changed (0 in the example above) or the other selected
// value (3 in the example above).
RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isAnyOfPattern(Loop *Loop, PHINode *OrigPhi,
                                     Instruction *I, InstDesc &Prev) {
  // We must handle the select(cmp(),x,y) as a single instruction. Advance to
  // the select.
  if (match(I, m_OneUse(m_Cmp()))) {
    if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
      return InstDesc(Select, Prev.getRecKind());
  }

  if (!match(I, m_Select(m_Cmp(), m_Value(), m_Value())))
    return InstDesc(false, I);

  SelectInst *SI = cast<SelectInst>(I);
  Value *NonPhi = nullptr;

  if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
    NonPhi = SI->getFalseValue();
  else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
    NonPhi = SI->getTrueValue();
  else
    return InstDesc(false, I);

  // We are looking for selects of the form:
  //   select(cmp(), phi, loop_invariant) or
  //   select(cmp(), loop_invariant, phi)
  if (!Loop->isLoopInvariant(NonPhi))
    return InstDesc(false, I);

  return InstDesc(I, RecurKind::AnyOf);
}

// We are looking for loops that do something like this:
//   int r = 0;
//   for (int i = 0; i < n; i++) {
//     if (src[i] > 3)
//       r = i;
//   }
// or like this:
//   int r = 0;
//   for (int i = 0; i < n; i++) {
//     if (src[i] > 3)
//       r = <loop-varying value>;
//   }
// The reduction value (r) is derived from either the values of an induction
// variable (i) sequence, an arbitrary loop-varying value, or from the start
// value (0). The LLVM IR generated for such loops would be as follows:
//   for.body:
//     %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
//     %i = phi i32 [ %inc, %for.body ], [ 0, %entry ]
//     ...
//     %cmp = icmp sgt i32 %5, 3
//     %spec.select = select i1 %cmp, i32 %i, i32 %r
//     %inc = add nsw i32 %i, 1
//     ...
//
// When searching for an arbitrary loop-varying value, the reduction value will
// either be the initial value (0) if the condition was never met, or the value
// of the loop-varying value in the most recent loop iteration where the
// condition was met.
RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isFindPattern(Loop *TheLoop, PHINode *OrigPhi,
                                    Instruction *I, ScalarEvolution &SE) {
  // TODO: Support the vectorization of FindLastIV when the reduction phi is
  // used by more than one select instruction. This vectorization is only
  // performed when the SCEV of each increasing induction variable used by the
  // select instructions is identical.
  if (!OrigPhi->hasOneUse())
    return InstDesc(false, I);

  // We are looking for selects of the form:
  //   select(cmp(), phi, value) or
  //   select(cmp(), value, phi)
  if (!match(I, m_CombineOr(m_Select(m_Cmp(), m_Value(), m_Specific(OrigPhi)),
                            m_Select(m_Cmp(), m_Specific(OrigPhi), m_Value()))))
    return InstDesc(false, I);

  return InstDesc(I, RecurKind::FindLast);
}

/// Returns true if the select instruction has users in the compare-and-add
/// reduction pattern below. The select instruction argument is the last one
/// in the sequence.
///
/// %sum.1 = phi ...
/// ...
/// %cmp = fcmp pred %0, %CFP
/// %add = fadd %0, %sum.1
/// %sum.2 = select %cmp, %add, %sum.1
RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isConditionalRdxPattern(Instruction *I) {
  Value *TrueVal, *FalseVal;
  // Only handle single use cases for now.
  if (!match(I,
             m_Select(m_OneUse(m_Cmp()), m_Value(TrueVal), m_Value(FalseVal))))
    return InstDesc(false, I);

  // Handle only when either of operands of select instruction is a PHI
  // node for now.
  if ((isa<PHINode>(TrueVal) && isa<PHINode>(FalseVal)) ||
      (!isa<PHINode>(TrueVal) && !isa<PHINode>(FalseVal)))
    return InstDesc(false, I);

  Instruction *I1 = isa<PHINode>(TrueVal) ? dyn_cast<Instruction>(FalseVal)
                                          : dyn_cast<Instruction>(TrueVal);
  if (!I1 || !I1->isBinaryOp())
    return InstDesc(false, I);

  Value *Op1, *Op2;
  if (!(((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
          m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
         I1->isFast()) ||
        (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast())) ||
        ((m_Add(m_Value(Op1), m_Value(Op2)).match(I1) ||
          m_Sub(m_Value(Op1), m_Value(Op2)).match(I1))) ||
        (m_Mul(m_Value(Op1), m_Value(Op2)).match(I1))))
    return InstDesc(false, I);

  Instruction *IPhi = isa<PHINode>(Op1) ? dyn_cast<Instruction>(Op1)
                                        : dyn_cast<Instruction>(Op2);
  if (!IPhi || IPhi != FalseVal)
    return InstDesc(false, I);

  return InstDesc(true, I);
}

RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
                                        Instruction *I, RecurKind Kind,
                                        InstDesc &Prev, ScalarEvolution *SE) {
  assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind);
  switch (I->getOpcode()) {
  default:
    return InstDesc(false, I);
  case Instruction::PHI:
    return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
  case Instruction::Sub:
    return InstDesc(
        Kind == RecurKind::Sub || Kind == RecurKind::AddChainWithSubs, I);
  case Instruction::Add:
    return InstDesc(
        Kind == RecurKind::Add || Kind == RecurKind::AddChainWithSubs, I);
  case Instruction::Mul:
    return InstDesc(Kind == RecurKind::Mul, I);
  case Instruction::And:
    return InstDesc(Kind == RecurKind::And, I);
  case Instruction::Or:
    return InstDesc(Kind == RecurKind::Or, I);
  case Instruction::Xor:
    return InstDesc(Kind == RecurKind::Xor, I);
  case Instruction::FDiv:
  case Instruction::FMul:
    return InstDesc(Kind == RecurKind::FMul, I,
                    I->hasAllowReassoc() ? nullptr : I);
  case Instruction::FSub:
    return InstDesc(Kind == RecurKind::FSub ||
                        Kind == RecurKind::FAddChainWithSubs,
                    I, I->hasAllowReassoc() ? nullptr : I);
  case Instruction::FAdd:
    return InstDesc(Kind == RecurKind::FAdd ||
                        Kind == RecurKind::FAddChainWithSubs,
                    I, I->hasAllowReassoc() ? nullptr : I);
  case Instruction::Select:
    if (isSubRecurrenceKind(Kind) || Kind == RecurKind::FAdd ||
        Kind == RecurKind::FMul || Kind == RecurKind::Add ||
        Kind == RecurKind::Mul || Kind == RecurKind::AddChainWithSubs ||
        Kind == RecurKind::FAddChainWithSubs)
      return isConditionalRdxPattern(I);
    if (isFindRecurrenceKind(Kind) && SE)
      return isFindPattern(L, OrigPhi, I, *SE);
    [[fallthrough]];
  case Instruction::FCmp:
  case Instruction::ICmp:
  case Instruction::Call:
    if (isAnyOfRecurrenceKind(Kind))
      return isAnyOfPattern(L, OrigPhi, I, Prev);
    if (isFMulAddIntrinsic(I))
      return InstDesc(Kind == RecurKind::FMulAdd, I,
                      I->hasAllowReassoc() ? nullptr : I);
    return InstDesc(false, I);
  }
}

bool RecurrenceDescriptor::hasMultipleUsesOf(
    Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
    unsigned MaxNumUses) {
  unsigned NumUses = 0;
  for (const Use &U : I->operands()) {
    if (Insts.count(dyn_cast<Instruction>(U)))
      ++NumUses;
    if (NumUses > MaxNumUses)
      return true;
  }

  return false;
}

bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
                                          RecurrenceDescriptor &RedDes,
                                          DemandedBits *DB, AssumptionCache *AC,
                                          DominatorTree *DT,
                                          ScalarEvolution *SE) {
  if (AddReductionVar(Phi, RecurKind::Add, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Sub, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a SUB reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::AddChainWithSubs, TheLoop, RedDes, DB, AC,
                      DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a chained ADD-SUB reduction PHI." << *Phi
                      << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Or, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::And, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
    return true;
  }
  auto RD = getMinMaxRecurrence(Phi, TheLoop, SE);
  if (RD.getRecurrenceKind() != RecurKind::None) {
    assert(
        RecurrenceDescriptor::isMinMaxRecurrenceKind(RD.getRecurrenceKind()) &&
        "Expected a min/max recurrence kind");
    LLVM_DEBUG(dbgs() << "Found a min/max reduction PHI." << *Phi << "\n");
    RedDes = std::move(RD);
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::AnyOf, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a conditional select reduction PHI." << *Phi
                      << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FindLast, TheLoop, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a Find reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FSub, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found an FSub reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, RedDes, DB, AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FAddChainWithSubs, TheLoop, RedDes, DB,
                      AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a chained FADD-FSUB chained reduction PHI."
                      << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");
    return true;
  }

  // Not a reduction of known type.
  return false;
}

bool RecurrenceDescriptor::isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                                                  DominatorTree *DT) {

  // Ensure the phi node is in the loop header and has two incoming values.
  if (Phi->getParent() != TheLoop->getHeader() ||
      Phi->getNumIncomingValues() != 2)
    return false;

  // Ensure the loop has a preheader and a single latch block. The loop
  // vectorizer will need the latch to set up the next iteration of the loop.
  auto *Preheader = TheLoop->getLoopPreheader();
  auto *Latch = TheLoop->getLoopLatch();
  if (!Preheader || !Latch)
    return false;

  // Ensure the phi node's incoming blocks are the loop preheader and latch.
  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
      Phi->getBasicBlockIndex(Latch) < 0)
    return false;

  // Get the previous value. The previous value comes from the latch edge while
  // the initial value comes from the preheader edge.
  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));

  // If Previous is a phi in the header, go through incoming values from the
  // latch until we find a non-phi value. Use this as the new Previous, all uses
  // in the header will be dominated by the original phi, but need to be moved
  // after the non-phi previous value.
  SmallPtrSet<PHINode *, 4> SeenPhis;
  while (auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
    if (PrevPhi->getParent() != Phi->getParent())
      return false;
    if (!SeenPhis.insert(PrevPhi).second)
      return false;
    Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
  }

  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous))
    return false;

  // Ensure every user of the phi node (recursively) is dominated by the
  // previous value. The dominance requirement ensures the loop vectorizer will
  // not need to vectorize the initial value prior to the first iteration of the
  // loop.
  // TODO: Consider extending this sinking to handle memory instructions.

  SmallPtrSet<Value *, 8> Seen;
  BasicBlock *PhiBB = Phi->getParent();
  SmallVector<Instruction *, 8> WorkList;
  auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {
    // Cyclic dependence.
    if (Previous == SinkCandidate)
      return false;

    if (!Seen.insert(SinkCandidate).second)
      return true;
    if (DT->dominates(Previous,
                      SinkCandidate)) // We already are good w/o sinking.
      return true;

    if (SinkCandidate->getParent() != PhiBB ||
        SinkCandidate->mayHaveSideEffects() ||
        SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
      return false;

    // If we reach a PHI node that is not dominated by Previous, we reached a
    // header PHI. No need for sinking.
    if (isa<PHINode>(SinkCandidate))
      return true;

    // Sink User tentatively and check its users
    WorkList.push_back(SinkCandidate);
    return true;
  };

  WorkList.push_back(Phi);
  // Try to recursively sink instructions and their users after Previous.
  while (!WorkList.empty()) {
    Instruction *Current = WorkList.pop_back_val();
    for (User *User : Current->users()) {
      if (!TryToPushSinkCandidate(cast<Instruction>(User)))
        return false;
    }
  }

  return true;
}

unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
  switch (Kind) {
  case RecurKind::Sub:
    return Instruction::Sub;
  case RecurKind::AddChainWithSubs:
  case RecurKind::Add:
    return Instruction::Add;
  case RecurKind::Mul:
    return Instruction::Mul;
  case RecurKind::Or:
    return Instruction::Or;
  case RecurKind::And:
    return Instruction::And;
  case RecurKind::Xor:
    return Instruction::Xor;
  case RecurKind::FMul:
    return Instruction::FMul;
  case RecurKind::FMulAdd:
  case RecurKind::FAddChainWithSubs:
  case RecurKind::FAdd:
    return Instruction::FAdd;
  case RecurKind::FSub:
    return Instruction::FSub;
  case RecurKind::SMax:
  case RecurKind::SMin:
  case RecurKind::UMax:
  case RecurKind::UMin:
    return Instruction::ICmp;
  case RecurKind::FMax:
  case RecurKind::FMin:
  case RecurKind::FMaximum:
  case RecurKind::FMinimum:
  case RecurKind::FMaximumNum:
  case RecurKind::FMinimumNum:
    return Instruction::FCmp;
  case RecurKind::FindLast:
  case RecurKind::AnyOf:
  case RecurKind::FindIV:
    // TODO: Set AnyOf and FindIV to Instruction::Select once in-loop reductions
    // are supported.
  default:
    llvm_unreachable("Unknown recurrence operation");
  }
}

SmallVector<Instruction *, 4>
RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
  SmallVector<Instruction *, 4> ReductionOperations;
  const bool IsMinMax = isMinMaxRecurrenceKind(Kind);

  // Search down from the Phi to the LoopExitInstr, looking for instructions
  // with a single user of the correct type for the reduction.

  // Note that we check that the type of the operand is correct for each item in
  // the chain, including the last (the loop exit value). This can come up from
  // sub, which would otherwise be treated as an add reduction. MinMax also need
  // to check for a pair of icmp/select, for which we use getNextInstruction and
  // isCorrectOpcode functions to step the right number of instruction, and
  // check the icmp/select pair.
  // FIXME: We also do not attempt to look through Select's yet, which might
  // be part of the reduction chain, or attempt to looks through And's to find a
  // smaller bitwidth. Subs are also currently not allowed (which are usually
  // treated as part of a add reduction) as they are expected to generally be
  // more expensive than out-of-loop reductions, and need to be costed more
  // carefully.
  unsigned ExpectedUses = 1;
  if (IsMinMax)
    ExpectedUses = 2;

  auto getNextInstruction = [&](Instruction *Cur) -> Instruction * {
    for (auto *User : Cur->users()) {
      Instruction *UI = cast<Instruction>(User);
      if (isa<PHINode>(UI))
        continue;
      if (IsMinMax) {
        // We are expecting a icmp/select pair, which we go to the next select
        // instruction if we can. We already know that Cur has 2 uses.
        if (isa<SelectInst>(UI))
          return UI;
        continue;
      }
      return UI;
    }
    return nullptr;
  };
  auto isCorrectOpcode = [&](Instruction *Cur) {
    if (IsMinMax) {
      Value *LHS, *RHS;
      return SelectPatternResult::isMinOrMax(
          matchSelectPattern(Cur, LHS, RHS).Flavor);
    }
    // Recognize a call to the llvm.fmuladd intrinsic.
    if (isFMulAddIntrinsic(Cur))
      return true;

    if (Cur->getOpcode() == Instruction::Sub &&
        Kind == RecurKind::AddChainWithSubs)
      return true;

    if (Cur->getOpcode() == Instruction::FSub &&
        Kind == RecurKind::FAddChainWithSubs)
      return true;

    return Cur->getOpcode() == getOpcode();
  };

  // Attempt to look through Phis which are part of the reduction chain
  unsigned ExtraPhiUses = 0;
  Instruction *RdxInstr = LoopExitInstr;
  if (auto ExitPhi = dyn_cast<PHINode>(LoopExitInstr)) {
    if (ExitPhi->getNumIncomingValues() != 2)
      return {};

    Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
    Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));

    Instruction *Chain = nullptr;
    if (Inc0 == Phi)
      Chain = Inc1;
    else if (Inc1 == Phi)
      Chain = Inc0;
    else
      return {};

    RdxInstr = Chain;
    ExtraPhiUses = 1;
  }

  // The loop exit instruction we check first (as a quick test) but add last. We
  // check the opcode is correct (and dont allow them to be Subs) and that they
  // have expected to have the expected number of uses. They will have one use
  // from the phi and one from a LCSSA value, no matter the type.
  if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(2))
    return {};

  // Check that the Phi has one (or two for min/max) uses, plus an extra use
  // for conditional reductions.
  if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))
    return {};

  Instruction *Cur = getNextInstruction(Phi);

  // Each other instruction in the chain should have the expected number of uses
  // and be the correct opcode.
  while (Cur != RdxInstr) {
    if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))
      return {};

    ReductionOperations.push_back(Cur);
    Cur = getNextInstruction(Cur);
  }

  ReductionOperations.push_back(Cur);
  return ReductionOperations;
}

InductionDescriptor::InductionDescriptor(
    Value *Start, InductionKind K, const SCEV *Step, BinaryOperator *BOp,
    SmallVectorImpl<Instruction *> *Casts,
    ArrayRef<const SCEVPredicate *> NoWrapPreds)
    : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
  assert(IK != IK_NoInduction && "Not an induction");

  // Start value type should match the induction kind and the value
  // itself should not be null.
  assert(StartValue && "StartValue is null");
  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
         "StartValue is not a pointer for pointer induction");
  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
         "StartValue is not an integer for integer induction");

  // Check the Step Value. It should be non-zero integer value.
  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
         "Step value is zero");

  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
         "StepValue is not an integer");

  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
         "StepValue is not FP for FpInduction");
  assert((IK != IK_FpInduction ||
          (InductionBinOp &&
           (InductionBinOp->getOpcode() == Instruction::FAdd ||
            InductionBinOp->getOpcode() == Instruction::FSub))) &&
         "Binary opcode should be specified for FP induction");

  if (Casts)
    llvm::append_range(RedundantCasts, *Casts);
  llvm::append_range(NoWrapPredicates, NoWrapPreds);
}

InductionDescriptor
InductionDescriptor::getCanonicalIntInduction(Type *Ty, ScalarEvolution &SE) {
  return InductionDescriptor(Constant::getNullValue(Ty), IK_IntInduction,
                             SE.getOne(Ty));
}

ConstantInt *InductionDescriptor::getConstIntStepValue() const {
  if (auto *ConstStep = dyn_cast<SCEVConstant>(Step))
    return ConstStep->getValue();
  return nullptr;
}

bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                           ScalarEvolution *SE,
                                           InductionDescriptor &D) {

  // Here we only handle FP induction variables.
  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");

  if (TheLoop->getHeader() != Phi->getParent())
    return false;

  // The loop may have multiple entrances or multiple exits; we can analyze
  // this phi if it has a unique entry value and a unique backedge value.
  if (Phi->getNumIncomingValues() != 2)
    return false;
  Value *BEValue = nullptr, *StartValue = nullptr;
  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
    BEValue = Phi->getIncomingValue(0);
    StartValue = Phi->getIncomingValue(1);
  } else {
    assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
           "Unexpected Phi node in the loop");
    BEValue = Phi->getIncomingValue(1);
    StartValue = Phi->getIncomingValue(0);
  }

  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
  if (!BOp)
    return false;

  Value *Addend = nullptr;
  if (BOp->getOpcode() == Instruction::FAdd) {
    if (BOp->getOperand(0) == Phi)
      Addend = BOp->getOperand(1);
    else if (BOp->getOperand(1) == Phi)
      Addend = BOp->getOperand(0);
  } else if (BOp->getOpcode() == Instruction::FSub)
    if (BOp->getOperand(0) == Phi)
      Addend = BOp->getOperand(1);

  if (!Addend)
    return false;

  // The addend should be loop invariant
  if (auto *I = dyn_cast<Instruction>(Addend))
    if (TheLoop->contains(I))
      return false;

  // FP Step has unknown SCEV
  const SCEV *Step = SE->getUnknown(Addend);
  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
  return true;
}

/// This function is called when we suspect that the update-chain of a phi node
/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
/// predicate P under which the SCEV expression for the phi can be the
/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
/// cast instructions that are involved in the update-chain of this induction.
/// A caller that adds the required runtime predicate can be free to drop these
/// cast instructions, and compute the phi using \p AR (instead of some scev
/// expression with casts).
///
/// For example, without a predicate the scev expression can take the following
/// form:
///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
///
/// It corresponds to the following IR sequence:
/// %for.body:
///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
///   %casted_phi = "ExtTrunc i64 %x"
///   %add = add i64 %casted_phi, %step
///
/// where %x is given in \p PN,
/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
/// several forms, for example, such as:
///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
/// or:
///   ExtTrunc2:    %t = shl %x, m
///                 %casted_phi = ashr %t, m
///
/// If we are able to find such sequence, we return the instructions
/// we found, namely %casted_phi and the instructions on its use-def chain up
/// to the phi (not including the phi).
static bool
getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
                        const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR,
                        SmallVectorImpl<Instruction *> &CastInsts,
                        ArrayRef<const SCEVPredicate *> NoWrapPreds) {

  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
  auto *PN = cast<PHINode>(PhiScev->getValue());

  // Build a predicate to rewrite SCEVs of values in the cast chain using the
  // predicates needed for this induction.
  ScalarEvolution &SE = *PSE.getSE();
  SCEVUnionPredicate NoWrapUnionPred(NoWrapPreds, SE);
  const Loop *L = AR->getLoop();
  assert(SE.rewriteUsingPredicate(SE.getSCEV(PN), L, NoWrapUnionPred) == AR &&
         "Unexpected phi node SCEV expression");

  // Find any cast instructions that participate in the def-use chain of
  // PhiScev in the loop.
  // FORNOW/TODO: We currently expect the def-use chain to include only
  // two-operand instructions, where one of the operands is an invariant.
  // createAddRecFromPHIWithCasts() currently does not support anything more
  // involved than that, so we keep the search simple. This can be
  // extended/generalized as needed.

  auto getDef = [&](const Value *Val) -> Value * {
    const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
    if (!BinOp)
      return nullptr;
    Value *Op0 = BinOp->getOperand(0);
    Value *Op1 = BinOp->getOperand(1);
    Value *Def = nullptr;
    if (L->isLoopInvariant(Op0))
      Def = Op1;
    else if (L->isLoopInvariant(Op1))
      Def = Op0;
    return Def;
  };

  // Look for the instruction that defines the induction via the
  // loop backedge.
  BasicBlock *Latch = L->getLoopLatch();
  if (!Latch)
    return false;
  Value *Val = PN->getIncomingValueForBlock(Latch);
  if (!Val)
    return false;

  // Follow the def-use chain until the induction phi is reached.
  // If on the way we encounter a Value that has the same SCEV Expr as the
  // phi node, we can consider the instructions we visit from that point
  // as part of the cast-sequence that can be ignored.
  bool InCastSequence = false;
  auto *Inst = dyn_cast<Instruction>(Val);
  while (Val != PN) {
    // If we encountered a phi node other than PN, or if we left the loop,
    // we bail out.
    if (!Inst || !L->contains(Inst)) {
      return false;
    }
    // Create AddRec with NoWrapPredicates applied.
    auto *AddRec = dyn_cast<SCEVAddRecExpr>(
        SE.rewriteUsingPredicate(SE.getSCEV(Val), L, NoWrapUnionPred));
    if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR, NoWrapPreds))
      InCastSequence = true;
    if (InCastSequence) {
      // Only the last instruction in the cast sequence is expected to have
      // uses outside the induction def-use chain.
      if (!CastInsts.empty())
        if (!Inst->hasOneUse())
          return false;
      CastInsts.push_back(Inst);
    }
    Val = getDef(Val);
    if (!Val)
      return false;
    Inst = dyn_cast<Instruction>(Val);
  }

  return InCastSequence;
}

bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                         PredicatedScalarEvolution &PSE,
                                         InductionDescriptor &D, bool Assume) {
  Type *PhiTy = Phi->getType();

  // Handle integer and pointer inductions variables.
  // Now we handle also FP induction but not trying to make a
  // recurrent expression from the PHI node in-place.

  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
      !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
    return false;

  if (PhiTy->isFloatingPointTy())
    return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);

  const SCEV *PhiScev = PSE.getSCEV(Phi);
  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);

  // Collect predicates needed to force the SCEV into an AddRecExpr.
  SmallVector<const SCEVPredicate *, 2> Preds;

  // We need this expression to be an AddRecExpr.
  if (Assume && !AR)
    AR = PSE.getAsAddRec(Phi, &Preds);

  if (!AR) {
    LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
    return false;
  }

  // Record any Cast instructions that participate in the induction update
  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
  // If we started from an UnknownSCEV, and managed to build an addRecurrence
  // only after enabling Assume with PSCEV, this means we may have encountered
  // cast instructions that required adding a runtime check in order to
  // guarantee the correctness of the AddRecurrence respresentation of the
  // induction.
  if (PhiScev != AR && SymbolicPhi) {
    SmallVector<Instruction *, 2> Casts;
    if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts, Preds))
      return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, Preds, AR, &Casts);
  }

  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, Preds, AR);
}

bool InductionDescriptor::isInductionPHI(
    PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
    InductionDescriptor &D, ArrayRef<const SCEVPredicate *> Preds,
    const SCEV *Expr, SmallVectorImpl<Instruction *> *CastsToIgnore) {
  Type *PhiTy = Phi->getType();
  // isSCEVable returns true for integer and pointer types.
  if (!SE->isSCEVable(PhiTy))
    return false;

  // Check that the PHI is consecutive.
  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
  const SCEV *Step;

  // FIXME: We are currently matching the specific loop TheLoop; if it doesn't
  // match, we should treat it as a uniform. Unfortunately, we don't currently
  // know how to handled uniform PHIs.
  if (!match(PhiScev, m_scev_AffineAddRec(m_SCEV(), m_SCEV(Step),
                                          m_SpecificLoop(TheLoop)))) {
    LLVM_DEBUG(
        dbgs() << "LV: PHI is not a poly recurrence for requested loop.\n");
    return false;
  }

  // This function assumes that InductionPhi is called only on Phi nodes
  // present inside loop headers. Check for the same, and throw an assert if
  // the current Phi is not present inside the loop header.
  assert(Phi->getParent() == TheLoop->getHeader() &&
         "Invalid Phi node, not present in loop header");

  if (!TheLoop->getLoopPreheader())
    return false;

  Value *StartValue =
      Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());

  BasicBlock *Latch = TheLoop->getLoopLatch();
  if (!Latch)
    return false;

  if (PhiTy->isIntegerTy()) {
    BinaryOperator *BOp =
        dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
    D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
                            CastsToIgnore, Preds);
    return true;
  }

  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");

  // This allows induction variables w/non-constant steps.
  D = InductionDescriptor(StartValue, IK_PtrInduction, Step,
                          /*InductionBinOp=*/nullptr, /*Casts=*/nullptr, Preds);
  return true;
}

// Recognize a conditional induction PHI by matching the following pattern:
// loop_header:
//   %conditional_iv = phi [ %start, %preheader ], [ %latch_phi, %latch ]
//   br i1 %do_step, label %step_bb, label %latch
//
// step_bb:
//   %step = add/gep %conditional_iv, %step_val
//   br label %latch
//
// latch:
//   %latch_phi = phi [ %conditional_iv, %loop_header ], [ %step, %step_bb ]
//   br label %loop_header
bool ConditionalInductionDescriptor::isConditionalInductionPHI(
    PHINode *PN, const Loop *L, ConditionalInductionDescriptor &Desc,
    ScalarEvolution &SE) {
  BasicBlock *Preheader = L->getLoopPreheader();
  if (!Preheader)
    return false;

  BasicBlock *Latch = L->getLoopLatch();
  if (!Latch || !PN->getType()->isIntOrPtrTy() ||
      PN->getParent() != L->getHeader())
    return false;

  auto *BackedgePHI = dyn_cast<PHINode>(PN->getIncomingValueForBlock(Latch));
  if (!BackedgePHI)
    return false;

  // Ensure the only users of the backedge PHI are outside the loop or the
  // header PHI (PN).
  for (User *U : BackedgePHI->users()) {
    auto *UI = cast<Instruction>(U);
    if (UI != PN && L->contains(UI))
      return false;
  }

  // Find the step operation used to increment the conditional induction PHI.
  // TODO: Support chains of PHIs.
  Value *StepOp =
      find_singleton<Value>(BackedgePHI->incoming_values(),
                            [&](Use &Incoming, bool /*AllowRepeats*/) {
                              return Incoming != PN ? Incoming.get() : nullptr;
                            });
  if (!StepOp || !StepOp->hasOneUse())
    return false;

  auto *StepInst = dyn_cast<Instruction>(StepOp);
  if (!StepInst)
    return false;

  Value *Step = nullptr;
  bool StepMatch =
      PN->getType()->isPointerTy()
          ? match(StepInst, m_PtrAdd(m_Specific(PN), m_Value(Step)))
          : match(StepInst, m_c_Add(m_Specific(PN), m_Value(Step)));
  if (!StepMatch || !L->isLoopInvariant(Step))
    return false;

  // Ensure GEP offsets are extended to the size of the PHI.
  const SCEV *StepSCEV = SE.getTruncateOrSignExtend(
      SE.getSCEV(Step), SE.getEffectiveSCEVType(PN->getType()));

  if (StepSCEV->isZero())
    return false;

  Value *Start = PN->getIncomingValueForBlock(Preheader);
  const SCEV *StartSCEV = SE.getSCEV(Start);

  SCEVFlags NoWrapFlags = SCEV::FlagNone;
  if (auto *GEP = dyn_cast<GEPOperator>(StepInst)) {
    // With NUSW, we can add NUW if the step is non-negative. We can't add NSW
    // as the base address is unsigned.
    if (GEP->hasNoUnsignedWrap() ||
        (GEP->hasNoUnsignedSignedWrap() && SE.isKnownNonNegative(StepSCEV)))
      NoWrapFlags = ScalarEvolution::setFlags(NoWrapFlags, SCEV::FlagNUW);
  } else if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(StepInst)) {
    if (OBO->hasNoUnsignedWrap())
      NoWrapFlags = ScalarEvolution::setFlags(NoWrapFlags, SCEV::FlagNUW);
    if (OBO->hasNoSignedWrap())
      NoWrapFlags = ScalarEvolution::setFlags(NoWrapFlags, SCEV::FlagNSW);
  }

  LLVM_DEBUG(dbgs() << "LV: Found a conditional induction phi: HeaderPHI: "
                    << *PN << ", StepInst: " << *StepInst << "\n");

  Desc = ConditionalInductionDescriptor(PN, BackedgePHI, StepInst, StartSCEV,
                                        StepSCEV, NoWrapFlags);
  return true;
}