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
142bool VPlanVerifier::verifyLastActiveLaneRecipe(
143 const VPInstruction &LastActiveLane) const {
144 assert(LastActiveLane.getOpcode() == VPInstruction::LastActiveLane &&
145 "must be called with VPInstruction::LastActiveLane");
146
147 if (LastActiveLane.getNumOperands() < 1) {
148 errs() << "LastActiveLane must have at least one operand\n";
149 return false;
150 }
151
152 const VPlan &Plan = *LastActiveLane.getParent()->getPlan();
153 // All operands must be prefix-mask. Currently we check for header masks or
154 // EVL-derived masks, as those are currently the only operands in practice,
155 // but this may need updating in the future.
156 for (VPValue *Op : LastActiveLane.operands()) {
157 if (vputils::isHeaderMask(V: Op, Plan))
158 continue;
159
160 // Masks derived from EVL are also fine.
161 auto BroadcastOrEVL =
162 m_CombineOr(L: m_Broadcast(Op0: m_EVL(Op0: m_VPValue())), R: m_EVL(Op0: m_VPValue()));
163 if (match(V: Op, P: m_CombineOr(L: m_ICmp(Op0: m_StepVector(), Op1: BroadcastOrEVL),
164 R: m_ICmp(Op0: BroadcastOrEVL, Op1: m_StepVector()))))
165 continue;
166
167 errs() << "LastActiveLane operand ";
168#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
169 VPSlotTracker Tracker(&Plan);
170 Op->printAsOperand(errs(), Tracker);
171#endif
172 errs() << " must be prefix mask (a header mask or an "
173 "EVL-derived mask currently)\n";
174 return false;
175 }
176
177 return true;
178}
179
180bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {
181 if (!verifyPhiRecipes(VPBB))
182 return false;
183
184 // Verify that defs in VPBB dominate all their uses.
185 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
186 unsigned Cnt = 0;
187 for (const VPRecipeBase &R : *VPBB)
188 RecipeNumbering[&R] = Cnt++;
189
190 for (const VPRecipeBase &R : *VPBB) {
191 if (isa<VPIRInstruction>(Val: &R) && !isa<VPIRBasicBlock>(Val: VPBB)) {
192 errs() << "VPIRInstructions ";
193#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
194 R.dump();
195 errs() << " ";
196#endif
197 errs() << "not in a VPIRBasicBlock!\n";
198 return false;
199 }
200 for (const VPValue *V : R.definedValues()) {
201 // Verify that we can infer a scalar type for each defined value. With
202 // assertions enabled, inferScalarType will perform some consistency
203 // checks during type inference.
204 if (!TypeInfo.inferScalarType(V)) {
205 errs() << "Failed to infer scalar type!\n";
206 return false;
207 }
208
209 for (const VPUser *U : V->users()) {
210 auto *UI = cast<VPRecipeBase>(Val: U);
211 if (isa<VPIRPhi>(Val: UI) &&
212 UI->getNumOperands() != UI->getParent()->getNumPredecessors()) {
213 errs() << "Phi-like recipe with different number of operands and "
214 "predecessors.\n";
215 return false;
216 }
217
218 if (auto *Phi = dyn_cast<VPPhiAccessors>(Val: UI)) {
219 for (const auto &[IncomingVPV, IncomingVPBB] :
220 Phi->incoming_values_and_blocks()) {
221 if (IncomingVPV != V)
222 continue;
223
224 if (VPDT.dominates(A: VPBB, B: IncomingVPBB))
225 continue;
226
227 errs() << "Incoming def does not dominate incoming block!\n";
228#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
229 VPSlotTracker Tracker(VPBB->getPlan());
230 IncomingVPV->getDefiningRecipe()->print(errs(), " ", Tracker);
231 errs() << "\n does not dominate " << IncomingVPBB->getName()
232 << " for\n";
233 UI->print(errs(), " ", Tracker);
234#endif
235 return false;
236 }
237 continue;
238 }
239 // TODO: Also verify VPPredInstPHIRecipe.
240 if (isa<VPPredInstPHIRecipe>(Val: UI))
241 continue;
242
243 // If the user is in the same block, check it comes after R in the
244 // block.
245 if (UI->getParent() == VPBB) {
246 if (RecipeNumbering[UI] >= RecipeNumbering[&R])
247 continue;
248 } else {
249 if (VPDT.dominates(A: VPBB, B: UI->getParent()))
250 continue;
251 }
252
253 errs() << "Use before def!\n";
254#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
255 VPSlotTracker Tracker(VPBB->getPlan());
256 UI->print(errs(), " ", Tracker);
257 errs() << "\n before\n";
258 R.print(errs(), " ", Tracker);
259 errs() << "\n";
260#endif
261 return false;
262 }
263 }
264 if (const auto *VPI = dyn_cast<VPInstruction>(Val: &R)) {
265 switch (VPI->getOpcode()) {
266 case VPInstruction::LastActiveLane:
267 if (!verifyLastActiveLaneRecipe(LastActiveLane: *VPI))
268 return false;
269 break;
270 default:
271 break;
272 }
273 }
274 }
275
276 auto *IRBB = dyn_cast<VPIRBasicBlock>(Val: VPBB);
277 if (!IRBB)
278 return true;
279
280 if (!WrappedIRBBs.insert(Ptr: IRBB->getIRBasicBlock()).second) {
281 errs() << "Same IR basic block used by multiple wrapper blocks!\n";
282 return false;
283 }
284
285 return true;
286}
287
288/// Utility function that checks whether \p VPBlockVec has duplicate
289/// VPBlockBases.
290static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
291 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
292 for (const auto *Block : VPBlockVec) {
293 if (!VPBlockSet.insert(V: Block).second)
294 return true;
295 }
296 return false;
297}
298
299bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
300 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
301 // Check block's condition bit.
302 if (VPBB && !isa<VPIRBasicBlock>(Val: VPB)) {
303 if (VPB->getNumSuccessors() > 1 ||
304 (VPBB->getParent() && VPBB->isExiting() &&
305 !VPBB->getParent()->isReplicator())) {
306 if (!VPBB->getTerminator()) {
307 errs() << "Block has multiple successors but doesn't "
308 "have a proper branch recipe!\n";
309 return false;
310 }
311 } else if (VPBB->getTerminator()) {
312 errs() << "Unexpected branch recipe!\n";
313 return false;
314 }
315 }
316
317 // Check block's successors.
318 const auto &Successors = VPB->getSuccessors();
319 // There must be only one instance of a successor in block's successor list.
320 // TODO: This won't work for switch statements.
321 if (hasDuplicates(VPBlockVec: Successors)) {
322 errs() << "Multiple instances of the same successor.\n";
323 return false;
324 }
325
326 for (const VPBlockBase *Succ : Successors) {
327 // There must be a bi-directional link between block and successor.
328 const auto &SuccPreds = Succ->getPredecessors();
329 if (!is_contained(Range: SuccPreds, Element: VPB)) {
330 errs() << "Missing predecessor link.\n";
331 return false;
332 }
333 }
334
335 // Check block's predecessors.
336 const auto &Predecessors = VPB->getPredecessors();
337 // There must be only one instance of a predecessor in block's predecessor
338 // list.
339 // TODO: This won't work for switch statements.
340 if (hasDuplicates(VPBlockVec: Predecessors)) {
341 errs() << "Multiple instances of the same predecessor.\n";
342 return false;
343 }
344
345 for (const VPBlockBase *Pred : Predecessors) {
346 // Block and predecessor must be inside the same region.
347 if (Pred->getParent() != VPB->getParent()) {
348 errs() << "Predecessor is not in the same region.\n";
349 return false;
350 }
351
352 // There must be a bi-directional link between block and predecessor.
353 const auto &PredSuccs = Pred->getSuccessors();
354 if (!is_contained(Range: PredSuccs, Element: VPB)) {
355 errs() << "Missing successor link.\n";
356 return false;
357 }
358 }
359 return !VPBB || verifyVPBasicBlock(VPBB);
360}
361
362bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {
363 for (const VPBlockBase *VPB : vp_depth_first_shallow(G: Region->getEntry())) {
364 // Check block's parent.
365 if (VPB->getParent() != Region) {
366 errs() << "VPBlockBase has wrong parent\n";
367 return false;
368 }
369
370 if (!verifyBlock(VPB))
371 return false;
372 }
373 return true;
374}
375
376bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {
377 const VPBlockBase *Entry = Region->getEntry();
378 const VPBlockBase *Exiting = Region->getExiting();
379
380 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
381 if (Entry->hasPredecessors()) {
382 errs() << "region entry block has predecessors\n";
383 return false;
384 }
385 if (Exiting->getNumSuccessors() != 0) {
386 errs() << "region exiting block has successors\n";
387 return false;
388 }
389
390 return verifyBlocksInRegion(Region);
391}
392
393bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
394 // Recurse inside nested regions and check all blocks inside the region.
395 return verifyRegion(Region) &&
396 all_of(Range: vp_depth_first_shallow(G: Region->getEntry()),
397 P: [this](const VPBlockBase *VPB) {
398 const auto *SubRegion = dyn_cast<VPRegionBlock>(Val: VPB);
399 return !SubRegion || verifyRegionRec(Region: SubRegion);
400 });
401}
402
403bool VPlanVerifier::verify(const VPlan &Plan) {
404 if (any_of(Range: vp_depth_first_shallow(G: Plan.getEntry()),
405 P: [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
406 return false;
407
408 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
409 // TODO: Verify all blocks using vp_depth_first_deep iterators.
410 if (!TopRegion)
411 return true;
412
413 if (!verifyRegionRec(Region: TopRegion))
414 return false;
415
416 if (TopRegion->getParent()) {
417 errs() << "VPlan Top Region should have no parent.\n";
418 return false;
419 }
420
421 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(Val: TopRegion->getEntry());
422 if (!Entry) {
423 errs() << "VPlan entry block is not a VPBasicBlock\n";
424 return false;
425 }
426
427 if (!isa<VPCanonicalIVPHIRecipe>(Val: &*Entry->begin())) {
428 errs() << "VPlan vector loop header does not start with a "
429 "VPCanonicalIVPHIRecipe\n";
430 return false;
431 }
432
433 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(Val: TopRegion->getExiting());
434 if (!Exiting) {
435 errs() << "VPlan exiting block is not a VPBasicBlock\n";
436 return false;
437 }
438
439 if (Exiting->empty()) {
440 errs() << "VPlan vector loop exiting block must end with BranchOnCount, "
441 "BranchOnCond, or BranchOnTwoConds VPInstruction but is empty\n";
442 return false;
443 }
444
445 auto *LastInst = dyn_cast<VPInstruction>(Val: std::prev(x: Exiting->end()));
446 if (!match(V: LastInst, P: m_CombineOr(L: m_BranchOnCond(),
447 R: m_CombineOr(L: m_BranchOnCount(),
448 R: m_BranchOnTwoConds())))) {
449 errs() << "VPlan vector loop exit must end with BranchOnCount, "
450 "BranchOnCond, or BranchOnTwoConds VPInstruction\n";
451 return false;
452 }
453
454 return true;
455}
456
457bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
458 VPDominatorTree VPDT(const_cast<VPlan &>(Plan));
459 VPTypeAnalysis TypeInfo(Plan);
460 VPlanVerifier Verifier(VPDT, TypeInfo);
461 return Verifier.verify(Plan);
462}
463