//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_CLANG_GR_SYMMGR_H
-#define LLVM_CLANG_GR_SYMMGR_H
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
#include "clang/AST/Decl.h"
#include "clang/AST/Expr.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Basic/LLVM.h"
-#include "llvm/Support/DataTypes.h"
-#include "llvm/ADT/FoldingSet.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
-
-namespace llvm {
-class BumpPtrAllocator;
-}
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/DataTypes.h"
namespace clang {
class ASTContext;
class BasicValueFactory;
class MemRegion;
class SubRegion;
- class TypedRegion;
+ class TypedValueRegion;
class VarRegion;
+/// \brief Symbolic value. These values used to capture symbolic execution of
+/// the program.
class SymExpr : public llvm::FoldingSetNode {
+ virtual void anchor();
public:
- enum Kind { BEGIN_SYMBOLS,
- RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
- MetadataKind,
- END_SYMBOLS,
- SymIntKind, SymSymKind };
+ enum Kind {
+ SymbolRegionValueKind,
+ SymbolConjuredKind,
+ SymbolDerivedKind,
+ SymbolExtentKind,
+ SymbolMetadataKind,
+ BEGIN_SYMBOLS = SymbolRegionValueKind,
+ END_SYMBOLS = SymbolMetadataKind,
+ SymIntExprKind,
+ IntSymExprKind,
+ SymSymExprKind,
+ BEGIN_BINARYSYMEXPRS = SymIntExprKind,
+ END_BINARYSYMEXPRS = SymSymExprKind,
+ SymbolCastKind
+ };
+
private:
Kind K;
Kind getKind() const { return K; }
- void dump() const;
+ virtual void dump() const;
- virtual void dumpToStream(raw_ostream &os) const = 0;
+ virtual void dumpToStream(raw_ostream &os) const {}
- virtual QualType getType(ASTContext&) const = 0;
+ virtual QualType getType() const = 0;
virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
- // Implement isa<T> support.
- static inline bool classof(const SymExpr*) { return true; }
+ /// \brief Iterator over symbols that the current symbol depends on.
+ ///
+ /// For SymbolData, it's the symbol itself; for expressions, it's the
+ /// expression symbol and all the operands in it. Note, SymbolDerived is
+ /// treated as SymbolData - the iterator will NOT visit the parent region.
+ class symbol_iterator {
+ SmallVector<const SymExpr*, 5> itr;
+ void expand();
+ public:
+ symbol_iterator() {}
+ symbol_iterator(const SymExpr *SE);
+
+ symbol_iterator &operator++();
+ const SymExpr* operator*();
+
+ bool operator==(const symbol_iterator &X) const;
+ bool operator!=(const symbol_iterator &X) const;
+ };
+
+ symbol_iterator symbol_begin() const {
+ return symbol_iterator(this);
+ }
+ static symbol_iterator symbol_end() { return symbol_iterator(); }
+
+ unsigned computeComplexity() const;
};
-typedef unsigned SymbolID;
+typedef const SymExpr* SymbolRef;
+typedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy;
+typedef unsigned SymbolID;
+/// \brief A symbol representing data which can be stored in a memory location
+/// (region).
class SymbolData : public SymExpr {
-private:
+ void anchor() override;
const SymbolID Sym;
protected:
SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
public:
- virtual ~SymbolData() {}
+ ~SymbolData() override {}
SymbolID getSymbolID() const { return Sym; }
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
+ static inline bool classof(const SymExpr *SE) {
Kind k = SE->getKind();
- return k > BEGIN_SYMBOLS && k < END_SYMBOLS;
+ return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
}
};
-typedef const SymbolData* SymbolRef;
-
-// A symbol representing the value of a MemRegion.
+///\brief A symbol representing the value stored at a MemRegion.
class SymbolRegionValue : public SymbolData {
- const TypedRegion *R;
+ const TypedValueRegion *R;
public:
- SymbolRegionValue(SymbolID sym, const TypedRegion *r)
- : SymbolData(RegionValueKind, sym), R(r) {}
+ SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
+ : SymbolData(SymbolRegionValueKind, sym), R(r) {}
- const TypedRegion* getRegion() const { return R; }
+ const TypedValueRegion* getRegion() const { return R; }
- static void Profile(llvm::FoldingSetNodeID& profile, const TypedRegion* R) {
- profile.AddInteger((unsigned) RegionValueKind);
+ static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
+ profile.AddInteger((unsigned) SymbolRegionValueKind);
profile.AddPointer(R);
}
- virtual void Profile(llvm::FoldingSetNodeID& profile) {
+ void Profile(llvm::FoldingSetNodeID& profile) override {
Profile(profile, R);
}
- void dumpToStream(raw_ostream &os) const;
+ void dumpToStream(raw_ostream &os) const override;
- QualType getType(ASTContext&) const;
+ QualType getType() const override;
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == RegionValueKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymbolRegionValueKind;
}
};
-// A symbol representing the result of an expression.
+/// A symbol representing the result of an expression in the case when we do
+/// not know anything about what the expression is.
class SymbolConjured : public SymbolData {
- const Stmt* S;
+ const Stmt *S;
QualType T;
unsigned Count;
- const void* SymbolTag;
+ const LocationContext *LCtx;
+ const void *SymbolTag;
public:
- SymbolConjured(SymbolID sym, const Stmt* s, QualType t, unsigned count,
- const void* symbolTag)
- : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count),
- SymbolTag(symbolTag) {}
+ SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
+ QualType t, unsigned count, const void *symbolTag)
+ : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count),
+ LCtx(lctx), SymbolTag(symbolTag) {}
- const Stmt* getStmt() const { return S; }
+ const Stmt *getStmt() const { return S; }
unsigned getCount() const { return Count; }
- const void* getTag() const { return SymbolTag; }
+ const void *getTag() const { return SymbolTag; }
- QualType getType(ASTContext&) const;
+ QualType getType() const override;
- void dumpToStream(raw_ostream &os) const;
+ void dumpToStream(raw_ostream &os) const override;
- static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S,
- QualType T, unsigned Count, const void* SymbolTag) {
- profile.AddInteger((unsigned) ConjuredKind);
+ static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
+ QualType T, unsigned Count, const LocationContext *LCtx,
+ const void *SymbolTag) {
+ profile.AddInteger((unsigned) SymbolConjuredKind);
profile.AddPointer(S);
+ profile.AddPointer(LCtx);
profile.Add(T);
profile.AddInteger(Count);
profile.AddPointer(SymbolTag);
}
- virtual void Profile(llvm::FoldingSetNodeID& profile) {
- Profile(profile, S, T, Count, SymbolTag);
+ void Profile(llvm::FoldingSetNodeID& profile) override {
+ Profile(profile, S, T, Count, LCtx, SymbolTag);
}
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == ConjuredKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymbolConjuredKind;
}
};
-// A symbol representing the value of a MemRegion whose parent region has
-// symbolic value.
+/// A symbol representing the value of a MemRegion whose parent region has
+/// symbolic value.
class SymbolDerived : public SymbolData {
SymbolRef parentSymbol;
- const TypedRegion *R;
+ const TypedValueRegion *R;
public:
- SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r)
- : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {}
+ SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
+ : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {}
SymbolRef getParentSymbol() const { return parentSymbol; }
- const TypedRegion *getRegion() const { return R; }
+ const TypedValueRegion *getRegion() const { return R; }
- QualType getType(ASTContext&) const;
+ QualType getType() const override;
- void dumpToStream(raw_ostream &os) const;
+ void dumpToStream(raw_ostream &os) const override;
static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
- const TypedRegion *r) {
- profile.AddInteger((unsigned) DerivedKind);
+ const TypedValueRegion *r) {
+ profile.AddInteger((unsigned) SymbolDerivedKind);
profile.AddPointer(r);
profile.AddPointer(parent);
}
- virtual void Profile(llvm::FoldingSetNodeID& profile) {
+ void Profile(llvm::FoldingSetNodeID& profile) override {
Profile(profile, parentSymbol, R);
}
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == DerivedKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymbolDerivedKind;
}
};
public:
SymbolExtent(SymbolID sym, const SubRegion *r)
- : SymbolData(ExtentKind, sym), R(r) {}
+ : SymbolData(SymbolExtentKind, sym), R(r) {}
const SubRegion *getRegion() const { return R; }
- QualType getType(ASTContext&) const;
+ QualType getType() const override;
- void dumpToStream(raw_ostream &os) const;
+ void dumpToStream(raw_ostream &os) const override;
static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
- profile.AddInteger((unsigned) ExtentKind);
+ profile.AddInteger((unsigned) SymbolExtentKind);
profile.AddPointer(R);
}
- virtual void Profile(llvm::FoldingSetNodeID& profile) {
+ void Profile(llvm::FoldingSetNodeID& profile) override {
Profile(profile, R);
}
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == ExtentKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymbolExtentKind;
}
};
/// Intended for use by checkers.
class SymbolMetadata : public SymbolData {
const MemRegion* R;
- const Stmt* S;
+ const Stmt *S;
QualType T;
unsigned Count;
- const void* Tag;
+ const void *Tag;
public:
- SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t,
- unsigned count, const void* tag)
- : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
+ SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
+ unsigned count, const void *tag)
+ : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
const MemRegion *getRegion() const { return R; }
- const Stmt* getStmt() const { return S; }
+ const Stmt *getStmt() const { return S; }
unsigned getCount() const { return Count; }
- const void* getTag() const { return Tag; }
+ const void *getTag() const { return Tag; }
- QualType getType(ASTContext&) const;
+ QualType getType() const override;
- void dumpToStream(raw_ostream &os) const;
+ void dumpToStream(raw_ostream &os) const override;
static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
const Stmt *S, QualType T, unsigned Count,
const void *Tag) {
- profile.AddInteger((unsigned) MetadataKind);
+ profile.AddInteger((unsigned) SymbolMetadataKind);
profile.AddPointer(R);
profile.AddPointer(S);
profile.Add(T);
profile.AddPointer(Tag);
}
- virtual void Profile(llvm::FoldingSetNodeID& profile) {
+ void Profile(llvm::FoldingSetNodeID& profile) override {
Profile(profile, R, S, T, Count, Tag);
}
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == MetadataKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymbolMetadataKind;
}
};
-// SymIntExpr - Represents symbolic expression like 'x' + 3.
-class SymIntExpr : public SymExpr {
- const SymExpr *LHS;
+/// \brief Represents a cast expression.
+class SymbolCast : public SymExpr {
+ const SymExpr *Operand;
+ /// Type of the operand.
+ QualType FromTy;
+ /// The type of the result.
+ QualType ToTy;
+
+public:
+ SymbolCast(const SymExpr *In, QualType From, QualType To) :
+ SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { }
+
+ QualType getType() const override { return ToTy; }
+
+ const SymExpr *getOperand() const { return Operand; }
+
+ void dumpToStream(raw_ostream &os) const override;
+
+ static void Profile(llvm::FoldingSetNodeID& ID,
+ const SymExpr *In, QualType From, QualType To) {
+ ID.AddInteger((unsigned) SymbolCastKind);
+ ID.AddPointer(In);
+ ID.Add(From);
+ ID.Add(To);
+ }
+
+ void Profile(llvm::FoldingSetNodeID& ID) override {
+ Profile(ID, Operand, FromTy, ToTy);
+ }
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymbolCastKind;
+ }
+};
+
+/// \brief Represents a symbolic expression involving a binary operator
+class BinarySymExpr : public SymExpr {
BinaryOperator::Opcode Op;
- const llvm::APSInt& RHS;
QualType T;
-public:
- SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
- const llvm::APSInt& rhs, QualType t)
- : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {}
+protected:
+ BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
+ : SymExpr(k), Op(op), T(t) {}
+public:
// FIXME: We probably need to make this out-of-line to avoid redundant
// generation of virtual functions.
- QualType getType(ASTContext& C) const { return T; }
+ QualType getType() const override { return T; }
BinaryOperator::Opcode getOpcode() const { return Op; }
- void dumpToStream(raw_ostream &os) const;
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr *SE) {
+ Kind k = SE->getKind();
+ return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
+ }
+};
+
+/// \brief Represents a symbolic expression like 'x' + 3.
+class SymIntExpr : public BinarySymExpr {
+ const SymExpr *LHS;
+ const llvm::APSInt& RHS;
+
+public:
+ SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
+ const llvm::APSInt& rhs, QualType t)
+ : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {}
+
+ void dumpToStream(raw_ostream &os) const override;
const SymExpr *getLHS() const { return LHS; }
const llvm::APSInt &getRHS() const { return RHS; }
static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
BinaryOperator::Opcode op, const llvm::APSInt& rhs,
QualType t) {
- ID.AddInteger((unsigned) SymIntKind);
+ ID.AddInteger((unsigned) SymIntExprKind);
ID.AddPointer(lhs);
ID.AddInteger(op);
ID.AddPointer(&rhs);
ID.Add(t);
}
- void Profile(llvm::FoldingSetNodeID& ID) {
- Profile(ID, LHS, Op, RHS, T);
+ void Profile(llvm::FoldingSetNodeID& ID) override {
+ Profile(ID, LHS, getOpcode(), RHS, getType());
+ }
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymIntExprKind;
+ }
+};
+
+/// \brief Represents a symbolic expression like 3 - 'x'.
+class IntSymExpr : public BinarySymExpr {
+ const llvm::APSInt& LHS;
+ const SymExpr *RHS;
+
+public:
+ IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op,
+ const SymExpr *rhs, QualType t)
+ : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {}
+
+ void dumpToStream(raw_ostream &os) const override;
+
+ const SymExpr *getRHS() const { return RHS; }
+ const llvm::APSInt &getLHS() const { return LHS; }
+
+ static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
+ BinaryOperator::Opcode op, const SymExpr *rhs,
+ QualType t) {
+ ID.AddInteger((unsigned) IntSymExprKind);
+ ID.AddPointer(&lhs);
+ ID.AddInteger(op);
+ ID.AddPointer(rhs);
+ ID.Add(t);
+ }
+
+ void Profile(llvm::FoldingSetNodeID& ID) override {
+ Profile(ID, LHS, getOpcode(), RHS, getType());
}
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == SymIntKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == IntSymExprKind;
}
};
-// SymSymExpr - Represents symbolic expression like 'x' + 'y'.
-class SymSymExpr : public SymExpr {
+/// \brief Represents a symbolic expression like 'x' + 'y'.
+class SymSymExpr : public BinarySymExpr {
const SymExpr *LHS;
- BinaryOperator::Opcode Op;
const SymExpr *RHS;
- QualType T;
public:
SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
QualType t)
- : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {}
+ : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {}
- BinaryOperator::Opcode getOpcode() const { return Op; }
const SymExpr *getLHS() const { return LHS; }
const SymExpr *getRHS() const { return RHS; }
- // FIXME: We probably need to make this out-of-line to avoid redundant
- // generation of virtual functions.
- QualType getType(ASTContext& C) const { return T; }
-
- void dumpToStream(raw_ostream &os) const;
+ void dumpToStream(raw_ostream &os) const override;
static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
- ID.AddInteger((unsigned) SymSymKind);
+ ID.AddInteger((unsigned) SymSymExprKind);
ID.AddPointer(lhs);
ID.AddInteger(op);
ID.AddPointer(rhs);
ID.Add(t);
}
- void Profile(llvm::FoldingSetNodeID& ID) {
- Profile(ID, LHS, Op, RHS, T);
+ void Profile(llvm::FoldingSetNodeID& ID) override {
+ Profile(ID, LHS, getOpcode(), RHS, getType());
}
// Implement isa<T> support.
- static inline bool classof(const SymExpr* SE) {
- return SE->getKind() == SymSymKind;
+ static inline bool classof(const SymExpr *SE) {
+ return SE->getKind() == SymSymExprKind;
}
};
class SymbolManager {
typedef llvm::FoldingSet<SymExpr> DataSetTy;
+ typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
+
DataSetTy DataSet;
+ /// Stores the extra dependencies between symbols: the data should be kept
+ /// alive as long as the key is live.
+ SymbolDependTy SymbolDependencies;
unsigned SymbolCounter;
llvm::BumpPtrAllocator& BPAlloc;
BasicValueFactory &BV;
- ASTContext& Ctx;
+ ASTContext &Ctx;
public:
- SymbolManager(ASTContext& ctx, BasicValueFactory &bv,
+ SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
llvm::BumpPtrAllocator& bpalloc)
- : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
+ : SymbolDependencies(16), SymbolCounter(0),
+ BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
~SymbolManager();
static bool canSymbolicate(QualType T);
- /// Make a unique symbol for MemRegion R according to its kind.
- const SymbolRegionValue* getRegionValueSymbol(const TypedRegion* R);
+ /// \brief Make a unique symbol for MemRegion R according to its kind.
+ const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
- const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T,
- unsigned VisitCount,
- const void* SymbolTag = 0);
+ const SymbolConjured* conjureSymbol(const Stmt *E,
+ const LocationContext *LCtx,
+ QualType T,
+ unsigned VisitCount,
+ const void *SymbolTag = nullptr);
- const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount,
- const void* SymbolTag = 0) {
- return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag);
+ const SymbolConjured* conjureSymbol(const Expr *E,
+ const LocationContext *LCtx,
+ unsigned VisitCount,
+ const void *SymbolTag = nullptr) {
+ return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
}
const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
- const TypedRegion *R);
+ const TypedValueRegion *R);
const SymbolExtent *getExtentSymbol(const SubRegion *R);
- const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S,
+ /// \brief Creates a metadata symbol associated with a specific region.
+ ///
+ /// VisitCount can be used to differentiate regions corresponding to
+ /// different loop iterations, thus, making the symbol path-dependent.
+ const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
QualType T, unsigned VisitCount,
- const void* SymbolTag = 0);
+ const void *SymbolTag = nullptr);
+
+ const SymbolCast* getCastSymbol(const SymExpr *Operand,
+ QualType From, QualType To);
const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
const llvm::APSInt& rhs, QualType t);
return getSymIntExpr(&lhs, op, rhs, t);
}
+ const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
+ BinaryOperator::Opcode op,
+ const SymExpr *rhs, QualType t);
+
const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
const SymExpr *rhs, QualType t);
QualType getType(const SymExpr *SE) const {
- return SE->getType(Ctx);
+ return SE->getType();
}
+ /// \brief Add artificial symbol dependency.
+ ///
+ /// The dependent symbol should stay alive as long as the primary is alive.
+ void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
+
+ const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
+
ASTContext &getContext() { return Ctx; }
BasicValueFactory &getBasicVals() { return BV; }
};
+/// \brief A class responsible for cleaning up unused symbols.
class SymbolReaper {
- typedef llvm::DenseSet<SymbolRef> SetTy;
+ enum SymbolStatus {
+ NotProcessed,
+ HaveMarkedDependents
+ };
- SetTy TheLiving;
- SetTy MetadataInUse;
- SetTy TheDead;
- const LocationContext *LCtx;
+ typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
+ typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
+ typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
+
+ SymbolMapTy TheLiving;
+ SymbolSetTy MetadataInUse;
+ SymbolSetTy TheDead;
+
+ RegionSetTy RegionRoots;
+
+ const StackFrameContext *LCtx;
const Stmt *Loc;
SymbolManager& SymMgr;
+ StoreRef reapedStore;
+ llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
public:
- SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr)
- : LCtx(ctx), Loc(s), SymMgr(symmgr) {}
-
- ~SymbolReaper() {}
+ /// \brief Construct a reaper object, which removes everything which is not
+ /// live before we execute statement s in the given location context.
+ ///
+ /// If the statement is NULL, everything is this and parent contexts is
+ /// considered live.
+ /// If the stack frame context is NULL, everything on stack is considered
+ /// dead.
+ SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
+ StoreManager &storeMgr)
+ : LCtx(Ctx), Loc(s), SymMgr(symmgr),
+ reapedStore(nullptr, storeMgr) {}
const LocationContext *getLocationContext() const { return LCtx; }
- const Stmt *getCurrentStatement() const { return Loc; }
bool isLive(SymbolRef sym);
- bool isLive(const Stmt *ExprVal) const;
- bool isLive(const VarRegion *VR) const;
-
- // markLive - Unconditionally marks a symbol as live. This should never be
- // used by checkers, only by the state infrastructure such as the store and
- // environment. Checkers should instead use metadata symbols and markInUse.
+ bool isLiveRegion(const MemRegion *region);
+ bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
+ bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
+
+ /// \brief Unconditionally marks a symbol as live.
+ ///
+ /// This should never be
+ /// used by checkers, only by the state infrastructure such as the store and
+ /// environment. Checkers should instead use metadata symbols and markInUse.
void markLive(SymbolRef sym);
- // markInUse - Marks a symbol as important to a checker. For metadata symbols,
- // this will keep the symbol alive as long as its associated region is also
- // live. For other symbols, this has no effect; checkers are not permitted
- // to influence the life of other symbols. This should be used before any
- // symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
+ /// \brief Marks a symbol as important to a checker.
+ ///
+ /// For metadata symbols,
+ /// this will keep the symbol alive as long as its associated region is also
+ /// live. For other symbols, this has no effect; checkers are not permitted
+ /// to influence the life of other symbols. This should be used before any
+ /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
void markInUse(SymbolRef sym);
- // maybeDead - If a symbol is known to be live, marks the symbol as live.
- // Otherwise, if the symbol cannot be proven live, it is marked as dead.
- // Returns true if the symbol is dead, false if live.
+ /// \brief If a symbol is known to be live, marks the symbol as live.
+ ///
+ /// Otherwise, if the symbol cannot be proven live, it is marked as dead.
+ /// Returns true if the symbol is dead, false if live.
bool maybeDead(SymbolRef sym);
- typedef SetTy::const_iterator dead_iterator;
+ typedef SymbolSetTy::const_iterator dead_iterator;
dead_iterator dead_begin() const { return TheDead.begin(); }
dead_iterator dead_end() const { return TheDead.end(); }
bool hasDeadSymbols() const {
return !TheDead.empty();
}
-
- /// isDead - Returns whether or not a symbol has been confirmed dead. This
- /// should only be called once all marking of dead symbols has completed.
- /// (For checkers, this means only in the evalDeadSymbols callback.)
+
+ typedef RegionSetTy::const_iterator region_iterator;
+ region_iterator region_begin() const { return RegionRoots.begin(); }
+ region_iterator region_end() const { return RegionRoots.end(); }
+
+ /// \brief Returns whether or not a symbol has been confirmed dead.
+ ///
+ /// This should only be called once all marking of dead symbols has completed.
+ /// (For checkers, this means only in the evalDeadSymbols callback.)
bool isDead(SymbolRef sym) const {
return TheDead.count(sym);
}
+
+ void markLive(const MemRegion *region);
+ void markElementIndicesLive(const MemRegion *region);
+
+ /// \brief Set to the value of the symbolic store after
+ /// StoreManager::removeDeadBindings has been called.
+ void setReapedStore(StoreRef st) { reapedStore = st; }
+
+private:
+ /// Mark the symbols dependent on the input symbol as live.
+ void markDependentsLive(SymbolRef sym);
};
class SymbolVisitor {
+protected:
+ ~SymbolVisitor() = default;
+
public:
- // VisitSymbol - A visitor method invoked by
- // GRStateManager::scanReachableSymbols. The method returns \c true if
- // symbols should continue be scanned and \c false otherwise.
+ SymbolVisitor() = default;
+ SymbolVisitor(const SymbolVisitor &) = default;
+ SymbolVisitor(SymbolVisitor &&) {}
+
+ /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
+ ///
+ /// The method returns \c true if symbols should continue be scanned and \c
+ /// false otherwise.
virtual bool VisitSymbol(SymbolRef sym) = 0;
- virtual ~SymbolVisitor();
+ virtual bool VisitMemRegion(const MemRegion *region) { return true; }
};
} // end GR namespace
} // end clang namespace
namespace llvm {
-static inline raw_ostream& operator<<(raw_ostream& os,
- const clang::ento::SymExpr *SE) {
+static inline raw_ostream &operator<<(raw_ostream &os,
+ const clang::ento::SymExpr *SE) {
SE->dumpToStream(os);
return os;
}
projects / clang / blobdiff