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 "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/Support/CommandLine.h"
19 
20 #define DEBUG_TYPE "loop-vectorize"
21 
22 using namespace llvm;
23 
24 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
25                                         cl::Hidden,
26                                         cl::desc("Verify VPlan H-CFG."));
27 
28 #ifndef NDEBUG
29 /// Utility function that checks whether \p VPBlockVec has duplicate
30 /// VPBlockBases.
31 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
32   SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
33   for (const auto *Block : VPBlockVec) {
34     if (VPBlockSet.count(Block))
35       return true;
36     VPBlockSet.insert(Block);
37   }
38   return false;
39 }
40 #endif
41 
42 /// Helper function that verifies the CFG invariants of the VPBlockBases within
43 /// \p Region. Checks in this function are generic for VPBlockBases. They are
44 /// not specific for VPBasicBlocks or VPRegionBlocks.
45 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
46   for (const VPBlockBase *VPB : make_range(
47            df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
48            df_iterator<const VPBlockBase *>::end(Region->getExiting()))) {
49     // Check block's parent.
50     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
51 
52     // Check block's condition bit.
53     if (VPB->getNumSuccessors() > 1 || Region->getExitingBasicBlock() == VPB)
54       assert(VPB->getCondBit() && "Missing condition bit!");
55     else
56       assert(!VPB->getCondBit() && "Unexpected condition bit!");
57 
58     // Check block's successors.
59     const auto &Successors = VPB->getSuccessors();
60     // There must be only one instance of a successor in block's successor list.
61     // TODO: This won't work for switch statements.
62     assert(!hasDuplicates(Successors) &&
63            "Multiple instances of the same successor.");
64 
65     for (const VPBlockBase *Succ : Successors) {
66       // There must be a bi-directional link between block and successor.
67       const auto &SuccPreds = Succ->getPredecessors();
68       assert(llvm::is_contained(SuccPreds, VPB) && "Missing predecessor link.");
69       (void)SuccPreds;
70     }
71 
72     // Check block's predecessors.
73     const auto &Predecessors = VPB->getPredecessors();
74     // There must be only one instance of a predecessor in block's predecessor
75     // list.
76     // TODO: This won't work for switch statements.
77     assert(!hasDuplicates(Predecessors) &&
78            "Multiple instances of the same predecessor.");
79 
80     for (const VPBlockBase *Pred : Predecessors) {
81       // Block and predecessor must be inside the same region.
82       assert(Pred->getParent() == VPB->getParent() &&
83              "Predecessor is not in the same region.");
84 
85       // There must be a bi-directional link between block and predecessor.
86       const auto &PredSuccs = Pred->getSuccessors();
87       assert(llvm::is_contained(PredSuccs, VPB) && "Missing successor link.");
88       (void)PredSuccs;
89     }
90   }
91 }
92 
93 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
94 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
95 static void verifyRegion(const VPRegionBlock *Region) {
96   const VPBlockBase *Entry = Region->getEntry();
97   const VPBlockBase *Exiting = Region->getExiting();
98 
99   // Entry and Exiting shouldn't have any predecessor/successor, respectively.
100   assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
101   assert(!Exiting->getNumSuccessors() &&
102          "Region exiting block has successors.");
103   (void)Entry;
104   (void)Exiting;
105 
106   verifyBlocksInRegion(Region);
107 }
108 
109 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
110 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
111 static void verifyRegionRec(const VPRegionBlock *Region) {
112   verifyRegion(Region);
113 
114   // Recurse inside nested regions.
115   for (const VPBlockBase *VPB : make_range(
116            df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
117            df_iterator<const VPBlockBase *>::end(Region->getExiting()))) {
118     if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
119       verifyRegionRec(SubRegion);
120   }
121 }
122 
123 void VPlanVerifier::verifyHierarchicalCFG(
124     const VPRegionBlock *TopRegion) const {
125   if (!EnableHCFGVerifier)
126     return;
127 
128   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
129   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
130   verifyRegionRec(TopRegion);
131 }
132 
133 bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
134   auto Iter = depth_first(
135       VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
136   for (const VPBasicBlock *VPBB :
137        VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
138     // Verify that phi-like recipes are at the beginning of the block, with no
139     // other recipes in between.
140     auto RecipeI = VPBB->begin();
141     auto End = VPBB->end();
142     while (RecipeI != End && RecipeI->isPhi())
143       RecipeI++;
144 
145     while (RecipeI != End) {
146       if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
147         errs() << "Found phi-like recipe after non-phi recipe";
148 
149 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
150         errs() << ": ";
151         RecipeI->dump();
152         errs() << "after\n";
153         std::prev(RecipeI)->dump();
154 #endif
155         return false;
156       }
157       RecipeI++;
158     }
159   }
160 
161   const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
162   const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
163   if (!Entry) {
164     errs() << "VPlan entry block is not a VPBasicBlock\n";
165     return false;
166   }
167 
168   if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
169     errs() << "VPlan vector loop header does not start with a "
170               "VPCanonicalIVPHIRecipe\n";
171     return false;
172   }
173 
174   const VPBasicBlock *Exiting = dyn_cast<VPBasicBlock>(TopRegion->getExiting());
175   if (!Exiting) {
176     errs() << "VPlan exiting block is not a VPBasicBlock\n";
177     return false;
178   }
179 
180   if (Exiting->empty()) {
181     errs() << "VPlan vector loop exiting block must end with BranchOnCount "
182               "VPInstruction but is empty\n";
183     return false;
184   }
185 
186   auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exiting->end()));
187   if (!LastInst || LastInst->getOpcode() != VPInstruction::BranchOnCount) {
188     errs() << "VPlan vector loop exit must end with BranchOnCount "
189               "VPInstruction\n";
190     return false;
191   }
192 
193   for (const VPRegionBlock *Region :
194        VPBlockUtils::blocksOnly<const VPRegionBlock>(
195            depth_first(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
196                Plan.getEntry())))) {
197     if (Region->getEntry()->getNumPredecessors() != 0) {
198       errs() << "region entry block has predecessors\n";
199       return false;
200     }
201     if (Region->getExiting()->getNumSuccessors() != 0) {
202       errs() << "region exiting block has successors\n";
203       return false;
204     }
205   }
206 
207   for (auto &KV : Plan.getLiveOuts())
208     if (KV.second->getNumOperands() != 1) {
209       errs() << "live outs must have a single operand\n";
210       return false;
211     }
212 
213   return true;
214 }
215