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 variable_bound_exiting_loops_widened(int x) {
+ int i = 0;
+ int t = 1;
+ while (i < x) {
+ ++i;
+ }
+ clang_analyzer_eval(t == 1); // expected-warning {{TRUE}} // expected-warning {{UNKNOWN}}
+}
+
+void nested_loop_outer_widen() {
+ 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 nested_loop_inner_widen() {
+ 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}}
+}
Index: test/Analysis/analyzer-config.cpp
===================================================================
--- test/Analysis/analyzer-config.cpp
+++ test/Analysis/analyzer-config.cpp
@@ -36,5 +36,6 @@
// 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 = 19
+// CHECK-NEXT: num-entries = 20
Index: test/Analysis/analyzer-config.c
===================================================================
--- test/Analysis/analyzer-config.c
+++ 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: lib/StaticAnalyzer/Core/LoopWidening.cpp
===================================================================
--- lib/StaticAnalyzer/Core/LoopWidening.cpp
+++ lib/StaticAnalyzer/Core/LoopWidening.cpp
@@ -0,0 +1,68 @@
+//===--- LoopWidening.cpp - 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 file contains functions which are used to widen loops. A loop may be
+/// widened to approximate the exit state(s), without analyzing every
+/// iteration. The widening is done by invalidating anything which might be
+/// modified by the body of the loop.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
+
+using namespace clang;
+using namespace ento;
+
+/// Return the loops condition Stmt or NULL if LoopStmt is not a loop
+static const Expr *getLoopCondition(const Stmt *LoopStmt) {
+ switch (LoopStmt->getStmtClass()) {
+ default:
+ return NULL;
+ case Stmt::ForStmtClass:
+ return cast<ForStmt>(LoopStmt)->getCond();
+ case Stmt::WhileStmtClass:
+ return cast<WhileStmt>(LoopStmt)->getCond();
+ case Stmt::DoStmtClass:
+ return cast<DoStmt>(LoopStmt)->getCond();
+ }
+}
+
+namespace clang {
+namespace ento {
+
+ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
+ const LocationContext *LCtx,
+ unsigned BlockCount, const Stmt *LoopStmt) {
+
+ assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
+ isa<DoStmt>(LoopStmt));
+
+ // Invalidate values in the current state.
+ // TODO Make this more conservative by only invalidating values that might
+ // be modified by the body of the loop.
+ // TODO Nested loops are currently widened as a result of the invalidation
+ // being so inprecise. When the invalidation is improved, the handling
+ // of nested loops will also need to be improved.
+ const StackFrameContext *STC = LCtx->getCurrentStackFrame();
+ MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
+ const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
+ MRMgr.getStackArgumentsRegion(STC),
+ MRMgr.getGlobalsRegion()};
+ RegionAndSymbolInvalidationTraits ITraits;
+ for (auto *Region : Regions) {
+ ITraits.setTrait(Region,
+ RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
+ }
+ return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
+ BlockCount, LCtx, true, nullptr, nullptr,
+ &ITraits);
+}
+
+} // end namespace ento
+} // end namespace clang
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -26,6 +26,7 @@
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
#include "llvm/ADT/ImmutableList.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/raw_ostream.h"
@@ -1391,8 +1392,25 @@
ExplodedNode *Pred) {
PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
+ // If this block is terminated by a loop and it has already been visited the
+ // maximum number of times, widen the loop.
+ unsigned int BlockCount = nodeBuilder.getContext().blockCount();
+ if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
+ AMgr.options.shouldWidenLoops()) {
+ const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
+ if (!(Term &&
+ (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
+ return;
+ // Widen.
+ const LocationContext *LCtx = Pred->getLocationContext();
+ ProgramStateRef WidenedState =
+ getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
+ nodeBuilder.generateNode(WidenedState, Pred);
+ return;
+ }
+
// FIXME: Refactor this into a checker.
- if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
+ if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
const ExplodedNode *Sink =
nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
Index: lib/StaticAnalyzer/Core/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Core/CMakeLists.txt
+++ lib/StaticAnalyzer/Core/CMakeLists.txt
@@ -28,6 +28,7 @@
ExprEngineObjC.cpp
FunctionSummary.cpp
HTMLDiagnostics.cpp
+ LoopWidening.cpp
MemRegion.cpp
PathDiagnostic.cpp
PlistDiagnostics.cpp
Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
===================================================================
--- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -338,3 +338,9 @@
InlineLambdas = getBooleanOption("inline-lambdas", /*Default=*/true);
return InlineLambdas.getValue();
}
+
+bool AnalyzerOptions::shouldWidenLoops() {
+ if (!WidenLoops.hasValue())
+ WidenLoops = getBooleanOption("widen-loops", /*Default=*/false);
+ return WidenLoops.getValue();
+}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
+++ 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: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
===================================================================
--- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
+++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
@@ -262,6 +262,9 @@
/// \sa shouldInlineLambdas
Optional<bool> InlineLambdas;
+ /// \sa shouldWidenLoops
+ Optional<bool> 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),
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
