eta_conv.cpp

Go to the documentation of this file.

#include "mim/phase/eta_conv.h"
 
namespace mim {
 
bool EtaConv::analyze() {
    for (auto def : old_world().externals().muts())
        visit(def, Lattice::Known);
    return false; // no fixed-point necessary
}
 
void EtaConv::analyze(const Def* def) {
    if (auto [_, ins] = analyzed_.emplace(def); !ins) return;
 
    if (auto app = def->isa<App>()) {
        // clang-format off
        visit(app->type(),   Lattice::Unknown_1);
        visit(app->callee(), Lattice::Known);
        visit(app->arg(),    Lattice::Unknown_1);
        // clang-format on
    } else {
        for (auto d : def->deps())
            visit(d, Lattice::Unknown_1);
    }
}
 
void EtaConv::visit(const Def* def, Lattice l) {
    // Wrapper-transparency: a use of `λx.f x` counts as a use of `f` at the same lattice `l`.
    // Do *not* descend into the wrapper's body (which would classify `f` as Known).
    if (auto f = Lam::eta_reduce(def)) return visit(f, l);
    if (auto lam = def->isa_mut<Lam>()) join(lam, l);
    analyze(def);
}
 
const Def* EtaConv::rewrite(const Def* old_def) {
    if (auto lam = old_def->isa<Lam>()) {
        if (auto f = Lam::eta_reduce(lam)) {
            // η-redex `λx.f x`: reduce unless `f` wants to stay expanded.
            if (!expand(f)) return rewrite_no_exp(lam);
            // Keep it - but as a *fresh* expansion wrapper (with a `tt` filter), so that a
            // pre-existing wrapper's stale filter does not leak downstream and every occurrence gets its own.
            return Lam::eta_expand(rewrite_no_eta(f));
        } else if (expand(lam)) {
            // bare Lam used in an unknown position more than once or in both positions: η-expand.
            profile_count("η-expansion");
            auto eta = Lam::eta_expand(rewrite_no_eta(lam));
            log().d("eta-expand {} → {}", lam, eta);
            invalidate();
            return eta;
        }
    }
 
    return RWPhase::rewrite(old_def);
}
 
const Def* EtaConv::rewrite_no_exp(const Def* old_def) {
    if (auto f = Lam::eta_reduce(old_def); f && !expand(f)) {
        profile_count("η-reduction");
        log().d("eta-reduce {} → {}", old_def, f);
        invalidate();
        return rewrite_no_eta(f);
    }
    return rewrite_no_eta(old_def);
}
 
const Def* EtaConv::rewrite_imm_App(const App* app) {
    auto callee = rewrite_no_exp(app->callee());
    return new_world().app(callee, rewrite(app->arg()));
}
 
const Def* EtaConv::rewrite_imm_Var(const Var* var) { return new_world().var(rewrite_no_eta(var->binder())->as_mut()); }
 
} // namespace mim