[analyzer] StackFrameContext: Add NodeBuilderContext::blockCount() to its profile

[Charusso]

Summary

It allows discriminating between stack frames of the same call that is
called multiple times in a loop.

Thanks to Artem Dergachev for the great idea!

[Charusso]

clang/include/clang/Analysis/AnalysisDeclContext.h

486 ↗

(On Diff #212842)

Deadlines, eh?

clang/test/Analysis/loop-unrolling.cpp

371 ↗

(On Diff #212842)

The ninja check-clang-analyzer-z3 is not really working and we definitely have different results based on the traversal, so I just swapped that.

[NoQ]

Ah, omission of the century :/

Thanks, this looks immediately good!

clang/include/clang/Analysis/AnalysisDeclContext.h

305 ↗

(On Diff #212842)

"The number of times the Block has been visited. Allows discriminating between stack frames of the same call that is called multiple times in a loop."

clang/test/Analysis/loop-unrolling.cpp

349–353 ↗

(On Diff #212842)

I'm mildly curious what happened here.

[Charusso]

• Fix.

[Charusso]

clang/test/Analysis/loop-unrolling.cpp

349–353 ↗

(On Diff #212842)

I will leave that comment not 'Done' as some kind of FIXME: Measure the loop unrolling.
But I believe these numbers supposed to be here from the start when @george.karpenkov made the traversing coverage-based (source: https://youtu.be/4n3l-ZcDJNY?t=540).

[Charusso]

Thanks for the review and for the idea!

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

public:
   llvm::iterator_range<referenced_decls_iterator>
   getReferencedBlockVars(const BlockDecl *BD);
 
   /// 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 Stmt *S, const CFGBlock *Blk,
+                                         unsigned BlockCount, unsigned Idx);
 
   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.
class StackFrameContext : public LocationContext {
   friend class LocationContextManager;
 
   // The callsite where this stack frame is established.
   const Stmt *CallSite;
 
   // The parent block of the callsite.
   const CFGBlock *Block;
 
+  // The number of times the 'Block' has been visited.
+  // It allows discriminating between stack frames of the same call that is
+  // called multiple times in a loop.
+  const unsigned BlockCount;
+
   // The index of the callsite in the CFGBlock.
-  unsigned Index;
+  const unsigned Index;
 
   StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent,
-                    const Stmt *s, const CFGBlock *blk,
-                    unsigned idx,
-                    int64_t ID)
-      : LocationContext(StackFrame, ctx, parent, ID), CallSite(s),
-        Block(blk), Index(idx) {}
+                    const Stmt *s, const CFGBlock *blk, unsigned blockCount,
+                    unsigned idx, int64_t ID)
+      : LocationContext(StackFrame, ctx, parent, ID), CallSite(s), Block(blk),
+        BlockCount(blockCount), Index(idx) {}
 
 public:
   ~StackFrameContext() override = default;
 
   const Stmt *getCallSite() const { return CallSite; }
 
   const CFGBlock *getCallSiteBlock() const { return Block; }
 
   /// Return true if the current LocationContext has no caller context.
   bool inTopFrame() const override { return getParent() == nullptr;  }
 
   unsigned getIndex() const { return Index; }
 
   void Profile(llvm::FoldingSetNodeID &ID) override;
 
   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
                       const LocationContext *parent, const Stmt *s,
-                      const CFGBlock *blk, unsigned idx) {
+                      const CFGBlock *blk, unsigned blockCount, unsigned idx) {
     ProfileCommon(ID, StackFrame, ctx, parent, s);
     ID.AddPointer(blk);
+    ID.AddInteger(blockCount);
     ID.AddInteger(idx);
   }
 
   static bool classof(const LocationContext *Ctx) {
     return Ctx->getKind() == StackFrame;
   }
 };
 
class LocationContextManager {
   /// ID used for generating a new location context.
   int64_t NewID = 0;
 
 public:
   ~LocationContextManager();
 
   const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
                                          const LocationContext *parent,
-                                         const Stmt *s,
-                                         const CFGBlock *blk, unsigned idx);
+                                         const Stmt *s, const CFGBlock *blk,
+                                         unsigned blockCount, unsigned idx);
 
   const ScopeContext *getScope(AnalysisDeclContext *ctx,
                                const LocationContext *parent,
                                const Stmt *s);
 
   const BlockInvocationContext *
   getBlockInvocationContext(AnalysisDeclContext *ctx,
                             const LocationContext *parent,
CFG::BuildOptions &getCFGBuildOptions() {
     return cfgBuildOptions;
   }
 
   /// Return true if faux bodies should be synthesized for well-known
   /// functions.
   bool synthesizeBodies() const { return SynthesizeBodies; }
 
   const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx,
-                                         LocationContext const *Parent,
-                                         const Stmt *S,
-                                         const CFGBlock *Blk,
-                                         unsigned Idx) {
-    return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx);
+                                         const LocationContext *Parent,
+                                         const Stmt *S, const CFGBlock *Blk,
+                                         unsigned BlockCount, unsigned Idx) {
+    return LocContexts.getStackFrame(Ctx, Parent, S, Blk, BlockCount, Idx);
   }
 
   // Get the top level stack frame.
   const StackFrameContext *getStackFrame(const Decl *D) {
     return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr,
-                                     0);
+                                     0, 0);
   }
 
   // Get a stack frame with parent.
   StackFrameContext const *getStackFrame(const Decl *D,
-                                         LocationContext const *Parent,
-                                         const Stmt *S,
-                                         const CFGBlock *Blk,
-                                         unsigned Idx) {
-    return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx);
+                                         const LocationContext *Parent,
+                                         const Stmt *S, const CFGBlock *Blk,
+                                         unsigned BlockCount, unsigned Idx) {
+    return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, BlockCount,
+                                     Idx);
   }
 
   /// Get a reference to {@code BodyFarm} instance.
   BodyFarm &getBodyFarm();
 
   /// Discard all previously created AnalysisDeclContexts.
   void clear();
 

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h

public:
   /// Returns AnalysisDeclContext for the callee stack frame.
   /// Currently may fail; returns null on failure.
   AnalysisDeclContext *getCalleeAnalysisDeclContext() const;
 
   /// Returns the callee stack frame. That stack frame will only be entered
   /// during analysis if the call is inlined, but it may still be useful
   /// in intermediate calculations even if the call isn't inlined.
   /// May fail; returns null on failure.
-  const StackFrameContext *getCalleeStackFrame() const;
+  const StackFrameContext *getCalleeStackFrame(unsigned BlockCount) const;
 
   /// Returns memory location for a parameter variable within the callee stack
   /// frame. May fail; returns null on failure.
-  const VarRegion *getParameterLocation(unsigned Index) const;
+  const VarRegion *getParameterLocation(unsigned Index,
+                                        unsigned BlockCount) const;
 
   /// Returns true if on the current path, the argument was constructed by
   /// calling a C++ constructor over it. This is an internal detail of the
   /// analysis which doesn't necessarily represent the program semantics:
   /// if we are supposed to construct an argument directly, we may still
   /// not do that because we don't know how (i.e., construction context is
   /// unavailable in the CFG or not supported by the analyzer).
   bool isArgumentConstructedDirectly(unsigned Index) const {

cfe/trunk/lib/Analysis/AnalysisDeclContext.cpp

if (!AC)
     AC = llvm::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
   return AC.get();
 }
 
 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 CFGBlock *Blk, unsigned BlockCount,
+                                   unsigned Idx) {
+  return getLocationContextManager().getStackFrame(this, Parent, S, Blk,
+                                                   BlockCount, Idx);
 }
 
 const BlockInvocationContext *
 AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
                                                const BlockDecl *BD,
                                                const void *ContextData) {
   return getLocationContextManager().getBlockInvocationContext(this, parent,
                                                                BD, ContextData);
void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
                                     const void *data) {
   ID.AddInteger(ck);
   ID.AddPointer(ctx);
   ID.AddPointer(parent);
   ID.AddPointer(data);
 }
 
 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
-  Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
+  Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block,
+          BlockCount, Index);
 }
 
 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
   Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
 }
 
 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
   Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
 
   if (!L) {
     L = new LOC(ctx, parent, d, ++NewID);
     Contexts.InsertNode(L, InsertPos);
   }
   return L;
 }
 
-const StackFrameContext*
-LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
-                                      const LocationContext *parent,
-                                      const Stmt *s,
-                                      const CFGBlock *blk, unsigned idx) {
+const StackFrameContext *LocationContextManager::getStackFrame(
+    AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s,
+    const CFGBlock *blk, unsigned blockCount, unsigned idx) {
   llvm::FoldingSetNodeID ID;
-  StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
+  StackFrameContext::Profile(ID, ctx, parent, s, blk, blockCount, idx);
   void *InsertPos;
   auto *L =
    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
   if (!L) {
-    L = new StackFrameContext(ctx, parent, s, blk, idx, ++NewID);
+    L = new StackFrameContext(ctx, parent, s, blk, blockCount, idx, ++NewID);
     Contexts.InsertNode(L, InsertPos);
   }
   return L;
 }
 
 const ScopeContext *
 LocationContextManager::getScope(AnalysisDeclContext *ctx,
                                  const LocationContext *parent,

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

AnalysisDeclContext *CallEvent::getCalleeAnalysisDeclContext() const {
   // TODO: For now we skip virtual functions, because this also rises
   // the problem of which decl to use, but now it's across different classes.
   if (RD.mayHaveOtherDefinitions() || RD.getDecl() != ADC->getDecl())
     return nullptr;
 
   return ADC;
 }
 
-const StackFrameContext *CallEvent::getCalleeStackFrame() const {
+const StackFrameContext *
+CallEvent::getCalleeStackFrame(unsigned BlockCount) const {
   AnalysisDeclContext *ADC = getCalleeAnalysisDeclContext();
   if (!ADC)
     return nullptr;
 
   const Expr *E = getOriginExpr();
   if (!E)
     return nullptr;
 
CallEvent::getCalleeStackFrame(unsigned BlockCount) const {
   // Also recover CFG index by scanning the CFG block.
   unsigned Idx = 0, Sz = B->size();
   for (; Idx < Sz; ++Idx)
     if (auto StmtElem = (*B)[Idx].getAs<CFGStmt>())
       if (StmtElem->getStmt() == E)
         break;
   assert(Idx < Sz);
 
-  return ADC->getManager()->getStackFrame(ADC, LCtx, E, B, Idx);
+  return ADC->getManager()->getStackFrame(ADC, LCtx, E, B, BlockCount, Idx);
 }
 
-const VarRegion *CallEvent::getParameterLocation(unsigned Index) const {
-  const StackFrameContext *SFC = getCalleeStackFrame();
+const VarRegion *CallEvent::getParameterLocation(unsigned Index,
+                                                 unsigned BlockCount) const {
+  const StackFrameContext *SFC = getCalleeStackFrame(BlockCount);
   // We cannot construct a VarRegion without a stack frame.
   if (!SFC)
     return nullptr;
 
   // Retrieve parameters of the definition, which are different from
   // CallEvent's parameters() because getDecl() isn't necessarily
   // the definition. SFC contains the definition that would be used
   // during analysis.
for (unsigned Idx = 0, Count = getNumArgs(); Idx != Count; ++Idx) {
     // destructor has access to the temporary object after the call.
     // TODO: Support placement arguments once we start
     // constructing them directly.
     // TODO: This is unnecessary when there's no destructor, but that's
     // currently hard to figure out.
     if (getKind() != CE_CXXAllocator)
       if (isArgumentConstructedDirectly(Idx))
         if (auto AdjIdx = getAdjustedParameterIndex(Idx))
-          if (const VarRegion *VR = getParameterLocation(*AdjIdx))
+          if (const VarRegion *VR = getParameterLocation(*AdjIdx, BlockCount))
             ValuesToInvalidate.push_back(loc::MemRegionVal(VR));
   }
 
   // Invalidate designated regions using the batch invalidation API.
   // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
   //  global variables.
   return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(),
                                    BlockCount, getLocationContext(),

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

case ConstructionContext::ArgumentKind: {
       const auto *ACC = cast<ArgumentConstructionContext>(CC);
       const Expr *E = ACC->getCallLikeExpr();
       unsigned Idx = ACC->getIndex();
       const CXXBindTemporaryExpr *BTE = ACC->getCXXBindTemporaryExpr();
 
       CallEventManager &CEMgr = getStateManager().getCallEventManager();
       SVal V = UnknownVal();
       auto getArgLoc = [&](CallEventRef<> Caller) -> Optional<SVal> {
-        const LocationContext *FutureSFC = Caller->getCalleeStackFrame();
+        const LocationContext *FutureSFC =
+            Caller->getCalleeStackFrame(currBldrCtx->blockCount());
         // Return early if we are unable to reliably foresee
         // the future stack frame.
         if (!FutureSFC)
           return None;
 
         // This should be equivalent to Caller->getDecl() for now, but
         // FutureSFC->getDecl() is likely to support better stuff (like
         // virtual functions) earlier.
         const Decl *CalleeD = FutureSFC->getDecl();
 
         // FIXME: Support for variadic arguments is not implemented here yet.
         if (CallEvent::isVariadic(CalleeD))
           return None;
 
         // Operator arguments do not correspond to operator parameters
         // because this-argument is implemented as a normal argument in
         // operator call expressions but not in operator declarations.
         const VarRegion *VR = Caller->getParameterLocation(
-            *Caller->getAdjustedParameterIndex(Idx));
+            *Caller->getAdjustedParameterIndex(Idx), currBldrCtx->blockCount());
         if (!VR)
           return None;
 
         return loc::MemRegionVal(VR);
       };
 
       if (const auto *CE = dyn_cast<CallExpr>(E)) {
         CallEventRef<> Caller = CEMgr.getSimpleCall(CE, State, LCtx);

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

bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
   }
 
   // This may be NULL, but that's fine.
   const Expr *CallE = Call.getOriginExpr();
 
   // Construct a new stack frame for the callee.
   AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
   const StackFrameContext *CalleeSFC =
-    CalleeADC->getStackFrame(ParentOfCallee, CallE,
-                             currBldrCtx->getBlock(),
-                             currStmtIdx);
+      CalleeADC->getStackFrame(ParentOfCallee, CallE, currBldrCtx->getBlock(),
+                               currBldrCtx->blockCount(), currStmtIdx);
 
   CallEnter Loc(CallE, CalleeSFC, CurLC);
 
   // Construct a new state which contains the mapping from actual to
   // formal arguments.
   State = State->enterStackFrame(Call, CalleeSFC);
 
   bool isNew;

cfe/trunk/test/Analysis/loop-block-counts.c

 // RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
 
 void clang_analyzer_eval(int);
 
 void callee(void **p) {
   int x;
   *p = &x;
 }
 
 void loop() {
   void *arr[2];
   for (int i = 0; i < 2; ++i)
     callee(&arr[i]);
   // FIXME: Should be UNKNOWN.
-  clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{TRUE}}
+  clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{FALSE}}
 }
 
 void loopWithCall() {
   void *arr[2];
   for (int i = 0; i < 2; ++i) {
     int x;
     arr[i] = &x;
   }
   // FIXME: Should be UNKNOWN.
   clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{TRUE}}
 }

cfe/trunk/test/Analysis/loop-unrolling.cpp

for (int i = 2; i < 12; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{90}}
   }
   return 0;
 }
 
 int simple_unknown_bound_loop() {
   for (int i = 2; i < getNum(); i++) {
 #ifdef DFS
-    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    clang_analyzer_numTimesReached(); // expected-warning {{16}}
 #else
-    clang_analyzer_numTimesReached(); // expected-warning {{13}}
+    clang_analyzer_numTimesReached(); // expected-warning {{8}}
 #endif
   }
   return 0;
 }
 
 int nested_inlined_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{9}}
     k = simple_known_bound_loop();    // no reevaluation without inlining
   }
   int a = 22 / k; // expected-warning {{Division by zero}}
   return 0;
 }
 
 int nested_inlined_no_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
-#ifdef ANALYZER_CM_Z3
-    clang_analyzer_numTimesReached(); // expected-warning {{13}}
+#ifdef DFS
+    clang_analyzer_numTimesReached(); // expected-warning {{18}}
 #else
-    clang_analyzer_numTimesReached(); // expected-warning {{15}}
+    clang_analyzer_numTimesReached(); // expected-warning {{14}}
 #endif
     k = simple_unknown_bound_loop();  // reevaluation without inlining, splits the state as well
   }
   int a = 22 / k; // no-warning
   return 0;
 }
 
 int recursion_unroll1(bool b) {

cfe/trunk/test/Analysis/stack-frame-context-revision.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,cplusplus.NewDelete -verify %s
+
+// expected-no-diagnostics:
+// From now the profile of the 'StackFrameContext' also contains the
+// 'NodeBuilderContext::blockCount()'. With this addition we can distinguish
+// between the 'StackArgumentsSpaceRegion' of the 'P' arguments being different
+// on every iteration.
+
+typedef __INTPTR_TYPE__ intptr_t;
+
+template <typename PointerTy>
+struct SmarterPointer {
+  PointerTy getFromVoidPointer(void *P) const {
+    return static_cast<PointerTy>(P);
+  }
+
+  PointerTy getPointer() const {
+    return getFromVoidPointer(reinterpret_cast<void *>(Value));
+  }
+
+  intptr_t Value = 13;
+};
+
+struct Node {
+  SmarterPointer<Node *> Pred;
+};
+
+void test(Node *N) {
+  while (N) {
+    SmarterPointer<Node *> Next = N->Pred;
+    delete N;
+
+    N = Next.getPointer();
+    // no-warning: 'Use of memory after it is freed' was here as the same
+    //             'StackArgumentsSpaceRegion' purged out twice as 'P'.
+  }
+}