//- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the dominators tree functionality for Clang CFGs.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/iterator.h"
#include "llvm/Support/GenericIteratedDominanceFrontier.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/raw_ostream.h"
// FIXME: There is no good reason for the domtree to require a print method
// which accepts an LLVM Module, so remove this (and the method's argument that
// needs it) when that is fixed.
namespace llvm {
class Module;
} // namespace llvm
namespace clang {
using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
/// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
template <bool IsPostDom>
class CFGDominatorTreeImpl : public ManagedAnalysis {
virtual void anchor();
public:
using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
CFGDominatorTreeImpl() = default;
CFGDominatorTreeImpl(CFG *cfg) {
buildDominatorTree(cfg);
}
~CFGDominatorTreeImpl() override = default;
DominatorTreeBase &getBase() { return DT; }
CFG *getCFG() { return cfg; }
/// \returns the root CFGBlock of the dominators tree.
CFGBlock *getRoot() const {
return DT.getRoot();
}
/// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
DomTreeNode *getRootNode() {
return DT.getRootNode();
}
/// Compares two dominator trees.
/// \returns false if the other dominator tree matches this dominator tree,
/// false otherwise.
bool compare(CFGDominatorTreeImpl &Other) const {
DomTreeNode *R = getRootNode();
DomTreeNode *OtherR = Other.getRootNode();
if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
return true;
if (DT.compare(Other.getBase()))
return true;
return false;
}
/// Builds the dominator tree for a given CFG.
void buildDominatorTree(CFG *cfg) {
assert(cfg);
this->cfg = cfg;
DT.recalculate(*cfg);
}
/// Dumps immediate dominators for each block.
void dump() {
llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
<< "dominance tree (Node#,IDom#):\n";
for (CFG::const_iterator I = cfg->begin(),
E = cfg->end(); I != E; ++I) {
assert(*I &&
"LLVM's Dominator tree builder uses nullpointers to signify the "
"virtual root!");
DomTreeNode *IDom = DT.getNode(*I)->getIDom();
if (IDom && IDom->getBlock())
llvm::errs() << "(" << (*I)->getBlockID()
<< ","
<< IDom->getBlock()->getBlockID()
<< ")\n";
else {
bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
bool IsExitBlock = *I == &(*I)->getParent()->getExit();
bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;
bool IsPostDomTreeRoot =
IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;
assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
"If the immediate dominator node is nullptr, the CFG block "
"should be the exit point (since it's the root of the dominator "
"tree), or if the CFG block it refers to is a nullpointer, it "
"must be the entry block (since it's the root of the post "
"dominator tree)");
(void)IsDomTreeRoot;
(void)IsPostDomTreeRoot;
llvm::errs() << "(" << (*I)->getBlockID()
<< "," << (*I)->getBlockID() << ")\n";
}
}
}
/// Tests whether \p A dominates \p B.
/// Note a block always dominates itself.
bool dominates(const CFGBlock *A, const CFGBlock *B) const {
return DT.dominates(A, B);
}
/// Tests whether \p A properly dominates \p B.
/// \returns false if \p A is the same block as \p B, otherwise whether A
/// dominates B.
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
return DT.properlyDominates(A, B);
}
/// \returns the nearest common dominator CFG block for CFG block \p A and \p
/// B. If there is no such block then return NULL.
CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
return DT.findNearestCommonDominator(A, B);
}
const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
const CFGBlock *B) {
return DT.findNearestCommonDominator(A, B);
}
/// Update the dominator tree information when a node's immediate dominator
/// changes.
void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
DT.changeImmediateDominator(N, NewIDom);
}
/// Tests whether \p A is reachable from the entry block.
bool isReachableFromEntry(const CFGBlock *A) {
return DT.isReachableFromEntry(A);
}
/// Releases the memory held by the dominator tree.
virtual void releaseMemory() { DT.reset(); }
/// Converts the dominator tree to human readable form.
virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
DT.print(OS);
}
private:
CFG *cfg;
DominatorTreeBase DT;
};
using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
template<> void CFGDominatorTreeImpl<true>::anchor();
template<> void CFGDominatorTreeImpl<false>::anchor();
} // end of namespace clang
namespace llvm {
namespace IDFCalculatorDetail {
/// Specialize ChildrenGetterTy to skip nullpointer successors.
template <bool IsPostDom>
struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;
using ChildrenTy = SmallVector<NodeRef, 8>;
ChildrenTy get(const NodeRef &N) {
using OrderedNodeTy =
typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
auto Children = children<OrderedNodeTy>(N);
ChildrenTy Ret{Children.begin(), Children.end()};
llvm::erase_value(Ret, nullptr);
return Ret;
}
};
} // end of namespace IDFCalculatorDetail
} // end of namespace llvm
namespace clang {
class ControlDependencyCalculator : public ManagedAnalysis {
using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
CFGPostDomTree PostDomTree;
IDFCalculator IDFCalc;
llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
public:
ControlDependencyCalculator(CFG *cfg)
: PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
// Lazily retrieves the set of control dependencies to \p A.
const CFGBlockVector &getControlDependencies(CFGBlock *A) {
auto It = ControlDepenencyMap.find(A);
if (It == ControlDepenencyMap.end()) {
CFGBlockSet DefiningBlock = {A};
IDFCalc.setDefiningBlocks(DefiningBlock);
CFGBlockVector ControlDependencies;
IDFCalc.calculate(ControlDependencies);
It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
}
assert(It != ControlDepenencyMap.end());
return It->second;
}
/// Whether \p A is control dependent on \p B.
bool isControlDependent(CFGBlock *A, CFGBlock *B) {
return llvm::is_contained(getControlDependencies(A), B);
}
// Dumps immediate control dependencies for each block.
LLVM_DUMP_METHOD void dump() {
CFG *cfg = PostDomTree.getCFG();
llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
for (CFGBlock *BB : *cfg) {
assert(BB &&
"LLVM's Dominator tree builder uses nullpointers to signify the "
"virtual root!");
for (CFGBlock *isControlDependency : getControlDependencies(BB))
llvm::errs() << "(" << BB->getBlockID()
<< ","
<< isControlDependency->getBlockID()
<< ")\n";
}
}
};
} // namespace clang
namespace llvm {
//===-------------------------------------
/// DominatorTree GraphTraits specialization so the DominatorTree can be
/// iterable by generic graph iterators.
///
template <> struct GraphTraits<clang::DomTreeNode *> {
using NodeRef = ::clang::DomTreeNode *;
using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
static NodeRef getEntryNode(NodeRef N) { return N; }
static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
static ChildIteratorType child_end(NodeRef N) { return N->end(); }
using nodes_iterator =
llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
return nodes_iterator(df_begin(getEntryNode(N)));
}
static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
return nodes_iterator(df_end(getEntryNode(N)));
}
};
template <> struct GraphTraits<clang::CFGDomTree *>
: public GraphTraits<clang::DomTreeNode *> {
static NodeRef getEntryNode(clang::CFGDomTree *DT) {
return DT->getRootNode();
}
static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
return nodes_iterator(df_begin(getEntryNode(N)));
}
static nodes_iterator nodes_end(clang::CFGDomTree *N) {
return nodes_iterator(df_end(getEntryNode(N)));
}
};
} // namespace llvm
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H