Index: clang/include/clang/Analysis/Analyses/Dominators.h =================================================================== --- clang/include/clang/Analysis/Analyses/Dominators.h +++ clang/include/clang/Analysis/Analyses/Dominators.h @@ -44,12 +44,12 @@ public: using DominatorTreeBase = llvm::DominatorTreeBase; - DominatorTreeBase DT; - CFGDominatorTreeImpl() = default; ~CFGDominatorTreeImpl() override = default; - DominatorTreeBase& getBase() { return *DT; } + DominatorTreeBase &getBase() { return DT; } + + CFG *getCFG() { return cfg; } /// \returns the root CFGBlock of the dominators tree. CFGBlock *getRoot() const { @@ -172,11 +172,66 @@ private: CFG *cfg; + DominatorTreeBase DT; }; using CFGDomTree = CFGDominatorTreeImpl; using CFGPostDomTree = CFGDominatorTreeImpl; +class CFGControlDependencyTree : public ManagedAnalysis { + CFGDomTree DomTree; + CFGPostDomTree PostDomTree; + +public: + void buildDominatorTree(CFG *cfg) { + DomTree.buildDominatorTree(cfg); + PostDomTree.buildDominatorTree(cfg); + } + + CFGDomTree &getCFGDomTree() { return DomTree; } + const CFGDomTree &getCFGDomTree() const { return DomTree; } + CFGPostDomTree &getCFGPostDomTree() { return PostDomTree; } + const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; } + + virtual void releaseMemory() { + DomTree.releaseMemory(); + PostDomTree.releaseMemory(); + } + + bool isControlDependency(CFGBlock *A, CFGBlock *B) const { + return DomTree.dominates(A, B) && !PostDomTree.dominates(B, A); + } + + /// Dumps immediate control dependencies for each block. + void dump() { + CFG *cfg = DomTree.getCFG(); + llvm::errs() << "Immediate control dependency 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 = DomTree.getBase().getNode(*I)->getIDom(); + if (IDom) { + if (!PostDomTree.dominates(*I, IDom->getBlock())) + llvm::errs() << "(" << (*I)->getBlockID() + << "," + << IDom->getBlock()->getBlockID() + << ")\n"; + } + + bool IsEntryBlock = *I == &(*I)->getParent()->getEntry(); + assert((IDom || IsEntryBlock) && + "If the immediate dominator node is nullptr, the CFG block " + "should be the entry point (since it's the root of the dominator " + "tree)"); + (void)IsEntryBlock; + } + } +}; + } // namespace clang namespace llvm { Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -1233,6 +1233,10 @@ HelpText<"Print the post dominance tree for a given CFG">, Documentation; +def ControlDependencyTreeDumper : Checker<"DumpControlDependencies">, + HelpText<"Print the post control dependency tree for a given CFG">, + Documentation; + def LiveVariablesDumper : Checker<"DumpLiveVars">, HelpText<"Print results of live variable analysis">, Documentation; Index: clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp @@ -77,6 +77,32 @@ return true; } +//===----------------------------------------------------------------------===// +// ControlDependencyTreeDumper +//===----------------------------------------------------------------------===// + +namespace { +class ControlDependencyTreeDumper : public Checker { +public: + void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, + BugReporter &BR) const { + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { + CFGControlDependencyTree dom; + dom.buildDominatorTree(AC->getCFG()); + dom.dump(); + } + } +}; +} + +void ento::registerControlDependencyTreeDumper(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterControlDependencyTreeDumper(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,7 @@ // RUN: %clang_analyze_cc1 %s \ // RUN: -analyzer-checker=debug.DumpDominators \ // RUN: -analyzer-checker=debug.DumpPostDominators \ +// RUN: -analyzer-checker=debug.DumpControlDependencies \ // RUN: 2>&1 | FileCheck %s // Test the DominatorsTree implementation with various control flows @@ -32,7 +33,11 @@ // V // [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,7) // CHECK-NEXT: (2,3) @@ -80,7 +85,11 @@ // / V // [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,6) // CHECK-NEXT: (2,3) @@ -127,7 +136,11 @@ // \ \ // --------> [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,7) // CHECK-NEXT: (2,5) @@ -176,7 +189,13 @@ // \ // -> [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,9) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (9,10) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,10) // CHECK-NEXT: (2,9) @@ -242,7 +261,14 @@ // V [B4] -----------------> / // [B2]---------------------------------> -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: (2,10) +// CHECK-NEXT: (4,9) +// CHECK-NEXT: (6,8) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (9,10) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,10) // CHECK-NEXT: (2,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.DumpDominators \ // RUN: -analyzer-checker=debug.DumpPostDominators \ +// RUN: -analyzer-checker=debug.DumpControlDependencies \ // RUN: 2>&1 | FileCheck %s bool coin(); @@ -20,7 +21,8 @@ // [B3 (ENTRY)] -> [B1] -> [B2] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,2) // CHECK-NEXT: (1,3) // CHECK-NEXT: (2,1) @@ -42,13 +44,16 @@ } } -// ----> [B2] ----> -// / \ -// [B5 (ENTRY)] -> [B4] -> [B3] -----------> [B1] -// \ / -// ----> [B0 (EXIT)] <---- +// 1st if 2nd if +// [B5 (ENTRY)] -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)] +// \ \ / / +// \ -------------> / +// ------------------------------> -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Immediate control dependency tree (Node#,IDom#): +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,4) // CHECK-NEXT: (1,3) // CHECK-NEXT: (2,3) Index: clang/unittests/Analysis/CFGDominatorTree.cpp =================================================================== --- clang/unittests/Analysis/CFGDominatorTree.cpp +++ clang/unittests/Analysis/CFGDominatorTree.cpp @@ -117,6 +117,105 @@ EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock)); } +TEST(CFGDominatorTree, ControlDependency) { + const char *Code = R"(bool coin(); + + void funcWithBranch() { + int x = 0; + if (coin()) { + if (coin()) { + x = 5; + } + int j = 10 / x; + (void)j; + } + };)"; + BuildResult Result = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + // 1st if 2nd if + // [B5 (ENTRY)] -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)] + // \ \ / / + // \ -------------> / + // ------------------------------> + + CFG *cfg = Result.getCFG(); + + // Sanity checks. + EXPECT_EQ(cfg->size(), 6u); + + CFGBlock *ExitBlock = *cfg->begin(); + EXPECT_EQ(ExitBlock, &cfg->getExit()); + + CFGBlock *NullDerefBlock = *(cfg->begin() + 1); + + CFGBlock *SecondThenBlock = *(cfg->begin() + 2); + + CFGBlock *SecondIfBlock = *(cfg->begin() + 3); + EXPECT_TRUE(hasStmtType(SecondIfBlock)); + + CFGBlock *FirstIfBlock = *(cfg->begin() + 4); + EXPECT_TRUE(hasStmtType(FirstIfBlock)); + + CFGBlock *EntryBlock = *(cfg->begin() + 5); + EXPECT_EQ(EntryBlock, &cfg->getEntry()); + + CFGControlDependencyTree Control; + Control.buildDominatorTree(cfg); + + EXPECT_TRUE(Control.isControlDependency(SecondIfBlock, SecondThenBlock)); + EXPECT_TRUE(Control.isControlDependency(FirstIfBlock, SecondIfBlock)); + EXPECT_FALSE(Control.isControlDependency(SecondIfBlock, NullDerefBlock)); +} + +TEST(CFGDominatorTree, ControlDependencyWithLoops) { + const char *Code = R"(int test3() { + int x,y,z; + + x = y = z = 1; + if (x > 0) { + while (x >= 0){ + while (y >= x) { + x = x-1; + y = y/2; + } + } + } + z = y; + + return 0; + })"; + BuildResult Result = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + // <------------- + // / \ + // | ---> [B2] + // | / + // [B8 (ENTRY)] -> [B7] -> [B6] -> [B5] -> [B4] -> [B3] + // \ | \ / + // \ | <------------- + // \ \ + // --------> [B1] -> [B0 (EXIT)] + + CFG *cfg = Result.getCFG(); + + CFGControlDependencyTree Control; + Control.buildDominatorTree(cfg); + + auto GetBlock = [cfg] (unsigned Index) -> CFGBlock * { + assert(Index < cfg->size()); + return *(cfg->begin() + Index); + }; + + // While not immediately obvious, the second block in fact post dominates the + // fifth, hence B5 is not a control dependency of 2. + EXPECT_FALSE(Control.isControlDependency(GetBlock(5), GetBlock(2))); + EXPECT_TRUE(Control.getCFGDomTree().dominates(GetBlock(5), GetBlock(2))); + EXPECT_TRUE(Control.getCFGPostDomTree().dominates(GetBlock(2), GetBlock(5))); +} + + } // namespace } // namespace analysis } // namespace clang