blob: cf933ef8ec67953815b233d69b2d2a98464a0924 [file]
/*
Copyright (c) 2018 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author: Leonardo de Moura
*/
#include "util/option_declarations.h"
#include "util/io.h"
#include "kernel/type_checker.h"
#include "kernel/kernel_exception.h"
#include "library/max_sharing.h"
#include "library/trace.h"
#include "library/time_task.h"
#include "library/compiler/util.h"
#include "library/compiler/lcnf.h"
#include "library/compiler/find_jp.h"
#include "library/compiler/cse.h"
#include "library/compiler/csimp.h"
#include "library/compiler/elim_dead_let.h"
#include "library/compiler/erase_irrelevant.h"
#include "library/compiler/specialize.h"
#include "library/compiler/eager_lambda_lifting.h"
#include "library/compiler/implemented_by_attribute.h"
#include "library/compiler/lambda_lifting.h"
#include "library/compiler/extract_closed.h"
#include "library/compiler/reduce_arity.h"
#include "library/compiler/ll_infer_type.h"
#include "library/compiler/simp_app_args.h"
#include "library/compiler/llnf.h"
#include "library/compiler/export_attribute.h"
#include "library/compiler/extern_attribute.h"
#include "library/compiler/struct_cases_on.h"
#include "library/compiler/ir.h"
namespace lean {
static name * g_extract_closed = nullptr;
bool is_extract_closed_enabled(options const & opts) { return opts.get_bool(*g_extract_closed, true); }
static name get_real_name(name const & n) {
if (optional<name> new_n = is_unsafe_rec_name(n))
return *new_n;
else
return n;
}
static comp_decls to_comp_decls(environment const & env, names const & cs) {
bool allow_opaque = true;
return map2<comp_decl>(cs, [&](name const & n) {
return comp_decl(get_real_name(n), env.get(n).get_value(allow_opaque));
});
}
static expr eta_expand(environment const & env, expr const & e) {
return type_checker(env).eta_expand(e);
}
template<typename F>
comp_decls apply(F && f, environment const & env, comp_decls const & ds) {
return map(ds, [&](comp_decl const & d) { return comp_decl(d.fst(), f(env, d.snd())); });
}
template<typename F>
comp_decls apply(F && f, comp_decls const & ds) {
return map(ds, [&](comp_decl const & d) { return comp_decl(d.fst(), f(d.snd())); });
}
void trace_comp_decl(comp_decl const & d) {
tout() << ">> " << d.fst() << "\n" << trace_pp_expr(d.snd()) << "\n";
}
void trace_comp_decls(comp_decls const & ds) {
for (comp_decl const & d : ds) {
trace_comp_decl(d);
}
}
static environment cache_stage1(environment env, comp_decls const & ds) {
for (comp_decl const & d : ds) {
name n = d.fst();
expr v = d.snd();
constant_info info = env.get(n);
env = register_stage1_decl(env, n, info.get_lparams(), info.get_type(), v);
}
return env;
}
static expr ensure_arity(expr const & t, unsigned arity) {
if (arity == 0) {
if (is_pi(t)) return mk_enf_object_type(); // closure
else return t;
}
lean_assert(is_pi(t));
return update_binding(t, binding_domain(t), ensure_arity(binding_body(t), arity-1));
}
static environment cache_stage2(environment env, comp_decls const & ds, bool only_new_ones = false) {
buffer<expr> ts;
ll_infer_type(env, ds, ts);
lean_assert(ts.size() == length(ds));
unsigned i = 0;
for (comp_decl const & d : ds) {
name n = d.fst();
expr v = d.snd();
if (!only_new_ones || !is_stage2_decl(env, n)) {
expr t = ts[i];
unsigned arity = get_num_nested_lambdas(v);
t = ensure_arity(t, arity);
lean_trace(name({"compiler", "stage2"}), tout() << n << " : " << t << "\n";);
lean_trace(name({"compiler", "ll_infer_type"}), tout() << n << " : " << t << "\n";);
env = register_stage2_decl(env, n, t, v);
}
i++;
}
return env;
}
/* Cache the declarations in `ds` that have not already been cached. */
static environment cache_new_stage2(environment env, comp_decls const & ds) {
return cache_stage2(env, ds, true);
}
bool is_main_fn(environment const & env, name const & n) {
if (n == "main") return true;
if (optional<name> c = get_export_name_for(env, n)) {
return *c == "main";
}
return false;
}
bool is_uint32_or_unit(expr const & type) {
return
is_constant(type, get_uint32_name()) ||
is_constant(type, get_unit_name()) ||
is_constant(type, get_punit_name());
}
/* Return true iff type is `(List String ->) IO (UInt32 | (P)Unit)` */
bool is_main_fn_type(expr const & type) {
if (is_arrow(type)) {
expr d = binding_domain(type);
expr r = binding_body(type);
return
is_app(r) &&
is_constant(app_fn(r), get_io_name()) &&
is_uint32_or_unit(app_arg(r)) &&
is_app(d) &&
is_constant(app_fn(d), get_list_name()) &&
is_constant(app_arg(d), get_string_name());
} else if (is_app(type)) {
return
is_constant(app_fn(type), get_io_name()) &&
is_uint32_or_unit(app_arg(type));
} else {
return false;
}
}
#define trace_compiler(k, ds) lean_trace(k, trace_comp_decls(ds););
extern "C" object* lean_csimp_replace_constants(object* env, object* n);
expr csimp_replace_constants(environment const & env, expr const & e) {
return expr(lean_csimp_replace_constants(env.to_obj_arg(), e.to_obj_arg()));
}
bool is_matcher(environment const & env, comp_decls const & ds) {
return length(ds) == 1 && is_matcher(env, head(ds).fst());
}
environment compile(environment const & env, options const & opts, names cs) {
/* Do not generate code for irrelevant decls */
cs = filter(cs, [&](name const & c) { return !is_irrelevant_type(env, env.get(c).get_type());});
if (empty(cs)) return env;
for (name const & c : cs) {
if (is_main_fn(env, c) && !is_main_fn_type(env.get(c).get_type())) {
throw exception("invalid `main` function, it must have type `List String -> IO UInt32`");
}
}
if (length(cs) == 1) {
name c = get_real_name(head(cs));
if (has_implemented_by_attribute(env, c))
return env;
if (is_extern_or_init_constant(env, c)) {
/* Generate boxed version for extern/native constant if needed. */
return ir::add_extern(env, c);
}
}
for (name const & c : cs) {
lean_assert(!is_extern_constant(env, get_real_name(c)));
constant_info cinfo = env.get(c);
if (!cinfo.is_definition() && !cinfo.is_opaque()) return env;
}
time_task t("compilation", opts, head(cs));
scope_trace_env scope_trace(env, opts);
comp_decls ds = to_comp_decls(env, cs);
csimp_cfg cfg(opts);
// Use the following line to see compiler intermediate steps
// scope_traces_as_string trace_scope;
auto simp = [&](environment const & env, expr const & e) { return csimp(env, e, cfg); };
auto esimp = [&](environment const & env, expr const & e) { return cesimp(env, e, cfg); };
trace_compiler(name({"compiler", "input"}), ds);
ds = apply(eta_expand, env, ds);
trace_compiler(name({"compiler", "eta_expand"}), ds);
ds = apply(to_lcnf, env, ds);
ds = apply(find_jp, env, ds);
// trace(ds);
trace_compiler(name({"compiler", "lcnf"}), ds);
// trace(ds);
ds = apply(cce, env, ds);
trace_compiler(name({"compiler", "cce"}), ds);
ds = apply(csimp_replace_constants, env, ds);
ds = apply(simp, env, ds);
trace_compiler(name({"compiler", "simp"}), ds);
// trace(ds);
environment new_env = env;
std::tie(new_env, ds) = eager_lambda_lifting(new_env, ds, cfg);
trace_compiler(name({"compiler", "eager_lambda_lifting"}), ds);
ds = apply(max_sharing, ds);
trace_compiler(name({"compiler", "stage1"}), ds);
new_env = cache_stage1(new_env, ds);
if (is_matcher(new_env, ds)) {
/* Auxiliary matcher applications are marked as inlined, and are always fully applied
(if users don't use them manually). So, we skip code generation for them.
By caching stage1, we make sure we have all information we need to inline them.
TODO: we should have a "[strong_inline]" annotation that will inline a definition even
when it is partially applied. Then, we can mark all `match` auxiliary functions as `[strong_inline]` */
return new_env;
}
std::tie(new_env, ds) = specialize(new_env, ds, cfg);
// The following check is incorrect. It was exposed by issue #1812.
// We will not fix the check since we will delete the compiler.
// lean_assert(lcnf_check_let_decls(new_env, ds));
trace_compiler(name({"compiler", "specialize"}), ds);
ds = apply(elim_dead_let, ds);
trace_compiler(name({"compiler", "elim_dead_let"}), ds);
ds = apply(erase_irrelevant, new_env, ds);
trace_compiler(name({"compiler", "erase_irrelevant"}), ds);
ds = apply(struct_cases_on, new_env, ds);
trace_compiler(name({"compiler", "struct_cases_on"}), ds);
ds = apply(esimp, new_env, ds);
trace_compiler(name({"compiler", "simp"}), ds);
ds = reduce_arity(new_env, ds);
trace_compiler(name({"compiler", "reduce_arity"}), ds);
std::tie(new_env, ds) = lambda_lifting(new_env, ds);
trace_compiler(name({"compiler", "lambda_lifting"}), ds);
// trace(ds);
ds = apply(esimp, new_env, ds);
trace_compiler(name({"compiler", "simp"}), ds);
new_env = cache_stage2(new_env, ds);
trace_compiler(name({"compiler", "stage2"}), ds);
if (is_extract_closed_enabled(opts)) {
std::tie(new_env, ds) = extract_closed(new_env, ds);
ds = apply(elim_dead_let, ds);
ds = apply(esimp, new_env, ds);
trace_compiler(name({"compiler", "extract_closed"}), ds);
}
new_env = cache_new_stage2(new_env, ds);
ds = apply(esimp, new_env, ds);
trace_compiler(name({"compiler", "simp"}), ds);
ds = apply(simp_app_args, new_env, ds);
ds = apply(ecse, new_env, ds);
ds = apply(elim_dead_let, ds);
trace_compiler(name({"compiler", "simp_app_args"}), ds);
// std::cout << trace_scope.get_string() << "\n";
/* compile IR. */
return compile_ir(new_env, opts, ds);
}
extern "C" LEAN_EXPORT object * lean_compile_decls(object * env, object * opts, object * decls) {
return catch_kernel_exceptions<environment>([&]() {
return compile(environment(env), options(opts, true), names(decls, true));
});
}
void initialize_compiler() {
g_extract_closed = new name{"compiler", "extract_closed"};
mark_persistent(g_extract_closed->raw());
register_bool_option(*g_extract_closed, true, "(compiler) enable/disable closed term caching");
register_trace_class("compiler");
register_trace_class({"compiler", "input"});
register_trace_class({"compiler", "inline"});
register_trace_class({"compiler", "eta_expand"});
register_trace_class({"compiler", "lcnf"});
register_trace_class({"compiler", "cce"});
register_trace_class({"compiler", "simp"});
register_trace_class({"compiler", "simp_detail"});
register_trace_class({"compiler", "simp_float_cases"});
register_trace_class({"compiler", "elim_dead_let"});
register_trace_class({"compiler", "cse"});
register_trace_class({"compiler", "specialize"});
register_trace_class({"compiler", "stage1"});
register_trace_class({"compiler", "stage2"});
register_trace_class({"compiler", "erase_irrelevant"});
register_trace_class({"compiler", "eager_lambda_lifting"});
register_trace_class({"compiler", "lambda_lifting"});
register_trace_class({"compiler", "extract_closed"});
register_trace_class({"compiler", "reduce_arity"});
register_trace_class({"compiler", "simp_app_args"});
register_trace_class({"compiler", "struct_cases_on"});
register_trace_class({"compiler", "llnf"});
register_trace_class({"compiler", "result"});
register_trace_class({"compiler", "optimize_bytecode"});
register_trace_class({"compiler", "code_gen"});
register_trace_class({"compiler", "ll_infer_type"});
register_trace_class({"compiler", "ir"});
register_trace_class({"compiler", "ir", "init"});
register_trace_class({"compiler", "ir", "push_proj"});
register_trace_class({"compiler", "ir", "reset_reuse"});
register_trace_class({"compiler", "ir", "elim_dead_branches"});
register_trace_class({"compiler", "ir", "elim_dead"});
register_trace_class({"compiler", "ir", "simp_case"});
register_trace_class({"compiler", "ir", "borrow"});
register_trace_class({"compiler", "ir", "boxing"});
register_trace_class({"compiler", "ir", "rc"});
register_trace_class({"compiler", "ir", "expand_reset_reuse"});
register_trace_class({"compiler", "ir", "result"});
}
void finalize_compiler() {
delete g_extract_closed;
}
}