1 //== Store.cpp - Interface for maps from Locations to Values ----*- C++ -*--==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defined the types Store and StoreManager.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Checker/PathSensitive/Store.h"
15 #include "clang/Checker/PathSensitive/GRState.h"
16 #include "clang/AST/CharUnits.h"
18 using namespace clang
;
20 StoreManager::StoreManager(GRStateManager
&stateMgr
)
21 : svalBuilder(stateMgr
.getSValBuilder()), StateMgr(stateMgr
),
22 MRMgr(svalBuilder
.getRegionManager()), Ctx(stateMgr
.getContext()) {}
24 Store
StoreManager::EnterStackFrame(const GRState
*state
,
25 const StackFrameContext
*frame
) {
26 return state
->getStore();
29 const MemRegion
*StoreManager::MakeElementRegion(const MemRegion
*Base
,
30 QualType EleTy
, uint64_t index
) {
31 NonLoc idx
= svalBuilder
.makeArrayIndex(index
);
32 return MRMgr
.getElementRegion(EleTy
, idx
, Base
, svalBuilder
.getContext());
35 // FIXME: Merge with the implementation of the same method in MemRegion.cpp
36 static bool IsCompleteType(ASTContext
&Ctx
, QualType Ty
) {
37 if (const RecordType
*RT
= Ty
->getAs
<RecordType
>()) {
38 const RecordDecl
*D
= RT
->getDecl();
39 if (!D
->getDefinition())
46 const ElementRegion
*StoreManager::GetElementZeroRegion(const MemRegion
*R
,
48 NonLoc idx
= svalBuilder
.makeZeroArrayIndex();
50 return MRMgr
.getElementRegion(T
, idx
, R
, Ctx
);
53 const MemRegion
*StoreManager::CastRegion(const MemRegion
*R
, QualType CastToTy
) {
55 ASTContext
& Ctx
= StateMgr
.getContext();
57 // Handle casts to Objective-C objects.
58 if (CastToTy
->isObjCObjectPointerType())
59 return R
->StripCasts();
61 if (CastToTy
->isBlockPointerType()) {
62 // FIXME: We may need different solutions, depending on the symbol
63 // involved. Blocks can be casted to/from 'id', as they can be treated
64 // as Objective-C objects. This could possibly be handled by enhancing
65 // our reasoning of downcasts of symbolic objects.
66 if (isa
<CodeTextRegion
>(R
) || isa
<SymbolicRegion
>(R
))
69 // We don't know what to make of it. Return a NULL region, which
70 // will be interpretted as UnknownVal.
74 // Now assume we are casting from pointer to pointer. Other cases should
75 // already be handled.
76 QualType PointeeTy
= CastToTy
->getAs
<PointerType
>()->getPointeeType();
77 QualType CanonPointeeTy
= Ctx
.getCanonicalType(PointeeTy
);
79 // Handle casts to void*. We just pass the region through.
80 if (CanonPointeeTy
.getLocalUnqualifiedType() == Ctx
.VoidTy
)
83 // Handle casts from compatible types.
85 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
)) {
86 QualType ObjTy
= Ctx
.getCanonicalType(TR
->getValueType());
87 if (CanonPointeeTy
== ObjTy
)
91 // Process region cast according to the kind of the region being cast.
92 switch (R
->getKind()) {
93 case MemRegion::CXXThisRegionKind
:
94 case MemRegion::GenericMemSpaceRegionKind
:
95 case MemRegion::StackLocalsSpaceRegionKind
:
96 case MemRegion::StackArgumentsSpaceRegionKind
:
97 case MemRegion::HeapSpaceRegionKind
:
98 case MemRegion::UnknownSpaceRegionKind
:
99 case MemRegion::NonStaticGlobalSpaceRegionKind
:
100 case MemRegion::StaticGlobalSpaceRegionKind
: {
101 assert(0 && "Invalid region cast");
105 case MemRegion::FunctionTextRegionKind
:
106 case MemRegion::BlockTextRegionKind
:
107 case MemRegion::BlockDataRegionKind
:
108 case MemRegion::StringRegionKind
:
109 // FIXME: Need to handle arbitrary downcasts.
110 case MemRegion::SymbolicRegionKind
:
111 case MemRegion::AllocaRegionKind
:
112 case MemRegion::CompoundLiteralRegionKind
:
113 case MemRegion::FieldRegionKind
:
114 case MemRegion::ObjCIvarRegionKind
:
115 case MemRegion::VarRegionKind
:
116 case MemRegion::CXXTempObjectRegionKind
:
117 case MemRegion::CXXBaseObjectRegionKind
:
118 return MakeElementRegion(R
, PointeeTy
);
120 case MemRegion::ElementRegionKind
: {
121 // If we are casting from an ElementRegion to another type, the
122 // algorithm is as follows:
124 // (1) Compute the "raw offset" of the ElementRegion from the
125 // base region. This is done by calling 'getAsRawOffset()'.
127 // (2a) If we get a 'RegionRawOffset' after calling
128 // 'getAsRawOffset()', determine if the absolute offset
129 // can be exactly divided into chunks of the size of the
130 // casted-pointee type. If so, create a new ElementRegion with
131 // the pointee-cast type as the new ElementType and the index
132 // being the offset divded by the chunk size. If not, create
133 // a new ElementRegion at offset 0 off the raw offset region.
135 // (2b) If we don't a get a 'RegionRawOffset' after calling
136 // 'getAsRawOffset()', it means that we are at offset 0.
138 // FIXME: Handle symbolic raw offsets.
140 const ElementRegion
*elementR
= cast
<ElementRegion
>(R
);
141 const RegionRawOffset
&rawOff
= elementR
->getAsArrayOffset();
142 const MemRegion
*baseR
= rawOff
.getRegion();
144 // If we cannot compute a raw offset, throw up our hands and return
145 // a NULL MemRegion*.
149 CharUnits off
= CharUnits::fromQuantity(rawOff
.getByteOffset());
152 // Edge case: we are at 0 bytes off the beginning of baseR. We
153 // check to see if type we are casting to is the same as the base
154 // region. If so, just return the base region.
155 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(baseR
)) {
156 QualType ObjTy
= Ctx
.getCanonicalType(TR
->getValueType());
157 QualType CanonPointeeTy
= Ctx
.getCanonicalType(PointeeTy
);
158 if (CanonPointeeTy
== ObjTy
)
162 // Otherwise, create a new ElementRegion at offset 0.
163 return MakeElementRegion(baseR
, PointeeTy
);
166 // We have a non-zero offset from the base region. We want to determine
167 // if the offset can be evenly divided by sizeof(PointeeTy). If so,
168 // we create an ElementRegion whose index is that value. Otherwise, we
169 // create two ElementRegions, one that reflects a raw offset and the other
170 // that reflects the cast.
172 // Compute the index for the new ElementRegion.
173 int64_t newIndex
= 0;
174 const MemRegion
*newSuperR
= 0;
176 // We can only compute sizeof(PointeeTy) if it is a complete type.
177 if (IsCompleteType(Ctx
, PointeeTy
)) {
178 // Compute the size in **bytes**.
179 CharUnits pointeeTySize
= Ctx
.getTypeSizeInChars(PointeeTy
);
180 if (!pointeeTySize
.isZero()) {
181 // Is the offset a multiple of the size? If so, we can layer the
182 // ElementRegion (with elementType == PointeeTy) directly on top of
184 if (off
% pointeeTySize
== 0) {
185 newIndex
= off
/ pointeeTySize
;
192 // Create an intermediate ElementRegion to represent the raw byte.
193 // This will be the super region of the final ElementRegion.
194 newSuperR
= MakeElementRegion(baseR
, Ctx
.CharTy
, off
.getQuantity());
197 return MakeElementRegion(newSuperR
, PointeeTy
, newIndex
);
201 assert(0 && "unreachable");
206 /// CastRetrievedVal - Used by subclasses of StoreManager to implement
207 /// implicit casts that arise from loads from regions that are reinterpreted
208 /// as another region.
209 SVal
StoreManager::CastRetrievedVal(SVal V
, const TypedRegion
*R
,
210 QualType castTy
, bool performTestOnly
) {
215 ASTContext
&Ctx
= svalBuilder
.getContext();
217 if (performTestOnly
) {
218 // Automatically translate references to pointers.
219 QualType T
= R
->getValueType();
220 if (const ReferenceType
*RT
= T
->getAs
<ReferenceType
>())
221 T
= Ctx
.getPointerType(RT
->getPointeeType());
223 assert(svalBuilder
.getContext().hasSameUnqualifiedType(castTy
, T
));
227 if (const Loc
*L
= dyn_cast
<Loc
>(&V
))
228 return svalBuilder
.evalCastL(*L
, castTy
);
229 else if (const NonLoc
*NL
= dyn_cast
<NonLoc
>(&V
))
230 return svalBuilder
.evalCastNL(*NL
, castTy
);
235 SVal
StoreManager::getLValueFieldOrIvar(const Decl
* D
, SVal Base
) {
236 if (Base
.isUnknownOrUndef())
239 Loc BaseL
= cast
<Loc
>(Base
);
240 const MemRegion
* BaseR
= 0;
242 switch (BaseL
.getSubKind()) {
243 case loc::MemRegionKind
:
244 BaseR
= cast
<loc::MemRegionVal
>(BaseL
).getRegion();
247 case loc::GotoLabelKind
:
248 // These are anormal cases. Flag an undefined value.
249 return UndefinedVal();
251 case loc::ConcreteIntKind
:
252 // While these seem funny, this can happen through casts.
253 // FIXME: What we should return is the field offset. For example,
254 // add the field offset to the integer value. That way funny things
255 // like this work properly: &(((struct foo *) 0xa)->f)
259 assert(0 && "Unhandled Base.");
263 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
265 if (const ObjCIvarDecl
*ID
= dyn_cast
<ObjCIvarDecl
>(D
))
266 return loc::MemRegionVal(MRMgr
.getObjCIvarRegion(ID
, BaseR
));
268 return loc::MemRegionVal(MRMgr
.getFieldRegion(cast
<FieldDecl
>(D
), BaseR
));
271 SVal
StoreManager::getLValueElement(QualType elementType
, NonLoc Offset
,
274 // If the base is an unknown or undefined value, just return it back.
275 // FIXME: For absolute pointer addresses, we just return that value back as
276 // well, although in reality we should return the offset added to that
278 if (Base
.isUnknownOrUndef() || isa
<loc::ConcreteInt
>(Base
))
281 const MemRegion
* BaseRegion
= cast
<loc::MemRegionVal
>(Base
).getRegion();
283 // Pointer of any type can be cast and used as array base.
284 const ElementRegion
*ElemR
= dyn_cast
<ElementRegion
>(BaseRegion
);
286 // Convert the offset to the appropriate size and signedness.
287 Offset
= cast
<NonLoc
>(svalBuilder
.convertToArrayIndex(Offset
));
291 // If the base region is not an ElementRegion, create one.
292 // This can happen in the following example:
294 // char *p = __builtin_alloc(10);
297 // Observe that 'p' binds to an AllocaRegion.
299 return loc::MemRegionVal(MRMgr
.getElementRegion(elementType
, Offset
,
303 SVal BaseIdx
= ElemR
->getIndex();
305 if (!isa
<nonloc::ConcreteInt
>(BaseIdx
))
308 const llvm::APSInt
& BaseIdxI
= cast
<nonloc::ConcreteInt
>(BaseIdx
).getValue();
310 // Only allow non-integer offsets if the base region has no offset itself.
311 // FIXME: This is a somewhat arbitrary restriction. We should be using
312 // SValBuilder here to add the two offsets without checking their types.
313 if (!isa
<nonloc::ConcreteInt
>(Offset
)) {
314 if (isa
<ElementRegion
>(BaseRegion
->StripCasts()))
317 return loc::MemRegionVal(MRMgr
.getElementRegion(elementType
, Offset
,
318 ElemR
->getSuperRegion(),
322 const llvm::APSInt
& OffI
= cast
<nonloc::ConcreteInt
>(Offset
).getValue();
323 assert(BaseIdxI
.isSigned());
325 // Compute the new index.
326 nonloc::ConcreteInt
NewIdx(svalBuilder
.getBasicValueFactory().getValue(BaseIdxI
+
329 // Construct the new ElementRegion.
330 const MemRegion
*ArrayR
= ElemR
->getSuperRegion();
331 return loc::MemRegionVal(MRMgr
.getElementRegion(elementType
, NewIdx
, ArrayR
,