[VPlan] Add VPMultiValue.

[fhahn]

Summary

This patch adds a new VPMultiValue, which can be used to wrap a VPValue
from a producer that produces multiple values, like VPInterleaveRecipe,
which produces a value for each member in an interleave group.

Note that it would also be possible to model the results as sub-values
by creating concatenating all results and extracting the relevant parts.
However, this would mean that we need to create values that might not be
used in the end and make analysis more complicated than necessary.

This patch adds the notion of a 'defining value', which is the actual
instance producing the (multi) value. The defining value for regular
VPValues is the VPValue itself. VPMultiValues keep track of their
defining value. Currently the defining value is a VPValue to keep things
simple. In practice this means the producer of a multi-value needs to
inherit from VPValue itself. This VPValue should not be referenced by
any other VPValues and only acts as convenient way to access all users
of all VPMultiValues by the same defining value.

With this scheme, it is possible to traverse the def-use chains as
follows:

1. To walk upwards given a VP(Multi)Value, use getDefiningValue to get the producer. Use the operands of the producer to continue the walk upwards.

2. To walk downwards, just iterate over all users of the producer. This can be done by iterating over all users of all VPMultiValues of the producer. Given that the producer is a VPValue itself, all users of the individual VPMultiValues are added as users of the producer.

[fhahn]

Superseded by the VPDef approach as outlined in D90558

llvm/lib/Transforms/Vectorize/VPlanValue.h

 
 public:
   /// An enumeration for keeping track of the concrete subclass of VPValue that
   /// are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPValue objects. They are used for concrete
   /// type identification.
   enum {
     VPValueSC,
+    VPMultiValueSC,
     VPInstructionSC,
     VPMemoryInstructionSC,
     VPVWidenCallSC,
     VPVWidenSelectSC,
     VPVWidenGEPSC
   };
 
   VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
+  virtual ~VPValue() {}
 
   /// \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; }
 
+  virtual VPValue *getDefiningValue() { return this; }
+  virtual VPValue const *getDefiningValue() const { return this; }
+
   void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
   void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
   void dump() const;
 
   unsigned getNumUsers() const { return Users.size(); }
-  void addUser(VPUser &User) { Users.push_back(&User); }
+  virtual void addUser(VPUser &User) { Users.push_back(&User); }
 
   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() { return Users.begin(); }
   const_user_iterator user_begin() const { return Users.begin(); }
bool hasMoreThanOneUniqueUser() {
     while (Current != user_end() && *user_begin() == *Current)
       Current++;
     return Current != user_end();
   }
 
   void replaceAllUsesWith(VPValue *New);
 };
 
+/// This class can be used to reference a VPValue produced by a recipe that
+/// defines multiple VPValues.
+class VPMultiValue : public VPValue {
+  VPValue *DefiningValue;
+
+public:
+  VPMultiValue(VPValue *DefiningValue, Value *UV = nullptr)
+      : VPValue(VPValue::VPMultiValueSC, UV), DefiningValue(DefiningValue) {}
+  ~VPMultiValue() override {}
+
+  VPValue *getDefiningValue() override { return DefiningValue; }
+  VPValue const *getDefiningValue() const override { return DefiningValue; }
+
+  void addUser(VPUser &User) override {
+    VPValue::addUser(User);
+    DefiningValue->addUser(User);
+  }
+
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPMultiValueSC;
+  }
+};
+
 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
 
 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
 
 /// This class augments VPValue with operands which provide the inverse def-use
 /// edges from VPValue's users to their defs.
 class VPUser {

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

EXPECT_EQ(ExpectedStr, FullDump);
     std::string I4Dump;
     raw_string_ostream OS(I4Dump);
     OS << *I4;
     OS.flush();
     EXPECT_EQ("vp<%2> = mul vp<%1> vp<%0>", I4Dump);
   }
 }
 
+struct VPTestMultiValueDef : public VPUser, public VPValue {
+  SmallVector<VPMultiValue *, 4> Defs;
+};
+
+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 VPMultiValue(&MultiDef));
+  MultiDef.Defs.push_back(new VPMultiValue(&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<VPUser *, 4> 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<VPUser *, 4> 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<VPUser *, 4> 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