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