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
|
// Copyright (c) 2015-2016 The Khronos Group Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef SOURCE_VAL_CONSTRUCT_H_
#define SOURCE_VAL_CONSTRUCT_H_
#include <cstdint>
#include <set>
#include <vector>
#include "source/val/basic_block.h"
namespace spvtools {
namespace val {
class ValidationState_t;
/// Functor for ordering BasicBlocks. BasicBlock pointers must not be null.
struct less_than_id {
bool operator()(const BasicBlock* lhs, const BasicBlock* rhs) const {
return lhs->id() < rhs->id();
}
};
enum class ConstructType : int {
kNone = 0,
/// The set of blocks dominated by a selection header, minus the set of blocks
/// dominated by the header's merge block
kSelection,
/// The set of blocks dominated by an OpLoopMerge's Continue Target and post
/// dominated by the corresponding back
kContinue,
/// The set of blocks dominated by a loop header, minus the set of blocks
/// dominated by the loop's merge block, minus the loop's corresponding
/// continue construct
kLoop,
/// The set of blocks dominated by an OpSwitch's Target or Default, minus the
/// set of blocks dominated by the OpSwitch's merge block (this construct is
/// only defined for those OpSwitch Target or Default that are not equal to
/// the OpSwitch's corresponding merge block)
kCase
};
class Function;
/// @brief This class tracks the CFG constructs as defined in the SPIR-V spec
class Construct {
public:
Construct(ConstructType type, BasicBlock* dominator,
BasicBlock* exit = nullptr,
std::vector<Construct*> constructs = std::vector<Construct*>());
/// Returns the type of the construct
ConstructType type() const;
const std::vector<Construct*>& corresponding_constructs() const;
std::vector<Construct*>& corresponding_constructs();
void set_corresponding_constructs(std::vector<Construct*> constructs);
/// Returns the dominator block of the construct.
///
/// This is usually the header block or the first block of the construct.
const BasicBlock* entry_block() const;
/// Returns the dominator block of the construct.
///
/// This is usually the header block or the first block of the construct.
BasicBlock* entry_block();
/// Returns the exit block of the construct.
///
/// For a continue construct it is the backedge block of the corresponding
/// loop construct. For the case construct it is the block that branches to
/// the OpSwitch merge block or other case blocks. Otherwise it is the merge
/// block of the corresponding header block
const BasicBlock* exit_block() const;
/// Returns the exit block of the construct.
///
/// For a continue construct it is the backedge block of the corresponding
/// loop construct. For the case construct it is the block that branches to
/// the OpSwitch merge block or other case blocks. Otherwise it is the merge
/// block of the corresponding header block
BasicBlock* exit_block();
/// Sets the exit block for this construct. This is useful for continue
/// constructs which do not know the back-edge block during construction
void set_exit(BasicBlock* exit_block);
// Returns whether the exit block of this construct is the merge block
// for an OpLoopMerge or OpSelectionMerge
bool ExitBlockIsMergeBlock() const {
return type_ == ConstructType::kLoop || type_ == ConstructType::kSelection;
}
using ConstructBlockSet = std::set<BasicBlock*, less_than_id>;
// Returns the basic blocks in this construct. This function should not
// be called before the exit block is set and dominators have been
// calculated.
ConstructBlockSet blocks(Function* function) const;
// Returns true if |dest| is structured exit from the construct. Structured
// exits depend on the construct type.
// Selection:
// * branch to the associated merge
// * branch to the merge or continue of the innermost loop containing the
// selection
// * branch to the merge block of the innermost switch containing the
// selection
// Loop:
// * branch to the associated merge or continue
// Continue:
// * back-edge to the associated loop header
// * branch to the associated loop merge
//
// Note: the validator does not generate case constructs. Switches are
// checked separately from other constructs.
bool IsStructuredExit(ValidationState_t& _, BasicBlock* dest) const;
private:
/// The type of the construct
ConstructType type_;
/// These are the constructs that are related to this construct. These
/// constructs can be the continue construct, for the corresponding loop
/// construct, the case construct that are part of the same OpSwitch
/// instruction
///
/// Here is a table that describes what constructs are included in
/// @p corresponding_constructs_
/// | this construct | corresponding construct |
/// |----------------|----------------------------------|
/// | loop | continue |
/// | continue | loop |
/// | case | other cases in the same OpSwitch |
///
/// kContinue and kLoop constructs will always have corresponding
/// constructs even if they are represented by the same block
std::vector<Construct*> corresponding_constructs_;
/// @brief Dominator block for the construct
///
/// The dominator block for the construct. Depending on the construct this may
/// be a selection header, a continue target of a loop, a loop header or a
/// Target or Default block of a switch
BasicBlock* entry_block_;
/// @brief Exiting block for the construct
///
/// The exit block for the construct. This can be a merge block for the loop
/// and selection constructs, a back-edge block for a continue construct, or
/// the branching block for the case construct
BasicBlock* exit_block_;
};
} // namespace val
} // namespace spvtools
#endif // SOURCE_VAL_CONSTRUCT_H_
|
