blob: 0d130ba65293227d51743126332ae669892c406d [file] [log] [blame] [edit]
// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "source/opt/dominator_tree.h"
#include <iostream>
#include <memory>
#include <set>
#include "source/cfa.h"
#include "source/opt/ir_context.h"
// Calculates the dominator or postdominator tree for a given function.
// 1 - Compute the successors and predecessors for each BasicBlock. We add a
// placeholder node for the start node or for postdominators the exit. This node
// will point to all entry or all exit nodes.
// 2 - Using the CFA::DepthFirstTraversal get a depth first postordered list of
// all BasicBlocks. Using the successors (or for postdominator, predecessors)
// calculated in step 1 to traverse the tree.
// 3 - Pass the list calculated in step 2 to the CFA::CalculateDominators using
// the predecessors list (or for postdominator, successors). This will give us a
// vector of BB pairs. Each BB and its immediate dominator.
// 4 - Using the list from 3 use those edges to build a tree of
// DominatorTreeNodes. Each node containing a link to the parent dominator and
// children which are dominated.
// 5 - Using the tree from 4, perform a depth first traversal to calculate the
// preorder and postorder index of each node. We use these indexes to compare
// nodes against each other for domination checks.
namespace spvtools {
namespace opt {
namespace {
// Wrapper around CFA::DepthFirstTraversal to provide an interface to perform
// depth first search on generic BasicBlock types. Will call post and pre order
// user defined functions during traversal
//
// BBType - BasicBlock type. Will either be BasicBlock or DominatorTreeNode
// SuccessorLambda - Lamdba matching the signature of 'const
// std::vector<BBType>*(const BBType *A)'. Will return a vector of the nodes
// succeeding BasicBlock A.
// PostLambda - Lamdba matching the signature of 'void (const BBType*)' will be
// called on each node traversed AFTER their children.
// PreLambda - Lamdba matching the signature of 'void (const BBType*)' will be
// called on each node traversed BEFORE their children.
template <typename BBType, typename SuccessorLambda, typename PreLambda,
typename PostLambda>
static void DepthFirstSearch(const BBType* bb, SuccessorLambda successors,
PreLambda pre, PostLambda post) {
auto no_terminal_blocks = [](const BBType*) { return false; };
CFA<BBType>::DepthFirstTraversal(bb, successors, pre, post,
no_terminal_blocks);
}
// Wrapper around CFA::DepthFirstTraversal to provide an interface to perform
// depth first search on generic BasicBlock types. This overload is for only
// performing user defined post order.
//
// BBType - BasicBlock type. Will either be BasicBlock or DominatorTreeNode
// SuccessorLambda - Lamdba matching the signature of 'const
// std::vector<BBType>*(const BBType *A)'. Will return a vector of the nodes
// succeeding BasicBlock A.
// PostLambda - Lamdba matching the signature of 'void (const BBType*)' will be
// called on each node traversed after their children.
template <typename BBType, typename SuccessorLambda, typename PostLambda>
static void DepthFirstSearchPostOrder(const BBType* bb,
SuccessorLambda successors,
PostLambda post) {
// Ignore preorder operation.
auto nop_preorder = [](const BBType*) {};
DepthFirstSearch(bb, successors, nop_preorder, post);
}
// Small type trait to get the function class type.
template <typename BBType>
struct GetFunctionClass {
using FunctionType = Function;
};
// Helper class to compute predecessors and successors for each Basic Block in a
// function. Through GetPredFunctor and GetSuccessorFunctor it provides an
// interface to get the successor and predecessor lists for each basic
// block. This is required by the DepthFirstTraversal and ComputeDominator
// functions which take as parameter an std::function returning the successors
// and predecessors respectively.
//
// When computing the post-dominator tree, all edges are inverted. So successors
// returned by this class will be predecessors in the original CFG.
template <typename BBType>
class BasicBlockSuccessorHelper {
// This should eventually become const BasicBlock.
using BasicBlock = BBType;
using Function = typename GetFunctionClass<BBType>::FunctionType;
using BasicBlockListTy = std::vector<BasicBlock*>;
using BasicBlockMapTy =
std::unordered_map<const BasicBlock*, BasicBlockListTy>;
public:
// For compliance with the dominance tree computation, entry nodes are
// connected to a single placeholder node.
BasicBlockSuccessorHelper(Function& func,
const BasicBlock* placeholder_start_node,
bool post);
// CFA::CalculateDominators requires std::vector<BasicBlock*>.
using GetBlocksFunction =
std::function<const std::vector<BasicBlock*>*(const BasicBlock*)>;
// Returns the list of predecessor functions.
GetBlocksFunction GetPredFunctor() {
return [this](const BasicBlock* bb) {
BasicBlockListTy* v = &this->predecessors_[bb];
return v;
};
}
// Returns a vector of the list of successor nodes from a given node.
GetBlocksFunction GetSuccessorFunctor() {
return [this](const BasicBlock* bb) {
BasicBlockListTy* v = &this->successors_[bb];
return v;
};
}
private:
bool invert_graph_;
BasicBlockMapTy successors_;
BasicBlockMapTy predecessors_;
// Build the successors and predecessors map for each basic blocks |f|.
// If |invert_graph_| is true, all edges are reversed (successors becomes
// predecessors and vice versa).
// For convenience, the start of the graph is |placeholder_start_node|.
// The dominator tree construction requires a unique entry node, which cannot
// be guaranteed for the postdominator graph. The |placeholder_start_node| BB
// is here to gather all entry nodes.
void CreateSuccessorMap(Function& f,
const BasicBlock* placeholder_start_node);
};
template <typename BBType>
BasicBlockSuccessorHelper<BBType>::BasicBlockSuccessorHelper(
Function& func, const BasicBlock* placeholder_start_node, bool invert)
: invert_graph_(invert) {
CreateSuccessorMap(func, placeholder_start_node);
}
template <typename BBType>
void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap(
Function& f, const BasicBlock* placeholder_start_node) {
IRContext* context = f.DefInst().context();
if (invert_graph_) {
// For the post dominator tree, we see the inverted graph.
// successors_ in the inverted graph are the predecessors in the CFG.
// The tree construction requires 1 entry point, so we add a placeholder
// node that is connected to all function exiting basic blocks. An exiting
// basic block is a block with an OpKill, OpUnreachable, OpReturn,
// OpReturnValue, or OpTerminateInvocation as terminator instruction.
for (BasicBlock& bb : f) {
if (bb.hasSuccessor()) {
BasicBlockListTy& pred_list = predecessors_[&bb];
const auto& const_bb = bb;
const_bb.ForEachSuccessorLabel(
[this, &pred_list, &bb, context](const uint32_t successor_id) {
BasicBlock* succ = context->get_instr_block(successor_id);
// Inverted graph: our successors in the CFG
// are our predecessors in the inverted graph.
this->successors_[succ].push_back(&bb);
pred_list.push_back(succ);
});
} else {
successors_[placeholder_start_node].push_back(&bb);
predecessors_[&bb].push_back(
const_cast<BasicBlock*>(placeholder_start_node));
}
}
} else {
successors_[placeholder_start_node].push_back(f.entry().get());
predecessors_[f.entry().get()].push_back(
const_cast<BasicBlock*>(placeholder_start_node));
for (BasicBlock& bb : f) {
BasicBlockListTy& succ_list = successors_[&bb];
const auto& const_bb = bb;
const_bb.ForEachSuccessorLabel([&](const uint32_t successor_id) {
BasicBlock* succ = context->get_instr_block(successor_id);
succ_list.push_back(succ);
predecessors_[succ].push_back(&bb);
});
}
}
}
} // namespace
bool DominatorTree::StrictlyDominates(uint32_t a, uint32_t b) const {
if (a == b) return false;
return Dominates(a, b);
}
bool DominatorTree::StrictlyDominates(const BasicBlock* a,
const BasicBlock* b) const {
return DominatorTree::StrictlyDominates(a->id(), b->id());
}
bool DominatorTree::StrictlyDominates(const DominatorTreeNode* a,
const DominatorTreeNode* b) const {
if (a == b) return false;
return Dominates(a, b);
}
bool DominatorTree::Dominates(uint32_t a, uint32_t b) const {
// Check that both of the inputs are actual nodes.
const DominatorTreeNode* a_node = GetTreeNode(a);
const DominatorTreeNode* b_node = GetTreeNode(b);
if (!a_node || !b_node) return false;
return Dominates(a_node, b_node);
}
bool DominatorTree::Dominates(const DominatorTreeNode* a,
const DominatorTreeNode* b) const {
if (!a || !b) return false;
// Node A dominates node B if they are the same.
if (a == b) return true;
return a->dfs_num_pre_ < b->dfs_num_pre_ &&
a->dfs_num_post_ > b->dfs_num_post_;
}
bool DominatorTree::Dominates(const BasicBlock* A, const BasicBlock* B) const {
return Dominates(A->id(), B->id());
}
BasicBlock* DominatorTree::ImmediateDominator(const BasicBlock* A) const {
return ImmediateDominator(A->id());
}
BasicBlock* DominatorTree::ImmediateDominator(uint32_t a) const {
// Check that A is a valid node in the tree.
auto a_itr = nodes_.find(a);
if (a_itr == nodes_.end()) return nullptr;
const DominatorTreeNode* node = &a_itr->second;
if (node->parent_ == nullptr) {
return nullptr;
}
return node->parent_->bb_;
}
DominatorTreeNode* DominatorTree::GetOrInsertNode(BasicBlock* bb) {
DominatorTreeNode* dtn = nullptr;
std::map<uint32_t, DominatorTreeNode>::iterator node_iter =
nodes_.find(bb->id());
if (node_iter == nodes_.end()) {
dtn = &nodes_.emplace(std::make_pair(bb->id(), DominatorTreeNode{bb}))
.first->second;
} else {
dtn = &node_iter->second;
}
return dtn;
}
void DominatorTree::GetDominatorEdges(
const Function* f, const BasicBlock* placeholder_start_node,
std::vector<std::pair<BasicBlock*, BasicBlock*>>* edges) {
// Each time the depth first traversal calls the postorder callback
// std::function we push that node into the postorder vector to create our
// postorder list.
std::vector<const BasicBlock*> postorder;
auto postorder_function = [&](const BasicBlock* b) {
postorder.push_back(b);
};
// CFA::CalculateDominators requires std::vector<BasicBlock*>
// BB are derived from F, so we need to const cast it at some point
// no modification is made on F.
BasicBlockSuccessorHelper<BasicBlock> helper{
*const_cast<Function*>(f), placeholder_start_node, postdominator_};
// The successor function tells DepthFirstTraversal how to move to successive
// nodes by providing an interface to get a list of successor nodes from any
// given node.
auto successor_functor = helper.GetSuccessorFunctor();
// The predecessor functor does the same as the successor functor
// but for all nodes preceding a given node.
auto predecessor_functor = helper.GetPredFunctor();
// If we're building a post dominator tree we traverse the tree in reverse
// using the predecessor function in place of the successor function and vice
// versa.
DepthFirstSearchPostOrder(placeholder_start_node, successor_functor,
postorder_function);
*edges = CFA<BasicBlock>::CalculateDominators(postorder, predecessor_functor);
}
void DominatorTree::InitializeTree(const CFG& cfg, const Function* f) {
ClearTree();
// Skip over empty functions.
if (f->cbegin() == f->cend()) {
return;
}
const BasicBlock* placeholder_start_node =
postdominator_ ? cfg.pseudo_exit_block() : cfg.pseudo_entry_block();
// Get the immediate dominator for each node.
std::vector<std::pair<BasicBlock*, BasicBlock*>> edges;
GetDominatorEdges(f, placeholder_start_node, &edges);
// Transform the vector<pair> into the tree structure which we can use to
// efficiently query dominance.
for (auto edge : edges) {
DominatorTreeNode* first = GetOrInsertNode(edge.first);
if (edge.first == edge.second) {
if (std::find(roots_.begin(), roots_.end(), first) == roots_.end())
roots_.push_back(first);
continue;
}
DominatorTreeNode* second = GetOrInsertNode(edge.second);
first->parent_ = second;
second->children_.push_back(first);
}
ResetDFNumbering();
}
void DominatorTree::ResetDFNumbering() {
int index = 0;
auto preFunc = [&index](const DominatorTreeNode* node) {
const_cast<DominatorTreeNode*>(node)->dfs_num_pre_ = ++index;
};
auto postFunc = [&index](const DominatorTreeNode* node) {
const_cast<DominatorTreeNode*>(node)->dfs_num_post_ = ++index;
};
auto getSucc = [](const DominatorTreeNode* node) { return &node->children_; };
for (auto root : roots_) DepthFirstSearch(root, getSucc, preFunc, postFunc);
}
void DominatorTree::DumpTreeAsDot(std::ostream& out_stream) const {
out_stream << "digraph {\n";
Visit([&out_stream](const DominatorTreeNode* node) {
// Print the node.
if (node->bb_) {
out_stream << node->bb_->id() << "[label=\"" << node->bb_->id()
<< "\"];\n";
}
// Print the arrow from the parent to this node. Entry nodes will not have
// parents so draw them as children from the placeholder node.
if (node->parent_) {
out_stream << node->parent_->bb_->id() << " -> " << node->bb_->id()
<< ";\n";
}
// Return true to continue the traversal.
return true;
});
out_stream << "}\n";
}
} // namespace opt
} // namespace spvtools