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 for (const VPUser *U : EVL.users()) { 138 if (!TypeSwitch<const VPUser *, bool>(U) 139 .Case<VPWidenIntrinsicRecipe>( 140 [&](const VPWidenIntrinsicRecipe *S) { 141 return VerifyEVLUse(*S, S->getNumOperands() - 1); 142 }) 143 .Case<VPWidenStoreEVLRecipe>([&](const VPWidenStoreEVLRecipe *S) { 144 return VerifyEVLUse(*S, 2); 145 }) 146 .Case<VPWidenLoadEVLRecipe, VPReverseVectorPointerRecipe>( 147 [&](const VPRecipeBase *R) { return VerifyEVLUse(*R, 1); }) 148 .Case<VPWidenEVLRecipe>([&](const VPWidenEVLRecipe *W) { 149 return VerifyEVLUse( 150 *W, Instruction::isUnaryOp(W->getOpcode()) ? 1 : 2); 151 }) 152 .Case<VPReductionEVLRecipe>([&](const VPReductionEVLRecipe *R) { 153 return VerifyEVLUse(*R, 2); 154 }) 155 .Case<VPScalarCastRecipe>( 156 [&](const VPScalarCastRecipe *S) { return true; }) 157 .Case<VPInstruction>([&](const VPInstruction *I) { 158 if (I->getOpcode() != Instruction::Add) { 159 errs() 160 << "EVL is used as an operand in non-VPInstruction::Add\n"; 161 return false; 162 } 163 if (I->getNumUsers() != 1) { 164 errs() << "EVL is used in VPInstruction:Add with multiple " 165 "users\n"; 166 return false; 167 } 168 if (!isa<VPEVLBasedIVPHIRecipe>(*I->users().begin())) { 169 errs() << "Result of VPInstruction::Add with EVL operand is " 170 "not used by VPEVLBasedIVPHIRecipe\n"; 171 return false; 172 } 173 return true; 174 }) 175 .Default([&](const VPUser *U) { 176 errs() << "EVL has unexpected user\n"; 177 return false; 178 })) { 179 return false; 180 } 181 } 182 return true; 183 } 184 185 bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) { 186 if (!verifyPhiRecipes(VPBB)) 187 return false; 188 189 // Verify that defs in VPBB dominate all their uses. The current 190 // implementation is still incomplete. 191 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering; 192 unsigned Cnt = 0; 193 for (const VPRecipeBase &R : *VPBB) 194 RecipeNumbering[&R] = Cnt++; 195 196 for (const VPRecipeBase &R : *VPBB) { 197 if (isa<VPIRInstruction>(&R) ^ isa<VPIRBasicBlock>(VPBB)) { 198 errs() << "VPIRInstructions "; 199 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 200 R.dump(); 201 errs() << " "; 202 #endif 203 errs() << "not in a VPIRBasicBlock!\n"; 204 return false; 205 } 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 || 211 isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPredInstPHIRecipe>(UI)) 212 continue; 213 214 // If the user is in the same block, check it comes after R in the 215 // block. 216 if (UI->getParent() == VPBB) { 217 if (RecipeNumbering[UI] < RecipeNumbering[&R]) { 218 errs() << "Use before def!\n"; 219 return false; 220 } 221 continue; 222 } 223 224 if (!VPDT.dominates(VPBB, UI->getParent())) { 225 errs() << "Use before def!\n"; 226 return false; 227 } 228 } 229 } 230 if (const auto *EVL = dyn_cast<VPInstruction>(&R)) { 231 if (EVL->getOpcode() == VPInstruction::ExplicitVectorLength && 232 !verifyEVLRecipe(*EVL)) { 233 errs() << "EVL VPValue is not used correctly\n"; 234 return false; 235 } 236 } 237 } 238 239 auto *IRBB = dyn_cast<VPIRBasicBlock>(VPBB); 240 if (!IRBB) 241 return true; 242 243 if (!WrappedIRBBs.insert(IRBB->getIRBasicBlock()).second) { 244 errs() << "Same IR basic block used by multiple wrapper blocks!\n"; 245 return false; 246 } 247 248 return true; 249 } 250 251 /// Utility function that checks whether \p VPBlockVec has duplicate 252 /// VPBlockBases. 253 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) { 254 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet; 255 for (const auto *Block : VPBlockVec) { 256 if (!VPBlockSet.insert(Block).second) 257 return true; 258 } 259 return false; 260 } 261 262 bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) { 263 auto *VPBB = dyn_cast<VPBasicBlock>(VPB); 264 // Check block's condition bit. 265 if (VPB->getNumSuccessors() > 1 || 266 (VPBB && VPBB->getParent() && VPBB->isExiting() && 267 !VPBB->getParent()->isReplicator())) { 268 if (!VPBB || !VPBB->getTerminator()) { 269 errs() << "Block has multiple successors but doesn't " 270 "have a proper branch recipe!\n"; 271 return false; 272 } 273 } else { 274 if (VPBB && VPBB->getTerminator()) { 275 errs() << "Unexpected branch recipe!\n"; 276 return false; 277 } 278 } 279 280 // Check block's successors. 281 const auto &Successors = VPB->getSuccessors(); 282 // There must be only one instance of a successor in block's successor list. 283 // TODO: This won't work for switch statements. 284 if (hasDuplicates(Successors)) { 285 errs() << "Multiple instances of the same successor.\n"; 286 return false; 287 } 288 289 for (const VPBlockBase *Succ : Successors) { 290 // There must be a bi-directional link between block and successor. 291 const auto &SuccPreds = Succ->getPredecessors(); 292 if (!is_contained(SuccPreds, VPB)) { 293 errs() << "Missing predecessor link.\n"; 294 return false; 295 } 296 } 297 298 // Check block's predecessors. 299 const auto &Predecessors = VPB->getPredecessors(); 300 // There must be only one instance of a predecessor in block's predecessor 301 // list. 302 // TODO: This won't work for switch statements. 303 if (hasDuplicates(Predecessors)) { 304 errs() << "Multiple instances of the same predecessor.\n"; 305 return false; 306 } 307 308 for (const VPBlockBase *Pred : Predecessors) { 309 // Block and predecessor must be inside the same region. 310 if (Pred->getParent() != VPB->getParent()) { 311 errs() << "Predecessor is not in the same region.\n"; 312 return false; 313 } 314 315 // There must be a bi-directional link between block and predecessor. 316 const auto &PredSuccs = Pred->getSuccessors(); 317 if (!is_contained(PredSuccs, VPB)) { 318 errs() << "Missing successor link.\n"; 319 return false; 320 } 321 } 322 return !VPBB || verifyVPBasicBlock(VPBB); 323 } 324 325 bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) { 326 for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) { 327 // Check block's parent. 328 if (VPB->getParent() != Region) { 329 errs() << "VPBlockBase has wrong parent\n"; 330 return false; 331 } 332 333 if (!verifyBlock(VPB)) 334 return false; 335 } 336 return true; 337 } 338 339 bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) { 340 const VPBlockBase *Entry = Region->getEntry(); 341 const VPBlockBase *Exiting = Region->getExiting(); 342 343 // Entry and Exiting shouldn't have any predecessor/successor, respectively. 344 if (Entry->getNumPredecessors() != 0) { 345 errs() << "region entry block has predecessors\n"; 346 return false; 347 } 348 if (Exiting->getNumSuccessors() != 0) { 349 errs() << "region exiting block has successors\n"; 350 return false; 351 } 352 353 return verifyBlocksInRegion(Region); 354 } 355 356 bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) { 357 // Recurse inside nested regions and check all blocks inside the region. 358 return verifyRegion(Region) && 359 all_of(vp_depth_first_shallow(Region->getEntry()), 360 [this](const VPBlockBase *VPB) { 361 const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB); 362 return !SubRegion || verifyRegionRec(SubRegion); 363 }); 364 } 365 366 bool VPlanVerifier::verify(const VPlan &Plan) { 367 if (any_of(vp_depth_first_shallow(Plan.getEntry()), 368 [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); })) 369 return false; 370 371 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion(); 372 if (!verifyRegionRec(TopRegion)) 373 return false; 374 375 if (TopRegion->getParent()) { 376 errs() << "VPlan Top Region should have no parent.\n"; 377 return false; 378 } 379 380 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry()); 381 if (!Entry) { 382 errs() << "VPlan entry block is not a VPBasicBlock\n"; 383 return false; 384 } 385 386 if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) { 387 errs() << "VPlan vector loop header does not start with a " 388 "VPCanonicalIVPHIRecipe\n"; 389 return false; 390 } 391 392 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting()); 393 if (!Exiting) { 394 errs() << "VPlan exiting block is not a VPBasicBlock\n"; 395 return false; 396 } 397 398 if (Exiting->empty()) { 399 errs() << "VPlan vector loop exiting block must end with BranchOnCount or " 400 "BranchOnCond VPInstruction but is empty\n"; 401 return false; 402 } 403 404 auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end())); 405 if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount && 406 LastInst->getOpcode() != VPInstruction::BranchOnCond)) { 407 errs() << "VPlan vector loop exit must end with BranchOnCount or " 408 "BranchOnCond VPInstruction\n"; 409 return false; 410 } 411 412 return true; 413 } 414 415 bool llvm::verifyVPlanIsValid(const VPlan &Plan) { 416 VPDominatorTree VPDT; 417 VPDT.recalculate(const_cast<VPlan &>(Plan)); 418 VPlanVerifier Verifier(VPDT); 419 return Verifier.verify(Plan); 420 } 421