LLVM 19.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 if (IRBB != IRBB->getPlan()->getPreheader()) {
164 errs() << "VPIRBasicBlock can only be used as pre-header at the moment!\n";
165 return false;
166 }
167 return true;
168}
169
170/// Utility function that checks whether \p VPBlockVec has duplicate
171/// VPBlockBases.
172static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
174 for (const auto *Block : VPBlockVec) {
175 if (VPBlockSet.count(Block))
176 return true;
177 VPBlockSet.insert(Block);
178 }
179 return false;
180}
181
182bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
183 auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
184 // Check block's condition bit.
185 if (VPB->getNumSuccessors() > 1 ||
186 (VPBB && VPBB->getParent() && VPBB->isExiting() &&
187 !VPBB->getParent()->isReplicator())) {
188 if (!VPBB || !VPBB->getTerminator()) {
189 errs() << "Block has multiple successors but doesn't "
190 "have a proper branch recipe!\n";
191 return false;
192 }
193 } else {
194 if (VPBB && VPBB->getTerminator()) {
195 errs() << "Unexpected branch recipe!\n";
196 return false;
197 }
198 }
199
200 // Check block's successors.
201 const auto &Successors = VPB->getSuccessors();
202 // There must be only one instance of a successor in block's successor list.
203 // TODO: This won't work for switch statements.
204 if (hasDuplicates(Successors)) {
205 errs() << "Multiple instances of the same successor.\n";
206 return false;
207 }
208
209 for (const VPBlockBase *Succ : Successors) {
210 // There must be a bi-directional link between block and successor.
211 const auto &SuccPreds = Succ->getPredecessors();
212 if (!is_contained(SuccPreds, VPB)) {
213 errs() << "Missing predecessor link.\n";
214 return false;
215 }
216 }
217
218 // Check block's predecessors.
219 const auto &Predecessors = VPB->getPredecessors();
220 // There must be only one instance of a predecessor in block's predecessor
221 // list.
222 // TODO: This won't work for switch statements.
223 if (hasDuplicates(Predecessors)) {
224 errs() << "Multiple instances of the same predecessor.\n";
225 return false;
226 }
227
228 for (const VPBlockBase *Pred : Predecessors) {
229 // Block and predecessor must be inside the same region.
230 if (Pred->getParent() != VPB->getParent()) {
231 errs() << "Predecessor is not in the same region.\n";
232 return false;
233 }
234
235 // There must be a bi-directional link between block and predecessor.
236 const auto &PredSuccs = Pred->getSuccessors();
237 if (!is_contained(PredSuccs, VPB)) {
238 errs() << "Missing successor link.\n";
239 return false;
240 }
241 }
242 return !VPBB || verifyVPBasicBlock(VPBB);
243}
244
245bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {
246 for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
247 // Check block's parent.
248 if (VPB->getParent() != Region) {
249 errs() << "VPBlockBase has wrong parent\n";
250 return false;
251 }
252
253 if (!verifyBlock(VPB))
254 return false;
255 }
256 return true;
257}
258
259bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {
260 const VPBlockBase *Entry = Region->getEntry();
261 const VPBlockBase *Exiting = Region->getExiting();
262
263 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
264 if (Entry->getNumPredecessors() != 0) {
265 errs() << "region entry block has predecessors\n";
266 return false;
267 }
268 if (Exiting->getNumSuccessors() != 0) {
269 errs() << "region exiting block has successors\n";
270 return false;
271 }
272
273 return verifyBlocksInRegion(Region);
274}
275
276bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
277 // Recurse inside nested regions and check all blocks inside the region.
278 return verifyRegion(Region) &&
280 [this](const VPBlockBase *VPB) {
281 const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB);
282 return !SubRegion || verifyRegionRec(SubRegion);
283 });
284}
285
286bool VPlanVerifier::verify(const VPlan &Plan) {
288 [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
289 return false;
290
291 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
292 if (!verifyRegionRec(TopRegion))
293 return false;
294
295 if (TopRegion->getParent()) {
296 errs() << "VPlan Top Region should have no parent.\n";
297 return false;
298 }
299
300 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
301 if (!Entry) {
302 errs() << "VPlan entry block is not a VPBasicBlock\n";
303 return false;
304 }
305
306 if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
307 errs() << "VPlan vector loop header does not start with a "
308 "VPCanonicalIVPHIRecipe\n";
309 return false;
310 }
311
312 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
313 if (!Exiting) {
314 errs() << "VPlan exiting block is not a VPBasicBlock\n";
315 return false;
316 }
317
318 if (Exiting->empty()) {
319 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
320 "BranchOnCond VPInstruction but is empty\n";
321 return false;
322 }
323
324 auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
325 if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
326 LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
327 errs() << "VPlan vector loop exit must end with BranchOnCount or "
328 "BranchOnCond VPInstruction\n";
329 return false;
330 }
331
332 for (const auto &KV : Plan.getLiveOuts())
333 if (KV.second->getNumOperands() != 1) {
334 errs() << "live outs must have a single operand\n";
335 return false;
336 }
337
338 return true;
339}
340
342 VPDominatorTree VPDT;
343 VPDT.recalculate(const_cast<VPlan &>(Plan));
344 VPlanVerifier Verifier(VPDT);
345 return Verifier.verify(Plan);
346}
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:427
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2835
iterator end()
Definition: VPlan.h:2869
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2867
bool empty() const
Definition: VPlan.h:2878
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:425
VPRegionBlock * getParent()
Definition: VPlan.h:497
size_t getNumSuccessors() const
Definition: VPlan.h:542
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:527
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:154
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:522
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:717
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:3010
const VPBlockBase * getEntry() const
Definition: VPlan.h:3049
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:3081
const VPBlockBase * getExiting() const
Definition: VPlan.h:3061
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:203
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:3111
VPBasicBlock * getEntry()
Definition: VPlan.h:3206
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3300
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:3324
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
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.