SymbolManager.cpp revision 8501b7a1c4c4a9ba0ea6cb8e500e601ef3759deb
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 30static void print(raw_ostream &os, BinaryOperator::Opcode Op) { 31 switch (Op) { 32 default: 33 llvm_unreachable("operator printing not implemented"); 34 case BO_Mul: os << '*' ; break; 35 case BO_Div: os << '/' ; break; 36 case BO_Rem: os << '%' ; break; 37 case BO_Add: os << '+' ; break; 38 case BO_Sub: os << '-' ; break; 39 case BO_Shl: os << "<<" ; break; 40 case BO_Shr: os << ">>" ; break; 41 case BO_LT: os << "<" ; break; 42 case BO_GT: os << '>' ; break; 43 case BO_LE: os << "<=" ; break; 44 case BO_GE: os << ">=" ; break; 45 case BO_EQ: os << "==" ; break; 46 case BO_NE: os << "!=" ; break; 47 case BO_And: os << '&' ; break; 48 case BO_Xor: os << '^' ; break; 49 case BO_Or: os << '|' ; break; 50 } 51} 52 53void SymIntExpr::dumpToStream(raw_ostream &os) const { 54 os << '('; 55 getLHS()->dumpToStream(os); 56 os << ") "; 57 print(os, getOpcode()); 58 os << ' ' << getRHS().getZExtValue(); 59 if (getRHS().isUnsigned()) os << 'U'; 60} 61 62void IntSymExpr::dumpToStream(raw_ostream &os) const { 63 os << ' ' << getLHS().getZExtValue(); 64 if (getLHS().isUnsigned()) os << 'U'; 65 print(os, getOpcode()); 66 os << '('; 67 getRHS()->dumpToStream(os); 68 os << ") "; 69} 70 71void SymSymExpr::dumpToStream(raw_ostream &os) const { 72 os << '('; 73 getLHS()->dumpToStream(os); 74 os << ") "; 75 os << '('; 76 getRHS()->dumpToStream(os); 77 os << ')'; 78} 79 80void SymbolCast::dumpToStream(raw_ostream &os) const { 81 os << '(' << ToTy.getAsString() << ") ("; 82 Operand->dumpToStream(os); 83 os << ')'; 84} 85 86void SymbolConjured::dumpToStream(raw_ostream &os) const { 87 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 88} 89 90void SymbolDerived::dumpToStream(raw_ostream &os) const { 91 os << "derived_$" << getSymbolID() << '{' 92 << getParentSymbol() << ',' << getRegion() << '}'; 93} 94 95void SymbolExtent::dumpToStream(raw_ostream &os) const { 96 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 97} 98 99void SymbolMetadata::dumpToStream(raw_ostream &os) const { 100 os << "meta_$" << getSymbolID() << '{' 101 << getRegion() << ',' << T.getAsString() << '}'; 102} 103 104void SymbolData::anchor() { } 105 106void SymbolRegionValue::dumpToStream(raw_ostream &os) const { 107 os << "reg_$" << getSymbolID() << "<" << R << ">"; 108} 109 110bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 111 return itr == X.itr; 112} 113 114bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 115 return itr != X.itr; 116} 117 118SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 119 itr.push_back(SE); 120} 121 122SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 123 assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 124 expand(); 125 return *this; 126} 127 128SymbolRef SymExpr::symbol_iterator::operator*() { 129 assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 130 return itr.back(); 131} 132 133void SymExpr::symbol_iterator::expand() { 134 const SymExpr *SE = itr.back(); 135 itr.pop_back(); 136 137 switch (SE->getKind()) { 138 case SymExpr::RegionValueKind: 139 case SymExpr::ConjuredKind: 140 case SymExpr::DerivedKind: 141 case SymExpr::ExtentKind: 142 case SymExpr::MetadataKind: 143 return; 144 case SymExpr::CastSymbolKind: 145 itr.push_back(cast<SymbolCast>(SE)->getOperand()); 146 return; 147 case SymExpr::SymIntKind: 148 itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 149 return; 150 case SymExpr::IntSymKind: 151 itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 152 return; 153 case SymExpr::SymSymKind: { 154 const SymSymExpr *x = cast<SymSymExpr>(SE); 155 itr.push_back(x->getLHS()); 156 itr.push_back(x->getRHS()); 157 return; 158 } 159 } 160 llvm_unreachable("unhandled expansion case"); 161} 162 163unsigned SymExpr::computeComplexity() const { 164 unsigned R = 0; 165 for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I) 166 R++; 167 return R; 168} 169 170const SymbolRegionValue* 171SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 172 llvm::FoldingSetNodeID profile; 173 SymbolRegionValue::Profile(profile, R); 174 void *InsertPos; 175 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 176 if (!SD) { 177 SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 178 new (SD) SymbolRegionValue(SymbolCounter, R); 179 DataSet.InsertNode(SD, InsertPos); 180 ++SymbolCounter; 181 } 182 183 return cast<SymbolRegionValue>(SD); 184} 185 186const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 187 const LocationContext *LCtx, 188 QualType T, 189 unsigned Count, 190 const void *SymbolTag) { 191 llvm::FoldingSetNodeID profile; 192 SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 193 void *InsertPos; 194 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 195 if (!SD) { 196 SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 197 new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 198 DataSet.InsertNode(SD, InsertPos); 199 ++SymbolCounter; 200 } 201 202 return cast<SymbolConjured>(SD); 203} 204 205const SymbolDerived* 206SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 207 const TypedValueRegion *R) { 208 209 llvm::FoldingSetNodeID profile; 210 SymbolDerived::Profile(profile, parentSymbol, R); 211 void *InsertPos; 212 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 213 if (!SD) { 214 SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 215 new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 216 DataSet.InsertNode(SD, InsertPos); 217 ++SymbolCounter; 218 } 219 220 return cast<SymbolDerived>(SD); 221} 222 223const SymbolExtent* 224SymbolManager::getExtentSymbol(const SubRegion *R) { 225 llvm::FoldingSetNodeID profile; 226 SymbolExtent::Profile(profile, R); 227 void *InsertPos; 228 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 229 if (!SD) { 230 SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 231 new (SD) SymbolExtent(SymbolCounter, R); 232 DataSet.InsertNode(SD, InsertPos); 233 ++SymbolCounter; 234 } 235 236 return cast<SymbolExtent>(SD); 237} 238 239const SymbolMetadata* 240SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 241 unsigned Count, const void *SymbolTag) { 242 243 llvm::FoldingSetNodeID profile; 244 SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 245 void *InsertPos; 246 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 247 if (!SD) { 248 SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 249 new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 250 DataSet.InsertNode(SD, InsertPos); 251 ++SymbolCounter; 252 } 253 254 return cast<SymbolMetadata>(SD); 255} 256 257const SymbolCast* 258SymbolManager::getCastSymbol(const SymExpr *Op, 259 QualType From, QualType To) { 260 llvm::FoldingSetNodeID ID; 261 SymbolCast::Profile(ID, Op, From, To); 262 void *InsertPos; 263 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 264 if (!data) { 265 data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 266 new (data) SymbolCast(Op, From, To); 267 DataSet.InsertNode(data, InsertPos); 268 } 269 270 return cast<SymbolCast>(data); 271} 272 273const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 274 BinaryOperator::Opcode op, 275 const llvm::APSInt& v, 276 QualType t) { 277 llvm::FoldingSetNodeID ID; 278 SymIntExpr::Profile(ID, lhs, op, v, t); 279 void *InsertPos; 280 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 281 282 if (!data) { 283 data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 284 new (data) SymIntExpr(lhs, op, v, t); 285 DataSet.InsertNode(data, InsertPos); 286 } 287 288 return cast<SymIntExpr>(data); 289} 290 291const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 292 BinaryOperator::Opcode op, 293 const SymExpr *rhs, 294 QualType t) { 295 llvm::FoldingSetNodeID ID; 296 IntSymExpr::Profile(ID, lhs, op, rhs, t); 297 void *InsertPos; 298 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 299 300 if (!data) { 301 data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 302 new (data) IntSymExpr(lhs, op, rhs, t); 303 DataSet.InsertNode(data, InsertPos); 304 } 305 306 return cast<IntSymExpr>(data); 307} 308 309const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 310 BinaryOperator::Opcode op, 311 const SymExpr *rhs, 312 QualType t) { 313 llvm::FoldingSetNodeID ID; 314 SymSymExpr::Profile(ID, lhs, op, rhs, t); 315 void *InsertPos; 316 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 317 318 if (!data) { 319 data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 320 new (data) SymSymExpr(lhs, op, rhs, t); 321 DataSet.InsertNode(data, InsertPos); 322 } 323 324 return cast<SymSymExpr>(data); 325} 326 327QualType SymbolConjured::getType() const { 328 return T; 329} 330 331QualType SymbolDerived::getType() const { 332 return R->getValueType(); 333} 334 335QualType SymbolExtent::getType() const { 336 ASTContext &Ctx = R->getMemRegionManager()->getContext(); 337 return Ctx.getSizeType(); 338} 339 340QualType SymbolMetadata::getType() const { 341 return T; 342} 343 344QualType SymbolRegionValue::getType() const { 345 return R->getValueType(); 346} 347 348SymbolManager::~SymbolManager() { 349 for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 350 E = SymbolDependencies.end(); I != E; ++I) { 351 delete I->second; 352 } 353 354} 355 356bool SymbolManager::canSymbolicate(QualType T) { 357 T = T.getCanonicalType(); 358 359 if (Loc::isLocType(T)) 360 return true; 361 362 if (T->isIntegerType()) 363 return T->isScalarType(); 364 365 if (T->isRecordType() && !T->isUnionType()) 366 return true; 367 368 return false; 369} 370 371void SymbolManager::addSymbolDependency(const SymbolRef Primary, 372 const SymbolRef Dependent) { 373 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 374 SymbolRefSmallVectorTy *dependencies = 0; 375 if (I == SymbolDependencies.end()) { 376 dependencies = new SymbolRefSmallVectorTy(); 377 SymbolDependencies[Primary] = dependencies; 378 } else { 379 dependencies = I->second; 380 } 381 dependencies->push_back(Dependent); 382} 383 384const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 385 const SymbolRef Primary) { 386 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 387 if (I == SymbolDependencies.end()) 388 return 0; 389 return I->second; 390} 391 392void SymbolReaper::markDependentsLive(SymbolRef sym) { 393 // Do not mark dependents more then once. 394 SymbolMapTy::iterator LI = TheLiving.find(sym); 395 assert(LI != TheLiving.end() && "The primary symbol is not live."); 396 if (LI->second == HaveMarkedDependents) 397 return; 398 LI->second = HaveMarkedDependents; 399 400 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 401 for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 402 E = Deps->end(); I != E; ++I) { 403 if (TheLiving.find(*I) != TheLiving.end()) 404 continue; 405 markLive(*I); 406 } 407 } 408} 409 410void SymbolReaper::markLive(SymbolRef sym) { 411 TheLiving[sym] = NotProcessed; 412 TheDead.erase(sym); 413 markDependentsLive(sym); 414} 415 416void SymbolReaper::markLive(const MemRegion *region) { 417 RegionRoots.insert(region); 418} 419 420void SymbolReaper::markInUse(SymbolRef sym) { 421 if (isa<SymbolMetadata>(sym)) 422 MetadataInUse.insert(sym); 423} 424 425bool SymbolReaper::maybeDead(SymbolRef sym) { 426 if (isLive(sym)) 427 return false; 428 429 TheDead.insert(sym); 430 return true; 431} 432 433bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 434 if (RegionRoots.count(MR)) 435 return true; 436 437 MR = MR->getBaseRegion(); 438 439 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 440 return isLive(SR->getSymbol()); 441 442 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 443 return isLive(VR, true); 444 445 // FIXME: This is a gross over-approximation. What we really need is a way to 446 // tell if anything still refers to this region. Unlike SymbolicRegions, 447 // AllocaRegions don't have associated symbols, though, so we don't actually 448 // have a way to track their liveness. 449 if (isa<AllocaRegion>(MR)) 450 return true; 451 452 if (isa<CXXThisRegion>(MR)) 453 return true; 454 455 if (isa<MemSpaceRegion>(MR)) 456 return true; 457 458 return false; 459} 460 461bool SymbolReaper::isLive(SymbolRef sym) { 462 if (TheLiving.count(sym)) { 463 markDependentsLive(sym); 464 return true; 465 } 466 467 bool KnownLive; 468 469 switch (sym->getKind()) { 470 case SymExpr::RegionValueKind: 471 // FIXME: We should be able to use isLiveRegion here (this behavior 472 // predates isLiveRegion), but doing so causes test failures. Investigate. 473 KnownLive = true; 474 break; 475 case SymExpr::ConjuredKind: 476 KnownLive = false; 477 break; 478 case SymExpr::DerivedKind: 479 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 480 break; 481 case SymExpr::ExtentKind: 482 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 483 break; 484 case SymExpr::MetadataKind: 485 KnownLive = MetadataInUse.count(sym) && 486 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 487 if (KnownLive) 488 MetadataInUse.erase(sym); 489 break; 490 case SymExpr::SymIntKind: 491 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 492 break; 493 case SymExpr::IntSymKind: 494 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 495 break; 496 case SymExpr::SymSymKind: 497 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 498 isLive(cast<SymSymExpr>(sym)->getRHS()); 499 break; 500 case SymExpr::CastSymbolKind: 501 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 502 break; 503 } 504 505 if (KnownLive) 506 markLive(sym); 507 508 return KnownLive; 509} 510 511bool 512SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 513 if (LCtx == 0) 514 return false; 515 516 if (LCtx != ELCtx) { 517 // If the reaper's location context is a parent of the expression's 518 // location context, then the expression value is now "out of scope". 519 if (LCtx->isParentOf(ELCtx)) 520 return false; 521 return true; 522 } 523 524 // If no statement is provided, everything is this and parent contexts is live. 525 if (!Loc) 526 return true; 527 528 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 529} 530 531bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 532 const StackFrameContext *VarContext = VR->getStackFrame(); 533 534 if (!VarContext) 535 return true; 536 537 if (!LCtx) 538 return false; 539 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 540 541 if (VarContext == CurrentContext) { 542 // If no statement is provided, everything is live. 543 if (!Loc) 544 return true; 545 546 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 547 return true; 548 549 if (!includeStoreBindings) 550 return false; 551 552 unsigned &cachedQuery = 553 const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 554 555 if (cachedQuery) { 556 return cachedQuery == 1; 557 } 558 559 // Query the store to see if the region occurs in any live bindings. 560 if (Store store = reapedStore.getStore()) { 561 bool hasRegion = 562 reapedStore.getStoreManager().includedInBindings(store, VR); 563 cachedQuery = hasRegion ? 1 : 2; 564 return hasRegion; 565 } 566 567 return false; 568 } 569 570 return VarContext->isParentOf(CurrentContext); 571} 572 573SymbolVisitor::~SymbolVisitor() {} 574