seaneveson updated this revision to Diff 36739.
seaneveson added a comment.
Updated to latest revision.
Change patch to widen all loops which do not exit.
Changed to widen on block entrance so the guard condition is accounted for
(thanks for the suggestion).
Updated tests to reflect changes.
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,159 @@
+// 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
+
+extern void clang_analyzer_eval(_Bool);
+extern 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) {}
+ clang_analyzer_eval(x == 1); // expected-warning {{TRUE}} // TODO?
+}
+
+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;
+ }
+}
+
+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) {
+ if (i >= 50) {
+ clang_analyzer_warnIfReached(); // no-warning
+ }
+ ++i;
+ }
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_false_after_loop() {
+ int i = 0;
+ while (i < 50) {
+ ++i;
+ }
+ if (i < 50) {
+ clang_analyzer_warnIfReached(); // no-warning
+ }
+ 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 // TODO
+ 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));
+ *h_ptr = 3;
+
+ 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); // expected-warning {{UNKNOWN}}
+ free(h_ptr);
+}
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,70 @@
+//===--- 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 Fix nested loops.
+ const StackFrameContext *STC = LCtx->getCurrentStackFrame();
+ MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
+ const unsigned NumRegions = 3;
+ const MemRegion *Regions[NumRegions] = {
+ MRMgr.getStackLocalsRegion(STC),
+ MRMgr.getStackArgumentsRegion(STC),
+ MRMgr.getGlobalsRegion()
+ };
+ RegionAndSymbolInvalidationTraits ITraits;
+ for (int RegionIndex = 0; RegionIndex < NumRegions; ++ RegionIndex) {
+ ITraits.setTrait(Regions[RegionIndex],
+ RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
+ }
+ return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
+ BlockCount, LCtx, false, 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 this is the last time it
+ // will be visited, 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))) {
+ 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
@@ -27,6 +27,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,7 @@
InlineLambdas = getBooleanOption("inline-lambdas", /*Default=*/true);
return InlineLambdas.getValue();
}
+
+bool AnalyzerOptions::shouldWidenLoops() {
+ return getBooleanOption("widen-loops", false);
+}
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,36 @@
+//===--- 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/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
+ 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,11 @@
/// 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
