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
@@ -154,6 +154,11 @@
   A VPUser represents an entity that uses a number of VPValues as operands.
   VPUser is similar in some aspects to LLVM's User class.
 
+:VPDef:
+  A VPDef represents an entity that defines zero, one or multiple VPValues.
+  It is used to model the fact that recipes in VPlan can define multiple
+  VPValues.
+
 :VPInstruction:
   A VPInstruction is both a VPRecipe and a VPUser. It models a single
   VPlan-level instruction to be generated if the VPlan is executed, including
diff --git a/llvm/lib/Transforms/Vectorize/VPlan.cpp b/llvm/lib/Transforms/Vectorize/VPlan.cpp
--- a/llvm/lib/Transforms/Vectorize/VPlan.cpp
+++ b/llvm/lib/Transforms/Vectorize/VPlan.cpp
@@ -56,6 +56,18 @@
   return OS;
 }
 
+VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
+    : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
+  if (Def)
+    Def->addDefinedValue(this);
+}
+
+VPValue::~VPValue() {
+  assert(Users.empty() && "trying to delete a VPValue with remaining users");
+  if (Def)
+    Def->removeDefinedValue(this);
+}
+
 void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
   if (const VPInstruction *Instr = dyn_cast<VPInstruction>(this))
     Instr->print(OS, SlotTracker);
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
@@ -10,7 +10,7 @@
 /// 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
+/// VPValue   VPUser   VPDef
 ///    |        |
 ///   VPInstruction
 /// These are documented in docs/VectorizationPlan.rst.
@@ -21,7 +21,9 @@
 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/ADT/iterator_range.h"
 
 namespace llvm {
@@ -29,6 +31,7 @@
 // Forward declarations.
 class raw_ostream;
 class Value;
+class VPDef;
 class VPSlotTracker;
 class VPUser;
 class VPRecipeBase;
@@ -39,6 +42,7 @@
 // and live-outs which the VPlan will need to fix accordingly.
 class VPValue {
   friend class VPBuilder;
+  friend class VPDef;
   friend struct VPlanTransforms;
   friend class VPBasicBlock;
   friend class VPInterleavedAccessInfo;
@@ -53,8 +57,11 @@
   // Hold the underlying Value, if any, attached to this VPValue.
   Value *UnderlyingVal;
 
-  VPValue(const unsigned char SC, Value *UV = nullptr)
-      : SubclassID(SC), UnderlyingVal(UV) {}
+  /// Pointer to the VPDef that defines this VPValue. If it is nullptr, the
+  /// VPValue is not defined by any recipe modeled in VPlan.
+  VPDef *Def;
+
+  VPValue(const unsigned char SC, Value *UV = nullptr, VPDef *Def = nullptr);
 
   // 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
@@ -87,13 +94,12 @@
     VPVWidenGEPSC
   };
 
-  VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
+  VPValue(Value *UV = nullptr, VPDef *Def = nullptr)
+      : VPValue(VPValueSC, UV, Def) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
 
-  virtual ~VPValue() {
-    assert(Users.empty() && "trying to delete a VPValue with remaining users");
-  }
+  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
@@ -152,6 +158,8 @@
   }
 
   void replaceAllUsesWith(VPValue *New);
+
+  VPDef *getDef() { return Def; }
 };
 
 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
@@ -223,6 +231,65 @@
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPRecipeBase *Recipe);
 };
+
+/// 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 VPValue;
+
+  /// The VPValues defined by this VPDef.
+  TinyPtrVector<VPValue *> DefinedValues;
+
+  /// Add \p V as a defined value by this VPDef.
+  void addDefinedValue(VPValue *V) {
+    assert(V->getDef() == 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(VPValue *V) {
+    assert(V->getDef() == this &&
+           "can only remove VPValue linked with this VPDef");
+    assert(find(DefinedValues, V) != DefinedValues.end() &&
+           "VPValue to remove must be in DefinedValues");
+    erase_value(DefinedValues, V);
+    V->Def = nullptr;
+  }
+
+public:
+  virtual ~VPDef() {
+    for (VPValue *D : make_early_inc_range(DefinedValues)) {
+      assert(D->Def == this &&
+             "all defined VPValues should point to the containing VPDef");
+      assert(D->getNumUsers() == 0 &&
+             "all defined VPValues should have no more users");
+      D->Def = nullptr;
+      delete D;
+    }
+  }
+
+  /// Returns the VPValue with index \p I defined by the VPDef.
+  VPValue *getVPValue(unsigned I = 0) {
+    assert(DefinedValues[I] && "defined value must be non-null");
+    return DefinedValues[I];
+  }
+  const VPValue *getVPValue(unsigned I = 0) const {
+    assert(DefinedValues[I] && "defined value must be non-null");
+    return DefinedValues[I];
+  }
+
+  /// Returns an ArrayRef of the values defined by the VPDef.
+  ArrayRef<VPValue *> definedValues() { return DefinedValues; }
+
+  /// Returns the number of values defined by the VPDef.
+  unsigned getNumDefinedValues() const { return DefinedValues.size(); }
+};
+
 class VPlan;
 class VPBasicBlock;
 class VPRegionBlock;
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,56 @@
   delete Load;
 }
 
+struct VPDoubleValueDef : public VPUser, public VPDef {
+  VPDoubleValueDef(ArrayRef<VPValue *> Operands) : VPUser(Operands), VPDef() {
+    new VPValue(nullptr, this);
+    new VPValue(nullptr, this);
+  }
+};
+
+TEST(VPDoubleValueDefTest, traverseUseLists) {
+  // Check that the def-use chains of a multi-def can be traversed in both
+  // directions.
+
+  // Create a new VPDef which defines 2 values and has 2 operands.
+  VPInstruction Op0(20, {});
+  VPInstruction Op1(30, {});
+  VPDoubleValueDef DoubleValueDef({&Op0, &Op1});
+
+  // Create a new users of the defined values.
+  VPInstruction I1(
+      1, {DoubleValueDef.getVPValue(0), DoubleValueDef.getVPValue(1)});
+  VPInstruction I2(2, {DoubleValueDef.getVPValue(0)});
+  VPInstruction I3(3, {DoubleValueDef.getVPValue(1)});
+
+  // Check operands of the VPDef (traversing upwards).
+  SmallVector<VPValue *, 4> DoubleOperands(DoubleValueDef.op_begin(),
+                                           DoubleValueDef.op_end());
+  EXPECT_EQ(2u, DoubleOperands.size());
+  EXPECT_EQ(&Op0, DoubleOperands[0]);
+  EXPECT_EQ(&Op1, DoubleOperands[1]);
+
+  // Check users of the defined values (traversing downwards).
+  SmallVector<VPUser *, 4> DoubleValueDefV0Users(
+      DoubleValueDef.getVPValue(0)->user_begin(),
+      DoubleValueDef.getVPValue(0)->user_end());
+  EXPECT_EQ(2u, DoubleValueDefV0Users.size());
+  EXPECT_EQ(&I1, DoubleValueDefV0Users[0]);
+  EXPECT_EQ(&I2, DoubleValueDefV0Users[1]);
+
+  SmallVector<VPUser *, 4> DoubleValueDefV1Users(
+      DoubleValueDef.getVPValue(1)->user_begin(),
+      DoubleValueDef.getVPValue(1)->user_end());
+  EXPECT_EQ(2u, DoubleValueDefV1Users.size());
+  EXPECT_EQ(&I1, DoubleValueDefV1Users[0]);
+  EXPECT_EQ(&I3, DoubleValueDefV1Users[1]);
+
+  // Now check that we can get the right VPDef for each defined value.
+  EXPECT_EQ(&DoubleValueDef, I1.getOperand(0)->getDef());
+  EXPECT_EQ(&DoubleValueDef, I1.getOperand(1)->getDef());
+  EXPECT_EQ(&DoubleValueDef, I2.getOperand(0)->getDef());
+  EXPECT_EQ(&DoubleValueDef, I3.getOperand(0)->getDef());
+}
+
 } // namespace
 } // namespace llvm