1 //=== BasicValueFactory.cpp - Basic values for Path Sens analysis --*- 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 BasicValueFactory, a class that manages the lifetime
11 // of APSInt objects and symbolic constraints used by ExprEngine
12 // and related classes.
14 //===----------------------------------------------------------------------===//
16 #include "clang/AST/ASTContext.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
20 using namespace clang;
23 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
24 llvm::ImmutableList<SVal> L) {
26 ID.AddPointer(L.getInternalPointer());
29 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
30 const StoreRef &store,
31 const TypedValueRegion *region) {
32 ID.AddPointer(store.getStore());
33 ID.AddPointer(region);
36 void PointerToMemberData::Profile(
37 llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
38 llvm::ImmutableList<const CXXBaseSpecifier *> L) {
40 ID.AddPointer(L.getInternalPointer());
43 typedef std::pair<SVal, uintptr_t> SValData;
44 typedef std::pair<SVal, SVal> SValPair;
47 template<> struct FoldingSetTrait<SValData> {
48 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
50 ID.AddPointer( (void*) X.second);
54 template<> struct FoldingSetTrait<SValPair> {
55 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
62 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> >
65 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> >
66 PersistentSValPairsTy;
68 BasicValueFactory::~BasicValueFactory() {
69 // Note that the dstor for the contents of APSIntSet will never be called,
70 // so we iterate over the set and invoke the dstor for each APSInt. This
71 // frees an aux. memory allocated to represent very large constants.
72 for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
73 I->getValue().~APSInt();
75 delete (PersistentSValsTy*) PersistentSVals;
76 delete (PersistentSValPairsTy*) PersistentSValPairs;
79 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
80 llvm::FoldingSetNodeID ID;
82 typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
85 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
88 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
89 new (P) FoldNodeTy(X);
90 APSIntSet.InsertNode(P, InsertPos);
96 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
98 llvm::APSInt V(X, isUnsigned);
102 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
104 llvm::APSInt V(BitWidth, isUnsigned);
109 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
111 return getValue(getAPSIntType(T).getValue(X));
114 const CompoundValData*
115 BasicValueFactory::getCompoundValData(QualType T,
116 llvm::ImmutableList<SVal> Vals) {
118 llvm::FoldingSetNodeID ID;
119 CompoundValData::Profile(ID, T, Vals);
122 CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
125 D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
126 new (D) CompoundValData(T, Vals);
127 CompoundValDataSet.InsertNode(D, InsertPos);
133 const LazyCompoundValData*
134 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
135 const TypedValueRegion *region) {
136 llvm::FoldingSetNodeID ID;
137 LazyCompoundValData::Profile(ID, store, region);
140 LazyCompoundValData *D =
141 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
144 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
145 new (D) LazyCompoundValData(store, region);
146 LazyCompoundValDataSet.InsertNode(D, InsertPos);
152 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
153 const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier*> L) {
154 llvm::FoldingSetNodeID ID;
155 PointerToMemberData::Profile(ID, DD, L);
158 PointerToMemberData *D =
159 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
162 D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
163 new (D) PointerToMemberData(DD, L);
164 PointerToMemberDataSet.InsertNode(D, InsertPos);
170 const clang::ento::PointerToMemberData *BasicValueFactory::accumCXXBase(
171 llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
172 const nonloc::PointerToMember &PTM) {
173 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
174 const DeclaratorDecl *DD = nullptr;
175 llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
177 if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
178 if (PTMDT.is<const DeclaratorDecl *>())
179 DD = PTMDT.get<const DeclaratorDecl *>();
181 PathList = CXXBaseListFactory.getEmptyList();
182 } else { // const PointerToMemberData *
183 const PointerToMemberData *PTMD =
184 PTMDT.get<const PointerToMemberData *>();
185 DD = PTMD->getDeclaratorDecl();
187 PathList = PTMD->getCXXBaseList();
190 for (const auto &I : llvm::reverse(PathRange))
191 PathList = prependCXXBase(I, PathList);
192 return getPointerToMemberData(DD, PathList);
196 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
197 const llvm::APSInt& V1, const llvm::APSInt& V2) {
201 assert (false && "Invalid Opcode.");
204 return &getValue( V1 * V2 );
207 if (V2 == 0) // Avoid division by zero
209 return &getValue( V1 / V2 );
212 if (V2 == 0) // Avoid division by zero
214 return &getValue( V1 % V2 );
217 return &getValue( V1 + V2 );
220 return &getValue( V1 - V2 );
224 // FIXME: This logic should probably go higher up, where we can
225 // test these conditions symbolically.
227 // FIXME: Expand these checks to include all undefined behavior.
228 if (V1.isSigned() && V1.isNegative())
231 if (V2.isSigned() && V2.isNegative())
234 uint64_t Amt = V2.getZExtValue();
236 if (Amt >= V1.getBitWidth())
239 return &getValue( V1.operator<<( (unsigned) Amt ));
244 // FIXME: This logic should probably go higher up, where we can
245 // test these conditions symbolically.
247 // FIXME: Expand these checks to include all undefined behavior.
249 if (V2.isSigned() && V2.isNegative())
252 uint64_t Amt = V2.getZExtValue();
254 if (Amt >= V1.getBitWidth())
257 return &getValue( V1.operator>>( (unsigned) Amt ));
261 return &getTruthValue( V1 < V2 );
264 return &getTruthValue( V1 > V2 );
267 return &getTruthValue( V1 <= V2 );
270 return &getTruthValue( V1 >= V2 );
273 return &getTruthValue( V1 == V2 );
276 return &getTruthValue( V1 != V2 );
278 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
281 return &getValue( V1 & V2 );
284 return &getValue( V1 | V2 );
287 return &getValue( V1 ^ V2 );
292 const std::pair<SVal, uintptr_t>&
293 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
295 // Lazily create the folding set.
296 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
298 llvm::FoldingSetNodeID ID;
301 ID.AddPointer((void*) Data);
303 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
305 typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy;
306 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
309 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
310 new (P) FoldNodeTy(std::make_pair(V, Data));
311 Map.InsertNode(P, InsertPos);
314 return P->getValue();
317 const std::pair<SVal, SVal>&
318 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
320 // Lazily create the folding set.
321 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
323 llvm::FoldingSetNodeID ID;
328 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
330 typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy;
331 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
334 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
335 new (P) FoldNodeTy(std::make_pair(V1, V2));
336 Map.InsertNode(P, InsertPos);
339 return P->getValue();
342 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
343 return &getPersistentSValWithData(X, 0).first;