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
26namespace spvtools {
27namespace val {
28
29enum 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
40class Instruction;
41
42// This class represents a basic block in a SPIR-V module
43class 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 /// Ends the block without a successor
110 void RegisterBranchInstruction(SpvOp branch_instruction);
111
112 /// Returns the label instruction for the block, or nullptr if not set.
113 const Instruction* label() const { return label_; }
114
115 //// Registers the label instruction for the block.
116 void set_label(const Instruction* t) { label_ = t; }
117
118 /// Registers the terminator instruction for the block.
119 void set_terminator(const Instruction* t) { terminator_ = t; }
120
121 /// Returns the terminator instruction for the block.
122 const Instruction* terminator() const { return terminator_; }
123
124 /// Adds @p next BasicBlocks as successors of this BasicBlock
125 void RegisterSuccessors(
126 const std::vector<BasicBlock*>& next = std::vector<BasicBlock*>());
127
128 /// Returns true if the id of the BasicBlock matches
129 bool operator==(const BasicBlock& other) const { return other.id_ == id_; }
130
131 /// Returns true if the id of the BasicBlock matches
132 bool operator==(const uint32_t& other_id) const { return other_id == id_; }
133
134 /// Returns true if this block dominates the other block.
135 /// Assumes dominators have been computed.
136 bool dominates(const BasicBlock& other) const;
137
138 /// Returns true if this block postdominates the other block.
139 /// Assumes dominators have been computed.
140 bool postdominates(const BasicBlock& other) const;
141
142 /// @brief A BasicBlock dominator iterator class
143 ///
144 /// This iterator will iterate over the (post)dominators of the block
145 class DominatorIterator
146 : public std::iterator<std::forward_iterator_tag, BasicBlock*> {
147 public:
148 /// @brief Constructs the end of dominator iterator
149 ///
150 /// This will create an iterator which will represent the element
151 /// before the root node of the dominator tree
152 DominatorIterator();
153
154 /// @brief Constructs an iterator for the given block which points to
155 /// @p block
156 ///
157 /// @param block The block which is referenced by the iterator
158 /// @param dominator_func This function will be called to get the immediate
159 /// (post)dominator of the current block
160 DominatorIterator(
161 const BasicBlock* block,
162 std::function<const BasicBlock*(const BasicBlock*)> dominator_func);
163
164 /// @brief Advances the iterator
165 DominatorIterator& operator++();
166
167 /// @brief Returns the current element
168 const BasicBlock*& operator*();
169
170 friend bool operator==(const DominatorIterator& lhs,
171 const DominatorIterator& rhs);
172
173 private:
174 const BasicBlock* current_;
175 std::function<const BasicBlock*(const BasicBlock*)> dom_func_;
176 };
177
178 /// Returns a dominator iterator which points to the current block
179 const DominatorIterator dom_begin() const;
180
181 /// Returns a dominator iterator which points to the current block
182 DominatorIterator dom_begin();
183
184 /// Returns a dominator iterator which points to one element past the first
185 /// block
186 const DominatorIterator dom_end() const;
187
188 /// Returns a dominator iterator which points to one element past the first
189 /// block
190 DominatorIterator dom_end();
191
192 /// Returns a post dominator iterator which points to the current block
193 const DominatorIterator pdom_begin() const;
194 /// Returns a post dominator iterator which points to the current block
195 DominatorIterator pdom_begin();
196
197 /// Returns a post dominator iterator which points to one element past the
198 /// last block
199 const DominatorIterator pdom_end() const;
200
201 /// Returns a post dominator iterator which points to one element past the
202 /// last block
203 DominatorIterator pdom_end();
204
205 private:
206 /// Id of the BasicBlock
207 const uint32_t id_;
208
209 /// Pointer to the immediate dominator of the BasicBlock
210 BasicBlock* immediate_dominator_;
211
212 /// Pointer to the immediate dominator of the BasicBlock
213 BasicBlock* immediate_post_dominator_;
214
215 /// The set of predecessors of the BasicBlock
216 std::vector<BasicBlock*> predecessors_;
217
218 /// The set of successors of the BasicBlock
219 std::vector<BasicBlock*> successors_;
220
221 /// The type of the block
222 std::bitset<kBlockTypeCOUNT> type_;
223
224 /// True if the block is reachable in the CFG
225 bool reachable_;
226
227 /// label of this block, if any.
228 const Instruction* label_;
229
230 /// Terminator of this block.
231 const Instruction* terminator_;
232};
233
234/// @brief Returns true if the iterators point to the same element or if both
235/// iterators point to the @p dom_end block
236bool operator==(const BasicBlock::DominatorIterator& lhs,
237 const BasicBlock::DominatorIterator& rhs);
238
239/// @brief Returns true if the iterators point to different elements and they
240/// do not both point to the @p dom_end block
241bool operator!=(const BasicBlock::DominatorIterator& lhs,
242 const BasicBlock::DominatorIterator& rhs);
243
244} // namespace val
245} // namespace spvtools
246
247#endif // SOURCE_VAL_BASIC_BLOCK_H_
248