1 //==- BasicValueFactory.h - Basic values for Path Sens analysis --*- 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 file defines BasicValueFactory, a class that manages the lifetime
11 //  of APSInt objects and symbolic constraints used by ExprEngine
12 //  and related classes.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
17 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
18 
19 #include "clang/AST/ASTContext.h"
20 #include "clang/AST/Expr.h"
21 #include "clang/AST/Type.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
26 #include "llvm/ADT/APSInt.h"
27 #include "llvm/ADT/FoldingSet.h"
28 #include "llvm/ADT/ImmutableList.h"
29 #include "llvm/ADT/iterator_range.h"
30 #include "llvm/Support/Allocator.h"
31 #include <cassert>
32 #include <cstdint>
33 #include <utility>
34 
35 namespace clang {
36 
37 class CXXBaseSpecifier;
38 class DeclaratorDecl;
39 
40 namespace ento {
41 
42 class CompoundValData : public llvm::FoldingSetNode {
43   QualType T;
44   llvm::ImmutableList<SVal> L;
45 
46 public:
CompoundValData(QualType t,llvm::ImmutableList<SVal> l)47   CompoundValData(QualType t, llvm::ImmutableList<SVal> l) : T(t), L(l) {
48     assert(NonLoc::isCompoundType(t));
49   }
50 
51   using iterator = llvm::ImmutableList<SVal>::iterator;
52 
begin()53   iterator begin() const { return L.begin(); }
end()54   iterator end() const { return L.end(); }
55 
56   static void Profile(llvm::FoldingSetNodeID& ID, QualType T,
57                       llvm::ImmutableList<SVal> L);
58 
Profile(llvm::FoldingSetNodeID & ID)59   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); }
60 };
61 
62 class LazyCompoundValData : public llvm::FoldingSetNode {
63   StoreRef store;
64   const TypedValueRegion *region;
65 
66 public:
LazyCompoundValData(const StoreRef & st,const TypedValueRegion * r)67   LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r)
68       : store(st), region(r) {
69     assert(NonLoc::isCompoundType(r->getValueType()));
70   }
71 
getStore()72   const void *getStore() const { return store.getStore(); }
getRegion()73   const TypedValueRegion *getRegion() const { return region; }
74 
75   static void Profile(llvm::FoldingSetNodeID& ID,
76                       const StoreRef &store,
77                       const TypedValueRegion *region);
78 
Profile(llvm::FoldingSetNodeID & ID)79   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); }
80 };
81 
82 class PointerToMemberData : public llvm::FoldingSetNode {
83   const DeclaratorDecl *D;
84   llvm::ImmutableList<const CXXBaseSpecifier *> L;
85 
86 public:
PointerToMemberData(const DeclaratorDecl * D,llvm::ImmutableList<const CXXBaseSpecifier * > L)87   PointerToMemberData(const DeclaratorDecl *D,
88                       llvm::ImmutableList<const CXXBaseSpecifier *> L)
89       : D(D), L(L) {}
90 
91   using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator;
92 
begin()93   iterator begin() const { return L.begin(); }
end()94   iterator end() const { return L.end(); }
95 
96   static void Profile(llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
97                       llvm::ImmutableList<const CXXBaseSpecifier *> L);
98 
Profile(llvm::FoldingSetNodeID & ID)99   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, D, L); }
getDeclaratorDecl()100   const DeclaratorDecl *getDeclaratorDecl() const {return D;}
101 
getCXXBaseList()102   llvm::ImmutableList<const CXXBaseSpecifier *> getCXXBaseList() const {
103     return L;
104   }
105 };
106 
107 class BasicValueFactory {
108   using APSIntSetTy =
109       llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt>>;
110 
111   ASTContext &Ctx;
112   llvm::BumpPtrAllocator& BPAlloc;
113 
114   APSIntSetTy APSIntSet;
115   void *PersistentSVals = nullptr;
116   void *PersistentSValPairs = nullptr;
117 
118   llvm::ImmutableList<SVal>::Factory SValListFactory;
119   llvm::ImmutableList<const CXXBaseSpecifier *>::Factory CXXBaseListFactory;
120   llvm::FoldingSet<CompoundValData>  CompoundValDataSet;
121   llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet;
122   llvm::FoldingSet<PointerToMemberData> PointerToMemberDataSet;
123 
124   // This is private because external clients should use the factory
125   // method that takes a QualType.
126   const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
127 
128 public:
BasicValueFactory(ASTContext & ctx,llvm::BumpPtrAllocator & Alloc)129   BasicValueFactory(ASTContext &ctx, llvm::BumpPtrAllocator &Alloc)
130       : Ctx(ctx), BPAlloc(Alloc), SValListFactory(Alloc),
131         CXXBaseListFactory(Alloc) {}
132 
133   ~BasicValueFactory();
134 
getContext()135   ASTContext &getContext() const { return Ctx; }
136 
137   const llvm::APSInt& getValue(const llvm::APSInt& X);
138   const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned);
139   const llvm::APSInt& getValue(uint64_t X, QualType T);
140 
141   /// Returns the type of the APSInt used to store values of the given QualType.
getAPSIntType(QualType T)142   APSIntType getAPSIntType(QualType T) const {
143     assert(T->isIntegralOrEnumerationType() || Loc::isLocType(T));
144     return APSIntType(Ctx.getIntWidth(T),
145                       !T->isSignedIntegerOrEnumerationType());
146   }
147 
148   /// Convert - Create a new persistent APSInt with the same value as 'From'
149   ///  but with the bitwidth and signedness of 'To'.
Convert(const llvm::APSInt & To,const llvm::APSInt & From)150   const llvm::APSInt &Convert(const llvm::APSInt& To,
151                               const llvm::APSInt& From) {
152     APSIntType TargetType(To);
153     if (TargetType == APSIntType(From))
154       return From;
155 
156     return getValue(TargetType.convert(From));
157   }
158 
Convert(QualType T,const llvm::APSInt & From)159   const llvm::APSInt &Convert(QualType T, const llvm::APSInt &From) {
160     APSIntType TargetType = getAPSIntType(T);
161     if (TargetType == APSIntType(From))
162       return From;
163 
164     return getValue(TargetType.convert(From));
165   }
166 
getIntValue(uint64_t X,bool isUnsigned)167   const llvm::APSInt &getIntValue(uint64_t X, bool isUnsigned) {
168     QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy;
169     return getValue(X, T);
170   }
171 
getMaxValue(const llvm::APSInt & v)172   const llvm::APSInt &getMaxValue(const llvm::APSInt &v) {
173     return getValue(APSIntType(v).getMaxValue());
174   }
175 
getMinValue(const llvm::APSInt & v)176   const llvm::APSInt &getMinValue(const llvm::APSInt &v) {
177     return getValue(APSIntType(v).getMinValue());
178   }
179 
getMaxValue(QualType T)180   const llvm::APSInt &getMaxValue(QualType T) {
181     return getValue(getAPSIntType(T).getMaxValue());
182   }
183 
getMinValue(QualType T)184   const llvm::APSInt &getMinValue(QualType T) {
185     return getValue(getAPSIntType(T).getMinValue());
186   }
187 
Add1(const llvm::APSInt & V)188   const llvm::APSInt &Add1(const llvm::APSInt &V) {
189     llvm::APSInt X = V;
190     ++X;
191     return getValue(X);
192   }
193 
Sub1(const llvm::APSInt & V)194   const llvm::APSInt &Sub1(const llvm::APSInt &V) {
195     llvm::APSInt X = V;
196     --X;
197     return getValue(X);
198   }
199 
getZeroWithTypeSize(QualType T)200   const llvm::APSInt &getZeroWithTypeSize(QualType T) {
201     assert(T->isScalarType());
202     return getValue(0, Ctx.getTypeSize(T), true);
203   }
204 
205   const llvm::APSInt &getZeroWithPtrWidth(bool isUnsigned = true) {
206     return getValue(0, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned);
207   }
208 
getIntWithPtrWidth(uint64_t X,bool isUnsigned)209   const llvm::APSInt &getIntWithPtrWidth(uint64_t X, bool isUnsigned) {
210     return getValue(X, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned);
211   }
212 
getTruthValue(bool b,QualType T)213   const llvm::APSInt &getTruthValue(bool b, QualType T) {
214     return getValue(b ? 1 : 0, Ctx.getIntWidth(T),
215                     T->isUnsignedIntegerOrEnumerationType());
216   }
217 
getTruthValue(bool b)218   const llvm::APSInt &getTruthValue(bool b) {
219     return getTruthValue(b, Ctx.getLogicalOperationType());
220   }
221 
222   const CompoundValData *getCompoundValData(QualType T,
223                                             llvm::ImmutableList<SVal> Vals);
224 
225   const LazyCompoundValData *getLazyCompoundValData(const StoreRef &store,
226                                             const TypedValueRegion *region);
227 
228   const PointerToMemberData *getPointerToMemberData(
229       const DeclaratorDecl *DD,
230       llvm::ImmutableList<const CXXBaseSpecifier *> L);
231 
getEmptySValList()232   llvm::ImmutableList<SVal> getEmptySValList() {
233     return SValListFactory.getEmptyList();
234   }
235 
prependSVal(SVal X,llvm::ImmutableList<SVal> L)236   llvm::ImmutableList<SVal> prependSVal(SVal X, llvm::ImmutableList<SVal> L) {
237     return SValListFactory.add(X, L);
238   }
239 
getEmptyCXXBaseList()240   llvm::ImmutableList<const CXXBaseSpecifier *> getEmptyCXXBaseList() {
241     return CXXBaseListFactory.getEmptyList();
242   }
243 
prependCXXBase(const CXXBaseSpecifier * CBS,llvm::ImmutableList<const CXXBaseSpecifier * > L)244   llvm::ImmutableList<const CXXBaseSpecifier *> prependCXXBase(
245       const CXXBaseSpecifier *CBS,
246       llvm::ImmutableList<const CXXBaseSpecifier *> L) {
247     return CXXBaseListFactory.add(CBS, L);
248   }
249 
250   const PointerToMemberData *accumCXXBase(
251       llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
252       const nonloc::PointerToMember &PTM);
253 
254   const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op,
255                                      const llvm::APSInt& V1,
256                                      const llvm::APSInt& V2);
257 
258   const std::pair<SVal, uintptr_t>&
259   getPersistentSValWithData(const SVal& V, uintptr_t Data);
260 
261   const std::pair<SVal, SVal>&
262   getPersistentSValPair(const SVal& V1, const SVal& V2);
263 
264   const SVal* getPersistentSVal(SVal X);
265 };
266 
267 } // namespace ento
268 
269 } // namespace clang
270 
271 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
272