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
24namespace spvtools {
25namespace val {
26class ValidationState_t;
27
28/// Functor for ordering BasicBlocks. BasicBlock pointers must not be null.
29struct less_than_id {
30 bool operator()(const BasicBlock* lhs, const BasicBlock* rhs) const {
31 return lhs->id() < rhs->id();
32 }
33};
34
35enum 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
54class Function;
55
56/// @brief This class tracks the CFG constructs as defined in the SPIR-V spec
57class 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_
171