1// Copyright (c) 2015-2016 The Khronos Group Inc.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a
4// copy of this software and/or associated documentation files (the
5// "Materials"), to deal in the Materials without restriction, including
6// without limitation the rights to use, copy, modify, merge, publish,
7// distribute, sublicense, and/or sell copies of the Materials, and to
8// permit persons to whom the Materials are furnished to do so, subject to
9// the following conditions:
10//
11// The above copyright notice and this permission notice shall be included
12// in all copies or substantial portions of the Materials.
13//
14// MODIFICATIONS TO THIS FILE MAY MEAN IT NO LONGER ACCURATELY REFLECTS
15// KHRONOS STANDARDS. THE UNMODIFIED, NORMATIVE VERSIONS OF KHRONOS
16// SPECIFICATIONS AND HEADER INFORMATION ARE LOCATED AT
17//    https://www.khronos.org/registry/
18//
19// THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
23// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25// MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS.
26
27#ifndef LIBSPIRV_VAL_FUNCTION_H_
28#define LIBSPIRV_VAL_FUNCTION_H_
29
30#include <list>
31#include <unordered_map>
32#include <unordered_set>
33#include <vector>
34
35#include "spirv-tools/libspirv.h"
36#include "spirv/1.1/spirv.h"
37#include "val/BasicBlock.h"
38
39namespace libspirv {
40
41enum class FunctionDecl {
42  kFunctionDeclUnknown,      /// < Unknown function declaration
43  kFunctionDeclDeclaration,  /// < Function declaration
44  kFunctionDeclDefinition    /// < Function definition
45};
46
47class Construct;
48class ValidationState_t;
49
50/// This class manages all function declaration and definitions in a module. It
51/// handles the state and id information while parsing a function in the SPIR-V
52/// binary.
53class Function {
54 public:
55  Function(uint32_t id, uint32_t result_type_id,
56           SpvFunctionControlMask function_control, uint32_t function_type_id,
57           ValidationState_t& module);
58
59  /// Registers a function parameter in the current function
60  /// @return Returns SPV_SUCCESS if the call was successful
61  spv_result_t RegisterFunctionParameter(uint32_t id, uint32_t type_id);
62
63  /// Sets the declaration type of the current function
64  /// @return Returns SPV_SUCCESS if the call was successful
65  spv_result_t RegisterSetFunctionDeclType(FunctionDecl type);
66
67  /// Registers a block in the current function. Subsequent block instructions
68  /// will target this block
69  /// @param id The ID of the label of the block
70  /// @return Returns SPV_SUCCESS if the call was successful
71  spv_result_t RegisterBlock(uint32_t id, bool is_definition = true);
72
73  /// Registers a variable in the current block
74  ///
75  /// @param[in] type_id The type ID of the varaible
76  /// @param[in] id      The ID of the varaible
77  /// @param[in] storage The storage of the variable
78  /// @param[in] init_id The initializer ID of the variable
79  ///
80  /// @return Returns SPV_SUCCESS if the call was successful
81  spv_result_t RegisterBlockVariable(uint32_t type_id, uint32_t id,
82                                     SpvStorageClass storage, uint32_t init_id);
83
84  /// Registers a loop merge construct in the function
85  ///
86  /// @param[in] merge_id The merge block ID of the loop
87  /// @param[in] continue_id The continue block ID of the loop
88  ///
89  /// @return Returns SPV_SUCCESS if the call was successful
90  spv_result_t RegisterLoopMerge(uint32_t merge_id, uint32_t continue_id);
91
92  /// Registers a selection merge construct in the function
93  /// @return Returns SPV_SUCCESS if the call was successful
94  spv_result_t RegisterSelectionMerge(uint32_t merge_id);
95
96  /// Registers the end of the block
97  ///
98  /// @param[in] successors_list A list of ids to the block's successors
99  /// @param[in] branch_instruction the branch instruction that ended the block
100  void RegisterBlockEnd(std::vector<uint32_t> successors_list,
101                        SpvOp branch_instruction);
102
103  /// Registers the end of the function.  This is idempotent.
104  void RegisterFunctionEnd();
105
106  /// Returns true if the \p id block is the first block of this function
107  bool IsFirstBlock(uint32_t id) const;
108
109  /// Returns true if the \p merge_block_id is a BlockType of \p type
110  bool IsBlockType(uint32_t merge_block_id, BlockType type) const;
111
112  /// Returns a pair consisting of the BasicBlock with \p id and a bool
113  /// which is true if the block has been defined, and false if it is
114  /// declared but not defined. This function will return nullptr if the
115  /// \p id was not declared and not defined at the current point in the binary
116  std::pair<const BasicBlock*, bool> GetBlock(uint32_t id) const;
117  std::pair<BasicBlock*, bool> GetBlock(uint32_t id);
118
119  /// Returns the first block of the current function
120  const BasicBlock* first_block() const;
121
122  /// Returns the first block of the current function
123  BasicBlock* first_block();
124
125  /// Returns a vector of all the blocks in the function
126  const std::vector<BasicBlock*>& ordered_blocks() const;
127
128  /// Returns a vector of all the blocks in the function
129  std::vector<BasicBlock*>& ordered_blocks();
130
131  /// Returns a list of all the cfg constructs in the function
132  const std::list<Construct>& constructs() const;
133
134  /// Returns a list of all the cfg constructs in the function
135  std::list<Construct>& constructs();
136
137  /// Returns the number of blocks in the current function being parsed
138  size_t block_count() const;
139
140  /// Returns the id of the funciton
141  uint32_t id() const { return id_; }
142
143  /// Returns the number of blocks in the current function being parsed
144  size_t undefined_block_count() const;
145  const std::unordered_set<uint32_t>& undefined_blocks() const {
146    return undefined_blocks_;
147  }
148
149  /// Returns the block that is currently being parsed in the binary
150  BasicBlock* current_block();
151
152  /// Returns the block that is currently being parsed in the binary
153  const BasicBlock* current_block() const;
154
155  /// Returns the pseudo exit block
156  BasicBlock* pseudo_entry_block();
157
158  /// Returns the pseudo exit block
159  const BasicBlock* pseudo_entry_block() const;
160
161  /// Returns the pseudo exit block
162  BasicBlock* pseudo_exit_block();
163
164  /// Returns the pseudo exit block
165  const BasicBlock* pseudo_exit_block() const;
166
167  /// Returns a vector with just the pseudo entry block.
168  /// This serves as the predecessors of each source node in the CFG when
169  /// computing dominators.
170  const std::vector<BasicBlock*>* pseudo_entry_blocks() const {
171    return &pseudo_entry_blocks_;
172  }
173
174  /// Returns a vector with just the pseudo exit block.
175  /// This serves as the successors of each sink node in the CFG when computing
176  /// dominators.
177  const std::vector<BasicBlock*>* pseudo_exit_blocks() const {
178    return &pseudo_exit_blocks_;
179  }
180
181  /// Prints a GraphViz digraph of the CFG of the current funciton
182  void PrintDotGraph() const;
183
184  /// Prints a directed graph of the CFG of the current funciton
185  void PrintBlocks() const;
186
187 private:
188  /// Parent module
189  ValidationState_t& module_;
190
191  /// The result id of the OpLabel that defined this block
192  uint32_t id_;
193
194  /// The type of the function
195  uint32_t function_type_id_;
196
197  /// The type of the return value
198  uint32_t result_type_id_;
199
200  /// The control fo the funciton
201  SpvFunctionControlMask function_control_;
202
203  /// The type of declaration of each function
204  FunctionDecl declaration_type_;
205
206  // Have we finished parsing this function?
207  bool end_has_been_registered_;
208
209  /// The blocks in the function mapped by block ID
210  std::unordered_map<uint32_t, BasicBlock> blocks_;
211
212  /// A list of blocks in the order they appeared in the binary
213  std::vector<BasicBlock*> ordered_blocks_;
214
215  /// Blocks which are forward referenced by blocks but not defined
216  std::unordered_set<uint32_t> undefined_blocks_;
217
218  /// The block that is currently being parsed
219  BasicBlock* current_block_;
220
221  /// A pseudo entry block that, for the purposes of dominance analysis,
222  /// is considered the predecessor to any ordinary block without predecessors.
223  /// After the function end has been registered, its successor list consists
224  /// of all ordinary blocks without predecessors.  It has no predecessors.
225  /// It does not appear in the predecessor or successor list of any
226  /// ordinary block.
227  /// It has Id 0.
228  BasicBlock pseudo_entry_block_;
229
230  /// A pseudo exit block that, for the purposes of dominance analysis,
231  /// is considered the successor to any ordinary block without successors.
232  /// After the function end has been registered, its predecessor list consists
233  /// of all ordinary blocks without successors.  It has no successors.
234  /// It does not appear in the predecessor or successor list of any
235  /// ordinary block.
236  BasicBlock pseudo_exit_block_;
237
238  // A vector containing pseudo_entry_block_.
239  const std::vector<BasicBlock*> pseudo_entry_blocks_;
240
241  // A vector containing pseudo_exit_block_.
242  const std::vector<BasicBlock*> pseudo_exit_blocks_;
243
244  /// The constructs that are available in this function
245  std::list<Construct> cfg_constructs_;
246
247  /// The variable IDs of the functions
248  std::vector<uint32_t> variable_ids_;
249
250  /// The function parameter ids of the functions
251  std::vector<uint32_t> parameter_ids_;
252};
253
254}  /// namespace libspirv
255
256#endif  /// LIBSPIRV_VAL_FUNCTION_H_
257