clang  6.0.0svn
BasicValueFactory.cpp
Go to the documentation of this file.
1 //=== BasicValueFactory.cpp - 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 #include "clang/AST/ASTContext.h"
19 
20 using namespace clang;
21 using namespace ento;
22 
23 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
25  T.Profile(ID);
26  ID.AddPointer(L.getInternalPointer());
27 }
28 
29 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
30  const StoreRef &store,
31  const TypedValueRegion *region) {
32  ID.AddPointer(store.getStore());
33  ID.AddPointer(region);
34 }
35 
37  llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
39  ID.AddPointer(D);
40  ID.AddPointer(L.getInternalPointer());
41 }
42 
43 typedef std::pair<SVal, uintptr_t> SValData;
44 typedef std::pair<SVal, SVal> SValPair;
45 
46 namespace llvm {
47 template<> struct FoldingSetTrait<SValData> {
48  static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
49  X.first.Profile(ID);
50  ID.AddPointer( (void*) X.second);
51  }
52 };
53 
54 template<> struct FoldingSetTrait<SValPair> {
55  static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
56  X.first.Profile(ID);
57  X.second.Profile(ID);
58  }
59 };
60 }
61 
62 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> >
64 
65 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> >
67 
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();
74 
75  delete (PersistentSValsTy*) PersistentSVals;
76  delete (PersistentSValPairsTy*) PersistentSValPairs;
77 }
78 
79 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
80  llvm::FoldingSetNodeID ID;
81  void *InsertPos;
82  typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
83 
84  X.Profile(ID);
85  FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
86 
87  if (!P) {
88  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
89  new (P) FoldNodeTy(X);
90  APSIntSet.InsertNode(P, InsertPos);
91  }
92 
93  return *P;
94 }
95 
96 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
97  bool isUnsigned) {
98  llvm::APSInt V(X, isUnsigned);
99  return getValue(V);
100 }
101 
102 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
103  bool isUnsigned) {
104  llvm::APSInt V(BitWidth, isUnsigned);
105  V = X;
106  return getValue(V);
107 }
108 
109 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
110 
111  return getValue(getAPSIntType(T).getValue(X));
112 }
113 
114 const CompoundValData*
117 
118  llvm::FoldingSetNodeID ID;
119  CompoundValData::Profile(ID, T, Vals);
120  void *InsertPos;
121 
122  CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
123 
124  if (!D) {
125  D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
126  new (D) CompoundValData(T, Vals);
127  CompoundValDataSet.InsertNode(D, InsertPos);
128  }
129 
130  return D;
131 }
132 
133 const LazyCompoundValData*
135  const TypedValueRegion *region) {
136  llvm::FoldingSetNodeID ID;
137  LazyCompoundValData::Profile(ID, store, region);
138  void *InsertPos;
139 
141  LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
142 
143  if (!D) {
144  D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
145  new (D) LazyCompoundValData(store, region);
146  LazyCompoundValDataSet.InsertNode(D, InsertPos);
147  }
148 
149  return D;
150 }
151 
154  llvm::FoldingSetNodeID ID;
155  PointerToMemberData::Profile(ID, DD, L);
156  void *InsertPos;
157 
159  PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
160 
161  if (!D) {
162  D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
163  new (D) PointerToMemberData(DD, L);
164  PointerToMemberDataSet.InsertNode(D, InsertPos);
165  }
166 
167  return D;
168 }
169 
171  llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
172  const nonloc::PointerToMember &PTM) {
174  const DeclaratorDecl *DD = nullptr;
176 
177  if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
178  if (PTMDT.is<const DeclaratorDecl *>())
179  DD = PTMDT.get<const DeclaratorDecl *>();
180 
181  PathList = CXXBaseListFactory.getEmptyList();
182  } else { // const PointerToMemberData *
183  const PointerToMemberData *PTMD =
184  PTMDT.get<const PointerToMemberData *>();
185  DD = PTMD->getDeclaratorDecl();
186 
187  PathList = PTMD->getCXXBaseList();
188  }
189 
190  for (const auto &I : llvm::reverse(PathRange))
191  PathList = prependCXXBase(I, PathList);
192  return getPointerToMemberData(DD, PathList);
193 }
194 
195 const llvm::APSInt*
197  const llvm::APSInt& V1, const llvm::APSInt& V2) {
198 
199  switch (Op) {
200  default:
201  assert (false && "Invalid Opcode.");
202 
203  case BO_Mul:
204  return &getValue( V1 * V2 );
205 
206  case BO_Div:
207  if (V2 == 0) // Avoid division by zero
208  return nullptr;
209  return &getValue( V1 / V2 );
210 
211  case BO_Rem:
212  if (V2 == 0) // Avoid division by zero
213  return nullptr;
214  return &getValue( V1 % V2 );
215 
216  case BO_Add:
217  return &getValue( V1 + V2 );
218 
219  case BO_Sub:
220  return &getValue( V1 - V2 );
221 
222  case BO_Shl: {
223 
224  // FIXME: This logic should probably go higher up, where we can
225  // test these conditions symbolically.
226 
227  // FIXME: Expand these checks to include all undefined behavior.
228  if (V1.isSigned() && V1.isNegative())
229  return nullptr;
230 
231  if (V2.isSigned() && V2.isNegative())
232  return nullptr;
233 
234  uint64_t Amt = V2.getZExtValue();
235 
236  if (Amt >= V1.getBitWidth())
237  return nullptr;
238 
239  return &getValue( V1.operator<<( (unsigned) Amt ));
240  }
241 
242  case BO_Shr: {
243 
244  // FIXME: This logic should probably go higher up, where we can
245  // test these conditions symbolically.
246 
247  // FIXME: Expand these checks to include all undefined behavior.
248 
249  if (V2.isSigned() && V2.isNegative())
250  return nullptr;
251 
252  uint64_t Amt = V2.getZExtValue();
253 
254  if (Amt >= V1.getBitWidth())
255  return nullptr;
256 
257  return &getValue( V1.operator>>( (unsigned) Amt ));
258  }
259 
260  case BO_LT:
261  return &getTruthValue( V1 < V2 );
262 
263  case BO_GT:
264  return &getTruthValue( V1 > V2 );
265 
266  case BO_LE:
267  return &getTruthValue( V1 <= V2 );
268 
269  case BO_GE:
270  return &getTruthValue( V1 >= V2 );
271 
272  case BO_EQ:
273  return &getTruthValue( V1 == V2 );
274 
275  case BO_NE:
276  return &getTruthValue( V1 != V2 );
277 
278  // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
279 
280  case BO_And:
281  return &getValue( V1 & V2 );
282 
283  case BO_Or:
284  return &getValue( V1 | V2 );
285 
286  case BO_Xor:
287  return &getValue( V1 ^ V2 );
288  }
289 }
290 
291 
292 const std::pair<SVal, uintptr_t>&
294 
295  // Lazily create the folding set.
296  if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
297 
298  llvm::FoldingSetNodeID ID;
299  void *InsertPos;
300  V.Profile(ID);
301  ID.AddPointer((void*) Data);
302 
303  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
304 
305  typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy;
306  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
307 
308  if (!P) {
309  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
310  new (P) FoldNodeTy(std::make_pair(V, Data));
311  Map.InsertNode(P, InsertPos);
312  }
313 
314  return P->getValue();
315 }
316 
317 const std::pair<SVal, SVal>&
319 
320  // Lazily create the folding set.
321  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
322 
323  llvm::FoldingSetNodeID ID;
324  void *InsertPos;
325  V1.Profile(ID);
326  V2.Profile(ID);
327 
328  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
329 
330  typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy;
331  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
332 
333  if (!P) {
334  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
335  new (P) FoldNodeTy(std::make_pair(V1, V2));
336  Map.InsertNode(P, InsertPos);
337  }
338 
339  return P->getValue();
340 }
341 
343  return &getPersistentSValWithData(X, 0).first;
344 }
Defines the clang::ASTContext interface.
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:511
A (possibly-)qualified type.
Definition: Type.h:653
Store getStore() const
Definition: StoreRef.h:46
llvm::ImmutableList< const CXXBaseSpecifier * > getCXXBaseList() const
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
const CompoundValData * getCompoundValData(QualType T, llvm::ImmutableList< SVal > Vals)
const std::pair< SVal, SVal > & getPersistentSValPair(const SVal &V1, const SVal &V2)
StringRef P
const clang::ento::PointerToMemberData * accumCXXBase(llvm::iterator_range< CastExpr::path_const_iterator > PathRange, const nonloc::PointerToMember &PTM)
const PTMDataType getPTMData() const
Definition: SVals.h:493
const DeclaratorDecl * getDeclaratorDecl() const
Value representing pointer-to-member.
Definition: SVals.h:487
BinaryOperatorKind
const SVal * getPersistentSVal(SVal X)
std::pair< SVal, SVal > SValPair
Represents a ValueDecl that came out of a declarator.
Definition: Decl.h:681
const PointerToMemberData * getPointerToMemberData(const DeclaratorDecl *DD, llvm::ImmutableList< const CXXBaseSpecifier *> L)
const FunctionProtoType * T
llvm::PointerUnion< const DeclaratorDecl *, const PointerToMemberData * > PTMDataType
Definition: SVals.h:492
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: Type.h:1051
static SVal getValue(SVal val, SValBuilder &svalBuilder)
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c.h:82
static void Profile(llvm::FoldingSetNodeID &ID, const StoreRef &store, const TypedValueRegion *region)
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: SVals.h:112
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValPair > > PersistentSValPairsTy
static void Profile(llvm::FoldingSetNodeID &ID, const DeclaratorDecl *D, llvm::ImmutableList< const CXXBaseSpecifier *> L)
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:63
const llvm::APSInt * evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1, const llvm::APSInt &V2)
std::pair< SVal, uintptr_t > SValData
Dataflow Directional Tag Classes.
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValData > > PersistentSValsTy
static void Profile(llvm::FoldingSetNodeID &ID, QualType T, llvm::ImmutableList< SVal > L)
static void Profile(const SValPair &X, llvm::FoldingSetNodeID &ID)
const std::pair< SVal, uintptr_t > & getPersistentSValWithData(const SVal &V, uintptr_t Data)
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13010
const LazyCompoundValData * getLazyCompoundValData(const StoreRef &store, const TypedValueRegion *region)
static void Profile(const SValData &X, llvm::FoldingSetNodeID &ID)
CompoundValData(QualType t, llvm::ImmutableList< SVal > l)