Szelethus updated this revision to Diff 221355.
Szelethus added a comment.
The following words are echoing in my ears as I'm knowingly going completely
against them:
In D45532#1083670 <https://reviews.llvm.org/D45532#1083670>, @NoQ wrote:
> I'm asking for this because it's, like, actually difficult and painful to
> understand formal information in large chunks. One-solution-at-a-time would
> have been so much easier. It is really a bad idea to start by presenting a
> working solution; the great idea is to present a small non-working solution
> with a reasonable idea behind it, and then extend it "in place" as much as it
> seems necessary. It is very comfortable when parts of the patch with
> different "status" (main ideas, corner-case fixes, heuristics, refactoring)
> stay in separate patches.
>
> Essentially every part of the solution that you implement, if you think it
> might deserve a separate discussion, also deserves a separate patch. It is
> reasonable to split the work into logical chunks before you start it. It's
> very unlikely that you have a single idea that takes 500 non-trivial lines of
> code to express. Splitting up ideas so that they were easy to grasp is an
> invaluable effort.
I'll keep this revision as more of a bag of ideas, and create a series of
patches when I got the core of this figured out. This algorithm is very hard to
implement, and its easier for me to not bother with splitting up my entire work
when I'm still shooting at a moving target. Several of my ideas required me to
make huge refactorings, and as the code grows, my overall desire for the
finished algorithm changes as well.
With that said.
I made the following changes:
- Added support for record, but not much in terms of C++ classes.
- Fields of a record are identified with a (variable, chain of fields) pair,
e.g. `Var.a.x.b` would be represented with (`Var`, `FieldDecl`s of `[a, x,
b]`).
- A `Definition` of a record object doesn't contain `Definition`s of its
fields -- instead, whenever a `Definition` of a record object is added to a GEN
set, a helper function creates adds `Definition`s for its fields. This is
convenient, else we'd need to flatten `Definition`s later on. For the example
mentioned earlier, we really need an entry separately for `Var`, `Var.a`,
`Var.a.x`, `Var.a.x.b` in order for the analyzer to conveniently ask for
reaching definitions later down the line.
- Added/corrected plenty of test cases.
- Haven't really touched variable invalidation.
- Decorated the code with a ton of `TODO`s, but not much documentation just yet.
There are a couple things I'm worrying about, especially those that @xazax.hun
mentioned in the inlines. I'm still confident that actual writes to a variable
may only be assignments and variable definitions, but they can be esoteric
enough, e.g. `(a, b) = 5`, `retrieveWhateverObject() = {9, 5, "remember the
vasa"}`. For now, performance doesn't really concern me, but eventually I'll
need to move the matchers to a builder class. Invalidation propagation (as
discussed on mailing list
<http://lists.llvm.org/pipermail/cfe-dev/2019-July/062975.html>) hide in them a
variety of tricky edge cases. All of these combined create a desire for a
thought-out, easily extensible way to create GEN sets.
So, here are my ideas.
- Overall code structure
- Create a builder object, stored in the calculator itself, which would store
the expensive-to-create matchers.
- Make assignment an event to which a variety of rules may be assigned to, so
special cases like `(a, b) = 5`, `retrieveWhateverObject() = {9, 5, "remember
the vasa"}`, assignment to `this`, and whatever pitfalls Objective-.* languages
have may be more easily handled.
- GEN sets store the outgoing, or in other words, last definition to each
variable, but this information is not enough. The way I described
<http://lists.llvm.org/pipermail/cfe-dev/2019-July/062885.html> how I plan to
make this algorithm semi-intraprocedural with the use of visitors in a nutshell
works by the analyzer trying to prove that an invalidation really does write a
variable, or can be discarded. However, in the same block, for the same
variable, multiple invalidations of the same variable may occur. So, instead of
storing the last definition, we should store all invalidations up to the first
write. Later, the analyzer could remove these definitions directly, and ask the
calculator to regenerate the KILL sets and recalculate the reaching definitions
sets.
- Invalidation
- Research type based alias analysis
<http://lists.llvm.org/pipermail/cfe-dev/2019-July/062984.html>, until then,
ignore aliases, and just invalidate objects of the same type.
- The example below highlights how the function call on line 2 is a
definition of `i`, because `ptr` might point to it, but may not be a definition
of `j`. Buuuuuuuuuuut, with the use of `goto`, it is possible
<https://stackoverflow.com/a/6791537>. This implies that every variable in a
non-nested scope has to be invalidated if a pointer with an aliasing type
escapes. This may be super tricky to implement precisely, so I'll probably just
take all variables, not only non-nested ones into account.
1 void f(int i, int *ptr) {
2 foo(ptr);
3 int j;
4 }
- Invalidation has to be very customizable. The static analyzer doesn't
generate code, so some relaxation of the invalidation ruleset maybe desirable,
such as assuming that `offsetof` isn't used to change the rest of the record if
a field of it escapes.
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,733 @@
+// 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 IN (ptr, [4, 3])
+// CHECK-NEXT: 0 OUT (global_var, [4, 6])
+// CHECK-NEXT: 0 OUT (ptr, [3, 3])
+// CHECK-NEXT: 0 OUT (ptr, [4, 3])
+// CHECK-NEXT: 1 IN (global_var, [4, 6])
+// CHECK-NEXT: 1 IN (ptr, [3, 3])
+// CHECK-NEXT: 1 IN (ptr, [4, 3])
+// CHECK-NEXT: 1 OUT (global_var, [4, 6])
+// CHECK-NEXT: 1 OUT (ptr, [3, 3])
+// CHECK-NEXT: 1 OUT (ptr, [4, 3])
+// CHECK-NEXT: 2 IN (global_var, [4, 6])
+// CHECK-NEXT: 2 IN (ptr, [3, 3])
+// CHECK-NEXT: 2 IN (ptr, [4, 3])
+// CHECK-NEXT: 2 OUT (global_var, [4, 6])
+// CHECK-NEXT: 2 OUT (ptr, [3, 3])
+// CHECK-NEXT: 2 OUT (ptr, [4, 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 IN (i, [4, 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 IN (i, [6, 3])
+// 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 IN (x, [4, 2])
+// CHECK-NEXT: 0 OUT (global_var, [2, 2])
+// CHECK-NEXT: 0 OUT (flag, [2, 2])
+// CHECK-NEXT: 0 OUT (x, [3, 3])
+// CHECK-NEXT: 0 OUT (x, [4, 2])
+// 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 IN (x, [4, 2])
+// CHECK-NEXT: 1 OUT (global_var, [2, 2])
+// CHECK-NEXT: 1 OUT (flag, [2, 2])
+// CHECK-NEXT: 1 OUT (x, [3, 3])
+// CHECK-NEXT: 1 OUT (x, [4, 2])
+// 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 IN (x, [4, 2])
+// CHECK-NEXT: 2 OUT (global_var, [2, 2])
+// CHECK-NEXT: 2 OUT (flag, [2, 2])
+// CHECK-NEXT: 2 OUT (x, [3, 3])
+// CHECK-NEXT: 2 OUT (x, [4, 2])
+// 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 (global_var, [2, 6])
+// CHECK-NEXT: 0 IN (ptr, [2, 3])
+// CHECK-NEXT: 0 OUT (global_var, [1, 2])
+// CHECK-NEXT: 0 OUT (global_var, [2, 6])
+// 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;
+}
+// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (i, [1, 5])
+// CHECK-NEXT: 1 (j, [1, 2])
+// 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, 5])
+// CHECK-NEXT: 2 (j, [1, 2])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (i, [1, 5])
+// CHECK-NEXT: 0 IN (j, [1, 2])
+// CHECK-NEXT: 0 IN (k, [1, 7])
+// CHECK-NEXT: 0 OUT (i, [1, 5])
+// CHECK-NEXT: 0 OUT (j, [1, 2])
+// 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, 5])
+// CHECK-NEXT: 1 OUT (j, [1, 2])
+// CHECK-NEXT: 1 OUT (k, [1, 7])
+// CHECK-NEXT: 2 OUT (i, [2, 0])
+// CHECK-NEXT: 2 OUT (j, [2, 0])
+
+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])
+// CHECK-NEXT: 1 (s.a, [1, 5])
+// CHECK-NEXT: 1 (s.b, [1, 1])
+// 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])
+// CHECK-NEXT: 0 IN (s.a, [1, 5])
+// CHECK-NEXT: 0 IN (s.b, [1, 1])
+// CHECK-NEXT: 0 OUT (s, [1, 1])
+// CHECK-NEXT: 0 OUT (s.a, [1, 5])
+// CHECK-NEXT: 0 OUT (s.b, [1, 1])
+// CHECK-NEXT: 1 OUT (s, [1, 1])
+// CHECK-NEXT: 1 OUT (s.a, [1, 5])
+// CHECK-NEXT: 1 OUT (s.b, [1, 1])
+
+void struct_param(S s) {
+ s.a = 5;
+}
+
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.a, [1, 3])
+// CHECK-NEXT: 2 (s, [2, 0])
+// CHECK-NEXT: 2 (s.a, [2, 0])
+// CHECK-NEXT: 2 (s.b, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.a, [2, 0])
+// CHECK-NEXT: 2 (s.a, [1, 3])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [2, 0])
+// CHECK-NEXT: 0 IN (s.a, [1, 3])
+// CHECK-NEXT: 0 IN (s.b, [2, 0])
+// CHECK-NEXT: 0 OUT (s, [2, 0])
+// CHECK-NEXT: 0 OUT (s.a, [1, 3])
+// CHECK-NEXT: 0 OUT (s.b, [2, 0])
+// CHECK-NEXT: 1 IN (s, [2, 0])
+// CHECK-NEXT: 1 IN (s.a, [2, 0])
+// CHECK-NEXT: 1 IN (s.b, [2, 0])
+// CHECK-NEXT: 1 OUT (s, [2, 0])
+// CHECK-NEXT: 1 OUT (s.a, [1, 3])
+// CHECK-NEXT: 1 OUT (s.b, [2, 0])
+// CHECK-NEXT: 2 OUT (s, [2, 0])
+// CHECK-NEXT: 2 OUT (s.a, [2, 0])
+// CHECK-NEXT: 2 OUT (s.b, [2, 0])
+
+} // 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])
+// CHECK-NEXT: 1 (s.y.b, [1, 9])
+// CHECK-NEXT: 2 (s, [2, 0])
+// CHECK-NEXT: 2 (s.x, [2, 0])
+// CHECK-NEXT: 2 (s.x.a, [2, 0])
+// CHECK-NEXT: 2 (s.x.b, [2, 0])
+// CHECK-NEXT: 2 (s.y, [2, 0])
+// CHECK-NEXT: 2 (s.y.a, [2, 0])
+// CHECK-NEXT: 2 (s.y.b, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.x.b, [2, 0])
+// CHECK-NEXT: 1 (s.y.b, [2, 0])
+// CHECK-NEXT: 2 (s.x.b, [1, 4])
+// CHECK-NEXT: 2 (s.y.b, [1, 9])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [2, 0])
+// CHECK-NEXT: 0 IN (s.x, [2, 0])
+// CHECK-NEXT: 0 IN (s.x.a, [2, 0])
+// CHECK-NEXT: 0 IN (s.x.b, [1, 4])
+// CHECK-NEXT: 0 IN (s.y, [2, 0])
+// CHECK-NEXT: 0 IN (s.y.a, [2, 0])
+// CHECK-NEXT: 0 IN (s.y.b, [1, 9])
+// CHECK-NEXT: 0 OUT (s, [2, 0])
+// CHECK-NEXT: 0 OUT (s.x, [2, 0])
+// CHECK-NEXT: 0 OUT (s.x.a, [2, 0])
+// CHECK-NEXT: 0 OUT (s.x.b, [1, 4])
+// CHECK-NEXT: 0 OUT (s.y, [2, 0])
+// CHECK-NEXT: 0 OUT (s.y.a, [2, 0])
+// CHECK-NEXT: 0 OUT (s.y.b, [1, 9])
+// CHECK-NEXT: 1 IN (s, [2, 0])
+// CHECK-NEXT: 1 IN (s.x, [2, 0])
+// CHECK-NEXT: 1 IN (s.x.a, [2, 0])
+// CHECK-NEXT: 1 IN (s.x.b, [2, 0])
+// CHECK-NEXT: 1 IN (s.y, [2, 0])
+// CHECK-NEXT: 1 IN (s.y.a, [2, 0])
+// CHECK-NEXT: 1 IN (s.y.b, [2, 0])
+// CHECK-NEXT: 1 OUT (s, [2, 0])
+// CHECK-NEXT: 1 OUT (s.x, [2, 0])
+// CHECK-NEXT: 1 OUT (s.x.a, [2, 0])
+// CHECK-NEXT: 1 OUT (s.x.b, [1, 4])
+// CHECK-NEXT: 1 OUT (s.y, [2, 0])
+// CHECK-NEXT: 1 OUT (s.y.a, [2, 0])
+// CHECK-NEXT: 1 OUT (s.y.b, [1, 9])
+// CHECK-NEXT: 2 OUT (s, [2, 0])
+// CHECK-NEXT: 2 OUT (s.x, [2, 0])
+// CHECK-NEXT: 2 OUT (s.x.a, [2, 0])
+// CHECK-NEXT: 2 OUT (s.x.b, [2, 0])
+// CHECK-NEXT: 2 OUT (s.y, [2, 0])
+// CHECK-NEXT: 2 OUT (s.y.a, [2, 0])
+// CHECK-NEXT: 2 OUT (s.y.b, [2, 0])
+
+} // 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])
+// CHECK-NEXT: 2 (s, [2, 0])
+// CHECK-NEXT: 2 (s.x, [2, 0])
+// CHECK-NEXT: 2 (s.y, [2, 0])
+// CHECK-NEXT: 2 (s.z, [2, 0])
+// CHECK-NEXT: 2 (s.z.a, [2, 0])
+// CHECK-NEXT: 2 (s.z.b, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.z.a, [2, 0])
+// CHECK-NEXT: 2 (s.z.a, [1, 15])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (s, [2, 0])
+// CHECK-NEXT: 0 IN (s.x, [2, 0])
+// CHECK-NEXT: 0 IN (s.y, [2, 0])
+// CHECK-NEXT: 0 IN (s.z, [2, 0])
+// CHECK-NEXT: 0 IN (s.z.a, [1, 15])
+// CHECK-NEXT: 0 IN (s.z.b, [2, 0])
+// CHECK-NEXT: 0 OUT (s, [2, 0])
+// CHECK-NEXT: 0 OUT (s.x, [2, 0])
+// CHECK-NEXT: 0 OUT (s.y, [2, 0])
+// CHECK-NEXT: 0 OUT (s.z, [2, 0])
+// CHECK-NEXT: 0 OUT (s.z.a, [1, 15])
+// CHECK-NEXT: 0 OUT (s.z.b, [2, 0])
+// CHECK-NEXT: 1 IN (s, [2, 0])
+// CHECK-NEXT: 1 IN (s.x, [2, 0])
+// CHECK-NEXT: 1 IN (s.y, [2, 0])
+// CHECK-NEXT: 1 IN (s.z, [2, 0])
+// CHECK-NEXT: 1 IN (s.z.a, [2, 0])
+// CHECK-NEXT: 1 IN (s.z.b, [2, 0])
+// CHECK-NEXT: 1 OUT (s, [2, 0])
+// CHECK-NEXT: 1 OUT (s.x, [2, 0])
+// CHECK-NEXT: 1 OUT (s.y, [2, 0])
+// CHECK-NEXT: 1 OUT (s.z, [2, 0])
+// CHECK-NEXT: 1 OUT (s.z.a, [1, 15])
+// CHECK-NEXT: 1 OUT (s.z.b, [2, 0])
+// CHECK-NEXT: 2 OUT (s, [2, 0])
+// CHECK-NEXT: 2 OUT (s.x, [2, 0])
+// CHECK-NEXT: 2 OUT (s.y, [2, 0])
+// CHECK-NEXT: 2 OUT (s.z, [2, 0])
+// CHECK-NEXT: 2 OUT (s.z.a, [2, 0])
+// CHECK-NEXT: 2 OUT (s.z.b, [2, 0])
+
+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])
+// CHECK-NEXT: 1 (s.z.a, [1, 19])
+// CHECK-NEXT: 2 (s, [2, 0])
+// CHECK-NEXT: 2 (s.x, [2, 0])
+// CHECK-NEXT: 2 (s.y, [2, 0])
+// CHECK-NEXT: 2 (s.z, [2, 0])
+// CHECK-NEXT: 2 (s.z.a, [2, 0])
+// CHECK-NEXT: 2 (s.z.b, [2, 0])
+// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 1 (s.z.a, [2, 0])
+// CHECK-NEXT: 2 (s.z.a, [1, 19])
+// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid])
+// CHECK-NEXT: 0 IN (global_var, [1, 14])
+// CHECK-NEXT: 0 IN (s, [2, 0])
+// CHECK-NEXT: 0 IN (s.x, [2, 0])
+// CHECK-NEXT: 0 IN (s.y, [2, 0])
+// CHECK-NEXT: 0 IN (s.z, [2, 0])
+// CHECK-NEXT: 0 IN (s.z.a, [1, 19])
+// CHECK-NEXT: 0 IN (s.z.b, [2, 0])
+// CHECK-NEXT: 0 OUT (global_var, [1, 14])
+// CHECK-NEXT: 0 OUT (s, [2, 0])
+// CHECK-NEXT: 0 OUT (s.x, [2, 0])
+// CHECK-NEXT: 0 OUT (s.y, [2, 0])
+// CHECK-NEXT: 0 OUT (s.z, [2, 0])
+// CHECK-NEXT: 0 OUT (s.z.a, [1, 19])
+// CHECK-NEXT: 0 OUT (s.z.b, [2, 0])
+// CHECK-NEXT: 1 IN (s, [2, 0])
+// CHECK-NEXT: 1 IN (s.x, [2, 0])
+// CHECK-NEXT: 1 IN (s.y, [2, 0])
+// CHECK-NEXT: 1 IN (s.z, [2, 0])
+// CHECK-NEXT: 1 IN (s.z.a, [2, 0])
+// CHECK-NEXT: 1 IN (s.z.b, [2, 0])
+// CHECK-NEXT: 1 OUT (global_var, [1, 14])
+// CHECK-NEXT: 1 OUT (s, [2, 0])
+// CHECK-NEXT: 1 OUT (s.x, [2, 0])
+// CHECK-NEXT: 1 OUT (s.y, [2, 0])
+// CHECK-NEXT: 1 OUT (s.z, [2, 0])
+// CHECK-NEXT: 1 OUT (s.z.a, [1, 19])
+// CHECK-NEXT: 1 OUT (s.z.b, [2, 0])
+// CHECK-NEXT: 2 OUT (s, [2, 0])
+// CHECK-NEXT: 2 OUT (s.x, [2, 0])
+// CHECK-NEXT: 2 OUT (s.y, [2, 0])
+// CHECK-NEXT: 2 OUT (s.z, [2, 0])
+// CHECK-NEXT: 2 OUT (s.z.a, [2, 0])
+// CHECK-NEXT: 2 OUT (s.z.b, [2, 0])
+
+} // namespace struct_ptr
+
+void lhs_in_parantheses(int a, int b) {
+ (a, b) = 5;
+}
+// CHECK: GEN sets: blockid (varname [blockid, elementid])
+// CHECK-NEXT: 2 (a, [2, 0])
+// CHECK-NEXT: 2 (b, [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 (a, [2, 0])
+// CHECK-NEXT: 0 IN (b, [2, 0])
+// CHECK-NEXT: 0 OUT (a, [2, 0])
+// CHECK-NEXT: 0 OUT (b, [2, 0])
+// CHECK-NEXT: 1 IN (a, [2, 0])
+// CHECK-NEXT: 1 IN (b, [2, 0])
+// CHECK-NEXT: 1 OUT (a, [2, 0])
+// CHECK-NEXT: 1 OUT (b, [2, 0])
+// CHECK-NEXT: 2 OUT (a, [2, 0])
+// CHECK-NEXT: 2 OUT (b, [2, 0])
+
+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])
+// CHECK-NEXT: 2 (b, [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 (a, [2, 0])
+// CHECK-NEXT: 0 IN (b, [2, 0])
+// CHECK-NEXT: 0 OUT (a, [2, 0])
+// CHECK-NEXT: 0 OUT (b, [2, 0])
+// CHECK-NEXT: 1 IN (a, [2, 0])
+// CHECK-NEXT: 1 IN (b, [2, 0])
+// CHECK-NEXT: 1 OUT (a, [2, 0])
+// CHECK-NEXT: 1 OUT (b, [2, 0])
+// CHECK-NEXT: 2 OUT (a, [2, 0])
+// CHECK-NEXT: 2 OUT (b, [2, 0])
+
+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])
+// CHECK-NEXT: 2 (b, [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 (a, [2, 0])
+// CHECK-NEXT: 0 IN (b, [2, 0])
+// CHECK-NEXT: 0 OUT (a, [2, 0])
+// CHECK-NEXT: 0 OUT (b, [2, 0])
+// CHECK-NEXT: 1 IN (a, [2, 0])
+// CHECK-NEXT: 1 IN (b, [2, 0])
+// CHECK-NEXT: 1 OUT (a, [2, 0])
+// CHECK-NEXT: 1 OUT (b, [2, 0])
+// CHECK-NEXT: 2 OUT (a, [2, 0])
+// CHECK-NEXT: 2 OUT (b, [2, 0])
+
+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])
+// CHECK-NEXT: 5 (b, [5, 0])
+// 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])
+// CHECK-NEXT: 0 IN (b, [5, 0])
+// CHECK-NEXT: 0 OUT (a, [5, 0])
+// CHECK-NEXT: 0 OUT (b, [5, 0])
+// CHECK-NEXT: 1 IN (a, [5, 0])
+// CHECK-NEXT: 1 IN (b, [5, 0])
+// CHECK-NEXT: 1 OUT (a, [5, 0])
+// CHECK-NEXT: 1 OUT (b, [5, 0])
+// CHECK-NEXT: 2 IN (a, [5, 0])
+// CHECK-NEXT: 2 IN (b, [5, 0])
+// CHECK-NEXT: 2 OUT (a, [5, 0])
+// CHECK-NEXT: 2 OUT (b, [5, 0])
+// CHECK-NEXT: 3 IN (a, [5, 0])
+// CHECK-NEXT: 3 IN (b, [5, 0])
+// CHECK-NEXT: 3 OUT (a, [5, 0])
+// CHECK-NEXT: 3 OUT (b, [5, 0])
+// CHECK-NEXT: 4 IN (a, [5, 0])
+// CHECK-NEXT: 4 IN (b, [5, 0])
+// CHECK-NEXT: 4 OUT (a, [5, 0])
+// CHECK-NEXT: 4 OUT (b, [5, 0])
+// CHECK-NEXT: 5 OUT (a, [5, 0])
+// CHECK-NEXT: 5 OUT (b, [5, 0])
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(), &AC->getASTContext());
+ 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(), &AC->getASTContext());
+ 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(), &AC->getASTContext());
+ 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,276 @@
+//===--- 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/ASTMatchers/ASTMatchers.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"
+
+using namespace clang;
+using namespace ReachingDefinitionsDetail;
+using DefinitionKind = Definition::DefinitionKind;
+
+void ReachingDefinitionsCalculator::anchor() {}
+
+using VarSet = llvm::SmallPtrSet<const VarDecl *, 5>;
+
+void insertToGenSet(GenSet &Gen, const VarDecl *Var, FieldChainTy FieldChain,
+ CFGBlock::ConstCFGElementRef E, DefinitionKind Kind) {
+ // 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;
+
+ Gen.emplace(Var, FieldChain, E, Kind);
+ if (const RecordDecl *R = FieldChain.back()->getType()->getAsRecordDecl()) {
+ for (const FieldDecl *Field : R->fields()) {
+ FieldChainTy Cpy = FieldChain;
+ Cpy.emplace_back(Field);
+ insertToGenSet(Gen, Var, Cpy, E, Kind);
+ }
+ }
+}
+
+void insertToGenSet(GenSet &Gen, const VarDecl *Var,
+ CFGBlock::ConstCFGElementRef E, DefinitionKind Kind) {
+ Gen.emplace(Var, E, Kind);
+ if (const RecordDecl *R = Var->getType()->getAsRecordDecl()) {
+ for (const FieldDecl *Field : R->fields()) {
+ insertToGenSet(Gen, Var, FieldChainTy({Field}), E, Kind);
+ }
+ }
+}
+
+void invalidateOnFunctionCall(const Decl *D, CFGBlock::ConstCFGElementRef E,
+ GenSet &Ret) {
+ const DeclContext *DC = D->getDeclContext();
+ while (DC) {
+ DC = DC->getPrimaryContext();
+ for (const Decl *Res : DC->decls())
+ if (const auto *VD = dyn_cast<VarDecl>(Res))
+ insertToGenSet(Ret, VD, E, DefinitionKind::Invalidation);
+ DC = DC->getParent();
+ }
+}
+
+LLVM_NODISCARD
+static GenSet getGenSetForCFGBlock(const Decl *D, const CFGBlock *B,
+ ASTContext *Context) {
+ if (B->empty())
+ return {};
+
+ using namespace ast_matchers;
+
+ GenSet Ret;
+
+ for (CFGBlock::ConstCFGElementRef E : B->rrefs()) {
+ if (E->getKind() != CFGElement::Kind::Statement)
+ continue;
+
+ const Stmt *S = E->castAs<CFGStmt>().getStmt();
+ assert(S);
+
+ // TODO: Moving an object?
+ // TODO: Method calls?
+ // TODO: Analyzing a method?
+ // TODO: What do you do with Objective.*???
+ //===------------------------------------------------------------------===//
+ {
+ // TODO: CXXOperatorCallExpr, as if a class' move or assignemnt operator.
+ auto AssignmentM =
+ binaryOperator(
+ isAssignmentOperator(),
+ hasLHS(anyOf(declRefExpr(to(varDecl().bind("var"))),
+ parenExpr().bind("paren"),
+ memberExpr(unless(hasAncestor(memberExpr())))
+ .bind("member"))))
+ .bind("assign");
+
+ auto Assignments = match(AssignmentM, *S, *Context);
+ if (!Assignments.empty()) {
+ for (const auto Assignment : Assignments) {
+ if (const auto *Var = Assignment.getNodeAs<VarDecl>("var"))
+ insertToGenSet(Ret, Var, E, DefinitionKind::Write);
+ if (const auto *Paren = Assignment.getNodeAs<ParenExpr>("paren")) {
+ // TODO
+ }
+ // 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.
+ if (const auto *Member = Assignment.getNodeAs<MemberExpr>("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());
+
+ insertToGenSet(
+ Ret, cast<VarDecl>(cast<DeclRefExpr>(NextBase)->getDecl()),
+ FieldChain, 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;
+
+ insertToGenSet(Ret, 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);
+
+ invalidateOnFunctionCall(D, E, Ret);
+ }
+ }
+ }
+
+ return Ret;
+}
+
+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;
+}
+
+void ReachingDefinitionsCalculator::init() {
+ for (const CFGBlock *B : *cfg) {
+ Gen[B] = getGenSetForCFGBlock(D, B, Context);
+ }
+
+ if (const auto *F = dyn_cast<FunctionDecl>(D)) {
+ for (const ParmVarDecl *Param : F->parameters()) {
+ insertToGenSet(Gen[&cfg->getEntry()], Param, {&cfg->getEntry(), 0},
+ Definition::DefinitionKind::Write);
+ }
+ }
+
+ 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,139 @@
+//===--- 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/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>;
+
+inline 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;
+}
+
+struct Definition {
+ enum DefinitionKind { Write, Invalidation };
+
+ static StringRef describeDefinitionKind(DefinitionKind K) {
+ switch (K) {
+ case Write:
+ return "write";
+ case Invalidation:
+ return "invalidation";
+ }
+ }
+
+ // TODO: Implicit parameters, such as captured fields, CXXThis etc?
+ const VarDecl *Var;
+ FieldChainTy FieldChain;
+
+ CFGBlock::ConstCFGElementRef E;
+ DefinitionKind Kind;
+
+ const CFGBlock *getCFGBlock() const { return E.getParent(); }
+
+ // (varname [blockid, elementid])
+ void dump() const {
+ llvm::errs() << "(" << Var->getNameAsString();
+
+ for (const FieldDecl *Field : FieldChain)
+ llvm::errs() << "." + Field->getNameAsString();
+
+ llvm::errs() << ", [" << getCFGBlock()->getIndexInCFG() << ", "
+ << E.getIndexInBlock() << "])";
+ }
+
+ Definition(const VarDecl *Var, FieldChainTy FieldChain,
+ CFGBlock::ConstCFGElementRef E, DefinitionKind Kind)
+ : Var(Var), FieldChain(std::move(FieldChain)), E(E), Kind(Kind) {}
+
+ Definition(const VarDecl *Var, CFGBlock::ConstCFGElementRef E,
+ DefinitionKind Kind)
+ : Definition(Var, /*FieldChain=*/{}, E, Kind) {}
+};
+
+struct VarLess {
+ bool operator()(Definition Lhs, Definition Rhs) {
+ return std::make_pair(Lhs.Var, Lhs.FieldChain) <
+ std::make_pair(Rhs.Var, Rhs.FieldChain);
+ }
+};
+
+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, VarLess>;
+using DefinitionSet = std::set<Definition, VarAndCFGElementLess>;
+
+} // end of namespace ReachingDefinitionsDetail
+
+class ReachingDefinitionsCalculator : public ManagedAnalysis {
+ virtual void anchor();
+
+public:
+ using GenSet = ReachingDefinitionsDetail::GenSet;
+ using DefinitionSet = ReachingDefinitionsDetail::DefinitionSet;
+
+ ReachingDefinitionsCalculator(const Decl *D, const CFG *cfg,
+ ASTContext *Context)
+ : cfg(cfg), Context(Context), 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;
+ ASTContext *Context;
+ const Decl *D;
+
+ 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
