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_CONSTRUCT_H_ 16 #define SOURCE_VAL_CONSTRUCT_H_ 17 18 #include <cstdint> 19 #include <set> 20 #include <vector> 21 22 #include "source/val/basic_block.h" 23 24 namespace spvtools { 25 namespace val { 26 27 /// Functor for ordering BasicBlocks. BasicBlock pointers must not be null. 28 struct less_than_id { operatorless_than_id29 bool operator()(const BasicBlock* lhs, const BasicBlock* rhs) const { 30 return lhs->id() < rhs->id(); 31 } 32 }; 33 34 enum class ConstructType : int { 35 kNone = 0, 36 /// The set of blocks dominated by a selection header, minus the set of blocks 37 /// dominated by the header's merge block 38 kSelection, 39 /// The set of blocks dominated by an OpLoopMerge's Continue Target and post 40 /// dominated by the corresponding back 41 kContinue, 42 /// The set of blocks dominated by a loop header, minus the set of blocks 43 /// dominated by the loop's merge block, minus the loop's corresponding 44 /// continue construct 45 kLoop, 46 /// The set of blocks dominated by an OpSwitch's Target or Default, minus the 47 /// set of blocks dominated by the OpSwitch's merge block (this construct is 48 /// only defined for those OpSwitch Target or Default that are not equal to 49 /// the OpSwitch's corresponding merge block) 50 kCase 51 }; 52 53 class Function; 54 55 /// @brief This class tracks the CFG constructs as defined in the SPIR-V spec 56 class Construct { 57 public: 58 Construct(ConstructType type, BasicBlock* dominator, 59 BasicBlock* exit = nullptr, 60 std::vector<Construct*> constructs = std::vector<Construct*>()); 61 62 /// Returns the type of the construct 63 ConstructType type() const; 64 65 const std::vector<Construct*>& corresponding_constructs() const; 66 std::vector<Construct*>& corresponding_constructs(); 67 void set_corresponding_constructs(std::vector<Construct*> constructs); 68 69 /// Returns the dominator block of the construct. 70 /// 71 /// This is usually the header block or the first block of the construct. 72 const BasicBlock* entry_block() const; 73 74 /// Returns the dominator block of the construct. 75 /// 76 /// This is usually the header block or the first block of the construct. 77 BasicBlock* entry_block(); 78 79 /// Returns the exit block of the construct. 80 /// 81 /// For a continue construct it is the backedge block of the corresponding 82 /// loop construct. For the case construct it is the block that branches to 83 /// the OpSwitch merge block or other case blocks. Otherwise it is the merge 84 /// block of the corresponding header block 85 const BasicBlock* exit_block() const; 86 87 /// Returns the exit block of the construct. 88 /// 89 /// For a continue construct it is the backedge block of the corresponding 90 /// loop construct. For the case construct it is the block that branches to 91 /// the OpSwitch merge block or other case blocks. Otherwise it is the merge 92 /// block of the corresponding header block 93 BasicBlock* exit_block(); 94 95 /// Sets the exit block for this construct. This is useful for continue 96 /// constructs which do not know the back-edge block during construction 97 void set_exit(BasicBlock* exit_block); 98 99 // Returns whether the exit block of this construct is the merge block 100 // for an OpLoopMerge or OpSelectionMerge ExitBlockIsMergeBlock()101 bool ExitBlockIsMergeBlock() const { 102 return type_ == ConstructType::kLoop || type_ == ConstructType::kSelection; 103 } 104 105 using ConstructBlockSet = std::set<BasicBlock*, less_than_id>; 106 107 // Returns the basic blocks in this construct. This function should not 108 // be called before the exit block is set and dominators have been 109 // calculated. 110 ConstructBlockSet blocks(Function* function) const; 111 112 private: 113 /// The type of the construct 114 ConstructType type_; 115 116 /// These are the constructs that are related to this construct. These 117 /// constructs can be the continue construct, for the corresponding loop 118 /// construct, the case construct that are part of the same OpSwitch 119 /// instruction 120 /// 121 /// Here is a table that describes what constructs are included in 122 /// @p corresponding_constructs_ 123 /// | this construct | corresponding construct | 124 /// |----------------|----------------------------------| 125 /// | loop | continue | 126 /// | continue | loop | 127 /// | case | other cases in the same OpSwitch | 128 /// 129 /// kContinue and kLoop constructs will always have corresponding 130 /// constructs even if they are represented by the same block 131 std::vector<Construct*> corresponding_constructs_; 132 133 /// @brief Dominator block for the construct 134 /// 135 /// The dominator block for the construct. Depending on the construct this may 136 /// be a selection header, a continue target of a loop, a loop header or a 137 /// Target or Default block of a switch 138 BasicBlock* entry_block_; 139 140 /// @brief Exiting block for the construct 141 /// 142 /// The exit block for the construct. This can be a merge block for the loop 143 /// and selection constructs, a back-edge block for a continue construct, or 144 /// the branching block for the case construct 145 BasicBlock* exit_block_; 146 }; 147 148 } // namespace val 149 } // namespace spvtools 150 151 #endif // SOURCE_VAL_CONSTRUCT_H_ 152