llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

   1 //===-- VPlanVerifier.cpp -------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This file defines the class VPlanVerifier, which contains utility functions
  11 /// to check the consistency and invariants of a VPlan.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "VPlanVerifier.h"
  16 #include "VPlan.h"
  17 #include "VPlanCFG.h"
  18 #include "VPlanDominatorTree.h"
  19 #include "llvm/ADT/DepthFirstIterator.h"
  20 #include "llvm/Support/CommandLine.h"
  21
  22 #define DEBUG_TYPE "loop-vectorize"
  23
  24 using namespace llvm;
  25
  26 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
  27                                         cl::Hidden,
  28                                         cl::desc("Verify VPlan H-CFG."));
  29
  30 #ifndef NDEBUG
  31 /// Utility function that checks whether \p VPBlockVec has duplicate
  32 /// VPBlockBases.
  33 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
  34   SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
  35   for (const auto *Block : VPBlockVec) {
  36     if (VPBlockSet.count(Block))
  37       return true;
  38     VPBlockSet.insert(Block);
  39   }
  40   return false;
  41 }
  42 #endif
  43
  44 /// Helper function that verifies the CFG invariants of the VPBlockBases within
  45 /// \p Region. Checks in this function are generic for VPBlockBases. They are
  46 /// not specific for VPBasicBlocks or VPRegionBlocks.
  47 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
  48   for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
  49     // Check block's parent.
  50     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
  51
  52     auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
  53     // Check block's condition bit.
  54     if (VPB->getNumSuccessors() > 1 || (VPBB && VPBB->isExiting()))
  55       assert(VPBB && VPBB->getTerminator() &&
  56              "Block has multiple successors but doesn't "
  57              "have a proper branch recipe!");
  58     else
  59       assert((!VPBB || !VPBB->getTerminator()) && "Unexpected branch recipe!");
  60
  61     // Check block's successors.
  62     const auto &Successors = VPB->getSuccessors();
  63     // There must be only one instance of a successor in block's successor list.
  64     // TODO: This won't work for switch statements.
  65     assert(!hasDuplicates(Successors) &&
  66            "Multiple instances of the same successor.");
  67
  68     for (const VPBlockBase *Succ : Successors) {
  69       // There must be a bi-directional link between block and successor.
  70       const auto &SuccPreds = Succ->getPredecessors();
  71       assert(llvm::is_contained(SuccPreds, VPB) && "Missing predecessor link.");
  72       (void)SuccPreds;
  73     }
  74
  75     // Check block's predecessors.
  76     const auto &Predecessors = VPB->getPredecessors();
  77     // There must be only one instance of a predecessor in block's predecessor
  78     // list.
  79     // TODO: This won't work for switch statements.
  80     assert(!hasDuplicates(Predecessors) &&
  81            "Multiple instances of the same predecessor.");
  82
  83     for (const VPBlockBase *Pred : Predecessors) {
  84       // Block and predecessor must be inside the same region.
  85       assert(Pred->getParent() == VPB->getParent() &&
  86              "Predecessor is not in the same region.");
  87
  88       // There must be a bi-directional link between block and predecessor.
  89       const auto &PredSuccs = Pred->getSuccessors();
  90       assert(llvm::is_contained(PredSuccs, VPB) && "Missing successor link.");
  91       (void)PredSuccs;
  92     }
  93   }
  94 }
  95
  96 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
  97 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
  98 static void verifyRegion(const VPRegionBlock *Region) {
  99   const VPBlockBase *Entry = Region->getEntry();
 100   const VPBlockBase *Exiting = Region->getExiting();
 101
 102   // Entry and Exiting shouldn't have any predecessor/successor, respectively.
 103   assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
 104   assert(!Exiting->getNumSuccessors() &&
 105          "Region exiting block has successors.");
 106   (void)Entry;
 107   (void)Exiting;
 108
 109   verifyBlocksInRegion(Region);
 110 }
 111
 112 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
 113 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
 114 static void verifyRegionRec(const VPRegionBlock *Region) {
 115   verifyRegion(Region);
 116
 117   // Recurse inside nested regions.
 118   for (const VPBlockBase *VPB : make_range(
 119            df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
 120            df_iterator<const VPBlockBase *>::end(Region->getExiting()))) {
 121     if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
 122       verifyRegionRec(SubRegion);
 123   }
 124 }
 125
 126 void VPlanVerifier::verifyHierarchicalCFG(
 127     const VPRegionBlock *TopRegion) const {
 128   if (!EnableHCFGVerifier)
 129     return;
 130
 131   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
 132   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
 133   verifyRegionRec(TopRegion);
 134 }
 135
 136 // Verify that phi-like recipes are at the beginning of \p VPBB, with no
 137 // other recipes in between. Also check that only header blocks contain
 138 // VPHeaderPHIRecipes.
 139 static bool verifyPhiRecipes(const VPBasicBlock *VPBB) {
 140   auto RecipeI = VPBB->begin();
 141   auto End = VPBB->end();
 142   unsigned NumActiveLaneMaskPhiRecipes = 0;
 143   const VPRegionBlock *ParentR = VPBB->getParent();
 144   bool IsHeaderVPBB = ParentR && !ParentR->isReplicator() &&
 145                       ParentR->getEntryBasicBlock() == VPBB;
 146   while (RecipeI != End && RecipeI->isPhi()) {
 147     if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))
 148       NumActiveLaneMaskPhiRecipes++;
 149
 150     if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe>(*RecipeI)) {
 151       errs() << "Found non-header PHI recipe in header VPBB";
 152 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 153       errs() << ": ";
 154       RecipeI->dump();
 155 #endif
 156       return false;
 157     }
 158
 159     if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {
 160       errs() << "Found header PHI recipe in non-header VPBB";
 161 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 162       errs() << ": ";
 163       RecipeI->dump();
 164 #endif
 165       return false;
 166     }
 167
 168     RecipeI++;
 169   }
 170
 171   if (NumActiveLaneMaskPhiRecipes > 1) {
 172     errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
 173     return false;
 174   }
 175
 176   while (RecipeI != End) {
 177     if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
 178       errs() << "Found phi-like recipe after non-phi recipe";
 179
 180 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 181       errs() << ": ";
 182       RecipeI->dump();
 183       errs() << "after\n";
 184       std::prev(RecipeI)->dump();
 185 #endif
 186       return false;
 187     }
 188     RecipeI++;
 189   }
 190   return true;
 191 }
 192
 193 static bool verifyVPBasicBlock(const VPBasicBlock *VPBB,
 194                                VPDominatorTree &VPDT) {
 195   if (!verifyPhiRecipes(VPBB))
 196     return false;
 197
 198   // Verify that defs in VPBB dominate all their uses. The current
 199   // implementation is still incomplete.
 200   DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
 201   unsigned Cnt = 0;
 202   for (const VPRecipeBase &R : *VPBB)
 203     RecipeNumbering[&R] = Cnt++;
 204
 205   for (const VPRecipeBase &R : *VPBB) {
 206     for (const VPValue *V : R.definedValues()) {
 207       for (const VPUser *U : V->users()) {
 208         auto *UI = dyn_cast<VPRecipeBase>(U);
 209         // TODO: check dominance of incoming values for phis properly.
 210         if (!UI || isa<VPHeaderPHIRecipe>(UI) || isa<VPPredInstPHIRecipe>(UI))
 211           continue;
 212
 213         // If the user is in the same block, check it comes after R in the
 214         // block.
 215         if (UI->getParent() == VPBB) {
 216           if (RecipeNumbering[UI] < RecipeNumbering[&R]) {
 217             errs() << "Use before def!\n";
 218             return false;
 219           }
 220           continue;
 221         }
 222
 223         if (!VPDT.dominates(VPBB, UI->getParent())) {
 224           errs() << "Use before def!\n";
 225           return false;
 226         }
 227       }
 228     }
 229   }
 230   return true;
 231 }
 232
 233 bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
 234   VPDominatorTree VPDT;
 235   VPDT.recalculate(const_cast<VPlan &>(Plan));
 236
 237   auto Iter = vp_depth_first_deep(Plan.getEntry());
 238   for (const VPBasicBlock *VPBB :
 239        VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
 240     if (!verifyVPBasicBlock(VPBB, VPDT))
 241       return false;
 242   }
 243
 244   const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
 245   const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
 246   if (!Entry) {
 247     errs() << "VPlan entry block is not a VPBasicBlock\n";
 248     return false;
 249   }
 250
 251   if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
 252     errs() << "VPlan vector loop header does not start with a "
 253               "VPCanonicalIVPHIRecipe\n";
 254     return false;
 255   }
 256
 257   const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
 258   if (!Exiting) {
 259     errs() << "VPlan exiting block is not a VPBasicBlock\n";
 260     return false;
 261   }
 262
 263   if (Exiting->empty()) {
 264     errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
 265               "BranchOnCond VPInstruction but is empty\n";
 266     return false;
 267   }
 268
 269   auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
 270   if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
 271                     LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
 272     errs() << "VPlan vector loop exit must end with BranchOnCount or "
 273               "BranchOnCond VPInstruction\n";
 274     return false;
 275   }
 276
 277   for (const VPRegionBlock *Region :
 278        VPBlockUtils::blocksOnly<const VPRegionBlock>(
 279            vp_depth_first_deep(Plan.getEntry()))) {
 280     if (Region->getEntry()->getNumPredecessors() != 0) {
 281       errs() << "region entry block has predecessors\n";
 282       return false;
 283     }
 284     if (Region->getExiting()->getNumSuccessors() != 0) {
 285       errs() << "region exiting block has successors\n";
 286       return false;
 287     }
 288   }
 289
 290   for (const auto &KV : Plan.getLiveOuts())
 291     if (KV.second->getNumOperands() != 1) {
 292       errs() << "live outs must have a single operand\n";
 293       return false;
 294     }
 295
 296   return true;
 297 }