1178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==// 2178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// 3178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// The LLVM Compiler Infrastructure 4178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// 5178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// This file is distributed under the University of Illinois Open Source 6178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// License. See LICENSE.TXT for details. 7178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// 8178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu//===----------------------------------------------------------------------===// 9178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// 10178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// This file defines a basic region store model. In this model, we do have field 11178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// sensitivity. But we assume nothing about the heap shape. So recursive data 12178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// structures are largely ignored. Basically we do 1-limiting analysis. 13178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// Parameter pointers are assumed with no aliasing. Pointee objects of 14178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// parameters are created lazily. 15178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu// 16178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu//===----------------------------------------------------------------------===// 173ed04d37573c566205d965d2e91d54ccae898d0aZhongxing Xu#include "clang/AST/CharUnits.h" 18c506357c3778092c2a3251243f12524e8eb89274Zhongxing Xu#include "clang/AST/DeclCXX.h" 19c506357c3778092c2a3251243f12524e8eb89274Zhongxing Xu#include "clang/AST/ExprCXX.h" 200a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose#include "clang/AST/CXXInheritance.h" 2166d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "clang/Analysis/Analyses/LiveVariables.h" 2266d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "clang/Analysis/AnalysisContext.h" 2366d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "clang/Basic/TargetInfo.h" 24f540c54701e3eeb34cb619a3a4eb18f1ac70ef2dJordan Rose#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 2518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 2618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 279b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 28dc0a25d9bff956cdbe54ea0bfc8fbbe3ceb4eb92Zhongxing Xu#include "llvm/ADT/ImmutableList.h" 2966d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "llvm/ADT/ImmutableMap.h" 3066d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "llvm/ADT/Optional.h" 31a071eb053aeeedc1c8128fd309b3a779b6c3152aZhongxing Xu#include "llvm/Support/raw_ostream.h" 32178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 33178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xuusing namespace clang; 349ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 3566d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenekusing llvm::Optional; 36178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 371c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 38e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek// Representation of binding keys. 391c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 401c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 4113d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xunamespace { 42e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekclass BindingKey { 4313d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xupublic: 44824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose enum Kind { Default = 0x0, Direct = 0x1 }; 4513d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xuprivate: 46824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose enum { Symbolic = 0x2 }; 47e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 48824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose llvm::PointerIntPair<const MemRegion *, 2> P; 49824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose uint64_t Data; 50e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 51824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose explicit BindingKey(const MemRegion *r, const MemRegion *Base, Kind k) 52824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { 53824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(r && Base && "Must have known regions."); 54824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); 55824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose } 56e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 57824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose : P(r, k), Data(offset) { 58824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(r && "Must have known regions."); 59824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(getOffset() == offset && "Failed to store offset"); 60d1a4f68a4301d1ee3098cc9db0cd507b96dd1beeBenjamin Kramer assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r)) && "Not a base"); 61824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose } 6213d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xupublic: 63e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 64824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose bool isDirect() const { return P.getInt() & Direct; } 65824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } 66e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 67e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek const MemRegion *getRegion() const { return P.getPointer(); } 68e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose uint64_t getOffset() const { 69e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose assert(!hasSymbolicOffset()); 70824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return Data; 71e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 72e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 73824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose const MemRegion *getConcreteOffsetRegion() const { 74824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(hasSymbolicOffset()); 75824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return reinterpret_cast<const MemRegion *>(static_cast<uintptr_t>(Data)); 76824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose } 77e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 781e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *getBaseRegion() const { 791e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (hasSymbolicOffset()) 801e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return getConcreteOffsetRegion()->getBaseRegion(); 811e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return getRegion()->getBaseRegion(); 821e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 831e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 8413d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu void Profile(llvm::FoldingSetNodeID& ID) const { 85e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek ID.AddPointer(P.getOpaqueValue()); 86824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose ID.AddInteger(Data); 8713d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu } 88e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 89e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek static BindingKey Make(const MemRegion *R, Kind k); 90e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 91e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek bool operator<(const BindingKey &X) const { 92e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek if (P.getOpaqueValue() < X.P.getOpaqueValue()) 93e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return true; 94e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek if (P.getOpaqueValue() > X.P.getOpaqueValue()) 95e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return false; 96824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return Data < X.Data; 97e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek } 98e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 99e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek bool operator==(const BindingKey &X) const { 100e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return P.getOpaqueValue() == X.P.getOpaqueValue() && 101824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose Data == X.Data; 1021c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek } 103e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose 1041e934431adba0f459668a59c6059b9596fd627b4Jordan Rose LLVM_ATTRIBUTE_USED void dump() const; 105e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek}; 1061c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} // end anonymous namespace 1071c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 108dc015e5398d3cdd7baaa5d9a0330aaeafdf1a7c3Zhongxing XuBindingKey BindingKey::Make(const MemRegion *R, Kind k) { 1094213e389d6f8fa96ab30eec0d932e4e3eee32997Ted Kremenek const RegionOffset &RO = R->getAsOffset(); 110824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose if (RO.hasSymbolicOffset()) 111824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return BindingKey(R, RO.getRegion(), k); 112e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 113824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return BindingKey(RO.getRegion(), RO.getOffset(), k); 114dc015e5398d3cdd7baaa5d9a0330aaeafdf1a7c3Zhongxing Xu} 115dc015e5398d3cdd7baaa5d9a0330aaeafdf1a7c3Zhongxing Xu 1161c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremeneknamespace llvm { 117e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek static inline 1189c378f705405d37f49795d5e915989de774fe11fTed Kremenek raw_ostream &operator<<(raw_ostream &os, BindingKey K) { 119e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose os << '(' << K.getRegion(); 120e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (!K.hasSymbolicOffset()) 121e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose os << ',' << K.getOffset(); 122e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose os << ',' << (K.isDirect() ? "direct" : "default") 123e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek << ')'; 1241c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek return os; 1251c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek } 1261c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} // end llvm namespace 1271c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 1281e934431adba0f459668a59c6059b9596fd627b4Jordan Rosevoid BindingKey::dump() const { 1291e934431adba0f459668a59c6059b9596fd627b4Jordan Rose llvm::errs() << *this; 1301e934431adba0f459668a59c6059b9596fd627b4Jordan Rose} 1311e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 1321c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 133baf03a7c0a846632396f9f5a19f6cd45bbe2b926Zhongxing Xu// Actual Store type. 1341c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 1351c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 1361e934431adba0f459668a59c6059b9596fd627b4Jordan Rosetypedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; 1371e934431adba0f459668a59c6059b9596fd627b4Jordan Rosetypedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> RegionBindings; 138baf03a7c0a846632396f9f5a19f6cd45bbe2b926Zhongxing Xu 13950dc1b3c851b5700ea32f81ed360586617e2c92fTed Kremenek//===----------------------------------------------------------------------===// 1409af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Fine-grained control of RegionStoreManager. 1419af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 1429af46f59242cfaec74fa491a66724970478263ebTed Kremenek 1439af46f59242cfaec74fa491a66724970478263ebTed Kremeneknamespace { 144ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamstruct minimal_features_tag {}; 145ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamstruct maximal_features_tag {}; 1461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 147ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass RegionStoreFeatures { 1489af46f59242cfaec74fa491a66724970478263ebTed Kremenek bool SupportsFields; 1499af46f59242cfaec74fa491a66724970478263ebTed Kremenekpublic: 1509af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures(minimal_features_tag) : 1510752d6d06721c55e5586cd2431d1239c0c8d27aeTed Kremenek SupportsFields(false) {} 1521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1539af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures(maximal_features_tag) : 1540752d6d06721c55e5586cd2431d1239c0c8d27aeTed Kremenek SupportsFields(true) {} 1551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1569af46f59242cfaec74fa491a66724970478263ebTed Kremenek void enableFields(bool t) { SupportsFields = t; } 1571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1589af46f59242cfaec74fa491a66724970478263ebTed Kremenek bool supportsFields() const { return SupportsFields; } 1599af46f59242cfaec74fa491a66724970478263ebTed Kremenek}; 1609af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 1619af46f59242cfaec74fa491a66724970478263ebTed Kremenek 1629af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 16350dc1b3c851b5700ea32f81ed360586617e2c92fTed Kremenek// Main RegionStore logic. 16450dc1b3c851b5700ea32f81ed360586617e2c92fTed Kremenek//===----------------------------------------------------------------------===// 165c48ea6e51dd0da0a3def87f148240718ffaaeb0dTed Kremenek 166178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xunamespace { 1671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 168ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass RegionStoreManager : public StoreManager { 1699af46f59242cfaec74fa491a66724970478263ebTed Kremenek const RegionStoreFeatures Features; 170451ac091cd1868433985396a25cbbf2092ae8ca9Ted Kremenek RegionBindings::Factory RBFactory; 1711e934431adba0f459668a59c6059b9596fd627b4Jordan Rose ClusterBindings::Factory CBFactory; 172e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 173178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xupublic: 17418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) 1751e934431adba0f459668a59c6059b9596fd627b4Jordan Rose : StoreManager(mgr), Features(f), 1761e934431adba0f459668a59c6059b9596fd627b4Jordan Rose RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()) {} 177178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 17813d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R); 179d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek /// getDefaultBinding - Returns an SVal* representing an optional default 180d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek /// binding associated with a region and its subregions. 18113d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R); 182e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 183027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek /// setImplicitDefaultValue - Set the default binding for the provided 184027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek /// MemRegion to the value implicitly defined for compound literals when 185e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek /// the value is not specified. 18677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef setImplicitDefaultValue(Store store, const MemRegion *R, QualType T); 1871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 188869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// ArrayToPointer - Emulates the "decay" of an array to a pointer 189869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// type. 'Array' represents the lvalue of the array being decayed 190869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// to a pointer, and the returned SVal represents the decayed 191869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// version of that lvalue (i.e., a pointer to the first element of 192d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// the array). This is called by ExprEngine when evaluating 193869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// casts from arrays to pointers. 194f1d537f460c529906c73de56d891046b45434fb3Zhongxing Xu SVal ArrayToPointer(Loc Array); 195b1d542a46eb71f23dafb5ce60b68247f280beb41Zhongxing Xu 1964fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it. 1974fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType); 1984fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu 199e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// \brief Evaluates C++ dynamic_cast cast. 200e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// The callback may result in the following 3 scenarios: 201e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// - Successful cast (ex: derived is subclass of base). 202e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// - Failed cast (ex: derived is definitely not a subclass of base). 203e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// - We don't know (base is a symbolic region and we don't have 204e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// enough info to determine if the cast will succeed at run time). 205e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// The function returns an SVal representing the derived class; it's 206e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks /// valid only if Failed flag is set to false. 207e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,bool &Failed); 208e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 20977a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef getInitialStore(const LocationContext *InitLoc) { 21077a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); 21117fd8632dcda97022a51effc24060eacdad9dbe0Zhongxing Xu } 21282cd37cf1cccde162d1f13eda6cdfe1398216f36Ted Kremenek 21367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===-------------------------------------------------------------------===// 21467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek // Binding values to regions. 21567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===-------------------------------------------------------------------===// 216eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks RegionBindings invalidateGlobalRegion(MemRegion::Kind K, 217eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks const Expr *Ex, 218eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks unsigned Count, 2193133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 220eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks RegionBindings B, 221eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks InvalidatedRegions *Invalidated); 2224193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu 223537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions, 22477a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const Expr *E, unsigned Count, 2253133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 22635bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek InvalidatedSymbols &IS, 227740d490593e0de8732a697c9f77b90ddd463863bJordan Rose const CallEvent *Call, 228537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose InvalidatedRegions *Invalidated); 2291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 230e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose bool scanReachableSymbols(Store S, const MemRegion *R, 231e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose ScanReachableSymbols &Callbacks); 232e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 233e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekpublic: // Made public for helper classes. 234e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 235e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose RegionBindings removeSubRegionBindings(RegionBindings B, const SubRegion *R); 2361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2373baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V); 238e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek 2393baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek RegionBindings addBinding(RegionBindings B, const MemRegion *R, 240e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek BindingKey::Kind k, SVal V); 241e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 2423baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek const SVal *lookup(RegionBindings B, BindingKey K); 2433baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k); 2441c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 2453baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek RegionBindings removeBinding(RegionBindings B, BindingKey K); 2463baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek RegionBindings removeBinding(RegionBindings B, const MemRegion *R, 24756a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek BindingKey::Kind k); 248e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 2493baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek RegionBindings removeBinding(RegionBindings B, const MemRegion *R) { 2503baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek return removeBinding(removeBinding(B, R, BindingKey::Direct), R, 2513baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek BindingKey::Default); 252e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek } 253e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek 2541e934431adba0f459668a59c6059b9596fd627b4Jordan Rose RegionBindings removeCluster(RegionBindings B, const MemRegion *R); 2551e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 256e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekpublic: // Part of public interface to class. 257e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek 25877a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef Bind(Store store, Loc LV, SVal V); 25953bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 26054460091f3987cda47a2604b07a9fb4642068ddaZhongxing Xu // BindDefault is only used to initialize a region with a default value. 26177a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef BindDefault(Store store, const MemRegion *R, SVal V) { 26254460091f3987cda47a2604b07a9fb4642068ddaZhongxing Xu RegionBindings B = GetRegionBindings(store); 2633baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek assert(!lookup(B, R, BindingKey::Default)); 2643baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek assert(!lookup(B, R, BindingKey::Direct)); 2651437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return StoreRef(addBinding(B, R, BindingKey::Default, V) 2661437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks .getRootWithoutRetain(), *this); 267a5ce966d1a23d84aa5e849cf0ed62494e736ea6aZhongxing Xu } 268a5ce966d1a23d84aa5e849cf0ed62494e736ea6aZhongxing Xu 2695be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// \brief Create a new store that binds a value to a compound literal. 2705be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// 2715be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// \param ST The original store whose bindings are the basis for the new 2725be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// store. 2735be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// 2745be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// \param CL The compound literal to bind (the binding key). 2755be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// 2765be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// \param LC The LocationContext for the binding. 2775be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// 2785be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek /// \param V The value to bind to the compound literal. 2795be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek StoreRef bindCompoundLiteral(Store ST, 2805be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek const CompoundLiteralExpr *CL, 28177a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const LocationContext *LC, SVal V); 2821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 28367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// BindStruct - Bind a compound value to a structure. 2849697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V); 2851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2868667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek /// BindVector - Bind a compound value to a vector. 2878667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek StoreRef BindVector(Store store, const TypedValueRegion* R, SVal V); 2888667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 2899697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V); 2901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2915ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose /// Clears out all bindings in the given region and assigns a new value 2925ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose /// as a Default binding. 2935ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose StoreRef BindAggregate(Store store, const TypedRegion *R, SVal DefaultVal); 29424194ef08ef3816d63686e2cac6d42795a015c68Zhongxing Xu 29556a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek /// \brief Create a new store with the specified binding removed. 296ad0fe03b897f9486191e75c8d90c3ffa9b4fd6a5Ted Kremenek /// \param ST the original store, that is the basis for the new store. 297ad0fe03b897f9486191e75c8d90c3ffa9b4fd6a5Ted Kremenek /// \param L the location whose binding should be removed. 298ad0fe03b897f9486191e75c8d90c3ffa9b4fd6a5Ted Kremenek StoreRef killBinding(Store ST, Loc L); 299e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 30077a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek void incrementReferenceCount(Store store) { 30177a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek GetRegionBindings(store).manualRetain(); 30277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek } 30377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek 30477a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek /// If the StoreManager supports it, decrement the reference count of 30577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek /// the specified Store object. If the reference count hits 0, the memory 30677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek /// associated with the object is recycled. 30777a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek void decrementReferenceCount(Store store) { 30877a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek GetRegionBindings(store).manualRelease(); 30977a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek } 310fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek 311fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek bool includedInBindings(Store store, const MemRegion *region) const; 31267f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek 3131437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// \brief Return the value bound to specified location in a given state. 3141437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// 31567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// The high level logic for this method is this: 3161437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// getBinding (L) 31767f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// if L has binding 31867f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return L's binding 31967f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// else if L is in killset 32067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return unknown 32167f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// else 32267f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// if L is on stack or heap 32367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return undefined 32467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// else 32567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return symbolic 3261437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBinding(Store store, Loc L, QualType T = QualType()); 327490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu 3281437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForElement(Store store, const ElementRegion *R); 329c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu 3301437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForField(Store store, const FieldRegion *R); 3311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3321437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForObjCIvar(Store store, const ObjCIvarRegion *R); 3331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3341437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForVar(Store store, const VarRegion *R); 3351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3361437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForLazySymbol(const TypedValueRegion *R); 3371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3381437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForFieldOrElementCommon(Store store, const TypedValueRegion *R, 3391437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType Ty, const MemRegion *superR); 340613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 3411437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getLazyBinding(const MemRegion *lazyBindingRegion, 3421437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks Store lazyBindingStore); 3431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3441437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// Get bindings for the values in a struct and return a CompoundVal, used 3451437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// when doing struct copy: 3461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump /// struct s x, y; 3470b242ecdd5755e8662386b528aa0a5153ec0121bZhongxing Xu /// x = y; 3480b242ecdd5755e8662386b528aa0a5153ec0121bZhongxing Xu /// y's value is retrieved by this method. 3491437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForStruct(Store store, const TypedValueRegion* R); 3501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3511437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForArray(Store store, const TypedValueRegion* R); 3521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 353dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek /// Used to lazily generate derived symbols for bindings that are defined 354dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek /// implicitly by default bindings in a super region. 3551437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks Optional<SVal> getBindingForDerivedDefaultValue(RegionBindings B, 3561437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const MemRegion *superR, 3571437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const TypedValueRegion *R, 3581437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType Ty); 359dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 360944ebc63c7b995864982366f31c07685d2aed509Zhongxing Xu /// Get the state and region whose binding this region R corresponds to. 361bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu std::pair<Store, const MemRegion*> 36245fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek GetLazyBinding(RegionBindings B, const MemRegion *R, 3638667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek const MemRegion *originalRegion, 3648667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek bool includeSuffix = false); 3651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 36667f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 36767f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek // State pruning. 36867f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 3691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 370db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 37167f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// It returns a new Store with these values removed. 37277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 373bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek SymbolReaper& SymReaper); 3747fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 37567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 37667f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek // Region "extents". 37767f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 3781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 37932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // FIXME: This method will soon be eliminated; see the note in Store.h. 3808bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, 3813ed04d37573c566205d965d2e91d54ccae898d0aZhongxing Xu const MemRegion* R, QualType EleTy); 38263123d8e48d47920f20eb277550ff40a92493e21Zhongxing Xu 38367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 3846e3f01cef27dd6cc7e36769618820c5b984f61daZhongxing Xu // Utility methods. 38567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 3861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 387451ac091cd1868433985396a25cbbf2092ae8ca9Ted Kremenek static inline RegionBindings GetRegionBindings(Store store) { 38813d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store)); 38967f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek } 39067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek 3919c378f705405d37f49795d5e915989de774fe11fTed Kremenek void print(Store store, raw_ostream &Out, const char* nl, 39253ba0b636194dbeaa65a6f85316c9397a0c5298bTed Kremenek const char *sep); 393a15f7ac7729b74d1d8bef0c009b803a4bbef20d3Zhongxing Xu 39467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek void iterBindings(Store store, BindingsHandler& f) { 3950e9910f8fe2600187e876adfb5d4b434100850e3Ted Kremenek RegionBindings B = GetRegionBindings(store); 3961e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { 3971e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = I.getData(); 3981e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 3991e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 4001e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const BindingKey &K = CI.getKey(); 4011e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!K.isDirect()) 4021e934431adba0f459668a59c6059b9596fd627b4Jordan Rose continue; 4031e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { 4041e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // FIXME: Possibly incorporate the offset? 4051e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!f.HandleBinding(*this, store, R, CI.getData())) 4061e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return; 4071e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 4080e9910f8fe2600187e876adfb5d4b434100850e3Ted Kremenek } 4090e9910f8fe2600187e876adfb5d4b434100850e3Ted Kremenek } 41067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek } 411178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu}; 412178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 413178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu} // end anonymous namespace 414178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 4159af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 4169af46f59242cfaec74fa491a66724970478263ebTed Kremenek// RegionStore creation. 4179af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 4189af46f59242cfaec74fa491a66724970478263ebTed Kremenek 41918c66fdc3c4008d335885695fe36fb5353c5f672Ted KremenekStoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) { 4209af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures F = maximal_features_tag(); 4219af46f59242cfaec74fa491a66724970478263ebTed Kremenek return new RegionStoreManager(StMgr, F); 4229af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 4239af46f59242cfaec74fa491a66724970478263ebTed Kremenek 4241437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksStoreManager * 4251437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaksento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { 4269af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures F = minimal_features_tag(); 4279af46f59242cfaec74fa491a66724970478263ebTed Kremenek F.enableFields(true); 4289af46f59242cfaec74fa491a66724970478263ebTed Kremenek return new RegionStoreManager(StMgr, F); 42995c7b00fe857a61a19185483aa0d85492ec9e258Ted Kremenek} 43095c7b00fe857a61a19185483aa0d85492ec9e258Ted Kremenek 431a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek 4329af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 433a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek// Region Cluster analysis. 434a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek//===----------------------------------------------------------------------===// 435a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 436a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremeneknamespace { 4375499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenektemplate <typename DERIVED> 438a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenekclass ClusterAnalysis { 439a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenekprotected: 4401e934431adba0f459668a59c6059b9596fd627b4Jordan Rose typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; 4411e934431adba0f459668a59c6059b9596fd627b4Jordan Rose typedef SmallVector<const MemRegion *, 10> WorkList; 4421e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 4431e934431adba0f459668a59c6059b9596fd627b4Jordan Rose llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; 4441e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 4455499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek WorkList WL; 446a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 447a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek RegionStoreManager &RM; 448a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek ASTContext &Ctx; 449c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SValBuilder &svalBuilder; 450a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 4515499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek RegionBindings B; 452d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek 453d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek const bool includeGlobals; 4545499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 4551e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *getCluster(const MemRegion *R) { 4561e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return B.lookup(R); 4571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 4581e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 459a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenekpublic: 46018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 461d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek RegionBindings b, const bool includeGlobals) 462c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek : RM(rm), Ctx(StateMgr.getContext()), 463c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek svalBuilder(StateMgr.getSValBuilder()), 464d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek B(b), includeGlobals(includeGlobals) {} 4655499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 4665499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek RegionBindings getRegionBindings() const { return B; } 4675499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 4685499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool isVisited(const MemRegion *R) { 4691e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return Visited.count(getCluster(R)); 4705499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 471a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 472d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek void GenerateClusters() { 4731e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Scan the entire set of bindings and record the region clusters. 4745499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 4751e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base = RI.getKey(); 4761e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 4771e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = RI.getData(); 4781e934431adba0f459668a59c6059b9596fd627b4Jordan Rose assert(!Cluster.isEmpty() && "Empty clusters should be removed"); 4791e934431adba0f459668a59c6059b9596fd627b4Jordan Rose static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); 4801e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 4811e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (includeGlobals) 4821e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (isa<NonStaticGlobalSpaceRegion>(Base->getMemorySpace())) 4831e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(Base, &Cluster); 4845499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 4855499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 4865499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 4871e934431adba0f459668a59c6059b9596fd627b4Jordan Rose bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) { 488ab9c04fda542d096c667d6a3746d94c884f80e7bTed Kremenek if (C && !Visited.insert(C)) 489ab9c04fda542d096c667d6a3746d94c884f80e7bTed Kremenek return false; 4901e934431adba0f459668a59c6059b9596fd627b4Jordan Rose WL.push_back(R); 4915499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return true; 492a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek } 493a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 4945499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool AddToWorkList(const MemRegion *R) { 4955499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const MemRegion *baseR = R->getBaseRegion(); 4965499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return AddToWorkList(baseR, getCluster(baseR)); 4975499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 4985499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 4995499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek void RunWorkList() { 5005499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek while (!WL.empty()) { 5011e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *baseR = WL.pop_back_val(); 5025499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 5031e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // First visit the cluster. 5041e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const ClusterBindings *Cluster = getCluster(baseR)) 5051e934431adba0f459668a59c6059b9596fd627b4Jordan Rose static_cast<DERIVED*>(this)->VisitCluster(baseR, *Cluster); 5065499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 5071e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Next, visit the base region. 50875a2d944fc4a398d226c32169fbe8efe8befd9c4Ted Kremenek static_cast<DERIVED*>(this)->VisitBaseRegion(baseR); 509a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek } 510a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek } 5115499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 5125499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenekpublic: 5131e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} 5141e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitCluster(const MemRegion *baseR, const ClusterBindings &C) {} 51575a2d944fc4a398d226c32169fbe8efe8befd9c4Ted Kremenek void VisitBaseRegion(const MemRegion *baseR) {} 5165499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek}; 517a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek} 518a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 519a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek//===----------------------------------------------------------------------===// 5201004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek// Binding invalidation. 5211004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek//===----------------------------------------------------------------------===// 5221004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek 523e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rosebool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, 524e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose ScanReachableSymbols &Callbacks) { 5251e934431adba0f459668a59c6059b9596fd627b4Jordan Rose assert(R == R->getBaseRegion() && "Should only be called for base regions"); 526e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose RegionBindings B = GetRegionBindings(S); 5271e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *Cluster = B.lookup(R); 5281e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 5291e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Cluster) 5301e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return true; 5311e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 5321e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); 5331e934431adba0f459668a59c6059b9596fd627b4Jordan Rose RI != RE; ++RI) { 5341e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Callbacks.scan(RI.getData())) 5351e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return false; 536e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 537a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 538e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose return true; 539e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose} 540e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 541e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan RoseRegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, 542e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const SubRegion *R) { 543e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose BindingKey SRKey = BindingKey::Make(R, BindingKey::Default); 5441e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *ClusterHead = SRKey.getBaseRegion(); 5451e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (R == ClusterHead) { 5461e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // We can remove an entire cluster's bindings all in one go. 5471e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.remove(B, R); 5481e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 5491e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 550e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (SRKey.hasSymbolicOffset()) { 551e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const SubRegion *Base = cast<SubRegion>(SRKey.getConcreteOffsetRegion()); 552e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose B = removeSubRegionBindings(B, Base); 553e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose return addBinding(B, Base, BindingKey::Default, UnknownVal()); 554e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 555e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 5561e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // This assumes the region being invalidated is char-aligned. This isn't 5571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // true for bitfields, but since bitfields have no subregions they shouldn't 5581e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // be using this function anyway. 559e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose uint64_t Length = UINT64_MAX; 560e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 561e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose SVal Extent = R->getExtent(svalBuilder); 562e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (nonloc::ConcreteInt *ExtentCI = dyn_cast<nonloc::ConcreteInt>(&Extent)) { 563e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 564e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 565e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // Extents are in bytes but region offsets are in bits. Be careful! 566e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose Length = ExtentInt.getLimitedValue() * Ctx.getCharWidth(); 567e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 568e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 5691e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *Cluster = B.lookup(ClusterHead); 5701e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Cluster) 5711e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return B; 5721e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 5731e934431adba0f459668a59c6059b9596fd627b4Jordan Rose ClusterBindings Result = *Cluster; 5741e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 575e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // It is safe to iterate over the bindings as they are being changed 576e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // because they are in an ImmutableMap. 5771e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator I = Cluster->begin(), E = Cluster->end(); 5781e934431adba0f459668a59c6059b9596fd627b4Jordan Rose I != E; ++I) { 5791e934431adba0f459668a59c6059b9596fd627b4Jordan Rose BindingKey NextKey = I.getKey(); 580e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (NextKey.getRegion() == SRKey.getRegion()) { 581e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (NextKey.getOffset() > SRKey.getOffset() && 5821e934431adba0f459668a59c6059b9596fd627b4Jordan Rose NextKey.getOffset() - SRKey.getOffset() < Length) { 5831e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 1: The next binding is inside the region we're invalidating. 5841e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Remove it. 5851e934431adba0f459668a59c6059b9596fd627b4Jordan Rose Result = CBFactory.remove(Result, NextKey); 5861e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } else if (NextKey.getOffset() == SRKey.getOffset()) { 5871e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 2: The next binding is at the same offset as the region we're 5881e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // invalidating. In this case, we need to leave default bindings alone, 5891e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // since they may be providing a default value for a regions beyond what 5901e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // we're invalidating. 5911e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // FIXME: This is probably incorrect; consider invalidating an outer 5921e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // struct whose first field is bound to a LazyCompoundVal. 593e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (NextKey.isDirect()) 5941e934431adba0f459668a59c6059b9596fd627b4Jordan Rose Result = CBFactory.remove(Result, NextKey); 5951e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 596e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } else if (NextKey.hasSymbolicOffset()) { 597e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 5981e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (R->isSubRegionOf(Base)) { 5991e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 3: The next key is symbolic and we just changed something within 6001e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // its concrete region. We don't know if the binding is still valid, so 6011e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // we'll be conservative and remove it. 6021e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (NextKey.isDirect()) 6031e934431adba0f459668a59c6059b9596fd627b4Jordan Rose Result = CBFactory.remove(Result, NextKey); 6041e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 6051e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 4: The next key is symbolic, but we changed a known 6061e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // super-region. In this case the binding is certainly no longer valid. 6071e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (R == Base || BaseSR->isSubRegionOf(R)) 6081e934431adba0f459668a59c6059b9596fd627b4Jordan Rose Result = CBFactory.remove(Result, NextKey); 6091e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 610e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 611e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 612e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 6131e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (Result.isEmpty()) 6141e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.remove(B, ClusterHead); 6151e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.add(B, ClusterHead, Result); 61619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek} 61719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek 618e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremeneknamespace { 6192534528c22260211a073e192c38d0db84c70c327Ted Kremenekclass invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> 6205499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek{ 6215499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const Expr *Ex; 6225499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek unsigned Count; 6233133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx; 62435bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek StoreManager::InvalidatedSymbols &IS; 625c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose StoreManager::InvalidatedRegions *Regions; 626e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekpublic: 6272534528c22260211a073e192c38d0db84c70c327Ted Kremenek invalidateRegionsWorker(RegionStoreManager &rm, 62818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramStateManager &stateMgr, 6295499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek RegionBindings b, 6305499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const Expr *ex, unsigned count, 6313133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *lctx, 63235bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek StoreManager::InvalidatedSymbols &is, 633d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek StoreManager::InvalidatedRegions *r, 634d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek bool includeGlobals) 6352534528c22260211a073e192c38d0db84c70c327Ted Kremenek : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals), 6363133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {} 637a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 6381e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); 63975a2d944fc4a398d226c32169fbe8efe8befd9c4Ted Kremenek void VisitBaseRegion(const MemRegion *baseR); 640a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 641e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekprivate: 642c1ddcabef0b0e1185b6ea35d64a1ff41dabd7626Ted Kremenek void VisitBinding(SVal V); 643a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek}; 6445b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek} 6455b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek 6462534528c22260211a073e192c38d0db84c70c327Ted Kremenekvoid invalidateRegionsWorker::VisitBinding(SVal V) { 647c1ddcabef0b0e1185b6ea35d64a1ff41dabd7626Ted Kremenek // A symbol? Mark it touched by the invalidation. 64835bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek if (SymbolRef Sym = V.getAsSymbol()) 64935bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek IS.insert(Sym); 650a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 65124c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek if (const MemRegion *R = V.getAsRegion()) { 65224c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek AddToWorkList(R); 65324c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek return; 65424c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek } 65524c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 65624c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek // Is it a LazyCompoundVal? All references get invalidated as well. 65724c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek if (const nonloc::LazyCompoundVal *LCS = 65824c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek dyn_cast<nonloc::LazyCompoundVal>(&V)) { 65924c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 66024c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek const MemRegion *LazyR = LCS->getRegion(); 66124c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); 66224c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 6631e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // FIXME: This should not have to walk all bindings in the old store. 66424c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 6651e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = RI.getData(); 6661e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 6671e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 6681e934431adba0f459668a59c6059b9596fd627b4Jordan Rose BindingKey K = CI.getKey(); 6691e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) { 6701e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (BaseR == LazyR) 6711e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(CI.getData()); 6721e934431adba0f459668a59c6059b9596fd627b4Jordan Rose else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR)) 6731e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(CI.getData()); 6741e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 6751e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 67624c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek } 67724c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 67824c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek return; 67924c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek } 68024c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek} 68124c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 6821e934431adba0f459668a59c6059b9596fd627b4Jordan Rosevoid invalidateRegionsWorker::VisitCluster(const MemRegion *BaseR, 6831e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &C) { 6841e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) 6851e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(I.getData()); 686a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 6871e934431adba0f459668a59c6059b9596fd627b4Jordan Rose B = RM.removeCluster(B, BaseR); 6885499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 6895b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek 6902534528c22260211a073e192c38d0db84c70c327Ted Kremenekvoid invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { 69135bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek // Symbolic region? Mark that symbol touched by the invalidation. 69235bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) 69335bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek IS.insert(SR->getSymbol()); 694a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 6955499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // BlockDataRegion? If so, invalidate captured variables that are passed 6965499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // by reference. 6975499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 6985499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek for (BlockDataRegion::referenced_vars_iterator 6995499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 7005499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek BI != BE; ++BI) { 7015499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const VarRegion *VR = *BI; 7025499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const VarDecl *VD = VR->getDecl(); 70385d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 7045499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek AddToWorkList(VR); 70585d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek } 70685d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek else if (Loc::isLocType(VR->getValueType())) { 70785d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // Map the current bindings to a Store to retrieve the value 70885d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // of the binding. If that binding itself is a region, we should 70985d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // invalidate that region. This is because a block may capture 71085d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // a pointer value, but the thing pointed by that pointer may 71185d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // get invalidated. 71285d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek Store store = B.getRootWithoutRetain(); 71385d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek SVal V = RM.getBinding(store, loc::MemRegionVal(VR)); 71485d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek if (const Loc *L = dyn_cast<Loc>(&V)) { 71585d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek if (const MemRegion *LR = L->getAsRegion()) 71685d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek AddToWorkList(LR); 71785d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek } 71885d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek } 7195b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek } 7205499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 7215499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 722a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 723c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose // Otherwise, we have a normal data region. Record that we touched the region. 724c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose if (Regions) 725c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose Regions->push_back(baseR); 726c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose 7275499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { 7285499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Invalidate the region by setting its default value to 7295499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // conjured symbol. The type of the symbol is irrelavant. 7303baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek DefinedOrUnknownSVal V = 7313b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 7323baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek B = RM.addBinding(B, baseR, BindingKey::Default, V); 7335499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 7345499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 735a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 7365499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (!baseR->isBoundable()) 7375499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 738a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 7399697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 740018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = TR->getValueType(); 741a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 742a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek // Invalidate the binding. 743bf1a66764a12f6cceb6ba8b349d4b74996e3786bTed Kremenek if (T->isStructureOrClassType()) { 7440b46b1bc647db68ed3511b53e96699cfe14658fdZhongxing Xu // Invalidate the region by setting its default value to 7450b46b1bc647db68ed3511b53e96699cfe14658fdZhongxing Xu // conjured symbol. The type of the symbol is irrelavant. 7463b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 7473b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek Ctx.IntTy, Count); 7483baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek B = RM.addBinding(B, baseR, BindingKey::Default, V); 7495499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 7505499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 7515b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek 7525499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 7535b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek // Set the default value of the array to conjured symbol. 7545499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek DefinedOrUnknownSVal V = 7553b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 7563133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek AT->getElementType(), Count); 7573baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek B = RM.addBinding(B, baseR, BindingKey::Default, V); 7585499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 7591004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek } 760c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek 761c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek if (includeGlobals && 762c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) { 763c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek // If the region is a global and we are invalidating all globals, 764c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek // just erase the entry. This causes all globals to be lazily 765c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek // symbolicated from the same base symbol. 7663baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek B = RM.removeBinding(B, baseR); 767c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek return; 768c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek } 769c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek 7701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7713b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 7723b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek T,Count); 7735499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 7743baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek B = RM.addBinding(B, baseR, BindingKey::Direct, V); 7751004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek} 7761004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek 777eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna ZaksRegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 778eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks const Expr *Ex, 779eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks unsigned Count, 7803133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 781eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks RegionBindings B, 782eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks InvalidatedRegions *Invalidated) { 783eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // Bind the globals memory space to a new symbol that we will use to derive 784eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // the bindings for all globals. 785eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 78631ba6135375433b617a8587ea6cc836a014ebd86Roman Divacky SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = */ (const void*) GS, Ex, LCtx, 7873b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek /* type does not matter */ Ctx.IntTy, 7883b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek Count); 789eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 790eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks B = removeBinding(B, GS); 791eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V); 792eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 793eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // Even if there are no bindings in the global scope, we still need to 794eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // record that we touched it. 795eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks if (Invalidated) 796eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks Invalidated->push_back(GS); 797eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 798eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks return B; 799eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks} 800eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 80177a4d5687c2cb3199c689892c9d040a94ff270afTed KremenekStoreRef RegionStoreManager::invalidateRegions(Store store, 802537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose ArrayRef<const MemRegion *> Regions, 80377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const Expr *Ex, unsigned Count, 8043133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 80535bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek InvalidatedSymbols &IS, 806740d490593e0de8732a697c9f77b90ddd463863bJordan Rose const CallEvent *Call, 807537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose InvalidatedRegions *Invalidated) { 8082534528c22260211a073e192c38d0db84c70c327Ted Kremenek invalidateRegionsWorker W(*this, StateMgr, 8095499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek RegionStoreManager::GetRegionBindings(store), 8103133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Ex, Count, LCtx, IS, Invalidated, false); 8115499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 8125499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Scan the bindings and generate the clusters. 813d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek W.GenerateClusters(); 8145499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 815537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose // Add the regions to the worklist. 816537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose for (ArrayRef<const MemRegion *>::iterator 817537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose I = Regions.begin(), E = Regions.end(); I != E; ++I) 8185499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.AddToWorkList(*I); 8195499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 8205499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.RunWorkList(); 8215499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 8225499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Return the new bindings. 823dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek RegionBindings B = W.getRegionBindings(); 824dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 825eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // For all globals which are not static nor immutable: determine which global 826eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // regions should be invalidated and invalidate them. 827eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // TODO: This could possibly be more precise with modules. 828eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // 829eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // System calls invalidate only system globals. 830eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks if (Call && Call->isInSystemHeader()) { 831eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 8323133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Ex, Count, LCtx, B, Invalidated); 833eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // Internal calls might invalidate both system and internal globals. 834eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks } else { 835eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 8363133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Ex, Count, LCtx, B, Invalidated); 837eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 8383133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Ex, Count, LCtx, B, Invalidated); 839dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek } 840dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 84177a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(B.getRootWithoutRetain(), *this); 842e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek} 843e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 8449af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 8459af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Extents for regions. 8469af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 8479af46f59242cfaec74fa491a66724970478263ebTed Kremenek 8481437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksDefinedOrUnknownSVal 8498bef8238181a30e52dea380789a7e2d760eac532Ted KremenekRegionStoreManager::getSizeInElements(ProgramStateRef state, 8501437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const MemRegion *R, 8511437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType EleTy) { 852c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder); 853846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size); 85432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (!SizeInt) 85532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return UnknownVal(); 8561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 85732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue()); 858555c77a27672186242019b38edac498ac9579b19Ted Kremenek 859555c77a27672186242019b38edac498ac9579b19Ted Kremenek if (Ctx.getAsVariableArrayType(EleTy)) { 860555c77a27672186242019b38edac498ac9579b19Ted Kremenek // FIXME: We need to track extra state to properly record the size 861555c77a27672186242019b38edac498ac9579b19Ted Kremenek // of VLAs. Returning UnknownVal here, however, is a stop-gap so that 862555c77a27672186242019b38edac498ac9579b19Ted Kremenek // we don't have a divide-by-zero below. 863555c77a27672186242019b38edac498ac9579b19Ted Kremenek return UnknownVal(); 864555c77a27672186242019b38edac498ac9579b19Ted Kremenek } 865555c77a27672186242019b38edac498ac9579b19Ted Kremenek 86657663fe6c3c7a0fb792626537c4f3f7d3594aa66Zhongxing Xu CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy); 8671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 86832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // If a variable is reinterpreted as a type that doesn't fit into a larger 86932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // type evenly, round it down. 87032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // This is a signed value, since it's used in arithmetic with signed indices. 871c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeIntVal(RegionSize / EleSize, false); 872e8a964bdb46349e4fa3433c8e5104d2a0f7f5c65Zhongxing Xu} 873e8a964bdb46349e4fa3433c8e5104d2a0f7f5c65Zhongxing Xu 8749af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 8759af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Location and region casting. 8769af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 8779af46f59242cfaec74fa491a66724970478263ebTed Kremenek 878869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// ArrayToPointer - Emulates the "decay" of an array to a pointer 879869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// type. 'Array' represents the lvalue of the array being decayed 880869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// to a pointer, and the returned SVal represents the decayed 881869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// version of that lvalue (i.e., a pointer to the first element of 882d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// the array). This is called by ExprEngine when evaluating casts 883869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// from arrays to pointers. 884f1d537f460c529906c73de56d891046b45434fb3Zhongxing XuSVal RegionStoreManager::ArrayToPointer(Loc Array) { 885abb042f33ea8e6107a7dc8efc51d2ace329f9f48Ted Kremenek if (!isa<loc::MemRegionVal>(Array)) 886abb042f33ea8e6107a7dc8efc51d2ace329f9f48Ted Kremenek return UnknownVal(); 8871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 888abb042f33ea8e6107a7dc8efc51d2ace329f9f48Ted Kremenek const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion(); 8899697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R); 8901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 891bbee1a790f77b42a0bcd79bdd3d367e46042db67Ted Kremenek if (!ArrayR) 892abb042f33ea8e6107a7dc8efc51d2ace329f9f48Ted Kremenek return UnknownVal(); 8931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8945b8c69494881b7d35bc6244b4a19be0cc2eab368Jordan Rose // Strip off typedefs from the ArrayRegion's ValueType. 8955b8c69494881b7d35bc6244b4a19be0cc2eab368Jordan Rose QualType T = ArrayR->getValueType().getDesugaredType(Ctx); 8965b8c69494881b7d35bc6244b4a19be0cc2eab368Jordan Rose const ArrayType *AT = cast<ArrayType>(T); 8975b8c69494881b7d35bc6244b4a19be0cc2eab368Jordan Rose T = AT->getElementType(); 8981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 899c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 90057663fe6c3c7a0fb792626537c4f3f7d3594aa66Zhongxing Xu return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); 901b1d542a46eb71f23dafb5ce60b68247f280beb41Zhongxing Xu} 902b1d542a46eb71f23dafb5ce60b68247f280beb41Zhongxing Xu 90321625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek// This mirrors Type::getCXXRecordDeclForPointerType(), but there doesn't 90421625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek// appear to be another need for this in the rest of the codebase. 90521625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenekstatic const CXXRecordDecl *GetCXXRecordDeclForReferenceType(QualType Ty) { 90621625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek if (const ReferenceType *RT = Ty->getAs<ReferenceType>()) 90721625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek if (const RecordType *RCT = RT->getPointeeType()->getAs<RecordType>()) 90821625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek return dyn_cast<CXXRecordDecl>(RCT->getDecl()); 90921625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek return 0; 91021625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek} 91121625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek 912eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing XuSVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) { 913eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu const CXXRecordDecl *baseDecl; 91421625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek 915eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu if (baseType->isPointerType()) 916eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu baseDecl = baseType->getCXXRecordDeclForPointerType(); 91721625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek else if (baseType->isReferenceType()) 91821625c69e88d232e71a3bd4ba9d4bbb484183bf1Ted Kremenek baseDecl = GetCXXRecordDeclForReferenceType(baseType); 919eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu else 920eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu baseDecl = baseType->getAsCXXRecordDecl(); 921eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu 9224fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu assert(baseDecl && "not a CXXRecordDecl?"); 923eee1df1e7ac74bbccd5282f0348381af70cf5e5eZhongxing Xu 9243e310d33e4b3b2094df11b25eabde2caab610a94Zhongxing Xu loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived); 9253e310d33e4b3b2094df11b25eabde2caab610a94Zhongxing Xu if (!derivedRegVal) 9263e310d33e4b3b2094df11b25eabde2caab610a94Zhongxing Xu return derived; 9273e310d33e4b3b2094df11b25eabde2caab610a94Zhongxing Xu 9284fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu const MemRegion *baseReg = 929d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion()); 930d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu 9314fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu return loc::MemRegionVal(baseReg); 9324fd56816e0925c04f2c92e75399f5c9018d5d6fbZhongxing Xu} 93394aa6c16e7404b2ff83a6f0ae7db8a758d389fc4Zhongxing Xu 934e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna ZaksSVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType, 935e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks bool &Failed) { 936e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks Failed = false; 937e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 938e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base); 939e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks if (!baseRegVal) 940e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return UnknownVal(); 941b11a3ada9a22e146c6edd33bcc6301e221fedd7aJordan Rose const MemRegion *BaseRegion = baseRegVal->stripCasts(/*StripBases=*/false); 942e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 943a2c8d2edfff1573450c6feba876830dd746ffaadAnna Zaks // Assume the derived class is a pointer or a reference to a CXX record. 944e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks derivedType = derivedType->getPointeeType(); 945e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks assert(!derivedType.isNull()); 946e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl(); 947e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks if (!DerivedDecl && !derivedType->isVoidType()) 948e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return UnknownVal(); 949e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 950e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // Drill down the CXXBaseObject chains, which represent upcasts (casts from 951e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // derived to base). 952e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks const MemRegion *SR = BaseRegion; 953e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { 954e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks QualType BaseType = TSR->getLocationType()->getPointeeType(); 955e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks assert(!BaseType.isNull()); 956e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); 957e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks if (!SRDecl) 958e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return UnknownVal(); 959e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 960e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // If found the derived class, the cast succeeds. 961e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks if (SRDecl == DerivedDecl) 962e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return loc::MemRegionVal(TSR); 963e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 964b11a3ada9a22e146c6edd33bcc6301e221fedd7aJordan Rose if (!derivedType->isVoidType()) { 965b11a3ada9a22e146c6edd33bcc6301e221fedd7aJordan Rose // Static upcasts are marked as DerivedToBase casts by Sema, so this will 966b11a3ada9a22e146c6edd33bcc6301e221fedd7aJordan Rose // only happen when multiple or virtual inheritance is involved. 9670a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, 9680a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose /*DetectVirtual=*/false); 9690a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose if (SRDecl->isDerivedFrom(DerivedDecl, Paths)) { 9700a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose SVal Result = loc::MemRegionVal(TSR); 9710a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose const CXXBasePath &Path = *Paths.begin(); 9720a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose for (CXXBasePath::const_iterator I = Path.begin(), E = Path.end(); 9730a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose I != E; ++I) { 9740a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose Result = evalDerivedToBase(Result, I->Base->getType()); 9750a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose } 9760a5629812019ce8bef86ade5425ac261bb544fd8Jordan Rose return Result; 977b11a3ada9a22e146c6edd33bcc6301e221fedd7aJordan Rose } 978e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks } 979e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 980e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) 981e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // Drill down the chain to get the derived classes. 982e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks SR = R->getSuperRegion(); 983e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks else { 984e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // We reached the bottom of the hierarchy. 985e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 986e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // If this is a cast to void*, return the region. 987e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks if (derivedType->isVoidType()) 988e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return loc::MemRegionVal(TSR); 989e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 990e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // We did not find the derived class. We we must be casting the base to 991e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks // derived, so the cast should fail. 992e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks Failed = true; 993e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return UnknownVal(); 994e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks } 995e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks } 996e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 997e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks return UnknownVal(); 998e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks} 999e19f86edab8fb3c2c1e99e0e9815b6058504df9bAnna Zaks 10009af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 10019af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Loading values from regions. 10029af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 10039af46f59242cfaec74fa491a66724970478263ebTed Kremenek 1004e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed KremenekOptional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B, 1005bdfa85fd5351d24bc42ce21a97d2fb8486df22b1Zhongxing Xu const MemRegion *R) { 100642c67bfedb0b3a998d46d3868208bdd9a4da520aZhongxing Xu 10073baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek if (const SVal *V = lookup(B, R, BindingKey::Direct)) 100842c67bfedb0b3a998d46d3868208bdd9a4da520aZhongxing Xu return *V; 1009e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek 101013d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu return Optional<SVal>(); 101113d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu} 101213d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu 101313d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing XuOptional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B, 1014d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek const MemRegion *R) { 1015d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek if (R->isBoundable()) 10169697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) 1017018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu if (TR->getValueType()->isUnionType()) 1018d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek return UnknownVal(); 1019d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek 10203baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek if (const SVal *V = lookup(B, R, BindingKey::Default)) 1021e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return *V; 102213d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu 102313d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu return Optional<SVal>(); 102413d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu} 102513d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu 10261437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { 102753bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu assert(!isa<UnknownVal>(L) && "location unknown"); 102853bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu assert(!isa<UndefinedVal>(L) && "location undefined"); 1029e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 103029836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // For access to concrete addresses, return UnknownVal. Checks 103129836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // for null dereferences (and similar errors) are done by checkers, not 103229836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // the Store. 103329836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // FIXME: We can consider lazily symbolicating such memory, but we really 103429836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // should defer this when we can reason easily about symbolicating arrays 103529836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // of bytes. 103629836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek if (isa<loc::ConcreteInt>(L)) { 103729836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek return UnknownVal(); 103829836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek } 103914429b918bd2f4cb52abc75546a7fe37142054caArgyrios Kyrtzidis if (!isa<loc::MemRegionVal>(L)) { 104014429b918bd2f4cb52abc75546a7fe37142054caArgyrios Kyrtzidis return UnknownVal(); 104114429b918bd2f4cb52abc75546a7fe37142054caArgyrios Kyrtzidis } 1042e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 104367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); 1044a1718c78770db93d1b762620f07728a56786f2aeZhongxing Xu 1045214323b78b01ef9c1ad226f0eb5bd1187f3efa70Ted Kremenek if (isa<AllocaRegion>(MR) || 1046214323b78b01ef9c1ad226f0eb5bd1187f3efa70Ted Kremenek isa<SymbolicRegion>(MR) || 1047214323b78b01ef9c1ad226f0eb5bd1187f3efa70Ted Kremenek isa<CodeTextRegion>(MR)) { 10487b050306b0ba3e7e564126fb12aca64b4c0b3f54Tom Care if (T.isNull()) { 1049ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1050ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks T = TR->getLocationType(); 1051ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks else { 1052ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks const SymbolicRegion *SR = cast<SymbolicRegion>(MR); 1053ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks T = SR->getSymbol()->getType(Ctx); 1054ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks } 10557b050306b0ba3e7e564126fb12aca64b4c0b3f54Tom Care } 105681491854222ad25953a643ce8efa0d6ea295ccfeZhongxing Xu MR = GetElementZeroRegion(MR, T); 10577b050306b0ba3e7e564126fb12aca64b4c0b3f54Tom Care } 10581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1059869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1060869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // instead of 'Loc', and have the other Loc cases handled at a higher level. 10619697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1062018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType RTy = R->getValueType(); 106353bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 1064869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // FIXME: We should eventually handle funny addressing. e.g.: 1065869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // 1066869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // int x = ...; 1067869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // int *p = &x; 1068869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // char *q = (char*) p; 1069869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // char c = *q; // returns the first byte of 'x'. 1070869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // 1071869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // Such funny addressing will occur due to layering of regions. 1072869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek 1073fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor if (RTy->isStructureOrClassType()) 10741437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForStruct(store, R); 10751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1076d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek // FIXME: Handle unions. 1077d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek if (RTy->isUnionType()) 1078c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return UnknownVal(); 10793e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu 10809955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose if (RTy->isArrayType()) { 10819955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose if (RTy->isConstantArrayType()) 10829955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose return getBindingForArray(store, R); 10839955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose else 10849955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose return UnknownVal(); 10859955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose } 10863e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu 10871038f9f69978ea99efccdda01f66215a1c56dc55Zhongxing Xu // FIXME: handle Vector types. 10881038f9f69978ea99efccdda01f66215a1c56dc55Zhongxing Xu if (RTy->isVectorType()) 1089c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return UnknownVal(); 109099c2030f917a76b792848e37d635067c902f96b2Zhongxing Xu 109199c2030f917a76b792848e37d635067c902f96b2Zhongxing Xu if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 10921437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return CastRetrievedVal(getBindingForField(store, FR), FR, T, false); 1093c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 1094c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1095c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Here we actually perform an implicit conversion from the loaded 1096c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // value to the element type. Eventually we want to compose these values 1097c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // more intelligently. For example, an 'element' can encompass multiple 1098c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // bound regions (e.g., several bound bytes), or could be a subset of 1099c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // a larger value. 11001437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return CastRetrievedVal(getBindingForElement(store, ER), ER, T, false); 1101e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek } 1102c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 1103c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1104c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Here we actually perform an implicit conversion from the loaded 1105c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // value to the ivar type. What we should model is stores to ivars 1106c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // that blow past the extent of the ivar. If the address of the ivar is 1107c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // reinterpretted, it is possible we stored a different value that could 1108c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // fit within the ivar. Either we need to cast these when storing them 1109c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // or reinterpret them lazily (as we do here). 11101437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return CastRetrievedVal(getBindingForObjCIvar(store, IVR), IVR, T, false); 1111c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek } 11121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1113c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1114c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Here we actually perform an implicit conversion from the loaded 1115c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // value to the variable type. What we should model is stores to variables 1116c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // that blow past the extent of the variable. If the address of the 1117c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // variable is reinterpretted, it is possible we stored a different value 1118c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // that could fit within the variable. Either we need to cast these when 1119e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek // storing them or reinterpret them lazily (as we do here). 11201437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return CastRetrievedVal(getBindingForVar(store, VR), VR, T, false); 1121c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek } 112225c545788da6e3a725206cfa378b9b83a7da6024Ted Kremenek 1123576bb92057979b14ca04b3080a9405662d0217a3Zhongxing Xu RegionBindings B = GetRegionBindings(store); 11243baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek const SVal *V = lookup(B, R, BindingKey::Direct); 112553bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 11264193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu // Check if the region has a binding. 11274193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu if (V) 1128c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return *V; 1129869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek 1130869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // The location does not have a bound value. This means that it has 1131869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // the value it had upon its creation and/or entry to the analyzed 1132869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // function/method. These are either symbolic values or 'undefined'. 1133de0d26310191215a6d1d189dc419f87af18ce6beTed Kremenek if (R->hasStackNonParametersStorage()) { 1134869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // All stack variables are considered to have undefined values 1135869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // upon creation. All heap allocated blocks are considered to 1136869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // have undefined values as well unless they are explicitly bound 1137869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // to specific values. 1138c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return UndefinedVal(); 1139869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek } 1140869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek 1141bb2b433ae14ca18e88a46032096ce5ec5c05c8e7Ted Kremenek // All other values are symbolic. 1142c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 114353bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu} 11441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1145bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xustd::pair<Store, const MemRegion *> 114645fa623886dfb6a23b3cfd6d8764e05884382180Ted KremenekRegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R, 11478667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek const MemRegion *originalRegion, 11488667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek bool includeSuffix) { 114945fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek 115045fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek if (originalRegion != R) { 115145fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek if (Optional<SVal> OV = getDefaultBinding(B, R)) { 115245fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek if (const nonloc::LazyCompoundVal *V = 115345fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer())) 115445fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek return std::make_pair(V->getStore(), V->getRegion()); 115545fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek } 115645fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek } 115745fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek 1158a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1159bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu const std::pair<Store, const MemRegion *> &X = 116045fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek GetLazyBinding(B, ER->getSuperRegion(), originalRegion); 11611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 11628ec4aac6d3dee698e4cb7b9f540d962e4ccab468Ted Kremenek if (X.second) 1163a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek return std::make_pair(X.first, 1164a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek MRMgr.getElementRegionWithSuper(ER, X.second)); 11651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 1166a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1167bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu const std::pair<Store, const MemRegion *> &X = 116845fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek GetLazyBinding(B, FR->getSuperRegion(), originalRegion); 11691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 11708667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (X.second) { 11718667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (includeSuffix) 11728667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek return std::make_pair(X.first, 11738667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek MRMgr.getFieldRegionWithSuper(FR, X.second)); 11748667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek return X; 11758667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 11768667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 1177a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek } 1178d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu // C++ base object region is another kind of region that we should blast 1179d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu // through to look for lazy compound value. It is like a field region. 1180d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu else if (const CXXBaseObjectRegion *baseReg = 1181d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu dyn_cast<CXXBaseObjectRegion>(R)) { 1182d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu const std::pair<Store, const MemRegion *> &X = 118345fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek GetLazyBinding(B, baseReg->getSuperRegion(), originalRegion); 1184d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu 11858667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (X.second) { 11868667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (includeSuffix) 11878667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek return std::make_pair(X.first, 11888667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek MRMgr.getCXXBaseObjectRegionWithSuper(baseReg, 11898667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek X.second)); 11908667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek return X; 11918667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 1192d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu } 1193613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 1194e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is 1195dcbcbdcff8b8d9c19e98c21477fce224c92ce8c4Zhongxing Xu // possible for a valid lazy binding. 1196bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu return std::make_pair((Store) 0, (const MemRegion *) 0); 1197a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek} 119853bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 11991437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForElement(Store store, 1200a8f2362307b436023095e66efd678ae591c02184Anna Zaks const ElementRegion* R) { 1201a8f2362307b436023095e66efd678ae591c02184Anna Zaks // We do not currently model bindings of the CompoundLiteralregion. 120250b5a5c32e07301e4edcc01aca1f8a49a128c66cAnna Zaks if (isa<CompoundLiteralRegion>(R->getBaseRegion())) 120350b5a5c32e07301e4edcc01aca1f8a49a128c66cAnna Zaks return UnknownVal(); 1204a8f2362307b436023095e66efd678ae591c02184Anna Zaks 1205c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu // Check if the region has a binding. 1206bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu RegionBindings B = GetRegionBindings(store); 12072cf073b7686a05bc0f637862bdc06f71232db954Ted Kremenek if (const Optional<SVal> &V = getDirectBinding(B, R)) 1208c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu return *V; 1209c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu 1210921109ab9c4a114da4588566bc56c09443ea2339Ted Kremenek const MemRegion* superR = R->getSuperRegion(); 1211921109ab9c4a114da4588566bc56c09443ea2339Ted Kremenek 1212c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu // Check if the region is an element region of a string literal. 1213921109ab9c4a114da4588566bc56c09443ea2339Ted Kremenek if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { 1214e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek // FIXME: Handle loads from strings where the literal is treated as 121595efe0f7fb2ff2d83f9e6f97d707a79370034d73Ted Kremenek // an integer, e.g., *((unsigned int*)"hello") 1216018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 121795efe0f7fb2ff2d83f9e6f97d707a79370034d73Ted Kremenek if (T != Ctx.getCanonicalType(R->getElementType())) 121895efe0f7fb2ff2d83f9e6f97d707a79370034d73Ted Kremenek return UnknownVal(); 1219e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1220c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu const StringLiteral *Str = StrR->getStringLiteral(); 1221c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu SVal Idx = R->getIndex(); 1222c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) { 1223c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu int64_t i = CI->getValue().getSExtValue(); 122431d922fdbf52ea14856f395cb1079173b33cefcdTed Kremenek // Abort on string underrun. This can be possible by arbitrary 12251437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks // clients of getBindingForElement(). 122631d922fdbf52ea14856f395cb1079173b33cefcdTed Kremenek if (i < 0) 122731d922fdbf52ea14856f395cb1079173b33cefcdTed Kremenek return UndefinedVal(); 1228729aa06b9d190ce01eccb7108415e698fc52f6f4Ted Kremenek int64_t length = Str->getLength(); 1229729aa06b9d190ce01eccb7108415e698fc52f6f4Ted Kremenek // Technically, only i == length is guaranteed to be null. 1230167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // However, such overflows should be caught before reaching this point; 1231167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // the only time such an access would be made is if a string literal was 1232167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // used to initialize a larger array. 1233729aa06b9d190ce01eccb7108415e698fc52f6f4Ted Kremenek char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1234c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeIntVal(c, T); 1235c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu } 1236c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu } 12371e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek 12381e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek // Check for loads from a code text region. For such loads, just give up. 123908140f99e507cfd593146bdf2efb01b24da822faTed Kremenek if (isa<CodeTextRegion>(superR)) 12401e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek return UnknownVal(); 12411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1242a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // Handle the case where we are indexing into a larger scalar object. 1243a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // For example, this handles: 1244a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // int x = ... 1245a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // char *y = &x; 1246a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // return *y; 1247a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // FIXME: This is a hack, and doesn't do anything really intelligent yet. 12487caf9b369cba6edaf6eac25121cbc65ee938f14dZhongxing Xu const RegionRawOffset &O = R->getAsArrayOffset(); 1249c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek 1250c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek // If we cannot reason about the offset, return an unknown value. 1251c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek if (!O.getRegion()) 1252c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek return UnknownVal(); 1253c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek 12549697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *baseR = 12559697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1256018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType baseT = baseR->getValueType(); 1257a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (baseT->isScalarType()) { 1258a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek QualType elemT = R->getElementType(); 1259a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (elemT->isScalarType()) { 1260a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1261a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (const Optional<SVal> &V = getDirectBinding(B, superR)) { 1262a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (SymbolRef parentSym = V->getAsSymbol()) 1263c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1264dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1265a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (V->isUnknownOrUndef()) 1266a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek return *V; 1267a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // Other cases: give up. We are indexing into a larger object 1268a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // that has some value, but we don't know how to handle that yet. 1269a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek return UnknownVal(); 1270a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek } 1271a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek } 1272a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek } 1273566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek } 12747abe019c2840e3890993c879c65acde9ea316166Zhongxing Xu } 12751437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForFieldOrElementCommon(store, R, R->getElementType(), 12761437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks superR); 1277c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu} 1278c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu 12791437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForField(Store store, 1280490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu const FieldRegion* R) { 1281490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu 1282490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu // Check if the region has a binding. 1283bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu RegionBindings B = GetRegionBindings(store); 12842cf073b7686a05bc0f637862bdc06f71232db954Ted Kremenek if (const Optional<SVal> &V = getDirectBinding(B, R)) 1285490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu return *V; 1286490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu 1287018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType Ty = R->getValueType(); 12881437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForFieldOrElementCommon(store, R, Ty, R->getSuperRegion()); 1289566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek} 12901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1291dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted KremenekOptional<SVal> 12921437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksRegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B, 12931437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const MemRegion *superR, 12941437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const TypedValueRegion *R, 12951437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType Ty) { 1296dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1297dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { 1298613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek const SVal &val = D.getValue(); 1299613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (SymbolRef parentSym = val.getAsSymbol()) 1300c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1301dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1302613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (val.isZeroConstant()) 1303c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeZeroVal(Ty); 1304dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1305613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (val.isUnknownOrUndef()) 1306613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek return val; 1307613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 1308613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek // Lazy bindings are handled later. 1309613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (isa<nonloc::LazyCompoundVal>(val)) 1310613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek return Optional<SVal>(); 1311dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1312b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Unknown default value"); 1313dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek } 1314dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1315dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek return Optional<SVal>(); 1316dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek} 1317dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 13181437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getLazyBinding(const MemRegion *lazyBindingRegion, 1319613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek Store lazyBindingStore) { 1320613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion)) 13211437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForElement(lazyBindingStore, ER); 1322613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 13231437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForField(lazyBindingStore, 13241437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks cast<FieldRegion>(lazyBindingRegion)); 1325613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek} 1326613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 13271437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store, 13289697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R, 1329566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek QualType Ty, 1330566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek const MemRegion *superR) { 1331566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek 13321437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks // At this point we have already checked in either getBindingForElement or 13331437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks // getBindingForField if 'R' has a direct binding. 1334bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu RegionBindings B = GetRegionBindings(store); 13358f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek 13368f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek // Lazy binding? 13378f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek Store lazyBindingStore = NULL; 13388f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek const MemRegion *lazyBindingRegion = NULL; 133951d18cab1f55df33d85137868b59fec0c4a8776aTed Kremenek llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R, 134051d18cab1f55df33d85137868b59fec0c4a8776aTed Kremenek true); 134131b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek 13428f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek if (lazyBindingRegion) 13438f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek return getLazyBinding(lazyBindingRegion, lazyBindingStore); 13448f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek 134531b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // Record whether or not we see a symbolic index. That can completely 134631b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // be out of scope of our lookup. 134731b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek bool hasSymbolicIndex = false; 13481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 134919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek while (superR) { 1350c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek if (const Optional<SVal> &D = 13511437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks getBindingForDerivedDefaultValue(B, superR, R, Ty)) 1352dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek return *D; 13531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 135431b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) { 135531b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek NonLoc index = ER->getIndex(); 135631b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (!index.isConstant()) 135731b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek hasSymbolicIndex = true; 135831b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek } 135931b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek 136019e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // If our super region is a field or element itself, walk up the region 136119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // hierarchy to see if there is a default value installed in an ancestor. 1362c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) { 1363c1143e598d6f2d8da045888298a9893a84e678dfTed Kremenek superR = SR->getSuperRegion(); 136419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek continue; 136519e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 136619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek break; 1367a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek } 13681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1369de0d26310191215a6d1d189dc419f87af18ce6beTed Kremenek if (R->hasStackNonParametersStorage()) { 137031b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (isa<ElementRegion>(R)) { 1371566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek // Currently we don't reason specially about Clang-style vectors. Check 1372566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek // if superR is a vector and if so return Unknown. 13739697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *typedSuperR = 13749697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek dyn_cast<TypedValueRegion>(superR)) { 1375018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu if (typedSuperR->getValueType()->isVectorType()) 1376566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek return UnknownVal(); 13771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 1378566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek } 13791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 138031b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // FIXME: We also need to take ElementRegions with symbolic indexes into 138131b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // account. This case handles both directly accessing an ElementRegion 138231b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // with a symbolic offset, but also fields within an element with 138331b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // a symbolic offset. 138431b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (hasSymbolicIndex) 138531b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek return UnknownVal(); 138631b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek 1387490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu return UndefinedVal(); 1388566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek } 13891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1390bb2b433ae14ca18e88a46032096ce5ec5c05c8e7Ted Kremenek // All other values are symbolic. 1391c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 1392490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu} 13931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 13941437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForObjCIvar(Store store, 13951437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const ObjCIvarRegion* R) { 13965bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek 13975bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek // Check if the region has a binding. 1398576bb92057979b14ca04b3080a9405662d0217a3Zhongxing Xu RegionBindings B = GetRegionBindings(store); 13995bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek 14002cf073b7686a05bc0f637862bdc06f71232db954Ted Kremenek if (const Optional<SVal> &V = getDirectBinding(B, R)) 14015bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek return *V; 14021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14035bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek const MemRegion *superR = R->getSuperRegion(); 14045bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek 1405ab22ee9ede5532f35c64b8eaccb4210f3f16397dTed Kremenek // Check if the super region has a default binding. 14062cf073b7686a05bc0f637862bdc06f71232db954Ted Kremenek if (const Optional<SVal> &V = getDefaultBinding(B, superR)) { 14075bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek if (SymbolRef parentSym = V->getAsSymbol()) 1408c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 14091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14105bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek // Other cases: give up. 14115bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek return UnknownVal(); 14125bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek } 14131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14141437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForLazySymbol(R); 141525c545788da6e3a725206cfa378b9b83a7da6024Ted Kremenek} 141625c545788da6e3a725206cfa378b9b83a7da6024Ted Kremenek 14171437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) { 14181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14199031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek // Check if the region has a binding. 1420576bb92057979b14ca04b3080a9405662d0217a3Zhongxing Xu RegionBindings B = GetRegionBindings(store); 14211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14222cf073b7686a05bc0f637862bdc06f71232db954Ted Kremenek if (const Optional<SVal> &V = getDirectBinding(B, R)) 14239031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek return *V; 14241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14259031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek // Lazily derive a value for the VarRegion. 14269031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek const VarDecl *VD = R->getDecl(); 14274dc1566a80648a74a19409c425809fa6a1683befTed Kremenek QualType T = VD->getType(); 14284dc1566a80648a74a19409c425809fa6a1683befTed Kremenek const MemSpaceRegion *MS = R->getMemorySpace(); 1429e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1430e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek if (isa<UnknownSpaceRegion>(MS) || 14314dc1566a80648a74a19409c425809fa6a1683befTed Kremenek isa<StackArgumentsSpaceRegion>(MS)) 1432c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 14331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14344dc1566a80648a74a19409c425809fa6a1683befTed Kremenek if (isa<GlobalsSpaceRegion>(MS)) { 1435dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek if (isa<NonStaticGlobalSpaceRegion>(MS)) { 14364552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek // Is 'VD' declared constant? If so, retrieve the constant value. 14374552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek QualType CT = Ctx.getCanonicalType(T); 14384552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek if (CT.isConstQualified()) { 14394552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek const Expr *Init = VD->getInit(); 14404552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek // Do the null check first, as we want to call 'IgnoreParenCasts'. 14414552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek if (Init) 14424552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek if (const IntegerLiteral *IL = 14434552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) { 1444c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL); 1445c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.evalCast(V, Init->getType(), IL->getType()); 14464552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek } 14474552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek } 14484552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek 14491437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks if (const Optional<SVal> &V 14501437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks = getBindingForDerivedDefaultValue(B, MS, R, CT)) 1451dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek return V.getValue(); 1452dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1453c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 14544552ff080062cacc4b57906e6f2f09e9d796b6a4Ted Kremenek } 14551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14564dc1566a80648a74a19409c425809fa6a1683befTed Kremenek if (T->isIntegerType()) 1457c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeIntVal(0, T); 145881861abe9cd1669ca46e13866f77f7ece8c4c85fTed Kremenek if (T->isPointerType()) 1459c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeNull(); 146081861abe9cd1669ca46e13866f77f7ece8c4c85fTed Kremenek 1461e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek return UnknownVal(); 14624dc1566a80648a74a19409c425809fa6a1683befTed Kremenek } 1463e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 14649031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek return UndefinedVal(); 14659031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek} 14669031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek 14671437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 14685bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek // All other values are symbolic. 1469c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 14705bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek} 14715bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek 1472752bee2493ec2931bd18899753552e3a47dc85feJordan Rosestatic bool mayHaveLazyBinding(QualType Ty) { 1473752bee2493ec2931bd18899753552e3a47dc85feJordan Rose return Ty->isArrayType() || Ty->isStructureOrClassType(); 1474752bee2493ec2931bd18899753552e3a47dc85feJordan Rose} 1475752bee2493ec2931bd18899753552e3a47dc85feJordan Rose 14761437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForStruct(Store store, 14779697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion* R) { 1478752bee2493ec2931bd18899753552e3a47dc85feJordan Rose const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 1479752bee2493ec2931bd18899753552e3a47dc85feJordan Rose if (RD->field_empty()) 1480752bee2493ec2931bd18899753552e3a47dc85feJordan Rose return UnknownVal(); 1481752bee2493ec2931bd18899753552e3a47dc85feJordan Rose 1482752bee2493ec2931bd18899753552e3a47dc85feJordan Rose // If we already have a lazy binding, don't create a new one, 1483752bee2493ec2931bd18899753552e3a47dc85feJordan Rose // unless the first field might have a lazy binding of its own. 1484752bee2493ec2931bd18899753552e3a47dc85feJordan Rose // (Right now we can't tell the difference.) 1485752bee2493ec2931bd18899753552e3a47dc85feJordan Rose QualType FirstFieldType = RD->field_begin()->getType(); 1486752bee2493ec2931bd18899753552e3a47dc85feJordan Rose if (!mayHaveLazyBinding(FirstFieldType)) { 1487752bee2493ec2931bd18899753552e3a47dc85feJordan Rose RegionBindings B = GetRegionBindings(store); 1488752bee2493ec2931bd18899753552e3a47dc85feJordan Rose BindingKey K = BindingKey::Make(R, BindingKey::Default); 1489752bee2493ec2931bd18899753552e3a47dc85feJordan Rose if (const nonloc::LazyCompoundVal *V = 1490752bee2493ec2931bd18899753552e3a47dc85feJordan Rose dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) { 1491752bee2493ec2931bd18899753552e3a47dc85feJordan Rose return *V; 1492752bee2493ec2931bd18899753552e3a47dc85feJordan Rose } 14937dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted Kremenek } 14947dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted Kremenek 1495cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 14966e3f01cef27dd6cc7e36769618820c5b984f61daZhongxing Xu} 14976e3f01cef27dd6cc7e36769618820c5b984f61daZhongxing Xu 14987dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted KremenekSVal RegionStoreManager::getBindingForArray(Store store, 14999697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion * R) { 1500752bee2493ec2931bd18899753552e3a47dc85feJordan Rose const ConstantArrayType *Ty = Ctx.getAsConstantArrayType(R->getValueType()); 1501752bee2493ec2931bd18899753552e3a47dc85feJordan Rose assert(Ty && "Only constant array types can have compound bindings."); 15027dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted Kremenek 1503752bee2493ec2931bd18899753552e3a47dc85feJordan Rose // If we already have a lazy binding, don't create a new one, 1504752bee2493ec2931bd18899753552e3a47dc85feJordan Rose // unless the first element might have a lazy binding of its own. 1505752bee2493ec2931bd18899753552e3a47dc85feJordan Rose // (Right now we can't tell the difference.) 1506752bee2493ec2931bd18899753552e3a47dc85feJordan Rose if (!mayHaveLazyBinding(Ty->getElementType())) { 1507752bee2493ec2931bd18899753552e3a47dc85feJordan Rose RegionBindings B = GetRegionBindings(store); 1508752bee2493ec2931bd18899753552e3a47dc85feJordan Rose BindingKey K = BindingKey::Make(R, BindingKey::Default); 1509752bee2493ec2931bd18899753552e3a47dc85feJordan Rose if (const nonloc::LazyCompoundVal *V = 1510752bee2493ec2931bd18899753552e3a47dc85feJordan Rose dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) { 1511752bee2493ec2931bd18899753552e3a47dc85feJordan Rose return *V; 1512752bee2493ec2931bd18899753552e3a47dc85feJordan Rose } 15137dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted Kremenek } 15147dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted Kremenek 1515cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 15163e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu} 15173e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu 1518fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenekbool RegionStoreManager::includedInBindings(Store store, 1519fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek const MemRegion *region) const { 1520fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek RegionBindings B = GetRegionBindings(store); 1521fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek region = region->getBaseRegion(); 15221e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 15231e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Quick path: if the base is the head of a cluster, the region is live. 15241e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (B.lookup(region)) 15251e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return true; 15261e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 15271e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Slow path: if the region is the VALUE of any binding, it is live. 15281e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 15291e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = RI.getData(); 15301e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 15311e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 15321e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const SVal &D = CI.getData(); 15331e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const MemRegion *R = D.getAsRegion()) 15341e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (R->getBaseRegion() == region) 15351e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return true; 15361e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 1537fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek } 15381e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 1539fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek return false; 1540fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek} 1541fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek 15429af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 15439af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Binding values to regions. 15449af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 15459af46f59242cfaec74fa491a66724970478263ebTed Kremenek 154656a46b51df691f857f7120aaf2d4deeff0b014deTed KremenekStoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 15479af46f59242cfaec74fa491a66724970478263ebTed Kremenek if (isa<loc::MemRegionVal>(L)) 1548c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) 154956a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek return StoreRef(removeBinding(GetRegionBindings(ST), 155077a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek R).getRootWithoutRetain(), 155177a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek *this); 15521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 155356a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek return StoreRef(ST, *this); 15549af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 15559af46f59242cfaec74fa491a66724970478263ebTed Kremenek 155677a4d5687c2cb3199c689892c9d040a94ff270afTed KremenekStoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { 155787453d1c39df791fb98618f6ba34b2edaae880e1Zhongxing Xu if (isa<loc::ConcreteInt>(L)) 155877a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(store, *this); 155987453d1c39df791fb98618f6ba34b2edaae880e1Zhongxing Xu 15604193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu // If we get here, the location should be a region. 156119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); 15621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 15634193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu // Check if the region is a struct region. 15648667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 15658667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek QualType Ty = TR->getValueType(); 156632a549a64922af0903bdb777613ae7ae4490b70fTed Kremenek if (Ty->isArrayType()) 156732a549a64922af0903bdb777613ae7ae4490b70fTed Kremenek return BindArray(store, TR, V); 15688667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (Ty->isStructureOrClassType()) 1569b4a9c612f901a47135ea531f60db997d4cc4cdf5Zhongxing Xu return BindStruct(store, TR, V); 15708667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (Ty->isVectorType()) 15718667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek return BindVector(store, TR, V); 15728667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 15731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1574e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 15750954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek // Binding directly to a symbolic region should be treated as binding 15760954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek // to element 0. 157757663fe6c3c7a0fb792626537c4f3f7d3594aa66Zhongxing Xu QualType T = SR->getSymbol()->getType(Ctx); 15784e45dba1c0234eec7b7c348dbbf568c5ac9fc471Jordan Rose if (T->isAnyPointerType() || T->isReferenceType()) 15794e45dba1c0234eec7b7c348dbbf568c5ac9fc471Jordan Rose T = T->getPointeeType(); 1580852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek 15810954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek R = GetElementZeroRegion(SR, T); 15820954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek } 15831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1584e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // Clear out bindings that may overlap with this binding. 1585e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 158619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // Perform the binding. 1587b4a9c612f901a47135ea531f60db997d4cc4cdf5Zhongxing Xu RegionBindings B = GetRegionBindings(store); 1588e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose B = removeSubRegionBindings(B, cast<SubRegion>(R)); 1589e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose BindingKey Key = BindingKey::Make(R, BindingKey::Direct); 1590e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose return StoreRef(addBinding(B, Key, V).getRootWithoutRetain(), *this); 15919c9ca08fdd27fb0b025782aa41fae93612edf440Zhongxing Xu} 15929c9ca08fdd27fb0b025782aa41fae93612edf440Zhongxing Xu 15934193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu// FIXME: this method should be merged into Bind(). 15945be88dc79d2768d67371103b6535fb8c4a6f27a1Ted KremenekStoreRef RegionStoreManager::bindCompoundLiteral(Store ST, 159577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const CompoundLiteralExpr *CL, 159677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const LocationContext *LC, 159777a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek SVal V) { 15985be88dc79d2768d67371103b6535fb8c4a6f27a1Ted Kremenek return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V); 1599f22679e3e5d5f5754931952e58112b4c863a4137Zhongxing Xu} 1600f22679e3e5d5f5754931952e58112b4c863a4137Zhongxing Xu 160177a4d5687c2cb3199c689892c9d040a94ff270afTed KremenekStoreRef RegionStoreManager::setImplicitDefaultValue(Store store, 160277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const MemRegion *R, 160377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek QualType T) { 1604027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek RegionBindings B = GetRegionBindings(store); 1605027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek SVal V; 1606027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek 16077dfc9420babe83e236a47e752f8723bd06070d9dZhanyong Wan if (Loc::isLocType(T)) 1608c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek V = svalBuilder.makeNull(); 1609027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek else if (T->isIntegerType()) 1610c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek V = svalBuilder.makeZeroVal(T); 1611fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor else if (T->isStructureOrClassType() || T->isArrayType()) { 1612027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // Set the default value to a zero constant when it is a structure 1613027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // or array. The type doesn't really matter. 1614c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek V = svalBuilder.makeZeroVal(Ctx.IntTy); 1615027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek } 1616027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek else { 1617eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // We can't represent values of this type, but we still need to set a value 1618eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // to record that the region has been initialized. 1619eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // If this assertion ever fires, a new case should be added above -- we 1620eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // should know how to default-initialize any value we can symbolicate. 1621eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1622eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose V = UnknownVal(); 1623027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek } 16241c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 162577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(addBinding(B, R, BindingKey::Default, 162677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek V).getRootWithoutRetain(), *this); 1627027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek} 1628e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 16299697934650354bed2e509d8e7e44f21a1fb00f76Ted KremenekStoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, 163077a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek SVal Init) { 1631e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1632018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1633e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek QualType ElementTy = AT->getElementType(); 1634fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek Optional<uint64_t> Size; 1635e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1636fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1637fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek Size = CAT->getSize().getZExtValue(); 1638e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1639167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // Check if the init expr is a string literal. 1640167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) { 1641167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 16424193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu 1643167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // Treat the string as a lazy compound value. 1644167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose nonloc::LazyCompoundVal LCV = 1645cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek cast<nonloc::LazyCompoundVal>(svalBuilder. 1646cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek makeLazyCompoundVal(StoreRef(store, *this), S)); 16475ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return BindAggregate(store, R, LCV); 16486987c7b74146b9658b1925c5981f8b0cd0672b55Zhongxing Xu } 16491a12a0ea00a62d785ce8c25e740a152015a3000aZhongxing Xu 1650a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek // Handle lazy compound values. 16515ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose if (isa<nonloc::LazyCompoundVal>(Init)) 16525ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return BindAggregate(store, R, Init); 16531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 16541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Remaining case: explicit compound values. 1655e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1656027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek if (Init.isUnknown()) 1657e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek return setImplicitDefaultValue(store, R, ElementTy); 1658e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 16591a12a0ea00a62d785ce8c25e740a152015a3000aZhongxing Xu nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); 16601a12a0ea00a62d785ce8c25e740a152015a3000aZhongxing Xu nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1661465373946b5ae84f7c3d890cc25cb23fd88dd650Ted Kremenek uint64_t i = 0; 16621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 166377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef newStore(store, *this); 1664fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 1665087d6c20876ced37d544552b43cf33332687f074Zhongxing Xu // The init list might be shorter than the array length. 16664193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu if (VI == VE) 16674193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu break; 1668a82512a2735bed5a3498e7a5f24f4c365bbd5704Zhongxing Xu 1669c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 167057663fe6c3c7a0fb792626537c4f3f7d3594aa66Zhongxing Xu const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 1671c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 1672fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor if (ElementTy->isStructureOrClassType()) 167377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = BindStruct(newStore.getStore(), ER, *VI); 167459b6dca7e5160d6f2aff42b1cf077d1cbd64e330Jordy Rose else if (ElementTy->isArrayType()) 167577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = BindArray(newStore.getStore(), ER, *VI); 16764193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu else 167777a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); 1678c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu } 1679c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 1680027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // If the init list is shorter than the array length, set the 1681027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // array default value. 1682fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek if (Size.hasValue() && i < Size.getValue()) 168377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy); 1684087d6c20876ced37d544552b43cf33332687f074Zhongxing Xu 168577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return newStore; 1686c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu} 1687c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 16888667052a53a47a6290dc9ae98e5c3d9277df5f4aTed KremenekStoreRef RegionStoreManager::BindVector(Store store, const TypedValueRegion* R, 16898667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek SVal V) { 16908667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek QualType T = R->getValueType(); 16918667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek assert(T->isVectorType()); 16928667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs. 16938667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 16945ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose // Handle lazy compound values and symbolic values. 16955ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V)) 16965ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return BindAggregate(store, R, V); 16978667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 16988667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek // We may get non-CompoundVal accidentally due to imprecise cast logic or 16998667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek // that we are binding symbolic struct value. Kill the field values, and if 17008667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek // the value is symbolic go and bind it as a "default" binding. 17015ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose if (!isa<nonloc::CompoundVal>(V)) { 17025ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return BindAggregate(store, R, UnknownVal()); 17038667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 17048667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 17058667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek QualType ElemType = VT->getElementType(); 17068667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 17078667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 17088667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek unsigned index = 0, numElements = VT->getNumElements(); 17098667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek StoreRef newStore(store, *this); 17108667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 17118667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek for ( ; index != numElements ; ++index) { 17128667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (VI == VE) 17138667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek break; 17148667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 17158667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek NonLoc Idx = svalBuilder.makeArrayIndex(index); 17168667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 17178667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 17188667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (ElemType->isArrayType()) 17198667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek newStore = BindArray(newStore.getStore(), ER, *VI); 17208667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek else if (ElemType->isStructureOrClassType()) 17218667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek newStore = BindStruct(newStore.getStore(), ER, *VI); 17228667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek else 17238667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); 17248667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 17258667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek return newStore; 17268667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek} 17278667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 17289697934650354bed2e509d8e7e44f21a1fb00f76Ted KremenekStoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, 172977a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek SVal V) { 17301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 173167f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek if (!Features.supportsFields()) 173277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(store, *this); 17331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1734018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = R->getValueType(); 1735fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor assert(T->isStructureOrClassType()); 1736af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu 17376217b80b7a1379b74cced1c076338262c3c980b3Ted Kremenek const RecordType* RT = T->getAs<RecordType>(); 17389c378f705405d37f49795d5e915989de774fe11fTed Kremenek RecordDecl *RD = RT->getDecl(); 1739c45a8253cadb640dee1d8f23fba4a6c6f8da27f4Zhongxing Xu 17405e1cdac63c3d9c9b32fa41fa0b2d242a58a20d49John McCall if (!RD->isCompleteDefinition()) 174177a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(store, *this); 1742af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu 17435ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose // Handle lazy compound values and symbolic values. 17445ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V)) 17455ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return BindAggregate(store, R, V); 17461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1747281e9dc6ba6ff10bf910b0fc8898dff2a429f156Ted Kremenek // We may get non-CompoundVal accidentally due to imprecise cast logic or 1748281e9dc6ba6ff10bf910b0fc8898dff2a429f156Ted Kremenek // that we are binding symbolic struct value. Kill the field values, and if 1749281e9dc6ba6ff10bf910b0fc8898dff2a429f156Ted Kremenek // the value is symbolic go and bind it as a "default" binding. 17505ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) 17515ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return BindAggregate(store, R, UnknownVal()); 17523f6978a3fefc16f203afbc64697fe04af329cf2bZhongxing Xu 17534193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1754af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1755dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu 1756dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu RecordDecl::field_iterator FI, FE; 175777a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef newStore(store, *this); 175877a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek 1759e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 1760af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu 1761dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu if (VI == VE) 17624193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu break; 1763ea8a1854137faca10ccb24acf4f1a74912fccfb2Zhongxing Xu 1764e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II // Skip any unnamed bitfields to stay in sync with the initializers. 1765262bc18e32500558af7cb0afa205b34bd37bafedDavid Blaikie if (FI->isUnnamedBitfield()) 1766e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II continue; 1767e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II 1768262bc18e32500558af7cb0afa205b34bd37bafedDavid Blaikie QualType FTy = FI->getType(); 1769581deb3da481053c4993c7600f97acf7768caac5David Blaikie const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 1770ea8a1854137faca10ccb24acf4f1a74912fccfb2Zhongxing Xu 1771cf54959eae25fb3050f41833f0eab91042fb1269Ted Kremenek if (FTy->isArrayType()) 177277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = BindArray(newStore.getStore(), FR, *VI); 1773fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor else if (FTy->isStructureOrClassType()) 177477a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = BindStruct(newStore.getStore(), FR, *VI); 1775cf54959eae25fb3050f41833f0eab91042fb1269Ted Kremenek else 177677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI); 1777e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II ++VI; 1778c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu } 1779c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 1780dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu // There may be fewer values in the initialize list than the fields of struct. 178113d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu if (FI != FE) { 178277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek RegionBindings B = GetRegionBindings(newStore.getStore()); 1783c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false)); 178477a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek newStore = StoreRef(B.getRootWithoutRetain(), *this); 178513d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu } 1786dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu 178777a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return newStore; 1788c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu} 1789c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 17905ad76c073e1822d11901a8552c6aa9372038b5f0Jordan RoseStoreRef RegionStoreManager::BindAggregate(Store store, const TypedRegion *R, 17915ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose SVal Val) { 1792e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // Remove the old bindings, using 'R' as the root of all regions 17935ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose // we will invalidate. Then add the new binding. 179413d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu RegionBindings B = GetRegionBindings(store); 17955834ed6999980d90bd125dd1c8f9301e9d48f40cZhongxing Xu 1796e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose B = removeSubRegionBindings(B, R); 17975ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose B = addBinding(B, R, BindingKey::Default, Val); 17981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17995ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose return StoreRef(B.getRootWithoutRetain(), *this); 18001c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18011c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18021c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 18031c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek// "Raw" retrievals and bindings. 18041c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 18051c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 1806c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 18073baf672378f105602d2b12f03f00277ae1936fe9Ted KremenekRegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K, 18083baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek SVal V) { 18091e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base = K.getBaseRegion(); 18101e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18111e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *ExistingCluster = B.lookup(Base); 18121e934431adba0f459668a59c6059b9596fd627b4Jordan Rose ClusterBindings Cluster = (ExistingCluster ? *ExistingCluster 18131e934431adba0f459668a59c6059b9596fd627b4Jordan Rose : CBFactory.getEmptyMap()); 18141e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18151e934431adba0f459668a59c6059b9596fd627b4Jordan Rose ClusterBindings NewCluster = CBFactory.add(Cluster, K, V); 18161e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.add(B, Base, NewCluster); 18171c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18181c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18193baf672378f105602d2b12f03f00277ae1936fe9Ted KremenekRegionBindings RegionStoreManager::addBinding(RegionBindings B, 18203baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek const MemRegion *R, 18213baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek BindingKey::Kind k, SVal V) { 18223baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek return addBinding(B, BindingKey::Make(R, k), V); 18231c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18241c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18253baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenekconst SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) { 18261e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *Cluster = B.lookup(K.getBaseRegion()); 18271e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Cluster) 18281e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return 0; 18291e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18301e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return Cluster->lookup(K); 18311c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18321c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18333baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenekconst SVal *RegionStoreManager::lookup(RegionBindings B, 1834e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek const MemRegion *R, 1835e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek BindingKey::Kind k) { 18363baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek return lookup(B, BindingKey::Make(R, k)); 18371c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18381c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18393baf672378f105602d2b12f03f00277ae1936fe9Ted KremenekRegionBindings RegionStoreManager::removeBinding(RegionBindings B, 18403baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek BindingKey K) { 18411e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base = K.getBaseRegion(); 18421e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *Cluster = B.lookup(Base); 18431e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Cluster) 1844e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose return B; 18451e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18461e934431adba0f459668a59c6059b9596fd627b4Jordan Rose ClusterBindings NewCluster = CBFactory.remove(*Cluster, K); 18471e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (NewCluster.isEmpty()) 18481e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.remove(B, Base); 18491e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.add(B, Base, NewCluster); 18501c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18511c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18523baf672378f105602d2b12f03f00277ae1936fe9Ted KremenekRegionBindings RegionStoreManager::removeBinding(RegionBindings B, 18533baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek const MemRegion *R, 185456a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek BindingKey::Kind k){ 18553baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek return removeBinding(B, BindingKey::Make(R, k)); 18561c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} 18571c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 18581e934431adba0f459668a59c6059b9596fd627b4Jordan RoseRegionBindings RegionStoreManager::removeCluster(RegionBindings B, 18591e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base) { 18601e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return RBFactory.remove(B, Base); 18611e934431adba0f459668a59c6059b9596fd627b4Jordan Rose} 18621e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18639af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 18649af46f59242cfaec74fa491a66724970478263ebTed Kremenek// State pruning. 18659af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 1866e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 18675499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremeneknamespace { 1868db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekclass removeDeadBindingsWorker : 1869db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek public ClusterAnalysis<removeDeadBindingsWorker> { 18705f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const SymbolicRegion*, 12> Postponed; 18715499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek SymbolReaper &SymReaper; 187217ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu const StackFrameContext *CurrentLCtx; 1873dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 18745499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenekpublic: 18751437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks removeDeadBindingsWorker(RegionStoreManager &rm, 18761437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks ProgramStateManager &stateMgr, 18775499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek RegionBindings b, SymbolReaper &symReaper, 18787dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose const StackFrameContext *LCtx) 1879db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, 1880d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek /* includeGlobals = */ false), 18817dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose SymReaper(symReaper), CurrentLCtx(LCtx) {} 18825499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 18835499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Called by ClusterAnalysis. 18841e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 18851e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); 18865499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 18875499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool UpdatePostponed(); 18885499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek void VisitBinding(SVal V); 18895499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek}; 18905499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 18911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1892db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekvoid removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 18931e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &C) { 1894e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 18955499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 18967dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose if (SymReaper.isLive(VR)) 18971e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(baseR, &C); 1898e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 18995499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 19009af46f59242cfaec74fa491a66724970478263ebTed Kremenek } 1901e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 19025499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 19035499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (SymReaper.isLive(SR->getSymbol())) 19041e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(SR, &C); 19055499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek else 19065499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek Postponed.push_back(SR); 1907e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 19085499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 19099af46f59242cfaec74fa491a66724970478263ebTed Kremenek } 191017ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu 1911dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 19121e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(baseR, &C); 1913dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek return; 1914dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek } 1915dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 191617ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu // CXXThisRegion in the current or parent location context is live. 191717ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 1918dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek const StackArgumentsSpaceRegion *StackReg = 191917ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 192017ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu const StackFrameContext *RegCtx = StackReg->getStackFrame(); 192117ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) 19221e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(TR, &C); 192317ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu } 19245499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 19251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1926db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekvoid removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 19271e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &C) { 1928f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose // Mark the symbol for any SymbolicRegion with live bindings as live itself. 1929f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose // This means we should continue to track that symbol. 1930f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 1931f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose SymReaper.markLive(SymR->getSymbol()); 1932f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose 1933f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) 19341e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(I.getData()); 19355499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 1936df165014c2defd9120a8f105a855d6a8b35befbeTed Kremenek 1937db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekvoid removeDeadBindingsWorker::VisitBinding(SVal V) { 19385499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Is it a LazyCompoundVal? All referenced regions are live as well. 19395499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const nonloc::LazyCompoundVal *LCS = 19401e934431adba0f459668a59c6059b9596fd627b4Jordan Rose dyn_cast<nonloc::LazyCompoundVal>(&V)) { 19419e17cc6abb5d55bd776d379b20d5b476bcc46c71Ted Kremenek 19425499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const MemRegion *LazyR = LCS->getRegion(); 19435499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); 19441e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 19451e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // FIXME: This should not have to walk all bindings in the old store. 19465499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 19471e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = RI.getData(); 19481e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 19491e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 19501e934431adba0f459668a59c6059b9596fd627b4Jordan Rose BindingKey K = CI.getKey(); 19511e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) { 19521e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (BaseR == LazyR) 19531e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(CI.getData()); 19541e934431adba0f459668a59c6059b9596fd627b4Jordan Rose else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR)) 19551e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(CI.getData()); 19561e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 19571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 1958a6d73af984d9633cd3b412f01b35edf7463dd31cTed Kremenek } 19591e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 19605499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 19615499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 19629e17cc6abb5d55bd776d379b20d5b476bcc46c71Ted Kremenek 19635499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // If V is a region, then add it to the worklist. 19647fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek if (const MemRegion *R = V.getAsRegion()) { 19655499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek AddToWorkList(R); 19667fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 19677fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek // All regions captured by a block are also live. 19687fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 19697fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 19707fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek E = BR->referenced_vars_end(); 1971f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose for ( ; I != E; ++I) 1972f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose AddToWorkList(I.getCapturedRegion()); 19737fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek } 19747fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek } 19757fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 19761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1977aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks // Update the set of live symbols. 19781d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 19791d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks SI!=SE; ++SI) 19805499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek SymReaper.markLive(*SI); 19815499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 1982e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1983db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekbool removeDeadBindingsWorker::UpdatePostponed() { 198401756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek // See if any postponed SymbolicRegions are actually live now, after 198501756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek // having done a scan. 19865499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool changed = false; 19875499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 19885f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner for (SmallVectorImpl<const SymbolicRegion*>::iterator 19895499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 1990f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose if (const SymbolicRegion *SR = *I) { 199101756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek if (SymReaper.isLive(SR->getSymbol())) { 19925499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek changed |= AddToWorkList(SR); 19935499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek *I = NULL; 199401756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek } 199501756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek } 199601756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek } 1997e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 19985499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return changed; 19995499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 20005499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 200177a4d5687c2cb3199c689892c9d040a94ff270afTed KremenekStoreRef RegionStoreManager::removeDeadBindings(Store store, 200277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const StackFrameContext *LCtx, 2003bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek SymbolReaper& SymReaper) { 20045e4cb347cbf12c292b80386c872e5eaef21b5c23Zhongxing Xu RegionBindings B = GetRegionBindings(store); 2005db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 20065499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.GenerateClusters(); 20075499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 20085499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Enqueue the region roots onto the worklist. 2009bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2010bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek E = SymReaper.region_end(); I != E; ++I) { 20115499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.AddToWorkList(*I); 2012bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek } 20135499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 20145499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek do W.RunWorkList(); while (W.UpdatePostponed()); 2015e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 20169af46f59242cfaec74fa491a66724970478263ebTed Kremenek // We have now scanned the store, marking reachable regions and symbols 20179af46f59242cfaec74fa491a66724970478263ebTed Kremenek // as live. We now remove all the regions that are dead from the store 20181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // as well as update DSymbols with the set symbols that are now dead. 2019451ac091cd1868433985396a25cbbf2092ae8ca9Ted Kremenek for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { 20201e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base = I.getKey(); 20215499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 2022b7118f7c379a652a910f92c4566cffceb2a8b5feTed Kremenek // If the cluster has been visited, we know the region has been marked. 20231e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (W.isVisited(Base)) 20249af46f59242cfaec74fa491a66724970478263ebTed Kremenek continue; 20251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 20265499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Remove the dead entry. 20271e934431adba0f459668a59c6059b9596fd627b4Jordan Rose B = removeCluster(B, Base); 20281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 20291e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base)) 20309af46f59242cfaec74fa491a66724970478263ebTed Kremenek SymReaper.maybeDead(SymR->getSymbol()); 20311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 20321e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Mark all non-live symbols that this binding references as dead. 20331e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = I.getData(); 20341e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 20351e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 20361e934431adba0f459668a59c6059b9596fd627b4Jordan Rose SVal X = CI.getData(); 20371e934431adba0f459668a59c6059b9596fd627b4Jordan Rose SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 20381e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (; SI != SE; ++SI) 20391e934431adba0f459668a59c6059b9596fd627b4Jordan Rose SymReaper.maybeDead(*SI); 20401e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 2041093569cfab473e7b461523136a4df30a0473324dTed Kremenek } 20425e4cb347cbf12c292b80386c872e5eaef21b5c23Zhongxing Xu 204377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(B.getRootWithoutRetain(), *this); 20449af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 20459af46f59242cfaec74fa491a66724970478263ebTed Kremenek 20469af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 20479af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Utility methods. 20489af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 20499af46f59242cfaec74fa491a66724970478263ebTed Kremenek 20509c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid RegionStoreManager::print(Store store, raw_ostream &OS, 20519af46f59242cfaec74fa491a66724970478263ebTed Kremenek const char* nl, const char *sep) { 2052451ac091cd1868433985396a25cbbf2092ae8ca9Ted Kremenek RegionBindings B = GetRegionBindings(store); 20536341931b144cbf369ab816e871322c99ee62bea7Ted Kremenek OS << "Store (direct and default bindings), " 20546341931b144cbf369ab816e871322c99ee62bea7Ted Kremenek << (void*) B.getRootWithoutRetain() 20556341931b144cbf369ab816e871322c99ee62bea7Ted Kremenek << " :" << nl; 20561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 20571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { 20581e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = I.getData(); 20591e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 20601e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 20611e934431adba0f459668a59c6059b9596fd627b4Jordan Rose OS << ' ' << CI.getKey() << " : " << CI.getData() << nl; 20621e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 20631e934431adba0f459668a59c6059b9596fd627b4Jordan Rose OS << nl; 20641e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 20659af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 2066