clang  14.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 "llvm/ADT/SmallPtrSet.h"
25 #include <cassert>
26 #include <cstdint>
27 #include <utility>
28 
29 using namespace clang;
30 using namespace ento;
31 
32 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
33  llvm::ImmutableList<SVal> L) {
34  T.Profile(ID);
35  ID.AddPointer(L.getInternalPointer());
36 }
37 
38 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
39  const StoreRef &store,
40  const TypedValueRegion *region) {
41  ID.AddPointer(store.getStore());
42  ID.AddPointer(region);
43 }
44 
46  llvm::FoldingSetNodeID &ID, const NamedDecl *D,
47  llvm::ImmutableList<const CXXBaseSpecifier *> L) {
48  ID.AddPointer(D);
49  ID.AddPointer(L.getInternalPointer());
50 }
51 
52 using SValData = std::pair<SVal, uintptr_t>;
53 using SValPair = std::pair<SVal, SVal>;
54 
55 namespace llvm {
56 
57 template<> struct FoldingSetTrait<SValData> {
58  static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
59  X.first.Profile(ID);
60  ID.AddPointer( (void*) X.second);
61  }
62 };
63 
64 template<> struct FoldingSetTrait<SValPair> {
65  static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
66  X.first.Profile(ID);
67  X.second.Profile(ID);
68  }
69 };
70 
71 } // namespace llvm
72 
73 using PersistentSValsTy =
74  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
75 
77  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78 
80  // Note that the dstor for the contents of APSIntSet will never be called,
81  // so we iterate over the set and invoke the dstor for each APSInt. This
82  // frees an aux. memory allocated to represent very large constants.
83  for (const auto &I : APSIntSet)
84  I.getValue().~APSInt();
85 
86  delete (PersistentSValsTy*) PersistentSVals;
87  delete (PersistentSValPairsTy*) PersistentSValPairs;
88 }
89 
90 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
91  llvm::FoldingSetNodeID ID;
92  void *InsertPos;
93 
94  using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>;
95 
96  X.Profile(ID);
97  FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
98 
99  if (!P) {
100  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
101  new (P) FoldNodeTy(X);
102  APSIntSet.InsertNode(P, InsertPos);
103  }
104 
105  return *P;
106 }
107 
108 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
109  bool isUnsigned) {
110  llvm::APSInt V(X, isUnsigned);
111  return getValue(V);
112 }
113 
114 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
115  bool isUnsigned) {
116  llvm::APSInt V(BitWidth, isUnsigned);
117  V = X;
118  return getValue(V);
119 }
120 
121 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
122  return getValue(getAPSIntType(T).getValue(X));
123 }
124 
125 const CompoundValData*
127  llvm::ImmutableList<SVal> Vals) {
128  llvm::FoldingSetNodeID ID;
129  CompoundValData::Profile(ID, T, Vals);
130  void *InsertPos;
131 
132  CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
133 
134  if (!D) {
135  D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
136  new (D) CompoundValData(T, Vals);
137  CompoundValDataSet.InsertNode(D, InsertPos);
138  }
139 
140  return D;
141 }
142 
143 const LazyCompoundValData*
145  const TypedValueRegion *region) {
146  llvm::FoldingSetNodeID ID;
147  LazyCompoundValData::Profile(ID, store, region);
148  void *InsertPos;
149 
151  LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
152 
153  if (!D) {
154  D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
155  new (D) LazyCompoundValData(store, region);
156  LazyCompoundValDataSet.InsertNode(D, InsertPos);
157  }
158 
159  return D;
160 }
161 
163  const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
164  llvm::FoldingSetNodeID ID;
166  void *InsertPos;
167 
169  PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
170 
171  if (!D) {
172  D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>();
173  new (D) PointerToMemberData(ND, L);
174  PointerToMemberDataSet.InsertNode(D, InsertPos);
175  }
176 
177  return D;
178 }
179 
180 LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(
181  llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) {
182  llvm::SmallPtrSet<QualType, 16> BaseSpecSeen;
183  for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
184  QualType BaseType = BaseSpec->getType();
185  // Check whether inserted
186  if (!BaseSpecSeen.insert(BaseType).second)
187  return false;
188  }
189  return true;
190 }
191 
193  llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
194  const nonloc::PointerToMember &PTM, const CastKind &kind) {
195  assert((kind == CK_DerivedToBaseMemberPointer ||
196  kind == CK_BaseToDerivedMemberPointer ||
197  kind == CK_ReinterpretMemberPointer) &&
198  "accumCXXBase called with wrong CastKind");
200  const NamedDecl *ND = nullptr;
201  llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
202 
203  if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
204  if (PTMDT.is<const NamedDecl *>())
205  ND = PTMDT.get<const NamedDecl *>();
206 
207  BaseSpecList = CXXBaseListFactory.getEmptyList();
208  } else {
209  const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
210  ND = PTMD->getDeclaratorDecl();
211 
212  BaseSpecList = PTMD->getCXXBaseList();
213  }
214 
215  assert(hasNoRepeatedElements(BaseSpecList) &&
216  "CXXBaseSpecifier list of PointerToMemberData must not have repeated "
217  "elements");
218 
219  if (kind == CK_DerivedToBaseMemberPointer) {
220  // Here we pop off matching CXXBaseSpecifiers from BaseSpecList.
221  // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and
222  // serves to remove a matching implicit cast. Note that static_cast's that
223  // are no-ops do not count since they produce an empty PathRange, a nice
224  // thing about Clang AST.
225 
226  // Now we know that there are no repetitions in BaseSpecList.
227  // So, popping the first element from it corresponding to each element in
228  // PathRange is equivalent to only including elements that are in
229  // BaseSpecList but not it PathRange
230  auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList();
231  for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
232  auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool {
233  return BaseSpec->getType() == I->getType();
234  };
235  if (llvm::none_of(PathRange, IsSameAsBaseSpec))
236  ReducedBaseSpecList =
237  CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList);
238  }
239 
240  return getPointerToMemberData(ND, ReducedBaseSpecList);
241  }
242  // FIXME: Reinterpret casts on member-pointers are not handled properly by
243  // this code
244  for (const CXXBaseSpecifier *I : llvm::reverse(PathRange))
245  BaseSpecList = prependCXXBase(I, BaseSpecList);
246  return getPointerToMemberData(ND, BaseSpecList);
247 }
248 
249 const llvm::APSInt*
251  const llvm::APSInt& V1, const llvm::APSInt& V2) {
252  switch (Op) {
253  default:
254  llvm_unreachable("Invalid Opcode.");
255 
256  case BO_Mul:
257  return &getValue( V1 * V2 );
258 
259  case BO_Div:
260  if (V2 == 0) // Avoid division by zero
261  return nullptr;
262  return &getValue( V1 / V2 );
263 
264  case BO_Rem:
265  if (V2 == 0) // Avoid division by zero
266  return nullptr;
267  return &getValue( V1 % V2 );
268 
269  case BO_Add:
270  return &getValue( V1 + V2 );
271 
272  case BO_Sub:
273  return &getValue( V1 - V2 );
274 
275  case BO_Shl: {
276  // FIXME: This logic should probably go higher up, where we can
277  // test these conditions symbolically.
278 
279  if (V2.isSigned() && V2.isNegative())
280  return nullptr;
281 
282  uint64_t Amt = V2.getZExtValue();
283 
284  if (Amt >= V1.getBitWidth())
285  return nullptr;
286 
287  if (!Ctx.getLangOpts().CPlusPlus20) {
288  if (V1.isSigned() && V1.isNegative())
289  return nullptr;
290 
291  if (V1.isSigned() && Amt > V1.countLeadingZeros())
292  return nullptr;
293  }
294 
295  return &getValue( V1.operator<<( (unsigned) Amt ));
296  }
297 
298  case BO_Shr: {
299  // FIXME: This logic should probably go higher up, where we can
300  // test these conditions symbolically.
301 
302  if (V2.isSigned() && V2.isNegative())
303  return nullptr;
304 
305  uint64_t Amt = V2.getZExtValue();
306 
307  if (Amt >= V1.getBitWidth())
308  return nullptr;
309 
310  return &getValue( V1.operator>>( (unsigned) Amt ));
311  }
312 
313  case BO_LT:
314  return &getTruthValue( V1 < V2 );
315 
316  case BO_GT:
317  return &getTruthValue( V1 > V2 );
318 
319  case BO_LE:
320  return &getTruthValue( V1 <= V2 );
321 
322  case BO_GE:
323  return &getTruthValue( V1 >= V2 );
324 
325  case BO_EQ:
326  return &getTruthValue( V1 == V2 );
327 
328  case BO_NE:
329  return &getTruthValue( V1 != V2 );
330 
331  // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
332 
333  case BO_And:
334  return &getValue( V1 & V2 );
335 
336  case BO_Or:
337  return &getValue( V1 | V2 );
338 
339  case BO_Xor:
340  return &getValue( V1 ^ V2 );
341  }
342 }
343 
344 const std::pair<SVal, uintptr_t>&
346  // Lazily create the folding set.
347  if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
348 
349  llvm::FoldingSetNodeID ID;
350  void *InsertPos;
351  V.Profile(ID);
352  ID.AddPointer((void*) Data);
353 
354  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
355 
356  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
357 
358  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
359 
360  if (!P) {
361  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
362  new (P) FoldNodeTy(std::make_pair(V, Data));
363  Map.InsertNode(P, InsertPos);
364  }
365 
366  return P->getValue();
367 }
368 
369 const std::pair<SVal, SVal>&
371  // Lazily create the folding set.
372  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
373 
374  llvm::FoldingSetNodeID ID;
375  void *InsertPos;
376  V1.Profile(ID);
377  V2.Profile(ID);
378 
379  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
380 
381  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
382 
383  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
384 
385  if (!P) {
386  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
387  new (P) FoldNodeTy(std::make_pair(V1, V2));
388  Map.InsertNode(P, InsertPos);
389  }
390 
391  return P->getValue();
392 }
393 
395  return &getPersistentSValWithData(X, 0).first;
396 }
clang::ento::BasicValueFactory::getPersistentSValWithData
const std::pair< SVal, uintptr_t > & getPersistentSValWithData(const SVal &V, uintptr_t Data)
Definition: BasicValueFactory.cpp:345
clang::ento::BasicValueFactory::~BasicValueFactory
~BasicValueFactory()
Definition: BasicValueFactory.cpp:79
llvm
Definition: Dominators.h:30
clang::interp::APInt
llvm::APInt APInt
Definition: Integral.h:27
clang::ento::LazyCompoundValData
Definition: BasicValueFactory.h:63
clang::ento::SVal::Profile
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: SVals.h:123
clang::ento::BasicValueFactory::prependCXXBase
llvm::ImmutableList< const CXXBaseSpecifier * > prependCXXBase(const CXXBaseSpecifier *CBS, llvm::ImmutableList< const CXXBaseSpecifier * > L)
Definition: BasicValueFactory.h:263
clang::ento::CompoundValData
Definition: BasicValueFactory.h:41
SVals.h
SValPair
std::pair< SVal, SVal > SValPair
Definition: BasicValueFactory.cpp:53
clang::NamedDecl
This represents a decl that may have a name.
Definition: Decl.h:249
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:673
clang::ento::BasicValueFactory::getPersistentSVal
const SVal * getPersistentSVal(SVal X)
Definition: BasicValueFactory.cpp:394
clang::ento::PointerToMemberData::getDeclaratorDecl
const NamedDecl * getDeclaratorDecl() const
Definition: BasicValueFactory.h:101
llvm::SmallPtrSet
Definition: ASTContext.h:82
clang::tooling::X
static ToolExecutorPluginRegistry::Add< AllTUsToolExecutorPlugin > X("all-TUs", "Runs FrontendActions on all TUs in the compilation database. " "Tool results are stored in memory.")
clang::ento::BasicValueFactory::getCompoundValData
const CompoundValData * getCompoundValData(QualType T, llvm::ImmutableList< SVal > Vals)
Definition: BasicValueFactory.cpp:126
clang::ento::PointerToMemberData::Profile
static void Profile(llvm::FoldingSetNodeID &ID, const NamedDecl *D, llvm::ImmutableList< const CXXBaseSpecifier * > L)
Definition: BasicValueFactory.cpp:45
clang::ento::BasicValueFactory::getPointerToMemberData
const PointerToMemberData * getPointerToMemberData(const NamedDecl *ND, llvm::ImmutableList< const CXXBaseSpecifier * > L)
Definition: BasicValueFactory.cpp:162
clang::ento::BasicValueFactory::accumCXXBase
const PointerToMemberData * accumCXXBase(llvm::iterator_range< CastExpr::path_const_iterator > PathRange, const nonloc::PointerToMember &PTM, const clang::CastKind &kind)
Definition: BasicValueFactory.cpp:192
llvm::FoldingSetTrait< SValPair >::Profile
static void Profile(const SValPair &X, llvm::FoldingSetNodeID &ID)
Definition: BasicValueFactory.cpp:65
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
V
#define V(N, I)
Definition: ASTContext.h:3121
clang::ento::StoreRef::getStore
Store getStore() const
Definition: StoreRef.h:46
PersistentSValsTy
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValData > > PersistentSValsTy
Definition: BasicValueFactory.cpp:74
clang::ento::StoreRef
Definition: StoreRef.h:29
Store.h
clang::ento::nonloc::PointerToMember
Value representing pointer-to-member.
Definition: SVals.h:532
clang::ento::nonloc::PointerToMember::getPTMData
const PTMDataType getPTMData() const
Definition: SVals.h:539
uintptr_t
__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:124
llvm::FoldingSetTrait
Definition: SourceLocation.h:29
BasicValueFactory.h
llvm::FoldingSetTrait< SValData >::Profile
static void Profile(const SValData &X, llvm::FoldingSetNodeID &ID)
Definition: BasicValueFactory.cpp:58
clang::ento::CompoundValData::Profile
static void Profile(llvm::FoldingSetNodeID &ID, QualType T, llvm::ImmutableList< SVal > L)
Definition: BasicValueFactory.cpp:32
clang::ento::LazyCompoundValData::Profile
static void Profile(llvm::FoldingSetNodeID &ID, const StoreRef &store, const TypedValueRegion *region)
Definition: BasicValueFactory.cpp:38
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::ento::nonloc::PointerToMember::PTMDataType
llvm::PointerUnion< const NamedDecl *, const PointerToMemberData * > PTMDataType
Definition: SVals.h:537
clang::ento::BasicValueFactory::getLazyCompoundValData
const LazyCompoundValData * getLazyCompoundValData(const StoreRef &store, const TypedValueRegion *region)
Definition: BasicValueFactory.cpp:144
APSIntType.h
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
clang::QualType::Profile
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: Type.h:1081
clang::Builtin::ID
ID
Definition: Builtins.h:48
clang
Definition: CalledOnceCheck.h:17
clang::ento::PointerToMemberData::getCXXBaseList
llvm::ImmutableList< const CXXBaseSpecifier * > getCXXBaseList() const
Definition: BasicValueFactory.h:103
SValData
std::pair< SVal, uintptr_t > SValData
Definition: BasicValueFactory.cpp:52
clang::CXXBaseSpecifier
Represents a base class of a C++ class.
Definition: DeclCXX.h:147
clang::ento::BasicValueFactory::evalAPSInt
const llvm::APSInt * evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1, const llvm::APSInt &V2)
Definition: BasicValueFactory.cpp:250
clang::ento::PointerToMemberData
Definition: BasicValueFactory.h:83
clang::ento::SVal
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:75
PersistentSValPairsTy
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValPair > > PersistentSValPairsTy
Definition: BasicValueFactory.cpp:77
clang::ento::TypedValueRegion
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:522
clang::CastKind
CastKind
CastKind - The kind of operation required for a conversion.
Definition: OperationKinds.h:20
hasNoRepeatedElements
LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(llvm::ImmutableList< const CXXBaseSpecifier * > BaseSpecList)
Definition: BasicValueFactory.cpp:180
StoreRef.h
clang::diag::kind
unsigned kind
All of the diagnostics that can be emitted by the frontend.
Definition: DiagnosticIDs.h:62
clang::ento::BasicValueFactory::getAPSIntType
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
Definition: BasicValueFactory.h:143
clang::ASTContext::getLangOpts
const LangOptions & getLangOpts() const
Definition: ASTContext.h:765
clang::ento::BasicValueFactory::getTruthValue
const llvm::APSInt & getTruthValue(bool b, QualType T)
Definition: BasicValueFactory.h:232
clang::ento::BasicValueFactory::getPersistentSValPair
const std::pair< SVal, SVal > & getPersistentSValPair(const SVal &V1, const SVal &V2)
Definition: BasicValueFactory.cpp:370