Index: clang/include/clang/Analysis/Analyses/Dominators.h =================================================================== --- clang/include/clang/Analysis/Analyses/Dominators.h +++ clang/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,35 @@ return Ret; } +using ClangCFGPostDomChildrenGetter = +SemiNCAInfo::ChildrenGetter< + /*Inverse=*/false>; + +template <> +template <> +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 <> +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 +274,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: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ clang/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: clang/lib/Analysis/Dominators.cpp =================================================================== --- clang/lib/Analysis/Dominators.cpp +++ clang/lib/Analysis/Dominators.cpp @@ -10,4 +10,8 @@ using namespace clang; -void DominatorTree::anchor() {} +template <> +void CFGDominatorTreeImpl::anchor() {} + +template <> +void CFGDominatorTreeImpl::anchor() {} Index: clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ clang/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(); } } @@ -51,6 +51,32 @@ return true; } +//===----------------------------------------------------------------------===// +// 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: clang/test/Analysis/domtest.c =================================================================== --- clang/test/Analysis/domtest.c +++ clang/test/Analysis/domtest.c @@ -1,6 +1,8 @@ -// RUN: rm -f %t -// RUN: %clang_analyze_cc1 -analyzer-checker=debug.DumpDominators %s > %t 2>&1 -// RUN: FileCheck --input-file=%t %s +// RUN: %clang_analyze_cc1 %s \ +// RUN: -analyzer-checker=debug.DumpCFG \ +// RUN: -analyzer-checker=debug.DumpDominators \ +// RUN: -analyzer-checker=debug.DumpPostDominators \ +// RUN: 2>&1 | FileCheck %s // Test the DominatorsTree implementation with various control flows int test1() @@ -24,17 +26,130 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,7) -// CHECK: (2,3) -// CHECK: (3,6) -// CHECK: (4,6) -// CHECK: (5,6) -// CHECK: (6,7) -// CHECK: (7,8) -// CHECK: (8,9) -// CHECK: (9,9) +// CHECK: int test1() +// CHECK-NEXT: [B9 (ENTRY)] +// CHECK-NEXT: Succs (1): B8 +// +// CHECK: [B1] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: y +// CHECK-NEXT: 4: [B1.3] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 5: [B1.2] + [B1.4] +// CHECK-NEXT: 6: z +// CHECK-NEXT: 7: [B1.6] = [B1.5] +// CHECK-NEXT: 8: 3 +// CHECK-NEXT: 9: z +// CHECK-NEXT: 10: [B1.9] = [B1.8] +// CHECK-NEXT: 11: 0 +// CHECK-NEXT: 12: return [B1.11]; +// CHECK-NEXT: Preds (1): B7 +// CHECK-NEXT: Succs (1): B0 +// +// CHECK: [B2] +// CHECK-NEXT: Preds (1): B3 +// CHECK-NEXT: Succs (1): B7 +// +// CHECK: [B3] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B3.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 1 +// CHECK-NEXT: 4: [B3.2] - [B3.3] +// CHECK-NEXT: 5: x +// CHECK-NEXT: 6: [B3.5] = [B3.4] +// CHECK-NEXT: 7: x +// CHECK-NEXT: 8: [B3.7] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 9: 1 +// CHECK-NEXT: 10: [B3.8] - [B3.9] +// CHECK-NEXT: 11: x +// CHECK-NEXT: 12: [B3.11] = [B3.10] +// CHECK-NEXT: Preds (2): B4 B5 +// CHECK-NEXT: Succs (1): B2 +// +// CHECK: [B4] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B4.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: y +// CHECK-NEXT: 4: [B4.3] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 5: [B4.2] - [B4.4] +// CHECK-NEXT: 6: z +// CHECK-NEXT: 7: [B4.6] = [B4.5] +// CHECK-NEXT: Preds (1): B6 +// CHECK-NEXT: Succs (1): B3 +// +// CHECK: [B5] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B5.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: y +// CHECK-NEXT: 4: [B5.3] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 5: [B5.2] / [B5.4] +// CHECK-NEXT: 6: x +// CHECK-NEXT: 7: [B5.6] = [B5.5] +// CHECK-NEXT: 8: y +// CHECK-NEXT: 9: [B5.8] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 10: 1 +// CHECK-NEXT: 11: [B5.9] - [B5.10] +// CHECK-NEXT: 12: y +// CHECK-NEXT: 13: [B5.12] = [B5.11] +// CHECK-NEXT: Preds (1): B6 +// CHECK-NEXT: Succs (1): B3 +// +// CHECK: [B6] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: x +// CHECK-NEXT: 4: [B6.3] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 5: [B6.2] < [B6.4] +// CHECK-NEXT: T: if [B6.5] +// CHECK-NEXT: Preds (1): B7 +// CHECK-NEXT: Succs (2): B5 B4 +// +// CHECK: [B7] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 0 +// CHECK-NEXT: 4: [B7.2] > [B7.3] +// CHECK-NEXT: T: while [B7.4] +// CHECK-NEXT: Preds (2): B2 B8 +// CHECK-NEXT: Succs (2): B6 B1 +// +// CHECK: [B8] +// CHECK-NEXT: 1: 6 +// CHECK-NEXT: 2: int x = 6; +// CHECK-NEXT: 3: x +// CHECK-NEXT: 4: [B8.3] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 5: 2 +// CHECK-NEXT: 6: [B8.4] / [B8.5] +// CHECK-NEXT: 7: int y = x / 2; +// CHECK-NEXT: 8: int z; +// CHECK-NEXT: Preds (1): B9 +// CHECK-NEXT: Succs (1): B7 +// +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: Preds (1): B1 + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,7) +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (3,6) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (6,7) +// 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() { @@ -54,15 +169,87 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,6) -// CHECK: (2,3) -// CHECK: (3,4) -// CHECK: (4,6) -// CHECK: (5,6) -// CHECK: (6,7) -// CHECK: (7,7) +// CHECK: int test2() +// CHECK-NEXT: [B7 (ENTRY)] +// CHECK-NEXT: Succs (1): B6 +// +// CHECK: [B1] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: z +// CHECK-NEXT: 4: [B1.3] = [B1.2] +// CHECK-NEXT: 5: 0 +// CHECK-NEXT: 6: return [B1.5]; +// CHECK-NEXT: Preds (2): B4 B5 +// CHECK-NEXT: Succs (1): B0 +// +// CHECK: [B2] +// CHECK-NEXT: Preds (1): B3 +// CHECK-NEXT: Succs (1): B4 +// +// CHECK: [B3] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B3.1]++ +// CHECK-NEXT: 3: y +// CHECK-NEXT: 4: [B3.3]++ +// CHECK-NEXT: Preds (1): B4 +// CHECK-NEXT: Succs (1): B2 +// +// CHECK: [B4] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B4.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 0 +// CHECK-NEXT: 4: [B4.2] <= [B4.3] +// CHECK-NEXT: T: while [B4.4] +// CHECK-NEXT: Preds (2): B2 B6 +// CHECK-NEXT: Succs (2): B3 B1 +// +// CHECK: [B5] +// CHECK-NEXT: 1: 1 +// CHECK-NEXT: 2: y +// CHECK-NEXT: 3: [B5.2] = [B5.1] +// CHECK-NEXT: Preds (1): B6 +// CHECK-NEXT: Succs (1): B1 +// +// CHECK: [B6] +// CHECK-NEXT: 1: int x; +// CHECK-NEXT: 2: int y; +// CHECK-NEXT: 3: int z; +// CHECK-NEXT: 4: 10 +// CHECK-NEXT: 5: x +// CHECK-NEXT: 6: [B6.5] = [B6.4] +// CHECK-NEXT: 7: 100 +// CHECK-NEXT: 8: y +// CHECK-NEXT: 9: [B6.8] = [B6.7] +// CHECK-NEXT: 10: x +// CHECK-NEXT: 11: [B6.10] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 12: 0 +// CHECK-NEXT: 13: [B6.11] > [B6.12] +// CHECK-NEXT: T: if [B6.13] +// CHECK-NEXT: Preds (1): B7 +// CHECK-NEXT: Succs (2): B5 B4 +// +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: Preds (1): B1 + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,6) +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,6) +// 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() { @@ -82,16 +269,105 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,7) -// CHECK: (2,5) -// CHECK: (3,4) -// CHECK: (4,5) -// CHECK: (5,6) -// CHECK: (6,7) -// CHECK: (7,8) -// CHECK: (8,8) +// CHECK: int test3() +// CHECK-NEXT: [B8 (ENTRY)] +// CHECK-NEXT: Succs (1): B7 +// +// CHECK: [B1] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: z +// CHECK-NEXT: 4: [B1.3] = [B1.2] +// CHECK-NEXT: 5: 0 +// CHECK-NEXT: 6: return [B1.5]; +// CHECK-NEXT: Preds (2): B6 B7 +// CHECK-NEXT: Succs (1): B0 +// +// CHECK: [B2] +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B6 +// +// CHECK: [B3] +// CHECK-NEXT: Preds (1): B4 +// CHECK-NEXT: Succs (1): B5 +// +// CHECK: [B4] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B4.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 1 +// CHECK-NEXT: 4: [B4.2] - [B4.3] +// CHECK-NEXT: 5: x +// CHECK-NEXT: 6: [B4.5] = [B4.4] +// CHECK-NEXT: 7: y +// CHECK-NEXT: 8: [B4.7] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 9: 2 +// CHECK-NEXT: 10: [B4.8] / [B4.9] +// CHECK-NEXT: 11: y +// CHECK-NEXT: 12: [B4.11] = [B4.10] +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B3 +// +// CHECK: [B5] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B5.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: x +// CHECK-NEXT: 4: [B5.3] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 5: [B5.2] >= [B5.4] +// CHECK-NEXT: T: while [B5.5] +// CHECK-NEXT: Preds (2): B3 B6 +// CHECK-NEXT: Succs (2): B4 B2 +// +// CHECK: [B6] +// CHECK-NEXT: 1: x +// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 0 +// CHECK-NEXT: 4: [B6.2] >= [B6.3] +// CHECK-NEXT: T: while [B6.4] +// CHECK-NEXT: Preds (2): B2 B7 +// CHECK-NEXT: Succs (2): B5 B1 +// +// CHECK: [B7] +// CHECK-NEXT: 1: int x; +// CHECK-NEXT: 2: int y; +// CHECK-NEXT: 3: int z; +// CHECK-NEXT: 4: 1 +// CHECK-NEXT: 5: z +// CHECK-NEXT: 6: [B7.5] = [B7.4] +// CHECK-NEXT: 7: y +// CHECK-NEXT: 8: [B7.7] = [B7.6] +// CHECK-NEXT: 9: x +// CHECK-NEXT: 10: [B7.9] = [B7.8] +// CHECK-NEXT: 11: x +// CHECK-NEXT: 12: [B7.11] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 13: 0 +// CHECK-NEXT: 14: [B7.12] > [B7.13] +// CHECK-NEXT: T: if [B7.14] +// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Succs (2): B6 B1 +// +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: Preds (1): B1 + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,7) +// CHECK-NEXT: (2,5) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,6) +// 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() { @@ -108,20 +384,113 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,10) -// CHECK: (2,9) -// CHECK: (3,4) -// CHECK: (4,5) -// CHECK: (5,9) -// CHECK: (6,7) -// CHECK: (7,8) -// CHECK: (8,9) -// CHECK: (9,10) -// CHECK: (10,11) -// CHECK: (11,12) -// CHECK: (12,12) +// CHECK: int test4() +// CHECK-NEXT: [B12 (ENTRY)] +// CHECK-NEXT: Succs (1): B11 +// +// CHECK: [B1] +// CHECK-NEXT: 1: 0 +// CHECK-NEXT: 2: return [B1.1]; +// CHECK-NEXT: Preds (1): B10 +// CHECK-NEXT: Succs (1): B0 +// +// CHECK: [B2] +// CHECK-NEXT: Preds (2): B5 B8 +// CHECK-NEXT: Succs (1): B10 +// +// CHECK: [B3] +// CHECK-NEXT: Preds (1): B4 +// CHECK-NEXT: Succs (1): B5 +// +// CHECK: [B4] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B4.1]++ +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B3 +// +// CHECK: [B5] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B5.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 10 +// CHECK-NEXT: 4: [B5.2] < [B5.3] +// CHECK-NEXT: T: while [B5.4] +// CHECK-NEXT: Preds (2): B3 B9 +// CHECK-NEXT: Succs (2): B4 B2 +// +// CHECK: [B6] +// CHECK-NEXT: Preds (1): B7 +// CHECK-NEXT: Succs (1): B8 +// +// CHECK: [B7] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B7.1]++ +// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Succs (1): B6 +// +// CHECK: [B8] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 0 +// CHECK-NEXT: 4: [B8.2] > [B8.3] +// CHECK-NEXT: T: while [B8.4] +// CHECK-NEXT: Preds (2): B6 B9 +// CHECK-NEXT: Succs (2): B7 B2 +// +// CHECK: [B9] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 3 +// CHECK-NEXT: 4: [B9.2] < [B9.3] +// CHECK-NEXT: T: if [B9.4] +// CHECK-NEXT: Preds (1): B10 +// CHECK-NEXT: Succs (2): B8 B5 +// +// CHECK: [B10] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B10.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 0 +// CHECK-NEXT: 4: [B10.2] > [B10.3] +// CHECK-NEXT: T: while [B10.4] +// CHECK-NEXT: Preds (2): B2 B11 +// CHECK-NEXT: Succs (2): B9 B1 +// +// CHECK: [B11] +// CHECK-NEXT: 1: 3 +// CHECK-NEXT: 2: int y = 3; +// CHECK-NEXT: Preds (1): B12 +// CHECK-NEXT: Succs (1): B10 +// +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: Preds (1): B1 + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,10) +// CHECK-NEXT: (2,9) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,9) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (9,10) +// 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() { @@ -151,18 +520,138 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,10) -// CHECK: (2,10) -// CHECK: (3,9) -// CHECK: (4,9) -// CHECK: (5,8) -// CHECK: (6,8) -// CHECK: (7,8) -// CHECK: (8,9) -// CHECK: (9,10) -// CHECK: (10,11) -// CHECK: (11,11) - +// CHECK: int test5() +// CHECK-NEXT: [B11 (ENTRY)] +// CHECK-NEXT: Succs (1): B10 +// +// CHECK: [B1] +// CHECK-NEXT: 1: 11 +// CHECK-NEXT: 2: c +// CHECK-NEXT: 3: [B1.2] = [B1.1] +// CHECK-NEXT: 4: 0 +// CHECK-NEXT: 5: return [B1.4]; +// CHECK-NEXT: Preds (2): B2 B3 +// CHECK-NEXT: Succs (1): B0 +// +// CHECK: [B2] +// CHECK-NEXT: 1: 7 +// CHECK-NEXT: 2: x +// CHECK-NEXT: 3: [B2.2] = [B2.1] +// CHECK-NEXT: Preds (1): B10 +// CHECK-NEXT: Succs (1): B1 +// +// CHECK: [B3] +// CHECK-NEXT: 1: 10 +// CHECK-NEXT: 2: b +// CHECK-NEXT: 3: [B3.2] = [B3.1] +// CHECK-NEXT: Preds (2): B4 B5 +// CHECK-NEXT: Succs (1): B1 +// +// CHECK: [B4] +// CHECK-NEXT: 1: 6 +// CHECK-NEXT: 2: x +// CHECK-NEXT: 3: [B4.2] = [B4.1] +// CHECK-NEXT: Preds (1): B9 +// CHECK-NEXT: Succs (1): B3 +// +// CHECK: [B5] +// CHECK-NEXT: 1: 10 +// CHECK-NEXT: 2: a +// CHECK-NEXT: 3: [B5.2] = [B5.1] +// CHECK-NEXT: Preds (2): B6 B7 +// CHECK-NEXT: Succs (1): B3 +// +// CHECK: [B6] +// CHECK-NEXT: 1: 5 +// CHECK-NEXT: 2: x +// CHECK-NEXT: 3: [B6.2] = [B6.1] +// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Succs (1): B5 +// +// CHECK: [B7] +// CHECK-NEXT: 1: 4 +// CHECK-NEXT: 2: x +// CHECK-NEXT: 3: [B7.2] = [B7.1] +// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Succs (1): B5 +// +// CHECK: [B8] +// CHECK-NEXT: 1: z +// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 10 +// CHECK-NEXT: 4: [B8.2] < [B8.3] +// CHECK-NEXT: T: if [B8.4] +// CHECK-NEXT: Preds (1): B9 +// CHECK-NEXT: Succs (2): B7 B6 +// +// CHECK: [B9] +// CHECK-NEXT: 1: y +// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 10 +// CHECK-NEXT: 4: [B9.2] < [B9.3] +// CHECK-NEXT: T: if [B9.4] +// CHECK-NEXT: Preds (1): B10 +// CHECK-NEXT: Succs (2): B8 B4 +// +// CHECK: [B10] +// CHECK-NEXT: 1: int x; +// CHECK-NEXT: 2: int y; +// CHECK-NEXT: 3: int z; +// CHECK-NEXT: 4: int a; +// CHECK-NEXT: 5: int b; +// CHECK-NEXT: 6: int c; +// CHECK-NEXT: 7: 1 +// CHECK-NEXT: 8: x +// CHECK-NEXT: 9: [B10.8] = [B10.7] +// CHECK-NEXT: 10: 2 +// CHECK-NEXT: 11: y +// CHECK-NEXT: 12: [B10.11] = [B10.10] +// CHECK-NEXT: 13: 3 +// CHECK-NEXT: 14: z +// CHECK-NEXT: 15: [B10.14] = [B10.13] +// CHECK-NEXT: 16: 4 +// CHECK-NEXT: 17: a +// CHECK-NEXT: 18: [B10.17] = [B10.16] +// CHECK-NEXT: 19: 5 +// CHECK-NEXT: 20: b +// CHECK-NEXT: 21: [B10.20] = [B10.19] +// CHECK-NEXT: 22: 6 +// CHECK-NEXT: 23: c +// CHECK-NEXT: 24: [B10.23] = [B10.22] +// CHECK-NEXT: 25: x +// CHECK-NEXT: 26: [B10.25] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 27: 10 +// CHECK-NEXT: 28: [B10.26] < [B10.27] +// CHECK-NEXT: T: if [B10.28] +// CHECK-NEXT: Preds (1): B11 +// CHECK-NEXT: Succs (2): B9 B2 +// +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: Preds (1): B1 +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,10) +// CHECK-NEXT: (2,10) +// CHECK-NEXT: (3,9) +// CHECK-NEXT: (4,9) +// CHECK-NEXT: (5,8) +// CHECK-NEXT: (6,8) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// 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: clang/test/Analysis/domtest.cpp =================================================================== --- clang/test/Analysis/domtest.cpp +++ clang/test/Analysis/domtest.cpp @@ -1,6 +1,7 @@ // RUN: %clang_analyze_cc1 %s \ // RUN: -analyzer-checker=debug.DumpCFG \ // RUN: -analyzer-checker=debug.DumpDominators \ +// RUN: -analyzer-checker=debug.DumpPostDominators \ // RUN: 2>&1 | FileCheck %s namespace pr42041_unreachable_cfg_successor { @@ -44,3 +45,8 @@ // 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)