1 //===-- VPlanVerifier.cpp -------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This file defines the class VPlanVerifier, which contains utility functions
12 /// to check the consistency and invariants of a VPlan.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #include "VPlanVerifier.h"
17 #include "llvm/ADT/DepthFirstIterator.h"
18 
19 #define DEBUG_TYPE "loop-vectorize"
20 
21 using namespace llvm;
22 
23 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
24                                         cl::Hidden,
25                                         cl::desc("Verify VPlan H-CFG."));
26 
27 #ifndef NDEBUG
28 /// Utility function that checks whether \p VPBlockVec has duplicate
29 /// VPBlockBases.
30 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
31   SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
32   for (const auto *Block : VPBlockVec) {
33     if (VPBlockSet.count(Block))
34       return true;
35     VPBlockSet.insert(Block);
36   }
37   return false;
38 }
39 #endif
40 
41 /// Helper function that verifies the CFG invariants of the VPBlockBases within
42 /// \p Region. Checks in this function are generic for VPBlockBases. They are
43 /// not specific for VPBasicBlocks or VPRegionBlocks.
44 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
45   for (const VPBlockBase *VPB :
46        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
47                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
48     // Check block's parent.
49     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
50 
51     // Check block's successors.
52     const auto &Successors = VPB->getSuccessors();
53     // There must be only one instance of a successor in block's successor list.
54     // TODO: This won't work for switch statements.
55     assert(!hasDuplicates(Successors) &&
56            "Multiple instances of the same successor.");
57 
58     for (const VPBlockBase *Succ : Successors) {
59       // There must be a bi-directional link between block and successor.
60       const auto &SuccPreds = Succ->getPredecessors();
61       assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) !=
62                  SuccPreds.end() &&
63              "Missing predecessor link.");
64       (void)SuccPreds;
65     }
66 
67     // Check block's predecessors.
68     const auto &Predecessors = VPB->getPredecessors();
69     // There must be only one instance of a predecessor in block's predecessor
70     // list.
71     // TODO: This won't work for switch statements.
72     assert(!hasDuplicates(Predecessors) &&
73            "Multiple instances of the same predecessor.");
74 
75     for (const VPBlockBase *Pred : Predecessors) {
76       // Block and predecessor must be inside the same region.
77       assert(Pred->getParent() == VPB->getParent() &&
78              "Predecessor is not in the same region.");
79 
80       // There must be a bi-directional link between block and predecessor.
81       const auto &PredSuccs = Pred->getSuccessors();
82       assert(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) !=
83                  PredSuccs.end() &&
84              "Missing successor link.");
85       (void)PredSuccs;
86     }
87   }
88 }
89 
90 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
91 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
92 static void verifyRegion(const VPRegionBlock *Region) {
93   const VPBlockBase *Entry = Region->getEntry();
94   const VPBlockBase *Exit = Region->getExit();
95 
96   // Entry and Exit shouldn't have any predecessor/successor, respectively.
97   assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
98   assert(!Exit->getNumSuccessors() && "Region exit has successors.");
99   (void)Entry;
100   (void)Exit;
101 
102   verifyBlocksInRegion(Region);
103 }
104 
105 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
106 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
107 static void verifyRegionRec(const VPRegionBlock *Region) {
108   verifyRegion(Region);
109 
110   // Recurse inside nested regions.
111   for (const VPBlockBase *VPB :
112        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
113                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
114     if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
115       verifyRegionRec(SubRegion);
116   }
117 }
118 
119 void VPlanVerifier::verifyHierarchicalCFG(
120     const VPRegionBlock *TopRegion) const {
121   if (!EnableHCFGVerifier)
122     return;
123 
124   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
125   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
126   verifyRegionRec(TopRegion);
127 }
128