| 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 |
// placeholder node for the start node or for postdominators the exit. This node |
| 26 |
// will 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 |
|
| 40 |
namespace spvtools { |
| 41 |
namespace opt { |
| 42 |
namespace { |
| 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. |
| 56 |
template <typename BBType, typename SuccessorLambda, typename PreLambda, |
| 57 |
typename PostLambda> |
| 58 |
static 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. |
| 75 |
template <typename BBType, typename SuccessorLambda, typename PostLambda> |
| 76 |
static 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. |
| 85 |
template <typename BBType> |
| 86 |
struct 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. |
| 99 |
template <typename BBType> |
| 100 |
class 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 placeholder node. |
| 111 |
BasicBlockSuccessorHelper(Function& func, |
| 112 |
const BasicBlock* placeholder_start_node, |
| 113 |
bool post); |
| 114 |
|
| 115 |
// CFA::CalculateDominators requires std::vector<BasicBlock*>. |
| 116 |
using GetBlocksFunction = |
| 117 |
std::function<const std::vector<BasicBlock*>*(const BasicBlock*)>; |
| 118 |
|
| 119 |
// Returns the list of predecessor functions. |
| 120 |
GetBlocksFunction GetPredFunctor() { |
| 121 |
return [this](const BasicBlock* bb) { |
| 122 |
BasicBlockListTy* v = &this->predecessors_[bb]; |
| 123 |
return v; |
| 124 |
}; |
| 125 |
} |
| 126 |
|
| 127 |
// Returns a vector of the list of successor nodes from a given node. |
| 128 |
GetBlocksFunction GetSuccessorFunctor() { |
| 129 |
return [this](const BasicBlock* bb) { |
| 130 |
BasicBlockListTy* v = &this->successors_[bb]; |
| 131 |
return v; |
| 132 |
}; |
| 133 |
} |
| 134 |
|
| 135 |
private: |
| 136 |
bool invert_graph_; |
| 137 |
BasicBlockMapTy successors_; |
| 138 |
BasicBlockMapTy predecessors_; |
| 139 |
|
| 140 |
// Build the successors and predecessors map for each basic blocks |f|. |
| 141 |
// If |invert_graph_| is true, all edges are reversed (successors becomes |
| 142 |
// predecessors and vice versa). |
| 143 |
// For convenience, the start of the graph is |placeholder_start_node|. |
| 144 |
// The dominator tree construction requires a unique entry node, which cannot |
| 145 |
// be guaranteed for the postdominator graph. The |placeholder_start_node| BB |
| 146 |
// is here to gather all entry nodes. |
| 147 |
void CreateSuccessorMap(Function& f, |
| 148 |
const BasicBlock* placeholder_start_node); |
| 149 |
}; |
| 150 |
|
| 151 |
template <typename BBType> |
| 152 |
BasicBlockSuccessorHelper<BBType>::BasicBlockSuccessorHelper( |
| 153 |
Function& func, const BasicBlock* placeholder_start_node, bool invert) |
| 154 |
: invert_graph_(invert) { |
| 155 |
CreateSuccessorMap(func, placeholder_start_node); |
| 156 |
} |
| 157 |
|
| 158 |
template <typename BBType> |
| 159 |
void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap( |
| 160 |
Function& f, const BasicBlock* placeholder_start_node) { |
| 161 |
std::map<uint32_t, BasicBlock*> id_to_BB_map; |
| 162 |
auto GetSuccessorBasicBlock = [&f, &id_to_BB_map](uint32_t successor_id) { |
| 163 |
BasicBlock*& Succ = id_to_BB_map[successor_id]; |
| 164 |
if (!Succ) { |
| 165 |
for (BasicBlock& BBIt : f) { |
| 166 |
if (successor_id == BBIt.id()) { |
| 167 |
Succ = &BBIt; |
| 168 |
break; |
| 169 |
} |
| 170 |
} |
| 171 |
} |
| 172 |
return Succ; |
| 173 |
}; |
| 174 |
|
| 175 |
if (invert_graph_) { |
| 176 |
// For the post dominator tree, we see the inverted graph. |
| 177 |
// successors_ in the inverted graph are the predecessors in the CFG. |
| 178 |
// The tree construction requires 1 entry point, so we add a placeholder |
| 179 |
// node that is connected to all function exiting basic blocks. An exiting |
| 180 |
// basic block is a block with an OpKill, OpUnreachable, OpReturn, |
| 181 |
// OpReturnValue, or OpTerminateInvocation as terminator instruction. |
| 182 |
for (BasicBlock& bb : f) { |
| 183 |
if (bb.hasSuccessor()) { |
| 184 |
BasicBlockListTy& pred_list = predecessors_[&bb]; |
| 185 |
const auto& const_bb = bb; |
| 186 |
const_bb.ForEachSuccessorLabel( |
| 187 |
[this, &pred_list, &bb, |
| 188 |
&GetSuccessorBasicBlock](const uint32_t successor_id) { |
| 189 |
BasicBlock* succ = GetSuccessorBasicBlock(successor_id); |
| 190 |
// Inverted graph: our successors in the CFG |
| 191 |
// are our predecessors in the inverted graph. |
| 192 |
this->successors_[succ].push_back(&bb); |
| 193 |
pred_list.push_back(succ); |
| 194 |
}); |
| 195 |
} else { |
| 196 |
successors_[placeholder_start_node].push_back(&bb); |
| 197 |
predecessors_[&bb].push_back( |
| 198 |
const_cast<BasicBlock*>(placeholder_start_node)); |
| 199 |
} |
| 200 |
} |
| 201 |
} else { |
| 202 |
successors_[placeholder_start_node].push_back(f.entry().get()); |
| 203 |
predecessors_[f.entry().get()].push_back( |
| 204 |
const_cast<BasicBlock*>(placeholder_start_node)); |
| 205 |
for (BasicBlock& bb : f) { |
| 206 |
BasicBlockListTy& succ_list = successors_[&bb]; |
| 207 |
|
| 208 |
const auto& const_bb = bb; |
| 209 |
const_bb.ForEachSuccessorLabel([&](const uint32_t successor_id) { |
| 210 |
BasicBlock* succ = GetSuccessorBasicBlock(successor_id); |
| 211 |
succ_list.push_back(succ); |
| 212 |
predecessors_[succ].push_back(&bb); |
| 213 |
}); |
| 214 |
} |
| 215 |
} |
| 216 |
} |
| 217 |
|
| 218 |
} // namespace |
| 219 |
|
| 220 |
bool DominatorTree::StrictlyDominates(uint32_t a, uint32_t b) const { |
| 221 |
if (a == b) return false; |
| 222 |
return Dominates(a, b); |
| 223 |
} |
| 224 |
|
| 225 |
bool DominatorTree::StrictlyDominates(const BasicBlock* a, |
| 226 |
const BasicBlock* b) const { |
| 227 |
return DominatorTree::StrictlyDominates(a->id(), b->id()); |
| 228 |
} |
| 229 |
|
| 230 |
bool DominatorTree::StrictlyDominates(const DominatorTreeNode* a, |
| 231 |
const DominatorTreeNode* b) const { |
| 232 |
if (a == b) return false; |
| 233 |
return Dominates(a, b); |
| 234 |
} |
| 235 |
|
| 236 |
bool DominatorTree::Dominates(uint32_t a, uint32_t b) const { |
| 237 |
// Check that both of the inputs are actual nodes. |
| 238 |
const DominatorTreeNode* a_node = GetTreeNode(a); |
| 239 |
const DominatorTreeNode* b_node = GetTreeNode(b); |
| 240 |
if (!a_node || !b_node) return false; |
| 241 |
|
| 242 |
return Dominates(a_node, b_node); |
| 243 |
} |
| 244 |
|
| 245 |
bool DominatorTree::Dominates(const DominatorTreeNode* a, |
| 246 |
const DominatorTreeNode* b) const { |
| 247 |
if (!a || !b) return false; |
| 248 |
// Node A dominates node B if they are the same. |
| 249 |
if (a == b) return true; |
| 250 |
|
| 251 |
return a->dfs_num_pre_ < b->dfs_num_pre_ && |
| 252 |
a->dfs_num_post_ > b->dfs_num_post_; |
| 253 |
} |
| 254 |
|
| 255 |
bool DominatorTree::Dominates(const BasicBlock* A, const BasicBlock* B) const { |
| 256 |
return Dominates(A->id(), B->id()); |
| 257 |
} |
| 258 |
|
| 259 |
BasicBlock* DominatorTree::ImmediateDominator(const BasicBlock* A) const { |
| 260 |
return ImmediateDominator(A->id()); |
| 261 |
} |
| 262 |
|
| 263 |
BasicBlock* DominatorTree::ImmediateDominator(uint32_t a) const { |
| 264 |
// Check that A is a valid node in the tree. |
| 265 |
auto a_itr = nodes_.find(a); |
| 266 |
if (a_itr == nodes_.end()) return nullptr; |
| 267 |
|
| 268 |
const DominatorTreeNode* node = &a_itr->second; |
| 269 |
|
| 270 |
if (node->parent_ == nullptr) { |
| 271 |
return nullptr; |
| 272 |
} |
| 273 |
|
| 274 |
return node->parent_->bb_; |
| 275 |
} |
| 276 |
|
| 277 |
DominatorTreeNode* DominatorTree::GetOrInsertNode(BasicBlock* bb) { |
| 278 |
DominatorTreeNode* dtn = nullptr; |
| 279 |
|
| 280 |
std::map<uint32_t, DominatorTreeNode>::iterator node_iter = |
| 281 |
nodes_.find(bb->id()); |
| 282 |
if (node_iter == nodes_.end()) { |
| 283 |
dtn = &nodes_.emplace(std::make_pair(bb->id(), DominatorTreeNode{bb})) |
| 284 |
.first->second; |
| 285 |
} else { |
| 286 |
dtn = &node_iter->second; |
| 287 |
} |
| 288 |
|
| 289 |
return dtn; |
| 290 |
} |
| 291 |
|
| 292 |
void DominatorTree::GetDominatorEdges( |
| 293 |
const Function* f, const BasicBlock* placeholder_start_node, |
| 294 |
std::vector<std::pair<BasicBlock*, BasicBlock*>>* edges) { |
| 295 |
// Each time the depth first traversal calls the postorder callback |
| 296 |
// std::function we push that node into the postorder vector to create our |
| 297 |
// postorder list. |
| 298 |
std::vector<const BasicBlock*> postorder; |
| 299 |
auto postorder_function = [&](const BasicBlock* b) { |
| 300 |
postorder.push_back(b); |
| 301 |
}; |
| 302 |
|
| 303 |
// CFA::CalculateDominators requires std::vector<BasicBlock*> |
| 304 |
// BB are derived from F, so we need to const cast it at some point |
| 305 |
// no modification is made on F. |
| 306 |
BasicBlockSuccessorHelper<BasicBlock> helper{ |
| 307 |
*const_cast<Function*>(f), placeholder_start_node, postdominator_}; |
| 308 |
|
| 309 |
// The successor function tells DepthFirstTraversal how to move to successive |
| 310 |
// nodes by providing an interface to get a list of successor nodes from any |
| 311 |
// given node. |
| 312 |
auto successor_functor = helper.GetSuccessorFunctor(); |
| 313 |
|
| 314 |
// The predecessor functor does the same as the successor functor |
| 315 |
// but for all nodes preceding a given node. |
| 316 |
auto predecessor_functor = helper.GetPredFunctor(); |
| 317 |
|
| 318 |
// If we're building a post dominator tree we traverse the tree in reverse |
| 319 |
// using the predecessor function in place of the successor function and vice |
| 320 |
// versa. |
| 321 |
DepthFirstSearchPostOrder(placeholder_start_node, successor_functor, |
| 322 |
postorder_function); |
| 323 |
*edges = CFA<BasicBlock>::CalculateDominators(postorder, predecessor_functor); |
| 324 |
} |
| 325 |
|
| 326 |
void DominatorTree::InitializeTree(const CFG& cfg, const Function* f) { |
| 327 |
ClearTree(); |
| 328 |
|
| 329 |
// Skip over empty functions. |
| 330 |
if (f->cbegin() == f->cend()) { |
| 331 |
return; |
| 332 |
} |
| 333 |
|
| 334 |
const BasicBlock* placeholder_start_node = |
| 335 |
postdominator_ ? cfg.pseudo_exit_block() : cfg.pseudo_entry_block(); |
| 336 |
|
| 337 |
// Get the immediate dominator for each node. |
| 338 |
std::vector<std::pair<BasicBlock*, BasicBlock*>> edges; |
| 339 |
GetDominatorEdges(f, placeholder_start_node, &edges); |
| 340 |
|
| 341 |
// Transform the vector<pair> into the tree structure which we can use to |
| 342 |
// efficiently query dominance. |
| 343 |
for (auto edge : edges) { |
| 344 |
DominatorTreeNode* first = GetOrInsertNode(edge.first); |
| 345 |
|
| 346 |
if (edge.first == edge.second) { |
| 347 |
if (std::find(roots_.begin(), roots_.end(), first) == roots_.end()) |
| 348 |
roots_.push_back(first); |
| 349 |
continue; |
| 350 |
} |
| 351 |
|
| 352 |
DominatorTreeNode* second = GetOrInsertNode(edge.second); |
| 353 |
|
| 354 |
first->parent_ = second; |
| 355 |
second->children_.push_back(first); |
| 356 |
} |
| 357 |
ResetDFNumbering(); |
| 358 |
} |
| 359 |
|
| 360 |
void DominatorTree::ResetDFNumbering() { |
| 361 |
int index = 0; |
| 362 |
auto preFunc = [&index](const DominatorTreeNode* node) { |
| 363 |
const_cast<DominatorTreeNode*>(node)->dfs_num_pre_ = ++index; |
| 364 |
}; |
| 365 |
|
| 366 |
auto postFunc = [&index](const DominatorTreeNode* node) { |
| 367 |
const_cast<DominatorTreeNode*>(node)->dfs_num_post_ = ++index; |
| 368 |
}; |
| 369 |
|
| 370 |
auto getSucc = [](const DominatorTreeNode* node) { return &node->children_; }; |
| 371 |
|
| 372 |
for (auto root : roots_) DepthFirstSearch(root, getSucc, preFunc, postFunc); |
| 373 |
} |
| 374 |
|
| 375 |
void DominatorTree::DumpTreeAsDot(std::ostream& out_stream) const { |
| 376 |
out_stream << "digraph {\n"; |
| 377 |
Visit([&out_stream](const DominatorTreeNode* node) { |
| 378 |
// Print the node. |
| 379 |
if (node->bb_) { |
| 380 |
out_stream << node->bb_->id() << "[label=\"" << node->bb_->id() |
| 381 |
<< "\"];\n"; |
| 382 |
} |
| 383 |
|
| 384 |
// Print the arrow from the parent to this node. Entry nodes will not have |
| 385 |
// parents so draw them as children from the placeholder node. |
| 386 |
if (node->parent_) { |
| 387 |
out_stream << node->parent_->bb_->id() << " -> " << node->bb_->id() |
| 388 |
<< ";\n"; |
| 389 |
} |
| 390 |
|
| 391 |
// Return true to continue the traversal. |
| 392 |
return true; |
| 393 |
}); |
| 394 |
out_stream << "}\n"; |
| 395 |
} |
| 396 |
|
| 397 |
} // namespace opt |
| 398 |
} // namespace spvtools |