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_BASICBLOCK_H_ 28 #define LIBSPIRV_VAL_BASICBLOCK_H_ 29 30 #include "spirv/1.1/spirv.h" 31 32 #include <cstdint> 33 34 #include <bitset> 35 #include <functional> 36 #include <vector> 37 38 namespace libspirv { 39 40 enum BlockType : uint32_t { 41 kBlockTypeUndefined, 42 kBlockTypeHeader, 43 kBlockTypeLoop, 44 kBlockTypeMerge, 45 kBlockTypeBreak, 46 kBlockTypeContinue, 47 kBlockTypeReturn, 48 kBlockTypeCOUNT ///< Total number of block types. (must be the last element) 49 }; 50 51 // This class represents a basic block in a SPIR-V module 52 class BasicBlock { 53 public: 54 /// Constructor for a BasicBlock 55 /// 56 /// @param[in] id The ID of the basic block 57 explicit BasicBlock(uint32_t id); 58 59 /// Returns the id of the BasicBlock 60 uint32_t id() const { return id_; } 61 62 /// Returns the predecessors of the BasicBlock 63 const std::vector<BasicBlock*>* predecessors() const { 64 return &predecessors_; 65 } 66 67 /// Returns the predecessors of the BasicBlock 68 std::vector<BasicBlock*>* predecessors() { return &predecessors_; } 69 70 /// Returns the successors of the BasicBlock 71 const std::vector<BasicBlock*>* successors() const { return &successors_; } 72 73 /// Returns the successors of the BasicBlock 74 std::vector<BasicBlock*>* successors() { return &successors_; } 75 76 /// Returns true if the block is reachable in the CFG 77 bool reachable() const { return reachable_; } 78 79 /// Returns true if BasicBlock is of the given type 80 bool is_type(BlockType type) const { 81 if (type == kBlockTypeUndefined) return type_.none(); 82 return type_.test(type); 83 } 84 85 /// Sets the reachability of the basic block in the CFG 86 void set_reachable(bool reachability) { reachable_ = reachability; } 87 88 /// Sets the type of the BasicBlock 89 void set_type(BlockType type) { 90 if (type == kBlockTypeUndefined) 91 type_.reset(); 92 else 93 type_.set(type); 94 } 95 96 /// Sets the immedate dominator of this basic block 97 /// 98 /// @param[in] dom_block The dominator block 99 void SetImmediateDominator(BasicBlock* dom_block); 100 101 /// Sets the immedate post dominator of this basic block 102 /// 103 /// @param[in] pdom_block The post dominator block 104 void SetImmediatePostDominator(BasicBlock* pdom_block); 105 106 /// Returns the immedate dominator of this basic block 107 BasicBlock* immediate_dominator(); 108 109 /// Returns the immedate dominator of this basic block 110 const BasicBlock* immediate_dominator() const; 111 112 /// Returns the immedate post dominator of this basic block 113 BasicBlock* immediate_post_dominator(); 114 115 /// Returns the immedate post dominator of this basic block 116 const BasicBlock* immediate_post_dominator() const; 117 118 /// Ends the block without a successor 119 void RegisterBranchInstruction(SpvOp branch_instruction); 120 121 /// Adds @p next BasicBlocks as successors of this BasicBlock 122 void RegisterSuccessors(const std::vector<BasicBlock*>& next = {}); 123 124 /// Set the successors to this block, without updating other internal state, 125 /// and without updating the other blocks. 126 void SetSuccessorsUnsafe(std::vector<BasicBlock*>&& others); 127 128 /// Set the predecessors to this block, without updating other internal state, 129 /// and without updating the other blocks. 130 void SetPredecessorsUnsafe(std::vector<BasicBlock*>&& others); 131 132 /// Returns true if the id of the BasicBlock matches 133 bool operator==(const BasicBlock& other) const { return other.id_ == id_; } 134 135 /// Returns true if the id of the BasicBlock matches 136 bool operator==(const uint32_t& other_id) const { return other_id == id_; } 137 138 /// @brief A BasicBlock dominator iterator class 139 /// 140 /// This iterator will iterate over the (post)dominators of the block 141 class DominatorIterator 142 : public std::iterator<std::forward_iterator_tag, BasicBlock*> { 143 public: 144 /// @brief Constructs the end of dominator iterator 145 /// 146 /// This will create an iterator which will represent the element 147 /// before the root node of the dominator tree 148 DominatorIterator(); 149 150 /// @brief Constructs an iterator for the given block which points to 151 /// @p block 152 /// 153 /// @param block The block which is referenced by the iterator 154 /// @param dominator_func This function will be called to get the immediate 155 /// (post)dominator of the current block 156 DominatorIterator( 157 const BasicBlock* block, 158 std::function<const BasicBlock*(const BasicBlock*)> dominator_func); 159 160 /// @brief Advances the iterator 161 DominatorIterator& operator++(); 162 163 /// @brief Returns the current element 164 const BasicBlock*& operator*(); 165 166 friend bool operator==(const DominatorIterator& lhs, 167 const DominatorIterator& rhs); 168 169 private: 170 const BasicBlock* current_; 171 std::function<const BasicBlock*(const BasicBlock*)> dom_func_; 172 }; 173 174 /// Returns a dominator iterator which points to the current block 175 const DominatorIterator dom_begin() const; 176 177 /// Returns a dominator iterator which points to the current block 178 DominatorIterator dom_begin(); 179 180 /// Returns a dominator iterator which points to one element past the first 181 /// block 182 const DominatorIterator dom_end() const; 183 184 /// Returns a dominator iterator which points to one element past the first 185 /// block 186 DominatorIterator dom_end(); 187 188 /// Returns a post dominator iterator which points to the current block 189 const DominatorIterator pdom_begin() const; 190 /// Returns a post dominator iterator which points to the current block 191 DominatorIterator pdom_begin(); 192 193 /// Returns a post dominator iterator which points to one element past the 194 /// last block 195 const DominatorIterator pdom_end() const; 196 197 /// Returns a post dominator iterator which points to one element past the 198 /// last block 199 DominatorIterator pdom_end(); 200 201 private: 202 /// Id of the BasicBlock 203 const uint32_t id_; 204 205 /// Pointer to the immediate dominator of the BasicBlock 206 BasicBlock* immediate_dominator_; 207 208 /// Pointer to the immediate dominator of the BasicBlock 209 BasicBlock* immediate_post_dominator_; 210 211 /// The set of predecessors of the BasicBlock 212 std::vector<BasicBlock*> predecessors_; 213 214 /// The set of successors of the BasicBlock 215 std::vector<BasicBlock*> successors_; 216 217 /// The type of the block 218 std::bitset<kBlockTypeCOUNT - 1> type_; 219 220 /// True if the block is reachable in the CFG 221 bool reachable_; 222 }; 223 224 /// @brief Returns true if the iterators point to the same element or if both 225 /// iterators point to the @p dom_end block 226 bool operator==(const BasicBlock::DominatorIterator& lhs, 227 const BasicBlock::DominatorIterator& rhs); 228 229 /// @brief Returns true if the iterators point to different elements and they 230 /// do not both point to the @p dom_end block 231 bool operator!=(const BasicBlock::DominatorIterator& lhs, 232 const BasicBlock::DominatorIterator& rhs); 233 234 } /// namespace libspirv 235 236 #endif /// LIBSPIRV_VAL_BASICBLOCK_H_ 237
