clang  10.0.0svn
BasicValueFactory.cpp
Go to the documentation of this file.
1 //===- BasicValueFactory.cpp - Basic values for Path Sens analysis --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines BasicValueFactory, a class that manages the lifetime
10 // of APSInt objects and symbolic constraints used by ExprEngine
11 // and related classes.
12 //
13 //===----------------------------------------------------------------------===//
14 
20 #include "llvm/ADT/APSInt.h"
21 #include "llvm/ADT/FoldingSet.h"
22 #include "llvm/ADT/ImmutableList.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include <cassert>
25 #include <cstdint>
26 #include <utility>
27 
28 using namespace clang;
29 using namespace ento;
30 
31 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
32  llvm::ImmutableList<SVal> L) {
33  T.Profile(ID);
34  ID.AddPointer(L.getInternalPointer());
35 }
36 
37 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
38  const StoreRef &store,
39  const TypedValueRegion *region) {
40  ID.AddPointer(store.getStore());
41  ID.AddPointer(region);
42 }
43 
45  llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
46  llvm::ImmutableList<const CXXBaseSpecifier *> L) {
47  ID.AddPointer(D);
48  ID.AddPointer(L.getInternalPointer());
49 }
50 
51 using SValData = std::pair<SVal, uintptr_t>;
52 using SValPair = std::pair<SVal, SVal>;
53 
54 namespace llvm {
55 
56 template<> struct FoldingSetTrait<SValData> {
57  static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
58  X.first.Profile(ID);
59  ID.AddPointer( (void*) X.second);
60  }
61 };
62 
63 template<> struct FoldingSetTrait<SValPair> {
64  static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
65  X.first.Profile(ID);
66  X.second.Profile(ID);
67  }
68 };
69 
70 } // namespace llvm
71 
72 using PersistentSValsTy =
73  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
74 
76  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
77 
79  // Note that the dstor for the contents of APSIntSet will never be called,
80  // so we iterate over the set and invoke the dstor for each APSInt. This
81  // frees an aux. memory allocated to represent very large constants.
82  for (const auto &I : APSIntSet)
83  I.getValue().~APSInt();
84 
85  delete (PersistentSValsTy*) PersistentSVals;
86  delete (PersistentSValPairsTy*) PersistentSValPairs;
87 }
88 
89 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
90  llvm::FoldingSetNodeID ID;
91  void *InsertPos;
92 
93  using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>;
94 
95  X.Profile(ID);
96  FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
97 
98  if (!P) {
99  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
100  new (P) FoldNodeTy(X);
101  APSIntSet.InsertNode(P, InsertPos);
102  }
103 
104  return *P;
105 }
106 
107 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
108  bool isUnsigned) {
109  llvm::APSInt V(X, isUnsigned);
110  return getValue(V);
111 }
112 
113 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
114  bool isUnsigned) {
115  llvm::APSInt V(BitWidth, isUnsigned);
116  V = X;
117  return getValue(V);
118 }
119 
120 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
121  return getValue(getAPSIntType(T).getValue(X));
122 }
123 
124 const CompoundValData*
126  llvm::ImmutableList<SVal> Vals) {
127  llvm::FoldingSetNodeID ID;
128  CompoundValData::Profile(ID, T, Vals);
129  void *InsertPos;
130 
131  CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
132 
133  if (!D) {
134  D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
135  new (D) CompoundValData(T, Vals);
136  CompoundValDataSet.InsertNode(D, InsertPos);
137  }
138 
139  return D;
140 }
141 
142 const LazyCompoundValData*
144  const TypedValueRegion *region) {
145  llvm::FoldingSetNodeID ID;
146  LazyCompoundValData::Profile(ID, store, region);
147  void *InsertPos;
148 
150  LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
151 
152  if (!D) {
153  D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
154  new (D) LazyCompoundValData(store, region);
155  LazyCompoundValDataSet.InsertNode(D, InsertPos);
156  }
157 
158  return D;
159 }
160 
162  const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
163  llvm::FoldingSetNodeID ID;
164  PointerToMemberData::Profile(ID, DD, L);
165  void *InsertPos;
166 
168  PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
169 
170  if (!D) {
171  D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
172  new (D) PointerToMemberData(DD, L);
173  PointerToMemberDataSet.InsertNode(D, InsertPos);
174  }
175 
176  return D;
177 }
178 
180  llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
181  const nonloc::PointerToMember &PTM) {
183  const DeclaratorDecl *DD = nullptr;
184  llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
185 
186  if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
187  if (PTMDT.is<const DeclaratorDecl *>())
188  DD = PTMDT.get<const DeclaratorDecl *>();
189 
190  PathList = CXXBaseListFactory.getEmptyList();
191  } else { // const PointerToMemberData *
192  const PointerToMemberData *PTMD =
193  PTMDT.get<const PointerToMemberData *>();
194  DD = PTMD->getDeclaratorDecl();
195 
196  PathList = PTMD->getCXXBaseList();
197  }
198 
199  for (const auto &I : llvm::reverse(PathRange))
200  PathList = prependCXXBase(I, PathList);
201  return getPointerToMemberData(DD, PathList);
202 }
203 
204 const llvm::APSInt*
206  const llvm::APSInt& V1, const llvm::APSInt& V2) {
207  switch (Op) {
208  default:
209  llvm_unreachable("Invalid Opcode.");
210 
211  case BO_Mul:
212  return &getValue( V1 * V2 );
213 
214  case BO_Div:
215  if (V2 == 0) // Avoid division by zero
216  return nullptr;
217  return &getValue( V1 / V2 );
218 
219  case BO_Rem:
220  if (V2 == 0) // Avoid division by zero
221  return nullptr;
222  return &getValue( V1 % V2 );
223 
224  case BO_Add:
225  return &getValue( V1 + V2 );
226 
227  case BO_Sub:
228  return &getValue( V1 - V2 );
229 
230  case BO_Shl: {
231  // FIXME: This logic should probably go higher up, where we can
232  // test these conditions symbolically.
233 
234  if (V2.isSigned() && V2.isNegative())
235  return nullptr;
236 
237  uint64_t Amt = V2.getZExtValue();
238 
239  if (Amt >= V1.getBitWidth())
240  return nullptr;
241 
242  if (!Ctx.getLangOpts().CPlusPlus2a) {
243  if (V1.isSigned() && V1.isNegative())
244  return nullptr;
245 
246  if (V1.isSigned() && Amt > V1.countLeadingZeros())
247  return nullptr;
248  }
249 
250  return &getValue( V1.operator<<( (unsigned) Amt ));
251  }
252 
253  case BO_Shr: {
254  // FIXME: This logic should probably go higher up, where we can
255  // test these conditions symbolically.
256 
257  if (V2.isSigned() && V2.isNegative())
258  return nullptr;
259 
260  uint64_t Amt = V2.getZExtValue();
261 
262  if (Amt >= V1.getBitWidth())
263  return nullptr;
264 
265  return &getValue( V1.operator>>( (unsigned) Amt ));
266  }
267 
268  case BO_LT:
269  return &getTruthValue( V1 < V2 );
270 
271  case BO_GT:
272  return &getTruthValue( V1 > V2 );
273 
274  case BO_LE:
275  return &getTruthValue( V1 <= V2 );
276 
277  case BO_GE:
278  return &getTruthValue( V1 >= V2 );
279 
280  case BO_EQ:
281  return &getTruthValue( V1 == V2 );
282 
283  case BO_NE:
284  return &getTruthValue( V1 != V2 );
285 
286  // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
287 
288  case BO_And:
289  return &getValue( V1 & V2 );
290 
291  case BO_Or:
292  return &getValue( V1 | V2 );
293 
294  case BO_Xor:
295  return &getValue( V1 ^ V2 );
296  }
297 }
298 
299 const std::pair<SVal, uintptr_t>&
301  // Lazily create the folding set.
302  if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
303 
304  llvm::FoldingSetNodeID ID;
305  void *InsertPos;
306  V.Profile(ID);
307  ID.AddPointer((void*) Data);
308 
309  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
310 
311  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
312 
313  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
314 
315  if (!P) {
316  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
317  new (P) FoldNodeTy(std::make_pair(V, Data));
318  Map.InsertNode(P, InsertPos);
319  }
320 
321  return P->getValue();
322 }
323 
324 const std::pair<SVal, SVal>&
326  // Lazily create the folding set.
327  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
328 
329  llvm::FoldingSetNodeID ID;
330  void *InsertPos;
331  V1.Profile(ID);
332  V2.Profile(ID);
333 
334  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
335 
336  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
337 
338  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
339 
340  if (!P) {
341  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
342  new (P) FoldNodeTy(std::make_pair(V1, V2));
343  Map.InsertNode(P, InsertPos);
344  }
345 
346  return P->getValue();
347 }
348 
350  return &getPersistentSValWithData(X, 0).first;
351 }
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:530
A (possibly-)qualified type.
Definition: Type.h:643
Store getStore() const
Definition: StoreRef.h:46
llvm::ImmutableList< const CXXBaseSpecifier * > getCXXBaseList() const
Specialize PointerLikeTypeTraits to allow LazyGenerationalUpdatePtr to be placed into a PointerUnion...
Definition: Dominators.h:30
const CompoundValData * getCompoundValData(QualType T, llvm::ImmutableList< SVal > Vals)
const std::pair< SVal, SVal > & getPersistentSValPair(const SVal &V1, const SVal &V2)
StringRef P
std::pair< SVal, SVal > SValPair
const PointerToMemberData * accumCXXBase(llvm::iterator_range< CastExpr::path_const_iterator > PathRange, const nonloc::PointerToMember &PTM)
const PTMDataType getPTMData() const
Definition: SVals.h:531
const DeclaratorDecl * getDeclaratorDecl() const
Value representing pointer-to-member.
Definition: SVals.h:524
BinaryOperatorKind
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValData > > PersistentSValsTy
const SVal * getPersistentSVal(SVal X)
Represents a ValueDecl that came out of a declarator.
Definition: Decl.h:696
const PointerToMemberData * getPointerToMemberData(const DeclaratorDecl *DD, llvm::ImmutableList< const CXXBaseSpecifier *> L)
#define V(N, I)
Definition: ASTContext.h:2921
__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-base.h:62
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: Type.h:1045
static SVal getValue(SVal val, SValBuilder &svalBuilder)
static void Profile(llvm::FoldingSetNodeID &ID, const StoreRef &store, const TypedValueRegion *region)
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: SVals.h:123
llvm::APSInt APSInt
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:75
llvm::APInt APInt
Definition: Integral.h:27
const llvm::APSInt * evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1, const llvm::APSInt &V2)
Dataflow Directional Tag Classes.
std::pair< SVal, uintptr_t > SValData
static void Profile(llvm::FoldingSetNodeID &ID, QualType T, llvm::ImmutableList< SVal > L)
static void Profile(llvm::FoldingSetNodeID &ID, const DeclaratorDecl *D, llvm::ImmutableList< const CXXBaseSpecifier *> L)
llvm::PointerUnion< const DeclaratorDecl *, const PointerToMemberData * > PTMDataType
Definition: SVals.h:529
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:14652
const LazyCompoundValData * getLazyCompoundValData(const StoreRef &store, const TypedValueRegion *region)
static void Profile(const SValData &X, llvm::FoldingSetNodeID &ID)
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValPair > > PersistentSValPairsTy
CompoundValData(QualType t, llvm::ImmutableList< SVal > l)