11 std::queue<const Def*> queue;
14 auto enqueue = [&](
const Def* def,
size_t i,
const Def* op) {
15 if (
nest.contains(op)) {
17 if (
auto [_, ins] = done.emplace(op); ins) queue.push(op);
21 for (
auto mut :
nest.muts()) {
23 assert_emplace(done, mut);
26 while (!queue.empty()) {
27 auto def = queue.front();
30 if (!def->is_set()) continue;
32 for (size_t i = 0, e = def->num_ops(); i != e; ++i) {
35 if (!def->op(i)->isa_mut()) enqueue(def, i, def->op(i));
43 if (
auto i = early_.find(def); i != early_.end())
return i->second;
44 if (def->
is_closed() || !
nest().contains(def))
return early_[def] =
nest().root();
45 if (
auto var = def->isa<
Var>())
return early_[def] =
nest()[var->mut()];
47 auto result =
nest().root();
48 for (
auto op : def->
deps()) {
50 auto node =
early(op);
51 if (node->level() > result->level()) result = node;
55 return early_[def] = result;
59 if (
auto i = late_.find(def); i != late_.end())
return i->second;
63 if (
auto mut = def->
isa_mut()) {
65 }
else if (
auto var = def->isa<
Var>()) {
66 result =
nest()[var->mut()];
68 for (
auto use :
uses(def)) {
69 auto mut =
late(curr_mut, use);
70 result = result ?
Nest::lca(result, mut) : mut;
74 if (!result) result =
nest()[curr_mut];
76 return late_[def] = result;
80 if (
auto i = smart_.find(def); i != smart_.end())
return i->second;
83 auto l =
late(curr_mut, def);
86 int depth = l->loop_depth();
87 for (
auto i = l; i != e;) {
91 world().ELOG(
"this should never occur - don't know where to put {}", def);
96 if (
int curr_depth = i->loop_depth(); curr_depth < depth) {
102 return smart_[def] = s;
106 if (!node->
mut()->isa<
Lam>())
return;
107 if (
auto [_, ins] = done.emplace(node->
mut()); !ins)
return;
109 for (
auto op : node->
mut()->
deps()) {
114 res.emplace_back(node->
mut());
Defs deps() const noexcept
T * isa_mut() const
If this is *mut*able, it will cast constness away and perform a dynamic_cast to T.
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
bool is_closed() const
Has no free_vars()?
Def * mut() const
The mutable capsulated in this Node or nullptr, if it's a virtual root comprising several Nodes.
Builds a nesting tree of all immutables/binders.
static const Node * lca(const Node *n, const Node *m)
Least common ancestor of n and m.
const auto & mut2node() const
const Nest::Node * smart(Def *curr, const Def *)
const Nest::Node * late(Def *curr, const Def *)
const Uses & uses(const Def *def) const
static Schedule schedule(const Nest &)
const Nest & nest() const
const Nest::Node * early(const Def *)
auto assert_emplace(C &container, Args &&... args)
Invokes emplace on container, asserts that insertion actually happened, and returns the iterator.
GIDSet< const Def * > DefSet
static void post_order(const Nest &nest, const Nest::Node *node, Scheduler::Schedule &res, MutSet &done)