| 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 |
#ifndef SOURCE_FUZZ_TRANSFORMATION_OUTLINE_FUNCTION_H_ |
| 16 |
#define SOURCE_FUZZ_TRANSFORMATION_OUTLINE_FUNCTION_H_ |
| 17 |
|
| 18 |
#include <map> |
| 19 |
#include <set> |
| 20 |
#include <vector> |
| 21 |
|
| 22 |
#include "source/fuzz/protobufs/spirvfuzz_protobufs.h" |
| 23 |
#include "source/fuzz/transformation.h" |
| 24 |
#include "source/fuzz/transformation_context.h" |
| 25 |
#include "source/opt/ir_context.h" |
| 26 |
|
| 27 |
namespace spvtools { |
| 28 |
namespace fuzz { |
| 29 |
|
| 30 |
class TransformationOutlineFunction : public Transformation { |
| 31 |
public: |
| 32 |
explicit TransformationOutlineFunction( |
| 33 |
const protobufs::TransformationOutlineFunction& message); |
| 34 |
|
| 35 |
TransformationOutlineFunction( |
| 36 |
uint32_t entry_block, uint32_t exit_block, |
| 37 |
uint32_t new_function_struct_return_type_id, |
| 38 |
uint32_t new_function_type_id, uint32_t new_function_id, |
| 39 |
uint32_t new_function_region_entry_block, uint32_t new_caller_result_id, |
| 40 |
uint32_t new_callee_result_id, |
| 41 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id, |
| 42 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id); |
| 43 |
|
| 44 |
// - All the fresh ids occurring in the transformation must be distinct and |
| 45 |
// fresh |
| 46 |
// - |message_.entry_block| and |message_.exit_block| must form a single-entry |
| 47 |
// single-exit control flow graph region |
| 48 |
// - |message_.entry_block| must not start with OpVariable |
| 49 |
// - |message_.entry_block| must not be a loop header |
| 50 |
// - |message_.exit_block| must not be a merge block or the continue target |
| 51 |
// of a loop |
| 52 |
// - A structured control flow construct must lie either completely within the |
| 53 |
// region or completely outside it |
| 54 |
// - |message.entry_block| must not start with OpPhi; this is to keep the |
| 55 |
// transformation simple - another transformation should be used to split |
| 56 |
// a desired entry block that starts with OpPhi if needed |
| 57 |
// - |message_.input_id_to_fresh_id| must contain an entry for every id |
| 58 |
// defined outside the region but used in the region |
| 59 |
// - |message_.output_id_to_fresh_id| must contain an entry for every id |
| 60 |
// defined in the region but used outside the region |
| 61 |
bool IsApplicable( |
| 62 |
opt::IRContext* ir_context, |
| 63 |
const TransformationContext& transformation_context) const override; |
| 64 |
|
| 65 |
// - A new function with id |message_.new_function_id| is added to the module. |
| 66 |
// - If the region generates output ids, the return type of this function is |
| 67 |
// a new struct type with one field per output id, and with type id |
| 68 |
// |message_.new_function_struct_return_type|, otherwise the function return |
| 69 |
// types is void and |message_.new_function_struct_return_type| is not used. |
| 70 |
// - If the region generates input ids, the new function has one parameter per |
| 71 |
// input id. Fresh ids for these parameters are provided by |
| 72 |
// |message_.input_id_to_fresh_id|. |
| 73 |
// - Unless the type required for the new function is already known, |
| 74 |
// |message_.new_function_type_id| is used as the type id for a new function |
| 75 |
// type, and the new function uses this type. |
| 76 |
// - The new function starts with a placeholder block with id |
| 77 |
// |message_.new_function_first_block|, which jumps straight to a successor |
| 78 |
// block, to avoid violating rules on what the first block in a function may |
| 79 |
// look like. |
| 80 |
// - The outlined region is replaced with a single block, with the same id |
| 81 |
// as |message_.entry_block|, and which calls the new function, passing the |
| 82 |
// region's input ids as parameters. The result is stored in |
| 83 |
// |message_.new_caller_result_id|, which has type |
| 84 |
// |message_.new_function_struct_return_type| (unless there are |
| 85 |
// no output ids, in which case the return type is void). The components |
| 86 |
// of this returned struct are then copied out into the region's output ids. |
| 87 |
// The block ends with the merge instruction (if any) and terminator of |
| 88 |
// |message_.exit_block|. |
| 89 |
// - The body of the new function is identical to the outlined region, except |
| 90 |
// that (a) the region's entry block has id |
| 91 |
// |message_.new_function_region_entry_block|, (b) input id uses are |
| 92 |
// replaced with parameter accesses, (c) and definitions of output ids are |
| 93 |
// replaced with definitions of corresponding fresh ids provided by |
| 94 |
// |message_.output_id_to_fresh_id|, and (d) the block of the function |
| 95 |
// ends by returning a composite of type |
| 96 |
// |message_.new_function_struct_return_type| comprised of all the fresh |
| 97 |
// output ids (unless the return type is void, in which case no value is |
| 98 |
// returned. |
| 99 |
void Apply(opt::IRContext* ir_context, |
| 100 |
TransformationContext* transformation_context) const override; |
| 101 |
|
| 102 |
std::unordered_set<uint32_t> GetFreshIds() const override; |
| 103 |
|
| 104 |
protobufs::Transformation ToMessage() const override; |
| 105 |
|
| 106 |
// Returns the set of blocks dominated by |entry_block| and post-dominated |
| 107 |
// by |exit_block|. |
| 108 |
static std::set<opt::BasicBlock*> GetRegionBlocks( |
| 109 |
opt::IRContext* ir_context, opt::BasicBlock* entry_block, |
| 110 |
opt::BasicBlock* exit_block); |
| 111 |
|
| 112 |
// Yields ids that are used in |region_set| and that are either parameters |
| 113 |
// to the function containing |region_set|, or are defined by blocks of this |
| 114 |
// function that are outside |region_set|. |
| 115 |
// |
| 116 |
// Special cases: OpPhi instructions in |region_entry_block| and the |
| 117 |
// terminator of |region_exit_block| do not get outlined, therefore |
| 118 |
// - id uses in OpPhi instructions in |region_entry_block| are ignored |
| 119 |
// - id uses in the terminator instruction of |region_exit_block| are ignored |
| 120 |
static std::vector<uint32_t> GetRegionInputIds( |
| 121 |
opt::IRContext* ir_context, const std::set<opt::BasicBlock*>& region_set, |
| 122 |
opt::BasicBlock* region_exit_block); |
| 123 |
|
| 124 |
// Yields all ids that are defined in |region_set| and used outside |
| 125 |
// |region_set|. |
| 126 |
// |
| 127 |
// Special cases: for similar reasons as for |GetRegionInputIds|, |
| 128 |
// - ids defined in the region and used in the terminator of |
| 129 |
// |region_exit_block| count as output ids |
| 130 |
static std::vector<uint32_t> GetRegionOutputIds( |
| 131 |
opt::IRContext* ir_context, const std::set<opt::BasicBlock*>& region_set, |
| 132 |
opt::BasicBlock* region_exit_block); |
| 133 |
|
| 134 |
private: |
| 135 |
// Ensures that the module's id bound is at least the maximum of any fresh id |
| 136 |
// associated with the transformation. |
| 137 |
void UpdateModuleIdBoundForFreshIds( |
| 138 |
opt::IRContext* ir_context, |
| 139 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id_map, |
| 140 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id_map) const; |
| 141 |
|
| 142 |
// Uses |input_id_to_fresh_id_map| and |output_id_to_fresh_id_map| to convert, |
| 143 |
// in the region to be outlined, all the input ids in |region_input_ids| and |
| 144 |
// the output ids in |region_output_ids| to their fresh counterparts. |
| 145 |
// Parameters |region_blocks| provides access to the blocks that must be |
| 146 |
// modified, and |original_region_exit_block| allows for some special cases |
| 147 |
// where ids should not be remapped. |
| 148 |
void RemapInputAndOutputIdsInRegion( |
| 149 |
opt::IRContext* ir_context, |
| 150 |
const opt::BasicBlock& original_region_exit_block, |
| 151 |
const std::set<opt::BasicBlock*>& region_blocks, |
| 152 |
const std::vector<uint32_t>& region_input_ids, |
| 153 |
const std::vector<uint32_t>& region_output_ids, |
| 154 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id_map, |
| 155 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id_map) const; |
| 156 |
|
| 157 |
// Produce a Function object that has the right function type and parameter |
| 158 |
// declarations. The function argument types and parameter ids are dictated |
| 159 |
// by |region_input_ids| and |input_id_to_fresh_id_map|. The function return |
| 160 |
// type is dictated by |region_output_ids|. |
| 161 |
// |
| 162 |
// A new struct type to represent the function return type, and a new function |
| 163 |
// type for the function, will be added to the module (unless suitable types |
| 164 |
// are already present). |
| 165 |
// |
| 166 |
// Facts about the function containing the outlined region that are relevant |
| 167 |
// to the new function are propagated via the vact manager in |
| 168 |
// |transformation_context|. |
| 169 |
std::unique_ptr<opt::Function> PrepareFunctionPrototype( |
| 170 |
const std::vector<uint32_t>& region_input_ids, |
| 171 |
const std::vector<uint32_t>& region_output_ids, |
| 172 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id_map, |
| 173 |
opt::IRContext* ir_context, |
| 174 |
TransformationContext* transformation_context) const; |
| 175 |
|
| 176 |
// Creates the body of the outlined function by cloning blocks from the |
| 177 |
// original region, given by |region_blocks|, adapting the cloned version |
| 178 |
// of |original_region_exit_block| so that it returns something appropriate, |
| 179 |
// and patching up branches to |original_region_entry_block| to refer to its |
| 180 |
// clone. Parameters |region_output_ids| and |output_id_to_fresh_id_map| are |
| 181 |
// used to determine what the function should return. Parameter |
| 182 |
// |output_id_to_type_id| provides the type of each output id. |
| 183 |
// |
| 184 |
// The |transformation_context| argument allow facts about blocks being |
| 185 |
// outlined, e.g. whether they are dead blocks, to be asserted about blocks |
| 186 |
// that get created during outlining. |
| 187 |
void PopulateOutlinedFunction( |
| 188 |
const opt::BasicBlock& original_region_entry_block, |
| 189 |
const opt::BasicBlock& original_region_exit_block, |
| 190 |
const std::set<opt::BasicBlock*>& region_blocks, |
| 191 |
const std::vector<uint32_t>& region_output_ids, |
| 192 |
const std::map<uint32_t, uint32_t>& output_id_to_type_id, |
| 193 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id_map, |
| 194 |
opt::IRContext* ir_context, opt::Function* outlined_function) const; |
| 195 |
|
| 196 |
// Shrinks the outlined region, given by |region_blocks|, down to the single |
| 197 |
// block |original_region_entry_block|. This block is itself shrunk to just |
| 198 |
// contain: |
| 199 |
// - any OpPhi instructions that were originally present |
| 200 |
// - a call to the outlined function, with parameters provided by |
| 201 |
// |region_input_ids| |
| 202 |
// - instructions to route components of the call's return value into |
| 203 |
// |region_output_ids| |
| 204 |
// - The merge instruction (if any) and terminator of the original region's |
| 205 |
// exit block, given by |cloned_exit_block_merge| and |
| 206 |
// |cloned_exit_block_terminator| |
| 207 |
// Parameters |output_id_to_type_id| and |return_type_id| provide the |
| 208 |
// provide types for the region's output ids, and the return type of the |
| 209 |
// outlined function: as the module is in an inconsistent state when this |
| 210 |
// function is called, this information cannot be gotten from the def-use |
| 211 |
// manager. |
| 212 |
void ShrinkOriginalRegion( |
| 213 |
opt::IRContext* ir_context, |
| 214 |
const std::set<opt::BasicBlock*>& region_blocks, |
| 215 |
const std::vector<uint32_t>& region_input_ids, |
| 216 |
const std::vector<uint32_t>& region_output_ids, |
| 217 |
const std::map<uint32_t, uint32_t>& output_id_to_type_id, |
| 218 |
uint32_t return_type_id, |
| 219 |
std::unique_ptr<opt::Instruction> cloned_exit_block_merge, |
| 220 |
std::unique_ptr<opt::Instruction> cloned_exit_block_terminator, |
| 221 |
opt::BasicBlock* original_region_entry_block) const; |
| 222 |
|
| 223 |
protobufs::TransformationOutlineFunction message_; |
| 224 |
}; |
| 225 |
|
| 226 |
} // namespace fuzz |
| 227 |
} // namespace spvtools |
| 228 |
|
| 229 |
#endif // SOURCE_FUZZ_TRANSFORMATION_OUTLINE_FUNCTION_H_ |