MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
domtree.cpp
Go to the documentation of this file.
2
3namespace mim {
4
5template<bool forward> void DomTreeBase<forward>::create() {
6 // Cooper et al, 2001. A Simple, Fast Dominance Algorithm. http://www.cs.rice.edu/~keith/EMBED/dom.pdf
7 idoms_[cfg().entry()] = cfg().entry();
8
9 // all idoms different from entry are set to their first found dominating pred
10 for (auto n : cfg().reverse_post_order().subspan(1)) {
11 for (auto pred : cfg().preds(n)) {
12 if (cfg().index(pred) < cfg().index(n)) {
13 idoms_[n] = pred;
14 goto outer_loop;
15 }
16 }
17 fe::unreachable();
18outer_loop:;
19 }
20
21 for (bool todo = true; todo;) {
22 todo = false;
23
24 for (auto n : cfg().reverse_post_order().subspan(1)) {
25 const CFNode* new_idom = nullptr;
26 for (auto pred : cfg().preds(n)) new_idom = new_idom ? least_common_ancestor(new_idom, pred) : pred;
27
28 assert(new_idom);
29 if (idom(n) != new_idom) {
30 idoms_[n] = new_idom;
31 todo = true;
32 }
33 }
34 }
35
36 for (auto n : cfg().reverse_post_order().subspan(1)) children_[idom(n)].push_back(n);
37}
38
39template<bool forward> void DomTreeBase<forward>::depth(const CFNode* n, int i) {
40 depth_[n] = i;
41 for (auto child : children(n)) depth(child, i + 1);
42}
43
44template<bool forward>
46 assert(i && j);
47 while (index(i) != index(j)) {
48 while (index(i) < index(j)) j = idom(j);
49 while (index(j) < index(i)) i = idom(i);
50 }
51 return i;
52}
53
54template class DomTreeBase<true>;
55template class DomTreeBase<false>;
56
57} // namespace mim
A Control-Flow Node.
Definition cfg.h:27
A Dominance Tree.
Definition schedule.h:7
int depth(const CFNode *n) const
Definition domtree.h:30
const CFNode * least_common_ancestor(const CFNode *i, const CFNode *j) const
Returns the least common ancestor of i and j.
Definition domtree.cpp:45
Definition cfg.h:11