dominator_tree.cpp | Explore in Territory

// 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 <iostream>
#include <memory>
#include <set>

#include "source/cfa.h"
#include "source/opt/dominator_tree.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>
void DepthFirstSearch(const BBType* bb, SuccessorLambda successors,
                      PreLambda pre, PostLambda post) { … }

// 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>
void DepthFirstSearchPostOrder(const BBType* bb, SuccessorLambda successors,
                               PostLambda post) { … }

// Small type trait to get the function class type.
template <typename BBType>
struct GetFunctionClass { … };

// 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 { … };

template <typename BBType>
BasicBlockSuccessorHelper<BBType>::BasicBlockSuccessorHelper(
    Function& func, const BasicBlock* placeholder_start_node, bool invert)
    : … { … }

template <typename BBType>
void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap(
    Function& f, const BasicBlock* placeholder_start_node) { … }

}  // namespace

bool DominatorTree::StrictlyDominates(uint32_t a, uint32_t b) const { … }

bool DominatorTree::StrictlyDominates(const BasicBlock* a,
                                      const BasicBlock* b) const { … }

bool DominatorTree::StrictlyDominates(const DominatorTreeNode* a,
                                      const DominatorTreeNode* b) const { … }

bool DominatorTree::Dominates(uint32_t a, uint32_t b) const { … }

bool DominatorTree::Dominates(const DominatorTreeNode* a,
                              const DominatorTreeNode* b) const { … }

bool DominatorTree::Dominates(const BasicBlock* A, const BasicBlock* B) const { … }

BasicBlock* DominatorTree::ImmediateDominator(const BasicBlock* A) const { … }

BasicBlock* DominatorTree::ImmediateDominator(uint32_t a) const { … }

DominatorTreeNode* DominatorTree::GetOrInsertNode(BasicBlock* bb) { … }

void DominatorTree::GetDominatorEdges(
    const Function* f, const BasicBlock* placeholder_start_node,
    std::vector<std::pair<BasicBlock*, BasicBlock*>>* edges) { … }

void DominatorTree::InitializeTree(const CFG& cfg, const Function* f) { … }

void DominatorTree::ResetDFNumbering() { … }

void DominatorTree::DumpTreeAsDot(std::ostream& out_stream) const { … }

}  // namespace opt
}  // namespace spvtools
chromium/third_party/spirv-tools/src/source/opt/dominator_tree.cpp
