SymbolManager.cpp revision 263508
1243730Srwatson//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2243730Srwatson// 3243730Srwatson// The LLVM Compiler Infrastructure 4243730Srwatson// 5243730Srwatson// This file is distributed under the University of Illinois Open Source 6243730Srwatson// License. See LICENSE.TXT for details. 7243730Srwatson// 8243730Srwatson//===----------------------------------------------------------------------===// 9243730Srwatson// 10243730Srwatson// This file defines SymbolManager, a class that manages symbolic values 11243730Srwatson// created for use by ExprEngine and related classes. 12243730Srwatson// 13243730Srwatson//===----------------------------------------------------------------------===// 14243730Srwatson 15243730Srwatson#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 16243730Srwatson#include "clang/Analysis/Analyses/LiveVariables.h" 17243730Srwatson#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 18243730Srwatson#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 19243730Srwatson#include "llvm/Support/raw_ostream.h" 20243730Srwatson 21243730Srwatsonusing namespace clang; 22243730Srwatsonusing namespace ento; 23243730Srwatson 24243730Srwatsonvoid SymExpr::anchor() { } 25243730Srwatson 26243730Srwatsonvoid SymExpr::dump() const { 27243730Srwatson dumpToStream(llvm::errs()); 28243730Srwatson} 29243730Srwatson 30243730Srwatsonvoid SymIntExpr::dumpToStream(raw_ostream &os) const { 31243730Srwatson os << '('; 32243730Srwatson getLHS()->dumpToStream(os); 33243730Srwatson os << ") " 34243730Srwatson << BinaryOperator::getOpcodeStr(getOpcode()) << ' ' 35243730Srwatson << getRHS().getZExtValue(); 36243730Srwatson if (getRHS().isUnsigned()) 37243730Srwatson os << 'U'; 38243730Srwatson} 39243730Srwatson 40243730Srwatsonvoid IntSymExpr::dumpToStream(raw_ostream &os) const { 41243730Srwatson os << getLHS().getZExtValue(); 42243730Srwatson if (getLHS().isUnsigned()) 43243730Srwatson os << 'U'; 44243730Srwatson os << ' ' 45243730Srwatson << BinaryOperator::getOpcodeStr(getOpcode()) 46243730Srwatson << " ("; 47243730Srwatson getRHS()->dumpToStream(os); 48243730Srwatson os << ')'; 49243730Srwatson} 50243730Srwatson 51243730Srwatsonvoid SymSymExpr::dumpToStream(raw_ostream &os) const { 52243730Srwatson os << '('; 53243730Srwatson getLHS()->dumpToStream(os); 54243730Srwatson os << ") " 55243730Srwatson << BinaryOperator::getOpcodeStr(getOpcode()) 56243730Srwatson << " ("; 57243730Srwatson getRHS()->dumpToStream(os); 58243730Srwatson os << ')'; 59243730Srwatson} 60243730Srwatson 61243730Srwatsonvoid SymbolCast::dumpToStream(raw_ostream &os) const { 62243730Srwatson os << '(' << ToTy.getAsString() << ") ("; 63243730Srwatson Operand->dumpToStream(os); 64243730Srwatson os << ')'; 65243730Srwatson} 66243730Srwatson 67243730Srwatsonvoid SymbolConjured::dumpToStream(raw_ostream &os) const { 68243730Srwatson os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 69243730Srwatson} 70243730Srwatson 71243730Srwatsonvoid SymbolDerived::dumpToStream(raw_ostream &os) const { 72243730Srwatson os << "derived_$" << getSymbolID() << '{' 73243730Srwatson << getParentSymbol() << ',' << getRegion() << '}'; 74243730Srwatson} 75243730Srwatson 76243730Srwatsonvoid SymbolExtent::dumpToStream(raw_ostream &os) const { 77243730Srwatson os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 78243730Srwatson} 79243730Srwatson 80243730Srwatsonvoid SymbolMetadata::dumpToStream(raw_ostream &os) const { 81243730Srwatson os << "meta_$" << getSymbolID() << '{' 82243730Srwatson << getRegion() << ',' << T.getAsString() << '}'; 83243730Srwatson} 84243730Srwatson 85243730Srwatsonvoid SymbolData::anchor() { } 86243730Srwatson 87243730Srwatsonvoid SymbolRegionValue::dumpToStream(raw_ostream &os) const { 88243730Srwatson os << "reg_$" << getSymbolID() << "<" << R << ">"; 89243730Srwatson} 90243730Srwatson 91243730Srwatsonbool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 92243730Srwatson return itr == X.itr; 93243730Srwatson} 94243730Srwatson 95243730Srwatsonbool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 96243730Srwatson return itr != X.itr; 97243730Srwatson} 98243730Srwatson 99243730SrwatsonSymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 100243730Srwatson itr.push_back(SE); 101243730Srwatson} 102243730Srwatson 103243730SrwatsonSymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 104243730Srwatson assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 105243730Srwatson expand(); 106243730Srwatson return *this; 107243730Srwatson} 108243730Srwatson 109243730SrwatsonSymbolRef SymExpr::symbol_iterator::operator*() { 110243730Srwatson assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 111243730Srwatson return itr.back(); 112243730Srwatson} 113243730Srwatson 114243730Srwatsonvoid SymExpr::symbol_iterator::expand() { 115243730Srwatson const SymExpr *SE = itr.pop_back_val(); 116243730Srwatson 117243730Srwatson switch (SE->getKind()) { 118243730Srwatson case SymExpr::RegionValueKind: 119243730Srwatson case SymExpr::ConjuredKind: 120243730Srwatson case SymExpr::DerivedKind: 121243730Srwatson case SymExpr::ExtentKind: 122243730Srwatson case SymExpr::MetadataKind: 123243730Srwatson return; 124243730Srwatson case SymExpr::CastSymbolKind: 125243730Srwatson itr.push_back(cast<SymbolCast>(SE)->getOperand()); 126243730Srwatson return; 127243730Srwatson case SymExpr::SymIntKind: 128243730Srwatson itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 129243730Srwatson return; 130243730Srwatson case SymExpr::IntSymKind: 131243730Srwatson itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 132243730Srwatson return; 133243730Srwatson case SymExpr::SymSymKind: { 134243730Srwatson const SymSymExpr *x = cast<SymSymExpr>(SE); 135243730Srwatson itr.push_back(x->getLHS()); 136243730Srwatson itr.push_back(x->getRHS()); 137243730Srwatson return; 138243730Srwatson } 139243730Srwatson } 140243730Srwatson llvm_unreachable("unhandled expansion case"); 141243730Srwatson} 142243730Srwatson 143243730Srwatsonunsigned SymExpr::computeComplexity() const { 144243730Srwatson unsigned R = 0; 145243730Srwatson for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I) 146243730Srwatson R++; 147243730Srwatson return R; 148243730Srwatson} 149243730Srwatson 150243730Srwatsonconst SymbolRegionValue* 151243730SrwatsonSymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 152243730Srwatson llvm::FoldingSetNodeID profile; 153243730Srwatson SymbolRegionValue::Profile(profile, R); 154243730Srwatson void *InsertPos; 155243730Srwatson SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 156243730Srwatson if (!SD) { 157243730Srwatson SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 158243730Srwatson new (SD) SymbolRegionValue(SymbolCounter, R); 159243730Srwatson DataSet.InsertNode(SD, InsertPos); 160243730Srwatson ++SymbolCounter; 161243730Srwatson } 162243730Srwatson 163243730Srwatson return cast<SymbolRegionValue>(SD); 164243730Srwatson} 165243730Srwatson 166243730Srwatsonconst SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 167243730Srwatson const LocationContext *LCtx, 168243730Srwatson QualType T, 169243730Srwatson unsigned Count, 170243730Srwatson const void *SymbolTag) { 171243730Srwatson llvm::FoldingSetNodeID profile; 172243730Srwatson SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 173243730Srwatson void *InsertPos; 174243730Srwatson SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 175243730Srwatson if (!SD) { 176243730Srwatson SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 177243730Srwatson new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 178243730Srwatson DataSet.InsertNode(SD, InsertPos); 179243730Srwatson ++SymbolCounter; 180243730Srwatson } 181243730Srwatson 182243730Srwatson return cast<SymbolConjured>(SD); 183243730Srwatson} 184243730Srwatson 185243730Srwatsonconst SymbolDerived* 186243730SrwatsonSymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 187243730Srwatson const TypedValueRegion *R) { 188243730Srwatson 189243730Srwatson llvm::FoldingSetNodeID profile; 190243730Srwatson SymbolDerived::Profile(profile, parentSymbol, R); 191243730Srwatson void *InsertPos; 192243730Srwatson SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 193243730Srwatson if (!SD) { 194243730Srwatson SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 195243730Srwatson new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 196243730Srwatson DataSet.InsertNode(SD, InsertPos); 197243730Srwatson ++SymbolCounter; 198243730Srwatson } 199243730Srwatson 200243730Srwatson return cast<SymbolDerived>(SD); 201243730Srwatson} 202243730Srwatson 203243730Srwatsonconst SymbolExtent* 204243730SrwatsonSymbolManager::getExtentSymbol(const SubRegion *R) { 205243730Srwatson llvm::FoldingSetNodeID profile; 206243730Srwatson SymbolExtent::Profile(profile, R); 207243730Srwatson void *InsertPos; 208243730Srwatson SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 209243730Srwatson if (!SD) { 210243730Srwatson SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 211243730Srwatson new (SD) SymbolExtent(SymbolCounter, R); 212243730Srwatson DataSet.InsertNode(SD, InsertPos); 213243730Srwatson ++SymbolCounter; 214243730Srwatson } 215243730Srwatson 216243730Srwatson return cast<SymbolExtent>(SD); 217243730Srwatson} 218243730Srwatson 219243730Srwatsonconst SymbolMetadata* 220243730SrwatsonSymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 221243730Srwatson unsigned Count, const void *SymbolTag) { 222243730Srwatson 223243730Srwatson llvm::FoldingSetNodeID profile; 224243730Srwatson SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 225243730Srwatson void *InsertPos; 226243730Srwatson SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 227243730Srwatson if (!SD) { 228243730Srwatson SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 229243730Srwatson new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 230243730Srwatson DataSet.InsertNode(SD, InsertPos); 231243730Srwatson ++SymbolCounter; 232243730Srwatson } 233 234 return cast<SymbolMetadata>(SD); 235} 236 237const SymbolCast* 238SymbolManager::getCastSymbol(const SymExpr *Op, 239 QualType From, QualType To) { 240 llvm::FoldingSetNodeID ID; 241 SymbolCast::Profile(ID, Op, From, To); 242 void *InsertPos; 243 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 244 if (!data) { 245 data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 246 new (data) SymbolCast(Op, From, To); 247 DataSet.InsertNode(data, InsertPos); 248 } 249 250 return cast<SymbolCast>(data); 251} 252 253const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 254 BinaryOperator::Opcode op, 255 const llvm::APSInt& v, 256 QualType t) { 257 llvm::FoldingSetNodeID ID; 258 SymIntExpr::Profile(ID, lhs, op, v, t); 259 void *InsertPos; 260 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 261 262 if (!data) { 263 data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 264 new (data) SymIntExpr(lhs, op, v, t); 265 DataSet.InsertNode(data, InsertPos); 266 } 267 268 return cast<SymIntExpr>(data); 269} 270 271const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 272 BinaryOperator::Opcode op, 273 const SymExpr *rhs, 274 QualType t) { 275 llvm::FoldingSetNodeID ID; 276 IntSymExpr::Profile(ID, lhs, op, rhs, t); 277 void *InsertPos; 278 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 279 280 if (!data) { 281 data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 282 new (data) IntSymExpr(lhs, op, rhs, t); 283 DataSet.InsertNode(data, InsertPos); 284 } 285 286 return cast<IntSymExpr>(data); 287} 288 289const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 290 BinaryOperator::Opcode op, 291 const SymExpr *rhs, 292 QualType t) { 293 llvm::FoldingSetNodeID ID; 294 SymSymExpr::Profile(ID, lhs, op, rhs, t); 295 void *InsertPos; 296 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 297 298 if (!data) { 299 data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 300 new (data) SymSymExpr(lhs, op, rhs, t); 301 DataSet.InsertNode(data, InsertPos); 302 } 303 304 return cast<SymSymExpr>(data); 305} 306 307QualType SymbolConjured::getType() const { 308 return T; 309} 310 311QualType SymbolDerived::getType() const { 312 return R->getValueType(); 313} 314 315QualType SymbolExtent::getType() const { 316 ASTContext &Ctx = R->getMemRegionManager()->getContext(); 317 return Ctx.getSizeType(); 318} 319 320QualType SymbolMetadata::getType() const { 321 return T; 322} 323 324QualType SymbolRegionValue::getType() const { 325 return R->getValueType(); 326} 327 328SymbolManager::~SymbolManager() { 329 for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 330 E = SymbolDependencies.end(); I != E; ++I) { 331 delete I->second; 332 } 333 334} 335 336bool SymbolManager::canSymbolicate(QualType T) { 337 T = T.getCanonicalType(); 338 339 if (Loc::isLocType(T)) 340 return true; 341 342 if (T->isIntegralOrEnumerationType()) 343 return true; 344 345 if (T->isRecordType() && !T->isUnionType()) 346 return true; 347 348 return false; 349} 350 351void SymbolManager::addSymbolDependency(const SymbolRef Primary, 352 const SymbolRef Dependent) { 353 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 354 SymbolRefSmallVectorTy *dependencies = 0; 355 if (I == SymbolDependencies.end()) { 356 dependencies = new SymbolRefSmallVectorTy(); 357 SymbolDependencies[Primary] = dependencies; 358 } else { 359 dependencies = I->second; 360 } 361 dependencies->push_back(Dependent); 362} 363 364const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 365 const SymbolRef Primary) { 366 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 367 if (I == SymbolDependencies.end()) 368 return 0; 369 return I->second; 370} 371 372void SymbolReaper::markDependentsLive(SymbolRef sym) { 373 // Do not mark dependents more then once. 374 SymbolMapTy::iterator LI = TheLiving.find(sym); 375 assert(LI != TheLiving.end() && "The primary symbol is not live."); 376 if (LI->second == HaveMarkedDependents) 377 return; 378 LI->second = HaveMarkedDependents; 379 380 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 381 for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 382 E = Deps->end(); I != E; ++I) { 383 if (TheLiving.find(*I) != TheLiving.end()) 384 continue; 385 markLive(*I); 386 } 387 } 388} 389 390void SymbolReaper::markLive(SymbolRef sym) { 391 TheLiving[sym] = NotProcessed; 392 TheDead.erase(sym); 393 markDependentsLive(sym); 394} 395 396void SymbolReaper::markLive(const MemRegion *region) { 397 RegionRoots.insert(region); 398} 399 400void SymbolReaper::markInUse(SymbolRef sym) { 401 if (isa<SymbolMetadata>(sym)) 402 MetadataInUse.insert(sym); 403} 404 405bool SymbolReaper::maybeDead(SymbolRef sym) { 406 if (isLive(sym)) 407 return false; 408 409 TheDead.insert(sym); 410 return true; 411} 412 413bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 414 if (RegionRoots.count(MR)) 415 return true; 416 417 MR = MR->getBaseRegion(); 418 419 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 420 return isLive(SR->getSymbol()); 421 422 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 423 return isLive(VR, true); 424 425 // FIXME: This is a gross over-approximation. What we really need is a way to 426 // tell if anything still refers to this region. Unlike SymbolicRegions, 427 // AllocaRegions don't have associated symbols, though, so we don't actually 428 // have a way to track their liveness. 429 if (isa<AllocaRegion>(MR)) 430 return true; 431 432 if (isa<CXXThisRegion>(MR)) 433 return true; 434 435 if (isa<MemSpaceRegion>(MR)) 436 return true; 437 438 if (isa<CodeTextRegion>(MR)) 439 return true; 440 441 return false; 442} 443 444bool SymbolReaper::isLive(SymbolRef sym) { 445 if (TheLiving.count(sym)) { 446 markDependentsLive(sym); 447 return true; 448 } 449 450 bool KnownLive; 451 452 switch (sym->getKind()) { 453 case SymExpr::RegionValueKind: 454 KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion()); 455 break; 456 case SymExpr::ConjuredKind: 457 KnownLive = false; 458 break; 459 case SymExpr::DerivedKind: 460 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 461 break; 462 case SymExpr::ExtentKind: 463 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 464 break; 465 case SymExpr::MetadataKind: 466 KnownLive = MetadataInUse.count(sym) && 467 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 468 if (KnownLive) 469 MetadataInUse.erase(sym); 470 break; 471 case SymExpr::SymIntKind: 472 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 473 break; 474 case SymExpr::IntSymKind: 475 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 476 break; 477 case SymExpr::SymSymKind: 478 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 479 isLive(cast<SymSymExpr>(sym)->getRHS()); 480 break; 481 case SymExpr::CastSymbolKind: 482 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 483 break; 484 } 485 486 if (KnownLive) 487 markLive(sym); 488 489 return KnownLive; 490} 491 492bool 493SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 494 if (LCtx == 0) 495 return false; 496 497 if (LCtx != ELCtx) { 498 // If the reaper's location context is a parent of the expression's 499 // location context, then the expression value is now "out of scope". 500 if (LCtx->isParentOf(ELCtx)) 501 return false; 502 return true; 503 } 504 505 // If no statement is provided, everything is this and parent contexts is live. 506 if (!Loc) 507 return true; 508 509 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 510} 511 512bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 513 const StackFrameContext *VarContext = VR->getStackFrame(); 514 515 if (!VarContext) 516 return true; 517 518 if (!LCtx) 519 return false; 520 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 521 522 if (VarContext == CurrentContext) { 523 // If no statement is provided, everything is live. 524 if (!Loc) 525 return true; 526 527 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 528 return true; 529 530 if (!includeStoreBindings) 531 return false; 532 533 unsigned &cachedQuery = 534 const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 535 536 if (cachedQuery) { 537 return cachedQuery == 1; 538 } 539 540 // Query the store to see if the region occurs in any live bindings. 541 if (Store store = reapedStore.getStore()) { 542 bool hasRegion = 543 reapedStore.getStoreManager().includedInBindings(store, VR); 544 cachedQuery = hasRegion ? 1 : 2; 545 return hasRegion; 546 } 547 548 return false; 549 } 550 551 return VarContext->isParentOf(CurrentContext); 552} 553 554SymbolVisitor::~SymbolVisitor() {} 555