Index: clang/include/clang/Analysis/Analyses/Dominators.h =================================================================== --- clang/include/clang/Analysis/Analyses/Dominators.h +++ clang/include/clang/Analysis/Analyses/Dominators.h @@ -18,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" @@ -44,12 +45,17 @@ public: using DominatorTreeBase = llvm::DominatorTreeBase; - DominatorTreeBase DT; - CFGDominatorTreeImpl() = default; + + CFGDominatorTreeImpl(CFG *cfg) { + buildDominatorTree(cfg); + } + ~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 +178,73 @@ private: CFG *cfg; + DominatorTreeBase DT; }; using CFGDomTree = CFGDominatorTreeImpl; using CFGPostDomTree = CFGDominatorTreeImpl; +class ControlDependencyCalculator : public ManagedAnalysis { + using IDFCalculator = llvm::IDFCalculatorBase; + using CFGBlockVector = llvm::SmallVector; + using CFGBlockSet = llvm::SmallPtrSet; + + CFGPostDomTree PostDomTree; + IDFCalculator IDFCalc; + + llvm::DenseMap ControlDepenencyMap; + +public: + ControlDependencyCalculator(CFG *cfg) + : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {} + + const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; } + + virtual void releaseMemory() { + PostDomTree.releaseMemory(); + } + + // 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. + 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 { @@ -251,6 +319,41 @@ } // end of namespace DomTreeBuilder +/// Aaaand the same goes for IDFCalculator. + +using ClangCFGIDFCalculator = + typename llvm::IDFCalculatorBase; + +template<> +inline ClangCFGIDFCalculator::ChildrenTy ClangCFGIDFCalculator::getChildren( + const ClangCFGIDFCalculator::NodeRef &N) { + + auto Children = children(N); + + ClangCFGIDFCalculator::ChildrenTy + Ret{Children.begin(), Children.end()}; + + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +using ClangCFGPostIDFCalculator = + typename llvm::IDFCalculatorBase; + +template<> +inline ClangCFGPostIDFCalculator::ChildrenTy +ClangCFGPostIDFCalculator::getChildren( + const ClangCFGPostIDFCalculator::NodeRef &N) { + + auto Children = children(N); + + ClangCFGPostIDFCalculator::ChildrenTy + Ret{Children.begin(), Children.end()}; + + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + //===------------------------------------- /// DominatorTree GraphTraits specialization so the DominatorTree can be /// iterable by generic graph iterators. 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,31 @@ 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)) { + ControlDependencyCalculator dom(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,16 @@ // V // [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: (2,7) +// CHECK-NEXT: (3,7) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (4,7) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (5,7) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (7,7) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,7) // CHECK-NEXT: (2,3) @@ -80,7 +90,15 @@ // / V // [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: (2,4) +// CHECK-NEXT: (2,6) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (3,6) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (4,4) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,6) // CHECK-NEXT: (2,3) @@ -117,17 +135,29 @@ return 0; } -// <------------- -// / \ -// | ---> [B2] -// | / -// [B8 (ENTRY)] -> [B7] -> [B6] -> [B5] -> [B4] -> [B3] -// \ | \ / -// \ | <------------- +// <- [B2] <- +// / \ +// [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3] +// \ | \ / +// \ | <------------- // \ \ // --------> [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: (2,6) +// CHECK-NEXT: (2,7) +// CHECK-NEXT: (3,5) +// CHECK-NEXT: (3,6) +// CHECK-NEXT: (3,7) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (4,7) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (5,5) +// CHECK-NEXT: (5,7) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (6,6) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,7) // CHECK-NEXT: (2,5) @@ -176,7 +206,29 @@ // \ // -> [B1] -> [B0 (EXIT)] -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: (2,10) +// CHECK-NEXT: (3,5) +// CHECK-NEXT: (3,9) +// CHECK-NEXT: (3,10) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (4,9) +// CHECK-NEXT: (4,10) +// CHECK-NEXT: (5,9) +// CHECK-NEXT: (5,5) +// CHECK-NEXT: (5,10) +// CHECK-NEXT: (6,8) +// CHECK-NEXT: (6,9) +// CHECK-NEXT: (6,10) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (7,9) +// CHECK-NEXT: (7,10) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (8,8) +// CHECK-NEXT: (8,10) +// CHECK-NEXT: (9,10) +// CHECK-NEXT: (10,10) +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,1) // CHECK-NEXT: (1,10) // CHECK-NEXT: (2,9) @@ -242,7 +294,23 @@ // V [B4] -----------------> / // [B2]---------------------------------> -// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: (2,10) +// CHECK-NEXT: (3,10) +// CHECK-NEXT: (4,9) +// CHECK-NEXT: (4,10) +// CHECK-NEXT: (5,9) +// CHECK-NEXT: (5,10) +// CHECK-NEXT: (6,8) +// CHECK-NEXT: (6,9) +// CHECK-NEXT: (6,10) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (7,9) +// CHECK-NEXT: (7,10) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (8,10) +// 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: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: Immediate dominance tree (Node#,IDom#): // CHECK-NEXT: (0,2) // CHECK-NEXT: (1,3) // CHECK-NEXT: (2,1) @@ -42,13 +44,18 @@ } } -// ----> [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: Control dependencies (Node#,Dependency#): +// CHECK-NEXT: (1,4) +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (2,4) +// 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,99 @@ 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()); + + ControlDependencyCalculator Control(cfg); + + EXPECT_TRUE(Control.isControlDependent(SecondThenBlock, SecondIfBlock)); + EXPECT_TRUE(Control.isControlDependent(SecondIfBlock, FirstIfBlock)); + EXPECT_FALSE(Control.isControlDependent(NullDerefBlock, SecondIfBlock)); +} + +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(); + + ControlDependencyCalculator Control(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.isControlDependent(GetBlock(5), GetBlock(2))); +} + + } // namespace } // namespace analysis } // namespace clang