Debian Codegraph @

third_party/spirv-tools/source/opt/function.cpp

raw
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 #include "source/opt/function.h"
16
17 #include <ostream>
18 #include <sstream>
19
20 #include "function.h"
21 #include "ir_context.h"
22 #include "source/util/bit_vector.h"
23
24 namespace spvtools {
25 namespace opt {
26
27 Function* Function::Clone(IRContext* ctx) const {
28 Function* clone =
29 new Function(std::unique_ptr<Instruction>(DefInst().Clone(ctx)));
30 clone->params_.reserve(params_.size());
31 ForEachParam(
32 [clone, ctx](const Instruction* inst) {
33 clone->AddParameter(std::unique_ptr<Instruction>(inst->Clone(ctx)));
34 },
35 true);
36
37 for (const auto& i : debug_insts_in_header_) {
38 clone->AddDebugInstructionInHeader(
39 std::unique_ptr<Instruction>(i.Clone(ctx)));
40 }
41
42 clone->blocks_.reserve(blocks_.size());
43 for (const auto& b : blocks_) {
44 std::unique_ptr<BasicBlock> bb(b->Clone(ctx));
45 bb->SetParent(clone);
46 clone->AddBasicBlock(std::move(bb));
47 }
48
49 clone->SetFunctionEnd(std::unique_ptr<Instruction>(EndInst()->Clone(ctx)));
50
51 clone->non_semantic_.reserve(non_semantic_.size());
52 for (auto& non_semantic : non_semantic_) {
53 clone->AddNonSemanticInstruction(
54 std::unique_ptr<Instruction>(non_semantic->Clone(ctx)));
55 }
56 return clone;
57 }
58
59 void Function::ForEachInst(const std::function<void(Instruction*)>& f,
60 bool run_on_debug_line_insts,
61 bool run_on_non_semantic_insts) {
62 WhileEachInst(
63 [&f](Instruction* inst) {
64 f(inst);
65 return true;
66 },
67 run_on_debug_line_insts, run_on_non_semantic_insts);
68 }
69
70 void Function::ForEachInst(const std::function<void(const Instruction*)>& f,
71 bool run_on_debug_line_insts,
72 bool run_on_non_semantic_insts) const {
73 WhileEachInst(
74 [&f](const Instruction* inst) {
75 f(inst);
76 return true;
77 },
78 run_on_debug_line_insts, run_on_non_semantic_insts);
79 }
80
81 bool Function::WhileEachInst(const std::function<bool(Instruction*)>& f,
82 bool run_on_debug_line_insts,
83 bool run_on_non_semantic_insts) {
84 if (def_inst_) {
85 if (!def_inst_->WhileEachInst(f, run_on_debug_line_insts)) {
86 return false;
87 }
88 }
89
90 for (auto& param : params_) {
91 if (!param->WhileEachInst(f, run_on_debug_line_insts)) {
92 return false;
93 }
94 }
95
96 if (!debug_insts_in_header_.empty()) {
97 Instruction* di = &debug_insts_in_header_.front();
98 while (di != nullptr) {
99 Instruction* next_instruction = di->NextNode();
100 if (!di->WhileEachInst(f, run_on_debug_line_insts)) return false;
101 di = next_instruction;
102 }
103 }
104
105 for (auto& bb : blocks_) {
106 if (!bb->WhileEachInst(f, run_on_debug_line_insts)) {
107 return false;
108 }
109 }
110
111 if (end_inst_) {
112 if (!end_inst_->WhileEachInst(f, run_on_debug_line_insts)) {
113 return false;
114 }
115 }
116
117 if (run_on_non_semantic_insts) {
118 for (auto& non_semantic : non_semantic_) {
119 if (!non_semantic->WhileEachInst(f, run_on_debug_line_insts)) {
120 return false;
121 }
122 }
123 }
124
125 return true;
126 }
127
128 bool Function::WhileEachInst(const std::function<bool(const Instruction*)>& f,
129 bool run_on_debug_line_insts,
130 bool run_on_non_semantic_insts) const {
131 if (def_inst_) {
132 if (!static_cast<const Instruction*>(def_inst_.get())
133 ->WhileEachInst(f, run_on_debug_line_insts)) {
134 return false;
135 }
136 }
137
138 for (const auto& param : params_) {
139 if (!static_cast<const Instruction*>(param.get())
140 ->WhileEachInst(f, run_on_debug_line_insts)) {
141 return false;
142 }
143 }
144
145 for (const auto& di : debug_insts_in_header_) {
146 if (!static_cast<const Instruction*>(&di)->WhileEachInst(
147 f, run_on_debug_line_insts))
148 return false;
149 }
150
151 for (const auto& bb : blocks_) {
152 if (!static_cast<const BasicBlock*>(bb.get())->WhileEachInst(
153 f, run_on_debug_line_insts)) {
154 return false;
155 }
156 }
157
158 if (end_inst_) {
159 if (!static_cast<const Instruction*>(end_inst_.get())
160 ->WhileEachInst(f, run_on_debug_line_insts)) {
161 return false;
162 }
163 }
164
165 if (run_on_non_semantic_insts) {
166 for (auto& non_semantic : non_semantic_) {
167 if (!static_cast<const Instruction*>(non_semantic.get())
168 ->WhileEachInst(f, run_on_debug_line_insts)) {
169 return false;
170 }
171 }
172 }
173
174 return true;
175 }
176
177 void Function::ForEachParam(const std::function<void(Instruction*)>& f,
178 bool run_on_debug_line_insts) {
179 for (auto& param : params_)
180 static_cast<Instruction*>(param.get())
181 ->ForEachInst(f, run_on_debug_line_insts);
182 }
183
184 void Function::ForEachParam(const std::function<void(const Instruction*)>& f,
185 bool run_on_debug_line_insts) const {
186 for (const auto& param : params_)
187 static_cast<const Instruction*>(param.get())
188 ->ForEachInst(f, run_on_debug_line_insts);
189 }
190
191 void Function::ForEachDebugInstructionsInHeader(
192 const std::function<void(Instruction*)>& f) {
193 if (debug_insts_in_header_.empty()) return;
194
195 Instruction* di = &debug_insts_in_header_.front();
196 while (di != nullptr) {
197 Instruction* next_instruction = di->NextNode();
198 di->ForEachInst(f);
199 di = next_instruction;
200 }
201 }
202
203 BasicBlock* Function::InsertBasicBlockAfter(
204 std::unique_ptr<BasicBlock>&& new_block, BasicBlock* position) {
205 for (auto bb_iter = begin(); bb_iter != end(); ++bb_iter) {
206 if (&*bb_iter == position) {
207 new_block->SetParent(this);
208 ++bb_iter;
209 bb_iter = bb_iter.InsertBefore(std::move(new_block));
210 return &*bb_iter;
211 }
212 }
213 assert(false && "Could not find insertion point.");
214 return nullptr;
215 }
216
217 BasicBlock* Function::InsertBasicBlockBefore(
218 std::unique_ptr<BasicBlock>&& new_block, BasicBlock* position) {
219 for (auto bb_iter = begin(); bb_iter != end(); ++bb_iter) {
220 if (&*bb_iter == position) {
221 new_block->SetParent(this);
222 bb_iter = bb_iter.InsertBefore(std::move(new_block));
223 return &*bb_iter;
224 }
225 }
226 assert(false && "Could not find insertion point.");
227 return nullptr;
228 }
229
230 bool Function::HasEarlyReturn() const {
231 auto post_dominator_analysis =
232 blocks_.front()->GetLabel()->context()->GetPostDominatorAnalysis(this);
233 for (auto& block : blocks_) {
234 if (spvOpcodeIsReturn(block->tail()->opcode()) &&
235 !post_dominator_analysis->Dominates(block.get(), entry().get())) {
236 return true;
237 }
238 }
239 return false;
240 }
241
242 bool Function::IsRecursive() const {
243 IRContext* ctx = blocks_.front()->GetLabel()->context();
244 IRContext::ProcessFunction mark_visited = [this](Function* fp) {
245 return fp == this;
246 };
247
248 // Process the call tree from all of the function called by |this|. If it get
249 // back to |this|, then we have a recursive function.
250 std::queue<uint32_t> roots;
251 ctx->AddCalls(this, &roots);
252 return ctx->ProcessCallTreeFromRoots(mark_visited, &roots);
253 }
254
255 std::ostream& operator<<(std::ostream& str, const Function& func) {
256 str << func.PrettyPrint();
257 return str;
258 }
259
260 void Function::Dump() const {
261 std::cerr << "Function #" << result_id() << "\n" << *this << "\n";
262 }
263
264 std::string Function::PrettyPrint(uint32_t options) const {
265 std::ostringstream str;
266 ForEachInst([&str, options](const Instruction* inst) {
267 str << inst->PrettyPrint(options);
268 if (inst->opcode() != SpvOpFunctionEnd) {
269 str << std::endl;
270 }
271 });
272 return str.str();
273 }
274 } // namespace opt
275 } // namespace spvtools