MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
lattice.h
Go to the documentation of this file.
1#pragma once
2
3#include <span>
4
5#include "mim/def.h"
6
7namespace mim {
8
9class Lam;
10class Sigma;
11
12/// Common base for TBound.
13class Bound : public Def {
14protected:
15 Bound(Node node, const Def* type, Defs ops)
16 : Def(node, type, ops, 0) {}
17
18 constexpr size_t reduction_offset() const noexcept final { return 0; }
19
20public:
21 /// @name Get Element by Type
22 ///@{
23 size_t find(const Def* type) const;
24 const Def* get(const Def* type) const { return op(find(type)); }
25 ///@}
26};
27
28/// Specific [Bound](https://en.wikipedia.org/wiki/Join_and_meet) depending on @p Up.
29/// The name @p Up refers to the property that a [Join](@ref mim::Join) **ascends** in the underlying
30/// [lattice](https://en.wikipedia.org/wiki/Lattice_(order)) while a [Meet](@ref mim::Meet) descends.
31/// * @p Up = `true`: [Join](@ref mim::Join) (aka least Upper bound/supremum/union)
32/// * @p Up = `false`: [Meet](@ref mim::Meet) (aka greatest lower bound/infimum/intersection)
33template<bool Up>
34class TBound : public Bound, public Setters<TBound<Up>> {
35private:
36 TBound(const Def* type, Defs ops)
37 : Bound(Node, type, ops) {}
38
39public:
40 using Setters<TBound<Up>>::set;
41
42 static constexpr auto Node = Up ? mim::Node::Join : mim::Node::Meet;
43 static constexpr size_t Num_Ops = std::dynamic_extent;
44
45private:
46 const Def* rebuild_(World&, const Def*, Defs) const final;
47
48 friend class World;
49};
50
51/// Constructs a [Meet](@ref mim::Meet) **value**.
52/// @remark [Ac](https://en.wikipedia.org/wiki/Wedge_(symbol)) is Latin and means *and*.
53class Merge : public Def, public Setters<Merge> {
54public:
55 using Setters<Merge>::set;
56 static constexpr auto Node = mim::Node::Merge;
57 static constexpr size_t Num_Ops = std::dynamic_extent;
58
59private:
60 Merge(const Def* type, Defs defs)
61 : Def(Node, type, defs, 0) {}
62
63 const Def* rebuild_(World&, const Def*, Defs) const final;
64
65 friend class World;
66};
67
68/// Constructs a [Join](@ref mim::Join) **value**.
69/// @remark [Inj](https://en.wikipedia.org/wiki/Wedge_(symbol)) is Latin and means *or*.
70class Inj : public Def, public Setters<Inj> {
71private:
72 Inj(const Def* type, const Def* value)
73 : Def(Node, type, {value}, 0) {}
74
75public:
76 using Setters<Inj>::set;
77
78 /// @name ops
79 ///@{
80 const Def* value() const { return op(0); }
81 ///@}
82
83 static constexpr auto Node = mim::Node::Inj;
84 static constexpr size_t Num_Ops = 1;
85
86private:
87 const Def* rebuild_(World&, const Def*, Defs) const final;
88
89 friend class World;
90};
91
92/// Picks the aspect of a Meet [value](Pick::value) by its [type](Def::type).
93class Split : public Def, public Setters<Split> {
94private:
95 Split(const Def* type, const Def* value)
96 : Def(Node, type, {value}, 0) {}
97
98public:
99 using Setters<Split>::set;
100
101 /// @name ops
102 ///@{
103 const Def* value() const { return op(0); }
104 ///@}
105
106 static constexpr auto Node = mim::Node::Split;
107 static constexpr size_t Num_Ops = 1;
108
109private:
110 const Def* rebuild_(World&, const Def*, Defs) const final;
111
112 friend class World;
113};
114
115/// Scrutinize Match::scrutinee() and dispatch to Match::arms.
116class Match : public Def, public Setters<Match> {
117private:
118 Match(const Def* type, Defs ops)
119 : Def(Node, type, ops, 0) {}
120
121public:
122 using Setters<Match>::set;
123 static constexpr auto Node = mim::Node::Match;
124 static constexpr size_t Num_Ops = std::dynamic_extent;
125
126 /// @name ops
127 ///@{
128 const Def* scrutinee() const { return op(0); }
129 template<size_t N = std::dynamic_extent>
130 constexpr auto arms() const noexcept {
131 return ops().subspan<1, N>();
132 }
133 const Def* arm(size_t i) const { return arms()[i]; }
134 size_t num_arms() const { return arms().size(); }
135 ///@}
136
137private:
138 const Def* rebuild_(World&, const Def*, Defs) const final;
139
140 friend class World;
141};
142
143/// Common base for TExt%remum.
144class Ext : public Def {
145protected:
146 Ext(Node node, const Def* type)
147 : Def(node, type, Defs{}, 0) {}
148};
149
150/// Ext%remum. Either Top (@p Up) or Bot%tom.
151template<bool Up>
152class TExt : public Ext, public Setters<TExt<Up>> {
153private:
154 TExt(const Def* type)
155 : Ext(Node, type) {}
156
157public:
158 using Setters<TExt<Up>>::set;
159
160 static constexpr auto Node = Up ? mim::Node::Top : mim::Node::Bot;
161 static constexpr size_t Num_Ops = 0;
162
163private:
164 const Def* rebuild_(World&, const Def*, Defs) const final;
165
166 friend class World;
167};
168
169/// @name Lattice
170///@{
173using Meet = TBound<false>; ///< AKA intersection.
174using Join = TBound<true>; ///< AKA union.
175/// @}
176
177/// A singleton wraps a type into a higher order type.
178/// Therefore any type can be the only inhabitant of a singleton.
179/// Use in conjunction with @ref mim::Join.
180class Uniq : public Def, public Setters<Uniq> {
181private:
182 Uniq(const Def* type, const Def* inner_type)
183 : Def(Node, type, {inner_type}, 0) {}
184
185public:
186 using Setters<Uniq>::set;
187
188 /// @name ops
189 ///@{
190 const Def* op() const { return Def::op(0); }
191 ///@}
192
193 static constexpr auto Node = mim::Node::Uniq;
194 static constexpr size_t Num_Ops = 1;
195
196private:
197 const Def* rebuild_(World&, const Def*, Defs) const final;
198
199 friend class World;
200};
201
202} // namespace mim
Bound(Node node, const Def *type, Defs ops)
Definition lattice.h:15
size_t find(const Def *type) const
Definition lattice.cpp:7
const Def * get(const Def *type) const
Definition lattice.h:24
constexpr size_t reduction_offset() const noexcept final
First Def::op that needs to be dealt with during reduction; e.g.
Definition lattice.h:18
Base class for all Defs.
Definition def.h:251
constexpr Node node() const noexcept
Definition def.h:274
Def * set(size_t i, const Def *)
Successively set from left to right.
Definition def.cpp:266
constexpr auto ops() const noexcept
Definition def.h:305
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
Ext(Node node, const Def *type)
Definition lattice.h:146
static constexpr auto Node
Definition lattice.h:83
const Def * value() const
Definition lattice.h:80
friend class World
Definition lattice.h:89
static constexpr size_t Num_Ops
Definition lattice.h:84
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:118
A function.
Definition lam.h:111
const Def * scrutinee() const
Definition lattice.h:128
size_t num_arms() const
Definition lattice.h:134
friend class World
Definition lattice.h:140
static constexpr size_t Num_Ops
Definition lattice.h:124
static constexpr auto Node
Definition lattice.h:123
const Def * arm(size_t i) const
Definition lattice.h:133
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:130
constexpr auto arms() const noexcept
Definition lattice.h:130
static constexpr size_t Num_Ops
Definition lattice.h:57
friend class World
Definition lattice.h:65
static constexpr auto Node
Definition lattice.h:56
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:122
CRTP-based mixin to declare setters for Def::loc & Def::name using a covariant return type.
Definition def.h:195
const TBound< Up > * set(Loc l) const
Definition def.h:202
A dependent tuple type.
Definition tuple.h:20
friend class World
Definition lattice.h:112
static constexpr auto Node
Definition lattice.h:106
const Def * value() const
Definition lattice.h:103
static constexpr size_t Num_Ops
Definition lattice.h:107
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:129
Specific Bound depending on Up.
Definition lattice.h:34
friend class World
Definition lattice.h:48
static constexpr size_t Num_Ops
Definition lattice.h:43
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:145
static constexpr auto Node
Definition lattice.h:42
Extremum. Either Top (Up) or Bottom.
Definition lattice.h:152
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:144
static constexpr auto Node
Definition lattice.h:160
friend class World
Definition lattice.h:166
static constexpr size_t Num_Ops
Definition lattice.h:161
const Def * op() const
Definition lattice.h:190
static constexpr size_t Num_Ops
Definition lattice.h:194
friend class World
Definition lattice.h:199
static constexpr auto Node
Definition lattice.h:193
const Def * rebuild_(World &, const Def *, Defs) const final
Definition def.cpp:135
The World represents the whole program and manages creation of MimIR nodes (Defs).
Definition world.h:36
Definition ast.h:14
View< const Def * > Defs
Definition def.h:76
TBound< true > Join
AKA union.
Definition lattice.h:174
TExt< true > Top
Definition lattice.h:172
TExt< false > Bot
Definition lattice.h:171
TBound< false > Meet
AKA intersection.
Definition lattice.h:173
Node
Definition def.h:112
@ Bot
Definition def.h:114
@ Meet
Definition def.h:114
@ Inj
Definition def.h:114
@ Merge
Definition def.h:114
@ Match
Definition def.h:114
@ Split
Definition def.h:114
@ Join
Definition def.h:114
@ Top
Definition def.h:114
@ Uniq
Definition def.h:114