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
24#define DEBUG_TYPE "loop-vectorize"
25
26using namespace llvm;
27using namespace VPlanPatternMatch;
28
29namespace {
30class VPlanVerifier {
31 const VPDominatorTree &VPDT;
32
33 SmallPtrSet<BasicBlock *, 8> WrappedIRBBs;
34
35 // Verify that phi-like recipes are at the beginning of \p VPBB, with no
36 // other recipes in between. Also check that only header blocks contain
37 // VPHeaderPHIRecipes.
38 bool verifyPhiRecipes(const VPBasicBlock *VPBB);
39
40 /// Verify that \p LastActiveLane's operand is guaranteed to be a prefix-mask.
41 bool verifyLastActiveLaneRecipe(const VPInstruction &LastActiveLane) 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
61public:
62 VPlanVerifier(VPDominatorTree &VPDT) : VPDT(VPDT) {}
63
64 bool verify(const VPlan &Plan);
65};
66} // namespace
67
68bool VPlanVerifier::verifyPhiRecipes(const VPBasicBlock *VPBB) {
69 auto RecipeI = VPBB->begin();
70 auto End = VPBB->end();
71 unsigned NumActiveLaneMaskPhiRecipes = 0;
72 bool IsHeaderVPBB = VPBlockUtils::isHeader(VPB: VPBB, VPDT);
73 while (RecipeI != End && RecipeI->isPhi()) {
74 if (isa<VPActiveLaneMaskPHIRecipe>(Val: RecipeI))
75 NumActiveLaneMaskPhiRecipes++;
76
77 if (IsHeaderVPBB &&
78 !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPhi>(Val: *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>(Val: *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 // In region form, VPCurrentIterationPHIRecipe must be the first header phi
97 // recipe. In a plain CFG VPlan, it must either be the first or second.
98 if (isa<VPCurrentIterationPHIRecipe>(Val: RecipeI) &&
99 (VPBB->getPlan()->getVectorLoopRegion()
100 ? RecipeI->getIterator() != VPBB->begin()
101 : RecipeI->getIterator() != VPBB->begin() &&
102 RecipeI->getIterator() != std::next(x: VPBB->begin()))) {
103 errs() << "CurrentIteration PHI is not the first/second recipe\n";
104 return false;
105 }
106
107 // Check if the recipe operands match the number of predecessors.
108 // TODO Extend to other phi-like recipes.
109 if (auto *PhiIRI = dyn_cast<VPIRPhi>(Val: &*RecipeI)) {
110 if (PhiIRI->getNumOperands() != VPBB->getNumPredecessors()) {
111 errs() << "Phi-like recipe with different number of operands and "
112 "predecessors.\n";
113 // TODO: Print broken recipe. At the moment printing an ill-formed
114 // phi-like recipe may crash.
115 return false;
116 }
117 }
118
119 RecipeI++;
120 }
121
122 if (!VPBB->getPlan()->isUnrolled() && NumActiveLaneMaskPhiRecipes > 1) {
123 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
124 return false;
125 }
126
127 while (RecipeI != End) {
128 if (RecipeI->isPhi() && !isa<VPBlendRecipe>(Val: &*RecipeI)) {
129 errs() << "Found phi-like recipe after non-phi recipe";
130
131#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
132 errs() << ": ";
133 RecipeI->dump();
134 errs() << "after\n";
135 std::prev(RecipeI)->dump();
136#endif
137 return false;
138 }
139 RecipeI++;
140 }
141 return true;
142}
143
144static bool isKnownMonotonic(VPValue *V) {
145 VPValue *X, *Y;
146 if (match(V, P: m_Add(Op0: m_VPValue(V&: X), Op1: m_VPValue(V&: Y))))
147 return cast<VPRecipeWithIRFlags>(Val: V)->hasNoUnsignedWrap() &&
148 isKnownMonotonic(V: X) && isKnownMonotonic(V: Y);
149 if (match(V, P: m_StepVector()))
150 return true;
151 // Only handle a subset of IVs until we can guarantee there's no overflow.
152 if (auto *WidenIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(Val: V))
153 return WidenIV->isCanonical() || WidenIV->hasNoUnsignedWrap();
154 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: V))
155 return match(V: Steps->getOperand(N: 0),
156 P: m_CombineOr(
157 Ps: m_CanonicalIV(),
158 Ps: m_DerivedIV(Op0: m_ZeroInt(), Op1: m_CanonicalIV(), Op2: m_One()))) &&
159 match(V: Steps->getStepValue(), P: m_One());
160 if (isa<VPWidenCanonicalIVRecipe>(Val: V))
161 return true;
162 return vputils::isUniformAcrossVFsAndUFs(V);
163}
164
165bool VPlanVerifier::verifyLastActiveLaneRecipe(
166 const VPInstruction &LastActiveLane) const {
167 assert(LastActiveLane.getOpcode() == VPInstruction::LastActiveLane &&
168 "must be called with VPInstruction::LastActiveLane");
169
170 if (LastActiveLane.getNumOperands() < 1) {
171 errs() << "LastActiveLane must have at least one operand\n";
172 return false;
173 }
174
175 // All operands must be prefix-mask. This means an icmp ult/ule LHS, RHS where
176 // the LHS is monotonically increasing and RHS is uniform across VFs and UF.
177 for (VPValue *Op : LastActiveLane.operands()) {
178 VPValue *Mask = Op;
179 VPValue *HeaderMask;
180
181 // Look through any `and`s with the incoming alias mask or a
182 // loop_dependence_war_mask, which are always prefix masks.
183 // TODO: Verify the full loop.dependence.mask chain.
184 if (match(V: Op,
185 P: m_c_BinaryAnd(
186 Op0: m_VPValue(V&: HeaderMask),
187 Op1: m_CombineOr(
188 Ps: m_c_BinaryAnd(
189 Op0: m_Intrinsic<Intrinsic::loop_dependence_war_mask>(),
190 Op1: m_VPValue()),
191 Ps: m_Intrinsic<Intrinsic::loop_dependence_war_mask>(),
192 Ps: m_VPInstruction<VPInstruction::IncomingAliasMask>()))))
193 Mask = HeaderMask;
194
195 // The header mask is a prefix mask. Before being materialized it is the
196 // loop region's abstract header mask; afterwards it is an active lane mask
197 // (an intrinsic or a phi), or the icmp checked below.
198 if (match(V: Mask, P: m_HeaderMask()) || isa<VPActiveLaneMaskPHIRecipe>(Val: Mask) ||
199 match(V: Mask, P: m_VPInstruction<VPInstruction::ActiveLaneMask>()))
200 continue;
201
202 CmpPredicate Pred;
203 VPValue *LHS, *RHS;
204 if (match(V: Mask, P: m_ICmp(Pred, Op0: m_VPValue(V&: LHS), Op1: m_VPValue(V&: RHS))) &&
205 (Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT) &&
206 isKnownMonotonic(V: LHS) &&
207 (vputils::isUniformAcrossVFsAndUFs(V: RHS) ||
208 match(V: RHS, P: m_EVL(Op0: m_VPValue()))))
209 continue;
210
211 errs() << "LastActiveLane operand ";
212#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
213 VPSlotTracker Tracker(LastActiveLane.getParent()->getPlan());
214 Op->printAsOperand(errs(), Tracker);
215#endif
216 errs() << " must be prefix mask (a header mask or an "
217 "EVL-derived mask currently)\n";
218 return false;
219 }
220
221 return true;
222}
223
224bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {
225 if (!verifyPhiRecipes(VPBB))
226 return false;
227
228 // Verify that defs in VPBB dominate all their uses.
229 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
230 unsigned Cnt = 0;
231 for (const VPRecipeBase &R : *VPBB)
232 RecipeNumbering[&R] = Cnt++;
233
234 for (const VPRecipeBase &R : *VPBB) {
235 if (isa<VPIRInstruction>(Val: &R) && !isa<VPIRBasicBlock>(Val: VPBB)) {
236 errs() << "VPIRInstructions ";
237#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
238 R.dump();
239 errs() << " ";
240#endif
241 errs() << "not in a VPIRBasicBlock!\n";
242 return false;
243 }
244 for (const VPValue *V : R.definedValues()) {
245 // Verify that each defined value has a scalar type.
246 if (!V->getScalarType()) {
247 errs() << "VPValue without scalar type!\n";
248 return false;
249 }
250
251 // MaskedCond may be used from blocks it don't dominate; the block will be
252 // linearized and it will dominate its users after linearization.
253 if (match(V: &R, P: m_VPInstruction<VPInstruction::MaskedCond>()))
254 continue;
255
256 for (const VPUser *U : V->users()) {
257 auto *UI = cast<VPRecipeBase>(Val: U);
258 if (isa<VPIRPhi>(Val: UI) &&
259 UI->getNumOperands() != UI->getParent()->getNumPredecessors()) {
260 errs() << "Phi-like recipe with different number of operands and "
261 "predecessors.\n";
262 return false;
263 }
264
265 if (auto *Phi = dyn_cast<VPPhiAccessors>(Val: UI)) {
266 for (const auto &[IncomingVPV, IncomingVPBB] :
267 Phi->incoming_values_and_blocks()) {
268 if (IncomingVPV != V)
269 continue;
270
271 if (VPDT.dominates(A: VPBB, B: IncomingVPBB))
272 continue;
273
274 errs() << "Incoming def does not dominate incoming block!\n";
275#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
276 VPSlotTracker Tracker(VPBB->getPlan());
277 IncomingVPV->getDefiningRecipe()->print(errs(), " ", Tracker);
278 errs() << "\n does not dominate " << IncomingVPBB->getName()
279 << " for\n";
280 UI->print(errs(), " ", Tracker);
281#endif
282 return false;
283 }
284 continue;
285 }
286 // TODO: Also verify VPPredInstPHIRecipe.
287 if (isa<VPPredInstPHIRecipe>(Val: UI))
288 continue;
289
290 // If the user is in the same block, check it comes after R in the
291 // block.
292 if (UI->getParent() == VPBB) {
293 if (RecipeNumbering[UI] >= RecipeNumbering[&R])
294 continue;
295 } else {
296 if (VPDT.dominates(A: VPBB, B: UI->getParent()))
297 continue;
298 }
299
300 // Recipes in blocks with a MaskedCond may be used in exit blocks; the
301 // block will be linearized and its recipes will dominate their users
302 // after linearization.
303 bool BlockHasMaskedCond = any_of(Range: *VPBB, P: [](const VPRecipeBase &R) {
304 return match(V: &R, P: m_VPInstruction<VPInstruction::MaskedCond>());
305 });
306 if (BlockHasMaskedCond &&
307 any_of(Range: VPBB->getPlan()->getExitBlocks(), P: [UI](VPIRBasicBlock *EB) {
308 return is_contained(Range&: EB->getPredecessors(), Element: UI->getParent());
309 })) {
310 continue;
311 }
312
313 errs() << "Use before def!\n";
314#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
315 VPSlotTracker Tracker(VPBB->getPlan());
316 UI->print(errs(), " ", Tracker);
317 errs() << "\n before\n";
318 R.print(errs(), " ", Tracker);
319 errs() << "\n";
320#endif
321 return false;
322 }
323 }
324 if (const auto *VPI = dyn_cast<VPInstruction>(Val: &R)) {
325 switch (VPI->getOpcode()) {
326 case VPInstruction::LastActiveLane:
327 if (!verifyLastActiveLaneRecipe(LastActiveLane: *VPI))
328 return false;
329 break;
330 default:
331 break;
332 }
333 }
334 if (const auto *DIV = dyn_cast<VPDerivedIVRecipe>(Val: &R)) {
335 if (!DIV->getStartValue()->isDefinedOutsideLoopRegions()) {
336 errs() << "VPDerivedIVRecipe must have start value defined outside "
337 "loop regions\n";
338 return false;
339 }
340 }
341 if (const auto *ScalarIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: &R)) {
342 unsigned NumOps = ScalarIVSteps->getNumOperands();
343 if (NumOps != 3 && NumOps != 4) {
344 errs() << "VPScalarIVStepsRecipe must have 3 or 4 operands\n";
345 return false;
346 }
347 }
348 }
349
350 auto *IRBB = dyn_cast<VPIRBasicBlock>(Val: VPBB);
351 if (!IRBB)
352 return true;
353
354 if (!WrappedIRBBs.insert(Ptr: IRBB->getIRBasicBlock()).second) {
355 errs() << "Same IR basic block used by multiple wrapper blocks!\n";
356 return false;
357 }
358
359 return true;
360}
361
362bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
363 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
364 // Check block's condition bit.
365 if (VPBB && !isa<VPIRBasicBlock>(Val: VPB)) {
366 // For plain CFG VPlans, verify header and latch block structure.
367 if (!VPBB->getParent()) {
368 if (VPBlockUtils::isHeader(VPB: VPBB, VPDT)) {
369 if (VPB->getNumPredecessors() != 2) {
370 errs()
371 << "Header block in plain CFG VPlan must have 2 predecessors!\n";
372 return false;
373 }
374 // Predecessor 0 is preheader, predecessor 1 is latch.
375 if (!VPBlockUtils::isLatch(VPB: VPB->getPredecessors()[1], VPDT)) {
376 errs() << "Header's second predecessor must be the latch!\n";
377 return false;
378 }
379 }
380
381 if (VPBlockUtils::isLatch(VPB: VPBB, VPDT)) {
382 if (!match(V: VPBB->getTerminator(), P: m_Branch())) {
383 errs() << "Latch block must have a branch terminator!\n";
384 return false;
385 }
386 // Successor 0 is middle block, successor 1 is header.
387 if (VPBlockUtils::isHeader(VPB: VPB->getSuccessors()[0], VPDT)) {
388 errs() << "Latch's first successor must not be the header (must be "
389 "middle block)!\n";
390 return false;
391 }
392 }
393 } else if (VPB->getNumSuccessors() > 1 ||
394 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {
395 if (!VPBB->getTerminator()) {
396 errs() << "Block has multiple successors but doesn't "
397 "have a proper branch recipe!\n";
398 return false;
399 }
400 } else if (VPBB->getTerminator()) {
401 errs() << "Unexpected branch recipe!\n";
402 return false;
403 }
404 }
405
406 // Check block's successors.
407 const auto &Successors = VPB->getSuccessors();
408 for (const VPBlockBase *Succ : Successors) {
409 // There must be a bi-directional link between block and successor.
410 const auto &SuccPreds = Succ->getPredecessors();
411 if (!is_contained(Range: SuccPreds, Element: VPB)) {
412 errs() << "Missing predecessor link.\n";
413 return false;
414 }
415 }
416
417 // Check block's predecessors.
418 const auto &Predecessors = VPB->getPredecessors();
419
420 for (const VPBlockBase *Pred : Predecessors) {
421 // Block and predecessor must be inside the same region.
422 if (Pred->getParent() != VPB->getParent()) {
423 errs() << "Predecessor is not in the same region.\n";
424 return false;
425 }
426
427 // There must be a bi-directional link between block and predecessor.
428 const auto &PredSuccs = Pred->getSuccessors();
429 if (!is_contained(Range: PredSuccs, Element: VPB)) {
430 errs() << "Missing successor link.\n";
431 return false;
432 }
433 }
434 return !VPBB || verifyVPBasicBlock(VPBB);
435}
436
437bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {
438 for (const VPBlockBase *VPB : vp_depth_first_shallow(G: Region->getEntry())) {
439 // Check block's parent.
440 if (VPB->getParent() != Region) {
441 errs() << "VPBlockBase has wrong parent\n";
442 return false;
443 }
444
445 if (!verifyBlock(VPB))
446 return false;
447 }
448 return true;
449}
450
451bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {
452 const VPBlockBase *Entry = Region->getEntry();
453 const VPBlockBase *Exiting = Region->getExiting();
454
455 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
456 if (Entry->hasPredecessors()) {
457 errs() << "region entry block has predecessors\n";
458 return false;
459 }
460 if (Exiting->getNumSuccessors() != 0) {
461 errs() << "region exiting block has successors\n";
462 return false;
463 }
464
465 return verifyBlocksInRegion(Region);
466}
467
468bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
469 // Recurse inside nested regions and check all blocks inside the region.
470 return verifyRegion(Region) &&
471 all_of(Range: vp_depth_first_shallow(G: Region->getEntry()),
472 P: [this](const VPBlockBase *VPB) {
473 const auto *SubRegion = dyn_cast<VPRegionBlock>(Val: VPB);
474 return !SubRegion || verifyRegionRec(Region: SubRegion);
475 });
476}
477
478bool VPlanVerifier::verify(const VPlan &Plan) {
479 if (any_of(Range: vp_depth_first_shallow(G: Plan.getEntry()),
480 P: [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
481 return false;
482
483 // Check that the plan has a single loop region reachable from entry, and it
484 // matches the one returned by getVectorLoopRegion.
485 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
486 if (any_of(Range: VPBlockUtils::blocksOnly<const VPRegionBlock>(
487 Range: vp_depth_first_shallow(G: Plan.getEntry())),
488 P: [TopRegion](const VPRegionBlock *R) {
489 return !R->isReplicator() && R != TopRegion;
490 })) {
491 errs() << "VPlan must have a single top-level loop region, reachable from "
492 "the entry by following the last successor of each block\n";
493 return false;
494 }
495
496 // TODO: Verify all blocks using vp_depth_first_deep iterators.
497 if (!TopRegion)
498 return true;
499
500 if (!verifyRegionRec(Region: TopRegion))
501 return false;
502
503 if (TopRegion->getParent()) {
504 errs() << "VPlan Top Region should have no parent.\n";
505 return false;
506 }
507
508 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(Val: TopRegion->getEntry());
509 if (!Entry) {
510 errs() << "VPlan entry block is not a VPBasicBlock\n";
511 return false;
512 }
513
514 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(Val: TopRegion->getExiting());
515 if (!Exiting) {
516 errs() << "VPlan exiting block is not a VPBasicBlock\n";
517 return false;
518 }
519
520 if (Exiting->empty()) {
521 errs() << "VPlan vector loop exiting block must end with BranchOnCount, "
522 "BranchOnCond, or BranchOnTwoConds VPInstruction but is empty\n";
523 return false;
524 }
525
526 auto *LastInst = dyn_cast<VPInstruction>(Val: std::prev(x: Exiting->end()));
527 if (!match(V: LastInst, P: m_Branch())) {
528 errs() << "VPlan vector loop exit must end with BranchOnCount, "
529 "BranchOnCond, or BranchOnTwoConds VPInstruction\n";
530 return false;
531 }
532
533 return true;
534}
535
536bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
537 // The entry must be the root of the plan's top-level CFG: the dominator tree
538 // constructed below and the verifier's block walks all start there.
539 if (Plan.getEntry()->hasPredecessors()) {
540 errs() << "VPlan entry block has predecessors\n";
541 return false;
542 }
543
544 VPDominatorTree VPDT(const_cast<VPlan &>(Plan));
545 VPlanVerifier Verifier(VPDT);
546 return Verifier.verify(Plan);
547}
548