[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki abandoned this revision. danielmarjamaki added a comment. Herald added subscribers: llvm-commits, a.sidorin, rnkovacs. I will not continue working on this. Feel free to take over the patch or write a new patch. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
NoQ added a comment. > however as far as I see this will mean the LoopUnroller AST matchers can't be > reused unless I change them. Hmm. What is the problem here? I'm expecting library linkage issues (i.e. libAnalysis is not linked to libASTMatchers directly), but i guess it'd better to have the whole thing in libAnalysis then (Peter, WDYT?). Or maybe we could move the code around a bit, so that we're still in libStaticAnalyzerCore but at roughly the same moment of time. Because you're duplicating the solution for exact same problem, using different technology, and this problem is not trivial (eg. you still need to consider reference-type declstmts and initializer lists which are not taken into account in your solution yet) so i'd dislike the idea of duplicating it. Comment at: lib/Analysis/CallGraph.cpp:104 + + void markModifiedVars(Stmt *S) { +// Increment/Decrement, taking address of variable A hint, even if we don't use visitors: the whole point of having a visitor is about not needing to make a pattern-matching (switch or sequence of dyn_casts) by statement kind yourself, like you do in this function. You already have VisitUnaryOperator, VisitBinaryOperator, VisitCallExpr, etc., so you can add the code there. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki added inline comments. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:123 + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) danielmarjamaki wrote: > danielmarjamaki wrote: > > dcoughlin wrote: > > > Since you are calling `getInitialStateForGlobalStaticVar()` in > > > `getInitialState()` for each static variable declaration and > > > `getInitialState()` is called for each top-level function, you are doing > > > an n^3 operation in the size of the translation unit, which is going to > > > be very, very expensive for large translation units. > > > > > > Have you considered doing the analysis for static variables that are > > > never changed during call-graph construction? This should be a linear > > > operation and doing it during call-graph construction would avoid an > > > extra walk of the entire translation unit. > > hmm... could you tell me where the call-graph construction is that I can > > tweak? > I think I found it: `clang/lib/Analysis/CallGraph.cpp` I now track variable modifications in call-graph construction instead. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:155 + Children.push(FuncBody); + while (!Children.empty()) { +const Stmt *Child = Children.top(); szepet wrote: > I think instead of this logic it would be better to use ConstStmtVisitor. In > this case it does quite the same thing in a (maybe?) more structured manner. > What do you think? As far as I see ConstStmtVisitor is also recursive. Imho let's have readable code instead.. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki updated this revision to Diff 118947. danielmarjamaki added a comment. Track modification of global static variables in CallGraph construction Repository: rL LLVM https://reviews.llvm.org/D37897 Files: include/clang/AST/Decl.h include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h lib/AST/Decl.cpp lib/Analysis/CallGraph.cpp lib/StaticAnalyzer/Core/ExprEngine.cpp test/Analysis/global-vars.c Index: test/Analysis/global-vars.c === --- test/Analysis/global-vars.c +++ test/Analysis/global-vars.c @@ -0,0 +1,18 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=alpha,core -verify %s + +// Avoid false positive. +static char *allv[] = {"rpcgen", "-s", "udp", "-s", "tcp"}; +static int allc = sizeof(allv) / sizeof(allv[0]); +static void falsePositive1(void) { + int i; + for (i = 1; i < allc; i++) { +const char *p = allv[i]; // no-warning +i++; + } +} + +// Detect division by zero. +static int zero = 0; +void truePositive1() { + int x = 1000 / zero; // expected-warning{{Division by zero}} +} Index: lib/StaticAnalyzer/Core/ExprEngine.cpp === --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -103,8 +103,71 @@ // Utility methods. //===--===// +/** Get initial state for global static variable */ +ProgramStateRef ExprEngine::getInitialStateForGlobalStaticVar( +const LocationContext *LCtx, ProgramStateRef State, const VarDecl *VD) { + // Is variable changed anywhere in TU? + if (VD->isModified()) +return State; + + // What is the initialized value? + llvm::APSInt InitVal; + if (const Expr *I = VD->getInit()) { +if (!I->EvaluateAsInt(InitVal, getContext())) + return State; + } else { +InitVal = 0; + } + + const MemRegion *R = State->getRegion(VD, LCtx); + if (!R) +return State; + SVal V = State->getSVal(loc::MemRegionVal(R)); + SVal Constraint_untested = + evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal), +svalBuilder.getConditionType()); + Optional Constraint = + Constraint_untested.getAs(); + if (!Constraint) +return State; + return State->assume(*Constraint, true); +} + +static void getGlobalStaticVars(const Stmt *FuncBody, +llvm::SmallSet *Vars) { + std::stack Children; + Children.push(FuncBody); + while (!Children.empty()) { +const Stmt *Child = Children.top(); +Children.pop(); +if (!Child) + continue; +for (const Stmt *C : Child->children()) { + Children.push(C); +} +if (const DeclRefExpr *D = dyn_cast(Child)) { + const VarDecl *VD = dyn_cast(D->getDecl()); + if (VD && VD->isDefinedOutsideFunctionOrMethod() && + VD->getType()->isIntegerType() && + VD->getStorageClass() == SC_Static && + !VD->getType()->isPointerType()) { +Vars->insert(VD); + } +} + } +} + ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { ProgramStateRef state = StateMgr.getInitialState(InitLoc); + // Get initial states for static global variables. + if (const auto *FD = dyn_cast(InitLoc->getDecl())) { +llvm::SmallSet Vars; +getGlobalStaticVars(FD->getBody(), ); +for (const VarDecl *VD : Vars) { + state = getInitialStateForGlobalStaticVar(InitLoc, state, VD); +} + } + const Decl *D = InitLoc->getDecl(); // Preconditions. Index: lib/Analysis/CallGraph.cpp === --- lib/Analysis/CallGraph.cpp +++ lib/Analysis/CallGraph.cpp @@ -33,10 +33,12 @@ CallGraphNode *CallerNode; public: - CGBuilder(CallGraph *g, CallGraphNode *N) -: G(g), CallerNode(N) {} + CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} - void VisitStmt(Stmt *S) { VisitChildren(S); } + void VisitStmt(Stmt *S) { +markModifiedVars(S); +VisitChildren(S); + } Decl *getDeclFromCall(CallExpr *CE) { if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) @@ -63,13 +65,14 @@ if (Decl *D = getDeclFromCall(CE)) addCalledDecl(D); VisitChildren(CE); +markModifiedVars(CE); } // Adds may-call edges for the ObjC message sends. void VisitObjCMessageExpr(ObjCMessageExpr *ME) { if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { Selector Sel = ME->getSelector(); - + // Find the callee definition within the same translation unit. Decl *D = nullptr; if (ME->isInstanceMessage()) @@ -88,6 +91,53 @@ if (SubStmt) this->Visit(SubStmt); } + + void modifyVar(Expr *E) { +auto *D = dyn_cast(E->IgnoreParenCasts()); +if (!D) + return; +VarDecl *VD = dyn_cast(D->getDecl()); +if (VD) + VD->setModified(); + } + + void markModifiedVars(Stmt *S) {
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki added inline comments. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:123 + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) danielmarjamaki wrote: > dcoughlin wrote: > > Since you are calling `getInitialStateForGlobalStaticVar()` in > > `getInitialState()` for each static variable declaration and > > `getInitialState()` is called for each top-level function, you are doing an > > n^3 operation in the size of the translation unit, which is going to be > > very, very expensive for large translation units. > > > > Have you considered doing the analysis for static variables that are never > > changed during call-graph construction? This should be a linear operation > > and doing it during call-graph construction would avoid an extra walk of > > the entire translation unit. > hmm... could you tell me where the call-graph construction is that I can > tweak? I think I found it: `clang/lib/Analysis/CallGraph.cpp` Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki added inline comments. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:123 + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) dcoughlin wrote: > Since you are calling `getInitialStateForGlobalStaticVar()` in > `getInitialState()` for each static variable declaration and > `getInitialState()` is called for each top-level function, you are doing an > n^3 operation in the size of the translation unit, which is going to be very, > very expensive for large translation units. > > Have you considered doing the analysis for static variables that are never > changed during call-graph construction? This should be a linear operation and > doing it during call-graph construction would avoid an extra walk of the > entire translation unit. hmm... could you tell me where the call-graph construction is that I can tweak? Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki added a comment. In https://reviews.llvm.org/D37897#892667, @dcoughlin wrote: > Apologies for the delay reviewing! As I noted inline, I'm pretty worried > about the performance impact of this. Is it possible to do the analysis in a > single traversal of the translation unit? I agree. I first tried more like that but ran into problems. Don't remember the details. I will try again.. however as far as I see this will mean the LoopUnroller AST matchers can't be reused unless I change them. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
dcoughlin requested changes to this revision. dcoughlin added a comment. This revision now requires changes to proceed. Apologies for the delay reviewing! As I noted inline, I'm pretty worried about the performance impact of this. Is it possible to do the analysis in a single traversal of the translation unit? Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:123 + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) Since you are calling `getInitialStateForGlobalStaticVar()` in `getInitialState()` for each static variable declaration and `getInitialState()` is called for each top-level function, you are doing an n^3 operation in the size of the translation unit, which is going to be very, very expensive for large translation units. Have you considered doing the analysis for static variables that are never changed during call-graph construction? This should be a linear operation and doing it during call-graph construction would avoid an extra walk of the entire translation unit. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
szepet added a comment. Hello Daniel! It is a great feature to add, thanks for working on this! I have just small comments (rather questions) on the code. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:155 + Children.push(FuncBody); + while (!Children.empty()) { +const Stmt *Child = Children.top(); I think instead of this logic it would be better to use ConstStmtVisitor. In this case it does quite the same thing in a (maybe?) more structured manner. What do you think? Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:168 + VD->getStorageClass() == SC_Static && + !VD->getType()->isPointerType()) { +Vars->insert(VD); Is it possible that a type is an IntegerType and a PointerType at the same time? If these are excluding cases then the check for !isPointer could be removed. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki marked an inline comment as done. danielmarjamaki added inline comments. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:107 +/** Recursively check if variable is changed in code. */ +static bool isChanged(const Stmt *S, const VarDecl *VD, bool Write) { + if (!S) xazax.hun wrote: > Usually, we do not like bug recursions since it might eat up the stack. > Also, do you consider the case when the variable is passed by reference to a > function in another translation unit? I rewrote the code to reuse the ast matchers in LoopUnroll.. and that is not recursive. I rewrote the getGlobalStaticVars (this code is longer and in my opinion less readable but it's not recursive). Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:169 + SVal Constraint_untested = + evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal), +svalBuilder.getConditionType()); xazax.hun wrote: > Does this work for non-integer typed e.g. structs? Currently static struct objects are unaffected by these changes. There is no regression. Reviews are taking too long time. I am not against getting reviews but I am against waiting for reviews for months, ideally people would only need to wait for at most a week to get a review. This is why I don't want to handle structs now -- I am not eager to prolong the review process for this patch. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki updated this revision to Diff 117956. danielmarjamaki added a comment. Herald added a subscriber: szepet. Fixes according to review comments. Reuse ast matchers in LoopUnrolling.cpp. Avoid some recursion (however the isChanged() is still recursive but it is very small and simple). Repository: rL LLVM https://reviews.llvm.org/D37897 Files: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h lib/StaticAnalyzer/Core/ExprEngine.cpp lib/StaticAnalyzer/Core/LoopUnrolling.cpp test/Analysis/global-vars.c Index: test/Analysis/global-vars.c === --- test/Analysis/global-vars.c +++ test/Analysis/global-vars.c @@ -0,0 +1,18 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=alpha,core -verify %s + +// Avoid false positive. +static char *allv[] = {"rpcgen", "-s", "udp", "-s", "tcp"}; +static int allc = sizeof(allv) / sizeof(allv[0]); +static void falsePositive1(void) { + int i; + for (i = 1; i < allc; i++) { +const char *p = allv[i]; // no-warning +i++; + } +} + +// Detect division by zero. +static int zero = 0; +void truePositive1() { + int x = 1000 / zero; // expected-warning{{Division by zero}} +} Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp === --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -99,7 +99,10 @@ declRefExpr(to(varDecl(VarNodeMatcher)), binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="), hasOperatorName("/="), hasOperatorName("*="), - hasOperatorName("-=")), + hasOperatorName("-="), hasOperatorName("%="), + hasOperatorName("<<="), hasOperatorName(">>="), + hasOperatorName("&="), hasOperatorName("|="), + hasOperatorName("^=")), hasLHS(ignoringParenImpCasts( declRefExpr(to(varDecl(VarNodeMatcher))); } @@ -283,5 +286,16 @@ return false; return true; } + +bool isVarChanged(const FunctionDecl *FD, const VarDecl *VD) { + if (!FD->getBody()) +return false; + auto Match = match( + stmt(hasDescendant(stmt(anyOf( + callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)), + assignedToRef(equalsNode(VD)), changeIntBoundNode(equalsNode(VD)), + *FD->getBody(), FD->getASTContext()); + return !Match.empty(); } -} +} // namespace ento +} // namespace clang Index: lib/StaticAnalyzer/Core/ExprEngine.cpp === --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -103,8 +103,86 @@ // Utility methods. //===--===// +static bool isChanged(const Decl *D, const VarDecl *VD) { + if (const auto *FD = dyn_cast(D)) { +return isVarChanged(FD, VD); + } + if (const auto *Rec = dyn_cast(D)) { +for (const auto *RecChild : Rec->decls()) { + if (isChanged(RecChild, VD)) +return true; +} + } + return false; +} + +/** Get initial state for global static variable */ +ProgramStateRef ExprEngine::getInitialStateForGlobalStaticVar( +const LocationContext *LCtx, ProgramStateRef State, const VarDecl *VD) { + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) + return State; + } + + // What is the initialized value? + llvm::APSInt InitVal; + if (const Expr *I = VD->getInit()) { +if (!I->EvaluateAsInt(InitVal, getContext())) + return State; + } else { +InitVal = 0; + } + + const MemRegion *R = State->getRegion(VD, LCtx); + if (!R) +return State; + SVal V = State->getSVal(loc::MemRegionVal(R)); + SVal Constraint_untested = + evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal), +svalBuilder.getConditionType()); + Optional Constraint = + Constraint_untested.getAs(); + if (!Constraint) +return State; + return State->assume(*Constraint, true); +} + +static void getGlobalStaticVars(const Stmt *FuncBody, +llvm::SmallSet *Vars) { + std::stack Children; + Children.push(FuncBody); + while (!Children.empty()) { +const Stmt *Child = Children.top(); +Children.pop(); +if (!Child) + continue; +for (const Stmt *C : Child->children()) { + Children.push(C); +} +if (const DeclRefExpr *D = dyn_cast(Child)) { + const VarDecl *VD = dyn_cast(D->getDecl()); + if (VD && VD->isDefinedOutsideFunctionOrMethod() && + VD->getType()->isIntegerType() && + VD->getStorageClass() == SC_Static && +
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
NoQ added a comment. The overall idea makes sense to me. I'd like you to join the effort with Peter who during his work on loop widening came up with a matcher-based procedure for finding out if a variable is changed anywhere; it currently lives in `LoopUnrolling.cpp` and we need only once implementation of that. Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
xazax.hun added a comment. I have some comments and questions but maybe you do not want to address those until Devin, NoQ, or Anna approved the general directions. Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:107 +/** Recursively check if variable is changed in code. */ +static bool isChanged(const Stmt *S, const VarDecl *VD, bool Write) { + if (!S) Usually, we do not like bug recursions since it might eat up the stack. Also, do you consider the case when the variable is passed by reference to a function in another translation unit? Comment at: lib/StaticAnalyzer/Core/ExprEngine.cpp:169 + SVal Constraint_untested = + evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal), +svalBuilder.getConditionType()); Does this work for non-integer typed e.g. structs? Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki added a comment. In https://reviews.llvm.org/D37897#871858, @xazax.hun wrote: > Out of curiosity, does the false positive disappear after making the static > variables const? Yes that fixes the false positive Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
xazax.hun added a comment. Out of curiosity, does the false positive disappear after making the static variables const? Repository: rL LLVM https://reviews.llvm.org/D37897 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki updated this revision to Diff 115385. danielmarjamaki added a comment. Minor cleanups. Changed names. Updated comments. Repository: rL LLVM https://reviews.llvm.org/D37897 Files: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h lib/StaticAnalyzer/Core/ExprEngine.cpp test/Analysis/global-vars.c Index: test/Analysis/global-vars.c === --- test/Analysis/global-vars.c +++ test/Analysis/global-vars.c @@ -0,0 +1,18 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=alpha,core -verify %s + +// Avoid false positive. +static char *allv[] = {"rpcgen", "-s", "udp", "-s", "tcp"}; +static int allc = sizeof(allv) / sizeof(allv[0]); +static void falsePositive1(void) { + int i; + for (i = 1; i < allc; i++) { +const char *p = allv[i]; // no-warning +i++; + } +} + +// Detect division by zero. +static int zero = 0; +void truePositive1() { + int x = 1000 / zero; // expected-warning{{Division by zero}} +} Index: lib/StaticAnalyzer/Core/ExprEngine.cpp === --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -103,8 +103,107 @@ // Utility methods. //===--===// +/** Recursively check if variable is changed in code. */ +static bool isChanged(const Stmt *S, const VarDecl *VD, bool Write) { + if (!S) +return false; + if (const BinaryOperator *B = dyn_cast(S)) { +if (B->isAssignmentOp()) + return isChanged(B->getLHS(), VD, true) || + isChanged(B->getRHS(), VD, Write); + } else if (const UnaryOperator *U = dyn_cast(S)) { +// Operators that mean operand is written. +// AddrOf is here because the address might be used to write the operand +// later indirectly. +if (U->getOpcode() == UO_AddrOf || U->getOpcode() == UO_PreInc || +U->getOpcode() == UO_PreDec || U->getOpcode() == UO_PostInc || +U->getOpcode() == UO_PostDec) + return isChanged(U->getSubExpr(), VD, true); + } else if (const DeclRefExpr *D = dyn_cast(S)) { +return Write && D->getDecl() == VD; + } + + for (const Stmt *Child : S->children()) { +if (isChanged(Child, VD, Write)) + return true; + } + return false; +} + +/** Is variable changed in function or method? */ +static bool isChanged(const Decl *D, const VarDecl *VD) { + if (isa(D)) +return isChanged(D->getBody(), VD, false); + if (const auto *Rec = dyn_cast(D)) { +for (const auto *RecChild : Rec->decls()) { + if (isChanged(RecChild, VD)) +return true; +} + } + return false; +} + +/** Get initial state for global static variable */ +ProgramStateRef ExprEngine::getInitialStateForGlobalStaticVar( +const LocationContext *LCtx, ProgramStateRef State, const VarDecl *VD) { + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) + return State; + } + + // What is the initialized value? + llvm::APSInt InitVal; + if (const Expr *I = VD->getInit()) { +if (!I->EvaluateAsInt(InitVal, getContext())) + return State; + } else { +InitVal = 0; + } + + const MemRegion *R = State->getRegion(VD, LCtx); + if (!R) +return State; + SVal V = State->getSVal(loc::MemRegionVal(R)); + SVal Constraint_untested = + evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal), +svalBuilder.getConditionType()); + Optional Constraint = + Constraint_untested.getAs(); + if (!Constraint) +return State; + return State->assume(*Constraint, true); +} + +static void getGlobalStaticVars(const Stmt *S, +llvm::SmallSet *Vars) { + if (!S) +return; + if (const DeclRefExpr *D = dyn_cast(S)) { +const VarDecl *VD = dyn_cast(D->getDecl()); +if (VD && VD->isDefinedOutsideFunctionOrMethod() && +VD->getType()->isIntegerType() && VD->getStorageClass() == SC_Static && +!VD->getType()->isPointerType()) { + Vars->insert(VD); +} + } + for (const Stmt *Child : S->children()) { +getStaticVars(Child, Vars); + } +} + ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { ProgramStateRef state = StateMgr.getInitialState(InitLoc); + + // Get initial states for static global variables. + if (const auto *FD = dyn_cast(InitLoc->getDecl())) { +llvm::SmallSet Vars; +getGlobalStaticVars(FD->getBody(), ); +for (const VarDecl *VD : Vars) { + state = getInitialState(InitLoc, state, VD); +} + } + const Decl *D = InitLoc->getDecl(); // Preconditions. Index: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h === --- include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
[PATCH] D37897: [StaticAnalyzer] Fix ProgramState for static variables that are not written
danielmarjamaki created this revision. I saw a false positive where the analyzer made wrong conclusions about a static variable. Static variables that are not written have known values (initialized values). This is the (simplified) code that motivated me to create this patch: static char *allv[] = { "rpcgen", "-s", "udp", "-s", "tcp", }; static int allc = sizeof(allv) / sizeof(allv[0]); static void f(void) { int i; for (i = 1; i < allc; i++) { const char *p = allv[i]; // <- line 28 i++; } } Clang output: array-fp3.c:28:19: warning: Access out-of-bound array element (buffer overflow) const char *p = allv[i]; ^~~ I added testcases that shows this patch solves both false positives and false negatives Repository: rL LLVM https://reviews.llvm.org/D37897 Files: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h lib/StaticAnalyzer/Core/ExprEngine.cpp test/Analysis/global-vars.c Index: test/Analysis/global-vars.c === --- test/Analysis/global-vars.c +++ test/Analysis/global-vars.c @@ -0,0 +1,18 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=alpha,core -verify %s + +// Avoid false positive. +static char *allv[] = {"rpcgen", "-s", "udp", "-s", "tcp"}; +static int allc = sizeof(allv) / sizeof(allv[0]); +static void falsePositive1(void) { + int i; + for (i = 1; i < allc; i++) { +const char *p = allv[i]; // no-warning +i++; + } +} + +// Detect division by zero. +static int zero = 0; +void truePositive1() { + int x = 1000 / zero; // expected-warning{{Division by zero}} +} Index: lib/StaticAnalyzer/Core/ExprEngine.cpp === --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -103,8 +103,106 @@ // Utility methods. //===--===// +static bool isChanged(const Stmt *S, const VarDecl *VD, bool W) { + if (!S) +return false; + if (const BinaryOperator *B = dyn_cast(S)) { +if (B->isAssignmentOp()) + return isChanged(B->getLHS(), VD, true) || isChanged(B->getRHS(), VD, W); + } else if (const UnaryOperator *U = dyn_cast(S)) { +if (U->getOpcode() == UO_AddrOf || U->getOpcode() == UO_PreInc || +U->getOpcode() == UO_PreDec || U->getOpcode() == UO_PostInc || +U->getOpcode() == UO_PostDec) + return isChanged(U->getSubExpr(), VD, true); + } else if (const DeclRefExpr *D = dyn_cast(S)) { +return W && D->getDecl() == VD; + } + + for (const Stmt *Child : S->children()) { +if (isChanged(Child, VD, W)) + return true; + } + return false; +} + +static bool isChanged(const Decl *D, const VarDecl *VD) { + if (isa(D)) +return isChanged(D->getBody(), VD, false); + if (const auto *Rec = dyn_cast(D)) { +for (const auto *RecChild : Rec->decls()) { + if (isChanged(RecChild, VD)) +return true; +} + } + return false; +} + +ProgramStateRef ExprEngine::getInitialState(const LocationContext *LCtx, +ProgramStateRef State, +const VarDecl *VD) { + // Is variable used in location context? + const FunctionDecl *FD = dyn_cast(LCtx->getDecl()); + if (!FD) +return State; + + // Is variable changed anywhere in TU? + for (const Decl *D : AMgr.getASTContext().getTranslationUnitDecl()->decls()) { +if (isChanged(D, VD)) + return State; + } + + // What is the initialized value? + llvm::APSInt InitVal; + if (const Expr *I = VD->getInit()) { +if (!I->EvaluateAsInt(InitVal, getContext())) + return State; + } else { +InitVal = 0; + } + + const MemRegion *R = State->getRegion(VD, LCtx); + if (!R) +return State; + SVal V = State->getSVal(loc::MemRegionVal(R)); + SVal Constraint_untested = + evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal), +svalBuilder.getConditionType()); + Optional Constraint = + Constraint_untested.getAs(); + if (!Constraint) +return State; + return State->assume(*Constraint, true); +} + +static void getStaticVars(const Stmt *S, + llvm::SmallSet *Vars) { + if (!S) +return; + if (const DeclRefExpr *D = dyn_cast(S)) { +const VarDecl *VD = dyn_cast(D->getDecl()); +if (VD && VD->isDefinedOutsideFunctionOrMethod() && +VD->getType()->isIntegerType() && VD->getStorageClass() == SC_Static && +!VD->getType()->isPointerType()) { + Vars->insert(VD); +} + } + for (const Stmt *Child : S->children()) { +getStaticVars(Child, Vars); + } +} + ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { ProgramStateRef state = StateMgr.getInitialState(InitLoc); + + // Get initial states for static global