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/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;

#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::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::FindFirstIVSMin:
  case RecurKind::FindFirstIVUMin:
  case RecurKind::FindLastIVSMax:
  case RecurKind::FindLastIVUMax:
    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;
}

/// 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;
}

bool RecurrenceDescriptor::AddReductionVar(
    PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF,
    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.
  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 min/max patterns formed by a icmp select sequence, we store
  // the number of instruction we saw from the recognized min/max pattern,
  //  to make sure we only see exactly the two instructions.
  unsigned NumCmpSelectPatternInst = 0;
  InstDesc ReduxDesc(false, nullptr);

  // 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.
  if (RecurrenceType->isFloatingPointTy()) {
    if (!isFloatingPointRecurrenceKind(Kind))
      return false;
  } else if (RecurrenceType->isIntegerTy()) {
    if (!isIntegerRecurrenceKind(Kind))
      return false;
    if (!isMinMaxRecurrenceKind(Kind))
      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);

    // 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, FuncFMF, 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) {
        FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
        if (auto *Sel = dyn_cast<SelectInst>(ReduxDesc.getPatternInst())) {
          // Accept FMF on either fcmp or select of a min/max idiom.
          // TODO: This is a hack to work-around the fact that FMF may not be
          //       assigned/propagated correctly. If that problem is fixed or we
          //       standardize on fmin/fmax via intrinsics, this can be removed.
          if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
            CurFMF |= FCmp->getFastMathFlags();
        }
        FMF &= CurFMF;
      }
      // 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 && !isMinMaxRecurrenceKind(Kind) &&
        !isAnyOfRecurrenceKind(Kind) && hasMultipleUsesOf(Cur, VisitedInsts, 1))
      return false;

    // All inputs to a PHI node must be a reduction value.
    if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
      return false;

    if (isIntMinMaxRecurrenceKind(Kind) && (isa<ICmpInst>(Cur) || IsASelect))
      ++NumCmpSelectPatternInst;
    if (isFPMinMaxRecurrenceKind(Kind) && (isa<FCmpInst>(Cur) || IsASelect))
      ++NumCmpSelectPatternInst;
    if (isAnyOfRecurrenceKind(Kind) && IsASelect)
      ++NumCmpSelectPatternInst;

    // Check  whether we found a reduction operator.
    FoundReduxOp |= !IsAPhi && 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 min/max
      // 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) &&
                 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                   !isa<SelectInst>(UI)) ||
                  (!isConditionalRdxPattern(UI).isRecurrence() &&
                   !isAnyOfPattern(TheLoop, Phi, UI, IgnoredVal)
                        .isRecurrence() &&
                   !isMinMaxPattern(UI, Kind, 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());
  }

  // This means we have seen one but not the other instruction of the
  // pattern or more than just a select and cmp. Zero implies that we saw a
  // llvm.min/max intrinsic, which is always OK.
  if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
      NumCmpSelectPatternInst != 0)
    return false;

  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.
  RecurrenceDescriptor RD(RdxStart, ExitInstruction, IntermediateStore, Kind,
                          FMF, ExactFPMathInst, RecurrenceType, IsSigned,
                          IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
  RedDes = RD;

  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;
//   }
// The reduction value (r) is derived from either the values of an induction
// variable (i) sequence, 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
//     ...
// Since 'i' is an induction variable, the reduction value after the loop will
// be the maximum (increasing induction) or minimum (decreasing induction) value
// of 'i' that the condition (src[i] > 3) is satisfied, or the start value (0 in
// the example above). When the start value of the induction variable 'i' is
// greater than the minimum (increasing induction) or maximum (decreasing
// induction) value of the data type, we can use the minimum (increasing
// induction) or maximum (decreasing induction) value of the data type as a
// sentinel value to replace the start value. This allows us to perform a single
// reduction max (increasing induction) or min (decreasing induction) operation
// to obtain the final reduction result.
// TODO: It is possible to solve the case where the start value is the minimum
// value of the data type or a non-constant value by using mask and multiple
// reduction operations.
RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isFindIVPattern(RecurKind Kind, 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, loop_induction) or
  //   select(cmp(), loop_induction, phi)
  // TODO: Match selects with multi-use cmp conditions.
  Value *NonRdxPhi = nullptr;
  if (!match(I, m_CombineOr(m_Select(m_OneUse(m_Cmp()), m_Value(NonRdxPhi),
                                     m_Specific(OrigPhi)),
                            m_Select(m_OneUse(m_Cmp()), m_Specific(OrigPhi),
                                     m_Value(NonRdxPhi)))))
    return InstDesc(false, I);

  // Returns either FindFirstIV/FindLastIV, if such a pattern is found, or
  // std::nullopt.
  auto GetRecurKind = [&](Value *V) -> std::optional<RecurKind> {
    Type *Ty = V->getType();
    if (!SE.isSCEVable(Ty))
      return std::nullopt;

    auto *AR = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(V));
    if (!AR || AR->getLoop() != TheLoop)
      return std::nullopt;

    const SCEV *Step = AR->getStepRecurrence(SE);
    if ((isFindFirstIVRecurrenceKind(Kind) && !SE.isKnownNegative(Step)) ||
        (isFindLastIVRecurrenceKind(Kind) && !SE.isKnownPositive(Step)))
      return std::nullopt;

    // Check if the minimum (FindLast) or maximum (FindFirst) value of the
    // recurrence type can be used as a sentinel value. The maximum acceptable
    // range for the induction variable, called the valid range will exclude
    // <sentinel value>, where <sentinel value> is
    // [Signed|Unsigned]Min(<recurrence type>) for FindLastIV or
    // [Signed|Unsigned]Max(<recurrence type>) for FindFirstIV.
    // TODO: This range restriction can be lifted by adding an additional
    // virtual OR reduction.
    auto CheckRange = [&](bool IsSigned) {
      const ConstantRange IVRange =
          IsSigned ? SE.getSignedRange(AR) : SE.getUnsignedRange(AR);
      unsigned NumBits = Ty->getIntegerBitWidth();
      ConstantRange ValidRange = ConstantRange::getEmpty(NumBits);
      if (isFindLastIVRecurrenceKind(Kind)) {
        APInt Sentinel = IsSigned ? APInt::getSignedMinValue(NumBits)
                                  : APInt::getMinValue(NumBits);
        ValidRange = ConstantRange::getNonEmpty(Sentinel + 1, Sentinel);
      } else {
        if (IsSigned)
          ValidRange =
              ConstantRange::getNonEmpty(APInt::getSignedMinValue(NumBits),
                                         APInt::getSignedMaxValue(NumBits) - 1);
        else
          ValidRange = ConstantRange::getNonEmpty(
              APInt::getMinValue(NumBits), APInt::getMaxValue(NumBits) - 1);
      }

      LLVM_DEBUG(dbgs() << "LV: "
                        << (isFindLastIVRecurrenceKind(Kind) ? "FindLastIV"
                                                             : "FindFirstIV")
                        << " valid range is " << ValidRange
                        << ", and the range of " << *AR << " is " << IVRange
                        << "\n");

      // Ensure the induction variable does not wrap around by verifying that
      // its range is fully contained within the valid range.
      return ValidRange.contains(IVRange);
    };
    if (isFindLastIVRecurrenceKind(Kind)) {
      if (CheckRange(true))
        return RecurKind::FindLastIVSMax;
      if (CheckRange(false))
        return RecurKind::FindLastIVUMax;
      return std::nullopt;
    }
    assert(isFindFirstIVRecurrenceKind(Kind) &&
           "Kind must either be a FindLastIV or FindFirstIV");

    if (CheckRange(true))
      return RecurKind::FindFirstIVSMin;
    if (CheckRange(false))
      return RecurKind::FindFirstIVUMin;
    return std::nullopt;
  };

  if (auto RK = GetRecurKind(NonRdxPhi))
    return InstDesc(I, *RK);

  return InstDesc(false, I);
}

RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
                                      const InstDesc &Prev) {
  assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&
         "Expected a cmp or select or call instruction");
  if (!isMinMaxRecurrenceKind(Kind))
    return InstDesc(false, I);

  // We must handle the select(cmp()) 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());
  }

  // Only match select with single use cmp condition, or a min/max intrinsic.
  if (!isa<IntrinsicInst>(I) &&
      !match(I, m_Select(m_OneUse(m_Cmp()), m_Value(), m_Value())))
    return InstDesc(false, I);

  // Look for a min/max pattern.
  if (match(I, m_UMin(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::UMin, I);
  if (match(I, m_UMax(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::UMax, I);
  if (match(I, m_SMax(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::SMax, I);
  if (match(I, m_SMin(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::SMin, I);
  if (match(I, m_OrdOrUnordFMin(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMin, I);
  if (match(I, m_OrdOrUnordFMax(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMax, I);
  if (match(I, m_FMinNum(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMin, I);
  if (match(I, m_FMaxNum(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMax, I);
  if (match(I, m_FMinimumNum(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMinimumNum, I);
  if (match(I, m_FMaximumNum(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMaximumNum, I);
  if (match(I, m_FMinimum(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMinimum, I);
  if (match(I, m_FMaximum(m_Value(), m_Value())))
    return InstDesc(Kind == RecurKind::FMaximum, I);

  return InstDesc(false, I);
}

/// 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) {
  SelectInst *SI = dyn_cast<SelectInst>(I);
  if (!SI)
    return InstDesc(false, I);

  CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
  // Only handle single use cases for now.
  if (!CI || !CI->hasOneUse())
    return InstDesc(false, I);

  Value *TrueVal = SI->getTrueValue();
  Value *FalseVal = SI->getFalseValue();
  // 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, SI);
}

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isRecurrenceInstr(
    Loop *L, PHINode *OrigPhi, Instruction *I, RecurKind Kind, InstDesc &Prev,
    FastMathFlags FuncFMF, 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:
  case Instruction::Add:
    return InstDesc(Kind == RecurKind::Add, 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:
  case Instruction::FAdd:
    return InstDesc(Kind == RecurKind::FAdd, I,
                    I->hasAllowReassoc() ? nullptr : I);
  case Instruction::Select:
    if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul ||
        Kind == RecurKind::Add || Kind == RecurKind::Mul)
      return isConditionalRdxPattern(I);
    if (isFindIVRecurrenceKind(Kind) && SE)
      return isFindIVPattern(Kind, L, OrigPhi, I, *SE);
    [[fallthrough]];
  case Instruction::FCmp:
  case Instruction::ICmp:
  case Instruction::Call:
    if (isAnyOfRecurrenceKind(Kind))
      return isAnyOfPattern(L, OrigPhi, I, Prev);
    auto HasRequiredFMF = [&]() {
     if (FuncFMF.noNaNs() && FuncFMF.noSignedZeros())
       return true;
     if (isa<FPMathOperator>(I) && I->hasNoNaNs() && I->hasNoSignedZeros())
       return true;
     // minimum/minnum and maximum/maxnum intrinsics do not require nsz and nnan
     // flags since NaN and signed zeroes are propagated in the intrinsic
     // implementation.
     return match(I, m_Intrinsic<Intrinsic::minimum>(m_Value(), m_Value())) ||
            match(I, m_Intrinsic<Intrinsic::maximum>(m_Value(), m_Value())) ||
            match(I,
                  m_Intrinsic<Intrinsic::minimumnum>(m_Value(), m_Value())) ||
            match(I, m_Intrinsic<Intrinsic::maximumnum>(m_Value(), m_Value()));
    };
    if (isIntMinMaxRecurrenceKind(Kind))
      return isMinMaxPattern(I, Kind, Prev);
    if (isFPMinMaxRecurrenceKind(Kind)) {
      InstDesc Res = isMinMaxPattern(I, Kind, Prev);
      if (!Res.isRecurrence())
        return InstDesc(false, I);
      if (HasRequiredFMF())
        return Res;
      // We may be able to vectorize FMax/FMin reductions using maxnum/minnum
      // intrinsics with extra checks ensuring the vector loop handles only
      // non-NaN inputs.
      if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value()))) {
        assert(Kind == RecurKind::FMax &&
               "unexpected recurrence kind for maxnum");
        return InstDesc(I, RecurKind::FMaxNum);
      }
      if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value()))) {
        assert(Kind == RecurKind::FMin &&
               "unexpected recurrence kind for minnum");
        return InstDesc(I, RecurKind::FMinNum);
      }
      return InstDesc(false, I);
    }
    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) {
  BasicBlock *Header = TheLoop->getHeader();
  Function &F = *Header->getParent();
  FastMathFlags FMF;
  FMF.setNoNaNs(
      F.getFnAttribute("no-nans-fp-math").getValueAsBool());
  FMF.setNoSignedZeros(
      F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());

  if (AddReductionVar(Phi, RecurKind::Add, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Or, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::And, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::AnyOf, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a conditional select reduction PHI." << *Phi
                      << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FindLastIVSMax, TheLoop, FMF, RedDes, DB,
                      AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a FindLastIV reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FindFirstIVSMin, TheLoop, FMF, RedDes, DB,
                      AC, DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a FindFirstIV reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMaximum, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a float MAXIMUM reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMinimum, TheLoop, FMF, RedDes, DB, AC, DT,
                      SE)) {
    LLVM_DEBUG(dbgs() << "Found a float MINIMUM reduction PHI." << *Phi << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMaximumNum, TheLoop, FMF, RedDes, DB, AC,
                      DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a float MAXIMUMNUM reduction PHI." << *Phi
                      << "\n");
    return true;
  }
  if (AddReductionVar(Phi, RecurKind::FMinimumNum, TheLoop, FMF, RedDes, DB, AC,
                      DT, SE)) {
    LLVM_DEBUG(dbgs() << "Found a float MINIMUMNUM 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::Add:
    return Instruction::Add;
  case RecurKind::Mul:
    return Instruction::Mul;
  case RecurKind::AnyOf:
  case RecurKind::FindFirstIVSMin:
  case RecurKind::FindFirstIVUMin:
  case RecurKind::FindLastIVSMax:
  case RecurKind::FindLastIVUMax:
  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::FAdd:
    return Instruction::FAdd;
  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;
  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;

    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)
    : 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);
}

ConstantInt *InductionDescriptor::getConstIntStepValue() const {
  if (isa<SCEVConstant>(Step))
    return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->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) {

  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
  auto *PN = cast<PHINode>(PhiScev->getValue());
  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
  const Loop *L = AR->getLoop();

  // 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;
    }
    auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
    if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
      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);

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

  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))
      return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
  }

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

bool InductionDescriptor::isInductionPHI(
    PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
    InductionDescriptor &D, 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 SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);

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

  if (AR->getLoop() != TheLoop) {
    // FIXME: We should treat this as a uniform. Unfortunately, we
    // don't currently know how to handled uniform PHIs.
    LLVM_DEBUG(
        dbgs() << "LV: PHI is a recurrence with respect to an outer 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() == AR->getLoop()->getHeader()
    && "Invalid Phi node, not present in loop header");

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

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

  const SCEV *Step = AR->getStepRecurrence(*SE);
  // Calculate the pointer stride and check if it is consecutive.
  // The stride may be a constant or a loop invariant integer value.
  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
  if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
    return false;

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