Vendor import of clang tags/RELEASE_33/final r183502 (effectively, 3.3

release):
http://llvm.org/svn/llvm-project/cfe/tags/RELEASE_33/final@183502

1 files changed, 178 insertions, 98 deletions

diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 0f4a682..88c4eee 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -19,10 +19,12 @@
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Basic/TargetInfo.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
 #include "llvm/ADT/ImmutableList.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/ADT/Optional.h"
@@ -323,6 +325,7 @@ class invalidateRegionsWorker;
 class RegionStoreManager : public StoreManager {
 public:
   const RegionStoreFeatures Features;
+
   RegionBindings::Factory RBFactory;
   mutable ClusterBindings::Factory CBFactory;
 
@@ -332,6 +335,16 @@ private:
                          SValListTy> LazyBindingsMapTy;
   LazyBindingsMapTy LazyBindingsMap;
 
+  /// The largest number of fields a struct can have and still be
+  /// considered "small".
+  ///
+  /// This is currently used to decide whether or not it is worth "forcing" a
+  /// LazyCompoundVal on bind.
+  ///
+  /// This is controlled by 'region-store-small-struct-limit' option.
+  /// To disable all small-struct-dependent behavior, set the option to "0".
+  unsigned SmallStructLimit;
+
   /// \brief A helper used to populate the work list with the given set of
   /// regions.
   void populateWorkList(invalidateRegionsWorker &W,
@@ -342,7 +355,14 @@ private:
 public:
   RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f)
     : StoreManager(mgr), Features(f),
-      RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()) {}
+      RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()),
+      SmallStructLimit(0) {
+    if (SubEngine *Eng = StateMgr.getOwningEngine()) {
+      AnalyzerOptions &Options = Eng->getAnalysisManager().options;
+      SmallStructLimit =
+        Options.getOptionAsInteger("region-store-small-struct-limit", 2);
+    }
+  }
 
 
   /// setImplicitDefaultValue - Set the default binding for the provided
@@ -409,19 +429,20 @@ public: // Part of public interface to class.
                      .getRootWithoutRetain(), *this);
   }
 
-  /// \brief Create a new store that binds a value to a compound literal.
+  /// Attempt to extract the fields of \p LCV and bind them to the struct region
+  /// \p R.
   ///
-  /// \param ST The original store whose bindings are the basis for the new
-  ///        store.
+  /// This path is used when it seems advantageous to "force" loading the values
+  /// within a LazyCompoundVal to bind memberwise to the struct region, rather
+  /// than using a Default binding at the base of the entire region. This is a
+  /// heuristic attempting to avoid building long chains of LazyCompoundVals.
   ///
-  /// \param CL The compound literal to bind (the binding key).
-  ///
-  /// \param LC The LocationContext for the binding.
-  ///
-  /// \param V The value to bind to the compound literal.
-  StoreRef bindCompoundLiteral(Store ST,
-                               const CompoundLiteralExpr *CL,
-                               const LocationContext *LC, SVal V);
+  /// \returns The updated store bindings, or \c None if binding non-lazily
+  ///          would be too expensive.
+  Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B,
+                                                 const TypedValueRegion *R,
+                                                 const RecordDecl *RD,
+                                                 nonloc::LazyCompoundVal LCV);
 
   /// BindStruct - Bind a compound value to a structure.
   RegionBindingsRef bindStruct(RegionBindingsConstRef B,
@@ -490,8 +511,7 @@ public: // Part of public interface to class.
 
   SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
                                          const TypedValueRegion *R,
-                                         QualType Ty,
-                                         const MemRegion *superR);
+                                         QualType Ty);
   
   SVal getLazyBinding(const SubRegion *LazyBindingRegion,
                       RegionBindingsRef LazyBinding);
@@ -604,6 +624,17 @@ ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) {
 //===----------------------------------------------------------------------===//
 
 namespace {
+/// Used to determine which global regions are automatically included in the
+/// initial worklist of a ClusterAnalysis.
+enum GlobalsFilterKind {
+  /// Don't include any global regions.
+  GFK_None,
+  /// Only include system globals.
+  GFK_SystemOnly,
+  /// Include all global regions.
+  GFK_All
+};
+
 template <typename DERIVED>
 class ClusterAnalysis  {
 protected:
@@ -620,19 +651,36 @@ protected:
   SValBuilder &svalBuilder;
 
   RegionBindingsRef B;
-  
-  const bool includeGlobals;
 
+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");
+  }
+
 public:
   ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
-                  RegionBindingsRef b, const bool includeGlobals)
+                  RegionBindingsRef b, GlobalsFilterKind GFK)
     : RM(rm), Ctx(StateMgr.getContext()),
       svalBuilder(StateMgr.getSValBuilder()),
-      B(b), includeGlobals(includeGlobals) {}
+      B(b), GlobalsFilter(GFK) {}
 
   RegionBindingsRef getRegionBindings() const { return B; }
 
@@ -650,9 +698,9 @@ public:
       assert(!Cluster.isEmpty() && "Empty clusters should be removed");
       static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);
 
-      if (includeGlobals)
-        if (isa<NonStaticGlobalSpaceRegion>(Base->getMemorySpace()))
-          AddToWorkList(Base, &Cluster);
+      // If this is an interesting global region, add it the work list up front.
+      if (isInitiallyIncludedGlobalRegion(Base))
+        AddToWorkList(WorkListElement(Base), &Cluster);
     }
   }
 
@@ -905,8 +953,8 @@ public:
                           InvalidatedSymbols &is,
                           InvalidatedSymbols &inConstIS,
                           StoreManager::InvalidatedRegions *r,
-                          bool includeGlobals)
-    : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals),
+                          GlobalsFilterKind GFK)
+    : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, GFK),
       Ex(ex), Count(count), LCtx(lctx), IS(is), ConstIS(inConstIS), Regions(r){}
 
   /// \param IsConst Specifies if the region we are invalidating is constant.
@@ -949,6 +997,7 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
     for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
       VisitBinding(I.getData());
 
+    // Invalidate the contents of a non-const base region.
     if (!IsConst)
       B = B.remove(baseR);
   }
@@ -981,18 +1030,19 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
   }
 
   // Symbolic region?
-  SymbolRef RegionSym = 0;
-  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
-    RegionSym = SR->getSymbol();
+  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
+    SymbolRef RegionSym = SR->getSymbol();
 
-  if (IsConst) {
     // Mark that symbol touched by the invalidation.
-    ConstIS.insert(RegionSym);
-    return;
+    if (IsConst)
+      ConstIS.insert(RegionSym);
+    else
+      IS.insert(RegionSym);
   }
-  
-  // Mark that symbol touched by the invalidation.
-  IS.insert(RegionSym);
+
+  // Nothing else should be done for a const region.
+  if (IsConst)
+    return;
 
   // Otherwise, we have a normal data region. Record that we touched the region.
   if (Regions)
@@ -1013,7 +1063,13 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
   const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
   QualType T = TR->getValueType();
 
-    // Invalidate the binding.
+  if (isInitiallyIncludedGlobalRegion(baseR)) {
+    // If the region is a global and we are invalidating all globals,
+    // erasing the entry is good enough.  This causes all globals to be lazily
+    // symbolicated from the same base symbol.
+    return;
+  }
+
   if (T->isStructureOrClassType()) {
     // Invalidate the region by setting its default value to
     // conjured symbol. The type of the symbol is irrelavant.
@@ -1031,16 +1087,6 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
     B = B.addBinding(baseR, BindingKey::Default, V);
     return;
   }
-  
-  if (includeGlobals && 
-      isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) {
-    // If the region is a global and we are invalidating all globals,
-    // just erase the entry.  This causes all globals to be lazily
-    // symbolicated from the same base symbol.
-    B = B.removeBinding(baseR);
-    return;
-  }
-  
 
   DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
                                                         T,Count);
@@ -1116,9 +1162,19 @@ RegionStoreManager::invalidateRegions(Store store,
                                       InvalidatedRegions *TopLevelRegions,
                                       InvalidatedRegions *TopLevelConstRegions,
                                       InvalidatedRegions *Invalidated) {
-  RegionBindingsRef B = RegionStoreManager::getRegionBindings(store);
+  GlobalsFilterKind GlobalsFilter;
+  if (Call) {
+    if (Call->isInSystemHeader())
+      GlobalsFilter = GFK_SystemOnly;
+    else
+      GlobalsFilter = GFK_All;
+  } else {
+    GlobalsFilter = GFK_None;
+  }
+
+  RegionBindingsRef B = getRegionBindings(store);
   invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS,
-                            Invalidated, false);
+                            Invalidated, GlobalsFilter);
 
   // Scan the bindings and generate the clusters.
   W.GenerateClusters();
@@ -1138,14 +1194,17 @@ RegionStoreManager::invalidateRegions(Store store,
   // invalidate them. (Note that function-static and immutable globals are never
   // invalidated by this.)
   // TODO: This could possibly be more precise with modules.
-  if (Call) {
+  switch (GlobalsFilter) {
+  case GFK_All:
+    B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind,
+                               Ex, Count, LCtx, B, Invalidated);
+    // FALLTHROUGH
+  case GFK_SystemOnly:
     B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
                                Ex, Count, LCtx, B, Invalidated);
-
-    if (!Call->isInSystemHeader()) {
-      B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind,
-                                 Ex, Count, LCtx, B, Invalidated);
-    }
+    // FALLTHROUGH
+  case GFK_None:
+    break;
   }
 
   return StoreRef(B.asStore(), *this);
@@ -1506,7 +1565,7 @@ SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
       }
     }
   }
-  return getBindingForFieldOrElementCommon(B, R, R->getElementType(),superR);
+  return getBindingForFieldOrElementCommon(B, R, R->getElementType());
 }
 
 SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
@@ -1517,7 +1576,7 @@ SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
     return *V;
 
   QualType Ty = R->getValueType();
-  return getBindingForFieldOrElementCommon(B, R, Ty, R->getSuperRegion());
+  return getBindingForFieldOrElementCommon(B, R, Ty);
 }
 
 Optional<SVal>
@@ -1580,8 +1639,7 @@ SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,
 SVal
 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
                                                       const TypedValueRegion *R,
-                                                      QualType Ty,
-                                                      const MemRegion *superR) {
+                                                      QualType Ty) {
 
   // At this point we have already checked in either getBindingForElement or
   // getBindingForField if 'R' has a direct binding.
@@ -1614,8 +1672,9 @@ RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
   // quickly result in a warning.
   bool hasPartialLazyBinding = false;
 
-  const SubRegion *Base = dyn_cast<SubRegion>(superR);
-  while (Base) {
+  const SubRegion *SR = dyn_cast<SubRegion>(R);
+  while (SR) {
+    const MemRegion *Base = SR->getSuperRegion();
     if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) {
       if (D->getAs<nonloc::LazyCompoundVal>()) {
         hasPartialLazyBinding = true;
@@ -1633,7 +1692,7 @@ RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
     
     // If our super region is a field or element itself, walk up the region
     // hierarchy to see if there is a default value installed in an ancestor.
-    Base = dyn_cast<SubRegion>(Base->getSuperRegion());
+    SR = dyn_cast<SubRegion>(Base);
   }
 
   if (R->hasStackNonParametersStorage()) {
@@ -1641,7 +1700,7 @@ RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
       // Currently we don't reason specially about Clang-style vectors.  Check
       // if superR is a vector and if so return Unknown.
       if (const TypedValueRegion *typedSuperR = 
-            dyn_cast<TypedValueRegion>(superR)) {
+            dyn_cast<TypedValueRegion>(R->getSuperRegion())) {
         if (typedSuperR->getValueType()->isVectorType())
           return UnknownVal();
       }
@@ -1682,26 +1741,6 @@ SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B,
   return getBindingForLazySymbol(R);
 }
 
-static Optional<SVal> getConstValue(SValBuilder &SVB, const VarDecl *VD) {
-  ASTContext &Ctx = SVB.getContext();
-  if (!VD->getType().isConstQualified())
-    return None;
-
-  const Expr *Init = VD->getInit();
-  if (!Init)
-    return None;
-
-  llvm::APSInt Result;
-  if (!Init->isGLValue() && Init->EvaluateAsInt(Result, Ctx))
-    return SVB.makeIntVal(Result);
-
-  if (Init->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull))
-    return SVB.makeNull();
-
-  // FIXME: Handle other possible constant expressions.
-  return None;
-}
-
 SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
                                           const VarRegion *R) {
 
@@ -1718,8 +1757,10 @@ SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
     return svalBuilder.getRegionValueSymbolVal(R);
 
   // Is 'VD' declared constant?  If so, retrieve the constant value.
-  if (Optional<SVal> V = getConstValue(svalBuilder, VD))
-    return *V;
+  if (VD->getType().isConstQualified())
+    if (const Expr *Init = VD->getInit())
+      if (Optional<SVal> V = svalBuilder.getConstantVal(Init))
+        return *V;
 
   // This must come after the check for constants because closure-captured
   // constant variables may appear in UnknownSpaceRegion.
@@ -1891,14 +1932,6 @@ RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) {
   return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V);
 }
 
-// FIXME: this method should be merged into Bind().
-StoreRef RegionStoreManager::bindCompoundLiteral(Store ST,
-                                                 const CompoundLiteralExpr *CL,
-                                                 const LocationContext *LC,
-                                                 SVal V) {
-  return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V);
-}
-
 RegionBindingsRef
 RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B,
                                             const MemRegion *R,
@@ -1907,7 +1940,7 @@ RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B,
 
   if (Loc::isLocType(T))
     V = svalBuilder.makeNull();
-  else if (T->isIntegerType())
+  else if (T->isIntegralOrEnumerationType())
     V = svalBuilder.makeZeroVal(T);
   else if (T->isStructureOrClassType() || T->isArrayType()) {
     // Set the default value to a zero constant when it is a structure
@@ -1977,7 +2010,7 @@ RegionStoreManager::bindArray(RegionBindingsConstRef B,
     else if (ElementTy->isArrayType())
       NewB = bindArray(NewB, ER, *VI);
     else
-      NewB = bind(NewB, svalBuilder.makeLoc(ER), *VI);
+      NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
   }
 
   // If the init list is shorter than the array length, set the
@@ -2018,17 +2051,59 @@ RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B,
     
     NonLoc Idx = svalBuilder.makeArrayIndex(index);
     const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
-    
+
     if (ElemType->isArrayType())
       NewB = bindArray(NewB, ER, *VI);
     else if (ElemType->isStructureOrClassType())
       NewB = bindStruct(NewB, ER, *VI);
     else
-      NewB = bind(NewB, svalBuilder.makeLoc(ER), *VI);
+      NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
   }
   return NewB;
 }
 
+Optional<RegionBindingsRef>
+RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B,
+                                       const TypedValueRegion *R,
+                                       const RecordDecl *RD,
+                                       nonloc::LazyCompoundVal LCV) {
+  FieldVector Fields;
+
+  if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD))
+    if (Class->getNumBases() != 0 || Class->getNumVBases() != 0)
+      return None;
+
+  for (RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
+       I != E; ++I) {
+    const FieldDecl *FD = *I;
+    if (FD->isUnnamedBitfield())
+      continue;
+
+    // If there are too many fields, or if any of the fields are aggregates,
+    // just use the LCV as a default binding.
+    if (Fields.size() == SmallStructLimit)
+      return None;
+
+    QualType Ty = FD->getType();
+    if (!(Ty->isScalarType() || Ty->isReferenceType()))
+      return None;
+
+    Fields.push_back(*I);
+  }
+
+  RegionBindingsRef NewB = B;
+  
+  for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){
+    const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion());
+    SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);
+
+    const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R);
+    NewB = bind(NewB, loc::MemRegionVal(DestFR), V);
+  }
+
+  return NewB;
+}
+
 RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B,
                                                  const TypedValueRegion* R,
                                                  SVal V) {
@@ -2039,13 +2114,19 @@ RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B,
   assert(T->isStructureOrClassType());
 
   const RecordType* RT = T->getAs<RecordType>();
-  RecordDecl *RD = RT->getDecl();
+  const RecordDecl *RD = RT->getDecl();
 
   if (!RD->isCompleteDefinition())
     return B;
 
   // Handle lazy compound values and symbolic values.
-  if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>())
+  if (Optional<nonloc::LazyCompoundVal> LCV =
+        V.getAs<nonloc::LazyCompoundVal>()) {
+    if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV))
+      return *NewB;
+    return bindAggregate(B, R, V);
+  }
+  if (V.getAs<nonloc::SymbolVal>())
     return bindAggregate(B, R, V);
 
   // We may get non-CompoundVal accidentally due to imprecise cast logic or
@@ -2077,7 +2158,7 @@ RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B,
     else if (FTy->isStructureOrClassType())
       NewB = bindStruct(NewB, FR, *VI);
     else
-      NewB = bind(NewB, svalBuilder.makeLoc(FR), *VI);
+      NewB = bind(NewB, loc::MemRegionVal(FR), *VI);
     ++VI;
   }
 
@@ -2115,8 +2196,7 @@ public:
                            ProgramStateManager &stateMgr,
                            RegionBindingsRef b, SymbolReaper &symReaper,
                            const StackFrameContext *LCtx)
-    : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b,
-                                                /* includeGlobals = */ false),
+    : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, GFK_None),
       SymReaper(symReaper), CurrentLCtx(LCtx) {}
 
   // Called by ClusterAnalysis.