1 //== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines SymbolManager, a class that manages symbolic values
11 // created for use by GRExprEngine and related classes.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_ANALYSIS_SYMMGR_H
16 #define LLVM_CLANG_ANALYSIS_SYMMGR_H
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/Analysis/AnalysisContext.h"
21 #include "llvm/Support/DataTypes.h"
22 #include "llvm/ADT/FoldingSet.h"
23 #include "llvm/ADT/DenseSet.h"
26 class BumpPtrAllocator
;
32 class BasicValueFactory
;
37 class StackFrameContext
;
39 class SymExpr
: public llvm::FoldingSetNode
{
41 enum Kind
{ BEGIN_SYMBOLS
,
42 RegionValueKind
, ConjuredKind
, DerivedKind
, ExtentKind
,
45 SymIntKind
, SymSymKind
};
50 SymExpr(Kind k
) : K(k
) {}
55 Kind
getKind() const { return K
; }
59 virtual void dumpToStream(llvm::raw_ostream
&os
) const = 0;
61 virtual QualType
getType(ASTContext
&) const = 0;
62 virtual void Profile(llvm::FoldingSetNodeID
& profile
) = 0;
64 // Implement isa<T> support.
65 static inline bool classof(const SymExpr
*) { return true; }
68 typedef unsigned SymbolID
;
70 class SymbolData
: public SymExpr
{
75 SymbolData(Kind k
, SymbolID sym
) : SymExpr(k
), Sym(sym
) {}
78 virtual ~SymbolData() {}
80 SymbolID
getSymbolID() const { return Sym
; }
82 // Implement isa<T> support.
83 static inline bool classof(const SymExpr
* SE
) {
84 Kind k
= SE
->getKind();
85 return k
> BEGIN_SYMBOLS
&& k
< END_SYMBOLS
;
89 typedef const SymbolData
* SymbolRef
;
91 // A symbol representing the value of a MemRegion.
92 class SymbolRegionValue
: public SymbolData
{
96 SymbolRegionValue(SymbolID sym
, const TypedRegion
*r
)
97 : SymbolData(RegionValueKind
, sym
), R(r
) {}
99 const TypedRegion
* getRegion() const { return R
; }
101 static void Profile(llvm::FoldingSetNodeID
& profile
, const TypedRegion
* R
) {
102 profile
.AddInteger((unsigned) RegionValueKind
);
103 profile
.AddPointer(R
);
106 virtual void Profile(llvm::FoldingSetNodeID
& profile
) {
110 void dumpToStream(llvm::raw_ostream
&os
) const;
112 QualType
getType(ASTContext
&) const;
114 // Implement isa<T> support.
115 static inline bool classof(const SymExpr
* SE
) {
116 return SE
->getKind() == RegionValueKind
;
120 // A symbol representing the result of an expression.
121 class SymbolConjured
: public SymbolData
{
125 const void* SymbolTag
;
128 SymbolConjured(SymbolID sym
, const Stmt
* s
, QualType t
, unsigned count
,
129 const void* symbolTag
)
130 : SymbolData(ConjuredKind
, sym
), S(s
), T(t
), Count(count
),
131 SymbolTag(symbolTag
) {}
133 const Stmt
* getStmt() const { return S
; }
134 unsigned getCount() const { return Count
; }
135 const void* getTag() const { return SymbolTag
; }
137 QualType
getType(ASTContext
&) const;
139 void dumpToStream(llvm::raw_ostream
&os
) const;
141 static void Profile(llvm::FoldingSetNodeID
& profile
, const Stmt
* S
,
142 QualType T
, unsigned Count
, const void* SymbolTag
) {
143 profile
.AddInteger((unsigned) ConjuredKind
);
144 profile
.AddPointer(S
);
146 profile
.AddInteger(Count
);
147 profile
.AddPointer(SymbolTag
);
150 virtual void Profile(llvm::FoldingSetNodeID
& profile
) {
151 Profile(profile
, S
, T
, Count
, SymbolTag
);
154 // Implement isa<T> support.
155 static inline bool classof(const SymExpr
* SE
) {
156 return SE
->getKind() == ConjuredKind
;
160 // A symbol representing the value of a MemRegion whose parent region has
162 class SymbolDerived
: public SymbolData
{
163 SymbolRef parentSymbol
;
164 const TypedRegion
*R
;
167 SymbolDerived(SymbolID sym
, SymbolRef parent
, const TypedRegion
*r
)
168 : SymbolData(DerivedKind
, sym
), parentSymbol(parent
), R(r
) {}
170 SymbolRef
getParentSymbol() const { return parentSymbol
; }
171 const TypedRegion
*getRegion() const { return R
; }
173 QualType
getType(ASTContext
&) const;
175 void dumpToStream(llvm::raw_ostream
&os
) const;
177 static void Profile(llvm::FoldingSetNodeID
& profile
, SymbolRef parent
,
178 const TypedRegion
*r
) {
179 profile
.AddInteger((unsigned) DerivedKind
);
180 profile
.AddPointer(r
);
181 profile
.AddPointer(parent
);
184 virtual void Profile(llvm::FoldingSetNodeID
& profile
) {
185 Profile(profile
, parentSymbol
, R
);
188 // Implement isa<T> support.
189 static inline bool classof(const SymExpr
* SE
) {
190 return SE
->getKind() == DerivedKind
;
194 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
195 /// Clients should not ask the SymbolManager for a region's extent. Always use
196 /// SubRegion::getExtent instead -- the value returned may not be a symbol.
197 class SymbolExtent
: public SymbolData
{
201 SymbolExtent(SymbolID sym
, const SubRegion
*r
)
202 : SymbolData(ExtentKind
, sym
), R(r
) {}
204 const SubRegion
*getRegion() const { return R
; }
206 QualType
getType(ASTContext
&) const;
208 void dumpToStream(llvm::raw_ostream
&os
) const;
210 static void Profile(llvm::FoldingSetNodeID
& profile
, const SubRegion
*R
) {
211 profile
.AddInteger((unsigned) ExtentKind
);
212 profile
.AddPointer(R
);
215 virtual void Profile(llvm::FoldingSetNodeID
& profile
) {
219 // Implement isa<T> support.
220 static inline bool classof(const SymExpr
* SE
) {
221 return SE
->getKind() == ExtentKind
;
225 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
226 /// Metadata symbols remain live as long as they are marked as in use before
227 /// dead-symbol sweeping AND their associated regions are still alive.
228 /// Intended for use by checkers.
229 class SymbolMetadata
: public SymbolData
{
236 SymbolMetadata(SymbolID sym
, const MemRegion
* r
, const Stmt
* s
, QualType t
,
237 unsigned count
, const void* tag
)
238 : SymbolData(MetadataKind
, sym
), R(r
), S(s
), T(t
), Count(count
), Tag(tag
) {}
240 const MemRegion
*getRegion() const { return R
; }
241 const Stmt
* getStmt() const { return S
; }
242 unsigned getCount() const { return Count
; }
243 const void* getTag() const { return Tag
; }
245 QualType
getType(ASTContext
&) const;
247 void dumpToStream(llvm::raw_ostream
&os
) const;
249 static void Profile(llvm::FoldingSetNodeID
& profile
, const MemRegion
*R
,
250 const Stmt
*S
, QualType T
, unsigned Count
,
252 profile
.AddInteger((unsigned) MetadataKind
);
253 profile
.AddPointer(R
);
254 profile
.AddPointer(S
);
256 profile
.AddInteger(Count
);
257 profile
.AddPointer(Tag
);
260 virtual void Profile(llvm::FoldingSetNodeID
& profile
) {
261 Profile(profile
, R
, S
, T
, Count
, Tag
);
264 // Implement isa<T> support.
265 static inline bool classof(const SymExpr
* SE
) {
266 return SE
->getKind() == MetadataKind
;
270 // SymIntExpr - Represents symbolic expression like 'x' + 3.
271 class SymIntExpr
: public SymExpr
{
273 BinaryOperator::Opcode Op
;
274 const llvm::APSInt
& RHS
;
278 SymIntExpr(const SymExpr
*lhs
, BinaryOperator::Opcode op
,
279 const llvm::APSInt
& rhs
, QualType t
)
280 : SymExpr(SymIntKind
), LHS(lhs
), Op(op
), RHS(rhs
), T(t
) {}
282 // FIXME: We probably need to make this out-of-line to avoid redundant
283 // generation of virtual functions.
284 QualType
getType(ASTContext
& C
) const { return T
; }
286 BinaryOperator::Opcode
getOpcode() const { return Op
; }
288 void dumpToStream(llvm::raw_ostream
&os
) const;
290 const SymExpr
*getLHS() const { return LHS
; }
291 const llvm::APSInt
&getRHS() const { return RHS
; }
293 static void Profile(llvm::FoldingSetNodeID
& ID
, const SymExpr
*lhs
,
294 BinaryOperator::Opcode op
, const llvm::APSInt
& rhs
,
296 ID
.AddInteger((unsigned) SymIntKind
);
303 void Profile(llvm::FoldingSetNodeID
& ID
) {
304 Profile(ID
, LHS
, Op
, RHS
, T
);
307 // Implement isa<T> support.
308 static inline bool classof(const SymExpr
* SE
) {
309 return SE
->getKind() == SymIntKind
;
313 // SymSymExpr - Represents symbolic expression like 'x' + 'y'.
314 class SymSymExpr
: public SymExpr
{
316 BinaryOperator::Opcode Op
;
321 SymSymExpr(const SymExpr
*lhs
, BinaryOperator::Opcode op
, const SymExpr
*rhs
,
323 : SymExpr(SymSymKind
), LHS(lhs
), Op(op
), RHS(rhs
), T(t
) {}
325 BinaryOperator::Opcode
getOpcode() const { return Op
; }
326 const SymExpr
*getLHS() const { return LHS
; }
327 const SymExpr
*getRHS() const { return RHS
; }
329 // FIXME: We probably need to make this out-of-line to avoid redundant
330 // generation of virtual functions.
331 QualType
getType(ASTContext
& C
) const { return T
; }
333 void dumpToStream(llvm::raw_ostream
&os
) const;
335 static void Profile(llvm::FoldingSetNodeID
& ID
, const SymExpr
*lhs
,
336 BinaryOperator::Opcode op
, const SymExpr
*rhs
, QualType t
) {
337 ID
.AddInteger((unsigned) SymSymKind
);
344 void Profile(llvm::FoldingSetNodeID
& ID
) {
345 Profile(ID
, LHS
, Op
, RHS
, T
);
348 // Implement isa<T> support.
349 static inline bool classof(const SymExpr
* SE
) {
350 return SE
->getKind() == SymSymKind
;
354 class SymbolManager
{
355 typedef llvm::FoldingSet
<SymExpr
> DataSetTy
;
357 unsigned SymbolCounter
;
358 llvm::BumpPtrAllocator
& BPAlloc
;
359 BasicValueFactory
&BV
;
363 SymbolManager(ASTContext
& ctx
, BasicValueFactory
&bv
,
364 llvm::BumpPtrAllocator
& bpalloc
)
365 : SymbolCounter(0), BPAlloc(bpalloc
), BV(bv
), Ctx(ctx
) {}
369 static bool canSymbolicate(QualType T
);
371 /// Make a unique symbol for MemRegion R according to its kind.
372 const SymbolRegionValue
* getRegionValueSymbol(const TypedRegion
* R
);
374 const SymbolConjured
* getConjuredSymbol(const Stmt
* E
, QualType T
,
376 const void* SymbolTag
= 0);
378 const SymbolConjured
* getConjuredSymbol(const Expr
* E
, unsigned VisitCount
,
379 const void* SymbolTag
= 0) {
380 return getConjuredSymbol(E
, E
->getType(), VisitCount
, SymbolTag
);
383 const SymbolDerived
*getDerivedSymbol(SymbolRef parentSymbol
,
384 const TypedRegion
*R
);
386 const SymbolExtent
*getExtentSymbol(const SubRegion
*R
);
388 const SymbolMetadata
* getMetadataSymbol(const MemRegion
* R
, const Stmt
* S
,
389 QualType T
, unsigned VisitCount
,
390 const void* SymbolTag
= 0);
392 const SymIntExpr
*getSymIntExpr(const SymExpr
*lhs
, BinaryOperator::Opcode op
,
393 const llvm::APSInt
& rhs
, QualType t
);
395 const SymIntExpr
*getSymIntExpr(const SymExpr
&lhs
, BinaryOperator::Opcode op
,
396 const llvm::APSInt
& rhs
, QualType t
) {
397 return getSymIntExpr(&lhs
, op
, rhs
, t
);
400 const SymSymExpr
*getSymSymExpr(const SymExpr
*lhs
, BinaryOperator::Opcode op
,
401 const SymExpr
*rhs
, QualType t
);
403 QualType
getType(const SymExpr
*SE
) const {
404 return SE
->getType(Ctx
);
407 ASTContext
&getContext() { return Ctx
; }
408 BasicValueFactory
&getBasicVals() { return BV
; }
412 typedef llvm::DenseSet
<SymbolRef
> SetTy
;
417 const LocationContext
*LCtx
;
419 SymbolManager
& SymMgr
;
422 SymbolReaper(const LocationContext
*ctx
, const Stmt
*s
, SymbolManager
& symmgr
)
423 : LCtx(ctx
), Loc(s
), SymMgr(symmgr
) {}
427 const LocationContext
*getLocationContext() const { return LCtx
; }
428 const Stmt
*getCurrentStatement() const { return Loc
; }
430 bool isLive(SymbolRef sym
);
431 bool isLive(const Stmt
*ExprVal
) const;
432 bool isLive(const VarRegion
*VR
) const;
434 // markLive - Unconditionally marks a symbol as live. This should never be
435 // used by checkers, only by the state infrastructure such as the store and
436 // environment. Checkers should instead use metadata symbols and markInUse.
437 void markLive(SymbolRef sym
);
439 // markInUse - Marks a symbol as important to a checker. For metadata symbols,
440 // this will keep the symbol alive as long as its associated region is also
441 // live. For other symbols, this has no effect; checkers are not permitted
442 // to influence the life of other symbols. This should be used before any
443 // symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
444 void markInUse(SymbolRef sym
);
446 // maybeDead - If a symbol is known to be live, marks the symbol as live.
447 // Otherwise, if the symbol cannot be proven live, it is marked as dead.
448 // Returns true if the symbol is dead, false if live.
449 bool maybeDead(SymbolRef sym
);
451 typedef SetTy::const_iterator dead_iterator
;
452 dead_iterator
dead_begin() const { return TheDead
.begin(); }
453 dead_iterator
dead_end() const { return TheDead
.end(); }
455 bool hasDeadSymbols() const {
456 return !TheDead
.empty();
459 /// isDead - Returns whether or not a symbol has been confirmed dead. This
460 /// should only be called once all marking of dead symbols has completed.
461 /// (For checkers, this means only in the evalDeadSymbols callback.)
462 bool isDead(SymbolRef sym
) const {
463 return TheDead
.count(sym
);
467 class SymbolVisitor
{
469 // VisitSymbol - A visitor method invoked by
470 // GRStateManager::scanReachableSymbols. The method returns \c true if
471 // symbols should continue be scanned and \c false otherwise.
472 virtual bool VisitSymbol(SymbolRef sym
) = 0;
473 virtual ~SymbolVisitor();
476 } // end clang namespace
479 static inline llvm::raw_ostream
& operator<<(llvm::raw_ostream
& os
,
480 const clang::SymExpr
*SE
) {
481 SE
->dumpToStream(os
);
484 } // end llvm namespace