clang  12.0.0git
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 NamedDecl *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 NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
163  llvm::FoldingSetNodeID ID;
165  void *InsertPos;
166 
168  PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
169 
170  if (!D) {
171  D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>();
172  new (D) PointerToMemberData(ND, 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 NamedDecl *ND = nullptr;
184  llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
185 
186  if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
187  if (PTMDT.is<const NamedDecl *>())
188  ND = PTMDT.get<const NamedDecl *>();
189 
190  PathList = CXXBaseListFactory.getEmptyList();
191  } else { // const PointerToMemberData *
192  const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
193  ND = PTMD->getDeclaratorDecl();
194 
195  PathList = PTMD->getCXXBaseList();
196  }
197 
198  for (const auto &I : llvm::reverse(PathRange))
199  PathList = prependCXXBase(I, PathList);
200  return getPointerToMemberData(ND, PathList);
201 }
202 
203 const llvm::APSInt*
205  const llvm::APSInt& V1, const llvm::APSInt& V2) {
206  switch (Op) {
207  default:
208  llvm_unreachable("Invalid Opcode.");
209 
210  case BO_Mul:
211  return &getValue( V1 * V2 );
212 
213  case BO_Div:
214  if (V2 == 0) // Avoid division by zero
215  return nullptr;
216  return &getValue( V1 / V2 );
217 
218  case BO_Rem:
219  if (V2 == 0) // Avoid division by zero
220  return nullptr;
221  return &getValue( V1 % V2 );
222 
223  case BO_Add:
224  return &getValue( V1 + V2 );
225 
226  case BO_Sub:
227  return &getValue( V1 - V2 );
228 
229  case BO_Shl: {
230  // FIXME: This logic should probably go higher up, where we can
231  // test these conditions symbolically.
232 
233  if (V2.isSigned() && V2.isNegative())
234  return nullptr;
235 
236  uint64_t Amt = V2.getZExtValue();
237 
238  if (Amt >= V1.getBitWidth())
239  return nullptr;
240 
241  if (!Ctx.getLangOpts().CPlusPlus20) {
242  if (V1.isSigned() && V1.isNegative())
243  return nullptr;
244 
245  if (V1.isSigned() && Amt > V1.countLeadingZeros())
246  return nullptr;
247  }
248 
249  return &getValue( V1.operator<<( (unsigned) Amt ));
250  }
251 
252  case BO_Shr: {
253  // FIXME: This logic should probably go higher up, where we can
254  // test these conditions symbolically.
255 
256  if (V2.isSigned() && V2.isNegative())
257  return nullptr;
258 
259  uint64_t Amt = V2.getZExtValue();
260 
261  if (Amt >= V1.getBitWidth())
262  return nullptr;
263 
264  return &getValue( V1.operator>>( (unsigned) Amt ));
265  }
266 
267  case BO_LT:
268  return &getTruthValue( V1 < V2 );
269 
270  case BO_GT:
271  return &getTruthValue( V1 > V2 );
272 
273  case BO_LE:
274  return &getTruthValue( V1 <= V2 );
275 
276  case BO_GE:
277  return &getTruthValue( V1 >= V2 );
278 
279  case BO_EQ:
280  return &getTruthValue( V1 == V2 );
281 
282  case BO_NE:
283  return &getTruthValue( V1 != V2 );
284 
285  // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
286 
287  case BO_And:
288  return &getValue( V1 & V2 );
289 
290  case BO_Or:
291  return &getValue( V1 | V2 );
292 
293  case BO_Xor:
294  return &getValue( V1 ^ V2 );
295  }
296 }
297 
298 const std::pair<SVal, uintptr_t>&
300  // Lazily create the folding set.
301  if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
302 
303  llvm::FoldingSetNodeID ID;
304  void *InsertPos;
305  V.Profile(ID);
306  ID.AddPointer((void*) Data);
307 
308  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
309 
310  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
311 
312  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
313 
314  if (!P) {
315  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
316  new (P) FoldNodeTy(std::make_pair(V, Data));
317  Map.InsertNode(P, InsertPos);
318  }
319 
320  return P->getValue();
321 }
322 
323 const std::pair<SVal, SVal>&
325  // Lazily create the folding set.
326  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
327 
328  llvm::FoldingSetNodeID ID;
329  void *InsertPos;
330  V1.Profile(ID);
331  V2.Profile(ID);
332 
333  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
334 
335  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
336 
337  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
338 
339  if (!P) {
340  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
341  new (P) FoldNodeTy(std::make_pair(V1, V2));
342  Map.InsertNode(P, InsertPos);
343  }
344 
345  return P->getValue();
346 }
347 
349  return &getPersistentSValWithData(X, 0).first;
350 }
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:522
A (possibly-)qualified type.
Definition: Type.h:661
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 llvm::APSInt & getTruthValue(bool b, QualType T)
const PTMDataType getPTMData() const
Definition: SVals.h:525
Value representing pointer-to-member.
Definition: SVals.h:518
llvm::ImmutableList< const CXXBaseSpecifier * > prependCXXBase(const CXXBaseSpecifier *CBS, llvm::ImmutableList< const CXXBaseSpecifier * > L)
BinaryOperatorKind
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValData > > PersistentSValsTy
const PointerToMemberData * getPointerToMemberData(const NamedDecl *ND, llvm::ImmutableList< const CXXBaseSpecifier * > L)
const SVal * getPersistentSVal(SVal X)
#define V(N, I)
Definition: ASTContext.h:2983
__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:1069
static void Profile(llvm::FoldingSetNodeID &ID, const StoreRef &store, const TypedValueRegion *region)
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: SVals.h:123
llvm::PointerUnion< const NamedDecl *, const PointerToMemberData * > PTMDataType
Definition: SVals.h:523
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)
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
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:15282
const NamedDecl * getDeclaratorDecl() const
const LazyCompoundValData * getLazyCompoundValData(const StoreRef &store, const TypedValueRegion *region)
static void Profile(llvm::FoldingSetNodeID &ID, const NamedDecl *D, llvm::ImmutableList< const CXXBaseSpecifier * > L)
static void Profile(const SValData &X, llvm::FoldingSetNodeID &ID)
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValPair > > PersistentSValPairsTy
This represents a decl that may have a name.
Definition: Decl.h:223
const LangOptions & getLangOpts() const
Definition: ASTContext.h:675