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