Szelethus updated this revision to Diff 211119.
Szelethus added a comment.
I plan to split this patch up eventually, but here's where I'm standing right
now:
- Correct the algorithm that by accident did this: `GEN[B] = GEN[B] union
(IN[B] - KILL[B])` instead of this: `OUT[B] = GEN[B] union (IN[B] - KILL[B])`
- Realize that `llvm::SmallSet` uses both `operator==` and `operator<`, and
since for a reaching definition set I'd like to sort by `VarDecl`, but for the
kill set that AND the `CFGElementRef`, give up on it and use `std::set` instead
with two different comparators
- Collect all non-local variables and regard all function calls as definitions
to them
- Collect parameter declarations as well, add them to `GEN[entry block]`
- Plenty more test cases
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D64991/new/
https://reviews.llvm.org/D64991
Files:
clang/include/clang/Analysis/Analyses/ReachingDefinitions.h
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
clang/lib/Analysis/CMakeLists.txt
clang/lib/Analysis/ReachingDefinitions.cpp
clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
clang/test/Analysis/dump-definitions.cpp
Index: clang/test/Analysis/dump-definitions.cpp
===================================================================
--- /dev/null
+++ clang/test/Analysis/dump-definitions.cpp
@@ -0,0 +1,385 @@
+// RUN: %clang_analyze_cc1 %s \
+// RUN: -analyzer-checker=debug.DumpCFG \
+// RUN: -analyzer-checker=debug.DumpGenSets \
+// RUN: -analyzer-checker=debug.DumpKillSets \
+// RUN: -analyzer-checker=debug.DumpReachingDefinitions \
+// RUN: 2>&1 | FileCheck %s
+
+int global_var;
+
+int getInt();
+int *getIntPtr();
+bool coin();
+
+
+void single_vardecl_in_declstmt() {
+ int *ptr = getIntPtr();
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 1 (ptr, [1, 3])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (ptr, [1, 3])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (ptr, [1, 3])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (ptr, [1, 3])
+
+void multiple_vardecl_in_declstmt() {
+ int *ptr = getIntPtr(), i;
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 1 (ptr, [1, 3])
+// CHECK-NEXT: 1 (i, [1, 4])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (ptr, [1, 3])
+// CHECK-NEXT: 0 IN (i, [1, 4])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (ptr, [1, 3])
+// CHECK-NEXT: 0 OUT (i, [1, 4])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (ptr, [1, 3])
+// CHECK-NEXT: 1 OUT (i, [1, 4])
+
+void function_and_vardecl_in_declstmt() {
+ int *ptr = getIntPtr(), a();
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 1 (ptr, [1, 3])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (ptr, [1, 3])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (ptr, [1, 3])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (ptr, [1, 3])
+
+void single_def_in_same_block() {
+ int *ptr = getIntPtr();
+
+ if (coin())
+ ptr = 0;
+
+ if (!ptr)
+ *ptr = 5;
+}
+// -> [B3] -> -> [B1] ->
+// / \ / \
+// [B5 (ENTRY)] -> [B4] ------> [B2] ---> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 3 (ptr, [3, 3])
+// CHECK-NEXT: 4 (global_var, [4, 6])
+// CHECK-NEXT: 4 (ptr, [4, 3])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 3 (ptr, [4, 3])
+// CHECK-NEXT: 4 (ptr, [3, 3])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [4, 6])
+// CHECK-NEXT: 0 IN (ptr, [3, 3])
+// CHECK-NEXT: 0 OUT (global_var, [4, 6])
+// CHECK-NEXT: 0 OUT (ptr, [3, 3])
+// CHECK-NEXT: 1 IN (global_var, [4, 6])
+// CHECK-NEXT: 1 IN (ptr, [3, 3])
+// CHECK-NEXT: 1 OUT (global_var, [4, 6])
+// CHECK-NEXT: 1 OUT (ptr, [3, 3])
+// CHECK-NEXT: 2 IN (global_var, [4, 6])
+// CHECK-NEXT: 2 IN (ptr, [3, 3])
+// CHECK-NEXT: 2 OUT (global_var, [4, 6])
+// CHECK-NEXT: 2 OUT (ptr, [3, 3])
+// CHECK-NEXT: 3 IN (global_var, [4, 6])
+// CHECK-NEXT: 3 IN (ptr, [4, 3])
+// CHECK-NEXT: 3 OUT (global_var, [4, 6])
+// CHECK-NEXT: 3 OUT (ptr, [3, 3])
+// CHECK-NEXT: 4 OUT (global_var, [4, 6])
+// CHECK-NEXT: 4 OUT (ptr, [4, 3])
+
+void different_assignments() {
+ int i = getInt();
+
+ if (coin())
+ i = 0;
+
+ i += 3;
+
+ if (!coin())
+ i -= 2;
+
+ i *= 9;
+
+ if (i = 0)
+ ;
+}
+// -> [B5] -> -> [B3] -> -> [B1] ->
+// / \ / \ / \
+// [B7 (ENTRY)] -> [B6] ------> [B4] -------> [B2] ---> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (i, [2, 5])
+// CHECK-NEXT: 3 (i, [3, 2])
+// CHECK-NEXT: 4 (global_var, [4, 5])
+// CHECK-NEXT: 4 (i, [4, 2])
+// CHECK-NEXT: 5 (i, [5, 2])
+// CHECK-NEXT: 6 (global_var, [6, 6])
+// CHECK-NEXT: 6 (i, [6, 3])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (i, [3, 2])
+// CHECK-NEXT: 2 (i, [4, 2])
+// CHECK-NEXT: 2 (i, [5, 2])
+// CHECK-NEXT: 2 (i, [6, 3])
+// CHECK-NEXT: 3 (i, [2, 5])
+// CHECK-NEXT: 3 (i, [4, 2])
+// CHECK-NEXT: 3 (i, [5, 2])
+// CHECK-NEXT: 3 (i, [6, 3])
+// CHECK-NEXT: 4 (global_var, [6, 6])
+// CHECK-NEXT: 4 (i, [2, 5])
+// CHECK-NEXT: 4 (i, [3, 2])
+// CHECK-NEXT: 4 (i, [5, 2])
+// CHECK-NEXT: 4 (i, [6, 3])
+// CHECK-NEXT: 5 (i, [2, 5])
+// CHECK-NEXT: 5 (i, [3, 2])
+// CHECK-NEXT: 5 (i, [4, 2])
+// CHECK-NEXT: 5 (i, [6, 3])
+// CHECK-NEXT: 6 (global_var, [4, 5])
+// CHECK-NEXT: 6 (i, [2, 5])
+// CHECK-NEXT: 6 (i, [3, 2])
+// CHECK-NEXT: 6 (i, [4, 2])
+// CHECK-NEXT: 6 (i, [5, 2])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [4, 5])
+// CHECK-NEXT: 0 IN (i, [2, 5])
+// CHECK-NEXT: 0 OUT (global_var, [4, 5])
+// CHECK-NEXT: 0 OUT (i, [2, 5])
+// CHECK-NEXT: 1 IN (global_var, [4, 5])
+// CHECK-NEXT: 1 IN (i, [2, 5])
+// CHECK-NEXT: 1 OUT (global_var, [4, 5])
+// CHECK-NEXT: 1 OUT (i, [2, 5])
+// CHECK-NEXT: 2 IN (global_var, [4, 5])
+// CHECK-NEXT: 2 IN (i, [3, 2])
+// CHECK-NEXT: 2 OUT (global_var, [4, 5])
+// CHECK-NEXT: 2 OUT (i, [2, 5])
+// CHECK-NEXT: 3 IN (global_var, [4, 5])
+// CHECK-NEXT: 3 IN (i, [4, 2])
+// CHECK-NEXT: 3 OUT (global_var, [4, 5])
+// CHECK-NEXT: 3 OUT (i, [3, 2])
+// CHECK-NEXT: 4 IN (global_var, [6, 6])
+// CHECK-NEXT: 4 IN (i, [5, 2])
+// CHECK-NEXT: 4 OUT (global_var, [4, 5])
+// CHECK-NEXT: 4 OUT (i, [4, 2])
+// CHECK-NEXT: 5 IN (global_var, [6, 6])
+// CHECK-NEXT: 5 IN (i, [6, 3])
+// CHECK-NEXT: 5 OUT (global_var, [6, 6])
+// CHECK-NEXT: 5 OUT (i, [5, 2])
+// CHECK-NEXT: 6 OUT (global_var, [6, 6])
+// CHECK-NEXT: 6 OUT (i, [6, 3])
+
+namespace example_1 {
+
+int flag;
+
+void foo() {
+ flag = coin();
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 1 (flag, [1, 5])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (flag, [1, 5])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (flag, [1, 5])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (flag, [1, 5])
+
+void f() {
+ int *x = nullptr;
+ flag = 1;
+
+ foo();
+ if (flag)
+ x = new int;
+
+ foo();
+ if (flag)
+ *x = 5;
+}
+// -> [B3] -> -> [B1] ->
+// / \ / \
+// [B5 (ENTRY)] -> [B4] ------> [B2] ---> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (global_var, [2, 2])
+// CHECK-NEXT: 2 (flag, [2, 2])
+// CHECK-NEXT: 3 (x, [3, 3])
+// CHECK-NEXT: 4 (global_var, [4, 8])
+// CHECK-NEXT: 4 (flag, [4, 8])
+// CHECK-NEXT: 4 (x, [4, 2])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (global_var, [4, 8])
+// CHECK-NEXT: 2 (flag, [4, 8])
+// CHECK-NEXT: 3 (x, [4, 2])
+// CHECK-NEXT: 4 (global_var, [2, 2])
+// CHECK-NEXT: 4 (flag, [2, 2])
+// CHECK-NEXT: 4 (x, [3, 3])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [2, 2])
+// CHECK-NEXT: 0 IN (flag, [2, 2])
+// CHECK-NEXT: 0 IN (x, [3, 3])
+// CHECK-NEXT: 0 OUT (global_var, [2, 2])
+// CHECK-NEXT: 0 OUT (flag, [2, 2])
+// CHECK-NEXT: 0 OUT (x, [3, 3])
+// CHECK-NEXT: 1 IN (global_var, [2, 2])
+// CHECK-NEXT: 1 IN (flag, [2, 2])
+// CHECK-NEXT: 1 IN (x, [3, 3])
+// CHECK-NEXT: 1 OUT (global_var, [2, 2])
+// CHECK-NEXT: 1 OUT (flag, [2, 2])
+// CHECK-NEXT: 1 OUT (x, [3, 3])
+// CHECK-NEXT: 2 IN (global_var, [4, 8])
+// CHECK-NEXT: 2 IN (flag, [4, 8])
+// CHECK-NEXT: 2 IN (x, [3, 3])
+// CHECK-NEXT: 2 OUT (global_var, [2, 2])
+// CHECK-NEXT: 2 OUT (flag, [2, 2])
+// CHECK-NEXT: 2 OUT (x, [3, 3])
+// CHECK-NEXT: 3 IN (global_var, [4, 8])
+// CHECK-NEXT: 3 IN (flag, [4, 8])
+// CHECK-NEXT: 3 IN (x, [4, 2])
+// CHECK-NEXT: 3 OUT (global_var, [4, 8])
+// CHECK-NEXT: 3 OUT (flag, [4, 8])
+// CHECK-NEXT: 3 OUT (x, [3, 3])
+// CHECK-NEXT: 4 OUT (global_var, [4, 8])
+// CHECK-NEXT: 4 OUT (flag, [4, 8])
+// CHECK-NEXT: 4 OUT (x, [4, 2])
+
+} // end of namespace example_1
+
+void assignment_buried_beneath_parentheses() {
+ int *ptr = getIntPtr();
+ if (coin())
+ (((((((((((((((ptr))))))) = getIntPtr()))))))));
+}
+// -> [B1] ->
+// / \
+// [B3 (ENTRY)] -> [B2] ---> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 2 (global_var, [2, 6])
+// CHECK-NEXT: 2 (ptr, [2, 3])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [2, 6])
+// CHECK-NEXT: 2 (global_var, [1, 2])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (ptr, [2, 3])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (ptr, [2, 3])
+// CHECK-NEXT: 1 IN (global_var, [2, 6])
+// CHECK-NEXT: 1 IN (ptr, [2, 3])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (ptr, [2, 3])
+// CHECK-NEXT: 2 OUT (global_var, [2, 6])
+// CHECK-NEXT: 2 OUT (ptr, [2, 3])
+
+void single_parameter(int i) {
+ int *ptr = getIntPtr();
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 1 (ptr, [1, 3])
+// CHECK-NEXT: 2 (i, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (i, [2, 0])
+// CHECK-NEXT: 0 IN (ptr, [1, 3])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (i, [2, 0])
+// CHECK-NEXT: 0 OUT (ptr, [1, 3])
+// CHECK-NEXT: 1 IN (i, [2, 0])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (i, [2, 0])
+// CHECK-NEXT: 1 OUT (ptr, [1, 3])
+// CHECK-NEXT: 2 OUT (i, [2, 0])
+
+void multiple_parameters(int i, int j, int k) {
+ int *ptr = getIntPtr();
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 2])
+// CHECK-NEXT: 1 (ptr, [1, 3])
+// CHECK-NEXT: 2 (i, [2, 0])
+// CHECK-NEXT: 2 (j, [2, 0])
+// CHECK-NEXT: 2 (k, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2])
+// CHECK-NEXT: 0 IN (i, [2, 0])
+// CHECK-NEXT: 0 IN (j, [2, 0])
+// CHECK-NEXT: 0 IN (k, [2, 0])
+// CHECK-NEXT: 0 IN (ptr, [1, 3])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (i, [2, 0])
+// CHECK-NEXT: 0 OUT (j, [2, 0])
+// CHECK-NEXT: 0 OUT (k, [2, 0])
+// CHECK-NEXT: 0 OUT (ptr, [1, 3])
+// CHECK-NEXT: 1 IN (i, [2, 0])
+// CHECK-NEXT: 1 IN (j, [2, 0])
+// CHECK-NEXT: 1 IN (k, [2, 0])
+// CHECK-NEXT: 1 OUT (global_var, [1, 2])
+// CHECK-NEXT: 1 OUT (i, [2, 0])
+// CHECK-NEXT: 1 OUT (j, [2, 0])
+// CHECK-NEXT: 1 OUT (k, [2, 0])
+// CHECK-NEXT: 1 OUT (ptr, [1, 3])
+// CHECK-NEXT: 2 OUT (i, [2, 0])
+// CHECK-NEXT: 2 OUT (j, [2, 0])
+// CHECK-NEXT: 2 OUT (k, [2, 0])
+
+void assignment_and_declaration_on_same_line(int i, int j) {
+ int k = i = j = 0;
+}
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (i, [1, 7])
+// CHECK-NEXT: 1 (j, [1, 7])
+// CHECK-NEXT: 1 (k, [1, 7])
+// CHECK-NEXT: 2 (i, [2, 0])
+// CHECK-NEXT: 2 (j, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (i, [2, 0])
+// CHECK-NEXT: 1 (j, [2, 0])
+// CHECK-NEXT: 2 (i, [1, 7])
+// CHECK-NEXT: 2 (j, [1, 7])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (i, [1, 7])
+// CHECK-NEXT: 0 IN (j, [1, 7])
+// CHECK-NEXT: 0 IN (k, [1, 7])
+// CHECK-NEXT: 0 OUT (i, [1, 7])
+// CHECK-NEXT: 0 OUT (j, [1, 7])
+// CHECK-NEXT: 0 OUT (k, [1, 7])
+// CHECK-NEXT: 1 IN (i, [2, 0])
+// CHECK-NEXT: 1 IN (j, [2, 0])
+// CHECK-NEXT: 1 OUT (i, [1, 7])
+// CHECK-NEXT: 1 OUT (j, [1, 7])
+// CHECK-NEXT: 1 OUT (k, [1, 7])
+// CHECK-NEXT: 2 OUT (i, [2, 0])
+// CHECK-NEXT: 2 OUT (j, [2, 0])
Index: clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
+++ clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
@@ -12,6 +12,7 @@
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/Analysis/Analyses/Dominators.h"
+#include "clang/Analysis/Analyses/ReachingDefinitions.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/Analysis/CallGraph.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
@@ -103,6 +104,82 @@
}
//===----------------------------------------------------------------------===//
+// GenSetDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class GenSetDumper : public Checker<check::ASTCodeBody> {
+public:
+ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
+ BugReporter &BR) const {
+ if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
+ ReachingDefinitionsCalculator R(D, AC->getCFG(), &AC->getASTContext());
+ R.dumpGenSet();
+ }
+ }
+};
+}
+
+void ento::registerGenSetDumper(CheckerManager &mgr) {
+ mgr.registerChecker<GenSetDumper>();
+}
+
+bool ento::shouldRegisterGenSetDumper(const LangOptions &LO) {
+ return true;
+}
+
+//===----------------------------------------------------------------------===//
+// KillSetDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class KillSetDumper : public Checker<check::ASTCodeBody> {
+public:
+ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
+ BugReporter &BR) const {
+ if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
+ ReachingDefinitionsCalculator R(D, AC->getCFG(), &AC->getASTContext());
+ R.dumpKillSet();
+ }
+ }
+};
+}
+
+void ento::registerKillSetDumper(CheckerManager &mgr) {
+ mgr.registerChecker<KillSetDumper>();
+}
+
+bool ento::shouldRegisterKillSetDumper(const LangOptions &LO) {
+ return true;
+}
+
+//===----------------------------------------------------------------------===//
+// ReachingDefinitionsDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class ReachingDefinitionsDumper : public Checker<check::ASTCodeBody> {
+public:
+ void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
+ BugReporter &BR) const {
+ if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
+ ReachingDefinitionsCalculator R(D, AC->getCFG(), &AC->getASTContext());
+ R.calculate();
+ R.dumpReachingDefinitions();
+ }
+ }
+};
+}
+
+void ento::registerReachingDefinitionsDumper(CheckerManager &mgr) {
+ mgr.registerChecker<ReachingDefinitionsDumper>();
+}
+
+bool ento::shouldRegisterReachingDefinitionsDumper(const LangOptions &LO) {
+ return true;
+}
+
+//===----------------------------------------------------------------------===//
// LiveVariablesDumper
//===----------------------------------------------------------------------===//
Index: clang/lib/Analysis/ReachingDefinitions.cpp
===================================================================
--- /dev/null
+++ clang/lib/Analysis/ReachingDefinitions.cpp
@@ -0,0 +1,213 @@
+//===--- ReachableDefinitions.cpp -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Calculates reachable definitions for a variable.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Analyses/ReachingDefinitions.h"
+#include "clang/AST/DeclLookups.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/ADT/SetOperations.h"
+
+using namespace clang;
+using namespace ReachingDefinitionsDetail;
+
+void ReachingDefinitionsCalculator::anchor() {}
+
+using VarSet = llvm::SmallPtrSet<const VarDecl *, 5>;
+
+LLVM_NODISCARD
+static VarSet getAllGlobalVariable(const Decl *D) {
+ VarSet Ret;
+ const DeclContext *DC = D->getDeclContext();
+ while (DC) {
+ DC = DC->getPrimaryContext();
+ for (const Decl *Res : DC->decls())
+ if (const VarDecl *VD = dyn_cast<VarDecl>(Res))
+ Ret.insert(VD);
+ DC = DC->getParent();
+ }
+ return Ret;
+}
+
+LLVM_NODISCARD
+static DefinitionSet
+getGenSetForCFGBlock(const Decl *D, const CFGBlock *B, ASTContext *Context) {
+ if (B->size() == 0) {
+ return {};
+ }
+
+ using namespace ast_matchers;
+ using DefinitionKind = Definition::DefinitionKind;
+
+ DefinitionSet Ret;
+ const VarSet GlobalVars = getAllGlobalVariable(D);
+ VarSet Vars;
+
+ for (size_t I = B->size() - 1; I > 0; --I) {
+ CFGElementRef E = B->getCFGElementRef(I);
+ if ((*E).getKind() != CFGElement::Kind::Statement)
+ continue;
+
+ const Stmt *S = (*E).castAs<CFGStmt>().getStmt();
+ assert(S);
+
+ auto AssignmentM =
+ binaryOperator(isAssignmentOperator(),
+ hasLHS(declRefExpr(to(varDecl().bind("var")))))
+ .bind("assign");
+
+ auto Assignments =
+ match(stmt(forEachDescendant(AssignmentM)), *S, *Context);
+ if (!Assignments.empty()) {
+ for (const auto Assignment : Assignments) {
+ const auto *Var = Assignment.getNodeAs<VarDecl>("var");
+ assert(Var);
+
+ if (Vars.insert(Var).second)
+ Ret.insert({Var, E, DefinitionKind::Write});
+ }
+ }
+
+ auto Declarations = match(declStmt().bind("decls"), *S, *Context);
+ if (!Declarations.empty()) {
+ assert(Declarations.size() == 1);
+ const auto *DS = Declarations[0].getNodeAs<DeclStmt>("decls");
+ assert(DS);
+
+ for (const Decl *D : DS->decls()) {
+ const auto *Var = dyn_cast<VarDecl>(D);
+ if (!Var)
+ continue;
+
+ if (Vars.insert(Var).second)
+ Ret.insert({Var, E, DefinitionKind::Write});
+ }
+ }
+
+ auto Calls = match(callExpr().bind("calls"), *S, *Context);
+ if (!Calls.empty()) {
+ assert(Calls.size() == 1);
+ const auto *Call = Calls[0].getNodeAs<CallExpr>("calls");
+ assert(Call);
+
+ for (const VarDecl *GlobalVD : GlobalVars)
+ if (Vars.insert(GlobalVD).second)
+ Ret.insert({GlobalVD, E, DefinitionKind::Invalidation});
+ }
+ }
+
+ return Ret;
+}
+
+bool killsVar(const VarDecl *VD, const DefinitionSet &Set) {
+ for (const Definition &Def : Set)
+ if (VD == Def.Var)
+ return true;
+ return false;
+}
+
+void ReachingDefinitionsCalculator::init() {
+ llvm::SmallVector<Definition, 16> AllDefinitions;
+
+ for (const CFGBlock *B : *cfg) {
+ for (const Definition &Def : getGenSetForCFGBlock(D, B, Context)) {
+ AllDefinitions.push_back(Def);
+ Gen[B].insert(Def);
+ }
+ }
+
+ if (const auto *F = dyn_cast<FunctionDecl>(D)) {
+ for (const ParmVarDecl *Param : F->parameters()) {
+ Definition ParamDef(Param, {&cfg->getEntry(), 0},
+ Definition::DefinitionKind::Write);
+ AllDefinitions.push_back(ParamDef);
+ Gen[&cfg->getEntry()].insert(ParamDef);
+ }
+ }
+
+ for (const std::pair<const CFGBlock *, DefinitionSet> &G : Gen)
+ for (const Definition &Def : AllDefinitions)
+ if (G.first != Def.getCFGBlock() && killsVar(Def.Var, G.second))
+ Kill[G.first].insert(Def);
+}
+
+using WorklistTy = llvm::SmallVector<const CFGBlock *, 5>;
+
+void ReachingDefinitionsCalculator::calculate() {
+ Out = Gen;
+
+ WorklistTy Worklist({cfg->begin(), cfg->end()});
+
+ while (!Worklist.empty()) {
+ const CFGBlock *N = Worklist.pop_back_val();
+
+ for (auto Pred = N->pred_begin(); Pred != N->pred_end(); ++Pred)
+ llvm::set_union(In[N], Out[*Pred]);
+
+ bool HasChanged =
+ llvm::set_union(Out[N], llvm::set_difference(In[N], Kill[N]));
+
+ if (llvm::set_union(Out[N], Gen[N]))
+ HasChanged = true;
+
+ if (HasChanged) {
+ for (auto Succ = N->succ_begin(); Succ != N->succ_begin(); ++Succ)
+ Worklist.push_back(*Succ);
+ }
+ }
+}
+
+void ReachingDefinitionsCalculator::dumpGenSet() const {
+ llvm::errs() << "GEN sets: blockid (varname [blockid, elementid])\n";
+ for (const std::pair<const CFGBlock *, DefinitionSet> &D : Gen) {
+ size_t BlockID = llvm::find(*cfg, D.first) - cfg->begin();
+ for (const Definition &Def : D.second) {
+ llvm::errs() << BlockID << ' ';
+ Def.dump();
+ llvm::errs() << '\n';
+ }
+ }
+}
+
+void ReachingDefinitionsCalculator::dumpKillSet() const {
+ llvm::errs() << "KILL sets: blockid (varname [blockid, elementid])\n";
+ for (const std::pair<const CFGBlock *, DefinitionKillSet> &D : Kill) {
+ size_t BlockID = llvm::find(*cfg, D.first) - cfg->begin();
+ for (const Definition &Def : D.second) {
+ llvm::errs() << BlockID << ' ';
+ Def.dump();
+ llvm::errs() << '\n';
+ }
+ }
+}
+
+void ReachingDefinitionsCalculator::dumpReachingDefinitions() const {
+ llvm::errs() << "Reaching definition sets: "
+ "blockid IN/OUT (varname [blockid, elementid])\n";
+ for (const CFGBlock *B : *cfg) {
+ size_t BlockID = llvm::find(*cfg, B) - cfg->begin();
+ if (In.count(B)) {
+ for (const Definition &Def : In.find(B)->second) {
+ llvm::errs() << BlockID << " IN ";
+ Def.dump();
+ llvm::errs() << '\n';
+ }
+ }
+
+ if (Out.count(B)) {
+ for (const Definition &Def : Out.find(B)->second) {
+ llvm::errs() << BlockID << " OUT ";
+ Def.dump();
+ llvm::errs() << '\n';
+ }
+ }
+ }
+}
Index: clang/lib/Analysis/CMakeLists.txt
===================================================================
--- clang/lib/Analysis/CMakeLists.txt
+++ clang/lib/Analysis/CMakeLists.txt
@@ -21,6 +21,7 @@
PostOrderCFGView.cpp
ProgramPoint.cpp
ReachableCode.cpp
+ ReachingDefinitions.cpp
RetainSummaryManager.cpp
ThreadSafety.cpp
ThreadSafetyCommon.cpp
Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -1297,8 +1297,19 @@
HelpText<"Emits a warning for every statement.">,
Documentation<NotDocumented>;
-} // end "debug"
+def GenSetDumper : Checker<"DumpGenSets">,
+ HelpText<"Dump the GEN sets for each block in a function">,
+ Documentation<NotDocumented>;
+
+def KillSetDumper : Checker<"DumpKillSets">,
+ HelpText<"Dump the KILL sets for each block in a function">,
+ Documentation<NotDocumented>;
+def ReachingDefinitionsDumper : Checker<"DumpReachingDefinitions">,
+ HelpText<"Dump the reaching definitions for each block in a function">,
+ Documentation<NotDocumented>;
+
+} // end "debug"
//===----------------------------------------------------------------------===//
// Clone Detection
Index: clang/include/clang/Analysis/Analyses/ReachingDefinitions.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/Analyses/ReachingDefinitions.h
@@ -0,0 +1,100 @@
+//===--- ReachingDefinitions.h ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Calculates reaching definitions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H
+
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include <set>
+#include <map>
+
+namespace clang {
+
+namespace ReachingDefinitionsDetail {
+
+struct Definition {
+ enum DefinitionKind {
+ Write,
+ Invalidation
+ };
+ const VarDecl *Var;
+ CFGElementRef E;
+ DefinitionKind Kind;
+
+ const CFGBlock *getCFGBlock() const { return E.getCFGBlock(); }
+
+ // (varname [blockid, elementid])
+ void dump() const {
+ llvm::errs() << "(" << Var->getNameAsString() << ", ["
+ << getCFGBlock()->getIndexInCFG() << ", " << E.getIndex()
+ << "])";
+ }
+
+ Definition(const VarDecl *Var, CFGElementRef E, DefinitionKind Kind)
+ : Var(Var), E(E), Kind(Kind) {}
+};
+
+struct VarLess {
+ bool operator()(Definition Lhs, Definition Rhs) {
+ return Lhs.Var < Rhs.Var;
+ }
+};
+
+struct VarAndCFGElementLess {
+ bool operator()(Definition Lhs, Definition Rhs) const {
+ if (Lhs.Var == Rhs.Var)
+ return Lhs.E < Rhs.E;
+ return Lhs.Var < Rhs.Var;
+ }
+};
+
+using DefinitionSet = std::set<Definition, VarLess>;
+using DefinitionKillSet = std::set<Definition, VarAndCFGElementLess>;
+
+} // end of namespace ReachingDefinitionsDetail
+
+class ReachingDefinitionsCalculator : public ManagedAnalysis {
+ virtual void anchor();
+
+public:
+ using DefinitionSet = ReachingDefinitionsDetail::DefinitionSet;
+ using DefinitionKillSet = ReachingDefinitionsDetail::DefinitionKillSet;
+
+ ReachingDefinitionsCalculator(const Decl *D, const CFG *cfg,
+ ASTContext *Context)
+ : cfg(cfg), Context(Context), D(D) {
+ init();
+ }
+
+ void init();
+ void calculate();
+
+ void dumpKillSet() const;
+ void dumpGenSet() const;
+ void dumpReachingDefinitions() const;
+
+private:
+ const CFG *cfg;
+ ASTContext *Context;
+ const Decl *D;
+
+ std::map<const CFGBlock *, DefinitionSet> Gen;
+ std::map<const CFGBlock *, DefinitionKillSet> Kill;
+
+ std::map<const CFGBlock *, DefinitionSet> In;
+ std::map<const CFGBlock *, DefinitionSet> Out;
+};
+
+} // end of namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
