Index: cfe/trunk/include/clang/Analysis/Analyses/Dominators.h =================================================================== --- cfe/trunk/include/clang/Analysis/Analyses/Dominators.h +++ cfe/trunk/include/clang/Analysis/Analyses/Dominators.h @@ -36,123 +36,147 @@ using DomTreeNode = llvm::DomTreeNodeBase; -/// 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 +class CFGDominatorTreeImpl : public ManagedAnalysis { virtual void anchor(); public: - llvm::DomTreeBase *DT; + using DominatorTreeBase = llvm::DominatorTreeBase; - DominatorTree() { - DT = new llvm::DomTreeBase(); - } + DominatorTreeBase DT; - ~DominatorTree() override { delete DT; } + CFGDominatorTreeImpl() = default; + ~CFGDominatorTreeImpl() override = default; - llvm::DomTreeBase& getBase() { return *DT; } + DominatorTreeBase& getBase() { return *DT; } - /// 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; }; +using CFGDomTree = CFGDominatorTreeImpl; +using CFGPostDomTree = CFGDominatorTreeImpl; + } // namespace clang namespace llvm { @@ -167,7 +191,8 @@ namespace DomTreeBuilder { using ClangCFGDomChildrenGetter = -SemiNCAInfo>::ChildrenGetter; +SemiNCAInfo::ChildrenGetter< + /*Inverse=*/false>; template <> template <> @@ -180,7 +205,8 @@ } using ClangCFGDomReverseChildrenGetter = -SemiNCAInfo>::ChildrenGetter; +SemiNCAInfo::ChildrenGetter< + /*Inverse=*/true>; template <> template <> @@ -193,6 +219,36 @@ return Ret; } +using ClangCFGPostDomChildrenGetter = +SemiNCAInfo::ChildrenGetter< + /*Inverse=*/false>; + +template <> +template <> +inline ClangCFGPostDomChildrenGetter::ResultTy +ClangCFGPostDomChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant) { + auto RChildren = reverse(children(N)); + ResultTy Ret(RChildren.begin(), RChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +using ClangCFGPostDomReverseChildrenGetter = +SemiNCAInfo::ChildrenGetter< + /*Inverse=*/true>; + +template <> +template <> +inline ClangCFGPostDomReverseChildrenGetter::ResultTy +ClangCFGPostDomReverseChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant) { + auto IChildren = inverse_children(N); + ResultTy Ret(IChildren.begin(), IChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + } // end of namespace DomTreeBuilder //===------------------------------------- @@ -219,17 +275,17 @@ } }; -template <> struct GraphTraits< ::clang::DominatorTree* > - : public GraphTraits< ::clang::DomTreeNode* > { - static NodeRef getEntryNode(::clang::DominatorTree *DT) { +template <> struct GraphTraits + : public GraphTraits { + 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))); } }; Index: cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -1229,6 +1229,10 @@ HelpText<"Print the dominance tree for a given CFG">, Documentation; +def PostDominatorsTreeDumper : Checker<"DumpPostDominators">, + HelpText<"Print the post dominance tree for a given CFG">, + Documentation; + def LiveVariablesDumper : Checker<"DumpLiveVars">, HelpText<"Print results of live variable analysis">, Documentation; Index: cfe/trunk/lib/Analysis/Dominators.cpp =================================================================== --- cfe/trunk/lib/Analysis/Dominators.cpp +++ cfe/trunk/lib/Analysis/Dominators.cpp @@ -10,4 +10,8 @@ using namespace clang; -void DominatorTree::anchor() {} +template <> +void CFGDominatorTreeImpl::anchor() {} + +template <> +void CFGDominatorTreeImpl::anchor() {} Index: cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp @@ -35,8 +35,8 @@ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, BugReporter &BR) const { if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { - DominatorTree dom; - dom.buildDominatorTree(*AC); + CFGDomTree dom; + dom.buildDominatorTree(AC->getCFG()); dom.dump(); } } @@ -52,6 +52,32 @@ } //===----------------------------------------------------------------------===// +// PostDominatorsTreeDumper +//===----------------------------------------------------------------------===// + +namespace { +class PostDominatorsTreeDumper : public Checker { +public: + void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, + BugReporter &BR) const { + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { + CFGPostDomTree dom; + dom.buildDominatorTree(AC->getCFG()); + dom.dump(); + } + } +}; +} + +void ento::registerPostDominatorsTreeDumper(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterPostDominatorsTreeDumper(const LangOptions &LO) { + return true; +} + +//===----------------------------------------------------------------------===// // LiveVariablesDumper //===----------------------------------------------------------------------===// Index: cfe/trunk/test/Analysis/domtest.c =================================================================== --- cfe/trunk/test/Analysis/domtest.c +++ cfe/trunk/test/Analysis/domtest.c @@ -1,5 +1,6 @@ // RUN: %clang_analyze_cc1 %s \ // RUN: -analyzer-checker=debug.DumpDominators \ +// RUN: -analyzer-checker=debug.DumpPostDominators \ // RUN: 2>&1 | FileCheck %s // Test the DominatorsTree implementation with various control flows @@ -42,6 +43,17 @@ // CHECK-NEXT: (7,8) // CHECK-NEXT: (8,9) // CHECK-NEXT: (9,9) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,0) +// CHECK-NEXT: (2,7) +// CHECK-NEXT: (3,2) +// CHECK-NEXT: (4,3) +// CHECK-NEXT: (5,3) +// CHECK-NEXT: (6,3) +// CHECK-NEXT: (7,1) +// CHECK-NEXT: (8,7) +// CHECK-NEXT: (9,8) int test2() { @@ -77,6 +89,15 @@ // CHECK-NEXT: (5,6) // CHECK-NEXT: (6,7) // CHECK-NEXT: (7,7) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,0) +// CHECK-NEXT: (2,4) +// CHECK-NEXT: (3,2) +// CHECK-NEXT: (4,1) +// CHECK-NEXT: (5,1) +// CHECK-NEXT: (6,1) +// CHECK-NEXT: (7,6) int test3() { @@ -116,6 +137,16 @@ // CHECK-NEXT: (6,7) // CHECK-NEXT: (7,8) // CHECK-NEXT: (8,8) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,0) +// CHECK-NEXT: (2,6) +// CHECK-NEXT: (3,5) +// CHECK-NEXT: (4,3) +// CHECK-NEXT: (5,2) +// CHECK-NEXT: (6,1) +// CHECK-NEXT: (7,1) +// CHECK-NEXT: (8,7) int test4() { @@ -159,6 +190,20 @@ // CHECK-NEXT: (10,11) // CHECK-NEXT: (11,12) // CHECK-NEXT: (12,12) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,0) +// CHECK-NEXT: (2,10) +// CHECK-NEXT: (3,5) +// CHECK-NEXT: (4,3) +// CHECK-NEXT: (5,2) +// CHECK-NEXT: (6,8) +// CHECK-NEXT: (7,6) +// CHECK-NEXT: (8,2) +// CHECK-NEXT: (9,2) +// CHECK-NEXT: (10,1) +// CHECK-NEXT: (11,10) +// CHECK-NEXT: (12,11) int test5() { @@ -210,3 +255,16 @@ // CHECK-NEXT: (9,10) // CHECK-NEXT: (10,11) // CHECK-NEXT: (11,11) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,0) +// CHECK-NEXT: (2,1) +// CHECK-NEXT: (3,1) +// CHECK-NEXT: (4,3) +// CHECK-NEXT: (5,3) +// CHECK-NEXT: (6,5) +// CHECK-NEXT: (7,5) +// CHECK-NEXT: (8,5) +// CHECK-NEXT: (9,3) +// CHECK-NEXT: (10,1) +// CHECK-NEXT: (11,10) Index: cfe/trunk/test/Analysis/domtest.cpp =================================================================== --- cfe/trunk/test/Analysis/domtest.cpp +++ cfe/trunk/test/Analysis/domtest.cpp @@ -1,5 +1,6 @@ // RUN: %clang_analyze_cc1 %s \ // RUN: -analyzer-checker=debug.DumpDominators \ +// RUN: -analyzer-checker=debug.DumpPostDominators \ // RUN: 2>&1 | FileCheck %s bool coin(); @@ -24,6 +25,11 @@ // CHECK-NEXT: (1,3) // CHECK-NEXT: (2,1) // CHECK-NEXT: (3,3) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,2) +// CHECK-NEXT: (2,0) +// CHECK-NEXT: (3,1) void funcWithBranch() { int x = 0; @@ -49,3 +55,10 @@ // CHECK-NEXT: (3,4) // CHECK-NEXT: (4,5) // CHECK-NEXT: (5,5) +// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,0) +// CHECK-NEXT: (1,0) +// CHECK-NEXT: (2,1) +// CHECK-NEXT: (3,1) +// CHECK-NEXT: (4,0) +// CHECK-NEXT: (5,4)