Index: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -618,6 +618,9 @@ bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC); + bool replayWithWidening(ExplodedNode *N, const Stmt *LoopStmt, + unsigned BlockCount); + /// Models a trivial copy or move constructor or trivial assignment operator /// call with a simple bind. void performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred, Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h @@ -18,6 +18,7 @@ #include "clang/Analysis/CFG.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" namespace clang { namespace ento { @@ -36,6 +37,15 @@ unsigned BlockCount, const Stmt *LoopStmt); +bool isWidenedState(ProgramStateRef State); +const Stmt *isInsideOfALoop(ProgramStateRef State); + +ProgramStateRef updateWidenLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred); + +ProgramStateRef processWidenLoopEnd(const Stmt *LoopStmt, + ProgramStateRef State); + } // end namespace ento } // end namespace clang Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -524,6 +524,9 @@ if(AMgr.options.shouldUnrollLoops()) NewState = processLoopEnd(S, NewState); + if(AMgr.options.shouldConservativelyWidenLoops()) + NewState = processWidenLoopEnd(S, NewState); + LoopExit PP(S, Pred->getLocationContext()); Bldr.generateNode(PP, NewState, Pred); // Enqueue the new nodes onto the work list. @@ -1515,6 +1518,49 @@ return true; } +bool ExprEngine::replayWithWidening(ExplodedNode *N, const Stmt *LoopStmt, + unsigned BlockCount) { + while (N) { + N = N->pred_empty() ? nullptr : *(N->pred_begin()); + ProgramPoint L = N->getLocation(); + if (!L.getAs()) + continue; + if (Optional BE = L.getAs()) + if(BE->getBlock()->getTerminator() != LoopStmt) + continue; + break; + } + assert(N && "Reaching the root without finding the entrance of LoopStmt"); + // TODO: Clean up the unneeded nodes. + + // Build an Epsilon node from which we will restart the analyzes. + ProgramPoint NewNodeLoc = + EpsilonPoint(N->getLocationContext(), LoopStmt); + + // Note, changing the state ensures that we are not going to cache out. + ProgramStateRef NewNodeState = getConservativelyWidenedLoopState( + N->getState(), AMgr.getASTContext(), N->getLocationContext(), + BlockCount, LoopStmt); + + if(NewNodeState == N->getState()) + return false; + + bool IsNew = false; + ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); + // We cached out at this point. Caching out is common due to us backtracking + // from the inlined function, which might spawn several paths. + if (!IsNew) + return true; + + NewNode->addPredecessor(N, G); + + // Add the new node to the work list. + ExplodedNodeSet Dst(NewNode); + Engine.enqueue(Dst); + return true; +} + + /// Block entrance. (Update counters). void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, @@ -1539,40 +1585,28 @@ return; } - // 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() || - AMgr.options.shouldConservativelyWidenLoops())) { - const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); - if (!(Term && - (isa(Term) || isa(Term) || isa(Term)))) - return; - // Widen. - const LocationContext *LCtx = Pred->getLocationContext(); - ProgramStateRef WidenedState = - AMgr.options.shouldConservativelyWidenLoops() - ? getConservativelyWidenedLoopState(Pred->getState(), - AMgr.getASTContext(), LCtx, - BlockCount, Term) - : getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term); - nodeBuilder.generateNode(WidenedState, Pred); - return; - } // FIXME: Refactor this into a checker. if (BlockCount >= AMgr.options.maxBlockVisitOnPath) { + ProgramStateRef State = Pred->getState(); static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded"); const ExplodedNode *Sink = - nodeBuilder.generateSink(Pred->getState(), Pred, &tag); + nodeBuilder.generateSink(State, Pred, &tag); + + if (AMgr.options.shouldConservativelyWidenLoops() && + !isWidenedState(State)) { + if (const Stmt *LoopStmt = isInsideOfALoop(State)) + if(replayWithWidening(Pred, LoopStmt, BlockCount)) + return; + } // Check if we stopped at the top level function or not. // Root node should have the location context of the top most function. const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame(); const LocationContext *RootLC = - (*G.roots_begin())->getLocation().getLocationContext(); + (*G.roots_begin())->getLocation().getLocationContext(); if (RootLC->getCurrentStackFrame() != CalleeSF) { Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); @@ -1589,7 +1623,45 @@ // Make sink nodes as exhausted(for stats) only if retry failed. Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); + return; + } + + do { + if (AMgr.options.shouldConservativelyWidenLoops()) { + const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); + ProgramStateRef NewState = updateWidenLoopStack(Term, + AMgr.getASTContext(), + Pred); + if(NewState == Pred->getState()) + break; + ExplodedNode *NewNode = nodeBuilder.generateNode(NewState, Pred); + if (!NewNode) + return; + Pred = NewNode; + } + }while(false); + + // If this block is terminated by a loop and it has already been visited the + // maximum number of times, widen the loop. + if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && + (AMgr.options.shouldWidenLoops() || + AMgr.options.shouldConservativelyWidenLoops())) { + const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); + if (!(Term && + (isa(Term) || isa(Term) || isa(Term)))) + return; + // Widen. + const LocationContext *LCtx = Pred->getLocationContext(); + ProgramStateRef WidenedState = + 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 @@ -18,13 +18,51 @@ #include "clang/AST/AST.h" #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "llvm/ADT/SmallSet.h" + using namespace clang; using namespace ento; using namespace clang::ast_matchers; +struct LoopState { +private: + enum Kind { Normal, Widened } K; + const Stmt *LoopStmt; + const LocationContext *LCtx; + LoopState(Kind InK, const Stmt *S, const LocationContext *L) + : K(InK), LoopStmt(S), LCtx(L) {} + +public: + static LoopState getNormal(const Stmt *S, const LocationContext *L) { + return LoopState(Normal, S, L); + } + static LoopState getWidened(const Stmt *S, const LocationContext *L) { + return LoopState(Widened, S, L); + } + bool isWidened() const { return K == Widened; } + const Stmt *getLoopStmt() const { return LoopStmt; } + const LocationContext *getLocationContext() const { return LCtx; } + bool operator==(const LoopState &X) const { + return K == X.K && LoopStmt == X.LoopStmt && LCtx == X.LCtx; + } + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddInteger(K); + ID.AddPointer(LoopStmt); + ID.AddPointer(LCtx); + } +}; + +// The tracked stack of loops. The stack indicates that which loops the +// simulated element contained by. The loops are marked depending if we decided +// to unroll them. +// TODO: The loop stack should not need to be in the program state since it is +// lexical in nature. Instead, the stack of loops should be tracked in the +// LocationContext. +REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState) + /// Return the loops condition Stmt or NULL if LoopStmt is not a loop static const Expr *getLoopCondition(const Stmt *LoopStmt) { switch (LoopStmt->getStmtClass()) { @@ -72,6 +110,11 @@ cxxNonConstCall("changedExpr")); } +static bool isLoopStmt(const Stmt *S) { + return S && (isa(S) || isa(S) || isa(S)); +} + + namespace clang { namespace ento { @@ -104,6 +147,32 @@ } } +ProgramStateRef processWidenLoopEnd(const Stmt *LoopStmt, + ProgramStateRef State) { + auto LS = State->get(); + if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt) + State = State->set(LS.getTail()); + return State; +} + +ProgramStateRef updateWidenLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred) { + auto State = Pred->getState(); + auto LCtx = Pred->getLocationContext(); + + if (!isLoopStmt(LoopStmt)) + return State; + + auto LS = State->get(); + if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && + LCtx == LS.getHead().getLocationContext()) { + return State; + } + + State = State->add(LoopState::getNormal(LoopStmt, LCtx)); + return State; +} + ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State, ASTContext &ASTCtx, const LocationContext *LCtx, @@ -118,6 +187,14 @@ if (!Success) return State; } + + auto LS = State->get(); + assert(LS.getHead().getLoopStmt() == LoopStmt); + assert(!LS.getHead().isWidened()); + + State = State->set(LS.getTail()); + State = State->add(LoopState::getWidened(LoopStmt, LCtx)); + llvm::SmallVector Regions; Regions.reserve(RegionsToInvalidate.size()); for (auto E : RegionsToInvalidate) @@ -128,6 +205,24 @@ true); } +bool isWidenedState(ProgramStateRef State) { + if (!State) + return false; + auto LS = State->get(); + if (LS.isEmpty() || !LS.getHead().isWidened()) + return false; + return true; +} + +const Stmt *isInsideOfALoop(ProgramStateRef State) { + if (!State) + return nullptr; + auto LS = State->get(); + if (LS.isEmpty()) + return nullptr; + return LS.getHead().getLoopStmt(); +} + ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, const LocationContext *LCtx, unsigned BlockCount, const Stmt *LoopStmt) { Index: test/Analysis/loop-widening-conservative.cpp =================================================================== --- test/Analysis/loop-widening-conservative.cpp +++ test/Analysis/loop-widening-conservative.cpp @@ -1,4 +1,4 @@ -// 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 +// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops-conservative=true,cfg-loopexit=true -verify -std=c++11 %s void clang_analyzer_eval(int); void clang_analyzer_warnIfReached(); @@ -140,13 +140,13 @@ int s_local = 2; int *h_ptr = (int *)malloc(sizeof(int)); int change_var = 1; - int nochange_var = 10; + int nochange_var = 2; 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(change_var == 1); // expected-warning {{UNKNOWN}} + clang_analyzer_eval(nochange_var == 2); // expected-warning {{TRUE}} clang_analyzer_eval(g_global); // expected-warning {{UNKNOWN}} clang_analyzer_eval(s_arg == 1); // expected-warning {{TRUE}} @@ -156,7 +156,8 @@ } void nested_loop_outer_widen() { - int i = 0, j = 0; + int i; + int j; for (i = 0; i < 10; i++) { clang_analyzer_eval(i < 10); // expected-warning {{TRUE}} for (j = 0; j < 2; j++) { @@ -164,7 +165,7 @@ } clang_analyzer_eval(j >= 2); // expected-warning {{TRUE}} } - clang_analyzer_warnIfReached(); // no-warning + clang_analyzer_eval(i >= 10); // expected-warning {{TRUE}} } void nested_loop_inner_widen() { @@ -176,7 +177,54 @@ } clang_analyzer_eval(j >= 10); // expected-warning {{TRUE}} } - clang_analyzer_warnIfReached(); // no-warning + clang_analyzer_eval(i >= 2); // expected-warning {{TRUE}} +} + +void nested_loops() { + int i = 0, j = 0; + int x = 2; + for (i = 0; i < 5; i++) { + if (i == 3) + break; + 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 >= 5); // expected-warning {{TRUE}} // expected-warning {{FALSE}} + clang_analyzer_eval(i == 3); // expected-warning {{TRUE}} // expected-warning {{FALSE}} + + // Precision loss of an inner loop variable resulted by the widening of the + // outer loop. + clang_analyzer_eval(j >= 10); // expected-warning {{UNKNOWN}} + + clang_analyzer_eval(x == 2); // expected-warning {{TRUE}} +} + +void nested_loops_2() { + int i = 0, j = 0, k = 0; + int x = 2; + for (i = 0; i < 5; i++) { + if (i == 3) + break; + for (j = 0; j < 10; j++) { + clang_analyzer_eval(j < 10); // expected-warning {{TRUE}} + for (k = 0; k < 42; k++) { + clang_analyzer_eval(k < 42); // expected-warning {{TRUE}} + } + } + clang_analyzer_eval(k >= 42); // expected-warning {{UNKNOWN}} + clang_analyzer_eval(j >= 10); // expected-warning {{TRUE}} + } + clang_analyzer_eval(i >= 5); // expected-warning {{TRUE}} // expected-warning {{FALSE}} + clang_analyzer_eval(i == 3); // expected-warning {{TRUE}} // expected-warning {{FALSE}} + + // Precision loss of the inner loop variables resulted by the widening of the + // outer loops. + clang_analyzer_eval(j >= 10); // expected-warning {{UNKNOWN}} + clang_analyzer_eval(k >= 42); // expected-warning {{UNKNOWN}} + + clang_analyzer_eval(x == 2); // expected-warning {{TRUE}} } struct A { @@ -189,6 +237,14 @@ void assign(const A &other) { num = other.num; } }; +void check_memberexpr() { + A a(2); + for (int i = 0; i < 10; ++i) { + a.num = i; + } + clang_analyzer_eval(a.num == 9); // expected-warning {{UNKNOWN}} +} + void non_const_method_call() { A a(42); for (int i = 0; i < 10; ++i) { @@ -205,7 +261,7 @@ clang_analyzer_eval(a.num == 42); // expected-warning {{TRUE}} } -void knwon_method_call() { +void known_method_call() { A a(42); A b(10); for (int i = 0; i < 10; ++i) {