| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* Copyright 2025 Jonathan S. Arney | ||
| 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 | * https://github.com/jarney/gyoji/blob/master/LICENSE | ||
| 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 <gyoji-mir/functions.hpp> | ||
| 16 | #include <variant> | ||
| 17 | #include <stdio.h> | ||
| 18 | |||
| 19 | using namespace Gyoji::mir; | ||
| 20 | |||
| 21 | ///////////////////////////////////// | ||
| 22 | // Functions | ||
| 23 | ///////////////////////////////////// | ||
| 24 | 30 | Functions::Functions() | |
| 25 | { | ||
| 26 | 30 | } | |
| 27 | |||
| 28 | 30 | Functions::~Functions() | |
| 29 | 30 | {} | |
| 30 | |||
| 31 | void | ||
| 32 | 270 | Functions::add_function(Gyoji::owned<Function> _function) | |
| 33 | { | ||
| 34 | 270 | functions.push_back(std::move(_function)); | |
| 35 | 270 | } | |
| 36 | |||
| 37 | const std::vector<Gyoji::owned<Function>> & | ||
| 38 | 140 | Functions::get_functions() const | |
| 39 | 140 | { return functions; } | |
| 40 | |||
| 41 | void | ||
| 42 | 28 | Functions::dump(FILE *out) const | |
| 43 | { | ||
| 44 |
2/2✓ Branch 5 taken 270 times.
✓ Branch 6 taken 28 times.
|
298 | for (const auto & function : functions) { |
| 45 | 270 | function->dump(out); | |
| 46 | } | ||
| 47 | 28 | } | |
| 48 | |||
| 49 | ///////////////////////////////////// | ||
| 50 | // Function | ||
| 51 | ///////////////////////////////////// | ||
| 52 | 270 | Function::Function( | |
| 53 | std::string _name, | ||
| 54 | const Type *_return_type, | ||
| 55 | const std::vector<FunctionArgument> & _arguments, | ||
| 56 | bool _is_unsafe, | ||
| 57 | const Gyoji::context::SourceReference & _source_ref | ||
| 58 | 270 | ) | |
| 59 | 270 | : name(_name) | |
| 60 | 270 | , return_type(_return_type) | |
| 61 | 270 | , arguments(_arguments) | |
| 62 | 270 | , m_is_unsafe(_is_unsafe) | |
| 63 | 270 | , source_ref(_source_ref) | |
| 64 | 270 | , blockid(0) | |
| 65 | { | ||
| 66 | 270 | } | |
| 67 | |||
| 68 | 540 | Function::~Function() | |
| 69 | 270 | {} | |
| 70 | |||
| 71 | const std::string & | ||
| 72 | 810 | Function::get_name() const | |
| 73 | 810 | { return name; } | |
| 74 | |||
| 75 | const Type * | ||
| 76 | 540 | Function::get_return_type() const | |
| 77 | 540 | { return return_type; } | |
| 78 | |||
| 79 | const std::vector<FunctionArgument> & | ||
| 80 | 810 | Function::get_arguments() const | |
| 81 | 810 | { return arguments; } | |
| 82 | |||
| 83 | const Gyoji::context::SourceReference & | ||
| 84 | ✗ | Function::get_source_ref() const | |
| 85 | ✗ | { return source_ref; } | |
| 86 | |||
| 87 | bool | ||
| 88 | ✗ | Function::is_unsafe() const | |
| 89 | ✗ | { return m_is_unsafe; } | |
| 90 | |||
| 91 | const BasicBlock & | ||
| 92 | 674 | Function::get_basic_block(size_t blockid) const | |
| 93 | { | ||
| 94 | 674 | const auto & it = blocks.find(blockid); | |
| 95 | 674 | return *(it->second); | |
| 96 | } | ||
| 97 | |||
| 98 | void | ||
| 99 | 3450 | Function::add_operation(size_t block_id, Gyoji::owned<Operation> operation) | |
| 100 | { | ||
| 101 | 3450 | tmpvar_operations[operation->get_result()] = operation.get(); | |
| 102 | 3450 | const auto & it = blocks.find(block_id); | |
| 103 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 3450 times.
|
3450 | if (it == blocks.end()) { |
| 104 | ✗ | return; | |
| 105 | } | ||
| 106 | 3450 | it->second->add_operation(std::move(operation)); | |
| 107 | } | ||
| 108 | |||
| 109 | void | ||
| 110 | 928 | Function::insert_operation(size_t block_id, size_t operation_index, Gyoji::owned<Operation> operation) | |
| 111 | { | ||
| 112 | 928 | tmpvar_operations[operation->get_result()] = operation.get(); | |
| 113 | 928 | const auto & it = blocks.find(block_id); | |
| 114 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 928 times.
|
928 | if (it == blocks.end()) { |
| 115 | ✗ | return; | |
| 116 | } | ||
| 117 | 928 | it->second->insert_operation(operation_index, std::move(operation)); | |
| 118 | } | ||
| 119 | |||
| 120 | |||
| 121 | size_t | ||
| 122 | 364 | Function::add_block() | |
| 123 | { | ||
| 124 | 364 | blocks[blockid] = std::make_unique<BasicBlock>(); | |
| 125 | 364 | size_t blockid_created = blockid; | |
| 126 | 364 | blockid++; | |
| 127 | 364 | return blockid_created; | |
| 128 | } | ||
| 129 | |||
| 130 | const std::map<size_t, Gyoji::owned<BasicBlock>> & | ||
| 131 | 2160 | Function::get_blocks() const | |
| 132 | 2160 | { return blocks; } | |
| 133 | |||
| 134 | const Type * | ||
| 135 | 3458 | Function::tmpvar_get(size_t tmpvar_id) const | |
| 136 | 3458 | { return tmpvars.at(tmpvar_id); } | |
| 137 | |||
| 138 | const Operation * | ||
| 139 | 90 | Function::tmpvar_get_operation(size_t tmpvar) const | |
| 140 | { | ||
| 141 | 90 | const auto & it = tmpvar_operations.find(tmpvar); | |
| 142 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 90 times.
|
90 | if (it == tmpvar_operations.end()) { |
| 143 | ✗ | return nullptr; | |
| 144 | } | ||
| 145 | 90 | return it->second; | |
| 146 | } | ||
| 147 | |||
| 148 | size_t | ||
| 149 | 2798 | Function::tmpvar_define(const Type* type) | |
| 150 | { | ||
| 151 | 2798 | tmpvars.push_back(type); | |
| 152 | 2798 | return tmpvars.size()-1; | |
| 153 | } | ||
| 154 | size_t | ||
| 155 | 6 | Function::tmpvar_duplicate(size_t tempvar_id) | |
| 156 | { | ||
| 157 | 6 | return tmpvar_define(tmpvar_get(tempvar_id)); | |
| 158 | } | ||
| 159 | |||
| 160 | void | ||
| 161 | 270 | Function::calculate_block_reachability() | |
| 162 | { | ||
| 163 | // This map encodes the relationship between a block | ||
| 164 | // and the blocks it is connected to. | ||
| 165 | 270 | std::map<size_t, std::vector<size_t>> edges; | |
| 166 | |||
| 167 | // This is the working list of blocks we're | ||
| 168 | // examining. | ||
| 169 | 270 | std::map<size_t, size_t> open_list; | |
| 170 | 270 | std::map<size_t, size_t> closed_list; | |
| 171 | |||
| 172 | // This is a map of blockid:blockid | ||
| 173 | // for the unreachable blocks. | ||
| 174 | 270 | std::map<size_t, size_t> unreachable; | |
| 175 | |||
| 176 | // Build a graph with the 'edges'. | ||
| 177 |
2/2✓ Branch 5 taken 364 times.
✓ Branch 6 taken 270 times.
|
634 | for (const auto & block : blocks) { |
| 178 | // Everything starts out as unreachable. | ||
| 179 | 364 | unreachable.insert(std::pair(block.first, block.first)); | |
| 180 | 364 | std::vector connections_to = block.second->get_connections(); | |
| 181 | 364 | edges.insert(std::pair(block.first, connections_to)); | |
| 182 | 364 | } | |
| 183 | // We start with only one element on the open list, | ||
| 184 | // that is the 'start' or 'entry' block. | ||
| 185 | |||
| 186 | 270 | open_list.insert(std::pair(0, 0)); | |
| 187 | // With each iteration, we look for | ||
| 188 | // blocks we connect to. Once we find them, | ||
| 189 | // we take them off the unreachable list. | ||
| 190 |
2/2✓ Branch 1 taken 364 times.
✓ Branch 2 taken 270 times.
|
634 | while (open_list.size() != 0) { |
| 191 | 364 | size_t current = open_list.begin()->first; | |
| 192 | 364 | open_list.erase(current); | |
| 193 | 364 | unreachable.erase(current); | |
| 194 | 364 | const auto & connections_to = edges[current]; | |
| 195 |
2/2✓ Branch 5 taken 116 times.
✓ Branch 6 taken 364 times.
|
480 | for (size_t to : connections_to) { |
| 196 | 116 | blocks[to]->add_reachable_from(current); | |
| 197 | |||
| 198 | // Only add it back to the open list | ||
| 199 | // if it wasn't found on the closed list | ||
| 200 | // becuase we've reached it already. | ||
| 201 |
2/2✓ Branch 3 taken 96 times.
✓ Branch 4 taken 20 times.
|
116 | if (closed_list.find(to) == closed_list.end()) { |
| 202 | 96 | open_list.insert(std::pair(to, to)); | |
| 203 | } | ||
| 204 | } | ||
| 205 | 364 | closed_list.insert(std::pair(current, current)); | |
| 206 | } | ||
| 207 |
1/2✗ Branch 5 not taken.
✓ Branch 6 taken 270 times.
|
270 | for (const auto & unreach : unreachable) { |
| 208 | // This is unreachable in the sense that the | ||
| 209 | // basic blocks are not a connected graph. | ||
| 210 | // If this happens, then there is a bug in the 'lowering' | ||
| 211 | // code which should prevent this from being constructed | ||
| 212 | // in this way. | ||
| 213 | ✗ | const BasicBlock & block = get_basic_block(unreach.first); | |
| 214 | |||
| 215 | // If this block is empty, we will already have | ||
| 216 | // reported that as an error, so we don't need to | ||
| 217 | // do that again. | ||
| 218 | ✗ | const auto & operations = block.get_operations(); | |
| 219 | ✗ | if (operations.size() == 0) { | |
| 220 | // Cull it from the block list | ||
| 221 | // becuase it's empty and unreachable. | ||
| 222 | ✗ | blocks.erase(unreach.first); | |
| 223 | } | ||
| 224 | } | ||
| 225 | |||
| 226 | 270 | } | |
| 227 | |||
| 228 | void | ||
| 229 | 810 | Function::iterate_operations(OperationVisitor & visitor) const | |
| 230 | { | ||
| 231 | 810 | const auto & blocks = get_blocks(); | |
| 232 |
2/2✓ Branch 5 taken 1092 times.
✓ Branch 6 taken 810 times.
|
1902 | for (const auto & block_it : blocks) { |
| 233 | 1092 | const BasicBlock & block = *block_it.second; | |
| 234 | 1092 | size_t operation_index = 0; | |
| 235 |
2/2✓ Branch 5 taken 13134 times.
✓ Branch 6 taken 1092 times.
|
14226 | for (const auto & op_it : block.get_operations()) { |
| 236 | 13134 | const Operation & operation = *op_it; | |
| 237 | 13134 | visitor.visit(block_it.first, block, operation_index, operation); | |
| 238 | 13134 | operation_index++; | |
| 239 | } | ||
| 240 | } | ||
| 241 | 810 | } | |
| 242 | |||
| 243 | |||
| 244 | |||
| 245 | |||
| 246 | void | ||
| 247 | 270 | Function::dump(FILE *out) const | |
| 248 | { | ||
| 249 | 270 | fprintf(out, " %s\n", get_name().c_str()); | |
| 250 | 270 | fprintf(out, " return-value : %s\n", return_type->get_name().c_str()); | |
| 251 |
2/2✓ Branch 5 taken 524 times.
✓ Branch 6 taken 270 times.
|
794 | for (const auto & arg : arguments) { |
| 252 | 524 | fprintf(out, " arg %s : %s\n", arg.get_name().c_str(), arg.get_type()->get_name().c_str()); | |
| 253 | } | ||
| 254 | 270 | fprintf(out, " temporary variables\n"); | |
| 255 | 270 | size_t varid = 0; | |
| 256 |
2/2✓ Branch 4 taken 2798 times.
✓ Branch 5 taken 270 times.
|
3068 | for (const auto & value : tmpvars) { |
| 257 | 2798 | fprintf(out, " _%ld : %s\n", varid, value->get_name().c_str()); | |
| 258 | 2798 | varid++; | |
| 259 | } | ||
| 260 | |||
| 261 | 270 | fprintf(out, " {\n"); | |
| 262 |
2/2✓ Branch 5 taken 364 times.
✓ Branch 6 taken 270 times.
|
634 | for (const auto & block_it : blocks) { |
| 263 | 364 | fprintf(out, " BB%ld:\n", block_it.first); | |
| 264 | 364 | const BasicBlock & block = *block_it.second; | |
| 265 | 364 | block.dump(out); | |
| 266 | } | ||
| 267 | 270 | fprintf(out, " }\n"); | |
| 268 | 270 | } | |
| 269 | |||
| 270 | ///////////////////////////////////// | ||
| 271 | // BasicBlock | ||
| 272 | ///////////////////////////////////// | ||
| 273 | |||
| 274 | 364 | BasicBlock::BasicBlock() | |
| 275 | 364 | {} | |
| 276 | |||
| 277 | 364 | BasicBlock::~BasicBlock() | |
| 278 | 364 | {} | |
| 279 | |||
| 280 | void | ||
| 281 | 3450 | BasicBlock::add_operation(Gyoji::owned<Operation> _operation) | |
| 282 | { | ||
| 283 | 3450 | operations.push_back(std::move(_operation)); | |
| 284 | 3450 | } | |
| 285 | |||
| 286 | void | ||
| 287 | 364 | BasicBlock::dump(FILE *out) const | |
| 288 | { | ||
| 289 | 364 | size_t operation_index = 0; | |
| 290 |
2/2✓ Branch 4 taken 4378 times.
✓ Branch 5 taken 364 times.
|
4742 | for (const auto & operation : operations) { |
| 291 | 4378 | operation->dump(out, operation_index); | |
| 292 | 4378 | operation_index++; | |
| 293 | } | ||
| 294 | 364 | } | |
| 295 | const std::vector<Gyoji::owned<Operation>> & | ||
| 296 | 3050 | BasicBlock::get_operations() const | |
| 297 | 3050 | { return operations; } | |
| 298 | |||
| 299 | bool | ||
| 300 | 408 | BasicBlock::contains_terminator() const | |
| 301 | { | ||
| 302 |
2/2✓ Branch 5 taken 4648 times.
✓ Branch 6 taken 24 times.
|
4672 | for (const auto & op : operations) { |
| 303 |
2/2✓ Branch 2 taken 384 times.
✓ Branch 3 taken 4264 times.
|
4648 | if (op->is_terminating()) return true; |
| 304 | } | ||
| 305 | 24 | return false; | |
| 306 | } | ||
| 307 | |||
| 308 | std::vector<size_t> | ||
| 309 | 364 | BasicBlock::get_connections() const | |
| 310 | { | ||
| 311 |
2/2✓ Branch 5 taken 4374 times.
✓ Branch 6 taken 4 times.
|
4378 | for (const auto & op : operations) { |
| 312 |
2/2✓ Branch 2 taken 360 times.
✓ Branch 3 taken 4014 times.
|
4374 | if (op->is_terminating()) { |
| 313 | 360 | return op->get_connections(); | |
| 314 | } | ||
| 315 | } | ||
| 316 | |||
| 317 | // In theory, this should not happen | ||
| 318 | // because we will already have checked | ||
| 319 | // that all blocks have terminators. | ||
| 320 | 4 | std::vector<size_t> empty_edges; | |
| 321 | 4 | return empty_edges; | |
| 322 | 4 | } | |
| 323 | const std::vector<size_t> & | ||
| 324 | 494 | BasicBlock::get_reachable_from() const | |
| 325 | 494 | { return reachable_from; } | |
| 326 | |||
| 327 | void | ||
| 328 | 116 | BasicBlock::add_reachable_from(size_t other_block) | |
| 329 | 116 | { reachable_from.push_back(other_block); } | |
| 330 | |||
| 331 | size_t | ||
| 332 | 730 | BasicBlock::size() const | |
| 333 | 730 | { return operations.size(); } | |
| 334 | |||
| 335 | void | ||
| 336 | 928 | BasicBlock::insert_operation(size_t position, Gyoji::owned<Operation> operation) | |
| 337 | { | ||
| 338 | 928 | operations.insert(operations.begin() + position, std::move(operation)); | |
| 339 | 928 | } | |
| 340 | |||
| 341 | |||
| 342 | ///////////////////////////////////// | ||
| 343 | // FunctionArgument | ||
| 344 | ///////////////////////////////////// | ||
| 345 | 524 | FunctionArgument::FunctionArgument( | |
| 346 | std::string & _name, | ||
| 347 | const Type * _type, | ||
| 348 | const Gyoji::context::SourceReference & _name_source_ref, | ||
| 349 | const Gyoji::context::SourceReference & _type_source_ref | ||
| 350 | 524 | ) | |
| 351 | 524 | : name(_name) | |
| 352 | 524 | , type(_type) | |
| 353 | 524 | , name_source_ref(_name_source_ref) | |
| 354 | 524 | , type_source_ref(_type_source_ref) | |
| 355 | 524 | {} | |
| 356 | |||
| 357 | 1308 | FunctionArgument::FunctionArgument(const FunctionArgument & _other) | |
| 358 | 1308 | : name(_other.name) | |
| 359 | 1308 | , type(_other.type) | |
| 360 | 1308 | , name_source_ref(_other.name_source_ref) | |
| 361 | 1308 | , type_source_ref(_other.type_source_ref) | |
| 362 | 1308 | {} | |
| 363 | |||
| 364 | 1832 | FunctionArgument::~FunctionArgument() | |
| 365 | 1832 | {} | |
| 366 | |||
| 367 | const std::string & | ||
| 368 | 3144 | FunctionArgument::get_name() const | |
| 369 | 3144 | { return name; } | |
| 370 | |||
| 371 | const Type* | ||
| 372 | 2096 | FunctionArgument::get_type() const | |
| 373 | 2096 | { return type; } | |
| 374 | |||
| 375 | const Gyoji::context::SourceReference & | ||
| 376 | ✗ | FunctionArgument::get_name_source_ref() const | |
| 377 | ✗ | { return name_source_ref; } | |
| 378 | |||
| 379 | const Gyoji::context::SourceReference & | ||
| 380 | ✗ | FunctionArgument::get_type_source_ref() const | |
| 381 | ✗ | { return type_source_ref; } | |
| 382 | ///////////////////////////////////// | ||
| 383 | // OperationVisitor | ||
| 384 | ///////////////////////////////////// | ||
| 385 | |||
| 386 | 810 | OperationVisitor::OperationVisitor() | |
| 387 | 810 | {} | |
| 388 | |||
| 389 | 810 | OperationVisitor::~OperationVisitor() | |
| 390 | 810 | {} | |
| 391 | |||
| 392 |