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
24namespace spvtools {
25namespace opt {
26
27Function* 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 return clone;
51}
52
53void Function::ForEachInst(const std::function<void(Instruction*)>& f,
54 bool run_on_debug_line_insts) {
55 WhileEachInst(
56 [&f](Instruction* inst) {
57 f(inst);
58 return true;
59 },
60 run_on_debug_line_insts);
61}
62
63void Function::ForEachInst(const std::function<void(const Instruction*)>& f,
64 bool run_on_debug_line_insts) const {
65 WhileEachInst(
66 [&f](const Instruction* inst) {
67 f(inst);
68 return true;
69 },
70 run_on_debug_line_insts);
71}
72
73bool Function::WhileEachInst(const std::function<bool(Instruction*)>& f,
74 bool run_on_debug_line_insts) {
75 if (def_inst_) {
76 if (!def_inst_->WhileEachInst(f, run_on_debug_line_insts)) {
77 return false;
78 }
79 }
80
81 for (auto& param : params_) {
82 if (!param->WhileEachInst(f, run_on_debug_line_insts)) {
83 return false;
84 }
85 }
86
87 for (auto& di : debug_insts_in_header_) {
88 if (!di.WhileEachInst(f, run_on_debug_line_insts)) {
89 return false;
90 }
91 }
92
93 for (auto& bb : blocks_) {
94 if (!bb->WhileEachInst(f, run_on_debug_line_insts)) {
95 return false;
96 }
97 }
98
99 if (end_inst_) return end_inst_->WhileEachInst(f, run_on_debug_line_insts);
100
101 return true;
102}
103
104bool Function::WhileEachInst(const std::function<bool(const Instruction*)>& f,
105 bool run_on_debug_line_insts) const {
106 if (def_inst_) {
107 if (!static_cast<const Instruction*>(def_inst_.get())
108 ->WhileEachInst(f, run_on_debug_line_insts)) {
109 return false;
110 }
111 }
112
113 for (const auto& param : params_) {
114 if (!static_cast<const Instruction*>(param.get())
115 ->WhileEachInst(f, run_on_debug_line_insts)) {
116 return false;
117 }
118 }
119
120 for (const auto& di : debug_insts_in_header_) {
121 if (!di.WhileEachInst(f, run_on_debug_line_insts)) {
122 return false;
123 }
124 }
125
126 for (const auto& bb : blocks_) {
127 if (!static_cast<const BasicBlock*>(bb.get())->WhileEachInst(
128 f, run_on_debug_line_insts)) {
129 return false;
130 }
131 }
132
133 if (end_inst_)
134 return static_cast<const Instruction*>(end_inst_.get())
135 ->WhileEachInst(f, run_on_debug_line_insts);
136
137 return true;
138}
139
140void Function::ForEachParam(const std::function<void(Instruction*)>& f,
141 bool run_on_debug_line_insts) {
142 for (auto& param : params_)
143 static_cast<Instruction*>(param.get())
144 ->ForEachInst(f, run_on_debug_line_insts);
145}
146
147void Function::ForEachParam(const std::function<void(const Instruction*)>& f,
148 bool run_on_debug_line_insts) const {
149 for (const auto& param : params_)
150 static_cast<const Instruction*>(param.get())
151 ->ForEachInst(f, run_on_debug_line_insts);
152}
153
154BasicBlock* Function::InsertBasicBlockAfter(
155 std::unique_ptr<BasicBlock>&& new_block, BasicBlock* position) {
156 for (auto bb_iter = begin(); bb_iter != end(); ++bb_iter) {
157 if (&*bb_iter == position) {
158 new_block->SetParent(this);
159 ++bb_iter;
160 bb_iter = bb_iter.InsertBefore(std::move(new_block));
161 return &*bb_iter;
162 }
163 }
164 assert(false && "Could not find insertion point.");
165 return nullptr;
166}
167
168BasicBlock* Function::InsertBasicBlockBefore(
169 std::unique_ptr<BasicBlock>&& new_block, BasicBlock* position) {
170 for (auto bb_iter = begin(); bb_iter != end(); ++bb_iter) {
171 if (&*bb_iter == position) {
172 new_block->SetParent(this);
173 bb_iter = bb_iter.InsertBefore(std::move(new_block));
174 return &*bb_iter;
175 }
176 }
177 assert(false && "Could not find insertion point.");
178 return nullptr;
179}
180
181bool Function::IsRecursive() const {
182 IRContext* ctx = blocks_.front()->GetLabel()->context();
183 IRContext::ProcessFunction mark_visited = [this](Function* fp) {
184 return fp == this;
185 };
186
187 // Process the call tree from all of the function called by |this|. If it get
188 // back to |this|, then we have a recursive function.
189 std::queue<uint32_t> roots;
190 ctx->AddCalls(this, &roots);
191 return ctx->ProcessCallTreeFromRoots(mark_visited, &roots);
192}
193
194std::ostream& operator<<(std::ostream& str, const Function& func) {
195 str << func.PrettyPrint();
196 return str;
197}
198
199void Function::Dump() const {
200 std::cerr << "Function #" << result_id() << "\n" << *this << "\n";
201}
202
203std::string Function::PrettyPrint(uint32_t options) const {
204 std::ostringstream str;
205 ForEachInst([&str, options](const Instruction* inst) {
206 str << inst->PrettyPrint(options);
207 if (inst->opcode() != SpvOpFunctionEnd) {
208 str << std::endl;
209 }
210 });
211 return str.str();
212}
213} // namespace opt
214} // namespace spvtools
215