MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
eta_exp.h
Go to the documentation of this file.
1#pragma once
2
3#include "mim/pass.h"
4
5namespace mim {
6
7class EtaRed;
8
9/// Performs η-expansion:
10/// `f -> λx.f x`, if `f` is a Lam with more than one user and does not appear in callee position.
11/// This rule is a generalization of critical edge elimination.
12/// It gives other Pass%es such as SSAConstr the opportunity to change `f`'s signature (e.g. adding or removingp Var%s).
13class EtaExp : public FPPass<EtaExp, Lam> {
14public:
17
18 void init(PassMan*) final;
19
20 /// @name interface for other passes
21 ///@{
22 const Proxy* proxy(Lam* lam) { return FPPass<EtaExp, Lam>::proxy(lam->type(), {lam}, 0); }
23 void new2old(Lam* new_lam, Lam* old_lam) { new2old_[new_lam] = old_lam; }
24 Lam* new2old(Lam* new_lam);
25 ///@}
26
27 /// @name Lattice
28 /// EtaExp uses the following lattice:
29 /// ```
30 /// expand_ <-- η-expand non-callee as the Lam occurs more than once.
31 /// / \ Don't η-reduce the expansion again.
32 /// Callee Non_Callee_1 <-- Pos: Either multiple callees, **or** exactly one non-callee are okay.
33 /// \ /
34 /// Bot <-- Never seen.
35 /// ```
36 /// * EtaExp::expand_ trackes if a Lam is the top element.
37 /// * If it's not within EtaExp::expand_, it's either `Pos` or `Bot`.
38 /// But there is no need to differentiate this any further.
39 /// * EtaExp::Pos tracks the particular element at that level and is memorized statefully.
40 ///@{
41 enum Pos : bool { Callee, Non_Callee_1 };
42 static std::string_view pos2str(Pos pos) { return pos == Callee ? "Callee" : "Non_Callee_1"; }
43
44 using Data = std::tuple<Def2Def, LamMap<Pos>>;
45 auto& old2new() { return data<0>(); }
46 auto& pos() { return data<1>(); }
47 ///@}
48
49private:
50 /// @name PassMan hooks
51 ///@{
52 const Def* rewrite(const Def*) override;
53 undo_t analyze(const Proxy*) override;
54 undo_t analyze(const Def*) override;
55 ///@}
56 Lam* eta_exp(Lam*); ///< Helper that peforms the actual η-expansion.
57
58 EtaRed* eta_red_;
59 LamSet expand_;
60 Lam2Lam exp2orig_;
61 Lam2Lam new2old_;
62 DefMap<DefVec> def2new_ops_;
63};
64
65} // namespace mim
Base class for all Defs.
Definition def.h:251
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
EtaExp(World &world, flags_t annex)
Definition eta_exp.h:15
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
std::tuple< Def2Def, LamMap< Pos > > Data
Definition eta_exp.h:44
auto & pos()
Definition eta_exp.h:46
Performs η-reduction.
Definition eta_red.h:9
FPPass(World &world, std::string name)
Definition pass.h:323
A function.
Definition lam.h:111
const Pi * type() const
Definition lam.h:131
An optimizer that combines several optimizations in an optimal way.
Definition pass.h:172
const Proxy * proxy(const Def *type, Defs ops, u32 tag=0)
Definition pass.h:141
World & world()
Definition pass.h:64
flags_t annex() const
Definition pass.h:68
The World represents the whole program and manages creation of MimIR nodes (Defs).
Definition world.h:36
Definition ast.h:14
GIDSet< Lam * > LamSet
Definition lam.h:221
u64 flags_t
Definition types.h:45
GIDMap< const Def *, To > DefMap
Definition def.h:73
LamMap< Lam * > Lam2Lam
Definition lam.h:222
size_t undo_t
Definition pass.h:21