diff options
Diffstat (limited to 'tiger-compiler/src/llvmtranslate')
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/escapes-collector.cc | 151 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/escapes-collector.hh | 13 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/fwd.hh | 31 | ||||
| -rwxr-xr-x | tiger-compiler/src/llvmtranslate/generate-runtime.sh | 32 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/libllvmtranslate.cc | 47 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/libllvmtranslate.hh | 31 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/llvm-type-visitor.cc | 110 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/llvm-type-visitor.hh | 50 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/local.am | 39 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/tasks.cc | 64 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/tasks.hh | 34 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/tiger-runtime.c | 304 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/translator.cc | 737 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/translator.hh | 145 | ||||
| -rw-r--r-- | tiger-compiler/src/llvmtranslate/translator.hxx | 30 |
15 files changed, 1818 insertions, 0 deletions
diff --git a/tiger-compiler/src/llvmtranslate/escapes-collector.cc b/tiger-compiler/src/llvmtranslate/escapes-collector.cc new file mode 100644 index 0000000..4984805 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/escapes-collector.cc @@ -0,0 +1,151 @@ +#include <ast/all.hh> +#include <ast/default-visitor.hh> +#include <ast/non-assert-visitor.hh> +#include <ast/non-object-visitor.hh> +#include <llvmtranslate/escapes-collector.hh> + +namespace llvmtranslate +{ + /// LLVM IR doesn't support static link and nested functions. + /// In order to translate those functions to LLVM IR, we use a technique + /// called Lambda Lifting, which consists in passing a pointer to + /// the escaped variables to the nested function using that variable. + /// + /// In order to do that, we need a visitor to collect these kind of + /// variables and associate them to each function. + + class EscapesCollector + : public ast::DefaultConstVisitor + , public ast::NonObjectConstVisitor + , public ast::NonAssertConstVisitor + { + public: + /// Super class. + using super_type = ast::DefaultConstVisitor; + /// Import overloaded operator() methods. + using super_type::operator(); + + EscapesCollector() + : did_modify_{false} + , escaped_{} + {} + + escaped_map_type& escaped_get() { return escaped_; } + + void operator()(const ast::FunctionChunk& e) override + { + const bool saved_did_modify = did_modify_; + + // Iterate on the chunk in order to iteratively collect all the callee + // functions' escaped variables. + did_modify_ = !e.empty(); + while (did_modify_) + { + did_modify_ = false; + super_type::operator()(e); + } + + did_modify_ = saved_did_modify; + } + + void operator()(const ast::FunctionDec& e) override + { + // Keep track of the current function + // FIXME DONE: Some code was deleted here. + const auto function_type = \ + dynamic_cast<const type::Function*>(&e.type_get()->actual()); + + precondition(function_type != nullptr); + + // Last visited function + const type::Function* previous_scope = current_; + + if (previous_scope == nullptr) + { + // Then we are at the first depth of the program, hence _main + main_function_ = function_type; + } + + current_ = function_type; + + if (!escaped_.contains(current_)) + { + escaped_[current_] = misc::set<const ast::VarDec*>{}; + } + + super_type::operator()(e); + + // Guess we only really need to go back one step before + current_ = previous_scope; + } + + void operator()(const ast::CallExp& e) override + { + super_type::operator()(e); + + // FIXME DONE: Some code was deleted here. + const auto escaped_reference = escaped_.find(current_); + precondition(escaped_reference != escaped_.end()); + const auto escaped_state = escaped_reference->second; + + const size_t before_size = escaped_state.size(); + + super_type::operator()(e.def_get()); + + // Check whether there are any newly collected escaped variables. + // If there are, mark the iteration as modified. + // FIXME DONE: Some code was deleted here. + const size_t after_size = escaped_state.size(); + + did_modify_ = before_size != after_size; + } + + void operator()(const ast::SimpleVar& e) override + { + // Associate escaped variables declared in parent frames with their + // functions + // FIXME DONE: Some code was deleted here. + if (current_ == main_function_ || !e.def_get()->escape_get()) + { + super_type::operator()(e); + return; + } + + // Checking that the variable is escaped because not all variables are + auto attached_to = escaped_.find(current_); + + // We have a function to attach this to + if (attached_to != escaped_.end() + && !attached_to->second.contains(e.def_get())) + { + attached_to->second.insert(e.def_get()); + did_modify_ = true; + } + + super_type::operator()(e); + } + + private: + /// Whether any modification was done during the iteration. + bool did_modify_ = false; + + /// Associate a set of variables with their function. + escaped_map_type escaped_; + + /// Current visiting function. + // FIXME DONE: Some code was deleted here. + const type::Function* current_ = nullptr; + + /// The reference to the main function + const type::Function* main_function_ = nullptr; + }; + + escaped_map_type collect_escapes(const ast::Ast& ast) + { + EscapesCollector collect; + collect(ast); + + return std::move(collect.escaped_get()); + } + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/escapes-collector.hh b/tiger-compiler/src/llvmtranslate/escapes-collector.hh new file mode 100644 index 0000000..dab93c6 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/escapes-collector.hh @@ -0,0 +1,13 @@ +#pragma once + +#include <ast/fwd.hh> +#include <llvmtranslate/fwd.hh> + +namespace llvmtranslate +{ + + /// Collect all escapes for every function in the ast, and store it in a map. + /// This is used for Lambda Lifting. + escaped_map_type collect_escapes(const ast::Ast& ast); + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/fwd.hh b/tiger-compiler/src/llvmtranslate/fwd.hh new file mode 100644 index 0000000..1eef45e --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/fwd.hh @@ -0,0 +1,31 @@ +#pragma once + +#include <map> + +#include <ast/fwd.hh> +#include <misc/set.hh> +#include <type/fwd.hh> + +namespace llvm +{ + // From llvm/IR/Module.h. + class Module; + + // From llvm/IR/DerivedTypes.h + class StructType; + + // From llvm/IR/Type.h + class Type; + + // From llvm/IR/LLVMContext.h + class LLVMContext; + +} // namespace llvm + +namespace llvmtranslate +{ + using escaped_map_type = + std::map<const type::Function*, misc::set<const ast::VarDec*>>; + using frame_map_type = escaped_map_type; + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/generate-runtime.sh b/tiger-compiler/src/llvmtranslate/generate-runtime.sh new file mode 100755 index 0000000..2e05445 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/generate-runtime.sh @@ -0,0 +1,32 @@ +#!/bin/sh + +[ -z "$1" ] && echo "$0: Missing input file" && exit +[ -z "$2" ] && echo "$0: Missing output file" && exit + +input=$1 +output=$2 + +awk 'BEGIN { + print("#include <string>"); + print("#include <llvmtranslate/libllvmtranslate.hh>"); + print(""); + print("namespace llvmtranslate"); + print("{"); + print("const char* runtime_string()"); + print("{"); + print(" return"); + printf("R\"0("); # The zero here only serves as an identifier for the raw string, it does not changes the code behavior at all. + } + /^#(<<|>>)/ { + next; + } + { + print($0); + } + END { + print(")0\";"); + print("}"); + print("} // namespace llvmtranslate"); + }' "$input" > "$output".tmp + +mv "$output".tmp "$output" diff --git a/tiger-compiler/src/llvmtranslate/libllvmtranslate.cc b/tiger-compiler/src/llvmtranslate/libllvmtranslate.cc new file mode 100644 index 0000000..b86b03a --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/libllvmtranslate.cc @@ -0,0 +1,47 @@ +/** + ** \file llvmtranslate/libllvmtranslate.hh + ** \brief Public llvmtranslate module interface implementation. + **/ + +#include <ast/default-visitor.hh> +#include <ast/non-object-visitor.hh> +#include <common.hh> // program_name + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-parameter" + +#include <llvm/AsmParser/Parser.h> +#include <llvm/IR/LLVMContext.h> +#include <llvm/IR/Module.h> +#include <llvm/IR/Verifier.h> +#include <llvm/Support/SourceMgr.h> // llvm::SMDiagnostic +#include <llvmtranslate/escapes-collector.hh> +#include <llvmtranslate/fwd.hh> +#include <llvmtranslate/libllvmtranslate.hh> +#include <llvmtranslate/translator.hh> + +#pragma GCC diagnostic pop + +namespace llvmtranslate +{ + std::pair<std::unique_ptr<llvm::LLVMContext>, std::unique_ptr<llvm::Module>> + translate(const ast::Ast& the_program) + { + auto ctx = std::make_unique<llvm::LLVMContext>(); + auto module = std::make_unique<llvm::Module>(program_name, *ctx); + + Translator translate{*module, collect_escapes(the_program)}; + translate(the_program); + + llvm::verifyModule(*module); + + return {std::move(ctx), std::move(module)}; + } + + std::unique_ptr<llvm::Module> runtime_get(llvm::LLVMContext& ctx) + { + llvm::SMDiagnostic diag; + return llvm::parseAssemblyString(runtime_string(), diag, ctx); + } + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/libllvmtranslate.hh b/tiger-compiler/src/llvmtranslate/libllvmtranslate.hh new file mode 100644 index 0000000..cf431e9 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/libllvmtranslate.hh @@ -0,0 +1,31 @@ +/** + ** \file llvmtranslate/libllvmtranslate.hh + ** \brief Public llvmtranslate module interface declaration. + */ + +#pragma once + +#include <memory> +#include <utility> + +#include <llvm/IR/LLVMContext.h> + +#include <ast/fwd.hh> +#include <llvmtranslate/fwd.hh> + +/// Translation from ast::Ast to llvm::Value. +namespace llvmtranslate +{ + /// Translate the file into a llvm::Module. + std::pair<std::unique_ptr<llvm::LLVMContext>, std::unique_ptr<llvm::Module>> + translate(const ast::Ast& the_program); + + /// Load the runtime as a llvm::Module. + std::unique_ptr<llvm::Module> runtime_get(llvm::LLVMContext& ctx); + + /// The LLVM runtime as a string, loaded from the generated file. + /// This function is implemented in $(build_dir)/src/llvmtranslate/runtime.cc + /// For more information take a look at `local.am`. + const char* runtime_string(); + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/llvm-type-visitor.cc b/tiger-compiler/src/llvmtranslate/llvm-type-visitor.cc new file mode 100644 index 0000000..a2130c9 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/llvm-type-visitor.cc @@ -0,0 +1,110 @@ +/** + ** \file llvmtranslate/llvm-type-visitor.cc + ** \brief Implementation of llvmtranslator::LLVMTypeVisitor. + */ + +#include <llvm/IR/DerivedTypes.h> + +#include <llvmtranslate/llvm-type-visitor.hh> +#include <type/types.hh> + +namespace llvmtranslate +{ + LLVMTypeVisitor::LLVMTypeVisitor(llvm::LLVMContext& ctx) + : ctx_{ctx} + {} + + llvm::Type* LLVMTypeVisitor::llvm_type_get() { return type_; } + + llvm::Type* LLVMTypeVisitor::get_record_ltype(const type::Record* e) + { + return structs_[e]; + } + + llvm::Type* LLVMTypeVisitor::llvm_type(const type::Type& type) + { + operator()(type); + return type_; + } + + void LLVMTypeVisitor::operator()(const type::Nil& e) + { + if (auto record_type = e.record_type_get()) + type_ = llvm_type(*record_type); + else + unreachable(); + } + + void LLVMTypeVisitor::operator()(const type::Void&) + { + // FIXME DONE: Some code was deleted here (Void types can be interpreted as int or void type). + // Je cite : "a variable can hold a void value (that are represented using an integer in LLVM)" + // Mais du coup, je sais pas ce qui détermine quel type on lui donne. + // En attendant je mets void tout le temps jusqu'à ce qu'on trouve pourquoi on le mettrait à int + // Y a un monde où ça se gère au dessus (genre les vardecs et les assignexp ?) + // Source : Un YAKA qui dit que en gros on a le choix mais qu'il vaut mieux le représenter comme int + // Du coup pour le distinguer c'est un int sur 0 bits + type_ = llvm::Type::getIntNTy(ctx_,0); + } + + void LLVMTypeVisitor::operator()(const type::Int&) + { + type_ = llvm::Type::getInt32Ty(ctx_); + } + + void LLVMTypeVisitor::operator()(const type::String&) + { + // Strings are pointers to characters in LLVM. + // FIXME DONE: Some code was deleted here. + // Bon vu qu'on a pas accès à la taille de la string on y va yolo. + // Du coup c'est un PointerType de Int8 (du coup 8 bits pour un char) + type_ = llvm::PointerType::get(llvm::Type::getInt8Ty(ctx_), 0); + } + + void LLVMTypeVisitor::operator()(const type::Named& e) + { + // FIXME DONE: Some code was deleted here. + llvm_type(e.actual()); + + const std::string reference_name = e.name_get().get(); + + if (const auto record_ref = dynamic_cast<const type::Record*>(&e.type_get()->actual()); + record_ref != nullptr && structs_[record_ref]->getName() != reference_name) + { + structs_[record_ref]->setName(reference_name); + } + } + + void LLVMTypeVisitor::operator()(const type::Record& e) + { + // If the record was never translated, translate it + if (!structs_[&e]) + { + // We need to create the struct in two passes to support recursive + // types, like 'type a = { next : a } + // So, first we create an empty struct + structs_[&e] = llvm::StructType::create(ctx_); + // Then set the body of the structure + std::vector<llvm::Type*> field_types; + field_types.reserve(e.fields_get().size()); + // FIXME DONE: Some code was deleted here. + //Martial: Copy and convert the fields ig + for (const auto& field : e.fields_get()) + { + super_type::operator()(field.type_get()); + field_types.push_back(type_); + } + //Martial: Set the body with the converted types + structs_[&e]->setBody(std::move(field_types), false); + } + type_ = llvm::PointerType::getUnqual(structs_[&e]); + } + + void LLVMTypeVisitor::operator()(const type::Array& e) + { + // Arrays are pointers to the array elements, like in C. + // FIXME DONE: Some code was deleted here. + llvm_type(*e.get_element_type()); + type_ = llvm::PointerType::getUnqual(type_); + } +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/llvm-type-visitor.hh b/tiger-compiler/src/llvmtranslate/llvm-type-visitor.hh new file mode 100644 index 0000000..d19ea9d --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/llvm-type-visitor.hh @@ -0,0 +1,50 @@ +/** + ** \file llvmtranslate/llvm-type-visitor.hh + ** \brief Definition of llvmtranslator::LLVMTypeVisitor. + */ + +#pragma once + +#include <llvm/IR/LLVMContext.h> + +#include <llvmtranslate/fwd.hh> +#include <type/default-visitor.hh> + +namespace llvmtranslate +{ + /// Visit a Type and return the corresponding llvm::Type. + class LLVMTypeVisitor : public type::DefaultConstVisitor + { + public: + using super_type = type::DefaultConstVisitor; + // Import overloaded virtual functions. + using super_type::operator(); + + LLVMTypeVisitor(llvm::LLVMContext& ctx); + + llvm::Type* llvm_type_get(); + llvm::Type* get_record_ltype(const type::Record* e); + + /// Visit methods. + /// \{ + void operator()(const type::Nil& e) override; + void operator()(const type::Void& e) override; + void operator()(const type::Int& e) override; + void operator()(const type::String& e) override; + void operator()(const type::Named& e) override; + void operator()(const type::Record& e) override; + void operator()(const type::Array& e) override; + /// \} + + private: + /// The global context. + llvm::LLVMContext& ctx_; + /// The type of the last visited node. + llvm::Type* type_ = nullptr; + /// llvm::StructTypes for each type::Record + std::map<const type::Record*, llvm::StructType*> structs_; + /// Recurse and return the type_. + llvm::Type* llvm_type(const type::Type& type); + }; + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/local.am b/tiger-compiler/src/llvmtranslate/local.am new file mode 100644 index 0000000..d5a752b --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/local.am @@ -0,0 +1,39 @@ +# Compile the LLVM Tiger runtime +EXTRA_DIST += %D%/tiger-runtime.c +CLEANFILES += %D%/runtime.ll +%D%/runtime.ll: %D%/tiger-runtime.c + $(AM_V_CC)$(CLANG) -c -m32 -std=c99 -emit-llvm -S -o $@ $^ + +LLVM_RUNTIME_GENERATION = %D%/generate-runtime.sh +EXTRA_DIST += $(LLVM_RUNTIME_GENERATION) +CLEANFILES += %D%/runtime.cc +%D%/runtime.cc: %D%/runtime.ll + $(AM_V_GEN)$(srcdir)/$(LLVM_RUNTIME_GENERATION) $< $@ + +## llvmtranslate module. +src_libtc_la_SOURCES += \ + %D%/escapes-collector.cc %D%/escapes-collector.hh \ + %D%/translator.hh %D%/translator.hxx %D%/translator.cc \ + %D%/libllvmtranslate.cc %D%/libllvmtranslate.hh \ + %D%/llvm-type-visitor.cc %D%/llvm-type-visitor.hh \ + %D%/fwd.hh + +nodist_src_libtc_la_SOURCES += %D%/runtime.cc + +## FIXME: Add SWIG support for this module + +## LLVM flags are found using `llvm-config`. + +if STATIC_LLVM +EXTRA_LLVM_CONFIG_FLAGS = --link-static +else +EXTRA_LLVM_CONFIG_FLAGS = +endif + +AM_CXXFLAGS += `$(LLVM_CONFIG) $(EXTRA_LLVM_CONFIG_FLAGS) --cppflags` +src_libtc_la_LDFLAGS += \ + `$(LLVM_CONFIG) $(EXTRA_LLVM_CONFIG_FLAGS) --ldflags` \ + `$(LLVM_CONFIG) $(EXTRA_LLVM_CONFIG_FLAGS) --libs core linker asmparser irprinter` \ + `$(LLVM_CONFIG) $(EXTRA_LLVM_CONFIG_FLAGS) --system-libs` + +TASKS += %D%/tasks.hh %D%/tasks.cc diff --git a/tiger-compiler/src/llvmtranslate/tasks.cc b/tiger-compiler/src/llvmtranslate/tasks.cc new file mode 100644 index 0000000..09f865c --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/tasks.cc @@ -0,0 +1,64 @@ +/** + ** \file llvmtranslate/tasks.cc + ** \brief LLVM Translate tasks. + */ + +#include <memory> + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-parameter" + +#include <llvm/Config/llvm-config.h> // LLVM_VERSION_* +#include <llvm/IR/Module.h> +#include <llvm/IR/PassManager.h> +#include <llvm/IRPrinter/IRPrintingPasses.h> +#include <llvm/Linker/Linker.h> +#include <llvm/Support/raw_ostream.h> // llvm::outs() + +#pragma GCC diagnostic pop + +#include <ast/tasks.hh> +#include <llvmtranslate/fwd.hh> +#include <llvmtranslate/libllvmtranslate.hh> +#define DEFINE_TASKS 1 +#include <llvmtranslate/tasks.hh> +#undef DEFINE_TASKS + +namespace llvmtranslate::tasks +{ + std::pair<std::unique_ptr<llvm::LLVMContext>, std::unique_ptr<llvm::Module>> + module = {nullptr, nullptr}; + + /// Translate the AST to LLVM IR. + void llvm_compute() { module = translate(*ast::tasks::the_program); } + + /// Display the LLVM IR. + void llvm_display() + { + // If the runtime has to be displayed, get the runtime module, + // link it with the program module and print it. + if (llvm_runtime_display_p) + { + auto runtime = runtime_get(*module.first); +#if LLVM_VERSION_MAJOR == 3 && LLVM_VERSION_MINOR <= 7 + auto link = + llvm::Linker::LinkModules(module.second.get(), runtime.get()); +#else + auto link = + llvm::Linker::linkModules(*module.second, std::move(runtime)); +#endif + (void)link; + postcondition(!link); // Returns true on error + } + + auto& out = llvm::outs(); + llvm::PrintModulePass printer{out}; +#if LLVM_VERSION_MAJOR == 3 && LLVM_VERSION_MINOR <= 8 + printer.run(*module.second); +#else + llvm::ModuleAnalysisManager dummy_mam; + printer.run(*module.second, dummy_mam); +#endif + } + +} // namespace llvmtranslate::tasks diff --git a/tiger-compiler/src/llvmtranslate/tasks.hh b/tiger-compiler/src/llvmtranslate/tasks.hh new file mode 100644 index 0000000..ade231a --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/tasks.hh @@ -0,0 +1,34 @@ +#pragma once + +#include <llvmtranslate/fwd.hh> +#include <task/libtask.hh> + +namespace llvmtranslate::tasks +{ + /// The global translation module of ast;:tasks::the_program. + extern std::pair<std::unique_ptr<llvm::LLVMContext>, + std::unique_ptr<llvm::Module>> + module; + + TASK_GROUP("5.5. Translation to LLVM Intermediate Representation"); + + /// Translate the AST to LLVM IR. + TASK_DECLARE("llvm-compute", + "translate to LLVM IR", + llvm_compute, + "typed desugar-for desugar-string-cmp desugar escapes-compute"); + + /// Activate displaying the runtime along with the LLVM IR. + BOOLEAN_TASK_DECLARE("llvm-runtime-display", + "enable runtime displaying" + "along with the LLVM IR", + llvm_runtime_display_p, + ""); + + /// Display the LLVM IR. + TASK_DECLARE("llvm-display", + "display the LLVM IR", + llvm_display, + "llvm-compute"); + +} // namespace llvmtranslate::tasks diff --git a/tiger-compiler/src/llvmtranslate/tiger-runtime.c b/tiger-compiler/src/llvmtranslate/tiger-runtime.c new file mode 100644 index 0000000..f952e0f --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/tiger-runtime.c @@ -0,0 +1,304 @@ +/** + \file llvm/tiger-runtime.c + \brief C Implementation of the Tiger runtime. +*/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/wait.h> +#include <unistd.h> + +#define EXIT_RUNTIME_FAILURE 120 + +// FWD, declared by tc +void tc_main(int); + +/** \name Internal functions (calls generated by the compiler only). */ +/** \{ */ + +/** \brief Allocate an array and fill it with a default value. + \param size The size of the array. + \param elt The default element. + + An element size is always the size of a word on 32-bit systems. +*/ +int *tc_init_array(int size, int elt) +{ + int *arr = (int *)malloc(size * sizeof (elt)); + for (size_t i = 0; i < size; ++i) + arr[i] = elt; + return arr; +} +/** \} */ + +/** \name Miscellaneous */ +/** \{ */ + +/** \brief Equivalent to operator! in C. + \param i The integer to be inversed. +*/ +int tc_not(int i) +{ + return !i; +} + +/** \brief Exit the program with the desired status. + \param status The status code. +*/ +void tc_exit(int status) +{ + exit(status); +} +/** \} */ + +/** \name Operations on strings. */ +/** \{ */ + +// Small trick. Add a \0 after each char in the consts +// This is filled in tc_main +static char consts[512] = { 0 }; + +/** \brief Get a string containing the character represented by the ascii value + * of \a i. + \param i The ascii value of the desired character. +*/ +const char *tc_chr(int i) +{ + if (!(0 <= i && i <= 255)) + { + fputs("chr: character out of range\n", stderr); + exit(EXIT_RUNTIME_FAILURE); + } + return consts + i * 2; +} + +/** \brief Concatenate two strings. + \param a The first string. + \param b The second string. +*/ +const char *tc_concat(const char *a, const char *b) +{ + size_t len_a = strlen(a); + size_t len_b = strlen(b); + if (len_a == 0) + return b; + else if (len_b == 0) + return a; + else + { + int i = 0; + int n = len_a + len_b; + char *t = (char *) malloc(n + 1); + for (i = 0; i < len_a; i++) + t[i] = a[i]; + for (i = 0; i < len_b; i++) + t[i + len_a] = b[i]; + t[n] = '\0'; + return t; + } +} + +/** \brief Get the ascii value of a character. + \param s The string representing the desired character to be converted. + + Inverse of `tc_chr`. +*/ +int tc_ord(const char *s) +{ + size_t len = strlen(s); + if (len == 0) + return -1; + else + return s[0]; +} + +/** \brief Get the size of a string. + \param s The string. +*/ +int tc_size(const char *s) +{ + return strlen(s); +} + +/** \brief Return a part of the string \a s. + \param s The source string + \param first The first character of the extraction (starting at 0) + \param n The number of characters to get. + + \a first and \a n must be positive, and one shall not go beyond the size + of \a s. Otherwise, exit with runtime failure. +*/ +const char *tc_substring(const char *s, int first, int n) +{ + size_t len = strlen(s); + if (!(0 <= first + && 0 <= n + && first + n <= len)) + { + fputs("substring: arguments out of bounds\n", stderr); + exit(EXIT_RUNTIME_FAILURE); + } + + if (n == 1) + return consts + s[first] * 2; + else + { + char *t = (char *) malloc(n + 1); + for (int i = 0; i < n; i++) + t[i] = s[first + i]; + t[n] = '\0'; + return t; + } +} + +/** \brief Compare two strings. + \param lhs The first string. + \param rhs The second string. +*/ +int tc_strcmp(const char *lhs, const char *rhs) +{ + return strcmp(lhs, rhs); +} + +/** \brief Return a part of the string \a s. + \param s The source string + \param first The first character of the extraction (starting at 0) + \param n The number of characters to get. + + \a first and \a n must be positive, and one shall not go beyond the size + of \a s. Otherwise, exit with runtime failure. +*/ +int tc_streq(const char *lhs, const char *rhs) +{ + return strcmp(lhs, rhs) == 0; +} +/** \} */ + +/** \name Input/Output. */ +/** \{ */ + +/** \brief Get a character from the standard input. +*/ +const char *tc_getchar() +{ + int i = getc(stdin); + if (i == EOF) + return ""; + else + return consts + i * 2; +} + +/** \brief Print a string on the standard output. + \param s The string to be printed. +*/ +void tc_print(const char *s) +{ + printf("%s", s); +} + +/** \brief Print a string on the standard error. + \param s The string to be printed. +*/ +void tc_print_err(const char *s) +{ + fprintf(stderr, "%s", s); +} + +/** \brief Print an int on the standard error. + \param i The int to be printed. +*/ +void tc_print_int(int i) +{ + printf("%d", i); +} + +/** \brief Flush the standard output. +*/ +void tc_flush() +{ + fflush(stdout); +} + +/** \} */ + +/** \name Custom primitives. */ +/** \{ */ + +/** \brief Terminate the program with an error if condition if false + \param condition Condition to assert, represented as a Tiger 32 bits integer + \param instruction_str The condition represented as a string, used for + pretty-printing. Can be NULL + \param filename File in which the assertion comes from. Can be NULL +*/ +void tc_assertion(const int condition, const char* instruction_str, + const char* filename) +{ + if (condition) + { + return; + } + + if (instruction_str == NULL) + { + instruction_str = ""; + } + + if (filename == NULL) + { + filename = ""; + } + + fprintf(stderr, "%s: %s assertion is false. aborting\n", filename, + instruction_str); + abort(); +} + +/** + * \brief Proceed to a fork syscall and return the resulting process id. + * \return the resulting pid for the parent, 0 for the child, or -1 if the + * process forking failed + */ +int tc_fork() + { + return fork(); + } + +/** + * \brief Wait for the process specified by the provided id to end and return + * the resulting status code. + * \param pid a process, referenced by its identifier + * \return the process' status code + */ +int tc_wait_pid(int pid) + { + int status_code = -1; + waitpid(pid, &status_code, WUNTRACED | WCONTINUED); + return status_code; + } + +/** + * \brief Determine the exit code specified by a status code and return it. + * \param status_code any process status code + * \return the implied exit code + */ +int tc_get_exit_code(int status_code) + { + return WEXITSTATUS(status_code); + } + +/** \} */ + +int main() +{ + // Fill the `consts` array with every character in the ascii table, followed + // by a null character. + for (int i = 0; i < 512; i += 2) + { + consts[i] = i / 2; + consts[i + 1] = 0; + } + + tc_main(0); + return 0; +} diff --git a/tiger-compiler/src/llvmtranslate/translator.cc b/tiger-compiler/src/llvmtranslate/translator.cc new file mode 100644 index 0000000..2c27db5 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/translator.cc @@ -0,0 +1,737 @@ +/** + ** \file llvmtranslate/translator.cc + ** \brief Implementation of llvmtranslate::Translator + */ + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-parameter" + +#include <llvm/Config/llvm-config.h> // LLVM_VERSION_* +#include <llvm/IR/LLVMContext.h> +#include <llvm/IR/Verifier.h> // llvm::verifyFunction +#include <llvm/Support/Casting.h> +#include <llvm/TargetParser/Host.h> // llvm::sys +#include <llvm/TargetParser/Triple.h> + +#pragma GCC diagnostic pop + +#include <ast/all.hh> +#include <llvmtranslate/translator.hh> + +#include "llvm-type-visitor.hh" + +namespace llvmtranslate +{ + using namespace std::string_literals; + + namespace + { + // Shorthands for integer type and pointer to integer type. + inline llvm::IntegerType* i32_t(llvm::LLVMContext& ctx) + { + return llvm::Type::getInt32Ty(ctx); + } + + inline llvm::PointerType* i32p_t(llvm::LLVMContext& ctx) + { + return llvm::PointerType::get(llvm::Type::getInt32Ty(ctx), 0); + } + + llvm::AllocaInst* create_alloca(llvm::Function* ll_function, + llvm::Type* ll_type, + const std::string& name) + { + // Create an IRBuilder starting at the beginning of the current entry + // block. LLVM treats allocas as local variables only if they occur at the + // beginning of a function. + llvm::IRBuilder<> tmp(&ll_function->getEntryBlock(), + ll_function->getEntryBlock().begin()); + return tmp.CreateAlloca(ll_type, nullptr, name); + } + + // Set default attributes to the functions + void set_default_attributes(llvm::Function& the_function, + const ast::FunctionDec& e) + { + the_function.addFnAttr(llvm::Attribute::NoUnwind); // No exceptions in TC + if (!e.body_get()) // Inline primitives + the_function.addFnAttr(llvm::Attribute::InlineHint); + } + + std::string function_dec_name(const ast::FunctionDec& e) + { + // Rename "_main" to "tc_main" + if (e.name_get() == "_main") + return "tc_main"; + // Prefix all the primitives with "tc_" + if (!e.body_get()) + return "tc_" + e.name_get().get(); + return e.name_get().get(); + } + } // namespace + + Translator::Translator(llvm::Module& module, escaped_map_type&& escaped) + : module_{module} + , ctx_{module_.getContext()} + , builder_{ctx_} + , escaped_{std::move(escaped)} + , type_visitor_{ctx_} + { + // The current process triple. + auto process_triple = llvm::Triple(llvm::sys::getProcessTriple()); + // Set the 32-bit version of the triple. + module_.setTargetTriple(process_triple.get32BitArchVariant().str()); + } + + void Translator::operator()(const ast::Ast& e) + { + translate(e); + value_ = nullptr; + } + + llvm::Value* Translator::translate(const ast::Ast& node) + { + node.accept(*this); + return value_; + } + + llvm::Value* Translator::access_var(const ast::Var& e) + { + if (auto var_ast = dynamic_cast<const ast::SimpleVar*>(&e)) + { + // FIXME DONE: Some code was deleted here. + // Chopper la VarDec + const ast::VarDec* dec = var_ast->def_get(); + if (dec == nullptr) + { + // This is probably a binder error + unreachable(); + } + // getFunction --> getValueSymbolTable --> lookup + auto all_vars = locals_[current_function_]; + // Ou si c'est un argument, juste iterer sur les arguments jusqu'a trouver la bonne + return all_vars[dec]; + + } + else if (auto arr_ast = dynamic_cast<const ast::SubscriptVar*>(&e)) + { + // FIXME DONE: Some code was deleted here. + // Here we have the case of an access in an array (var[index]) + // Faire un call recursif sur la variable parent afin d'obtenir une reference + llvm::Value* mother_val = translate(arr_ast->var_get()); + + // Utiliser cette ref pour trouver le type associe + llvm::Type* mother_ty = llvm_type(*(arr_ast->var_get().type_get())); + + // Creer une array ref afin de pouvoir stocker les indexs + // Ici, l'index en question est index_ de la variable e + llvm::Value* index_exp = translate(arr_ast->index_get()); + //std::vector<llvm::Value*> = + const auto index = llvm::ArrayRef(index_exp); + // Et il n'y a plus qu'a cree tout ca en utilisant un llvm::IRBuilderBase::CreateGEP + + return builder_.CreateGEP(mother_ty, mother_val, index, "subscriptptr_"s + "some_index"); + } + else if (auto field_ast = dynamic_cast<const ast::FieldVar*>(&e)) + { + const ast::Var* var = nullptr; + // FIXME DONE: Some code was deleted here. + // Wait, isn't this going to recurse and create many instances of the thing? + // Or it is just a small piece of the path towards the full path to this var? + var = &(field_ast->var_get()); + + auto var_val = translate(*var); + + const type::Record* record_type = nullptr; + // FIXME DONE: Some code was deleted here. + record_type = dynamic_cast<const type::Record*>(&var->type_get()->actual()); + + if (record_type == nullptr) + { + // This could be a typing error (we do not have a var pointing to a record?) + unreachable(); + } + + misc::symbol field_name; + // FIXME DONE: Some code was deleted here. + field_name = field_ast->name_get(); + + int index = -1; + // FIXME DONE: Some code was deleted here (Get the index of the field). + index = record_type->field_index(field_name); + + // The GEP instruction provides us with safe pointer arithmetics, + // usually used with records or arrays. + llvm::Type* record_ltype = nullptr; + // FIXME DONE: Some code was deleted here (Get record's corresponding LLVM type). + llvm_type(*record_type); + record_ltype = type_visitor_.get_record_ltype(record_type); + + return builder_.CreateStructGEP(record_ltype, var_val, index, + "fieldptr_"s + field_name.get()); + } + else + unreachable(); + } + + llvm::Value* Translator::init_array(llvm::Value* count_val, + llvm::Value* init_val) + { + // Cast everything so that it is conform to the signature of init_array + // int *init_array(int, int) + + // We need to separate the pointers and the ints. + // LLVM requires a ptrtoint instruction for pointers + // and a bitcast for others. + auto init_val_cast = init_val->getType()->isPointerTy() + ? builder_.CreatePtrToInt(init_val, i32_t(ctx_), "init_array_ptrtoint") + : builder_.CreateBitCast(init_val, i32_t(ctx_), "init_array_bitcast"); + + // Create the init_array function: + // First, the arguments (int*, int, int) + std::vector<llvm::Type*> arg_type{i32_t(ctx_), init_val_cast->getType()}; + + // Then, create the FunctionType. + auto init_array_ltype = + llvm::FunctionType::get(i32p_t(ctx_), arg_type, false); + + // Get the llvm::Function from the module related to the name and type + auto init_array_function = + module_.getOrInsertFunction("tc_init_array", init_array_ltype); + + // Prepare the arguments. + std::vector<llvm::Value*> arg_vals{count_val, init_val_cast}; + + // Create the call. + auto init_array_call = + builder_.CreateCall(init_array_function, arg_vals, "init_array_call"); + + // Cast the result of the call in the desired type. + return builder_.CreateBitCast(init_array_call, + init_val->getType()->getPointerTo(), + "init_array_call_cast"); + } + + llvm::Type* Translator::llvm_type(const type::Type& type) + { + type_visitor_(type); + return type_visitor_.llvm_type_get(); + } + + llvm::FunctionType* + Translator::llvm_function_type(const type::Function& function_type) + { + // Prepare the arguments + std::vector<llvm::Type*> args_types; + // First, if there are any escaped vars, create ptr arguments for it + // (Lambda lifting) + + if (auto escapes_it = escaped_.find(&function_type); + escapes_it != std::end(escaped_)) + { + auto& escapes = escapes_it->second; + args_types.reserve(escapes.size() + + function_type.formals_get().fields_get().size()); + for (const auto dec : escapes) + { + llvm::Type* var_ltype = nullptr; + // FIXME DONE: Some code was deleted here (Get the llvm type of the VarDec). + var_ltype = llvm_type(*dec->type_get()); + + args_types.emplace_back(llvm::PointerType::getUnqual(var_ltype)); + } + } + else + args_types.reserve(function_type.formals_get().fields_get().size()); + + // Then, the actual arguments + for (const auto& field : function_type.formals_get()) + args_types.emplace_back(llvm_type(field.type_get())); + + llvm::Type* result_ltype = nullptr; + // FIXME DONE: Some code was deleted here (If the result is void typed, we assign llvm void type to result_ltype). + result_ltype = dynamic_cast<const type::Void*>(&function_type.result_get().actual()) != nullptr + ? llvm::Type::getVoidTy(ctx_) + : llvm_type(function_type.result_get()); + + return llvm::FunctionType::get(result_ltype, args_types, false); + } + + void Translator::operator()(const ast::SimpleVar& e) + { + // Void var types are actually Ints represented by a 0 + // FIXME DONE: Some code was deleted here. + value_ = access_var(e); + } + + void Translator::operator()(const ast::FieldVar& e) + { + // FIXME DONE: Some code was deleted here. + value_ = access_var(e); + } + + void Translator::operator()(const ast::SubscriptVar& e) + { + // FIXME DONE: Some code was deleted here. + value_ = access_var(e); + } + + void Translator::operator()(const ast::NilExp& e) + { + // FIXME DONE: Some code was deleted here (Get the record_type of the Nil type, and create a null pointer). + const llvm::Type* pointer_type = llvm_type(*e.type_get()); + value_ = llvm::ConstantPointerNull::get(pointer_type->getPointerTo()); + } + + void Translator::operator()(const ast::IntExp& e) + { + // FIXME DONE: Some code was deleted here (Integers in Tiger are all 32bit signed). + value_ = builder_.getInt32(e.value_get()); + } + + void Translator::operator()(const ast::StringExp& e) + { + // FIXME DONE: Some code was deleted here (Strings are translated as `i8*` values, like C's `char*`). + value_ = builder_.CreateGlobalStringPtr(e.value_get(), "str_exp"); + } + + void Translator::operator()(const ast::RecordExp& e) + { + // Get the record type + const type::Record* record_type = nullptr; + // FIXME DONE: Some code was deleted here. + record_type = dynamic_cast<const type::Record*>(&e.type_get()->actual()); + + // Type the record and use get_record_ltype() to get its LLVM type + llvm_type(*record_type); + auto struct_ltype = type_visitor_.get_record_ltype(record_type); + + // The size of the structure and cast it to int + auto sizeof_val = llvm::ConstantExpr::getSizeOf(struct_ltype); + sizeof_val = llvm::ConstantExpr::getTruncOrBitCast(sizeof_val, i32_t(ctx_)); + + // Generate the instruction calling Malloc + auto malloc_val = builder_.CreateMalloc( + i32_t(ctx_), struct_ltype, sizeof_val, nullptr, nullptr, "malloccall"); + + // Init the fields + // FIXME DONE: Some code was deleted here. + auto& fields = e.fields_get(); + + assertion(fields.size() == record_type->fields_get().size()); + + for (const auto field : fields) + { + const auto field_value = translate(field->init_get()); + const auto field_index = record_type->field_index(field->name_get()); + + assertion(field_index >= 0); + + const auto field_llvm_address = builder_.CreateStructGEP( + struct_ltype, malloc_val, field_index, "field_" + field->name_get().get() + ); + + value_ = builder_.CreateStore(field_value, field_llvm_address); + } + + value_ = malloc_val; + } + + void Translator::operator()(const ast::OpExp& e) + { + // FIXME DONE: Some code was deleted here. + // The comparison instructions returns an i1, and we need an i32, since everything + // is an i32 in Tiger. Use a zero-extension to avoid this. + const auto left_operand = \ + get_dereferenced(translate(e.left_get()), e.left_get().type_get()); + const auto right_operand = \ + get_dereferenced(translate(e.right_get()), e.right_get().type_get()); + + switch (e.oper_get()) + { + case ast::OpExp::Oper::add: + value_ = builder_.CreateAdd(left_operand, right_operand, "op_add"); + break; + case ast::OpExp::Oper::sub: + value_ = builder_.CreateSub(left_operand, right_operand, "op_sub"); + break; + case ast::OpExp::Oper::mul: + value_ = builder_.CreateMul(left_operand, right_operand, "op_mul"); + break; + case ast::OpExp::Oper::div: + value_ = builder_.CreateSDiv(left_operand, right_operand, "op_div"); + break; + case ast::OpExp::Oper::eq: + value_ = builder_.CreateICmpEQ(left_operand, right_operand, "op_eq"); + break; + case ast::OpExp::Oper::ne: + value_ = builder_.CreateICmpNE(left_operand, right_operand, "op_ne"); + break; + case ast::OpExp::Oper::gt: + value_ = builder_.CreateICmpSGT(left_operand, right_operand, "op_gt"); + break; + case ast::OpExp::Oper::ge: + value_ = builder_.CreateICmpSGE(left_operand, right_operand, "op_ge"); + break; + case ast::OpExp::Oper::lt: + value_ = builder_.CreateICmpSLT(left_operand, right_operand, "op_lt"); + break; + case ast::OpExp::Oper::le: + value_ = builder_.CreateICmpSLE(left_operand, right_operand, "op_le"); + break; + } + + value_ = builder_.CreateZExtOrTrunc(value_, i32_t(ctx_), "op_zext"); + } + + void Translator::operator()(const ast::SeqExp& e) + { + // An empty SeqExp is an empty expression, so we should return an int + // containing 0, since its type is void. + // FIXME DONE: Some code was deleted here. + if (e.exps_get().empty()) + { + value_ = get_void_value(); + return; + } + + for (const auto& exp : e.exps_get()) + { + translate(*exp); + + if (dynamic_cast<const ast::Var*>(exp) != nullptr) + { + value_ = get_dereferenced(value_, exp->type_get()); + } + } + } + + void Translator::operator()(const ast::AssignExp& e) + { + // FIXME DONE: Some code was deleted here. + llvm::Value* value = \ + get_dereferenced(translate(e.exp_get()), e.exp_get().type_get()); + llvm::Value* variable = translate(e.var_get()); + + value_ = builder_.CreateStore(value, variable); + } + + void Translator::operator()(const ast::IfExp& e) + { + // FIXME: Some code was deleted here (IfExps are handled in a similar way to Kaleidoscope (see LangImpl5.html)). + llvm::Value* cond = translate(e.test_get()); + + auto zero_val = llvm::ConstantInt::getSigned(cond->getType(), 0); + + // The condition may not be correct we are checking that this is different than 0 + cond = builder_.CreateICmpNE(cond, zero_val, "ifcond"); + + // We create the blocks + auto then_block = llvm::BasicBlock::Create(ctx_, "then_body", current_function_); + auto else_block = llvm::BasicBlock::Create(ctx_, "else_body", current_function_); + auto after_if = llvm::BasicBlock::Create(ctx_, "after_if", current_function_); + + // Explicitely create the if statement + builder_.CreateCondBr(cond, then_block, else_block); + + // We now tell the builder to insert newly added code to this block + builder_.SetInsertPoint(then_block); + + llvm::Value* then_body = translate(e.thenclause_get()); + + // Create an unconditional jump to the end of the if statement + builder_.CreateBr(after_if); + + // Very akward case where we have an if inside another if + // Apparently this is done to not disturb the PHI node + then_block = builder_.GetInsertBlock(); + + // We add the else block to the current function + // Function is private so we directly add the block to the function + // current_function_->getBasicBlockList().push_back(else_block); + + // We are now adding stuff in the else block + builder_.SetInsertPoint(else_block); + + llvm::Value* else_body = translate(e.elseclause_get()); + + builder_.CreateBr(after_if); + + else_block = builder_.GetInsertBlock(); + + // Finally we add the remaining block, the one to be executer after the if + // current_function_->getBasicBlockList().push_back(after_if); + + builder_.SetInsertPoint(after_if); + + if (dynamic_cast<const type::Void*>(e.type_get()) == nullptr) + { + // And now for the star of the show: The PHI node + // This is a value that can take multiple values depending on the path + llvm::PHINode* phi = builder_.CreatePHI(llvm_type(*e.elseclause_get().type_get()), 2, "phinode"); + + phi->addIncoming(then_body, then_block); + phi->addIncoming(else_body, else_block); + + value_ = phi; + } + } + + void Translator::operator()(const ast::WhileExp& e) + { + // Bb containing the test and the branching + auto test_bb = llvm::BasicBlock::Create(ctx_, "test", current_function_); + auto body_bb = llvm::BasicBlock::Create(ctx_, "body", current_function_); + auto after_bb = + llvm::BasicBlock::Create(ctx_, "afterloop", current_function_); + + // Save the after block for breaks + loop_end_[&e] = after_bb; + + // Explicitly fall through from the current block + builder_.CreateBr(test_bb); + + // Start inside the test BasicBlock + builder_.SetInsertPoint(test_bb); + + auto cond_val = translate(e.test_get()); + auto zero_val = llvm::ConstantInt::getSigned(cond_val->getType(), 0); + auto cmp_val = builder_.CreateICmpNE(cond_val, zero_val, "loopcond"); + + // Create the branching + builder_.CreateCondBr(cmp_val, body_bb, after_bb); + + // Translate the body inside the body BasicBlock + builder_.SetInsertPoint(body_bb); + // Don't store the return value, is should be void. + translate(e.body_get()); + + // Go back to the Test BasicBlock + builder_.CreateBr(test_bb); + + // Continue after the loop BasicBlock + builder_.SetInsertPoint(after_bb); + } + + void Translator::operator()(const ast::BreakExp& e) + { + // FIXME DONE: Some code was deleted here. + const auto while_node = dynamic_cast<const ast::WhileExp*>(e.def_get()); + + precondition(loop_end_.contains(while_node)); + + value_ = builder_.CreateBr(loop_end_.at(while_node)); + } + + void Translator::operator()(const ast::ArrayExp& e) + { + // Translate the number of elements, + // fill the array with the default value, then + // return the pointer to the allocated zone. + // FIXME DONE: Some code was deleted here (Use `init_array`). + llvm::Value* size = translate(e.size_get()); + llvm::Value* init_value = translate(e.init_get()); + value_ = init_array(size, init_value); + } + + void Translator::operator()(const ast::CastExp& e) + { + auto exp_val = translate(e.exp_get()); + llvm::Type* ltype = nullptr; + // FIXME DONE: Some code was deleted here (Destination llvm type). + ltype = llvm_type(*e.type_get()); + value_ = builder_.CreateBitCast(exp_val, ltype, "cast_exp"); + } + + void Translator::operator()(const ast::FunctionChunk& e) + { + for (const auto& fdec : e) + visit_function_dec_header(*fdec); + + for (const auto& fdec : e) + // There is nothing to translate for primitives. + if (fdec->body_get()) + visit_function_dec_body(*fdec); + } + + void Translator::visit_function_dec_header(const ast::FunctionDec& e) + { + bool is_main = e.name_get() == "_main"; + bool is_primitive = e.body_get() == nullptr; + auto name = function_dec_name(e); + + const type::Type* node_type = nullptr; + // FIXME DONE: Some code was deleted here. + node_type = &e.type_get()->actual(); + + auto& function_type = static_cast<const type::Function&>(*node_type); + auto function_ltype = llvm_function_type(function_type); + + // Main and primitives have External linkage. + // Other Tiger functions are treated as "static" functions in C. + auto linkage = is_main || is_primitive ? llvm::Function::ExternalLinkage + : llvm::Function::InternalLinkage; + + auto the_function = + llvm::Function::Create(function_ltype, linkage, name, &module_); + set_default_attributes(*the_function, e); + + auto& escaped = escaped_[&function_type]; + + // Name each argument of the function + for (auto arg_it = the_function->arg_begin(); + arg_it != the_function->arg_end(); ++arg_it) + { + auto i = std::distance(the_function->arg_begin(), arg_it); + auto var = escaped.size() && static_cast<size_t>(i) < escaped.size() + ? *std::next(escaped_[&function_type].begin(), i) + : e.formals_get()[i - escaped.size()]; + + arg_it->setName(var->name_get().get()); + } + } + + void Translator::visit_function_dec_body(const ast::FunctionDec& e) + { + auto the_function = module_.getFunction(function_dec_name(e)); + + // Save the old function in case a nested function occurs. + auto old_insert_point = builder_.saveIP(); + auto old_function = current_function_; + current_function_ = the_function; + + // Create a new basic block to start the function. + auto bb = llvm::BasicBlock::Create(ctx_, "entry_"s + e.name_get().get(), + the_function); + builder_.SetInsertPoint(bb); + + const type::Type* node_type = nullptr; + // FIXME DONE: Some code was deleted here. + node_type = &e.type_get()->actual(); + + auto& function_type = static_cast<const type::Function&>(*node_type); + auto& escaped = escaped_[&function_type]; + auto& formals = e.formals_get(); + + auto arg_it = the_function->arg_begin(); + + for (const auto var : escaped) + { + locals_[current_function_][var] = &*arg_it; + ++arg_it; + } + + // FIXME DONE: Some code was deleted here (Create alloca instructions for each variable). + for (size_t i = 0; i < formals.decs_get().size(); i++) + { + const ast::VarDec* const parameter = formals.decs_get().at(i); + locals_[current_function_][parameter] = arg_it + i; + } + + translate(*e.body_get()); + + // FIXME DONE: Some code was deleted here (Create a return instruction). + if (dynamic_cast<const type::Void*>(&function_type.result_get().actual()) != nullptr) + { + value_ = builder_.CreateRetVoid(); + } + else + { + if (dynamic_cast<const ast::Var*>(e.body_get()) != nullptr) + { + value_ = get_dereferenced(value_, e.body_get()->type_get()); + } + + value_ = builder_.CreateRet(value_); + } + + // Validate the generated code, checking for consistency. + llvm::verifyFunction(*the_function); + + // Restore the context of the old function. + current_function_ = old_function; + builder_.restoreIP(old_insert_point); + } + + void Translator::operator()(const ast::CallExp& e) + { + // Look up the name in the global module table. + // If it's a primitive, rename the call to tc_name. + // + // Then, add the escaped variables and the rest of the arguments to the + // list of arguments, and return the correct value. + // FIXME DONE: Some code was deleted here. + const auto function_type = dynamic_cast<const type::Function*>(e.def_get()->type_get()); + + precondition(function_type != nullptr); + + std::string function_name = e.name_get().get(); + + if (e.def_get()->body_get() == nullptr) + { + // then the call references a primitive + function_name = "tc_" + function_name; + } + + llvm::Function* function = module_.getFunction(function_name); + std::vector<llvm::Value*> args; + std::string twine = "call_" + e.name_get().get(); + + assertion(function != nullptr); + + for (auto& var : escaped_[function_type]) + { + args.push_back(translate(*var)); + } + + for (auto& parameter : e.args_get()) + { + llvm::Value* variable = translate(*parameter); + llvm::Value* value = dynamic_cast<ast::Var*>(parameter) != nullptr + ? get_dereferenced(variable, parameter->type_get()) + : variable; + args.push_back(value); + } + + if (dynamic_cast<const type::Void*>(&function_type->result_get().actual()) != nullptr) + { + twine = ""; + } + + value_ = builder_.CreateCall(function, args, twine); + } + + void Translator::operator()(const ast::VarDec& e) + { + // Void var types are actually Ints represented by a 0 + // FIXME DONE: Some code was deleted here. + if (const auto existing_ref = declaration_in_current_scope(e)) + { + value_ = existing_ref; + return; + } + + llvm::Type* variable_type = llvm_type(*e.type_get()); + + llvm::Value* init_value = translate(*e.init_get()); + + llvm::Value* variable = create_alloca(current_function_, variable_type, + "var_" + e.name_get().get()); + + locals_[current_function_][&e] = variable; + value_ = builder_.CreateStore(init_value, variable); + } + + llvm::Value* Translator::declaration_in_current_scope(const ast::VarDec& e) const + { + if (!locals_.contains(current_function_)) + { + return nullptr; + } + + const auto current_scope = locals_.at(current_function_); + + return current_scope.contains(&e) ? current_scope.at(&e) : nullptr; + } + +} // namespace llvmtranslate diff --git a/tiger-compiler/src/llvmtranslate/translator.hh b/tiger-compiler/src/llvmtranslate/translator.hh new file mode 100644 index 0000000..3ddb625 --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/translator.hh @@ -0,0 +1,145 @@ +/** + ** \file llvmtranslate/translator.hh + ** \brief Declaration of llvmtranslate::Translator + */ + +#pragma once + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-parameter" + +#include <llvm/IR/IRBuilder.h> +#include <llvm/IR/Module.h> +#include <llvm/IR/Value.h> + +#pragma GCC diagnostic pop + +#include <ast/default-visitor.hh> +#include <ast/non-assert-visitor.hh> +#include <ast/non-object-visitor.hh> +#include <llvmtranslate/fwd.hh> +#include <llvmtranslate/llvm-type-visitor.hh> + +namespace llvmtranslate +{ + class Translator + : public ast::DefaultConstVisitor + , public ast::NonObjectConstVisitor + , public ast::NonAssertConstVisitor + { + public: + /// Super class. + using super_type = ast::DefaultConstVisitor; + /// Import overloaded operator() methods. + using super_type::operator(); + + Translator(llvm::Module& module, escaped_map_type&& escaped); + + /// Run the translation. + void operator()(const ast::Ast& e) override; + + /// \brief Run this visitor on \a node, and return its translation. + /// + /// It is also guaranteed that \a value_ is set to it. + /// More generally, this routine saves from direct calls to \a accept. + llvm::Value* translate(const ast::Ast& node); + + /// \name Lvalues + /// \{ + void operator()(const ast::SimpleVar& e) override; + void operator()(const ast::FieldVar& e) override; + void operator()(const ast::SubscriptVar& e) override; + /// \} + + /// \name Expressions + /// \{ + void operator()(const ast::NilExp&) override; + void operator()(const ast::IntExp& e) override; + void operator()(const ast::StringExp& e) override; + void operator()(const ast::RecordExp& e) override; + void operator()(const ast::CallExp& e) override; + void operator()(const ast::OpExp& e) override; + void operator()(const ast::SeqExp& e) override; + void operator()(const ast::AssignExp& e) override; + void operator()(const ast::IfExp& e) override; + void operator()(const ast::WhileExp& e) override; + void operator()(const ast::BreakExp&) override; + void operator()(const ast::ArrayExp& e) override; + void operator()(const ast::CastExp& e) override; + /// \} + + /// \name Declarations + /// \{ + void operator()(const ast::FunctionChunk& e) override; + void visit_function_dec_header(const ast::FunctionDec& e); + void visit_function_dec_body(const ast::FunctionDec& e); + void operator()(const ast::VarDec& e) override; + + /** + * Check for the existence of a VarDec node within the current function + * scoped (locals_[current_function_]). + * + * If the node does exist within the scope, its LLVM reference is returned + * afterward. If not, nullptr is returned instead. + * + * @param e The node to look for + * @return The associated LLVM value if e does exist within the scope. + * nullptr otherwise + */ + llvm::Value* declaration_in_current_scope(const ast::VarDec& e) const; + + /// \} + + protected: + /// The translation of the last visited node. + llvm::Value* value_ = nullptr; + + /// The current function. + llvm::Function* current_function_ = nullptr; + + /// The module containing the metadata and this file's AST. + llvm::Module& module_; + + /// The global context of the translator. + llvm::LLVMContext& ctx_; + + /// IR builder to simplify building nodes and instructions. + llvm::IRBuilder<> builder_; + + /// Access for each "variable". + /// Since the AST doesn't contain the arguments added + /// for the lambda lifting, we need to identify them by their declaration. + std::map<const llvm::Function*, std::map<const ast::VarDec*, llvm::Value*>> + locals_; + + /// For each loop, the basic block immediately after it. + std::map<const ast::WhileExp*, llvm::BasicBlock*> loop_end_; + + /// Access every escaped variable for each function. + escaped_map_type escaped_; + + /// The llvm type translator. + LLVMTypeVisitor type_visitor_; + + /// Get a Tiger void value. + inline llvm::Value* get_void_value(); + + inline llvm::Value* get_dereferenced(llvm::Value* ptr, const type::Type* type); + + private: + /// Get a LLVM access to a variable, usually to be loaded right after. + llvm::Value* access_var(const ast::Var& e); + + /// Call the init_array function that allocates and initialize the array. + llvm::Value* init_array(llvm::Value* count_val, llvm::Value* init_val); + + /// Get a llvm::Type from a type::Type using the type_visitor_. + llvm::Type* llvm_type(const type::Type& type); + + /// Create a llvm function from a function type. + llvm::FunctionType* llvm_function_type(const type::Function& function_t); + }; + +} // namespace llvmtranslate + +#include <llvmtranslate/translator.hxx> diff --git a/tiger-compiler/src/llvmtranslate/translator.hxx b/tiger-compiler/src/llvmtranslate/translator.hxx new file mode 100644 index 0000000..a509d4d --- /dev/null +++ b/tiger-compiler/src/llvmtranslate/translator.hxx @@ -0,0 +1,30 @@ +/** + ** \file llvmtranslate/translator.hxx + ** \brief Inline methods for llvmtranslate::Translator. + */ + +#pragma once + +#include <llvmtranslate/translator.hh> + +namespace llvmtranslate +{ + + inline llvm::Value* Translator::get_void_value() + { + return builder_.getIntN(0, 0); + } + + inline llvm::Value* Translator::get_dereferenced(llvm::Value* ptr, + const type::Type* type) + { + if (!ptr->getType()->isPointerTy()) + { + return ptr; + } + + return builder_.CreateLoad(llvm_type(*type), ptr, ptr->getName() + "_dereferenced"); + } + + +} // namespace llvmtranslate |