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
@@ -9158,7 +9158,11 @@
   // VPBasicBlock as exit.
   VPBlockUtils::tryToMergeBlockIntoPredecessor(TopRegion->getExiting());
 
-  assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
+#ifndef NDEBUG
+  VPDominatorTree VPDT;
+  VPDT.recalculate(*Plan);
+  assert(VPlanVerifier::verifyPlanIsValid(*Plan, VPDT) && "VPlan is invalid");
+#endif
   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
@@ -24,6 +24,8 @@
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H
 
+#include "VPlanDominatorTree.h"
+
 namespace llvm {
 class VPRegionBlock;
 class VPlan;
@@ -41,7 +43,7 @@
   /// 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);
+  static bool verifyPlanIsValid(const VPlan &Plan, VPDominatorTree &VPDT);
 };
 } // 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
@@ -15,6 +15,7 @@
 #include "VPlanVerifier.h"
 #include "VPlan.h"
 #include "VPlanCFG.h"
+#include "VPlanDominatorTree.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/Support/CommandLine.h"
 
@@ -190,9 +191,8 @@
   return true;
 }
 
-static bool
-verifyVPBasicBlock(const VPBasicBlock *VPBB,
-                   DenseMap<const VPBlockBase *, unsigned> &BlockNumbering) {
+static bool verifyVPBasicBlock(const VPBasicBlock *VPBB,
+                               VPDominatorTree &VPDT) {
   if (!verifyPhiRecipes(VPBB))
     return false;
 
@@ -207,7 +207,7 @@
     for (const VPValue *V : R.definedValues()) {
       for (const VPUser *U : V->users()) {
         auto *UI = dyn_cast<VPRecipeBase>(U);
-        if (!UI || isa<VPHeaderPHIRecipe>(UI))
+        if (!UI || UI->isPhi())
           continue;
 
         // If the user is in the same block, check it comes after R in the
@@ -220,28 +220,13 @@
           continue;
         }
 
-        // Skip blocks outside any region for now and blocks outside
-        // replicate-regions.
-        auto *ParentR = VPBB->getParent();
-        if (!ParentR || !ParentR->isReplicator())
-          continue;
-
-        // For replicators, verify that VPPRedInstPHIRecipe defs are only used
-        // in subsequent blocks.
-        if (isa<VPPredInstPHIRecipe>(&R)) {
-          auto I = BlockNumbering.find(UI->getParent());
-          unsigned BlockNumber = I == BlockNumbering.end() ? std::numeric_limits<unsigned>::max() : I->second;
-          if (BlockNumber < BlockNumbering[ParentR]) {
-            errs() << "Use before def!\n";
-            return false;
-          }
-          continue;
-        }
-
-        // All non-VPPredInstPHIRecipe recipes in the block must be used in
-        // the replicate region only.
-        if (UI->getParent()->getParent() != ParentR) {
+        if (!VPDT.dominates(VPBB, UI->getParent())) {
           errs() << "Use before def!\n";
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+          UI->dump();
+          errs() << "before\n";
+          R.dump();
+#endif
           return false;
         }
       }
@@ -250,17 +235,15 @@
   return true;
 }
 
-bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
-  DenseMap<const VPBlockBase *, unsigned> BlockNumbering;
-  unsigned Cnt = 0;
+bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan,
+                                      VPDominatorTree &VPDT) {
   auto Iter = depth_first(
       VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
   for (const VPBlockBase *VPB : Iter) {
-    BlockNumbering[VPB] = Cnt++;
     auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
     if (!VPBB)
       continue;
-    if (!verifyVPBasicBlock(VPBB, BlockNumbering))
+    if (!verifyVPBasicBlock(VPBB, VPDT))
       return false;
   }