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