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::dump() const { 25 dumpToStream(llvm::errs()); 26} 27 |
28static 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 |
51void 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 |
60void SymSymExpr::dumpToStream(raw_ostream &os) const { |
61 os << '('; 62 getLHS()->dumpToStream(os); 63 os << ") "; 64 os << '('; 65 getRHS()->dumpToStream(os); 66 os << ')'; 67} 68 |
69void SymbolConjured::dumpToStream(raw_ostream &os) const { |
70 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 71} 72 |
73void SymbolDerived::dumpToStream(raw_ostream &os) const { |
74 os << "derived_$" << getSymbolID() << '{' 75 << getParentSymbol() << ',' << getRegion() << '}'; 76} 77 |
78void SymbolExtent::dumpToStream(raw_ostream &os) const { |
79 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 80} 81 |
82void SymbolMetadata::dumpToStream(raw_ostream &os) const { |
83 os << "meta_$" << getSymbolID() << '{' 84 << getRegion() << ',' << T.getAsString() << '}'; 85} 86 |
87void SymbolRegionValue::dumpToStream(raw_ostream &os) const { |
88 os << "reg_$" << getSymbolID() << "<" << R << ">"; 89} 90 91const SymbolRegionValue* |
92SymbolManager::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 107const SymbolConjured* |
108SymbolManager::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 125const SymbolDerived* 126SymbolManager::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 143const SymbolExtent* 144SymbolManager::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 159const SymbolMetadata* |
160SymbolManager::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 --- 35 unchanged lines hidden (view full) --- 209 210 return cast<SymSymExpr>(data); 211} 212 213QualType SymbolConjured::getType(ASTContext&) const { 214 return T; 215} 216 |
217QualType SymbolDerived::getType(ASTContext &Ctx) const { |
218 return R->getValueType(); 219} 220 |
221QualType SymbolExtent::getType(ASTContext &Ctx) const { |
222 return Ctx.getSizeType(); 223} 224 225QualType SymbolMetadata::getType(ASTContext&) const { 226 return T; 227} 228 |
229QualType SymbolRegionValue::getType(ASTContext &C) const { |
230 return R->getValueType(); 231} 232 |
233SymbolManager::~SymbolManager() { 234 for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(), 235 E = SymbolDependencies.end(); I != E; ++I) { 236 delete I->second; 237 } |
238 |
239} 240 |
241bool 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 |
256void 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 269const 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 277void 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 |
295void SymbolReaper::markLive(SymbolRef sym) { |
296 TheLiving[sym] = NotProcessed; |
297 TheDead.erase(sym); |
298 markDependentsLive(sym); |
299} 300 |
301void SymbolReaper::markLive(const MemRegion *region) { 302 RegionRoots.insert(region); 303} 304 |
305void SymbolReaper::markInUse(SymbolRef sym) { 306 if (isa<SymbolMetadata>(sym)) 307 MetadataInUse.insert(sym); 308} 309 310bool SymbolReaper::maybeDead(SymbolRef sym) { 311 if (isLive(sym)) 312 return false; 313 314 TheDead.insert(sym); 315 return true; 316} 317 |
318bool 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 346bool 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 |
384bool SymbolReaper::isLive(const Stmt *ExprVal) const { 385 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); |
386} 387 |
388bool 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 420SymbolVisitor::~SymbolVisitor() {} |