MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
deptree.cpp
Go to the documentation of this file.
2
3#include "mim/world.h"
4
5namespace mim {
6
7namespace {
8void merge(VarSet& vars, VarSet&& other) { vars.insert(other.begin(), other.end()); }
9} // namespace
10
11void DepTree::run() {
12 for (const auto& [_, mut] : world().externals()) run(mut);
13 adjust_depth(root_.get(), 0);
14}
15
16VarSet DepTree::run(Def* mut) {
17 auto [i, inserted] = mut2node_.emplace(mut, std::unique_ptr<DepNode>());
18 if (!inserted) {
19 if (auto i = def2vars_.find(mut); i != def2vars_.end()) return i->second;
20 return {};
21 }
22
23 i->second = std::make_unique<DepNode>(mut, stack_.size() + 1);
24 auto node = i->second.get();
25 stack_.push_back(node);
26
27 auto result = run(mut, mut);
28 auto parent = root_.get();
29 for (auto var : result) {
30 auto n = mut2node_[var->mut()].get();
31 if (!n) {
32 world().ELOG("var {} used before mut {} discovered, old var still around?", var, var->mut());
33 world().ELOG("var {} : {} [{}]", var, var->type(), var->node_name());
34 world().ELOG("var mut {} : {}", var->mut(), var->mut()->type());
35 }
36 assert(n && "Old var still around?");
37 parent = n->depth() > parent->depth() ? n : parent;
38 }
39 if (mut->is_external() && parent != root_.get()) {
40 world().WLOG("external {} would be hidden inside parent {}.", mut, parent->mut());
41 node->set_parent(root_.get());
42 } else
43 node->set_parent(parent);
44
45 stack_.pop_back();
46 return result;
47}
48
49VarSet DepTree::run(Def* curr_mut, const Def* def) {
50 if (def->dep_const()) return {};
51 if (auto i = def2vars_.find(def); i != def2vars_.end()) return i->second;
52 if (auto mut = def->isa_mut(); mut && curr_mut != mut) return run(mut);
53
54 VarSet result;
55 if (auto var = def->isa<Var>()) {
56 result.emplace(var);
57 } else {
58 for (auto op : def->extended_ops()) merge(result, run(curr_mut, op));
59
60 if (auto v = curr_mut->var()) {
61 if (auto var = v->isa<Var>(); var && curr_mut == def) result.erase(var);
62 }
63 }
64
65 return def2vars_[def] = result;
66}
67
68void DepTree::adjust_depth(DepNode* node, size_t depth) {
69 node->depth_ = depth;
70
71 for (const auto& child : node->children()) adjust_depth(child, depth + 1);
72}
73
74bool DepTree::depends(Def* a, Def* b) const {
75 auto n = mut2node(a);
76 auto m = mut2node(b);
77
78 if (n->depth() < m->depth()) return false;
79
80 auto i = n;
81 for (size_t e = m->depth(); i->depth() != e; i = i->parent()) {}
82
83 return i == m;
84}
85
86} // namespace mim
Base class for all Defs.
Definition def.h:223
const DepNode * mut2node(Def *mut) const
Definition deptree.h:46
World & world() const
Definition deptree.h:44
bool depends(Def *a, Def *b) const
Does a depend on b?
Definition deptree.cpp:74
Definition cfg.h:11
GIDSet< const Var * > VarSet
Definition def.h:78
DefVec merge(Defs, Defs)
Definition tuple.cpp:86