blob: 9b5b44be64273489a32439a06e36268262280559 [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//===----------------------------------------------------------------------===//
17#include "clang/Analysis/PathSensitive/MemRegion.h"
Zhongxing Xu0b143312009-08-21 13:25:15 +000018#include "clang/Analysis/PathSensitive/AnalysisContext.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000019#include "clang/Analysis/PathSensitive/GRState.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000020#include "clang/Analysis/PathSensitive/GRStateTrait.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000021#include "clang/Analysis/Analyses/LiveVariables.h"
Ted Kremenekd4e5a602009-08-06 21:43:54 +000022#include "clang/Analysis/Support/Optional.h"
Zhongxing Xu41fd0182009-05-06 11:51:48 +000023#include "clang/Basic/TargetInfo.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000024
25#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000026#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000027#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000028
29using namespace clang;
30
Ted Kremeneka5e81f12009-08-06 01:20:57 +000031#define USE_EXPLICIT_COMPOUND 0
Ted Kremenek356e9d62009-07-22 04:35:42 +000032
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000033//===----------------------------------------------------------------------===//
34// Representation of value bindings.
35//===----------------------------------------------------------------------===//
36
Zhongxing Xu13d50172009-10-11 08:08:02 +000037namespace {
38class BindingVal {
39public:
40 enum BindingKind { Direct, Default };
41private:
42 SVal Value;
43 BindingKind Kind;
44
45public:
46 BindingVal(SVal V, BindingKind K) : Value(V), Kind(K) {}
47
48 bool isDefault() const { return Kind == Default; }
49
50 const SVal *getValue() const { return &Value; }
51
52 const SVal *getDirectValue() const { return isDefault() ? 0 : &Value; }
53
54 const SVal *getDefaultValue() const { return isDefault() ? &Value : 0; }
55
56 void Profile(llvm::FoldingSetNodeID& ID) const {
57 Value.Profile(ID);
58 ID.AddInteger(Kind);
59 }
60
61 inline bool operator==(const BindingVal& R) const {
62 return Value == R.Value && Kind == R.Kind;
63 }
64
65 inline bool operator!=(const BindingVal& R) const {
66 return !(*this == R);
67 }
68};
69}
70
71namespace llvm {
72static inline
73llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingVal V) {
74 if (V.isDefault())
75 os << "(default) ";
76 else
77 os << "(direct) ";
78 os << *V.getValue();
79 return os;
80}
81} // end llvm namespace
82
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000083//===----------------------------------------------------------------------===//
84// Representation of binding keys.
85//===----------------------------------------------------------------------===//
86
87namespace {
88 class BindingKey : public std::pair<const MemRegion*, uint64_t> {
89public:
Ted Kremenekc50e6df2010-01-11 02:33:26 +000090 explicit BindingKey(const MemRegion *r, uint64_t offset)
91 : std::pair<const MemRegion*,uint64_t>(r, offset) { assert(r); }
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +000092
93 const MemRegion *getRegion() const { return first; }
94 uint64_t getOffset() const { return second; }
95
96 void Profile(llvm::FoldingSetNodeID& ID) const {
97 ID.AddPointer(getRegion());
98 ID.AddInteger(getOffset());
99 }
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000100
101 static BindingKey Make(const MemRegion *R);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000102};
103} // end anonymous namespace
104
105namespace llvm {
106 static inline
107 llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingKey K) {
108 os << '(' << K.getRegion() << ',' << K.getOffset() << ')';
109 return os;
110 }
111} // end llvm namespace
112
113//===----------------------------------------------------------------------===//
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000114// Actual Store type.
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000115//===----------------------------------------------------------------------===//
116
117typedef llvm::ImmutableMap<BindingKey, BindingVal> RegionBindings;
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000118
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000119//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +0000120// Fine-grained control of RegionStoreManager.
121//===----------------------------------------------------------------------===//
122
123namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000124struct minimal_features_tag {};
125struct maximal_features_tag {};
Mike Stump1eb44332009-09-09 15:08:12 +0000126
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000127class RegionStoreFeatures {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000128 bool SupportsFields;
129 bool SupportsRemaining;
Mike Stump1eb44332009-09-09 15:08:12 +0000130
Ted Kremenek9af46f52009-06-16 22:36:44 +0000131public:
132 RegionStoreFeatures(minimal_features_tag) :
133 SupportsFields(false), SupportsRemaining(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000134
Ted Kremenek9af46f52009-06-16 22:36:44 +0000135 RegionStoreFeatures(maximal_features_tag) :
136 SupportsFields(true), SupportsRemaining(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000137
Ted Kremenek9af46f52009-06-16 22:36:44 +0000138 void enableFields(bool t) { SupportsFields = t; }
Mike Stump1eb44332009-09-09 15:08:12 +0000139
Ted Kremenek9af46f52009-06-16 22:36:44 +0000140 bool supportsFields() const { return SupportsFields; }
141 bool supportsRemaining() const { return SupportsRemaining; }
142};
143}
144
145//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000146// Region "Extents"
147//===----------------------------------------------------------------------===//
148//
149// MemRegions represent chunks of memory with a size (their "extent"). This
150// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000151//
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000152namespace { class RegionExtents {}; }
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000153static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000154namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000155 template<> struct GRStateTrait<RegionExtents>
156 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
157 static void* GDMIndex() { return &RegionExtentsIndex; }
158 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000159}
160
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000161//===----------------------------------------------------------------------===//
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000162// Utility functions.
163//===----------------------------------------------------------------------===//
164
165static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) {
166 if (ty->isAnyPointerType())
167 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000168
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000169 return ty->isIntegerType() && ty->isScalarType() &&
170 Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy);
171}
172
173//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000174// Main RegionStore logic.
175//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000176
Zhongxing Xu17892752008-10-08 02:50:44 +0000177namespace {
Mike Stump1eb44332009-09-09 15:08:12 +0000178
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000179class RegionStoreSubRegionMap : public SubRegionMap {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000180 typedef llvm::ImmutableSet<const MemRegion*> SetTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000181 typedef llvm::DenseMap<const MemRegion*, SetTy> Map;
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000182 SetTy::Factory F;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000183 Map M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000184public:
Ted Kremenekd8c01922009-08-05 19:09:24 +0000185 bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000186 Map::iterator I = M.find(Parent);
Ted Kremenekd8c01922009-08-05 19:09:24 +0000187
188 if (I == M.end()) {
Ted Kremenek4ed45982009-08-05 05:31:02 +0000189 M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion)));
Ted Kremenekd8c01922009-08-05 19:09:24 +0000190 return true;
191 }
192
193 I->second = F.Add(I->second, SubRegion);
194 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000195 }
Mike Stump1eb44332009-09-09 15:08:12 +0000196
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000197 void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000198
Ted Kremenek59e8f112009-03-03 01:35:36 +0000199 ~RegionStoreSubRegionMap() {}
Mike Stump1eb44332009-09-09 15:08:12 +0000200
Ted Kremenek5dc27462009-03-03 02:51:43 +0000201 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +0000202 Map::const_iterator I = M.find(Parent);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000203
204 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000205 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000206
Ted Kremenek59e8f112009-03-03 01:35:36 +0000207 llvm::ImmutableSet<const MemRegion*> S = I->second;
208 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
209 SI != SE; ++SI) {
210 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000211 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000212 }
Mike Stump1eb44332009-09-09 15:08:12 +0000213
Ted Kremenek5dc27462009-03-03 02:51:43 +0000214 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000215 }
Mike Stump1eb44332009-09-09 15:08:12 +0000216
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000217 typedef SetTy::iterator iterator;
218
219 std::pair<iterator, iterator> begin_end(const MemRegion *R) {
220 Map::iterator I = M.find(R);
221 SetTy S = I == M.end() ? F.GetEmptySet() : I->second;
222 return std::make_pair(S.begin(), S.end());
223 }
Mike Stump1eb44332009-09-09 15:08:12 +0000224};
Ted Kremenek59e8f112009-03-03 01:35:36 +0000225
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000226class RegionStoreManager : public StoreManager {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000227 const RegionStoreFeatures Features;
Ted Kremenek451ac092009-08-06 04:50:20 +0000228 RegionBindings::Factory RBFactory;
Ted Kremenek9e17cc62009-09-29 06:35:00 +0000229
230 typedef llvm::DenseMap<const GRState *, RegionStoreSubRegionMap*> SMCache;
231 SMCache SC;
232
Zhongxing Xu17892752008-10-08 02:50:44 +0000233public:
Mike Stump1eb44332009-09-09 15:08:12 +0000234 RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
Ted Kremenekf7a0cf42009-07-29 21:43:22 +0000235 : StoreManager(mgr),
Ted Kremenek9af46f52009-06-16 22:36:44 +0000236 Features(f),
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000237 RBFactory(mgr.getAllocator()) {}
Zhongxing Xu17892752008-10-08 02:50:44 +0000238
Ted Kremenek9e17cc62009-09-29 06:35:00 +0000239 virtual ~RegionStoreManager() {
240 for (SMCache::iterator I = SC.begin(), E = SC.end(); I != E; ++I)
241 delete (*I).second;
242 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000243
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000244 SubRegionMap *getSubRegionMap(const GRState *state);
Mike Stump1eb44332009-09-09 15:08:12 +0000245
Zhongxing Xu13d50172009-10-11 08:08:02 +0000246 RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
Mike Stump1eb44332009-09-09 15:08:12 +0000247
Zhongxing Xu13d50172009-10-11 08:08:02 +0000248 Optional<SVal> getBinding(RegionBindings B, const MemRegion *R);
249 Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000250 /// getDefaultBinding - Returns an SVal* representing an optional default
251 /// binding associated with a region and its subregions.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000252 Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
Ted Kremenek027e2662009-11-19 20:20:24 +0000253
254 /// setImplicitDefaultValue - Set the default binding for the provided
255 /// MemRegion to the value implicitly defined for compound literals when
256 /// the value is not specified.
257 const GRState *setImplicitDefaultValue(const GRState *state,
258 const MemRegion *R,
259 QualType T);
Mike Stump1eb44332009-09-09 15:08:12 +0000260
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000261 /// getLValueString - Returns an SVal representing the lvalue of a
262 /// StringLiteral. Within RegionStore a StringLiteral has an
263 /// associated StringRegion, and the lvalue of a StringLiteral is
264 /// the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000265 SVal getLValueString(const StringLiteral* S);
Zhongxing Xu143bf822008-10-25 14:18:57 +0000266
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000267 /// getLValueCompoundLiteral - Returns an SVal representing the
268 /// lvalue of a compound literal. Within RegionStore a compound
269 /// literal has an associated region, and the lvalue of the
270 /// compound literal is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000271 SVal getLValueCompoundLiteral(const CompoundLiteralExpr*);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000272
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000273 /// getLValueVar - Returns an SVal that represents the lvalue of a
274 /// variable. Within RegionStore a variable has an associated
275 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000276 SVal getLValueVar(const VarDecl *VD, const LocationContext *LC);
Mike Stump1eb44332009-09-09 15:08:12 +0000277
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000278 SVal getLValueIvar(const ObjCIvarDecl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000279
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000280 SVal getLValueField(const FieldDecl* D, SVal Base);
Mike Stump1eb44332009-09-09 15:08:12 +0000281
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000282 SVal getLValueFieldOrIvar(const Decl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000283
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000284 SVal getLValueElement(QualType elementType, SVal Offset, SVal Base);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000285
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000286
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000287 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
288 /// type. 'Array' represents the lvalue of the array being decayed
289 /// to a pointer, and the returned SVal represents the decayed
290 /// version of that lvalue (i.e., a pointer to the first element of
291 /// the array). This is called by GRExprEngine when evaluating
292 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000293 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000294
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000295 SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L,
Ted Kremenek5c734622009-06-26 00:41:43 +0000296 NonLoc R, QualType resultTy);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000297
Mike Stump1eb44332009-09-09 15:08:12 +0000298 Store getInitialStore(const LocationContext *InitLoc) {
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000299 return RBFactory.GetEmptyMap().getRoot();
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000300 }
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000301
Ted Kremenek67f28532009-06-17 22:02:04 +0000302 //===-------------------------------------------------------------------===//
303 // Binding values to regions.
304 //===-------------------------------------------------------------------===//
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000305
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000306 const GRState *InvalidateRegion(const GRState *state, const MemRegion *R,
Ted Kremenek473e1672009-10-16 00:30:49 +0000307 const Expr *E, unsigned Count,
Ted Kremenek81a95832009-12-03 03:27:11 +0000308 InvalidatedSymbols *IS) {
309 return RegionStoreManager::InvalidateRegions(state, &R, &R+1, E, Count, IS);
310 }
311
312 const GRState *InvalidateRegions(const GRState *state,
313 const MemRegion * const *Begin,
314 const MemRegion * const *End,
315 const Expr *E, unsigned Count,
316 InvalidatedSymbols *IS);
Mike Stump1eb44332009-09-09 15:08:12 +0000317
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000318private:
Zhongxing Xu13d50172009-10-11 08:08:02 +0000319 void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000320 RegionStoreSubRegionMap &M);
Mike Stump1eb44332009-09-09 15:08:12 +0000321
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000322 RegionBindings Add(RegionBindings B, BindingKey K, BindingVal V);
323 RegionBindings Add(RegionBindings B, const MemRegion *R, BindingVal V);
324
325 const BindingVal *Lookup(RegionBindings B, BindingKey K);
326 const BindingVal *Lookup(RegionBindings B, const MemRegion *R);
327
328 RegionBindings Remove(RegionBindings B, BindingKey K);
329 RegionBindings Remove(RegionBindings B, const MemRegion *R);
330 Store Remove(Store store, BindingKey K);
331
Mike Stump1eb44332009-09-09 15:08:12 +0000332public:
Ted Kremenek67f28532009-06-17 22:02:04 +0000333 const GRState *Bind(const GRState *state, Loc LV, SVal V);
334
335 const GRState *BindCompoundLiteral(const GRState *state,
Ted Kremenek67d12872009-12-07 22:05:27 +0000336 const CompoundLiteralExpr* CL,
337 const LocationContext *LC,
338 SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000339
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000340 const GRState *BindDecl(const GRState *ST, const VarRegion *VR,
341 SVal InitVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000342
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000343 const GRState *BindDeclWithNoInit(const GRState *state,
344 const VarRegion *) {
Ted Kremenek67f28532009-06-17 22:02:04 +0000345 return state;
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000346 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000347
Ted Kremenek67f28532009-06-17 22:02:04 +0000348 /// BindStruct - Bind a compound value to a structure.
349 const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000350
Ted Kremenek67f28532009-06-17 22:02:04 +0000351 const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000352
353 /// KillStruct - Set the entire struct to unknown.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000354 Store KillStruct(Store store, const TypedRegion* R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000355
Ted Kremenek67f28532009-06-17 22:02:04 +0000356 Store Remove(Store store, Loc LV);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000357
Ted Kremenek67f28532009-06-17 22:02:04 +0000358
359 //===------------------------------------------------------------------===//
360 // Loading values from regions.
361 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000362
Ted Kremenek67f28532009-06-17 22:02:04 +0000363 /// The high level logic for this method is this:
364 /// Retrieve (L)
365 /// if L has binding
366 /// return L's binding
367 /// else if L is in killset
368 /// return unknown
369 /// else
370 /// if L is on stack or heap
371 /// return undefined
372 /// else
373 /// return symbolic
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000374 SValuator::CastResult Retrieve(const GRState *state, Loc L,
375 QualType T = QualType());
Zhongxing Xu490b0f02009-06-25 04:50:44 +0000376
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000377 SVal RetrieveElement(const GRState *state, const ElementRegion *R);
Zhongxing Xuc00346f2009-06-25 05:29:39 +0000378
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000379 SVal RetrieveField(const GRState *state, const FieldRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000380
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000381 SVal RetrieveObjCIvar(const GRState *state, const ObjCIvarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000382
Ted Kremenek9031dd72009-07-21 00:12:07 +0000383 SVal RetrieveVar(const GRState *state, const VarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000384
Ted Kremenek25c54572009-07-20 22:58:02 +0000385 SVal RetrieveLazySymbol(const GRState *state, const TypedRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000386
Ted Kremenek566a6fa2009-08-06 22:33:36 +0000387 SVal RetrieveFieldOrElementCommon(const GRState *state, const TypedRegion *R,
388 QualType Ty, const MemRegion *superR);
Mike Stump1eb44332009-09-09 15:08:12 +0000389
Ted Kremenek67f28532009-06-17 22:02:04 +0000390 /// Retrieve the values in a struct and return a CompoundVal, used when doing
Mike Stump1eb44332009-09-09 15:08:12 +0000391 /// struct copy:
392 /// struct s x, y;
Ted Kremenek67f28532009-06-17 22:02:04 +0000393 /// x = y;
394 /// y's value is retrieved by this method.
395 SVal RetrieveStruct(const GRState *St, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000396
Ted Kremenek67f28532009-06-17 22:02:04 +0000397 SVal RetrieveArray(const GRState *St, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000398
Zhongxing Xu944ebc62009-12-21 06:52:24 +0000399 /// Get the state and region whose binding this region R corresponds to.
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000400 std::pair<const GRState*, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +0000401 GetLazyBinding(RegionBindings B, const MemRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000402
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000403 const GRState* CopyLazyBindings(nonloc::LazyCompoundVal V,
404 const GRState *state,
405 const TypedRegion *R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000406
Ted Kremenek0954cde2009-09-24 04:11:44 +0000407 const ElementRegion *GetElementZeroRegion(const SymbolicRegion *SR,
408 QualType T);
409
Ted Kremenek67f28532009-06-17 22:02:04 +0000410 //===------------------------------------------------------------------===//
411 // State pruning.
412 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000413
Ted Kremenek67f28532009-06-17 22:02:04 +0000414 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
415 /// It returns a new Store with these values removed.
Ted Kremenek2f26bc32009-08-02 04:45:08 +0000416 void RemoveDeadBindings(GRState &state, Stmt* Loc, SymbolReaper& SymReaper,
Ted Kremenek67f28532009-06-17 22:02:04 +0000417 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
418
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +0000419 const GRState *EnterStackFrame(const GRState *state,
420 const StackFrameContext *frame);
421
Ted Kremenek67f28532009-06-17 22:02:04 +0000422 //===------------------------------------------------------------------===//
423 // Region "extents".
424 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000425
Ted Kremenek67f28532009-06-17 22:02:04 +0000426 const GRState *setExtent(const GRState *state, const MemRegion* R, SVal Extent);
Zhongxing Xue884ff82009-11-12 02:48:32 +0000427 DefinedOrUnknownSVal getSizeInElements(const GRState *state,
428 const MemRegion* R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000429
430 //===------------------------------------------------------------------===//
Ted Kremenek67f28532009-06-17 22:02:04 +0000431 // Utility methods.
432 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000433
Ted Kremenek451ac092009-08-06 04:50:20 +0000434 static inline RegionBindings GetRegionBindings(Store store) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000435 return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000436 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000437
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000438 void print(Store store, llvm::raw_ostream& Out, const char* nl,
439 const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000440
441 void iterBindings(Store store, BindingsHandler& f) {
442 // FIXME: Implement.
443 }
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000444
Ted Kremenek67f28532009-06-17 22:02:04 +0000445 // FIXME: Remove.
446 BasicValueFactory& getBasicVals() {
447 return StateMgr.getBasicVals();
448 }
Mike Stump1eb44332009-09-09 15:08:12 +0000449
Ted Kremenek67f28532009-06-17 22:02:04 +0000450 // FIXME: Remove.
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000451 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xu17892752008-10-08 02:50:44 +0000452};
453
454} // end anonymous namespace
455
Ted Kremenek9af46f52009-06-16 22:36:44 +0000456//===----------------------------------------------------------------------===//
457// RegionStore creation.
458//===----------------------------------------------------------------------===//
459
460StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
461 RegionStoreFeatures F = maximal_features_tag();
462 return new RegionStoreManager(StMgr, F);
463}
464
465StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
466 RegionStoreFeatures F = minimal_features_tag();
467 F.enableFields(true);
468 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000469}
470
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000471void
472RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL,
Mike Stump1eb44332009-09-09 15:08:12 +0000473 const SubRegion *R) {
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000474 const MemRegion *superR = R->getSuperRegion();
475 if (add(superR, R))
476 if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
Mike Stump1eb44332009-09-09 15:08:12 +0000477 WL.push_back(sr);
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000478}
479
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000480RegionStoreSubRegionMap*
Zhongxing Xu13d50172009-10-11 08:08:02 +0000481RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
482 RegionBindings B = GetRegionBindings(store);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000483 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
Mike Stump1eb44332009-09-09 15:08:12 +0000484
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000485 llvm::SmallVector<const SubRegion*, 10> WL;
486
Ted Kremenek451ac092009-08-06 04:50:20 +0000487 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000488 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000489 M->process(WL, R);
Mike Stump1eb44332009-09-09 15:08:12 +0000490
Mike Stump1eb44332009-09-09 15:08:12 +0000491 // We also need to record in the subregion map "intermediate" regions that
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000492 // don't have direct bindings but are super regions of those that do.
493 while (!WL.empty()) {
494 const SubRegion *R = WL.back();
495 WL.pop_back();
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000496 M->process(WL, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000497 }
498
Ted Kremenek14453bf2009-03-03 19:02:42 +0000499 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000500}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000501
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000502SubRegionMap *RegionStoreManager::getSubRegionMap(const GRState *state) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000503 return getRegionStoreSubRegionMap(state->getStore());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000504}
505
Ted Kremenek9af46f52009-06-16 22:36:44 +0000506//===----------------------------------------------------------------------===//
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000507// Binding invalidation.
508//===----------------------------------------------------------------------===//
509
Zhongxing Xu13d50172009-10-11 08:08:02 +0000510void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
511 const MemRegion *R,
512 RegionStoreSubRegionMap &M) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000513 RegionStoreSubRegionMap::iterator I, E;
514
515 for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I)
Zhongxing Xu13d50172009-10-11 08:08:02 +0000516 RemoveSubRegionBindings(B, *I, M);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000517
518 B = Remove(B, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000519}
520
Ted Kremenek81a95832009-12-03 03:27:11 +0000521const GRState *RegionStoreManager::InvalidateRegions(const GRState *state,
522 const MemRegion * const *I,
523 const MemRegion * const *E,
524 const Expr *Ex,
525 unsigned Count,
526 InvalidatedSymbols *IS) {
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000527 ASTContext& Ctx = StateMgr.getContext();
Mike Stump1eb44332009-09-09 15:08:12 +0000528
Ted Kremenek87806792009-09-27 20:45:21 +0000529 // Get the mapping of regions -> subregions.
530 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +0000531 SubRegions(getRegionStoreSubRegionMap(state->getStore()));
Ted Kremenek87806792009-09-27 20:45:21 +0000532
533 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +0000534
Ted Kremenek87806792009-09-27 20:45:21 +0000535 llvm::DenseMap<const MemRegion *, unsigned> Visited;
536 llvm::SmallVector<const MemRegion *, 10> WorkList;
Ted Kremenek81a95832009-12-03 03:27:11 +0000537
538 for ( ; I != E; ++I) {
539 // Strip away casts.
540 WorkList.push_back((*I)->StripCasts());
541 }
Ted Kremenek87806792009-09-27 20:45:21 +0000542
543 while (!WorkList.empty()) {
Ted Kremenek81a95832009-12-03 03:27:11 +0000544 const MemRegion *R = WorkList.back();
Ted Kremenek87806792009-09-27 20:45:21 +0000545 WorkList.pop_back();
546
547 // Have we visited this region before?
548 unsigned &visited = Visited[R];
549 if (visited)
550 continue;
551 visited = 1;
Mike Stump1eb44332009-09-09 15:08:12 +0000552
Ted Kremenek87806792009-09-27 20:45:21 +0000553 // Add subregions to work list.
554 RegionStoreSubRegionMap::iterator I, E;
555 for (llvm::tie(I, E) = SubRegions->begin_end(R); I!=E; ++I)
556 WorkList.push_back(*I);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000557
558 // Get the old binding. Is it a region? If so, add it to the worklist.
559 if (Optional<SVal> V = getDirectBinding(B, R)) {
560 if (const MemRegion *RV = V->getAsRegion())
561 WorkList.push_back(RV);
Ted Kremenek473e1672009-10-16 00:30:49 +0000562
563 // A symbol? Mark it touched by the invalidation.
564 if (IS) {
565 if (SymbolRef Sym = V->getAsSymbol())
566 IS->insert(Sym);
567 }
Zhongxing Xu13d50172009-10-11 08:08:02 +0000568 }
569
Ted Kremenek473e1672009-10-16 00:30:49 +0000570 // Symbolic region? Mark that symbol touched by the invalidation.
571 if (IS) {
572 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
573 IS->insert(SR->getSymbol());
574 }
Ted Kremenek2ffbfd92009-12-03 08:25:47 +0000575
576 // BlockDataRegion? If so, invalidate captured variables that are passed
577 // by reference.
578 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
579 for (BlockDataRegion::referenced_vars_iterator
580 I = BR->referenced_vars_begin(), E = BR->referenced_vars_end() ;
581 I != E; ++I) {
582 const VarRegion *VR = *I;
583 if (VR->getDecl()->getAttr<BlocksAttr>())
584 WorkList.push_back(VR);
585 }
586 continue;
587 }
Ted Kremenek473e1672009-10-16 00:30:49 +0000588
589 // Handle the region itself.
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000590 if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R)) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000591 // Invalidate the region by setting its default value to
592 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek87806792009-09-27 20:45:21 +0000593 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000594 Count);
595 B = Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000596 continue;
597 }
Mike Stump1eb44332009-09-09 15:08:12 +0000598
Ted Kremenek87806792009-09-27 20:45:21 +0000599 if (!R->isBoundable())
600 continue;
601
602 const TypedRegion *TR = cast<TypedRegion>(R);
603 QualType T = TR->getValueType(Ctx);
604
605 if (const RecordType *RT = T->getAsStructureType()) {
Ted Kremenek87806792009-09-27 20:45:21 +0000606 const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx);
607
Zhongxing Xu13d50172009-10-11 08:08:02 +0000608 // No record definition. There is nothing we can do.
Ted Kremenek87806792009-09-27 20:45:21 +0000609 if (!RD)
610 continue;
611
Zhongxing Xu13d50172009-10-11 08:08:02 +0000612 // Invalidate the region by setting its default value to
613 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek87806792009-09-27 20:45:21 +0000614 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
615 Count);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000616 B = Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000617 continue;
618 }
619
620 if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
621 // Set the default value of the array to conjured symbol.
622 DefinedOrUnknownSVal V =
623 ValMgr.getConjuredSymbolVal(R, Ex, AT->getElementType(), Count);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000624 B = Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000625 continue;
626 }
Ted Kremeneka5971b32009-09-29 03:34:03 +0000627
628 if ((isa<FieldRegion>(R)||isa<ElementRegion>(R)||isa<ObjCIvarRegion>(R))
629 && Visited[cast<SubRegion>(R)->getSuperRegion()]) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000630 // For fields and elements whose super region has also been invalidated,
631 // only remove the old binding. The super region will get set with a
632 // default value from which we can lazily derive a new symbolic value.
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000633 B = Remove(B, R);
Ted Kremeneka5971b32009-09-29 03:34:03 +0000634 continue;
635 }
Ted Kremenek87806792009-09-27 20:45:21 +0000636
Ted Kremenek389c44c2009-09-29 03:12:50 +0000637 // Invalidate the binding.
Ted Kremenek87806792009-09-27 20:45:21 +0000638 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, T, Count);
639 assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000640 B = Add(B, R, BindingVal(V, BindingVal::Direct));
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000641 }
642
Ted Kremenek87806792009-09-27 20:45:21 +0000643 // Create a new state with the updated bindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000644 return state->makeWithStore(B.getRoot());
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000645}
646
647//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +0000648// getLValueXXX methods.
649//===----------------------------------------------------------------------===//
650
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000651/// getLValueString - Returns an SVal representing the lvalue of a
652/// StringLiteral. Within RegionStore a StringLiteral has an
653/// associated StringRegion, and the lvalue of a StringLiteral is the
654/// lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000655SVal RegionStoreManager::getLValueString(const StringLiteral* S) {
Zhongxing Xu143bf822008-10-25 14:18:57 +0000656 return loc::MemRegionVal(MRMgr.getStringRegion(S));
657}
658
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000659/// getLValueVar - Returns an SVal that represents the lvalue of a
660/// variable. Within RegionStore a variable has an associated
661/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000662SVal RegionStoreManager::getLValueVar(const VarDecl *VD,
Ted Kremenekd17da2b2009-08-21 22:28:32 +0000663 const LocationContext *LC) {
664 return loc::MemRegionVal(MRMgr.getVarRegion(VD, LC));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000665}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000666
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000667SVal RegionStoreManager::getLValueIvar(const ObjCIvarDecl* D, SVal Base) {
668 return getLValueFieldOrIvar(D, Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000669}
670
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000671SVal RegionStoreManager::getLValueField(const FieldDecl* D, SVal Base) {
672 return getLValueFieldOrIvar(D, Base);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000673}
674
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000675SVal RegionStoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000676 if (Base.isUnknownOrUndef())
677 return Base;
678
679 Loc BaseL = cast<Loc>(Base);
680 const MemRegion* BaseR = 0;
681
682 switch (BaseL.getSubKind()) {
683 case loc::MemRegionKind:
684 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
685 break;
686
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000687 case loc::GotoLabelKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000688 // These are anormal cases. Flag an undefined value.
689 return UndefinedVal();
690
691 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000692 // While these seem funny, this can happen through casts.
693 // FIXME: What we should return is the field offset. For example,
694 // add the field offset to the integer value. That way funny things
695 // like this work properly: &(((struct foo *) 0xa)->f)
696 return Base;
697
698 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000699 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000700 return Base;
701 }
Mike Stump1eb44332009-09-09 15:08:12 +0000702
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000703 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
704 // of FieldDecl.
705 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
706 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000707
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000708 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000709}
710
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000711SVal RegionStoreManager::getLValueElement(QualType elementType, SVal Offset,
712 SVal Base) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000713
Ted Kremenekde7ec632009-03-09 22:44:49 +0000714 // If the base is an unknown or undefined value, just return it back.
715 // FIXME: For absolute pointer addresses, we just return that value back as
716 // well, although in reality we should return the offset added to that
717 // value.
718 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000719 return Base;
720
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000721 // Only handle integer offsets... for now.
722 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000723 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000724
Zhongxing Xuce760782009-05-09 13:20:07 +0000725 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000726
727 // Pointer of any type can be cast and used as array base.
728 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
Mike Stump1eb44332009-09-09 15:08:12 +0000729
Ted Kremenek46537392009-07-16 01:33:37 +0000730 // Convert the offset to the appropriate size and signedness.
731 Offset = ValMgr.convertToArrayIndex(Offset);
Mike Stump1eb44332009-09-09 15:08:12 +0000732
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000733 if (!ElemR) {
734 //
735 // If the base region is not an ElementRegion, create one.
736 // This can happen in the following example:
737 //
738 // char *p = __builtin_alloc(10);
739 // p[1] = 8;
740 //
Zhongxing Xuce760782009-05-09 13:20:07 +0000741 // Observe that 'p' binds to an AllocaRegion.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000742 //
Ted Kremenekf936f452009-05-04 06:18:28 +0000743 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000744 BaseRegion, getContext()));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000745 }
Mike Stump1eb44332009-09-09 15:08:12 +0000746
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000747 SVal BaseIdx = ElemR->getIndex();
Mike Stump1eb44332009-09-09 15:08:12 +0000748
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000749 if (!isa<nonloc::ConcreteInt>(BaseIdx))
750 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000751
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000752 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
753 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
754 assert(BaseIdxI.isSigned());
Mike Stump1eb44332009-09-09 15:08:12 +0000755
Ted Kremenek46537392009-07-16 01:33:37 +0000756 // Compute the new index.
757 SVal NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Mike Stump1eb44332009-09-09 15:08:12 +0000758
Ted Kremenek46537392009-07-16 01:33:37 +0000759 // Construct the new ElementRegion.
760 const MemRegion *ArrayR = ElemR->getSuperRegion();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000761 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
Mike Stump1eb44332009-09-09 15:08:12 +0000762 getContext()));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000763}
764
Ted Kremenek9af46f52009-06-16 22:36:44 +0000765//===----------------------------------------------------------------------===//
766// Extents for regions.
767//===----------------------------------------------------------------------===//
768
Zhongxing Xue884ff82009-11-12 02:48:32 +0000769DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state,
770 const MemRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +0000771
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000772 switch (R->getKind()) {
Ted Kremenekde0d2632010-01-05 02:18:06 +0000773 case MemRegion::CXXThisRegionKind:
774 assert(0 && "Cannot get size of 'this' region");
Ted Kremenek67d12872009-12-07 22:05:27 +0000775 case MemRegion::GenericMemSpaceRegionKind:
776 case MemRegion::StackLocalsSpaceRegionKind:
777 case MemRegion::StackArgumentsSpaceRegionKind:
778 case MemRegion::HeapSpaceRegionKind:
779 case MemRegion::GlobalsSpaceRegionKind:
Ted Kremenek2b87ae42009-12-11 06:43:27 +0000780 case MemRegion::UnknownSpaceRegionKind:
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000781 assert(0 && "Cannot index into a MemSpace");
Mike Stump1eb44332009-09-09 15:08:12 +0000782 return UnknownVal();
783
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000784 case MemRegion::FunctionTextRegionKind:
785 case MemRegion::BlockTextRegionKind:
Ted Kremenek0a8112a2009-11-25 23:53:07 +0000786 case MemRegion::BlockDataRegionKind:
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000787 // Technically this can happen if people do funny things with casts.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000788 return UnknownVal();
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000789
790 // Not yet handled.
791 case MemRegion::AllocaRegionKind:
792 case MemRegion::CompoundLiteralRegionKind:
793 case MemRegion::ElementRegionKind:
794 case MemRegion::FieldRegionKind:
795 case MemRegion::ObjCIvarRegionKind:
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000796 case MemRegion::SymbolicRegionKind:
Zhongxing Xubb141212009-12-16 11:27:52 +0000797 case MemRegion::CXXObjectRegionKind:
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000798 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000799
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000800 case MemRegion::StringRegionKind: {
801 const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral();
Mike Stump1eb44332009-09-09 15:08:12 +0000802 // We intentionally made the size value signed because it participates in
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000803 // operations with signed indices.
804 return ValMgr.makeIntVal(Str->getByteLength()+1, false);
Ted Kremenek14553ab2009-01-30 00:08:43 +0000805 }
Mike Stump1eb44332009-09-09 15:08:12 +0000806
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000807 case MemRegion::VarRegionKind: {
808 const VarRegion* VR = cast<VarRegion>(R);
809 // Get the type of the variable.
810 QualType T = VR->getDesugaredValueType(getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000811
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000812 // FIXME: Handle variable-length arrays.
813 if (isa<VariableArrayType>(T))
814 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000815
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000816 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
817 // return the size as signed integer.
818 return ValMgr.makeIntVal(CAT->getSize(), false);
819 }
Ted Kremenekdf74e252009-08-02 05:15:23 +0000820
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000821 // Clients can use ordinary variables as if they were arrays. These
822 // essentially are arrays of size 1.
823 return ValMgr.makeIntVal(1, false);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000824 }
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000825 }
Mike Stump1eb44332009-09-09 15:08:12 +0000826
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000827 assert(0 && "Unreachable");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000828 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000829}
830
Ted Kremenek67f28532009-06-17 22:02:04 +0000831const GRState *RegionStoreManager::setExtent(const GRState *state,
832 const MemRegion *region,
833 SVal extent) {
834 return state->set<RegionExtents>(region, extent);
Ted Kremenek9af46f52009-06-16 22:36:44 +0000835}
836
837//===----------------------------------------------------------------------===//
838// Location and region casting.
839//===----------------------------------------------------------------------===//
840
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000841/// ArrayToPointer - Emulates the "decay" of an array to a pointer
842/// type. 'Array' represents the lvalue of the array being decayed
843/// to a pointer, and the returned SVal represents the decayed
844/// version of that lvalue (i.e., a pointer to the first element of
845/// the array). This is called by GRExprEngine when evaluating casts
846/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000847SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000848 if (!isa<loc::MemRegionVal>(Array))
849 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000850
Ted Kremenekabb042f2008-12-13 19:24:37 +0000851 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
852 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000853
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000854 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000855 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000856
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000857 // Strip off typedefs from the ArrayRegion's ValueType.
John McCallbf1cc052009-09-29 23:03:30 +0000858 QualType T = ArrayR->getValueType(getContext()).getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000859 ArrayType *AT = cast<ArrayType>(T);
860 T = AT->getElementType();
Mike Stump1eb44332009-09-09 15:08:12 +0000861
Ted Kremenek75185b52009-07-16 00:00:11 +0000862 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
Ted Kremenekb48ad642009-12-04 00:26:31 +0000863 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR,
864 getContext()));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000865}
866
Ted Kremenek9af46f52009-06-16 22:36:44 +0000867//===----------------------------------------------------------------------===//
868// Pointer arithmetic.
869//===----------------------------------------------------------------------===//
870
Mike Stump1eb44332009-09-09 15:08:12 +0000871SVal RegionStoreManager::EvalBinOp(const GRState *state,
Ted Kremenek5c734622009-06-26 00:41:43 +0000872 BinaryOperator::Opcode Op, Loc L, NonLoc R,
873 QualType resultTy) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000874 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000875 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000876 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000877
Zhongxing Xua1718c72009-04-03 07:33:13 +0000878 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000879 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000880
Ted Kremenek3bccf082009-07-11 00:58:27 +0000881 switch (MR->getKind()) {
882 case MemRegion::SymbolicRegionKind: {
883 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000884 SymbolRef Sym = SR->getSymbol();
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000885 QualType T = Sym->getType(getContext());
886 QualType EleTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000887
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000888 if (const PointerType *PT = T->getAs<PointerType>())
889 EleTy = PT->getPointeeType();
890 else
John McCall183700f2009-09-21 23:43:11 +0000891 EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000892
Ted Kremenek3bccf082009-07-11 00:58:27 +0000893 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
894 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000895 break;
Zhongxing Xu005f07b2009-06-19 04:51:14 +0000896 }
Ted Kremenek3bccf082009-07-11 00:58:27 +0000897 case MemRegion::AllocaRegionKind: {
Ted Kremenek3bccf082009-07-11 00:58:27 +0000898 const AllocaRegion *AR = cast<AllocaRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000899 QualType T = getContext().CharTy; // Create an ElementRegion of bytes.
Ted Kremenek6217b802009-07-29 21:53:49 +0000900 QualType EleTy = T->getAs<PointerType>()->getPointeeType();
Ted Kremenek3bccf082009-07-11 00:58:27 +0000901 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
902 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000903 break;
Ted Kremenek3bccf082009-07-11 00:58:27 +0000904 }
Zhongxing Xua1718c72009-04-03 07:33:13 +0000905
Ted Kremenek3bccf082009-07-11 00:58:27 +0000906 case MemRegion::ElementRegionKind: {
907 ER = cast<ElementRegion>(MR);
908 break;
909 }
Mike Stump1eb44332009-09-09 15:08:12 +0000910
Ted Kremenek3bccf082009-07-11 00:58:27 +0000911 // Not yet handled.
912 case MemRegion::VarRegionKind:
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000913 case MemRegion::StringRegionKind: {
914
915 }
916 // Fall-through.
Ted Kremenek3bccf082009-07-11 00:58:27 +0000917 case MemRegion::CompoundLiteralRegionKind:
918 case MemRegion::FieldRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000919 case MemRegion::ObjCIvarRegionKind:
Zhongxing Xubb141212009-12-16 11:27:52 +0000920 case MemRegion::CXXObjectRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000921 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000922
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000923 case MemRegion::FunctionTextRegionKind:
924 case MemRegion::BlockTextRegionKind:
Ted Kremenek0a8112a2009-11-25 23:53:07 +0000925 case MemRegion::BlockDataRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000926 // Technically this can happen if people do funny things with casts.
927 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000928
Ted Kremenekde0d2632010-01-05 02:18:06 +0000929 case MemRegion::CXXThisRegionKind:
930 assert(0 &&
931 "Cannot perform pointer arithmetic on implicit argument 'this'");
Ted Kremenek67d12872009-12-07 22:05:27 +0000932 case MemRegion::GenericMemSpaceRegionKind:
933 case MemRegion::StackLocalsSpaceRegionKind:
934 case MemRegion::StackArgumentsSpaceRegionKind:
935 case MemRegion::HeapSpaceRegionKind:
936 case MemRegion::GlobalsSpaceRegionKind:
Ted Kremenek2b87ae42009-12-11 06:43:27 +0000937 case MemRegion::UnknownSpaceRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000938 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
939 return UnknownVal();
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000940 }
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000941
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000942 SVal Idx = ER->getIndex();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000943 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000944
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000945 // For now, only support:
946 // (a) concrete integer indices that can easily be resolved
947 // (b) 0 + symbolic index
948 if (Base) {
949 if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) {
950 // FIXME: Should use SValuator here.
951 SVal NewIdx =
952 Base->evalBinOp(ValMgr, Op,
Ted Kremenek46537392009-07-16 01:33:37 +0000953 cast<nonloc::ConcreteInt>(ValMgr.convertToArrayIndex(*Offset)));
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000954 const MemRegion* NewER =
955 MRMgr.getElementRegion(ER->getElementType(), NewIdx,
956 ER->getSuperRegion(), getContext());
957 return ValMgr.makeLoc(NewER);
958 }
959 if (0 == Base->getValue()) {
960 const MemRegion* NewER =
961 MRMgr.getElementRegion(ER->getElementType(), R,
962 ER->getSuperRegion(), getContext());
963 return ValMgr.makeLoc(NewER);
964 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000965 }
Mike Stump1eb44332009-09-09 15:08:12 +0000966
Ted Kremenek5dc27462009-03-03 02:51:43 +0000967 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000968}
969
Ted Kremenek9af46f52009-06-16 22:36:44 +0000970//===----------------------------------------------------------------------===//
971// Loading values from regions.
972//===----------------------------------------------------------------------===//
973
Zhongxing Xu13d50172009-10-11 08:08:02 +0000974Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
975 const MemRegion *R) {
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000976 if (const BindingVal *BV = Lookup(B, R))
Zhongxing Xu13d50172009-10-11 08:08:02 +0000977 return Optional<SVal>::create(BV->getDirectValue());
978
979 return Optional<SVal>();
980}
981
982Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000983 const MemRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +0000984
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000985 if (R->isBoundable())
986 if (const TypedRegion *TR = dyn_cast<TypedRegion>(R))
987 if (TR->getValueType(getContext())->isUnionType())
988 return UnknownVal();
989
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000990 if (const BindingVal *V = Lookup(B, R))
Zhongxing Xu13d50172009-10-11 08:08:02 +0000991 return Optional<SVal>::create(V->getDefaultValue());
992
993 return Optional<SVal>();
994}
995
996Optional<SVal> RegionStoreManager::getBinding(RegionBindings B,
997 const MemRegion *R) {
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +0000998 if (const BindingVal *BV = Lookup(B, R))
Zhongxing Xu13d50172009-10-11 08:08:02 +0000999 return Optional<SVal>::create(BV->getValue());
1000
1001 return Optional<SVal>();
Ted Kremenekd4e5a602009-08-06 21:43:54 +00001002}
1003
Ted Kremeneka6275a52009-07-15 02:31:43 +00001004static bool IsReinterpreted(QualType RTy, QualType UsedTy, ASTContext &Ctx) {
1005 RTy = Ctx.getCanonicalType(RTy);
1006 UsedTy = Ctx.getCanonicalType(UsedTy);
Mike Stump1eb44332009-09-09 15:08:12 +00001007
Ted Kremeneka6275a52009-07-15 02:31:43 +00001008 if (RTy == UsedTy)
1009 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001010
1011
Ted Kremenek25c54572009-07-20 22:58:02 +00001012 // Recursively check the types. We basically want to see if a pointer value
Mike Stump1eb44332009-09-09 15:08:12 +00001013 // is ever reinterpreted as a non-pointer, e.g. void** and intptr_t*
Ted Kremenek25c54572009-07-20 22:58:02 +00001014 // represents a reinterpretation.
1015 if (Loc::IsLocType(RTy) && Loc::IsLocType(UsedTy)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001016 const PointerType *PRTy = RTy->getAs<PointerType>();
Ted Kremenek6217b802009-07-29 21:53:49 +00001017 const PointerType *PUsedTy = UsedTy->getAs<PointerType>();
Ted Kremenek25c54572009-07-20 22:58:02 +00001018
1019 return PUsedTy && PRTy &&
1020 IsReinterpreted(PRTy->getPointeeType(),
Mike Stump1eb44332009-09-09 15:08:12 +00001021 PUsedTy->getPointeeType(), Ctx);
Ted Kremenek25c54572009-07-20 22:58:02 +00001022 }
1023
1024 return true;
Ted Kremeneka6275a52009-07-15 02:31:43 +00001025}
1026
Ted Kremenek0954cde2009-09-24 04:11:44 +00001027const ElementRegion *
1028RegionStoreManager::GetElementZeroRegion(const SymbolicRegion *SR, QualType T) {
1029 ASTContext &Ctx = getContext();
1030 SVal idx = ValMgr.makeZeroArrayIndex();
1031 assert(!T.isNull());
1032 return MRMgr.getElementRegion(T, idx, SR, Ctx);
1033}
1034
1035
1036
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001037SValuator::CastResult
1038RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
Ted Kremenek67f28532009-06-17 22:02:04 +00001039
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001040 assert(!isa<UnknownVal>(L) && "location unknown");
1041 assert(!isa<UndefinedVal>(L) && "location undefined");
Ted Kremenek28172a22009-12-15 23:23:27 +00001042
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001043 // FIXME: Is this even possible? Shouldn't this be treated as a null
1044 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001045 if (isa<loc::ConcreteInt>(L))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001046 return SValuator::CastResult(state, UndefinedVal());
Ted Kremenek28172a22009-12-15 23:23:27 +00001047
Ted Kremenek67f28532009-06-17 22:02:04 +00001048 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +00001049
Zhongxing Xu91844122009-05-20 09:18:48 +00001050 // FIXME: return symbolic value for these cases.
Zhongxing Xua1718c72009-04-03 07:33:13 +00001051 // Example:
1052 // void f(int* p) { int x = *p; }
Zhongxing Xu91844122009-05-20 09:18:48 +00001053 // char* p = alloca();
1054 // read(p);
1055 // c = *p;
Ted Kremenek60fbe8f2009-07-14 20:48:22 +00001056 if (isa<AllocaRegion>(MR))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001057 return SValuator::CastResult(state, UnknownVal());
Mike Stump1eb44332009-09-09 15:08:12 +00001058
Ted Kremenek0954cde2009-09-24 04:11:44 +00001059 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1060 MR = GetElementZeroRegion(SR, T);
Mike Stump1eb44332009-09-09 15:08:12 +00001061
Ted Kremenek968f0a62009-08-03 21:41:46 +00001062 if (isa<CodeTextRegion>(MR))
1063 return SValuator::CastResult(state, UnknownVal());
Mike Stump1eb44332009-09-09 15:08:12 +00001064
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001065 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1066 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Ted Kremenek67f28532009-06-17 22:02:04 +00001067 const TypedRegion *R = cast<TypedRegion>(MR);
Ted Kremeneka6275a52009-07-15 02:31:43 +00001068 QualType RTy = R->getValueType(getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001069
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001070 // FIXME: We should eventually handle funny addressing. e.g.:
1071 //
1072 // int x = ...;
1073 // int *p = &x;
1074 // char *q = (char*) p;
1075 // char c = *q; // returns the first byte of 'x'.
1076 //
1077 // Such funny addressing will occur due to layering of regions.
1078
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001079#if 0
Ted Kremeneka6275a52009-07-15 02:31:43 +00001080 ASTContext &Ctx = getContext();
1081 if (!T.isNull() && IsReinterpreted(RTy, T, Ctx)) {
Ted Kremenek46537392009-07-16 01:33:37 +00001082 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
1083 R = MRMgr.getElementRegion(T, ZeroIdx, R, Ctx);
Ted Kremeneka6275a52009-07-15 02:31:43 +00001084 RTy = T;
Ted Kremenek41fb0df2009-07-15 04:23:32 +00001085 assert(Ctx.getCanonicalType(RTy) ==
1086 Ctx.getCanonicalType(R->getValueType(Ctx)));
Mike Stump1eb44332009-09-09 15:08:12 +00001087 }
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001088#endif
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001089
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001090 if (RTy->isStructureType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001091 return SValuator::CastResult(state, RetrieveStruct(state, R));
Mike Stump1eb44332009-09-09 15:08:12 +00001092
Ted Kremenekd4e5a602009-08-06 21:43:54 +00001093 // FIXME: Handle unions.
1094 if (RTy->isUnionType())
1095 return SValuator::CastResult(state, UnknownVal());
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001096
1097 if (RTy->isArrayType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001098 return SValuator::CastResult(state, RetrieveArray(state, R));
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001099
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001100 // FIXME: handle Vector types.
1101 if (RTy->isVectorType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001102 return SValuator::CastResult(state, UnknownVal());
Zhongxing Xu99c20302009-06-28 14:16:39 +00001103
1104 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
Zhongxing Xu652be342009-11-16 04:49:44 +00001105 return SValuator::CastResult(state,
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001106 CastRetrievedVal(RetrieveField(state, FR), FR,
1107 T, false));
Zhongxing Xu99c20302009-06-28 14:16:39 +00001108
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001109 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1110 // FIXME: Here we actually perform an implicit conversion from the loaded
1111 // value to the element type. Eventually we want to compose these values
1112 // more intelligently. For example, an 'element' can encompass multiple
1113 // bound regions (e.g., several bound bytes), or could be a subset of
1114 // a larger value.
Zhongxing Xu652be342009-11-16 04:49:44 +00001115 return SValuator::CastResult(state,
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001116 CastRetrievedVal(RetrieveElement(state, ER),
1117 ER, T, false));
1118 }
Mike Stump1eb44332009-09-09 15:08:12 +00001119
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001120 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1121 // FIXME: Here we actually perform an implicit conversion from the loaded
1122 // value to the ivar type. What we should model is stores to ivars
1123 // that blow past the extent of the ivar. If the address of the ivar is
1124 // reinterpretted, it is possible we stored a different value that could
1125 // fit within the ivar. Either we need to cast these when storing them
1126 // or reinterpret them lazily (as we do here).
Zhongxing Xu652be342009-11-16 04:49:44 +00001127 return SValuator::CastResult(state,
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001128 CastRetrievedVal(RetrieveObjCIvar(state, IVR),
1129 IVR, T, false));
1130 }
Mike Stump1eb44332009-09-09 15:08:12 +00001131
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001132 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1133 // FIXME: Here we actually perform an implicit conversion from the loaded
1134 // value to the variable type. What we should model is stores to variables
1135 // that blow past the extent of the variable. If the address of the
1136 // variable is reinterpretted, it is possible we stored a different value
1137 // that could fit within the variable. Either we need to cast these when
1138 // storing them or reinterpret them lazily (as we do here).
Zhongxing Xu652be342009-11-16 04:49:44 +00001139 return SValuator::CastResult(state,
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001140 CastRetrievedVal(RetrieveVar(state, VR), VR, T,
1141 false));
1142 }
Ted Kremenek25c54572009-07-20 22:58:02 +00001143
Ted Kremenek451ac092009-08-06 04:50:20 +00001144 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001145 const BindingVal *V = Lookup(B, R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001146
1147 // Check if the region has a binding.
1148 if (V)
Zhongxing Xu13d50172009-10-11 08:08:02 +00001149 if (SVal const *SV = V->getValue())
1150 return SValuator::CastResult(state, *SV);
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001151
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001152 // The location does not have a bound value. This means that it has
1153 // the value it had upon its creation and/or entry to the analyzed
1154 // function/method. These are either symbolic values or 'undefined'.
Ted Kremenekde0d2632010-01-05 02:18:06 +00001155 if (R->hasStackNonParametersStorage()) {
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001156 // All stack variables are considered to have undefined values
1157 // upon creation. All heap allocated blocks are considered to
1158 // have undefined values as well unless they are explicitly bound
1159 // to specific values.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001160 return SValuator::CastResult(state, UndefinedVal());
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001161 }
1162
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001163 // All other values are symbolic.
Ted Kremenek28172a22009-12-15 23:23:27 +00001164 return SValuator::CastResult(state, ValMgr.getRegionValueSymbolVal(R, RTy));
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001165}
Mike Stump1eb44332009-09-09 15:08:12 +00001166
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001167std::pair<const GRState*, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +00001168RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001169 if (Optional<SVal> OV = getDirectBinding(B, R))
1170 if (const nonloc::LazyCompoundVal *V =
1171 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
1172 return std::make_pair(V->getState(), V->getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001173
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001174 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1175 const std::pair<const GRState *, const MemRegion *> &X =
1176 GetLazyBinding(B, ER->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001177
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001178 if (X.first)
1179 return std::make_pair(X.first,
1180 MRMgr.getElementRegionWithSuper(ER, X.second));
Mike Stump1eb44332009-09-09 15:08:12 +00001181 }
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001182 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1183 const std::pair<const GRState *, const MemRegion *> &X =
1184 GetLazyBinding(B, FR->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001185
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001186 if (X.first)
1187 return std::make_pair(X.first,
1188 MRMgr.getFieldRegionWithSuper(FR, X.second));
1189 }
1190
1191 return std::make_pair((const GRState*) 0, (const MemRegion *) 0);
1192}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001193
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001194SVal RegionStoreManager::RetrieveElement(const GRState* state,
1195 const ElementRegion* R) {
1196 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001197 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001198 if (Optional<SVal> V = getDirectBinding(B, R))
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001199 return *V;
1200
Ted Kremenek921109a2009-07-01 23:19:52 +00001201 const MemRegion* superR = R->getSuperRegion();
1202
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001203 // Check if the region is an element region of a string literal.
Ted Kremenek921109a2009-07-01 23:19:52 +00001204 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001205 // FIXME: Handle loads from strings where the literal is treated as
1206 // an integer, e.g., *((unsigned int*)"hello")
1207 ASTContext &Ctx = getContext();
Douglas Gregor89c49f02009-11-09 22:08:55 +00001208 QualType T = Ctx.getAsArrayType(StrR->getValueType(Ctx))->getElementType();
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001209 if (T != Ctx.getCanonicalType(R->getElementType()))
1210 return UnknownVal();
1211
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001212 const StringLiteral *Str = StrR->getStringLiteral();
1213 SVal Idx = R->getIndex();
1214 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1215 int64_t i = CI->getValue().getSExtValue();
Mike Stump1eb44332009-09-09 15:08:12 +00001216 int64_t byteLength = Str->getByteLength();
Ted Kremenek0667db32009-09-05 17:59:01 +00001217 if (i > byteLength) {
1218 // Buffer overflow checking in GRExprEngine should handle this case,
1219 // but we shouldn't rely on it to not overflow here if that checking
1220 // is disabled.
1221 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001222 }
Ted Kremenek0667db32009-09-05 17:59:01 +00001223 char c = (i == byteLength) ? '\0' : Str->getStrData()[i];
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001224 return ValMgr.makeIntVal(c, T);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001225 }
1226 }
Mike Stump1eb44332009-09-09 15:08:12 +00001227
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001228 // Check if the immediate super region has a direct binding.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001229 if (Optional<SVal> V = getDirectBinding(B, superR)) {
Ted Kremeneka6275a52009-07-15 02:31:43 +00001230 if (SymbolRef parentSym = V->getAsSymbol())
1231 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenek356e9d62009-07-22 04:35:42 +00001232
1233 if (V->isUnknownOrUndef())
1234 return *V;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001235
1236 // Handle LazyCompoundVals for the immediate super region. Other cases
1237 // are handled in 'RetrieveFieldOrElementCommon'.
Mike Stump1eb44332009-09-09 15:08:12 +00001238 if (const nonloc::LazyCompoundVal *LCV =
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001239 dyn_cast<nonloc::LazyCompoundVal>(V)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001240
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001241 R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion());
1242 return RetrieveElement(LCV->getState(), R);
1243 }
Mike Stump1eb44332009-09-09 15:08:12 +00001244
Ted Kremeneka6275a52009-07-15 02:31:43 +00001245 // Other cases: give up.
Zhongxing Xu8834af32009-07-03 06:11:41 +00001246 return UnknownVal();
Zhongxing Xu7abe0192009-06-30 12:32:59 +00001247 }
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001248
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001249 return RetrieveFieldOrElementCommon(state, R, R->getElementType(), superR);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001250}
1251
Mike Stump1eb44332009-09-09 15:08:12 +00001252SVal RegionStoreManager::RetrieveField(const GRState* state,
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001253 const FieldRegion* R) {
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001254
1255 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001256 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001257 if (Optional<SVal> V = getDirectBinding(B, R))
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001258 return *V;
1259
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001260 QualType Ty = R->getValueType(getContext());
1261 return RetrieveFieldOrElementCommon(state, R, Ty, R->getSuperRegion());
1262}
Mike Stump1eb44332009-09-09 15:08:12 +00001263
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001264SVal RegionStoreManager::RetrieveFieldOrElementCommon(const GRState *state,
1265 const TypedRegion *R,
1266 QualType Ty,
1267 const MemRegion *superR) {
1268
Mike Stump1eb44332009-09-09 15:08:12 +00001269 // At this point we have already checked in either RetrieveElement or
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001270 // RetrieveField if 'R' has a direct binding.
Mike Stump1eb44332009-09-09 15:08:12 +00001271
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001272 RegionBindings B = GetRegionBindings(state->getStore());
Mike Stump1eb44332009-09-09 15:08:12 +00001273
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001274 while (superR) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001275 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001276 if (SymbolRef parentSym = D->getAsSymbol())
1277 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001278
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001279 if (D->isZeroConstant())
1280 return ValMgr.makeZeroVal(Ty);
Mike Stump1eb44332009-09-09 15:08:12 +00001281
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001282 if (D->isUnknown())
1283 return *D;
Mike Stump1eb44332009-09-09 15:08:12 +00001284
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001285 assert(0 && "Unknown default value");
1286 }
Mike Stump1eb44332009-09-09 15:08:12 +00001287
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001288 // If our super region is a field or element itself, walk up the region
1289 // hierarchy to see if there is a default value installed in an ancestor.
1290 if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) {
1291 superR = cast<SubRegion>(superR)->getSuperRegion();
1292 continue;
1293 }
Mike Stump1eb44332009-09-09 15:08:12 +00001294
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001295 break;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001296 }
Mike Stump1eb44332009-09-09 15:08:12 +00001297
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001298 // Lazy binding?
1299 const GRState *lazyBindingState = NULL;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001300 const MemRegion *lazyBindingRegion = NULL;
1301 llvm::tie(lazyBindingState, lazyBindingRegion) = GetLazyBinding(B, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001302
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001303 if (lazyBindingState) {
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001304 assert(lazyBindingRegion && "Lazy-binding region not set");
Mike Stump1eb44332009-09-09 15:08:12 +00001305
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001306 if (isa<ElementRegion>(R))
1307 return RetrieveElement(lazyBindingState,
1308 cast<ElementRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001309
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001310 return RetrieveField(lazyBindingState,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001311 cast<FieldRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001312 }
1313
Ted Kremenekde0d2632010-01-05 02:18:06 +00001314 if (R->hasStackNonParametersStorage()) {
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001315 if (isa<ElementRegion>(R)) {
1316 // Currently we don't reason specially about Clang-style vectors. Check
1317 // if superR is a vector and if so return Unknown.
1318 if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) {
1319 if (typedSuperR->getValueType(getContext())->isVectorType())
1320 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001321 }
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001322 }
Mike Stump1eb44332009-09-09 15:08:12 +00001323
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001324 return UndefinedVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001325 }
Mike Stump1eb44332009-09-09 15:08:12 +00001326
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001327 // All other values are symbolic.
Ted Kremenek28172a22009-12-15 23:23:27 +00001328 return ValMgr.getRegionValueSymbolVal(R, Ty);
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001329}
Mike Stump1eb44332009-09-09 15:08:12 +00001330
1331SVal RegionStoreManager::RetrieveObjCIvar(const GRState* state,
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001332 const ObjCIvarRegion* R) {
1333
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001334 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001335 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001336
Zhongxing Xu13d50172009-10-11 08:08:02 +00001337 if (Optional<SVal> V = getDirectBinding(B, R))
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001338 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001339
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001340 const MemRegion *superR = R->getSuperRegion();
1341
Ted Kremenekab22ee92009-10-20 01:20:57 +00001342 // Check if the super region has a default binding.
1343 if (Optional<SVal> V = getDefaultBinding(B, superR)) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001344 if (SymbolRef parentSym = V->getAsSymbol())
1345 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001346
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001347 // Other cases: give up.
1348 return UnknownVal();
1349 }
Mike Stump1eb44332009-09-09 15:08:12 +00001350
Ted Kremenek25c54572009-07-20 22:58:02 +00001351 return RetrieveLazySymbol(state, R);
1352}
1353
Ted Kremenek9031dd72009-07-21 00:12:07 +00001354SVal RegionStoreManager::RetrieveVar(const GRState *state,
1355 const VarRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001356
Ted Kremenek9031dd72009-07-21 00:12:07 +00001357 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001358 RegionBindings B = GetRegionBindings(state->getStore());
Mike Stump1eb44332009-09-09 15:08:12 +00001359
Zhongxing Xu13d50172009-10-11 08:08:02 +00001360 if (Optional<SVal> V = getDirectBinding(B, R))
Ted Kremenek9031dd72009-07-21 00:12:07 +00001361 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001362
Ted Kremenek9031dd72009-07-21 00:12:07 +00001363 // Lazily derive a value for the VarRegion.
1364 const VarDecl *VD = R->getDecl();
Mike Stump1eb44332009-09-09 15:08:12 +00001365
Ted Kremenek2b87ae42009-12-11 06:43:27 +00001366 if (R->hasGlobalsOrParametersStorage() ||
1367 isa<UnknownSpaceRegion>(R->getMemorySpace()))
Ted Kremenek28172a22009-12-15 23:23:27 +00001368 return ValMgr.getRegionValueSymbolVal(R, VD->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00001369
Ted Kremenek9031dd72009-07-21 00:12:07 +00001370 return UndefinedVal();
1371}
1372
Mike Stump1eb44332009-09-09 15:08:12 +00001373SVal RegionStoreManager::RetrieveLazySymbol(const GRState *state,
Ted Kremenek25c54572009-07-20 22:58:02 +00001374 const TypedRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001375
Ted Kremenek25c54572009-07-20 22:58:02 +00001376 QualType valTy = R->getValueType(getContext());
Ted Kremenek356e9d62009-07-22 04:35:42 +00001377
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001378 // All other values are symbolic.
Ted Kremenek28172a22009-12-15 23:23:27 +00001379 return ValMgr.getRegionValueSymbolVal(R, valTy);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001380}
1381
Mike Stump1eb44332009-09-09 15:08:12 +00001382SVal RegionStoreManager::RetrieveStruct(const GRState *state,
1383 const TypedRegion* R) {
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001384 QualType T = R->getValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001385 assert(T->isStructureType());
1386
Zhongxing Xub7507d12009-06-11 07:27:30 +00001387 const RecordType* RT = T->getAsStructureType();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001388 RecordDecl* RD = RT->getDecl();
1389 assert(RD->isDefinition());
Mike Stump1aeb2472009-08-06 12:56:50 +00001390 (void)RD;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001391#if USE_EXPLICIT_COMPOUND
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001392 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
1393
Ted Kremenek67f28532009-06-17 22:02:04 +00001394 // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a
1395 // reverse iterator, we should implement one.
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001396 std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end());
Douglas Gregor44b43212008-12-11 16:49:14 +00001397
Douglas Gregore267ff32008-12-11 20:41:00 +00001398 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
1399 FieldEnd = Fields.rend();
1400 Field != FieldEnd; ++Field) {
1401 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001402 QualType FTy = (*Field)->getType();
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001403 SVal FieldValue = Retrieve(state, loc::MemRegionVal(FR), FTy).getSVal();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001404 StructVal = getBasicVals().consVals(FieldValue, StructVal);
1405 }
1406
Zhongxing Xud91ee272009-06-23 09:02:15 +00001407 return ValMgr.makeCompoundVal(T, StructVal);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001408#else
1409 return ValMgr.makeLazyCompoundVal(state, R);
1410#endif
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001411}
1412
Ted Kremenek67f28532009-06-17 22:02:04 +00001413SVal RegionStoreManager::RetrieveArray(const GRState *state,
1414 const TypedRegion * R) {
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001415#if USE_EXPLICIT_COMPOUND
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001416 QualType T = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001417 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1418
1419 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
Ted Kremenek46537392009-07-16 01:33:37 +00001420 uint64_t size = CAT->getSize().getZExtValue();
1421 for (uint64_t i = 0; i < size; ++i) {
1422 SVal Idx = ValMgr.makeArrayIndex(i);
Zhongxing Xu143b2fc2009-06-16 09:55:50 +00001423 ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
Mike Stump1eb44332009-09-09 15:08:12 +00001424 getContext());
Ted Kremenekf936f452009-05-04 06:18:28 +00001425 QualType ETy = ER->getElementType();
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001426 SVal ElementVal = Retrieve(state, loc::MemRegionVal(ER), ETy).getSVal();
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001427 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
1428 }
1429
Zhongxing Xud91ee272009-06-23 09:02:15 +00001430 return ValMgr.makeCompoundVal(T, ArrayVal);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001431#else
1432 assert(isa<ConstantArrayType>(R->getValueType(getContext())));
1433 return ValMgr.makeLazyCompoundVal(state, R);
1434#endif
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001435}
1436
Ted Kremenek9af46f52009-06-16 22:36:44 +00001437//===----------------------------------------------------------------------===//
1438// Binding values to regions.
1439//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +00001440
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001441Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +00001442 if (isa<loc::MemRegionVal>(L))
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001443 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
1444 return Remove(store, BindingKey::Make(R));
Mike Stump1eb44332009-09-09 15:08:12 +00001445
Ted Kremenek0964a062009-01-21 06:57:53 +00001446 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001447}
1448
Ted Kremenek67f28532009-06-17 22:02:04 +00001449const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +00001450 if (isa<loc::ConcreteInt>(L))
1451 return state;
1452
Ted Kremenek9af46f52009-06-16 22:36:44 +00001453 // If we get here, the location should be a region.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001454 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001455
Ted Kremenek9af46f52009-06-16 22:36:44 +00001456 // Check if the region is a struct region.
1457 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
1458 if (TR->getValueType(getContext())->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001459 return BindStruct(state, TR, V);
Mike Stump1eb44332009-09-09 15:08:12 +00001460
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001461 // Special case: the current region represents a cast and it and the super
1462 // region both have pointer types or intptr_t types. If so, perform the
1463 // bind to the super region.
1464 // This is needed to support OSAtomicCompareAndSwap and friends or other
Mike Stump1eb44332009-09-09 15:08:12 +00001465 // loads that treat integers as pointers and vis versa.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001466 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1467 if (ER->getIndex().isZeroConstant()) {
1468 if (const TypedRegion *superR =
1469 dyn_cast<TypedRegion>(ER->getSuperRegion())) {
1470 ASTContext &Ctx = getContext();
1471 QualType superTy = superR->getValueType(Ctx);
1472 QualType erTy = ER->getValueType(Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +00001473
1474 if (IsAnyPointerOrIntptr(superTy, Ctx) &&
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001475 IsAnyPointerOrIntptr(erTy, Ctx)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001476 SValuator::CastResult cr =
1477 ValMgr.getSValuator().EvalCast(V, state, superTy, erTy);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001478 return Bind(cr.getState(), loc::MemRegionVal(superR), cr.getSVal());
1479 }
Ted Kremenek69181a82009-09-21 22:58:52 +00001480 // For now, just invalidate the fields of the struct/union/class.
1481 // FIXME: Precisely handle the fields of the record.
1482 if (superTy->isRecordType())
Ted Kremenek473e1672009-10-16 00:30:49 +00001483 return InvalidateRegion(state, superR, NULL, 0, NULL);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001484 }
1485 }
1486 }
Ted Kremenek0954cde2009-09-24 04:11:44 +00001487 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1488 // Binding directly to a symbolic region should be treated as binding
1489 // to element 0.
1490 QualType T = SR->getSymbol()->getType(getContext());
Ted Kremenek852274d2009-12-16 03:18:58 +00001491
1492 // FIXME: Is this the right way to handle symbols that are references?
1493 if (const PointerType *PT = T->getAs<PointerType>())
1494 T = PT->getPointeeType();
1495 else
1496 T = T->getAs<ReferenceType>()->getPointeeType();
1497
Ted Kremenek0954cde2009-09-24 04:11:44 +00001498 R = GetElementZeroRegion(SR, T);
1499 }
Mike Stump1eb44332009-09-09 15:08:12 +00001500
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001501 // Perform the binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001502 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001503 return state->makeWithStore(Add(B, R,
1504 BindingVal(V, BindingVal::Direct)).getRoot());
Ted Kremenek9af46f52009-06-16 22:36:44 +00001505}
1506
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001507const GRState *RegionStoreManager::BindDecl(const GRState *ST,
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001508 const VarRegion *VR,
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001509 SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +00001510
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001511 QualType T = VR->getDecl()->getType();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001512
Ted Kremenek0964a062009-01-21 06:57:53 +00001513 if (T->isArrayType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001514 return BindArray(ST, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +00001515 if (T->isStructureType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001516 return BindStruct(ST, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001517
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001518 return Bind(ST, ValMgr.makeLoc(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001519}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001520
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001521// FIXME: this method should be merged into Bind().
Ted Kremenek67f28532009-06-17 22:02:04 +00001522const GRState *
1523RegionStoreManager::BindCompoundLiteral(const GRState *state,
Ted Kremenek67d12872009-12-07 22:05:27 +00001524 const CompoundLiteralExpr *CL,
1525 const LocationContext *LC,
Ted Kremenek67f28532009-06-17 22:02:04 +00001526 SVal V) {
Ted Kremenek67d12872009-12-07 22:05:27 +00001527 return Bind(state, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)),
1528 V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001529}
1530
Ted Kremenek027e2662009-11-19 20:20:24 +00001531const GRState *RegionStoreManager::setImplicitDefaultValue(const GRState *state,
1532 const MemRegion *R,
1533 QualType T) {
1534 Store store = state->getStore();
1535 RegionBindings B = GetRegionBindings(store);
1536 SVal V;
1537
1538 if (Loc::IsLocType(T))
1539 V = ValMgr.makeNull();
1540 else if (T->isIntegerType())
1541 V = ValMgr.makeZeroVal(T);
1542 else if (T->isStructureType() || T->isArrayType()) {
1543 // Set the default value to a zero constant when it is a structure
1544 // or array. The type doesn't really matter.
1545 V = ValMgr.makeZeroVal(ValMgr.getContext().IntTy);
1546 }
1547 else {
1548 return state;
1549 }
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001550
1551 return state->makeWithStore(Add(B, R,
1552 BindingVal(V, BindingVal::Default)).getRoot());
Ted Kremenek027e2662009-11-19 20:20:24 +00001553}
1554
Ted Kremenek67f28532009-06-17 22:02:04 +00001555const GRState *RegionStoreManager::BindArray(const GRState *state,
Ted Kremenek46537392009-07-16 01:33:37 +00001556 const TypedRegion* R,
Ted Kremenek67f28532009-06-17 22:02:04 +00001557 SVal Init) {
1558
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001559 QualType T = R->getValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001560 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001561 QualType ElementTy = CAT->getElementType();
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001562
Ted Kremenek46537392009-07-16 01:33:37 +00001563 uint64_t size = CAT->getSize().getZExtValue();
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001564
1565 // Check if the init expr is a StringLiteral.
1566 if (isa<loc::MemRegionVal>(Init)) {
1567 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1568 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1569 const char* str = S->getStrData();
1570 unsigned len = S->getByteLength();
1571 unsigned j = 0;
1572
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001573 // Copy bytes from the string literal into the target array. Trailing bytes
1574 // in the array that are not covered by the string literal are initialized
1575 // to zero.
Ted Kremenek46537392009-07-16 01:33:37 +00001576 for (uint64_t i = 0; i < size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001577 if (j >= len)
1578 break;
1579
Ted Kremenek46537392009-07-16 01:33:37 +00001580 SVal Idx = ValMgr.makeArrayIndex(i);
Ted Kremenekb48ad642009-12-04 00:26:31 +00001581 const ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R,
1582 getContext());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001583
Zhongxing Xud91ee272009-06-23 09:02:15 +00001584 SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true);
Ted Kremenek67f28532009-06-17 22:02:04 +00001585 state = Bind(state, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001586 }
1587
Ted Kremenek67f28532009-06-17 22:02:04 +00001588 return state;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001589 }
1590
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001591 // Handle lazy compound values.
1592 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
1593 return CopyLazyBindings(*LCV, state, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001594
1595 // Remaining case: explicit compound values.
Ted Kremenek027e2662009-11-19 20:20:24 +00001596
1597 if (Init.isUnknown())
1598 return setImplicitDefaultValue(state, R, ElementTy);
1599
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001600 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001601 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Ted Kremenek46537392009-07-16 01:33:37 +00001602 uint64_t i = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001603
Ted Kremenek46537392009-07-16 01:33:37 +00001604 for (; i < size; ++i, ++VI) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001605 // The init list might be shorter than the array length.
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001606 if (VI == VE)
1607 break;
1608
Ted Kremenek46537392009-07-16 01:33:37 +00001609 SVal Idx = ValMgr.makeArrayIndex(i);
Ted Kremenekb48ad642009-12-04 00:26:31 +00001610 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001611
1612 if (CAT->getElementType()->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001613 state = BindStruct(state, ER, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001614 else
Ted Kremenekcf549592009-09-22 21:19:14 +00001615 // FIXME: Do we need special handling of nested arrays?
Zhongxing Xud91ee272009-06-23 09:02:15 +00001616 state = Bind(state, ValMgr.makeLoc(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001617 }
1618
Ted Kremenek027e2662009-11-19 20:20:24 +00001619 // If the init list is shorter than the array length, set the
1620 // array default value.
1621 if (i < size)
1622 state = setImplicitDefaultValue(state, R, ElementTy);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001623
Ted Kremenek67f28532009-06-17 22:02:04 +00001624 return state;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001625}
1626
Ted Kremenek67f28532009-06-17 22:02:04 +00001627const GRState *
1628RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R,
1629 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001630
Ted Kremenek67f28532009-06-17 22:02:04 +00001631 if (!Features.supportsFields())
1632 return state;
Mike Stump1eb44332009-09-09 15:08:12 +00001633
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001634 QualType T = R->getValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001635 assert(T->isStructureType());
1636
Ted Kremenek6217b802009-07-29 21:53:49 +00001637 const RecordType* RT = T->getAs<RecordType>();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001638 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001639
1640 if (!RD->isDefinition())
Ted Kremenek67f28532009-06-17 22:02:04 +00001641 return state;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001642
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001643 // Handle lazy compound values.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001644 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001645 return CopyLazyBindings(*LCV, state, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001646
Ted Kremenek67f28532009-06-17 22:02:04 +00001647 // We may get non-CompoundVal accidentally due to imprecise cast logic.
1648 // Ignore them and kill the field values.
1649 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
Zhongxing Xu13d50172009-10-11 08:08:02 +00001650 return state->makeWithStore(KillStruct(state->getStore(), R));
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001651
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001652 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001653 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001654
1655 RecordDecl::field_iterator FI, FE;
1656
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001657 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001658
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001659 if (VI == VE)
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001660 break;
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001661
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001662 QualType FTy = (*FI)->getType();
Ted Kremenekcf549592009-09-22 21:19:14 +00001663 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001664
Ted Kremenekcf549592009-09-22 21:19:14 +00001665 if (FTy->isArrayType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001666 state = BindArray(state, FR, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001667 else if (FTy->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001668 state = BindStruct(state, FR, *VI);
Ted Kremenekcf549592009-09-22 21:19:14 +00001669 else
1670 state = Bind(state, ValMgr.makeLoc(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001671 }
1672
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001673 // There may be fewer values in the initialize list than the fields of struct.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001674 if (FI != FE) {
1675 Store store = state->getStore();
1676 RegionBindings B = GetRegionBindings(store);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001677 B = Add(B, R, BindingVal(ValMgr.makeIntVal(0, false), BindingVal::Default));
Zhongxing Xu13d50172009-10-11 08:08:02 +00001678 state = state->makeWithStore(B.getRoot());
1679 }
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001680
Ted Kremenek67f28532009-06-17 22:02:04 +00001681 return state;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001682}
1683
Zhongxing Xu13d50172009-10-11 08:08:02 +00001684Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R) {
1685 RegionBindings B = GetRegionBindings(store);
1686 llvm::OwningPtr<RegionStoreSubRegionMap>
1687 SubRegions(getRegionStoreSubRegionMap(store));
1688 RemoveSubRegionBindings(B, R, *SubRegions);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001689
Zhongxing Xue4df9c42009-06-25 05:52:16 +00001690 // Set the default value of the struct region to "unknown".
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001691 B = Add(B, R, BindingVal(UnknownVal(), BindingVal::Default));
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001692
Zhongxing Xu13d50172009-10-11 08:08:02 +00001693 return B.getRoot();
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001694}
1695
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001696const GRState*
1697RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1698 const GRState *state,
1699 const TypedRegion *R) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001700
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001701 // Nuke the old bindings stemming from R.
Ted Kremenek451ac092009-08-06 04:50:20 +00001702 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001703
Mike Stump1eb44332009-09-09 15:08:12 +00001704 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +00001705 SubRegions(getRegionStoreSubRegionMap(state->getStore()));
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001706
Mike Stump1eb44332009-09-09 15:08:12 +00001707 // B and DVM are updated after the call to RemoveSubRegionBindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001708 RemoveSubRegionBindings(B, R, *SubRegions.get());
Mike Stump1eb44332009-09-09 15:08:12 +00001709
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001710 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1711 // results in a zero-copy algorithm.
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001712 return state->makeWithStore(Add(B, R,
1713 BindingVal(V, BindingVal::Direct)).getRoot());
1714}
1715
1716//===----------------------------------------------------------------------===//
1717// "Raw" retrievals and bindings.
1718//===----------------------------------------------------------------------===//
1719
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001720BindingKey BindingKey::Make(const MemRegion *R) {
1721 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1722 const RegionRawOffset &O = ER->getAsRawOffset();
1723
1724 if (O.getRegion())
1725 return BindingKey(O.getRegion(), O.getByteOffset());
1726
1727 // FIXME: There are some ElementRegions for which we cannot compute
1728 // raw offsets yet, including regions with symbolic offsets.
1729 }
1730
1731 return BindingKey(R, 0);
1732}
1733
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001734RegionBindings RegionStoreManager::Add(RegionBindings B, BindingKey K,
1735 BindingVal V) {
1736 return RBFactory.Add(B, K, V);
1737}
1738
1739RegionBindings RegionStoreManager::Add(RegionBindings B, const MemRegion *R,
1740 BindingVal V) {
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001741 return Add(B, BindingKey::Make(R), V);
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001742}
1743
1744const BindingVal *RegionStoreManager::Lookup(RegionBindings B, BindingKey K) {
1745 return B.lookup(K);
1746}
1747
1748const BindingVal *RegionStoreManager::Lookup(RegionBindings B,
1749 const MemRegion *R) {
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001750 return Lookup(B, BindingKey::Make(R));
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001751}
1752
1753RegionBindings RegionStoreManager::Remove(RegionBindings B, BindingKey K) {
1754 return RBFactory.Remove(B, K);
1755}
1756
1757RegionBindings RegionStoreManager::Remove(RegionBindings B, const MemRegion *R){
Ted Kremenekc50e6df2010-01-11 02:33:26 +00001758 return Remove(B, BindingKey::Make(R));
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001759}
1760
1761Store RegionStoreManager::Remove(Store store, BindingKey K) {
1762 RegionBindings B = GetRegionBindings(store);
1763 return Remove(B, K).getRoot();
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001764}
Mike Stump1eb44332009-09-09 15:08:12 +00001765
Ted Kremenek9af46f52009-06-16 22:36:44 +00001766//===----------------------------------------------------------------------===//
1767// State pruning.
1768//===----------------------------------------------------------------------===//
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001769
Mike Stump1eb44332009-09-09 15:08:12 +00001770void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc,
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001771 SymbolReaper& SymReaper,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001772 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +00001773{
Ted Kremenek781115c2009-10-17 17:45:11 +00001774 typedef std::pair<const GRState*, const MemRegion *> RBDNode;
1775
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001776 Store store = state.getStore();
Ted Kremenek451ac092009-08-06 04:50:20 +00001777 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001778
Ted Kremenek9af46f52009-06-16 22:36:44 +00001779 // The backmap from regions to subregions.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001780 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +00001781 SubRegions(getRegionStoreSubRegionMap(store));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001782
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001783 // Do a pass over the regions in the store. For VarRegions we check if
1784 // the variable is still live and if so add it to the list of live roots.
1785 // For other regions we populate our region backmap.
Ted Kremenek9af46f52009-06-16 22:36:44 +00001786 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001787
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001788 // Scan the direct bindings for "intermediate" roots.
Ted Kremenek451ac092009-08-06 04:50:20 +00001789 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001790 const MemRegion *R = I.getKey().getRegion();
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001791 IntermediateRoots.push_back(R);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001792 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001793
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001794 // Process the "intermediate" roots to find if they are referenced by
Mike Stump1eb44332009-09-09 15:08:12 +00001795 // real roots.
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001796 llvm::SmallVector<RBDNode, 10> WorkList;
Ted Kremenek01756192009-10-29 05:14:17 +00001797 llvm::SmallVector<RBDNode, 10> Postponed;
1798
Zhongxing Xu6800b332009-10-18 04:15:47 +00001799 llvm::DenseSet<const MemRegion*> IntermediateVisited;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001800
Ted Kremenek9af46f52009-06-16 22:36:44 +00001801 while (!IntermediateRoots.empty()) {
1802 const MemRegion* R = IntermediateRoots.back();
1803 IntermediateRoots.pop_back();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001804
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001805 if (IntermediateVisited.count(R))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001806 continue;
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001807 IntermediateVisited.insert(R);
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001808
Ted Kremenek9af46f52009-06-16 22:36:44 +00001809 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
Ted Kremenekedeb5b62009-12-04 20:32:20 +00001810 if (SymReaper.isLive(Loc, VR))
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001811 WorkList.push_back(std::make_pair(&state, VR));
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001812 continue;
1813 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001814
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001815 if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
Ted Kremenek01756192009-10-29 05:14:17 +00001816 llvm::SmallVectorImpl<RBDNode> &Q =
1817 SymReaper.isLive(SR->getSymbol()) ? WorkList : Postponed;
1818
1819 Q.push_back(std::make_pair(&state, SR));
1820
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001821 continue;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001822 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001823
1824 // Add the super region for R to the worklist if it is a subregion.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001825 if (const SubRegion* superR =
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001826 dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion()))
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001827 IntermediateRoots.push_back(superR);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001828 }
Mike Stump1eb44332009-09-09 15:08:12 +00001829
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001830 // Enqueue the RegionRoots onto WorkList.
1831 for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(),
1832 E=RegionRoots.end(); I!=E; ++I) {
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001833 WorkList.push_back(std::make_pair(&state, *I));
Mike Stump1eb44332009-09-09 15:08:12 +00001834 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001835 RegionRoots.clear();
1836
Zhongxing Xu6800b332009-10-18 04:15:47 +00001837 llvm::DenseSet<RBDNode> Visited;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001838
Ted Kremenek01756192009-10-29 05:14:17 +00001839tryAgain:
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001840 while (!WorkList.empty()) {
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001841 RBDNode N = WorkList.back();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001842 WorkList.pop_back();
1843
1844 // Have we visited this node before?
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001845 if (Visited.count(N))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001846 continue;
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001847 Visited.insert(N);
Mike Stump1eb44332009-09-09 15:08:12 +00001848
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001849 const MemRegion *R = N.second;
1850 const GRState *state_N = N.first;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001851
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001852 // Enqueue subregions.
1853 RegionStoreSubRegionMap *M;
1854
1855 if (&state == state_N)
1856 M = SubRegions.get();
1857 else {
1858 RegionStoreSubRegionMap *& SM = SC[state_N];
1859 if (!SM)
1860 SM = getRegionStoreSubRegionMap(state_N->getStore());
1861 M = SM;
1862 }
1863
1864 RegionStoreSubRegionMap::iterator I, E;
1865 for (llvm::tie(I, E) = M->begin_end(R); I != E; ++I)
1866 WorkList.push_back(std::make_pair(state_N, *I));
1867
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001868 // Enqueue the super region.
1869 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1870 const MemRegion *superR = SR->getSuperRegion();
1871 if (!isa<MemSpaceRegion>(superR)) {
1872 // If 'R' is a field or an element, we want to keep the bindings
1873 // for the other fields and elements around. The reason is that
Zhongxing Xu13d50172009-10-11 08:08:02 +00001874 // pointer arithmetic can get us to the other fields or elements.
Zhongxing Xu8801beb2009-10-17 07:32:08 +00001875 assert(isa<FieldRegion>(R) || isa<ElementRegion>(R)
1876 || isa<ObjCIvarRegion>(R));
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001877 WorkList.push_back(std::make_pair(state_N, superR));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001878 }
1879 }
1880
1881 // Mark the symbol for any live SymbolicRegion as "live". This means we
1882 // should continue to track that symbol.
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001883 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001884 SymReaper.markLive(SymR->getSymbol());
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001885
Ted Kremeneka7a8dfd2009-12-03 17:48:05 +00001886 // For BlockDataRegions, enqueue the VarRegions for variables marked
1887 // with __block (passed-by-reference).
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001888 // via BlockDeclRefExprs.
1889 if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
1890 for (BlockDataRegion::referenced_vars_iterator
1891 RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
Ted Kremeneka7a8dfd2009-12-03 17:48:05 +00001892 RI != RE; ++RI) {
1893 if ((*RI)->getDecl()->getAttr<BlocksAttr>())
1894 WorkList.push_back(std::make_pair(state_N, *RI));
1895 }
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001896 // No possible data bindings on a BlockDataRegion. Continue to the
1897 // next region in the worklist.
1898 continue;
1899 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001900
1901 Store store_N = state_N->getStore();
1902 RegionBindings B_N = GetRegionBindings(store_N);
1903
1904 // Get the data binding for R (if any).
Zhongxing Xu13d50172009-10-11 08:08:02 +00001905 Optional<SVal> V = getBinding(B_N, R);
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001906
Zhongxing Xu13d50172009-10-11 08:08:02 +00001907 if (V) {
1908 // Check for lazy bindings.
1909 if (const nonloc::LazyCompoundVal *LCV =
1910 dyn_cast<nonloc::LazyCompoundVal>(V.getPointer())) {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001911
Zhongxing Xu13d50172009-10-11 08:08:02 +00001912 const LazyCompoundValData *D = LCV->getCVData();
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001913 WorkList.push_back(std::make_pair(D->getState(), D->getRegion()));
Zhongxing Xu13d50172009-10-11 08:08:02 +00001914 }
1915 else {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001916 // Update the set of live symbols.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001917 for (SVal::symbol_iterator SI=V->symbol_begin(), SE=V->symbol_end();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001918 SI!=SE;++SI)
1919 SymReaper.markLive(*SI);
1920
Zhongxing Xu13d50172009-10-11 08:08:02 +00001921 // If V is a region, then add it to the worklist.
1922 if (const MemRegion *RX = V->getAsRegion())
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001923 WorkList.push_back(std::make_pair(state_N, RX));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001924 }
1925 }
1926 }
1927
Ted Kremenek01756192009-10-29 05:14:17 +00001928 // See if any postponed SymbolicRegions are actually live now, after
1929 // having done a scan.
1930 for (llvm::SmallVectorImpl<RBDNode>::iterator I = Postponed.begin(),
1931 E = Postponed.end() ; I != E ; ++I) {
1932 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(I->second)) {
1933 if (SymReaper.isLive(SR->getSymbol())) {
1934 WorkList.push_back(*I);
1935 I->second = NULL;
1936 }
1937 }
1938 }
1939
1940 if (!WorkList.empty())
1941 goto tryAgain;
1942
Ted Kremenek9af46f52009-06-16 22:36:44 +00001943 // We have now scanned the store, marking reachable regions and symbols
1944 // as live. We now remove all the regions that are dead from the store
Mike Stump1eb44332009-09-09 15:08:12 +00001945 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenek451ac092009-08-06 04:50:20 +00001946 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001947 const MemRegion* R = I.getKey().getRegion();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001948 // If this region live? Is so, none of its symbols are dead.
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001949 if (Visited.count(std::make_pair(&state, R)))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001950 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001951
Ted Kremenek9af46f52009-06-16 22:36:44 +00001952 // Remove this dead region from the store.
Ted Kremenek1c1ae6b2010-01-11 00:07:44 +00001953 store = Remove(store, I.getKey());
Mike Stump1eb44332009-09-09 15:08:12 +00001954
Ted Kremenek9af46f52009-06-16 22:36:44 +00001955 // Mark all non-live symbols that this region references as dead.
1956 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1957 SymReaper.maybeDead(SymR->getSymbol());
Mike Stump1eb44332009-09-09 15:08:12 +00001958
Zhongxing Xu13d50172009-10-11 08:08:02 +00001959 SVal X = *I.getData().getValue();
Ted Kremenek093569c2009-08-02 05:00:15 +00001960 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1961 for (; SI != SE; ++SI)
1962 SymReaper.maybeDead(*SI);
1963 }
Mike Stump1eb44332009-09-09 15:08:12 +00001964
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001965 // Write the store back.
1966 state.setStore(store);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001967}
1968
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001969GRState const *RegionStoreManager::EnterStackFrame(GRState const *state,
1970 StackFrameContext const *frame) {
1971 FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
1972 CallExpr const *CE = cast<CallExpr>(frame->getCallSite());
1973
1974 FunctionDecl::param_const_iterator PI = FD->param_begin();
1975
1976 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1977
1978 // Copy the arg expression value to the arg variables.
1979 for (; AI != AE; ++AI, ++PI) {
1980 SVal ArgVal = state->getSVal(*AI);
Ted Kremenekb48ad642009-12-04 00:26:31 +00001981 state = Bind(state, ValMgr.makeLoc(MRMgr.getVarRegion(*PI, frame)), ArgVal);
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001982 }
1983
1984 return state;
1985}
1986
Ted Kremenek9af46f52009-06-16 22:36:44 +00001987//===----------------------------------------------------------------------===//
1988// Utility methods.
1989//===----------------------------------------------------------------------===//
1990
Ted Kremenek53ba0b62009-06-24 23:06:47 +00001991void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001992 const char* nl, const char *sep) {
Ted Kremenek451ac092009-08-06 04:50:20 +00001993 RegionBindings B = GetRegionBindings(store);
Ted Kremenekab22ee92009-10-20 01:20:57 +00001994 OS << "Store (direct and default bindings):" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +00001995
Ted Kremenek451ac092009-08-06 04:50:20 +00001996 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
Mike Stump1eb44332009-09-09 15:08:12 +00001997 OS << ' ' << I.getKey() << " : " << I.getData() << nl;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001998}