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(ASTContext&) const { 328 return T; 329} 330 331QualType SymbolDerived::getType(ASTContext &Ctx) const { 332 return R->getValueType(); 333} 334 335QualType SymbolExtent::getType(ASTContext &Ctx) const { 336 return Ctx.getSizeType(); 337} 338 339QualType SymbolMetadata::getType(ASTContext&) const { 340 return T; 341} 342 343QualType SymbolRegionValue::getType(ASTContext &C) const { 344 return R->getValueType(); 345} 346 347SymbolManager::~SymbolManager() { 348 for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 349 E = SymbolDependencies.end(); I != E; ++I) { 350 delete I->second; 351 } 352 353} 354 355bool SymbolManager::canSymbolicate(QualType T) { 356 T = T.getCanonicalType(); 357 358 if (Loc::isLocType(T)) 359 return true; 360 361 if (T->isIntegerType()) 362 return T->isScalarType(); 363 364 if (T->isRecordType() && !T->isUnionType()) 365 return true; 366 367 return false; 368} 369 370void SymbolManager::addSymbolDependency(const SymbolRef Primary, 371 const SymbolRef Dependent) { 372 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 373 SymbolRefSmallVectorTy *dependencies = 0; 374 if (I == SymbolDependencies.end()) { 375 dependencies = new SymbolRefSmallVectorTy(); 376 SymbolDependencies[Primary] = dependencies; 377 } else { 378 dependencies = I->second; 379 } 380 dependencies->push_back(Dependent); 381} 382 383const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 384 const SymbolRef Primary) { 385 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 386 if (I == SymbolDependencies.end()) 387 return 0; 388 return I->second; 389} 390 391void SymbolReaper::markDependentsLive(SymbolRef sym) { 392 // Do not mark dependents more then once. 393 SymbolMapTy::iterator LI = TheLiving.find(sym); 394 assert(LI != TheLiving.end() && "The primary symbol is not live."); 395 if (LI->second == HaveMarkedDependents) 396 return; 397 LI->second = HaveMarkedDependents; 398 399 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 400 for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 401 E = Deps->end(); I != E; ++I) { 402 if (TheLiving.find(*I) != TheLiving.end()) 403 continue; 404 markLive(*I); 405 } 406 } 407} 408 409void SymbolReaper::markLive(SymbolRef sym) { 410 TheLiving[sym] = NotProcessed; 411 TheDead.erase(sym); 412 markDependentsLive(sym); 413} 414 415void SymbolReaper::markLive(const MemRegion *region) { 416 RegionRoots.insert(region); 417} 418 419void SymbolReaper::markInUse(SymbolRef sym) { 420 if (isa<SymbolMetadata>(sym)) 421 MetadataInUse.insert(sym); 422} 423 424bool SymbolReaper::maybeDead(SymbolRef sym) { 425 if (isLive(sym)) 426 return false; 427 428 TheDead.insert(sym); 429 return true; 430} 431 432bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 433 if (RegionRoots.count(MR)) 434 return true; 435 436 MR = MR->getBaseRegion(); 437 438 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 439 return isLive(SR->getSymbol()); 440 441 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 442 return isLive(VR, true); 443 444 // FIXME: This is a gross over-approximation. What we really need is a way to 445 // tell if anything still refers to this region. Unlike SymbolicRegions, 446 // AllocaRegions don't have associated symbols, though, so we don't actually 447 // have a way to track their liveness. 448 if (isa<AllocaRegion>(MR)) 449 return true; 450 451 if (isa<CXXThisRegion>(MR)) 452 return true; 453 454 if (isa<MemSpaceRegion>(MR)) 455 return true; 456 457 return false; 458} 459 460bool SymbolReaper::isLive(SymbolRef sym) { 461 if (TheLiving.count(sym)) { 462 markDependentsLive(sym); 463 return true; 464 } 465 466 if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { 467 if (isLive(derived->getParentSymbol())) { 468 markLive(sym); 469 return true; 470 } 471 return false; 472 } 473 474 if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { 475 if (isLiveRegion(extent->getRegion())) { 476 markLive(sym); 477 return true; 478 } 479 return false; 480 } 481 482 if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) { 483 if (MetadataInUse.count(sym)) { 484 if (isLiveRegion(metadata->getRegion())) { 485 markLive(sym); 486 MetadataInUse.erase(sym); 487 return true; 488 } 489 } 490 return false; 491 } 492 493 // Interogate the symbol. It may derive from an input value to 494 // the analyzed function/method. 495 return isa<SymbolRegionValue>(sym); 496} 497 498bool 499SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 500 if (LCtx != ELCtx) { 501 // If the reaper's location context is a parent of the expression's 502 // location context, then the expression value is now "out of scope". 503 if (LCtx->isParentOf(ELCtx)) 504 return false; 505 return true; 506 } 507 // If no statement is provided, everything is this and parent contexts is live. 508 if (!Loc) 509 return true; 510 511 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 512} 513 514bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 515 const StackFrameContext *VarContext = VR->getStackFrame(); 516 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 517 518 if (VarContext == CurrentContext) { 519 // If no statement is provided, everything is live. 520 if (!Loc) 521 return true; 522 523 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 524 return true; 525 526 if (!includeStoreBindings) 527 return false; 528 529 unsigned &cachedQuery = 530 const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 531 532 if (cachedQuery) { 533 return cachedQuery == 1; 534 } 535 536 // Query the store to see if the region occurs in any live bindings. 537 if (Store store = reapedStore.getStore()) { 538 bool hasRegion = 539 reapedStore.getStoreManager().includedInBindings(store, VR); 540 cachedQuery = hasRegion ? 1 : 2; 541 return hasRegion; 542 } 543 544 return false; 545 } 546 547 return !VarContext || VarContext->isParentOf(CurrentContext); 548} 549 550SymbolVisitor::~SymbolVisitor() {} 551