Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h @@ -26,7 +26,7 @@ /// /// Widen the loop by invalidating anything that might be modified /// by the loop body in any iteration. -ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, +ProgramStateRef getWidenedLoopState(ProgramStateRef State, ASTContext &ASTCtx, const LocationContext *LCtx, unsigned BlockCount, const Stmt *LoopStmt); Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1551,8 +1551,9 @@ return; // Widen. const LocationContext *LCtx = Pred->getLocationContext(); - ProgramStateRef WidenedState = - getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term); + ProgramStateRef WidenedState = getWidenedLoopState(Pred->getState(), + AMgr.getASTContext(), + 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,35 +39,92 @@ } } +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 +changedByIncrementOrDecrement(StringRef NodeName) { + return unaryOperator( + anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts(expr().bind(NodeName)))); +} + +static internal::Matcher changeVariable() { + return anyOf(changedByIncrementOrDecrement("changedExpr"), + changedByAssignement("changedExpr"), callByRef("changedExpr"), + cxxNonConstCall("changedExpr")); +} + namespace clang { namespace ento { -ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, +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 getWidenedLoopState(ProgramStateRef State, ASTContext &ASTCtx, 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); + 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; } - return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt), - BlockCount, LCtx, true, nullptr, nullptr, - &ITraits); + 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); } } // end namespace ento Index: test/Analysis/loop-widening.c =================================================================== --- test/Analysis/loop-widening.c +++ /dev/null @@ -1,190 +0,0 @@ -// RUN: %clang_analyze_cc1 -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/loop-widening.cpp =================================================================== --- /dev/null +++ test/Analysis/loop-widening.cpp @@ -0,0 +1,290 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=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 +} + +void no_widen_pointer2() { + int a = 1; + int *p = &a; + for (int i = 0; i < 10; ++i) { + (*p)++; + } + clang_analyzer_warnIfReached(); // no-warning +} + +void no_widen_pointer3() { + int a = 1; + int *p = &a; + for (int i = 0; i < 10; ++i) { + *p = 2; + } + clang_analyzer_warnIfReached(); // no-warning +}