From b6b3d20d06987d33f18a68c02dfefc792d1b0b01 Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Wed, 25 Jan 2023 16:32:40 +0000
Subject: [PATCH] [VPlan] Use VPDominatorTree in VPlanVerifier .

Use VPDominatorTree to generalize def-use verification.

Depends on D140513.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D140514
---
 .../Transforms/Vectorize/VPlanVerifier.cpp    | 45 +++++--------------
 .../Vectorize/VPlanVerifierTest.cpp           | 14 +++---
 2 files changed, 18 insertions(+), 41 deletions(-)

diff --git a/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp b/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
index 18125cebed33..d6b81543dbc9 100644
--- 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"
 
@@ -189,9 +190,8 @@ static bool verifyPhiRecipes(const VPBasicBlock *VPBB) {
   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;
 
@@ -206,7 +206,8 @@ verifyVPBasicBlock(const VPBasicBlock *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
@@ -219,27 +220,7 @@ verifyVPBasicBlock(const VPBasicBlock *VPBB,
           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;
         }
@@ -250,15 +231,13 @@ verifyVPBasicBlock(const VPBasicBlock *VPBB,
 }
 
 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;
   }
 
diff --git a/llvm/unittests/Transforms/Vectorize/VPlanVerifierTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanVerifierTest.cpp
index 7c252cf2c4fb..516d1142daf8 100644
--- a/llvm/unittests/Transforms/Vectorize/VPlanVerifierTest.cpp
+++ b/llvm/unittests/Transforms/Vectorize/VPlanVerifierTest.cpp
@@ -57,14 +57,13 @@ TEST(VPVerifierTest, VPInstructionUseBeforeDefDifferentBB) {
   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
 }
 
@@ -99,14 +98,13 @@ TEST(VPVerifierTest, VPBlendUseBeforeDefDifferentBB) {
   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;
-- 
2.34.1