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