1 // Copyright (c) 2020 André Perez Maselco
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_inline_function.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/instruction_descriptor.h"
19
20 namespace spvtools {
21 namespace fuzz {
22
TransformationInlineFunction(protobufs::TransformationInlineFunction message)23 TransformationInlineFunction::TransformationInlineFunction(
24 protobufs::TransformationInlineFunction message)
25 : message_(std::move(message)) {}
26
TransformationInlineFunction(uint32_t function_call_id,const std::map<uint32_t,uint32_t> & result_id_map)27 TransformationInlineFunction::TransformationInlineFunction(
28 uint32_t function_call_id,
29 const std::map<uint32_t, uint32_t>& result_id_map) {
30 message_.set_function_call_id(function_call_id);
31 *message_.mutable_result_id_map() =
32 fuzzerutil::MapToRepeatedUInt32Pair(result_id_map);
33 }
34
IsApplicable(opt::IRContext * ir_context,const TransformationContext & transformation_context) const35 bool TransformationInlineFunction::IsApplicable(
36 opt::IRContext* ir_context,
37 const TransformationContext& transformation_context) const {
38 // The values in the |message_.result_id_map| must be all fresh and all
39 // distinct.
40 const auto result_id_map =
41 fuzzerutil::RepeatedUInt32PairToMap(message_.result_id_map());
42 std::set<uint32_t> ids_used_by_this_transformation;
43 for (auto& pair : result_id_map) {
44 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
45 pair.second, ir_context, &ids_used_by_this_transformation)) {
46 return false;
47 }
48 }
49
50 // |function_call_instruction| must be suitable for inlining.
51 auto* function_call_instruction =
52 ir_context->get_def_use_mgr()->GetDef(message_.function_call_id());
53 if (!IsSuitableForInlining(ir_context, function_call_instruction)) {
54 return false;
55 }
56
57 // |function_call_instruction| must be the penultimate instruction in its
58 // block and its block termination instruction must be an OpBranch. This
59 // avoids the case where the penultimate instruction is an OpLoopMerge, which
60 // would make the back-edge block not branch to the loop header.
61 auto* function_call_instruction_block =
62 ir_context->get_instr_block(function_call_instruction);
63 if (function_call_instruction !=
64 &*--function_call_instruction_block->tail() ||
65 function_call_instruction_block->terminator()->opcode() !=
66 spv::Op::OpBranch) {
67 return false;
68 }
69
70 auto* called_function = fuzzerutil::FindFunction(
71 ir_context, function_call_instruction->GetSingleWordInOperand(0));
72 for (auto& block : *called_function) {
73 // Since the entry block label will not be inlined, only the remaining
74 // labels must have a corresponding value in the map.
75 if (&block != &*called_function->entry() &&
76 !result_id_map.count(block.id()) &&
77 !transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
78 return false;
79 }
80
81 // |result_id_map| must have an entry for every result id in the called
82 // function.
83 for (auto& instruction : block) {
84 // If |instruction| has result id, then it must have a mapped id in
85 // |result_id_map|.
86 if (instruction.HasResultId() &&
87 !result_id_map.count(instruction.result_id()) &&
88 !transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
89 return false;
90 }
91 }
92 }
93
94 // |result_id_map| must not contain an entry for any parameter of the function
95 // that is being inlined.
96 bool found_entry_for_parameter = false;
97 called_function->ForEachParam(
98 [&result_id_map, &found_entry_for_parameter](opt::Instruction* param) {
99 if (result_id_map.count(param->result_id())) {
100 found_entry_for_parameter = true;
101 }
102 });
103 return !found_entry_for_parameter;
104 }
105
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const106 void TransformationInlineFunction::Apply(
107 opt::IRContext* ir_context,
108 TransformationContext* transformation_context) const {
109 auto* function_call_instruction =
110 ir_context->get_def_use_mgr()->GetDef(message_.function_call_id());
111 auto* caller_function =
112 ir_context->get_instr_block(function_call_instruction)->GetParent();
113 auto* called_function = fuzzerutil::FindFunction(
114 ir_context, function_call_instruction->GetSingleWordInOperand(0));
115 std::map<uint32_t, uint32_t> result_id_map =
116 fuzzerutil::RepeatedUInt32PairToMap(message_.result_id_map());
117
118 // If there are gaps in the result id map, fill them using overflow ids.
119 for (auto& block : *called_function) {
120 if (&block != &*called_function->entry() &&
121 !result_id_map.count(block.id())) {
122 result_id_map.insert(
123 {block.id(),
124 transformation_context->GetOverflowIdSource()->GetNextOverflowId()});
125 }
126 for (auto& instruction : block) {
127 // If |instruction| has result id, then it must have a mapped id in
128 // |result_id_map|.
129 if (instruction.HasResultId() &&
130 !result_id_map.count(instruction.result_id())) {
131 result_id_map.insert({instruction.result_id(),
132 transformation_context->GetOverflowIdSource()
133 ->GetNextOverflowId()});
134 }
135 }
136 }
137
138 auto* successor_block = ir_context->cfg()->block(
139 ir_context->get_instr_block(function_call_instruction)
140 ->terminator()
141 ->GetSingleWordInOperand(0));
142
143 // Inline the |called_function| entry block.
144 for (auto& entry_block_instruction : *called_function->entry()) {
145 opt::Instruction* inlined_instruction;
146
147 if (entry_block_instruction.opcode() == spv::Op::OpVariable) {
148 // All OpVariable instructions in a function must be in the first block
149 // in the function.
150 inlined_instruction = caller_function->begin()->begin()->InsertBefore(
151 std::unique_ptr<opt::Instruction>(
152 entry_block_instruction.Clone(ir_context)));
153 } else {
154 inlined_instruction = function_call_instruction->InsertBefore(
155 std::unique_ptr<opt::Instruction>(
156 entry_block_instruction.Clone(ir_context)));
157 }
158
159 AdaptInlinedInstruction(result_id_map, ir_context, inlined_instruction);
160 }
161
162 // If the function call's successor block contains OpPhi instructions that
163 // refer to the block containing the call then these will need to be rewritten
164 // to instead refer to the block associated with "returning" from the inlined
165 // function, as this block will be the predecessor of what used to be the
166 // function call's successor block. We look out for this block.
167 uint32_t new_return_block_id = 0;
168
169 // Inline the |called_function| non-entry blocks.
170 for (auto& block : *called_function) {
171 if (&block == &*called_function->entry()) {
172 continue;
173 }
174
175 // Check whether this is the function's return block. Take note if it is,
176 // so that OpPhi instructions in the successor of the original function call
177 // block can be re-written.
178 if (block.terminator()->IsReturn()) {
179 assert(new_return_block_id == 0 &&
180 "There should be only one return block.");
181 new_return_block_id = result_id_map.at(block.id());
182 }
183
184 auto* cloned_block = block.Clone(ir_context);
185 cloned_block = caller_function->InsertBasicBlockBefore(
186 std::unique_ptr<opt::BasicBlock>(cloned_block), successor_block);
187 cloned_block->GetLabel()->SetResultId(result_id_map.at(cloned_block->id()));
188 fuzzerutil::UpdateModuleIdBound(ir_context, cloned_block->id());
189
190 for (auto& inlined_instruction : *cloned_block) {
191 AdaptInlinedInstruction(result_id_map, ir_context, &inlined_instruction);
192 }
193 }
194
195 opt::BasicBlock* block_containing_function_call =
196 ir_context->get_instr_block(function_call_instruction);
197
198 assert(((new_return_block_id == 0) ==
199 called_function->entry()->terminator()->IsReturn()) &&
200 "We should have found a return block unless the function being "
201 "inlined returns in its first block.");
202 if (new_return_block_id != 0) {
203 // Rewrite any OpPhi instructions in the successor block so that they refer
204 // to the new return block instead of the block that originally contained
205 // the function call.
206 ir_context->get_def_use_mgr()->ForEachUse(
207 block_containing_function_call->id(),
208 [ir_context, new_return_block_id, successor_block](
209 opt::Instruction* use_instruction, uint32_t operand_index) {
210 if (use_instruction->opcode() == spv::Op::OpPhi &&
211 ir_context->get_instr_block(use_instruction) == successor_block) {
212 use_instruction->SetOperand(operand_index, {new_return_block_id});
213 }
214 });
215 }
216
217 // Removes the function call instruction and its block termination instruction
218 // from |caller_function|.
219 ir_context->KillInst(block_containing_function_call->terminator());
220 ir_context->KillInst(function_call_instruction);
221
222 // Since the SPIR-V module has changed, no analyses must be validated.
223 ir_context->InvalidateAnalysesExceptFor(
224 opt::IRContext::Analysis::kAnalysisNone);
225 }
226
ToMessage() const227 protobufs::Transformation TransformationInlineFunction::ToMessage() const {
228 protobufs::Transformation result;
229 *result.mutable_inline_function() = message_;
230 return result;
231 }
232
IsSuitableForInlining(opt::IRContext * ir_context,opt::Instruction * function_call_instruction)233 bool TransformationInlineFunction::IsSuitableForInlining(
234 opt::IRContext* ir_context, opt::Instruction* function_call_instruction) {
235 // |function_call_instruction| must be defined and must be an OpFunctionCall
236 // instruction.
237 if (!function_call_instruction ||
238 function_call_instruction->opcode() != spv::Op::OpFunctionCall) {
239 return false;
240 }
241
242 // If |function_call_instruction| return type is void, then
243 // |function_call_instruction| must not have uses.
244 if (ir_context->get_type_mgr()
245 ->GetType(function_call_instruction->type_id())
246 ->AsVoid() &&
247 ir_context->get_def_use_mgr()->NumUses(function_call_instruction) != 0) {
248 return false;
249 }
250
251 // |called_function| must not have an early return.
252 auto called_function = fuzzerutil::FindFunction(
253 ir_context, function_call_instruction->GetSingleWordInOperand(0));
254 if (called_function->HasEarlyReturn()) {
255 return false;
256 }
257
258 // |called_function| must not use OpKill or OpUnreachable.
259 if (fuzzerutil::FunctionContainsOpKillOrUnreachable(*called_function)) {
260 return false;
261 }
262
263 return true;
264 }
265
AdaptInlinedInstruction(const std::map<uint32_t,uint32_t> & result_id_map,opt::IRContext * ir_context,opt::Instruction * instruction_to_be_inlined) const266 void TransformationInlineFunction::AdaptInlinedInstruction(
267 const std::map<uint32_t, uint32_t>& result_id_map,
268 opt::IRContext* ir_context,
269 opt::Instruction* instruction_to_be_inlined) const {
270 auto* function_call_instruction =
271 ir_context->get_def_use_mgr()->GetDef(message_.function_call_id());
272 auto* called_function = fuzzerutil::FindFunction(
273 ir_context, function_call_instruction->GetSingleWordInOperand(0));
274
275 const auto* function_call_block =
276 ir_context->get_instr_block(function_call_instruction);
277 assert(function_call_block && "OpFunctionCall must belong to some block");
278
279 // Replaces the operand ids with their mapped result ids.
280 instruction_to_be_inlined->ForEachInId(
281 [called_function, function_call_instruction, &result_id_map,
282 function_call_block](uint32_t* id) {
283 // We are not inlining the entry block of the |called_function|.
284 //
285 // We must check this condition first since we can't use the fresh id
286 // from |result_id_map| even if it has one. This is because that fresh
287 // id will never be added to the module since entry blocks are not
288 // inlined.
289 if (*id == called_function->entry()->id()) {
290 *id = function_call_block->id();
291 return;
292 }
293
294 // If |id| is mapped, then set it to its mapped value.
295 if (result_id_map.count(*id)) {
296 *id = result_id_map.at(*id);
297 return;
298 }
299
300 uint32_t parameter_index = 0;
301 called_function->ForEachParam(
302 [id, function_call_instruction,
303 ¶meter_index](opt::Instruction* parameter_instruction) {
304 // If the id is a function parameter, then set it to the
305 // parameter value passed in the function call instruction.
306 if (*id == parameter_instruction->result_id()) {
307 // We do + 1 because the first in-operand for OpFunctionCall is
308 // the function id that is being called.
309 *id = function_call_instruction->GetSingleWordInOperand(
310 parameter_index + 1);
311 }
312 parameter_index++;
313 });
314 });
315
316 // If |instruction_to_be_inlined| has result id, then set it to its mapped
317 // value.
318 if (instruction_to_be_inlined->HasResultId()) {
319 assert(result_id_map.count(instruction_to_be_inlined->result_id()) &&
320 "Result id must be mapped to a fresh id.");
321 instruction_to_be_inlined->SetResultId(
322 result_id_map.at(instruction_to_be_inlined->result_id()));
323 fuzzerutil::UpdateModuleIdBound(ir_context,
324 instruction_to_be_inlined->result_id());
325 }
326
327 // The return instruction will be changed into an OpBranch to the basic
328 // block that follows the block containing the function call.
329 if (spvOpcodeIsReturn(instruction_to_be_inlined->opcode())) {
330 uint32_t successor_block_id =
331 ir_context->get_instr_block(function_call_instruction)
332 ->terminator()
333 ->GetSingleWordInOperand(0);
334 switch (instruction_to_be_inlined->opcode()) {
335 case spv::Op::OpReturn:
336 instruction_to_be_inlined->AddOperand(
337 {SPV_OPERAND_TYPE_ID, {successor_block_id}});
338 break;
339 case spv::Op::OpReturnValue: {
340 instruction_to_be_inlined->InsertBefore(MakeUnique<opt::Instruction>(
341 ir_context, spv::Op::OpCopyObject,
342 function_call_instruction->type_id(),
343 function_call_instruction->result_id(),
344 opt::Instruction::OperandList(
345 {{SPV_OPERAND_TYPE_ID,
346 {instruction_to_be_inlined->GetSingleWordOperand(0)}}})));
347 instruction_to_be_inlined->SetInOperand(0, {successor_block_id});
348 break;
349 }
350 default:
351 break;
352 }
353 instruction_to_be_inlined->SetOpcode(spv::Op::OpBranch);
354 }
355 }
356
GetFreshIds() const357 std::unordered_set<uint32_t> TransformationInlineFunction::GetFreshIds() const {
358 std::unordered_set<uint32_t> result;
359 for (auto& pair : message_.result_id_map()) {
360 result.insert(pair.second());
361 }
362 return result;
363 }
364
365 } // namespace fuzz
366 } // namespace spvtools
367