MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
tail_rec_elim.cpp
Go to the documentation of this file.
2
3#include "mim/pass/eta_red.h"
4
5namespace mim {
6
8 : FPPass(man, "tail_rec_elim")
9 , eta_red_(man.find<EtaRed>()) {}
10
11const Def* TailRecElim::rewrite(const Def* def) {
12 if (auto [app, old] = isa_apped_mut_lam(def); old) {
13 if (auto i = old2rec_loop_.find(old); i != old2rec_loop_.end()) {
14 auto [rec, loop] = i->second;
15 auto args = app->args();
16 if (auto ret_var = rec->ret_var(); app->args().back() == ret_var)
17 return world().app(loop, args.view().rsubspan(1));
18 else
19 return world().app(rec, args);
20 }
21 }
22
23 return def;
24}
25
27 if (auto [app, old] = isa_apped_mut_lam(def); old) {
28 if (auto ret_var = old->ret_var(); ret_var && app->args().back() == ret_var) {
29 if (auto [i, ins] = old2rec_loop_.emplace(old, std::pair<Lam*, Lam*>(nullptr, nullptr)); ins) {
30 auto& [rec, loop] = i->second;
31 rec = old->stub(old->type());
32 auto doms = rec->doms();
33 auto loop_dom = doms.view().rsubspan(1);
34 loop = rec->stub(world().cn(loop_dom));
35 world().DLOG("old {} -> (rec: {}, loop: {})", old, rec, loop);
36
37 auto n = rec->num_doms();
38 DefVec loop_args(n - 1);
39 DefVec loop_vars(n);
40 for (size_t i = 0; i != n - 1; ++i) {
41 loop_args[i] = rec->var(i);
42 loop_vars[i] = loop->var(i);
43 }
44 loop_vars.back() = rec->vars().back();
45
46 loop->set(old->reduce(world().tuple(loop_vars)));
47 rec->app(false, loop, loop_args);
48 if (eta_red_) eta_red_->mark_irreducible(loop);
49
50 return undo_visit(old);
51 }
52 }
53 }
54
55 return No_Undo;
56}
57
58} // namespace mim
Base class for all Defs.
Definition def.h:251
Performs η-reduction.
Definition eta_red.h:9
FPPass(PassMan &man, std::string name)
Definition pass.h:268
undo_t undo_visit(Def *mut) const
Definition pass.h:303
An optimizer that combines several optimizations in an optimal way.
Definition pass.h:111
World & world()
Definition pass.h:326
PassMan & man()
Definition pass.h:34
TailRecElim(PassMan &)
undo_t analyze(const Def *) override
const Def * rewrite(const Def *) override
const Def * app(const Def *callee, const Def *arg)
Definition world.cpp:196
Definition ast.h:14
Vector< const Def * > DefVec
Definition def.h:77
std::pair< const App *, Lam * > isa_apped_mut_lam(const Def *def)
Definition lam.h:350
size_t undo_t
Definition pass.h:18
Value * find(IndexMap< Indexer, Key, Value * > &map, Key key)
Definition indexmap.h:71
static constexpr undo_t No_Undo
Definition pass.h:19