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