SymbolManager.cpp revision 243830
1218887Sdim//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines SymbolManager, a class that manages symbolic values 11218887Sdim// created for use by ExprEngine and related classes. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 16218887Sdim#include "clang/Analysis/Analyses/LiveVariables.h" 17218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 18226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 19218887Sdim#include "llvm/Support/raw_ostream.h" 20218887Sdim 21218887Sdimusing namespace clang; 22218887Sdimusing namespace ento; 23218887Sdim 24234353Sdimvoid SymExpr::anchor() { } 25234353Sdim 26218887Sdimvoid SymExpr::dump() const { 27218887Sdim dumpToStream(llvm::errs()); 28218887Sdim} 29218887Sdim 30226633Sdimstatic void print(raw_ostream &os, BinaryOperator::Opcode Op) { 31218887Sdim switch (Op) { 32218887Sdim default: 33226633Sdim llvm_unreachable("operator printing not implemented"); 34218887Sdim case BO_Mul: os << '*' ; break; 35218887Sdim case BO_Div: os << '/' ; break; 36218887Sdim case BO_Rem: os << '%' ; break; 37218887Sdim case BO_Add: os << '+' ; break; 38218887Sdim case BO_Sub: os << '-' ; break; 39218887Sdim case BO_Shl: os << "<<" ; break; 40218887Sdim case BO_Shr: os << ">>" ; break; 41218887Sdim case BO_LT: os << "<" ; break; 42218887Sdim case BO_GT: os << '>' ; break; 43218887Sdim case BO_LE: os << "<=" ; break; 44218887Sdim case BO_GE: os << ">=" ; break; 45218887Sdim case BO_EQ: os << "==" ; break; 46218887Sdim case BO_NE: os << "!=" ; break; 47218887Sdim case BO_And: os << '&' ; break; 48218887Sdim case BO_Xor: os << '^' ; break; 49218887Sdim case BO_Or: os << '|' ; break; 50218887Sdim } 51218887Sdim} 52218887Sdim 53226633Sdimvoid SymIntExpr::dumpToStream(raw_ostream &os) const { 54218887Sdim os << '('; 55218887Sdim getLHS()->dumpToStream(os); 56218887Sdim os << ") "; 57218887Sdim print(os, getOpcode()); 58218887Sdim os << ' ' << getRHS().getZExtValue(); 59218887Sdim if (getRHS().isUnsigned()) os << 'U'; 60218887Sdim} 61218887Sdim 62234353Sdimvoid IntSymExpr::dumpToStream(raw_ostream &os) const { 63234353Sdim os << ' ' << getLHS().getZExtValue(); 64234353Sdim if (getLHS().isUnsigned()) os << 'U'; 65234353Sdim print(os, getOpcode()); 66234353Sdim os << '('; 67234353Sdim getRHS()->dumpToStream(os); 68234353Sdim os << ") "; 69234353Sdim} 70234353Sdim 71226633Sdimvoid SymSymExpr::dumpToStream(raw_ostream &os) const { 72218887Sdim os << '('; 73218887Sdim getLHS()->dumpToStream(os); 74218887Sdim os << ") "; 75218887Sdim os << '('; 76218887Sdim getRHS()->dumpToStream(os); 77218887Sdim os << ')'; 78218887Sdim} 79218887Sdim 80234353Sdimvoid SymbolCast::dumpToStream(raw_ostream &os) const { 81234353Sdim os << '(' << ToTy.getAsString() << ") ("; 82234353Sdim Operand->dumpToStream(os); 83234353Sdim os << ')'; 84234353Sdim} 85234353Sdim 86226633Sdimvoid SymbolConjured::dumpToStream(raw_ostream &os) const { 87218887Sdim os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 88218887Sdim} 89218887Sdim 90226633Sdimvoid SymbolDerived::dumpToStream(raw_ostream &os) const { 91218887Sdim os << "derived_$" << getSymbolID() << '{' 92218887Sdim << getParentSymbol() << ',' << getRegion() << '}'; 93218887Sdim} 94218887Sdim 95226633Sdimvoid SymbolExtent::dumpToStream(raw_ostream &os) const { 96218887Sdim os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 97218887Sdim} 98218887Sdim 99226633Sdimvoid SymbolMetadata::dumpToStream(raw_ostream &os) const { 100218887Sdim os << "meta_$" << getSymbolID() << '{' 101218887Sdim << getRegion() << ',' << T.getAsString() << '}'; 102218887Sdim} 103218887Sdim 104234353Sdimvoid SymbolData::anchor() { } 105234353Sdim 106226633Sdimvoid SymbolRegionValue::dumpToStream(raw_ostream &os) const { 107218887Sdim os << "reg_$" << getSymbolID() << "<" << R << ">"; 108218887Sdim} 109218887Sdim 110234353Sdimbool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 111234353Sdim return itr == X.itr; 112234353Sdim} 113234353Sdim 114234353Sdimbool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 115234353Sdim return itr != X.itr; 116234353Sdim} 117234353Sdim 118234353SdimSymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 119234353Sdim itr.push_back(SE); 120234353Sdim} 121234353Sdim 122234353SdimSymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 123234353Sdim assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 124243830Sdim expand(); 125234353Sdim return *this; 126234353Sdim} 127234353Sdim 128234353SdimSymbolRef SymExpr::symbol_iterator::operator*() { 129234353Sdim assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 130243830Sdim return itr.back(); 131234353Sdim} 132234353Sdim 133234353Sdimvoid SymExpr::symbol_iterator::expand() { 134234353Sdim const SymExpr *SE = itr.back(); 135234353Sdim itr.pop_back(); 136234353Sdim 137234353Sdim switch (SE->getKind()) { 138234353Sdim case SymExpr::RegionValueKind: 139234353Sdim case SymExpr::ConjuredKind: 140234353Sdim case SymExpr::DerivedKind: 141234353Sdim case SymExpr::ExtentKind: 142234353Sdim case SymExpr::MetadataKind: 143234353Sdim return; 144234353Sdim case SymExpr::CastSymbolKind: 145234353Sdim itr.push_back(cast<SymbolCast>(SE)->getOperand()); 146234353Sdim return; 147234353Sdim case SymExpr::SymIntKind: 148234353Sdim itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 149234353Sdim return; 150234353Sdim case SymExpr::IntSymKind: 151234353Sdim itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 152234353Sdim return; 153234353Sdim case SymExpr::SymSymKind: { 154234353Sdim const SymSymExpr *x = cast<SymSymExpr>(SE); 155234353Sdim itr.push_back(x->getLHS()); 156234353Sdim itr.push_back(x->getRHS()); 157234353Sdim return; 158234353Sdim } 159234353Sdim } 160234353Sdim llvm_unreachable("unhandled expansion case"); 161234353Sdim} 162234353Sdim 163239462Sdimunsigned SymExpr::computeComplexity() const { 164239462Sdim unsigned R = 0; 165239462Sdim for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I) 166239462Sdim R++; 167239462Sdim return R; 168239462Sdim} 169239462Sdim 170218887Sdimconst SymbolRegionValue* 171226633SdimSymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 172218887Sdim llvm::FoldingSetNodeID profile; 173218887Sdim SymbolRegionValue::Profile(profile, R); 174226633Sdim void *InsertPos; 175218887Sdim SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 176218887Sdim if (!SD) { 177218887Sdim SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 178218887Sdim new (SD) SymbolRegionValue(SymbolCounter, R); 179218887Sdim DataSet.InsertNode(SD, InsertPos); 180218887Sdim ++SymbolCounter; 181218887Sdim } 182218887Sdim 183218887Sdim return cast<SymbolRegionValue>(SD); 184218887Sdim} 185218887Sdim 186243830Sdimconst SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 187243830Sdim const LocationContext *LCtx, 188243830Sdim QualType T, 189243830Sdim unsigned Count, 190243830Sdim const void *SymbolTag) { 191218887Sdim llvm::FoldingSetNodeID profile; 192234353Sdim SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 193226633Sdim void *InsertPos; 194218887Sdim SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 195218887Sdim if (!SD) { 196218887Sdim SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 197234353Sdim new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 198218887Sdim DataSet.InsertNode(SD, InsertPos); 199218887Sdim ++SymbolCounter; 200218887Sdim } 201218887Sdim 202218887Sdim return cast<SymbolConjured>(SD); 203218887Sdim} 204218887Sdim 205218887Sdimconst SymbolDerived* 206218887SdimSymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 207226633Sdim const TypedValueRegion *R) { 208218887Sdim 209218887Sdim llvm::FoldingSetNodeID profile; 210218887Sdim SymbolDerived::Profile(profile, parentSymbol, R); 211226633Sdim void *InsertPos; 212218887Sdim SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 213218887Sdim if (!SD) { 214218887Sdim SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 215218887Sdim new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 216218887Sdim DataSet.InsertNode(SD, InsertPos); 217218887Sdim ++SymbolCounter; 218218887Sdim } 219218887Sdim 220218887Sdim return cast<SymbolDerived>(SD); 221218887Sdim} 222218887Sdim 223218887Sdimconst SymbolExtent* 224218887SdimSymbolManager::getExtentSymbol(const SubRegion *R) { 225218887Sdim llvm::FoldingSetNodeID profile; 226218887Sdim SymbolExtent::Profile(profile, R); 227226633Sdim void *InsertPos; 228218887Sdim SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 229218887Sdim if (!SD) { 230218887Sdim SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 231218887Sdim new (SD) SymbolExtent(SymbolCounter, R); 232218887Sdim DataSet.InsertNode(SD, InsertPos); 233218887Sdim ++SymbolCounter; 234218887Sdim } 235218887Sdim 236218887Sdim return cast<SymbolExtent>(SD); 237218887Sdim} 238218887Sdim 239218887Sdimconst SymbolMetadata* 240226633SdimSymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 241226633Sdim unsigned Count, const void *SymbolTag) { 242218887Sdim 243218887Sdim llvm::FoldingSetNodeID profile; 244218887Sdim SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 245226633Sdim void *InsertPos; 246218887Sdim SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 247218887Sdim if (!SD) { 248218887Sdim SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 249218887Sdim new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 250218887Sdim DataSet.InsertNode(SD, InsertPos); 251218887Sdim ++SymbolCounter; 252218887Sdim } 253218887Sdim 254218887Sdim return cast<SymbolMetadata>(SD); 255218887Sdim} 256218887Sdim 257234353Sdimconst SymbolCast* 258234353SdimSymbolManager::getCastSymbol(const SymExpr *Op, 259234353Sdim QualType From, QualType To) { 260234353Sdim llvm::FoldingSetNodeID ID; 261234353Sdim SymbolCast::Profile(ID, Op, From, To); 262234353Sdim void *InsertPos; 263234353Sdim SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 264234353Sdim if (!data) { 265234353Sdim data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 266234353Sdim new (data) SymbolCast(Op, From, To); 267234353Sdim DataSet.InsertNode(data, InsertPos); 268234353Sdim } 269234353Sdim 270234353Sdim return cast<SymbolCast>(data); 271234353Sdim} 272234353Sdim 273218887Sdimconst SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 274218887Sdim BinaryOperator::Opcode op, 275218887Sdim const llvm::APSInt& v, 276218887Sdim QualType t) { 277218887Sdim llvm::FoldingSetNodeID ID; 278218887Sdim SymIntExpr::Profile(ID, lhs, op, v, t); 279218887Sdim void *InsertPos; 280218887Sdim SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 281218887Sdim 282218887Sdim if (!data) { 283218887Sdim data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 284218887Sdim new (data) SymIntExpr(lhs, op, v, t); 285218887Sdim DataSet.InsertNode(data, InsertPos); 286218887Sdim } 287218887Sdim 288218887Sdim return cast<SymIntExpr>(data); 289218887Sdim} 290218887Sdim 291234353Sdimconst IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 292234353Sdim BinaryOperator::Opcode op, 293234353Sdim const SymExpr *rhs, 294234353Sdim QualType t) { 295234353Sdim llvm::FoldingSetNodeID ID; 296234353Sdim IntSymExpr::Profile(ID, lhs, op, rhs, t); 297234353Sdim void *InsertPos; 298234353Sdim SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 299234353Sdim 300234353Sdim if (!data) { 301234353Sdim data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 302234353Sdim new (data) IntSymExpr(lhs, op, rhs, t); 303234353Sdim DataSet.InsertNode(data, InsertPos); 304234353Sdim } 305234353Sdim 306234353Sdim return cast<IntSymExpr>(data); 307234353Sdim} 308234353Sdim 309218887Sdimconst SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 310218887Sdim BinaryOperator::Opcode op, 311218887Sdim const SymExpr *rhs, 312218887Sdim QualType t) { 313218887Sdim llvm::FoldingSetNodeID ID; 314218887Sdim SymSymExpr::Profile(ID, lhs, op, rhs, t); 315218887Sdim void *InsertPos; 316218887Sdim SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 317218887Sdim 318218887Sdim if (!data) { 319218887Sdim data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 320218887Sdim new (data) SymSymExpr(lhs, op, rhs, t); 321218887Sdim DataSet.InsertNode(data, InsertPos); 322218887Sdim } 323218887Sdim 324218887Sdim return cast<SymSymExpr>(data); 325218887Sdim} 326218887Sdim 327243830SdimQualType SymbolConjured::getType() const { 328218887Sdim return T; 329218887Sdim} 330218887Sdim 331243830SdimQualType SymbolDerived::getType() const { 332218887Sdim return R->getValueType(); 333218887Sdim} 334218887Sdim 335243830SdimQualType SymbolExtent::getType() const { 336243830Sdim ASTContext &Ctx = R->getMemRegionManager()->getContext(); 337218887Sdim return Ctx.getSizeType(); 338218887Sdim} 339218887Sdim 340243830SdimQualType SymbolMetadata::getType() const { 341218887Sdim return T; 342218887Sdim} 343218887Sdim 344243830SdimQualType SymbolRegionValue::getType() const { 345218887Sdim return R->getValueType(); 346218887Sdim} 347218887Sdim 348226633SdimSymbolManager::~SymbolManager() { 349226633Sdim for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 350226633Sdim E = SymbolDependencies.end(); I != E; ++I) { 351226633Sdim delete I->second; 352226633Sdim } 353218887Sdim 354226633Sdim} 355226633Sdim 356218887Sdimbool SymbolManager::canSymbolicate(QualType T) { 357218887Sdim T = T.getCanonicalType(); 358218887Sdim 359218887Sdim if (Loc::isLocType(T)) 360218887Sdim return true; 361218887Sdim 362218887Sdim if (T->isIntegerType()) 363218887Sdim return T->isScalarType(); 364218887Sdim 365218887Sdim if (T->isRecordType() && !T->isUnionType()) 366218887Sdim return true; 367218887Sdim 368218887Sdim return false; 369218887Sdim} 370218887Sdim 371226633Sdimvoid SymbolManager::addSymbolDependency(const SymbolRef Primary, 372226633Sdim const SymbolRef Dependent) { 373226633Sdim SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 374226633Sdim SymbolRefSmallVectorTy *dependencies = 0; 375226633Sdim if (I == SymbolDependencies.end()) { 376226633Sdim dependencies = new SymbolRefSmallVectorTy(); 377226633Sdim SymbolDependencies[Primary] = dependencies; 378226633Sdim } else { 379226633Sdim dependencies = I->second; 380226633Sdim } 381226633Sdim dependencies->push_back(Dependent); 382226633Sdim} 383226633Sdim 384226633Sdimconst SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 385226633Sdim const SymbolRef Primary) { 386226633Sdim SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 387226633Sdim if (I == SymbolDependencies.end()) 388226633Sdim return 0; 389226633Sdim return I->second; 390226633Sdim} 391226633Sdim 392226633Sdimvoid SymbolReaper::markDependentsLive(SymbolRef sym) { 393226633Sdim // Do not mark dependents more then once. 394226633Sdim SymbolMapTy::iterator LI = TheLiving.find(sym); 395226633Sdim assert(LI != TheLiving.end() && "The primary symbol is not live."); 396226633Sdim if (LI->second == HaveMarkedDependents) 397226633Sdim return; 398226633Sdim LI->second = HaveMarkedDependents; 399226633Sdim 400226633Sdim if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 401226633Sdim for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 402226633Sdim E = Deps->end(); I != E; ++I) { 403226633Sdim if (TheLiving.find(*I) != TheLiving.end()) 404226633Sdim continue; 405226633Sdim markLive(*I); 406226633Sdim } 407226633Sdim } 408226633Sdim} 409226633Sdim 410218887Sdimvoid SymbolReaper::markLive(SymbolRef sym) { 411226633Sdim TheLiving[sym] = NotProcessed; 412218887Sdim TheDead.erase(sym); 413226633Sdim markDependentsLive(sym); 414218887Sdim} 415218887Sdim 416226633Sdimvoid SymbolReaper::markLive(const MemRegion *region) { 417226633Sdim RegionRoots.insert(region); 418226633Sdim} 419226633Sdim 420218887Sdimvoid SymbolReaper::markInUse(SymbolRef sym) { 421218887Sdim if (isa<SymbolMetadata>(sym)) 422218887Sdim MetadataInUse.insert(sym); 423218887Sdim} 424218887Sdim 425218887Sdimbool SymbolReaper::maybeDead(SymbolRef sym) { 426218887Sdim if (isLive(sym)) 427218887Sdim return false; 428218887Sdim 429218887Sdim TheDead.insert(sym); 430218887Sdim return true; 431218887Sdim} 432218887Sdim 433226633Sdimbool SymbolReaper::isLiveRegion(const MemRegion *MR) { 434226633Sdim if (RegionRoots.count(MR)) 435226633Sdim return true; 436226633Sdim 437218887Sdim MR = MR->getBaseRegion(); 438218887Sdim 439218887Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 440226633Sdim return isLive(SR->getSymbol()); 441218887Sdim 442218887Sdim if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 443226633Sdim return isLive(VR, true); 444218887Sdim 445218887Sdim // FIXME: This is a gross over-approximation. What we really need is a way to 446218887Sdim // tell if anything still refers to this region. Unlike SymbolicRegions, 447218887Sdim // AllocaRegions don't have associated symbols, though, so we don't actually 448218887Sdim // have a way to track their liveness. 449218887Sdim if (isa<AllocaRegion>(MR)) 450218887Sdim return true; 451218887Sdim 452218887Sdim if (isa<CXXThisRegion>(MR)) 453218887Sdim return true; 454218887Sdim 455218887Sdim if (isa<MemSpaceRegion>(MR)) 456218887Sdim return true; 457218887Sdim 458218887Sdim return false; 459218887Sdim} 460218887Sdim 461218887Sdimbool SymbolReaper::isLive(SymbolRef sym) { 462226633Sdim if (TheLiving.count(sym)) { 463226633Sdim markDependentsLive(sym); 464218887Sdim return true; 465226633Sdim } 466243830Sdim 467243830Sdim bool KnownLive; 468243830Sdim 469243830Sdim switch (sym->getKind()) { 470243830Sdim case SymExpr::RegionValueKind: 471243830Sdim // FIXME: We should be able to use isLiveRegion here (this behavior 472243830Sdim // predates isLiveRegion), but doing so causes test failures. Investigate. 473243830Sdim KnownLive = true; 474243830Sdim break; 475243830Sdim case SymExpr::ConjuredKind: 476243830Sdim KnownLive = false; 477243830Sdim break; 478243830Sdim case SymExpr::DerivedKind: 479243830Sdim KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 480243830Sdim break; 481243830Sdim case SymExpr::ExtentKind: 482243830Sdim KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 483243830Sdim break; 484243830Sdim case SymExpr::MetadataKind: 485243830Sdim KnownLive = MetadataInUse.count(sym) && 486243830Sdim isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 487243830Sdim if (KnownLive) 488243830Sdim MetadataInUse.erase(sym); 489243830Sdim break; 490243830Sdim case SymExpr::SymIntKind: 491243830Sdim KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 492243830Sdim break; 493243830Sdim case SymExpr::IntSymKind: 494243830Sdim KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 495243830Sdim break; 496243830Sdim case SymExpr::SymSymKind: 497243830Sdim KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 498243830Sdim isLive(cast<SymSymExpr>(sym)->getRHS()); 499243830Sdim break; 500243830Sdim case SymExpr::CastSymbolKind: 501243830Sdim KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 502243830Sdim break; 503218887Sdim } 504218887Sdim 505243830Sdim if (KnownLive) 506243830Sdim markLive(sym); 507218887Sdim 508243830Sdim return KnownLive; 509218887Sdim} 510218887Sdim 511234353Sdimbool 512234353SdimSymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 513243830Sdim if (LCtx == 0) 514243830Sdim return false; 515243830Sdim 516234353Sdim if (LCtx != ELCtx) { 517234353Sdim // If the reaper's location context is a parent of the expression's 518234353Sdim // location context, then the expression value is now "out of scope". 519234353Sdim if (LCtx->isParentOf(ELCtx)) 520234353Sdim return false; 521234353Sdim return true; 522234353Sdim } 523243830Sdim 524239462Sdim // If no statement is provided, everything is this and parent contexts is live. 525239462Sdim if (!Loc) 526239462Sdim return true; 527234353Sdim 528226633Sdim return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 529218887Sdim} 530218887Sdim 531226633Sdimbool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 532218887Sdim const StackFrameContext *VarContext = VR->getStackFrame(); 533243830Sdim 534243830Sdim if (!VarContext) 535243830Sdim return true; 536243830Sdim 537243830Sdim if (!LCtx) 538243830Sdim return false; 539218887Sdim const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 540218887Sdim 541226633Sdim if (VarContext == CurrentContext) { 542243830Sdim // If no statement is provided, everything is live. 543239462Sdim if (!Loc) 544239462Sdim return true; 545239462Sdim 546226633Sdim if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 547226633Sdim return true; 548218887Sdim 549226633Sdim if (!includeStoreBindings) 550226633Sdim return false; 551226633Sdim 552226633Sdim unsigned &cachedQuery = 553226633Sdim const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 554226633Sdim 555226633Sdim if (cachedQuery) { 556226633Sdim return cachedQuery == 1; 557226633Sdim } 558226633Sdim 559226633Sdim // Query the store to see if the region occurs in any live bindings. 560226633Sdim if (Store store = reapedStore.getStore()) { 561226633Sdim bool hasRegion = 562226633Sdim reapedStore.getStoreManager().includedInBindings(store, VR); 563226633Sdim cachedQuery = hasRegion ? 1 : 2; 564226633Sdim return hasRegion; 565226633Sdim } 566226633Sdim 567226633Sdim return false; 568226633Sdim } 569226633Sdim 570218887Sdim return VarContext->isParentOf(CurrentContext); 571218887Sdim} 572218887Sdim 573218887SdimSymbolVisitor::~SymbolVisitor() {} 574