text: //===- 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. Specializations of GraphTraits that allow VPBlockBase graphs to be
  ///    treated as proper graphs for generic algorithms;
  /// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained
  ///    within VPBasicBlocks;
  /// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
  ///    instruction;
  /// 5. The VPlan class holding a candidate for vectorization;
  /// 6. The VPlanPrinter class providing a way to print a plan in dot format;
  /// These are documented in docs/VectorizationPlan.rst.
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
  #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
  
  #include "VPlanLoopInfo.h"
  #include "VPlanValue.h"
  #include "llvm/ADT/DenseMap.h"
  #include "llvm/ADT/DepthFirstIterator.h"
  #include "llvm/ADT/GraphTraits.h"
  #include "llvm/ADT/Optional.h"
  #include "llvm/ADT/SmallPtrSet.h"
  #include "llvm/ADT/SmallSet.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/VectorUtils.h"
  #include "llvm/IR/IRBuilder.h"
  #include <algorithm>
  #include <cassert>
  #include <cstddef>
  #include <map>
  #include <string>
  
  namespace llvm {
  
  class LoopVectorizationLegality;
  class LoopVectorizationCostModel;
  class BasicBlock;
  class DominatorTree;
  class InnerLoopVectorizer;
  template <class T> class InterleaveGroup;
  class LoopInfo;
  class raw_ostream;
  class Value;
  class VPBasicBlock;
  class VPRegionBlock;
  class VPlan;
  class VPlanSlp;
  
  /// A range of powers-of-2 vectorization factors with fixed start and
  /// adjustable end. The range includes start and excludes end, e.g.,:
  /// [1, 9) = {1, 2, 4, 8}
  struct VFRange {
    // A power of 2.
    const unsigned Start;
  
    // Need not be a power of 2. If End <= Start range is empty.
    unsigned End;
  };
  
  using VPlanPtr = std::unique_ptr<VPlan>;
  
  /// In what follows, the term "input IR" refers to code that is fed into the
  /// vectorizer whereas the term "output IR" refers to code that is generated by
  /// the vectorizer.
  
  /// VPIteration represents a single point in the iteration space of the output
  /// (vectorized and/or unrolled) IR loop.
  struct VPIteration {
    /// in [0..UF)
    unsigned Part;
  
    /// in [0..VF)
    unsigned Lane;
  };
  
  /// This is a helper struct for maintaining vectorization state. It's used for
  /// mapping values from the original loop to their corresponding values in
  /// the new loop. Two mappings are maintained: one for vectorized values and
  /// one for scalarized values. Vectorized values are represented with UF
  /// vector values in the new loop, and scalarized values are represented with
  /// UF x VF scalar values in the new loop. UF and VF are the unroll and
  /// vectorization factors, respectively.
  ///
  /// Entries can be added to either map with setVectorValue and setScalarValue,
  /// which assert that an entry was not already added before. If an entry is to
  /// replace an existing one, call resetVectorValue and resetScalarValue. This is
  /// currently needed to modify the mapped values during "fix-up" operations that
  /// occur once the first phase of widening is complete. These operations include
  /// type truncation and the second phase of recurrence widening.
  ///
  /// Entries from either map can be retrieved using the getVectorValue and
  /// getScalarValue functions, which assert that the desired value exists.
  struct VectorizerValueMap {
    friend struct VPTransformState;
  
  private:
    /// The unroll factor. Each entry in the vector map contains UF vector values.
    unsigned UF;
  
    /// The vectorization factor. Each entry in the scalar map contains UF x VF
    /// scalar values.
    unsigned VF;
  
    /// The vector and scalar map storage. We use std::map and not DenseMap
    /// because insertions to DenseMap invalidate its iterators.
    using VectorParts = SmallVector<Value *, 2>;
    using ScalarParts = SmallVector<SmallVector<Value *, 4>, 2>;
    std::map<Value *, VectorParts> VectorMapStorage;
    std::map<Value *, ScalarParts> ScalarMapStorage;
  
  public:
    /// Construct an empty map with the given unroll and vectorization factors.
    VectorizerValueMap(unsigned UF, unsigned VF) : UF(UF), VF(VF) {}
  
    /// \return True if the map has any vector entry for \p Key.
    bool hasAnyVectorValue(Value *Key) const {
      return VectorMapStorage.count(Key);
    }
  
    /// \return True if the map has a vector entry for \p Key and \p Part.
    bool hasVectorValue(Value *Key, unsigned Part) const {
      assert(Part < UF && "Queried Vector Part is too large.");
      if (!hasAnyVectorValue(Key))
        return false;
      const VectorParts &Entry = VectorMapStorage.find(Key)->second;
      assert(Entry.size() == UF && "VectorParts has wrong dimensions.");
      return Entry[Part] != nullptr;
    }
  
    /// \return True if the map has any scalar entry for \p Key.
    bool hasAnyScalarValue(Value *Key) const {
      return ScalarMapStorage.count(Key);
    }
  
    /// \return True if the map has a scalar entry for \p Key and \p Instance.
    bool hasScalarValue(Value *Key, const VPIteration &Instance) const {
      assert(Instance.Part < UF && "Queried Scalar Part is too large.");
      assert(Instance.Lane < VF && "Queried Scalar Lane is too large.");
      if (!hasAnyScalarValue(Key))
        return false;
      const ScalarParts &Entry = ScalarMapStorage.find(Key)->second;
      assert(Entry.size() == UF && "ScalarParts has wrong dimensions.");
      assert(Entry[Instance.Part].size() == VF &&
             "ScalarParts has wrong dimensions.");
      return Entry[Instance.Part][Instance.Lane] != nullptr;
    }
  
    /// Retrieve the existing vector value that corresponds to \p Key and
    /// \p Part.
    Value *getVectorValue(Value *Key, unsigned Part) {
      assert(hasVectorValue(Key, Part) && "Getting non-existent value.");
      return VectorMapStorage[Key][Part];
    }
  
    /// Retrieve the existing scalar value that corresponds to \p Key and
    /// \p Instance.
    Value *getScalarValue(Value *Key, const VPIteration &Instance) {
      assert(hasScalarValue(Key, Instance) && "Getting non-existent value.");
      return ScalarMapStorage[Key][Instance.Part][Instance.Lane];
    }
  
    /// Set a vector value associated with \p Key and \p Part. Assumes such a
    /// value is not already set. If it is, use resetVectorValue() instead.
    void setVectorValue(Value *Key, unsigned Part, Value *Vector) {
      assert(!hasVectorValue(Key, Part) && "Vector value already set for part");
      if (!VectorMapStorage.count(Key)) {
        VectorParts Entry(UF);
        VectorMapStorage[Key] = Entry;
      }
      VectorMapStorage[Key][Part] = Vector;
    }
  
    /// Set a scalar value associated with \p Key and \p Instance. Assumes such a
    /// value is not already set.
    void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar) {
      assert(!hasScalarValue(Key, Instance) && "Scalar value already set");
      if (!ScalarMapStorage.count(Key)) {
        ScalarParts Entry(UF);
        // TODO: Consider storing uniform values only per-part, as they occupy
        //       lane 0 only, keeping the other VF-1 redundant entries null.
        for (unsigned Part = 0; Part < UF; ++Part)
          Entry[Part].resize(VF, nullptr);
        ScalarMapStorage[Key] = Entry;
      }
      ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
    }
  
    /// Reset the vector value associated with \p Key for the given \p Part.
    /// This function can be used to update values that have already been
    /// vectorized. This is the case for "fix-up" operations including type
    /// truncation and the second phase of recurrence vectorization.
    void resetVectorValue(Value *Key, unsigned Part, Value *Vector) {
      assert(hasVectorValue(Key, Part) && "Vector value not set for part");
      VectorMapStorage[Key][Part] = Vector;
    }
  
    /// Reset the scalar value associated with \p Key for \p Part and \p Lane.
    /// This function can be used to update values that have already been
    /// scalarized. This is the case for "fix-up" operations including scalar phi
    /// nodes for scalarized and predicated instructions.
    void resetScalarValue(Value *Key, const VPIteration &Instance,
                          Value *Scalar) {
      assert(hasScalarValue(Key, Instance) &&
             "Scalar value not set for part and lane");
      ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
    }
  };
  
  /// This class is used to enable the VPlan to invoke a method of ILV. This is
  /// needed until the method is refactored out of ILV and becomes reusable.
  struct VPCallback {
    virtual ~VPCallback() {}
    virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0;
  };
  
  /// VPTransformState holds information passed down when "executing" a VPlan,
  /// needed for generating the output IR.
  struct VPTransformState {
    VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT,
                     IRBuilder<> &Builder, VectorizerValueMap &ValueMap,
                     InnerLoopVectorizer *ILV, VPCallback &Callback)
        : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder),
          ValueMap(ValueMap), ILV(ILV), Callback(Callback) {}
  
    /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
    unsigned VF;
    unsigned UF;
  
    /// Hold the indices to generate specific scalar instructions. Null indicates
    /// that all instances are to be generated, using either scalar or vector
    /// instructions.
    Optional<VPIteration> Instance;
  
    struct DataState {
      /// A type for vectorized values in the new loop. Each value from the
      /// original loop, when vectorized, is represented by UF vector values in
      /// the new unrolled loop, where UF is the unroll factor.
      typedef SmallVector<Value *, 2> PerPartValuesTy;
  
      DenseMap<VPValue *, PerPartValuesTy> PerPartOutput;
    } Data;
  
    /// Get the generated Value for a given VPValue and a given Part. Note that
    /// as some Defs are still created by ILV and managed in its ValueMap, this
    /// method will delegate the call to ILV in such cases in order to provide
    /// callers a consistent API.
    /// \see set.
    Value *get(VPValue *Def, unsigned Part) {
      // If Values have been set for this Def return the one relevant for \p Part.
      if (Data.PerPartOutput.count(Def))
        return Data.PerPartOutput[Def][Part];
      // Def is managed by ILV: bring the Values from ValueMap.
      return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part);
    }
  
    /// Set the generated Value for a given VPValue and a given Part.
    void set(VPValue *Def, Value *V, unsigned Part) {
      if (!Data.PerPartOutput.count(Def)) {
        DataState::PerPartValuesTy Entry(UF);
        Data.PerPartOutput[Def] = Entry;
      }
      Data.PerPartOutput[Def][Part] = V;
    }
  
    /// Hold state information used when constructing the CFG of the output IR,
    /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
    struct CFGState {
      /// The previous VPBasicBlock visited. Initially set to null.
      VPBasicBlock *PrevVPBB = nullptr;
  
      /// The previous IR BasicBlock created or used. Initially set to the new
      /// header BasicBlock.
      BasicBlock *PrevBB = nullptr;
  
      /// The last IR BasicBlock in the output IR. Set to the new latch
      /// BasicBlock, used for placing the newly created BasicBlocks.
      BasicBlock *LastBB = nullptr;
  
      /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
      /// of replication, maps the BasicBlock of the last replica created.
      SmallDenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB;
  
      /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed
      /// up at the end of vector code generation.
      SmallVector<VPBasicBlock *, 8> VPBBsToFix;
  
      CFGState() = default;
    } CFG;
  
    /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
    LoopInfo *LI;
  
    /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
    DominatorTree *DT;
  
    /// Hold a reference to the IRBuilder used to generate output IR code.
    IRBuilder<> &Builder;
  
    /// Hold a reference to the Value state information used when generating the
    /// Values of the output IR.
    VectorizerValueMap &ValueMap;
  
    /// Hold a reference to a mapping between VPValues in VPlan and original
    /// Values they correspond to.
    VPValue2ValueTy VPValue2Value;
  
    /// Hold the trip count of the scalar loop.
    Value *TripCount = nullptr;
  
    /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
    InnerLoopVectorizer *ILV;
  
    VPCallback &Callback;
  };
  
  /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
  /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
  class VPBlockBase {
    friend class VPBlockUtils;
  
  private:
    const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
  
    /// 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;
  
    /// Successor selector, null for zero or single successor blocks.
    VPValue *CondBit = nullptr;
  
    /// Current block predicate - null if the block does not need a predicate.
    VPValue *Predicate = nullptr;
  
    /// 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 = std::find(Predecessors.begin(), Predecessors.end(), 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 = std::find(Successors.begin(), Successors.end(), Successor);
      assert(Pos && "Successor does not exist");
      Successors.erase(Pos);
    }
  
  protected:
    VPBlockBase(const unsigned char SC, const std::string &N)
        : SubclassID(SC), Name(N) {}
  
  public:
    /// 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 { VPBasicBlockSC, VPRegionBlockSC };
  
    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; }
  
    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 exit of this VPBlockBase,
    /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
    /// VPBlockBase is a VPBasicBlock, it is returned.
    const VPBasicBlock *getExitBasicBlock() const;
    VPBasicBlock *getExitBasicBlock();
  
    const VPBlocksTy &getSuccessors() const { return Successors; }
    VPBlocksTy &getSuccessors() { return Successors; }
  
    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 successor of this VPBlockBase if it has a single
    /// hierarchical successor. Otherwise return a null pointer.
    VPBlockBase *getSingleHierarchicalSuccessor() {
      return getEnclosingBlockWithSuccessors()->getSingleSuccessor();
    }
  
    /// \return the predecessors either attached directly to this VPBlockBase or,
    /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
    /// predecessors of its own, search recursively for the first enclosing
    /// VPRegionBlock that has predecessors and return them. If no such
    /// VPRegionBlock exists, return the (empty) predecessors of the topmost
    /// VPBlockBase reached.
    const VPBlocksTy &getHierarchicalPredecessors() {
      return getEnclosingBlockWithPredecessors()->getPredecessors();
    }
  
    /// \return the hierarchical predecessor of this VPBlockBase if it has a
    /// single hierarchical predecessor. Otherwise return a null pointer.
    VPBlockBase *getSingleHierarchicalPredecessor() {
      return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
    }
  
    /// \return the condition bit selecting the successor.
    VPValue *getCondBit() { return CondBit; }
  
    const VPValue *getCondBit() const { return CondBit; }
  
    void setCondBit(VPValue *CV) { CondBit = CV; }
  
    VPValue *getPredicate() { return Predicate; }
  
    const VPValue *getPredicate() const { return Predicate; }
  
    void setPredicate(VPValue *Pred) { Predicate = Pred; }
  
    /// 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.");
      appendSuccessor(Successor);
    }
  
    /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
    /// successors of this VPBlockBase. \p Condition is set as the successor
    /// selector. 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,
                          VPValue *Condition) {
      assert(Successors.empty() && "Setting two successors when others exist.");
      assert(Condition && "Setting two successors without condition!");
      CondBit = Condition;
      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);
    }
  
    /// Remove all the predecessor of this block.
    void clearPredecessors() { Predecessors.clear(); }
  
    /// Remove all the successors of this block and set to null its condition bit
    void clearSuccessors() {
      Successors.clear();
      CondBit = nullptr;
    }
  
    /// The method which generates the output IR that correspond to this
    /// VPBlockBase, thereby "executing" the VPlan.
    virtual void execute(struct VPTransformState *State) = 0;
  
    /// Delete all blocks reachable from a given VPBlockBase, inclusive.
    static void deleteCFG(VPBlockBase *Entry);
  
    void printAsOperand(raw_ostream &OS, bool PrintType) const {
      OS << getName();
    }
  
    void print(raw_ostream &OS) const {
      // TODO: Only printing VPBB name for now since we only have dot printing
      // support for VPInstructions/Recipes.
      printAsOperand(OS, false);
    }
  
    /// Return true if it is legal to hoist instructions into this block.
    bool isLegalToHoistInto() {
      // There are currently no constraints that prevent an instruction to be
      // hoisted into a VPBlockBase.
      return true;
    }
  };
  
  /// VPRecipeBase is a base class modeling a sequence of one or more output IR
  /// instructions.
  class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
    friend VPBasicBlock;
  
  private:
    const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
  
    /// Each VPRecipe belongs to a single VPBasicBlock.
    VPBasicBlock *Parent = nullptr;
  
  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 {
      VPBlendSC,
      VPBranchOnMaskSC,
      VPInstructionSC,
      VPInterleaveSC,
      VPPredInstPHISC,
      VPReplicateSC,
      VPWidenIntOrFpInductionSC,
      VPWidenMemoryInstructionSC,
      VPWidenPHISC,
      VPWidenSC,
    };
  
    VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
    virtual ~VPRecipeBase() = default;
  
    /// \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 getVPRecipeID() const { return SubclassID; }
  
    /// \return the VPBasicBlock which this VPRecipe belongs to.
    VPBasicBlock *getParent() { return Parent; }
    const VPBasicBlock *getParent() const { return Parent; }
  
    /// The method which generates the output IR instructions that correspond to
    /// this VPRecipe, thereby "executing" the VPlan.
    virtual void execute(struct VPTransformState &State) = 0;
  
    /// Each recipe prints itself.
    virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
  
    /// Insert an unlinked recipe into a basic block immediately before
    /// the specified recipe.
    void insertBefore(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);
  
    /// 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();
  };
  
  /// 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.
  class VPInstruction : public VPUser, public VPRecipeBase {
    friend class VPlanHCFGTransforms;
    friend class VPlanSlp;
  
  public:
    /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
    enum {
      Not = Instruction::OtherOpsEnd + 1,
      ICmpULE,
      SLPLoad,
      SLPStore,
    };
  
  private:
    typedef unsigned char OpcodeTy;
    OpcodeTy Opcode;
  
    /// Utility method serving execute(): generates a single instance of the
    /// modeled instruction.
    void generateInstruction(VPTransformState &State, unsigned Part);
  
  protected:
    Instruction *getUnderlyingInstr() {
      return cast_or_null<Instruction>(getUnderlyingValue());
    }
  
    void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
  
  public:
    VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
        : VPUser(VPValue::VPInstructionSC, Operands),
          VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
  
    VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
        : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {}
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPValue *V) {
      return V->getVPValueID() == VPValue::VPInstructionSC;
    }
  
    VPInstruction *clone() const {
      SmallVector<VPValue *, 2> Operands(operands());
      return new VPInstruction(Opcode, Operands);
    }
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *R) {
      return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
    }
  
    unsigned getOpcode() const { return Opcode; }
  
    /// Generate the instruction.
    /// TODO: We currently execute only per-part unless a specific instance is
    /// provided.
    void execute(VPTransformState &State) override;
  
    /// Print the Recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  
    /// Print the VPInstruction.
    void print(raw_ostream &O) const;
  
    /// Return true if this instruction may modify memory.
    bool mayWriteToMemory() const {
      // TODO: we can use attributes of the called function to rule out memory
      //       modifications.
      return Opcode == Instruction::Store || Opcode == Instruction::Call ||
             Opcode == Instruction::Invoke || Opcode == SLPStore;
    }
  };
  
  /// VPWidenRecipe is a recipe for producing a copy of vector type for each
  /// Instruction in its ingredients independently, in order. This recipe covers
  /// most of the traditional vectorization cases where each ingredient transforms
  /// into a vectorized version of itself.
  class VPWidenRecipe : public VPRecipeBase {
  private:
    /// Hold the ingredients by pointing to their original BasicBlock location.
    BasicBlock::iterator Begin;
    BasicBlock::iterator End;
  
  public:
    VPWidenRecipe(Instruction *I) : VPRecipeBase(VPWidenSC) {
      End = I->getIterator();
      Begin = End++;
    }
  
    ~VPWidenRecipe() override = default;
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
    }
  
    /// Produce widened copies of all Ingredients.
    void execute(VPTransformState &State) override;
  
    /// Augment the recipe to include Instr, if it lies at its End.
    bool appendInstruction(Instruction *Instr) {
      if (End != Instr->getIterator())
        return false;
      End++;
      return true;
    }
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// A recipe for handling phi nodes of integer and floating-point inductions,
  /// producing their vector and scalar values.
  class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
  private:
    PHINode *IV;
    TruncInst *Trunc;
  
  public:
    VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr)
        : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
    ~VPWidenIntOrFpInductionRecipe() override = default;
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
    }
  
    /// Generate the vectorized and scalarized versions of the phi node as
    /// needed by their users.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// A recipe for handling all phi nodes except for integer and FP inductions.
  class VPWidenPHIRecipe : public VPRecipeBase {
  private:
    PHINode *Phi;
  
  public:
    VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
    ~VPWidenPHIRecipe() override = default;
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
    }
  
    /// Generate the phi/select nodes.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// A recipe for vectorizing a phi-node as a sequence of mask-based select
  /// instructions.
  class VPBlendRecipe : public VPRecipeBase {
  private:
    PHINode *Phi;
  
    /// The blend operation is a User of a mask, if not null.
    std::unique_ptr<VPUser> User;
  
  public:
    VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Masks)
        : VPRecipeBase(VPBlendSC), Phi(Phi) {
      assert((Phi->getNumIncomingValues() == 1 ||
              Phi->getNumIncomingValues() == Masks.size()) &&
             "Expected the same number of incoming values and masks");
      if (!Masks.empty())
        User.reset(new VPUser(Masks));
    }
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
    }
  
    /// Generate the phi/select nodes.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
  /// or stores into one wide load/store and shuffles.
  class VPInterleaveRecipe : public VPRecipeBase {
  private:
    const InterleaveGroup<Instruction> *IG;
    std::unique_ptr<VPUser> User;
  
  public:
    VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Mask)
        : VPRecipeBase(VPInterleaveSC), IG(IG) {
      if (Mask) // Create a VPInstruction to register as a user of the mask.
        User.reset(new VPUser({Mask}));
    }
    ~VPInterleaveRecipe() override = default;
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
    }
  
    /// Generate the wide load or store, and shuffles.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  
    const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; }
  };
  
  /// 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
  /// uniform only one copy, per lane zero, will be generated.
  class VPReplicateRecipe : public VPRecipeBase {
  private:
    /// The instruction being replicated.
    Instruction *Ingredient;
  
    /// Indicator if only a single replica per lane is needed.
    bool IsUniform;
  
    /// Indicator if the replicas are also predicated.
    bool IsPredicated;
  
    /// Indicator if the scalar values should also be packed into a vector.
    bool AlsoPack;
  
  public:
    VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false)
        : VPRecipeBase(VPReplicateSC), Ingredient(I), IsUniform(IsUniform),
          IsPredicated(IsPredicated) {
      // Retain the previous behavior of predicateInstructions(), where an
      // insert-element of a predicated instruction got hoisted into the
      // predicated basic block iff it was its only user. This is achieved by
      // having predicated instructions also pack their values into a vector by
      // default unless they have a replicated user which uses their scalar value.
      AlsoPack = IsPredicated && !I->use_empty();
    }
  
    ~VPReplicateRecipe() override = default;
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == 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;
  
    void setAlsoPack(bool Pack) { AlsoPack = Pack; }
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// A recipe for generating conditional branches on the bits of a mask.
  class VPBranchOnMaskRecipe : public VPRecipeBase {
  private:
    std::unique_ptr<VPUser> User;
  
  public:
    VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
      if (BlockInMask) // nullptr means all-one mask.
        User.reset(new VPUser({BlockInMask}));
    }
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
    }
  
    /// Generate the extraction of the appropriate bit from the block mask and the
    /// conditional branch.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override {
      O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
      if (User)
        O << *User->getOperand(0);
      else
        O << " All-One";
      O << "\\l\"";
    }
  };
  
  /// 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 VPPredInstPHIRecipe : public VPRecipeBase {
  private:
    Instruction *PredInst;
  
  public:
    /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
    /// nodes after merging back from a Branch-on-Mask.
    VPPredInstPHIRecipe(Instruction *PredInst)
        : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
    ~VPPredInstPHIRecipe() override = default;
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
    }
  
    /// Generates phi nodes for live-outs as needed to retain SSA form.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// A Recipe for widening load/store operations.
  /// TODO: We currently execute only per-part unless a specific instance is
  /// provided.
  class VPWidenMemoryInstructionRecipe : public VPRecipeBase {
  private:
    Instruction &Instr;
    std::unique_ptr<VPUser> User;
  
  public:
    VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask)
        : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) {
      if (Mask) // Create a VPInstruction to register as a user of the mask.
        User.reset(new VPUser({Mask}));
    }
  
    /// Method to support type inquiry through isa, cast, and dyn_cast.
    static inline bool classof(const VPRecipeBase *V) {
      return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
    }
  
    /// Generate the wide load/store.
    void execute(VPTransformState &State) override;
  
    /// Print the recipe.
    void print(raw_ostream &O, const Twine &Indent) const override;
  };
  
  /// 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.
  class VPBasicBlock : public VPBlockBase {
  public:
    using RecipeListTy = iplist<VPRecipeBase>;
  
  private:
    /// The VPRecipes held in the order of output instructions to generate.
    RecipeListTy Recipes;
  
  public:
    VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
        : VPBlockBase(VPBasicBlockSC, Name.str()) {
      if (Recipe)
        appendRecipe(Recipe);
    }
  
    ~VPBasicBlock() override { Recipes.clear(); }
  
    /// 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;
    }
  
    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(struct VPTransformState *State) override;
  
  private:
    /// Create an IR BasicBlock to hold the output instructions generated by this
    /// VPBasicBlock, and return it. Update the CFGState accordingly.
    BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
  };
  
  /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
  /// which form a Single-Entry-Single-Exit 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 VPRegionBlock : public VPBlockBase {
  private:
    /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
    VPBlockBase *Entry;
  
    /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock.
    VPBlockBase *Exit;
  
    /// An indicator whether this region is to generate multiple replicated
    /// instances of output IR corresponding to its VPBlockBases.
    bool IsReplicator;
  
  public:
    VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit,
                  const std::string &Name = "", bool IsReplicator = false)
        : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit),
          IsReplicator(IsReplicator) {
      assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
      assert(Exit->getSuccessors().empty() && "Exit block has successors.");
      Entry->setParent(this);
      Exit->setParent(this);
    }
    VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
        : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr),
          IsReplicator(IsReplicator) {}
  
    ~VPRegionBlock() override {
      if (Entry)
        deleteCFG(Entry);
    }
  
    /// 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->getPredecessors().empty() &&
             "Entry block cannot have predecessors.");
      Entry = EntryBlock;
      EntryBlock->setParent(this);
    }
  
    // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
    // specific interface of llvm::Function, instead of using
    // GraphTraints::getEntryNode. We should add a new template parameter to
    // DominatorTreeBase representing the Graph type.
    VPBlockBase &front() const { return *Entry; }
  
    const VPBlockBase *getExit() const { return Exit; }
    VPBlockBase *getExit() { return Exit; }
  
    /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p
    /// ExitBlock must have no successors.
    void setExit(VPBlockBase *ExitBlock) {
      assert(ExitBlock->getSuccessors().empty() &&
             "Exit block cannot have successors.");
      Exit = ExitBlock;
      ExitBlock->setParent(this);
    }
  
    /// An indicator whether this region is to generate multiple replicated
    /// instances of output IR corresponding to its VPBlockBases.
    bool isReplicator() const { return IsReplicator; }
  
    /// The method which generates the output IR instructions that correspond to
    /// this VPRegionBlock, thereby "executing" the VPlan.
    void execute(struct VPTransformState *State) override;
  };
  
  /// 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
  /// VPBlock.
  class VPlan {
    friend class VPlanPrinter;
  
  private:
    /// Hold the single entry to the Hierarchical CFG of the VPlan.
    VPBlockBase *Entry;
  
    /// Holds the VFs applicable to this VPlan.
    SmallSet<unsigned, 2> VFs;
  
    /// Holds the name of the VPlan, for printing.
    std::string Name;
  
    /// Holds all the external definitions created for this VPlan.
    // TODO: Introduce a specific representation for external definitions in
    // VPlan. External definitions must be immutable and hold a pointer to its
    // underlying IR that will be used to implement its structural comparison
    // (operators '==' and '<').
    SmallPtrSet<VPValue *, 16> VPExternalDefs;
  
    /// Represents the backedge taken count of the original loop, for folding
    /// the tail.
    VPValue *BackedgeTakenCount = nullptr;
  
    /// Holds a mapping between Values and their corresponding VPValue inside
    /// VPlan.
    Value2VPValueTy Value2VPValue;
  
    /// Holds the VPLoopInfo analysis for this VPlan.
    VPLoopInfo VPLInfo;
  
    /// Holds the condition bit values built during VPInstruction to VPRecipe transformation.
    SmallVector<VPValue *, 4> VPCBVs;
  
  public:
    VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {}
  
    ~VPlan() {
      if (Entry)
        VPBlockBase::deleteCFG(Entry);
      for (auto &MapEntry : Value2VPValue)
        if (MapEntry.second != BackedgeTakenCount)
          delete MapEntry.second;
      if (BackedgeTakenCount)
        delete BackedgeTakenCount; // Delete once, if in Value2VPValue or not.
      for (VPValue *Def : VPExternalDefs)
        delete Def;
      for (VPValue *CBV : VPCBVs)
        delete CBV;
    }
  
    /// Generate the IR code for this VPlan.
    void execute(struct VPTransformState *State);
  
    VPBlockBase *getEntry() { return Entry; }
    const VPBlockBase *getEntry() const { return Entry; }
  
    VPBlockBase *setEntry(VPBlockBase *Block) { return Entry = Block; }
  
    /// The backedge taken count of the original loop.
    VPValue *getOrCreateBackedgeTakenCount() {
      if (!BackedgeTakenCount)
        BackedgeTakenCount = new VPValue();
      return BackedgeTakenCount;
    }
  
    void addVF(unsigned VF) { VFs.insert(VF); }
  
    bool hasVF(unsigned VF) { return VFs.count(VF); }
  
    const std::string &getName() const { return Name; }
  
    void setName(const Twine &newName) { Name = newName.str(); }
  
    /// Add \p VPVal to the pool of external definitions if it's not already
    /// in the pool.
    void addExternalDef(VPValue *VPVal) {
      VPExternalDefs.insert(VPVal);
    }
  
    /// Add \p CBV to the vector of condition bit values.
    void addCBV(VPValue *CBV) {
      VPCBVs.push_back(CBV);
    }
  
    void addVPValue(Value *V) {
      assert(V && "Trying to add a null Value to VPlan");
      assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
      Value2VPValue[V] = new VPValue();
    }
  
    VPValue *getVPValue(Value *V) {
      assert(V && "Trying to get the VPValue of a null Value");
      assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
      return Value2VPValue[V];
    }
  
    /// Return the VPLoopInfo analysis for this VPlan.
    VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
    const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
  
  private:
    /// Add to the given dominator tree the header block and every new basic block
    /// that was created between it and the latch block, inclusive.
    static void updateDominatorTree(DominatorTree *DT,
                                    BasicBlock *LoopPreHeaderBB,
                                    BasicBlock *LoopLatchBB);
  };
  
  /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
  /// indented and follows the dot format.
  class VPlanPrinter {
    friend inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan);
    friend inline raw_ostream &operator<<(raw_ostream &OS,
                                          const struct VPlanIngredient &I);
  
  private:
    raw_ostream &OS;
    VPlan &Plan;
    unsigned Depth;
    unsigned TabWidth = 2;
    std::string Indent;
    unsigned BID = 0;
    SmallDenseMap<const VPBlockBase *, unsigned> BlockID;
  
    VPlanPrinter(raw_ostream &O, VPlan &P) : OS(O), Plan(P) {}
  
    /// Handle indentation.
    void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
  
    /// Print a given \p Block of the Plan.
    void dumpBlock(const VPBlockBase *Block);
  
    /// Print the information related to the CFG edges going out of a given
    /// \p Block, followed by printing the successor blocks themselves.
    void dumpEdges(const VPBlockBase *Block);
  
    /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
    /// its successor blocks.
    void dumpBasicBlock(const VPBasicBlock *BasicBlock);
  
    /// Print a given \p Region of the Plan.
    void dumpRegion(const VPRegionBlock *Region);
  
    unsigned getOrCreateBID(const VPBlockBase *Block) {
      return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
    }
  
    const Twine getOrCreateName(const VPBlockBase *Block);
  
    const Twine getUID(const VPBlockBase *Block);
  
    /// Print the information related to a CFG edge between two VPBlockBases.
    void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
                  const Twine &Label);
  
    void dump();
  
    static void printAsIngredient(raw_ostream &O, Value *V);
  };
  
  struct VPlanIngredient {
    Value *V;
  
    VPlanIngredient(Value *V) : V(V) {}
  };
  
  inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) {
    VPlanPrinter::printAsIngredient(OS, I.V);
    return OS;
  }
  
  inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan) {
    VPlanPrinter Printer(OS, Plan);
    Printer.dump();
    return OS;
  }
  
  //===----------------------------------------------------------------------===//
  // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs     //
  //===----------------------------------------------------------------------===//
  
  // The following set of template specializations implement GraphTraits to treat
  // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
  // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
  // VPBlockBase is a VPRegionBlock, this specialization provides access to its
  // successors/predecessors but not to the blocks inside the region.
  
  template <> struct GraphTraits<VPBlockBase *> {
    using NodeRef = VPBlockBase *;
    using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
  
    static NodeRef getEntryNode(NodeRef N) { return N; }
  
    static inline ChildIteratorType child_begin(NodeRef N) {
      return N->getSuccessors().begin();
    }
  
    static inline ChildIteratorType child_end(NodeRef N) {
      return N->getSuccessors().end();
    }
  };
  
  template <> struct GraphTraits<const VPBlockBase *> {
    using NodeRef = const VPBlockBase *;
    using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
  
    static NodeRef getEntryNode(NodeRef N) { return N; }
  
    static inline ChildIteratorType child_begin(NodeRef N) {
      return N->getSuccessors().begin();
    }
  
    static inline ChildIteratorType child_end(NodeRef N) {
      return N->getSuccessors().end();
    }
  };
  
  // Inverse order specialization for VPBasicBlocks. Predecessors are used instead
  // of successors for the inverse traversal.
  template <> struct GraphTraits<Inverse<VPBlockBase *>> {
    using NodeRef = VPBlockBase *;
    using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
  
    static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
  
    static inline ChildIteratorType child_begin(NodeRef N) {
      return N->getPredecessors().begin();
    }
  
    static inline ChildIteratorType child_end(NodeRef N) {
      return N->getPredecessors().end();
    }
  };
  
  // The following set of template specializations implement GraphTraits to
  // treat VPRegionBlock as a graph and recurse inside its nodes. It's important
  // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
  // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
  // there won't be automatic recursion into other VPBlockBases that turn to be
  // VPRegionBlocks.
  
  template <>
  struct GraphTraits<VPRegionBlock *> : public GraphTraits<VPBlockBase *> {
    using GraphRef = VPRegionBlock *;
    using nodes_iterator = df_iterator<NodeRef>;
  
    static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
  
    static nodes_iterator nodes_begin(GraphRef N) {
      return nodes_iterator::begin(N->getEntry());
    }
  
    static nodes_iterator nodes_end(GraphRef N) {
      // df_iterator::end() returns an empty iterator so the node used doesn't
      // matter.
      return nodes_iterator::end(N);
    }
  };
  
  template <>
  struct GraphTraits<const VPRegionBlock *>
      : public GraphTraits<const VPBlockBase *> {
    using GraphRef = const VPRegionBlock *;
    using nodes_iterator = df_iterator<NodeRef>;
  
    static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
  
    static nodes_iterator nodes_begin(GraphRef N) {
      return nodes_iterator::begin(N->getEntry());
    }
  
    static nodes_iterator nodes_end(GraphRef N) {
      // df_iterator::end() returns an empty iterator so the node used doesn't
      // matter.
      return nodes_iterator::end(N);
    }
  };
  
  template <>
  struct GraphTraits<Inverse<VPRegionBlock *>>
      : public GraphTraits<Inverse<VPBlockBase *>> {
    using GraphRef = VPRegionBlock *;
    using nodes_iterator = df_iterator<NodeRef>;
  
    static NodeRef getEntryNode(Inverse<GraphRef> N) {
      return N.Graph->getExit();
    }
  
    static nodes_iterator nodes_begin(GraphRef N) {
      return nodes_iterator::begin(N->getExit());
    }
  
    static nodes_iterator nodes_end(GraphRef N) {
      // df_iterator::end() returns an empty iterator so the node used doesn't
      // matter.
      return nodes_iterator::end(N);
    }
  };
  
  //===----------------------------------------------------------------------===//
  // VPlan Utilities
  //===----------------------------------------------------------------------===//
  
  /// Class that provides utilities for VPBlockBases in VPlan.
  class VPBlockUtils {
  public:
    VPBlockUtils() = delete;
  
    /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
    /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
    /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr
    /// has more than one successor, its conditional bit is propagated to \p
    /// NewBlock. \p NewBlock must have neither successors nor predecessors.
    static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
      assert(NewBlock->getSuccessors().empty() &&
             "Can't insert new block with successors.");
      // TODO: move successors from BlockPtr to NewBlock when this functionality
      // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr
      // already has successors.
      BlockPtr->setOneSuccessor(NewBlock);
      NewBlock->setPredecessors({BlockPtr});
      NewBlock->setParent(BlockPtr->getParent());
    }
  
    /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
    /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
    /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
    /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor
    /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse
    /// must have neither successors nor predecessors.
    static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
                                     VPValue *Condition, VPBlockBase *BlockPtr) {
      assert(IfTrue->getSuccessors().empty() &&
             "Can't insert IfTrue with successors.");
      assert(IfFalse->getSuccessors().empty() &&
             "Can't insert IfFalse with successors.");
      BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition);
      IfTrue->setPredecessors({BlockPtr});
      IfFalse->setPredecessors({BlockPtr});
      IfTrue->setParent(BlockPtr->getParent());
      IfFalse->setParent(BlockPtr->getParent());
    }
  
    /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
    /// the successors of \p From and \p From to the predecessors of \p To. Both
    /// VPBlockBases must have the same parent, which can be null. Both
    /// VPBlockBases can be already connected to other VPBlockBases.
    static void connectBlocks(VPBlockBase *From, VPBlockBase *To) {
      assert((From->getParent() == To->getParent()) &&
             "Can't connect two block with different parents");
      assert(From->getNumSuccessors() < 2 &&
             "Blocks can't have more than two successors.");
      From->appendSuccessor(To);
      To->appendPredecessor(From);
    }
  
    /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
    /// from the successors of \p From and \p From from the predecessors of \p To.
    static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
      assert(To && "Successor to disconnect is null.");
      From->removeSuccessor(To);
      To->removePredecessor(From);
    }
  
    /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge.
    static bool isBackEdge(const VPBlockBase *FromBlock,
                           const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) {
      assert(FromBlock->getParent() == ToBlock->getParent() &&
             FromBlock->getParent() && "Must be in same region");
      const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock);
      const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock);
      if (!FromLoop || !ToLoop || FromLoop != ToLoop)
        return false;
  
      // A back-edge is a branch from the loop latch to its header.
      return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader();
    }
  
    /// Returns true if \p Block is a loop latch
    static bool blockIsLoopLatch(const VPBlockBase *Block,
                                 const VPLoopInfo *VPLInfo) {
      if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block))
        return ParentVPL->isLoopLatch(Block);
  
      return false;
    }
  
    /// Count and return the number of succesors of \p PredBlock excluding any
    /// backedges.
    static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock,
                                        VPLoopInfo *VPLI) {
      unsigned Count = 0;
      for (VPBlockBase *SuccBlock : PredBlock->getSuccessors()) {
        if (!VPBlockUtils::isBackEdge(PredBlock, SuccBlock, VPLI))
          Count++;
      }
      return Count;
    }
  };
  
  class VPInterleavedAccessInfo {
  private:
    DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *>
        InterleaveGroupMap;
  
    /// Type for mapping of instruction based interleave groups to VPInstruction
    /// interleave groups
    using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *,
                               InterleaveGroup<VPInstruction> *>;
  
    /// Recursively \p Region and populate VPlan based interleave groups based on
    /// \p IAI.
    void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
                     InterleavedAccessInfo &IAI);
    /// Recursively traverse \p Block and populate VPlan based interleave groups
    /// based on \p IAI.
    void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
                    InterleavedAccessInfo &IAI);
  
  public:
    VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI);
  
    ~VPInterleavedAccessInfo() {
      SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet;
      // Avoid releasing a pointer twice.
      for (auto &I : InterleaveGroupMap)
        DelSet.insert(I.second);
      for (auto *Ptr : DelSet)
        delete Ptr;
    }
  
    /// Get the interleave group that \p Instr belongs to.
    ///
    /// \returns nullptr if doesn't have such group.
    InterleaveGroup<VPInstruction> *
    getInterleaveGroup(VPInstruction *Instr) const {
      if (InterleaveGroupMap.count(Instr))
        return InterleaveGroupMap.find(Instr)->second;
      return nullptr;
    }
  };
  
  /// Class that maps (parts of) an existing VPlan to trees of combined
  /// VPInstructions.
  class VPlanSlp {
  private:
    enum class OpMode { Failed, Load, Opcode };
  
    /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as
    /// DenseMap keys.
    struct BundleDenseMapInfo {
      static SmallVector<VPValue *, 4> getEmptyKey() {
        return {reinterpret_cast<VPValue *>(-1)};
      }
  
      static SmallVector<VPValue *, 4> getTombstoneKey() {
        return {reinterpret_cast<VPValue *>(-2)};
      }
  
      static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) {
        return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
      }
  
      static bool isEqual(const SmallVector<VPValue *, 4> &LHS,
                          const SmallVector<VPValue *, 4> &RHS) {
        return LHS == RHS;
      }
    };
  
    /// Mapping of values in the original VPlan to a combined VPInstruction.
    DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo>
        BundleToCombined;
  
    VPInterleavedAccessInfo &IAI;
  
    /// Basic block to operate on. For now, only instructions in a single BB are
    /// considered.
    const VPBasicBlock &BB;
  
    /// Indicates whether we managed to combine all visited instructions or not.
    bool CompletelySLP = true;
  
    /// Width of the widest combined bundle in bits.
    unsigned WidestBundleBits = 0;
  
    using MultiNodeOpTy =
        typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
  
    // Input operand bundles for the current multi node. Each multi node operand
    // bundle contains values not matching the multi node's opcode. They will
    // be reordered in reorderMultiNodeOps, once we completed building a
    // multi node.
    SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
  
    /// Indicates whether we are building a multi node currently.
    bool MultiNodeActive = false;
  
    /// Check if we can vectorize Operands together.
    bool areVectorizable(ArrayRef<VPValue *> Operands) const;
  
    /// Add combined instruction \p New for the bundle \p Operands.
    void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
  
    /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
    VPInstruction *markFailed();
  
    /// Reorder operands in the multi node to maximize sequential memory access
    /// and commutative operations.
    SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
  
    /// Choose the best candidate to use for the lane after \p Last. The set of
    /// candidates to choose from are values with an opcode matching \p Last's
    /// or loads consecutive to \p Last.
    std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
                                         SmallPtrSetImpl<VPValue *> &Candidates,
                                         VPInterleavedAccessInfo &IAI);
  
    /// Print bundle \p Values to dbgs().
    void dumpBundle(ArrayRef<VPValue *> Values);
  
  public:
    VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}
  
    ~VPlanSlp() {
      for (auto &KV : BundleToCombined)
        delete KV.second;
    }
  
    /// Tries to build an SLP tree rooted at \p Operands and returns a
    /// VPInstruction combining \p Operands, if they can be combined.
    VPInstruction *buildGraph(ArrayRef<VPValue *> Operands);
  
    /// Return the width of the widest combined bundle in bits.
    unsigned getWidestBundleBits() const { return WidestBundleBits; }
  
    /// Return true if all visited instruction can be combined.
    bool isCompletelySLP() const { return CompletelySLP; }
  };
  } // end namespace llvm
  
  #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
  