Szelethus created this revision.
Szelethus added reviewers: kuhar, NoQ, dcoughlin, xazax.hun, rnkovacs,
baloghadamsoftware, Charusso.
Szelethus added a project: clang.
Herald added subscribers: cfe-commits, gamesh411, dkrupp, donat.nagy,
mikhail.ramalho, a.sidorin, szepet, whisperity.
Szelethus added a parent revision: D62611: [analyzer][Dominators] Add unittests.
Block A is a control dependency of block B, is A dominates B but B doesn't post
dominate A.
In detail:
- Create the `CFGControlDependencyTree`, which in fact stores both a dominator
and a post dominator tree
- Add the new debug checker `debug.DumpControlDependencies`
- Add both lit and unit tests.
Now I'm not sure whether this is the optimal approach -- In fact I'm fairly
certain that this isn't the most efficient way of calculating control
dependencies, however, I'm not that concerned with performance just yet. This
will be used to improve bug reports the static analyzer emits, and if this
turns out to be useful, I might look enhancing this further.
Repository:
rC Clang
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,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<IfStmt>(SecondIfBlock));
+
+ CFGBlock *FirstIfBlock = *(cfg->begin() + 4);
+ EXPECT_TRUE(hasStmtType<IfStmt>(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
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/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/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<check::ASTCodeBody> {
+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<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
@@ -44,12 +44,12 @@
public:
using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
- 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</*IsPostDom*/ false>;
using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
+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 {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
