[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 ↗

(On Diff #484706)

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

209–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).

237–238

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 ↗

(On Diff #484706)

Done, thanks!

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

209–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.

237–238

Done, thanks!

[Ayal]

Ship it!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9165 ↗

(On Diff #491770)

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

9165 ↗

(On Diff #491770)

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/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))
+        // TODO: check dominance of incoming values for phis properly.
+        if (!UI || isa<VPHeaderPHIRecipe>(UI) || isa<VPPredInstPHIRecipe>(UI))
           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";
           return false;
         }
       }
     }
   }
   return true;
 }
 
 bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
-  DenseMap<const VPBlockBase *, unsigned> BlockNumbering;
-  unsigned Cnt = 0;
+  VPDominatorTree VPDT;
+  VPDT.recalculate(const_cast<VPlan &>(Plan));
+
   auto Iter = vp_depth_first_deep(Plan.getEntry());
-  for (const VPBlockBase *VPB : Iter) {
-    BlockNumbering[VPB] = Cnt++;
-    auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
-    if (!VPBB)
-      continue;
-    if (!verifyVPBasicBlock(VPBB, BlockNumbering))
+  for (const VPBasicBlock *VPBB :
+       VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
+    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;

llvm/unittests/Transforms/Vectorize/VPlanVerifierTest.cpp

TEST(VPVerifierTest, VPInstructionUseBeforeDefDifferentBB) {
   VPBB2->appendRecipe(BranchOnCond);
 
   VPRegionBlock *R1 = new VPRegionBlock(VPBB2, VPBB2, "R1");
   VPBlockUtils::connectBlocks(VPBB1, R1);
 
   VPlan Plan;
   Plan.setEntry(VPBB1);
 
-  // TODO: UseI uses DefI but DefI does not dominate UseI. Currently missed by
-  // the verifier.
 #if GTEST_HAS_STREAM_REDIRECTION
   ::testing::internal::CaptureStderr();
 #endif
-  EXPECT_TRUE(VPlanVerifier::verifyPlanIsValid(Plan));
+  EXPECT_FALSE(VPlanVerifier::verifyPlanIsValid(Plan));
 #if GTEST_HAS_STREAM_REDIRECTION
-  EXPECT_STREQ("", ::testing::internal::GetCapturedStderr().c_str());
+  EXPECT_STREQ("Use before def!\n",
+               ::testing::internal::GetCapturedStderr().c_str());
 #endif
 }
 
 TEST(VPVerifierTest, VPBlendUseBeforeDefDifferentBB) {
   LLVMContext C;
   IntegerType *Int32 = IntegerType::get(C, 32);
   auto *Phi = PHINode::Create(Int32, 1);
 
TEST(VPVerifierTest, VPBlendUseBeforeDefDifferentBB) {
   VPBlockUtils::connectBlocks(VPBB2, VPBB3);
   VPBlockUtils::connectBlocks(VPBB3, VPBB4);
   VPRegionBlock *R1 = new VPRegionBlock(VPBB2, VPBB4, "R1");
   VPBlockUtils::connectBlocks(VPBB1, R1);
 
   VPlan Plan;
   Plan.setEntry(VPBB1);
 
-  // TODO: Blend uses Def but Def does not dominate Blend. Currently missed by
-  // the verifier.
 #if GTEST_HAS_STREAM_REDIRECTION
   ::testing::internal::CaptureStderr();
 #endif
-  EXPECT_TRUE(VPlanVerifier::verifyPlanIsValid(Plan));
+  EXPECT_FALSE(VPlanVerifier::verifyPlanIsValid(Plan));
 #if GTEST_HAS_STREAM_REDIRECTION
-  EXPECT_STREQ("", ::testing::internal::GetCapturedStderr().c_str());
+  EXPECT_STREQ("Use before def!\n",
+               ::testing::internal::GetCapturedStderr().c_str());
 #endif
 
   delete Phi;
 }
 } // namespace