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