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 { operatorbb_constr_type_pair_hash37 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 id()140 uint32_t id() const { return id_; } 141 142 /// Returns return type id of the function GetResultTypeId()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; undefined_blocks()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 pseudo_entry_block()172 BasicBlock* pseudo_entry_block() { return &pseudo_entry_block_; } 173 174 /// Returns the pseudo exit block pseudo_entry_block()175 const BasicBlock* pseudo_entry_block() const { return &pseudo_entry_block_; } 176 177 /// Returns the pseudo exit block pseudo_exit_block()178 BasicBlock* pseudo_exit_block() { return &pseudo_exit_block_; } 179 180 /// Returns the pseudo exit block 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. RegisterExecutionModelLimitation(std::function<bool (SpvExecutionModel,std::string *)> is_compatible)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. RegisterLimitation(std::function<bool (const ValidationState_t & _,const Function *,std::string *)> is_compatible)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. AddFunctionCallTarget(uint32_t call_target_id)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. function_call_targets()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. GetMergeHeader(BasicBlock * merge_block)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. GetContinueHeaders(BasicBlock * continue_target)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_ 401