lib/Checker/BasicStore.cpp

   1 //== BasicStore.cpp - Basic map from Locations to Values --------*- 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 defined the BasicStore and BasicStoreManager classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/DeclCXX.h"
  15 #include "clang/AST/ExprObjC.h"
  16 #include "clang/Analysis/Analyses/LiveVariables.h"
  17 #include "clang/Analysis/AnalysisContext.h"
  18 #include "clang/GR/PathSensitive/GRState.h"
  19 #include "llvm/ADT/ImmutableMap.h"
  20
  21 using namespace clang;
  22
  23 typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
  24
  25 namespace {
  26
  27 class BasicStoreSubRegionMap : public SubRegionMap {
  28 public:
  29   BasicStoreSubRegionMap() {}
  30
  31   bool iterSubRegions(const MemRegion* R, Visitor& V) const {
  32     return true; // Do nothing.  No subregions.
  33   }
  34 };
  35
  36 class BasicStoreManager : public StoreManager {
  37   BindingsTy::Factory VBFactory;
  38 public:
  39   BasicStoreManager(GRStateManager& mgr)
  40     : StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
  41
  42   ~BasicStoreManager() {}
  43
  44   SubRegionMap *getSubRegionMap(Store store) {
  45     return new BasicStoreSubRegionMap();
  46   }
  47
  48   SVal Retrieve(Store store, Loc loc, QualType T = QualType());
  49
  50   Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
  51                          unsigned Count, InvalidatedSymbols *IS);
  52
  53   Store InvalidateRegions(Store store, const MemRegion * const *Begin,
  54                           const MemRegion * const *End, const Expr *E,
  55                           unsigned Count, InvalidatedSymbols *IS,
  56                           bool invalidateGlobals, InvalidatedRegions *Regions);
  57
  58   Store scanForIvars(Stmt *B, const Decl* SelfDecl,
  59                      const MemRegion *SelfRegion, Store St);
  60
  61   Store Bind(Store St, Loc loc, SVal V);
  62   Store Remove(Store St, Loc loc);
  63   Store getInitialStore(const LocationContext *InitLoc);
  64
  65   Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
  66                             const LocationContext*, SVal val) {
  67     return store;
  68   }
  69
  70   /// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit
  71   ///  conversions between arrays and pointers.
  72   SVal ArrayToPointer(Loc Array) { return Array; }
  73
  74   /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
  75   ///  It updatees the GRState object in place with the values removed.
  76   Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
  77                            SymbolReaper& SymReaper,
  78                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
  79
  80   void iterBindings(Store store, BindingsHandler& f);
  81
  82   Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
  83     return BindDeclInternal(store, VR, &InitVal);
  84   }
  85
  86   Store BindDeclWithNoInit(Store store, const VarRegion *VR) {
  87     return BindDeclInternal(store, VR, 0);
  88   }
  89
  90   Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
  91
  92   static inline BindingsTy GetBindings(Store store) {
  93     return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
  94   }
  95
  96   void print(Store store, llvm::raw_ostream& Out, const char* nl,
  97              const char *sep);
  98
  99 private:
 100   SVal LazyRetrieve(Store store, const TypedRegion *R);
 101 };
 102
 103 } // end anonymous namespace
 104
 105
 106 StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) {
 107   return new BasicStoreManager(StMgr);
 108 }
 109
 110 static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
 111   bool foundPointer = false;
 112   while (1) {
 113     const PointerType *PT = T->getAs<PointerType>();
 114     if (!PT) {
 115       if (!foundPointer)
 116         return false;
 117
 118       // intptr_t* or intptr_t**, etc?
 119       if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
 120         return true;
 121
 122       QualType X = C.getCanonicalType(T).getUnqualifiedType();
 123       return X == C.VoidTy;
 124     }
 125
 126     foundPointer = true;
 127     T = PT->getPointeeType();
 128   }
 129 }
 130
 131 SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
 132   const VarRegion *VR = dyn_cast<VarRegion>(R);
 133   if (!VR)
 134     return UnknownVal();
 135
 136   const VarDecl *VD = VR->getDecl();
 137   QualType T = VD->getType();
 138
 139   // Only handle simple types that we can symbolicate.
 140   if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
 141     return UnknownVal();
 142
 143   // Globals and parameters start with symbolic values.
 144   // Local variables initially are undefined.
 145
 146   // Non-static globals may have had their values reset by InvalidateRegions.
 147   const MemSpaceRegion *MS = VR->getMemorySpace();
 148   if (isa<NonStaticGlobalSpaceRegion>(MS)) {
 149     BindingsTy B = GetBindings(store);
 150     // FIXME: Copy-and-pasted from RegionStore.cpp.
 151     if (BindingsTy::data_type *Val = B.lookup(MS)) {
 152       if (SymbolRef parentSym = Val->getAsSymbol())
 153         return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
 154
 155       if (Val->isZeroConstant())
 156         return svalBuilder.makeZeroVal(T);
 157
 158       if (Val->isUnknownOrUndef())
 159         return *Val;
 160
 161       assert(0 && "Unknown default value.");
 162     }
 163   }
 164
 165   if (VR->hasGlobalsOrParametersStorage() ||
 166       isa<UnknownSpaceRegion>(VR->getMemorySpace()))
 167     return svalBuilder.getRegionValueSymbolVal(R);
 168
 169   return UndefinedVal();
 170 }
 171
 172 SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
 173   if (isa<UnknownVal>(loc))
 174     return UnknownVal();
 175
 176   assert(!isa<UndefinedVal>(loc));
 177
 178   switch (loc.getSubKind()) {
 179
 180     case loc::MemRegionKind: {
 181       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 182
 183       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
 184           isa<CXXThisRegion>(R)))
 185         return UnknownVal();
 186
 187       BindingsTy B = GetBindings(store);
 188       BindingsTy::data_type *Val = B.lookup(R);
 189       const TypedRegion *TR = cast<TypedRegion>(R);
 190
 191       if (Val)
 192         return CastRetrievedVal(*Val, TR, T);
 193
 194       SVal V = LazyRetrieve(store, TR);
 195       return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
 196     }
 197
 198     case loc::ConcreteIntKind:
 199       // Support direct accesses to memory.  It's up to individual checkers
 200       // to flag an error.
 201       return UnknownVal();
 202
 203     default:
 204       assert (false && "Invalid Loc.");
 205       break;
 206   }
 207
 208   return UnknownVal();
 209 }
 210
 211 Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
 212   if (isa<loc::ConcreteInt>(loc))
 213     return store;
 214
 215   const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 216
 217   // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
 218   //  that is used to derive other symbols.
 219   if (isa<NonStaticGlobalSpaceRegion>(R)) {
 220     BindingsTy B = GetBindings(store);
 221     return VBFactory.add(B, R, V).getRoot();
 222   }
 223
 224   // Special case: handle store of pointer values (Loc) to pointers via
 225   // a cast to intXX_t*, void*, etc.  This is needed to handle
 226   // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
 227   if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
 228     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 229       // FIXME: Should check for index 0.
 230       QualType T = ER->getLocationType();
 231
 232       if (isHigherOrderRawPtr(T, Ctx))
 233         R = ER->getSuperRegion();
 234     }
 235
 236   if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
 237     return store;
 238
 239   const TypedRegion *TyR = cast<TypedRegion>(R);
 240
 241   // Do not bind to arrays.  We need to explicitly check for this so that
 242   // we do not encounter any weirdness of trying to load/store from arrays.
 243   if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
 244     return store;
 245
 246   if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
 247     // Only convert 'V' to a location iff the underlying region type
 248     // is a location as well.
 249     // FIXME: We are allowing a store of an arbitrary location to
 250     // a pointer.  We may wish to flag a type error here if the types
 251     // are incompatible.  This may also cause lots of breakage
 252     // elsewhere. Food for thought.
 253     if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
 254       V = X->getLoc();
 255   }
 256
 257   BindingsTy B = GetBindings(store);
 258   return V.isUnknown()
 259     ? VBFactory.remove(B, R).getRoot()
 260     : VBFactory.add(B, R, V).getRoot();
 261 }
 262
 263 Store BasicStoreManager::Remove(Store store, Loc loc) {
 264   switch (loc.getSubKind()) {
 265     case loc::MemRegionKind: {
 266       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 267
 268       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
 269           isa<CXXThisRegion>(R)))
 270         return store;
 271
 272       return VBFactory.remove(GetBindings(store), R).getRoot();
 273     }
 274     default:
 275       assert ("Remove for given Loc type not yet implemented.");
 276       return store;
 277   }
 278 }
 279
 280 Store BasicStoreManager::RemoveDeadBindings(Store store,
 281                                             const StackFrameContext *LCtx,
 282                                             SymbolReaper& SymReaper,
 283                            llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
 284 {
 285   BindingsTy B = GetBindings(store);
 286   typedef SVal::symbol_iterator symbol_iterator;
 287
 288   // Iterate over the variable bindings.
 289   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
 290     if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
 291       if (SymReaper.isLive(VR))
 292         RegionRoots.push_back(VR);
 293       else
 294         continue;
 295     }
 296     else if (isa<ObjCIvarRegion>(I.getKey()) ||
 297              isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
 298              isa<CXXThisRegion>(I.getKey()))
 299       RegionRoots.push_back(I.getKey());
 300     else
 301       continue;
 302
 303     // Mark the bindings in the data as live.
 304     SVal X = I.getData();
 305     for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
 306       SymReaper.markLive(*SI);
 307   }
 308
 309   // Scan for live variables and live symbols.
 310   llvm::SmallPtrSet<const MemRegion*, 10> Marked;
 311
 312   while (!RegionRoots.empty()) {
 313     const MemRegion* MR = RegionRoots.back();
 314     RegionRoots.pop_back();
 315
 316     while (MR) {
 317       if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
 318         SymReaper.markLive(SymR->getSymbol());
 319         break;
 320       }
 321       else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
 322                isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
 323         if (Marked.count(MR))
 324           break;
 325
 326         Marked.insert(MR);
 327         SVal X = Retrieve(store, loc::MemRegionVal(MR));
 328
 329         // FIXME: We need to handle symbols nested in region definitions.
 330         for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
 331           SymReaper.markLive(*SI);
 332
 333         if (!isa<loc::MemRegionVal>(X))
 334           break;
 335
 336         const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
 337         RegionRoots.push_back(LVD.getRegion());
 338         break;
 339       }
 340       else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
 341         MR = R->getSuperRegion();
 342       else
 343         break;
 344     }
 345   }
 346
 347   // Remove dead variable bindings.
 348   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
 349     const MemRegion* R = I.getKey();
 350
 351     if (!Marked.count(R)) {
 352       store = Remove(store, svalBuilder.makeLoc(R));
 353       SVal X = I.getData();
 354
 355       for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
 356         SymReaper.maybeDead(*SI);
 357     }
 358   }
 359
 360   return store;
 361 }
 362
 363 Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
 364                                       const MemRegion *SelfRegion, Store St) {
 365   for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
 366        CI != CE; ++CI) {
 367
 368     if (!*CI)
 369       continue;
 370
 371     // Check if the statement is an ivar reference.  We only
 372     // care about self.ivar.
 373     if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
 374       const Expr *Base = IV->getBase()->IgnoreParenCasts();
 375       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
 376         if (DR->getDecl() == SelfDecl) {
 377           const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
 378                                                          SelfRegion);
 379           SVal X = svalBuilder.getRegionValueSymbolVal(IVR);
 380           St = Bind(St, svalBuilder.makeLoc(IVR), X);
 381         }
 382       }
 383     }
 384     else
 385       St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
 386   }
 387
 388   return St;
 389 }
 390
 391 Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
 392   // The LiveVariables information already has a compilation of all VarDecls
 393   // used in the function.  Iterate through this set, and "symbolicate"
 394   // any VarDecl whose value originally comes from outside the function.
 395   typedef LiveVariables::AnalysisDataTy LVDataTy;
 396   LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
 397   Store St = VBFactory.getEmptyMap().getRoot();
 398
 399   for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
 400     const NamedDecl* ND = I->first;
 401
 402     // Handle implicit parameters.
 403     if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
 404       const Decl& CD = *InitLoc->getDecl();
 405       if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
 406         if (MD->getSelfDecl() == PD) {
 407           // FIXME: Add type constraints (when they become available) to
 408           // SelfRegion?  (i.e., it implements MD->getClassInterface()).
 409           const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
 410           const MemRegion *SelfRegion =
 411             svalBuilder.getRegionValueSymbolVal(VR).getAsRegion();
 412           assert(SelfRegion);
 413           St = Bind(St, svalBuilder.makeLoc(VR), loc::MemRegionVal(SelfRegion));
 414           // Scan the method for ivar references.  While this requires an
 415           // entire AST scan, the cost should not be high in practice.
 416           St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
 417         }
 418       }
 419     }
 420   }
 421
 422   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
 423     // For C++ methods add symbolic region for 'this' in initial stack frame.
 424     QualType ThisT = MD->getThisType(StateMgr.getContext());
 425     MemRegionManager &RegMgr = svalBuilder.getRegionManager();
 426     const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
 427     SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR);
 428     St = Bind(St, svalBuilder.makeLoc(ThisR), ThisV);
 429   }
 430
 431   return St;
 432 }
 433
 434 Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
 435                                           SVal* InitVal) {
 436
 437   BasicValueFactory& BasicVals = StateMgr.getBasicVals();
 438   const VarDecl *VD = VR->getDecl();
 439
 440   // BasicStore does not model arrays and structs.
 441   if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
 442     return store;
 443
 444   if (VD->hasGlobalStorage()) {
 445     // Handle variables with global storage: extern, static, PrivateExtern.
 446
 447     // FIXME:: static variables may have an initializer, but the second time a
 448     // function is called those values may not be current. Currently, a function
 449     // will not be called more than once.
 450
 451     // Static global variables should not be visited here.
 452     assert(!(VD->getStorageClass() == SC_Static &&
 453              VD->isFileVarDecl()));
 454
 455     // Process static variables.
 456     if (VD->getStorageClass() == SC_Static) {
 457       // C99: 6.7.8 Initialization
 458       //  If an object that has static storage duration is not initialized
 459       //  explicitly, then:
 460       //   —if it has pointer type, it is initialized to a null pointer;
 461       //   —if it has arithmetic type, it is initialized to (positive or
 462       //     unsigned) zero;
 463       if (!InitVal) {
 464         QualType T = VD->getType();
 465         if (Loc::IsLocType(T))
 466           store = Bind(store, loc::MemRegionVal(VR),
 467                        loc::ConcreteInt(BasicVals.getValue(0, T)));
 468         else if (T->isIntegerType() && T->isScalarType())
 469           store = Bind(store, loc::MemRegionVal(VR),
 470                        nonloc::ConcreteInt(BasicVals.getValue(0, T)));
 471       } else {
 472         store = Bind(store, loc::MemRegionVal(VR), *InitVal);
 473       }
 474     }
 475   } else {
 476     // Process local scalar variables.
 477     QualType T = VD->getType();
 478     // BasicStore only supports scalars.
 479     if ((T->isScalarType() || T->isReferenceType()) &&
 480         svalBuilder.getSymbolManager().canSymbolicate(T)) {
 481       SVal V = InitVal ? *InitVal : UndefinedVal();
 482       store = Bind(store, loc::MemRegionVal(VR), V);
 483     }
 484   }
 485
 486   return store;
 487 }
 488
 489 void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
 490                               const char* nl, const char *sep) {
 491
 492   BindingsTy B = GetBindings(store);
 493   Out << "Variables:" << nl;
 494
 495   bool isFirst = true;
 496
 497   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
 498     if (isFirst)
 499       isFirst = false;
 500     else
 501       Out << nl;
 502
 503     Out << ' ' << I.getKey() << " : " << I.getData();
 504   }
 505 }
 506
 507
 508 void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
 509   BindingsTy B = GetBindings(store);
 510
 511   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
 512     if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
 513       return;
 514
 515 }
 516
 517 StoreManager::BindingsHandler::~BindingsHandler() {}
 518
 519 //===----------------------------------------------------------------------===//
 520 // Binding invalidation.
 521 //===----------------------------------------------------------------------===//
 522
 523
 524 Store BasicStoreManager::InvalidateRegions(Store store,
 525                                            const MemRegion * const *I,
 526                                            const MemRegion * const *End,
 527                                            const Expr *E, unsigned Count,
 528                                            InvalidatedSymbols *IS,
 529                                            bool invalidateGlobals,
 530                                            InvalidatedRegions *Regions) {
 531   if (invalidateGlobals) {
 532     BindingsTy B = GetBindings(store);
 533     for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
 534       const MemRegion *R = I.getKey();
 535       if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 536         store = InvalidateRegion(store, R, E, Count, IS);
 537     }
 538   }
 539
 540   for ( ; I != End ; ++I) {
 541     const MemRegion *R = *I;
 542     // Don't invalidate globals twice.
 543     if (invalidateGlobals) {
 544       if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 545         continue;
 546     }
 547     store = InvalidateRegion(store, *I, E, Count, IS);
 548     if (Regions)
 549       Regions->push_back(R);
 550   }
 551
 552   // FIXME: This is copy-and-paste from RegionStore.cpp.
 553   if (invalidateGlobals) {
 554     // Bind the non-static globals memory space to a new symbol that we will
 555     // use to derive the bindings for all non-static globals.
 556     const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
 557     SVal V =
 558       svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
 559                                   /* symbol type, doesn't matter */ Ctx.IntTy,
 560                                   Count);
 561
 562     store = Bind(store, loc::MemRegionVal(GS), V);
 563     if (Regions)
 564       Regions->push_back(GS);
 565   }
 566
 567   return store;
 568 }
 569
 570
 571 Store BasicStoreManager::InvalidateRegion(Store store,
 572                                           const MemRegion *R,
 573                                           const Expr *E,
 574                                           unsigned Count,
 575                                           InvalidatedSymbols *IS) {
 576   R = R->StripCasts();
 577
 578   if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
 579       return store;
 580
 581   if (IS) {
 582     BindingsTy B = GetBindings(store);
 583     if (BindingsTy::data_type *Val = B.lookup(R)) {
 584       if (SymbolRef Sym = Val->getAsSymbol())
 585         IS->insert(Sym);
 586     }
 587   }
 588
 589   QualType T = cast<TypedRegion>(R)->getValueType();
 590   SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count);
 591   return Bind(store, loc::MemRegionVal(R), V);
 592 }
 593