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
25using namespace llvm;
26
27namespace {
28class 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
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>(Val: RecipeI))
72 NumActiveLaneMaskPhiRecipes++;
73
74 if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe>(Val: *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>(Val: *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>(Val: &*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.
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>(Val: U);
132 // TODO: check dominance of incoming values for phis properly.
133 if (!UI ||
134 isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPredInstPHIRecipe>(Val: 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(A: VPBB, B: UI->getParent())) {
148 errs() << "Use before def!\n";
149 return false;
150 }
151 }
152 }
153 }
154
155 auto *IRBB = dyn_cast<VPIRBasicBlock>(Val: VPBB);
156 if (!IRBB)
157 return true;
158
159 if (!WrappedIRBBs.insert(Ptr: 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.
177static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
178 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
179 for (const auto *Block : VPBlockVec) {
180 if (VPBlockSet.count(V: Block))
181 return true;
182 VPBlockSet.insert(V: Block);
183 }
184 return false;
185}
186
187bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {
188 auto *VPBB = dyn_cast<VPBasicBlock>(Val: 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(VPBlockVec: 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(Range: SuccPreds, Element: 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(VPBlockVec: 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(Range: PredSuccs, Element: 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(G: 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) &&
284 all_of(Range: vp_depth_first_shallow(G: Region->getEntry()),
285 P: [this](const VPBlockBase *VPB) {
286 const auto *SubRegion = dyn_cast<VPRegionBlock>(Val: VPB);
287 return !SubRegion || verifyRegionRec(Region: SubRegion);
288 });
289}
290
291bool VPlanVerifier::verify(const VPlan &Plan) {
292 if (any_of(Range: vp_depth_first_shallow(G: Plan.getEntry()),
293 P: [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))
294 return false;
295
296 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
297 if (!verifyRegionRec(Region: 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>(Val: TopRegion->getEntry());
306 if (!Entry) {
307 errs() << "VPlan entry block is not a VPBasicBlock\n";
308 return false;
309 }
310
311 if (!isa<VPCanonicalIVPHIRecipe>(Val: &*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>(Val: 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>(Val: std::prev(x: 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
346bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
347 VPDominatorTree VPDT;
348 VPDT.recalculate(Func&: const_cast<VPlan &>(Plan));
349 VPlanVerifier Verifier(VPDT);
350 return Verifier.verify(Plan);
351}
352