summaryrefslogtreecommitdiff
path: root/tiger-compiler/src/inlining
diff options
context:
space:
mode:
Diffstat (limited to 'tiger-compiler/src/inlining')
-rw-r--r--tiger-compiler/src/inlining/inliner.cc64
-rw-r--r--tiger-compiler/src/inlining/inliner.hh44
-rw-r--r--tiger-compiler/src/inlining/libinlining.cc54
-rw-r--r--tiger-compiler/src/inlining/libinlining.hh42
-rw-r--r--tiger-compiler/src/inlining/local.am8
-rw-r--r--tiger-compiler/src/inlining/pruner.cc34
-rw-r--r--tiger-compiler/src/inlining/pruner.hh42
-rw-r--r--tiger-compiler/src/inlining/tasks.cc31
-rw-r--r--tiger-compiler/src/inlining/tasks.hh36
9 files changed, 355 insertions, 0 deletions
diff --git a/tiger-compiler/src/inlining/inliner.cc b/tiger-compiler/src/inlining/inliner.cc
new file mode 100644
index 0000000..85bbc88
--- /dev/null
+++ b/tiger-compiler/src/inlining/inliner.cc
@@ -0,0 +1,64 @@
+/**
+ ** \file inlining/inliner.cc
+ ** \brief Implementation of inlining::Inliner.
+ */
+
+#include <boost/graph/transitive_closure.hpp>
+
+#include <ranges>
+#include <callgraph/libcallgraph.hh>
+#include <inlining/inliner.hh>
+#include <parse/libparse.hh>
+#include <parse/tweast.hh>
+
+namespace inlining
+{
+ using namespace ast;
+
+ Inliner::Inliner(const ast::Ast& tree)
+ : super_type()
+ , rec_funs_()
+ {
+ // Compute the transitive closure of the call graph to compute the
+ // set of recursive functions.
+ const callgraph::CallGraph* graph = callgraph::callgraph_compute(tree);
+ callgraph::CallGraph closure;
+ boost::transitive_closure(*graph, closure);
+
+ // Compute the parent graph to get nested functions.
+ const callgraph::ParentGraph* parentGraph =
+ callgraph::parentgraph_compute(const_cast<ast::Ast&>(tree));
+
+ // Re-attach properties to the vertices.
+ for (auto [i, i_end] = boost::vertices(closure); i != i_end; ++i)
+ closure[*i] = (*graph)[*i];
+ // Detect recursive functions.
+ for (auto [i, i_end] = boost::vertices(closure); i != i_end; ++i)
+ {
+ for (auto [j, j_end] = boost::adjacent_vertices(*i, closure);
+ j != j_end; ++j)
+ {
+ // Check all parent functions to detect cases like these :
+ // function a() =
+ // (
+ // let
+ // function b() = a()
+ // in
+ // end
+ // )
+ if (parentGraph->hfundec_deep_get(closure[*i], closure[*j]))
+ rec_funs_.insert(closure[*j]);
+ }
+ }
+ delete graph;
+ delete parentGraph;
+ }
+
+ const misc::set<const ast::FunctionDec*>& Inliner::rec_funs_get() const
+ {
+ return rec_funs_;
+ }
+
+ // FIXME: Some code was deleted here.
+
+} // namespace inlining
diff --git a/tiger-compiler/src/inlining/inliner.hh b/tiger-compiler/src/inlining/inliner.hh
new file mode 100644
index 0000000..fc2f71f
--- /dev/null
+++ b/tiger-compiler/src/inlining/inliner.hh
@@ -0,0 +1,44 @@
+/**
+ ** \file inlining/inliner.hh
+ ** \brief Declaration of inlining::Inliner.
+ */
+
+#pragma once
+
+#include <map>
+
+#include <ast/function-dec.hh>
+#include <astclone/cloner.hh>
+#include <misc/scoped-map.hh>
+#include <misc/set.hh>
+
+namespace inlining
+{
+ /// Perform inline expansion of functions.
+ class Inliner : public astclone::Cloner
+ {
+ public:
+ using super_type = astclone::Cloner;
+
+ // Import overloaded virtual functions.
+ using super_type::operator();
+
+ /// Build an Inliner.
+ Inliner(const ast::Ast& tree);
+
+ /// \name Visit methods.
+ /// \{
+ // FIXME: Some code was deleted here.
+ /// \}
+
+ /// \name Getters.
+ /// \{
+ const misc::set<const ast::FunctionDec*>& rec_funs_get() const;
+ /// \}
+
+ private:
+ /// Recursive functions of the program.
+ misc::set<const ast::FunctionDec*> rec_funs_;
+ };
+
+} // namespace inlining
diff --git a/tiger-compiler/src/inlining/libinlining.cc b/tiger-compiler/src/inlining/libinlining.cc
new file mode 100644
index 0000000..3f6e6b9
--- /dev/null
+++ b/tiger-compiler/src/inlining/libinlining.cc
@@ -0,0 +1,54 @@
+/**
+ ** \file inlining/libinlining.cc
+ ** \brief Functions exported by the inlining module.
+ */
+
+#include <memory>
+
+#include <ast/exp.hh>
+#include <desugar/libdesugar.hh>
+#include <inlining/inliner.hh>
+#include <inlining/libinlining.hh>
+#include <inlining/pruner.hh>
+
+namespace inlining
+{
+ /*-----------.
+ | Inlining. |
+ `-----------*/
+
+ template <typename A> A* inline_expand(const A& tree)
+ {
+ // Inline.
+ Inliner inline_expand(tree);
+ inline_expand(tree);
+ A* inlined = dynamic_cast<A*>(inline_expand.result_get());
+ assertion(inlined);
+ std::unique_ptr<A> inlined_ptr(inlined);
+ // Recompute the bindings and the types.
+ desugar::bind_and_types_check(*inlined_ptr);
+ return inlined_ptr.release();
+ }
+
+ template ast::ChunkList* inline_expand(const ast::ChunkList&);
+
+ /*-------------------.
+ | Function pruning. |
+ `-------------------*/
+
+ template <typename A> A* prune(const A& tree)
+ {
+ // Prune unused functions.
+ Pruner prune;
+ prune(tree);
+ A* pruned = dynamic_cast<A*>(prune.result_get());
+ assertion(pruned);
+ std::unique_ptr<A> pruned_ptr(pruned);
+ // Recompute the bindings and the types.
+ desugar::bind_and_types_check(*pruned_ptr);
+ return pruned_ptr.release();
+ }
+
+ template ast::ChunkList* prune(const ast::ChunkList&);
+
+} // namespace inlining
diff --git a/tiger-compiler/src/inlining/libinlining.hh b/tiger-compiler/src/inlining/libinlining.hh
new file mode 100644
index 0000000..183349a
--- /dev/null
+++ b/tiger-compiler/src/inlining/libinlining.hh
@@ -0,0 +1,42 @@
+/**
+ ** \file inlining/libinlining.hh
+ ** \brief Declare functions exported by the inlining module.
+ */
+
+#pragma once
+
+#include <ast/fwd.hh>
+#include <misc/error.hh>
+
+/// Inlining functions of an ast::Ast.
+namespace inlining
+{
+ /*-----------.
+ | Inlining. |
+ `-----------*/
+
+ /** Perform inline expansion of function bodies.
+
+ \param tree abstract syntax tree's root, whose bindings and types
+ have been computed. Each identifier must also be unique
+ within the AST to avoid name capture.
+
+ \return the AST where the bodies of non recursive functions have
+ been expanded (inlined), with bindings and type-checked.
+ */
+ template <typename A> A* inline_expand(const A& tree);
+
+ /*-------------------.
+ | Function pruning. |
+ `-------------------*/
+
+ /** Prune unused function from the AST.
+
+ \param tree abstract syntax tree's root, whose bindings and types
+ have been computed, and whose identifiers are all unique.
+
+ \return the AST whose unused functions have been removed, with
+ bindings and type-checked. */
+ template <typename A> A* prune(const A& tree);
+
+} // namespace inlining
diff --git a/tiger-compiler/src/inlining/local.am b/tiger-compiler/src/inlining/local.am
new file mode 100644
index 0000000..7a127bd
--- /dev/null
+++ b/tiger-compiler/src/inlining/local.am
@@ -0,0 +1,8 @@
+## inlining module.
+src_libtc_la_SOURCES += \
+ %D%/inliner.hh %D%/inliner.cc \
+ %D%/pruner.hh %D%/pruner.cc \
+ %D%/libinlining.hh %D%/libinlining.cc
+
+
+TASKS += %D%/tasks.hh %D%/tasks.cc
diff --git a/tiger-compiler/src/inlining/pruner.cc b/tiger-compiler/src/inlining/pruner.cc
new file mode 100644
index 0000000..edb20eb
--- /dev/null
+++ b/tiger-compiler/src/inlining/pruner.cc
@@ -0,0 +1,34 @@
+/**
+ ** \file inlining/pruner.cc
+ ** \brief Implementation of inlining::Pruner.
+ */
+
+#include <inlining/pruner.hh>
+
+namespace inlining
+{
+ using namespace ast;
+
+ ast::FunctionChunk* Pruner::prune(ast::FunctionChunk& e)
+ {
+ while (true)
+ {
+ auto [remove_begin, remove_end] =
+ std::ranges::remove_if(e, [&](ast::FunctionDec* func_dec) {
+ if (!func_dec->body_get() || func_dec->name_get() == "_main")
+ return false;
+ else
+ return called_functions_[func_dec->name_get()] == 0;
+ });
+
+ if (remove_begin == remove_end)
+ break;
+ e.erase(remove_begin, remove_end);
+ }
+
+ return new FunctionChunk(e.location_get(), &e.decs_get());
+ }
+
+ // FIXME: Some code was deleted here.
+
+} // namespace inlining
diff --git a/tiger-compiler/src/inlining/pruner.hh b/tiger-compiler/src/inlining/pruner.hh
new file mode 100644
index 0000000..30a0609
--- /dev/null
+++ b/tiger-compiler/src/inlining/pruner.hh
@@ -0,0 +1,42 @@
+/**
+ ** \file inlining/pruner.hh
+ ** \brief Declaration of inlining::Pruner.
+ */
+
+#pragma once
+
+#include <map>
+
+#include <astclone/cloner.hh>
+#include <misc/set.hh>
+
+namespace inlining
+{
+ /// Prune useless function declarations within an AST.
+ class Pruner : public astclone::Cloner
+ {
+ public:
+ using super_type = astclone::Cloner;
+
+ // Import overloaded virtual functions.
+ using super_type::operator();
+
+ using func_vect = std::vector<ast::FunctionDec*>;
+ using func_count = std::map<misc::symbol, int>;
+
+ /// \name Visit methods.
+ /// \{
+ // FIXME: Some code was deleted here.
+ /// \}
+
+ ast::FunctionChunk* prune(ast::FunctionChunk& e);
+
+ private:
+ // Keep track of current nested functions
+ std::vector<const ast::FunctionDec*> current_functions_;
+
+ // Associate function dec with the number of CallExp calling it
+ func_count called_functions_;
+ };
+
+} // namespace inlining
diff --git a/tiger-compiler/src/inlining/tasks.cc b/tiger-compiler/src/inlining/tasks.cc
new file mode 100644
index 0000000..f812d03
--- /dev/null
+++ b/tiger-compiler/src/inlining/tasks.cc
@@ -0,0 +1,31 @@
+/**
+ ** \file inlining/tasks.cc
+ ** \brief Inlining module related tasks' implementation.
+ **/
+
+#include <ast/tasks.hh>
+#include <astclone/libastclone.hh>
+#include <common.hh>
+#include <inlining/libinlining.hh>
+#define DEFINE_TASKS 1
+#include <inlining/tasks.hh>
+#undef DEFINE_TASKS
+
+namespace inlining::tasks
+{
+ /*-----------.
+ | Inlining. |
+ `-----------*/
+
+ void inline_expand()
+ {
+ astclone::apply(::inlining::inline_expand, ast::tasks::the_program);
+ }
+
+ /*-------------------.
+ | Function pruning. |
+ `-------------------*/
+
+ void prune() { astclone::apply(::inlining::prune, ast::tasks::the_program); }
+
+} // namespace inlining::tasks
diff --git a/tiger-compiler/src/inlining/tasks.hh b/tiger-compiler/src/inlining/tasks.hh
new file mode 100644
index 0000000..6c190ed
--- /dev/null
+++ b/tiger-compiler/src/inlining/tasks.hh
@@ -0,0 +1,36 @@
+/**
+ ** \file inlining/tasks.hh
+ ** \brief Inlining module tasks.
+ */
+
+#pragma once
+
+#include <config.h>
+#include <misc/fwd.hh>
+#include <task/libtask.hh>
+
+namespace inlining::tasks
+{
+ TASK_GROUP("Inlining");
+
+ /*-----------.
+ | Inlining. |
+ `-----------*/
+
+ /// Expand the body of functions at the call sites.
+ TASK_DECLARE("inline",
+ "inline functions",
+ inline_expand,
+ "types-compute rename");
+
+ /*-------------------.
+ | Function pruning. |
+ `-------------------*/
+
+ /// Prune unused function definitions from the AST.
+ TASK_DECLARE("prune",
+ "prune unused functions",
+ prune,
+ "rename types-compute");
+
+} // namespace inlining::tasks
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-14 19:42:45 +0000