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