LLVM 20.0.0git
VPlanVerifier.cpp
Go to the documentation of this file.
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"
22
23#define DEBUG_TYPE "loop-vectorize"
24
25using namespace llvm;
26
27namespace {
28class VPlanVerifier {
29 const VPDominatorTree &VPDT;
30
32
33 // Verify that phi-like recipes are at the beginning of \p VPBB, with no
34 // other recipes in between. Also check that only header blocks contain
35 // VPHeaderPHIRecipes.
36 bool verifyPhiRecipes(const VPBasicBlock *VPBB);
37
38 bool verifyVPBasicBlock(const VPBasicBlock *VPBB);
39
40 bool verifyBlock(const VPBlockBase *VPB);
41
42 /// Helper function that verifies the CFG invariants of the VPBlockBases
43 /// within
44 /// \p Region. Checks in this function are generic for VPBlockBases. They are
45 /// not specific for VPBasicBlocks or VPRegionBlocks.
46 bool verifyBlocksInRegion(const VPRegionBlock *Region);
47
48 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
49 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
50 bool verifyRegion(const VPRegionBlock *Region);
51
52 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
53 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
54 bool verifyRegionRec(const VPRegionBlock *Region);
55
56public:
57 VPlanVerifier(VPDominatorTree &VPDT) : VPDT(VPDT) {}
58
59 bool verify(const VPlan &Plan);
60};
61} // namespace
62
63bool VPlanVerifier::verifyPhiRecipes(const VPBasicBlock *VPBB) {
64 auto RecipeI = VPBB->begin();
65 auto End = VPBB->end();
66 unsigned NumActiveLaneMaskPhiRecipes = 0;
67 const VPRegionBlock *ParentR = VPBB->getParent();
68 bool IsHeaderVPBB = ParentR && !ParentR->isReplicator() &&
69 ParentR->getEntryBasicBlock() == VPBB;
70 while (RecipeI != End && RecipeI->isPhi()) {
71 if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))
72 NumActiveLaneMaskPhiRecipes++;
73
74 if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe>(*RecipeI)) {
75 errs() << "Found non-header PHI recipe in header VPBB";
76#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
77 errs() << ": ";
78 RecipeI->dump();
79#endif
80 return false;
81 }
82
83 if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {
84 errs() << "Found header PHI recipe in non-header VPBB";
85#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
86 errs() << ": ";
87 RecipeI->dump();
88#endif
89 return false;
90 }
91
92 RecipeI++;
93 }
94
95 if (NumActiveLaneMaskPhiRecipes > 1) {
96 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
97 return false;
98 }
99
100 while (RecipeI != End) {
101 if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
102 errs() << "Found phi-like recipe after non-phi recipe";
103
104#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
105 errs() << ": ";
106 RecipeI->dump();
107 errs() << "after\n";
108 std::prev(RecipeI)->dump();
109#endif
110 return false;
111 }
112 RecipeI++;
113 }
114 return true;
115}
116
117bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {
118 if (!verifyPhiRecipes(VPBB))
119 return false;
120
121 // Verify that defs in VPBB dominate all their uses. The current
122 // implementation is still incomplete.
124 unsigned Cnt = 0;
125 for (const VPRecipeBase &R : *VPBB)
126 RecipeNumbering[&R] = Cnt++;
127
128 for (const VPRecipeBase &R : *VPBB) {
129 for (const VPValue *V : R.definedValues()) {
130 for (const VPUser *U : V->users()) {
131 auto *UI = dyn_cast<VPRecipeBase>(U);
132 // TODO: check dominance of incoming values for phis properly.
133 if (!UI ||
134 isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPredInstPHIRecipe>(UI))
135 continue;
136
137 // If the user is in the same block, check it comes after R in the
138 // block.
139 if (UI->getParent() == VPBB) {
140 if (RecipeNumbering[UI] < RecipeNumbering[&R]) {
141 errs() << "Use before def!\n";
142 return false;
143 }
144 continue;
145 }
146
147 if (!VPDT.dominates(VPBB, UI->getParent())) {
148 errs() << "Use before def!\n";
149 return false;
150 }
151 }
152 }
153 }
154
155 auto *IRBB = dyn_cast<VPIRBasicBlock>(VPBB);
156 if (!IRBB)
157 return true;
158
159 if (!WrappedIRBBs.insert(IRBB->getIRBasicBlock()).second) {
160 errs() << "Same IR basic block used by multiple wrapper blocks!\n";
161 return false;
162 }
163
164 VPBlockBase *MiddleBB =
166 if (IRBB != IRBB->getPlan()->getPreheader() &&
167 IRBB->getSinglePredecessor() != MiddleBB) {
168 errs() << "VPIRBasicBlock can only be used as pre-header or a successor of "
169 "middle-block at the moment!\n";
170 return false;
171 }
172 return true;
173}
174
175/// Utility function that checks whether \p VPBlockVec has duplicate
176/// VPBlockBases.
177static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
179 for (const auto *Block : VPBlockVec) {
180 if (VPBlockSet.count(Block))
181 return true;
182 VPBlockSet.insert(Block);
183 }
184 return false;
185}
186
187bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
188 auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
189 // Check block's condition bit.
190 if (VPB->getNumSuccessors() > 1 ||
191 (VPBB && VPBB->getParent() && VPBB->isExiting() &&
192 !VPBB->getParent()->isReplicator())) {
193 if (!VPBB || !VPBB->getTerminator()) {
194 errs() << "Block has multiple successors but doesn't "
195 "have a proper branch recipe!\n";
196 return false;
197 }
198 } else {
199 if (VPBB && VPBB->getTerminator()) {
200 errs() << "Unexpected branch recipe!\n";
201 return false;
202 }
203 }
204
205 // Check block's successors.
206 const auto &Successors = VPB->getSuccessors();
207 // There must be only one instance of a successor in block's successor list.
208 // TODO: This won't work for switch statements.
209 if (hasDuplicates(Successors)) {
210 errs() << "Multiple instances of the same successor.\n";
211 return false;
212 }
213
214 for (const VPBlockBase *Succ : Successors) {
215 // There must be a bi-directional link between block and successor.
216 const auto &SuccPreds = Succ->getPredecessors();
217 if (!is_contained(SuccPreds, VPB)) {
218 errs() << "Missing predecessor link.\n";
219 return false;
220 }
221 }
222
223 // Check block's predecessors.
224 const auto &Predecessors = VPB->getPredecessors();
225 // There must be only one instance of a predecessor in block's predecessor
226 // list.
227 // TODO: This won't work for switch statements.
228 if (hasDuplicates(Predecessors)) {
229 errs() << "Multiple instances of the same predecessor.\n";
230 return false;
231 }
232
233 for (const VPBlockBase *Pred : Predecessors) {
234 // Block and predecessor must be inside the same region.
235 if (Pred->getParent() != VPB->getParent()) {
236 errs() << "Predecessor is not in the same region.\n";
237 return false;
238 }
239
240 // There must be a bi-directional link between block and predecessor.
241 const auto &PredSuccs = Pred->getSuccessors();
242 if (!is_contained(PredSuccs, VPB)) {
243 errs() << "Missing successor link.\n";
244 return false;
245 }
246 }
247 return !VPBB || verifyVPBasicBlock(VPBB);
248}
249
250bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {
251 for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
252 // Check block's parent.
253 if (VPB->getParent() != Region) {
254 errs() << "VPBlockBase has wrong parent\n";
255 return false;
256 }
257
258 if (!verifyBlock(VPB))
259 return false;
260 }
261 return true;
262}
263
264bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {
265 const VPBlockBase *Entry = Region->getEntry();
266 const VPBlockBase *Exiting = Region->getExiting();
267
268 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
269 if (Entry->getNumPredecessors() != 0) {
270 errs() << "region entry block has predecessors\n";
271 return false;
272 }
273 if (Exiting->getNumSuccessors() != 0) {
274 errs() << "region exiting block has successors\n";
275 return false;
276 }
277
278 return verifyBlocksInRegion(Region);
279}
280
281bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
282 // Recurse inside nested regions and check all blocks inside the region.
283 return verifyRegion(Region) &&
285 [this](const VPBlockBase *VPB) {
286 const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB);
287 return !SubRegion || verifyRegionRec(SubRegion);
288 });
289}
290
291bool VPlanVerifier::verify(const VPlan &Plan) {
293 [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
294 return false;
295
296 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
297 if (!verifyRegionRec(TopRegion))
298 return false;
299
300 if (TopRegion->getParent()) {
301 errs() << "VPlan Top Region should have no parent.\n";
302 return false;
303 }
304
305 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
306 if (!Entry) {
307 errs() << "VPlan entry block is not a VPBasicBlock\n";
308 return false;
309 }
310
311 if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
312 errs() << "VPlan vector loop header does not start with a "
313 "VPCanonicalIVPHIRecipe\n";
314 return false;
315 }
316
317 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
318 if (!Exiting) {
319 errs() << "VPlan exiting block is not a VPBasicBlock\n";
320 return false;
321 }
322
323 if (Exiting->empty()) {
324 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
325 "BranchOnCond VPInstruction but is empty\n";
326 return false;
327 }
328
329 auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
330 if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
331 LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
332 errs() << "VPlan vector loop exit must end with BranchOnCount or "
333 "BranchOnCond VPInstruction\n";
334 return false;
335 }
336
337 for (const auto &KV : Plan.getLiveOuts())
338 if (KV.second->getNumOperands() != 1) {
339 errs() << "live outs must have a single operand\n";
340 return false;
341 }
342
343 return true;
344}
345
347 VPDominatorTree VPDT;
348 VPDT.recalculate(const_cast<VPlan &>(Plan));
349 VPlanVerifier Verifier(VPDT);
350 return Verifier.verify(Plan);
351}
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:480
ppc ctr loops verify
verify safepoint Safepoint IR Verifier
This file defines the SmallPtrSet class.
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static bool hasDuplicates(const SmallVectorImpl< VPBlockBase * > &VPBlockVec)
Utility function that checks whether VPBlockVec has duplicate VPBlockBases.
This file declares the class VPlanVerifier, which contains utility functions to check the consistency...
This file contains the declarations of the Vectorization Plan base classes:
Core dominator tree base class.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2978
iterator end()
Definition: VPlan.h:3012
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:3010
bool empty() const
Definition: VPlan.h:3021
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:437
VPRegionBlock * getParent()
Definition: VPlan.h:509
size_t getNumSuccessors() const
Definition: VPlan.h:554
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:539
VPlan * getPlan()
Definition: VPlan.cpp:150
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:155
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:544
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:534
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:764
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:3156
const VPBlockBase * getEntry() const
Definition: VPlan.h:3195
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:3227
const VPBlockBase * getExiting() const
Definition: VPlan.h:3207
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:202
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:3260
VPBasicBlock * getEntry()
Definition: VPlan.h:3362
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3462
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:3481
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
@ Entry
Definition: COFF.h:826
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
iterator_range< df_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order.
Definition: VPlanCFG.h:214
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
bool verifyVPlanIsValid(const VPlan &Plan)
Verify invariants for general VPlans.