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::dump() const { 25 dumpToStream(llvm::errs()); 26 } 27 28 static void print(raw_ostream &os, BinaryOperator::Opcode Op) { 29 switch (Op) { 30 default: 31 llvm_unreachable("operator printing not implemented"); 32 case BO_Mul: os << '*' ; break; 33 case BO_Div: os << '/' ; break; 34 case BO_Rem: os << '%' ; break; 35 case BO_Add: os << '+' ; break; 36 case BO_Sub: os << '-' ; break; 37 case BO_Shl: os << "<<" ; break; 38 case BO_Shr: os << ">>" ; break; 39 case BO_LT: os << "<" ; break; 40 case BO_GT: os << '>' ; break; 41 case BO_LE: os << "<=" ; break; 42 case BO_GE: os << ">=" ; break; 43 case BO_EQ: os << "==" ; break; 44 case BO_NE: os << "!=" ; break; 45 case BO_And: os << '&' ; break; 46 case BO_Xor: os << '^' ; break; 47 case BO_Or: os << '|' ; break; 48 } 49 } 50 51 void SymIntExpr::dumpToStream(raw_ostream &os) const { 52 os << '('; 53 getLHS()->dumpToStream(os); 54 os << ") "; 55 print(os, getOpcode()); 56 os << ' ' << getRHS().getZExtValue(); 57 if (getRHS().isUnsigned()) os << 'U'; 58 } 59 60 void SymSymExpr::dumpToStream(raw_ostream &os) const { 61 os << '('; 62 getLHS()->dumpToStream(os); 63 os << ") "; 64 os << '('; 65 getRHS()->dumpToStream(os); 66 os << ')'; 67 } 68 69 void SymbolConjured::dumpToStream(raw_ostream &os) const { 70 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 71 } 72 73 void SymbolDerived::dumpToStream(raw_ostream &os) const { 74 os << "derived_$" << getSymbolID() << '{' 75 << getParentSymbol() << ',' << getRegion() << '}'; 76 } 77 78 void SymbolExtent::dumpToStream(raw_ostream &os) const { 79 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 80 } 81 82 void SymbolMetadata::dumpToStream(raw_ostream &os) const { 83 os << "meta_$" << getSymbolID() << '{' 84 << getRegion() << ',' << T.getAsString() << '}'; 85 } 86 87 void SymbolRegionValue::dumpToStream(raw_ostream &os) const { 88 os << "reg_$" << getSymbolID() << "<" << R << ">"; 89 } 90 91 const SymbolRegionValue* 92 SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 93 llvm::FoldingSetNodeID profile; 94 SymbolRegionValue::Profile(profile, R); 95 void *InsertPos; 96 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 97 if (!SD) { 98 SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 99 new (SD) SymbolRegionValue(SymbolCounter, R); 100 DataSet.InsertNode(SD, InsertPos); 101 ++SymbolCounter; 102 } 103 104 return cast<SymbolRegionValue>(SD); 105 } 106 107 const SymbolConjured* 108 SymbolManager::getConjuredSymbol(const Stmt *E, QualType T, unsigned Count, 109 const void *SymbolTag) { 110 111 llvm::FoldingSetNodeID profile; 112 SymbolConjured::Profile(profile, E, T, Count, SymbolTag); 113 void *InsertPos; 114 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 115 if (!SD) { 116 SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 117 new (SD) SymbolConjured(SymbolCounter, E, T, Count, SymbolTag); 118 DataSet.InsertNode(SD, InsertPos); 119 ++SymbolCounter; 120 } 121 122 return cast<SymbolConjured>(SD); 123 } 124 125 const SymbolDerived* 126 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 127 const TypedValueRegion *R) { 128 129 llvm::FoldingSetNodeID profile; 130 SymbolDerived::Profile(profile, parentSymbol, R); 131 void *InsertPos; 132 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 133 if (!SD) { 134 SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 135 new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 136 DataSet.InsertNode(SD, InsertPos); 137 ++SymbolCounter; 138 } 139 140 return cast<SymbolDerived>(SD); 141 } 142 143 const SymbolExtent* 144 SymbolManager::getExtentSymbol(const SubRegion *R) { 145 llvm::FoldingSetNodeID profile; 146 SymbolExtent::Profile(profile, R); 147 void *InsertPos; 148 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 149 if (!SD) { 150 SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 151 new (SD) SymbolExtent(SymbolCounter, R); 152 DataSet.InsertNode(SD, InsertPos); 153 ++SymbolCounter; 154 } 155 156 return cast<SymbolExtent>(SD); 157 } 158 159 const SymbolMetadata* 160 SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 161 unsigned Count, const void *SymbolTag) { 162 163 llvm::FoldingSetNodeID profile; 164 SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag); 165 void *InsertPos; 166 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 167 if (!SD) { 168 SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 169 new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag); 170 DataSet.InsertNode(SD, InsertPos); 171 ++SymbolCounter; 172 } 173 174 return cast<SymbolMetadata>(SD); 175 } 176 177 const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 178 BinaryOperator::Opcode op, 179 const llvm::APSInt& v, 180 QualType t) { 181 llvm::FoldingSetNodeID ID; 182 SymIntExpr::Profile(ID, lhs, op, v, t); 183 void *InsertPos; 184 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 185 186 if (!data) { 187 data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 188 new (data) SymIntExpr(lhs, op, v, t); 189 DataSet.InsertNode(data, InsertPos); 190 } 191 192 return cast<SymIntExpr>(data); 193 } 194 195 const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 196 BinaryOperator::Opcode op, 197 const SymExpr *rhs, 198 QualType t) { 199 llvm::FoldingSetNodeID ID; 200 SymSymExpr::Profile(ID, lhs, op, rhs, t); 201 void *InsertPos; 202 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 203 204 if (!data) { 205 data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 206 new (data) SymSymExpr(lhs, op, rhs, t); 207 DataSet.InsertNode(data, InsertPos); 208 } 209 210 return cast<SymSymExpr>(data); 211 } 212 213 QualType SymbolConjured::getType(ASTContext&) const { 214 return T; 215 } 216 217 QualType SymbolDerived::getType(ASTContext &Ctx) const { 218 return R->getValueType(); 219 } 220 221 QualType SymbolExtent::getType(ASTContext &Ctx) const { 222 return Ctx.getSizeType(); 223 } 224 225 QualType SymbolMetadata::getType(ASTContext&) const { 226 return T; 227 } 228 229 QualType SymbolRegionValue::getType(ASTContext &C) const { 230 return R->getValueType(); 231 } 232 233 SymbolManager::~SymbolManager() { 234 for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 235 E = SymbolDependencies.end(); I != E; ++I) { 236 delete I->second; 237 } 238 239 } 240 241 bool SymbolManager::canSymbolicate(QualType T) { 242 T = T.getCanonicalType(); 243 244 if (Loc::isLocType(T)) 245 return true; 246 247 if (T->isIntegerType()) 248 return T->isScalarType(); 249 250 if (T->isRecordType() && !T->isUnionType()) 251 return true; 252 253 return false; 254 } 255 256 void SymbolManager::addSymbolDependency(const SymbolRef Primary, 257 const SymbolRef Dependent) { 258 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 259 SymbolRefSmallVectorTy *dependencies = 0; 260 if (I == SymbolDependencies.end()) { 261 dependencies = new SymbolRefSmallVectorTy(); 262 SymbolDependencies[Primary] = dependencies; 263 } else { 264 dependencies = I->second; 265 } 266 dependencies->push_back(Dependent); 267 } 268 269 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 270 const SymbolRef Primary) { 271 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 272 if (I == SymbolDependencies.end()) 273 return 0; 274 return I->second; 275 } 276 277 void SymbolReaper::markDependentsLive(SymbolRef sym) { 278 // Do not mark dependents more then once. 279 SymbolMapTy::iterator LI = TheLiving.find(sym); 280 assert(LI != TheLiving.end() && "The primary symbol is not live."); 281 if (LI->second == HaveMarkedDependents) 282 return; 283 LI->second = HaveMarkedDependents; 284 285 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 286 for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(), 287 E = Deps->end(); I != E; ++I) { 288 if (TheLiving.find(*I) != TheLiving.end()) 289 continue; 290 markLive(*I); 291 } 292 } 293 } 294 295 void SymbolReaper::markLive(SymbolRef sym) { 296 TheLiving[sym] = NotProcessed; 297 TheDead.erase(sym); 298 markDependentsLive(sym); 299 } 300 301 void SymbolReaper::markLive(const MemRegion *region) { 302 RegionRoots.insert(region); 303 } 304 305 void SymbolReaper::markInUse(SymbolRef sym) { 306 if (isa<SymbolMetadata>(sym)) 307 MetadataInUse.insert(sym); 308 } 309 310 bool SymbolReaper::maybeDead(SymbolRef sym) { 311 if (isLive(sym)) 312 return false; 313 314 TheDead.insert(sym); 315 return true; 316 } 317 318 bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 319 if (RegionRoots.count(MR)) 320 return true; 321 322 MR = MR->getBaseRegion(); 323 324 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 325 return isLive(SR->getSymbol()); 326 327 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 328 return isLive(VR, true); 329 330 // FIXME: This is a gross over-approximation. What we really need is a way to 331 // tell if anything still refers to this region. Unlike SymbolicRegions, 332 // AllocaRegions don't have associated symbols, though, so we don't actually 333 // have a way to track their liveness. 334 if (isa<AllocaRegion>(MR)) 335 return true; 336 337 if (isa<CXXThisRegion>(MR)) 338 return true; 339 340 if (isa<MemSpaceRegion>(MR)) 341 return true; 342 343 return false; 344 } 345 346 bool SymbolReaper::isLive(SymbolRef sym) { 347 if (TheLiving.count(sym)) { 348 markDependentsLive(sym); 349 return true; 350 } 351 352 if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { 353 if (isLive(derived->getParentSymbol())) { 354 markLive(sym); 355 return true; 356 } 357 return false; 358 } 359 360 if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { 361 if (isLiveRegion(extent->getRegion())) { 362 markLive(sym); 363 return true; 364 } 365 return false; 366 } 367 368 if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) { 369 if (MetadataInUse.count(sym)) { 370 if (isLiveRegion(metadata->getRegion())) { 371 markLive(sym); 372 MetadataInUse.erase(sym); 373 return true; 374 } 375 } 376 return false; 377 } 378 379 // Interogate the symbol. It may derive from an input value to 380 // the analyzed function/method. 381 return isa<SymbolRegionValue>(sym); 382 } 383 384 bool SymbolReaper::isLive(const Stmt *ExprVal) const { 385 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 386 } 387 388 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 389 const StackFrameContext *VarContext = VR->getStackFrame(); 390 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 391 392 if (VarContext == CurrentContext) { 393 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 394 return true; 395 396 if (!includeStoreBindings) 397 return false; 398 399 unsigned &cachedQuery = 400 const_cast<SymbolReaper*>(this)->includedRegionCache[VR]; 401 402 if (cachedQuery) { 403 return cachedQuery == 1; 404 } 405 406 // Query the store to see if the region occurs in any live bindings. 407 if (Store store = reapedStore.getStore()) { 408 bool hasRegion = 409 reapedStore.getStoreManager().includedInBindings(store, VR); 410 cachedQuery = hasRegion ? 1 : 2; 411 return hasRegion; 412 } 413 414 return false; 415 } 416 417 return VarContext->isParentOf(CurrentContext); 418 } 419 420 SymbolVisitor::~SymbolVisitor() {} 421