LLVM 17.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
26static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
28 cl::desc("Verify VPlan H-CFG."));
29
30#ifndef NDEBUG
31/// Utility function that checks whether \p VPBlockVec has duplicate
32/// VPBlockBases.
33static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
35 for (const auto *Block : VPBlockVec) {
36 if (VPBlockSet.count(Block))
37 return true;
38 VPBlockSet.insert(Block);
39 }
40 return false;
41}
42#endif
43
44/// Helper function that verifies the CFG invariants of the VPBlockBases within
45/// \p Region. Checks in this function are generic for VPBlockBases. They are
46/// not specific for VPBasicBlocks or VPRegionBlocks.
48 for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
49 // Check block's parent.
50 assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
51
52 auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
53 // Check block's condition bit.
54 if (VPB->getNumSuccessors() > 1 || (VPBB && VPBB->isExiting()))
55 assert(VPBB && VPBB->getTerminator() &&
56 "Block has multiple successors but doesn't "
57 "have a proper branch recipe!");
58 else
59 assert((!VPBB || !VPBB->getTerminator()) && "Unexpected branch recipe!");
60
61 // Check block's successors.
62 const auto &Successors = VPB->getSuccessors();
63 // There must be only one instance of a successor in block's successor list.
64 // TODO: This won't work for switch statements.
65 assert(!hasDuplicates(Successors) &&
66 "Multiple instances of the same successor.");
67
68 for (const VPBlockBase *Succ : Successors) {
69 // There must be a bi-directional link between block and successor.
70 const auto &SuccPreds = Succ->getPredecessors();
71 assert(llvm::is_contained(SuccPreds, VPB) && "Missing predecessor link.");
72 (void)SuccPreds;
73 }
74
75 // Check block's predecessors.
76 const auto &Predecessors = VPB->getPredecessors();
77 // There must be only one instance of a predecessor in block's predecessor
78 // list.
79 // TODO: This won't work for switch statements.
80 assert(!hasDuplicates(Predecessors) &&
81 "Multiple instances of the same predecessor.");
82
83 for (const VPBlockBase *Pred : Predecessors) {
84 // Block and predecessor must be inside the same region.
85 assert(Pred->getParent() == VPB->getParent() &&
86 "Predecessor is not in the same region.");
87
88 // There must be a bi-directional link between block and predecessor.
89 const auto &PredSuccs = Pred->getSuccessors();
90 assert(llvm::is_contained(PredSuccs, VPB) && "Missing successor link.");
91 (void)PredSuccs;
92 }
93 }
94}
95
96/// Verify the CFG invariants of VPRegionBlock \p Region and its nested
97/// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
98static void verifyRegion(const VPRegionBlock *Region) {
99 const VPBlockBase *Entry = Region->getEntry();
100 const VPBlockBase *Exiting = Region->getExiting();
101
102 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
103 assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
104 assert(!Exiting->getNumSuccessors() &&
105 "Region exiting block has successors.");
106 (void)Entry;
107 (void)Exiting;
108
110}
111
112/// Verify the CFG invariants of VPRegionBlock \p Region and its nested
113/// VPBlockBases. Recurse inside nested VPRegionBlocks.
116
117 // Recurse inside nested regions.
118 for (const VPBlockBase *VPB : make_range(
121 if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
122 verifyRegionRec(SubRegion);
123 }
124}
125
127 const VPRegionBlock *TopRegion) const {
129 return;
130
131 LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
132 assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
133 verifyRegionRec(TopRegion);
134}
135
136// Verify that phi-like recipes are at the beginning of \p VPBB, with no
137// other recipes in between. Also check that only header blocks contain
138// VPHeaderPHIRecipes.
139static bool verifyPhiRecipes(const VPBasicBlock *VPBB) {
140 auto RecipeI = VPBB->begin();
141 auto End = VPBB->end();
142 unsigned NumActiveLaneMaskPhiRecipes = 0;
143 const VPRegionBlock *ParentR = VPBB->getParent();
144 bool IsHeaderVPBB = ParentR && !ParentR->isReplicator() &&
145 ParentR->getEntryBasicBlock() == VPBB;
146 while (RecipeI != End && RecipeI->isPhi()) {
147 if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))
148 NumActiveLaneMaskPhiRecipes++;
149
150 if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe>(*RecipeI)) {
151 errs() << "Found non-header PHI recipe in header VPBB";
152#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
153 errs() << ": ";
154 RecipeI->dump();
155#endif
156 return false;
157 }
158
159 if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {
160 errs() << "Found header PHI recipe in non-header VPBB";
161#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
162 errs() << ": ";
163 RecipeI->dump();
164#endif
165 return false;
166 }
167
168 RecipeI++;
169 }
170
171 if (NumActiveLaneMaskPhiRecipes > 1) {
172 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";
173 return false;
174 }
175
176 while (RecipeI != End) {
177 if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
178 errs() << "Found phi-like recipe after non-phi recipe";
179
180#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
181 errs() << ": ";
182 RecipeI->dump();
183 errs() << "after\n";
184 std::prev(RecipeI)->dump();
185#endif
186 return false;
187 }
188 RecipeI++;
189 }
190 return true;
191}
192
193static bool verifyVPBasicBlock(const VPBasicBlock *VPBB,
194 VPDominatorTree &VPDT) {
195 if (!verifyPhiRecipes(VPBB))
196 return false;
197
198 // Verify that defs in VPBB dominate all their uses. The current
199 // implementation is still incomplete.
201 unsigned Cnt = 0;
202 for (const VPRecipeBase &R : *VPBB)
203 RecipeNumbering[&R] = Cnt++;
204
205 for (const VPRecipeBase &R : *VPBB) {
206 for (const VPValue *V : R.definedValues()) {
207 for (const VPUser *U : V->users()) {
208 auto *UI = dyn_cast<VPRecipeBase>(U);
209 // TODO: check dominance of incoming values for phis properly.
210 if (!UI || isa<VPHeaderPHIRecipe>(UI) || isa<VPPredInstPHIRecipe>(UI))
211 continue;
212
213 // If the user is in the same block, check it comes after R in the
214 // block.
215 if (UI->getParent() == VPBB) {
216 if (RecipeNumbering[UI] < RecipeNumbering[&R]) {
217 errs() << "Use before def!\n";
218 return false;
219 }
220 continue;
221 }
222
223 if (!VPDT.dominates(VPBB, UI->getParent())) {
224 errs() << "Use before def!\n";
225 return false;
226 }
227 }
228 }
229 }
230 return true;
231}
232
234 VPDominatorTree VPDT;
235 VPDT.recalculate(const_cast<VPlan &>(Plan));
236
237 auto Iter = vp_depth_first_deep(Plan.getEntry());
238 for (const VPBasicBlock *VPBB :
239 VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
240 if (!verifyVPBasicBlock(VPBB, VPDT))
241 return false;
242 }
243
244 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
245 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
246 if (!Entry) {
247 errs() << "VPlan entry block is not a VPBasicBlock\n";
248 return false;
249 }
250
251 if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
252 errs() << "VPlan vector loop header does not start with a "
253 "VPCanonicalIVPHIRecipe\n";
254 return false;
255 }
256
257 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
258 if (!Exiting) {
259 errs() << "VPlan exiting block is not a VPBasicBlock\n";
260 return false;
261 }
262
263 if (Exiting->empty()) {
264 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
265 "BranchOnCond VPInstruction but is empty\n";
266 return false;
267 }
268
269 auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
270 if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
271 LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
272 errs() << "VPlan vector loop exit must end with BranchOnCount or "
273 "BranchOnCond VPInstruction\n";
274 return false;
275 }
276
277 for (const VPRegionBlock *Region :
278 VPBlockUtils::blocksOnly<const VPRegionBlock>(
279 vp_depth_first_deep(Plan.getEntry()))) {
280 if (Region->getEntry()->getNumPredecessors() != 0) {
281 errs() << "region entry block has predecessors\n";
282 return false;
283 }
284 if (Region->getExiting()->getNumSuccessors() != 0) {
285 errs() << "region exiting block has successors\n";
286 return false;
287 }
288 }
289
290 for (const auto &KV : Plan.getLiveOuts())
291 if (KV.second->getNumOperands() != 1) {
292 errs() << "live outs must have a single operand\n";
293 return false;
294 }
295
296 return true;
297}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:464
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static void verifyRegionRec(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static cl::opt< bool > EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false), cl::Hidden, cl::desc("Verify VPlan H-CFG."))
static bool verifyPhiRecipes(const VPBasicBlock *VPBB)
static bool verifyVPBasicBlock(const VPBasicBlock *VPBB, VPDominatorTree &VPDT)
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static bool hasDuplicates(const SmallVectorImpl< VPBlockBase * > &VPBlockVec)
Utility function that checks whether VPBlockVec has duplicate VPBlockBases.
static void verifyBlocksInRegion(const VPRegionBlock *Region)
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:577
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2192
iterator end()
Definition: VPlan.h:2223
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2221
bool empty() const
Definition: VPlan.h:2232
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:418
VPRegionBlock * getParent()
Definition: VPlan.h:490
size_t getNumSuccessors() const
Definition: VPlan.h:535
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:151
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:703
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2316
const VPBlockBase * getEntry() const
Definition: VPlan.h:2355
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:2387
const VPBlockBase * getExiting() const
Definition: VPlan.h:2367
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:2413
VPBasicBlock * getEntry()
Definition: VPlan.h:2505
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2613
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:2641
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
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
Definition: VPlanCFG.h:226
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:1976
static bool verifyPlanIsValid(const VPlan &Plan)
Verify invariants for general VPlans.
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.