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
@@ -78,6 +78,7 @@
   /// type identification.
   enum {
     VPValueSC,
+    VPMultiValueSC,
     VPInstructionSC,
     VPMemoryInstructionSC,
     VPVWidenCallSC,
@@ -88,18 +89,22 @@
   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;
@@ -130,6 +135,29 @@
   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;
 
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
@@ -247,5 +247,52 @@
   }
 }
 
+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