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 typedef std::pair<SVal, uintptr_t> SValData;
37 typedef std::pair<SVal, SVal> SValPair;
38 
39 namespace llvm {
40 template<> struct FoldingSetTrait<SValData> {
41   static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
42     X.first.Profile(ID);
43     ID.AddPointer( (void*) X.second);
44   }
45 };
46 
47 template<> struct FoldingSetTrait<SValPair> {
48   static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
49     X.first.Profile(ID);
50     X.second.Profile(ID);
51   }
52 };
53 }
54 
55 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> >
56   PersistentSValsTy;
57 
58 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> >
59   PersistentSValPairsTy;
60 
61 BasicValueFactory::~BasicValueFactory() {
62   // Note that the dstor for the contents of APSIntSet will never be called,
63   // so we iterate over the set and invoke the dstor for each APSInt.  This
64   // frees an aux. memory allocated to represent very large constants.
65   for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
66     I->getValue().~APSInt();
67 
68   delete (PersistentSValsTy*) PersistentSVals;
69   delete (PersistentSValPairsTy*) PersistentSValPairs;
70 }
71 
72 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
73   llvm::FoldingSetNodeID ID;
74   void *InsertPos;
75   typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
76 
77   X.Profile(ID);
78   FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
79 
80   if (!P) {
81     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
82     new (P) FoldNodeTy(X);
83     APSIntSet.InsertNode(P, InsertPos);
84   }
85 
86   return *P;
87 }
88 
89 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
90                                                 bool isUnsigned) {
91   llvm::APSInt V(X, isUnsigned);
92   return getValue(V);
93 }
94 
95 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
96                                            bool isUnsigned) {
97   llvm::APSInt V(BitWidth, isUnsigned);
98   V = X;
99   return getValue(V);
100 }
101 
102 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
103 
104   unsigned bits = Ctx.getTypeSize(T);
105   llvm::APSInt V(bits,
106                  T->isUnsignedIntegerOrEnumerationType() || Loc::isLocType(T));
107   V = X;
108   return getValue(V);
109 }
110 
111 const CompoundValData*
112 BasicValueFactory::getCompoundValData(QualType T,
113                                       llvm::ImmutableList<SVal> Vals) {
114 
115   llvm::FoldingSetNodeID ID;
116   CompoundValData::Profile(ID, T, Vals);
117   void *InsertPos;
118 
119   CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
120 
121   if (!D) {
122     D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
123     new (D) CompoundValData(T, Vals);
124     CompoundValDataSet.InsertNode(D, InsertPos);
125   }
126 
127   return D;
128 }
129 
130 const LazyCompoundValData*
131 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
132                                           const TypedValueRegion *region) {
133   llvm::FoldingSetNodeID ID;
134   LazyCompoundValData::Profile(ID, store, region);
135   void *InsertPos;
136 
137   LazyCompoundValData *D =
138     LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
139 
140   if (!D) {
141     D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
142     new (D) LazyCompoundValData(store, region);
143     LazyCompoundValDataSet.InsertNode(D, InsertPos);
144   }
145 
146   return D;
147 }
148 
149 const llvm::APSInt*
150 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
151                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
152 
153   switch (Op) {
154     default:
155       assert (false && "Invalid Opcode.");
156 
157     case BO_Mul:
158       return &getValue( V1 * V2 );
159 
160     case BO_Div:
161       return &getValue( V1 / V2 );
162 
163     case BO_Rem:
164       return &getValue( V1 % V2 );
165 
166     case BO_Add:
167       return &getValue( V1 + V2 );
168 
169     case BO_Sub:
170       return &getValue( V1 - V2 );
171 
172     case BO_Shl: {
173 
174       // FIXME: This logic should probably go higher up, where we can
175       // test these conditions symbolically.
176 
177       // FIXME: Expand these checks to include all undefined behavior.
178 
179       if (V2.isSigned() && V2.isNegative())
180         return NULL;
181 
182       uint64_t Amt = V2.getZExtValue();
183 
184       if (Amt > V1.getBitWidth())
185         return NULL;
186 
187       return &getValue( V1.operator<<( (unsigned) Amt ));
188     }
189 
190     case BO_Shr: {
191 
192       // FIXME: This logic should probably go higher up, where we can
193       // test these conditions symbolically.
194 
195       // FIXME: Expand these checks to include all undefined behavior.
196 
197       if (V2.isSigned() && V2.isNegative())
198         return NULL;
199 
200       uint64_t Amt = V2.getZExtValue();
201 
202       if (Amt > V1.getBitWidth())
203         return NULL;
204 
205       return &getValue( V1.operator>>( (unsigned) Amt ));
206     }
207 
208     case BO_LT:
209       return &getTruthValue( V1 < V2 );
210 
211     case BO_GT:
212       return &getTruthValue( V1 > V2 );
213 
214     case BO_LE:
215       return &getTruthValue( V1 <= V2 );
216 
217     case BO_GE:
218       return &getTruthValue( V1 >= V2 );
219 
220     case BO_EQ:
221       return &getTruthValue( V1 == V2 );
222 
223     case BO_NE:
224       return &getTruthValue( V1 != V2 );
225 
226       // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
227 
228     case BO_And:
229       return &getValue( V1 & V2 );
230 
231     case BO_Or:
232       return &getValue( V1 | V2 );
233 
234     case BO_Xor:
235       return &getValue( V1 ^ V2 );
236   }
237 }
238 
239 
240 const std::pair<SVal, uintptr_t>&
241 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
242 
243   // Lazily create the folding set.
244   if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
245 
246   llvm::FoldingSetNodeID ID;
247   void *InsertPos;
248   V.Profile(ID);
249   ID.AddPointer((void*) Data);
250 
251   PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
252 
253   typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy;
254   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
255 
256   if (!P) {
257     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
258     new (P) FoldNodeTy(std::make_pair(V, Data));
259     Map.InsertNode(P, InsertPos);
260   }
261 
262   return P->getValue();
263 }
264 
265 const std::pair<SVal, SVal>&
266 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
267 
268   // Lazily create the folding set.
269   if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
270 
271   llvm::FoldingSetNodeID ID;
272   void *InsertPos;
273   V1.Profile(ID);
274   V2.Profile(ID);
275 
276   PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
277 
278   typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy;
279   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
280 
281   if (!P) {
282     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
283     new (P) FoldNodeTy(std::make_pair(V1, V2));
284     Map.InsertNode(P, InsertPos);
285   }
286 
287   return P->getValue();
288 }
289 
290 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
291   return &getPersistentSValWithData(X, 0).first;
292 }
293