llvm/lib/Transforms/Vectorize/VPlanValue.h

//===- VPlanValue.h - Represent Values in Vectorizer Plan -----------------===//
//
// 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 entities induced by Vectorization
/// Plans, e.g. the instructions the VPlan intends to generate if executed.
/// VPlan models the following entities:
/// VPValue   VPUser   VPDef
///    |        |
///   VPInstruction
/// These are documented in docs/VectorizationPlan.rst.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H

#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"

namespace llvm {

// Forward declarations.
class raw_ostream;
class Type;
class Value;
class VPDef;
class VPSlotTracker;
class VPUser;
class VPRecipeBase;
class VPPhiAccessors;
class VPRegionValue;
class VPRegionBlock;
class VPSingleDefRecipe;

/// This is the base class of the VPlan Def/Use graph, used for modeling the
/// data flow into, within and out of the VPlan. VPValues can stand for live-ins
/// coming from the input IR, symbolic values and values defined by recipes.
class LLVM_ABI_FOR_TEST VPValue {
  friend struct VPIRValue;
  friend class VPSymbolicValue;
  friend class VPRecipeValue;
  friend class VPRegionValue;

  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).

  SmallVector<VPUser *, 1> Users;

  /// Hold the underlying Value, if any, attached to this VPValue.
  Value *UnderlyingVal;

  VPValue(const unsigned char SC, Value *UV = nullptr)
      : SubclassID(SC), UnderlyingVal(UV) {}

  // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
  // the front-end and back-end of VPlan so that the middle-end is as
  // independent as possible of the underlying IR. We grant access to the
  // underlying IR using friendship. In that way, we should be able to use VPlan
  // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
  // back-end and analysis information for the new IR.

public:
  /// Return the underlying Value attached to this VPValue.
  Value *getUnderlyingValue() const { return UnderlyingVal; }

  /// Return the underlying IR value for a VPIRValue.
  Value *getLiveInIRValue() const;

  /// An enumeration for keeping track of the concrete subclass of VPValue that
  /// are actually instantiated.
  enum {
    VPVIRValueSC,        /// A live-in VPValue wrapping an IR Value.
    VPVSymbolicSC,       /// A symbolic live-in VPValue without IR backing.
    VPVSingleDefValueSC, /// A VPValue defined by a VPSingleDefRecipe.
    VPVMultiDefValueSC,  /// A VPValue defined by a multi-def recipe.
    VPRegionValueSC,     /// A VPValue sub-class that is defined by a
                         /// region, like a loop region canonical IV.
  };

  VPValue(const VPValue &) = delete;
  VPValue &operator=(const VPValue &) = delete;

  virtual ~VPValue() {
    assert(user_empty() && "trying to delete a VPValue with remaining users");
  }

  /// \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 getVPValueID() const { return SubclassID; }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
  void print(raw_ostream &OS, VPSlotTracker &Tracker) const;

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

  /// Assert that this VPValue has not been materialized, if it is a
  /// VPSymbolicValue.
  void assertNotMaterialized() const;

  unsigned getNumUsers() const {
    if (user_empty())
      return 0;
    assertNotMaterialized();
    return Users.size();
  }
  void addUser(VPUser &User) {
    assertNotMaterialized();
    Users.push_back(&User);
  }

  /// Remove a single \p User from the list of users.
  void removeUser(VPUser &User) {
    assertNotMaterialized();
    // The same user can be added multiple times, e.g. because the same VPValue
    // is used twice by the same VPUser. Remove a single one.
    auto *I = find(Users, &User);
    if (I != Users.end())
      Users.erase(I);
  }

  typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
  typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
  typedef iterator_range<user_iterator> user_range;
  typedef iterator_range<const_user_iterator> const_user_range;

  user_iterator user_begin() {
    assertNotMaterialized();
    return Users.begin();
  }
  const_user_iterator user_begin() const {
    assertNotMaterialized();
    return Users.begin();
  }
  user_iterator user_end() {
    assertNotMaterialized();
    return Users.end();
  }
  const_user_iterator user_end() const {
    assertNotMaterialized();
    return Users.end();
  }
  user_range users() { return user_range(user_begin(), user_end()); }
  const_user_range users() const {
    return const_user_range(user_begin(), user_end());
  }
  bool user_empty() const { return Users.empty(); } // NOLINT

  /// Returns true if the value has more than one unique user.
  bool hasMoreThanOneUniqueUser() const {
    if (user_empty())
      return false;

    // Check if all users match the first user.
    auto Current = std::next(user_begin());
    while (Current != user_end() && *user_begin() == *Current)
      Current++;
    return Current != user_end();
  }

  bool hasOneUse() const { return getNumUsers() == 1; }

  /// Return the single user of this value, or nullptr if there is not exactly
  /// one user.
  VPUser *getSingleUser() { return hasOneUse() ? *user_begin() : nullptr; }
  const VPUser *getSingleUser() const {
    return hasOneUse() ? *user_begin() : nullptr;
  }

  void replaceAllUsesWith(VPValue *New);

  /// Go through the uses list for this VPValue and make each use point to \p
  /// New if the callback ShouldReplace returns true for the given use specified
  /// by a pair of (VPUser, the use index).
  void replaceUsesWithIf(
      VPValue *New,
      llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace);

  /// Returns the recipe defining this VPValue or nullptr if it is not defined
  /// by a recipe, i.e. is a live-in.
  VPRecipeBase *getDefiningRecipe();
  const VPRecipeBase *getDefiningRecipe() const;

  /// Returns the scalar type of this VPValue, dispatching based on the
  /// concrete subclass.
  Type *getScalarType() const;

  /// Returns true if the VPValue is defined outside any loop.
  bool isDefinedOutsideLoopRegions() const;

  // Set \p Val as the underlying Value of this VPValue.
  void setUnderlyingValue(Value *Val) {
    assert(!UnderlyingVal && "Underlying Value is already set.");
    UnderlyingVal = Val;
  }
};

/// A symbolic live-in VPValue, used for values like vector trip count, VF, and
/// VFxUF.
class VPSymbolicValue : public VPValue {
  /// The scalar type of this symbolic value.
  Type *Ty;

  /// Track whether this value has been materialized (replaced). After
  /// materialization, accessing users should trigger an assertion.
  bool Materialized = false;

protected:
  VPSymbolicValue(unsigned char SC, Type *Ty) : VPValue(SC, nullptr), Ty(Ty) {}

public:
  VPSymbolicValue(Type *Ty) : VPSymbolicValue(VPVSymbolicSC, Ty) {}

  /// Returns the scalar type of this symbolic value.
  Type *getType() const { return Ty; }

  /// Returns true if this value has been materialized.
  bool isMaterialized() const { return Materialized; }

  /// Mark this value as materialized.
  void markMaterialized() {
    assert(!Materialized && "VPSymbolicValue already materialized");
    Materialized = true;
  }

  static bool classof(const VPValue *V) {
    return V->getVPValueID() == VPVSymbolicSC ||
           V->getVPValueID() == VPRegionValueSC;
  }
};

/// VPValues are defined by a VPRegionBlock, like the canonical IV. They must
/// be materialized when the containing region is dissolved, before VPlan
/// execution.
class VPRegionValue : public VPSymbolicValue {
  VPRegionBlock *DefiningRegion;
  DebugLoc DL;

public:
  VPRegionValue(Type *Ty, DebugLoc DL, VPRegionBlock *Region)
      : VPSymbolicValue(VPValue::VPRegionValueSC, Ty), DefiningRegion(Region),
        DL(DL) {}

  ~VPRegionValue() override = default;

  /// Returns the region that defines this value.
  VPRegionBlock *getDefiningRegion() const { return DefiningRegion; }

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

  static inline bool classof(const VPValue *V) {
    return V->getVPValueID() == VPValue::VPRegionValueSC;
  }
};

LLVM_ABI_FOR_TEST raw_ostream &operator<<(raw_ostream &OS,
                                          const VPRecipeBase &R);

/// A VPValue representing a live-in from the input IR or a constant. It wraps
/// an underlying IR Value.
struct VPIRValue : public VPValue {
  VPIRValue(Value *UV) : VPValue(VPVIRValueSC, UV) {
    assert(UV && "VPIRValue requires an underlying IR value");
  }

  /// Returns the underlying IR value.
  Value *getValue() const { return getUnderlyingValue(); }

  /// Returns the type of the underlying IR value.
  Type *getType() const;

  static bool classof(const VPValue *V) {
    return V->getVPValueID() == VPVIRValueSC;
  }
};

/// An overlay on VPIRValue for VPValues that wrap a Constant. May be an
/// integer, floating-point, or a vector constant.
struct VPConstant : public VPIRValue {
  VPConstant(Constant *C) : VPIRValue(C) {}

  static bool classof(const VPValue *V) {
    auto *IRV = dyn_cast<VPIRValue>(V);
    return IRV && isa<Constant>(IRV->getValue());
  }

  const Constant *getConstant() const { return cast<Constant>(getValue()); }
};

/// An overlay on VPConstant for VPValues that wrap a ConstantInt. Provides
/// convenient accessors for the underlying APInt.
struct VPConstantInt : public VPConstant {
  VPConstantInt(ConstantInt *CI) : VPConstant(CI) {}

  static bool classof(const VPValue *V) {
    auto *VPC = dyn_cast<VPConstant>(V);
    return VPC && isa<ConstantInt>(VPC->getConstant());
  }

  bool isOne() const { return getAPInt().isOne(); }

  bool isZero() const { return getAPInt().isZero(); }

  const APInt &getAPInt() const {
    return cast<ConstantInt>(getValue())->getValue();
  }

  unsigned getBitWidth() const { return getAPInt().getBitWidth(); }

  uint64_t getZExtValue() const { return getAPInt().getZExtValue(); }
};

/// Abstract base class for VPValues defined by a VPRecipeBase.
class VPRecipeValue : public VPValue {
  friend class VPValue;
  friend class VPDef;

  /// The scalar type of the value produced by this recipe.
  Type *Ty = nullptr;

#if !defined(NDEBUG)
  /// Returns true if this VPRecipeValue is defined by \p D.
  /// NOTE: Only used by VPDef to assert that VPRecipeValues added/removed from
  /// /p D are associated with its VPRecipeBase.
  bool isDefinedBy(const VPDef *D) const;
#endif

protected:
  VPRecipeValue(unsigned char SC, Value *UV, Type *Ty = nullptr)
      : VPValue(SC, UV), Ty(Ty) {}

public:
  LLVM_ABI_FOR_TEST virtual ~VPRecipeValue() = 0;

  /// Returns the scalar type of this VPRecipeValue.
  Type *getScalarType() const { return Ty; }

  static bool classof(const VPValue *V) {
    return V->getVPValueID() == VPVMultiDefValueSC ||
           V->getVPValueID() == VPVSingleDefValueSC;
  }
};

/// A VPRecipeValue defined by a VPSingleDefRecipe.
class LLVM_ABI_FOR_TEST VPSingleDefValue : public VPRecipeValue {
  friend class VPDef;
  friend class VPSingleDefRecipe;

protected:
  /// Construct a VPSingleDefValue. Must only be used by VPSingleDefRecipe.
  VPSingleDefValue(VPSingleDefRecipe *Def, Value *UV = nullptr,
                   Type *Ty = nullptr);

public:
  ~VPSingleDefValue() override;

  static bool classof(const VPValue *V) {
    return V->getVPValueID() == VPVSingleDefValueSC;
  }
};

/// A VPRecipeValue defined by a multi-def recipe, stores a pointer to it.
class VPMultiDefValue : public VPRecipeValue {
  friend class VPDef;

  /// Pointer to the multi-def recipe that defines this VPValue, among others.
  VPRecipeBase *Def;

public:
  LLVM_ABI_FOR_TEST VPMultiDefValue(VPRecipeBase *Def, Value *UV, Type *Ty);

  ~VPMultiDefValue() override;

  VPRecipeBase *getDef() const { return Def; }

  static bool classof(const VPValue *V) {
    return V->getVPValueID() == VPVMultiDefValueSC;
  }
};

/// This class augments VPValue with operands which provide the inverse def-use
/// edges from VPValue's users to their defs.
class LLVM_ABI_FOR_TEST VPUser {
  /// Grant access to removeOperand for VPPhiAccessors, the only supported user.
  friend class VPPhiAccessors;
  /// Grant access to addOperand for VPWidenMemoryRecipe.
  friend class VPWidenMemoryRecipe;

  SmallVector<VPValue *, 2> Operands;

  /// Removes the operand at index \p Idx. This also removes the VPUser from the
  /// use-list of the operand.
  void removeOperand(unsigned Idx) {
    getOperand(Idx)->removeUser(*this);
    Operands.erase(Operands.begin() + Idx);
  }

protected:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Print the operands to \p O.
  void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
#endif

  VPUser(ArrayRef<VPValue *> Operands) {
    for (VPValue *Operand : Operands)
      addOperand(Operand);
  }

  void addOperand(VPValue *Operand) {
    Operands.push_back(Operand);
    Operand->addUser(*this);
  }

public:
  VPUser() = delete;
  VPUser(const VPUser &) = delete;
  VPUser &operator=(const VPUser &) = delete;
  virtual ~VPUser() {
    for (VPValue *Op : operands())
      Op->removeUser(*this);
  }

  unsigned getNumOperands() const { return Operands.size(); }
  inline VPValue *getOperand(unsigned N) const {
    assert(N < Operands.size() && "Operand index out of bounds");
    return Operands[N];
  }

  void setOperand(unsigned I, VPValue *New) {
    assert((!Operands[I]->getScalarType() || !New->getScalarType() ||
            Operands[I]->getScalarType() == New->getScalarType()) &&
           "scalar type of new operand must match the old operand");
    Operands[I]->removeUser(*this);
    Operands[I] = New;
    New->addUser(*this);
  }

  /// Swap operands of the VPUser. It must have exactly 2 operands.
  void swapOperands() {
    assert(Operands.size() == 2 && "must have 2 operands to swap");
    std::swap(Operands[0], Operands[1]);
  }

  /// Replaces all uses of \p From in the VPUser with \p To.
  void replaceUsesOfWith(VPValue *From, VPValue *To);

  typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
  typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
  typedef iterator_range<operand_iterator> operand_range;
  typedef iterator_range<const_operand_iterator> const_operand_range;

  operand_iterator op_begin() { return Operands.begin(); }
  const_operand_iterator op_begin() const { return Operands.begin(); }
  operand_iterator op_end() { return Operands.end(); }
  const_operand_iterator op_end() const { return Operands.end(); }
  operand_range operands() { return operand_range(op_begin(), op_end()); }
  const_operand_range operands() const {
    return const_operand_range(op_begin(), op_end());
  }
  bool operands_empty() const { return Operands.empty(); } // NOLINT

  /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
  /// returns if only first (scalar) lane is used, as default.
  virtual bool usesScalars(const VPValue *Op) const {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return usesFirstLaneOnly(Op);
  }

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

  /// Returns true if the VPUser only uses the first part of operand \p Op.
  /// Conservatively returns false.
  virtual bool usesFirstPartOnly(const VPValue *Op) const {
    assert(is_contained(operands(), Op) &&
           "Op must be an operand of the recipe");
    return false;
  }
};

/// This class augments a recipe with a set of VPValues defined by the recipe.
/// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
/// the VPValues it defines and is responsible for deleting its defined values.
/// Single-value VPDefs that also inherit from VPValue must make sure to inherit
/// from VPDef before VPValue.
class VPDef {
  friend class VPRecipeValue;
  friend class VPSingleDefValue;
  friend class VPMultiDefValue;

  /// The VPValues defined by this VPDef.
  TinyPtrVector<VPRecipeValue *> DefinedValues;

  /// Add \p V as a defined value by this VPDef.
  void addDefinedValue(VPRecipeValue *V) {
    assert(V->isDefinedBy(this) &&
           "can only add VPValue already linked with this VPDef");
    DefinedValues.push_back(V);
  }

  /// Remove \p V from the values defined by this VPDef. \p V must be a defined
  /// value of this VPDef.
  void removeDefinedValue(VPRecipeValue *V) {
    assert(V->isDefinedBy(this) &&
           "can only remove VPValue linked with this VPDef");
    assert(is_contained(DefinedValues, V) &&
           "VPValue to remove must be in DefinedValues");
    llvm::erase(DefinedValues, V);
    if (auto *SV = dyn_cast<VPMultiDefValue>(V))
      SV->Def = nullptr;
  }

public:
  VPDef() {}

  virtual ~VPDef() {
    for (VPRecipeValue *D : to_vector(DefinedValues)) {
      assert(D->isDefinedBy(this) &&
             "all defined VPValues should point to the containing VPDef");
      assert(D->user_empty() &&
             "all defined VPValues should have no more users");
      delete D;
    }
  }

  /// Returns the only VPValue defined by the VPDef. Can only be called for
  /// VPDefs with a single defined value.
  VPValue *getVPSingleValue() {
    assert(DefinedValues.size() == 1 && "must have exactly one defined value");
    assert(DefinedValues[0] && "defined value must be non-null");
    return DefinedValues[0];
  }
  const VPValue *getVPSingleValue() const {
    assert(DefinedValues.size() == 1 && "must have exactly one defined value");
    assert(DefinedValues[0] && "defined value must be non-null");
    return DefinedValues[0];
  }

  /// Returns the VPValue with index \p I defined by the VPDef.
  VPValue *getVPValue(unsigned I) {
    assert(DefinedValues[I] && "defined value must be non-null");
    return DefinedValues[I];
  }
  const VPValue *getVPValue(unsigned I) const {
    assert(DefinedValues[I] && "defined value must be non-null");
    return DefinedValues[I];
  }

  /// Returns an ArrayRef of the values defined by the VPDef.
  ArrayRef<VPRecipeValue *> definedValues() { return DefinedValues; }
  /// Returns an ArrayRef of the values defined by the VPDef.
  ArrayRef<VPRecipeValue *> definedValues() const { return DefinedValues; }

  /// Returns the number of values defined by the VPDef.
  unsigned getNumDefinedValues() const { return DefinedValues.size(); }
};

inline void VPValue::assertNotMaterialized() const {
  assert((!isa<VPSymbolicValue>(this) ||
          !cast<VPSymbolicValue>(this)->isMaterialized()) &&
         "accessing materialized symbolic value");
}

} // namespace llvm

#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H