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 Kremenekstatic void print(raw_ostream &os, BinaryOperator::Opcode Op) { 31e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek switch (Op) { 32e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek default: 33b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("operator printing not implemented"); 342de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Mul: os << '*' ; break; 352de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Div: os << '/' ; break; 362de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Rem: os << '%' ; break; 372de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Add: os << '+' ; break; 382de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Sub: os << '-' ; break; 392de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Shl: os << "<<" ; break; 402de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Shr: os << ">>" ; break; 412de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LT: os << "<" ; break; 422de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GT: os << '>' ; break; 432de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LE: os << "<=" ; break; 442de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GE: os << ">=" ; break; 452de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: os << "==" ; break; 462de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: os << "!=" ; break; 472de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_And: os << '&' ; break; 482de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Xor: os << '^' ; break; 492de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Or: os << '|' ; break; 501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 51e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 52e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 539c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymIntExpr::dumpToStream(raw_ostream &os) const { 54e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << '('; 558800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek getLHS()->dumpToStream(os); 56e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << ") "; 578800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek print(os, getOpcode()); 588800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek os << ' ' << getRHS().getZExtValue(); 598800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek if (getRHS().isUnsigned()) os << 'U'; 60e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaksvoid IntSymExpr::dumpToStream(raw_ostream &os) const { 6324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks os << ' ' << getLHS().getZExtValue(); 6424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks if (getLHS().isUnsigned()) os << 'U'; 6524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks print(os, getOpcode()); 6624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks os << '('; 6724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks getRHS()->dumpToStream(os); 6824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks os << ") "; 6924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks} 7024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 719c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymSymExpr::dumpToStream(raw_ostream &os) const { 72e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << '('; 738800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek getLHS()->dumpToStream(os); 74e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << ") "; 75e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek os << '('; 768800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek getRHS()->dumpToStream(os); 771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump os << ')'; 78e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 79e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 80aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaksvoid SymbolCast::dumpToStream(raw_ostream &os) const { 81aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks os << '(' << ToTy.getAsString() << ") ("; 82aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks Operand->dumpToStream(os); 83aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks os << ')'; 84aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks} 85aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 869c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolConjured::dumpToStream(raw_ostream &os) const { 8719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 88e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 89e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 909c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolDerived::dumpToStream(raw_ostream &os) const { 91fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek os << "derived_$" << getSymbolID() << '{' 92fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek << getParentSymbol() << ',' << getRegion() << '}'; 93fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek} 94fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 959c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolExtent::dumpToStream(raw_ostream &os) const { 9632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 9732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 9832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 999c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolMetadata::dumpToStream(raw_ostream &os) const { 100bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose os << "meta_$" << getSymbolID() << '{' 101bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose << getRegion() << ',' << T.getAsString() << '}'; 102bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 103bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 10499ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid SymbolData::anchor() { } 10599ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 1069c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid SymbolRegionValue::dumpToStream(raw_ostream &os) const { 1078800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek os << "reg_$" << getSymbolID() << "<" << R << ">"; 10894c969804b1f98650316a8f75434b2d24dbe94eaTed Kremenek} 10994c969804b1f98650316a8f75434b2d24dbe94eaTed Kremenek 1101d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaksbool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 1111d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return itr == X.itr; 1121d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1131d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1141d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaksbool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 1151d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return itr != X.itr; 1161d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1171d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1181d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna ZaksSymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 1191d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks itr.push_back(SE); 1201d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1211d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1221d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna ZaksSymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 1231d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 12424c7f98828e039005cff3bd847e7ab404a6a09f8Jordan Rose expand(); 1251d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return *this; 1261d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1271d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1281d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna ZaksSymbolRef SymExpr::symbol_iterator::operator*() { 1291d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 13024c7f98828e039005cff3bd847e7ab404a6a09f8Jordan Rose return itr.back(); 1311d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1321d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 1331d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaksvoid SymExpr::symbol_iterator::expand() { 1341d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks const SymExpr *SE = itr.back(); 1351d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks itr.pop_back(); 1361d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 13724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks switch (SE->getKind()) { 13824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::RegionValueKind: 13924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::ConjuredKind: 14024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::DerivedKind: 14124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::ExtentKind: 14224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::MetadataKind: 14324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 14424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::CastSymbolKind: 14524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(cast<SymbolCast>(SE)->getOperand()); 14624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 14724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::SymIntKind: 14824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 14924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 15024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::IntSymKind: 15124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 15224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 15324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::SymSymKind: { 15424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks const SymSymExpr *x = cast<SymSymExpr>(SE); 15524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(x->getLHS()); 15624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks itr.push_back(x->getRHS()); 15724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return; 15824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks } 1591d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks } 1601d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks llvm_unreachable("unhandled expansion case"); 1611d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks} 1621d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 163baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaksunsigned SymExpr::computeComplexity() const { 164baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks unsigned R = 0; 165baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I) 166baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks R++; 167baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks return R; 168baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks} 169baeaa9ad120f60b1c5b6f1a84286b507dbe2b55dAnna Zaks 1701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpconst SymbolRegionValue* 1719697934650354bed2e509d8e7e44f21a1fb00f76Ted KremenekSymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 17200a3a5f024ac54088ab887712b292171188064f0Ted Kremenek llvm::FoldingSetNodeID profile; 17314d2328ecfc5102b077fa2c2c129dce1574c8831Zhongxing Xu SymbolRegionValue::Profile(profile, R); 1749c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 1761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!SD) { 177d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 17814d2328ecfc5102b077fa2c2c129dce1574c8831Zhongxing Xu new (SD) SymbolRegionValue(SymbolCounter, R); 179e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek DataSet.InsertNode(SD, InsertPos); 180e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ++SymbolCounter; 181e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 1821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 183d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu return cast<SymbolRegionValue>(SD); 184eabf776661662a8e652eb692084d20fddffd5ccaZhongxing Xu} 18500a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 1863b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenekconst SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 1873b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const LocationContext *LCtx, 1883b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek QualType T, 1893b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek unsigned Count, 1903b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const void *SymbolTag) { 19100a3a5f024ac54088ab887712b292171188064f0Ted Kremenek llvm::FoldingSetNodeID profile; 1923133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 1939c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 1941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 1951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!SD) { 196e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 1973133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 1981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DataSet.InsertNode(SD, InsertPos); 199e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ++SymbolCounter; 200e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 2011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 202e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return cast<SymbolConjured>(SD); 20300a3a5f024ac54088ab887712b292171188064f0Ted Kremenek} 20400a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 205fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenekconst SymbolDerived* 206fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted KremenekSymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 2079697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R) { 2081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 209fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek llvm::FoldingSetNodeID profile; 210fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek SymbolDerived::Profile(profile, parentSymbol, R); 2119c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 2121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 2131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!SD) { 214fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 215fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 2161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DataSet.InsertNode(SD, InsertPos); 217fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek ++SymbolCounter; 218fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek } 2191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 220fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek return cast<SymbolDerived>(SD); 221fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek} 222fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 22332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Roseconst SymbolExtent* 22432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy RoseSymbolManager::getExtentSymbol(const SubRegion *R) { 22532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose llvm::FoldingSetNodeID profile; 22632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SymbolExtent::Profile(profile, R); 2279c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 22832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 22932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (!SD) { 23032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 23132f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose new (SD) SymbolExtent(SymbolCounter, R); 23232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose DataSet.InsertNode(SD, InsertPos); 23332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose ++SymbolCounter; 23432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose } 23532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 23632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return cast<SymbolExtent>(SD); 23732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 23832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 239bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Roseconst SymbolMetadata* 2409c378f705405d37f49795d5e915989de774fe11fTed KremenekSymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 2419c378f705405d37f49795d5e915989de774fe11fTed Kremenek unsigned Count, const void *SymbolTag) { 242bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 243bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose llvm::FoldingSetNodeID profile; 244bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 2459c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *InsertPos; 246bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 247bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (!SD) { 248bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 249bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 250bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose DataSet.InsertNode(SD, InsertPos); 251bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose ++SymbolCounter; 252bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 253bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 254bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return cast<SymbolMetadata>(SD); 255bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 256bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 257aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaksconst SymbolCast* 258aace9ef279be3dadd53b481aee568bd7701178b4Anna ZaksSymbolManager::getCastSymbol(const SymExpr *Op, 259aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks QualType From, QualType To) { 260aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks llvm::FoldingSetNodeID ID; 261aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks SymbolCast::Profile(ID, Op, From, To); 262aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks void *InsertPos; 263aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 264aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks if (!data) { 265aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 266aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks new (data) SymbolCast(Op, From, To); 267aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks DataSet.InsertNode(data, InsertPos); 268aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks } 269aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 270aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return cast<SymbolCast>(data); 271aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks} 272aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 273e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenekconst SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 2741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump BinaryOperator::Opcode op, 275e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const llvm::APSInt& v, 276e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek QualType t) { 277a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu llvm::FoldingSetNodeID ID; 278a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu SymIntExpr::Profile(ID, lhs, op, v, t); 279e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek void *InsertPos; 280e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 281e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 282e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek if (!data) { 283e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 284e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek new (data) SymIntExpr(lhs, op, v, t); 285e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek DataSet.InsertNode(data, InsertPos); 286e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 2871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 288e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return cast<SymIntExpr>(data); 289a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu} 290a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 29124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaksconst IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 29224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks BinaryOperator::Opcode op, 29324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks const SymExpr *rhs, 29424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks QualType t) { 29524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks llvm::FoldingSetNodeID ID; 29624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks IntSymExpr::Profile(ID, lhs, op, rhs, t); 29724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks void *InsertPos; 29824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 29924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 30024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks if (!data) { 30124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 30224d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks new (data) IntSymExpr(lhs, op, rhs, t); 30324d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks DataSet.InsertNode(data, InsertPos); 30424d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks } 30524d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 30624d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return cast<IntSymExpr>(data); 30724d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks} 30824d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks 309e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenekconst SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 310e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek BinaryOperator::Opcode op, 311e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *rhs, 312e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek QualType t) { 313a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu llvm::FoldingSetNodeID ID; 314a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu SymSymExpr::Profile(ID, lhs, op, rhs, t); 315e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek void *InsertPos; 316e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 317e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 318e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek if (!data) { 319e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 320e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek new (data) SymSymExpr(lhs, op, rhs, t); 321e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek DataSet.InsertNode(data, InsertPos); 322e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 3231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 324e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return cast<SymSymExpr>(data); 32500a3a5f024ac54088ab887712b292171188064f0Ted Kremenek} 32600a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 3279ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed KremenekQualType SymbolConjured::getType(ASTContext&) const { 3289ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek return T; 3299ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek} 330f3d416267ec92cf28da11a79b47383179b77c5d0Ted Kremenek 3319c378f705405d37f49795d5e915989de774fe11fTed KremenekQualType SymbolDerived::getType(ASTContext &Ctx) const { 332018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu return R->getValueType(); 333fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek} 334fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 3359c378f705405d37f49795d5e915989de774fe11fTed KremenekQualType SymbolExtent::getType(ASTContext &Ctx) const { 33632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return Ctx.getSizeType(); 33732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 33832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 339bd533aa4ff8895c676d4634d0d3de254962569d0Jordy RoseQualType SymbolMetadata::getType(ASTContext&) const { 340bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return T; 341bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 342bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 3439c378f705405d37f49795d5e915989de774fe11fTed KremenekQualType SymbolRegionValue::getType(ASTContext &C) const { 344018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu return R->getValueType(); 345d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek} 346d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 347579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna ZaksSymbolManager::~SymbolManager() { 348579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 349579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks E = SymbolDependencies.end(); I != E; ++I) { 350579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks delete I->second; 351579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks } 352579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks 353579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks} 354241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek 355693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenekbool SymbolManager::canSymbolicate(QualType T) { 356f6a19fb92556e040db2d6a7b35b504ba7ebca3bfTed Kremenek T = T.getCanonicalType(); 357f6a19fb92556e040db2d6a7b35b504ba7ebca3bfTed Kremenek 3587dfc9420babe83e236a47e752f8723bd06070d9dZhanyong Wan if (Loc::isLocType(T)) 35917c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek return true; 36017c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek 36117c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek if (T->isIntegerType()) 36217c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek return T->isScalarType(); 36317c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek 364fd11957f02da689480618d5fc642ef14164e9cdcJordan Rose if (T->isRecordType() && !T->isUnionType()) 365fd11957f02da689480618d5fc642ef14164e9cdcJordan Rose return true; 366fd11957f02da689480618d5fc642ef14164e9cdcJordan Rose 36717c571c91d431ce2756ca6e5d7e822f7333258b6Ted Kremenek return false; 368693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenek} 369693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenek 37089f920940de4b414616cabb310c37fa84ed2476aAnna Zaksvoid SymbolManager::addSymbolDependency(const SymbolRef Primary, 37189f920940de4b414616cabb310c37fa84ed2476aAnna Zaks const SymbolRef Dependent) { 372579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 373579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolRefSmallVectorTy *dependencies = 0; 374579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks if (I == SymbolDependencies.end()) { 375579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks dependencies = new SymbolRefSmallVectorTy(); 376579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolDependencies[Primary] = dependencies; 377579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks } else { 378579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks dependencies = I->second; 379579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks } 380579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks dependencies->push_back(Dependent); 38189f920940de4b414616cabb310c37fa84ed2476aAnna Zaks} 38289f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 38389f920940de4b414616cabb310c37fa84ed2476aAnna Zaksconst SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 38489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks const SymbolRef Primary) { 38589f920940de4b414616cabb310c37fa84ed2476aAnna Zaks SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 38689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks if (I == SymbolDependencies.end()) 38789f920940de4b414616cabb310c37fa84ed2476aAnna Zaks return 0; 388579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks return I->second; 38989f920940de4b414616cabb310c37fa84ed2476aAnna Zaks} 39089f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 39189f920940de4b414616cabb310c37fa84ed2476aAnna Zaksvoid SymbolReaper::markDependentsLive(SymbolRef sym) { 392579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks // Do not mark dependents more then once. 393579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolMapTy::iterator LI = TheLiving.find(sym); 394579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks assert(LI != TheLiving.end() && "The primary symbol is not live."); 395579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks if (LI->second == HaveMarkedDependents) 396579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks return; 397579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks LI->second = HaveMarkedDependents; 398579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks 39989f920940de4b414616cabb310c37fa84ed2476aAnna Zaks if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 40089f920940de4b414616cabb310c37fa84ed2476aAnna Zaks for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 40189f920940de4b414616cabb310c37fa84ed2476aAnna Zaks E = Deps->end(); I != E; ++I) { 402579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks if (TheLiving.find(*I) != TheLiving.end()) 403579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks continue; 40489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks markLive(*I); 40589f920940de4b414616cabb310c37fa84ed2476aAnna Zaks } 40689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks } 40789f920940de4b414616cabb310c37fa84ed2476aAnna Zaks} 40889f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 409241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenekvoid SymbolReaper::markLive(SymbolRef sym) { 410579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks TheLiving[sym] = NotProcessed; 411a97d54c165ca6b6e57b9f333059a84c2188dd591Ted Kremenek TheDead.erase(sym); 41289f920940de4b414616cabb310c37fa84ed2476aAnna Zaks markDependentsLive(sym); 413241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek} 414241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek 415bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenekvoid SymbolReaper::markLive(const MemRegion *region) { 416bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek RegionRoots.insert(region); 417bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek} 418bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 419bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rosevoid SymbolReaper::markInUse(SymbolRef sym) { 420bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<SymbolMetadata>(sym)) 421bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose MetadataInUse.insert(sym); 422bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 423bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 424241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenekbool SymbolReaper::maybeDead(SymbolRef sym) { 425241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek if (isLive(sym)) 426241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek return false; 4271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 428a97d54c165ca6b6e57b9f333059a84c2188dd591Ted Kremenek TheDead.insert(sym); 429241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek return true; 430241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek} 431241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek 432bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenekbool SymbolReaper::isLiveRegion(const MemRegion *MR) { 433bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek if (RegionRoots.count(MR)) 434bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek return true; 435bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 436bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose MR = MR->getBaseRegion(); 437bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 438bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 439bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek return isLive(SR->getSymbol()); 440bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 441bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 442bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek return isLive(VR, true); 443bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 444bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // FIXME: This is a gross over-approximation. What we really need is a way to 445bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // tell if anything still refers to this region. Unlike SymbolicRegions, 446bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // AllocaRegions don't have associated symbols, though, so we don't actually 447bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // have a way to track their liveness. 448bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<AllocaRegion>(MR)) 449bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 450bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 451bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<CXXThisRegion>(MR)) 452bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 453bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 454bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (isa<MemSpaceRegion>(MR)) 455bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 456bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 457bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return false; 458bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose} 459bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 4609ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenekbool SymbolReaper::isLive(SymbolRef sym) { 46189f920940de4b414616cabb310c37fa84ed2476aAnna Zaks if (TheLiving.count(sym)) { 46289f920940de4b414616cabb310c37fa84ed2476aAnna Zaks markDependentsLive(sym); 463dcb6a26586bb05237f1f32f80de7b7f2bdab8ac3Ted Kremenek return true; 46489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks } 4651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 46619e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { 46719e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek if (isLive(derived->getParentSymbol())) { 46819e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek markLive(sym); 46919e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek return true; 47019e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 47119e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek return false; 47219e1f0ba5cec738ce6cebe3fe0e1edc782206494Ted Kremenek } 4731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 47432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { 475bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek if (isLiveRegion(extent->getRegion())) { 476bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose markLive(sym); 477bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 478bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 479bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return false; 480bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 481bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 482bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) { 483bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose if (MetadataInUse.count(sym)) { 484bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek if (isLiveRegion(metadata->getRegion())) { 485bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose markLive(sym); 486bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose MetadataInUse.erase(sym); 487bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return true; 488bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 489bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 49032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return false; 49132f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose } 49232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 493dcb6a26586bb05237f1f32f80de7b7f2bdab8ac3Ted Kremenek // Interogate the symbol. It may derive from an input value to 494dcb6a26586bb05237f1f32f80de7b7f2bdab8ac3Ted Kremenek // the analyzed function/method. 495d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu return isa<SymbolRegionValue>(sym); 496241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek} 4975216ad7e095873f19e535ad1efba91973f05d8e8Ted Kremenek 4985eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekbool 4995eca482fe895ea57bc82410222e6426c09e63284Ted KremenekSymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 5005eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek if (LCtx != ELCtx) { 5015eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // If the reaper's location context is a parent of the expression's 5025eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // location context, then the expression value is now "out of scope". 5035eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek if (LCtx->isParentOf(ELCtx)) 5045eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek return false; 5055eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek return true; 5065eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek } 5070b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks // If no statement is provided, everything is this and parent contexts is live. 5080b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks if (!Loc) 5090b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return true; 5105eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek 511a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 512c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu} 513c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu 514882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 515bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const StackFrameContext *VarContext = VR->getStackFrame(); 516bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 517df3a61bb5148361254c253eccd91aa4517cc8eaaZhongxing Xu 518882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (VarContext == CurrentContext) { 519a8eaf008e92759142982f7b40720b2b2674bd663Richard Smith // If no statement is provided, everything is live. 5200b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks if (!Loc) 5210b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return true; 5220b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 523a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 524882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return true; 525882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 526882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!includeStoreBindings) 527882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return false; 528882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 529882998923889a2fcce9b49696506c499e22cf38fTed Kremenek unsigned &cachedQuery = 530882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 531882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 532882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (cachedQuery) { 533882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return cachedQuery == 1; 534882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 535882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 536882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Query the store to see if the region occurs in any live bindings. 537882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (Store store = reapedStore.getStore()) { 538882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bool hasRegion = 539882998923889a2fcce9b49696506c499e22cf38fTed Kremenek reapedStore.getStoreManager().includedInBindings(store, VR); 540882998923889a2fcce9b49696506c499e22cf38fTed Kremenek cachedQuery = hasRegion ? 1 : 2; 541882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return hasRegion; 542882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 543882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 544882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return false; 545882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 546bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 547a8eaf008e92759142982f7b40720b2b2674bd663Richard Smith return !VarContext || VarContext->isParentOf(CurrentContext); 548edeb5b6b50e773b243e0ee0d84589cd1f7dea9b0Ted Kremenek} 549edeb5b6b50e773b243e0ee0d84589cd1f7dea9b0Ted Kremenek 5505216ad7e095873f19e535ad1efba91973f05d8e8Ted KremenekSymbolVisitor::~SymbolVisitor() {} 551