[VPlan] Use VPDominatorTree in VPlanVerifier .

[fhahn]

Summary

Use VPDominatorTree to generalize def-use verification.

Depends on D140513.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9164

nit: can alternatively have the verifier construct a dominator tree? Once one is used for non-verification purposes, it could be passed in, to save a recalculation.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

210

Blend recipe should adhere to def-before-use?
PredInstPHI should be considered a header phi?
Worth having a test to check the verifier?

216

nit: can early-continue (independent of this patch).

243

nit: can use utils to iterate over basic blocks only, now that regions needs not be assigned numbers.

[fhahn]

Rebased on top of new unit tests (dc8e2ea92953a6) and addressed comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9164

Done, thanks!

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

210

Blend recipe should adhere to def-before-use?

Yep, updated the condition to not skip blend recipes

PredInstPHI should be considered a header phi?

Not sure if it makes sense to classify PredInstPHI as header-phi, but the verifier needs extending so to check the incoming values dominate the end of the incoming block. Will put up a patch for that separately.

Worth having a test to check the verifier?

Added initial tests in dc8e2ea9 and update the patch to show improvements.

216

I kept the order for now as is, so the check directly relates to the error message.

226

I removed that unrelated change from the diff, will submit a separate patch for that.

243

Done, thanks!

[Ayal]

Ship it!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9161

nit: can be done independent of this patch.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

212

nit: can introduce a method that takes two recipes (along with their numberings) and says if one dominates the other, whether they belong to the same VPBB's or not. Analogous to DominatorTree interfaces.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9161

It's not needed any longer now that the VPDominatorTree is computed inside the call. I'll remove it.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

212

That would indeed be a useful utility. I'll prepare that separately.

[fhahn]

rebase before landing.

[fhahn]

Remove unnecessary ifdef change.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   VPlanTransforms::mergeReplicateRegions(*Plan);
   VPlanTransforms::removeRedundantExpandSCEVRecipes(*Plan);
 
   // Fold Exit block into its predecessor if possible.
   // TODO: Fold block earlier once all VPlan transforms properly maintain a
   // 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;
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Outer loop handling: They may require CFG and instruction level
   // transformations before even evaluating whether vectorization is profitable.
   // Since we cannot modify the incoming IR, we need to build VPlan upfront in
   // the vectorization pipeline.

llvm/lib/Transforms/Vectorize/VPlanVerifier.h

 ///   - All predecessors/successors of a block must belong to the same region.
 ///   - Blocks must have no duplicated successor/predecessor.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H
 
+#include "VPlanDominatorTree.h"
+
 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.
 struct VPlanVerifier {
   /// Verify the invariants of the H-CFG starting from \p TopRegion. The
   /// verification process comprises the following steps:
   /// 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);
+  static bool verifyPlanIsValid(const VPlan &Plan, VPDominatorTree &VPDT);
 };
 } // namespace llvm
 
 #endif //LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

 /// This file defines the class VPlanVerifier, which contains utility functions
 /// to check the consistency and invariants of a VPlan.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "VPlanVerifier.h"
 #include "VPlan.h"
 #include "VPlanCFG.h"
+#include "VPlanDominatorTree.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/Support/CommandLine.h"
 
 #define DEBUG_TYPE "loop-vectorize"
 
 using namespace llvm;
 
 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),

 #endif
       return false;
     }
     RecipeI++;
   }
   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;
 
   // Verify that defs in VPBB dominate all their uses. The current
   // implementation is still incomplete.
   DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
   unsigned Cnt = 0;
   for (const VPRecipeBase &R : *VPBB)
     RecipeNumbering[&R] = Cnt++;
 
   for (const VPRecipeBase &R : *VPBB) {
     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
         // block.
         if (UI->getParent() == VPBB) {
           if (RecipeNumbering[UI] < RecipeNumbering[&R]) {
             errs() << "Use before def!\n";
             return false;
           }
           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;
         }
       }
     }
   }
   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;
   }
 
   const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
   const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
   if (!Entry) {
     errs() << "VPlan entry block is not a VPBasicBlock\n";
     return false;