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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
// 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.
#include "source/val/validate.h"
#include <cassert>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <stack>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
#include "source/diagnostic.h"
#include "source/instruction.h"
#include "source/opcode.h"
#include "source/operand.h"
#include "source/spirv_validator_options.h"
#include "source/val/function.h"
#include "source/val/validation_state.h"
#include "spirv-tools/libspirv.h"
namespace spvtools {
namespace val {
spv_result_t UpdateIdUse(ValidationState_t& _, const Instruction* inst) {
for (auto& operand : inst->operands()) {
const spv_operand_type_t& type = operand.type;
const uint32_t operand_id = inst->word(operand.offset);
if (spvIsIdType(type) && type != SPV_OPERAND_TYPE_RESULT_ID) {
if (auto def = _.FindDef(operand_id))
def->RegisterUse(inst, operand.offset);
}
}
return SPV_SUCCESS;
}
/// This function checks all ID definitions dominate their use in the CFG.
///
/// This function will iterate over all ID definitions that are defined in the
/// functions of a module and make sure that the definitions appear in a
/// block that dominates their use.
///
/// NOTE: This function does NOT check module scoped functions which are
/// checked during the initial binary parse in the IdPass below
spv_result_t CheckIdDefinitionDominateUse(ValidationState_t& _) {
std::vector<const Instruction*> phi_instructions;
std::unordered_set<uint32_t> phi_ids;
for (const auto& inst : _.ordered_instructions()) {
if (inst.id() == 0) continue;
if (const Function* func = inst.function()) {
if (const BasicBlock* block = inst.block()) {
// If the Id is defined within a block then make sure all references to
// that Id appear in a blocks that are dominated by the defining block
for (auto& use_index_pair : inst.uses()) {
const Instruction* use = use_index_pair.first;
if (const BasicBlock* use_block = use->block()) {
if (use_block->reachable() == false) continue;
if (use->opcode() == SpvOpPhi) {
if (phi_ids.insert(use->id()).second) {
phi_instructions.push_back(use);
}
} else if (!block->dominates(*use->block())) {
return _.diag(SPV_ERROR_INVALID_ID, use_block->label())
<< "ID " << _.getIdName(inst.id()) << " defined in block "
<< _.getIdName(block->id())
<< " does not dominate its use in block "
<< _.getIdName(use_block->id());
}
}
}
} else {
// If the Ids defined within a function but not in a block(i.e. function
// parameters, block ids), then make sure all references to that Id
// appear within the same function
for (auto use : inst.uses()) {
const Instruction* user = use.first;
if (user->function() && user->function() != func) {
return _.diag(SPV_ERROR_INVALID_ID, _.FindDef(func->id()))
<< "ID " << _.getIdName(inst.id()) << " used in function "
<< _.getIdName(user->function()->id())
<< " is used outside of it's defining function "
<< _.getIdName(func->id());
}
}
}
}
// NOTE: Ids defined outside of functions must appear before they are used
// This check is being performed in the IdPass function
}
// Check all OpPhi parent blocks are dominated by the variable's defining
// blocks
for (const Instruction* phi : phi_instructions) {
if (phi->block()->reachable() == false) continue;
for (size_t i = 3; i < phi->operands().size(); i += 2) {
const Instruction* variable = _.FindDef(phi->word(i));
const BasicBlock* parent =
phi->function()->GetBlock(phi->word(i + 1)).first;
if (variable->block() && parent->reachable() &&
!variable->block()->dominates(*parent)) {
return _.diag(SPV_ERROR_INVALID_ID, phi)
<< "In OpPhi instruction " << _.getIdName(phi->id()) << ", ID "
<< _.getIdName(variable->id())
<< " definition does not dominate its parent "
<< _.getIdName(parent->id());
}
}
}
return SPV_SUCCESS;
}
// Performs SSA validation on the IDs of an instruction. The
// can_have_forward_declared_ids functor should return true if the
// instruction operand's ID can be forward referenced.
spv_result_t IdPass(ValidationState_t& _, Instruction* inst) {
auto can_have_forward_declared_ids =
inst->opcode() == SpvOpExtInst &&
spvExtInstIsDebugInfo(inst->ext_inst_type())
? spvDbgInfoExtOperandCanBeForwardDeclaredFunction(
inst->ext_inst_type(), inst->word(4))
: spvOperandCanBeForwardDeclaredFunction(inst->opcode());
// Keep track of a result id defined by this instruction. 0 means it
// does not define an id.
uint32_t result_id = 0;
for (unsigned i = 0; i < inst->operands().size(); i++) {
const spv_parsed_operand_t& operand = inst->operand(i);
const spv_operand_type_t& type = operand.type;
// We only care about Id operands, which are a single word.
const uint32_t operand_word = inst->word(operand.offset);
auto ret = SPV_ERROR_INTERNAL;
switch (type) {
case SPV_OPERAND_TYPE_RESULT_ID:
// NOTE: Multiple Id definitions are being checked by the binary parser.
//
// Defer undefined-forward-reference removal until after we've analyzed
// the remaining operands to this instruction. Deferral only matters
// for OpPhi since it's the only case where it defines its own forward
// reference. Other instructions that can have forward references
// either don't define a value or the forward reference is to a function
// Id (and hence defined outside of a function body).
result_id = operand_word;
// NOTE: The result Id is added (in RegisterInstruction) *after* all of
// the other Ids have been checked to avoid premature use in the same
// instruction.
ret = SPV_SUCCESS;
break;
case SPV_OPERAND_TYPE_ID:
case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
case SPV_OPERAND_TYPE_SCOPE_ID:
if (const auto def = _.FindDef(operand_word)) {
const auto opcode = inst->opcode();
if (spvOpcodeGeneratesType(def->opcode()) &&
!spvOpcodeGeneratesType(opcode) && !spvOpcodeIsDebug(opcode) &&
!inst->IsDebugInfo() && !inst->IsNonSemantic() &&
!spvOpcodeIsDecoration(opcode) && opcode != SpvOpFunction &&
opcode != SpvOpCooperativeMatrixLengthNV &&
!(opcode == SpvOpSpecConstantOp &&
inst->word(3) == SpvOpCooperativeMatrixLengthNV)) {
return _.diag(SPV_ERROR_INVALID_ID, inst)
<< "Operand " << _.getIdName(operand_word)
<< " cannot be a type";
} else if (def->type_id() == 0 && !spvOpcodeGeneratesType(opcode) &&
!spvOpcodeIsDebug(opcode) && !inst->IsDebugInfo() &&
!inst->IsNonSemantic() && !spvOpcodeIsDecoration(opcode) &&
!spvOpcodeIsBranch(opcode) && opcode != SpvOpPhi &&
opcode != SpvOpExtInst && opcode != SpvOpExtInstImport &&
opcode != SpvOpSelectionMerge &&
opcode != SpvOpLoopMerge && opcode != SpvOpFunction &&
opcode != SpvOpCooperativeMatrixLengthNV &&
!(opcode == SpvOpSpecConstantOp &&
inst->word(3) == SpvOpCooperativeMatrixLengthNV)) {
return _.diag(SPV_ERROR_INVALID_ID, inst)
<< "Operand " << _.getIdName(operand_word)
<< " requires a type";
} else if (def->IsNonSemantic() && !inst->IsNonSemantic()) {
return _.diag(SPV_ERROR_INVALID_ID, inst)
<< "Operand " << _.getIdName(operand_word)
<< " in semantic instruction cannot be a non-semantic "
"instruction";
} else {
ret = SPV_SUCCESS;
}
} else if (can_have_forward_declared_ids(i)) {
if (spvOpcodeGeneratesType(inst->opcode()) &&
!_.IsForwardPointer(operand_word)) {
ret = _.diag(SPV_ERROR_INVALID_ID, inst)
<< "Operand " << _.getIdName(operand_word)
<< " requires a previous definition";
} else {
ret = _.ForwardDeclareId(operand_word);
}
} else {
ret = _.diag(SPV_ERROR_INVALID_ID, inst)
<< "ID " << _.getIdName(operand_word)
<< " has not been defined";
}
break;
case SPV_OPERAND_TYPE_TYPE_ID:
if (_.IsDefinedId(operand_word)) {
auto* def = _.FindDef(operand_word);
if (!spvOpcodeGeneratesType(def->opcode())) {
ret = _.diag(SPV_ERROR_INVALID_ID, inst)
<< "ID " << _.getIdName(operand_word) << " is not a type id";
} else {
ret = SPV_SUCCESS;
}
} else {
ret = _.diag(SPV_ERROR_INVALID_ID, inst)
<< "ID " << _.getIdName(operand_word)
<< " has not been defined";
}
break;
default:
ret = SPV_SUCCESS;
break;
}
if (SPV_SUCCESS != ret) return ret;
}
if (result_id) _.RemoveIfForwardDeclared(result_id);
return SPV_SUCCESS;
}
} // namespace val
} // namespace spvtools
|
