//===- VPlanRecipes.cpp - Implementations for VPlan recipes ---------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file contains implementations for different VPlan recipes.
///
//===----------------------------------------------------------------------===//

#include "LoopVectorizationPlanner.h"
#include "VPlan.h"
#include "VPlanHelpers.h"
#include "VPlanPatternMatch.h"
#include "VPlanUtils.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallVectorExtras.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>

using namespace llvm;
using namespace llvm::VPlanPatternMatch;

using VectorParts = SmallVector<Value *, 2>;

#define LV_NAME "loop-vectorize"
#define DEBUG_TYPE LV_NAME

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
// It is sometimes necessary to disable printing of metadata in tests in order
// to avoid non-deterministic behaviour due to metadata introduced by VPlan
// that wasn't present in the original scalar IR.
static cl::opt<bool> VPlanPrintMetadata(
    "vplan-print-metadata", cl::init(true), cl::Hidden,
    cl::desc("Controls the printing of recipe metadata when debugging."));
#endif

bool VPRecipeBase::mayWriteToMemory() const {
  switch (getVPRecipeID()) {
  case VPExpressionSC:
    return cast<VPExpressionRecipe>(this)->mayReadOrWriteMemory();
  case VPInstructionSC: {
    auto *VPI = cast<VPInstruction>(this);
    // Loads read from memory but don't write to memory.
    if (VPI->getOpcode() == Instruction::Load)
      return false;
    return VPI->opcodeMayReadOrWriteFromMemory();
  }
  case VPInterleaveEVLSC:
  case VPInterleaveSC:
    return cast<VPInterleaveBase>(this)->getNumStoreOperands() > 0;
  case VPWidenStoreEVLSC:
  case VPWidenStoreSC:
    return true;
  case VPReplicateSC:
    return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
        ->mayWriteToMemory();
  case VPWidenCallSC:
    return !cast<VPWidenCallRecipe>(this)
                ->getCalledScalarFunction()
                ->onlyReadsMemory();
  case VPWidenMemIntrinsicSC:
  case VPWidenIntrinsicSC:
    return cast<VPWidenIntrinsicRecipe>(this)->mayWriteToMemory();
  case VPActiveLaneMaskPHISC:
  case VPCurrentIterationPHISC:
  case VPBranchOnMaskSC:
  case VPDerivedIVSC:
  case VPFirstOrderRecurrencePHISC:
  case VPReductionPHISC:
  case VPScalarIVStepsSC:
  case VPPredInstPHISC:
  case VPExpandSCEVSC:
    return false;
  case VPBlendSC:
  case VPReductionEVLSC:
  case VPReductionSC:
  case VPVectorPointerSC:
  case VPWidenCanonicalIVSC:
  case VPWidenCastSC:
  case VPWidenGEPSC:
  case VPWidenIntOrFpInductionSC:
  case VPWidenLoadEVLSC:
  case VPWidenLoadSC:
  case VPWidenPHISC:
  case VPWidenPointerInductionSC:
  case VPWidenSC: {
    const Instruction *I =
        dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
    (void)I;
    assert((!I || !I->mayWriteToMemory()) &&
           "underlying instruction may write to memory");
    return false;
  }
  default:
    return true;
  }
}

bool VPRecipeBase::mayReadFromMemory() const {
  switch (getVPRecipeID()) {
  case VPExpressionSC:
    return cast<VPExpressionRecipe>(this)->mayReadOrWriteMemory();
  case VPInstructionSC:
    return cast<VPInstruction>(this)->opcodeMayReadOrWriteFromMemory();
  case VPWidenLoadEVLSC:
  case VPWidenLoadSC:
    return true;
  case VPReplicateSC:
    return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
        ->mayReadFromMemory();
  case VPWidenCallSC:
    return !cast<VPWidenCallRecipe>(this)
                ->getCalledScalarFunction()
                ->onlyWritesMemory();
  case VPWidenMemIntrinsicSC:
  case VPWidenIntrinsicSC:
    return cast<VPWidenIntrinsicRecipe>(this)->mayReadFromMemory();
  case VPBranchOnMaskSC:
  case VPDerivedIVSC:
  case VPCurrentIterationPHISC:
  case VPFirstOrderRecurrencePHISC:
  case VPReductionPHISC:
  case VPPredInstPHISC:
  case VPScalarIVStepsSC:
  case VPWidenStoreEVLSC:
  case VPWidenStoreSC:
  case VPExpandSCEVSC:
    return false;
  case VPBlendSC:
  case VPReductionEVLSC:
  case VPReductionSC:
  case VPVectorPointerSC:
  case VPWidenCanonicalIVSC:
  case VPWidenCastSC:
  case VPWidenGEPSC:
  case VPWidenIntOrFpInductionSC:
  case VPWidenPHISC:
  case VPWidenPointerInductionSC:
  case VPWidenSC: {
    const Instruction *I =
        dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
    (void)I;
    assert((!I || !I->mayReadFromMemory()) &&
           "underlying instruction may read from memory");
    return false;
  }
  default:
    // FIXME: Return false if the recipe represents an interleaved store.
    return true;
  }
}

bool VPRecipeBase::mayHaveSideEffects() const {
  switch (getVPRecipeID()) {
  case VPExpressionSC:
    return cast<VPExpressionRecipe>(this)->mayHaveSideEffects();
  case VPActiveLaneMaskPHISC:
  case VPDerivedIVSC:
  case VPCurrentIterationPHISC:
  case VPFirstOrderRecurrencePHISC:
  case VPReductionPHISC:
  case VPPredInstPHISC:
  case VPVectorEndPointerSC:
  case VPExpandSCEVSC:
    return false;
  case VPInstructionSC: {
    auto *VPI = cast<VPInstruction>(this);
    return mayWriteToMemory() ||
           VPI->getOpcode() == VPInstruction::BranchOnCount ||
           VPI->getOpcode() == VPInstruction::BranchOnCond ||
           VPI->getOpcode() == VPInstruction::BranchOnTwoConds;
  }
  case VPWidenCallSC: {
    Function *Fn = cast<VPWidenCallRecipe>(this)->getCalledScalarFunction();
    return mayWriteToMemory() || !Fn->doesNotThrow() || !Fn->willReturn();
  }
  case VPWidenMemIntrinsicSC:
  case VPWidenIntrinsicSC:
    return cast<VPWidenIntrinsicRecipe>(this)->mayHaveSideEffects();
  case VPBlendSC:
  case VPReductionEVLSC:
  case VPReductionSC:
  case VPScalarIVStepsSC:
  case VPVectorPointerSC:
  case VPWidenCanonicalIVSC:
  case VPWidenCastSC:
  case VPWidenGEPSC:
  case VPWidenIntOrFpInductionSC:
  case VPWidenPHISC:
  case VPWidenPointerInductionSC:
  case VPWidenSC: {
    const Instruction *I =
        dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
    (void)I;
    assert((!I || !I->mayHaveSideEffects()) &&
           "underlying instruction has side-effects");
    return false;
  }
  case VPInterleaveEVLSC:
  case VPInterleaveSC:
    return mayWriteToMemory();
  case VPWidenLoadEVLSC:
  case VPWidenLoadSC:
  case VPWidenStoreEVLSC:
  case VPWidenStoreSC:
    assert(
        cast<VPWidenMemoryRecipe>(this)->getIngredient().mayHaveSideEffects() ==
            mayWriteToMemory() &&
        "mayHaveSideffects result for ingredient differs from this "
        "implementation");
    return mayWriteToMemory();
  case VPReplicateSC: {
    auto *R = cast<VPReplicateRecipe>(this);
    return R->getUnderlyingInstr()->mayHaveSideEffects();
  }
  default:
    return true;
  }
}

bool VPRecipeBase::isSafeToSpeculativelyExecute() const {
  switch (getVPRecipeID()) {
  default:
    return false;
  case VPInstructionSC: {
    unsigned Opcode = cast<VPInstruction>(this)->getOpcode();
    if (Instruction::isCast(Opcode))
      return true;

    switch (Opcode) {
    default:
      return false;
    case Instruction::Add:
    case Instruction::Sub:
    case Instruction::Mul:
    case Instruction::GetElementPtr:
      return true;
    }
  }
  }
}

void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
  assert(!Parent && "Recipe already in some VPBasicBlock");
  assert(InsertPos->getParent() &&
         "Insertion position not in any VPBasicBlock");
  InsertPos->getParent()->insert(this, InsertPos->getIterator());
}

void VPRecipeBase::insertBefore(VPBasicBlock &BB,
                                iplist<VPRecipeBase>::iterator I) {
  assert(!Parent && "Recipe already in some VPBasicBlock");
  assert(I == BB.end() || I->getParent() == &BB);
  BB.insert(this, I);
}

void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
  assert(!Parent && "Recipe already in some VPBasicBlock");
  assert(InsertPos->getParent() &&
         "Insertion position not in any VPBasicBlock");
  InsertPos->getParent()->insert(this, std::next(InsertPos->getIterator()));
}

void VPRecipeBase::removeFromParent() {
  assert(getParent() && "Recipe not in any VPBasicBlock");
  getParent()->getRecipeList().remove(getIterator());
  Parent = nullptr;
}

iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
  assert(getParent() && "Recipe not in any VPBasicBlock");
  return getParent()->getRecipeList().erase(getIterator());
}

void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
  removeFromParent();
  insertAfter(InsertPos);
}

void VPRecipeBase::moveBefore(VPBasicBlock &BB,
                              iplist<VPRecipeBase>::iterator I) {
  removeFromParent();
  insertBefore(BB, I);
}

InstructionCost VPRecipeBase::cost(ElementCount VF, VPCostContext &Ctx) {
  // Get the underlying instruction for the recipe, if there is one. It is used
  // to
  //   * decide if cost computation should be skipped for this recipe,
  //   * apply forced target instruction cost.
  Instruction *UI = nullptr;
  if (auto *S = dyn_cast<VPSingleDefRecipe>(this))
    UI = dyn_cast_or_null<Instruction>(S->getUnderlyingValue());
  else if (auto *IG = dyn_cast<VPInterleaveBase>(this))
    UI = IG->getInsertPos();
  else if (auto *WidenMem = dyn_cast<VPWidenMemoryRecipe>(this))
    UI = &WidenMem->getIngredient();

  InstructionCost RecipeCost;
  if (UI && Ctx.skipCostComputation(UI, VF.isVector())) {
    RecipeCost = 0;
  } else {
    RecipeCost = computeCost(VF, Ctx);
    if (ForceTargetInstructionCost.getNumOccurrences() > 0 &&
        RecipeCost.isValid()) {
      if (UI)
        RecipeCost = InstructionCost(ForceTargetInstructionCost);
      else
        RecipeCost = InstructionCost(0);
    }
  }

  LLVM_DEBUG({
    dbgs() << "Cost of " << RecipeCost << " for VF " << VF << ": ";
    if (VPSlotTracker *SlotTracker = Ctx.getSlotTracker()) {
      print(dbgs(), "", *SlotTracker);
      dbgs() << "\n";
    } else {
      dump();
    }
  });
  return RecipeCost;
}

InstructionCost VPRecipeBase::computeCost(ElementCount VF,
                                          VPCostContext &Ctx) const {
  llvm_unreachable("subclasses should implement computeCost");
}

bool VPRecipeBase::isPhi() const {
  return (getVPRecipeID() >= VPFirstPHISC && getVPRecipeID() <= VPLastPHISC) ||
         isa<VPPhi, VPIRPhi>(this);
}

void VPIRFlags::intersectFlags(const VPIRFlags &Other) {
  assert(OpType == Other.OpType && "OpType must match");
  switch (OpType) {
  case OperationType::OverflowingBinOp:
    WrapFlags.HasNUW &= Other.WrapFlags.HasNUW;
    WrapFlags.HasNSW &= Other.WrapFlags.HasNSW;
    break;
  case OperationType::Trunc:
    TruncFlags.HasNUW &= Other.TruncFlags.HasNUW;
    TruncFlags.HasNSW &= Other.TruncFlags.HasNSW;
    break;
  case OperationType::DisjointOp:
    DisjointFlags.IsDisjoint &= Other.DisjointFlags.IsDisjoint;
    break;
  case OperationType::PossiblyExactOp:
    ExactFlags.IsExact &= Other.ExactFlags.IsExact;
    break;
  case OperationType::GEPOp:
    GEPFlagsStorage &= Other.GEPFlagsStorage;
    break;
  case OperationType::FPMathOp:
  case OperationType::FCmp:
    assert((OpType != OperationType::FCmp ||
            FCmpFlags.CmpPredStorage == Other.FCmpFlags.CmpPredStorage) &&
           "Cannot drop CmpPredicate");
    getFMFsRef() = getFastMathFlagsOrNone() & Other.getFastMathFlagsOrNone();
    break;
  case OperationType::NonNegOp:
    NonNegFlags.NonNeg &= Other.NonNegFlags.NonNeg;
    break;
  case OperationType::Cmp:
    assert(CmpPredStorage == Other.CmpPredStorage &&
           "Cannot drop CmpPredicate");
    break;
  case OperationType::ReductionOp:
    assert(ReductionFlags.Kind == Other.ReductionFlags.Kind &&
           "Cannot change RecurKind");
    assert(ReductionFlags.IsOrdered == Other.ReductionFlags.IsOrdered &&
           "Cannot change IsOrdered");
    assert(ReductionFlags.IsInLoop == Other.ReductionFlags.IsInLoop &&
           "Cannot change IsInLoop");
    getFMFsRef() = getFastMathFlagsOrNone() & Other.getFastMathFlagsOrNone();
    break;
  case OperationType::Other:
    break;
  }
}

FastMathFlags VPIRFlags::getFastMathFlagsOrNone() const {
  if (!hasFastMathFlags())
    return {};
  const FastMathFlagsTy &F = getFMFsRef();
  FastMathFlags Res;
  Res.setAllowReassoc(F.AllowReassoc);
  Res.setNoNaNs(F.NoNaNs);
  Res.setNoInfs(F.NoInfs);
  Res.setNoSignedZeros(F.NoSignedZeros);
  Res.setAllowReciprocal(F.AllowReciprocal);
  Res.setAllowContract(F.AllowContract);
  Res.setApproxFunc(F.ApproxFunc);
  return Res;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPSingleDefRecipe::dump() const { VPRecipeBase::dump(); }

void VPRecipeBase::print(raw_ostream &O, const Twine &Indent,
                         VPSlotTracker &SlotTracker) const {
  printRecipe(O, Indent, SlotTracker);
  if (auto DL = getDebugLoc()) {
    O << ", !dbg ";
    DL.print(O);
  }

  if (auto *Metadata = dyn_cast<VPIRMetadata>(this))
    Metadata->print(O, SlotTracker);
}
#endif

VPExpandSCEVRecipe::VPExpandSCEVRecipe(const SCEV *Expr)
    : VPSingleDefRecipe(VPRecipeBase::VPExpandSCEVSC, {}, Expr->getType()),
      Expr(Expr) {}

/// For call VPInstruction operands, return the operand index of the called
/// function. The function is either the last operand (for unmasked calls) or
/// the second-to-last operand (for masked calls).
static unsigned getCalledFnOperandIndex(ArrayRef<VPValue *> Operands) {
  unsigned NumOps = Operands.size();
  auto *LastOp = dyn_cast<VPIRValue>(Operands[NumOps - 1]);
  if (LastOp && isa<Function>(LastOp->getValue()))
    return NumOps - 1;
  assert(isa<Function>(cast<VPIRValue>(Operands[NumOps - 2])->getValue()) &&
         "expected function operand");
  return NumOps - 2;
}

/// For call VPInstruction operands, return the called function.
static Function *getCalledFunction(ArrayRef<VPValue *> Operands) {
  unsigned Idx = getCalledFnOperandIndex(Operands);
  return cast<Function>(cast<VPIRValue>(Operands[Idx])->getValue());
}

Type *llvm::computeScalarTypeForInstruction(unsigned Opcode,
                                            ArrayRef<VPValue *> Operands) {
  assert(!Operands.empty() &&
         "zero-operand VPInstruction opcodes must pass explicit ResultTy");
  // Assert operand \p Idx (if present and typed) has type \p ExpectedTy.
  [[maybe_unused]] auto AssertOperandType = [&Operands](unsigned Idx,
                                                        Type *ExpectedTy) {
    if (!ExpectedTy || Operands.size() <= Idx)
      return;
    [[maybe_unused]] Type *OpTy = Operands[Idx]->getScalarType();
    assert((!OpTy || OpTy == ExpectedTy) &&
           "different types inferred for different operands");
  };

  Type *Op0Ty = Operands[0]->getScalarType();
  LLVMContext &Ctx = Op0Ty->getContext();
  switch (Opcode) {
  case VPInstruction::BranchOnCond:
    assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
    return Type::getVoidTy(Ctx);
  case VPInstruction::BranchOnTwoConds:
    assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
    AssertOperandType(1, IntegerType::get(Ctx, 1));
    return Type::getVoidTy(Ctx);
  case VPInstruction::BranchOnCount:
    assert(Op0Ty->isIntegerTy() && "expected integer operand");
    AssertOperandType(1, Op0Ty);
    return Type::getVoidTy(Ctx);
  case VPInstruction::CanonicalIVIncrementForPart:
    assert(Op0Ty->isIntegerTy() && "expected integer operand");
    for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
      AssertOperandType(Idx, Op0Ty);
    return Op0Ty;
  case Instruction::Switch:
    for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
      AssertOperandType(Idx, Op0Ty);
    return Type::getVoidTy(Ctx);
  case Instruction::Store:
    return Type::getVoidTy(Ctx);
  case Instruction::ICmp:
    assert(Op0Ty->isIntOrPtrTy() && "expected integer or pointer operand");
    AssertOperandType(1, Op0Ty);
    return IntegerType::get(Ctx, 1);
  case Instruction::FCmp:
    assert(Op0Ty->isFloatingPointTy() && "expected floating-point operand");
    AssertOperandType(1, Op0Ty);
    return IntegerType::get(Ctx, 1);
  case VPInstruction::ActiveLaneMask:
  case VPInstruction::WideActiveLaneMask:
    assert(Op0Ty->isIntegerTy() && "expected integer operand");
    AssertOperandType(1, Op0Ty);
    return IntegerType::get(Ctx, 1);
  case VPInstruction::MaskedCond:
    assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
    return IntegerType::get(Ctx, 1);
  case VPInstruction::LogicalAnd:
  case VPInstruction::LogicalOr:
    assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
    AssertOperandType(1, Op0Ty);
    return IntegerType::get(Ctx, 1);
  case VPInstruction::AnyOf:
    assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
    for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
      AssertOperandType(Idx, Op0Ty);
    return IntegerType::get(Ctx, 1);
  case VPInstruction::ExplicitVectorLength:
    assert(Op0Ty->isIntegerTy() && "expected integer operand");
    return IntegerType::get(Ctx, 32);
  case Instruction::Select: {
    assert((!Op0Ty || Op0Ty->isIntegerTy(1)) &&
           "select condition must be bool");
    Type *Op1Ty = Operands[1]->getScalarType();
    AssertOperandType(2, Op1Ty);
    return Op1Ty;
  }
  case Instruction::InsertElement:
    // The inserted scalar (operand 1) must match the vector element type;
    // operand 2 must be an integer.
    AssertOperandType(1, Op0Ty);
    assert(Operands[2]->getScalarType()->isIntegerTy() &&
           "expected integer operand");
    return Op0Ty;
  case VPInstruction::ReductionStartVector:
    // The start value and the identity value (operands 0 and 1) fill the same
    // vector and must match in type; operand 2 is the scaling factor.
    AssertOperandType(1, Op0Ty);
    return Op0Ty;
  case VPInstruction::ExtractLane: {
    assert(Operands.size() >= 2 && "ExtractLane requires a lane operand and "
                                   "at least one source vector operand");
    // Operand 0 is the lane index, used for integer arithmetic.
    assert(Op0Ty->isIntegerTy() && "expected integer operand");
    Type *Op1Ty = Operands[1]->getScalarType();
    for (unsigned Idx = 2; Idx != Operands.size(); ++Idx)
      AssertOperandType(Idx, Op1Ty);
    return Op1Ty;
  }
  case VPInstruction::PtrAdd:
  case VPInstruction::WidePtrAdd:
    assert(Operands[0]->getScalarType()->isPointerTy() &&
           "expected pointer operand");
    assert(Operands[1]->getScalarType()->isIntegerTy() &&
           "expected integer operand");
    return Op0Ty;
  case Instruction::ExtractValue: {
    assert(Operands.size() == 2 && "expected single level extractvalue");
    auto *StructTy = cast<StructType>(Op0Ty);
    return StructTy->getTypeAtIndex(
        cast<VPConstantInt>(Operands[1])->getZExtValue());
  }
  case VPInstruction::FirstActiveLane:
  case VPInstruction::LastActiveLane:
  case VPInstruction::NumActiveLanes:
  case VPInstruction::IncomingAliasMask:
  case Instruction::Load:
  case Instruction::Alloca:
    llvm_unreachable("type must be passed explicitly");
  case Instruction::Call:
    return getCalledFunction(Operands)->getReturnType();
  default:
    break;
  }

  // Opcodes that require all operands to share the same scalar type as the
  // result.
  bool AllOperandsSameType =
      Instruction::isBinaryOp(Opcode) ||
      is_contained({VPInstruction::FirstOrderRecurrenceSplice,
                    VPInstruction::BuildVector,
                    VPInstruction::BuildStructVector},
                   Opcode);
  if (AllOperandsSameType)
    for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
      AssertOperandType(Idx, Op0Ty);

  return Op0Ty;
}

Type *VPReplicateRecipe::computeScalarType(const Instruction *I,
                                           ArrayRef<VPValue *> Operands) {
  unsigned Opcode = I->getOpcode();
  if (Instruction::isCast(Opcode) ||
      is_contained(ArrayRef<unsigned>({Instruction::ExtractValue,
                                       Instruction::Load, Instruction::Alloca}),
                   Opcode))
    return I->getType();
  return computeScalarTypeForInstruction(Opcode, Operands);
}

VPInstruction::VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,
                             const VPIRFlags &Flags, const VPIRMetadata &MD,
                             DebugLoc DL, const Twine &Name, Type *ResultTy)
    : VPRecipeWithIRFlags(
          VPRecipeBase::VPInstructionSC, Operands,
          ResultTy ? ResultTy
                   : computeScalarTypeForInstruction(Opcode, Operands),
          Flags, DL),
      VPIRMetadata(MD), Opcode(Opcode), Name(Name.str()) {
  assert(flagsValidForOpcode(getOpcode()) &&
         "Set flags not supported for the provided opcode");
  assert(hasRequiredFlagsForOpcode(getOpcode(), getScalarType()) &&
         "Opcode requires specific flags to be set");
  assert((getNumOperandsForOpcode() == -1u ||
          getNumOperandsForOpcode() == getNumOperands() ||
          (isMasked() && getNumOperandsForOpcode() + 1 == getNumOperands())) &&
         "number of operands does not match opcode");
}

unsigned VPInstruction::getNumOperandsForOpcode() const {
  if (Instruction::isUnaryOp(Opcode) || Instruction::isCast(Opcode))
    return 1;

  if (Instruction::isBinaryOp(Opcode))
    return 2;

  switch (Opcode) {
  case VPInstruction::StepVector:
  case VPInstruction::IncomingAliasMask:
    return 0;
  case Instruction::Alloca:
  case Instruction::ExtractValue:
  case Instruction::Freeze:
  case Instruction::Load:
  case VPInstruction::BranchOnCond:
  case VPInstruction::Broadcast:
  case VPInstruction::ExitingIVValue:
  case VPInstruction::ExplicitVectorLength:
  case VPInstruction::ExtractLastLane:
  case VPInstruction::ExtractLastPart:
  case VPInstruction::ExtractPenultimateElement:
  case VPInstruction::MaskedCond:
  case VPInstruction::Not:
  case VPInstruction::Reverse:
  case VPInstruction::Unpack:
  case VPInstruction::NumActiveLanes:
    return 1;
  case Instruction::ICmp:
  case Instruction::FCmp:
  case Instruction::ExtractElement:
  case Instruction::Store:
  case VPInstruction::ActiveLaneMask:
  case VPInstruction::BranchOnCount:
  case VPInstruction::BranchOnTwoConds:
  case VPInstruction::FirstOrderRecurrenceSplice:
  case VPInstruction::LogicalAnd:
  case VPInstruction::LogicalOr:
  case VPInstruction::PtrAdd:
  case VPInstruction::WidePtrAdd:
  case VPInstruction::WideIVStep:
  case VPInstruction::ResumeForEpilogue:
  case VPInstruction::ExtractVectorForPart:
    return 2;
  case Instruction::InsertElement:
  case Instruction::Select:
  case VPInstruction::WideActiveLaneMask:
  case VPInstruction::ReductionStartVector:
    return 3;
  case Instruction::Call:
    return getCalledFnOperandIndex(operands()) + 1;
  case Instruction::GetElementPtr:
  case Instruction::PHI:
  case Instruction::Switch:
  case Instruction::AtomicRMW:
  case Instruction::AtomicCmpXchg:
  case Instruction::Fence:
  case VPInstruction::AnyOf:
  case VPInstruction::BuildStructVector:
  case VPInstruction::BuildVector:
  case VPInstruction::Intrinsic:
  case VPInstruction::CanonicalIVIncrementForPart:
  case VPInstruction::ComputeReductionResult:
  case VPInstruction::FirstActiveLane:
  case VPInstruction::LastActiveLane:
  case VPInstruction::ExtractLane:
  case VPInstruction::ExtractLastActive:
    // Cannot determine the number of operands from the opcode.
    return -1u;
  }
  llvm_unreachable("all cases should be handled above");
}

bool VPInstruction::doesGeneratePerAllLanes() const {
  return Opcode == VPInstruction::Unpack ||
         (Opcode == VPInstruction::PtrAdd && !vputils::onlyFirstLaneUsed(this));
}

bool VPInstruction::canGenerateScalarForFirstLane() const {
  if (Instruction::isBinaryOp(getOpcode()) || Instruction::isCast(getOpcode()))
    return true;
  if (isSingleScalar() || isVectorToScalar())
    return true;
  switch (Opcode) {
  case Instruction::Freeze:
  case Instruction::ICmp:
  case Instruction::PHI:
  case Instruction::Select:
  case VPInstruction::BranchOnCond:
  case VPInstruction::BranchOnTwoConds:
  case VPInstruction::BranchOnCount:
  case VPInstruction::CanonicalIVIncrementForPart:
  case VPInstruction::PtrAdd:
  case VPInstruction::ExplicitVectorLength:
  case VPInstruction::AnyOf:
  case VPInstruction::Not:
    return true;
  default:
    return false;
  }
}

static Instruction::BinaryOps getSubRecurOpcode(RecurKind Kind) {
  if (Kind == RecurKind::Sub)
    return Instruction::Add;
  if (Kind == RecurKind::FSub)
    return Instruction::FAdd;
  llvm_unreachable("RecurKind should be Sub/FSub.");
}

Value *VPInstruction::generate(VPTransformState &State) {
  IRBuilderBase &Builder = State.Builder;

  if (Instruction::isBinaryOp(getOpcode())) {
    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);
    Value *A = State.get(getOperand(0), OnlyFirstLaneUsed);
    Value *B = State.get(getOperand(1), OnlyFirstLaneUsed);
    auto *Res =
        Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B, Name);
    if (auto *I = dyn_cast<Instruction>(Res))
      applyFlags(*I);
    return Res;
  }

  switch (getOpcode()) {
  case VPInstruction::Not: {
    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);
    Value *A = State.get(getOperand(0), OnlyFirstLaneUsed);
    return Builder.CreateNot(A, Name);
  }
  case Instruction::ExtractElement: {
    assert(State.VF.isVector() && "Only extract elements from vectors");
    if (auto *Idx = dyn_cast<VPConstantInt>(getOperand(1)))
      return State.get(getOperand(0), VPLane(Idx->getZExtValue()));
    Value *Vec = State.get(getOperand(0));
    Value *Idx = State.get(getOperand(1), /*IsScalar=*/true);
    return Builder.CreateExtractElement(Vec, Idx, Name);
  }
  case Instruction::InsertElement: {
    assert(State.VF.isVector() && "Can only insert elements into vectors");
    Value *Vec = State.get(getOperand(0), /*IsScalar=*/false);
    Value *Elt = State.get(getOperand(1), /*IsScalar=*/true);
    Value *Idx = State.get(getOperand(2), /*IsScalar=*/true);
    return Builder.CreateInsertElement(Vec, Elt, Idx, Name);
  }
  case Instruction::Freeze: {
    Value *Op = State.get(getOperand(0), vputils::onlyFirstLaneUsed(this));
    return Builder.CreateFreeze(Op, Name);
  }
  case Instruction::FCmp:
  case Instruction::ICmp: {
    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);
    Value *A = State.get(getOperand(0), OnlyFirstLaneUsed);
    Value *B = State.get(getOperand(1), OnlyFirstLaneUsed);
    return Builder.CreateCmp(getPredicate(), A, B, Name);
  }
  case Instruction::PHI: {
    llvm_unreachable("should be handled by VPPhi::execute");
  }
  case Instruction::Select: {
    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);
    Value *Cond =
        State.get(getOperand(0),
                  OnlyFirstLaneUsed || vputils::isSingleScalar(getOperand(0)));
    Value *Op1 = State.get(getOperand(1), OnlyFirstLaneUsed);
    Value *Op2 = State.get(getOperand(2), OnlyFirstLaneUsed);
    return Builder.CreateSelectFMF(Cond, Op1, Op2, getFastMathFlagsOrNone(),
                                   Name);
  }
  case VPInstruction::ActiveLaneMask:
  case VPInstruction::WideActiveLaneMask: {
    // Get first lane of vector induction variable.
    Value *VIVElem0 = State.get(getOperand(0), VPLane(0));
    // Get the original loop tripcount.
    Value *ScalarTC = State.get(getOperand(1), VPLane(0));

    uint64_t Multiplier =
        getOpcode() == VPInstruction::WideActiveLaneMask
            ? cast<VPConstantInt>(getOperand(2))->getZExtValue()
            : 1;

    // If this part of the active lane mask is scalar, generate the CMP directly
    // to avoid unnecessary extracts.
    if (State.VF.isScalar() && Multiplier == 1)
      return Builder.CreateCmp(CmpInst::Predicate::ICMP_ULT, VIVElem0, ScalarTC,
                               Name);

    ElementCount EC = State.VF.multiplyCoefficientBy(Multiplier);
    auto *PredTy = VectorType::get(Builder.getInt1Ty(), EC);
    return Builder.CreateIntrinsic(Intrinsic::get_active_lane_mask,
                                   {PredTy, ScalarTC->getType()},
                                   {VIVElem0, ScalarTC}, nullptr, Name);
  }
  case VPInstruction::NumActiveLanes: {
    Value *Op = State.get(getOperand(0));
    auto *VecTy = cast<VectorType>(Op->getType());
    assert(VecTy->getScalarSizeInBits() == 1 &&
           "NumActiveLanes only implemented for i1 vectors");

    Type *Ty = getScalarType();
    Value *ZExt = Builder.CreateCast(
        Instruction::ZExt, Op, VectorType::get(Ty, VecTy->getElementCount()));
    Value *NumActive =
        Builder.CreateUnaryIntrinsic(Intrinsic::vector_reduce_add, ZExt);
    return NumActive;
  }
  case VPInstruction::FirstOrderRecurrenceSplice: {
    // Generate code to combine the previous and current values in vector v3.
    //
    //   vector.ph:
    //     v_init = vector(..., ..., ..., a[-1])
    //     br vector.body
    //
    //   vector.body
    //     i = phi [0, vector.ph], [i+4, vector.body]
    //     v1 = phi [v_init, vector.ph], [v2, vector.body]
    //     v2 = a[i, i+1, i+2, i+3];
    //     v3 = vector(v1(3), v2(0, 1, 2))

    auto *V1 = State.get(getOperand(0));
    if (!V1->getType()->isVectorTy())
      return V1;
    Value *V2 = State.get(getOperand(1));
    return Builder.CreateVectorSpliceRight(V1, V2, 1, Name);
  }
  case VPInstruction::ExplicitVectorLength: {
    // TODO: Restructure this code with an explicit remainder loop, vsetvli can
    // be outside of the main loop.
    Value *AVL = State.get(getOperand(0), /*IsScalar*/ true);
    // Compute EVL
    assert(AVL->getType()->isIntegerTy() &&
           "Requested vector length should be an integer.");

    assert(State.VF.isScalable() && "Expected scalable vector factor.");
    Value *VFArg = Builder.getInt32(State.VF.getKnownMinValue());

    Value *EVL = Builder.CreateIntrinsic(
        Builder.getInt32Ty(), Intrinsic::experimental_get_vector_length,
        {AVL, VFArg, Builder.getTrue()});
    return EVL;
  }
  case VPInstruction::BranchOnCond: {
    Value *Cond = State.get(getOperand(0), VPLane(0));
    // Replace the temporary unreachable terminator with a new conditional
    // branch, hooking it up to backward destination for latch blocks now, and
    // to forward destination(s) later when they are created.
    // Second successor may be backwards - iff it is already in VPBB2IRBB.
    VPBasicBlock *SecondVPSucc =
        cast<VPBasicBlock>(getParent()->getSuccessors()[1]);
    BasicBlock *SecondIRSucc = State.CFG.VPBB2IRBB.lookup(SecondVPSucc);
    BasicBlock *IRBB = State.CFG.VPBB2IRBB[getParent()];
    auto *Br = Builder.CreateCondBr(Cond, IRBB, SecondIRSucc);
    // First successor is always forward, reset it to nullptr.
    Br->setSuccessor(0, nullptr);
    IRBB->getTerminator()->eraseFromParent();
    applyMetadata(*Br);
    return Br;
  }
  case VPInstruction::Broadcast: {
    return Builder.CreateVectorSplat(
        State.VF, State.get(getOperand(0), /*IsScalar*/ true), "broadcast");
  }
  case VPInstruction::BuildStructVector: {
    // For struct types, we need to build a new 'wide' struct type, where each
    // element is widened, i.e., we create a struct of vectors.
    auto *StructTy = cast<StructType>(getOperand(0)->getScalarType());
    Value *Res = PoisonValue::get(toVectorizedTy(StructTy, State.VF));
    for (const auto &[LaneIndex, Op] : enumerate(operands())) {
      for (unsigned FieldIndex = 0; FieldIndex != StructTy->getNumElements();
           FieldIndex++) {
        Value *ScalarValue =
            Builder.CreateExtractValue(State.get(Op, true), FieldIndex);
        Value *VectorValue = Builder.CreateExtractValue(Res, FieldIndex);
        VectorValue =
            Builder.CreateInsertElement(VectorValue, ScalarValue, LaneIndex);
        Res = Builder.CreateInsertValue(Res, VectorValue, FieldIndex);
      }
    }
    return Res;
  }
  case VPInstruction::BuildVector: {
    auto *ScalarTy = getOperand(0)->getScalarType();
    auto NumOfElements = ElementCount::getFixed(getNumOperands());
    Value *Res = PoisonValue::get(toVectorizedTy(ScalarTy, NumOfElements));
    for (const auto &[Idx, Op] : enumerate(operands()))
      Res = Builder.CreateInsertElement(Res, State.get(Op, true),
                                        Builder.getInt64(Idx));
    return Res;
  }
  case VPInstruction::ReductionStartVector: {
    if (State.VF.isScalar())
      return State.get(getOperand(0), true);
    IRBuilderBase::FastMathFlagGuard FMFG(Builder);
    Builder.setFastMathFlags(getFastMathFlagsOrNone());
    // If this start vector is scaled then it should produce a vector with fewer
    // elements than the VF.
    ElementCount VF = State.VF.divideCoefficientBy(
        cast<VPConstantInt>(getOperand(2))->getZExtValue());
    auto *Iden = Builder.CreateVectorSplat(VF, State.get(getOperand(1), true));
    return Builder.CreateInsertElement(Iden, State.get(getOperand(0), true),
                                       Builder.getInt64(0));
  }
  case VPInstruction::ComputeReductionResult: {
    RecurKind RK = getRecurKind();
    bool IsOrdered = isReductionOrdered();
    bool IsInLoop = isReductionInLoop();
    assert(!RecurrenceDescriptor::isFindIVRecurrenceKind(RK) &&
           "FindIV should use min/max reduction kinds");

    // The recipe may have multiple operands to be reduced together.
    unsigned NumOperandsToReduce = getNumOperands();
    VectorParts RdxParts(NumOperandsToReduce);
    for (unsigned Part = 0; Part < NumOperandsToReduce; ++Part)
      RdxParts[Part] = State.get(getOperand(Part), IsInLoop);

    IRBuilderBase::FastMathFlagGuard FMFG(Builder);
    Builder.setFastMathFlags(getFastMathFlagsOrNone());

    // Reduce multiple operands into one.
    Value *ReducedPartRdx = RdxParts[0];
    if (IsOrdered) {
      ReducedPartRdx = RdxParts[NumOperandsToReduce - 1];
    } else {
      // Floating-point operations should have some FMF to enable the reduction.
      for (unsigned Part = 1; Part < NumOperandsToReduce; ++Part) {
        Value *RdxPart = RdxParts[Part];
        if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK))
          ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart);
        else {
          // For sub-recurrences, each part's reduction variable is already
          // negative, we need to do: reduce.add(-acc_uf0 + -acc_uf1)
          Instruction::BinaryOps Opcode =
              RecurrenceDescriptor::isSubRecurrenceKind(RK)
                  ? getSubRecurOpcode(RK)
                  : (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(RK);
          ReducedPartRdx =
              Builder.CreateBinOp(Opcode, RdxPart, ReducedPartRdx, "bin.rdx");
        }
      }
    }

    // Create the reduction after the loop. Note that inloop reductions create
    // the target reduction in the loop using a Reduction recipe.
    if (State.VF.isVector() && !IsInLoop) {
      // TODO: Support in-order reductions based on the recurrence descriptor.
      // All ops in the reduction inherit fast-math-flags from the recurrence
      // descriptor.
      ReducedPartRdx = createSimpleReduction(Builder, ReducedPartRdx, RK);
    }

    return ReducedPartRdx;
  }
  case VPInstruction::ExtractLastLane:
  case VPInstruction::ExtractPenultimateElement: {
    unsigned Offset =
        getOpcode() == VPInstruction::ExtractPenultimateElement ? 2 : 1;
    Value *Res;
    if (State.VF.isVector()) {
      assert(Offset <= State.VF.getKnownMinValue() &&
             "invalid offset to extract from");
      // Extract lane VF - Offset from the operand.
      Res = State.get(getOperand(0), VPLane::getLaneFromEnd(State.VF, Offset));
    } else {
      // TODO: Remove ExtractLastLane for scalar VFs.
      assert(Offset <= 1 && "invalid offset to extract from");
      Res = State.get(getOperand(0));
    }
    if (isa<ExtractElementInst>(Res))
      Res->setName(Name);
    return Res;
  }
  case VPInstruction::LogicalAnd: {
    Value *A = State.get(getOperand(0));
    Value *B = State.get(getOperand(1));
    return Builder.CreateLogicalAnd(A, B, Name);
  }
  case VPInstruction::LogicalOr: {
    Value *A = State.get(getOperand(0));
    Value *B = State.get(getOperand(1));
    return Builder.CreateLogicalOr(A, B, Name);
  }
  case VPInstruction::PtrAdd: {
    assert((State.VF.isScalar() || vputils::onlyFirstLaneUsed(this)) &&
           "can only generate first lane for PtrAdd");
    Value *Ptr = State.get(getOperand(0), VPLane(0));
    Value *Addend = State.get(getOperand(1), VPLane(0));
    return Builder.CreatePtrAdd(Ptr, Addend, Name, getGEPNoWrapFlags());
  }
  case VPInstruction::WidePtrAdd: {
    Value *Ptr =
        State.get(getOperand(0), vputils::isSingleScalar(getOperand(0)));
    Value *Addend = State.get(getOperand(1));
    return Builder.CreatePtrAdd(Ptr, Addend, Name, getGEPNoWrapFlags());
  }
  case VPInstruction::AnyOf: {
    Value *Res = Builder.CreateFreeze(State.get(getOperand(0)));
    for (VPValue *Op : drop_begin(operands()))
      Res = Builder.CreateOr(Res, Builder.CreateFreeze(State.get(Op)));
    return State.VF.isScalar() ? Res : Builder.CreateOrReduce(Res);
  }
  case VPInstruction::ExtractLane: {
    assert(getNumOperands() != 2 && "ExtractLane from single source should be "
                                    "simplified to ExtractElement.");
    Value *LaneToExtract = State.get(getOperand(0), true);
    Type *IdxTy = getOperand(0)->getScalarType();
    Value *Res = nullptr;
    Value *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);

    for (unsigned Idx = 1; Idx != getNumOperands(); ++Idx) {
      Value *VectorStart =
          Builder.CreateMul(RuntimeVF, ConstantInt::get(IdxTy, Idx - 1));
      Value *VectorIdx = Idx == 1
                             ? LaneToExtract
                             : Builder.CreateSub(LaneToExtract, VectorStart);
      Value *Ext = State.VF.isScalar()
                       ? State.get(getOperand(Idx))
                       : Builder.CreateExtractElement(
                             State.get(getOperand(Idx)), VectorIdx);
      if (Res) {
        Value *Cmp = Builder.CreateICmpUGE(LaneToExtract, VectorStart);
        Res = Builder.CreateSelect(Cmp, Ext, Res);
      } else {
        Res = Ext;
      }
    }
    return Res;
  }
  case VPInstruction::FirstActiveLane: {
    Type *Ty = this->getScalarType();
    if (getNumOperands() == 1) {
      Value *Mask = State.get(getOperand(0));
      return Builder.CreateCountTrailingZeroElems(Ty, Mask,
                                                  /*ZeroIsPoison=*/false, Name);
    }
    // If there are multiple operands, create a chain of selects to pick the
    // first operand with an active lane and add the number of lanes of the
    // preceding operands.
    Value *RuntimeVF = getRuntimeVF(Builder, Ty, State.VF);
    unsigned LastOpIdx = getNumOperands() - 1;
    Value *Res = nullptr;
    for (int Idx = LastOpIdx; Idx >= 0; --Idx) {
      Value *TrailingZeros =
          State.VF.isScalar()
              ? Builder.CreateZExt(
                    Builder.CreateICmpEQ(State.get(getOperand(Idx)),
                                         Builder.getFalse()),
                    Ty)
              : Builder.CreateCountTrailingZeroElems(
                    Ty, State.get(getOperand(Idx)),
                    /*ZeroIsPoison=*/false, Name);
      Value *Current = Builder.CreateAdd(
          Builder.CreateMul(RuntimeVF, ConstantInt::get(Ty, Idx)),
          TrailingZeros);
      if (Res) {
        Value *Cmp = Builder.CreateICmpNE(TrailingZeros, RuntimeVF);
        Res = Builder.CreateSelect(Cmp, Current, Res);
      } else {
        Res = Current;
      }
    }

    return Res;
  }
  case VPInstruction::ResumeForEpilogue:
    return State.get(getOperand(0), true);
  case VPInstruction::Reverse:
    return Builder.CreateVectorReverse(State.get(getOperand(0)), "reverse");
  case VPInstruction::ExtractLastActive: {
    Value *Result = State.get(getOperand(0), /*IsScalar=*/true);
    for (unsigned Idx = 1; Idx < getNumOperands(); Idx += 2) {
      Value *Data = State.get(getOperand(Idx));
      Value *Mask = State.get(getOperand(Idx + 1));
      Type *VTy = Data->getType();

      if (State.VF.isScalar())
        Result = Builder.CreateSelect(Mask, Data, Result);
      else
        Result = Builder.CreateIntrinsic(
            Intrinsic::experimental_vector_extract_last_active, {VTy},
            {Data, Mask, Result});
    }

    return Result;
  }
  case VPInstruction::ExtractVectorForPart: {
    Value *Src = State.get(getOperand(0));
    Type *DstTy = VectorType::get(getScalarType(), State.VF);
    uint64_t Part = cast<VPConstantInt>(getOperand(1))->getZExtValue();

    if (Src->getType() == DstTy)
      return Src;

    return Builder.CreateExtractVector(
        DstTy, Src, Builder.getInt64(State.VF.getKnownMinValue() * Part), Name);
  }
  default:
    llvm_unreachable("Unsupported opcode for instruction");
  }
}

InstructionCost VPRecipeWithIRFlags::getCostForRecipeWithOpcode(
    unsigned Opcode, ElementCount VF, VPCostContext &Ctx) const {
  Type *ScalarTy = this->getScalarType();
  Type *ResultTy = VF.isVector() ? toVectorTy(ScalarTy, VF) : ScalarTy;
  switch (Opcode) {
  case Instruction::FNeg:
    return Ctx.TTI.getArithmeticInstrCost(Opcode, ResultTy, Ctx.CostKind);
  case Instruction::UDiv:
  case Instruction::SDiv:
  case Instruction::SRem:
  case Instruction::URem:
  case Instruction::Add:
  case Instruction::FAdd:
  case Instruction::Sub:
  case Instruction::FSub:
  case Instruction::Mul:
  case Instruction::FMul:
  case Instruction::FDiv:
  case Instruction::FRem:
  case Instruction::Shl:
  case Instruction::LShr:
  case Instruction::AShr:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor: {
    // Certain instructions can be cheaper if they have a constant second
    // operand. One example of this are shifts on x86.
    VPValue *RHS = getOperand(1);
    TargetTransformInfo::OperandValueInfo RHSInfo = Ctx.getOperandInfo(RHS);

    if (RHSInfo.Kind == TargetTransformInfo::OK_AnyValue &&
        getOperand(1)->isDefinedOutsideLoopRegions())
      RHSInfo.Kind = TargetTransformInfo::OK_UniformValue;

    Instruction *CtxI = dyn_cast_or_null<Instruction>(getUnderlyingValue());
    SmallVector<const Value *, 4> Operands;
    if (CtxI)
      Operands.append(CtxI->value_op_begin(), CtxI->value_op_end());
    return Ctx.TTI.getArithmeticInstrCost(
        Opcode, ResultTy, Ctx.CostKind,
        {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
        RHSInfo, Operands, CtxI, &Ctx.TLI);
  }
  case Instruction::Freeze:
    // NOTE: The only way to ask for the cost is via getInstructionCost, which
    // requires the actual vector instruction. Instead, both here and in the
    // LoopVectorizationCostModel::getInstructionCost the costs mirror the
    // current behaviour in llvm/Analysis/TargetTransformInfoImpl.h to keep
    // them in sync.
    return TTI::TCC_Free;
  case Instruction::ExtractValue:
    return Ctx.TTI.getInsertExtractValueCost(Instruction::ExtractValue,
                                             Ctx.CostKind);
  case Instruction::ICmp:
  case Instruction::FCmp: {
    Type *ScalarOpTy = getOperand(0)->getScalarType();
    Type *OpTy = VF.isVector() ? toVectorTy(ScalarOpTy, VF) : ScalarOpTy;
    Instruction *CtxI = dyn_cast_or_null<Instruction>(getUnderlyingValue());
    return Ctx.TTI.getCmpSelInstrCost(
        Opcode, OpTy, CmpInst::makeCmpResultType(OpTy), getPredicate(),
        Ctx.CostKind, {TTI::OK_AnyValue, TTI::OP_None},
        {TTI::OK_AnyValue, TTI::OP_None}, CtxI);
  }
  case Instruction::BitCast: {
    Type *ScalarTy = this->getScalarType();
    if (ScalarTy->isPointerTy())
      return 0;
    [[fallthrough]];
  }
  case Instruction::SExt:
  case Instruction::ZExt:
  case Instruction::FPToUI:
  case Instruction::FPToSI:
  case Instruction::FPExt:
  case Instruction::PtrToInt:
  case Instruction::PtrToAddr:
  case Instruction::IntToPtr:
  case Instruction::SIToFP:
  case Instruction::UIToFP:
  case Instruction::Trunc:
  case Instruction::FPTrunc:
  case Instruction::AddrSpaceCast: {
    // Computes the CastContextHint from a recipe that may access memory.
    auto ComputeCCH = [&](const VPRecipeBase *R) -> TTI::CastContextHint {
      if (isa<VPInterleaveBase>(R))
        return TTI::CastContextHint::Interleave;
      if (const auto *ReplicateRecipe = dyn_cast<VPReplicateRecipe>(R)) {
        // Only compute CCH for memory operations, matching the legacy model
        // which only considers loads/stores for cast context hints.
        auto *UI = cast<Instruction>(ReplicateRecipe->getUnderlyingValue());
        if (!isa<LoadInst, StoreInst>(UI))
          return TTI::CastContextHint::None;
        return ReplicateRecipe->isPredicated() ? TTI::CastContextHint::Masked
                                               : TTI::CastContextHint::Normal;
      }
      const auto *WidenMemoryRecipe = dyn_cast<VPWidenMemoryRecipe>(R);
      if (WidenMemoryRecipe == nullptr)
        return TTI::CastContextHint::None;
      if (VF.isScalar())
        return TTI::CastContextHint::Normal;
      if (!WidenMemoryRecipe->isConsecutive())
        return TTI::CastContextHint::GatherScatter;
      if (WidenMemoryRecipe->isMasked())
        return TTI::CastContextHint::Masked;
      return TTI::CastContextHint::Normal;
    };

    VPValue *Operand = getOperand(0);
    TTI::CastContextHint CCH = TTI::CastContextHint::None;
    bool IsReverse = false;
    // For Trunc/FPTrunc, get the context from the only user.
    if (Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) {
      if (auto *Recipe = cast_or_null<VPRecipeBase>(getSingleUser())) {
        if (match(Recipe,
                  m_CombineOr(
                      m_Reverse(m_VPValue()),
                      m_Intrinsic<Intrinsic::experimental_vp_reverse>()))) {
          IsReverse = true;
          Recipe = cast_or_null<VPRecipeBase>(
              Recipe->getVPSingleValue()->getSingleUser());
        }
        if (Recipe)
          CCH = ComputeCCH(Recipe);
      }
    }
    // For Z/Sext, get the context from the operand.
    else if (Opcode == Instruction::ZExt || Opcode == Instruction::SExt ||
             Opcode == Instruction::FPExt) {
      if (auto *Recipe = Operand->getDefiningRecipe()) {
        VPValue *ReverseOp;
        if (match(Recipe,
                  m_CombineOr(m_Reverse(m_VPValue(ReverseOp)),
                              m_Intrinsic<Intrinsic::experimental_vp_reverse>(
                                  m_VPValue(ReverseOp))))) {
          Recipe = ReverseOp->getDefiningRecipe();
          IsReverse = true;
        }
        if (Recipe)
          CCH = ComputeCCH(Recipe);
      }
    }
    if (IsReverse && CCH != TTI::CastContextHint::None)
      CCH = TTI::CastContextHint::Reversed;

    auto *ScalarSrcTy = Operand->getScalarType();
    Type *SrcTy = VF.isVector() ? toVectorTy(ScalarSrcTy, VF) : ScalarSrcTy;
    // Arm TTI will use the underlying instruction to determine the cost.
    return Ctx.TTI.getCastInstrCost(
        Opcode, ResultTy, SrcTy, CCH, Ctx.CostKind,
        dyn_cast_if_present<Instruction>(getUnderlyingValue()));
  }
  case Instruction::Select: {
    SelectInst *SI = cast_or_null<SelectInst>(getUnderlyingValue());
    bool IsScalarCond = getOperand(0)->isDefinedOutsideLoopRegions();
    Type *ScalarTy = this->getScalarType();

    VPValue *Op0, *Op1;
    bool IsLogicalAnd =
        match(this, m_c_LogicalAnd(m_VPValue(Op0), m_VPValue(Op1)));
    bool IsLogicalOr =
        match(this, m_c_LogicalOr(m_VPValue(Op0), m_VPValue(Op1)));
    // Also match the inverted forms:
    // select x, false, y --> !x & y (still AND)
    // select x, y, true --> !x | y (still OR)
    IsLogicalAnd |=
        match(this, m_Select(m_VPValue(Op0), m_False(), m_VPValue(Op1)));
    IsLogicalOr |=
        match(this, m_Select(m_VPValue(Op0), m_VPValue(Op1), m_True()));

    if (!IsScalarCond && ScalarTy->getScalarSizeInBits() == 1 &&
        (IsLogicalAnd || IsLogicalOr)) {
      // select x, y, false --> x & y
      // select x, true, y --> x | y
      const auto [Op1VK, Op1VP] = Ctx.getOperandInfo(Op0);
      const auto [Op2VK, Op2VP] = Ctx.getOperandInfo(Op1);

      SmallVector<const Value *, 2> Operands;
      if (SI && all_of(operands(),
                       [](VPValue *Op) { return Op->getUnderlyingValue(); }))
        append_range(Operands, SI->operands());
      return Ctx.TTI.getArithmeticInstrCost(
          IsLogicalOr ? Instruction::Or : Instruction::And, ResultTy,
          Ctx.CostKind, {Op1VK, Op1VP}, {Op2VK, Op2VP}, Operands, SI);
    }

    Type *CondTy = getOperand(0)->getScalarType();
    if (!IsScalarCond && VF.isVector())
      CondTy = VectorType::get(CondTy, VF);

    llvm::CmpPredicate Pred;
    if (!match(getOperand(0), m_Cmp(Pred, m_VPValue(), m_VPValue())))
      if (auto *CondIRV = dyn_cast<VPIRValue>(getOperand(0)))
        if (auto *Cmp = dyn_cast<CmpInst>(CondIRV->getValue()))
          Pred = Cmp->getPredicate();
    Type *VectorTy = toVectorTy(this->getScalarType(), VF);
    return Ctx.TTI.getCmpSelInstrCost(
        Instruction::Select, VectorTy, CondTy, Pred, Ctx.CostKind,
        {TTI::OK_AnyValue, TTI::OP_None}, {TTI::OK_AnyValue, TTI::OP_None}, SI);
  }
  }
  llvm_unreachable("called for unsupported opcode");
}

InstructionCost VPInstruction::computeCost(ElementCount VF,
                                           VPCostContext &Ctx) const {
  if (Instruction::isBinaryOp(getOpcode())) {
    if (!getUnderlyingValue() && getOpcode() != Instruction::FMul) {
      // TODO: Compute cost for VPInstructions without underlying values once
      // the legacy cost model has been retired.
      return 0;
    }

    assert(!doesGeneratePerAllLanes() &&
           "Should only generate a vector value or single scalar, not scalars "
           "for all lanes.");
    return getCostForRecipeWithOpcode(
        getOpcode(),
        vputils::onlyFirstLaneUsed(this) ? ElementCount::getFixed(1) : VF, Ctx);
  }

  switch (getOpcode()) {
  case Instruction::Select: {
    llvm::CmpPredicate Pred = CmpInst::BAD_ICMP_PREDICATE;
    match(getOperand(0), m_Cmp(Pred, m_VPValue(), m_VPValue()));
    auto *CondTy = getOperand(0)->getScalarType();
    auto *VecTy = getOperand(1)->getScalarType();
    if (!vputils::onlyFirstLaneUsed(this)) {
      CondTy = toVectorTy(CondTy, VF);
      VecTy = toVectorTy(VecTy, VF);
    }
    return Ctx.TTI.getCmpSelInstrCost(Instruction::Select, VecTy, CondTy, Pred,
                                      Ctx.CostKind);
  }
  case Instruction::ExtractElement:
  case VPInstruction::ExtractLane: {
    if (VF.isScalar()) {
      // ExtractLane with VF=1 takes care of handling extracting across multiple
      // parts.
      return 0;
    }

    // Add on the cost of extracting the element.
    auto *VecTy = toVectorTy(getOperand(0)->getScalarType(), VF);
    return Ctx.TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy,
                                      Ctx.CostKind);
  }
  case VPInstruction::AnyOf: {
    auto *VecTy = toVectorTy(this->getScalarType(), VF);
    return Ctx.TTI.getArithmeticReductionCost(
        Instruction::Or, cast<VectorType>(VecTy), std::nullopt, Ctx.CostKind);
  }
  case VPInstruction::FirstActiveLane: {
    Type *Ty = this->getScalarType();
    Type *ScalarTy = getOperand(0)->getScalarType();
    if (VF.isScalar())
      return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ScalarTy,
                                        CmpInst::makeCmpResultType(ScalarTy),
                                        CmpInst::ICMP_EQ, Ctx.CostKind);
    // Calculate the cost of determining the lane index.
    auto *PredTy = toVectorTy(ScalarTy, VF);
    IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
                                  {PredTy, Type::getInt1Ty(Ctx.LLVMCtx)});
    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
  }
  case VPInstruction::LastActiveLane: {
    Type *Ty = this->getScalarType();
    Type *ScalarTy = getOperand(0)->getScalarType();
    if (VF.isScalar())
      return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ScalarTy,
                                        CmpInst::makeCmpResultType(ScalarTy),
                                        CmpInst::ICMP_EQ, Ctx.CostKind);
    // Calculate the cost of determining the lane index: NOT + cttz_elts + SUB.
    auto *PredTy = toVectorTy(ScalarTy, VF);
    IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
                                  {PredTy, Type::getInt1Ty(Ctx.LLVMCtx)});
    InstructionCost Cost = Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
    // Add cost of NOT operation on the predicate.
    Cost += Ctx.TTI.getArithmeticInstrCost(
        Instruction::Xor, PredTy, Ctx.CostKind,
        {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
        {TargetTransformInfo::OK_UniformConstantValue,
         TargetTransformInfo::OP_None});
    // Add cost of SUB operation on the index.
    Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::Sub, Ty, Ctx.CostKind);
    return Cost;
  }
  case VPInstruction::ExtractLastActive: {
    Type *ScalarTy = this->getScalarType();
    Type *VecTy = toVectorTy(ScalarTy, VF);
    Type *MaskTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF);
    IntrinsicCostAttributes ICA(
        Intrinsic::experimental_vector_extract_last_active, ScalarTy,
        {VecTy, MaskTy, ScalarTy});
    return Ctx.TTI.getIntrinsicInstrCost(ICA, Ctx.CostKind);
  }
  case VPInstruction::FirstOrderRecurrenceSplice: {
    assert(VF.isVector() && "Scalar FirstOrderRecurrenceSplice?");
    Type *VectorTy = toVectorTy(this->getScalarType(), VF);
    return Ctx.TTI.getShuffleCost(
        TargetTransformInfo::SK_Splice, cast<VectorType>(VectorTy),
        cast<VectorType>(VectorTy), Ctx.CostKind, {}, -1);
  }
  case VPInstruction::ActiveLaneMask:
  case VPInstruction::WideActiveLaneMask: {
    Type *ArgTy = getOperand(0)->getScalarType();
    uint64_t Multiplier =
        getOpcode() == VPInstruction::WideActiveLaneMask
            ? cast<VPConstantInt>(getOperand(2))->getZExtValue()
            : 1;
    Type *RetTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF * Multiplier);
    IntrinsicCostAttributes Attrs(Intrinsic::get_active_lane_mask, RetTy,
                                  {ArgTy, ArgTy});
    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
  }
  case VPInstruction::ExplicitVectorLength: {
    Type *Arg0Ty = getOperand(0)->getScalarType();
    Type *I32Ty = Type::getInt32Ty(Ctx.LLVMCtx);
    Type *I1Ty = Type::getInt1Ty(Ctx.LLVMCtx);
    IntrinsicCostAttributes Attrs(Intrinsic::experimental_get_vector_length,
                                  I32Ty, {Arg0Ty, I32Ty, I1Ty});
    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
  }
  case VPInstruction::Reverse: {
    assert(VF.isVector() && "Reverse operation must be vector type");
    Type *EltTy = this->getScalarType();
    // Skip the reverse operation cost for the mask.
    // FIXME: Remove this once redundant mask reverse operations can be
    // eliminated by VPlanTransforms::cse before cost computation.
    if (EltTy->isIntegerTy(1))
      return 0;
    auto *VectorTy = cast<VectorType>(toVectorTy(EltTy, VF));
    return Ctx.TTI.getShuffleCost(TargetTransformInfo::SK_Reverse, VectorTy,
                                  VectorTy, Ctx.CostKind, /*Mask=*/{},
                                  /*Index=*/0);
  }
  case VPInstruction::ExtractLastLane: {
    // Add on the cost of extracting the element.
    auto *VecTy = toVectorTy(getOperand(0)->getScalarType(), VF);
    return Ctx.TTI.getIndexedVectorInstrCostFromEnd(Instruction::ExtractElement,
                                                    VecTy, Ctx.CostKind, 0);
  }
  case VPInstruction::Not: {
    Type *ValTy = this->getScalarType();
    // InstCombine will fold `xor` to the conditional branch.
    if (auto *U = const_cast<VPUser *>(getSingleUser()))
      if (match(U, m_BranchOnCond(m_VPValue())))
        return 0;
    if (!vputils::onlyFirstLaneUsed(this))
      ValTy = toVectorTy(ValTy, VF);
    return Ctx.TTI.getArithmeticInstrCost(Instruction::Xor, ValTy,
                                          Ctx.CostKind);
  }
  case VPInstruction::BranchOnCount: {
    // If TC <= VF then this is just a branch.
    // FIXME: Removing the branch happens in simplifyBranchConditionForVFAndUF
    // where it checks TC <= VF * UF, but we don't know UF yet. This means in
    // some cases we get a cost that's too high due to counting a cmp that
    // later gets removed.
    // FIXME: The compare could also be removed if TC = M * vscale,
    // VF = N * vscale, and M <= N. Detecting that would require having the
    // trip count as a SCEV though.
    Value *TC = getParent()->getPlan()->getTripCount()->getUnderlyingValue();
    ConstantInt *TCConst = dyn_cast_if_present<ConstantInt>(TC);
    if (TCConst && TCConst->getValue().ule(VF.getKnownMinValue()))
      return 0;
    // Otherwise BranchOnCount generates ICmpEQ followed by a branch.
    Type *ValTy = getOperand(0)->getScalarType();
    return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ValTy,
                                      CmpInst::makeCmpResultType(ValTy),
                                      CmpInst::ICMP_EQ, Ctx.CostKind);
  }
  case Instruction::FCmp:
  case Instruction::ICmp:
    return getCostForRecipeWithOpcode(
        getOpcode(),
        vputils::onlyFirstLaneUsed(this) ? ElementCount::getFixed(1) : VF, Ctx);
  case VPInstruction::ExtractPenultimateElement:
    if (VF == ElementCount::getScalable(1))
      return InstructionCost::getInvalid();
    [[fallthrough]];
  default:
    // TODO: Compute cost other VPInstructions once the legacy cost model has
    // been retired.
    assert(!getUnderlyingValue() &&
           "unexpected VPInstruction witht underlying value");
    return 0;
  }
}

bool VPInstruction::isVectorToScalar() const {
  return getOpcode() == VPInstruction::ExtractLastLane ||
         getOpcode() == VPInstruction::ExtractPenultimateElement ||
         getOpcode() == Instruction::ExtractElement ||
         getOpcode() == VPInstruction::ExtractLane ||
         getOpcode() == VPInstruction::FirstActiveLane ||
         getOpcode() == VPInstruction::LastActiveLane ||
         getOpcode() == VPInstruction::ExtractLastActive ||
         getOpcode() == VPInstruction::ComputeReductionResult ||
         getOpcode() == VPInstruction::AnyOf ||
         getOpcode() == VPInstruction::NumActiveLanes;
}

bool VPInstruction::isSingleScalar() const {
  switch (getOpcode()) {
  case Instruction::Load:
  case Instruction::PHI:
  case VPInstruction::ExplicitVectorLength:
  case VPInstruction::ResumeForEpilogue:
  case VPInstruction::Intrinsic:
    return true;
  default:
    return Instruction::isCast(getOpcode());
  }
}

void VPInstruction::addOperand(VPValue *Op) {
#ifndef NDEBUG
  Type *Ty = Op->getScalarType();
  switch (getOpcode()) {
  case VPInstruction::AnyOf:
  case VPInstruction::FirstActiveLane:
  case VPInstruction::LastActiveLane:
    assert(Ty == getOperand(0)->getScalarType() &&
           "types of operand 0 and new operand must match");
    break;
  case VPInstruction::ComputeReductionResult:
  case VPInstruction::BuildVector:
  case VPInstruction::BuildStructVector:
    assert(Ty == getOperand(0)->getScalarType() &&
           "appended operand must match operand 0's scalar type");
    break;
  case VPInstruction::ExtractLane:
    assert(Ty == getOperand(1)->getScalarType() &&
           "appended operand must match operand 1's scalar type");
    break;
  case VPInstruction::ExtractLastActive: {
    // The recipe is constructed with 3 operands (result, data, mask). Extra
    // operands beyond that are appended in (data, mask) pairs.
    constexpr unsigned NumInitialOperands = 3;
    assert(getNumOperands() >= NumInitialOperands &&
           "ExtractLastActive must have at least the initial 3 operands");
    bool IsMaskSlot = ((getNumOperands() - NumInitialOperands) & 1u) == 1u;
    assert((IsMaskSlot ? Ty->isIntegerTy(1)
                       : Ty == getOperand(1)->getScalarType()) &&
           "ExtractLastActive expects alternating data/mask operands "
           "matching operand 1's type and i1, respectively");
    break;
  }
  default:
    llvm_unreachable("opcode does not support growing the operand list "
                     "outside of construction");
  }
#endif
  VPUser::addOperand(Op);
}

void VPInstruction::execute(VPTransformState &State) {
  assert(!isMasked() && "cannot execute masked VPInstruction");
  IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
  assert(flagsValidForOpcode(getOpcode()) &&
         "Set flags not supported for the provided opcode");
  assert(hasRequiredFlagsForOpcode(getOpcode(), getScalarType()) &&
         "Opcode requires specific flags to be set");
  State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
  Value *GeneratedValue = generate(State);
  if (!hasResult())
    return;
  assert(GeneratedValue && "generate must produce a value");
  bool GeneratesPerFirstLaneOnly = canGenerateScalarForFirstLane() &&
                                   (vputils::onlyFirstLaneUsed(this) ||
                                    isVectorToScalar() || isSingleScalar());
  assert((((GeneratedValue->getType()->isVectorTy() ||
            GeneratedValue->getType()->isStructTy()) ==
           !GeneratesPerFirstLaneOnly) ||
          State.VF.isScalar()) &&
         "scalar value but not only first lane defined");
  State.set(this, GeneratedValue,
            /*IsScalar*/ GeneratesPerFirstLaneOnly);
  if (getOpcode() == VPInstruction::ResumeForEpilogue ||
      getOpcode() == Instruction::Freeze) {
    // FIXME: This is a workaround to enable reliable updates of the scalar loop
    // resume phis, and to let epilogue vectorization recover the frozen
    // reduction start from the main plan. Must be removed once epilogue
    // vectorization explicitly connects VPlans.
    setUnderlyingValue(GeneratedValue);
  }
}

bool VPInstruction::opcodeMayReadOrWriteFromMemory() const {
  if (Instruction::isBinaryOp(getOpcode()) ||
      Instruction::isUnaryOp(getOpcode()) || Instruction::isCast(getOpcode()))
    return false;
  switch (getOpcode()) {
  case Instruction::ExtractValue:
  case Instruction::InsertValue:
  case Instruction::GetElementPtr:
  case Instruction::ExtractElement:
  case Instruction::InsertElement:
  case Instruction::Freeze:
  case Instruction::FCmp:
  case Instruction::ICmp:
  case Instruction::Select:
  case Instruction::PHI:
  case VPInstruction::AnyOf:
  case VPInstruction::BranchOnCond:
  case VPInstruction::BranchOnTwoConds:
  case VPInstruction::BranchOnCount:
  case VPInstruction::Broadcast:
  case VPInstruction::BuildStructVector:
  case VPInstruction::BuildVector:
  case VPInstruction::CanonicalIVIncrementForPart:
  case VPInstruction::ComputeReductionResult:
  case VPInstruction::ExtractLane:
  case VPInstruction::ExtractLastLane:
  case VPInstruction::ExtractLastPart:
  case VPInstruction::ExtractPenultimateElement:
  case VPInstruction::ActiveLaneMask:
  case VPInstruction::WideActiveLaneMask:
  case VPInstruction::IncomingAliasMask:
  case VPInstruction::ExitingIVValue:
  case VPInstruction::ExplicitVectorLength:
  case VPInstruction::FirstActiveLane:
  case VPInstruction::LastActiveLane:
  case VPInstruction::ExtractLastActive:
  case VPInstruction::ExtractVectorForPart:
  case VPInstruction::FirstOrderRecurrenceSplice:
  case VPInstruction::LogicalAnd:
  case VPInstruction::LogicalOr:
  case VPInstruction::MaskedCond:
  case VPInstruction::Not:
  case VPInstruction::PtrAdd:
  case VPInstruction::WideIVStep:
  case VPInstruction::WidePtrAdd:
  case VPInstruction::StepVector:
  case VPInstruction::ReductionStartVector:
  case VPInstruction::Reverse:
  case VPInstruction::Unpack:
    return false;
  case VPInstruction::Intrinsic: {
    LLVMContext &Ctx = getScalarType()->getContext();
    AttributeSet Attrs =
        Intrinsic::getFnAttributes(Ctx, vputils::getIntrinsicID(this));
    return !Attrs.getMemoryEffects().doesNotAccessMemory();
  }
  case Instruction::Call:
    return !getCalledFunction(operands())->doesNotAccessMemory();
  default:
    return true;
  }
}

bool VPInstruction::usesFirstLaneOnly(const VPValue *Op) const {
  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
  if (Instruction::isBinaryOp(getOpcode()) || Instruction::isCast(getOpcode()))
    return vputils::onlyFirstLaneUsed(this);

  switch (getOpcode()) {
  default:
    return false;
  case Instruction::ExtractElement:
    return Op == getOperand(1);
  case Instruction::InsertElement:
    return Op == getOperand(1) || Op == getOperand(2);
  case Instruction::PHI:
    return true;
  case Instruction::FCmp:
  case Instruction::ICmp:
  case Instruction::Select:
  case Instruction::Or:
  case Instruction::Freeze:
  case VPInstruction::Not:
    // TODO: Cover additional opcodes.
    return vputils::onlyFirstLaneUsed(this);
  case Instruction::Load:
  case VPInstruction::ActiveLaneMask:
  case VPInstruction::WideActiveLaneMask:
  case VPInstruction::ExplicitVectorLength:
  case VPInstruction::CanonicalIVIncrementForPart:
  case VPInstruction::BranchOnCount:
  case VPInstruction::BranchOnCond:
  case VPInstruction::BranchOnTwoConds:
  case VPInstruction::Broadcast:
  case VPInstruction::Intrinsic:
  case VPInstruction::ReductionStartVector:
  case VPInstruction::ResumeForEpilogue:
    return true;
  case VPInstruction::BuildStructVector:
  case VPInstruction::BuildVector:
    // Before replicating by VF, Build(Struct)Vector uses all lanes of the
    // operand, after replicating its operands only the first lane is used.
    // Before replicating, it will have only a single operand.
    return getNumOperands() > 1;
  case VPInstruction::PtrAdd:
    return Op == getOperand(0) || vputils::onlyFirstLaneUsed(this);
  case VPInstruction::WidePtrAdd:
    // WidePtrAdd supports scalar and vector base addresses.
    return false;
  case VPInstruction::ExitingIVValue:
  case VPInstruction::ExtractLane:
    return Op == getOperand(0);
  };
  llvm_unreachable("switch should return");
}

bool VPInstruction::usesFirstPartOnly(const VPValue *Op) const {
  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
  if (Instruction::isBinaryOp(getOpcode()))
    return vputils::onlyFirstPartUsed(this);

  switch (getOpcode()) {
  default:
    return false;
  case Instruction::FCmp:
  case Instruction::ICmp:
  case Instruction::Select:
    return vputils::onlyFirstPartUsed(this);
  case VPInstruction::BranchOnCount:
  case VPInstruction::BranchOnCond:
  case VPInstruction::BranchOnTwoConds:
  case VPInstruction::CanonicalIVIncrementForPart:
    return true;
  };
  llvm_unreachable("switch should return");
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPInstruction::dump() const {
  VPSlotTracker SlotTracker(getParent()->getPlan());
  printRecipe(dbgs(), "", SlotTracker);
}

void VPInstruction::printRecipe(raw_ostream &O, const Twine &Indent,
                                VPSlotTracker &SlotTracker) const {
  O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";

  if (hasResult()) {
    printAsOperand(O, SlotTracker);
    O << " = ";
  }

  switch (getOpcode()) {
  case VPInstruction::Not:
    O << "not";
    break;
  case VPInstruction::ActiveLaneMask:
    O << "active lane mask";
    break;
  case VPInstruction::WideActiveLaneMask:
    O << "wide active lane mask";
    break;
  case VPInstruction::IncomingAliasMask:
    O << "incoming-alias-mask";
    break;
  case VPInstruction::ExplicitVectorLength:
    O << "EXPLICIT-VECTOR-LENGTH";
    break;
  case VPInstruction::FirstOrderRecurrenceSplice:
    O << "first-order splice";
    break;
  case VPInstruction::BranchOnCond:
    O << "branch-on-cond";
    break;
  case VPInstruction::BranchOnTwoConds:
    O << "branch-on-two-conds";
    break;
  case VPInstruction::CanonicalIVIncrementForPart:
    O << "VF * Part +";
    break;
  case VPInstruction::BranchOnCount:
    O << "branch-on-count";
    break;
  case VPInstruction::Broadcast:
    O << "broadcast";
    break;
  case VPInstruction::BuildStructVector:
    O << "buildstructvector";
    break;
  case VPInstruction::BuildVector:
    O << "buildvector";
    break;
  case VPInstruction::ExitingIVValue:
    O << "exiting-iv-value";
    break;
  case VPInstruction::MaskedCond:
    O << "masked-cond";
    break;
  case VPInstruction::ExtractLane:
    O << "extract-lane";
    break;
  case VPInstruction::ExtractLastLane:
    O << "extract-last-lane";
    break;
  case VPInstruction::ExtractLastPart:
    O << "extract-last-part";
    break;
  case VPInstruction::ExtractPenultimateElement:
    O << "extract-penultimate-element";
    break;
  case VPInstruction::ExtractVectorForPart:
    O << "extract-vector-for-part";
    break;
  case VPInstruction::ComputeReductionResult:
    O << "compute-reduction-result";
    break;
  case VPInstruction::LogicalAnd:
    O << "logical-and";
    break;
  case VPInstruction::LogicalOr:
    O << "logical-or";
    break;
  case VPInstruction::PtrAdd:
    O << "ptradd";
    break;
  case VPInstruction::WidePtrAdd:
    O << "wide-ptradd";
    break;
  case VPInstruction::AnyOf:
    O << "any-of";
    break;
  case VPInstruction::FirstActiveLane:
    O << "first-active-lane";
    break;
  case VPInstruction::LastActiveLane:
    O << "last-active-lane";
    break;
  case VPInstruction::ReductionStartVector:
    O << "reduction-start-vector";
    break;
  case VPInstruction::ResumeForEpilogue:
    O << "resume-for-epilogue";
    break;
  case VPInstruction::Reverse:
    O << "reverse";
    break;
  case VPInstruction::Unpack:
    O << "unpack";
    break;
  case VPInstruction::ExtractLastActive:
    O << "extract-last-active";
    break;
  case VPInstruction::NumActiveLanes:
    O << "num-active-lanes";
    break;
  default:
    O << Instruction::getOpcodeName(getOpcode());
  }

  printFlags(O);
  printOperands(O, SlotTracker);
}
#endif

void VPInstructionWithType::execute(VPTransformState &State) {
  Type *ResultTy = getResultType();
  if (Instruction::isCast(getOpcode())) {
    Value *Op = State.get(getOperand(0), VPLane(0));
    Value *Cast = State.Builder.CreateCast(Instruction::CastOps(getOpcode()),
                                           Op, ResultTy);
    if (auto *CastOp = dyn_cast<Instruction>(Cast)) {
      applyFlags(*CastOp);
      applyMetadata(*CastOp);
    }
    State.set(this, Cast, VPLane(0));
    return;
  }
  switch (getOpcode()) {
  case VPInstruction::StepVector: {
    Value *StepVector =
        State.Builder.CreateStepVector(VectorType::get(ResultTy, State.VF));
    State.set(this, StepVector);
    break;
  }
  case VPInstruction::Intrinsic: {
    SmallVector<Value *, 2> Args;
    for (VPValue *Op : drop_end(operands()))
      Args.push_back(State.get(Op, /*IsSingleScalar=*/true));
    Value *Call =
        State.Builder.CreateIntrinsic(ResultTy, vputils::getIntrinsicID(this),
                                      Args, /*FMFSource=*/nullptr, getName());
    State.set(this, Call, true);
    break;
  }

  default:
    llvm_unreachable("opcode not implemented yet");
  }
}

InstructionCost VPInstructionWithType::computeCost(ElementCount VF,
                                                   VPCostContext &Ctx) const {
  // NOTE: At the moment it seems only possible to expose this path for
  // the trunc, zext and sext opcodes. However, isScalarCast also covers
  // int<>fp conversions, bitcasts, ptr<>int conversions, etc.
  if (Instruction::isCast(getOpcode()))
    return getCostForRecipeWithOpcode(getOpcode(), ElementCount::getFixed(1),
                                      Ctx);

  switch (getOpcode()) {
  case VPInstruction::StepVector:
    // TODO: This isn't quite right since even if the step-vector is hoisted
    // out of the loop it has a non-zero cost in the middle block, etc.
    // Once the stepvector is correctly hoisted out of the vector loop by the
    // licm transform we can add the cost here so that it doesn't incorrectly
    // affect the choice of VF.
    return 0;
  case VPInstruction::Intrinsic: {
    Type *Ty = getScalarType();
    SmallVector<Type *, 2> ArgTys;
    for (const VPValue *Op : drop_end(operands()))
      ArgTys.push_back(Op->getScalarType());
    IntrinsicCostAttributes Attrs(vputils::getIntrinsicID(this), Ty, ArgTys);
    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
  }
  default:
    // Although VPInstructionWithType is also used for
    // VPInstruction::WideIVStep it isn't currently possible to expose cases
    // where the cost is queried.
    llvm_unreachable("Unhandled opcode");
  }
  return 0;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPInstructionWithType::printRecipe(raw_ostream &O, const Twine &Indent,
                                        VPSlotTracker &SlotTracker) const {
  O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
  printAsOperand(O, SlotTracker);
  O << " = ";

  Type *ResultTy = getResultType();
  switch (getOpcode()) {
  case VPInstruction::WideIVStep:
    O << "wide-iv-step ";
    printOperands(O, SlotTracker);
    break;
  case VPInstruction::StepVector:
    O << "step-vector " << *ResultTy;
    break;
  case VPInstruction::Intrinsic: {
    O << "call " << *ResultTy << " @"
      << Intrinsic::getBaseName(vputils::getIntrinsicID(this)) << "(";
    interleaveComma(drop_end(operands()), O, [&O, &SlotTracker](VPValue *Op) {
      Op->printAsOperand(O, SlotTracker);
    });
    O << ")";
    break;
  }
  case Instruction::Load:
    O << "load ";
    printOperands(O, SlotTracker);
    break;
  default:
    assert(Instruction::isCast(getOpcode()) && "unhandled opcode");
    O << Instruction::getOpcodeName(getOpcode());
    printFlags(O);
    printOperands(O, SlotTracker);
    O << " to " << *ResultTy;
  }
}
#endif

/// Shared execute logic for VPPhi and VPWidenPHIRecipe. Creates a PHI node,
/// adds incoming values, and stores the result in State. For header phis, only
/// the preheader incoming value is added; the backedge is fixed up later by
/// VPlan::execute().
static void executePhiRecipe(VPSingleDefRecipe *R, VPPhiAccessors &Phi,
                             VPTransformState &State, bool IsScalar,
                             const Twine &Name) {
  unsigned NumIncoming = VPBlockUtils::isHeader(R->getParent(), State.VPDT)
                             ? 1
                             : Phi.getNumIncoming();
  Value *FirstInc = State.get(Phi.getIncomingValue(0), IsScalar);
  PHINode *NewPhi = State.Builder.CreatePHI(FirstInc->getType(), 2, Name);
  NewPhi->addIncoming(FirstInc,
                      State.CFG.VPBB2IRBB.at(Phi.getIncomingBlock(0)));
  for (unsigned Idx = 1; Idx != NumIncoming; ++Idx)
    NewPhi->addIncoming(State.get(Phi.getIncomingValue(Idx), IsScalar),
                        State.CFG.VPBB2IRBB.at(Phi.getIncomingBlock(Idx)));
  State.set(R, NewPhi, IsScalar);
}

void VPPhi::execute(VPTransformState &State) {
  executePhiRecipe(this, *this, State, /*IsScalar=*/true, getName());
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPPhi::printRecipe(raw_ostream &O, const Twine &Indent,
                        VPSlotTracker &SlotTracker) const {
  O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
  printAsOperand(O, SlotTracker);
  O << " = phi";
  printFlags(O);
  printPhiOperands(O, SlotTracker);
}
#endif

VPIRInstruction *VPIRInstruction ::create(Instruction &I) {
  if (auto *Phi = dyn_cast<PHINode>(&I))
    return new VPIRPhi(*Phi);
  return new VPIRInstruction(I);
}

void VPIRInstruction::execute(VPTransformState &State) {
  assert(!isa<VPIRPhi>(this) && getNumOperands() == 0 &&
         "PHINodes must be handled by VPIRPhi");
  // Advance the insert point after the wrapped IR instruction. This allows
  // interleaving VPIRInstructions and other recipes.
  State.Builder.SetInsertPoint(I.getParent(), std::next(I.getIterator()));
}

InstructionCost VPIRInstruction::computeCost(ElementCount VF,
                                             VPCostContext &Ctx) const {
  // The recipe wraps an existing IR instruction on the border of VPlan's scope,
  // hence it does not contribute to the cost-modeling for the VPlan.
  return 0;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPIRInstruction::printRecipe(raw_ostream &O, const Twine &Indent,
                                  VPSlotTracker &SlotTracker) const {
  O << Indent << "IR " << I;
}
#endif

void VPIRPhi::execute(VPTransformState &State) {
  PHINode *Phi = &getIRPhi();
  for (const auto &[Idx, Op] : enumerate(operands())) {
    VPValue *ExitValue = Op;
    auto Lane = vputils::isSingleScalar(ExitValue)
                    ? VPLane::getFirstLane()
                    : VPLane::getLastLaneForVF(State.VF);
    VPBlockBase *Pred = getParent()->getPredecessors()[Idx];
    auto *PredVPBB = Pred->getExitingBasicBlock();
    BasicBlock *PredBB = State.CFG.VPBB2IRBB[PredVPBB];
    // Set insertion point in PredBB in case an extract needs to be generated.
    // TODO: Model extracts explicitly.
    State.Builder.SetInsertPoint(PredBB->getTerminator());
    Value *V = State.get(ExitValue, VPLane(Lane));
    // If there is no existing block for PredBB in the phi, add a new incoming
    // value. Otherwise update the existing incoming value for PredBB.
    if (Phi->getBasicBlockIndex(PredBB) == -1)
      Phi->addIncoming(V, PredBB);
    else
      Phi->setIncomingValueForBlock(PredBB, V);
  }

  // Advance the insert point after the wrapped IR instruction. This allows
  // interleaving VPIRInstructions and other recipes.
  State.Builder.SetInsertPoint(Phi->getParent(), std::next(Phi->getIterator()));
}

void VPPhiAccessors::removeIncomingValueFor(VPBlockBase *IncomingBlock) const {
  VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
  assert(R->getNumOperands() == R->getParent()->getNumPredecessors() &&
         "Number of phi operands must match number of predecessors");
  unsigned Position = R->getParent()->getIndexForPredecessor(IncomingBlock);
  R->removeOperand(Position);
}

VPValue *
VPPhiAccessors::getIncomingValueForBlock(const VPBasicBlock *VPBB) const {
  VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
  return getIncomingValue(R->getParent()->getIndexForPredecessor(VPBB));
}

void VPPhiAccessors::setIncomingValueForBlock(const VPBasicBlock *VPBB,
                                              VPValue *V) const {
  VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
  R->setOperand(R->getParent()->getIndexForPredecessor(VPBB), V);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPPhiAccessors::printPhiOperands(raw_ostream &O,
                                      VPSlotTracker &SlotTracker) const {
  interleaveComma(incoming_values_and_blocks(), O, [&O, &SlotTracker](auto Op) {
    O << "[ ";
    std::get<0>(Op)->printAsOperand(O, SlotTracker);
    O << ", ";
    std::get<1>(Op)->printAsOperand(O);
    O << " ]";
  });
}
#endif

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPIRPhi::printRecipe(raw_ostream &O, const Twine &Indent,
                          VPSlotTracker &SlotTracker) const {
  VPIRInstruction::printRecipe(O, Indent, SlotTracker);

  if (getNumOperands() != 0) {
    O << " (extra operand" << (getNumOperands() > 1 ? "s" : "") << ": ";
    interleaveComma(incoming_values_and_blocks(), O,
                    [&O, &SlotTracker](auto Op) {
                      std::get<0>(Op)->printAsOperand(O, SlotTracker);
                      O << " from ";
                      std::get<1>(Op)->printAsOperand(O);
                    });
    O << ")";
  }
}
#endif

void VPIRMetadata::applyMetadata(Instruction &I) const {
  for (const auto &[Kind, Node] : Metadata)
    I.setMetadata(Kind, Node);
}

void VPIRMetadata::intersect(const VPIRMetadata &Other) {
  SmallVector<std::pair<unsigned, MDNode *>> MetadataIntersection;
  for (const auto &[KindA, MDA] : Metadata) {
    for (const auto &[KindB, MDB] : Other.Metadata) {
      if (KindA == KindB && MDA == MDB) {
        MetadataIntersection.emplace_back(KindA, MDA);
        break;
      }
    }
  }
  Metadata = std::move(MetadataIntersection);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPIRMetadata::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
  const Module *M = SlotTracker.getModule();
  if (Metadata.empty() || !M || !VPlanPrintMetadata)
    return;

  ArrayRef<StringRef> MDNames = SlotTracker.getMDNames();
  O << " (";
  interleaveComma(Metadata, O, [&](const auto &KindNodePair) {
    auto [Kind, Node] = KindNodePair;
    assert(Kind < MDNames.size() && !MDNames[Kind].empty() &&
           "Unexpected unnamed metadata kind");
    O << "!" << MDNames[Kind] << " ";
    Node->printAsOperand(O, M);
  });
  O << ")";
}
#endif

void VPWidenCallRecipe::execute(VPTransformState &State) {
  assert(State.VF.isVector() && "not widening");
  assert(Variant != nullptr && "Can't create vector function.");

  FunctionType *VFTy = Variant->getFunctionType();
  // Add return type if intrinsic is overloaded on it.
  SmallVector<Value *, 4> Args;
  for (const auto &I : enumerate(args())) {
    Value *Arg;
    // Some vectorized function variants may also take a scalar argument,
    // e.g. linear parameters for pointers. This needs to be the scalar value
    // from the start of the respective part when interleaving.
    if (!VFTy->getParamType(I.index())->isVectorTy())
      Arg = State.get(I.value(), VPLane(0));
    else
      Arg = State.get(I.value(), usesFirstLaneOnly(I.value()));
    Args.push_back(Arg);
  }

  auto *CI = cast_or_null<CallInst>(getUnderlyingValue());
  SmallVector<OperandBundleDef, 1> OpBundles;
  if (CI)
    CI->getOperandBundlesAsDefs(OpBundles);

  CallInst *V = State.Builder.CreateCall(Variant, Args, OpBundles);
  applyFlags(*V);
  applyMetadata(*V);
  V->setCallingConv(Variant->getCallingConv());

  if (!V->getType()->isVoidTy())
    State.set(this, V);
}

InstructionCost VPWidenCallRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  assert(getVectorizedTypeVF(Variant->getReturnType()) == VF &&
         "Variant return type must match VF");
  return computeCallCost(Variant, Ctx);
}

InstructionCost VPWidenCallRecipe::computeCallCost(Function *Variant,
                                                   VPCostContext &Ctx) {
  return Ctx.TTI.getCallInstrCost(nullptr, Variant->getReturnType(),
                                  Variant->getFunctionType()->params(),
                                  Ctx.CostKind);
}

bool VPWidenCallRecipe::usesFirstLaneOnly(const VPValue *Op) const {
  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
  assert(Variant && "Variant not set");
  FunctionType *VFTy = Variant->getFunctionType();
  return all_of(enumerate(args()), [VFTy, &Op](const auto &Arg) {
    auto [Idx, V] = Arg;
    Type *ArgTy = VFTy->getParamType(Idx);
    return V != Op || ArgTy->isIntegerTy() || ArgTy->isFloatingPointTy() ||
           ArgTy->isPointerTy() || ArgTy->isByteTy();
  });
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenCallRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-CALL ";

  Function *CalledFn = getCalledScalarFunction();
  if (CalledFn->getReturnType()->isVoidTy())
    O << "void ";
  else {
    printAsOperand(O, SlotTracker);
    O << " = ";
  }

  O << "call";
  printFlags(O);
  O << "@" << CalledFn->getName() << "(";
  interleaveComma(args(), O, [&O, &SlotTracker](VPValue *Op) {
    Op->printAsOperand(O, SlotTracker);
  });
  O << ")";

  O << " (using library function";
  if (Variant->hasName())
    O << ": " << Variant->getName();
  O << ")";
}
#endif

CallInst *VPWidenIntrinsicRecipe::createVectorCall(VPTransformState &State) {
  assert(State.VF.isVector() && "not widening");

  SmallVector<Type *, 2> TysForDecl;
  // Add return type if intrinsic is overloaded on it.
  if (isVectorIntrinsicWithOverloadTypeAtArg(VectorIntrinsicID, -1,
                                             State.TTI)) {
    Type *RetTy = toVectorizedTy(getScalarType(), State.VF);
    ArrayRef<Type *> ContainedTys = getContainedTypes(RetTy);
    for (auto [Idx, Ty] : enumerate(ContainedTys)) {
      if (isVectorIntrinsicWithStructReturnOverloadAtField(VectorIntrinsicID,
                                                           Idx, State.TTI))
        TysForDecl.push_back(Ty);
    }
  }
  SmallVector<Value *, 4> Args;
  for (const auto &I : enumerate(operands())) {
    // Some intrinsics have a scalar argument - don't replace it with a
    // vector.
    Value *Arg;
    if (isVectorIntrinsicWithScalarOpAtArg(VectorIntrinsicID, I.index(),
                                           State.TTI))
      Arg = State.get(I.value(), VPLane(0));
    else
      Arg = State.get(I.value(), usesFirstLaneOnly(I.value()));
    if (isVectorIntrinsicWithOverloadTypeAtArg(VectorIntrinsicID, I.index(),
                                               State.TTI))
      TysForDecl.push_back(Arg->getType());
    Args.push_back(Arg);
  }

  // Use vector version of the intrinsic.
  Module *M = State.Builder.GetInsertBlock()->getModule();
  Function *VectorF =
      Intrinsic::getOrInsertDeclaration(M, VectorIntrinsicID, TysForDecl);
  assert(VectorF &&
         "Can't retrieve vector intrinsic or vector-predication intrinsics.");

  auto *CI = cast_or_null<CallInst>(getUnderlyingValue());
  SmallVector<OperandBundleDef, 1> OpBundles;
  if (CI)
    CI->getOperandBundlesAsDefs(OpBundles);

  CallInst *V = State.Builder.CreateCall(VectorF, Args, OpBundles);

  applyFlags(*V);
  applyMetadata(*V);

  return V;
}

void VPWidenIntrinsicRecipe::execute(VPTransformState &State) {
  CallInst *V = createVectorCall(State);
  if (!V->getType()->isVoidTy())
    State.set(this, V);
}

InstructionCost VPWidenIntrinsicRecipe::computeCallCost(
    Intrinsic::ID ID, ArrayRef<const VPValue *> Operands,
    const VPRecipeWithIRFlags &R, ElementCount VF, VPCostContext &Ctx) {
  Type *ScalarRetTy = R.getScalarType();
  // Skip the reverse operation cost for the mask.
  // FIXME: Remove this once redundant mask reverse operations can be eliminated
  // by VPlanTransforms::cse before cost computation.
  if (ID == Intrinsic::experimental_vp_reverse && ScalarRetTy->isIntegerTy(1))
    return InstructionCost(0);

  // Some backends analyze intrinsic arguments to determine cost. Use the
  // underlying value for the operand if it has one. Otherwise try to use the
  // operand of the underlying call instruction, if there is one. Otherwise
  // clear Arguments.
  // TODO: Rework TTI interface to be independent of concrete IR values.
  SmallVector<const Value *> Arguments;
  for (const auto &[Idx, Op] : enumerate(Operands)) {
    auto *V = Op->getUnderlyingValue();
    if (!V) {
      if (auto *UI = dyn_cast_or_null<CallBase>(R.getUnderlyingValue())) {
        Arguments.push_back(UI->getArgOperand(Idx));
        continue;
      }
      Arguments.clear();
      break;
    }
    Arguments.push_back(V);
  }

  Type *RetTy = VF.isVector() ? toVectorizedTy(ScalarRetTy, VF) : ScalarRetTy;
  SmallVector<Type *> ParamTys =
      map_to_vector(Operands, [&](const VPValue *Op) {
        return toVectorTy(Op->getScalarType(), VF);
      });

  VectorInstrContext VIC = VectorInstrContext::None;
  for (const VPValue *Op : Operands)
    if (isa<VPWidenRecipe>(Op) &&
        Instruction::isBinaryOp(cast<VPWidenRecipe>(Op)->getOpcode())) {
      VIC = VectorInstrContext::BinaryOp;
      break;
    }

  // TODO: Rework TTI interface to avoid reliance on underlying IntrinsicInst.
  IntrinsicCostAttributes CostAttrs(
      ID, RetTy, Arguments, ParamTys, R.getFastMathFlagsOrNone(),
      dyn_cast_or_null<IntrinsicInst>(R.getUnderlyingValue()),
      InstructionCost::getInvalid(), VIC);
  return Ctx.TTI.getIntrinsicInstrCost(CostAttrs, Ctx.CostKind);
}

InstructionCost VPWidenIntrinsicRecipe::computeCost(ElementCount VF,
                                                    VPCostContext &Ctx) const {
  return computeCallCost(VectorIntrinsicID, operands(), *this, VF, Ctx);
}

StringRef VPWidenIntrinsicRecipe::getIntrinsicName() const {
  return Intrinsic::getBaseName(VectorIntrinsicID);
}

bool VPWidenIntrinsicRecipe::usesFirstLaneOnly(const VPValue *Op) const {
  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
  return all_of(enumerate(operands()), [this, &Op](const auto &X) {
    auto [Idx, V] = X;
    return V != Op || isVectorIntrinsicWithScalarOpAtArg(getVectorIntrinsicID(),
                                                         Idx, nullptr);
  });
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenIntrinsicRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                         VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-INTRINSIC ";
  if (getScalarType()->isVoidTy()) {
    O << "void ";
  } else {
    printAsOperand(O, SlotTracker);
    O << " = ";
  }

  O << "call";
  printFlags(O);
  O << getIntrinsicName() << "(";
  printOperands(O, SlotTracker);
  O << ")";
}
#endif

void VPWidenMemIntrinsicRecipe::execute(VPTransformState &State) {
  CallInst *MemI = createVectorCall(State);
  auto PtrPos = VPIntrinsic::getMemoryPointerParamPos(getVectorIntrinsicID());
  assert(PtrPos && "Expected a memory intrinsic with a valid pointer position");
  MemI->addParamAttr(
      *PtrPos, Attribute::getWithAlignment(MemI->getContext(), Alignment));
  if (!MemI->getType()->isVoidTy())
    State.set(this, MemI);
}

InstructionCost VPWidenMemIntrinsicRecipe::computeMemIntrinsicCost(
    Intrinsic::ID IID, Type *Ty, bool IsMasked, Align Alignment,
    VPCostContext &Ctx) {
  return Ctx.TTI.getMemIntrinsicInstrCost(
      MemIntrinsicCostAttributes(IID, Ty, /*Ptr=*/nullptr, IsMasked, Alignment),
      Ctx.CostKind);
}

InstructionCost
VPWidenMemIntrinsicRecipe::computeCost(ElementCount VF,
                                       VPCostContext &Ctx) const {
  Type *DataTy;
  if (auto DataPos = VPIntrinsic::getMemoryDataParamPos(getVectorIntrinsicID()))
    DataTy = getOperand(*DataPos)->getScalarType();
  else
    DataTy = getScalarType();
  assert(!DataTy->isVoidTy() && "Expected a non-void data type");
  Type *Ty = toVectorTy(DataTy, VF);
  auto MaskPos = VPIntrinsic::getMaskParamPos(getVectorIntrinsicID());
  assert(MaskPos && "Expected a memory intrinsic with a valid mask position");
  return computeMemIntrinsicCost(getVectorIntrinsicID(), Ty,
                                 !match(getOperand(*MaskPos), m_True()),
                                 Alignment, Ctx);
}

void VPHistogramRecipe::execute(VPTransformState &State) {
  IRBuilderBase &Builder = State.Builder;

  Value *Address = State.get(getOperand(0));
  Value *IncAmt = State.get(getOperand(1), /*IsScalar=*/true);
  VectorType *VTy = cast<VectorType>(Address->getType());

  // The histogram intrinsic requires a mask even if the recipe doesn't;
  // if the mask operand was omitted then all lanes should be executed and
  // we just need to synthesize an all-true mask.
  Value *Mask = nullptr;
  if (VPValue *VPMask = getMask())
    Mask = State.get(VPMask);
  else
    Mask =
        Builder.CreateVectorSplat(VTy->getElementCount(), Builder.getInt1(1));

  // If this is a subtract, we want to invert the increment amount. We may
  // add a separate intrinsic in future, but for now we'll try this.
  if (Opcode == Instruction::Sub)
    IncAmt = Builder.CreateNeg(IncAmt);
  else
    assert(Opcode == Instruction::Add && "only add or sub supported for now");

  Instruction *HistogramInst = State.Builder.CreateIntrinsicWithoutFolding(
      Intrinsic::experimental_vector_histogram_add, {VTy, IncAmt->getType()},
      {Address, IncAmt, Mask});
  applyMetadata(*HistogramInst);
}

InstructionCost VPHistogramRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  // FIXME: Take the gather and scatter into account as well. For now we're
  //        generating the same cost as the fallback path, but we'll likely
  //        need to create a new TTI method for determining the cost, including
  //        whether we can use base + vec-of-smaller-indices or just
  //        vec-of-pointers.
  assert(VF.isVector() && "Invalid VF for histogram cost");
  Type *AddressTy = getOperand(0)->getScalarType();
  VPValue *IncAmt = getOperand(1);
  Type *IncTy = IncAmt->getScalarType();
  VectorType *VTy = VectorType::get(IncTy, VF);

  // Assume that a non-constant update value (or a constant != 1) requires
  // a multiply, and add that into the cost.
  InstructionCost MulCost =
      Ctx.TTI.getArithmeticInstrCost(Instruction::Mul, VTy, Ctx.CostKind);
  if (match(IncAmt, m_One()))
    MulCost = TTI::TCC_Free;

  // Find the cost of the histogram operation itself.
  Type *PtrTy = VectorType::get(AddressTy, VF);
  Type *MaskTy = VectorType::get(Type::getInt1Ty(Ctx.LLVMCtx), VF);
  IntrinsicCostAttributes ICA(Intrinsic::experimental_vector_histogram_add,
                              Type::getVoidTy(Ctx.LLVMCtx),
                              {PtrTy, IncTy, MaskTy});

  // Add the costs together with the add/sub operation.
  return Ctx.TTI.getIntrinsicInstrCost(ICA, Ctx.CostKind) + MulCost +
         Ctx.TTI.getArithmeticInstrCost(Opcode, VTy, Ctx.CostKind);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPHistogramRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-HISTOGRAM buckets: ";
  getOperand(0)->printAsOperand(O, SlotTracker);

  if (Opcode == Instruction::Sub)
    O << ", dec: ";
  else {
    assert(Opcode == Instruction::Add);
    O << ", inc: ";
  }
  getOperand(1)->printAsOperand(O, SlotTracker);

  if (VPValue *Mask = getMask()) {
    O << ", mask: ";
    Mask->printAsOperand(O, SlotTracker);
  }
}
#endif

VPIRFlags::FastMathFlagsTy::FastMathFlagsTy(const FastMathFlags &FMF) {
  AllowReassoc = FMF.allowReassoc();
  NoNaNs = FMF.noNaNs();
  NoInfs = FMF.noInfs();
  NoSignedZeros = FMF.noSignedZeros();
  AllowReciprocal = FMF.allowReciprocal();
  AllowContract = FMF.allowContract();
  ApproxFunc = FMF.approxFunc();
}

VPIRFlags VPIRFlags::getDefaultFlags(unsigned Opcode, Type *ResultTy) {
  switch (Opcode) {
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::Mul:
  case Instruction::Shl:
  case VPInstruction::CanonicalIVIncrementForPart:
    return WrapFlagsTy(false, false);
  case Instruction::Trunc:
    return TruncFlagsTy(false, false);
  case Instruction::Or:
    return DisjointFlagsTy(false);
  case Instruction::AShr:
  case Instruction::LShr:
  case Instruction::UDiv:
  case Instruction::SDiv:
    return ExactFlagsTy(false);
  case Instruction::GetElementPtr:
  case VPInstruction::PtrAdd:
  case VPInstruction::WidePtrAdd:
    return GEPNoWrapFlags::none();
  case Instruction::ZExt:
  case Instruction::UIToFP:
    return NonNegFlagsTy(false);
  case Instruction::FAdd:
  case Instruction::FSub:
  case Instruction::FMul:
  case Instruction::FDiv:
  case Instruction::FRem:
  case Instruction::FNeg:
  case Instruction::FPExt:
  case Instruction::FPTrunc:
    return FastMathFlags();
  case Instruction::Select:
  case Instruction::PHI:
  case Instruction::Call:
    // Selects, phis and calls only have fast-math flags if they have a
    // supported floating-point result type.
    if (FPMathOperator::isSupportedFloatingPointType(ResultTy))
      return FastMathFlags();
    return VPIRFlags();
  case Instruction::ICmp:
  case Instruction::FCmp:
  case VPInstruction::ComputeReductionResult:
    llvm_unreachable("opcode requires explicit flags");
  default:
    return VPIRFlags();
  }
}

#if !defined(NDEBUG)
bool VPIRFlags::flagsValidForOpcode(unsigned Opcode) const {
  switch (OpType) {
  case OperationType::OverflowingBinOp:
    return Opcode == Instruction::Add || Opcode == Instruction::Sub ||
           Opcode == Instruction::Mul || Opcode == Instruction::Shl ||
           Opcode == VPInstruction::VPInstruction::CanonicalIVIncrementForPart;
  case OperationType::Trunc:
    return Opcode == Instruction::Trunc;
  case OperationType::DisjointOp:
    return Opcode == Instruction::Or;
  case OperationType::PossiblyExactOp:
    return Opcode == Instruction::AShr || Opcode == Instruction::LShr ||
           Opcode == Instruction::UDiv || Opcode == Instruction::SDiv;
  case OperationType::GEPOp:
    return Opcode == Instruction::GetElementPtr ||
           Opcode == VPInstruction::PtrAdd ||
           Opcode == VPInstruction::WidePtrAdd;
  case OperationType::FPMathOp:
    return Opcode == Instruction::Call || Opcode == Instruction::FAdd ||
           Opcode == Instruction::FMul || Opcode == Instruction::FSub ||
           Opcode == Instruction::FNeg || Opcode == Instruction::FDiv ||
           Opcode == Instruction::FRem || Opcode == Instruction::FPExt ||
           Opcode == Instruction::FPTrunc || Opcode == Instruction::PHI ||
           Opcode == Instruction::Select || Opcode == Instruction::SIToFP ||
           Opcode == Instruction::UIToFP ||
           Opcode == VPInstruction::WideIVStep ||
           Opcode == VPInstruction::ReductionStartVector;
  case OperationType::FCmp:
    return Opcode == Instruction::FCmp;
  case OperationType::NonNegOp:
    return Opcode == Instruction::ZExt || Opcode == Instruction::UIToFP;
  case OperationType::Cmp:
    return Opcode == Instruction::FCmp || Opcode == Instruction::ICmp;
  case OperationType::ReductionOp:
    return Opcode == VPInstruction::ComputeReductionResult;
  case OperationType::Other:
    return true;
  }
  llvm_unreachable("Unknown OperationType enum");
}

bool VPIRFlags::hasRequiredFlagsForOpcode(unsigned Opcode,
                                          Type *ResultTy) const {
  // Handle opcodes without default flags.
  if (Opcode == Instruction::ICmp)
    return OpType == OperationType::Cmp;
  if (Opcode == Instruction::FCmp)
    return OpType == OperationType::FCmp;
  if (Opcode == VPInstruction::ComputeReductionResult)
    return OpType == OperationType::ReductionOp;

  OperationType Required = getDefaultFlags(Opcode, ResultTy).OpType;
  return Required == OperationType::Other || Required == OpType;
}
#endif

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
static void printRecurrenceKind(raw_ostream &OS, const RecurKind &Kind) {
  switch (Kind) {
  case RecurKind::None:
    OS << "none";
    break;
  case RecurKind::Add:
    OS << "add";
    break;
  case RecurKind::Sub:
    OS << "sub";
    break;
  case RecurKind::AddChainWithSubs:
    OS << "add-chain-with-subs";
    break;
  case RecurKind::Mul:
    OS << "mul";
    break;
  case RecurKind::Or:
    OS << "or";
    break;
  case RecurKind::And:
    OS << "and";
    break;
  case RecurKind::Xor:
    OS << "xor";
    break;
  case RecurKind::SMin:
    OS << "smin";
    break;
  case RecurKind::SMax:
    OS << "smax";
    break;
  case RecurKind::UMin:
    OS << "umin";
    break;
  case RecurKind::UMax:
    OS << "umax";
    break;
  case RecurKind::FAdd:
    OS << "fadd";
    break;
  case RecurKind::FAddChainWithSubs:
    OS << "fadd-chain-with-subs";
    break;
  case RecurKind::FSub:
    OS << "fsub";
    break;
  case RecurKind::FMul:
    OS << "fmul";
    break;
  case RecurKind::FMin:
    OS << "fmin";
    break;
  case RecurKind::FMax:
    OS << "fmax";
    break;
  case RecurKind::FMinNum:
    OS << "fminnum";
    break;
  case RecurKind::FMaxNum:
    OS << "fmaxnum";
    break;
  case RecurKind::FMinimum:
    OS << "fminimum";
    break;
  case RecurKind::FMaximum:
    OS << "fmaximum";
    break;
  case RecurKind::FMinimumNum:
    OS << "fminimumnum";
    break;
  case RecurKind::FMaximumNum:
    OS << "fmaximumnum";
    break;
  case RecurKind::FMulAdd:
    OS << "fmuladd";
    break;
  case RecurKind::AnyOf:
    OS << "any-of";
    break;
  case RecurKind::FindIV:
    OS << "find-iv";
    break;
  case RecurKind::FindLast:
    OS << "find-last";
    break;
  }
}

void VPIRFlags::printFlags(raw_ostream &O) const {
  switch (OpType) {
  case OperationType::Cmp:
    O << " " << CmpInst::getPredicateName(getPredicate());
    break;
  case OperationType::FCmp:
    O << " " << CmpInst::getPredicateName(getPredicate());
    getFastMathFlagsOrNone().print(O);
    break;
  case OperationType::DisjointOp:
    if (DisjointFlags.IsDisjoint)
      O << " disjoint";
    break;
  case OperationType::PossiblyExactOp:
    if (ExactFlags.IsExact)
      O << " exact";
    break;
  case OperationType::OverflowingBinOp:
    if (WrapFlags.HasNUW)
      O << " nuw";
    if (WrapFlags.HasNSW)
      O << " nsw";
    break;
  case OperationType::Trunc:
    if (TruncFlags.HasNUW)
      O << " nuw";
    if (TruncFlags.HasNSW)
      O << " nsw";
    break;
  case OperationType::FPMathOp:
    getFastMathFlagsOrNone().print(O);
    break;
  case OperationType::GEPOp: {
    GEPNoWrapFlags Flags = getGEPNoWrapFlags();
    if (Flags.isInBounds())
      O << " inbounds";
    else if (Flags.hasNoUnsignedSignedWrap())
      O << " nusw";
    if (Flags.hasNoUnsignedWrap())
      O << " nuw";
    break;
  }
  case OperationType::NonNegOp:
    if (NonNegFlags.NonNeg)
      O << " nneg";
    break;
  case OperationType::ReductionOp: {
    O << " (";
    printRecurrenceKind(O, getRecurKind());
    if (isReductionInLoop())
      O << ", in-loop";
    if (isReductionOrdered())
      O << ", ordered";
    O << ")";
    getFastMathFlagsOrNone().print(O);
    break;
  }
  case OperationType::Other:
    break;
  }
  O << " ";
}
#endif

void VPWidenRecipe::execute(VPTransformState &State) {
  auto &Builder = State.Builder;
  switch (Opcode) {
  case Instruction::Call:
  case Instruction::UncondBr:
  case Instruction::CondBr:
  case Instruction::PHI:
  case Instruction::GetElementPtr:
    llvm_unreachable("This instruction is handled by a different recipe.");
  case Instruction::UDiv:
  case Instruction::SDiv:
  case Instruction::SRem:
  case Instruction::URem:
  case Instruction::Add:
  case Instruction::FAdd:
  case Instruction::Sub:
  case Instruction::FSub:
  case Instruction::FNeg:
  case Instruction::Mul:
  case Instruction::FMul:
  case Instruction::FDiv:
  case Instruction::FRem:
  case Instruction::Shl:
  case Instruction::LShr:
  case Instruction::AShr:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor: {
    // Just widen unops and binops.
    SmallVector<Value *, 2> Ops;
    for (VPValue *VPOp : operands())
      Ops.push_back(State.get(VPOp));

    Value *V = Builder.CreateNAryOp(Opcode, Ops);

    if (auto *VecOp = dyn_cast<Instruction>(V)) {
      applyFlags(*VecOp);
      applyMetadata(*VecOp);
    }

    // Use this vector value for all users of the original instruction.
    State.set(this, V);
    break;
  }
  case Instruction::ExtractValue: {
    assert(getNumOperands() == 2 && "expected single level extractvalue");
    Value *Op = State.get(getOperand(0));
    Value *Extract = Builder.CreateExtractValue(
        Op, cast<VPConstantInt>(getOperand(1))->getZExtValue());
    State.set(this, Extract);
    break;
  }
  case Instruction::Freeze: {
    Value *Op = State.get(getOperand(0));
    Value *Freeze = Builder.CreateFreeze(Op);
    State.set(this, Freeze);
    break;
  }
  case Instruction::ICmp:
  case Instruction::FCmp: {
    // Widen compares. Generate vector compares.
    bool FCmp = Opcode == Instruction::FCmp;
    Value *A = State.get(getOperand(0));
    Value *B = State.get(getOperand(1));
    Value *C = nullptr;
    if (FCmp) {
      C = Builder.CreateFCmp(getPredicate(), A, B);
    } else {
      C = Builder.CreateICmp(getPredicate(), A, B);
    }
    if (auto *I = dyn_cast<Instruction>(C)) {
      applyFlags(*I);
      applyMetadata(*I);
    }
    State.set(this, C);
    break;
  }
  case Instruction::Select: {
    VPValue *CondOp = getOperand(0);
    Value *Cond = State.get(CondOp, vputils::isSingleScalar(CondOp));
    Value *Op0 = State.get(getOperand(1));
    Value *Op1 = State.get(getOperand(2));
    Value *Sel = State.Builder.CreateSelect(Cond, Op0, Op1);
    State.set(this, Sel);
    if (auto *I = dyn_cast<Instruction>(Sel)) {
      if (isa<FPMathOperator>(I))
        applyFlags(*I);
      applyMetadata(*I);
    }
    break;
  }
  default:
    // This instruction is not vectorized by simple widening.
    LLVM_DEBUG(dbgs() << "LV: Found an unhandled opcode : "
                      << Instruction::getOpcodeName(Opcode));
    llvm_unreachable("Unhandled instruction!");
  } // end of switch.

#if !defined(NDEBUG)
  // Verify that VPlan type inference results agree with the type of the
  // generated values.
  assert(VectorType::get(this->getScalarType(), State.VF) ==
             State.get(this)->getType() &&
         "inferred type and type from generated instructions do not match");
#endif
}

InstructionCost VPWidenRecipe::computeCost(ElementCount VF,
                                           VPCostContext &Ctx) const {
  switch (Opcode) {
  case Instruction::UDiv:
  case Instruction::SDiv:
  case Instruction::SRem:
  case Instruction::URem:
    // If the div/rem operation isn't safe to speculate and requires
    // predication, then the only way we can even create a vplan is to insert
    // a select on the second input operand to ensure we use the value of 1
    // for the inactive lanes. The select will be costed separately.
  case Instruction::FNeg:
  case Instruction::Add:
  case Instruction::FAdd:
  case Instruction::Sub:
  case Instruction::FSub:
  case Instruction::Mul:
  case Instruction::FMul:
  case Instruction::FDiv:
  case Instruction::FRem:
  case Instruction::Shl:
  case Instruction::LShr:
  case Instruction::AShr:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
  case Instruction::Freeze:
  case Instruction::ExtractValue:
  case Instruction::ICmp:
  case Instruction::FCmp:
  case Instruction::Select:
    return getCostForRecipeWithOpcode(getOpcode(), VF, Ctx);
  default:
    llvm_unreachable("Unsupported opcode for instruction");
  }
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN ";
  printAsOperand(O, SlotTracker);
  O << " = " << Instruction::getOpcodeName(Opcode);
  printFlags(O);
  printOperands(O, SlotTracker);
}
#endif

void VPWidenCastRecipe::execute(VPTransformState &State) {
  auto &Builder = State.Builder;
  /// Vectorize casts.
  assert(State.VF.isVector() && "Not vectorizing?");
  Type *DestTy = VectorType::get(getScalarType(), State.VF);
  VPValue *Op = getOperand(0);
  Value *A = State.get(Op);
  Value *Cast = Builder.CreateCast(Instruction::CastOps(Opcode), A, DestTy);
  State.set(this, Cast);
  if (auto *CastOp = dyn_cast<Instruction>(Cast)) {
    applyFlags(*CastOp);
    applyMetadata(*CastOp);
  }
}

InstructionCost VPWidenCastRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  return getCostForRecipeWithOpcode(getOpcode(), VF, Ctx);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenCastRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-CAST ";
  printAsOperand(O, SlotTracker);
  O << " = " << Instruction::getOpcodeName(Opcode);
  printFlags(O);
  printOperands(O, SlotTracker);
  O << " to " << *getScalarType();
}
#endif

InstructionCost VPHeaderPHIRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenIntOrFpInductionRecipe::printRecipe(
    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
  O << Indent;
  printAsOperand(O, SlotTracker);
  O << " = WIDEN-INDUCTION";
  printFlags(O);
  printOperands(O, SlotTracker);

  if (auto *TI = getTruncInst())
    O << " (truncated to " << *TI->getType() << ")";
}
#endif

bool VPWidenIntOrFpInductionRecipe::isCanonical() const {
  // The step may be defined by a recipe in the preheader (e.g. if it requires
  // SCEV expansion), but for the canonical induction the step is required to be
  // 1, which is represented as live-in.
  return match(getStartValue(), m_ZeroInt()) &&
         match(getStepValue(), m_One()) &&
         getScalarType() == getRegion()->getCanonicalIVType();
}

InstructionCost
VPWidenIntOrFpInductionRecipe::computeCost(ElementCount VF,
                                           VPCostContext &Ctx) const {
  // A widened induction generates a vector phi and increments it by the
  // splatted step each iteration.
  const InductionDescriptor &ID = getInductionDescriptor();
  InstructionCost Cost = Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
  Type *StepTy = getScalarType();
  unsigned IncOpc = ID.getKind() == InductionDescriptor::IK_IntInduction
                        ? Instruction::Add
                        : ID.getInductionOpcode();
  assert(IncOpc != Instruction::BinaryOpsEnd &&
         "induction must have a valid increment opcode");
  return Cost + Ctx.TTI.getArithmeticInstrCost(IncOpc, toVectorTy(StepTy, VF),
                                               Ctx.CostKind);
}

InstructionCost VPDerivedIVRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  // The cost model for this is modelled on expandVPDerivedIV in
  // VPlanTransforms.cpp. In order to avoid overly pessimistic costs that can
  // negatively affect vectorization it takes into account any expected
  // simplifications that happen in simplifyRecipe.
  switch (getInductionKind()) {
  default:
    // TODO: Compute cost for remaining kinds.
    break;
  case InductionDescriptor::IK_IntInduction: {
    // There are currently no tests that expose a path where all lanes are
    // used, so it's better to bail out for now.
    if (!vputils::onlyFirstLaneUsed(this))
      break;

    // Start off by assuming we need both mul and add, then refine this.
    bool NeedsMul = true, NeedsAdd = true, NeedsShl = false;

    // If the start value is zero the add gets folded away.
    if (auto *StartC = dyn_cast<VPConstantInt>(getStartValue()))
      NeedsAdd = !StartC->isZero();

    // For some values of step the arithmetic changes:
    //  1. A step of 1 requires no operation.
    //  2. A step of -1 requires a negate.
    //  3. A power-of-2 step will use a shl, instead of a mul.
    Type *StepTy = getStepValue()->getScalarType();
    InstructionCost Cost(0);
    if (auto *StepC = dyn_cast<VPConstantInt>(getStepValue())) {
      if (StepC->isOne())
        NeedsMul = false;
      else if (StepC->getAPInt().isAllOnes()) {
        // This will most likely end up as a negate in simplifyRecipe, and
        // the negate will be combined with the add to make a sub.
        // NOTE: This is perhaps an invalid assumption that the cost of an
        // 'add' is the same as a 'sub'.
        NeedsMul = false;
        NeedsAdd = true;
      } else if (StepC->getAPInt().isPowerOf2()) {
        // This will most likely end up as a shift-left in simplifyRecipe
        NeedsMul = false;
        NeedsShl = true;
      }
    }

    // Add the cost of the conversion from index to step type if the index
    // will be used.
    Type *IndexTy = getIndex()->getScalarType();
    unsigned StepTySize = StepTy->getScalarSizeInBits();
    unsigned IndexTySize = IndexTy->getScalarSizeInBits();
    if ((NeedsAdd || NeedsMul || NeedsShl) && StepTySize != IndexTySize) {
      unsigned CastOpc =
          StepTySize < IndexTySize ? Instruction::Trunc : Instruction::ZExt;
      Cost += Ctx.TTI.getCastInstrCost(
          CastOpc, StepTy, IndexTy, TTI::CastContextHint::None, Ctx.CostKind);
    }

    if (NeedsMul)
      Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::Mul, StepTy,
                                             Ctx.CostKind);
    if (NeedsShl)
      Cost += Ctx.TTI.getArithmeticInstrCost(
          Instruction::Shl, StepTy, Ctx.CostKind,
          {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
          {TargetTransformInfo::OK_UniformConstantValue,
           TargetTransformInfo::OP_None});
    if (NeedsAdd)
      Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::Add, StepTy,
                                             Ctx.CostKind);
    return Cost;
  }
  }

  return 0;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPDerivedIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  O << Indent;
  printAsOperand(O, SlotTracker);
  O << " = DERIVED-IV";
  printFlags(O);
  getStartValue()->printAsOperand(O, SlotTracker);
  O << " + ";
  getOperand(1)->printAsOperand(O, SlotTracker);
  O << " * ";
  getStepValue()->printAsOperand(O, SlotTracker);
}
#endif

bool VPScalarIVStepsRecipe::doesGeneratePerAllLanes() const {
  return !vputils::onlyFirstLaneUsed(this);
}

InstructionCost VPScalarIVStepsRecipe::computeCost(ElementCount VF,
                                                   VPCostContext &Ctx) const {
  // TODO: Add costs for floating point.
  Type *BaseIVTy = getOperand(0)->getScalarType();
  if (!BaseIVTy->isIntegerTy())
    return 0;

  // TODO: Add support for predicated regions. Requires scaling the cost by the
  // probability of entering the block.
  if (getRegion() && getRegion()->isReplicator())
    return 0;

  // If only the first lane is used, then there won't be any code that remains
  // in the loop for the first unrolled part.
  if (vputils::onlyFirstLaneUsed(this))
    return 0;

  // Typically the operations are:
  //   1. Add the start index to each lane value.
  //   2. Multiply the start index by the step.
  //   3. Add the scaled start index to base IV.
  // Any code generated for 1 and 2 should be loop invariant and therefore
  // hoisted out of the loop. We only need to add on the cost of 3.

  // Given the users of VPScalarIVStepsRecipe tend to be scalarized GEPs, i.e.
  //  %add1 = add i32 %iv, 0
  //  %add2 = add i32 %iv, 1
  //  %gep1 = getelementptr i8, ptr %p, i32 %add1
  //  %gep2 = getelementptr i8, ptr %p, i32 %add2
  // it's very likely that these GEPs will all be rewritten to have a common
  // base such that what's left is just
  //  %base_gep = getelementptr i8, ptr %p, i32 %iv
  //  %gep1 = getelementptr i8, ptr %base_gep, i32 0
  //  %gep2 = getelementptr i8, ptr %base_gep, i32 1
  // Therefore, in reality the cost is somewhere betwen 1*AddCost and
  // (NumLanes - 1) * AddCost. For now, assume the cost of a single add.
  return Ctx.TTI.getArithmeticInstrCost(Instruction::Add, BaseIVTy,
                                        Ctx.CostKind);
}

void VPScalarIVStepsRecipe::execute(VPTransformState &State) {
  // Fast-math-flags propagate from the original induction instruction.
  IRBuilder<>::FastMathFlagGuard FMFG(State.Builder);
  State.Builder.setFastMathFlags(getFastMathFlagsOrNone());

  /// Compute scalar induction steps. \p ScalarIV is the scalar induction
  /// variable on which to base the steps, \p Step is the size of the step.

  Value *BaseIV = State.get(getOperand(0), VPLane(0));
  Value *Step = State.get(getStepValue(), VPLane(0));
  IRBuilderBase &Builder = State.Builder;

  // Ensure step has the same type as that of scalar IV.
  Type *BaseIVTy = BaseIV->getType()->getScalarType();
  assert(BaseIVTy == Step->getType() && "Types of BaseIV and Step must match!");

  // We build scalar steps for both integer and floating-point induction
  // variables. Here, we determine the kind of arithmetic we will perform.
  Instruction::BinaryOps AddOp;
  Instruction::BinaryOps MulOp;
  if (BaseIVTy->isIntegerTy()) {
    AddOp = Instruction::Add;
    MulOp = Instruction::Mul;
  } else {
    AddOp = InductionOpcode;
    MulOp = Instruction::FMul;
  }

  // Determine the number of scalars we need to generate.
  bool FirstLaneOnly = vputils::onlyFirstLaneUsed(this);
  // Compute the scalar steps and save the results in State.

  unsigned EndLane = FirstLaneOnly ? 1 : State.VF.getKnownMinValue();
  Value *StartIdx0 = getStartIndex() ? State.get(getStartIndex(), true)
                                     : Constant::getNullValue(BaseIVTy);

  for (unsigned Lane = 0; Lane < EndLane; ++Lane) {
    // It is okay if the induction variable type cannot hold the lane number,
    // we expect truncation in this case.
    Constant *LaneValue =
        BaseIVTy->isIntegerTy()
            ? ConstantInt::get(BaseIVTy, Lane, /*IsSigned=*/false,
                               /*ImplicitTrunc=*/true)
            : ConstantFP::get(BaseIVTy, Lane);
    Value *StartIdx = Builder.CreateBinOp(AddOp, StartIdx0, LaneValue);
    assert((State.VF.isScalable() || isa<Constant>(StartIdx)) &&
           "Expected StartIdx to be folded to a constant when VF is not "
           "scalable");
    auto *Mul = Builder.CreateBinOp(MulOp, StartIdx, Step);
    auto *Add = Builder.CreateBinOp(AddOp, BaseIV, Mul);
    State.set(this, Add, VPLane(Lane));
  }
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPScalarIVStepsRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                        VPSlotTracker &SlotTracker) const {
  O << Indent;
  printAsOperand(O, SlotTracker);
  O << " = SCALAR-STEPS ";
  printOperands(O, SlotTracker);
}
#endif

bool VPWidenGEPRecipe::usesFirstLaneOnly(const VPValue *Op) const {
  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
  return vputils::isSingleScalar(Op);
}

void VPWidenGEPRecipe::execute(VPTransformState &State) {
  assert(State.VF.isVector() && "not widening");
  auto Ops = map_to_vector(operands(), [&](VPValue *Op) {
    return State.get(Op, vputils::isSingleScalar(Op));
  });
  auto *GEP =
      State.Builder.CreateGEP(getSourceElementType(), Ops.front(),
                              drop_begin(Ops), "wide.gep", getGEPNoWrapFlags());
  State.set(this, GEP, vputils::isSingleScalar(this));
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenGEPRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                   VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-GEP ";
  printAsOperand(O, SlotTracker);
  O << " = getelementptr";
  printFlags(O);
  printOperands(O, SlotTracker);
}
#endif

void VPVectorEndPointerRecipe::materializeOffset(unsigned Part) {
  assert(!getOffset() && "Unexpected offset operand");
  VPBuilder Builder(this);
  VPlan &Plan = *getParent()->getPlan();
  VPValue *VFVal = getVFValue();
  const DataLayout &DL = Plan.getDataLayout();
  Type *IndexTy = DL.getIndexType(this->getScalarType());
  VPValue *Stride =
      Plan.getConstantInt(IndexTy, getStride(), /*IsSigned=*/true);
  VPValue *VF =
      Builder.createScalarZExtOrTrunc(VFVal, IndexTy, DebugLoc::getUnknown());

  // Offset for Part0 = Offset0 = Stride * (VF - 1).
  VPInstruction *VFMinusOne =
      Builder.createSub(VF, Plan.getConstantInt(IndexTy, 1u),
                        DebugLoc::getUnknown(), "", {true, true});
  VPInstruction *Offset0 =
      Builder.createOverflowingOp(Instruction::Mul, {VFMinusOne, Stride});

  // Offset for PartN = Offset0 + Part * Stride * VF.
  VPValue *PartxStride =
      Plan.getConstantInt(IndexTy, Part * getStride(), /*IsSigned=*/true);
  VPValue *Offset = Builder.createAdd(
      Offset0,
      Builder.createOverflowingOp(Instruction::Mul, {PartxStride, VF}));
  addOffset(Offset);
}

void VPVectorEndPointerRecipe::execute(VPTransformState &State) {
  auto &Builder = State.Builder;
  assert(getOffset() && "Expected prior materialization of offset");
  Value *Ptr = State.get(getPointer(), true);
  Value *Offset = State.get(getOffset(), true);
  Value *ResultPtr = Builder.CreateGEP(getSourceElementType(), Ptr, Offset, "",
                                       getGEPNoWrapFlags());
  State.set(this, ResultPtr, /*IsScalar*/ true);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPVectorEndPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                           VPSlotTracker &SlotTracker) const {
  O << Indent;
  printAsOperand(O, SlotTracker);
  O << " = vector-end-pointer";
  printFlags(O);
  getSourceElementType()->print(O);
  O << ", ";
  printOperands(O, SlotTracker);
}
#endif

void VPVectorPointerRecipe::execute(VPTransformState &State) {
  assert(getVFxPart() &&
         "Expected prior simplification of recipe without VFxPart");

  auto &Builder = State.Builder;
  Value *Ptr = State.get(getOperand(0), VPLane(0));
  Value *Offset = State.get(getVFxPart(), true);
  // TODO: Expand to VPInstruction to support constant folding.
  if (!match(getStride(), m_One())) {
    Value *Stride = Builder.CreateZExtOrTrunc(State.get(getStride(), true),
                                              Offset->getType());
    Offset = Builder.CreateMul(Offset, Stride);
  }
  Value *ResultPtr = Builder.CreateGEP(getSourceElementType(), Ptr, Offset, "",
                                       getGEPNoWrapFlags());
  State.set(this, ResultPtr, /*IsScalar*/ true);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPVectorPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                        VPSlotTracker &SlotTracker) const {
  O << Indent;
  printAsOperand(O, SlotTracker);
  O << " = vector-pointer";
  printFlags(O);
  getSourceElementType()->print(O);
  O << ", ";
  printOperands(O, SlotTracker);
}
#endif

InstructionCost VPBlendRecipe::computeCost(ElementCount VF,
                                           VPCostContext &Ctx) const {
  // A blend will be expanded to a select VPInstruction, which will generate a
  // scalar select if only the first lane is used.
  if (vputils::onlyFirstLaneUsed(this))
    VF = ElementCount::getFixed(1);

  Type *ResultTy = toVectorTy(this->getScalarType(), VF);
  Type *CmpTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF);
  return (getNumIncomingValues() - 1) *
         Ctx.TTI.getCmpSelInstrCost(Instruction::Select, ResultTy, CmpTy,
                                    CmpInst::BAD_ICMP_PREDICATE, Ctx.CostKind);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPBlendRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                VPSlotTracker &SlotTracker) const {
  O << Indent << "BLEND ";
  printAsOperand(O, SlotTracker);
  O << " =";
  printFlags(O);
  if (getNumIncomingValues() == 1) {
    // Not a User of any mask: not really blending, this is a
    // single-predecessor phi.
    getIncomingValue(0)->printAsOperand(O, SlotTracker);
  } else {
    for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
      if (I != 0)
        O << " ";
      getIncomingValue(I)->printAsOperand(O, SlotTracker);
      if (I == 0 && isNormalized())
        continue;
      O << "/";
      getMask(I)->printAsOperand(O, SlotTracker);
    }
  }
}
#endif

void VPReductionRecipe::execute(VPTransformState &State) {
  RecurKind Kind = getRecurrenceKind();
  assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
         "In-loop AnyOf reductions aren't currently supported");
  // Propagate the fast-math flags carried by the underlying instruction.
  IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
  State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
  Value *NewVecOp = State.get(getVecOp());
  if (VPValue *Cond = getCondOp()) {
    Value *NewCond = State.get(Cond, State.VF.isScalar());
    VectorType *VecTy = dyn_cast<VectorType>(NewVecOp->getType());
    Type *ElementTy = VecTy ? VecTy->getElementType() : NewVecOp->getType();

    Value *Start =
        getRecurrenceIdentity(Kind, ElementTy, getFastMathFlagsOrNone());
    if (State.VF.isVector())
      Start = State.Builder.CreateVectorSplat(VecTy->getElementCount(), Start);

    Value *Select = State.Builder.CreateSelect(NewCond, NewVecOp, Start);
    NewVecOp = Select;
  }
  Value *NewRed;
  Value *NextInChain;
  if (isOrdered()) {
    Value *PrevInChain = State.get(getChainOp(), /*IsScalar*/ true);
    if (State.VF.isVector())
      NewRed =
          createOrderedReduction(State.Builder, Kind, NewVecOp, PrevInChain);
    else
      NewRed = State.Builder.CreateBinOp(
          (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),
          PrevInChain, NewVecOp);
    PrevInChain = NewRed;
    NextInChain = NewRed;
  } else if (isPartialReduction()) {
    assert((Kind == RecurKind::Add || Kind == RecurKind::FAdd) &&
           "Unexpected partial reduction kind");
    Value *PrevInChain = State.get(getChainOp(), /*IsScalar*/ false);
    NewRed = State.Builder.CreateIntrinsic(
        PrevInChain->getType(),
        Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
                               : Intrinsic::vector_partial_reduce_fadd,
        {PrevInChain, NewVecOp}, State.Builder.getFastMathFlags(),
        "partial.reduce");
    PrevInChain = NewRed;
    NextInChain = NewRed;
  } else {
    assert(isInLoop() &&
           "The reduction must either be ordered, partial or in-loop");
    Value *PrevInChain = State.get(getChainOp(), /*IsScalar*/ true);
    NewRed = createSimpleReduction(State.Builder, NewVecOp, Kind);
    if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))
      NextInChain = createMinMaxOp(State.Builder, Kind, NewRed, PrevInChain);
    else
      NextInChain = State.Builder.CreateBinOp(
          (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),
          PrevInChain, NewRed);
  }
  State.set(this, NextInChain, /*IsScalar*/ !isPartialReduction());
}

void VPReductionEVLRecipe::execute(VPTransformState &State) {

  assert(State.VF.isVector() &&
         "Shouldn't generate VPReductionEVLRecipe with scalar VF");
  auto &Builder = State.Builder;
  // Propagate the fast-math flags carried by the underlying instruction.
  IRBuilderBase::FastMathFlagGuard FMFGuard(Builder);
  Builder.setFastMathFlags(getFastMathFlagsOrNone());

  RecurKind Kind = getRecurrenceKind();
  Value *Prev = State.get(getChainOp(), /*IsScalar*/ !isPartialReduction());
  Value *VecOp = State.get(getVecOp());
  Value *EVL = State.get(getEVL(), VPLane(0));

  Value *Mask;
  if (VPValue *CondOp = getCondOp())
    Mask = State.get(CondOp);
  else
    Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());

  Value *NewRed;
  if (isPartialReduction()) {
    // For partial reductions, we need to generate a predicated select
    // (vp.merge) since `@llvm.vector.partial.reduce()` doesn't have a vector
    // predicated version.
    VectorType *VecTy = cast<VectorType>(VecOp->getType());
    Value *Identity = getRecurrenceIdentity(Kind, VecTy->getElementType(),
                                            getFastMathFlagsOrNone());
    Identity =
        State.Builder.CreateVectorSplat(VecTy->getElementCount(), Identity);

    // TODO: Calculate the predicate cost for the partial reduction.
    Value *NewVecOp = State.Builder.CreateIntrinsic(
        VecTy, Intrinsic::vp_merge, {Mask, VecOp, Identity, EVL});
    assert((Kind == RecurKind::Add || Kind == RecurKind::FAdd) &&
           "Unexpected partial reduction kind");
    NewRed = State.Builder.CreateIntrinsic(
        Prev->getType(),
        Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
                               : Intrinsic::vector_partial_reduce_fadd,
        {Prev, NewVecOp}, State.Builder.getFastMathFlags(), "partial.reduce");
  } else if (isOrdered()) {
    NewRed = createOrderedReduction(Builder, Kind, VecOp, Prev, Mask, EVL);
  } else {
    NewRed = createSimpleReduction(Builder, VecOp, Kind, Mask, EVL);
    if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))
      NewRed = createMinMaxOp(Builder, Kind, NewRed, Prev);
    else
      NewRed = Builder.CreateBinOp(
          (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind), NewRed,
          Prev);
  }
  State.set(this, NewRed, !isPartialReduction());
}

InstructionCost VPReductionRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  RecurKind RdxKind = getRecurrenceKind();
  Type *ElementTy = this->getScalarType();
  auto *VectorTy = cast<VectorType>(toVectorTy(ElementTy, VF));
  unsigned Opcode = RecurrenceDescriptor::getOpcode(RdxKind);
  FastMathFlags FMFs = getFastMathFlagsOrNone();
  std::optional<FastMathFlags> OptionalFMF =
      ElementTy->isFloatingPointTy() ? std::make_optional(FMFs) : std::nullopt;

  if (isPartialReduction()) {
    InstructionCost CondCost = 0;
    if (isConditional()) {
      CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;
      auto *CondTy =
          cast<VectorType>(toVectorTy(getCondOp()->getScalarType(), VF));
      CondCost = Ctx.TTI.getCmpSelInstrCost(Instruction::Select, VectorTy,
                                            CondTy, Pred, Ctx.CostKind);
    }
    return CondCost + Ctx.TTI.getPartialReductionCost(
                          Opcode, ElementTy, ElementTy, ElementTy, VF,
                          TTI::PR_None, TTI::PR_None, {}, Ctx.CostKind,
                          OptionalFMF);
  }

  // TODO: Support any-of reductions.
  assert(
      (!RecurrenceDescriptor::isAnyOfRecurrenceKind(RdxKind) ||
       ForceTargetInstructionCost.getNumOccurrences() > 0) &&
      "Any-of reduction not implemented in VPlan-based cost model currently.");

  // Note that TTI should model the cost of moving result to the scalar register
  // and the BinOp cost in the getMinMaxReductionCost().
  if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind)) {
    Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RdxKind);
    return Ctx.TTI.getMinMaxReductionCost(Id, VectorTy, FMFs, Ctx.CostKind);
  }

  // Note that TTI should model the cost of moving result to the scalar register
  // and the BinOp cost in the getArithmeticReductionCost().
  return Ctx.TTI.getArithmeticReductionCost(Opcode, VectorTy, OptionalFMF,
                                            Ctx.CostKind);
}

VPExpressionRecipe::VPExpressionRecipe(
    ExpressionTypes ExpressionType,
    ArrayRef<VPSingleDefRecipe *> ExpressionRecipes)
    : VPSingleDefRecipe(VPRecipeBase::VPExpressionSC, {},
                        cast<VPReductionRecipe>(ExpressionRecipes.back())
                            ->getChainOp()
                            ->getScalarType()),
      ExpressionRecipes(ExpressionRecipes), ExpressionType(ExpressionType) {
  assert(!ExpressionRecipes.empty() && "Nothing to combine?");
  assert(
      none_of(ExpressionRecipes,
              [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&
      "expression cannot contain recipes with side-effects");

  // Maintain a copy of the expression recipes as a set of users.
  SmallPtrSet<VPUser *, 4> ExpressionRecipesAsSetOfUsers;
  for (auto *R : ExpressionRecipes)
    ExpressionRecipesAsSetOfUsers.insert(R);

  // Recipes in the expression, except the last one, must only be used by
  // (other) recipes inside the expression. If there are other users, external
  // to the expression, use a clone of the recipe for external users.
  for (VPSingleDefRecipe *R : reverse(ExpressionRecipes)) {
    if (R != ExpressionRecipes.back() &&
        any_of(R->users(), [&ExpressionRecipesAsSetOfUsers](VPUser *U) {
          return !ExpressionRecipesAsSetOfUsers.contains(U);
        })) {
      // There are users outside of the expression. Clone the recipe and use the
      // clone those external users.
      VPSingleDefRecipe *CopyForExtUsers = R->clone();
      R->replaceUsesWithIf(CopyForExtUsers, [&ExpressionRecipesAsSetOfUsers](
                                                VPUser &U, unsigned) {
        return !ExpressionRecipesAsSetOfUsers.contains(&U);
      });
      CopyForExtUsers->insertBefore(R);
    }
    if (R->getParent())
      R->removeFromParent();
  }

  // Internalize all external operands to the expression recipes. To do so,
  // create new temporary VPValues for all operands defined by a recipe outside
  // the expression. The original operands are added as operands of the
  // VPExpressionRecipe itself.
  for (auto *R : ExpressionRecipes) {
    for (const auto &[Idx, Op] : enumerate(R->operands())) {
      auto *Def = Op->getDefiningRecipe();
      if (Def && ExpressionRecipesAsSetOfUsers.contains(Def))
        continue;
      addOperand(Op);
      LiveInPlaceholders.push_back(new VPSymbolicValue(Op->getScalarType()));
    }
  }

  // Replace each external operand with the first one created for it in
  // LiveInPlaceholders.
  for (auto *R : ExpressionRecipes)
    for (auto const &[LiveIn, Tmp] : zip(operands(), LiveInPlaceholders))
      R->replaceUsesOfWith(LiveIn, Tmp);
}

SmallVector<VPSingleDefRecipe *> VPExpressionRecipe::decompose() {
  for (auto *R : ExpressionRecipes)
    // Since the list could contain duplicates, make sure the recipe hasn't
    // already been inserted.
    if (!R->getParent())
      R->insertBefore(this);

  for (const auto &[Idx, Op] : enumerate(operands()))
    LiveInPlaceholders[Idx]->replaceAllUsesWith(Op);

  replaceAllUsesWith(ExpressionRecipes.back());
  SmallVector<VPSingleDefRecipe *> DecomposedRecipes(ExpressionRecipes);
  ExpressionRecipes.clear();
  return DecomposedRecipes;
}

InstructionCost VPExpressionRecipe::computeCost(ElementCount VF,
                                                VPCostContext &Ctx) const {
  Type *RedTy = this->getScalarType();
  auto *SrcVecTy =
      cast<VectorType>(toVectorTy(getOperand(0)->getScalarType(), VF));
  unsigned Opcode = RecurrenceDescriptor::getOpcode(
      cast<VPReductionRecipe>(ExpressionRecipes.back())->getRecurrenceKind());
  switch (ExpressionType) {
  case ExpressionTypes::NegatedExtendedReduction:
    assert((Opcode == Instruction::Add || Opcode == Instruction::FAdd) &&
           "Unexpected opcode");
    Opcode = Opcode == Instruction::Add ? Instruction::Sub : Instruction::FSub;
    [[fallthrough]];
  case ExpressionTypes::ExtendedReduction: {
    auto *RedR = cast<VPReductionRecipe>(ExpressionRecipes.back());
    auto *ExtR = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);

    if (RedR->isPartialReduction())
      return Ctx.TTI.getPartialReductionCost(
          Opcode, getOperand(0)->getScalarType(), nullptr, RedTy, VF,
          TargetTransformInfo::getPartialReductionExtendKind(ExtR->getOpcode()),
          TargetTransformInfo::PR_None, std::nullopt, Ctx.CostKind,
          RedTy->isFloatingPointTy()
              ? std::optional{RedR->getFastMathFlagsOrNone()}
              : std::nullopt);
    else if (!RedTy->isFloatingPointTy())
      // TTI::getExtendedReductionCost only supports integer types.
      return Ctx.TTI.getExtendedReductionCost(
          Opcode, ExtR->getOpcode() == Instruction::ZExt, RedTy, SrcVecTy,
          std::nullopt, Ctx.CostKind);
    else
      return InstructionCost::getInvalid();
  }
  case ExpressionTypes::MulAccReduction:
    return Ctx.TTI.getMulAccReductionCost(false, Opcode, RedTy, SrcVecTy,
                                          Ctx.CostKind);

  case ExpressionTypes::ExtNegatedMulAccReduction:
    switch (Opcode) {
    case Instruction::Add:
      Opcode = Instruction::Sub;
      break;
    case Instruction::FAdd:
      Opcode = Instruction::FSub;
      break;
    default:
      llvm_unreachable("Unsupported opcode for ExtNegatedMulAccReduction");
    }
    [[fallthrough]];
  case ExpressionTypes::ExtMulAccReduction: {
    auto *RedR = cast<VPReductionRecipe>(ExpressionRecipes.back());
    if (RedR->isPartialReduction()) {
      auto *Ext0R = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
      auto *Ext1R = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
      auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);
      return Ctx.TTI.getPartialReductionCost(
          Opcode, getOperand(0)->getScalarType(),
          getOperand(1)->getScalarType(), RedTy, VF,
          TargetTransformInfo::getPartialReductionExtendKind(
              Ext0R->getOpcode()),
          TargetTransformInfo::getPartialReductionExtendKind(
              Ext1R->getOpcode()),
          Mul->getOpcode(), Ctx.CostKind,
          RedTy->isFloatingPointTy()
              ? std::optional{RedR->getFastMathFlagsOrNone()}
              : std::nullopt);
    }
    assert(Opcode != Instruction::FSub && "Only integer types are supported");
    return Ctx.TTI.getMulAccReductionCost(
        cast<VPWidenCastRecipe>(ExpressionRecipes.front())->getOpcode() ==
            Instruction::ZExt,
        Opcode, RedTy, SrcVecTy, Ctx.CostKind);
  }
  }
  llvm_unreachable("Unknown VPExpressionRecipe::ExpressionTypes enum");
}

bool VPExpressionRecipe::mayReadOrWriteMemory() const {
  return any_of(ExpressionRecipes, [](VPSingleDefRecipe *R) {
    return R->mayReadFromMemory() || R->mayWriteToMemory();
  });
}

bool VPExpressionRecipe::mayHaveSideEffects() const {
  assert(
      none_of(ExpressionRecipes,
              [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&
      "expression cannot contain recipes with side-effects");
  return false;
}

bool VPExpressionRecipe::isVectorToScalar() const {
  auto *RR = dyn_cast<VPReductionRecipe>(ExpressionRecipes.back());
  return RR && !RR->isPartialReduction();
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

void VPExpressionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                     VPSlotTracker &SlotTracker) const {
  O << Indent << "EXPRESSION ";
  printAsOperand(O, SlotTracker);
  O << " = ";
  auto *Red = cast<VPReductionRecipe>(ExpressionRecipes.back());
  unsigned Opcode = RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind());
  VPValue *Mask = getOperand(getNumOperands() - 1);
  VPValue *EVL =
      isa<VPReductionEVLRecipe>(Red)
          ? getOperand(getNumOperands() - (Red->isConditional() ? 2 : 1))
          : nullptr;
  VPValue *RdxStart = getOperand(
      getNumOperands() - (Red->isConditional() ? 2 : 1) - (EVL ? 1 : 0));
  auto PrintEVLAndMask = [&]() {
    if (EVL) {
      O << ", ";
      EVL->printAsOperand(O, SlotTracker);
    }
    if (Red->isConditional()) {
      O << ", ";
      Mask->printAsOperand(O, SlotTracker);
    }
  };

  switch (ExpressionType) {
  case ExpressionTypes::NegatedExtendedReduction:
  case ExpressionTypes::ExtendedReduction: {
    bool Negated = ExpressionType == ExpressionTypes::NegatedExtendedReduction;
    getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);
    O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
    O << Instruction::getOpcodeName(Opcode) << " (";
    if (Negated)
      O << (Opcode == Instruction::Add ? "sub (0, " : "fneg(");
    getOperand(0)->printAsOperand(O, SlotTracker);
    if (Negated)
      O << ")";
    Red->printFlags(O);

    auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
    O << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
      << *Ext0->getScalarType();
    PrintEVLAndMask();
    O << ")";
    break;
  }
  case ExpressionTypes::ExtNegatedMulAccReduction: {
    RdxStart->printAsOperand(O, SlotTracker);
    O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
    O << Instruction::getOpcodeName(
             RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
      << " (sub (0, mul";
    auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);
    Mul->printFlags(O);
    O << "(";
    getOperand(0)->printAsOperand(O, SlotTracker);
    auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
    O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
      << *Ext0->getScalarType() << "), (";
    getOperand(1)->printAsOperand(O, SlotTracker);
    auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
    O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "
      << *Ext1->getScalarType() << ")";
    PrintEVLAndMask();
    O << "))";
    break;
  }
  case ExpressionTypes::MulAccReduction:
  case ExpressionTypes::ExtMulAccReduction: {
    RdxStart->printAsOperand(O, SlotTracker);
    O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
    O << Instruction::getOpcodeName(
             RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
      << " (";
    O << "mul";
    bool IsExtended = ExpressionType == ExpressionTypes::ExtMulAccReduction;
    auto *Mul = cast<VPWidenRecipe>(IsExtended ? ExpressionRecipes[2]
                                               : ExpressionRecipes[0]);
    Mul->printFlags(O);
    if (IsExtended)
      O << "(";
    getOperand(0)->printAsOperand(O, SlotTracker);
    if (IsExtended) {
      auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
      O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
        << *Ext0->getScalarType() << "), (";
    } else {
      O << ", ";
    }
    getOperand(1)->printAsOperand(O, SlotTracker);
    if (IsExtended) {
      auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
      O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "
        << *Ext1->getScalarType() << ")";
    }
    PrintEVLAndMask();
    O << ")";
    break;
  }
  }
}

void VPReductionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  if (isPartialReduction())
    O << Indent << "PARTIAL-REDUCE ";
  else
    O << Indent << "REDUCE ";
  printAsOperand(O, SlotTracker);
  O << " = ";
  getChainOp()->printAsOperand(O, SlotTracker);
  O << " +";
  printFlags(O);
  O << " reduce.";
  printRecurrenceKind(O, getRecurrenceKind());
  O << " (";
  getVecOp()->printAsOperand(O, SlotTracker);
  if (isConditional()) {
    O << ", ";
    getCondOp()->printAsOperand(O, SlotTracker);
  }
  O << ")";
}

void VPReductionEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                       VPSlotTracker &SlotTracker) const {
  if (isPartialReduction())
    O << Indent << "PARTIAL-REDUCE ";
  else
    O << Indent << "REDUCE ";
  printAsOperand(O, SlotTracker);
  O << " = ";
  getChainOp()->printAsOperand(O, SlotTracker);
  O << " +";
  printFlags(O);
  O << " vp.reduce."
    << Instruction::getOpcodeName(
           RecurrenceDescriptor::getOpcode(getRecurrenceKind()))
    << " (";
  getVecOp()->printAsOperand(O, SlotTracker);
  O << ", ";
  getEVL()->printAsOperand(O, SlotTracker);
  if (isConditional()) {
    O << ", ";
    getCondOp()->printAsOperand(O, SlotTracker);
  }
  O << ")";
}

#endif

void VPReplicateRecipe::execute(VPTransformState &State) {
  assert(IsSingleScalar &&
         "VPReplicateRecipes must be unrolled before ::execute");
  auto *Instr = getUnderlyingInstr();
  Instruction *Cloned = Instr->clone();
  Type *ResultTy = getScalarType();
  if (!ResultTy->isVoidTy()) {
    Cloned->setName(Instr->getName() + ".cloned");
    // The operands of the replicate recipe may have been narrowed, resulting in
    // a narrower result type. Update the type of the cloned instruction to the
    // correct type.
    if (ResultTy != Cloned->getType())
      Cloned->mutateType(ResultTy);
  }

  applyFlags(*Cloned);
  applyMetadata(*Cloned);

  if (hasPredicate())
    cast<CmpInst>(Cloned)->setPredicate(getPredicate());

  // Replace the operands of the cloned instructions with their scalar
  // equivalents in the new loop.
  for (const auto &[Idx, V] : enumerate(operands()))
    Cloned->setOperand(Idx, State.get(V, true));

  // Place the cloned scalar in the new loop.
  State.Builder.Insert(Cloned);

  State.set(this, Cloned, true);

  // If we just cloned a new assumption, add it the assumption cache.
  if (auto *II = dyn_cast<AssumeInst>(Cloned))
    State.AC->registerAssumption(II);
}

/// Returns a SCEV expression for \p Ptr if it is a pointer computation for
/// which the legacy cost model computes a SCEV expression when computing the
/// address cost. Computing SCEVs for VPValues is incomplete and returns
/// SCEVCouldNotCompute in cases the legacy cost model can compute SCEVs. In
/// those cases we fall back to the legacy cost model. Otherwise return nullptr.
static const SCEV *getAddressAccessSCEV(const VPValue *Ptr,
                                        PredicatedScalarEvolution &PSE,
                                        const Loop *L) {
  const SCEV *Addr = vputils::getSCEVExprForVPValue(Ptr, PSE, L);
  if (isa<SCEVCouldNotCompute>(Addr))
    return Addr;

  return vputils::isAddressSCEVForCost(Addr, *PSE.getSE(), L) ? Addr : nullptr;
}

InstructionCost VPReplicateRecipe::computeCost(ElementCount VF,
                                               VPCostContext &Ctx) const {
  Instruction *UI = cast<Instruction>(getUnderlyingValue());
  // VPReplicateRecipe may be cloned as part of an existing VPlan-to-VPlan
  // transform, avoid computing their cost multiple times for now.
  Ctx.SkipCostComputation.insert(UI);

  if (VF.isScalable() && !isSingleScalar())
    return InstructionCost::getInvalid();

  switch (UI->getOpcode()) {
  case Instruction::Alloca:
    if (VF.isScalable())
      return InstructionCost::getInvalid();
    return Ctx.TTI.getArithmeticInstrCost(Instruction::Mul,
                                          this->getScalarType(), Ctx.CostKind);
  case Instruction::GetElementPtr:
    // We mark this instruction as zero-cost because the cost of GEPs in
    // vectorized code depends on whether the corresponding memory instruction
    // is scalarized or not. Therefore, we handle GEPs with the memory
    // instruction cost.
    return 0;
  case Instruction::Call: {
    auto *CalledFn =
        cast<Function>(getOperand(getNumOperands() - 1)->getLiveInIRValue());
    Type *ResultTy = this->getScalarType();
    return computeCallCost(CalledFn, ResultTy, drop_end(operands()),
                           isSingleScalar(), VF, Ctx);
  }
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::FAdd:
  case Instruction::FSub:
  case Instruction::Mul:
  case Instruction::FMul:
  case Instruction::FDiv:
  case Instruction::FRem:
  case Instruction::Shl:
  case Instruction::LShr:
  case Instruction::AShr:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
  case Instruction::ICmp:
  case Instruction::FCmp:
    return getCostForRecipeWithOpcode(getOpcode(), ElementCount::getFixed(1),
                                      Ctx) *
           (isSingleScalar() ? 1 : VF.getFixedValue());
  case Instruction::SDiv:
  case Instruction::UDiv:
  case Instruction::SRem:
  case Instruction::URem: {
    InstructionCost ScalarCost =
        getCostForRecipeWithOpcode(getOpcode(), ElementCount::getFixed(1), Ctx);
    if (isSingleScalar())
      return ScalarCost;

    // If any of the operands is from a different replicate region and has its
    // cost skipped, it may have been forced to scalar. Fall back to legacy cost
    // model to avoid cost mis-match.
    if (any_of(operands(), [&Ctx, VF](VPValue *Op) {
          auto *PredR = dyn_cast<VPPredInstPHIRecipe>(Op);
          if (!PredR)
            return false;
          return Ctx.skipCostComputation(
              dyn_cast_or_null<Instruction>(
                  PredR->getOperand(0)->getUnderlyingValue()),
              VF.isVector());
        }))
      break;

    ScalarCost = ScalarCost * VF.getFixedValue() +
                 Ctx.getScalarizationOverhead(this->getScalarType(),
                                              to_vector(operands()), VF);
    // If the recipe is not predicated (i.e. not in a replicate region), return
    // the scalar cost. Otherwise handle predicated cost.
    if (!getRegion()->isReplicator())
      return ScalarCost;

    // Account for the phi nodes that we will create.
    ScalarCost += VF.getFixedValue() *
                  Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
    // Scale the cost by the probability of executing the predicated blocks.
    // This assumes the predicated block for each vector lane is equally
    // likely.
    ScalarCost /= Ctx.getPredBlockCostDivisor(UI->getParent());
    return ScalarCost;
  }
  case Instruction::Load:
  case Instruction::Store: {
    bool IsLoad = UI->getOpcode() == Instruction::Load;
    const VPValue *PtrOp = getOperand(!IsLoad);
    const SCEV *PtrSCEV = getAddressAccessSCEV(PtrOp, Ctx.PSE, Ctx.L);
    if (isa_and_nonnull<SCEVCouldNotCompute>(PtrSCEV))
      break;

    Type *ValTy = (IsLoad ? this : getOperand(0))->getScalarType();
    Type *ScalarPtrTy = PtrOp->getScalarType();
    const Align Alignment = getLoadStoreAlignment(UI);
    unsigned AS = cast<PointerType>(ScalarPtrTy)->getAddressSpace();
    TTI::OperandValueInfo OpInfo = TTI::getOperandInfo(UI->getOperand(0));
    bool PreferVectorizedAddressing = Ctx.TTI.prefersVectorizedAddressing();
    bool UsedByLoadStoreAddress =
        !PreferVectorizedAddressing && vputils::isUsedByLoadStoreAddress(this);
    InstructionCost ScalarMemOpCost = Ctx.TTI.getMemoryOpCost(
        UI->getOpcode(), ValTy, Alignment, AS, Ctx.CostKind, OpInfo,
        UsedByLoadStoreAddress ? UI : nullptr);

    Type *PtrTy = isSingleScalar() ? ScalarPtrTy : toVectorTy(ScalarPtrTy, VF);
    InstructionCost ScalarCost =
        ScalarMemOpCost +
        Ctx.TTI.getAddressComputationCost(
            PtrTy, UsedByLoadStoreAddress ? nullptr : Ctx.PSE.getSE(), PtrSCEV,
            Ctx.CostKind);
    if (isSingleScalar())
      return ScalarCost;

    SmallVector<const VPValue *> OpsToScalarize;
    Type *ResultTy = Type::getVoidTy(PtrTy->getContext());
    // Set ResultTy and OpsToScalarize, if scalarization is needed. Currently we
    // don't assign scalarization overhead in general, if the target prefers
    // vectorized addressing or the loaded value is used as part of an address
    // of another load or store.
    if (!UsedByLoadStoreAddress) {
      bool EfficientVectorLoadStore =
          Ctx.TTI.supportsEfficientVectorElementLoadStore();
      if (!(IsLoad && !PreferVectorizedAddressing) &&
          !(!IsLoad && EfficientVectorLoadStore))
        append_range(OpsToScalarize, operands());

      if (!EfficientVectorLoadStore)
        ResultTy = this->getScalarType();
    }

    TTI::VectorInstrContext VIC =
        IsLoad ? TTI::VectorInstrContext::Load : TTI::VectorInstrContext::Store;
    InstructionCost Cost =
        (ScalarCost * VF.getFixedValue()) +
        Ctx.getScalarizationOverhead(ResultTy, OpsToScalarize, VF, VIC, true);

    const VPRegionBlock *ParentRegion = getRegion();
    if (ParentRegion && ParentRegion->isReplicator()) {
      if (!PtrSCEV)
        break;
      Cost /= Ctx.getPredBlockCostDivisor(UI->getParent());
      Cost += Ctx.TTI.getCFInstrCost(Instruction::CondBr, Ctx.CostKind);

      auto *VecI1Ty = VectorType::get(
          IntegerType::getInt1Ty(Ctx.L->getHeader()->getContext()), VF);
      Cost += Ctx.TTI.getScalarizationOverhead(
          VecI1Ty, APInt::getAllOnes(VF.getFixedValue()),
          /*Insert=*/false, /*Extract=*/true, Ctx.CostKind);

      if (Ctx.useEmulatedMaskMemRefHack(this, VF)) {
        // Artificially setting to a high enough value to practically disable
        // vectorization with such operations.
        return 3000000;
      }
    }
    return Cost;
  }
  case Instruction::SExt:
  case Instruction::ZExt:
  case Instruction::FPToUI:
  case Instruction::FPToSI:
  case Instruction::FPExt:
  case Instruction::PtrToInt:
  case Instruction::PtrToAddr:
  case Instruction::IntToPtr:
  case Instruction::SIToFP:
  case Instruction::UIToFP:
  case Instruction::Trunc:
  case Instruction::FPTrunc:
  case Instruction::Select:
  case Instruction::AddrSpaceCast: {
    return getCostForRecipeWithOpcode(getOpcode(), ElementCount::getFixed(1),
                                      Ctx) *
           (isSingleScalar() ? 1 : VF.getFixedValue());
  }
  case Instruction::ExtractValue:
  case Instruction::InsertValue:
    return Ctx.TTI.getInsertExtractValueCost(getOpcode(), Ctx.CostKind);
  }

  return Ctx.getLegacyCost(UI, VF);
}

InstructionCost VPReplicateRecipe::computeCallCost(
    Function *CalledFn, Type *ResultTy, ArrayRef<const VPValue *> ArgOps,
    bool IsSingleScalar, ElementCount VF, VPCostContext &Ctx) {
  SmallVector<Type *, 4> Tys = map_to_vector<4>(
      ArgOps, [&](const VPValue *Op) { return Op->getScalarType(); });

  Intrinsic::ID IntrinID = CalledFn->getIntrinsicID();
  auto GetIntrinsicCost = [&] {
    if (!IntrinID)
      return InstructionCost::getInvalid();
    return Ctx.TTI.getIntrinsicInstrCost(
        IntrinsicCostAttributes(IntrinID, ResultTy, Tys), Ctx.CostKind);
  };

  if (IntrinID && VPCostContext::isFreeScalarIntrinsic(IntrinID)) {
    assert(GetIntrinsicCost() == 0 && "scalarizing intrinsic should be free");
    return 0;
  }

  InstructionCost ScalarCallCost =
      Ctx.TTI.getCallInstrCost(CalledFn, ResultTy, Tys, Ctx.CostKind);
  if (IsSingleScalar) {
    ScalarCallCost = std::min(ScalarCallCost, GetIntrinsicCost());
    return ScalarCallCost;
  }

  // Scalarization overhead is undefined for scalable VFs.
  if (VF.isScalable())
    return InstructionCost::getInvalid();

  return ScalarCallCost * VF.getFixedValue() +
         Ctx.getScalarizationOverhead(ResultTy, ArgOps, VF);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPReplicateRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  O << Indent << (IsSingleScalar ? "CLONE " : "REPLICATE ");

  if (!getScalarType()->isVoidTy()) {
    printAsOperand(O, SlotTracker);
    O << " = ";
  }
  if (auto *CB = dyn_cast<CallBase>(getUnderlyingInstr())) {
    O << "call";
    printFlags(O);
    O << "@" << CB->getCalledFunction()->getName() << "(";
    interleaveComma(drop_end(operands()), O, [&O, &SlotTracker](VPValue *Op) {
      Op->printAsOperand(O, SlotTracker);
    });
    O << ")";
  } else {
    O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode());
    printFlags(O);
    printOperands(O, SlotTracker);
  }

  // Find if the recipe is used by a widened recipe via an intervening
  // VPPredInstPHIRecipe. In this case, also pack the scalar values in a vector.
  if (any_of(users(), [](const VPUser *U) {
        if (auto *PredR = dyn_cast<VPPredInstPHIRecipe>(U))
          return !vputils::onlyScalarValuesUsed(PredR);
        return false;
      }))
    O << " (S->V)";
}
#endif

void VPBranchOnMaskRecipe::execute(VPTransformState &State) {
  llvm_unreachable("recipe must be removed when dissolving replicate region");
}

InstructionCost VPBranchOnMaskRecipe::computeCost(ElementCount VF,
                                                  VPCostContext &Ctx) const {
  // The legacy cost model doesn't assign costs to branches for individual
  // replicate regions. Match the current behavior in the VPlan cost model for
  // now.
  return 0;
}

void VPPredInstPHIRecipe::execute(VPTransformState &State) {
  llvm_unreachable("recipe must be removed when dissolving replicate region");
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPPredInstPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                      VPSlotTracker &SlotTracker) const {
  O << Indent << "PHI-PREDICATED-INSTRUCTION ";
  printAsOperand(O, SlotTracker);
  O << " = ";
  printOperands(O, SlotTracker);
}
#endif

VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() { return this; }
const VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() const { return this; }

VPRecipeBase *VPWidenLoadEVLRecipe::getAsRecipe() { return this; }
const VPRecipeBase *VPWidenLoadEVLRecipe::getAsRecipe() const { return this; }

VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() { return this; }
const VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() const { return this; }

VPRecipeBase *VPWidenStoreEVLRecipe::getAsRecipe() { return this; }
const VPRecipeBase *VPWidenStoreEVLRecipe::getAsRecipe() const { return this; }

InstructionCost VPWidenMemoryRecipe::computeCost(ElementCount VF,
                                                 VPCostContext &Ctx) const {
  const VPRecipeBase *R = getAsRecipe();
  bool IsLoad = isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(R);
  Type *ScalarTy = IsLoad ? cast<VPSingleDefRecipe>(R)->getScalarType()
                          : R->getOperand(1)->getScalarType();
  Type *Ty = toVectorTy(ScalarTy, VF);
  unsigned AS =
      cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
  unsigned Opcode = IsLoad ? Instruction::Load : Instruction::Store;

  if (!Consecutive) {
    // TODO: Using the original IR may not be accurate.
    // Currently, ARM will use the underlying IR to calculate gather/scatter
    // instruction cost.
    Type *PtrTy = getAddr()->getScalarType();
    const Value *Ptr = getAddr()->getUnderlyingValue();

    // If the address value is uniform across all lanes, then the address can be
    // calculated with scalar type and broadcast.
    if (!vputils::isSingleScalar(getAddr()))
      PtrTy = toVectorTy(PtrTy, VF);

    unsigned IID = isa<VPWidenLoadRecipe>(R)      ? Intrinsic::masked_gather
                   : isa<VPWidenStoreRecipe>(R)   ? Intrinsic::masked_scatter
                   : isa<VPWidenLoadEVLRecipe>(R) ? Intrinsic::vp_gather
                                                  : Intrinsic::vp_scatter;
    return Ctx.TTI.getAddressComputationCost(PtrTy, nullptr, nullptr,
                                             Ctx.CostKind) +
           Ctx.TTI.getMemIntrinsicInstrCost(
               MemIntrinsicCostAttributes(IID, Ty, Ptr, IsMasked, Alignment,
                                          &Ingredient),
               Ctx.CostKind);
  }

  InstructionCost Cost = 0;
  if (IsMasked) {
    unsigned IID = isa<VPWidenLoadRecipe>(R) ? Intrinsic::masked_load
                                             : Intrinsic::masked_store;
    Cost += Ctx.TTI.getMemIntrinsicInstrCost(
        MemIntrinsicCostAttributes(IID, Ty, Alignment, AS), Ctx.CostKind);
  } else {
    TTI::OperandValueInfo OpInfo = Ctx.getOperandInfo(
        isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(R) ? R->getOperand(0)
                                                        : R->getOperand(1));
    Cost += Ctx.TTI.getMemoryOpCost(Opcode, Ty, Alignment, AS, Ctx.CostKind,
                                    OpInfo, &Ingredient);
  }
  return Cost;
}

void VPWidenLoadRecipe::execute(VPTransformState &State) {
  Type *ScalarDataTy = getScalarType();
  auto *DataTy = VectorType::get(ScalarDataTy, State.VF);
  bool CreateGather = !isConsecutive();

  auto &Builder = State.Builder;
  Value *Mask = nullptr;
  if (auto *VPMask = getMask())
    Mask = State.get(VPMask);

  Value *Addr = State.get(getAddr(), /*IsScalar*/ !CreateGather);
  Value *NewLI;
  if (CreateGather) {
    NewLI = Builder.CreateMaskedGather(DataTy, Addr, Alignment, Mask, nullptr,
                                       "wide.masked.gather");
  } else if (Mask) {
    NewLI =
        Builder.CreateMaskedLoad(DataTy, Addr, Alignment, Mask,
                                 PoisonValue::get(DataTy), "wide.masked.load");
  } else {
    NewLI = Builder.CreateAlignedLoad(DataTy, Addr, Alignment, "wide.load");
  }
  applyMetadata(*cast<Instruction>(NewLI));
  State.set(this, NewLI);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenLoadRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN ";
  printAsOperand(O, SlotTracker);
  O << " = load ";
  printOperands(O, SlotTracker);
}
#endif

void VPWidenLoadEVLRecipe::execute(VPTransformState &State) {
  Type *ScalarDataTy = getScalarType();
  auto *DataTy = VectorType::get(ScalarDataTy, State.VF);
  bool CreateGather = !isConsecutive();

  auto &Builder = State.Builder;
  CallInst *NewLI;
  Value *EVL = State.get(getEVL(), VPLane(0));
  Value *Addr = State.get(getAddr(), !CreateGather);
  Value *Mask = nullptr;
  if (VPValue *VPMask = getMask())
    Mask = State.get(VPMask);
  else
    Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());

  if (CreateGather) {
    NewLI = Builder.CreateIntrinsicWithoutFolding(DataTy, Intrinsic::vp_gather,
                                                  {Addr, Mask, EVL}, nullptr,
                                                  "wide.masked.gather");
  } else {
    NewLI = Builder.CreateIntrinsicWithoutFolding(
        DataTy, Intrinsic::vp_load, {Addr, Mask, EVL}, nullptr, "vp.op.load");
  }
  NewLI->addParamAttr(
      0, Attribute::getWithAlignment(NewLI->getContext(), Alignment));
  applyMetadata(*NewLI);
  State.set(this, NewLI);
}

InstructionCost VPWidenLoadEVLRecipe::computeCost(ElementCount VF,
                                                  VPCostContext &Ctx) const {
  if (!Consecutive || IsMasked)
    return VPWidenMemoryRecipe::computeCost(VF, Ctx);

  // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
  // here because the EVL recipes using EVL to replace the tail mask. But in the
  // legacy model, it will always calculate the cost of mask.
  // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost  when we
  // don't need to compare to the legacy cost model.
  Type *Ty = toVectorTy(getScalarType(), VF);
  unsigned AS =
      cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
  return Ctx.TTI.getMemIntrinsicInstrCost(
      MemIntrinsicCostAttributes(Intrinsic::vp_load, Ty, Alignment, AS),
      Ctx.CostKind);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenLoadEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                       VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN ";
  printAsOperand(O, SlotTracker);
  O << " = vp.load ";
  printOperands(O, SlotTracker);
}
#endif

void VPWidenStoreRecipe::execute(VPTransformState &State) {
  VPValue *StoredVPValue = getStoredValue();
  bool CreateScatter = !isConsecutive();

  auto &Builder = State.Builder;

  Value *Mask = nullptr;
  if (auto *VPMask = getMask())
    Mask = State.get(VPMask);

  Value *StoredVal = State.get(StoredVPValue);
  Value *Addr = State.get(getAddr(), /*IsScalar*/ !CreateScatter);
  Instruction *NewSI = nullptr;
  if (CreateScatter)
    NewSI = Builder.CreateMaskedScatter(StoredVal, Addr, Alignment, Mask);
  else if (Mask)
    NewSI = Builder.CreateMaskedStore(StoredVal, Addr, Alignment, Mask);
  else
    NewSI = Builder.CreateAlignedStore(StoredVal, Addr, Alignment);
  applyMetadata(*NewSI);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenStoreRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                     VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN store ";
  printOperands(O, SlotTracker);
}
#endif

void VPWidenStoreEVLRecipe::execute(VPTransformState &State) {
  VPValue *StoredValue = getStoredValue();
  bool CreateScatter = !isConsecutive();

  auto &Builder = State.Builder;

  CallInst *NewSI = nullptr;
  Value *StoredVal = State.get(StoredValue);
  Value *EVL = State.get(getEVL(), VPLane(0));
  Value *Mask = nullptr;
  if (VPValue *VPMask = getMask())
    Mask = State.get(VPMask);
  else
    Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());

  Value *Addr = State.get(getAddr(), !CreateScatter);
  if (CreateScatter) {
    NewSI = Builder.CreateIntrinsicWithoutFolding(
        Type::getVoidTy(EVL->getContext()), Intrinsic::vp_scatter,
        {StoredVal, Addr, Mask, EVL});
  } else {
    NewSI = Builder.CreateIntrinsicWithoutFolding(
        Type::getVoidTy(EVL->getContext()), Intrinsic::vp_store,
        {StoredVal, Addr, Mask, EVL});
  }
  NewSI->addParamAttr(
      1, Attribute::getWithAlignment(NewSI->getContext(), Alignment));
  applyMetadata(*NewSI);
}

InstructionCost VPWidenStoreEVLRecipe::computeCost(ElementCount VF,
                                                   VPCostContext &Ctx) const {
  if (!Consecutive || IsMasked)
    return VPWidenMemoryRecipe::computeCost(VF, Ctx);

  // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
  // here because the EVL recipes using EVL to replace the tail mask. But in the
  // legacy model, it will always calculate the cost of mask.
  // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
  // don't need to compare to the legacy cost model.
  Type *Ty = toVectorTy(getStoredValue()->getScalarType(), VF);
  unsigned AS =
      cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
  return Ctx.TTI.getMemIntrinsicInstrCost(
      MemIntrinsicCostAttributes(Intrinsic::vp_store, Ty, Alignment, AS),
      Ctx.CostKind);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenStoreEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                        VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN vp.store ";
  printOperands(O, SlotTracker);
}
#endif

static Value *createBitOrPointerCast(IRBuilderBase &Builder, Value *V,
                                     VectorType *DstVTy, const DataLayout &DL) {
  // Verify that V is a vector type with same number of elements as DstVTy.
  auto VF = DstVTy->getElementCount();
  auto *SrcVecTy = cast<VectorType>(V->getType());
  assert(VF == SrcVecTy->getElementCount() && "Vector dimensions do not match");
  Type *SrcElemTy = SrcVecTy->getElementType();
  Type *DstElemTy = DstVTy->getElementType();
  assert((DL.getTypeSizeInBits(SrcElemTy) == DL.getTypeSizeInBits(DstElemTy)) &&
         "Vector elements must have same size");

  // Do a direct cast if element types are castable.
  if (CastInst::isBitOrNoopPointerCastable(SrcElemTy, DstElemTy, DL)) {
    return Builder.CreateBitOrPointerCast(V, DstVTy);
  }
  // V cannot be directly casted to desired vector type.
  // May happen when V is a floating point vector but DstVTy is a vector of
  // pointers or vice-versa. Handle this using a two-step bitcast using an
  // intermediate Integer type for the bitcast i.e. Ptr <-> Int <-> Float.
  assert((DstElemTy->isPointerTy() != SrcElemTy->isPointerTy()) &&
         "Only one type should be a pointer type");
  assert((DstElemTy->isFloatingPointTy() != SrcElemTy->isFloatingPointTy()) &&
         "Only one type should be a floating point type");
  Type *IntTy =
      IntegerType::getIntNTy(V->getContext(), DL.getTypeSizeInBits(SrcElemTy));
  auto *VecIntTy = VectorType::get(IntTy, VF);
  Value *CastVal = Builder.CreateBitOrPointerCast(V, VecIntTy);
  return Builder.CreateBitOrPointerCast(CastVal, DstVTy);
}

/// Return a vector containing interleaved elements from multiple
/// smaller input vectors.
static Value *interleaveVectors(IRBuilderBase &Builder, ArrayRef<Value *> Vals,
                                const Twine &Name) {
  unsigned Factor = Vals.size();
  assert(Factor > 1 && "Tried to interleave invalid number of vectors");

  VectorType *VecTy = cast<VectorType>(Vals[0]->getType());
#ifndef NDEBUG
  for (Value *Val : Vals)
    assert(Val->getType() == VecTy && "Tried to interleave mismatched types");
#endif

  // Scalable vectors cannot use arbitrary shufflevectors (only splats), so
  // must use intrinsics to interleave.
  if (VecTy->isScalableTy()) {
    assert(Factor <= 8 && "Unsupported interleave factor for scalable vectors");
    return Builder.CreateVectorInterleave(Vals, Name);
  }

  // Fixed length. Start by concatenating all vectors into a wide vector.
  Value *WideVec = concatenateVectors(Builder, Vals);

  // Interleave the elements into the wide vector.
  const unsigned NumElts = VecTy->getElementCount().getFixedValue();
  return Builder.CreateShuffleVector(
      WideVec, createInterleaveMask(NumElts, Factor), Name);
}

// Try to vectorize the interleave group that \p Instr belongs to.
//
// E.g. Translate following interleaved load group (factor = 3):
//   for (i = 0; i < N; i+=3) {
//     R = Pic[i];             // Member of index 0
//     G = Pic[i+1];           // Member of index 1
//     B = Pic[i+2];           // Member of index 2
//     ... // do something to R, G, B
//   }
// To:
//   %wide.vec = load <12 x i32>                       ; Read 4 tuples of R,G,B
//   %R.vec = shuffle %wide.vec, poison, <0, 3, 6, 9>   ; R elements
//   %G.vec = shuffle %wide.vec, poison, <1, 4, 7, 10>  ; G elements
//   %B.vec = shuffle %wide.vec, poison, <2, 5, 8, 11>  ; B elements
//
// Or translate following interleaved store group (factor = 3):
//   for (i = 0; i < N; i+=3) {
//     ... do something to R, G, B
//     Pic[i]   = R;           // Member of index 0
//     Pic[i+1] = G;           // Member of index 1
//     Pic[i+2] = B;           // Member of index 2
//   }
// To:
//   %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>
//   %B_U.vec = shuffle %B.vec, poison, <0, 1, 2, 3, u, u, u, u>
//   %interleaved.vec = shuffle %R_G.vec, %B_U.vec,
//        <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>    ; Interleave R,G,B elements
//   store <12 x i32> %interleaved.vec              ; Write 4 tuples of R,G,B
void VPInterleaveRecipe::execute(VPTransformState &State) {
  assert((!needsMaskForGaps() || !State.VF.isScalable()) &&
         "Masking gaps for scalable vectors is not yet supported.");
  const InterleaveGroup<Instruction> *Group = getInterleaveGroup();
  Instruction *Instr = Group->getInsertPos();

  // Prepare for the vector type of the interleaved load/store.
  Type *ScalarTy = getLoadStoreType(Instr);
  unsigned InterleaveFactor = Group->getFactor();
  auto *VecTy = VectorType::get(ScalarTy, State.VF * InterleaveFactor);

  VPValue *BlockInMask = getMask();
  VPValue *Addr = getAddr();
  Value *ResAddr = State.get(Addr, VPLane(0));

  auto CreateGroupMask = [&BlockInMask, &State,
                          &InterleaveFactor](Value *MaskForGaps) -> Value * {
    if (State.VF.isScalable()) {
      assert(!MaskForGaps && "Interleaved groups with gaps are not supported.");
      assert(InterleaveFactor <= 8 &&
             "Unsupported deinterleave factor for scalable vectors");
      auto *ResBlockInMask = State.get(BlockInMask);
      SmallVector<Value *> Ops(InterleaveFactor, ResBlockInMask);
      return interleaveVectors(State.Builder, Ops, "interleaved.mask");
    }

    if (!BlockInMask)
      return MaskForGaps;

    Value *ResBlockInMask = State.get(BlockInMask);
    Value *ShuffledMask = State.Builder.CreateShuffleVector(
        ResBlockInMask,
        createReplicatedMask(InterleaveFactor, State.VF.getFixedValue()),
        "interleaved.mask");
    return MaskForGaps ? State.Builder.CreateBinOp(Instruction::And,
                                                   ShuffledMask, MaskForGaps)
                       : ShuffledMask;
  };

  const DataLayout &DL = Instr->getDataLayout();
  // Vectorize the interleaved load group.
  if (isa<LoadInst>(Instr)) {
    Value *MaskForGaps = nullptr;
    if (needsMaskForGaps()) {
      MaskForGaps =
          createBitMaskForGaps(State.Builder, State.VF.getFixedValue(), *Group);
      assert(MaskForGaps && "Mask for Gaps is required but it is null");
    }

    Instruction *NewLoad;
    if (BlockInMask || MaskForGaps) {
      Value *GroupMask = CreateGroupMask(MaskForGaps);
      Value *PoisonVec = PoisonValue::get(VecTy);
      NewLoad = State.Builder.CreateMaskedLoad(VecTy, ResAddr,
                                               Group->getAlign(), GroupMask,
                                               PoisonVec, "wide.masked.vec");
    } else
      NewLoad = State.Builder.CreateAlignedLoad(VecTy, ResAddr,
                                                Group->getAlign(), "wide.vec");
    applyMetadata(*NewLoad);
    // TODO: Also manage existing metadata using VPIRMetadata.
    Group->addMetadata(NewLoad);

    ArrayRef<VPRecipeValue *> VPDefs = definedValues();
    if (VecTy->isScalableTy()) {
      // Scalable vectors cannot use arbitrary shufflevectors (only splats),
      // so must use intrinsics to deinterleave.
      assert(InterleaveFactor <= 8 &&
             "Unsupported deinterleave factor for scalable vectors");
      NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
          Intrinsic::getDeinterleaveIntrinsicID(InterleaveFactor),
          NewLoad->getType(), NewLoad,
          /*FMFSource=*/nullptr, "strided.vec");
    }

    auto CreateStridedVector = [&InterleaveFactor, &State,
                                &NewLoad](unsigned Index) -> Value * {
      assert(Index < InterleaveFactor && "Illegal group index");
      if (State.VF.isScalable())
        return State.Builder.CreateExtractValue(NewLoad, Index);

      // For fixed length VF, use shuffle to extract the sub-vectors from the
      // wide load.
      auto StrideMask =
          createStrideMask(Index, InterleaveFactor, State.VF.getFixedValue());
      return State.Builder.CreateShuffleVector(NewLoad, StrideMask,
                                               "strided.vec");
    };

    for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
      Instruction *Member = Group->getMember(I);

      // Skip the gaps in the group.
      if (!Member)
        continue;

      Value *StridedVec = CreateStridedVector(I);

      // If this member has different type, cast the result type.
      if (Member->getType() != ScalarTy) {
        VectorType *OtherVTy = VectorType::get(Member->getType(), State.VF);
        StridedVec =
            createBitOrPointerCast(State.Builder, StridedVec, OtherVTy, DL);
      }

      if (Group->isReverse())
        StridedVec = State.Builder.CreateVectorReverse(StridedVec, "reverse");

      State.set(VPDefs[J], StridedVec);
      ++J;
    }
    return;
  }

  // The sub vector type for current instruction.
  auto *SubVT = VectorType::get(ScalarTy, State.VF);

  // Vectorize the interleaved store group.
  Value *MaskForGaps =
      createBitMaskForGaps(State.Builder, State.VF.getKnownMinValue(), *Group);
  assert(((MaskForGaps != nullptr) == needsMaskForGaps()) &&
         "Mismatch between NeedsMaskForGaps and MaskForGaps");
  ArrayRef<VPValue *> StoredValues = getStoredValues();
  // Collect the stored vector from each member.
  SmallVector<Value *, 4> StoredVecs;
  unsigned StoredIdx = 0;
  for (unsigned i = 0; i < InterleaveFactor; i++) {
    assert((Group->getMember(i) || MaskForGaps) &&
           "Fail to get a member from an interleaved store group");
    Instruction *Member = Group->getMember(i);

    // Skip the gaps in the group.
    if (!Member) {
      Value *Undef = PoisonValue::get(SubVT);
      StoredVecs.push_back(Undef);
      continue;
    }

    Value *StoredVec = State.get(StoredValues[StoredIdx]);
    ++StoredIdx;

    if (Group->isReverse())
      StoredVec = State.Builder.CreateVectorReverse(StoredVec, "reverse");

    // If this member has different type, cast it to a unified type.

    if (StoredVec->getType() != SubVT)
      StoredVec = createBitOrPointerCast(State.Builder, StoredVec, SubVT, DL);

    StoredVecs.push_back(StoredVec);
  }

  // Interleave all the smaller vectors into one wider vector.
  Value *IVec = interleaveVectors(State.Builder, StoredVecs, "interleaved.vec");
  Instruction *NewStoreInstr;
  if (BlockInMask || MaskForGaps) {
    Value *GroupMask = CreateGroupMask(MaskForGaps);
    NewStoreInstr = State.Builder.CreateMaskedStore(
        IVec, ResAddr, Group->getAlign(), GroupMask);
  } else
    NewStoreInstr =
        State.Builder.CreateAlignedStore(IVec, ResAddr, Group->getAlign());

  applyMetadata(*NewStoreInstr);
  // TODO: Also manage existing metadata using VPIRMetadata.
  Group->addMetadata(NewStoreInstr);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPInterleaveRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                     VPSlotTracker &SlotTracker) const {
  const InterleaveGroup<Instruction> *IG = getInterleaveGroup();
  O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
  getAddr()->printAsOperand(O, SlotTracker);
  VPValue *Mask = getMask();
  if (Mask) {
    O << ", ";
    Mask->printAsOperand(O, SlotTracker);
  }

  unsigned OpIdx = 0;
  for (unsigned i = 0; i < IG->getFactor(); ++i) {
    if (!IG->getMember(i))
      continue;
    if (getNumStoreOperands() > 0) {
      O << "\n" << Indent << "  store ";
      getOperand(1 + OpIdx)->printAsOperand(O, SlotTracker);
      O << " to index " << i;
    } else {
      O << "\n" << Indent << "  ";
      getVPValue(OpIdx)->printAsOperand(O, SlotTracker);
      O << " = load from index " << i;
    }
    ++OpIdx;
  }
}
#endif

void VPInterleaveEVLRecipe::execute(VPTransformState &State) {
  assert(State.VF.isScalable() &&
         "Only support scalable VF for EVL tail-folding.");
  assert(!needsMaskForGaps() &&
         "Masking gaps for scalable vectors is not yet supported.");
  const InterleaveGroup<Instruction> *Group = getInterleaveGroup();
  Instruction *Instr = Group->getInsertPos();

  // Prepare for the vector type of the interleaved load/store.
  Type *ScalarTy = getLoadStoreType(Instr);
  unsigned InterleaveFactor = Group->getFactor();
  assert(InterleaveFactor <= 8 &&
         "Unsupported deinterleave/interleave factor for scalable vectors");
  ElementCount WideVF = State.VF * InterleaveFactor;
  auto *VecTy = VectorType::get(ScalarTy, WideVF);

  VPValue *Addr = getAddr();
  Value *ResAddr = State.get(Addr, VPLane(0));
  Value *EVL = State.get(getEVL(), VPLane(0));
  Value *InterleaveEVL = State.Builder.CreateMul(
      EVL, ConstantInt::get(EVL->getType(), InterleaveFactor), "interleave.evl",
      /* NUW= */ true, /* NSW= */ true);
  LLVMContext &Ctx = State.Builder.getContext();

  Value *GroupMask = nullptr;
  if (VPValue *BlockInMask = getMask()) {
    SmallVector<Value *> Ops(InterleaveFactor, State.get(BlockInMask));
    GroupMask = interleaveVectors(State.Builder, Ops, "interleaved.mask");
  } else {
    GroupMask =
        State.Builder.CreateVectorSplat(WideVF, State.Builder.getTrue());
  }

  // Vectorize the interleaved load group.
  if (isa<LoadInst>(Instr)) {
    CallInst *NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
        VecTy, Intrinsic::vp_load, {ResAddr, GroupMask, InterleaveEVL}, nullptr,
        "wide.vp.load");
    NewLoad->addParamAttr(0,
                          Attribute::getWithAlignment(Ctx, Group->getAlign()));

    applyMetadata(*NewLoad);
    // TODO: Also manage existing metadata using VPIRMetadata.
    Group->addMetadata(NewLoad);

    // Scalable vectors cannot use arbitrary shufflevectors (only splats),
    // so must use intrinsics to deinterleave.
    NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
        Intrinsic::getDeinterleaveIntrinsicID(InterleaveFactor),
        NewLoad->getType(), NewLoad,
        /*FMFSource=*/nullptr, "strided.vec");

    const DataLayout &DL = Instr->getDataLayout();
    for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
      Instruction *Member = Group->getMember(I);
      // Skip the gaps in the group.
      if (!Member)
        continue;

      Value *StridedVec = State.Builder.CreateExtractValue(NewLoad, I);
      // If this member has different type, cast the result type.
      if (Member->getType() != ScalarTy) {
        VectorType *OtherVTy = VectorType::get(Member->getType(), State.VF);
        StridedVec =
            createBitOrPointerCast(State.Builder, StridedVec, OtherVTy, DL);
      }

      State.set(getVPValue(J), StridedVec);
      ++J;
    }
    return;
  } // End for interleaved load.

  // The sub vector type for current instruction.
  auto *SubVT = VectorType::get(ScalarTy, State.VF);
  // Vectorize the interleaved store group.
  ArrayRef<VPValue *> StoredValues = getStoredValues();
  // Collect the stored vector from each member.
  SmallVector<Value *, 4> StoredVecs;
  const DataLayout &DL = Instr->getDataLayout();
  for (unsigned I = 0, StoredIdx = 0; I < InterleaveFactor; I++) {
    Instruction *Member = Group->getMember(I);
    // Skip the gaps in the group.
    if (!Member) {
      StoredVecs.push_back(PoisonValue::get(SubVT));
      continue;
    }

    Value *StoredVec = State.get(StoredValues[StoredIdx]);
    // If this member has different type, cast it to a unified type.
    if (StoredVec->getType() != SubVT)
      StoredVec = createBitOrPointerCast(State.Builder, StoredVec, SubVT, DL);

    StoredVecs.push_back(StoredVec);
    ++StoredIdx;
  }

  // Interleave all the smaller vectors into one wider vector.
  Value *IVec = interleaveVectors(State.Builder, StoredVecs, "interleaved.vec");
  CallInst *NewStore = State.Builder.CreateIntrinsicWithoutFolding(
      Type::getVoidTy(Ctx), Intrinsic::vp_store,
      {IVec, ResAddr, GroupMask, InterleaveEVL});

  NewStore->addParamAttr(1,
                         Attribute::getWithAlignment(Ctx, Group->getAlign()));

  applyMetadata(*NewStore);
  // TODO: Also manage existing metadata using VPIRMetadata.
  Group->addMetadata(NewStore);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPInterleaveEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                        VPSlotTracker &SlotTracker) const {
  const InterleaveGroup<Instruction> *IG = getInterleaveGroup();
  O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
  getAddr()->printAsOperand(O, SlotTracker);
  O << ", ";
  getEVL()->printAsOperand(O, SlotTracker);
  if (VPValue *Mask = getMask()) {
    O << ", ";
    Mask->printAsOperand(O, SlotTracker);
  }

  unsigned OpIdx = 0;
  for (unsigned i = 0; i < IG->getFactor(); ++i) {
    if (!IG->getMember(i))
      continue;
    if (getNumStoreOperands() > 0) {
      O << "\n" << Indent << "  vp.store ";
      getOperand(2 + OpIdx)->printAsOperand(O, SlotTracker);
      O << " to index " << i;
    } else {
      O << "\n" << Indent << "  ";
      getVPValue(OpIdx)->printAsOperand(O, SlotTracker);
      O << " = vp.load from index " << i;
    }
    ++OpIdx;
  }
}
#endif

InstructionCost VPInterleaveBase::computeCost(ElementCount VF,
                                              VPCostContext &Ctx) const {
  Instruction *InsertPos = getInsertPos();
  // Find the VPValue index of the interleave group. We need to skip gaps.
  unsigned InsertPosIdx = 0;
  for (unsigned Idx = 0; IG->getFactor(); ++Idx)
    if (auto *Member = IG->getMember(Idx)) {
      if (Member == InsertPos)
        break;
      InsertPosIdx++;
    }
  const VPValue *ValV = getNumDefinedValues() > 0
                            ? getVPValue(InsertPosIdx)
                            : getStoredValues()[InsertPosIdx];
  Type *ValTy = ValV->getScalarType();
  auto *VectorTy = cast<VectorType>(toVectorTy(ValTy, VF));
  unsigned AS =
      cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();

  unsigned InterleaveFactor = IG->getFactor();
  auto *WideVecTy = VectorType::get(ValTy, VF * InterleaveFactor);

  // Holds the indices of existing members in the interleaved group.
  SmallVector<unsigned, 4> Indices;
  for (unsigned IF = 0; IF < InterleaveFactor; IF++)
    if (IG->getMember(IF))
      Indices.push_back(IF);

  // Calculate the cost of the whole interleaved group.
  InstructionCost Cost = Ctx.TTI.getInterleavedMemoryOpCost(
      InsertPos->getOpcode(), WideVecTy, IG->getFactor(), Indices,
      IG->getAlign(), AS, Ctx.CostKind, getMask(), NeedsMaskForGaps);

  if (!IG->isReverse())
    return Cost;

  return Cost + IG->getNumMembers() *
                    Ctx.TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,
                                           VectorTy, VectorTy, Ctx.CostKind, {},
                                           0);
}

bool VPWidenPointerInductionRecipe::onlyScalarsGenerated(bool IsScalable) {
  return vputils::onlyScalarValuesUsed(this) &&
         (!IsScalable || vputils::onlyFirstLaneUsed(this));
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenPointerInductionRecipe::printRecipe(
    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
  assert((getNumOperands() == 3 || getNumOperands() == 5) &&
         "unexpected number of operands");
  O << Indent << "EMIT ";
  printAsOperand(O, SlotTracker);
  O << " = WIDEN-POINTER-INDUCTION ";
  getStartValue()->printAsOperand(O, SlotTracker);
  O << ", ";
  getStepValue()->printAsOperand(O, SlotTracker);
  O << ", ";
  getOperand(2)->printAsOperand(O, SlotTracker);
  if (getNumOperands() == 5) {
    O << ", ";
    getOperand(3)->printAsOperand(O, SlotTracker);
    O << ", ";
    getOperand(4)->printAsOperand(O, SlotTracker);
  }
}

void VPExpandSCEVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                     VPSlotTracker &SlotTracker) const {
  O << Indent << "EMIT ";
  printAsOperand(O, SlotTracker);
  O << " = EXPAND SCEV " << *Expr;
}
#endif

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenCanonicalIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                           VPSlotTracker &SlotTracker) const {
  O << Indent << "EMIT ";
  printAsOperand(O, SlotTracker);
  O << " = WIDEN-CANONICAL-INDUCTION";
  printFlags(O);
  printOperands(O, SlotTracker);
}
#endif

void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {
  auto &Builder = State.Builder;
  // Create a vector from the initial value.
  auto *VectorInit = getStartValue()->getLiveInIRValue();

  Type *VecTy = State.VF.isScalar()
                    ? VectorInit->getType()
                    : VectorType::get(VectorInit->getType(), State.VF);

  BasicBlock *VectorPH =
      State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));
  if (State.VF.isVector()) {
    auto *IdxTy = Builder.getInt32Ty();
    auto *One = ConstantInt::get(IdxTy, 1);
    IRBuilder<>::InsertPointGuard Guard(Builder);
    Builder.SetInsertPoint(VectorPH->getTerminator());
    auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
    auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
    VectorInit = Builder.CreateInsertElement(
        PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
  }

  // Create a phi node for the new recurrence.
  PHINode *Phi = PHINode::Create(VecTy, 2, "vector.recur");
  Phi->insertBefore(State.CFG.PrevBB->getFirstInsertionPt());
  Phi->addIncoming(VectorInit, VectorPH);
  State.set(this, Phi);
}

InstructionCost
VPFirstOrderRecurrencePHIRecipe::computeCost(ElementCount VF,
                                             VPCostContext &Ctx) const {
  if (VF.isScalar())
    return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);

  return 0;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPFirstOrderRecurrencePHIRecipe::printRecipe(
    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
  O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
  printAsOperand(O, SlotTracker);
  O << " = phi ";
  printOperands(O, SlotTracker);
}
#endif

void VPReductionPHIRecipe::execute(VPTransformState &State) {
  // Reductions do not have to start at zero. They can start with
  // any loop invariant values.
  VPValue *StartVPV = getStartValue();

  // In order to support recurrences we need to be able to vectorize Phi nodes.
  // Phi nodes have cycles, so we need to vectorize them in two stages. This is
  // stage #1: We create a new vector PHI node with no incoming edges. We'll use
  // this value when we vectorize all of the instructions that use the PHI.
  BasicBlock *VectorPH =
      State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));
  bool ScalarPHI = State.VF.isScalar() || isInLoop();
  Value *StartV = State.get(StartVPV, ScalarPHI);
  Type *VecTy = StartV->getType();

  BasicBlock *HeaderBB = State.CFG.PrevBB;
  assert(State.CurrentParentLoop->getHeader() == HeaderBB &&
         "recipe must be in the vector loop header");
  auto *Phi = PHINode::Create(VecTy, 2, "vec.phi");
  Phi->insertBefore(HeaderBB->getFirstInsertionPt());
  State.set(this, Phi, isInLoop());

  Phi->addIncoming(StartV, VectorPH);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPReductionPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                       VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-REDUCTION-PHI ";

  printAsOperand(O, SlotTracker);
  O << " = phi (";
  printRecurrenceKind(O, Kind);
  O << ")";
  printFlags(O);
  printOperands(O, SlotTracker);
  if (getVFScaleFactor() > 1)
    O << " (VF scaled by 1/" << getVFScaleFactor() << ")";
}
#endif

bool VPBlendRecipe::usesFirstLaneOnly(const VPValue *Op) const {
  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
  return vputils::onlyFirstLaneUsed(this);
}

void VPWidenPHIRecipe::execute(VPTransformState &State) {
  executePhiRecipe(this, *this, State, /*IsScalar=*/false, Name);
}

InstructionCost VPWidenPHIRecipe::computeCost(ElementCount VF,
                                              VPCostContext &Ctx) const {
  return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                   VPSlotTracker &SlotTracker) const {
  O << Indent << "WIDEN-PHI ";

  printAsOperand(O, SlotTracker);
  O << " = phi ";
  printPhiOperands(O, SlotTracker);
}
#endif

void VPActiveLaneMaskPHIRecipe::execute(VPTransformState &State) {
  BasicBlock *VectorPH =
      State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));
  Value *StartMask = State.get(getOperand(0));
  PHINode *Phi =
      State.Builder.CreatePHI(StartMask->getType(), 2, "active.lane.mask");
  Phi->addIncoming(StartMask, VectorPH);
  State.set(this, Phi);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPActiveLaneMaskPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
                                            VPSlotTracker &SlotTracker) const {
  O << Indent << "ACTIVE-LANE-MASK-PHI ";

  printAsOperand(O, SlotTracker);
  O << " = phi ";
  printOperands(O, SlotTracker);
}
#endif

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPCurrentIterationPHIRecipe::printRecipe(
    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
  O << Indent << "CURRENT-ITERATION-PHI ";

  printAsOperand(O, SlotTracker);
  O << " = phi ";
  printOperands(O, SlotTracker);
}
#endif