MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
eta_exp.cpp
Go to the documentation of this file.
1#include "mim/pass/eta_exp.h"
2
3#include "mim/pass/eta_red.h"
4
5using namespace std::literals;
6
7namespace mim {
8
11 eta_red_ = man->find<EtaRed>();
12}
13
15 if (auto old = lookup(new2old_, new_lam)) {
16 auto root = new2old(old); // path compression
17 assert(root != new_lam);
18 new2old_[new_lam] = root;
19 return root;
20 }
21
22 return new_lam;
23}
24
25const Def* EtaExp::rewrite(const Def* def) {
26 if (std::ranges::none_of(def->ops(), [](const Def* def) { return def->isa<Lam>(); })) return def;
27 if (auto n = lookup(old2new(), def)) return n;
28
29 auto [i, ins] = def2new_ops_.emplace(def, DefVec{});
30 auto& new_ops = i->second;
31 if (ins) new_ops.assign(def->ops().begin(), def->ops().end());
32
33 for (size_t i = 0, e = def->num_ops(); i != e; ++i) {
34 if (auto lam = def->op(i)->isa_mut<Lam>(); lam && lam->is_set()) {
35 if (isa_callee(def, i)) {
36 if (auto orig = lookup(exp2orig_, lam)) new_ops[i] = orig;
37 } else if (expand_.contains(lam)) {
38 if (new_ops[i] == lam) new_ops[i] = eta_exp(lam);
39 } else if (auto orig = lookup(exp2orig_, lam)) {
40 if (new_ops[i] == lam) new_ops[i] = eta_exp(orig);
41 }
42 }
43 }
44
45 auto new_def = def->rebuild(def->type(), new_ops);
46 return old2new()[new_def] = new_def;
47}
48
49Lam* EtaExp::eta_exp(Lam* lam) {
50 auto exp = lam->stub(lam->type());
51 exp2orig_.emplace(exp, lam);
52 exp->debug_suffix("eta_"s + lam->sym().str());
53 exp->app(false, lam, exp->var());
54 if (eta_red_) eta_red_->mark_irreducible(exp);
55 return exp;
56}
57
59 DLOG("found proxy: {}", proxy);
60 auto lam = proxy->op(0)->as_mut<Lam>();
61 if (expand_.emplace(lam).second) return undo_visit(lam);
62 return No_Undo;
63}
64
66 auto undo = No_Undo;
67 for (size_t i = 0, e = def->num_ops(); i != e; ++i) {
68 if (auto lam = def->op(i)->isa_mut<Lam>(); lam && lam->is_set()) {
69 lam = new2old(lam);
70 if (expand_.contains(lam) || exp2orig_.contains(lam)) continue;
71
72 if (isa_callee(def, i)) {
73 if (auto [_, p] = *pos().emplace(lam, Pos::Callee).first; p == Pos::Non_Callee_1) {
74 DLOG("Callee: Callee -> Expand: '{}'", lam);
75 expand_.emplace(lam);
76 undo = std::min(undo, undo_visit(lam));
77 } else {
78 DLOG("Callee: Bot/Callee -> Callee: '{}'", lam);
79 }
80 } else {
81 auto [it, first] = pos().emplace(lam, Pos::Non_Callee_1);
82
83 if (first) {
84 DLOG("Non_Callee: Bot -> Non_Callee_1: '{}'", lam);
85 } else {
86 DLOG("Non_Callee: {} -> Expand: '{}'", pos2str(it->second), lam);
87 expand_.emplace(lam);
88 undo = std::min(undo, undo_visit(lam));
89 }
90 }
91 }
92 }
93
94 return undo;
95}
96
97} // namespace mim
Base class for all Defs.
Definition def.h:251
bool is_set() const
Yields true if empty or the last op is set.
Definition def.cpp:298
constexpr auto ops() const noexcept
Definition def.h:305
T * isa_mut() const
If this is mutable, it will cast constness away and perform a dynamic_cast to T.
Definition def.h:482
const Def * op(size_t i) const noexcept
Definition def.h:308
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
Definition def.h:295
const Def * rebuild(World &w, const Def *type, Defs ops) const
Def::rebuilds this Def while using new_op as substitute for its i'th Def::op.
Definition def.h:545
Sym sym() const
Definition def.h:504
constexpr size_t num_ops() const noexcept
Definition def.h:309
void new2old(Lam *new_lam, Lam *old_lam)
Definition eta_exp.h:23
undo_t analyze(const Proxy *) override
Definition eta_exp.cpp:58
void init(PassMan *) final
Definition eta_exp.cpp:9
const Def * rewrite(const Def *) override
Definition eta_exp.cpp:25
@ Non_Callee_1
Definition eta_exp.h:41
static std::string_view pos2str(Pos pos)
Definition eta_exp.h:42
auto & old2new()
Definition eta_exp.h:45
const Proxy * proxy(Lam *lam)
Definition eta_exp.h:22
auto & pos()
Definition eta_exp.h:46
Performs η-reduction.
Definition eta_red.h:9
void mark_irreducible(Lam *lam)
Definition eta_red.h:27
undo_t undo_visit(Def *mut) const
Definition pass.h:360
A function.
Definition lam.h:111
const Pi * type() const
Definition lam.h:131
Lam * stub(const Def *type)
Definition lam.h:185
An optimizer that combines several optimizations in an optimal way.
Definition pass.h:172
virtual void init(PassMan *)
Definition pass.cpp:30
PassMan & man()
Definition pass.h:97
#define DLOG(...)
Vaporizes to nothingness in Debug build.
Definition log.h:95
Definition ast.h:14
Vector< const Def * > DefVec
Definition def.h:77
auto lookup(const C &container, const K &key)
Yields pointer to element (or the element itself if it is already a pointer), if found and nullptr ot...
Definition util.h:100
const App * isa_callee(const Def *def, size_t i)
Definition lam.h:346
size_t undo_t
Definition pass.h:21
static constexpr undo_t No_Undo
Definition pass.h:22