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