11 , root_(make_node(r)) {
17 , root_(make_node(nullptr)) {
18 for (
auto mut :
muts) make_node(mut, root_);
24 , root_(make_node(nullptr)) {
29void Nest::populate() {
30 std::queue<Node*> queue;
35 for (
auto [_, child] : root_->child_mut2node_) queue.push(child);
37 while (!queue.empty()) {
38 auto curr_node =
pop(queue);
39 for (
auto op : curr_node->mut()->deps()) {
43 if (curr_node->level() < local_mut->free_vars().size()) {
44 for (
auto node = curr_node;; node = node->parent_) {
45 if (
auto var = node->mut()->has_var()) {
46 if (local_mut->free_vars().contains(var)) {
47 queue.push(make_node(local_mut, node));
55 for (
auto var : local_mut->free_vars()) {
56 if (
auto node = mut2node_nonconst(var->mut()); node && node->level() > max) {
61 queue.push(make_node(local_mut, parent));
69 auto node = std::unique_ptr<Node>(
new Node(*
this, mut, parent));
70 auto res = node.get();
71 mut2node_.emplace(mut, std::move(node));
73 if (
auto var = mut->has_var()) vars_ =
world().
vars().insert(vars_, var);
79 while (n->
level() < m->level()) m = m->parent();
83 if (n->deps().depends_.contains(m))
return n;
84 if (m->deps().depends_.contains(n))
return m;
91void Nest::deps(
Node* curr)
const {
93 for (
auto op : curr->mut()->deps()) {
95 if (
auto local_node = mut2node_nonconst(local_mut)) {
96 if (local_node == curr)
97 local_node->link(local_node);
98 else if (
auto parent = local_node->parent()) {
99 if (
auto curr_child = parent->curr_child) {
100 assert(parent->child_mut2node_.contains(curr_child->mut()));
101 curr_child->link(local_node);
109 for (
auto [_, child] : curr->child_mut2node_) {
110 curr->curr_child = child;
112 curr->curr_child =
nullptr;
116void Nest::find_SCCs(
Node* curr)
const {
118 for (
auto [_, child] : curr->child_mut2node_) {
119 child->loop_depth_ = child->is_recursive() ? curr->loop_depth() + 1 : curr->loop_depth();
124void Nest::Node::find_SCCs() {
126 for (
int i = 0;
auto& [_, node] : child_mut2node_)
127 if (node->idx_ == Unvisited) i = node->tarjan(i,
this, stack);
130uint32_t Nest::Node::tarjan(uint32_t i,
Node* parent, Stack& stack) {
131 this->idx_ = this->low_ = i++;
132 this->on_stack_ =
true;
135 for (
auto dep : this->depends_) {
136 if (dep->idx_ == Unvisited) i = dep->tarjan(i, parent, stack);
137 if (dep->on_stack_) this->low_ = std::min(this->low_, dep->low_);
140 if (this->idx_ == this->low_) {
141 parent_->topo_.emplace_front(std::make_unique<SCC>());
142 SCC* scc = parent_->topo_.front().get();
147 node->on_stack_ =
false;
148 node->recursive_ =
true;
149 node->low_ = this->idx_;
153 auto [_, ins] = parent_->SCCs_.emplace(node, scc);
155 }
while (node !=
this);
157 if (num == 1 && !this->depends_.contains(
this)) this->recursive_ =
false;
static Vector< M * > collect(World &world)
Wrapper to directly receive all closed mutables as Vector.
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
const Node * parent() const
static const Node * lca(const Node *n, const Node *m)
Least common ancestor of n and m.
const Node * root() const
const auto & mut2node() const
bool contains(const Def *def) const
The World represents the whole program and manages creation of MimIR nodes (Defs).
auto pop(S &s) -> decltype(s.top(), typename S::value_type())