SymbolManager.h revision 314564
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_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 16#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_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/MemRegion.h" 23#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 24#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/DenseSet.h" 27#include "llvm/ADT/FoldingSet.h" 28#include "llvm/Support/Allocator.h" 29#include "llvm/Support/DataTypes.h" 30 31namespace clang { 32 class ASTContext; 33 class StackFrameContext; 34 35namespace ento { 36 class BasicValueFactory; 37 class SubRegion; 38 class TypedValueRegion; 39 class VarRegion; 40 41///\brief A symbol representing the value stored at a MemRegion. 42class SymbolRegionValue : public SymbolData { 43 const TypedValueRegion *R; 44 45public: 46 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 47 : SymbolData(SymbolRegionValueKind, sym), R(r) {} 48 49 const TypedValueRegion* getRegion() const { return R; } 50 51 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 52 profile.AddInteger((unsigned) SymbolRegionValueKind); 53 profile.AddPointer(R); 54 } 55 56 void Profile(llvm::FoldingSetNodeID& profile) override { 57 Profile(profile, R); 58 } 59 60 void dumpToStream(raw_ostream &os) const override; 61 const MemRegion *getOriginRegion() const override { return getRegion(); } 62 63 QualType getType() const override; 64 65 // Implement isa<T> support. 66 static inline bool classof(const SymExpr *SE) { 67 return SE->getKind() == SymbolRegionValueKind; 68 } 69}; 70 71/// A symbol representing the result of an expression in the case when we do 72/// not know anything about what the expression is. 73class SymbolConjured : public SymbolData { 74 const Stmt *S; 75 QualType T; 76 unsigned Count; 77 const LocationContext *LCtx; 78 const void *SymbolTag; 79 80public: 81 SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 82 QualType t, unsigned count, const void *symbolTag) 83 : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count), 84 LCtx(lctx), SymbolTag(symbolTag) {} 85 86 const Stmt *getStmt() const { return S; } 87 unsigned getCount() const { return Count; } 88 const void *getTag() const { return SymbolTag; } 89 90 QualType getType() const override; 91 92 void dumpToStream(raw_ostream &os) const override; 93 94 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 95 QualType T, unsigned Count, const LocationContext *LCtx, 96 const void *SymbolTag) { 97 profile.AddInteger((unsigned) SymbolConjuredKind); 98 profile.AddPointer(S); 99 profile.AddPointer(LCtx); 100 profile.Add(T); 101 profile.AddInteger(Count); 102 profile.AddPointer(SymbolTag); 103 } 104 105 void Profile(llvm::FoldingSetNodeID& profile) override { 106 Profile(profile, S, T, Count, LCtx, SymbolTag); 107 } 108 109 // Implement isa<T> support. 110 static inline bool classof(const SymExpr *SE) { 111 return SE->getKind() == SymbolConjuredKind; 112 } 113}; 114 115/// A symbol representing the value of a MemRegion whose parent region has 116/// symbolic value. 117class SymbolDerived : public SymbolData { 118 SymbolRef parentSymbol; 119 const TypedValueRegion *R; 120 121public: 122 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 123 : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {} 124 125 SymbolRef getParentSymbol() const { return parentSymbol; } 126 const TypedValueRegion *getRegion() const { return R; } 127 128 QualType getType() const override; 129 130 void dumpToStream(raw_ostream &os) const override; 131 const MemRegion *getOriginRegion() const override { return getRegion(); } 132 133 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 134 const TypedValueRegion *r) { 135 profile.AddInteger((unsigned) SymbolDerivedKind); 136 profile.AddPointer(r); 137 profile.AddPointer(parent); 138 } 139 140 void Profile(llvm::FoldingSetNodeID& profile) override { 141 Profile(profile, parentSymbol, R); 142 } 143 144 // Implement isa<T> support. 145 static inline bool classof(const SymExpr *SE) { 146 return SE->getKind() == SymbolDerivedKind; 147 } 148}; 149 150/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 151/// Clients should not ask the SymbolManager for a region's extent. Always use 152/// SubRegion::getExtent instead -- the value returned may not be a symbol. 153class SymbolExtent : public SymbolData { 154 const SubRegion *R; 155 156public: 157 SymbolExtent(SymbolID sym, const SubRegion *r) 158 : SymbolData(SymbolExtentKind, sym), R(r) {} 159 160 const SubRegion *getRegion() const { return R; } 161 162 QualType getType() const override; 163 164 void dumpToStream(raw_ostream &os) const override; 165 166 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 167 profile.AddInteger((unsigned) SymbolExtentKind); 168 profile.AddPointer(R); 169 } 170 171 void Profile(llvm::FoldingSetNodeID& profile) override { 172 Profile(profile, R); 173 } 174 175 // Implement isa<T> support. 176 static inline bool classof(const SymExpr *SE) { 177 return SE->getKind() == SymbolExtentKind; 178 } 179}; 180 181/// SymbolMetadata - Represents path-dependent metadata about a specific region. 182/// Metadata symbols remain live as long as they are marked as in use before 183/// dead-symbol sweeping AND their associated regions are still alive. 184/// Intended for use by checkers. 185class SymbolMetadata : public SymbolData { 186 const MemRegion* R; 187 const Stmt *S; 188 QualType T; 189 const LocationContext *LCtx; 190 unsigned Count; 191 const void *Tag; 192public: 193 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 194 const LocationContext *LCtx, unsigned count, const void *tag) 195 : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx), 196 Count(count), Tag(tag) {} 197 198 const MemRegion *getRegion() const { return R; } 199 const Stmt *getStmt() const { return S; } 200 const LocationContext *getLocationContext() const { return LCtx; } 201 unsigned getCount() const { return Count; } 202 const void *getTag() const { return Tag; } 203 204 QualType getType() const override; 205 206 void dumpToStream(raw_ostream &os) const override; 207 208 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 209 const Stmt *S, QualType T, const LocationContext *LCtx, 210 unsigned Count, const void *Tag) { 211 profile.AddInteger((unsigned) SymbolMetadataKind); 212 profile.AddPointer(R); 213 profile.AddPointer(S); 214 profile.Add(T); 215 profile.AddPointer(LCtx); 216 profile.AddInteger(Count); 217 profile.AddPointer(Tag); 218 } 219 220 void Profile(llvm::FoldingSetNodeID& profile) override { 221 Profile(profile, R, S, T, LCtx, Count, Tag); 222 } 223 224 // Implement isa<T> support. 225 static inline bool classof(const SymExpr *SE) { 226 return SE->getKind() == SymbolMetadataKind; 227 } 228}; 229 230/// \brief Represents a cast expression. 231class SymbolCast : public SymExpr { 232 const SymExpr *Operand; 233 /// Type of the operand. 234 QualType FromTy; 235 /// The type of the result. 236 QualType ToTy; 237 238public: 239 SymbolCast(const SymExpr *In, QualType From, QualType To) : 240 SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { } 241 242 QualType getType() const override { return ToTy; } 243 244 const SymExpr *getOperand() const { return Operand; } 245 246 void dumpToStream(raw_ostream &os) const override; 247 248 static void Profile(llvm::FoldingSetNodeID& ID, 249 const SymExpr *In, QualType From, QualType To) { 250 ID.AddInteger((unsigned) SymbolCastKind); 251 ID.AddPointer(In); 252 ID.Add(From); 253 ID.Add(To); 254 } 255 256 void Profile(llvm::FoldingSetNodeID& ID) override { 257 Profile(ID, Operand, FromTy, ToTy); 258 } 259 260 // Implement isa<T> support. 261 static inline bool classof(const SymExpr *SE) { 262 return SE->getKind() == SymbolCastKind; 263 } 264}; 265 266/// \brief Represents a symbolic expression involving a binary operator 267class BinarySymExpr : public SymExpr { 268 BinaryOperator::Opcode Op; 269 QualType T; 270 271protected: 272 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 273 : SymExpr(k), Op(op), T(t) {} 274 275public: 276 // FIXME: We probably need to make this out-of-line to avoid redundant 277 // generation of virtual functions. 278 QualType getType() const override { return T; } 279 280 BinaryOperator::Opcode getOpcode() const { return Op; } 281 282 // Implement isa<T> support. 283 static inline bool classof(const SymExpr *SE) { 284 Kind k = SE->getKind(); 285 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 286 } 287}; 288 289/// \brief Represents a symbolic expression like 'x' + 3. 290class SymIntExpr : public BinarySymExpr { 291 const SymExpr *LHS; 292 const llvm::APSInt& RHS; 293 294public: 295 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 296 const llvm::APSInt& rhs, QualType t) 297 : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {} 298 299 void dumpToStream(raw_ostream &os) const override; 300 301 const SymExpr *getLHS() const { return LHS; } 302 const llvm::APSInt &getRHS() const { return RHS; } 303 304 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 305 BinaryOperator::Opcode op, const llvm::APSInt& rhs, 306 QualType t) { 307 ID.AddInteger((unsigned) SymIntExprKind); 308 ID.AddPointer(lhs); 309 ID.AddInteger(op); 310 ID.AddPointer(&rhs); 311 ID.Add(t); 312 } 313 314 void Profile(llvm::FoldingSetNodeID& ID) override { 315 Profile(ID, LHS, getOpcode(), RHS, getType()); 316 } 317 318 // Implement isa<T> support. 319 static inline bool classof(const SymExpr *SE) { 320 return SE->getKind() == SymIntExprKind; 321 } 322}; 323 324/// \brief Represents a symbolic expression like 3 - 'x'. 325class IntSymExpr : public BinarySymExpr { 326 const llvm::APSInt& LHS; 327 const SymExpr *RHS; 328 329public: 330 IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 331 const SymExpr *rhs, QualType t) 332 : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {} 333 334 void dumpToStream(raw_ostream &os) const override; 335 336 const SymExpr *getRHS() const { return RHS; } 337 const llvm::APSInt &getLHS() const { return LHS; } 338 339 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 340 BinaryOperator::Opcode op, const SymExpr *rhs, 341 QualType t) { 342 ID.AddInteger((unsigned) IntSymExprKind); 343 ID.AddPointer(&lhs); 344 ID.AddInteger(op); 345 ID.AddPointer(rhs); 346 ID.Add(t); 347 } 348 349 void Profile(llvm::FoldingSetNodeID& ID) override { 350 Profile(ID, LHS, getOpcode(), RHS, getType()); 351 } 352 353 // Implement isa<T> support. 354 static inline bool classof(const SymExpr *SE) { 355 return SE->getKind() == IntSymExprKind; 356 } 357}; 358 359/// \brief Represents a symbolic expression like 'x' + 'y'. 360class SymSymExpr : public BinarySymExpr { 361 const SymExpr *LHS; 362 const SymExpr *RHS; 363 364public: 365 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 366 QualType t) 367 : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {} 368 369 const SymExpr *getLHS() const { return LHS; } 370 const SymExpr *getRHS() const { return RHS; } 371 372 void dumpToStream(raw_ostream &os) const override; 373 374 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 375 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 376 ID.AddInteger((unsigned) SymSymExprKind); 377 ID.AddPointer(lhs); 378 ID.AddInteger(op); 379 ID.AddPointer(rhs); 380 ID.Add(t); 381 } 382 383 void Profile(llvm::FoldingSetNodeID& ID) override { 384 Profile(ID, LHS, getOpcode(), RHS, getType()); 385 } 386 387 // Implement isa<T> support. 388 static inline bool classof(const SymExpr *SE) { 389 return SE->getKind() == SymSymExprKind; 390 } 391}; 392 393class SymbolManager { 394 typedef llvm::FoldingSet<SymExpr> DataSetTy; 395 typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 396 397 DataSetTy DataSet; 398 /// Stores the extra dependencies between symbols: the data should be kept 399 /// alive as long as the key is live. 400 SymbolDependTy SymbolDependencies; 401 unsigned SymbolCounter; 402 llvm::BumpPtrAllocator& BPAlloc; 403 BasicValueFactory &BV; 404 ASTContext &Ctx; 405 406public: 407 SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 408 llvm::BumpPtrAllocator& bpalloc) 409 : SymbolDependencies(16), SymbolCounter(0), 410 BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 411 412 ~SymbolManager(); 413 414 static bool canSymbolicate(QualType T); 415 416 /// \brief Make a unique symbol for MemRegion R according to its kind. 417 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 418 419 const SymbolConjured* conjureSymbol(const Stmt *E, 420 const LocationContext *LCtx, 421 QualType T, 422 unsigned VisitCount, 423 const void *SymbolTag = nullptr); 424 425 const SymbolConjured* conjureSymbol(const Expr *E, 426 const LocationContext *LCtx, 427 unsigned VisitCount, 428 const void *SymbolTag = nullptr) { 429 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 430 } 431 432 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 433 const TypedValueRegion *R); 434 435 const SymbolExtent *getExtentSymbol(const SubRegion *R); 436 437 /// \brief Creates a metadata symbol associated with a specific region. 438 /// 439 /// VisitCount can be used to differentiate regions corresponding to 440 /// different loop iterations, thus, making the symbol path-dependent. 441 const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, 442 QualType T, 443 const LocationContext *LCtx, 444 unsigned VisitCount, 445 const void *SymbolTag = nullptr); 446 447 const SymbolCast* getCastSymbol(const SymExpr *Operand, 448 QualType From, QualType To); 449 450 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 451 const llvm::APSInt& rhs, QualType t); 452 453 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 454 const llvm::APSInt& rhs, QualType t) { 455 return getSymIntExpr(&lhs, op, rhs, t); 456 } 457 458 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 459 BinaryOperator::Opcode op, 460 const SymExpr *rhs, QualType t); 461 462 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 463 const SymExpr *rhs, QualType t); 464 465 QualType getType(const SymExpr *SE) const { 466 return SE->getType(); 467 } 468 469 /// \brief Add artificial symbol dependency. 470 /// 471 /// The dependent symbol should stay alive as long as the primary is alive. 472 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 473 474 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 475 476 ASTContext &getContext() { return Ctx; } 477 BasicValueFactory &getBasicVals() { return BV; } 478}; 479 480/// \brief A class responsible for cleaning up unused symbols. 481class SymbolReaper { 482 enum SymbolStatus { 483 NotProcessed, 484 HaveMarkedDependents 485 }; 486 487 typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 488 typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 489 typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 490 491 SymbolMapTy TheLiving; 492 SymbolSetTy MetadataInUse; 493 SymbolSetTy TheDead; 494 495 RegionSetTy RegionRoots; 496 497 const StackFrameContext *LCtx; 498 const Stmt *Loc; 499 SymbolManager& SymMgr; 500 StoreRef reapedStore; 501 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 502 503public: 504 /// \brief Construct a reaper object, which removes everything which is not 505 /// live before we execute statement s in the given location context. 506 /// 507 /// If the statement is NULL, everything is this and parent contexts is 508 /// considered live. 509 /// If the stack frame context is NULL, everything on stack is considered 510 /// dead. 511 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 512 StoreManager &storeMgr) 513 : LCtx(Ctx), Loc(s), SymMgr(symmgr), 514 reapedStore(nullptr, storeMgr) {} 515 516 const LocationContext *getLocationContext() const { return LCtx; } 517 518 bool isLive(SymbolRef sym); 519 bool isLiveRegion(const MemRegion *region); 520 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 521 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 522 523 /// \brief Unconditionally marks a symbol as live. 524 /// 525 /// This should never be 526 /// used by checkers, only by the state infrastructure such as the store and 527 /// environment. Checkers should instead use metadata symbols and markInUse. 528 void markLive(SymbolRef sym); 529 530 /// \brief Marks a symbol as important to a checker. 531 /// 532 /// For metadata symbols, 533 /// this will keep the symbol alive as long as its associated region is also 534 /// live. For other symbols, this has no effect; checkers are not permitted 535 /// to influence the life of other symbols. This should be used before any 536 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 537 void markInUse(SymbolRef sym); 538 539 /// \brief If a symbol is known to be live, marks the symbol as live. 540 /// 541 /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 542 /// Returns true if the symbol is dead, false if live. 543 bool maybeDead(SymbolRef sym); 544 545 typedef SymbolSetTy::const_iterator dead_iterator; 546 dead_iterator dead_begin() const { return TheDead.begin(); } 547 dead_iterator dead_end() const { return TheDead.end(); } 548 549 bool hasDeadSymbols() const { 550 return !TheDead.empty(); 551 } 552 553 typedef RegionSetTy::const_iterator region_iterator; 554 region_iterator region_begin() const { return RegionRoots.begin(); } 555 region_iterator region_end() const { return RegionRoots.end(); } 556 557 /// \brief Returns whether or not a symbol has been confirmed dead. 558 /// 559 /// This should only be called once all marking of dead symbols has completed. 560 /// (For checkers, this means only in the evalDeadSymbols callback.) 561 bool isDead(SymbolRef sym) const { 562 return TheDead.count(sym); 563 } 564 565 void markLive(const MemRegion *region); 566 void markElementIndicesLive(const MemRegion *region); 567 568 /// \brief Set to the value of the symbolic store after 569 /// StoreManager::removeDeadBindings has been called. 570 void setReapedStore(StoreRef st) { reapedStore = st; } 571 572private: 573 /// Mark the symbols dependent on the input symbol as live. 574 void markDependentsLive(SymbolRef sym); 575}; 576 577class SymbolVisitor { 578protected: 579 ~SymbolVisitor() = default; 580 581public: 582 SymbolVisitor() = default; 583 SymbolVisitor(const SymbolVisitor &) = default; 584 SymbolVisitor(SymbolVisitor &&) {} 585 586 /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 587 /// 588 /// The method returns \c true if symbols should continue be scanned and \c 589 /// false otherwise. 590 virtual bool VisitSymbol(SymbolRef sym) = 0; 591 virtual bool VisitMemRegion(const MemRegion *region) { return true; } 592}; 593 594} // end GR namespace 595 596} // end clang namespace 597 598namespace llvm { 599static inline raw_ostream &operator<<(raw_ostream &os, 600 const clang::ento::SymExpr *SE) { 601 SE->dumpToStream(os); 602 return os; 603} 604} // end llvm namespace 605#endif 606