Debian Codegraph @

third_party/spirv-tools/source/val/function.h

raw
1 // Copyright (c) 2015-2016 The Khronos Group Inc.
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_VAL_FUNCTION_H_
16 #define SOURCE_VAL_FUNCTION_H_
17
18 #include <functional>
19 #include <list>
20 #include <map>
21 #include <set>
22 #include <string>
23 #include <unordered_map>
24 #include <unordered_set>
25 #include <utility>
26 #include <vector>
27
28 #include "source/latest_version_spirv_header.h"
29 #include "source/val/basic_block.h"
30 #include "source/val/construct.h"
31 #include "spirv-tools/libspirv.h"
32
33 namespace spvtools {
34 namespace val {
35
36 struct bb_constr_type_pair_hash {
37 std::size_t operator()(
38 const std::pair<const BasicBlock*, ConstructType>& p) const {
39 auto h1 = std::hash<const BasicBlock*>{}(p.first);
40 auto h2 = std::hash<std::underlying_type<ConstructType>::type>{}(
41 static_cast<std::underlying_type<ConstructType>::type>(p.second));
42 return (h1 ^ h2);
43 }
44 };
45
46 enum class FunctionDecl {
47 kFunctionDeclUnknown, /// < Unknown function declaration
48 kFunctionDeclDeclaration, /// < Function declaration
49 kFunctionDeclDefinition /// < Function definition
50 };
51
52 /// This class manages all function declaration and definitions in a module. It
53 /// handles the state and id information while parsing a function in the SPIR-V
54 /// binary.
55 class Function {
56 public:
57 Function(uint32_t id, uint32_t result_type_id,
58 SpvFunctionControlMask function_control, uint32_t function_type_id);
59
60 /// Registers a function parameter in the current function
61 /// @return Returns SPV_SUCCESS if the call was successful
62 spv_result_t RegisterFunctionParameter(uint32_t id, uint32_t type_id);
63
64 /// Sets the declaration type of the current function
65 /// @return Returns SPV_SUCCESS if the call was successful
66 spv_result_t RegisterSetFunctionDeclType(FunctionDecl type);
67
68 /// Registers a block in the current function. Subsequent block instructions
69 /// will target this block
70 /// @param id The ID of the label of the block
71 /// @return Returns SPV_SUCCESS if the call was successful
72 spv_result_t RegisterBlock(uint32_t id, bool is_definition = true);
73
74 /// Registers a variable in the current block
75 ///
76 /// @param[in] type_id The type ID of the varaible
77 /// @param[in] id The ID of the varaible
78 /// @param[in] storage The storage of the variable
79 /// @param[in] init_id The initializer ID of the variable
80 ///
81 /// @return Returns SPV_SUCCESS if the call was successful
82 spv_result_t RegisterBlockVariable(uint32_t type_id, uint32_t id,
83 SpvStorageClass storage, uint32_t init_id);
84
85 /// Registers a loop merge construct in the function
86 ///
87 /// @param[in] merge_id The merge block ID of the loop
88 /// @param[in] continue_id The continue block ID of the loop
89 ///
90 /// @return Returns SPV_SUCCESS if the call was successful
91 spv_result_t RegisterLoopMerge(uint32_t merge_id, uint32_t continue_id);
92
93 /// Registers a selection merge construct in the function
94 /// @return Returns SPV_SUCCESS if the call was successful
95 spv_result_t RegisterSelectionMerge(uint32_t merge_id);
96
97 /// Registers the end of the block
98 ///
99 /// @param[in] successors_list A list of ids to the block's successors
100 void RegisterBlockEnd(std::vector<uint32_t> successors_list);
101
102 /// Registers the end of the function. This is idempotent.
103 void RegisterFunctionEnd();
104
105 /// Returns true if the \p id block is the first block of this function
106 bool IsFirstBlock(uint32_t id) const;
107
108 /// Returns true if the \p merge_block_id is a BlockType of \p type
109 bool IsBlockType(uint32_t merge_block_id, BlockType type) const;
110
111 /// Returns a pair consisting of the BasicBlock with \p id and a bool
112 /// which is true if the block has been defined, and false if it is
113 /// declared but not defined. This function will return nullptr if the
114 /// \p id was not declared and not defined at the current point in the binary
115 std::pair<const BasicBlock*, bool> GetBlock(uint32_t id) const;
116 std::pair<BasicBlock*, bool> GetBlock(uint32_t id);
117
118 /// Returns the first block of the current function
119 const BasicBlock* first_block() const;
120
121 /// Returns the first block of the current function
122 BasicBlock* first_block();
123
124 /// Returns a vector of all the blocks in the function
125 const std::vector<BasicBlock*>& ordered_blocks() const;
126
127 /// Returns a vector of all the blocks in the function
128 std::vector<BasicBlock*>& ordered_blocks();
129
130 /// Returns a list of all the cfg constructs in the function
131 const std::list<Construct>& constructs() const;
132
133 /// Returns a list of all the cfg constructs in the function
134 std::list<Construct>& constructs();
135
136 /// Returns the number of blocks in the current function being parsed
137 size_t block_count() const;
138
139 /// Returns the id of the function
140 uint32_t id() const { return id_; }
141
142 /// Returns return type id of the function
143 uint32_t GetResultTypeId() const { return result_type_id_; }
144
145 /// Returns the number of blocks in the current function being parsed
146 size_t undefined_block_count() const;
147 const std::unordered_set<uint32_t>& undefined_blocks() const {
148 return undefined_blocks_;
149 }
150
151 /// Returns the block that is currently being parsed in the binary
152 BasicBlock* current_block();
153
154 /// Returns the block that is currently being parsed in the binary
155 const BasicBlock* current_block() const;
156
157 // For dominance calculations, we want to analyze all the
158 // blocks in the function, even in degenerate control flow cases
159 // including unreachable blocks. We therefore make an "augmented CFG"
160 // which is the same as the ordinary CFG but adds:
161 // - A pseudo-entry node.
162 // - A pseudo-exit node.
163 // - A minimal set of edges so that a forward traversal from the
164 // pseudo-entry node will visit all nodes.
165 // - A minimal set of edges so that a backward traversal from the
166 // pseudo-exit node will visit all nodes.
167 // In particular, the pseudo-entry node is the unique source of the
168 // augmented CFG, and the psueo-exit node is the unique sink of the
169 // augmented CFG.
170
171 /// Returns the pseudo exit block
172 BasicBlock* pseudo_entry_block() { return &pseudo_entry_block_; }
173
174 /// Returns the pseudo exit block
175 const BasicBlock* pseudo_entry_block() const { return &pseudo_entry_block_; }
176
177 /// Returns the pseudo exit block
178 BasicBlock* pseudo_exit_block() { return &pseudo_exit_block_; }
179
180 /// Returns the pseudo exit block
181 const BasicBlock* pseudo_exit_block() const { return &pseudo_exit_block_; }
182
183 using GetBlocksFunction =
184 std::function<const std::vector<BasicBlock*>*(const BasicBlock*)>;
185 /// Returns the block successors function for the augmented CFG.
186 GetBlocksFunction AugmentedCFGSuccessorsFunction() const;
187 /// Like AugmentedCFGSuccessorsFunction, but also includes a forward edge from
188 /// a loop header block to its continue target, if they are different blocks.
189 GetBlocksFunction
190 AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge() const;
191 /// Returns the block predecessors function for the augmented CFG.
192 GetBlocksFunction AugmentedCFGPredecessorsFunction() const;
193
194 /// Returns the control flow nesting depth of the given basic block.
195 /// This function only works when you have structured control flow.
196 /// This function should only be called after the control flow constructs have
197 /// been identified and dominators have been computed.
198 int GetBlockDepth(BasicBlock* bb);
199
200 /// Prints a GraphViz digraph of the CFG of the current funciton
201 void PrintDotGraph() const;
202
203 /// Prints a directed graph of the CFG of the current funciton
204 void PrintBlocks() const;
205
206 /// Registers execution model limitation such as "Feature X is only available
207 /// with Execution Model Y".
208 void RegisterExecutionModelLimitation(SpvExecutionModel model,
209 const std::string& message);
210
211 /// Registers execution model limitation with an |is_compatible| functor.
212 void RegisterExecutionModelLimitation(
213 std::function<bool(SpvExecutionModel, std::string*)> is_compatible) {
214 execution_model_limitations_.push_back(is_compatible);
215 }
216
217 /// Registers limitation with an |is_compatible| functor.
218 void RegisterLimitation(std::function<bool(const ValidationState_t& _,
219 const Function*, std::string*)>
220 is_compatible) {
221 limitations_.push_back(is_compatible);
222 }
223
224 bool CheckLimitations(const ValidationState_t& _, const Function* entry_point,
225 std::string* reason) const;
226
227 /// Returns true if the given execution model passes the limitations stored in
228 /// execution_model_limitations_. Returns false otherwise and fills optional
229 /// |reason| parameter.
230 bool IsCompatibleWithExecutionModel(SpvExecutionModel model,
231 std::string* reason = nullptr) const;
232
233 // Inserts id to the set of functions called from this function.
234 void AddFunctionCallTarget(uint32_t call_target_id) {
235 function_call_targets_.insert(call_target_id);
236 }
237
238 // Returns a set with ids of all functions called from this function.
239 const std::set<uint32_t> function_call_targets() const {
240 return function_call_targets_;
241 }
242
243 // Returns the block containing the OpSelectionMerge or OpLoopMerge that
244 // references |merge_block|.
245 // Values of |merge_block_header_| inserted by CFGPass, so do not call before
246 // the first iteration of ordered instructions in
247 // ValidateBinaryUsingContextAndValidationState has completed.
248 BasicBlock* GetMergeHeader(BasicBlock* merge_block) {
249 return merge_block_header_[merge_block];
250 }
251
252 // Returns vector of the blocks containing a OpLoopMerge that references
253 // |continue_target|.
254 // Values of |continue_target_headers_| inserted by CFGPass, so do not call
255 // before the first iteration of ordered instructions in
256 // ValidateBinaryUsingContextAndValidationState has completed.
257 std::vector<BasicBlock*> GetContinueHeaders(BasicBlock* continue_target) {
258 if (continue_target_headers_.find(continue_target) ==
259 continue_target_headers_.end()) {
260 return {};
261 }
262 return continue_target_headers_[continue_target];
263 }
264
265 private:
266 // Computes the representation of the augmented CFG.
267 // Populates augmented_successors_map_ and augmented_predecessors_map_.
268 void ComputeAugmentedCFG();
269
270 // Adds a copy of the given Construct, and tracks it by its entry block.
271 // Returns a reference to the stored construct.
272 Construct& AddConstruct(const Construct& new_construct);
273
274 // Returns a reference to the construct corresponding to the given entry
275 // block.
276 Construct& FindConstructForEntryBlock(const BasicBlock* entry_block,
277 ConstructType t);
278
279 /// The result id of the OpLabel that defined this block
280 uint32_t id_;
281
282 /// The type of the function
283 uint32_t function_type_id_;
284
285 /// The type of the return value
286 uint32_t result_type_id_;
287
288 /// The control fo the funciton
289 SpvFunctionControlMask function_control_;
290
291 /// The type of declaration of each function
292 FunctionDecl declaration_type_;
293
294 // Have we finished parsing this function?
295 bool end_has_been_registered_;
296
297 /// The blocks in the function mapped by block ID
298 std::unordered_map<uint32_t, BasicBlock> blocks_;
299
300 /// A list of blocks in the order they appeared in the binary
301 std::vector<BasicBlock*> ordered_blocks_;
302
303 /// Blocks which are forward referenced by blocks but not defined
304 std::unordered_set<uint32_t> undefined_blocks_;
305
306 /// The block that is currently being parsed
307 BasicBlock* current_block_;
308
309 /// A pseudo entry node used in dominance analysis.
310 /// After the function end has been registered, the successor list of the
311 /// pseudo entry node is the minimal set of nodes such that all nodes in the
312 /// CFG can be reached by following successor lists. That is, the successors
313 /// will be:
314 /// - Any basic block without predecessors. This includes the entry
315 /// block to the function.
316 /// - A single node from each otherwise unreachable cycle in the CFG, if
317 /// such cycles exist.
318 /// The pseudo entry node does not appear in the predecessor or successor
319 /// list of any ordinary block.
320 /// It has no predecessors.
321 /// It has Id 0.
322 BasicBlock pseudo_entry_block_;
323
324 /// A pseudo exit block used in dominance analysis.
325 /// After the function end has been registered, the predecessor list of the
326 /// pseudo exit node is the minimal set of nodes such that all nodes in the
327 /// CFG can be reached by following predecessor lists. That is, the
328 /// predecessors will be:
329 /// - Any basic block without successors. This includes any basic block
330 /// ending with an OpReturn, OpReturnValue or similar instructions.
331 /// - A single node from each otherwise unreachable cycle in the CFG, if
332 /// such cycles exist.
333 /// The pseudo exit node does not appear in the predecessor or successor
334 /// list of any ordinary block.
335 /// It has no successors.
336 BasicBlock pseudo_exit_block_;
337
338 // Maps a block to its successors in the augmented CFG, if that set is
339 // different from its successors in the ordinary CFG.
340 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>>
341 augmented_successors_map_;
342 // Maps a block to its predecessors in the augmented CFG, if that set is
343 // different from its predecessors in the ordinary CFG.
344 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>>
345 augmented_predecessors_map_;
346
347 // Maps a structured loop header to its CFG successors and also its
348 // continue target if that continue target is not the loop header
349 // itself. This might have duplicates.
350 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>>
351 loop_header_successors_plus_continue_target_map_;
352
353 /// The constructs that are available in this function
354 std::list<Construct> cfg_constructs_;
355
356 /// The variable IDs of the functions
357 std::vector<uint32_t> variable_ids_;
358
359 /// The function parameter ids of the functions
360 std::vector<uint32_t> parameter_ids_;
361
362 /// Maps a construct's entry block to the construct(s).
363 /// Since a basic block may be the entry block of different types of
364 /// constructs, the type of the construct should also be specified in order to
365 /// get the unique construct.
366 std::unordered_map<std::pair<const BasicBlock*, ConstructType>, Construct*,
367 bb_constr_type_pair_hash>
368 entry_block_to_construct_;
369
370 /// This map provides the header block for a given merge block.
371 std::unordered_map<BasicBlock*, BasicBlock*> merge_block_header_;
372
373 /// This map provides the header blocks for a given continue target.
374 std::unordered_map<BasicBlock*, std::vector<BasicBlock*>>
375 continue_target_headers_;
376
377 /// Stores the control flow nesting depth of a given basic block
378 std::unordered_map<BasicBlock*, int> block_depth_;
379
380 /// Stores execution model limitations imposed by instructions used within the
381 /// function. The functor stored in the list return true if execution model
382 /// is compatible, false otherwise. If the functor returns false, it can also
383 /// optionally fill the string parameter with the reason for incompatibility.
384 std::list<std::function<bool(SpvExecutionModel, std::string*)>>
385 execution_model_limitations_;
386
387 /// Stores limitations imposed by instructions used within the function.
388 /// Similar to execution_model_limitations_;
389 std::list<std::function<bool(const ValidationState_t& _, const Function*,
390 std::string*)>>
391 limitations_;
392
393 /// Stores ids of all functions called from this function.
394 std::set<uint32_t> function_call_targets_;
395 };
396
397 } // namespace val
398 } // namespace spvtools
399
400 #endif // SOURCE_VAL_FUNCTION_H_