1 // Copyright (c) 2020 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 "transformation_composite_insert.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/instruction_descriptor.h"
19
20 namespace spvtools {
21 namespace fuzz {
22
TransformationCompositeInsert(protobufs::TransformationCompositeInsert message)23 TransformationCompositeInsert::TransformationCompositeInsert(
24 protobufs::TransformationCompositeInsert message)
25 : message_(std::move(message)) {}
26
TransformationCompositeInsert(const protobufs::InstructionDescriptor & instruction_to_insert_before,uint32_t fresh_id,uint32_t composite_id,uint32_t object_id,const std::vector<uint32_t> & index)27 TransformationCompositeInsert::TransformationCompositeInsert(
28 const protobufs::InstructionDescriptor& instruction_to_insert_before,
29 uint32_t fresh_id, uint32_t composite_id, uint32_t object_id,
30 const std::vector<uint32_t>& index) {
31 *message_.mutable_instruction_to_insert_before() =
32 instruction_to_insert_before;
33 message_.set_fresh_id(fresh_id);
34 message_.set_composite_id(composite_id);
35 message_.set_object_id(object_id);
36 for (auto an_index : index) {
37 message_.add_index(an_index);
38 }
39 }
40
IsApplicable(opt::IRContext * ir_context,const TransformationContext &) const41 bool TransformationCompositeInsert::IsApplicable(
42 opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
43 // |message_.fresh_id| must be fresh.
44 if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
45 return false;
46 }
47
48 // |message_.composite_id| must refer to an existing composite value.
49 auto composite =
50 ir_context->get_def_use_mgr()->GetDef(message_.composite_id());
51
52 if (!IsCompositeInstructionSupported(ir_context, composite)) {
53 return false;
54 }
55
56 // The indices in |message_.index| must be suitable for indexing into
57 // |composite->type_id()|.
58 auto component_to_be_replaced_type_id = fuzzerutil::WalkCompositeTypeIndices(
59 ir_context, composite->type_id(), message_.index());
60 if (component_to_be_replaced_type_id == 0) {
61 return false;
62 }
63
64 // The instruction having the id of |message_.object_id| must be defined.
65 auto object_instruction =
66 ir_context->get_def_use_mgr()->GetDef(message_.object_id());
67 if (object_instruction == nullptr || object_instruction->type_id() == 0) {
68 return false;
69 }
70
71 // We ignore pointers for now.
72 auto object_instruction_type =
73 ir_context->get_type_mgr()->GetType(object_instruction->type_id());
74 if (object_instruction_type->AsPointer() != nullptr) {
75 return false;
76 }
77
78 // The type id of the object having |message_.object_id| and the type id of
79 // the component of the composite at index |message_.index| must be the same.
80 if (component_to_be_replaced_type_id != object_instruction->type_id()) {
81 return false;
82 }
83
84 // |message_.instruction_to_insert_before| must be a defined instruction.
85 auto instruction_to_insert_before =
86 FindInstruction(message_.instruction_to_insert_before(), ir_context);
87 if (instruction_to_insert_before == nullptr) {
88 return false;
89 }
90
91 // |message_.composite_id| and |message_.object_id| must be available before
92 // the |message_.instruction_to_insert_before|.
93 if (!fuzzerutil::IdIsAvailableBeforeInstruction(
94 ir_context, instruction_to_insert_before, message_.composite_id())) {
95 return false;
96 }
97 if (!fuzzerutil::IdIsAvailableBeforeInstruction(
98 ir_context, instruction_to_insert_before, message_.object_id())) {
99 return false;
100 }
101
102 // It must be possible to insert an OpCompositeInsert before this
103 // instruction.
104 return fuzzerutil::CanInsertOpcodeBeforeInstruction(
105 SpvOpCompositeInsert, instruction_to_insert_before);
106 }
107
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const108 void TransformationCompositeInsert::Apply(
109 opt::IRContext* ir_context,
110 TransformationContext* transformation_context) const {
111 // |message_.struct_fresh_id| must be fresh.
112 assert(fuzzerutil::IsFreshId(ir_context, message_.fresh_id()) &&
113 "|message_.fresh_id| must be fresh");
114
115 std::vector<uint32_t> index =
116 fuzzerutil::RepeatedFieldToVector(message_.index());
117 opt::Instruction::OperandList in_operands;
118 in_operands.push_back({SPV_OPERAND_TYPE_ID, {message_.object_id()}});
119 in_operands.push_back({SPV_OPERAND_TYPE_ID, {message_.composite_id()}});
120 for (auto i : index) {
121 in_operands.push_back({SPV_OPERAND_TYPE_LITERAL_INTEGER, {i}});
122 }
123 auto composite_type_id =
124 fuzzerutil::GetTypeId(ir_context, message_.composite_id());
125
126 auto insert_before =
127 FindInstruction(message_.instruction_to_insert_before(), ir_context);
128 auto new_instruction = MakeUnique<opt::Instruction>(
129 ir_context, SpvOpCompositeInsert, composite_type_id, message_.fresh_id(),
130 std::move(in_operands));
131 auto new_instruction_ptr = new_instruction.get();
132 insert_before->InsertBefore(std::move(new_instruction));
133
134 fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
135
136 // Inform the def-use manager about the new instruction and record its basic
137 // block.
138 ir_context->get_def_use_mgr()->AnalyzeInstDefUse(new_instruction_ptr);
139 ir_context->set_instr_block(new_instruction_ptr,
140 ir_context->get_instr_block(insert_before));
141
142 // Add data synonym facts that arise from the insertion.
143 AddDataSynonymFacts(ir_context, transformation_context);
144 }
145
ToMessage() const146 protobufs::Transformation TransformationCompositeInsert::ToMessage() const {
147 protobufs::Transformation result;
148 *result.mutable_composite_insert() = message_;
149 return result;
150 }
151
IsCompositeInstructionSupported(opt::IRContext * ir_context,opt::Instruction * instruction)152 bool TransformationCompositeInsert::IsCompositeInstructionSupported(
153 opt::IRContext* ir_context, opt::Instruction* instruction) {
154 if (instruction == nullptr) {
155 return false;
156 }
157 if (instruction->result_id() == 0 || instruction->type_id() == 0) {
158 return false;
159 }
160 auto composite_type =
161 ir_context->get_type_mgr()->GetType(instruction->type_id());
162 if (!fuzzerutil::IsCompositeType(composite_type)) {
163 return false;
164 }
165
166 // Empty composites are not supported.
167 auto instruction_type_inst =
168 ir_context->get_def_use_mgr()->GetDef(instruction->type_id());
169 if (fuzzerutil::GetBoundForCompositeIndex(*instruction_type_inst,
170 ir_context) == 0) {
171 return false;
172 }
173 return true;
174 }
175
GetFreshIds() const176 std::unordered_set<uint32_t> TransformationCompositeInsert::GetFreshIds()
177 const {
178 return {message_.fresh_id()};
179 }
180
AddDataSynonymFacts(opt::IRContext * ir_context,TransformationContext * transformation_context) const181 void TransformationCompositeInsert::AddDataSynonymFacts(
182 opt::IRContext* ir_context,
183 TransformationContext* transformation_context) const {
184 // If the result id arising from the insertion is irrelevant then do not add
185 // any data synonym facts. (The result id can be irrelevant if the insertion
186 // occurs in a dead block.)
187 if (transformation_context->GetFactManager()->IdIsIrrelevant(
188 message_.fresh_id())) {
189 return;
190 }
191
192 // So long as the |message_.composite_id| is suitable for participating in
193 // synonyms, every every element of the insertion result except for at the
194 // index being inserted into is synonymous with the corresponding element of
195 // |message_.composite_id|. In that case, for every index that is a prefix of
196 // |index|, the components different from the one that contains the inserted
197 // object are synonymous with corresponding elements in the original
198 // composite.
199 uint32_t current_node_type_id =
200 fuzzerutil::GetTypeId(ir_context, message_.composite_id());
201 std::vector<uint32_t> current_index;
202
203 std::vector<uint32_t> index =
204 fuzzerutil::RepeatedFieldToVector(message_.index());
205
206 for (uint32_t current_level : index) {
207 auto current_node_type_inst =
208 ir_context->get_def_use_mgr()->GetDef(current_node_type_id);
209 uint32_t index_to_skip = current_level;
210 uint32_t num_of_components = fuzzerutil::GetBoundForCompositeIndex(
211 *current_node_type_inst, ir_context);
212
213 // Update the current_node_type_id.
214 current_node_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
215 ir_context, current_node_type_id, index_to_skip);
216
217 for (uint32_t i = 0; i < num_of_components; i++) {
218 if (i == index_to_skip) {
219 continue;
220 }
221 current_index.push_back(i);
222 if (fuzzerutil::CanMakeSynonymOf(ir_context, *transformation_context,
223 *ir_context->get_def_use_mgr()->GetDef(
224 message_.composite_id()))) {
225 transformation_context->GetFactManager()->AddFactDataSynonym(
226 MakeDataDescriptor(message_.fresh_id(), current_index),
227 MakeDataDescriptor(message_.composite_id(), current_index));
228 }
229 current_index.pop_back();
230 }
231 // Store the prefix of the |index|.
232 current_index.push_back(current_level);
233 }
234 // If the object being inserted supports synonym creation then it is
235 // synonymous with the result of the insert instruction at the given index.
236 if (fuzzerutil::CanMakeSynonymOf(
237 ir_context, *transformation_context,
238 *ir_context->get_def_use_mgr()->GetDef(message_.object_id()))) {
239 transformation_context->GetFactManager()->AddFactDataSynonym(
240 MakeDataDescriptor(message_.object_id(), {}),
241 MakeDataDescriptor(message_.fresh_id(), index));
242 }
243 }
244
245 } // namespace fuzz
246 } // namespace spvtools
247