blob: 79202da545ac3a5764e80f38535d72c854c17d57 [file] [log] [blame]
Ted Kremeneka90ccfe2008-01-31 19:34:24 +00001//== RValues.h - Abstract RValues for Path-Sens. Value Tracking -*- C++ -*--==//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This files defines RValue, LValue, and NonLValue, classes that represent
11// abstract r-values for use with path-sensitive value tracking.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_ANALYSIS_RVALUE_H
16#define LLVM_CLANG_ANALYSIS_RVALUE_H
17
18// FIXME: reduce the number of includes.
19
20#include "clang/Analysis/PathSensitive/GREngine.h"
21#include "clang/AST/Expr.h"
22#include "clang/AST/Decl.h"
23#include "clang/AST/ASTContext.h"
24#include "clang/Analysis/Analyses/LiveVariables.h"
25
26#include "llvm/Support/Casting.h"
27#include "llvm/Support/DataTypes.h"
28#include "llvm/ADT/APSInt.h"
29#include "llvm/ADT/FoldingSet.h"
30#include "llvm/ADT/ImmutableMap.h"
31#include "llvm/ADT/SmallVector.h"
32#include "llvm/ADT/SmallPtrSet.h"
33#include "llvm/Support/Allocator.h"
34#include "llvm/Support/Compiler.h"
35#include "llvm/Support/Streams.h"
36
37#include <functional>
38
39//==------------------------------------------------------------------------==//
40// RValue "management" data structures.
41//==------------------------------------------------------------------------==//
42
43namespace clang {
44
45class SymbolID {
46 unsigned Data;
47public:
48 SymbolID() : Data(~0) {}
49 SymbolID(unsigned x) : Data(x) {}
50
51 bool isInitialized() const { return Data != (unsigned) ~0; }
52 operator unsigned() const { assert (isInitialized()); return Data; }
53};
54
55class SymbolData {
56 uintptr_t Data;
57public:
58 enum Kind { ParmKind = 0x0, Mask = 0x3 };
59
60 SymbolData(ParmVarDecl* D)
61 : Data(reinterpret_cast<uintptr_t>(D) | ParmKind) {}
62
63 inline Kind getKind() const { return (Kind) (Data & Mask); }
64 inline void* getPtr() const { return reinterpret_cast<void*>(Data & ~Mask); }
65 inline bool operator==(const SymbolData& R) const { return Data == R.Data; }
66};
67
68class SymbolManager {
69 std::vector<SymbolData> SymbolToData;
70
71 typedef llvm::DenseMap<void*,SymbolID> MapTy;
72 MapTy DataToSymbol;
73
74public:
75 SymbolManager();
76 ~SymbolManager();
77
78 SymbolData getSymbolData(SymbolID id) const {
79 assert (id < SymbolToData.size());
80 return SymbolToData[id];
81 }
82
83 SymbolID getSymbol(ParmVarDecl* D);
84};
85
86class ValueManager {
87 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> >
88 APSIntSetTy;
89
90 ASTContext& Ctx;
91 APSIntSetTy APSIntSet;
92 llvm::BumpPtrAllocator BPAlloc;
93
94public:
95 ValueManager(ASTContext& ctx) : Ctx(ctx) {}
96 ~ValueManager();
97
98 ASTContext& getContext() const { return Ctx; }
99 llvm::APSInt& getValue(const llvm::APSInt& X);
100 llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
101 llvm::APSInt& getValue(uint64_t X, QualType T,
102 SourceLocation Loc = SourceLocation());
103};
104
105//==------------------------------------------------------------------------==//
106// Base RValue types.
107//==------------------------------------------------------------------------==//
108
109class RValue {
110public:
111 enum BaseKind { LValueKind=0x0,
112 NonLValueKind=0x1,
113 UninitializedKind=0x2,
114 InvalidKind=0x3 };
115
116 enum { BaseBits = 2,
117 BaseMask = 0x3 };
118
119private:
120 void* Data;
121 unsigned Kind;
122
123protected:
124 RValue(const void* d, bool isLValue, unsigned ValKind)
125 : Data(const_cast<void*>(d)),
126 Kind((isLValue ? LValueKind : NonLValueKind) | (ValKind << BaseBits)) {}
127
128 explicit RValue(BaseKind k)
129 : Data(0), Kind(k) {}
130
131 void* getRawPtr() const {
132 return reinterpret_cast<void*>(Data);
133 }
134
135public:
136 ~RValue() {};
137
138 RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
139
140 unsigned getRawKind() const { return Kind; }
141 BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
142 unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
143
144 void Profile(llvm::FoldingSetNodeID& ID) const {
145 ID.AddInteger((unsigned) getRawKind());
146 ID.AddPointer(reinterpret_cast<void*>(Data));
147 }
148
149 bool operator==(const RValue& RHS) const {
150 return getRawKind() == RHS.getRawKind() && Data == RHS.Data;
151 }
152
153 static RValue GetSymbolValue(SymbolManager& SymMgr, ParmVarDecl *D);
154
155 inline bool isValid() const { return getRawKind() != InvalidKind; }
156 inline bool isInvalid() const { return getRawKind() == InvalidKind; }
157
158 void print(std::ostream& OS) const;
159 void print() const { print(*llvm::cerr.stream()); }
160
161 // Implement isa<T> support.
162 static inline bool classof(const RValue*) { return true; }
163};
164
165class InvalidValue : public RValue {
166public:
167 InvalidValue() : RValue(InvalidKind) {}
168
169 static inline bool classof(const RValue* V) {
170 return V->getBaseKind() == InvalidKind;
171 }
172};
173
174class UninitializedValue : public RValue {
175public:
176 UninitializedValue() : RValue(UninitializedKind) {}
177
178 static inline bool classof(const RValue* V) {
179 return V->getBaseKind() == UninitializedKind;
180 }
181};
182
183class NonLValue : public RValue {
184protected:
185 NonLValue(unsigned SubKind, const void* d) : RValue(d, false, SubKind) {}
186
187public:
188 void print(std::ostream& Out) const;
189
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000190 RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
191
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000192 // Arithmetic operators.
193 NonLValue Add(ValueManager& ValMgr, const NonLValue& RHS) const;
194 NonLValue Sub(ValueManager& ValMgr, const NonLValue& RHS) const;
195 NonLValue Mul(ValueManager& ValMgr, const NonLValue& RHS) const;
196 NonLValue Div(ValueManager& ValMgr, const NonLValue& RHS) const;
197 NonLValue Rem(ValueManager& ValMgr, const NonLValue& RHS) const;
198 NonLValue UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const;
Ted Kremenekc5d3b4c2008-02-04 16:58:30 +0000199 NonLValue BitwiseComplement(ValueManager& ValMgr) const;
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000200
201 // Equality operators.
202 NonLValue EQ(ValueManager& ValMgr, const NonLValue& RHS) const;
203 NonLValue NE(ValueManager& ValMgr, const NonLValue& RHS) const;
204
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000205
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000206 // Utility methods to create NonLValues.
207 static NonLValue GetValue(ValueManager& ValMgr, uint64_t X, QualType T,
208 SourceLocation Loc = SourceLocation());
209
210 static NonLValue GetValue(ValueManager& ValMgr, IntegerLiteral* I);
211
212 static inline NonLValue GetIntTruthValue(ValueManager& ValMgr, bool X) {
213 return GetValue(ValMgr, X ? 1U : 0U, ValMgr.getContext().IntTy);
214 }
215
216 // Implement isa<T> support.
217 static inline bool classof(const RValue* V) {
218 return V->getBaseKind() >= NonLValueKind;
219 }
220};
221
222class LValue : public RValue {
223protected:
Ted Kremenek516f91b2008-01-31 22:17:03 +0000224 LValue(unsigned SubKind, const void* D) : RValue(const_cast<void*>(D),
225 true, SubKind) {}
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000226
227public:
228 void print(std::ostream& Out) const;
229
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000230 RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
231
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000232 // Equality operators.
233 NonLValue EQ(ValueManager& ValMgr, const LValue& RHS) const;
234 NonLValue NE(ValueManager& ValMgr, const LValue& RHS) const;
235
236 // Implement isa<T> support.
237 static inline bool classof(const RValue* V) {
238 return V->getBaseKind() == LValueKind;
239 }
240};
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000241
242//==------------------------------------------------------------------------==//
243// Subclasses of NonLValue.
244//==------------------------------------------------------------------------==//
245
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000246enum NonLValueKind { SymbolicNonLValueKind, ConcreteIntKind, NumNonLValueKind };
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000247
248class SymbolicNonLValue : public NonLValue {
249public:
250 SymbolicNonLValue(unsigned SymID)
251 : NonLValue(SymbolicNonLValueKind,
252 reinterpret_cast<void*>((uintptr_t) SymID)) {}
253
254 SymbolID getSymbolID() const {
255 return (SymbolID) reinterpret_cast<uintptr_t>(getRawPtr());
256 }
257
258 static inline bool classof(const RValue* V) {
259 return V->getSubKind() == SymbolicNonLValueKind;
260 }
261};
262
263class ConcreteInt : public NonLValue {
264public:
265 ConcreteInt(const llvm::APSInt& V) : NonLValue(ConcreteIntKind, &V) {}
266
267 const llvm::APSInt& getValue() const {
268 return *static_cast<llvm::APSInt*>(getRawPtr());
269 }
270
271 // Arithmetic operators.
272
273 ConcreteInt Add(ValueManager& ValMgr, const ConcreteInt& V) const {
274 return ValMgr.getValue(getValue() + V.getValue());
275 }
276
277 ConcreteInt Sub(ValueManager& ValMgr, const ConcreteInt& V) const {
278 return ValMgr.getValue(getValue() - V.getValue());
279 }
280
281 ConcreteInt Mul(ValueManager& ValMgr, const ConcreteInt& V) const {
282 return ValMgr.getValue(getValue() * V.getValue());
283 }
284
285 ConcreteInt Div(ValueManager& ValMgr, const ConcreteInt& V) const {
286 return ValMgr.getValue(getValue() / V.getValue());
287 }
288
289 ConcreteInt Rem(ValueManager& ValMgr, const ConcreteInt& V) const {
290 return ValMgr.getValue(getValue() % V.getValue());
291 }
292
293 ConcreteInt UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const {
294 assert (U->getType() == U->getSubExpr()->getType());
295 assert (U->getType()->isIntegerType());
296 return ValMgr.getValue(-getValue());
297 }
298
Ted Kremenekc5d3b4c2008-02-04 16:58:30 +0000299 ConcreteInt BitwiseComplement(ValueManager& ValMgr) const {
300 return ValMgr.getValue(~getValue());
301 }
302
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000303 // Casting.
304
305 ConcreteInt Cast(ValueManager& ValMgr, Expr* CastExpr) const {
306 assert (CastExpr->getType()->isIntegerType());
307
308 llvm::APSInt X(getValue());
309 X.extOrTrunc(ValMgr.getContext().getTypeSize(CastExpr->getType(),
310 CastExpr->getLocStart()));
311 return ValMgr.getValue(X);
312 }
313
314 // Equality operators.
315
316 ConcreteInt EQ(ValueManager& ValMgr, const ConcreteInt& V) const {
317 const llvm::APSInt& Val = getValue();
318 return ValMgr.getValue(Val == V.getValue() ? 1U : 0U,
319 Val.getBitWidth(), Val.isUnsigned());
320 }
321
322 ConcreteInt NE(ValueManager& ValMgr, const ConcreteInt& V) const {
323 const llvm::APSInt& Val = getValue();
324 return ValMgr.getValue(Val != V.getValue() ? 1U : 0U,
325 Val.getBitWidth(), Val.isUnsigned());
326 }
327
328 // Implement isa<T> support.
329 static inline bool classof(const RValue* V) {
330 return V->getSubKind() == ConcreteIntKind;
331 }
332};
Ted Kremenek516f91b2008-01-31 22:17:03 +0000333
334//==------------------------------------------------------------------------==//
335// Subclasses of LValue.
336//==------------------------------------------------------------------------==//
337
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000338enum LValueKind { SymbolicLValueKind, LValueDeclKind, ConcreteIntLValueKind,
339 NumLValueKind };
340
Ted Kremenek516f91b2008-01-31 22:17:03 +0000341class SymbolicLValue : public LValue {
342public:
343 SymbolicLValue(unsigned SymID)
344 : LValue(SymbolicLValueKind, reinterpret_cast<void*>((uintptr_t) SymID)) {}
345
346 SymbolID getSymbolID() const {
347 return (SymbolID) reinterpret_cast<uintptr_t>(getRawPtr());
348 }
349
350 static inline bool classof(const RValue* V) {
351 return V->getSubKind() == SymbolicLValueKind;
352 }
353};
354
355class LValueDecl : public LValue {
356public:
357 LValueDecl(const ValueDecl* vd) : LValue(LValueDeclKind,vd) {}
358
359 ValueDecl* getDecl() const {
360 return static_cast<ValueDecl*>(getRawPtr());
361 }
362
363 inline bool operator==(const LValueDecl& R) const {
364 return getDecl() == R.getDecl();
365 }
366
367 inline bool operator!=(const LValueDecl& R) const {
368 return getDecl() != R.getDecl();
369 }
370
371 // Implement isa<T> support.
372 static inline bool classof(const RValue* V) {
373 return V->getSubKind() == LValueDeclKind;
374 }
375};
376
377class ConcreteIntLValue : public LValue {
378public:
379 ConcreteIntLValue(const llvm::APSInt& V) : LValue(ConcreteIntLValueKind, &V) {}
380
381 const llvm::APSInt& getValue() const {
382 return *static_cast<llvm::APSInt*>(getRawPtr());
383 }
384
385 // Arithmetic operators.
386
387 ConcreteIntLValue Add(ValueManager& ValMgr, const ConcreteInt& V) const {
388 return ValMgr.getValue(getValue() + V.getValue());
389 }
390
391 ConcreteIntLValue Sub(ValueManager& ValMgr, const ConcreteInt& V) const {
392 return ValMgr.getValue(getValue() - V.getValue());
393 }
394
395 // Equality operators.
396
397 ConcreteInt EQ(ValueManager& ValMgr, const ConcreteIntLValue& V) const {
398 const llvm::APSInt& Val = getValue();
399 return ValMgr.getValue(Val == V.getValue() ? 1U : 0U,
400 Val.getBitWidth(), Val.isUnsigned());
401 }
402
403 ConcreteInt NE(ValueManager& ValMgr, const ConcreteIntLValue& V) const {
404 const llvm::APSInt& Val = getValue();
405 return ValMgr.getValue(Val != V.getValue() ? 1U : 0U,
406 Val.getBitWidth(), Val.isUnsigned());
407 }
408
409 // Implement isa<T> support.
410 static inline bool classof(const RValue* V) {
411 return V->getSubKind() == ConcreteIntLValueKind;
412 }
413};
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000414
415} // end clang namespace
416
417//==------------------------------------------------------------------------==//
418// Casting machinery to get cast<> and dyn_cast<> working with SymbolData.
419//==------------------------------------------------------------------------==//
420
421namespace llvm {
422
423template<> inline bool
424isa<clang::ParmVarDecl,clang::SymbolData>(const clang::SymbolData& V) {
425 return V.getKind() == clang::SymbolData::ParmKind;
426}
427
428template<> struct cast_retty_impl<clang::ParmVarDecl,clang::SymbolData> {
429 typedef const clang::ParmVarDecl* ret_type;
430};
431
432template<> struct simplify_type<clang::SymbolData> {
433 typedef void* SimpleType;
434 static inline SimpleType getSimplifiedValue(const clang::SymbolData &V) {
435 return V.getPtr();
436 }
437};
438
439} // end llvm namespace
440
441#endif