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_ 230