1 // Copyright (c) 2015-2016 The Khronos Group Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <unordered_set>
16 #include <vector>
17
18 #include "source/instruction.h"
19 #include "source/opcode.h"
20 #include "source/operand.h"
21 #include "source/val/function.h"
22 #include "source/val/validate.h"
23 #include "source/val/validation_state.h"
24 #include "spirv-tools/libspirv.h"
25
26 namespace spvtools {
27 namespace val {
28
UpdateIdUse(ValidationState_t & _,const Instruction * inst)29 spv_result_t UpdateIdUse(ValidationState_t& _, const Instruction* inst) {
30 for (auto& operand : inst->operands()) {
31 const spv_operand_type_t& type = operand.type;
32 const uint32_t operand_id = inst->word(operand.offset);
33 if (spvIsIdType(type) && type != SPV_OPERAND_TYPE_RESULT_ID) {
34 if (auto def = _.FindDef(operand_id))
35 def->RegisterUse(inst, operand.offset);
36 }
37 }
38
39 return SPV_SUCCESS;
40 }
41
42 /// This function checks all ID definitions dominate their use in the CFG.
43 ///
44 /// This function will iterate over all ID definitions that are defined in the
45 /// functions of a module and make sure that the definitions appear in a
46 /// block that dominates their use.
47 ///
48 /// NOTE: This function does NOT check module scoped functions which are
49 /// checked during the initial binary parse in the IdPass below
CheckIdDefinitionDominateUse(ValidationState_t & _)50 spv_result_t CheckIdDefinitionDominateUse(ValidationState_t& _) {
51 std::vector<const Instruction*> phi_instructions;
52 std::unordered_set<uint32_t> phi_ids;
53 for (const auto& inst : _.ordered_instructions()) {
54 if (inst.id() == 0) continue;
55 if (const Function* func = inst.function()) {
56 if (const BasicBlock* block = inst.block()) {
57 // If the Id is defined within a block then make sure all references to
58 // that Id appear in a blocks that are dominated by the defining block
59 for (auto& use_index_pair : inst.uses()) {
60 const Instruction* use = use_index_pair.first;
61 if (const BasicBlock* use_block = use->block()) {
62 if (use_block->reachable() == false) continue;
63 if (use->opcode() == spv::Op::OpPhi) {
64 if (phi_ids.insert(use->id()).second) {
65 phi_instructions.push_back(use);
66 }
67 } else if (!block->dominates(*use->block())) {
68 return _.diag(SPV_ERROR_INVALID_ID, use_block->label())
69 << "ID " << _.getIdName(inst.id()) << " defined in block "
70 << _.getIdName(block->id())
71 << " does not dominate its use in block "
72 << _.getIdName(use_block->id());
73 }
74 }
75 }
76 } else {
77 // If the Ids defined within a function but not in a block(i.e. function
78 // parameters, block ids), then make sure all references to that Id
79 // appear within the same function
80 for (auto use : inst.uses()) {
81 const Instruction* user = use.first;
82 if (user->function() && user->function() != func) {
83 return _.diag(SPV_ERROR_INVALID_ID, _.FindDef(func->id()))
84 << "ID " << _.getIdName(inst.id()) << " used in function "
85 << _.getIdName(user->function()->id())
86 << " is used outside of it's defining function "
87 << _.getIdName(func->id());
88 }
89 }
90 }
91 }
92 // NOTE: Ids defined outside of functions must appear before they are used
93 // This check is being performed in the IdPass function
94 }
95
96 // Check all OpPhi parent blocks are dominated by the variable's defining
97 // blocks
98 for (const Instruction* phi : phi_instructions) {
99 if (phi->block()->reachable() == false) continue;
100 for (size_t i = 3; i < phi->operands().size(); i += 2) {
101 const Instruction* variable = _.FindDef(phi->word(i));
102 const BasicBlock* parent =
103 phi->function()->GetBlock(phi->word(i + 1)).first;
104 if (variable->block() && parent->reachable() &&
105 !variable->block()->dominates(*parent)) {
106 return _.diag(SPV_ERROR_INVALID_ID, phi)
107 << "In OpPhi instruction " << _.getIdName(phi->id()) << ", ID "
108 << _.getIdName(variable->id())
109 << " definition does not dominate its parent "
110 << _.getIdName(parent->id());
111 }
112 }
113 }
114
115 return SPV_SUCCESS;
116 }
117
118 // Performs SSA validation on the IDs of an instruction. The
119 // can_have_forward_declared_ids functor should return true if the
120 // instruction operand's ID can be forward referenced.
IdPass(ValidationState_t & _,Instruction * inst)121 spv_result_t IdPass(ValidationState_t& _, Instruction* inst) {
122 auto can_have_forward_declared_ids =
123 inst->opcode() == spv::Op::OpExtInst &&
124 spvExtInstIsDebugInfo(inst->ext_inst_type())
125 ? spvDbgInfoExtOperandCanBeForwardDeclaredFunction(
126 inst->ext_inst_type(), inst->word(4))
127 : spvOperandCanBeForwardDeclaredFunction(inst->opcode());
128
129 // Keep track of a result id defined by this instruction. 0 means it
130 // does not define an id.
131 uint32_t result_id = 0;
132
133 for (unsigned i = 0; i < inst->operands().size(); i++) {
134 const spv_parsed_operand_t& operand = inst->operand(i);
135 const spv_operand_type_t& type = operand.type;
136 // We only care about Id operands, which are a single word.
137 const uint32_t operand_word = inst->word(operand.offset);
138
139 auto ret = SPV_ERROR_INTERNAL;
140 switch (type) {
141 case SPV_OPERAND_TYPE_RESULT_ID:
142 // NOTE: Multiple Id definitions are being checked by the binary parser.
143 //
144 // Defer undefined-forward-reference removal until after we've analyzed
145 // the remaining operands to this instruction. Deferral only matters
146 // for OpPhi since it's the only case where it defines its own forward
147 // reference. Other instructions that can have forward references
148 // either don't define a value or the forward reference is to a function
149 // Id (and hence defined outside of a function body).
150 result_id = operand_word;
151 // NOTE: The result Id is added (in RegisterInstruction) *after* all of
152 // the other Ids have been checked to avoid premature use in the same
153 // instruction.
154 ret = SPV_SUCCESS;
155 break;
156 case SPV_OPERAND_TYPE_ID:
157 case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
158 case SPV_OPERAND_TYPE_SCOPE_ID:
159 if (const auto def = _.FindDef(operand_word)) {
160 const auto opcode = inst->opcode();
161 if (spvOpcodeGeneratesType(def->opcode()) &&
162 !spvOpcodeGeneratesType(opcode) && !spvOpcodeIsDebug(opcode) &&
163 !inst->IsDebugInfo() && !inst->IsNonSemantic() &&
164 !spvOpcodeIsDecoration(opcode) && opcode != spv::Op::OpFunction &&
165 opcode != spv::Op::OpCooperativeMatrixLengthNV &&
166 opcode != spv::Op::OpCooperativeMatrixLengthKHR &&
167 !(opcode == spv::Op::OpSpecConstantOp &&
168 (spv::Op(inst->word(3)) ==
169 spv::Op::OpCooperativeMatrixLengthNV ||
170 spv::Op(inst->word(3)) ==
171 spv::Op::OpCooperativeMatrixLengthKHR))) {
172 return _.diag(SPV_ERROR_INVALID_ID, inst)
173 << "Operand " << _.getIdName(operand_word)
174 << " cannot be a type";
175 } else if (def->type_id() == 0 && !spvOpcodeGeneratesType(opcode) &&
176 !spvOpcodeIsDebug(opcode) && !inst->IsDebugInfo() &&
177 !inst->IsNonSemantic() && !spvOpcodeIsDecoration(opcode) &&
178 !spvOpcodeIsBranch(opcode) && opcode != spv::Op::OpPhi &&
179 opcode != spv::Op::OpExtInst &&
180 opcode != spv::Op::OpExtInstImport &&
181 opcode != spv::Op::OpSelectionMerge &&
182 opcode != spv::Op::OpLoopMerge &&
183 opcode != spv::Op::OpFunction &&
184 opcode != spv::Op::OpCooperativeMatrixLengthNV &&
185 opcode != spv::Op::OpCooperativeMatrixLengthKHR &&
186 !(opcode == spv::Op::OpSpecConstantOp &&
187 (spv::Op(inst->word(3)) ==
188 spv::Op::OpCooperativeMatrixLengthNV ||
189 spv::Op(inst->word(3)) ==
190 spv::Op::OpCooperativeMatrixLengthKHR))) {
191 return _.diag(SPV_ERROR_INVALID_ID, inst)
192 << "Operand " << _.getIdName(operand_word)
193 << " requires a type";
194 } else if (def->IsNonSemantic() && !inst->IsNonSemantic()) {
195 return _.diag(SPV_ERROR_INVALID_ID, inst)
196 << "Operand " << _.getIdName(operand_word)
197 << " in semantic instruction cannot be a non-semantic "
198 "instruction";
199 } else {
200 ret = SPV_SUCCESS;
201 }
202 } else if (can_have_forward_declared_ids(i)) {
203 if (spvOpcodeGeneratesType(inst->opcode()) &&
204 !_.IsForwardPointer(operand_word)) {
205 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
206 << "Operand " << _.getIdName(operand_word)
207 << " requires a previous definition";
208 } else {
209 ret = _.ForwardDeclareId(operand_word);
210 }
211 } else {
212 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
213 << "ID " << _.getIdName(operand_word)
214 << " has not been defined";
215 }
216 break;
217 case SPV_OPERAND_TYPE_TYPE_ID:
218 if (_.IsDefinedId(operand_word)) {
219 auto* def = _.FindDef(operand_word);
220 if (!spvOpcodeGeneratesType(def->opcode())) {
221 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
222 << "ID " << _.getIdName(operand_word) << " is not a type id";
223 } else {
224 ret = SPV_SUCCESS;
225 }
226 } else {
227 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
228 << "ID " << _.getIdName(operand_word)
229 << " has not been defined";
230 }
231 break;
232 default:
233 ret = SPV_SUCCESS;
234 break;
235 }
236 if (SPV_SUCCESS != ret) return ret;
237 }
238 if (result_id) _.RemoveIfForwardDeclared(result_id);
239
240 return SPV_SUCCESS;
241 }
242
243 } // namespace val
244 } // namespace spvtools
245