blob: ef7c82ecddbe469b1406db71fbf3a10f9802d2b7 [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//==------------------------------------------------------------------------==//
Ted Kremenek1fbdb022008-02-05 21:32:43 +000040// Values and ValueManager.
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000041//==------------------------------------------------------------------------==//
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; }
Ted Kremenek174aea42008-02-05 18:51:06 +000053
Ted Kremenek1fbdb022008-02-05 21:32:43 +000054 void Profile(llvm::FoldingSetNodeID& ID) const {
55 assert (isInitialized());
56 ID.AddInteger(Data);
57 }
Ted Kremenek174aea42008-02-05 18:51:06 +000058
59 static inline void Profile(llvm::FoldingSetNodeID& ID, SymbolID X) {
60 X.Profile(ID);
61 }
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000062};
63
64class SymbolData {
65 uintptr_t Data;
66public:
67 enum Kind { ParmKind = 0x0, Mask = 0x3 };
68
69 SymbolData(ParmVarDecl* D)
70 : Data(reinterpret_cast<uintptr_t>(D) | ParmKind) {}
71
72 inline Kind getKind() const { return (Kind) (Data & Mask); }
73 inline void* getPtr() const { return reinterpret_cast<void*>(Data & ~Mask); }
74 inline bool operator==(const SymbolData& R) const { return Data == R.Data; }
75};
Ted Kremenek1fbdb022008-02-05 21:32:43 +000076
77
78class SymIntConstraint : public llvm::FoldingSetNode {
79 SymbolID Symbol;
80 BinaryOperator::Opcode Op;
81 const llvm::APSInt& Val;
82public:
83 SymIntConstraint(SymbolID sym, BinaryOperator::Opcode op,
84 const llvm::APSInt& V)
85 : Symbol(sym),
86 Op(op), Val(V) {}
87
88 BinaryOperator::Opcode getOpcode() const { return Op; }
89 SymbolID getSymbol() const { return Symbol; }
90 const llvm::APSInt& getInt() const { return Val; }
91
92 static inline void Profile(llvm::FoldingSetNodeID& ID,
93 const SymbolID& Symbol,
94 BinaryOperator::Opcode Op,
95 const llvm::APSInt& Val) {
96 Symbol.Profile(ID);
97 ID.AddInteger(Op);
98 ID.AddPointer(&Val);
99 }
100
101 void Profile(llvm::FoldingSetNodeID& ID) {
102 Profile(ID, Symbol, Op, Val);
103 }
104};
105
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000106
107class SymbolManager {
108 std::vector<SymbolData> SymbolToData;
109
110 typedef llvm::DenseMap<void*,SymbolID> MapTy;
111 MapTy DataToSymbol;
112
113public:
114 SymbolManager();
115 ~SymbolManager();
116
117 SymbolData getSymbolData(SymbolID id) const {
118 assert (id < SymbolToData.size());
119 return SymbolToData[id];
120 }
121
122 SymbolID getSymbol(ParmVarDecl* D);
123};
Ted Kremenek1fbdb022008-02-05 21:32:43 +0000124
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000125
126class ValueManager {
127 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> >
128 APSIntSetTy;
129
Ted Kremenek1fbdb022008-02-05 21:32:43 +0000130 typedef llvm::FoldingSet<SymIntConstraint>
131 SymIntCSetTy;
132
133
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000134 ASTContext& Ctx;
Ted Kremenek768ad162008-02-05 05:15:51 +0000135 llvm::BumpPtrAllocator& BPAlloc;
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000136
Ted Kremenek1fbdb022008-02-05 21:32:43 +0000137 APSIntSetTy APSIntSet;
138 SymIntCSetTy SymIntCSet;
139
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000140public:
Ted Kremenek768ad162008-02-05 05:15:51 +0000141 ValueManager(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc)
142 : Ctx(ctx), BPAlloc(Alloc) {}
143
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000144 ~ValueManager();
145
146 ASTContext& getContext() const { return Ctx; }
Ted Kremenek1fbdb022008-02-05 21:32:43 +0000147 const llvm::APSInt& getValue(const llvm::APSInt& X);
148 const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
149 const llvm::APSInt& getValue(uint64_t X, QualType T,
150 SourceLocation Loc = SourceLocation());
151
152 const SymIntConstraint& getConstraint(SymbolID sym, BinaryOperator::Opcode Op,
153 const llvm::APSInt& V);
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000154};
155
156//==------------------------------------------------------------------------==//
157// Base RValue types.
158//==------------------------------------------------------------------------==//
159
160class RValue {
161public:
162 enum BaseKind { LValueKind=0x0,
163 NonLValueKind=0x1,
164 UninitializedKind=0x2,
165 InvalidKind=0x3 };
166
167 enum { BaseBits = 2,
168 BaseMask = 0x3 };
169
170private:
171 void* Data;
172 unsigned Kind;
173
174protected:
175 RValue(const void* d, bool isLValue, unsigned ValKind)
176 : Data(const_cast<void*>(d)),
177 Kind((isLValue ? LValueKind : NonLValueKind) | (ValKind << BaseBits)) {}
178
179 explicit RValue(BaseKind k)
180 : Data(0), Kind(k) {}
181
182 void* getRawPtr() const {
183 return reinterpret_cast<void*>(Data);
184 }
185
186public:
187 ~RValue() {};
188
Ted Kremenekcba2e432008-02-05 19:35:18 +0000189 /// BufferTy - A temporary buffer to hold a set of RValues.
190 typedef llvm::SmallVector<RValue,5> BufferTy;
191
192
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000193 RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
194
195 unsigned getRawKind() const { return Kind; }
196 BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
197 unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
198
199 void Profile(llvm::FoldingSetNodeID& ID) const {
200 ID.AddInteger((unsigned) getRawKind());
201 ID.AddPointer(reinterpret_cast<void*>(Data));
202 }
203
204 bool operator==(const RValue& RHS) const {
205 return getRawKind() == RHS.getRawKind() && Data == RHS.Data;
206 }
207
208 static RValue GetSymbolValue(SymbolManager& SymMgr, ParmVarDecl *D);
209
210 inline bool isValid() const { return getRawKind() != InvalidKind; }
211 inline bool isInvalid() const { return getRawKind() == InvalidKind; }
212
213 void print(std::ostream& OS) const;
214 void print() const { print(*llvm::cerr.stream()); }
215
216 // Implement isa<T> support.
217 static inline bool classof(const RValue*) { return true; }
218};
219
220class InvalidValue : public RValue {
221public:
222 InvalidValue() : RValue(InvalidKind) {}
223
224 static inline bool classof(const RValue* V) {
225 return V->getBaseKind() == InvalidKind;
226 }
227};
228
229class UninitializedValue : public RValue {
230public:
231 UninitializedValue() : RValue(UninitializedKind) {}
232
233 static inline bool classof(const RValue* V) {
234 return V->getBaseKind() == UninitializedKind;
235 }
236};
237
238class NonLValue : public RValue {
239protected:
240 NonLValue(unsigned SubKind, const void* d) : RValue(d, false, SubKind) {}
241
242public:
243 void print(std::ostream& Out) const;
244
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000245 RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
246
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000247 // Arithmetic operators.
248 NonLValue Add(ValueManager& ValMgr, const NonLValue& RHS) const;
249 NonLValue Sub(ValueManager& ValMgr, const NonLValue& RHS) const;
250 NonLValue Mul(ValueManager& ValMgr, const NonLValue& RHS) const;
251 NonLValue Div(ValueManager& ValMgr, const NonLValue& RHS) const;
252 NonLValue Rem(ValueManager& ValMgr, const NonLValue& RHS) const;
253 NonLValue UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const;
Ted Kremenekc5d3b4c2008-02-04 16:58:30 +0000254 NonLValue BitwiseComplement(ValueManager& ValMgr) const;
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000255
256 // Equality operators.
257 NonLValue EQ(ValueManager& ValMgr, const NonLValue& RHS) const;
258 NonLValue NE(ValueManager& ValMgr, const NonLValue& RHS) const;
259
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000260
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000261 // Utility methods to create NonLValues.
262 static NonLValue GetValue(ValueManager& ValMgr, uint64_t X, QualType T,
263 SourceLocation Loc = SourceLocation());
264
265 static NonLValue GetValue(ValueManager& ValMgr, IntegerLiteral* I);
266
267 static inline NonLValue GetIntTruthValue(ValueManager& ValMgr, bool X) {
268 return GetValue(ValMgr, X ? 1U : 0U, ValMgr.getContext().IntTy);
269 }
270
271 // Implement isa<T> support.
272 static inline bool classof(const RValue* V) {
273 return V->getBaseKind() >= NonLValueKind;
274 }
275};
276
277class LValue : public RValue {
278protected:
Ted Kremenek516f91b2008-01-31 22:17:03 +0000279 LValue(unsigned SubKind, const void* D) : RValue(const_cast<void*>(D),
280 true, SubKind) {}
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000281
282public:
283 void print(std::ostream& Out) const;
284
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000285 RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
286
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000287 // Equality operators.
288 NonLValue EQ(ValueManager& ValMgr, const LValue& RHS) const;
289 NonLValue NE(ValueManager& ValMgr, const LValue& RHS) const;
290
291 // Implement isa<T> support.
292 static inline bool classof(const RValue* V) {
293 return V->getBaseKind() == LValueKind;
294 }
295};
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000296
297//==------------------------------------------------------------------------==//
298// Subclasses of NonLValue.
299//==------------------------------------------------------------------------==//
300
Ted Kremenek329f8542008-02-05 21:52:21 +0000301namespace nonlval {
302
303 enum Kind { SymbolValKind,
Ted Kremenek9466aa82008-02-05 22:10:48 +0000304 SymIntConstraintValKind,
Ted Kremenek329f8542008-02-05 21:52:21 +0000305 ConcreteIntKind,
306 NumKind };
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000307
Ted Kremenek329f8542008-02-05 21:52:21 +0000308 class SymbolVal : public NonLValue {
309 public:
310 SymbolVal(unsigned SymID)
311 : NonLValue(SymbolValKind,
312 reinterpret_cast<void*>((uintptr_t) SymID)) {}
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000313
Ted Kremenek329f8542008-02-05 21:52:21 +0000314 SymbolID getSymbolID() const {
315 return (SymbolID) reinterpret_cast<uintptr_t>(getRawPtr());
316 }
317
318 static inline bool classof(const RValue* V) {
Ted Kremenek9466aa82008-02-05 22:10:48 +0000319 return isa<NonLValue>(V) && V->getSubKind() == SymbolValKind;
320 }
321 };
322
323 class SymIntConstraintVal : public NonLValue {
324 public:
325 SymIntConstraintVal(const SymIntConstraint& C)
326 : NonLValue(SymIntConstraintValKind, reinterpret_cast<const void*>(&C)) {}
327
328 const SymIntConstraint& getConstraint() const {
329 return *reinterpret_cast<SymIntConstraint*>(getRawPtr());
330 }
331
332 static inline bool classof(const RValue* V) {
333 return isa<NonLValue>(V) && V->getSubKind() == SymIntConstraintValKind;
334 }
Ted Kremenek329f8542008-02-05 21:52:21 +0000335 };
336
337 class ConcreteInt : public NonLValue {
338 public:
339 ConcreteInt(const llvm::APSInt& V) : NonLValue(ConcreteIntKind, &V) {}
340
341 const llvm::APSInt& getValue() const {
342 return *static_cast<llvm::APSInt*>(getRawPtr());
343 }
344
345 // Arithmetic operators.
346
347 ConcreteInt Add(ValueManager& ValMgr, const ConcreteInt& V) const {
348 return ValMgr.getValue(getValue() + V.getValue());
349 }
350
351 ConcreteInt Sub(ValueManager& ValMgr, const ConcreteInt& V) const {
352 return ValMgr.getValue(getValue() - V.getValue());
353 }
354
355 ConcreteInt Mul(ValueManager& ValMgr, const ConcreteInt& V) const {
356 return ValMgr.getValue(getValue() * V.getValue());
357 }
358
359 ConcreteInt Div(ValueManager& ValMgr, const ConcreteInt& V) const {
360 return ValMgr.getValue(getValue() / V.getValue());
361 }
362
363 ConcreteInt Rem(ValueManager& ValMgr, const ConcreteInt& V) const {
364 return ValMgr.getValue(getValue() % V.getValue());
365 }
366
367 ConcreteInt UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const {
368 assert (U->getType() == U->getSubExpr()->getType());
369 assert (U->getType()->isIntegerType());
370 return ValMgr.getValue(-getValue());
371 }
372
373 ConcreteInt BitwiseComplement(ValueManager& ValMgr) const {
374 return ValMgr.getValue(~getValue());
375 }
376
377 // Casting.
378
379 ConcreteInt Cast(ValueManager& ValMgr, Expr* CastExpr) const {
380 assert (CastExpr->getType()->isIntegerType());
381
382 llvm::APSInt X(getValue());
383 X.extOrTrunc(ValMgr.getContext().getTypeSize(CastExpr->getType(),
384 CastExpr->getLocStart()));
385 return ValMgr.getValue(X);
386 }
387
388 // Equality operators.
389
390 ConcreteInt EQ(ValueManager& ValMgr, const ConcreteInt& V) const {
391 const llvm::APSInt& Val = getValue();
392 return ValMgr.getValue(Val == V.getValue() ? 1U : 0U,
393 Val.getBitWidth(), Val.isUnsigned());
394 }
395
396 ConcreteInt NE(ValueManager& ValMgr, const ConcreteInt& V) const {
397 const llvm::APSInt& Val = getValue();
398 return ValMgr.getValue(Val != V.getValue() ? 1U : 0U,
399 Val.getBitWidth(), Val.isUnsigned());
400 }
401
402 // Implement isa<T> support.
403 static inline bool classof(const RValue* V) {
Ted Kremenek9466aa82008-02-05 22:10:48 +0000404 return isa<NonLValue>(V) && V->getSubKind() == ConcreteIntKind;
Ted Kremenek329f8542008-02-05 21:52:21 +0000405 }
406 };
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000407
Ted Kremenek329f8542008-02-05 21:52:21 +0000408} // end namespace clang::nonlval
Ted Kremenek516f91b2008-01-31 22:17:03 +0000409
410//==------------------------------------------------------------------------==//
411// Subclasses of LValue.
412//==------------------------------------------------------------------------==//
413
Ted Kremenek329f8542008-02-05 21:52:21 +0000414namespace lval {
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000415
Ted Kremenek329f8542008-02-05 21:52:21 +0000416 enum Kind { SymbolValKind,
417 DeclValKind,
418 ConcreteIntKind,
419 NumKind };
Ted Kremenek516f91b2008-01-31 22:17:03 +0000420
Ted Kremenek329f8542008-02-05 21:52:21 +0000421 class SymbolVal : public LValue {
422 public:
423 SymbolVal(unsigned SymID)
424 : LValue(SymbolValKind, reinterpret_cast<void*>((uintptr_t) SymID)) {}
425
426 SymbolID getSymbolID() const {
427 return (SymbolID) reinterpret_cast<uintptr_t>(getRawPtr());
428 }
429
430 static inline bool classof(const RValue* V) {
431 return V->getSubKind() == SymbolValKind;
432 }
433 };
Ted Kremenek516f91b2008-01-31 22:17:03 +0000434
Ted Kremenek329f8542008-02-05 21:52:21 +0000435 class DeclVal : public LValue {
436 public:
437 DeclVal(const ValueDecl* vd) : LValue(DeclValKind,vd) {}
438
439 ValueDecl* getDecl() const {
440 return static_cast<ValueDecl*>(getRawPtr());
441 }
442
443 inline bool operator==(const DeclVal& R) const {
444 return getDecl() == R.getDecl();
445 }
446
447 inline bool operator!=(const DeclVal& R) const {
448 return getDecl() != R.getDecl();
449 }
450
451 // Implement isa<T> support.
452 static inline bool classof(const RValue* V) {
453 return V->getSubKind() == DeclValKind;
454 }
455 };
Ted Kremenek516f91b2008-01-31 22:17:03 +0000456
Ted Kremenek329f8542008-02-05 21:52:21 +0000457 class ConcreteInt : public LValue {
458 public:
459 ConcreteInt(const llvm::APSInt& V) : LValue(ConcreteIntKind, &V) {}
460
461 const llvm::APSInt& getValue() const {
462 return *static_cast<llvm::APSInt*>(getRawPtr());
463 }
464
465 // Arithmetic operators.
466
467 ConcreteInt Add(ValueManager& ValMgr, const ConcreteInt& V) const {
468 return ValMgr.getValue(getValue() + V.getValue());
469 }
470
471 ConcreteInt Sub(ValueManager& ValMgr, const ConcreteInt& V) const {
472 return ValMgr.getValue(getValue() - V.getValue());
473 }
474
475 // Equality operators.
476
477 ConcreteInt EQ(ValueManager& ValMgr, const ConcreteInt& V) const {
478 const llvm::APSInt& Val = getValue();
479 return ValMgr.getValue(Val == V.getValue() ? 1U : 0U,
480 Val.getBitWidth(), Val.isUnsigned());
481 }
482
483 ConcreteInt NE(ValueManager& ValMgr, const ConcreteInt& V) const {
484 const llvm::APSInt& Val = getValue();
485 return ValMgr.getValue(Val != V.getValue() ? 1U : 0U,
486 Val.getBitWidth(), Val.isUnsigned());
487 }
488
489 // Implement isa<T> support.
490 static inline bool classof(const RValue* V) {
491 return V->getSubKind() == ConcreteIntKind;
492 }
493 };
494} // end clang::lval namespace
Ted Kremenek516f91b2008-01-31 22:17:03 +0000495
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000496
497} // end clang namespace
498
499//==------------------------------------------------------------------------==//
500// Casting machinery to get cast<> and dyn_cast<> working with SymbolData.
501//==------------------------------------------------------------------------==//
502
503namespace llvm {
504
505template<> inline bool
506isa<clang::ParmVarDecl,clang::SymbolData>(const clang::SymbolData& V) {
507 return V.getKind() == clang::SymbolData::ParmKind;
508}
509
510template<> struct cast_retty_impl<clang::ParmVarDecl,clang::SymbolData> {
511 typedef const clang::ParmVarDecl* ret_type;
512};
513
514template<> struct simplify_type<clang::SymbolData> {
515 typedef void* SimpleType;
516 static inline SimpleType getSimplifiedValue(const clang::SymbolData &V) {
517 return V.getPtr();
518 }
519};
520
521} // end llvm namespace
522
523#endif