1d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 3d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// The LLVM Compiler Infrastructure 4d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 5d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// This file is distributed under the University of Illinois Open Source 6d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// License. See LICENSE.TXT for details. 7d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 8d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//===----------------------------------------------------------------------===// 9d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 10843e934ba8c6ebc00d2f6969a50af7074597e8e3Gabor Greif// This file defines SymbolManager, a class that manages symbolic values 11d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// created for use by ExprEngine and related classes. 12d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 13d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//===----------------------------------------------------------------------===// 14d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 159b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 165e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer#include "clang/Analysis/Analyses/LiveVariables.h" 179b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 18882998923889a2fcce9b49696506c499e22cf38fTed Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 19562731eabbed616535874c99655c81cc55d713fbTed Kremenek#include "llvm/Support/raw_ostream.h" 20d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 21d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenekusing namespace clang; 229ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 23d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 2499ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid SymExpr::anchor() { } 2599ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 268800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenekvoid SymExpr::dump() const { 278800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek dumpToStream(llvm::errs()); 288800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek} 29e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 309c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymIntExpr::dumpToStream(raw_ostream &os) const { 31e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << '('; 328800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek getLHS()->dumpToStream(os); 3305cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << ") " 3405cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose << BinaryOperator::getOpcodeStr(getOpcode()) << ' ' 3505cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose << getRHS().getZExtValue(); 3605cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose if (getRHS().isUnsigned()) 3705cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << 'U'; 38e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaksvoid IntSymExpr::dumpToStream(raw_ostream &os) const { 4105cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << getLHS().getZExtValue(); 4205cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose if (getLHS().isUnsigned()) 4305cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << 'U'; 4405cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << ' ' 4505cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose << BinaryOperator::getOpcodeStr(getOpcode()) 4605cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose << " ("; 4724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks getRHS()->dumpToStream(os); 4805cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << ')'; 4924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks} 5024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 519c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymSymExpr::dumpToStream(raw_ostream &os) const { 52e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << '('; 538800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek getLHS()->dumpToStream(os); 5405cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose os << ") " 5505cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose << BinaryOperator::getOpcodeStr(getOpcode()) 5605cb2eb0a79a05e6079106575fbf0dd58a388edfJordan Rose << " ("; 578800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek getRHS()->dumpToStream(os); 581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump os << ')'; 59e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 60e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 61aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaksvoid SymbolCast::dumpToStream(raw_ostream &os) const { 62aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks os << '(' << ToTy.getAsString() << ") ("; 63aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks Operand->dumpToStream(os); 64aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks os << ')'; 65aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks} 66aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 679c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolConjured::dumpToStream(raw_ostream &os) const { 6819e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 69e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 70e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 719c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolDerived::dumpToStream(raw_ostream &os) const { 72fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek os << "derived_$" << getSymbolID() << '{' 73fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek << getParentSymbol() << ',' << getRegion() << '}'; 74fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek} 75fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 769c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolExtent::dumpToStream(raw_ostream &os) const { 7732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 7832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 7932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 809c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolMetadata::dumpToStream(raw_ostream &os) const { 81bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose os << "meta_$" << getSymbolID() << '{' 82bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose << getRegion() << ',' << T.getAsString() << '}'; 83bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 84bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 8599ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid SymbolData::anchor() { } 8699ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 879c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolRegionValue::dumpToStream(raw_ostream &os) const { 888800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek os << "reg_$" << getSymbolID() << "<" << R << ">"; 8994c969804b1f98650316a8f75434b2d24dbe94eaTed Kremenek} 9094c969804b1f98650316a8f75434b2d24dbe94eaTed Kremenek 911d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaksbool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 921d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return itr == X.itr; 931d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 941d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 951d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaksbool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 961d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return itr != X.itr; 971d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 981d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 991d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna ZaksSymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 1001d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks itr.push_back(SE); 1011d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1021d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1031d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna ZaksSymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 1041d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 1050073a5c7ce38e98365c00921316030627b3d129fJordan Rose expand(); 1061d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return *this; 1071d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1081d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1091d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna ZaksSymbolRef SymExpr::symbol_iterator::operator*() { 1101d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 1110073a5c7ce38e98365c00921316030627b3d129fJordan Rose return itr.back(); 1121d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1131d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1141d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaksvoid SymExpr::symbol_iterator::expand() { 1151d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks const SymExpr *SE = itr.back(); 1161d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks itr.pop_back(); 1171d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 11824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks switch (SE->getKind()) { 11924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::RegionValueKind: 12024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::ConjuredKind: 12124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::DerivedKind: 12224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::ExtentKind: 12324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::MetadataKind: 12424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 12524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::CastSymbolKind: 12624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(cast<SymbolCast>(SE)->getOperand()); 12724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 12824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::SymIntKind: 12924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 13024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 13124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::IntSymKind: 13224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 13324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 13424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::SymSymKind: { 13524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks const SymSymExpr *x = cast<SymSymExpr>(SE); 13624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(x->getLHS()); 13724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(x->getRHS()); 13824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 13924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks } 1401d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks } 1411d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks llvm_unreachable("unhandled expansion case"); 1421d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1431d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 144baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaksunsigned SymExpr::computeComplexity() const { 145baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks unsigned R = 0; 146baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I) 147baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks R++; 148baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks return R; 149baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks} 150baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks 1511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpconst SymbolRegionValue* 1529697934650354bed2e509d8e7e44f21a1fb00f76Ted KremenekSymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 15300a3a5f024ac54088ab887712b292171188064f0Ted Kremenek llvm::FoldingSetNodeID profile; 15414d2328ecfc5102b077fa2c2c129dce1574c8831Zhongxing Xu SymbolRegionValue::Profile(profile, R); 1559c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 1561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 1571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!SD) { 158d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 15914d2328ecfc5102b077fa2c2c129dce1574c8831Zhongxing Xu new (SD) SymbolRegionValue(SymbolCounter, R); 160e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek DataSet.InsertNode(SD, InsertPos); 161e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ++SymbolCounter; 162e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 1631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 164d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu return cast<SymbolRegionValue>(SD); 165eabf776661662a8e652eb692084d20fddffd5ccaZhongxing Xu} 16600a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 1673b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenekconst SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 1683b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const LocationContext *LCtx, 1693b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek QualType T, 1703b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek unsigned Count, 1713b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const void *SymbolTag) { 17200a3a5f024ac54088ab887712b292171188064f0Ted Kremenek llvm::FoldingSetNodeID profile; 1733133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 1749c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 1761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!SD) { 177e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 1783133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 1791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DataSet.InsertNode(SD, InsertPos); 180e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ++SymbolCounter; 181e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 1821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 183e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return cast<SymbolConjured>(SD); 18400a3a5f024ac54088ab887712b292171188064f0Ted Kremenek} 18500a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 186fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenekconst SymbolDerived* 187fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted KremenekSymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 1889697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R) { 1891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 190fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek llvm::FoldingSetNodeID profile; 191fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek SymbolDerived::Profile(profile, parentSymbol, R); 1929c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 1931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 1941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!SD) { 195fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 196fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 1971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DataSet.InsertNode(SD, InsertPos); 198fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek ++SymbolCounter; 199fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek } 2001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 201fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek return cast<SymbolDerived>(SD); 202fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek} 203fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 20432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Roseconst SymbolExtent* 20532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy RoseSymbolManager::getExtentSymbol(const SubRegion *R) { 20632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose llvm::FoldingSetNodeID profile; 20732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SymbolExtent::Profile(profile, R); 2089c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 20932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 21032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (!SD) { 21132f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 21232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose new (SD) SymbolExtent(SymbolCounter, R); 21332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose DataSet.InsertNode(SD, InsertPos); 21432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose ++SymbolCounter; 21532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose } 21632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 21732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return cast<SymbolExtent>(SD); 21832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 21932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 220bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Roseconst SymbolMetadata* 2219c378f705405d37f49795d5e915989de774fe11fTed KremenekSymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 2229c378f705405d37f49795d5e915989de774fe11fTed Kremenek unsigned Count, const void *SymbolTag) { 223bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 224bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose llvm::FoldingSetNodeID profile; 225bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 2269c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 227bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 228bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (!SD) { 229bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 230bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 231bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose DataSet.InsertNode(SD, InsertPos); 232bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose ++SymbolCounter; 233bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 234bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 235bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return cast<SymbolMetadata>(SD); 236bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 237bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 238aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaksconst SymbolCast* 239aace9ef279be3dadd53b481aee568bd7701178b4Anna ZaksSymbolManager::getCastSymbol(const SymExpr *Op, 240aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks QualType From, QualType To) { 241aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks llvm::FoldingSetNodeID ID; 242aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks SymbolCast::Profile(ID, Op, From, To); 243aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks void *InsertPos; 244aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 245aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks if (!data) { 246aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 247aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks new (data) SymbolCast(Op, From, To); 248aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks DataSet.InsertNode(data, InsertPos); 249aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks } 250aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 251aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return cast<SymbolCast>(data); 252aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks} 253aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 254e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenekconst SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 2551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump BinaryOperator::Opcode op, 256e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const llvm::APSInt& v, 257e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek QualType t) { 258a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu llvm::FoldingSetNodeID ID; 259a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu SymIntExpr::Profile(ID, lhs, op, v, t); 260e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek void *InsertPos; 261e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 262e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 263e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek if (!data) { 264e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 265e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek new (data) SymIntExpr(lhs, op, v, t); 266e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek DataSet.InsertNode(data, InsertPos); 267e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 2681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 269e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return cast<SymIntExpr>(data); 270a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu} 271a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 27224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaksconst IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 27324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks BinaryOperator::Opcode op, 27424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks const SymExpr *rhs, 27524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks QualType t) { 27624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks llvm::FoldingSetNodeID ID; 27724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks IntSymExpr::Profile(ID, lhs, op, rhs, t); 27824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks void *InsertPos; 27924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 28024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 28124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks if (!data) { 28224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 28324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks new (data) IntSymExpr(lhs, op, rhs, t); 28424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks DataSet.InsertNode(data, InsertPos); 28524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks } 28624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 28724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return cast<IntSymExpr>(data); 28824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks} 28924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 290e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenekconst SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 291e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek BinaryOperator::Opcode op, 292e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *rhs, 293e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek QualType t) { 294a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu llvm::FoldingSetNodeID ID; 295a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu SymSymExpr::Profile(ID, lhs, op, rhs, t); 296e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek void *InsertPos; 297e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 298e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 299e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek if (!data) { 300e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 301e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek new (data) SymSymExpr(lhs, op, rhs, t); 302e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek DataSet.InsertNode(data, InsertPos); 303e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 3041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 305e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return cast<SymSymExpr>(data); 30600a3a5f024ac54088ab887712b292171188064f0Ted Kremenek} 30700a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 308732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted KremenekQualType SymbolConjured::getType() const { 3099ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek return T; 3109ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek} 311f3d416267ec92cf28da11a79b47383179b77c5d0Ted Kremenek 312732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted KremenekQualType SymbolDerived::getType() const { 313018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu return R->getValueType(); 314fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek} 315fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 316732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted KremenekQualType SymbolExtent::getType() const { 317732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted Kremenek ASTContext &Ctx = R->getMemRegionManager()->getContext(); 31832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return Ctx.getSizeType(); 31932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 32032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 321732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted KremenekQualType SymbolMetadata::getType() const { 322bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return T; 323bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 324bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 325732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted KremenekQualType SymbolRegionValue::getType() const { 326018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu return R->getValueType(); 327d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek} 328d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 329579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna ZaksSymbolManager::~SymbolManager() { 330579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 331579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks E = SymbolDependencies.end(); I != E; ++I) { 332579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks delete I->second; 333579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks } 334579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks 335579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks} 336241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek 337693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenekbool SymbolManager::canSymbolicate(QualType T) { 338f6a19fb92556e040db2d6a7b35b504ba7ebca3bfTed Kremenek T = T.getCanonicalType(); 339f6a19fb92556e040db2d6a7b35b504ba7ebca3bfTed Kremenek 3407dfc9420babe83e236a47e752f8723bd06070d9dZhanyong Wan if (Loc::isLocType(T)) 34117c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek return true; 34217c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek 343a5796f87229b4aeebca71fa6ee1790ae7a5a0382Jordan Rose if (T->isIntegralOrEnumerationType()) 344a5796f87229b4aeebca71fa6ee1790ae7a5a0382Jordan Rose return true; 34517c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek 346fd11957f02da689480618d5fc642ef14164e9cdcJordan Rose if (T->isRecordType() && !T->isUnionType()) 347fd11957f02da689480618d5fc642ef14164e9cdcJordan Rose return true; 348fd11957f02da689480618d5fc642ef14164e9cdcJordan Rose 34917c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek return false; 350693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenek} 351693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenek 35289f920940de4b414616cabb310c37fa84ed2476aAnna Zaksvoid SymbolManager::addSymbolDependency(const SymbolRef Primary, 35389f920940de4b414616cabb310c37fa84ed2476aAnna Zaks const SymbolRef Dependent) { 354579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 355579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolRefSmallVectorTy *dependencies = 0; 356579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks if (I == SymbolDependencies.end()) { 357579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks dependencies = new SymbolRefSmallVectorTy(); 358579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolDependencies[Primary] = dependencies; 359579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks } else { 360579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks dependencies = I->second; 361579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks } 362579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks dependencies->push_back(Dependent); 36389f920940de4b414616cabb310c37fa84ed2476aAnna Zaks} 36489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 36589f920940de4b414616cabb310c37fa84ed2476aAnna Zaksconst SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 36689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks const SymbolRef Primary) { 36789f920940de4b414616cabb310c37fa84ed2476aAnna Zaks SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 36889f920940de4b414616cabb310c37fa84ed2476aAnna Zaks if (I == SymbolDependencies.end()) 36989f920940de4b414616cabb310c37fa84ed2476aAnna Zaks return 0; 370579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks return I->second; 37189f920940de4b414616cabb310c37fa84ed2476aAnna Zaks} 37289f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 37389f920940de4b414616cabb310c37fa84ed2476aAnna Zaksvoid SymbolReaper::markDependentsLive(SymbolRef sym) { 374579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks // Do not mark dependents more then once. 375579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolMapTy::iterator LI = TheLiving.find(sym); 376579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks assert(LI != TheLiving.end() && "The primary symbol is not live."); 377579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks if (LI->second == HaveMarkedDependents) 378579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks return; 379579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks LI->second = HaveMarkedDependents; 380579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks 38189f920940de4b414616cabb310c37fa84ed2476aAnna Zaks if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 38289f920940de4b414616cabb310c37fa84ed2476aAnna Zaks for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 38389f920940de4b414616cabb310c37fa84ed2476aAnna Zaks E = Deps->end(); I != E; ++I) { 384579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks if (TheLiving.find(*I) != TheLiving.end()) 385579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks continue; 38689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks markLive(*I); 38789f920940de4b414616cabb310c37fa84ed2476aAnna Zaks } 38889f920940de4b414616cabb310c37fa84ed2476aAnna Zaks } 38989f920940de4b414616cabb310c37fa84ed2476aAnna Zaks} 39089f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 391241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenekvoid SymbolReaper::markLive(SymbolRef sym) { 392579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks TheLiving[sym] = NotProcessed; 393a97d54c165ca6b6e57b9f333059a84c2188dd591Ted Kremenek TheDead.erase(sym); 39489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks markDependentsLive(sym); 395241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek} 396241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek 397bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenekvoid SymbolReaper::markLive(const MemRegion *region) { 398bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek RegionRoots.insert(region); 399bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek} 400bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 401bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rosevoid SymbolReaper::markInUse(SymbolRef sym) { 402bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<SymbolMetadata>(sym)) 403bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose MetadataInUse.insert(sym); 404bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 405bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 406241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenekbool SymbolReaper::maybeDead(SymbolRef sym) { 407241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek if (isLive(sym)) 408241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek return false; 4091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 410a97d54c165ca6b6e57b9f333059a84c2188dd591Ted Kremenek TheDead.insert(sym); 411241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek return true; 412241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek} 413241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek 414bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenekbool SymbolReaper::isLiveRegion(const MemRegion *MR) { 415bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek if (RegionRoots.count(MR)) 416bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek return true; 417bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 418bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose MR = MR->getBaseRegion(); 419bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 420bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 421bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek return isLive(SR->getSymbol()); 422bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 423bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 424bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek return isLive(VR, true); 425bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 426bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // FIXME: This is a gross over-approximation. What we really need is a way to 427bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // tell if anything still refers to this region. Unlike SymbolicRegions, 428bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // AllocaRegions don't have associated symbols, though, so we don't actually 429bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // have a way to track their liveness. 430bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<AllocaRegion>(MR)) 431bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 432bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 433bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<CXXThisRegion>(MR)) 434bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 435bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 436bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<MemSpaceRegion>(MR)) 437bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 438bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 439bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return false; 440bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 441bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 4429ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenekbool SymbolReaper::isLive(SymbolRef sym) { 44389f920940de4b414616cabb310c37fa84ed2476aAnna Zaks if (TheLiving.count(sym)) { 44489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks markDependentsLive(sym); 445dcb6a26586bb05237f1f32f80de7b7f2bdab8ac3Ted Kremenek return true; 44689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks } 4476e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose 4486e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose bool KnownLive; 4496e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose 4506e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose switch (sym->getKind()) { 4516e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::RegionValueKind: 45274c0d6988462c2cb882e7a8b8050fe119a5af56fAnna Zaks KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion()); 4536e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4546e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::ConjuredKind: 4556e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = false; 4566e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4576e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::DerivedKind: 4586e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 4596e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4606e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::ExtentKind: 4616e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 4626e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4636e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::MetadataKind: 4646e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = MetadataInUse.count(sym) && 4656e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 4666e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose if (KnownLive) 4676e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose MetadataInUse.erase(sym); 4686e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4696e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::SymIntKind: 4706e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 4716e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4726e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::IntSymKind: 4736e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 4746e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4756e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::SymSymKind: 4766e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 4776e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose isLive(cast<SymSymExpr>(sym)->getRHS()); 4786e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 4796e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose case SymExpr::CastSymbolKind: 4806e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 4816e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose break; 482bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 483bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 4846e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose if (KnownLive) 4856e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose markLive(sym); 48632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 4876e3bf21f20d4d744fdf5acd719e9f442f4a144fcJordan Rose return KnownLive; 488241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek} 4895216ad7e095873f19e535ad1efba91973f05d8e8Ted Kremenek 4905eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekbool 4915eca482fe895ea57bc82410222e6426c09e63284Ted KremenekSymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 4928501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks if (LCtx == 0) 4938501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks return false; 4948501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks 4955eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek if (LCtx != ELCtx) { 4965eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // If the reaper's location context is a parent of the expression's 4975eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // location context, then the expression value is now "out of scope". 4985eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek if (LCtx->isParentOf(ELCtx)) 4995eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek return false; 5005eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek return true; 5015eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek } 5028501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks 5030b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks // If no statement is provided, everything is this and parent contexts is live. 5040b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks if (!Loc) 5050b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return true; 5065eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek 507a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 508c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu} 509c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu 510882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 511bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const StackFrameContext *VarContext = VR->getStackFrame(); 5128501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks 5138501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks if (!VarContext) 5148501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks return true; 5158501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks 5168501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks if (!LCtx) 5178501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks return false; 518bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 519df3a61bb5148361254c253eccd91aa4517cc8eaaZhongxing Xu 520882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (VarContext == CurrentContext) { 521a8eaf008e92759142982f7b40720b2b2674bd663Richard Smith // If no statement is provided, everything is live. 5220b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks if (!Loc) 5230b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return true; 5240b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 525a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 526882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return true; 527882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 528882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!includeStoreBindings) 529882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return false; 530882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 531882998923889a2fcce9b49696506c499e22cf38fTed Kremenek unsigned &cachedQuery = 532882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 533882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 534882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (cachedQuery) { 535882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return cachedQuery == 1; 536882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 537882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 538882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Query the store to see if the region occurs in any live bindings. 539882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (Store store = reapedStore.getStore()) { 540882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bool hasRegion = 541882998923889a2fcce9b49696506c499e22cf38fTed Kremenek reapedStore.getStoreManager().includedInBindings(store, VR); 542882998923889a2fcce9b49696506c499e22cf38fTed Kremenek cachedQuery = hasRegion ? 1 : 2; 543882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return hasRegion; 544882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 545882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 546882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return false; 547882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 548bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 5498501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks return VarContext->isParentOf(CurrentContext); 550edeb5b6b50e773b243e0ee0d84589cd1f7dea9b0Ted Kremenek} 551edeb5b6b50e773b243e0ee0d84589cd1f7dea9b0Ted Kremenek 5525216ad7e095873f19e535ad1efba91973f05d8e8Ted KremenekSymbolVisitor::~SymbolVisitor() {} 553