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