Szelethus updated this revision to Diff 204972.
Szelethus retitled this revision from "[analyzer][Dominators] Add a control
dependency tree builder + a new debug checker" to "[analyzer][Dominators] Add a
control dependency calculator + a new debug checker".
Szelethus edited the summary of this revision.
Szelethus added a comment.
Now using `llvm::IDFCalculator`.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D62619/new/
https://reviews.llvm.org/D62619
Files:
clang/include/clang/Analysis/Analyses/Dominators.h
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
clang/test/Analysis/domtest.c
clang/test/Analysis/domtest.cpp
clang/unittests/Analysis/CFGDominatorTree.cpp
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<IfStmt>(SecondIfBlock));
+
+ CFGBlock *FirstIfBlock = *(cfg->begin() + 4);
+ EXPECT_TRUE(hasStmtType<IfStmt>(FirstIfBlock));
+
+ CFGBlock *EntryBlock = *(cfg->begin() + 5);
+ EXPECT_EQ(EntryBlock, &cfg->getEntry());
+
+ ControlDependencyCalculator Control(cfg);
+
+ EXPECT_TRUE(Control.isControlDependent(SecondIfBlock, SecondThenBlock));
+ EXPECT_TRUE(Control.isControlDependent(FirstIfBlock, SecondIfBlock));
+ EXPECT_FALSE(Control.isControlDependent(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();
+
+ 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
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/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/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<check::ASTCodeBody> {
+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<ControlDependencyTreeDumper>();
+}
+
+bool ento::shouldRegisterControlDependencyTreeDumper(const LangOptions &LO) {
+ return true;
+}
+
//===----------------------------------------------------------------------===//
// LiveVariablesDumper
//===----------------------------------------------------------------------===//
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<NotDocumented>;
+def ControlDependencyTreeDumper : Checker<"DumpControlDependencies">,
+ HelpText<"Print the post control dependency tree for a given CFG">,
+ Documentation<NotDocumented>;
+
def LiveVariablesDumper : Checker<"DumpLiveVars">,
HelpText<"Print results of live variable analysis">,
Documentation<NotDocumented>;
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<CFGBlock, IsPostDom>;
- 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,74 @@
private:
CFG *cfg;
+ DominatorTreeBase DT;
};
using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
+class ControlDependencyCalculator : public ManagedAnalysis {
+ using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
+ using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
+ using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
+
+ CFGPostDomTree PostDomTree;
+ IDFCalculator IDFCalc;
+
+ llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
+
+public:
+ ControlDependencyCalculator(CFG *cfg)
+ : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
+
+ CFGPostDomTree &getCFGPostDomTree() { return PostDomTree; }
+ 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 of \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 +320,41 @@
} // end of namespace DomTreeBuilder
+/// Aaaand the same goes for IDFCalculator.
+
+using ClangCFGIDFCalculator =
+ typename llvm::IDFCalculatorBase<clang::CFGBlock, false>;
+
+template<>
+inline ClangCFGIDFCalculator::ChildrenTy ClangCFGIDFCalculator::getChildren(
+ const ClangCFGIDFCalculator::NodeRef &N) {
+
+ auto Children = children<OrderedNodeTy>(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<clang::CFGBlock, true>;
+
+template<>
+inline ClangCFGPostIDFCalculator::ChildrenTy
+ClangCFGPostIDFCalculator::getChildren(
+ const ClangCFGPostIDFCalculator::NodeRef &N) {
+
+ auto Children = children<OrderedNodeTy>(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.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
