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#include <iostream>
16#include <memory>
17#include <set>
18
19#include "source/cfa.h"
20#include "source/opt/dominator_tree.h"
21#include "source/opt/ir_context.h"
22
23// Calculates the dominator or postdominator tree for a given function.
24// 1 - Compute the successors and predecessors for each BasicBlock. We add a
25// dummy node for the start node or for postdominators the exit. This node will
26// point to all entry or all exit nodes.
27// 2 - Using the CFA::DepthFirstTraversal get a depth first postordered list of
28// all BasicBlocks. Using the successors (or for postdominator, predecessors)
29// calculated in step 1 to traverse the tree.
30// 3 - Pass the list calculated in step 2 to the CFA::CalculateDominators using
31// the predecessors list (or for postdominator, successors). This will give us a
32// vector of BB pairs. Each BB and its immediate dominator.
33// 4 - Using the list from 3 use those edges to build a tree of
34// DominatorTreeNodes. Each node containing a link to the parent dominator and
35// children which are dominated.
36// 5 - Using the tree from 4, perform a depth first traversal to calculate the
37// preorder and postorder index of each node. We use these indexes to compare
38// nodes against each other for domination checks.
39
40namespace spvtools {
41namespace opt {
42namespace {
43
44// Wrapper around CFA::DepthFirstTraversal to provide an interface to perform
45// depth first search on generic BasicBlock types. Will call post and pre order
46// user defined functions during traversal
47//
48// BBType - BasicBlock type. Will either be BasicBlock or DominatorTreeNode
49// SuccessorLambda - Lamdba matching the signature of 'const
50// std::vector<BBType>*(const BBType *A)'. Will return a vector of the nodes
51// succeding BasicBlock A.
52// PostLambda - Lamdba matching the signature of 'void (const BBType*)' will be
53// called on each node traversed AFTER their children.
54// PreLambda - Lamdba matching the signature of 'void (const BBType*)' will be
55// called on each node traversed BEFORE their children.
56template <typename BBType, typename SuccessorLambda, typename PreLambda,
57 typename PostLambda>
58static void DepthFirstSearch(const BBType* bb, SuccessorLambda successors,
59 PreLambda pre, PostLambda post) {
60 // Ignore backedge operation.
61 auto nop_backedge = [](const BBType*, const BBType*) {};
62 CFA<BBType>::DepthFirstTraversal(bb, successors, pre, post, nop_backedge);
63}
64
65// Wrapper around CFA::DepthFirstTraversal to provide an interface to perform
66// depth first search on generic BasicBlock types. This overload is for only
67// performing user defined post order.
68//
69// BBType - BasicBlock type. Will either be BasicBlock or DominatorTreeNode
70// SuccessorLambda - Lamdba matching the signature of 'const
71// std::vector<BBType>*(const BBType *A)'. Will return a vector of the nodes
72// succeding BasicBlock A.
73// PostLambda - Lamdba matching the signature of 'void (const BBType*)' will be
74// called on each node traversed after their children.
75template <typename BBType, typename SuccessorLambda, typename PostLambda>
76static void DepthFirstSearchPostOrder(const BBType* bb,
77 SuccessorLambda successors,
78 PostLambda post) {
79 // Ignore preorder operation.
80 auto nop_preorder = [](const BBType*) {};
81 DepthFirstSearch(bb, successors, nop_preorder, post);
82}
83
84// Small type trait to get the function class type.
85template <typename BBType>
86struct GetFunctionClass {
87 using FunctionType = Function;
88};
89
90// Helper class to compute predecessors and successors for each Basic Block in a
91// function. Through GetPredFunctor and GetSuccessorFunctor it provides an
92// interface to get the successor and predecessor lists for each basic
93// block. This is required by the DepthFirstTraversal and ComputeDominator
94// functions which take as parameter an std::function returning the successors
95// and predecessors respectively.
96//
97// When computing the post-dominator tree, all edges are inverted. So successors
98// returned by this class will be predecessors in the original CFG.
99template <typename BBType>
100class BasicBlockSuccessorHelper {
101 // This should eventually become const BasicBlock.
102 using BasicBlock = BBType;
103 using Function = typename GetFunctionClass<BBType>::FunctionType;
104
105 using BasicBlockListTy = std::vector<BasicBlock*>;
106 using BasicBlockMapTy = std::map<const BasicBlock*, BasicBlockListTy>;
107
108 public:
109 // For compliance with the dominance tree computation, entry nodes are
110 // connected to a single dummy node.
111 BasicBlockSuccessorHelper(Function& func, const BasicBlock* dummy_start_node,
112 bool post);
113
114 // CFA::CalculateDominators requires std::vector<BasicBlock*>.
115 using GetBlocksFunction =
116 std::function<const std::vector<BasicBlock*>*(const BasicBlock*)>;
117
118 // Returns the list of predecessor functions.
119 GetBlocksFunction GetPredFunctor() {
120 return [this](const BasicBlock* bb) {
121 BasicBlockListTy* v = &this->predecessors_[bb];
122 return v;
123 };
124 }
125
126 // Returns a vector of the list of successor nodes from a given node.
127 GetBlocksFunction GetSuccessorFunctor() {
128 return [this](const BasicBlock* bb) {
129 BasicBlockListTy* v = &this->successors_[bb];
130 return v;
131 };
132 }
133
134 private:
135 bool invert_graph_;
136 BasicBlockMapTy successors_;
137 BasicBlockMapTy predecessors_;
138
139 // Build the successors and predecessors map for each basic blocks |f|.
140 // If |invert_graph_| is true, all edges are reversed (successors becomes
141 // predecessors and vice versa).
142 // For convenience, the start of the graph is |dummy_start_node|.
143 // The dominator tree construction requires a unique entry node, which cannot
144 // be guaranteed for the postdominator graph. The |dummy_start_node| BB is
145 // here to gather all entry nodes.
146 void CreateSuccessorMap(Function& f, const BasicBlock* dummy_start_node);
147};
148
149template <typename BBType>
150BasicBlockSuccessorHelper<BBType>::BasicBlockSuccessorHelper(
151 Function& func, const BasicBlock* dummy_start_node, bool invert)
152 : invert_graph_(invert) {
153 CreateSuccessorMap(func, dummy_start_node);
154}
155
156template <typename BBType>
157void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap(
158 Function& f, const BasicBlock* dummy_start_node) {
159 std::map<uint32_t, BasicBlock*> id_to_BB_map;
160 auto GetSuccessorBasicBlock = [&f, &id_to_BB_map](uint32_t successor_id) {
161 BasicBlock*& Succ = id_to_BB_map[successor_id];
162 if (!Succ) {
163 for (BasicBlock& BBIt : f) {
164 if (successor_id == BBIt.id()) {
165 Succ = &BBIt;
166 break;
167 }
168 }
169 }
170 return Succ;
171 };
172
173 if (invert_graph_) {
174 // For the post dominator tree, we see the inverted graph.
175 // successors_ in the inverted graph are the predecessors in the CFG.
176 // The tree construction requires 1 entry point, so we add a dummy node
177 // that is connected to all function exiting basic blocks.
178 // An exiting basic block is a block with an OpKill, OpUnreachable,
179 // OpReturn or OpReturnValue as terminator instruction.
180 for (BasicBlock& bb : f) {
181 if (bb.hasSuccessor()) {
182 BasicBlockListTy& pred_list = predecessors_[&bb];
183 const auto& const_bb = bb;
184 const_bb.ForEachSuccessorLabel(
185 [this, &pred_list, &bb,
186 &GetSuccessorBasicBlock](const uint32_t successor_id) {
187 BasicBlock* succ = GetSuccessorBasicBlock(successor_id);
188 // Inverted graph: our successors in the CFG
189 // are our predecessors in the inverted graph.
190 this->successors_[succ].push_back(&bb);
191 pred_list.push_back(succ);
192 });
193 } else {
194 successors_[dummy_start_node].push_back(&bb);
195 predecessors_[&bb].push_back(const_cast<BasicBlock*>(dummy_start_node));
196 }
197 }
198 } else {
199 successors_[dummy_start_node].push_back(f.entry().get());
200 predecessors_[f.entry().get()].push_back(
201 const_cast<BasicBlock*>(dummy_start_node));
202 for (BasicBlock& bb : f) {
203 BasicBlockListTy& succ_list = successors_[&bb];
204
205 const auto& const_bb = bb;
206 const_bb.ForEachSuccessorLabel([&](const uint32_t successor_id) {
207 BasicBlock* succ = GetSuccessorBasicBlock(successor_id);
208 succ_list.push_back(succ);
209 predecessors_[succ].push_back(&bb);
210 });
211 }
212 }
213}
214
215} // namespace
216
217bool DominatorTree::StrictlyDominates(uint32_t a, uint32_t b) const {
218 if (a == b) return false;
219 return Dominates(a, b);
220}
221
222bool DominatorTree::StrictlyDominates(const BasicBlock* a,
223 const BasicBlock* b) const {
224 return DominatorTree::StrictlyDominates(a->id(), b->id());
225}
226
227bool DominatorTree::StrictlyDominates(const DominatorTreeNode* a,
228 const DominatorTreeNode* b) const {
229 if (a == b) return false;
230 return Dominates(a, b);
231}
232
233bool DominatorTree::Dominates(uint32_t a, uint32_t b) const {
234 // Check that both of the inputs are actual nodes.
235 const DominatorTreeNode* a_node = GetTreeNode(a);
236 const DominatorTreeNode* b_node = GetTreeNode(b);
237 if (!a_node || !b_node) return false;
238
239 return Dominates(a_node, b_node);
240}
241
242bool DominatorTree::Dominates(const DominatorTreeNode* a,
243 const DominatorTreeNode* b) const {
244 if (!a || !b) return false;
245 // Node A dominates node B if they are the same.
246 if (a == b) return true;
247
248 return a->dfs_num_pre_ < b->dfs_num_pre_ &&
249 a->dfs_num_post_ > b->dfs_num_post_;
250}
251
252bool DominatorTree::Dominates(const BasicBlock* A, const BasicBlock* B) const {
253 return Dominates(A->id(), B->id());
254}
255
256BasicBlock* DominatorTree::ImmediateDominator(const BasicBlock* A) const {
257 return ImmediateDominator(A->id());
258}
259
260BasicBlock* DominatorTree::ImmediateDominator(uint32_t a) const {
261 // Check that A is a valid node in the tree.
262 auto a_itr = nodes_.find(a);
263 if (a_itr == nodes_.end()) return nullptr;
264
265 const DominatorTreeNode* node = &a_itr->second;
266
267 if (node->parent_ == nullptr) {
268 return nullptr;
269 }
270
271 return node->parent_->bb_;
272}
273
274DominatorTreeNode* DominatorTree::GetOrInsertNode(BasicBlock* bb) {
275 DominatorTreeNode* dtn = nullptr;
276
277 std::map<uint32_t, DominatorTreeNode>::iterator node_iter =
278 nodes_.find(bb->id());
279 if (node_iter == nodes_.end()) {
280 dtn = &nodes_.emplace(std::make_pair(bb->id(), DominatorTreeNode{bb}))
281 .first->second;
282 } else {
283 dtn = &node_iter->second;
284 }
285
286 return dtn;
287}
288
289void DominatorTree::GetDominatorEdges(
290 const Function* f, const BasicBlock* dummy_start_node,
291 std::vector<std::pair<BasicBlock*, BasicBlock*>>* edges) {
292 // Each time the depth first traversal calls the postorder callback
293 // std::function we push that node into the postorder vector to create our
294 // postorder list.
295 std::vector<const BasicBlock*> postorder;
296 auto postorder_function = [&](const BasicBlock* b) {
297 postorder.push_back(b);
298 };
299
300 // CFA::CalculateDominators requires std::vector<BasicBlock*>
301 // BB are derived from F, so we need to const cast it at some point
302 // no modification is made on F.
303 BasicBlockSuccessorHelper<BasicBlock> helper{
304 *const_cast<Function*>(f), dummy_start_node, postdominator_};
305
306 // The successor function tells DepthFirstTraversal how to move to successive
307 // nodes by providing an interface to get a list of successor nodes from any
308 // given node.
309 auto successor_functor = helper.GetSuccessorFunctor();
310
311 // The predecessor functor does the same as the successor functor
312 // but for all nodes preceding a given node.
313 auto predecessor_functor = helper.GetPredFunctor();
314
315 // If we're building a post dominator tree we traverse the tree in reverse
316 // using the predecessor function in place of the successor function and vice
317 // versa.
318 DepthFirstSearchPostOrder(dummy_start_node, successor_functor,
319 postorder_function);
320 *edges = CFA<BasicBlock>::CalculateDominators(postorder, predecessor_functor);
321}
322
323void DominatorTree::InitializeTree(const CFG& cfg, const Function* f) {
324 ClearTree();
325
326 // Skip over empty functions.
327 if (f->cbegin() == f->cend()) {
328 return;
329 }
330
331 const BasicBlock* dummy_start_node =
332 postdominator_ ? cfg.pseudo_exit_block() : cfg.pseudo_entry_block();
333
334 // Get the immediate dominator for each node.
335 std::vector<std::pair<BasicBlock*, BasicBlock*>> edges;
336 GetDominatorEdges(f, dummy_start_node, &edges);
337
338 // Transform the vector<pair> into the tree structure which we can use to
339 // efficiently query dominance.
340 for (auto edge : edges) {
341 DominatorTreeNode* first = GetOrInsertNode(edge.first);
342
343 if (edge.first == edge.second) {
344 if (std::find(roots_.begin(), roots_.end(), first) == roots_.end())
345 roots_.push_back(first);
346 continue;
347 }
348
349 DominatorTreeNode* second = GetOrInsertNode(edge.second);
350
351 first->parent_ = second;
352 second->children_.push_back(first);
353 }
354 ResetDFNumbering();
355}
356
357void DominatorTree::ResetDFNumbering() {
358 int index = 0;
359 auto preFunc = [&index](const DominatorTreeNode* node) {
360 const_cast<DominatorTreeNode*>(node)->dfs_num_pre_ = ++index;
361 };
362
363 auto postFunc = [&index](const DominatorTreeNode* node) {
364 const_cast<DominatorTreeNode*>(node)->dfs_num_post_ = ++index;
365 };
366
367 auto getSucc = [](const DominatorTreeNode* node) { return &node->children_; };
368
369 for (auto root : roots_) DepthFirstSearch(root, getSucc, preFunc, postFunc);
370}
371
372void DominatorTree::DumpTreeAsDot(std::ostream& out_stream) const {
373 out_stream << "digraph {\n";
374 Visit([&out_stream](const DominatorTreeNode* node) {
375 // Print the node.
376 if (node->bb_) {
377 out_stream << node->bb_->id() << "[label=\"" << node->bb_->id()
378 << "\"];\n";
379 }
380
381 // Print the arrow from the parent to this node. Entry nodes will not have
382 // parents so draw them as children from the dummy node.
383 if (node->parent_) {
384 out_stream << node->parent_->bb_->id() << " -> " << node->bb_->id()
385 << ";\n";
386 }
387
388 // Return true to continue the traversal.
389 return true;
390 });
391 out_stream << "}\n";
392}
393
394} // namespace opt
395} // namespace spvtools
396