10using namespace std::literals;
21 , node_(unsigned(node))
29 , num_ops_(ops.size())
32 for (
size_t i = 0, e =
ops.size(); i != e; ++i) {
38 gid_ =
world().next_gid();
40 if (
auto var = isa<Var>()) {
61 :
Def(nullptr, n, type, ops, flags) {}
74 std::fill_n(ops_ptr(),
num_ops,
nullptr);
78 :
Def(Node, world.type(),
Defs{}, 0) {}
80UMax::UMax(World& world,
Defs ops)
81 : Def(Node, world.univ(), ops, 0) {}
98Ref Insert ::rebuild_(
World& w,
Ref ,
Defs o)
const {
return w.insert(o[0], o[1], o[2]); }
101Ref Pack ::rebuild_(
World& w,
Ref t,
Defs o)
const {
return w.pack(t->arity(), o[0]); }
102Ref Pi ::rebuild_(
World& w,
Ref ,
Defs o)
const {
return w.pi(o[0], o[1], is_implicit()); }
104Ref Proxy ::rebuild_(
World& w,
Ref t,
Defs o)
const {
return w.proxy(t, o, pass(), tag()); }
108Ref Test ::rebuild_(
World& w,
Ref ,
Defs o)
const {
return w.test(o[0], o[1], o[2], o[3]); }
113Ref Vel ::rebuild_(
World& w,
Ref t,
Defs o)
const {
return w.vel(t, o[0])->set(dbg()); }
116 if (&w != &world())
return w.axiom(normalizer(), curry(), trip(), t, plugin(), tag(), sub())->set(dbg());
133Pi* Pi ::stub_(
World& w,
Ref t) {
return w.mut_pi (t, is_implicit()); }
184 if (
auto n =
Lit::isa(
shape()); n && *n < w.flags().scalarize_threshold)
185 return w.sigma(
DefVec(*n, [&](
size_t i) {
return reduce(w.lit_idx(*n, i)); }));
194 if (
auto n =
Lit::isa(
shape()); n && *n < w.flags().scalarize_threshold)
195 return w.tuple(
DefVec(*n, [&](
size_t i) {
return reduce(w.lit_idx(*n, i)); }));
205 if (
auto mut =
isa_mut())
return mut->reduce(arg);
211 auto& cache =
world().move_.cache;
212 if (
auto i = cache.find({this, arg}); i != cache.end())
return i->second;
216 for (
size_t i = 0, e = res.size(); i != e; ++i) res[i] = rw.rewrite(
op(i));
218 return cache[{
this, arg}] = res;
224 if (
auto mut =
isa_mut(); mut &&
has_var())
return mut->reduce(arg)[i];
246 assert(def && !
op(i) && curr_op_ == i);
248 curr_op_ = (curr_op_ + 1) %
num_ops();
253 if (
auto t =
check(); t !=
type()) type_ = t;
264 for (
size_t i = 0, e =
num_ops(); i != e; ++i) {
268 assert(std::all_of(ops_ptr() + i + 1, ops_ptr() +
num_ops(), [](
auto op) {
return !
op; }));
277 ops_ptr()[i] =
nullptr;
282 if (
num_ops() == 0)
return true;
283 bool result =
ops().back();
284 assert((!result || std::ranges::all_of(
ops().rsubspan(1), [](
auto op) {
return op; }))
285 &&
"the last operand is set but others in front of it aren't");
305 if (
auto mut =
isa_mut())
return mut->free_vars();
319 for (
bool todo =
true, cyclic =
false; todo;) {
335 if (mark_ != 0 && mark_ != run - 1)
return cyclic |= mark_ == run, vars_;
344 local_mut->muts_ =
world().
muts().insert(local_mut->muts_,
this);
345 fvs =
world().
vars().merge(fvs, local_mut->free_vars(todo, cyclic, run));
354void Def::invalidate() {
357 for (
auto mut :
users()) mut->invalidate();
365#ifdef MIM_ENABLE_CHECKS
385 if (isa<Univ>())
return *world_;
392 if (
auto t = isa<Type>())
return world().
type(
world().uinc(t->level()));
402#define CODE(op, abbr) \
403 case Node::op: return #abbr;
406 default: fe::unreachable();
411 if (isa<Type>() || isa<Univ>())
return Defs();
413 return Defs(ops_ptr() - 1, (
is_set() ? num_ops_ : 0) + 1);
424 if (var_)
return var_;
427 if (w.is_frozen())
return nullptr;
428 if (
auto lam = isa<Lam >())
return w.var(lam ->dom(), lam);
429 if (
auto pi = isa<Pi >())
return w.var(pi ->dom(), pi);
430 if (
auto sig = isa<Sigma>())
return w.var(sig, sig);
431 if (
auto arr = isa<Arr >())
return w.var(w.type_idx(arr ->shape()), arr );
432 if (
auto pack = isa<Pack >())
return w.var(w.type_idx(pack->shape()), pack);
433 if (isa<Bound >())
return w.var(
this,
this);
434 if (isa<Infer >())
return nullptr;
435 if (isa<Global>())
return nullptr;
440 if (
auto t =
type()) {
441 if (
auto u = t->type()) {
443 if (
auto level =
Lit::isa(
type->level()))
return *level == 0;
451 if (
auto sigma = isa<Sigma>())
return world().
lit_nat(sigma->num_ops());
452 if (
auto arr = isa<Arr >())
return arr->shape();
453 if (
auto t =
type())
return t->arity();
458 if (
auto sigma = isa<Sigma>())
return sigma->
num_ops();
459 if (
auto arr = isa<Arr >())
return Lit::isa(arr->shape());
460 if (
auto t =
type())
return t->isa_lit_arity();
466bool Def::equal(
const Def* other)
const {
467 if (isa<Univ>() || this->
isa_mut() || other->
isa_mut())
return this == other;
472 for (
size_t i = 0, e =
num_ops(); result && i != e; ++i) result &= this->
op(i) == other->
op(i);
490 if (
auto arr = isa<Arr>()) {
491 if (arr->arity()->isa<
Top>())
return arr->body();
492 return arr->reduce(w.lit_idx(a, i));
493 }
else if (
auto pack = isa<Pack>()) {
494 if (pack->arity()->isa<
Top>())
return pack->body();
495 assert(!w.is_frozen() &&
"TODO");
496 return pack->reduce(w.lit_idx(a, i));
500 if (!
type())
return this;
504 if (isa<Tuple>() || isa<Sigma>())
return op(i);
505 if (w.is_frozen())
return nullptr;
507 return w.extract(
this, a, i);
515 if (
auto app = def->isa<
App>()) {
516 if (app->callee()->isa<
Idx>())
return app->arg();
524 if (
auto l =
Lit::isa(size))
return l;
529 if (size->isa<
Top>())
return 64;
A (possibly paramterized) Array.
const Def * immutabilize() override
Tries to make an immutable from a mutable.
Ref reduce(Ref arg) const
static bool alpha(Ref d1, Ref d2)
bool is_set() const
Yields true if empty or the last op is set.
Ref op(size_t i) const noexcept
Ref var()
Not necessarily a Var: E.g., if the return type is [], this will yield ().
nat_t num_tprojs() const
As above but yields 1, if Flags::scalarize_threshold is exceeded.
World & world() const noexcept
Muts mut_local_muts()
All local_muts() of this mutable's deps().
std::string_view node_name() const
constexpr auto ops() const noexcept
Vars local_vars() const
Vars reachable by following immutable deps().
Ref unfold_type() const
Yields the type of this Def and builds a new Type (UInc n) if necessary.
constexpr flags_t flags() const noexcept
Def * set(size_t i, Ref)
Successively set from left to right.
T * isa_mut() const
If this is *mut*able, it will cast constness away and perform a dynamic_cast to T.
DefVec reduce(Ref arg) const
Rewrites Def::ops by substituting this mutable's Var with arg.
bool is_term() const
Yields true if this:T and T:(Type 0).
bool has_const_dep() const
Neither a Dep::Mut nor a Dep::Var; can often be used as shortcut as an optimization.
const Def * debug_prefix(std::string) const
bool is_immutabilizable()
Def * reset(size_t i, Ref def)
Successively reset from left to right.
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 }...
Ref type() const noexcept
Yields the raw type of this Def, i.e. maybe nullptr.
const Def * debug_suffix(std::string) const
constexpr node_t node() const noexcept
std::optional< nat_t > isa_lit_arity() const
Ref rebuild(World &w, Ref type, Defs ops) const
Def::rebuilds this Def while using new_op as substitute for its i'th Def::op.
Ref 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 u32 gid() const noexcept
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.
Ref refine(size_t i, Ref new_op) const
bool is_closed() const
Has no free_vars()?
Vars free_vars() const
Compute a global solution, i.e., by transitively following mutables as well.
const Var * has_var()
Only returns not nullptr, if Var of this mutable has ever been created.
constexpr size_t num_ops() const noexcept
Global * stub_(World &, Ref) override
A built-in constant of type Nat -> *.
static constexpr nat_t size2bitwidth(nat_t n)
static Ref isa(Ref def)
Checks if def is a Idx s and returns s or nullptr otherwise.
static std::optional< nat_t > isa_lit(Ref def)
This node is a hole in the IR that is inferred by its context later on.
static std::optional< T > isa(Ref def)
A (possibly paramterized) Tuple.
Ref reduce(Ref arg) const
const Def * immutabilize() override
Tries to make an immutable from a mutable.
A dependent function type.
const Pi * immutabilize() override
Tries to make an immutable from a mutable.
constexpr bool contains(const T &elem) const
constexpr bool empty() const noexcept
constexpr void clear() noexcept
Helper class to retrieve Infer::arg if present.
const Def * immutabilize() override
Tries to make an immutable from a mutable.
This is a thin wrapper for std::span<T, N> with the following additional features:
Specific Bound depending on Up.
Ref rebuild_(World &, Ref, Defs) const override
TBound * stub_(World &, Ref) override
Extremum. Either Top (Up) or Bottom.
Ref rebuild_(World &, Ref, Defs) const override
TExt * stub_(World &, Ref) override
The World represents the whole program and manages creation of MimIR nodes (Defs).
void make_internal(Def *def)
Flags & flags()
Retrieve compile Flags.
Sym sym(std::string_view)
const Pi * pi(Ref dom, Ref codom, bool implicit=false)
void make_external(Def *def)
const Lit * lit_nat(nat_t a)
const Type * type(Ref level)
Vector< const Def * > DefVec
uint64_t scalarize_threshold
size_t hash_combine(size_t seed, T v)