[analyzer] Adding LoopContext and improve loop modeling

[szepet]

Summary

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.
In the current situation the loop unrolling keeps track the currently simulated loop by having a stack of loops. However, the elements of the stack (so the needed information to describe the currently simulated loop) contains not just a Stmt* but a LocationContext* too which is a stack as well. So in order to store this information more efficient and intuitive I have added it to the LocationContext stack.

[MTC]

include/clang/Analysis/ProgramPoint.h

619

A minor typo, it should be 'program' :).

[xazax.hun]

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?

[a.sidorin]

This thing is very similar to D19979. Do we really need to create a separate LoopContext or we can reuse ScopeContext instead?

[NoQ]

So, essentially, LoopContext is per-loop, while ScopeContext is per-iteration?

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

28–46

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.

[NoQ]

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.

[NoQ]

*asked stuff in D39398 regarding how indirect gotos are supported*

[szepet]

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 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.

[szepet]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

28–46

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.)

include/clang/Analysis/AnalysisDeclContext.h

 class CFGStmtMap;
 class LiveVariables;
 class ManagedAnalysis;
 class ParentMap;
 class PseudoConstantAnalysis;
 class LocationContextManager;
 class StackFrameContext;
 class BlockInvocationContext;
+class LoopContext;
 class AnalysisDeclContextManager;
 class LocationContext;
 
 namespace idx { class TranslationUnit; }
 
 /// The base class of a hierarchy of objects representing analyses tied
 /// to AnalysisDeclContext.
 class ManagedAnalysis {
public:
   /// Return the ImplicitParamDecl* associated with 'self' if this
   /// AnalysisDeclContext wraps an ObjCMethodDecl.  Returns NULL otherwise.
   const ImplicitParamDecl *getSelfDecl() const;
 
   const StackFrameContext *getStackFrame(LocationContext const *Parent,
                                          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,
                             const void *ContextData);
 
   /// Return the specified analysis object, lazily running the analysis if
   /// necessary.  Return NULL if the analysis could not run.
   template <typename T>

 private:
   ManagedAnalysis *&getAnalysisImpl(const void* tag);
 
   LocationContextManager &getLocationContextManager();
 };
 
 class LocationContext : public llvm::FoldingSetNode {
 public:
-  enum ContextKind { StackFrame, Scope, Block };
+  enum ContextKind { StackFrame, Scope, Block, Loop };
 
 private:
   ContextKind Kind;
 
   // AnalysisDeclContext can't be const since some methods may modify its
   // member.
   AnalysisDeclContext *Ctx;
 
public:
   }
 
   const ImplicitParamDecl *getSelfDecl() const {
     return Ctx->getSelfDecl();
   }
 
   const StackFrameContext *getCurrentStackFrame() const;
 
+  const LoopContext *getCurrentLoop() const;
+
   /// Return true if the current LocationContext has no caller context.
   virtual bool inTopFrame() const;
 
   virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
 
   void dumpStack(raw_ostream &OS, StringRef Indent = "") const;
   void dumpStack() const;
 
static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
     ID.AddInteger(idx);
   }
 
   static bool classof(const LocationContext *Ctx) {
     return Ctx->getKind() == StackFrame;
   }
 };
 
+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;
 
   friend class LocationContextManager;
   ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent,
                const Stmt *s)
     : LocationContext(Scope, ctx, parent), Enter(s) {}
 
public:
   const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
                                          const LocationContext *parent,
                                          const Stmt *s,
                                          const CFGBlock *blk, unsigned idx);
 
   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,
                             const BlockDecl *BD,
                             const void *ContextData);
 
   /// Discard all previously created LocationContext objects.
   void clear();

include/clang/Analysis/ProgramPoint.h

enum Kind { BlockEdgeKind,
               PostInitializerKind,
               CallEnterKind,
               CallExitBeginKind,
               CallExitEndKind,
               PreImplicitCallKind,
               PostImplicitCallKind,
               MinImplicitCallKind = PreImplicitCallKind,
               MaxImplicitCallKind = PostImplicitCallKind,
+              LoopEnterKind,
               LoopExitKind,
               EpsilonKind};
 
 private:
   const void *Data1;
   llvm::PointerIntPair<const void *, 2, unsigned> Data2;
 
   // The LocationContext could be NULL to allow ProgramPoint to be used in
static bool isKind(const ProgramPoint &Location) {
     return Location.getKind() == CallEnterKind;
   }
 };
 
 /// Represents a point when we start the call exit sequence (for inlined call).
 ///
 /// The call exit is simulated with a sequence of nodes, which occur between
 /// CallExitBegin and CallExitEnd. The following operations occur between the
 /// two program points:
 /// - CallExitBegin
 /// - Bind the return value
 /// - Run Remove dead bindings (to clean up the dead symbols from the callee).
 /// - CallExitEnd
 class CallExitBegin : public ProgramPoint {
 public:
   // CallExitBegin uses the callee's location context.
   CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS)

 private:
   friend class ProgramPoint;
   CallExitEnd() {}
   static bool isKind(const ProgramPoint &Location) {
     return Location.getKind() == CallExitEndKind;
   }
 };
 
+/// 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)
             : ProgramPoint(LoopStmt, nullptr, LoopExitKind, LC) {}
 
     const Stmt *getLoopStmt() const {
       return static_cast<const Stmt *>(getData1());
     }

include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

public:
 
   /// processCFGElement - Called by CoreEngine. Used to generate new successor
   ///  nodes by processing the 'effects' of a CFG element.
   void processCFGElement(const CFGElement E, ExplodedNode *Pred,
                          unsigned StmtIdx, NodeBuilderContext *Ctx) override;
 
   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);
 
   void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred);
 
   void ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred);
 
   void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
                                ExplodedNode *Pred, ExplodedNodeSet &Dst);
   void ProcessDeleteDtor(const CFGDeleteDtor D,
                          ExplodedNode *Pred, ExplodedNodeSet &Dst);
   void ProcessBaseDtor(const CFGBaseDtor D,
                        ExplodedNode *Pred, ExplodedNodeSet &Dst);
   void ProcessMemberDtor(const CFGMemberDtor D,
                          ExplodedNode *Pred, ExplodedNodeSet &Dst);
   void ProcessTemporaryDtor(const CFGTemporaryDtor D, 
                             ExplodedNode *Pred, ExplodedNodeSet &Dst);
 
   /// Called by CoreEngine when processing the entrance of a CFGBlock.
   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, 
                      NodeBuilderContext& BuilderCtx,
                      ExplodedNode *Pred,
                      ExplodedNodeSet &Dst,
                      const CFGBlock *DstT,
                      const CFGBlock *DstF) override;

include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h

 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 namespace clang {
 namespace ento {
 class AnalysisManager;
 
 /// 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
 
 #endif

lib/Analysis/AnalysisDeclContext.cpp

 BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }
 
 const StackFrameContext *
 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
                                const CFGBlock *Blk, unsigned Idx) {
   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,
                                                const void *ContextData) {
   return getLocationContextManager().getBlockInvocationContext(this, parent,
                                                                BD, ContextData);
 }
 

 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
 }
 
 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
   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);
 }
 
 //===----------------------------------------------------------------------===//
 // LocationContext creation.
 //===----------------------------------------------------------------------===//
 

 
 const ScopeContext *
 LocationContextManager::getScope(AnalysisDeclContext *ctx,
                                  const LocationContext *parent,
                                  const Stmt *s) {
   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,
                                                   const BlockDecl *BD,
                                                   const void *ContextData) {
   llvm::FoldingSetNodeID ID;
   BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
   void *InsertPos;
const StackFrameContext *LocationContext::getCurrentStackFrame() const {
   while (LC) {
     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC))
       return SFC;
     LC = LC->getParent();
   }
   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();
 }
 
 bool LocationContext::isParentOf(const LocationContext *LC) const {
   do {
     const LocationContext *Parent = LC->getParent();
     if (Parent == this)
for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
     case Scope:
       OS << Indent << "    (scope)\n";
       break;
     case Block:
       OS << Indent << "    (block context: "
                    << cast<BlockInvocationContext>(LCtx)->getContextData()
                    << ")\n";
       break;
+    case Loop:
+      OS << Indent << "    (loop context: "
+         << cast<LoopContext>(LCtx)->getLoopStmt()->getStmtClassName() << ")\n";
+      break;
     }
   }
 }
 
 LLVM_DUMP_METHOD void LocationContext::dumpStack() const {
   dumpStack(llvm::errs());
 }
 

lib/StaticAnalyzer/Core/BugReporter.cpp

do {
       PDB.LC = N->getLocationContext();
 
       // Record the mapping from the active path to the location
       // context.
       assert(!LCM[&PD.getActivePath()] ||
              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();
         // Propagate the interesting symbols accordingly.
         if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
                                               N->getState().get(), Ex,
                                               N->getLocationContext());

lib/StaticAnalyzer/Core/CallEvent.cpp

CallEventManager::getSimpleCall(const CallExpr *CE, ProgramStateRef State,
   return create<SimpleFunctionCall>(CE, State, LCtx);
 }
 
 
 CallEventRef<>
 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();
 
   if (CallSite) {
     if (const CallExpr *CE = dyn_cast<CallExpr>(CallSite))
       return getSimpleCall(CE, State, CallerCtx);
 

lib/StaticAnalyzer/Core/CoreEngine.cpp

case ProgramPoint::EpsilonKind: {
       dispatchWorkItem(Pred, PNode->getLocation(), WU);
       break;
     }
     default:
       assert(Loc.getAs<PostStmt>() ||
              Loc.getAs<PostInitializer>() ||
              Loc.getAs<PostImplicitCall>() ||
              Loc.getAs<CallExitEnd>() ||
+             Loc.getAs<LoopEnter>() ||
              Loc.getAs<LoopExit>());
       HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
       break;
   }
 }
 
 bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
                                                  unsigned Steps,
if (N->getLocation().getAs<CallEnter>()) {
     // StackFrameContext.
     WList->enqueue(N, Block, Idx);
     return;
   }
 
   // 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;
   }
 
   if (N->getLocation().getAs<EpsilonPoint>()) {
     WList->enqueue(N, Block, Idx);
     return;
for (ExplodedNodeSet::iterator I = Set.begin(),
                                  E = Set.end(); I != E; ++I) {
     enqueueStmtNode(*I, Block, Idx);
   }
 }
 
 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);
     } else {
       // TODO: We should run remove dead bindings here.
       G.addEndOfPath(N);
       NumPathsExplored++;
     }

lib/StaticAnalyzer/Core/ExprEngine.cpp

switch (E.getKind()) {
     case CFGElement::BaseDtor:
     case CFGElement::MemberDtor:
     case CFGElement::TemporaryDtor:
       ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
       return;
     case CFGElement::LoopExit:
       ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
       return;
+    case CFGElement::LoopEntrance:
+      ProcessLoopEntrance(E.castAs<CFGLoopEntrance>().getLoopStmt(), Pred);
+      return;
     case CFGElement::LifetimeEnds:
       return;
   }
 }
 
 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
                                      const CFGStmt S,
                                      const ExplodedNode *Pred,
for (ExplodedNodeSet::iterator I = CleanedStates.begin(),
     Visit(currStmt, *I, DstI);
     Dst.insert(DstI);
   }
 
   // Enqueue the new nodes onto the work list.
   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;
+
+  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);
+    }
+  }
 
-  LoopExit PP(S, Pred->getLocationContext());
-  Bldr.generateNode(PP, NewState, Pred);
+  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);
 }
 
 void ExprEngine::ProcessInitializer(const CFGInitializer Init,
                                     ExplodedNode *Pred) {
   const CXXCtorInitializer *BMI = Init.getInitializer();
 

 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   // If we reach a loop which has a known bound (and meets
   // other constraints) then consider completely unrolling it.
   if(AMgr.options.shouldUnrollLoops()) {
+    const LoopContext *CurrLoop = Pred->getLocationContext()->getCurrentLoop();
+    do {
       unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
       const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
-    if (Term) {
-      ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
-                                                 Pred, maxBlockVisitOnPath);
+
+      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;
   }
 
   // If this block is terminated by a loop and it has already been visited the
   // maximum number of times, widen the loop.
   unsigned int BlockCount = nodeBuilder.getContext().blockCount();
   if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
       AMgr.options.shouldWidenLoops()) {
switch (Loc.getKind()) {
         break;
 
       case ProgramPoint::LoopExitKind: {
         LoopExit LE = Loc.castAs<LoopExit>();
         Out << "LoopExit: " << LE.getLoopStmt()->getStmtClassName();
         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: ";
 
         // FIXME: Get proper printing options.
         PC.getDecl()->print(Out, LangOptions());
         printLocation(Out, PC.getLocation());
         break;
for (; LC; LC = LC->getParent(), ++Idx) {
           Out << " defined at ";
           printLocation2(Out, D->getLocStart());
         }
         break;
       case LocationContext::Scope:
         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";
     }
     Out << "\\l";
 
     state->printDOT(Out);
 
     Out << "\\l";

lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

 void ExprEngine::processCallExit(ExplodedNode *CEBNode) {
   // Step 1 CEBNode was generated before the call.
   PrettyStackTraceLocationContext CrashInfo(CEBNode->getLocationContext());
   const StackFrameContext *calleeCtx =
       CEBNode->getLocationContext()->getCurrentStackFrame();
 
   // 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();
   // Find the last statement in the function and the corresponding basic block.
   const Stmt *LastSt = nullptr;
   const CFGBlock *Blk = nullptr;
   std::tie(LastSt, Blk) = getLastStmt(CEBNode);
 
REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap,
                                                              unsigned))
 
 bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
                             NodeBuilder &Bldr, ExplodedNode *Pred,
                             ProgramStateRef State) {
   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);
   }
 
   // This may be NULL, but that's fine.
   const Expr *CallE = Call.getOriginExpr();
 
   // Construct a new stack frame for the callee.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// This file contains functions which are used to decide if a loop worth to be
 /// unrolled. Moreover, these functions manages the stack of loop which is
 /// tracked by the ProgramState.
 ///
 //===----------------------------------------------------------------------===//
 
-#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;
 using namespace clang::ast_matchers;
 
 static const int MAXIMUM_STEP_UNROLLED = 128;
 
 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) {
   return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
                               hasOperatorName("<="), hasOperatorName(">="),
                               hasOperatorName("!=")),
                         hasEitherOperand(ignoringParenImpCasts(declRefExpr(
                             to(varDecl(hasType(isInteger())).bind(BindName))))),
return forStmt(
                                 hasRHS(integerLiteral().bind("initNum"))))),
              // Incrementation should be a simple increment or decrement
              // operator call.
              hasIncrement(unaryOperator(
                  anyOf(hasOperatorName("++"), hasOperatorName("--")),
                  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) {
   // Global variables assumed as escaped variables.
   if (VD->hasGlobalStorage())
     return true;
 
   while (!N->pred_empty()) {
bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
   }
 
   if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
     maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
   else
     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);
 }
 
 bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
   const Stmt *S = nullptr;
   while (!N->pred_empty()) {
     if (N->succ_size() > 1)
       return true;
 
     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");
+
+  if (LM.contains(LoopCtx) && LM.lookup(LoopCtx)->isUnrolled() &&
+      madeNewBranch(Pred, LoopStmt))
+    return State->set<LoopMap>(LoopCtx, LoopState::getNormal(MaxVisitOnPath));
 
-  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));
+  if (LM.contains(LoopCtx))
     return State;
-  }
-
-  unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
 
-  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

lib/StaticAnalyzer/Core/PathDiagnostic.cpp

getLocationForCaller(const StackFrameContext *SFC,
   }
   case CFGElement::BaseDtor:
   case CFGElement::MemberDtor: {
     const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
     if (const Stmt *CallerBody = CallerInfo->getBody())
       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!");
   }
 
   llvm_unreachable("Unknown CFGElement kind");
 }
 
 PathDiagnosticLocation
 PathDiagnosticLocation::createBegin(const Decl *D,
const Stmt *PathDiagnosticLocation::getStmt(const ExplodedNode *N) {
   if (Optional<BlockEdge> BE = P.getAs<BlockEdge>())
     return BE->getSrc()->getTerminator();
   if (Optional<CallEnter> CE = P.getAs<CallEnter>())
     return CE->getCallExpr();
   if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>())
     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;
 }
 
 const Stmt *PathDiagnosticLocation::getNextStmt(const ExplodedNode *N) {
   for (N = N->getFirstSucc(); N; N = N->getFirstSucc()) {
     if (const Stmt *S = getStmt(N)) {
       // Check if the statement is '?' or '&&'/'||'.  These are "merges",

test/Analysis/loop-unrolling.cpp

for (int i = 0; i < getNum(); i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{1}}
     for (int j = 0; j < 33; j++) {
       clang_analyzer_numTimesReached(); // expected-warning {{4}}
     }
   }
   return 0;
 }
 
-
 void pr34943() {
   for (int i = 0; i < 6L; ++i) {
     clang_analyzer_numTimesReached(); // expected-warning {{6}}
   }
 }