[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
szepet added inline comments. Comment at: lib/StaticAnalyzer/Core/LoopUnrolling.cpp:28-46 struct LoopState { private: enum Kind { Normal, Unrolled } K; - const Stmt *LoopStmt; - const LocationContext *LCtx; - unsigned maxStep; - LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) - : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} + unsigned MaxStep; + LoopState(Kind InK, unsigned N) : K(InK), MaxStep(N) {} public: NoQ wrote: > Should the whole `LoopState` be reduced to a field(s) in `LoopContext`? It > seems to make sense to me, unless we're planning to modify it in the middle > of the loop. I'm not sure about that. I mean, LoopContext is a general thing for all of the loops. It can easily happen that we modify the bound in the middle of the loop. Another thing what we keep track on if it is unrolled or not which is again something that we can decide to change in the middle of an iteration (e.g. it splits the state). Yes, in our case MaxStep is not likely to change since we store loops that have a fix bound. (This could change in the future but maybe this is a too bold idea.) https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
szepet updated this revision to Diff 130516. szepet marked 2 inline comments as done. szepet added a comment. First, sorry for this delayed update, however, I was working on this and running this on real projects. I wanted to make sure that this update will be complete enough that this patch would not cause any harm (yes, these features are hidden behind a flag but anyway) and not crashes on edge cases I haven't thought of. The core used the fact that LocationContext only contains StackFramce and BlockInvocation and I aimed to eliminate all these code snippets (more like rewrite). > This thing is very similar to https://reviews.llvm.org/D19979. Do we really > need to create a separate LoopContext or we can reuse ScopeContext instead? > I guess LoopContext can be treated as a sub-class of ScopeContext. And i > don't mind having ScopeContext be split into small distinct sub-classes. > Because we're stuck in corner cases for covering all possible scopes, while > we're fine with covering only simple scopes (it's better than nothing) and > lacking a scope from time to time. In this patch I left it as it was, so a separate context. I agree with Aleksei that yes, it could be implemented as a ScopeContext and checked if it contains a While/Do/For Statement. On the other hand, I like the idea more, that we split ScopeContext into small distinct subclasses which would result in a more manageable code. However, this would require refactoring on ScopeContext as well, in order to make it a great base class (like StmtPoint for ProgramPoint). Then, LoopContext would be its only subclass. So, I do not really see the point of doing these changes right now. I think in this state (when ScopeContext not used by the analyzer as I can see) the LoopContext could live as a separate Context and not make any harm. In case when another Context shows up which is similar LoopContext (e.g. ScopeContext) I would happily refactor it but right now, I do not see the point of this. https://reviews.llvm.org/D41151 Files: include/clang/Analysis/AnalysisDeclContext.h include/clang/Analysis/ProgramPoint.h include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h lib/Analysis/AnalysisDeclContext.cpp lib/StaticAnalyzer/Core/BugReporter.cpp lib/StaticAnalyzer/Core/CallEvent.cpp lib/StaticAnalyzer/Core/CoreEngine.cpp lib/StaticAnalyzer/Core/ExprEngine.cpp lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp lib/StaticAnalyzer/Core/LoopUnrolling.cpp lib/StaticAnalyzer/Core/PathDiagnostic.cpp test/Analysis/loop-unrolling.cpp Index: test/Analysis/loop-unrolling.cpp === --- test/Analysis/loop-unrolling.cpp +++ test/Analysis/loop-unrolling.cpp @@ -373,7 +373,6 @@ return 0; } - void pr34943() { for (int i = 0; i < 6L; ++i) { clang_analyzer_numTimesReached(); // expected-warning {{6}} Index: lib/StaticAnalyzer/Core/PathDiagnostic.cpp === --- lib/StaticAnalyzer/Core/PathDiagnostic.cpp +++ lib/StaticAnalyzer/Core/PathDiagnostic.cpp @@ -576,12 +576,18 @@ return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx); return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM); } + case CFGElement::LoopEntrance: { +const Stmt *LoopStmt = Source.castAs().getLoopStmt(); +return PathDiagnosticLocation(LoopStmt, SM, CallerCtx); + } + case CFGElement::LoopExit: { +const Stmt *LoopStmt = Source.castAs().getLoopStmt(); +return PathDiagnosticLocation::createEnd(LoopStmt, SM, CallerCtx); + } case CFGElement::TemporaryDtor: case CFGElement::NewAllocator: llvm_unreachable("not yet implemented!"); case CFGElement::LifetimeEnds: - case CFGElement::LoopExit: - case CFGElement::LoopEntrance: llvm_unreachable("CFGElement kind should not be on callsite!"); } @@ -742,6 +748,10 @@ return CEE->getCalleeContext()->getCallSite(); if (Optional PIPP = P.getAs()) return PIPP->getInitializer()->getInit(); + if (Optional LE = P.getAs()) +return LE->getLoopStmt(); + if (Optional LE = P.getAs()) +return LE->getLoopStmt(); return nullptr; } Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp === --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -13,11 +13,11 @@ /// //===--===// -#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" #include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" -#include
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
NoQ added a comment. //*asked stuff in https://reviews.llvm.org/D39398 regarding how indirect gotos are supported*// https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
NoQ added a comment. Or not. Loop counter has its own whole-loop scope. I guess `LoopContext` can be treated as a sub-class of `ScopeContext`. And i don't mind having `ScopeContext` be split into small distinct sub-classes. Because we're stuck in cornercases for covering all possible scopes, while we're fine with covering only simple scopes (it's better than nothing) and lacking a scope from time to time. https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
NoQ added a comment. So, essentially, `LoopContext` is per-loop, while `ScopeContext` is per-iteration? Comment at: lib/StaticAnalyzer/Core/LoopUnrolling.cpp:28-46 struct LoopState { private: enum Kind { Normal, Unrolled } K; - const Stmt *LoopStmt; - const LocationContext *LCtx; - unsigned maxStep; - LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) - : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} + unsigned MaxStep; + LoopState(Kind InK, unsigned N) : K(InK), MaxStep(N) {} public: Should the whole `LoopState` be reduced to a field(s) in `LoopContext`? It seems to make sense to me, unless we're planning to modify it in the middle of the loop. https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
a.sidorin added a comment. This thing is very similar to https://reviews.llvm.org/D19979. Do we really need to create a separate LoopContext or we can reuse ScopeContext instead? https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
xazax.hun added a comment. Just to be sure, this is just a refactoring to make this cleaner or you expect this to have other effects as well, like better performance? https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
MTC added inline comments. Comment at: include/clang/Analysis/ProgramPoint.h:619 /// CallExitBegin and CallExitEnd. The following operations occur between the -/// two program points: +/// two preogram points: /// - CallExitBegin A minor typo, it should be 'program' :). https://reviews.llvm.org/D41151 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41151: [analyzer] Adding LoopContext and improve loop modeling
szepet created this revision. szepet added reviewers: dcoughlin, NoQ, zaks.anna, xazax.hun, a.sidorin. Herald added subscribers: dkrupp, baloghadamsoftware, whisperity. Based on the CFGLoopEntrance element, it is possible to have a CFG driven LocationContext update which contains loop information as well. Updated the loop unrolling feature as well to use purely the LocationContext stack and not implement its own. https://reviews.llvm.org/D41151 Files: include/clang/Analysis/AnalysisDeclContext.h include/clang/Analysis/ProgramPoint.h include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h lib/Analysis/AnalysisDeclContext.cpp lib/StaticAnalyzer/Core/CoreEngine.cpp lib/StaticAnalyzer/Core/ExprEngine.cpp lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp lib/StaticAnalyzer/Core/LoopUnrolling.cpp test/Analysis/loop-unrolling.cpp Index: test/Analysis/loop-unrolling.cpp === --- test/Analysis/loop-unrolling.cpp +++ test/Analysis/loop-unrolling.cpp @@ -373,7 +373,6 @@ return 0; } - void pr34943() { for (int i = 0; i < 6L; ++i) { clang_analyzer_numTimesReached(); // expected-warning {{6}} Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp === --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -13,11 +13,11 @@ /// //===--===// -#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" #include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" using namespace clang; using namespace ento; @@ -28,56 +28,36 @@ struct LoopState { private: enum Kind { Normal, Unrolled } K; - const Stmt *LoopStmt; - const LocationContext *LCtx; - unsigned maxStep; - LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) - : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} + unsigned MaxStep; + LoopState(Kind InK, unsigned N) : K(InK), MaxStep(N) {} public: - static LoopState getNormal(const Stmt *S, const LocationContext *L, - unsigned N) { -return LoopState(Normal, S, L, N); - } - static LoopState getUnrolled(const Stmt *S, const LocationContext *L, - unsigned N) { -return LoopState(Unrolled, S, L, N); - } + static LoopState getNormal(unsigned N) { return LoopState(Normal, N); } + static LoopState getUnrolled(unsigned N) { return LoopState(Unrolled, N); } bool isUnrolled() const { return K == Unrolled; } - unsigned getMaxStep() const { return maxStep; } - const Stmt *getLoopStmt() const { return LoopStmt; } - const LocationContext *getLocationContext() const { return LCtx; } + unsigned getMaxStep() const { return MaxStep; } bool operator==(const LoopState ) const { -return K == X.K && LoopStmt == X.LoopStmt; +return K == X.K && MaxStep == X.MaxStep; } void Profile(llvm::FoldingSetNodeID ) const { ID.AddInteger(K); -ID.AddPointer(LoopStmt); -ID.AddPointer(LCtx); -ID.AddInteger(maxStep); +ID.AddInteger(MaxStep); } }; -// 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) +// The map of the currently simulated loops which are marked depending if we +// decided to unroll them. +REGISTER_MAP_WITH_PROGRAMSTATE(LoopMap, const LoopContext *, LoopState) namespace clang { namespace ento { static bool isLoopStmt(const Stmt *S) { return S && (isa(S) || isa(S) || isa(S)); } -ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { - auto LS = State->get(); - if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt) -State = State->set(LS.getTail()); - return State; +ProgramStateRef processLoopEnd(const LoopContext *LC, ProgramStateRef State) { + return State->remove(LC); } static internal::Matcher simpleCondition(StringRef BindName) { @@ -157,7 +137,8 @@ hasUnaryOperand(declRefExpr( to(varDecl(allOf(equalsBoundNode("initVarName"), hasType(isInteger(), - unless(hasBody(hasSuspiciousStmt("initVarName".bind("forLoop"); +