diff --git a/llvm/docs/Proposals/VectorizationPlan.rst b/llvm/docs/Proposals/VectorizationPlan.rst --- a/llvm/docs/Proposals/VectorizationPlan.rst +++ b/llvm/docs/Proposals/VectorizationPlan.rst @@ -149,6 +149,22 @@ The base of VPlan's def-use relations class hierarchy. When instantiated, it models a constant or a live-in Value in VPlan. It has users, which are of type VPUser, but no operands. + There are 3 different kinds of VPValues: + 1. Concrete VPValues + Concrete VPValues are either live-ins coming from IR or instructions/ + recipes in VPlan which produce a single value. They are the most common + kind. + 2. Sub VPValues + Sub-VPValues are result values from instructions/recipes in VPlan that + produce multiple values. They contain a reference to the producing + 'virtual' VPValue. + 3. Virtual VPValues + Virtual VPValues are used to model instructions/recipes that either produce + multiple subvalues or no values at all. A virtual VPValue does not refer to + a concrete value, which means it cannot be used like concrete or subvalues. + For example, they cannot be used as operands. They can be used to traverse + the def-use chains upwards. They also provide convenient access to all + users of all sub-values of the producer. :VPUser: A VPUser represents an entity that uses a number of VPValues as operands. diff --git a/llvm/lib/Transforms/Vectorize/VPlanValue.h b/llvm/lib/Transforms/Vectorize/VPlanValue.h --- a/llvm/lib/Transforms/Vectorize/VPlanValue.h +++ b/llvm/lib/Transforms/Vectorize/VPlanValue.h @@ -21,6 +21,7 @@ #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerSumType.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator_range.h" @@ -33,10 +34,43 @@ class VPUser; class VPRecipeBase; +class VPValue; + +/// Custom specialization for VPValue, so we can have a VPValue PointerSumType +/// member inside VPValue. This assumes 2 low bits available for VPValue *, +/// which is checked with a static_assert after the VPValue class definition. +template <> struct PointerLikeTypeTraits { + static inline void *getAsVoidPointer(VPValue *P) { + return reinterpret_cast(P); + } + static inline VPValue *getFromVoidPointer(void *P) { + return reinterpret_cast(P); + } + + static constexpr int NumLowBitsAvailable = 2; +}; + // 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, instructions which VPlan will generate if executed // and live-outs which the VPlan will need to fix accordingly. +// +// There are 3 different kinds of VPValues: +// 1. Concrete VPValues +// Concrete VPValues are either live-ins coming from IR or instructions/ +// recipes in VPlan which produce a single value. They are the most common +// kind. +// 2. Sub VPValues +// Sub-VPValues are result values from instructions/recipes in VPlan that +// produce multiple values. They contain a reference to the producing +// 'virtual' VPValue. +// 3. Virtual VPValues +// Virtual VPValues are used to model instructions/recipes that either produce +// multiple subvalues or no values at all. A virtual VPValue does not refer to +// a concrete value, which means it cannot be used like concrete or subvalues. +// For example, they cannot be used as operands. They can be used to traverse +// the def-use chains upwards. They also provide convenient access to all +// users of all sub-values of the producer. class VPValue { friend class VPBuilder; friend struct VPlanTransforms; @@ -50,11 +84,20 @@ SmallVector Users; protected: - // Hold the underlying Value, if any, attached to this VPValue. - Value *UnderlyingVal; + using UnderlyingOrProducerTy = + PointerSumType, + PointerSumTypeMember>; + /// Hold the underlying Value, if any, attached to this VPValue for concrete + /// VPValues or a pointer to the producing/defining VPValue. + UnderlyingOrProducerTy UnderlyingOrProducer; VPValue(const unsigned char SC, Value *UV = nullptr) - : SubclassID(SC), UnderlyingVal(UV) {} + : SubclassID(SC), + UnderlyingOrProducer(UnderlyingOrProducerTy::create(UV)) {} + + VPValue(const unsigned char SC, VPValue *Base) + : SubclassID(SC), + UnderlyingOrProducer(UnderlyingOrProducerTy::create(Base)) {} // 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 @@ -64,13 +107,16 @@ // back-end and analysis information for the new IR. /// Return the underlying Value attached to this VPValue. - Value *getUnderlyingValue() { return UnderlyingVal; } - const Value *getUnderlyingValue() const { return UnderlyingVal; } + Value *getUnderlyingValue() { return UnderlyingOrProducer.cast(); } + const Value *getUnderlyingValue() const { + return UnderlyingOrProducer.cast(); + } // Set \p Val as the underlying Value of this VPValue. void setUnderlyingValue(Value *Val) { - assert(!UnderlyingVal && "Underlying Value is already set."); - UnderlyingVal = Val; + assert(!UnderlyingOrProducer.cast() && + "Underlying Value is already set."); + UnderlyingOrProducer.set(Val); } public: @@ -80,14 +126,18 @@ /// type identification. enum { VPValueSC, + VPVirtualValueSC, + VPMultiValueSC, VPInstructionSC, VPMemoryInstructionSC, VPVWidenCallSC, VPVWidenSelectSC, - VPVWidenGEPSC + VPVWidenGEPSC, + VPVInterleaveSC }; VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {} + VPValue(VPValue *Base) : VPValue(VPValueSC, Base) {} VPValue(const VPValue &) = delete; VPValue &operator=(const VPValue &) = delete; @@ -103,7 +153,11 @@ void dump() const; unsigned getNumUsers() const { return Users.size(); } - void addUser(VPUser &User) { Users.push_back(&User); } + void addUser(VPUser &User) { + Users.push_back(&User); + if (isSubValue()) + getDefiningValue()->Users.push_back(&User); + } /// Remove a single \p User from the list of users. void removeUser(VPUser &User) { @@ -119,6 +173,10 @@ } return false; }); + + // For sub-values, also update the users of the defining value. + if (isSubValue()) + getDefiningValue()->removeUser(User); } typedef SmallVectorImpl::iterator user_iterator; @@ -148,8 +206,24 @@ } void replaceAllUsesWith(VPValue *New); + + VPValue *getDefiningValue() { return UnderlyingOrProducer.cast(); } + VPValue const *getDefiningValue() const { + return UnderlyingOrProducer.cast(); + } + + bool isConcrete() const { return !isSubValue() && !isVirtual(); } + + bool isSubValue() const { return UnderlyingOrProducer.is(); } + + bool isVirtual() const { return getVPValueID() == VPVirtualValueSC; } }; +// Check size assertions made in the PointerLikeTypeTraits specialization for +// VPValue *. +static_assert(detail::ConstantLog2::value >= 2, + "alignment of VPValue is smaller than assumed above"); + typedef DenseMap Value2VPValueTy; typedef DenseMap VPValue2ValueTy; @@ -163,15 +237,21 @@ public: VPUser() {} VPUser(ArrayRef Operands) { - for (VPValue *Operand : Operands) + for (VPValue *Operand : Operands) { + assert(!Operand->isVirtual() && + "cannot use a virtual VPValue as operand"); addOperand(Operand); + } } VPUser(std::initializer_list Operands) : VPUser(ArrayRef(Operands)) {} template VPUser(iterator_range Operands) { - for (VPValue *Operand : Operands) + for (VPValue *Operand : Operands) { + assert(!Operand->isVirtual() && + "cannot use a virtual VPValue as operand"); addOperand(Operand); + } } VPUser(const VPUser &) = delete; @@ -182,6 +262,7 @@ } void addOperand(VPValue *Operand) { + assert(!Operand->isVirtual() && "cannot use a virtual VPValue as operand"); Operands.push_back(Operand); Operand->addUser(*this); } @@ -193,6 +274,7 @@ } void setOperand(unsigned I, VPValue *New) { + assert(!New->isVirtual() && "cannot use a virtual VPValue as operand"); Operands[I]->removeUser(*this); Operands[I] = New; New->addUser(*this); diff --git a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp --- a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp +++ b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp @@ -521,5 +521,54 @@ delete Load; } +struct VPTestMultiValueDef : public VPUser, public VPValue { + SmallVector Defs; + + VPTestMultiValueDef() : VPValue(VPValue::VPVirtualValueSC) {} +}; + +TEST(VPMultiValueTest, traverseUseLists) { + // Check that the def-use chains of a multi-def can be traversed in both + // directions. + + // Create a multi-value def which defines 2 values. + VPTestMultiValueDef MultiDef; + MultiDef.Defs.push_back(new VPValue(&MultiDef)); + MultiDef.Defs.push_back(new VPValue(&MultiDef)); + + VPInstruction I1(1, {MultiDef.Defs[0], MultiDef.Defs[1]}); + VPInstruction I2(2, {MultiDef.Defs[0]}); + VPInstruction I3(3, {MultiDef.Defs[1]}); + + // Check that we can get all users of all definitions in the multi-value. + SmallVector MultiDefUsers(MultiDef.user_begin(), + MultiDef.user_end()); + // Note: Currently users may contain duplicates! + EXPECT_EQ(4u, MultiDefUsers.size()); + EXPECT_EQ(&I1, MultiDefUsers[0]); + EXPECT_EQ(&I1, MultiDefUsers[1]); + EXPECT_EQ(&I2, MultiDefUsers[2]); + EXPECT_EQ(&I3, MultiDefUsers[3]); + + SmallVector MultiDefV0Users(MultiDef.Defs[0]->user_begin(), + MultiDef.Defs[0]->user_end()); + EXPECT_EQ(2u, MultiDefV0Users.size()); + EXPECT_EQ(&I1, MultiDefV0Users[0]); + EXPECT_EQ(&I2, MultiDefV0Users[1]); + + SmallVector MultiDefV1Users(MultiDef.Defs[1]->user_begin(), + MultiDef.Defs[1]->user_end()); + EXPECT_EQ(2u, MultiDefV1Users.size()); + EXPECT_EQ(&I1, MultiDefV1Users[0]); + EXPECT_EQ(&I3, MultiDefV1Users[1]); + + // Now check that we can get the right defining value for each multi-value + // handed out. + EXPECT_EQ(&MultiDef, I1.getOperand(0)->getDefiningValue()); + EXPECT_EQ(&MultiDef, I1.getOperand(1)->getDefiningValue()); + EXPECT_EQ(&MultiDef, I2.getOperand(0)->getDefiningValue()); + EXPECT_EQ(&MultiDef, I3.getOperand(0)->getDefiningValue()); +} + } // namespace } // namespace llvm