[StaticAnalyzer] Handle LoopExit CFGElement in the analyzer

[szepet]

Summary

This patch adds handling of the LoopExit CFGElements to the StaticAnalyzer.
This is reached by introducing a new ProgramPoint.

[szepet]

Accidentally left debug print removed.

[dcoughlin]

include/clang/Analysis/ProgramPoint.h

658 ↗

(On Diff #108312)

Can you add a comment explaining what meaning of this program point is.

lib/StaticAnalyzer/Core/CoreEngine.cpp

586 ↗

(On Diff #108312)

I'm surprised both this and the checks for N's location above are needed. How does this arise?

[szepet]

Updates based on comments.

[szepet]

include/clang/Analysis/ProgramPoint.h

658 ↗

(On Diff #108312)

Can you help me with that? I am not sure what is important to say about this point to understand it better than from its name.

lib/StaticAnalyzer/Core/CoreEngine.cpp

586 ↗

(On Diff #108312)

We don't need both of the checks, I just left it by mistake.

[dcoughlin]

Looks good to me! (Please expand the comment, though.)

include/clang/Analysis/ProgramPoint.h

658 ↗

(On Diff #108312)

My recommendation would be to think about it from the perspective of someone new to the codebase trying to understand when the analyzer will reach such a program point. What additional context will they need that is not conveyed in the name alone?

At a minimum, I think it is worth mentioning that a LoopExit point can arise even when a loop is not entered and that not all loop exits will result in a LoopExit program point.

[dcoughlin]

Also, please mention in the commit message that tests will be added in a following commit.

cfe/trunk/include/clang/Analysis/ProgramPoint.h

enum Kind { BlockEdgeKind,
               PostInitializerKind,
               CallEnterKind,
               CallExitBeginKind,
               CallExitEndKind,
               PreImplicitCallKind,
               PostImplicitCallKind,
               MinImplicitCallKind = PreImplicitCallKind,
               MaxImplicitCallKind = PostImplicitCallKind,
+              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
   // context insensitive analysis.

 private:
   friend class ProgramPoint;
   CallExitEnd() {}
   static bool isKind(const ProgramPoint &Location) {
     return Location.getKind() == CallExitEndKind;
   }
 };
 
+/// 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.
+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());
+    }
+
+private:
+    friend class ProgramPoint;
+    LoopExit() {}
+    static bool isKind(const ProgramPoint &Location) {
+      return Location.getKind() == LoopExitKind;
+    }
+};
+
 /// This is a meta program point, which should be skipped by all the diagnostic
 /// reasoning etc.
 class EpsilonPoint : public ProgramPoint {
 public:
   EpsilonPoint(const LocationContext *L, const void *Data1,
                const void *Data2 = nullptr,
                const ProgramPointTag *tag = nullptr)
     : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}

cfe/trunk/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 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);

cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp

case ProgramPoint::EpsilonKind: {
       ExplodedNode *PNode = Pred->getFirstPred();
       dispatchWorkItem(Pred, PNode->getLocation(), WU);
       break;
     }
     default:
       assert(Loc.getAs<PostStmt>() ||
              Loc.getAs<PostInitializer>() ||
              Loc.getAs<PostImplicitCall>() ||
-             Loc.getAs<CallExitEnd>());
+             Loc.getAs<CallExitEnd>() ||
+             Loc.getAs<LoopExit>());
       HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
       break;
   }
 }
 
 bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
                                                  unsigned Steps,
                                                  ProgramStateRef InitState,
if (N->getLocation().getAs<CallEnter>()) {
     // Still use the index of the CallExpr. It's needed to create the callee
     // 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<PostImplicitCall>()||
+      N->getLocation().getAs<LoopExit>()) {
     WList->enqueue(N, Block, Idx+1);
     return;
   }
 
   if (N->getLocation().getAs<EpsilonPoint>()) {
     WList->enqueue(N, Block, Idx);
     return;
   }

cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp

case CFGElement::NewAllocator:
       return;
     case CFGElement::AutomaticObjectDtor:
     case CFGElement::DeleteDtor:
     case CFGElement::BaseDtor:
     case CFGElement::MemberDtor:
     case CFGElement::TemporaryDtor:
       ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
       return;
-    case CFGElement::LifetimeEnds:
     case CFGElement::LoopExit:
+      ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
+      return;
+    case CFGElement::LifetimeEnds:
       return;
   }
 }
 
 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
                                      const CFGStmt S,
                                      const ExplodedNode *Pred,
                                      const LocationContext *LC) {
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) {
+  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
+                                S->getLocStart(),
+                                "Error evaluating end of the loop");
+  ExplodedNodeSet Dst;
+  Dst.Add(Pred);
+  NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
+
+  LoopExit PP(S, Pred->getLocationContext());
+  Bldr.generateNode(PP, Pred->getState(), 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();
 
   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
                                 BMI->getSourceLocation(),
                                 "Error evaluating initializer");
 
switch (Loc.getKind()) {
       case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
         Out << "PreStmtPurgeDeadSymbols";
         break;
 
       case ProgramPoint::EpsilonKind:
         Out << "Epsilon Point";
         break;
 
+      case ProgramPoint::LoopExitKind: {
+        LoopExit LE = Loc.castAs<LoopExit>();
+        Out << "LoopExit: " << 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;