diff --git a/llvm/lib/Transforms/Vectorize/VPlan.h b/llvm/lib/Transforms/Vectorize/VPlan.h
--- a/llvm/lib/Transforms/Vectorize/VPlan.h
+++ b/llvm/lib/Transforms/Vectorize/VPlan.h
@@ -579,6 +579,9 @@
     // All VPDefs are also VPRecipeBases.
     return true;
   }
+
+  /// Clone this recipe.
+  virtual VPRecipeBase *clone() = 0;
 };
 
 inline bool VPUser::classof(const VPDef *Def) {
@@ -643,9 +646,11 @@
     return V->getVPValueID() == VPValue::VPVInstructionSC;
   }
 
-  VPInstruction *clone() const {
+  VPRecipeBase *clone() override {
     SmallVector<VPValue *, 2> Operands(operands());
-    return new VPInstruction(Opcode, Operands);
+    VPInstruction *NewI = new VPInstruction(Opcode, Operands);
+    NewI->setUnderlyingValue(getUnderlyingValue());
+    return NewI;
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
@@ -722,6 +727,11 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  /// Clone the recipe.
+  VPRecipeBase *clone() override {
+    return new VPWidenRecipe(*getUnderlyingInstr(), operands());
+  }
 };
 
 /// A recipe for widening Call instructions.
@@ -746,6 +756,12 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  /// Clone the recipe.
+  VPRecipeBase *clone() override {
+    return new VPWidenCallRecipe(*cast<CallInst>(getUnderlyingInstr()),
+                                 operands());
+  }
 };
 
 /// A recipe for widening select instructions.
@@ -775,6 +791,12 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  /// Clone the recipe.
+  VPRecipeBase *clone() override {
+    return new VPWidenSelectRecipe(*cast<SelectInst>(getUnderlyingInstr()),
+                                   operands(), InvariantCond);
+  }
 };
 
 /// A recipe for handling GEP instructions.
@@ -782,6 +804,14 @@
   bool IsPtrLoopInvariant;
   SmallBitVector IsIndexLoopInvariant;
 
+  template <typename IterT>
+  VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands,
+                   bool IsPtrLoopInvariant, SmallBitVector IsIndexLoopInvariant)
+      : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands),
+        VPValue(VPWidenGEPSC, GEP, this),
+        IsPtrLoopInvariant(IsPtrLoopInvariant),
+        IsIndexLoopInvariant(IsIndexLoopInvariant) {}
+
 public:
   template <typename IterT>
   VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands)
@@ -813,6 +843,13 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  /// Clone the recipe.
+  VPRecipeBase *clone() override {
+    return new VPWidenGEPRecipe(cast<GetElementPtrInst>(getUnderlyingInstr()),
+                                operands(), IsPtrLoopInvariant,
+                                IsIndexLoopInvariant);
+  }
 };
 
 /// A recipe for handling phi nodes of integer and floating-point inductions,
@@ -867,6 +904,15 @@
   const TruncInst *getTruncInst() const {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
+
+  /// Clone the recipe.
+  VPRecipeBase *clone() override {
+    VPValue *CastV = getCastValue();
+    return new VPWidenIntOrFpInductionRecipe(
+        IV, getStartValue(),
+        CastV ? cast<Instruction>(CastV->getUnderlyingValue()) : nullptr,
+        getTruncInst());
+  }
 };
 
 /// A recipe for handling all phi nodes except for integer and FP inductions.
@@ -927,6 +973,17 @@
 
   /// Returns the \p I th incoming VPBasicBlock.
   VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; }
+
+  /// Clone the recipe.
+  VPRecipeBase *clone() override {
+    PHINode *Phi = cast<PHINode>(getUnderlyingValue());
+    if (RdxDesc)
+      return new VPWidenPHIRecipe(Phi, *RdxDesc, *getStartValue());
+    VPWidenPHIRecipe *VPhi = new VPWidenPHIRecipe(Phi);
+    for (unsigned I = 0, E = IncomingBlocks.size(); I != E; ++I)
+      VPhi->addIncoming(getIncomingValue(I), getIncomingBlock(I));
+    return VPhi;
+  }
 };
 
 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
@@ -968,6 +1025,11 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
@@ -1033,6 +1095,11 @@
              VPSlotTracker &SlotTracker) const override;
 
   const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; }
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return new VPInterleaveRecipe(IG, getAddr(), {}, getMask());
+  }
 };
 
 /// A recipe to represent inloop reduction operations, performing a reduction on
@@ -1080,6 +1147,11 @@
   VPValue *getCondOp() const {
     return getNumOperands() > 2 ? getOperand(2) : nullptr;
   }
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
@@ -1135,6 +1207,11 @@
   bool isUniform() const { return IsUniform; }
 
   bool isPacked() const { return AlsoPack; }
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// A recipe for generating conditional branches on the bits of a mask.
@@ -1173,6 +1250,11 @@
     // Mask is optional.
     return getNumOperands() == 1 ? getOperand(0) : nullptr;
   }
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
@@ -1200,6 +1282,11 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// A Recipe for widening load/store operations.
@@ -1267,6 +1354,11 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// A Recipe for widening the canonical induction variable of the vector loop.
@@ -1291,6 +1383,11 @@
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  VPRecipeBase *clone() override {
+    // FIXME!
+    return nullptr;
+  }
 };
 
 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It