Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -278,6 +278,9 @@ /// \sa shouldWidenLoops Optional WidenLoops; + /// \sa shouldWidenLoops + Optional ConservativelyWidenLoops; + /// \sa shouldUnrollLoops Optional UnrollLoops; @@ -573,7 +576,12 @@ /// This is controlled by the 'widen-loops' config option. bool shouldWidenLoops(); - /// Returns true if the analysis should try to unroll loops with known bounds. + /// Returns true if the analysis should try to widen loops in a conservative + /// manner (only widen loops which meets specific requirements). + /// This is controlled by the 'widen-loops-conservative' config option. + bool shouldConservativelyWidenLoops(); + + /// Returns true if the analysis should try to unroll loops with known bounds. /// This is controlled by the 'unroll-loops' config option. bool shouldUnrollLoops(); Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h @@ -30,6 +30,12 @@ const LocationContext *LCtx, unsigned BlockCount, const Stmt *LoopStmt); +ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State, + ASTContext &ASTCtx, + const LocationContext *LCtx, + unsigned BlockCount, + const Stmt *LoopStmt); + } // end namespace ento } // end namespace clang Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -382,6 +382,12 @@ return WidenLoops.getValue(); } +bool AnalyzerOptions::shouldConservativelyWidenLoops() { + if (!ConservativelyWidenLoops.hasValue()) + ConservativelyWidenLoops = getBooleanOption("widen-loops-conservative", false); + return ConservativelyWidenLoops.getValue(); +} + bool AnalyzerOptions::shouldUnrollLoops() { if (!UnrollLoops.hasValue()) UnrollLoops = getBooleanOption("unroll-loops", /*Default=*/false); Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1543,7 +1543,8 @@ // maximum number of times, widen the loop. unsigned int BlockCount = nodeBuilder.getContext().blockCount(); if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && - AMgr.options.shouldWidenLoops()) { + (AMgr.options.shouldWidenLoops() || + AMgr.options.shouldConservativelyWidenLoops())) { const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); if (!(Term && (isa(Term) || isa(Term) || isa(Term)))) @@ -1551,7 +1552,11 @@ // Widen. const LocationContext *LCtx = Pred->getLocationContext(); ProgramStateRef WidenedState = - getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term); + AMgr.options.shouldConservativelyWidenLoops() + ? getConservativelyWidenedLoopState(Pred->getState(), + AMgr.getASTContext(), LCtx, + BlockCount, Term) + : getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term); nodeBuilder.generateNode(WidenedState, Pred); return; } Index: lib/StaticAnalyzer/Core/LoopWidening.cpp =================================================================== --- lib/StaticAnalyzer/Core/LoopWidening.cpp +++ lib/StaticAnalyzer/Core/LoopWidening.cpp @@ -15,9 +15,15 @@ //===----------------------------------------------------------------------===// #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h" +#include "clang/AST/AST.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" +#include "llvm/ADT/SmallSet.h" using namespace clang; using namespace ento; +using namespace clang::ast_matchers; /// Return the loops condition Stmt or NULL if LoopStmt is not a loop static const Expr *getLoopCondition(const Stmt *LoopStmt) { @@ -33,9 +39,95 @@ } } +static internal::Matcher callByRef(StringRef NodeName) { + return callExpr(forEachArgumentWithParam( + expr().bind(NodeName), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher cxxNonConstCall(StringRef NodeName) { + return anyOf(cxxMemberCallExpr(on(expr().bind("changedExpr")), + unless(callee(cxxMethodDecl(isConst())))), + cxxOperatorCallExpr( + hasArgument(0, ignoringImpCasts(expr().bind(NodeName))), + unless(callee(cxxMethodDecl(isConst()))))); +} +static internal::Matcher changedByAssignement(StringRef NodeName) { + return binaryOperator( + anyOf(hasOperatorName("="), hasOperatorName("+="), hasOperatorName("/="), + hasOperatorName("*="), hasOperatorName("-="), hasOperatorName("%="), + hasOperatorName("&="), hasOperatorName("|="), hasOperatorName("^="), + hasOperatorName("<<="), hasOperatorName(">>=")), + hasLHS(ignoringParenImpCasts(expr().bind(NodeName)))); +} +static internal::Matcher changedByIncrement(StringRef NodeName) { + return unaryOperator( + anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts(expr().bind(NodeName)))); +} + +static internal::Matcher changeVariable() { + return anyOf(changedByIncrement("changedExpr"), + changedByAssignement("changedExpr"), callByRef("changedExpr"), + cxxNonConstCall("changedExpr")); +} + namespace clang { namespace ento { +bool collectRegion(const Expr *E, + llvm::SmallSet &RegionsToInvalidate, + ProgramStateRef State, const LocationContext *LCtx) { + const VarDecl *VD = nullptr; + while (true) { + E = E->IgnoreParenImpCasts(); + switch (E->getStmtClass()) { + case Stmt::DeclRefExprClass: + VD = dyn_cast(cast(E)->getDecl()); + if (!VD || VD->getType()->isAnyPointerType() || + VD->getType()->isReferenceType()) + return false; + RegionsToInvalidate.insert(State->getLValue(VD, LCtx).getAsRegion()); + return true; + case Stmt::MemberExprClass: + E = cast(E)->getBase(); + break; + case Stmt::CXXDependentScopeMemberExprClass: + E = cast(E)->getBase(); + break; + case Stmt::ArraySubscriptExprClass: + E = cast(E)->getBase(); + break; + default: + return false; + } + } +} + +ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State, + ASTContext &ASTCtx, + const LocationContext *LCtx, + unsigned BlockCount, + const Stmt *LoopStmt) { + + llvm::SmallSet RegionsToInvalidate; + auto Matches = match(findAll(changeVariable()), *LoopStmt, ASTCtx); + for (auto &Match : Matches) { + auto E = Match.getNodeAs("changedExpr"); + bool Success = collectRegion(E, RegionsToInvalidate, State, LCtx); + if (!Success) + return State; + } + llvm::SmallVector Regions; + Regions.reserve(RegionsToInvalidate.size()); + for (auto E : RegionsToInvalidate) + Regions.push_back(E); + + return State->invalidateRegions(llvm::makeArrayRef(Regions), + getLoopCondition(LoopStmt), BlockCount, LCtx, + true); +} + ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, const LocationContext *LCtx, unsigned BlockCount, const Stmt *LoopStmt) { Index: test/Analysis/analyzer-config.c =================================================================== --- test/Analysis/analyzer-config.c +++ test/Analysis/analyzer-config.c @@ -30,5 +30,6 @@ // CHECK-NEXT: region-store-small-struct-limit = 2 // CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false +// CHECK-NEXT: widen-loops-conservative = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 19 +// CHECK-NEXT: num-entries = 20 Index: test/Analysis/analyzer-config.cpp =================================================================== --- test/Analysis/analyzer-config.cpp +++ test/Analysis/analyzer-config.cpp @@ -41,5 +41,6 @@ // CHECK-NEXT: region-store-small-struct-limit = 2 // CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false +// CHECK-NEXT: widen-loops-conservative = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 24 +// CHECK-NEXT: num-entries = 25 Index: test/Analysis/loop-widening-conservative.cpp =================================================================== --- /dev/null +++ test/Analysis/loop-widening-conservative.cpp @@ -0,0 +1,256 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops-conservative=true -verify -std=c++11 %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) {} + clang_analyzer_eval(x == 1); // expected-warning {{TRUE}} + for (i = 0; i < 4; ++i) {} + clang_analyzer_eval(x == 1); // expected-warning {{TRUE}} +} + +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}} + } + } + 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 invariably_infinite_loop() { + int i = 0; + for (;;) { ++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}} + // x is known to be 0, not reachable from break. + if (i == 10) clang_analyzer_warnIfReached(); // no-warning + // 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 = (int *) malloc(sizeof(int)); + int change_var = 1; + int nochange_var = 10; + for (int i = 0; i < 10; ++i) { + change_var *= nochange_var + nochange_var; + } + + clang_analyzer_eval(change_var == 1); // expected-warning {{UNKNOWN}} + clang_analyzer_eval(nochange_var == 10); // expected-warning {{TRUE}} + + clang_analyzer_eval(g_global); // expected-warning {{UNKNOWN}} + clang_analyzer_eval(s_arg == 1); // expected-warning {{TRUE}} + clang_analyzer_eval(s_local == 2); // expected-warning {{TRUE}} + clang_analyzer_eval(h_ptr == 0); // expected-warning {{UNKNOWN}} + free(h_ptr); +} + +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_warnIfReached();// no-warning +} + +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_warnIfReached(); // no-warning +} + +struct A +{ + A(int n):num(n){}; + int num; + void foo(); + void bar() const; + bool operator==(const A& other) const; + void operator=(const A& other); + void assign(const A& other){ num = other.num;} +}; + +void non_const_method_call() { + A a(42); + for (int i = 0; i < 10; ++i) { + a.foo(); + } + clang_analyzer_eval(a.num == 42); // expected-warning {{UNKNOWN}} +} + +void const_method_call() { + A a(42); + for (int i = 0; i < 10; ++i) { + a.bar(); + } + clang_analyzer_eval(a.num == 42); // expected-warning {{TRUE}} +} + +void knwon_method_call() { + A a(42); + A b(10); + for (int i = 0; i < 10; ++i) { + a.assign(b); + } + // Loss of precision. It could be worth to simulate the last iteration after + // widening as well. + clang_analyzer_eval(a.num == 10); // expected-warning {{UNKNOWN}} +} + +void non_const_operator_call() { + A a(42); + A b(10); + for (int i = 0; i < 10; ++i) { + a = b; + } + clang_analyzer_eval(a.num == 42); // expected-warning {{UNKNOWN}} +} + +void const_operator_call() { + A a(42); + A b(10); + for (int i = 0; i < 10; ++i) { + if(a == b) + continue; + } + clang_analyzer_eval(a.num == 42); // expected-warning {{TRUE}} +} + +void passByRef(int& n); +void passByConstRef(const int& n); + +void widen_escape() { + int n = 2; + for (int i = 0; i < 10; ++i) { + passByRef(n); + } + clang_analyzer_eval(n == 2); // expected-warning {{UNKNOWN}} +} + +void widen_const_escape() { + int n = 2; + for (int i = 0; i < 10; ++i) { + passByConstRef(n); + } + clang_analyzer_eval(n == 2); // expected-warning {{TRUE}} +} + +void widen_array() { + int arr[10]; + for (int i = 0; i < 10; ++i) {arr[i]=i;} + clang_analyzer_eval(arr[5] == 5); // expected-warning {{UNKNOWN}} +} + +void no_widen_pointer() { + int *r = nullptr; + for (int i = 0; i < 10; ++i) { + int *p; + p = r; + } + clang_analyzer_warnIfReached(); // no-warning +} +