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 } 412