1 //== MemRegion.cpp - Abstract memory regions for static analysis --*- 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 MemRegion and its subclasses. MemRegion defines a 11 // partially-typed abstraction of memory useful for path-sensitive dataflow 12 // analyses. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 17 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 18 #include "clang/Analysis/AnalysisContext.h" 19 #include "clang/Analysis/Support/BumpVector.h" 20 #include "clang/AST/CharUnits.h" 21 #include "clang/AST/DeclObjC.h" 22 #include "clang/AST/RecordLayout.h" 23 #include "clang/Basic/SourceManager.h" 24 #include "llvm/Support/raw_ostream.h" 25 26 using namespace clang; 27 using namespace ento; 28 29 //===----------------------------------------------------------------------===// 30 // MemRegion Construction. 31 //===----------------------------------------------------------------------===// 32 33 template<typename RegionTy> struct MemRegionManagerTrait; 34 35 template <typename RegionTy, typename A1> 36 RegionTy* MemRegionManager::getRegion(const A1 a1) { 37 38 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = 39 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1); 40 41 llvm::FoldingSetNodeID ID; 42 RegionTy::ProfileRegion(ID, a1, superRegion); 43 void *InsertPos; 44 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 45 InsertPos)); 46 47 if (!R) { 48 R = (RegionTy*) A.Allocate<RegionTy>(); 49 new (R) RegionTy(a1, superRegion); 50 Regions.InsertNode(R, InsertPos); 51 } 52 53 return R; 54 } 55 56 template <typename RegionTy, typename A1> 57 RegionTy* MemRegionManager::getSubRegion(const A1 a1, 58 const MemRegion *superRegion) { 59 llvm::FoldingSetNodeID ID; 60 RegionTy::ProfileRegion(ID, a1, superRegion); 61 void *InsertPos; 62 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 63 InsertPos)); 64 65 if (!R) { 66 R = (RegionTy*) A.Allocate<RegionTy>(); 67 new (R) RegionTy(a1, superRegion); 68 Regions.InsertNode(R, InsertPos); 69 } 70 71 return R; 72 } 73 74 template <typename RegionTy, typename A1, typename A2> 75 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) { 76 77 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = 78 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2); 79 80 llvm::FoldingSetNodeID ID; 81 RegionTy::ProfileRegion(ID, a1, a2, superRegion); 82 void *InsertPos; 83 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 84 InsertPos)); 85 86 if (!R) { 87 R = (RegionTy*) A.Allocate<RegionTy>(); 88 new (R) RegionTy(a1, a2, superRegion); 89 Regions.InsertNode(R, InsertPos); 90 } 91 92 return R; 93 } 94 95 template <typename RegionTy, typename A1, typename A2> 96 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, 97 const MemRegion *superRegion) { 98 99 llvm::FoldingSetNodeID ID; 100 RegionTy::ProfileRegion(ID, a1, a2, superRegion); 101 void *InsertPos; 102 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 103 InsertPos)); 104 105 if (!R) { 106 R = (RegionTy*) A.Allocate<RegionTy>(); 107 new (R) RegionTy(a1, a2, superRegion); 108 Regions.InsertNode(R, InsertPos); 109 } 110 111 return R; 112 } 113 114 template <typename RegionTy, typename A1, typename A2, typename A3> 115 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3, 116 const MemRegion *superRegion) { 117 118 llvm::FoldingSetNodeID ID; 119 RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion); 120 void *InsertPos; 121 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 122 InsertPos)); 123 124 if (!R) { 125 R = (RegionTy*) A.Allocate<RegionTy>(); 126 new (R) RegionTy(a1, a2, a3, superRegion); 127 Regions.InsertNode(R, InsertPos); 128 } 129 130 return R; 131 } 132 133 //===----------------------------------------------------------------------===// 134 // Object destruction. 135 //===----------------------------------------------------------------------===// 136 137 MemRegion::~MemRegion() {} 138 139 MemRegionManager::~MemRegionManager() { 140 // All regions and their data are BumpPtrAllocated. No need to call 141 // their destructors. 142 } 143 144 //===----------------------------------------------------------------------===// 145 // Basic methods. 146 //===----------------------------------------------------------------------===// 147 148 bool SubRegion::isSubRegionOf(const MemRegion* R) const { 149 const MemRegion* r = getSuperRegion(); 150 while (r != 0) { 151 if (r == R) 152 return true; 153 if (const SubRegion* sr = dyn_cast<SubRegion>(r)) 154 r = sr->getSuperRegion(); 155 else 156 break; 157 } 158 return false; 159 } 160 161 MemRegionManager* SubRegion::getMemRegionManager() const { 162 const SubRegion* r = this; 163 do { 164 const MemRegion *superRegion = r->getSuperRegion(); 165 if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) { 166 r = sr; 167 continue; 168 } 169 return superRegion->getMemRegionManager(); 170 } while (1); 171 } 172 173 const StackFrameContext *VarRegion::getStackFrame() const { 174 const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace()); 175 return SSR ? SSR->getStackFrame() : NULL; 176 } 177 178 //===----------------------------------------------------------------------===// 179 // Region extents. 180 //===----------------------------------------------------------------------===// 181 182 DefinedOrUnknownSVal DeclRegion::getExtent(SValBuilder &svalBuilder) const { 183 ASTContext &Ctx = svalBuilder.getContext(); 184 QualType T = getDesugaredValueType(Ctx); 185 186 if (isa<VariableArrayType>(T)) 187 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 188 if (isa<IncompleteArrayType>(T)) 189 return UnknownVal(); 190 191 CharUnits size = Ctx.getTypeSizeInChars(T); 192 QualType sizeTy = svalBuilder.getArrayIndexType(); 193 return svalBuilder.makeIntVal(size.getQuantity(), sizeTy); 194 } 195 196 DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const { 197 DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder); 198 199 // A zero-length array at the end of a struct often stands for dynamically- 200 // allocated extra memory. 201 if (Extent.isZeroConstant()) { 202 QualType T = getDesugaredValueType(svalBuilder.getContext()); 203 204 if (isa<ConstantArrayType>(T)) 205 return UnknownVal(); 206 } 207 208 return Extent; 209 } 210 211 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const { 212 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 213 } 214 215 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const { 216 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 217 } 218 219 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const { 220 return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1, 221 svalBuilder.getArrayIndexType()); 222 } 223 224 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg) 225 : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} 226 227 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const { 228 return cast<ObjCIvarDecl>(D); 229 } 230 231 QualType ObjCIvarRegion::getValueType() const { 232 return getDecl()->getType(); 233 } 234 235 QualType CXXBaseObjectRegion::getValueType() const { 236 return QualType(decl->getTypeForDecl(), 0); 237 } 238 239 //===----------------------------------------------------------------------===// 240 // FoldingSet profiling. 241 //===----------------------------------------------------------------------===// 242 243 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const { 244 ID.AddInteger((unsigned)getKind()); 245 } 246 247 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 248 ID.AddInteger((unsigned)getKind()); 249 ID.AddPointer(getStackFrame()); 250 } 251 252 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 253 ID.AddInteger((unsigned)getKind()); 254 ID.AddPointer(getCodeRegion()); 255 } 256 257 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 258 const StringLiteral* Str, 259 const MemRegion* superRegion) { 260 ID.AddInteger((unsigned) StringRegionKind); 261 ID.AddPointer(Str); 262 ID.AddPointer(superRegion); 263 } 264 265 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 266 const ObjCStringLiteral* Str, 267 const MemRegion* superRegion) { 268 ID.AddInteger((unsigned) ObjCStringRegionKind); 269 ID.AddPointer(Str); 270 ID.AddPointer(superRegion); 271 } 272 273 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 274 const Expr *Ex, unsigned cnt, 275 const MemRegion *) { 276 ID.AddInteger((unsigned) AllocaRegionKind); 277 ID.AddPointer(Ex); 278 ID.AddInteger(cnt); 279 } 280 281 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const { 282 ProfileRegion(ID, Ex, Cnt, superRegion); 283 } 284 285 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const { 286 CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion); 287 } 288 289 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 290 const CompoundLiteralExpr *CL, 291 const MemRegion* superRegion) { 292 ID.AddInteger((unsigned) CompoundLiteralRegionKind); 293 ID.AddPointer(CL); 294 ID.AddPointer(superRegion); 295 } 296 297 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 298 const PointerType *PT, 299 const MemRegion *sRegion) { 300 ID.AddInteger((unsigned) CXXThisRegionKind); 301 ID.AddPointer(PT); 302 ID.AddPointer(sRegion); 303 } 304 305 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const { 306 CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion); 307 } 308 309 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 310 const ObjCIvarDecl *ivd, 311 const MemRegion* superRegion) { 312 DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); 313 } 314 315 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D, 316 const MemRegion* superRegion, Kind k) { 317 ID.AddInteger((unsigned) k); 318 ID.AddPointer(D); 319 ID.AddPointer(superRegion); 320 } 321 322 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const { 323 DeclRegion::ProfileRegion(ID, D, superRegion, getKind()); 324 } 325 326 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const { 327 VarRegion::ProfileRegion(ID, getDecl(), superRegion); 328 } 329 330 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym, 331 const MemRegion *sreg) { 332 ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind); 333 ID.Add(sym); 334 ID.AddPointer(sreg); 335 } 336 337 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const { 338 SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion()); 339 } 340 341 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 342 QualType ElementType, SVal Idx, 343 const MemRegion* superRegion) { 344 ID.AddInteger(MemRegion::ElementRegionKind); 345 ID.Add(ElementType); 346 ID.AddPointer(superRegion); 347 Idx.Profile(ID); 348 } 349 350 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const { 351 ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion); 352 } 353 354 void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 355 const FunctionDecl *FD, 356 const MemRegion*) { 357 ID.AddInteger(MemRegion::FunctionTextRegionKind); 358 ID.AddPointer(FD); 359 } 360 361 void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { 362 FunctionTextRegion::ProfileRegion(ID, FD, superRegion); 363 } 364 365 void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 366 const BlockDecl *BD, CanQualType, 367 const AnalysisDeclContext *AC, 368 const MemRegion*) { 369 ID.AddInteger(MemRegion::BlockTextRegionKind); 370 ID.AddPointer(BD); 371 } 372 373 void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { 374 BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion); 375 } 376 377 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 378 const BlockTextRegion *BC, 379 const LocationContext *LC, 380 const MemRegion *sReg) { 381 ID.AddInteger(MemRegion::BlockDataRegionKind); 382 ID.AddPointer(BC); 383 ID.AddPointer(LC); 384 ID.AddPointer(sReg); 385 } 386 387 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const { 388 BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion()); 389 } 390 391 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 392 Expr const *Ex, 393 const MemRegion *sReg) { 394 ID.AddPointer(Ex); 395 ID.AddPointer(sReg); 396 } 397 398 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 399 ProfileRegion(ID, Ex, getSuperRegion()); 400 } 401 402 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 403 const CXXRecordDecl *decl, 404 const MemRegion *sReg) { 405 ID.AddPointer(decl); 406 ID.AddPointer(sReg); 407 } 408 409 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 410 ProfileRegion(ID, decl, superRegion); 411 } 412 413 //===----------------------------------------------------------------------===// 414 // Region anchors. 415 //===----------------------------------------------------------------------===// 416 417 void GlobalsSpaceRegion::anchor() { } 418 void HeapSpaceRegion::anchor() { } 419 void UnknownSpaceRegion::anchor() { } 420 void StackLocalsSpaceRegion::anchor() { } 421 void StackArgumentsSpaceRegion::anchor() { } 422 void TypedRegion::anchor() { } 423 void TypedValueRegion::anchor() { } 424 void CodeTextRegion::anchor() { } 425 void SubRegion::anchor() { } 426 427 //===----------------------------------------------------------------------===// 428 // Region pretty-printing. 429 //===----------------------------------------------------------------------===// 430 431 void MemRegion::dump() const { 432 dumpToStream(llvm::errs()); 433 } 434 435 std::string MemRegion::getString() const { 436 std::string s; 437 llvm::raw_string_ostream os(s); 438 dumpToStream(os); 439 return os.str(); 440 } 441 442 void MemRegion::dumpToStream(raw_ostream &os) const { 443 os << "<Unknown Region>"; 444 } 445 446 void AllocaRegion::dumpToStream(raw_ostream &os) const { 447 os << "alloca{" << (void*) Ex << ',' << Cnt << '}'; 448 } 449 450 void FunctionTextRegion::dumpToStream(raw_ostream &os) const { 451 os << "code{" << getDecl()->getDeclName().getAsString() << '}'; 452 } 453 454 void BlockTextRegion::dumpToStream(raw_ostream &os) const { 455 os << "block_code{" << (void*) this << '}'; 456 } 457 458 void BlockDataRegion::dumpToStream(raw_ostream &os) const { 459 os << "block_data{" << BC << '}'; 460 } 461 462 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { 463 // FIXME: More elaborate pretty-printing. 464 os << "{ " << (void*) CL << " }"; 465 } 466 467 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { 468 os << "temp_object{" << getValueType().getAsString() << ',' 469 << (void*) Ex << '}'; 470 } 471 472 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const { 473 os << "base " << decl->getName(); 474 } 475 476 void CXXThisRegion::dumpToStream(raw_ostream &os) const { 477 os << "this"; 478 } 479 480 void ElementRegion::dumpToStream(raw_ostream &os) const { 481 os << "element{" << superRegion << ',' 482 << Index << ',' << getElementType().getAsString() << '}'; 483 } 484 485 void FieldRegion::dumpToStream(raw_ostream &os) const { 486 os << superRegion << "->" << *getDecl(); 487 } 488 489 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const { 490 os << "ivar{" << superRegion << ',' << *getDecl() << '}'; 491 } 492 493 void StringRegion::dumpToStream(raw_ostream &os) const { 494 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts())); 495 } 496 497 void ObjCStringRegion::dumpToStream(raw_ostream &os) const { 498 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts())); 499 } 500 501 void SymbolicRegion::dumpToStream(raw_ostream &os) const { 502 os << "SymRegion{" << sym << '}'; 503 } 504 505 void VarRegion::dumpToStream(raw_ostream &os) const { 506 os << *cast<VarDecl>(D); 507 } 508 509 void RegionRawOffset::dump() const { 510 dumpToStream(llvm::errs()); 511 } 512 513 void RegionRawOffset::dumpToStream(raw_ostream &os) const { 514 os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}'; 515 } 516 517 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const { 518 os << "StaticGlobalsMemSpace{" << CR << '}'; 519 } 520 521 void NonStaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const { 522 os << "NonStaticGlobalSpaceRegion"; 523 } 524 525 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const { 526 os << "GlobalInternalSpaceRegion"; 527 } 528 529 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const { 530 os << "GlobalSystemSpaceRegion"; 531 } 532 533 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const { 534 os << "GlobalImmutableSpaceRegion"; 535 } 536 537 void MemRegion::dumpPretty(raw_ostream &os) const { 538 return; 539 } 540 541 void VarRegion::dumpPretty(raw_ostream &os) const { 542 os << getDecl()->getName(); 543 } 544 545 void FieldRegion::dumpPretty(raw_ostream &os) const { 546 superRegion->dumpPretty(os); 547 os << "->" << getDecl(); 548 } 549 550 //===----------------------------------------------------------------------===// 551 // MemRegionManager methods. 552 //===----------------------------------------------------------------------===// 553 554 template <typename REG> 555 const REG *MemRegionManager::LazyAllocate(REG*& region) { 556 if (!region) { 557 region = (REG*) A.Allocate<REG>(); 558 new (region) REG(this); 559 } 560 561 return region; 562 } 563 564 template <typename REG, typename ARG> 565 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) { 566 if (!region) { 567 region = (REG*) A.Allocate<REG>(); 568 new (region) REG(this, a); 569 } 570 571 return region; 572 } 573 574 const StackLocalsSpaceRegion* 575 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) { 576 assert(STC); 577 StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC]; 578 579 if (R) 580 return R; 581 582 R = A.Allocate<StackLocalsSpaceRegion>(); 583 new (R) StackLocalsSpaceRegion(this, STC); 584 return R; 585 } 586 587 const StackArgumentsSpaceRegion * 588 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) { 589 assert(STC); 590 StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC]; 591 592 if (R) 593 return R; 594 595 R = A.Allocate<StackArgumentsSpaceRegion>(); 596 new (R) StackArgumentsSpaceRegion(this, STC); 597 return R; 598 } 599 600 const GlobalsSpaceRegion 601 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K, 602 const CodeTextRegion *CR) { 603 if (!CR) { 604 if (K == MemRegion::GlobalSystemSpaceRegionKind) 605 return LazyAllocate(SystemGlobals); 606 if (K == MemRegion::GlobalImmutableSpaceRegionKind) 607 return LazyAllocate(ImmutableGlobals); 608 assert(K == MemRegion::GlobalInternalSpaceRegionKind); 609 return LazyAllocate(InternalGlobals); 610 } 611 612 assert(K == MemRegion::StaticGlobalSpaceRegionKind); 613 StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR]; 614 if (R) 615 return R; 616 617 R = A.Allocate<StaticGlobalSpaceRegion>(); 618 new (R) StaticGlobalSpaceRegion(this, CR); 619 return R; 620 } 621 622 const HeapSpaceRegion *MemRegionManager::getHeapRegion() { 623 return LazyAllocate(heap); 624 } 625 626 const MemSpaceRegion *MemRegionManager::getUnknownRegion() { 627 return LazyAllocate(unknown); 628 } 629 630 const MemSpaceRegion *MemRegionManager::getCodeRegion() { 631 return LazyAllocate(code); 632 } 633 634 //===----------------------------------------------------------------------===// 635 // Constructing regions. 636 //===----------------------------------------------------------------------===// 637 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){ 638 return getSubRegion<StringRegion>(Str, getGlobalsRegion()); 639 } 640 641 const ObjCStringRegion * 642 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){ 643 return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion()); 644 } 645 646 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, 647 const LocationContext *LC) { 648 const MemRegion *sReg = 0; 649 650 if (D->hasGlobalStorage() && !D->isStaticLocal()) { 651 652 // First handle the globals defined in system headers. 653 if (C.getSourceManager().isInSystemHeader(D->getLocation())) { 654 // Whitelist the system globals which often DO GET modified, assume the 655 // rest are immutable. 656 if (D->getName().find("errno") != StringRef::npos) 657 sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind); 658 else 659 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 660 661 // Treat other globals as GlobalInternal unless they are constants. 662 } else { 663 QualType GQT = D->getType(); 664 const Type *GT = GQT.getTypePtrOrNull(); 665 // TODO: We could walk the complex types here and see if everything is 666 // constified. 667 if (GT && GQT.isConstQualified() && GT->isArithmeticType()) 668 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 669 else 670 sReg = getGlobalsRegion(); 671 } 672 673 // Finally handle static locals. 674 } else { 675 // FIXME: Once we implement scope handling, we will need to properly lookup 676 // 'D' to the proper LocationContext. 677 const DeclContext *DC = D->getDeclContext(); 678 const StackFrameContext *STC = LC->getStackFrameForDeclContext(DC); 679 680 if (!STC) 681 sReg = getUnknownRegion(); 682 else { 683 if (D->hasLocalStorage()) { 684 sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D) 685 ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC)) 686 : static_cast<const MemRegion*>(getStackLocalsRegion(STC)); 687 } 688 else { 689 assert(D->isStaticLocal()); 690 const Decl *D = STC->getDecl(); 691 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) 692 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, 693 getFunctionTextRegion(FD)); 694 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { 695 const BlockTextRegion *BTR = 696 getBlockTextRegion(BD, 697 C.getCanonicalType(BD->getSignatureAsWritten()->getType()), 698 STC->getAnalysisDeclContext()); 699 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, 700 BTR); 701 } 702 else { 703 // FIXME: For ObjC-methods, we need a new CodeTextRegion. For now 704 // just use the main global memspace. 705 sReg = getGlobalsRegion(); 706 } 707 } 708 } 709 } 710 711 return getSubRegion<VarRegion>(D, sReg); 712 } 713 714 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D, 715 const MemRegion *superR) { 716 return getSubRegion<VarRegion>(D, superR); 717 } 718 719 const BlockDataRegion * 720 MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, 721 const LocationContext *LC) { 722 const MemRegion *sReg = 0; 723 const BlockDecl *BD = BC->getDecl(); 724 if (!BD->hasCaptures()) { 725 // This handles 'static' blocks. 726 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 727 } 728 else { 729 if (LC) { 730 // FIXME: Once we implement scope handling, we want the parent region 731 // to be the scope. 732 const StackFrameContext *STC = LC->getCurrentStackFrame(); 733 assert(STC); 734 sReg = getStackLocalsRegion(STC); 735 } 736 else { 737 // We allow 'LC' to be NULL for cases where want BlockDataRegions 738 // without context-sensitivity. 739 sReg = getUnknownRegion(); 740 } 741 } 742 743 return getSubRegion<BlockDataRegion>(BC, LC, sReg); 744 } 745 746 const CompoundLiteralRegion* 747 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL, 748 const LocationContext *LC) { 749 750 const MemRegion *sReg = 0; 751 752 if (CL->isFileScope()) 753 sReg = getGlobalsRegion(); 754 else { 755 const StackFrameContext *STC = LC->getCurrentStackFrame(); 756 assert(STC); 757 sReg = getStackLocalsRegion(STC); 758 } 759 760 return getSubRegion<CompoundLiteralRegion>(CL, sReg); 761 } 762 763 const ElementRegion* 764 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx, 765 const MemRegion* superRegion, 766 ASTContext &Ctx){ 767 768 QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType(); 769 770 llvm::FoldingSetNodeID ID; 771 ElementRegion::ProfileRegion(ID, T, Idx, superRegion); 772 773 void *InsertPos; 774 MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); 775 ElementRegion* R = cast_or_null<ElementRegion>(data); 776 777 if (!R) { 778 R = (ElementRegion*) A.Allocate<ElementRegion>(); 779 new (R) ElementRegion(T, Idx, superRegion); 780 Regions.InsertNode(R, InsertPos); 781 } 782 783 return R; 784 } 785 786 const FunctionTextRegion * 787 MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) { 788 return getSubRegion<FunctionTextRegion>(FD, getCodeRegion()); 789 } 790 791 const BlockTextRegion * 792 MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy, 793 AnalysisDeclContext *AC) { 794 return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion()); 795 } 796 797 798 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region. 799 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) { 800 return getSubRegion<SymbolicRegion>(sym, getUnknownRegion()); 801 } 802 803 const FieldRegion* 804 MemRegionManager::getFieldRegion(const FieldDecl *d, 805 const MemRegion* superRegion){ 806 return getSubRegion<FieldRegion>(d, superRegion); 807 } 808 809 const ObjCIvarRegion* 810 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d, 811 const MemRegion* superRegion) { 812 return getSubRegion<ObjCIvarRegion>(d, superRegion); 813 } 814 815 const CXXTempObjectRegion* 816 MemRegionManager::getCXXTempObjectRegion(Expr const *E, 817 LocationContext const *LC) { 818 const StackFrameContext *SFC = LC->getCurrentStackFrame(); 819 assert(SFC); 820 return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC)); 821 } 822 823 const CXXBaseObjectRegion * 824 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl, 825 const MemRegion *superRegion) { 826 return getSubRegion<CXXBaseObjectRegion>(decl, superRegion); 827 } 828 829 const CXXThisRegion* 830 MemRegionManager::getCXXThisRegion(QualType thisPointerTy, 831 const LocationContext *LC) { 832 const StackFrameContext *STC = LC->getCurrentStackFrame(); 833 assert(STC); 834 const PointerType *PT = thisPointerTy->getAs<PointerType>(); 835 assert(PT); 836 return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC)); 837 } 838 839 const AllocaRegion* 840 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt, 841 const LocationContext *LC) { 842 const StackFrameContext *STC = LC->getCurrentStackFrame(); 843 assert(STC); 844 return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC)); 845 } 846 847 const MemSpaceRegion *MemRegion::getMemorySpace() const { 848 const MemRegion *R = this; 849 const SubRegion* SR = dyn_cast<SubRegion>(this); 850 851 while (SR) { 852 R = SR->getSuperRegion(); 853 SR = dyn_cast<SubRegion>(R); 854 } 855 856 return dyn_cast<MemSpaceRegion>(R); 857 } 858 859 bool MemRegion::hasStackStorage() const { 860 return isa<StackSpaceRegion>(getMemorySpace()); 861 } 862 863 bool MemRegion::hasStackNonParametersStorage() const { 864 return isa<StackLocalsSpaceRegion>(getMemorySpace()); 865 } 866 867 bool MemRegion::hasStackParametersStorage() const { 868 return isa<StackArgumentsSpaceRegion>(getMemorySpace()); 869 } 870 871 bool MemRegion::hasGlobalsOrParametersStorage() const { 872 const MemSpaceRegion *MS = getMemorySpace(); 873 return isa<StackArgumentsSpaceRegion>(MS) || 874 isa<GlobalsSpaceRegion>(MS); 875 } 876 877 // getBaseRegion strips away all elements and fields, and get the base region 878 // of them. 879 const MemRegion *MemRegion::getBaseRegion() const { 880 const MemRegion *R = this; 881 while (true) { 882 switch (R->getKind()) { 883 case MemRegion::ElementRegionKind: 884 case MemRegion::FieldRegionKind: 885 case MemRegion::ObjCIvarRegionKind: 886 case MemRegion::CXXBaseObjectRegionKind: 887 R = cast<SubRegion>(R)->getSuperRegion(); 888 continue; 889 default: 890 break; 891 } 892 break; 893 } 894 return R; 895 } 896 897 //===----------------------------------------------------------------------===// 898 // View handling. 899 //===----------------------------------------------------------------------===// 900 901 const MemRegion *MemRegion::StripCasts() const { 902 const MemRegion *R = this; 903 while (true) { 904 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 905 // FIXME: generalize. Essentially we want to strip away ElementRegions 906 // that were layered on a symbolic region because of casts. We only 907 // want to strip away ElementRegions, however, where the index is 0. 908 SVal index = ER->getIndex(); 909 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) { 910 if (CI->getValue().getSExtValue() == 0) { 911 R = ER->getSuperRegion(); 912 continue; 913 } 914 } 915 } 916 break; 917 } 918 return R; 919 } 920 921 // FIXME: Merge with the implementation of the same method in Store.cpp 922 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 923 if (const RecordType *RT = Ty->getAs<RecordType>()) { 924 const RecordDecl *D = RT->getDecl(); 925 if (!D->getDefinition()) 926 return false; 927 } 928 929 return true; 930 } 931 932 RegionRawOffset ElementRegion::getAsArrayOffset() const { 933 CharUnits offset = CharUnits::Zero(); 934 const ElementRegion *ER = this; 935 const MemRegion *superR = NULL; 936 ASTContext &C = getContext(); 937 938 // FIXME: Handle multi-dimensional arrays. 939 940 while (ER) { 941 superR = ER->getSuperRegion(); 942 943 // FIXME: generalize to symbolic offsets. 944 SVal index = ER->getIndex(); 945 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) { 946 // Update the offset. 947 int64_t i = CI->getValue().getSExtValue(); 948 949 if (i != 0) { 950 QualType elemType = ER->getElementType(); 951 952 // If we are pointing to an incomplete type, go no further. 953 if (!IsCompleteType(C, elemType)) { 954 superR = ER; 955 break; 956 } 957 958 CharUnits size = C.getTypeSizeInChars(elemType); 959 offset += (i * size); 960 } 961 962 // Go to the next ElementRegion (if any). 963 ER = dyn_cast<ElementRegion>(superR); 964 continue; 965 } 966 967 return NULL; 968 } 969 970 assert(superR && "super region cannot be NULL"); 971 return RegionRawOffset(superR, offset); 972 } 973 974 RegionOffset MemRegion::getAsOffset() const { 975 const MemRegion *R = this; 976 int64_t Offset = 0; 977 978 while (1) { 979 switch (R->getKind()) { 980 default: 981 return RegionOffset(0); 982 case SymbolicRegionKind: 983 case AllocaRegionKind: 984 case CompoundLiteralRegionKind: 985 case CXXThisRegionKind: 986 case StringRegionKind: 987 case VarRegionKind: 988 case CXXTempObjectRegionKind: 989 goto Finish; 990 case ElementRegionKind: { 991 const ElementRegion *ER = cast<ElementRegion>(R); 992 QualType EleTy = ER->getValueType(); 993 994 if (!IsCompleteType(getContext(), EleTy)) 995 return RegionOffset(0); 996 997 SVal Index = ER->getIndex(); 998 if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) { 999 int64_t i = CI->getValue().getSExtValue(); 1000 CharUnits Size = getContext().getTypeSizeInChars(EleTy); 1001 Offset += i * Size.getQuantity() * 8; 1002 } else { 1003 // We cannot compute offset for non-concrete index. 1004 return RegionOffset(0); 1005 } 1006 R = ER->getSuperRegion(); 1007 break; 1008 } 1009 case FieldRegionKind: { 1010 const FieldRegion *FR = cast<FieldRegion>(R); 1011 const RecordDecl *RD = FR->getDecl()->getParent(); 1012 if (!RD->isCompleteDefinition()) 1013 // We cannot compute offset for incomplete type. 1014 return RegionOffset(0); 1015 // Get the field number. 1016 unsigned idx = 0; 1017 for (RecordDecl::field_iterator FI = RD->field_begin(), 1018 FE = RD->field_end(); FI != FE; ++FI, ++idx) 1019 if (FR->getDecl() == *FI) 1020 break; 1021 1022 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD); 1023 // This is offset in bits. 1024 Offset += Layout.getFieldOffset(idx); 1025 R = FR->getSuperRegion(); 1026 break; 1027 } 1028 } 1029 } 1030 1031 Finish: 1032 return RegionOffset(R, Offset); 1033 } 1034 1035 //===----------------------------------------------------------------------===// 1036 // BlockDataRegion 1037 //===----------------------------------------------------------------------===// 1038 1039 void BlockDataRegion::LazyInitializeReferencedVars() { 1040 if (ReferencedVars) 1041 return; 1042 1043 AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext(); 1044 AnalysisDeclContext::referenced_decls_iterator I, E; 1045 llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl()); 1046 1047 if (I == E) { 1048 ReferencedVars = (void*) 0x1; 1049 return; 1050 } 1051 1052 MemRegionManager &MemMgr = *getMemRegionManager(); 1053 llvm::BumpPtrAllocator &A = MemMgr.getAllocator(); 1054 BumpVectorContext BC(A); 1055 1056 typedef BumpVector<const MemRegion*> VarVec; 1057 VarVec *BV = (VarVec*) A.Allocate<VarVec>(); 1058 new (BV) VarVec(BC, E - I); 1059 1060 for ( ; I != E; ++I) { 1061 const VarDecl *VD = *I; 1062 const VarRegion *VR = 0; 1063 1064 if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) 1065 VR = MemMgr.getVarRegion(VD, this); 1066 else { 1067 if (LC) 1068 VR = MemMgr.getVarRegion(VD, LC); 1069 else { 1070 VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion()); 1071 } 1072 } 1073 1074 assert(VR); 1075 BV->push_back(VR, BC); 1076 } 1077 1078 ReferencedVars = BV; 1079 } 1080 1081 BlockDataRegion::referenced_vars_iterator 1082 BlockDataRegion::referenced_vars_begin() const { 1083 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars(); 1084 1085 BumpVector<const MemRegion*> *Vec = 1086 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); 1087 1088 return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ? 1089 NULL : Vec->begin()); 1090 } 1091 1092 BlockDataRegion::referenced_vars_iterator 1093 BlockDataRegion::referenced_vars_end() const { 1094 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars(); 1095 1096 BumpVector<const MemRegion*> *Vec = 1097 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); 1098 1099 return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ? 1100 NULL : Vec->end()); 1101 } 1102