Debian Codegraph @

third_party/spirv-tools/source/val/basic_block.h

raw
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
51 uint32_t id() const { return id_; }
52
53 /// Returns the predecessors of the BasicBlock
54 const std::vector<BasicBlock*>* predecessors() const {
55 return &predecessors_;
56 }
57
58 /// Returns the predecessors of the BasicBlock
59 std::vector<BasicBlock*>* predecessors() { return &predecessors_; }
60
61 /// Returns the successors of the BasicBlock
62 const std::vector<BasicBlock*>* successors() const { return &successors_; }
63
64 /// Returns the successors of the BasicBlock
65 std::vector<BasicBlock*>* successors() { return &successors_; }
66
67 /// Returns true if the block is reachable in the CFG
68 bool reachable() const { return reachable_; }
69
70 /// Returns true if BasicBlock is of the given type
71 bool is_type(BlockType type) const {
72 if (type == kBlockTypeUndefined) return type_.none();
73 return type_.test(type);
74 }
75
76 /// Sets the reachability of the basic block in the CFG
77 void set_reachable(bool reachability) { reachable_ = reachability; }
78
79 /// Sets the type of the BasicBlock
80 void set_type(BlockType type) {
81 if (type == kBlockTypeUndefined)
82 type_.reset();
83 else
84 type_.set(type);
85 }
86
87 /// Sets the immedate dominator of this basic block
88 ///
89 /// @param[in] dom_block The dominator block
90 void SetImmediateDominator(BasicBlock* dom_block);
91
92 /// Sets the immedate post dominator of this basic block
93 ///
94 /// @param[in] pdom_block The post dominator block
95 void SetImmediatePostDominator(BasicBlock* pdom_block);
96
97 /// Returns the immedate dominator of this basic block
98 BasicBlock* immediate_dominator();
99
100 /// Returns the immedate dominator of this basic block
101 const BasicBlock* immediate_dominator() const;
102
103 /// Returns the immedate post dominator of this basic block
104 BasicBlock* immediate_post_dominator();
105
106 /// Returns the immedate post dominator of this basic block
107 const BasicBlock* immediate_post_dominator() const;
108
109 /// Returns the label instruction for the block, or nullptr if not set.
110 const Instruction* label() const { return label_; }
111
112 //// Registers the label instruction for the block.
113 void set_label(const Instruction* t) { label_ = t; }
114
115 /// Registers the terminator instruction for the block.
116 void set_terminator(const Instruction* t) { terminator_ = t; }
117
118 /// Returns the terminator instruction for the block.
119 const Instruction* terminator() const { return terminator_; }
120
121 /// Adds @p next BasicBlocks as successors of this BasicBlock
122 void RegisterSuccessors(
123 const std::vector<BasicBlock*>& next = std::vector<BasicBlock*>());
124
125 /// Returns true if the id of the BasicBlock matches
126 bool operator==(const BasicBlock& other) const { return other.id_ == id_; }
127
128 /// Returns true if the id of the BasicBlock matches
129 bool operator==(const uint32_t& other_id) const { return other_id == id_; }
130
131 /// Returns true if this block dominates the other block.
132 /// Assumes dominators have been computed.
133 bool dominates(const BasicBlock& other) const;
134
135 /// Returns true if this block postdominates the other block.
136 /// Assumes dominators have been computed.
137 bool postdominates(const BasicBlock& other) const;
138
139 /// @brief A BasicBlock dominator iterator class
140 ///
141 /// This iterator will iterate over the (post)dominators of the block
142 class DominatorIterator
143 : public std::iterator<std::forward_iterator_tag, BasicBlock*> {
144 public:
145 /// @brief Constructs the end of dominator iterator
146 ///
147 /// This will create an iterator which will represent the element
148 /// before the root node of the dominator tree
149 DominatorIterator();
150
151 /// @brief Constructs an iterator for the given block which points to
152 /// @p block
153 ///
154 /// @param block The block which is referenced by the iterator
155 /// @param dominator_func This function will be called to get the immediate
156 /// (post)dominator of the current block
157 DominatorIterator(
158 const BasicBlock* block,
159 std::function<const BasicBlock*(const BasicBlock*)> dominator_func);
160
161 /// @brief Advances the iterator
162 DominatorIterator& operator++();
163
164 /// @brief Returns the current element
165 const BasicBlock*& operator*();
166
167 friend bool operator==(const DominatorIterator& lhs,
168 const DominatorIterator& rhs);
169
170 private:
171 const BasicBlock* current_;
172 std::function<const BasicBlock*(const BasicBlock*)> dom_func_;
173 };
174
175 /// Returns a dominator iterator which points to the current block
176 const DominatorIterator dom_begin() const;
177
178 /// Returns a dominator iterator which points to the current block
179 DominatorIterator dom_begin();
180
181 /// Returns a dominator iterator which points to one element past the first
182 /// block
183 const DominatorIterator dom_end() const;
184
185 /// Returns a dominator iterator which points to one element past the first
186 /// block
187 DominatorIterator dom_end();
188
189 /// Returns a post dominator iterator which points to the current block
190 const DominatorIterator pdom_begin() const;
191 /// Returns a post dominator iterator which points to the current block
192 DominatorIterator pdom_begin();
193
194 /// Returns a post dominator iterator which points to one element past the
195 /// last block
196 const DominatorIterator pdom_end() const;
197
198 /// Returns a post dominator iterator which points to one element past the
199 /// last block
200 DominatorIterator pdom_end();
201
202 private:
203 /// Id of the BasicBlock
204 const uint32_t id_;
205
206 /// Pointer to the immediate dominator of the BasicBlock
207 BasicBlock* immediate_dominator_;
208
209 /// Pointer to the immediate dominator of the BasicBlock
210 BasicBlock* immediate_post_dominator_;
211
212 /// The set of predecessors of the BasicBlock
213 std::vector<BasicBlock*> predecessors_;
214
215 /// The set of successors of the BasicBlock
216 std::vector<BasicBlock*> successors_;
217
218 /// The type of the block
219 std::bitset<kBlockTypeCOUNT> type_;
220
221 /// True if the block is reachable in the CFG
222 bool reachable_;
223
224 /// label of this block, if any.
225 const Instruction* label_;
226
227 /// Terminator of this block.
228 const Instruction* terminator_;
229 };
230
231 /// @brief Returns true if the iterators point to the same element or if both
232 /// iterators point to the @p dom_end block
233 bool operator==(const BasicBlock::DominatorIterator& lhs,
234 const BasicBlock::DominatorIterator& rhs);
235
236 /// @brief Returns true if the iterators point to different elements and they
237 /// do not both point to the @p dom_end block
238 bool operator!=(const BasicBlock::DominatorIterator& lhs,
239 const BasicBlock::DominatorIterator& rhs);
240
241 } // namespace val
242 } // namespace spvtools
243
244 #endif // SOURCE_VAL_BASIC_BLOCK_H_