• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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              &parameter_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