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