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