blob: 91f7cfaf6c83df7002dcd2cace03cf9aae1ea06f [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"
23#include "clang/Checker/PathSensitive/GRState.h"
24#include "clang/Checker/PathSensitive/GRStateTrait.h"
25#include "clang/Checker/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 Kremenek4ed45982009-08-05 05:31:02 +0000151 M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion)));
Ted Kremenekd8c01922009-08-05 19:09:24 +0000152 return true;
153 }
154
155 I->second = F.Add(I->second, SubRegion);
156 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 Xu461147f2010-02-05 05:24:20 +0000227 SVal EvalBinOp(BinaryOperator::Opcode Op,Loc L, NonLoc R, QualType resultTy);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000228
Mike Stump1eb44332009-09-09 15:08:12 +0000229 Store getInitialStore(const LocationContext *InitLoc) {
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000230 return RBFactory.GetEmptyMap().getRoot();
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000231 }
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000232
Ted Kremenek67f28532009-06-17 22:02:04 +0000233 //===-------------------------------------------------------------------===//
234 // Binding values to regions.
235 //===-------------------------------------------------------------------===//
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000236
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000237 Store InvalidateRegions(Store store,
238 const MemRegion * const *Begin,
239 const MemRegion * const *End,
240 const Expr *E, unsigned Count,
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000241 InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000242 bool invalidateGlobals,
243 InvalidatedRegions *Regions);
Mike Stump1eb44332009-09-09 15:08:12 +0000244
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000245public: // Made public for helper classes.
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000246
Zhongxing Xu13d50172009-10-11 08:08:02 +0000247 void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000248 RegionStoreSubRegionMap &M);
Mike Stump1eb44332009-09-09 15:08:12 +0000249
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000250 RegionBindings Add(RegionBindings B, BindingKey K, SVal V);
251
252 RegionBindings Add(RegionBindings B, const MemRegion *R,
253 BindingKey::Kind k, SVal V);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000254
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000255 const SVal *Lookup(RegionBindings B, BindingKey K);
256 const SVal *Lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000257
258 RegionBindings Remove(RegionBindings B, BindingKey K);
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000259 RegionBindings Remove(RegionBindings B, const MemRegion *R,
260 BindingKey::Kind k);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000261
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000262 RegionBindings Remove(RegionBindings B, const MemRegion *R) {
263 return Remove(Remove(B, R, BindingKey::Direct), R, BindingKey::Default);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000264 }
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000265
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000266public: // Part of public interface to class.
267
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000268 Store Bind(Store store, Loc LV, SVal V);
Ted Kremenek67f28532009-06-17 22:02:04 +0000269
Zhongxing Xu54460092010-06-01 04:49:26 +0000270 // BindDefault is only used to initialize a region with a default value.
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000271 Store BindDefault(Store store, const MemRegion *R, SVal V) {
Zhongxing Xu54460092010-06-01 04:49:26 +0000272 RegionBindings B = GetRegionBindings(store);
273 assert(!Lookup(B, R, BindingKey::Default));
274 assert(!Lookup(B, R, BindingKey::Direct));
275 return Add(B, R, BindingKey::Default, V).getRoot();
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000276 }
277
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000278 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL,
279 const LocationContext *LC, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000280
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000281 Store BindDecl(Store store, const VarRegion *VR, SVal InitVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000282
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000283 Store BindDeclWithNoInit(Store store, const VarRegion *) {
284 return store;
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000285 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000286
Ted Kremenek67f28532009-06-17 22:02:04 +0000287 /// BindStruct - Bind a compound value to a structure.
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000288 Store BindStruct(Store store, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000289
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000290 Store BindArray(Store store, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000291
292 /// KillStruct - Set the entire struct to unknown.
Ted Kremenek281e9dc2010-07-29 00:28:47 +0000293 Store KillStruct(Store store, const TypedRegion* R, SVal DefaultVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000294
Ted Kremenek67f28532009-06-17 22:02:04 +0000295 Store Remove(Store store, Loc LV);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000296
Ted Kremenek67f28532009-06-17 22:02:04 +0000297
298 //===------------------------------------------------------------------===//
299 // Loading values from regions.
300 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000301
Ted Kremenek67f28532009-06-17 22:02:04 +0000302 /// The high level logic for this method is this:
303 /// Retrieve (L)
304 /// if L has binding
305 /// return L's binding
306 /// else if L is in killset
307 /// return unknown
308 /// else
309 /// if L is on stack or heap
310 /// return undefined
311 /// else
312 /// return symbolic
Zhongxing Xu576bb922010-02-05 03:01:53 +0000313 SVal Retrieve(Store store, Loc L, QualType T = QualType());
Zhongxing Xu490b0f02009-06-25 04:50:44 +0000314
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000315 SVal RetrieveElement(Store store, const ElementRegion *R);
Zhongxing Xuc00346f2009-06-25 05:29:39 +0000316
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000317 SVal RetrieveField(Store store, const FieldRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000318
Zhongxing Xu576bb922010-02-05 03:01:53 +0000319 SVal RetrieveObjCIvar(Store store, const ObjCIvarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000320
Zhongxing Xu576bb922010-02-05 03:01:53 +0000321 SVal RetrieveVar(Store store, const VarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000322
Zhongxing Xu576bb922010-02-05 03:01:53 +0000323 SVal RetrieveLazySymbol(const TypedRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000324
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000325 SVal RetrieveFieldOrElementCommon(Store store, const TypedRegion *R,
Ted Kremenek566a6fa2009-08-06 22:33:36 +0000326 QualType Ty, const MemRegion *superR);
Mike Stump1eb44332009-09-09 15:08:12 +0000327
Ted Kremenek67f28532009-06-17 22:02:04 +0000328 /// Retrieve the values in a struct and return a CompoundVal, used when doing
Mike Stump1eb44332009-09-09 15:08:12 +0000329 /// struct copy:
330 /// struct s x, y;
Ted Kremenek67f28532009-06-17 22:02:04 +0000331 /// x = y;
332 /// y's value is retrieved by this method.
Zhongxing Xu576bb922010-02-05 03:01:53 +0000333 SVal RetrieveStruct(Store store, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000334
Zhongxing Xu576bb922010-02-05 03:01:53 +0000335 SVal RetrieveArray(Store store, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000336
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000337 /// Used to lazily generate derived symbols for bindings that are defined
338 /// implicitly by default bindings in a super region.
339 Optional<SVal> RetrieveDerivedDefaultValue(RegionBindings B,
340 const MemRegion *superR,
341 const TypedRegion *R, QualType Ty);
342
Zhongxing Xu944ebc62009-12-21 06:52:24 +0000343 /// Get the state and region whose binding this region R corresponds to.
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000344 std::pair<Store, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +0000345 GetLazyBinding(RegionBindings B, const MemRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000346
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000347 Store CopyLazyBindings(nonloc::LazyCompoundVal V, Store store,
348 const TypedRegion *R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000349
350 //===------------------------------------------------------------------===//
351 // State pruning.
352 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000353
Ted Kremenek67f28532009-06-17 22:02:04 +0000354 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
355 /// It returns a new Store with these values removed.
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000356 Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
357 SymbolReaper& SymReaper,
Ted Kremenek67f28532009-06-17 22:02:04 +0000358 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
359
Jordy Roseff59efd2010-08-03 20:44:35 +0000360 Store EnterStackFrame(const GRState *state, const StackFrameContext *frame);
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +0000361
Ted Kremenek67f28532009-06-17 22:02:04 +0000362 //===------------------------------------------------------------------===//
363 // Region "extents".
364 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000365
Jordy Rose32f26562010-07-04 00:00:41 +0000366 // FIXME: This method will soon be eliminated; see the note in Store.h.
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000367 DefinedOrUnknownSVal getSizeInElements(const GRState *state,
Zhongxing Xu3ed04d32010-01-18 08:54:31 +0000368 const MemRegion* R, QualType EleTy);
Ted Kremenek67f28532009-06-17 22:02:04 +0000369
370 //===------------------------------------------------------------------===//
Ted Kremenek67f28532009-06-17 22:02:04 +0000371 // Utility methods.
372 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000373
Ted Kremenek451ac092009-08-06 04:50:20 +0000374 static inline RegionBindings GetRegionBindings(Store store) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000375 return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000376 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000377
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000378 void print(Store store, llvm::raw_ostream& Out, const char* nl,
379 const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000380
381 void iterBindings(Store store, BindingsHandler& f) {
Ted Kremenek0e9910f2010-06-17 00:24:42 +0000382 RegionBindings B = GetRegionBindings(store);
383 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
384 const BindingKey &K = I.getKey();
385 if (!K.isDirect())
386 continue;
387 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) {
388 // FIXME: Possibly incorporate the offset?
389 if (!f.HandleBinding(*this, store, R, I.getData()))
390 return;
391 }
392 }
Ted Kremenek67f28532009-06-17 22:02:04 +0000393 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000394};
395
396} // end anonymous namespace
397
Ted Kremenek9af46f52009-06-16 22:36:44 +0000398//===----------------------------------------------------------------------===//
399// RegionStore creation.
400//===----------------------------------------------------------------------===//
401
402StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
403 RegionStoreFeatures F = maximal_features_tag();
404 return new RegionStoreManager(StMgr, F);
405}
406
407StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
408 RegionStoreFeatures F = minimal_features_tag();
409 F.enableFields(true);
410 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000411}
412
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000413
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000414RegionStoreSubRegionMap*
Zhongxing Xu13d50172009-10-11 08:08:02 +0000415RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
416 RegionBindings B = GetRegionBindings(store);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000417 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
Mike Stump1eb44332009-09-09 15:08:12 +0000418
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000419 llvm::SmallVector<const SubRegion*, 10> WL;
420
Ted Kremenek451ac092009-08-06 04:50:20 +0000421 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000422 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000423 M->process(WL, R);
Mike Stump1eb44332009-09-09 15:08:12 +0000424
Mike Stump1eb44332009-09-09 15:08:12 +0000425 // We also need to record in the subregion map "intermediate" regions that
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000426 // don't have direct bindings but are super regions of those that do.
427 while (!WL.empty()) {
428 const SubRegion *R = WL.back();
429 WL.pop_back();
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000430 M->process(WL, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000431 }
432
Ted Kremenek14453bf2009-03-03 19:02:42 +0000433 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000434}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000435
Ted Kremenek9af46f52009-06-16 22:36:44 +0000436//===----------------------------------------------------------------------===//
Ted Kremeneka4fab032010-03-10 07:19:59 +0000437// Region Cluster analysis.
438//===----------------------------------------------------------------------===//
439
440namespace {
Ted Kremenek5499b842010-03-10 16:32:56 +0000441template <typename DERIVED>
Ted Kremeneka4fab032010-03-10 07:19:59 +0000442class ClusterAnalysis {
443protected:
444 typedef BumpVector<BindingKey> RegionCluster;
445 typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap;
Ted Kremenek5499b842010-03-10 16:32:56 +0000446 llvm::DenseMap<const RegionCluster*, unsigned> Visited;
447 typedef llvm::SmallVector<std::pair<const MemRegion *, RegionCluster*>, 10>
448 WorkList;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000449
450 BumpVectorContext BVC;
451 ClusterMap ClusterM;
Ted Kremenek5499b842010-03-10 16:32:56 +0000452 WorkList WL;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000453
454 RegionStoreManager &RM;
455 ASTContext &Ctx;
456 ValueManager &ValMgr;
457
Ted Kremenek5499b842010-03-10 16:32:56 +0000458 RegionBindings B;
459
Ted Kremeneka4fab032010-03-10 07:19:59 +0000460public:
Ted Kremenek5499b842010-03-10 16:32:56 +0000461 ClusterAnalysis(RegionStoreManager &rm, GRStateManager &StateMgr,
462 RegionBindings b)
463 : RM(rm), Ctx(StateMgr.getContext()), ValMgr(StateMgr.getValueManager()),
464 B(b) {}
Ted Kremeneka4fab032010-03-10 07:19:59 +0000465
Ted Kremenek5499b842010-03-10 16:32:56 +0000466 RegionBindings getRegionBindings() const { return B; }
Ted Kremeneka4fab032010-03-10 07:19:59 +0000467
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000468 RegionCluster &AddToCluster(BindingKey K) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000469 const MemRegion *R = K.getRegion();
470 const MemRegion *baseR = R->getBaseRegion();
471 RegionCluster &C = getCluster(baseR);
472 C.push_back(K, BVC);
473 static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000474 return C;
Ted Kremeneka4fab032010-03-10 07:19:59 +0000475 }
Ted Kremeneka4fab032010-03-10 07:19:59 +0000476
Ted Kremenek5499b842010-03-10 16:32:56 +0000477 bool isVisited(const MemRegion *R) {
478 return (bool) Visited[&getCluster(R->getBaseRegion())];
479 }
480
481 RegionCluster& getCluster(const MemRegion *R) {
482 RegionCluster *&CRef = ClusterM[R];
483 if (!CRef) {
484 void *Mem = BVC.getAllocator().template Allocate<RegionCluster>();
485 CRef = new (Mem) RegionCluster(BVC, 10);
486 }
487 return *CRef;
488 }
489
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000490 void GenerateClusters(bool includeGlobals = false) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000491 // Scan the entire set of bindings and make the region clusters.
492 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000493 RegionCluster &C = AddToCluster(RI.getKey());
Ted Kremenek5499b842010-03-10 16:32:56 +0000494 if (const MemRegion *R = RI.getData().getAsRegion()) {
495 // Generate a cluster, but don't add the region to the cluster
496 // if there aren't any bindings.
497 getCluster(R->getBaseRegion());
498 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000499 if (includeGlobals) {
500 const MemRegion *R = RI.getKey().getRegion();
501 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
502 AddToWorkList(R, C);
503 }
Ted Kremeneka4fab032010-03-10 07:19:59 +0000504 }
505 }
Ted Kremenek5499b842010-03-10 16:32:56 +0000506
507 bool AddToWorkList(const MemRegion *R, RegionCluster &C) {
508 if (unsigned &visited = Visited[&C])
509 return false;
510 else
511 visited = 1;
512
513 WL.push_back(std::make_pair(R, &C));
514 return true;
515 }
516
517 bool AddToWorkList(BindingKey K) {
518 return AddToWorkList(K.getRegion());
519 }
520
521 bool AddToWorkList(const MemRegion *R) {
522 const MemRegion *baseR = R->getBaseRegion();
523 return AddToWorkList(baseR, getCluster(baseR));
524 }
525
526 void RunWorkList() {
527 while (!WL.empty()) {
528 const MemRegion *baseR;
529 RegionCluster *C;
530 llvm::tie(baseR, C) = WL.back();
531 WL.pop_back();
532
533 // First visit the cluster.
534 static_cast<DERIVED*>(this)->VisitCluster(baseR, C->begin(), C->end());
535
Ted Kremenek75a2d942010-04-01 00:15:55 +0000536 // Next, visit the base region.
537 static_cast<DERIVED*>(this)->VisitBaseRegion(baseR);
Ted Kremenek5499b842010-03-10 16:32:56 +0000538 }
539 }
540
541public:
542 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C) {}
543 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E) {}
Ted Kremenek75a2d942010-04-01 00:15:55 +0000544 void VisitBaseRegion(const MemRegion *baseR) {}
Ted Kremenek5499b842010-03-10 16:32:56 +0000545};
Ted Kremeneka4fab032010-03-10 07:19:59 +0000546}
547
548//===----------------------------------------------------------------------===//
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000549// Binding invalidation.
550//===----------------------------------------------------------------------===//
551
Zhongxing Xu13d50172009-10-11 08:08:02 +0000552void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
553 const MemRegion *R,
554 RegionStoreSubRegionMap &M) {
Ted Kremeneka4fab032010-03-10 07:19:59 +0000555
Ted Kremenekdf165012010-02-02 22:38:47 +0000556 if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R))
557 for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end();
558 I != E; ++I)
559 RemoveSubRegionBindings(B, *I, M);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000560
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000561 B = Remove(B, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000562}
563
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000564namespace {
Ted Kremenek5499b842010-03-10 16:32:56 +0000565class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker>
566{
567 const Expr *Ex;
568 unsigned Count;
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000569 StoreManager::InvalidatedSymbols *IS;
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000570 StoreManager::InvalidatedRegions *Regions;
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000571public:
Ted Kremenek24c37ad2010-02-13 01:52:33 +0000572 InvalidateRegionsWorker(RegionStoreManager &rm,
Ted Kremenek5499b842010-03-10 16:32:56 +0000573 GRStateManager &stateMgr,
574 RegionBindings b,
575 const Expr *ex, unsigned count,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000576 StoreManager::InvalidatedSymbols *is,
577 StoreManager::InvalidatedRegions *r)
Ted Kremenek5499b842010-03-10 16:32:56 +0000578 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b),
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000579 Ex(ex), Count(count), IS(is), Regions(r) {}
Ted Kremeneka4fab032010-03-10 07:19:59 +0000580
Ted Kremenek5499b842010-03-10 16:32:56 +0000581 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
Ted Kremenek75a2d942010-04-01 00:15:55 +0000582 void VisitBaseRegion(const MemRegion *baseR);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000583
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000584private:
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000585 void VisitBinding(SVal V);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000586};
Ted Kremenek5b290652010-02-03 04:16:00 +0000587}
588
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000589void InvalidateRegionsWorker::VisitBinding(SVal V) {
Ted Kremenekc1ddcab2010-02-13 00:54:03 +0000590 // A symbol? Mark it touched by the invalidation.
591 if (IS)
592 if (SymbolRef Sym = V.getAsSymbol())
593 IS->insert(Sym);
Ted Kremeneka4fab032010-03-10 07:19:59 +0000594
Ted Kremenek24c37ad2010-02-13 01:52:33 +0000595 if (const MemRegion *R = V.getAsRegion()) {
596 AddToWorkList(R);
597 return;
598 }
599
600 // Is it a LazyCompoundVal? All references get invalidated as well.
601 if (const nonloc::LazyCompoundVal *LCS =
602 dyn_cast<nonloc::LazyCompoundVal>(&V)) {
603
604 const MemRegion *LazyR = LCS->getRegion();
605 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
606
607 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
Ted Kremenek0ea0e8b2010-07-06 23:53:29 +0000608 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
609 if (baseR && baseR->isSubRegionOf(LazyR))
Ted Kremenek24c37ad2010-02-13 01:52:33 +0000610 VisitBinding(RI.getData());
611 }
612
613 return;
614 }
615}
616
Ted Kremenek5499b842010-03-10 16:32:56 +0000617void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
618 BindingKey *I, BindingKey *E) {
619 for ( ; I != E; ++I) {
620 // Get the old binding. Is it a region? If so, add it to the worklist.
621 const BindingKey &K = *I;
622 if (const SVal *V = RM.Lookup(B, K))
623 VisitBinding(*V);
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000624
Ted Kremenek5499b842010-03-10 16:32:56 +0000625 B = RM.Remove(B, K);
626 }
627}
Ted Kremeneka4fab032010-03-10 07:19:59 +0000628
Ted Kremenek75a2d942010-04-01 00:15:55 +0000629void InvalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000630 if (IS) {
631 // Symbolic region? Mark that symbol touched by the invalidation.
632 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
633 IS->insert(SR->getSymbol());
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000634 }
635
Ted Kremenek5499b842010-03-10 16:32:56 +0000636 // BlockDataRegion? If so, invalidate captured variables that are passed
637 // by reference.
638 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
639 for (BlockDataRegion::referenced_vars_iterator
640 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
641 BI != BE; ++BI) {
642 const VarRegion *VR = *BI;
643 const VarDecl *VD = VR->getDecl();
644 if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage())
645 AddToWorkList(VR);
646 }
647 return;
648 }
649
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000650 // Otherwise, we have a normal data region. Record that we touched the region.
651 if (Regions)
652 Regions->push_back(baseR);
653
Ted Kremenek5499b842010-03-10 16:32:56 +0000654 if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
655 // Invalidate the region by setting its default value to
656 // conjured symbol. The type of the symbol is irrelavant.
657 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy,
658 Count);
659 B = RM.Add(B, baseR, BindingKey::Default, V);
660 return;
661 }
662
663 if (!baseR->isBoundable())
664 return;
665
666 const TypedRegion *TR = cast<TypedRegion>(baseR);
Zhongxing Xu018220c2010-08-11 06:10:55 +0000667 QualType T = TR->getValueType();
Ted Kremenek5499b842010-03-10 16:32:56 +0000668
669 // Invalidate the binding.
Zhongxing Xu61453402010-08-21 06:51:45 +0000670 if (T->isStructureType()) {
Zhongxing Xu0b46b1b2010-08-21 06:26:59 +0000671 // Invalidate the region by setting its default value to
672 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek5499b842010-03-10 16:32:56 +0000673 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy,
674 Count);
675 B = RM.Add(B, baseR, BindingKey::Default, V);
676 return;
677 }
678
679 if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
680 // Set the default value of the array to conjured symbol.
681 DefinedOrUnknownSVal V =
682 ValMgr.getConjuredSymbolVal(baseR, Ex, AT->getElementType(), Count);
683 B = RM.Add(B, baseR, BindingKey::Default, V);
684 return;
685 }
686
687 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, T, Count);
688 assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
689 B = RM.Add(B, baseR, BindingKey::Direct, V);
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000690}
691
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000692Store RegionStoreManager::InvalidateRegions(Store store,
693 const MemRegion * const *I,
694 const MemRegion * const *E,
695 const Expr *Ex, unsigned Count,
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000696 InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000697 bool invalidateGlobals,
698 InvalidatedRegions *Regions) {
Ted Kremenek5499b842010-03-10 16:32:56 +0000699 InvalidateRegionsWorker W(*this, StateMgr,
700 RegionStoreManager::GetRegionBindings(store),
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000701 Ex, Count, IS, Regions);
Ted Kremenek5499b842010-03-10 16:32:56 +0000702
703 // Scan the bindings and generate the clusters.
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000704 W.GenerateClusters(invalidateGlobals);
Ted Kremenek5499b842010-03-10 16:32:56 +0000705
706 // Add I .. E to the worklist.
707 for ( ; I != E; ++I)
708 W.AddToWorkList(*I);
709
710 W.RunWorkList();
711
712 // Return the new bindings.
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000713 RegionBindings B = W.getRegionBindings();
714
715 if (invalidateGlobals) {
716 // Bind the non-static globals memory space to a new symbol that we will
717 // use to derive the bindings for all non-static globals.
718 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
719 SVal V =
720 ValMgr.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex,
721 /* symbol type, doesn't matter */ Ctx.IntTy,
722 Count);
723 B = Add(B, BindingKey::Make(GS, BindingKey::Default), V);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000724
725 // Even if there are no bindings in the global scope, we still need to
726 // record that we touched it.
727 if (Regions)
728 Regions->push_back(GS);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000729 }
730
731 return B.getRoot();
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000732}
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000733
Ted Kremenek9af46f52009-06-16 22:36:44 +0000734//===----------------------------------------------------------------------===//
735// Extents for regions.
736//===----------------------------------------------------------------------===//
737
Zhongxing Xue884ff82009-11-12 02:48:32 +0000738DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state,
Zhongxing Xu3ed04d32010-01-18 08:54:31 +0000739 const MemRegion *R,
740 QualType EleTy) {
Jordy Rose32f26562010-07-04 00:00:41 +0000741 SVal Size = cast<SubRegion>(R)->getExtent(ValMgr);
742 SValuator &SVator = ValMgr.getSValuator();
743 const llvm::APSInt *SizeInt = SVator.getKnownValue(state, Size);
744 if (!SizeInt)
745 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000746
Jordy Rose32f26562010-07-04 00:00:41 +0000747 CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
Ted Kremenek555c77a2010-09-14 23:08:34 +0000748
749 if (Ctx.getAsVariableArrayType(EleTy)) {
750 // FIXME: We need to track extra state to properly record the size
751 // of VLAs. Returning UnknownVal here, however, is a stop-gap so that
752 // we don't have a divide-by-zero below.
753 return UnknownVal();
754 }
755
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000756 CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
Mike Stump1eb44332009-09-09 15:08:12 +0000757
Jordy Rose32f26562010-07-04 00:00:41 +0000758 // If a variable is reinterpreted as a type that doesn't fit into a larger
759 // type evenly, round it down.
760 // This is a signed value, since it's used in arithmetic with signed indices.
761 return ValMgr.makeIntVal(RegionSize / EleSize, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000762}
763
Ted Kremenek9af46f52009-06-16 22:36:44 +0000764//===----------------------------------------------------------------------===//
765// Location and region casting.
766//===----------------------------------------------------------------------===//
767
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000768/// ArrayToPointer - Emulates the "decay" of an array to a pointer
769/// type. 'Array' represents the lvalue of the array being decayed
770/// to a pointer, and the returned SVal represents the decayed
771/// version of that lvalue (i.e., a pointer to the first element of
772/// the array). This is called by GRExprEngine when evaluating casts
773/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000774SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000775 if (!isa<loc::MemRegionVal>(Array))
776 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000777
Ted Kremenekabb042f2008-12-13 19:24:37 +0000778 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
779 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000780
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000781 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000782 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000783
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000784 // Strip off typedefs from the ArrayRegion's ValueType.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000785 QualType T = ArrayR->getValueType().getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000786 ArrayType *AT = cast<ArrayType>(T);
787 T = AT->getElementType();
Mike Stump1eb44332009-09-09 15:08:12 +0000788
Ted Kremenek02282ac2010-09-15 03:13:30 +0000789 NonLoc ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000790 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000791}
792
Ted Kremenek9af46f52009-06-16 22:36:44 +0000793//===----------------------------------------------------------------------===//
794// Pointer arithmetic.
795//===----------------------------------------------------------------------===//
796
Zhongxing Xu461147f2010-02-05 05:24:20 +0000797SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R,
Ted Kremenek5c734622009-06-26 00:41:43 +0000798 QualType resultTy) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000799 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000800 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000801 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000802
Jordy Roseeac4a002010-06-28 08:26:15 +0000803 // Special case for zero RHS.
804 if (R.isZeroConstant()) {
805 switch (Op) {
806 default:
807 // Handle it normally.
808 break;
John McCall2de56d12010-08-25 11:45:40 +0000809 case BO_Add:
810 case BO_Sub:
Jordy Roseeac4a002010-06-28 08:26:15 +0000811 // FIXME: does this need to be casted to match resultTy?
812 return L;
813 }
814 }
815
Zhongxing Xua1718c72009-04-03 07:33:13 +0000816 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000817 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000818
Ted Kremenek3bccf082009-07-11 00:58:27 +0000819 switch (MR->getKind()) {
820 case MemRegion::SymbolicRegionKind: {
821 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000822 SymbolRef Sym = SR->getSymbol();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000823 QualType T = Sym->getType(Ctx);
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000824 QualType EleTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000825
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000826 if (const PointerType *PT = T->getAs<PointerType>())
827 EleTy = PT->getPointeeType();
828 else
John McCall183700f2009-09-21 23:43:11 +0000829 EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000830
Ted Kremenek02282ac2010-09-15 03:13:30 +0000831 const NonLoc &ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000832 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +0000833 break;
Zhongxing Xu005f07b2009-06-19 04:51:14 +0000834 }
Ted Kremenek3bccf082009-07-11 00:58:27 +0000835 case MemRegion::AllocaRegionKind: {
Ted Kremenek3bccf082009-07-11 00:58:27 +0000836 const AllocaRegion *AR = cast<AllocaRegion>(MR);
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000837 QualType EleTy = Ctx.CharTy; // Create an ElementRegion of bytes.
Ted Kremenek02282ac2010-09-15 03:13:30 +0000838 NonLoc ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000839 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +0000840 break;
Ted Kremenek3bccf082009-07-11 00:58:27 +0000841 }
Zhongxing Xua1718c72009-04-03 07:33:13 +0000842
Ted Kremenek3bccf082009-07-11 00:58:27 +0000843 case MemRegion::ElementRegionKind: {
844 ER = cast<ElementRegion>(MR);
845 break;
846 }
Mike Stump1eb44332009-09-09 15:08:12 +0000847
Ted Kremenek3bccf082009-07-11 00:58:27 +0000848 // Not yet handled.
849 case MemRegion::VarRegionKind:
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000850 case MemRegion::StringRegionKind: {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000851
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000852 }
853 // Fall-through.
Ted Kremenek3bccf082009-07-11 00:58:27 +0000854 case MemRegion::CompoundLiteralRegionKind:
855 case MemRegion::FieldRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000856 case MemRegion::ObjCIvarRegionKind:
Zhongxing Xubb141212009-12-16 11:27:52 +0000857 case MemRegion::CXXObjectRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000858 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000859
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000860 case MemRegion::FunctionTextRegionKind:
861 case MemRegion::BlockTextRegionKind:
Ted Kremenek0a8112a2009-11-25 23:53:07 +0000862 case MemRegion::BlockDataRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000863 // Technically this can happen if people do funny things with casts.
864 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000865
Ted Kremenekde0d2632010-01-05 02:18:06 +0000866 case MemRegion::CXXThisRegionKind:
867 assert(0 &&
868 "Cannot perform pointer arithmetic on implicit argument 'this'");
Ted Kremenek67d12872009-12-07 22:05:27 +0000869 case MemRegion::GenericMemSpaceRegionKind:
870 case MemRegion::StackLocalsSpaceRegionKind:
871 case MemRegion::StackArgumentsSpaceRegionKind:
872 case MemRegion::HeapSpaceRegionKind:
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000873 case MemRegion::NonStaticGlobalSpaceRegionKind:
874 case MemRegion::StaticGlobalSpaceRegionKind:
Ted Kremenek2b87ae42009-12-11 06:43:27 +0000875 case MemRegion::UnknownSpaceRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000876 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
877 return UnknownVal();
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000878 }
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000879
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000880 SVal Idx = ER->getIndex();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000881 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000882
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000883 // For now, only support:
884 // (a) concrete integer indices that can easily be resolved
885 // (b) 0 + symbolic index
886 if (Base) {
887 if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) {
888 // FIXME: Should use SValuator here.
889 SVal NewIdx =
890 Base->evalBinOp(ValMgr, Op,
Ted Kremenek46537392009-07-16 01:33:37 +0000891 cast<nonloc::ConcreteInt>(ValMgr.convertToArrayIndex(*Offset)));
Ted Kremenek02282ac2010-09-15 03:13:30 +0000892
893 if (!isa<NonLoc>(NewIdx))
894 return UnknownVal();
895
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000896 const MemRegion* NewER =
Ted Kremenek02282ac2010-09-15 03:13:30 +0000897 MRMgr.getElementRegion(ER->getElementType(), cast<NonLoc>(NewIdx),
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000898 ER->getSuperRegion(), Ctx);
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000899 return ValMgr.makeLoc(NewER);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000900 }
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000901 if (0 == Base->getValue()) {
902 const MemRegion* NewER =
903 MRMgr.getElementRegion(ER->getElementType(), R,
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000904 ER->getSuperRegion(), Ctx);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000905 return ValMgr.makeLoc(NewER);
906 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000907 }
Mike Stump1eb44332009-09-09 15:08:12 +0000908
Ted Kremenek5dc27462009-03-03 02:51:43 +0000909 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000910}
911
Ted Kremenek9af46f52009-06-16 22:36:44 +0000912//===----------------------------------------------------------------------===//
913// Loading values from regions.
914//===----------------------------------------------------------------------===//
915
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000916Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
Zhongxing Xubdfa85f2010-05-29 06:23:24 +0000917 const MemRegion *R) {
Zhongxing Xu42c67bf2010-05-29 06:49:04 +0000918
919 if (const SVal *V = Lookup(B, R, BindingKey::Direct))
920 return *V;
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000921
Zhongxing Xu13d50172009-10-11 08:08:02 +0000922 return Optional<SVal>();
923}
924
925Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000926 const MemRegion *R) {
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000927 if (R->isBoundable())
928 if (const TypedRegion *TR = dyn_cast<TypedRegion>(R))
Zhongxing Xu018220c2010-08-11 06:10:55 +0000929 if (TR->getValueType()->isUnionType())
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000930 return UnknownVal();
931
Ted Kremeneke393f4a2010-02-03 03:06:46 +0000932 if (const SVal *V = Lookup(B, R, BindingKey::Default))
933 return *V;
Zhongxing Xu13d50172009-10-11 08:08:02 +0000934
935 return Optional<SVal>();
936}
937
Zhongxing Xu576bb922010-02-05 03:01:53 +0000938SVal RegionStoreManager::Retrieve(Store store, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000939 assert(!isa<UnknownVal>(L) && "location unknown");
940 assert(!isa<UndefinedVal>(L) && "location undefined");
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000941
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000942 // FIXME: Is this even possible? Shouldn't this be treated as a null
943 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000944 if (isa<loc::ConcreteInt>(L))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000945 return UndefinedVal();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +0000946
Ted Kremenek67f28532009-06-17 22:02:04 +0000947 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000948
Tom Care7b050302010-06-25 18:22:31 +0000949 if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR)) {
950 if (T.isNull()) {
951 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000952 T = SR->getSymbol()->getType(Ctx);
Tom Care7b050302010-06-25 18:22:31 +0000953 }
Zhongxing Xu81491852010-02-08 08:43:02 +0000954 MR = GetElementZeroRegion(MR, T);
Tom Care7b050302010-06-25 18:22:31 +0000955 }
Mike Stump1eb44332009-09-09 15:08:12 +0000956
Zhongxing Xu2db08ca2010-03-01 05:29:02 +0000957 if (isa<CodeTextRegion>(MR)) {
958 assert(0 && "Why load from a code text region?");
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000959 return UnknownVal();
Zhongxing Xu2db08ca2010-03-01 05:29:02 +0000960 }
Mike Stump1eb44332009-09-09 15:08:12 +0000961
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000962 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
963 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Ted Kremenek67f28532009-06-17 22:02:04 +0000964 const TypedRegion *R = cast<TypedRegion>(MR);
Zhongxing Xu018220c2010-08-11 06:10:55 +0000965 QualType RTy = R->getValueType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000966
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000967 // FIXME: We should eventually handle funny addressing. e.g.:
968 //
969 // int x = ...;
970 // int *p = &x;
971 // char *q = (char*) p;
972 // char c = *q; // returns the first byte of 'x'.
973 //
974 // Such funny addressing will occur due to layering of regions.
975
Douglas Gregorfb87b892010-04-26 21:31:17 +0000976 if (RTy->isStructureOrClassType())
Zhongxing Xu576bb922010-02-05 03:01:53 +0000977 return RetrieveStruct(store, R);
Mike Stump1eb44332009-09-09 15:08:12 +0000978
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000979 // FIXME: Handle unions.
980 if (RTy->isUnionType())
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000981 return UnknownVal();
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000982
983 if (RTy->isArrayType())
Zhongxing Xu576bb922010-02-05 03:01:53 +0000984 return RetrieveArray(store, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000985
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000986 // FIXME: handle Vector types.
987 if (RTy->isVectorType())
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000988 return UnknownVal();
Zhongxing Xu99c20302009-06-28 14:16:39 +0000989
990 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
Zhongxing Xu576bb922010-02-05 03:01:53 +0000991 return CastRetrievedVal(RetrieveField(store, FR), FR, T, false);
Zhongxing Xu99c20302009-06-28 14:16:39 +0000992
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000993 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
994 // FIXME: Here we actually perform an implicit conversion from the loaded
995 // value to the element type. Eventually we want to compose these values
996 // more intelligently. For example, an 'element' can encompass multiple
997 // bound regions (e.g., several bound bytes), or could be a subset of
998 // a larger value.
Zhongxing Xu576bb922010-02-05 03:01:53 +0000999 return CastRetrievedVal(RetrieveElement(store, ER), ER, T, false);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001000 }
Mike Stump1eb44332009-09-09 15:08:12 +00001001
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001002 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1003 // FIXME: Here we actually perform an implicit conversion from the loaded
1004 // value to the ivar type. What we should model is stores to ivars
1005 // that blow past the extent of the ivar. If the address of the ivar is
1006 // reinterpretted, it is possible we stored a different value that could
1007 // fit within the ivar. Either we need to cast these when storing them
1008 // or reinterpret them lazily (as we do here).
Zhongxing Xu576bb922010-02-05 03:01:53 +00001009 return CastRetrievedVal(RetrieveObjCIvar(store, IVR), IVR, T, false);
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001010 }
Mike Stump1eb44332009-09-09 15:08:12 +00001011
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001012 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1013 // FIXME: Here we actually perform an implicit conversion from the loaded
1014 // value to the variable type. What we should model is stores to variables
1015 // that blow past the extent of the variable. If the address of the
1016 // variable is reinterpretted, it is possible we stored a different value
1017 // that could fit within the variable. Either we need to cast these when
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001018 // storing them or reinterpret them lazily (as we do here).
Zhongxing Xu576bb922010-02-05 03:01:53 +00001019 return CastRetrievedVal(RetrieveVar(store, VR), VR, T, false);
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001020 }
Ted Kremenek25c54572009-07-20 22:58:02 +00001021
Zhongxing Xu576bb922010-02-05 03:01:53 +00001022 RegionBindings B = GetRegionBindings(store);
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001023 const SVal *V = Lookup(B, R, BindingKey::Direct);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001024
1025 // Check if the region has a binding.
1026 if (V)
Zhongxing Xuc999ed72010-02-04 02:39:47 +00001027 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001028
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001029 // The location does not have a bound value. This means that it has
1030 // the value it had upon its creation and/or entry to the analyzed
1031 // function/method. These are either symbolic values or 'undefined'.
Ted Kremenekde0d2632010-01-05 02:18:06 +00001032 if (R->hasStackNonParametersStorage()) {
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001033 // All stack variables are considered to have undefined values
1034 // upon creation. All heap allocated blocks are considered to
1035 // have undefined values as well unless they are explicitly bound
1036 // to specific values.
Zhongxing Xuc999ed72010-02-04 02:39:47 +00001037 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001038 }
1039
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001040 // All other values are symbolic.
Zhongxing Xu14d23282010-03-01 06:56:52 +00001041 return ValMgr.getRegionValueSymbolVal(R);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001042}
Mike Stump1eb44332009-09-09 15:08:12 +00001043
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001044std::pair<Store, const MemRegion *>
Ted Kremenek451ac092009-08-06 04:50:20 +00001045RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001046 if (Optional<SVal> OV = getDirectBinding(B, R))
1047 if (const nonloc::LazyCompoundVal *V =
1048 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001049 return std::make_pair(V->getStore(), V->getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001050
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001051 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001052 const std::pair<Store, const MemRegion *> &X =
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001053 GetLazyBinding(B, ER->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001054
Ted Kremenek8ec4aac2010-02-09 19:11:53 +00001055 if (X.second)
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001056 return std::make_pair(X.first,
1057 MRMgr.getElementRegionWithSuper(ER, X.second));
Mike Stump1eb44332009-09-09 15:08:12 +00001058 }
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001059 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001060 const std::pair<Store, const MemRegion *> &X =
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001061 GetLazyBinding(B, FR->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001062
Ted Kremenek8ec4aac2010-02-09 19:11:53 +00001063 if (X.second)
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001064 return std::make_pair(X.first,
1065 MRMgr.getFieldRegionWithSuper(FR, X.second));
1066 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001067 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
Zhongxing Xudcbcbdc2010-02-10 02:02:10 +00001068 // possible for a valid lazy binding.
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001069 return std::make_pair((Store) 0, (const MemRegion *) 0);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001070}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001071
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001072SVal RegionStoreManager::RetrieveElement(Store store,
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001073 const ElementRegion* R) {
1074 // Check if the region has a binding.
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001075 RegionBindings B = GetRegionBindings(store);
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001076 if (const Optional<SVal> &V = getDirectBinding(B, R))
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001077 return *V;
1078
Ted Kremenek921109a2009-07-01 23:19:52 +00001079 const MemRegion* superR = R->getSuperRegion();
1080
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001081 // Check if the region is an element region of a string literal.
Ted Kremenek921109a2009-07-01 23:19:52 +00001082 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001083 // FIXME: Handle loads from strings where the literal is treated as
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001084 // an integer, e.g., *((unsigned int*)"hello")
Zhongxing Xu018220c2010-08-11 06:10:55 +00001085 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001086 if (T != Ctx.getCanonicalType(R->getElementType()))
1087 return UnknownVal();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001088
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001089 const StringLiteral *Str = StrR->getStringLiteral();
1090 SVal Idx = R->getIndex();
1091 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1092 int64_t i = CI->getValue().getSExtValue();
Mike Stump1eb44332009-09-09 15:08:12 +00001093 int64_t byteLength = Str->getByteLength();
Jordy Rose167cc372010-07-29 06:40:33 +00001094 // Technically, only i == byteLength is guaranteed to be null.
1095 // However, such overflows should be caught before reaching this point;
1096 // the only time such an access would be made is if a string literal was
1097 // used to initialize a larger array.
Benjamin Kramer2f4eaef2010-08-17 12:54:38 +00001098 char c = (i >= byteLength) ? '\0' : Str->getString()[i];
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001099 return ValMgr.makeIntVal(c, T);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001100 }
1101 }
Ted Kremenek1e4a32a2010-09-01 23:00:46 +00001102
1103 // Check for loads from a code text region. For such loads, just give up.
Ted Kremenek08140f92010-09-02 00:34:30 +00001104 if (isa<CodeTextRegion>(superR))
Ted Kremenek1e4a32a2010-09-01 23:00:46 +00001105 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001106
Ted Kremeneka709b872010-05-31 01:22:04 +00001107 // Handle the case where we are indexing into a larger scalar object.
1108 // For example, this handles:
1109 // int x = ...
1110 // char *y = &x;
1111 // return *y;
1112 // FIXME: This is a hack, and doesn't do anything really intelligent yet.
Zhongxing Xu7caf9b32010-08-02 04:56:14 +00001113 const RegionRawOffset &O = R->getAsArrayOffset();
Ted Kremeneka709b872010-05-31 01:22:04 +00001114 if (const TypedRegion *baseR = dyn_cast_or_null<TypedRegion>(O.getRegion())) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001115 QualType baseT = baseR->getValueType();
Ted Kremeneka709b872010-05-31 01:22:04 +00001116 if (baseT->isScalarType()) {
1117 QualType elemT = R->getElementType();
1118 if (elemT->isScalarType()) {
1119 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
1120 if (const Optional<SVal> &V = getDirectBinding(B, superR)) {
1121 if (SymbolRef parentSym = V->getAsSymbol())
1122 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001123
Ted Kremeneka709b872010-05-31 01:22:04 +00001124 if (V->isUnknownOrUndef())
1125 return *V;
1126 // Other cases: give up. We are indexing into a larger object
1127 // that has some value, but we don't know how to handle that yet.
1128 return UnknownVal();
1129 }
1130 }
1131 }
Zhongxing Xu42c67bf2010-05-29 06:49:04 +00001132 }
Zhongxing Xu7abe0192009-06-30 12:32:59 +00001133 }
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001134 return RetrieveFieldOrElementCommon(store, R, R->getElementType(), superR);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001135}
1136
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001137SVal RegionStoreManager::RetrieveField(Store store,
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001138 const FieldRegion* R) {
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001139
1140 // Check if the region has a binding.
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001141 RegionBindings B = GetRegionBindings(store);
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001142 if (const Optional<SVal> &V = getDirectBinding(B, R))
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001143 return *V;
1144
Zhongxing Xu018220c2010-08-11 06:10:55 +00001145 QualType Ty = R->getValueType();
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001146 return RetrieveFieldOrElementCommon(store, R, Ty, R->getSuperRegion());
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001147}
Mike Stump1eb44332009-09-09 15:08:12 +00001148
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001149Optional<SVal>
1150RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B,
1151 const MemRegion *superR,
1152 const TypedRegion *R,
1153 QualType Ty) {
1154
1155 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
1156 if (SymbolRef parentSym = D->getAsSymbol())
1157 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
1158
1159 if (D->isZeroConstant())
1160 return ValMgr.makeZeroVal(Ty);
1161
1162 if (D->isUnknownOrUndef())
1163 return *D;
1164
1165 assert(0 && "Unknown default value");
1166 }
1167
1168 return Optional<SVal>();
1169}
1170
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001171SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001172 const TypedRegion *R,
1173 QualType Ty,
1174 const MemRegion *superR) {
1175
Mike Stump1eb44332009-09-09 15:08:12 +00001176 // At this point we have already checked in either RetrieveElement or
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001177 // RetrieveField if 'R' has a direct binding.
Mike Stump1eb44332009-09-09 15:08:12 +00001178
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001179 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001180
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001181 while (superR) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001182 if (const Optional<SVal> &D = RetrieveDerivedDefaultValue(B, superR, R, Ty))
1183 return *D;
Mike Stump1eb44332009-09-09 15:08:12 +00001184
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001185 // If our super region is a field or element itself, walk up the region
1186 // hierarchy to see if there is a default value installed in an ancestor.
1187 if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) {
1188 superR = cast<SubRegion>(superR)->getSuperRegion();
1189 continue;
1190 }
Mike Stump1eb44332009-09-09 15:08:12 +00001191
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001192 break;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001193 }
Mike Stump1eb44332009-09-09 15:08:12 +00001194
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001195 // Lazy binding?
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001196 Store lazyBindingStore = NULL;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001197 const MemRegion *lazyBindingRegion = NULL;
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001198 llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001199
Ted Kremenek8ec4aac2010-02-09 19:11:53 +00001200 if (lazyBindingRegion) {
1201 if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion))
1202 return RetrieveElement(lazyBindingStore, ER);
Zhongxing Xubfcaf802010-02-05 02:26:30 +00001203 return RetrieveField(lazyBindingStore,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001204 cast<FieldRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001205 }
1206
Ted Kremenekde0d2632010-01-05 02:18:06 +00001207 if (R->hasStackNonParametersStorage()) {
Ted Kremenek41be9672010-09-01 23:27:26 +00001208 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001209 // Currently we don't reason specially about Clang-style vectors. Check
1210 // if superR is a vector and if so return Unknown.
1211 if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001212 if (typedSuperR->getValueType()->isVectorType())
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001213 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001214 }
Ted Kremenek41be9672010-09-01 23:27:26 +00001215
1216 // FIXME: We also need to take ElementRegions with symbolic indexes into
1217 // account.
1218 if (!ER->getIndex().isConstant())
1219 return UnknownVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001220 }
Mike Stump1eb44332009-09-09 15:08:12 +00001221
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001222 return UndefinedVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001223 }
Mike Stump1eb44332009-09-09 15:08:12 +00001224
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001225 // All other values are symbolic.
Zhongxing Xu14d23282010-03-01 06:56:52 +00001226 return ValMgr.getRegionValueSymbolVal(R);
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001227}
Mike Stump1eb44332009-09-09 15:08:12 +00001228
Zhongxing Xu576bb922010-02-05 03:01:53 +00001229SVal RegionStoreManager::RetrieveObjCIvar(Store store, const ObjCIvarRegion* R){
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001230
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001231 // Check if the region has a binding.
Zhongxing Xu576bb922010-02-05 03:01:53 +00001232 RegionBindings B = GetRegionBindings(store);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001233
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001234 if (const Optional<SVal> &V = getDirectBinding(B, R))
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001235 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001236
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001237 const MemRegion *superR = R->getSuperRegion();
1238
Ted Kremenekab22ee92009-10-20 01:20:57 +00001239 // Check if the super region has a default binding.
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001240 if (const Optional<SVal> &V = getDefaultBinding(B, superR)) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001241 if (SymbolRef parentSym = V->getAsSymbol())
1242 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001243
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001244 // Other cases: give up.
1245 return UnknownVal();
1246 }
Mike Stump1eb44332009-09-09 15:08:12 +00001247
Zhongxing Xu576bb922010-02-05 03:01:53 +00001248 return RetrieveLazySymbol(R);
Ted Kremenek25c54572009-07-20 22:58:02 +00001249}
1250
Zhongxing Xu576bb922010-02-05 03:01:53 +00001251SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001252
Ted Kremenek9031dd72009-07-21 00:12:07 +00001253 // Check if the region has a binding.
Zhongxing Xu576bb922010-02-05 03:01:53 +00001254 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001255
Ted Kremenek2cf073b2010-03-30 20:30:52 +00001256 if (const Optional<SVal> &V = getDirectBinding(B, R))
Ted Kremenek9031dd72009-07-21 00:12:07 +00001257 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001258
Ted Kremenek9031dd72009-07-21 00:12:07 +00001259 // Lazily derive a value for the VarRegion.
1260 const VarDecl *VD = R->getDecl();
Ted Kremenek4dc15662010-02-06 03:57:59 +00001261 QualType T = VD->getType();
1262 const MemSpaceRegion *MS = R->getMemorySpace();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001263
1264 if (isa<UnknownSpaceRegion>(MS) ||
Ted Kremenek4dc15662010-02-06 03:57:59 +00001265 isa<StackArgumentsSpaceRegion>(MS))
Zhongxing Xu14d23282010-03-01 06:56:52 +00001266 return ValMgr.getRegionValueSymbolVal(R);
Mike Stump1eb44332009-09-09 15:08:12 +00001267
Ted Kremenek4dc15662010-02-06 03:57:59 +00001268 if (isa<GlobalsSpaceRegion>(MS)) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001269 if (isa<NonStaticGlobalSpaceRegion>(MS)) {
Ted Kremenek4552ff02010-03-30 20:31:04 +00001270 // Is 'VD' declared constant? If so, retrieve the constant value.
1271 QualType CT = Ctx.getCanonicalType(T);
1272 if (CT.isConstQualified()) {
1273 const Expr *Init = VD->getInit();
1274 // Do the null check first, as we want to call 'IgnoreParenCasts'.
1275 if (Init)
1276 if (const IntegerLiteral *IL =
1277 dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) {
1278 const nonloc::ConcreteInt &V = ValMgr.makeIntVal(IL);
1279 return ValMgr.getSValuator().EvalCast(V, Init->getType(),
1280 IL->getType());
1281 }
1282 }
1283
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001284 if (const Optional<SVal> &V = RetrieveDerivedDefaultValue(B, MS, R, CT))
1285 return V.getValue();
1286
Zhongxing Xu14d23282010-03-01 06:56:52 +00001287 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenek4552ff02010-03-30 20:31:04 +00001288 }
Mike Stump1eb44332009-09-09 15:08:12 +00001289
Ted Kremenek4dc15662010-02-06 03:57:59 +00001290 if (T->isIntegerType())
1291 return ValMgr.makeIntVal(0, T);
Ted Kremenek81861ab2010-02-06 04:04:46 +00001292 if (T->isPointerType())
1293 return ValMgr.makeNull();
1294
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001295 return UnknownVal();
Ted Kremenek4dc15662010-02-06 03:57:59 +00001296 }
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001297
Ted Kremenek9031dd72009-07-21 00:12:07 +00001298 return UndefinedVal();
1299}
1300
Zhongxing Xu576bb922010-02-05 03:01:53 +00001301SVal RegionStoreManager::RetrieveLazySymbol(const TypedRegion *R) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001302 // All other values are symbolic.
Zhongxing Xu14d23282010-03-01 06:56:52 +00001303 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001304}
1305
Zhongxing Xu576bb922010-02-05 03:01:53 +00001306SVal RegionStoreManager::RetrieveStruct(Store store, const TypedRegion* R) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001307 QualType T = R->getValueType();
Douglas Gregorfb87b892010-04-26 21:31:17 +00001308 assert(T->isStructureOrClassType());
Zhongxing Xu576bb922010-02-05 03:01:53 +00001309 return ValMgr.makeLazyCompoundVal(store, R);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001310}
1311
Zhongxing Xu576bb922010-02-05 03:01:53 +00001312SVal RegionStoreManager::RetrieveArray(Store store, const TypedRegion * R) {
Ted Kremenek091cbbd2010-09-14 23:29:38 +00001313 assert(Ctx.getAsConstantArrayType(R->getValueType()));
Zhongxing Xu576bb922010-02-05 03:01:53 +00001314 return ValMgr.makeLazyCompoundVal(store, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001315}
1316
Ted Kremenek9af46f52009-06-16 22:36:44 +00001317//===----------------------------------------------------------------------===//
1318// Binding values to regions.
1319//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +00001320
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001321Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +00001322 if (isa<loc::MemRegionVal>(L))
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001323 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001324 return Remove(GetRegionBindings(store), R).getRoot();
Mike Stump1eb44332009-09-09 15:08:12 +00001325
Ted Kremenek0964a062009-01-21 06:57:53 +00001326 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001327}
1328
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001329Store RegionStoreManager::Bind(Store store, Loc L, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +00001330 if (isa<loc::ConcreteInt>(L))
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001331 return store;
Zhongxing Xu87453d12009-06-28 10:16:11 +00001332
Ted Kremenek9af46f52009-06-16 22:36:44 +00001333 // If we get here, the location should be a region.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001334 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001335
Ted Kremenek9af46f52009-06-16 22:36:44 +00001336 // Check if the region is a struct region.
1337 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
Zhongxing Xu018220c2010-08-11 06:10:55 +00001338 if (TR->getValueType()->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001339 return BindStruct(store, TR, V);
Mike Stump1eb44332009-09-09 15:08:12 +00001340
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001341 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1342 if (ER->getIndex().isZeroConstant()) {
1343 if (const TypedRegion *superR =
1344 dyn_cast<TypedRegion>(ER->getSuperRegion())) {
Zhongxing Xu018220c2010-08-11 06:10:55 +00001345 QualType superTy = superR->getValueType();
Ted Kremenek69181a82009-09-21 22:58:52 +00001346 // For now, just invalidate the fields of the struct/union/class.
Zhongxing Xu81fa4ec2010-08-21 11:03:37 +00001347 // This is for test rdar_test_7185607 in misc-ps-region-store.m.
Ted Kremenek69181a82009-09-21 22:58:52 +00001348 // FIXME: Precisely handle the fields of the record.
Jordy Rose58f8b202010-08-05 03:28:45 +00001349 if (superTy->isStructureOrClassType())
1350 return KillStruct(store, superR, UnknownVal());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001351 }
1352 }
1353 }
Ted Kremenek0954cde2009-09-24 04:11:44 +00001354 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1355 // Binding directly to a symbolic region should be treated as binding
1356 // to element 0.
Zhongxing Xu57663fe2010-08-15 10:08:38 +00001357 QualType T = SR->getSymbol()->getType(Ctx);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001358
Ted Kremenek852274d2009-12-16 03:18:58 +00001359 // FIXME: Is this the right way to handle symbols that are references?
1360 if (const PointerType *PT = T->getAs<PointerType>())
1361 T = PT->getPointeeType();
1362 else
1363 T = T->getAs<ReferenceType>()->getPointeeType();
1364
Ted Kremenek0954cde2009-09-24 04:11:44 +00001365 R = GetElementZeroRegion(SR, T);
1366 }
Mike Stump1eb44332009-09-09 15:08:12 +00001367
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001368 // Perform the binding.
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001369 RegionBindings B = GetRegionBindings(store);
1370 return Add(B, R, BindingKey::Direct, V).getRoot();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001371}
1372
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001373Store RegionStoreManager::BindDecl(Store store, const VarRegion *VR,
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001374 SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +00001375
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001376 QualType T = VR->getDecl()->getType();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001377
Ted Kremenek0964a062009-01-21 06:57:53 +00001378 if (T->isArrayType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001379 return BindArray(store, VR, InitVal);
Douglas Gregorfb87b892010-04-26 21:31:17 +00001380 if (T->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001381 return BindStruct(store, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001382
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001383 return Bind(store, ValMgr.makeLoc(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001384}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001385
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001386// FIXME: this method should be merged into Bind().
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001387Store RegionStoreManager::BindCompoundLiteral(Store store,
1388 const CompoundLiteralExpr *CL,
1389 const LocationContext *LC,
1390 SVal V) {
1391 return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)),
Ted Kremenek67d12872009-12-07 22:05:27 +00001392 V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001393}
1394
Zhongxing Xua5ce9662010-06-01 03:01:33 +00001395
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001396Store RegionStoreManager::setImplicitDefaultValue(Store store,
1397 const MemRegion *R,
1398 QualType T) {
Ted Kremenek027e2662009-11-19 20:20:24 +00001399 RegionBindings B = GetRegionBindings(store);
1400 SVal V;
1401
1402 if (Loc::IsLocType(T))
1403 V = ValMgr.makeNull();
1404 else if (T->isIntegerType())
1405 V = ValMgr.makeZeroVal(T);
Douglas Gregorfb87b892010-04-26 21:31:17 +00001406 else if (T->isStructureOrClassType() || T->isArrayType()) {
Ted Kremenek027e2662009-11-19 20:20:24 +00001407 // Set the default value to a zero constant when it is a structure
1408 // or array. The type doesn't really matter.
Zhongxing Xu57663fe2010-08-15 10:08:38 +00001409 V = ValMgr.makeZeroVal(Ctx.IntTy);
Ted Kremenek027e2662009-11-19 20:20:24 +00001410 }
1411 else {
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001412 return store;
Ted Kremenek027e2662009-11-19 20:20:24 +00001413 }
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001414
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001415 return Add(B, R, BindingKey::Default, V).getRoot();
Ted Kremenek027e2662009-11-19 20:20:24 +00001416}
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001417
1418Store RegionStoreManager::BindArray(Store store, const TypedRegion* R,
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001419 SVal Init) {
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001420
Zhongxing Xu018220c2010-08-11 06:10:55 +00001421 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001422 QualType ElementTy = AT->getElementType();
Ted Kremenekfee90812010-01-26 23:51:00 +00001423 Optional<uint64_t> Size;
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001424
Ted Kremenekfee90812010-01-26 23:51:00 +00001425 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
1426 Size = CAT->getSize().getZExtValue();
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001427
Jordy Rose167cc372010-07-29 06:40:33 +00001428 // Check if the init expr is a string literal.
1429 if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) {
1430 const StringRegion *S = cast<StringRegion>(MRV->getRegion());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001431
Jordy Rose167cc372010-07-29 06:40:33 +00001432 // Treat the string as a lazy compound value.
1433 nonloc::LazyCompoundVal LCV =
1434 cast<nonloc::LazyCompoundVal>(ValMgr.makeLazyCompoundVal(store, S));
1435 return CopyLazyBindings(LCV, store, R);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001436 }
1437
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001438 // Handle lazy compound values.
1439 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001440 return CopyLazyBindings(*LCV, store, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001441
1442 // Remaining case: explicit compound values.
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001443
Ted Kremenek027e2662009-11-19 20:20:24 +00001444 if (Init.isUnknown())
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001445 return setImplicitDefaultValue(store, R, ElementTy);
1446
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001447 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001448 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Ted Kremenek46537392009-07-16 01:33:37 +00001449 uint64_t i = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001450
Ted Kremenekfee90812010-01-26 23:51:00 +00001451 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001452 // The init list might be shorter than the array length.
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001453 if (VI == VE)
1454 break;
1455
Ted Kremenek02282ac2010-09-15 03:13:30 +00001456 const NonLoc &Idx = ValMgr.makeArrayIndex(i);
Zhongxing Xu57663fe2010-08-15 10:08:38 +00001457 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001458
Douglas Gregorfb87b892010-04-26 21:31:17 +00001459 if (ElementTy->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001460 store = BindStruct(store, ER, *VI);
Jordy Rose59b6dca2010-08-20 01:05:59 +00001461 else if (ElementTy->isArrayType())
1462 store = BindArray(store, ER, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001463 else
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001464 store = Bind(store, ValMgr.makeLoc(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001465 }
1466
Ted Kremenek027e2662009-11-19 20:20:24 +00001467 // If the init list is shorter than the array length, set the
1468 // array default value.
Ted Kremenekfee90812010-01-26 23:51:00 +00001469 if (Size.hasValue() && i < Size.getValue())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001470 store = setImplicitDefaultValue(store, R, ElementTy);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001471
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001472 return store;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001473}
1474
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001475Store RegionStoreManager::BindStruct(Store store, const TypedRegion* R,
1476 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001477
Ted Kremenek67f28532009-06-17 22:02:04 +00001478 if (!Features.supportsFields())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001479 return store;
Mike Stump1eb44332009-09-09 15:08:12 +00001480
Zhongxing Xu018220c2010-08-11 06:10:55 +00001481 QualType T = R->getValueType();
Douglas Gregorfb87b892010-04-26 21:31:17 +00001482 assert(T->isStructureOrClassType());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001483
Ted Kremenek6217b802009-07-29 21:53:49 +00001484 const RecordType* RT = T->getAs<RecordType>();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001485 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001486
1487 if (!RD->isDefinition())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001488 return store;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001489
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001490 // Handle lazy compound values.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001491 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001492 return CopyLazyBindings(*LCV, store, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001493
Ted Kremenek281e9dc2010-07-29 00:28:47 +00001494 // We may get non-CompoundVal accidentally due to imprecise cast logic or
1495 // that we are binding symbolic struct value. Kill the field values, and if
1496 // the value is symbolic go and bind it as a "default" binding.
Ted Kremenek4af473c2010-08-17 23:29:06 +00001497 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) {
1498 SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal();
1499 return KillStruct(store, R, SV);
1500 }
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001501
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001502 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001503 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001504
1505 RecordDecl::field_iterator FI, FE;
1506
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001507 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001508
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001509 if (VI == VE)
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001510 break;
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001511
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001512 QualType FTy = (*FI)->getType();
Ted Kremenekcf549592009-09-22 21:19:14 +00001513 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001514
Ted Kremenekcf549592009-09-22 21:19:14 +00001515 if (FTy->isArrayType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001516 store = BindArray(store, FR, *VI);
Douglas Gregorfb87b892010-04-26 21:31:17 +00001517 else if (FTy->isStructureOrClassType())
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001518 store = BindStruct(store, FR, *VI);
Ted Kremenekcf549592009-09-22 21:19:14 +00001519 else
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001520 store = Bind(store, ValMgr.makeLoc(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001521 }
1522
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001523 // There may be fewer values in the initialize list than the fields of struct.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001524 if (FI != FE) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001525 RegionBindings B = GetRegionBindings(store);
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001526 B = Add(B, R, BindingKey::Default, ValMgr.makeIntVal(0, false));
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001527 store = B.getRoot();
Zhongxing Xu13d50172009-10-11 08:08:02 +00001528 }
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001529
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001530 return store;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001531}
1532
Ted Kremenek281e9dc2010-07-29 00:28:47 +00001533Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R,
1534 SVal DefaultVal) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001535 RegionBindings B = GetRegionBindings(store);
1536 llvm::OwningPtr<RegionStoreSubRegionMap>
1537 SubRegions(getRegionStoreSubRegionMap(store));
1538 RemoveSubRegionBindings(B, R, *SubRegions);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001539
Zhongxing Xue4df9c42009-06-25 05:52:16 +00001540 // Set the default value of the struct region to "unknown".
Ted Kremenek281e9dc2010-07-29 00:28:47 +00001541 return Add(B, R, BindingKey::Default, DefaultVal).getRoot();
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001542}
1543
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001544Store RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1545 Store store, const TypedRegion *R) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001546
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001547 // Nuke the old bindings stemming from R.
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001548 RegionBindings B = GetRegionBindings(store);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001549
Mike Stump1eb44332009-09-09 15:08:12 +00001550 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001551 SubRegions(getRegionStoreSubRegionMap(store));
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001552
Mike Stump1eb44332009-09-09 15:08:12 +00001553 // B and DVM are updated after the call to RemoveSubRegionBindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001554 RemoveSubRegionBindings(B, R, *SubRegions.get());
Mike Stump1eb44332009-09-09 15:08:12 +00001555
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001556 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1557 // results in a zero-copy algorithm.
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001558 return Add(B, R, BindingKey::Direct, V).getRoot();
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001559}
1560
1561//===----------------------------------------------------------------------===//
1562// "Raw" retrievals and bindings.
1563//===----------------------------------------------------------------------===//
1564
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001565
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001566RegionBindings RegionStoreManager::Add(RegionBindings B, BindingKey K, SVal V) {
Jordy Rosed5addb42010-08-16 20:53:01 +00001567 if (!K.isValid())
Jordy Rosee7011172010-08-16 01:15:17 +00001568 return B;
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001569 return RBFactory.Add(B, K, V);
1570}
1571
1572RegionBindings RegionStoreManager::Add(RegionBindings B, const MemRegion *R,
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001573 BindingKey::Kind k, SVal V) {
1574 return Add(B, BindingKey::Make(R, k), V);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001575}
1576
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001577const SVal *RegionStoreManager::Lookup(RegionBindings B, BindingKey K) {
Jordy Rosed5addb42010-08-16 20:53:01 +00001578 if (!K.isValid())
Jordy Rosee7011172010-08-16 01:15:17 +00001579 return NULL;
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001580 return B.lookup(K);
1581}
1582
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001583const SVal *RegionStoreManager::Lookup(RegionBindings B,
1584 const MemRegion *R,
1585 BindingKey::Kind k) {
1586 return Lookup(B, BindingKey::Make(R, k));
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001587}
1588
1589RegionBindings RegionStoreManager::Remove(RegionBindings B, BindingKey K) {
Jordy Rosed5addb42010-08-16 20:53:01 +00001590 if (!K.isValid())
Jordy Rosee7011172010-08-16 01:15:17 +00001591 return B;
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001592 return RBFactory.Remove(B, K);
1593}
1594
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001595RegionBindings RegionStoreManager::Remove(RegionBindings B, const MemRegion *R,
1596 BindingKey::Kind k){
1597 return Remove(B, BindingKey::Make(R, k));
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001598}
1599
Ted Kremenek9af46f52009-06-16 22:36:44 +00001600//===----------------------------------------------------------------------===//
1601// State pruning.
1602//===----------------------------------------------------------------------===//
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001603
Ted Kremenek5499b842010-03-10 16:32:56 +00001604namespace {
1605class RemoveDeadBindingsWorker :
1606 public ClusterAnalysis<RemoveDeadBindingsWorker> {
1607 llvm::SmallVector<const SymbolicRegion*, 12> Postponed;
1608 SymbolReaper &SymReaper;
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001609 const StackFrameContext *CurrentLCtx;
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001610
Ted Kremenek5499b842010-03-10 16:32:56 +00001611public:
1612 RemoveDeadBindingsWorker(RegionStoreManager &rm, GRStateManager &stateMgr,
1613 RegionBindings b, SymbolReaper &symReaper,
Jordy Rose7dadf792010-07-01 20:09:55 +00001614 const StackFrameContext *LCtx)
Ted Kremenek5499b842010-03-10 16:32:56 +00001615 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b),
Jordy Rose7dadf792010-07-01 20:09:55 +00001616 SymReaper(symReaper), CurrentLCtx(LCtx) {}
Ted Kremenek5499b842010-03-10 16:32:56 +00001617
1618 // Called by ClusterAnalysis.
1619 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C);
1620 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
Ted Kremenek5499b842010-03-10 16:32:56 +00001621
Ted Kremenek75a2d942010-04-01 00:15:55 +00001622 void VisitBindingKey(BindingKey K);
Ted Kremenek5499b842010-03-10 16:32:56 +00001623 bool UpdatePostponed();
1624 void VisitBinding(SVal V);
1625};
1626}
1627
1628void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
1629 RegionCluster &C) {
1630
1631 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
Jordy Rose7dadf792010-07-01 20:09:55 +00001632 if (SymReaper.isLive(VR))
Ted Kremenek5499b842010-03-10 16:32:56 +00001633 AddToWorkList(baseR, C);
1634
1635 return;
1636 }
1637
1638 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
1639 if (SymReaper.isLive(SR->getSymbol()))
1640 AddToWorkList(SR, C);
1641 else
1642 Postponed.push_back(SR);
1643
1644 return;
1645 }
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001646
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001647 if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
1648 AddToWorkList(baseR, C);
1649 return;
1650 }
1651
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001652 // CXXThisRegion in the current or parent location context is live.
1653 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001654 const StackArgumentsSpaceRegion *StackReg =
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001655 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
1656 const StackFrameContext *RegCtx = StackReg->getStackFrame();
1657 if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))
1658 AddToWorkList(TR, C);
1659 }
Ted Kremenek5499b842010-03-10 16:32:56 +00001660}
1661
1662void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
1663 BindingKey *I, BindingKey *E) {
Ted Kremenek75a2d942010-04-01 00:15:55 +00001664 for ( ; I != E; ++I)
1665 VisitBindingKey(*I);
Ted Kremenek5499b842010-03-10 16:32:56 +00001666}
1667
1668void RemoveDeadBindingsWorker::VisitBinding(SVal V) {
1669 // Is it a LazyCompoundVal? All referenced regions are live as well.
1670 if (const nonloc::LazyCompoundVal *LCS =
1671 dyn_cast<nonloc::LazyCompoundVal>(&V)) {
1672
1673 const MemRegion *LazyR = LCS->getRegion();
1674 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
1675 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
Ted Kremenek0ea0e8b2010-07-06 23:53:29 +00001676 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
1677 if (baseR && baseR->isSubRegionOf(LazyR))
Ted Kremenek5499b842010-03-10 16:32:56 +00001678 VisitBinding(RI.getData());
1679 }
1680 return;
1681 }
1682
1683 // If V is a region, then add it to the worklist.
1684 if (const MemRegion *R = V.getAsRegion())
1685 AddToWorkList(R);
1686
1687 // Update the set of live symbols.
1688 for (SVal::symbol_iterator SI=V.symbol_begin(), SE=V.symbol_end();
1689 SI!=SE;++SI)
1690 SymReaper.markLive(*SI);
1691}
1692
Ted Kremenek75a2d942010-04-01 00:15:55 +00001693void RemoveDeadBindingsWorker::VisitBindingKey(BindingKey K) {
1694 const MemRegion *R = K.getRegion();
1695
Ted Kremenek5499b842010-03-10 16:32:56 +00001696 // Mark this region "live" by adding it to the worklist. This will cause
1697 // use to visit all regions in the cluster (if we haven't visited them
1698 // already).
Ted Kremenek75a2d942010-04-01 00:15:55 +00001699 if (AddToWorkList(R)) {
1700 // Mark the symbol for any live SymbolicRegion as "live". This means we
1701 // should continue to track that symbol.
1702 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
1703 SymReaper.markLive(SymR->getSymbol());
Ted Kremenek5499b842010-03-10 16:32:56 +00001704
Ted Kremenek75a2d942010-04-01 00:15:55 +00001705 // For BlockDataRegions, enqueue the VarRegions for variables marked
1706 // with __block (passed-by-reference).
1707 // via BlockDeclRefExprs.
1708 if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
1709 for (BlockDataRegion::referenced_vars_iterator
1710 RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
1711 RI != RE; ++RI) {
1712 if ((*RI)->getDecl()->getAttr<BlocksAttr>())
1713 AddToWorkList(*RI);
1714 }
Ted Kremenek5499b842010-03-10 16:32:56 +00001715
Ted Kremenek75a2d942010-04-01 00:15:55 +00001716 // No possible data bindings on a BlockDataRegion.
1717 return;
Ted Kremenek5499b842010-03-10 16:32:56 +00001718 }
Ted Kremenek5499b842010-03-10 16:32:56 +00001719 }
1720
Ted Kremenek75a2d942010-04-01 00:15:55 +00001721 // Visit the data binding for K.
1722 if (const SVal *V = RM.Lookup(B, K))
Ted Kremenek5499b842010-03-10 16:32:56 +00001723 VisitBinding(*V);
1724}
1725
1726bool RemoveDeadBindingsWorker::UpdatePostponed() {
1727 // See if any postponed SymbolicRegions are actually live now, after
1728 // having done a scan.
1729 bool changed = false;
1730
1731 for (llvm::SmallVectorImpl<const SymbolicRegion*>::iterator
1732 I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) {
1733 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) {
1734 if (SymReaper.isLive(SR->getSymbol())) {
1735 changed |= AddToWorkList(SR);
1736 *I = NULL;
1737 }
1738 }
1739 }
1740
1741 return changed;
1742}
1743
Zhongxing Xu5e4cb342010-08-15 12:45:09 +00001744Store RegionStoreManager::RemoveDeadBindings(Store store,
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +00001745 const StackFrameContext *LCtx,
Zhongxing Xu72119c42010-02-05 05:34:29 +00001746 SymbolReaper& SymReaper,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001747 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +00001748{
Zhongxing Xu5e4cb342010-08-15 12:45:09 +00001749 RegionBindings B = GetRegionBindings(store);
Jordy Rose7dadf792010-07-01 20:09:55 +00001750 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
Ted Kremenek5499b842010-03-10 16:32:56 +00001751 W.GenerateClusters();
Mike Stump1eb44332009-09-09 15:08:12 +00001752
Ted Kremenek5499b842010-03-10 16:32:56 +00001753 // Enqueue the region roots onto the worklist.
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001754 for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(),
Ted Kremenek5499b842010-03-10 16:32:56 +00001755 E=RegionRoots.end(); I!=E; ++I)
1756 W.AddToWorkList(*I);
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001757
Ted Kremenek5499b842010-03-10 16:32:56 +00001758 do W.RunWorkList(); while (W.UpdatePostponed());
Ted Kremeneke5ea0ca2010-03-10 07:20:03 +00001759
Ted Kremenek9af46f52009-06-16 22:36:44 +00001760 // We have now scanned the store, marking reachable regions and symbols
1761 // as live. We now remove all the regions that are dead from the store
Mike Stump1eb44332009-09-09 15:08:12 +00001762 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenek451ac092009-08-06 04:50:20 +00001763 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek5499b842010-03-10 16:32:56 +00001764 const BindingKey &K = I.getKey();
1765
Ted Kremenekb7118f72010-03-10 16:38:41 +00001766 // If the cluster has been visited, we know the region has been marked.
Ted Kremenek5499b842010-03-10 16:32:56 +00001767 if (W.isVisited(K.getRegion()))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001768 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001769
Ted Kremenek5499b842010-03-10 16:32:56 +00001770 // Remove the dead entry.
1771 B = Remove(B, K);
Mike Stump1eb44332009-09-09 15:08:12 +00001772
Ted Kremenek5499b842010-03-10 16:32:56 +00001773 // Mark all non-live symbols that this binding references as dead.
1774 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion()))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001775 SymReaper.maybeDead(SymR->getSymbol());
Mike Stump1eb44332009-09-09 15:08:12 +00001776
Ted Kremeneke393f4a2010-02-03 03:06:46 +00001777 SVal X = I.getData();
Ted Kremenek093569c2009-08-02 05:00:15 +00001778 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1779 for (; SI != SE; ++SI)
1780 SymReaper.maybeDead(*SI);
1781 }
Zhongxing Xu5e4cb342010-08-15 12:45:09 +00001782
1783 return B.getRoot();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001784}
1785
Ted Kremenek5499b842010-03-10 16:32:56 +00001786
Jordy Roseff59efd2010-08-03 20:44:35 +00001787Store RegionStoreManager::EnterStackFrame(const GRState *state,
1788 const StackFrameContext *frame) {
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001789 FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001790 FunctionDecl::param_const_iterator PI = FD->param_begin();
Zhongxing Xub4a9c612010-02-05 05:06:13 +00001791 Store store = state->getStore();
Zhongxing Xuc5063572010-03-16 13:14:16 +00001792
1793 if (CallExpr const *CE = dyn_cast<CallExpr>(frame->getCallSite())) {
1794 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1795
1796 // Copy the arg expression value to the arg variables.
1797 for (; AI != AE; ++AI, ++PI) {
1798 SVal ArgVal = state->getSVal(*AI);
1799 store = Bind(store, ValMgr.makeLoc(MRMgr.getVarRegion(*PI,frame)),ArgVal);
1800 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001801 } else if (const CXXConstructExpr *CE =
Zhongxing Xuc5063572010-03-16 13:14:16 +00001802 dyn_cast<CXXConstructExpr>(frame->getCallSite())) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +00001803 CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(),
Zhongxing Xuc5063572010-03-16 13:14:16 +00001804 AE = CE->arg_end();
1805
1806 // Copy the arg expression value to the arg variables.
1807 for (; AI != AE; ++AI, ++PI) {
1808 SVal ArgVal = state->getSVal(*AI);
1809 store = Bind(store, ValMgr.makeLoc(MRMgr.getVarRegion(*PI,frame)),ArgVal);
1810 }
1811 } else
Jordy Roseff59efd2010-08-03 20:44:35 +00001812 llvm_unreachable("Unhandled call expression.");
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001813
Jordy Roseff59efd2010-08-03 20:44:35 +00001814 return store;
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001815}
1816
Ted Kremenek9af46f52009-06-16 22:36:44 +00001817//===----------------------------------------------------------------------===//
1818// Utility methods.
1819//===----------------------------------------------------------------------===//
1820
Ted Kremenek53ba0b62009-06-24 23:06:47 +00001821void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001822 const char* nl, const char *sep) {
Ted Kremenek451ac092009-08-06 04:50:20 +00001823 RegionBindings B = GetRegionBindings(store);
Ted Kremenekab22ee92009-10-20 01:20:57 +00001824 OS << "Store (direct and default bindings):" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +00001825
Ted Kremenek451ac092009-08-06 04:50:20 +00001826 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
Mike Stump1eb44332009-09-09 15:08:12 +00001827 OS << ' ' << I.getKey() << " : " << I.getData() << nl;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001828}