Thorin 1.9.0
The Higher ORder INtermediate representation
Loading...
Searching...
No Matches
looptree.cpp
Go to the documentation of this file.
1#include "thorin/analyses/looptree.h"
2
3#include <algorithm>
4#include <iostream>
5#include <stack>
6
7#include "thorin/def.h"
8
9#include "thorin/analyses/cfg.h"
10
11/*
12 * The implementation is based on Steensgard's algorithm to find loops in irreducible CFGs.
13 *
14 * In short, Steensgard's algorithm recursively applies Tarjan's SCC algorithm to find nested SCCs.
15 * In the next recursion, backedges from the prior run are ignored.
16 * Please, check out
17 * http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
18 * for more details on Tarjan's SCC algorithm
19 */
20
21namespace thorin {
22
23namespace {
24enum {
25 InSCC = 1, // is in current walk_scc run?
26 OnStack = 2, // is in current SCC stack?
27 IsHead = 4, // all heads are marked, so subsequent runs can ignore backedges when searching for SCCs
28};
29} // namespace
30
31template<bool forward> class LoopTreeBuilder {
32public:
33 using Base = typename LoopTree<forward>::Base;
34 using Leaf = typename LoopTree<forward>::Leaf;
35 using Head = typename LoopTree<forward>::Head;
36
37 LoopTreeBuilder(LoopTree<forward>& looptree)
38 : looptree_(looptree)
39 , numbers_(cfg())
40 , states_(cfg())
41 , set_(cfg())
42 , index_(0) {
43 stack_.reserve(looptree.cfg().size());
44 build();
45 }
46
47private:
48 struct Number {
49 Number()
50 : dfs(-1)
51 , low(-1) {}
52 Number(size_t i)
53 : dfs(i)
54 , low(i) {}
55
56 size_t dfs; // depth-first-search number
57 size_t low; // low link (see Tarjan's SCC algo)
58 };
59
60 void build();
61 const CFG<forward>& cfg() const { return looptree_.cfg(); }
62 Number& number(const CFNode* n) { return numbers_[n]; }
63 size_t& lowlink(const CFNode* n) { return number(n).low; }
64 size_t& dfs(const CFNode* n) { return number(n).dfs; }
65 bool on_stack(const CFNode* n) {
66 assert(set_.contains(n));
67 return (states_[n] & OnStack) != 0;
68 }
69 bool in_scc(const CFNode* n) { return states_[n] & InSCC; }
70 bool is_head(const CFNode* n) { return states_[n] & IsHead; }
71
72 bool is_leaf(const CFNode* n, size_t num) {
73 if (num == 1) {
74 for (const auto& succ : cfg().succs(n))
75 if (!is_head(succ) && n == succ) return false;
76 return true;
77 }
78 return false;
79 }
80
81 void push(const CFNode* n) {
82 assert(set_.contains(n) && (states_[n] & OnStack) == 0);
83 stack_.emplace_back(n);
84 states_[n] |= OnStack;
85 }
86
87 int visit(const CFNode* n, int counter) {
88 visit_first(set_, n);
89 numbers_[n] = Number(counter++);
90 push(n);
91 return counter;
92 }
93
94 void recurse(Head* parent, View<const CFNode*> heads, int depth);
95 int walk_scc(const CFNode* cur, Head* parent, int depth, int scc_counter);
96
97private:
98 LoopTree<forward>& looptree_;
99 typename CFG<forward>::template Map<Number> numbers_;
100 typename CFG<forward>::template Map<uint8_t> states_;
101 typename CFG<forward>::Set set_;
102 size_t index_;
103 std::vector<const CFNode*> stack_;
104};
105
106template<bool forward> void LoopTreeBuilder<forward>::build() {
107 for (const auto& n : cfg().reverse_post_order()) // clear all flags
108 states_[n] = 0;
109
110 auto head = new Head(nullptr, 0, std::vector<const CFNode*>(0));
111 looptree_.root_.reset(head);
112 recurse(head, {cfg().entry()}, 1);
113}
114
115template<bool forward> void LoopTreeBuilder<forward>::recurse(Head* parent, View<const CFNode*> heads, int depth) {
116 size_t curr_new_child = 0;
117 for (const auto& head : heads) {
118 set_.clear();
119 walk_scc(head, parent, depth, 0);
120
121 // now mark all newly found heads globally as head
122 for (size_t e = parent->num_children(); curr_new_child != e; ++curr_new_child)
123 for (const auto& head : parent->child(curr_new_child)->cf_nodes()) states_[head] |= IsHead;
124 }
125
126 for (const auto& node : parent->children())
127 if (auto new_parent = node->template isa<Head>()) recurse(new_parent, new_parent->cf_nodes(), depth + 1);
128}
129
130template<bool forward>
131int LoopTreeBuilder<forward>::walk_scc(const CFNode* cur, Head* parent, int depth, int scc_counter) {
132 scc_counter = visit(cur, scc_counter);
133
134 for (const auto& succ : cfg().succs(cur)) {
135 if (is_head(succ)) continue; // this is a backedge
136 if (!set_.contains(succ)) {
137 scc_counter = walk_scc(succ, parent, depth, scc_counter);
138 lowlink(cur) = std::min(lowlink(cur), lowlink(succ));
139 } else if (on_stack(succ))
140 lowlink(cur) = std::min(lowlink(cur), lowlink(succ));
141 }
142
143 // root of SCC
144 if (lowlink(cur) == dfs(cur)) {
145 std::vector<const CFNode*> heads;
146
147 // mark all cf_nodes in current SCC (all cf_nodes from back to cur on the stack) as 'InSCC'
148 size_t num = 0, e = stack_.size(), b = e - 1;
149 do {
150 states_[stack_[b]] |= InSCC;
151 ++num;
152 } while (stack_[b--] != cur);
153
154 // for all cf_nodes in current SCC
155 for (size_t i = ++b; i != e; ++i) {
156 const CFNode* n = stack_[i];
157
158 if (cfg().entry() == n)
159 heads.emplace_back(n); // entries are axiomatically heads
160 else {
161 for (const auto& pred : cfg().preds(n)) {
162 // all backedges are also inducing heads
163 // but do not yet mark them globally as head -- we are still running through the SCC
164 if (!in_scc(pred)) {
165 heads.emplace_back(n);
166 break;
167 }
168 }
169 }
170 }
171
172 if (is_leaf(cur, num)) {
173 assert(heads.size() == 1);
174 looptree_.leaves_[heads.front()] = new Leaf(index_++, parent, depth, heads);
175 } else
176 new Head(parent, depth, heads);
177
178 // reset InSCC and OnStack flags
179 for (size_t i = b; i != e; ++i) states_[stack_[i]] &= ~(OnStack | InSCC);
180
181 // pop whole SCC
182 stack_.resize(b);
183 }
184
185 return scc_counter;
186}
187
188//------------------------------------------------------------------------------
189
190template<bool forward>
191LoopTree<forward>::Base::Base(Head* parent, int depth, View<const CFNode*> cf_nodes)
192 : parent_(parent)
193 , cf_nodes_(cf_nodes.begin(), cf_nodes.end())
194 , depth_(depth) {
195 if (parent_) parent_->children_.emplace_back(this);
196}
197
198template<bool forward>
199LoopTree<forward>::LoopTree(const CFG<forward>& cfg)
200 : cfg_(cfg)
201 , leaves_(cfg) {
202 LoopTreeBuilder<forward>(*this);
203}
204
205/// @name std::ostream operator
206///@{
207template<bool forward> std::ostream& operator<<(std::ostream& os, const typename LoopTree<forward>::Base* n) {
208 using LT = LoopTree<forward>;
209 if (auto l = n->template isa<typename LT::Leaf>()) return print(os, "<{} | dfs: {}", l->cf_node(), l->index());
210 if (auto h = n->template isa<typename LT::Head>()) return print(os, "[{, }]", h->cf_nodes());
211 fe::unreachable();
212}
213///@}
214
215#ifndef DOXYGEN
216template class LoopTree<true>;
217template class LoopTree<false>;
218template std::ostream& operator<< <true>(std::ostream&, const typename LoopTree<true>::Base*);
219template std::ostream& operator<< <false>(std::ostream&, const typename LoopTree<false>::Base*);
220#endif
221
222//------------------------------------------------------------------------------
223
224} // namespace thorin
thorin::CFG::Set
IndexSet< CFG< forward >, const CFNode * > Set
Definition cfg.h:119
thorin::LoopTreeBuilder::LoopTreeBuilder
LoopTreeBuilder(LoopTree< forward > &looptree)
Definition looptree.cpp:37
thorin::LoopTreeBuilder::Base
typename LoopTree< forward >::Base Base
Definition looptree.cpp:33
thorin::LoopTreeBuilder::Leaf
typename LoopTree< forward >::Leaf Leaf
Definition looptree.cpp:34
thorin::LoopTreeBuilder::Head
typename LoopTree< forward >::Head Head
Definition looptree.cpp:35
thorin::LoopTree::Base
Represents a node of a loop nesting forest.
Definition looptree.h:25
thorin::LoopTree::Base::Base
Base(Head *parent, int depth, View< const CFNode * >)
Definition looptree.cpp:191
thorin::LoopTree::Head
A Head owns further nodes as children.
Definition looptree.h:42
thorin::LoopTree::Leaf
A Leaf only holds a single CFNode and does not have any children.
Definition looptree.h:61
thorin::LoopTree
Calculates a loop nesting forest rooted at LoopTree::root_.
Definition looptree.h:16
thorin::LoopTree::LoopTreeBuilder< forward >
friend class LoopTreeBuilder< forward >
Definition looptree.h:100
thorin::LoopTree::LoopTree
LoopTree(const LoopTree &)=delete
thorin::LoopTree::cfg
const CFG< forward > & cfg() const
Definition looptree.h:84
thorin
Definition cfg.h:11
thorin::visit_first
void visit_first(IndexSet< Indexer, Key > &set, const Key &key)
Definition indexset.h:97
thorin::print
std::ostream & print(std::ostream &os, const char *s)
Base case.
Definition print.cpp:5
thorin::operator<<
std::ostream & operator<<(std::ostream &, const CFNode *)
Definition cfg.cpp:25
thorin::visit
bool visit(IndexSet< Indexer, Key > &set, const Key &key)
Definition indexset.h:95