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 | |
24 | using 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. |
29 | static 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 = 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 | |
83 | static 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. |
126 | static 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 | |
136 | static 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. |
202 | static 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. |
219 | static 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. |
239 | static 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 | |
250 | bool 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 | |