[analyzer] Improve performance of NoStoreFuncVisitor

[george.karpenkov]

Summary

Compute modifying frames lazily on demand.
NB: two sets can be indeed replaced by a map, but IMO readability would suffer, and the performance gain would be tiny.

[NoQ]

We've had a 4x analysis time increase on a specific file due to this code interacting in weird manner with temporary constructor inlining.

Thanks for fixing this! :)

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

 /// for which  the region of interest \p RegionOfInterest was passed into,
 /// but not written inside, and it has caused an undefined read or a null
 /// pointer dereference outside.
 class NoStoreFuncVisitor final
     : public BugReporterVisitorImpl<NoStoreFuncVisitor> {
   const SubRegion *RegionOfInterest;
   static constexpr const char *DiagnosticsMsg =
       "Returning without writing to '";
-  bool Initialized = false;
 
   /// Frames writing into \c RegionOfInterest.
   /// This visitor generates a note only if a function does not write into
   /// a region of interest. This information is not immediately available
   /// by looking at the node associated with the exit from the function
   /// (usually the return statement). To avoid recomputing the same information
   /// many times (going up the path for each node and checking whether the
-  /// region was written into) we instead pre-compute and store all
-  /// stack frames along the path which write into the region of interest
-  /// on the first \c VisitNode invocation.
+  /// region was written into) we instead lazily compute the
+  /// stack frames along the path which write into the region of interest.
   llvm::SmallPtrSet<const StackFrameContext *, 32> FramesModifyingRegion;
+  llvm::SmallPtrSet<const StackFrameContext *, 32> FramesModifyingCalculated;
 
 public:
   NoStoreFuncVisitor(const SubRegion *R) : RegionOfInterest(R) {}
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     static int Tag = 0;
     ID.AddPointer(&Tag);
   }
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
                                                  const ExplodedNode *PrevN,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override {
-    if (!Initialized) {
-      findModifyingFrames(N);
-      Initialized = true;
-    }
 
     const LocationContext *Ctx = N->getLocationContext();
     const StackFrameContext *SCtx = Ctx->getCurrentStackFrame();
     ProgramStateRef State = N->getState();
     auto CallExitLoc = N->getLocationAs<CallExitBegin>();
 
     // No diagnostic if region was modified inside the frame.
-    if (!CallExitLoc || FramesModifyingRegion.count(SCtx))
+    if (!CallExitLoc)
       return nullptr;
 
     CallEventRef<> Call =
         BRC.getStateManager().getCallEventManager().getCaller(SCtx, State);
 
     const PrintingPolicy &PP = BRC.getASTContext().getPrintingPolicy();
     const SourceManager &SM = BRC.getSourceManager();
     if (const auto *CCall = dyn_cast<CXXConstructorCall>(Call)) {
       const MemRegion *ThisRegion = CCall->getCXXThisVal().getAsRegion();
-      if (RegionOfInterest->isSubRegionOf(ThisRegion) &&
-          !CCall->getDecl()->isImplicit())
+      if (RegionOfInterest->isSubRegionOf(ThisRegion)
+          && !CCall->getDecl()->isImplicit()
+          && !isRegionOfInterestModifiedInFrame(N))
         return notModifiedInConstructorDiagnostics(Ctx, SM, PP, *CallExitLoc,
                                                    CCall, ThisRegion);
     }
 
     ArrayRef<ParmVarDecl *> parameters = getCallParameters(Call);
     for (unsigned I = 0, E = Call->getNumArgs(); I != E; ++I) {
       const ParmVarDecl *PVD = parameters[I];
       SVal S = Call->getArgSVal(I);
       unsigned IndirectionLevel = 1;
       QualType T = PVD->getType();
       while (const MemRegion *R = S.getAsRegion()) {
-        if (RegionOfInterest->isSubRegionOf(R) &&
-            !isPointerToConst(PVD->getType()))
+        if (RegionOfInterest->isSubRegionOf(R)
+            && !isPointerToConst(PVD->getType())) {
+
+          if (isRegionOfInterestModifiedInFrame(N))
+            return nullptr;
+
           return notModifiedDiagnostics(
               Ctx, SM, PP, *CallExitLoc, Call, PVD, R, IndirectionLevel);
+        }
         QualType PT = T->getPointeeType();
         if (PT.isNull() || PT->isVoidType()) break;
         S = State->getSVal(R, PT);
         T = PT;
         IndirectionLevel++;
       }
     }
 
     return nullptr;
   }
 
 private:
+  /// Check and lazily calculate whether the region of interest is
+  /// modified in the stack frame to which \p N belongs.
+  /// The calculation is cached in FramesModifyingRegion.
+  bool isRegionOfInterestModifiedInFrame(const ExplodedNode *N) {
+    const LocationContext *Ctx = N->getLocationContext();
+    const StackFrameContext *SCtx = Ctx->getCurrentStackFrame();
+    if (!FramesModifyingCalculated.count(SCtx))
+      findModifyingFrames(N);
+    return FramesModifyingRegion.count(SCtx);
+  }
+
+
   /// Write to \c FramesModifyingRegion all stack frames along
-  /// the path which modify \c RegionOfInterest.
+  /// the path in the current stack frame which modify \c RegionOfInterest.
   void findModifyingFrames(const ExplodedNode *N) {
-    ProgramStateRef LastReturnState;
+    assert(N->getLocationAs<CallExitBegin>());
+    ProgramStateRef LastReturnState = N->getState();
+    SVal ValueAtReturn = LastReturnState->getSVal(RegionOfInterest);
+    const LocationContext *Ctx = N->getLocationContext();
+    const StackFrameContext *OriginalSCtx = Ctx->getCurrentStackFrame();
+
     do {
       ProgramStateRef State = N->getState();
       auto CallExitLoc = N->getLocationAs<CallExitBegin>();
       if (CallExitLoc) {
         LastReturnState = State;
+        ValueAtReturn = LastReturnState->getSVal(RegionOfInterest);
       }
-      if (LastReturnState &&
-          wasRegionOfInterestModifiedAt(N, LastReturnState)) {
+
+      FramesModifyingCalculated.insert(
+        N->getLocationContext()->getCurrentStackFrame());
+
+      if (wasRegionOfInterestModifiedAt(N, LastReturnState, ValueAtReturn)) {
         const StackFrameContext *SCtx =
             N->getLocationContext()->getCurrentStackFrame();
         while (!SCtx->inTopFrame()) {
           auto p = FramesModifyingRegion.insert(SCtx);
           if (!p.second)
             break; // Frame and all its parents already inserted.
           SCtx = SCtx->getParent()->getCurrentStackFrame();
         }
       }
 
+      // Stop calculation at the call to the current function.
+      if (auto CE = N->getLocationAs<CallEnter>())
+        if (CE->getCalleeContext() == OriginalSCtx)
+          break;
+
       N = N->getFirstPred();
     } while (N);
   }
 
   /// \return Whether \c RegionOfInterest was modified at \p N,
   /// where \p ReturnState is a state associated with the return
   /// from the current frame.
   bool wasRegionOfInterestModifiedAt(const ExplodedNode *N,
-                                     ProgramStateRef ReturnState) {
-    SVal ValueAtReturn = ReturnState->getSVal(RegionOfInterest);
+                                     ProgramStateRef ReturnState,
+                                     SVal ValueAtReturn) {
+    if (!N->getLocationAs<PostStore>()
+        && !N->getLocationAs<PostInitializer>()
+        && !N->getLocationAs<PostStmt>())
+      return false;
 
     // Writing into region of interest.
     if (auto PS = N->getLocationAs<PostStmt>())
       if (auto *BO = PS->getStmtAs<BinaryOperator>())
         if (BO->isAssignmentOp() && RegionOfInterest->isSubRegionOf(
                                         N->getSVal(BO->getLHS()).getAsRegion()))
           return true;