[analyzer] Remove the "postponed" hack, deal with derived symbols using an extra map

[george.karpenkov]

Summary

The "derived" symbols indicate children fields of a larger symbol.
As parents do not have pointers to their children, the garbage collection algorithm the analyzer currently uses adds such symbols into a "postponed" category, and then keeps running through the worklist until the fixed point is reached.

The current patch rectifies that by instead using a helper map which stores pointers from parents to children, so that no fixed point calculation is necessary.

The current patch yields ~5% improvement in running time on sqlite.

[NoQ]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2509

I suspect that this is unnecessary. We are guaranteed that R is live, therefore we are guaranteed that RVS is live.

2539–2541

Loc::isLocType()?

2544

Let's make whitespace consistent.

2548–2549

The constructor of SymbolicRegion contains an assertion that no other symbolic regions are possible.

Let's add comment to that assertion that RegionStore now relies on that and needs to be updated if more cases are introduced.

[NoQ]

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

773 ↗

(On Diff #163238)

Actually, let's assert even more: in the HeapSpaceRegion case, s is always SymbolConjured.

Also maybe let's point directly to populateWorklistFromSymbol() in the comment, otherwise nobody would have an idea what to look for, but if we point to a function then even if the function gets renamed the reader would be able to pick it up from the history.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2527

Formatting.

[NoQ]

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

2539–2543 ↗

(On Diff #164526)

Argh, this isn't enough.

In a nutshell, this code says "Uhm, is this symbol $x (say, reg_$N<x>) now live and it is a pointer? Ok, RegionStore, re-check the symbolic region *$x (aka SymRegion{reg_$N<x>})." Which is good. By "re-check" we mean "add it to the RegionStore's worklist", which would cause re-exploration of *bindings* within it. However, not every value stored in a region is a binding within the region! For instance, all values within **$x (aka SymRegion{reg_$M<SymRegion{reg_$N<x>}} are also kept alive, which we will fail to mark live when, say, *x has no bindings at all - SymbolRegionValue is still presumed to be there.

It would have been fine if it was just sub-regions, but in fact an infinite tree of *base* regions (namely, symbolic regions of non-assigned/invalidated pointer-type sub-regions) also become live every time a region becomes live, while only a finite amount of base regions become reachable when the traversal method implemented here gets applied.

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

public:
   /// getInitialStore - Returns the initial "empty" store representing the
   ///  value bindings upon entry to an analyzed function.
   virtual StoreRef getInitialStore(const LocationContext *InitLoc) = 0;
 
   /// getRegionManager - Returns the internal RegionManager object that is
   ///  used to query and manipulate MemRegion objects.
   MemRegionManager& getRegionManager() { return MRMgr; }
 
+  SValBuilder& getSValBuilder() { return svalBuilder; }
+
   virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) {
     return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC));
   }
 
   Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL,
                                const LocationContext *LC) {
     return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC));
   }

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

   return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val);
 }
 
 //===----------------------------------------------------------------------===//
 // State pruning.
 //===----------------------------------------------------------------------===//
 
 namespace {
-class RemoveDeadBindingsWorker :
-  public ClusterAnalysis<RemoveDeadBindingsWorker> {
-  SmallVector<const SymbolicRegion*, 12> Postponed;
+class RemoveDeadBindingsWorker
+    : public ClusterAnalysis<RemoveDeadBindingsWorker> {
+
+  using ChildrenListTy = SmallVector<const SymbolDerived *, 4>;
+  using MapParentsToDerivedTy = llvm::DenseMap<SymbolRef, ChildrenListTy>;
+
+  MapParentsToDerivedTy ParentsToDerived;
   SymbolReaper &SymReaper;
   const StackFrameContext *CurrentLCtx;
 
 public:
   RemoveDeadBindingsWorker(RegionStoreManager &rm,
                            ProgramStateManager &stateMgr,
                            RegionBindingsRef b, SymbolReaper &symReaper,
                            const StackFrameContext *LCtx)
     : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b),
       SymReaper(symReaper), CurrentLCtx(LCtx) {}
 
   // Called by ClusterAnalysis.
   void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);
   void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);
   using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster;
 
   using ClusterAnalysis::AddToWorkList;
 
   bool AddToWorkList(const MemRegion *R);
 
-  bool UpdatePostponed();
   void VisitBinding(SVal V);
+
+private:
+  void populateWorklistFromSymbol(SymbolRef s);
 };
 }
 
 bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) {
   const MemRegion *BaseR = R->getBaseRegion();
   return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
 }
 
 void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
                                                    const ClusterBindings &C) {
 
   if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
     if (SymReaper.isLive(VR))
       AddToWorkList(baseR, &C);
 
     return;
   }
 
   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
-    if (SymReaper.isLive(SR->getSymbol()))
+    if (SymReaper.isLive(SR->getSymbol())) {
       AddToWorkList(SR, &C);
-    else
-      Postponed.push_back(SR);
+    } else if (const auto *SD = dyn_cast<SymbolDerived>(SR->getSymbol())) {
+      ParentsToDerived[SD->getParentSymbol()].push_back(SD);
+    }
 
     return;
   }
 
   if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
     AddToWorkList(baseR, &C);
     return;
   }
 
   // CXXThisRegion in the current or parent location context is live.
   if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
-    const StackArgumentsSpaceRegion *StackReg =
+    const auto *StackReg =
       cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
     const StackFrameContext *RegCtx = StackReg->getStackFrame();
     if (CurrentLCtx &&
         (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)))
       AddToWorkList(TR, &C);
   }
 }
 

       VisitBinding(*I);
 
     return;
   }
 
   // If V is a region, then add it to the worklist.
   if (const MemRegion *R = V.getAsRegion()) {
     AddToWorkList(R);
+
+    if (const auto *TVR = dyn_cast<TypedValueRegion>(R)) {
+      DefinedOrUnknownSVal RVS =
+          RM.getSValBuilder().getRegionValueSymbolVal(TVR);
+      if (const MemRegion *SR = RVS.getAsRegion()) {
+        SymReaper.markLive(SR);
+        AddToWorkList(SR);
+      }
+    }
+
     SymReaper.markLive(R);
 
     // All regions captured by a block are also live.
     if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
       BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
                                                 E = BR->referenced_vars_end();
       for ( ; I != E; ++I)
         AddToWorkList(I.getCapturedRegion());
     }
   }
 
 
   // Update the set of live symbols.
-  for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end();
-       SI!=SE; ++SI)
+  for (auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI) {
+    populateWorklistFromSymbol(*SI);
+
+    for (const auto *SD : ParentsToDerived[*SI])
+      populateWorklistFromSymbol(SD);
+
     SymReaper.markLive(*SI);
+  }
 }
 
-bool RemoveDeadBindingsWorker::UpdatePostponed() {
-  // See if any postponed SymbolicRegions are actually live now, after
-  // having done a scan.
-  bool changed = false;
+void RemoveDeadBindingsWorker::populateWorklistFromSymbol(SymbolRef S) {
+  if (const auto *SD = dyn_cast<SymbolData>(S)) {
+    if ((SD->getType()->isAnyPointerType()
+         || SD->getType()->isReferenceType()
+         || SD->getType()->isBlockPointerType()) && !SymReaper.isLive(SD)) {
 
-  for (SmallVectorImpl<const SymbolicRegion*>::iterator
-        I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) {
-    if (const SymbolicRegion *SR = *I) {
-      if (SymReaper.isLive(SR->getSymbol())) {
-        changed |= AddToWorkList(SR);
-        *I = nullptr;
-      }
+      const SymbolicRegion *SR = RM.getRegionManager().getSymbolicRegion(SD);
+
+      if (B.contains(SR))
+        AddToWorkList(SR);
+
+      const SymbolicRegion *SHR =
+          RM.getRegionManager().getSymbolicHeapRegion(SD);
+      if (B.contains(SHR))
+        AddToWorkList(SHR);
     }
   }
-
-  return changed;
 }
 
 StoreRef RegionStoreManager::removeDeadBindings(Store store,
                                                 const StackFrameContext *LCtx,
                                                 SymbolReaper& SymReaper) {
   RegionBindingsRef B = getRegionBindings(store);
   RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
   W.GenerateClusters();
 
   // Enqueue the region roots onto the worklist.
   for (SymbolReaper::region_iterator I = SymReaper.region_begin(),
        E = SymReaper.region_end(); I != E; ++I) {
     W.AddToWorkList(*I);
   }
 
-  do W.RunWorkList(); while (W.UpdatePostponed());
+  W.RunWorkList();
 
   // We have now scanned the store, marking reachable regions and symbols
   // as live.  We now remove all the regions that are dead from the store
   // as well as update DSymbols with the set symbols that are now dead.
   for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
     const MemRegion *Base = I.getKey();
 
     // If the cluster has been visited, we know the region has been marked.