1// Copyright (c) 2016 Google 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// This file defines the language constructs for representing a SPIR-V
16// module in memory.
17
18#ifndef SOURCE_OPT_BASIC_BLOCK_H_
19#define SOURCE_OPT_BASIC_BLOCK_H_
20
21#include <functional>
22#include <iterator>
23#include <memory>
24#include <ostream>
25#include <string>
26#include <utility>
27#include <vector>
28
29#include "source/opt/instruction.h"
30#include "source/opt/instruction_list.h"
31#include "source/opt/iterator.h"
32
33namespace spvtools {
34namespace opt {
35
36class Function;
37class IRContext;
38
39// A SPIR-V basic block.
40class BasicBlock {
41 public:
42 using iterator = InstructionList::iterator;
43 using const_iterator = InstructionList::const_iterator;
44 using reverse_iterator = std::reverse_iterator<InstructionList::iterator>;
45 using const_reverse_iterator =
46 std::reverse_iterator<InstructionList::const_iterator>;
47
48 // Creates a basic block with the given starting |label|.
49 inline explicit BasicBlock(std::unique_ptr<Instruction> label);
50
51 explicit BasicBlock(const BasicBlock& bb) = delete;
52
53 // Creates a clone of the basic block in the given |context|
54 //
55 // The parent function will default to null and needs to be explicitly set by
56 // the user.
57 //
58 // If the inst-to-block map in |context| is valid, then the new instructions
59 // will be inserted into the map.
60 BasicBlock* Clone(IRContext*) const;
61
62 // Sets the enclosing function for this basic block.
63 void SetParent(Function* function) { function_ = function; }
64
65 // Return the enclosing function
66 inline Function* GetParent() const { return function_; }
67
68 // Appends an instruction to this basic block.
69 inline void AddInstruction(std::unique_ptr<Instruction> i);
70
71 // Appends all of block's instructions (except label) to this block
72 inline void AddInstructions(BasicBlock* bp);
73
74 // The pointer to the label starting this basic block.
75 std::unique_ptr<Instruction>& GetLabel() { return label_; }
76
77 // The label starting this basic block.
78 Instruction* GetLabelInst() { return label_.get(); }
79 const Instruction* GetLabelInst() const { return label_.get(); }
80
81 // Returns the merge instruction in this basic block, if it exists.
82 // Otherwise return null. May be used whenever tail() can be used.
83 const Instruction* GetMergeInst() const;
84 Instruction* GetMergeInst();
85
86 // Returns the OpLoopMerge instruciton in this basic block, if it exists.
87 // Otherwise return null. May be used whenever tail() can be used.
88 const Instruction* GetLoopMergeInst() const;
89 Instruction* GetLoopMergeInst();
90
91 // Returns the id of the label at the top of this block
92 inline uint32_t id() const { return label_->result_id(); }
93
94 iterator begin() { return insts_.begin(); }
95 iterator end() { return insts_.end(); }
96 const_iterator begin() const { return insts_.cbegin(); }
97 const_iterator end() const { return insts_.cend(); }
98 const_iterator cbegin() const { return insts_.cbegin(); }
99 const_iterator cend() const { return insts_.cend(); }
100
101 reverse_iterator rbegin() { return reverse_iterator(end()); }
102 reverse_iterator rend() { return reverse_iterator(begin()); }
103 const_reverse_iterator rbegin() const {
104 return const_reverse_iterator(cend());
105 }
106 const_reverse_iterator rend() const {
107 return const_reverse_iterator(cbegin());
108 }
109 const_reverse_iterator crbegin() const {
110 return const_reverse_iterator(cend());
111 }
112 const_reverse_iterator crend() const {
113 return const_reverse_iterator(cbegin());
114 }
115
116 // Returns an iterator pointing to the last instruction. This may only
117 // be used if this block has an instruction other than the OpLabel
118 // that defines it.
119 iterator tail() {
120 assert(!insts_.empty());
121 return --end();
122 }
123
124 // Returns a const iterator, but othewrise similar to tail().
125 const_iterator ctail() const {
126 assert(!insts_.empty());
127 return --insts_.cend();
128 }
129
130 // Returns true if the basic block has at least one successor.
131 inline bool hasSuccessor() const { return ctail()->IsBranch(); }
132
133 // Runs the given function |f| on each instruction in this basic block, and
134 // optionally on the debug line instructions that might precede them.
135 inline void ForEachInst(const std::function<void(Instruction*)>& f,
136 bool run_on_debug_line_insts = false);
137 inline void ForEachInst(const std::function<void(const Instruction*)>& f,
138 bool run_on_debug_line_insts = false) const;
139
140 // Runs the given function |f| on each instruction in this basic block, and
141 // optionally on the debug line instructions that might precede them. If |f|
142 // returns false, iteration is terminated and this function returns false.
143 inline bool WhileEachInst(const std::function<bool(Instruction*)>& f,
144 bool run_on_debug_line_insts = false);
145 inline bool WhileEachInst(const std::function<bool(const Instruction*)>& f,
146 bool run_on_debug_line_insts = false) const;
147
148 // Runs the given function |f| on each Phi instruction in this basic block,
149 // and optionally on the debug line instructions that might precede them.
150 inline void ForEachPhiInst(const std::function<void(Instruction*)>& f,
151 bool run_on_debug_line_insts = false);
152
153 // Runs the given function |f| on each Phi instruction in this basic block,
154 // and optionally on the debug line instructions that might precede them. If
155 // |f| returns false, iteration is terminated and this function return false.
156 inline bool WhileEachPhiInst(const std::function<bool(Instruction*)>& f,
157 bool run_on_debug_line_insts = false);
158
159 // Runs the given function |f| on each label id of each successor block
160 void ForEachSuccessorLabel(
161 const std::function<void(const uint32_t)>& f) const;
162
163 // Runs the given function |f| on each label id of each successor block. If
164 // |f| returns false, iteration is terminated and this function returns false.
165 bool WhileEachSuccessorLabel(
166 const std::function<bool(const uint32_t)>& f) const;
167
168 // Runs the given function |f| on each label id of each successor block.
169 // Modifying the pointed value will change the branch taken by the basic
170 // block. It is the caller responsibility to update or invalidate the CFG.
171 void ForEachSuccessorLabel(const std::function<void(uint32_t*)>& f);
172
173 // Returns true if |block| is a direct successor of |this|.
174 bool IsSuccessor(const BasicBlock* block) const;
175
176 // Runs the given function |f| on the merge and continue label, if any
177 void ForMergeAndContinueLabel(const std::function<void(const uint32_t)>& f);
178
179 // Returns true if this basic block has any Phi instructions.
180 bool HasPhiInstructions() {
181 return !WhileEachPhiInst([](Instruction*) { return false; });
182 }
183
184 // Return true if this block is a loop header block.
185 bool IsLoopHeader() const { return GetLoopMergeInst() != nullptr; }
186
187 // Returns the ID of the merge block declared by a merge instruction in this
188 // block, if any. If none, returns zero.
189 uint32_t MergeBlockIdIfAny() const;
190
191 // Returns MergeBlockIdIfAny() and asserts that it is non-zero.
192 uint32_t MergeBlockId() const;
193
194 // Returns the ID of the continue block declared by a merge instruction in
195 // this block, if any. If none, returns zero.
196 uint32_t ContinueBlockIdIfAny() const;
197
198 // Returns ContinueBlockIdIfAny() and asserts that it is non-zero.
199 uint32_t ContinueBlockId() const;
200
201 // Returns the terminator instruction. Assumes the terminator exists.
202 Instruction* terminator() { return &*tail(); }
203 const Instruction* terminator() const { return &*ctail(); }
204
205 // Returns true if this basic block exits this function and returns to its
206 // caller.
207 bool IsReturn() const { return ctail()->IsReturn(); }
208
209 // Returns true if this basic block exits this function or aborts execution.
210 bool IsReturnOrAbort() const { return ctail()->IsReturnOrAbort(); }
211
212 // Kill all instructions in this block. Whether or not to kill the label is
213 // indicated by |killLabel|.
214 void KillAllInsts(bool killLabel);
215
216 // Splits this basic block into two. Returns a new basic block with label
217 // |label_id| containing the instructions from |iter| onwards. Instructions
218 // prior to |iter| remain in this basic block. The new block will be added
219 // to the function immediately after the original block.
220 BasicBlock* SplitBasicBlock(IRContext* context, uint32_t label_id,
221 iterator iter);
222
223 // Pretty-prints this basic block into a std::string by printing every
224 // instruction in it.
225 //
226 // |options| are the disassembly options. SPV_BINARY_TO_TEXT_OPTION_NO_HEADER
227 // is always added to |options|.
228 std::string PrettyPrint(uint32_t options = 0u) const;
229
230 // Dump this basic block on stderr. Useful when running interactive
231 // debuggers.
232 void Dump() const;
233
234 private:
235 // The enclosing function.
236 Function* function_;
237 // The label starting this basic block.
238 std::unique_ptr<Instruction> label_;
239 // Instructions inside this basic block, but not the OpLabel.
240 InstructionList insts_;
241};
242
243// Pretty-prints |block| to |str|. Returns |str|.
244std::ostream& operator<<(std::ostream& str, const BasicBlock& block);
245
246inline BasicBlock::BasicBlock(std::unique_ptr<Instruction> label)
247 : function_(nullptr), label_(std::move(label)) {}
248
249inline void BasicBlock::AddInstruction(std::unique_ptr<Instruction> i) {
250 insts_.push_back(std::move(i));
251}
252
253inline void BasicBlock::AddInstructions(BasicBlock* bp) {
254 auto bEnd = end();
255 (void)bEnd.MoveBefore(&bp->insts_);
256}
257
258inline bool BasicBlock::WhileEachInst(
259 const std::function<bool(Instruction*)>& f, bool run_on_debug_line_insts) {
260 if (label_) {
261 if (!label_->WhileEachInst(f, run_on_debug_line_insts)) return false;
262 }
263 if (insts_.empty()) {
264 return true;
265 }
266
267 Instruction* inst = &insts_.front();
268 while (inst != nullptr) {
269 Instruction* next_instruction = inst->NextNode();
270 if (!inst->WhileEachInst(f, run_on_debug_line_insts)) return false;
271 inst = next_instruction;
272 }
273 return true;
274}
275
276inline bool BasicBlock::WhileEachInst(
277 const std::function<bool(const Instruction*)>& f,
278 bool run_on_debug_line_insts) const {
279 if (label_) {
280 if (!static_cast<const Instruction*>(label_.get())
281 ->WhileEachInst(f, run_on_debug_line_insts))
282 return false;
283 }
284 for (const auto& inst : insts_) {
285 if (!static_cast<const Instruction*>(&inst)->WhileEachInst(
286 f, run_on_debug_line_insts))
287 return false;
288 }
289 return true;
290}
291
292inline void BasicBlock::ForEachInst(const std::function<void(Instruction*)>& f,
293 bool run_on_debug_line_insts) {
294 WhileEachInst(
295 [&f](Instruction* inst) {
296 f(inst);
297 return true;
298 },
299 run_on_debug_line_insts);
300}
301
302inline void BasicBlock::ForEachInst(
303 const std::function<void(const Instruction*)>& f,
304 bool run_on_debug_line_insts) const {
305 WhileEachInst(
306 [&f](const Instruction* inst) {
307 f(inst);
308 return true;
309 },
310 run_on_debug_line_insts);
311}
312
313inline bool BasicBlock::WhileEachPhiInst(
314 const std::function<bool(Instruction*)>& f, bool run_on_debug_line_insts) {
315 if (insts_.empty()) {
316 return true;
317 }
318
319 Instruction* inst = &insts_.front();
320 while (inst != nullptr) {
321 Instruction* next_instruction = inst->NextNode();
322 if (inst->opcode() != SpvOpPhi) break;
323 if (!inst->WhileEachInst(f, run_on_debug_line_insts)) return false;
324 inst = next_instruction;
325 }
326 return true;
327}
328
329inline void BasicBlock::ForEachPhiInst(
330 const std::function<void(Instruction*)>& f, bool run_on_debug_line_insts) {
331 WhileEachPhiInst(
332 [&f](Instruction* inst) {
333 f(inst);
334 return true;
335 },
336 run_on_debug_line_insts);
337}
338
339} // namespace opt
340} // namespace spvtools
341
342#endif // SOURCE_OPT_BASIC_BLOCK_H_
343