Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
seaneveson updated this revision to Diff 38717.
seaneveson added a comment.
Updated to latest revision
http://reviews.llvm.org/D12358
Files:
include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
lib/StaticAnalyzer/Core/CMakeLists.txt
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/LoopWidening.cpp
test/Analysis/analyzer-config.c
test/Analysis/analyzer-config.cpp
test/Analysis/loop-widening.c
Index: test/Analysis/loop-widening.c
===
--- /dev/null
+++ test/Analysis/loop-widening.c
@@ -0,0 +1,190 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=true -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached();
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+void free(void *);
+
+void loop_which_iterates_limit_times_not_widened() {
+ int i;
+ int x = 1;
+ // Check loop isn't widened by checking x isn't invalidated
+ for (i = 0; i < 1; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 2; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 3; ++i) {}
+ // FIXME loss of precision as a result of evaluating the widened loop body
+ // *instead* of the last iteration.
+ clang_analyzer_eval(x == 1); // expected-warning {{UNKNOWN}}
+}
+
+int a_global;
+
+void loop_evaluated_before_widening() {
+ int i;
+ a_global = 1;
+ for (i = 0; i < 10; ++i) {
+if (i == 2) {
+ // True before widening then unknown after.
+ clang_analyzer_eval(a_global == 1); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}}
+}
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void warnings_after_loop() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void for_loop_exits() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void while_loop_exits() {
+ int i = 0;
+ while (i < 10) {++i;}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void do_while_loop_exits() {
+ int i = 0;
+ do {++i;} while (i < 10);
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void loop_body_is_widened() {
+ int i = 0;
+ while (i < 100) {
+if (i > 10) {
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void invariably_infinite_loop() {
+ int i = 0;
+ while (1) { ++i; }
+ clang_analyzer_warnIfReached(); // no-warning
+}
+
+void invariably_infinite_break_loop() {
+ int i = 0;
+ while (1) {
+++i;
+int x = 1;
+if (!x) break;
+ }
+ clang_analyzer_warnIfReached(); // no-warning
+}
+
+void reachable_break_loop() {
+ int i = 0;
+ while (1) {
+++i;
+if (i == 100) break;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_true_in_loop() {
+ int i = 0;
+ while (i < 50) {
+clang_analyzer_eval(i < 50); // expected-warning {{TRUE}}
+++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_false_after_loop() {
+ int i = 0;
+ while (i < 50) {
+++i;
+ }
+ clang_analyzer_eval(i >= 50); // expected-warning {{TRUE}}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void multiple_exit_test() {
+ int x = 0;
+ int i = 0;
+ while (i < 50) {
+if (x) {
+ i = 10;
+ break;
+}
+++i;
+ }
+ // Reachable by 'normal' exit
+ if (i == 50) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ // Reachable by break point
+ if (i == 10) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ // Not reachable
+ if (i < 10) clang_analyzer_warnIfReached(); // no-warning
+ if (i > 10 && i < 50) clang_analyzer_warnIfReached(); // no-warning
+}
+
+void pointer_doesnt_leak_from_loop() {
+ int *h_ptr = (int *) malloc(sizeof(int));
+ for (int i = 0; i < 2; ++i) {}
+ for (int i = 0; i < 10; ++i) {} // no-warning
+ free(h_ptr);
+}
+
+int g_global;
+
+void unknown_after_loop(int s_arg) {
+ g_global = 0;
+ s_arg = 1;
+ int s_local = 2;
+ int *h_ptr = malloc(sizeof(int));
+
+ for (int i = 0; i < 10; ++i) {}
+
+ clang_analyzer_eval(g_global); // expected-warning {{UNKNOWN}}
+ clang_analyzer_eval(s_arg); // expected-warning {{UNKNOWN}}
+ clang_analyzer_eval(s_local); // expected-warning {{UNKNOWN}}
+ clang_analyzer_eval(h_ptr == 0); // expected-warning {{UNKNOWN}}
+ free(h_ptr);
+}
+
+void variable_bound_exiting_loops_widened(int x) {
+ int i = 0;
+ int t = 1;
+ while (i < x) {
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
This revision was automatically updated to reflect the committed changes.
Closed by commit rL251621: [Analyzer] Widening loops which do not exit
(authored by seaneveson).
Changed prior to commit:
http://reviews.llvm.org/D12358?vs=38717=38718#toc
Repository:
rL LLVM
http://reviews.llvm.org/D12358
Files:
cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt
cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp
cfe/trunk/lib/StaticAnalyzer/Core/LoopWidening.cpp
cfe/trunk/test/Analysis/analyzer-config.c
cfe/trunk/test/Analysis/analyzer-config.cpp
cfe/trunk/test/Analysis/loop-widening.c
Index: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
===
--- cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
+++ cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
@@ -262,6 +262,9 @@
/// \sa shouldInlineLambdas
Optional InlineLambdas;
+ /// \sa shouldWidenLoops
+ Optional WidenLoops;
+
/// A helper function that retrieves option for a given full-qualified
/// checker name.
/// Options for checkers can be specified via 'analyzer-config' command-line
@@ -526,6 +529,10 @@
/// generated each time a LambdaExpr is visited.
bool shouldInlineLambdas();
+ /// Returns true if the analysis should try to widen loops.
+ /// This is controlled by the 'widen-loops' config option.
+ bool shouldWidenLoops();
+
public:
AnalyzerOptions() :
AnalysisStoreOpt(RegionStoreModel),
Index: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
===
--- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
+++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
@@ -0,0 +1,37 @@
+//===--- LoopWidening.h - Instruction class definition --*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+///
+/// This header contains the declarations of functions which are used to widen
+/// loops which do not otherwise exit. The widening is done by invalidating
+/// anything which might be modified by the body of the loop.
+///
+//===--===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPWIDENING_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPWIDENING_H
+
+#include "clang/Analysis/CFG.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+
+namespace clang {
+namespace ento {
+
+/// \brief Get the states that result from widening the loop.
+///
+/// Widen the loop by invalidating anything that might be modified
+/// by the loop body in any iteration.
+ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
+const LocationContext *LCtx,
+unsigned BlockCount,
+const Stmt *LoopStmt);
+
+} // end namespace ento
+} // end namespace clang
+
+#endif
Index: cfe/trunk/test/Analysis/analyzer-config.c
===
--- cfe/trunk/test/Analysis/analyzer-config.c
+++ cfe/trunk/test/Analysis/analyzer-config.c
@@ -25,6 +25,7 @@
// CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
// CHECK-NEXT: mode = deep
// CHECK-NEXT: region-store-small-struct-limit = 2
+// CHECK-NEXT: widen-loops = false
// CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 14
+// CHECK-NEXT: num-entries = 15
Index: cfe/trunk/test/Analysis/loop-widening.c
===
--- cfe/trunk/test/Analysis/loop-widening.c
+++ cfe/trunk/test/Analysis/loop-widening.c
@@ -0,0 +1,190 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=true -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached();
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+void free(void *);
+
+void loop_which_iterates_limit_times_not_widened() {
+ int i;
+ int x = 1;
+ // Check loop isn't widened by checking x isn't invalidated
+ for (i = 0; i < 1; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 2; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 3; ++i) {}
+ // FIXME loss of precision as a result of evaluating the widened loop body
+ // *instead* of the last iteration.
+ clang_analyzer_eval(x == 1); //
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
dcoughlin accepted this revision. dcoughlin added a comment. LGTM. Please commit. Thanks for tackling this, Sean! http://reviews.llvm.org/D12358 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
seaneveson updated this revision to Diff 38519.
seaneveson added a comment.
Removed checking for already exited loops
Addressed Comments
http://reviews.llvm.org/D12358
Files:
include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
lib/StaticAnalyzer/Core/CMakeLists.txt
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/LoopWidening.cpp
test/Analysis/analyzer-config.c
test/Analysis/analyzer-config.cpp
test/Analysis/loop-widening.c
Index: test/Analysis/loop-widening.c
===
--- test/Analysis/loop-widening.c
+++ test/Analysis/loop-widening.c
@@ -0,0 +1,190 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=true -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached();
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+void free(void *);
+
+void loop_which_iterates_limit_times_not_widened() {
+ int i;
+ int x = 1;
+ // Check loop isn't widened by checking x isn't invalidated
+ for (i = 0; i < 1; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 2; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 3; ++i) {}
+ // FIXME loss of precision as a result of evaluating the widened loop body
+ // *instead* of the last iteration.
+ clang_analyzer_eval(x == 1); // expected-warning {{UNKNOWN}}
+}
+
+int a_global;
+
+void loop_evaluated_before_widening() {
+ int i;
+ a_global = 1;
+ for (i = 0; i < 10; ++i) {
+if (i == 2) {
+ // True before widening then unknown after.
+ clang_analyzer_eval(a_global == 1); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}}
+}
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void warnings_after_loop() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void for_loop_exits() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void while_loop_exits() {
+ int i = 0;
+ while (i < 10) {++i;}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void do_while_loop_exits() {
+ int i = 0;
+ do {++i;} while (i < 10);
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void loop_body_is_widened() {
+ int i = 0;
+ while (i < 100) {
+if (i > 10) {
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void invariably_infinite_loop() {
+ int i = 0;
+ while (1) { ++i; }
+ clang_analyzer_warnIfReached(); // no-warning
+}
+
+void invariably_infinite_break_loop() {
+ int i = 0;
+ while (1) {
+++i;
+int x = 1;
+if (!x) break;
+ }
+ clang_analyzer_warnIfReached(); // no-warning
+}
+
+void reachable_break_loop() {
+ int i = 0;
+ while (1) {
+++i;
+if (i == 100) break;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_true_in_loop() {
+ int i = 0;
+ while (i < 50) {
+clang_analyzer_eval(i < 50); // expected-warning {{TRUE}}
+++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_false_after_loop() {
+ int i = 0;
+ while (i < 50) {
+++i;
+ }
+ clang_analyzer_eval(i >= 50); // expected-warning {{TRUE}}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void multiple_exit_test() {
+ int x = 0;
+ int i = 0;
+ while (i < 50) {
+if (x) {
+ i = 10;
+ break;
+}
+++i;
+ }
+ // Reachable by 'normal' exit
+ if (i == 50) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ // Reachable by break point
+ if (i == 10) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ // Not reachable
+ if (i < 10) clang_analyzer_warnIfReached(); // no-warning
+ if (i > 10 && i < 50) clang_analyzer_warnIfReached(); // no-warning
+}
+
+void pointer_doesnt_leak_from_loop() {
+ int *h_ptr = (int *) malloc(sizeof(int));
+ for (int i = 0; i < 2; ++i) {}
+ for (int i = 0; i < 10; ++i) {} // no-warning
+ free(h_ptr);
+}
+
+int g_global;
+
+void unknown_after_loop(int s_arg) {
+ g_global = 0;
+ s_arg = 1;
+ int s_local = 2;
+ int *h_ptr = malloc(sizeof(int));
+
+ for (int i = 0; i < 10; ++i) {}
+
+ clang_analyzer_eval(g_global); // expected-warning {{UNKNOWN}}
+ clang_analyzer_eval(s_arg); // expected-warning {{UNKNOWN}}
+ clang_analyzer_eval(s_local); // expected-warning {{UNKNOWN}}
+ clang_analyzer_eval(h_ptr == 0); // expected-warning {{UNKNOWN}}
+ free(h_ptr);
+}
+
+void
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
seaneveson marked 5 inline comments as done.
Comment at: test/Analysis/loop-widening.c:160
@@ +159,3 @@
+void variable_bound_exiting_loops_widened(int x) {
+ int i = 0;
+ int t = 1;
The inner loop will now be widened in the first example test, which
'coincidentally' widens the outer loop as well. This means this text now passes.
http://reviews.llvm.org/D12358
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
seaneveson marked an inline comment as done.
seaneveson added a comment.
Hi Devin,
Sorry it also took me so long to get back to you.
Comment at: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h:266
@@ +265,3 @@
+ /// \sa shouldWidenLoops
+ bool WidenLoops;
+
dcoughlin wrote:
> Is this field used?
No. Thanks I'll fix that.
Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:1407
@@ +1406,3 @@
+const CFGBlock *Following = getBlockAfterLoop(L.getDst());
+if (Following && nodeBuilder.getContext().Eng.blockWasVisited(Following))
+ return;
dcoughlin wrote:
> What is the purpose of checking whether the block has already been visited by
> some other path?
>
> If I understand correctly, this will stop the analyzer from widening before
> the "last" iteration through the loop and so will result in a sink after that
> iteration. What this means is that we will never explore the code beyond the
> loop in the widened state -- but isn't this the whole point of the widening?
>
> So, for example, in your `variable_bound_exiting_loops_not_widened()` test,
> don't we want the clang_analyzer_eval() statement after the loop to be
> symbolically executed on 4 separate paths? That is, once when i is 0, once
> when i is 1, once when i is 2 and once when i is $conj_i$ + 1 where $conj_i$
> is the value conjured for i when widening.
>
> Also, in general, analysis of one path should not depend at all on whether
> another path has been explored. This is because we want the analyzer to be
> free choose different strategies about path exploration (e.g., BFS vs. DFS,
> prioritizing some paths over others, etc.) without changing the issues
> reported on along any given path. For this reason, I don't think we
> necessarily want to track and expose `blockWasVisited()` on CoreEngine or use
> this to determine when to permit a sink.
>
>
I was trying to avoid doing unnecessary invalidation, where the variable bound
loop had already exited. I suppose this won’t be a concern when the
invalidation is improved. If everyone is happy for loops that have already
exited to be widened then I will remove the related changes.
Comment at: lib/StaticAnalyzer/Core/LoopWidening.cpp:98
@@ +97,3 @@
+ RegionAndSymbolInvalidationTraits ITraits;
+ for (int RegionIndex = 0; RegionIndex < NumRegions; ++ RegionIndex) {
+ITraits.setTrait(Regions[RegionIndex],
dcoughlin wrote:
> I get a warning here about comparing a signed int (RegionIndex) to an
> unsigned (NumRegions).
>
> I think you can avoid this and simplify things by using a range-based for
> loop:
> ```
> const MemRegion *Regions[] = {
> ...
> };
> RegionAndSymbolInvalidationTraits ITraits;
> for (auto *Region : Regions) {
> ...
> }
> ```
Will do. Thanks.
http://reviews.llvm.org/D12358
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
dcoughlin added a comment.
Hi Sean,
Sorry it took me so long to get back to you.
Comment at: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h:266
@@ +265,3 @@
+ /// \sa shouldWidenLoops
+ bool WidenLoops;
+
Is this field used?
Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:1407
@@ +1406,3 @@
+const CFGBlock *Following = getBlockAfterLoop(L.getDst());
+if (Following && nodeBuilder.getContext().Eng.blockWasVisited(Following))
+ return;
What is the purpose of checking whether the block has already been visited by
some other path?
If I understand correctly, this will stop the analyzer from widening before the
"last" iteration through the loop and so will result in a sink after that
iteration. What this means is that we will never explore the code beyond the
loop in the widened state -- but isn't this the whole point of the widening?
So, for example, in your `variable_bound_exiting_loops_not_widened()` test,
don't we want the clang_analyzer_eval() statement after the loop to be
symbolically executed on 4 separate paths? That is, once when i is 0, once when
i is 1, once when i is 2 and once when i is $conj_i$ + 1 where $conj_i$ is the
value conjured for i when widening.
Also, in general, analysis of one path should not depend at all on whether
another path has been explored. This is because we want the analyzer to be free
choose different strategies about path exploration (e.g., BFS vs. DFS,
prioritizing some paths over others, etc.) without changing the issues reported
on along any given path. For this reason, I don't think we necessarily want to
track and expose `blockWasVisited()` on CoreEngine or use this to determine
when to permit a sink.
Comment at: lib/StaticAnalyzer/Core/LoopWidening.cpp:98
@@ +97,3 @@
+ RegionAndSymbolInvalidationTraits ITraits;
+ for (int RegionIndex = 0; RegionIndex < NumRegions; ++ RegionIndex) {
+ITraits.setTrait(Regions[RegionIndex],
I get a warning here about comparing a signed int (RegionIndex) to an unsigned
(NumRegions).
I think you can avoid this and simplify things by using a range-based for loop:
```
const MemRegion *Regions[] = {
...
};
RegionAndSymbolInvalidationTraits ITraits;
for (auto *Region : Regions) {
...
}
```
http://reviews.llvm.org/D12358
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
seaneveson marked 3 inline comments as done.
seaneveson added a comment.
In http://reviews.llvm.org/D12358#266391, @dcoughlin wrote:
> I think this is an acceptable loss of precision because, in general, it is
> unlikely that a concrete-bounded loop will be executed *exactly*
> maxBlockVisitOnPath times. You could add special syntactic checks to try to
> detect this, but I think it is unlikely to make much different in practice.
I agree.
The problem can be solved by executing the widened state after the last
iteration, rather than instead of it. This can only really be done by changing
the max block visit approach. This needs to be done in the future in order to
support nested loops. This precision issue could also be resolved at that time.
Comment at: include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h:84
@@ +83,3 @@
+ /// The blocks that have been visited during analysis
+ llvm::DenseSet blocksVisited;
+
The BlockCount is specific to the path of analysis, so it can't be used to
check if a loop has been exited before. I've added this set to store and
identify previously visited blocks. Is there a better way this can/could be
done?
Comment at: lib/StaticAnalyzer/Core/LoopWidening.cpp:65
@@ +64,3 @@
+ if (FalseBranch)
+return FalseBranch;
+ // If there isn't a false branch we still have to check for break points
Perfect, thanks.
Perhaps it could be changed back to false when the invalidation is better? Then
it could catch true positives e.g.
```
int *a = new int[10]
for (int i = 0; i < 100; ++i) {
if (i > 90)
++a;
...
}
```
Comment at: test/Analysis/loop-widening.c:159
@@ +158,3 @@
+
+void variable_bound_exiting_loops_not_widened(int x) {
+ int i = 0;
Thank you for the example tests.
When an inner loop is widened, any outer loops are widened 'coincidentally'
since everything is invalidated. This means the second example test passes.
When an inner loop is not widened the outer loop will not be widened. This is
because a sink is generated when the max block count is reached the second time
through the outer loop. i.e.
```
for (i = 0; i < 10; i++) {
for (j = 0; j < 2; j++) {
// A sink is generated here on the second iteration of the outer loop,
// since this block was already visited twice (when i == 0).
...
}
}
// Never reach here
```
This means the first example test does not pass. I’ve added the tests with a
FIXME comment.
http://reviews.llvm.org/D12358
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
seaneveson updated this revision to Diff 37462.
seaneveson added a comment.
Set CausedByPointerEscape to true
Check if the loop has already been exited before widening
Changed tests to use void clang_analyze_eval(int)
Added variable bound loop tests
Added nested loop tests
http://reviews.llvm.org/D12358
Files:
include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
lib/StaticAnalyzer/Core/CMakeLists.txt
lib/StaticAnalyzer/Core/CoreEngine.cpp
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/LoopWidening.cpp
test/Analysis/analyzer-config.c
test/Analysis/analyzer-config.cpp
test/Analysis/loop-widening.c
Index: test/Analysis/loop-widening.c
===
--- test/Analysis/loop-widening.c
+++ test/Analysis/loop-widening.c
@@ -0,0 +1,202 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-store=region -analyzer-max-loop 4 -analyzer-config widen-loops=true -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached();
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+void free(void *);
+
+void loop_which_iterates_limit_times_not_widened() {
+ int i;
+ int x = 1;
+ // Check loop isn't widened by checking x isn't invalidated
+ for (i = 0; i < 1; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 2; ++i) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+ for (i = 0; i < 3; ++i) {}
+ // FIXME loss of precision as a result of evaluating the widened loop body
+ // *instead* of the last iteration.
+ clang_analyzer_eval(x == 1); // expected-warning {{UNKNOWN}}
+}
+
+int a_global;
+
+void loop_evaluated_before_widening() {
+ int i;
+ a_global = 1;
+ for (i = 0; i < 10; ++i) {
+if (i == 2) {
+ // True before widening then unknown after.
+ clang_analyzer_eval(a_global == 1); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}}
+}
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void warnings_after_loop() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void for_loop_exits() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void while_loop_exits() {
+ int i = 0;
+ while (i < 10) {++i;}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void do_while_loop_exits() {
+ int i = 0;
+ do {++i;} while (i < 10);
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void loop_body_is_widened() {
+ int i = 0;
+ while (i < 100) {
+if (i > 10) {
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void invariably_infinite_loop() {
+ int i = 0;
+ while (1) { ++i; }
+ clang_analyzer_warnIfReached(); // no-warning
+}
+
+void invariably_infinite_break_loop() {
+ int i = 0;
+ while (1) {
+++i;
+int x = 1;
+if (!x) break;
+ }
+ clang_analyzer_warnIfReached(); // no-warning
+}
+
+void reachable_break_loop() {
+ int i = 0;
+ while (1) {
+++i;
+if (i == 100) break;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_true_in_loop() {
+ int i = 0;
+ while (i < 50) {
+clang_analyzer_eval(i < 50); // expected-warning {{TRUE}}
+++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_false_after_loop() {
+ int i = 0;
+ while (i < 50) {
+++i;
+ }
+ clang_analyzer_eval(i >= 50); // expected-warning {{TRUE}}
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void multiple_exit_test() {
+ int x = 0;
+ int i = 0;
+ while (i < 50) {
+if (x) {
+ i = 10;
+ break;
+}
+++i;
+ }
+ // Reachable by 'normal' exit
+ if (i == 50) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ // Reachable by break point
+ if (i == 10) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ // Not reachable
+ if (i < 10) clang_analyzer_warnIfReached(); // no-warning
+ if (i > 10 && i < 50) clang_analyzer_warnIfReached(); // no-warning
+}
+
+void pointer_doesnt_leak_from_loop() {
+ int *h_ptr = (int *) malloc(sizeof(int));
+ for (int i = 0; i < 2; ++i) {}
+ for (int i = 0; i < 10; ++i) {} // no-warning
+ free(h_ptr);
+}
+
+int g_global;
+
+void unknown_after_loop(int s_arg) {
+ g_global = 0;
+ s_arg = 1;
+ int s_local = 2;
+ int *h_ptr = malloc(sizeof(int));
+
+ for (int i = 0; i < 10; ++i) {}
+
+ clang_analyzer_eval(g_global); // expected-warning
Re: [PATCH] D12358: [Analyzer] Widening loops which do not exit
dcoughlin added a comment.
> There is a loss of precision for loops that need to be executed exactly
> maxBlockVisitOnPath times, as the loop body is executed with the widened
> state instead of the last iteration.
I think this is an acceptable loss of precision because, in general, it is
unlikely that a concrete-bounded loop will be executed *exactly*
maxBlockVisitOnPath times. You could add special syntactic checks to try to
detect this, but I think it is unlikely to make much different in practice.
Comment at: lib/StaticAnalyzer/Core/LoopWidening.cpp:64
@@ +63,3 @@
+ }
+ return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
+ BlockCount, LCtx, false, nullptr,
Passing `true` here instead of `false` for `CausedByPointerEscape` should fix
the false alarm. This will cause invalidation to tell the MallocChecker that
the pointer has escaped and so shouldn't be treated as a leak.
Comment at: test/Analysis/loop-widening.c:3
@@ +2,3 @@
+
+extern void clang_analyzer_eval(_Bool);
+extern void clang_analyzer_warnIfReached();
There seems to be some weirdness when using `_Bool` in the prototype (vs. int).
It adds an extra `!= 0` to symbolic expressions, which can result in
clang_analyzer_eval() yielding `UNKNOWN` when using `extern void
clang_analyze_eval(int)` would print `TRUE` or `FALSE`.
We should track this down and fix it, but for now I think it is better to use
`extern void clang_analyze_eval(int)`.
Comment at: test/Analysis/loop-widening.c:13
@@ +12,3 @@
+ int x = 1;
+ // Check loop isn't widened by checking x isn't invalidated
+ for (i = 0; i < 1; ++i) {}
This is clever.
Comment at: test/Analysis/loop-widening.c:111
@@ +110,3 @@
+ }
+ if (i < 50) {
+clang_analyzer_warnIfReached(); // no-warning
After changing the `clang_analyzer_eval()` prototype to take an int, you can
use `clang_analyzer_eval(i >= 50); // expected-warning {{TRUE}}`.
Comment at: test/Analysis/loop-widening.c:158
@@ +157,3 @@
+ clang_analyzer_eval(h_ptr); // expected-warning {{UNKNOWN}}
+ free(h_ptr);
+}
I think it would be good to add some nested loop tests. For example:
```
void nested1() {
int i = 0, j = 0;
for (i = 0; i < 10; i++) {
clang_analyzer_eval(i < 10); // expected-warning {{TRUE}}
for (j = 0; j < 2; j++) {
clang_analyzer_eval(j < 2); // expected-warning {{TRUE}}
}
clang_analyzer_eval(j >= 2); // expected-warning {{TRUE}}
}
clang_analyzer_eval(i >= 10); // expected-warning {{TRUE}}
}
void nested2() {
int i = 0, j = 0;
for (i = 0; i < 2; i++) {
clang_analyzer_eval(i < 2); // expected-warning {{TRUE}}
for (j = 0; j < 10; j++) {
clang_analyzer_eval(j < 10); // expected-warning {{TRUE}}
}
clang_analyzer_eval(j >= 10); // expected-warning {{TRUE}}
}
clang_analyzer_eval(i >= 2); // expected-warning {{TRUE}}
}
```
http://reviews.llvm.org/D12358
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
