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/SmallPtrSet.h"
  20 #include "llvm/ADT/TypeSwitch.h"
  21
  22 #define DEBUG_TYPE "loop-vectorize"
  23
  24 using namespace llvm;
  25
  26 namespace {
  27 class VPlanVerifier {
  28   const VPDominatorTree &VPDT;
  29
  30   SmallPtrSet<BasicBlock *, 8> WrappedIRBBs;
  31
  32   // Verify that phi-like recipes are at the beginning of \p VPBB, with no
  33   // other recipes in between. Also check that only header blocks contain
  34   // VPHeaderPHIRecipes.
  35   bool verifyPhiRecipes(const VPBasicBlock *VPBB);
  36
  37   /// Verify that \p EVL is used correctly. The user must be either in
  38   /// EVL-based recipes as a last operand or VPInstruction::Add which is
  39   /// incoming value into EVL's recipe.
  40   bool verifyEVLRecipe(const VPInstruction &EVL) const;
  41
  42   bool verifyVPBasicBlock(const VPBasicBlock *VPBB);
  43
  44   bool verifyBlock(const VPBlockBase *VPB);
  45
  46   /// Helper function that verifies the CFG invariants of the VPBlockBases
  47   /// within
  48   /// \p Region. Checks in this function are generic for VPBlockBases. They are
  49   /// not specific for VPBasicBlocks or VPRegionBlocks.
  50   bool verifyBlocksInRegion(const VPRegionBlock *Region);
  51
  52   /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
  53   /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
  54   bool verifyRegion(const VPRegionBlock *Region);
  55
  56   /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
  57   /// VPBlockBases. Recurse inside nested VPRegionBlocks.
  58   bool verifyRegionRec(const VPRegionBlock *Region);
  59
  60 public:
  61   VPlanVerifier(VPDominatorTree &VPDT) : VPDT(VPDT) {}
  62
  63   bool verify(const VPlan &Plan);
  64 };
  65 } // namespace
  66
  67 bool VPlanVerifier::verifyPhiRecipes(const VPBasicBlock *VPBB) {
  68   auto RecipeI = VPBB->begin();
  69   auto End = VPBB->end();
  70   unsigned NumActiveLaneMaskPhiRecipes = 0;
  71   const VPRegionBlock *ParentR = VPBB->getParent();
  72   bool IsHeaderVPBB = ParentR && !ParentR->isReplicator() &&
  73                       ParentR->getEntryBasicBlock() == VPBB;
  74   while (RecipeI != End && RecipeI->isPhi()) {
  75     if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))
  76       NumActiveLaneMaskPhiRecipes++;
  77
  78     if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe>(*RecipeI)) {
  79       errs() << "Found non-header PHI recipe in header VPBB";
  80 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  81       errs() << ": ";
  82       RecipeI->dump();
  83 #endif
  84       return false;
  85     }
  86
  87     if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {
  88       errs() << "Found header PHI recipe in non-header VPBB";
  89 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  90       errs() << ": ";
  91       RecipeI->dump();
  92 #endif
  93       return false;
  94     }
  95
  96     RecipeI++;
  97   }
  98
  99   if (NumActiveLaneMaskPhiRecipes > 1) {
 100     errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
 101     return false;
 102   }
 103
 104   while (RecipeI != End) {
 105     if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
 106       errs() << "Found phi-like recipe after non-phi recipe";
 107
 108 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 109       errs() << ": ";
 110       RecipeI->dump();
 111       errs() << "after\n";
 112       std::prev(RecipeI)->dump();
 113 #endif
 114       return false;
 115     }
 116     RecipeI++;
 117   }
 118   return true;
 119 }
 120
 121 bool VPlanVerifier::verifyEVLRecipe(const VPInstruction &EVL) const {
 122   if (EVL.getOpcode() != VPInstruction::ExplicitVectorLength) {
 123     errs() << "verifyEVLRecipe should only be called on "
 124               "VPInstruction::ExplicitVectorLength\n";
 125     return false;
 126   }
 127   auto VerifyEVLUse = [&](const VPRecipeBase &R,
 128                           const unsigned ExpectedIdx) -> bool {
 129     SmallVector<const VPValue *> Ops(R.operands());
 130     unsigned UseCount = count(Ops, &EVL);
 131     if (UseCount != 1 || Ops[ExpectedIdx] != &EVL) {
 132       errs() << "EVL is used as non-last operand in EVL-based recipe\n";
 133       return false;
 134     }
 135     return true;
 136   };
 137   return all_of(EVL.users(), [&VerifyEVLUse](VPUser *U) {
 138     return TypeSwitch<const VPUser *, bool>(U)
 139         .Case<VPWidenIntrinsicRecipe>([&](const VPWidenIntrinsicRecipe *S) {
 140           return VerifyEVLUse(*S, S->getNumOperands() - 1);
 141         })
 142         .Case<VPWidenStoreEVLRecipe, VPReductionEVLRecipe>(
 143             [&](const VPRecipeBase *S) { return VerifyEVLUse(*S, 2); })
 144         .Case<VPWidenLoadEVLRecipe, VPReverseVectorPointerRecipe>(
 145             [&](const VPRecipeBase *R) { return VerifyEVLUse(*R, 1); })
 146         .Case<VPWidenEVLRecipe>([&](const VPWidenEVLRecipe *W) {
 147           return VerifyEVLUse(*W,
 148                               Instruction::isUnaryOp(W->getOpcode()) ? 1 : 2);
 149         })
 150         .Case<VPScalarCastRecipe>(
 151             [&](const VPScalarCastRecipe *S) { return VerifyEVLUse(*S, 0); })
 152         .Case<VPInstruction>([&](const VPInstruction *I) {
 153           if (I->getOpcode() != Instruction::Add) {
 154             errs() << "EVL is used as an operand in non-VPInstruction::Add\n";
 155             return false;
 156           }
 157           if (I->getNumUsers() != 1) {
 158             errs() << "EVL is used in VPInstruction:Add with multiple "
 159                       "users\n";
 160             return false;
 161           }
 162           if (!isa<VPEVLBasedIVPHIRecipe>(*I->users().begin())) {
 163             errs() << "Result of VPInstruction::Add with EVL operand is "
 164                       "not used by VPEVLBasedIVPHIRecipe\n";
 165             return false;
 166           }
 167           return true;
 168         })
 169         .Default([&](const VPUser *U) {
 170           errs() << "EVL has unexpected user\n";
 171           return false;
 172         });
 173   });
 174 }
 175
 176 bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {
 177   if (!verifyPhiRecipes(VPBB))
 178     return false;
 179
 180   // Verify that defs in VPBB dominate all their uses. The current
 181   // implementation is still incomplete.
 182   DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
 183   unsigned Cnt = 0;
 184   for (const VPRecipeBase &R : *VPBB)
 185     RecipeNumbering[&R] = Cnt++;
 186
 187   for (const VPRecipeBase &R : *VPBB) {
 188     if (isa<VPIRInstruction>(&R) && !isa<VPIRBasicBlock>(VPBB)) {
 189       errs() << "VPIRInstructions ";
 190 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 191       R.dump();
 192       errs() << " ";
 193 #endif
 194       errs() << "not in a VPIRBasicBlock!\n";
 195       return false;
 196     }
 197     for (const VPValue *V : R.definedValues()) {
 198       for (const VPUser *U : V->users()) {
 199         auto *UI = dyn_cast<VPRecipeBase>(U);
 200         // TODO: check dominance of incoming values for phis properly.
 201         if (!UI ||
 202             isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPredInstPHIRecipe>(UI))
 203           continue;
 204
 205         // If the user is in the same block, check it comes after R in the
 206         // block.
 207         if (UI->getParent() == VPBB) {
 208           if (RecipeNumbering[UI] < RecipeNumbering[&R]) {
 209             errs() << "Use before def!\n";
 210             return false;
 211           }
 212           continue;
 213         }
 214
 215         if (!VPDT.dominates(VPBB, UI->getParent())) {
 216           errs() << "Use before def!\n";
 217           return false;
 218         }
 219       }
 220     }
 221     if (const auto *EVL = dyn_cast<VPInstruction>(&R)) {
 222       if (EVL->getOpcode() == VPInstruction::ExplicitVectorLength &&
 223           !verifyEVLRecipe(*EVL)) {
 224         errs() << "EVL VPValue is not used correctly\n";
 225         return false;
 226       }
 227     }
 228   }
 229
 230   auto *IRBB = dyn_cast<VPIRBasicBlock>(VPBB);
 231   if (!IRBB)
 232     return true;
 233
 234   if (!WrappedIRBBs.insert(IRBB->getIRBasicBlock()).second) {
 235     errs() << "Same IR basic block used by multiple wrapper blocks!\n";
 236     return false;
 237   }
 238
 239   return true;
 240 }
 241
 242 /// Utility function that checks whether \p VPBlockVec has duplicate
 243 /// VPBlockBases.
 244 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
 245   SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
 246   for (const auto *Block : VPBlockVec) {
 247     if (!VPBlockSet.insert(Block).second)
 248       return true;
 249   }
 250   return false;
 251 }
 252
 253 bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
 254   auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
 255   // Check block's condition bit.
 256   if (VPB->getNumSuccessors() > 1 ||
 257       (VPBB && VPBB->getParent() && VPBB->isExiting() &&
 258        !VPBB->getParent()->isReplicator())) {
 259     if (!VPBB || !VPBB->getTerminator()) {
 260       errs() << "Block has multiple successors but doesn't "
 261                 "have a proper branch recipe!\n";
 262       return false;
 263     }
 264   } else {
 265     if (VPBB && VPBB->getTerminator()) {
 266       errs() << "Unexpected branch recipe!\n";
 267       return false;
 268     }
 269   }
 270
 271   // Check block's successors.
 272   const auto &Successors = VPB->getSuccessors();
 273   // There must be only one instance of a successor in block's successor list.
 274   // TODO: This won't work for switch statements.
 275   if (hasDuplicates(Successors)) {
 276     errs() << "Multiple instances of the same successor.\n";
 277     return false;
 278   }
 279
 280   for (const VPBlockBase *Succ : Successors) {
 281     // There must be a bi-directional link between block and successor.
 282     const auto &SuccPreds = Succ->getPredecessors();
 283     if (!is_contained(SuccPreds, VPB)) {
 284       errs() << "Missing predecessor link.\n";
 285       return false;
 286     }
 287   }
 288
 289   // Check block's predecessors.
 290   const auto &Predecessors = VPB->getPredecessors();
 291   // There must be only one instance of a predecessor in block's predecessor
 292   // list.
 293   // TODO: This won't work for switch statements.
 294   if (hasDuplicates(Predecessors)) {
 295     errs() << "Multiple instances of the same predecessor.\n";
 296     return false;
 297   }
 298
 299   for (const VPBlockBase *Pred : Predecessors) {
 300     // Block and predecessor must be inside the same region.
 301     if (Pred->getParent() != VPB->getParent()) {
 302       errs() << "Predecessor is not in the same region.\n";
 303       return false;
 304     }
 305
 306     // There must be a bi-directional link between block and predecessor.
 307     const auto &PredSuccs = Pred->getSuccessors();
 308     if (!is_contained(PredSuccs, VPB)) {
 309       errs() << "Missing successor link.\n";
 310       return false;
 311     }
 312   }
 313   return !VPBB || verifyVPBasicBlock(VPBB);
 314 }
 315
 316 bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {
 317   for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
 318     // Check block's parent.
 319     if (VPB->getParent() != Region) {
 320       errs() << "VPBlockBase has wrong parent\n";
 321       return false;
 322     }
 323
 324     if (!verifyBlock(VPB))
 325       return false;
 326   }
 327   return true;
 328 }
 329
 330 bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {
 331   const VPBlockBase *Entry = Region->getEntry();
 332   const VPBlockBase *Exiting = Region->getExiting();
 333
 334   // Entry and Exiting shouldn't have any predecessor/successor, respectively.
 335   if (Entry->getNumPredecessors() != 0) {
 336     errs() << "region entry block has predecessors\n";
 337     return false;
 338   }
 339   if (Exiting->getNumSuccessors() != 0) {
 340     errs() << "region exiting block has successors\n";
 341     return false;
 342   }
 343
 344   return verifyBlocksInRegion(Region);
 345 }
 346
 347 bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
 348   // Recurse inside nested regions and check all blocks inside the region.
 349   return verifyRegion(Region) &&
 350          all_of(vp_depth_first_shallow(Region->getEntry()),
 351                 [this](const VPBlockBase *VPB) {
 352                   const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB);
 353                   return !SubRegion || verifyRegionRec(SubRegion);
 354                 });
 355 }
 356
 357 bool VPlanVerifier::verify(const VPlan &Plan) {
 358   if (any_of(vp_depth_first_shallow(Plan.getEntry()),
 359              [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
 360     return false;
 361
 362   const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
 363   if (!verifyRegionRec(TopRegion))
 364     return false;
 365
 366   if (TopRegion->getParent()) {
 367     errs() << "VPlan Top Region should have no parent.\n";
 368     return false;
 369   }
 370
 371   const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
 372   if (!Entry) {
 373     errs() << "VPlan entry block is not a VPBasicBlock\n";
 374     return false;
 375   }
 376
 377   if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
 378     errs() << "VPlan vector loop header does not start with a "
 379               "VPCanonicalIVPHIRecipe\n";
 380     return false;
 381   }
 382
 383   const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
 384   if (!Exiting) {
 385     errs() << "VPlan exiting block is not a VPBasicBlock\n";
 386     return false;
 387   }
 388
 389   if (Exiting->empty()) {
 390     errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
 391               "BranchOnCond VPInstruction but is empty\n";
 392     return false;
 393   }
 394
 395   auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
 396   if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
 397                     LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
 398     errs() << "VPlan vector loop exit must end with BranchOnCount or "
 399               "BranchOnCond VPInstruction\n";
 400     return false;
 401   }
 402
 403   return true;
 404 }
 405
 406 bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
 407   VPDominatorTree VPDT;
 408   VPDT.recalculate(const_cast<VPlan &>(Plan));
 409   VPlanVerifier Verifier(VPDT);
 410   return Verifier.verify(Plan);
 411 }