SymbolManager.h revision 218887
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#ifndef LLVM_CLANG_GR_SYMMGR_H 16#define LLVM_CLANG_GR_SYMMGR_H 17 18#include "clang/AST/Decl.h" 19#include "clang/AST/Expr.h" 20#include "clang/Analysis/AnalysisContext.h" 21#include "llvm/Support/DataTypes.h" 22#include "llvm/ADT/FoldingSet.h" 23#include "llvm/ADT/DenseSet.h" 24 25namespace llvm { 26class BumpPtrAllocator; 27class raw_ostream; 28} 29 30namespace clang { 31 class ASTContext; 32 class StackFrameContext; 33 34namespace ento { 35 class BasicValueFactory; 36 class MemRegion; 37 class SubRegion; 38 class TypedRegion; 39 class VarRegion; 40 41class SymExpr : public llvm::FoldingSetNode { 42public: 43 enum Kind { BEGIN_SYMBOLS, 44 RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, 45 MetadataKind, 46 END_SYMBOLS, 47 SymIntKind, SymSymKind }; 48private: 49 Kind K; 50 51protected: 52 SymExpr(Kind k) : K(k) {} 53 54public: 55 virtual ~SymExpr() {} 56 57 Kind getKind() const { return K; } 58 59 void dump() const; 60 61 virtual void dumpToStream(llvm::raw_ostream &os) const = 0; 62 63 virtual QualType getType(ASTContext&) const = 0; 64 virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 65 66 // Implement isa<T> support. 67 static inline bool classof(const SymExpr*) { return true; } 68}; 69 70typedef unsigned SymbolID; 71 72class SymbolData : public SymExpr { 73private: 74 const SymbolID Sym; 75 76protected: 77 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} 78 79public: 80 virtual ~SymbolData() {} 81 82 SymbolID getSymbolID() const { return Sym; } 83 84 // Implement isa<T> support. 85 static inline bool classof(const SymExpr* SE) { 86 Kind k = SE->getKind(); 87 return k > BEGIN_SYMBOLS && k < END_SYMBOLS; 88 } 89}; 90 91typedef const SymbolData* SymbolRef; 92 93// A symbol representing the value of a MemRegion. 94class SymbolRegionValue : public SymbolData { 95 const TypedRegion *R; 96 97public: 98 SymbolRegionValue(SymbolID sym, const TypedRegion *r) 99 : SymbolData(RegionValueKind, sym), R(r) {} 100 101 const TypedRegion* getRegion() const { return R; } 102 103 static void Profile(llvm::FoldingSetNodeID& profile, const TypedRegion* R) { 104 profile.AddInteger((unsigned) RegionValueKind); 105 profile.AddPointer(R); 106 } 107 108 virtual void Profile(llvm::FoldingSetNodeID& profile) { 109 Profile(profile, R); 110 } 111 112 void dumpToStream(llvm::raw_ostream &os) const; 113 114 QualType getType(ASTContext&) const; 115 116 // Implement isa<T> support. 117 static inline bool classof(const SymExpr* SE) { 118 return SE->getKind() == RegionValueKind; 119 } 120}; 121 122// A symbol representing the result of an expression. 123class SymbolConjured : public SymbolData { 124 const Stmt* S; 125 QualType T; 126 unsigned Count; 127 const void* SymbolTag; 128 129public: 130 SymbolConjured(SymbolID sym, const Stmt* s, QualType t, unsigned count, 131 const void* symbolTag) 132 : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 133 SymbolTag(symbolTag) {} 134 135 const Stmt* getStmt() const { return S; } 136 unsigned getCount() const { return Count; } 137 const void* getTag() const { return SymbolTag; } 138 139 QualType getType(ASTContext&) const; 140 141 void dumpToStream(llvm::raw_ostream &os) const; 142 143 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S, 144 QualType T, unsigned Count, const void* SymbolTag) { 145 profile.AddInteger((unsigned) ConjuredKind); 146 profile.AddPointer(S); 147 profile.Add(T); 148 profile.AddInteger(Count); 149 profile.AddPointer(SymbolTag); 150 } 151 152 virtual void Profile(llvm::FoldingSetNodeID& profile) { 153 Profile(profile, S, T, Count, SymbolTag); 154 } 155 156 // Implement isa<T> support. 157 static inline bool classof(const SymExpr* SE) { 158 return SE->getKind() == ConjuredKind; 159 } 160}; 161 162// A symbol representing the value of a MemRegion whose parent region has 163// symbolic value. 164class SymbolDerived : public SymbolData { 165 SymbolRef parentSymbol; 166 const TypedRegion *R; 167 168public: 169 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r) 170 : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 171 172 SymbolRef getParentSymbol() const { return parentSymbol; } 173 const TypedRegion *getRegion() const { return R; } 174 175 QualType getType(ASTContext&) const; 176 177 void dumpToStream(llvm::raw_ostream &os) const; 178 179 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 180 const TypedRegion *r) { 181 profile.AddInteger((unsigned) DerivedKind); 182 profile.AddPointer(r); 183 profile.AddPointer(parent); 184 } 185 186 virtual void Profile(llvm::FoldingSetNodeID& profile) { 187 Profile(profile, parentSymbol, R); 188 } 189 190 // Implement isa<T> support. 191 static inline bool classof(const SymExpr* SE) { 192 return SE->getKind() == DerivedKind; 193 } 194}; 195 196/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 197/// Clients should not ask the SymbolManager for a region's extent. Always use 198/// SubRegion::getExtent instead -- the value returned may not be a symbol. 199class SymbolExtent : public SymbolData { 200 const SubRegion *R; 201 202public: 203 SymbolExtent(SymbolID sym, const SubRegion *r) 204 : SymbolData(ExtentKind, sym), R(r) {} 205 206 const SubRegion *getRegion() const { return R; } 207 208 QualType getType(ASTContext&) const; 209 210 void dumpToStream(llvm::raw_ostream &os) const; 211 212 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 213 profile.AddInteger((unsigned) ExtentKind); 214 profile.AddPointer(R); 215 } 216 217 virtual void Profile(llvm::FoldingSetNodeID& profile) { 218 Profile(profile, R); 219 } 220 221 // Implement isa<T> support. 222 static inline bool classof(const SymExpr* SE) { 223 return SE->getKind() == ExtentKind; 224 } 225}; 226 227/// SymbolMetadata - Represents path-dependent metadata about a specific region. 228/// Metadata symbols remain live as long as they are marked as in use before 229/// dead-symbol sweeping AND their associated regions are still alive. 230/// Intended for use by checkers. 231class SymbolMetadata : public SymbolData { 232 const MemRegion* R; 233 const Stmt* S; 234 QualType T; 235 unsigned Count; 236 const void* Tag; 237public: 238 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t, 239 unsigned count, const void* tag) 240 : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 241 242 const MemRegion *getRegion() const { return R; } 243 const Stmt* getStmt() const { return S; } 244 unsigned getCount() const { return Count; } 245 const void* getTag() const { return Tag; } 246 247 QualType getType(ASTContext&) const; 248 249 void dumpToStream(llvm::raw_ostream &os) const; 250 251 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 252 const Stmt *S, QualType T, unsigned Count, 253 const void *Tag) { 254 profile.AddInteger((unsigned) MetadataKind); 255 profile.AddPointer(R); 256 profile.AddPointer(S); 257 profile.Add(T); 258 profile.AddInteger(Count); 259 profile.AddPointer(Tag); 260 } 261 262 virtual void Profile(llvm::FoldingSetNodeID& profile) { 263 Profile(profile, R, S, T, Count, Tag); 264 } 265 266 // Implement isa<T> support. 267 static inline bool classof(const SymExpr* SE) { 268 return SE->getKind() == MetadataKind; 269 } 270}; 271 272// SymIntExpr - Represents symbolic expression like 'x' + 3. 273class SymIntExpr : public SymExpr { 274 const SymExpr *LHS; 275 BinaryOperator::Opcode Op; 276 const llvm::APSInt& RHS; 277 QualType T; 278 279public: 280 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 281 const llvm::APSInt& rhs, QualType t) 282 : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 283 284 // FIXME: We probably need to make this out-of-line to avoid redundant 285 // generation of virtual functions. 286 QualType getType(ASTContext& C) const { return T; } 287 288 BinaryOperator::Opcode getOpcode() const { return Op; } 289 290 void dumpToStream(llvm::raw_ostream &os) const; 291 292 const SymExpr *getLHS() const { return LHS; } 293 const llvm::APSInt &getRHS() const { return RHS; } 294 295 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 296 BinaryOperator::Opcode op, const llvm::APSInt& rhs, 297 QualType t) { 298 ID.AddInteger((unsigned) SymIntKind); 299 ID.AddPointer(lhs); 300 ID.AddInteger(op); 301 ID.AddPointer(&rhs); 302 ID.Add(t); 303 } 304 305 void Profile(llvm::FoldingSetNodeID& ID) { 306 Profile(ID, LHS, Op, RHS, T); 307 } 308 309 // Implement isa<T> support. 310 static inline bool classof(const SymExpr* SE) { 311 return SE->getKind() == SymIntKind; 312 } 313}; 314 315// SymSymExpr - Represents symbolic expression like 'x' + 'y'. 316class SymSymExpr : public SymExpr { 317 const SymExpr *LHS; 318 BinaryOperator::Opcode Op; 319 const SymExpr *RHS; 320 QualType T; 321 322public: 323 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 324 QualType t) 325 : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 326 327 BinaryOperator::Opcode getOpcode() const { return Op; } 328 const SymExpr *getLHS() const { return LHS; } 329 const SymExpr *getRHS() const { return RHS; } 330 331 // FIXME: We probably need to make this out-of-line to avoid redundant 332 // generation of virtual functions. 333 QualType getType(ASTContext& C) const { return T; } 334 335 void dumpToStream(llvm::raw_ostream &os) const; 336 337 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 338 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 339 ID.AddInteger((unsigned) SymSymKind); 340 ID.AddPointer(lhs); 341 ID.AddInteger(op); 342 ID.AddPointer(rhs); 343 ID.Add(t); 344 } 345 346 void Profile(llvm::FoldingSetNodeID& ID) { 347 Profile(ID, LHS, Op, RHS, T); 348 } 349 350 // Implement isa<T> support. 351 static inline bool classof(const SymExpr* SE) { 352 return SE->getKind() == SymSymKind; 353 } 354}; 355 356class SymbolManager { 357 typedef llvm::FoldingSet<SymExpr> DataSetTy; 358 DataSetTy DataSet; 359 unsigned SymbolCounter; 360 llvm::BumpPtrAllocator& BPAlloc; 361 BasicValueFactory &BV; 362 ASTContext& Ctx; 363 364public: 365 SymbolManager(ASTContext& ctx, BasicValueFactory &bv, 366 llvm::BumpPtrAllocator& bpalloc) 367 : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 368 369 ~SymbolManager(); 370 371 static bool canSymbolicate(QualType T); 372 373 /// Make a unique symbol for MemRegion R according to its kind. 374 const SymbolRegionValue* getRegionValueSymbol(const TypedRegion* R); 375 376 const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, 377 unsigned VisitCount, 378 const void* SymbolTag = 0); 379 380 const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount, 381 const void* SymbolTag = 0) { 382 return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag); 383 } 384 385 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 386 const TypedRegion *R); 387 388 const SymbolExtent *getExtentSymbol(const SubRegion *R); 389 390 const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S, 391 QualType T, unsigned VisitCount, 392 const void* SymbolTag = 0); 393 394 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 395 const llvm::APSInt& rhs, QualType t); 396 397 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 398 const llvm::APSInt& rhs, QualType t) { 399 return getSymIntExpr(&lhs, op, rhs, t); 400 } 401 402 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 403 const SymExpr *rhs, QualType t); 404 405 QualType getType(const SymExpr *SE) const { 406 return SE->getType(Ctx); 407 } 408 409 ASTContext &getContext() { return Ctx; } 410 BasicValueFactory &getBasicVals() { return BV; } 411}; 412 413class SymbolReaper { 414 typedef llvm::DenseSet<SymbolRef> SetTy; 415 416 SetTy TheLiving; 417 SetTy MetadataInUse; 418 SetTy TheDead; 419 const LocationContext *LCtx; 420 const Stmt *Loc; 421 SymbolManager& SymMgr; 422 423public: 424 SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr) 425 : LCtx(ctx), Loc(s), SymMgr(symmgr) {} 426 427 ~SymbolReaper() {} 428 429 const LocationContext *getLocationContext() const { return LCtx; } 430 const Stmt *getCurrentStatement() const { return Loc; } 431 432 bool isLive(SymbolRef sym); 433 bool isLive(const Stmt *ExprVal) const; 434 bool isLive(const VarRegion *VR) const; 435 436 // markLive - Unconditionally marks a symbol as live. This should never be 437 // used by checkers, only by the state infrastructure such as the store and 438 // environment. Checkers should instead use metadata symbols and markInUse. 439 void markLive(SymbolRef sym); 440 441 // markInUse - Marks a symbol as important to a checker. For metadata symbols, 442 // this will keep the symbol alive as long as its associated region is also 443 // live. For other symbols, this has no effect; checkers are not permitted 444 // to influence the life of other symbols. This should be used before any 445 // symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 446 void markInUse(SymbolRef sym); 447 448 // maybeDead - If a symbol is known to be live, marks the symbol as live. 449 // Otherwise, if the symbol cannot be proven live, it is marked as dead. 450 // Returns true if the symbol is dead, false if live. 451 bool maybeDead(SymbolRef sym); 452 453 typedef SetTy::const_iterator dead_iterator; 454 dead_iterator dead_begin() const { return TheDead.begin(); } 455 dead_iterator dead_end() const { return TheDead.end(); } 456 457 bool hasDeadSymbols() const { 458 return !TheDead.empty(); 459 } 460 461 /// isDead - Returns whether or not a symbol has been confirmed dead. This 462 /// should only be called once all marking of dead symbols has completed. 463 /// (For checkers, this means only in the evalDeadSymbols callback.) 464 bool isDead(SymbolRef sym) const { 465 return TheDead.count(sym); 466 } 467}; 468 469class SymbolVisitor { 470public: 471 // VisitSymbol - A visitor method invoked by 472 // GRStateManager::scanReachableSymbols. The method returns \c true if 473 // symbols should continue be scanned and \c false otherwise. 474 virtual bool VisitSymbol(SymbolRef sym) = 0; 475 virtual ~SymbolVisitor(); 476}; 477 478} // end GR namespace 479 480} // end clang namespace 481 482namespace llvm { 483static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, 484 const clang::ento::SymExpr *SE) { 485 SE->dumpToStream(os); 486 return os; 487} 488} // end llvm namespace 489#endif 490