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