1 // Copyright (c) 2019 Google LLC
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 "source/fuzz/transformation_composite_construct.h"
16
17 #include "source/fuzz/data_descriptor.h"
18 #include "source/fuzz/fuzzer_util.h"
19 #include "source/fuzz/instruction_descriptor.h"
20 #include "source/opt/instruction.h"
21
22 namespace spvtools {
23 namespace fuzz {
24
TransformationCompositeConstruct(protobufs::TransformationCompositeConstruct message)25 TransformationCompositeConstruct::TransformationCompositeConstruct(
26 protobufs::TransformationCompositeConstruct message)
27 : message_(std::move(message)) {}
28
TransformationCompositeConstruct(uint32_t composite_type_id,std::vector<uint32_t> component,const protobufs::InstructionDescriptor & instruction_to_insert_before,uint32_t fresh_id)29 TransformationCompositeConstruct::TransformationCompositeConstruct(
30 uint32_t composite_type_id, std::vector<uint32_t> component,
31 const protobufs::InstructionDescriptor& instruction_to_insert_before,
32 uint32_t fresh_id) {
33 message_.set_composite_type_id(composite_type_id);
34 for (auto a_component : component) {
35 message_.add_component(a_component);
36 }
37 *message_.mutable_instruction_to_insert_before() =
38 instruction_to_insert_before;
39 message_.set_fresh_id(fresh_id);
40 }
41
IsApplicable(opt::IRContext * ir_context,const TransformationContext &) const42 bool TransformationCompositeConstruct::IsApplicable(
43 opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
44 if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
45 // We require the id for the composite constructor to be unused.
46 return false;
47 }
48
49 auto insert_before =
50 FindInstruction(message_.instruction_to_insert_before(), ir_context);
51 if (!insert_before) {
52 // The instruction before which the composite should be inserted was not
53 // found.
54 return false;
55 }
56
57 auto composite_type =
58 ir_context->get_type_mgr()->GetType(message_.composite_type_id());
59
60 if (!fuzzerutil::IsCompositeType(composite_type)) {
61 // The type must actually be a composite.
62 return false;
63 }
64
65 // If the type is an array, matrix, struct or vector, the components need to
66 // be suitable for constructing something of that type.
67 if (composite_type->AsArray() &&
68 !ComponentsForArrayConstructionAreOK(ir_context,
69 *composite_type->AsArray())) {
70 return false;
71 }
72 if (composite_type->AsMatrix() &&
73 !ComponentsForMatrixConstructionAreOK(ir_context,
74 *composite_type->AsMatrix())) {
75 return false;
76 }
77 if (composite_type->AsStruct() &&
78 !ComponentsForStructConstructionAreOK(ir_context,
79 *composite_type->AsStruct())) {
80 return false;
81 }
82 if (composite_type->AsVector() &&
83 !ComponentsForVectorConstructionAreOK(ir_context,
84 *composite_type->AsVector())) {
85 return false;
86 }
87
88 // Now check whether every component being used to initialize the composite is
89 // available at the desired program point.
90 for (auto component : message_.component()) {
91 auto* inst = ir_context->get_def_use_mgr()->GetDef(component);
92 if (!inst) {
93 return false;
94 }
95
96 if (!fuzzerutil::IdIsAvailableBeforeInstruction(ir_context, insert_before,
97 component)) {
98 return false;
99 }
100 }
101
102 return true;
103 }
104
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const105 void TransformationCompositeConstruct::Apply(
106 opt::IRContext* ir_context,
107 TransformationContext* transformation_context) const {
108 // Use the base and offset information from the transformation to determine
109 // where in the module a new instruction should be inserted.
110 auto insert_before_inst =
111 FindInstruction(message_.instruction_to_insert_before(), ir_context);
112 auto destination_block = ir_context->get_instr_block(insert_before_inst);
113 auto insert_before = fuzzerutil::GetIteratorForInstruction(
114 destination_block, insert_before_inst);
115
116 // Prepare the input operands for an OpCompositeConstruct instruction.
117 opt::Instruction::OperandList in_operands;
118 for (auto& component_id : message_.component()) {
119 in_operands.push_back({SPV_OPERAND_TYPE_ID, {component_id}});
120 }
121
122 // Insert an OpCompositeConstruct instruction.
123 auto new_instruction = MakeUnique<opt::Instruction>(
124 ir_context, SpvOpCompositeConstruct, message_.composite_type_id(),
125 message_.fresh_id(), in_operands);
126 auto new_instruction_ptr = new_instruction.get();
127 insert_before.InsertBefore(std::move(new_instruction));
128 ir_context->get_def_use_mgr()->AnalyzeInstDefUse(new_instruction_ptr);
129 ir_context->set_instr_block(new_instruction_ptr, destination_block);
130
131 fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
132
133 // No analyses need to be invalidated since the transformation is local to a
134 // block and the def-use and instruction-to-block mappings have been updated.
135
136 AddDataSynonymFacts(ir_context, transformation_context);
137 }
138
ComponentsForArrayConstructionAreOK(opt::IRContext * ir_context,const opt::analysis::Array & array_type) const139 bool TransformationCompositeConstruct::ComponentsForArrayConstructionAreOK(
140 opt::IRContext* ir_context, const opt::analysis::Array& array_type) const {
141 if (array_type.length_info().words[0] !=
142 opt::analysis::Array::LengthInfo::kConstant) {
143 // We only handle constant-sized arrays.
144 return false;
145 }
146 if (array_type.length_info().words.size() != 2) {
147 // We only handle the case where the array size can be captured in a single
148 // word.
149 return false;
150 }
151 // Get the array size.
152 auto array_size = array_type.length_info().words[1];
153 if (static_cast<uint32_t>(message_.component().size()) != array_size) {
154 // The number of components must match the array size.
155 return false;
156 }
157 // Check that each component is the result id of an instruction whose type is
158 // the array's element type.
159 for (auto component_id : message_.component()) {
160 auto inst = ir_context->get_def_use_mgr()->GetDef(component_id);
161 if (inst == nullptr || !inst->type_id()) {
162 // The component does not correspond to an instruction with a result
163 // type.
164 return false;
165 }
166 auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
167 assert(component_type);
168 if (component_type != array_type.element_type()) {
169 // The component's type does not match the array's element type.
170 return false;
171 }
172 }
173 return true;
174 }
175
ComponentsForMatrixConstructionAreOK(opt::IRContext * ir_context,const opt::analysis::Matrix & matrix_type) const176 bool TransformationCompositeConstruct::ComponentsForMatrixConstructionAreOK(
177 opt::IRContext* ir_context,
178 const opt::analysis::Matrix& matrix_type) const {
179 if (static_cast<uint32_t>(message_.component().size()) !=
180 matrix_type.element_count()) {
181 // The number of components must match the number of columns of the matrix.
182 return false;
183 }
184 // Check that each component is the result id of an instruction whose type is
185 // the matrix's column type.
186 for (auto component_id : message_.component()) {
187 auto inst = ir_context->get_def_use_mgr()->GetDef(component_id);
188 if (inst == nullptr || !inst->type_id()) {
189 // The component does not correspond to an instruction with a result
190 // type.
191 return false;
192 }
193 auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
194 assert(component_type);
195 if (component_type != matrix_type.element_type()) {
196 // The component's type does not match the matrix's column type.
197 return false;
198 }
199 }
200 return true;
201 }
202
ComponentsForStructConstructionAreOK(opt::IRContext * ir_context,const opt::analysis::Struct & struct_type) const203 bool TransformationCompositeConstruct::ComponentsForStructConstructionAreOK(
204 opt::IRContext* ir_context,
205 const opt::analysis::Struct& struct_type) const {
206 if (static_cast<uint32_t>(message_.component().size()) !=
207 struct_type.element_types().size()) {
208 // The number of components must match the number of fields of the struct.
209 return false;
210 }
211 // Check that each component is the result id of an instruction those type
212 // matches the associated field type.
213 for (uint32_t field_index = 0;
214 field_index < struct_type.element_types().size(); field_index++) {
215 auto inst = ir_context->get_def_use_mgr()->GetDef(
216 message_.component()[field_index]);
217 if (inst == nullptr || !inst->type_id()) {
218 // The component does not correspond to an instruction with a result
219 // type.
220 return false;
221 }
222 auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
223 assert(component_type);
224 if (component_type != struct_type.element_types()[field_index]) {
225 // The component's type does not match the corresponding field type.
226 return false;
227 }
228 }
229 return true;
230 }
231
ComponentsForVectorConstructionAreOK(opt::IRContext * ir_context,const opt::analysis::Vector & vector_type) const232 bool TransformationCompositeConstruct::ComponentsForVectorConstructionAreOK(
233 opt::IRContext* ir_context,
234 const opt::analysis::Vector& vector_type) const {
235 uint32_t base_element_count = 0;
236 auto element_type = vector_type.element_type();
237 for (auto& component_id : message_.component()) {
238 auto inst = ir_context->get_def_use_mgr()->GetDef(component_id);
239 if (inst == nullptr || !inst->type_id()) {
240 // The component does not correspond to an instruction with a result
241 // type.
242 return false;
243 }
244 auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
245 assert(component_type);
246 if (component_type == element_type) {
247 base_element_count++;
248 } else if (component_type->AsVector() &&
249 component_type->AsVector()->element_type() == element_type) {
250 base_element_count += component_type->AsVector()->element_count();
251 } else {
252 // The component was not appropriate; e.g. no type corresponding to the
253 // given id was found, or the type that was found was not compatible
254 // with the vector being constructed.
255 return false;
256 }
257 }
258 // The number of components provided (when vector components are flattened
259 // out) needs to match the length of the vector being constructed.
260 return base_element_count == vector_type.element_count();
261 }
262
ToMessage() const263 protobufs::Transformation TransformationCompositeConstruct::ToMessage() const {
264 protobufs::Transformation result;
265 *result.mutable_composite_construct() = message_;
266 return result;
267 }
268
GetFreshIds() const269 std::unordered_set<uint32_t> TransformationCompositeConstruct::GetFreshIds()
270 const {
271 return {message_.fresh_id()};
272 }
273
AddDataSynonymFacts(opt::IRContext * ir_context,TransformationContext * transformation_context) const274 void TransformationCompositeConstruct::AddDataSynonymFacts(
275 opt::IRContext* ir_context,
276 TransformationContext* transformation_context) const {
277 // If the result id of the composite we are constructing is irrelevant (e.g.
278 // because it is in a dead block) then we do not make any synonyms.
279 if (transformation_context->GetFactManager()->IdIsIrrelevant(
280 message_.fresh_id())) {
281 return;
282 }
283
284 // Inform the fact manager that we now have new synonyms: every component of
285 // the composite is synonymous with the id used to construct that component
286 // (so long as it is legitimate to create a synonym from that id), except in
287 // the case of a vector where a single vector id can span multiple components.
288 auto composite_type =
289 ir_context->get_type_mgr()->GetType(message_.composite_type_id());
290 uint32_t index = 0;
291 for (auto component : message_.component()) {
292 auto component_type = ir_context->get_type_mgr()->GetType(
293 ir_context->get_def_use_mgr()->GetDef(component)->type_id());
294 // Whether the component is a vector being packed into a vector determines
295 // how we should keep track of the indices associated with components.
296 const bool packing_vector_into_vector =
297 composite_type->AsVector() && component_type->AsVector();
298 if (!fuzzerutil::CanMakeSynonymOf(
299 ir_context, *transformation_context,
300 *ir_context->get_def_use_mgr()->GetDef(component))) {
301 // We can't make a synonym of this component, so we skip on to the next
302 // component. In the case where we're packing a vector into a vector we
303 // have to skip as many components of the resulting vectors as there are
304 // elements of the component vector.
305 index += packing_vector_into_vector
306 ? component_type->AsVector()->element_count()
307 : 1;
308 continue;
309 }
310 if (packing_vector_into_vector) {
311 // The case where the composite being constructed is a vector and the
312 // component provided for construction is also a vector is special. It
313 // requires adding a synonym fact relating each element of the sub-vector
314 // to the corresponding element of the composite being constructed.
315 assert(component_type->AsVector()->element_type() ==
316 composite_type->AsVector()->element_type());
317 assert(component_type->AsVector()->element_count() <
318 composite_type->AsVector()->element_count());
319 for (uint32_t subvector_index = 0;
320 subvector_index < component_type->AsVector()->element_count();
321 subvector_index++) {
322 transformation_context->GetFactManager()->AddFactDataSynonym(
323 MakeDataDescriptor(component, {subvector_index}),
324 MakeDataDescriptor(message_.fresh_id(), {index}));
325 index++;
326 }
327 } else {
328 // The other cases are simple: the component is made directly synonymous
329 // with the element of the composite being constructed.
330 transformation_context->GetFactManager()->AddFactDataSynonym(
331 MakeDataDescriptor(component, {}),
332 MakeDataDescriptor(message_.fresh_id(), {index}));
333 index++;
334 }
335 }
336 }
337
338 } // namespace fuzz
339 } // namespace spvtools
340