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 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
27                                         cl::Hidden,
28                                         cl::desc("Verify VPlan H-CFG."));
29 
30 #ifndef NDEBUG
31 /// Utility function that checks whether \p VPBlockVec has duplicate
32 /// VPBlockBases.
33 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
34   SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
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.
47 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
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.
98 static 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 
109   verifyBlocksInRegion(Region);
110 }
111 
112 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
113 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
114 static void verifyRegionRec(const VPRegionBlock *Region) {
115   verifyRegion(Region);
116 
117   // Recurse inside nested regions.
118   for (const VPBlockBase *VPB : make_range(
119            df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
120            df_iterator<const VPBlockBase *>::end(Region->getExiting()))) {
121     if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
122       verifyRegionRec(SubRegion);
123   }
124 }
125 
126 void VPlanVerifier::verifyHierarchicalCFG(
127     const VPRegionBlock *TopRegion) const {
128   if (!EnableHCFGVerifier)
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.
139 static 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 
193 static 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.
200   DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;
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 
233 bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
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 }
298