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
15#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
16#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
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
29using namespace clang;
30using namespace ento;
31
32void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
33                              llvm::ImmutableList<SVal> L) {
34  T.Profile(ID);
35  ID.AddPointer(L.getInternalPointer());
36}
37
38void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
39                                  const StoreRef &store,
40                                  const TypedValueRegion *region) {
41  ID.AddPointer(store.getStore());
42  ID.AddPointer(region);
43}
44
45void PointerToMemberData::Profile(
46    llvm::FoldingSetNodeID &ID, const NamedDecl *D,
47    llvm::ImmutableList<const CXXBaseSpecifier *> L) {
48  ID.AddPointer(D);
49  ID.AddPointer(L.getInternalPointer());
50}
51
52using SValData = std::pair<SVal, uintptr_t>;
53using SValPair = std::pair<SVal, SVal>;
54
55namespace llvm {
56
57template<> 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
64template<> 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
73using PersistentSValsTy =
74    llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
75
76using PersistentSValPairsTy =
77    llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78
79BasicValueFactory::~BasicValueFactory() {
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
90const 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
108const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
109                                                bool isUnsigned) {
110  llvm::APSInt V(X, isUnsigned);
111  return getValue(V);
112}
113
114const 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
121const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
122  return getValue(getAPSIntType(T).getValue(X));
123}
124
125const CompoundValData*
126BasicValueFactory::getCompoundValData(QualType T,
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
143const LazyCompoundValData*
144BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
145                                          const TypedValueRegion *region) {
146  llvm::FoldingSetNodeID ID;
147  LazyCompoundValData::Profile(ID, store, region);
148  void *InsertPos;
149
150  LazyCompoundValData *D =
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
162const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
163    const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
164  llvm::FoldingSetNodeID ID;
165  PointerToMemberData::Profile(ID, ND, L);
166  void *InsertPos;
167
168  PointerToMemberData *D =
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
180LLVM_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
192const PointerToMemberData *BasicValueFactory::accumCXXBase(
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");
199  nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
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
249const llvm::APSInt*
250BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
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
344const std::pair<SVal, uintptr_t>&
345BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
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
369const std::pair<SVal, SVal>&
370BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
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
394const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
395  return &getPersistentSValWithData(X, 0).first;
396}
397