This is a fairly large patch, which resulted from a cascade of changes

made to RegionStore (and related classes) in order to handle some
analyzer failures involving casts and manipulation of symbolic memory.

The root of the change is in StoreManager::CastRegion().  Instead of
using ad hoc heuristics to decide when to layer an ElementRegion on a
casted MemRegion, we now always layer an ElementRegion when the cast
type is different than the original type of the region.  This carries
the current cast information associated with a region around without
resorting to the error prone recording of "casted types" in GRState.

Along with this new policy of layering ElementRegions, I added a new
algorithm to strip away existing ElementRegions when they simply
represented casts of a base memory object.  This algorithm computes
the raw "byte offset" that an ElementRegion represents from the base
region, and allows the new ElementRegion to be based off that offset.
The added benefit is that this naturally handles a series of casts of
a MemRegion without building up a set of redundant ElementRegions
(thus canonicalizing the region view).

Other related changes that cascaded from this one (as tests were
failing in RegionStore):

- Revamped RegionStoreManager::InvalidateRegion() to completely remove
  all bindings and default values from a region and all subregions.
  Now invalidated fields are not bound directly to new symbolic
  values; instead the base region has a "default" symbol value from
  which "derived symbols" can be created.  The main advantage of this
  approach is that it allows us to invalidate a region hierarchy and
  then lazily instantiate new values no matter how deep the hierarchy
  went (i.e., regardless of the number of field accesses,
  e.g. x->f->y->z->...).  The previous approach did not do this.

- Slightly reworked RegionStoreManager::RemoveDeadBindings() to also
  incorporate live symbols and live regions that do not have direct
  bindings but also have "default values" used for lazy instantiation.
  The changes to 'InvalidateRegion' revealed that these were necessary
  in order to achieve lazy instantiation of values in the region store
  with those bindings being removed too early.

- The changes to InvalidateRegion() and RemoveDeadBindings() revealed
  a serious bug in 'getSubRegionMap()' where not all region -> subregion
  relationships involved in actually bindings (explicit and implicit)
  were being recorded.  This has been fixed by using a worklist algorithm
  to iteratively fill in the region map.

- Added special support to RegionStoreManager::Bind()/Retrieve() to handle
  OSAtomicCompareAndSwap in light of the new 'CastRegion' changes and the
  layering of ElementRegions.

- Fixed a bug in SymbolReaper::isLive() where derived symbols were not
  being marked live if the symbol they were derived from was also live.
  This fix was critical for getting lazy instantiation in RegionStore
  to work.

- Tidied up the implementation of ValueManager::getXXXSymbolVal() methods
  to use SymbolManager::canSymbolicate() to decide whether or not a
  symbol should be symbolicated.

- 'test/Analysis/misc-ps-xfail.m' now passes; that test case has been
  moved to 'test/Analysis/misc-ps.m'.

- Tweaked some pretty-printing of MemRegions, and implemented
  'ElementRegion::getRawOffset()' for use with the CastRegion changes.



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

1 files changed, 96 insertions, 47 deletions

diff --git a/lib/Analysis/Store.cpp b/lib/Analysis/Store.cpp
index 68bb49cbe3..bfcb0f41ca 100644
--- a/lib/Analysis/Store.cpp
+++ b/lib/Analysis/Store.cpp
@@ -22,17 +22,15 @@ StoreManager::StoreManager(GRStateManager &stateMgr)
 
 StoreManager::CastResult
 StoreManager::MakeElementRegion(const GRState *state, const MemRegion *region,
-                                QualType pointeeTy, QualType castToTy) {
-  
-  // Record the cast type of the region.
-  state = setCastType(state, region, castToTy);
-  
-  // Create a new ElementRegion at offset 0.
-  SVal idx = ValMgr.makeZeroArrayIndex();
+                                QualType pointeeTy, QualType castToTy,
+                                uint64_t index) {
+  // Create a new ElementRegion.
+  SVal idx = ValMgr.makeArrayIndex(index);
   return CastResult(state, MRMgr.getElementRegion(pointeeTy, idx, region,
                                                   ValMgr.getContext()));  
 }
 
+// FIXME: Merge with the implementation of the same method in MemRegion.cpp
 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
   if (const RecordType *RT = Ty->getAs<RecordType>()) {
     const RecordDecl *D = RT->getDecl();
@@ -49,15 +47,10 @@ StoreManager::CastRegion(const GRState *state, const MemRegion* R,
   
   ASTContext& Ctx = StateMgr.getContext();
   
-  // We need to know the real type of CastToTy.
-  QualType ToTy = Ctx.getCanonicalType(CastToTy);
-
   // Handle casts to Objective-C objects.
-  if (CastToTy->isObjCObjectPointerType()) {
-    state = setCastType(state, R, CastToTy);
-    return CastResult(state, R);
-  }
-  
+  if (CastToTy->isObjCObjectPointerType())
+    return CastResult(state, R->getBaseRegion());
+
   if (CastToTy->isBlockPointerType()) {
     if (isa<CodeTextRegion>(R))
       return CastResult(state, R);
@@ -79,6 +72,15 @@ StoreManager::CastRegion(const GRState *state, const MemRegion* R,
   // already be handled.
   QualType PointeeTy = CastToTy->getAs<PointerType>()->getPointeeType();
   
+  // Handle casts from compatible types or to void*.
+  if (R->isBoundable())
+    if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
+      QualType ObjTy = Ctx.getCanonicalType(TR->getValueType(Ctx));
+      QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
+      if (CanonPointeeTy == ObjTy || CanonPointeeTy == Ctx.VoidTy)
+        return CastResult(state, R);
+    }
+
   // Process region cast according to the kind of the region being cast.
   switch (R->getKind()) {
     case MemRegion::BEG_TYPED_REGIONS:
@@ -88,8 +90,7 @@ StoreManager::CastRegion(const GRState *state, const MemRegion* R,
     case MemRegion::END_TYPED_REGIONS: {
       assert(0 && "Invalid region cast");
       break;
-    }
-      
+    }      
     case MemRegion::CodeTextRegionKind: {
       // CodeTextRegion should be cast to only a function or block pointer type,
       // although they can in practice be casted to anything, e.g, void*,
@@ -99,46 +100,94 @@ StoreManager::CastRegion(const GRState *state, const MemRegion* R,
     }
       
     case MemRegion::StringRegionKind:
-      // Handle casts of string literals.
-      return MakeElementRegion(state, R, PointeeTy, CastToTy);
-
     case MemRegion::ObjCObjectRegionKind:
-    case MemRegion::SymbolicRegionKind:
       // FIXME: Need to handle arbitrary downcasts.
-    case MemRegion::AllocaRegionKind: {  
-      state = setCastType(state, R, CastToTy);
-      break;
-    }
-
+    case MemRegion::SymbolicRegionKind:
+    case MemRegion::AllocaRegionKind:
     case MemRegion::CompoundLiteralRegionKind:
-    case MemRegion::ElementRegionKind:
     case MemRegion::FieldRegionKind:
     case MemRegion::ObjCIvarRegionKind:
-    case MemRegion::VarRegionKind: {
-      // VarRegion, ElementRegion, and FieldRegion has an inherent type.
-      // Normally they should not be cast. We only layer an ElementRegion when
-      // the cast-to pointee type is of smaller size. In other cases, we return
-      // the original VarRegion.
+    case MemRegion::VarRegionKind:   
+      return MakeElementRegion(state, R, PointeeTy, CastToTy);
+      
+    case MemRegion::ElementRegionKind: {
+      // If we are casting from an ElementRegion to another type, the
+      // algorithm is as follows:
+      //
+      // (1) Compute the "raw offset" of the ElementRegion from the
+      //     base region.  This is done by calling 'getAsRawOffset()'.
+      //
+      // (2a) If we get a 'RegionRawOffset' after calling 
+      //      'getAsRawOffset()', determine if the absolute offset
+      //      can be exactly divided into chunks of the size of the 
+      //      casted-pointee type.  If so, create a new ElementRegion with 
+      //      the pointee-cast type as the new ElementType and the index
+      //      being the offset divded by the chunk size.  If not, create
+      //      a new ElementRegion at offset 0 off the raw offset region.
+      //
+      // (2b) If we don't a get a 'RegionRawOffset' after calling
+      //      'getAsRawOffset()', it means that we are at offset 0.
+      //      
+      // FIXME: Handle symbolic raw offsets.
       
-      // If the pointee or object type is incomplete, do not compute their
-      // sizes, and return the original region.
-      QualType ObjTy = cast<TypedRegion>(R)->getValueType(Ctx);
+      const ElementRegion *elementR = cast<ElementRegion>(R);
+      const RegionRawOffset &rawOff = elementR->getAsRawOffset();
+      const MemRegion *baseR = rawOff.getRegion();
       
-      if (!IsCompleteType(Ctx, PointeeTy) || !IsCompleteType(Ctx, ObjTy)) {
-        state = setCastType(state, R, ToTy);
-        break;
+      // If we cannot compute a raw offset, throw up our hands and return
+      // a NULL MemRegion*.
+      if (!baseR)
+        return CastResult(state, NULL);
+      
+      int64_t off = rawOff.getByteOffset();
+      
+      if (off == 0) {
+        // Edge case: we are at 0 bytes off the beginning of baseR.  We
+        // check to see if type we are casting to is the same as the base
+        // region.  If so, just return the base region.        
+        if (const TypedRegion *TR = dyn_cast<TypedRegion>(baseR)) {
+          QualType ObjTy = Ctx.getCanonicalType(TR->getValueType(Ctx));
+          QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
+          if (CanonPointeeTy == ObjTy)
+            return CastResult(state, baseR);
+        }
+        
+        // Otherwise, create a new ElementRegion at offset 0.
+        return MakeElementRegion(state, baseR, PointeeTy, CastToTy, 0);
       }
+      
+      // We have a non-zero offset from the base region.  We want to determine
+      // if the offset can be evenly divided by sizeof(PointeeTy).  If so,
+      // we create an ElementRegion whose index is that value.  Otherwise, we
+      // create two ElementRegions, one that reflects a raw offset and the other
+      // that reflects the cast.
+      
+      // Compute the index for the new ElementRegion.
+      int64_t newIndex = 0;
+      const MemRegion *newSuperR = 0;
 
-      uint64_t PointeeTySize = Ctx.getTypeSize(PointeeTy);
-      uint64_t ObjTySize = Ctx.getTypeSize(ObjTy);
+      // We can only compute sizeof(PointeeTy) if it is a complete type.
+      if (IsCompleteType(Ctx, PointeeTy)) {
+        // Compute the size in **bytes**.
+        int64_t pointeeTySize = (int64_t) (Ctx.getTypeSize(PointeeTy) / 8);
+
+        // Is the offset a multiple of the size?  If so, we can layer the
+        // ElementRegion (with elementType == PointeeTy) directly on top of
+        // the base region.
+        if (off % pointeeTySize == 0) {
+          newIndex = off / pointeeTySize;
+          newSuperR = baseR;
+        }
+      }
       
-      if ((PointeeTySize > 0 && PointeeTySize < ObjTySize) ||
-          (ObjTy->isAggregateType() && PointeeTy->isScalarType()) ||
-          ObjTySize == 0 /* R has 'void*' type. */)
-        return MakeElementRegion(state, R, PointeeTy, ToTy);
-        
-      state = setCastType(state, R, ToTy);
-      break;
+      if (!newSuperR) {
+        // Create an intermediate ElementRegion to represent the raw byte.
+        // This will be the super region of the final ElementRegion.
+        SVal idx = ValMgr.makeArrayIndex(off);
+        newSuperR = MRMgr.getElementRegion(Ctx.CharTy, idx, baseR, Ctx);
+      }
+            
+      return MakeElementRegion(state, newSuperR, PointeeTy, CastToTy, newIndex);
     }
   }