Clang Project

clang_source_code/lib/StaticAnalyzer/Core/BasicValueFactory.cpp
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 (V1.isSigned() && V1.isNegative())
235        return nullptr;
236
237      if (V2.isSigned() && V2.isNegative())
238        return nullptr;
239
240      uint64_t Amt = V2.getZExtValue();
241
242      if (Amt >= V1.getBitWidth())
243        return nullptr;
244
245      if (V1.isSigned() && Amt > V1.countLeadingZeros())
246          return nullptr;
247
248      return &getValue( V1.operator<<( (unsigned) Amt ));
249    }
250
251    case BO_Shr: {
252      // FIXME: This logic should probably go higher up, where we can
253      // test these conditions symbolically.
254
255      if (V2.isSigned() && V2.isNegative())
256        return nullptr;
257
258      uint64_t Amt = V2.getZExtValue();
259
260      if (Amt >= V1.getBitWidth())
261        return nullptr;
262
263      return &getValue( V1.operator>>( (unsigned) Amt ));
264    }
265
266    case BO_LT:
267      return &getTruthValue( V1 < V2 );
268
269    case BO_GT:
270      return &getTruthValue( V1 > V2 );
271
272    case BO_LE:
273      return &getTruthValue( V1 <= V2 );
274
275    case BO_GE:
276      return &getTruthValue( V1 >= V2 );
277
278    case BO_EQ:
279      return &getTruthValue( V1 == V2 );
280
281    case BO_NE:
282      return &getTruthValue( V1 != V2 );
283
284      // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
285
286    case BO_And:
287      return &getValue( V1 & V2 );
288
289    case BO_Or:
290      return &getValue( V1 | V2 );
291
292    case BO_Xor:
293      return &getValue( V1 ^ V2 );
294  }
295}
296
297const std::pair<SVal, uintptr_t>&
298BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
299  // Lazily create the folding set.
300  if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
301
302  llvm::FoldingSetNodeID ID;
303  void *InsertPos;
304  V.Profile(ID);
305  ID.AddPointer((void*) Data);
306
307  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
308
309  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
310
311  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
312
313  if (!P) {
314    P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
315    new (P) FoldNodeTy(std::make_pair(V, Data));
316    Map.InsertNode(P, InsertPos);
317  }
318
319  return P->getValue();
320}
321
322const std::pair<SVal, SVal>&
323BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
324  // Lazily create the folding set.
325  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
326
327  llvm::FoldingSetNodeID ID;
328  void *InsertPos;
329  V1.Profile(ID);
330  V2.Profile(ID);
331
332  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
333
334  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
335
336  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
337
338  if (!P) {
339    P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
340    new (P) FoldNodeTy(std::make_pair(V1, V2));
341    Map.InsertNode(P, InsertPos);
342  }
343
344  return P->getValue();
345}
346
347const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
348  return &getPersistentSValWithData(X, 0).first;
349}
350
clang::ento::CompoundValData::Profile
clang::ento::LazyCompoundValData::Profile
clang::ento::PointerToMemberData::Profile
clang::ento::BasicValueFactory::getValue
clang::ento::BasicValueFactory::getValue
clang::ento::BasicValueFactory::getValue
clang::ento::BasicValueFactory::getValue
clang::ento::BasicValueFactory::getCompoundValData
clang::ento::BasicValueFactory::getLazyCompoundValData
clang::ento::BasicValueFactory::getPointerToMemberData
CodeThinker, Enjoy your reading code