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 "llvm/Support/raw_ostream.h" 19 20 using namespace clang; 21 using namespace ento; 22 23 void SymExpr::dump() const { 24 dumpToStream(llvm::errs()); 25 } 26 27 static void print(llvm::raw_ostream& os, BinaryOperator::Opcode Op) { 28 switch (Op) { 29 default: 30 assert(false && "operator printing not implemented"); 31 break; 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(llvm::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(llvm::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(llvm::raw_ostream& os) const { 70 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; 71 } 72 73 void SymbolDerived::dumpToStream(llvm::raw_ostream& os) const { 74 os << "derived_$" << getSymbolID() << '{' 75 << getParentSymbol() << ',' << getRegion() << '}'; 76 } 77 78 void SymbolExtent::dumpToStream(llvm::raw_ostream& os) const { 79 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 80 } 81 82 void SymbolMetadata::dumpToStream(llvm::raw_ostream& os) const { 83 os << "meta_$" << getSymbolID() << '{' 84 << getRegion() << ',' << T.getAsString() << '}'; 85 } 86 87 void SymbolRegionValue::dumpToStream(llvm::raw_ostream& os) const { 88 os << "reg_$" << getSymbolID() << "<" << R << ">"; 89 } 90 91 const SymbolRegionValue* 92 SymbolManager::getRegionValueSymbol(const TypedRegion* 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 TypedRegion *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 235 bool SymbolManager::canSymbolicate(QualType T) { 236 T = T.getCanonicalType(); 237 238 if (Loc::isLocType(T)) 239 return true; 240 241 if (T->isIntegerType()) 242 return T->isScalarType(); 243 244 if (T->isRecordType() && !T->isUnionType()) 245 return true; 246 247 return false; 248 } 249 250 void SymbolReaper::markLive(SymbolRef sym) { 251 TheLiving.insert(sym); 252 TheDead.erase(sym); 253 } 254 255 void SymbolReaper::markInUse(SymbolRef sym) { 256 if (isa<SymbolMetadata>(sym)) 257 MetadataInUse.insert(sym); 258 } 259 260 bool SymbolReaper::maybeDead(SymbolRef sym) { 261 if (isLive(sym)) 262 return false; 263 264 TheDead.insert(sym); 265 return true; 266 } 267 268 static bool IsLiveRegion(SymbolReaper &Reaper, const MemRegion *MR) { 269 MR = MR->getBaseRegion(); 270 271 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 272 return Reaper.isLive(SR->getSymbol()); 273 274 if (const VarRegion *VR = dyn_cast<VarRegion>(MR)) 275 return Reaper.isLive(VR); 276 277 // FIXME: This is a gross over-approximation. What we really need is a way to 278 // tell if anything still refers to this region. Unlike SymbolicRegions, 279 // AllocaRegions don't have associated symbols, though, so we don't actually 280 // have a way to track their liveness. 281 if (isa<AllocaRegion>(MR)) 282 return true; 283 284 if (isa<CXXThisRegion>(MR)) 285 return true; 286 287 if (isa<MemSpaceRegion>(MR)) 288 return true; 289 290 return false; 291 } 292 293 bool SymbolReaper::isLive(SymbolRef sym) { 294 if (TheLiving.count(sym)) 295 return true; 296 297 if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { 298 if (isLive(derived->getParentSymbol())) { 299 markLive(sym); 300 return true; 301 } 302 return false; 303 } 304 305 if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { 306 if (IsLiveRegion(*this, extent->getRegion())) { 307 markLive(sym); 308 return true; 309 } 310 return false; 311 } 312 313 if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) { 314 if (MetadataInUse.count(sym)) { 315 if (IsLiveRegion(*this, metadata->getRegion())) { 316 markLive(sym); 317 MetadataInUse.erase(sym); 318 return true; 319 } 320 } 321 return false; 322 } 323 324 // Interogate the symbol. It may derive from an input value to 325 // the analyzed function/method. 326 return isa<SymbolRegionValue>(sym); 327 } 328 329 bool SymbolReaper::isLive(const Stmt* ExprVal) const { 330 return LCtx->getAnalysisContext()->getRelaxedLiveVariables()-> 331 isLive(Loc, ExprVal); 332 } 333 334 bool SymbolReaper::isLive(const VarRegion *VR) const { 335 const StackFrameContext *VarContext = VR->getStackFrame(); 336 const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); 337 338 if (VarContext == CurrentContext) 339 return LCtx->getAnalysisContext()->getRelaxedLiveVariables()-> 340 isLive(Loc, VR->getDecl()); 341 342 return VarContext->isParentOf(CurrentContext); 343 } 344 345 SymbolVisitor::~SymbolVisitor() {} 346
