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