blob: 6c452c23dccac911fc9ce3b10923e9679aa9ef5e [file] [log] [blame]
Zhongxing Xu17892752008-10-08 02:50:44 +00001//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines a basic region store model. In this model, we do have field
11// sensitivity. But we assume nothing about the heap shape. So recursive data
12// structures are largely ignored. Basically we do 1-limiting analysis.
13// Parameter pointers are assumed with no aliasing. Pointee objects of
14// parameters are created lazily.
15//
16//===----------------------------------------------------------------------===//
17#include "clang/Analysis/PathSensitive/MemRegion.h"
Zhongxing Xu0b143312009-08-21 13:25:15 +000018#include "clang/Analysis/PathSensitive/AnalysisContext.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000019#include "clang/Analysis/PathSensitive/GRState.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000020#include "clang/Analysis/PathSensitive/GRStateTrait.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000021#include "clang/Analysis/Analyses/LiveVariables.h"
Ted Kremenekd4e5a602009-08-06 21:43:54 +000022#include "clang/Analysis/Support/Optional.h"
Zhongxing Xu41fd0182009-05-06 11:51:48 +000023#include "clang/Basic/TargetInfo.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000024
25#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000026#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000027#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000028
29using namespace clang;
30
Ted Kremenek356e9d62009-07-22 04:35:42 +000031#define HEAP_UNDEFINED 0
Ted Kremeneka5e81f12009-08-06 01:20:57 +000032#define USE_EXPLICIT_COMPOUND 0
Ted Kremenek356e9d62009-07-22 04:35:42 +000033
Zhongxing Xu13d50172009-10-11 08:08:02 +000034namespace {
35class BindingVal {
36public:
37 enum BindingKind { Direct, Default };
38private:
39 SVal Value;
40 BindingKind Kind;
41
42public:
43 BindingVal(SVal V, BindingKind K) : Value(V), Kind(K) {}
44
45 bool isDefault() const { return Kind == Default; }
46
47 const SVal *getValue() const { return &Value; }
48
49 const SVal *getDirectValue() const { return isDefault() ? 0 : &Value; }
50
51 const SVal *getDefaultValue() const { return isDefault() ? &Value : 0; }
52
53 void Profile(llvm::FoldingSetNodeID& ID) const {
54 Value.Profile(ID);
55 ID.AddInteger(Kind);
56 }
57
58 inline bool operator==(const BindingVal& R) const {
59 return Value == R.Value && Kind == R.Kind;
60 }
61
62 inline bool operator!=(const BindingVal& R) const {
63 return !(*this == R);
64 }
65};
66}
67
68namespace llvm {
69static inline
70llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingVal V) {
71 if (V.isDefault())
72 os << "(default) ";
73 else
74 os << "(direct) ";
75 os << *V.getValue();
76 return os;
77}
78} // end llvm namespace
79
Zhongxing Xubaf03a72008-11-24 09:44:56 +000080// Actual Store type.
Zhongxing Xu13d50172009-10-11 08:08:02 +000081typedef llvm::ImmutableMap<const MemRegion*, BindingVal> RegionBindings;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000082
Ted Kremenek50dc1b32008-12-24 01:05:03 +000083//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +000084// Fine-grained control of RegionStoreManager.
85//===----------------------------------------------------------------------===//
86
87namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000088struct minimal_features_tag {};
89struct maximal_features_tag {};
Mike Stump1eb44332009-09-09 15:08:12 +000090
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000091class RegionStoreFeatures {
Ted Kremenek9af46f52009-06-16 22:36:44 +000092 bool SupportsFields;
93 bool SupportsRemaining;
Mike Stump1eb44332009-09-09 15:08:12 +000094
Ted Kremenek9af46f52009-06-16 22:36:44 +000095public:
96 RegionStoreFeatures(minimal_features_tag) :
97 SupportsFields(false), SupportsRemaining(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +000098
Ted Kremenek9af46f52009-06-16 22:36:44 +000099 RegionStoreFeatures(maximal_features_tag) :
100 SupportsFields(true), SupportsRemaining(false) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000101
Ted Kremenek9af46f52009-06-16 22:36:44 +0000102 void enableFields(bool t) { SupportsFields = t; }
Mike Stump1eb44332009-09-09 15:08:12 +0000103
Ted Kremenek9af46f52009-06-16 22:36:44 +0000104 bool supportsFields() const { return SupportsFields; }
105 bool supportsRemaining() const { return SupportsRemaining; }
106};
107}
108
109//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000110// Region "Extents"
111//===----------------------------------------------------------------------===//
112//
113// MemRegions represent chunks of memory with a size (their "extent"). This
114// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000115//
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000116namespace { class RegionExtents {}; }
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000117static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000118namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000119 template<> struct GRStateTrait<RegionExtents>
120 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
121 static void* GDMIndex() { return &RegionExtentsIndex; }
122 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000123}
124
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000125//===----------------------------------------------------------------------===//
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000126// Utility functions.
127//===----------------------------------------------------------------------===//
128
129static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) {
130 if (ty->isAnyPointerType())
131 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000132
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000133 return ty->isIntegerType() && ty->isScalarType() &&
134 Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy);
135}
136
137//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000138// Main RegionStore logic.
139//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000140
Zhongxing Xu17892752008-10-08 02:50:44 +0000141namespace {
Mike Stump1eb44332009-09-09 15:08:12 +0000142
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000143class RegionStoreSubRegionMap : public SubRegionMap {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000144 typedef llvm::ImmutableSet<const MemRegion*> SetTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000145 typedef llvm::DenseMap<const MemRegion*, SetTy> Map;
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000146 SetTy::Factory F;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000147 Map M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000148public:
Ted Kremenekd8c01922009-08-05 19:09:24 +0000149 bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000150 Map::iterator I = M.find(Parent);
Ted Kremenekd8c01922009-08-05 19:09:24 +0000151
152 if (I == M.end()) {
Ted Kremenek4ed45982009-08-05 05:31:02 +0000153 M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion)));
Ted Kremenekd8c01922009-08-05 19:09:24 +0000154 return true;
155 }
156
157 I->second = F.Add(I->second, SubRegion);
158 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000159 }
Mike Stump1eb44332009-09-09 15:08:12 +0000160
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000161 void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000162
Ted Kremenek59e8f112009-03-03 01:35:36 +0000163 ~RegionStoreSubRegionMap() {}
Mike Stump1eb44332009-09-09 15:08:12 +0000164
Ted Kremenek5dc27462009-03-03 02:51:43 +0000165 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +0000166 Map::const_iterator I = M.find(Parent);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000167
168 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000169 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000170
Ted Kremenek59e8f112009-03-03 01:35:36 +0000171 llvm::ImmutableSet<const MemRegion*> S = I->second;
172 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
173 SI != SE; ++SI) {
174 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000175 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000176 }
Mike Stump1eb44332009-09-09 15:08:12 +0000177
Ted Kremenek5dc27462009-03-03 02:51:43 +0000178 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000179 }
Mike Stump1eb44332009-09-09 15:08:12 +0000180
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000181 typedef SetTy::iterator iterator;
182
183 std::pair<iterator, iterator> begin_end(const MemRegion *R) {
184 Map::iterator I = M.find(R);
185 SetTy S = I == M.end() ? F.GetEmptySet() : I->second;
186 return std::make_pair(S.begin(), S.end());
187 }
Mike Stump1eb44332009-09-09 15:08:12 +0000188};
Ted Kremenek59e8f112009-03-03 01:35:36 +0000189
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000190class RegionStoreManager : public StoreManager {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000191 const RegionStoreFeatures Features;
Ted Kremenek451ac092009-08-06 04:50:20 +0000192 RegionBindings::Factory RBFactory;
Ted Kremenek9e17cc62009-09-29 06:35:00 +0000193
194 typedef llvm::DenseMap<const GRState *, RegionStoreSubRegionMap*> SMCache;
195 SMCache SC;
196
Zhongxing Xu17892752008-10-08 02:50:44 +0000197public:
Mike Stump1eb44332009-09-09 15:08:12 +0000198 RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
Ted Kremenekf7a0cf42009-07-29 21:43:22 +0000199 : StoreManager(mgr),
Ted Kremenek9af46f52009-06-16 22:36:44 +0000200 Features(f),
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000201 RBFactory(mgr.getAllocator()) {}
Zhongxing Xu17892752008-10-08 02:50:44 +0000202
Ted Kremenek9e17cc62009-09-29 06:35:00 +0000203 virtual ~RegionStoreManager() {
204 for (SMCache::iterator I = SC.begin(), E = SC.end(); I != E; ++I)
205 delete (*I).second;
206 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000207
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000208 SubRegionMap *getSubRegionMap(const GRState *state);
Mike Stump1eb44332009-09-09 15:08:12 +0000209
Zhongxing Xu13d50172009-10-11 08:08:02 +0000210 RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
Mike Stump1eb44332009-09-09 15:08:12 +0000211
Zhongxing Xu13d50172009-10-11 08:08:02 +0000212 Optional<SVal> getBinding(RegionBindings B, const MemRegion *R);
213 Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000214 /// getDefaultBinding - Returns an SVal* representing an optional default
215 /// binding associated with a region and its subregions.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000216 Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
Ted Kremenek027e2662009-11-19 20:20:24 +0000217
218 /// setImplicitDefaultValue - Set the default binding for the provided
219 /// MemRegion to the value implicitly defined for compound literals when
220 /// the value is not specified.
221 const GRState *setImplicitDefaultValue(const GRState *state,
222 const MemRegion *R,
223 QualType T);
Mike Stump1eb44332009-09-09 15:08:12 +0000224
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000225 /// getLValueString - Returns an SVal representing the lvalue of a
226 /// StringLiteral. Within RegionStore a StringLiteral has an
227 /// associated StringRegion, and the lvalue of a StringLiteral is
228 /// the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000229 SVal getLValueString(const StringLiteral* S);
Zhongxing Xu143bf822008-10-25 14:18:57 +0000230
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000231 /// getLValueCompoundLiteral - Returns an SVal representing the
232 /// lvalue of a compound literal. Within RegionStore a compound
233 /// literal has an associated region, and the lvalue of the
234 /// compound literal is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000235 SVal getLValueCompoundLiteral(const CompoundLiteralExpr*);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000236
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000237 /// getLValueVar - Returns an SVal that represents the lvalue of a
238 /// variable. Within RegionStore a variable has an associated
239 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000240 SVal getLValueVar(const VarDecl *VD, const LocationContext *LC);
Mike Stump1eb44332009-09-09 15:08:12 +0000241
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000242 SVal getLValueIvar(const ObjCIvarDecl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000243
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000244 SVal getLValueField(const FieldDecl* D, SVal Base);
Mike Stump1eb44332009-09-09 15:08:12 +0000245
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000246 SVal getLValueFieldOrIvar(const Decl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000247
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000248 SVal getLValueElement(QualType elementType, SVal Offset, SVal Base);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000249
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000250
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000251 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
252 /// type. 'Array' represents the lvalue of the array being decayed
253 /// to a pointer, and the returned SVal represents the decayed
254 /// version of that lvalue (i.e., a pointer to the first element of
255 /// the array). This is called by GRExprEngine when evaluating
256 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000257 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000258
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000259 SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L,
Ted Kremenek5c734622009-06-26 00:41:43 +0000260 NonLoc R, QualType resultTy);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000261
Mike Stump1eb44332009-09-09 15:08:12 +0000262 Store getInitialStore(const LocationContext *InitLoc) {
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000263 return RBFactory.GetEmptyMap().getRoot();
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000264 }
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000265
Ted Kremenek67f28532009-06-17 22:02:04 +0000266 //===-------------------------------------------------------------------===//
267 // Binding values to regions.
268 //===-------------------------------------------------------------------===//
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000269
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000270 const GRState *InvalidateRegion(const GRState *state, const MemRegion *R,
Ted Kremenek473e1672009-10-16 00:30:49 +0000271 const Expr *E, unsigned Count,
Ted Kremenek81a95832009-12-03 03:27:11 +0000272 InvalidatedSymbols *IS) {
273 return RegionStoreManager::InvalidateRegions(state, &R, &R+1, E, Count, IS);
274 }
275
276 const GRState *InvalidateRegions(const GRState *state,
277 const MemRegion * const *Begin,
278 const MemRegion * const *End,
279 const Expr *E, unsigned Count,
280 InvalidatedSymbols *IS);
Mike Stump1eb44332009-09-09 15:08:12 +0000281
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000282private:
Zhongxing Xu13d50172009-10-11 08:08:02 +0000283 void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000284 RegionStoreSubRegionMap &M);
Mike Stump1eb44332009-09-09 15:08:12 +0000285
286public:
Ted Kremenek67f28532009-06-17 22:02:04 +0000287 const GRState *Bind(const GRState *state, Loc LV, SVal V);
288
289 const GRState *BindCompoundLiteral(const GRState *state,
Zhongxing Xu13d50172009-10-11 08:08:02 +0000290 const CompoundLiteralExpr* CL, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000291
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000292 const GRState *BindDecl(const GRState *ST, const VarRegion *VR,
293 SVal InitVal);
Ted Kremenek67f28532009-06-17 22:02:04 +0000294
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000295 const GRState *BindDeclWithNoInit(const GRState *state,
296 const VarRegion *) {
Ted Kremenek67f28532009-06-17 22:02:04 +0000297 return state;
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000298 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000299
Ted Kremenek67f28532009-06-17 22:02:04 +0000300 /// BindStruct - Bind a compound value to a structure.
301 const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000302
Ted Kremenek67f28532009-06-17 22:02:04 +0000303 const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V);
Mike Stump1eb44332009-09-09 15:08:12 +0000304
305 /// KillStruct - Set the entire struct to unknown.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000306 Store KillStruct(Store store, const TypedRegion* R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000307
Ted Kremenek67f28532009-06-17 22:02:04 +0000308 Store Remove(Store store, Loc LV);
309
310 //===------------------------------------------------------------------===//
311 // Loading values from regions.
312 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000313
Ted Kremenek67f28532009-06-17 22:02:04 +0000314 /// The high level logic for this method is this:
315 /// Retrieve (L)
316 /// if L has binding
317 /// return L's binding
318 /// else if L is in killset
319 /// return unknown
320 /// else
321 /// if L is on stack or heap
322 /// return undefined
323 /// else
324 /// return symbolic
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000325 SValuator::CastResult Retrieve(const GRState *state, Loc L,
326 QualType T = QualType());
Zhongxing Xu490b0f02009-06-25 04:50:44 +0000327
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000328 SVal RetrieveElement(const GRState *state, const ElementRegion *R);
Zhongxing Xuc00346f2009-06-25 05:29:39 +0000329
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000330 SVal RetrieveField(const GRState *state, const FieldRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000331
Ted Kremenek5bd2fe32009-07-15 06:09:28 +0000332 SVal RetrieveObjCIvar(const GRState *state, const ObjCIvarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000333
Ted Kremenek9031dd72009-07-21 00:12:07 +0000334 SVal RetrieveVar(const GRState *state, const VarRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000335
Ted Kremenek25c54572009-07-20 22:58:02 +0000336 SVal RetrieveLazySymbol(const GRState *state, const TypedRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000337
Ted Kremenek566a6fa2009-08-06 22:33:36 +0000338 SVal RetrieveFieldOrElementCommon(const GRState *state, const TypedRegion *R,
339 QualType Ty, const MemRegion *superR);
Mike Stump1eb44332009-09-09 15:08:12 +0000340
Ted Kremenek67f28532009-06-17 22:02:04 +0000341 /// Retrieve the values in a struct and return a CompoundVal, used when doing
Mike Stump1eb44332009-09-09 15:08:12 +0000342 /// struct copy:
343 /// struct s x, y;
Ted Kremenek67f28532009-06-17 22:02:04 +0000344 /// x = y;
345 /// y's value is retrieved by this method.
346 SVal RetrieveStruct(const GRState *St, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000347
Ted Kremenek67f28532009-06-17 22:02:04 +0000348 SVal RetrieveArray(const GRState *St, const TypedRegion* R);
Mike Stump1eb44332009-09-09 15:08:12 +0000349
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000350 std::pair<const GRState*, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +0000351 GetLazyBinding(RegionBindings B, const MemRegion *R);
Mike Stump1eb44332009-09-09 15:08:12 +0000352
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000353 const GRState* CopyLazyBindings(nonloc::LazyCompoundVal V,
354 const GRState *state,
355 const TypedRegion *R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000356
Ted Kremenek0954cde2009-09-24 04:11:44 +0000357 const ElementRegion *GetElementZeroRegion(const SymbolicRegion *SR,
358 QualType T);
359
Ted Kremenek67f28532009-06-17 22:02:04 +0000360 //===------------------------------------------------------------------===//
361 // State pruning.
362 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000363
Ted Kremenek67f28532009-06-17 22:02:04 +0000364 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
365 /// It returns a new Store with these values removed.
Ted Kremenek2f26bc32009-08-02 04:45:08 +0000366 void RemoveDeadBindings(GRState &state, Stmt* Loc, SymbolReaper& SymReaper,
Ted Kremenek67f28532009-06-17 22:02:04 +0000367 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
368
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +0000369 const GRState *EnterStackFrame(const GRState *state,
370 const StackFrameContext *frame);
371
Ted Kremenek67f28532009-06-17 22:02:04 +0000372 //===------------------------------------------------------------------===//
373 // Region "extents".
374 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000375
Ted Kremenek67f28532009-06-17 22:02:04 +0000376 const GRState *setExtent(const GRState *state, const MemRegion* R, SVal Extent);
Zhongxing Xue884ff82009-11-12 02:48:32 +0000377 DefinedOrUnknownSVal getSizeInElements(const GRState *state,
378 const MemRegion* R);
Ted Kremenek67f28532009-06-17 22:02:04 +0000379
380 //===------------------------------------------------------------------===//
Ted Kremenek67f28532009-06-17 22:02:04 +0000381 // Utility methods.
382 //===------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000383
Ted Kremenek451ac092009-08-06 04:50:20 +0000384 static inline RegionBindings GetRegionBindings(Store store) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000385 return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000386 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000387
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000388 void print(Store store, llvm::raw_ostream& Out, const char* nl,
389 const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000390
391 void iterBindings(Store store, BindingsHandler& f) {
392 // FIXME: Implement.
393 }
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000394
Ted Kremenek67f28532009-06-17 22:02:04 +0000395 // FIXME: Remove.
396 BasicValueFactory& getBasicVals() {
397 return StateMgr.getBasicVals();
398 }
Mike Stump1eb44332009-09-09 15:08:12 +0000399
Ted Kremenek67f28532009-06-17 22:02:04 +0000400 // FIXME: Remove.
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000401 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xu17892752008-10-08 02:50:44 +0000402};
403
404} // end anonymous namespace
405
Ted Kremenek9af46f52009-06-16 22:36:44 +0000406//===----------------------------------------------------------------------===//
407// RegionStore creation.
408//===----------------------------------------------------------------------===//
409
410StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
411 RegionStoreFeatures F = maximal_features_tag();
412 return new RegionStoreManager(StMgr, F);
413}
414
415StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
416 RegionStoreFeatures F = minimal_features_tag();
417 F.enableFields(true);
418 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000419}
420
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000421void
422RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL,
Mike Stump1eb44332009-09-09 15:08:12 +0000423 const SubRegion *R) {
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000424 const MemRegion *superR = R->getSuperRegion();
425 if (add(superR, R))
426 if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
Mike Stump1eb44332009-09-09 15:08:12 +0000427 WL.push_back(sr);
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000428}
429
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000430RegionStoreSubRegionMap*
Zhongxing Xu13d50172009-10-11 08:08:02 +0000431RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
432 RegionBindings B = GetRegionBindings(store);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000433 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
Mike Stump1eb44332009-09-09 15:08:12 +0000434
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000435 llvm::SmallVector<const SubRegion*, 10> WL;
436
Ted Kremenek451ac092009-08-06 04:50:20 +0000437 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000438 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey()))
439 M->process(WL, R);
Mike Stump1eb44332009-09-09 15:08:12 +0000440
Mike Stump1eb44332009-09-09 15:08:12 +0000441 // We also need to record in the subregion map "intermediate" regions that
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000442 // don't have direct bindings but are super regions of those that do.
443 while (!WL.empty()) {
444 const SubRegion *R = WL.back();
445 WL.pop_back();
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000446 M->process(WL, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000447 }
448
Ted Kremenek14453bf2009-03-03 19:02:42 +0000449 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000450}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000451
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000452SubRegionMap *RegionStoreManager::getSubRegionMap(const GRState *state) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000453 return getRegionStoreSubRegionMap(state->getStore());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000454}
455
Ted Kremenek9af46f52009-06-16 22:36:44 +0000456//===----------------------------------------------------------------------===//
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000457// Binding invalidation.
458//===----------------------------------------------------------------------===//
459
Zhongxing Xu13d50172009-10-11 08:08:02 +0000460void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
461 const MemRegion *R,
462 RegionStoreSubRegionMap &M) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000463 RegionStoreSubRegionMap::iterator I, E;
464
465 for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I)
Zhongxing Xu13d50172009-10-11 08:08:02 +0000466 RemoveSubRegionBindings(B, *I, M);
Mike Stump1eb44332009-09-09 15:08:12 +0000467
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000468 B = RBFactory.Remove(B, R);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000469}
470
Ted Kremenek81a95832009-12-03 03:27:11 +0000471const GRState *RegionStoreManager::InvalidateRegions(const GRState *state,
472 const MemRegion * const *I,
473 const MemRegion * const *E,
474 const Expr *Ex,
475 unsigned Count,
476 InvalidatedSymbols *IS) {
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000477 ASTContext& Ctx = StateMgr.getContext();
Mike Stump1eb44332009-09-09 15:08:12 +0000478
Ted Kremenek87806792009-09-27 20:45:21 +0000479 // Get the mapping of regions -> subregions.
480 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +0000481 SubRegions(getRegionStoreSubRegionMap(state->getStore()));
Ted Kremenek87806792009-09-27 20:45:21 +0000482
483 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +0000484
Ted Kremenek87806792009-09-27 20:45:21 +0000485 llvm::DenseMap<const MemRegion *, unsigned> Visited;
486 llvm::SmallVector<const MemRegion *, 10> WorkList;
Ted Kremenek81a95832009-12-03 03:27:11 +0000487
488 for ( ; I != E; ++I) {
489 // Strip away casts.
490 WorkList.push_back((*I)->StripCasts());
491 }
Ted Kremenek87806792009-09-27 20:45:21 +0000492
493 while (!WorkList.empty()) {
Ted Kremenek81a95832009-12-03 03:27:11 +0000494 const MemRegion *R = WorkList.back();
Ted Kremenek87806792009-09-27 20:45:21 +0000495 WorkList.pop_back();
496
497 // Have we visited this region before?
498 unsigned &visited = Visited[R];
499 if (visited)
500 continue;
501 visited = 1;
Mike Stump1eb44332009-09-09 15:08:12 +0000502
Ted Kremenek87806792009-09-27 20:45:21 +0000503 // Add subregions to work list.
504 RegionStoreSubRegionMap::iterator I, E;
505 for (llvm::tie(I, E) = SubRegions->begin_end(R); I!=E; ++I)
506 WorkList.push_back(*I);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000507
508 // Get the old binding. Is it a region? If so, add it to the worklist.
509 if (Optional<SVal> V = getDirectBinding(B, R)) {
510 if (const MemRegion *RV = V->getAsRegion())
511 WorkList.push_back(RV);
Ted Kremenek473e1672009-10-16 00:30:49 +0000512
513 // A symbol? Mark it touched by the invalidation.
514 if (IS) {
515 if (SymbolRef Sym = V->getAsSymbol())
516 IS->insert(Sym);
517 }
Zhongxing Xu13d50172009-10-11 08:08:02 +0000518 }
519
Ted Kremenek473e1672009-10-16 00:30:49 +0000520 // Symbolic region? Mark that symbol touched by the invalidation.
521 if (IS) {
522 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
523 IS->insert(SR->getSymbol());
524 }
Ted Kremenek2ffbfd92009-12-03 08:25:47 +0000525
526 // BlockDataRegion? If so, invalidate captured variables that are passed
527 // by reference.
528 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
529 for (BlockDataRegion::referenced_vars_iterator
530 I = BR->referenced_vars_begin(), E = BR->referenced_vars_end() ;
531 I != E; ++I) {
532 const VarRegion *VR = *I;
533 if (VR->getDecl()->getAttr<BlocksAttr>())
534 WorkList.push_back(VR);
535 }
536 continue;
537 }
Ted Kremenek473e1672009-10-16 00:30:49 +0000538
539 // Handle the region itself.
Ted Kremenek87806792009-09-27 20:45:21 +0000540 if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R) ||
541 isa<ObjCObjectRegion>(R)) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000542 // Invalidate the region by setting its default value to
543 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek87806792009-09-27 20:45:21 +0000544 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
545 Count);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000546 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000547 continue;
548 }
Mike Stump1eb44332009-09-09 15:08:12 +0000549
Ted Kremenek87806792009-09-27 20:45:21 +0000550 if (!R->isBoundable())
551 continue;
552
553 const TypedRegion *TR = cast<TypedRegion>(R);
554 QualType T = TR->getValueType(Ctx);
555
556 if (const RecordType *RT = T->getAsStructureType()) {
Ted Kremenek87806792009-09-27 20:45:21 +0000557 const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx);
558
Zhongxing Xu13d50172009-10-11 08:08:02 +0000559 // No record definition. There is nothing we can do.
Ted Kremenek87806792009-09-27 20:45:21 +0000560 if (!RD)
561 continue;
562
Zhongxing Xu13d50172009-10-11 08:08:02 +0000563 // Invalidate the region by setting its default value to
564 // conjured symbol. The type of the symbol is irrelavant.
Ted Kremenek87806792009-09-27 20:45:21 +0000565 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
566 Count);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000567 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000568 continue;
569 }
570
571 if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
572 // Set the default value of the array to conjured symbol.
573 DefinedOrUnknownSVal V =
574 ValMgr.getConjuredSymbolVal(R, Ex, AT->getElementType(), Count);
Zhongxing Xu13d50172009-10-11 08:08:02 +0000575 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
Ted Kremenek87806792009-09-27 20:45:21 +0000576 continue;
577 }
Ted Kremeneka5971b32009-09-29 03:34:03 +0000578
579 if ((isa<FieldRegion>(R)||isa<ElementRegion>(R)||isa<ObjCIvarRegion>(R))
580 && Visited[cast<SubRegion>(R)->getSuperRegion()]) {
Zhongxing Xu13d50172009-10-11 08:08:02 +0000581 // For fields and elements whose super region has also been invalidated,
582 // only remove the old binding. The super region will get set with a
583 // default value from which we can lazily derive a new symbolic value.
Ted Kremeneka5971b32009-09-29 03:34:03 +0000584 B = RBFactory.Remove(B, R);
585 continue;
586 }
Ted Kremenek87806792009-09-27 20:45:21 +0000587
Ted Kremenek389c44c2009-09-29 03:12:50 +0000588 // Invalidate the binding.
Ted Kremenek87806792009-09-27 20:45:21 +0000589 DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, T, Count);
590 assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
Zhongxing Xu13d50172009-10-11 08:08:02 +0000591 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Direct));
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000592 }
593
Ted Kremenek87806792009-09-27 20:45:21 +0000594 // Create a new state with the updated bindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +0000595 return state->makeWithStore(B.getRoot());
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000596}
597
598//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +0000599// getLValueXXX methods.
600//===----------------------------------------------------------------------===//
601
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000602/// getLValueString - Returns an SVal representing the lvalue of a
603/// StringLiteral. Within RegionStore a StringLiteral has an
604/// associated StringRegion, and the lvalue of a StringLiteral is the
605/// lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000606SVal RegionStoreManager::getLValueString(const StringLiteral* S) {
Zhongxing Xu143bf822008-10-25 14:18:57 +0000607 return loc::MemRegionVal(MRMgr.getStringRegion(S));
608}
609
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000610/// getLValueVar - Returns an SVal that represents the lvalue of a
611/// variable. Within RegionStore a variable has an associated
612/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000613SVal RegionStoreManager::getLValueVar(const VarDecl *VD,
Ted Kremenekd17da2b2009-08-21 22:28:32 +0000614 const LocationContext *LC) {
615 return loc::MemRegionVal(MRMgr.getVarRegion(VD, LC));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000616}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000617
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000618/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
619/// of a compound literal. Within RegionStore a compound literal
620/// has an associated region, and the lvalue of the compound literal
621/// is the lvalue of that region.
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000622SVal
623RegionStoreManager::getLValueCompoundLiteral(const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000624 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
625}
626
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000627SVal RegionStoreManager::getLValueIvar(const ObjCIvarDecl* D, SVal Base) {
628 return getLValueFieldOrIvar(D, Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000629}
630
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000631SVal RegionStoreManager::getLValueField(const FieldDecl* D, SVal Base) {
632 return getLValueFieldOrIvar(D, Base);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000633}
634
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000635SVal RegionStoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000636 if (Base.isUnknownOrUndef())
637 return Base;
638
639 Loc BaseL = cast<Loc>(Base);
640 const MemRegion* BaseR = 0;
641
642 switch (BaseL.getSubKind()) {
643 case loc::MemRegionKind:
644 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
645 break;
646
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000647 case loc::GotoLabelKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000648 // These are anormal cases. Flag an undefined value.
649 return UndefinedVal();
650
651 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000652 // While these seem funny, this can happen through casts.
653 // FIXME: What we should return is the field offset. For example,
654 // add the field offset to the integer value. That way funny things
655 // like this work properly: &(((struct foo *) 0xa)->f)
656 return Base;
657
658 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000659 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000660 return Base;
661 }
Mike Stump1eb44332009-09-09 15:08:12 +0000662
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000663 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
664 // of FieldDecl.
665 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
666 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000667
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000668 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000669}
670
Zhongxing Xud0f8bb12009-10-14 03:33:08 +0000671SVal RegionStoreManager::getLValueElement(QualType elementType, SVal Offset,
672 SVal Base) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000673
Ted Kremenekde7ec632009-03-09 22:44:49 +0000674 // If the base is an unknown or undefined value, just return it back.
675 // FIXME: For absolute pointer addresses, we just return that value back as
676 // well, although in reality we should return the offset added to that
677 // value.
678 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000679 return Base;
680
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000681 // Only handle integer offsets... for now.
682 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000683 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000684
Zhongxing Xuce760782009-05-09 13:20:07 +0000685 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000686
687 // Pointer of any type can be cast and used as array base.
688 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
Mike Stump1eb44332009-09-09 15:08:12 +0000689
Ted Kremenek46537392009-07-16 01:33:37 +0000690 // Convert the offset to the appropriate size and signedness.
691 Offset = ValMgr.convertToArrayIndex(Offset);
Mike Stump1eb44332009-09-09 15:08:12 +0000692
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000693 if (!ElemR) {
694 //
695 // If the base region is not an ElementRegion, create one.
696 // This can happen in the following example:
697 //
698 // char *p = __builtin_alloc(10);
699 // p[1] = 8;
700 //
Zhongxing Xuce760782009-05-09 13:20:07 +0000701 // Observe that 'p' binds to an AllocaRegion.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000702 //
Ted Kremenekf936f452009-05-04 06:18:28 +0000703 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000704 BaseRegion, getContext()));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000705 }
Mike Stump1eb44332009-09-09 15:08:12 +0000706
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000707 SVal BaseIdx = ElemR->getIndex();
Mike Stump1eb44332009-09-09 15:08:12 +0000708
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000709 if (!isa<nonloc::ConcreteInt>(BaseIdx))
710 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000711
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000712 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
713 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
714 assert(BaseIdxI.isSigned());
Mike Stump1eb44332009-09-09 15:08:12 +0000715
Ted Kremenek46537392009-07-16 01:33:37 +0000716 // Compute the new index.
717 SVal NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Mike Stump1eb44332009-09-09 15:08:12 +0000718
Ted Kremenek46537392009-07-16 01:33:37 +0000719 // Construct the new ElementRegion.
720 const MemRegion *ArrayR = ElemR->getSuperRegion();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000721 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
Mike Stump1eb44332009-09-09 15:08:12 +0000722 getContext()));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000723}
724
Ted Kremenek9af46f52009-06-16 22:36:44 +0000725//===----------------------------------------------------------------------===//
726// Extents for regions.
727//===----------------------------------------------------------------------===//
728
Zhongxing Xue884ff82009-11-12 02:48:32 +0000729DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state,
730 const MemRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +0000731
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000732 switch (R->getKind()) {
733 case MemRegion::MemSpaceRegionKind:
734 assert(0 && "Cannot index into a MemSpace");
Mike Stump1eb44332009-09-09 15:08:12 +0000735 return UnknownVal();
736
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000737 case MemRegion::FunctionTextRegionKind:
738 case MemRegion::BlockTextRegionKind:
Ted Kremenek0a8112a2009-11-25 23:53:07 +0000739 case MemRegion::BlockDataRegionKind:
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000740 // Technically this can happen if people do funny things with casts.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000741 return UnknownVal();
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000742
743 // Not yet handled.
744 case MemRegion::AllocaRegionKind:
745 case MemRegion::CompoundLiteralRegionKind:
746 case MemRegion::ElementRegionKind:
747 case MemRegion::FieldRegionKind:
748 case MemRegion::ObjCIvarRegionKind:
749 case MemRegion::ObjCObjectRegionKind:
750 case MemRegion::SymbolicRegionKind:
751 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000752
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000753 case MemRegion::StringRegionKind: {
754 const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral();
Mike Stump1eb44332009-09-09 15:08:12 +0000755 // We intentionally made the size value signed because it participates in
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000756 // operations with signed indices.
757 return ValMgr.makeIntVal(Str->getByteLength()+1, false);
Ted Kremenek14553ab2009-01-30 00:08:43 +0000758 }
Mike Stump1eb44332009-09-09 15:08:12 +0000759
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000760 case MemRegion::VarRegionKind: {
761 const VarRegion* VR = cast<VarRegion>(R);
762 // Get the type of the variable.
763 QualType T = VR->getDesugaredValueType(getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000764
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000765 // FIXME: Handle variable-length arrays.
766 if (isa<VariableArrayType>(T))
767 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000768
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000769 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
770 // return the size as signed integer.
771 return ValMgr.makeIntVal(CAT->getSize(), false);
772 }
Ted Kremenekdf74e252009-08-02 05:15:23 +0000773
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000774 // Clients can use ordinary variables as if they were arrays. These
775 // essentially are arrays of size 1.
776 return ValMgr.makeIntVal(1, false);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000777 }
Mike Stump1eb44332009-09-09 15:08:12 +0000778
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000779 case MemRegion::BEG_DECL_REGIONS:
780 case MemRegion::END_DECL_REGIONS:
781 case MemRegion::BEG_TYPED_REGIONS:
782 case MemRegion::END_TYPED_REGIONS:
783 assert(0 && "Infeasible region");
784 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000785 }
Mike Stump1eb44332009-09-09 15:08:12 +0000786
Ted Kremenek7ecbfbc2009-07-10 22:30:06 +0000787 assert(0 && "Unreachable");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000788 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000789}
790
Ted Kremenek67f28532009-06-17 22:02:04 +0000791const GRState *RegionStoreManager::setExtent(const GRState *state,
792 const MemRegion *region,
793 SVal extent) {
794 return state->set<RegionExtents>(region, extent);
Ted Kremenek9af46f52009-06-16 22:36:44 +0000795}
796
797//===----------------------------------------------------------------------===//
798// Location and region casting.
799//===----------------------------------------------------------------------===//
800
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000801/// ArrayToPointer - Emulates the "decay" of an array to a pointer
802/// type. 'Array' represents the lvalue of the array being decayed
803/// to a pointer, and the returned SVal represents the decayed
804/// version of that lvalue (i.e., a pointer to the first element of
805/// the array). This is called by GRExprEngine when evaluating casts
806/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000807SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000808 if (!isa<loc::MemRegionVal>(Array))
809 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000810
Ted Kremenekabb042f2008-12-13 19:24:37 +0000811 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
812 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000813
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000814 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000815 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000816
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000817 // Strip off typedefs from the ArrayRegion's ValueType.
John McCallbf1cc052009-09-29 23:03:30 +0000818 QualType T = ArrayR->getValueType(getContext()).getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000819 ArrayType *AT = cast<ArrayType>(T);
820 T = AT->getElementType();
Mike Stump1eb44332009-09-09 15:08:12 +0000821
Ted Kremenek75185b52009-07-16 00:00:11 +0000822 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
823 ElementRegion* ER = MRMgr.getElementRegion(T, ZeroIdx, ArrayR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000824
825 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000826}
827
Ted Kremenek9af46f52009-06-16 22:36:44 +0000828//===----------------------------------------------------------------------===//
829// Pointer arithmetic.
830//===----------------------------------------------------------------------===//
831
Mike Stump1eb44332009-09-09 15:08:12 +0000832SVal RegionStoreManager::EvalBinOp(const GRState *state,
Ted Kremenek5c734622009-06-26 00:41:43 +0000833 BinaryOperator::Opcode Op, Loc L, NonLoc R,
834 QualType resultTy) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000835 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000836 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000837 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000838
Zhongxing Xua1718c72009-04-03 07:33:13 +0000839 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000840 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000841
Ted Kremenek3bccf082009-07-11 00:58:27 +0000842 switch (MR->getKind()) {
843 case MemRegion::SymbolicRegionKind: {
844 const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000845 SymbolRef Sym = SR->getSymbol();
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000846 QualType T = Sym->getType(getContext());
847 QualType EleTy;
Mike Stump1eb44332009-09-09 15:08:12 +0000848
Ted Kremenekbcf62a92009-08-25 22:55:09 +0000849 if (const PointerType *PT = T->getAs<PointerType>())
850 EleTy = PT->getPointeeType();
851 else
John McCall183700f2009-09-21 23:43:11 +0000852 EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000853
Ted Kremenek3bccf082009-07-11 00:58:27 +0000854 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
855 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000856 break;
Zhongxing Xu005f07b2009-06-19 04:51:14 +0000857 }
Ted Kremenek3bccf082009-07-11 00:58:27 +0000858 case MemRegion::AllocaRegionKind: {
Ted Kremenek3bccf082009-07-11 00:58:27 +0000859 const AllocaRegion *AR = cast<AllocaRegion>(MR);
Ted Kremenekdf74e252009-08-02 05:15:23 +0000860 QualType T = getContext().CharTy; // Create an ElementRegion of bytes.
Ted Kremenek6217b802009-07-29 21:53:49 +0000861 QualType EleTy = T->getAs<PointerType>()->getPointeeType();
Ted Kremenek3bccf082009-07-11 00:58:27 +0000862 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
863 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000864 break;
Ted Kremenek3bccf082009-07-11 00:58:27 +0000865 }
Zhongxing Xua1718c72009-04-03 07:33:13 +0000866
Ted Kremenek3bccf082009-07-11 00:58:27 +0000867 case MemRegion::ElementRegionKind: {
868 ER = cast<ElementRegion>(MR);
869 break;
870 }
Mike Stump1eb44332009-09-09 15:08:12 +0000871
Ted Kremenek3bccf082009-07-11 00:58:27 +0000872 // Not yet handled.
873 case MemRegion::VarRegionKind:
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000874 case MemRegion::StringRegionKind: {
875
876 }
877 // Fall-through.
Ted Kremenek3bccf082009-07-11 00:58:27 +0000878 case MemRegion::CompoundLiteralRegionKind:
879 case MemRegion::FieldRegionKind:
880 case MemRegion::ObjCObjectRegionKind:
881 case MemRegion::ObjCIvarRegionKind:
882 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000883
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000884 case MemRegion::FunctionTextRegionKind:
885 case MemRegion::BlockTextRegionKind:
Ted Kremenek0a8112a2009-11-25 23:53:07 +0000886 case MemRegion::BlockDataRegionKind:
Ted Kremenek3bccf082009-07-11 00:58:27 +0000887 // Technically this can happen if people do funny things with casts.
888 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000889
Ted Kremenek3bccf082009-07-11 00:58:27 +0000890 case MemRegion::MemSpaceRegionKind:
891 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
892 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000893
Ted Kremenek3bccf082009-07-11 00:58:27 +0000894 case MemRegion::BEG_DECL_REGIONS:
895 case MemRegion::END_DECL_REGIONS:
896 case MemRegion::BEG_TYPED_REGIONS:
897 case MemRegion::END_TYPED_REGIONS:
898 assert(0 && "Infeasible region");
899 return UnknownVal();
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000900 }
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000901
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000902 SVal Idx = ER->getIndex();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000903 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000904
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000905 // For now, only support:
906 // (a) concrete integer indices that can easily be resolved
907 // (b) 0 + symbolic index
908 if (Base) {
909 if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) {
910 // FIXME: Should use SValuator here.
911 SVal NewIdx =
912 Base->evalBinOp(ValMgr, Op,
Ted Kremenek46537392009-07-16 01:33:37 +0000913 cast<nonloc::ConcreteInt>(ValMgr.convertToArrayIndex(*Offset)));
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000914 const MemRegion* NewER =
915 MRMgr.getElementRegion(ER->getElementType(), NewIdx,
916 ER->getSuperRegion(), getContext());
917 return ValMgr.makeLoc(NewER);
918 }
919 if (0 == Base->getValue()) {
920 const MemRegion* NewER =
921 MRMgr.getElementRegion(ER->getElementType(), R,
922 ER->getSuperRegion(), getContext());
923 return ValMgr.makeLoc(NewER);
924 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000925 }
Mike Stump1eb44332009-09-09 15:08:12 +0000926
Ted Kremenek5dc27462009-03-03 02:51:43 +0000927 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000928}
929
Ted Kremenek9af46f52009-06-16 22:36:44 +0000930//===----------------------------------------------------------------------===//
931// Loading values from regions.
932//===----------------------------------------------------------------------===//
933
Zhongxing Xu13d50172009-10-11 08:08:02 +0000934Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
935 const MemRegion *R) {
936 if (const BindingVal *BV = B.lookup(R))
937 return Optional<SVal>::create(BV->getDirectValue());
938
939 return Optional<SVal>();
940}
941
942Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000943 const MemRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +0000944
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000945 if (R->isBoundable())
946 if (const TypedRegion *TR = dyn_cast<TypedRegion>(R))
947 if (TR->getValueType(getContext())->isUnionType())
948 return UnknownVal();
949
Zhongxing Xu13d50172009-10-11 08:08:02 +0000950 if (BindingVal const *V = B.lookup(R))
951 return Optional<SVal>::create(V->getDefaultValue());
952
953 return Optional<SVal>();
954}
955
956Optional<SVal> RegionStoreManager::getBinding(RegionBindings B,
957 const MemRegion *R) {
958 if (const BindingVal *BV = B.lookup(R))
959 return Optional<SVal>::create(BV->getValue());
960
961 return Optional<SVal>();
Ted Kremenekd4e5a602009-08-06 21:43:54 +0000962}
963
Ted Kremeneka6275a52009-07-15 02:31:43 +0000964static bool IsReinterpreted(QualType RTy, QualType UsedTy, ASTContext &Ctx) {
965 RTy = Ctx.getCanonicalType(RTy);
966 UsedTy = Ctx.getCanonicalType(UsedTy);
Mike Stump1eb44332009-09-09 15:08:12 +0000967
Ted Kremeneka6275a52009-07-15 02:31:43 +0000968 if (RTy == UsedTy)
969 return false;
Mike Stump1eb44332009-09-09 15:08:12 +0000970
971
Ted Kremenek25c54572009-07-20 22:58:02 +0000972 // Recursively check the types. We basically want to see if a pointer value
Mike Stump1eb44332009-09-09 15:08:12 +0000973 // is ever reinterpreted as a non-pointer, e.g. void** and intptr_t*
Ted Kremenek25c54572009-07-20 22:58:02 +0000974 // represents a reinterpretation.
975 if (Loc::IsLocType(RTy) && Loc::IsLocType(UsedTy)) {
Mike Stump1eb44332009-09-09 15:08:12 +0000976 const PointerType *PRTy = RTy->getAs<PointerType>();
Ted Kremenek6217b802009-07-29 21:53:49 +0000977 const PointerType *PUsedTy = UsedTy->getAs<PointerType>();
Ted Kremenek25c54572009-07-20 22:58:02 +0000978
979 return PUsedTy && PRTy &&
980 IsReinterpreted(PRTy->getPointeeType(),
Mike Stump1eb44332009-09-09 15:08:12 +0000981 PUsedTy->getPointeeType(), Ctx);
Ted Kremenek25c54572009-07-20 22:58:02 +0000982 }
983
984 return true;
Ted Kremeneka6275a52009-07-15 02:31:43 +0000985}
986
Ted Kremenek0954cde2009-09-24 04:11:44 +0000987const ElementRegion *
988RegionStoreManager::GetElementZeroRegion(const SymbolicRegion *SR, QualType T) {
989 ASTContext &Ctx = getContext();
990 SVal idx = ValMgr.makeZeroArrayIndex();
991 assert(!T.isNull());
992 return MRMgr.getElementRegion(T, idx, SR, Ctx);
993}
994
995
996
Ted Kremenek32c3fa42009-07-21 21:03:30 +0000997SValuator::CastResult
998RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
Ted Kremenek67f28532009-06-17 22:02:04 +0000999
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001000 assert(!isa<UnknownVal>(L) && "location unknown");
1001 assert(!isa<UndefinedVal>(L) && "location undefined");
1002
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001003 // FIXME: Is this even possible? Shouldn't this be treated as a null
1004 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001005 if (isa<loc::ConcreteInt>(L))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001006 return SValuator::CastResult(state, UndefinedVal());
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001007
Ted Kremenek67f28532009-06-17 22:02:04 +00001008 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +00001009
Zhongxing Xu91844122009-05-20 09:18:48 +00001010 // FIXME: return symbolic value for these cases.
Zhongxing Xua1718c72009-04-03 07:33:13 +00001011 // Example:
1012 // void f(int* p) { int x = *p; }
Zhongxing Xu91844122009-05-20 09:18:48 +00001013 // char* p = alloca();
1014 // read(p);
1015 // c = *p;
Ted Kremenek60fbe8f2009-07-14 20:48:22 +00001016 if (isa<AllocaRegion>(MR))
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001017 return SValuator::CastResult(state, UnknownVal());
Mike Stump1eb44332009-09-09 15:08:12 +00001018
Ted Kremenek0954cde2009-09-24 04:11:44 +00001019 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1020 MR = GetElementZeroRegion(SR, T);
Mike Stump1eb44332009-09-09 15:08:12 +00001021
Ted Kremenek968f0a62009-08-03 21:41:46 +00001022 if (isa<CodeTextRegion>(MR))
1023 return SValuator::CastResult(state, UnknownVal());
Mike Stump1eb44332009-09-09 15:08:12 +00001024
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001025 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1026 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Ted Kremenek67f28532009-06-17 22:02:04 +00001027 const TypedRegion *R = cast<TypedRegion>(MR);
Ted Kremeneka6275a52009-07-15 02:31:43 +00001028 QualType RTy = R->getValueType(getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001029
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001030 // FIXME: We should eventually handle funny addressing. e.g.:
1031 //
1032 // int x = ...;
1033 // int *p = &x;
1034 // char *q = (char*) p;
1035 // char c = *q; // returns the first byte of 'x'.
1036 //
1037 // Such funny addressing will occur due to layering of regions.
1038
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001039#if 0
Ted Kremeneka6275a52009-07-15 02:31:43 +00001040 ASTContext &Ctx = getContext();
1041 if (!T.isNull() && IsReinterpreted(RTy, T, Ctx)) {
Ted Kremenek46537392009-07-16 01:33:37 +00001042 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
1043 R = MRMgr.getElementRegion(T, ZeroIdx, R, Ctx);
Ted Kremeneka6275a52009-07-15 02:31:43 +00001044 RTy = T;
Ted Kremenek41fb0df2009-07-15 04:23:32 +00001045 assert(Ctx.getCanonicalType(RTy) ==
1046 Ctx.getCanonicalType(R->getValueType(Ctx)));
Mike Stump1eb44332009-09-09 15:08:12 +00001047 }
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001048#endif
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001049
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001050 if (RTy->isStructureType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001051 return SValuator::CastResult(state, RetrieveStruct(state, R));
Mike Stump1eb44332009-09-09 15:08:12 +00001052
Ted Kremenekd4e5a602009-08-06 21:43:54 +00001053 // FIXME: Handle unions.
1054 if (RTy->isUnionType())
1055 return SValuator::CastResult(state, UnknownVal());
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001056
1057 if (RTy->isArrayType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001058 return SValuator::CastResult(state, RetrieveArray(state, R));
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001059
Zhongxing Xu1038f9f2009-03-09 09:15:51 +00001060 // FIXME: handle Vector types.
1061 if (RTy->isVectorType())
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001062 return SValuator::CastResult(state, UnknownVal());
Zhongxing Xu99c20302009-06-28 14:16:39 +00001063
1064 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
Zhongxing Xu652be342009-11-16 04:49:44 +00001065 return SValuator::CastResult(state,
1066 CastRetrievedVal(RetrieveField(state, FR), FR, T));
Zhongxing Xu99c20302009-06-28 14:16:39 +00001067
1068 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R))
Zhongxing Xu652be342009-11-16 04:49:44 +00001069 return SValuator::CastResult(state,
1070 CastRetrievedVal(RetrieveElement(state, ER), ER, T));
Mike Stump1eb44332009-09-09 15:08:12 +00001071
Ted Kremenek25c54572009-07-20 22:58:02 +00001072 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R))
Zhongxing Xu652be342009-11-16 04:49:44 +00001073 return SValuator::CastResult(state,
1074 CastRetrievedVal(RetrieveObjCIvar(state, IVR), IVR, T));
Mike Stump1eb44332009-09-09 15:08:12 +00001075
Ted Kremenek9031dd72009-07-21 00:12:07 +00001076 if (const VarRegion *VR = dyn_cast<VarRegion>(R))
Zhongxing Xu652be342009-11-16 04:49:44 +00001077 return SValuator::CastResult(state,
1078 CastRetrievedVal(RetrieveVar(state, VR), VR, T));
Ted Kremenek25c54572009-07-20 22:58:02 +00001079
Ted Kremenek451ac092009-08-06 04:50:20 +00001080 RegionBindings B = GetRegionBindings(state->getStore());
1081 RegionBindings::data_type* V = B.lookup(R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001082
1083 // Check if the region has a binding.
1084 if (V)
Zhongxing Xu13d50172009-10-11 08:08:02 +00001085 if (SVal const *SV = V->getValue())
1086 return SValuator::CastResult(state, *SV);
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001087
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001088 // The location does not have a bound value. This means that it has
1089 // the value it had upon its creation and/or entry to the analyzed
1090 // function/method. These are either symbolic values or 'undefined'.
1091
Ted Kremenek356e9d62009-07-22 04:35:42 +00001092#if HEAP_UNDEFINED
Ted Kremenekbb7c96f2009-06-23 18:17:08 +00001093 if (R->hasHeapOrStackStorage()) {
Ted Kremenek356e9d62009-07-22 04:35:42 +00001094#else
1095 if (R->hasStackStorage()) {
1096#endif
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001097 // All stack variables are considered to have undefined values
1098 // upon creation. All heap allocated blocks are considered to
1099 // have undefined values as well unless they are explicitly bound
1100 // to specific values.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001101 return SValuator::CastResult(state, UndefinedVal());
Ted Kremenek869fb4a2008-12-24 07:46:32 +00001102 }
1103
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001104 // All other values are symbolic.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001105 return SValuator::CastResult(state,
1106 ValMgr.getRegionValueSymbolValOrUnknown(R, RTy));
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001107}
Mike Stump1eb44332009-09-09 15:08:12 +00001108
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001109std::pair<const GRState*, const MemRegion*>
Ted Kremenek451ac092009-08-06 04:50:20 +00001110RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001111 if (Optional<SVal> OV = getDirectBinding(B, R))
1112 if (const nonloc::LazyCompoundVal *V =
1113 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
1114 return std::make_pair(V->getState(), V->getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001115
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001116 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1117 const std::pair<const GRState *, const MemRegion *> &X =
1118 GetLazyBinding(B, ER->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001119
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001120 if (X.first)
1121 return std::make_pair(X.first,
1122 MRMgr.getElementRegionWithSuper(ER, X.second));
Mike Stump1eb44332009-09-09 15:08:12 +00001123 }
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001124 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1125 const std::pair<const GRState *, const MemRegion *> &X =
1126 GetLazyBinding(B, FR->getSuperRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001127
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001128 if (X.first)
1129 return std::make_pair(X.first,
1130 MRMgr.getFieldRegionWithSuper(FR, X.second));
1131 }
1132
1133 return std::make_pair((const GRState*) 0, (const MemRegion *) 0);
1134}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001135
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001136SVal RegionStoreManager::RetrieveElement(const GRState* state,
1137 const ElementRegion* R) {
1138 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001139 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001140 if (Optional<SVal> V = getDirectBinding(B, R))
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001141 return *V;
1142
Ted Kremenek921109a2009-07-01 23:19:52 +00001143 const MemRegion* superR = R->getSuperRegion();
1144
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001145 // Check if the region is an element region of a string literal.
Ted Kremenek921109a2009-07-01 23:19:52 +00001146 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001147 // FIXME: Handle loads from strings where the literal is treated as
1148 // an integer, e.g., *((unsigned int*)"hello")
1149 ASTContext &Ctx = getContext();
Douglas Gregor89c49f02009-11-09 22:08:55 +00001150 QualType T = Ctx.getAsArrayType(StrR->getValueType(Ctx))->getElementType();
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001151 if (T != Ctx.getCanonicalType(R->getElementType()))
1152 return UnknownVal();
1153
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001154 const StringLiteral *Str = StrR->getStringLiteral();
1155 SVal Idx = R->getIndex();
1156 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1157 int64_t i = CI->getValue().getSExtValue();
Mike Stump1eb44332009-09-09 15:08:12 +00001158 int64_t byteLength = Str->getByteLength();
Ted Kremenek0667db32009-09-05 17:59:01 +00001159 if (i > byteLength) {
1160 // Buffer overflow checking in GRExprEngine should handle this case,
1161 // but we shouldn't rely on it to not overflow here if that checking
1162 // is disabled.
1163 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001164 }
Ted Kremenek0667db32009-09-05 17:59:01 +00001165 char c = (i == byteLength) ? '\0' : Str->getStrData()[i];
Ted Kremenek95efe0f2009-09-29 16:36:48 +00001166 return ValMgr.makeIntVal(c, T);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001167 }
1168 }
Mike Stump1eb44332009-09-09 15:08:12 +00001169
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001170 // Check if the immediate super region has a direct binding.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001171 if (Optional<SVal> V = getDirectBinding(B, superR)) {
Ted Kremeneka6275a52009-07-15 02:31:43 +00001172 if (SymbolRef parentSym = V->getAsSymbol())
1173 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenek356e9d62009-07-22 04:35:42 +00001174
1175 if (V->isUnknownOrUndef())
1176 return *V;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001177
1178 // Handle LazyCompoundVals for the immediate super region. Other cases
1179 // are handled in 'RetrieveFieldOrElementCommon'.
Mike Stump1eb44332009-09-09 15:08:12 +00001180 if (const nonloc::LazyCompoundVal *LCV =
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001181 dyn_cast<nonloc::LazyCompoundVal>(V)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001182
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001183 R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion());
1184 return RetrieveElement(LCV->getState(), R);
1185 }
Mike Stump1eb44332009-09-09 15:08:12 +00001186
Ted Kremeneka6275a52009-07-15 02:31:43 +00001187 // Other cases: give up.
Zhongxing Xu8834af32009-07-03 06:11:41 +00001188 return UnknownVal();
Zhongxing Xu7abe0192009-06-30 12:32:59 +00001189 }
Zhongxing Xu13d50172009-10-11 08:08:02 +00001190
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001191 return RetrieveFieldOrElementCommon(state, R, R->getElementType(), superR);
Zhongxing Xuc00346f2009-06-25 05:29:39 +00001192}
1193
Mike Stump1eb44332009-09-09 15:08:12 +00001194SVal RegionStoreManager::RetrieveField(const GRState* state,
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001195 const FieldRegion* R) {
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001196
1197 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001198 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001199 if (Optional<SVal> V = getDirectBinding(B, R))
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001200 return *V;
1201
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001202 QualType Ty = R->getValueType(getContext());
1203 return RetrieveFieldOrElementCommon(state, R, Ty, R->getSuperRegion());
1204}
Mike Stump1eb44332009-09-09 15:08:12 +00001205
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001206SVal RegionStoreManager::RetrieveFieldOrElementCommon(const GRState *state,
1207 const TypedRegion *R,
1208 QualType Ty,
1209 const MemRegion *superR) {
1210
Mike Stump1eb44332009-09-09 15:08:12 +00001211 // At this point we have already checked in either RetrieveElement or
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001212 // RetrieveField if 'R' has a direct binding.
Mike Stump1eb44332009-09-09 15:08:12 +00001213
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001214 RegionBindings B = GetRegionBindings(state->getStore());
Mike Stump1eb44332009-09-09 15:08:12 +00001215
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001216 while (superR) {
Zhongxing Xu13d50172009-10-11 08:08:02 +00001217 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001218 if (SymbolRef parentSym = D->getAsSymbol())
1219 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001220
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001221 if (D->isZeroConstant())
1222 return ValMgr.makeZeroVal(Ty);
Mike Stump1eb44332009-09-09 15:08:12 +00001223
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001224 if (D->isUnknown())
1225 return *D;
Mike Stump1eb44332009-09-09 15:08:12 +00001226
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001227 assert(0 && "Unknown default value");
1228 }
Mike Stump1eb44332009-09-09 15:08:12 +00001229
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001230 // If our super region is a field or element itself, walk up the region
1231 // hierarchy to see if there is a default value installed in an ancestor.
1232 if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) {
1233 superR = cast<SubRegion>(superR)->getSuperRegion();
1234 continue;
1235 }
Mike Stump1eb44332009-09-09 15:08:12 +00001236
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001237 break;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001238 }
Mike Stump1eb44332009-09-09 15:08:12 +00001239
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001240 // Lazy binding?
1241 const GRState *lazyBindingState = NULL;
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001242 const MemRegion *lazyBindingRegion = NULL;
1243 llvm::tie(lazyBindingState, lazyBindingRegion) = GetLazyBinding(B, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001244
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001245 if (lazyBindingState) {
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001246 assert(lazyBindingRegion && "Lazy-binding region not set");
Mike Stump1eb44332009-09-09 15:08:12 +00001247
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001248 if (isa<ElementRegion>(R))
1249 return RetrieveElement(lazyBindingState,
1250 cast<ElementRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001251
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001252 return RetrieveField(lazyBindingState,
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001253 cast<FieldRegion>(lazyBindingRegion));
Mike Stump1eb44332009-09-09 15:08:12 +00001254 }
1255
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001256 if (R->hasStackStorage() && !R->hasParametersStorage()) {
Mike Stump1eb44332009-09-09 15:08:12 +00001257
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001258 if (isa<ElementRegion>(R)) {
1259 // Currently we don't reason specially about Clang-style vectors. Check
1260 // if superR is a vector and if so return Unknown.
1261 if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) {
1262 if (typedSuperR->getValueType(getContext())->isVectorType())
1263 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001264 }
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001265 }
Mike Stump1eb44332009-09-09 15:08:12 +00001266
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001267 return UndefinedVal();
Ted Kremenek566a6fa2009-08-06 22:33:36 +00001268 }
Mike Stump1eb44332009-09-09 15:08:12 +00001269
Ted Kremenekbb2b4332009-07-02 22:16:42 +00001270 // All other values are symbolic.
1271 return ValMgr.getRegionValueSymbolValOrUnknown(R, Ty);
Zhongxing Xu490b0f02009-06-25 04:50:44 +00001272}
Mike Stump1eb44332009-09-09 15:08:12 +00001273
1274SVal RegionStoreManager::RetrieveObjCIvar(const GRState* state,
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001275 const ObjCIvarRegion* R) {
1276
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001277 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001278 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001279
Zhongxing Xu13d50172009-10-11 08:08:02 +00001280 if (Optional<SVal> V = getDirectBinding(B, R))
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001281 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001282
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001283 const MemRegion *superR = R->getSuperRegion();
1284
Ted Kremenekab22ee92009-10-20 01:20:57 +00001285 // Check if the super region has a default binding.
1286 if (Optional<SVal> V = getDefaultBinding(B, superR)) {
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001287 if (SymbolRef parentSym = V->getAsSymbol())
1288 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001289
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001290 // Other cases: give up.
1291 return UnknownVal();
1292 }
Mike Stump1eb44332009-09-09 15:08:12 +00001293
Ted Kremenek25c54572009-07-20 22:58:02 +00001294 return RetrieveLazySymbol(state, R);
1295}
1296
Ted Kremenek9031dd72009-07-21 00:12:07 +00001297SVal RegionStoreManager::RetrieveVar(const GRState *state,
1298 const VarRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001299
Ted Kremenek9031dd72009-07-21 00:12:07 +00001300 // Check if the region has a binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001301 RegionBindings B = GetRegionBindings(state->getStore());
Mike Stump1eb44332009-09-09 15:08:12 +00001302
Zhongxing Xu13d50172009-10-11 08:08:02 +00001303 if (Optional<SVal> V = getDirectBinding(B, R))
Ted Kremenek9031dd72009-07-21 00:12:07 +00001304 return *V;
Mike Stump1eb44332009-09-09 15:08:12 +00001305
Ted Kremenek9031dd72009-07-21 00:12:07 +00001306 // Lazily derive a value for the VarRegion.
1307 const VarDecl *VD = R->getDecl();
Mike Stump1eb44332009-09-09 15:08:12 +00001308
Ted Kremenek9031dd72009-07-21 00:12:07 +00001309 if (R->hasGlobalsOrParametersStorage())
1310 return ValMgr.getRegionValueSymbolValOrUnknown(R, VD->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00001311
Ted Kremenek9031dd72009-07-21 00:12:07 +00001312 return UndefinedVal();
1313}
1314
Mike Stump1eb44332009-09-09 15:08:12 +00001315SVal RegionStoreManager::RetrieveLazySymbol(const GRState *state,
Ted Kremenek25c54572009-07-20 22:58:02 +00001316 const TypedRegion *R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001317
Ted Kremenek25c54572009-07-20 22:58:02 +00001318 QualType valTy = R->getValueType(getContext());
Ted Kremenek356e9d62009-07-22 04:35:42 +00001319
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001320 // All other values are symbolic.
Ted Kremenek25c54572009-07-20 22:58:02 +00001321 return ValMgr.getRegionValueSymbolValOrUnknown(R, valTy);
Ted Kremenek5bd2fe32009-07-15 06:09:28 +00001322}
1323
Mike Stump1eb44332009-09-09 15:08:12 +00001324SVal RegionStoreManager::RetrieveStruct(const GRState *state,
1325 const TypedRegion* R) {
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001326 QualType T = R->getValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001327 assert(T->isStructureType());
1328
Zhongxing Xub7507d12009-06-11 07:27:30 +00001329 const RecordType* RT = T->getAsStructureType();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001330 RecordDecl* RD = RT->getDecl();
1331 assert(RD->isDefinition());
Mike Stump1aeb2472009-08-06 12:56:50 +00001332 (void)RD;
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001333#if USE_EXPLICIT_COMPOUND
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001334 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
1335
Ted Kremenek67f28532009-06-17 22:02:04 +00001336 // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a
1337 // reverse iterator, we should implement one.
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001338 std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end());
Douglas Gregor44b43212008-12-11 16:49:14 +00001339
Douglas Gregore267ff32008-12-11 20:41:00 +00001340 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
1341 FieldEnd = Fields.rend();
1342 Field != FieldEnd; ++Field) {
1343 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001344 QualType FTy = (*Field)->getType();
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001345 SVal FieldValue = Retrieve(state, loc::MemRegionVal(FR), FTy).getSVal();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001346 StructVal = getBasicVals().consVals(FieldValue, StructVal);
1347 }
1348
Zhongxing Xud91ee272009-06-23 09:02:15 +00001349 return ValMgr.makeCompoundVal(T, StructVal);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001350#else
1351 return ValMgr.makeLazyCompoundVal(state, R);
1352#endif
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +00001353}
1354
Ted Kremenek67f28532009-06-17 22:02:04 +00001355SVal RegionStoreManager::RetrieveArray(const GRState *state,
1356 const TypedRegion * R) {
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001357#if USE_EXPLICIT_COMPOUND
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001358 QualType T = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001359 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1360
1361 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
Ted Kremenek46537392009-07-16 01:33:37 +00001362 uint64_t size = CAT->getSize().getZExtValue();
1363 for (uint64_t i = 0; i < size; ++i) {
1364 SVal Idx = ValMgr.makeArrayIndex(i);
Zhongxing Xu143b2fc2009-06-16 09:55:50 +00001365 ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
Mike Stump1eb44332009-09-09 15:08:12 +00001366 getContext());
Ted Kremenekf936f452009-05-04 06:18:28 +00001367 QualType ETy = ER->getElementType();
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001368 SVal ElementVal = Retrieve(state, loc::MemRegionVal(ER), ETy).getSVal();
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001369 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
1370 }
1371
Zhongxing Xud91ee272009-06-23 09:02:15 +00001372 return ValMgr.makeCompoundVal(T, ArrayVal);
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001373#else
1374 assert(isa<ConstantArrayType>(R->getValueType(getContext())));
1375 return ValMgr.makeLazyCompoundVal(state, R);
1376#endif
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001377}
1378
Ted Kremenek9af46f52009-06-16 22:36:44 +00001379//===----------------------------------------------------------------------===//
1380// Binding values to regions.
1381//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +00001382
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001383Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +00001384 const MemRegion* R = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001385
Ted Kremenek0964a062009-01-21 06:57:53 +00001386 if (isa<loc::MemRegionVal>(L))
1387 R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001388
Ted Kremenek0964a062009-01-21 06:57:53 +00001389 if (R) {
Mike Stump1eb44332009-09-09 15:08:12 +00001390 RegionBindings B = GetRegionBindings(store);
Ted Kremenek0964a062009-01-21 06:57:53 +00001391 return RBFactory.Remove(B, R).getRoot();
1392 }
Mike Stump1eb44332009-09-09 15:08:12 +00001393
Ted Kremenek0964a062009-01-21 06:57:53 +00001394 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001395}
1396
Ted Kremenek67f28532009-06-17 22:02:04 +00001397const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +00001398 if (isa<loc::ConcreteInt>(L))
1399 return state;
1400
Ted Kremenek9af46f52009-06-16 22:36:44 +00001401 // If we get here, the location should be a region.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001402 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +00001403
Ted Kremenek9af46f52009-06-16 22:36:44 +00001404 // Check if the region is a struct region.
1405 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
1406 if (TR->getValueType(getContext())->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001407 return BindStruct(state, TR, V);
Mike Stump1eb44332009-09-09 15:08:12 +00001408
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001409 // Special case: the current region represents a cast and it and the super
1410 // region both have pointer types or intptr_t types. If so, perform the
1411 // bind to the super region.
1412 // This is needed to support OSAtomicCompareAndSwap and friends or other
Mike Stump1eb44332009-09-09 15:08:12 +00001413 // loads that treat integers as pointers and vis versa.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001414 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1415 if (ER->getIndex().isZeroConstant()) {
1416 if (const TypedRegion *superR =
1417 dyn_cast<TypedRegion>(ER->getSuperRegion())) {
1418 ASTContext &Ctx = getContext();
1419 QualType superTy = superR->getValueType(Ctx);
1420 QualType erTy = ER->getValueType(Ctx);
Mike Stump1eb44332009-09-09 15:08:12 +00001421
1422 if (IsAnyPointerOrIntptr(superTy, Ctx) &&
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001423 IsAnyPointerOrIntptr(erTy, Ctx)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001424 SValuator::CastResult cr =
1425 ValMgr.getSValuator().EvalCast(V, state, superTy, erTy);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001426 return Bind(cr.getState(), loc::MemRegionVal(superR), cr.getSVal());
1427 }
Ted Kremenek69181a82009-09-21 22:58:52 +00001428 // For now, just invalidate the fields of the struct/union/class.
1429 // FIXME: Precisely handle the fields of the record.
1430 if (superTy->isRecordType())
Ted Kremenek473e1672009-10-16 00:30:49 +00001431 return InvalidateRegion(state, superR, NULL, 0, NULL);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001432 }
1433 }
1434 }
Ted Kremenek0954cde2009-09-24 04:11:44 +00001435 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1436 // Binding directly to a symbolic region should be treated as binding
1437 // to element 0.
1438 QualType T = SR->getSymbol()->getType(getContext());
Ted Kremenek35dcad82009-09-24 06:24:32 +00001439 T = T->getAs<PointerType>()->getPointeeType();
Ted Kremenek0954cde2009-09-24 04:11:44 +00001440 R = GetElementZeroRegion(SR, T);
1441 }
Mike Stump1eb44332009-09-09 15:08:12 +00001442
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001443 // Perform the binding.
Ted Kremenek451ac092009-08-06 04:50:20 +00001444 RegionBindings B = GetRegionBindings(state->getStore());
Zhongxing Xu13d50172009-10-11 08:08:02 +00001445 return state->makeWithStore(
1446 RBFactory.Add(B, R, BindingVal(V, BindingVal::Direct)).getRoot());
Ted Kremenek9af46f52009-06-16 22:36:44 +00001447}
1448
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001449const GRState *RegionStoreManager::BindDecl(const GRState *ST,
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001450 const VarRegion *VR,
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001451 SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +00001452
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001453 QualType T = VR->getDecl()->getType();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001454
Ted Kremenek0964a062009-01-21 06:57:53 +00001455 if (T->isArrayType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001456 return BindArray(ST, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +00001457 if (T->isStructureType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001458 return BindStruct(ST, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001459
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001460 return Bind(ST, ValMgr.makeLoc(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001461}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001462
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001463// FIXME: this method should be merged into Bind().
Ted Kremenek67f28532009-06-17 22:02:04 +00001464const GRState *
1465RegionStoreManager::BindCompoundLiteral(const GRState *state,
1466 const CompoundLiteralExpr* CL,
1467 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001468
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001469 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Ted Kremenek67f28532009-06-17 22:02:04 +00001470 return Bind(state, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001471}
1472
Ted Kremenek027e2662009-11-19 20:20:24 +00001473const GRState *RegionStoreManager::setImplicitDefaultValue(const GRState *state,
1474 const MemRegion *R,
1475 QualType T) {
1476 Store store = state->getStore();
1477 RegionBindings B = GetRegionBindings(store);
1478 SVal V;
1479
1480 if (Loc::IsLocType(T))
1481 V = ValMgr.makeNull();
1482 else if (T->isIntegerType())
1483 V = ValMgr.makeZeroVal(T);
1484 else if (T->isStructureType() || T->isArrayType()) {
1485 // Set the default value to a zero constant when it is a structure
1486 // or array. The type doesn't really matter.
1487 V = ValMgr.makeZeroVal(ValMgr.getContext().IntTy);
1488 }
1489 else {
1490 return state;
1491 }
1492
1493 B = RBFactory.Add(B, R, BindingVal(V, BindingVal::Default));
1494 return state->makeWithStore(B.getRoot());
1495}
1496
Ted Kremenek67f28532009-06-17 22:02:04 +00001497const GRState *RegionStoreManager::BindArray(const GRState *state,
Ted Kremenek46537392009-07-16 01:33:37 +00001498 const TypedRegion* R,
Ted Kremenek67f28532009-06-17 22:02:04 +00001499 SVal Init) {
1500
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001501 QualType T = R->getValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001502 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001503 QualType ElementTy = CAT->getElementType();
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001504
Ted Kremenek46537392009-07-16 01:33:37 +00001505 uint64_t size = CAT->getSize().getZExtValue();
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001506
1507 // Check if the init expr is a StringLiteral.
1508 if (isa<loc::MemRegionVal>(Init)) {
1509 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1510 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1511 const char* str = S->getStrData();
1512 unsigned len = S->getByteLength();
1513 unsigned j = 0;
1514
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001515 // Copy bytes from the string literal into the target array. Trailing bytes
1516 // in the array that are not covered by the string literal are initialized
1517 // to zero.
Ted Kremenek46537392009-07-16 01:33:37 +00001518 for (uint64_t i = 0; i < size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001519 if (j >= len)
1520 break;
1521
Ted Kremenek46537392009-07-16 01:33:37 +00001522 SVal Idx = ValMgr.makeArrayIndex(i);
1523 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R,
1524 getContext());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001525
Zhongxing Xud91ee272009-06-23 09:02:15 +00001526 SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true);
Ted Kremenek67f28532009-06-17 22:02:04 +00001527 state = Bind(state, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001528 }
1529
Ted Kremenek67f28532009-06-17 22:02:04 +00001530 return state;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001531 }
1532
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001533 // Handle lazy compound values.
1534 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
1535 return CopyLazyBindings(*LCV, state, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001536
1537 // Remaining case: explicit compound values.
Ted Kremenek027e2662009-11-19 20:20:24 +00001538
1539 if (Init.isUnknown())
1540 return setImplicitDefaultValue(state, R, ElementTy);
1541
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001542 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001543 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Ted Kremenek46537392009-07-16 01:33:37 +00001544 uint64_t i = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001545
Ted Kremenek46537392009-07-16 01:33:37 +00001546 for (; i < size; ++i, ++VI) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001547 // The init list might be shorter than the array length.
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001548 if (VI == VE)
1549 break;
1550
Ted Kremenek46537392009-07-16 01:33:37 +00001551 SVal Idx = ValMgr.makeArrayIndex(i);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001552 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001553
1554 if (CAT->getElementType()->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001555 state = BindStruct(state, ER, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001556 else
Ted Kremenekcf549592009-09-22 21:19:14 +00001557 // FIXME: Do we need special handling of nested arrays?
Zhongxing Xud91ee272009-06-23 09:02:15 +00001558 state = Bind(state, ValMgr.makeLoc(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001559 }
1560
Ted Kremenek027e2662009-11-19 20:20:24 +00001561 // If the init list is shorter than the array length, set the
1562 // array default value.
1563 if (i < size)
1564 state = setImplicitDefaultValue(state, R, ElementTy);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001565
Ted Kremenek67f28532009-06-17 22:02:04 +00001566 return state;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001567}
1568
Ted Kremenek67f28532009-06-17 22:02:04 +00001569const GRState *
1570RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R,
1571 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +00001572
Ted Kremenek67f28532009-06-17 22:02:04 +00001573 if (!Features.supportsFields())
1574 return state;
Mike Stump1eb44332009-09-09 15:08:12 +00001575
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001576 QualType T = R->getValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001577 assert(T->isStructureType());
1578
Ted Kremenek6217b802009-07-29 21:53:49 +00001579 const RecordType* RT = T->getAs<RecordType>();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001580 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001581
1582 if (!RD->isDefinition())
Ted Kremenek67f28532009-06-17 22:02:04 +00001583 return state;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001584
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001585 // Handle lazy compound values.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001586 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001587 return CopyLazyBindings(*LCV, state, R);
Mike Stump1eb44332009-09-09 15:08:12 +00001588
Ted Kremenek67f28532009-06-17 22:02:04 +00001589 // We may get non-CompoundVal accidentally due to imprecise cast logic.
1590 // Ignore them and kill the field values.
1591 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
Zhongxing Xu13d50172009-10-11 08:08:02 +00001592 return state->makeWithStore(KillStruct(state->getStore(), R));
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001593
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001594 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001595 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001596
1597 RecordDecl::field_iterator FI, FE;
1598
Argyrios Kyrtzidis17945a02009-06-30 02:36:12 +00001599 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001600
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001601 if (VI == VE)
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001602 break;
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001603
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001604 QualType FTy = (*FI)->getType();
Ted Kremenekcf549592009-09-22 21:19:14 +00001605 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001606
Ted Kremenekcf549592009-09-22 21:19:14 +00001607 if (FTy->isArrayType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001608 state = BindArray(state, FR, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001609 else if (FTy->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001610 state = BindStruct(state, FR, *VI);
Ted Kremenekcf549592009-09-22 21:19:14 +00001611 else
1612 state = Bind(state, ValMgr.makeLoc(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001613 }
1614
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001615 // There may be fewer values in the initialize list than the fields of struct.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001616 if (FI != FE) {
1617 Store store = state->getStore();
1618 RegionBindings B = GetRegionBindings(store);
1619 B = RBFactory.Add(B, R,
1620 BindingVal(ValMgr.makeIntVal(0, false), BindingVal::Default));
1621 state = state->makeWithStore(B.getRoot());
1622 }
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001623
Ted Kremenek67f28532009-06-17 22:02:04 +00001624 return state;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001625}
1626
Zhongxing Xu13d50172009-10-11 08:08:02 +00001627Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R) {
1628 RegionBindings B = GetRegionBindings(store);
1629 llvm::OwningPtr<RegionStoreSubRegionMap>
1630 SubRegions(getRegionStoreSubRegionMap(store));
1631 RemoveSubRegionBindings(B, R, *SubRegions);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001632
Zhongxing Xue4df9c42009-06-25 05:52:16 +00001633 // Set the default value of the struct region to "unknown".
Zhongxing Xu13d50172009-10-11 08:08:02 +00001634 B = RBFactory.Add(B, R, BindingVal(UnknownVal(), BindingVal::Default));
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001635
Zhongxing Xu13d50172009-10-11 08:08:02 +00001636 return B.getRoot();
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001637}
1638
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001639const GRState*
1640RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1641 const GRState *state,
1642 const TypedRegion *R) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001643
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001644 // Nuke the old bindings stemming from R.
Ted Kremenek451ac092009-08-06 04:50:20 +00001645 RegionBindings B = GetRegionBindings(state->getStore());
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001646
Mike Stump1eb44332009-09-09 15:08:12 +00001647 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +00001648 SubRegions(getRegionStoreSubRegionMap(state->getStore()));
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001649
Mike Stump1eb44332009-09-09 15:08:12 +00001650 // B and DVM are updated after the call to RemoveSubRegionBindings.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001651 RemoveSubRegionBindings(B, R, *SubRegions.get());
Mike Stump1eb44332009-09-09 15:08:12 +00001652
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001653 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1654 // results in a zero-copy algorithm.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001655 return state->makeWithStore(
1656 RBFactory.Add(B, R, BindingVal(V, BindingVal::Direct)).getRoot());
Ted Kremeneka5e81f12009-08-06 01:20:57 +00001657}
Mike Stump1eb44332009-09-09 15:08:12 +00001658
Ted Kremenek9af46f52009-06-16 22:36:44 +00001659//===----------------------------------------------------------------------===//
1660// State pruning.
1661//===----------------------------------------------------------------------===//
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001662
Mike Stump1eb44332009-09-09 15:08:12 +00001663void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc,
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001664 SymbolReaper& SymReaper,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001665 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +00001666{
Ted Kremenek781115c2009-10-17 17:45:11 +00001667 typedef std::pair<const GRState*, const MemRegion *> RBDNode;
1668
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001669 Store store = state.getStore();
Ted Kremenek451ac092009-08-06 04:50:20 +00001670 RegionBindings B = GetRegionBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +00001671
Ted Kremenek9af46f52009-06-16 22:36:44 +00001672 // The backmap from regions to subregions.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001673 llvm::OwningPtr<RegionStoreSubRegionMap>
Zhongxing Xu13d50172009-10-11 08:08:02 +00001674 SubRegions(getRegionStoreSubRegionMap(store));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001675
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001676 // Do a pass over the regions in the store. For VarRegions we check if
1677 // the variable is still live and if so add it to the list of live roots.
1678 // For other regions we populate our region backmap.
Ted Kremenek9af46f52009-06-16 22:36:44 +00001679 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001680
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001681 // Scan the direct bindings for "intermediate" roots.
Ted Kremenek451ac092009-08-06 04:50:20 +00001682 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001683 const MemRegion *R = I.getKey();
1684 IntermediateRoots.push_back(R);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001685 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001686
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001687 // Process the "intermediate" roots to find if they are referenced by
Mike Stump1eb44332009-09-09 15:08:12 +00001688 // real roots.
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001689 llvm::SmallVector<RBDNode, 10> WorkList;
Ted Kremenek01756192009-10-29 05:14:17 +00001690 llvm::SmallVector<RBDNode, 10> Postponed;
1691
Zhongxing Xu6800b332009-10-18 04:15:47 +00001692 llvm::DenseSet<const MemRegion*> IntermediateVisited;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001693
Ted Kremenek9af46f52009-06-16 22:36:44 +00001694 while (!IntermediateRoots.empty()) {
1695 const MemRegion* R = IntermediateRoots.back();
1696 IntermediateRoots.pop_back();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001697
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001698 if (IntermediateVisited.count(R))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001699 continue;
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001700 IntermediateVisited.insert(R);
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001701
Ted Kremenek9af46f52009-06-16 22:36:44 +00001702 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001703 if (SymReaper.isLive(Loc, VR->getDecl()))
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001704 WorkList.push_back(std::make_pair(&state, VR));
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001705 continue;
1706 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001707
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001708 if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
Ted Kremenek01756192009-10-29 05:14:17 +00001709 llvm::SmallVectorImpl<RBDNode> &Q =
1710 SymReaper.isLive(SR->getSymbol()) ? WorkList : Postponed;
1711
1712 Q.push_back(std::make_pair(&state, SR));
1713
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001714 continue;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001715 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001716
1717 // Add the super region for R to the worklist if it is a subregion.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001718 if (const SubRegion* superR =
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001719 dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion()))
Ted Kremenek19e1f0b2009-08-01 06:17:29 +00001720 IntermediateRoots.push_back(superR);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001721 }
Mike Stump1eb44332009-09-09 15:08:12 +00001722
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001723 // Enqueue the RegionRoots onto WorkList.
1724 for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(),
1725 E=RegionRoots.end(); I!=E; ++I) {
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001726 WorkList.push_back(std::make_pair(&state, *I));
Mike Stump1eb44332009-09-09 15:08:12 +00001727 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001728 RegionRoots.clear();
1729
Zhongxing Xu6800b332009-10-18 04:15:47 +00001730 llvm::DenseSet<RBDNode> Visited;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001731
Ted Kremenek01756192009-10-29 05:14:17 +00001732tryAgain:
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001733 while (!WorkList.empty()) {
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001734 RBDNode N = WorkList.back();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001735 WorkList.pop_back();
1736
1737 // Have we visited this node before?
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001738 if (Visited.count(N))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001739 continue;
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001740 Visited.insert(N);
Mike Stump1eb44332009-09-09 15:08:12 +00001741
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001742 const MemRegion *R = N.second;
1743 const GRState *state_N = N.first;
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001744
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001745 // Enqueue subregions.
1746 RegionStoreSubRegionMap *M;
1747
1748 if (&state == state_N)
1749 M = SubRegions.get();
1750 else {
1751 RegionStoreSubRegionMap *& SM = SC[state_N];
1752 if (!SM)
1753 SM = getRegionStoreSubRegionMap(state_N->getStore());
1754 M = SM;
1755 }
1756
1757 RegionStoreSubRegionMap::iterator I, E;
1758 for (llvm::tie(I, E) = M->begin_end(R); I != E; ++I)
1759 WorkList.push_back(std::make_pair(state_N, *I));
1760
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001761 // Enqueue the super region.
1762 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1763 const MemRegion *superR = SR->getSuperRegion();
1764 if (!isa<MemSpaceRegion>(superR)) {
1765 // If 'R' is a field or an element, we want to keep the bindings
1766 // for the other fields and elements around. The reason is that
Zhongxing Xu13d50172009-10-11 08:08:02 +00001767 // pointer arithmetic can get us to the other fields or elements.
Zhongxing Xu8801beb2009-10-17 07:32:08 +00001768 assert(isa<FieldRegion>(R) || isa<ElementRegion>(R)
1769 || isa<ObjCIvarRegion>(R));
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001770 WorkList.push_back(std::make_pair(state_N, superR));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001771 }
1772 }
1773
1774 // Mark the symbol for any live SymbolicRegion as "live". This means we
1775 // should continue to track that symbol.
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001776 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001777 SymReaper.markLive(SymR->getSymbol());
Ted Kremeneka6d73af2009-11-26 02:35:42 +00001778
1779 // For BlockDataRegions, enqueue all VarRegions for that are referenced
1780 // via BlockDeclRefExprs.
1781 if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
1782 for (BlockDataRegion::referenced_vars_iterator
1783 RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
1784 RI != RE; ++RI)
1785 WorkList.push_back(std::make_pair(state_N, *RI));
1786
1787 // No possible data bindings on a BlockDataRegion. Continue to the
1788 // next region in the worklist.
1789 continue;
1790 }
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001791
1792 Store store_N = state_N->getStore();
1793 RegionBindings B_N = GetRegionBindings(store_N);
1794
1795 // Get the data binding for R (if any).
Zhongxing Xu13d50172009-10-11 08:08:02 +00001796 Optional<SVal> V = getBinding(B_N, R);
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001797
Zhongxing Xu13d50172009-10-11 08:08:02 +00001798 if (V) {
1799 // Check for lazy bindings.
1800 if (const nonloc::LazyCompoundVal *LCV =
1801 dyn_cast<nonloc::LazyCompoundVal>(V.getPointer())) {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001802
Zhongxing Xu13d50172009-10-11 08:08:02 +00001803 const LazyCompoundValData *D = LCV->getCVData();
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001804 WorkList.push_back(std::make_pair(D->getState(), D->getRegion()));
Zhongxing Xu13d50172009-10-11 08:08:02 +00001805 }
1806 else {
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001807 // Update the set of live symbols.
Zhongxing Xu13d50172009-10-11 08:08:02 +00001808 for (SVal::symbol_iterator SI=V->symbol_begin(), SE=V->symbol_end();
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001809 SI!=SE;++SI)
1810 SymReaper.markLive(*SI);
1811
Zhongxing Xu13d50172009-10-11 08:08:02 +00001812 // If V is a region, then add it to the worklist.
1813 if (const MemRegion *RX = V->getAsRegion())
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001814 WorkList.push_back(std::make_pair(state_N, RX));
Ted Kremenek9e17cc62009-09-29 06:35:00 +00001815 }
1816 }
1817 }
1818
Ted Kremenek01756192009-10-29 05:14:17 +00001819 // See if any postponed SymbolicRegions are actually live now, after
1820 // having done a scan.
1821 for (llvm::SmallVectorImpl<RBDNode>::iterator I = Postponed.begin(),
1822 E = Postponed.end() ; I != E ; ++I) {
1823 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(I->second)) {
1824 if (SymReaper.isLive(SR->getSymbol())) {
1825 WorkList.push_back(*I);
1826 I->second = NULL;
1827 }
1828 }
1829 }
1830
1831 if (!WorkList.empty())
1832 goto tryAgain;
1833
Ted Kremenek9af46f52009-06-16 22:36:44 +00001834 // We have now scanned the store, marking reachable regions and symbols
1835 // as live. We now remove all the regions that are dead from the store
Mike Stump1eb44332009-09-09 15:08:12 +00001836 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenek451ac092009-08-06 04:50:20 +00001837 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001838 const MemRegion* R = I.getKey();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001839 // If this region live? Is so, none of its symbols are dead.
Zhongxing Xuf77869f2009-10-17 08:39:24 +00001840 if (Visited.count(std::make_pair(&state, R)))
Ted Kremenek9af46f52009-06-16 22:36:44 +00001841 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001842
Ted Kremenek9af46f52009-06-16 22:36:44 +00001843 // Remove this dead region from the store.
Zhongxing Xud91ee272009-06-23 09:02:15 +00001844 store = Remove(store, ValMgr.makeLoc(R));
Mike Stump1eb44332009-09-09 15:08:12 +00001845
Ted Kremenek9af46f52009-06-16 22:36:44 +00001846 // Mark all non-live symbols that this region references as dead.
1847 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1848 SymReaper.maybeDead(SymR->getSymbol());
Mike Stump1eb44332009-09-09 15:08:12 +00001849
Zhongxing Xu13d50172009-10-11 08:08:02 +00001850 SVal X = *I.getData().getValue();
Ted Kremenek093569c2009-08-02 05:00:15 +00001851 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1852 for (; SI != SE; ++SI)
1853 SymReaper.maybeDead(*SI);
1854 }
Mike Stump1eb44332009-09-09 15:08:12 +00001855
Ted Kremenek2f26bc32009-08-02 04:45:08 +00001856 // Write the store back.
1857 state.setStore(store);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001858}
1859
Zhongxing Xu4e3c1f72009-10-13 02:24:55 +00001860GRState const *RegionStoreManager::EnterStackFrame(GRState const *state,
1861 StackFrameContext const *frame) {
1862 FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
1863 CallExpr const *CE = cast<CallExpr>(frame->getCallSite());
1864
1865 FunctionDecl::param_const_iterator PI = FD->param_begin();
1866
1867 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1868
1869 // Copy the arg expression value to the arg variables.
1870 for (; AI != AE; ++AI, ++PI) {
1871 SVal ArgVal = state->getSVal(*AI);
1872 MemRegion *R = MRMgr.getVarRegion(*PI, frame);
1873 state = Bind(state, ValMgr.makeLoc(R), ArgVal);
1874 }
1875
1876 return state;
1877}
1878
Ted Kremenek9af46f52009-06-16 22:36:44 +00001879//===----------------------------------------------------------------------===//
1880// Utility methods.
1881//===----------------------------------------------------------------------===//
1882
Ted Kremenek53ba0b62009-06-24 23:06:47 +00001883void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001884 const char* nl, const char *sep) {
Ted Kremenek451ac092009-08-06 04:50:20 +00001885 RegionBindings B = GetRegionBindings(store);
Ted Kremenekab22ee92009-10-20 01:20:57 +00001886 OS << "Store (direct and default bindings):" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +00001887
Ted Kremenek451ac092009-08-06 04:50:20 +00001888 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
Mike Stump1eb44332009-09-09 15:08:12 +00001889 OS << ' ' << I.getKey() << " : " << I.getData() << nl;
Ted Kremenek9af46f52009-06-16 22:36:44 +00001890}