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 the structural successors of the BasicBlock structural_predecessors()68 std::vector<BasicBlock*>* structural_predecessors() { 69 return &structural_predecessors_; 70 } 71 72 /// Returns the structural predecessors of the BasicBlock structural_predecessors()73 const std::vector<BasicBlock*>* structural_predecessors() const { 74 return &structural_predecessors_; 75 } 76 77 /// Returns the structural successors of the BasicBlock structural_successors()78 std::vector<BasicBlock*>* structural_successors() { 79 return &structural_successors_; 80 } 81 82 /// Returns the structural predecessors of the BasicBlock structural_successors()83 const std::vector<BasicBlock*>* structural_successors() const { 84 return &structural_successors_; 85 } 86 87 /// Returns true if the block is reachable in the CFG. reachable()88 bool reachable() const { return reachable_; } 89 90 /// Returns true if the block is structurally reachable in the CFG. structurally_reachable()91 bool structurally_reachable() const { return structurally_reachable_; } 92 93 /// Returns true if BasicBlock is of the given type is_type(BlockType type)94 bool is_type(BlockType type) const { 95 if (type == kBlockTypeUndefined) return type_.none(); 96 return type_.test(type); 97 } 98 99 /// Sets the reachability of the basic block in the CFG set_reachable(bool reachability)100 void set_reachable(bool reachability) { reachable_ = reachability; } 101 102 /// Sets the structural reachability of the basic block in the CFG set_structurally_reachable(bool reachability)103 void set_structurally_reachable(bool reachability) { 104 structurally_reachable_ = reachability; 105 } 106 107 /// Sets the type of the BasicBlock set_type(BlockType type)108 void set_type(BlockType type) { 109 if (type == kBlockTypeUndefined) 110 type_.reset(); 111 else 112 type_.set(type); 113 } 114 115 /// Sets the immediate dominator of this basic block 116 /// 117 /// @param[in] dom_block The dominator block 118 void SetImmediateDominator(BasicBlock* dom_block); 119 120 /// Sets the immediate dominator of this basic block 121 /// 122 /// @param[in] dom_block The dominator block 123 void SetImmediateStructuralDominator(BasicBlock* dom_block); 124 125 /// Sets the immediate post dominator of this basic block 126 /// 127 /// @param[in] pdom_block The post dominator block 128 void SetImmediateStructuralPostDominator(BasicBlock* pdom_block); 129 130 /// Returns the immediate dominator of this basic block 131 BasicBlock* immediate_dominator(); 132 133 /// Returns the immediate dominator of this basic block 134 const BasicBlock* immediate_dominator() const; 135 136 /// Returns the immediate dominator of this basic block 137 BasicBlock* immediate_structural_dominator(); 138 139 /// Returns the immediate dominator of this basic block 140 const BasicBlock* immediate_structural_dominator() const; 141 142 /// Returns the immediate post dominator of this basic block 143 BasicBlock* immediate_structural_post_dominator(); 144 145 /// Returns the immediate post dominator of this basic block 146 const BasicBlock* immediate_structural_post_dominator() const; 147 148 /// Returns the label instruction for the block, or nullptr if not set. label()149 const Instruction* label() const { return label_; } 150 151 //// Registers the label instruction for the block. set_label(const Instruction * t)152 void set_label(const Instruction* t) { label_ = t; } 153 154 /// Registers the terminator instruction for the block. set_terminator(const Instruction * t)155 void set_terminator(const Instruction* t) { terminator_ = t; } 156 157 /// Returns the terminator instruction for the block. terminator()158 const Instruction* terminator() const { return terminator_; } 159 160 /// Adds @p next BasicBlocks as successors of this BasicBlock 161 void RegisterSuccessors( 162 const std::vector<BasicBlock*>& next = std::vector<BasicBlock*>()); 163 164 /// Returns true if the id of the BasicBlock matches 165 bool operator==(const BasicBlock& other) const { return other.id_ == id_; } 166 167 /// Returns true if the id of the BasicBlock matches 168 bool operator==(const uint32_t& other_id) const { return other_id == id_; } 169 170 /// Returns true if this block dominates the other block. 171 /// Assumes dominators have been computed. 172 bool dominates(const BasicBlock& other) const; 173 174 /// Returns true if this block structurally dominates the other block. 175 /// Assumes structural dominators have been computed. 176 bool structurally_dominates(const BasicBlock& other) const; 177 178 /// Returns true if this block structurally postdominates the other block. 179 /// Assumes structural dominators have been computed. 180 bool structurally_postdominates(const BasicBlock& other) const; 181 RegisterStructuralSuccessor(BasicBlock * block)182 void RegisterStructuralSuccessor(BasicBlock* block) { 183 block->structural_predecessors_.push_back(this); 184 structural_successors_.push_back(block); 185 } 186 187 /// @brief A BasicBlock dominator iterator class 188 /// 189 /// This iterator will iterate over the (post)dominators of the block 190 class DominatorIterator { 191 public: 192 using iterator_category = std::forward_iterator_tag; 193 using value_type = BasicBlock*; 194 using pointer = value_type*; 195 using reference = value_type&; 196 using difference_type = std::ptrdiff_t; 197 198 /// @brief Constructs the end of dominator iterator 199 /// 200 /// This will create an iterator which will represent the element 201 /// before the root node of the dominator tree 202 DominatorIterator(); 203 204 /// @brief Constructs an iterator for the given block which points to 205 /// @p block 206 /// 207 /// @param block The block which is referenced by the iterator 208 /// @param dominator_func This function will be called to get the immediate 209 /// (post)dominator of the current block 210 DominatorIterator( 211 const BasicBlock* block, 212 std::function<const BasicBlock*(const BasicBlock*)> dominator_func); 213 214 /// @brief Advances the iterator 215 DominatorIterator& operator++(); 216 217 /// @brief Returns the current element 218 const BasicBlock*& operator*(); 219 220 friend bool operator==(const DominatorIterator& lhs, 221 const DominatorIterator& rhs); 222 223 private: 224 const BasicBlock* current_; 225 std::function<const BasicBlock*(const BasicBlock*)> dom_func_; 226 }; 227 228 /// Returns a dominator iterator which points to the current block 229 const DominatorIterator dom_begin() const; 230 231 /// Returns a dominator iterator which points to the current block 232 DominatorIterator dom_begin(); 233 234 /// Returns a dominator iterator which points to one element past the first 235 /// block 236 const DominatorIterator dom_end() const; 237 238 /// Returns a dominator iterator which points to one element past the first 239 /// block 240 DominatorIterator dom_end(); 241 242 /// Returns a dominator iterator which points to the current block 243 const DominatorIterator structural_dom_begin() const; 244 245 /// Returns a dominator iterator which points to the current block 246 DominatorIterator structural_dom_begin(); 247 248 /// Returns a dominator iterator which points to one element past the first 249 /// block 250 const DominatorIterator structural_dom_end() const; 251 252 /// Returns a dominator iterator which points to one element past the first 253 /// block 254 DominatorIterator structural_dom_end(); 255 256 /// Returns a post dominator iterator which points to the current block 257 const DominatorIterator structural_pdom_begin() const; 258 /// Returns a post dominator iterator which points to the current block 259 DominatorIterator structural_pdom_begin(); 260 261 /// Returns a post dominator iterator which points to one element past the 262 /// last block 263 const DominatorIterator structural_pdom_end() const; 264 265 /// Returns a post dominator iterator which points to one element past the 266 /// last block 267 DominatorIterator structural_pdom_end(); 268 269 private: 270 /// Id of the BasicBlock 271 const uint32_t id_; 272 273 /// Pointer to the immediate dominator of the BasicBlock 274 BasicBlock* immediate_dominator_; 275 276 /// Pointer to the immediate structural dominator of the BasicBlock 277 BasicBlock* immediate_structural_dominator_; 278 279 /// Pointer to the immediate structural post dominator of the BasicBlock 280 BasicBlock* immediate_structural_post_dominator_; 281 282 /// The set of predecessors of the BasicBlock 283 std::vector<BasicBlock*> predecessors_; 284 285 /// The set of successors of the BasicBlock 286 std::vector<BasicBlock*> successors_; 287 288 /// The type of the block 289 std::bitset<kBlockTypeCOUNT> type_; 290 291 /// True if the block is reachable in the CFG 292 bool reachable_; 293 294 /// True if the block is structurally reachable in the CFG 295 bool structurally_reachable_; 296 297 /// label of this block, if any. 298 const Instruction* label_; 299 300 /// Terminator of this block. 301 const Instruction* terminator_; 302 303 std::vector<BasicBlock*> structural_predecessors_; 304 std::vector<BasicBlock*> structural_successors_; 305 }; 306 307 /// @brief Returns true if the iterators point to the same element or if both 308 /// iterators point to the @p dom_end block 309 bool operator==(const BasicBlock::DominatorIterator& lhs, 310 const BasicBlock::DominatorIterator& rhs); 311 312 /// @brief Returns true if the iterators point to different elements and they 313 /// do not both point to the @p dom_end block 314 bool operator!=(const BasicBlock::DominatorIterator& lhs, 315 const BasicBlock::DominatorIterator& rhs); 316 317 } // namespace val 318 } // namespace spvtools 319 320 #endif // SOURCE_VAL_BASIC_BLOCK_H_ 321