[analyzer] Teach invalidateRegions that regions within LazyCompoundVal need to be invalidated

Refactor invalidateRegions to take SVals instead of Regions as input and teach RegionStore
about processing LazyCompoundVal as a top-level “escaping” value.

This addresses several false positives that get triggered by the NewDelete checker, but the
underlying issue is reproducible with other checkers as well (for example, MallocChecker).

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@178518 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 127 insertions, 54 deletions

diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp
index 78400ba359..45b2e219d9 100644
--- a/lib/StaticAnalyzer/Core/CallEvent.cpp
+++ b/lib/StaticAnalyzer/Core/CallEvent.cpp
@@ -140,9 +140,10 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
                                              ProgramStateRef Orig) const {
   ProgramStateRef Result = (Orig ? Orig : getState());
 
-  SmallVector<const MemRegion *, 8> ConstRegions;
-  SmallVector<const MemRegion *, 8> RegionsToInvalidate;
-  getExtraInvalidatedRegions(RegionsToInvalidate);
+  SmallVector<SVal, 8> ConstValues;
+  SmallVector<SVal, 8> ValuesToInvalidate;
+
+  getExtraInvalidatedValues(ValuesToInvalidate);
 
   // Indexes of arguments whose values will be preserved by the call.
   llvm::SmallSet<unsigned, 4> PreserveArgs;
@@ -150,25 +151,21 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
     findPtrToConstParams(PreserveArgs, *this);
 
   for (unsigned Idx = 0, Count = getNumArgs(); Idx != Count; ++Idx) {
-    const MemRegion *R = getArgSVal(Idx).getAsRegion();
-    if (!R)
-      continue;
-
     // Mark this region for invalidation.  We batch invalidate regions
     // below for efficiency.
     if (PreserveArgs.count(Idx))
-      ConstRegions.push_back(R);
+      ConstValues.push_back(getArgSVal(Idx));
     else
-      RegionsToInvalidate.push_back(R);
+      ValuesToInvalidate.push_back(getArgSVal(Idx));
   }
 
   // Invalidate designated regions using the batch invalidation API.
   // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
   //  global variables.
-  return Result->invalidateRegions(RegionsToInvalidate, getOriginExpr(),
+  return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(),
                                    BlockCount, getLocationContext(),
                                    /*CausedByPointerEscape*/ true,
-                                   /*Symbols=*/0, this, ConstRegions);
+                                   /*Symbols=*/0, this, ConstValues);
 }
 
 ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
@@ -374,9 +371,8 @@ const FunctionDecl *CXXInstanceCall::getDecl() const {
   return getSVal(CE->getCallee()).getAsFunctionDecl();
 }
 
-void CXXInstanceCall::getExtraInvalidatedRegions(RegionList &Regions) const {
-  if (const MemRegion *R = getCXXThisVal().getAsRegion())
-    Regions.push_back(R);
+void CXXInstanceCall::getExtraInvalidatedValues(ValueList &Values) const {
+  Values.push_back(getCXXThisVal());
 }
 
 SVal CXXInstanceCall::getCXXThisVal() const {
@@ -529,10 +525,10 @@ CallEvent::param_iterator BlockCall::param_end() const {
   return D->param_end();
 }
 
-void BlockCall::getExtraInvalidatedRegions(RegionList &Regions) const {
+void BlockCall::getExtraInvalidatedValues(ValueList &Values) const {
   // FIXME: This also needs to invalidate captured globals.
   if (const MemRegion *R = getBlockRegion())
-    Regions.push_back(R);
+    Values.push_back(loc::MemRegionVal(R));
 }
 
 void BlockCall::getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
@@ -550,9 +546,9 @@ SVal CXXConstructorCall::getCXXThisVal() const {
   return UnknownVal();
 }
 
-void CXXConstructorCall::getExtraInvalidatedRegions(RegionList &Regions) const {
+void CXXConstructorCall::getExtraInvalidatedValues(ValueList &Values) const {
   if (Data)
-    Regions.push_back(static_cast<const MemRegion *>(Data));
+    Values.push_back(loc::MemRegionVal(static_cast<const MemRegion *>(Data)));
 }
 
 void CXXConstructorCall::getInitialStackFrameContents(
@@ -604,9 +600,8 @@ CallEvent::param_iterator ObjCMethodCall::param_end() const {
 }
 
 void
-ObjCMethodCall::getExtraInvalidatedRegions(RegionList &Regions) const {
-  if (const MemRegion *R = getReceiverSVal().getAsRegion())
-    Regions.push_back(R);
+ObjCMethodCall::getExtraInvalidatedValues(ValueList &Values) const {
+  Values.push_back(getReceiverSVal());
 }
 
 SVal ObjCMethodCall::getSelfSVal() const {
diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp
index 9aac8df0a2..ebce0c1f4d 100644
--- a/lib/StaticAnalyzer/Core/ProgramState.cpp
+++ b/lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -141,6 +141,7 @@ ProgramStateRef ProgramState::bindDefault(SVal loc, SVal V) const {
 }
 
 typedef ArrayRef<const MemRegion *> RegionList;
+typedef ArrayRef<SVal> ValueList;
 
 ProgramStateRef 
 ProgramState::invalidateRegions(RegionList Regions,
@@ -150,54 +151,92 @@ ProgramState::invalidateRegions(RegionList Regions,
                                 InvalidatedSymbols *IS,
                                 const CallEvent *Call,
                                 RegionList ConstRegions) const {
+  SmallVector<SVal, 8> Values;
+  for (RegionList::const_iterator I = Regions.begin(),
+                                  E = Regions.end(); I != E; ++I)
+    Values.push_back(loc::MemRegionVal(*I));
+
+  SmallVector<SVal, 8> ConstValues;
+  for (RegionList::const_iterator I = ConstRegions.begin(),
+                                  E = ConstRegions.end(); I != E; ++I)
+    ConstValues.push_back(loc::MemRegionVal(*I));
+
   if (!IS) {
     InvalidatedSymbols invalidated;
-    return invalidateRegionsImpl(Regions, E, Count, LCtx,
+    return invalidateRegionsImpl(Values, E, Count, LCtx,
                                  CausedByPointerEscape,
-                                 invalidated, Call, ConstRegions);
+                                 invalidated, Call, ConstValues);
   }
-  return invalidateRegionsImpl(Regions, E, Count, LCtx, CausedByPointerEscape,
-                               *IS, Call, ConstRegions);
+  return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
+                               *IS, Call, ConstValues);
 }
 
-ProgramStateRef 
-ProgramState::invalidateRegionsImpl(RegionList Regions,
+ProgramStateRef
+ProgramState::invalidateRegions(ValueList Values,
+                                const Expr *E, unsigned Count,
+                                const LocationContext *LCtx,
+                                bool CausedByPointerEscape,
+                                InvalidatedSymbols *IS,
+                                const CallEvent *Call,
+                                ValueList ConstValues) const {
+  if (!IS) {
+    InvalidatedSymbols invalidated;
+    return invalidateRegionsImpl(Values, E, Count, LCtx,
+                                 CausedByPointerEscape,
+                                 invalidated, Call, ConstValues);
+  }
+  return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
+                               *IS, Call, ConstValues);
+}
+
+ProgramStateRef
+ProgramState::invalidateRegionsImpl(ValueList Values,
                                     const Expr *E, unsigned Count,
                                     const LocationContext *LCtx,
                                     bool CausedByPointerEscape,
                                     InvalidatedSymbols &IS,
                                     const CallEvent *Call,
-                                    RegionList ConstRegions) const {
+                                    ValueList ConstValues) const {
   ProgramStateManager &Mgr = getStateManager();
   SubEngine* Eng = Mgr.getOwningEngine();
   InvalidatedSymbols ConstIS;
 
   if (Eng) {
+    StoreManager::InvalidatedRegions TopLevelInvalidated;
+    StoreManager::InvalidatedRegions TopLevelConstInvalidated;
     StoreManager::InvalidatedRegions Invalidated;
     const StoreRef &newStore
-      = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS,
-                                        Call, ConstRegions, ConstIS,
-                                        &Invalidated);
+    = Mgr.StoreMgr->invalidateRegions(getStore(), Values, ConstValues,
+                                      E, Count, LCtx, Call,
+                                      IS, ConstIS,
+                                      &TopLevelInvalidated,
+                                      &TopLevelConstInvalidated,
+                                      &Invalidated);
 
     ProgramStateRef newState = makeWithStore(newStore);
 
     if (CausedByPointerEscape) {
-      newState = Eng->notifyCheckersOfPointerEscape(newState,
-                                               &IS, Regions, Invalidated, Call);
-      if (!ConstRegions.empty()) {
+      newState = Eng->notifyCheckersOfPointerEscape(newState, &IS,
+                                                    TopLevelInvalidated,
+                                                    Invalidated, Call);
+      if (!ConstValues.empty()) {
         StoreManager::InvalidatedRegions Empty;
         newState = Eng->notifyCheckersOfPointerEscape(newState, &ConstIS,
-                                                      ConstRegions, Empty, Call,
+                                                      TopLevelConstInvalidated,
+                                                      Empty, Call,
                                                       true);
       }
     }
 
-    return Eng->processRegionChanges(newState, &IS, Regions, Invalidated, Call);
+    return Eng->processRegionChanges(newState, &IS,
+                                     TopLevelInvalidated, Invalidated,
+                                     Call);
   }
 
   const StoreRef &newStore =
-    Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS,
-                                    Call, ConstRegions, ConstIS, NULL);
+  Mgr.StoreMgr->invalidateRegions(getStore(), Values, ConstValues,
+                                  E, Count, LCtx, Call,
+                                  IS, ConstIS, NULL, NULL, NULL);
   return makeWithStore(newStore);
 }
 
diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 08110dd3b9..514fe256cd 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -318,6 +318,7 @@ public:
 //===----------------------------------------------------------------------===//
 
 namespace {
+class invalidateRegionsWorker;
 
 class RegionStoreManager : public StoreManager {
 public:
@@ -331,6 +332,13 @@ private:
                          SValListTy> LazyBindingsMapTy;
   LazyBindingsMapTy LazyBindingsMap;
 
+  /// \brief A helper used to populate the work list with the given set of
+  /// regions.
+  void populateWorkList(invalidateRegionsWorker &W,
+                        ArrayRef<SVal> Values,
+                        bool IsArrayOfConstRegions,
+                        InvalidatedRegions *TopLevelRegions);
+
 public:
   RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f)
     : StoreManager(mgr), Features(f),
@@ -365,14 +373,17 @@ public:
                                            RegionBindingsRef B,
                                            InvalidatedRegions *Invalidated);
 
-  StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions,
+  StoreRef invalidateRegions(Store store,
+                             ArrayRef<SVal> Values,
+                             ArrayRef<SVal> ConstValues,
                              const Expr *E, unsigned Count,
                              const LocationContext *LCtx,
-                             InvalidatedSymbols &IS,
                              const CallEvent *Call,
-                             ArrayRef<const MemRegion *> ConstRegions,
+                             InvalidatedSymbols &IS,
                              InvalidatedSymbols &ConstIS,
-                             InvalidatedRegions *Invalidated);
+                             InvalidatedRegions *Invalidated,
+                             InvalidatedRegions *InvalidatedTopLevel,
+                             InvalidatedRegions *InvalidatedTopLevelConst);
 
   bool scanReachableSymbols(Store S, const MemRegion *R,
                             ScanReachableSymbols &Callbacks);
@@ -1062,15 +1073,48 @@ RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K,
   return B;
 }
 
+void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W,
+                                          ArrayRef<SVal> Values,
+                                          bool IsArrayOfConstRegions,
+                                          InvalidatedRegions *TopLevelRegions) {
+  for (ArrayRef<SVal>::iterator I = Values.begin(),
+                                E = Values.end(); I != E; ++I) {
+    SVal V = *I;
+    if (Optional<nonloc::LazyCompoundVal> LCS =
+        V.getAs<nonloc::LazyCompoundVal>()) {
+
+      const SValListTy &Vals = getInterestingValues(*LCS);
+
+      for (SValListTy::const_iterator I = Vals.begin(),
+                                      E = Vals.end(); I != E; ++I) {
+        // Note: the last argumet is false here because these are
+        // non-top-level regions.
+        if (const MemRegion *R = (*I).getAsRegion())
+          W.AddToWorkList(R, /*IsConst=*/ false);
+      }
+      continue;
+    }
+
+    if (const MemRegion *R = V.getAsRegion()) {
+      if (TopLevelRegions)
+        TopLevelRegions->push_back(R);
+      W.AddToWorkList(R, /*IsConst=*/ IsArrayOfConstRegions);
+      continue;
+    }
+  }
+}
+
 StoreRef
 RegionStoreManager::invalidateRegions(Store store,
-                                      ArrayRef<const MemRegion *> Regions,
+                                      ArrayRef<SVal> Values,
+                                      ArrayRef<SVal> ConstValues,
                                       const Expr *Ex, unsigned Count,
                                       const LocationContext *LCtx,
-                                      InvalidatedSymbols &IS,
                                       const CallEvent *Call,
-                                      ArrayRef<const MemRegion *> ConstRegions,
+                                      InvalidatedSymbols &IS,
                                       InvalidatedSymbols &ConstIS,
+                                      InvalidatedRegions *TopLevelRegions,
+                                      InvalidatedRegions *TopLevelConstRegions,
                                       InvalidatedRegions *Invalidated) {
   RegionBindingsRef B = RegionStoreManager::getRegionBindings(store);
   invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS,
@@ -1080,15 +1124,10 @@ RegionStoreManager::invalidateRegions(Store store,
   W.GenerateClusters();
 
   // Add the regions to the worklist.
-  for (ArrayRef<const MemRegion *>::iterator
-       I = Regions.begin(), E = Regions.end(); I != E; ++I)
-    W.AddToWorkList(*I, /*IsConst=*/false);
-
-  for (ArrayRef<const MemRegion *>::iterator I = ConstRegions.begin(),
-                                             E = ConstRegions.end();
-       I != E; ++I) {
-    W.AddToWorkList(*I, /*IsConst=*/true);
-  }
+  populateWorkList(W, Values, /*IsArrayOfConstRegions*/ false,
+                   TopLevelRegions);
+  populateWorkList(W, ConstValues, /*IsArrayOfConstRegions*/ true,
+                   TopLevelConstRegions);
 
   W.RunWorkList();