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 @@ -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,96 @@ private: CFG *cfg; + DominatorTreeBase DT; }; using CFGDomTree = CFGDominatorTreeImpl; using CFGPostDomTree = CFGDominatorTreeImpl; +} // end of namespace clang + +namespace llvm { +namespace IDFCalculatorDetail { + +/// Specialize ChildrenGetterTy to skip nullpointer successors. +template +struct ChildrenGetterTy { + using NodeRef = typename GraphTraits::NodeRef; + using ChildrenTy = SmallVector; + + ChildrenTy get(const NodeRef &N) { + using OrderedNodeTy = + typename IDFCalculatorBase::OrderedNodeTy; + + auto Children = children(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; + 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; } + + // 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 { Index: cfe/trunk/include/clang/Analysis/CFG.h =================================================================== --- cfe/trunk/include/clang/Analysis/CFG.h +++ cfe/trunk/include/clang/Analysis/CFG.h @@ -1285,6 +1285,9 @@ static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } }; +template <> struct GraphTraits + : GraphTraits {}; + template <> struct GraphTraits< const ::clang::CFGBlock *> { using NodeRef = const ::clang::CFGBlock *; using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; @@ -1294,6 +1297,9 @@ static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } }; +template <> struct GraphTraits + : GraphTraits {}; + template <> struct GraphTraits> { using NodeRef = ::clang::CFGBlock *; using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; @@ -1306,6 +1312,9 @@ static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } }; +template <> struct GraphTraits> + : GraphTraits {}; + template <> struct GraphTraits> { using NodeRef = const ::clang::CFGBlock *; using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; @@ -1318,6 +1327,9 @@ static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } }; +template <> struct GraphTraits> + : GraphTraits {}; + // Traits for: CFG template <> struct GraphTraits< ::clang::CFG* > 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 @@ -1237,6 +1237,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: cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp @@ -35,9 +35,9 @@ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, BugReporter &BR) const { if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { - CFGDomTree dom; - dom.buildDominatorTree(AC->getCFG()); - dom.dump(); + CFGDomTree Dom; + Dom.buildDominatorTree(AC->getCFG()); + Dom.dump(); } } }; @@ -61,9 +61,9 @@ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, BugReporter &BR) const { if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { - CFGPostDomTree dom; - dom.buildDominatorTree(AC->getCFG()); - dom.dump(); + CFGPostDomTree Dom; + Dom.buildDominatorTree(AC->getCFG()); + Dom.dump(); } } }; @@ -78,6 +78,31 @@ } //===----------------------------------------------------------------------===// +// 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: cfe/trunk/test/Analysis/domtest.c =================================================================== --- cfe/trunk/test/Analysis/domtest.c +++ cfe/trunk/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: cfe/trunk/test/Analysis/domtest.cpp =================================================================== --- cfe/trunk/test/Analysis/domtest.cpp +++ cfe/trunk/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: cfe/trunk/unittests/Analysis/CFGDominatorTree.cpp =================================================================== --- cfe/trunk/unittests/Analysis/CFGDominatorTree.cpp +++ cfe/trunk/unittests/Analysis/CFGDominatorTree.cpp @@ -98,6 +98,97 @@ 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); + + CFGBlock *FirstIfBlock = *(cfg->begin() + 4); + + 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