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