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#ifndef SOURCE_OPT_FUNCTION_H_
16#define SOURCE_OPT_FUNCTION_H_
17
18#include <algorithm>
19#include <functional>
20#include <memory>
21#include <string>
22#include <utility>
23#include <vector>
24
25#include "source/opt/basic_block.h"
26#include "source/opt/instruction.h"
27#include "source/opt/iterator.h"
28
29namespace spvtools {
30namespace opt {
31
32class CFG;
33class IRContext;
34class Module;
35
36// A SPIR-V function.
37class Function {
38 public:
39 using iterator = UptrVectorIterator<BasicBlock>;
40 using const_iterator = UptrVectorIterator<BasicBlock, true>;
41
42 // Creates a function instance declared by the given OpFunction instruction
43 // |def_inst|.
44 inline explicit Function(std::unique_ptr<Instruction> def_inst);
45
46 explicit Function(const Function& f) = delete;
47
48 // Creates a clone of the instruction in the given |context|
49 //
50 // The parent module will default to null and needs to be explicitly set by
51 // the user.
52 Function* Clone(IRContext*) const;
53 // The OpFunction instruction that begins the definition of this function.
54 Instruction& DefInst() { return *def_inst_; }
55 const Instruction& DefInst() const { return *def_inst_; }
56
57 // Appends a parameter to this function.
58 inline void AddParameter(std::unique_ptr<Instruction> p);
59 // Appends a debug instruction in function header to this function.
60 inline void AddDebugInstructionInHeader(std::unique_ptr<Instruction> p);
61 // Appends a basic block to this function.
62 inline void AddBasicBlock(std::unique_ptr<BasicBlock> b);
63 // Appends a basic block to this function at the position |ip|.
64 inline void AddBasicBlock(std::unique_ptr<BasicBlock> b, iterator ip);
65 template <typename T>
66 inline void AddBasicBlocks(T begin, T end, iterator ip);
67
68 // Move basic block with |id| to the position after |ip|. Both have to be
69 // contained in this function.
70 inline void MoveBasicBlockToAfter(uint32_t id, BasicBlock* ip);
71
72 // Delete all basic blocks that contain no instructions.
73 inline void RemoveEmptyBlocks();
74
75 // Saves the given function end instruction.
76 inline void SetFunctionEnd(std::unique_ptr<Instruction> end_inst);
77
78 // Returns the given function end instruction.
79 inline Instruction* EndInst() { return end_inst_.get(); }
80 inline const Instruction* EndInst() const { return end_inst_.get(); }
81
82 // Returns function's id
83 inline uint32_t result_id() const { return def_inst_->result_id(); }
84
85 // Returns function's return type id
86 inline uint32_t type_id() const { return def_inst_->type_id(); }
87
88 // Returns the entry basic block for this function.
89 const std::unique_ptr<BasicBlock>& entry() const { return blocks_.front(); }
90
91 iterator begin() { return iterator(&blocks_, blocks_.begin()); }
92 iterator end() { return iterator(&blocks_, blocks_.end()); }
93 const_iterator begin() const { return cbegin(); }
94 const_iterator end() const { return cend(); }
95 const_iterator cbegin() const {
96 return const_iterator(&blocks_, blocks_.cbegin());
97 }
98 const_iterator cend() const {
99 return const_iterator(&blocks_, blocks_.cend());
100 }
101
102 // Returns an iterator to the basic block |id|.
103 iterator FindBlock(uint32_t bb_id) {
104 return std::find_if(begin(), end(), [bb_id](const BasicBlock& it_bb) {
105 return bb_id == it_bb.id();
106 });
107 }
108
109 // Runs the given function |f| on instructions in this function, in order,
110 // and optionally on debug line instructions that might precede them.
111 void ForEachInst(const std::function<void(Instruction*)>& f,
112 bool run_on_debug_line_insts = false);
113 void ForEachInst(const std::function<void(const Instruction*)>& f,
114 bool run_on_debug_line_insts = false) const;
115 // Runs the given function |f| on instructions in this function, in order,
116 // and optionally on debug line instructions that might precede them.
117 // If |f| returns false, iteration is terminated and this function returns
118 // false.
119 bool WhileEachInst(const std::function<bool(Instruction*)>& f,
120 bool run_on_debug_line_insts = false);
121 bool WhileEachInst(const std::function<bool(const Instruction*)>& f,
122 bool run_on_debug_line_insts = false) const;
123
124 // Runs the given function |f| on each parameter instruction in this function,
125 // in order, and optionally on debug line instructions that might precede
126 // them.
127 void ForEachParam(const std::function<void(const Instruction*)>& f,
128 bool run_on_debug_line_insts = false) const;
129 void ForEachParam(const std::function<void(Instruction*)>& f,
130 bool run_on_debug_line_insts = false);
131
132 BasicBlock* InsertBasicBlockAfter(std::unique_ptr<BasicBlock>&& new_block,
133 BasicBlock* position);
134
135 BasicBlock* InsertBasicBlockBefore(std::unique_ptr<BasicBlock>&& new_block,
136 BasicBlock* position);
137
138 // Return true if the function calls itself either directly or indirectly.
139 bool IsRecursive() const;
140
141 // Pretty-prints all the basic blocks in this function into a std::string.
142 //
143 // |options| are the disassembly options. SPV_BINARY_TO_TEXT_OPTION_NO_HEADER
144 // is always added to |options|.
145 std::string PrettyPrint(uint32_t options = 0u) const;
146
147 // Dump this function on stderr. Useful when running interactive
148 // debuggers.
149 void Dump() const;
150
151 private:
152 // The OpFunction instruction that begins the definition of this function.
153 std::unique_ptr<Instruction> def_inst_;
154 // All parameters to this function.
155 std::vector<std::unique_ptr<Instruction>> params_;
156 // All debug instructions in this function's header.
157 InstructionList debug_insts_in_header_;
158 // All basic blocks inside this function in specification order
159 std::vector<std::unique_ptr<BasicBlock>> blocks_;
160 // The OpFunctionEnd instruction.
161 std::unique_ptr<Instruction> end_inst_;
162};
163
164// Pretty-prints |func| to |str|. Returns |str|.
165std::ostream& operator<<(std::ostream& str, const Function& func);
166
167inline Function::Function(std::unique_ptr<Instruction> def_inst)
168 : def_inst_(std::move(def_inst)), end_inst_() {}
169
170inline void Function::AddParameter(std::unique_ptr<Instruction> p) {
171 params_.emplace_back(std::move(p));
172}
173
174inline void Function::AddDebugInstructionInHeader(
175 std::unique_ptr<Instruction> p) {
176 debug_insts_in_header_.push_back(std::move(p));
177}
178
179inline void Function::AddBasicBlock(std::unique_ptr<BasicBlock> b) {
180 AddBasicBlock(std::move(b), end());
181}
182
183inline void Function::AddBasicBlock(std::unique_ptr<BasicBlock> b,
184 iterator ip) {
185 ip.InsertBefore(std::move(b));
186}
187
188template <typename T>
189inline void Function::AddBasicBlocks(T src_begin, T src_end, iterator ip) {
190 blocks_.insert(ip.Get(), std::make_move_iterator(src_begin),
191 std::make_move_iterator(src_end));
192}
193
194inline void Function::MoveBasicBlockToAfter(uint32_t id, BasicBlock* ip) {
195 auto block_to_move = std::move(*FindBlock(id).Get());
196
197 assert(block_to_move->GetParent() == ip->GetParent() &&
198 "Both blocks have to be in the same function.");
199
200 InsertBasicBlockAfter(std::move(block_to_move), ip);
201 blocks_.erase(std::find(std::begin(blocks_), std::end(blocks_), nullptr));
202}
203
204inline void Function::RemoveEmptyBlocks() {
205 auto first_empty =
206 std::remove_if(std::begin(blocks_), std::end(blocks_),
207 [](const std::unique_ptr<BasicBlock>& bb) -> bool {
208 return bb->GetLabelInst()->opcode() == SpvOpNop;
209 });
210 blocks_.erase(first_empty, std::end(blocks_));
211}
212
213inline void Function::SetFunctionEnd(std::unique_ptr<Instruction> end_inst) {
214 end_inst_ = std::move(end_inst);
215}
216
217} // namespace opt
218} // namespace spvtools
219
220#endif // SOURCE_OPT_FUNCTION_H_
221