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//===----------------------------------------------------------------------===// 172fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/AST/Attr.h" 183ed04d37573c566205d965d2e91d54ccae898d0aZhongxing Xu#include "clang/AST/CharUnits.h" 1966d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "clang/Analysis/Analyses/LiveVariables.h" 2066d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "clang/Analysis/AnalysisContext.h" 2166d5142ab5026aa77ab6f1d7e4d9bdb0b438d55aTed Kremenek#include "clang/Basic/TargetInfo.h" 22258277d5a922e06ef523f7805900689b680ddc7dJordan Rose#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 23f540c54701e3eeb34cb619a3a4eb18f1ac70ef2dJordan Rose#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 242fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 2518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 2618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 27258277d5a922e06ef523f7805900689b680ddc7dJordan Rose#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.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; 35178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 361c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 37e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek// Representation of binding keys. 381c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 391c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 4013d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xunamespace { 41e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekclass BindingKey { 4213d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xupublic: 43824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose enum Kind { Default = 0x0, Direct = 0x1 }; 4413d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xuprivate: 45824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose enum { Symbolic = 0x2 }; 46e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 47824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose llvm::PointerIntPair<const MemRegion *, 2> P; 48824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose uint64_t Data; 49e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 509d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose /// Create a key for a binding to region \p r, which has a symbolic offset 519d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose /// from region \p Base. 529d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) 53824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { 54824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(r && Base && "Must have known regions."); 55824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); 56824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose } 579d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose 589d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose /// Create a key for a binding at \p offset from base region \p r. 59e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 60824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose : P(r, k), Data(offset) { 61824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(r && "Must have known regions."); 62824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(getOffset() == offset && "Failed to store offset"); 63d1a4f68a4301d1ee3098cc9db0cd507b96dd1beeBenjamin Kramer assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r)) && "Not a base"); 64824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose } 6513d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xupublic: 66e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 67824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose bool isDirect() const { return P.getInt() & Direct; } 68824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } 69e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 70e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek const MemRegion *getRegion() const { return P.getPointer(); } 71e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose uint64_t getOffset() const { 72e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose assert(!hasSymbolicOffset()); 73824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return Data; 74e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 75e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 769d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose const SubRegion *getConcreteOffsetRegion() const { 77824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose assert(hasSymbolicOffset()); 789d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); 79824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose } 80e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 811e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *getBaseRegion() const { 821e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (hasSymbolicOffset()) 831e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return getConcreteOffsetRegion()->getBaseRegion(); 841e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return getRegion()->getBaseRegion(); 851e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 861e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 8713d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu void Profile(llvm::FoldingSetNodeID& ID) const { 88e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek ID.AddPointer(P.getOpaqueValue()); 89824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose ID.AddInteger(Data); 9013d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu } 91e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 92e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek static BindingKey Make(const MemRegion *R, Kind k); 93e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 94e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek bool operator<(const BindingKey &X) const { 95e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek if (P.getOpaqueValue() < X.P.getOpaqueValue()) 96e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return true; 97e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek if (P.getOpaqueValue() > X.P.getOpaqueValue()) 98e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return false; 99824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return Data < X.Data; 100e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek } 101e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 102e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek bool operator==(const BindingKey &X) const { 103e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek return P.getOpaqueValue() == X.P.getOpaqueValue() && 104824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose Data == X.Data; 1051c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek } 106e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose 1071e934431adba0f459668a59c6059b9596fd627b4Jordan Rose LLVM_ATTRIBUTE_USED void dump() const; 108e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek}; 1091c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} // end anonymous namespace 1101c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 111dc015e5398d3cdd7baaa5d9a0330aaeafdf1a7c3Zhongxing XuBindingKey BindingKey::Make(const MemRegion *R, Kind k) { 1124213e389d6f8fa96ab30eec0d932e4e3eee32997Ted Kremenek const RegionOffset &RO = R->getAsOffset(); 113824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose if (RO.hasSymbolicOffset()) 1149d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); 115e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 116824e07ac8f5c9efdddb4254de0203b9675b1ef0bJordan Rose return BindingKey(RO.getRegion(), RO.getOffset(), k); 117dc015e5398d3cdd7baaa5d9a0330aaeafdf1a7c3Zhongxing Xu} 118dc015e5398d3cdd7baaa5d9a0330aaeafdf1a7c3Zhongxing Xu 1191c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremeneknamespace llvm { 120e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek static inline 1219c378f705405d37f49795d5e915989de774fe11fTed Kremenek raw_ostream &operator<<(raw_ostream &os, BindingKey K) { 122e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose os << '(' << K.getRegion(); 123e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (!K.hasSymbolicOffset()) 124e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose os << ',' << K.getOffset(); 125e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose os << ',' << (K.isDirect() ? "direct" : "default") 126e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek << ')'; 1271c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek return os; 1281c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek } 129e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose 130e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose template <typename T> struct isPodLike; 131e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose template <> struct isPodLike<BindingKey> { 132e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose static const bool value = true; 133e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose }; 1341c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek} // end llvm namespace 1351c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 1361e934431adba0f459668a59c6059b9596fd627b4Jordan Rosevoid BindingKey::dump() const { 1371e934431adba0f459668a59c6059b9596fd627b4Jordan Rose llvm::errs() << *this; 1381e934431adba0f459668a59c6059b9596fd627b4Jordan Rose} 1391e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 1401c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 141baf03a7c0a846632396f9f5a19f6cd45bbe2b926Zhongxing Xu// Actual Store type. 1421c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek//===----------------------------------------------------------------------===// 1431c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 14423dca7d88f3e9a7925bfb2c5449499900c906633Ted Kremenektypedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; 14523dca7d88f3e9a7925bfb2c5449499900c906633Ted Kremenektypedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; 146e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rosetypedef std::pair<BindingKey, SVal> BindingPair; 14729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 14829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenektypedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> 14929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindings; 15029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 15129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremeneknamespace { 15229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenekclass RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, 15329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek ClusterBindings> { 15429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek ClusterBindings::Factory &CBFactory; 15529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenekpublic: 15629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> 15729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek ParentTy; 15829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 15929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef(ClusterBindings::Factory &CBFactory, 16029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const RegionBindings::TreeTy *T, 16129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindings::TreeTy::Factory *F) 16275191fdbc3d3eec5f3447b285acf6cfcc2054b25David Blaikie : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), 16375191fdbc3d3eec5f3447b285acf6cfcc2054b25David Blaikie CBFactory(CBFactory) {} 16429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 16529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef(const ParentTy &P, ClusterBindings::Factory &CBFactory) 16675191fdbc3d3eec5f3447b285acf6cfcc2054b25David Blaikie : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), 16775191fdbc3d3eec5f3447b285acf6cfcc2054b25David Blaikie CBFactory(CBFactory) {} 16829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 16918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef add(key_type_ref K, data_type_ref D) const { 17018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return RegionBindingsRef(static_cast<const ParentTy*>(this)->add(K, D), 17129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek CBFactory); 17229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek } 17329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 17418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef remove(key_type_ref K) const { 17518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return RegionBindingsRef(static_cast<const ParentTy*>(this)->remove(K), 17629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek CBFactory); 17729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek } 17829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 17918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef addBinding(BindingKey K, SVal V) const; 18029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 18129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef addBinding(const MemRegion *R, 18218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek BindingKey::Kind k, SVal V) const; 18329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 18429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef &operator=(const RegionBindingsRef &X) { 18529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek *static_cast<ParentTy*>(this) = X; 18629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return *this; 18729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek } 18829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 18918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const SVal *lookup(BindingKey K) const; 19018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; 19129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const ClusterBindings *lookup(const MemRegion *R) const { 19229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return static_cast<const ParentTy*>(this)->lookup(R); 19329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek } 19429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 19529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef removeBinding(BindingKey K); 19629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 19729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef removeBinding(const MemRegion *R, 19829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek BindingKey::Kind k); 19929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 20029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef removeBinding(const MemRegion *R) { 20129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return removeBinding(R, BindingKey::Direct). 20229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek removeBinding(R, BindingKey::Default); 20329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek } 20429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 20518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek Optional<SVal> getDirectBinding(const MemRegion *R) const; 20629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 20729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek /// getDefaultBinding - Returns an SVal* representing an optional default 20829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek /// binding associated with a region and its subregions. 20918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek Optional<SVal> getDefaultBinding(const MemRegion *R) const; 2100c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek 2110c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek /// Return the internal tree as a Store. 2120c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek Store asStore() const { 2130c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek return asImmutableMap().getRootWithoutRetain(); 2140c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek } 215b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek 216cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko void dump(raw_ostream &OS, const char *nl) const { 217b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek for (iterator I = begin(), E = end(); I != E; ++I) { 218b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek const ClusterBindings &Cluster = I.getData(); 219b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 220b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek CI != CE; ++CI) { 221b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek OS << ' ' << CI.getKey() << " : " << CI.getData() << nl; 222b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek } 223b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek OS << nl; 224b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek } 225b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek } 226b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek 227b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek LLVM_ATTRIBUTE_USED void dump() const { 228b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek dump(llvm::errs(), "\n"); 229b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek } 23029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek}; 23129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} // end anonymous namespace 23229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 23318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenektypedef const RegionBindingsRef& RegionBindingsConstRef; 23418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek 23518f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekOptional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { 236472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose return Optional<SVal>::create(lookup(R, BindingKey::Direct)); 23729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 23829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 23918f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekOptional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { 24029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (R->isBoundable()) 24129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) 24229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (TR->getValueType()->isUnionType()) 24329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return UnknownVal(); 244472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose 245472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose return Optional<SVal>::create(lookup(R, BindingKey::Default)); 24629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 24729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 24818f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { 24929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const MemRegion *Base = K.getBaseRegion(); 25029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 25129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const ClusterBindings *ExistingCluster = lookup(Base); 25229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek ClusterBindings Cluster = (ExistingCluster ? *ExistingCluster 25329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek : CBFactory.getEmptyMap()); 25429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 25529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek ClusterBindings NewCluster = CBFactory.add(Cluster, K, V); 25629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return add(Base, NewCluster); 25729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 25829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 25929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 26029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekRegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, 26129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek BindingKey::Kind k, 26218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal V) const { 26329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return addBinding(BindingKey::Make(R, k), V); 26429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 26529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 26618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenekconst SVal *RegionBindingsRef::lookup(BindingKey K) const { 26729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const ClusterBindings *Cluster = lookup(K.getBaseRegion()); 26829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (!Cluster) 26929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return 0; 27029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return Cluster->lookup(K); 27129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 27229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 27329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenekconst SVal *RegionBindingsRef::lookup(const MemRegion *R, 27418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek BindingKey::Kind k) const { 27529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return lookup(BindingKey::Make(R, k)); 27629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 27729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 27829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekRegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { 27929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const MemRegion *Base = K.getBaseRegion(); 28029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const ClusterBindings *Cluster = lookup(Base); 28129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (!Cluster) 28229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return *this; 28329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 28429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek ClusterBindings NewCluster = CBFactory.remove(*Cluster, K); 28529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (NewCluster.isEmpty()) 28629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return remove(Base); 28729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return add(Base, NewCluster); 28829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 28929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek 29029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekRegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, 29129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek BindingKey::Kind k){ 29229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return removeBinding(BindingKey::Make(R, k)); 29329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek} 294baf03a7c0a846632396f9f5a19f6cd45bbe2b926Zhongxing Xu 29550dc1b3c851b5700ea32f81ed360586617e2c92fTed Kremenek//===----------------------------------------------------------------------===// 2969af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Fine-grained control of RegionStoreManager. 2979af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 2989af46f59242cfaec74fa491a66724970478263ebTed Kremenek 2999af46f59242cfaec74fa491a66724970478263ebTed Kremeneknamespace { 300ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamstruct minimal_features_tag {}; 301ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamstruct maximal_features_tag {}; 3021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 303ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass RegionStoreFeatures { 3049af46f59242cfaec74fa491a66724970478263ebTed Kremenek bool SupportsFields; 3059af46f59242cfaec74fa491a66724970478263ebTed Kremenekpublic: 3069af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures(minimal_features_tag) : 3070752d6d06721c55e5586cd2431d1239c0c8d27aeTed Kremenek SupportsFields(false) {} 3081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3099af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures(maximal_features_tag) : 3100752d6d06721c55e5586cd2431d1239c0c8d27aeTed Kremenek SupportsFields(true) {} 3111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3129af46f59242cfaec74fa491a66724970478263ebTed Kremenek void enableFields(bool t) { SupportsFields = t; } 3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3149af46f59242cfaec74fa491a66724970478263ebTed Kremenek bool supportsFields() const { return SupportsFields; } 3159af46f59242cfaec74fa491a66724970478263ebTed Kremenek}; 3169af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 3179af46f59242cfaec74fa491a66724970478263ebTed Kremenek 3189af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 31950dc1b3c851b5700ea32f81ed360586617e2c92fTed Kremenek// Main RegionStore logic. 32050dc1b3c851b5700ea32f81ed360586617e2c92fTed Kremenek//===----------------------------------------------------------------------===// 321c48ea6e51dd0da0a3def87f148240718ffaaeb0dTed Kremenek 322178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xunamespace { 323658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaksclass invalidateRegionsWorker; 3241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 325ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass RegionStoreManager : public StoreManager { 32629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenekpublic: 3279af46f59242cfaec74fa491a66724970478263ebTed Kremenek const RegionStoreFeatures Features; 328258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 329451ac091cd1868433985396a25cbbf2092ae8ca9Ted Kremenek RegionBindings::Factory RBFactory; 33029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek mutable ClusterBindings::Factory CBFactory; 331e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 33228743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose typedef std::vector<SVal> SValListTy; 33328743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Roseprivate: 33428743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose typedef llvm::DenseMap<const LazyCompoundValData *, 33528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose SValListTy> LazyBindingsMapTy; 33628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose LazyBindingsMapTy LazyBindingsMap; 33728743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 338258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// The largest number of fields a struct can have and still be 339258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// considered "small". 340258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// 341258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// This is currently used to decide whether or not it is worth "forcing" a 342258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// LazyCompoundVal on bind. 343258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// 344258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// This is controlled by 'region-store-small-struct-limit' option. 345258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// To disable all small-struct-dependent behavior, set the option to "0". 346258277d5a922e06ef523f7805900689b680ddc7dJordan Rose unsigned SmallStructLimit; 347258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 348658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks /// \brief A helper used to populate the work list with the given set of 349658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks /// regions. 350658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks void populateWorkList(invalidateRegionsWorker &W, 351658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks ArrayRef<SVal> Values, 352658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks bool IsArrayOfConstRegions, 353658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *TopLevelRegions); 354658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 35528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rosepublic: 35618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) 3571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose : StoreManager(mgr), Features(f), 358258277d5a922e06ef523f7805900689b680ddc7dJordan Rose RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()), 359258277d5a922e06ef523f7805900689b680ddc7dJordan Rose SmallStructLimit(0) { 360258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (SubEngine *Eng = StateMgr.getOwningEngine()) { 361258277d5a922e06ef523f7805900689b680ddc7dJordan Rose AnalyzerOptions &Options = Eng->getAnalysisManager().options; 362258277d5a922e06ef523f7805900689b680ddc7dJordan Rose SmallStructLimit = 363258277d5a922e06ef523f7805900689b680ddc7dJordan Rose Options.getOptionAsInteger("region-store-small-struct-limit", 2); 364258277d5a922e06ef523f7805900689b680ddc7dJordan Rose } 365258277d5a922e06ef523f7805900689b680ddc7dJordan Rose } 366178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 367e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 368027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek /// setImplicitDefaultValue - Set the default binding for the provided 369027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek /// MemRegion to the value implicitly defined for compound literals when 370e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek /// the value is not specified. 37118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, 37218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const MemRegion *R, QualType T); 3731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 374869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// ArrayToPointer - Emulates the "decay" of an array to a pointer 375869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// type. 'Array' represents the lvalue of the array being decayed 376869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// to a pointer, and the returned SVal represents the decayed 377869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// version of that lvalue (i.e., a pointer to the first element of 378d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// the array). This is called by ExprEngine when evaluating 379869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek /// casts from arrays to pointers. 3807f1fd2f182717d5ce6cde60398128910c90f98beAnna Zaks SVal ArrayToPointer(Loc Array, QualType ElementTy); 381b1d542a46eb71f23dafb5ce60b68247f280beb41Zhongxing Xu 38277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef getInitialStore(const LocationContext *InitLoc) { 38377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); 38417fd8632dcda97022a51effc24060eacdad9dbe0Zhongxing Xu } 38582cd37cf1cccde162d1f13eda6cdfe1398216f36Ted Kremenek 38667f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===-------------------------------------------------------------------===// 38767f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek // Binding values to regions. 38867f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===-------------------------------------------------------------------===// 38929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, 39029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const Expr *Ex, 39129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek unsigned Count, 39229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const LocationContext *LCtx, 39329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B, 39429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek InvalidatedRegions *Invalidated); 3954193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu 396658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks StoreRef invalidateRegions(Store store, 397658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks ArrayRef<SVal> Values, 398658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks ArrayRef<SVal> ConstValues, 39977a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const Expr *E, unsigned Count, 4003133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 401740d490593e0de8732a697c9f77b90ddd463863bJordan Rose const CallEvent *Call, 402658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedSymbols &IS, 40341988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks InvalidatedSymbols &ConstIS, 404658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *Invalidated, 405658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *InvalidatedTopLevel, 406658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *InvalidatedTopLevelConst); 4071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 408e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose bool scanReachableSymbols(Store S, const MemRegion *R, 409e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose ScanReachableSymbols &Callbacks); 410e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 41118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, 41229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const SubRegion *R); 4131e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 414e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekpublic: // Part of public interface to class. 415e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek 41618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek virtual StoreRef Bind(Store store, Loc LV, SVal V) { 41718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); 41818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek } 41918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek 42018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); 42153bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 42254460091f3987cda47a2604b07a9fb4642068ddaZhongxing Xu // BindDefault is only used to initialize a region with a default value. 42377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef BindDefault(Store store, const MemRegion *R, SVal V) { 42429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B = getRegionBindings(store); 42529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek assert(!B.lookup(R, BindingKey::Default)); 42629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek assert(!B.lookup(R, BindingKey::Direct)); 42729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return StoreRef(B.addBinding(R, BindingKey::Default, V) 42829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek .asImmutableMap() 42929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek .getRootWithoutRetain(), *this); 430a5ce966d1a23d84aa5e849cf0ed62494e736ea6aZhongxing Xu } 431a5ce966d1a23d84aa5e849cf0ed62494e736ea6aZhongxing Xu 432258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// Attempt to extract the fields of \p LCV and bind them to the struct region 433258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// \p R. 434258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// 435258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// This path is used when it seems advantageous to "force" loading the values 436258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// within a LazyCompoundVal to bind memberwise to the struct region, rather 437258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// than using a Default binding at the base of the entire region. This is a 438258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// heuristic attempting to avoid building long chains of LazyCompoundVals. 439258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// 440258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// \returns The updated store bindings, or \c None if binding non-lazily 441258277d5a922e06ef523f7805900689b680ddc7dJordan Rose /// would be too expensive. 442258277d5a922e06ef523f7805900689b680ddc7dJordan Rose Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B, 443258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const TypedValueRegion *R, 444258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const RecordDecl *RD, 445258277d5a922e06ef523f7805900689b680ddc7dJordan Rose nonloc::LazyCompoundVal LCV); 446258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 44767f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// BindStruct - Bind a compound value to a structure. 44818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef bindStruct(RegionBindingsConstRef B, 44918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion* R, SVal V); 4501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4518667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek /// BindVector - Bind a compound value to a vector. 45218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef bindVector(RegionBindingsConstRef B, 45318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion* R, SVal V); 4548667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 45518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef bindArray(RegionBindingsConstRef B, 45618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion* R, 45718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal V); 4581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4595ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose /// Clears out all bindings in the given region and assigns a new value 4605ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose /// as a Default binding. 46118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef bindAggregate(RegionBindingsConstRef B, 46218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedRegion *R, 46318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal DefaultVal); 46424194ef08ef3816d63686e2cac6d42795a015c68Zhongxing Xu 46556a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek /// \brief Create a new store with the specified binding removed. 466ad0fe03b897f9486191e75c8d90c3ffa9b4fd6a5Ted Kremenek /// \param ST the original store, that is the basis for the new store. 467ad0fe03b897f9486191e75c8d90c3ffa9b4fd6a5Ted Kremenek /// \param L the location whose binding should be removed. 46818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek virtual StoreRef killBinding(Store ST, Loc L); 469e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 47077a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek void incrementReferenceCount(Store store) { 47129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek getRegionBindings(store).manualRetain(); 47277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek } 47377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek 47477a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek /// If the StoreManager supports it, decrement the reference count of 47577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek /// the specified Store object. If the reference count hits 0, the memory 47677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek /// associated with the object is recycled. 47777a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek void decrementReferenceCount(Store store) { 47829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek getRegionBindings(store).manualRelease(); 47977a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek } 480fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek 481fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek bool includedInBindings(Store store, const MemRegion *region) const; 48267f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek 4831437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// \brief Return the value bound to specified location in a given state. 4841437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// 48567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// The high level logic for this method is this: 4861437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// getBinding (L) 48767f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// if L has binding 48867f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return L's binding 48967f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// else if L is in killset 49067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return unknown 49167f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// else 49267f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// if L is on stack or heap 49367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return undefined 49467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// else 49567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// return symbolic 49618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek virtual SVal getBinding(Store S, Loc L, QualType T) { 49718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return getBinding(getRegionBindings(S), L, T); 49818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek } 49918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek 50018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); 501490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu 50218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); 503c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu 50418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); 5051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 50618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); 5071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 50818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); 5091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5101437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks SVal getBindingForLazySymbol(const TypedValueRegion *R); 5111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 51218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 51318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion *R, 514262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose QualType Ty); 515613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 51611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose SVal getLazyBinding(const SubRegion *LazyBindingRegion, 51718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef LazyBinding); 5181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5191437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// Get bindings for the values in a struct and return a CompoundVal, used 5201437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks /// when doing struct copy: 5211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump /// struct s x, y; 5220b242ecdd5755e8662386b528aa0a5153ec0121bZhongxing Xu /// x = y; 5230b242ecdd5755e8662386b528aa0a5153ec0121bZhongxing Xu /// y's value is retrieved by this method. 524978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); 525978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); 526978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); 5271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 528dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek /// Used to lazily generate derived symbols for bindings that are defined 529deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose /// implicitly by default bindings in a super region. 530deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose /// 531deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose /// Note that callers may need to specially handle LazyCompoundVals, which 532deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose /// are returned as is in case the caller needs to treat them differently. 53318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 5341437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const MemRegion *superR, 5351437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const TypedValueRegion *R, 5361437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType Ty); 537dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 53865f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose /// Get the state and region whose binding this region \p R corresponds to. 53965f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose /// 54065f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose /// If there is no lazy binding for \p R, the returned value will have a null 54165f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose /// \c second. Note that a null pointer can represents a valid Store. 54211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose std::pair<Store, const SubRegion *> 54311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, 54411f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose const SubRegion *originalRegion); 5451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 54628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose /// Returns the cached set of interesting SVals contained within a lazy 54728743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose /// binding. 54828743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose /// 54928743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose /// The precise value of "interesting" is determined for the purposes of 55028743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose /// RegionStore's internal analysis. It must always contain all regions and 55128743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose /// symbols, but may omit constants and other kinds of SVal. 55228743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); 55328743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 55467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 55567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek // State pruning. 55667f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 5571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 558db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 55967f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek /// It returns a new Store with these values removed. 56077a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 561bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek SymbolReaper& SymReaper); 5627fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 56367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 56467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek // Region "extents". 56567f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 5661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 56732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // FIXME: This method will soon be eliminated; see the note in Store.h. 5688bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, 5693ed04d37573c566205d965d2e91d54ccae898d0aZhongxing Xu const MemRegion* R, QualType EleTy); 57063123d8e48d47920f20eb277550ff40a92493e21Zhongxing Xu 57167f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 5726e3f01cef27dd6cc7e36769618820c5b984f61daZhongxing Xu // Utility methods. 57367f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek //===------------------------------------------------------------------===// 5741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 57529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef getRegionBindings(Store store) const { 57629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return RegionBindingsRef(CBFactory, 57729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek static_cast<const RegionBindings::TreeTy*>(store), 57829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RBFactory.getTreeFactory()); 57967f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek } 58067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek 5819c378f705405d37f49795d5e915989de774fe11fTed Kremenek void print(Store store, raw_ostream &Out, const char* nl, 58253ba0b636194dbeaa65a6f85316c9397a0c5298bTed Kremenek const char *sep); 583a15f7ac7729b74d1d8bef0c009b803a4bbef20d3Zhongxing Xu 58467f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek void iterBindings(Store store, BindingsHandler& f) { 58529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B = getRegionBindings(store); 58629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 5871e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = I.getData(); 5881e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 5891e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 5901e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const BindingKey &K = CI.getKey(); 5911e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!K.isDirect()) 5921e934431adba0f459668a59c6059b9596fd627b4Jordan Rose continue; 5931e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { 5941e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // FIXME: Possibly incorporate the offset? 5951e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!f.HandleBinding(*this, store, R, CI.getData())) 5961e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return; 5971e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 5980e9910f8fe2600187e876adfb5d4b434100850e3Ted Kremenek } 5990e9910f8fe2600187e876adfb5d4b434100850e3Ted Kremenek } 60067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek } 601178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu}; 602178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 603178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu} // end anonymous namespace 604178927517fa09ddbb04dc8ef725b5716c18aae21Zhongxing Xu 6059af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 6069af46f59242cfaec74fa491a66724970478263ebTed Kremenek// RegionStore creation. 6079af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 6089af46f59242cfaec74fa491a66724970478263ebTed Kremenek 60918c66fdc3c4008d335885695fe36fb5353c5f672Ted KremenekStoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) { 6109af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures F = maximal_features_tag(); 6119af46f59242cfaec74fa491a66724970478263ebTed Kremenek return new RegionStoreManager(StMgr, F); 6129af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 6139af46f59242cfaec74fa491a66724970478263ebTed Kremenek 6141437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksStoreManager * 6151437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaksento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { 6169af46f59242cfaec74fa491a66724970478263ebTed Kremenek RegionStoreFeatures F = minimal_features_tag(); 6179af46f59242cfaec74fa491a66724970478263ebTed Kremenek F.enableFields(true); 6189af46f59242cfaec74fa491a66724970478263ebTed Kremenek return new RegionStoreManager(StMgr, F); 61995c7b00fe857a61a19185483aa0d85492ec9e258Ted Kremenek} 62095c7b00fe857a61a19185483aa0d85492ec9e258Ted Kremenek 621a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek 6229af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 623a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek// Region Cluster analysis. 624a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek//===----------------------------------------------------------------------===// 625a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 626a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremeneknamespace { 627e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose/// Used to determine which global regions are automatically included in the 628e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose/// initial worklist of a ClusterAnalysis. 629e0208ff84598f48e0aafecf5b543afeff8574045Jordan Roseenum GlobalsFilterKind { 630e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose /// Don't include any global regions. 631e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GFK_None, 632e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose /// Only include system globals. 633e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GFK_SystemOnly, 634e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose /// Include all global regions. 635e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GFK_All 636e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose}; 637e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose 6385499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenektemplate <typename DERIVED> 639a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenekclass ClusterAnalysis { 640a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenekprotected: 6411e934431adba0f459668a59c6059b9596fd627b4Jordan Rose typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; 642f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose typedef llvm::PointerIntPair<const MemRegion *, 1, bool> WorkListElement; 643f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose typedef SmallVector<WorkListElement, 10> WorkList; 6441e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 6451e934431adba0f459668a59c6059b9596fd627b4Jordan Rose llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; 6461e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 6475499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek WorkList WL; 648a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 649a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek RegionStoreManager &RM; 650a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek ASTContext &Ctx; 651c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SValBuilder &svalBuilder; 652a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 65329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B; 6545499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 655e0208ff84598f48e0aafecf5b543afeff8574045Jordan Roseprivate: 656e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GlobalsFilterKind GlobalsFilter; 657e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose 658e0208ff84598f48e0aafecf5b543afeff8574045Jordan Roseprotected: 6591e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *getCluster(const MemRegion *R) { 6601e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return B.lookup(R); 6611e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 6621e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 663e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose /// Returns true if the memory space of the given region is one of the global 664e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose /// regions specially included at the start of analysis. 665e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose bool isInitiallyIncludedGlobalRegion(const MemRegion *R) { 666e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose switch (GlobalsFilter) { 667e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose case GFK_None: 668e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose return false; 669e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose case GFK_SystemOnly: 670e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose return isa<GlobalSystemSpaceRegion>(R->getMemorySpace()); 671e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose case GFK_All: 672e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()); 673e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose } 674e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose 675e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose llvm_unreachable("unknown globals filter"); 676e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose } 677e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose 678a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenekpublic: 67918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 680e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose RegionBindingsRef b, GlobalsFilterKind GFK) 681c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek : RM(rm), Ctx(StateMgr.getContext()), 682c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek svalBuilder(StateMgr.getSValBuilder()), 683e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose B(b), GlobalsFilter(GFK) {} 6845499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 68529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef getRegionBindings() const { return B; } 6865499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 6875499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool isVisited(const MemRegion *R) { 6881e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return Visited.count(getCluster(R)); 6895499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 690a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 691d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek void GenerateClusters() { 6921e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Scan the entire set of bindings and record the region clusters. 69329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 69429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RI != RE; ++RI){ 6951e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base = RI.getKey(); 6961e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 6971e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = RI.getData(); 6981e934431adba0f459668a59c6059b9596fd627b4Jordan Rose assert(!Cluster.isEmpty() && "Empty clusters should be removed"); 6991e934431adba0f459668a59c6059b9596fd627b4Jordan Rose static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); 7001e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 701e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose // If this is an interesting global region, add it the work list up front. 702e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose if (isInitiallyIncludedGlobalRegion(Base)) 703e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose AddToWorkList(WorkListElement(Base), &Cluster); 7045499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 7055499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 7065499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 707f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { 708ab9c04fda542d096c667d6a3746d94c884f80e7bTed Kremenek if (C && !Visited.insert(C)) 709ab9c04fda542d096c667d6a3746d94c884f80e7bTed Kremenek return false; 710f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose WL.push_back(E); 7115499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return true; 712a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek } 713a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 714f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose bool AddToWorkList(const MemRegion *R, bool Flag = false) { 715f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose const MemRegion *BaseR = R->getBaseRegion(); 716f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose return AddToWorkList(WorkListElement(BaseR, Flag), getCluster(BaseR)); 7175499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 7185499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 7195499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek void RunWorkList() { 7205499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek while (!WL.empty()) { 721f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose WorkListElement E = WL.pop_back_val(); 722f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose const MemRegion *BaseR = E.getPointer(); 7235499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 724f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR), 725f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose E.getInt()); 726a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek } 727a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek } 7285499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 7291e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} 730f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} 731f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose 732f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, 733f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose bool Flag) { 734f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); 735f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose } 7365499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek}; 737a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek} 738a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 739a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek//===----------------------------------------------------------------------===// 7401004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek// Binding invalidation. 7411004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek//===----------------------------------------------------------------------===// 7421004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek 743e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rosebool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, 744e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose ScanReachableSymbols &Callbacks) { 7451e934431adba0f459668a59c6059b9596fd627b4Jordan Rose assert(R == R->getBaseRegion() && "Should only be called for base regions"); 74629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B = getRegionBindings(S); 7471e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings *Cluster = B.lookup(R); 7481e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 7491e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Cluster) 7501e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return true; 7511e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 7521e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); 7531e934431adba0f459668a59c6059b9596fd627b4Jordan Rose RI != RE; ++RI) { 7541e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (!Callbacks.scan(RI.getData())) 7551e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return false; 756e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 757a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 758e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose return true; 759e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose} 760e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 7614e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rosestatic inline bool isUnionField(const FieldRegion *FR) { 7624e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose return FR->getDecl()->getParent()->isUnion(); 7634e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose} 7644e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7654e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rosetypedef SmallVector<const FieldDecl *, 8> FieldVector; 7664e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7674e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rosevoid getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { 7684e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 7694e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7704e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose const MemRegion *Base = K.getConcreteOffsetRegion(); 7714e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose const MemRegion *R = K.getRegion(); 7724e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7734e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose while (R != Base) { 7744e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) 7754e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose if (!isUnionField(FR)) 7764e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose Fields.push_back(FR->getDecl()); 7774e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7784e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose R = cast<SubRegion>(R)->getSuperRegion(); 7794e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose } 7804e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose} 7814e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7824e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rosestatic bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { 7834e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 7844e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7854e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose if (Fields.empty()) 7864e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose return true; 7874e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7884e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose FieldVector FieldsInBindingKey; 7894e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose getSymbolicOffsetFields(K, FieldsInBindingKey); 7904e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 7914e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); 7924e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose if (Delta >= 0) 7934e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose return std::equal(FieldsInBindingKey.begin() + Delta, 7944e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose FieldsInBindingKey.end(), 7954e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose Fields.begin()); 7964e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose else 7974e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), 7984e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose Fields.begin() - Delta); 7994e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose} 8004e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 801e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose/// Collects all bindings in \p Cluster that may refer to bindings within 802e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose/// \p Top. 803e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose/// 804e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose/// Each binding is a pair whose \c first is the key (a BindingKey) and whose 805e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose/// \c second is the value (an SVal). 8060a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose/// 8070a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose/// The \p IncludeAllDefaultBindings parameter specifies whether to include 8080a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is 8090a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose/// an aggregate within a larger aggregate with a default binding. 810e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rosestatic void 811e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan RosecollectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 812e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose SValBuilder &SVB, const ClusterBindings &Cluster, 813e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose const SubRegion *Top, BindingKey TopKey, 814e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose bool IncludeAllDefaultBindings) { 8154e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose FieldVector FieldsInSymbolicSubregions; 8169d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (TopKey.hasSymbolicOffset()) { 8179d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); 8189d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose Top = cast<SubRegion>(TopKey.getConcreteOffsetRegion()); 8199d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose TopKey = BindingKey::Make(Top, BindingKey::Default); 820e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 821e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 822d764e20189dbb42b38ada383a0a159f6adc0d56cJordan Rose // Find the length (in bits) of the region being invalidated. 823e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose uint64_t Length = UINT64_MAX; 8249d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose SVal Extent = Top->getExtent(SVB); 825dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::ConcreteInt> ExtentCI = 8265251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie Extent.getAs<nonloc::ConcreteInt>()) { 827e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 828e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 829e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // Extents are in bytes but region offsets are in bits. Be careful! 8309d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); 831d764e20189dbb42b38ada383a0a159f6adc0d56cJordan Rose } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { 832d764e20189dbb42b38ada383a0a159f6adc0d56cJordan Rose if (FR->getDecl()->isBitField()) 833d764e20189dbb42b38ada383a0a159f6adc0d56cJordan Rose Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); 834e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 835e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 8369d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); 8371e934431adba0f459668a59c6059b9596fd627b4Jordan Rose I != E; ++I) { 8381e934431adba0f459668a59c6059b9596fd627b4Jordan Rose BindingKey NextKey = I.getKey(); 8399d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (NextKey.getRegion() == TopKey.getRegion()) { 8404e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose // FIXME: This doesn't catch the case where we're really invalidating a 8414e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose // region with a symbolic offset. Example: 8424e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose // R: points[i].y 8434e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose // Next: points[0].x 8444e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 8459d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (NextKey.getOffset() > TopKey.getOffset() && 8469d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose NextKey.getOffset() - TopKey.getOffset() < Length) { 8471e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 1: The next binding is inside the region we're invalidating. 848e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose // Include it. 849e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose Bindings.push_back(*I); 8504e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 8519d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose } else if (NextKey.getOffset() == TopKey.getOffset()) { 8521e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 2: The next binding is at the same offset as the region we're 8531e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // invalidating. In this case, we need to leave default bindings alone, 8541e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // since they may be providing a default value for a regions beyond what 8551e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // we're invalidating. 8561e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // FIXME: This is probably incorrect; consider invalidating an outer 8571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // struct whose first field is bound to a LazyCompoundVal. 8580a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose if (IncludeAllDefaultBindings || NextKey.isDirect()) 859e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose Bindings.push_back(*I); 8601e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 8619d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose 862e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } else if (NextKey.hasSymbolicOffset()) { 863e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 8649d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (Top->isSubRegionOf(Base)) { 8651e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 3: The next key is symbolic and we just changed something within 8661e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // its concrete region. We don't know if the binding is still valid, so 867e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose // we'll be conservative and include it. 8680a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose if (IncludeAllDefaultBindings || NextKey.isDirect()) 8694e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 870e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose Bindings.push_back(*I); 8711e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 8721e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Case 4: The next key is symbolic, but we changed a known 873e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose // super-region. In this case the binding is certainly included. 8749d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (Top == Base || BaseSR->isSubRegionOf(Top)) 8754e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 876e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose Bindings.push_back(*I); 8771e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 878e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 879e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 8809d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose} 8819d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose 882e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rosestatic void 883e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan RosecollectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 884e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose SValBuilder &SVB, const ClusterBindings &Cluster, 885e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose const SubRegion *Top, bool IncludeAllDefaultBindings) { 886e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose collectSubRegionBindings(Bindings, SVB, Cluster, Top, 887e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose BindingKey::Make(Top, BindingKey::Default), 888e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose IncludeAllDefaultBindings); 8890a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose} 8900a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose 8919d688e219caa37e60975ec8d5bebe74a176c9c2bJordan RoseRegionBindingsRef 8929d688e219caa37e60975ec8d5bebe74a176c9c2bJordan RoseRegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, 8939d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose const SubRegion *Top) { 8949d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); 8959d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose const MemRegion *ClusterHead = TopKey.getBaseRegion(); 8965db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks 8979d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (Top == ClusterHead) { 8989d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose // We can remove an entire cluster's bindings all in one go. 8999d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose return B.remove(Top); 9009d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose } 9019d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose 902df5f80f8a34e26a4fb77f48f858c7838426a0785Anna Zaks const ClusterBindings *Cluster = B.lookup(ClusterHead); 9035db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks if (!Cluster) { 9045db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks // If we're invalidating a region with a symbolic offset, we need to make 9055db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks // sure we don't treat the base region as uninitialized anymore. 9065db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks if (TopKey.hasSymbolicOffset()) { 9075db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 9085db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); 9095db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks } 9109d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose return B; 9115db8fac5f304d9973f724d5aeb4108367d36f781Anna Zaks } 9129d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose 913e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose SmallVector<BindingPair, 32> Bindings; 914e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, 915e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose /*IncludeAllDefaultBindings=*/false); 9169d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose 9179d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose ClusterBindingsRef Result(*Cluster, CBFactory); 918e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 919e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose E = Bindings.end(); 9209d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose I != E; ++I) 921e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose Result = Result.remove(I->first); 922e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 9234e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose // If we're invalidating a region with a symbolic offset, we need to make sure 9244e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose // we don't treat the base region as uninitialized anymore. 925683d25656f28937f78c815f70545139c432f1ff3Anna Zaks // FIXME: This isn't very precise; see the example in 926683d25656f28937f78c815f70545139c432f1ff3Anna Zaks // collectSubRegionBindings. 9279d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose if (TopKey.hasSymbolicOffset()) { 9289d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 9299d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), 9309d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose UnknownVal()); 9319d688e219caa37e60975ec8d5bebe74a176c9c2bJordan Rose } 9324e674f77150b52d8e6ae82faf64fbdac79d675d3Jordan Rose 93314491490a5276ff4da9b28100fb8e7d442944288Ted Kremenek if (Result.isEmpty()) 93429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return B.remove(ClusterHead); 93523dca7d88f3e9a7925bfb2c5449499900c906633Ted Kremenek return B.add(ClusterHead, Result.asImmutableMap()); 93619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek} 93719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek 938e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremeneknamespace { 9392534528c22260211a073e192c38d0db84c70c327Ted Kremenekclass invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> 9405499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek{ 9415499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const Expr *Ex; 9425499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek unsigned Count; 9433133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx; 944bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks InvalidatedSymbols &IS; 94541988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks InvalidatedSymbols &ConstIS; 946c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose StoreManager::InvalidatedRegions *Regions; 947e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenekpublic: 9482534528c22260211a073e192c38d0db84c70c327Ted Kremenek invalidateRegionsWorker(RegionStoreManager &rm, 94918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramStateManager &stateMgr, 95029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef b, 9515499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const Expr *ex, unsigned count, 9523133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *lctx, 953bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks InvalidatedSymbols &is, 95441988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks InvalidatedSymbols &inConstIS, 955d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek StoreManager::InvalidatedRegions *r, 956e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GlobalsFilterKind GFK) 957e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, GFK), 95841988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks Ex(ex), Count(count), LCtx(lctx), IS(is), ConstIS(inConstIS), Regions(r){} 959a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 96041988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks /// \param IsConst Specifies if the region we are invalidating is constant. 96141988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks /// If it is, we invalidate all subregions, but not the base region itself. 962f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose void VisitCluster(const MemRegion *baseR, const ClusterBindings *C, 96341988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks bool IsConst); 964c1ddcabef0b0e1185b6ea35d64a1ff41dabd7626Ted Kremenek void VisitBinding(SVal V); 965a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek}; 9665b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek} 9675b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek 9682534528c22260211a073e192c38d0db84c70c327Ted Kremenekvoid invalidateRegionsWorker::VisitBinding(SVal V) { 969c1ddcabef0b0e1185b6ea35d64a1ff41dabd7626Ted Kremenek // A symbol? Mark it touched by the invalidation. 97035bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek if (SymbolRef Sym = V.getAsSymbol()) 97135bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek IS.insert(Sym); 972a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 97324c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek if (const MemRegion *R = V.getAsRegion()) { 97424c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek AddToWorkList(R); 97524c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek return; 97624c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek } 97724c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 97824c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek // Is it a LazyCompoundVal? All references get invalidated as well. 979dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::LazyCompoundVal> LCS = 9805251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie V.getAs<nonloc::LazyCompoundVal>()) { 98124c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 98228743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 98324c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 98428743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 98528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose E = Vals.end(); 98628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose I != E; ++I) 98728743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose VisitBinding(*I); 98824c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 98924c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek return; 99024c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek } 99124c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek} 99224c37ad067320e9d40978d97a73e4bca0f0eae54Ted Kremenek 993f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rosevoid invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, 994f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose const ClusterBindings *C, 995f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose bool IsConst) { 996f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose if (C) { 997f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 998f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose VisitBinding(I.getData()); 9995b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek 1000e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev // Invalidate the contents of a non-const base region. 1001f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose if (!IsConst) 1002f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose B = B.remove(baseR); 1003f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose } 1004a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 10055499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // BlockDataRegion? If so, invalidate captured variables that are passed 10065499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // by reference. 10075499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 10085499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek for (BlockDataRegion::referenced_vars_iterator 10095499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 10105499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek BI != BE; ++BI) { 1011e3ce2c10c3f6ae7b26700d758de909deab190d42Ted Kremenek const VarRegion *VR = BI.getCapturedRegion(); 10125499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek const VarDecl *VD = VR->getDecl(); 101385d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 10145499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek AddToWorkList(VR); 101585d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek } 101685d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek else if (Loc::isLocType(VR->getValueType())) { 101785d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // Map the current bindings to a Store to retrieve the value 101885d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // of the binding. If that binding itself is a region, we should 101985d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // invalidate that region. This is because a block may capture 102085d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // a pointer value, but the thing pointed by that pointer may 102185d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek // get invalidated. 102218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); 1023dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<Loc> L = V.getAs<Loc>()) { 102485d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek if (const MemRegion *LR = L->getAsRegion()) 102585d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek AddToWorkList(LR); 102685d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek } 102785d87df66a50a15a1957f7213802000b451a8ec9Ted Kremenek } 10285b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek } 10295499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 10305499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 1031a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 103241988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks // Symbolic region? 1033e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 1034e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev SymbolRef RegionSym = SR->getSymbol(); 103541988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks 103641988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks // Mark that symbol touched by the invalidation. 1037e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev if (IsConst) 1038e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev ConstIS.insert(RegionSym); 1039e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev else 1040e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev IS.insert(RegionSym); 104141988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks } 1042e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev 1043e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev // Nothing else should be done for a const region. 1044e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev if (IsConst) 1045e0262e25206bef1d7efb0cb2f37abd1e42ada4cbAnton Yartsev return; 1046f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose 1047c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose // Otherwise, we have a normal data region. Record that we touched the region. 1048c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose if (Regions) 1049c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose Regions->push_back(baseR); 1050c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose 10515499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { 10525499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Invalidate the region by setting its default value to 10535499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // conjured symbol. The type of the symbol is irrelavant. 10543baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek DefinedOrUnknownSVal V = 10553b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 105629f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek B = B.addBinding(baseR, BindingKey::Default, V); 10575499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 10585499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 1059a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 10605499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (!baseR->isBoundable()) 10615499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 1062a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 10639697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 1064018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = TR->getValueType(); 1065a4fab03fa3efd32f0c21d5dd721fe88b827c7716Ted Kremenek 1066b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose if (isInitiallyIncludedGlobalRegion(baseR)) { 1067b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose // If the region is a global and we are invalidating all globals, 1068b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose // erasing the entry is good enough. This causes all globals to be lazily 1069b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose // symbolicated from the same base symbol. 1070b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose return; 1071b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose } 1072b93fc8ebed158ed5516fd85d11e89fffaf80622bJordan Rose 1073bf1a66764a12f6cceb6ba8b349d4b74996e3786bTed Kremenek if (T->isStructureOrClassType()) { 10740b46b1bc647db68ed3511b53e96699cfe14658fdZhongxing Xu // Invalidate the region by setting its default value to 10750b46b1bc647db68ed3511b53e96699cfe14658fdZhongxing Xu // conjured symbol. The type of the symbol is irrelavant. 10763b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 10773b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek Ctx.IntTy, Count); 107829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek B = B.addBinding(baseR, BindingKey::Default, V); 10795499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 10805499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 10815b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek 10825499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 10835b290658c5af4cc186fe556311db2bfbb316c00aTed Kremenek // Set the default value of the array to conjured symbol. 10845499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek DefinedOrUnknownSVal V = 10853b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 10863133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek AT->getElementType(), Count); 108729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek B = B.addBinding(baseR, BindingKey::Default, V); 10885499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 10891004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek } 10901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 10913b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 10923b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek T,Count); 10935499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 109429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek B = B.addBinding(baseR, BindingKey::Direct, V); 10951004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek} 10961004a9f2b9eaf885e55ad8656194ef2a341db0f5Ted Kremenek 109729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekRegionBindingsRef 109829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekRegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 109929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const Expr *Ex, 110029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek unsigned Count, 110129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const LocationContext *LCtx, 110229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B, 110329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek InvalidatedRegions *Invalidated) { 1104eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // Bind the globals memory space to a new symbol that we will use to derive 1105eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // the bindings for all globals. 1106eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 110731ba6135375433b617a8587ea6cc836a014ebd86Roman Divacky SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = */ (const void*) GS, Ex, LCtx, 11083b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek /* type does not matter */ Ctx.IntTy, 11093b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek Count); 1110eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 111129f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek B = B.removeBinding(GS) 111229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek .addBinding(BindingKey::Make(GS, BindingKey::Default), V); 1113eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 1114eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // Even if there are no bindings in the global scope, we still need to 1115eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // record that we touched it. 1116eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks if (Invalidated) 1117eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks Invalidated->push_back(GS); 1118eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 1119eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks return B; 1120eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks} 1121eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 1122658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaksvoid RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, 1123658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks ArrayRef<SVal> Values, 1124658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks bool IsArrayOfConstRegions, 1125658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *TopLevelRegions) { 1126658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks for (ArrayRef<SVal>::iterator I = Values.begin(), 1127658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks E = Values.end(); I != E; ++I) { 1128658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks SVal V = *I; 1129658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks if (Optional<nonloc::LazyCompoundVal> LCS = 1130658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks V.getAs<nonloc::LazyCompoundVal>()) { 1131658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 1132658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks const SValListTy &Vals = getInterestingValues(*LCS); 1133658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 1134658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks for (SValListTy::const_iterator I = Vals.begin(), 1135658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks E = Vals.end(); I != E; ++I) { 11363d3fb9078f0112fa51d8d9862221f5544c5c80e7Anna Zaks // Note: the last argument is false here because these are 1137658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks // non-top-level regions. 1138658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks if (const MemRegion *R = (*I).getAsRegion()) 1139658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks W.AddToWorkList(R, /*IsConst=*/ false); 1140658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks } 1141658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks continue; 1142658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks } 1143658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 1144658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks if (const MemRegion *R = V.getAsRegion()) { 1145658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks if (TopLevelRegions) 1146658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks TopLevelRegions->push_back(R); 1147658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks W.AddToWorkList(R, /*IsConst=*/ IsArrayOfConstRegions); 1148658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks continue; 1149658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks } 1150658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks } 1151658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks} 1152658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 115329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekStoreRef 115429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted KremenekRegionStoreManager::invalidateRegions(Store store, 1155658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks ArrayRef<SVal> Values, 1156658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks ArrayRef<SVal> ConstValues, 115729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const Expr *Ex, unsigned Count, 115829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const LocationContext *LCtx, 115929f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const CallEvent *Call, 1160658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedSymbols &IS, 116141988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks InvalidatedSymbols &ConstIS, 1162658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *TopLevelRegions, 1163658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks InvalidatedRegions *TopLevelConstRegions, 116429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek InvalidatedRegions *Invalidated) { 1165e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GlobalsFilterKind GlobalsFilter; 1166e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose if (Call) { 1167e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose if (Call->isInSystemHeader()) 1168e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GlobalsFilter = GFK_SystemOnly; 1169e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose else 1170e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GlobalsFilter = GFK_All; 1171e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose } else { 1172e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose GlobalsFilter = GFK_None; 1173e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose } 1174e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose 1175e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose RegionBindingsRef B = getRegionBindings(store); 117641988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS, 1177e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose Invalidated, GlobalsFilter); 11785499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 11795499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Scan the bindings and generate the clusters. 1180d45d59f4aebfe6399437074ed5391928c73993bbTed Kremenek W.GenerateClusters(); 11815499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 1182537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose // Add the regions to the worklist. 1183658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks populateWorkList(W, Values, /*IsArrayOfConstRegions*/ false, 1184658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks TopLevelRegions); 1185658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks populateWorkList(W, ConstValues, /*IsArrayOfConstRegions*/ true, 1186658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks TopLevelConstRegions); 11875499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 11885499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.RunWorkList(); 11895499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 11905499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Return the new bindings. 1191f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose B = W.getRegionBindings(); 1192dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1193f8e2c06cea1548c437761cb65cfbf97d50a057a7Jordan Rose // For calls, determine which global regions should be invalidated and 1194f8e2c06cea1548c437761cb65cfbf97d50a057a7Jordan Rose // invalidate them. (Note that function-static and immutable globals are never 1195f8e2c06cea1548c437761cb65cfbf97d50a057a7Jordan Rose // invalidated by this.) 1196eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks // TODO: This could possibly be more precise with modules. 1197e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose switch (GlobalsFilter) { 1198e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose case GFK_All: 1199e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 1200e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose Ex, Count, LCtx, B, Invalidated); 1201e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose // FALLTHROUGH 1202e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose case GFK_SystemOnly: 1203eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 12043133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Ex, Count, LCtx, B, Invalidated); 1205e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose // FALLTHROUGH 1206e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose case GFK_None: 1207e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose break; 1208dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek } 1209dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 12100c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek return StoreRef(B.asStore(), *this); 1211e393f4afcd1a5c3cd73697d838b064a9b5af832fTed Kremenek} 1212e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 12139af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 12149af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Extents for regions. 12159af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 12169af46f59242cfaec74fa491a66724970478263ebTed Kremenek 12171437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksDefinedOrUnknownSVal 12188bef8238181a30e52dea380789a7e2d760eac532Ted KremenekRegionStoreManager::getSizeInElements(ProgramStateRef state, 12191437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const MemRegion *R, 12201437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType EleTy) { 1221c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder); 1222846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size); 122332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (!SizeInt) 122432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return UnknownVal(); 12251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 122632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue()); 1227555c77a27672186242019b38edac498ac9579b19Ted Kremenek 1228555c77a27672186242019b38edac498ac9579b19Ted Kremenek if (Ctx.getAsVariableArrayType(EleTy)) { 1229555c77a27672186242019b38edac498ac9579b19Ted Kremenek // FIXME: We need to track extra state to properly record the size 1230555c77a27672186242019b38edac498ac9579b19Ted Kremenek // of VLAs. Returning UnknownVal here, however, is a stop-gap so that 1231555c77a27672186242019b38edac498ac9579b19Ted Kremenek // we don't have a divide-by-zero below. 1232555c77a27672186242019b38edac498ac9579b19Ted Kremenek return UnknownVal(); 1233555c77a27672186242019b38edac498ac9579b19Ted Kremenek } 1234555c77a27672186242019b38edac498ac9579b19Ted Kremenek 123557663fe6c3c7a0fb792626537c4f3f7d3594aa66Zhongxing Xu CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy); 12361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 123732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // If a variable is reinterpreted as a type that doesn't fit into a larger 123832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // type evenly, round it down. 123932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // This is a signed value, since it's used in arithmetic with signed indices. 1240c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeIntVal(RegionSize / EleSize, false); 1241e8a964bdb46349e4fa3433c8e5104d2a0f7f5c65Zhongxing Xu} 1242e8a964bdb46349e4fa3433c8e5104d2a0f7f5c65Zhongxing Xu 12439af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 12449af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Location and region casting. 12459af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 12469af46f59242cfaec74fa491a66724970478263ebTed Kremenek 1247869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// ArrayToPointer - Emulates the "decay" of an array to a pointer 1248869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// type. 'Array' represents the lvalue of the array being decayed 1249869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// to a pointer, and the returned SVal represents the decayed 1250869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// version of that lvalue (i.e., a pointer to the first element of 1251d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// the array). This is called by ExprEngine when evaluating casts 1252869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek/// from arrays to pointers. 12537f1fd2f182717d5ce6cde60398128910c90f98beAnna ZaksSVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { 12545251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!Array.getAs<loc::MemRegionVal>()) 1255abb042f33ea8e6107a7dc8efc51d2ace329f9f48Ted Kremenek return UnknownVal(); 12561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 12575251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const MemRegion* R = Array.castAs<loc::MemRegionVal>().getRegion(); 1258c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 12597f1fd2f182717d5ce6cde60398128910c90f98beAnna Zaks return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx)); 1260b1d542a46eb71f23dafb5ce60b68247f280beb41Zhongxing Xu} 1261b1d542a46eb71f23dafb5ce60b68247f280beb41Zhongxing Xu 12629af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 12639af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Loading values from regions. 12649af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 12659af46f59242cfaec74fa491a66724970478263ebTed Kremenek 126618f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { 12675251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie assert(!L.getAs<UnknownVal>() && "location unknown"); 12685251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie assert(!L.getAs<UndefinedVal>() && "location undefined"); 1269e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 127029836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // For access to concrete addresses, return UnknownVal. Checks 127129836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // for null dereferences (and similar errors) are done by checkers, not 127229836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // the Store. 127329836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // FIXME: We can consider lazily symbolicating such memory, but we really 127429836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // should defer this when we can reason easily about symbolicating arrays 127529836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek // of bytes. 12765251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (L.getAs<loc::ConcreteInt>()) { 127729836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek return UnknownVal(); 127829836f9e4750f1ccb72c24f661c20686507f0063Ted Kremenek } 12795251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!L.getAs<loc::MemRegionVal>()) { 128014429b918bd2f4cb52abc75546a7fe37142054caArgyrios Kyrtzidis return UnknownVal(); 128114429b918bd2f4cb52abc75546a7fe37142054caArgyrios Kyrtzidis } 1282e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 12835251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); 1284a1718c78770db93d1b762620f07728a56786f2aeZhongxing Xu 1285214323b78b01ef9c1ad226f0eb5bd1187f3efa70Ted Kremenek if (isa<AllocaRegion>(MR) || 1286214323b78b01ef9c1ad226f0eb5bd1187f3efa70Ted Kremenek isa<SymbolicRegion>(MR) || 1287214323b78b01ef9c1ad226f0eb5bd1187f3efa70Ted Kremenek isa<CodeTextRegion>(MR)) { 12887b050306b0ba3e7e564126fb12aca64b4c0b3f54Tom Care if (T.isNull()) { 1289ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1290ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks T = TR->getLocationType(); 1291ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks else { 1292ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks const SymbolicRegion *SR = cast<SymbolicRegion>(MR); 1293732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted Kremenek T = SR->getSymbol()->getType(); 1294ce8ef16b1c58a304b7b59fad9836ad32d6ed020cAnna Zaks } 12957b050306b0ba3e7e564126fb12aca64b4c0b3f54Tom Care } 129681491854222ad25953a643ce8efa0d6ea295ccfeZhongxing Xu MR = GetElementZeroRegion(MR, T); 12977b050306b0ba3e7e564126fb12aca64b4c0b3f54Tom Care } 12981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1299869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1300869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // instead of 'Loc', and have the other Loc cases handled at a higher level. 13019697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1302018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType RTy = R->getValueType(); 130353bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 1304beac9e3772e255f89dad0abe34811953121912b2Ted Kremenek // FIXME: we do not yet model the parts of a complex type, so treat the 1305beac9e3772e255f89dad0abe34811953121912b2Ted Kremenek // whole thing as "unknown". 1306beac9e3772e255f89dad0abe34811953121912b2Ted Kremenek if (RTy->isAnyComplexType()) 1307beac9e3772e255f89dad0abe34811953121912b2Ted Kremenek return UnknownVal(); 1308beac9e3772e255f89dad0abe34811953121912b2Ted Kremenek 1309869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // FIXME: We should eventually handle funny addressing. e.g.: 1310869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // 1311869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // int x = ...; 1312869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // int *p = &x; 1313869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // char *q = (char*) p; 1314869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // char c = *q; // returns the first byte of 'x'. 1315869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // 1316869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // Such funny addressing will occur due to layering of regions. 1317fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor if (RTy->isStructureOrClassType()) 131818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return getBindingForStruct(B, R); 13191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1320d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek // FIXME: Handle unions. 1321d4e5a606c9c64e24c05e5f4610796087e911fb9cTed Kremenek if (RTy->isUnionType()) 1322c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return UnknownVal(); 13233e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu 13249955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose if (RTy->isArrayType()) { 13259955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose if (RTy->isConstantArrayType()) 132618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return getBindingForArray(B, R); 13279955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose else 13289955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose return UnknownVal(); 13299955e708ffadb479b82b26d93dfcf0f5a2a6e372Jordan Rose } 13303e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu 13311038f9f69978ea99efccdda01f66215a1c56dc55Zhongxing Xu // FIXME: handle Vector types. 13321038f9f69978ea99efccdda01f66215a1c56dc55Zhongxing Xu if (RTy->isVectorType()) 1333c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return UnknownVal(); 133499c2030f917a76b792848e37d635067c902f96b2Zhongxing Xu 133599c2030f917a76b792848e37d635067c902f96b2Zhongxing Xu if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 133618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return CastRetrievedVal(getBindingForField(B, FR), FR, T, false); 1337c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 1338c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1339c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Here we actually perform an implicit conversion from the loaded 1340c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // value to the element type. Eventually we want to compose these values 1341c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // more intelligently. For example, an 'element' can encompass multiple 1342c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // bound regions (e.g., several bound bytes), or could be a subset of 1343c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // a larger value. 134418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return CastRetrievedVal(getBindingForElement(B, ER), ER, T, false); 1345e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek } 1346c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 1347c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1348c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Here we actually perform an implicit conversion from the loaded 1349c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // value to the ivar type. What we should model is stores to ivars 1350c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // that blow past the extent of the ivar. If the address of the ivar is 1351c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // reinterpretted, it is possible we stored a different value that could 1352c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // fit within the ivar. Either we need to cast these when storing them 1353c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // or reinterpret them lazily (as we do here). 135418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T, false); 1355c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek } 13561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1357c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1358c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Here we actually perform an implicit conversion from the loaded 1359c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // value to the variable type. What we should model is stores to variables 1360c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // that blow past the extent of the variable. If the address of the 1361c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // variable is reinterpretted, it is possible we stored a different value 1362c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // that could fit within the variable. Either we need to cast these when 1363e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek // storing them or reinterpret them lazily (as we do here). 136418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return CastRetrievedVal(getBindingForVar(B, VR), VR, T, false); 1365c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek } 136625c545788da6e3a725206cfa378b9b83a7da6024Ted Kremenek 136729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek const SVal *V = B.lookup(R, BindingKey::Direct); 136853bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 13694193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu // Check if the region has a binding. 13704193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu if (V) 1371c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return *V; 1372869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek 1373869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // The location does not have a bound value. This means that it has 1374869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // the value it had upon its creation and/or entry to the analyzed 1375869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // function/method. These are either symbolic values or 'undefined'. 1376de0d26310191215a6d1d189dc419f87af18ce6beTed Kremenek if (R->hasStackNonParametersStorage()) { 1377869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // All stack variables are considered to have undefined values 1378869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // upon creation. All heap allocated blocks are considered to 1379869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // have undefined values as well unless they are explicitly bound 1380869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek // to specific values. 1381c999ed792900026c462027e546d63c3f39310755Zhongxing Xu return UndefinedVal(); 1382869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek } 1383869fb4a8c5e53952fce508a690646ab9e3192f30Ted Kremenek 1384bb2b433ae14ca18e88a46032096ce5ec5c05c8e7Ted Kremenek // All other values are symbolic. 1385c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 138653bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu} 13871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 13889f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaksstatic QualType getUnderlyingType(const SubRegion *R) { 13899f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks QualType RegionTy; 13909f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) 13919f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks RegionTy = TVR->getValueType(); 13929f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks 13939f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 13949f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks RegionTy = SR->getSymbol()->getType(); 13959f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks 13969f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks return RegionTy; 13979f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks} 13989f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks 139911f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// Checks to see if store \p B has a lazy binding for region \p R. 140011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// 140111f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected 140211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// if there are additional bindings within \p R. 140311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// 140411f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// Note that unlike RegionStoreManager::findLazyBinding, this will not search 140511f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose/// for lazy bindings for super-regions of \p R. 140611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rosestatic Optional<nonloc::LazyCompoundVal> 140711f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan RosegetExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, 140811f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose const SubRegion *R, bool AllowSubregionBindings) { 140911f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Optional<SVal> V = B.getDefaultBinding(R); 141011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (!V) 1411472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose return None; 141211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 141311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); 141411f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (!LCV) 1415472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose return None; 141611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 14179f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks // If the LCV is for a subregion, the types might not match, and we shouldn't 14189f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks // reuse the binding. 14199f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks QualType RegionTy = getUnderlyingType(R); 14209f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks if (!RegionTy.isNull() && 14219f3495aeaa24da4eacf8f6c274adcef65e2f3617Anna Zaks !RegionTy->isVoidPointerType()) { 142211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose QualType SourceRegionTy = LCV->getRegion()->getValueType(); 142311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) 1424472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose return None; 142511f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose } 142611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 142711f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (!AllowSubregionBindings) { 142811f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose // If there are any other bindings within this region, we shouldn't reuse 142911f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose // the top-level binding. 1430e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose SmallVector<BindingPair, 16> Bindings; 1431e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, 1432e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose /*IncludeAllDefaultBindings=*/true); 1433e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose if (Bindings.size() > 1) 1434472b0613ff67e8598ef6a69bb478c721b21a9294Jordan Rose return None; 143511f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose } 143611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 143711f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose return *LCV; 143811f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose} 143965f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose 144011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 144111f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rosestd::pair<Store, const SubRegion *> 144211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan RoseRegionStoreManager::findLazyBinding(RegionBindingsConstRef B, 144311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose const SubRegion *R, 144411f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose const SubRegion *originalRegion) { 144545fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek if (originalRegion != R) { 144611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (Optional<nonloc::LazyCompoundVal> V = 144711f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose getExistingLazyBinding(svalBuilder, B, R, true)) 144811f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose return std::make_pair(V->getStore(), V->getRegion()); 144945fa623886dfb6a23b3cfd6d8764e05884382180Ted Kremenek } 145011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 145111f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose typedef std::pair<Store, const SubRegion *> StoreRegionPair; 145211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose StoreRegionPair Result = StoreRegionPair(); 145311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 1454a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 145511f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), 145611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose originalRegion); 14571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 145811f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (Result.second) 145911f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); 146011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 146111f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 146211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), 146311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose originalRegion); 146411f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose 146511f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (Result.second) 146611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); 14671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 146865f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose } else if (const CXXBaseObjectRegion *BaseReg = 146965f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose dyn_cast<CXXBaseObjectRegion>(R)) { 147065f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose // C++ base object region is another kind of region that we should blast 147165f991ccbec43b4a860f70594c92528ee8fb7c6fJordan Rose // through to look for lazy compound value. It is like a field region. 147211f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), 147311f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose originalRegion); 1474d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu 147511f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (Result.second) 147611f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, 147711f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose Result.second); 1478d074441e027471a914cbb909a7aad1d43224950fZhongxing Xu } 1479613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 148011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose return Result; 1481a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek} 148253bcdd4fadc022f4a37a929954a72af98f32e91aZhongxing Xu 148318f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, 1484a8f2362307b436023095e66efd678ae591c02184Anna Zaks const ElementRegion* R) { 1485a8f2362307b436023095e66efd678ae591c02184Anna Zaks // We do not currently model bindings of the CompoundLiteralregion. 148650b5a5c32e07301e4edcc01aca1f8a49a128c66cAnna Zaks if (isa<CompoundLiteralRegion>(R->getBaseRegion())) 148750b5a5c32e07301e4edcc01aca1f8a49a128c66cAnna Zaks return UnknownVal(); 1488a8f2362307b436023095e66efd678ae591c02184Anna Zaks 1489c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu // Check if the region has a binding. 149029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &V = B.getDirectBinding(R)) 1491c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu return *V; 1492c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu 1493921109ab9c4a114da4588566bc56c09443ea2339Ted Kremenek const MemRegion* superR = R->getSuperRegion(); 1494921109ab9c4a114da4588566bc56c09443ea2339Ted Kremenek 1495c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu // Check if the region is an element region of a string literal. 1496921109ab9c4a114da4588566bc56c09443ea2339Ted Kremenek if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { 1497e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek // FIXME: Handle loads from strings where the literal is treated as 149895efe0f7fb2ff2d83f9e6f97d707a79370034d73Ted Kremenek // an integer, e.g., *((unsigned int*)"hello") 1499018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1500df70700f5aa5744d7f70fb3e6610ff434f643a71Jordan Rose if (!Ctx.hasSameUnqualifiedType(T, R->getElementType())) 150195efe0f7fb2ff2d83f9e6f97d707a79370034d73Ted Kremenek return UnknownVal(); 1502e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1503c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu const StringLiteral *Str = StrR->getStringLiteral(); 1504c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu SVal Idx = R->getIndex(); 1505dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) { 1506c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu int64_t i = CI->getValue().getSExtValue(); 150731d922fdbf52ea14856f395cb1079173b33cefcdTed Kremenek // Abort on string underrun. This can be possible by arbitrary 15081437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks // clients of getBindingForElement(). 150931d922fdbf52ea14856f395cb1079173b33cefcdTed Kremenek if (i < 0) 151031d922fdbf52ea14856f395cb1079173b33cefcdTed Kremenek return UndefinedVal(); 1511729aa06b9d190ce01eccb7108415e698fc52f6f4Ted Kremenek int64_t length = Str->getLength(); 1512729aa06b9d190ce01eccb7108415e698fc52f6f4Ted Kremenek // Technically, only i == length is guaranteed to be null. 1513167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // However, such overflows should be caught before reaching this point; 1514167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // the only time such an access would be made is if a string literal was 1515167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // used to initialize a larger array. 1516729aa06b9d190ce01eccb7108415e698fc52f6f4Ted Kremenek char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1517c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeIntVal(c, T); 1518c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu } 1519c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu } 15201e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek 15211e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek // Check for loads from a code text region. For such loads, just give up. 152208140f99e507cfd593146bdf2efb01b24da822faTed Kremenek if (isa<CodeTextRegion>(superR)) 15231e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek return UnknownVal(); 15241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1525a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // Handle the case where we are indexing into a larger scalar object. 1526a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // For example, this handles: 1527a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // int x = ... 1528a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // char *y = &x; 1529a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // return *y; 1530a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // FIXME: This is a hack, and doesn't do anything really intelligent yet. 15317caf9b369cba6edaf6eac25121cbc65ee938f14dZhongxing Xu const RegionRawOffset &O = R->getAsArrayOffset(); 1532c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek 1533c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek // If we cannot reason about the offset, return an unknown value. 1534c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek if (!O.getRegion()) 1535c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek return UnknownVal(); 1536c46d6410947b18ac4c52cff4d0f8021b10a57c1eTed Kremenek 15379697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *baseR = 15389697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1539018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType baseT = baseR->getValueType(); 1540a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (baseT->isScalarType()) { 1541a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek QualType elemT = R->getElementType(); 1542a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (elemT->isScalarType()) { 1543a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 154429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &V = B.getDirectBinding(superR)) { 1545a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (SymbolRef parentSym = V->getAsSymbol()) 1546c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1547dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1548a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek if (V->isUnknownOrUndef()) 1549a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek return *V; 1550a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // Other cases: give up. We are indexing into a larger object 1551a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek // that has some value, but we don't know how to handle that yet. 1552a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek return UnknownVal(); 1553a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek } 1554a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek } 1555a709b87de4644c05d7787f9fb246d2b4dc38bf51Ted Kremenek } 1556566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek } 15577abe019c2840e3890993c879c65acde9ea316166Zhongxing Xu } 1558262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose return getBindingForFieldOrElementCommon(B, R, R->getElementType()); 1559c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu} 1560c00346fff95b961241abffdcc257a90e6cb1cb4bZhongxing Xu 156118f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, 156218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const FieldRegion* R) { 1563490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu 1564490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu // Check if the region has a binding. 156529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &V = B.getDirectBinding(R)) 1566490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu return *V; 1567490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu 1568018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType Ty = R->getValueType(); 1569262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose return getBindingForFieldOrElementCommon(B, R, Ty); 1570566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek} 15711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1572dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted KremenekOptional<SVal> 157318f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 15741437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const MemRegion *superR, 15751437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const TypedValueRegion *R, 15761437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks QualType Ty) { 1577dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 157829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { 1579613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek const SVal &val = D.getValue(); 1580613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (SymbolRef parentSym = val.getAsSymbol()) 1581c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1582dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1583613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (val.isZeroConstant()) 1584c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.makeZeroVal(Ty); 1585dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1586613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek if (val.isUnknownOrUndef()) 1587613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek return val; 1588613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 1589deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // Lazy bindings are usually handled through getExistingLazyBinding(). 1590deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // We should unify these two code paths at some point. 15915251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (val.getAs<nonloc::LazyCompoundVal>()) 1592deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose return val; 1593dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 1594b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Unknown default value"); 1595dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek } 1596dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 159766874fb18afbffb8b2ca05576851a64534be3352David Blaikie return None; 1598dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek} 1599dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 160011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan RoseSVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, 160118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef LazyBinding) { 16020e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose SVal Result; 160318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) 16040e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose Result = getBindingForElement(LazyBinding, ER); 16050e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose else 16060e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose Result = getBindingForField(LazyBinding, 16070e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose cast<FieldRegion>(LazyBindingRegion)); 16080e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose 1609deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 16100e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // default value for /part/ of an aggregate from a default value for the 16110e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // /entire/ aggregate. The most common case of this is when struct Outer 16120e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // has as its first member a struct Inner, which is copied in from a stack 16130e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // variable. In this case, even if the Outer's default value is symbolic, 0, 16140e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // or unknown, it gets overridden by the Inner's default value of undefined. 16150e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // 16160e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // This is a general problem -- if the Inner is zero-initialized, the Outer 16170e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // will now look zero-initialized. The proper way to solve this is with a 16180e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // new version of RegionStore that tracks the extent of a binding as well 16190e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // as the offset. 16200e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // 16210e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // This hack only takes care of the undefined case because that can very 16220e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose // quickly result in a warning. 16230e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose if (Result.isUndef()) 16240e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose Result = UnknownVal(); 16250e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose 16260e450cbd94e5936fdecf42b810069e7becd3938dJordan Rose return Result; 1627613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek} 1628613744181322b9680a4b3d59cce87d7e5e572c99Ted Kremenek 162918f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal 163018f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 16319697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R, 1632262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose QualType Ty) { 1633566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek 16341437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks // At this point we have already checked in either getBindingForElement or 16351437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks // getBindingForField if 'R' has a direct binding. 16368f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek 16378f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek // Lazy binding? 16388f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek Store lazyBindingStore = NULL; 163911f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose const SubRegion *lazyBindingRegion = NULL; 164011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose llvm::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); 16418f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek if (lazyBindingRegion) 164218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return getLazyBinding(lazyBindingRegion, 164318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek getRegionBindings(lazyBindingStore)); 16448f40afbf7740c39fccaa4b8cc5aa2814d5ed6fdcTed Kremenek 164531b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // Record whether or not we see a symbolic index. That can completely 164631b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // be out of scope of our lookup. 164731b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek bool hasSymbolicIndex = false; 16481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1649deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1650deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // default value for /part/ of an aggregate from a default value for the 1651deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // /entire/ aggregate. The most common case of this is when struct Outer 1652deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // has as its first member a struct Inner, which is copied in from a stack 1653deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // variable. In this case, even if the Outer's default value is symbolic, 0, 1654deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // or unknown, it gets overridden by the Inner's default value of undefined. 1655deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // 1656deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // This is a general problem -- if the Inner is zero-initialized, the Outer 1657deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // will now look zero-initialized. The proper way to solve this is with a 1658deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // new version of RegionStore that tracks the extent of a binding as well 1659deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // as the offset. 1660deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // 1661deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // This hack only takes care of the undefined case because that can very 1662deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose // quickly result in a warning. 1663deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose bool hasPartialLazyBinding = false; 1664deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose 1665262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose const SubRegion *SR = dyn_cast<SubRegion>(R); 1666262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose while (SR) { 1667262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose const MemRegion *Base = SR->getSuperRegion(); 1668deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { 1669deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose if (D->getAs<nonloc::LazyCompoundVal>()) { 1670deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose hasPartialLazyBinding = true; 1671deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose break; 1672deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose } 1673deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose 1674dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek return *D; 1675deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose } 16761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1677deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { 167831b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek NonLoc index = ER->getIndex(); 167931b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (!index.isConstant()) 168031b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek hasSymbolicIndex = true; 168131b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek } 168231b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek 168319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // If our super region is a field or element itself, walk up the region 168419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // hierarchy to see if there is a default value installed in an ancestor. 1685262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose SR = dyn_cast<SubRegion>(Base); 1686a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek } 16871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1688de0d26310191215a6d1d189dc419f87af18ce6beTed Kremenek if (R->hasStackNonParametersStorage()) { 168931b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (isa<ElementRegion>(R)) { 1690566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek // Currently we don't reason specially about Clang-style vectors. Check 1691566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek // if superR is a vector and if so return Unknown. 16929697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *typedSuperR = 1693262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose dyn_cast<TypedValueRegion>(R->getSuperRegion())) { 1694018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu if (typedSuperR->getValueType()->isVectorType()) 1695566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek return UnknownVal(); 16961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 1697566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek } 16981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 169931b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // FIXME: We also need to take ElementRegions with symbolic indexes into 170031b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // account. This case handles both directly accessing an ElementRegion 170131b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // with a symbolic offset, but also fields within an element with 170231b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek // a symbolic offset. 170331b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek if (hasSymbolicIndex) 170431b57628576a2355428fd4b57f828a3aa8423000Ted Kremenek return UnknownVal(); 1705deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose 1706deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose if (!hasPartialLazyBinding) 1707deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose return UndefinedVal(); 1708566a6faa54235590ab8d7d177dfac08586f545b0Ted Kremenek } 17091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1710bb2b433ae14ca18e88a46032096ce5ec5c05c8e7Ted Kremenek // All other values are symbolic. 1711c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 1712490b0f0877b1a6d3caf18abb4ab62ed592e13c4aZhongxing Xu} 17131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 171418f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, 17151437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks const ObjCIvarRegion* R) { 171618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek // Check if the region has a binding. 171729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &V = B.getDirectBinding(R)) 17185bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek return *V; 17191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17205bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek const MemRegion *superR = R->getSuperRegion(); 17215bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek 1722ab22ee9ede5532f35c64b8eaccb4210f3f16397dTed Kremenek // Check if the super region has a default binding. 172329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { 17245bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek if (SymbolRef parentSym = V->getAsSymbol()) 1725c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 17261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17275bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek // Other cases: give up. 17285bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek return UnknownVal(); 17295bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek } 17301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17311437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks return getBindingForLazySymbol(R); 173225c545788da6e3a725206cfa378b9b83a7da6024Ted Kremenek} 173325c545788da6e3a725206cfa378b9b83a7da6024Ted Kremenek 173418f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, 173518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const VarRegion *R) { 17361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17379031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek // Check if the region has a binding. 173829f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek if (const Optional<SVal> &V = B.getDirectBinding(R)) 17399031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek return *V; 17401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17419031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek // Lazily derive a value for the VarRegion. 17429031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek const VarDecl *VD = R->getDecl(); 17434dc1566a80648a74a19409c425809fa6a1683befTed Kremenek const MemSpaceRegion *MS = R->getMemorySpace(); 1744e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1745697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose // Arguments are always symbolic. 1746697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose if (isa<StackArgumentsSpaceRegion>(MS)) 1747697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose return svalBuilder.getRegionValueSymbolVal(R); 1748697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose 1749697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose // Is 'VD' declared constant? If so, retrieve the constant value. 1750e2b1246a24e8babf2f58c93713fba16b8edb8e2dJordan Rose if (VD->getType().isConstQualified()) 1751e2b1246a24e8babf2f58c93713fba16b8edb8e2dJordan Rose if (const Expr *Init = VD->getInit()) 1752e2b1246a24e8babf2f58c93713fba16b8edb8e2dJordan Rose if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 1753e2b1246a24e8babf2f58c93713fba16b8edb8e2dJordan Rose return *V; 1754697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose 1755697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose // This must come after the check for constants because closure-captured 1756697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose // constant variables may appear in UnknownSpaceRegion. 1757697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose if (isa<UnknownSpaceRegion>(MS)) 1758c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 17591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17604dc1566a80648a74a19409c425809fa6a1683befTed Kremenek if (isa<GlobalsSpaceRegion>(MS)) { 1761697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose QualType T = VD->getType(); 1762697a68590a75f5cd2326c8f686a6c666b51688b6Jordan Rose 176304870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose // Function-scoped static variables are default-initialized to 0; if they 176404870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose // have an initializer, it would have been processed by now. 176504870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose if (isa<StaticGlobalSpaceRegion>(MS)) 176604870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose return svalBuilder.makeZeroVal(T); 176704870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose 1768deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { 1769deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose assert(!V->getAs<nonloc::LazyCompoundVal>()); 177004870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose return V.getValue(); 1771deb8f5d533b7bcd962976ecdbc1464fe754b6de0Jordan Rose } 177281861abe9cd1669ca46e13866f77f7ece8c4c85fTed Kremenek 177304870edbea6cf88412c8c9c1eba65f7fc1fa12d9Jordan Rose return svalBuilder.getRegionValueSymbolVal(R); 17744dc1566a80648a74a19409c425809fa6a1683befTed Kremenek } 1775e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 17769031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek return UndefinedVal(); 17779031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek} 17789031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek 17791437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna ZaksSVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 17805bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek // All other values are symbolic. 1781c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return svalBuilder.getRegionValueSymbolVal(R); 17825bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek} 17835bd2fe365f29799a78a862df2d1cff365d792b63Ted Kremenek 178428743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Roseconst RegionStoreManager::SValListTy & 178528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan RoseRegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { 178628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose // First, check the cache. 178728743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); 178828743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose if (I != LazyBindingsMap.end()) 178928743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose return I->second; 179028743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 179128743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose // If we don't have a list of values cached, start constructing it. 1792206f49966f66ad7cbfe3d37c14fa7e6e7410f3beJordan Rose SValListTy List; 179328743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 179428743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose const SubRegion *LazyR = LCV.getRegion(); 179528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose RegionBindingsRef B = getRegionBindings(LCV.getStore()); 179628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 179728743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose // If this region had /no/ bindings at the time, there are no interesting 179828743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose // values to return. 179928743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); 180028743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose if (!Cluster) 1801206f49966f66ad7cbfe3d37c14fa7e6e7410f3beJordan Rose return (LazyBindingsMap[LCV.getCVData()] = llvm_move(List)); 180228743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 1803e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose SmallVector<BindingPair, 32> Bindings; 1804e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, 1805e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose /*IncludeAllDefaultBindings=*/true); 1806e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 1807e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose E = Bindings.end(); 180828743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose I != E; ++I) { 1809e33d852452c7008ccd0677aae88f1055cf1a9af1Jordan Rose SVal V = I->second; 181028743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose if (V.isUnknownOrUndef() || V.isConstant()) 181128743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose continue; 181228743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 1813dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::LazyCompoundVal> InnerLCV = 18145251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie V.getAs<nonloc::LazyCompoundVal>()) { 181528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose const SValListTy &InnerList = getInterestingValues(*InnerLCV); 181628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose List.insert(List.end(), InnerList.begin(), InnerList.end()); 181728743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose continue; 181828743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose } 181928743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 182028743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose List.push_back(V); 182128743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose } 182228743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 1823206f49966f66ad7cbfe3d37c14fa7e6e7410f3beJordan Rose return (LazyBindingsMap[LCV.getCVData()] = llvm_move(List)); 182428743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose} 182528743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose 1826978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan RoseNonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, 1827978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose const TypedValueRegion *R) { 182811f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose if (Optional<nonloc::LazyCompoundVal> V = 182911f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose getExistingLazyBinding(svalBuilder, B, R, false)) 183011f0cae4bf4f62dcc706d33c1f795d460cd64816Jordan Rose return *V; 1831978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose 1832978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); 1833752bee2493ec2931bd18899753552e3a47dc85feJordan Rose} 1834752bee2493ec2931bd18899753552e3a47dc85feJordan Rose 183518f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, 1836978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose const TypedValueRegion *R) { 1837752bee2493ec2931bd18899753552e3a47dc85feJordan Rose const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 1838752bee2493ec2931bd18899753552e3a47dc85feJordan Rose if (RD->field_empty()) 1839752bee2493ec2931bd18899753552e3a47dc85feJordan Rose return UnknownVal(); 1840752bee2493ec2931bd18899753552e3a47dc85feJordan Rose 1841978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose return createLazyBinding(B, R); 18426e3f01cef27dd6cc7e36769618820c5b984f61daZhongxing Xu} 18436e3f01cef27dd6cc7e36769618820c5b984f61daZhongxing Xu 184418f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekSVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, 1845978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose const TypedValueRegion *R) { 1846978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose assert(Ctx.getAsConstantArrayType(R->getValueType()) && 1847978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose "Only constant array types can have compound bindings."); 18487dbbc2178fb487f3a8bff03a2c9e87f727bf2b98Ted Kremenek 1849978aeac1a90020b2a0ae6c7eb7fe65aa8226f74aJordan Rose return createLazyBinding(B, R); 18503e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu} 18513e001f393d112a50e13c9a8f9a4c0d97f3f51cf4Zhongxing Xu 1852fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenekbool RegionStoreManager::includedInBindings(Store store, 1853fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek const MemRegion *region) const { 185429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B = getRegionBindings(store); 1855fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek region = region->getBaseRegion(); 18561e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18571e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Quick path: if the base is the head of a cluster, the region is live. 18581e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (B.lookup(region)) 18591e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return true; 18601e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 18611e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Slow path: if the region is the VALUE of any binding, it is live. 186229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 18631e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = RI.getData(); 18641e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 18651e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 18661e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const SVal &D = CI.getData(); 18671e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const MemRegion *R = D.getAsRegion()) 18681e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (R->getBaseRegion() == region) 18691e934431adba0f459668a59c6059b9596fd627b4Jordan Rose return true; 18701e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 1871fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek } 18721e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 1873fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek return false; 1874fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek} 1875fa7a95c62aa573a30d87c215b320b0086ed08bdcTed Kremenek 18769af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 18779af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Binding values to regions. 18789af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 18799af46f59242cfaec74fa491a66724970478263ebTed Kremenek 188056a46b51df691f857f7120aaf2d4deeff0b014deTed KremenekStoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 1881dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) 18825251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (const MemRegion* R = LV->getRegion()) 188329f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek return StoreRef(getRegionBindings(ST).removeBinding(R) 188429f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek .asImmutableMap() 188529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek .getRootWithoutRetain(), 188677a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek *this); 18871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 188856a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek return StoreRef(ST, *this); 18899af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 18909af46f59242cfaec74fa491a66724970478263ebTed Kremenek 189118f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef 189218f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { 18935251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (L.getAs<loc::ConcreteInt>()) 189418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return B; 189587453d1c39df791fb98618f6ba34b2edaae880e1Zhongxing Xu 18964193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu // If we get here, the location should be a region. 18975251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); 18981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 18994193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu // Check if the region is a struct region. 19008667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 19018667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek QualType Ty = TR->getValueType(); 190232a549a64922af0903bdb777613ae7ae4490b70fTed Kremenek if (Ty->isArrayType()) 190318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindArray(B, TR, V); 19048667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (Ty->isStructureOrClassType()) 190518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindStruct(B, TR, V); 19068667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (Ty->isVectorType()) 190718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindVector(B, TR, V); 19088667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 19091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1910e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 19110954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek // Binding directly to a symbolic region should be treated as binding 19120954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek // to element 0. 1913732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted Kremenek QualType T = SR->getSymbol()->getType(); 19144e45dba1c0234eec7b7c348dbbf568c5ac9fc471Jordan Rose if (T->isAnyPointerType() || T->isReferenceType()) 19154e45dba1c0234eec7b7c348dbbf568c5ac9fc471Jordan Rose T = T->getPointeeType(); 1916852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek 19170954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek R = GetElementZeroRegion(SR, T); 19180954cdec4b13f1b3fd4c8711e02ded914968000bTed Kremenek } 19191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1920e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // Clear out bindings that may overlap with this binding. 192118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); 192218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); 19239c9ca08fdd27fb0b025782aa41fae93612edf440Zhongxing Xu} 19249c9ca08fdd27fb0b025782aa41fae93612edf440Zhongxing Xu 192518f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef 192618f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, 192718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const MemRegion *R, 192818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek QualType T) { 1929027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek SVal V; 1930027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek 19317dfc9420babe83e236a47e752f8723bd06070d9dZhanyong Wan if (Loc::isLocType(T)) 1932c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek V = svalBuilder.makeNull(); 1933a5796f87229b4aeebca71fa6ee1790ae7a5a0382Jordan Rose else if (T->isIntegralOrEnumerationType()) 1934c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek V = svalBuilder.makeZeroVal(T); 1935fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor else if (T->isStructureOrClassType() || T->isArrayType()) { 1936027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // Set the default value to a zero constant when it is a structure 1937027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // or array. The type doesn't really matter. 1938c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek V = svalBuilder.makeZeroVal(Ctx.IntTy); 1939027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek } 1940027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek else { 1941eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // We can't represent values of this type, but we still need to set a value 1942eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // to record that the region has been initialized. 1943eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // If this assertion ever fires, a new case should be added above -- we 1944eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose // should know how to default-initialize any value we can symbolicate. 1945eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1946eda368791b21aafaf87012c8552dc5181c0ff7a1Jordy Rose V = UnknownVal(); 1947027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek } 19481c1ae6bdaf89145648484db5dfebcd04a60595c9Ted Kremenek 194918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return B.addBinding(R, BindingKey::Default, V); 1950027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek} 1951e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 195218f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef 195318f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionStoreManager::bindArray(RegionBindingsConstRef B, 195418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion* R, 195518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal Init) { 1956e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1957018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1958e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek QualType ElementTy = AT->getElementType(); 1959fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek Optional<uint64_t> Size; 1960e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1961fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1962fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek Size = CAT->getSize().getZExtValue(); 1963e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1964167cc379756e525bdf5b6b722fd78d415ed0eb2cJordy Rose // Check if the init expr is a string literal. 1965dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { 19663881866dc782c5e13b21031bd363e93fbf367167Ted Kremenek const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 19673881866dc782c5e13b21031bd363e93fbf367167Ted Kremenek 19683881866dc782c5e13b21031bd363e93fbf367167Ted Kremenek // Treat the string as a lazy compound value. 196918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek StoreRef store(B.asStore(), *this); 19705251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie nonloc::LazyCompoundVal LCV = svalBuilder.makeLazyCompoundVal(store, S) 19715251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie .castAs<nonloc::LazyCompoundVal>(); 197218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindAggregate(B, R, LCV); 19736987c7b74146b9658b1925c5981f8b0cd0672b55Zhongxing Xu } 19741a12a0ea00a62d785ce8c25e740a152015a3000aZhongxing Xu 1975a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek // Handle lazy compound values. 19765251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (Init.getAs<nonloc::LazyCompoundVal>()) 197718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindAggregate(B, R, Init); 19781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 19791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Remaining case: explicit compound values. 1980e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 1981027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek if (Init.isUnknown()) 198218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return setImplicitDefaultValue(B, R, ElementTy); 1983e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 19845251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); 19851a12a0ea00a62d785ce8c25e740a152015a3000aZhongxing Xu nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1986465373946b5ae84f7c3d890cc25cb23fd88dd650Ted Kremenek uint64_t i = 0; 19871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 198818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef NewB(B); 198918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek 1990fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 1991087d6c20876ced37d544552b43cf33332687f074Zhongxing Xu // The init list might be shorter than the array length. 19924193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu if (VI == VE) 19934193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu break; 1994a82512a2735bed5a3498e7a5f24f4c365bbd5704Zhongxing Xu 1995c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 199657663fe6c3c7a0fb792626537c4f3f7d3594aa66Zhongxing Xu const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 1997c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 1998fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor if (ElementTy->isStructureOrClassType()) 199918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = bindStruct(NewB, ER, *VI); 200059b6dca7e5160d6f2aff42b1cf077d1cbd64e330Jordy Rose else if (ElementTy->isArrayType()) 200118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = bindArray(NewB, ER, *VI); 20024193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu else 2003258277d5a922e06ef523f7805900689b680ddc7dJordan Rose NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2004c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu } 2005c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 2006027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // If the init list is shorter than the array length, set the 2007027e2667315f265a85c6241f26e8a514db219b3fTed Kremenek // array default value. 2008fee90811c665893bc27a9bfa8b116548afe1b89bTed Kremenek if (Size.hasValue() && i < Size.getValue()) 200918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = setImplicitDefaultValue(NewB, R, ElementTy); 2010087d6c20876ced37d544552b43cf33332687f074Zhongxing Xu 201118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return NewB; 2012c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu} 2013c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 201418f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, 201518f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion* R, 201618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal V) { 20178667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek QualType T = R->getValueType(); 20188667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek assert(T->isVectorType()); 20198667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs. 20208667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 20215ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose // Handle lazy compound values and symbolic values. 20225251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) 202318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindAggregate(B, R, V); 20248667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 20258667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek // We may get non-CompoundVal accidentally due to imprecise cast logic or 20268667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek // that we are binding symbolic struct value. Kill the field values, and if 20278667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek // the value is symbolic go and bind it as a "default" binding. 20285251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!V.getAs<nonloc::CompoundVal>()) { 202918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindAggregate(B, R, UnknownVal()); 20308667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 20318667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 20328667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek QualType ElemType = VT->getElementType(); 20335251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); 20348667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 20358667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek unsigned index = 0, numElements = VT->getNumElements(); 203618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef NewB(B); 203718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek 20388667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek for ( ; index != numElements ; ++index) { 20398667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (VI == VE) 20408667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek break; 20418667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 20428667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek NonLoc Idx = svalBuilder.makeArrayIndex(index); 20438667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 2044258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 20458667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek if (ElemType->isArrayType()) 204618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = bindArray(NewB, ER, *VI); 20478667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek else if (ElemType->isStructureOrClassType()) 204818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = bindStruct(NewB, ER, *VI); 20498667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek else 2050258277d5a922e06ef523f7805900689b680ddc7dJordan Rose NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2051258277d5a922e06ef523f7805900689b680ddc7dJordan Rose } 2052258277d5a922e06ef523f7805900689b680ddc7dJordan Rose return NewB; 2053258277d5a922e06ef523f7805900689b680ddc7dJordan Rose} 2054258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2055258277d5a922e06ef523f7805900689b680ddc7dJordan RoseOptional<RegionBindingsRef> 2056258277d5a922e06ef523f7805900689b680ddc7dJordan RoseRegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, 2057258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const TypedValueRegion *R, 2058258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const RecordDecl *RD, 2059258277d5a922e06ef523f7805900689b680ddc7dJordan Rose nonloc::LazyCompoundVal LCV) { 2060258277d5a922e06ef523f7805900689b680ddc7dJordan Rose FieldVector Fields; 2061258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2062258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) 2063258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (Class->getNumBases() != 0 || Class->getNumVBases() != 0) 2064258277d5a922e06ef523f7805900689b680ddc7dJordan Rose return None; 2065258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2066258277d5a922e06ef523f7805900689b680ddc7dJordan Rose for (RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end(); 2067258277d5a922e06ef523f7805900689b680ddc7dJordan Rose I != E; ++I) { 2068258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const FieldDecl *FD = *I; 2069258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (FD->isUnnamedBitfield()) 2070258277d5a922e06ef523f7805900689b680ddc7dJordan Rose continue; 2071258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2072258277d5a922e06ef523f7805900689b680ddc7dJordan Rose // If there are too many fields, or if any of the fields are aggregates, 2073258277d5a922e06ef523f7805900689b680ddc7dJordan Rose // just use the LCV as a default binding. 2074258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (Fields.size() == SmallStructLimit) 2075258277d5a922e06ef523f7805900689b680ddc7dJordan Rose return None; 2076258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2077258277d5a922e06ef523f7805900689b680ddc7dJordan Rose QualType Ty = FD->getType(); 2078258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (!(Ty->isScalarType() || Ty->isReferenceType())) 2079258277d5a922e06ef523f7805900689b680ddc7dJordan Rose return None; 2080258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2081258277d5a922e06ef523f7805900689b680ddc7dJordan Rose Fields.push_back(*I); 20828667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek } 2083258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2084258277d5a922e06ef523f7805900689b680ddc7dJordan Rose RegionBindingsRef NewB = B; 2085258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2086258277d5a922e06ef523f7805900689b680ddc7dJordan Rose for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){ 2087258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion()); 2088258277d5a922e06ef523f7805900689b680ddc7dJordan Rose SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR); 2089258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 2090258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R); 2091258277d5a922e06ef523f7805900689b680ddc7dJordan Rose NewB = bind(NewB, loc::MemRegionVal(DestFR), V); 2092258277d5a922e06ef523f7805900689b680ddc7dJordan Rose } 2093258277d5a922e06ef523f7805900689b680ddc7dJordan Rose 209418f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return NewB; 20958667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek} 20968667052a53a47a6290dc9ae98e5c3d9277df5f4aTed Kremenek 209718f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, 209818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedValueRegion* R, 209918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal V) { 210067f28534c090650ffa123afa84ff4a96f56de14eTed Kremenek if (!Features.supportsFields()) 210118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return B; 21021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2103018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = R->getValueType(); 2104fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor assert(T->isStructureOrClassType()); 2105af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu 21066217b80b7a1379b74cced1c076338262c3c980b3Ted Kremenek const RecordType* RT = T->getAs<RecordType>(); 2107258277d5a922e06ef523f7805900689b680ddc7dJordan Rose const RecordDecl *RD = RT->getDecl(); 2108c45a8253cadb640dee1d8f23fba4a6c6f8da27f4Zhongxing Xu 21095e1cdac63c3d9c9b32fa41fa0b2d242a58a20d49John McCall if (!RD->isCompleteDefinition()) 211018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return B; 2111af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu 21125ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose // Handle lazy compound values and symbolic values. 2113258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (Optional<nonloc::LazyCompoundVal> LCV = 2114258277d5a922e06ef523f7805900689b680ddc7dJordan Rose V.getAs<nonloc::LazyCompoundVal>()) { 2115258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV)) 2116258277d5a922e06ef523f7805900689b680ddc7dJordan Rose return *NewB; 2117258277d5a922e06ef523f7805900689b680ddc7dJordan Rose return bindAggregate(B, R, V); 2118258277d5a922e06ef523f7805900689b680ddc7dJordan Rose } 2119258277d5a922e06ef523f7805900689b680ddc7dJordan Rose if (V.getAs<nonloc::SymbolVal>()) 212018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindAggregate(B, R, V); 21211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2122281e9dc6ba6ff10bf910b0fc8898dff2a429f156Ted Kremenek // We may get non-CompoundVal accidentally due to imprecise cast logic or 2123281e9dc6ba6ff10bf910b0fc8898dff2a429f156Ted Kremenek // that we are binding symbolic struct value. Kill the field values, and if 2124281e9dc6ba6ff10bf910b0fc8898dff2a429f156Ted Kremenek // the value is symbolic go and bind it as a "default" binding. 21255251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()) 212618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return bindAggregate(B, R, UnknownVal()); 21273f6978a3fefc16f203afbc64697fe04af329cf2bZhongxing Xu 21285251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); 2129af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2130dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu 2131dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu RecordDecl::field_iterator FI, FE; 213218f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek RegionBindingsRef NewB(B); 213318f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek 2134e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 2135af0a844542247d337947b4585e684b5eb72d4ffbZhongxing Xu 2136dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu if (VI == VE) 21374193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu break; 2138ea8a1854137faca10ccb24acf4f1a74912fccfb2Zhongxing Xu 2139e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II // Skip any unnamed bitfields to stay in sync with the initializers. 2140262bc18e32500558af7cb0afa205b34bd37bafedDavid Blaikie if (FI->isUnnamedBitfield()) 2141e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II continue; 2142e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II 2143262bc18e32500558af7cb0afa205b34bd37bafedDavid Blaikie QualType FTy = FI->getType(); 2144581deb3da481053c4993c7600f97acf7768caac5David Blaikie const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 2145ea8a1854137faca10ccb24acf4f1a74912fccfb2Zhongxing Xu 2146cf54959eae25fb3050f41833f0eab91042fb1269Ted Kremenek if (FTy->isArrayType()) 214718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = bindArray(NewB, FR, *VI); 2148fb87b89fc9eb103e19fb8e4b925c23f0bd091b99Douglas Gregor else if (FTy->isStructureOrClassType()) 214918f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = bindStruct(NewB, FR, *VI); 2150cf54959eae25fb3050f41833f0eab91042fb1269Ted Kremenek else 2151258277d5a922e06ef523f7805900689b680ddc7dJordan Rose NewB = bind(NewB, loc::MemRegionVal(FR), *VI); 2152e42a0ab77ca4ad5201591aac5679ef47a08af4b6Jim Goodnow II ++VI; 2153c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu } 2154c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 2155dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu // There may be fewer values in the initialize list than the fields of struct. 215613d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu if (FI != FE) { 215718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek NewB = NewB.addBinding(R, BindingKey::Default, 215818f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek svalBuilder.makeIntVal(0, false)); 215913d50177b13161b209579e1f30a5e3cc72f7e2bdZhongxing Xu } 2160dbdf2195803e8e723f25176627caef05740cfbb1Zhongxing Xu 216118f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return NewB; 2162c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu} 2163c3a0599bac9dabbae9481674313aa6e1a26159b6Zhongxing Xu 216418f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionBindingsRef 216518f860ee6cc43c8fc80834073b097eb5c02b22cfTed KremenekRegionStoreManager::bindAggregate(RegionBindingsConstRef B, 216618f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek const TypedRegion *R, 216718f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek SVal Val) { 2168e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // Remove the old bindings, using 'R' as the root of all regions 21695ad76c073e1822d11901a8552c6aa9372038b5f0Jordan Rose // we will invalidate. Then add the new binding. 217018f860ee6cc43c8fc80834073b097eb5c02b22cfTed Kremenek return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); 21711e934431adba0f459668a59c6059b9596fd627b4Jordan Rose} 21721e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 21739af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 21749af46f59242cfaec74fa491a66724970478263ebTed Kremenek// State pruning. 21759af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 2176e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 21775499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremeneknamespace { 2178db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekclass removeDeadBindingsWorker : 2179db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek public ClusterAnalysis<removeDeadBindingsWorker> { 21805f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const SymbolicRegion*, 12> Postponed; 21815499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek SymbolReaper &SymReaper; 218217ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu const StackFrameContext *CurrentLCtx; 2183dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 21845499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenekpublic: 21851437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks removeDeadBindingsWorker(RegionStoreManager &rm, 21861437425a62dbf7bdb0a855d3ed3b05ed2019ec1eAnna Zaks ProgramStateManager &stateMgr, 218729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef b, SymbolReaper &symReaper, 21887dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose const StackFrameContext *LCtx) 2189e0208ff84598f48e0aafecf5b543afeff8574045Jordan Rose : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, GFK_None), 21907dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose SymReaper(symReaper), CurrentLCtx(LCtx) {} 21915499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 21925499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Called by ClusterAnalysis. 21931e934431adba0f459668a59c6059b9596fd627b4Jordan Rose void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 2194f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 2195aa5573364b79bf4d85380aaec59cae2eeefcb322Jordan Rose using ClusterAnalysis<removeDeadBindingsWorker>::VisitCluster; 21965499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 21975499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool UpdatePostponed(); 21985499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek void VisitBinding(SVal V); 21995499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek}; 22005499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 22011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2202db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekvoid removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 22031e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &C) { 2204e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 22055499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 22067dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose if (SymReaper.isLive(VR)) 22071e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(baseR, &C); 2208e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 22095499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 22109af46f59242cfaec74fa491a66724970478263ebTed Kremenek } 2211e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 22125499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 22135499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek if (SymReaper.isLive(SR->getSymbol())) 22141e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(SR, &C); 22155499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek else 22165499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek Postponed.push_back(SR); 2217e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 22185499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 22199af46f59242cfaec74fa491a66724970478263ebTed Kremenek } 222017ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu 2221dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 22221e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(baseR, &C); 2223dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek return; 2224dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek } 2225dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek 222617ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu // CXXThisRegion in the current or parent location context is live. 222717ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 2228dcee3ce97fc76f20ce8f5a7451071e3dec537073Ted Kremenek const StackArgumentsSpaceRegion *StackReg = 222917ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 223017ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu const StackFrameContext *RegCtx = StackReg->getStackFrame(); 22318501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks if (CurrentLCtx && 22328501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) 22331e934431adba0f459668a59c6059b9596fd627b4Jordan Rose AddToWorkList(TR, &C); 223417ddf1c108bb847fb05111fec09d664c9bb2e49bZhongxing Xu } 22355499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 22361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2237db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekvoid removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 2238f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose const ClusterBindings *C) { 2239f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose if (!C) 2240f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose return; 2241f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose 2242f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose // Mark the symbol for any SymbolicRegion with live bindings as live itself. 2243f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose // This means we should continue to track that symbol. 2244f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 2245f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose SymReaper.markLive(SymR->getSymbol()); 2246f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose 2247f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 22481e934431adba0f459668a59c6059b9596fd627b4Jordan Rose VisitBinding(I.getData()); 22495499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 2250df165014c2defd9120a8f105a855d6a8b35befbeTed Kremenek 2251db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekvoid removeDeadBindingsWorker::VisitBinding(SVal V) { 22525499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Is it a LazyCompoundVal? All referenced regions are live as well. 2253dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::LazyCompoundVal> LCS = 22545251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie V.getAs<nonloc::LazyCompoundVal>()) { 22559e17cc6abb5d55bd776d379b20d5b476bcc46c71Ted Kremenek 225628743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 22570a0f1309d0fbeb0e77edbbc4e0b15cc330c3a28cJordan Rose 225828743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 225928743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose E = Vals.end(); 226028743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose I != E; ++I) 226128743b006bd88cd7d0ea97b4f17646f8fc429b89Jordan Rose VisitBinding(*I); 22621e934431adba0f459668a59c6059b9596fd627b4Jordan Rose 22635499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return; 22645499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek } 22659e17cc6abb5d55bd776d379b20d5b476bcc46c71Ted Kremenek 22665499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // If V is a region, then add it to the worklist. 22677fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek if (const MemRegion *R = V.getAsRegion()) { 22685499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek AddToWorkList(R); 22697fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 22707fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek // All regions captured by a block are also live. 22717fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 22727fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 22737fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek E = BR->referenced_vars_end(); 2274f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose for ( ; I != E; ++I) 2275f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose AddToWorkList(I.getCapturedRegion()); 22767fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek } 22777fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek } 22787fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 22791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2280aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks // Update the set of live symbols. 22811d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 22821d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks SI!=SE; ++SI) 22835499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek SymReaper.markLive(*SI); 22845499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 2285e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 2286db0594bfc013131f88429add4eb653c285fa94fbTed Kremenekbool removeDeadBindingsWorker::UpdatePostponed() { 228701756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek // See if any postponed SymbolicRegions are actually live now, after 228801756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek // having done a scan. 22895499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek bool changed = false; 22905499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 22915f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner for (SmallVectorImpl<const SymbolicRegion*>::iterator 22925499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 2293f6d05bbedd482e634507a099e3416fa05cbc0e78Jordan Rose if (const SymbolicRegion *SR = *I) { 229401756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek if (SymReaper.isLive(SR->getSymbol())) { 22955499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek changed |= AddToWorkList(SR); 22965499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek *I = NULL; 229701756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek } 229801756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek } 229901756192fe41f07b36498ab5ead5653d6dae16feTed Kremenek } 2300e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 23015499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek return changed; 23025499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek} 23035499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 230477a4d5687c2cb3199c689892c9d040a94ff270afTed KremenekStoreRef RegionStoreManager::removeDeadBindings(Store store, 230577a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek const StackFrameContext *LCtx, 2306bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek SymbolReaper& SymReaper) { 230729f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B = getRegionBindings(store); 2308db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 23095499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.GenerateClusters(); 23105499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 23115499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Enqueue the region roots onto the worklist. 2312bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2313bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek E = SymReaper.region_end(); I != E; ++I) { 23145499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek W.AddToWorkList(*I); 2315bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek } 23165499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 23175499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek do W.RunWorkList(); while (W.UpdatePostponed()); 2318e5ea0cae7769866b5a5f9fa979e7c9d1d23a6bccTed Kremenek 23199af46f59242cfaec74fa491a66724970478263ebTed Kremenek // We have now scanned the store, marking reachable regions and symbols 23209af46f59242cfaec74fa491a66724970478263ebTed Kremenek // as live. We now remove all the regions that are dead from the store 23211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // as well as update DSymbols with the set symbols that are now dead. 232229f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 23231e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const MemRegion *Base = I.getKey(); 23245499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek 2325b7118f7c379a652a910f92c4566cffceb2a8b5feTed Kremenek // If the cluster has been visited, we know the region has been marked. 23261e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (W.isVisited(Base)) 23279af46f59242cfaec74fa491a66724970478263ebTed Kremenek continue; 23281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 23295499b8487c56917e17ed5a03d95898e8b7e41e45Ted Kremenek // Remove the dead entry. 233029f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek B = B.remove(Base); 23311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 23321e934431adba0f459668a59c6059b9596fd627b4Jordan Rose if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base)) 23339af46f59242cfaec74fa491a66724970478263ebTed Kremenek SymReaper.maybeDead(SymR->getSymbol()); 23341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 23351e934431adba0f459668a59c6059b9596fd627b4Jordan Rose // Mark all non-live symbols that this binding references as dead. 23361e934431adba0f459668a59c6059b9596fd627b4Jordan Rose const ClusterBindings &Cluster = I.getData(); 23371e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 23381e934431adba0f459668a59c6059b9596fd627b4Jordan Rose CI != CE; ++CI) { 23391e934431adba0f459668a59c6059b9596fd627b4Jordan Rose SVal X = CI.getData(); 23401e934431adba0f459668a59c6059b9596fd627b4Jordan Rose SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 23411e934431adba0f459668a59c6059b9596fd627b4Jordan Rose for (; SI != SE; ++SI) 23421e934431adba0f459668a59c6059b9596fd627b4Jordan Rose SymReaper.maybeDead(*SI); 23431e934431adba0f459668a59c6059b9596fd627b4Jordan Rose } 2344093569cfab473e7b461523136a4df30a0473324dTed Kremenek } 23455e4cb347cbf12c292b80386c872e5eaef21b5c23Zhongxing Xu 23460c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek return StoreRef(B.asStore(), *this); 23479af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 23489af46f59242cfaec74fa491a66724970478263ebTed Kremenek 23499af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 23509af46f59242cfaec74fa491a66724970478263ebTed Kremenek// Utility methods. 23519af46f59242cfaec74fa491a66724970478263ebTed Kremenek//===----------------------------------------------------------------------===// 23529af46f59242cfaec74fa491a66724970478263ebTed Kremenek 23539c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid RegionStoreManager::print(Store store, raw_ostream &OS, 23549af46f59242cfaec74fa491a66724970478263ebTed Kremenek const char* nl, const char *sep) { 235529f5ccd7ef9bc066cb5894834945eaad2c4c7e53Ted Kremenek RegionBindingsRef B = getRegionBindings(store); 23566341931b144cbf369ab816e871322c99ee62bea7Ted Kremenek OS << "Store (direct and default bindings), " 23570c312a90c5b9d27e1425bf8d0448e133a97806ceTed Kremenek << B.asStore() 23586341931b144cbf369ab816e871322c99ee62bea7Ted Kremenek << " :" << nl; 2359b0abacf2f1f77214e4c77d6ec8a02b097bb98f7aTed Kremenek B.dump(OS, nl); 23609af46f59242cfaec74fa491a66724970478263ebTed Kremenek} 2361