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 
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 
45 void 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 
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 
76 using PersistentSValPairsTy =
77     llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78 
79 BasicValueFactory::~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 
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 = new (BPAlloc) 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*
125 BasicValueFactory::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 = new (BPAlloc) CompoundValData(T, Vals);
135     CompoundValDataSet.InsertNode(D, InsertPos);
136   }
137 
138   return D;
139 }
140 
141 const LazyCompoundValData*
142 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
143                                           const TypedValueRegion *region) {
144   llvm::FoldingSetNodeID ID;
145   LazyCompoundValData::Profile(ID, store, region);
146   void *InsertPos;
147 
148   LazyCompoundValData *D =
149     LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
150 
151   if (!D) {
152     D = new (BPAlloc) LazyCompoundValData(store, region);
153     LazyCompoundValDataSet.InsertNode(D, InsertPos);
154   }
155 
156   return D;
157 }
158 
159 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
160     const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
161   llvm::FoldingSetNodeID ID;
162   PointerToMemberData::Profile(ID, ND, L);
163   void *InsertPos;
164 
165   PointerToMemberData *D =
166       PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
167 
168   if (!D) {
169     D = new (BPAlloc) PointerToMemberData(ND, L);
170     PointerToMemberDataSet.InsertNode(D, InsertPos);
171   }
172 
173   return D;
174 }
175 
176 LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(
177     llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) {
178   llvm::SmallPtrSet<QualType, 16> BaseSpecSeen;
179   for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
180     QualType BaseType = BaseSpec->getType();
181     // Check whether inserted
182     if (!BaseSpecSeen.insert(BaseType).second)
183       return false;
184   }
185   return true;
186 }
187 
188 const PointerToMemberData *BasicValueFactory::accumCXXBase(
189     llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
190     const nonloc::PointerToMember &PTM, const CastKind &kind) {
191   assert((kind == CK_DerivedToBaseMemberPointer ||
192           kind == CK_BaseToDerivedMemberPointer ||
193           kind == CK_ReinterpretMemberPointer) &&
194          "accumCXXBase called with wrong CastKind");
195   nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
196   const NamedDecl *ND = nullptr;
197   llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
198 
199   if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
200     if (PTMDT.is<const NamedDecl *>())
201       ND = PTMDT.get<const NamedDecl *>();
202 
203     BaseSpecList = CXXBaseListFactory.getEmptyList();
204   } else {
205     const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
206     ND = PTMD->getDeclaratorDecl();
207 
208     BaseSpecList = PTMD->getCXXBaseList();
209   }
210 
211   assert(hasNoRepeatedElements(BaseSpecList) &&
212          "CXXBaseSpecifier list of PointerToMemberData must not have repeated "
213          "elements");
214 
215   if (kind == CK_DerivedToBaseMemberPointer) {
216     // Here we pop off matching CXXBaseSpecifiers from BaseSpecList.
217     // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and
218     // serves to remove a matching implicit cast. Note that static_cast's that
219     // are no-ops do not count since they produce an empty PathRange, a nice
220     // thing about Clang AST.
221 
222     // Now we know that there are no repetitions in BaseSpecList.
223     // So, popping the first element from it corresponding to each element in
224     // PathRange is equivalent to only including elements that are in
225     // BaseSpecList but not it PathRange
226     auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList();
227     for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
228       auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool {
229         return BaseSpec->getType() == I->getType();
230       };
231       if (llvm::none_of(PathRange, IsSameAsBaseSpec))
232         ReducedBaseSpecList =
233             CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList);
234     }
235 
236     return getPointerToMemberData(ND, ReducedBaseSpecList);
237   }
238   // FIXME: Reinterpret casts on member-pointers are not handled properly by
239   // this code
240   for (const CXXBaseSpecifier *I : llvm::reverse(PathRange))
241     BaseSpecList = prependCXXBase(I, BaseSpecList);
242   return getPointerToMemberData(ND, BaseSpecList);
243 }
244 
245 const llvm::APSInt*
246 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
247                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
248   switch (Op) {
249     default:
250       llvm_unreachable("Invalid Opcode.");
251 
252     case BO_Mul:
253       return &getValue( V1 * V2 );
254 
255     case BO_Div:
256       if (V2 == 0) // Avoid division by zero
257         return nullptr;
258       return &getValue( V1 / V2 );
259 
260     case BO_Rem:
261       if (V2 == 0) // Avoid division by zero
262         return nullptr;
263       return &getValue( V1 % V2 );
264 
265     case BO_Add:
266       return &getValue( V1 + V2 );
267 
268     case BO_Sub:
269       return &getValue( V1 - V2 );
270 
271     case BO_Shl: {
272       // FIXME: This logic should probably go higher up, where we can
273       // test these conditions symbolically.
274 
275       if (V2.isSigned() && V2.isNegative())
276         return nullptr;
277 
278       uint64_t Amt = V2.getZExtValue();
279 
280       if (Amt >= V1.getBitWidth())
281         return nullptr;
282 
283       if (!Ctx.getLangOpts().CPlusPlus20) {
284         if (V1.isSigned() && V1.isNegative())
285           return nullptr;
286 
287         if (V1.isSigned() && Amt > V1.countl_zero())
288           return nullptr;
289       }
290 
291       return &getValue( V1.operator<<( (unsigned) Amt ));
292     }
293 
294     case BO_Shr: {
295       // FIXME: This logic should probably go higher up, where we can
296       // test these conditions symbolically.
297 
298       if (V2.isSigned() && V2.isNegative())
299         return nullptr;
300 
301       uint64_t Amt = V2.getZExtValue();
302 
303       if (Amt >= V1.getBitWidth())
304         return nullptr;
305 
306       return &getValue( V1.operator>>( (unsigned) Amt ));
307     }
308 
309     case BO_LT:
310       return &getTruthValue( V1 < V2 );
311 
312     case BO_GT:
313       return &getTruthValue( V1 > V2 );
314 
315     case BO_LE:
316       return &getTruthValue( V1 <= V2 );
317 
318     case BO_GE:
319       return &getTruthValue( V1 >= V2 );
320 
321     case BO_EQ:
322       return &getTruthValue( V1 == V2 );
323 
324     case BO_NE:
325       return &getTruthValue( V1 != V2 );
326 
327       // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
328 
329     case BO_And:
330       return &getValue( V1 & V2 );
331 
332     case BO_Or:
333       return &getValue( V1 | V2 );
334 
335     case BO_Xor:
336       return &getValue( V1 ^ V2 );
337   }
338 }
339 
340 const std::pair<SVal, uintptr_t>&
341 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
342   // Lazily create the folding set.
343   if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
344 
345   llvm::FoldingSetNodeID ID;
346   void *InsertPos;
347   V.Profile(ID);
348   ID.AddPointer((void*) Data);
349 
350   PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
351 
352   using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
353 
354   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
355 
356   if (!P) {
357     P = new (BPAlloc) FoldNodeTy(std::make_pair(V, Data));
358     Map.InsertNode(P, InsertPos);
359   }
360 
361   return P->getValue();
362 }
363 
364 const std::pair<SVal, SVal>&
365 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
366   // Lazily create the folding set.
367   if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
368 
369   llvm::FoldingSetNodeID ID;
370   void *InsertPos;
371   V1.Profile(ID);
372   V2.Profile(ID);
373 
374   PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
375 
376   using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
377 
378   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
379 
380   if (!P) {
381     P = new (BPAlloc) FoldNodeTy(std::make_pair(V1, V2));
382     Map.InsertNode(P, InsertPos);
383   }
384 
385   return P->getValue();
386 }
387 
388 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
389   return &getPersistentSValWithData(X, 0).first;
390 }
391