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<CFGLoopEntrance>().getLoopStmt();
+ return PathDiagnosticLocation(LoopStmt, SM, CallerCtx);
+ }
+ case CFGElement::LoopExit: {
+ const Stmt *LoopStmt = Source.castAs<CFGLoopExit>().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<PostInitializer> PIPP = P.getAs<PostInitializer>())
return PIPP->getInitializer()->getInit();
+ if (Optional<LoopEnter> LE = P.getAs<LoopEnter>())
+ return LE->getLoopStmt();
+ if (Optional<LoopExit> LE = P.getAs<LoopExit>())
+ 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 "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 &X) const {
- return K == X.K && LoopStmt == X.LoopStmt;
+ return K == X.K && MaxStep == X.MaxStep;
}
void Profile(llvm::FoldingSetNodeID &ID) 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<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
}
-ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
- auto LS = State->get<LoopStack>();
- if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
- State = State->set<LoopStack>(LS.getTail());
- return State;
+ProgramStateRef processLoopEnd(const LoopContext *LC, ProgramStateRef State) {
+ return State->remove<LoopMap>(LC);
}
static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
@@ -157,7 +137,16 @@
hasUnaryOperand(declRefExpr(
to(varDecl(allOf(equalsBoundNode("initVarName"),
hasType(isInteger())))))))),
- unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
+ unless(hasBody(hasSuspiciousStmt("initVarName"))))
+ .bind("forLoop");
+}
+
+extern const internal::VariadicDynCastAllOfMatcher<Stmt, IndirectGotoStmt>
+ indirectGotoStmt;
+
+bool isPreciselyModelableLoop(const Stmt *LoopStmt, ASTContext &ASTCtx) {
+ return match(stmt(hasDescendant(indirectGotoStmt())), *LoopStmt, ASTCtx)
+ .empty();
}
static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
@@ -224,6 +213,12 @@
maxStep = (BoundNum - InitNum).abs().getZExtValue();
// Check if the counter of the loop is not escaped before.
+ // In case it is defined in the init statement then it couldn't escape yet.
+ if (auto ForLoop = dyn_cast<ForStmt>(LoopStmt))
+ if (auto InitStmt = dyn_cast<DeclStmt>(ForLoop->getInit()))
+ if (InitStmt->getSingleDecl() == CounterVar->getCanonicalDecl())
+ return true;
+ // Otherwise walk up on the ExplodedGraph and check for every possibility.
return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
}
@@ -236,59 +231,56 @@
ProgramPoint P = N->getLocation();
if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>())
S = BE->getBlock()->getTerminator();
+ else if (Optional<LoopEnter> LE = P.getAs<LoopEnter>())
+ S = LE->getLoopStmt();
if (S == LoopStmt)
return false;
N = N->getFirstPred();
}
-
llvm_unreachable("Reached root without encountering the previous step");
}
-// updateLoopStack is called on every basic block, therefore it needs to be fast
-ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
- ExplodedNode *Pred, unsigned maxVisitOnPath) {
+// updateLoopStates is called on every basic block, therefore it needs to be
+// fast
+ProgramStateRef updateLoopStates(const LoopContext *LoopCtx, ASTContext &ASTCtx,
+ ExplodedNode *Pred, unsigned MaxVisitOnPath) {
auto State = Pred->getState();
- auto LCtx = Pred->getLocationContext();
+ auto LM = State->get<LoopMap>();
+ auto LoopStmt = LoopCtx->getLoopStmt();
- if (!isLoopStmt(LoopStmt))
- return State;
+ assert((!LM.contains(LoopCtx) ||
+ (LM.contains(LoopCtx) &&
+ Pred->getLocation().getKind() == ProgramPoint::BlockEdgeKind)) &&
+ "LoopEnter Block encountered for an already entered loop");
- auto LS = State->get<LoopStack>();
- if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
- LCtx == LS.getHead().getLocationContext()) {
- if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
- State = State->set<LoopStack>(LS.getTail());
- State = State->add<LoopStack>(
- LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
- }
- return State;
- }
- unsigned maxStep;
- if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) {
- State = State->add<LoopStack>(
- LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
- return State;
- }
+ if (LM.contains(LoopCtx) && LM.lookup(LoopCtx)->isUnrolled() &&
+ madeNewBranch(Pred, LoopStmt))
+ return State->set<LoopMap>(LoopCtx, LoopState::getNormal(MaxVisitOnPath));
- unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
+ if (LM.contains(LoopCtx))
+ return State;
- unsigned innerMaxStep = maxStep * outerStep;
- if (innerMaxStep > MAXIMUM_STEP_UNROLLED)
- State = State->add<LoopStack>(
- LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
+ unsigned MaxStep;
+ if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, MaxStep))
+ return State->set<LoopMap>(LoopCtx, LoopState::getNormal(MaxVisitOnPath));
+
+ const auto OuterLoopCtx =
+ cast_or_null<LoopContext>(Pred->getLocationContext()->getCurrentLoop());
+ unsigned OuterStep =
+ (OuterLoopCtx ? LM.lookup(OuterLoopCtx)->getMaxStep() : 1);
+ unsigned InnerMaxStep = MaxStep * OuterStep;
+ if (InnerMaxStep > MAXIMUM_STEP_UNROLLED)
+ return State->set<LoopMap>(LoopCtx, LoopState::getNormal(MaxVisitOnPath));
else
- State = State->add<LoopStack>(
- LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
- return State;
+ return State->set<LoopMap>(LoopCtx, LoopState::getUnrolled(InnerMaxStep));
}
-bool isUnrolledState(ProgramStateRef State) {
- auto LS = State->get<LoopStack>();
- if (LS.isEmpty() || !LS.getHead().isUnrolled())
- return false;
- return true;
-}
-}
+bool isUnrolledLoopContext(const LoopContext *LC, ProgramStateRef State) {
+ auto LM = State->get<LoopMap>();
+ return LM.contains(LC) && LM.lookup(LC)->isUnrolled();
}
+
+} // namespace ento
+} // namespace clang
Index: lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
@@ -226,8 +226,9 @@
// The parent context might not be a stack frame, so make sure we
// look up the first enclosing stack frame.
- const StackFrameContext *callerCtx =
- calleeCtx->getParent()->getCurrentStackFrame();
+ const LocationContext *callerCtx = calleeCtx->getParent();
+ if (isa<BlockInvocationContext>(callerCtx))
+ callerCtx = callerCtx->getParent();
const Stmt *CE = calleeCtx->getCallSite();
ProgramStateRef state = CEBNode->getState();
@@ -407,14 +408,14 @@
assert(D);
const LocationContext *CurLC = Pred->getLocationContext();
- const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
- const LocationContext *ParentOfCallee = CallerSFC;
+ const LocationContext *ParentOfCallee =
+ (isa<BlockInvocationContext>(CurLC) ? CurLC->getParent() : CurLC);
if (Call.getKind() == CE_Block &&
!cast<BlockCall>(Call).isConversionFromLambda()) {
const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
assert(BR && "If we have the block definition we should have its region");
AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D);
- ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
+ ParentOfCallee = BlockCtx->getBlockInvocationContext(CurLC,
cast<BlockDecl>(D),
BR);
}
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -367,6 +367,9 @@
case CFGElement::LoopExit:
ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
return;
+ case CFGElement::LoopEntrance:
+ ProcessLoopEntrance(E.castAs<CFGLoopEntrance>().getLoopStmt(), Pred);
+ return;
case CFGElement::LifetimeEnds:
return;
}
@@ -512,20 +515,51 @@
Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
}
-void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
+void ExprEngine::ProcessLoopEntrance(const Stmt *LoopStmt, ExplodedNode *Pred) {
PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
- S->getLocStart(),
- "Error evaluating end of the loop");
+ LoopStmt->getLocStart(),
+ "Error evaluating enter of the loop");
ExplodedNodeSet Dst;
- Dst.Add(Pred);
NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
ProgramStateRef NewState = Pred->getState();
- if(AMgr.options.shouldUnrollLoops())
- NewState = processLoopEnd(S, NewState);
+ const LocationContext *PrevLC = Pred->getLocationContext();
+ const LocationContext *NewLC = PrevLC;
- LoopExit PP(S, Pred->getLocationContext());
- Bldr.generateNode(PP, NewState, Pred);
+ if (isPreciselyModelableLoop(LoopStmt, AMgr.getASTContext())) {
+ NewLC = PrevLC->getAnalysisDeclContext()->getLoopContext(PrevLC, LoopStmt);
+ if (AMgr.options.shouldUnrollLoops()) {
+ NewState =
+ updateLoopStates(cast<LoopContext>(NewLC), AMgr.getASTContext(), Pred,
+ AMgr.getAnalyzerOptions().maxBlockVisitOnPath);
+ }
+ }
+
+ LoopEnter LE(LoopStmt, NewLC);
+ Bldr.generateNode(LE, NewState, Pred);
+ // Enqueue the new nodes onto the work list.
+ Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
+}
+
+void ExprEngine::ProcessLoopExit(const Stmt *LoopStmt, ExplodedNode *Pred) {
+ PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
+ LoopStmt->getLocStart(),
+ "Error evaluating end of the loop");
+
+ ExplodedNodeSet Dst;
+ NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
+ ProgramStateRef NewState = Pred->getState();
+ const LocationContext *NewLCtx = Pred->getLocationContext();
+
+ if (NewLCtx->getKind() == LocationContext::Loop &&
+ cast<LoopContext>(NewLCtx)->getLoopStmt() == LoopStmt) {
+ if (AMgr.options.shouldUnrollLoops()) {
+ NewState = processLoopEnd(cast<LoopContext>(NewLCtx), NewState);
+ }
+ NewLCtx = NewLCtx->getParent();
+ }
+ LoopExit LE(LoopStmt, NewLCtx);
+ Bldr.generateNode(LE, NewState, Pred);
// Enqueue the new nodes onto the work list.
Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
}
@@ -1559,20 +1593,25 @@
// If we reach a loop which has a known bound (and meets
// other constraints) then consider completely unrolling it.
if(AMgr.options.shouldUnrollLoops()) {
- unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
- const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
- if (Term) {
- ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
- Pred, maxBlockVisitOnPath);
+ const LoopContext *CurrLoop = Pred->getLocationContext()->getCurrentLoop();
+ do {
+ unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
+ const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
+
+ if (!(Term &&
+ (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
+ break;
+ ProgramStateRef NewState = updateLoopStates(
+ CurrLoop, AMgr.getASTContext(), Pred, maxBlockVisitOnPath);
if (NewState != Pred->getState()) {
ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
if (!UpdatedNode)
return;
Pred = UpdatedNode;
}
- }
- // Is we are inside an unrolled loop then no need the check the counters.
- if(isUnrolledState(Pred->getState()))
+ } while (false);
+ // If we are inside an unrolled loop then no need the check the counters.
+ if (isUnrolledLoopContext(CurrLoop, Pred->getState()))
return;
}
@@ -2750,6 +2789,12 @@
break;
}
+ case ProgramPoint::LoopEnterKind: {
+ LoopEnter LE = Loc.castAs<LoopEnter>();
+ Out << "LoopEnter: " << LE.getLoopStmt()->getStmtClassName();
+ break;
+ }
+
case ProgramPoint::PreImplicitCallKind: {
ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
Out << "PreCall: ";
@@ -2900,6 +2945,11 @@
Out << "Entering scope";
// FIXME: Add more info once ScopeContext is activated.
break;
+ case LocationContext::Loop:
+ Out << "Entering loop: ";
+ cast<LoopContext>(LC)->getLoopStmt()->printPretty(
+ Out, nullptr, PrintingPolicy(LangOptions()));
+ break;
}
Out << "\\l";
}
Index: lib/StaticAnalyzer/Core/CoreEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -275,6 +275,7 @@
Loc.getAs<PostInitializer>() ||
Loc.getAs<PostImplicitCall>() ||
Loc.getAs<CallExitEnd>() ||
+ Loc.getAs<LoopEnter>() ||
Loc.getAs<LoopExit>());
HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
break;
@@ -568,6 +569,7 @@
// Do not create extra nodes. Move to the next CFG element.
if (N->getLocation().getAs<PostInitializer>() ||
N->getLocation().getAs<PostImplicitCall>()||
+ N->getLocation().getAs<LoopEnter>() ||
N->getLocation().getAs<LoopExit>()) {
WList->enqueue(N, Block, Idx+1);
return;
@@ -636,8 +638,8 @@
void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
ExplodedNode *N = *I;
- // If we are in an inlined call, generate CallExitBegin node.
- if (N->getLocationContext()->getParent()) {
+ if (isa<StackFrameContext>(N->getLocationContext()) &&
+ N->getLocationContext()->getParent()) {
N = generateCallExitBeginNode(N, RS);
if (N)
WList->enqueue(N);
Index: lib/StaticAnalyzer/Core/CallEvent.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CallEvent.cpp
+++ lib/StaticAnalyzer/Core/CallEvent.cpp
@@ -1158,7 +1158,9 @@
CallEventManager::getCaller(const StackFrameContext *CalleeCtx,
ProgramStateRef State) {
const LocationContext *ParentCtx = CalleeCtx->getParent();
- const LocationContext *CallerCtx = ParentCtx->getCurrentStackFrame();
+ const LocationContext *CallerCtx = ParentCtx;
+ if (isa<BlockInvocationContext>(CallerCtx))
+ CallerCtx = CallerCtx->getParent();
assert(CallerCtx && "This should not be used for top-level stack frames");
const Stmt *CallSite = CalleeCtx->getCallSite();
Index: lib/StaticAnalyzer/Core/BugReporter.cpp
===================================================================
--- lib/StaticAnalyzer/Core/BugReporter.cpp
+++ lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -1742,6 +1742,25 @@
LCM[&PD.getActivePath()] == PDB.LC);
LCM[&PD.getActivePath()] = PDB.LC;
+ if (Optional<LoopExit> LE = P.getAs<LoopExit>()) {
+ PathDiagnosticLocation L(LE->getLoopStmt(), SM, PDB.LC);
+ auto E = std::make_shared<PathDiagnosticEventPiece>(L, "Exited loop");
+ E->setPrunable(true);
+ addEdgeToPath(PD.getActivePath(), PrevLoc, E->getLocation(), PDB.LC);
+ const LoopContext *LoopCtx =
+ PDB.LC->getAnalysisDeclContext()->getLoopContext(PDB.LC,
+ LE->getLoopStmt());
+ LCM[&PD.getActivePath()] = LoopCtx;
+ }
+
+ if (Optional<LoopEnter> LE = P.getAs<LoopEnter>()) {
+ PathDiagnosticLocation L(LE->getLoopStmt(), SM, PDB.LC);
+ auto E = std::make_shared<PathDiagnosticEventPiece>(L, "Entered loop");
+ E->setPrunable(true);
+ addEdgeToPath(PD.getActivePath(), PrevLoc, E->getLocation(), PDB.LC);
+ LCM[&PD.getActivePath()] = PDB.LC->getParent();
+ }
+
// Have we encountered an exit from a function call?
if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
const Stmt *S = CE->getCalleeContext()->getCallSite();
Index: lib/Analysis/AnalysisDeclContext.cpp
===================================================================
--- lib/Analysis/AnalysisDeclContext.cpp
+++ lib/Analysis/AnalysisDeclContext.cpp
@@ -313,6 +313,12 @@
return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
}
+const LoopContext *
+AnalysisDeclContext::getLoopContext(const LocationContext *Parent,
+ const Stmt *LoopStmt) {
+ return getLocationContextManager().getLoopContext(this, Parent, LoopStmt);
+}
+
const BlockInvocationContext *
AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
const clang::BlockDecl *BD,
@@ -365,6 +371,10 @@
Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
}
+void LoopContext::Profile(llvm::FoldingSetNodeID &ID) {
+ Profile(ID, getAnalysisDeclContext(), getParent(), getLoopStmt());
+}
+
void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
}
@@ -415,6 +425,13 @@
return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
}
+const LoopContext *
+LocationContextManager::getLoopContext(AnalysisDeclContext *Ctx,
+ const LocationContext *Parent,
+ const Stmt *LoopStmt) {
+ return getLocationContext<LoopContext, Stmt>(Ctx, Parent, LoopStmt);
+}
+
const BlockInvocationContext *
LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
const LocationContext *parent,
@@ -447,6 +464,16 @@
return nullptr;
}
+const LoopContext *LocationContext::getCurrentLoop() const {
+ const LocationContext *LC = this;
+ while (LC) {
+ if (const LoopContext *LoopCtx = dyn_cast<LoopContext>(LC))
+ return LoopCtx;
+ LC = LC->getParent();
+ }
+ return nullptr;
+}
+
bool LocationContext::inTopFrame() const {
return getCurrentStackFrame()->inTopFrame();
}
@@ -484,6 +511,10 @@
<< cast<BlockInvocationContext>(LCtx)->getContextData()
<< ")\n";
break;
+ case Loop:
+ OS << Indent << " (loop context: "
+ << cast<LoopContext>(LCtx)->getLoopStmt()->getStmtClassName() << ")\n";
+ break;
}
}
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h
@@ -34,15 +34,17 @@
/// Returns if the given State indicates that is inside a completely unrolled
/// loop.
-bool isUnrolledState(ProgramStateRef State);
+bool isUnrolledLoopContext(const LoopContext *LC, ProgramStateRef State);
/// Updates the stack of loops contained by the ProgramState.
-ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
- ExplodedNode* Pred, unsigned maxVisitOnPath);
+ProgramStateRef updateLoopStates(const LoopContext *LC, ASTContext &ASTCtx,
+ ExplodedNode *Pred, unsigned MaxVisitOnPath);
/// Updates the given ProgramState. In current implementation it removes the top
/// element of the stack of loops.
-ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State);
+ProgramStateRef processLoopEnd(const LoopContext *LC, ProgramStateRef State);
+
+bool isPreciselyModelableLoop(const Stmt *LoopStmt, ASTContext &ASTCtx);
} // end namespace ento
} // end namespace clang
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -196,6 +196,8 @@
void ProcessStmt(const CFGStmt S, ExplodedNode *Pred);
+ void ProcessLoopEntrance(const Stmt *S, ExplodedNode *Pred);
+
void ProcessLoopExit(const Stmt* S, ExplodedNode *Pred);
void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred);
@@ -219,7 +221,7 @@
void processCFGBlockEntrance(const BlockEdge &L,
NodeBuilderWithSinks &nodeBuilder,
ExplodedNode *Pred) override;
-
+
/// ProcessBranch - Called by CoreEngine. Used to generate successor
/// nodes by processing the 'effects' of a branch condition.
void processBranch(const Stmt *Condition, const Stmt *Term,
Index: include/clang/Analysis/ProgramPoint.h
===================================================================
--- include/clang/Analysis/ProgramPoint.h
+++ include/clang/Analysis/ProgramPoint.h
@@ -83,6 +83,7 @@
PostImplicitCallKind,
MinImplicitCallKind = PreImplicitCallKind,
MaxImplicitCallKind = PostImplicitCallKind,
+ LoopEnterKind,
LoopExitKind,
EpsilonKind};
@@ -655,12 +656,31 @@
}
};
+/// Represents a point when we enter a loop.
+/// When this ProgramPoint is encountered we can be sure that the symbolic
+/// execution of the corresponding LoopStmt will be done.
+class LoopEnter : public ProgramPoint {
+public:
+ LoopEnter(const Stmt *LoopStmt, const LocationContext *LC)
+ : ProgramPoint(LoopStmt, nullptr, LoopEnterKind, LC) {}
+
+ const Stmt *getLoopStmt() const {
+ return static_cast<const Stmt *>(getData1());
+ }
+
+private:
+ friend class ProgramPoint;
+ LoopEnter() {}
+ static bool isKind(const ProgramPoint &Location) {
+ return Location.getKind() == LoopEnterKind;
+ }
+};
+
/// Represents a point when we exit a loop.
/// When this ProgramPoint is encountered we can be sure that the symbolic
/// execution of the corresponding LoopStmt is finished on the given path.
/// Note: It is possible to encounter a LoopExit element when we haven't even
-/// encountered the loop itself. At the current state not all loop exits will
-/// result in a LoopExit program point.
+/// encountered the loop itself.
class LoopExit : public ProgramPoint {
public:
LoopExit(const Stmt *LoopStmt, const LocationContext *LC)
Index: include/clang/Analysis/AnalysisDeclContext.h
===================================================================
--- include/clang/Analysis/AnalysisDeclContext.h
+++ include/clang/Analysis/AnalysisDeclContext.h
@@ -36,6 +36,7 @@
class LocationContextManager;
class StackFrameContext;
class BlockInvocationContext;
+class LoopContext;
class AnalysisDeclContextManager;
class LocationContext;
@@ -185,7 +186,10 @@
const Stmt *S,
const CFGBlock *Blk,
unsigned Idx);
-
+
+ const LoopContext *getLoopContext(const LocationContext *Parent,
+ const Stmt *LoopStmt);
+
const BlockInvocationContext *
getBlockInvocationContext(const LocationContext *parent,
const BlockDecl *BD,
@@ -214,7 +218,7 @@
class LocationContext : public llvm::FoldingSetNode {
public:
- enum ContextKind { StackFrame, Scope, Block };
+ enum ContextKind { StackFrame, Scope, Block, Loop };
private:
ContextKind Kind;
@@ -260,6 +264,8 @@
const StackFrameContext *getCurrentStackFrame() const;
+ const LoopContext *getCurrentLoop() const;
+
/// Return true if the current LocationContext has no caller context.
virtual bool inTopFrame() const;
@@ -320,6 +326,31 @@
}
};
+class LoopContext : public LocationContext {
+ const Stmt *LoopStmt;
+
+ friend class LocationContextManager;
+ LoopContext(AnalysisDeclContext *Ctx, const LocationContext *Parent,
+ const Stmt *LS)
+ : LocationContext(Loop, Ctx, Parent), LoopStmt(LS) {}
+
+public:
+ ~LoopContext() override {}
+
+ const Stmt *getLoopStmt() const { return LoopStmt; }
+
+ void Profile(llvm::FoldingSetNodeID &ID) override;
+
+ static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *Ctx,
+ const LocationContext *Parent, const Stmt *LS) {
+ ProfileCommon(ID, Scope, Ctx, Parent, LS);
+ }
+
+ static bool classof(const LocationContext *Ctx) {
+ return Ctx->getKind() == Loop;
+ }
+};
+
class ScopeContext : public LocationContext {
const Stmt *Enter;
@@ -390,7 +421,11 @@
const ScopeContext *getScope(AnalysisDeclContext *ctx,
const LocationContext *parent,
const Stmt *s);
-
+
+ const LoopContext *getLoopContext(AnalysisDeclContext *Ctx,
+ const LocationContext *Parent,
+ const Stmt *LoopStmt);
+
const BlockInvocationContext *
getBlockInvocationContext(AnalysisDeclContext *ctx,
const LocationContext *parent,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
