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