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
35 SmallPtrSet<BasicBlock *, 8> WrappedIRBBs;
36
37 // Verify that phi-like recipes are at the beginning of \p VPBB, with no
38 // other recipes in between. Also check that only header blocks contain
39 // VPHeaderPHIRecipes.
40 bool verifyPhiRecipes(const VPBasicBlock *VPBB);
41
42 /// Verify that \p LastActiveLane's operand is guaranteed to be a prefix-mask.
43 bool verifyLastActiveLaneRecipe(const VPInstruction &LastActiveLane) const;
44
45 bool verifyVPBasicBlock(const VPBasicBlock *VPBB);
46
47 bool verifyBlock(const VPBlockBase *VPB);
48
49 /// Helper function that verifies the CFG invariants of the VPBlockBases
50 /// within
51 /// \p Region. Checks in this function are generic for VPBlockBases. They are
52 /// not specific for VPBasicBlocks or VPRegionBlocks.
53 bool verifyBlocksInRegion(const VPRegionBlock *Region);
54
55 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
56 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
57 bool verifyRegion(const VPRegionBlock *Region);
58
59 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
60 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
61 bool verifyRegionRec(const VPRegionBlock *Region);
62
63public:
64 VPlanVerifier(VPDominatorTree &VPDT, VPTypeAnalysis &TypeInfo)
65 : VPDT(VPDT), TypeInfo(TypeInfo) {}
66
67 bool verify(const VPlan &Plan);
68};
69} // namespace
70
71bool VPlanVerifier::verifyPhiRecipes(const VPBasicBlock *VPBB) {
72 auto RecipeI = VPBB->begin();
73 auto End = VPBB->end();
74 unsigned NumActiveLaneMaskPhiRecipes = 0;
75 bool IsHeaderVPBB = VPBlockUtils::isHeader(VPB: VPBB, VPDT);
76 while (RecipeI != End && RecipeI->isPhi()) {
77 if (isa<VPActiveLaneMaskPHIRecipe>(Val: RecipeI))
78 NumActiveLaneMaskPhiRecipes++;
79
80 if (IsHeaderVPBB &&
81 !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPhi>(Val: *RecipeI)) {
82 errs() << "Found non-header PHI recipe in header VPBB";
83#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
84 errs() << ": ";
85 RecipeI->dump();
86#endif
87 return false;
88 }
89
90 if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(Val: *RecipeI)) {
91 errs() << "Found header PHI recipe in non-header VPBB";
92#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
93 errs() << ": ";
94 RecipeI->dump();
95#endif
96 return false;
97 }
98
99 if (isa<VPCurrentIterationPHIRecipe>(Val: RecipeI) &&
100 !isa_and_nonnull<VPCanonicalIVPHIRecipe>(Val: std::prev(x: RecipeI))) {
101 errs() << "CurrentIteration PHI is not immediately after canonical IV\n";
102 return false;
103 }
104
105 // Check if the recipe operands match the number of predecessors.
106 // TODO Extend to other phi-like recipes.
107 if (auto *PhiIRI = dyn_cast<VPIRPhi>(Val: &*RecipeI)) {
108 if (PhiIRI->getNumOperands() != VPBB->getNumPredecessors()) {
109 errs() << "Phi-like recipe with different number of operands and "
110 "predecessors.\n";
111 // TODO: Print broken recipe. At the moment printing an ill-formed
112 // phi-like recipe may crash.
113 return false;
114 }
115 }
116
117 RecipeI++;
118 }
119
120 if (!VPBB->getPlan()->isUnrolled() && NumActiveLaneMaskPhiRecipes > 1) {
121 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
122 return false;
123 }
124
125 while (RecipeI != End) {
126 if (RecipeI->isPhi() && !isa<VPBlendRecipe>(Val: &*RecipeI)) {
127 errs() << "Found phi-like recipe after non-phi recipe";
128
129#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
130 errs() << ": ";
131 RecipeI->dump();
132 errs() << "after\n";
133 std::prev(RecipeI)->dump();
134#endif
135 return false;
136 }
137 RecipeI++;
138 }
139 return true;
140}
141
142static bool isKnownMonotonic(VPValue *V) {
143 VPValue *X, *Y;
144 if (match(V, P: m_Add(Op0: m_VPValue(V&: X), Op1: m_VPValue(V&: Y))))
145 return cast<VPRecipeWithIRFlags>(Val: V)->hasNoUnsignedWrap() &&
146 isKnownMonotonic(V: X) && isKnownMonotonic(V: Y);
147 if (match(V, P: m_StepVector()))
148 return true;
149 // Only handle a subset of IVs until we can guarantee there's no overflow.
150 if (auto *WidenIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(Val: V))
151 return WidenIV->isCanonical();
152 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: V))
153 return match(V: Steps->getOperand(N: 0),
154 P: m_CombineOr(
155 L: m_CanonicalIV(),
156 R: m_DerivedIV(Op0: m_ZeroInt(), Op1: m_CanonicalIV(), Op2: m_One()))) &&
157 match(V: Steps->getStepValue(), P: m_One());
158 if (isa<VPWidenCanonicalIVRecipe>(Val: V))
159 return true;
160 return vputils::isUniformAcrossVFsAndUFs(V);
161}
162
163bool VPlanVerifier::verifyLastActiveLaneRecipe(
164 const VPInstruction &LastActiveLane) const {
165 assert(LastActiveLane.getOpcode() == VPInstruction::LastActiveLane &&
166 "must be called with VPInstruction::LastActiveLane");
167
168 if (LastActiveLane.getNumOperands() < 1) {
169 errs() << "LastActiveLane must have at least one operand\n";
170 return false;
171 }
172
173 const VPlan &Plan = *LastActiveLane.getParent()->getPlan();
174 // All operands must be prefix-mask. This means an icmp ult/ule LHS, RHS where
175 // the LHS is monotonically increasing and RHS is uniform across VFs and UF.
176 for (VPValue *Op : LastActiveLane.operands()) {
177 if (vputils::isHeaderMask(V: Op, Plan))
178 continue;
179
180 CmpPredicate Pred;
181 VPValue *LHS, *RHS;
182 if (match(V: Op, P: m_ICmp(Pred, Op0: m_VPValue(V&: LHS), Op1: m_VPValue(V&: RHS))) &&
183 (Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT) &&
184 isKnownMonotonic(V: LHS) &&
185 (vputils::isUniformAcrossVFsAndUFs(V: RHS) ||
186 match(V: RHS, P: m_EVL(Op0: m_VPValue()))))
187 continue;
188
189 errs() << "LastActiveLane operand ";
190#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
191 VPSlotTracker Tracker(&Plan);
192 Op->printAsOperand(errs(), Tracker);
193#endif
194 errs() << " must be prefix mask (a header mask or an "
195 "EVL-derived mask currently)\n";
196 return false;
197 }
198
199 return true;
200}
201
202bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {
203 if (!verifyPhiRecipes(VPBB))
204 return false;
205
206 // Verify that defs in VPBB dominate all their uses.
207 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
208 unsigned Cnt = 0;
209 for (const VPRecipeBase &R : *VPBB)
210 RecipeNumbering[&R] = Cnt++;
211
212 for (const VPRecipeBase &R : *VPBB) {
213 if (isa<VPIRInstruction>(Val: &R) && !isa<VPIRBasicBlock>(Val: VPBB)) {
214 errs() << "VPIRInstructions ";
215#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
216 R.dump();
217 errs() << " ";
218#endif
219 errs() << "not in a VPIRBasicBlock!\n";
220 return false;
221 }
222 for (const VPValue *V : R.definedValues()) {
223 // Verify that we can infer a scalar type for each defined value. With
224 // assertions enabled, inferScalarType will perform some consistency
225 // checks during type inference.
226 if (!TypeInfo.inferScalarType(V)) {
227 errs() << "Failed to infer scalar type!\n";
228 return false;
229 }
230
231 for (const VPUser *U : V->users()) {
232 auto *UI = cast<VPRecipeBase>(Val: U);
233 if (isa<VPIRPhi>(Val: UI) &&
234 UI->getNumOperands() != UI->getParent()->getNumPredecessors()) {
235 errs() << "Phi-like recipe with different number of operands and "
236 "predecessors.\n";
237 return false;
238 }
239
240 if (auto *Phi = dyn_cast<VPPhiAccessors>(Val: UI)) {
241 for (const auto &[IncomingVPV, IncomingVPBB] :
242 Phi->incoming_values_and_blocks()) {
243 if (IncomingVPV != V)
244 continue;
245
246 if (VPDT.dominates(A: VPBB, B: IncomingVPBB))
247 continue;
248
249 errs() << "Incoming def does not dominate incoming block!\n";
250#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
251 VPSlotTracker Tracker(VPBB->getPlan());
252 IncomingVPV->getDefiningRecipe()->print(errs(), " ", Tracker);
253 errs() << "\n does not dominate " << IncomingVPBB->getName()
254 << " for\n";
255 UI->print(errs(), " ", Tracker);
256#endif
257 return false;
258 }
259 continue;
260 }
261 // TODO: Also verify VPPredInstPHIRecipe.
262 if (isa<VPPredInstPHIRecipe>(Val: UI))
263 continue;
264
265 // If the user is in the same block, check it comes after R in the
266 // block.
267 if (UI->getParent() == VPBB) {
268 if (RecipeNumbering[UI] >= RecipeNumbering[&R])
269 continue;
270 } else {
271 if (VPDT.dominates(A: VPBB, B: UI->getParent()))
272 continue;
273 }
274
275 errs() << "Use before def!\n";
276#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
277 VPSlotTracker Tracker(VPBB->getPlan());
278 UI->print(errs(), " ", Tracker);
279 errs() << "\n before\n";
280 R.print(errs(), " ", Tracker);
281 errs() << "\n";
282#endif
283 return false;
284 }
285 }
286 if (const auto *VPI = dyn_cast<VPInstruction>(Val: &R)) {
287 switch (VPI->getOpcode()) {
288 case VPInstruction::LastActiveLane:
289 if (!verifyLastActiveLaneRecipe(LastActiveLane: *VPI))
290 return false;
291 break;
292 default:
293 break;
294 }
295 }
296 if (const auto *ScalarIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: &R)) {
297 unsigned NumOps = ScalarIVSteps->getNumOperands();
298 if (NumOps != 3 && NumOps != 4) {
299 errs() << "VPScalarIVStepsRecipe must have 3 or 4 operands\n";
300 return false;
301 }
302 }
303 }
304
305 auto *IRBB = dyn_cast<VPIRBasicBlock>(Val: VPBB);
306 if (!IRBB)
307 return true;
308
309 if (!WrappedIRBBs.insert(Ptr: IRBB->getIRBasicBlock()).second) {
310 errs() << "Same IR basic block used by multiple wrapper blocks!\n";
311 return false;
312 }
313
314 return true;
315}
316
317/// Utility function that checks whether \p VPBlockVec has duplicate
318/// VPBlockBases.
319static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
320 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
321 for (const auto *Block : VPBlockVec) {
322 if (!VPBlockSet.insert(V: Block).second)
323 return true;
324 }
325 return false;
326}
327
328bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
329 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
330 // Check block's condition bit.
331 if (VPBB && !isa<VPIRBasicBlock>(Val: VPB)) {
332 if (VPB->getNumSuccessors() > 1 ||
333 (VPBB->getParent() && VPBB->isExiting() &&
334 !VPBB->getParent()->isReplicator())) {
335 if (!VPBB->getTerminator()) {
336 errs() << "Block has multiple successors but doesn't "
337 "have a proper branch recipe!\n";
338 return false;
339 }
340 } else if (VPBB->getTerminator()) {
341 errs() << "Unexpected branch recipe!\n";
342 return false;
343 }
344 }
345
346 // Check block's successors.
347 const auto &Successors = VPB->getSuccessors();
348 // There must be only one instance of a successor in block's successor list.
349 // TODO: This won't work for switch statements.
350 if (hasDuplicates(VPBlockVec: Successors)) {
351 errs() << "Multiple instances of the same successor.\n";
352 return false;
353 }
354
355 for (const VPBlockBase *Succ : Successors) {
356 // There must be a bi-directional link between block and successor.
357 const auto &SuccPreds = Succ->getPredecessors();
358 if (!is_contained(Range: SuccPreds, Element: VPB)) {
359 errs() << "Missing predecessor link.\n";
360 return false;
361 }
362 }
363
364 // Check block's predecessors.
365 const auto &Predecessors = VPB->getPredecessors();
366 // There must be only one instance of a predecessor in block's predecessor
367 // list.
368 // TODO: This won't work for switch statements.
369 if (hasDuplicates(VPBlockVec: Predecessors)) {
370 errs() << "Multiple instances of the same predecessor.\n";
371 return false;
372 }
373
374 for (const VPBlockBase *Pred : Predecessors) {
375 // Block and predecessor must be inside the same region.
376 if (Pred->getParent() != VPB->getParent()) {
377 errs() << "Predecessor is not in the same region.\n";
378 return false;
379 }
380
381 // There must be a bi-directional link between block and predecessor.
382 const auto &PredSuccs = Pred->getSuccessors();
383 if (!is_contained(Range: PredSuccs, Element: VPB)) {
384 errs() << "Missing successor link.\n";
385 return false;
386 }
387 }
388 return !VPBB || verifyVPBasicBlock(VPBB);
389}
390
391bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {
392 for (const VPBlockBase *VPB : vp_depth_first_shallow(G: Region->getEntry())) {
393 // Check block's parent.
394 if (VPB->getParent() != Region) {
395 errs() << "VPBlockBase has wrong parent\n";
396 return false;
397 }
398
399 if (!verifyBlock(VPB))
400 return false;
401 }
402 return true;
403}
404
405bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {
406 const VPBlockBase *Entry = Region->getEntry();
407 const VPBlockBase *Exiting = Region->getExiting();
408
409 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
410 if (Entry->hasPredecessors()) {
411 errs() << "region entry block has predecessors\n";
412 return false;
413 }
414 if (Exiting->getNumSuccessors() != 0) {
415 errs() << "region exiting block has successors\n";
416 return false;
417 }
418
419 return verifyBlocksInRegion(Region);
420}
421
422bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
423 // Recurse inside nested regions and check all blocks inside the region.
424 return verifyRegion(Region) &&
425 all_of(Range: vp_depth_first_shallow(G: Region->getEntry()),
426 P: [this](const VPBlockBase *VPB) {
427 const auto *SubRegion = dyn_cast<VPRegionBlock>(Val: VPB);
428 return !SubRegion || verifyRegionRec(Region: SubRegion);
429 });
430}
431
432bool VPlanVerifier::verify(const VPlan &Plan) {
433 if (any_of(Range: vp_depth_first_shallow(G: Plan.getEntry()),
434 P: [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
435 return false;
436
437 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
438 // TODO: Verify all blocks using vp_depth_first_deep iterators.
439 if (!TopRegion)
440 return true;
441
442 if (!verifyRegionRec(Region: TopRegion))
443 return false;
444
445 if (TopRegion->getParent()) {
446 errs() << "VPlan Top Region should have no parent.\n";
447 return false;
448 }
449
450 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(Val: TopRegion->getEntry());
451 if (!Entry) {
452 errs() << "VPlan entry block is not a VPBasicBlock\n";
453 return false;
454 }
455
456 if (!isa<VPCanonicalIVPHIRecipe>(Val: &*Entry->begin())) {
457 errs() << "VPlan vector loop header does not start with a "
458 "VPCanonicalIVPHIRecipe\n";
459 return false;
460 }
461
462 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(Val: TopRegion->getExiting());
463 if (!Exiting) {
464 errs() << "VPlan exiting block is not a VPBasicBlock\n";
465 return false;
466 }
467
468 if (Exiting->empty()) {
469 errs() << "VPlan vector loop exiting block must end with BranchOnCount, "
470 "BranchOnCond, or BranchOnTwoConds VPInstruction but is empty\n";
471 return false;
472 }
473
474 auto *LastInst = dyn_cast<VPInstruction>(Val: std::prev(x: Exiting->end()));
475 if (!match(V: LastInst, P: m_CombineOr(L: m_BranchOnCond(),
476 R: m_CombineOr(L: m_BranchOnCount(),
477 R: m_BranchOnTwoConds())))) {
478 errs() << "VPlan vector loop exit must end with BranchOnCount, "
479 "BranchOnCond, or BranchOnTwoConds VPInstruction\n";
480 return false;
481 }
482
483 return true;
484}
485
486bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
487 VPDominatorTree VPDT(const_cast<VPlan &>(Plan));
488 VPTypeAnalysis TypeInfo(Plan);
489 VPlanVerifier Verifier(VPDT, TypeInfo);
490 return Verifier.verify(Plan);
491}
492