contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp

   1 //== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a basic region store model. In this model, we do have field
  11 // sensitivity. But we assume nothing about the heap shape. So recursive data
  12 // structures are largely ignored. Basically we do 1-limiting analysis.
  13 // Parameter pointers are assumed with no aliasing. Pointee objects of
  14 // parameters are created lazily.
  15 //
  16 //===----------------------------------------------------------------------===//
  17 #include "clang/AST/CharUnits.h"
  18 #include "clang/AST/DeclCXX.h"
  19 #include "clang/AST/ExprCXX.h"
  20 #include "clang/Analysis/Analyses/LiveVariables.h"
  21 #include "clang/Analysis/AnalysisContext.h"
  22 #include "clang/Basic/TargetInfo.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  27 #include "llvm/ADT/ImmutableList.h"
  28 #include "llvm/ADT/ImmutableMap.h"
  29 #include "llvm/ADT/Optional.h"
  30 #include "llvm/Support/raw_ostream.h"
  31
  32 using namespace clang;
  33 using namespace ento;
  34 using llvm::Optional;
  35
  36 //===----------------------------------------------------------------------===//
  37 // Representation of binding keys.
  38 //===----------------------------------------------------------------------===//
  39
  40 namespace {
  41 class BindingKey {
  42 public:
  43   enum Kind { Direct = 0x0, Default = 0x1 };
  44 private:
  45   llvm ::PointerIntPair<const MemRegion*, 1> P;
  46   uint64_t Offset;
  47
  48   explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)
  49     : P(r, (unsigned) k), Offset(offset) {}
  50 public:
  51
  52   bool isDirect() const { return P.getInt() == Direct; }
  53
  54   const MemRegion *getRegion() const { return P.getPointer(); }
  55   uint64_t getOffset() const { return Offset; }
  56
  57   void Profile(llvm::FoldingSetNodeID& ID) const {
  58     ID.AddPointer(P.getOpaqueValue());
  59     ID.AddInteger(Offset);
  60   }
  61
  62   static BindingKey Make(const MemRegion *R, Kind k);
  63
  64   bool operator<(const BindingKey &X) const {
  65     if (P.getOpaqueValue() < X.P.getOpaqueValue())
  66       return true;
  67     if (P.getOpaqueValue() > X.P.getOpaqueValue())
  68       return false;
  69     return Offset < X.Offset;
  70   }
  71
  72   bool operator==(const BindingKey &X) const {
  73     return P.getOpaqueValue() == X.P.getOpaqueValue() &&
  74            Offset == X.Offset;
  75   }
  76
  77   bool isValid() const {
  78     return getRegion() != NULL;
  79   }
  80 };
  81 } // end anonymous namespace
  82
  83 BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
  84   if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
  85     const RegionRawOffset &O = ER->getAsArrayOffset();
  86
  87     // FIXME: There are some ElementRegions for which we cannot compute
  88     // raw offsets yet, including regions with symbolic offsets. These will be
  89     // ignored by the store.
  90     return BindingKey(O.getRegion(), O.getOffset().getQuantity(), k);
  91   }
  92
  93   return BindingKey(R, 0, k);
  94 }
  95
  96 namespace llvm {
  97   static inline
  98   raw_ostream &operator<<(raw_ostream &os, BindingKey K) {
  99     os << '(' << K.getRegion() << ',' << K.getOffset()
 100        << ',' << (K.isDirect() ? "direct" : "default")
 101        << ')';
 102     return os;
 103   }
 104 } // end llvm namespace
 105
 106 //===----------------------------------------------------------------------===//
 107 // Actual Store type.
 108 //===----------------------------------------------------------------------===//
 109
 110 typedef llvm::ImmutableMap<BindingKey, SVal> RegionBindings;
 111
 112 //===----------------------------------------------------------------------===//
 113 // Fine-grained control of RegionStoreManager.
 114 //===----------------------------------------------------------------------===//
 115
 116 namespace {
 117 struct minimal_features_tag {};
 118 struct maximal_features_tag {};
 119
 120 class RegionStoreFeatures {
 121   bool SupportsFields;
 122 public:
 123   RegionStoreFeatures(minimal_features_tag) :
 124     SupportsFields(false) {}
 125
 126   RegionStoreFeatures(maximal_features_tag) :
 127     SupportsFields(true) {}
 128
 129   void enableFields(bool t) { SupportsFields = t; }
 130
 131   bool supportsFields() const { return SupportsFields; }
 132 };
 133 }
 134
 135 //===----------------------------------------------------------------------===//
 136 // Main RegionStore logic.
 137 //===----------------------------------------------------------------------===//
 138
 139 namespace {
 140
 141 class RegionStoreSubRegionMap : public SubRegionMap {
 142 public:
 143   typedef llvm::ImmutableSet<const MemRegion*> Set;
 144   typedef llvm::DenseMap<const MemRegion*, Set> Map;
 145 private:
 146   Set::Factory F;
 147   Map M;
 148 public:
 149   bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
 150     Map::iterator I = M.find(Parent);
 151
 152     if (I == M.end()) {
 153       M.insert(std::make_pair(Parent, F.add(F.getEmptySet(), SubRegion)));
 154       return true;
 155     }
 156
 157     I->second = F.add(I->second, SubRegion);
 158     return false;
 159   }
 160
 161   void process(SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
 162
 163   ~RegionStoreSubRegionMap() {}
 164
 165   const Set *getSubRegions(const MemRegion *Parent) const {
 166     Map::const_iterator I = M.find(Parent);
 167     return I == M.end() ? NULL : &I->second;
 168   }
 169
 170   bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
 171     Map::const_iterator I = M.find(Parent);
 172
 173     if (I == M.end())
 174       return true;
 175
 176     Set S = I->second;
 177     for (Set::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) {
 178       if (!V.Visit(Parent, *SI))
 179         return false;
 180     }
 181
 182     return true;
 183   }
 184 };
 185
 186 void
 187 RegionStoreSubRegionMap::process(SmallVectorImpl<const SubRegion*> &WL,
 188                                  const SubRegion *R) {
 189   const MemRegion *superR = R->getSuperRegion();
 190   if (add(superR, R))
 191     if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
 192       WL.push_back(sr);
 193 }
 194
 195 class RegionStoreManager : public StoreManager {
 196   const RegionStoreFeatures Features;
 197   RegionBindings::Factory RBFactory;
 198
 199 public:
 200   RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f)
 201     : StoreManager(mgr),
 202       Features(f),
 203       RBFactory(mgr.getAllocator()) {}
 204
 205   SubRegionMap *getSubRegionMap(Store store) {
 206     return getRegionStoreSubRegionMap(store);
 207   }
 208
 209   RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
 210
 211   Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
 212   /// getDefaultBinding - Returns an SVal* representing an optional default
 213   ///  binding associated with a region and its subregions.
 214   Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
 215
 216   /// setImplicitDefaultValue - Set the default binding for the provided
 217   ///  MemRegion to the value implicitly defined for compound literals when
 218   ///  the value is not specified.
 219   StoreRef setImplicitDefaultValue(Store store, const MemRegion *R, QualType T);
 220
 221   /// ArrayToPointer - Emulates the "decay" of an array to a pointer
 222   ///  type.  'Array' represents the lvalue of the array being decayed
 223   ///  to a pointer, and the returned SVal represents the decayed
 224   ///  version of that lvalue (i.e., a pointer to the first element of
 225   ///  the array).  This is called by ExprEngine when evaluating
 226   ///  casts from arrays to pointers.
 227   SVal ArrayToPointer(Loc Array);
 228
 229   /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it.
 230   virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType);
 231
 232   /// \brief Evaluates C++ dynamic_cast cast.
 233   /// The callback may result in the following 3 scenarios:
 234   ///  - Successful cast (ex: derived is subclass of base).
 235   ///  - Failed cast (ex: derived is definitely not a subclass of base).
 236   ///  - We don't know (base is a symbolic region and we don't have
 237   ///    enough info to determine if the cast will succeed at run time).
 238   /// The function returns an SVal representing the derived class; it's
 239   /// valid only if Failed flag is set to false.
 240   virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,bool &Failed);
 241
 242   StoreRef getInitialStore(const LocationContext *InitLoc) {
 243     return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this);
 244   }
 245
 246   //===-------------------------------------------------------------------===//
 247   // Binding values to regions.
 248   //===-------------------------------------------------------------------===//
 249   RegionBindings invalidateGlobalRegion(MemRegion::Kind K,
 250                                         const Expr *Ex,
 251                                         unsigned Count,
 252                                         const LocationContext *LCtx,
 253                                         RegionBindings B,
 254                                         InvalidatedRegions *Invalidated);
 255
 256   StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions,
 257                              const Expr *E, unsigned Count,
 258                              const LocationContext *LCtx,
 259                              InvalidatedSymbols &IS,
 260                              const CallOrObjCMessage *Call,
 261                              InvalidatedRegions *Invalidated);
 262
 263 public:   // Made public for helper classes.
 264
 265   void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
 266                                RegionStoreSubRegionMap &M);
 267
 268   RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V);
 269
 270   RegionBindings addBinding(RegionBindings B, const MemRegion *R,
 271                      BindingKey::Kind k, SVal V);
 272
 273   const SVal *lookup(RegionBindings B, BindingKey K);
 274   const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k);
 275
 276   RegionBindings removeBinding(RegionBindings B, BindingKey K);
 277   RegionBindings removeBinding(RegionBindings B, const MemRegion *R,
 278                         BindingKey::Kind k);
 279
 280   RegionBindings removeBinding(RegionBindings B, const MemRegion *R) {
 281     return removeBinding(removeBinding(B, R, BindingKey::Direct), R,
 282                         BindingKey::Default);
 283   }
 284
 285 public: // Part of public interface to class.
 286
 287   StoreRef Bind(Store store, Loc LV, SVal V);
 288
 289   // BindDefault is only used to initialize a region with a default value.
 290   StoreRef BindDefault(Store store, const MemRegion *R, SVal V) {
 291     RegionBindings B = GetRegionBindings(store);
 292     assert(!lookup(B, R, BindingKey::Default));
 293     assert(!lookup(B, R, BindingKey::Direct));
 294     return StoreRef(addBinding(B, R, BindingKey::Default, V)
 295                       .getRootWithoutRetain(), *this);
 296   }
 297
 298   StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr *CL,
 299                                const LocationContext *LC, SVal V);
 300
 301   StoreRef BindDecl(Store store, const VarRegion *VR, SVal InitVal);
 302
 303   StoreRef BindDeclWithNoInit(Store store, const VarRegion *) {
 304     return StoreRef(store, *this);
 305   }
 306
 307   /// BindStruct - Bind a compound value to a structure.
 308   StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V);
 309
 310   StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V);
 311
 312   /// KillStruct - Set the entire struct to unknown.
 313   StoreRef KillStruct(Store store, const TypedRegion* R, SVal DefaultVal);
 314
 315   StoreRef Remove(Store store, Loc LV);
 316
 317   void incrementReferenceCount(Store store) {
 318     GetRegionBindings(store).manualRetain();
 319   }
 320
 321   /// If the StoreManager supports it, decrement the reference count of
 322   /// the specified Store object.  If the reference count hits 0, the memory
 323   /// associated with the object is recycled.
 324   void decrementReferenceCount(Store store) {
 325     GetRegionBindings(store).manualRelease();
 326   }
 327
 328   bool includedInBindings(Store store, const MemRegion *region) const;
 329
 330   /// \brief Return the value bound to specified location in a given state.
 331   ///
 332   /// The high level logic for this method is this:
 333   /// getBinding (L)
 334   ///   if L has binding
 335   ///     return L's binding
 336   ///   else if L is in killset
 337   ///     return unknown
 338   ///   else
 339   ///     if L is on stack or heap
 340   ///       return undefined
 341   ///     else
 342   ///       return symbolic
 343   SVal getBinding(Store store, Loc L, QualType T = QualType());
 344
 345   SVal getBindingForElement(Store store, const ElementRegion *R);
 346
 347   SVal getBindingForField(Store store, const FieldRegion *R);
 348
 349   SVal getBindingForObjCIvar(Store store, const ObjCIvarRegion *R);
 350
 351   SVal getBindingForVar(Store store, const VarRegion *R);
 352
 353   SVal getBindingForLazySymbol(const TypedValueRegion *R);
 354
 355   SVal getBindingForFieldOrElementCommon(Store store, const TypedValueRegion *R,
 356                                          QualType Ty, const MemRegion *superR);
 357
 358   SVal getLazyBinding(const MemRegion *lazyBindingRegion,
 359                       Store lazyBindingStore);
 360
 361   /// Get bindings for the values in a struct and return a CompoundVal, used
 362   /// when doing struct copy:
 363   /// struct s x, y;
 364   /// x = y;
 365   /// y's value is retrieved by this method.
 366   SVal getBindingForStruct(Store store, const TypedValueRegion* R);
 367
 368   SVal getBindingForArray(Store store, const TypedValueRegion* R);
 369
 370   /// Used to lazily generate derived symbols for bindings that are defined
 371   ///  implicitly by default bindings in a super region.
 372   Optional<SVal> getBindingForDerivedDefaultValue(RegionBindings B,
 373                                                   const MemRegion *superR,
 374                                                   const TypedValueRegion *R,
 375                                                   QualType Ty);
 376
 377   /// Get the state and region whose binding this region R corresponds to.
 378   std::pair<Store, const MemRegion*>
 379   GetLazyBinding(RegionBindings B, const MemRegion *R,
 380                  const MemRegion *originalRegion);
 381
 382   StoreRef CopyLazyBindings(nonloc::LazyCompoundVal V, Store store,
 383                             const TypedRegion *R);
 384
 385   //===------------------------------------------------------------------===//
 386   // State pruning.
 387   //===------------------------------------------------------------------===//
 388
 389   /// removeDeadBindings - Scans the RegionStore of 'state' for dead values.
 390   ///  It returns a new Store with these values removed.
 391   StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
 392                               SymbolReaper& SymReaper);
 393
 394   StoreRef enterStackFrame(ProgramStateRef state,
 395                            const LocationContext *callerCtx,
 396                            const StackFrameContext *calleeCtx);
 397
 398   //===------------------------------------------------------------------===//
 399   // Region "extents".
 400   //===------------------------------------------------------------------===//
 401
 402   // FIXME: This method will soon be eliminated; see the note in Store.h.
 403   DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
 404                                          const MemRegion* R, QualType EleTy);
 405
 406   //===------------------------------------------------------------------===//
 407   // Utility methods.
 408   //===------------------------------------------------------------------===//
 409
 410   static inline RegionBindings GetRegionBindings(Store store) {
 411     return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
 412   }
 413
 414   void print(Store store, raw_ostream &Out, const char* nl,
 415              const char *sep);
 416
 417   void iterBindings(Store store, BindingsHandler& f) {
 418     RegionBindings B = GetRegionBindings(store);
 419     for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
 420       const BindingKey &K = I.getKey();
 421       if (!K.isDirect())
 422         continue;
 423       if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) {
 424         // FIXME: Possibly incorporate the offset?
 425         if (!f.HandleBinding(*this, store, R, I.getData()))
 426           return;
 427       }
 428     }
 429   }
 430 };
 431
 432 } // end anonymous namespace
 433
 434 //===----------------------------------------------------------------------===//
 435 // RegionStore creation.
 436 //===----------------------------------------------------------------------===//
 437
 438 StoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) {
 439   RegionStoreFeatures F = maximal_features_tag();
 440   return new RegionStoreManager(StMgr, F);
 441 }
 442
 443 StoreManager *
 444 ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) {
 445   RegionStoreFeatures F = minimal_features_tag();
 446   F.enableFields(true);
 447   return new RegionStoreManager(StMgr, F);
 448 }
 449
 450
 451 RegionStoreSubRegionMap*
 452 RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
 453   RegionBindings B = GetRegionBindings(store);
 454   RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
 455
 456   SmallVector<const SubRegion*, 10> WL;
 457
 458   for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
 459     if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
 460       M->process(WL, R);
 461
 462   // We also need to record in the subregion map "intermediate" regions that
 463   // don't have direct bindings but are super regions of those that do.
 464   while (!WL.empty()) {
 465     const SubRegion *R = WL.back();
 466     WL.pop_back();
 467     M->process(WL, R);
 468   }
 469
 470   return M;
 471 }
 472
 473 //===----------------------------------------------------------------------===//
 474 // Region Cluster analysis.
 475 //===----------------------------------------------------------------------===//
 476
 477 namespace {
 478 template <typename DERIVED>
 479 class ClusterAnalysis  {
 480 protected:
 481   typedef BumpVector<BindingKey> RegionCluster;
 482   typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap;
 483   llvm::DenseMap<const RegionCluster*, unsigned> Visited;
 484   typedef SmallVector<std::pair<const MemRegion *, RegionCluster*>, 10>
 485     WorkList;
 486
 487   BumpVectorContext BVC;
 488   ClusterMap ClusterM;
 489   WorkList WL;
 490
 491   RegionStoreManager &RM;
 492   ASTContext &Ctx;
 493   SValBuilder &svalBuilder;
 494
 495   RegionBindings B;
 496
 497   const bool includeGlobals;
 498
 499 public:
 500   ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
 501                   RegionBindings b, const bool includeGlobals)
 502     : RM(rm), Ctx(StateMgr.getContext()),
 503       svalBuilder(StateMgr.getSValBuilder()),
 504       B(b), includeGlobals(includeGlobals) {}
 505
 506   RegionBindings getRegionBindings() const { return B; }
 507
 508   RegionCluster &AddToCluster(BindingKey K) {
 509     const MemRegion *R = K.getRegion();
 510     const MemRegion *baseR = R->getBaseRegion();
 511     RegionCluster &C = getCluster(baseR);
 512     C.push_back(K, BVC);
 513     static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C);
 514     return C;
 515   }
 516
 517   bool isVisited(const MemRegion *R) {
 518     return (bool) Visited[&getCluster(R->getBaseRegion())];
 519   }
 520
 521   RegionCluster& getCluster(const MemRegion *R) {
 522     RegionCluster *&CRef = ClusterM[R];
 523     if (!CRef) {
 524       void *Mem = BVC.getAllocator().template Allocate<RegionCluster>();
 525       CRef = new (Mem) RegionCluster(BVC, 10);
 526     }
 527     return *CRef;
 528   }
 529
 530   void GenerateClusters() {
 531       // Scan the entire set of bindings and make the region clusters.
 532     for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
 533       RegionCluster &C = AddToCluster(RI.getKey());
 534       if (const MemRegion *R = RI.getData().getAsRegion()) {
 535         // Generate a cluster, but don't add the region to the cluster
 536         // if there aren't any bindings.
 537         getCluster(R->getBaseRegion());
 538       }
 539       if (includeGlobals) {
 540         const MemRegion *R = RI.getKey().getRegion();
 541         if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 542           AddToWorkList(R, C);
 543       }
 544     }
 545   }
 546
 547   bool AddToWorkList(const MemRegion *R, RegionCluster &C) {
 548     if (unsigned &visited = Visited[&C])
 549       return false;
 550     else
 551       visited = 1;
 552
 553     WL.push_back(std::make_pair(R, &C));
 554     return true;
 555   }
 556
 557   bool AddToWorkList(BindingKey K) {
 558     return AddToWorkList(K.getRegion());
 559   }
 560
 561   bool AddToWorkList(const MemRegion *R) {
 562     const MemRegion *baseR = R->getBaseRegion();
 563     return AddToWorkList(baseR, getCluster(baseR));
 564   }
 565
 566   void RunWorkList() {
 567     while (!WL.empty()) {
 568       const MemRegion *baseR;
 569       RegionCluster *C;
 570       llvm::tie(baseR, C) = WL.back();
 571       WL.pop_back();
 572
 573         // First visit the cluster.
 574       static_cast<DERIVED*>(this)->VisitCluster(baseR, C->begin(), C->end());
 575
 576         // Next, visit the base region.
 577       static_cast<DERIVED*>(this)->VisitBaseRegion(baseR);
 578     }
 579   }
 580
 581 public:
 582   void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C) {}
 583   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E) {}
 584   void VisitBaseRegion(const MemRegion *baseR) {}
 585 };
 586 }
 587
 588 //===----------------------------------------------------------------------===//
 589 // Binding invalidation.
 590 //===----------------------------------------------------------------------===//
 591
 592 void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
 593                                                  const MemRegion *R,
 594                                                  RegionStoreSubRegionMap &M) {
 595
 596   if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R))
 597     for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end();
 598          I != E; ++I)
 599       RemoveSubRegionBindings(B, *I, M);
 600
 601   B = removeBinding(B, R);
 602 }
 603
 604 namespace {
 605 class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker>
 606 {
 607   const Expr *Ex;
 608   unsigned Count;
 609   const LocationContext *LCtx;
 610   StoreManager::InvalidatedSymbols &IS;
 611   StoreManager::InvalidatedRegions *Regions;
 612 public:
 613   invalidateRegionsWorker(RegionStoreManager &rm,
 614                           ProgramStateManager &stateMgr,
 615                           RegionBindings b,
 616                           const Expr *ex, unsigned count,
 617                           const LocationContext *lctx,
 618                           StoreManager::InvalidatedSymbols &is,
 619                           StoreManager::InvalidatedRegions *r,
 620                           bool includeGlobals)
 621     : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals),
 622       Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {}
 623
 624   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
 625   void VisitBaseRegion(const MemRegion *baseR);
 626
 627 private:
 628   void VisitBinding(SVal V);
 629 };
 630 }
 631
 632 void invalidateRegionsWorker::VisitBinding(SVal V) {
 633   // A symbol?  Mark it touched by the invalidation.
 634   if (SymbolRef Sym = V.getAsSymbol())
 635     IS.insert(Sym);
 636
 637   if (const MemRegion *R = V.getAsRegion()) {
 638     AddToWorkList(R);
 639     return;
 640   }
 641
 642   // Is it a LazyCompoundVal?  All references get invalidated as well.
 643   if (const nonloc::LazyCompoundVal *LCS =
 644         dyn_cast<nonloc::LazyCompoundVal>(&V)) {
 645
 646     const MemRegion *LazyR = LCS->getRegion();
 647     RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
 648
 649     for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
 650       const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
 651       if (baseR && baseR->isSubRegionOf(LazyR))
 652         VisitBinding(RI.getData());
 653     }
 654
 655     return;
 656   }
 657 }
 658
 659 void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
 660                                            BindingKey *I, BindingKey *E) {
 661   for ( ; I != E; ++I) {
 662     // Get the old binding.  Is it a region?  If so, add it to the worklist.
 663     const BindingKey &K = *I;
 664     if (const SVal *V = RM.lookup(B, K))
 665       VisitBinding(*V);
 666
 667     B = RM.removeBinding(B, K);
 668   }
 669 }
 670
 671 void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
 672   // Symbolic region?  Mark that symbol touched by the invalidation.
 673   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
 674     IS.insert(SR->getSymbol());
 675
 676   // BlockDataRegion?  If so, invalidate captured variables that are passed
 677   // by reference.
 678   if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
 679     for (BlockDataRegion::referenced_vars_iterator
 680          BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
 681          BI != BE; ++BI) {
 682       const VarRegion *VR = *BI;
 683       const VarDecl *VD = VR->getDecl();
 684       if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage())
 685         AddToWorkList(VR);
 686     }
 687     return;
 688   }
 689
 690   // Otherwise, we have a normal data region. Record that we touched the region.
 691   if (Regions)
 692     Regions->push_back(baseR);
 693
 694   if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
 695     // Invalidate the region by setting its default value to
 696     // conjured symbol. The type of the symbol is irrelavant.
 697     DefinedOrUnknownSVal V =
 698       svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count);
 699     B = RM.addBinding(B, baseR, BindingKey::Default, V);
 700     return;
 701   }
 702
 703   if (!baseR->isBoundable())
 704     return;
 705
 706   const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
 707   QualType T = TR->getValueType();
 708
 709     // Invalidate the binding.
 710   if (T->isStructureOrClassType()) {
 711     // Invalidate the region by setting its default value to
 712     // conjured symbol. The type of the symbol is irrelavant.
 713     DefinedOrUnknownSVal V =
 714       svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count);
 715     B = RM.addBinding(B, baseR, BindingKey::Default, V);
 716     return;
 717   }
 718
 719   if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
 720       // Set the default value of the array to conjured symbol.
 721     DefinedOrUnknownSVal V =
 722     svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx,
 723                                      AT->getElementType(), Count);
 724     B = RM.addBinding(B, baseR, BindingKey::Default, V);
 725     return;
 726   }
 727
 728   if (includeGlobals &&
 729       isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) {
 730     // If the region is a global and we are invalidating all globals,
 731     // just erase the entry.  This causes all globals to be lazily
 732     // symbolicated from the same base symbol.
 733     B = RM.removeBinding(B, baseR);
 734     return;
 735   }
 736
 737
 738   DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx,
 739                                                             T,Count);
 740   assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
 741   B = RM.addBinding(B, baseR, BindingKey::Direct, V);
 742 }
 743
 744 RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K,
 745                                                           const Expr *Ex,
 746                                                           unsigned Count,
 747                                                     const LocationContext *LCtx,
 748                                                           RegionBindings B,
 749                                             InvalidatedRegions *Invalidated) {
 750   // Bind the globals memory space to a new symbol that we will use to derive
 751   // the bindings for all globals.
 752   const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);
 753   SVal V =
 754       svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex, LCtx,
 755           /* symbol type, doesn't matter */ Ctx.IntTy,
 756           Count);
 757
 758   B = removeBinding(B, GS);
 759   B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V);
 760
 761   // Even if there are no bindings in the global scope, we still need to
 762   // record that we touched it.
 763   if (Invalidated)
 764     Invalidated->push_back(GS);
 765
 766   return B;
 767 }
 768
 769 StoreRef RegionStoreManager::invalidateRegions(Store store,
 770                                             ArrayRef<const MemRegion *> Regions,
 771                                                const Expr *Ex, unsigned Count,
 772                                                const LocationContext *LCtx,
 773                                                InvalidatedSymbols &IS,
 774                                                const CallOrObjCMessage *Call,
 775                                               InvalidatedRegions *Invalidated) {
 776   invalidateRegionsWorker W(*this, StateMgr,
 777                             RegionStoreManager::GetRegionBindings(store),
 778                             Ex, Count, LCtx, IS, Invalidated, false);
 779
 780   // Scan the bindings and generate the clusters.
 781   W.GenerateClusters();
 782
 783   // Add the regions to the worklist.
 784   for (ArrayRef<const MemRegion *>::iterator
 785        I = Regions.begin(), E = Regions.end(); I != E; ++I)
 786     W.AddToWorkList(*I);
 787
 788   W.RunWorkList();
 789
 790   // Return the new bindings.
 791   RegionBindings B = W.getRegionBindings();
 792
 793   // For all globals which are not static nor immutable: determine which global
 794   // regions should be invalidated and invalidate them.
 795   // TODO: This could possibly be more precise with modules.
 796   //
 797   // System calls invalidate only system globals.
 798   if (Call && Call->isInSystemHeader()) {
 799     B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
 800                                Ex, Count, LCtx, B, Invalidated);
 801   // Internal calls might invalidate both system and internal globals.
 802   } else {
 803     B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
 804                                Ex, Count, LCtx, B, Invalidated);
 805     B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind,
 806                                Ex, Count, LCtx, B, Invalidated);
 807   }
 808
 809   return StoreRef(B.getRootWithoutRetain(), *this);
 810 }
 811
 812 //===----------------------------------------------------------------------===//
 813 // Extents for regions.
 814 //===----------------------------------------------------------------------===//
 815
 816 DefinedOrUnknownSVal
 817 RegionStoreManager::getSizeInElements(ProgramStateRef state,
 818                                       const MemRegion *R,
 819                                       QualType EleTy) {
 820   SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder);
 821   const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
 822   if (!SizeInt)
 823     return UnknownVal();
 824
 825   CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
 826
 827   if (Ctx.getAsVariableArrayType(EleTy)) {
 828     // FIXME: We need to track extra state to properly record the size
 829     // of VLAs.  Returning UnknownVal here, however, is a stop-gap so that
 830     // we don't have a divide-by-zero below.
 831     return UnknownVal();
 832   }
 833
 834   CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
 835
 836   // If a variable is reinterpreted as a type that doesn't fit into a larger
 837   // type evenly, round it down.
 838   // This is a signed value, since it's used in arithmetic with signed indices.
 839   return svalBuilder.makeIntVal(RegionSize / EleSize, false);
 840 }
 841
 842 //===----------------------------------------------------------------------===//
 843 // Location and region casting.
 844 //===----------------------------------------------------------------------===//
 845
 846 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
 847 ///  type.  'Array' represents the lvalue of the array being decayed
 848 ///  to a pointer, and the returned SVal represents the decayed
 849 ///  version of that lvalue (i.e., a pointer to the first element of
 850 ///  the array).  This is called by ExprEngine when evaluating casts
 851 ///  from arrays to pointers.
 852 SVal RegionStoreManager::ArrayToPointer(Loc Array) {
 853   if (!isa<loc::MemRegionVal>(Array))
 854     return UnknownVal();
 855
 856   const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
 857   const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R);
 858
 859   if (!ArrayR)
 860     return UnknownVal();
 861
 862   // Strip off typedefs from the ArrayRegion's ValueType.
 863   QualType T = ArrayR->getValueType().getDesugaredType(Ctx);
 864   const ArrayType *AT = cast<ArrayType>(T);
 865   T = AT->getElementType();
 866
 867   NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
 868   return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx));
 869 }
 870
 871 SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) {
 872   const CXXRecordDecl *baseDecl;
 873   if (baseType->isPointerType())
 874     baseDecl = baseType->getCXXRecordDeclForPointerType();
 875   else
 876     baseDecl = baseType->getAsCXXRecordDecl();
 877
 878   assert(baseDecl && "not a CXXRecordDecl?");
 879
 880   loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived);
 881   if (!derivedRegVal)
 882     return derived;
 883
 884   const MemRegion *baseReg =
 885     MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion());
 886
 887   return loc::MemRegionVal(baseReg);
 888 }
 889
 890 SVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType,
 891                                          bool &Failed) {
 892   Failed = false;
 893
 894   loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base);
 895   if (!baseRegVal)
 896     return UnknownVal();
 897   const MemRegion *BaseRegion = baseRegVal->stripCasts();
 898
 899   // Assume the derived class is a pointer or a reference to a CXX record.
 900   derivedType = derivedType->getPointeeType();
 901   assert(!derivedType.isNull());
 902   const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl();
 903   if (!DerivedDecl && !derivedType->isVoidType())
 904     return UnknownVal();
 905
 906   // Drill down the CXXBaseObject chains, which represent upcasts (casts from
 907   // derived to base).
 908   const MemRegion *SR = BaseRegion;
 909   while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) {
 910     QualType BaseType = TSR->getLocationType()->getPointeeType();
 911     assert(!BaseType.isNull());
 912     const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl();
 913     if (!SRDecl)
 914       return UnknownVal();
 915
 916     // If found the derived class, the cast succeeds.
 917     if (SRDecl == DerivedDecl)
 918       return loc::MemRegionVal(TSR);
 919
 920     // If the region type is a subclass of the derived type.
 921     if (!derivedType->isVoidType() && SRDecl->isDerivedFrom(DerivedDecl)) {
 922       // This occurs in two cases.
 923       // 1) We are processing an upcast.
 924       // 2) We are processing a downcast but we jumped directly from the
 925       // ancestor to a child of the cast value, so conjure the
 926       // appropriate region to represent value (the intermediate node).
 927       return loc::MemRegionVal(MRMgr.getCXXBaseObjectRegion(DerivedDecl,
 928                                                             BaseRegion));
 929     }
 930
 931     // If super region is not a parent of derived class, the cast definitely
 932     // fails.
 933     if (!derivedType->isVoidType() &&
 934         DerivedDecl->isProvablyNotDerivedFrom(SRDecl)) {
 935       Failed = true;
 936       return UnknownVal();
 937     }
 938
 939     if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR))
 940       // Drill down the chain to get the derived classes.
 941       SR = R->getSuperRegion();
 942     else {
 943       // We reached the bottom of the hierarchy.
 944
 945       // If this is a cast to void*, return the region.
 946       if (derivedType->isVoidType())
 947         return loc::MemRegionVal(TSR);
 948
 949       // We did not find the derived class. We we must be casting the base to
 950       // derived, so the cast should fail.
 951       Failed = true;
 952       return UnknownVal();
 953     }
 954   }
 955
 956   return UnknownVal();
 957 }
 958
 959 //===----------------------------------------------------------------------===//
 960 // Loading values from regions.
 961 //===----------------------------------------------------------------------===//
 962
 963 Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
 964                                                     const MemRegion *R) {
 965
 966   if (const SVal *V = lookup(B, R, BindingKey::Direct))
 967     return *V;
 968
 969   return Optional<SVal>();
 970 }
 971
 972 Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
 973                                                      const MemRegion *R) {
 974   if (R->isBoundable())
 975     if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R))
 976       if (TR->getValueType()->isUnionType())
 977         return UnknownVal();
 978
 979   if (const SVal *V = lookup(B, R, BindingKey::Default))
 980     return *V;
 981
 982   return Optional<SVal>();
 983 }
 984
 985 SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) {
 986   assert(!isa<UnknownVal>(L) && "location unknown");
 987   assert(!isa<UndefinedVal>(L) && "location undefined");
 988
 989   // For access to concrete addresses, return UnknownVal.  Checks
 990   // for null dereferences (and similar errors) are done by checkers, not
 991   // the Store.
 992   // FIXME: We can consider lazily symbolicating such memory, but we really
 993   // should defer this when we can reason easily about symbolicating arrays
 994   // of bytes.
 995   if (isa<loc::ConcreteInt>(L)) {
 996     return UnknownVal();
 997   }
 998   if (!isa<loc::MemRegionVal>(L)) {
 999     return UnknownVal();
1000   }
1001
1002   const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
1003
1004   if (isa<AllocaRegion>(MR) ||
1005       isa<SymbolicRegion>(MR) ||
1006       isa<CodeTextRegion>(MR)) {
1007     if (T.isNull()) {
1008       if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR))
1009         T = TR->getLocationType();
1010       else {
1011         const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
1012         T = SR->getSymbol()->getType(Ctx);
1013       }
1014     }
1015     MR = GetElementZeroRegion(MR, T);
1016   }
1017
1018   // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1019   //  instead of 'Loc', and have the other Loc cases handled at a higher level.
1020   const TypedValueRegion *R = cast<TypedValueRegion>(MR);
1021   QualType RTy = R->getValueType();
1022
1023   // FIXME: We should eventually handle funny addressing.  e.g.:
1024   //
1025   //   int x = ...;
1026   //   int *p = &x;
1027   //   char *q = (char*) p;
1028   //   char c = *q;  // returns the first byte of 'x'.
1029   //
1030   // Such funny addressing will occur due to layering of regions.
1031
1032   if (RTy->isStructureOrClassType())
1033     return getBindingForStruct(store, R);
1034
1035   // FIXME: Handle unions.
1036   if (RTy->isUnionType())
1037     return UnknownVal();
1038
1039   if (RTy->isArrayType())
1040     return getBindingForArray(store, R);
1041
1042   // FIXME: handle Vector types.
1043   if (RTy->isVectorType())
1044     return UnknownVal();
1045
1046   if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
1047     return CastRetrievedVal(getBindingForField(store, FR), FR, T, false);
1048
1049   if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1050     // FIXME: Here we actually perform an implicit conversion from the loaded
1051     // value to the element type.  Eventually we want to compose these values
1052     // more intelligently.  For example, an 'element' can encompass multiple
1053     // bound regions (e.g., several bound bytes), or could be a subset of
1054     // a larger value.
1055     return CastRetrievedVal(getBindingForElement(store, ER), ER, T, false);
1056   }
1057
1058   if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1059     // FIXME: Here we actually perform an implicit conversion from the loaded
1060     // value to the ivar type.  What we should model is stores to ivars
1061     // that blow past the extent of the ivar.  If the address of the ivar is
1062     // reinterpretted, it is possible we stored a different value that could
1063     // fit within the ivar.  Either we need to cast these when storing them
1064     // or reinterpret them lazily (as we do here).
1065     return CastRetrievedVal(getBindingForObjCIvar(store, IVR), IVR, T, false);
1066   }
1067
1068   if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1069     // FIXME: Here we actually perform an implicit conversion from the loaded
1070     // value to the variable type.  What we should model is stores to variables
1071     // that blow past the extent of the variable.  If the address of the
1072     // variable is reinterpretted, it is possible we stored a different value
1073     // that could fit within the variable.  Either we need to cast these when
1074     // storing them or reinterpret them lazily (as we do here).
1075     return CastRetrievedVal(getBindingForVar(store, VR), VR, T, false);
1076   }
1077
1078   RegionBindings B = GetRegionBindings(store);
1079   const SVal *V = lookup(B, R, BindingKey::Direct);
1080
1081   // Check if the region has a binding.
1082   if (V)
1083     return *V;
1084
1085   // The location does not have a bound value.  This means that it has
1086   // the value it had upon its creation and/or entry to the analyzed
1087   // function/method.  These are either symbolic values or 'undefined'.
1088   if (R->hasStackNonParametersStorage()) {
1089     // All stack variables are considered to have undefined values
1090     // upon creation.  All heap allocated blocks are considered to
1091     // have undefined values as well unless they are explicitly bound
1092     // to specific values.
1093     return UndefinedVal();
1094   }
1095
1096   // All other values are symbolic.
1097   return svalBuilder.getRegionValueSymbolVal(R);
1098 }
1099
1100 std::pair<Store, const MemRegion *>
1101 RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R,
1102                                    const MemRegion *originalRegion) {
1103
1104   if (originalRegion != R) {
1105     if (Optional<SVal> OV = getDefaultBinding(B, R)) {
1106       if (const nonloc::LazyCompoundVal *V =
1107           dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
1108         return std::make_pair(V->getStore(), V->getRegion());
1109     }
1110   }
1111
1112   if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1113     const std::pair<Store, const MemRegion *> &X =
1114       GetLazyBinding(B, ER->getSuperRegion(), originalRegion);
1115
1116     if (X.second)
1117       return std::make_pair(X.first,
1118                             MRMgr.getElementRegionWithSuper(ER, X.second));
1119   }
1120   else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1121     const std::pair<Store, const MemRegion *> &X =
1122       GetLazyBinding(B, FR->getSuperRegion(), originalRegion);
1123
1124     if (X.second)
1125       return std::make_pair(X.first,
1126                             MRMgr.getFieldRegionWithSuper(FR, X.second));
1127   }
1128   // C++ base object region is another kind of region that we should blast
1129   // through to look for lazy compound value. It is like a field region.
1130   else if (const CXXBaseObjectRegion *baseReg =
1131                             dyn_cast<CXXBaseObjectRegion>(R)) {
1132     const std::pair<Store, const MemRegion *> &X =
1133       GetLazyBinding(B, baseReg->getSuperRegion(), originalRegion);
1134
1135     if (X.second)
1136       return std::make_pair(X.first,
1137                      MRMgr.getCXXBaseObjectRegionWithSuper(baseReg, X.second));
1138   }
1139
1140   // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
1141   // possible for a valid lazy binding.
1142   return std::make_pair((Store) 0, (const MemRegion *) 0);
1143 }
1144
1145 SVal RegionStoreManager::getBindingForElement(Store store,
1146                                          const ElementRegion* R) {
1147   // Check if the region has a binding.
1148   RegionBindings B = GetRegionBindings(store);
1149   if (const Optional<SVal> &V = getDirectBinding(B, R))
1150     return *V;
1151
1152   const MemRegion* superR = R->getSuperRegion();
1153
1154   // Check if the region is an element region of a string literal.
1155   if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
1156     // FIXME: Handle loads from strings where the literal is treated as
1157     // an integer, e.g., *((unsigned int*)"hello")
1158     QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
1159     if (T != Ctx.getCanonicalType(R->getElementType()))
1160       return UnknownVal();
1161
1162     const StringLiteral *Str = StrR->getStringLiteral();
1163     SVal Idx = R->getIndex();
1164     if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1165       int64_t i = CI->getValue().getSExtValue();
1166       // Abort on string underrun.  This can be possible by arbitrary
1167       // clients of getBindingForElement().
1168       if (i < 0)
1169         return UndefinedVal();
1170       int64_t length = Str->getLength();
1171       // Technically, only i == length is guaranteed to be null.
1172       // However, such overflows should be caught before reaching this point;
1173       // the only time such an access would be made is if a string literal was
1174       // used to initialize a larger array.
1175       char c = (i >= length) ? '\0' : Str->getCodeUnit(i);
1176       return svalBuilder.makeIntVal(c, T);
1177     }
1178   }
1179
1180   // Check for loads from a code text region.  For such loads, just give up.
1181   if (isa<CodeTextRegion>(superR))
1182     return UnknownVal();
1183
1184   // Handle the case where we are indexing into a larger scalar object.
1185   // For example, this handles:
1186   //   int x = ...
1187   //   char *y = &x;
1188   //   return *y;
1189   // FIXME: This is a hack, and doesn't do anything really intelligent yet.
1190   const RegionRawOffset &O = R->getAsArrayOffset();
1191
1192   // If we cannot reason about the offset, return an unknown value.
1193   if (!O.getRegion())
1194     return UnknownVal();
1195
1196   if (const TypedValueRegion *baseR =
1197         dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
1198     QualType baseT = baseR->getValueType();
1199     if (baseT->isScalarType()) {
1200       QualType elemT = R->getElementType();
1201       if (elemT->isScalarType()) {
1202         if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
1203           if (const Optional<SVal> &V = getDirectBinding(B, superR)) {
1204             if (SymbolRef parentSym = V->getAsSymbol())
1205               return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1206
1207             if (V->isUnknownOrUndef())
1208               return *V;
1209             // Other cases: give up.  We are indexing into a larger object
1210             // that has some value, but we don't know how to handle that yet.
1211             return UnknownVal();
1212           }
1213         }
1214       }
1215     }
1216   }
1217   return getBindingForFieldOrElementCommon(store, R, R->getElementType(),
1218                                            superR);
1219 }
1220
1221 SVal RegionStoreManager::getBindingForField(Store store,
1222                                        const FieldRegion* R) {
1223
1224   // Check if the region has a binding.
1225   RegionBindings B = GetRegionBindings(store);
1226   if (const Optional<SVal> &V = getDirectBinding(B, R))
1227     return *V;
1228
1229   QualType Ty = R->getValueType();
1230   return getBindingForFieldOrElementCommon(store, R, Ty, R->getSuperRegion());
1231 }
1232
1233 Optional<SVal>
1234 RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B,
1235                                                      const MemRegion *superR,
1236                                                      const TypedValueRegion *R,
1237                                                      QualType Ty) {
1238
1239   if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
1240     const SVal &val = D.getValue();
1241     if (SymbolRef parentSym = val.getAsSymbol())
1242       return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1243
1244     if (val.isZeroConstant())
1245       return svalBuilder.makeZeroVal(Ty);
1246
1247     if (val.isUnknownOrUndef())
1248       return val;
1249
1250     // Lazy bindings are handled later.
1251     if (isa<nonloc::LazyCompoundVal>(val))
1252       return Optional<SVal>();
1253
1254     llvm_unreachable("Unknown default value");
1255   }
1256
1257   return Optional<SVal>();
1258 }
1259
1260 SVal RegionStoreManager::getLazyBinding(const MemRegion *lazyBindingRegion,
1261                                              Store lazyBindingStore) {
1262   if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion))
1263     return getBindingForElement(lazyBindingStore, ER);
1264
1265   return getBindingForField(lazyBindingStore,
1266                             cast<FieldRegion>(lazyBindingRegion));
1267 }
1268
1269 SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store,
1270                                                       const TypedValueRegion *R,
1271                                                       QualType Ty,
1272                                                       const MemRegion *superR) {
1273
1274   // At this point we have already checked in either getBindingForElement or
1275   // getBindingForField if 'R' has a direct binding.
1276   RegionBindings B = GetRegionBindings(store);
1277
1278   // Record whether or not we see a symbolic index.  That can completely
1279   // be out of scope of our lookup.
1280   bool hasSymbolicIndex = false;
1281
1282   while (superR) {
1283     if (const Optional<SVal> &D =
1284         getBindingForDerivedDefaultValue(B, superR, R, Ty))
1285       return *D;
1286
1287     if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) {
1288       NonLoc index = ER->getIndex();
1289       if (!index.isConstant())
1290         hasSymbolicIndex = true;
1291     }
1292
1293     // If our super region is a field or element itself, walk up the region
1294     // hierarchy to see if there is a default value installed in an ancestor.
1295     if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) {
1296       superR = SR->getSuperRegion();
1297       continue;
1298     }
1299     break;
1300   }
1301
1302   // Lazy binding?
1303   Store lazyBindingStore = NULL;
1304   const MemRegion *lazyBindingRegion = NULL;
1305   llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R);
1306
1307   if (lazyBindingRegion)
1308     return getLazyBinding(lazyBindingRegion, lazyBindingStore);
1309
1310   if (R->hasStackNonParametersStorage()) {
1311     if (isa<ElementRegion>(R)) {
1312       // Currently we don't reason specially about Clang-style vectors.  Check
1313       // if superR is a vector and if so return Unknown.
1314       if (const TypedValueRegion *typedSuperR =
1315             dyn_cast<TypedValueRegion>(superR)) {
1316         if (typedSuperR->getValueType()->isVectorType())
1317           return UnknownVal();
1318       }
1319     }
1320
1321     // FIXME: We also need to take ElementRegions with symbolic indexes into
1322     // account.  This case handles both directly accessing an ElementRegion
1323     // with a symbolic offset, but also fields within an element with
1324     // a symbolic offset.
1325     if (hasSymbolicIndex)
1326       return UnknownVal();
1327
1328     return UndefinedVal();
1329   }
1330
1331   // All other values are symbolic.
1332   return svalBuilder.getRegionValueSymbolVal(R);
1333 }
1334
1335 SVal RegionStoreManager::getBindingForObjCIvar(Store store,
1336                                                const ObjCIvarRegion* R) {
1337
1338     // Check if the region has a binding.
1339   RegionBindings B = GetRegionBindings(store);
1340
1341   if (const Optional<SVal> &V = getDirectBinding(B, R))
1342     return *V;
1343
1344   const MemRegion *superR = R->getSuperRegion();
1345
1346   // Check if the super region has a default binding.
1347   if (const Optional<SVal> &V = getDefaultBinding(B, superR)) {
1348     if (SymbolRef parentSym = V->getAsSymbol())
1349       return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1350
1351     // Other cases: give up.
1352     return UnknownVal();
1353   }
1354
1355   return getBindingForLazySymbol(R);
1356 }
1357
1358 SVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) {
1359
1360   // Check if the region has a binding.
1361   RegionBindings B = GetRegionBindings(store);
1362
1363   if (const Optional<SVal> &V = getDirectBinding(B, R))
1364     return *V;
1365
1366   // Lazily derive a value for the VarRegion.
1367   const VarDecl *VD = R->getDecl();
1368   QualType T = VD->getType();
1369   const MemSpaceRegion *MS = R->getMemorySpace();
1370
1371   if (isa<UnknownSpaceRegion>(MS) ||
1372       isa<StackArgumentsSpaceRegion>(MS))
1373     return svalBuilder.getRegionValueSymbolVal(R);
1374
1375   if (isa<GlobalsSpaceRegion>(MS)) {
1376     if (isa<NonStaticGlobalSpaceRegion>(MS)) {
1377       // Is 'VD' declared constant?  If so, retrieve the constant value.
1378       QualType CT = Ctx.getCanonicalType(T);
1379       if (CT.isConstQualified()) {
1380         const Expr *Init = VD->getInit();
1381         // Do the null check first, as we want to call 'IgnoreParenCasts'.
1382         if (Init)
1383           if (const IntegerLiteral *IL =
1384               dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) {
1385             const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL);
1386             return svalBuilder.evalCast(V, Init->getType(), IL->getType());
1387           }
1388       }
1389
1390       if (const Optional<SVal> &V
1391             = getBindingForDerivedDefaultValue(B, MS, R, CT))
1392         return V.getValue();
1393
1394       return svalBuilder.getRegionValueSymbolVal(R);
1395     }
1396
1397     if (T->isIntegerType())
1398       return svalBuilder.makeIntVal(0, T);
1399     if (T->isPointerType())
1400       return svalBuilder.makeNull();
1401
1402     return UnknownVal();
1403   }
1404
1405   return UndefinedVal();
1406 }
1407
1408 SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) {
1409   // All other values are symbolic.
1410   return svalBuilder.getRegionValueSymbolVal(R);
1411 }
1412
1413 SVal RegionStoreManager::getBindingForStruct(Store store,
1414                                         const TypedValueRegion* R) {
1415   assert(R->getValueType()->isStructureOrClassType());
1416   return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R);
1417 }
1418
1419 SVal RegionStoreManager::getBindingForArray(Store store,
1420                                        const TypedValueRegion * R) {
1421   assert(Ctx.getAsConstantArrayType(R->getValueType()));
1422   return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R);
1423 }
1424
1425 bool RegionStoreManager::includedInBindings(Store store,
1426                                             const MemRegion *region) const {
1427   RegionBindings B = GetRegionBindings(store);
1428   region = region->getBaseRegion();
1429
1430   for (RegionBindings::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
1431     const BindingKey &K = it.getKey();
1432     if (region == K.getRegion())
1433       return true;
1434     const SVal &D = it.getData();
1435     if (const MemRegion *r = D.getAsRegion())
1436       if (r == region)
1437         return true;
1438   }
1439   return false;
1440 }
1441
1442 //===----------------------------------------------------------------------===//
1443 // Binding values to regions.
1444 //===----------------------------------------------------------------------===//
1445
1446 StoreRef RegionStoreManager::Remove(Store store, Loc L) {
1447   if (isa<loc::MemRegionVal>(L))
1448     if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
1449       return StoreRef(removeBinding(GetRegionBindings(store),
1450                                     R).getRootWithoutRetain(),
1451                       *this);
1452
1453   return StoreRef(store, *this);
1454 }
1455
1456 StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) {
1457   if (isa<loc::ConcreteInt>(L))
1458     return StoreRef(store, *this);
1459
1460   // If we get here, the location should be a region.
1461   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
1462
1463   // Check if the region is a struct region.
1464   if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R))
1465     if (TR->getValueType()->isStructureOrClassType())
1466       return BindStruct(store, TR, V);
1467
1468   if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1469     if (ER->getIndex().isZeroConstant()) {
1470       if (const TypedValueRegion *superR =
1471             dyn_cast<TypedValueRegion>(ER->getSuperRegion())) {
1472         QualType superTy = superR->getValueType();
1473         // For now, just invalidate the fields of the struct/union/class.
1474         // This is for test rdar_test_7185607 in misc-ps-region-store.m.
1475         // FIXME: Precisely handle the fields of the record.
1476         if (superTy->isStructureOrClassType())
1477           return KillStruct(store, superR, UnknownVal());
1478       }
1479     }
1480   }
1481   else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1482     // Binding directly to a symbolic region should be treated as binding
1483     // to element 0.
1484     QualType T = SR->getSymbol()->getType(Ctx);
1485
1486     // FIXME: Is this the right way to handle symbols that are references?
1487     if (const PointerType *PT = T->getAs<PointerType>())
1488       T = PT->getPointeeType();
1489     else
1490       T = T->getAs<ReferenceType>()->getPointeeType();
1491
1492     R = GetElementZeroRegion(SR, T);
1493   }
1494
1495   // Perform the binding.
1496   RegionBindings B = GetRegionBindings(store);
1497   return StoreRef(addBinding(B, R, BindingKey::Direct,
1498                              V).getRootWithoutRetain(), *this);
1499 }
1500
1501 StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR,
1502                                       SVal InitVal) {
1503
1504   QualType T = VR->getDecl()->getType();
1505
1506   if (T->isArrayType())
1507     return BindArray(store, VR, InitVal);
1508   if (T->isStructureOrClassType())
1509     return BindStruct(store, VR, InitVal);
1510
1511   return Bind(store, svalBuilder.makeLoc(VR), InitVal);
1512 }
1513
1514 // FIXME: this method should be merged into Bind().
1515 StoreRef RegionStoreManager::BindCompoundLiteral(Store store,
1516                                                  const CompoundLiteralExpr *CL,
1517                                                  const LocationContext *LC,
1518                                                  SVal V) {
1519   return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)),
1520               V);
1521 }
1522
1523 StoreRef RegionStoreManager::setImplicitDefaultValue(Store store,
1524                                                      const MemRegion *R,
1525                                                      QualType T) {
1526   RegionBindings B = GetRegionBindings(store);
1527   SVal V;
1528
1529   if (Loc::isLocType(T))
1530     V = svalBuilder.makeNull();
1531   else if (T->isIntegerType())
1532     V = svalBuilder.makeZeroVal(T);
1533   else if (T->isStructureOrClassType() || T->isArrayType()) {
1534     // Set the default value to a zero constant when it is a structure
1535     // or array.  The type doesn't really matter.
1536     V = svalBuilder.makeZeroVal(Ctx.IntTy);
1537   }
1538   else {
1539     // We can't represent values of this type, but we still need to set a value
1540     // to record that the region has been initialized.
1541     // If this assertion ever fires, a new case should be added above -- we
1542     // should know how to default-initialize any value we can symbolicate.
1543     assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
1544     V = UnknownVal();
1545   }
1546
1547   return StoreRef(addBinding(B, R, BindingKey::Default,
1548                              V).getRootWithoutRetain(), *this);
1549 }
1550
1551 StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R,
1552                                        SVal Init) {
1553
1554   const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
1555   QualType ElementTy = AT->getElementType();
1556   Optional<uint64_t> Size;
1557
1558   if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
1559     Size = CAT->getSize().getZExtValue();
1560
1561   // Check if the init expr is a string literal.
1562   if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) {
1563     const StringRegion *S = cast<StringRegion>(MRV->getRegion());
1564
1565     // Treat the string as a lazy compound value.
1566     nonloc::LazyCompoundVal LCV =
1567       cast<nonloc::LazyCompoundVal>(svalBuilder.
1568                                 makeLazyCompoundVal(StoreRef(store, *this), S));
1569     return CopyLazyBindings(LCV, store, R);
1570   }
1571
1572   // Handle lazy compound values.
1573   if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
1574     return CopyLazyBindings(*LCV, store, R);
1575
1576   // Remaining case: explicit compound values.
1577
1578   if (Init.isUnknown())
1579     return setImplicitDefaultValue(store, R, ElementTy);
1580
1581   nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
1582   nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1583   uint64_t i = 0;
1584
1585   StoreRef newStore(store, *this);
1586   for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
1587     // The init list might be shorter than the array length.
1588     if (VI == VE)
1589       break;
1590
1591     const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
1592     const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
1593
1594     if (ElementTy->isStructureOrClassType())
1595       newStore = BindStruct(newStore.getStore(), ER, *VI);
1596     else if (ElementTy->isArrayType())
1597       newStore = BindArray(newStore.getStore(), ER, *VI);
1598     else
1599       newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI);
1600   }
1601
1602   // If the init list is shorter than the array length, set the
1603   // array default value.
1604   if (Size.hasValue() && i < Size.getValue())
1605     newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy);
1606
1607   return newStore;
1608 }
1609
1610 StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R,
1611                                         SVal V) {
1612
1613   if (!Features.supportsFields())
1614     return StoreRef(store, *this);
1615
1616   QualType T = R->getValueType();
1617   assert(T->isStructureOrClassType());
1618
1619   const RecordType* RT = T->getAs<RecordType>();
1620   RecordDecl *RD = RT->getDecl();
1621
1622   if (!RD->isCompleteDefinition())
1623     return StoreRef(store, *this);
1624
1625   // Handle lazy compound values.
1626   if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
1627     return CopyLazyBindings(*LCV, store, R);
1628
1629   // We may get non-CompoundVal accidentally due to imprecise cast logic or
1630   // that we are binding symbolic struct value. Kill the field values, and if
1631   // the value is symbolic go and bind it as a "default" binding.
1632   if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) {
1633     SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal();
1634     return KillStruct(store, R, SV);
1635   }
1636
1637   nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
1638   nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1639
1640   RecordDecl::field_iterator FI, FE;
1641   StoreRef newStore(store, *this);
1642
1643   for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {
1644
1645     if (VI == VE)
1646       break;
1647
1648     // Skip any unnamed bitfields to stay in sync with the initializers.
1649     if ((*FI)->isUnnamedBitfield())
1650       continue;
1651
1652     QualType FTy = (*FI)->getType();
1653     const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1654
1655     if (FTy->isArrayType())
1656       newStore = BindArray(newStore.getStore(), FR, *VI);
1657     else if (FTy->isStructureOrClassType())
1658       newStore = BindStruct(newStore.getStore(), FR, *VI);
1659     else
1660       newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI);
1661     ++VI;
1662   }
1663
1664   // There may be fewer values in the initialize list than the fields of struct.
1665   if (FI != FE) {
1666     RegionBindings B = GetRegionBindings(newStore.getStore());
1667     B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false));
1668     newStore = StoreRef(B.getRootWithoutRetain(), *this);
1669   }
1670
1671   return newStore;
1672 }
1673
1674 StoreRef RegionStoreManager::KillStruct(Store store, const TypedRegion* R,
1675                                      SVal DefaultVal) {
1676   BindingKey key = BindingKey::Make(R, BindingKey::Default);
1677
1678   // The BindingKey may be "invalid" if we cannot handle the region binding
1679   // explicitly.  One example is something like array[index], where index
1680   // is a symbolic value.  In such cases, we want to invalidate the entire
1681   // array, as the index assignment could have been to any element.  In
1682   // the case of nested symbolic indices, we need to march up the region
1683   // hierarchy untile we reach a region whose binding we can reason about.
1684   const SubRegion *subReg = R;
1685
1686   while (!key.isValid()) {
1687     if (const SubRegion *tmp = dyn_cast<SubRegion>(subReg->getSuperRegion())) {
1688       subReg = tmp;
1689       key = BindingKey::Make(tmp, BindingKey::Default);
1690     }
1691     else
1692       break;
1693   }
1694
1695   // Remove the old bindings, using 'subReg' as the root of all regions
1696   // we will invalidate.
1697   RegionBindings B = GetRegionBindings(store);
1698   OwningPtr<RegionStoreSubRegionMap>
1699     SubRegions(getRegionStoreSubRegionMap(store));
1700   RemoveSubRegionBindings(B, subReg, *SubRegions);
1701
1702   // Set the default value of the struct region to "unknown".
1703   if (!key.isValid())
1704     return StoreRef(B.getRootWithoutRetain(), *this);
1705
1706   return StoreRef(addBinding(B, key, DefaultVal).getRootWithoutRetain(), *this);
1707 }
1708
1709 StoreRef RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1710                                               Store store,
1711                                               const TypedRegion *R) {
1712
1713   // Nuke the old bindings stemming from R.
1714   RegionBindings B = GetRegionBindings(store);
1715
1716   OwningPtr<RegionStoreSubRegionMap>
1717     SubRegions(getRegionStoreSubRegionMap(store));
1718
1719   // B and DVM are updated after the call to RemoveSubRegionBindings.
1720   RemoveSubRegionBindings(B, R, *SubRegions.get());
1721
1722   // Now copy the bindings.  This amounts to just binding 'V' to 'R'.  This
1723   // results in a zero-copy algorithm.
1724   return StoreRef(addBinding(B, R, BindingKey::Default,
1725                              V).getRootWithoutRetain(), *this);
1726 }
1727
1728 //===----------------------------------------------------------------------===//
1729 // "Raw" retrievals and bindings.
1730 //===----------------------------------------------------------------------===//
1731
1732
1733 RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K,
1734                                               SVal V) {
1735   if (!K.isValid())
1736     return B;
1737   return RBFactory.add(B, K, V);
1738 }
1739
1740 RegionBindings RegionStoreManager::addBinding(RegionBindings B,
1741                                               const MemRegion *R,
1742                                               BindingKey::Kind k, SVal V) {
1743   return addBinding(B, BindingKey::Make(R, k), V);
1744 }
1745
1746 const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) {
1747   if (!K.isValid())
1748     return NULL;
1749   return B.lookup(K);
1750 }
1751
1752 const SVal *RegionStoreManager::lookup(RegionBindings B,
1753                                        const MemRegion *R,
1754                                        BindingKey::Kind k) {
1755   return lookup(B, BindingKey::Make(R, k));
1756 }
1757
1758 RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1759                                                  BindingKey K) {
1760   if (!K.isValid())
1761     return B;
1762   return RBFactory.remove(B, K);
1763 }
1764
1765 RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1766                                                  const MemRegion *R,
1767                                                 BindingKey::Kind k){
1768   return removeBinding(B, BindingKey::Make(R, k));
1769 }
1770
1771 //===----------------------------------------------------------------------===//
1772 // State pruning.
1773 //===----------------------------------------------------------------------===//
1774
1775 namespace {
1776 class removeDeadBindingsWorker :
1777   public ClusterAnalysis<removeDeadBindingsWorker> {
1778   SmallVector<const SymbolicRegion*, 12> Postponed;
1779   SymbolReaper &SymReaper;
1780   const StackFrameContext *CurrentLCtx;
1781
1782 public:
1783   removeDeadBindingsWorker(RegionStoreManager &rm,
1784                            ProgramStateManager &stateMgr,
1785                            RegionBindings b, SymbolReaper &symReaper,
1786                            const StackFrameContext *LCtx)
1787     : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b,
1788                                                 /* includeGlobals = */ false),
1789       SymReaper(symReaper), CurrentLCtx(LCtx) {}
1790
1791   // Called by ClusterAnalysis.
1792   void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C);
1793   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
1794
1795   void VisitBindingKey(BindingKey K);
1796   bool UpdatePostponed();
1797   void VisitBinding(SVal V);
1798 };
1799 }
1800
1801 void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
1802                                                    RegionCluster &C) {
1803
1804   if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
1805     if (SymReaper.isLive(VR))
1806       AddToWorkList(baseR, C);
1807
1808     return;
1809   }
1810
1811   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
1812     if (SymReaper.isLive(SR->getSymbol()))
1813       AddToWorkList(SR, C);
1814     else
1815       Postponed.push_back(SR);
1816
1817     return;
1818   }
1819
1820   if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
1821     AddToWorkList(baseR, C);
1822     return;
1823   }
1824
1825   // CXXThisRegion in the current or parent location context is live.
1826   if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
1827     const StackArgumentsSpaceRegion *StackReg =
1828       cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
1829     const StackFrameContext *RegCtx = StackReg->getStackFrame();
1830     if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))
1831       AddToWorkList(TR, C);
1832   }
1833 }
1834
1835 void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
1836                                             BindingKey *I, BindingKey *E) {
1837   for ( ; I != E; ++I)
1838     VisitBindingKey(*I);
1839 }
1840
1841 void removeDeadBindingsWorker::VisitBinding(SVal V) {
1842   // Is it a LazyCompoundVal?  All referenced regions are live as well.
1843   if (const nonloc::LazyCompoundVal *LCS =
1844       dyn_cast<nonloc::LazyCompoundVal>(&V)) {
1845
1846     const MemRegion *LazyR = LCS->getRegion();
1847     RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
1848     for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
1849       const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
1850       if (baseR && baseR->isSubRegionOf(LazyR))
1851         VisitBinding(RI.getData());
1852     }
1853     return;
1854   }
1855
1856   // If V is a region, then add it to the worklist.
1857   if (const MemRegion *R = V.getAsRegion())
1858     AddToWorkList(R);
1859
1860   // Update the set of live symbols.
1861   for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end();
1862        SI!=SE; ++SI)
1863     SymReaper.markLive(*SI);
1864 }
1865
1866 void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) {
1867   const MemRegion *R = K.getRegion();
1868
1869   // Mark this region "live" by adding it to the worklist.  This will cause
1870   // use to visit all regions in the cluster (if we haven't visited them
1871   // already).
1872   if (AddToWorkList(R)) {
1873     // Mark the symbol for any live SymbolicRegion as "live".  This means we
1874     // should continue to track that symbol.
1875     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
1876       SymReaper.markLive(SymR->getSymbol());
1877
1878     // For BlockDataRegions, enqueue the VarRegions for variables marked
1879     // with __block (passed-by-reference).
1880     // via BlockDeclRefExprs.
1881     if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
1882       for (BlockDataRegion::referenced_vars_iterator
1883            RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
1884            RI != RE; ++RI) {
1885         if ((*RI)->getDecl()->getAttr<BlocksAttr>())
1886           AddToWorkList(*RI);
1887       }
1888
1889       // No possible data bindings on a BlockDataRegion.
1890       return;
1891     }
1892   }
1893
1894   // Visit the data binding for K.
1895   if (const SVal *V = RM.lookup(B, K))
1896     VisitBinding(*V);
1897 }
1898
1899 bool removeDeadBindingsWorker::UpdatePostponed() {
1900   // See if any postponed SymbolicRegions are actually live now, after
1901   // having done a scan.
1902   bool changed = false;
1903
1904   for (SmallVectorImpl<const SymbolicRegion*>::iterator
1905         I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) {
1906     if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) {
1907       if (SymReaper.isLive(SR->getSymbol())) {
1908         changed |= AddToWorkList(SR);
1909         *I = NULL;
1910       }
1911     }
1912   }
1913
1914   return changed;
1915 }
1916
1917 StoreRef RegionStoreManager::removeDeadBindings(Store store,
1918                                                 const StackFrameContext *LCtx,
1919                                                 SymbolReaper& SymReaper) {
1920   RegionBindings B = GetRegionBindings(store);
1921   removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
1922   W.GenerateClusters();
1923
1924   // Enqueue the region roots onto the worklist.
1925   for (SymbolReaper::region_iterator I = SymReaper.region_begin(),
1926        E = SymReaper.region_end(); I != E; ++I) {
1927     W.AddToWorkList(*I);
1928   }
1929
1930   do W.RunWorkList(); while (W.UpdatePostponed());
1931
1932   // We have now scanned the store, marking reachable regions and symbols
1933   // as live.  We now remove all the regions that are dead from the store
1934   // as well as update DSymbols with the set symbols that are now dead.
1935   for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1936     const BindingKey &K = I.getKey();
1937
1938     // If the cluster has been visited, we know the region has been marked.
1939     if (W.isVisited(K.getRegion()))
1940       continue;
1941
1942     // Remove the dead entry.
1943     B = removeBinding(B, K);
1944
1945     // Mark all non-live symbols that this binding references as dead.
1946     if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion()))
1947       SymReaper.maybeDead(SymR->getSymbol());
1948
1949     SVal X = I.getData();
1950     SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1951     for (; SI != SE; ++SI)
1952       SymReaper.maybeDead(*SI);
1953   }
1954
1955   return StoreRef(B.getRootWithoutRetain(), *this);
1956 }
1957
1958
1959 StoreRef RegionStoreManager::enterStackFrame(ProgramStateRef state,
1960                                              const LocationContext *callerCtx,
1961                                              const StackFrameContext *calleeCtx)
1962 {
1963   FunctionDecl const *FD = cast<FunctionDecl>(calleeCtx->getDecl());
1964   FunctionDecl::param_const_iterator PI = FD->param_begin(),
1965                                      PE = FD->param_end();
1966   StoreRef store = StoreRef(state->getStore(), *this);
1967
1968   if (CallExpr const *CE = dyn_cast<CallExpr>(calleeCtx->getCallSite())) {
1969     CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1970
1971     // Copy the arg expression value to the arg variables.  We check that
1972     // PI != PE because the actual number of arguments may be different than
1973     // the function declaration.
1974     for (; AI != AE && PI != PE; ++AI, ++PI) {
1975       SVal ArgVal = state->getSVal(*AI, callerCtx);
1976       store = Bind(store.getStore(),
1977                    svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)),
1978                    ArgVal);
1979     }
1980   } else if (const CXXConstructExpr *CE =
1981                dyn_cast<CXXConstructExpr>(calleeCtx->getCallSite())) {
1982     CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(),
1983       AE = CE->arg_end();
1984
1985     // Copy the arg expression value to the arg variables.
1986     for (; AI != AE; ++AI, ++PI) {
1987       SVal ArgVal = state->getSVal(*AI, callerCtx);
1988       store = Bind(store.getStore(),
1989                    svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)),
1990                    ArgVal);
1991     }
1992   } else
1993     assert(isa<CXXDestructorDecl>(calleeCtx->getDecl()));
1994
1995   return store;
1996 }
1997
1998 //===----------------------------------------------------------------------===//
1999 // Utility methods.
2000 //===----------------------------------------------------------------------===//
2001
2002 void RegionStoreManager::print(Store store, raw_ostream &OS,
2003                                const char* nl, const char *sep) {
2004   RegionBindings B = GetRegionBindings(store);
2005   OS << "Store (direct and default bindings):" << nl;
2006
2007   for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
2008     OS << ' ' << I.getKey() << " : " << I.getData() << nl;
2009 }