Store.cpp revision 48b6247804eacc262cc5508e0fbb74ed819fbb6e
1//== Store.cpp - Interface for maps from Locations to Values ----*- 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 defined the types Store and StoreManager. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 15#include "clang/StaticAnalyzer/Core/PathSensitive/Calls.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17#include "clang/AST/CharUnits.h" 18#include "clang/AST/DeclObjC.h" 19 20using namespace clang; 21using namespace ento; 22 23StoreManager::StoreManager(ProgramStateManager &stateMgr) 24 : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 25 MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 26 27StoreRef StoreManager::enterStackFrame(Store OldStore, 28 const CallEvent &Call, 29 const StackFrameContext *LCtx) { 30 StoreRef Store = StoreRef(OldStore, *this); 31 32 unsigned Idx = 0; 33 for (CallEvent::param_iterator I = Call.param_begin(/*UseDefinition=*/true), 34 E = Call.param_end(/*UseDefinition=*/true); 35 I != E; ++I, ++Idx) { 36 const ParmVarDecl *Decl = *I; 37 assert(Decl && "Formal parameter has no decl?"); 38 39 SVal ArgVal = Call.getArgSVal(Idx); 40 if (!ArgVal.isUnknown()) { 41 Store = Bind(Store.getStore(), 42 svalBuilder.makeLoc(MRMgr.getVarRegion(Decl, LCtx)), 43 ArgVal); 44 } 45 } 46 47 // FIXME: We will eventually want to generalize this to handle other non- 48 // parameter arguments besides 'this' (such as 'self' for ObjC methods). 49 SVal ThisVal = Call.getCXXThisVal(); 50 if (isa<DefinedSVal>(ThisVal)) { 51 const CXXMethodDecl *MD = cast<CXXMethodDecl>(Call.getDecl()); 52 loc::MemRegionVal ThisRegion = svalBuilder.getCXXThis(MD, LCtx); 53 Store = Bind(Store.getStore(), ThisRegion, ThisVal); 54 } 55 56 return Store; 57} 58 59const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base, 60 QualType EleTy, uint64_t index) { 61 NonLoc idx = svalBuilder.makeArrayIndex(index); 62 return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext()); 63} 64 65// FIXME: Merge with the implementation of the same method in MemRegion.cpp 66static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 67 if (const RecordType *RT = Ty->getAs<RecordType>()) { 68 const RecordDecl *D = RT->getDecl(); 69 if (!D->getDefinition()) 70 return false; 71 } 72 73 return true; 74} 75 76StoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) { 77 return StoreRef(store, *this); 78} 79 80const ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R, 81 QualType T) { 82 NonLoc idx = svalBuilder.makeZeroArrayIndex(); 83 assert(!T.isNull()); 84 return MRMgr.getElementRegion(T, idx, R, Ctx); 85} 86 87const MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) { 88 89 ASTContext &Ctx = StateMgr.getContext(); 90 91 // Handle casts to Objective-C objects. 92 if (CastToTy->isObjCObjectPointerType()) 93 return R->StripCasts(); 94 95 if (CastToTy->isBlockPointerType()) { 96 // FIXME: We may need different solutions, depending on the symbol 97 // involved. Blocks can be casted to/from 'id', as they can be treated 98 // as Objective-C objects. This could possibly be handled by enhancing 99 // our reasoning of downcasts of symbolic objects. 100 if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R)) 101 return R; 102 103 // We don't know what to make of it. Return a NULL region, which 104 // will be interpretted as UnknownVal. 105 return NULL; 106 } 107 108 // Now assume we are casting from pointer to pointer. Other cases should 109 // already be handled. 110 QualType PointeeTy = CastToTy->getPointeeType(); 111 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 112 113 // Handle casts to void*. We just pass the region through. 114 if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy) 115 return R; 116 117 // Handle casts from compatible types. 118 if (R->isBoundable()) 119 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 120 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 121 if (CanonPointeeTy == ObjTy) 122 return R; 123 } 124 125 // Process region cast according to the kind of the region being cast. 126 switch (R->getKind()) { 127 case MemRegion::CXXThisRegionKind: 128 case MemRegion::GenericMemSpaceRegionKind: 129 case MemRegion::StackLocalsSpaceRegionKind: 130 case MemRegion::StackArgumentsSpaceRegionKind: 131 case MemRegion::HeapSpaceRegionKind: 132 case MemRegion::UnknownSpaceRegionKind: 133 case MemRegion::StaticGlobalSpaceRegionKind: 134 case MemRegion::GlobalInternalSpaceRegionKind: 135 case MemRegion::GlobalSystemSpaceRegionKind: 136 case MemRegion::GlobalImmutableSpaceRegionKind: { 137 llvm_unreachable("Invalid region cast"); 138 } 139 140 case MemRegion::FunctionTextRegionKind: 141 case MemRegion::BlockTextRegionKind: 142 case MemRegion::BlockDataRegionKind: 143 case MemRegion::StringRegionKind: 144 // FIXME: Need to handle arbitrary downcasts. 145 case MemRegion::SymbolicRegionKind: 146 case MemRegion::AllocaRegionKind: 147 case MemRegion::CompoundLiteralRegionKind: 148 case MemRegion::FieldRegionKind: 149 case MemRegion::ObjCIvarRegionKind: 150 case MemRegion::ObjCStringRegionKind: 151 case MemRegion::VarRegionKind: 152 case MemRegion::CXXTempObjectRegionKind: 153 case MemRegion::CXXBaseObjectRegionKind: 154 return MakeElementRegion(R, PointeeTy); 155 156 case MemRegion::ElementRegionKind: { 157 // If we are casting from an ElementRegion to another type, the 158 // algorithm is as follows: 159 // 160 // (1) Compute the "raw offset" of the ElementRegion from the 161 // base region. This is done by calling 'getAsRawOffset()'. 162 // 163 // (2a) If we get a 'RegionRawOffset' after calling 164 // 'getAsRawOffset()', determine if the absolute offset 165 // can be exactly divided into chunks of the size of the 166 // casted-pointee type. If so, create a new ElementRegion with 167 // the pointee-cast type as the new ElementType and the index 168 // being the offset divded by the chunk size. If not, create 169 // a new ElementRegion at offset 0 off the raw offset region. 170 // 171 // (2b) If we don't a get a 'RegionRawOffset' after calling 172 // 'getAsRawOffset()', it means that we are at offset 0. 173 // 174 // FIXME: Handle symbolic raw offsets. 175 176 const ElementRegion *elementR = cast<ElementRegion>(R); 177 const RegionRawOffset &rawOff = elementR->getAsArrayOffset(); 178 const MemRegion *baseR = rawOff.getRegion(); 179 180 // If we cannot compute a raw offset, throw up our hands and return 181 // a NULL MemRegion*. 182 if (!baseR) 183 return NULL; 184 185 CharUnits off = rawOff.getOffset(); 186 187 if (off.isZero()) { 188 // Edge case: we are at 0 bytes off the beginning of baseR. We 189 // check to see if type we are casting to is the same as the base 190 // region. If so, just return the base region. 191 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(baseR)) { 192 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 193 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 194 if (CanonPointeeTy == ObjTy) 195 return baseR; 196 } 197 198 // Otherwise, create a new ElementRegion at offset 0. 199 return MakeElementRegion(baseR, PointeeTy); 200 } 201 202 // We have a non-zero offset from the base region. We want to determine 203 // if the offset can be evenly divided by sizeof(PointeeTy). If so, 204 // we create an ElementRegion whose index is that value. Otherwise, we 205 // create two ElementRegions, one that reflects a raw offset and the other 206 // that reflects the cast. 207 208 // Compute the index for the new ElementRegion. 209 int64_t newIndex = 0; 210 const MemRegion *newSuperR = 0; 211 212 // We can only compute sizeof(PointeeTy) if it is a complete type. 213 if (IsCompleteType(Ctx, PointeeTy)) { 214 // Compute the size in **bytes**. 215 CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy); 216 if (!pointeeTySize.isZero()) { 217 // Is the offset a multiple of the size? If so, we can layer the 218 // ElementRegion (with elementType == PointeeTy) directly on top of 219 // the base region. 220 if (off % pointeeTySize == 0) { 221 newIndex = off / pointeeTySize; 222 newSuperR = baseR; 223 } 224 } 225 } 226 227 if (!newSuperR) { 228 // Create an intermediate ElementRegion to represent the raw byte. 229 // This will be the super region of the final ElementRegion. 230 newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity()); 231 } 232 233 return MakeElementRegion(newSuperR, PointeeTy, newIndex); 234 } 235 } 236 237 llvm_unreachable("unreachable"); 238} 239 240 241/// CastRetrievedVal - Used by subclasses of StoreManager to implement 242/// implicit casts that arise from loads from regions that are reinterpreted 243/// as another region. 244SVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R, 245 QualType castTy, bool performTestOnly) { 246 247 if (castTy.isNull() || V.isUnknownOrUndef()) 248 return V; 249 250 ASTContext &Ctx = svalBuilder.getContext(); 251 252 if (performTestOnly) { 253 // Automatically translate references to pointers. 254 QualType T = R->getValueType(); 255 if (const ReferenceType *RT = T->getAs<ReferenceType>()) 256 T = Ctx.getPointerType(RT->getPointeeType()); 257 258 assert(svalBuilder.getContext().hasSameUnqualifiedType(castTy, T)); 259 return V; 260 } 261 262 return svalBuilder.dispatchCast(V, castTy); 263} 264 265SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) { 266 if (Base.isUnknownOrUndef()) 267 return Base; 268 269 Loc BaseL = cast<Loc>(Base); 270 const MemRegion* BaseR = 0; 271 272 switch (BaseL.getSubKind()) { 273 case loc::MemRegionKind: 274 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion(); 275 break; 276 277 case loc::GotoLabelKind: 278 // These are anormal cases. Flag an undefined value. 279 return UndefinedVal(); 280 281 case loc::ConcreteIntKind: 282 // While these seem funny, this can happen through casts. 283 // FIXME: What we should return is the field offset. For example, 284 // add the field offset to the integer value. That way funny things 285 // like this work properly: &(((struct foo *) 0xa)->f) 286 return Base; 287 288 default: 289 llvm_unreachable("Unhandled Base."); 290 } 291 292 // NOTE: We must have this check first because ObjCIvarDecl is a subclass 293 // of FieldDecl. 294 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D)) 295 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR)); 296 297 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR)); 298} 299 300SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 301 return getLValueFieldOrIvar(decl, base); 302} 303 304SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, 305 SVal Base) { 306 307 // If the base is an unknown or undefined value, just return it back. 308 // FIXME: For absolute pointer addresses, we just return that value back as 309 // well, although in reality we should return the offset added to that 310 // value. 311 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base)) 312 return Base; 313 314 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion(); 315 316 // Pointer of any type can be cast and used as array base. 317 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion); 318 319 // Convert the offset to the appropriate size and signedness. 320 Offset = cast<NonLoc>(svalBuilder.convertToArrayIndex(Offset)); 321 322 if (!ElemR) { 323 // 324 // If the base region is not an ElementRegion, create one. 325 // This can happen in the following example: 326 // 327 // char *p = __builtin_alloc(10); 328 // p[1] = 8; 329 // 330 // Observe that 'p' binds to an AllocaRegion. 331 // 332 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 333 BaseRegion, Ctx)); 334 } 335 336 SVal BaseIdx = ElemR->getIndex(); 337 338 if (!isa<nonloc::ConcreteInt>(BaseIdx)) 339 return UnknownVal(); 340 341 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue(); 342 343 // Only allow non-integer offsets if the base region has no offset itself. 344 // FIXME: This is a somewhat arbitrary restriction. We should be using 345 // SValBuilder here to add the two offsets without checking their types. 346 if (!isa<nonloc::ConcreteInt>(Offset)) { 347 if (isa<ElementRegion>(BaseRegion->StripCasts())) 348 return UnknownVal(); 349 350 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 351 ElemR->getSuperRegion(), 352 Ctx)); 353 } 354 355 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue(); 356 assert(BaseIdxI.isSigned()); 357 358 // Compute the new index. 359 nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 360 OffI)); 361 362 // Construct the new ElementRegion. 363 const MemRegion *ArrayR = ElemR->getSuperRegion(); 364 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 365 Ctx)); 366} 367 368StoreManager::BindingsHandler::~BindingsHandler() {} 369 370bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 371 Store store, 372 const MemRegion* R, 373 SVal val) { 374 SymbolRef SymV = val.getAsLocSymbol(); 375 if (!SymV || SymV != Sym) 376 return true; 377 378 if (Binding) { 379 First = false; 380 return false; 381 } 382 else 383 Binding = R; 384 385 return true; 386} 387 388void SubRegionMap::anchor() { } 389void SubRegionMap::Visitor::anchor() { } 390