LLVM  9.0.0svn
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"
17 
18 #define DEBUG_TYPE "loop-vectorize"
19 
20 using namespace llvm;
21 
22 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
23  cl::Hidden,
24  cl::desc("Verify VPlan H-CFG."));
25 
26 #ifndef NDEBUG
27 /// Utility function that checks whether \p VPBlockVec has duplicate
28 /// VPBlockBases.
29 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
31  for (const auto *Block : VPBlockVec) {
32  if (VPBlockSet.count(Block))
33  return true;
34  VPBlockSet.insert(Block);
35  }
36  return false;
37 }
38 #endif
39 
40 /// Helper function that verifies the CFG invariants of the VPBlockBases within
41 /// \p Region. Checks in this function are generic for VPBlockBases. They are
42 /// not specific for VPBasicBlocks or VPRegionBlocks.
44  for (const VPBlockBase *VPB :
47  // Check block's parent.
48  assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
49 
50  // Check block's condition bit.
51  if (VPB->getNumSuccessors() > 1)
52  assert(VPB->getCondBit() && "Missing condition bit!");
53  else
54  assert(!VPB->getCondBit() && "Unexpected condition bit!");
55 
56  // Check block's successors.
57  const auto &Successors = VPB->getSuccessors();
58  // There must be only one instance of a successor in block's successor list.
59  // TODO: This won't work for switch statements.
60  assert(!hasDuplicates(Successors) &&
61  "Multiple instances of the same successor.");
62 
63  for (const VPBlockBase *Succ : Successors) {
64  // There must be a bi-directional link between block and successor.
65  const auto &SuccPreds = Succ->getPredecessors();
66  assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) !=
67  SuccPreds.end() &&
68  "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(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) !=
88  PredSuccs.end() &&
89  "Missing successor link.");
90  (void)PredSuccs;
91  }
92  }
93 }
94 
95 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
96 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
97 static void verifyRegion(const VPRegionBlock *Region) {
98  const VPBlockBase *Entry = Region->getEntry();
99  const VPBlockBase *Exit = Region->getExit();
100 
101  // Entry and Exit shouldn't have any predecessor/successor, respectively.
102  assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
103  assert(!Exit->getNumSuccessors() && "Region exit has successors.");
104  (void)Entry;
105  (void)Exit;
106 
107  verifyBlocksInRegion(Region);
108 }
109 
110 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
111 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
112 static void verifyRegionRec(const VPRegionBlock *Region) {
113  verifyRegion(Region);
114 
115  // Recurse inside nested regions.
116  for (const VPBlockBase *VPB :
119  if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
120  verifyRegionRec(SubRegion);
121  }
122 }
123 
125  const VPRegionBlock *TopRegion) const {
126  if (!EnableHCFGVerifier)
127  return;
128 
129  LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
130  assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
131  verifyRegionRec(TopRegion);
132 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
VPRegionBlock * getParent()
Definition: VPlan.h:408
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1067
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static bool hasDuplicates(const SmallVectorImpl< VPBlockBase *> &VPBlockVec)
Utility function that checks whether VPBlockVec has duplicate VPBlockBases.
static cl::opt< bool > EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false), cl::Hidden, cl::desc("Verify VPlan H-CFG."))
const VPBlockBase * getExit() const
Definition: VPlan.h:1121
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
size_t getNumPredecessors() const
Definition: VPlan.h:444
size_t getNumSuccessors() const
Definition: VPlan.h:443
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:333
static void verifyRegionRec(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:267
const VPBlockBase * getEntry() const
Definition: VPlan.h:1103
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:91
This file declares the class VPlanVerifier, which contains utility functions to check the consistency...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define LLVM_DEBUG(X)
Definition: Debug.h:122
static void verifyBlocksInRegion(const VPRegionBlock *Region)
Helper function that verifies the CFG invariants of the VPBlockBases within Region.