Index: lib/Transforms/Vectorize/CMakeLists.txt
===================================================================
--- lib/Transforms/Vectorize/CMakeLists.txt
+++ lib/Transforms/Vectorize/CMakeLists.txt
@@ -6,6 +6,7 @@
   Vectorize.cpp
   VPlan.cpp
   VPlanHCFGBuilder.cpp
+  VPlanHCFGTransforms.cpp
   VPlanVerifier.cpp
 
   ADDITIONAL_HEADER_DIRS
Index: lib/Transforms/Vectorize/VPlanHCFGTransforms.h
===================================================================
--- /dev/null
+++ lib/Transforms/Vectorize/VPlanHCFGTransforms.h
@@ -0,0 +1,38 @@
+//===- VPlanHCFGTransfroms.h - Utility VPlan to VPlan transforms ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file provides utility VPlan to VPlan transformations.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANHCFGTRANSFORMS_H
+#define LLVM_TRANSFORMS_VECTORIZE_VPLANHCFGTRANSFORMS_H
+
+#include "LoopVectorizationPlanner.h"
+#include "VPlan.h"
+#include "llvm/IR/Instruction.h"
+
+namespace llvm {
+
+class VPlanHCFGTransforms {
+  using VPlanPtr = std::unique_ptr<VPlan>;
+
+public:
+  /// Sinks instructions in \p Plan, depending on their underlying values in
+  /// \p SinkAfter.
+  // FIXME: Migrate to using a VPlan based mapping, once
+  // LoopVectorizationLegality::getSinkAfter is moved to VPlan.
+  static void
+  sinkInstructions(VPlanPtr &Plan,
+                   DenseMap<Instruction *, Instruction *> &SinkAfter);
+};
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANHCFGTRANSFORMS_H
Index: lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp
===================================================================
--- /dev/null
+++ lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp
@@ -0,0 +1,57 @@
+//===-- VPlanHCFGTransforms.cpp -------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file implements a set of utility VPlan to VPlan transformations.
+///
+//===----------------------------------------------------------------------===//
+
+#include "VPlanHCFGTransforms.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "loop-vectorize"
+
+void VPlanHCFGTransforms::sinkInstructions(
+    VPlanPtr &Plan, DenseMap<Instruction *, Instruction *> &SinkAfter) {
+  DenseMap<Instruction *, VPInstruction *> SinkAfterInverse;
+  VPRegionBlock *TopRegion = dyn_cast<VPRegionBlock>(Plan->getEntry());
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
+  for (VPBlockBase *Base : RPOT) {
+    VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
+    for (VPRecipeBase &Ingredient : *OriginalVPBB) {
+      VPInstruction *VPInst = dyn_cast<VPInstruction>(&Ingredient);
+      if (!VPInst)
+        continue;
+
+      Instruction *Instr = dyn_cast<Instruction>(VPInst->getUnderlyingValue());
+      assert(Instr && "Need Instruction as underlying value");
+
+      // Move instructions to handle first-order recurrences, step 1: avoid
+      // handling this instruction until after we've handled the instruction it
+      // should follow.
+      auto SAIt = SinkAfter.find(Instr);
+      if (SAIt != SinkAfter.end()) {
+        LLVM_DEBUG(dbgs() << "Sinking" << *SAIt->first << " after"
+                          << *SAIt->second
+                          << " to vectorize a 1st order recurrence.\n");
+        SinkAfterInverse[SAIt->second] = VPInst;
+        continue;
+      }
+
+      // Move instructions to handle first-order recurrences, step 2: push the
+      // instruction to be sunk at its insertion point.
+      auto SAInvIt = SinkAfterInverse.find(Instr);
+      if (SAInvIt != SinkAfterInverse.end())
+        SAInvIt->second->moveAfter(VPInst);
+    }
+  }
+}
Index: lib/Transforms/Vectorize/VPlanValue.h
===================================================================
--- lib/Transforms/Vectorize/VPlanValue.h
+++ lib/Transforms/Vectorize/VPlanValue.h
@@ -38,6 +38,8 @@
 // and live-outs which the VPlan will need to fix accordingly.
 class VPValue {
   friend class VPBuilder;
+  friend class VPlanHCFGTransforms;
+
 private:
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
Index: unittests/Transforms/Vectorize/VPlanTest.cpp
===================================================================
--- unittests/Transforms/Vectorize/VPlanTest.cpp
+++ unittests/Transforms/Vectorize/VPlanTest.cpp
@@ -8,6 +8,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "../lib/Transforms/Vectorize/VPlan.h"
+#include "../lib/Transforms/Vectorize/VPlanHCFGTransforms.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
 #include "gtest/gtest.h"
 
 namespace llvm {
@@ -48,5 +51,46 @@
   CHECK_ITERATOR(VPBB2, I4, I3, I5);
 }
 
+TEST(VPInstructionTest, sinkInstructions) {
+  // Create some dummy instructions, we need those for the SinkAfter mapping.
+  LLVMContext Context;
+  Value *V = new Argument(Type::getInt32Ty(Context));
+  Instruction *I1 = BinaryOperator::Create(Instruction::Add, V, V);
+  Instruction *I2 = BinaryOperator::Create(Instruction::Add, I1, V);
+  Instruction *I3 = BinaryOperator::Create(Instruction::Add, I2, V);
+  Instruction *I4 = BinaryOperator::Create(Instruction::Add, I3, V);
+  Instruction *I5 = BinaryOperator::Create(Instruction::Add, I4, V);
+
+  VPBuilder Builder;
+
+  VPBasicBlock *VPBB1 = new VPBasicBlock();
+  Builder.setInsertPoint(VPBB1);
+  VPInstruction *VI1 = dyn_cast<VPInstruction>(Builder.createNaryOp(1, {}, I1));
+  VPInstruction *VI2 = dyn_cast<VPInstruction>(Builder.createNaryOp(2, {}, I2));
+  VPInstruction *VI3 = dyn_cast<VPInstruction>(Builder.createNaryOp(3, {}, I3));
+
+  VPBasicBlock *VPBB2 = new VPBasicBlock();
+  Builder.setInsertPoint(VPBB2);
+  VPInstruction *VI4 = dyn_cast<VPInstruction>(Builder.createNaryOp(4, {}, I4));
+  VPInstruction *VI5 = dyn_cast<VPInstruction>(Builder.createNaryOp(5, {}, I5));
+
+  VPBB1->setOneSuccessor(VPBB2);
+
+  VPRegionBlock *TopRegion =
+      new VPRegionBlock("TopRegion", false /*isReplicator*/);
+  TopRegion->setEntry(VPBB1);
+  TopRegion->setExit(VPBB2);
+  auto Plan = llvm::make_unique<VPlan>(TopRegion);
+
+  DenseMap<Instruction *, Instruction *> SinkAfter;
+  SinkAfter[I1] = I3;
+  SinkAfter[I2] = I4;
+
+  VPlanHCFGTransforms::sinkInstructions(Plan, SinkAfter);
+
+  CHECK_ITERATOR((*VPBB1), VI3, VI1);
+  CHECK_ITERATOR((*VPBB2), VI4, VI2, VI5);
+}
+
 } // namespace
 } // namespace llvm