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 = (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*
126 BasicValueFactory::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 
143 const LazyCompoundValData*
144 BasicValueFactory::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 
162 const 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 
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 
192 const 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 
249 const llvm::APSInt*
250 BasicValueFactory::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 
344 const std::pair<SVal, uintptr_t>&
345 BasicValueFactory::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 
369 const std::pair<SVal, SVal>&
370 BasicValueFactory::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 
394 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
395   return &getPersistentSValWithData(X, 0).first;
396 }
397