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 LIBSPIRV_VAL_FUNCTION_H_ 16 #define LIBSPIRV_VAL_FUNCTION_H_ 17 18 #include <functional> 19 #include <list> 20 #include <unordered_map> 21 #include <unordered_set> 22 #include <vector> 23 24 #include "spirv-tools/libspirv.h" 25 #include "spirv/1.2/spirv.h" 26 #include "val/basic_block.h" 27 #include "val/construct.h" 28 29 namespace libspirv { 30 31 struct bb_constr_type_pair_hash { 32 std::size_t operator()( 33 const std::pair<const BasicBlock*, ConstructType>& p) const { 34 auto h1 = std::hash<const BasicBlock*>{}(p.first); 35 auto h2 = std::hash<std::underlying_type<ConstructType>::type>{}( 36 static_cast<std::underlying_type<ConstructType>::type>(p.second)); 37 return (h1 ^ h2); 38 } 39 }; 40 41 enum class FunctionDecl { 42 kFunctionDeclUnknown, /// < Unknown function declaration 43 kFunctionDeclDeclaration, /// < Function declaration 44 kFunctionDeclDefinition /// < Function definition 45 }; 46 47 /// This class manages all function declaration and definitions in a module. It 48 /// handles the state and id information while parsing a function in the SPIR-V 49 /// binary. 50 class Function { 51 public: 52 Function(uint32_t id, uint32_t result_type_id, 53 SpvFunctionControlMask function_control, uint32_t function_type_id); 54 55 /// Registers a function parameter in the current function 56 /// @return Returns SPV_SUCCESS if the call was successful 57 spv_result_t RegisterFunctionParameter(uint32_t id, uint32_t type_id); 58 59 /// Sets the declaration type of the current function 60 /// @return Returns SPV_SUCCESS if the call was successful 61 spv_result_t RegisterSetFunctionDeclType(FunctionDecl type); 62 63 /// Registers a block in the current function. Subsequent block instructions 64 /// will target this block 65 /// @param id The ID of the label of the block 66 /// @return Returns SPV_SUCCESS if the call was successful 67 spv_result_t RegisterBlock(uint32_t id, bool is_definition = true); 68 69 /// Registers a variable in the current block 70 /// 71 /// @param[in] type_id The type ID of the varaible 72 /// @param[in] id The ID of the varaible 73 /// @param[in] storage The storage of the variable 74 /// @param[in] init_id The initializer ID of the variable 75 /// 76 /// @return Returns SPV_SUCCESS if the call was successful 77 spv_result_t RegisterBlockVariable(uint32_t type_id, uint32_t id, 78 SpvStorageClass storage, uint32_t init_id); 79 80 /// Registers a loop merge construct in the function 81 /// 82 /// @param[in] merge_id The merge block ID of the loop 83 /// @param[in] continue_id The continue block ID of the loop 84 /// 85 /// @return Returns SPV_SUCCESS if the call was successful 86 spv_result_t RegisterLoopMerge(uint32_t merge_id, uint32_t continue_id); 87 88 /// Registers a selection merge construct in the function 89 /// @return Returns SPV_SUCCESS if the call was successful 90 spv_result_t RegisterSelectionMerge(uint32_t merge_id); 91 92 /// Registers the end of the block 93 /// 94 /// @param[in] successors_list A list of ids to the block's successors 95 /// @param[in] branch_instruction the branch instruction that ended the block 96 void RegisterBlockEnd(std::vector<uint32_t> successors_list, 97 SpvOp branch_instruction); 98 99 /// Registers the end of the function. This is idempotent. 100 void RegisterFunctionEnd(); 101 102 /// Returns true if the \p id block is the first block of this function 103 bool IsFirstBlock(uint32_t id) const; 104 105 /// Returns true if the \p merge_block_id is a BlockType of \p type 106 bool IsBlockType(uint32_t merge_block_id, BlockType type) const; 107 108 /// Returns a pair consisting of the BasicBlock with \p id and a bool 109 /// which is true if the block has been defined, and false if it is 110 /// declared but not defined. This function will return nullptr if the 111 /// \p id was not declared and not defined at the current point in the binary 112 std::pair<const BasicBlock*, bool> GetBlock(uint32_t id) const; 113 std::pair<BasicBlock*, bool> GetBlock(uint32_t id); 114 115 /// Returns the first block of the current function 116 const BasicBlock* first_block() const; 117 118 /// Returns the first block of the current function 119 BasicBlock* first_block(); 120 121 /// Returns a vector of all the blocks in the function 122 const std::vector<BasicBlock*>& ordered_blocks() const; 123 124 /// Returns a vector of all the blocks in the function 125 std::vector<BasicBlock*>& ordered_blocks(); 126 127 /// Returns a list of all the cfg constructs in the function 128 const std::list<Construct>& constructs() const; 129 130 /// Returns a list of all the cfg constructs in the function 131 std::list<Construct>& constructs(); 132 133 /// Returns the number of blocks in the current function being parsed 134 size_t block_count() const; 135 136 /// Returns the id of the funciton 137 uint32_t id() const { return id_; } 138 139 /// Returns the number of blocks in the current function being parsed 140 size_t undefined_block_count() const; 141 const std::unordered_set<uint32_t>& undefined_blocks() const { 142 return undefined_blocks_; 143 } 144 145 /// Returns the block that is currently being parsed in the binary 146 BasicBlock* current_block(); 147 148 /// Returns the block that is currently being parsed in the binary 149 const BasicBlock* current_block() const; 150 151 // For dominance calculations, we want to analyze all the 152 // blocks in the function, even in degenerate control flow cases 153 // including unreachable blocks. We therefore make an "augmented CFG" 154 // which is the same as the ordinary CFG but adds: 155 // - A pseudo-entry node. 156 // - A pseudo-exit node. 157 // - A minimal set of edges so that a forward traversal from the 158 // pseudo-entry node will visit all nodes. 159 // - A minimal set of edges so that a backward traversal from the 160 // pseudo-exit node will visit all nodes. 161 // In particular, the pseudo-entry node is the unique source of the 162 // augmented CFG, and the psueo-exit node is the unique sink of the 163 // augmented CFG. 164 165 /// Returns the pseudo exit block 166 BasicBlock* pseudo_entry_block() { return &pseudo_entry_block_; } 167 168 /// Returns the pseudo exit block 169 const BasicBlock* pseudo_entry_block() const { return &pseudo_entry_block_; } 170 171 /// Returns the pseudo exit block 172 BasicBlock* pseudo_exit_block() { return &pseudo_exit_block_; } 173 174 /// Returns the pseudo exit block 175 const BasicBlock* pseudo_exit_block() const { return &pseudo_exit_block_; } 176 177 using GetBlocksFunction = 178 std::function<const std::vector<BasicBlock*>*(const BasicBlock*)>; 179 /// Returns the block successors function for the augmented CFG. 180 GetBlocksFunction AugmentedCFGSuccessorsFunction() const; 181 /// Like AugmentedCFGSuccessorsFunction, but also includes a forward edge from 182 /// a loop header block to its continue target, if they are different blocks. 183 GetBlocksFunction AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge() const; 184 /// Returns the block predecessors function for the augmented CFG. 185 GetBlocksFunction AugmentedCFGPredecessorsFunction() const; 186 187 /// Returns the control flow nesting depth of the given basic block. 188 /// This function only works when you have structured control flow. 189 /// This function should only be called after the control flow constructs have 190 /// been identified and dominators have been computed. 191 int GetBlockDepth(BasicBlock* bb); 192 193 /// Prints a GraphViz digraph of the CFG of the current funciton 194 void PrintDotGraph() const; 195 196 /// Prints a directed graph of the CFG of the current funciton 197 void PrintBlocks() const; 198 199 private: 200 // Computes the representation of the augmented CFG. 201 // Populates augmented_successors_map_ and augmented_predecessors_map_. 202 void ComputeAugmentedCFG(); 203 204 // Adds a copy of the given Construct, and tracks it by its entry block. 205 // Returns a reference to the stored construct. 206 Construct& AddConstruct(const Construct& new_construct); 207 208 // Returns a reference to the construct corresponding to the given entry 209 // block. 210 Construct& FindConstructForEntryBlock(const BasicBlock* entry_block, 211 ConstructType t); 212 213 /// The result id of the OpLabel that defined this block 214 uint32_t id_; 215 216 /// The type of the function 217 uint32_t function_type_id_; 218 219 /// The type of the return value 220 uint32_t result_type_id_; 221 222 /// The control fo the funciton 223 SpvFunctionControlMask function_control_; 224 225 /// The type of declaration of each function 226 FunctionDecl declaration_type_; 227 228 // Have we finished parsing this function? 229 bool end_has_been_registered_; 230 231 /// The blocks in the function mapped by block ID 232 std::unordered_map<uint32_t, BasicBlock> blocks_; 233 234 /// A list of blocks in the order they appeared in the binary 235 std::vector<BasicBlock*> ordered_blocks_; 236 237 /// Blocks which are forward referenced by blocks but not defined 238 std::unordered_set<uint32_t> undefined_blocks_; 239 240 /// The block that is currently being parsed 241 BasicBlock* current_block_; 242 243 /// A pseudo entry node used in dominance analysis. 244 /// After the function end has been registered, the successor list of the 245 /// pseudo entry node is the minimal set of nodes such that all nodes in the 246 /// CFG can be reached by following successor lists. That is, the successors 247 /// will be: 248 /// - Any basic block without predecessors. This includes the entry 249 /// block to the function. 250 /// - A single node from each otherwise unreachable cycle in the CFG, if 251 /// such cycles exist. 252 /// The pseudo entry node does not appear in the predecessor or successor 253 /// list of any ordinary block. 254 /// It has no predecessors. 255 /// It has Id 0. 256 BasicBlock pseudo_entry_block_; 257 258 /// A pseudo exit block used in dominance analysis. 259 /// After the function end has been registered, the predecessor list of the 260 /// pseudo exit node is the minimal set of nodes such that all nodes in the 261 /// CFG can be reached by following predecessor lists. That is, the 262 /// predecessors will be: 263 /// - Any basic block without successors. This includes any basic block 264 /// ending with an OpReturn, OpReturnValue or similar instructions. 265 /// - A single node from each otherwise unreachable cycle in the CFG, if 266 /// such cycles exist. 267 /// The pseudo exit node does not appear in the predecessor or successor 268 /// list of any ordinary block. 269 /// It has no successors. 270 BasicBlock pseudo_exit_block_; 271 272 // Maps a block to its successors in the augmented CFG, if that set is 273 // different from its successors in the ordinary CFG. 274 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>> 275 augmented_successors_map_; 276 // Maps a block to its predecessors in the augmented CFG, if that set is 277 // different from its predecessors in the ordinary CFG. 278 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>> 279 augmented_predecessors_map_; 280 281 // Maps a structured loop header to its CFG successors and also its 282 // continue target if that continue target is not the loop header 283 // itself. This might have duplicates. 284 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>> 285 loop_header_successors_plus_continue_target_map_; 286 287 /// The constructs that are available in this function 288 std::list<Construct> cfg_constructs_; 289 290 /// The variable IDs of the functions 291 std::vector<uint32_t> variable_ids_; 292 293 /// The function parameter ids of the functions 294 std::vector<uint32_t> parameter_ids_; 295 296 /// Maps a construct's entry block to the construct(s). 297 /// Since a basic block may be the entry block of different types of 298 /// constructs, the type of the construct should also be specified in order to 299 /// get the unique construct. 300 std::unordered_map<std::pair<const BasicBlock*, ConstructType>, Construct*, 301 libspirv::bb_constr_type_pair_hash> 302 entry_block_to_construct_; 303 304 /// This map provides the header block for a given merge block. 305 std::unordered_map<BasicBlock*, BasicBlock*> merge_block_header_; 306 307 /// Stores the control flow nesting depth of a given basic block 308 std::unordered_map<BasicBlock*, int> block_depth_; 309 }; 310 311 } /// namespace libspirv 312 313 #endif /// LIBSPIRV_VAL_FUNCTION_H_ 314
