Thorin 1.9.0
The Higher ORder INtermediate representation
Loading...
Searching...
No Matches
looptree.h
Go to the documentation of this file.
1#pragma once
2
3#include <vector>
4
5#include <fe/cast.h>
6
7#include "thorin/analyses/cfg.h"
8
9namespace thorin {
10
11template<bool> class LoopTreeBuilder;
12
13/// Calculates a loop nesting forest rooted at LoopTree::root_.
14/// The implementation uses Steensgard's algorithm.
15/// Check out G. Ramalingam, "On Loops, Dominators, and Dominance Frontiers", 1999, for more information.
16template<bool forward> class LoopTree {
17public:
18 class Head;
19
20 /// Represents a node of a loop nesting forest.
21 /// A LoopTree::Base consists of a set of header CFNode%s.
22 /// The header CFNode%s are the set of CFNode%s not dominated by any other CFNode within the loop.
23 /// The root node is a LoopTree::Head without any CFNode%s but further children and `depth_ -1`.
24 /// Thus, the forest is pooled into a tree.
25 class Base : public fe::RuntimeCast<Base> {
26 public:
27 Base(Head* parent, int depth, View<const CFNode*>);
28 virtual ~Base() = default;
29
30 int depth() const { return depth_; }
31 const Head* parent() const { return parent_; }
32 auto cf_nodes() const { return cf_nodes_.view(); }
33 size_t num_cf_nodes() const { return cf_nodes().size(); }
34
35 protected:
36 Head* parent_;
37 Vector<const CFNode*> cf_nodes_;
38 int depth_;
39 };
40
41 /// A Head owns further nodes as children.
42 class Head : public Base {
43 private:
44 Head(Head* parent, int depth, View<const CFNode*> cf_nodes)
45 : Base(parent, depth, cf_nodes) {}
46
47 public:
48 auto children() const { return children_.view(); }
49 const Base* child(size_t i) const { return children_[i].get(); }
50 size_t num_children() const { return children().size(); }
51 bool is_root() const { return Base::parent_ == 0; }
52
53 private:
54 Vector<std::unique_ptr<Base>> children_;
55
56 friend class Base;
57 friend class LoopTreeBuilder<forward>;
58 };
59
60 /// A Leaf only holds a single CFNode and does not have any children.
61 class Leaf : public Base {
62 private:
63 Leaf(size_t index, Head* parent, int depth, View<const CFNode*> cf_nodes)
64 : Base(parent, depth, cf_nodes)
65 , index_(index) {
66 assert(Leaf::num_cf_nodes() == 1);
67 }
68
69 public:
70 const CFNode* cf_node() const { return Leaf::cf_nodes().front(); }
71 /// Index of a DFS of LoopTree::Leaf%s.
72 size_t index() const { return index_; }
73
74 private:
75 size_t index_;
76
77 friend class LoopTreeBuilder<forward>;
78 };
79
80 LoopTree(const LoopTree&) = delete;
81 LoopTree& operator=(LoopTree) = delete;
82
83 explicit LoopTree(const CFG<forward>& cfg);
84 const CFG<forward>& cfg() const { return cfg_; }
85 const Head* root() const { return root_.get(); }
86 const Leaf* operator[](const CFNode* n) const { return find(leaves_, n); }
87
88private:
89 static void get_nodes(Vector<const Base*>& nodes, const Base* node) {
90 nodes.push_back(node);
91 if (auto head = node->template isa<Head>())
92 for (const auto& child : head->children()) get_nodes(nodes, child.get());
93 }
94
95 const CFG<forward>& cfg_;
96 typename CFG<forward>::template Map<Leaf*> leaves_;
97 std::unique_ptr<Head> root_;
98
99 template<bool f> friend std::ostream& operator<<(std::ostream&, const typename LoopTree<f>::Base*);
100 friend class LoopTreeBuilder<forward>;
101};
102
103} // namespace thorin
thorin::CFNode
A Control-Flow Node.
Definition cfg.h:27
thorin::LoopTree::Base
Represents a node of a loop nesting forest.
Definition looptree.h:25
thorin::LoopTree::Base::parent
const Head * parent() const
Definition looptree.h:31
thorin::LoopTree::Base::cf_nodes
auto cf_nodes() const
Definition looptree.h:32
thorin::LoopTree::Base::~Base
virtual ~Base()=default
thorin::LoopTree::Base::depth
int depth() const
Definition looptree.h:30
thorin::LoopTree::Base::num_cf_nodes
size_t num_cf_nodes() const
Definition looptree.h:33
thorin::LoopTree::Base::cf_nodes_
Vector< const CFNode * > cf_nodes_
Definition looptree.h:37
thorin::LoopTree::Head
A Head owns further nodes as children.
Definition looptree.h:42
thorin::LoopTree::Head::is_root
bool is_root() const
Definition looptree.h:51
thorin::LoopTree::Head::child
const Base * child(size_t i) const
Definition looptree.h:49
thorin::LoopTree::Head::Base
friend class Base
Definition looptree.h:56
thorin::LoopTree::Head::children
auto children() const
Definition looptree.h:48
thorin::LoopTree::Head::num_children
size_t num_children() const
Definition looptree.h:50
thorin::LoopTree::Leaf
A Leaf only holds a single CFNode and does not have any children.
Definition looptree.h:61
thorin::LoopTree::Leaf::index
size_t index() const
Index of a DFS of LoopTree::Leafs.
Definition looptree.h:72
thorin::LoopTree::Leaf::cf_node
const CFNode * cf_node() const
Definition looptree.h:70
thorin::LoopTree
Calculates a loop nesting forest rooted at LoopTree::root_.
Definition looptree.h:16
thorin::LoopTree::LoopTree
LoopTree(const LoopTree &)=delete
thorin::LoopTree::operator<<
friend std::ostream & operator<<(std::ostream &, const typename LoopTree< f >::Base *)
thorin::LoopTree::cfg
const CFG< forward > & cfg() const
Definition looptree.h:84
thorin::LoopTree::operator=
LoopTree & operator=(LoopTree)=delete
thorin::LoopTree::root
const Head * root() const
Definition looptree.h:85
thorin::LoopTree::operator[]
const Leaf * operator[](const CFNode *n) const
Definition looptree.h:86
thorin::Vector
This is a thin wrapper for absl::InlinedVector<T, N, A> which in turn is a drop-in replacement for st...
Definition vector.h:16
thorin
Definition cfg.h:11
thorin::find
Value * find(IndexMap< Indexer, Key, Value * > &map, Key key)
Definition indexmap.h:67