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, 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(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/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/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: 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(ctx, parent, s); } +const LoopContext * +LocationContextManager::getLoopContext(AnalysisDeclContext *Ctx, + const LocationContext *Parent, + const Stmt *LoopStmt) { + return getLocationContext(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(LC)) + return LoopCtx; + LC = LC->getParent(); + } + return nullptr; +} + bool LocationContext::inTopFrame() const { return getCurrentStackFrame()->inTopFrame(); } @@ -484,6 +511,10 @@ << cast(LCtx)->getContextData() << ")\n"; break; + case Loop: + OS << Indent << " (loop context: " + << cast(LCtx)->getLoopStmt()->getStmtClassName() << ")\n"; + break; } } } 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 LE = P.getAs()) { + PathDiagnosticLocation L(LE->getLoopStmt(), SM, PDB.LC); + auto E = std::make_shared(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 LE = P.getAs()) { + PathDiagnosticLocation L(LE->getLoopStmt(), SM, PDB.LC); + auto E = std::make_shared(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 CE = P.getAs()) { const Stmt *S = CE->getCalleeContext()->getCallSite(); 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(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/CoreEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/CoreEngine.cpp +++ lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -275,6 +275,7 @@ Loc.getAs() || Loc.getAs() || Loc.getAs() || + Loc.getAs() || Loc.getAs()); 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() || N->getLocation().getAs()|| + N->getLocation().getAs() || N->getLocation().getAs()) { 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(N->getLocationContext()) && + N->getLocationContext()->getParent()) { N = generateCallExitBeginNode(N, RS); if (N) WList->enqueue(N); 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().getLoopStmt(), Pred); return; + case CFGElement::LoopEntrance: + ProcessLoopEntrance(E.castAs().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(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(NewLCtx)->getLoopStmt() == LoopStmt) { + if (AMgr.options.shouldUnrollLoops()) { + NewState = processLoopEnd(cast(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(Term) || isa(Term) || isa(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(); + Out << "LoopEnter: " << LE.getLoopStmt()->getStmtClassName(); + break; + } + case ProgramPoint::PreImplicitCallKind: { ImplicitCallPoint PC = Loc.castAs(); 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(LC)->getLoopStmt()->printPretty( + Out, nullptr, PrintingPolicy(LangOptions())); + break; } Out << "\\l"; } 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(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(CurLC) ? CurLC->getParent() : CurLC); if (Call.getKind() == CE_Block && !cast(Call).isConversionFromLambda()) { const BlockDataRegion *BR = cast(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(D), BR); } 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,43 +28,26 @@ 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 { @@ -73,11 +56,8 @@ 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,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 + 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(LoopStmt)) + if (auto InitStmt = dyn_cast(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 BE = P.getAs()) S = BE->getBlock()->getTerminator(); + else if (Optional LE = P.getAs()) + 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(); + 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(); - if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && - LCtx == LS.getHead().getLocationContext()) { - if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { - State = State->set(LS.getTail()); - State = State->add( - LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); - } - return State; - } - unsigned maxStep; - if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { - State = State->add( - LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); - return State; - } + if (LM.contains(LoopCtx) && LM.lookup(LoopCtx)->isUnrolled() && + madeNewBranch(Pred, LoopStmt)) + return State->set(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( - LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); + unsigned MaxStep; + if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, MaxStep)) + return State->set(LoopCtx, LoopState::getNormal(MaxVisitOnPath)); + + const auto OuterLoopCtx = + cast_or_null(Pred->getLocationContext()->getCurrentLoop()); + unsigned OuterStep = + (OuterLoopCtx ? LM.lookup(OuterLoopCtx)->getMaxStep() : 1); + unsigned InnerMaxStep = MaxStep * OuterStep; + if (InnerMaxStep > MAXIMUM_STEP_UNROLLED) + return State->set(LoopCtx, LoopState::getNormal(MaxVisitOnPath)); else - State = State->add( - LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); - return State; + return State->set(LoopCtx, LoopState::getUnrolled(InnerMaxStep)); } -bool isUnrolledState(ProgramStateRef State) { - auto LS = State->get(); - if (LS.isEmpty() || !LS.getHead().isUnrolled()) - return false; - return true; -} -} +bool isUnrolledLoopContext(const LoopContext *LC, ProgramStateRef State) { + auto LM = State->get(); + return LM.contains(LC) && LM.lookup(LC)->isUnrolled(); } + +} // namespace ento +} // namespace clang 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: 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}}