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>([&](const VPWidenLoadEVLRecipe *L) { 147 return VerifyEVLUse(*L, 1); 148 }) 149 .Case<VPWidenEVLRecipe>([&](const VPWidenEVLRecipe *W) { 150 return VerifyEVLUse( 151 *W, Instruction::isUnaryOp(W->getOpcode()) ? 1 : 2); 152 }) 153 .Case<VPReductionEVLRecipe>([&](const VPReductionEVLRecipe *R) { 154 return VerifyEVLUse(*R, 2); 155 }) 156 .Case<VPScalarCastRecipe>( 157 [&](const VPScalarCastRecipe *S) { return true; }) 158 .Case<VPInstruction>([&](const VPInstruction *I) { 159 if (I->getOpcode() != Instruction::Add) { 160 errs() 161 << "EVL is used as an operand in non-VPInstruction::Add\n"; 162 return false; 163 } 164 if (I->getNumUsers() != 1) { 165 errs() << "EVL is used in VPInstruction:Add with multiple " 166 "users\n"; 167 return false; 168 } 169 if (!isa<VPEVLBasedIVPHIRecipe>(*I->users().begin())) { 170 errs() << "Result of VPInstruction::Add with EVL operand is " 171 "not used by VPEVLBasedIVPHIRecipe\n"; 172 return false; 173 } 174 return true; 175 }) 176 .Default([&](const VPUser *U) { 177 errs() << "EVL has unexpected user\n"; 178 return false; 179 })) { 180 return false; 181 } 182 } 183 return true; 184 } 185 186 bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) { 187 if (!verifyPhiRecipes(VPBB)) 188 return false; 189 190 // Verify that defs in VPBB dominate all their uses. The current 191 // implementation is still incomplete. 192 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering; 193 unsigned Cnt = 0; 194 for (const VPRecipeBase &R : *VPBB) 195 RecipeNumbering[&R] = Cnt++; 196 197 for (const VPRecipeBase &R : *VPBB) { 198 if (isa<VPIRInstruction>(&R) ^ isa<VPIRBasicBlock>(VPBB)) { 199 errs() << "VPIRInstructions "; 200 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 201 R.dump(); 202 errs() << " "; 203 #endif 204 errs() << "not in a VPIRBasicBlock!\n"; 205 return false; 206 } 207 for (const VPValue *V : R.definedValues()) { 208 for (const VPUser *U : V->users()) { 209 auto *UI = dyn_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 VPlanVerifier Verifier(VPDT); 420 return Verifier.verify(Plan); 421 } 422