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