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 
28 using namespace clang;
29 using namespace ento;
30 
31 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
32                               llvm::ImmutableList<SVal> L) {
33   T.Profile(ID);
34   ID.AddPointer(L.getInternalPointer());
35 }
36 
37 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
38                                   const StoreRef &store,
39                                   const TypedValueRegion *region) {
40   ID.AddPointer(store.getStore());
41   ID.AddPointer(region);
42 }
43 
44 void 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 
51 using SValData = std::pair<SVal, uintptr_t>;
52 using SValPair = std::pair<SVal, SVal>;
53 
54 namespace llvm {
55 
56 template<> 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 
63 template<> 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 
72 using PersistentSValsTy =
73     llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
74 
75 using PersistentSValPairsTy =
76     llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
77 
78 BasicValueFactory::~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 
89 const 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 
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 = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
135     new (D) CompoundValData(T, Vals);
136     CompoundValDataSet.InsertNode(D, InsertPos);
137   }
138 
139   return D;
140 }
141 
142 const LazyCompoundValData*
143 BasicValueFactory::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 
161 const 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 
179 const 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 
204 const llvm::APSInt*
205 BasicValueFactory::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 
297 const std::pair<SVal, uintptr_t>&
298 BasicValueFactory::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 
322 const std::pair<SVal, SVal>&
323 BasicValueFactory::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 
347 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
348   return &getPersistentSValWithData(X, 0).first;
349 }
350