diff options
Diffstat (limited to 'include/clang/Analysis/Analyses/Dominators.h')
| -rw-r--r-- | include/clang/Analysis/Analyses/Dominators.h | 315 |
1 files changed, 251 insertions, 64 deletions
diff --git a/include/clang/Analysis/Analyses/Dominators.h b/include/clang/Analysis/Analyses/Dominators.h index 021e98dcd8854..061c98137da29 100644 --- a/include/clang/Analysis/Analyses/Dominators.h +++ b/include/clang/Analysis/Analyses/Dominators.h @@ -1,9 +1,8 @@ //- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// 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 // //===----------------------------------------------------------------------===// // @@ -19,6 +18,7 @@ #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" @@ -37,132 +37,319 @@ namespace clang { using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>; -/// Concrete subclass of DominatorTreeBase for Clang -/// This class implements the dominators tree functionality given a Clang CFG. -/// -class DominatorTree : public ManagedAnalysis { +/// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase. +template <bool IsPostDom> +class CFGDominatorTreeImpl : public ManagedAnalysis { virtual void anchor(); public: - llvm::DomTreeBase<CFGBlock> *DT; + using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>; - DominatorTree() { - DT = new llvm::DomTreeBase<CFGBlock>(); + CFGDominatorTreeImpl() = default; + + CFGDominatorTreeImpl(CFG *cfg) { + buildDominatorTree(cfg); } - ~DominatorTree() override { delete DT; } + ~CFGDominatorTreeImpl() override = default; + + DominatorTreeBase &getBase() { return DT; } - llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; } + CFG *getCFG() { return cfg; } - /// This method returns the root CFGBlock of the dominators tree. + /// \returns the root CFGBlock of the dominators tree. CFGBlock *getRoot() const { - return DT->getRoot(); + return DT.getRoot(); } - /// This method returns the root DomTreeNode, which is the wrapper - /// for CFGBlock. - DomTreeNode *getRootNode() const { - return DT->getRootNode(); + /// \returns the root DomTreeNode, which is the wrapper for CFGBlock. + DomTreeNode *getRootNode() { + return DT.getRootNode(); } - /// This method compares two dominator trees. - /// The method returns false if the other dominator tree matches this - /// dominator tree, otherwise returns true. - bool compare(DominatorTree &Other) const { + /// 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())) + if (DT.compare(Other.getBase())) return true; return false; } - /// This method builds the dominator tree for a given CFG - /// The CFG information is passed via AnalysisDeclContext - void buildDominatorTree(AnalysisDeclContext &AC) { - cfg = AC.getCFG(); - DT->recalculate(*cfg); + /// Builds the dominator tree for a given CFG. + void buildDominatorTree(CFG *cfg) { + assert(cfg); + this->cfg = cfg; + DT.recalculate(*cfg); } - /// This method dumps immediate dominators for each block, - /// mainly used for debug purposes. + /// Dumps immediate dominators for each block. void dump() { - llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; + llvm::errs() << "Immediate " << (IsPostDom ? "post " : "") + << "dominance tree (Node#,IDom#):\n"; for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { - if(DT->getNode(*I)->getIDom()) + + 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() << "," - << DT->getNode(*I)->getIDom()->getBlock()->getBlockID() + << IDom->getBlock()->getBlockID() << ")\n"; - else llvm::errs() << "(" << (*I)->getBlockID() - << "," << (*I)->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"; + } } } - /// This method tests if one CFGBlock dominates the other. - /// The method return true if A dominates B, false otherwise. + /// 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); + return DT.dominates(A, B); } - /// This method tests if one CFGBlock properly dominates the other. - /// The method return true if A properly dominates B, false otherwise. + /// 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); + return DT.properlyDominates(A, B); } - /// This method finds the nearest common dominator CFG block - /// for CFG block A and B. If there is no such block then return NULL. + /// \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); + return DT.findNearestCommonDominator(A, B); } const CFGBlock *findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B) { - return DT->findNearestCommonDominator(A, B); + return DT.findNearestCommonDominator(A, B); } - /// This method is used to update the dominator - /// tree information when a node's immediate dominator changes. + /// Update the dominator tree information when a node's immediate dominator + /// changes. void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { - DT->changeImmediateDominator(N, NewIDom); + DT.changeImmediateDominator(N, NewIDom); } - /// This method tests if the given CFGBlock can be reachable from root. - /// Returns true if reachable, false otherwise. + /// Tests whether \p A is reachable from the entry block. bool isReachableFromEntry(const CFGBlock *A) { - return DT->isReachableFromEntry(A); + return DT.isReachableFromEntry(A); } - /// This method releases the memory held by the dominator tree. + /// Releases the memory held by the dominator tree. virtual void releaseMemory() { - DT->releaseMemory(); + DT.releaseMemory(); } - /// This method converts the dominator tree to human readable form. + /// Converts the dominator tree to human readable form. virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const { - DT->print(OS); + 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()}; + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + 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 { + +/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an +/// if statement's condition is always false, it's 'then' branch is represented +/// with a nullptr. This however will result in a nullpointer derefernece for +/// dominator tree calculation. +/// +/// To circumvent this, let's just crudely specialize the children getters +/// used in LLVM's dominator tree builder. +namespace DomTreeBuilder { + +using ClangCFGDomChildrenGetter = +SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter< + /*Inverse=*/false>; + +template <> +template <> +inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) { + auto RChildren = reverse(children<NodePtr>(N)); + ResultTy Ret(RChildren.begin(), RChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +using ClangCFGDomReverseChildrenGetter = +SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter< + /*Inverse=*/true>; + +template <> +template <> +inline ClangCFGDomReverseChildrenGetter::ResultTy +ClangCFGDomReverseChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) { + auto IChildren = inverse_children<NodePtr>(N); + ResultTy Ret(IChildren.begin(), IChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +using ClangCFGPostDomChildrenGetter = +SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter< + /*Inverse=*/false>; + +template <> +template <> +inline ClangCFGPostDomChildrenGetter::ResultTy +ClangCFGPostDomChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) { + auto RChildren = reverse(children<NodePtr>(N)); + ResultTy Ret(RChildren.begin(), RChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +using ClangCFGPostDomReverseChildrenGetter = +SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter< + /*Inverse=*/true>; + +template <> +template <> +inline ClangCFGPostDomReverseChildrenGetter::ResultTy +ClangCFGPostDomReverseChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) { + auto IChildren = inverse_children<NodePtr>(N); + ResultTy Ret(IChildren.begin(), IChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +} // end of namespace DomTreeBuilder + //===------------------------------------- /// DominatorTree GraphTraits specialization so the DominatorTree can be /// iterable by generic graph iterators. /// -namespace llvm { - -template <> struct GraphTraits< ::clang::DomTreeNode* > { +template <> struct GraphTraits<clang::DomTreeNode *> { using NodeRef = ::clang::DomTreeNode *; using ChildIteratorType = ::clang::DomTreeNode::iterator; @@ -182,17 +369,17 @@ template <> struct GraphTraits< ::clang::DomTreeNode* > { } }; -template <> struct GraphTraits< ::clang::DominatorTree* > - : public GraphTraits< ::clang::DomTreeNode* > { - static NodeRef getEntryNode(::clang::DominatorTree *DT) { +template <> struct GraphTraits<clang::CFGDomTree *> + : public GraphTraits<clang::DomTreeNode *> { + static NodeRef getEntryNode(clang::CFGDomTree *DT) { return DT->getRootNode(); } - static nodes_iterator nodes_begin(::clang::DominatorTree *N) { + static nodes_iterator nodes_begin(clang::CFGDomTree *N) { return nodes_iterator(df_begin(getEntryNode(N))); } - static nodes_iterator nodes_end(::clang::DominatorTree *N) { + static nodes_iterator nodes_end(clang::CFGDomTree *N) { return nodes_iterator(df_end(getEntryNode(N))); } }; |