LLVM  16.0.0git
VPlanVerifier.cpp
Go to the documentation of this file.
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"
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) {
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.
46  for (const VPBlockBase *VPB : make_range(
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 
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) {
116 
117  // Recurse inside nested regions.
118  for (const VPBlockBase *VPB : make_range(
121  if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
122  verifyRegionRec(SubRegion);
123  }
124 }
125 
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
195  DenseMap<const VPBlockBase *, unsigned> &BlockNumbering) {
196  if (!verifyPhiRecipes(VPBB))
197  return false;
198 
199  // Verify that defs in VPBB dominate all their uses. The current
200  // implementation is still incomplete.
202  unsigned Cnt = 0;
203  for (const VPRecipeBase &R : *VPBB)
204  RecipeNumbering[&R] = Cnt++;
205 
206  for (const VPRecipeBase &R : *VPBB) {
207  for (const VPValue *V : R.definedValues()) {
208  for (const VPUser *U : V->users()) {
209  auto *UI = dyn_cast<VPRecipeBase>(U);
210  if (!UI || isa<VPHeaderPHIRecipe>(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  // Skip blocks outside any region for now and blocks outside
224  // replicate-regions.
225  auto *ParentR = VPBB->getParent();
226  if (!ParentR || !ParentR->isReplicator())
227  continue;
228 
229  // For replicators, verify that VPPRedInstPHIRecipe defs are only used
230  // in subsequent blocks.
231  if (isa<VPPredInstPHIRecipe>(&R)) {
232  auto I = BlockNumbering.find(UI->getParent());
233  unsigned BlockNumber = I == BlockNumbering.end() ? std::numeric_limits<unsigned>::max() : I->second;
234  if (BlockNumber < BlockNumbering[ParentR]) {
235  errs() << "Use before def!\n";
236  return false;
237  }
238  continue;
239  }
240 
241  // All non-VPPredInstPHIRecipe recipes in the block must be used in
242  // the replicate region only.
243  if (UI->getParent()->getParent() != ParentR) {
244  errs() << "Use before def!\n";
245  return false;
246  }
247  }
248  }
249  }
250  return true;
251 }
252 
255  unsigned Cnt = 0;
256  auto Iter = depth_first(
258  for (const VPBlockBase *VPB : Iter) {
259  BlockNumbering[VPB] = Cnt++;
260  auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
261  if (!VPBB)
262  continue;
263  if (!verifyVPBasicBlock(VPBB, BlockNumbering))
264  return false;
265  }
266 
267  const VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
268  const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
269  if (!Entry) {
270  errs() << "VPlan entry block is not a VPBasicBlock\n";
271  return false;
272  }
273 
274  if (!isa<VPCanonicalIVPHIRecipe>(&*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>(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>(std::prev(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 VPRegionBlock *Region :
301  VPBlockUtils::blocksOnly<const VPRegionBlock>(
303  Plan.getEntry())))) {
304  if (Region->getEntry()->getNumPredecessors() != 0) {
305  errs() << "region entry block has predecessors\n";
306  return false;
307  }
308  if (Region->getExiting()->getNumSuccessors() != 0) {
309  errs() << "region exiting block has successors\n";
310  return false;
311  }
312  }
313 
314  for (const auto &KV : Plan.getLiveOuts())
315  if (KV.second->getNumOperands() != 1) {
316  errs() << "live outs must have a single operand\n";
317  return false;
318  }
319 
320  return true;
321 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::VPlanVerifier::verifyPlanIsValid
static bool verifyPlanIsValid(const VPlan &Plan)
Verify invariants for general VPlans.
Definition: VPlanVerifier.cpp:253
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
verifyRegion
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
Definition: VPlanVerifier.cpp:98
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2065
verifyBlocksInRegion
static void verifyBlocksInRegion(const VPRegionBlock *Region)
Helper function that verifies the CFG invariants of the VPBlockBases within Region.
Definition: VPlanVerifier.cpp:45
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::VPInstruction::BranchOnCond
@ BranchOnCond
Definition: VPlan.h:796
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:891
llvm::VPRegionBlock::getEntry
const VPBlockBase * getEntry() const
Definition: VPlan.h:2228
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
verifyPhiRecipes
static bool verifyPhiRecipes(const VPBasicBlock *VPBB)
Definition: VPlanVerifier.cpp:139
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
llvm::VPBlockBase
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:389
llvm::VPValue
Definition: VPlanValue.h:44
VPlan.h
llvm::VPBasicBlock::end
iterator end()
Definition: VPlan.h:2096
llvm::VPBasicBlock::empty
bool empty() const
Definition: VPlan.h:2105
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2189
llvm::VPBlockBase::getNumSuccessors
size_t getNumSuccessors() const
Definition: VPlan.h:506
llvm::cl::opt< bool >
llvm::RegionBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::VPRegionBlock::getExiting
const VPBlockBase * getExiting() const
Definition: VPlan.h:2246
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
EnableHCFGVerifier
static cl::opt< bool > EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false), cl::Hidden, cl::desc("Verify VPlan H-CFG."))
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1868
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2621
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::df_iterator
Definition: DepthFirstIterator.h:86
llvm::VPlan::getVectorLoopRegion
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2734
llvm::VPInstruction::BranchOnCount
@ BranchOnCount
Definition: VPlan.h:795
llvm::VPBlockBase::getEntryBasicBlock
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:147
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
VPlanVerifier.h
hasDuplicates
static bool hasDuplicates(const SmallVectorImpl< VPBlockBase * > &VPBlockVec)
Utility function that checks whether VPBlockVec has duplicate VPBlockBases.
Definition: VPlanVerifier.cpp:31
llvm::VPBlockBase::getParent
VPRegionBlock * getParent()
Definition: VPlan.h:461
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:663
verifyVPBasicBlock
static bool verifyVPBasicBlock(const VPBasicBlock *VPBB, DenseMap< const VPBlockBase *, unsigned > &BlockNumbering)
Definition: VPlanVerifier.cpp:194
llvm::VPUser
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:221
llvm::VPBasicBlock::begin
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2094
llvm::VPlan::getLiveOuts
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:2768
llvm::SmallVectorImpl< VPBlockBase * >
verifyRegionRec
static void verifyRegionRec(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
Definition: VPlanVerifier.cpp:114
llvm::VPlanVerifier::verifyHierarchicalCFG
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.
Definition: VPlanVerifier.cpp:126
llvm::VPRegionBlock::isReplicator
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:2266
llvm::cl::desc
Definition: CommandLine.h:413
llvm::Region
Definition: RegionInfo.h:889
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2488
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2544