commit 0a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28c
author Jordan Rose <jordan_rose@apple.com> Fri Feb 15 00:32:06 2013 +0000
committer Jordan Rose <jordan_rose@apple.com> Fri Feb 15 00:32:06 2013 +0000
tree 5f65a23f83cd21376e82dcbbdac95fd839325d86
parent 9d688e219caa37e60975ec8d5bebe74a176c9c2b

[analyzer] Use collectSubRegionKeys to make removeDeadBindings faster.

Previously, whenever we had a LazyCompoundVal, we crawled through the
entire store snapshot looking for bindings within the LCV's region. Now, we
just ask for the subregion bindings of the lazy region and only visit those.

This is an optimization (so no test case), but it may allow us to clean up
more dead bindings than we were previously.

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

lib/StaticAnalyzer/Core/RegionStore.cpp

diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 7b1d72b..76abf23 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -713,10 +713,16 @@
                       Fields.begin() - Delta);
 }
 
+/// Collects all keys in \p Cluster that may refer to bindings within \p Top.
+///
+/// The \p IncludeAllDefaultBindings parameter specifies whether to include
+/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is
+/// an aggregate within a larger aggregate with a default binding.
 static void collectSubRegionKeys(SmallVectorImpl<BindingKey> &Keys,
                                  SValBuilder &SVB,
                                  const ClusterBindings &Cluster,
-                                 const SubRegion *Top, BindingKey TopKey) {
+                                 const SubRegion *Top, BindingKey TopKey,
+                                 bool IncludeAllDefaultBindings) {
   FieldVector FieldsInSymbolicSubregions;
   if (TopKey.hasSymbolicOffset()) {
     getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions);
@@ -758,7 +764,7 @@
         // we're invalidating.
         // FIXME: This is probably incorrect; consider invalidating an outer
         // struct whose first field is bound to a LazyCompoundVal.
-        if (NextKey.isDirect())
+        if (IncludeAllDefaultBindings || NextKey.isDirect())
           Keys.push_back(NextKey);
       }
 
@@ -768,7 +774,7 @@
         // Case 3: The next key is symbolic and we just changed something within
         // its concrete region. We don't know if the binding is still valid, so
         // we'll be conservative and remove it.
-        if (NextKey.isDirect())
+        if (IncludeAllDefaultBindings || NextKey.isDirect())
           if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
             Keys.push_back(NextKey);
       } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) {
@@ -782,6 +788,16 @@
   }
 }
 
+static void collectSubRegionKeys(SmallVectorImpl<BindingKey> &Keys,
+                                 SValBuilder &SVB,
+                                 const ClusterBindings &Cluster,
+                                 const SubRegion *Top,
+                                 bool IncludeAllDefaultBindings) {
+  collectSubRegionKeys(Keys, SVB, Cluster, Top,
+                       BindingKey::Make(Top, BindingKey::Default),
+                       IncludeAllDefaultBindings);
+}
+
 RegionBindingsRef
 RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B,
                                             const SubRegion *Top) {
@@ -797,7 +813,8 @@
     return B;
 
   SmallVector<BindingKey, 32> Keys;
-  collectSubRegionKeys(Keys, svalBuilder, *Cluster, Top, TopKey);
+  collectSubRegionKeys(Keys, svalBuilder, *Cluster, Top, TopKey,
+                       /*IncludeAllDefaultBindings=*/false);
 
   ClusterBindingsRef Result(*Cluster, CBFactory);
   for (SmallVectorImpl<BindingKey>::const_iterator I = Keys.begin(),
@@ -1974,23 +1991,20 @@
   if (const nonloc::LazyCompoundVal *LCS =
         dyn_cast<nonloc::LazyCompoundVal>(&V)) {
 
-    const MemRegion *LazyR = LCS->getRegion();
+    const SubRegion *LazyR = LCS->getRegion();
     RegionBindingsRef B = RM.getRegionBindings(LCS->getStore());
 
-    // FIXME: This should not have to walk all bindings in the old store.
-    for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();
-         RI != RE; ++RI){
-      const ClusterBindings &Cluster = RI.getData();
-      for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
-           CI != CE; ++CI) {
-        BindingKey K = CI.getKey();
-        if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) {
-          if (BaseR == LazyR)
-            VisitBinding(CI.getData());
-          else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR))
-            VisitBinding(CI.getData());
-        }
-      }
+    const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion());
+    if (!Cluster)
+      return;
+
+    SmallVector<BindingKey, 32> Keys;
+    collectSubRegionKeys(Keys, svalBuilder, *Cluster, LazyR,
+                         /*IncludeAllDefaultBindings=*/true);
+    for (SmallVectorImpl<BindingKey>::const_iterator I = Keys.begin(),
+                                                     E = Keys.end();
+         I != E; ++I) {
+      VisitBinding(*Cluster->lookup(*I));
     }
 
     return;