| 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 { |
| 30 |
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 |
| 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_ |