SymbolManager.cpp revision 344472ebeded2fca2ed5013b9e87f81d09bfa908
1//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines SymbolManager, a class that manages symbolic values 11// created for use by ExprEngine and related classes. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 16#include "clang/Analysis/Analyses/LiveVariables.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 19#include "llvm/Support/raw_ostream.h" 20 21using namespace clang; 22using namespace ento; 23 24void SymExpr::anchor() { } 25 26void SymExpr::dump() const { 27 dumpToStream(llvm::errs()); 28} 29 30void SymIntExpr::dumpToStream(raw_ostream &os) const { 31 os << '('; 32 getLHS()->dumpToStream(os); 33 os << ") " 34 << BinaryOperator::getOpcodeStr(getOpcode()) << ' ' 35 << getRHS().getZExtValue(); 36 if (getRHS().isUnsigned()) 37 os << 'U'; 38} 39 40void IntSymExpr::dumpToStream(raw_ostream &os) const { 41 os << getLHS().getZExtValue(); 42 if (getLHS().isUnsigned()) 43 os << 'U'; 44 os << ' ' 45 << BinaryOperator::getOpcodeStr(getOpcode()) 46 << " ("; 47 getRHS()->dumpToStream(os); 48 os << ')'; 49} 50 51void SymSymExpr::dumpToStream(raw_ostream &os) const { 52 os << '('; 53 getLHS()->dumpToStream(os); 54 os << ") " 55 << BinaryOperator::getOpcodeStr(getOpcode()) 56 << " ("; 57 getRHS()->dumpToStream(os); 58 os << ')'; 59} 60 61void SymbolCast::dumpToStream(raw_ostream &os) const { 62 os << '(' << ToTy.getAsString() << ") ("; 63 Operand->dumpToStream(os); 64 os << ')'; 65} 66 67void SymbolConjured::dumpToStream(raw_ostream &os) const { 68 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 69} 70 71void SymbolDerived::dumpToStream(raw_ostream &os) const { 72 os << "derived_$" << getSymbolID() << '{' 73 << getParentSymbol() << ',' << getRegion() << '}'; 74} 75 76void SymbolExtent::dumpToStream(raw_ostream &os) const { 77 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 78} 79 80void SymbolMetadata::dumpToStream(raw_ostream &os) const { 81 os << "meta_$" << getSymbolID() << '{' 82 << getRegion() << ',' << T.getAsString() << '}'; 83} 84 85void SymbolData::anchor() { } 86 87void SymbolRegionValue::dumpToStream(raw_ostream &os) const { 88 os << "reg_$" << getSymbolID() << "<" << R << ">"; 89} 90 91bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 92 return itr == X.itr; 93} 94 95bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 96 return itr != X.itr; 97} 98 99SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 100 itr.push_back(SE); 101} 102 103SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 104 assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 105 expand(); 106 return *this; 107} 108 109SymbolRef SymExpr::symbol_iterator::operator*() { 110 assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 111 return itr.back(); 112} 113 114void SymExpr::symbol_iterator::expand() { 115 const SymExpr *SE = itr.pop_back_val(); 116 117 switch (SE->getKind()) { 118 case SymExpr::RegionValueKind: 119 case SymExpr::ConjuredKind: 120 case SymExpr::DerivedKind: 121 case SymExpr::ExtentKind: 122 case SymExpr::MetadataKind: 123 return; 124 case SymExpr::CastSymbolKind: 125 itr.push_back(cast<SymbolCast>(SE)->getOperand()); 126 return; 127 case SymExpr::SymIntKind: 128 itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 129 return; 130 case SymExpr::IntSymKind: 131 itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 132 return; 133 case SymExpr::SymSymKind: { 134 const SymSymExpr *x = cast<SymSymExpr>(SE); 135 itr.push_back(x->getLHS()); 136 itr.push_back(x->getRHS()); 137 return; 138 } 139 } 140 llvm_unreachable("unhandled expansion case"); 141} 142 143unsigned SymExpr::computeComplexity() const { 144 unsigned R = 0; 145 for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I) 146 R++; 147 return R; 148} 149 150const SymbolRegionValue* 151SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 152 llvm::FoldingSetNodeID profile; 153 SymbolRegionValue::Profile(profile, R); 154 void *InsertPos; 155 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 156 if (!SD) { 157 SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 158 new (SD) SymbolRegionValue(SymbolCounter, R); 159 DataSet.InsertNode(SD, InsertPos); 160 ++SymbolCounter; 161 } 162 163 return cast<SymbolRegionValue>(SD); 164} 165 166const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 167 const LocationContext *LCtx, 168 QualType T, 169 unsigned Count, 170 const void *SymbolTag) { 171 llvm::FoldingSetNodeID profile; 172 SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 173 void *InsertPos; 174 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 175 if (!SD) { 176 SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 177 new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 178 DataSet.InsertNode(SD, InsertPos); 179 ++SymbolCounter; 180 } 181 182 return cast<SymbolConjured>(SD); 183} 184 185const SymbolDerived* 186SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 187 const TypedValueRegion *R) { 188 189 llvm::FoldingSetNodeID profile; 190 SymbolDerived::Profile(profile, parentSymbol, R); 191 void *InsertPos; 192 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 193 if (!SD) { 194 SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 195 new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 196 DataSet.InsertNode(SD, InsertPos); 197 ++SymbolCounter; 198 } 199 200 return cast<SymbolDerived>(SD); 201} 202 203const SymbolExtent* 204SymbolManager::getExtentSymbol(const SubRegion *R) { 205 llvm::FoldingSetNodeID profile; 206 SymbolExtent::Profile(profile, R); 207 void *InsertPos; 208 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 209 if (!SD) { 210 SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 211 new (SD) SymbolExtent(SymbolCounter, R); 212 DataSet.InsertNode(SD, InsertPos); 213 ++SymbolCounter; 214 } 215 216 return cast<SymbolExtent>(SD); 217} 218 219const SymbolMetadata* 220SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 221 unsigned Count, const void *SymbolTag) { 222 223 llvm::FoldingSetNodeID profile; 224 SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 225 void *InsertPos; 226 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 227 if (!SD) { 228 SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 229 new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 230 DataSet.InsertNode(SD, InsertPos); 231 ++SymbolCounter; 232 } 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 return false; 439} 440 441bool SymbolReaper::isLive(SymbolRef sym) { 442 if (TheLiving.count(sym)) { 443 markDependentsLive(sym); 444 return true; 445 } 446 447 bool KnownLive; 448 449 switch (sym->getKind()) { 450 case SymExpr::RegionValueKind: 451 KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion()); 452 break; 453 case SymExpr::ConjuredKind: 454 KnownLive = false; 455 break; 456 case SymExpr::DerivedKind: 457 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 458 break; 459 case SymExpr::ExtentKind: 460 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 461 break; 462 case SymExpr::MetadataKind: 463 KnownLive = MetadataInUse.count(sym) && 464 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 465 if (KnownLive) 466 MetadataInUse.erase(sym); 467 break; 468 case SymExpr::SymIntKind: 469 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 470 break; 471 case SymExpr::IntSymKind: 472 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 473 break; 474 case SymExpr::SymSymKind: 475 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 476 isLive(cast<SymSymExpr>(sym)->getRHS()); 477 break; 478 case SymExpr::CastSymbolKind: 479 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 480 break; 481 } 482 483 if (KnownLive) 484 markLive(sym); 485 486 return KnownLive; 487} 488 489bool 490SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 491 if (LCtx == 0) 492 return false; 493 494 if (LCtx != ELCtx) { 495 // If the reaper's location context is a parent of the expression's 496 // location context, then the expression value is now "out of scope". 497 if (LCtx->isParentOf(ELCtx)) 498 return false; 499 return true; 500 } 501 502 // If no statement is provided, everything is this and parent contexts is live. 503 if (!Loc) 504 return true; 505 506 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 507} 508 509bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 510 const StackFrameContext *VarContext = VR->getStackFrame(); 511 512 if (!VarContext) 513 return true; 514 515 if (!LCtx) 516 return false; 517 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 518 519 if (VarContext == CurrentContext) { 520 // If no statement is provided, everything is live. 521 if (!Loc) 522 return true; 523 524 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 525 return true; 526 527 if (!includeStoreBindings) 528 return false; 529 530 unsigned &cachedQuery = 531 const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 532 533 if (cachedQuery) { 534 return cachedQuery == 1; 535 } 536 537 // Query the store to see if the region occurs in any live bindings. 538 if (Store store = reapedStore.getStore()) { 539 bool hasRegion = 540 reapedStore.getStoreManager().includedInBindings(store, VR); 541 cachedQuery = hasRegion ? 1 : 2; 542 return hasRegion; 543 } 544 545 return false; 546 } 547 548 return VarContext->isParentOf(CurrentContext); 549} 550 551SymbolVisitor::~SymbolVisitor() {} 552