1 //== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines a basic region store model. In this model, we do have field 10 // sensitivity. But we assume nothing about the heap shape. So recursive data 11 // structures are largely ignored. Basically we do 1-limiting analysis. 12 // Parameter pointers are assumed with no aliasing. Pointee objects of 13 // parameters are created lazily. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "clang/AST/Attr.h" 18 #include "clang/AST/CharUnits.h" 19 #include "clang/ASTMatchers/ASTMatchFinder.h" 20 #include "clang/Analysis/Analyses/LiveVariables.h" 21 #include "clang/Analysis/AnalysisDeclContext.h" 22 #include "clang/Basic/JsonSupport.h" 23 #include "clang/Basic/TargetInfo.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 30 #include "llvm/ADT/ImmutableMap.h" 31 #include "llvm/ADT/Optional.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include <utility> 34 35 using namespace clang; 36 using namespace ento; 37 38 //===----------------------------------------------------------------------===// 39 // Representation of binding keys. 40 //===----------------------------------------------------------------------===// 41 42 namespace { 43 class BindingKey { 44 public: 45 enum Kind { Default = 0x0, Direct = 0x1 }; 46 private: 47 enum { Symbolic = 0x2 }; 48 49 llvm::PointerIntPair<const MemRegion *, 2> P; 50 uint64_t Data; 51 52 /// Create a key for a binding to region \p r, which has a symbolic offset 53 /// from region \p Base. 54 explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) 55 : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { 56 assert(r && Base && "Must have known regions."); 57 assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); 58 } 59 60 /// Create a key for a binding at \p offset from base region \p r. 61 explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 62 : P(r, k), Data(offset) { 63 assert(r && "Must have known regions."); 64 assert(getOffset() == offset && "Failed to store offset"); 65 assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r) || 66 isa <CXXDerivedObjectRegion>(r)) && 67 "Not a base"); 68 } 69 public: 70 71 bool isDirect() const { return P.getInt() & Direct; } 72 bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } 73 74 const MemRegion *getRegion() const { return P.getPointer(); } 75 uint64_t getOffset() const { 76 assert(!hasSymbolicOffset()); 77 return Data; 78 } 79 80 const SubRegion *getConcreteOffsetRegion() const { 81 assert(hasSymbolicOffset()); 82 return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); 83 } 84 85 const MemRegion *getBaseRegion() const { 86 if (hasSymbolicOffset()) 87 return getConcreteOffsetRegion()->getBaseRegion(); 88 return getRegion()->getBaseRegion(); 89 } 90 91 void Profile(llvm::FoldingSetNodeID& ID) const { 92 ID.AddPointer(P.getOpaqueValue()); 93 ID.AddInteger(Data); 94 } 95 96 static BindingKey Make(const MemRegion *R, Kind k); 97 98 bool operator<(const BindingKey &X) const { 99 if (P.getOpaqueValue() < X.P.getOpaqueValue()) 100 return true; 101 if (P.getOpaqueValue() > X.P.getOpaqueValue()) 102 return false; 103 return Data < X.Data; 104 } 105 106 bool operator==(const BindingKey &X) const { 107 return P.getOpaqueValue() == X.P.getOpaqueValue() && 108 Data == X.Data; 109 } 110 111 LLVM_DUMP_METHOD void dump() const; 112 }; 113 } // end anonymous namespace 114 115 BindingKey BindingKey::Make(const MemRegion *R, Kind k) { 116 const RegionOffset &RO = R->getAsOffset(); 117 if (RO.hasSymbolicOffset()) 118 return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); 119 120 return BindingKey(RO.getRegion(), RO.getOffset(), k); 121 } 122 123 namespace llvm { 124 static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) { 125 Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default") 126 << "\", \"offset\": "; 127 128 if (!K.hasSymbolicOffset()) 129 Out << K.getOffset(); 130 else 131 Out << "null"; 132 133 return Out; 134 } 135 136 } // namespace llvm 137 138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 139 void BindingKey::dump() const { llvm::errs() << *this; } 140 #endif 141 142 //===----------------------------------------------------------------------===// 143 // Actual Store type. 144 //===----------------------------------------------------------------------===// 145 146 typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; 147 typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; 148 typedef std::pair<BindingKey, SVal> BindingPair; 149 150 typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> 151 RegionBindings; 152 153 namespace { 154 class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, 155 ClusterBindings> { 156 ClusterBindings::Factory *CBFactory; 157 158 // This flag indicates whether the current bindings are within the analysis 159 // that has started from main(). It affects how we perform loads from 160 // global variables that have initializers: if we have observed the 161 // program execution from the start and we know that these variables 162 // have not been overwritten yet, we can be sure that their initializers 163 // are still relevant. This flag never gets changed when the bindings are 164 // updated, so it could potentially be moved into RegionStoreManager 165 // (as if it's the same bindings but a different loading procedure) 166 // however that would have made the manager needlessly stateful. 167 bool IsMainAnalysis; 168 169 public: 170 typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> 171 ParentTy; 172 173 RegionBindingsRef(ClusterBindings::Factory &CBFactory, 174 const RegionBindings::TreeTy *T, 175 RegionBindings::TreeTy::Factory *F, 176 bool IsMainAnalysis) 177 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), 178 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} 179 180 RegionBindingsRef(const ParentTy &P, 181 ClusterBindings::Factory &CBFactory, 182 bool IsMainAnalysis) 183 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), 184 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} 185 186 RegionBindingsRef add(key_type_ref K, data_type_ref D) const { 187 return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D), 188 *CBFactory, IsMainAnalysis); 189 } 190 191 RegionBindingsRef remove(key_type_ref K) const { 192 return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K), 193 *CBFactory, IsMainAnalysis); 194 } 195 196 RegionBindingsRef addBinding(BindingKey K, SVal V) const; 197 198 RegionBindingsRef addBinding(const MemRegion *R, 199 BindingKey::Kind k, SVal V) const; 200 201 const SVal *lookup(BindingKey K) const; 202 const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; 203 using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup; 204 205 RegionBindingsRef removeBinding(BindingKey K); 206 207 RegionBindingsRef removeBinding(const MemRegion *R, 208 BindingKey::Kind k); 209 210 RegionBindingsRef removeBinding(const MemRegion *R) { 211 return removeBinding(R, BindingKey::Direct). 212 removeBinding(R, BindingKey::Default); 213 } 214 215 Optional<SVal> getDirectBinding(const MemRegion *R) const; 216 217 /// getDefaultBinding - Returns an SVal* representing an optional default 218 /// binding associated with a region and its subregions. 219 Optional<SVal> getDefaultBinding(const MemRegion *R) const; 220 221 /// Return the internal tree as a Store. 222 Store asStore() const { 223 llvm::PointerIntPair<Store, 1, bool> Ptr = { 224 asImmutableMap().getRootWithoutRetain(), IsMainAnalysis}; 225 return reinterpret_cast<Store>(Ptr.getOpaqueValue()); 226 } 227 228 bool isMainAnalysis() const { 229 return IsMainAnalysis; 230 } 231 232 void printJson(raw_ostream &Out, const char *NL = "\n", 233 unsigned int Space = 0, bool IsDot = false) const { 234 for (iterator I = begin(); I != end(); ++I) { 235 // TODO: We might need a .printJson for I.getKey() as well. 236 Indent(Out, Space, IsDot) 237 << "{ \"cluster\": \"" << I.getKey() << "\", \"pointer\": \"" 238 << (const void *)I.getKey() << "\", \"items\": [" << NL; 239 240 ++Space; 241 const ClusterBindings &CB = I.getData(); 242 for (ClusterBindings::iterator CI = CB.begin(); CI != CB.end(); ++CI) { 243 Indent(Out, Space, IsDot) << "{ " << CI.getKey() << ", \"value\": "; 244 CI.getData().printJson(Out, /*AddQuotes=*/true); 245 Out << " }"; 246 if (std::next(CI) != CB.end()) 247 Out << ','; 248 Out << NL; 249 } 250 251 --Space; 252 Indent(Out, Space, IsDot) << "]}"; 253 if (std::next(I) != end()) 254 Out << ','; 255 Out << NL; 256 } 257 } 258 259 LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); } 260 }; 261 } // end anonymous namespace 262 263 typedef const RegionBindingsRef& RegionBindingsConstRef; 264 265 Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { 266 return Optional<SVal>::create(lookup(R, BindingKey::Direct)); 267 } 268 269 Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { 270 return Optional<SVal>::create(lookup(R, BindingKey::Default)); 271 } 272 273 RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { 274 const MemRegion *Base = K.getBaseRegion(); 275 276 const ClusterBindings *ExistingCluster = lookup(Base); 277 ClusterBindings Cluster = 278 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap()); 279 280 ClusterBindings NewCluster = CBFactory->add(Cluster, K, V); 281 return add(Base, NewCluster); 282 } 283 284 285 RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, 286 BindingKey::Kind k, 287 SVal V) const { 288 return addBinding(BindingKey::Make(R, k), V); 289 } 290 291 const SVal *RegionBindingsRef::lookup(BindingKey K) const { 292 const ClusterBindings *Cluster = lookup(K.getBaseRegion()); 293 if (!Cluster) 294 return nullptr; 295 return Cluster->lookup(K); 296 } 297 298 const SVal *RegionBindingsRef::lookup(const MemRegion *R, 299 BindingKey::Kind k) const { 300 return lookup(BindingKey::Make(R, k)); 301 } 302 303 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { 304 const MemRegion *Base = K.getBaseRegion(); 305 const ClusterBindings *Cluster = lookup(Base); 306 if (!Cluster) 307 return *this; 308 309 ClusterBindings NewCluster = CBFactory->remove(*Cluster, K); 310 if (NewCluster.isEmpty()) 311 return remove(Base); 312 return add(Base, NewCluster); 313 } 314 315 RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, 316 BindingKey::Kind k){ 317 return removeBinding(BindingKey::Make(R, k)); 318 } 319 320 //===----------------------------------------------------------------------===// 321 // Fine-grained control of RegionStoreManager. 322 //===----------------------------------------------------------------------===// 323 324 namespace { 325 struct minimal_features_tag {}; 326 struct maximal_features_tag {}; 327 328 class RegionStoreFeatures { 329 bool SupportsFields; 330 public: 331 RegionStoreFeatures(minimal_features_tag) : 332 SupportsFields(false) {} 333 334 RegionStoreFeatures(maximal_features_tag) : 335 SupportsFields(true) {} 336 337 void enableFields(bool t) { SupportsFields = t; } 338 339 bool supportsFields() const { return SupportsFields; } 340 }; 341 } 342 343 //===----------------------------------------------------------------------===// 344 // Main RegionStore logic. 345 //===----------------------------------------------------------------------===// 346 347 namespace { 348 class InvalidateRegionsWorker; 349 350 class RegionStoreManager : public StoreManager { 351 public: 352 const RegionStoreFeatures Features; 353 354 RegionBindings::Factory RBFactory; 355 mutable ClusterBindings::Factory CBFactory; 356 357 typedef std::vector<SVal> SValListTy; 358 private: 359 typedef llvm::DenseMap<const LazyCompoundValData *, 360 SValListTy> LazyBindingsMapTy; 361 LazyBindingsMapTy LazyBindingsMap; 362 363 /// The largest number of fields a struct can have and still be 364 /// considered "small". 365 /// 366 /// This is currently used to decide whether or not it is worth "forcing" a 367 /// LazyCompoundVal on bind. 368 /// 369 /// This is controlled by 'region-store-small-struct-limit' option. 370 /// To disable all small-struct-dependent behavior, set the option to "0". 371 unsigned SmallStructLimit; 372 373 /// A helper used to populate the work list with the given set of 374 /// regions. 375 void populateWorkList(InvalidateRegionsWorker &W, 376 ArrayRef<SVal> Values, 377 InvalidatedRegions *TopLevelRegions); 378 379 public: 380 RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) 381 : StoreManager(mgr), Features(f), 382 RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()), 383 SmallStructLimit(0) { 384 ExprEngine &Eng = StateMgr.getOwningEngine(); 385 AnalyzerOptions &Options = Eng.getAnalysisManager().options; 386 SmallStructLimit = Options.RegionStoreSmallStructLimit; 387 } 388 389 390 /// setImplicitDefaultValue - Set the default binding for the provided 391 /// MemRegion to the value implicitly defined for compound literals when 392 /// the value is not specified. 393 RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, 394 const MemRegion *R, QualType T); 395 396 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 397 /// type. 'Array' represents the lvalue of the array being decayed 398 /// to a pointer, and the returned SVal represents the decayed 399 /// version of that lvalue (i.e., a pointer to the first element of 400 /// the array). This is called by ExprEngine when evaluating 401 /// casts from arrays to pointers. 402 SVal ArrayToPointer(Loc Array, QualType ElementTy) override; 403 404 /// Creates the Store that correctly represents memory contents before 405 /// the beginning of the analysis of the given top-level stack frame. 406 StoreRef getInitialStore(const LocationContext *InitLoc) override { 407 bool IsMainAnalysis = false; 408 if (const auto *FD = dyn_cast<FunctionDecl>(InitLoc->getDecl())) 409 IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus; 410 return StoreRef(RegionBindingsRef( 411 RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory), 412 CBFactory, IsMainAnalysis).asStore(), *this); 413 } 414 415 //===-------------------------------------------------------------------===// 416 // Binding values to regions. 417 //===-------------------------------------------------------------------===// 418 RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, 419 const Expr *Ex, 420 unsigned Count, 421 const LocationContext *LCtx, 422 RegionBindingsRef B, 423 InvalidatedRegions *Invalidated); 424 425 StoreRef invalidateRegions(Store store, 426 ArrayRef<SVal> Values, 427 const Expr *E, unsigned Count, 428 const LocationContext *LCtx, 429 const CallEvent *Call, 430 InvalidatedSymbols &IS, 431 RegionAndSymbolInvalidationTraits &ITraits, 432 InvalidatedRegions *Invalidated, 433 InvalidatedRegions *InvalidatedTopLevel) override; 434 435 bool scanReachableSymbols(Store S, const MemRegion *R, 436 ScanReachableSymbols &Callbacks) override; 437 438 RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, 439 const SubRegion *R); 440 441 public: // Part of public interface to class. 442 443 StoreRef Bind(Store store, Loc LV, SVal V) override { 444 return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); 445 } 446 447 RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); 448 449 // BindDefaultInitial is only used to initialize a region with 450 // a default value. 451 StoreRef BindDefaultInitial(Store store, const MemRegion *R, 452 SVal V) override { 453 RegionBindingsRef B = getRegionBindings(store); 454 // Use other APIs when you have to wipe the region that was initialized 455 // earlier. 456 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) && 457 "Double initialization!"); 458 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); 459 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); 460 } 461 462 // BindDefaultZero is used for zeroing constructors that may accidentally 463 // overwrite existing bindings. 464 StoreRef BindDefaultZero(Store store, const MemRegion *R) override { 465 // FIXME: The offsets of empty bases can be tricky because of 466 // of the so called "empty base class optimization". 467 // If a base class has been optimized out 468 // we should not try to create a binding, otherwise we should. 469 // Unfortunately, at the moment ASTRecordLayout doesn't expose 470 // the actual sizes of the empty bases 471 // and trying to infer them from offsets/alignments 472 // seems to be error-prone and non-trivial because of the trailing padding. 473 // As a temporary mitigation we don't create bindings for empty bases. 474 if (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R)) 475 if (BR->getDecl()->isEmpty()) 476 return StoreRef(store, *this); 477 478 RegionBindingsRef B = getRegionBindings(store); 479 SVal V = svalBuilder.makeZeroVal(Ctx.CharTy); 480 B = removeSubRegionBindings(B, cast<SubRegion>(R)); 481 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); 482 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); 483 } 484 485 /// Attempt to extract the fields of \p LCV and bind them to the struct region 486 /// \p R. 487 /// 488 /// This path is used when it seems advantageous to "force" loading the values 489 /// within a LazyCompoundVal to bind memberwise to the struct region, rather 490 /// than using a Default binding at the base of the entire region. This is a 491 /// heuristic attempting to avoid building long chains of LazyCompoundVals. 492 /// 493 /// \returns The updated store bindings, or \c None if binding non-lazily 494 /// would be too expensive. 495 Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B, 496 const TypedValueRegion *R, 497 const RecordDecl *RD, 498 nonloc::LazyCompoundVal LCV); 499 500 /// BindStruct - Bind a compound value to a structure. 501 RegionBindingsRef bindStruct(RegionBindingsConstRef B, 502 const TypedValueRegion* R, SVal V); 503 504 /// BindVector - Bind a compound value to a vector. 505 RegionBindingsRef bindVector(RegionBindingsConstRef B, 506 const TypedValueRegion* R, SVal V); 507 508 RegionBindingsRef bindArray(RegionBindingsConstRef B, 509 const TypedValueRegion* R, 510 SVal V); 511 512 /// Clears out all bindings in the given region and assigns a new value 513 /// as a Default binding. 514 RegionBindingsRef bindAggregate(RegionBindingsConstRef B, 515 const TypedRegion *R, 516 SVal DefaultVal); 517 518 /// Create a new store with the specified binding removed. 519 /// \param ST the original store, that is the basis for the new store. 520 /// \param L the location whose binding should be removed. 521 StoreRef killBinding(Store ST, Loc L) override; 522 523 void incrementReferenceCount(Store store) override { 524 getRegionBindings(store).manualRetain(); 525 } 526 527 /// If the StoreManager supports it, decrement the reference count of 528 /// the specified Store object. If the reference count hits 0, the memory 529 /// associated with the object is recycled. 530 void decrementReferenceCount(Store store) override { 531 getRegionBindings(store).manualRelease(); 532 } 533 534 bool includedInBindings(Store store, const MemRegion *region) const override; 535 536 /// Return the value bound to specified location in a given state. 537 /// 538 /// The high level logic for this method is this: 539 /// getBinding (L) 540 /// if L has binding 541 /// return L's binding 542 /// else if L is in killset 543 /// return unknown 544 /// else 545 /// if L is on stack or heap 546 /// return undefined 547 /// else 548 /// return symbolic 549 SVal getBinding(Store S, Loc L, QualType T) override { 550 return getBinding(getRegionBindings(S), L, T); 551 } 552 553 Optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override { 554 RegionBindingsRef B = getRegionBindings(S); 555 // Default bindings are always applied over a base region so look up the 556 // base region's default binding, otherwise the lookup will fail when R 557 // is at an offset from R->getBaseRegion(). 558 return B.getDefaultBinding(R->getBaseRegion()); 559 } 560 561 SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); 562 563 SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); 564 565 SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); 566 567 SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); 568 569 SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); 570 571 SVal getBindingForLazySymbol(const TypedValueRegion *R); 572 573 SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 574 const TypedValueRegion *R, 575 QualType Ty); 576 577 SVal getLazyBinding(const SubRegion *LazyBindingRegion, 578 RegionBindingsRef LazyBinding); 579 580 /// Get bindings for the values in a struct and return a CompoundVal, used 581 /// when doing struct copy: 582 /// struct s x, y; 583 /// x = y; 584 /// y's value is retrieved by this method. 585 SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); 586 SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); 587 NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); 588 589 /// Used to lazily generate derived symbols for bindings that are defined 590 /// implicitly by default bindings in a super region. 591 /// 592 /// Note that callers may need to specially handle LazyCompoundVals, which 593 /// are returned as is in case the caller needs to treat them differently. 594 Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 595 const MemRegion *superR, 596 const TypedValueRegion *R, 597 QualType Ty); 598 599 /// Get the state and region whose binding this region \p R corresponds to. 600 /// 601 /// If there is no lazy binding for \p R, the returned value will have a null 602 /// \c second. Note that a null pointer can represents a valid Store. 603 std::pair<Store, const SubRegion *> 604 findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, 605 const SubRegion *originalRegion); 606 607 /// Returns the cached set of interesting SVals contained within a lazy 608 /// binding. 609 /// 610 /// The precise value of "interesting" is determined for the purposes of 611 /// RegionStore's internal analysis. It must always contain all regions and 612 /// symbols, but may omit constants and other kinds of SVal. 613 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); 614 615 //===------------------------------------------------------------------===// 616 // State pruning. 617 //===------------------------------------------------------------------===// 618 619 /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 620 /// It returns a new Store with these values removed. 621 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 622 SymbolReaper& SymReaper) override; 623 624 //===------------------------------------------------------------------===// 625 // Utility methods. 626 //===------------------------------------------------------------------===// 627 628 RegionBindingsRef getRegionBindings(Store store) const { 629 llvm::PointerIntPair<Store, 1, bool> Ptr; 630 Ptr.setFromOpaqueValue(const_cast<void *>(store)); 631 return RegionBindingsRef( 632 CBFactory, 633 static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()), 634 RBFactory.getTreeFactory(), 635 Ptr.getInt()); 636 } 637 638 void printJson(raw_ostream &Out, Store S, const char *NL = "\n", 639 unsigned int Space = 0, bool IsDot = false) const override; 640 641 void iterBindings(Store store, BindingsHandler& f) override { 642 RegionBindingsRef B = getRegionBindings(store); 643 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 644 const ClusterBindings &Cluster = I.getData(); 645 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 646 CI != CE; ++CI) { 647 const BindingKey &K = CI.getKey(); 648 if (!K.isDirect()) 649 continue; 650 if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { 651 // FIXME: Possibly incorporate the offset? 652 if (!f.HandleBinding(*this, store, R, CI.getData())) 653 return; 654 } 655 } 656 } 657 } 658 }; 659 660 } // end anonymous namespace 661 662 //===----------------------------------------------------------------------===// 663 // RegionStore creation. 664 //===----------------------------------------------------------------------===// 665 666 std::unique_ptr<StoreManager> 667 ento::CreateRegionStoreManager(ProgramStateManager &StMgr) { 668 RegionStoreFeatures F = maximal_features_tag(); 669 return std::make_unique<RegionStoreManager>(StMgr, F); 670 } 671 672 std::unique_ptr<StoreManager> 673 ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { 674 RegionStoreFeatures F = minimal_features_tag(); 675 F.enableFields(true); 676 return std::make_unique<RegionStoreManager>(StMgr, F); 677 } 678 679 680 //===----------------------------------------------------------------------===// 681 // Region Cluster analysis. 682 //===----------------------------------------------------------------------===// 683 684 namespace { 685 /// Used to determine which global regions are automatically included in the 686 /// initial worklist of a ClusterAnalysis. 687 enum GlobalsFilterKind { 688 /// Don't include any global regions. 689 GFK_None, 690 /// Only include system globals. 691 GFK_SystemOnly, 692 /// Include all global regions. 693 GFK_All 694 }; 695 696 template <typename DERIVED> 697 class ClusterAnalysis { 698 protected: 699 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; 700 typedef const MemRegion * WorkListElement; 701 typedef SmallVector<WorkListElement, 10> WorkList; 702 703 llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; 704 705 WorkList WL; 706 707 RegionStoreManager &RM; 708 ASTContext &Ctx; 709 SValBuilder &svalBuilder; 710 711 RegionBindingsRef B; 712 713 714 protected: 715 const ClusterBindings *getCluster(const MemRegion *R) { 716 return B.lookup(R); 717 } 718 719 /// Returns true if all clusters in the given memspace should be initially 720 /// included in the cluster analysis. Subclasses may provide their 721 /// own implementation. 722 bool includeEntireMemorySpace(const MemRegion *Base) { 723 return false; 724 } 725 726 public: 727 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 728 RegionBindingsRef b) 729 : RM(rm), Ctx(StateMgr.getContext()), 730 svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {} 731 732 RegionBindingsRef getRegionBindings() const { return B; } 733 734 bool isVisited(const MemRegion *R) { 735 return Visited.count(getCluster(R)); 736 } 737 738 void GenerateClusters() { 739 // Scan the entire set of bindings and record the region clusters. 740 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 741 RI != RE; ++RI){ 742 const MemRegion *Base = RI.getKey(); 743 744 const ClusterBindings &Cluster = RI.getData(); 745 assert(!Cluster.isEmpty() && "Empty clusters should be removed"); 746 static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); 747 748 // If the base's memspace should be entirely invalidated, add the cluster 749 // to the workspace up front. 750 if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base)) 751 AddToWorkList(WorkListElement(Base), &Cluster); 752 } 753 } 754 755 bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { 756 if (C && !Visited.insert(C).second) 757 return false; 758 WL.push_back(E); 759 return true; 760 } 761 762 bool AddToWorkList(const MemRegion *R) { 763 return static_cast<DERIVED*>(this)->AddToWorkList(R); 764 } 765 766 void RunWorkList() { 767 while (!WL.empty()) { 768 WorkListElement E = WL.pop_back_val(); 769 const MemRegion *BaseR = E; 770 771 static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); 772 } 773 } 774 775 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} 776 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} 777 778 void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, 779 bool Flag) { 780 static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); 781 } 782 }; 783 } 784 785 //===----------------------------------------------------------------------===// 786 // Binding invalidation. 787 //===----------------------------------------------------------------------===// 788 789 bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, 790 ScanReachableSymbols &Callbacks) { 791 assert(R == R->getBaseRegion() && "Should only be called for base regions"); 792 RegionBindingsRef B = getRegionBindings(S); 793 const ClusterBindings *Cluster = B.lookup(R); 794 795 if (!Cluster) 796 return true; 797 798 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); 799 RI != RE; ++RI) { 800 if (!Callbacks.scan(RI.getData())) 801 return false; 802 } 803 804 return true; 805 } 806 807 static inline bool isUnionField(const FieldRegion *FR) { 808 return FR->getDecl()->getParent()->isUnion(); 809 } 810 811 typedef SmallVector<const FieldDecl *, 8> FieldVector; 812 813 static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { 814 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 815 816 const MemRegion *Base = K.getConcreteOffsetRegion(); 817 const MemRegion *R = K.getRegion(); 818 819 while (R != Base) { 820 if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) 821 if (!isUnionField(FR)) 822 Fields.push_back(FR->getDecl()); 823 824 R = cast<SubRegion>(R)->getSuperRegion(); 825 } 826 } 827 828 static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { 829 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 830 831 if (Fields.empty()) 832 return true; 833 834 FieldVector FieldsInBindingKey; 835 getSymbolicOffsetFields(K, FieldsInBindingKey); 836 837 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); 838 if (Delta >= 0) 839 return std::equal(FieldsInBindingKey.begin() + Delta, 840 FieldsInBindingKey.end(), 841 Fields.begin()); 842 else 843 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), 844 Fields.begin() - Delta); 845 } 846 847 /// Collects all bindings in \p Cluster that may refer to bindings within 848 /// \p Top. 849 /// 850 /// Each binding is a pair whose \c first is the key (a BindingKey) and whose 851 /// \c second is the value (an SVal). 852 /// 853 /// The \p IncludeAllDefaultBindings parameter specifies whether to include 854 /// default bindings that may extend beyond \p Top itself, e.g. if \p Top is 855 /// an aggregate within a larger aggregate with a default binding. 856 static void 857 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 858 SValBuilder &SVB, const ClusterBindings &Cluster, 859 const SubRegion *Top, BindingKey TopKey, 860 bool IncludeAllDefaultBindings) { 861 FieldVector FieldsInSymbolicSubregions; 862 if (TopKey.hasSymbolicOffset()) { 863 getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); 864 Top = TopKey.getConcreteOffsetRegion(); 865 TopKey = BindingKey::Make(Top, BindingKey::Default); 866 } 867 868 // Find the length (in bits) of the region being invalidated. 869 uint64_t Length = UINT64_MAX; 870 SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB); 871 if (Optional<nonloc::ConcreteInt> ExtentCI = 872 Extent.getAs<nonloc::ConcreteInt>()) { 873 const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 874 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 875 // Extents are in bytes but region offsets are in bits. Be careful! 876 Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); 877 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { 878 if (FR->getDecl()->isBitField()) 879 Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); 880 } 881 882 for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); 883 I != E; ++I) { 884 BindingKey NextKey = I.getKey(); 885 if (NextKey.getRegion() == TopKey.getRegion()) { 886 // FIXME: This doesn't catch the case where we're really invalidating a 887 // region with a symbolic offset. Example: 888 // R: points[i].y 889 // Next: points[0].x 890 891 if (NextKey.getOffset() > TopKey.getOffset() && 892 NextKey.getOffset() - TopKey.getOffset() < Length) { 893 // Case 1: The next binding is inside the region we're invalidating. 894 // Include it. 895 Bindings.push_back(*I); 896 897 } else if (NextKey.getOffset() == TopKey.getOffset()) { 898 // Case 2: The next binding is at the same offset as the region we're 899 // invalidating. In this case, we need to leave default bindings alone, 900 // since they may be providing a default value for a regions beyond what 901 // we're invalidating. 902 // FIXME: This is probably incorrect; consider invalidating an outer 903 // struct whose first field is bound to a LazyCompoundVal. 904 if (IncludeAllDefaultBindings || NextKey.isDirect()) 905 Bindings.push_back(*I); 906 } 907 908 } else if (NextKey.hasSymbolicOffset()) { 909 const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 910 if (Top->isSubRegionOf(Base) && Top != Base) { 911 // Case 3: The next key is symbolic and we just changed something within 912 // its concrete region. We don't know if the binding is still valid, so 913 // we'll be conservative and include it. 914 if (IncludeAllDefaultBindings || NextKey.isDirect()) 915 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 916 Bindings.push_back(*I); 917 } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 918 // Case 4: The next key is symbolic, but we changed a known 919 // super-region. In this case the binding is certainly included. 920 if (BaseSR->isSubRegionOf(Top)) 921 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 922 Bindings.push_back(*I); 923 } 924 } 925 } 926 } 927 928 static void 929 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 930 SValBuilder &SVB, const ClusterBindings &Cluster, 931 const SubRegion *Top, bool IncludeAllDefaultBindings) { 932 collectSubRegionBindings(Bindings, SVB, Cluster, Top, 933 BindingKey::Make(Top, BindingKey::Default), 934 IncludeAllDefaultBindings); 935 } 936 937 RegionBindingsRef 938 RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, 939 const SubRegion *Top) { 940 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); 941 const MemRegion *ClusterHead = TopKey.getBaseRegion(); 942 943 if (Top == ClusterHead) { 944 // We can remove an entire cluster's bindings all in one go. 945 return B.remove(Top); 946 } 947 948 const ClusterBindings *Cluster = B.lookup(ClusterHead); 949 if (!Cluster) { 950 // If we're invalidating a region with a symbolic offset, we need to make 951 // sure we don't treat the base region as uninitialized anymore. 952 if (TopKey.hasSymbolicOffset()) { 953 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 954 return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); 955 } 956 return B; 957 } 958 959 SmallVector<BindingPair, 32> Bindings; 960 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, 961 /*IncludeAllDefaultBindings=*/false); 962 963 ClusterBindingsRef Result(*Cluster, CBFactory); 964 for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 965 E = Bindings.end(); 966 I != E; ++I) 967 Result = Result.remove(I->first); 968 969 // If we're invalidating a region with a symbolic offset, we need to make sure 970 // we don't treat the base region as uninitialized anymore. 971 // FIXME: This isn't very precise; see the example in 972 // collectSubRegionBindings. 973 if (TopKey.hasSymbolicOffset()) { 974 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 975 Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), 976 UnknownVal()); 977 } 978 979 if (Result.isEmpty()) 980 return B.remove(ClusterHead); 981 return B.add(ClusterHead, Result.asImmutableMap()); 982 } 983 984 namespace { 985 class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker> 986 { 987 const Expr *Ex; 988 unsigned Count; 989 const LocationContext *LCtx; 990 InvalidatedSymbols &IS; 991 RegionAndSymbolInvalidationTraits &ITraits; 992 StoreManager::InvalidatedRegions *Regions; 993 GlobalsFilterKind GlobalsFilter; 994 public: 995 InvalidateRegionsWorker(RegionStoreManager &rm, 996 ProgramStateManager &stateMgr, 997 RegionBindingsRef b, 998 const Expr *ex, unsigned count, 999 const LocationContext *lctx, 1000 InvalidatedSymbols &is, 1001 RegionAndSymbolInvalidationTraits &ITraitsIn, 1002 StoreManager::InvalidatedRegions *r, 1003 GlobalsFilterKind GFK) 1004 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b), 1005 Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r), 1006 GlobalsFilter(GFK) {} 1007 1008 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 1009 void VisitBinding(SVal V); 1010 1011 using ClusterAnalysis::AddToWorkList; 1012 1013 bool AddToWorkList(const MemRegion *R); 1014 1015 /// Returns true if all clusters in the memory space for \p Base should be 1016 /// be invalidated. 1017 bool includeEntireMemorySpace(const MemRegion *Base); 1018 1019 /// Returns true if the memory space of the given region is one of the global 1020 /// regions specially included at the start of invalidation. 1021 bool isInitiallyIncludedGlobalRegion(const MemRegion *R); 1022 }; 1023 } 1024 1025 bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) { 1026 bool doNotInvalidateSuperRegion = ITraits.hasTrait( 1027 R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); 1028 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion(); 1029 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); 1030 } 1031 1032 void InvalidateRegionsWorker::VisitBinding(SVal V) { 1033 // A symbol? Mark it touched by the invalidation. 1034 if (SymbolRef Sym = V.getAsSymbol()) 1035 IS.insert(Sym); 1036 1037 if (const MemRegion *R = V.getAsRegion()) { 1038 AddToWorkList(R); 1039 return; 1040 } 1041 1042 // Is it a LazyCompoundVal? All references get invalidated as well. 1043 if (Optional<nonloc::LazyCompoundVal> LCS = 1044 V.getAs<nonloc::LazyCompoundVal>()) { 1045 1046 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 1047 1048 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 1049 E = Vals.end(); 1050 I != E; ++I) 1051 VisitBinding(*I); 1052 1053 return; 1054 } 1055 } 1056 1057 void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR, 1058 const ClusterBindings *C) { 1059 1060 bool PreserveRegionsContents = 1061 ITraits.hasTrait(baseR, 1062 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 1063 1064 if (C) { 1065 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 1066 VisitBinding(I.getData()); 1067 1068 // Invalidate regions contents. 1069 if (!PreserveRegionsContents) 1070 B = B.remove(baseR); 1071 } 1072 1073 if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) { 1074 if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) { 1075 1076 // Lambdas can affect all static local variables without explicitly 1077 // capturing those. 1078 // We invalidate all static locals referenced inside the lambda body. 1079 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) { 1080 using namespace ast_matchers; 1081 1082 const char *DeclBind = "DeclBind"; 1083 StatementMatcher RefToStatic = stmt(hasDescendant(declRefExpr( 1084 to(varDecl(hasStaticStorageDuration()).bind(DeclBind))))); 1085 auto Matches = 1086 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(), 1087 RD->getASTContext()); 1088 1089 for (BoundNodes &Match : Matches) { 1090 auto *VD = Match.getNodeAs<VarDecl>(DeclBind); 1091 const VarRegion *ToInvalidate = 1092 RM.getRegionManager().getVarRegion(VD, LCtx); 1093 AddToWorkList(ToInvalidate); 1094 } 1095 } 1096 } 1097 } 1098 1099 // BlockDataRegion? If so, invalidate captured variables that are passed 1100 // by reference. 1101 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 1102 for (BlockDataRegion::referenced_vars_iterator 1103 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 1104 BI != BE; ++BI) { 1105 const VarRegion *VR = BI.getCapturedRegion(); 1106 const VarDecl *VD = VR->getDecl(); 1107 if (VD->hasAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 1108 AddToWorkList(VR); 1109 } 1110 else if (Loc::isLocType(VR->getValueType())) { 1111 // Map the current bindings to a Store to retrieve the value 1112 // of the binding. If that binding itself is a region, we should 1113 // invalidate that region. This is because a block may capture 1114 // a pointer value, but the thing pointed by that pointer may 1115 // get invalidated. 1116 SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); 1117 if (Optional<Loc> L = V.getAs<Loc>()) { 1118 if (const MemRegion *LR = L->getAsRegion()) 1119 AddToWorkList(LR); 1120 } 1121 } 1122 } 1123 return; 1124 } 1125 1126 // Symbolic region? 1127 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) 1128 IS.insert(SR->getSymbol()); 1129 1130 // Nothing else should be done in the case when we preserve regions context. 1131 if (PreserveRegionsContents) 1132 return; 1133 1134 // Otherwise, we have a normal data region. Record that we touched the region. 1135 if (Regions) 1136 Regions->push_back(baseR); 1137 1138 if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { 1139 // Invalidate the region by setting its default value to 1140 // conjured symbol. The type of the symbol is irrelevant. 1141 DefinedOrUnknownSVal V = 1142 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 1143 B = B.addBinding(baseR, BindingKey::Default, V); 1144 return; 1145 } 1146 1147 if (!baseR->isBoundable()) 1148 return; 1149 1150 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 1151 QualType T = TR->getValueType(); 1152 1153 if (isInitiallyIncludedGlobalRegion(baseR)) { 1154 // If the region is a global and we are invalidating all globals, 1155 // erasing the entry is good enough. This causes all globals to be lazily 1156 // symbolicated from the same base symbol. 1157 return; 1158 } 1159 1160 if (T->isRecordType()) { 1161 // Invalidate the region by setting its default value to 1162 // conjured symbol. The type of the symbol is irrelevant. 1163 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1164 Ctx.IntTy, Count); 1165 B = B.addBinding(baseR, BindingKey::Default, V); 1166 return; 1167 } 1168 1169 if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 1170 bool doNotInvalidateSuperRegion = ITraits.hasTrait( 1171 baseR, 1172 RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); 1173 1174 if (doNotInvalidateSuperRegion) { 1175 // We are not doing blank invalidation of the whole array region so we 1176 // have to manually invalidate each elements. 1177 Optional<uint64_t> NumElements; 1178 1179 // Compute lower and upper offsets for region within array. 1180 if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT)) 1181 NumElements = CAT->getSize().getZExtValue(); 1182 if (!NumElements) // We are not dealing with a constant size array 1183 goto conjure_default; 1184 QualType ElementTy = AT->getElementType(); 1185 uint64_t ElemSize = Ctx.getTypeSize(ElementTy); 1186 const RegionOffset &RO = baseR->getAsOffset(); 1187 const MemRegion *SuperR = baseR->getBaseRegion(); 1188 if (RO.hasSymbolicOffset()) { 1189 // If base region has a symbolic offset, 1190 // we revert to invalidating the super region. 1191 if (SuperR) 1192 AddToWorkList(SuperR); 1193 goto conjure_default; 1194 } 1195 1196 uint64_t LowerOffset = RO.getOffset(); 1197 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize; 1198 bool UpperOverflow = UpperOffset < LowerOffset; 1199 1200 // Invalidate regions which are within array boundaries, 1201 // or have a symbolic offset. 1202 if (!SuperR) 1203 goto conjure_default; 1204 1205 const ClusterBindings *C = B.lookup(SuperR); 1206 if (!C) 1207 goto conjure_default; 1208 1209 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; 1210 ++I) { 1211 const BindingKey &BK = I.getKey(); 1212 Optional<uint64_t> ROffset = 1213 BK.hasSymbolicOffset() ? Optional<uint64_t>() : BK.getOffset(); 1214 1215 // Check offset is not symbolic and within array's boundaries. 1216 // Handles arrays of 0 elements and of 0-sized elements as well. 1217 if (!ROffset || 1218 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) || 1219 (UpperOverflow && 1220 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) || 1221 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) { 1222 B = B.removeBinding(I.getKey()); 1223 // Bound symbolic regions need to be invalidated for dead symbol 1224 // detection. 1225 SVal V = I.getData(); 1226 const MemRegion *R = V.getAsRegion(); 1227 if (R && isa<SymbolicRegion>(R)) 1228 VisitBinding(V); 1229 } 1230 } 1231 } 1232 conjure_default: 1233 // Set the default value of the array to conjured symbol. 1234 DefinedOrUnknownSVal V = 1235 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1236 AT->getElementType(), Count); 1237 B = B.addBinding(baseR, BindingKey::Default, V); 1238 return; 1239 } 1240 1241 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1242 T,Count); 1243 assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 1244 B = B.addBinding(baseR, BindingKey::Direct, V); 1245 } 1246 1247 bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion( 1248 const MemRegion *R) { 1249 switch (GlobalsFilter) { 1250 case GFK_None: 1251 return false; 1252 case GFK_SystemOnly: 1253 return isa<GlobalSystemSpaceRegion>(R->getMemorySpace()); 1254 case GFK_All: 1255 return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()); 1256 } 1257 1258 llvm_unreachable("unknown globals filter"); 1259 } 1260 1261 bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) { 1262 if (isInitiallyIncludedGlobalRegion(Base)) 1263 return true; 1264 1265 const MemSpaceRegion *MemSpace = Base->getMemorySpace(); 1266 return ITraits.hasTrait(MemSpace, 1267 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); 1268 } 1269 1270 RegionBindingsRef 1271 RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 1272 const Expr *Ex, 1273 unsigned Count, 1274 const LocationContext *LCtx, 1275 RegionBindingsRef B, 1276 InvalidatedRegions *Invalidated) { 1277 // Bind the globals memory space to a new symbol that we will use to derive 1278 // the bindings for all globals. 1279 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 1280 SVal V = svalBuilder.conjureSymbolVal(/* symbolTag = */ (const void*) GS, Ex, LCtx, 1281 /* type does not matter */ Ctx.IntTy, 1282 Count); 1283 1284 B = B.removeBinding(GS) 1285 .addBinding(BindingKey::Make(GS, BindingKey::Default), V); 1286 1287 // Even if there are no bindings in the global scope, we still need to 1288 // record that we touched it. 1289 if (Invalidated) 1290 Invalidated->push_back(GS); 1291 1292 return B; 1293 } 1294 1295 void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W, 1296 ArrayRef<SVal> Values, 1297 InvalidatedRegions *TopLevelRegions) { 1298 for (ArrayRef<SVal>::iterator I = Values.begin(), 1299 E = Values.end(); I != E; ++I) { 1300 SVal V = *I; 1301 if (Optional<nonloc::LazyCompoundVal> LCS = 1302 V.getAs<nonloc::LazyCompoundVal>()) { 1303 1304 const SValListTy &Vals = getInterestingValues(*LCS); 1305 1306 for (SValListTy::const_iterator I = Vals.begin(), 1307 E = Vals.end(); I != E; ++I) { 1308 // Note: the last argument is false here because these are 1309 // non-top-level regions. 1310 if (const MemRegion *R = (*I).getAsRegion()) 1311 W.AddToWorkList(R); 1312 } 1313 continue; 1314 } 1315 1316 if (const MemRegion *R = V.getAsRegion()) { 1317 if (TopLevelRegions) 1318 TopLevelRegions->push_back(R); 1319 W.AddToWorkList(R); 1320 continue; 1321 } 1322 } 1323 } 1324 1325 StoreRef 1326 RegionStoreManager::invalidateRegions(Store store, 1327 ArrayRef<SVal> Values, 1328 const Expr *Ex, unsigned Count, 1329 const LocationContext *LCtx, 1330 const CallEvent *Call, 1331 InvalidatedSymbols &IS, 1332 RegionAndSymbolInvalidationTraits &ITraits, 1333 InvalidatedRegions *TopLevelRegions, 1334 InvalidatedRegions *Invalidated) { 1335 GlobalsFilterKind GlobalsFilter; 1336 if (Call) { 1337 if (Call->isInSystemHeader()) 1338 GlobalsFilter = GFK_SystemOnly; 1339 else 1340 GlobalsFilter = GFK_All; 1341 } else { 1342 GlobalsFilter = GFK_None; 1343 } 1344 1345 RegionBindingsRef B = getRegionBindings(store); 1346 InvalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits, 1347 Invalidated, GlobalsFilter); 1348 1349 // Scan the bindings and generate the clusters. 1350 W.GenerateClusters(); 1351 1352 // Add the regions to the worklist. 1353 populateWorkList(W, Values, TopLevelRegions); 1354 1355 W.RunWorkList(); 1356 1357 // Return the new bindings. 1358 B = W.getRegionBindings(); 1359 1360 // For calls, determine which global regions should be invalidated and 1361 // invalidate them. (Note that function-static and immutable globals are never 1362 // invalidated by this.) 1363 // TODO: This could possibly be more precise with modules. 1364 switch (GlobalsFilter) { 1365 case GFK_All: 1366 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 1367 Ex, Count, LCtx, B, Invalidated); 1368 LLVM_FALLTHROUGH; 1369 case GFK_SystemOnly: 1370 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 1371 Ex, Count, LCtx, B, Invalidated); 1372 LLVM_FALLTHROUGH; 1373 case GFK_None: 1374 break; 1375 } 1376 1377 return StoreRef(B.asStore(), *this); 1378 } 1379 1380 //===----------------------------------------------------------------------===// 1381 // Location and region casting. 1382 //===----------------------------------------------------------------------===// 1383 1384 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 1385 /// type. 'Array' represents the lvalue of the array being decayed 1386 /// to a pointer, and the returned SVal represents the decayed 1387 /// version of that lvalue (i.e., a pointer to the first element of 1388 /// the array). This is called by ExprEngine when evaluating casts 1389 /// from arrays to pointers. 1390 SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { 1391 if (Array.getAs<loc::ConcreteInt>()) 1392 return Array; 1393 1394 if (!Array.getAs<loc::MemRegionVal>()) 1395 return UnknownVal(); 1396 1397 const SubRegion *R = 1398 cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion()); 1399 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 1400 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx)); 1401 } 1402 1403 //===----------------------------------------------------------------------===// 1404 // Loading values from regions. 1405 //===----------------------------------------------------------------------===// 1406 1407 SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { 1408 assert(!L.getAs<UnknownVal>() && "location unknown"); 1409 assert(!L.getAs<UndefinedVal>() && "location undefined"); 1410 1411 // For access to concrete addresses, return UnknownVal. Checks 1412 // for null dereferences (and similar errors) are done by checkers, not 1413 // the Store. 1414 // FIXME: We can consider lazily symbolicating such memory, but we really 1415 // should defer this when we can reason easily about symbolicating arrays 1416 // of bytes. 1417 if (L.getAs<loc::ConcreteInt>()) { 1418 return UnknownVal(); 1419 } 1420 if (!L.getAs<loc::MemRegionVal>()) { 1421 return UnknownVal(); 1422 } 1423 1424 const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); 1425 1426 if (isa<BlockDataRegion>(MR)) { 1427 return UnknownVal(); 1428 } 1429 1430 if (!isa<TypedValueRegion>(MR)) { 1431 if (T.isNull()) { 1432 if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1433 T = TR->getLocationType()->getPointeeType(); 1434 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 1435 T = SR->getSymbol()->getType()->getPointeeType(); 1436 } 1437 assert(!T.isNull() && "Unable to auto-detect binding type!"); 1438 assert(!T->isVoidType() && "Attempting to dereference a void pointer!"); 1439 MR = GetElementZeroRegion(cast<SubRegion>(MR), T); 1440 } else { 1441 T = cast<TypedValueRegion>(MR)->getValueType(); 1442 } 1443 1444 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1445 // instead of 'Loc', and have the other Loc cases handled at a higher level. 1446 const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1447 QualType RTy = R->getValueType(); 1448 1449 // FIXME: we do not yet model the parts of a complex type, so treat the 1450 // whole thing as "unknown". 1451 if (RTy->isAnyComplexType()) 1452 return UnknownVal(); 1453 1454 // FIXME: We should eventually handle funny addressing. e.g.: 1455 // 1456 // int x = ...; 1457 // int *p = &x; 1458 // char *q = (char*) p; 1459 // char c = *q; // returns the first byte of 'x'. 1460 // 1461 // Such funny addressing will occur due to layering of regions. 1462 if (RTy->isStructureOrClassType()) 1463 return getBindingForStruct(B, R); 1464 1465 // FIXME: Handle unions. 1466 if (RTy->isUnionType()) 1467 return createLazyBinding(B, R); 1468 1469 if (RTy->isArrayType()) { 1470 if (RTy->isConstantArrayType()) 1471 return getBindingForArray(B, R); 1472 else 1473 return UnknownVal(); 1474 } 1475 1476 // FIXME: handle Vector types. 1477 if (RTy->isVectorType()) 1478 return UnknownVal(); 1479 1480 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1481 return svalBuilder.evalCast(getBindingForField(B, FR), T, QualType{}); 1482 1483 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1484 // FIXME: Here we actually perform an implicit conversion from the loaded 1485 // value to the element type. Eventually we want to compose these values 1486 // more intelligently. For example, an 'element' can encompass multiple 1487 // bound regions (e.g., several bound bytes), or could be a subset of 1488 // a larger value. 1489 return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{}); 1490 } 1491 1492 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1493 // FIXME: Here we actually perform an implicit conversion from the loaded 1494 // value to the ivar type. What we should model is stores to ivars 1495 // that blow past the extent of the ivar. If the address of the ivar is 1496 // reinterpretted, it is possible we stored a different value that could 1497 // fit within the ivar. Either we need to cast these when storing them 1498 // or reinterpret them lazily (as we do here). 1499 return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T, QualType{}); 1500 } 1501 1502 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1503 // FIXME: Here we actually perform an implicit conversion from the loaded 1504 // value to the variable type. What we should model is stores to variables 1505 // that blow past the extent of the variable. If the address of the 1506 // variable is reinterpretted, it is possible we stored a different value 1507 // that could fit within the variable. Either we need to cast these when 1508 // storing them or reinterpret them lazily (as we do here). 1509 return svalBuilder.evalCast(getBindingForVar(B, VR), T, QualType{}); 1510 } 1511 1512 const SVal *V = B.lookup(R, BindingKey::Direct); 1513 1514 // Check if the region has a binding. 1515 if (V) 1516 return *V; 1517 1518 // The location does not have a bound value. This means that it has 1519 // the value it had upon its creation and/or entry to the analyzed 1520 // function/method. These are either symbolic values or 'undefined'. 1521 if (R->hasStackNonParametersStorage()) { 1522 // All stack variables are considered to have undefined values 1523 // upon creation. All heap allocated blocks are considered to 1524 // have undefined values as well unless they are explicitly bound 1525 // to specific values. 1526 return UndefinedVal(); 1527 } 1528 1529 // All other values are symbolic. 1530 return svalBuilder.getRegionValueSymbolVal(R); 1531 } 1532 1533 static QualType getUnderlyingType(const SubRegion *R) { 1534 QualType RegionTy; 1535 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) 1536 RegionTy = TVR->getValueType(); 1537 1538 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1539 RegionTy = SR->getSymbol()->getType(); 1540 1541 return RegionTy; 1542 } 1543 1544 /// Checks to see if store \p B has a lazy binding for region \p R. 1545 /// 1546 /// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected 1547 /// if there are additional bindings within \p R. 1548 /// 1549 /// Note that unlike RegionStoreManager::findLazyBinding, this will not search 1550 /// for lazy bindings for super-regions of \p R. 1551 static Optional<nonloc::LazyCompoundVal> 1552 getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, 1553 const SubRegion *R, bool AllowSubregionBindings) { 1554 Optional<SVal> V = B.getDefaultBinding(R); 1555 if (!V) 1556 return None; 1557 1558 Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); 1559 if (!LCV) 1560 return None; 1561 1562 // If the LCV is for a subregion, the types might not match, and we shouldn't 1563 // reuse the binding. 1564 QualType RegionTy = getUnderlyingType(R); 1565 if (!RegionTy.isNull() && 1566 !RegionTy->isVoidPointerType()) { 1567 QualType SourceRegionTy = LCV->getRegion()->getValueType(); 1568 if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) 1569 return None; 1570 } 1571 1572 if (!AllowSubregionBindings) { 1573 // If there are any other bindings within this region, we shouldn't reuse 1574 // the top-level binding. 1575 SmallVector<BindingPair, 16> Bindings; 1576 collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, 1577 /*IncludeAllDefaultBindings=*/true); 1578 if (Bindings.size() > 1) 1579 return None; 1580 } 1581 1582 return *LCV; 1583 } 1584 1585 1586 std::pair<Store, const SubRegion *> 1587 RegionStoreManager::findLazyBinding(RegionBindingsConstRef B, 1588 const SubRegion *R, 1589 const SubRegion *originalRegion) { 1590 if (originalRegion != R) { 1591 if (Optional<nonloc::LazyCompoundVal> V = 1592 getExistingLazyBinding(svalBuilder, B, R, true)) 1593 return std::make_pair(V->getStore(), V->getRegion()); 1594 } 1595 1596 typedef std::pair<Store, const SubRegion *> StoreRegionPair; 1597 StoreRegionPair Result = StoreRegionPair(); 1598 1599 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1600 Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), 1601 originalRegion); 1602 1603 if (Result.second) 1604 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); 1605 1606 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1607 Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), 1608 originalRegion); 1609 1610 if (Result.second) 1611 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); 1612 1613 } else if (const CXXBaseObjectRegion *BaseReg = 1614 dyn_cast<CXXBaseObjectRegion>(R)) { 1615 // C++ base object region is another kind of region that we should blast 1616 // through to look for lazy compound value. It is like a field region. 1617 Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), 1618 originalRegion); 1619 1620 if (Result.second) 1621 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, 1622 Result.second); 1623 } 1624 1625 return Result; 1626 } 1627 1628 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, 1629 const ElementRegion* R) { 1630 // Check if the region has a binding. 1631 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1632 return *V; 1633 1634 const MemRegion* superR = R->getSuperRegion(); 1635 1636 // Check if the region is an element region of a string literal. 1637 if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) { 1638 // FIXME: Handle loads from strings where the literal is treated as 1639 // an integer, e.g., *((unsigned int*)"hello") 1640 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1641 if (!Ctx.hasSameUnqualifiedType(T, R->getElementType())) 1642 return UnknownVal(); 1643 1644 const StringLiteral *Str = StrR->getStringLiteral(); 1645 SVal Idx = R->getIndex(); 1646 if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) { 1647 int64_t i = CI->getValue().getSExtValue(); 1648 // Abort on string underrun. This can be possible by arbitrary 1649 // clients of getBindingForElement(). 1650 if (i < 0) 1651 return UndefinedVal(); 1652 int64_t length = Str->getLength(); 1653 // Technically, only i == length is guaranteed to be null. 1654 // However, such overflows should be caught before reaching this point; 1655 // the only time such an access would be made is if a string literal was 1656 // used to initialize a larger array. 1657 char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1658 return svalBuilder.makeIntVal(c, T); 1659 } 1660 } else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) { 1661 // Check if the containing array has an initialized value that we can trust. 1662 // We can trust a const value or a value of a global initializer in main(). 1663 const VarDecl *VD = VR->getDecl(); 1664 if (VD->getType().isConstQualified() || 1665 R->getElementType().isConstQualified() || 1666 (B.isMainAnalysis() && VD->hasGlobalStorage())) { 1667 if (const Expr *Init = VD->getAnyInitializer()) { 1668 if (const auto *InitList = dyn_cast<InitListExpr>(Init)) { 1669 // The array index has to be known. 1670 if (auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) { 1671 int64_t i = CI->getValue().getSExtValue(); 1672 // If it is known that the index is out of bounds, we can return 1673 // an undefined value. 1674 if (i < 0) 1675 return UndefinedVal(); 1676 1677 if (auto CAT = Ctx.getAsConstantArrayType(VD->getType())) 1678 if (CAT->getSize().sle(i)) 1679 return UndefinedVal(); 1680 1681 // If there is a list, but no init, it must be zero. 1682 if (i >= InitList->getNumInits()) 1683 return svalBuilder.makeZeroVal(R->getElementType()); 1684 1685 if (const Expr *ElemInit = InitList->getInit(i)) 1686 if (Optional<SVal> V = svalBuilder.getConstantVal(ElemInit)) 1687 return *V; 1688 } 1689 } 1690 } 1691 } 1692 } 1693 1694 // Check for loads from a code text region. For such loads, just give up. 1695 if (isa<CodeTextRegion>(superR)) 1696 return UnknownVal(); 1697 1698 // Handle the case where we are indexing into a larger scalar object. 1699 // For example, this handles: 1700 // int x = ... 1701 // char *y = &x; 1702 // return *y; 1703 // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1704 const RegionRawOffset &O = R->getAsArrayOffset(); 1705 1706 // If we cannot reason about the offset, return an unknown value. 1707 if (!O.getRegion()) 1708 return UnknownVal(); 1709 1710 if (const TypedValueRegion *baseR = 1711 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1712 QualType baseT = baseR->getValueType(); 1713 if (baseT->isScalarType()) { 1714 QualType elemT = R->getElementType(); 1715 if (elemT->isScalarType()) { 1716 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1717 if (const Optional<SVal> &V = B.getDirectBinding(superR)) { 1718 if (SymbolRef parentSym = V->getAsSymbol()) 1719 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1720 1721 if (V->isUnknownOrUndef()) 1722 return *V; 1723 // Other cases: give up. We are indexing into a larger object 1724 // that has some value, but we don't know how to handle that yet. 1725 return UnknownVal(); 1726 } 1727 } 1728 } 1729 } 1730 } 1731 return getBindingForFieldOrElementCommon(B, R, R->getElementType()); 1732 } 1733 1734 SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, 1735 const FieldRegion* R) { 1736 1737 // Check if the region has a binding. 1738 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1739 return *V; 1740 1741 // Is the field declared constant and has an in-class initializer? 1742 const FieldDecl *FD = R->getDecl(); 1743 QualType Ty = FD->getType(); 1744 if (Ty.isConstQualified()) 1745 if (const Expr *Init = FD->getInClassInitializer()) 1746 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 1747 return *V; 1748 1749 // If the containing record was initialized, try to get its constant value. 1750 const MemRegion* superR = R->getSuperRegion(); 1751 if (const auto *VR = dyn_cast<VarRegion>(superR)) { 1752 const VarDecl *VD = VR->getDecl(); 1753 QualType RecordVarTy = VD->getType(); 1754 unsigned Index = FD->getFieldIndex(); 1755 // Either the record variable or the field has an initializer that we can 1756 // trust. We trust initializers of constants and, additionally, respect 1757 // initializers of globals when analyzing main(). 1758 if (RecordVarTy.isConstQualified() || Ty.isConstQualified() || 1759 (B.isMainAnalysis() && VD->hasGlobalStorage())) 1760 if (const Expr *Init = VD->getAnyInitializer()) 1761 if (const auto *InitList = dyn_cast<InitListExpr>(Init)) { 1762 if (Index < InitList->getNumInits()) { 1763 if (const Expr *FieldInit = InitList->getInit(Index)) 1764 if (Optional<SVal> V = svalBuilder.getConstantVal(FieldInit)) 1765 return *V; 1766 } else { 1767 return svalBuilder.makeZeroVal(Ty); 1768 } 1769 } 1770 } 1771 1772 return getBindingForFieldOrElementCommon(B, R, Ty); 1773 } 1774 1775 Optional<SVal> 1776 RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 1777 const MemRegion *superR, 1778 const TypedValueRegion *R, 1779 QualType Ty) { 1780 1781 if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { 1782 const SVal &val = D.getValue(); 1783 if (SymbolRef parentSym = val.getAsSymbol()) 1784 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1785 1786 if (val.isZeroConstant()) 1787 return svalBuilder.makeZeroVal(Ty); 1788 1789 if (val.isUnknownOrUndef()) 1790 return val; 1791 1792 // Lazy bindings are usually handled through getExistingLazyBinding(). 1793 // We should unify these two code paths at some point. 1794 if (val.getAs<nonloc::LazyCompoundVal>() || 1795 val.getAs<nonloc::CompoundVal>()) 1796 return val; 1797 1798 llvm_unreachable("Unknown default value"); 1799 } 1800 1801 return None; 1802 } 1803 1804 SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, 1805 RegionBindingsRef LazyBinding) { 1806 SVal Result; 1807 if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) 1808 Result = getBindingForElement(LazyBinding, ER); 1809 else 1810 Result = getBindingForField(LazyBinding, 1811 cast<FieldRegion>(LazyBindingRegion)); 1812 1813 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1814 // default value for /part/ of an aggregate from a default value for the 1815 // /entire/ aggregate. The most common case of this is when struct Outer 1816 // has as its first member a struct Inner, which is copied in from a stack 1817 // variable. In this case, even if the Outer's default value is symbolic, 0, 1818 // or unknown, it gets overridden by the Inner's default value of undefined. 1819 // 1820 // This is a general problem -- if the Inner is zero-initialized, the Outer 1821 // will now look zero-initialized. The proper way to solve this is with a 1822 // new version of RegionStore that tracks the extent of a binding as well 1823 // as the offset. 1824 // 1825 // This hack only takes care of the undefined case because that can very 1826 // quickly result in a warning. 1827 if (Result.isUndef()) 1828 Result = UnknownVal(); 1829 1830 return Result; 1831 } 1832 1833 SVal 1834 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 1835 const TypedValueRegion *R, 1836 QualType Ty) { 1837 1838 // At this point we have already checked in either getBindingForElement or 1839 // getBindingForField if 'R' has a direct binding. 1840 1841 // Lazy binding? 1842 Store lazyBindingStore = nullptr; 1843 const SubRegion *lazyBindingRegion = nullptr; 1844 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); 1845 if (lazyBindingRegion) 1846 return getLazyBinding(lazyBindingRegion, 1847 getRegionBindings(lazyBindingStore)); 1848 1849 // Record whether or not we see a symbolic index. That can completely 1850 // be out of scope of our lookup. 1851 bool hasSymbolicIndex = false; 1852 1853 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1854 // default value for /part/ of an aggregate from a default value for the 1855 // /entire/ aggregate. The most common case of this is when struct Outer 1856 // has as its first member a struct Inner, which is copied in from a stack 1857 // variable. In this case, even if the Outer's default value is symbolic, 0, 1858 // or unknown, it gets overridden by the Inner's default value of undefined. 1859 // 1860 // This is a general problem -- if the Inner is zero-initialized, the Outer 1861 // will now look zero-initialized. The proper way to solve this is with a 1862 // new version of RegionStore that tracks the extent of a binding as well 1863 // as the offset. 1864 // 1865 // This hack only takes care of the undefined case because that can very 1866 // quickly result in a warning. 1867 bool hasPartialLazyBinding = false; 1868 1869 const SubRegion *SR = R; 1870 while (SR) { 1871 const MemRegion *Base = SR->getSuperRegion(); 1872 if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { 1873 if (D->getAs<nonloc::LazyCompoundVal>()) { 1874 hasPartialLazyBinding = true; 1875 break; 1876 } 1877 1878 return *D; 1879 } 1880 1881 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { 1882 NonLoc index = ER->getIndex(); 1883 if (!index.isConstant()) 1884 hasSymbolicIndex = true; 1885 } 1886 1887 // If our super region is a field or element itself, walk up the region 1888 // hierarchy to see if there is a default value installed in an ancestor. 1889 SR = dyn_cast<SubRegion>(Base); 1890 } 1891 1892 if (R->hasStackNonParametersStorage()) { 1893 if (isa<ElementRegion>(R)) { 1894 // Currently we don't reason specially about Clang-style vectors. Check 1895 // if superR is a vector and if so return Unknown. 1896 if (const TypedValueRegion *typedSuperR = 1897 dyn_cast<TypedValueRegion>(R->getSuperRegion())) { 1898 if (typedSuperR->getValueType()->isVectorType()) 1899 return UnknownVal(); 1900 } 1901 } 1902 1903 // FIXME: We also need to take ElementRegions with symbolic indexes into 1904 // account. This case handles both directly accessing an ElementRegion 1905 // with a symbolic offset, but also fields within an element with 1906 // a symbolic offset. 1907 if (hasSymbolicIndex) 1908 return UnknownVal(); 1909 1910 // Additionally allow introspection of a block's internal layout. 1911 if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) 1912 return UndefinedVal(); 1913 } 1914 1915 // All other values are symbolic. 1916 return svalBuilder.getRegionValueSymbolVal(R); 1917 } 1918 1919 SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, 1920 const ObjCIvarRegion* R) { 1921 // Check if the region has a binding. 1922 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1923 return *V; 1924 1925 const MemRegion *superR = R->getSuperRegion(); 1926 1927 // Check if the super region has a default binding. 1928 if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { 1929 if (SymbolRef parentSym = V->getAsSymbol()) 1930 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1931 1932 // Other cases: give up. 1933 return UnknownVal(); 1934 } 1935 1936 return getBindingForLazySymbol(R); 1937 } 1938 1939 SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, 1940 const VarRegion *R) { 1941 1942 // Check if the region has a binding. 1943 if (Optional<SVal> V = B.getDirectBinding(R)) 1944 return *V; 1945 1946 if (Optional<SVal> V = B.getDefaultBinding(R)) 1947 return *V; 1948 1949 // Lazily derive a value for the VarRegion. 1950 const VarDecl *VD = R->getDecl(); 1951 const MemSpaceRegion *MS = R->getMemorySpace(); 1952 1953 // Arguments are always symbolic. 1954 if (isa<StackArgumentsSpaceRegion>(MS)) 1955 return svalBuilder.getRegionValueSymbolVal(R); 1956 1957 // Is 'VD' declared constant? If so, retrieve the constant value. 1958 if (VD->getType().isConstQualified()) { 1959 if (const Expr *Init = VD->getAnyInitializer()) { 1960 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 1961 return *V; 1962 1963 // If the variable is const qualified and has an initializer but 1964 // we couldn't evaluate initializer to a value, treat the value as 1965 // unknown. 1966 return UnknownVal(); 1967 } 1968 } 1969 1970 // This must come after the check for constants because closure-captured 1971 // constant variables may appear in UnknownSpaceRegion. 1972 if (isa<UnknownSpaceRegion>(MS)) 1973 return svalBuilder.getRegionValueSymbolVal(R); 1974 1975 if (isa<GlobalsSpaceRegion>(MS)) { 1976 QualType T = VD->getType(); 1977 1978 // If we're in main(), then global initializers have not become stale yet. 1979 if (B.isMainAnalysis()) 1980 if (const Expr *Init = VD->getAnyInitializer()) 1981 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 1982 return *V; 1983 1984 // Function-scoped static variables are default-initialized to 0; if they 1985 // have an initializer, it would have been processed by now. 1986 // FIXME: This is only true when we're starting analysis from main(). 1987 // We're losing a lot of coverage here. 1988 if (isa<StaticGlobalSpaceRegion>(MS)) 1989 return svalBuilder.makeZeroVal(T); 1990 1991 if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { 1992 assert(!V->getAs<nonloc::LazyCompoundVal>()); 1993 return V.getValue(); 1994 } 1995 1996 return svalBuilder.getRegionValueSymbolVal(R); 1997 } 1998 1999 return UndefinedVal(); 2000 } 2001 2002 SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 2003 // All other values are symbolic. 2004 return svalBuilder.getRegionValueSymbolVal(R); 2005 } 2006 2007 const RegionStoreManager::SValListTy & 2008 RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { 2009 // First, check the cache. 2010 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); 2011 if (I != LazyBindingsMap.end()) 2012 return I->second; 2013 2014 // If we don't have a list of values cached, start constructing it. 2015 SValListTy List; 2016 2017 const SubRegion *LazyR = LCV.getRegion(); 2018 RegionBindingsRef B = getRegionBindings(LCV.getStore()); 2019 2020 // If this region had /no/ bindings at the time, there are no interesting 2021 // values to return. 2022 const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); 2023 if (!Cluster) 2024 return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); 2025 2026 SmallVector<BindingPair, 32> Bindings; 2027 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, 2028 /*IncludeAllDefaultBindings=*/true); 2029 for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 2030 E = Bindings.end(); 2031 I != E; ++I) { 2032 SVal V = I->second; 2033 if (V.isUnknownOrUndef() || V.isConstant()) 2034 continue; 2035 2036 if (Optional<nonloc::LazyCompoundVal> InnerLCV = 2037 V.getAs<nonloc::LazyCompoundVal>()) { 2038 const SValListTy &InnerList = getInterestingValues(*InnerLCV); 2039 List.insert(List.end(), InnerList.begin(), InnerList.end()); 2040 continue; 2041 } 2042 2043 List.push_back(V); 2044 } 2045 2046 return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); 2047 } 2048 2049 NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, 2050 const TypedValueRegion *R) { 2051 if (Optional<nonloc::LazyCompoundVal> V = 2052 getExistingLazyBinding(svalBuilder, B, R, false)) 2053 return *V; 2054 2055 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); 2056 } 2057 2058 static bool isRecordEmpty(const RecordDecl *RD) { 2059 if (!RD->field_empty()) 2060 return false; 2061 if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) 2062 return CRD->getNumBases() == 0; 2063 return true; 2064 } 2065 2066 SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, 2067 const TypedValueRegion *R) { 2068 const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 2069 if (!RD->getDefinition() || isRecordEmpty(RD)) 2070 return UnknownVal(); 2071 2072 return createLazyBinding(B, R); 2073 } 2074 2075 SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, 2076 const TypedValueRegion *R) { 2077 assert(Ctx.getAsConstantArrayType(R->getValueType()) && 2078 "Only constant array types can have compound bindings."); 2079 2080 return createLazyBinding(B, R); 2081 } 2082 2083 bool RegionStoreManager::includedInBindings(Store store, 2084 const MemRegion *region) const { 2085 RegionBindingsRef B = getRegionBindings(store); 2086 region = region->getBaseRegion(); 2087 2088 // Quick path: if the base is the head of a cluster, the region is live. 2089 if (B.lookup(region)) 2090 return true; 2091 2092 // Slow path: if the region is the VALUE of any binding, it is live. 2093 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 2094 const ClusterBindings &Cluster = RI.getData(); 2095 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 2096 CI != CE; ++CI) { 2097 const SVal &D = CI.getData(); 2098 if (const MemRegion *R = D.getAsRegion()) 2099 if (R->getBaseRegion() == region) 2100 return true; 2101 } 2102 } 2103 2104 return false; 2105 } 2106 2107 //===----------------------------------------------------------------------===// 2108 // Binding values to regions. 2109 //===----------------------------------------------------------------------===// 2110 2111 StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 2112 if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) 2113 if (const MemRegion* R = LV->getRegion()) 2114 return StoreRef(getRegionBindings(ST).removeBinding(R) 2115 .asImmutableMap() 2116 .getRootWithoutRetain(), 2117 *this); 2118 2119 return StoreRef(ST, *this); 2120 } 2121 2122 RegionBindingsRef 2123 RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { 2124 if (L.getAs<loc::ConcreteInt>()) 2125 return B; 2126 2127 // If we get here, the location should be a region. 2128 const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); 2129 2130 // Check if the region is a struct region. 2131 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 2132 QualType Ty = TR->getValueType(); 2133 if (Ty->isArrayType()) 2134 return bindArray(B, TR, V); 2135 if (Ty->isStructureOrClassType()) 2136 return bindStruct(B, TR, V); 2137 if (Ty->isVectorType()) 2138 return bindVector(B, TR, V); 2139 if (Ty->isUnionType()) 2140 return bindAggregate(B, TR, V); 2141 } 2142 2143 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 2144 // Binding directly to a symbolic region should be treated as binding 2145 // to element 0. 2146 QualType T = SR->getSymbol()->getType(); 2147 if (T->isAnyPointerType() || T->isReferenceType()) 2148 T = T->getPointeeType(); 2149 2150 R = GetElementZeroRegion(SR, T); 2151 } 2152 2153 assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) && 2154 "'this' pointer is not an l-value and is not assignable"); 2155 2156 // Clear out bindings that may overlap with this binding. 2157 RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); 2158 return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); 2159 } 2160 2161 RegionBindingsRef 2162 RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, 2163 const MemRegion *R, 2164 QualType T) { 2165 SVal V; 2166 2167 if (Loc::isLocType(T)) 2168 V = svalBuilder.makeNull(); 2169 else if (T->isIntegralOrEnumerationType()) 2170 V = svalBuilder.makeZeroVal(T); 2171 else if (T->isStructureOrClassType() || T->isArrayType()) { 2172 // Set the default value to a zero constant when it is a structure 2173 // or array. The type doesn't really matter. 2174 V = svalBuilder.makeZeroVal(Ctx.IntTy); 2175 } 2176 else { 2177 // We can't represent values of this type, but we still need to set a value 2178 // to record that the region has been initialized. 2179 // If this assertion ever fires, a new case should be added above -- we 2180 // should know how to default-initialize any value we can symbolicate. 2181 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 2182 V = UnknownVal(); 2183 } 2184 2185 return B.addBinding(R, BindingKey::Default, V); 2186 } 2187 2188 RegionBindingsRef 2189 RegionStoreManager::bindArray(RegionBindingsConstRef B, 2190 const TypedValueRegion* R, 2191 SVal Init) { 2192 2193 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 2194 QualType ElementTy = AT->getElementType(); 2195 Optional<uint64_t> Size; 2196 2197 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 2198 Size = CAT->getSize().getZExtValue(); 2199 2200 // Check if the init expr is a literal. If so, bind the rvalue instead. 2201 // FIXME: It's not responsibility of the Store to transform this lvalue 2202 // to rvalue. ExprEngine or maybe even CFG should do this before binding. 2203 if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { 2204 SVal V = getBinding(B.asStore(), *MRV, R->getValueType()); 2205 return bindAggregate(B, R, V); 2206 } 2207 2208 // Handle lazy compound values. 2209 if (Init.getAs<nonloc::LazyCompoundVal>()) 2210 return bindAggregate(B, R, Init); 2211 2212 if (Init.isUnknown()) 2213 return bindAggregate(B, R, UnknownVal()); 2214 2215 // Remaining case: explicit compound values. 2216 const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); 2217 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2218 uint64_t i = 0; 2219 2220 RegionBindingsRef NewB(B); 2221 2222 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 2223 // The init list might be shorter than the array length. 2224 if (VI == VE) 2225 break; 2226 2227 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 2228 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 2229 2230 if (ElementTy->isStructureOrClassType()) 2231 NewB = bindStruct(NewB, ER, *VI); 2232 else if (ElementTy->isArrayType()) 2233 NewB = bindArray(NewB, ER, *VI); 2234 else 2235 NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2236 } 2237 2238 // If the init list is shorter than the array length (or the array has 2239 // variable length), set the array default value. Values that are already set 2240 // are not overwritten. 2241 if (!Size.hasValue() || i < Size.getValue()) 2242 NewB = setImplicitDefaultValue(NewB, R, ElementTy); 2243 2244 return NewB; 2245 } 2246 2247 RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, 2248 const TypedValueRegion* R, 2249 SVal V) { 2250 QualType T = R->getValueType(); 2251 const VectorType *VT = T->castAs<VectorType>(); // Use castAs for typedefs. 2252 2253 // Handle lazy compound values and symbolic values. 2254 if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) 2255 return bindAggregate(B, R, V); 2256 2257 // We may get non-CompoundVal accidentally due to imprecise cast logic or 2258 // that we are binding symbolic struct value. Kill the field values, and if 2259 // the value is symbolic go and bind it as a "default" binding. 2260 if (!V.getAs<nonloc::CompoundVal>()) { 2261 return bindAggregate(B, R, UnknownVal()); 2262 } 2263 2264 QualType ElemType = VT->getElementType(); 2265 nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); 2266 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2267 unsigned index = 0, numElements = VT->getNumElements(); 2268 RegionBindingsRef NewB(B); 2269 2270 for ( ; index != numElements ; ++index) { 2271 if (VI == VE) 2272 break; 2273 2274 NonLoc Idx = svalBuilder.makeArrayIndex(index); 2275 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 2276 2277 if (ElemType->isArrayType()) 2278 NewB = bindArray(NewB, ER, *VI); 2279 else if (ElemType->isStructureOrClassType()) 2280 NewB = bindStruct(NewB, ER, *VI); 2281 else 2282 NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2283 } 2284 return NewB; 2285 } 2286 2287 Optional<RegionBindingsRef> 2288 RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, 2289 const TypedValueRegion *R, 2290 const RecordDecl *RD, 2291 nonloc::LazyCompoundVal LCV) { 2292 FieldVector Fields; 2293 2294 if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) 2295 if (Class->getNumBases() != 0 || Class->getNumVBases() != 0) 2296 return None; 2297 2298 for (const auto *FD : RD->fields()) { 2299 if (FD->isUnnamedBitfield()) 2300 continue; 2301 2302 // If there are too many fields, or if any of the fields are aggregates, 2303 // just use the LCV as a default binding. 2304 if (Fields.size() == SmallStructLimit) 2305 return None; 2306 2307 QualType Ty = FD->getType(); 2308 if (!(Ty->isScalarType() || Ty->isReferenceType())) 2309 return None; 2310 2311 Fields.push_back(FD); 2312 } 2313 2314 RegionBindingsRef NewB = B; 2315 2316 for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){ 2317 const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion()); 2318 SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR); 2319 2320 const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R); 2321 NewB = bind(NewB, loc::MemRegionVal(DestFR), V); 2322 } 2323 2324 return NewB; 2325 } 2326 2327 RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, 2328 const TypedValueRegion* R, 2329 SVal V) { 2330 if (!Features.supportsFields()) 2331 return B; 2332 2333 QualType T = R->getValueType(); 2334 assert(T->isStructureOrClassType()); 2335 2336 const RecordType* RT = T->castAs<RecordType>(); 2337 const RecordDecl *RD = RT->getDecl(); 2338 2339 if (!RD->isCompleteDefinition()) 2340 return B; 2341 2342 // Handle lazy compound values and symbolic values. 2343 if (Optional<nonloc::LazyCompoundVal> LCV = 2344 V.getAs<nonloc::LazyCompoundVal>()) { 2345 if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV)) 2346 return *NewB; 2347 return bindAggregate(B, R, V); 2348 } 2349 if (V.getAs<nonloc::SymbolVal>()) 2350 return bindAggregate(B, R, V); 2351 2352 // We may get non-CompoundVal accidentally due to imprecise cast logic or 2353 // that we are binding symbolic struct value. Kill the field values, and if 2354 // the value is symbolic go and bind it as a "default" binding. 2355 if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()) 2356 return bindAggregate(B, R, UnknownVal()); 2357 2358 // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable) 2359 // list of other values. It appears pretty much only when there's an actual 2360 // initializer list expression in the program, and the analyzer tries to 2361 // unwrap it as soon as possible. 2362 // This code is where such unwrap happens: when the compound value is put into 2363 // the object that it was supposed to initialize (it's an *initializer* list, 2364 // after all), instead of binding the whole value to the whole object, we bind 2365 // sub-values to sub-objects. Sub-values may themselves be compound values, 2366 // and in this case the procedure becomes recursive. 2367 // FIXME: The annoying part about compound values is that they don't carry 2368 // any sort of information about which value corresponds to which sub-object. 2369 // It's simply a list of values in the middle of nowhere; we expect to match 2370 // them to sub-objects, essentially, "by index": first value binds to 2371 // the first field, second value binds to the second field, etc. 2372 // It would have been much safer to organize non-lazy compound values as 2373 // a mapping from fields/bases to values. 2374 const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); 2375 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2376 2377 RegionBindingsRef NewB(B); 2378 2379 // In C++17 aggregates may have base classes, handle those as well. 2380 // They appear before fields in the initializer list / compound value. 2381 if (const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) { 2382 // If the object was constructed with a constructor, its value is a 2383 // LazyCompoundVal. If it's a raw CompoundVal, it means that we're 2384 // performing aggregate initialization. The only exception from this 2385 // rule is sending an Objective-C++ message that returns a C++ object 2386 // to a nil receiver; in this case the semantics is to return a 2387 // zero-initialized object even if it's a C++ object that doesn't have 2388 // this sort of constructor; the CompoundVal is empty in this case. 2389 assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) && 2390 "Non-aggregates are constructed with a constructor!"); 2391 2392 for (const auto &B : CRD->bases()) { 2393 // (Multiple inheritance is fine though.) 2394 assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!"); 2395 2396 if (VI == VE) 2397 break; 2398 2399 QualType BTy = B.getType(); 2400 assert(BTy->isStructureOrClassType() && "Base classes must be classes!"); 2401 2402 const CXXRecordDecl *BRD = BTy->getAsCXXRecordDecl(); 2403 assert(BRD && "Base classes must be C++ classes!"); 2404 2405 const CXXBaseObjectRegion *BR = 2406 MRMgr.getCXXBaseObjectRegion(BRD, R, /*IsVirtual=*/false); 2407 2408 NewB = bindStruct(NewB, BR, *VI); 2409 2410 ++VI; 2411 } 2412 } 2413 2414 RecordDecl::field_iterator FI, FE; 2415 2416 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 2417 2418 if (VI == VE) 2419 break; 2420 2421 // Skip any unnamed bitfields to stay in sync with the initializers. 2422 if (FI->isUnnamedBitfield()) 2423 continue; 2424 2425 QualType FTy = FI->getType(); 2426 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 2427 2428 if (FTy->isArrayType()) 2429 NewB = bindArray(NewB, FR, *VI); 2430 else if (FTy->isStructureOrClassType()) 2431 NewB = bindStruct(NewB, FR, *VI); 2432 else 2433 NewB = bind(NewB, loc::MemRegionVal(FR), *VI); 2434 ++VI; 2435 } 2436 2437 // There may be fewer values in the initialize list than the fields of struct. 2438 if (FI != FE) { 2439 NewB = NewB.addBinding(R, BindingKey::Default, 2440 svalBuilder.makeIntVal(0, false)); 2441 } 2442 2443 return NewB; 2444 } 2445 2446 RegionBindingsRef 2447 RegionStoreManager::bindAggregate(RegionBindingsConstRef B, 2448 const TypedRegion *R, 2449 SVal Val) { 2450 // Remove the old bindings, using 'R' as the root of all regions 2451 // we will invalidate. Then add the new binding. 2452 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); 2453 } 2454 2455 //===----------------------------------------------------------------------===// 2456 // State pruning. 2457 //===----------------------------------------------------------------------===// 2458 2459 namespace { 2460 class RemoveDeadBindingsWorker 2461 : public ClusterAnalysis<RemoveDeadBindingsWorker> { 2462 SmallVector<const SymbolicRegion *, 12> Postponed; 2463 SymbolReaper &SymReaper; 2464 const StackFrameContext *CurrentLCtx; 2465 2466 public: 2467 RemoveDeadBindingsWorker(RegionStoreManager &rm, 2468 ProgramStateManager &stateMgr, 2469 RegionBindingsRef b, SymbolReaper &symReaper, 2470 const StackFrameContext *LCtx) 2471 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b), 2472 SymReaper(symReaper), CurrentLCtx(LCtx) {} 2473 2474 // Called by ClusterAnalysis. 2475 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 2476 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 2477 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster; 2478 2479 using ClusterAnalysis::AddToWorkList; 2480 2481 bool AddToWorkList(const MemRegion *R); 2482 2483 bool UpdatePostponed(); 2484 void VisitBinding(SVal V); 2485 }; 2486 } 2487 2488 bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) { 2489 const MemRegion *BaseR = R->getBaseRegion(); 2490 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); 2491 } 2492 2493 void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 2494 const ClusterBindings &C) { 2495 2496 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 2497 if (SymReaper.isLive(VR)) 2498 AddToWorkList(baseR, &C); 2499 2500 return; 2501 } 2502 2503 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 2504 if (SymReaper.isLive(SR->getSymbol())) 2505 AddToWorkList(SR, &C); 2506 else 2507 Postponed.push_back(SR); 2508 2509 return; 2510 } 2511 2512 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 2513 AddToWorkList(baseR, &C); 2514 return; 2515 } 2516 2517 // CXXThisRegion in the current or parent location context is live. 2518 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 2519 const auto *StackReg = 2520 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 2521 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 2522 if (CurrentLCtx && 2523 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) 2524 AddToWorkList(TR, &C); 2525 } 2526 } 2527 2528 void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 2529 const ClusterBindings *C) { 2530 if (!C) 2531 return; 2532 2533 // Mark the symbol for any SymbolicRegion with live bindings as live itself. 2534 // This means we should continue to track that symbol. 2535 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 2536 SymReaper.markLive(SymR->getSymbol()); 2537 2538 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) { 2539 // Element index of a binding key is live. 2540 SymReaper.markElementIndicesLive(I.getKey().getRegion()); 2541 2542 VisitBinding(I.getData()); 2543 } 2544 } 2545 2546 void RemoveDeadBindingsWorker::VisitBinding(SVal V) { 2547 // Is it a LazyCompoundVal? All referenced regions are live as well. 2548 if (Optional<nonloc::LazyCompoundVal> LCS = 2549 V.getAs<nonloc::LazyCompoundVal>()) { 2550 2551 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 2552 2553 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 2554 E = Vals.end(); 2555 I != E; ++I) 2556 VisitBinding(*I); 2557 2558 return; 2559 } 2560 2561 // If V is a region, then add it to the worklist. 2562 if (const MemRegion *R = V.getAsRegion()) { 2563 AddToWorkList(R); 2564 SymReaper.markLive(R); 2565 2566 // All regions captured by a block are also live. 2567 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 2568 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 2569 E = BR->referenced_vars_end(); 2570 for ( ; I != E; ++I) 2571 AddToWorkList(I.getCapturedRegion()); 2572 } 2573 } 2574 2575 2576 // Update the set of live symbols. 2577 for (auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI) 2578 SymReaper.markLive(*SI); 2579 } 2580 2581 bool RemoveDeadBindingsWorker::UpdatePostponed() { 2582 // See if any postponed SymbolicRegions are actually live now, after 2583 // having done a scan. 2584 bool Changed = false; 2585 2586 for (auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I) { 2587 if (const SymbolicRegion *SR = *I) { 2588 if (SymReaper.isLive(SR->getSymbol())) { 2589 Changed |= AddToWorkList(SR); 2590 *I = nullptr; 2591 } 2592 } 2593 } 2594 2595 return Changed; 2596 } 2597 2598 StoreRef RegionStoreManager::removeDeadBindings(Store store, 2599 const StackFrameContext *LCtx, 2600 SymbolReaper& SymReaper) { 2601 RegionBindingsRef B = getRegionBindings(store); 2602 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 2603 W.GenerateClusters(); 2604 2605 // Enqueue the region roots onto the worklist. 2606 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2607 E = SymReaper.region_end(); I != E; ++I) { 2608 W.AddToWorkList(*I); 2609 } 2610 2611 do W.RunWorkList(); while (W.UpdatePostponed()); 2612 2613 // We have now scanned the store, marking reachable regions and symbols 2614 // as live. We now remove all the regions that are dead from the store 2615 // as well as update DSymbols with the set symbols that are now dead. 2616 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 2617 const MemRegion *Base = I.getKey(); 2618 2619 // If the cluster has been visited, we know the region has been marked. 2620 // Otherwise, remove the dead entry. 2621 if (!W.isVisited(Base)) 2622 B = B.remove(Base); 2623 } 2624 2625 return StoreRef(B.asStore(), *this); 2626 } 2627 2628 //===----------------------------------------------------------------------===// 2629 // Utility methods. 2630 //===----------------------------------------------------------------------===// 2631 2632 void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL, 2633 unsigned int Space, bool IsDot) const { 2634 RegionBindingsRef Bindings = getRegionBindings(S); 2635 2636 Indent(Out, Space, IsDot) << "\"store\": "; 2637 2638 if (Bindings.isEmpty()) { 2639 Out << "null," << NL; 2640 return; 2641 } 2642 2643 Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL; 2644 Bindings.printJson(Out, NL, Space + 1, IsDot); 2645 Indent(Out, Space, IsDot) << "]}," << NL; 2646 } 2647