summaryrefslogtreecommitdiffstats
path: root/include/clang/Analysis/PathSensitive/SymbolManager.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/clang/Analysis/PathSensitive/SymbolManager.h')
-rw-r--r--include/clang/Analysis/PathSensitive/SymbolManager.h329
1 files changed, 329 insertions, 0 deletions
diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h
new file mode 100644
index 0000000..d424526
--- /dev/null
+++ b/include/clang/Analysis/PathSensitive/SymbolManager.h
@@ -0,0 +1,329 @@
+//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines SymbolManager, a class that manages symbolic values
+// created for use by GRExprEngine and related classes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_SYMMGR_H
+#define LLVM_CLANG_ANALYSIS_SYMMGR_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+#include "clang/Analysis/Analyses/LiveVariables.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ImmutableSet.h"
+
+namespace llvm {
+ class raw_ostream;
+}
+
+namespace clang {
+ class MemRegion;
+ class ASTContext;
+ class BasicValueFactory;
+}
+
+namespace clang {
+
+class SymExpr : public llvm::FoldingSetNode {
+public:
+ enum Kind { BEGIN_SYMBOLS, RegionValueKind, ConjuredKind, END_SYMBOLS,
+ SymIntKind, SymSymKind };
+private:
+ Kind K;
+
+protected:
+ SymExpr(Kind k) : K(k) {}
+
+public:
+ virtual ~SymExpr() {}
+
+ Kind getKind() const { return K; }
+
+ virtual QualType getType(ASTContext&) const = 0;
+ virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr*) { return true; }
+};
+
+typedef unsigned SymbolID;
+
+class SymbolData : public SymExpr {
+private:
+ const SymbolID Sym;
+
+protected:
+ SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
+
+public:
+ virtual ~SymbolData() {}
+
+ SymbolID getSymbolID() const { return Sym; }
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr* SE) {
+ Kind k = SE->getKind();
+ return k > BEGIN_SYMBOLS && k < END_SYMBOLS;
+ }
+};
+
+typedef const SymbolData* SymbolRef;
+
+class SymbolRegionValue : public SymbolData {
+ const MemRegion *R;
+public:
+ SymbolRegionValue(SymbolID sym, const MemRegion *r)
+ : SymbolData(RegionValueKind, sym), R(r) {}
+
+ const MemRegion* getRegion() const { return R; }
+
+ static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion* R) {
+ profile.AddInteger((unsigned) RegionValueKind);
+ profile.AddPointer(R);
+ }
+
+ virtual void Profile(llvm::FoldingSetNodeID& profile) {
+ Profile(profile, R);
+ }
+
+ QualType getType(ASTContext&) const;
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr* SE) {
+ return SE->getKind() == RegionValueKind;
+ }
+};
+
+class SymbolConjured : public SymbolData {
+ const Stmt* S;
+ QualType T;
+ unsigned Count;
+ 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) {}
+
+ const Stmt* getStmt() const { return S; }
+ unsigned getCount() const { return Count; }
+ const void* getTag() const { return SymbolTag; }
+
+ QualType getType(ASTContext&) const;
+
+ static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S,
+ QualType T, unsigned Count, const void* SymbolTag) {
+ profile.AddInteger((unsigned) ConjuredKind);
+ profile.AddPointer(S);
+ profile.Add(T);
+ profile.AddInteger(Count);
+ profile.AddPointer(SymbolTag);
+ }
+
+ virtual void Profile(llvm::FoldingSetNodeID& profile) {
+ Profile(profile, S, T, Count, SymbolTag);
+ }
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr* SE) {
+ return SE->getKind() == ConjuredKind;
+ }
+};
+
+// SymIntExpr - Represents symbolic expression like 'x' + 3.
+class SymIntExpr : public SymExpr {
+ const SymExpr *LHS;
+ 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) {}
+
+ // FIXME: We probably need to make this out-of-line to avoid redundant
+ // generation of virtual functions.
+ QualType getType(ASTContext& C) const { return T; }
+
+ BinaryOperator::Opcode getOpcode() const { return Op; }
+
+ 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.AddPointer(lhs);
+ ID.AddInteger(op);
+ ID.AddPointer(&rhs);
+ ID.Add(t);
+ }
+
+ void Profile(llvm::FoldingSetNodeID& ID) {
+ Profile(ID, LHS, Op, RHS, T);
+ }
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr* SE) {
+ return SE->getKind() == SymIntKind;
+ }
+};
+
+// SymSymExpr - Represents symbolic expression like 'x' + 'y'.
+class SymSymExpr : public SymExpr {
+ 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) {}
+
+ 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; }
+
+ static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
+ BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
+ ID.AddInteger((unsigned) SymSymKind);
+ ID.AddPointer(lhs);
+ ID.AddInteger(op);
+ ID.AddPointer(rhs);
+ ID.Add(t);
+ }
+
+ void Profile(llvm::FoldingSetNodeID& ID) {
+ Profile(ID, LHS, Op, RHS, T);
+ }
+
+ // Implement isa<T> support.
+ static inline bool classof(const SymExpr* SE) {
+ return SE->getKind() == SymSymKind;
+ }
+};
+
+class SymbolManager {
+ typedef llvm::FoldingSet<SymExpr> DataSetTy;
+ DataSetTy DataSet;
+ unsigned SymbolCounter;
+ llvm::BumpPtrAllocator& BPAlloc;
+ BasicValueFactory &BV;
+ ASTContext& Ctx;
+
+public:
+ SymbolManager(ASTContext& ctx, BasicValueFactory &bv,
+ llvm::BumpPtrAllocator& bpalloc)
+ : 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 MemRegion* R);
+ const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T,
+ unsigned VisitCount,
+ const void* SymbolTag = 0);
+
+ const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount,
+ const void* SymbolTag = 0) {
+ return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag);
+ }
+
+ const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
+ const llvm::APSInt& rhs, QualType t);
+
+ const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
+ const llvm::APSInt& rhs, QualType t) {
+ return getSymIntExpr(&lhs, op, rhs, 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);
+ }
+
+ ASTContext &getContext() { return Ctx; }
+ BasicValueFactory &getBasicVals() { return BV; }
+};
+
+class SymbolReaper {
+ typedef llvm::ImmutableSet<SymbolRef> SetTy;
+ typedef SetTy::Factory FactoryTy;
+
+ FactoryTy F;
+ SetTy TheLiving;
+ SetTy TheDead;
+ LiveVariables& Liveness;
+ SymbolManager& SymMgr;
+
+public:
+ SymbolReaper(LiveVariables& liveness, SymbolManager& symmgr)
+ : TheLiving(F.GetEmptySet()), TheDead(F.GetEmptySet()),
+ Liveness(liveness), SymMgr(symmgr) {}
+
+ bool isLive(SymbolRef sym);
+
+ bool isLive(const Stmt* Loc, const Stmt* ExprVal) const {
+ return Liveness.isLive(Loc, ExprVal);
+ }
+
+ bool isLive(const Stmt* Loc, const VarDecl* VD) const {
+ return Liveness.isLive(Loc, VD);
+ }
+
+ void markLive(SymbolRef sym);
+ bool maybeDead(SymbolRef sym);
+
+ typedef SetTy::iterator dead_iterator;
+ dead_iterator dead_begin() const { return TheDead.begin(); }
+ dead_iterator dead_end() const { return TheDead.end(); }
+
+ bool hasDeadSymbols() const {
+ return !TheDead.isEmpty();
+ }
+};
+
+class SymbolVisitor {
+public:
+ // VisitSymbol - A visitor method invoked by
+ // GRStateManager::scanReachableSymbols. The method returns \c true if
+ // symbols should continue be scanned and \c false otherwise.
+ virtual bool VisitSymbol(SymbolRef sym) = 0;
+ virtual ~SymbolVisitor();
+};
+
+} // end clang namespace
+
+namespace llvm {
+ llvm::raw_ostream& operator<<(llvm::raw_ostream& Out,
+ const clang::SymExpr *SE);
+}
+namespace std {
+ std::ostream& operator<<(std::ostream& Out,
+ const clang::SymExpr *SE);
+}
+
+#endif
OpenPOWER on IntegriCloud