LLVM  14.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 :
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)
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 *Exit = Region->getExit();
98 
99  // Entry and Exit shouldn't have any predecessor/successor, respectively.
100  assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
101  assert(!Exit->getNumSuccessors() && "Region exit has successors.");
102  (void)Entry;
103  (void)Exit;
104 
106 }
107 
108 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
109 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
110 static void verifyRegionRec(const VPRegionBlock *Region) {
112 
113  // Recurse inside nested regions.
114  for (const VPBlockBase *VPB :
117  if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
118  verifyRegionRec(SubRegion);
119  }
120 }
121 
123  const VPRegionBlock *TopRegion) const {
124  if (!EnableHCFGVerifier)
125  return;
126 
127  LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
128  assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
129  verifyRegionRec(TopRegion);
130 }
131 
133  auto Iter = depth_first(
135  for (const VPBasicBlock *VPBB :
136  VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
137  // Verify that phi-like recipes are at the beginning of the block, with no
138  // other recipes in between.
139  auto RecipeI = VPBB->begin();
140  auto End = VPBB->end();
141  while (RecipeI != End && RecipeI->isPhi())
142  RecipeI++;
143 
144  while (RecipeI != End) {
145  if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
146  errs() << "Found phi-like recipe after non-phi recipe";
147 
148 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
149  errs() << ": ";
150  RecipeI->dump();
151  errs() << "after\n";
152  std::prev(RecipeI)->dump();
153 #endif
154  return false;
155  }
156  RecipeI++;
157  }
158  }
159  return true;
160 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::VPlanVerifier::verifyPlanIsValid
static bool verifyPlanIsValid(const VPlan &Plan)
Verify invariants for general VPlans.
Definition: VPlanVerifier.cpp:132
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:95
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1630
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:143
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
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
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:393
VPlan.h
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1744
llvm::VPBlockBase::getNumSuccessors
size_t getNumSuccessors() const
Definition: VPlan.h:518
llvm::cl::opt< bool >
llvm::RegionBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
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:1665
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2156
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
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:475
llvm::SmallVectorImpl< VPBlockBase * >
verifyRegionRec
static void verifyRegionRec(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
Definition: VPlanVerifier.cpp:110
llvm::VPlanVerifier::verifyHierarchicalCFG
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.
Definition: VPlanVerifier.cpp:122
llvm::cl::desc
Definition: CommandLine.h:412
llvm::Region
Definition: RegionInfo.h:889
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2036
llvm::RegionBase::getExit
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:359
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2092