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/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ cfe/trunk/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: cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt +++ cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt @@ -28,6 +28,7 @@ ExprEngineObjC.cpp FunctionSummary.cpp HTMLDiagnostics.cpp + LoopWidening.cpp MemRegion.cpp PathDiagnostic.cpp PlistDiagnostics.cpp Index: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ cfe/trunk/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" @@ -1395,8 +1396,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(Term) || isa(Term) || isa(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: cfe/trunk/lib/StaticAnalyzer/Core/LoopWidening.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopWidening.cpp +++ cfe/trunk/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(LoopStmt)->getCond(); + case Stmt::WhileStmtClass: + return cast(LoopStmt)->getCond(); + case Stmt::DoStmtClass: + return cast(LoopStmt)->getCond(); + } +} + +namespace clang { +namespace ento { + +ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, + const LocationContext *LCtx, + unsigned BlockCount, const Stmt *LoopStmt) { + + assert(isa(LoopStmt) || isa(LoopStmt) || + isa(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: 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/analyzer-config.cpp =================================================================== --- cfe/trunk/test/Analysis/analyzer-config.cpp +++ cfe/trunk/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: 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); // 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}} +}