[analyzer] Add TK_EntireMemSpace invalidation trait.

[dcoughlin]

Summary

This is a patch to support Sean Eveson's work on loop widening. It adds a new
TK_EntireMemSpace invalidation trait that, when applied to a MemSpaceRegion, indicates
that the entire memory space should be invalidated.

Clients would add this trait before invalidating. For example:

RegionAndSymbolInvalidationTraits ITraits;
ITraits.setTrait(MRMgr.getStackLocalsRegion(STC),
                 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);

This patch updates the existing logic invalidating global memspace regions for calls to
additionally handle arbitrary memspaces. When generating initial clusters during
cluster analysis we will now add a cluster to the worklist if the memspace for its
base is marked with TK_EntireMemSpace.

The patch also moves the logic for invalidating globals from ClusterAnalysis to
invalidateRegionsWorker so that it is not shared with removeDeadBindingsWorker.

There are no explicit tests with this patch -- but when applied to Sean's patch in
http://reviews.llvm.org/D12358 and after updating his code to set the trait,
the failing tests in that patch now pass.

[seaneveson]

Thank you for working on this! I have updated my patch (http://reviews.llvm.org/D12358) to depend on this one.

[seaneveson]

Could you update this patch to the latest trunk please? There's a conflict with http://reviews.llvm.org/rL248516.

Thanks.

[dcoughlin]

Sean, I've committed this patch. You can update to trunk to get it.

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

 public:
   /// \brief Describes different invalidation traits.
   enum InvalidationKinds {
     /// Tells that a region's contents is not changed.
     TK_PreserveContents = 0x1,
     /// Suppress pointer-escaping of a region.
     TK_SuppressEscape = 0x2,
     // Do not invalidate super region.
-    TK_DoNotInvalidateSuperRegion = 0x4
+    TK_DoNotInvalidateSuperRegion = 0x4,
+    /// When applied to a MemSpaceRegion, indicates the entire memory space
+    /// should be invalidated.
+    TK_EntireMemSpace = 0x8
 
     // Do not forget to extend StorageTypeForKinds if number of traits exceed 
     // the number of bits StorageTypeForKinds can store.
   };
 
   void setTrait(SymbolRef Sym, InvalidationKinds IK);
   void setTrait(const MemRegion *MR, InvalidationKinds IK);
   bool hasTrait(SymbolRef Sym, InvalidationKinds IK);

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

protected:
   WorkList WL;
 
   RegionStoreManager &RM;
   ASTContext &Ctx;
   SValBuilder &svalBuilder;
 
   RegionBindingsRef B;
 
-private:
-  GlobalsFilterKind GlobalsFilter;
 
 protected:
   const ClusterBindings *getCluster(const MemRegion *R) {
     return B.lookup(R);
   }
 
-  /// Returns true if the memory space of the given region is one of the global
-  /// regions specially included at the start of analysis.
-  bool isInitiallyIncludedGlobalRegion(const MemRegion *R) {
-    switch (GlobalsFilter) {
-    case GFK_None:
-      return false;
-    case GFK_SystemOnly:
-      return isa<GlobalSystemSpaceRegion>(R->getMemorySpace());
-    case GFK_All:
-      return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace());
-    }
-
-    llvm_unreachable("unknown globals filter");
+  /// Returns true if all clusters in the given memspace should be initially
+  /// included in the cluster analysis. Subclasses may provide their
+  /// own implementation.
+  bool includeEntireMemorySpace(const MemRegion *Base) {
   }
 
 public:
   ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
-                  RegionBindingsRef b, GlobalsFilterKind GFK)
+                  RegionBindingsRef b )
     : RM(rm), Ctx(StateMgr.getContext()),
       svalBuilder(StateMgr.getSValBuilder()),
-      B(b), GlobalsFilter(GFK) {}
+      B(b) {}
 
   RegionBindingsRef getRegionBindings() const { return B; }
 
   bool isVisited(const MemRegion *R) {
     return Visited.count(getCluster(R));
   }
 
   void GenerateClusters() {
     // Scan the entire set of bindings and record the region clusters.
     for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();
          RI != RE; ++RI){
       const MemRegion *Base = RI.getKey();
 
       const ClusterBindings &Cluster = RI.getData();
       assert(!Cluster.isEmpty() && "Empty clusters should be removed");
       static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);
 
-      // If this is an interesting global region, add it the work list up front.
-      if (isInitiallyIncludedGlobalRegion(Base))
+      // If the base's memspace should be entirely invalidated, add the cluster
+      // to the workspace up front.
+      if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base))
         AddToWorkList(WorkListElement(Base), &Cluster);
     }
   }
 
   bool AddToWorkList(WorkListElement E, const ClusterBindings *C) {
     if (C && !Visited.insert(C).second)
       return false;
     WL.push_back(E);

 class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker>
 {
   const Expr *Ex;
   unsigned Count;
   const LocationContext *LCtx;
   InvalidatedSymbols &IS;
   RegionAndSymbolInvalidationTraits &ITraits;
   StoreManager::InvalidatedRegions *Regions;
+  GlobalsFilterKind GlobalsFilter;
 public:
   invalidateRegionsWorker(RegionStoreManager &rm,
                           ProgramStateManager &stateMgr,
                           RegionBindingsRef b,
                           const Expr *ex, unsigned count,
                           const LocationContext *lctx,
                           InvalidatedSymbols &is,
                           RegionAndSymbolInvalidationTraits &ITraitsIn,
                           StoreManager::InvalidatedRegions *r,
                           GlobalsFilterKind GFK)
-    : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, GFK),
-      Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r){}
+     : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b),
+       Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),
+       GlobalsFilter(GFK) {}
 
   void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);
   void VisitBinding(SVal V);
 
   using ClusterAnalysis::AddToWorkList;
 
   bool AddToWorkList(const MemRegion *R);
+
+  /// Returns true if all clusters in the memory space for \p Base should be
+  /// be invalidated.
+  bool includeEntireMemorySpace(const MemRegion *Base);
+
+  /// Returns true if the memory space of the given region is one of the global
+  /// regions specially included at the start of invalidation.
+  bool isInitiallyIncludedGlobalRegion(const MemRegion *R);
 };
 }
 
 bool invalidateRegionsWorker::AddToWorkList(const MemRegion *R) {
   bool doNotInvalidateSuperRegion = ITraits.hasTrait(
       R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
   const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();
   return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
   }
 
   DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
                                                         T,Count);
   assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
   B = B.addBinding(baseR, BindingKey::Direct, V);
 }
 
+bool invalidateRegionsWorker::isInitiallyIncludedGlobalRegion(
+    const MemRegion *R) {
+  switch (GlobalsFilter) {
+  case GFK_None:
+    return false;
+  case GFK_SystemOnly:
+    return isa<GlobalSystemSpaceRegion>(R->getMemorySpace());
+  case GFK_All:
+    return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace());
+  }
+
+  llvm_unreachable("unknown globals filter");
+}
+
+bool invalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) {
+  if (isInitiallyIncludedGlobalRegion(Base))
+    return true;
+
+  const MemSpaceRegion *MemSpace = Base->getMemorySpace();
+  return ITraits.hasTrait(MemSpace,
+                          RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
+}
+
 RegionBindingsRef
 RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K,
                                            const Expr *Ex,
                                            unsigned Count,
                                            const LocationContext *LCtx,
                                            RegionBindingsRef B,
                                            InvalidatedRegions *Invalidated) {
   // Bind the globals memory space to a new symbol that we will use to derive
class removeDeadBindingsWorker :
   SymbolReaper &SymReaper;
   const StackFrameContext *CurrentLCtx;
 
 public:
   removeDeadBindingsWorker(RegionStoreManager &rm,
                            ProgramStateManager &stateMgr,
                            RegionBindingsRef b, SymbolReaper &symReaper,
                            const StackFrameContext *LCtx)
-    : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, GFK_None),
+    : 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;