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