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/Support/CommandLine.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>(Val: RecipeI))
38 NumActiveLaneMaskPhiRecipes++;
39
40 if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe, VPWidenPHIRecipe>(Val: *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>(Val: *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>(Val: &*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(x: 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.
90 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
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>(Val: U);
99 // TODO: check dominance of incoming values for phis properly.
100 if (!UI ||
101 isa<VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPredInstPHIRecipe>(Val: 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(A: VPBB, B: 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) {
127 SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
128 for (const auto *Block : VPBlockVec) {
129 if (VPBlockSet.count(V: Block))
130 return true;
131 VPBlockSet.insert(V: Block);
132 }
133 return false;
134}
135
136static bool verifyBlock(const VPBlockBase *VPB, const VPDominatorTree &VPDT) {
137 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
138 // Check block's condition bit.
139 if (VPB->getNumSuccessors() > 1 ||
140 (VPBB && VPBB->getParent() && VPBB->isExiting() &&
141 !VPBB->getParent()->isReplicator())) {
142 if (!VPBB || !VPBB->getTerminator()) {
143 errs() << "Block has multiple successors but doesn't "
144 "have a proper branch recipe!\n";
145 return false;
146 }
147 } else {
148 if (VPBB && VPBB->getTerminator()) {
149 errs() << "Unexpected branch recipe!\n";
150 return false;
151 }
152 }
153
154 // Check block's successors.
155 const auto &Successors = VPB->getSuccessors();
156 // There must be only one instance of a successor in block's successor list.
157 // TODO: This won't work for switch statements.
158 if (hasDuplicates(VPBlockVec: Successors)) {
159 errs() << "Multiple instances of the same successor.\n";
160 return false;
161 }
162
163 for (const VPBlockBase *Succ : Successors) {
164 // There must be a bi-directional link between block and successor.
165 const auto &SuccPreds = Succ->getPredecessors();
166 if (!is_contained(Range: SuccPreds, Element: VPB)) {
167 errs() << "Missing predecessor link.\n";
168 return false;
169 }
170 }
171
172 // Check block's predecessors.
173 const auto &Predecessors = VPB->getPredecessors();
174 // There must be only one instance of a predecessor in block's predecessor
175 // list.
176 // TODO: This won't work for switch statements.
177 if (hasDuplicates(VPBlockVec: Predecessors)) {
178 errs() << "Multiple instances of the same predecessor.\n";
179 return false;
180 }
181
182 for (const VPBlockBase *Pred : Predecessors) {
183 // Block and predecessor must be inside the same region.
184 if (Pred->getParent() != VPB->getParent()) {
185 errs() << "Predecessor is not in the same region.\n";
186 return false;
187 }
188
189 // There must be a bi-directional link between block and predecessor.
190 const auto &PredSuccs = Pred->getSuccessors();
191 if (!is_contained(Range: PredSuccs, Element: VPB)) {
192 errs() << "Missing successor link.\n";
193 return false;
194 }
195 }
196 return !VPBB || verifyVPBasicBlock(VPBB, VPDT);
197}
198
199/// Helper function that verifies the CFG invariants of the VPBlockBases within
200/// \p Region. Checks in this function are generic for VPBlockBases. They are
201/// not specific for VPBasicBlocks or VPRegionBlocks.
202static bool verifyBlocksInRegion(const VPRegionBlock *Region,
203 const VPDominatorTree &VPDT) {
204 for (const VPBlockBase *VPB : vp_depth_first_shallow(G: Region->getEntry())) {
205 // Check block's parent.
206 if (VPB->getParent() != Region) {
207 errs() << "VPBlockBase has wrong parent\n";
208 return false;
209 }
210
211 if (!verifyBlock(VPB, VPDT))
212 return false;
213 }
214 return true;
215}
216
217/// Verify the CFG invariants of VPRegionBlock \p Region and its nested
218/// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
219static bool verifyRegion(const VPRegionBlock *Region,
220 const VPDominatorTree &VPDT) {
221 const VPBlockBase *Entry = Region->getEntry();
222 const VPBlockBase *Exiting = Region->getExiting();
223
224 // Entry and Exiting shouldn't have any predecessor/successor, respectively.
225 if (Entry->getNumPredecessors() != 0) {
226 errs() << "region entry block has predecessors\n";
227 return false;
228 }
229 if (Exiting->getNumSuccessors() != 0) {
230 errs() << "region exiting block has successors\n";
231 return false;
232 }
233
234 return verifyBlocksInRegion(Region, VPDT);
235}
236
237/// Verify the CFG invariants of VPRegionBlock \p Region and its nested
238/// VPBlockBases. Recurse inside nested VPRegionBlocks.
239static bool verifyRegionRec(const VPRegionBlock *Region,
240 const VPDominatorTree &VPDT) {
241 // Recurse inside nested regions and check all blocks inside the region.
242 return verifyRegion(Region, VPDT) &&
243 all_of(Range: vp_depth_first_shallow(G: Region->getEntry()),
244 P: [&VPDT](const VPBlockBase *VPB) {
245 const auto *SubRegion = dyn_cast<VPRegionBlock>(Val: VPB);
246 return !SubRegion || verifyRegionRec(Region: SubRegion, VPDT);
247 });
248}
249
250bool llvm::verifyVPlanIsValid(const VPlan &Plan) {
251 VPDominatorTree VPDT;
252 VPDT.recalculate(Func&: const_cast<VPlan &>(Plan));
253
254 if (any_of(
255 Range: vp_depth_first_shallow(G: Plan.getEntry()),
256 P: [&VPDT](const VPBlockBase *VPB) { return !verifyBlock(VPB, VPDT); }))
257 return false;
258
259 const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
260 if (!verifyRegionRec(Region: TopRegion, VPDT))
261 return false;
262
263 if (TopRegion->getParent()) {
264 errs() << "VPlan Top Region should have no parent.\n";
265 return false;
266 }
267
268 const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(Val: TopRegion->getEntry());
269 if (!Entry) {
270 errs() << "VPlan entry block is not a VPBasicBlock\n";
271 return false;
272 }
273
274 if (!isa<VPCanonicalIVPHIRecipe>(Val: &*Entry->begin())) {
275 errs() << "VPlan vector loop header does not start with a "
276 "VPCanonicalIVPHIRecipe\n";
277 return false;
278 }
279
280 const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(Val: TopRegion->getExiting());
281 if (!Exiting) {
282 errs() << "VPlan exiting block is not a VPBasicBlock\n";
283 return false;
284 }
285
286 if (Exiting->empty()) {
287 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "
288 "BranchOnCond VPInstruction but is empty\n";
289 return false;
290 }
291
292 auto *LastInst = dyn_cast<VPInstruction>(Val: std::prev(x: Exiting->end()));
293 if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
294 LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
295 errs() << "VPlan vector loop exit must end with BranchOnCount or "
296 "BranchOnCond VPInstruction\n";
297 return false;
298 }
299
300 for (const auto &KV : Plan.getLiveOuts())
301 if (KV.second->getNumOperands() != 1) {
302 errs() << "live outs must have a single operand\n";
303 return false;
304 }
305
306 return true;
307}
308

source code of llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp