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 21 using namespace clang; 22 using namespace ento; 23 24 void SymExpr::anchor() { } 25 26 void SymExpr::dump() const { 27 dumpToStream(llvm::errs()); 28 } 29 30 void 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 40 void 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 51 void 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 61 void SymbolCast::dumpToStream(raw_ostream &os) const { 62 os << '(' << ToTy.getAsString() << ") ("; 63 Operand->dumpToStream(os); 64 os << ')'; 65 } 66 67 void SymbolConjured::dumpToStream(raw_ostream &os) const { 68 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 69 } 70 71 void SymbolDerived::dumpToStream(raw_ostream &os) const { 72 os << "derived_$" << getSymbolID() << '{' 73 << getParentSymbol() << ',' << getRegion() << '}'; 74 } 75 76 void SymbolExtent::dumpToStream(raw_ostream &os) const { 77 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 78 } 79 80 void SymbolMetadata::dumpToStream(raw_ostream &os) const { 81 os << "meta_$" << getSymbolID() << '{' 82 << getRegion() << ',' << T.getAsString() << '}'; 83 } 84 85 void SymbolData::anchor() { } 86 87 void SymbolRegionValue::dumpToStream(raw_ostream &os) const { 88 os << "reg_$" << getSymbolID() << "<" << R << ">"; 89 } 90 91 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 92 return itr == X.itr; 93 } 94 95 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 96 return itr != X.itr; 97 } 98 99 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 100 itr.push_back(SE); 101 } 102 103 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 104 assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 105 expand(); 106 return *this; 107 } 108 109 SymbolRef SymExpr::symbol_iterator::operator*() { 110 assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 111 return itr.back(); 112 } 113 114 void 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 143 unsigned 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 150 const SymbolRegionValue* 151 SymbolManager::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 166 const 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 185 const SymbolDerived* 186 SymbolManager::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 203 const SymbolExtent* 204 SymbolManager::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 219 const SymbolMetadata* 220 SymbolManager::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 237 const SymbolCast* 238 SymbolManager::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 253 const 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 271 const 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 289 const 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 307 QualType SymbolConjured::getType() const { 308 return T; 309 } 310 311 QualType SymbolDerived::getType() const { 312 return R->getValueType(); 313 } 314 315 QualType SymbolExtent::getType() const { 316 ASTContext &Ctx = R->getMemRegionManager()->getContext(); 317 return Ctx.getSizeType(); 318 } 319 320 QualType SymbolMetadata::getType() const { 321 return T; 322 } 323 324 QualType SymbolRegionValue::getType() const { 325 return R->getValueType(); 326 } 327 328 SymbolManager::~SymbolManager() { 329 llvm::DeleteContainerSeconds(SymbolDependencies); 330 } 331 332 bool SymbolManager::canSymbolicate(QualType T) { 333 T = T.getCanonicalType(); 334 335 if (Loc::isLocType(T)) 336 return true; 337 338 if (T->isIntegralOrEnumerationType()) 339 return true; 340 341 if (T->isRecordType() && !T->isUnionType()) 342 return true; 343 344 return false; 345 } 346 347 void SymbolManager::addSymbolDependency(const SymbolRef Primary, 348 const SymbolRef Dependent) { 349 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 350 SymbolRefSmallVectorTy *dependencies = nullptr; 351 if (I == SymbolDependencies.end()) { 352 dependencies = new SymbolRefSmallVectorTy(); 353 SymbolDependencies[Primary] = dependencies; 354 } else { 355 dependencies = I->second; 356 } 357 dependencies->push_back(Dependent); 358 } 359 360 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 361 const SymbolRef Primary) { 362 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 363 if (I == SymbolDependencies.end()) 364 return nullptr; 365 return I->second; 366 } 367 368 void SymbolReaper::markDependentsLive(SymbolRef sym) { 369 // Do not mark dependents more then once. 370 SymbolMapTy::iterator LI = TheLiving.find(sym); 371 assert(LI != TheLiving.end() && "The primary symbol is not live."); 372 if (LI->second == HaveMarkedDependents) 373 return; 374 LI->second = HaveMarkedDependents; 375 376 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 377 for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 378 E = Deps->end(); I != E; ++I) { 379 if (TheLiving.find(*I) != TheLiving.end()) 380 continue; 381 markLive(*I); 382 } 383 } 384 } 385 386 void SymbolReaper::markLive(SymbolRef sym) { 387 TheLiving[sym] = NotProcessed; 388 TheDead.erase(sym); 389 markDependentsLive(sym); 390 } 391 392 void SymbolReaper::markLive(const MemRegion *region) { 393 RegionRoots.insert(region); 394 } 395 396 void SymbolReaper::markInUse(SymbolRef sym) { 397 if (isa<SymbolMetadata>(sym)) 398 MetadataInUse.insert(sym); 399 } 400 401 bool SymbolReaper::maybeDead(SymbolRef sym) { 402 if (isLive(sym)) 403 return false; 404 405 TheDead.insert(sym); 406 return true; 407 } 408 409 bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 410 if (RegionRoots.count(MR)) 411 return true; 412 413 MR = MR->getBaseRegion(); 414 415 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 416 return isLive(SR->getSymbol()); 417 418 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 419 return isLive(VR, true); 420 421 // FIXME: This is a gross over-approximation. What we really need is a way to 422 // tell if anything still refers to this region. Unlike SymbolicRegions, 423 // AllocaRegions don't have associated symbols, though, so we don't actually 424 // have a way to track their liveness. 425 if (isa<AllocaRegion>(MR)) 426 return true; 427 428 if (isa<CXXThisRegion>(MR)) 429 return true; 430 431 if (isa<MemSpaceRegion>(MR)) 432 return true; 433 434 if (isa<CodeTextRegion>(MR)) 435 return true; 436 437 return false; 438 } 439 440 bool SymbolReaper::isLive(SymbolRef sym) { 441 if (TheLiving.count(sym)) { 442 markDependentsLive(sym); 443 return true; 444 } 445 446 bool KnownLive; 447 448 switch (sym->getKind()) { 449 case SymExpr::RegionValueKind: 450 KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion()); 451 break; 452 case SymExpr::ConjuredKind: 453 KnownLive = false; 454 break; 455 case SymExpr::DerivedKind: 456 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 457 break; 458 case SymExpr::ExtentKind: 459 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 460 break; 461 case SymExpr::MetadataKind: 462 KnownLive = MetadataInUse.count(sym) && 463 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 464 if (KnownLive) 465 MetadataInUse.erase(sym); 466 break; 467 case SymExpr::SymIntKind: 468 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 469 break; 470 case SymExpr::IntSymKind: 471 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 472 break; 473 case SymExpr::SymSymKind: 474 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 475 isLive(cast<SymSymExpr>(sym)->getRHS()); 476 break; 477 case SymExpr::CastSymbolKind: 478 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 479 break; 480 } 481 482 if (KnownLive) 483 markLive(sym); 484 485 return KnownLive; 486 } 487 488 bool 489 SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 490 if (LCtx == nullptr) 491 return false; 492 493 if (LCtx != ELCtx) { 494 // If the reaper's location context is a parent of the expression's 495 // location context, then the expression value is now "out of scope". 496 if (LCtx->isParentOf(ELCtx)) 497 return false; 498 return true; 499 } 500 501 // If no statement is provided, everything is this and parent contexts is live. 502 if (!Loc) 503 return true; 504 505 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 506 } 507 508 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 509 const StackFrameContext *VarContext = VR->getStackFrame(); 510 511 if (!VarContext) 512 return true; 513 514 if (!LCtx) 515 return false; 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->isParentOf(CurrentContext); 548 } 549 550 SymbolVisitor::~SymbolVisitor() {} 551