SymbolManager.cpp revision 0b3ade86a1c60cf0c7b56aa238aff458eb7f5974
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 while (!isa<SymbolData>(itr.back())) expand(); 121} 122 123SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 124 assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 125 assert(isa<SymbolData>(itr.back())); 126 itr.pop_back(); 127 if (!itr.empty()) 128 while (!isa<SymbolData>(itr.back())) expand(); 129 return *this; 130} 131 132SymbolRef SymExpr::symbol_iterator::operator*() { 133 assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 134 return cast<SymbolData>(itr.back()); 135} 136 137void SymExpr::symbol_iterator::expand() { 138 const SymExpr *SE = itr.back(); 139 itr.pop_back(); 140 141 switch (SE->getKind()) { 142 case SymExpr::RegionValueKind: 143 case SymExpr::ConjuredKind: 144 case SymExpr::DerivedKind: 145 case SymExpr::ExtentKind: 146 case SymExpr::MetadataKind: 147 return; 148 case SymExpr::CastSymbolKind: 149 itr.push_back(cast<SymbolCast>(SE)->getOperand()); 150 return; 151 case SymExpr::SymIntKind: 152 itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 153 return; 154 case SymExpr::IntSymKind: 155 itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 156 return; 157 case SymExpr::SymSymKind: { 158 const SymSymExpr *x = cast<SymSymExpr>(SE); 159 itr.push_back(x->getLHS()); 160 itr.push_back(x->getRHS()); 161 return; 162 } 163 } 164 llvm_unreachable("unhandled expansion case"); 165} 166 167const SymbolRegionValue* 168SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 169 llvm::FoldingSetNodeID profile; 170 SymbolRegionValue::Profile(profile, R); 171 void *InsertPos; 172 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 173 if (!SD) { 174 SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 175 new (SD) SymbolRegionValue(SymbolCounter, R); 176 DataSet.InsertNode(SD, InsertPos); 177 ++SymbolCounter; 178 } 179 180 return cast<SymbolRegionValue>(SD); 181} 182 183const SymbolConjured* 184SymbolManager::getConjuredSymbol(const Stmt *E, const LocationContext *LCtx, 185 QualType T, unsigned Count, 186 const void *SymbolTag) { 187 188 llvm::FoldingSetNodeID profile; 189 SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 190 void *InsertPos; 191 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 192 if (!SD) { 193 SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 194 new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 195 DataSet.InsertNode(SD, InsertPos); 196 ++SymbolCounter; 197 } 198 199 return cast<SymbolConjured>(SD); 200} 201 202const SymbolDerived* 203SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 204 const TypedValueRegion *R) { 205 206 llvm::FoldingSetNodeID profile; 207 SymbolDerived::Profile(profile, parentSymbol, R); 208 void *InsertPos; 209 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 210 if (!SD) { 211 SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 212 new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 213 DataSet.InsertNode(SD, InsertPos); 214 ++SymbolCounter; 215 } 216 217 return cast<SymbolDerived>(SD); 218} 219 220const SymbolExtent* 221SymbolManager::getExtentSymbol(const SubRegion *R) { 222 llvm::FoldingSetNodeID profile; 223 SymbolExtent::Profile(profile, R); 224 void *InsertPos; 225 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 226 if (!SD) { 227 SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 228 new (SD) SymbolExtent(SymbolCounter, R); 229 DataSet.InsertNode(SD, InsertPos); 230 ++SymbolCounter; 231 } 232 233 return cast<SymbolExtent>(SD); 234} 235 236const SymbolMetadata* 237SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 238 unsigned Count, const void *SymbolTag) { 239 240 llvm::FoldingSetNodeID profile; 241 SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 242 void *InsertPos; 243 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 244 if (!SD) { 245 SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 246 new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 247 DataSet.InsertNode(SD, InsertPos); 248 ++SymbolCounter; 249 } 250 251 return cast<SymbolMetadata>(SD); 252} 253 254const SymbolCast* 255SymbolManager::getCastSymbol(const SymExpr *Op, 256 QualType From, QualType To) { 257 llvm::FoldingSetNodeID ID; 258 SymbolCast::Profile(ID, Op, From, To); 259 void *InsertPos; 260 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 261 if (!data) { 262 data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 263 new (data) SymbolCast(Op, From, To); 264 DataSet.InsertNode(data, InsertPos); 265 } 266 267 return cast<SymbolCast>(data); 268} 269 270const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 271 BinaryOperator::Opcode op, 272 const llvm::APSInt& v, 273 QualType t) { 274 llvm::FoldingSetNodeID ID; 275 SymIntExpr::Profile(ID, lhs, op, v, t); 276 void *InsertPos; 277 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 278 279 if (!data) { 280 data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 281 new (data) SymIntExpr(lhs, op, v, t); 282 DataSet.InsertNode(data, InsertPos); 283 } 284 285 return cast<SymIntExpr>(data); 286} 287 288const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 289 BinaryOperator::Opcode op, 290 const SymExpr *rhs, 291 QualType t) { 292 llvm::FoldingSetNodeID ID; 293 IntSymExpr::Profile(ID, lhs, op, rhs, t); 294 void *InsertPos; 295 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 296 297 if (!data) { 298 data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 299 new (data) IntSymExpr(lhs, op, rhs, t); 300 DataSet.InsertNode(data, InsertPos); 301 } 302 303 return cast<IntSymExpr>(data); 304} 305 306const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 307 BinaryOperator::Opcode op, 308 const SymExpr *rhs, 309 QualType t) { 310 llvm::FoldingSetNodeID ID; 311 SymSymExpr::Profile(ID, lhs, op, rhs, t); 312 void *InsertPos; 313 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 314 315 if (!data) { 316 data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 317 new (data) SymSymExpr(lhs, op, rhs, t); 318 DataSet.InsertNode(data, InsertPos); 319 } 320 321 return cast<SymSymExpr>(data); 322} 323 324QualType SymbolConjured::getType(ASTContext&) const { 325 return T; 326} 327 328QualType SymbolDerived::getType(ASTContext &Ctx) const { 329 return R->getValueType(); 330} 331 332QualType SymbolExtent::getType(ASTContext &Ctx) const { 333 return Ctx.getSizeType(); 334} 335 336QualType SymbolMetadata::getType(ASTContext&) const { 337 return T; 338} 339 340QualType SymbolRegionValue::getType(ASTContext &C) const { 341 return R->getValueType(); 342} 343 344SymbolManager::~SymbolManager() { 345 for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 346 E = SymbolDependencies.end(); I != E; ++I) { 347 delete I->second; 348 } 349 350} 351 352bool SymbolManager::canSymbolicate(QualType T) { 353 T = T.getCanonicalType(); 354 355 if (Loc::isLocType(T)) 356 return true; 357 358 if (T->isIntegerType()) 359 return T->isScalarType(); 360 361 if (T->isRecordType() && !T->isUnionType()) 362 return true; 363 364 return false; 365} 366 367void SymbolManager::addSymbolDependency(const SymbolRef Primary, 368 const SymbolRef Dependent) { 369 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 370 SymbolRefSmallVectorTy *dependencies = 0; 371 if (I == SymbolDependencies.end()) { 372 dependencies = new SymbolRefSmallVectorTy(); 373 SymbolDependencies[Primary] = dependencies; 374 } else { 375 dependencies = I->second; 376 } 377 dependencies->push_back(Dependent); 378} 379 380const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 381 const SymbolRef Primary) { 382 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 383 if (I == SymbolDependencies.end()) 384 return 0; 385 return I->second; 386} 387 388void SymbolReaper::markDependentsLive(SymbolRef sym) { 389 // Do not mark dependents more then once. 390 SymbolMapTy::iterator LI = TheLiving.find(sym); 391 assert(LI != TheLiving.end() && "The primary symbol is not live."); 392 if (LI->second == HaveMarkedDependents) 393 return; 394 LI->second = HaveMarkedDependents; 395 396 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 397 for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 398 E = Deps->end(); I != E; ++I) { 399 if (TheLiving.find(*I) != TheLiving.end()) 400 continue; 401 markLive(*I); 402 } 403 } 404} 405 406void SymbolReaper::markLive(SymbolRef sym) { 407 TheLiving[sym] = NotProcessed; 408 TheDead.erase(sym); 409 markDependentsLive(sym); 410} 411 412void SymbolReaper::markLive(const MemRegion *region) { 413 RegionRoots.insert(region); 414} 415 416void SymbolReaper::markInUse(SymbolRef sym) { 417 if (isa<SymbolMetadata>(sym)) 418 MetadataInUse.insert(sym); 419} 420 421bool SymbolReaper::maybeDead(SymbolRef sym) { 422 if (isLive(sym)) 423 return false; 424 425 TheDead.insert(sym); 426 return true; 427} 428 429bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 430 if (RegionRoots.count(MR)) 431 return true; 432 433 MR = MR->getBaseRegion(); 434 435 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 436 return isLive(SR->getSymbol()); 437 438 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 439 return isLive(VR, true); 440 441 // FIXME: This is a gross over-approximation. What we really need is a way to 442 // tell if anything still refers to this region. Unlike SymbolicRegions, 443 // AllocaRegions don't have associated symbols, though, so we don't actually 444 // have a way to track their liveness. 445 if (isa<AllocaRegion>(MR)) 446 return true; 447 448 if (isa<CXXThisRegion>(MR)) 449 return true; 450 451 if (isa<MemSpaceRegion>(MR)) 452 return true; 453 454 return false; 455} 456 457bool SymbolReaper::isLive(SymbolRef sym) { 458 if (TheLiving.count(sym)) { 459 markDependentsLive(sym); 460 return true; 461 } 462 463 if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { 464 if (isLive(derived->getParentSymbol())) { 465 markLive(sym); 466 return true; 467 } 468 return false; 469 } 470 471 if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { 472 if (isLiveRegion(extent->getRegion())) { 473 markLive(sym); 474 return true; 475 } 476 return false; 477 } 478 479 if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) { 480 if (MetadataInUse.count(sym)) { 481 if (isLiveRegion(metadata->getRegion())) { 482 markLive(sym); 483 MetadataInUse.erase(sym); 484 return true; 485 } 486 } 487 return false; 488 } 489 490 // Interogate the symbol. It may derive from an input value to 491 // the analyzed function/method. 492 return isa<SymbolRegionValue>(sym); 493} 494 495bool 496SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 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 // If no statement is provided, everything is this and parent contexts is live. 505 if (!Loc) 506 return true; 507 508 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 509} 510 511bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 512 const StackFrameContext *VarContext = VR->getStackFrame(); 513 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 514 515 if (VarContext == CurrentContext) { 516 // If no statemetnt is provided, everything is live. 517 if (!Loc) 518 return true; 519 520 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 521 return true; 522 523 if (!includeStoreBindings) 524 return false; 525 526 unsigned &cachedQuery = 527 const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 528 529 if (cachedQuery) { 530 return cachedQuery == 1; 531 } 532 533 // Query the store to see if the region occurs in any live bindings. 534 if (Store store = reapedStore.getStore()) { 535 bool hasRegion = 536 reapedStore.getStoreManager().includedInBindings(store, VR); 537 cachedQuery = hasRegion ? 1 : 2; 538 return hasRegion; 539 } 540 541 return false; 542 } 543 544 return VarContext->isParentOf(CurrentContext); 545} 546 547SymbolVisitor::~SymbolVisitor() {} 548