12using namespace std::literals;
33 , num_ops_(
ops.size())
36 gid_ =
world->next_gid();
38 }
else if (
auto var = isa<Var>()) {
40 gid_ =
type->world().next_gid();
68 gid_ =
world->next_gid();
70 for (
size_t i = 0, e =
ops.size(); i != e; ++i) {
74 vars_ =
vars->merge(vars_,
op->local_vars());
75 muts_ = muts->
merge(muts_,
op->local_muts());
95 std::fill_n(ops_ptr(),
num_ops,
nullptr);
101UMax::UMax(World& world,
Defs ops)
102 : Def(Node, world.univ(), ops, 0) {}
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]); }
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]); }
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()); }
136const Def* Axiom ::rebuild_(
World& w,
const Def* t,
Defs )
const {
149Arr* Arr ::stub_(
World& w,
const Def* t) {
return w.mut_arr (t); }
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); }
155Sigma* Sigma ::stub_(
World& w,
const Def* t) {
return w.mut_sigma(t,
num_ops()); }
171template TExt<false>* TExt<false> ::stub_(
World&,
const Def*);
172template TExt<true >* TExt<true > ::stub_(
World&,
const Def*);
184 if (
op->free_vars().contains(v))
return false;
187 for (
auto mut :
op->local_muts())
188 if (mut ==
this)
return false;
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)); }));
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)); }));
228 if (
auto mut =
isa_mut())
return mut->reduce(arg);
234 auto& cache =
world().move_.cache;
235 if (
auto i = cache.find({this, arg}); i != cache.end())
return i->second;
239 for (
size_t i = 0, e = res.size(); i != e; ++i) res[i] = rw.rewrite(
op(i));
241 return cache[{
this, arg}] = res;
247 if (
auto mut =
isa_mut(); mut &&
has_var())
return mut->reduce(arg)[i];
269 assert(def && !
op(i) && curr_op_ == i);
271 curr_op_ = (curr_op_ + 1) %
num_ops();
276 if (
auto t =
check(); t !=
type()) type_ = t;
287 for (
size_t i = 0, e =
num_ops(); i != e; ++i) {
291 assert(std::all_of(ops_ptr() + i + 1, ops_ptr() +
num_ops(), [](
auto op) {
return !
op; }));
300 ops_ptr()[i] =
nullptr;
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");
322 if (
auto mut =
isa_mut())
return mut->free_vars();
326 for (
auto mut :
local_muts()) fvs =
vars.merge(fvs, mut->free_vars());
341 for (
bool todo =
true, cyclic =
false; todo;) {
357 if (mark_ != 0 && mark_ != run - 1)
return cyclic |= mark_ == run, vars_;
363 auto& muts = w.muts();
364 auto&
vars = w.vars();
370 mut->muts_ = muts.
insert(mut->muts_,
this);
371 fvs =
vars.merge(fvs, mut->free_vars(todo, cyclic, run));
381void Def::invalidate() {
385 for (
auto mut :
users()) mut->invalidate();
394#ifdef MIM_ENABLE_CHECKS
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_;
423 if (
auto t = isa<Type>())
return w.type(w.uinc(t->level()));
433#define CODE(name, _, __) \
434 case Node::name: return #name;
437 default: fe::unreachable();
442 if (isa<Type>() || isa<Univ>())
return Defs();
444 return Defs(ops_ptr() - 1, (
is_set() ? num_ops_ : 0) + 1);
449#define CODE(n, _, j) \
450 case Node::n: return u32(j);
453 default: fe::unreachable();
458 if (
auto t =
type()) {
459 if (
auto u = t->type()) {
461 if (
auto level =
Lit::isa(
type->level()))
return *level == 0;
476 if (var_)
return var_;
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 );
484 if (
auto pack = isa<Pack >())
return w.var(w.type_idx(pack->shape()), pack);
485 if (isa<Bound >())
return w.var(
this,
this);
486 if (isa<Hole >())
return nullptr;
487 if (isa<Global>())
return nullptr;
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();
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();
507bool Def::equal(
const Def* other)
const {
508 if (isa<Univ>() || this->
isa_mut() || other->
isa_mut())
return this == other;
513 for (
size_t i = 0, e =
num_ops(); result && i != e; ++i) result &= this->
op(i) == other->
op(i);
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));
541 if (!
type())
return this;
545 if (isa<Tuple>() || isa<Sigma>())
return op(i);
546 if (w.is_frozen())
return nullptr;
548 return w.extract(
this, a, i);
556 if (
auto app = def->isa<
App>()) {
557 if (app->callee()->isa<Idx>())
return app->arg();
565 if (
auto l =
Lit::isa(size))
return l;
570 if (size->isa<
Top>())
return 64;
const Def * immutabilize() override
Tries to make an immutable from a mutable.
const Def * shape() const
const Def * reduce(const Def *arg) const
NormalizeFn normalizer() const
static bool alpha(const Def *d1, const Def *d2)
bool is_set() const
Yields true if empty or the last op is set.
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.
constexpr Node node() const noexcept
Def * set(size_t i, const Def *)
Successively set from left to right.
T * as_mut() const
Asserts that this is a mutable, casts constness away and performs a static_cast to T.
Defs deps() const noexcept
nat_t num_tprojs() const
As above but yields 1, if Flags::scalarize_threshold is exceeded.
World & world() const noexcept
virtual const Def * check()
const Def * refine(size_t i, const Def *new_op) const
std::string_view node_name() const
constexpr auto ops() const noexcept
Vars local_vars() const
Vars reachable by following immutable deps().
constexpr flags_t flags() const noexcept
T * isa_mut() const
If this is *mut*able, it will cast constness away and perform a dynamic_cast to T.
const Def * debug_prefix(std::string) const
const Def * op(size_t i) const noexcept
bool is_immutabilizable()
DefVec reduce(const Def *arg) const
Rewrites Def::ops by substituting this mutable's Var with arg.
const Def * var(nat_t a, nat_t i) noexcept
const Def * unfold_type() const
Yields the type of this Def and builds a new Type (UInc n) if necessary.
bool is_open() const
Has free_vars()?
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
const Def * debug_suffix(std::string) const
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
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.
const Def * var()
Not necessarily a Var: E.g., if the return type is [], this will yield ().
std::optional< nat_t > isa_lit_arity() const
constexpr u32 gid() const noexcept
Global id - unique number for this Def.
const Def * arity() const
Def * unset()
Unsets all Def::ops; works even, if not set at all or partially.
std::string unique_name() const
name + "_" + Def::gid
Muts users()
Set of mutables where this mutable is locally referenced.
bool is_closed() const
Has no free_vars()?
Def * reset(size_t i, const Def *def)
Successively reset from left to right.
Vars free_vars() const
Compute a global solution by transitively following mutables as well.
u32 judge() const noexcept
const Var * has_var()
Only returns not nullptr, if Var of this mutable has ever been created.
constexpr size_t num_ops() const noexcept
const Def * alloced_type() const
Global * stub_(World &, const Def *) override
This node is a hole in the IR that is inferred by its context later on.
static constexpr nat_t size2bitwidth(nat_t n)
static const Def * isa(const Def *def)
Checks if def is a Idx s and returns s or nullptr otherwise.
static std::optional< nat_t > isa_lit(const Def *def)
static std::optional< T > isa(const Def *def)
const Def * shape() const
const Def * reduce(const Def *arg) const
const Def * immutabilize() override
Tries to make an immutable from a mutable.
A dependent function type.
Pi(const Def *type, const Def *dom, const Def *codom, bool implicit)
Constructor for an immutable Pi.
const Def * codom() const
const Pi * immutabilize() override
Tries to make an immutable from a mutable.
u32 pass() const
IPass::index within PassMan.
constexpr bool empty() const noexcept
Is empty?
Set merge(Set s1, Set s2)
Yields .
Set insert(Set s, D *d)
Yields .
const TExt< Up > * set(Loc l) const
const Def * immutabilize() override
Tries to make an immutable from a mutable.
Specific Bound depending on Up.
TBound * stub_(World &, const Def *) override
const Def * rebuild_(World &, const Def *, Defs) const override
Extremum. Either Top (Up) or Bottom.
const Def * rebuild_(World &, const Def *, Defs) const override
TExt * stub_(World &, const Def *) override
The World represents the whole program and manages creation of MimIR nodes (Defs).
void make_external(Def *)
const Def * sigma(Defs ops)
const Pi * pi(const Def *dom, const Def *codom, bool implicit=false)
Flags & flags()
Retrieve compile Flags.
Sym sym(std::string_view)
void make_internal(Def *)
const Lit * lit_nat(nat_t a)
Vector< const Def * > DefVec
Dep
Tracks a dependency to certain Defs transitively through the Def::deps() up to but excliding mutables...
uint64_t scalarize_threshold
constexpr size_t hash_combine(size_t seed, T v) noexcept
constexpr decltype(auto) get(Span< T, N > span) noexcept
consteval size_t hash_begin() noexcept
constexpr size_t hash(size_t h) noexcept
Sets< const Var >::Set Vars