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 "llvm/ADT/DepthFirstIterator.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/Support/CommandLine.h"
22
23 #define DEBUG_TYPE "loop-vectorize"
24
25 using namespace llvm;
26
27 namespace {
28 class VPlanVerifier {
29 const VPDominatorTree &VPDT;
30
31 SmallPtrSet<BasicBlock *, 8> WrappedIRBBs;
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
56 public:
VPlanVerifier(VPDominatorTree & VPDT)57 VPlanVerifier(VPDominatorTree &VPDT) : VPDT(VPDT) {}
58
59 bool verify(const VPlan &Plan);
60 };
61 } // namespace
62
verifyPhiRecipes(const VPBasicBlock * VPBB)63 bool 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
verifyVPBasicBlock(const VPBasicBlock * VPBB)117 bool 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.
123 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
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 =
165 IRBB->getPlan()->getVectorLoopRegion()->getSingleSuccessor();
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.
hasDuplicates(const SmallVectorImpl<VPBlockBase * > & VPBlockVec)177 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
178 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
179 for (const auto *Block : VPBlockVec) {
180 if (VPBlockSet.count(Block))
181 return true;
182 VPBlockSet.insert(Block);
183 }
184 return false;
185 }
186
verifyBlock(const VPBlockBase * VPB)187 bool 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
verifyBlocksInRegion(const VPRegionBlock * Region)250 bool 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
verifyRegion(const VPRegionBlock * Region)264 bool 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
verifyRegionRec(const VPRegionBlock * Region)281 bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {
282 // Recurse inside nested regions and check all blocks inside the region.
283 return verifyRegion(Region) &&
284 all_of(vp_depth_first_shallow(Region->getEntry()),
285 [this](const VPBlockBase *VPB) {
286 const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB);
287 return !SubRegion || verifyRegionRec(SubRegion);
288 });
289 }
290
verify(const VPlan & Plan)291 bool VPlanVerifier::verify(const VPlan &Plan) {
292 if (any_of(vp_depth_first_shallow(Plan.getEntry()),
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
verifyVPlanIsValid(const VPlan & Plan)346 bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
347 VPDominatorTree VPDT;
348 VPDT.recalculate(const_cast<VPlan &>(Plan));
349 VPlanVerifier Verifier(VPDT);
350 return Verifier.verify(Plan);
351 }
352