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"
21
22#define DEBUG_TYPE "loop-vectorize"
23
24using namespace llvm;
25
26// Verify that phi-like recipes are at the beginning of \p VPBB, with no
27// other recipes in between. Also check that only header blocks contain
28// VPHeaderPHIRecipes.
29static bool verifyPhiRecipes(const VPBasicBlock *VPBB) {
30 auto RecipeI = VPBB->begin();
31 auto End = VPBB->end();
32 unsigned NumActiveLaneMaskPhiRecipes = 0;
33 const VPRegionBlock *ParentR = VPBB->getParent();
34 bool IsHeaderVPBB = ParentR && !ParentR->isReplicator() &&
35 ParentR->getEntryBasicBlock() == VPBB;
36 while (RecipeI != End && RecipeI->isPhi()) {
37 if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))
38 NumActiveLaneMaskPhiRecipes++;
39
40 if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe>(*RecipeI)) {
41 errs() << "Found non-header PHI recipe in header VPBB";
42#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
43 errs() << ": ";
44 RecipeI->dump();
45#endif
46 return false;
47 }
48
49 if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {
50 errs() << "Found header PHI recipe in non-header VPBB";
51#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
52 errs() << ": ";
53 RecipeI->dump();
54#endif
55 return false;
56 }
57
58 RecipeI++;
59 }
60
61 if (NumActiveLaneMaskPhiRecipes > 1) {
62 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
63 return false;
64 }
65
66 while (RecipeI != End) {
67 if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
68 errs() << "Found phi-like recipe after non-phi recipe";
69
70#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
71 errs() << ": ";
72 RecipeI->dump();
73 errs() << "after\n";
74 std::prev(RecipeI)->dump();
75#endif
76 return false;
77 }
78 RecipeI++;
79 }
80 return true;
81}
82
83static bool verifyVPBasicBlock(const VPBasicBlock *VPBB,
84 const VPDominatorTree &VPDT) {
85 if (!verifyPhiRecipes(VPBB))
86 return false;
87
88 // Verify that defs in VPBB dominate all their uses. The current
89 // implementation is still incomplete.
91 unsigned Cnt = 0;
92 for (const VPRecipeBase &R : *VPBB)
93 RecipeNumbering[&R] = Cnt++;
94
95 for (const VPRecipeBase &R : *VPBB) {
96 for (const VPValue *V : R.definedValues()) {
97 for (const VPUser *U : V->users()) {
98 auto *UI = dyn_cast<VPRecipeBase>(U);
99 // TODO: check dominance of incoming values for phis properly.
100 if (!UI ||
101 isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPredInstPHIRecipe>(UI))
102 continue;
103
104 // If the user is in the same block, check it comes after R in the
105 // block.
106 if (UI->getParent() == VPBB) {
107 if (RecipeNumbering[UI] < RecipeNumbering[&R]) {
108 errs() << "Use before def!\n";
109 return false;
110 }
111 continue;
112 }
113
114 if (!VPDT.dominates(VPBB, UI->getParent())) {
115 errs() << "Use before def!\n";
116 return false;
117 }
118 }
119 }
120 }
121 return true;
122}
123
124/// Utility function that checks whether \p VPBlockVec has duplicate
125/// VPBlockBases.
126static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
128 for (const auto *Block : VPBlockVec) {
129 if (VPBlockSet.count(Block))
130 return true;
131 VPBlockSet.insert(Block);
132 }
133 return false;
134}
135
136static bool verifyBlock(const VPBlockBase *VPB, const VPDominatorTree &VPDT) {
137 auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
138 if (VPBB && !verifyVPBasicBlock(VPBB, VPDT))
139 return false;
140
141 // Check block's condition bit.
142 if (VPB->getNumSuccessors() > 1 ||
143 (VPBB && VPBB->getParent() && VPBB->isExiting() &&
144 !VPBB->getParent()->isReplicator())) {
145 if (!VPBB || !VPBB->getTerminator()) {
146 errs() << "Block has multiple successors but doesn't "
147 "have a proper branch recipe!\n";
148 return false;
149 }
150 } else {
151 if (VPBB && VPBB->getTerminator()) {
152 errs() << "Unexpected branch recipe!\n";
153 return false;
154 }
155 }
156
157 // Check block's successors.
158 const auto &Successors = VPB->getSuccessors();
159 // There must be only one instance of a successor in block's successor list.
160 // TODO: This won't work for switch statements.
161 if (hasDuplicates(Successors)) {
162 errs() << "Multiple instances of the same successor.\n";
163 return false;
164 }
165
166 for (const VPBlockBase *Succ : Successors) {
167 // There must be a bi-directional link between block and successor.
168 const auto &SuccPreds = Succ->getPredecessors();
169 if (!is_contained(SuccPreds, VPB)) {
170 errs() << "Missing predecessor link.\n";
171 return false;
172 }
173 }
174
175 // Check block's predecessors.
176 const auto &Predecessors = VPB->getPredecessors();
177 // There must be only one instance of a predecessor in block's predecessor
178 // list.
179 // TODO: This won't work for switch statements.
180 if (hasDuplicates(Predecessors)) {
181 errs() << "Multiple instances of the same predecessor.\n";
182 return false;
183 }
184
185 for (const VPBlockBase *Pred : Predecessors) {
186 // Block and predecessor must be inside the same region.
187 if (Pred->getParent() != VPB->getParent()) {
188 errs() << "Predecessor is not in the same region.\n";
189 return false;
190 }
191
192 // There must be a bi-directional link between block and predecessor.
193 const auto &PredSuccs = Pred->getSuccessors();
194 if (!is_contained(PredSuccs, VPB)) {
195 errs() << "Missing successor link.\n";
196 return false;
197 }
198 }
199 return true;
200}
201
202/// Helper function that verifies the CFG invariants of the VPBlockBases within
203/// \p Region. Checks in this function are generic for VPBlockBases. They are
204/// not specific for VPBasicBlocks or VPRegionBlocks.
206 const VPDominatorTree &VPDT) {
207 for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
208 // Check block's parent.
209 if (VPB->getParent() != Region) {
210 errs() << "VPBlockBase has wrong parent\n";
211 return false;
212 }
213
214 if (!verifyBlock(VPB, VPDT))
215 return false;
216 }
217 return true;
218}
219
220/// Verify the CFG invariants of VPRegionBlock \p Region and its nested
221/// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
223 const VPDominatorTree &VPDT) {
224 const VPBlockBase *Entry = Region->getEntry();
225 const VPBlockBase *Exiting = Region->getExiting();
226
227 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
228 if (Entry->getNumPredecessors() != 0) {
229 errs() << "region entry block has predecessors\n";
230 return false;
231 }
232 if (Exiting->getNumSuccessors() != 0) {
233 errs() << "region exiting block has successors\n";
234 return false;
235 }
236
237 return verifyBlocksInRegion(Region, VPDT);
238}
239
240/// Verify the CFG invariants of VPRegionBlock \p Region and its nested
241/// VPBlockBases. Recurse inside nested VPRegionBlocks.
243 const VPDominatorTree &VPDT) {
244 // Recurse inside nested regions and check all blocks inside the region.
245 return verifyRegion(Region, VPDT) &&
247 [&VPDT](const VPBlockBase *VPB) {
248 const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB);
249 return !SubRegion || verifyRegionRec(SubRegion, VPDT);
250 });
251}
252
254 VPDominatorTree VPDT;
255 VPDT.recalculate(const_cast<VPlan &>(Plan));
256
257 if (any_of(
259 [&VPDT](const VPBlockBase *VPB) { return !verifyBlock(VPB, VPDT); }))
260 return false;
261
262 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
263 if (!verifyRegionRec(TopRegion, VPDT))
264 return false;
265
266 if (TopRegion->getParent()) {
267 errs() << "VPlan Top Region should have no parent.\n";
268 return false;
269 }
270
271 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
272 if (!Entry) {
273 errs() << "VPlan entry block is not a VPBasicBlock\n";
274 return false;
275 }
276
277 if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
278 errs() << "VPlan vector loop header does not start with a "
279 "VPCanonicalIVPHIRecipe\n";
280 return false;
281 }
282
283 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
284 if (!Exiting) {
285 errs() << "VPlan exiting block is not a VPBasicBlock\n";
286 return false;
287 }
288
289 if (Exiting->empty()) {
290 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
291 "BranchOnCond VPInstruction but is empty\n";
292 return false;
293 }
294
295 auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
296 if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
297 LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
298 errs() << "VPlan vector loop exit must end with BranchOnCount or "
299 "BranchOnCond VPInstruction\n";
300 return false;
301 }
302
303 for (const auto &KV : Plan.getLiveOuts())
304 if (KV.second->getNumOperands() != 1) {
305 errs() << "live outs must have a single operand\n";
306 return false;
307 }
308
309 return true;
310}
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:480
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static bool verifyPhiRecipes(const VPBasicBlock *VPBB)
static bool verifyRegion(const VPRegionBlock *Region, const VPDominatorTree &VPDT)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static bool verifyRegionRec(const VPRegionBlock *Region, const VPDominatorTree &VPDT)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static bool verifyVPBasicBlock(const VPBasicBlock *VPBB, const VPDominatorTree &VPDT)
static bool verifyBlock(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
static bool hasDuplicates(const SmallVectorImpl< VPBlockBase * > &VPBlockVec)
Utility function that checks whether VPBlockVec has duplicate VPBlockBases.
static bool verifyBlocksInRegion(const VPRegionBlock *Region, const VPDominatorTree &VPDT)
Helper function that verifies the CFG invariants of the VPBlockBases within Region.
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.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
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
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:2578
iterator end()
Definition: VPlan.h:2609
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2607
bool empty() const
Definition: VPlan.h:2618
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:412
VPRegionBlock * getParent()
Definition: VPlan.h:484
size_t getNumSuccessors() const
Definition: VPlan.h:529
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:514
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:151
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:509
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:704
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2711
const VPBlockBase * getEntry() const
Definition: VPlan.h:2750
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:2782
const VPBlockBase * getExiting() const
Definition: VPlan.h:2762
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:204
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2812
VPBasicBlock * getEntry()
Definition: VPlan.h:2909
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3020
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:3044
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:1731
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:1738
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:1888
bool verifyVPlanIsValid(const VPlan &Plan)
Verify invariants for general VPlans.