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