blob: a310b1918131562450e52c7bce21bbe8ffa740a2 [file] [log] [blame]
Zhongxing Xu17892752008-10-08 02:50:44 +00001//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines a basic region store model. In this model, we do have field
11// sensitivity. But we assume nothing about the heap shape. So recursive data
12// structures are largely ignored. Basically we do 1-limiting analysis.
13// Parameter pointers are assumed with no aliasing. Pointee objects of
14// parameters are created lazily.
15//
16//===----------------------------------------------------------------------===//
Zhongxing Xu3ed04d32010-01-18 08:54:31 +000017#include "clang/AST/CharUnits.h"
Zhongxing Xuc5063572010-03-16 13:14:16 +000018#include "clang/AST/DeclCXX.h"
19#include "clang/AST/ExprCXX.h"
Ted Kremenek66d51422010-04-09 20:26:58 +000020#include "clang/Analysis/Analyses/LiveVariables.h"
21#include "clang/Analysis/AnalysisContext.h"
22#include "clang/Basic/TargetInfo.h"
Argyrios Kyrtzidis98cabba2010-12-22 18:51:49 +000023#include "clang/GR/PathSensitive/GRState.h"
24#include "clang/GR/PathSensitive/GRStateTrait.h"
25#include "clang/GR/PathSensitive/MemRegion.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000026#include "llvm/ADT/ImmutableList.h"
Ted Kremenek66d51422010-04-09 20:26:58 +000027#include "llvm/ADT/ImmutableMap.h"
28#include "llvm/ADT/Optional.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000029#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000030
31using namespace clang;
Ted Kremenek66d51422010-04-09 20:26:58 +000032using llvm::Optional;
Zhongxing Xu17892752008-10-08 02:50:44 +000033
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000034//===----------------------------------------------------------------------===//
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000035// Representation of binding keys.
36//===----------------------------------------------------------------------===//
37
38namespace {
Ted Kremeneke393f4a2010-02-03 03:06:46 +000039class BindingKey {
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000040public:
Ted Kremeneke393f4a2010-02-03 03:06:46 +000041 enum Kind { Direct = 0x0, Default = 0x1 };
42private:
43 llvm ::PointerIntPair<const MemRegion*, 1> P;
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000044 uint64_t Offset;
45
Ted Kremeneke393f4a2010-02-03 03:06:46 +000046 explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)
Jordy Rosee7011172010-08-16 01:15:17 +000047 : P(r, (unsigned) k), Offset(offset) {}
Ted Kremeneke393f4a2010-02-03 03:06:46 +000048public:
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000049
Ted Kremeneke393f4a2010-02-03 03:06:46 +000050 bool isDirect() const { return P.getInt() == Direct; }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000051
Ted Kremeneke393f4a2010-02-03 03:06:46 +000052 const MemRegion *getRegion() const { return P.getPointer(); }
53 uint64_t getOffset() const { return Offset; }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000054
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000055 void Profile(llvm::FoldingSetNodeID& ID) const {
Ted Kremeneke393f4a2010-02-03 03:06:46 +000056 ID.AddPointer(P.getOpaqueValue());
57 ID.AddInteger(Offset);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000058 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000059
Ted Kremeneke393f4a2010-02-03 03:06:46 +000060 static BindingKey Make(const MemRegion *R, Kind k);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000061
Ted Kremeneke393f4a2010-02-03 03:06:46 +000062 bool operator<(const BindingKey &X) const {
63 if (P.getOpaqueValue() < X.P.getOpaqueValue())
64 return true;
65 if (P.getOpaqueValue() > X.P.getOpaqueValue())
66 return false;
67 return Offset < X.Offset;
68 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000069
Ted Kremeneke393f4a2010-02-03 03:06:46 +000070 bool operator==(const BindingKey &X) const {
71 return P.getOpaqueValue() == X.P.getOpaqueValue() &&
72 Offset == X.Offset;
73 }
Jordy Rosee7011172010-08-16 01:15:17 +000074
Jordy Rosed5addb42010-08-16 20:53:01 +000075 bool isValid() const {
Jordy Rosee7011172010-08-16 01:15:17 +000076 return getRegion() != NULL;
77 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000078};
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000079} // end anonymous namespace
80
Zhongxing Xudc015e52010-08-21 12:24:38 +000081BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
82 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
83 const RegionRawOffset &O = ER->getAsArrayOffset();
84
85 // FIXME: There are some ElementRegions for which we cannot compute
86 // raw offsets yet, including regions with symbolic offsets. These will be
87 // ignored by the store.
88 return BindingKey(O.getRegion(), O.getByteOffset(), k);
89 }
90
91 return BindingKey(R, 0, k);
92}
93
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000094namespace llvm {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +000095 static inline
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000096 llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingKey K) {
Ted Kremeneke393f4a2010-02-03 03:06:46 +000097 os << '(' << K.getRegion() << ',' << K.getOffset()
98 << ',' << (K.isDirect() ? "direct" : "default")
99 << ')';
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000100 return os;
101 }
102} // end llvm namespace
103
104//===----------------------------------------------------------------------===//
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000105// Actual Store type.
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000106//===----------------------------------------------------------------------===//
107
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000108typedef llvm::ImmutableMap<BindingKey, SVal> RegionBindings;
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000109
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000110//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +0000111// Fine-grained control of RegionStoreManager.
112//===----------------------------------------------------------------------===//
113
114namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000115struct minimal_features_tag {};
116struct maximal_features_tag {};
Mike Stump1eb44332009-09-09 15:08:12 +0000117
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000118class RegionStoreFeatures {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000119 bool SupportsFields;
Ted Kremenek9af46f52009-06-16 22:36:44 +0000120public:
121 RegionStoreFeatures(minimal_features_tag) :
Ted Kremenek0752d6d2010-08-20 06:06:41 +0000122 SupportsFields(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000123
Ted Kremenek9af46f52009-06-16 22:36:44 +0000124 RegionStoreFeatures(maximal_features_tag) :
Ted Kremenek0752d6d2010-08-20 06:06:41 +0000125 SupportsFields(true) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000126
Ted Kremenek9af46f52009-06-16 22:36:44 +0000127 void enableFields(bool t) { SupportsFields = t; }
Mike Stump1eb44332009-09-09 15:08:12 +0000128
Ted Kremenek9af46f52009-06-16 22:36:44 +0000129 bool supportsFields() const { return SupportsFields; }
Ted Kremenek9af46f52009-06-16 22:36:44 +0000130};
131}
132
133//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000134// Main RegionStore logic.
135//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000136
Zhongxing Xu17892752008-10-08 02:50:44 +0000137namespace {
Mike Stump1eb44332009-09-09 15:08:12 +0000138
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000139class RegionStoreSubRegionMap : public SubRegionMap {
Ted Kremenekdf165012010-02-02 22:38:47 +0000140public:
141 typedef llvm::ImmutableSet<const MemRegion*> Set;
142 typedef llvm::DenseMap<const MemRegion*, Set> Map;
143private:
144 Set::Factory F;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000145 Map M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000146public:
Ted Kremenekd8c01922009-08-05 19:09:24 +0000147 bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000148 Map::iterator I = M.find(Parent);
Ted Kremenekd8c01922009-08-05 19:09:24 +0000149
150 if (I == M.end()) {
Ted Kremenek3baf6722010-11-24 00:54:37 +0000151 M.insert(std::make_pair(Parent, F.add(F.getEmptySet(), SubRegion)));
Ted Kremenekd8c01922009-08-05 19:09:24 +0000152 return true;
153 }
154
Ted Kremenek3baf6722010-11-24 00:54:37 +0000155 I->second = F.add(I->second, SubRegion);
Ted Kremenekd8c01922009-08-05 19:09:24 +0000156 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000157 }
Mike Stump1eb44332009-09-09 15:08:12 +0000158
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000159 void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000160
Ted Kremenek59e8f112009-03-03 01:35:36 +0000161 ~RegionStoreSubRegionMap() {}
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000162
Ted Kremenekdf165012010-02-02 22:38:47 +0000163 const Set *getSubRegions(const MemRegion *Parent) const {
164 Map::const_iterator I = M.find(Parent);
165 return I == M.end() ? NULL : &I->second;
166 }
Mike Stump1eb44332009-09-09 15:08:12 +0000167
Ted Kremenek5dc27462009-03-03 02:51:43 +0000168 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +0000169 Map::const_iterator I = M.find(Parent);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000170
171 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000172 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000173
Ted Kremenekdf165012010-02-02 22:38:47 +0000174 Set S = I->second;
175 for (Set::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000176 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000177 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000178 }
Mike Stump1eb44332009-09-09 15:08:12 +0000179
Ted Kremenek5dc27462009-03-03 02:51:43 +0000180 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000181 }
Mike Stump1eb44332009-09-09 15:08:12 +0000182};
Ted Kremenek59e8f112009-03-03 01:35:36 +0000183
Zhongxing Xu796788f2010-08-23 01:37:32 +0000184void
185RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL,
186 const SubRegion *R) {
187 const MemRegion *superR = R->getSuperRegion();
188 if (add(superR, R))
189 if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
190 WL.push_back(sr);
191}
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000192
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000193class RegionStoreManager : public StoreManager {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000194 const RegionStoreFeatures Features;
Ted Kremenek451ac092009-08-06 04:50:20 +0000195 RegionBindings::Factory RBFactory;
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000196
Zhongxing Xu17892752008-10-08 02:50:44 +0000197public:
Mike Stump1eb44332009-09-09 15:08:12 +0000198 RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
Ted Kremenekf7a0cf42009-07-29 21:43:22 +0000199 : StoreManager(mgr),
Ted Kremenek9af46f52009-06-16 22:36:44 +0000200 Features(f),
Ted Kremenek8928d412010-02-04 04:14:49 +0000201 RBFactory(mgr.getAllocator()) {}
Zhongxing Xu17892752008-10-08 02:50:44 +0000202
Zhongxing Xuf5416bd2010-02-05 05:18:47 +0000203 SubRegionMap *getSubRegionMap(Store store) {
204 return getRegionStoreSubRegionMap(store);
205 }
Mike Stump1eb44332009-09-09 15:08:12 +0000206
Zhongxing Xu13d50172009-10-11 08:08:02 +0000207 RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
Mike Stump1eb44332009-09-09 15:08:12 +0000208
Zhongxing Xu13d50172009-10-11 08:08:02 +0000209 Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000210 /// getDefaultBinding - Returns an SVal* representing an optional default
211 /// binding associated with a region and its subregions.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000212 Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000213
Ted Kremenek027e2662009-11-19 20:20:24 +0000214 /// setImplicitDefaultValue - Set the default binding for the provided
215 /// MemRegion to the value implicitly defined for compound literals when
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000216 /// the value is not specified.
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000217 Store setImplicitDefaultValue(Store store, const MemRegion *R, QualType T);
Mike Stump1eb44332009-09-09 15:08:12 +0000218
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000219 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
220 /// type. 'Array' represents the lvalue of the array being decayed
221 /// to a pointer, and the returned SVal represents the decayed
222 /// version of that lvalue (i.e., a pointer to the first element of
223 /// the array). This is called by GRExprEngine when evaluating
224 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000225 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000226
Zhongxing Xu4fd56812010-11-26 08:21:53 +0000227 /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it.
228 virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType);
229
Ted Kremenek9c149532010-12-01 21:57:22 +0000230 SVal evalBinOp(BinaryOperator::Opcode Op,Loc L, NonLoc R, QualType resultTy);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000231
Mike Stump1eb44332009-09-09 15:08:12 +0000232 Store getInitialStore(const LocationContext *InitLoc) {
Ted Kremenek3baf6722010-11-24 00:54:37 +0000233 return RBFactory.getEmptyMap().getRoot();
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000234 }
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000235
Ted Kremenek67f28532009-06-17 22:02:04 +0000236 //===-------------------------------------------------------------------===//
237 // Binding values to regions.
238 //===-------------------------------------------------------------------===//
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000239
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000240 Store InvalidateRegions(Store store,
241 const MemRegion * const *Begin,
242 const MemRegion * const *End,
243 const Expr *E, unsigned Count,
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000244 InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000245 bool invalidateGlobals,
246 InvalidatedRegions *Regions);
Mike Stump1eb44332009-09-09 15:08:12 +0000247
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000248public: // Made public for helper classes.
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000249
Zhongxing Xu13d50172009-10-11 08:08:02 +0000250 void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000251 RegionStoreSubRegionMap &M);
Mike Stump1eb44332009-09-09 15:08:12 +0000252
Ted Kremenek3baf6722010-11-24 00:54:37 +0000253 RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V);
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000254
Ted Kremenek3baf6722010-11-24 00:54:37 +0000255 RegionBindings addBinding(RegionBindings B, const MemRegion *R,
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000256 BindingKey::Kind k, SVal V);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000257
Ted Kremenek3baf6722010-11-24 00:54:37 +0000258 const SVal *lookup(RegionBindings B, BindingKey K);
259 const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000260
Ted Kremenek3baf6722010-11-24 00:54:37 +0000261 RegionBindings removeBinding(RegionBindings B, BindingKey K);
262 RegionBindings removeBinding(RegionBindings B, const MemRegion *R,
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000263 BindingKey::Kind k);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000264
Ted Kremenek3baf6722010-11-24 00:54:37 +0000265 RegionBindings removeBinding(RegionBindings B, const MemRegion *R) {
266 return removeBinding(removeBinding(B, R, BindingKey::Direct), R,
267 BindingKey::Default);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000268 }
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000269
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000270public: // Part of public interface to class.
271
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000272 Store Bind(Store store, Loc LV, SVal V);
Ted Kremenek67f28532009-06-17 22:02:04 +0000273
Zhongxing Xu54460092010-06-01 04:49:26 +0000274 // BindDefault is only used to initialize a region with a default value.
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000275 Store BindDefault(Store store, const MemRegion *R, SVal V) {
Zhongxing Xu54460092010-06-01 04:49:26 +0000276 RegionBindings B = GetRegionBindings(store);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000277 assert(!lookup(B, R, BindingKey::Default));
278 assert(!lookup(B, R, BindingKey::Direct));
279 return addBinding(B, R, BindingKey::Default, V).getRoot();
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000280 }
281
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000282 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL,
283 const LocationContext *LC, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000284
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000285 Store BindDecl(Store store, const VarRegion *VR, SVal InitVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000286
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000287 Store BindDeclWithNoInit(Store store, const VarRegion *) {
288 return store;
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000289 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000290
Ted Kremenek67f28532009-06-17 22:02:04 +0000291 /// BindStruct - Bind a compound value to a structure.
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000292 Store BindStruct(Store store, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000293
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000294 Store BindArray(Store store, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000295
296 /// KillStruct - Set the entire struct to unknown.
Ted Kremenek281e9dc2010-07-29 00:28:47 +0000297 Store KillStruct(Store store, const TypedRegion* R, SVal DefaultVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000298
Ted Kremenek67f28532009-06-17 22:02:04 +0000299 Store Remove(Store store, Loc LV);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000300
Ted Kremenek67f28532009-06-17 22:02:04 +0000301
302 //===------------------------------------------------------------------===//
303 // Loading values from regions.
304 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000305
Ted Kremenek67f28532009-06-17 22:02:04 +0000306 /// The high level logic for this method is this:
307 /// Retrieve (L)
308 /// if L has binding
309 /// return L's binding
310 /// else if L is in killset
311 /// return unknown
312 /// else
313 /// if L is on stack or heap
314 /// return undefined
315 /// else
316 /// return symbolic
Zhongxing Xu576bb922010-02-05 03:01:53 +0000317 SVal Retrieve(Store store, Loc L, QualType T = QualType());
Zhongxing Xu490b0f02009-06-25 04:50:44 +0000318
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000319 SVal RetrieveElement(Store store, const ElementRegion *R);
Zhongxing Xuc00346f2009-06-25 05:29:39 +0000320
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000321 SVal RetrieveField(Store store, const FieldRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000322
Zhongxing Xu576bb922010-02-05 03:01:53 +0000323 SVal RetrieveObjCIvar(Store store, const ObjCIvarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000324
Zhongxing Xu576bb922010-02-05 03:01:53 +0000325 SVal RetrieveVar(Store store, const VarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000326
Zhongxing Xu576bb922010-02-05 03:01:53 +0000327 SVal RetrieveLazySymbol(const TypedRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000328
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000329 SVal RetrieveFieldOrElementCommon(Store store, const TypedRegion *R,
Ted Kremenek566a6fa2009-08-06 22:33:36 +0000330 QualType Ty, const MemRegion *superR);
Mike Stump1eb44332009-09-09 15:08:12 +0000331
Ted Kremenek67f28532009-06-17 22:02:04 +0000332 /// Retrieve the values in a struct and return a CompoundVal, used when doing
Mike Stump1eb44332009-09-09 15:08:12 +0000333 /// struct copy:
334 /// struct s x, y;
Ted Kremenek67f28532009-06-17 22:02:04 +0000335 /// x = y;
336 /// y's value is retrieved by this method.
Zhongxing Xu576bb922010-02-05 03:01:53 +0000337 SVal RetrieveStruct(Store store, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000338
Zhongxing Xu576bb922010-02-05 03:01:53 +0000339 SVal RetrieveArray(Store store, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000340
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000341 /// Used to lazily generate derived symbols for bindings that are defined
342 /// implicitly by default bindings in a super region.
343 Optional<SVal> RetrieveDerivedDefaultValue(RegionBindings B,
344 const MemRegion *superR,
345 const TypedRegion *R, QualType Ty);
346
Zhongxing Xu944ebc62009-12-21 06:52:24 +0000347 /// Get the state and region whose binding this region R corresponds to.
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000348 std::pair<Store, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +0000349 GetLazyBinding(RegionBindings B, const MemRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000350
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000351 Store CopyLazyBindings(nonloc::LazyCompoundVal V, Store store,
352 const TypedRegion *R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000353
354 //===------------------------------------------------------------------===//
355 // State pruning.
356 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000357
Ted Kremenek67f28532009-06-17 22:02:04 +0000358 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
359 /// It returns a new Store with these values removed.
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000360 Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
361 SymbolReaper& SymReaper,
Ted Kremenek67f28532009-06-17 22:02:04 +0000362 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
363
Jordy Roseff59efd2010-08-03 20:44:35 +0000364 Store EnterStackFrame(const GRState *state, const StackFrameContext *frame);
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +0000365
Ted Kremenek67f28532009-06-17 22:02:04 +0000366 //===------------------------------------------------------------------===//
367 // Region "extents".
368 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000369
Jordy Rose32f26562010-07-04 00:00:41 +0000370 // FIXME: This method will soon be eliminated; see the note in Store.h.
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000371 DefinedOrUnknownSVal getSizeInElements(const GRState *state,
Zhongxing Xu3ed04d32010-01-18 08:54:31 +0000372 const MemRegion* R, QualType EleTy);
Ted Kremenek67f28532009-06-17 22:02:04 +0000373
374 //===------------------------------------------------------------------===//
Ted Kremenek67f28532009-06-17 22:02:04 +0000375 // Utility methods.
376 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000377
Ted Kremenek451ac092009-08-06 04:50:20 +0000378 static inline RegionBindings GetRegionBindings(Store store) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000379 return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000380 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000381
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000382 void print(Store store, llvm::raw_ostream& Out, const char* nl,
383 const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000384
385 void iterBindings(Store store, BindingsHandler& f) {
Ted Kremenek0e9910f2010-06-17 00:24:42 +0000386 RegionBindings B = GetRegionBindings(store);
387 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
388 const BindingKey &K = I.getKey();
389 if (!K.isDirect())
390 continue;
391 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) {
392 // FIXME: Possibly incorporate the offset?
393 if (!f.HandleBinding(*this, store, R, I.getData()))
394 return;
395 }
396 }
Ted Kremenek67f28532009-06-17 22:02:04 +0000397 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000398};
399
400} // end anonymous namespace
401
Ted Kremenek9af46f52009-06-16 22:36:44 +0000402//===----------------------------------------------------------------------===//
403// RegionStore creation.
404//===----------------------------------------------------------------------===//
405
406StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
407 RegionStoreFeatures F = maximal_features_tag();
408 return new RegionStoreManager(StMgr, F);
409}
410
411StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
412 RegionStoreFeatures F = minimal_features_tag();
413 F.enableFields(true);
414 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000415}
416
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000417
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000418RegionStoreSubRegionMap*
Zhongxing Xu13d50172009-10-11 08:08:02 +0000419RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
420 RegionBindings B = GetRegionBindings(store);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000421 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
Mike Stump1eb44332009-09-09 15:08:12 +0000422
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000423 llvm::SmallVector<const SubRegion*, 10> WL;
424
Ted Kremenek451ac092009-08-06 04:50:20 +0000425 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000426 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000427 M->process(WL, R);
Mike Stump1eb44332009-09-09 15:08:12 +0000428
Mike Stump1eb44332009-09-09 15:08:12 +0000429 // We also need to record in the subregion map "intermediate" regions that
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000430 // don't have direct bindings but are super regions of those that do.
431 while (!WL.empty()) {
432 const SubRegion *R = WL.back();
433 WL.pop_back();
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000434 M->process(WL, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000435 }
436
Ted Kremenek14453bf2009-03-03 19:02:42 +0000437 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000438}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000439
Ted Kremenek9af46f52009-06-16 22:36:44 +0000440//===----------------------------------------------------------------------===//
Ted Kremeneka4fab032010-03-10 07:19:59 +0000441// Region Cluster analysis.
442//===----------------------------------------------------------------------===//
443
444namespace {
Ted Kremenek5499b842010-03-10 16:32:56 +0000445template <typename DERIVED>
Ted Kremeneka4fab032010-03-10 07:19:59 +0000446class ClusterAnalysis {
447protected:
448 typedef BumpVector<BindingKey> RegionCluster;
449 typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap;
Ted Kremenek5499b842010-03-10 16:32:56 +0000450 llvm::DenseMap<const RegionCluster*, unsigned> Visited;
451 typedef llvm::SmallVector<std::pair<const MemRegion *, RegionCluster*>, 10>
452 WorkList;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000453
454 BumpVectorContext BVC;
455 ClusterMap ClusterM;
Ted Kremenek5499b842010-03-10 16:32:56 +0000456 WorkList WL;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000457
458 RegionStoreManager &RM;
459 ASTContext &Ctx;
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000460 SValBuilder &svalBuilder;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000461
Ted Kremenek5499b842010-03-10 16:32:56 +0000462 RegionBindings B;
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000463
464 const bool includeGlobals;
Ted Kremenek5499b842010-03-10 16:32:56 +0000465
Ted Kremeneka4fab032010-03-10 07:19:59 +0000466public:
Ted Kremenek5499b842010-03-10 16:32:56 +0000467 ClusterAnalysis(RegionStoreManager &rm, GRStateManager &StateMgr,
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000468 RegionBindings b, const bool includeGlobals)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000469 : RM(rm), Ctx(StateMgr.getContext()),
470 svalBuilder(StateMgr.getSValBuilder()),
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000471 B(b), includeGlobals(includeGlobals) {}
Ted Kremeneka4fab032010-03-10 07:19:59 +0000472
Ted Kremenek5499b842010-03-10 16:32:56 +0000473 RegionBindings getRegionBindings() const { return B; }
Ted Kremeneka4fab032010-03-10 07:19:59 +0000474
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000475 RegionCluster &AddToCluster(BindingKey K) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000476 const MemRegion *R = K.getRegion();
477 const MemRegion *baseR = R->getBaseRegion();
478 RegionCluster &C = getCluster(baseR);
479 C.push_back(K, BVC);
480 static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000481 return C;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000482 }
Ted Kremeneka4fab032010-03-10 07:19:59 +0000483
Ted Kremenek5499b842010-03-10 16:32:56 +0000484 bool isVisited(const MemRegion *R) {
485 return (bool) Visited[&getCluster(R->getBaseRegion())];
486 }
487
488 RegionCluster& getCluster(const MemRegion *R) {
489 RegionCluster *&CRef = ClusterM[R];
490 if (!CRef) {
491 void *Mem = BVC.getAllocator().template Allocate<RegionCluster>();
492 CRef = new (Mem) RegionCluster(BVC, 10);
493 }
494 return *CRef;
495 }
496
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000497 void GenerateClusters() {
Ted Kremenek5499b842010-03-10 16:32:56 +0000498 // Scan the entire set of bindings and make the region clusters.
499 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000500 RegionCluster &C = AddToCluster(RI.getKey());
Ted Kremenek5499b842010-03-10 16:32:56 +0000501 if (const MemRegion *R = RI.getData().getAsRegion()) {
502 // Generate a cluster, but don't add the region to the cluster
503 // if there aren't any bindings.
504 getCluster(R->getBaseRegion());
505 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000506 if (includeGlobals) {
507 const MemRegion *R = RI.getKey().getRegion();
508 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
509 AddToWorkList(R, C);
510 }
Ted Kremeneka4fab032010-03-10 07:19:59 +0000511 }
512 }
Ted Kremenek5499b842010-03-10 16:32:56 +0000513
514 bool AddToWorkList(const MemRegion *R, RegionCluster &C) {
515 if (unsigned &visited = Visited[&C])
516 return false;
517 else
518 visited = 1;
519
520 WL.push_back(std::make_pair(R, &C));
521 return true;
522 }
523
524 bool AddToWorkList(BindingKey K) {
525 return AddToWorkList(K.getRegion());
526 }
527
528 bool AddToWorkList(const MemRegion *R) {
529 const MemRegion *baseR = R->getBaseRegion();
530 return AddToWorkList(baseR, getCluster(baseR));
531 }
532
533 void RunWorkList() {
534 while (!WL.empty()) {
535 const MemRegion *baseR;
536 RegionCluster *C;
537 llvm::tie(baseR, C) = WL.back();
538 WL.pop_back();
539
540 // First visit the cluster.
541 static_cast<DERIVED*>(this)->VisitCluster(baseR, C->begin(), C->end());
542
Ted Kremenek75a2d942010-04-01 00:15:55 +0000543 // Next, visit the base region.
544 static_cast<DERIVED*>(this)->VisitBaseRegion(baseR);
Ted Kremenek5499b842010-03-10 16:32:56 +0000545 }
546 }
547
548public:
549 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C) {}
550 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E) {}
Ted Kremenek75a2d942010-04-01 00:15:55 +0000551 void VisitBaseRegion(const MemRegion *baseR) {}
Ted Kremenek5499b842010-03-10 16:32:56 +0000552};
Ted Kremeneka4fab032010-03-10 07:19:59 +0000553}
554
555//===----------------------------------------------------------------------===//
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000556// Binding invalidation.
557//===----------------------------------------------------------------------===//
558
Zhongxing Xu13d50172009-10-11 08:08:02 +0000559void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
560 const MemRegion *R,
561 RegionStoreSubRegionMap &M) {
Ted Kremeneka4fab032010-03-10 07:19:59 +0000562
Ted Kremenekdf165012010-02-02 22:38:47 +0000563 if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R))
564 for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end();
565 I != E; ++I)
566 RemoveSubRegionBindings(B, *I, M);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000567
Ted Kremenek3baf6722010-11-24 00:54:37 +0000568 B = removeBinding(B, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000569}
570
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000571namespace {
Ted Kremenek5499b842010-03-10 16:32:56 +0000572class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker>
573{
574 const Expr *Ex;
575 unsigned Count;
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000576 StoreManager::InvalidatedSymbols *IS;
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000577 StoreManager::InvalidatedRegions *Regions;
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000578public:
Ted Kremenek24c37ad2010-02-13 01:52:33 +0000579 InvalidateRegionsWorker(RegionStoreManager &rm,
Ted Kremenek5499b842010-03-10 16:32:56 +0000580 GRStateManager &stateMgr,
581 RegionBindings b,
582 const Expr *ex, unsigned count,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000583 StoreManager::InvalidatedSymbols *is,
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000584 StoreManager::InvalidatedRegions *r,
585 bool includeGlobals)
586 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b, includeGlobals),
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000587 Ex(ex), Count(count), IS(is), Regions(r) {}
Ted Kremeneka4fab032010-03-10 07:19:59 +0000588
Ted Kremenek5499b842010-03-10 16:32:56 +0000589 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
Ted Kremenek75a2d942010-04-01 00:15:55 +0000590 void VisitBaseRegion(const MemRegion *baseR);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000591
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000592private:
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000593 void VisitBinding(SVal V);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000594};
Ted Kremenek5b290652010-02-03 04:16:00 +0000595}
596
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000597void InvalidateRegionsWorker::VisitBinding(SVal V) {
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000598 // A symbol? Mark it touched by the invalidation.
599 if (IS)
600 if (SymbolRef Sym = V.getAsSymbol())
601 IS->insert(Sym);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000602
Ted Kremenek24c37ad2010-02-13 01:52:33 +0000603 if (const MemRegion *R = V.getAsRegion()) {
604 AddToWorkList(R);
605 return;
606 }
607
608 // Is it a LazyCompoundVal? All references get invalidated as well.
609 if (const nonloc::LazyCompoundVal *LCS =
610 dyn_cast<nonloc::LazyCompoundVal>(&V)) {
611
612 const MemRegion *LazyR = LCS->getRegion();
613 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
614
615 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
Ted Kremenek0ea0e8b2010-07-06 23:53:29 +0000616 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
617 if (baseR && baseR->isSubRegionOf(LazyR))
Ted Kremenek24c37ad2010-02-13 01:52:33 +0000618 VisitBinding(RI.getData());
619 }
620
621 return;
622 }
623}
624
Ted Kremenek5499b842010-03-10 16:32:56 +0000625void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
626 BindingKey *I, BindingKey *E) {
627 for ( ; I != E; ++I) {
628 // Get the old binding. Is it a region? If so, add it to the worklist.
629 const BindingKey &K = *I;
Ted Kremenek3baf6722010-11-24 00:54:37 +0000630 if (const SVal *V = RM.lookup(B, K))
Ted Kremenek5499b842010-03-10 16:32:56 +0000631 VisitBinding(*V);
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000632
Ted Kremenek3baf6722010-11-24 00:54:37 +0000633 B = RM.removeBinding(B, K);
Ted Kremenek5499b842010-03-10 16:32:56 +0000634 }
635}
Ted Kremeneka4fab032010-03-10 07:19:59 +0000636
Ted Kremenek75a2d942010-04-01 00:15:55 +0000637void InvalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000638 if (IS) {
639 // Symbolic region? Mark that symbol touched by the invalidation.
640 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
641 IS->insert(SR->getSymbol());
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000642 }
643
Ted Kremenek5499b842010-03-10 16:32:56 +0000644 // BlockDataRegion? If so, invalidate captured variables that are passed
645 // by reference.
646 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
647 for (BlockDataRegion::referenced_vars_iterator
648 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
649 BI != BE; ++BI) {
650 const VarRegion *VR = *BI;
651 const VarDecl *VD = VR->getDecl();
652 if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage())
653 AddToWorkList(VR);
654 }
655 return;
656 }
657
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000658 // Otherwise, we have a normal data region. Record that we touched the region.
659 if (Regions)
660 Regions->push_back(baseR);
661
Ted Kremenek5499b842010-03-10 16:32:56 +0000662 if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
663 // Invalidate the region by setting its default value to
664 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek3baf6722010-11-24 00:54:37 +0000665 DefinedOrUnknownSVal V =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000666 svalBuilder.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy, Count);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000667 B = RM.addBinding(B, baseR, BindingKey::Default, V);
Ted Kremenek5499b842010-03-10 16:32:56 +0000668 return;
669 }
670
671 if (!baseR->isBoundable())
672 return;
673
674 const TypedRegion *TR = cast<TypedRegion>(baseR);
Zhongxing Xu018220c2010-08-11 06:10:55 +0000675 QualType T = TR->getValueType();
Ted Kremenek5499b842010-03-10 16:32:56 +0000676
677 // Invalidate the binding.
Zhongxing Xu61453402010-08-21 06:51:45 +0000678 if (T->isStructureType()) {
Zhongxing Xu0b46b1b2010-08-21 06:26:59 +0000679 // Invalidate the region by setting its default value to
680 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000681 DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy,
Ted Kremenek5499b842010-03-10 16:32:56 +0000682 Count);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000683 B = RM.addBinding(B, baseR, BindingKey::Default, V);
Ted Kremenek5499b842010-03-10 16:32:56 +0000684 return;
685 }
686
687 if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
688 // Set the default value of the array to conjured symbol.
689 DefinedOrUnknownSVal V =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000690 svalBuilder.getConjuredSymbolVal(baseR, Ex, AT->getElementType(), Count);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000691 B = RM.addBinding(B, baseR, BindingKey::Default, V);
Ted Kremenek5499b842010-03-10 16:32:56 +0000692 return;
693 }
Ted Kremenekc1143e52010-10-26 00:06:17 +0000694
695 if (includeGlobals &&
696 isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) {
697 // If the region is a global and we are invalidating all globals,
698 // just erase the entry. This causes all globals to be lazily
699 // symbolicated from the same base symbol.
Ted Kremenek3baf6722010-11-24 00:54:37 +0000700 B = RM.removeBinding(B, baseR);
Ted Kremenekc1143e52010-10-26 00:06:17 +0000701 return;
702 }
703
Ted Kremenek5499b842010-03-10 16:32:56 +0000704
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000705 DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, T, Count);
Ted Kremenek5499b842010-03-10 16:32:56 +0000706 assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
Ted Kremenek3baf6722010-11-24 00:54:37 +0000707 B = RM.addBinding(B, baseR, BindingKey::Direct, V);
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000708}
709
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000710Store RegionStoreManager::InvalidateRegions(Store store,
711 const MemRegion * const *I,
712 const MemRegion * const *E,
713 const Expr *Ex, unsigned Count,
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000714 InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000715 bool invalidateGlobals,
716 InvalidatedRegions *Regions) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000717 InvalidateRegionsWorker W(*this, StateMgr,
718 RegionStoreManager::GetRegionBindings(store),
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000719 Ex, Count, IS, Regions, invalidateGlobals);
Ted Kremenek5499b842010-03-10 16:32:56 +0000720
721 // Scan the bindings and generate the clusters.
Ted Kremenekd45d59f2010-10-26 00:06:15 +0000722 W.GenerateClusters();
Ted Kremenek5499b842010-03-10 16:32:56 +0000723
724 // Add I .. E to the worklist.
725 for ( ; I != E; ++I)
726 W.AddToWorkList(*I);
727
728 W.RunWorkList();
729
730 // Return the new bindings.
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000731 RegionBindings B = W.getRegionBindings();
732
733 if (invalidateGlobals) {
734 // Bind the non-static globals memory space to a new symbol that we will
735 // use to derive the bindings for all non-static globals.
736 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
737 SVal V =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000738 svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex,
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000739 /* symbol type, doesn't matter */ Ctx.IntTy,
740 Count);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000741 B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000742
743 // Even if there are no bindings in the global scope, we still need to
744 // record that we touched it.
745 if (Regions)
746 Regions->push_back(GS);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000747 }
748
749 return B.getRoot();
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000750}
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000751
Ted Kremenek9af46f52009-06-16 22:36:44 +0000752//===----------------------------------------------------------------------===//
753// Extents for regions.
754//===----------------------------------------------------------------------===//
755
Zhongxing Xue884ff82009-11-12 02:48:32 +0000756DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state,
Zhongxing Xu3ed04d32010-01-18 08:54:31 +0000757 const MemRegion *R,
758 QualType EleTy) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000759 SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder);
Ted Kremenek846eabd2010-12-01 21:28:31 +0000760 const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
Jordy Rose32f26562010-07-04 00:00:41 +0000761 if (!SizeInt)
762 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000763
Jordy Rose32f26562010-07-04 00:00:41 +0000764 CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
Ted Kremenek555c77a2010-09-14 23:08:34 +0000765
766 if (Ctx.getAsVariableArrayType(EleTy)) {
767 // FIXME: We need to track extra state to properly record the size
768 // of VLAs. Returning UnknownVal here, however, is a stop-gap so that
769 // we don't have a divide-by-zero below.
770 return UnknownVal();
771 }
772
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000773 CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
Mike Stump1eb44332009-09-09 15:08:12 +0000774
Jordy Rose32f26562010-07-04 00:00:41 +0000775 // If a variable is reinterpreted as a type that doesn't fit into a larger
776 // type evenly, round it down.
777 // This is a signed value, since it's used in arithmetic with signed indices.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000778 return svalBuilder.makeIntVal(RegionSize / EleSize, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000779}
780
Ted Kremenek9af46f52009-06-16 22:36:44 +0000781//===----------------------------------------------------------------------===//
782// Location and region casting.
783//===----------------------------------------------------------------------===//
784
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000785/// ArrayToPointer - Emulates the "decay" of an array to a pointer
786/// type. 'Array' represents the lvalue of the array being decayed
787/// to a pointer, and the returned SVal represents the decayed
788/// version of that lvalue (i.e., a pointer to the first element of
789/// the array). This is called by GRExprEngine when evaluating casts
790/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000791SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000792 if (!isa<loc::MemRegionVal>(Array))
793 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000794
Ted Kremenekabb042f2008-12-13 19:24:37 +0000795 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
796 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000797
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000798 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000799 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000800
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000801 // Strip off typedefs from the ArrayRegion's ValueType.
John McCall49f4e1c2010-12-10 11:01:00 +0000802 QualType T = ArrayR->getValueType().getDesugaredType(Ctx);
Ted Kremenekf936f452009-05-04 06:18:28 +0000803 ArrayType *AT = cast<ArrayType>(T);
804 T = AT->getElementType();
Mike Stump1eb44332009-09-09 15:08:12 +0000805
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000806 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000807 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000808}
809
Zhongxing Xueee1df12010-12-22 08:12:57 +0000810SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) {
811 const CXXRecordDecl *baseDecl;
812 if (baseType->isPointerType())
813 baseDecl = baseType->getCXXRecordDeclForPointerType();
814 else
815 baseDecl = baseType->getAsCXXRecordDecl();
816
Zhongxing Xu4fd56812010-11-26 08:21:53 +0000817 assert(baseDecl && "not a CXXRecordDecl?");
Zhongxing Xueee1df12010-12-22 08:12:57 +0000818
Zhongxing Xu4fd56812010-11-26 08:21:53 +0000819 loc::MemRegionVal &derivedRegVal = cast<loc::MemRegionVal>(derived);
820 const MemRegion *baseReg =
821 MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal.getRegion());
822 return loc::MemRegionVal(baseReg);
823}
Ted Kremenek9af46f52009-06-16 22:36:44 +0000824//===----------------------------------------------------------------------===//
825// Pointer arithmetic.
826//===----------------------------------------------------------------------===//
827
Ted Kremenek9c149532010-12-01 21:57:22 +0000828SVal RegionStoreManager::evalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R,
Ted Kremenek5c734622009-06-26 00:41:43 +0000829 QualType resultTy) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000830 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000831 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000832 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000833
Jordy Roseeac4a002010-06-28 08:26:15 +0000834 // Special case for zero RHS.
835 if (R.isZeroConstant()) {
836 switch (Op) {
837 default:
838 // Handle it normally.
839 break;
John McCall2de56d12010-08-25 11:45:40 +0000840 case BO_Add:
841 case BO_Sub:
Jordy Roseeac4a002010-06-28 08:26:15 +0000842 // FIXME: does this need to be casted to match resultTy?
843 return L;
844 }
845 }
846
Zhongxing Xua1718c72009-04-03 07:33:13 +0000847 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000848 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000849
Ted Kremenek3bccf082009-07-11 00:58:27 +0000850 switch (MR->getKind()) {
851 case MemRegion::SymbolicRegionKind: {
852 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000853 SymbolRef Sym = SR->getSymbol();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000854 QualType T = Sym->getType(Ctx);
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000855 QualType EleTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000856
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000857 if (const PointerType *PT = T->getAs<PointerType>())
858 EleTy = PT->getPointeeType();
859 else
John McCall183700f2009-09-21 23:43:11 +0000860 EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000861
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000862 const NonLoc &ZeroIdx = svalBuilder.makeZeroArrayIndex();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000863 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +0000864 break;
Zhongxing Xu005f07b2009-06-19 04:51:14 +0000865 }
Ted Kremenek3bccf082009-07-11 00:58:27 +0000866 case MemRegion::AllocaRegionKind: {
Ted Kremenek3bccf082009-07-11 00:58:27 +0000867 const AllocaRegion *AR = cast<AllocaRegion>(MR);
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000868 QualType EleTy = Ctx.CharTy; // Create an ElementRegion of bytes.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000869 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000870 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +0000871 break;
Ted Kremenek3bccf082009-07-11 00:58:27 +0000872 }
Zhongxing Xua1718c72009-04-03 07:33:13 +0000873
Ted Kremenek3bccf082009-07-11 00:58:27 +0000874 case MemRegion::ElementRegionKind: {
875 ER = cast<ElementRegion>(MR);
876 break;
877 }
Mike Stump1eb44332009-09-09 15:08:12 +0000878
Ted Kremenek3bccf082009-07-11 00:58:27 +0000879 // Not yet handled.
880 case MemRegion::VarRegionKind:
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000881 case MemRegion::StringRegionKind: {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000882
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000883 }
884 // Fall-through.
Ted Kremenek3bccf082009-07-11 00:58:27 +0000885 case MemRegion::CompoundLiteralRegionKind:
886 case MemRegion::FieldRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000887 case MemRegion::ObjCIvarRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000888 case MemRegion::CXXTempObjectRegionKind:
Zhongxing Xu4fd56812010-11-26 08:21:53 +0000889 case MemRegion::CXXBaseObjectRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000890 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000891
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000892 case MemRegion::FunctionTextRegionKind:
893 case MemRegion::BlockTextRegionKind:
Ted Kremenek0a8112a2009-11-25 23:53:07 +0000894 case MemRegion::BlockDataRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000895 // Technically this can happen if people do funny things with casts.
896 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000897
Ted Kremenekde0d2632010-01-05 02:18:06 +0000898 case MemRegion::CXXThisRegionKind:
899 assert(0 &&
900 "Cannot perform pointer arithmetic on implicit argument 'this'");
Ted Kremenek67d12872009-12-07 22:05:27 +0000901 case MemRegion::GenericMemSpaceRegionKind:
902 case MemRegion::StackLocalsSpaceRegionKind:
903 case MemRegion::StackArgumentsSpaceRegionKind:
904 case MemRegion::HeapSpaceRegionKind:
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000905 case MemRegion::NonStaticGlobalSpaceRegionKind:
906 case MemRegion::StaticGlobalSpaceRegionKind:
Ted Kremenek2b87ae42009-12-11 06:43:27 +0000907 case MemRegion::UnknownSpaceRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000908 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
909 return UnknownVal();
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000910 }
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000911
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000912 SVal Idx = ER->getIndex();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000913 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000914
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000915 // For now, only support:
916 // (a) concrete integer indices that can easily be resolved
917 // (b) 0 + symbolic index
918 if (Base) {
919 if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) {
Ted Kremenek846eabd2010-12-01 21:28:31 +0000920 // FIXME: Should use SValBuilder here.
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000921 SVal NewIdx =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000922 Base->evalBinOp(svalBuilder, Op,
923 cast<nonloc::ConcreteInt>(svalBuilder.convertToArrayIndex(*Offset)));
Ted Kremenek02282ac2010-09-15 03:13:30 +0000924
925 if (!isa<NonLoc>(NewIdx))
926 return UnknownVal();
927
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000928 const MemRegion* NewER =
Ted Kremenek02282ac2010-09-15 03:13:30 +0000929 MRMgr.getElementRegion(ER->getElementType(), cast<NonLoc>(NewIdx),
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000930 ER->getSuperRegion(), Ctx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000931 return svalBuilder.makeLoc(NewER);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000932 }
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000933 if (0 == Base->getValue()) {
934 const MemRegion* NewER =
935 MRMgr.getElementRegion(ER->getElementType(), R,
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000936 ER->getSuperRegion(), Ctx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000937 return svalBuilder.makeLoc(NewER);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000938 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000939 }
Mike Stump1eb44332009-09-09 15:08:12 +0000940
Ted Kremenek5dc27462009-03-03 02:51:43 +0000941 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000942}
943
Ted Kremenek9af46f52009-06-16 22:36:44 +0000944//===----------------------------------------------------------------------===//
945// Loading values from regions.
946//===----------------------------------------------------------------------===//
947
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000948Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
Zhongxing Xubdfa85f2010-05-29 06:23:24 +0000949 const MemRegion *R) {
Zhongxing Xu42c67bf2010-05-29 06:49:04 +0000950
Ted Kremenek3baf6722010-11-24 00:54:37 +0000951 if (const SVal *V = lookup(B, R, BindingKey::Direct))
Zhongxing Xu42c67bf2010-05-29 06:49:04 +0000952 return *V;
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000953
Zhongxing Xu13d50172009-10-11 08:08:02 +0000954 return Optional<SVal>();
955}
956
957Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000958 const MemRegion *R) {
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000959 if (R->isBoundable())
960 if (const TypedRegion *TR = dyn_cast<TypedRegion>(R))
Zhongxing Xu018220c2010-08-11 06:10:55 +0000961 if (TR->getValueType()->isUnionType())
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000962 return UnknownVal();
963
Ted Kremenek3baf6722010-11-24 00:54:37 +0000964 if (const SVal *V = lookup(B, R, BindingKey::Default))
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000965 return *V;
Zhongxing Xu13d50172009-10-11 08:08:02 +0000966
967 return Optional<SVal>();
968}
969
Zhongxing Xu576bb922010-02-05 03:01:53 +0000970SVal RegionStoreManager::Retrieve(Store store, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000971 assert(!isa<UnknownVal>(L) && "location unknown");
972 assert(!isa<UndefinedVal>(L) && "location undefined");
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000973
Ted Kremenek29836f92010-11-11 23:10:10 +0000974 // For access to concrete addresses, return UnknownVal. Checks
975 // for null dereferences (and similar errors) are done by checkers, not
976 // the Store.
977 // FIXME: We can consider lazily symbolicating such memory, but we really
978 // should defer this when we can reason easily about symbolicating arrays
979 // of bytes.
980 if (isa<loc::ConcreteInt>(L)) {
981 return UnknownVal();
982 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000983
Ted Kremenek67f28532009-06-17 22:02:04 +0000984 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000985
Tom Care7b050302010-06-25 18:22:31 +0000986 if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR)) {
987 if (T.isNull()) {
988 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000989 T = SR->getSymbol()->getType(Ctx);
Tom Care7b050302010-06-25 18:22:31 +0000990 }
Zhongxing Xu81491852010-02-08 08:43:02 +0000991 MR = GetElementZeroRegion(MR, T);
Tom Care7b050302010-06-25 18:22:31 +0000992 }
Mike Stump1eb44332009-09-09 15:08:12 +0000993
Zhongxing Xu2db08ca2010-03-01 05:29:02 +0000994 if (isa<CodeTextRegion>(MR)) {
995 assert(0 && "Why load from a code text region?");
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000996 return UnknownVal();
Zhongxing Xu2db08ca2010-03-01 05:29:02 +0000997 }
Mike Stump1eb44332009-09-09 15:08:12 +0000998
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000999 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1000 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Ted Kremenek67f28532009-06-17 22:02:04 +00001001 const TypedRegion *R = cast<TypedRegion>(MR);
Zhongxing Xu018220c2010-08-11 06:10:55 +00001002 QualType RTy = R->getValueType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001003
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001004 // FIXME: We should eventually handle funny addressing. e.g.:
1005 //
1006 // int x = ...;
1007 // int *p = &x;
1008 // char *q = (char*) p;
1009 // char c = *q; // returns the first byte of 'x'.
1010 //
1011 // Such funny addressing will occur due to layering of regions.
1012
Douglas Gregorfb87b892010-04-26 21:31:17 +00001013 if (RTy->isStructureOrClassType())
Zhongxing Xu576bb922010-02-05 03:01:53 +00001014 return RetrieveStruct(store, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001015
Ted Kremenekd4e5a602009-08-06 21:43:54 +00001016 // FIXME: Handle unions.
1017 if (RTy->isUnionType())
Zhongxing Xuc999ed72010-02-04 02:39:47 +00001018 return UnknownVal();
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001019
1020 if (RTy->isArrayType())
Zhongxing Xu576bb922010-02-05 03:01:53 +00001021 return RetrieveArray(store, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001022
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001023 // FIXME: handle Vector types.
1024 if (RTy->isVectorType())
Zhongxing Xuc999ed72010-02-04 02:39:47 +00001025 return UnknownVal();
Zhongxing Xu99c20302009-06-28 14:16:39 +00001026
1027 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
Zhongxing Xu576bb922010-02-05 03:01:53 +00001028 return CastRetrievedVal(RetrieveField(store, FR), FR, T, false);
Zhongxing Xu99c20302009-06-28 14:16:39 +00001029
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001030 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1031 // FIXME: Here we actually perform an implicit conversion from the loaded
1032 // value to the element type. Eventually we want to compose these values
1033 // more intelligently. For example, an 'element' can encompass multiple
1034 // bound regions (e.g., several bound bytes), or could be a subset of
1035 // a larger value.
Zhongxing Xu576bb922010-02-05 03:01:53 +00001036 return CastRetrievedVal(RetrieveElement(store, ER), ER, T, false);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001037 }
Mike Stump1eb44332009-09-09 15:08:12 +00001038
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001039 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1040 // FIXME: Here we actually perform an implicit conversion from the loaded
1041 // value to the ivar type. What we should model is stores to ivars
1042 // that blow past the extent of the ivar. If the address of the ivar is
1043 // reinterpretted, it is possible we stored a different value that could
1044 // fit within the ivar. Either we need to cast these when storing them
1045 // or reinterpret them lazily (as we do here).
Zhongxing Xu576bb922010-02-05 03:01:53 +00001046 return CastRetrievedVal(RetrieveObjCIvar(store, IVR), IVR, T, false);
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001047 }
Mike Stump1eb44332009-09-09 15:08:12 +00001048
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001049 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1050 // FIXME: Here we actually perform an implicit conversion from the loaded
1051 // value to the variable type. What we should model is stores to variables
1052 // that blow past the extent of the variable. If the address of the
1053 // variable is reinterpretted, it is possible we stored a different value
1054 // that could fit within the variable. Either we need to cast these when
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001055 // storing them or reinterpret them lazily (as we do here).
Zhongxing Xu576bb922010-02-05 03:01:53 +00001056 return CastRetrievedVal(RetrieveVar(store, VR), VR, T, false);
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001057 }
Ted Kremenek25c54572009-07-20 22:58:02 +00001058
Zhongxing Xu576bb922010-02-05 03:01:53 +00001059 RegionBindings B = GetRegionBindings(store);
Ted Kremenek3baf6722010-11-24 00:54:37 +00001060 const SVal *V = lookup(B, R, BindingKey::Direct);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001061
1062 // Check if the region has a binding.
1063 if (V)
Zhongxing Xuc999ed72010-02-04 02:39:47 +00001064 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001065
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001066 // The location does not have a bound value. This means that it has
1067 // the value it had upon its creation and/or entry to the analyzed
1068 // function/method. These are either symbolic values or 'undefined'.
Ted Kremenekde0d2632010-01-05 02:18:06 +00001069 if (R->hasStackNonParametersStorage()) {
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001070 // All stack variables are considered to have undefined values
1071 // upon creation. All heap allocated blocks are considered to
1072 // have undefined values as well unless they are explicitly bound
1073 // to specific values.
Zhongxing Xuc999ed72010-02-04 02:39:47 +00001074 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001075 }
1076
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001077 // All other values are symbolic.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001078 return svalBuilder.getRegionValueSymbolVal(R);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001079}
Mike Stump1eb44332009-09-09 15:08:12 +00001080
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001081std::pair<Store, const MemRegion *>
Ted Kremenek451ac092009-08-06 04:50:20 +00001082RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001083 if (Optional<SVal> OV = getDirectBinding(B, R))
1084 if (const nonloc::LazyCompoundVal *V =
1085 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001086 return std::make_pair(V->getStore(), V->getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001087
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001088 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001089 const std::pair<Store, const MemRegion *> &X =
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001090 GetLazyBinding(B, ER->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001091
Ted Kremenek8ec4aac2010-02-09 19:11:53 +00001092 if (X.second)
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001093 return std::make_pair(X.first,
1094 MRMgr.getElementRegionWithSuper(ER, X.second));
Mike Stump1eb44332009-09-09 15:08:12 +00001095 }
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001096 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001097 const std::pair<Store, const MemRegion *> &X =
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001098 GetLazyBinding(B, FR->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001099
Ted Kremenek8ec4aac2010-02-09 19:11:53 +00001100 if (X.second)
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001101 return std::make_pair(X.first,
1102 MRMgr.getFieldRegionWithSuper(FR, X.second));
1103 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001104 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
Zhongxing Xudcbcbdc2010-02-10 02:02:10 +00001105 // possible for a valid lazy binding.
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001106 return std::make_pair((Store) 0, (const MemRegion *) 0);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001107}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001108
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001109SVal RegionStoreManager::RetrieveElement(Store store,
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001110 const ElementRegion* R) {
1111 // Check if the region has a binding.
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001112 RegionBindings B = GetRegionBindings(store);
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001113 if (const Optional<SVal> &V = getDirectBinding(B, R))
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001114 return *V;
1115
Ted Kremenek921109a2009-07-01 23:19:52 +00001116 const MemRegion* superR = R->getSuperRegion();
1117
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001118 // Check if the region is an element region of a string literal.
Ted Kremenek921109a2009-07-01 23:19:52 +00001119 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001120 // FIXME: Handle loads from strings where the literal is treated as
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001121 // an integer, e.g., *((unsigned int*)"hello")
Zhongxing Xu018220c2010-08-11 06:10:55 +00001122 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001123 if (T != Ctx.getCanonicalType(R->getElementType()))
1124 return UnknownVal();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001125
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001126 const StringLiteral *Str = StrR->getStringLiteral();
1127 SVal Idx = R->getIndex();
1128 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1129 int64_t i = CI->getValue().getSExtValue();
Mike Stump1eb44332009-09-09 15:08:12 +00001130 int64_t byteLength = Str->getByteLength();
Jordy Rose167cc372010-07-29 06:40:33 +00001131 // Technically, only i == byteLength is guaranteed to be null.
1132 // However, such overflows should be caught before reaching this point;
1133 // the only time such an access would be made is if a string literal was
1134 // used to initialize a larger array.
Benjamin Kramer2f4eaef2010-08-17 12:54:38 +00001135 char c = (i >= byteLength) ? '\0' : Str->getString()[i];
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001136 return svalBuilder.makeIntVal(c, T);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001137 }
1138 }
Ted Kremenek1e4a32a2010-09-01 23:00:46 +00001139
1140 // Check for loads from a code text region. For such loads, just give up.
Ted Kremenek08140f92010-09-02 00:34:30 +00001141 if (isa<CodeTextRegion>(superR))
Ted Kremenek1e4a32a2010-09-01 23:00:46 +00001142 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001143
Ted Kremeneka709b872010-05-31 01:22:04 +00001144 // Handle the case where we are indexing into a larger scalar object.
1145 // For example, this handles:
1146 // int x = ...
1147 // char *y = &x;
1148 // return *y;
1149 // FIXME: This is a hack, and doesn't do anything really intelligent yet.
Zhongxing Xu7caf9b32010-08-02 04:56:14 +00001150 const RegionRawOffset &O = R->getAsArrayOffset();
Ted Kremeneka709b872010-05-31 01:22:04 +00001151 if (const TypedRegion *baseR = dyn_cast_or_null<TypedRegion>(O.getRegion())) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001152 QualType baseT = baseR->getValueType();
Ted Kremeneka709b872010-05-31 01:22:04 +00001153 if (baseT->isScalarType()) {
1154 QualType elemT = R->getElementType();
1155 if (elemT->isScalarType()) {
1156 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
1157 if (const Optional<SVal> &V = getDirectBinding(B, superR)) {
1158 if (SymbolRef parentSym = V->getAsSymbol())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001159 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001160
Ted Kremeneka709b872010-05-31 01:22:04 +00001161 if (V->isUnknownOrUndef())
1162 return *V;
1163 // Other cases: give up. We are indexing into a larger object
1164 // that has some value, but we don't know how to handle that yet.
1165 return UnknownVal();
1166 }
1167 }
1168 }
Zhongxing Xu42c67bf2010-05-29 06:49:04 +00001169 }
Zhongxing Xu7abe0192009-06-30 12:32:59 +00001170 }
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001171 return RetrieveFieldOrElementCommon(store, R, R->getElementType(), superR);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001172}
1173
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001174SVal RegionStoreManager::RetrieveField(Store store,
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001175 const FieldRegion* R) {
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001176
1177 // Check if the region has a binding.
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001178 RegionBindings B = GetRegionBindings(store);
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001179 if (const Optional<SVal> &V = getDirectBinding(B, R))
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001180 return *V;
1181
Zhongxing Xu018220c2010-08-11 06:10:55 +00001182 QualType Ty = R->getValueType();
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001183 return RetrieveFieldOrElementCommon(store, R, Ty, R->getSuperRegion());
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001184}
Mike Stump1eb44332009-09-09 15:08:12 +00001185
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001186Optional<SVal>
1187RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B,
1188 const MemRegion *superR,
1189 const TypedRegion *R,
1190 QualType Ty) {
1191
1192 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
1193 if (SymbolRef parentSym = D->getAsSymbol())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001194 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001195
1196 if (D->isZeroConstant())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001197 return svalBuilder.makeZeroVal(Ty);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001198
1199 if (D->isUnknownOrUndef())
1200 return *D;
1201
1202 assert(0 && "Unknown default value");
1203 }
1204
1205 return Optional<SVal>();
1206}
1207
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001208SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001209 const TypedRegion *R,
1210 QualType Ty,
1211 const MemRegion *superR) {
1212
Mike Stump1eb44332009-09-09 15:08:12 +00001213 // At this point we have already checked in either RetrieveElement or
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001214 // RetrieveField if 'R' has a direct binding.
Mike Stump1eb44332009-09-09 15:08:12 +00001215
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001216 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001217
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001218 while (superR) {
Ted Kremenekc1143e52010-10-26 00:06:17 +00001219 if (const Optional<SVal> &D =
1220 RetrieveDerivedDefaultValue(B, superR, R, Ty))
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001221 return *D;
Mike Stump1eb44332009-09-09 15:08:12 +00001222
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001223 // If our super region is a field or element itself, walk up the region
1224 // hierarchy to see if there is a default value installed in an ancestor.
Ted Kremenekc1143e52010-10-26 00:06:17 +00001225 if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) {
1226 superR = SR->getSuperRegion();
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001227 continue;
1228 }
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001229 break;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001230 }
Mike Stump1eb44332009-09-09 15:08:12 +00001231
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001232 // Lazy binding?
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001233 Store lazyBindingStore = NULL;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001234 const MemRegion *lazyBindingRegion = NULL;
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001235 llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001236
Ted Kremenek8ec4aac2010-02-09 19:11:53 +00001237 if (lazyBindingRegion) {
1238 if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion))
1239 return RetrieveElement(lazyBindingStore, ER);
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001240 return RetrieveField(lazyBindingStore,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001241 cast<FieldRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001242 }
1243
Ted Kremenekde0d2632010-01-05 02:18:06 +00001244 if (R->hasStackNonParametersStorage()) {
Ted Kremenek41be9672010-09-01 23:27:26 +00001245 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001246 // Currently we don't reason specially about Clang-style vectors. Check
1247 // if superR is a vector and if so return Unknown.
1248 if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001249 if (typedSuperR->getValueType()->isVectorType())
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001250 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001251 }
Ted Kremenek41be9672010-09-01 23:27:26 +00001252
1253 // FIXME: We also need to take ElementRegions with symbolic indexes into
1254 // account.
1255 if (!ER->getIndex().isConstant())
1256 return UnknownVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001257 }
Mike Stump1eb44332009-09-09 15:08:12 +00001258
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001259 return UndefinedVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001260 }
Mike Stump1eb44332009-09-09 15:08:12 +00001261
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001262 // All other values are symbolic.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001263 return svalBuilder.getRegionValueSymbolVal(R);
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001264}
Mike Stump1eb44332009-09-09 15:08:12 +00001265
Zhongxing Xu576bb922010-02-05 03:01:53 +00001266SVal RegionStoreManager::RetrieveObjCIvar(Store store, const ObjCIvarRegion* R){
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001267
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001268 // Check if the region has a binding.
Zhongxing Xu576bb922010-02-05 03:01:53 +00001269 RegionBindings B = GetRegionBindings(store);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001270
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001271 if (const Optional<SVal> &V = getDirectBinding(B, R))
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001272 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001273
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001274 const MemRegion *superR = R->getSuperRegion();
1275
Ted Kremenekab22ee92009-10-20 01:20:57 +00001276 // Check if the super region has a default binding.
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001277 if (const Optional<SVal> &V = getDefaultBinding(B, superR)) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001278 if (SymbolRef parentSym = V->getAsSymbol())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001279 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001280
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001281 // Other cases: give up.
1282 return UnknownVal();
1283 }
Mike Stump1eb44332009-09-09 15:08:12 +00001284
Zhongxing Xu576bb922010-02-05 03:01:53 +00001285 return RetrieveLazySymbol(R);
Ted Kremenek25c54572009-07-20 22:58:02 +00001286}
1287
Zhongxing Xu576bb922010-02-05 03:01:53 +00001288SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001289
Ted Kremenek9031dd72009-07-21 00:12:07 +00001290 // Check if the region has a binding.
Zhongxing Xu576bb922010-02-05 03:01:53 +00001291 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001292
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001293 if (const Optional<SVal> &V = getDirectBinding(B, R))
Ted Kremenek9031dd72009-07-21 00:12:07 +00001294 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001295
Ted Kremenek9031dd72009-07-21 00:12:07 +00001296 // Lazily derive a value for the VarRegion.
1297 const VarDecl *VD = R->getDecl();
Ted Kremenek4dc15662010-02-06 03:57:59 +00001298 QualType T = VD->getType();
1299 const MemSpaceRegion *MS = R->getMemorySpace();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001300
1301 if (isa<UnknownSpaceRegion>(MS) ||
Ted Kremenek4dc15662010-02-06 03:57:59 +00001302 isa<StackArgumentsSpaceRegion>(MS))
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001303 return svalBuilder.getRegionValueSymbolVal(R);
Mike Stump1eb44332009-09-09 15:08:12 +00001304
Ted Kremenek4dc15662010-02-06 03:57:59 +00001305 if (isa<GlobalsSpaceRegion>(MS)) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001306 if (isa<NonStaticGlobalSpaceRegion>(MS)) {
Ted Kremenek4552ff02010-03-30 20:31:04 +00001307 // Is 'VD' declared constant? If so, retrieve the constant value.
1308 QualType CT = Ctx.getCanonicalType(T);
1309 if (CT.isConstQualified()) {
1310 const Expr *Init = VD->getInit();
1311 // Do the null check first, as we want to call 'IgnoreParenCasts'.
1312 if (Init)
1313 if (const IntegerLiteral *IL =
1314 dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001315 const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL);
1316 return svalBuilder.evalCast(V, Init->getType(), IL->getType());
Ted Kremenek4552ff02010-03-30 20:31:04 +00001317 }
1318 }
1319
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001320 if (const Optional<SVal> &V = RetrieveDerivedDefaultValue(B, MS, R, CT))
1321 return V.getValue();
1322
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001323 return svalBuilder.getRegionValueSymbolVal(R);
Ted Kremenek4552ff02010-03-30 20:31:04 +00001324 }
Mike Stump1eb44332009-09-09 15:08:12 +00001325
Ted Kremenek4dc15662010-02-06 03:57:59 +00001326 if (T->isIntegerType())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001327 return svalBuilder.makeIntVal(0, T);
Ted Kremenek81861ab2010-02-06 04:04:46 +00001328 if (T->isPointerType())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001329 return svalBuilder.makeNull();
Ted Kremenek81861ab2010-02-06 04:04:46 +00001330
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001331 return UnknownVal();
Ted Kremenek4dc15662010-02-06 03:57:59 +00001332 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001333
Ted Kremenek9031dd72009-07-21 00:12:07 +00001334 return UndefinedVal();
1335}
1336
Zhongxing Xu576bb922010-02-05 03:01:53 +00001337SVal RegionStoreManager::RetrieveLazySymbol(const TypedRegion *R) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001338 // All other values are symbolic.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001339 return svalBuilder.getRegionValueSymbolVal(R);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001340}
1341
Zhongxing Xu576bb922010-02-05 03:01:53 +00001342SVal RegionStoreManager::RetrieveStruct(Store store, const TypedRegion* R) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001343 QualType T = R->getValueType();
Douglas Gregorfb87b892010-04-26 21:31:17 +00001344 assert(T->isStructureOrClassType());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001345 return svalBuilder.makeLazyCompoundVal(store, R);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001346}
1347
Zhongxing Xu576bb922010-02-05 03:01:53 +00001348SVal RegionStoreManager::RetrieveArray(Store store, const TypedRegion * R) {
Ted Kremenek091cbbd2010-09-14 23:29:38 +00001349 assert(Ctx.getAsConstantArrayType(R->getValueType()));
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001350 return svalBuilder.makeLazyCompoundVal(store, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001351}
1352
Ted Kremenek9af46f52009-06-16 22:36:44 +00001353//===----------------------------------------------------------------------===//
1354// Binding values to regions.
1355//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +00001356
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001357Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +00001358 if (isa<loc::MemRegionVal>(L))
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001359 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
Ted Kremenek3baf6722010-11-24 00:54:37 +00001360 return removeBinding(GetRegionBindings(store), R).getRoot();
Mike Stump1eb44332009-09-09 15:08:12 +00001361
Ted Kremenek0964a062009-01-21 06:57:53 +00001362 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001363}
1364
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001365Store RegionStoreManager::Bind(Store store, Loc L, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +00001366 if (isa<loc::ConcreteInt>(L))
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001367 return store;
Zhongxing Xu87453d12009-06-28 10:16:11 +00001368
Ted Kremenek9af46f52009-06-16 22:36:44 +00001369 // If we get here, the location should be a region.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001370 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001371
Ted Kremenek9af46f52009-06-16 22:36:44 +00001372 // Check if the region is a struct region.
1373 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
Zhongxing Xu018220c2010-08-11 06:10:55 +00001374 if (TR->getValueType()->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001375 return BindStruct(store, TR, V);
Mike Stump1eb44332009-09-09 15:08:12 +00001376
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001377 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1378 if (ER->getIndex().isZeroConstant()) {
1379 if (const TypedRegion *superR =
1380 dyn_cast<TypedRegion>(ER->getSuperRegion())) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001381 QualType superTy = superR->getValueType();
Ted Kremenek69181a82009-09-21 22:58:52 +00001382 // For now, just invalidate the fields of the struct/union/class.
Zhongxing Xu81fa4ec2010-08-21 11:03:37 +00001383 // This is for test rdar_test_7185607 in misc-ps-region-store.m.
Ted Kremenek69181a82009-09-21 22:58:52 +00001384 // FIXME: Precisely handle the fields of the record.
Jordy Rose58f8b202010-08-05 03:28:45 +00001385 if (superTy->isStructureOrClassType())
1386 return KillStruct(store, superR, UnknownVal());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001387 }
1388 }
1389 }
Ted Kremenek0954cde2009-09-24 04:11:44 +00001390 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1391 // Binding directly to a symbolic region should be treated as binding
1392 // to element 0.
Zhongxing Xu57663fe2010-08-15 10:08:38 +00001393 QualType T = SR->getSymbol()->getType(Ctx);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001394
Ted Kremenek852274d2009-12-16 03:18:58 +00001395 // FIXME: Is this the right way to handle symbols that are references?
1396 if (const PointerType *PT = T->getAs<PointerType>())
1397 T = PT->getPointeeType();
1398 else
1399 T = T->getAs<ReferenceType>()->getPointeeType();
1400
Ted Kremenek0954cde2009-09-24 04:11:44 +00001401 R = GetElementZeroRegion(SR, T);
1402 }
Mike Stump1eb44332009-09-09 15:08:12 +00001403
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001404 // Perform the binding.
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001405 RegionBindings B = GetRegionBindings(store);
Ted Kremenek3baf6722010-11-24 00:54:37 +00001406 return addBinding(B, R, BindingKey::Direct, V).getRoot();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001407}
1408
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001409Store RegionStoreManager::BindDecl(Store store, const VarRegion *VR,
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001410 SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +00001411
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001412 QualType T = VR->getDecl()->getType();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001413
Ted Kremenek0964a062009-01-21 06:57:53 +00001414 if (T->isArrayType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001415 return BindArray(store, VR, InitVal);
Douglas Gregorfb87b892010-04-26 21:31:17 +00001416 if (T->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001417 return BindStruct(store, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001418
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001419 return Bind(store, svalBuilder.makeLoc(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001420}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001421
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001422// FIXME: this method should be merged into Bind().
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001423Store RegionStoreManager::BindCompoundLiteral(Store store,
1424 const CompoundLiteralExpr *CL,
1425 const LocationContext *LC,
1426 SVal V) {
1427 return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)),
Ted Kremenek67d12872009-12-07 22:05:27 +00001428 V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001429}
1430
Zhongxing Xua5ce9662010-06-01 03:01:33 +00001431
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001432Store RegionStoreManager::setImplicitDefaultValue(Store store,
1433 const MemRegion *R,
1434 QualType T) {
Ted Kremenek027e2662009-11-19 20:20:24 +00001435 RegionBindings B = GetRegionBindings(store);
1436 SVal V;
1437
1438 if (Loc::IsLocType(T))
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001439 V = svalBuilder.makeNull();
Ted Kremenek027e2662009-11-19 20:20:24 +00001440 else if (T->isIntegerType())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001441 V = svalBuilder.makeZeroVal(T);
Douglas Gregorfb87b892010-04-26 21:31:17 +00001442 else if (T->isStructureOrClassType() || T->isArrayType()) {
Ted Kremenek027e2662009-11-19 20:20:24 +00001443 // Set the default value to a zero constant when it is a structure
1444 // or array. The type doesn't really matter.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001445 V = svalBuilder.makeZeroVal(Ctx.IntTy);
Ted Kremenek027e2662009-11-19 20:20:24 +00001446 }
1447 else {
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001448 return store;
Ted Kremenek027e2662009-11-19 20:20:24 +00001449 }
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001450
Ted Kremenek3baf6722010-11-24 00:54:37 +00001451 return addBinding(B, R, BindingKey::Default, V).getRoot();
Ted Kremenek027e2662009-11-19 20:20:24 +00001452}
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001453
1454Store RegionStoreManager::BindArray(Store store, const TypedRegion* R,
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001455 SVal Init) {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001456
Zhongxing Xu018220c2010-08-11 06:10:55 +00001457 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001458 QualType ElementTy = AT->getElementType();
Ted Kremenekfee90812010-01-26 23:51:00 +00001459 Optional<uint64_t> Size;
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001460
Ted Kremenekfee90812010-01-26 23:51:00 +00001461 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
1462 Size = CAT->getSize().getZExtValue();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001463
Jordy Rose167cc372010-07-29 06:40:33 +00001464 // Check if the init expr is a string literal.
1465 if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) {
1466 const StringRegion *S = cast<StringRegion>(MRV->getRegion());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001467
Jordy Rose167cc372010-07-29 06:40:33 +00001468 // Treat the string as a lazy compound value.
1469 nonloc::LazyCompoundVal LCV =
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001470 cast<nonloc::LazyCompoundVal>(svalBuilder.makeLazyCompoundVal(store, S));
Jordy Rose167cc372010-07-29 06:40:33 +00001471 return CopyLazyBindings(LCV, store, R);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001472 }
1473
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001474 // Handle lazy compound values.
1475 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001476 return CopyLazyBindings(*LCV, store, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001477
1478 // Remaining case: explicit compound values.
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001479
Ted Kremenek027e2662009-11-19 20:20:24 +00001480 if (Init.isUnknown())
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001481 return setImplicitDefaultValue(store, R, ElementTy);
1482
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001483 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001484 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Ted Kremenek46537392009-07-16 01:33:37 +00001485 uint64_t i = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001486
Ted Kremenekfee90812010-01-26 23:51:00 +00001487 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001488 // The init list might be shorter than the array length.
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001489 if (VI == VE)
1490 break;
1491
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001492 const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
Zhongxing Xu57663fe2010-08-15 10:08:38 +00001493 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001494
Douglas Gregorfb87b892010-04-26 21:31:17 +00001495 if (ElementTy->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001496 store = BindStruct(store, ER, *VI);
Jordy Rose59b6dca2010-08-20 01:05:59 +00001497 else if (ElementTy->isArrayType())
1498 store = BindArray(store, ER, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001499 else
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001500 store = Bind(store, svalBuilder.makeLoc(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001501 }
1502
Ted Kremenek027e2662009-11-19 20:20:24 +00001503 // If the init list is shorter than the array length, set the
1504 // array default value.
Ted Kremenekfee90812010-01-26 23:51:00 +00001505 if (Size.hasValue() && i < Size.getValue())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001506 store = setImplicitDefaultValue(store, R, ElementTy);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001507
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001508 return store;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001509}
1510
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001511Store RegionStoreManager::BindStruct(Store store, const TypedRegion* R,
1512 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001513
Ted Kremenek67f28532009-06-17 22:02:04 +00001514 if (!Features.supportsFields())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001515 return store;
Mike Stump1eb44332009-09-09 15:08:12 +00001516
Zhongxing Xu018220c2010-08-11 06:10:55 +00001517 QualType T = R->getValueType();
Douglas Gregorfb87b892010-04-26 21:31:17 +00001518 assert(T->isStructureOrClassType());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001519
Ted Kremenek6217b802009-07-29 21:53:49 +00001520 const RecordType* RT = T->getAs<RecordType>();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001521 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001522
1523 if (!RD->isDefinition())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001524 return store;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001525
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001526 // Handle lazy compound values.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001527 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001528 return CopyLazyBindings(*LCV, store, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001529
Ted Kremenek281e9dc2010-07-29 00:28:47 +00001530 // We may get non-CompoundVal accidentally due to imprecise cast logic or
1531 // that we are binding symbolic struct value. Kill the field values, and if
1532 // the value is symbolic go and bind it as a "default" binding.
Ted Kremenek4af473c2010-08-17 23:29:06 +00001533 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) {
1534 SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal();
1535 return KillStruct(store, R, SV);
1536 }
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001537
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001538 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001539 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001540
1541 RecordDecl::field_iterator FI, FE;
1542
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001543 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001544
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001545 if (VI == VE)
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001546 break;
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001547
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001548 QualType FTy = (*FI)->getType();
Ted Kremenekcf549592009-09-22 21:19:14 +00001549 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001550
Ted Kremenekcf549592009-09-22 21:19:14 +00001551 if (FTy->isArrayType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001552 store = BindArray(store, FR, *VI);
Douglas Gregorfb87b892010-04-26 21:31:17 +00001553 else if (FTy->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001554 store = BindStruct(store, FR, *VI);
Ted Kremenekcf549592009-09-22 21:19:14 +00001555 else
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001556 store = Bind(store, svalBuilder.makeLoc(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001557 }
1558
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001559 // There may be fewer values in the initialize list than the fields of struct.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001560 if (FI != FE) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001561 RegionBindings B = GetRegionBindings(store);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001562 B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false));
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001563 store = B.getRoot();
Zhongxing Xu13d50172009-10-11 08:08:02 +00001564 }
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001565
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001566 return store;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001567}
1568
Ted Kremenek281e9dc2010-07-29 00:28:47 +00001569Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R,
1570 SVal DefaultVal) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001571 RegionBindings B = GetRegionBindings(store);
1572 llvm::OwningPtr<RegionStoreSubRegionMap>
1573 SubRegions(getRegionStoreSubRegionMap(store));
1574 RemoveSubRegionBindings(B, R, *SubRegions);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001575
Zhongxing Xue4df9c42009-06-25 05:52:16 +00001576 // Set the default value of the struct region to "unknown".
Ted Kremenek3baf6722010-11-24 00:54:37 +00001577 return addBinding(B, R, BindingKey::Default, DefaultVal).getRoot();
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001578}
1579
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001580Store RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1581 Store store, const TypedRegion *R) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001582
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001583 // Nuke the old bindings stemming from R.
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001584 RegionBindings B = GetRegionBindings(store);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001585
Mike Stump1eb44332009-09-09 15:08:12 +00001586 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001587 SubRegions(getRegionStoreSubRegionMap(store));
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001588
Mike Stump1eb44332009-09-09 15:08:12 +00001589 // B and DVM are updated after the call to RemoveSubRegionBindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001590 RemoveSubRegionBindings(B, R, *SubRegions.get());
Mike Stump1eb44332009-09-09 15:08:12 +00001591
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001592 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1593 // results in a zero-copy algorithm.
Ted Kremenek3baf6722010-11-24 00:54:37 +00001594 return addBinding(B, R, BindingKey::Direct, V).getRoot();
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001595}
1596
1597//===----------------------------------------------------------------------===//
1598// "Raw" retrievals and bindings.
1599//===----------------------------------------------------------------------===//
1600
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001601
Ted Kremenek3baf6722010-11-24 00:54:37 +00001602RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K,
1603 SVal V) {
Jordy Rosed5addb42010-08-16 20:53:01 +00001604 if (!K.isValid())
Jordy Rosee7011172010-08-16 01:15:17 +00001605 return B;
Ted Kremenek3baf6722010-11-24 00:54:37 +00001606 return RBFactory.add(B, K, V);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001607}
1608
Ted Kremenek3baf6722010-11-24 00:54:37 +00001609RegionBindings RegionStoreManager::addBinding(RegionBindings B,
1610 const MemRegion *R,
1611 BindingKey::Kind k, SVal V) {
1612 return addBinding(B, BindingKey::Make(R, k), V);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001613}
1614
Ted Kremenek3baf6722010-11-24 00:54:37 +00001615const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) {
Jordy Rosed5addb42010-08-16 20:53:01 +00001616 if (!K.isValid())
Jordy Rosee7011172010-08-16 01:15:17 +00001617 return NULL;
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001618 return B.lookup(K);
1619}
1620
Ted Kremenek3baf6722010-11-24 00:54:37 +00001621const SVal *RegionStoreManager::lookup(RegionBindings B,
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001622 const MemRegion *R,
1623 BindingKey::Kind k) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001624 return lookup(B, BindingKey::Make(R, k));
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001625}
1626
Ted Kremenek3baf6722010-11-24 00:54:37 +00001627RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1628 BindingKey K) {
Jordy Rosed5addb42010-08-16 20:53:01 +00001629 if (!K.isValid())
Jordy Rosee7011172010-08-16 01:15:17 +00001630 return B;
Ted Kremenek3baf6722010-11-24 00:54:37 +00001631 return RBFactory.remove(B, K);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001632}
1633
Ted Kremenek3baf6722010-11-24 00:54:37 +00001634RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1635 const MemRegion *R,
1636 BindingKey::Kind k){
1637 return removeBinding(B, BindingKey::Make(R, k));
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001638}
1639
Ted Kremenek9af46f52009-06-16 22:36:44 +00001640//===----------------------------------------------------------------------===//
1641// State pruning.
1642//===----------------------------------------------------------------------===//
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001643
Ted Kremenek5499b842010-03-10 16:32:56 +00001644namespace {
1645class RemoveDeadBindingsWorker :
1646 public ClusterAnalysis<RemoveDeadBindingsWorker> {
1647 llvm::SmallVector<const SymbolicRegion*, 12> Postponed;
1648 SymbolReaper &SymReaper;
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001649 const StackFrameContext *CurrentLCtx;
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001650
Ted Kremenek5499b842010-03-10 16:32:56 +00001651public:
1652 RemoveDeadBindingsWorker(RegionStoreManager &rm, GRStateManager &stateMgr,
1653 RegionBindings b, SymbolReaper &symReaper,
Jordy Rose7dadf792010-07-01 20:09:55 +00001654 const StackFrameContext *LCtx)
Ted Kremenekd45d59f2010-10-26 00:06:15 +00001655 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b,
1656 /* includeGlobals = */ false),
Jordy Rose7dadf792010-07-01 20:09:55 +00001657 SymReaper(symReaper), CurrentLCtx(LCtx) {}
Ted Kremenek5499b842010-03-10 16:32:56 +00001658
1659 // Called by ClusterAnalysis.
1660 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C);
1661 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
Ted Kremenek5499b842010-03-10 16:32:56 +00001662
Ted Kremenek75a2d942010-04-01 00:15:55 +00001663 void VisitBindingKey(BindingKey K);
Ted Kremenek5499b842010-03-10 16:32:56 +00001664 bool UpdatePostponed();
1665 void VisitBinding(SVal V);
1666};
1667}
1668
1669void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
1670 RegionCluster &C) {
1671
1672 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
Jordy Rose7dadf792010-07-01 20:09:55 +00001673 if (SymReaper.isLive(VR))
Ted Kremenek5499b842010-03-10 16:32:56 +00001674 AddToWorkList(baseR, C);
1675
1676 return;
1677 }
1678
1679 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
1680 if (SymReaper.isLive(SR->getSymbol()))
1681 AddToWorkList(SR, C);
1682 else
1683 Postponed.push_back(SR);
1684
1685 return;
1686 }
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001687
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001688 if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
1689 AddToWorkList(baseR, C);
1690 return;
1691 }
1692
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001693 // CXXThisRegion in the current or parent location context is live.
1694 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001695 const StackArgumentsSpaceRegion *StackReg =
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001696 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
1697 const StackFrameContext *RegCtx = StackReg->getStackFrame();
1698 if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))
1699 AddToWorkList(TR, C);
1700 }
Ted Kremenek5499b842010-03-10 16:32:56 +00001701}
1702
1703void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
1704 BindingKey *I, BindingKey *E) {
Ted Kremenek75a2d942010-04-01 00:15:55 +00001705 for ( ; I != E; ++I)
1706 VisitBindingKey(*I);
Ted Kremenek5499b842010-03-10 16:32:56 +00001707}
1708
1709void RemoveDeadBindingsWorker::VisitBinding(SVal V) {
1710 // Is it a LazyCompoundVal? All referenced regions are live as well.
1711 if (const nonloc::LazyCompoundVal *LCS =
1712 dyn_cast<nonloc::LazyCompoundVal>(&V)) {
1713
1714 const MemRegion *LazyR = LCS->getRegion();
1715 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
1716 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
Ted Kremenek0ea0e8b2010-07-06 23:53:29 +00001717 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
1718 if (baseR && baseR->isSubRegionOf(LazyR))
Ted Kremenek5499b842010-03-10 16:32:56 +00001719 VisitBinding(RI.getData());
1720 }
1721 return;
1722 }
1723
1724 // If V is a region, then add it to the worklist.
1725 if (const MemRegion *R = V.getAsRegion())
1726 AddToWorkList(R);
1727
1728 // Update the set of live symbols.
1729 for (SVal::symbol_iterator SI=V.symbol_begin(), SE=V.symbol_end();
1730 SI!=SE;++SI)
1731 SymReaper.markLive(*SI);
1732}
1733
Ted Kremenek75a2d942010-04-01 00:15:55 +00001734void RemoveDeadBindingsWorker::VisitBindingKey(BindingKey K) {
1735 const MemRegion *R = K.getRegion();
1736
Ted Kremenek5499b842010-03-10 16:32:56 +00001737 // Mark this region "live" by adding it to the worklist. This will cause
1738 // use to visit all regions in the cluster (if we haven't visited them
1739 // already).
Ted Kremenek75a2d942010-04-01 00:15:55 +00001740 if (AddToWorkList(R)) {
1741 // Mark the symbol for any live SymbolicRegion as "live". This means we
1742 // should continue to track that symbol.
1743 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
1744 SymReaper.markLive(SymR->getSymbol());
Ted Kremenek5499b842010-03-10 16:32:56 +00001745
Ted Kremenek75a2d942010-04-01 00:15:55 +00001746 // For BlockDataRegions, enqueue the VarRegions for variables marked
1747 // with __block (passed-by-reference).
1748 // via BlockDeclRefExprs.
1749 if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
1750 for (BlockDataRegion::referenced_vars_iterator
1751 RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
1752 RI != RE; ++RI) {
1753 if ((*RI)->getDecl()->getAttr<BlocksAttr>())
1754 AddToWorkList(*RI);
1755 }
Ted Kremenek5499b842010-03-10 16:32:56 +00001756
Ted Kremenek75a2d942010-04-01 00:15:55 +00001757 // No possible data bindings on a BlockDataRegion.
1758 return;
Ted Kremenek5499b842010-03-10 16:32:56 +00001759 }
Ted Kremenek5499b842010-03-10 16:32:56 +00001760 }
1761
Ted Kremenek75a2d942010-04-01 00:15:55 +00001762 // Visit the data binding for K.
Ted Kremenek3baf6722010-11-24 00:54:37 +00001763 if (const SVal *V = RM.lookup(B, K))
Ted Kremenek5499b842010-03-10 16:32:56 +00001764 VisitBinding(*V);
1765}
1766
1767bool RemoveDeadBindingsWorker::UpdatePostponed() {
1768 // See if any postponed SymbolicRegions are actually live now, after
1769 // having done a scan.
1770 bool changed = false;
1771
1772 for (llvm::SmallVectorImpl<const SymbolicRegion*>::iterator
1773 I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) {
1774 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) {
1775 if (SymReaper.isLive(SR->getSymbol())) {
1776 changed |= AddToWorkList(SR);
1777 *I = NULL;
1778 }
1779 }
1780 }
1781
1782 return changed;
1783}
1784
Zhongxing Xu5e4cb342010-08-15 12:45:09 +00001785Store RegionStoreManager::RemoveDeadBindings(Store store,
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001786 const StackFrameContext *LCtx,
Zhongxing Xu72119c42010-02-05 05:34:29 +00001787 SymbolReaper& SymReaper,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001788 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +00001789{
Zhongxing Xu5e4cb342010-08-15 12:45:09 +00001790 RegionBindings B = GetRegionBindings(store);
Jordy Rose7dadf792010-07-01 20:09:55 +00001791 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
Ted Kremenek5499b842010-03-10 16:32:56 +00001792 W.GenerateClusters();
Mike Stump1eb44332009-09-09 15:08:12 +00001793
Ted Kremenek5499b842010-03-10 16:32:56 +00001794 // Enqueue the region roots onto the worklist.
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001795 for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(),
Ted Kremenek5499b842010-03-10 16:32:56 +00001796 E=RegionRoots.end(); I!=E; ++I)
1797 W.AddToWorkList(*I);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001798
Ted Kremenek5499b842010-03-10 16:32:56 +00001799 do W.RunWorkList(); while (W.UpdatePostponed());
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001800
Ted Kremenek9af46f52009-06-16 22:36:44 +00001801 // We have now scanned the store, marking reachable regions and symbols
1802 // as live. We now remove all the regions that are dead from the store
Mike Stump1eb44332009-09-09 15:08:12 +00001803 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenek451ac092009-08-06 04:50:20 +00001804 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek5499b842010-03-10 16:32:56 +00001805 const BindingKey &K = I.getKey();
1806
Ted Kremenekb7118f72010-03-10 16:38:41 +00001807 // If the cluster has been visited, we know the region has been marked.
Ted Kremenek5499b842010-03-10 16:32:56 +00001808 if (W.isVisited(K.getRegion()))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001809 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001810
Ted Kremenek5499b842010-03-10 16:32:56 +00001811 // Remove the dead entry.
Ted Kremenek3baf6722010-11-24 00:54:37 +00001812 B = removeBinding(B, K);
Mike Stump1eb44332009-09-09 15:08:12 +00001813
Ted Kremenek5499b842010-03-10 16:32:56 +00001814 // Mark all non-live symbols that this binding references as dead.
1815 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion()))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001816 SymReaper.maybeDead(SymR->getSymbol());
Mike Stump1eb44332009-09-09 15:08:12 +00001817
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001818 SVal X = I.getData();
Ted Kremenek093569c2009-08-02 05:00:15 +00001819 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1820 for (; SI != SE; ++SI)
1821 SymReaper.maybeDead(*SI);
1822 }
Zhongxing Xu5e4cb342010-08-15 12:45:09 +00001823
1824 return B.getRoot();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001825}
1826
Ted Kremenek5499b842010-03-10 16:32:56 +00001827
Jordy Roseff59efd2010-08-03 20:44:35 +00001828Store RegionStoreManager::EnterStackFrame(const GRState *state,
1829 const StackFrameContext *frame) {
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001830 FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001831 FunctionDecl::param_const_iterator PI = FD->param_begin();
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001832 Store store = state->getStore();
Zhongxing Xuc5063572010-03-16 13:14:16 +00001833
1834 if (CallExpr const *CE = dyn_cast<CallExpr>(frame->getCallSite())) {
1835 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1836
1837 // Copy the arg expression value to the arg variables.
1838 for (; AI != AE; ++AI, ++PI) {
1839 SVal ArgVal = state->getSVal(*AI);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001840 store = Bind(store,
1841 svalBuilder.makeLoc(MRMgr.getVarRegion(*PI,frame)), ArgVal);
Zhongxing Xuc5063572010-03-16 13:14:16 +00001842 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001843 } else if (const CXXConstructExpr *CE =
Zhongxing Xuc5063572010-03-16 13:14:16 +00001844 dyn_cast<CXXConstructExpr>(frame->getCallSite())) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001845 CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(),
Zhongxing Xuc5063572010-03-16 13:14:16 +00001846 AE = CE->arg_end();
1847
1848 // Copy the arg expression value to the arg variables.
1849 for (; AI != AE; ++AI, ++PI) {
1850 SVal ArgVal = state->getSVal(*AI);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001851 store = Bind(store,
1852 svalBuilder.makeLoc(MRMgr.getVarRegion(*PI,frame)), ArgVal);
Zhongxing Xuc5063572010-03-16 13:14:16 +00001853 }
1854 } else
Zhongxing Xub13453b2010-11-20 06:53:12 +00001855 assert(isa<CXXDestructorDecl>(frame->getDecl()));
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001856
Jordy Roseff59efd2010-08-03 20:44:35 +00001857 return store;
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001858}
1859
Ted Kremenek9af46f52009-06-16 22:36:44 +00001860//===----------------------------------------------------------------------===//
1861// Utility methods.
1862//===----------------------------------------------------------------------===//
1863
Ted Kremenek53ba0b62009-06-24 23:06:47 +00001864void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001865 const char* nl, const char *sep) {
Ted Kremenek451ac092009-08-06 04:50:20 +00001866 RegionBindings B = GetRegionBindings(store);
Ted Kremenekab22ee92009-10-20 01:20:57 +00001867 OS << "Store (direct and default bindings):" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +00001868
Ted Kremenek451ac092009-08-06 04:50:20 +00001869 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
Mike Stump1eb44332009-09-09 15:08:12 +00001870 OS << ' ' << I.getKey() << " : " << I.getData() << nl;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001871}