[VPlan] Add initial VPlan verification.

[fhahn]

Summary

This patch adds a function to verify general properties of VPlans. The
first check makes sure that all phi-like recipes are at the beginning of
a block, with no other recipes in between.

Note that this currently may not hold for VPBlendRecipes at the moment,
as other recipes may be inserted before the VPBlendRecipe during mask
creation.

Note that this patch depends on D111300 and D111301, which fix code that
breaks the checked invariant.

[Ayal]

Looks good to me, thanks!
Perhaps also worth checking that all header-phi recipes reside in the header?

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

148

worth spelling out the offenders?

[fhahn]

In D111302#3085781, @Ayal wrote:

Looks good to me, thanks!
Perhaps also worth checking that all header-phi recipes reside in the header?

That sounds like a good idea. I'll put up a follow-up patch, to keep the patches smaller in case they highlight any issues.

[Ayal]

Thanks for pushing this forward!

Wondering about:

/// Note that currently there is still an exception for VPBlendRecipes.

// FIXME: At the moment, creating a mask might insert non-phi recipes before VPBlendRecipes.

VPBlendRecipes are indeed exceptional (not only currently?), as they represent a 'select' rather than a 'phi'. Is the FIXME needed?

[akuegel]

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

147

The dump() method is not necessarily available, it is guarded by:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

You should guard the calls to it in the same way.

[fhahn]

In D111302#3117711, @Ayal wrote:

Thanks for pushing this forward!

Wondering about:

/// Note that currently there is still an exception for VPBlendRecipes.

// FIXME: At the moment, creating a mask might insert non-phi recipes before VPBlendRecipes.

VPBlendRecipes are indeed exceptional (not only currently?), as they represent a 'select' rather than a 'phi'. Is the FIXME needed?

Good point, I removed the fixme in the committed version.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

147

Thanks, this should already be fixed by acbefbf19f6c

148

Thanks, I updated the code to print the phi-like recipe and the previous (non-phi like)

[akuegel]

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

147

Ok, I see your commit now :)
Thanks for the fix.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   for (VF *= 2; ElementCount::isKnownLT(VF, Range.End); VF *= 2) {
     Plan->addVF(VF);
     RSO << "," << VF;
   }
   RSO << "},UF>=1";
   RSO.flush();
   Plan->setName(PlanName);
 
+  assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
   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

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_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);
 };
 } // namespace llvm
 
 #endif //LLVM_TRANSFORMS_VECTORIZE_VPLANVERIFIER_H

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

void VPlanVerifier::verifyHierarchicalCFG(
     const VPRegionBlock *TopRegion) const {
   if (!EnableHCFGVerifier)
     return;
 
   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
   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;
+}