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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
//===-- 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 "VPlan.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/Support/CommandLine.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(llvm::is_contained(SuccPreds, VPB) && "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(llvm::is_contained(PredSuccs, VPB) && "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);
}
bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
auto Iter = depth_first(
VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
for (const VPBasicBlock *VPBB :
VPBlockUtils::blocksOnly<const VPBasicBlock>(Iter)) {
// Verify that phi-like recipes are at the beginning of the block, with no
// other recipes in between.
auto RecipeI = VPBB->begin();
auto End = VPBB->end();
while (RecipeI != End && RecipeI->isPhi())
RecipeI++;
while (RecipeI != End) {
if (RecipeI->isPhi() && !isa<VPBlendRecipe>(&*RecipeI)) {
errs() << "Found phi-like recipe after non-phi recipe";
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
errs() << ": ";
RecipeI->dump();
errs() << "after\n";
std::prev(RecipeI)->dump();
#endif
return false;
}
RecipeI++;
}
}
const VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan.getEntry());
const VPBasicBlock *Entry = dyn_cast<VPBasicBlock>(TopRegion->getEntry());
if (!Entry) {
errs() << "VPlan entry block is not a VPBasicBlock\n";
return false;
}
if (!isa<VPCanonicalIVPHIRecipe>(&*Entry->begin())) {
errs() << "VPlan vector loop header does not start with a "
"VPCanonicalIVPHIRecipe\n";
return false;
}
const VPBasicBlock *Exit = dyn_cast<VPBasicBlock>(TopRegion->getExit());
if (!Exit) {
errs() << "VPlan exit block is not a VPBasicBlock\n";
return false;
}
if (Exit->empty()) {
errs() << "VPlan vector loop exit must end with BranchOnCount "
"VPInstruction but is empty\n";
return false;
}
auto *LastInst = dyn_cast<VPInstruction>(std::prev(Exit->end()));
if (!LastInst || LastInst->getOpcode() != VPInstruction::BranchOnCount) {
errs() << "VPlan vector loop exit must end with BranchOnCount "
"VPInstruction\n";
return false;
}
for (const VPRegionBlock *Region :
VPBlockUtils::blocksOnly<const VPRegionBlock>(
depth_first(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
Plan.getEntry())))) {
if (Region->getEntry()->getNumPredecessors() != 0) {
errs() << "region entry block has predecessors\n";
return false;
}
if (Region->getExit()->getNumSuccessors() != 0) {
errs() << "region exit block has successors\n";
return false;
}
}
return true;
}
|
