blob: 8106260f18f053e4da5478020af4b7e9b5a18b71 [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#include "llvm/Support/Compiler.h"
29
30using namespace clang;
31
Ted Kremenek356e9d62009-07-22 04:35:42 +000032#define HEAP_UNDEFINED 0
Ted Kremeneka5e81f12009-08-06 01:20:57 +000033#define USE_EXPLICIT_COMPOUND 0
Ted Kremenek356e9d62009-07-22 04:35:42 +000034
Zhongxing Xu13d50172009-10-11 08:08:02 +000035namespace {
36class BindingVal {
37public:
38 enum BindingKind { Direct, Default };
39private:
40 SVal Value;
41 BindingKind Kind;
42
43public:
44 BindingVal(SVal V, BindingKind K) : Value(V), Kind(K) {}
45
46 bool isDefault() const { return Kind == Default; }
47
48 const SVal *getValue() const { return &Value; }
49
50 const SVal *getDirectValue() const { return isDefault() ? 0 : &Value; }
51
52 const SVal *getDefaultValue() const { return isDefault() ? &Value : 0; }
53
54 void Profile(llvm::FoldingSetNodeID& ID) const {
55 Value.Profile(ID);
56 ID.AddInteger(Kind);
57 }
58
59 inline bool operator==(const BindingVal& R) const {
60 return Value == R.Value && Kind == R.Kind;
61 }
62
63 inline bool operator!=(const BindingVal& R) const {
64 return !(*this == R);
65 }
66};
67}
68
69namespace llvm {
70static inline
71llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingVal V) {
72 if (V.isDefault())
73 os << "(default) ";
74 else
75 os << "(direct) ";
76 os << *V.getValue();
77 return os;
78}
79} // end llvm namespace
80
Zhongxing Xubaf03a72008-11-24 09:44:56 +000081// Actual Store type.
Zhongxing Xu13d50172009-10-11 08:08:02 +000082typedef llvm::ImmutableMap<const MemRegion*, BindingVal> RegionBindings;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000083
Ted Kremenek50dc1b32008-12-24 01:05:03 +000084//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +000085// Fine-grained control of RegionStoreManager.
86//===----------------------------------------------------------------------===//
87
88namespace {
89struct VISIBILITY_HIDDEN minimal_features_tag {};
Mike Stump1eb44332009-09-09 15:08:12 +000090struct VISIBILITY_HIDDEN maximal_features_tag {};
91
Ted Kremenek9af46f52009-06-16 22:36:44 +000092class VISIBILITY_HIDDEN RegionStoreFeatures {
93 bool SupportsFields;
94 bool SupportsRemaining;
Mike Stump1eb44332009-09-09 15:08:12 +000095
Ted Kremenek9af46f52009-06-16 22:36:44 +000096public:
97 RegionStoreFeatures(minimal_features_tag) :
98 SupportsFields(false), SupportsRemaining(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +000099
Ted Kremenek9af46f52009-06-16 22:36:44 +0000100 RegionStoreFeatures(maximal_features_tag) :
101 SupportsFields(true), SupportsRemaining(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000102
Ted Kremenek9af46f52009-06-16 22:36:44 +0000103 void enableFields(bool t) { SupportsFields = t; }
Mike Stump1eb44332009-09-09 15:08:12 +0000104
Ted Kremenek9af46f52009-06-16 22:36:44 +0000105 bool supportsFields() const { return SupportsFields; }
106 bool supportsRemaining() const { return SupportsRemaining; }
107};
108}
109
110//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000111// Region "Extents"
112//===----------------------------------------------------------------------===//
113//
114// MemRegions represent chunks of memory with a size (their "extent"). This
115// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000116//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000117namespace { class VISIBILITY_HIDDEN RegionExtents {}; }
118static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000119namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000120 template<> struct GRStateTrait<RegionExtents>
121 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
122 static void* GDMIndex() { return &RegionExtentsIndex; }
123 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000124}
125
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000126//===----------------------------------------------------------------------===//
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000127// Utility functions.
128//===----------------------------------------------------------------------===//
129
130static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) {
131 if (ty->isAnyPointerType())
132 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000133
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000134 return ty->isIntegerType() && ty->isScalarType() &&
135 Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy);
136}
137
138//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000139// Main RegionStore logic.
140//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000141
Zhongxing Xu17892752008-10-08 02:50:44 +0000142namespace {
Mike Stump1eb44332009-09-09 15:08:12 +0000143
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000144class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
145 typedef llvm::ImmutableSet<const MemRegion*> SetTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000146 typedef llvm::DenseMap<const MemRegion*, SetTy> Map;
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000147 SetTy::Factory F;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000148 Map M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000149public:
Ted Kremenekd8c01922009-08-05 19:09:24 +0000150 bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000151 Map::iterator I = M.find(Parent);
Ted Kremenekd8c01922009-08-05 19:09:24 +0000152
153 if (I == M.end()) {
Ted Kremenek4ed45982009-08-05 05:31:02 +0000154 M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion)));
Ted Kremenekd8c01922009-08-05 19:09:24 +0000155 return true;
156 }
157
158 I->second = F.Add(I->second, SubRegion);
159 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000160 }
Mike Stump1eb44332009-09-09 15:08:12 +0000161
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000162 void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000163
Ted Kremenek59e8f112009-03-03 01:35:36 +0000164 ~RegionStoreSubRegionMap() {}
Mike Stump1eb44332009-09-09 15:08:12 +0000165
Ted Kremenek5dc27462009-03-03 02:51:43 +0000166 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +0000167 Map::const_iterator I = M.find(Parent);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000168
169 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000170 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000171
Ted Kremenek59e8f112009-03-03 01:35:36 +0000172 llvm::ImmutableSet<const MemRegion*> S = I->second;
173 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
174 SI != SE; ++SI) {
175 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000176 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000177 }
Mike Stump1eb44332009-09-09 15:08:12 +0000178
Ted Kremenek5dc27462009-03-03 02:51:43 +0000179 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000180 }
Mike Stump1eb44332009-09-09 15:08:12 +0000181
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000182 typedef SetTy::iterator iterator;
183
184 std::pair<iterator, iterator> begin_end(const MemRegion *R) {
185 Map::iterator I = M.find(R);
186 SetTy S = I == M.end() ? F.GetEmptySet() : I->second;
187 return std::make_pair(S.begin(), S.end());
188 }
Mike Stump1eb44332009-09-09 15:08:12 +0000189};
Ted Kremenek59e8f112009-03-03 01:35:36 +0000190
Zhongxing Xu17892752008-10-08 02:50:44 +0000191class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000192 const RegionStoreFeatures Features;
Ted Kremenek451ac092009-08-06 04:50:20 +0000193 RegionBindings::Factory RBFactory;
Ted Kremenek9e17cc62009-09-29 06:35:00 +0000194
195 typedef llvm::DenseMap<const GRState *, RegionStoreSubRegionMap*> SMCache;
196 SMCache SC;
197
Zhongxing Xu17892752008-10-08 02:50:44 +0000198public:
Mike Stump1eb44332009-09-09 15:08:12 +0000199 RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
Ted Kremenekf7a0cf42009-07-29 21:43:22 +0000200 : StoreManager(mgr),
Ted Kremenek9af46f52009-06-16 22:36:44 +0000201 Features(f),
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000202 RBFactory(mgr.getAllocator()) {}
Zhongxing Xu17892752008-10-08 02:50:44 +0000203
Ted Kremenek9e17cc62009-09-29 06:35:00 +0000204 virtual ~RegionStoreManager() {
205 for (SMCache::iterator I = SC.begin(), E = SC.end(); I != E; ++I)
206 delete (*I).second;
207 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000208
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000209 SubRegionMap *getSubRegionMap(const GRState *state);
Mike Stump1eb44332009-09-09 15:08:12 +0000210
Zhongxing Xu13d50172009-10-11 08:08:02 +0000211 RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
Mike Stump1eb44332009-09-09 15:08:12 +0000212
Zhongxing Xu13d50172009-10-11 08:08:02 +0000213 Optional<SVal> getBinding(RegionBindings B, const MemRegion *R);
214 Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000215 /// getDefaultBinding - Returns an SVal* representing an optional default
216 /// binding associated with a region and its subregions.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000217 Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000218
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000219 /// getLValueString - Returns an SVal representing the lvalue of a
220 /// StringLiteral. Within RegionStore a StringLiteral has an
221 /// associated StringRegion, and the lvalue of a StringLiteral is
222 /// the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000223 SVal getLValueString(const StringLiteral* S);
Zhongxing Xu143bf822008-10-25 14:18:57 +0000224
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000225 /// getLValueCompoundLiteral - Returns an SVal representing the
226 /// lvalue of a compound literal. Within RegionStore a compound
227 /// literal has an associated region, and the lvalue of the
228 /// compound literal is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000229 SVal getLValueCompoundLiteral(const CompoundLiteralExpr*);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000230
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000231 /// getLValueVar - Returns an SVal that represents the lvalue of a
232 /// variable. Within RegionStore a variable has an associated
233 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000234 SVal getLValueVar(const VarDecl *VD, const LocationContext *LC);
Mike Stump1eb44332009-09-09 15:08:12 +0000235
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000236 SVal getLValueIvar(const ObjCIvarDecl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000237
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000238 SVal getLValueField(const FieldDecl* D, SVal Base);
Mike Stump1eb44332009-09-09 15:08:12 +0000239
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000240 SVal getLValueFieldOrIvar(const Decl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000241
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000242 SVal getLValueElement(QualType elementType, SVal Offset, SVal Base);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000243
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000244
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000245 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
246 /// type. 'Array' represents the lvalue of the array being decayed
247 /// to a pointer, and the returned SVal represents the decayed
248 /// version of that lvalue (i.e., a pointer to the first element of
249 /// the array). This is called by GRExprEngine when evaluating
250 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000251 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000252
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000253 SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L,
Ted Kremenek5c734622009-06-26 00:41:43 +0000254 NonLoc R, QualType resultTy);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000255
Mike Stump1eb44332009-09-09 15:08:12 +0000256 Store getInitialStore(const LocationContext *InitLoc) {
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000257 return RBFactory.GetEmptyMap().getRoot();
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000258 }
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000259
Ted Kremenek67f28532009-06-17 22:02:04 +0000260 //===-------------------------------------------------------------------===//
261 // Binding values to regions.
262 //===-------------------------------------------------------------------===//
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000263
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000264 const GRState *InvalidateRegion(const GRState *state, const MemRegion *R,
Ted Kremenek473e1672009-10-16 00:30:49 +0000265 const Expr *E, unsigned Count,
266 InvalidatedSymbols *IS);
Mike Stump1eb44332009-09-09 15:08:12 +0000267
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000268private:
Zhongxing Xu13d50172009-10-11 08:08:02 +0000269 void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000270 RegionStoreSubRegionMap &M);
Mike Stump1eb44332009-09-09 15:08:12 +0000271
272public:
Ted Kremenek67f28532009-06-17 22:02:04 +0000273 const GRState *Bind(const GRState *state, Loc LV, SVal V);
274
275 const GRState *BindCompoundLiteral(const GRState *state,
Zhongxing Xu13d50172009-10-11 08:08:02 +0000276 const CompoundLiteralExpr* CL, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000277
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000278 const GRState *BindDecl(const GRState *ST, const VarRegion *VR,
279 SVal InitVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000280
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000281 const GRState *BindDeclWithNoInit(const GRState *state,
282 const VarRegion *) {
Ted Kremenek67f28532009-06-17 22:02:04 +0000283 return state;
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000284 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000285
Ted Kremenek67f28532009-06-17 22:02:04 +0000286 /// BindStruct - Bind a compound value to a structure.
287 const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000288
Ted Kremenek67f28532009-06-17 22:02:04 +0000289 const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000290
291 /// KillStruct - Set the entire struct to unknown.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000292 Store KillStruct(Store store, const TypedRegion* R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000293
Ted Kremenek67f28532009-06-17 22:02:04 +0000294 Store Remove(Store store, Loc LV);
295
296 //===------------------------------------------------------------------===//
297 // Loading values from regions.
298 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000299
Ted Kremenek67f28532009-06-17 22:02:04 +0000300 /// The high level logic for this method is this:
301 /// Retrieve (L)
302 /// if L has binding
303 /// return L's binding
304 /// else if L is in killset
305 /// return unknown
306 /// else
307 /// if L is on stack or heap
308 /// return undefined
309 /// else
310 /// return symbolic
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000311 SValuator::CastResult Retrieve(const GRState *state, Loc L,
312 QualType T = QualType());
Zhongxing Xu490b0f02009-06-25 04:50:44 +0000313
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000314 SVal RetrieveElement(const GRState *state, const ElementRegion *R);
Zhongxing Xuc00346f2009-06-25 05:29:39 +0000315
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000316 SVal RetrieveField(const GRState *state, const FieldRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000317
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000318 SVal RetrieveObjCIvar(const GRState *state, const ObjCIvarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000319
Ted Kremenek9031dd72009-07-21 00:12:07 +0000320 SVal RetrieveVar(const GRState *state, const VarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000321
Ted Kremenek25c54572009-07-20 22:58:02 +0000322 SVal RetrieveLazySymbol(const GRState *state, const TypedRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000323
Ted Kremenek566a6fa2009-08-06 22:33:36 +0000324 SVal RetrieveFieldOrElementCommon(const GRState *state, const TypedRegion *R,
325 QualType Ty, const MemRegion *superR);
Mike Stump1eb44332009-09-09 15:08:12 +0000326
Ted Kremenek67f28532009-06-17 22:02:04 +0000327 /// Retrieve the values in a struct and return a CompoundVal, used when doing
Mike Stump1eb44332009-09-09 15:08:12 +0000328 /// struct copy:
329 /// struct s x, y;
Ted Kremenek67f28532009-06-17 22:02:04 +0000330 /// x = y;
331 /// y's value is retrieved by this method.
332 SVal RetrieveStruct(const GRState *St, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000333
Ted Kremenek67f28532009-06-17 22:02:04 +0000334 SVal RetrieveArray(const GRState *St, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000335
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000336 std::pair<const GRState*, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +0000337 GetLazyBinding(RegionBindings B, const MemRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000338
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000339 const GRState* CopyLazyBindings(nonloc::LazyCompoundVal V,
340 const GRState *state,
341 const TypedRegion *R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000342
Ted Kremenek0954cde2009-09-24 04:11:44 +0000343 const ElementRegion *GetElementZeroRegion(const SymbolicRegion *SR,
344 QualType T);
345
Ted Kremenek67f28532009-06-17 22:02:04 +0000346 //===------------------------------------------------------------------===//
347 // State pruning.
348 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000349
Ted Kremenek67f28532009-06-17 22:02:04 +0000350 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
351 /// It returns a new Store with these values removed.
Ted Kremenek2f26bc32009-08-02 04:45:08 +0000352 void RemoveDeadBindings(GRState &state, Stmt* Loc, SymbolReaper& SymReaper,
Ted Kremenek67f28532009-06-17 22:02:04 +0000353 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
354
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +0000355 const GRState *EnterStackFrame(const GRState *state,
356 const StackFrameContext *frame);
357
Ted Kremenek67f28532009-06-17 22:02:04 +0000358 //===------------------------------------------------------------------===//
359 // Region "extents".
360 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000361
Ted Kremenek67f28532009-06-17 22:02:04 +0000362 const GRState *setExtent(const GRState *state, const MemRegion* R, SVal Extent);
363 SVal getSizeInElements(const GRState *state, const MemRegion* R);
364
365 //===------------------------------------------------------------------===//
Ted Kremenek67f28532009-06-17 22:02:04 +0000366 // Utility methods.
367 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000368
Ted Kremenek451ac092009-08-06 04:50:20 +0000369 static inline RegionBindings GetRegionBindings(Store store) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000370 return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000371 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000372
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000373 void print(Store store, llvm::raw_ostream& Out, const char* nl,
374 const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000375
376 void iterBindings(Store store, BindingsHandler& f) {
377 // FIXME: Implement.
378 }
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000379
Ted Kremenek67f28532009-06-17 22:02:04 +0000380 // FIXME: Remove.
381 BasicValueFactory& getBasicVals() {
382 return StateMgr.getBasicVals();
383 }
Mike Stump1eb44332009-09-09 15:08:12 +0000384
Ted Kremenek67f28532009-06-17 22:02:04 +0000385 // FIXME: Remove.
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000386 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xu17892752008-10-08 02:50:44 +0000387};
388
389} // end anonymous namespace
390
Ted Kremenek9af46f52009-06-16 22:36:44 +0000391//===----------------------------------------------------------------------===//
392// RegionStore creation.
393//===----------------------------------------------------------------------===//
394
395StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
396 RegionStoreFeatures F = maximal_features_tag();
397 return new RegionStoreManager(StMgr, F);
398}
399
400StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
401 RegionStoreFeatures F = minimal_features_tag();
402 F.enableFields(true);
403 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000404}
405
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000406void
407RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL,
Mike Stump1eb44332009-09-09 15:08:12 +0000408 const SubRegion *R) {
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000409 const MemRegion *superR = R->getSuperRegion();
410 if (add(superR, R))
411 if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
Mike Stump1eb44332009-09-09 15:08:12 +0000412 WL.push_back(sr);
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000413}
414
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000415RegionStoreSubRegionMap*
Zhongxing Xu13d50172009-10-11 08:08:02 +0000416RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
417 RegionBindings B = GetRegionBindings(store);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000418 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
Mike Stump1eb44332009-09-09 15:08:12 +0000419
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000420 llvm::SmallVector<const SubRegion*, 10> WL;
421
Ted Kremenek451ac092009-08-06 04:50:20 +0000422 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000423 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey()))
424 M->process(WL, R);
Mike Stump1eb44332009-09-09 15:08:12 +0000425
Mike Stump1eb44332009-09-09 15:08:12 +0000426 // We also need to record in the subregion map "intermediate" regions that
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000427 // don't have direct bindings but are super regions of those that do.
428 while (!WL.empty()) {
429 const SubRegion *R = WL.back();
430 WL.pop_back();
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000431 M->process(WL, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000432 }
433
Ted Kremenek14453bf2009-03-03 19:02:42 +0000434 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000435}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000436
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000437SubRegionMap *RegionStoreManager::getSubRegionMap(const GRState *state) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000438 return getRegionStoreSubRegionMap(state->getStore());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000439}
440
Ted Kremenek9af46f52009-06-16 22:36:44 +0000441//===----------------------------------------------------------------------===//
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000442// Binding invalidation.
443//===----------------------------------------------------------------------===//
444
Zhongxing Xu13d50172009-10-11 08:08:02 +0000445void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
446 const MemRegion *R,
447 RegionStoreSubRegionMap &M) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000448 RegionStoreSubRegionMap::iterator I, E;
449
450 for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I)
Zhongxing Xu13d50172009-10-11 08:08:02 +0000451 RemoveSubRegionBindings(B, *I, M);
Mike Stump1eb44332009-09-09 15:08:12 +0000452
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000453 B = RBFactory.Remove(B, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000454}
455
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000456const GRState *RegionStoreManager::InvalidateRegion(const GRState *state,
457 const MemRegion *R,
Ted Kremenek87806792009-09-27 20:45:21 +0000458 const Expr *Ex,
Ted Kremenek473e1672009-10-16 00:30:49 +0000459 unsigned Count,
460 InvalidatedSymbols *IS) {
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000461 ASTContext& Ctx = StateMgr.getContext();
Mike Stump1eb44332009-09-09 15:08:12 +0000462
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000463 // Strip away casts.
464 R = R->getBaseRegion();
465
Ted Kremenek87806792009-09-27 20:45:21 +0000466 // Get the mapping of regions -> subregions.
467 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +0000468 SubRegions(getRegionStoreSubRegionMap(state->getStore()));
Ted Kremenek87806792009-09-27 20:45:21 +0000469
470 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +0000471
Ted Kremenek87806792009-09-27 20:45:21 +0000472 llvm::DenseMap<const MemRegion *, unsigned> Visited;
473 llvm::SmallVector<const MemRegion *, 10> WorkList;
474 WorkList.push_back(R);
475
476 while (!WorkList.empty()) {
477 R = WorkList.back();
478 WorkList.pop_back();
479
480 // Have we visited this region before?
481 unsigned &visited = Visited[R];
482 if (visited)
483 continue;
484 visited = 1;
Mike Stump1eb44332009-09-09 15:08:12 +0000485
Ted Kremenek87806792009-09-27 20:45:21 +0000486 // Add subregions to work list.
487 RegionStoreSubRegionMap::iterator I, E;
488 for (llvm::tie(I, E) = SubRegions->begin_end(R); I!=E; ++I)
489 WorkList.push_back(*I);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000490
491 // Get the old binding. Is it a region? If so, add it to the worklist.
492 if (Optional<SVal> V = getDirectBinding(B, R)) {
493 if (const MemRegion *RV = V->getAsRegion())
494 WorkList.push_back(RV);
Ted Kremenek473e1672009-10-16 00:30:49 +0000495
496 // A symbol? Mark it touched by the invalidation.
497 if (IS) {
498 if (SymbolRef Sym = V->getAsSymbol())
499 IS->insert(Sym);
500 }
Zhongxing Xu13d50172009-10-11 08:08:02 +0000501 }
502
Ted Kremenek473e1672009-10-16 00:30:49 +0000503 // Symbolic region? Mark that symbol touched by the invalidation.
504 if (IS) {
505 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
506 IS->insert(SR->getSymbol());
507 }
508
509 // Handle the region itself.
Ted Kremenek87806792009-09-27 20:45:21 +0000510 if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R) ||
511 isa<ObjCObjectRegion>(R)) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000512 // Invalidate the region by setting its default value to
513 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek87806792009-09-27 20:45:21 +0000514 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
515 Count);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000516 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000517 continue;
518 }
Mike Stump1eb44332009-09-09 15:08:12 +0000519
Ted Kremenek87806792009-09-27 20:45:21 +0000520 if (!R->isBoundable())
521 continue;
522
523 const TypedRegion *TR = cast<TypedRegion>(R);
524 QualType T = TR->getValueType(Ctx);
525
526 if (const RecordType *RT = T->getAsStructureType()) {
Ted Kremenek87806792009-09-27 20:45:21 +0000527 const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx);
528
Zhongxing Xu13d50172009-10-11 08:08:02 +0000529 // No record definition. There is nothing we can do.
Ted Kremenek87806792009-09-27 20:45:21 +0000530 if (!RD)
531 continue;
532
Zhongxing Xu13d50172009-10-11 08:08:02 +0000533 // Invalidate the region by setting its default value to
534 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek87806792009-09-27 20:45:21 +0000535 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
536 Count);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000537 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000538 continue;
539 }
540
541 if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
542 // Set the default value of the array to conjured symbol.
543 DefinedOrUnknownSVal V =
544 ValMgr.getConjuredSymbolVal(R, Ex, AT->getElementType(), Count);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000545 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000546 continue;
547 }
Ted Kremeneka5971b32009-09-29 03:34:03 +0000548
549 if ((isa<FieldRegion>(R)||isa<ElementRegion>(R)||isa<ObjCIvarRegion>(R))
550 && Visited[cast<SubRegion>(R)->getSuperRegion()]) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000551 // For fields and elements whose super region has also been invalidated,
552 // only remove the old binding. The super region will get set with a
553 // default value from which we can lazily derive a new symbolic value.
Ted Kremeneka5971b32009-09-29 03:34:03 +0000554 B = RBFactory.Remove(B, R);
555 continue;
556 }
Ted Kremenek87806792009-09-27 20:45:21 +0000557
Ted Kremenek389c44c2009-09-29 03:12:50 +0000558 // Invalidate the binding.
Ted Kremenek87806792009-09-27 20:45:21 +0000559 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, T, Count);
560 assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
Zhongxing Xu13d50172009-10-11 08:08:02 +0000561 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Direct));
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000562 }
563
Ted Kremenek87806792009-09-27 20:45:21 +0000564 // Create a new state with the updated bindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000565 return state->makeWithStore(B.getRoot());
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000566}
567
568//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +0000569// getLValueXXX methods.
570//===----------------------------------------------------------------------===//
571
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000572/// getLValueString - Returns an SVal representing the lvalue of a
573/// StringLiteral. Within RegionStore a StringLiteral has an
574/// associated StringRegion, and the lvalue of a StringLiteral is the
575/// lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000576SVal RegionStoreManager::getLValueString(const StringLiteral* S) {
Zhongxing Xu143bf822008-10-25 14:18:57 +0000577 return loc::MemRegionVal(MRMgr.getStringRegion(S));
578}
579
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000580/// getLValueVar - Returns an SVal that represents the lvalue of a
581/// variable. Within RegionStore a variable has an associated
582/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000583SVal RegionStoreManager::getLValueVar(const VarDecl *VD,
Ted Kremenekd17da2b2009-08-21 22:28:32 +0000584 const LocationContext *LC) {
585 return loc::MemRegionVal(MRMgr.getVarRegion(VD, LC));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000586}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000587
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000588/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
589/// of a compound literal. Within RegionStore a compound literal
590/// has an associated region, and the lvalue of the compound literal
591/// is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000592SVal
593RegionStoreManager::getLValueCompoundLiteral(const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000594 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
595}
596
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000597SVal RegionStoreManager::getLValueIvar(const ObjCIvarDecl* D, SVal Base) {
598 return getLValueFieldOrIvar(D, Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000599}
600
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000601SVal RegionStoreManager::getLValueField(const FieldDecl* D, SVal Base) {
602 return getLValueFieldOrIvar(D, Base);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000603}
604
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000605SVal RegionStoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000606 if (Base.isUnknownOrUndef())
607 return Base;
608
609 Loc BaseL = cast<Loc>(Base);
610 const MemRegion* BaseR = 0;
611
612 switch (BaseL.getSubKind()) {
613 case loc::MemRegionKind:
614 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
615 break;
616
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000617 case loc::GotoLabelKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000618 // These are anormal cases. Flag an undefined value.
619 return UndefinedVal();
620
621 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000622 // While these seem funny, this can happen through casts.
623 // FIXME: What we should return is the field offset. For example,
624 // add the field offset to the integer value. That way funny things
625 // like this work properly: &(((struct foo *) 0xa)->f)
626 return Base;
627
628 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000629 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000630 return Base;
631 }
Mike Stump1eb44332009-09-09 15:08:12 +0000632
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000633 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
634 // of FieldDecl.
635 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
636 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000637
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000638 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000639}
640
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000641SVal RegionStoreManager::getLValueElement(QualType elementType, SVal Offset,
642 SVal Base) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000643
Ted Kremenekde7ec632009-03-09 22:44:49 +0000644 // If the base is an unknown or undefined value, just return it back.
645 // FIXME: For absolute pointer addresses, we just return that value back as
646 // well, although in reality we should return the offset added to that
647 // value.
648 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000649 return Base;
650
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000651 // Only handle integer offsets... for now.
652 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000653 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000654
Zhongxing Xuce760782009-05-09 13:20:07 +0000655 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000656
657 // Pointer of any type can be cast and used as array base.
658 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
Mike Stump1eb44332009-09-09 15:08:12 +0000659
Ted Kremenek46537392009-07-16 01:33:37 +0000660 // Convert the offset to the appropriate size and signedness.
661 Offset = ValMgr.convertToArrayIndex(Offset);
Mike Stump1eb44332009-09-09 15:08:12 +0000662
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000663 if (!ElemR) {
664 //
665 // If the base region is not an ElementRegion, create one.
666 // This can happen in the following example:
667 //
668 // char *p = __builtin_alloc(10);
669 // p[1] = 8;
670 //
Zhongxing Xuce760782009-05-09 13:20:07 +0000671 // Observe that 'p' binds to an AllocaRegion.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000672 //
Ted Kremenekf936f452009-05-04 06:18:28 +0000673 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000674 BaseRegion, getContext()));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000675 }
Mike Stump1eb44332009-09-09 15:08:12 +0000676
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000677 SVal BaseIdx = ElemR->getIndex();
Mike Stump1eb44332009-09-09 15:08:12 +0000678
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000679 if (!isa<nonloc::ConcreteInt>(BaseIdx))
680 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000681
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000682 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
683 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
684 assert(BaseIdxI.isSigned());
Mike Stump1eb44332009-09-09 15:08:12 +0000685
Ted Kremenek46537392009-07-16 01:33:37 +0000686 // Compute the new index.
687 SVal NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Mike Stump1eb44332009-09-09 15:08:12 +0000688
Ted Kremenek46537392009-07-16 01:33:37 +0000689 // Construct the new ElementRegion.
690 const MemRegion *ArrayR = ElemR->getSuperRegion();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000691 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
Mike Stump1eb44332009-09-09 15:08:12 +0000692 getContext()));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000693}
694
Ted Kremenek9af46f52009-06-16 22:36:44 +0000695//===----------------------------------------------------------------------===//
696// Extents for regions.
697//===----------------------------------------------------------------------===//
698
Ted Kremenek67f28532009-06-17 22:02:04 +0000699SVal RegionStoreManager::getSizeInElements(const GRState *state,
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000700 const MemRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +0000701
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000702 switch (R->getKind()) {
703 case MemRegion::MemSpaceRegionKind:
704 assert(0 && "Cannot index into a MemSpace");
Mike Stump1eb44332009-09-09 15:08:12 +0000705 return UnknownVal();
706
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000707 case MemRegion::CodeTextRegionKind:
708 // Technically this can happen if people do funny things with casts.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000709 return UnknownVal();
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000710
711 // Not yet handled.
712 case MemRegion::AllocaRegionKind:
713 case MemRegion::CompoundLiteralRegionKind:
714 case MemRegion::ElementRegionKind:
715 case MemRegion::FieldRegionKind:
716 case MemRegion::ObjCIvarRegionKind:
717 case MemRegion::ObjCObjectRegionKind:
718 case MemRegion::SymbolicRegionKind:
719 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000720
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000721 case MemRegion::StringRegionKind: {
722 const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral();
Mike Stump1eb44332009-09-09 15:08:12 +0000723 // We intentionally made the size value signed because it participates in
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000724 // operations with signed indices.
725 return ValMgr.makeIntVal(Str->getByteLength()+1, false);
Ted Kremenek14553ab2009-01-30 00:08:43 +0000726 }
Mike Stump1eb44332009-09-09 15:08:12 +0000727
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000728 case MemRegion::VarRegionKind: {
729 const VarRegion* VR = cast<VarRegion>(R);
730 // Get the type of the variable.
731 QualType T = VR->getDesugaredValueType(getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000732
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000733 // FIXME: Handle variable-length arrays.
734 if (isa<VariableArrayType>(T))
735 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000736
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000737 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
738 // return the size as signed integer.
739 return ValMgr.makeIntVal(CAT->getSize(), false);
740 }
Ted Kremenekdf74e252009-08-02 05:15:23 +0000741
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000742 // Clients can use ordinary variables as if they were arrays. These
743 // essentially are arrays of size 1.
744 return ValMgr.makeIntVal(1, false);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000745 }
Mike Stump1eb44332009-09-09 15:08:12 +0000746
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000747 case MemRegion::BEG_DECL_REGIONS:
748 case MemRegion::END_DECL_REGIONS:
749 case MemRegion::BEG_TYPED_REGIONS:
750 case MemRegion::END_TYPED_REGIONS:
751 assert(0 && "Infeasible region");
752 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000753 }
Mike Stump1eb44332009-09-09 15:08:12 +0000754
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000755 assert(0 && "Unreachable");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000756 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000757}
758
Ted Kremenek67f28532009-06-17 22:02:04 +0000759const GRState *RegionStoreManager::setExtent(const GRState *state,
760 const MemRegion *region,
761 SVal extent) {
762 return state->set<RegionExtents>(region, extent);
Ted Kremenek9af46f52009-06-16 22:36:44 +0000763}
764
765//===----------------------------------------------------------------------===//
766// Location and region casting.
767//===----------------------------------------------------------------------===//
768
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000769/// ArrayToPointer - Emulates the "decay" of an array to a pointer
770/// type. 'Array' represents the lvalue of the array being decayed
771/// to a pointer, and the returned SVal represents the decayed
772/// version of that lvalue (i.e., a pointer to the first element of
773/// the array). This is called by GRExprEngine when evaluating casts
774/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000775SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000776 if (!isa<loc::MemRegionVal>(Array))
777 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000778
Ted Kremenekabb042f2008-12-13 19:24:37 +0000779 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
780 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000781
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000782 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000783 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000784
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000785 // Strip off typedefs from the ArrayRegion's ValueType.
John McCallbf1cc052009-09-29 23:03:30 +0000786 QualType T = ArrayR->getValueType(getContext()).getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000787 ArrayType *AT = cast<ArrayType>(T);
788 T = AT->getElementType();
Mike Stump1eb44332009-09-09 15:08:12 +0000789
Ted Kremenek75185b52009-07-16 00:00:11 +0000790 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
791 ElementRegion* ER = MRMgr.getElementRegion(T, ZeroIdx, ArrayR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000792
793 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000794}
795
Ted Kremenek9af46f52009-06-16 22:36:44 +0000796//===----------------------------------------------------------------------===//
797// Pointer arithmetic.
798//===----------------------------------------------------------------------===//
799
Mike Stump1eb44332009-09-09 15:08:12 +0000800SVal RegionStoreManager::EvalBinOp(const GRState *state,
Ted Kremenek5c734622009-06-26 00:41:43 +0000801 BinaryOperator::Opcode Op, Loc L, NonLoc R,
802 QualType resultTy) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000803 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000804 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000805 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000806
Zhongxing Xua1718c72009-04-03 07:33:13 +0000807 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000808 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000809
Ted Kremenek3bccf082009-07-11 00:58:27 +0000810 switch (MR->getKind()) {
811 case MemRegion::SymbolicRegionKind: {
812 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000813 SymbolRef Sym = SR->getSymbol();
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000814 QualType T = Sym->getType(getContext());
815 QualType EleTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000816
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000817 if (const PointerType *PT = T->getAs<PointerType>())
818 EleTy = PT->getPointeeType();
819 else
John McCall183700f2009-09-21 23:43:11 +0000820 EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000821
Ted Kremenek3bccf082009-07-11 00:58:27 +0000822 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
823 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000824 break;
Zhongxing Xu005f07b2009-06-19 04:51:14 +0000825 }
Ted Kremenek3bccf082009-07-11 00:58:27 +0000826 case MemRegion::AllocaRegionKind: {
Ted Kremenek3bccf082009-07-11 00:58:27 +0000827 const AllocaRegion *AR = cast<AllocaRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000828 QualType T = getContext().CharTy; // Create an ElementRegion of bytes.
Ted Kremenek6217b802009-07-29 21:53:49 +0000829 QualType EleTy = T->getAs<PointerType>()->getPointeeType();
Ted Kremenek3bccf082009-07-11 00:58:27 +0000830 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
831 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000832 break;
Ted Kremenek3bccf082009-07-11 00:58:27 +0000833 }
Zhongxing Xua1718c72009-04-03 07:33:13 +0000834
Ted Kremenek3bccf082009-07-11 00:58:27 +0000835 case MemRegion::ElementRegionKind: {
836 ER = cast<ElementRegion>(MR);
837 break;
838 }
Mike Stump1eb44332009-09-09 15:08:12 +0000839
Ted Kremenek3bccf082009-07-11 00:58:27 +0000840 // Not yet handled.
841 case MemRegion::VarRegionKind:
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000842 case MemRegion::StringRegionKind: {
843
844 }
845 // Fall-through.
Ted Kremenek3bccf082009-07-11 00:58:27 +0000846 case MemRegion::CompoundLiteralRegionKind:
847 case MemRegion::FieldRegionKind:
848 case MemRegion::ObjCObjectRegionKind:
849 case MemRegion::ObjCIvarRegionKind:
850 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000851
Ted Kremenek3bccf082009-07-11 00:58:27 +0000852 case MemRegion::CodeTextRegionKind:
853 // Technically this can happen if people do funny things with casts.
854 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000855
Ted Kremenek3bccf082009-07-11 00:58:27 +0000856 case MemRegion::MemSpaceRegionKind:
857 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
858 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000859
Ted Kremenek3bccf082009-07-11 00:58:27 +0000860 case MemRegion::BEG_DECL_REGIONS:
861 case MemRegion::END_DECL_REGIONS:
862 case MemRegion::BEG_TYPED_REGIONS:
863 case MemRegion::END_TYPED_REGIONS:
864 assert(0 && "Infeasible region");
865 return UnknownVal();
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000866 }
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000867
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000868 SVal Idx = ER->getIndex();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000869 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000870
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000871 // For now, only support:
872 // (a) concrete integer indices that can easily be resolved
873 // (b) 0 + symbolic index
874 if (Base) {
875 if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) {
876 // FIXME: Should use SValuator here.
877 SVal NewIdx =
878 Base->evalBinOp(ValMgr, Op,
Ted Kremenek46537392009-07-16 01:33:37 +0000879 cast<nonloc::ConcreteInt>(ValMgr.convertToArrayIndex(*Offset)));
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000880 const MemRegion* NewER =
881 MRMgr.getElementRegion(ER->getElementType(), NewIdx,
882 ER->getSuperRegion(), getContext());
883 return ValMgr.makeLoc(NewER);
884 }
885 if (0 == Base->getValue()) {
886 const MemRegion* NewER =
887 MRMgr.getElementRegion(ER->getElementType(), R,
888 ER->getSuperRegion(), getContext());
889 return ValMgr.makeLoc(NewER);
890 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000891 }
Mike Stump1eb44332009-09-09 15:08:12 +0000892
Ted Kremenek5dc27462009-03-03 02:51:43 +0000893 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000894}
895
Ted Kremenek9af46f52009-06-16 22:36:44 +0000896//===----------------------------------------------------------------------===//
897// Loading values from regions.
898//===----------------------------------------------------------------------===//
899
Zhongxing Xu13d50172009-10-11 08:08:02 +0000900Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
901 const MemRegion *R) {
902 if (const BindingVal *BV = B.lookup(R))
903 return Optional<SVal>::create(BV->getDirectValue());
904
905 return Optional<SVal>();
906}
907
908Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000909 const MemRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +0000910
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000911 if (R->isBoundable())
912 if (const TypedRegion *TR = dyn_cast<TypedRegion>(R))
913 if (TR->getValueType(getContext())->isUnionType())
914 return UnknownVal();
915
Zhongxing Xu13d50172009-10-11 08:08:02 +0000916 if (BindingVal const *V = B.lookup(R))
917 return Optional<SVal>::create(V->getDefaultValue());
918
919 return Optional<SVal>();
920}
921
922Optional<SVal> RegionStoreManager::getBinding(RegionBindings B,
923 const MemRegion *R) {
924 if (const BindingVal *BV = B.lookup(R))
925 return Optional<SVal>::create(BV->getValue());
926
927 return Optional<SVal>();
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000928}
929
Ted Kremeneka6275a52009-07-15 02:31:43 +0000930static bool IsReinterpreted(QualType RTy, QualType UsedTy, ASTContext &Ctx) {
931 RTy = Ctx.getCanonicalType(RTy);
932 UsedTy = Ctx.getCanonicalType(UsedTy);
Mike Stump1eb44332009-09-09 15:08:12 +0000933
Ted Kremeneka6275a52009-07-15 02:31:43 +0000934 if (RTy == UsedTy)
935 return false;
Mike Stump1eb44332009-09-09 15:08:12 +0000936
937
Ted Kremenek25c54572009-07-20 22:58:02 +0000938 // Recursively check the types. We basically want to see if a pointer value
Mike Stump1eb44332009-09-09 15:08:12 +0000939 // is ever reinterpreted as a non-pointer, e.g. void** and intptr_t*
Ted Kremenek25c54572009-07-20 22:58:02 +0000940 // represents a reinterpretation.
941 if (Loc::IsLocType(RTy) && Loc::IsLocType(UsedTy)) {
Mike Stump1eb44332009-09-09 15:08:12 +0000942 const PointerType *PRTy = RTy->getAs<PointerType>();
Ted Kremenek6217b802009-07-29 21:53:49 +0000943 const PointerType *PUsedTy = UsedTy->getAs<PointerType>();
Ted Kremenek25c54572009-07-20 22:58:02 +0000944
945 return PUsedTy && PRTy &&
946 IsReinterpreted(PRTy->getPointeeType(),
Mike Stump1eb44332009-09-09 15:08:12 +0000947 PUsedTy->getPointeeType(), Ctx);
Ted Kremenek25c54572009-07-20 22:58:02 +0000948 }
949
950 return true;
Ted Kremeneka6275a52009-07-15 02:31:43 +0000951}
952
Ted Kremenek0954cde2009-09-24 04:11:44 +0000953const ElementRegion *
954RegionStoreManager::GetElementZeroRegion(const SymbolicRegion *SR, QualType T) {
955 ASTContext &Ctx = getContext();
956 SVal idx = ValMgr.makeZeroArrayIndex();
957 assert(!T.isNull());
958 return MRMgr.getElementRegion(T, idx, SR, Ctx);
959}
960
961
962
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000963SValuator::CastResult
964RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
Ted Kremenek67f28532009-06-17 22:02:04 +0000965
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000966 assert(!isa<UnknownVal>(L) && "location unknown");
967 assert(!isa<UndefinedVal>(L) && "location undefined");
968
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000969 // FIXME: Is this even possible? Shouldn't this be treated as a null
970 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000971 if (isa<loc::ConcreteInt>(L))
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000972 return SValuator::CastResult(state, UndefinedVal());
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000973
Ted Kremenek67f28532009-06-17 22:02:04 +0000974 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000975
Zhongxing Xu91844122009-05-20 09:18:48 +0000976 // FIXME: return symbolic value for these cases.
Zhongxing Xua1718c72009-04-03 07:33:13 +0000977 // Example:
978 // void f(int* p) { int x = *p; }
Zhongxing Xu91844122009-05-20 09:18:48 +0000979 // char* p = alloca();
980 // read(p);
981 // c = *p;
Ted Kremenek60fbe8f2009-07-14 20:48:22 +0000982 if (isa<AllocaRegion>(MR))
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000983 return SValuator::CastResult(state, UnknownVal());
Mike Stump1eb44332009-09-09 15:08:12 +0000984
Ted Kremenek0954cde2009-09-24 04:11:44 +0000985 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
986 MR = GetElementZeroRegion(SR, T);
Mike Stump1eb44332009-09-09 15:08:12 +0000987
Ted Kremenek968f0a62009-08-03 21:41:46 +0000988 if (isa<CodeTextRegion>(MR))
989 return SValuator::CastResult(state, UnknownVal());
Mike Stump1eb44332009-09-09 15:08:12 +0000990
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000991 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
992 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Ted Kremenek67f28532009-06-17 22:02:04 +0000993 const TypedRegion *R = cast<TypedRegion>(MR);
Ted Kremeneka6275a52009-07-15 02:31:43 +0000994 QualType RTy = R->getValueType(getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000995
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000996 // FIXME: We should eventually handle funny addressing. e.g.:
997 //
998 // int x = ...;
999 // int *p = &x;
1000 // char *q = (char*) p;
1001 // char c = *q; // returns the first byte of 'x'.
1002 //
1003 // Such funny addressing will occur due to layering of regions.
1004
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001005#if 0
Ted Kremeneka6275a52009-07-15 02:31:43 +00001006 ASTContext &Ctx = getContext();
1007 if (!T.isNull() && IsReinterpreted(RTy, T, Ctx)) {
Ted Kremenek46537392009-07-16 01:33:37 +00001008 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
1009 R = MRMgr.getElementRegion(T, ZeroIdx, R, Ctx);
Ted Kremeneka6275a52009-07-15 02:31:43 +00001010 RTy = T;
Ted Kremenek41fb0df2009-07-15 04:23:32 +00001011 assert(Ctx.getCanonicalType(RTy) ==
1012 Ctx.getCanonicalType(R->getValueType(Ctx)));
Mike Stump1eb44332009-09-09 15:08:12 +00001013 }
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001014#endif
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001015
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001016 if (RTy->isStructureType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001017 return SValuator::CastResult(state, RetrieveStruct(state, R));
Mike Stump1eb44332009-09-09 15:08:12 +00001018
Ted Kremenekd4e5a602009-08-06 21:43:54 +00001019 // FIXME: Handle unions.
1020 if (RTy->isUnionType())
1021 return SValuator::CastResult(state, UnknownVal());
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001022
1023 if (RTy->isArrayType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001024 return SValuator::CastResult(state, RetrieveArray(state, R));
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001025
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001026 // FIXME: handle Vector types.
1027 if (RTy->isVectorType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001028 return SValuator::CastResult(state, UnknownVal());
Zhongxing Xu99c20302009-06-28 14:16:39 +00001029
1030 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001031 return CastRetrievedVal(RetrieveField(state, FR), state, FR, T);
Zhongxing Xu99c20302009-06-28 14:16:39 +00001032
1033 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001034 return CastRetrievedVal(RetrieveElement(state, ER), state, ER, T);
Mike Stump1eb44332009-09-09 15:08:12 +00001035
Ted Kremenek25c54572009-07-20 22:58:02 +00001036 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001037 return CastRetrievedVal(RetrieveObjCIvar(state, IVR), state, IVR, T);
Mike Stump1eb44332009-09-09 15:08:12 +00001038
Ted Kremenek9031dd72009-07-21 00:12:07 +00001039 if (const VarRegion *VR = dyn_cast<VarRegion>(R))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001040 return CastRetrievedVal(RetrieveVar(state, VR), state, VR, T);
Ted Kremenek25c54572009-07-20 22:58:02 +00001041
Ted Kremenek451ac092009-08-06 04:50:20 +00001042 RegionBindings B = GetRegionBindings(state->getStore());
1043 RegionBindings::data_type* V = B.lookup(R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001044
1045 // Check if the region has a binding.
1046 if (V)
Zhongxing Xu13d50172009-10-11 08:08:02 +00001047 if (SVal const *SV = V->getValue())
1048 return SValuator::CastResult(state, *SV);
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001049
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001050 // The location does not have a bound value. This means that it has
1051 // the value it had upon its creation and/or entry to the analyzed
1052 // function/method. These are either symbolic values or 'undefined'.
1053
Ted Kremenek356e9d62009-07-22 04:35:42 +00001054#if HEAP_UNDEFINED
Ted Kremenekbb7c96f2009-06-23 18:17:08 +00001055 if (R->hasHeapOrStackStorage()) {
Ted Kremenek356e9d62009-07-22 04:35:42 +00001056#else
1057 if (R->hasStackStorage()) {
1058#endif
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001059 // All stack variables are considered to have undefined values
1060 // upon creation. All heap allocated blocks are considered to
1061 // have undefined values as well unless they are explicitly bound
1062 // to specific values.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001063 return SValuator::CastResult(state, UndefinedVal());
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001064 }
1065
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001066 // All other values are symbolic.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001067 return SValuator::CastResult(state,
1068 ValMgr.getRegionValueSymbolValOrUnknown(R, RTy));
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001069}
Mike Stump1eb44332009-09-09 15:08:12 +00001070
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001071std::pair<const GRState*, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +00001072RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001073 if (Optional<SVal> OV = getDirectBinding(B, R))
1074 if (const nonloc::LazyCompoundVal *V =
1075 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
1076 return std::make_pair(V->getState(), V->getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001077
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001078 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1079 const std::pair<const GRState *, const MemRegion *> &X =
1080 GetLazyBinding(B, ER->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001081
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001082 if (X.first)
1083 return std::make_pair(X.first,
1084 MRMgr.getElementRegionWithSuper(ER, X.second));
Mike Stump1eb44332009-09-09 15:08:12 +00001085 }
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001086 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1087 const std::pair<const GRState *, const MemRegion *> &X =
1088 GetLazyBinding(B, FR->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001089
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001090 if (X.first)
1091 return std::make_pair(X.first,
1092 MRMgr.getFieldRegionWithSuper(FR, X.second));
1093 }
1094
1095 return std::make_pair((const GRState*) 0, (const MemRegion *) 0);
1096}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001097
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001098SVal RegionStoreManager::RetrieveElement(const GRState* state,
1099 const ElementRegion* R) {
1100 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001101 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001102 if (Optional<SVal> V = getDirectBinding(B, R))
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001103 return *V;
1104
Ted Kremenek921109a2009-07-01 23:19:52 +00001105 const MemRegion* superR = R->getSuperRegion();
1106
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001107 // Check if the region is an element region of a string literal.
Ted Kremenek921109a2009-07-01 23:19:52 +00001108 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001109 // FIXME: Handle loads from strings where the literal is treated as
1110 // an integer, e.g., *((unsigned int*)"hello")
1111 ASTContext &Ctx = getContext();
Douglas Gregor89c49f02009-11-09 22:08:55 +00001112 QualType T = Ctx.getAsArrayType(StrR->getValueType(Ctx))->getElementType();
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001113 if (T != Ctx.getCanonicalType(R->getElementType()))
1114 return UnknownVal();
1115
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001116 const StringLiteral *Str = StrR->getStringLiteral();
1117 SVal Idx = R->getIndex();
1118 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1119 int64_t i = CI->getValue().getSExtValue();
Mike Stump1eb44332009-09-09 15:08:12 +00001120 int64_t byteLength = Str->getByteLength();
Ted Kremenek0667db32009-09-05 17:59:01 +00001121 if (i > byteLength) {
1122 // Buffer overflow checking in GRExprEngine should handle this case,
1123 // but we shouldn't rely on it to not overflow here if that checking
1124 // is disabled.
1125 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001126 }
Ted Kremenek0667db32009-09-05 17:59:01 +00001127 char c = (i == byteLength) ? '\0' : Str->getStrData()[i];
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001128 return ValMgr.makeIntVal(c, T);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001129 }
1130 }
Mike Stump1eb44332009-09-09 15:08:12 +00001131
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001132 // Check if the immediate super region has a direct binding.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001133 if (Optional<SVal> V = getDirectBinding(B, superR)) {
Ted Kremeneka6275a52009-07-15 02:31:43 +00001134 if (SymbolRef parentSym = V->getAsSymbol())
1135 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenek356e9d62009-07-22 04:35:42 +00001136
1137 if (V->isUnknownOrUndef())
1138 return *V;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001139
1140 // Handle LazyCompoundVals for the immediate super region. Other cases
1141 // are handled in 'RetrieveFieldOrElementCommon'.
Mike Stump1eb44332009-09-09 15:08:12 +00001142 if (const nonloc::LazyCompoundVal *LCV =
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001143 dyn_cast<nonloc::LazyCompoundVal>(V)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001144
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001145 R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion());
1146 return RetrieveElement(LCV->getState(), R);
1147 }
Mike Stump1eb44332009-09-09 15:08:12 +00001148
Ted Kremeneka6275a52009-07-15 02:31:43 +00001149 // Other cases: give up.
Zhongxing Xu8834af32009-07-03 06:11:41 +00001150 return UnknownVal();
Zhongxing Xu7abe0192009-06-30 12:32:59 +00001151 }
Zhongxing Xu13d50172009-10-11 08:08:02 +00001152
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001153 return RetrieveFieldOrElementCommon(state, R, R->getElementType(), superR);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001154}
1155
Mike Stump1eb44332009-09-09 15:08:12 +00001156SVal RegionStoreManager::RetrieveField(const GRState* state,
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001157 const FieldRegion* R) {
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001158
1159 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001160 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001161 if (Optional<SVal> V = getDirectBinding(B, R))
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001162 return *V;
1163
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001164 QualType Ty = R->getValueType(getContext());
1165 return RetrieveFieldOrElementCommon(state, R, Ty, R->getSuperRegion());
1166}
Mike Stump1eb44332009-09-09 15:08:12 +00001167
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001168SVal RegionStoreManager::RetrieveFieldOrElementCommon(const GRState *state,
1169 const TypedRegion *R,
1170 QualType Ty,
1171 const MemRegion *superR) {
1172
Mike Stump1eb44332009-09-09 15:08:12 +00001173 // At this point we have already checked in either RetrieveElement or
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001174 // RetrieveField if 'R' has a direct binding.
Mike Stump1eb44332009-09-09 15:08:12 +00001175
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001176 RegionBindings B = GetRegionBindings(state->getStore());
Mike Stump1eb44332009-09-09 15:08:12 +00001177
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001178 while (superR) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001179 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001180 if (SymbolRef parentSym = D->getAsSymbol())
1181 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001182
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001183 if (D->isZeroConstant())
1184 return ValMgr.makeZeroVal(Ty);
Mike Stump1eb44332009-09-09 15:08:12 +00001185
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001186 if (D->isUnknown())
1187 return *D;
Mike Stump1eb44332009-09-09 15:08:12 +00001188
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001189 assert(0 && "Unknown default value");
1190 }
Mike Stump1eb44332009-09-09 15:08:12 +00001191
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001192 // If our super region is a field or element itself, walk up the region
1193 // hierarchy to see if there is a default value installed in an ancestor.
1194 if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) {
1195 superR = cast<SubRegion>(superR)->getSuperRegion();
1196 continue;
1197 }
Mike Stump1eb44332009-09-09 15:08:12 +00001198
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001199 break;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001200 }
Mike Stump1eb44332009-09-09 15:08:12 +00001201
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001202 // Lazy binding?
1203 const GRState *lazyBindingState = NULL;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001204 const MemRegion *lazyBindingRegion = NULL;
1205 llvm::tie(lazyBindingState, lazyBindingRegion) = GetLazyBinding(B, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001206
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001207 if (lazyBindingState) {
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001208 assert(lazyBindingRegion && "Lazy-binding region not set");
Mike Stump1eb44332009-09-09 15:08:12 +00001209
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001210 if (isa<ElementRegion>(R))
1211 return RetrieveElement(lazyBindingState,
1212 cast<ElementRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001213
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001214 return RetrieveField(lazyBindingState,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001215 cast<FieldRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001216 }
1217
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001218 if (R->hasStackStorage() && !R->hasParametersStorage()) {
Mike Stump1eb44332009-09-09 15:08:12 +00001219
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001220 if (isa<ElementRegion>(R)) {
1221 // Currently we don't reason specially about Clang-style vectors. Check
1222 // if superR is a vector and if so return Unknown.
1223 if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) {
1224 if (typedSuperR->getValueType(getContext())->isVectorType())
1225 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001226 }
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001227 }
Mike Stump1eb44332009-09-09 15:08:12 +00001228
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001229 return UndefinedVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001230 }
Mike Stump1eb44332009-09-09 15:08:12 +00001231
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001232 // All other values are symbolic.
1233 return ValMgr.getRegionValueSymbolValOrUnknown(R, Ty);
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001234}
Mike Stump1eb44332009-09-09 15:08:12 +00001235
1236SVal RegionStoreManager::RetrieveObjCIvar(const GRState* state,
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001237 const ObjCIvarRegion* R) {
1238
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001239 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001240 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001241
Zhongxing Xu13d50172009-10-11 08:08:02 +00001242 if (Optional<SVal> V = getDirectBinding(B, R))
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001243 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001244
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001245 const MemRegion *superR = R->getSuperRegion();
1246
Ted Kremenekab22ee92009-10-20 01:20:57 +00001247 // Check if the super region has a default binding.
1248 if (Optional<SVal> V = getDefaultBinding(B, superR)) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001249 if (SymbolRef parentSym = V->getAsSymbol())
1250 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001251
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001252 // Other cases: give up.
1253 return UnknownVal();
1254 }
Mike Stump1eb44332009-09-09 15:08:12 +00001255
Ted Kremenek25c54572009-07-20 22:58:02 +00001256 return RetrieveLazySymbol(state, R);
1257}
1258
Ted Kremenek9031dd72009-07-21 00:12:07 +00001259SVal RegionStoreManager::RetrieveVar(const GRState *state,
1260 const VarRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001261
Ted Kremenek9031dd72009-07-21 00:12:07 +00001262 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001263 RegionBindings B = GetRegionBindings(state->getStore());
Mike Stump1eb44332009-09-09 15:08:12 +00001264
Zhongxing Xu13d50172009-10-11 08:08:02 +00001265 if (Optional<SVal> V = getDirectBinding(B, R))
Ted Kremenek9031dd72009-07-21 00:12:07 +00001266 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001267
Ted Kremenek9031dd72009-07-21 00:12:07 +00001268 // Lazily derive a value for the VarRegion.
1269 const VarDecl *VD = R->getDecl();
Mike Stump1eb44332009-09-09 15:08:12 +00001270
Ted Kremenek9031dd72009-07-21 00:12:07 +00001271 if (R->hasGlobalsOrParametersStorage())
1272 return ValMgr.getRegionValueSymbolValOrUnknown(R, VD->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00001273
Ted Kremenek9031dd72009-07-21 00:12:07 +00001274 return UndefinedVal();
1275}
1276
Mike Stump1eb44332009-09-09 15:08:12 +00001277SVal RegionStoreManager::RetrieveLazySymbol(const GRState *state,
Ted Kremenek25c54572009-07-20 22:58:02 +00001278 const TypedRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001279
Ted Kremenek25c54572009-07-20 22:58:02 +00001280 QualType valTy = R->getValueType(getContext());
Ted Kremenek356e9d62009-07-22 04:35:42 +00001281
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001282 // All other values are symbolic.
Ted Kremenek25c54572009-07-20 22:58:02 +00001283 return ValMgr.getRegionValueSymbolValOrUnknown(R, valTy);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001284}
1285
Mike Stump1eb44332009-09-09 15:08:12 +00001286SVal RegionStoreManager::RetrieveStruct(const GRState *state,
1287 const TypedRegion* R) {
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001288 QualType T = R->getValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001289 assert(T->isStructureType());
1290
Zhongxing Xub7507d12009-06-11 07:27:30 +00001291 const RecordType* RT = T->getAsStructureType();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001292 RecordDecl* RD = RT->getDecl();
1293 assert(RD->isDefinition());
Mike Stump1aeb2472009-08-06 12:56:50 +00001294 (void)RD;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001295#if USE_EXPLICIT_COMPOUND
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001296 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
1297
Ted Kremenek67f28532009-06-17 22:02:04 +00001298 // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a
1299 // reverse iterator, we should implement one.
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001300 std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end());
Douglas Gregor44b43212008-12-11 16:49:14 +00001301
Douglas Gregore267ff32008-12-11 20:41:00 +00001302 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
1303 FieldEnd = Fields.rend();
1304 Field != FieldEnd; ++Field) {
1305 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001306 QualType FTy = (*Field)->getType();
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001307 SVal FieldValue = Retrieve(state, loc::MemRegionVal(FR), FTy).getSVal();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001308 StructVal = getBasicVals().consVals(FieldValue, StructVal);
1309 }
1310
Zhongxing Xud91ee272009-06-23 09:02:15 +00001311 return ValMgr.makeCompoundVal(T, StructVal);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001312#else
1313 return ValMgr.makeLazyCompoundVal(state, R);
1314#endif
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001315}
1316
Ted Kremenek67f28532009-06-17 22:02:04 +00001317SVal RegionStoreManager::RetrieveArray(const GRState *state,
1318 const TypedRegion * R) {
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001319#if USE_EXPLICIT_COMPOUND
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001320 QualType T = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001321 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1322
1323 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
Ted Kremenek46537392009-07-16 01:33:37 +00001324 uint64_t size = CAT->getSize().getZExtValue();
1325 for (uint64_t i = 0; i < size; ++i) {
1326 SVal Idx = ValMgr.makeArrayIndex(i);
Zhongxing Xu143b2fc2009-06-16 09:55:50 +00001327 ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
Mike Stump1eb44332009-09-09 15:08:12 +00001328 getContext());
Ted Kremenekf936f452009-05-04 06:18:28 +00001329 QualType ETy = ER->getElementType();
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001330 SVal ElementVal = Retrieve(state, loc::MemRegionVal(ER), ETy).getSVal();
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001331 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
1332 }
1333
Zhongxing Xud91ee272009-06-23 09:02:15 +00001334 return ValMgr.makeCompoundVal(T, ArrayVal);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001335#else
1336 assert(isa<ConstantArrayType>(R->getValueType(getContext())));
1337 return ValMgr.makeLazyCompoundVal(state, R);
1338#endif
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001339}
1340
Ted Kremenek9af46f52009-06-16 22:36:44 +00001341//===----------------------------------------------------------------------===//
1342// Binding values to regions.
1343//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +00001344
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001345Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +00001346 const MemRegion* R = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001347
Ted Kremenek0964a062009-01-21 06:57:53 +00001348 if (isa<loc::MemRegionVal>(L))
1349 R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001350
Ted Kremenek0964a062009-01-21 06:57:53 +00001351 if (R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001352 RegionBindings B = GetRegionBindings(store);
Ted Kremenek0964a062009-01-21 06:57:53 +00001353 return RBFactory.Remove(B, R).getRoot();
1354 }
Mike Stump1eb44332009-09-09 15:08:12 +00001355
Ted Kremenek0964a062009-01-21 06:57:53 +00001356 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001357}
1358
Ted Kremenek67f28532009-06-17 22:02:04 +00001359const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +00001360 if (isa<loc::ConcreteInt>(L))
1361 return state;
1362
Ted Kremenek9af46f52009-06-16 22:36:44 +00001363 // If we get here, the location should be a region.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001364 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001365
Ted Kremenek9af46f52009-06-16 22:36:44 +00001366 // Check if the region is a struct region.
1367 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
1368 if (TR->getValueType(getContext())->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001369 return BindStruct(state, TR, V);
Mike Stump1eb44332009-09-09 15:08:12 +00001370
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001371 // Special case: the current region represents a cast and it and the super
1372 // region both have pointer types or intptr_t types. If so, perform the
1373 // bind to the super region.
1374 // This is needed to support OSAtomicCompareAndSwap and friends or other
Mike Stump1eb44332009-09-09 15:08:12 +00001375 // loads that treat integers as pointers and vis versa.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001376 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1377 if (ER->getIndex().isZeroConstant()) {
1378 if (const TypedRegion *superR =
1379 dyn_cast<TypedRegion>(ER->getSuperRegion())) {
1380 ASTContext &Ctx = getContext();
1381 QualType superTy = superR->getValueType(Ctx);
1382 QualType erTy = ER->getValueType(Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +00001383
1384 if (IsAnyPointerOrIntptr(superTy, Ctx) &&
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001385 IsAnyPointerOrIntptr(erTy, Ctx)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001386 SValuator::CastResult cr =
1387 ValMgr.getSValuator().EvalCast(V, state, superTy, erTy);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001388 return Bind(cr.getState(), loc::MemRegionVal(superR), cr.getSVal());
1389 }
Ted Kremenek69181a82009-09-21 22:58:52 +00001390 // For now, just invalidate the fields of the struct/union/class.
1391 // FIXME: Precisely handle the fields of the record.
1392 if (superTy->isRecordType())
Ted Kremenek473e1672009-10-16 00:30:49 +00001393 return InvalidateRegion(state, superR, NULL, 0, NULL);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001394 }
1395 }
1396 }
Ted Kremenek0954cde2009-09-24 04:11:44 +00001397 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1398 // Binding directly to a symbolic region should be treated as binding
1399 // to element 0.
1400 QualType T = SR->getSymbol()->getType(getContext());
Ted Kremenek35dcad82009-09-24 06:24:32 +00001401 T = T->getAs<PointerType>()->getPointeeType();
Ted Kremenek0954cde2009-09-24 04:11:44 +00001402 R = GetElementZeroRegion(SR, T);
1403 }
Mike Stump1eb44332009-09-09 15:08:12 +00001404
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001405 // Perform the binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001406 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001407 return state->makeWithStore(
1408 RBFactory.Add(B, R, BindingVal(V, BindingVal::Direct)).getRoot());
Ted Kremenek9af46f52009-06-16 22:36:44 +00001409}
1410
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001411const GRState *RegionStoreManager::BindDecl(const GRState *ST,
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001412 const VarRegion *VR,
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001413 SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +00001414
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001415 QualType T = VR->getDecl()->getType();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001416
Ted Kremenek0964a062009-01-21 06:57:53 +00001417 if (T->isArrayType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001418 return BindArray(ST, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +00001419 if (T->isStructureType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001420 return BindStruct(ST, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001421
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001422 return Bind(ST, ValMgr.makeLoc(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001423}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001424
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001425// FIXME: this method should be merged into Bind().
Ted Kremenek67f28532009-06-17 22:02:04 +00001426const GRState *
1427RegionStoreManager::BindCompoundLiteral(const GRState *state,
1428 const CompoundLiteralExpr* CL,
1429 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001430
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001431 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Ted Kremenek67f28532009-06-17 22:02:04 +00001432 return Bind(state, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001433}
1434
Ted Kremenek67f28532009-06-17 22:02:04 +00001435const GRState *RegionStoreManager::BindArray(const GRState *state,
Ted Kremenek46537392009-07-16 01:33:37 +00001436 const TypedRegion* R,
Ted Kremenek67f28532009-06-17 22:02:04 +00001437 SVal Init) {
1438
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001439 QualType T = R->getValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001440 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001441 QualType ElementTy = CAT->getElementType();
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001442
Ted Kremenek46537392009-07-16 01:33:37 +00001443 uint64_t size = CAT->getSize().getZExtValue();
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001444
1445 // Check if the init expr is a StringLiteral.
1446 if (isa<loc::MemRegionVal>(Init)) {
1447 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1448 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1449 const char* str = S->getStrData();
1450 unsigned len = S->getByteLength();
1451 unsigned j = 0;
1452
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001453 // Copy bytes from the string literal into the target array. Trailing bytes
1454 // in the array that are not covered by the string literal are initialized
1455 // to zero.
Ted Kremenek46537392009-07-16 01:33:37 +00001456 for (uint64_t i = 0; i < size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001457 if (j >= len)
1458 break;
1459
Ted Kremenek46537392009-07-16 01:33:37 +00001460 SVal Idx = ValMgr.makeArrayIndex(i);
1461 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R,
1462 getContext());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001463
Zhongxing Xud91ee272009-06-23 09:02:15 +00001464 SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true);
Ted Kremenek67f28532009-06-17 22:02:04 +00001465 state = Bind(state, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001466 }
1467
Ted Kremenek67f28532009-06-17 22:02:04 +00001468 return state;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001469 }
1470
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001471 // Handle lazy compound values.
1472 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
1473 return CopyLazyBindings(*LCV, state, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001474
1475 // Remaining case: explicit compound values.
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001476 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001477 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Ted Kremenek46537392009-07-16 01:33:37 +00001478 uint64_t i = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001479
Ted Kremenek46537392009-07-16 01:33:37 +00001480 for (; i < size; ++i, ++VI) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001481 // The init list might be shorter than the array length.
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001482 if (VI == VE)
1483 break;
1484
Ted Kremenek46537392009-07-16 01:33:37 +00001485 SVal Idx = ValMgr.makeArrayIndex(i);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001486 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001487
1488 if (CAT->getElementType()->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001489 state = BindStruct(state, ER, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001490 else
Ted Kremenekcf549592009-09-22 21:19:14 +00001491 // FIXME: Do we need special handling of nested arrays?
Zhongxing Xud91ee272009-06-23 09:02:15 +00001492 state = Bind(state, ValMgr.makeLoc(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001493 }
1494
Zhongxing Xue3a765f2009-06-24 00:56:31 +00001495 // If the init list is shorter than the array length, set the array default
1496 // value.
Ted Kremenek46537392009-07-16 01:33:37 +00001497 if (i < size) {
Zhongxing Xue3a765f2009-06-24 00:56:31 +00001498 if (ElementTy->isIntegerType()) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001499 SVal V = ValMgr.makeZeroVal(ElementTy);
Zhongxing Xu13d50172009-10-11 08:08:02 +00001500 Store store = state->getStore();
1501 RegionBindings B = GetRegionBindings(store);
1502 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
1503 state = state->makeWithStore(B.getRoot());
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001504 }
1505 }
1506
Ted Kremenek67f28532009-06-17 22:02:04 +00001507 return state;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001508}
1509
Ted Kremenek67f28532009-06-17 22:02:04 +00001510const GRState *
1511RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R,
1512 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001513
Ted Kremenek67f28532009-06-17 22:02:04 +00001514 if (!Features.supportsFields())
1515 return state;
Mike Stump1eb44332009-09-09 15:08:12 +00001516
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001517 QualType T = R->getValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001518 assert(T->isStructureType());
1519
Ted Kremenek6217b802009-07-29 21:53:49 +00001520 const RecordType* RT = T->getAs<RecordType>();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001521 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001522
1523 if (!RD->isDefinition())
Ted Kremenek67f28532009-06-17 22:02:04 +00001524 return state;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001525
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001526 // Handle lazy compound values.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001527 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001528 return CopyLazyBindings(*LCV, state, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001529
Ted Kremenek67f28532009-06-17 22:02:04 +00001530 // We may get non-CompoundVal accidentally due to imprecise cast logic.
1531 // Ignore them and kill the field values.
1532 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
Zhongxing Xu13d50172009-10-11 08:08:02 +00001533 return state->makeWithStore(KillStruct(state->getStore(), R));
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001534
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001535 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001536 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001537
1538 RecordDecl::field_iterator FI, FE;
1539
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001540 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001541
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001542 if (VI == VE)
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001543 break;
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001544
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001545 QualType FTy = (*FI)->getType();
Ted Kremenekcf549592009-09-22 21:19:14 +00001546 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001547
Ted Kremenekcf549592009-09-22 21:19:14 +00001548 if (FTy->isArrayType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001549 state = BindArray(state, FR, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001550 else if (FTy->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001551 state = BindStruct(state, FR, *VI);
Ted Kremenekcf549592009-09-22 21:19:14 +00001552 else
1553 state = Bind(state, ValMgr.makeLoc(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001554 }
1555
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001556 // There may be fewer values in the initialize list than the fields of struct.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001557 if (FI != FE) {
1558 Store store = state->getStore();
1559 RegionBindings B = GetRegionBindings(store);
1560 B = RBFactory.Add(B, R,
1561 BindingVal(ValMgr.makeIntVal(0, false), BindingVal::Default));
1562 state = state->makeWithStore(B.getRoot());
1563 }
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001564
Ted Kremenek67f28532009-06-17 22:02:04 +00001565 return state;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001566}
1567
Zhongxing Xu13d50172009-10-11 08:08:02 +00001568Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R) {
1569 RegionBindings B = GetRegionBindings(store);
1570 llvm::OwningPtr<RegionStoreSubRegionMap>
1571 SubRegions(getRegionStoreSubRegionMap(store));
1572 RemoveSubRegionBindings(B, R, *SubRegions);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001573
Zhongxing Xue4df9c42009-06-25 05:52:16 +00001574 // Set the default value of the struct region to "unknown".
Zhongxing Xu13d50172009-10-11 08:08:02 +00001575 B = RBFactory.Add(B, R, BindingVal(UnknownVal(), BindingVal::Default));
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001576
Zhongxing Xu13d50172009-10-11 08:08:02 +00001577 return B.getRoot();
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001578}
1579
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001580const GRState*
1581RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1582 const GRState *state,
1583 const TypedRegion *R) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001584
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001585 // Nuke the old bindings stemming from R.
Ted Kremenek451ac092009-08-06 04:50:20 +00001586 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001587
Mike Stump1eb44332009-09-09 15:08:12 +00001588 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +00001589 SubRegions(getRegionStoreSubRegionMap(state->getStore()));
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001590
Mike Stump1eb44332009-09-09 15:08:12 +00001591 // B and DVM are updated after the call to RemoveSubRegionBindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001592 RemoveSubRegionBindings(B, R, *SubRegions.get());
Mike Stump1eb44332009-09-09 15:08:12 +00001593
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001594 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1595 // results in a zero-copy algorithm.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001596 return state->makeWithStore(
1597 RBFactory.Add(B, R, BindingVal(V, BindingVal::Direct)).getRoot());
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001598}
Mike Stump1eb44332009-09-09 15:08:12 +00001599
Ted Kremenek9af46f52009-06-16 22:36:44 +00001600//===----------------------------------------------------------------------===//
1601// State pruning.
1602//===----------------------------------------------------------------------===//
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001603
Mike Stump1eb44332009-09-09 15:08:12 +00001604void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc,
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001605 SymbolReaper& SymReaper,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001606 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +00001607{
Ted Kremenek781115c2009-10-17 17:45:11 +00001608 typedef std::pair<const GRState*, const MemRegion *> RBDNode;
1609
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001610 Store store = state.getStore();
Ted Kremenek451ac092009-08-06 04:50:20 +00001611 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001612
Ted Kremenek9af46f52009-06-16 22:36:44 +00001613 // The backmap from regions to subregions.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001614 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +00001615 SubRegions(getRegionStoreSubRegionMap(store));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001616
1617 // Do a pass over the regions in the store. For VarRegions we check if
1618 // the variable is still live and if so add it to the list of live roots.
1619 // For other regions we populate our region backmap.
Ted Kremenek9af46f52009-06-16 22:36:44 +00001620 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001621
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001622 // Scan the direct bindings for "intermediate" roots.
Ted Kremenek451ac092009-08-06 04:50:20 +00001623 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001624 const MemRegion *R = I.getKey();
1625 IntermediateRoots.push_back(R);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001626 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001627
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001628 // Process the "intermediate" roots to find if they are referenced by
Mike Stump1eb44332009-09-09 15:08:12 +00001629 // real roots.
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001630 llvm::SmallVector<RBDNode, 10> WorkList;
Ted Kremenek01756192009-10-29 05:14:17 +00001631 llvm::SmallVector<RBDNode, 10> Postponed;
1632
Zhongxing Xu6800b332009-10-18 04:15:47 +00001633 llvm::DenseSet<const MemRegion*> IntermediateVisited;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001634
Ted Kremenek9af46f52009-06-16 22:36:44 +00001635 while (!IntermediateRoots.empty()) {
1636 const MemRegion* R = IntermediateRoots.back();
1637 IntermediateRoots.pop_back();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001638
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001639 if (IntermediateVisited.count(R))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001640 continue;
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001641 IntermediateVisited.insert(R);
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001642
Ted Kremenek9af46f52009-06-16 22:36:44 +00001643 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001644 if (SymReaper.isLive(Loc, VR->getDecl()))
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001645 WorkList.push_back(std::make_pair(&state, VR));
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001646 continue;
1647 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001648
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001649 if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
Ted Kremenek01756192009-10-29 05:14:17 +00001650 llvm::SmallVectorImpl<RBDNode> &Q =
1651 SymReaper.isLive(SR->getSymbol()) ? WorkList : Postponed;
1652
1653 Q.push_back(std::make_pair(&state, SR));
1654
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001655 continue;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001656 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001657
1658 // Add the super region for R to the worklist if it is a subregion.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001659 if (const SubRegion* superR =
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001660 dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion()))
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001661 IntermediateRoots.push_back(superR);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001662 }
Mike Stump1eb44332009-09-09 15:08:12 +00001663
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001664 // Enqueue the RegionRoots onto WorkList.
1665 for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(),
1666 E=RegionRoots.end(); I!=E; ++I) {
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001667 WorkList.push_back(std::make_pair(&state, *I));
Mike Stump1eb44332009-09-09 15:08:12 +00001668 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001669 RegionRoots.clear();
1670
Zhongxing Xu6800b332009-10-18 04:15:47 +00001671 llvm::DenseSet<RBDNode> Visited;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001672
Ted Kremenek01756192009-10-29 05:14:17 +00001673tryAgain:
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001674 while (!WorkList.empty()) {
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001675 RBDNode N = WorkList.back();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001676 WorkList.pop_back();
1677
1678 // Have we visited this node before?
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001679 if (Visited.count(N))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001680 continue;
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001681 Visited.insert(N);
Mike Stump1eb44332009-09-09 15:08:12 +00001682
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001683 const MemRegion *R = N.second;
1684 const GRState *state_N = N.first;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001685
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001686 // Enqueue subregions.
1687 RegionStoreSubRegionMap *M;
1688
1689 if (&state == state_N)
1690 M = SubRegions.get();
1691 else {
1692 RegionStoreSubRegionMap *& SM = SC[state_N];
1693 if (!SM)
1694 SM = getRegionStoreSubRegionMap(state_N->getStore());
1695 M = SM;
1696 }
1697
1698 RegionStoreSubRegionMap::iterator I, E;
1699 for (llvm::tie(I, E) = M->begin_end(R); I != E; ++I)
1700 WorkList.push_back(std::make_pair(state_N, *I));
1701
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001702 // Enqueue the super region.
1703 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1704 const MemRegion *superR = SR->getSuperRegion();
1705 if (!isa<MemSpaceRegion>(superR)) {
1706 // If 'R' is a field or an element, we want to keep the bindings
1707 // for the other fields and elements around. The reason is that
Zhongxing Xu13d50172009-10-11 08:08:02 +00001708 // pointer arithmetic can get us to the other fields or elements.
Zhongxing Xu8801beb2009-10-17 07:32:08 +00001709 assert(isa<FieldRegion>(R) || isa<ElementRegion>(R)
1710 || isa<ObjCIvarRegion>(R));
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001711 WorkList.push_back(std::make_pair(state_N, superR));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001712 }
1713 }
1714
1715 // Mark the symbol for any live SymbolicRegion as "live". This means we
1716 // should continue to track that symbol.
1717 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1718 SymReaper.markLive(SymR->getSymbol());
1719
1720 Store store_N = state_N->getStore();
1721 RegionBindings B_N = GetRegionBindings(store_N);
1722
1723 // Get the data binding for R (if any).
Zhongxing Xu13d50172009-10-11 08:08:02 +00001724 Optional<SVal> V = getBinding(B_N, R);
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001725
Zhongxing Xu13d50172009-10-11 08:08:02 +00001726 if (V) {
1727 // Check for lazy bindings.
1728 if (const nonloc::LazyCompoundVal *LCV =
1729 dyn_cast<nonloc::LazyCompoundVal>(V.getPointer())) {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001730
Zhongxing Xu13d50172009-10-11 08:08:02 +00001731 const LazyCompoundValData *D = LCV->getCVData();
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001732 WorkList.push_back(std::make_pair(D->getState(), D->getRegion()));
Zhongxing Xu13d50172009-10-11 08:08:02 +00001733 }
1734 else {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001735 // Update the set of live symbols.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001736 for (SVal::symbol_iterator SI=V->symbol_begin(), SE=V->symbol_end();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001737 SI!=SE;++SI)
1738 SymReaper.markLive(*SI);
1739
Zhongxing Xu13d50172009-10-11 08:08:02 +00001740 // If V is a region, then add it to the worklist.
1741 if (const MemRegion *RX = V->getAsRegion())
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001742 WorkList.push_back(std::make_pair(state_N, RX));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001743 }
1744 }
1745 }
1746
Ted Kremenek01756192009-10-29 05:14:17 +00001747 // See if any postponed SymbolicRegions are actually live now, after
1748 // having done a scan.
1749 for (llvm::SmallVectorImpl<RBDNode>::iterator I = Postponed.begin(),
1750 E = Postponed.end() ; I != E ; ++I) {
1751 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(I->second)) {
1752 if (SymReaper.isLive(SR->getSymbol())) {
1753 WorkList.push_back(*I);
1754 I->second = NULL;
1755 }
1756 }
1757 }
1758
1759 if (!WorkList.empty())
1760 goto tryAgain;
1761
Ted Kremenek9af46f52009-06-16 22:36:44 +00001762 // We have now scanned the store, marking reachable regions and symbols
1763 // as live. We now remove all the regions that are dead from the store
Mike Stump1eb44332009-09-09 15:08:12 +00001764 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenek451ac092009-08-06 04:50:20 +00001765 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001766 const MemRegion* R = I.getKey();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001767 // If this region live? Is so, none of its symbols are dead.
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001768 if (Visited.count(std::make_pair(&state, R)))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001769 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001770
Ted Kremenek9af46f52009-06-16 22:36:44 +00001771 // Remove this dead region from the store.
Zhongxing Xud91ee272009-06-23 09:02:15 +00001772 store = Remove(store, ValMgr.makeLoc(R));
Mike Stump1eb44332009-09-09 15:08:12 +00001773
Ted Kremenek9af46f52009-06-16 22:36:44 +00001774 // Mark all non-live symbols that this region references as dead.
1775 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1776 SymReaper.maybeDead(SymR->getSymbol());
Mike Stump1eb44332009-09-09 15:08:12 +00001777
Zhongxing Xu13d50172009-10-11 08:08:02 +00001778 SVal X = *I.getData().getValue();
Ted Kremenek093569c2009-08-02 05:00:15 +00001779 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1780 for (; SI != SE; ++SI)
1781 SymReaper.maybeDead(*SI);
1782 }
Mike Stump1eb44332009-09-09 15:08:12 +00001783
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001784 // Write the store back.
1785 state.setStore(store);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001786}
1787
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001788GRState const *RegionStoreManager::EnterStackFrame(GRState const *state,
1789 StackFrameContext const *frame) {
1790 FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
1791 CallExpr const *CE = cast<CallExpr>(frame->getCallSite());
1792
1793 FunctionDecl::param_const_iterator PI = FD->param_begin();
1794
1795 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1796
1797 // Copy the arg expression value to the arg variables.
1798 for (; AI != AE; ++AI, ++PI) {
1799 SVal ArgVal = state->getSVal(*AI);
1800 MemRegion *R = MRMgr.getVarRegion(*PI, frame);
1801 state = Bind(state, ValMgr.makeLoc(R), ArgVal);
1802 }
1803
1804 return state;
1805}
1806
Ted Kremenek9af46f52009-06-16 22:36:44 +00001807//===----------------------------------------------------------------------===//
1808// Utility methods.
1809//===----------------------------------------------------------------------===//
1810
Ted Kremenek53ba0b62009-06-24 23:06:47 +00001811void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001812 const char* nl, const char *sep) {
Ted Kremenek451ac092009-08-06 04:50:20 +00001813 RegionBindings B = GetRegionBindings(store);
Ted Kremenekab22ee92009-10-20 01:20:57 +00001814 OS << "Store (direct and default bindings):" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +00001815
Ted Kremenek451ac092009-08-06 04:50:20 +00001816 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
Mike Stump1eb44332009-09-09 15:08:12 +00001817 OS << ' ' << I.getKey() << " : " << I.getData() << nl;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001818}