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 @@ -380,6 +380,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 @@ -1540,7 +1540,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)))) @@ -1548,7 +1549,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,14 @@ //===----------------------------------------------------------------------===// #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" 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 +38,94 @@ } } +/// Return the loops body Stmt or NULL if LoopStmt is not a loop +static const Stmt *getLoopBody(const Stmt *LoopStmt) { + switch (LoopStmt->getStmtClass()) { + default: + return nullptr; + case Stmt::ForStmtClass: + return cast(LoopStmt)->getBody(); + case Stmt::WhileStmtClass: + return cast(LoopStmt)->getBody(); + case Stmt::DoStmtClass: + return cast(LoopStmt)->getBody(); + } +} + namespace clang { namespace ento { +static internal::Matcher callByRef(StringRef NodeName) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl().bind(NodeName))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher changeVariable() { + return anyOf( + unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts( + declRefExpr(to(varDecl().bind("changedVar")))))), + binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="), + hasOperatorName("/="), hasOperatorName("*="), + hasOperatorName("-=")), + hasLHS(ignoringParenImpCasts( + declRefExpr(to(varDecl().bind("changedVar")))))), + callByRef("changedVar"), + cxxMemberCallExpr( + anyOf(on(declRefExpr(to(varDecl().bind("changedDecl")))), + unless(callee(cxxMethodDecl(isConst()))))), + cxxOperatorCallExpr(hasArgument(0, ignoringImpCasts(declRefExpr(to( + varDecl().bind("changedVar"))))), + unless(callee(cxxMethodDecl(isConst()))))); +} + +static internal::Matcher hasPointerStmt() { + return hasDescendant(declRefExpr( + to(varDecl(anyOf(hasType(isAnyPointer()), hasType(arrayType())))))); +} + +bool shouldWiden(const Stmt *LoopStmt, ASTContext &ASTCtx) { + auto Matches = match(hasPointerStmt(), *LoopStmt, ASTCtx); + if (!Matches.empty()) + return false; + + return true; +} + +ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State, + ASTContext &ASTCtx, + const LocationContext *LCtx, + unsigned BlockCount, + const Stmt *LoopStmt) { + if (!shouldWiden(LoopStmt, ASTCtx)) + return State; + + std::set LoopVars; + auto Matches = + match(findAll(varDecl().bind("varDecl")), *getLoopBody(LoopStmt), ASTCtx); + for (auto &Match : Matches) + LoopVars.insert(Match.getNodeAs("varDecl")); + + std::set RegionsToInvalidate; + Matches = match(findAll(changeVariable()), *LoopStmt, ASTCtx); + for (auto &Match : Matches) { + auto VD = Match.getNodeAs("changedVar"); + if (!VD || LoopVars.find(VD) != LoopVars.end()) + continue; + if (auto Region = State->getLValue(VD, LCtx).getAsRegion()) + RegionsToInvalidate.insert(Region); + } + std::vector 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