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