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 <cassert>
25#include <cstdint>
26#include <utility>
27
28using namespace clang;
29using namespace ento;
30
31void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
32                              llvm::ImmutableList<SVal> L) {
33  T.Profile(ID);
34  ID.AddPointer(L.getInternalPointer());
35}
36
37void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
38                                  const StoreRef &store,
39                                  const TypedValueRegion *region) {
40  ID.AddPointer(store.getStore());
41  ID.AddPointer(region);
42}
43
44void PointerToMemberData::Profile(
45    llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
46    llvm::ImmutableList<const CXXBaseSpecifier *> L) {
47  ID.AddPointer(D);
48  ID.AddPointer(L.getInternalPointer());
49}
50
51using SValData = std::pair<SVal, uintptr_t>;
52using SValPair = std::pair<SVal, SVal>;
53
54namespace llvm {
55
56template<> 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
63template<> 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
72using PersistentSValsTy =
73    llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
74
75using PersistentSValPairsTy =
76    llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
77
78BasicValueFactory::~BasicValueFactory() {
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
89const 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
107const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
108                                                bool isUnsigned) {
109  llvm::APSInt V(X, isUnsigned);
110  return getValue(V);
111}
112
113const 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
120const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
121  return getValue(getAPSIntType(T).getValue(X));
122}
123
124const CompoundValData*
125BasicValueFactory::getCompoundValData(QualType T,
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
142const LazyCompoundValData*
143BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
144                                          const TypedValueRegion *region) {
145  llvm::FoldingSetNodeID ID;
146  LazyCompoundValData::Profile(ID, store, region);
147  void *InsertPos;
148
149  LazyCompoundValData *D =
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
161const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
162    const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
163  llvm::FoldingSetNodeID ID;
164  PointerToMemberData::Profile(ID, DD, L);
165  void *InsertPos;
166
167  PointerToMemberData *D =
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
179const PointerToMemberData *BasicValueFactory::accumCXXBase(
180    llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
181    const nonloc::PointerToMember &PTM) {
182  nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
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
204const llvm::APSInt*
205BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
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
299const std::pair<SVal, uintptr_t>&
300BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
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
324const std::pair<SVal, SVal>&
325BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
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
349const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
350  return &getPersistentSValWithData(X, 0).first;
351}
352