Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Compiler_Backend_C.H
Go to the documentation of this file.
1/*
2 Aleph_w
3
4 Data structures & Algorithms
5 version 2.0.0b
6 https://github.com/lrleon/Aleph-w
7
8 This file is part of Aleph-w library
9
10 Copyright (c) 2002-2026 Leandro Rabindranath Leon
11
12 Permission is hereby granted, free of charge, to any person obtaining a copy
13 of this software and associated documentation files (the "Software"), to deal
14 in the Software without restriction, including without limitation the rights
15 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 copies of the Software, and to permit persons to whom the Software is
17 furnished to do so, subject to the following conditions:
18
19 The above copyright notice and this permission notice shall be included in all
20 copies or substantial portions of the Software.
21
22 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28 SOFTWARE.
29*/
30
58#ifndef COMPILER_BACKEND_C_H
59#define COMPILER_BACKEND_C_H
60
61#include <cctype>
62#include <cstdlib>
63#include <sstream>
64#include <string>
65#include <string_view>
66#include <utility>
67
68#include <Compiler_IR_Model.H>
69#include <ah-errors.H>
70#include <tpl_dynArray.H>
71
72namespace Aleph {
75{
76 std::string module_name = "module";
78 = false;
80 = true;
81};
82
108
109namespace Compiler_Backend_C_Detail {
110inline std::string sanitize_identifier(std::string_view text)
111{
112 std::string result;
113 result.reserve(text.size() + 8);
114 for (const unsigned char ch : text)
115 {
116 if (std::isalnum(ch))
117 result.push_back(static_cast<char>(std::tolower(ch)));
118 else
119 result.push_back('_');
120 }
121
122 while (not result.empty() and result.front() == '_')
123 result.erase(result.begin());
124 while (not result.empty() and result.back() == '_')
125 result.pop_back();
126 while (result.find("__") != std::string::npos)
127 result.replace(result.find("__"), 2, "_");
128
129 if (result.empty())
130 result = "item";
131 if (std::isdigit(static_cast<unsigned char>(result.front())))
132 result.insert(result.begin(), '_');
133 return result;
134}
135
136inline std::string upper_identifier(std::string_view text)
137{
138 std::string result = sanitize_identifier(text);
139 for (char &ch : result)
140 ch = static_cast<char>(std::toupper(static_cast<unsigned char>(ch)));
141 return result;
142}
143
144inline std::string c_string_literal(std::string_view text)
145{
146 std::string result;
147 result.reserve(text.size() + 2);
148 result.push_back('"');
149 for (const char ch : text)
150 switch (ch)
151 {
152 case '\\':
153 result += "\\\\";
154 break;
155 case '"':
156 result += "\\\"";
157 break;
158 case '\n':
159 result += "\\n";
160 break;
161 case '\r':
162 result += "\\r";
163 break;
164 case '\t':
165 result += "\\t";
166 break;
167 default:
168 result.push_back(ch);
169 }
170 result.push_back('"');
171 return result;
172}
173
174inline std::string safe_comment_text(std::string text)
175{
176 while (text.find("*/") != std::string::npos)
177 text.replace(text.find("*/"), 2, "* /");
178 return text;
179}
180
181inline bool parse_integer_literal(const std::string &text, long long &value) noexcept
182{
183 if (text.empty())
184 return false;
185
186 char *end = nullptr;
187 value = std::strtoll(text.c_str(), &end, 10);
188 return end != nullptr and *end == '\0';
189}
190
191inline size_t count_parameters(const Compiler_IR_Function &function) noexcept
192{
193 size_t count = 0;
194 for (size_t i = 0; i < function.local_slots.size(); ++i)
195 if (function.local_slots.access(i).kind == Compiler_IR_Slot_Kind::Parameter)
196 ++count;
197 return count;
198}
199
200inline std::string token_name(const Compiler_Operator_Kind kind) noexcept
201{
202 return compiler_operator_name(kind);
203}
204
205inline std::string value_name(const Compiler_IR_Value_Id id)
206{
207 return "v" + std::to_string(id);
208}
209
210inline std::string local_name(const Compiler_IR_Local_Slot_Id id)
211{
212 return "s" + std::to_string(id);
213}
214
215inline std::string global_name(const Compiler_IR_Global_Slot_Id id)
216{
217 return "g" + std::to_string(id);
218}
219
220inline std::string block_label(const size_t id)
221{
222 return "B" + std::to_string(id);
223}
224
225inline std::string indent(const size_t count)
226{
227 return std::string(count, ' ');
228}
229} // namespace Compiler_Backend_C_Detail
230
233{
235
237 {
238 std::string prefix;
239 std::string upper_prefix;
240 std::string tag_enum_name;
241 std::string value_type_name;
248 std::string tag_name_symbol;
249 std::string panic_symbol;
254 std::string equal_symbol;
255 std::string call_symbol;
257 std::string make_unit_symbol;
258 std::string make_bool_symbol;
259 std::string make_int_symbol;
261 std::string make_char_symbol;
263 std::string top_level_symbol;
264 std::string tag_invalid_name;
265 std::string tag_unit_name;
266 std::string tag_bool_name;
267 std::string tag_int_name;
268 std::string tag_string_name;
269 std::string tag_char_name;
270 std::string tag_function_name;
271 };
272
274 {
276 const Compiler_IR_Module *module_ = nullptr;
280
281 void fail(const std::string &message)
282 {
283 emission_.valid = false;
285 }
286
287 void warn(const std::string &message)
288 {
290 }
291
292 [[nodiscard]] std::string type_comment(const Compiler_Type_Id type_id) const
293 {
294 if (types_ == nullptr or type_id == 0)
295 return "";
296 return types_->to_string(type_id);
297 }
298
300 {
301 names_.prefix = "alephc_"
303 ? std::string("module")
307 names_.value_type_name = names_.prefix + "_value";
308 names_.function_type_name = names_.prefix + "_function";
311 names_.module_init_symbol = names_.prefix + "_module_init";
312 names_.dump_globals_symbol = names_.prefix + "_dump_globals";
313 names_.print_value_symbol = names_.prefix + "_print_value";
314 names_.tag_name_symbol = names_.prefix + "_tag_name";
315 names_.panic_symbol = names_.prefix + "_panic";
316 names_.require_assigned_symbol = names_.prefix + "_require_assigned";
317 names_.require_int_symbol = names_.prefix + "_require_int";
318 names_.require_bool_symbol = names_.prefix + "_require_bool";
319 names_.require_function_symbol = names_.prefix + "_require_function";
320 names_.equal_symbol = names_.prefix + "_equal";
321 names_.call_symbol = names_.prefix + "_call";
322 names_.make_invalid_symbol = names_.prefix + "_make_invalid";
323 names_.make_unit_symbol = names_.prefix + "_make_unit";
324 names_.make_bool_symbol = names_.prefix + "_make_bool";
325 names_.make_int_symbol = names_.prefix + "_make_int";
326 names_.make_string_symbol = names_.prefix + "_make_string";
327 names_.make_char_symbol = names_.prefix + "_make_char";
328 names_.make_function_symbol = names_.prefix + "_make_function";
329 names_.top_level_symbol = names_.prefix + "_top_level";
330 names_.tag_invalid_name = names_.upper_prefix + "_TAG_INVALID";
331 names_.tag_unit_name = names_.upper_prefix + "_TAG_UNIT";
332 names_.tag_bool_name = names_.upper_prefix + "_TAG_BOOL";
333 names_.tag_int_name = names_.upper_prefix + "_TAG_INT";
334 names_.tag_string_name = names_.upper_prefix + "_TAG_STRING";
335 names_.tag_char_name = names_.upper_prefix + "_TAG_CHAR";
336 names_.tag_function_name = names_.upper_prefix + "_TAG_FUNCTION";
337
345
346 for (size_t i = 0; i < module_->functions.size(); ++i)
347 {
348 const auto &function = *module_->functions.access(i);
349 const std::string symbol = names_.prefix + "_f" + std::to_string(i) + "_"
352 emission_.function_descriptor_symbols.append(symbol + "_descriptor");
353 }
354 }
355
357 {
358 const auto [valid, errors, warnings] = validate_ir_module(*module_);
359 if (not valid)
360 for (size_t i = 0; i < errors.size(); ++i)
361 fail(errors.access(i));
362 for (size_t i = 0; i < warnings.size(); ++i)
363 warn(warnings.access(i));
364
365 for (size_t i = 0; i < module_->functions.size(); ++i)
366 if (module_->functions.access(i)->id != i)
367 fail("C backend requires dense zero-based function ids; function '"
368 + module_->functions.access(i)->name + "' has id "
369 + std::to_string(module_->functions.access(i)->id) + " but its module index is "
370 + std::to_string(i));
371 }
372
373 [[nodiscard]] std::string function_symbol(const size_t index) const
374 {
375 return emission_.function_symbols.access(index);
376 }
377
378 [[nodiscard]] std::string function_descriptor_symbol(const size_t index) const
379 {
381 }
382
384 std::string &expression,
385 std::string &error) const
386 {
387 if (inst.text == "unit")
388 {
390 return true;
391 }
392
393 if (inst.text == "true" or inst.text == "false")
394 {
396 + std::string(inst.text == "true" ? "true" : "false") + ")";
397 return true;
398 }
399
400 long long integer_value = 0;
402 {
403 expression = names_.make_int_symbol + "(" + std::to_string(integer_value) + "LL)";
404 return true;
405 }
406
407 if (inst.text.size() >= 2 and inst.text.front() == '"' and inst.text.back() == '"')
408 {
409 expression = names_.make_string_symbol + "(" + inst.text + ")";
410 return true;
411 }
412
413 if (inst.text.size() >= 3 and inst.text.front() == '\'' and inst.text.back() == '\'')
414 {
415 expression = names_.make_char_symbol + "(" + inst.text + ")";
416 return true;
417 }
418
419 error = "C backend does not know how to emit constant literal '" + inst.text + "'";
420 return false;
421 }
422
423 void emit_runtime_prelude(std::ostream &out) const
424 {
425 out << "#include <stdbool.h>\n"
426 << "#include <stddef.h>\n"
427 << "#include <stdio.h>\n"
428 << "#include <stdlib.h>\n"
429 << "#include <string.h>\n\n"
430 << "typedef struct " << names_.value_type_name << " " << names_.value_type_name << ";\n"
431 << "typedef struct " << names_.function_type_name << " " << names_.function_type_name
432 << ";\n"
433 << "typedef struct " << names_.module_struct_name << " " << names_.module_struct_name
434 << ";\n\n"
435 << "typedef enum " << names_.tag_enum_name << "\n"
436 << "{\n"
437 << " " << names_.tag_invalid_name << " = 0,\n"
438 << " " << names_.tag_unit_name << ",\n"
439 << " " << names_.tag_bool_name << ",\n"
440 << " " << names_.tag_int_name << ",\n"
441 << " " << names_.tag_string_name << ",\n"
442 << " " << names_.tag_char_name << ",\n"
443 << " " << names_.tag_function_name << "\n"
444 << "} " << names_.tag_enum_name << ";\n\n"
445 << "struct " << names_.value_type_name << "\n"
446 << "{\n"
447 << " " << names_.tag_enum_name << " tag;\n"
448 << " union\n"
449 << " {\n"
450 << " bool boolean;\n"
451 << " long long integer;\n"
452 << " const char * string;\n"
453 << " char character;\n"
454 << " const " << names_.function_type_name << " * function;\n"
455 << " } as;\n"
456 << "};\n\n"
457 << "typedef " << names_.value_type_name << " (*" << names_.function_pointer_type_name
458 << ")(" << names_.module_struct_name << " * module,\n"
460 << " * args,\n"
461 << Compiler_Backend_C_Detail::indent(52) << "size_t argc);\n\n"
462 << "struct " << names_.function_type_name << "\n"
463 << "{\n"
464 << " " << names_.function_pointer_type_name << " pointer;\n"
465 << " size_t arity;\n"
466 << " const char * name;\n"
467 << "};\n\n"
468 << "static const char *\n"
469 << names_.tag_name_symbol << "(" << names_.tag_enum_name << " tag)\n"
470 << "{\n"
471 << " switch (tag)\n"
472 << " {\n"
473 << " case " << names_.tag_invalid_name << ": return \"Invalid\";\n"
474 << " case " << names_.tag_unit_name << ": return \"Unit\";\n"
475 << " case " << names_.tag_bool_name << ": return \"Bool\";\n"
476 << " case " << names_.tag_int_name << ": return \"Int\";\n"
477 << " case " << names_.tag_string_name << ": return \"String\";\n"
478 << " case " << names_.tag_char_name << ": return \"Char\";\n"
479 << " case " << names_.tag_function_name << ": return \"Function\";\n"
480 << " }\n"
481 << " return \"Unknown\";\n"
482 << "}\n\n"
483 << "static void\n"
484 << names_.panic_symbol << "(const char * message)\n"
485 << "{\n"
486 << " fprintf(stderr, \"[" << names_.prefix << "] %s\\n\", message);\n"
487 << " exit(1);\n"
488 << "}\n\n"
489 << "static " << names_.value_type_name << "\n"
490 << names_.make_invalid_symbol << "(void)\n"
491 << "{\n"
492 << " " << names_.value_type_name << " value;\n"
493 << " value.tag = " << names_.tag_invalid_name << ";\n"
494 << " value.as.integer = 0;\n"
495 << " return value;\n"
496 << "}\n\n"
497 << "static " << names_.value_type_name << "\n"
498 << names_.make_unit_symbol << "(void)\n"
499 << "{\n"
500 << " " << names_.value_type_name << " value;\n"
501 << " value.tag = " << names_.tag_unit_name << ";\n"
502 << " value.as.integer = 0;\n"
503 << " return value;\n"
504 << "}\n\n"
505 << "static " << names_.value_type_name << "\n"
506 << names_.make_bool_symbol << "(bool value_in)\n"
507 << "{\n"
508 << " " << names_.value_type_name << " value;\n"
509 << " value.tag = " << names_.tag_bool_name << ";\n"
510 << " value.as.boolean = value_in;\n"
511 << " return value;\n"
512 << "}\n\n"
513 << "static " << names_.value_type_name << "\n"
514 << names_.make_int_symbol << "(long long value_in)\n"
515 << "{\n"
516 << " " << names_.value_type_name << " value;\n"
517 << " value.tag = " << names_.tag_int_name << ";\n"
518 << " value.as.integer = value_in;\n"
519 << " return value;\n"
520 << "}\n\n"
521 << "static " << names_.value_type_name << "\n"
522 << names_.make_string_symbol << "(const char * value_in)\n"
523 << "{\n"
524 << " " << names_.value_type_name << " value;\n"
525 << " value.tag = " << names_.tag_string_name << ";\n"
526 << " value.as.string = value_in;\n"
527 << " return value;\n"
528 << "}\n\n"
529 << "static " << names_.value_type_name << "\n"
530 << names_.make_char_symbol << "(char value_in)\n"
531 << "{\n"
532 << " " << names_.value_type_name << " value;\n"
533 << " value.tag = " << names_.tag_char_name << ";\n"
534 << " value.as.character = value_in;\n"
535 << " return value;\n"
536 << "}\n\n"
537 << "static " << names_.value_type_name << "\n"
538 << names_.make_function_symbol << "(const " << names_.function_type_name << " * function)\n"
539 << "{\n"
540 << " " << names_.value_type_name << " value;\n"
541 << " value.tag = " << names_.tag_function_name << ";\n"
542 << " value.as.function = function;\n"
543 << " return value;\n"
544 << "}\n\n"
545 << "static " << names_.value_type_name << "\n"
546 << names_.require_assigned_symbol << "(" << names_.value_type_name << " value,\n"
547 << Compiler_Backend_C_Detail::indent(37) << "const char * context)\n"
548 << "{\n"
549 << " if (value.tag == " << names_.tag_invalid_name << ")\n"
550 << " {\n"
551 << " fprintf(stderr, \"[" << names_.prefix
552 << "] %s uses an uninitialized value\\n\", context);\n"
553 << " exit(1);\n"
554 << " }\n"
555 << " return value;\n"
556 << "}\n\n"
557 << "static long long\n"
558 << names_.require_int_symbol << "(" << names_.value_type_name << " value,\n"
559 << Compiler_Backend_C_Detail::indent(32) << "const char * context)\n"
560 << "{\n"
561 << " value = " << names_.require_assigned_symbol << "(value, context);\n"
562 << " if (value.tag != " << names_.tag_int_name << ")\n"
563 << " {\n"
564 << " fprintf(stderr, \"[" << names_.prefix
565 << "] %s expects Int but received %s\\n\",\n"
566 << Compiler_Backend_C_Detail::indent(14) << "context,\n"
567 << Compiler_Backend_C_Detail::indent(14) << names_.tag_name_symbol << "(value.tag));\n"
568 << " exit(1);\n"
569 << " }\n"
570 << " return value.as.integer;\n"
571 << "}\n\n"
572 << "static bool\n"
573 << names_.require_bool_symbol << "(" << names_.value_type_name << " value,\n"
574 << Compiler_Backend_C_Detail::indent(33) << "const char * context)\n"
575 << "{\n"
576 << " value = " << names_.require_assigned_symbol << "(value, context);\n"
577 << " if (value.tag != " << names_.tag_bool_name << ")\n"
578 << " {\n"
579 << " fprintf(stderr, \"[" << names_.prefix
580 << "] %s expects Bool but received %s\\n\",\n"
581 << Compiler_Backend_C_Detail::indent(14) << "context,\n"
582 << Compiler_Backend_C_Detail::indent(14) << names_.tag_name_symbol << "(value.tag));\n"
583 << " exit(1);\n"
584 << " }\n"
585 << " return value.as.boolean;\n"
586 << "}\n\n"
587 << "static const " << names_.function_type_name << " *\n"
588 << names_.require_function_symbol << "(" << names_.value_type_name << " value,\n"
589 << Compiler_Backend_C_Detail::indent(37) << "const char * context)\n"
590 << "{\n"
591 << " value = " << names_.require_assigned_symbol << "(value, context);\n"
592 << " if (value.tag != " << names_.tag_function_name << ")\n"
593 << " {\n"
594 << " fprintf(stderr, \"[" << names_.prefix
595 << "] %s expects Function but received %s\\n\",\n"
596 << Compiler_Backend_C_Detail::indent(14) << "context,\n"
597 << Compiler_Backend_C_Detail::indent(14) << names_.tag_name_symbol << "(value.tag));\n"
598 << " exit(1);\n"
599 << " }\n"
600 << " return value.as.function;\n"
601 << "}\n\n"
602 << "static bool\n"
603 << names_.equal_symbol << "(" << names_.value_type_name << " lhs,\n"
605 << "{\n"
606 << " lhs = " << names_.require_assigned_symbol << "(lhs, \"equality lhs\");\n"
607 << " rhs = " << names_.require_assigned_symbol << "(rhs, \"equality rhs\");\n"
608 << " if (lhs.tag != rhs.tag)\n"
609 << " return false;\n"
610 << " switch (lhs.tag)\n"
611 << " {\n"
612 << " case " << names_.tag_invalid_name << ":\n"
613 << " case " << names_.tag_unit_name << ":\n"
614 << " return true;\n"
615 << " case " << names_.tag_bool_name << ":\n"
616 << " return lhs.as.boolean == rhs.as.boolean;\n"
617 << " case " << names_.tag_int_name << ":\n"
618 << " return lhs.as.integer == rhs.as.integer;\n"
619 << " case " << names_.tag_string_name << ":\n"
620 << " return strcmp(lhs.as.string, rhs.as.string) == 0;\n"
621 << " case " << names_.tag_char_name << ":\n"
622 << " return lhs.as.character == rhs.as.character;\n"
623 << " case " << names_.tag_function_name << ":\n"
624 << " return lhs.as.function == rhs.as.function;\n"
625 << " }\n"
626 << " return false;\n"
627 << "}\n\n"
628 << "static " << names_.value_type_name << "\n"
629 << names_.call_symbol << "(" << names_.module_struct_name << " * module,\n"
632 << " * args,\n"
633 << Compiler_Backend_C_Detail::indent(19) << "size_t argc)\n"
634 << "{\n"
635 << " const " << names_.function_type_name << " * function\n"
636 << " = " << names_.require_function_symbol << "(callee, \"call callee\");\n"
637 << " if (function->arity != argc)\n"
638 << " {\n"
639 << " fprintf(stderr, \"[" << names_.prefix
640 << "] function %s expects %zu arguments but received %zu\\n\",\n"
641 << Compiler_Backend_C_Detail::indent(14) << "function->name,\n"
642 << Compiler_Backend_C_Detail::indent(14) << "function->arity,\n"
643 << Compiler_Backend_C_Detail::indent(14) << "argc);\n"
644 << " exit(1);\n"
645 << " }\n"
646 << " return function->pointer(module, args, argc);\n"
647 << "}\n\n"
648 << "static void\n"
649 << names_.print_value_symbol << "(FILE * out,\n"
651 << "{\n"
652 << " value = " << names_.require_assigned_symbol << "(value, \"print value\");\n"
653 << " switch (value.tag)\n"
654 << " {\n"
655 << " case " << names_.tag_invalid_name << ":\n"
656 << " fputs(\"Invalid\", out);\n"
657 << " return;\n"
658 << " case " << names_.tag_unit_name << ":\n"
659 << " fputs(\"Unit\", out);\n"
660 << " return;\n"
661 << " case " << names_.tag_bool_name << ":\n"
662 << " fputs(value.as.boolean ? \"Bool(true)\" : \"Bool(false)\", out);\n"
663 << " return;\n"
664 << " case " << names_.tag_int_name << ":\n"
665 << " fprintf(out, \"Int(%lld)\", value.as.integer);\n"
666 << " return;\n"
667 << " case " << names_.tag_string_name << ":\n"
668 << " fprintf(out, \"String(\\\"%s\\\")\", value.as.string);\n"
669 << " return;\n"
670 << " case " << names_.tag_char_name << ":\n"
671 << " fprintf(out, \"Char('%c')\", value.as.character);\n"
672 << " return;\n"
673 << " case " << names_.tag_function_name << ":\n"
674 << " fprintf(out, \"Function(%s)\", value.as.function->name);\n"
675 << " return;\n"
676 << " }\n"
677 << "}\n\n";
678 }
679
680 void emit_module_layout(std::ostream &out) const
681 {
682 const size_t global_count = module_->global_slots.size();
683 out << "enum { " << names_.upper_prefix << "_GLOBAL_COUNT = " << global_count << " };\n\n";
684
685 out << "struct " << names_.module_struct_name << "\n"
686 << "{\n";
687 if (global_count == 0)
688 out << " " << names_.value_type_name << " unused_global;\n";
689 else
690 out << " " << names_.value_type_name << " globals[" << names_.upper_prefix
691 << "_GLOBAL_COUNT];\n";
692 out << "};\n\n";
693
694 out << "static void\n"
695 << names_.module_init_symbol << "(" << names_.module_struct_name << " * module)\n"
696 << "{\n";
697 if (global_count == 0)
698 out << " (void) module;\n";
699 else
700 out << " for (size_t i = 0; i < " << names_.upper_prefix << "_GLOBAL_COUNT; ++i)\n"
701 << " module->globals[i] = " << names_.make_invalid_symbol << "();\n";
702 out << "}\n\n";
703
704 out << "static void\n"
705 << names_.dump_globals_symbol << "(FILE * out,\n"
707 << " * module)\n"
708 << "{\n"
709 << " fputs(\"Globals\\n\", out);\n";
710 if (global_count == 0)
711 out << " fputs(\" <none>\\n\", out);\n";
712 else
713 for (size_t i = 0; i < module_->global_slots.size(); ++i)
714 {
715 const auto &slot = module_->global_slots.access(i);
716 out << " fputs(\" g" << slot.id << " "
717 << Compiler_Backend_C_Detail::safe_comment_text(slot.name) << " = \", out);\n"
718 << " " << names_.print_value_symbol << "(out, module->globals[" << i << "]);\n"
719 << " fputc('\\n', out);\n";
720 }
721 out << "}\n\n";
722 }
723
724 void emit_prototypes(std::ostream &out) const
725 {
726 for (size_t i = 0; i < module_->functions.size(); ++i)
727 out << "static " << names_.value_type_name << "\n"
728 << function_symbol(i) << "(" << names_.module_struct_name << " * module,\n"
730 << names_.value_type_name << " * args,\n"
731 << Compiler_Backend_C_Detail::indent(function_symbol(i).size() + 8) << "size_t argc);\n"
732 << "static const " << names_.function_type_name << " "
733 << function_descriptor_symbol(i) << ";\n\n";
734
735 if (module_->top_level != nullptr)
736 out << "static " << names_.value_type_name << "\n"
737 << names_.top_level_symbol << "(" << names_.module_struct_name << " * module,\n"
739 << names_.value_type_name << " * args,\n"
741 << "size_t argc);\n\n";
742 }
743
744 void emit_function_signature(std::ostream &out, const std::string &symbol) const
745 {
746 out << "static " << names_.value_type_name << "\n"
747 << symbol << "(" << names_.module_struct_name << " * module,\n"
748 << Compiler_Backend_C_Detail::indent(symbol.size() + 8) << "const "
749 << names_.value_type_name << " * args,\n"
750 << Compiler_Backend_C_Detail::indent(symbol.size() + 8) << "size_t argc)\n";
751 }
752
753 void emit_slot_declarations(std::ostream &out, const Compiler_IR_Function &function) const
754 {
755 for (size_t i = 0; i < function.local_slots.size(); ++i)
756 {
757 const auto &slot = function.local_slots.access(i);
758 out << " " << names_.value_type_name << " "
760 << names_.make_invalid_symbol << "();";
762 {
763 out << " /* " << compiler_ir_slot_kind_name(slot.kind) << ' '
765 const auto type_text = type_comment(slot.type_id);
766 if (not type_text.empty())
768 out << " */";
769 }
770 out << '\n';
771 }
772 }
773
774 void emit_value_declarations(std::ostream &out, const Compiler_IR_Function &function) const
775 {
776 for (size_t value_id = 1; value_id <= function.next_value_id; ++value_id)
777 out << " " << names_.value_type_name << " "
778 << Compiler_Backend_C_Detail::value_name(value_id) << " = "
779 << names_.make_invalid_symbol << "();\n";
780 }
781
782 void emit_parameter_bindings(std::ostream &out, const Compiler_IR_Function &function) const
783 {
784 const size_t arity = Compiler_Backend_C_Detail::count_parameters(function);
785 out << " if (argc != " << arity << "u)\n"
786 << " {\n"
787 << " fprintf(stderr, \"[" << names_.prefix << "] function "
789 << " expects %zu arguments but received %zu\\n\",\n"
790 << " (size_t) " << arity << "u,\n"
791 << " argc);\n"
792 << " exit(1);\n"
793 << " }\n";
794
795 size_t parameter_index = 0;
796 for (size_t i = 0; i < function.local_slots.size(); ++i)
797 {
798 const auto &slot = function.local_slots.access(i);
800 continue;
801
802 out << " " << Compiler_Backend_C_Detail::local_name(slot.id) << " = args["
803 << parameter_index << "];\n";
805 }
806 }
807
809 {
811 return;
812
813 out << " /* ";
814 if (inst.result_id != 0)
815 out << Compiler_Backend_C_Detail::value_name(inst.result_id) << " = ";
823 out << "(f" << inst.function_id << ')';
824 out << " */\n";
825 }
826
827 void emit_instruction(std::ostream &out,
829 const Compiler_IR_Function &function)
830 {
831 (void) function;
832 const auto value = [](const Compiler_IR_Value_Id id)
833 {
835 };
836 const auto slot = [](const Compiler_IR_Local_Slot_Id id)
837 {
839 };
840
842
843 switch (inst.kind)
844 {
846 {
847 std::string expression;
848 std::string error;
850 {
851 fail(error);
852 return;
853 }
854
855 out << " " << value(inst.result_id) << " = " << expression << ";\n";
856 break;
857 }
858
860 if (inst.global_slot_id != compiler_ir_invalid_id())
861 out << " " << value(inst.result_id) << " = " << names_.require_assigned_symbol
862 << "(module->globals[" << inst.global_slot_id << "], "
864 "load " + Compiler_Backend_C_Detail::global_name(inst.global_slot_id))
865 << ");\n";
866 else
867 out << " " << value(inst.result_id) << " = " << names_.require_assigned_symbol << "("
868 << slot(inst.local_slot_id) << ", "
870 "load " + Compiler_Backend_C_Detail::local_name(inst.local_slot_id))
871 << ");\n";
872 break;
873
875 if (inst.operands.is_empty())
876 {
877 fail("C backend cannot emit Store without one operand");
878 return;
879 }
880
881 if (inst.global_slot_id != compiler_ir_invalid_id())
882 out << " module->globals[" << inst.global_slot_id
883 << "] = " << names_.require_assigned_symbol << "(" << value(inst.operands.access(0))
884 << ", "
886 + value(inst.operands.access(0)))
887 << ");\n";
888 else
889 out << " " << slot(inst.local_slot_id) << " = " << names_.require_assigned_symbol
890 << "(" << value(inst.operands.access(0)) << ", "
892 + value(inst.operands.access(0)))
893 << ");\n";
894 break;
895
897 if (inst.operands.is_empty())
898 {
899 fail("C backend cannot emit Unary without one operand");
900 return;
901 }
902
903 switch (inst.op)
904 {
906 out << " " << value(inst.result_id) << " = " << names_.make_int_symbol << "(-"
907 << names_.require_int_symbol << "(" << value(inst.operands.access(0)) << ", "
908 << Compiler_Backend_C_Detail::c_string_literal("unary minus") << "));\n";
909 break;
910
912 out << " " << value(inst.result_id) << " = " << names_.make_bool_symbol << "(!"
913 << names_.require_bool_symbol << "(" << value(inst.operands.access(0)) << ", "
914 << Compiler_Backend_C_Detail::c_string_literal("logical not") << "));\n";
915 break;
916
918 out << " " << value(inst.result_id) << " = " << names_.make_int_symbol << "(~"
919 << names_.require_int_symbol << "(" << value(inst.operands.access(0)) << ", "
920 << Compiler_Backend_C_Detail::c_string_literal("bitwise not") << "));\n";
921 break;
922
923 default:
924 fail("C backend does not support unary operator '"
926 break;
927 }
928 break;
929
931 if (inst.operands.size() < 2)
932 {
933 fail("C backend cannot emit Binary without two operands");
934 return;
935 }
936
937 switch (inst.op)
938 {
945 {
946 const char *op_text = inst.op == Compiler_Operator_Kind::Plus ? "+"
951 : "^";
952 out << " {\n"
953 << " long long lhs_value = " << names_.require_int_symbol << "("
954 << value(inst.operands.access(0)) << ", "
956 + std::string(op_text))
957 << ");\n"
958 << " long long rhs_value = " << names_.require_int_symbol << "("
959 << value(inst.operands.access(1)) << ", "
961 + std::string(op_text))
962 << ");\n"
963 << " " << value(inst.result_id) << " = " << names_.make_int_symbol
964 << "(lhs_value " << op_text << " rhs_value);\n"
965 << " }\n";
966 break;
967 }
968
971 {
972 const char *op_text = inst.op == Compiler_Operator_Kind::Slash ? "/" : "%";
973 const char *message = inst.op == Compiler_Operator_Kind::Slash ? "division by zero"
974 : "modulo by zero";
975 out << " {\n"
976 << " long long lhs_value = " << names_.require_int_symbol << "("
977 << value(inst.operands.access(0)) << ", "
979 + std::string(op_text))
980 << ");\n"
981 << " long long rhs_value = " << names_.require_int_symbol << "("
982 << value(inst.operands.access(1)) << ", "
984 + std::string(op_text))
985 << ");\n"
986 << " if (rhs_value == 0LL)\n"
987 << " " << names_.panic_symbol << "("
989 << " " << value(inst.result_id) << " = " << names_.make_int_symbol
990 << "(lhs_value " << op_text << " rhs_value);\n"
991 << " }\n";
992 break;
993 }
994
999 {
1000 const char *op_text = inst.op == Compiler_Operator_Kind::Less ? "<"
1003 : ">=";
1004 out << " {\n"
1005 << " long long lhs_value = " << names_.require_int_symbol << "("
1006 << value(inst.operands.access(0)) << ", "
1008 + std::string(op_text))
1009 << ");\n"
1010 << " long long rhs_value = " << names_.require_int_symbol << "("
1011 << value(inst.operands.access(1)) << ", "
1013 + std::string(op_text))
1014 << ");\n"
1015 << " " << value(inst.result_id) << " = " << names_.make_bool_symbol
1016 << "(lhs_value " << op_text << " rhs_value);\n"
1017 << " }\n";
1018 break;
1019 }
1020
1023 {
1024 const char *op_text = inst.op == Compiler_Operator_Kind::AndAnd ? "&&" : "||";
1025 out << " {\n"
1026 << " bool lhs_value = " << names_.require_bool_symbol << "("
1027 << value(inst.operands.access(0)) << ", "
1029 + std::string(op_text))
1030 << ");\n"
1031 << " bool rhs_value = " << names_.require_bool_symbol << "("
1032 << value(inst.operands.access(1)) << ", "
1034 + std::string(op_text))
1035 << ");\n"
1036 << " " << value(inst.result_id) << " = " << names_.make_bool_symbol
1037 << "(lhs_value " << op_text << " rhs_value);\n"
1038 << " }\n";
1039 break;
1040 }
1041
1044 out << " " << value(inst.result_id) << " = " << names_.make_bool_symbol << "("
1045 << (inst.op == Compiler_Operator_Kind::NotEq ? "!" : "") << names_.equal_symbol
1046 << "(" << value(inst.operands.access(0)) << ", " << value(inst.operands.access(1))
1047 << "));\n";
1048 break;
1049
1050 default:
1051 fail("C backend does not support binary operator '"
1053 break;
1054 }
1055 break;
1056
1058 if (inst.operands.is_empty())
1059 {
1060 fail("C backend cannot emit Call without a callee operand");
1061 return;
1062 }
1063
1064 out << " {\n";
1065 if (inst.operands.size() == 1)
1066 out << " " << value(inst.result_id) << " = " << names_.call_symbol << "(module, "
1067 << value(inst.operands.access(0)) << ", NULL, 0u);\n";
1068 else
1069 {
1070 out << " const " << names_.value_type_name << " call_args[] =\n"
1071 << " {\n";
1072 for (size_t i = 1; i < inst.operands.size(); ++i)
1073 out << " " << names_.require_assigned_symbol << "("
1074 << value(inst.operands.access(i)) << ", "
1076 + std::to_string(i - 1))
1077 << ")" << (i + 1 < inst.operands.size() ? "," : "") << '\n';
1078 out << " };\n"
1079 << " " << value(inst.result_id) << " = " << names_.call_symbol << "(module, "
1080 << value(inst.operands.access(0)) << ", call_args, " << (inst.operands.size() - 1)
1081 << "u);\n";
1082 }
1083 out << " }\n";
1084 break;
1085
1087 out << " " << value(inst.result_id) << " = " << names_.make_function_symbol << "(&"
1088 << function_descriptor_symbol(inst.function_id) << ");\n";
1089 break;
1090 }
1091 }
1092
1093 void emit_terminator(std::ostream &out,
1094 const Compiler_IR_Block &block,
1095 const Compiler_IR_Function &function)
1096 {
1098 out << " /* Terminator: " << compiler_ir_terminator_kind_name(block.terminator.kind)
1099 << " */\n";
1100
1101 switch (block.terminator.kind)
1102 {
1104 out << " goto " << names_.prefix << '_'
1106 << ";\n";
1107 break;
1108
1110 out << " if (" << names_.require_bool_symbol << "("
1112 << Compiler_Backend_C_Detail::c_string_literal("branch condition") << "))\n"
1113 << " goto " << names_.prefix << '_'
1115 << ";\n"
1116 << " goto " << names_.prefix << '_'
1118 << ";\n";
1119 break;
1120
1122 out << " return " << names_.require_assigned_symbol << "("
1124 << Compiler_Backend_C_Detail::c_string_literal("return value") << ");\n";
1125 break;
1126
1128 out << " return " << names_.make_unit_symbol << "();\n";
1129 break;
1130
1132 out << " " << names_.panic_symbol << "("
1134 "entered unreachable block in function " + function.name)
1135 << ");\n"
1136 << " return " << names_.make_invalid_symbol << "();\n";
1137 break;
1138
1140 fail("C backend cannot emit unterminated block "
1142 break;
1143 }
1144 }
1145
1146 void emit_function_body(std::ostream &out,
1147 const Compiler_IR_Function &function,
1148 const std::string &symbol)
1149 {
1151 {
1153 const auto type_text = type_comment(function.type_id);
1154 if (not type_text.empty())
1156 out << " */\n";
1157 }
1158
1160 out << "{\n"
1161 << " (void) module;\n";
1162 emit_slot_declarations(out, function);
1163 emit_value_declarations(out, function);
1164 emit_parameter_bindings(out, function);
1165 out << " goto " << names_.prefix << '_'
1167
1168 for (size_t i = 0; i < function.blocks.size(); ++i)
1169 {
1170 const auto &block = function.blocks.access(i);
1171 out << names_.prefix << '_' << Compiler_Backend_C_Detail::block_label(block.id) << ":\n";
1173 out << " /* Block " << Compiler_Backend_C_Detail::block_label(block.id) << ": "
1175 for (size_t inst_index = 0; inst_index < block.instructions.size(); ++inst_index)
1176 emit_instruction(out, block.instructions.access(inst_index), function);
1177 emit_terminator(out, block, function);
1178 out << '\n';
1179 }
1180
1181 out << "}\n\n";
1182 }
1183
1184 void emit_function(const size_t index, std::ostream &out)
1185 {
1186 emit_function_body(out, *module_->functions.access(index), function_symbol(index));
1187 }
1188
1189 void emit_top_level(std::ostream &out)
1190 {
1192 }
1193
1194 void emit_function_descriptors(std::ostream &out) const
1195 {
1196 for (size_t i = 0; i < module_->functions.size(); ++i)
1197 {
1198 const auto &function = *module_->functions.access(i);
1199 out << "static const " << names_.function_type_name << " "
1200 << function_descriptor_symbol(i) << " =\n"
1201 << "{\n"
1202 << " " << function_symbol(i) << ",\n"
1203 << " " << Compiler_Backend_C_Detail::count_parameters(function) << "u,\n"
1204 << " " << Compiler_Backend_C_Detail::c_string_literal(function.name) << "\n"
1205 << "};\n\n";
1206 }
1207 }
1208
1209 void emit_main(std::ostream &out)
1210 {
1211 if (not options_->emit_main)
1212 return;
1213
1214 if (module_->top_level == nullptr)
1215 {
1216 warn("C backend was asked to emit main(), but the IR module has no top-level body");
1217 return;
1218 }
1219
1220 out << "int\n"
1221 << "main(void)\n"
1222 << "{\n"
1223 << " " << names_.module_struct_name << " module;\n"
1224 << " " << names_.module_init_symbol << "(&module);\n"
1225 << " " << names_.value_type_name << " result = " << names_.top_level_symbol
1226 << "(&module, NULL, 0u);\n"
1227 << " fputs(\"Result = \", stdout);\n"
1228 << " " << names_.print_value_symbol << "(stdout, result);\n"
1229 << " fputc('\\n', stdout);\n"
1230 << " " << names_.dump_globals_symbol << "(stdout, &module);\n"
1231 << " return 0;\n"
1232 << "}\n";
1233 }
1234
1235 public:
1244
1247 {
1249 if (not emission_.valid)
1250 return emission_;
1251
1252 std::ostringstream out;
1254 out << "/* Generated by Compiler_Backend_C.H from explicit IR. */\n\n";
1255
1259 for (size_t i = 0; i < module_->functions.size(); ++i)
1260 emit_function(i, out);
1261 if (module_->top_level != nullptr)
1264 emit_main(out);
1265
1266 if (emission_.valid)
1267 emission_.source = out.str();
1268 return emission_;
1269 }
1270 };
1271
1272public:
1277
1286 const Compiler_Type_Context *types
1287 = nullptr) const
1288 {
1290 if (module == nullptr)
1291 {
1292 emission.valid = false;
1293 emission.errors.append("Compiler_C_Backend::emit_module(): null IR module");
1294 return emission;
1295 }
1296
1297 return Emitter(options, *module, types).run();
1298 }
1299};
1300
1304 = {},
1305 const Compiler_Type_Context *types = nullptr)
1306{
1307 return Compiler_C_Backend(options).emit_module(module, types);
1308}
1309} // namespace Aleph
1310
1311#endif
Reusable explicit-value IR model, validation, and deterministic dumps.
Exception handling system with formatted messages for Aleph-w.
size_t size_t int32_t value
Definition ca-c-api.h:116
size_t size_t int32_t * out
Definition ca-c-api.h:120
Emitter(const Compiler_C_Backend_Options &options_in, const Compiler_IR_Module &module_in, const Compiler_Type_Context *types_in)
Builds an emitter over one module and one option set.
const Compiler_IR_Module * module_
void emit_instruction(std::ostream &out, const Compiler_IR_Instruction &inst, const Compiler_IR_Function &function)
void emit_module_layout(std::ostream &out) const
void emit_function(const size_t index, std::ostream &out)
Compiler_C_Backend_Emission emission_
void emit_value_declarations(std::ostream &out, const Compiler_IR_Function &function) const
bool emit_constant_expression(const Compiler_IR_Instruction &inst, std::string &expression, std::string &error) const
const Compiler_C_Backend_Options * options_
void warn(const std::string &message)
std::string function_symbol(const size_t index) const
void emit_parameter_bindings(std::ostream &out, const Compiler_IR_Function &function) const
std::string type_comment(const Compiler_Type_Id type_id) const
const Compiler_Type_Context * types_
void emit_prototypes(std::ostream &out) const
std::string function_descriptor_symbol(const size_t index) const
void emit_function_descriptors(std::ostream &out) const
void emit_slot_declarations(std::ostream &out, const Compiler_IR_Function &function) const
void emit_function_body(std::ostream &out, const Compiler_IR_Function &function, const std::string &symbol)
void emit_function_signature(std::ostream &out, const std::string &symbol) const
void emit_runtime_prelude(std::ostream &out) const
Compiler_C_Backend_Emission run()
Emits the full C translation unit.
void emit_terminator(std::ostream &out, const Compiler_IR_Block &block, const Compiler_IR_Function &function)
void emit_instruction_comment(std::ostream &out, const Compiler_IR_Instruction &inst) const
void fail(const std::string &message)
Emits portable C from one validated Compiler_IR_Module.
Compiler_C_Backend_Emission emit_module(const Compiler_IR_Module *module, const Compiler_Type_Context *types=nullptr) const
Emits one validated IR module as portable C.
Compiler_C_Backend_Options options
Compiler_C_Backend(Compiler_C_Backend_Options options_in={})
Builds one reusable C backend with options_in.
Context owning all compiler type nodes.
std::string to_string(const Compiler_Type_Id id) const
Renders one type to a deterministic human-readable string.
T & access(const size_t i) const noexcept
Fast access without checking allocation and bound_min_clock checking.
T & append()
Allocate a new entry to the end of array.
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466
std::string global_name(const Compiler_IR_Global_Slot_Id id)
size_t count_parameters(const Compiler_IR_Function &function) noexcept
std::string token_name(const Compiler_Operator_Kind kind) noexcept
bool parse_integer_literal(const std::string &text, long long &value) noexcept
std::string indent(const size_t count)
std::string value_name(const Compiler_IR_Value_Id id)
std::string upper_identifier(std::string_view text)
std::string block_label(const size_t id)
std::string sanitize_identifier(std::string_view text)
std::string local_name(const Compiler_IR_Local_Slot_Id id)
std::string c_string_literal(std::string_view text)
std::string safe_comment_text(std::string text)
Main namespace for Aleph-w library functions.
Definition ah-arena.H:89
const char * compiler_ir_terminator_kind_name(const Compiler_IR_Terminator_Kind kind) noexcept
Stable debug name for one terminator kind.
void message(const char *file, int line, const char *format,...)
Print an informational message with file and line info.
Definition ahDefs.C:95
size_t size(Node *root) noexcept
const char * compiler_operator_name(const Compiler_Operator_Kind kind) noexcept
Returns a stable debug name for one operator kind.
Compiler_IR_Validation_Report validate_ir_module(const Compiler_IR_Module &module)
Validates all functions in one lowered IR module.
and
Check uniqueness with explicit hash + equality functors.
size_t Compiler_IR_Value_Id
constexpr size_t compiler_ir_invalid_id() noexcept
Returns the sentinel invalid IR id.
size_t Compiler_Type_Id
const char * compiler_ir_slot_kind_name(const Compiler_IR_Slot_Kind kind) noexcept
Stable debug name for one slot kind.
void error(const char *file, int line, const char *format,...)
Print an error message with file and line info.
Definition ahDefs.C:100
size_t Compiler_IR_Global_Slot_Id
const char * compiler_ir_instruction_kind_name(const Compiler_IR_Instruction_Kind kind) noexcept
Stable debug name for one instruction kind.
Compiler_C_Backend_Emission compiler_emit_c_module(const Compiler_IR_Module *module, const Compiler_C_Backend_Options &options={}, const Compiler_Type_Context *types=nullptr)
Convenience wrapper that emits one IR module to portable C.
Compiler_Operator_Kind
Stable operator kinds shared by reusable compiler layers.
size_t Compiler_IR_Local_Slot_Id
Itor::difference_type count(const Itor &beg, const Itor &end, const T &value)
Count elements equal to a value.
Definition ahAlgo.H:127
STL namespace.
static struct argp_option options[]
Definition ntreepic.C:1886
Result of one C backend emission request.
DynArray< std::string > errors
Hard emission failures.
bool valid
Whether emission completed successfully.
DynArray< std::string > warnings
Non-fatal findings.
std::string value_type_name
Generated C typedef name for runtime values.
std::string print_value_symbol
Generated C symbol that prints one runtime value.
std::string module_struct_name
Generated C struct name for module state.
std::string c_prefix
Shared prefix used for runtime helpers and generated symbols.
DynArray< std::string > function_descriptor_symbols
Generated callable descriptor symbols aligned with module.functions.
std::string dump_globals_symbol
Generated C symbol that prints current global state.
std::string module_init_symbol
Generated C symbol that initializes module globals.
bool ok() const noexcept
Returns whether emission finished without hard errors.
std::string top_level_symbol
Generated C symbol for the lowered top-level body, if any.
DynArray< std::string > function_symbols
Generated C function symbols aligned with module.functions.
std::string source
Final generated C translation unit.
Options that control one C backend emission request.
bool emit_comments
Whether to annotate the generated C with readable IR-derived comments.
bool emit_main
Whether to emit a standalone main() when the IR has a top-level body.
std::string module_name
Prefix used to derive stable C identifiers.
One basic block of IR instructions.
Lowered IR for one function or top-level body.
Compiler_IR_Value_Id next_value_id
Next value id to allocate while lowering.
DynArray< Compiler_IR_Block > blocks
Basic blocks in deterministic id order.
std::string name
Debug or source-level name.
Compiler_Type_Id type_id
Full function type, when known.
Compiler_IR_Block_Id entry_block
Canonical entry block.
DynArray< Compiler_IR_Slot > local_slots
Parameter/local slots in stable order.
One instruction producing an optional explicit result value.
Lowered IR module with shared global slots and functions.
DynArray< Compiler_IR_Slot > global_slots
Module-wide global slots.
DynArray< Compiler_IR_Function * > functions
Lowered non-top-level functions.
Compiler_IR_Function * top_level
Optional top-level body lowered as a function.
Compiler_SSA_Block_Id id
Dense SSA block id.
Definition SSA.H:163
DynArray< Compiler_SSA_Instruction > instructions
Linear SSA instruction list.
Definition SSA.H:168
std::string label
Deterministic debug label.
Definition SSA.H:165
Compiler_SSA_Terminator terminator
Explicit block terminator.
Definition SSA.H:169
Compiler_SSA_Value_Id return_value
Return value, when relevant.
Definition SSA.H:156
DynArray< Compiler_SSA_Block_Id > successors
Successors in deterministic order.
Definition SSA.H:157
Compiler_IR_Terminator_Kind kind
Terminator category.
Definition SSA.H:153
Compiler_SSA_Value_Id condition_value
Branch condition, when relevant.
Definition SSA.H:155
Lazy and scalable dynamic array implementation.