Szelethus updated this revision to Diff 222514.
Szelethus added a comment.
I'm starting to be really happy with the current direction! I think I'll start
splitting this up soon, I'm confident that the current interface (after some
polishing) is general enough to develop incrementally.
- Introduce `Variable`, a base class of `Definition`, which is a (`VarDecl`,
`FieldChain`) pair.
- Introduce `GenSetBuilder`, a class that owns all `MatchFinder`s and
associated callbacks used for finding potential writes and invalidations to
`Variable`s, use exclusively it to build GEN sets.
- Use a very flexible interface for creating and registering matchers for
either
- Creating the set of `Variable`s accessible to a function
- Finding statements that may write any of those
- Teasing an `Expr` apart to find `Variable`s in it
- In an `init()` pass, collect all variables used, or potentially invalidated
in the function. This allows for invalidations and writes to be done in a
single pass on a `CFGStmt`.
- Added a very primitive solution to invalidate variables passed to functions
as a non-const reference.
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,823 @@
+// 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]) <invalidation>
+// CHECK-NEXT: 1 (ptr, [1, 3]) <write>
+// 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]) <invalidation>
+// CHECK-NEXT: 0 IN (ptr, [1, 3]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (ptr, [1, 3]) <write>
+
+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]) <invalidation>
+// CHECK-NEXT: 1 (ptr, [1, 3]) <write>
+// CHECK-NEXT: 1 (i, [1, 4]) <write>
+// 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]) <invalidation>
+// CHECK-NEXT: 0 IN (ptr, [1, 3]) <write>
+// CHECK-NEXT: 0 IN (i, [1, 4]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 0 OUT (i, [1, 4]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 1 OUT (i, [1, 4]) <write>
+
+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]) <invalidation>
+// CHECK-NEXT: 1 (ptr, [1, 3]) <write>
+// 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]) <invalidation>
+// CHECK-NEXT: 0 IN (ptr, [1, 3]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (ptr, [1, 3]) <write>
+
+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]) <write>
+// CHECK-NEXT: 4 (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 4 (ptr, [4, 3]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 3 (ptr, [4, 3]) <write>
+// CHECK-NEXT: 4 (ptr, [3, 3]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 0 IN (ptr, [3, 3]) <write>
+// CHECK-NEXT: 0 IN (ptr, [4, 3]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 0 OUT (ptr, [3, 3]) <write>
+// CHECK-NEXT: 0 OUT (ptr, [4, 3]) <write>
+// CHECK-NEXT: 1 IN (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 1 IN (ptr, [3, 3]) <write>
+// CHECK-NEXT: 1 IN (ptr, [4, 3]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 1 OUT (ptr, [3, 3]) <write>
+// CHECK-NEXT: 1 OUT (ptr, [4, 3]) <write>
+// CHECK-NEXT: 2 IN (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 2 IN (ptr, [3, 3]) <write>
+// CHECK-NEXT: 2 IN (ptr, [4, 3]) <write>
+// CHECK-NEXT: 2 OUT (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 2 OUT (ptr, [3, 3]) <write>
+// CHECK-NEXT: 2 OUT (ptr, [4, 3]) <write>
+// CHECK-NEXT: 3 IN (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 3 IN (ptr, [4, 3]) <write>
+// CHECK-NEXT: 3 OUT (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 3 OUT (ptr, [3, 3]) <write>
+// CHECK-NEXT: 4 OUT (global_var, [4, 6]) <invalidation>
+// CHECK-NEXT: 4 OUT (ptr, [4, 3]) <write>
+
+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]) <write>
+// CHECK-NEXT: 3 (i, [3, 2]) <write>
+// CHECK-NEXT: 4 (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 4 (i, [4, 2]) <write>
+// CHECK-NEXT: 5 (i, [5, 2]) <write>
+// CHECK-NEXT: 6 (global_var, [6, 6]) <invalidation>
+// CHECK-NEXT: 6 (i, [6, 3]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (i, [3, 2]) <write>
+// CHECK-NEXT: 2 (i, [4, 2]) <write>
+// CHECK-NEXT: 2 (i, [5, 2]) <write>
+// CHECK-NEXT: 2 (i, [6, 3]) <write>
+// CHECK-NEXT: 3 (i, [2, 5]) <write>
+// CHECK-NEXT: 3 (i, [4, 2]) <write>
+// CHECK-NEXT: 3 (i, [5, 2]) <write>
+// CHECK-NEXT: 3 (i, [6, 3]) <write>
+// CHECK-NEXT: 4 (global_var, [6, 6]) <invalidation>
+// CHECK-NEXT: 4 (i, [2, 5]) <write>
+// CHECK-NEXT: 4 (i, [3, 2]) <write>
+// CHECK-NEXT: 4 (i, [5, 2]) <write>
+// CHECK-NEXT: 4 (i, [6, 3]) <write>
+// CHECK-NEXT: 5 (i, [2, 5]) <write>
+// CHECK-NEXT: 5 (i, [3, 2]) <write>
+// CHECK-NEXT: 5 (i, [4, 2]) <write>
+// CHECK-NEXT: 5 (i, [6, 3]) <write>
+// CHECK-NEXT: 6 (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 6 (i, [2, 5]) <write>
+// CHECK-NEXT: 6 (i, [3, 2]) <write>
+// CHECK-NEXT: 6 (i, [4, 2]) <write>
+// CHECK-NEXT: 6 (i, [5, 2]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 0 IN (i, [2, 5]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 0 OUT (i, [2, 5]) <write>
+// CHECK-NEXT: 1 IN (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 1 IN (i, [2, 5]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 1 OUT (i, [2, 5]) <write>
+// CHECK-NEXT: 2 IN (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 2 IN (i, [3, 2]) <write>
+// CHECK-NEXT: 2 IN (i, [4, 2]) <write>
+// CHECK-NEXT: 2 OUT (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 2 OUT (i, [2, 5]) <write>
+// CHECK-NEXT: 3 IN (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 3 IN (i, [4, 2]) <write>
+// CHECK-NEXT: 3 OUT (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 3 OUT (i, [3, 2]) <write>
+// CHECK-NEXT: 4 IN (global_var, [6, 6]) <invalidation>
+// CHECK-NEXT: 4 IN (i, [5, 2]) <write>
+// CHECK-NEXT: 4 IN (i, [6, 3]) <write>
+// CHECK-NEXT: 4 OUT (global_var, [4, 5]) <invalidation>
+// CHECK-NEXT: 4 OUT (i, [4, 2]) <write>
+// CHECK-NEXT: 5 IN (global_var, [6, 6]) <invalidation>
+// CHECK-NEXT: 5 IN (i, [6, 3]) <write>
+// CHECK-NEXT: 5 OUT (global_var, [6, 6]) <invalidation>
+// CHECK-NEXT: 5 OUT (i, [5, 2]) <write>
+// CHECK-NEXT: 6 OUT (global_var, [6, 6]) <invalidation>
+// CHECK-NEXT: 6 OUT (i, [6, 3]) <write>
+
+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]) <invalidation>
+// CHECK-NEXT: 1 (flag, [1, 5]) <write>
+// 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]) <invalidation>
+// CHECK-NEXT: 0 IN (flag, [1, 5]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (flag, [1, 5]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (flag, [1, 5]) <write>
+
+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]) <invalidation>
+// CHECK-NEXT: 2 (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 3 (x, [3, 3]) <write>
+// CHECK-NEXT: 4 (global_var, [4, 8]) <invalidation>
+// CHECK-NEXT: 4 (flag, [4, 8]) <invalidation>
+// CHECK-NEXT: 4 (x, [4, 2]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (global_var, [4, 8]) <invalidation>
+// CHECK-NEXT: 2 (flag, [4, 8]) <invalidation>
+// CHECK-NEXT: 3 (x, [4, 2]) <write>
+// CHECK-NEXT: 4 (global_var, [2, 2]) <invalidation>
+// CHECK-NEXT: 4 (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 4 (x, [3, 3]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [2, 2]) <invalidation>
+// CHECK-NEXT: 0 IN (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 0 IN (x, [3, 3]) <write>
+// CHECK-NEXT: 0 IN (x, [4, 2]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [2, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (x, [3, 3]) <write>
+// CHECK-NEXT: 0 OUT (x, [4, 2]) <write>
+// CHECK-NEXT: 1 IN (global_var, [2, 2]) <invalidation>
+// CHECK-NEXT: 1 IN (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 1 IN (x, [3, 3]) <write>
+// CHECK-NEXT: 1 IN (x, [4, 2]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [2, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (x, [3, 3]) <write>
+// CHECK-NEXT: 1 OUT (x, [4, 2]) <write>
+// CHECK-NEXT: 2 IN (global_var, [4, 8]) <invalidation>
+// CHECK-NEXT: 2 IN (flag, [4, 8]) <invalidation>
+// CHECK-NEXT: 2 IN (x, [3, 3]) <write>
+// CHECK-NEXT: 2 IN (x, [4, 2]) <write>
+// CHECK-NEXT: 2 OUT (global_var, [2, 2]) <invalidation>
+// CHECK-NEXT: 2 OUT (flag, [2, 2]) <invalidation>
+// CHECK-NEXT: 2 OUT (x, [3, 3]) <write>
+// CHECK-NEXT: 2 OUT (x, [4, 2]) <write>
+// CHECK-NEXT: 3 IN (global_var, [4, 8]) <invalidation>
+// CHECK-NEXT: 3 IN (flag, [4, 8]) <invalidation>
+// CHECK-NEXT: 3 IN (x, [4, 2]) <write>
+// CHECK-NEXT: 3 OUT (global_var, [4, 8]) <invalidation>
+// CHECK-NEXT: 3 OUT (flag, [4, 8]) <invalidation>
+// CHECK-NEXT: 3 OUT (x, [3, 3]) <write>
+// CHECK-NEXT: 4 OUT (global_var, [4, 8]) <invalidation>
+// CHECK-NEXT: 4 OUT (flag, [4, 8]) <invalidation>
+// CHECK-NEXT: 4 OUT (x, [4, 2]) <write>
+
+} // 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]) <invalidation>
+// CHECK-NEXT: 2 (global_var, [2, 6]) <invalidation>
+// CHECK-NEXT: 2 (ptr, [2, 3]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [2, 6]) <invalidation>
+// CHECK-NEXT: 2 (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 IN (global_var, [2, 6]) <invalidation>
+// CHECK-NEXT: 0 IN (ptr, [2, 3]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (global_var, [2, 6]) <invalidation>
+// CHECK-NEXT: 0 OUT (ptr, [2, 3]) <write>
+// CHECK-NEXT: 1 IN (global_var, [2, 6]) <invalidation>
+// CHECK-NEXT: 1 IN (ptr, [2, 3]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (ptr, [2, 3]) <write>
+// CHECK-NEXT: 2 OUT (global_var, [2, 6]) <invalidation>
+// CHECK-NEXT: 2 OUT (ptr, [2, 3]) <write>
+
+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]) <invalidation>
+// CHECK-NEXT: 1 (ptr, [1, 3]) <write>
+// CHECK-NEXT: 2 (i, [2, 0]) <write>
+// 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]) <invalidation>
+// CHECK-NEXT: 0 IN (i, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (ptr, [1, 3]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (i, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 1 IN (i, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (i, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 2 OUT (i, [2, 0]) <write>
+
+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]) <invalidation>
+// CHECK-NEXT: 1 (ptr, [1, 3]) <write>
+// CHECK-NEXT: 2 (i, [2, 0]) <write>
+// CHECK-NEXT: 2 (j, [2, 0]) <write>
+// CHECK-NEXT: 2 (k, [2, 0]) <write>
+// 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]) <invalidation>
+// CHECK-NEXT: 0 IN (i, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (j, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (k, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (ptr, [1, 3]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 0 OUT (i, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (j, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (k, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 1 IN (i, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (j, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (k, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 2]) <invalidation>
+// CHECK-NEXT: 1 OUT (i, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (j, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (k, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (ptr, [1, 3]) <write>
+// CHECK-NEXT: 2 OUT (i, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (j, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (k, [2, 0]) <write>
+
+void assignment_and_declaration_on_same_line(int i, int j) {
+ int k = i = j = 0;
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (i, [1, 5]) <write>
+// CHECK-NEXT: 1 (j, [1, 2]) <write>
+// CHECK-NEXT: 1 (k, [1, 7]) <write>
+// CHECK-NEXT: 2 (i, [2, 0]) <write>
+// CHECK-NEXT: 2 (j, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (i, [2, 0]) <write>
+// CHECK-NEXT: 1 (j, [2, 0]) <write>
+// CHECK-NEXT: 2 (i, [1, 5]) <write>
+// CHECK-NEXT: 2 (j, [1, 2]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (i, [1, 5]) <write>
+// CHECK-NEXT: 0 IN (j, [1, 2]) <write>
+// CHECK-NEXT: 0 IN (k, [1, 7]) <write>
+// CHECK-NEXT: 0 OUT (i, [1, 5]) <write>
+// CHECK-NEXT: 0 OUT (j, [1, 2]) <write>
+// CHECK-NEXT: 0 OUT (k, [1, 7]) <write>
+// CHECK-NEXT: 1 IN (i, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (j, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (i, [1, 5]) <write>
+// CHECK-NEXT: 1 OUT (j, [1, 2]) <write>
+// CHECK-NEXT: 1 OUT (k, [1, 7]) <write>
+// CHECK-NEXT: 2 OUT (i, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (j, [2, 0]) <write>
+
+namespace struct1 {
+
+struct S {
+ int a, b;
+};
+
+void structtest() {
+ S s;
+ s.a = 5;
+}
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s, [1, 1]) <write>
+// CHECK-NEXT: 1 (s.a, [1, 5]) <write>
+// CHECK-NEXT: 1 (s.b, [1, 1]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [1, 1]) <write>
+// CHECK-NEXT: 0 IN (s.a, [1, 5]) <write>
+// CHECK-NEXT: 0 IN (s.b, [1, 1]) <write>
+// CHECK-NEXT: 0 OUT (s, [1, 1]) <write>
+// CHECK-NEXT: 0 OUT (s.a, [1, 5]) <write>
+// CHECK-NEXT: 0 OUT (s.b, [1, 1]) <write>
+// CHECK-NEXT: 1 OUT (s, [1, 1]) <write>
+// CHECK-NEXT: 1 OUT (s.a, [1, 5]) <write>
+// CHECK-NEXT: 1 OUT (s.b, [1, 1]) <write>
+
+void struct_param(S s) {
+ s.a = 5;
+}
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.a, [1, 3]) <write>
+// CHECK-NEXT: 2 (s, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.a, [1, 3]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.a, [1, 3]) <write>
+// CHECK-NEXT: 0 IN (s.b, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.a, [1, 3]) <write>
+// CHECK-NEXT: 0 OUT (s.b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.a, [1, 3]) <write>
+// CHECK-NEXT: 1 OUT (s.b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.b, [2, 0]) <write>
+
+} // end of namespace struct1
+
+namespace struct2 {
+
+struct Inner {
+ int a, b;
+};
+
+struct S {
+ Inner x;
+ Inner y;
+};
+
+void struct_param(S s) {
+ s.x.b = 7;
+ s.y.b = 5;
+}
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.x.b, [1, 4]) <write>
+// CHECK-NEXT: 1 (s.y.b, [1, 9]) <write>
+// CHECK-NEXT: 2 (s, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.x, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.x.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.x.b, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.y, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.y.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.y.b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.x.b, [2, 0]) <write>
+// CHECK-NEXT: 1 (s.y.b, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.x.b, [1, 4]) <write>
+// CHECK-NEXT: 2 (s.y.b, [1, 9]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.x, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.x.a, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.x.b, [1, 4]) <write>
+// CHECK-NEXT: 0 IN (s.y, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.y.a, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.y.b, [1, 9]) <write>
+// CHECK-NEXT: 0 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.x.a, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.x.b, [1, 4]) <write>
+// CHECK-NEXT: 0 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.y.a, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.y.b, [1, 9]) <write>
+// CHECK-NEXT: 1 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.x, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.x.a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.x.b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.y, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.y.a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.y.b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.x.a, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.x.b, [1, 4]) <write>
+// CHECK-NEXT: 1 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.y.a, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.y.b, [1, 9]) <write>
+// CHECK-NEXT: 2 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.x.a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.x.b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.y.a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.y.b, [2, 0]) <write>
+
+} // namespace struct2
+
+namespace struct_ptr {
+
+struct Inner {
+ int a, b;
+};
+
+struct S {
+ Inner *x;
+ Inner &y;
+ Inner z;
+ S();
+};
+
+void struct_param(S s) {
+ s.x->b = 7;
+ s.y.b = 5;
+ s.z.a = 5;
+}
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.z.a, [1, 15]) <write>
+// CHECK-NEXT: 2 (s, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.x, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.y, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z.a, [1, 15]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.x, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.y, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.z, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.z.a, [1, 15]) <write>
+// CHECK-NEXT: 0 IN (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.z, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.z.a, [1, 15]) <write>
+// CHECK-NEXT: 0 OUT (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.x, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.y, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.z, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.z, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.z.a, [1, 15]) <write>
+// CHECK-NEXT: 1 OUT (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.z, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.z.b, [2, 0]) <write>
+
+void struct_switten(S s) {
+ s.x->b = 7;
+ s.y = {};
+ s.z.a = 5;
+}
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 14]) <invalidation>
+// CHECK-NEXT: 1 (s.z.a, [1, 19]) <write>
+// CHECK-NEXT: 2 (s, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.x, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.y, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 2 (s.z.a, [1, 19]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 14]) <invalidation>
+// CHECK-NEXT: 0 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.x, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.y, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.z, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (s.z.a, [1, 19]) <write>
+// CHECK-NEXT: 0 IN (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 14]) <invalidation>
+// CHECK-NEXT: 0 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.z, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (s.z.a, [1, 19]) <write>
+// CHECK-NEXT: 0 OUT (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.x, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.y, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.z, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 14]) <invalidation>
+// CHECK-NEXT: 1 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.z, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (s.z.a, [1, 19]) <write>
+// CHECK-NEXT: 1 OUT (s.z.b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.x, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.y, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.z, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.z.a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (s.z.b, [2, 0]) <write>
+
+} // namespace struct_ptr
+
+namespace simple_invalidation {
+
+void invalidate(int &i, double d);
+
+void invalidateOnFnCall() {
+ int i;
+ double d = 0.0;
+
+ if (coin())
+ i = 5;
+
+ if (coin())
+ d = 2.3;
+
+ invalidate(i, d);
+}
+// -> [B4] -> -> [B2] ->
+// / \ / \
+// [B6 (ENTRY)] -> [B5] ------> [B3] ------> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [1, 5]) <invalidation>
+// CHECK-NEXT: 1 (i, [1, 5]) <invalidation>
+// CHECK-NEXT: 2 (d, [2, 2]) <write>
+// CHECK-NEXT: 3 (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 4 (i, [4, 2]) <write>
+// CHECK-NEXT: 5 (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 5 (i, [5, 0]) <write>
+// CHECK-NEXT: 5 (d, [5, 2]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 1 (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 1 (i, [4, 2]) <write>
+// CHECK-NEXT: 1 (i, [5, 0]) <write>
+// CHECK-NEXT: 2 (d, [5, 2]) <write>
+// CHECK-NEXT: 3 (global_var, [1, 5]) <invalidation>
+// CHECK-NEXT: 3 (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 4 (i, [1, 5]) <invalidation>
+// CHECK-NEXT: 4 (i, [5, 0]) <write>
+// CHECK-NEXT: 5 (global_var, [1, 5]) <invalidation>
+// CHECK-NEXT: 5 (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 5 (i, [1, 5]) <invalidation>
+// CHECK-NEXT: 5 (i, [4, 2]) <write>
+// CHECK-NEXT: 5 (d, [2, 2]) <write>
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 5]) <invalidation>
+// CHECK-NEXT: 0 IN (i, [1, 5]) <invalidation>
+// CHECK-NEXT: 0 IN (d, [2, 2]) <write>
+// CHECK-NEXT: 0 IN (d, [5, 2]) <write>
+// CHECK-NEXT: 0 OUT (global_var, [1, 5]) <invalidation>
+// CHECK-NEXT: 0 OUT (i, [1, 5]) <invalidation>
+// CHECK-NEXT: 0 OUT (d, [2, 2]) <write>
+// CHECK-NEXT: 0 OUT (d, [5, 2]) <write>
+// CHECK-NEXT: 1 IN (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 1 IN (i, [4, 2]) <write>
+// CHECK-NEXT: 1 IN (i, [5, 0]) <write>
+// CHECK-NEXT: 1 IN (d, [2, 2]) <write>
+// CHECK-NEXT: 1 IN (d, [5, 2]) <write>
+// CHECK-NEXT: 1 OUT (global_var, [1, 5]) <invalidation>
+// CHECK-NEXT: 1 OUT (i, [1, 5]) <invalidation>
+// CHECK-NEXT: 1 OUT (d, [2, 2]) <write>
+// CHECK-NEXT: 1 OUT (d, [5, 2]) <write>
+// CHECK-NEXT: 2 IN (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 2 IN (i, [4, 2]) <write>
+// CHECK-NEXT: 2 IN (i, [5, 0]) <write>
+// CHECK-NEXT: 2 IN (d, [5, 2]) <write>
+// CHECK-NEXT: 2 OUT (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 2 OUT (i, [4, 2]) <write>
+// CHECK-NEXT: 2 OUT (i, [5, 0]) <write>
+// CHECK-NEXT: 2 OUT (d, [2, 2]) <write>
+// CHECK-NEXT: 3 IN (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 3 IN (i, [4, 2]) <write>
+// CHECK-NEXT: 3 IN (i, [5, 0]) <write>
+// CHECK-NEXT: 3 IN (d, [5, 2]) <write>
+// CHECK-NEXT: 3 OUT (global_var, [3, 2]) <invalidation>
+// CHECK-NEXT: 3 OUT (i, [4, 2]) <write>
+// CHECK-NEXT: 3 OUT (i, [5, 0]) <write>
+// CHECK-NEXT: 3 OUT (d, [5, 2]) <write>
+// CHECK-NEXT: 4 IN (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 4 IN (i, [5, 0]) <write>
+// CHECK-NEXT: 4 IN (d, [5, 2]) <write>
+// CHECK-NEXT: 4 OUT (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 4 OUT (i, [4, 2]) <write>
+// CHECK-NEXT: 4 OUT (d, [5, 2]) <write>
+// CHECK-NEXT: 5 OUT (global_var, [5, 5]) <invalidation>
+// CHECK-NEXT: 5 OUT (i, [5, 0]) <write>
+// CHECK-NEXT: 5 OUT (d, [5, 2]) <write>
+
+} // namespace simple_invalidation
+
+void lhs_in_parantheses(int a, int b) {
+ (a, b) = 5;
+}
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (a, [2, 0]) <write>
+// CHECK-NEXT: 2 (b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (a, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (b, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (b, [2, 0]) <write>
+
+void lhs_buried_in_parantheses(int a, int b) {
+ ((((((((a, b)))))))) = 5;
+}
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (a, [2, 0]) <write>
+// CHECK-NEXT: 2 (b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (a, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (b, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (b, [2, 0]) <write>
+
+void lhs_buried_in_parantheses2(int a, int b) {
+ ((((((((a))))), b))) = 5;
+}
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (a, [2, 0]) <write>
+// CHECK-NEXT: 2 (b, [2, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (a, [2, 0]) <write>
+// CHECK-NEXT: 0 IN (b, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 0 OUT (b, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (a, [2, 0]) <write>
+// CHECK-NEXT: 1 IN (b, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 1 OUT (b, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (a, [2, 0]) <write>
+// CHECK-NEXT: 2 OUT (b, [2, 0]) <write>
+
+void lhs_is_conditional_operator(int a, int b) {
+ (a ? a : b) = 5;
+}
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 5 (a, [5, 0]) <write>
+// CHECK-NEXT: 5 (b, [5, 0]) <write>
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (a, [5, 0]) <write>
+// CHECK-NEXT: 0 IN (b, [5, 0]) <write>
+// CHECK-NEXT: 0 OUT (a, [5, 0]) <write>
+// CHECK-NEXT: 0 OUT (b, [5, 0]) <write>
+// CHECK-NEXT: 1 IN (a, [5, 0]) <write>
+// CHECK-NEXT: 1 IN (b, [5, 0]) <write>
+// CHECK-NEXT: 1 OUT (a, [5, 0]) <write>
+// CHECK-NEXT: 1 OUT (b, [5, 0]) <write>
+// CHECK-NEXT: 2 IN (a, [5, 0]) <write>
+// CHECK-NEXT: 2 IN (b, [5, 0]) <write>
+// CHECK-NEXT: 2 OUT (a, [5, 0]) <write>
+// CHECK-NEXT: 2 OUT (b, [5, 0]) <write>
+// CHECK-NEXT: 3 IN (a, [5, 0]) <write>
+// CHECK-NEXT: 3 IN (b, [5, 0]) <write>
+// CHECK-NEXT: 3 OUT (a, [5, 0]) <write>
+// CHECK-NEXT: 3 OUT (b, [5, 0]) <write>
+// CHECK-NEXT: 4 IN (a, [5, 0]) <write>
+// CHECK-NEXT: 4 IN (b, [5, 0]) <write>
+// CHECK-NEXT: 4 OUT (a, [5, 0]) <write>
+// CHECK-NEXT: 4 OUT (b, [5, 0]) <write>
+// CHECK-NEXT: 5 OUT (a, [5, 0]) <write>
+// CHECK-NEXT: 5 OUT (b, [5, 0]) <write>
Index: clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
+++ clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
@@ -10,12 +10,13 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/Analysis/Analyses/Dominators.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
+#include "clang/Analysis/Analyses/ReachingDefinitions.h"
#include "clang/Analysis/CallGraph.h"
-#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
@@ -102,6 +103,78 @@
return true;
}
+//===----------------------------------------------------------------------===//
+// 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());
+ R.dumpGenSet();
+ }
+ }
+};
+} // namespace
+
+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());
+ R.dumpKillSet();
+ }
+ }
+};
+} // namespace
+
+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());
+ R.calculate();
+ R.dumpReachingDefinitions();
+ }
+ }
+};
+} // namespace
+
+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,498 @@
+//===--- 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/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclLookups.h"
+#include "clang/AST/Expr.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/ASTMatchersInternal.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetOperations.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <memory>
+
+using namespace clang;
+using namespace ReachingDefinitionsDetail;
+using namespace ast_matchers;
+
+using DefinitionKind = Definition::DefinitionKind;
+
+//===----------------------------------------------------------------------===//
+// Utility functions.
+//===----------------------------------------------------------------------===//
+
+template <class CallBack>
+static void forAllFields(const VarDecl *Var, FieldChainTy FieldChain,
+ CallBack CB) {
+ // Let's not argue about pointees. For the following code snippet:
+ // s.x->y = 4;
+ // We would like to note a write to s.x, but not to s.x->y.
+ if (FieldChain.size() != 1)
+ if (std::find_if(FieldChain.begin(), FieldChain.end(),
+ [](const FieldDecl *F) {
+ return ento::Loc::isLocType(F->getType());
+ }) != FieldChain.end())
+ return;
+
+ const RecordDecl *R = nullptr;
+ if (FieldChain.empty()) {
+ R = Var->getType()->getAsRecordDecl();
+ } else {
+ R = FieldChain.back()->getType()->getAsRecordDecl();
+ }
+
+ CB(FieldChain);
+
+ if (R) {
+ for (const FieldDecl *Field : R->fields()) {
+ FieldChainTy Cpy = FieldChain;
+ Cpy.emplace_back(Field);
+ forAllFields(Var, Cpy, CB);
+ }
+ }
+}
+
+static bool killsVar(const Definition &Victim, const GenSet &Set) {
+ for (const Definition &Perpetrator : Set)
+ if (std::make_pair(Victim.Var, Victim.FieldChain) ==
+ std::make_pair(Perpetrator.Var, Perpetrator.FieldChain))
+ return true;
+ return false;
+}
+
+static StringRef describeDefinitionKind(DefinitionKind K) {
+ switch (K) {
+ case Definition::Write:
+ return "write";
+ case Definition::Invalidation:
+ return "invalidation";
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// Methods of Definition.
+//===----------------------------------------------------------------------===//
+//
+bool operator<(const FieldChainTy &Lhs, const FieldChainTy &Rhs) {
+ if (Lhs.size() != Rhs.size())
+ return Lhs.size() < Rhs.size();
+
+ for (size_t Index = 0; Index < Lhs.size(); ++Index) {
+ if (Lhs[Index] != Rhs[Index])
+ return Lhs[Index] < Rhs[Index];
+ }
+
+ return false;
+}
+
+void Definition::dump() const {
+ llvm::errs() << "(" << Var->getNameAsString();
+
+ for (const FieldDecl *Field : FieldChain)
+ llvm::errs() << "." + Field->getNameAsString();
+
+ llvm::errs() << ", [" << getCFGBlock()->getIndexInCFG() << ", "
+ << E.getIndexInBlock() << "])"
+ << " <" << (describeDefinitionKind(Kind)) << ">";
+}
+
+//===----------------------------------------------------------------------===//
+// Matcher callbacks for constructing GEN sets.
+//===----------------------------------------------------------------------===//
+
+class DeclRefExprCB : public GenSetMatcherCallback {
+public:
+ DeclRefExprCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return declRefExpr(to(varDecl().bind("var")));
+ }
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ const auto *Var = Result.Nodes.getNodeAs<VarDecl>("var");
+ assert(Var);
+ GSBuilder.insertToGenSet(Var, GSBuilder.CurrentKind);
+ }
+};
+
+class ParenExprCB : public GenSetMatcherCallback {
+public:
+ ParenExprCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return parenExpr().bind("paren");
+ }
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ const auto *Paren = Result.Nodes.getNodeAs<ParenExpr>("paren");
+ assert(Paren);
+ // TODO
+ }
+};
+
+class MemberExprCB : public GenSetMatcherCallback {
+public:
+ MemberExprCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return memberExpr(unless(hasAncestor(memberExpr()))).bind("member");
+ }
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ // If we found an assignemnt to S.x.y.z, the matcher will match for
+ // the last MemberExpr (z), let's build the fieldchain back up.
+ const auto *Member = Result.Nodes.getNodeAs<MemberExpr>("member");
+ assert(Member);
+ FieldChainTy FieldChain;
+ FieldChain.emplace_back(cast<FieldDecl>(Member->getMemberDecl()));
+
+ const Expr *NextBase = Member->getBase()->IgnoreParenCasts();
+ // Retrieve the next field in the fieldchain.
+ while ((Member = dyn_cast<MemberExpr>(NextBase))) {
+ FieldChain.emplace_back(cast<FieldDecl>(Member->getMemberDecl()));
+ NextBase = Member->getBase()->IgnoreParenCasts();
+ }
+ std::reverse(FieldChain.begin(), FieldChain.end());
+
+ GSBuilder.insertToGenSet(
+ cast<VarDecl>(cast<DeclRefExpr>(NextBase)->getDecl()), FieldChain,
+ GSBuilder.CurrentKind);
+ }
+};
+
+class AssignmentOperatorCB : public GenSetMatcherCallback {
+public:
+ AssignmentOperatorCB(GenSetBuilder &GSBuilder)
+ : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return binaryOperator(isAssignmentOperator()).bind("assign");
+ }
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ const auto *BO = Result.Nodes.getNodeAs<BinaryOperator>("assign");
+ assert(BO);
+ GSBuilder.handleExpr(BO->getLHS(), DefinitionKind::Write);
+ }
+};
+
+class DeclarationCB : public GenSetMatcherCallback {
+public:
+ DeclarationCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return declStmt().bind("decls");
+ }
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ const auto *DS = Result.Nodes.getNodeAs<DeclStmt>("decls");
+ assert(DS);
+
+ for (const Decl *D : DS->decls()) {
+ const auto *Var = dyn_cast<VarDecl>(D);
+ if (!Var)
+ continue;
+
+ GSBuilder.insertToGenSet(Var, DefinitionKind::Write);
+ }
+ }
+};
+
+class CallExprCB : public GenSetMatcherCallback {
+public:
+ CallExprCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return callExpr().bind("calls");
+ }
+
+ void invalidateGlobals() {
+ for (const Variable &Var : GSBuilder.AllGlobalVariables)
+ GSBuilder.insertToGenSet(Var.Var, Var.FieldChain,
+ DefinitionKind::Invalidation);
+ }
+
+ static QualType stripPointers(QualType T) {
+ while (!T->getPointeeType().isNull())
+ T = T->getPointeeType();
+
+ return T;
+ }
+
+ static bool isPointerToNonConstTy(QualType T) {
+ if (T->getPointeeType().isNull())
+ return false;
+ return !stripPointers(T).isConstQualified();
+ }
+
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ const auto *Call = Result.Nodes.getNodeAs<CallExpr>("calls");
+ assert(Call);
+
+ invalidateGlobals();
+
+ const FunctionDecl *FD = Call->getDirectCallee();
+ if (!FD)
+ return;
+ bool HasImplicitThisParam = isa<CXXMethodDecl>(FD);
+
+ for (size_t Index = 0,
+ E = Call->getNumArgs() - (HasImplicitThisParam ? 1 : 0);
+ Index < E; ++Index) {
+ QualType ParamTy = FD->getParamDecl(Index)->getOriginalType();
+ if (!ParamTy->isRecordType() && !isPointerToNonConstTy(ParamTy))
+ continue;
+ GSBuilder.handleExpr(Call->getArg(Index) + (HasImplicitThisParam ? 1 : 0),
+ Definition::Invalidation);
+ }
+ }
+};
+
+// This should be okay. For tricky global functions, we invalidate them at
+// every function call anyways. Retrieving an object out of thin air is only
+// problematic if they are pointing to an external object, something we don't
+// dare reasoning about.
+// As unbelievable as it may sound, variables and their fields of DeclRefExprs,
+// coupled with all the non-local visible objects should be all that we have to
+// calculate with.
+class VariableCollectorCB : public GenSetMatcherCallback {
+public:
+ VariableCollectorCB(GenSetBuilder &GSBuilder)
+ : GenSetMatcherCallback(GSBuilder) {}
+
+ static internal::Matcher<Stmt> getMatcher() {
+ return stmt(forEachDescendant(declRefExpr().bind("var")));
+ }
+
+ virtual void run(const MatchFinder::MatchResult &Result) override {
+ const auto *E = Result.Nodes.getNodeAs<DeclRefExpr>("var");
+ assert(E);
+ if (const VarDecl *Var = dyn_cast<VarDecl>(E->getDecl()))
+ GSBuilder.addVariable(Var, {});
+ }
+};
+
+//===----------------------------------------------------------------------===//
+// Methods of GenSetBuilder.
+//===----------------------------------------------------------------------===//
+
+GenSetBuilder::GenSetBuilder() {
+ addMatcher<&GenSetBuilder::VariableFinder, VariableCollectorCB>();
+
+ // TODO: Elvis operator (?:).
+ addMatcher<&GenSetBuilder::ExpressionFinder, DeclRefExprCB>();
+ addMatcher<&GenSetBuilder::ExpressionFinder, MemberExprCB>();
+ addMatcher<&GenSetBuilder::ExpressionFinder, ParenExprCB>();
+
+ // TODO: Destructor calls? Should we be THAT conservative?
+ // TODO: Moving an object?
+ // TODO: Method calls?
+ // TODO: Analyzing a method?
+ // TODO: What do you do with Objective.*???
+ addMatcher<&GenSetBuilder::DefinitionFinder, AssignmentOperatorCB>();
+ addMatcher<&GenSetBuilder::DefinitionFinder, DeclarationCB>();
+ addMatcher<&GenSetBuilder::DefinitionFinder, CallExprCB>();
+}
+
+template <ast_matchers::MatchFinder GenSetBuilder::*Finder,
+ class GenSetMatcherCallbackTy>
+void GenSetBuilder::addMatcher() {
+ Callbacks.emplace_back(std::make_unique<GenSetMatcherCallbackTy>(*this));
+ (this->*Finder)
+ .addMatcher(GenSetMatcherCallbackTy::getMatcher(),
+ Callbacks.back().get());
+}
+
+void GenSetBuilder::insertToGenSet(const VarDecl *Var, FieldChainTy FieldChain,
+ DefinitionKind Kind) {
+ forAllFields(Var, FieldChain, [this, Var, Kind](const FieldChainTy &FC) {
+ CurrentGenSet->emplace(Var, FC, *CurrentCFGElem, Kind);
+ // TODO: Invalidate all variables that can alias with this type.
+ });
+}
+
+void GenSetBuilder::addVariable(const VarDecl *Var, FieldChainTy FieldChain) {
+ forAllFields(Var, FieldChain, [this, Var](const FieldChainTy &FC) {
+ AllVariables.emplace(Var, FC);
+ });
+}
+
+void GenSetBuilder::addGlobalVariable(const VarDecl *Var) {
+ forAllFields(Var, FieldChainTy{}, [this, Var](const FieldChainTy &FC) {
+ AllGlobalVariables.emplace(Var, FC);
+ });
+}
+
+void GenSetBuilder::init(const Decl *D) {
+ Context = &D->getASTContext();
+
+ // Collect all variables.
+ if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
+ VariableFinder.match(*FD, FD->getASTContext());
+ for (const ParmVarDecl *Param : FD->parameters())
+ addVariable(Param, {});
+ }
+
+ // Collect all non-local variables in a separate set.
+ // TODO: Does this actually collect all non-local but visible variables?
+ const DeclContext *DC = D->getDeclContext();
+ while (DC) {
+ DC = DC->getPrimaryContext();
+ for (const Decl *Res : DC->decls())
+ if (const auto *VD = dyn_cast<VarDecl>(Res))
+ addGlobalVariable(VD);
+ DC = DC->getParent();
+ }
+}
+
+void GenSetBuilder::handleExpr(const Expr *E, DefinitionKind Kind) {
+ CurrentKind = Kind;
+ ExpressionFinder.match(*E, *Context);
+}
+
+LLVM_NODISCARD
+GenSet GenSetBuilder::getGenSetForCFGBlock(const Decl *D, const CFGBlock *B) {
+ if (B->empty())
+ return {};
+
+ VariableFinder.match(*D, D->getASTContext());
+
+ CurrentGenSet = GenSet{};
+
+ for (CFGBlock::ConstCFGElementRef E : B->rrefs()) {
+ if (E->getKind() != CFGElement::Kind::Statement)
+ continue;
+ CurrentCFGElem = E;
+
+ const Stmt *S = E->castAs<CFGStmt>().getStmt();
+ assert(S);
+ DefinitionFinder.match(*S, D->getASTContext());
+ }
+
+ return *CurrentGenSet;
+}
+
+LLVM_NODISCARD GenSet
+GenSetBuilder::getGenSetForParameters(const Decl *D, const CFGBlock *Entry) {
+ CurrentGenSet = GenSet{};
+ CurrentCFGElem = {Entry, 0};
+ if (const auto *F = dyn_cast<FunctionDecl>(D)) {
+ for (const ParmVarDecl *Param : F->parameters()) {
+ insertToGenSet(Param, Definition::DefinitionKind::Write);
+ }
+ }
+ return *CurrentGenSet;
+}
+
+//===----------------------------------------------------------------------===//
+// Methods of ReachingDefinitionsCalculator.
+//===----------------------------------------------------------------------===//
+
+void ReachingDefinitionsCalculator::init() {
+ GSBuilder.init(D);
+
+ for (const CFGBlock *B : *cfg)
+ Gen[B] = GSBuilder.getGenSetForCFGBlock(D, B);
+
+ Gen[&cfg->getEntry()] = GSBuilder.getGenSetForParameters(D, &cfg->getEntry());
+
+ llvm::SmallVector<Definition, 16> AllDefinitions;
+ for (const std::pair<const CFGBlock *, GenSet> &G : Gen)
+ for (const Definition &Def : G.second)
+ AllDefinitions.push_back(Def);
+
+ for (const std::pair<const CFGBlock *, GenSet> &G : Gen)
+ for (const Definition &Def : AllDefinitions)
+ if (G.first != Def.getCFGBlock() && killsVar(Def, G.second))
+ Kill[G.first].insert(Def);
+}
+
+using WorklistTy = llvm::SmallVector<const CFGBlock *, 5>;
+
+void ReachingDefinitionsCalculator::calculate() {
+ for (const std::pair<const CFGBlock *, GenSet> &G : Gen)
+ Out[G.first] = {G.second.begin(), G.second.end()};
+
+ WorklistTy Worklist({cfg->begin(), cfg->end()});
+
+ while (!Worklist.empty()) {
+ const CFGBlock *N = Worklist.pop_back_val();
+
+ for (const CFGBlock *Pred : N->preds())
+ 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 (const CFGBlock *Succ : N->succs())
+ Worklist.push_back(Succ);
+ }
+ }
+}
+
+void ReachingDefinitionsCalculator::dumpGenSet() const {
+ llvm::errs() << "GEN sets: blockid (varname [blockid, elementid])\n";
+ for (const std::pair<const CFGBlock *, GenSet> &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 *, DefinitionSet> &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
@@ -22,6 +22,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
@@ -1343,8 +1343,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,176 @@
+//===--- 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/AST/Decl.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/ADT/SmallVector.h"
+#include <set>
+
+namespace clang {
+
+namespace ReachingDefinitionsDetail {
+
+using FieldChainTy = llvm::SmallVector<const FieldDecl *, 2>;
+bool operator<(const FieldChainTy &Lhs, const FieldChainTy &Rhs);
+
+struct Variable {
+ // TODO: Implicit parameters, such as captured fields, CXXThis etc?
+ const VarDecl *Var;
+ FieldChainTy FieldChain;
+
+ Variable(const VarDecl *Var, FieldChainTy FieldChain)
+ : Var(Var), FieldChain(FieldChain) {}
+};
+
+struct VariableLess {
+ // TODO: const ref? but what if we change this to immutablelist?
+ bool operator()(Variable Lhs, Variable Rhs) {
+ return std::make_pair(Lhs.Var, Lhs.FieldChain) <
+ std::make_pair(Rhs.Var, Rhs.FieldChain);
+ }
+};
+
+struct Definition : Variable {
+ enum DefinitionKind { Write, Invalidation };
+
+ CFGBlock::ConstCFGElementRef E;
+ DefinitionKind Kind;
+
+ const CFGBlock *getCFGBlock() const { return E.getParent(); }
+
+ // (varname [blockid, elementid]) (reason)
+ void dump() const;
+
+ Definition(const VarDecl *Var, FieldChainTy FieldChain,
+ CFGBlock::ConstCFGElementRef E, DefinitionKind Kind)
+ : Variable(Var, std::move(FieldChain)), E(E), Kind(Kind) {}
+
+ Definition(const VarDecl *Var, CFGBlock::ConstCFGElementRef E,
+ DefinitionKind Kind)
+ : Definition(Var, /*FieldChain=*/{}, E, Kind) {}
+};
+
+struct VarAndCFGElementLess {
+ bool operator()(Definition Lhs, Definition Rhs) const {
+ return std::tie(Lhs.Var, Lhs.FieldChain, Lhs.E) <
+ std::tie(Rhs.Var, Rhs.FieldChain, Rhs.E);
+ }
+};
+
+// TODO: This aint gonna be good. We need to track more then a single definition
+// to a variable. Say, the static analyzer manages to prove that a potential
+// invalidation definition (like a function call) didn't write the variable, we
+// need to retrieve the definitions up to that point in the block.
+using GenSet = std::set<Definition, VariableLess>;
+using DefinitionSet = std::set<Definition, VarAndCFGElementLess>;
+
+class GenSetBuilder;
+
+class GenSetMatcherCallback : public ast_matchers::MatchFinder::MatchCallback {
+protected:
+ GenSetBuilder &GSBuilder;
+
+ GenSetMatcherCallback(GenSetBuilder &GSBuilder) : GSBuilder(GSBuilder) {}
+};
+
+class GenSetBuilder {
+ using DefinitionKind = Definition::DefinitionKind;
+
+ llvm::SmallVector<std::unique_ptr<GenSetMatcherCallback>, 8> Callbacks;
+
+ ast_matchers::MatchFinder DefinitionFinder;
+ ast_matchers::MatchFinder VariableFinder;
+ ast_matchers::MatchFinder ExpressionFinder;
+
+ Optional<GenSet> CurrentGenSet;
+ Optional<CFGBlock::ConstCFGElementRef> CurrentCFGElem;
+
+ ASTContext *Context = nullptr;
+
+public:
+ std::set<Variable, VariableLess> AllVariables;
+ std::set<Variable, VariableLess> AllGlobalVariables;
+ // TODO: this is super wonky, come oooon duuuuuude
+ DefinitionKind CurrentKind = Definition::Write;
+
+private:
+ template <ast_matchers::MatchFinder GenSetBuilder::*Finder,
+ class GenSetMatcherCallbackTy>
+ void addMatcher();
+
+public:
+ GenSetBuilder();
+ void init(const Decl *D);
+
+ LLVM_NODISCARD GenSet getGenSetForCFGBlock(const Decl *D, const CFGBlock *B);
+
+ LLVM_NODISCARD GenSet getGenSetForParameters(const Decl *D,
+ const CFGBlock *Entry);
+
+ void insertToGenSet(const VarDecl *Var, DefinitionKind Kind) {
+ insertToGenSet(Var, FieldChainTy{}, Kind);
+ }
+
+ void insertToGenSet(const VarDecl *Var, FieldChainTy FieldChain,
+ DefinitionKind Kind);
+
+ void handleExpr(const Expr *E, DefinitionKind Kind);
+
+ void addVariable(const VarDecl *Var, FieldChainTy FieldChain);
+ void addGlobalVariable(const VarDecl *Var);
+};
+
+} // end of namespace ReachingDefinitionsDetail
+
+// TODO: Maybe use the fact that this is a ManagedAnalysis? Also, control dep
+// calculator isn't doing it either.
+class ReachingDefinitionsCalculator : public ManagedAnalysis {
+public:
+ using GenSet = ReachingDefinitionsDetail::GenSet;
+ using DefinitionSet = ReachingDefinitionsDetail::DefinitionSet;
+ using GenSetBuilder = ReachingDefinitionsDetail::GenSetBuilder;
+
+ ReachingDefinitionsCalculator(const Decl *D, const CFG *cfg)
+ : cfg(cfg), D(D) {
+ init();
+ }
+
+ // TODO: Should we expose the Gen map so that entries could be deleted and
+ // the kill/reaching definition sets recalculated?
+ void init();
+ void calculate();
+
+ void dumpKillSet() const;
+ void dumpGenSet() const;
+ void dumpReachingDefinitions() const;
+
+private:
+ const CFG *cfg;
+ const Decl *D;
+
+ GenSetBuilder GSBuilder;
+
+ std::map<const CFGBlock *, GenSet> Gen;
+ std::map<const CFGBlock *, DefinitionSet> 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
