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 /// Utility function that checks whether \p VPBlockVec has duplicate
28 /// VPBlockBases.
29 LLVM_ATTRIBUTE_USED static bool
30 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 
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.
43 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
44   for (const VPBlockBase *VPB :
45        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
46                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
47     // Check block's parent.
48     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
49 
50     // Check block's successors.
51     const auto &Successors = VPB->getSuccessors();
52     // There must be only one instance of a successor in block's successor list.
53     // TODO: This won't work for switch statements.
54     assert(!hasDuplicates(Successors) &&
55            "Multiple instances of the same successor.");
56 
57     for (const VPBlockBase *Succ : Successors) {
58       // There must be a bi-directional link between block and successor.
59       const auto &SuccPreds = Succ->getPredecessors();
60       assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) !=
61                  SuccPreds.end() &&
62              "Missing predecessor link.");
63       (void)SuccPreds;
64     }
65 
66     // Check block's predecessors.
67     const auto &Predecessors = VPB->getPredecessors();
68     // There must be only one instance of a predecessor in block's predecessor
69     // list.
70     // TODO: This won't work for switch statements.
71     assert(!hasDuplicates(Predecessors) &&
72            "Multiple instances of the same predecessor.");
73 
74     for (const VPBlockBase *Pred : Predecessors) {
75       // Block and predecessor must be inside the same region.
76       assert(Pred->getParent() == VPB->getParent() &&
77              "Predecessor is not in the same region.");
78 
79       // There must be a bi-directional link between block and predecessor.
80       const auto &PredSuccs = Pred->getSuccessors();
81       assert(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) !=
82                  PredSuccs.end() &&
83              "Missing successor link.");
84       (void)PredSuccs;
85     }
86   }
87 }
88 
89 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
90 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
91 static void verifyRegion(const VPRegionBlock *Region) {
92   const VPBlockBase *Entry = Region->getEntry();
93   const VPBlockBase *Exit = Region->getExit();
94 
95   // Entry and Exit shouldn't have any predecessor/successor, respectively.
96   assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
97   assert(!Exit->getNumSuccessors() && "Region exit has successors.");
98   (void)Entry;
99   (void)Exit;
100 
101   verifyBlocksInRegion(Region);
102 }
103 
104 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
105 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
106 static void verifyRegionRec(const VPRegionBlock *Region) {
107   verifyRegion(Region);
108 
109   // Recurse inside nested regions.
110   for (const VPBlockBase *VPB :
111        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
112                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
113     if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
114       verifyRegionRec(SubRegion);
115   }
116 }
117 
118 void VPlanVerifier::verifyHierarchicalCFG(
119     const VPRegionBlock *TopRegion) const {
120   if (!EnableHCFGVerifier)
121     return;
122 
123   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
124   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
125   verifyRegionRec(TopRegion);
126 }
127