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