555 lines · 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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file defines the class VPlanVerifier, which contains utility functions11/// 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 "VPlanHelpers.h"20#include "VPlanPatternMatch.h"21#include "VPlanUtils.h"22#include "llvm/ADT/SmallPtrSet.h"23#include "llvm/ADT/TypeSwitch.h"24 25#define DEBUG_TYPE "loop-vectorize"26 27using namespace llvm;28using namespace VPlanPatternMatch;29 30namespace {31class VPlanVerifier {32 const VPDominatorTree &VPDT;33 VPTypeAnalysis &TypeInfo;34 bool VerifyLate;35 36 SmallPtrSet<BasicBlock *, 8> WrappedIRBBs;37 38 // Verify that phi-like recipes are at the beginning of \p VPBB, with no39 // other recipes in between. Also check that only header blocks contain40 // VPHeaderPHIRecipes.41 bool verifyPhiRecipes(const VPBasicBlock *VPBB);42 43 /// Verify that \p EVL is used correctly. The user must be either in44 /// EVL-based recipes as a last operand or VPInstruction::Add which is45 /// incoming value into EVL's recipe.46 bool verifyEVLRecipe(const VPInstruction &EVL) const;47 48 /// Verify that \p LastActiveLane's operand is guaranteed to be a prefix-mask.49 bool verifyLastActiveLaneRecipe(const VPInstruction &LastActiveLane) const;50 51 bool verifyVPBasicBlock(const VPBasicBlock *VPBB);52 53 bool verifyBlock(const VPBlockBase *VPB);54 55 /// Helper function that verifies the CFG invariants of the VPBlockBases56 /// within57 /// \p Region. Checks in this function are generic for VPBlockBases. They are58 /// not specific for VPBasicBlocks or VPRegionBlocks.59 bool verifyBlocksInRegion(const VPRegionBlock *Region);60 61 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested62 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.63 bool verifyRegion(const VPRegionBlock *Region);64 65 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested66 /// VPBlockBases. Recurse inside nested VPRegionBlocks.67 bool verifyRegionRec(const VPRegionBlock *Region);68 69public:70 VPlanVerifier(VPDominatorTree &VPDT, VPTypeAnalysis &TypeInfo,71 bool VerifyLate)72 : VPDT(VPDT), TypeInfo(TypeInfo), VerifyLate(VerifyLate) {}73 74 bool verify(const VPlan &Plan);75};76} // namespace77 78bool VPlanVerifier::verifyPhiRecipes(const VPBasicBlock *VPBB) {79 auto RecipeI = VPBB->begin();80 auto End = VPBB->end();81 unsigned NumActiveLaneMaskPhiRecipes = 0;82 bool IsHeaderVPBB = VPBlockUtils::isHeader(VPBB, VPDT);83 while (RecipeI != End && RecipeI->isPhi()) {84 if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))85 NumActiveLaneMaskPhiRecipes++;86 87 if (IsHeaderVPBB &&88 !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPhi>(*RecipeI)) {89 errs() << "Found non-header PHI recipe in header VPBB";90#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)91 errs() << ": ";92 RecipeI->dump();93#endif94 return false;95 }96 97 if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {98 errs() << "Found header PHI recipe in non-header VPBB";99#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)100 errs() << ": ";101 RecipeI->dump();102#endif103 return false;104 }105 106 // Check if the recipe operands match the number of predecessors.107 // TODO Extend to other phi-like recipes.108 if (auto *PhiIRI = dyn_cast<VPIRPhi>(&*RecipeI)) {109 if (PhiIRI->getNumOperands() != VPBB->getNumPredecessors()) {110 errs() << "Phi-like recipe with different number of operands and "111 "predecessors.\n";112 // TODO: Print broken recipe. At the moment printing an ill-formed113 // phi-like recipe may crash.114 return false;115 }116 }117 118 RecipeI++;119 }120 121 if (!VerifyLate && NumActiveLaneMaskPhiRecipes > 1) {122 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";123 return false;124 }125 126 while (RecipeI != End) {127 if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {128 errs() << "Found phi-like recipe after non-phi recipe";129 130#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)131 errs() << ": ";132 RecipeI->dump();133 errs() << "after\n";134 std::prev(RecipeI)->dump();135#endif136 return false;137 }138 RecipeI++;139 }140 return true;141}142 143bool VPlanVerifier::verifyEVLRecipe(const VPInstruction &EVL) const {144 if (EVL.getOpcode() != VPInstruction::ExplicitVectorLength) {145 errs() << "verifyEVLRecipe should only be called on "146 "VPInstruction::ExplicitVectorLength\n";147 return false;148 }149 auto VerifyEVLUse = [&](const VPRecipeBase &R,150 const unsigned ExpectedIdx) -> bool {151 SmallVector<const VPValue *> Ops(R.operands());152 unsigned UseCount = count(Ops, &EVL);153 if (UseCount != 1 || Ops[ExpectedIdx] != &EVL) {154 errs() << "EVL is used as non-last operand in EVL-based recipe\n";155 return false;156 }157 return true;158 };159 return all_of(EVL.users(), [this, &VerifyEVLUse](VPUser *U) {160 return TypeSwitch<const VPUser *, bool>(U)161 .Case<VPWidenIntrinsicRecipe>([&](const VPWidenIntrinsicRecipe *S) {162 return VerifyEVLUse(*S, S->getNumOperands() - 1);163 })164 .Case<VPWidenStoreEVLRecipe, VPReductionEVLRecipe,165 VPWidenIntOrFpInductionRecipe, VPWidenPointerInductionRecipe>(166 [&](const VPRecipeBase *S) { return VerifyEVLUse(*S, 2); })167 .Case<VPScalarIVStepsRecipe>([&](auto *R) {168 if (R->getNumOperands() != 3) {169 errs() << "Unrolling with EVL tail folding not yet supported\n";170 return false;171 }172 return VerifyEVLUse(*R, 2);173 })174 .Case<VPWidenLoadEVLRecipe, VPVectorEndPointerRecipe,175 VPInterleaveEVLRecipe>(176 [&](const VPRecipeBase *R) { return VerifyEVLUse(*R, 1); })177 .Case<VPInstructionWithType>(178 [&](const VPInstructionWithType *S) { return VerifyEVLUse(*S, 0); })179 .Case<VPInstruction>([&](const VPInstruction *I) {180 if (I->getOpcode() == Instruction::PHI ||181 I->getOpcode() == Instruction::ICmp ||182 I->getOpcode() == Instruction::Sub)183 return VerifyEVLUse(*I, 1);184 switch (I->getOpcode()) {185 case Instruction::Add:186 break;187 case Instruction::UIToFP:188 case Instruction::Trunc:189 case Instruction::ZExt:190 case Instruction::Mul:191 case Instruction::FMul:192 case VPInstruction::Broadcast:193 // Opcodes above can only use EVL after wide inductions have been194 // expanded.195 if (!VerifyLate) {196 errs() << "EVL used by unexpected VPInstruction\n";197 return false;198 }199 break;200 default:201 errs() << "EVL used by unexpected VPInstruction\n";202 return false;203 }204 // EVLIVIncrement is only used by EVLIV & BranchOnCount.205 // Having more than two users is unexpected.206 if (I->getOpcode() != VPInstruction::Broadcast &&207 I->getNumUsers() != 1 &&208 (I->getNumUsers() != 2 ||209 none_of(I->users(), match_fn(m_BranchOnCount(m_Specific(I),210 m_VPValue()))))) {211 errs() << "EVL is used in VPInstruction with multiple users\n";212 return false;213 }214 if (!VerifyLate && !isa<VPEVLBasedIVPHIRecipe>(*I->users().begin())) {215 errs() << "Result of VPInstruction::Add with EVL operand is "216 "not used by VPEVLBasedIVPHIRecipe\n";217 return false;218 }219 return true;220 })221 .Default([&](const VPUser *U) {222 errs() << "EVL has unexpected user\n";223 return false;224 });225 });226}227 228bool VPlanVerifier::verifyLastActiveLaneRecipe(229 const VPInstruction &LastActiveLane) const {230 assert(LastActiveLane.getOpcode() == VPInstruction::LastActiveLane &&231 "must be called with VPInstruction::LastActiveLane");232 233 if (LastActiveLane.getNumOperands() < 1) {234 errs() << "LastActiveLane must have at least one operand\n";235 return false;236 }237 238 const VPlan &Plan = *LastActiveLane.getParent()->getPlan();239 // All operands must be prefix-mask. Currently we check for header masks or240 // EVL-derived masks, as those are currently the only operands in practice,241 // but this may need updating in the future.242 for (VPValue *Op : LastActiveLane.operands()) {243 if (vputils::isHeaderMask(Op, Plan))244 continue;245 246 // Masks derived from EVL are also fine.247 auto BroadcastOrEVL =248 m_CombineOr(m_Broadcast(m_EVL(m_VPValue())), m_EVL(m_VPValue()));249 if (match(Op, m_CombineOr(m_ICmp(m_StepVector(), BroadcastOrEVL),250 m_ICmp(BroadcastOrEVL, m_StepVector()))))251 continue;252 253 errs() << "LastActiveLane operand ";254#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)255 VPSlotTracker Tracker(&Plan);256 Op->printAsOperand(errs(), Tracker);257#endif258 errs() << " must be prefix mask (a header mask or an "259 "EVL-derived mask currently)\n";260 return false;261 }262 263 return true;264}265 266bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {267 if (!verifyPhiRecipes(VPBB))268 return false;269 270 // Verify that defs in VPBB dominate all their uses.271 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;272 unsigned Cnt = 0;273 for (const VPRecipeBase &R : *VPBB)274 RecipeNumbering[&R] = Cnt++;275 276 for (const VPRecipeBase &R : *VPBB) {277 if (isa<VPIRInstruction>(&R) && !isa<VPIRBasicBlock>(VPBB)) {278 errs() << "VPIRInstructions ";279#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)280 R.dump();281 errs() << " ";282#endif283 errs() << "not in a VPIRBasicBlock!\n";284 return false;285 }286 for (const VPValue *V : R.definedValues()) {287 // Verify that we can infer a scalar type for each defined value. With288 // assertions enabled, inferScalarType will perform some consistency289 // checks during type inference.290 if (!TypeInfo.inferScalarType(V)) {291 errs() << "Failed to infer scalar type!\n";292 return false;293 }294 295 for (const VPUser *U : V->users()) {296 auto *UI = cast<VPRecipeBase>(U);297 if (isa<VPIRPhi>(UI) &&298 UI->getNumOperands() != UI->getParent()->getNumPredecessors()) {299 errs() << "Phi-like recipe with different number of operands and "300 "predecessors.\n";301 return false;302 }303 304 if (auto *Phi = dyn_cast<VPPhiAccessors>(UI)) {305 for (const auto &[IncomingVPV, IncomingVPBB] :306 Phi->incoming_values_and_blocks()) {307 if (IncomingVPV != V)308 continue;309 310 if (VPDT.dominates(VPBB, IncomingVPBB))311 continue;312 313 errs() << "Incoming def does not dominate incoming block!\n";314#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)315 VPSlotTracker Tracker(VPBB->getPlan());316 IncomingVPV->getDefiningRecipe()->print(errs(), " ", Tracker);317 errs() << "\n does not dominate " << IncomingVPBB->getName()318 << " for\n";319 UI->print(errs(), " ", Tracker);320#endif321 return false;322 }323 continue;324 }325 // TODO: Also verify VPPredInstPHIRecipe.326 if (isa<VPPredInstPHIRecipe>(UI))327 continue;328 329 // If the user is in the same block, check it comes after R in the330 // block.331 if (UI->getParent() == VPBB) {332 if (RecipeNumbering[UI] >= RecipeNumbering[&R])333 continue;334 } else {335 if (VPDT.dominates(VPBB, UI->getParent()))336 continue;337 }338 339 errs() << "Use before def!\n";340#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)341 VPSlotTracker Tracker(VPBB->getPlan());342 UI->print(errs(), " ", Tracker);343 errs() << "\n before\n";344 R.print(errs(), " ", Tracker);345 errs() << "\n";346#endif347 return false;348 }349 }350 if (const auto *VPI = dyn_cast<VPInstruction>(&R)) {351 switch (VPI->getOpcode()) {352 case VPInstruction::ExplicitVectorLength:353 if (!verifyEVLRecipe(*VPI)) {354 errs() << "EVL VPValue is not used correctly\n";355 return false;356 }357 break;358 case VPInstruction::LastActiveLane:359 if (!verifyLastActiveLaneRecipe(*VPI))360 return false;361 break;362 default:363 break;364 }365 }366 }367 368 auto *IRBB = dyn_cast<VPIRBasicBlock>(VPBB);369 if (!IRBB)370 return true;371 372 if (!WrappedIRBBs.insert(IRBB->getIRBasicBlock()).second) {373 errs() << "Same IR basic block used by multiple wrapper blocks!\n";374 return false;375 }376 377 return true;378}379 380/// Utility function that checks whether \p VPBlockVec has duplicate381/// VPBlockBases.382static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {383 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;384 for (const auto *Block : VPBlockVec) {385 if (!VPBlockSet.insert(Block).second)386 return true;387 }388 return false;389}390 391bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {392 auto *VPBB = dyn_cast<VPBasicBlock>(VPB);393 // Check block's condition bit.394 if (!isa<VPIRBasicBlock>(VPB)) {395 if (VPB->getNumSuccessors() > 1 ||396 (VPBB && VPBB->getParent() && VPBB->isExiting() &&397 !VPBB->getParent()->isReplicator())) {398 if (!VPBB || !VPBB->getTerminator()) {399 errs() << "Block has multiple successors but doesn't "400 "have a proper branch recipe!\n";401 return false;402 }403 } else {404 if (VPBB && VPBB->getTerminator()) {405 errs() << "Unexpected branch recipe!\n";406 return false;407 }408 }409 }410 411 // Check block's successors.412 const auto &Successors = VPB->getSuccessors();413 // There must be only one instance of a successor in block's successor list.414 // TODO: This won't work for switch statements.415 if (hasDuplicates(Successors)) {416 errs() << "Multiple instances of the same successor.\n";417 return false;418 }419 420 for (const VPBlockBase *Succ : Successors) {421 // There must be a bi-directional link between block and successor.422 const auto &SuccPreds = Succ->getPredecessors();423 if (!is_contained(SuccPreds, VPB)) {424 errs() << "Missing predecessor link.\n";425 return false;426 }427 }428 429 // Check block's predecessors.430 const auto &Predecessors = VPB->getPredecessors();431 // There must be only one instance of a predecessor in block's predecessor432 // list.433 // TODO: This won't work for switch statements.434 if (hasDuplicates(Predecessors)) {435 errs() << "Multiple instances of the same predecessor.\n";436 return false;437 }438 439 for (const VPBlockBase *Pred : Predecessors) {440 // Block and predecessor must be inside the same region.441 if (Pred->getParent() != VPB->getParent()) {442 errs() << "Predecessor is not in the same region.\n";443 return false;444 }445 446 // There must be a bi-directional link between block and predecessor.447 const auto &PredSuccs = Pred->getSuccessors();448 if (!is_contained(PredSuccs, VPB)) {449 errs() << "Missing successor link.\n";450 return false;451 }452 }453 return !VPBB || verifyVPBasicBlock(VPBB);454}455 456bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {457 for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {458 // Check block's parent.459 if (VPB->getParent() != Region) {460 errs() << "VPBlockBase has wrong parent\n";461 return false;462 }463 464 if (!verifyBlock(VPB))465 return false;466 }467 return true;468}469 470bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {471 const VPBlockBase *Entry = Region->getEntry();472 const VPBlockBase *Exiting = Region->getExiting();473 474 // Entry and Exiting shouldn't have any predecessor/successor, respectively.475 if (Entry->hasPredecessors()) {476 errs() << "region entry block has predecessors\n";477 return false;478 }479 if (Exiting->getNumSuccessors() != 0) {480 errs() << "region exiting block has successors\n";481 return false;482 }483 484 return verifyBlocksInRegion(Region);485}486 487bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {488 // Recurse inside nested regions and check all blocks inside the region.489 return verifyRegion(Region) &&490 all_of(vp_depth_first_shallow(Region->getEntry()),491 [this](const VPBlockBase *VPB) {492 const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB);493 return !SubRegion || verifyRegionRec(SubRegion);494 });495}496 497bool VPlanVerifier::verify(const VPlan &Plan) {498 if (any_of(vp_depth_first_shallow(Plan.getEntry()),499 [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))500 return false;501 502 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();503 // TODO: Verify all blocks using vp_depth_first_deep iterators.504 if (!TopRegion)505 return true;506 507 if (!verifyRegionRec(TopRegion))508 return false;509 510 if (TopRegion->getParent()) {511 errs() << "VPlan Top Region should have no parent.\n";512 return false;513 }514 515 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());516 if (!Entry) {517 errs() << "VPlan entry block is not a VPBasicBlock\n";518 return false;519 }520 521 if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {522 errs() << "VPlan vector loop header does not start with a "523 "VPCanonicalIVPHIRecipe\n";524 return false;525 }526 527 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());528 if (!Exiting) {529 errs() << "VPlan exiting block is not a VPBasicBlock\n";530 return false;531 }532 533 if (Exiting->empty()) {534 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "535 "BranchOnCond VPInstruction but is empty\n";536 return false;537 }538 539 auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));540 if (!match(LastInst, m_CombineOr(m_BranchOnCond(), m_BranchOnCount()))) {541 errs() << "VPlan vector loop exit must end with BranchOnCount or "542 "BranchOnCond VPInstruction\n";543 return false;544 }545 546 return true;547}548 549bool llvm::verifyVPlanIsValid(const VPlan &Plan, bool VerifyLate) {550 VPDominatorTree VPDT(const_cast<VPlan &>(Plan));551 VPTypeAnalysis TypeInfo(Plan);552 VPlanVerifier Verifier(VPDT, TypeInfo, VerifyLate);553 return Verifier.verify(Plan);554}555