MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
def.cpp
Go to the documentation of this file.
1#include "mim/def.h"
2
3#include <algorithm>
4
5#include <fe/assert.h>
6
7#include "mim/rewrite.h"
8#include "mim/world.h"
9
10#include "mim/util/hash.h"
11
12using namespace std::literals;
13
14namespace mim {
15
16template void Sets<const Var>::dot();
17template void Sets<Def>::dot();
18
19/*
20 * constructors
21 */
22
23Def::Def(World* world, Node node, const Def* type, Defs ops, flags_t flags)
24 : world_(world)
25 , flags_(flags)
26 , node_(node)
27 , mut_(false)
28 , external_(false)
29 , dep_(node == Node::Hole ? unsigned(Dep::Hole)
30 : node == Node::Proxy ? unsigned(Dep::Proxy)
31 : node == Node::Var ? (Dep::Var | Dep::Mut)
32 : 0)
33 , num_ops_(ops.size())
34 , type_(type) {
35 if (node == Node::Univ) {
36 gid_ = world->next_gid();
38 } else if (auto var = isa<Var>()) {
39 assert(flags_ == 0); // if we ever need flags here, we need to hash that
40 gid_ = type->world().next_gid();
41 vars_ = Vars(var);
42 dep_ |= type->dep_;
43 auto op = ops[0];
44 ops_ptr()[0] = op;
45 hash_ = hash_begin(node_t(Node::Var));
46 hash_ = hash_combine(hash_, type->gid());
47 hash_ = hash_combine(hash_, op->gid());
48 } else {
50 Sets<Def>* muts;
51 hash_ = hash_begin(u8(node));
52 hash_ = hash_combine(hash_, flags_);
53
54 if (type) {
55 world = &type->world();
56 vars = &world->vars();
57 muts = &world->muts();
58 dep_ |= type->dep_;
59 vars_ = vars->merge(vars_, type->local_vars());
60 muts_ = muts->merge(muts_, type->local_muts());
61 hash_ = hash_combine(hash_, type->gid());
62 } else {
63 world = &ops[0]->world();
64 vars = &world->vars();
65 muts = &world->muts();
66 }
67
68 gid_ = world->next_gid();
69 auto ptr = ops_ptr();
70 for (size_t i = 0, e = ops.size(); i != e; ++i) {
71 auto op = ops[i];
72 ptr[i] = op;
73 dep_ |= op->dep_;
74 vars_ = vars->merge(vars_, op->local_vars());
75 muts_ = muts->merge(muts_, op->local_muts());
76 hash_ = hash_combine(hash_, op->gid());
77 }
78 }
79}
80
81Def::Def(Node n, const Def* type, Defs ops, flags_t flags)
82 : Def(nullptr, n, type, ops, flags) {}
83
84Def::Def(Node node, const Def* type, size_t num_ops, flags_t flags)
85 : flags_(flags)
86 , node_(node)
87 , mut_(true)
88 , external_(false)
89 , dep_(Dep::Mut | (node == Node::Hole ? Dep::Hole : Dep::None))
90 , num_ops_(num_ops)
91 , type_(type) {
92 gid_ = world().next_gid();
93 hash_ = mim::hash(gid());
94 var_ = nullptr;
95 std::fill_n(ops_ptr(), num_ops, nullptr);
96}
97
98Nat::Nat(World& world)
99 : Def(Node, world.type(), Defs{}, 0) {}
100
101UMax::UMax(World& world, Defs ops)
102 : Def(Node, world.univ(), ops, 0) {}
103
104// clang-format off
105
106/*
107 * rebuild
108 */
109
110const Def* Hole ::rebuild_(World&, const Def*, Defs ) const { fe::unreachable(); }
111const Def* Global ::rebuild_(World&, const Def*, Defs ) const { fe::unreachable(); }
112const Def* Idx ::rebuild_(World& w, const Def* , Defs ) const { return w.type_idx(); }
113const Def* Nat ::rebuild_(World& w, const Def* , Defs ) const { return w.type_nat(); }
114const Def* Univ ::rebuild_(World& w, const Def* , Defs ) const { return w.univ(); }
115const Def* Ac ::rebuild_(World& w, const Def* t, Defs o) const { return w.ac(t, o); }
116const Def* App ::rebuild_(World& w, const Def* , Defs o) const { return w.app(o[0], o[1]); }
117const Def* Arr ::rebuild_(World& w, const Def* , Defs o) const { return w.arr(o[0], o[1]); }
118const Def* Extract::rebuild_(World& w, const Def* , Defs o) const { return w.extract(o[0], o[1]); }
119const Def* Insert ::rebuild_(World& w, const Def* , Defs o) const { return w.insert(o[0], o[1], o[2]); }
120const Def* Lam ::rebuild_(World& w, const Def* t, Defs o) const { return w.lam(t->as<Pi>(), o[0], o[1]); }
121const Def* Lit ::rebuild_(World& w, const Def* t, Defs ) const { return w.lit(t, get()); }
122const Def* Pack ::rebuild_(World& w, const Def* t, Defs o) const { return w.pack(t->arity(), o[0]); }
123const Def* Pi ::rebuild_(World& w, const Def* , Defs o) const { return w.pi(o[0], o[1], is_implicit()); }
124const Def* Pick ::rebuild_(World& w, const Def* t, Defs o) const { return w.pick(t, o[0]); }
125const Def* Proxy ::rebuild_(World& w, const Def* t, Defs o) const { return w.proxy(t, o, pass(), tag()); }
126const Def* Sigma ::rebuild_(World& w, const Def* , Defs o) const { return w.sigma(o); }
127const Def* Uniq ::rebuild_(World& w, const Def* , Defs o) const { return w.uniq(o[0]); }
128const Def* Type ::rebuild_(World& w, const Def* , Defs o) const { return w.type(o[0]); }
129const Def* Test ::rebuild_(World& w, const Def* , Defs o) const { return w.test(o[0], o[1], o[2], o[3]); }
130const Def* Tuple ::rebuild_(World& w, const Def* t, Defs o) const { return w.tuple(t, o); }
131const Def* UInc ::rebuild_(World& w, const Def* , Defs o) const { return w.uinc(o[0], offset()); }
132const Def* UMax ::rebuild_(World& w, const Def* , Defs o) const { return w.umax(o); }
133const Def* Var ::rebuild_(World& w, const Def* t, Defs o) const { return w.var(t, o[0]->as_mut()); }
134const Def* Vel ::rebuild_(World& w, const Def* t, Defs o) const { return w.vel(t, o[0])->set(dbg()); }
135
136const Def* Axiom ::rebuild_(World& w, const Def* t, Defs ) const {
137 if (&w != &world()) return w.axiom(normalizer(), curry(), trip(), t, plugin(), tag(), sub())->set(dbg());
139 return this;
140}
141
142template<bool up> const Def* TExt <up>::rebuild_(World& w, const Def* t, Defs ) const { return w.ext <up>(t)->set(dbg()); }
143template<bool up> const Def* TBound<up>::rebuild_(World& w, const Def* , Defs o) const { return w.bound<up>(o)->set(dbg()); }
144
145/*
146 * stub
147 */
148
149Arr* Arr ::stub_(World& w, const Def* t) { return w.mut_arr (t); }
150Global* Global::stub_(World& w, const Def* t) { return w.global (t, is_mutable()); }
151Hole* Hole ::stub_(World& w, const Def* t) { return w.mut_hole(t); }
152Lam* Lam ::stub_(World& w, const Def* t) { return w.mut_lam (t->as<Pi>()); }
153Pack* Pack ::stub_(World& w, const Def* t) { return w.mut_pack (t); }
154Pi* Pi ::stub_(World& w, const Def* t) { return w.mut_pi (t, is_implicit()); }
155Sigma* Sigma ::stub_(World& w, const Def* t) { return w.mut_sigma(t, num_ops()); }
156
157template<bool up> TBound<up>* TBound<up>::stub_(World& w, const Def* t) { return w.mut_bound<up>(t, num_ops()); }
158template<bool up> TExt <up>* TExt <up>::stub_(World& , const Def* ) { fe::unreachable(); }
159
160/*
161 * instantiate templates
162 */
163
164#ifndef DOXYGEN
165template const Def* TExt<false> ::rebuild_(World&, const Def*, Defs) const;
166template const Def* TExt<true > ::rebuild_(World&, const Def*, Defs) const;
167template const Def* TBound<false>::rebuild_(World&, const Def*, Defs) const;
168template const Def* TBound<true >::rebuild_(World&, const Def*, Defs) const;
171template TExt<false>* TExt<false> ::stub_(World&, const Def*);
172template TExt<true >* TExt<true > ::stub_(World&, const Def*);
173#endif
174
175// clang-format on
176
177/*
178 * immutabilize
179 */
180
182 if (auto v = has_var()) {
183 for (auto op : deps())
184 if (op->free_vars().contains(v)) return false;
185 }
186 for (auto op : deps()) {
187 for (auto mut : op->local_muts())
188 if (mut == this) return false; // recursion
189 }
190 return true;
191}
192
194 if (is_immutabilizable()) return world().pi(dom(), codom());
195 return nullptr;
196}
197
199 if (is_immutabilizable()) return static_cast<const Sigma*>(world().sigma(ops()));
200 return nullptr;
201}
202
203const Def* Arr::immutabilize() {
204 auto& w = world();
205 if (is_immutabilizable()) return w.arr(shape(), body());
206
207 if (auto n = Lit::isa(shape()); n && *n < w.flags().scalarize_threshold)
208 return w.sigma(DefVec(*n, [&](size_t i) { return reduce(w.lit_idx(*n, i)); }));
209
210 return nullptr;
211}
212
213const Def* Pack::immutabilize() {
214 auto& w = world();
215 if (is_immutabilizable()) return w.pack(shape(), body());
216
217 if (auto n = Lit::isa(shape()); n && *n < w.flags().scalarize_threshold)
218 return w.tuple(DefVec(*n, [&](size_t i) { return reduce(w.lit_idx(*n, i)); }));
219
220 return nullptr;
221}
222
223/*
224 * reduce
225 */
226
227DefVec Def::reduce(const Def* arg) const {
228 if (auto mut = isa_mut()) return mut->reduce(arg);
229 return DefVec(ops().begin(), ops().end());
230}
231
232DefVec Def::reduce(const Def* arg) {
233 if (auto var = has_var()) {
234 auto& cache = world().move_.cache;
235 if (auto i = cache.find({this, arg}); i != cache.end()) return i->second;
236
237 auto rw = VarRewriter(var, arg);
238 auto res = DefVec(num_ops());
239 for (size_t i = 0, e = res.size(); i != e; ++i) res[i] = rw.rewrite(op(i));
240
241 return cache[{this, arg}] = res;
242 }
243 return DefVec(ops().begin(), ops().end());
244}
245
246const Def* Def::reduce(size_t i, const Def* arg) const {
247 if (auto mut = isa_mut(); mut && has_var()) return mut->reduce(arg)[i];
248 return op(i);
249}
250
251const Def* Def::refine(size_t i, const Def* new_op) const {
252 DefVec new_ops(ops().begin(), ops().end());
253 new_ops[i] = new_op;
254 return rebuild(type(), new_ops);
255}
256
257/*
258 * Def - set
259 */
260
261// clang-format off
262Def* Def:: set(Defs ops) { assert(ops.size() == num_ops()); for (size_t i = 0, e = num_ops(); i != e; ++i) set(i, ops[i]); return this; }
263Def* Def::reset(Defs ops) { assert(ops.size() == num_ops()); for (size_t i = 0, e = num_ops(); i != e; ++i) reset(i, ops[i]); return this; }
264// clang-format on
265
266Def* Def::set(size_t i, const Def* def) {
267 invalidate();
268 def = check(i, def);
269 assert(def && !op(i) && curr_op_ == i);
270#ifndef NDEBUG
271 curr_op_ = (curr_op_ + 1) % num_ops();
272#endif
273 ops_ptr()[i] = def;
274
275 if (i == num_ops() - 1) { // set last op, so check kind
276 if (auto t = check(); t != type()) type_ = t;
277 }
278
279 return this;
280}
281
283 invalidate();
284#ifndef NDEBUG
285 curr_op_ = 0;
286#endif
287 for (size_t i = 0, e = num_ops(); i != e; ++i) {
288 if (op(i))
289 unset(i);
290 else {
291 assert(std::all_of(ops_ptr() + i + 1, ops_ptr() + num_ops(), [](auto op) { return !op; }));
292 break;
293 }
294 }
295 return this;
296}
297
298Def* Def::unset(size_t i) {
299 invalidate();
300 ops_ptr()[i] = nullptr;
301 return this;
302}
303
304bool Def::is_set() const {
305 if (num_ops() == 0) return true;
306 bool result = ops().back();
307 assert((!result || std::ranges::all_of(ops().rsubspan(1), [](auto op) { return op; }))
308 && "the last operand is set but others in front of it aren't");
309 return result;
310}
311
312/*
313 * free_vars
314 */
315
317 if (auto mut = isa_mut()) return Muts(mut);
318 return muts_;
319}
320
322 if (auto mut = isa_mut()) return mut->free_vars();
323
324 auto& vars = world().vars();
325 auto fvs = local_vars();
326 for (auto mut : local_muts()) fvs = vars.merge(fvs, mut->free_vars());
327
328 return fvs;
329}
330
331Vars Def::local_vars() const { return mut_ ? Vars() : vars_; }
332
334 if (!is_set()) return {};
335
336 if (mark_ == 0) {
337 // fixed-point iteration to recompute free vars:
338 // (run - 1) identifies the previous iteration; so make sure to offset run by 2 for the first iteration
339 auto& w = world();
340 w.next_run();
341 for (bool todo = true, cyclic = false; todo;) {
342 todo = false;
343 free_vars(todo, cyclic, w.next_run());
344 if (!cyclic) break; // triggers either immediately or never
345 }
346 }
347
348 return vars_;
349}
350
351Vars Def::free_vars(bool& todo, bool& cyclic, uint32_t run) {
352 // Recursively recompute free vars. If
353 // * mark_ == 0: invalid - need to recompute
354 // * mark_ == run - 1: Previous iteration - need to recompute
355 // * mark_ == run: We are running in cycles within the *current* iteration of our fixed-point loop
356 // * all other values for mark_: valid!
357 if (mark_ != 0 && mark_ != run - 1) return cyclic |= mark_ == run, vars_;
358 mark_ = run;
359
360 auto fvs0 = vars_;
361 auto fvs = fvs0;
362 auto& w = world();
363 auto& muts = w.muts();
364 auto& vars = w.vars();
365
366 for (auto op : deps()) {
367 fvs = vars.merge(fvs, op->local_vars());
368
369 for (auto mut : op->local_muts()) {
370 mut->muts_ = muts.insert(mut->muts_, this); // register "this" as user of local_mut
371 fvs = vars.merge(fvs, mut->free_vars(todo, cyclic, run));
372 }
373 }
374
375 if (auto var = has_var()) fvs = vars.erase(fvs, var); // FV(λx.e) = FV(e) \ {x}
376
377 todo |= fvs0 != fvs;
378 return vars_ = fvs;
379}
380
381void Def::invalidate() {
382 if (mark_ != 0) {
383 mark_ = 0;
384 if (vars_) { // only necessary, if the cached free vars are non-empty
385 for (auto mut : users()) mut->invalidate();
386 vars_ = Vars();
387 }
388 muts_ = Muts();
389 }
390}
391
392bool Def::is_closed() const {
393 if (local_vars().empty() && local_muts().empty()) return true;
394#ifdef MIM_ENABLE_CHECKS
395 assert(!is_external() || free_vars().empty());
396#endif
397 return free_vars().empty();
398}
399
400bool Def::is_open() const {
401 if (!local_vars().empty()) return true;
402 return !free_vars().empty();
403}
404
405/*
406 * Def - misc
407 */
408
409Sym Def::sym(const char* s) const { return world().sym(s); }
410Sym Def::sym(std::string_view s) const { return world().sym(s); }
411Sym Def::sym(std::string s) const { return world().sym(std::move(s)); }
412
413World& Def::world() const noexcept {
414 for (auto def = this;; def = def->type()) {
415 if (def->isa<Univ>()) return *def->world_;
416 if (auto type = def->isa<Type>()) return *type->level()->type()->as<Univ>()->world_;
417 }
418}
419
420const Def* Def::unfold_type() const {
421 if (!type_) {
422 auto& w = world();
423 if (auto t = isa<Type>()) return w.type(w.uinc(t->level()));
424 assert(isa<Univ>());
425 return nullptr;
426 }
427
428 return type_;
429}
430
431std::string_view Def::node_name() const {
432 switch (node()) {
433#define CODE(name, _, __) \
434 case Node::name: return #name;
436#undef CODE
437 default: fe::unreachable();
438 }
439}
440
441Defs Def::deps() const noexcept {
442 if (isa<Type>() || isa<Univ>()) return Defs();
443 assert(type());
444 return Defs(ops_ptr() - 1, (is_set() ? num_ops_ : 0) + 1);
445}
446
447u32 Def::judge() const noexcept {
448 switch (node()) {
449#define CODE(n, _, j) \
450 case Node::n: return u32(j);
452#undef CODE
453 default: fe::unreachable();
454 }
455}
456
457bool Def::is_term() const {
458 if (auto t = type()) {
459 if (auto u = t->type()) {
460 if (auto type = u->isa<Type>()) {
461 if (auto level = Lit::isa(type->level())) return *level == 0;
462 }
463 }
464 }
465 return false;
466}
467
468#ifndef NDEBUG
469const Def* Def::debug_prefix(std::string prefix) const { return dbg_.set(world().sym(prefix + sym().str())), this; }
470const Def* Def::debug_suffix(std::string suffix) const { return dbg_.set(world().sym(sym().str() + suffix)), this; }
471#endif
472
473// clang-format off
474
475const Def* Def::var() {
476 if (var_) return var_;
477 auto& w = world();
478
479 if (w.is_frozen()) return nullptr;
480 if (auto lam = isa<Lam >()) return w.var(lam ->dom(), lam);
481 if (auto pi = isa<Pi >()) return w.var(pi ->dom(), pi);
482 if (auto sig = isa<Sigma>()) return w.var(sig, sig);
483 if (auto arr = isa<Arr >()) return w.var(w.type_idx(arr ->shape()), arr ); // TODO shapes like (2, 3)
484 if (auto pack = isa<Pack >()) return w.var(w.type_idx(pack->shape()), pack); // TODO shapes like (2, 3)
485 if (isa<Bound >()) return w.var(this, this);
486 if (isa<Hole >()) return nullptr;
487 if (isa<Global>()) return nullptr;
488 fe::unreachable();
489}
490
491const Def* Def::arity() const {
492 if (auto sigma = isa<Sigma>()) return world().lit_nat(sigma->num_ops());
493 if (auto arr = isa<Arr >()) return arr->shape();
494 if (auto t = type()) return t->arity();
495 return world().lit_nat_1();
496}
497
498std::optional<nat_t> Def::isa_lit_arity() const {
499 if (auto sigma = isa<Sigma>()) return sigma->num_ops();
500 if (auto arr = isa<Arr >()) return Lit::isa(arr->shape());
501 if (auto t = type()) return t->isa_lit_arity();
502 return 1;
503}
504
505// clang-format on
506
507bool Def::equal(const Def* other) const {
508 if (isa<Univ>() || this->isa_mut() || other->isa_mut()) return this == other;
509
510 bool result = this->node() == other->node() && this->flags() == other->flags()
511 && this->num_ops() == other->num_ops() && this->type() == other->type();
512
513 for (size_t i = 0, e = num_ops(); result && i != e; ++i) result &= this->op(i) == other->op(i);
514
515 return result;
516}
517
518void Def::make_external() { return world().make_external(this); }
519void Def::make_internal() { return world().make_internal(this); }
520
521std::string Def::unique_name() const { return sym().str() + "_"s + std::to_string(gid()); }
522
524 if (auto a = isa_lit_arity(); a && *a < world().flags().scalarize_threshold) return *a;
525 return 1;
526}
527
528const Def* Def::proj(nat_t a, nat_t i) const {
529 World& w = world();
530
531 if (auto arr = isa<Arr>()) {
532 if (arr->arity()->isa<Top>()) return arr->body();
533 return arr->reduce(w.lit_idx(a, i));
534 } else if (auto pack = isa<Pack>()) {
535 if (pack->arity()->isa<Top>()) return pack->body();
536 assert(!w.is_frozen() && "TODO");
537 return pack->reduce(w.lit_idx(a, i));
538 }
539
540 if (a == 1) {
541 if (!type()) return this;
542 if (!isa_mut<Sigma>() && !type()->isa_mut<Sigma>()) return this;
543 }
544
545 if (isa<Tuple>() || isa<Sigma>()) return op(i);
546 if (w.is_frozen()) return nullptr;
547
548 return w.extract(this, a, i);
549}
550
551/*
552 * Idx
553 */
554
555const Def* Idx::isa(const Def* def) {
556 if (auto app = def->isa<App>()) {
557 if (app->callee()->isa<Idx>()) return app->arg();
558 }
559
560 return nullptr;
561}
562
563std::optional<nat_t> Idx::isa_lit(const Def* def) {
564 if (auto size = Idx::isa(def))
565 if (auto l = Lit::isa(size)) return l;
566 return {};
567}
568
569std::optional<nat_t> Idx::size2bitwidth(const Def* size) {
570 if (size->isa<Top>()) return 64;
571 if (auto s = Lit::isa(size)) return size2bitwidth(*s);
572 return {};
573}
574
575/*
576 * Global
577 */
578
579const App* Global::type() const { return Def::type()->as<App>(); }
580const Def* Global::alloced_type() const { return type()->arg(0); }
581
582} // namespace mim
friend class World
Definition lattice.h:65
friend class World
Definition lam.h:241
const Def * arg() const
Definition lam.h:225
const Def * immutabilize() override
Tries to make an immutable from a mutable.
Definition def.cpp:203
const Def * body() const
Definition tuple.h:79
friend class World
Definition tuple.h:110
const Def * shape() const
Definition tuple.h:78
const Def * reduce(const Def *arg) const
Definition tuple.h:93
NormalizeFn normalizer() const
Definition axiom.h:36
u8 curry() const
Definition axiom.h:37
sub_t sub() const
Definition axiom.h:54
tag_t tag() const
Definition axiom.h:53
friend class World
Definition axiom.h:68
plugin_t plugin() const
Definition axiom.h:52
u8 trip() const
Definition axiom.h:38
static bool alpha(const Def *d1, const Def *d2)
Definition check.h:71
Base class for all Defs.
Definition def.h:198
bool is_set() const
Yields true if empty or the last op is set.
Definition def.cpp:304
const Def * proj(nat_t a, nat_t i) const
Similar to World::extract while assuming an arity of a, but also works on Sigmas and Arrays.
Definition def.cpp:528
constexpr Node node() const noexcept
Definition def.h:221
Def * set(size_t i, const Def *)
Successively set from left to right.
Definition def.cpp:266
void make_internal()
Definition def.cpp:519
T * as_mut() const
Asserts that this is a mutable, casts constness away and performs a static_cast to T.
Definition def.h:438
Defs deps() const noexcept
Definition def.cpp:441
nat_t num_tprojs() const
As above but yields 1, if Flags::scalarize_threshold is exceeded.
Definition def.cpp:523
World & world() const noexcept
Definition def.cpp:413
virtual const Def * check()
Definition def.h:515
const Def * refine(size_t i, const Def *new_op) const
Definition def.cpp:251
std::string_view node_name() const
Definition def.cpp:431
constexpr auto ops() const noexcept
Definition def.h:261
Vars local_vars() const
Vars reachable by following immutable deps().
Definition def.cpp:331
void make_external()
Definition def.cpp:518
constexpr flags_t flags() const noexcept
Definition def.h:216
Dbg dbg_
Definition def.h:562
T * isa_mut() const
If this is *mut*able, it will cast constness away and perform a dynamic_cast to T.
Definition def.h:430
auto vars() noexcept
Definition def.h:379
bool is_term() const
Definition def.cpp:457
const Def * debug_prefix(std::string) const
Definition def.cpp:469
const Def * op(size_t i) const noexcept
Definition def.h:264
bool is_immutabilizable()
Definition def.cpp:181
DefVec reduce(const Def *arg) const
Rewrites Def::ops by substituting this mutable's Var with arg.
Definition def.cpp:227
const Def * var(nat_t a, nat_t i) noexcept
Definition def.h:379
bool is_external() const
Definition def.h:414
const Def * unfold_type() const
Yields the type of this Def and builds a new Type (UInc n) if necessary.
Definition def.cpp:420
bool is_open() const
Has free_vars()?
Definition def.cpp:400
friend class World
Definition def.h:591
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
Definition def.cpp:316
const Def * debug_suffix(std::string) const
Definition def.cpp:470
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
Definition def.h:242
auto vars(F f) noexcept
Definition def.h:379
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:492
const Def * var()
Not necessarily a Var: E.g., if the return type is [], this will yield ().
Definition def.cpp:475
Sym sym() const
Definition def.h:451
std::optional< nat_t > isa_lit_arity() const
Definition def.cpp:498
flags_t flags_
Definition def.h:569
constexpr u32 gid() const noexcept
Global id - unique number for this Def.
Definition def.h:217
const Def * arity() const
Definition def.cpp:491
Def * unset()
Unsets all Def::ops; works even, if not set at all or partially.
Definition def.cpp:282
std::string unique_name() const
name + "_" + Def::gid
Definition def.cpp:521
Muts users()
Set of mutables where this mutable is locally referenced.
Definition def.h:407
bool is_closed() const
Has no free_vars()?
Definition def.cpp:392
Def * reset(size_t i, const Def *def)
Successively reset from left to right.
Definition def.h:286
Vars free_vars() const
Compute a global solution by transitively following mutables as well.
Definition def.cpp:321
Dbg dbg() const
Definition def.h:449
u32 judge() const noexcept
Definition def.cpp:447
const Var * has_var()
Only returns not nullptr, if Var of this mutable has ever been created.
Definition def.h:383
constexpr size_t num_ops() const noexcept
Definition def.h:265
const Def * rebuild_(World &, const Def *, Defs) const override
Definition def.cpp:118
friend class World
Definition tuple.h:174
const Def * alloced_type() const
Definition def.cpp:580
friend class World
Definition def.h:866
bool is_mutable() const
Definition def.h:852
const App * type() const
Definition def.cpp:579
Global * stub_(World &, const Def *) override
Definition def.cpp:150
This node is a hole in the IR that is inferred by its context later on.
Definition check.h:10
friend class World
Definition check.h:51
static constexpr nat_t size2bitwidth(nat_t n)
Definition def.h:792
static const Def * isa(const Def *def)
Checks if def is a Idx s and returns s or nullptr otherwise.
Definition def.cpp:555
friend class World
Definition def.h:802
static std::optional< nat_t > isa_lit(const Def *def)
Definition def.cpp:563
friend class World
Definition tuple.h:201
friend class World
Definition lam.h:191
static std::optional< T > isa(const Def *def)
Definition def.h:730
friend class World
Definition def.h:743
friend class World
Definition def.h:756
const Def * body() const
Definition tuple.h:125
const Def * shape() const
Definition tuple.cpp:40
friend class World
Definition tuple.h:151
const Def * reduce(const Def *arg) const
Definition tuple.h:140
const Def * immutabilize() override
Tries to make an immutable from a mutable.
Definition def.cpp:213
A dependent function type.
Definition lam.h:11
Pi(const Def *type, const Def *dom, const Def *codom, bool implicit)
Constructor for an immutable Pi.
Definition lam.h:14
bool is_implicit() const
Definition lam.h:23
const Def * dom() const
Definition lam.h:32
friend class World
Definition lam.h:100
const Def * codom() const
Definition lam.h:33
const Pi * immutabilize() override
Tries to make an immutable from a mutable.
Definition def.cpp:193
friend class World
Definition lattice.h:110
friend class World
Definition def.h:824
u32 pass() const
IPass::index within PassMan.
Definition def.h:815
u32 tag() const
Definition def.h:816
constexpr bool empty() const noexcept
Is empty?
Definition sets.h:235
void dot()
Definition sets.h:553
Set merge(Set s1, Set s2)
Yields .
Definition sets.h:481
Set insert(Set s, D *d)
Yields .
Definition sets.h:415
const TExt< Up > * set(Loc l) const
Definition def.h:150
const Def * immutabilize() override
Tries to make an immutable from a mutable.
Definition def.cpp:198
friend class World
Definition tuple.h:45
Specific Bound depending on Up.
Definition lattice.h:31
friend class World
Definition lattice.h:49
TBound * stub_(World &, const Def *) override
Definition def.cpp:157
const Def * rebuild_(World &, const Def *, Defs) const override
Definition def.cpp:143
Extremum. Either Top (Up) or Bottom.
Definition lattice.h:156
friend class World
Definition lattice.h:172
const Def * rebuild_(World &, const Def *, Defs) const override
Definition def.cpp:142
TExt * stub_(World &, const Def *) override
Definition def.cpp:158
friend class World
Definition lattice.h:145
friend class World
Definition tuple.h:62
friend class World
Definition def.h:705
friend class World
Definition def.h:684
level_t offset() const
Definition def.h:676
friend class World
Definition def.h:662
friend class World
Definition lattice.h:204
friend class World
Definition def.h:649
friend class World
Definition def.h:635
friend class World
Definition lattice.h:88
The World represents the whole program and manages creation of MimIR nodes (Defs).
Definition world.h:33
auto & muts()
Definition world.h:515
void make_external(Def *)
Definition world.cpp:87
const Def * sigma(Defs ops)
Definition world.cpp:238
const Pi * pi(const Def *dom, const Def *codom, bool implicit=false)
Definition world.h:251
Flags & flags()
Retrieve compile Flags.
Definition world.cpp:71
u32 next_gid()
Definition world.h:89
Sym sym(std::string_view)
Definition world.cpp:74
void make_internal(Def *)
Definition world.cpp:94
const Lit * lit_nat(nat_t a)
Definition world.h:384
auto & vars()
Definition world.h:514
const Lit * lit_nat_1()
Definition world.h:386
#define MIM_NODE(m)
Definition def.h:18
Definition ast.h:14
View< const Def * > Defs
Definition def.h:49
u64 nat_t
Definition types.h:43
Vector< const Def * > DefVec
Definition def.h:50
Dep
Tracks a dependency to certain Defs transitively through the Def::deps() up to but excliding mutables...
Definition def.h:97
@ None
Definition def.h:98
@ Mut
Definition def.h:99
u64 flags_t
Definition types.h:45
uint64_t scalarize_threshold
Definition flags.h:13
u8 node_t
Definition types.h:44
constexpr size_t hash_combine(size_t seed, T v) noexcept
Definition hash.h:58
Sets< Def >::Set Muts
Definition def.h:59
TExt< true > Top
Definition lattice.h:178
constexpr decltype(auto) get(Span< T, N > span) noexcept
Definition span.h:102
consteval size_t hash_begin() noexcept
Definition hash.h:71
constexpr size_t hash(size_t h) noexcept
Definition hash.h:32
Sets< const Var >::Set Vars
Definition def.h:68
uint32_t u32
Definition types.h:34
uint8_t u8
Definition types.h:34
Node
Definition def.h:83
@ Univ
Definition def.h:85
@ Var
Definition def.h:85
CODE(node, name, _)
Definition def.h:84