llvm/lib/Transforms/Vectorize/VPlan.h

//===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file contains the declarations of the Vectorization Plan base classes:
/// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual
///    VPBlockBase, together implementing a Hierarchical CFG;
/// 2. Pure virtual VPRecipeBase serving as the base class for recipes contained
///    within VPBasicBlocks;
/// 3. Pure virtual VPSingleDefRecipe serving as a base class for recipes that
///    also inherit from VPValue.
/// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
///    instruction;
/// 5. The VPlan class holding a candidate for vectorization;
/// These are documented in docs/VectorizationPlan.rst.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H

#include "VPlanValue.h"
#include "llvm/ADT/Bitfields.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/FMF.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/InstructionCost.h"
#include <cassert>
#include <cstddef>
#include <functional>
#include <optional>
#include <string>
#include <utility>
#include <variant>

namespace llvm {

class BasicBlock;
class DominatorTree;
class InnerLoopVectorizer;
class IRBuilderBase;
struct VPTransformState;
class raw_ostream;
class RecurrenceDescriptor;
class SCEV;
class SCEVPredicate;
class Type;
class VPBasicBlock;
struct VPBuilderDefaultInserter;
template <typename InserterTy = VPBuilderDefaultInserter> class VPBuilderBase;
using VPBuilder = VPBuilderBase<>;
class VPDominatorTree;
class VPRegionBlock;
class VPlan;
class VPLane;
class VPReplicateRecipe;
class Value;
class LoopVectorizationCostModel;

struct VPCostContext;

using VPlanPtr = std::unique_ptr<VPlan>;

/// \enum UncountableExitStyle
/// Different methods of handling early exits.
///
enum class UncountableExitStyle {
  /// No side effects to worry about, so we can process any uncountable exits
  /// in the loop and branch either to the middle block if the trip count was
  /// reached, or an early exitblock to determine which exit was taken.
  ReadOnly,
  /// All memory operations other than the load(s) required to determine whether
  /// an uncountable exit occurre will be masked based on that condition. If an
  /// uncountable exit is taken, then all lanes before the exiting lane will
  /// complete, leaving just the final lane to execute in the scalar tail.
  MaskedHandleExitInScalarLoop,
};

/// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
/// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
class LLVM_ABI_FOR_TEST VPBlockBase {
  friend class VPBlockUtils;

protected:
  /// An enumeration for keeping track of the concrete subclass of VPBlockBase
  /// that are actually instantiated. Values of this enumeration are kept in the
  /// SubclassID field of the VPBlockBase objects. They are used for concrete
  /// type identification.
  using VPBlockTy = enum : unsigned char {
    VPRegionBlockSC,
    VPBasicBlockSC,
    VPIRBasicBlockSC
  };

private:
  /// An optional name for the block.
  std::string Name;

  /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
  /// it is a topmost VPBlockBase.
  VPRegionBlock *Parent = nullptr;

  /// List of predecessor blocks.
  SmallVector<VPBlockBase *, 1> Predecessors;

  /// List of successor blocks.
  SmallVector<VPBlockBase *, 1> Successors;

  /// VPlan containing the block. Set when the block is created via VPlan
  /// helpers.
  VPlan *Plan = nullptr;

  /// Subclass identifier (for isa/dyn_cast).
  const VPBlockTy SubclassID;

  /// Unique number, used as node number in the dominator tree.
  unsigned Number;

  /// Add \p Successor as the last successor to this block.
  void appendSuccessor(VPBlockBase *Successor) {
    assert(Successor && "Cannot add nullptr successor!");
    Successors.push_back(Successor);
  }

  /// Add \p Predecessor as the last predecessor to this block.
  void appendPredecessor(VPBlockBase *Predecessor) {
    assert(Predecessor && "Cannot add nullptr predecessor!");
    Predecessors.push_back(Predecessor);
  }

  /// Remove \p Predecessor from the predecessors of this block.
  void removePredecessor(VPBlockBase *Predecessor) {
    auto Pos = find(Predecessors, Predecessor);
    assert(Pos && "Predecessor does not exist");
    Predecessors.erase(Pos);
  }

  /// Remove \p Successor from the successors of this block.
  void removeSuccessor(VPBlockBase *Successor) {
    auto Pos = find(Successors, Successor);
    assert(Pos && "Successor does not exist");
    Successors.erase(Pos);
  }

  /// This function replaces one predecessor with another, useful when
  /// trying to replace an old block in the CFG with a new one.
  void replacePredecessor(VPBlockBase *Old, VPBlockBase *New) {
    auto I = find(Predecessors, Old);
    assert(I != Predecessors.end());
    assert(Old->getParent() == New->getParent() &&
           "replaced predecessor must have the same parent");
    *I = New;
  }

  /// This function replaces one successor with another, useful when
  /// trying to replace an old block in the CFG with a new one.
  void replaceSuccessor(VPBlockBase *Old, VPBlockBase *New) {
    auto I = find(Successors, Old);
    assert(I != Successors.end());
    assert(Old->getParent() == New->getParent() &&
           "replaced successor must have the same parent");
    *I = New;
  }

public:
  using VPBlocksTy = SmallVectorImpl<VPBlockBase *>;

  virtual ~VPBlockBase() = default;

  const std::string &getName() const { return Name; }

  void setName(const Twine &newName) { Name = newName.str(); }

  /// \return an ID for the concrete type of this object.
  /// This is used to implement the classof checks. This should not be used
  /// for any other purpose, as the values may change as LLVM evolves.
  unsigned getVPBlockID() const { return SubclassID; }

  VPRegionBlock *getParent() { return Parent; }
  const VPRegionBlock *getParent() const { return Parent; }

  /// \return A pointer to the plan containing the current block.
  VPlan *getPlan() { return Plan; }
  const VPlan *getPlan() const { return Plan; }

  /// Sets the pointer of the plan containing the block.
  void setPlan(VPlan *ParentPlan) { Plan = ParentPlan; }

  void setParent(VPRegionBlock *P) { Parent = P; }

  /// \return the VPBasicBlock that is the entry of this VPBlockBase,
  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
  /// VPBlockBase is a VPBasicBlock, it is returned.
  const VPBasicBlock *getEntryBasicBlock() const;
  VPBasicBlock *getEntryBasicBlock();

  /// \return the VPBasicBlock that is the exiting this VPBlockBase,
  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
  /// VPBlockBase is a VPBasicBlock, it is returned.
  const VPBasicBlock *getExitingBasicBlock() const;
  VPBasicBlock *getExitingBasicBlock();

  const VPBlocksTy &getSuccessors() const { return Successors; }
  VPBlocksTy &getSuccessors() { return Successors; }

  /// Returns true if this block has any successors.
  bool hasSuccessors() const { return !Successors.empty(); }
  /// Returns true if this block has any predecessors.
  bool hasPredecessors() const { return !Predecessors.empty(); }

  iterator_range<VPBlockBase **> successors() { return Successors; }
  iterator_range<VPBlockBase **> predecessors() { return Predecessors; }

  const VPBlocksTy &getPredecessors() const { return Predecessors; }
  VPBlocksTy &getPredecessors() { return Predecessors; }

  /// \return the successor of this VPBlockBase if it has a single successor.
  /// Otherwise return a null pointer.
  VPBlockBase *getSingleSuccessor() const {
    return (Successors.size() == 1 ? *Successors.begin() : nullptr);
  }

  /// \return the predecessor of this VPBlockBase if it has a single
  /// predecessor. Otherwise return a null pointer.
  VPBlockBase *getSinglePredecessor() const {
    return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
  }

  size_t getNumSuccessors() const { return Successors.size(); }
  size_t getNumPredecessors() const { return Predecessors.size(); }

  /// An Enclosing Block of a block B is any block containing B, including B
  /// itself. \return the closest enclosing block starting from "this", which
  /// has successors. \return the root enclosing block if all enclosing blocks
  /// have no successors.
  VPBlockBase *getEnclosingBlockWithSuccessors();

  /// \return the closest enclosing block starting from "this", which has
  /// predecessors. \return the root enclosing block if all enclosing blocks
  /// have no predecessors.
  VPBlockBase *getEnclosingBlockWithPredecessors();

  /// \return the successors either attached directly to this VPBlockBase or, if
  /// this VPBlockBase is the exit block of a VPRegionBlock and has no
  /// successors of its own, search recursively for the first enclosing
  /// VPRegionBlock that has successors and return them. If no such
  /// VPRegionBlock exists, return the (empty) successors of the topmost
  /// VPBlockBase reached.
  const VPBlocksTy &getHierarchicalSuccessors() {
    return getEnclosingBlockWithSuccessors()->getSuccessors();
  }

  /// \return the hierarchical predecessor of this VPBlockBase if it has a
  /// single hierarchical predecessor. Otherwise return a null pointer.
  VPBlockBase *getSingleHierarchicalPredecessor() {
    return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
  }

  /// Set a given VPBlockBase \p Successor as the single successor of this
  /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
  /// This VPBlockBase must have no successors.
  void setOneSuccessor(VPBlockBase *Successor) {
    assert(Successors.empty() && "Setting one successor when others exist.");
    assert(Successor->getParent() == getParent() &&
           "connected blocks must have the same parent");
    appendSuccessor(Successor);
  }

  /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
  /// successors of this VPBlockBase. This VPBlockBase is not added as
  /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
  /// successors.
  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
    assert(Successors.empty() && "Setting two successors when others exist.");
    appendSuccessor(IfTrue);
    appendSuccessor(IfFalse);
  }

  /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
  /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
  /// as successor of any VPBasicBlock in \p NewPreds.
  void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {
    assert(Predecessors.empty() && "Block predecessors already set.");
    for (auto *Pred : NewPreds)
      appendPredecessor(Pred);
  }

  /// Set each VPBasicBlock in \p NewSuccss as successor of this VPBlockBase.
  /// This VPBlockBase must have no successors. This VPBlockBase is not added
  /// as predecessor of any VPBasicBlock in \p NewSuccs.
  void setSuccessors(ArrayRef<VPBlockBase *> NewSuccs) {
    assert(Successors.empty() && "Block successors already set.");
    for (auto *Succ : NewSuccs)
      appendSuccessor(Succ);
  }

  /// Remove all the predecessor of this block.
  void clearPredecessors() { Predecessors.clear(); }

  /// Remove all the successors of this block.
  void clearSuccessors() { Successors.clear(); }

  /// Swap predecessors of the block. The block must have exactly 2
  /// predecessors.
  void swapPredecessors() {
    assert(Predecessors.size() == 2 && "must have 2 predecessors to swap");
    std::swap(Predecessors[0], Predecessors[1]);
  }

  /// Swap successors of the block. The block must have exactly 2 successors.
  // TODO: This should be part of introducing conditional branch recipes rather
  // than being independent.
  void swapSuccessors() {
    assert(Successors.size() == 2 && "must have 2 successors to swap");
    std::swap(Successors[0], Successors[1]);
  }

  /// Returns the index for \p Pred in the blocks predecessors list.
  unsigned getIndexForPredecessor(const VPBlockBase *Pred) const {
    assert(count(Predecessors, Pred) == 1 &&
           "must have Pred exactly once in Predecessors");
    return std::distance(Predecessors.begin(), find(Predecessors, Pred));
  }

  /// Returns the index for \p Succ in the blocks successor list.
  unsigned getIndexForSuccessor(const VPBlockBase *Succ) const {
    assert(count(Successors, Succ) == 1 &&
           "must have Succ exactly once in Successors");
    return std::distance(Successors.begin(), find(Successors, Succ));
  }

  /// Return the unique number of the block.
  unsigned getNumber() const { return Number; }

  /// Set the unique number of the block, used for dominator tree.
  void setNumber(unsigned N) { Number = N; }

  /// The method which generates the output IR that correspond to this
  /// VPBlockBase, thereby "executing" the VPlan.
  virtual void execute(VPTransformState *State) = 0;

  /// Return the cost of the block.
  virtual InstructionCost cost(ElementCount VF, VPCostContext &Ctx) = 0;

  void printAsOperand(raw_ostream &OS, bool PrintType = false) const {
    OS << getName();
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines
  /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using
  /// consequtive numbers.
  ///
  /// Note that the numbering is applied to the whole VPlan, so printing
  /// individual blocks is consistent with the whole VPlan printing.
  virtual void print(raw_ostream &O, const Twine &Indent,
                     VPSlotTracker &SlotTracker) const = 0;

  /// Print plain-text dump of this VPlan to \p O.
  void print(raw_ostream &O) const;

  /// Print the successors of this block to \p O, prefixing all lines with \p
  /// Indent.
  void printSuccessors(raw_ostream &O, const Twine &Indent) const;

  /// Dump this VPBlockBase to dbgs().
  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
#endif

  /// Clone the current block and it's recipes without updating the operands of
  /// the cloned recipes, including all blocks in the single-entry single-exit
  /// region for VPRegionBlocks.
  virtual VPBlockBase *clone() = 0;

protected:
  VPBlockBase(VPBlockTy SC, const std::string &N) : Name(N), SubclassID(SC) {}
};

/// VPRecipeBase is a base class modeling a sequence of one or more output IR
/// instructions. VPRecipeBase owns the VPValues it defines through VPDef
/// and is responsible for deleting its defined values. Single-value
/// recipes must inherit from VPSingleDef instead of inheriting from both
/// VPRecipeBase and VPValue separately.
class LLVM_ABI_FOR_TEST VPRecipeBase
    : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
      public VPDef,
      public VPUser {
  friend VPBasicBlock;
  friend class VPBlockUtils;

  /// Each VPRecipe belongs to a single VPBasicBlock.
  VPBasicBlock *Parent = nullptr;

  /// The debug location for the recipe.
  DebugLoc DL;

public:
  /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
  /// that is actually instantiated. Values of this enumeration are kept in the
  /// SubclassID field of the VPRecipeBase objects. They are used for concrete
  /// type identification.
  using VPRecipeTy = enum : unsigned char {
    VPBranchOnMaskSC,
    VPDerivedIVSC,
    VPExpandSCEVSC,
    VPExpressionSC,
    VPIRInstructionSC,
    VPInstructionSC,
    VPInterleaveEVLSC,
    VPInterleaveSC,
    VPReductionEVLSC,
    VPReductionSC,
    VPReplicateSC,
    VPScalarIVStepsSC,
    VPVectorPointerSC,
    VPVectorEndPointerSC,
    VPWidenCallSC,
    VPWidenCanonicalIVSC,
    VPWidenCastSC,
    VPWidenGEPSC,
    VPWidenIntrinsicSC,
    VPWidenMemIntrinsicSC,
    VPWidenLoadEVLSC,
    VPWidenLoadSC,
    VPWidenStoreEVLSC,
    VPWidenStoreSC,
    VPWidenSC,
    VPBlendSC,
    VPHistogramSC,
    // START: Phi-like recipes. Need to be kept together.
    VPWidenPHISC,
    VPPredInstPHISC,
    // START: SubclassID for recipes that inherit VPHeaderPHIRecipe.
    // VPHeaderPHIRecipe need to be kept together.
    VPCurrentIterationPHISC,
    VPActiveLaneMaskPHISC,
    VPFirstOrderRecurrencePHISC,
    VPWidenIntOrFpInductionSC,
    VPWidenPointerInductionSC,
    VPReductionPHISC,
    // END: SubclassID for recipes that inherit VPHeaderPHIRecipe
    // END: Phi-like recipes
    VPFirstPHISC = VPWidenPHISC,
    VPFirstHeaderPHISC = VPCurrentIterationPHISC,
    VPLastHeaderPHISC = VPReductionPHISC,
    VPLastPHISC = VPReductionPHISC,
  };

  VPRecipeBase(VPRecipeTy SC, ArrayRef<VPValue *> Operands,
               DebugLoc DL = DebugLoc::getUnknown())
      : VPDef(), VPUser(Operands), DL(DL), SubclassID(SC) {}

  ~VPRecipeBase() override = default;

  /// Clone the current recipe.
  virtual VPRecipeBase *clone() = 0;

  /// \return the VPBasicBlock which this VPRecipe belongs to.
  VPBasicBlock *getParent() { return Parent; }
  const VPBasicBlock *getParent() const { return Parent; }

  /// \return the VPRegionBlock which the recipe belongs to.
  VPRegionBlock *getRegion();
  const VPRegionBlock *getRegion() const;

  /// The method which generates the output IR instructions that correspond to
  /// this VPRecipe, thereby "executing" the VPlan.
  virtual void execute(VPTransformState &State) = 0;

  /// Return the cost of this recipe, taking into account if the cost
  /// computation should be skipped and the ForceTargetInstructionCost flag.
  /// Also takes care of printing the cost for debugging.
  InstructionCost cost(ElementCount VF, VPCostContext &Ctx);

  /// Insert an unlinked recipe into a basic block immediately before
  /// the specified recipe.
  void insertBefore(VPRecipeBase *InsertPos);
  /// Insert an unlinked recipe into \p BB immediately before the insertion
  /// point \p IP;
  void insertBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator IP);

  /// Insert an unlinked Recipe into a basic block immediately after
  /// the specified Recipe.
  void insertAfter(VPRecipeBase *InsertPos);

  /// Unlink this recipe from its current VPBasicBlock and insert it into
  /// the VPBasicBlock that MovePos lives in, right after MovePos.
  void moveAfter(VPRecipeBase *MovePos);

  /// Unlink this recipe and insert into BB before I.
  ///
  /// \pre I is a valid iterator into BB.
  void moveBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator I);

  /// This method unlinks 'this' from the containing basic block, but does not
  /// delete it.
  void removeFromParent();

  /// This method unlinks 'this' from the containing basic block and deletes it.
  ///
  /// \returns an iterator pointing to the element after the erased one
  iplist<VPRecipeBase>::iterator eraseFromParent();

  /// \return an ID for the concrete type of this object.
  VPRecipeTy getVPRecipeID() const { return SubclassID; }

  /// Method to support type inquiry through isa, cast, and dyn_cast.
  static inline bool classof(const VPDef *D) {
    // All VPDefs are also VPRecipeBases.
    return true;
  }

  static inline bool classof(const VPUser *U) { return true; }

  /// Returns true if the recipe may have side-effects.
  bool mayHaveSideEffects() const;

  /// Return true if we can safely execute this recipe unconditionally even if
  /// it is masked originally.
  bool isSafeToSpeculativelyExecute() const;

  /// Returns true for PHI-like recipes.
  bool isPhi() const;

  /// Returns true if the recipe may read from memory.
  bool mayReadFromMemory() const;

  /// Returns true if the recipe may write to memory.
  bool mayWriteToMemory() const;

  /// Returns true if the recipe may read from or write to memory.
  bool mayReadOrWriteMemory() const {
    return mayReadFromMemory() || mayWriteToMemory();
  }

  /// Returns the debug location of the recipe.
  DebugLoc getDebugLoc() const { return DL; }

  /// Set the recipe's debug location to \p NewDL.
  void setDebugLoc(DebugLoc NewDL) { DL = NewDL; }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Dump the recipe to stderr (for debugging).
  void dump() const;

  /// Print the recipe, delegating to printRecipe().
  void print(raw_ostream &O, const Twine &Indent,
             VPSlotTracker &SlotTracker) const;
#endif

private:
  /// Subclass identifier (for isa/dyn_cast).
  const VPRecipeTy SubclassID;

protected:
  /// Compute the cost of this recipe either using a recipe's specialized
  /// implementation or using the legacy cost model and the underlying
  /// instructions.
  virtual InstructionCost computeCost(ElementCount VF,
                                      VPCostContext &Ctx) const;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Each concrete VPRecipe prints itself, without printing common information,
  /// like debug info or metadata.
  virtual void printRecipe(raw_ostream &O, const Twine &Indent,
                           VPSlotTracker &SlotTracker) const = 0;
#endif
};

// Helper macro to define common classof implementations for recipes.
#define VP_CLASSOF_IMPL(VPRecipeID)                                            \
  static inline bool classof(const VPRecipeBase *R) {                          \
    return R->getVPRecipeID() == VPRecipeID;                                   \
  }                                                                            \
  static inline bool classof(const VPValue *V) {                               \
    auto *R = V->getDefiningRecipe();                                          \
    return R && R->getVPRecipeID() == VPRecipeID;                              \
  }                                                                            \
  static inline bool classof(const VPUser *U) {                                \
    auto *R = dyn_cast<VPRecipeBase>(U);                                       \
    return R && R->getVPRecipeID() == VPRecipeID;                              \
  }                                                                            \
  static inline bool classof(const VPSingleDefRecipe *R) {                     \
    return R->getVPRecipeID() == VPRecipeID;                                   \
  }

/// Compute the scalar result type for an IR \p Opcode given \p Operands.
LLVM_ABI Type *computeScalarTypeForInstruction(unsigned Opcode,
                                               ArrayRef<VPValue *> Operands);

/// VPSingleDefRecipe is a base class for recipes that model a sequence of one
/// or more output IR that define a single result VPValue. Note that
/// VPSingleDefRecipe must inherit from VPRecipeBase before VPSingleDefValue.
class LLVM_ABI_FOR_TEST VPSingleDefRecipe : public VPRecipeBase,
                                            public VPSingleDefValue {
public:
  VPSingleDefRecipe(VPRecipeTy SC, ArrayRef<VPValue *> Operands,
                    DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeBase(SC, Operands, DL), VPSingleDefValue(this) {}

  VPSingleDefRecipe(VPRecipeTy SC, ArrayRef<VPValue *> Operands, Value *UV,
                    DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeBase(SC, Operands, DL), VPSingleDefValue(this, UV) {}

  VPSingleDefRecipe(VPRecipeTy SC, ArrayRef<VPValue *> Operands, Type *ResultTy,
                    Value *UV = nullptr, DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeBase(SC, Operands, DL), VPSingleDefValue(this, UV, ResultTy) {}

  static inline bool classof(const VPRecipeBase *R) {
    switch (R->getVPRecipeID()) {
    case VPRecipeBase::VPDerivedIVSC:
    case VPRecipeBase::VPExpandSCEVSC:
    case VPRecipeBase::VPExpressionSC:
    case VPRecipeBase::VPInstructionSC:
    case VPRecipeBase::VPReductionEVLSC:
    case VPRecipeBase::VPReductionSC:
    case VPRecipeBase::VPReplicateSC:
    case VPRecipeBase::VPScalarIVStepsSC:
    case VPRecipeBase::VPVectorPointerSC:
    case VPRecipeBase::VPVectorEndPointerSC:
    case VPRecipeBase::VPWidenCallSC:
    case VPRecipeBase::VPWidenCanonicalIVSC:
    case VPRecipeBase::VPWidenCastSC:
    case VPRecipeBase::VPWidenGEPSC:
    case VPRecipeBase::VPWidenIntrinsicSC:
    case VPRecipeBase::VPWidenMemIntrinsicSC:
    case VPRecipeBase::VPWidenSC:
    case VPRecipeBase::VPBlendSC:
    case VPRecipeBase::VPPredInstPHISC:
    case VPRecipeBase::VPCurrentIterationPHISC:
    case VPRecipeBase::VPActiveLaneMaskPHISC:
    case VPRecipeBase::VPFirstOrderRecurrencePHISC:
    case VPRecipeBase::VPWidenPHISC:
    case VPRecipeBase::VPWidenIntOrFpInductionSC:
    case VPRecipeBase::VPWidenPointerInductionSC:
    case VPRecipeBase::VPReductionPHISC:
    case VPRecipeBase::VPWidenLoadEVLSC:
    case VPRecipeBase::VPWidenLoadSC:
      return true;
    case VPRecipeBase::VPBranchOnMaskSC:
    case VPRecipeBase::VPInterleaveEVLSC:
    case VPRecipeBase::VPInterleaveSC:
    case VPRecipeBase::VPIRInstructionSC:
    case VPRecipeBase::VPWidenStoreEVLSC:
    case VPRecipeBase::VPWidenStoreSC:
    case VPRecipeBase::VPHistogramSC:
      return false;
    }
    llvm_unreachable("Unhandled VPRecipeID");
  }

  static inline bool classof(const VPValue *V) {
    auto *R = V->getDefiningRecipe();
    return R && classof(R);
  }

  static inline bool classof(const VPUser *U) {
    auto *R = dyn_cast<VPRecipeBase>(U);
    return R && classof(R);
  }

  VPSingleDefRecipe *clone() override = 0;

  /// Returns the underlying instruction.
  Instruction *getUnderlyingInstr() {
    return cast<Instruction>(getUnderlyingValue());
  }
  const Instruction *getUnderlyingInstr() const {
    return cast<Instruction>(getUnderlyingValue());
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print this VPSingleDefRecipe to dbgs() (for debugging).
  LLVM_DUMP_METHOD void dump() const;
#endif
};

/// Class to record and manage LLVM IR flags.
LLVM_PACKED_START
class VPIRFlags {
  enum class OperationType : unsigned char {
    Cmp,
    FCmp,
    OverflowingBinOp,
    Trunc,
    DisjointOp,
    PossiblyExactOp,
    GEPOp,
    FPMathOp,
    NonNegOp,
    ReductionOp,
    Other
  };

public:
  struct WrapFlagsTy {
    char HasNUW : 1;
    char HasNSW : 1;

    WrapFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}
    WrapFlagsTy() : HasNUW(false), HasNSW(false) {}
  };

  struct TruncFlagsTy {
    char HasNUW : 1;
    char HasNSW : 1;

    TruncFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}
  };

  struct DisjointFlagsTy {
    char IsDisjoint : 1;
    DisjointFlagsTy(bool IsDisjoint) : IsDisjoint(IsDisjoint) {}
  };

  struct NonNegFlagsTy {
    char NonNeg : 1;
    NonNegFlagsTy(bool IsNonNeg) : NonNeg(IsNonNeg) {}
  };

private:
  struct ExactFlagsTy {
    char IsExact : 1;
    ExactFlagsTy(bool Exact) : IsExact(Exact) {}
  };
  struct FastMathFlagsTy {
    char AllowReassoc : 1;
    char NoNaNs : 1;
    char NoInfs : 1;
    char NoSignedZeros : 1;
    char AllowReciprocal : 1;
    char AllowContract : 1;
    char ApproxFunc : 1;

    LLVM_ABI_FOR_TEST FastMathFlagsTy(const FastMathFlags &FMF);
  };
  /// Holds both the predicate and fast-math flags for floating-point
  /// comparisons.
  struct FCmpFlagsTy {
    uint8_t CmpPredStorage;
    FastMathFlagsTy FMFs;
  };
  /// Holds reduction-specific flags: RecurKind, IsOrdered, IsInLoop, and FMFs.
  struct ReductionFlagsTy {
    // RecurKind has ~26 values, needs 5 bits but uses 6 bits to account for
    // additional kinds.
    unsigned char Kind : 6;
    // TODO: Derive order/in-loop from plan and remove here.
    unsigned char IsOrdered : 1;
    unsigned char IsInLoop : 1;
    FastMathFlagsTy FMFs;

    ReductionFlagsTy(RecurKind Kind, bool IsOrdered, bool IsInLoop,
                     FastMathFlags FMFs)
        : Kind(static_cast<unsigned char>(Kind)), IsOrdered(IsOrdered),
          IsInLoop(IsInLoop), FMFs(FMFs) {}
  };

  OperationType OpType;

  union {
    uint8_t CmpPredStorage;
    WrapFlagsTy WrapFlags;
    TruncFlagsTy TruncFlags;
    DisjointFlagsTy DisjointFlags;
    ExactFlagsTy ExactFlags;
    uint8_t GEPFlagsStorage;
    NonNegFlagsTy NonNegFlags;
    FastMathFlagsTy FMFs;
    FCmpFlagsTy FCmpFlags;
    ReductionFlagsTy ReductionFlags;
    uint8_t AllFlags[2];
  };

public:
  VPIRFlags() : OpType(OperationType::Other), AllFlags() {}

  VPIRFlags(Instruction &I) : VPIRFlags() {
    if (auto *FCmp = dyn_cast<FCmpInst>(&I)) {
      OpType = OperationType::FCmp;
      Bitfield::set<CmpInst::PredicateField>(FCmpFlags.CmpPredStorage,
                                             FCmp->getPredicate());
      assert(getPredicate() == FCmp->getPredicate() && "predicate truncated");
      FCmpFlags.FMFs = FCmp->getFastMathFlags();
    } else if (auto *Op = dyn_cast<CmpInst>(&I)) {
      OpType = OperationType::Cmp;
      Bitfield::set<CmpInst::PredicateField>(CmpPredStorage,
                                             Op->getPredicate());
      assert(getPredicate() == Op->getPredicate() && "predicate truncated");
    } else if (auto *Op = dyn_cast<PossiblyDisjointInst>(&I)) {
      OpType = OperationType::DisjointOp;
      DisjointFlags.IsDisjoint = Op->isDisjoint();
    } else if (auto *Op = dyn_cast<OverflowingBinaryOperator>(&I)) {
      OpType = OperationType::OverflowingBinOp;
      WrapFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};
    } else if (auto *Op = dyn_cast<TruncInst>(&I)) {
      OpType = OperationType::Trunc;
      TruncFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};
    } else if (auto *Op = dyn_cast<PossiblyExactOperator>(&I)) {
      OpType = OperationType::PossiblyExactOp;
      ExactFlags.IsExact = Op->isExact();
    } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
      OpType = OperationType::GEPOp;
      GEPFlagsStorage = GEP->getNoWrapFlags().getRaw();
      assert(getGEPNoWrapFlags() == GEP->getNoWrapFlags() &&
             "wrap flags truncated");
    } else if (auto *PNNI = dyn_cast<PossiblyNonNegInst>(&I)) {
      OpType = OperationType::NonNegOp;
      NonNegFlags.NonNeg = PNNI->hasNonNeg();
    } else if (auto *Op = dyn_cast<FPMathOperator>(&I)) {
      OpType = OperationType::FPMathOp;
      FMFs = Op->getFastMathFlags();
    }
  }

  VPIRFlags(CmpInst::Predicate Pred) : OpType(OperationType::Cmp), AllFlags() {
    Bitfield::set<CmpInst::PredicateField>(CmpPredStorage, Pred);
    assert(getPredicate() == Pred && "predicate truncated");
  }

  VPIRFlags(CmpInst::Predicate Pred, FastMathFlags FMFs)
      : OpType(OperationType::FCmp), AllFlags() {
    Bitfield::set<CmpInst::PredicateField>(FCmpFlags.CmpPredStorage, Pred);
    assert(getPredicate() == Pred && "predicate truncated");
    FCmpFlags.FMFs = FMFs;
  }

  VPIRFlags(WrapFlagsTy WrapFlags)
      : OpType(OperationType::OverflowingBinOp), AllFlags() {
    this->WrapFlags = WrapFlags;
  }

  VPIRFlags(TruncFlagsTy TruncFlags)
      : OpType(OperationType::Trunc), AllFlags() {
    this->TruncFlags = TruncFlags;
  }

  VPIRFlags(FastMathFlags FMFs) : OpType(OperationType::FPMathOp), AllFlags() {
    this->FMFs = FMFs;
  }

  VPIRFlags(DisjointFlagsTy DisjointFlags)
      : OpType(OperationType::DisjointOp), AllFlags() {
    this->DisjointFlags = DisjointFlags;
  }

  VPIRFlags(NonNegFlagsTy NonNegFlags)
      : OpType(OperationType::NonNegOp), AllFlags() {
    this->NonNegFlags = NonNegFlags;
  }

  VPIRFlags(ExactFlagsTy ExactFlags)
      : OpType(OperationType::PossiblyExactOp), AllFlags() {
    this->ExactFlags = ExactFlags;
  }

  VPIRFlags(GEPNoWrapFlags GEPFlags)
      : OpType(OperationType::GEPOp), AllFlags() {
    GEPFlagsStorage = GEPFlags.getRaw();
  }

  VPIRFlags(RecurKind Kind, bool IsOrdered, bool IsInLoop, FastMathFlags FMFs)
      : OpType(OperationType::ReductionOp), AllFlags() {
    ReductionFlags = ReductionFlagsTy(Kind, IsOrdered, IsInLoop, FMFs);
  }

  void transferFlags(VPIRFlags &Other) {
    OpType = Other.OpType;
    AllFlags[0] = Other.AllFlags[0];
    AllFlags[1] = Other.AllFlags[1];
  }

  /// Only keep flags also present in \p Other. \p Other must have the same
  /// OpType as the current object.
  void intersectFlags(const VPIRFlags &Other);

  /// Drop all poison-generating flags.
  void dropPoisonGeneratingFlags() {
    // NOTE: This needs to be kept in-sync with
    // Instruction::dropPoisonGeneratingFlags.
    switch (OpType) {
    case OperationType::OverflowingBinOp:
      WrapFlags.HasNUW = false;
      WrapFlags.HasNSW = false;
      break;
    case OperationType::Trunc:
      TruncFlags.HasNUW = false;
      TruncFlags.HasNSW = false;
      break;
    case OperationType::DisjointOp:
      DisjointFlags.IsDisjoint = false;
      break;
    case OperationType::PossiblyExactOp:
      ExactFlags.IsExact = false;
      break;
    case OperationType::GEPOp:
      GEPFlagsStorage = 0;
      break;
    case OperationType::FPMathOp:
    case OperationType::FCmp:
    case OperationType::ReductionOp:
      getFMFsRef().NoNaNs = false;
      getFMFsRef().NoInfs = false;
      break;
    case OperationType::NonNegOp:
      NonNegFlags.NonNeg = false;
      break;
    case OperationType::Cmp:
    case OperationType::Other:
      break;
    }
  }

  /// Apply the IR flags to \p I.
  void applyFlags(Instruction &I) const {
    switch (OpType) {
    case OperationType::OverflowingBinOp:
      I.setHasNoUnsignedWrap(WrapFlags.HasNUW);
      I.setHasNoSignedWrap(WrapFlags.HasNSW);
      break;
    case OperationType::Trunc:
      I.setHasNoUnsignedWrap(TruncFlags.HasNUW);
      I.setHasNoSignedWrap(TruncFlags.HasNSW);
      break;
    case OperationType::DisjointOp:
      cast<PossiblyDisjointInst>(&I)->setIsDisjoint(DisjointFlags.IsDisjoint);
      break;
    case OperationType::PossiblyExactOp:
      I.setIsExact(ExactFlags.IsExact);
      break;
    case OperationType::GEPOp:
      cast<GetElementPtrInst>(&I)->setNoWrapFlags(
          GEPNoWrapFlags::fromRaw(GEPFlagsStorage));
      break;
    case OperationType::FPMathOp:
    case OperationType::FCmp: {
      const FastMathFlagsTy &F = getFMFsRef();
      I.setHasAllowReassoc(F.AllowReassoc);
      I.setHasNoNaNs(F.NoNaNs);
      I.setHasNoInfs(F.NoInfs);
      I.setHasNoSignedZeros(F.NoSignedZeros);
      I.setHasAllowReciprocal(F.AllowReciprocal);
      I.setHasAllowContract(F.AllowContract);
      I.setHasApproxFunc(F.ApproxFunc);
      break;
    }
    case OperationType::NonNegOp:
      I.setNonNeg(NonNegFlags.NonNeg);
      break;
    case OperationType::ReductionOp:
      llvm_unreachable("reduction ops should not use applyFlags");
    case OperationType::Cmp:
    case OperationType::Other:
      break;
    }
  }

  CmpInst::Predicate getPredicate() const {
    assert((OpType == OperationType::Cmp || OpType == OperationType::FCmp) &&
           "recipe doesn't have a compare predicate");
    uint8_t Storage = OpType == OperationType::FCmp ? FCmpFlags.CmpPredStorage
                                                    : CmpPredStorage;
    return Bitfield::get<CmpInst::PredicateField>(Storage);
  }

  void setPredicate(CmpInst::Predicate Pred) {
    assert((OpType == OperationType::Cmp || OpType == OperationType::FCmp) &&
           "recipe doesn't have a compare predicate");
    if (OpType == OperationType::FCmp)
      Bitfield::set<CmpInst::PredicateField>(FCmpFlags.CmpPredStorage, Pred);
    else
      Bitfield::set<CmpInst::PredicateField>(CmpPredStorage, Pred);
    assert(getPredicate() == Pred && "predicate truncated");
  }

  GEPNoWrapFlags getGEPNoWrapFlags() const {
    return GEPNoWrapFlags::fromRaw(GEPFlagsStorage);
  }

  /// Returns true if the recipe has a comparison predicate.
  bool hasPredicate() const {
    return OpType == OperationType::Cmp || OpType == OperationType::FCmp;
  }

  /// Returns true if the recipe has fast-math flags.
  bool hasFastMathFlags() const {
    return OpType == OperationType::FPMathOp || OpType == OperationType::FCmp ||
           OpType == OperationType::ReductionOp;
  }

  LLVM_ABI_FOR_TEST FastMathFlags getFastMathFlagsOrNone() const;

  bool hasNoUnsignedWrap() const {
    switch (OpType) {
    case OperationType::OverflowingBinOp:
      return WrapFlags.HasNUW;
    case OperationType::Trunc:
      return TruncFlags.HasNUW;
    default:
      llvm_unreachable("recipe doesn't have a NUW flag");
    }
  }

  bool hasNoSignedWrap() const {
    switch (OpType) {
    case OperationType::OverflowingBinOp:
      return WrapFlags.HasNSW;
    case OperationType::Trunc:
      return TruncFlags.HasNSW;
    default:
      llvm_unreachable("recipe doesn't have a NSW flag");
    }
  }

  WrapFlagsTy getNoWrapFlagsOrNone() const {
    switch (OpType) {
    case OperationType::OverflowingBinOp:
    case OperationType::Trunc:
      return {hasNoUnsignedWrap(), hasNoSignedWrap()};
    default:
      return {};
    }
  }

  WrapFlagsTy getNoWrapFlags() const {
    return {hasNoUnsignedWrap(), hasNoSignedWrap()};
  }

  bool isDisjoint() const {
    assert(OpType == OperationType::DisjointOp &&
           "recipe cannot have a disjoing flag");
    return DisjointFlags.IsDisjoint;
  }

  RecurKind getRecurKind() const {
    assert(OpType == OperationType::ReductionOp &&
           "recipe doesn't have reduction flags");
    return static_cast<RecurKind>(ReductionFlags.Kind);
  }

  bool isReductionOrdered() const {
    assert(OpType == OperationType::ReductionOp &&
           "recipe doesn't have reduction flags");
    return ReductionFlags.IsOrdered;
  }

  bool isReductionInLoop() const {
    assert(OpType == OperationType::ReductionOp &&
           "recipe doesn't have reduction flags");
    return ReductionFlags.IsInLoop;
  }

private:
  /// Get a reference to the fast-math flags for FPMathOp, FCmp or ReductionOp.
  FastMathFlagsTy &getFMFsRef() {
    if (OpType == OperationType::FCmp)
      return FCmpFlags.FMFs;
    if (OpType == OperationType::ReductionOp)
      return ReductionFlags.FMFs;
    return FMFs;
  }
  const FastMathFlagsTy &getFMFsRef() const {
    if (OpType == OperationType::FCmp)
      return FCmpFlags.FMFs;
    if (OpType == OperationType::ReductionOp)
      return ReductionFlags.FMFs;
    return FMFs;
  }

public:
  /// Returns default flags for \p Opcode and scalar \p ResultTy for opcodes
  /// that support it, asserts otherwise. Opcodes not supporting default flags
  /// include compares and ComputeReductionResult.
  LLVM_ABI_FOR_TEST static VPIRFlags getDefaultFlags(unsigned Opcode,
                                                     Type *ResultTy = nullptr);

#if !defined(NDEBUG)
  /// Returns true if the set flags are valid for \p Opcode.
  LLVM_ABI_FOR_TEST bool flagsValidForOpcode(unsigned Opcode) const;

  /// Returns true if \p Opcode with scalar result type \p ResultTy has its
  /// required flags set.
  LLVM_ABI_FOR_TEST bool hasRequiredFlagsForOpcode(unsigned Opcode,
                                                   Type *ResultTy) const;
#endif

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void printFlags(raw_ostream &O) const;
#endif
};
LLVM_PACKED_END

static_assert(sizeof(VPIRFlags) <= 3, "VPIRFlags should not grow");

/// A pure-virtual common base class for recipes defining a single VPValue and
/// using IR flags.
struct VPRecipeWithIRFlags : public VPSingleDefRecipe, public VPIRFlags {
  VPRecipeWithIRFlags(VPRecipeTy SC, ArrayRef<VPValue *> Operands,
                      const VPIRFlags &Flags,
                      DebugLoc DL = DebugLoc::getUnknown())
      : VPSingleDefRecipe(SC, Operands, DL), VPIRFlags(Flags) {}

  VPRecipeWithIRFlags(VPRecipeTy SC, ArrayRef<VPValue *> Operands,
                      Type *ResultTy, const VPIRFlags &Flags,
                      DebugLoc DL = DebugLoc::getUnknown())
      : VPSingleDefRecipe(SC, Operands, ResultTy, /*UV=*/nullptr, DL),
        VPIRFlags(Flags) {}

  static inline bool classof(const VPRecipeBase *R) {
    return R->getVPRecipeID() == VPRecipeBase::VPBlendSC ||
           R->getVPRecipeID() == VPRecipeBase::VPInstructionSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenGEPSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenCallSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenCastSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenIntrinsicSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenMemIntrinsicSC ||
           R->getVPRecipeID() == VPRecipeBase::VPReductionSC ||
           R->getVPRecipeID() == VPRecipeBase::VPReductionEVLSC ||
           R->getVPRecipeID() == VPRecipeBase::VPReplicateSC ||
           R->getVPRecipeID() == VPRecipeBase::VPVectorEndPointerSC ||
           R->getVPRecipeID() == VPRecipeBase::VPVectorPointerSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenCanonicalIVSC ||
           R->getVPRecipeID() == VPRecipeBase::VPDerivedIVSC;
  }

  static inline bool classof(const VPUser *U) {
    auto *R = dyn_cast<VPRecipeBase>(U);
    return R && classof(R);
  }

  static inline bool classof(const VPValue *V) {
    auto *R = V->getDefiningRecipe();
    return R && classof(R);
  }

  VPRecipeWithIRFlags *clone() override = 0;

  static inline bool classof(const VPSingleDefRecipe *R) {
    return classof(static_cast<const VPRecipeBase *>(R));
  }

  void execute(VPTransformState &State) override = 0;

  /// Compute the cost for this recipe for \p VF, using \p Opcode and \p Ctx.
  InstructionCost getCostForRecipeWithOpcode(unsigned Opcode, ElementCount VF,
                                             VPCostContext &Ctx) const;
};

/// The frequency with which a recipe executes, relative to the entry of the
/// loop region. IsEstimated is set if any branch weight it was composed from
/// was estimated from static heuristics.
struct VPExecutionFrequency {
  const BlockFrequency Freq;
  const bool IsEstimated;

  VPExecutionFrequency(BlockFrequency Freq, bool IsEstimated)
      : Freq(Freq), IsEstimated(IsEstimated) {
    assert(Freq > BlockFrequency() && "execution frequency must be non-zero");
  }
};

/// Helper to manage IR metadata for recipes. It filters out metadata that
/// cannot be propagated.
class LLVM_ABI_FOR_TEST VPIRMetadata {
  SmallVector<std::pair<unsigned, MDNode *>> Metadata;

  /// Name of the VPlan-internal metadata kind holding the execution frequency.
  static constexpr StringLiteral ExecutionFrequencyMDName =
      "vplan.execution.frequency";

  /// Name of the VPlan-internal metadata kind holding estimated branch weights.
  static constexpr StringLiteral EstimatedProfileMDName =
      "vplan.prof.estimated";

  /// Returns the ID of the metadata kind named \p Kind, taking the context from
  /// any attached node; all belong to the context of the VPlan's function.
  unsigned getMDKindID(StringRef Kind) const {
    assert(!Metadata.empty() && "no node to take the context from");
    return Metadata.front().second->getContext().getMDKindID(Kind);
  }

  /// Returns the node attached under the VPlan-internal metadata kind named
  /// \p Kind, or nullptr if there is none.
  MDNode *getInternalMetadata(StringRef Kind) const {
    return Metadata.empty() ? nullptr : getMetadata(getMDKindID(Kind));
  }

public:
  VPIRMetadata() = default;

  /// Adds metatadata that can be preserved from the original instruction
  /// \p I.
  VPIRMetadata(Instruction &I) {
    getMetadataToPropagate(&I, Metadata);
    // Retain the branch weights of terminators. They are used to compute the
    // frequencies with which the blocks of the original loop execute. Also
    // retain !prof on selects.
    if (I.isTerminator() || isa<SelectInst>(&I))
      if (MDNode *BW = I.getMetadata(LLVMContext::MD_prof))
        Metadata.emplace_back(LLVMContext::MD_prof, BW);
  }

  /// Copy constructor for cloning.
  VPIRMetadata(const VPIRMetadata &Other) = default;

  VPIRMetadata &operator=(const VPIRMetadata &Other) = default;

  /// Add all metadata to \p I.
  void applyMetadata(Instruction &I) const;

  /// Set metadata with kind \p Kind to \p Node. If metadata with \p Kind
  /// already exists, it will be replaced. Otherwise, it will be added.
  void setMetadata(unsigned Kind, MDNode *Node) {
    auto It =
        llvm::find_if(Metadata, [Kind](const std::pair<unsigned, MDNode *> &P) {
          return P.first == Kind;
        });
    if (It != Metadata.end())
      It->second = Node;
    else
      Metadata.emplace_back(Kind, Node);
  }

  /// Remove the metadata of kind \p Kind, if present.
  void eraseMetadata(unsigned Kind) {
    erase_if(Metadata, [Kind](const auto &P) { return P.first == Kind; });
  }

  /// Intersect this VPIRMetadata object with \p MD, keeping only metadata
  /// nodes that are common to both.
  void intersect(const VPIRMetadata &MD);

  /// Get metadata of kind \p Kind. Returns nullptr if not found.
  MDNode *getMetadata(unsigned Kind) const {
    auto It =
        find_if(Metadata, [Kind](const auto &P) { return P.first == Kind; });
    return It != Metadata.end() ? It->second : nullptr;
  }

  /// Record that the recipe executes with frequency \p Freq, relative to the
  /// entry of the loop region.
  void setExecutionFrequency(std::optional<VPExecutionFrequency> Freq,
                             LLVMContext &Ctx);

  /// Returns the frequency recorded by setExecutionFrequency, if any.
  std::optional<VPExecutionFrequency> getExecutionFrequency() const;

  /// Drop the frequency recorded by setExecutionFrequency, if any.
  void clearExecutionFrequency();

  /// Returns the branch weights recorded for this terminator, preferring real
  /// profile data over an estimate, or nullptr if there are none.
  MDNode *getBranchWeights() const {
    MDNode *Node = getMetadata(LLVMContext::MD_prof);
    return Node ? Node : getInternalMetadata(EstimatedProfileMDName);
  }

  /// Returns true if the weights returned by getBranchWeights are estimated.
  bool hasEstimatedBranchWeights() const {
    return getInternalMetadata(EstimatedProfileMDName);
  }

  /// Set estimated branch weights to \p Node.
  void setEstimatedBranchWeights(MDNode *Node) {
    assert(!getMetadata(LLVMContext::MD_prof) &&
           "real profile data takes precedence over an estimate");
    setMetadata(Node->getContext().getMDKindID(EstimatedProfileMDName), Node);
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print metadata with node IDs.
  void print(raw_ostream &O, VPSlotTracker &SlotTracker) const;
#endif
};

/// This is a concrete Recipe that models a single VPlan-level instruction.
/// While as any Recipe it may generate a sequence of IR instructions when
/// executed, these instructions would always form a single-def expression as
/// the VPInstruction is also a single def-use vertex. Most VPInstruction
/// opcodes can take an optional mask. Masks may be assigned during
/// predication.
class LLVM_ABI_FOR_TEST VPInstruction : public VPRecipeWithIRFlags,
                                        public VPIRMetadata {
public:
  /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
  enum {
    FirstOrderRecurrenceSplice = Instruction::OtherOpsEnd +
        1, // Combines the incoming and previous
           // values of a first-order recurrence.
    Not,
    // Creates a mask where each lane is active (true) whilst the current
    // counter (first operand + index) is less than the second operand. i.e.
    //    mask[i] = icmpt ult (op0 + i), op1
    // ActiveLaneMask is used for early-exit loops with stores, plus tail
    // folding for all styles except DataAndControlFlow. The size of the
    // mask returned is VF. When unrolled, ActiveLaneMask is duplicated.
    ActiveLaneMask,
    // As above, but takes an additional operand (Multiplier). The size of
    // the mask returned is VF * Multiplier (UF, op2).
    // WideActiveLaneMask is used for control flow and is unrolled by widening,
    // with one extract vector created per unroll part.
    WideActiveLaneMask,
    // Signature: Vectors... -> WideVector
    // Concatenates all vector operands to a single wide vector.
    ConcatVectors,
    // Signature: (Multiplier, Address, Align) -> Vector
    // Loads a single wide vector of `Multiplier * VF` elements.
    WideVectorLoad,
    // Signature: (Multiplier, Address, Alignment, Vector)
    // Stores a single wide vector of `Multiplier * VF` elements.
    WideVectorStore,
    // Extracts each unrolled part of a (VF * UF) widened vector/mask.
    ExtractVectorForPart,
    ExplicitVectorLength,
    // Represents the incoming loop-invariant alias-mask. All memory accesses
    // in the loop must stay within the active lanes.
    IncomingAliasMask,
    // Increment the canonical IV separately for each unrolled part.
    CanonicalIVIncrementForPart,
    // Abstract instruction that compares two values and branches. This is
    // lowered to ICmp + BranchOnCond during VPlan to VPlan transformation.
    BranchOnCount,
    BranchOnCond,
    // Branch with 2 boolean condition operands and 3 successors. If condition
    // 0 is true, branches to successor 0; if condition 1 is true, branches to
    // successor 1; otherwise branches to successor 2. Expanded after region
    // dissolution into: (1) an OR of the two conditions branching to
    // middle.split or successor 2, and (2) middle.split branching to successor
    // 0 or successor 1 based on condition 0.
    BranchOnTwoConds,
    Broadcast,
    /// Given operands of (the same) struct type, creates a struct of fixed-
    /// width vectors each containing a struct field of all operands. The
    /// number of operands matches the element count of every vector.
    BuildStructVector,
    /// Creates a fixed-width vector containing all operands. The number of
    /// operands matches the vector element count.
    BuildVector,
    /// Extracts all lanes from its (non-scalable) vector operand. This is an
    /// abstract VPInstruction whose single defined VPValue represents VF
    /// scalars extracted from a vector, to be replaced by VF ExtractElement
    /// VPInstructions.
    Unpack,
    /// Reduce the operands to the final reduction result using the operation
    /// specified via the operation's VPIRFlags.
    ComputeReductionResult,
    // Extracts the last part of its operand. Removed during unrolling.
    ExtractLastPart,
    // Extracts the last lane of its vector operand, per part.
    ExtractLastLane,
    // Extracts the second-to-last lane from its operand or the second-to-last
    // part if it is scalar. In the latter case, the recipe will be removed
    // during unrolling.
    ExtractPenultimateElement,
    LogicalAnd,     // Non-poison propagating logical And.
    LogicalOr,      // Non-poison propagating logical Or.
    NumActiveLanes, // Counts the number of active lanes in a mask.
    // Add an offset in bytes (second operand) to a base pointer (first
    // operand). Only generates scalar values (either for the first lane only or
    // for all lanes, depending on its uses).
    PtrAdd,
    // Add a vector offset in bytes (second operand) to a scalar base pointer
    // (first operand).
    WidePtrAdd,
    // Returns a scalar boolean value, which is true if any lane of its
    // (boolean) vector operands is true. It produces the reduced value across
    // all unrolled iterations. Unrolling will add all copies of its original
    // operand as additional operands. Note does not block poison propagation.
    AnyOf,
    // Calculates the first active lane index of the vector predicate operands.
    // It produces the lane index across all unrolled iterations. Unrolling will
    // add all copies of its original operand as additional operands.
    // Implemented with @llvm.experimental.cttz.elts, but returns the expected
    // result even with operands that are all zeroes.
    FirstActiveLane,
    // Calculates the last active lane index of the vector predicate operands.
    // The predicates must be prefix-masks (all 1s before all 0s). Used when
    // tail-folding to extract the correct live-out value from the last active
    // iteration. It produces the lane index across all unrolled iterations.
    // Unrolling will add all copies of its original operand as additional
    // operands.
    LastActiveLane,
    // Returns a reversed vector for the operand.
    Reverse,
    /// Start vector for reductions with 3 operands: the original start value,
    /// the identity value for the reduction and an integer indicating the
    /// scaling factor.
    ReductionStartVector,
    /// Extracts a single lane (first operand) from a set of vector operands.
    /// The lane specifies an index into a vector formed by combining all vector
    /// operands (all operands after the first one).
    ExtractLane,
    /// Explicit user for values in the main VPlan, used by the epilogue vector
    /// loop.
    ResumeForEpilogue,
    /// Extracts the last active lane from a set of vectors. The first operand
    /// is the default value if no lanes in the masks are active. Conceptually,
    /// this concatenates all data vectors (odd operands), concatenates all
    /// masks (even operands -- ignoring the default value), and returns the
    /// last active value from the combined data vector using the combined mask.
    ExtractLastActive,
    /// Compute the exiting value of a wide induction after vectorization, that
    /// is the value of the last lane of the induction increment (i.e. its
    /// backedge value). Has the wide induction recipe as operand.
    ExitingIVValue,
    MaskedCond,
    /// Scale the first operand (vector step) by the second operand
    /// (scalar-step).  Casts both operands to the result type if needed.
    WideIVStep,
    // Creates a step vector starting from 0 to VF with a step of 1.
    StepVector,
    /// Calls a scalar intrinsic. The intrinsic ID is the last operand.
    Intrinsic,

    OpsEnd = Intrinsic,
  };

  /// Returns true if this recipe produces scalar values for all VF lanes.
  bool doesGeneratePerAllLanes() const;

  /// Return the number of operands determined by the opcode of the
  /// VPInstruction, excluding mask. Returns -1u if the number of operands
  /// cannot be determined directly by the opcode.
  unsigned getNumOperandsForOpcode() const;

private:
  typedef unsigned char OpcodeTy;
  OpcodeTy Opcode;

  /// An optional name that can be used for the generated IR instruction.
  std::string Name;

  /// Returns true if we can generate a scalar for the first lane only if
  /// needed.
  bool doesGenerateSingleScalar() const;

  /// Utility method serving execute: Generates either a single-scalar or vector
  /// value. \p GenerateSingleScalar determines whether to generate a
  /// single-scalar value.
  Value *generate(VPTransformState &State, bool GenerateSingleScalar);

  /// Returns true if the VPInstruction does not need masking.
  bool alwaysUnmasked() const {
    if (Opcode == VPInstruction::MaskedCond)
      return false;

    // For now only VPInstructions with underlying values use masks.
    // TODO: provide masks to VPInstructions w/o underlying values.
    if (!getUnderlyingValue())
      return true;

    return Instruction::isCast(Opcode) || Opcode == Instruction::PHI ||
           Opcode == Instruction::GetElementPtr;
  }

public:
  VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,
                const VPIRFlags &Flags = {}, const VPIRMetadata &MD = {},
                DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "",
                Type *ResultTy = nullptr);

  VP_CLASSOF_IMPL(VPRecipeBase::VPInstructionSC)

  VPInstruction *clone() override {
    return cloneWithOperands(operands(), getScalarType());
  }

  VPInstruction *cloneWithOperands(ArrayRef<VPValue *> NewOperands,
                                   Type *ResultTy = nullptr) {
    auto *New = new VPInstruction(Opcode, NewOperands, *this, *this,
                                  getDebugLoc(), Name, ResultTy);
    if (getUnderlyingValue())
      New->setUnderlyingValue(getUnderlyingInstr());
    return New;
  }

  unsigned getOpcode() const { return Opcode; }

  /// Add \p Op as operand of this VPInstruction. Only supported for AnyOf,
  /// ComputeReductionResult, BuildVector, BuildStructVector, ExtractLane,
  /// ExtractLastActive, FirstActiveLane, LastActiveLane.
  void addOperand(VPValue *Op);

  /// Generate the instruction.
  /// TODO: We currently execute only per-part unless a specific instance is
  /// provided.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPInstruction.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the VPInstruction to dbgs() (for debugging).
  LLVM_DUMP_METHOD void dump() const;
#endif

  bool hasResult() const {
    // CallInst may or may not have a result, depending on the called function.
    // Conservatively return calls have results for now.
    switch (getOpcode()) {
    case Instruction::Ret:
    case Instruction::UncondBr:
    case Instruction::CondBr:
    case Instruction::Store:
    case Instruction::Switch:
    case Instruction::IndirectBr:
    case Instruction::Resume:
    case Instruction::CatchRet:
    case Instruction::Unreachable:
    case Instruction::Fence:
    case Instruction::AtomicRMW:
    case VPInstruction::BranchOnCond:
    case VPInstruction::BranchOnTwoConds:
    case VPInstruction::BranchOnCount:
    case VPInstruction::WideVectorStore:
      return false;
    default:
      return true;
    }
  }

  /// Returns true if the VPInstruction has a mask operand.
  bool isMasked() const {
    unsigned NumOpsForOpcode = getNumOperandsForOpcode();
    // VPInstructions without a fixed number of operands cannot be masked.
    if (NumOpsForOpcode == -1u)
      return false;
    return NumOpsForOpcode + 1 == getNumOperands();
  }

  /// Returns the number of operands, excluding the mask if the VPInstruction is
  /// masked.
  unsigned getNumOperandsWithoutMask() const {
    return getNumOperands() - isMasked();
  }

  /// Add mask \p Mask to an unmasked VPInstruction, if it needs masking.
  void addMask(VPValue *Mask) {
    assert(!isMasked() && "recipe is already masked");
    if (alwaysUnmasked())
      return;
    assert(Mask->getScalarType()->isIntegerTy(1) &&
           "Mask must be an i1 (vector)");
    VPUser::addOperand(Mask);
  }

  /// Returns the mask for the VPInstruction. Returns nullptr for unmasked
  /// VPInstructions.
  VPValue *getMask() const {
    return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
  }

  /// Returns an iterator range over the operands excluding the mask operand
  /// if present.
  iterator_range<operand_iterator> operandsWithoutMask() {
    return make_range(op_begin(), op_begin() + getNumOperandsWithoutMask());
  }
  iterator_range<const_operand_iterator> operandsWithoutMask() const {
    return make_range(op_begin(), op_begin() + getNumOperandsWithoutMask());
  }

  /// Returns true if the underlying opcode may read from or write to memory.
  bool opcodeMayReadOrWriteFromMemory() const;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override;

  /// Returns true if the recipe only uses scalars of operand \p Op.
  bool usesScalars(const VPValue *Op) const override {
    return isSingleScalar() || usesFirstLaneOnly(Op);
  }

  /// Returns true if the recipe only uses the first part of operand \p Op.
  bool usesFirstPartOnly(const VPValue *Op) const override;

  /// Returns true if this VPInstruction produces a scalar value from a vector,
  /// e.g. by performing a reduction or extracting a lane.
  bool isVectorToScalar() const;

  /// Returns true if the recipe produces a single scalar value.
  bool isSingleScalar() const;

  /// Returns the symbolic name assigned to the VPInstruction.
  StringRef getName() const { return Name; }

  /// Set the symbolic name for the VPInstruction.
  void setName(StringRef NewName) { Name = NewName.str(); }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the VPInstruction to \p O.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// Helper type to provide functions to access incoming values and blocks for
/// phi-like recipes.
class VPPhiAccessors {
protected:
  /// Return a VPRecipeBase* to the current object.
  virtual const VPRecipeBase *getAsRecipe() const = 0;

public:
  virtual ~VPPhiAccessors() = default;

  /// Returns the incoming VPValue with index \p Idx.
  VPValue *getIncomingValue(unsigned Idx) const {
    return getAsRecipe()->getOperand(Idx);
  }

  /// Returns the incoming block with index \p Idx.
  const VPBasicBlock *getIncomingBlock(unsigned Idx) const;

  /// Returns the incoming value for \p VPBB. \p VPBB must be an incoming block.
  LLVM_ABI_FOR_TEST VPValue *
  getIncomingValueForBlock(const VPBasicBlock *VPBB) const;

  /// Sets the incoming value for \p VPBB to \p V. \p VPBB must be an incoming
  /// block.
  void setIncomingValueForBlock(const VPBasicBlock *VPBB, VPValue *V) const;

  /// Returns the number of incoming values, also number of incoming blocks.
  virtual unsigned getNumIncoming() const {
    return getAsRecipe()->getNumOperands();
  }

  /// Returns an interator range over the incoming values.
  VPUser::const_operand_range incoming_values() const {
    return make_range(getAsRecipe()->op_begin(),
                      getAsRecipe()->op_begin() + getNumIncoming());
  }

  using const_incoming_blocks_range = iterator_range<mapped_iterator<
      detail::index_iterator, std::function<const VPBasicBlock *(size_t)>>>;

  /// Returns an iterator range over the incoming blocks.
  const_incoming_blocks_range incoming_blocks() const {
    std::function<const VPBasicBlock *(size_t)> GetBlock = [this](size_t Idx) {
      return getIncomingBlock(Idx);
    };
    return map_range(index_range(0, getNumIncoming()), GetBlock);
  }

  /// Returns an iterator range over pairs of incoming values and corresponding
  /// incoming blocks.
  detail::zippy<llvm::detail::zip_first, VPUser::const_operand_range,
                const_incoming_blocks_range>
  incoming_values_and_blocks() const {
    return zip_equal(incoming_values(), incoming_blocks());
  }

  /// Removes the incoming value for \p IncomingBlock, which must be a
  /// predecessor.
  void removeIncomingValueFor(VPBlockBase *IncomingBlock) const;

  /// Append \p IncomingV as an incoming value to the phi-like recipe.
  void addIncoming(VPValue *IncomingV) {
    auto *R = const_cast<VPRecipeBase *>(getAsRecipe());
    assert((R->getNumOperands() == 0 ||
            IncomingV->getScalarType() == R->getOperand(0)->getScalarType()) &&
           "all incoming values must have the same type");
    R->addOperand(IncomingV);
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printPhiOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
#endif
};

struct LLVM_ABI_FOR_TEST VPPhi : public VPInstruction, public VPPhiAccessors {
  VPPhi(ArrayRef<VPValue *> Operands, const VPIRFlags &Flags, DebugLoc DL,
        const Twine &Name = "", Type *ResultTy = nullptr)
      : VPInstruction(Instruction::PHI, Operands, Flags, {}, DL, Name,
                      ResultTy) {}

  static inline bool classof(const VPUser *U) {
    auto *VPI = dyn_cast<VPInstruction>(U);
    return VPI && VPI->getOpcode() == Instruction::PHI;
  }

  static inline bool classof(const VPValue *V) {
    auto *VPI = dyn_cast<VPInstruction>(V);
    return VPI && VPI->getOpcode() == Instruction::PHI;
  }

  static inline bool classof(const VPSingleDefRecipe *SDR) {
    auto *VPI = dyn_cast<VPInstruction>(SDR);
    return VPI && VPI->getOpcode() == Instruction::PHI;
  }

  VPPhi *clone() override {
    auto *PhiR = new VPPhi(operands(), *this, getDebugLoc(), getName());
    PhiR->setUnderlyingValue(getUnderlyingValue());
    return PhiR;
  }

  void execute(VPTransformState &State) override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif

  const VPRecipeBase *getAsRecipe() const override { return this; }
};

/// A recipe to wrap on original IR instruction not to be modified during
/// execution, except for PHIs. PHIs are modeled via the VPIRPhi subclass.
/// Expect PHIs, VPIRInstructions cannot have any operands.
class VPIRInstruction : public VPRecipeBase {
  Instruction &I;

protected:
  /// VPIRInstruction::create() should be used to create VPIRInstructions, as
  /// subclasses may need to be created, e.g. VPIRPhi.
  VPIRInstruction(Instruction &I)
      : VPRecipeBase(VPRecipeBase::VPIRInstructionSC, {}), I(I) {}

public:
  ~VPIRInstruction() override = default;

  /// Create a new VPIRPhi for \p \I, if it is a PHINode, otherwise create a
  /// VPIRInstruction.
  LLVM_ABI_FOR_TEST static VPIRInstruction *create(Instruction &I);

  VP_CLASSOF_IMPL(VPRecipeBase::VPIRInstructionSC)

  VPIRInstruction *clone() override {
    auto *R = create(I);
    for (auto *Op : operands())
      R->addOperand(Op);
    return R;
  }

  void execute(VPTransformState &State) override;

  /// Return the cost of this VPIRInstruction.
  LLVM_ABI_FOR_TEST InstructionCost
  computeCost(ElementCount VF, VPCostContext &Ctx) const override;

  Instruction &getInstruction() const { return I; }

  bool usesScalars(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }

  bool usesFirstPartOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }

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

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// An overlay for VPIRInstructions wrapping PHI nodes enabling convenient use
/// cast/dyn_cast/isa and execute() implementation. A single VPValue operand is
/// allowed, and it is used to add a new incoming value for the single
/// predecessor VPBB.
struct LLVM_ABI_FOR_TEST VPIRPhi : public VPIRInstruction,
                                   public VPPhiAccessors {
  VPIRPhi(PHINode &PN) : VPIRInstruction(PN) {}

  static inline bool classof(const VPRecipeBase *U) {
    auto *R = dyn_cast<VPIRInstruction>(U);
    return R && isa<PHINode>(R->getInstruction());
  }

  static inline bool classof(const VPUser *U) {
    auto *R = dyn_cast<VPRecipeBase>(U);
    return R && classof(R);
  }

  PHINode &getIRPhi() const { return cast<PHINode>(getInstruction()); }

  void execute(VPTransformState &State) override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif

  const VPRecipeBase *getAsRecipe() const override { return this; }
};

/// VPWidenRecipe is a recipe for producing a widened instruction using the
/// opcode and operands of the recipe. This recipe covers most of the
/// traditional vectorization cases where each recipe transforms into a
/// vectorized version of itself.
class LLVM_ABI_FOR_TEST VPWidenRecipe : public VPRecipeWithIRFlags,
                                        public VPIRMetadata {
  unsigned Opcode;

public:
  VPWidenRecipe(Instruction &I, ArrayRef<VPValue *> Operands,
                const VPIRFlags &Flags = {}, const VPIRMetadata &Metadata = {},
                DebugLoc DL = {})
      : VPWidenRecipe(I.getOpcode(), Operands, Flags, Metadata, DL) {
    setUnderlyingValue(&I);
  }

  VPWidenRecipe(unsigned Opcode, ArrayRef<VPValue *> Operands,
                const VPIRFlags &Flags = {}, const VPIRMetadata &Metadata = {},
                DebugLoc DL = {})
      : VPRecipeWithIRFlags(VPRecipeBase::VPWidenSC, Operands,
                            computeScalarTypeForInstruction(Opcode, Operands),
                            Flags, DL),
        VPIRMetadata(Metadata), Opcode(Opcode) {
    assert(flagsValidForOpcode(Opcode) &&
           "Set flags not supported for the provided opcode");
    assert(hasRequiredFlagsForOpcode(Opcode, getScalarType()) &&
           "Opcode requires specific flags to be set");
  }

  ~VPWidenRecipe() override = default;

  VPWidenRecipe *clone() override { return cloneWithOperands(operands()); }

  VPWidenRecipe *cloneWithOperands(ArrayRef<VPValue *> NewOperands) {
    if (auto *UV = getUnderlyingValue())
      return new VPWidenRecipe(*cast<Instruction>(UV), NewOperands, *this,
                               *this, getDebugLoc());
    return new VPWidenRecipe(Opcode, NewOperands, *this, *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenSC)

  /// Produce a widened instruction using the opcode and operands of the recipe,
  /// processing State.VF elements.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  unsigned getOpcode() const { return Opcode; }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return Opcode == Instruction::Select && Op == getOperand(0) &&
           isa<VPIRValue>(Op);
  }
};

/// VPWidenCastRecipe is a recipe to create vector cast instructions.
/// TODO: Merge with VPWidenRecipe now that type is associated to every
/// VPRecipeValue.
class LLVM_ABI_FOR_TEST VPWidenCastRecipe : public VPRecipeWithIRFlags,
                                            public VPIRMetadata {
  /// Cast instruction opcode.
  Instruction::CastOps Opcode;

public:
  VPWidenCastRecipe(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy,
                    CastInst *CI = nullptr, const VPIRFlags &Flags = {},
                    const VPIRMetadata &Metadata = {},
                    DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeWithIRFlags(VPRecipeBase::VPWidenCastSC, Op, ResultTy, Flags,
                            DL),
        VPIRMetadata(Metadata), Opcode(Opcode) {
    assert(flagsValidForOpcode(Opcode) &&
           "Set flags not supported for the provided opcode");
    assert(hasRequiredFlagsForOpcode(Opcode, ResultTy) &&
           "Opcode requires specific flags to be set");
    setUnderlyingValue(CI);
  }

  ~VPWidenCastRecipe() override = default;

  VPWidenCastRecipe *clone() override {
    return new VPWidenCastRecipe(Opcode, getOperand(0), getScalarType(),
                                 cast_or_null<CastInst>(getUnderlyingValue()),
                                 *this, *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenCastSC)

  /// Produce widened copies of the cast.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenCastRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  Instruction::CastOps getOpcode() const { return Opcode; }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for widening vector intrinsics.
class LLVM_ABI_FOR_TEST VPWidenIntrinsicRecipe : public VPRecipeWithIRFlags,
                                                 public VPIRMetadata {
  /// ID of the vector intrinsic to widen.
  Intrinsic::ID VectorIntrinsicID;

  /// True if the intrinsic may read from memory.
  bool MayReadFromMemory;

  /// True if the intrinsic may read write to memory.
  bool MayWriteToMemory;

  /// True if the intrinsic may have side-effects.
  bool MayHaveSideEffects;

protected:
  VPWidenIntrinsicRecipe(VPRecipeTy SC, Intrinsic::ID VectorIntrinsicID,
                         ArrayRef<VPValue *> CallArguments, Type *Ty,
                         const VPIRFlags &Flags = {},
                         const VPIRMetadata &MD = {},
                         DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeWithIRFlags(SC, CallArguments, Ty, Flags, DL), VPIRMetadata(MD),
        VectorIntrinsicID(VectorIntrinsicID) {
    LLVMContext &Ctx = Ty->getContext();
    AttributeSet Attrs = Intrinsic::getFnAttributes(Ctx, VectorIntrinsicID);
    MemoryEffects ME = Attrs.getMemoryEffects();
    MayReadFromMemory = !ME.onlyWritesMemory();
    MayWriteToMemory = !ME.onlyReadsMemory();
    MayHaveSideEffects = MayWriteToMemory ||
                         !Attrs.hasAttribute(Attribute::NoUnwind) ||
                         !Attrs.hasAttribute(Attribute::WillReturn);
  }

  /// Helper function to produce the widened intrinsic call.
  CallInst *createVectorCall(VPTransformState &State);

public:
  VPWidenIntrinsicRecipe(CallInst &CI, Intrinsic::ID VectorIntrinsicID,
                         ArrayRef<VPValue *> CallArguments, Type *Ty,
                         const VPIRFlags &Flags = {},
                         const VPIRMetadata &MD = {},
                         DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeWithIRFlags(VPRecipeBase::VPWidenIntrinsicSC, CallArguments, Ty,
                            Flags, DL),
        VPIRMetadata(MD), VectorIntrinsicID(VectorIntrinsicID),
        MayReadFromMemory(CI.mayReadFromMemory()),
        MayWriteToMemory(CI.mayWriteToMemory()),
        MayHaveSideEffects(CI.mayHaveSideEffects()) {
    setUnderlyingValue(&CI);
  }

  VPWidenIntrinsicRecipe(Intrinsic::ID VectorIntrinsicID,
                         ArrayRef<VPValue *> CallArguments, Type *Ty,
                         const VPIRFlags &Flags = {},
                         const VPIRMetadata &Metadata = {},
                         DebugLoc DL = DebugLoc::getUnknown())
      : VPWidenIntrinsicRecipe(VPRecipeBase::VPWidenIntrinsicSC,
                               VectorIntrinsicID, CallArguments, Ty, Flags,
                               Metadata, DL) {}

  ~VPWidenIntrinsicRecipe() override = default;

  VPWidenIntrinsicRecipe *clone() override {
    if (Value *CI = getUnderlyingValue())
      return new VPWidenIntrinsicRecipe(*cast<CallInst>(CI), VectorIntrinsicID,
                                        operands(), getScalarType(), *this,
                                        *this, getDebugLoc());
    return new VPWidenIntrinsicRecipe(VectorIntrinsicID, operands(),
                                      getScalarType(), *this, *this,
                                      getDebugLoc());
  }

  static inline bool classof(const VPRecipeBase *R) {
    return R->getVPRecipeID() == VPRecipeBase::VPWidenIntrinsicSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenMemIntrinsicSC;
  }

  static inline bool classof(const VPUser *U) {
    auto *R = dyn_cast<VPRecipeBase>(U);
    return R && classof(R);
  }

  static inline bool classof(const VPValue *V) {
    auto *R = V->getDefiningRecipe();
    return R && classof(R);
  }

  static inline bool classof(const VPSingleDefRecipe *R) {
    return classof(static_cast<const VPRecipeBase *>(R));
  }

  /// Produce a widened version of the vector intrinsic.
  void execute(VPTransformState &State) override;

  /// Compute the cost of a vector intrinsic with \p ID and \p Operands.
  static InstructionCost computeCallCost(Intrinsic::ID ID,
                                         ArrayRef<const VPValue *> Operands,
                                         const VPRecipeWithIRFlags &R,
                                         ElementCount VF, VPCostContext &Ctx);

  /// Return the cost of this vector intrinsic.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Return the ID of the intrinsic.
  Intrinsic::ID getVectorIntrinsicID() const { return VectorIntrinsicID; }

  /// Return to name of the intrinsic as string.
  StringRef getIntrinsicName() const;

  /// Returns true if the intrinsic may read from memory.
  bool mayReadFromMemory() const { return MayReadFromMemory; }

  /// Returns true if the intrinsic may write to memory.
  bool mayWriteToMemory() const { return MayWriteToMemory; }

  /// Returns true if the intrinsic may have side-effects.
  bool mayHaveSideEffects() const { return MayHaveSideEffects; }

  bool usesFirstLaneOnly(const VPValue *Op) const override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for widening vector memory intrinsics.
class VPWidenMemIntrinsicRecipe final : public VPWidenIntrinsicRecipe {
  /// Alignment information for this memory access.
  Align Alignment;

public:
  VPWidenMemIntrinsicRecipe(Intrinsic::ID VectorIntrinsicID,
                            ArrayRef<VPValue *> CallArguments, Type *Ty,
                            Align Alignment, const VPIRMetadata &MD = {},
                            DebugLoc DL = DebugLoc::getUnknown())
      : VPWidenIntrinsicRecipe(VPRecipeBase::VPWidenMemIntrinsicSC,
                               VectorIntrinsicID, CallArguments, Ty, {}, MD,
                               DL),
        Alignment(Alignment) {
    assert((VectorIntrinsicID == Intrinsic::experimental_vp_strided_load ||
            VectorIntrinsicID == Intrinsic::experimental_vp_strided_store) &&
           "Unexpected intrinsic");
  }

  ~VPWidenMemIntrinsicRecipe() override = default;

  VPWidenMemIntrinsicRecipe *clone() override {
    return new VPWidenMemIntrinsicRecipe(getVectorIntrinsicID(), operands(),
                                         getScalarType(), Alignment, *this,
                                         getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenMemIntrinsicSC)

  /// Produce a widened version of the vector memory intrinsic.
  void execute(VPTransformState &State) override;

  /// Helper function for computing the cost of vector memory intrinsic.
  static InstructionCost computeMemIntrinsicCost(Intrinsic::ID IID, Type *Ty,
                                                 bool IsMasked, Align Alignment,
                                                 VPCostContext &Ctx);

  /// Return the cost of this vector memory intrinsic.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;
};

/// A recipe for widening Call instructions using library calls.
class LLVM_ABI_FOR_TEST VPWidenCallRecipe : public VPRecipeWithIRFlags,
                                            public VPIRMetadata {
  /// Variant stores a pointer to the chosen function. There is a 1:1 mapping
  /// between a given VF and the chosen vectorized variant, so there will be a
  /// different VPlan for each VF with a valid variant.
  Function *Variant;

public:
  VPWidenCallRecipe(Value *UV, Function *Variant,
                    ArrayRef<VPValue *> CallArguments,
                    const VPIRFlags &Flags = {},
                    const VPIRMetadata &Metadata = {}, DebugLoc DL = {})
      : VPRecipeWithIRFlags(VPRecipeBase::VPWidenCallSC, CallArguments,
                            toScalarizedTy(Variant->getReturnType()), Flags,
                            DL),
        VPIRMetadata(Metadata), Variant(Variant) {
    setUnderlyingValue(UV);
    assert(
        isa<Function>(getOperand(getNumOperands() - 1)->getLiveInIRValue()) &&
        "last operand must be the called function");
    assert(cast<Function>(CallArguments.back()->getLiveInIRValue())
                   ->getReturnType() == getScalarType() &&
           "Scalar type must match return type of called scalar function");
  }

  ~VPWidenCallRecipe() override = default;

  VPWidenCallRecipe *clone() override {
    return new VPWidenCallRecipe(getUnderlyingValue(), Variant, operands(),
                                 *this, *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenCallSC)

  /// Produce a widened version of the call instruction.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenCallRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Return the cost of widening a call using the vector function \p Variant.
  static InstructionCost computeCallCost(Function *Variant, VPCostContext &Ctx);

  Function *getCalledScalarFunction() const {
    return cast<Function>(getOperand(getNumOperands() - 1)->getLiveInIRValue());
  }

  operand_range args() { return drop_end(operands()); }
  const_operand_range args() const { return drop_end(operands()); }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe representing a sequence of load -> update -> store as part of
/// a histogram operation. This means there may be aliasing between vector
/// lanes, which is handled by the llvm.experimental.vector.histogram family
/// of intrinsics. The only update operations currently supported are
/// 'add' and 'sub' where the other term is loop-invariant.
class VPHistogramRecipe : public VPRecipeBase, public VPIRMetadata {
  /// Opcode of the update operation, currently either add or sub.
  unsigned Opcode;

public:
  VPHistogramRecipe(unsigned Opcode, ArrayRef<VPValue *> Operands,
                    const VPIRMetadata &Metadata = {},
                    DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeBase(VPRecipeBase::VPHistogramSC, Operands, DL),
        VPIRMetadata(Metadata), Opcode(Opcode) {}

  ~VPHistogramRecipe() override = default;

  VPHistogramRecipe *clone() override {
    return new VPHistogramRecipe(Opcode, operands(), *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPHistogramSC);

  /// Produce a vectorized histogram operation.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPHistogramRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Return the mask operand if one was provided, or a null pointer if all
  /// lanes should be executed unconditionally.
  VPValue *getMask() const {
    return getNumOperands() == 3 ? getOperand(2) : nullptr;
  }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return Op == getOperand(1);
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for handling GEP instructions.
class LLVM_ABI_FOR_TEST VPWidenGEPRecipe : public VPRecipeWithIRFlags {
  Type *SourceElementTy;

public:
  VPWidenGEPRecipe(Type *SourceElementTy, ArrayRef<VPValue *> Operands,
                   const VPIRFlags &Flags = {},
                   DebugLoc DL = DebugLoc::getUnknown(),
                   GetElementPtrInst *UV = nullptr)
      : VPRecipeWithIRFlags(VPRecipeBase::VPWidenGEPSC, Operands,
                            Operands[0]->getScalarType(), Flags, DL),
        SourceElementTy(SourceElementTy) {
    if (UV) {
      setUnderlyingValue(UV);
      [[maybe_unused]] SmallVector<std::pair<unsigned, MDNode *>> Metadata;
      getMetadataToPropagate(UV, Metadata);
      assert(Metadata.empty() && "unexpected metadata on GEP");
    }
  }

  ~VPWidenGEPRecipe() override = default;

  VPWidenGEPRecipe *clone() override {
    return new VPWidenGEPRecipe(
        getSourceElementType(), operands(), *this, getDebugLoc(),
        cast_or_null<GetElementPtrInst>(getUnderlyingValue()));
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenGEPSC)

  /// This recipe generates a GEP instruction.
  unsigned getOpcode() const { return Instruction::GetElementPtr; }

  /// Generate the gep nodes.
  void execute(VPTransformState &State) override;

  Type *getSourceElementType() const { return SourceElementTy; }

  /// Return the cost of this VPWidenGEPRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // TODO: Compute accurate cost after retiring the legacy cost model.
    return 0;
  }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe to compute a pointer to the last element of each part of a widened
/// memory access for widened memory accesses of SourceElementTy. Used for
/// VPWidenMemoryRecipes or VPInterleaveRecipes that are reversed. An extra
/// Offset operand is added by convertToConcreteRecipes when UF = 1, and by the
/// unroller otherwise.
class VPVectorEndPointerRecipe : public VPRecipeWithIRFlags {
  Type *SourceElementTy;

  /// The constant stride of the pointer computed by this recipe, expressed in
  /// units of SourceElementTy.
  int64_t Stride;

public:
  VPVectorEndPointerRecipe(VPValue *Ptr, VPValue *VF, Type *SourceElementTy,
                           int64_t Stride, GEPNoWrapFlags GEPFlags, DebugLoc DL)
      : VPRecipeWithIRFlags(VPRecipeBase::VPVectorEndPointerSC, {Ptr, VF},
                            Ptr->getScalarType(), GEPFlags, DL),
        SourceElementTy(SourceElementTy), Stride(Stride) {
    assert(Stride < 0 && "Stride must be negative");
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPVectorEndPointerSC)

  Type *getSourceElementType() const { return SourceElementTy; }
  int64_t getStride() const { return Stride; }
  VPValue *getPointer() const { return getOperand(0); }
  VPValue *getVFValue() const { return getOperand(1); }
  VPValue *getOffset() const {
    return getNumOperands() == 3 ? getOperand(2) : nullptr;
  }

  /// Adds the offset operand to the recipe.
  /// Offset = Stride * (VF - 1) + Part * Stride * VF.
  void materializeOffset(unsigned Part = 0);

  /// Append \p Offset as the offset operand. The offset is an integer index
  /// expressed in units of SourceElementTy.
  void addOffset(VPValue *Offset) {
    assert(Offset->getScalarType()->isIntegerTy() &&
           "offset must be an integer index");
    VPUser::addOperand(Offset);
  }

  void execute(VPTransformState &State) override;

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

  /// Return the cost of this VPVectorPointerRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // TODO: Compute accurate cost after retiring the legacy cost model.
    return 0;
  }

  /// Returns true if the recipe only uses the first part of operand \p Op.
  bool usesFirstPartOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    assert(getNumOperands() <= 2 && "must have at most two operands");
    return true;
  }

  VPVectorEndPointerRecipe *clone() override {
    auto *VEPR = new VPVectorEndPointerRecipe(
        getPointer(), getVFValue(), getSourceElementType(), getStride(),
        getGEPNoWrapFlags(), getDebugLoc());
    if (auto *Offset = getOffset())
      VEPR->addOffset(Offset);
    return VEPR;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe to compute the pointers for widened memory accesses of \p
/// SourceElementTy, with the \p Stride expressed in units of \p
/// SourceElementTy. Unrolling adds an extra \p VFxPart operand for unrolled
/// parts > 0 and it produces `GEP SourceElementTy Ptr, VFxPart * Stride`.
class VPVectorPointerRecipe : public VPRecipeWithIRFlags {
  Type *SourceElementTy;

public:
  VPVectorPointerRecipe(VPValue *Ptr, Type *SourceElementTy, VPValue *Stride,
                        GEPNoWrapFlags GEPFlags, DebugLoc DL)
      : VPRecipeWithIRFlags(VPRecipeBase::VPVectorPointerSC,
                            ArrayRef<VPValue *>({Ptr, Stride}),
                            Ptr->getScalarType(), GEPFlags, DL),
        SourceElementTy(SourceElementTy) {}

  VP_CLASSOF_IMPL(VPRecipeBase::VPVectorPointerSC)

  VPValue *getStride() const { return getOperand(1); }

  VPValue *getVFxPart() const {
    return getNumOperands() > 2 ? getOperand(2) : nullptr;
  }

  /// Add the per-part offset (VFxPart) used for unrolled parts > 0.
  void addPerPartOffset(VPValue *VFxPart) {
    assert(VFxPart->getScalarType()->isIntegerTy() &&
           "per-part offset must be an integer index");
    VPUser::addOperand(VFxPart);
  }

  void execute(VPTransformState &State) override;

  Type *getSourceElementType() const { return SourceElementTy; }

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

  /// Returns true if the recipe only uses the first part of operand \p Op.
  bool usesFirstPartOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    assert(getNumOperands() <= 2 && "must have at most two operands");
    return true;
  }

  VPVectorPointerRecipe *clone() override {
    auto *Clone =
        new VPVectorPointerRecipe(getOperand(0), SourceElementTy, getStride(),
                                  getGEPNoWrapFlags(), getDebugLoc());
    if (auto *VFxPart = getVFxPart())
      Clone->addPerPartOffset(VFxPart);
    return Clone;
  }

  /// Return the cost of this VPHeaderPHIRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // TODO: Compute accurate cost after retiring the legacy cost model.
    return 0;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A pure virtual base class for all recipes modeling header phis, including
/// phis for first order recurrences, pointer inductions and reductions. The
/// start value is the first operand of the recipe and the incoming value from
/// the backedge is the second operand.
///
/// Inductions are modeled using the following sub-classes:
///  * VPWidenIntOrFpInductionRecipe: Generates vector values for integer and
///    floating point inductions with arbitrary start and step values. Produces
///    a vector PHI per-part.
///  * VPWidenPointerInductionRecipe: Generate vector and scalar values for a
///    pointer induction. Produces either a vector PHI per-part or scalar values
///    per-lane based on the canonical induction.
///  * VPFirstOrderRecurrencePHIRecipe
///  * VPReductionPHIRecipe
///  * VPActiveLaneMaskPHIRecipe
///  * VPEVLBasedIVPHIRecipe
///
/// Note that the canonical IV is modeled as a VPRegionValue associated with
/// its loop region.
class LLVM_ABI_FOR_TEST VPHeaderPHIRecipe : public VPSingleDefRecipe,
                                            public VPPhiAccessors {
protected:
  VPHeaderPHIRecipe(VPRecipeTy VPRecipeID, Instruction *UnderlyingInstr,
                    VPValue *Start, DebugLoc DL = DebugLoc::getUnknown())
      : VPHeaderPHIRecipe(VPRecipeID, UnderlyingInstr, Start,
                          Start->getScalarType(), DL) {}

  VPHeaderPHIRecipe(VPRecipeTy VPRecipeID, Instruction *UnderlyingInstr,
                    VPValue *Start, Type *ResultTy, DebugLoc DL)
      : VPSingleDefRecipe(VPRecipeID, Start, ResultTy, UnderlyingInstr, DL) {}

  const VPRecipeBase *getAsRecipe() const override { return this; }

public:
  ~VPHeaderPHIRecipe() override = default;

  /// Method to support type inquiry through isa, cast, and dyn_cast.
  static inline bool classof(const VPRecipeBase *R) {
    return R->getVPRecipeID() >= VPRecipeBase::VPFirstHeaderPHISC &&
           R->getVPRecipeID() <= VPRecipeBase::VPLastHeaderPHISC;
  }
  static inline bool classof(const VPValue *V) {
    return isa<VPHeaderPHIRecipe>(V->getDefiningRecipe());
  }
  static inline bool classof(const VPSingleDefRecipe *R) {
    return isa<VPHeaderPHIRecipe>(static_cast<const VPRecipeBase *>(R));
  }

  /// Generate the phi nodes.
  void execute(VPTransformState &State) override = 0;

  /// Return the cost of this header phi recipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns the start value of the phi, if one is set.
  VPValue *getStartValue() {
    return getNumOperands() == 0 ? nullptr : getOperand(0);
  }
  VPValue *getStartValue() const {
    return getNumOperands() == 0 ? nullptr : getOperand(0);
  }

  /// Update the start value of the recipe.
  void setStartValue(VPValue *V) { setOperand(0, V); }

  /// Returns the incoming value from the loop backedge.
  virtual VPValue *getBackedgeValue() { return getOperand(1); }

  /// Update the incoming value from the loop backedge.
  void setBackedgeValue(VPValue *V) { setOperand(1, V); }

  /// Add \p V as the incoming value from the loop backedge.
  void addBackedgeValue(VPValue *V) {
    assert(getNumOperands() == 1 &&
           "backedge value must be appended right after construction");
    assert(V->getScalarType() == getScalarType() &&
           "backedge value must have the same type as the start value");
    VPUser::addOperand(V);
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override = 0;
#endif
};

/// Base class for widened induction (VPWidenIntOrFpInductionRecipe and
/// VPWidenPointerInductionRecipe), providing shared functionality, including
/// retrieving the step value, induction descriptor and original phi node.
class VPWidenInductionRecipe : public VPHeaderPHIRecipe {
  InductionDescriptor IndDesc;

public:
  VPWidenInductionRecipe(VPRecipeTy Kind, PHINode *IV, VPValue *Start,
                         VPValue *Step, const InductionDescriptor &IndDesc,
                         DebugLoc DL)
      : VPWidenInductionRecipe(Kind, IV, Start, Step, IndDesc,
                               Start->getScalarType(), DL) {}

  VPWidenInductionRecipe(VPRecipeTy Kind, PHINode *IV, VPValue *Start,
                         VPValue *Step, const InductionDescriptor &IndDesc,
                         Type *ResultTy, DebugLoc DL)
      : VPHeaderPHIRecipe(Kind, IV, Start, ResultTy, DL), IndDesc(IndDesc) {
    addOperand(Step);
  }

  /// After unrolling, append the splat-VF step (`VF * step`) and the value of
  /// the induction at the last unrolled part.
  void addUnrolledPartOperands(VPValue *SplatVFStep, VPValue *LastPart) {
    assert(LastPart->getScalarType() == getScalarType() &&
           "last-part value must match the induction recipe's scalar type");
    assert((getScalarType()->isPointerTy()
                ? SplatVFStep->getScalarType()->isIntegerTy()
                : SplatVFStep->getScalarType() == getScalarType()) &&
           "splat-step must match the induction type for non-pointer "
           "inductions, or be an integer index for pointer inductions");
    VPUser::addOperand(SplatVFStep);
    VPUser::addOperand(LastPart);
  }

  static inline bool classof(const VPRecipeBase *R) {
    return R->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC ||
           R->getVPRecipeID() == VPRecipeBase::VPWidenPointerInductionSC;
  }

  static inline bool classof(const VPValue *V) {
    auto *R = V->getDefiningRecipe();
    return R && classof(R);
  }

  static inline bool classof(const VPSingleDefRecipe *R) {
    return classof(static_cast<const VPRecipeBase *>(R));
  }

  void execute(VPTransformState &State) override = 0;

  /// Returns the step value of the induction.
  VPValue *getStepValue() { return getOperand(1); }
  const VPValue *getStepValue() const { return getOperand(1); }

  VPValue *getVFValue() { return getOperand(2); }
  const VPValue *getVFValue() const { return getOperand(2); }

  /// Returns the number of incoming values, also number of incoming blocks.
  /// Note that at the moment, VPWidenPointerInductionRecipe only has a single
  /// incoming value, its start value.
  unsigned getNumIncoming() const override { return 1; }

  /// Returns the underlying PHINode if one exists, or null otherwise.
  PHINode *getPHINode() const {
    return cast_if_present<PHINode>(getUnderlyingValue());
  }

  /// Returns the induction descriptor for the recipe.
  const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }

  /// Returns the SCEV predicates associated with this induction.
  ArrayRef<const SCEVPredicate *> getNoWrapPredicates() const {
    return IndDesc.getNoWrapPredicates();
  }

  VPValue *getBackedgeValue() override {
    // TODO: All operands of base recipe must exist and be at same index in
    // derived recipe.
    llvm_unreachable(
        "VPWidenIntOrFpInductionRecipe generates its own backedge value");
  }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    // The recipe creates its own wide start value, so it only requests the
    // first lane of the operand.
    // TODO: Remove once creating the start value is modeled separately.
    return Op == getStartValue() || Op == getStepValue();
  }
};

/// A recipe for handling phi nodes of integer and floating-point inductions,
/// producing their vector values. This is an abstract recipe and must be
/// converted to concrete recipes before executing.
class VPWidenIntOrFpInductionRecipe : public VPWidenInductionRecipe,
                                      public VPIRFlags {
  TruncInst *Trunc;

  // If this recipe is unrolled it will have 2 additional operands.
  bool isUnrolled() const { return getNumOperands() == 5; }

public:
  VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,
                                VPValue *VF, const InductionDescriptor &IndDesc,
                                const VPIRFlags &Flags, DebugLoc DL)
      : VPWidenInductionRecipe(VPRecipeBase::VPWidenIntOrFpInductionSC, IV,
                               Start, Step, IndDesc, DL),
        VPIRFlags(Flags), Trunc(nullptr) {
    addOperand(VF);
  }

  VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,
                                VPValue *VF, const InductionDescriptor &IndDesc,
                                TruncInst *Trunc, const VPIRFlags &Flags,
                                DebugLoc DL)
      : VPWidenInductionRecipe(
            VPRecipeBase::VPWidenIntOrFpInductionSC, IV, Start, Step, IndDesc,
            Trunc ? Trunc->getType() : Start->getScalarType(), DL),
        VPIRFlags(Flags), Trunc(Trunc) {
    addOperand(VF);
    SmallVector<std::pair<unsigned, MDNode *>> Metadata;
    if (Trunc)
      getMetadataToPropagate(Trunc, Metadata);
    assert(Metadata.empty() && "unexpected metadata on Trunc");
  }

  ~VPWidenIntOrFpInductionRecipe() override = default;

  VPWidenIntOrFpInductionRecipe *clone() override {
    return new VPWidenIntOrFpInductionRecipe(
        getPHINode(), getStartValue(), getStepValue(), getVFValue(),
        getInductionDescriptor(), Trunc, *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenIntOrFpInductionSC)

  void execute(VPTransformState &State) override {
    llvm_unreachable("cannot execute this recipe, should be expanded via "
                     "expandVPWidenIntOrFpInductionRecipe");
  }

  /// If the recipe has been unrolled, return the VPValue for the induction
  /// increment, otherwise return null.
  VPValue *getSplatVFValue() const {
    return isUnrolled() ? getOperand(getNumOperands() - 2) : nullptr;
  }

  /// Returns the number of incoming values, also number of incoming blocks.
  /// Note that at the moment, VPWidenIntOrFpInductionRecipes only have a single
  /// incoming value, its start value.
  unsigned getNumIncoming() const override { return 1; }

  /// Returns the first defined value as TruncInst, if it is one or nullptr
  /// otherwise.
  TruncInst *getTruncInst() { return Trunc; }
  const TruncInst *getTruncInst() const { return Trunc; }

  /// Return the cost of this VPWidenIntOrFpInductionRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if the induction is canonical, i.e. starting at 0 and
  /// incremented by UF * VF (= the original IV is incremented by 1) and has the
  /// same type as the canonical induction.
  bool isCanonical() const;

  /// Returns the VPValue representing the value of this induction at
  /// the last unrolled part, if it exists. Returns itself if unrolling did not
  /// take place.
  VPValue *getLastUnrolledPartOperand() {
    return isUnrolled() ? getOperand(getNumOperands() - 1) : this;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

class VPWidenPointerInductionRecipe : public VPWidenInductionRecipe {
public:
  /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p
  /// Start and the number of elements unrolled \p NumUnrolledElems, typically
  /// VF*UF.
  VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, VPValue *Step,
                                VPValue *NumUnrolledElems,
                                const InductionDescriptor &IndDesc, DebugLoc DL)
      : VPWidenInductionRecipe(VPRecipeBase::VPWidenPointerInductionSC, Phi,
                               Start, Step, IndDesc, DL) {
    addOperand(NumUnrolledElems);
  }

  ~VPWidenPointerInductionRecipe() override = default;

  VPWidenPointerInductionRecipe *clone() override {
    return new VPWidenPointerInductionRecipe(
        cast<PHINode>(getUnderlyingInstr()), getOperand(0), getOperand(1),
        getOperand(2), getInductionDescriptor(), getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenPointerInductionSC)

  /// Generate vector values for the pointer induction.
  void execute(VPTransformState &State) override {
    llvm_unreachable("cannot execute this recipe, should be expanded via "
                     "expandVPWidenPointerInduction");
  };

  /// Returns true if only scalar values will be generated.
  bool onlyScalarsGenerated(bool IsScalable);

  /// Return the cost of this VPWidenPointerInductionRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for widened phis. Incoming values are operands of the recipe and
/// their operand index corresponds to the incoming predecessor block. If the
/// recipe is placed in an entry block to a (non-replicate) region, it must have
/// exactly 2 incoming values, the first from the predecessor of the region and
/// the second from the exiting block of the region.
class LLVM_ABI_FOR_TEST VPWidenPHIRecipe : public VPSingleDefRecipe,
                                           public VPPhiAccessors {
  /// Name to use for the generated IR instruction for the widened phi.
  std::string Name;

public:
  /// Create a new VPWidenPHIRecipe with incoming values \p IncomingValues,
  /// debug location \p DL and \p Name.
  VPWidenPHIRecipe(ArrayRef<VPValue *> IncomingValues,
                   DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "")
      : VPSingleDefRecipe(VPRecipeBase::VPWidenPHISC, IncomingValues,
                          IncomingValues[0]->getScalarType(),
                          /*UV=*/nullptr, DL),
        Name(Name.str()) {
    assert(all_of(IncomingValues,
                  [this](VPValue *VPV) {
                    return VPV->getScalarType() == getScalarType();
                  }) &&
           "all incoming values must have the same type");
  }

  VPWidenPHIRecipe *clone() override {
    return new VPWidenPHIRecipe(operands(), getDebugLoc(), Name);
  }

  ~VPWidenPHIRecipe() override = default;

  /// This recipe generates a PHI.
  unsigned getOpcode() const { return Instruction::PHI; }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenPHISC)

  /// Generate the phi/select nodes.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenPHIRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif

  const VPRecipeBase *getAsRecipe() const override { return this; }
};

/// A recipe for handling first-order recurrence phis. The start value is the
/// first operand of the recipe and the incoming value from the backedge is the
/// second operand.
struct VPFirstOrderRecurrencePHIRecipe : public VPHeaderPHIRecipe {
  VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start,
                                  VPValue &BackedgeValue)
      : VPHeaderPHIRecipe(VPRecipeBase::VPFirstOrderRecurrencePHISC, Phi,
                          &Start) {
    addOperand(&BackedgeValue);
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPFirstOrderRecurrencePHISC)

  VPFirstOrderRecurrencePHIRecipe *clone() override {
    return new VPFirstOrderRecurrencePHIRecipe(
        cast<PHINode>(getUnderlyingInstr()), *getOperand(0), *getOperand(1));
  }

  void execute(VPTransformState &State) override;

  /// Return the cost of this first-order recurrence phi recipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return Op == getStartValue();
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// Possible variants of a reduction.

/// This reduction is ordered and in-loop.
struct RdxOrdered {};
/// This reduction is in-loop.
struct RdxInLoop {};
/// This reduction is unordered with the partial result scaled down by some
/// factor.
struct RdxUnordered {
  unsigned VFScaleFactor;
};
using ReductionStyle = std::variant<RdxOrdered, RdxInLoop, RdxUnordered>;

inline ReductionStyle getReductionStyle(bool InLoop, bool Ordered,
                                        unsigned ScaleFactor) {
  assert((!Ordered || InLoop) && "Ordered implies in-loop");
  if (Ordered)
    return RdxOrdered{};
  if (InLoop)
    return RdxInLoop{};
  return RdxUnordered{/*VFScaleFactor=*/ScaleFactor};
}

/// A recipe for handling reduction phis. The start value is the first operand
/// of the recipe and the incoming value from the backedge is the second
/// operand.
class VPReductionPHIRecipe : public VPHeaderPHIRecipe, public VPIRFlags {
  /// The recurrence kind of the reduction.
  const RecurKind Kind;

  ReductionStyle Style;

  /// The phi is part of a multi-use reduction (e.g., used in FindIV
  /// patterns for argmin/argmax).
  /// TODO: Also support cases where the phi itself has a single use, but its
  /// compare has multiple uses.
  bool HasUsesOutsideReductionChain;

  /// Temporary flag indicating that the FindIV reduction expression has been
  /// sunk. While this is true, epilogue vectorization is disabled to avoid
  /// applying the sunk expression twice (once in the main vector loop and again
  /// in the epilogue), which can produce incorrect results by applying the sunk
  /// operation twice.
  /// TODO: Remove this flag once epilogue vectorization properly supports
  /// sunk FindIV expressions.
  bool ExpressionSunk = false;

public:
  /// Create a new VPReductionPHIRecipe for the reduction \p Phi.
  VPReductionPHIRecipe(PHINode *Phi, RecurKind Kind, VPValue &Start,
                       VPValue &BackedgeValue, ReductionStyle Style,
                       const VPIRFlags &Flags,
                       bool HasUsesOutsideReductionChain = false)
      : VPHeaderPHIRecipe(VPRecipeBase::VPReductionPHISC, Phi, &Start),
        VPIRFlags(Flags), Kind(Kind), Style(Style),
        HasUsesOutsideReductionChain(HasUsesOutsideReductionChain) {
    addOperand(&BackedgeValue);
  }

  ~VPReductionPHIRecipe() override = default;

  VPReductionPHIRecipe *cloneWithOperands(VPValue *Start,
                                          VPValue *BackedgeValue) {
    auto *Clone = new VPReductionPHIRecipe(
        dyn_cast_or_null<PHINode>(getUnderlyingValue()), getRecurrenceKind(),
        *Start, *BackedgeValue, Style, *this, HasUsesOutsideReductionChain);
    Clone->ExpressionSunk = ExpressionSunk;
    return Clone;
  }

  VPReductionPHIRecipe *clone() override {
    return cloneWithOperands(getOperand(0), getBackedgeValue());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPReductionPHISC)

  /// Generate the phi/select nodes.
  void execute(VPTransformState &State) override;

  /// Get the factor that the VF of this recipe's output should be scaled by, or
  /// 1 if it isn't scaled.
  unsigned getVFScaleFactor() const {
    auto *Partial = std::get_if<RdxUnordered>(&Style);
    return Partial ? Partial->VFScaleFactor : 1;
  }

  /// Set the VFScaleFactor for this reduction phi. Can only be set to a factor
  /// > 1.
  void setVFScaleFactor(unsigned ScaleFactor) {
    assert(ScaleFactor > 1 && "must set to scale factor > 1");
    Style = RdxUnordered{ScaleFactor};
  }

  /// Returns the recurrence kind of the reduction.
  RecurKind getRecurrenceKind() const { return Kind; }

  /// Returns true, if the phi is part of an ordered reduction.
  bool isOrdered() const { return std::holds_alternative<RdxOrdered>(Style); }

  /// Returns true if the phi is part of an in-loop reduction.
  bool isInLoop() const {
    return std::holds_alternative<RdxInLoop>(Style) ||
           std::holds_alternative<RdxOrdered>(Style);
  }

  /// Returns true, if the phi is part of a multi-use reduction.
  bool hasUsesOutsideReductionChain() const {
    return HasUsesOutsideReductionChain;
  }

  void setExpressionSunk() { ExpressionSunk = true; }

  bool isExpressionSunk() const { return ExpressionSunk; }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return isOrdered() || isInLoop();
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for vectorizing a phi-node as a sequence of mask-based select
/// instructions.
class LLVM_ABI_FOR_TEST VPBlendRecipe : public VPRecipeWithIRFlags {
public:
  /// The blend operation is a User of the incoming values and of their
  /// respective masks, ordered [I0, M0, I1, M1, I2, M2, ...]. Note that M0 can
  /// be omitted (implied by passing an odd number of operands) in which case
  /// all other incoming values are merged into it.
  VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands,
                const VPIRFlags &Flags, DebugLoc DL)
      : VPRecipeWithIRFlags(VPRecipeBase::VPBlendSC, Operands,
                            Operands[0]->getScalarType(), Flags, DL) {
    assert(Operands.size() >= 2 && "Expected at least two operands!");
    assert(all_of(seq<unsigned>(0, getNumIncomingValues()),
                  [this](unsigned I) {
                    return getIncomingValue(I)->getScalarType() ==
                           getScalarType();
                  }) &&
           "all incoming values must have the same type");
    assert(all_of(seq<unsigned>(isNormalized(), getNumIncomingValues()),
                  [this](unsigned I) {
                    return getMask(I)->getScalarType()->isIntegerTy(1);
                  }) &&
           "masks must be a bool");
    assert(hasRequiredFlagsForOpcode(Instruction::PHI, getScalarType()) &&
           "blends require the flags of the phi they replace");
    setUnderlyingValue(Phi);
  }

  VPBlendRecipe *clone() override { return cloneWithOperands(operands()); }

  VPBlendRecipe *cloneWithOperands(ArrayRef<VPValue *> NewOperands) {
    return new VPBlendRecipe(cast_or_null<PHINode>(getUnderlyingValue()),
                             NewOperands, *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPBlendSC)

  /// A normalized blend is one that has an odd number of operands, whereby the
  /// first operand does not have an associated mask.
  bool isNormalized() const { return getNumOperands() % 2; }

  /// Return the number of incoming values, taking into account when normalized
  /// the first incoming value will have no mask.
  unsigned getNumIncomingValues() const {
    return (getNumOperands() + isNormalized()) / 2;
  }

  /// Return incoming value number \p Idx.
  VPValue *getIncomingValue(unsigned Idx) const {
    return Idx == 0 ? getOperand(0) : getOperand(Idx * 2 - isNormalized());
  }

  /// Return mask number \p Idx.
  VPValue *getMask(unsigned Idx) const {
    assert((Idx > 0 || !isNormalized()) && "First index has no mask!");
    return Idx == 0 ? getOperand(1) : getOperand(Idx * 2 + !isNormalized());
  }

  /// Set mask number \p Idx to \p V.
  void setMask(unsigned Idx, VPValue *V) {
    assert((Idx > 0 || !isNormalized()) && "First index has no mask!");
    assert(V->getScalarType()->isIntegerTy(1) && "Mask must be an i1 (vector)");
    Idx == 0 ? setOperand(1, V) : setOperand(Idx * 2 + !isNormalized(), V);
  }

  void execute(VPTransformState &State) override {
    llvm_unreachable("VPBlendRecipe should be expanded by simplifyBlends");
  }

  /// Return the cost of this VPWidenMemoryRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A common base class for interleaved memory operations.
/// An Interleaved memory operation is a memory access method that combines
/// multiple strided loads/stores into a single wide load/store with shuffles.
/// The first operand is the start address. The optional operands are, in order,
/// the stored values and the mask.
class LLVM_ABI_FOR_TEST VPInterleaveBase : public VPRecipeBase,
                                           public VPIRMetadata {
  const InterleaveGroup<Instruction> *IG;

  /// Indicates if the interleave group is in a conditional block and requires a
  /// mask.
  bool HasMask = false;

  /// Indicates if gaps between members of the group need to be masked out or if
  /// unusued gaps can be loaded speculatively.
  bool NeedsMaskForGaps = false;

protected:
  VPInterleaveBase(VPRecipeTy SC, const InterleaveGroup<Instruction> *IG,
                   ArrayRef<VPValue *> Operands,
                   ArrayRef<VPValue *> StoredValues, VPValue *Mask,
                   bool NeedsMaskForGaps, const VPIRMetadata &MD, DebugLoc DL)
      : VPRecipeBase(SC, Operands, DL), VPIRMetadata(MD), IG(IG),
        NeedsMaskForGaps(NeedsMaskForGaps) {
    // TODO: extend the masked interleaved-group support to reversed access.
    assert((!Mask || !IG->isReverse()) &&
           "Reversed masked interleave-group not supported.");
    if (StoredValues.empty()) {
      for (Instruction *Inst : IG->members()) {
        assert(!Inst->getType()->isVoidTy() && "must have result");
        new VPMultiDefValue(this, Inst, Inst->getType());
      }
    } else {
      for (auto *SV : StoredValues)
        addOperand(SV);
    }
    if (Mask) {
      HasMask = true;
      addOperand(Mask);
    }
  }

public:
  VPInterleaveBase *clone() override = 0;

  static inline bool classof(const VPRecipeBase *R) {
    return R->getVPRecipeID() == VPRecipeBase::VPInterleaveSC ||
           R->getVPRecipeID() == VPRecipeBase::VPInterleaveEVLSC;
  }

  static inline bool classof(const VPUser *U) {
    auto *R = dyn_cast<VPRecipeBase>(U);
    return R && classof(R);
  }

  /// Return the address accessed by this recipe.
  VPValue *getAddr() const {
    return getOperand(0); // Address is the 1st, mandatory operand.
  }

  /// Return the mask used by this recipe. Note that a full mask is represented
  /// by a nullptr.
  VPValue *getMask() const {
    // Mask is optional and the last operand.
    return HasMask ? getOperand(getNumOperands() - 1) : nullptr;
  }

  /// Return true if the access needs a mask because of the gaps.
  bool needsMaskForGaps() const { return NeedsMaskForGaps; }

  const InterleaveGroup<Instruction> *getInterleaveGroup() const { return IG; }

  Instruction *getInsertPos() const { return IG->getInsertPos(); }

  void execute(VPTransformState &State) override {
    llvm_unreachable("VPInterleaveBase should not be instantiated.");
  }

  /// Return the cost of this recipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override = 0;

  /// Returns the number of stored operands of this interleave group. Returns 0
  /// for load interleave groups.
  virtual unsigned getNumStoreOperands() const = 0;

  /// Return the VPValues stored by this interleave group. If it is a load
  /// interleave group, return an empty ArrayRef.
  ArrayRef<VPValue *> getStoredValues() const {
    return {op_end() - (getNumStoreOperands() + (HasMask ? 1 : 0)),
            getNumStoreOperands()};
  }
};

/// VPInterleaveRecipe is a recipe for transforming an interleave group of load
/// or stores into one wide load/store and shuffles. The first operand of a
/// VPInterleave recipe is the address, followed by the stored values, followed
/// by an optional mask.
class LLVM_ABI_FOR_TEST VPInterleaveRecipe final : public VPInterleaveBase {
public:
  VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
                     ArrayRef<VPValue *> StoredValues, VPValue *Mask,
                     bool NeedsMaskForGaps, const VPIRMetadata &MD, DebugLoc DL)
      : VPInterleaveBase(VPRecipeBase::VPInterleaveSC, IG, Addr, StoredValues,
                         Mask, NeedsMaskForGaps, MD, DL) {}

  ~VPInterleaveRecipe() override = default;

  VPInterleaveRecipe *clone() override {
    return new VPInterleaveRecipe(getInterleaveGroup(), getAddr(),
                                  getStoredValues(), getMask(),
                                  needsMaskForGaps(), *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPInterleaveSC)

  /// Generate the wide load or store, and shuffles.
  void execute(VPTransformState &State) override;

  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return Op == getAddr() && !llvm::is_contained(getStoredValues(), Op);
  }

  unsigned getNumStoreOperands() const override {
    return getNumOperands() - (getMask() ? 2 : 1);
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for interleaved memory operations with vector-predication
/// intrinsics. The first operand is the address, the second operand is the
/// explicit vector length. Stored values and mask are optional operands.
class LLVM_ABI_FOR_TEST VPInterleaveEVLRecipe final : public VPInterleaveBase {
public:
  VPInterleaveEVLRecipe(VPInterleaveRecipe &R, VPValue &EVL, VPValue *Mask)
      : VPInterleaveBase(VPRecipeBase::VPInterleaveEVLSC,
                         R.getInterleaveGroup(), {R.getAddr(), &EVL},
                         R.getStoredValues(), Mask, R.needsMaskForGaps(), R,
                         R.getDebugLoc()) {
    assert(!getInterleaveGroup()->isReverse() &&
           "Reversed interleave-group with tail folding is not supported.");
    assert(!needsMaskForGaps() && "Interleaved access with gap mask is not "
                                  "supported for scalable vector.");
  }

  ~VPInterleaveEVLRecipe() override = default;

  VPInterleaveEVLRecipe *clone() override {
    llvm_unreachable("cloning not implemented yet");
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPInterleaveEVLSC)

  /// The VPValue of the explicit vector length.
  VPValue *getEVL() const { return getOperand(1); }

  /// Generate the wide load or store, and shuffles.
  void execute(VPTransformState &State) override;

  /// The recipe only uses the first lane of the address, and EVL operand.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return (Op == getAddr() && !llvm::is_contained(getStoredValues(), Op)) ||
           Op == getEVL();
  }

  unsigned getNumStoreOperands() const override {
    return getNumOperands() - (getMask() ? 3 : 2);
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe to represent inloop, ordered or partial reduction operations. It
/// performs a reduction on a vector operand into a scalar (vector in the case
/// of a partial reduction) value, and adds the result to a chain. The Operands
/// are {ChainOp, VecOp, [Condition]}.
class LLVM_ABI_FOR_TEST VPReductionRecipe : public VPRecipeWithIRFlags {

  /// The recurrence kind for the reduction in question.
  RecurKind RdxKind;
  /// Whether the reduction is conditional.
  bool IsConditional = false;
  ReductionStyle Style;

protected:
  VPReductionRecipe(VPRecipeTy SC, RecurKind RdxKind, FastMathFlags FMFs,
                    Instruction *I, ArrayRef<VPValue *> Operands,
                    VPValue *CondOp, ReductionStyle Style, DebugLoc DL)
      : VPRecipeWithIRFlags(SC, Operands, Operands[0]->getScalarType(), FMFs,
                            DL),
        RdxKind(RdxKind), Style(Style) {
    assert(all_of(Operands,
                  [this](VPValue *VPV) {
                    return VPV->getScalarType() == getScalarType() ||
                           (isa<VPInstruction>(VPV) &&
                            cast<VPInstruction>(VPV)->getOpcode() ==
                                VPInstruction::ExplicitVectorLength);
                  }) &&
           "all incoming values must have the same type");
    if (CondOp) {
      assert(CondOp->getScalarType()->isIntegerTy(1) &&
             "CondOp must be a bool");
      IsConditional = true;
      addOperand(CondOp);
    }
    setUnderlyingValue(I);
  }

public:
  VPReductionRecipe(RecurKind RdxKind, FastMathFlags FMFs, Instruction *I,
                    VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
                    ReductionStyle Style, DebugLoc DL = DebugLoc::getUnknown())
      : VPReductionRecipe(VPRecipeBase::VPReductionSC, RdxKind, FMFs, I,
                          {ChainOp, VecOp}, CondOp, Style, DL) {}

  VPReductionRecipe(const RecurKind RdxKind, FastMathFlags FMFs,
                    VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
                    ReductionStyle Style, DebugLoc DL = DebugLoc::getUnknown())
      : VPReductionRecipe(VPRecipeBase::VPReductionSC, RdxKind, FMFs, nullptr,
                          {ChainOp, VecOp}, CondOp, Style, DL) {}

  ~VPReductionRecipe() override = default;

  VPReductionRecipe *clone() override {
    return new VPReductionRecipe(RdxKind, getFastMathFlagsOrNone(),
                                 getUnderlyingInstr(), getChainOp(), getVecOp(),
                                 getCondOp(), Style, getDebugLoc());
  }

  static inline bool classof(const VPRecipeBase *R) {
    return R->getVPRecipeID() == VPRecipeBase::VPReductionSC ||
           R->getVPRecipeID() == VPRecipeBase::VPReductionEVLSC;
  }

  static inline bool classof(const VPUser *U) {
    auto *R = dyn_cast<VPRecipeBase>(U);
    return R && classof(R);
  }

  static inline bool classof(const VPValue *VPV) {
    const VPRecipeBase *R = VPV->getDefiningRecipe();
    return R && classof(R);
  }

  static inline bool classof(const VPSingleDefRecipe *R) {
    return classof(static_cast<const VPRecipeBase *>(R));
  }

  /// Generate the reduction in the loop.
  void execute(VPTransformState &State) override;

  /// Return the cost of VPReductionRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Return the recurrence kind for the in-loop reduction.
  RecurKind getRecurrenceKind() const { return RdxKind; }
  /// Return true if the in-loop reduction is ordered.
  bool isOrdered() const { return std::holds_alternative<RdxOrdered>(Style); };
  /// Return true if the in-loop reduction is conditional.
  bool isConditional() const { return IsConditional; };
  /// Returns true if the reduction outputs a vector with a scaled down VF.
  bool isPartialReduction() const {
    return std::holds_alternative<RdxUnordered>(Style);
  }
  /// Returns true if the reduction is in-loop.
  bool isInLoop() const {
    return std::holds_alternative<RdxInLoop>(Style) ||
           std::holds_alternative<RdxOrdered>(Style);
  }
  /// The VPValue of the scalar Chain being accumulated.
  VPValue *getChainOp() const { return getOperand(0); }
  /// The VPValue of the vector value to be reduced.
  VPValue *getVecOp() const { return getOperand(1); }
  /// The VPValue of the condition for the block.
  VPValue *getCondOp() const {
    return isConditional() ? getOperand(getNumOperands() - 1) : nullptr;
  }
  /// Get the factor that the VF of this recipe's output should be scaled by, or
  /// 1 if it isn't scaled.
  unsigned getVFScaleFactor() const {
    auto *Partial = std::get_if<RdxUnordered>(&Style);
    return Partial ? Partial->VFScaleFactor : 1;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe to represent inloop reduction operations with vector-predication
/// intrinsics, performing a reduction on a vector operand with the explicit
/// vector length (EVL) into a scalar value, and adding the result to a chain.
/// The Operands are {ChainOp, VecOp, EVL, [Condition]}.
class LLVM_ABI_FOR_TEST VPReductionEVLRecipe : public VPReductionRecipe {
public:
  VPReductionEVLRecipe(VPReductionRecipe &R, VPValue &EVL, VPValue *CondOp,
                       DebugLoc DL = DebugLoc::getUnknown())
      : VPReductionRecipe(VPRecipeBase::VPReductionEVLSC, R.getRecurrenceKind(),
                          R.getFastMathFlagsOrNone(),
                          cast_or_null<Instruction>(R.getUnderlyingValue()),
                          {R.getChainOp(), R.getVecOp(), &EVL}, CondOp,
                          getReductionStyle(R.isInLoop(), R.isOrdered(),
                                            R.getVFScaleFactor()),
                          DL) {}

  ~VPReductionEVLRecipe() override = default;

  VPReductionEVLRecipe *clone() override {
    llvm_unreachable("cloning not implemented yet");
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPReductionEVLSC)

  /// Generate the reduction in the loop
  void execute(VPTransformState &State) override;

  /// The VPValue of the explicit vector length.
  VPValue *getEVL() const { return getOperand(2); }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return Op == getEVL();
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// VPReplicateRecipe replicates a given instruction producing multiple scalar
/// copies of the original scalar type, one per lane, instead of producing a
/// single copy of widened type for all lanes. If the instruction is known to be
/// a single scalar, only one copy will be generated.
class LLVM_ABI_FOR_TEST VPReplicateRecipe : public VPRecipeWithIRFlags,
                                            public VPIRMetadata {
  /// Indicator if only a single replica per lane is needed.
  bool IsSingleScalar;

  /// Indicator if the replicas are also predicated.
  bool IsPredicated;

public:
  VPReplicateRecipe(Instruction *I, ArrayRef<VPValue *> Operands,
                    bool IsSingleScalar, VPValue *Mask = nullptr,
                    const VPIRFlags &Flags = {}, VPIRMetadata Metadata = {},
                    DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeWithIRFlags(VPRecipeBase::VPReplicateSC, Operands,
                            computeScalarType(I, Operands), Flags, DL),
        VPIRMetadata(Metadata), IsSingleScalar(IsSingleScalar),
        IsPredicated(Mask) {
    assert((!IsSingleScalar || !I->isCast()) &&
           "Single-scalar casts should use VPInstruction");
    setUnderlyingValue(I);
    if (Mask)
      addOperand(Mask);
  }

  ~VPReplicateRecipe() override = default;

  /// Compute the scalar result type for a VPReplicateRecipe wrapping \p I with
  /// \p Operands (excluding any predicate mask).
  static Type *computeScalarType(const Instruction *I,
                                 ArrayRef<VPValue *> Operands);

  VPReplicateRecipe *clone() override { return cloneWithOperands(operands()); }

  VPReplicateRecipe *cloneWithOperands(ArrayRef<VPValue *> NewOperands) {
    auto *Copy = new VPReplicateRecipe(
        getUnderlyingInstr(), NewOperands, IsSingleScalar,
        isPredicated() ? getMask() : nullptr, *this, *this, getDebugLoc());
    Copy->transferFlags(*this);
    return Copy;
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPReplicateSC)

  /// Generate replicas of the desired Ingredient. Replicas will be generated
  /// for all parts and lanes unless a specific part and lane are specified in
  /// the \p State.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPReplicateRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Return the cost of scalarizing a call to \p CalledFn with argument
  /// operands \p ArgOps for a given \p VF.
  static InstructionCost computeCallCost(Function *CalledFn, Type *ResultTy,
                                         ArrayRef<const VPValue *> ArgOps,
                                         bool IsSingleScalar, ElementCount VF,
                                         VPCostContext &Ctx);

  /// Returns true if the recipe produces a single scalar value.
  bool isSingleScalar() const { return IsSingleScalar; }

  /// Returns true if the recipe produces scalar values for all VF lanes.
  bool doesGeneratePerAllLanes() const { return !IsSingleScalar; }

  bool isPredicated() const { return IsPredicated; }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return isSingleScalar();
  }

  /// Returns true if the recipe uses scalars of operand \p Op.
  bool usesScalars(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }

  /// Return the mask of a predicated VPReplicateRecipe.
  VPValue *getMask() {
    assert(isPredicated() && "Trying to get the mask of a unpredicated recipe");
    return getOperand(getNumOperands() - 1);
  }

  /// Return the recipe's operands, excluding the mask of a predicated recipe.
  operand_range operandsWithoutMask() {
    return isPredicated() ? drop_end(operands()) : operands();
  }

  /// Returns the number of operands, excluding the mask if the recipe is
  /// predicated.
  unsigned getNumOperandsWithoutMask() const {
    return getNumOperands() - isPredicated();
  }

  unsigned getOpcode() const { return getUnderlyingInstr()->getOpcode(); }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for generating conditional branches on the bits of a mask.
class LLVM_ABI_FOR_TEST VPBranchOnMaskRecipe : public VPRecipeBase,
                                               public VPIRMetadata {
public:
  VPBranchOnMaskRecipe(VPValue *BlockInMask, DebugLoc DL,
                       const VPIRMetadata &Metadata = {})
      : VPRecipeBase(VPRecipeBase::VPBranchOnMaskSC, {BlockInMask}, DL),
        VPIRMetadata(Metadata) {}

  VPBranchOnMaskRecipe *clone() override {
    return new VPBranchOnMaskRecipe(getOperand(0), getDebugLoc(), *this);
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPBranchOnMaskSC)

  /// Generate the extraction of the appropriate bit from the block mask and the
  /// conditional branch.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPBranchOnMaskRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override {
    O << Indent << "BRANCH-ON-MASK ";
    printOperands(O, SlotTracker);
  }
#endif

  /// Returns true if the recipe uses scalars of operand \p Op.
  bool usesScalars(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }
};

/// A recipe to combine multiple recipes into a single 'expression' recipe,
/// which should be considered a single entity for cost-modeling and transforms.
/// The recipe needs to be 'decomposed', i.e. replaced by its individual
/// expression recipes, before execute. The individual expression recipes are
/// completely disconnected from the def-use graph of other recipes not part of
/// the expression. Def-use edges between pairs of expression recipes remain
/// intact, whereas every edge between an expression recipe and a recipe outside
/// the expression is elevated to connect the non-expression recipe with the
/// VPExpressionRecipe itself.
class VPExpressionRecipe : public VPSingleDefRecipe {
  /// Recipes included in this VPExpressionRecipe. This could contain
  /// duplicates.
  SmallVector<VPSingleDefRecipe *> ExpressionRecipes;

  /// Temporary VPValues used for external operands of the expression, i.e.
  /// operands not defined by recipes in the expression.
  SmallVector<VPValue *> LiveInPlaceholders;

  enum class ExpressionTypes {
    /// Represents an inloop extended reduction operation, performing a
    /// reduction on an extended vector operand into a scalar value, and adding
    /// the result to a chain.
    ExtendedReduction,
    /// Represents an inloop extended reduction operation, which is negated,
    /// then reduced before adding the result to a chain.
    NegatedExtendedReduction,
    /// Represent an inloop multiply-accumulate reduction, multiplying the
    /// extended vector operands, performing a reduction.add on the result, and
    /// adding the scalar result to a chain.
    ExtMulAccReduction,
    /// Represent an inloop multiply-accumulate reduction, multiplying the
    /// vector operands, performing a reduction.add on the result, and adding
    /// the scalar result to a chain.
    MulAccReduction,
    /// Represent an inloop multiply-accumulate reduction, multiplying the
    /// extended vector operands, negating the multiplication, performing a
    /// reduction.add on the result, and adding the scalar result to a chain.
    ExtNegatedMulAccReduction,
  };

  /// Type of the expression.
  ExpressionTypes ExpressionType;

public:
  /// Construct a new VPExpressionRecipe by internalizing recipes in \p
  /// ExpressionRecipes. External operands (i.e. not defined by another recipe
  /// in the expression) are replaced by temporary VPValues and the original
  /// operands are transferred to the VPExpressionRecipe itself. Clone recipes
  /// as needed (excluding last) to ensure they are only used by other recipes
  /// in the expression.
  VPExpressionRecipe(ExpressionTypes ExpressionType,
                     ArrayRef<VPSingleDefRecipe *> ExpressionRecipes);

  VPExpressionRecipe(VPWidenCastRecipe *Ext, VPReductionRecipe *Red)
      : VPExpressionRecipe(ExpressionTypes::ExtendedReduction, {Ext, Red}) {}
  VPExpressionRecipe(VPWidenCastRecipe *Ext, VPWidenRecipe *Neg,
                     VPReductionRecipe *Red)
      : VPExpressionRecipe(ExpressionTypes::NegatedExtendedReduction,
                           {Ext, Neg, Red}) {
    assert((Red->getRecurrenceKind() == RecurKind::Add ||
            Red->getRecurrenceKind() == RecurKind::FAdd ||
            Red->getRecurrenceKind() == RecurKind::AddChainWithSubs) &&
           "Expected an add or add-chain-with-subs reduction");
    if (Neg->getOpcode() == Instruction::Sub) {
      [[maybe_unused]] auto *SubConst = dyn_cast<VPConstantInt>(getOperand(1));
      assert(SubConst && SubConst->isZero() && "Expected a negating sub");
    } else
      assert(Neg->getOpcode() == Instruction::FNeg && "Unexpected opcode");
  }
  VPExpressionRecipe(VPWidenRecipe *Mul, VPReductionRecipe *Red)
      : VPExpressionRecipe(ExpressionTypes::MulAccReduction, {Mul, Red}) {}
  VPExpressionRecipe(VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,
                     VPWidenRecipe *Mul, VPReductionRecipe *Red)
      : VPExpressionRecipe(ExpressionTypes::ExtMulAccReduction,
                           {Ext0, Ext1, Mul, Red}) {}
  VPExpressionRecipe(VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,
                     VPWidenRecipe *Mul, VPWidenRecipe *Neg,
                     VPReductionRecipe *Red)
      : VPExpressionRecipe(ExpressionTypes::ExtNegatedMulAccReduction,
                           {Ext0, Ext1, Mul, Neg, Red}) {
    assert((Mul->getOpcode() == Instruction::Mul ||
            Mul->getOpcode() == Instruction::FMul) &&
           "Expected a mul");
    assert((Red->getRecurrenceKind() == RecurKind::Add ||
            Red->getRecurrenceKind() == RecurKind::FAdd ||
            Red->getRecurrenceKind() == RecurKind::AddChainWithSubs) &&
           "Expected an add or add-chain-with-subs reduction");
    assert(getNumOperands() >= 3 && "Expected at least three operands");
    if (Neg->getOpcode() == Instruction::Sub) {
      [[maybe_unused]] auto *SubConst = dyn_cast<VPConstantInt>(getOperand(2));
      assert(SubConst && SubConst->isZero() &&
             Neg->getOpcode() == Instruction::Sub && "Expected a negating sub");
    } else
      assert(Neg->getOpcode() == Instruction::FNeg && "Unexpected opcode");
  }

  ~VPExpressionRecipe() override {
    SmallPtrSet<VPSingleDefRecipe *, 4> ExpressionRecipesSeen;
    for (auto *R : reverse(ExpressionRecipes)) {
      if (ExpressionRecipesSeen.insert(R).second)
        delete R;
    }
    for (VPValue *T : LiveInPlaceholders)
      delete T;
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPExpressionSC)

  VPExpressionRecipe *clone() override {
    assert(!ExpressionRecipes.empty() && "empty expressions should be removed");
    SmallVector<VPSingleDefRecipe *> NewExpressiondRecipes;
    for (auto *R : ExpressionRecipes)
      NewExpressiondRecipes.push_back(R->clone());
    for (auto *New : NewExpressiondRecipes) {
      for (const auto &[Idx, Old] : enumerate(ExpressionRecipes))
        New->replaceUsesOfWith(Old, NewExpressiondRecipes[Idx]);
      // Update placeholder operands in the cloned recipe to use the external
      // operands, to be internalized when the cloned expression is constructed.
      for (const auto &[Placeholder, OutsideOp] :
           zip(LiveInPlaceholders, operands()))
        New->replaceUsesOfWith(Placeholder, OutsideOp);
    }
    return new VPExpressionRecipe(ExpressionType, NewExpressiondRecipes);
  }

  /// Return and insert the recipes of the expression back into the VPlan,
  /// directly before the current recipe. Leaves the expression recipe empty,
  /// which must be removed before codegen.
  SmallVector<VPSingleDefRecipe *> decompose();

  /// Returns the expression type of this recipe.
  ExpressionTypes getExpressionType() const { return ExpressionType; }

  unsigned getVFScaleFactor() const {
    auto *PR = dyn_cast<VPReductionRecipe>(ExpressionRecipes.back());
    return PR ? PR->getVFScaleFactor() : 1;
  }

  /// Method for generating code, must not be called as this recipe is abstract.
  void execute(VPTransformState &State) override {
    llvm_unreachable("recipe must be removed before execute");
  }

  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if this expression contains recipes that may read from or
  /// write to memory.
  bool mayReadOrWriteMemory() const;

  /// Returns true if this expression contains recipes that may have side
  /// effects.
  bool mayHaveSideEffects() const;

  /// Returns true if this VPExpressionRecipe produces a single scalar.
  bool isVectorToScalar() const;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
/// control converges back from a Branch-on-Mask. The phi nodes are needed in
/// order to merge values that are set under such a branch and feed their uses.
/// The phi nodes can be scalar or vector depending on the users of the value.
/// This recipe works in concert with VPBranchOnMaskRecipe.
class LLVM_ABI_FOR_TEST VPPredInstPHIRecipe : public VPSingleDefRecipe {
public:
  /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
  /// nodes after merging back from a Branch-on-Mask.
  VPPredInstPHIRecipe(VPValue *PredV, DebugLoc DL)
      : VPSingleDefRecipe(VPRecipeBase::VPPredInstPHISC, PredV,
                          PredV->getScalarType(), /*UV=*/nullptr, DL) {}
  ~VPPredInstPHIRecipe() override = default;

  VPPredInstPHIRecipe *clone() override {
    return new VPPredInstPHIRecipe(getOperand(0), getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPPredInstPHISC)

  /// Generates phi nodes for live-outs (from a replicate region) as needed to
  /// retain SSA form.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPPredInstPHIRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // TODO: Compute accurate cost after retiring the legacy cost model.
    return 0;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A common mixin class for widening memory operations. An optional mask can be
/// provided as the last operand.
class LLVM_ABI_FOR_TEST VPWidenMemoryRecipe : public VPIRMetadata {
protected:
  Instruction &Ingredient;

  /// Alignment information for this memory access.
  Align Alignment;

  /// Whether the accessed addresses are consecutive.
  bool Consecutive;

  /// Whether the memory access is masked.
  bool IsMasked = false;

  void setMask(VPValue *Mask) {
    assert(!IsMasked && "cannot re-set mask");
    if (!Mask)
      return;
    assert(Mask->getScalarType()->isIntegerTy(1) &&
           "Mask must be an i1 (vector)");
    getAsRecipe()->addOperand(Mask);
    IsMasked = true;
  }

  VPWidenMemoryRecipe(Instruction &I, bool Consecutive,
                      const VPIRMetadata &Metadata)
      : VPIRMetadata(Metadata), Ingredient(I),
        Alignment(getLoadStoreAlignment(&I)), Consecutive(Consecutive) {}

public:
  virtual ~VPWidenMemoryRecipe() = default;

  /// Return a VPRecipeBase* to the current object.
  virtual VPRecipeBase *getAsRecipe() = 0;
  virtual const VPRecipeBase *getAsRecipe() const = 0;

  /// Return whether the loaded-from / stored-to addresses are consecutive.
  bool isConsecutive() const { return Consecutive; }

  /// Return the address accessed by this recipe.
  VPValue *getAddr() const { return getAsRecipe()->getOperand(0); }

  /// Returns true if the recipe is masked.
  bool isMasked() const { return IsMasked; }

  /// Return the mask used by this recipe. Note that a full mask is represented
  /// by a nullptr.
  VPValue *getMask() const {
    // Mask is optional and therefore the last operand.
    const VPRecipeBase *R = getAsRecipe();
    return isMasked() ? R->getOperand(R->getNumOperands() - 1) : nullptr;
  }

  /// Returns the alignment of the memory access.
  Align getAlign() const { return Alignment; }

  /// Return the cost of this VPWidenMemoryRecipe.
  InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const;

  Instruction &getIngredient() const { return Ingredient; }
};

/// A recipe for widening load operations, using the address to load from and an
/// optional mask.
struct LLVM_ABI_FOR_TEST VPWidenLoadRecipe final : public VPSingleDefRecipe,
                                                   public VPWidenMemoryRecipe {
  VPWidenLoadRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask,
                    bool Consecutive, const VPIRMetadata &Metadata, DebugLoc DL)
      : VPSingleDefRecipe(VPRecipeBase::VPWidenLoadSC, {Addr}, Load.getType(),
                          &Load, DL),
        VPWidenMemoryRecipe(Load, Consecutive, Metadata) {
    setMask(Mask);
  }

  VPWidenLoadRecipe *clone() override {
    return new VPWidenLoadRecipe(cast<LoadInst>(Ingredient), getAddr(),
                                 getMask(), Consecutive, *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenLoadSC);

  /// Returns the opcode of the widened load.
  unsigned getOpcode() const { return Instruction::Load; }

  /// Generate a wide load or gather.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenLoadRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    return VPWidenMemoryRecipe::computeCost(VF, Ctx);
  }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    // Widened, consecutive loads operations only demand the first lane of
    // their address.
    return Op == getAddr() && isConsecutive();
  }

protected:
  VPRecipeBase *getAsRecipe() override;
  const VPRecipeBase *getAsRecipe() const override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for widening load operations with vector-predication intrinsics,
/// using the address to load from, the explicit vector length and an optional
/// mask.
struct LLVM_ABI_FOR_TEST VPWidenLoadEVLRecipe final
    : public VPSingleDefRecipe,
      public VPWidenMemoryRecipe {
  VPWidenLoadEVLRecipe(VPWidenLoadRecipe &L, VPValue *Addr, VPValue &EVL,
                       VPValue *Mask)
      : VPSingleDefRecipe(VPRecipeBase::VPWidenLoadEVLSC, {Addr, &EVL},
                          L.getIngredient().getType(), &L.getIngredient(),
                          L.getDebugLoc()),
        VPWidenMemoryRecipe(L.getIngredient(), L.isConsecutive(), L) {
    setMask(Mask);
  }

  VPWidenLoadEVLRecipe *clone() override {
    llvm_unreachable("cloning not supported");
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenLoadEVLSC)

  /// Returns the opcode of the widened load.
  unsigned getOpcode() const { return Instruction::Load; }

  /// Return the EVL operand.
  VPValue *getEVL() const { return getOperand(1); }

  /// Generate the wide load or gather.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenLoadEVLRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    // Widened loads only demand the first lane of EVL and consecutive loads
    // only demand the first lane of their address.
    return Op == getEVL() || (Op == getAddr() && isConsecutive());
  }

protected:
  VPRecipeBase *getAsRecipe() override;
  const VPRecipeBase *getAsRecipe() const override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for widening store operations, using the stored value, the address
/// to store to and an optional mask.
struct LLVM_ABI_FOR_TEST VPWidenStoreRecipe final : public VPRecipeBase,
                                                    public VPWidenMemoryRecipe {
  VPWidenStoreRecipe(StoreInst &Store, VPValue *Addr, VPValue *StoredVal,
                     VPValue *Mask, bool Consecutive,
                     const VPIRMetadata &Metadata, DebugLoc DL)
      : VPRecipeBase(VPRecipeBase::VPWidenStoreSC, {Addr, StoredVal}, DL),
        VPWidenMemoryRecipe(Store, Consecutive, Metadata) {
    setMask(Mask);
  }

  VPWidenStoreRecipe *clone() override {
    return new VPWidenStoreRecipe(cast<StoreInst>(Ingredient), getAddr(),
                                  getStoredValue(), getMask(), Consecutive,
                                  *this, getDebugLoc());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenStoreSC);

  /// Return the value stored by this recipe.
  VPValue *getStoredValue() const { return getOperand(1); }

  /// Generate a wide store or scatter.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenStoreRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    return VPWidenMemoryRecipe::computeCost(VF, Ctx);
  }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    // Widened, consecutive stores only demand the first lane of their address,
    // unless the same operand is also stored.
    return Op == getAddr() && isConsecutive() && Op != getStoredValue();
  }

protected:
  VPRecipeBase *getAsRecipe() override;
  const VPRecipeBase *getAsRecipe() const override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for widening store operations with vector-predication intrinsics,
/// using the value to store, the address to store to, the explicit vector
/// length and an optional mask.
struct LLVM_ABI_FOR_TEST VPWidenStoreEVLRecipe final
    : public VPRecipeBase,
      public VPWidenMemoryRecipe {
  VPWidenStoreEVLRecipe(VPWidenStoreRecipe &S, VPValue *Addr,
                        VPValue *StoredVal, VPValue &EVL, VPValue *Mask)
      : VPRecipeBase(VPRecipeBase::VPWidenStoreEVLSC, {Addr, StoredVal, &EVL},
                     S.getDebugLoc()),
        VPWidenMemoryRecipe(S.getIngredient(), S.isConsecutive(), S) {
    setMask(Mask);
  }

  VPWidenStoreEVLRecipe *clone() override {
    llvm_unreachable("cloning not supported");
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenStoreEVLSC)

  /// Return the address accessed by this recipe.
  VPValue *getStoredValue() const { return getOperand(1); }

  /// Return the EVL operand.
  VPValue *getEVL() const { return getOperand(2); }

  /// Generate the wide store or scatter.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPWidenStoreEVLRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    if (Op == getEVL()) {
      assert(getStoredValue() != Op && "unexpected store of EVL");
      return true;
    }
    // Widened, consecutive memory operations only demand the first lane of
    // their address, unless the same operand is also stored. That latter can
    // happen with opaque pointers.
    return Op == getAddr() && isConsecutive() && Op != getStoredValue();
  }

protected:
  VPRecipeBase *getAsRecipe() override;
  const VPRecipeBase *getAsRecipe() const override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// Recipe to expand a SCEV expression.
class VPExpandSCEVRecipe : public VPSingleDefRecipe {
  const SCEV *Expr;

public:
  VPExpandSCEVRecipe(const SCEV *Expr);

  ~VPExpandSCEVRecipe() override = default;

  VPExpandSCEVRecipe *clone() override { return new VPExpandSCEVRecipe(Expr); }

  VP_CLASSOF_IMPL(VPRecipeBase::VPExpandSCEVSC)

  void execute(VPTransformState &State) override {
    llvm_unreachable("SCEV expressions must be expanded before final execute");
  }

  /// Return the cost of this VPExpandSCEVRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // TODO: Compute accurate cost after retiring the legacy cost model.
    return 0;
  }

  const SCEV *getSCEV() const { return Expr; }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for generating the active lane mask for the vector loop that is
/// used to predicate the vector operations.
class VPActiveLaneMaskPHIRecipe : public VPHeaderPHIRecipe {
public:
  VPActiveLaneMaskPHIRecipe(VPValue *StartMask, DebugLoc DL)
      : VPHeaderPHIRecipe(VPRecipeBase::VPActiveLaneMaskPHISC, nullptr,
                          StartMask, DL) {}

  ~VPActiveLaneMaskPHIRecipe() override = default;

  VPActiveLaneMaskPHIRecipe *clone() override {
    auto *R = new VPActiveLaneMaskPHIRecipe(getOperand(0), getDebugLoc());
    if (getNumOperands() == 2)
      R->addBackedgeValue(getOperand(1));
    return R;
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPActiveLaneMaskPHISC)

  /// Generate the active lane mask phi of the vector loop.
  void execute(VPTransformState &State) override;

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for generating the phi node tracking the current scalar iteration
/// index. It starts at the start value of the canonical induction and gets
/// incremented by the number of scalar iterations processed by the vector loop
/// iteration. The increment does not have to be loop invariant.
class VPCurrentIterationPHIRecipe : public VPHeaderPHIRecipe {
public:
  VPCurrentIterationPHIRecipe(VPValue *StartIV, DebugLoc DL)
      : VPHeaderPHIRecipe(VPRecipeBase::VPCurrentIterationPHISC, nullptr,
                          StartIV, DL) {}

  ~VPCurrentIterationPHIRecipe() override = default;

  VPCurrentIterationPHIRecipe *clone() override {
    llvm_unreachable("cloning not implemented yet");
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPCurrentIterationPHISC)

  void execute(VPTransformState &State) override {
    llvm_unreachable("cannot execute this recipe, should be replaced by a "
                     "scalar phi recipe");
  }

  /// Return the cost of this VPCurrentIterationPHIRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // For now, match the behavior of the legacy cost model.
    return 0;
  }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  LLVM_ABI_FOR_TEST void printRecipe(raw_ostream &O, const Twine &Indent,
                                     VPSlotTracker &SlotTracker) const override;
#endif
};

/// A Recipe for widening the canonical induction variable of the vector loop.
/// First operand is the canonical IV recipe, a second step operand  (VF * Part)
/// is added during unrolling.
class VPWidenCanonicalIVRecipe : public VPRecipeWithIRFlags {
public:
  VPWidenCanonicalIVRecipe(VPRegionValue *CanonicalIV,
                           const VPIRFlags::WrapFlagsTy &Flags = {})
      : VPRecipeWithIRFlags(VPRecipeBase::VPWidenCanonicalIVSC, CanonicalIV,
                            CanonicalIV->getType(), Flags) {}

  ~VPWidenCanonicalIVRecipe() override = default;

  VPWidenCanonicalIVRecipe *clone() override {
    auto *WideCanIV =
        new VPWidenCanonicalIVRecipe(getCanonicalIV(), getNoWrapFlags());
    if (VPValue *Step = getStepValue())
      WideCanIV->addPerPartStep(Step);
    return WideCanIV;
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPWidenCanonicalIVSC)

  void execute(VPTransformState &State) override {
    llvm_unreachable("Expected prior expansion of WidenCanonicalIV recipes");
  }

  /// Return the cost of this VPWidenCanonicalIVPHIRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override {
    // TODO: Compute accurate cost after retiring the legacy cost model.
    return 0;
  }

  /// Return the canonical IV being widened.
  VPRegionValue *getCanonicalIV() const {
    return cast<VPRegionValue>(getOperand(0));
  }

  VPValue *getStepValue() const {
    return getNumOperands() == 2 ? getOperand(1) : nullptr;
  }

  /// Add the per-part step (VF * Part) used for unrolled parts.
  void addPerPartStep(VPValue *Step) {
    assert(Step->getScalarType() == getScalarType() &&
           "per-part step must have the same type as the canonical IV");
    VPUser::addOperand(Step);
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for converting \p Current into \p Start + \p Current * \p Step.
/// FastMathFlags are derived from the \p FPBinOp in the case of FP inductions,
/// and the passed NoWrap \p Flags apply in the case of Ptr and Int inductions.
class LLVM_ABI_FOR_TEST VPDerivedIVRecipe : public VPRecipeWithIRFlags {
  /// Kind of the induction.
  const InductionDescriptor::InductionKind Kind;
  /// If not nullptr, the floating point induction binary operator. Must be set
  /// for floating point inductions.
  const FPMathOperator *FPBinOp;

public:
  VPDerivedIVRecipe(InductionDescriptor::InductionKind Kind,
                    const FPMathOperator *FPBinOp, VPValue *Start,
                    VPValue *Current, VPValue *Step,
                    const VPIRFlags::WrapFlagsTy &Flags = {})
      : VPRecipeWithIRFlags(VPRecipeBase::VPDerivedIVSC, {Start, Current, Step},
                            Start->getScalarType(), Flags),
        Kind(Kind), FPBinOp(FPBinOp) {}

  ~VPDerivedIVRecipe() override = default;

  VPDerivedIVRecipe *clone() override {
    return new VPDerivedIVRecipe(Kind, FPBinOp, getStartValue(), getOperand(1),
                                 getStepValue(), getNoWrapFlags());
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPDerivedIVSC)

  void execute(VPTransformState &State) override {
    llvm_unreachable("Expected prior expansion of this recipe");
  }

  /// Return the cost of this VPDerivedIVRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  VPValue *getStartValue() const { return getOperand(0); }
  VPValue *getIndex() const { return getOperand(1); }
  VPValue *getStepValue() const { return getOperand(2); }
  const FPMathOperator *getFPBinOp() const { return FPBinOp; }
  InductionDescriptor::InductionKind getInductionKind() const { return Kind; }

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// A recipe for handling phi nodes of integer and floating-point inductions,
/// producing their scalar values. Before unrolling by UF the recipe represents
/// the VF*UF scalar values to be produced, or UF scalar values if only first
/// lane is used, and has 3 operands: IV, step and VF. Unrolling adds one extra
/// operand StartIndex to all unroll parts except part 0, as the recipe
/// represents the VF scalar values (this number of values is taken from
/// State.VF rather than from the VF operand) starting at IV + StartIndex.
class LLVM_ABI_FOR_TEST VPScalarIVStepsRecipe : public VPRecipeWithIRFlags {
  Instruction::BinaryOps InductionOpcode;

public:
  VPScalarIVStepsRecipe(VPValue *IV, VPValue *Step, VPValue *VF,
                        Instruction::BinaryOps Opcode, FastMathFlags FMFs = {},
                        DebugLoc DL = DebugLoc::getUnknown())
      : VPRecipeWithIRFlags(VPRecipeBase::VPScalarIVStepsSC, {IV, Step, VF},
                            IV->getScalarType(), FMFs, DL),
        InductionOpcode(Opcode) {}

  ~VPScalarIVStepsRecipe() override = default;

  VPScalarIVStepsRecipe *clone() override {
    auto *NewR = new VPScalarIVStepsRecipe(
        getOperand(0), getOperand(1), getOperand(2), InductionOpcode,
        getFastMathFlagsOrNone(), getDebugLoc());
    if (VPValue *StartIndex = getStartIndex())
      NewR->setStartIndex(StartIndex);
    return NewR;
  }

  VP_CLASSOF_IMPL(VPRecipeBase::VPScalarIVStepsSC)

  /// Generate the scalarized versions of the phi node as needed by their users.
  void execute(VPTransformState &State) override;

  /// Return the cost of this VPScalarIVStepsRecipe.
  InstructionCost computeCost(ElementCount VF,
                              VPCostContext &Ctx) const override;

  VPValue *getStepValue() const { return getOperand(1); }

  /// Return the number of scalars to produce per unroll part, used to compute
  /// StartIndex during unrolling.
  VPValue *getVFValue() const { return getOperand(2); }

  /// Return the StartIndex, or null if known to be zero, valid only after
  /// unrolling.
  VPValue *getStartIndex() const {
    return getNumOperands() == 4 ? getOperand(3) : nullptr;
  }

  /// Set or add the StartIndex operand.
  void setStartIndex(VPValue *StartIndex) {
    if (getNumOperands() == 4)
      setOperand(3, StartIndex);
    else
      addOperand(StartIndex);
  }

  /// Returns true if this recipe produces scalar values for all VF lanes.
  bool doesGeneratePerAllLanes() const;

  /// Returns true if the recipe only uses the first lane of operand \p Op.
  bool usesFirstLaneOnly(const VPValue *Op) const override {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return true;
  }

  Instruction::BinaryOps getInductionOpcode() const { return InductionOpcode; }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the recipe.
  void printRecipe(raw_ostream &O, const Twine &Indent,
                   VPSlotTracker &SlotTracker) const override;
#endif
};

/// CastInfo helper for casting from VPRecipeBase to a mixin class that is not
/// part of the VPRecipeBase class hierarchy (e.g. VPPhiAccessors,
/// VPIRMetadata).
namespace vpdetail {
template <typename VPMixin, typename... RecipeTys>
struct CastInfoMixinImpl
    : public DefaultDoCastIfPossible<VPMixin *, VPRecipeBase *,
                                     CastInfoMixinImpl<VPMixin, RecipeTys...>> {
  static_assert((std::is_base_of_v<VPMixin, RecipeTys> && ...),
                "Each type in RecipeTys must derive from VPMixin");

  /// Used by isa.
  static bool isPossible(VPRecipeBase *R) { return isa<RecipeTys...>(R); }

  /// Used by cast.
  static VPMixin *doCast(VPRecipeBase *R) {
    VPMixin *Out = nullptr;
    ((Out = dyn_cast<RecipeTys>(R)) || ...);
    assert(Out && "Illegal recipe for cast");
    return Out;
  }
  static VPMixin *castFailed() { return nullptr; }
};
} // namespace vpdetail

/// Support casting from VPRecipeBase -> VPPhiAccessors.
template <>
struct CastInfo<VPPhiAccessors, VPRecipeBase *>
    : vpdetail::CastInfoMixinImpl<VPPhiAccessors, VPPhi, VPIRPhi,
                                  VPWidenPHIRecipe, VPHeaderPHIRecipe> {};

template <>
struct CastInfo<VPPhiAccessors, const VPRecipeBase *>
    : public ConstStrippingForwardingCast<
          VPPhiAccessors, const VPRecipeBase *,
          CastInfo<VPPhiAccessors, VPRecipeBase *>> {};
template <>
struct CastInfo<VPPhiAccessors, VPRecipeBase>
    : public ForwardToPointerCast<VPPhiAccessors, VPRecipeBase *,
                                  CastInfo<VPPhiAccessors, VPRecipeBase *>> {};

/// Support casting from VPRecipeBase / VPUser -> VPWidenMemoryRecipe.
template <>
struct CastInfo<VPWidenMemoryRecipe, VPRecipeBase *>
    : vpdetail::CastInfoMixinImpl<VPWidenMemoryRecipe, VPWidenLoadRecipe,
                                  VPWidenLoadEVLRecipe, VPWidenStoreRecipe,
                                  VPWidenStoreEVLRecipe> {};
template <>
struct CastInfo<VPWidenMemoryRecipe, const VPRecipeBase *>
    : public ConstStrippingForwardingCast<
          VPWidenMemoryRecipe, const VPRecipeBase *,
          CastInfo<VPWidenMemoryRecipe, VPRecipeBase *>> {};

/// Support casting from VPSingleDefRecipe -> VPWidenMemoryRecipe (loads only).
template <>
struct CastInfo<VPWidenMemoryRecipe, VPSingleDefRecipe *>
    : vpdetail::CastInfoMixinImpl<VPWidenMemoryRecipe, VPWidenLoadRecipe,
                                  VPWidenLoadEVLRecipe> {};
template <>
struct CastInfo<VPWidenMemoryRecipe, const VPSingleDefRecipe *>
    : public ConstStrippingForwardingCast<
          VPWidenMemoryRecipe, const VPSingleDefRecipe *,
          CastInfo<VPWidenMemoryRecipe, VPSingleDefRecipe *>> {};

/// Support casting from VPRecipeBase -> VPIRMetadata.
template <>
struct CastInfo<VPIRMetadata, VPRecipeBase *>
    : vpdetail::CastInfoMixinImpl<VPIRMetadata, VPInstruction, VPWidenRecipe,
                                  VPWidenCastRecipe, VPWidenIntrinsicRecipe,
                                  VPWidenCallRecipe, VPReplicateRecipe,
                                  VPInterleaveBase, VPWidenMemoryRecipe,
                                  VPHistogramRecipe, VPBranchOnMaskRecipe> {};

template <>
struct CastInfo<VPIRMetadata, const VPRecipeBase *>
    : public ConstStrippingForwardingCast<
          VPIRMetadata, const VPRecipeBase *,
          CastInfo<VPIRMetadata, VPRecipeBase *>> {};
template <>
struct CastInfo<VPIRMetadata, VPRecipeBase>
    : public ForwardToPointerCast<VPIRMetadata, VPRecipeBase *,
                                  CastInfo<VPIRMetadata, VPRecipeBase *>> {};

/// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
/// holds a sequence of zero or more VPRecipe's each representing a sequence of
/// output IR instructions. All PHI-like recipes must come before any non-PHI
/// recipes.
class LLVM_ABI_FOR_TEST VPBasicBlock : public VPBlockBase {
  friend class VPlan;

  /// Use VPlan::createVPBasicBlock to create VPBasicBlocks.
  VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
      : VPBlockBase(VPBasicBlockSC, Name.str()) {
    if (Recipe)
      appendRecipe(Recipe);
  }

public:
  using RecipeListTy = iplist<VPRecipeBase>;

protected:
  /// The VPRecipes held in the order of output instructions to generate.
  RecipeListTy Recipes;

  VPBasicBlock(VPBlockTy BlockSC, const Twine &Name = "")
      : VPBlockBase(BlockSC, Name.str()) {}

public:
  ~VPBasicBlock() override {
    while (!Recipes.empty())
      Recipes.pop_back();
  }

  /// Instruction iterators...
  using iterator = RecipeListTy::iterator;
  using const_iterator = RecipeListTy::const_iterator;
  using reverse_iterator = RecipeListTy::reverse_iterator;
  using const_reverse_iterator = RecipeListTy::const_reverse_iterator;

  //===--------------------------------------------------------------------===//
  /// Recipe iterator methods
  ///
  inline iterator begin() { return Recipes.begin(); }
  inline const_iterator begin() const { return Recipes.begin(); }
  inline iterator end() { return Recipes.end(); }
  inline const_iterator end() const { return Recipes.end(); }

  inline reverse_iterator rbegin() { return Recipes.rbegin(); }
  inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
  inline reverse_iterator rend() { return Recipes.rend(); }
  inline const_reverse_iterator rend() const { return Recipes.rend(); }

  inline size_t size() const { return Recipes.size(); }
  inline bool empty() const { return Recipes.empty(); }
  inline const VPRecipeBase &front() const { return Recipes.front(); }
  inline VPRecipeBase &front() { return Recipes.front(); }
  inline const VPRecipeBase &back() const { return Recipes.back(); }
  inline VPRecipeBase &back() { return Recipes.back(); }

  /// Returns a reference to the list of recipes.
  RecipeListTy &getRecipeList() { return Recipes; }

  /// Returns a pointer to a member of the recipe list.
  static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {
    return &VPBasicBlock::Recipes;
  }

  /// Method to support type inquiry through isa, cast, and dyn_cast.
  static inline bool classof(const VPBlockBase *V) {
    return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC ||
           V->getVPBlockID() == VPBlockBase::VPIRBasicBlockSC;
  }

  void insert(VPRecipeBase *Recipe, iterator InsertPt) {
    assert(Recipe && "No recipe to append.");
    assert(!Recipe->Parent && "Recipe already in VPlan");
    Recipe->Parent = this;
    Recipes.insert(InsertPt, Recipe);
  }

  /// Augment the existing recipes of a VPBasicBlock with an additional
  /// \p Recipe as the last recipe.
  void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }

  /// The method which generates the output IR instructions that correspond to
  /// this VPBasicBlock, thereby "executing" the VPlan.
  void execute(VPTransformState *State) override;

  /// Return the cost of this VPBasicBlock.
  InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override;

  /// Return the position of the first non-phi node recipe in the block.
  iterator getFirstNonPhi();

  /// Returns an iterator range over the PHI-like recipes in the block.
  iterator_range<iterator> phis() {
    return make_range(begin(), getFirstNonPhi());
  }

  /// Split current block at \p SplitAt by inserting a new block between the
  /// current block and its successors and moving all recipes starting at
  /// SplitAt to the new block. Returns the new block.
  VPBasicBlock *splitAt(iterator SplitAt);

  VPRegionBlock *getEnclosingLoopRegion();
  const VPRegionBlock *getEnclosingLoopRegion() const;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
  /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
  ///
  /// Note that the numbering is applied to the whole VPlan, so printing
  /// individual blocks is consistent with the whole VPlan printing.
  void print(raw_ostream &O, const Twine &Indent,
             VPSlotTracker &SlotTracker) const override;
  using VPBlockBase::print; // Get the print(raw_stream &O) version.
#endif

  /// If the block has multiple successors, return the branch recipe terminating
  /// the block. If there are no or only a single successor, return nullptr;
  VPRecipeBase *getTerminator();
  const VPRecipeBase *getTerminator() const;

  /// Returns true if the block is exiting it's parent region.
  bool isExiting() const;

  /// Clone the current block and it's recipes, without updating the operands of
  /// the cloned recipes.
  VPBasicBlock *clone() override;

  /// Returns the predecessor block at index \p Idx with the predecessors as per
  /// the corresponding plain CFG. If the block is an entry block to a region,
  /// the first predecessor is the single predecessor of a region, and the
  /// second predecessor is the exiting block of the region.
  const VPBasicBlock *getCFGPredecessor(unsigned Idx) const;

protected:
  /// Execute the recipes in the IR basic block \p BB.
  void executeRecipes(VPTransformState *State, BasicBlock *BB);

  /// Connect the VPBBs predecessors' in the VPlan CFG to the IR basic block
  /// generated for this VPBB.
  void connectToPredecessors(VPTransformState &State);

private:
  /// Create an IR BasicBlock to hold the output instructions generated by this
  /// VPBasicBlock, and return it. Update the CFGState accordingly.
  BasicBlock *createEmptyBasicBlock(VPTransformState &State);
};

inline const VPBasicBlock *
VPPhiAccessors::getIncomingBlock(unsigned Idx) const {
  return getAsRecipe()->getParent()->getCFGPredecessor(Idx);
}

/// A special type of VPBasicBlock that wraps an existing IR basic block.
/// Recipes of the block get added before the first non-phi instruction in the
/// wrapped block.
/// Note: At the moment, VPIRBasicBlock can only be used to wrap VPlan's
/// preheader block.
class VPIRBasicBlock : public VPBasicBlock {
  friend class VPlan;

  BasicBlock *IRBB;

  /// Use VPlan::createVPIRBasicBlock to create VPIRBasicBlocks.
  VPIRBasicBlock(BasicBlock *IRBB)
      : VPBasicBlock(VPIRBasicBlockSC,
                     (Twine("ir-bb<") + IRBB->getName() + Twine(">")).str()),
        IRBB(IRBB) {}

public:
  ~VPIRBasicBlock() override = default;

  static inline bool classof(const VPBlockBase *V) {
    return V->getVPBlockID() == VPBlockBase::VPIRBasicBlockSC;
  }

  /// The method which generates the output IR instructions that correspond to
  /// this VPBasicBlock, thereby "executing" the VPlan.
  void execute(VPTransformState *State) override;

  VPIRBasicBlock *clone() override;

  BasicBlock *getIRBasicBlock() const { return IRBB; }
};

/// Track information about the canonical IV and header mask of a loop region.
/// TODO: Have it also track the canonical IV increment, subject of NUW flag.
class VPCanonicalIVInfo {
  /// VPRegionValue for the canonical IV, whose allocation is managed by
  /// VPCanonicalIVInfo.
  std::unique_ptr<VPRegionValue> CanIV;

  /// Optional VPRegionValue for the header mask, set when tail folding.
  std::unique_ptr<VPRegionValue> HeaderMask;

  /// Whether the increment of the canonical IV may unsigned wrap or not.
  bool HasNUW = true;

public:
  VPCanonicalIVInfo(Type *Ty, DebugLoc DL, VPRegionBlock *Region)
      : CanIV(std::make_unique<VPRegionValue>(Ty, DL, Region)) {}

  VPRegionValue *getRegionValue() { return CanIV.get(); }
  const VPRegionValue *getRegionValue() const { return CanIV.get(); }

  VPRegionValue *getHeaderMask() const { return HeaderMask.get(); }

  /// Create the header mask for the region and return it. Must only be called
  /// when no header mask exists yet.
  VPRegionValue *createHeaderMask() {
    assert(!HeaderMask && "Header mask already created");
    HeaderMask = std::make_unique<VPRegionValue>(
        Type::getInt1Ty(CanIV->getType()->getContext()), DebugLoc::getUnknown(),
        CanIV->getDefiningRegion());
    return HeaderMask.get();
  }

  bool hasNUW() const { return HasNUW; }

  void clearNUW() { HasNUW = false; }
};

/// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
/// which form a Single-Entry-Single-Exiting subgraph of the output IR CFG.
/// A VPRegionBlock may indicate that its contents are to be replicated several
/// times. This is designed to support predicated scalarization, in which a
/// scalar if-then code structure needs to be generated VF * UF times. Having
/// this replication indicator helps to keep a single model for multiple
/// candidate VF's. The actual replication takes place only once the desired VF
/// and UF have been determined.
class LLVM_ABI_FOR_TEST VPRegionBlock : public VPBlockBase {
  friend class VPlan;

  /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
  VPBlockBase *Entry;

  /// Hold the Single Exiting block of the SESE region modelled by the
  /// VPRegionBlock.
  VPBlockBase *Exiting;

  /// Holds the Canonical IV of the loop region along with additional
  /// information. If CanIVInfo is nullptr, the region is a replicating region.
  /// Loop regions retain their canonical IVs until they are dissolved, even if
  /// the canonical IV has no users.
  std::unique_ptr<VPCanonicalIVInfo> CanIVInfo;

  /// Use VPlan::createLoopRegion() and VPlan::createReplicateRegion() to create
  /// VPRegionBlocks.
  VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting,
                const std::string &Name = "")
      : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exiting(Exiting) {
    if (Entry) {
      assert(!Entry->hasPredecessors() && "Entry block has predecessors.");
      assert(Exiting && "Must also pass Exiting if Entry is passed.");
      assert(!Exiting->hasSuccessors() && "Exit block has successors.");
      Entry->setParent(this);
      Exiting->setParent(this);
    }
  }

  VPRegionBlock(Type *CanIVTy, DebugLoc DL, VPBlockBase *Entry,
                VPBlockBase *Exiting, const std::string &Name = "")
      : VPRegionBlock(Entry, Exiting, Name) {
    CanIVInfo = std::make_unique<VPCanonicalIVInfo>(CanIVTy, DL, this);
  }

public:
  ~VPRegionBlock() override = default;

  /// Method to support type inquiry through isa, cast, and dyn_cast.
  static inline bool classof(const VPBlockBase *V) {
    return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
  }

  const VPBlockBase *getEntry() const { return Entry; }
  VPBlockBase *getEntry() { return Entry; }

  /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
  /// EntryBlock must have no predecessors.
  void setEntry(VPBlockBase *EntryBlock) {
    assert(!EntryBlock->hasPredecessors() &&
           "Entry block cannot have predecessors.");
    Entry = EntryBlock;
    EntryBlock->setParent(this);
  }

  const VPBlockBase *getExiting() const { return Exiting; }
  VPBlockBase *getExiting() { return Exiting; }

  /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p
  /// ExitingBlock must have no successors.
  void setExiting(VPBlockBase *ExitingBlock) {
    assert(!ExitingBlock->hasSuccessors() &&
           "Exit block cannot have successors.");
    Exiting = ExitingBlock;
    ExitingBlock->setParent(this);
  }

  /// Returns the pre-header VPBasicBlock of the loop region.
  VPBasicBlock *getPreheaderVPBB() {
    assert(!isReplicator() && "should only get pre-header of loop regions");
    return getSinglePredecessor()->getExitingBasicBlock();
  }

  /// An indicator whether this region is to generate multiple replicated
  /// instances of output IR corresponding to its VPBlockBases.
  bool isReplicator() const { return !CanIVInfo; }

  /// Return the VPBranchOnMaskRecipe from the entry block of this replicating
  /// region.
  const VPBranchOnMaskRecipe *getEntryBranchOnMask() const;
  VPBranchOnMaskRecipe *getEntryBranchOnMask() {
    return const_cast<VPBranchOnMaskRecipe *>(
        static_cast<const VPRegionBlock *>(this)->getEntryBranchOnMask());
  }

  /// The method which generates the output IR instructions that correspond to
  /// this VPRegionBlock, thereby "executing" the VPlan.
  void execute(VPTransformState *State) override;

  // Return the cost of this region.
  InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with
  /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using
  /// consequtive numbers.
  ///
  /// Note that the numbering is applied to the whole VPlan, so printing
  /// individual regions is consistent with the whole VPlan printing.
  void print(raw_ostream &O, const Twine &Indent,
             VPSlotTracker &SlotTracker) const override;
  using VPBlockBase::print; // Get the print(raw_stream &O) version.
#endif

  /// Clone all blocks in the single-entry single-exit region of the block and
  /// their recipes without updating the operands of the cloned recipes.
  VPRegionBlock *clone() override;

  /// Remove the current region from its VPlan, connecting its predecessor to
  /// its entry, and its exiting block to its successor.
  void dissolveToCFGLoop();

  /// Get the canonical IV increment instruction if it exists. Otherwise, create
  /// a new increment before the terminator and return it. The canonical IV
  /// increment is subject to DCE if unused, unlike the canonical IV itself.
  VPInstruction *getOrCreateCanonicalIVIncrement();

  /// Return the canonical induction variable of the region, null for
  /// replicating regions.
  VPRegionValue *getCanonicalIV() {
    return CanIVInfo ? CanIVInfo->getRegionValue() : nullptr;
  }
  const VPRegionValue *getCanonicalIV() const {
    return CanIVInfo ? CanIVInfo->getRegionValue() : nullptr;
  }

  /// Return the type of the canonical IV for loop regions.
  Type *getCanonicalIVType() const {
    return CanIVInfo->getRegionValue()->getType();
  }

  /// Return the header mask of the region, or null if not set.
  VPRegionValue *getHeaderMask() const {
    return CanIVInfo ? CanIVInfo->getHeaderMask() : nullptr;
  }

  /// Return the header mask if it exists and is used, or null otherwise. The
  /// mask is materialized into concrete recipes only after costing, so cost and
  /// codegen accounting sites use this to skip an unused mask.
  VPRegionValue *getUsedHeaderMask() const {
    VPRegionValue *HeaderMask = getHeaderMask();
    return HeaderMask && HeaderMask->getNumUsers() > 0 ? HeaderMask : nullptr;
  }

  /// Create the header mask for the region and return it. Must only be called
  /// on loop regions that don't already have a header mask.
  VPRegionValue *createHeaderMask() {
    assert(CanIVInfo && "Can only create header mask for loop regions");
    return CanIVInfo->createHeaderMask();
  }

  /// Return the region values of the loop region (canonical IV, header mask)
  /// or an empty vector for replicate regions.
  SmallVector<VPRegionValue *, 2> getRegionValues() const {
    if (!CanIVInfo)
      return {};
    SmallVector<VPRegionValue *, 2> R = {CanIVInfo->getRegionValue()};
    if (auto *HM = CanIVInfo->getHeaderMask())
      R.push_back(HM);
    return R;
  }

  /// Indicates if NUW is set for the canonical IV increment, for loop regions.
  bool hasCanonicalIVNUW() const { return CanIVInfo->hasNUW(); }

  /// Unsets NUW for the canonical IV increment \p Increment, for loop regions.
  void clearCanonicalIVNUW(VPInstruction *Increment) {
    assert(Increment && "Must provide increment to clear");
    Increment->dropPoisonGeneratingFlags();
    CanIVInfo->clearNUW();
  }
};

inline VPRegionBlock *VPRecipeBase::getRegion() {
  return getParent()->getParent();
}

inline const VPRegionBlock *VPRecipeBase::getRegion() const {
  return getParent()->getParent();
}

/// VPlan models a candidate for vectorization, encoding various decisions take
/// to produce efficient output IR, including which branches, basic-blocks and
/// output IR instructions to generate, and their cost. VPlan holds a
/// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
/// VPBasicBlock.
class VPlan {
  friend class VPlanPrinter;
  friend class VPSlotTracker;

  /// VPBasicBlock corresponding to the original preheader. Used to place
  /// VPExpandSCEV recipes for expressions used during skeleton creation and the
  /// rest of VPlan execution.
  /// When this VPlan is used for the epilogue vector loop, the entry will be
  /// replaced by a new entry block created during skeleton creation.
  VPBasicBlock *Entry;

  /// VPIRBasicBlock wrapping the header of the original scalar loop.
  VPIRBasicBlock *ScalarHeader;

  /// Immutable list of VPIRBasicBlocks wrapping the exit blocks of the original
  /// scalar loop. Note that some exit blocks may be unreachable at the moment,
  /// e.g. if the scalar epilogue always executes.
  SmallVector<VPIRBasicBlock *, 2> ExitBlocks;

  /// Holds the VFs applicable to this VPlan.
  SmallSetVector<ElementCount, 2> VFs;

  /// Holds the UFs applicable to this VPlan. If empty, the VPlan is valid for
  /// any UF.
  SmallSetVector<unsigned, 2> UFs;

  /// Holds the name of the VPlan, for printing.
  std::string Name;

  /// Represents the trip count of the original loop, for folding
  /// the tail.
  VPValue *TripCount = nullptr;

  /// Represents the backedge taken count of the original loop, for folding
  /// the tail. It equals TripCount - 1.
  VPSymbolicValue *BackedgeTakenCount = nullptr;

  /// Represents the vector trip count.
  VPSymbolicValue VectorTripCount;

  /// Represents the vectorization factor of the loop.
  VPSymbolicValue VF;

  /// Represents the unroll factor of the loop.
  VPSymbolicValue UF;

  /// Represents the loop-invariant VF * UF of the vector loop region.
  VPSymbolicValue VFxUF;

  /// Contains all the external definitions created for this VPlan, as a mapping
  /// from IR Values to VPIRValues.
  SmallMapVector<Value *, VPIRValue *, 16> LiveIns;

  /// Blocks allocated and owned by the VPlan. They will be deleted once the
  /// VPlan is destroyed.
  SmallVector<VPBlockBase *> CreatedBlocks;

  /// Construct a VPlan with \p Entry to the plan and with \p ScalarHeader
  /// wrapping the original header of the scalar loop. The vector loop will have
  /// index type \p IdxTy.
  VPlan(VPBasicBlock *Entry, VPIRBasicBlock *ScalarHeader, Type *IdxTy)
      : Entry(Entry), ScalarHeader(ScalarHeader), VectorTripCount(IdxTy),
        VF(IdxTy), UF(IdxTy), VFxUF(IdxTy) {
    Entry->setPlan(this);
    assert(ScalarHeader->getNumSuccessors() == 0 &&
           "scalar header must be a leaf node");
  }

public:
  /// Construct a VPlan for \p L. This will create VPIRBasicBlocks wrapping the
  /// original preheader and scalar header of \p L, to be used as entry and
  /// scalar header blocks of the new VPlan. The vector loop will have index
  /// type \p IdxTy.
  VPlan(Loop *L, Type *IdxTy);

  /// Construct a VPlan with a new VPBasicBlock as entry, a VPIRBasicBlock
  /// wrapping \p ScalarHeaderBB and vector loop index of type \p IdxTy.
  VPlan(BasicBlock *ScalarHeaderBB, Type *IdxTy)
      : VectorTripCount(IdxTy), VF(IdxTy), UF(IdxTy), VFxUF(IdxTy) {
    setEntry(createVPBasicBlock("preheader"));
    ScalarHeader = createVPIRBasicBlock(ScalarHeaderBB);
  }

  LLVM_ABI_FOR_TEST ~VPlan();

  void setEntry(VPBasicBlock *VPBB) {
    Entry = VPBB;
    VPBB->setPlan(this);
  }

  /// Generate the IR code for this VPlan.
  void execute(VPTransformState *State);

  /// Return the cost of this plan.
  InstructionCost cost(ElementCount VF, VPCostContext &Ctx);

  VPBasicBlock *getEntry() { return Entry; }
  const VPBasicBlock *getEntry() const { return Entry; }

  /// Returns the preheader of the vector loop region, if one exists, or null
  /// otherwise.
  VPBasicBlock *getVectorPreheader() const {
    const VPRegionBlock *VectorRegion = getVectorLoopRegion();
    return VectorRegion
               ? cast<VPBasicBlock>(VectorRegion->getSinglePredecessor())
               : nullptr;
  }

  /// Returns the VPRegionBlock of the vector loop.
  LLVM_ABI_FOR_TEST VPRegionBlock *getVectorLoopRegion();
  LLVM_ABI_FOR_TEST const VPRegionBlock *getVectorLoopRegion() const;

  /// Returns true if this VPlan is for an outer loop, i.e., its vector
  /// loop region contains a nested loop region.
  LLVM_ABI_FOR_TEST bool isOuterLoop() const;

  /// Returns true if the vector loop region is tail-folded.
  bool hasTailFolded() const {
    const VPRegionBlock *LoopRegion = getVectorLoopRegion();
    return LoopRegion && LoopRegion->getHeaderMask();
  }

  /// Returns true if the plan requires a scalar epilogue after the vector
  /// loop. Must be called before removeBranchOnConst.
  bool requiresScalarEpilogue() const {
    const VPBasicBlock *MiddleVPBB = getMiddleBlock();
    return MiddleVPBB->getSingleSuccessor() == getScalarPreheader();
  }

  /// Returns the 'middle' block of the plan, that is the block that selects
  /// whether to execute the scalar tail loop or the exit block from the loop
  /// latch. If there is an early exit from the vector loop, the middle block
  /// conceptully has the early exit block as third successor, split accross 2
  /// VPBBs. In that case, the second VPBB selects whether to execute the scalar
  /// tail loop or the exit block. If the scalar tail loop or exit block are
  /// known to always execute, the middle block may branch directly to that
  /// block. This function cannot be called once the vector loop region has been
  /// removed.
  VPBasicBlock *getMiddleBlock() {
    VPRegionBlock *LoopRegion = getVectorLoopRegion();
    assert(
        LoopRegion &&
        "cannot call the function after vector loop region has been removed");
    // The middle block is always the last successor of the region.
    return cast<VPBasicBlock>(LoopRegion->getSuccessors().back());
  }

  const VPBasicBlock *getMiddleBlock() const {
    return const_cast<VPlan *>(this)->getMiddleBlock();
  }

  /// Return the VPBasicBlock for the preheader of the scalar loop.
  VPBasicBlock *getScalarPreheader() const {
    return dyn_cast_or_null<VPBasicBlock>(
        getScalarHeader()->getSinglePredecessor());
  }

  /// Return the VPIRBasicBlock wrapping the header of the scalar loop.
  VPIRBasicBlock *getScalarHeader() const { return ScalarHeader; }

  /// Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of
  /// the original scalar loop.
  ArrayRef<VPIRBasicBlock *> getExitBlocks() const { return ExitBlocks; }

  /// Returns true if \p VPBB is an exit block.
  bool isExitBlock(VPBlockBase *VPBB);

  /// The trip count of the original loop.
  VPValue *getTripCount() const {
    assert(TripCount && "trip count needs to be set before accessing it");
    return TripCount;
  }

  /// Set the trip count assuming it is currently null; if it is not - use
  /// resetTripCount().
  void setTripCount(VPValue *NewTripCount) {
    assert(!TripCount && NewTripCount && "TripCount should not be set yet.");
    TripCount = NewTripCount;
  }

  /// Resets the trip count for the VPlan. The caller must make sure all uses of
  /// the original trip count have been replaced.
  void resetTripCount(VPValue *NewTripCount) {
    assert(TripCount && NewTripCount && TripCount->user_empty() &&
           "TripCount must be set when resetting");
    TripCount = NewTripCount;
  }

  /// The backedge taken count of the original loop.
  VPValue *getOrCreateBackedgeTakenCount() {
    // BTC shares the canonical IV type with VectorTripCount.
    if (!BackedgeTakenCount)
      BackedgeTakenCount = new VPSymbolicValue(VectorTripCount.getType());
    return BackedgeTakenCount;
  }
  VPValue *getBackedgeTakenCount() const { return BackedgeTakenCount; }

  /// The vector trip count.
  VPSymbolicValue &getVectorTripCount() { return VectorTripCount; }

  /// Returns the VF of the vector loop region.
  VPSymbolicValue &getVF() { return VF; };
  const VPSymbolicValue &getVF() const { return VF; };

  /// Returns the UF of the vector loop region.
  VPSymbolicValue &getUF() { return UF; };

  /// Returns VF * UF of the vector loop region.
  VPSymbolicValue &getVFxUF() { return VFxUF; }

  LLVMContext &getContext() const {
    return getScalarHeader()->getIRBasicBlock()->getContext();
  }

  const DataLayout &getDataLayout() const {
    return getScalarHeader()->getIRBasicBlock()->getDataLayout();
  }

  Function *getIRFunction() const {
    return getScalarHeader()->getIRBasicBlock()->getParent();
  }

  void addVF(ElementCount VF) { VFs.insert(VF); }

  void setVF(ElementCount VF) {
    assert(hasVF(VF) && "Cannot set VF not already in plan");
    VFs.clear();
    VFs.insert(VF);
  }

  /// Remove \p VF from the plan.
  void removeVF(ElementCount VF) {
    assert(hasVF(VF) && "tried to remove VF not present in plan");
    VFs.remove(VF);
  }

  bool hasVF(ElementCount VF) const { return VFs.count(VF); }
  bool hasScalableVF() const {
    return any_of(VFs, [](ElementCount VF) { return VF.isScalable(); });
  }

  /// Returns an iterator range over all VFs of the plan.
  iterator_range<SmallSetVector<ElementCount, 2>::iterator>
  vectorFactors() const {
    return VFs;
  }

  /// Returns the single VF of the plan, asserting that the plan has exactly
  /// one VF.
  ElementCount getSingleVF() const {
    assert(VFs.size() == 1 && "expected plan with single VF");
    return VFs[0];
  }

  bool hasScalarVFOnly() const {
    bool HasScalarVFOnly = VFs.size() == 1 && VFs[0].isScalar();
    assert(HasScalarVFOnly == hasVF(ElementCount::getFixed(1)) &&
           "Plan with scalar VF should only have a single VF");
    return HasScalarVFOnly;
  }

  bool hasUF(unsigned UF) const { return UFs.empty() || UFs.contains(UF); }

  /// Returns the concrete UF of the plan, after unrolling.
  unsigned getConcreteUF() const {
    assert(UFs.size() == 1 && "Expected a single UF");
    return UFs[0];
  }

  void setUF(unsigned UF) {
    assert(hasUF(UF) && "Cannot set the UF not already in plan");
    UFs.clear();
    UFs.insert(UF);
  }

  /// Returns true if the VPlan already has been unrolled, i.e. it has a single
  /// concrete UF.
  bool isUnrolled() const { return UFs.size() == 1; }

  /// Return a string with the name of the plan and the applicable VFs and UFs.
  std::string getName() const;

  void setName(const Twine &newName) { Name = newName.str(); }

  /// Gets the live-in VPIRValue for \p V or adds a new live-in (if none exists
  ///  yet) for \p V.
  VPIRValue *getOrAddLiveIn(Value *V) {
    assert(V && "Trying to get or add the VPIRValue of a null Value");
    auto [It, Inserted] = LiveIns.try_emplace(V);
    if (Inserted) {
      if (auto *CI = dyn_cast<ConstantInt>(V))
        It->second = new VPConstantInt(CI);
      else
        It->second = new VPIRValue(V);
    }

    assert(isa<VPIRValue>(It->second) &&
           "Only VPIRValues should be in mapping");
    return It->second;
  }
  VPIRValue *getOrAddLiveIn(VPIRValue *V) {
    assert(V && "Trying to get or add the VPIRValue of a null VPIRValue");
    return getOrAddLiveIn(V->getValue());
  }

  /// Return a VPIRValue wrapping i1 true.
  VPIRValue *getTrue() { return getConstantInt(1, 1); }

  /// Return a VPIRValue wrapping i1 false.
  VPIRValue *getFalse() { return getConstantInt(1, 0); }

  /// Return a VPIRValue wrapping the null value of type \p Ty.
  VPIRValue *getZero(Type *Ty) { return getConstantInt(Ty, 0); }

  /// Return a VPIRValue wrapping the AllOnes value of type \p Ty.
  VPIRValue *getAllOnesValue(Type *Ty) {
    return getConstantInt(APInt::getAllOnes(Ty->getIntegerBitWidth()));
  }

  /// Return a VPIRValue wrapping a ConstantInt with the given type and value.
  VPIRValue *getConstantInt(Type *Ty, uint64_t Val, bool IsSigned = false) {
    return getOrAddLiveIn(ConstantInt::get(Ty, Val, IsSigned));
  }

  /// Return a VPIRValue wrapping a ConstantInt with the given bitwidth and
  /// value.
  VPIRValue *getConstantInt(unsigned BitWidth, uint64_t Val,
                            bool IsSigned = false) {
    return getConstantInt(APInt(BitWidth, Val, IsSigned));
  }

  /// Return a VPIRValue wrapping a ConstantInt with the given APInt value.
  VPIRValue *getConstantInt(const APInt &Val) {
    return getOrAddLiveIn(ConstantInt::get(getContext(), Val));
  }

  /// Return a VPIRValue wrapping a poison value of type \p Ty.
  VPIRValue *getPoison(Type *Ty) {
    return getOrAddLiveIn(PoisonValue::get(Ty));
  }

  /// Return the live-in VPIRValue for \p V, if there is one or nullptr
  /// otherwise.
  VPIRValue *getLiveIn(Value *V) const { return LiveIns.lookup(V); }

  /// Return the list of live-in VPValues available in the VPlan.
  auto getLiveIns() const { return LiveIns.values(); }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the live-ins of this VPlan to \p O.
  void printLiveIns(raw_ostream &O) const;

  /// Print this VPlan to \p O.
  LLVM_ABI_FOR_TEST void print(raw_ostream &O) const;

  /// Print this VPlan in DOT format to \p O.
  LLVM_ABI_FOR_TEST void printDOT(raw_ostream &O) const;

  /// Dump the plan to stderr (for debugging).
  LLVM_DUMP_METHOD void dump() const;
#endif

  /// Clone the current VPlan, update all VPValues of the new VPlan and cloned
  /// recipes to refer to the clones, and return it.
  LLVM_ABI_FOR_TEST VPlan *duplicate();

  /// Create a new VPBasicBlock with \p Name and containing \p Recipe if
  /// present. The returned block is owned by the VPlan and deleted once the
  /// VPlan is destroyed.
  VPBasicBlock *createVPBasicBlock(const Twine &Name,
                                   VPRecipeBase *Recipe = nullptr) {
    auto *VPB = new VPBasicBlock(Name, Recipe);
    VPB->setPlan(this);
    VPB->setNumber(CreatedBlocks.size());
    CreatedBlocks.push_back(VPB);
    return VPB;
  }

  /// Create a new loop region with a canonical IV using \p CanIVTy and
  /// \p DL. Use \p Name as the region's name and set entry and exiting blocks
  /// to \p Entry and \p Exiting respectively, if provided. The returned block
  /// is owned by the VPlan and deleted once the VPlan is destroyed.
  VPRegionBlock *createLoopRegion(Type *CanIVTy, DebugLoc DL,
                                  const std::string &Name = "",
                                  VPBlockBase *Entry = nullptr,
                                  VPBlockBase *Exiting = nullptr) {
    auto *VPB = new VPRegionBlock(CanIVTy, DL, Entry, Exiting, Name);
    VPB->setPlan(this);
    VPB->setNumber(CreatedBlocks.size());
    CreatedBlocks.push_back(VPB);
    return VPB;
  }

  /// Create a new replicate region with \p Entry, \p Exiting and \p Name. The
  /// returned block is owned by the VPlan and deleted once the VPlan is
  /// destroyed.
  VPRegionBlock *createReplicateRegion(VPBlockBase *Entry, VPBlockBase *Exiting,
                                       const std::string &Name = "") {
    auto *VPB = new VPRegionBlock(Entry, Exiting, Name);
    VPB->setPlan(this);
    VPB->setNumber(CreatedBlocks.size());
    CreatedBlocks.push_back(VPB);
    return VPB;
  }

  /// Create a VPIRBasicBlock wrapping \p IRBB, but do not create
  /// VPIRInstructions wrapping the instructions in t\p IRBB.  The returned
  /// block is owned by the VPlan and deleted once the VPlan is destroyed.
  VPIRBasicBlock *createEmptyVPIRBasicBlock(BasicBlock *IRBB);

  /// Create a VPIRBasicBlock from \p IRBB containing VPIRInstructions for all
  /// instructions in \p IRBB, except its terminator which is managed by the
  /// successors of the block in VPlan. The returned block is owned by the VPlan
  /// and deleted once the VPlan is destroyed.
  LLVM_ABI_FOR_TEST VPIRBasicBlock *createVPIRBasicBlock(BasicBlock *IRBB);

  unsigned getMaxBlockNumber() const { return CreatedBlocks.size(); }

  /// Returns true if the VPlan is based on a loop with an early exit.
  bool hasEarlyExit() const {
    unsigned NumExitPredecessors =
        sum_of(map_range(ExitBlocks, [](VPIRBasicBlock *EB) {
          return EB->getNumPredecessors();
        }));

    // If the scalar preheader executes unconditionally, there's no branch from
    // middle block to any exit. If there is any edge to an exit block
    // remaining, it must be an early exit.
    VPBasicBlock *ScalarPH = getScalarPreheader();
    VPBlockBase *ScalarPHPred =
        ScalarPH ? ScalarPH->getSinglePredecessor() : nullptr;
    if (ScalarPHPred && ScalarPHPred->getNumSuccessors() == 1)
      return NumExitPredecessors >= 1;

    // Otherwise there must be at least 2 edges to exit blocks (from the middle
    // block and the early exiting edge).
    return NumExitPredecessors > 1;
  }

  /// Returns true if the scalar tail may execute after the vector loop, i.e.
  /// if the middle block is a predecessor of the scalar preheader. Note that
  /// this relies on unneeded branches to the scalar tail loop being removed.
  bool hasScalarTail() const {
    auto *ScalarPH = getScalarPreheader();
    return ScalarPH &&
           is_contained(ScalarPH->getPredecessors(), getMiddleBlock());
  }

  /// The type of the canonical induction variable of the vector loop.
  Type *getIndexType() const { return VF.getType(); }
};

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {
  Plan.print(OS);
  return OS;
}
#endif

} // end namespace llvm

#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H