1c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek//== Store.cpp - Interface for maps from Locations to Values ----*- C++ -*--==// 2c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// 3c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// The LLVM Compiler Infrastructure 4c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// 5c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// This file is distributed under the University of Illinois Open Source 6c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// License. See LICENSE.TXT for details. 7c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// 8c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek//===----------------------------------------------------------------------===// 9c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// 10c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// This file defined the types Store and StoreManager. 11c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek// 12c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek//===----------------------------------------------------------------------===// 13c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek 149b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 15f540c54701e3eeb34cb619a3a4eb18f1ac70ef2dJordan Rose#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 1618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17199c3d6cd16aebbb9c7f0d42af9d922c9628bf70Ken Dyck#include "clang/AST/CharUnits.h" 18c35fb7d67d515659ad2325b4f6ec97c9fe64fb63Benjamin Kramer#include "clang/AST/DeclObjC.h" 19c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek 20c62abc1012feb0b15eff091b02c176649766a347Ted Kremenekusing namespace clang; 219ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 22c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek 2318c66fdc3c4008d335885695fe36fb5353c5f672Ted KremenekStoreManager::StoreManager(ProgramStateManager &stateMgr) 24c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 25c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 26c62abc1012feb0b15eff091b02c176649766a347Ted Kremenek 27e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan RoseStoreRef StoreManager::enterStackFrame(Store OldStore, 28e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose const CallEvent &Call, 29e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose const StackFrameContext *LCtx) { 30e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose StoreRef Store = StoreRef(OldStore, *this); 31e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose 32ef15831780b705475e7b237ac16418e9b53cb7a6Jordan Rose SmallVector<CallEvent::FrameBindingTy, 16> InitialBindings; 33ef15831780b705475e7b237ac16418e9b53cb7a6Jordan Rose Call.getInitialStackFrameContents(LCtx, InitialBindings); 34e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose 35ef15831780b705475e7b237ac16418e9b53cb7a6Jordan Rose for (CallEvent::BindingsTy::iterator I = InitialBindings.begin(), 36ef15831780b705475e7b237ac16418e9b53cb7a6Jordan Rose E = InitialBindings.end(); 37ef15831780b705475e7b237ac16418e9b53cb7a6Jordan Rose I != E; ++I) { 38ef15831780b705475e7b237ac16418e9b53cb7a6Jordan Rose Store = Bind(Store.getStore(), I->first, I->second); 39e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose } 40e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose 41e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose return Store; 42ff59efd65bb1f2f8d005079597f814a3c8381f95Jordy Rose} 43ff59efd65bb1f2f8d005079597f814a3c8381f95Jordy Rose 4409270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xuconst MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base, 45652be346f74feba027bcbdeb6a3e3f4755a0e62cZhongxing Xu QualType EleTy, uint64_t index) { 46c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek NonLoc idx = svalBuilder.makeArrayIndex(index); 47c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext()); 48411af40d038947b6d2a8ad9549c85c1c4c52d15aTed Kremenek} 49411af40d038947b6d2a8ad9549c85c1c4c52d15aTed Kremenek 5019e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek// FIXME: Merge with the implementation of the same method in MemRegion.cpp 51169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenekstatic bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 526217b80b7a1379b74cced1c076338262c3c980b3Ted Kremenek if (const RecordType *RT = Ty->getAs<RecordType>()) { 53169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek const RecordDecl *D = RT->getDecl(); 54952b017601f9c82b51119c3a1600f1312a833db9Douglas Gregor if (!D->getDefinition()) 55169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek return false; 56169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek } 571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 58169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek return true; 59169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek} 60169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek 6177a4d5687c2cb3199c689892c9d040a94ff270afTed KremenekStoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) { 6277a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek return StoreRef(store, *this); 6377a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek} 6477a4d5687c2cb3199c689892c9d040a94ff270afTed Kremenek 65856c6bcaea56e05255e9f3997ddd56b5c18a14f0Zhongxing Xuconst ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R, 66856c6bcaea56e05255e9f3997ddd56b5c18a14f0Zhongxing Xu QualType T) { 67c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek NonLoc idx = svalBuilder.makeZeroArrayIndex(); 68856c6bcaea56e05255e9f3997ddd56b5c18a14f0Zhongxing Xu assert(!T.isNull()); 69856c6bcaea56e05255e9f3997ddd56b5c18a14f0Zhongxing Xu return MRMgr.getElementRegion(T, idx, R, Ctx); 70856c6bcaea56e05255e9f3997ddd56b5c18a14f0Zhongxing Xu} 71856c6bcaea56e05255e9f3997ddd56b5c18a14f0Zhongxing Xu 722534528c22260211a073e192c38d0db84c70c327Ted Kremenekconst MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) { 731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 749c378f705405d37f49795d5e915989de774fe11fTed Kremenek ASTContext &Ctx = StateMgr.getContext(); 751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 76b9a44250c502cf9f9a2c18ccd50f06158dd7357bTed Kremenek // Handle casts to Objective-C objects. 7719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (CastToTy->isObjCObjectPointerType()) 78479529e679957fbb92b56e116e3c86734429331eZhongxing Xu return R->StripCasts(); 7919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek 8063b9cfe8f2aaec53710b59e565bb8d5afb558b40Ted Kremenek if (CastToTy->isBlockPointerType()) { 81abd46e13cfd48f2c9bf26d9759edb4366aaa6d5bTed Kremenek // FIXME: We may need different solutions, depending on the symbol 8263b9cfe8f2aaec53710b59e565bb8d5afb558b40Ted Kremenek // involved. Blocks can be casted to/from 'id', as they can be treated 83abd46e13cfd48f2c9bf26d9759edb4366aaa6d5bTed Kremenek // as Objective-C objects. This could possibly be handled by enhancing 841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // our reasoning of downcasts of symbolic objects. 85abd46e13cfd48f2c9bf26d9759edb4366aaa6d5bTed Kremenek if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R)) 8609270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return R; 8763b9cfe8f2aaec53710b59e565bb8d5afb558b40Ted Kremenek 8863b9cfe8f2aaec53710b59e565bb8d5afb558b40Ted Kremenek // We don't know what to make of it. Return a NULL region, which 8963b9cfe8f2aaec53710b59e565bb8d5afb558b40Ted Kremenek // will be interpretted as UnknownVal. 9009270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return NULL; 9163b9cfe8f2aaec53710b59e565bb8d5afb558b40Ted Kremenek } 92411af40d038947b6d2a8ad9549c85c1c4c52d15aTed Kremenek 9348ce7deb86ffb1e028ac9a8e7cddffc32843c26cTed Kremenek // Now assume we are casting from pointer to pointer. Other cases should 9448ce7deb86ffb1e028ac9a8e7cddffc32843c26cTed Kremenek // already be handled. 95b14175a5371a6c71f3b2dbe4e7aa14803ac38c54Argyrios Kyrtzidis QualType PointeeTy = CastToTy->getPointeeType(); 969a108eb88f93c524dfa5fb2c3fea3896b1eb6525Ted Kremenek QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 979a108eb88f93c524dfa5fb2c3fea3896b1eb6525Ted Kremenek 989a108eb88f93c524dfa5fb2c3fea3896b1eb6525Ted Kremenek // Handle casts to void*. We just pass the region through. 99a4923eb7c4b04d360cb2747641a5e92818edf804Douglas Gregor if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy) 10009270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return R; 1011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1029a108eb88f93c524dfa5fb2c3fea3896b1eb6525Ted Kremenek // Handle casts from compatible types. 10319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (R->isBoundable()) 1049697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 105018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 1069a108eb88f93c524dfa5fb2c3fea3896b1eb6525Ted Kremenek if (CanonPointeeTy == ObjTy) 10709270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return R; 10819e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 10919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek 11048ce7deb86ffb1e028ac9a8e7cddffc32843c26cTed Kremenek // Process region cast according to the kind of the region being cast. 111fc8f57c31d8336db0ccb2ce8eb9ebf52228a47c1Ted Kremenek switch (R->getKind()) { 112de0d26310191215a6d1d189dc419f87af18ce6beTed Kremenek case MemRegion::CXXThisRegionKind: 11367d1287035767f4f6c8ca0c2bb755990012a44caTed Kremenek case MemRegion::GenericMemSpaceRegionKind: 11467d1287035767f4f6c8ca0c2bb755990012a44caTed Kremenek case MemRegion::StackLocalsSpaceRegionKind: 11567d1287035767f4f6c8ca0c2bb755990012a44caTed Kremenek case MemRegion::StackArgumentsSpaceRegionKind: 11667d1287035767f4f6c8ca0c2bb755990012a44caTed Kremenek case MemRegion::HeapSpaceRegionKind: 1172b87ae45e129b941d0a4d221c9d4842385a119bdTed Kremenek case MemRegion::UnknownSpaceRegionKind: 118eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks case MemRegion::StaticGlobalSpaceRegionKind: 119eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks case MemRegion::GlobalInternalSpaceRegionKind: 120eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks case MemRegion::GlobalSystemSpaceRegionKind: 121eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks case MemRegion::GlobalImmutableSpaceRegionKind: { 122b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Invalid region cast"); 1231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 1241e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek 125eb1c7a04509f5d25c09005a6d46bd8bbb3ca88cbTed Kremenek case MemRegion::FunctionTextRegionKind: 126bf0fe6c5b7bd7bc67b6b3ef0acb22bf4811f2a1bTed Kremenek case MemRegion::BlockTextRegionKind: 1271e4a32acfad6a9f4cf555fdbc5c6c44c558b9fcbTed Kremenek case MemRegion::BlockDataRegionKind: 128fc8f57c31d8336db0ccb2ce8eb9ebf52228a47c1Ted Kremenek case MemRegion::StringRegionKind: 129fc8f57c31d8336db0ccb2ce8eb9ebf52228a47c1Ted Kremenek // FIXME: Need to handle arbitrary downcasts. 13019e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek case MemRegion::SymbolicRegionKind: 13119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek case MemRegion::AllocaRegionKind: 132fc8f57c31d8336db0ccb2ce8eb9ebf52228a47c1Ted Kremenek case MemRegion::CompoundLiteralRegionKind: 133fc8f57c31d8336db0ccb2ce8eb9ebf52228a47c1Ted Kremenek case MemRegion::FieldRegionKind: 134fc8f57c31d8336db0ccb2ce8eb9ebf52228a47c1Ted Kremenek case MemRegion::ObjCIvarRegionKind: 1354c62b557e269a27515dfca1f754ae936c8fdb824Ted Kremenek case MemRegion::ObjCStringRegionKind: 1361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump case MemRegion::VarRegionKind: 13702fe28c8a6da29d4ad88d0900c133dcf22d24a75Zhongxing Xu case MemRegion::CXXTempObjectRegionKind: 13802fe28c8a6da29d4ad88d0900c133dcf22d24a75Zhongxing Xu case MemRegion::CXXBaseObjectRegionKind: 13909270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return MakeElementRegion(R, PointeeTy); 1401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek case MemRegion::ElementRegionKind: { 14219e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // If we are casting from an ElementRegion to another type, the 14319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // algorithm is as follows: 14419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // 14519e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // (1) Compute the "raw offset" of the ElementRegion from the 14619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // base region. This is done by calling 'getAsRawOffset()'. 14719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // 1481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // (2a) If we get a 'RegionRawOffset' after calling 14919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // 'getAsRawOffset()', determine if the absolute offset 1501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // can be exactly divided into chunks of the size of the 1511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // casted-pointee type. If so, create a new ElementRegion with 15219e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // the pointee-cast type as the new ElementType and the index 15319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // being the offset divded by the chunk size. If not, create 15419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // a new ElementRegion at offset 0 off the raw offset region. 15519e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // 15619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // (2b) If we don't a get a 'RegionRawOffset' after calling 15719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // 'getAsRawOffset()', it means that we are at offset 0. 1581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // 15919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // FIXME: Handle symbolic raw offsets. 1601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 16119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek const ElementRegion *elementR = cast<ElementRegion>(R); 1627caf9b369cba6edaf6eac25121cbc65ee938f14dZhongxing Xu const RegionRawOffset &rawOff = elementR->getAsArrayOffset(); 16319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek const MemRegion *baseR = rawOff.getRegion(); 1641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 16519e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // If we cannot compute a raw offset, throw up our hands and return 16619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // a NULL MemRegion*. 16719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (!baseR) 16809270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return NULL; 1691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1709ff2b13aee0f89d23ef4820218f9b88bb5e5c1c1Ken Dyck CharUnits off = rawOff.getOffset(); 1711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 172199c3d6cd16aebbb9c7f0d42af9d922c9628bf70Ken Dyck if (off.isZero()) { 17319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // Edge case: we are at 0 bytes off the beginning of baseR. We 17419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // check to see if type we are casting to is the same as the base 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // region. If so, just return the base region. 1769697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(baseR)) { 177018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 17819e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 17919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (CanonPointeeTy == ObjTy) 18009270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return baseR; 18119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 1821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 18319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // Otherwise, create a new ElementRegion at offset 0. 18409270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return MakeElementRegion(baseR, PointeeTy); 185169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek } 1861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 18719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // We have a non-zero offset from the base region. We want to determine 18819e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // if the offset can be evenly divided by sizeof(PointeeTy). If so, 18919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // we create an ElementRegion whose index is that value. Otherwise, we 19019e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // create two ElementRegions, one that reflects a raw offset and the other 19119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // that reflects the cast. 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 19319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // Compute the index for the new ElementRegion. 19419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek int64_t newIndex = 0; 19519e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek const MemRegion *newSuperR = 0; 196169077dde4d91270a7495793f1e00b22aa0bc7caTed Kremenek 19719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // We can only compute sizeof(PointeeTy) if it is a complete type. 19819e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (IsCompleteType(Ctx, PointeeTy)) { 19919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // Compute the size in **bytes**. 200199c3d6cd16aebbb9c7f0d42af9d922c9628bf70Ken Dyck CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy); 201974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek if (!pointeeTySize.isZero()) { 202974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek // Is the offset a multiple of the size? If so, we can layer the 203974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek // ElementRegion (with elementType == PointeeTy) directly on top of 204974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek // the base region. 205974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek if (off % pointeeTySize == 0) { 206974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek newIndex = off / pointeeTySize; 207974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek newSuperR = baseR; 208974d97b251aaf5a735af83367cd3a930f3eb4333Ted Kremenek } 20919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 21019e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 2111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 21219e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (!newSuperR) { 21319e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // Create an intermediate ElementRegion to represent the raw byte. 21419e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek // This will be the super region of the final ElementRegion. 215199c3d6cd16aebbb9c7f0d42af9d922c9628bf70Ken Dyck newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity()); 21619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 2171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 21809270cc1b9cdd4c50012cb7984df8745e05833e5Zhongxing Xu return MakeElementRegion(newSuperR, PointeeTy, newIndex); 21948ce7deb86ffb1e028ac9a8e7cddffc32843c26cTed Kremenek } 22048ce7deb86ffb1e028ac9a8e7cddffc32843c26cTed Kremenek } 2211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 222b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("unreachable"); 22348ce7deb86ffb1e028ac9a8e7cddffc32843c26cTed Kremenek} 2241894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek 2252c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan RoseSVal StoreManager::evalDerivedToBase(SVal Derived, const CastExpr *Cast) { 2262c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose // Walk through the cast path to create nested CXXBaseRegions. 2272c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose SVal Result = Derived; 2282c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose for (CastExpr::path_const_iterator I = Cast->path_begin(), 2292c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose E = Cast->path_end(); 2302c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose I != E; ++I) { 2312c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose Result = evalDerivedToBase(Result, (*I)->getType()); 2322c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose } 2332c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose return Result; 2342c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose} 2352c5f8d79ed128892fa548a3308a938a3a53fbb5eJordan Rose 2361894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek 2371894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek/// CastRetrievedVal - Used by subclasses of StoreManager to implement 2381894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek/// implicit casts that arise from loads from regions that are reinterpreted 2391894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek/// as another region. 2409697934650354bed2e509d8e7e44f21a1fb00f76Ted KremenekSVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R, 241c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek QualType castTy, bool performTestOnly) { 242852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek 243aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks if (castTy.isNull() || V.isUnknownOrUndef()) 244652be346f74feba027bcbdeb6a3e3f4755a0e62cZhongxing Xu return V; 245852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek 246c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek ASTContext &Ctx = svalBuilder.getContext(); 2472f4a6b25a7409f6f05e8a5e6864de21a337c8958Zhongxing Xu 248c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (performTestOnly) { 249c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // Automatically translate references to pointers. 250018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu QualType T = R->getValueType(); 251c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (const ReferenceType *RT = T->getAs<ReferenceType>()) 252c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek T = Ctx.getPointerType(RT->getPointeeType()); 253c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 254c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek assert(svalBuilder.getContext().hasSameUnqualifiedType(castTy, T)); 255c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek return V; 256c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek } 257c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek 258aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return svalBuilder.dispatchCast(V, castTy); 2591894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek} 2601894dce96476dbe58c0e60d47f8987cbeb3d3869Ted Kremenek 2619c378f705405d37f49795d5e915989de774fe11fTed KremenekSVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) { 262c1511e04998e685c9e030323e248363b9633267dZhongxing Xu if (Base.isUnknownOrUndef()) 263c1511e04998e685c9e030323e248363b9633267dZhongxing Xu return Base; 264c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 265c1511e04998e685c9e030323e248363b9633267dZhongxing Xu Loc BaseL = cast<Loc>(Base); 266c1511e04998e685c9e030323e248363b9633267dZhongxing Xu const MemRegion* BaseR = 0; 267c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 268c1511e04998e685c9e030323e248363b9633267dZhongxing Xu switch (BaseL.getSubKind()) { 269c1511e04998e685c9e030323e248363b9633267dZhongxing Xu case loc::MemRegionKind: 270c1511e04998e685c9e030323e248363b9633267dZhongxing Xu BaseR = cast<loc::MemRegionVal>(BaseL).getRegion(); 271c1511e04998e685c9e030323e248363b9633267dZhongxing Xu break; 272c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 273c1511e04998e685c9e030323e248363b9633267dZhongxing Xu case loc::GotoLabelKind: 274c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // These are anormal cases. Flag an undefined value. 275c1511e04998e685c9e030323e248363b9633267dZhongxing Xu return UndefinedVal(); 276c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 277c1511e04998e685c9e030323e248363b9633267dZhongxing Xu case loc::ConcreteIntKind: 278c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // While these seem funny, this can happen through casts. 279c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // FIXME: What we should return is the field offset. For example, 280c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // add the field offset to the integer value. That way funny things 281c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // like this work properly: &(((struct foo *) 0xa)->f) 282c1511e04998e685c9e030323e248363b9633267dZhongxing Xu return Base; 283c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 284c1511e04998e685c9e030323e248363b9633267dZhongxing Xu default: 285b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Unhandled Base."); 286c1511e04998e685c9e030323e248363b9633267dZhongxing Xu } 287c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 288c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // NOTE: We must have this check first because ObjCIvarDecl is a subclass 289c1511e04998e685c9e030323e248363b9633267dZhongxing Xu // of FieldDecl. 290c1511e04998e685c9e030323e248363b9633267dZhongxing Xu if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D)) 291c1511e04998e685c9e030323e248363b9633267dZhongxing Xu return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR)); 292c1511e04998e685c9e030323e248363b9633267dZhongxing Xu 293c1511e04998e685c9e030323e248363b9633267dZhongxing Xu return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR)); 294c1511e04998e685c9e030323e248363b9633267dZhongxing Xu} 29552535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 296c35fb7d67d515659ad2325b4f6ec97c9fe64fb63Benjamin KramerSVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 297c35fb7d67d515659ad2325b4f6ec97c9fe64fb63Benjamin Kramer return getLValueFieldOrIvar(decl, base); 298c35fb7d67d515659ad2325b4f6ec97c9fe64fb63Benjamin Kramer} 299c35fb7d67d515659ad2325b4f6ec97c9fe64fb63Benjamin Kramer 30002282acd7a42d06a3178e3102d34a585bd82dd9fTed KremenekSVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, 30152535688b1339e0b3898ac0d670052482851a3abZhongxing Xu SVal Base) { 30252535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 30352535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // If the base is an unknown or undefined value, just return it back. 30452535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // FIXME: For absolute pointer addresses, we just return that value back as 30552535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // well, although in reality we should return the offset added to that 30652535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // value. 30752535688b1339e0b3898ac0d670052482851a3abZhongxing Xu if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base)) 30852535688b1339e0b3898ac0d670052482851a3abZhongxing Xu return Base; 30952535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 31052535688b1339e0b3898ac0d670052482851a3abZhongxing Xu const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion(); 31152535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 31252535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // Pointer of any type can be cast and used as array base. 31352535688b1339e0b3898ac0d670052482851a3abZhongxing Xu const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion); 31452535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 31552535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // Convert the offset to the appropriate size and signedness. 316c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek Offset = cast<NonLoc>(svalBuilder.convertToArrayIndex(Offset)); 31752535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 31852535688b1339e0b3898ac0d670052482851a3abZhongxing Xu if (!ElemR) { 31952535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // 32052535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // If the base region is not an ElementRegion, create one. 32152535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // This can happen in the following example: 32252535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // 32352535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // char *p = __builtin_alloc(10); 32452535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // p[1] = 8; 32552535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // 32652535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // Observe that 'p' binds to an AllocaRegion. 32752535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // 32852535688b1339e0b3898ac0d670052482851a3abZhongxing Xu return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 32952535688b1339e0b3898ac0d670052482851a3abZhongxing Xu BaseRegion, Ctx)); 33052535688b1339e0b3898ac0d670052482851a3abZhongxing Xu } 33152535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 33252535688b1339e0b3898ac0d670052482851a3abZhongxing Xu SVal BaseIdx = ElemR->getIndex(); 33352535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 33452535688b1339e0b3898ac0d670052482851a3abZhongxing Xu if (!isa<nonloc::ConcreteInt>(BaseIdx)) 33552535688b1339e0b3898ac0d670052482851a3abZhongxing Xu return UnknownVal(); 33652535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 33752535688b1339e0b3898ac0d670052482851a3abZhongxing Xu const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue(); 338e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose 339e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose // Only allow non-integer offsets if the base region has no offset itself. 340e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose // FIXME: This is a somewhat arbitrary restriction. We should be using 341846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek // SValBuilder here to add the two offsets without checking their types. 342e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose if (!isa<nonloc::ConcreteInt>(Offset)) { 343e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose if (isa<ElementRegion>(BaseRegion->StripCasts())) 344e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose return UnknownVal(); 345e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose 346e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 347e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose ElemR->getSuperRegion(), 348e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose Ctx)); 349e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose } 350e701117b21356d3c60133315b5bdd50232ec6ccaJordy Rose 35152535688b1339e0b3898ac0d670052482851a3abZhongxing Xu const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue(); 35252535688b1339e0b3898ac0d670052482851a3abZhongxing Xu assert(BaseIdxI.isSigned()); 35352535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 35452535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // Compute the new index. 355c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 35602282acd7a42d06a3178e3102d34a585bd82dd9fTed Kremenek OffI)); 35752535688b1339e0b3898ac0d670052482851a3abZhongxing Xu 35852535688b1339e0b3898ac0d670052482851a3abZhongxing Xu // Construct the new ElementRegion. 35952535688b1339e0b3898ac0d670052482851a3abZhongxing Xu const MemRegion *ArrayR = ElemR->getSuperRegion(); 36052535688b1339e0b3898ac0d670052482851a3abZhongxing Xu return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 36152535688b1339e0b3898ac0d670052482851a3abZhongxing Xu Ctx)); 36252535688b1339e0b3898ac0d670052482851a3abZhongxing Xu} 363a4c7a4314ffbe402091695874e93d9b0a79c8099Ted Kremenek 364a4c7a4314ffbe402091695874e93d9b0a79c8099Ted KremenekStoreManager::BindingsHandler::~BindingsHandler() {} 365a4c7a4314ffbe402091695874e93d9b0a79c8099Ted Kremenek 36627b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaksbool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 36727b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks Store store, 36827b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks const MemRegion* R, 36927b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks SVal val) { 37027b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks SymbolRef SymV = val.getAsLocSymbol(); 37127b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks if (!SymV || SymV != Sym) 37227b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks return true; 37327b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks 37427b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks if (Binding) { 37527b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks First = false; 37627b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks return false; 37727b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks } 37827b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks else 37927b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks Binding = R; 38027b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks 38127b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks return true; 38227b867ea1c9cb4b40f9b817c303d6df3ee753da9Anna Zaks} 383