[analyzer] Make directly bounded LazyCompoundVal as lazily copied

[steakhal]

Summary

Previously, LazyCompoundVal bindings to subregions referred by
LazyCopoundVals, were not marked as lazily copied.

This change returns LazyCompoundVals from getInterestingValues(),
so their regions can be marked as lazily copied in RemoveDeadBindingsWorker::VisitBinding().

Depends on D134947

Authored by: Tomasz Kamiński <tomasz.kamiń[e-mail]>

[steakhal]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2290

Here is the continue which previously prevented getInterestingValues() returning a list containing LazyCompoundVals. Now, we actually want them to be able to mark them as lazily copied as described in the summary.
I'm just highlighting this, as when I reviewed this change it did not immediately stand out.

[steakhal]

rebased

[steakhal]

Ping.

[martong]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2290

Yes, I was looking for the change too :D

2843

Why can we remove this line?
If LCS->getRegion() returns a non-null unconditionally then please add an assert.

clang/test/Analysis/trivial-copy-struct.cpp

95–97

Good!

[tomasz-kaminski-sonarsource]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2843

The interface of the LazyCompoundVal is already marked as returning non-null, and this is why we removed the if condition:

LLVM_ATTRIBUTE_RETURNS_NONNULL
const TypedValueRegion *getRegion() const;

[martong]

LGTM

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2843

Ok.

[steakhal]

Thanks for the review @martong!
I'll land this tomorrow.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

findLazyBinding(RegionBindingsConstRef B, const SubRegion *R,
                   const SubRegion *originalRegion);
 
   /// Returns the cached set of interesting SVals contained within a lazy
   /// binding.
   ///
   /// The precise value of "interesting" is determined for the purposes of
   /// RegionStore's internal analysis. It must always contain all regions and
   /// symbols, but may omit constants and other kinds of SVal.
+  ///
+  /// In contrast to compound values, LazyCompoundVals are also added
+  /// to the 'interesting values' list in addition to the child interesting
+  /// values.
   const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);
 
   //===------------------------------------------------------------------===//
   // State pruning.
   //===------------------------------------------------------------------===//
 
   /// removeDeadBindings - Scans the RegionStore of 'state' for dead values.
   ///  It returns a new Store with these values removed.
if (const MemRegion *R = V.getAsRegion()) {
     AddToWorkList(R);
     return;
   }
 
   // Is it a LazyCompoundVal?  All references get invalidated as well.
   if (Optional<nonloc::LazyCompoundVal> LCS =
           V.getAs<nonloc::LazyCompoundVal>()) {
 
-    const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
-
-    for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
-                                                        E = Vals.end();
-         I != E; ++I)
-      VisitBinding(*I);
+    // `getInterestingValues()` returns SVals contained within LazyCompoundVals,
+    // so there is no need to visit them.
+    for (SVal V : RM.getInterestingValues(*LCS))
+      if (!isa<nonloc::LazyCompoundVal>(V))
+        VisitBinding(V);
 
     return;
   }
 }
 
 void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
                                            const ClusterBindings *C) {
 
void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
                                           ArrayRef<SVal> Values,
                                           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 argument is false here because these are
-        // non-top-level regions.
-        if (const MemRegion *R = (*I).getAsRegion())
+      for (SVal S : getInterestingValues(*LCS))
+        if (const MemRegion *R = S.getAsRegion())
           W.AddToWorkList(R);
-      }
+
       continue;
     }
 
     if (const MemRegion *R = V.getAsRegion()) {
       if (TopLevelRegions)
         TopLevelRegions->push_back(R);
       W.AddToWorkList(R);
       continue;
collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR,
                            /*IncludeAllDefaultBindings=*/true);
   for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(),
                                                     E = Bindings.end();
        I != E; ++I) {
     SVal V = I->second;
     if (V.isUnknownOrUndef() || V.isConstant())
       continue;
 
-    if (Optional<nonloc::LazyCompoundVal> InnerLCV =
-            V.getAs<nonloc::LazyCompoundVal>()) {
+    if (auto InnerLCV = V.getAs<nonloc::LazyCompoundVal>()) {
       const SValListTy &InnerList = getInterestingValues(*InnerLCV);
       List.insert(List.end(), InnerList.begin(), InnerList.end());
-      continue;
     }
 
     List.push_back(V);
   }
 
   return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
 }
 
for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
     // Element index of a binding key is live.
     SymReaper.markElementIndicesLive(I.getKey().getRegion());
 
     VisitBinding(I.getData());
   }
 }
 
 void RemoveDeadBindingsWorker::VisitBinding(SVal V) {
-  // Is it a LazyCompoundVal?  All referenced regions are live as well.
-  if (Optional<nonloc::LazyCompoundVal> LCS =
-          V.getAs<nonloc::LazyCompoundVal>()) {
-    // TODO: Make regions referred to by `lazyCompoundVals` that are bound to
-    // subregions of the `LCS.getRegion()` also lazily copied.
-    if (const MemRegion *R = LCS->getRegion())
-      SymReaper.markLazilyCopied(R);
-
-    const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
-
-    for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
-                                                        E = Vals.end();
-         I != E; ++I)
-      VisitBinding(*I);
+  // Is it a LazyCompoundVal? All referenced regions are live as well.
+  // The LazyCompoundVal itself is not live but should be readable.
+  if (auto LCS = V.getAs<nonloc::LazyCompoundVal>()) {
+    SymReaper.markLazilyCopied(LCS->getRegion());
+
+    for (SVal V : RM.getInterestingValues(*LCS)) {
+      if (auto DepLCS = V.getAs<nonloc::LazyCompoundVal>())
+        SymReaper.markLazilyCopied(DepLCS->getRegion());
+      else
+        VisitBinding(V);
+    }
 
     return;
   }
 
   // If V is a region, then add it to the worklist.
   if (const MemRegion *R = V.getAsRegion()) {
     AddToWorkList(R);
     SymReaper.markLive(R);

clang/test/Analysis/trivial-copy-struct.cpp

void nestedLazyCompoundVal(List* n) {
   Wrapper* w = 0;
   {
      Wrapper lw;
      lw.head = *n;
      w = new Wrapper(lw);
   }
   if (!n->next) {
     if (w->head.next) {
-      // FIXME: Unreachable, w->head is a copy of *n, therefore
+      // Unreachable, w->head is a copy of *n, therefore
       // w->head.next and n->next are equal
-      clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+      clang_analyzer_warnIfReached(); // no-warning: unreachable
     }
   }
   delete w;
 }