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