Debian Codegraph @

third_party/spirv-tools/source/fuzz/transformation_outline_function.h

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