1// Copyright (c) 2017 Google Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_OPT_DOMINATOR_TREE_H_
16#define SOURCE_OPT_DOMINATOR_TREE_H_
17
18#include <algorithm>
19#include <cstdint>
20#include <map>
21#include <utility>
22#include <vector>
23
24#include "source/opt/cfg.h"
25#include "source/opt/tree_iterator.h"
26
27namespace spvtools {
28namespace opt {
29// This helper struct forms the nodes in the tree, with each node containing its
30// children. It also contains two values, for the pre and post indexes in the
31// tree which are used to compare two nodes.
32struct DominatorTreeNode {
33 explicit DominatorTreeNode(BasicBlock* bb)
34 : bb_(bb),
35 parent_(nullptr),
36 children_({}),
37 dfs_num_pre_(-1),
38 dfs_num_post_(-1) {}
39
40 using iterator = std::vector<DominatorTreeNode*>::iterator;
41 using const_iterator = std::vector<DominatorTreeNode*>::const_iterator;
42
43 // depth first preorder iterator.
44 using df_iterator = TreeDFIterator<DominatorTreeNode>;
45 using const_df_iterator = TreeDFIterator<const DominatorTreeNode>;
46 // depth first postorder iterator.
47 using post_iterator = PostOrderTreeDFIterator<DominatorTreeNode>;
48 using const_post_iterator = PostOrderTreeDFIterator<const DominatorTreeNode>;
49
50 iterator begin() { return children_.begin(); }
51 iterator end() { return children_.end(); }
52 const_iterator begin() const { return cbegin(); }
53 const_iterator end() const { return cend(); }
54 const_iterator cbegin() const { return children_.begin(); }
55 const_iterator cend() const { return children_.end(); }
56
57 // Depth first preorder iterator using this node as root.
58 df_iterator df_begin() { return df_iterator(this); }
59 df_iterator df_end() { return df_iterator(); }
60 const_df_iterator df_begin() const { return df_cbegin(); }
61 const_df_iterator df_end() const { return df_cend(); }
62 const_df_iterator df_cbegin() const { return const_df_iterator(this); }
63 const_df_iterator df_cend() const { return const_df_iterator(); }
64
65 // Depth first postorder iterator using this node as root.
66 post_iterator post_begin() { return post_iterator::begin(this); }
67 post_iterator post_end() { return post_iterator::end(nullptr); }
68 const_post_iterator post_begin() const { return post_cbegin(); }
69 const_post_iterator post_end() const { return post_cend(); }
70 const_post_iterator post_cbegin() const {
71 return const_post_iterator::begin(this);
72 }
73 const_post_iterator post_cend() const {
74 return const_post_iterator::end(nullptr);
75 }
76
77 inline uint32_t id() const { return bb_->id(); }
78
79 BasicBlock* bb_;
80 DominatorTreeNode* parent_;
81 std::vector<DominatorTreeNode*> children_;
82
83 // These indexes are used to compare two given nodes. A node is a child or
84 // grandchild of another node if its preorder index is greater than the
85 // first nodes preorder index AND if its postorder index is less than the
86 // first nodes postorder index.
87 int dfs_num_pre_;
88 int dfs_num_post_;
89};
90
91// A class representing a tree of BasicBlocks in a given function, where each
92// node is dominated by its parent.
93class DominatorTree {
94 public:
95 // Map OpLabel ids to dominator tree nodes
96 using DominatorTreeNodeMap = std::map<uint32_t, DominatorTreeNode>;
97 using iterator = TreeDFIterator<DominatorTreeNode>;
98 using const_iterator = TreeDFIterator<const DominatorTreeNode>;
99 using post_iterator = PostOrderTreeDFIterator<DominatorTreeNode>;
100 using const_post_iterator = PostOrderTreeDFIterator<const DominatorTreeNode>;
101
102 // List of DominatorTreeNode to define the list of roots
103 using DominatorTreeNodeList = std::vector<DominatorTreeNode*>;
104 using roots_iterator = DominatorTreeNodeList::iterator;
105 using roots_const_iterator = DominatorTreeNodeList::const_iterator;
106
107 DominatorTree() : postdominator_(false) {}
108 explicit DominatorTree(bool post) : postdominator_(post) {}
109
110 // Depth first iterators.
111 // Traverse the dominator tree in a depth first pre-order.
112 // The pseudo-block is ignored.
113 iterator begin() { return ++iterator(GetRoot()); }
114 iterator end() { return iterator(); }
115 const_iterator begin() const { return cbegin(); }
116 const_iterator end() const { return cend(); }
117 const_iterator cbegin() const { return ++const_iterator(GetRoot()); }
118 const_iterator cend() const { return const_iterator(); }
119
120 // Traverse the dominator tree in a depth first post-order.
121 // The pseudo-block is ignored.
122 post_iterator post_begin() { return post_iterator::begin(GetRoot()); }
123 post_iterator post_end() { return post_iterator::end(GetRoot()); }
124 const_post_iterator post_begin() const { return post_cbegin(); }
125 const_post_iterator post_end() const { return post_cend(); }
126 const_post_iterator post_cbegin() const {
127 return const_post_iterator::begin(GetRoot());
128 }
129 const_post_iterator post_cend() const {
130 return const_post_iterator::end(GetRoot());
131 }
132
133 roots_iterator roots_begin() { return roots_.begin(); }
134 roots_iterator roots_end() { return roots_.end(); }
135 roots_const_iterator roots_begin() const { return roots_cbegin(); }
136 roots_const_iterator roots_end() const { return roots_cend(); }
137 roots_const_iterator roots_cbegin() const { return roots_.begin(); }
138 roots_const_iterator roots_cend() const { return roots_.end(); }
139
140 // Get the unique root of the tree.
141 // It is guaranteed to work on a dominator tree.
142 // post-dominator might have a list.
143 DominatorTreeNode* GetRoot() {
144 assert(roots_.size() == 1);
145 return *roots_.begin();
146 }
147
148 const DominatorTreeNode* GetRoot() const {
149 assert(roots_.size() == 1);
150 return *roots_.begin();
151 }
152
153 const DominatorTreeNodeList& Roots() const { return roots_; }
154
155 // Dumps the tree in the graphvis dot format into the |out_stream|.
156 void DumpTreeAsDot(std::ostream& out_stream) const;
157
158 // Build the (post-)dominator tree for the given control flow graph
159 // |cfg| and the function |f|. |f| must exist in the |cfg|. Any
160 // existing data in the dominator tree will be overwritten
161 void InitializeTree(const CFG& cfg, const Function* f);
162
163 // Check if the basic block |a| dominates the basic block |b|.
164 bool Dominates(const BasicBlock* a, const BasicBlock* b) const;
165
166 // Check if the basic block id |a| dominates the basic block id |b|.
167 bool Dominates(uint32_t a, uint32_t b) const;
168
169 // Check if the dominator tree node |a| dominates the dominator tree node |b|.
170 bool Dominates(const DominatorTreeNode* a, const DominatorTreeNode* b) const;
171
172 // Check if the basic block |a| strictly dominates the basic block |b|.
173 bool StrictlyDominates(const BasicBlock* a, const BasicBlock* b) const;
174
175 // Check if the basic block id |a| strictly dominates the basic block id |b|.
176 bool StrictlyDominates(uint32_t a, uint32_t b) const;
177
178 // Check if the dominator tree node |a| strictly dominates the dominator tree
179 // node |b|.
180 bool StrictlyDominates(const DominatorTreeNode* a,
181 const DominatorTreeNode* b) const;
182
183 // Returns the immediate dominator of basic block |a|.
184 BasicBlock* ImmediateDominator(const BasicBlock* A) const;
185
186 // Returns the immediate dominator of basic block id |a|.
187 BasicBlock* ImmediateDominator(uint32_t a) const;
188
189 // Returns true if the basic block |a| is reachable by this tree. A node would
190 // be unreachable if it cannot be reached by traversal from the start node or
191 // for a postdominator tree, cannot be reached from the exit nodes.
192 inline bool ReachableFromRoots(const BasicBlock* a) const {
193 if (!a) return false;
194 return ReachableFromRoots(a->id());
195 }
196
197 // Returns true if the basic block id |a| is reachable by this tree.
198 bool ReachableFromRoots(uint32_t a) const {
199 return GetTreeNode(a) != nullptr;
200 }
201
202 // Returns true if this tree is a post dominator tree.
203 bool IsPostDominator() const { return postdominator_; }
204
205 // Clean up the tree.
206 void ClearTree() {
207 nodes_.clear();
208 roots_.clear();
209 }
210
211 // Applies the std::function |func| to all nodes in the dominator tree.
212 // Tree nodes are visited in a depth first pre-order.
213 bool Visit(std::function<bool(DominatorTreeNode*)> func) {
214 for (auto n : *this) {
215 if (!func(&n)) return false;
216 }
217 return true;
218 }
219
220 // Applies the std::function |func| to all nodes in the dominator tree.
221 // Tree nodes are visited in a depth first pre-order.
222 bool Visit(std::function<bool(const DominatorTreeNode*)> func) const {
223 for (auto n : *this) {
224 if (!func(&n)) return false;
225 }
226 return true;
227 }
228
229 // Applies the std::function |func| to all nodes in the dominator tree from
230 // |node| downwards. The boolean return from |func| is used to determine
231 // whether or not the children should also be traversed. Tree nodes are
232 // visited in a depth first pre-order.
233 void VisitChildrenIf(std::function<bool(DominatorTreeNode*)> func,
234 iterator node) {
235 if (func(&*node)) {
236 for (auto n : *node) {
237 VisitChildrenIf(func, n->df_begin());
238 }
239 }
240 }
241
242 // Returns the DominatorTreeNode associated with the basic block |bb|.
243 // If the |bb| is unknown to the dominator tree, it returns null.
244 inline DominatorTreeNode* GetTreeNode(BasicBlock* bb) {
245 return GetTreeNode(bb->id());
246 }
247 // Returns the DominatorTreeNode associated with the basic block |bb|.
248 // If the |bb| is unknown to the dominator tree, it returns null.
249 inline const DominatorTreeNode* GetTreeNode(BasicBlock* bb) const {
250 return GetTreeNode(bb->id());
251 }
252
253 // Returns the DominatorTreeNode associated with the basic block id |id|.
254 // If the id |id| is unknown to the dominator tree, it returns null.
255 inline DominatorTreeNode* GetTreeNode(uint32_t id) {
256 DominatorTreeNodeMap::iterator node_iter = nodes_.find(id);
257 if (node_iter == nodes_.end()) {
258 return nullptr;
259 }
260 return &node_iter->second;
261 }
262 // Returns the DominatorTreeNode associated with the basic block id |id|.
263 // If the id |id| is unknown to the dominator tree, it returns null.
264 inline const DominatorTreeNode* GetTreeNode(uint32_t id) const {
265 DominatorTreeNodeMap::const_iterator node_iter = nodes_.find(id);
266 if (node_iter == nodes_.end()) {
267 return nullptr;
268 }
269 return &node_iter->second;
270 }
271
272 // Adds the basic block |bb| to the tree structure if it doesn't already
273 // exist.
274 DominatorTreeNode* GetOrInsertNode(BasicBlock* bb);
275
276 // Recomputes the DF numbering of the tree.
277 void ResetDFNumbering();
278
279 private:
280 // Wrapper function which gets the list of pairs of each BasicBlocks to its
281 // immediately dominating BasicBlock and stores the result in the the edges
282 // parameter.
283 //
284 // The |edges| vector will contain the dominator tree as pairs of nodes.
285 // The first node in the pair is a node in the graph. The second node in the
286 // pair is its immediate dominator.
287 // The root of the tree has themself as immediate dominator.
288 void GetDominatorEdges(
289 const Function* f, const BasicBlock* dummy_start_node,
290 std::vector<std::pair<BasicBlock*, BasicBlock*>>* edges);
291
292 // The roots of the tree.
293 std::vector<DominatorTreeNode*> roots_;
294
295 // Pairs each basic block id to the tree node containing that basic block.
296 DominatorTreeNodeMap nodes_;
297
298 // True if this is a post dominator tree.
299 bool postdominator_;
300};
301
302} // namespace opt
303} // namespace spvtools
304
305#endif // SOURCE_OPT_DOMINATOR_TREE_H_
306