diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
--- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -9560,6 +9560,7 @@
   RSO.flush();
   Plan->setName(PlanName);
 
+  assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
   return Plan;
 }
 
diff --git a/llvm/lib/Transforms/Vectorize/VPlanVerifier.h b/llvm/lib/Transforms/Vectorize/VPlanVerifier.h
--- a/llvm/lib/Transforms/Vectorize/VPlanVerifier.h
+++ b/llvm/lib/Transforms/Vectorize/VPlanVerifier.h
@@ -26,6 +26,7 @@
 
 namespace llvm {
 class VPRegionBlock;
+class VPlan;
 
 /// Struct with utility functions that can be used to check the consistency and
 /// invariants of a VPlan, including the components of its H-CFG.
@@ -35,6 +36,12 @@
   /// 1. Region/Block verification: Check the Region/Block verification
   /// invariants for every region in the H-CFG.
   void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const;
+
+  /// Verify invariants for general VPlans. Currently it checks the following:
+  /// 1. all phi-like recipes must be at the beginning of a block, with no other
+  /// recipes in between. Note that currently there is still an exception for
+  /// VPBlendRecipes.
+  static bool verifyPlanIsValid(const VPlan &Plan);
 };
 } // namespace llvm
 
diff --git a/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp b/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
--- a/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
+++ b/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
@@ -128,3 +128,29 @@
   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
   verifyRegionRec(TopRegion);
 }
+
+bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
+  auto Iter = depth_first(
+      VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
+  for (const VPBasicBlock *VPBB :
+       VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
+    // Verify that phi-like recipes are at the beginning of the block, with no
+    // other recipes in between.
+    auto RecipeI = VPBB->begin();
+    auto End = VPBB->end();
+    while (RecipeI != End && RecipeI->isPhi())
+      RecipeI++;
+
+    while (RecipeI != End) {
+      if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
+        errs() << "Found phi-like recipe after non-phi recipe:";
+        RecipeI->dump();
+        errs() << "after\n";
+        std::prev(RecipeI)->dump();
+        return false;
+      }
+      RecipeI++;
+    }
+  }
+  return true;
+}