1 //=== BasicValueFactory.cpp - Basic values for Path Sens analysis --*- C++ -*-//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines BasicValueFactory, a class that manages the lifetime
11 //  of APSInt objects and symbolic constraints used by ExprEngine
12 //  and related classes.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "clang/AST/ASTContext.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
19 
20 using namespace clang;
21 using namespace ento;
22 
23 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
24                               llvm::ImmutableList<SVal> L) {
25   T.Profile(ID);
26   ID.AddPointer(L.getInternalPointer());
27 }
28 
29 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
30                                   const StoreRef &store,
31                                   const TypedValueRegion *region) {
32   ID.AddPointer(store.getStore());
33   ID.AddPointer(region);
34 }
35 
36 void PointerToMemberData::Profile(
37     llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
38     llvm::ImmutableList<const CXXBaseSpecifier *> L) {
39   ID.AddPointer(D);
40   ID.AddPointer(L.getInternalPointer());
41 }
42 
43 typedef std::pair<SVal, uintptr_t> SValData;
44 typedef std::pair<SVal, SVal> SValPair;
45 
46 namespace llvm {
47 template<> struct FoldingSetTrait<SValData> {
48   static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
49     X.first.Profile(ID);
50     ID.AddPointer( (void*) X.second);
51   }
52 };
53 
54 template<> struct FoldingSetTrait<SValPair> {
55   static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
56     X.first.Profile(ID);
57     X.second.Profile(ID);
58   }
59 };
60 }
61 
62 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> >
63   PersistentSValsTy;
64 
65 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> >
66   PersistentSValPairsTy;
67 
68 BasicValueFactory::~BasicValueFactory() {
69   // Note that the dstor for the contents of APSIntSet will never be called,
70   // so we iterate over the set and invoke the dstor for each APSInt.  This
71   // frees an aux. memory allocated to represent very large constants.
72   for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
73     I->getValue().~APSInt();
74 
75   delete (PersistentSValsTy*) PersistentSVals;
76   delete (PersistentSValPairsTy*) PersistentSValPairs;
77 }
78 
79 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
80   llvm::FoldingSetNodeID ID;
81   void *InsertPos;
82   typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
83 
84   X.Profile(ID);
85   FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
86 
87   if (!P) {
88     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
89     new (P) FoldNodeTy(X);
90     APSIntSet.InsertNode(P, InsertPos);
91   }
92 
93   return *P;
94 }
95 
96 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
97                                                 bool isUnsigned) {
98   llvm::APSInt V(X, isUnsigned);
99   return getValue(V);
100 }
101 
102 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
103                                            bool isUnsigned) {
104   llvm::APSInt V(BitWidth, isUnsigned);
105   V = X;
106   return getValue(V);
107 }
108 
109 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
110 
111   return getValue(getAPSIntType(T).getValue(X));
112 }
113 
114 const CompoundValData*
115 BasicValueFactory::getCompoundValData(QualType T,
116                                       llvm::ImmutableList<SVal> Vals) {
117 
118   llvm::FoldingSetNodeID ID;
119   CompoundValData::Profile(ID, T, Vals);
120   void *InsertPos;
121 
122   CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
123 
124   if (!D) {
125     D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
126     new (D) CompoundValData(T, Vals);
127     CompoundValDataSet.InsertNode(D, InsertPos);
128   }
129 
130   return D;
131 }
132 
133 const LazyCompoundValData*
134 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
135                                           const TypedValueRegion *region) {
136   llvm::FoldingSetNodeID ID;
137   LazyCompoundValData::Profile(ID, store, region);
138   void *InsertPos;
139 
140   LazyCompoundValData *D =
141     LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
142 
143   if (!D) {
144     D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
145     new (D) LazyCompoundValData(store, region);
146     LazyCompoundValDataSet.InsertNode(D, InsertPos);
147   }
148 
149   return D;
150 }
151 
152 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
153     const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier*> L) {
154   llvm::FoldingSetNodeID ID;
155   PointerToMemberData::Profile(ID, DD, L);
156   void *InsertPos;
157 
158   PointerToMemberData *D =
159       PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
160 
161   if (!D) {
162     D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
163     new (D) PointerToMemberData(DD, L);
164     PointerToMemberDataSet.InsertNode(D, InsertPos);
165   }
166 
167   return D;
168 }
169 
170 const clang::ento::PointerToMemberData *BasicValueFactory::accumCXXBase(
171     llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
172     const nonloc::PointerToMember &PTM) {
173   nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
174   const DeclaratorDecl *DD = nullptr;
175   llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
176 
177   if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
178     if (PTMDT.is<const DeclaratorDecl *>())
179       DD = PTMDT.get<const DeclaratorDecl *>();
180 
181     PathList = CXXBaseListFactory.getEmptyList();
182   } else { // const PointerToMemberData *
183     const PointerToMemberData *PTMD =
184         PTMDT.get<const PointerToMemberData *>();
185     DD = PTMD->getDeclaratorDecl();
186 
187     PathList = PTMD->getCXXBaseList();
188   }
189 
190   for (const auto &I : llvm::reverse(PathRange))
191     PathList = prependCXXBase(I, PathList);
192   return getPointerToMemberData(DD, PathList);
193 }
194 
195 const llvm::APSInt*
196 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
197                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
198 
199   switch (Op) {
200     default:
201       assert (false && "Invalid Opcode.");
202 
203     case BO_Mul:
204       return &getValue( V1 * V2 );
205 
206     case BO_Div:
207       if (V2 == 0) // Avoid division by zero
208         return nullptr;
209       return &getValue( V1 / V2 );
210 
211     case BO_Rem:
212       if (V2 == 0) // Avoid division by zero
213         return nullptr;
214       return &getValue( V1 % V2 );
215 
216     case BO_Add:
217       return &getValue( V1 + V2 );
218 
219     case BO_Sub:
220       return &getValue( V1 - V2 );
221 
222     case BO_Shl: {
223 
224       // FIXME: This logic should probably go higher up, where we can
225       // test these conditions symbolically.
226 
227       if (V1.isSigned() && V1.isNegative())
228         return nullptr;
229 
230       if (V2.isSigned() && V2.isNegative())
231         return nullptr;
232 
233       uint64_t Amt = V2.getZExtValue();
234 
235       if (Amt >= V1.getBitWidth())
236         return nullptr;
237 
238       if (V1.isSigned() && Amt > V1.countLeadingZeros())
239           return nullptr;
240 
241       return &getValue( V1.operator<<( (unsigned) Amt ));
242     }
243 
244     case BO_Shr: {
245 
246       // FIXME: This logic should probably go higher up, where we can
247       // test these conditions symbolically.
248 
249       if (V2.isSigned() && V2.isNegative())
250         return nullptr;
251 
252       uint64_t Amt = V2.getZExtValue();
253 
254       if (Amt >= V1.getBitWidth())
255         return nullptr;
256 
257       return &getValue( V1.operator>>( (unsigned) Amt ));
258     }
259 
260     case BO_LT:
261       return &getTruthValue( V1 < V2 );
262 
263     case BO_GT:
264       return &getTruthValue( V1 > V2 );
265 
266     case BO_LE:
267       return &getTruthValue( V1 <= V2 );
268 
269     case BO_GE:
270       return &getTruthValue( V1 >= V2 );
271 
272     case BO_EQ:
273       return &getTruthValue( V1 == V2 );
274 
275     case BO_NE:
276       return &getTruthValue( V1 != V2 );
277 
278       // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
279 
280     case BO_And:
281       return &getValue( V1 & V2 );
282 
283     case BO_Or:
284       return &getValue( V1 | V2 );
285 
286     case BO_Xor:
287       return &getValue( V1 ^ V2 );
288   }
289 }
290 
291 
292 const std::pair<SVal, uintptr_t>&
293 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
294 
295   // Lazily create the folding set.
296   if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
297 
298   llvm::FoldingSetNodeID ID;
299   void *InsertPos;
300   V.Profile(ID);
301   ID.AddPointer((void*) Data);
302 
303   PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
304 
305   typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy;
306   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
307 
308   if (!P) {
309     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
310     new (P) FoldNodeTy(std::make_pair(V, Data));
311     Map.InsertNode(P, InsertPos);
312   }
313 
314   return P->getValue();
315 }
316 
317 const std::pair<SVal, SVal>&
318 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
319 
320   // Lazily create the folding set.
321   if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
322 
323   llvm::FoldingSetNodeID ID;
324   void *InsertPos;
325   V1.Profile(ID);
326   V2.Profile(ID);
327 
328   PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
329 
330   typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy;
331   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
332 
333   if (!P) {
334     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
335     new (P) FoldNodeTy(std::make_pair(V1, V2));
336     Map.InsertNode(P, InsertPos);
337   }
338 
339   return P->getValue();
340 }
341 
342 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
343   return &getPersistentSValWithData(X, 0).first;
344 }
345