1d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 3d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// The LLVM Compiler Infrastructure 4d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 5d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// This file is distributed under the University of Illinois Open Source 6d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// License. See LICENSE.TXT for details. 7d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 8d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//===----------------------------------------------------------------------===// 9d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 10843e934ba8c6ebc00d2f6969a50af7074597e8e3Gabor Greif// This file defines SymbolManager, a class that manages symbolic values 11d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// created for use by ExprEngine and related classes. 12d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 13d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//===----------------------------------------------------------------------===// 14d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 15176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 16176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 17d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 18d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek#include "clang/AST/Decl.h" 19d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek#include "clang/AST/Expr.h" 205e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer#include "clang/Analysis/AnalysisContext.h" 21d47d3b0cfeb7e8564ff77f48130fe63282b6d127Chris Lattner#include "clang/Basic/LLVM.h" 224967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 23882998923889a2fcce9b49696506c499e22cf38fTed Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 244967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 25882998923889a2fcce9b49696506c499e22cf38fTed Kremenek#include "llvm/ADT/DenseMap.h" 2630a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/ADT/DenseSet.h" 2730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/ADT/FoldingSet.h" 28651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "llvm/Support/Allocator.h" 2930a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/Support/DataTypes.h" 30d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpnamespace clang { 32e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek class ASTContext; 335a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis class StackFrameContext; 345a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 359ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 36e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek class BasicValueFactory; 3732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose class SubRegion; 389697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek class TypedValueRegion; 39edeb5b6b50e773b243e0ee0d84589cd1f7dea9b0Ted Kremenek class VarRegion; 401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 415fc7def35ee858791e591d005b4ae343632ca931Anna Zaks///\brief A symbol representing the value stored at a MemRegion. 42d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xuclass SymbolRegionValue : public SymbolData { 439697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R; 4445257c37a4e9a8f915661e0f964aec375909eb4cZhongxing Xu 45d763eb91aab5bdecd11825fadb35d6d8cc905f63Ted Kremenekpublic: 469697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 474967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : SymbolData(SymbolRegionValueKind, sym), R(r) {} 481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 499697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion* getRegion() const { return R; } 509ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek 519697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 524967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar profile.AddInteger((unsigned) SymbolRegionValueKind); 539ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek profile.AddPointer(R); 5400a3a5f024ac54088ab887712b292171188064f0Ted Kremenek } 551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 56651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& profile) override { 5714d2328ecfc5102b077fa2c2c129dce1574c8831Zhongxing Xu Profile(profile, R); 5800a3a5f024ac54088ab887712b292171188064f0Ted Kremenek } 591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 60651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 614967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar const MemRegion *getOriginRegion() const override { return getRegion(); } 621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 63651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override; 649ab6b9cfb76ee56a61829e2bdb08e5cdc288726eTed Kremenek 65d763eb91aab5bdecd11825fadb35d6d8cc905f63Ted Kremenek // Implement isa<T> support. 669c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 674967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymbolRegionValueKind; 68eabf776661662a8e652eb692084d20fddffd5ccaZhongxing Xu } 69eabf776661662a8e652eb692084d20fddffd5ccaZhongxing Xu}; 70eabf776661662a8e652eb692084d20fddffd5ccaZhongxing Xu 713cdf584e068056540769dab56cad333e95a89750Anna Zaks/// A symbol representing the result of an expression in the case when we do 723cdf584e068056540769dab56cad333e95a89750Anna Zaks/// not know anything about what the expression is. 73361fa8ecd122a5b06c2c59d44419e202f42e1c5dTed Kremenekclass SymbolConjured : public SymbolData { 749c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *S; 7560a6e0ce72a24d6247602625c631fc3dc7bfd8d4Ted Kremenek QualType T; 7600a3a5f024ac54088ab887712b292171188064f0Ted Kremenek unsigned Count; 773133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx; 789c378f705405d37f49795d5e915989de774fe11fTed Kremenek const void *SymbolTag; 7900a3a5f024ac54088ab887712b292171188064f0Ted Kremenek 8000a3a5f024ac54088ab887712b292171188064f0Ted Kremenekpublic: 813133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 824967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar QualType t, unsigned count, const void *symbolTag) 834967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count), 844967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar LCtx(lctx), SymbolTag(symbolTag) {} 851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 869c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *getStmt() const { return S; } 87a880b66d6e0e446501fcbc27b87a1ec0e4ecde4cTed Kremenek unsigned getCount() const { return Count; } 889c378f705405d37f49795d5e915989de774fe11fTed Kremenek const void *getTag() const { return SymbolTag; } 891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 90651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override; 911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 92651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 949c378f705405d37f49795d5e915989de774fe11fTed Kremenek static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 953133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek QualType T, unsigned Count, const LocationContext *LCtx, 963133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const void *SymbolTag) { 974967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar profile.AddInteger((unsigned) SymbolConjuredKind); 98b5abb429e7aac731c3b4363a6118a6b3a6e27abcTed Kremenek profile.AddPointer(S); 993133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek profile.AddPointer(LCtx); 10060a6e0ce72a24d6247602625c631fc3dc7bfd8d4Ted Kremenek profile.Add(T); 10100a3a5f024ac54088ab887712b292171188064f0Ted Kremenek profile.AddInteger(Count); 102a880b66d6e0e446501fcbc27b87a1ec0e4ecde4cTed Kremenek profile.AddPointer(SymbolTag); 10300a3a5f024ac54088ab887712b292171188064f0Ted Kremenek } 104a880b66d6e0e446501fcbc27b87a1ec0e4ecde4cTed Kremenek 105651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& profile) override { 1063133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Profile(profile, S, T, Count, LCtx, SymbolTag); 10700a3a5f024ac54088ab887712b292171188064f0Ted Kremenek } 108a880b66d6e0e446501fcbc27b87a1ec0e4ecde4cTed Kremenek 10900a3a5f024ac54088ab887712b292171188064f0Ted Kremenek // Implement isa<T> support. 1109c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 1114967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymbolConjuredKind; 1121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 11300a3a5f024ac54088ab887712b292171188064f0Ted Kremenek}; 1141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 11575eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks/// A symbol representing the value of a MemRegion whose parent region has 11675eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks/// symbolic value. 117fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenekclass SymbolDerived : public SymbolData { 118fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek SymbolRef parentSymbol; 1199697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R; 1201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 121fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenekpublic: 1229697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 1234967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {} 124fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek 125fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek SymbolRef getParentSymbol() const { return parentSymbol; } 1269697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *getRegion() const { return R; } 1271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 128651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override; 1291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 130651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 1314967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar const MemRegion *getOriginRegion() const override { return getRegion(); } 1321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 133fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 1349697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *r) { 1354967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar profile.AddInteger((unsigned) SymbolDerivedKind); 136fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek profile.AddPointer(r); 137fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek profile.AddPointer(parent); 138fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek } 1391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 140651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& profile) override { 141fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek Profile(profile, parentSymbol, R); 142fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek } 1431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 144fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek // Implement isa<T> support. 1459c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 1464967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymbolDerivedKind; 1471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 148fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek}; 149d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 150bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 151bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// Clients should not ask the SymbolManager for a region's extent. Always use 152bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// SubRegion::getExtent instead -- the value returned may not be a symbol. 15332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Roseclass SymbolExtent : public SymbolData { 15432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose const SubRegion *R; 15532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 15632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rosepublic: 15732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SymbolExtent(SymbolID sym, const SubRegion *r) 1584967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : SymbolData(SymbolExtentKind, sym), R(r) {} 15932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 16032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose const SubRegion *getRegion() const { return R; } 16132f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 162651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override; 16332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 164651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 16532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 16632f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 1674967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar profile.AddInteger((unsigned) SymbolExtentKind); 16832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose profile.AddPointer(R); 16932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose } 17032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 171651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& profile) override { 17232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose Profile(profile, R); 17332f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose } 17432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 17532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // Implement isa<T> support. 1769c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 1774967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymbolExtentKind; 17832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose } 17932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose}; 18032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 181bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// SymbolMetadata - Represents path-dependent metadata about a specific region. 182bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// Metadata symbols remain live as long as they are marked as in use before 183bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// dead-symbol sweeping AND their associated regions are still alive. 184bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose/// Intended for use by checkers. 185bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Roseclass SymbolMetadata : public SymbolData { 186bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const MemRegion* R; 1879c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *S; 188bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose QualType T; 189bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose unsigned Count; 1909c378f705405d37f49795d5e915989de774fe11fTed Kremenek const void *Tag; 191bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rosepublic: 1929c378f705405d37f49795d5e915989de774fe11fTed Kremenek SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 1939c378f705405d37f49795d5e915989de774fe11fTed Kremenek unsigned count, const void *tag) 1944967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 195bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 196bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const MemRegion *getRegion() const { return R; } 1979c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *getStmt() const { return S; } 198bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose unsigned getCount() const { return Count; } 1999c378f705405d37f49795d5e915989de774fe11fTed Kremenek const void *getTag() const { return Tag; } 200bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 201651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override; 202bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 203651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 204bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 205bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 206bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const Stmt *S, QualType T, unsigned Count, 207bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose const void *Tag) { 2084967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar profile.AddInteger((unsigned) SymbolMetadataKind); 209bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose profile.AddPointer(R); 210bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose profile.AddPointer(S); 211bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose profile.Add(T); 212bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose profile.AddInteger(Count); 213bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose profile.AddPointer(Tag); 214bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 215bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 216651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& profile) override { 217bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose Profile(profile, R, S, T, Count, Tag); 218bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 219bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 220bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose // Implement isa<T> support. 2219c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 2224967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymbolMetadataKind; 223bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 224bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose}; 225bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 226aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks/// \brief Represents a cast expression. 227aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaksclass SymbolCast : public SymExpr { 228aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks const SymExpr *Operand; 229aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks /// Type of the operand. 230aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks QualType FromTy; 231aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks /// The type of the result. 232aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks QualType ToTy; 233aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 234aace9ef279be3dadd53b481aee568bd7701178b4Anna Zakspublic: 235aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks SymbolCast(const SymExpr *In, QualType From, QualType To) : 2364967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { } 237aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 238651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override { return ToTy; } 239aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 2404617e2843e711136746865d7d6d27c7cead21f2bEli Friedman const SymExpr *getOperand() const { return Operand; } 241aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 242651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 243aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 244aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks static void Profile(llvm::FoldingSetNodeID& ID, 245aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks const SymExpr *In, QualType From, QualType To) { 2464967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar ID.AddInteger((unsigned) SymbolCastKind); 247aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks ID.AddPointer(In); 248aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks ID.Add(From); 249aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks ID.Add(To); 250aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks } 251aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 252651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& ID) override { 253aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks Profile(ID, Operand, FromTy, ToTy); 254aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks } 255aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 256aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks // Implement isa<T> support. 257aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks static inline bool classof(const SymExpr *SE) { 2584967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymbolCastKind; 259aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks } 260aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks}; 261aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 2624de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes/// \brief Represents a symbolic expression involving a binary operator 2634de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostesclass BinarySymExpr : public SymExpr { 264a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu BinaryOperator::Opcode Op; 265a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu QualType T; 266a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 2674de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostesprotected: 2684de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 2694de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes : SymExpr(k), Op(op), T(t) {} 270a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 2714de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostespublic: 272e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek // FIXME: We probably need to make this out-of-line to avoid redundant 273e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek // generation of virtual functions. 274651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines QualType getType() const override { return T; } 2751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 276e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek BinaryOperator::Opcode getOpcode() const { return Op; } 2771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2784de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes // Implement isa<T> support. 2794de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes static inline bool classof(const SymExpr *SE) { 2804de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes Kind k = SE->getKind(); 2814de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 2824de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes } 2834de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes}; 2844de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes 2854de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes/// \brief Represents a symbolic expression like 'x' + 3. 2864de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostesclass SymIntExpr : public BinarySymExpr { 2874de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes const SymExpr *LHS; 2884de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes const llvm::APSInt& RHS; 2894de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes 2904de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostespublic: 2914de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 2924de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes const llvm::APSInt& rhs, QualType t) 2934967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {} 2944de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes 295651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 2961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 297e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *getLHS() const { return LHS; } 298e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const llvm::APSInt &getRHS() const { return RHS; } 299a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 3001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 301e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek BinaryOperator::Opcode op, const llvm::APSInt& rhs, 302a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu QualType t) { 3034967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar ID.AddInteger((unsigned) SymIntExprKind); 304e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ID.AddPointer(lhs); 305a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu ID.AddInteger(op); 306e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ID.AddPointer(&rhs); 307a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu ID.Add(t); 308a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu } 309a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 310651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& ID) override { 3114de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes Profile(ID, LHS, getOpcode(), RHS, getType()); 312a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu } 3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 314e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek // Implement isa<T> support. 3159c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 3164967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymIntExprKind; 3171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 318a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu}; 319a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 3204de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes/// \brief Represents a symbolic expression like 3 - 'x'. 3214de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostesclass IntSymExpr : public BinarySymExpr { 3226d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const llvm::APSInt& LHS; 3236d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const SymExpr *RHS; 3246d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 3256d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zakspublic: 3266d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 3276d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const SymExpr *rhs, QualType t) 3284967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {} 3296d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 330651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 3316d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 3326d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const SymExpr *getRHS() const { return RHS; } 3336d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const llvm::APSInt &getLHS() const { return LHS; } 3346d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 3356d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 3366d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks BinaryOperator::Opcode op, const SymExpr *rhs, 3376d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks QualType t) { 3384967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar ID.AddInteger((unsigned) IntSymExprKind); 3396d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks ID.AddPointer(&lhs); 3406d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks ID.AddInteger(op); 3416d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks ID.AddPointer(rhs); 3426d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks ID.Add(t); 3436d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks } 3446d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 345651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& ID) override { 3464de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes Profile(ID, LHS, getOpcode(), RHS, getType()); 3476d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks } 3486d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 3496d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks // Implement isa<T> support. 3506d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks static inline bool classof(const SymExpr *SE) { 3514967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == IntSymExprKind; 3526d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks } 3536d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks}; 3546d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 3554de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes/// \brief Represents a symbolic expression like 'x' + 'y'. 3564de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostesclass SymSymExpr : public BinarySymExpr { 357e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *LHS; 358e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *RHS; 359a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 360a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xupublic: 361e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 362e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek QualType t) 3634967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {} 364a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 365e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *getLHS() const { return LHS; } 366e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *getRHS() const { return RHS; } 3671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 368651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void dumpToStream(raw_ostream &os) const override; 3691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 370e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 371d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 3724967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar ID.AddInteger((unsigned) SymSymExprKind); 373e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ID.AddPointer(lhs); 374a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu ID.AddInteger(op); 375e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ID.AddPointer(rhs); 376a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu ID.Add(t); 377a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu } 378a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 379651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void Profile(llvm::FoldingSetNodeID& ID) override { 3804de561f470be0cffeff5a92a286e9d6bf9bd8cffRyan Govostes Profile(ID, LHS, getOpcode(), RHS, getType()); 381a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu } 3821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 383e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek // Implement isa<T> support. 3849c378f705405d37f49795d5e915989de774fe11fTed Kremenek static inline bool classof(const SymExpr *SE) { 3854967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar return SE->getKind() == SymSymExprKind; 3861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 387d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek}; 388d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 389d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenekclass SymbolManager { 390e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek typedef llvm::FoldingSet<SymExpr> DataSetTy; 391579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 39275eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks 3931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DataSetTy DataSet; 39489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks /// Stores the extra dependencies between symbols: the data should be kept 39589f920940de4b414616cabb310c37fa84ed2476aAnna Zaks /// alive as long as the key is live. 39689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks SymbolDependTy SymbolDependencies; 39700a3a5f024ac54088ab887712b292171188064f0Ted Kremenek unsigned SymbolCounter; 39800a3a5f024ac54088ab887712b292171188064f0Ted Kremenek llvm::BumpPtrAllocator& BPAlloc; 399e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek BasicValueFactory &BV; 4009c378f705405d37f49795d5e915989de774fe11fTed Kremenek ASTContext &Ctx; 4011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 402d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenekpublic: 4039c378f705405d37f49795d5e915989de774fe11fTed Kremenek SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 404e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek llvm::BumpPtrAllocator& bpalloc) 405579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks : SymbolDependencies(16), SymbolCounter(0), 406579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 4071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 408d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek ~SymbolManager(); 4091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 410693de5d7feb92c096431c98ea6ee637494bfe6fbTed Kremenek static bool canSymbolicate(QualType T); 4114193eca10ce0cc8b2dae887e935a43b26f492b5bZhongxing Xu 41275eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief Make a unique symbol for MemRegion R according to its kind. 4139697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 41414d2328ecfc5102b077fa2c2c129dce1574c8831Zhongxing Xu 4153b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const SymbolConjured* conjureSymbol(const Stmt *E, 4163b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const LocationContext *LCtx, 4173b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek QualType T, 4183b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek unsigned VisitCount, 4196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const void *SymbolTag = nullptr); 4203b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek 4213b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const SymbolConjured* conjureSymbol(const Expr *E, 4223b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek const LocationContext *LCtx, 4233b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek unsigned VisitCount, 4246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const void *SymbolTag = nullptr) { 4253b1df8bb941a18c4a7256d7cfcbccb9de7e39995Ted Kremenek return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 42660a6e0ce72a24d6247602625c631fc3dc7bfd8d4Ted Kremenek } 4271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 428fb91c70e24e20f8704edf9bc5049ffbe7e234a38Ted Kremenek const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 4299697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *R); 430a129eb974d8ff0ad4a4dd94ad1e6c5f98897ddb4Zhongxing Xu 43132f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose const SymbolExtent *getExtentSymbol(const SubRegion *R); 43232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 43375eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief Creates a metadata symbol associated with a specific region. 43475eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// 4353f10e32b15e54f507aed90cb72d73c7acaa500bbAnna Zaks /// VisitCount can be used to differentiate regions corresponding to 4363f10e32b15e54f507aed90cb72d73c7acaa500bbAnna Zaks /// different loop iterations, thus, making the symbol path-dependent. 4376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, 438bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose QualType T, unsigned VisitCount, 4396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const void *SymbolTag = nullptr); 440bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 441aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks const SymbolCast* getCastSymbol(const SymExpr *Operand, 442aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks QualType From, QualType To); 443aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 444d9b6ad609ef0b90527e848ba69dc2e492771be4fZhongxing Xu const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 445e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const llvm::APSInt& rhs, QualType t); 4461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 447e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 448e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const llvm::APSInt& rhs, QualType t) { 449e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek return getSymIntExpr(&lhs, op, rhs, t); 450e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek } 451e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek 4526d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 4536d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks BinaryOperator::Opcode op, 4546d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks const SymExpr *rhs, QualType t); 4556d6a83c3754b449ac24cb83bc6d3a50b10535061Anna Zaks 456e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 457e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek const SymExpr *rhs, QualType t); 4581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 459e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek QualType getType(const SymExpr *SE) const { 460732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted Kremenek return SE->getType(); 461d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek } 4621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 46389f920940de4b414616cabb310c37fa84ed2476aAnna Zaks /// \brief Add artificial symbol dependency. 46489f920940de4b414616cabb310c37fa84ed2476aAnna Zaks /// 46589f920940de4b414616cabb310c37fa84ed2476aAnna Zaks /// The dependent symbol should stay alive as long as the primary is alive. 46689f920940de4b414616cabb310c37fa84ed2476aAnna Zaks void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 46789f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 46889f920940de4b414616cabb310c37fa84ed2476aAnna Zaks const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 46989f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 470e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek ASTContext &getContext() { return Ctx; } 471e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek BasicValueFactory &getBasicVals() { return BV; } 472d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek}; 4731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 474914edfbb07c34d8cad8d0451193b4f9dd02a2d5aDavid Blaikie/// \brief A class responsible for cleaning up unused symbols. 475241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenekclass SymbolReaper { 476579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks enum SymbolStatus { 477579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks NotProcessed, 478579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks HaveMarkedDependents 479579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks }; 480579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks 481bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 482579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 483bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 4841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 485579ad7ac56f7940cc543b7216ee1b1a7de1ed712Anna Zaks SymbolMapTy TheLiving; 486bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek SymbolSetTy MetadataInUse; 487bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek SymbolSetTy TheDead; 488bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 489bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek RegionSetTy RegionRoots; 490bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 4917fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek const StackFrameContext *LCtx; 4927dadf79bd809cc01fe275f9a7243593bc2af5c10Jordy Rose const Stmt *Loc; 493241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek SymbolManager& SymMgr; 494882998923889a2fcce9b49696506c499e22cf38fTed Kremenek StoreRef reapedStore; 495882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 4961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 497241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenekpublic: 4980b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// \brief Construct a reaper object, which removes everything which is not 4990b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// live before we execute statement s in the given location context. 5000b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 5010b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// If the statement is NULL, everything is this and parent contexts is 5020b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// considered live. 5038501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks /// If the stack frame context is NULL, everything on stack is considered 5048501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks /// dead. 5058501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 506882998923889a2fcce9b49696506c499e22cf38fTed Kremenek StoreManager &storeMgr) 5078501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks : LCtx(Ctx), Loc(s), SymMgr(symmgr), 5086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines reapedStore(nullptr, storeMgr) {} 5091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 510c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu const LocationContext *getLocationContext() const { return LCtx; } 511c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu 512241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek bool isLive(SymbolRef sym); 513bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek bool isLiveRegion(const MemRegion *region); 5145eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 515882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 516bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 51775eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief Unconditionally marks a symbol as live. 51875eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// 51975eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// This should never be 52075eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// used by checkers, only by the state infrastructure such as the store and 52175eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// environment. Checkers should instead use metadata symbols and markInUse. 522241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek void markLive(SymbolRef sym); 523bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 52475eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief Marks a symbol as important to a checker. 52575eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// 52675eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// For metadata symbols, 52775eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// this will keep the symbol alive as long as its associated region is also 52875eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// live. For other symbols, this has no effect; checkers are not permitted 52975eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// to influence the life of other symbols. This should be used before any 53075eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 531bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose void markInUse(SymbolRef sym); 532bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 53375eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief If a symbol is known to be live, marks the symbol as live. 53475eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// 53575eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 53675eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// Returns true if the symbol is dead, false if live. 537241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek bool maybeDead(SymbolRef sym); 5381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 539bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek typedef SymbolSetTy::const_iterator dead_iterator; 540241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek dead_iterator dead_begin() const { return TheDead.begin(); } 541241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek dead_iterator dead_end() const { return TheDead.end(); } 5421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 543241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek bool hasDeadSymbols() const { 544a97d54c165ca6b6e57b9f333059a84c2188dd591Ted Kremenek return !TheDead.empty(); 545241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek } 546bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 547bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek typedef RegionSetTy::const_iterator region_iterator; 548bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek region_iterator region_begin() const { return RegionRoots.begin(); } 549bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek region_iterator region_end() const { return RegionRoots.end(); } 550bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose 55175eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief Returns whether or not a symbol has been confirmed dead. 55275eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// 55375eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// This should only be called once all marking of dead symbols has completed. 55475eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// (For checkers, this means only in the evalDeadSymbols callback.) 555bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose bool isDead(SymbolRef sym) const { 556bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose return TheDead.count(sym); 557bd533aa4ff8895c676d4634d0d3de254962569d0Jordy Rose } 558882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 559bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek void markLive(const MemRegion *region); 56087d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar void markElementIndicesLive(const MemRegion *region); 561bea2753da897ede723e70bcd17023d050b0603d0Ted Kremenek 56275eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// \brief Set to the value of the symbolic store after 563882998923889a2fcce9b49696506c499e22cf38fTed Kremenek /// StoreManager::removeDeadBindings has been called. 564882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void setReapedStore(StoreRef st) { reapedStore = st; } 56589f920940de4b414616cabb310c37fa84ed2476aAnna Zaks 56689f920940de4b414616cabb310c37fa84ed2476aAnna Zaksprivate: 56789f920940de4b414616cabb310c37fa84ed2476aAnna Zaks /// Mark the symbols dependent on the input symbol as live. 56889f920940de4b414616cabb310c37fa84ed2476aAnna Zaks void markDependentsLive(SymbolRef sym); 569241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek}; 5701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5715216ad7e095873f19e535ad1efba91973f05d8e8Ted Kremenekclass SymbolVisitor { 57287d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainarprotected: 57387d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar ~SymbolVisitor() = default; 57487d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 5755216ad7e095873f19e535ad1efba91973f05d8e8Ted Kremenekpublic: 57687d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar SymbolVisitor() = default; 57787d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar SymbolVisitor(const SymbolVisitor &) = default; 57887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar SymbolVisitor(SymbolVisitor &&) {} 57987d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 58018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 58175eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// 58275eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// The method returns \c true if symbols should continue be scanned and \c 58375eeeb173cd3f6425247d3686c19e49117834fc3Anna Zaks /// false otherwise. 5845216ad7e095873f19e535ad1efba91973f05d8e8Ted Kremenek virtual bool VisitSymbol(SymbolRef sym) = 0; 585cb9657cfba92d5a3009e1b37109e03258c20d327Bill Wendling virtual bool VisitMemRegion(const MemRegion *region) { return true; } 5865216ad7e095873f19e535ad1efba91973f05d8e8Ted Kremenek}; 5871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5885a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 5895a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 590d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek} // end clang namespace 591d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 592e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremeneknamespace llvm { 5939c378f705405d37f49795d5e915989de774fe11fTed Kremenekstatic inline raw_ostream &operator<<(raw_ostream &os, 5943352ea914644edb2b56e999c94319ce915d68707Anna Zaks const clang::ento::SymExpr *SE) { 5958800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek SE->dumpToStream(os); 5968800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek return os; 597e0e4ebf6bfca5a71b2344d8a1b748b852509279cTed Kremenek} 5988800ad4eaa1621f6d23c8264971063b9f8da6a2eTed Kremenek} // end llvm namespace 599d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek#endif 600