• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
Profile(llvm::FoldingSetNodeID & ID,QualType T,llvm::ImmutableList<SVal> L)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 
Profile(llvm::FoldingSetNodeID & ID,const StoreRef & store,const TypedValueRegion * region)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> {
Profilellvm::FoldingSetTrait41   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> {
Profilellvm::FoldingSetTrait48   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 
~BasicValueFactory()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 
getValue(const llvm::APSInt & X)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 
getValue(const llvm::APInt & X,bool isUnsigned)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 
getValue(uint64_t X,unsigned BitWidth,bool isUnsigned)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 
getValue(uint64_t X,QualType T)102 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
103 
104   return getValue(getAPSIntType(T).getValue(X));
105 }
106 
107 const CompoundValData*
getCompoundValData(QualType T,llvm::ImmutableList<SVal> Vals)108 BasicValueFactory::getCompoundValData(QualType T,
109                                       llvm::ImmutableList<SVal> Vals) {
110 
111   llvm::FoldingSetNodeID ID;
112   CompoundValData::Profile(ID, T, Vals);
113   void *InsertPos;
114 
115   CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
116 
117   if (!D) {
118     D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
119     new (D) CompoundValData(T, Vals);
120     CompoundValDataSet.InsertNode(D, InsertPos);
121   }
122 
123   return D;
124 }
125 
126 const LazyCompoundValData*
getLazyCompoundValData(const StoreRef & store,const TypedValueRegion * region)127 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
128                                           const TypedValueRegion *region) {
129   llvm::FoldingSetNodeID ID;
130   LazyCompoundValData::Profile(ID, store, region);
131   void *InsertPos;
132 
133   LazyCompoundValData *D =
134     LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
135 
136   if (!D) {
137     D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
138     new (D) LazyCompoundValData(store, region);
139     LazyCompoundValDataSet.InsertNode(D, InsertPos);
140   }
141 
142   return D;
143 }
144 
145 const llvm::APSInt*
evalAPSInt(BinaryOperator::Opcode Op,const llvm::APSInt & V1,const llvm::APSInt & V2)146 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
147                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
148 
149   switch (Op) {
150     default:
151       assert (false && "Invalid Opcode.");
152 
153     case BO_Mul:
154       return &getValue( V1 * V2 );
155 
156     case BO_Div:
157       if (V2 == 0) // Avoid division by zero
158         return nullptr;
159       return &getValue( V1 / V2 );
160 
161     case BO_Rem:
162       if (V2 == 0) // Avoid division by zero
163         return nullptr;
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 nullptr;
181 
182       uint64_t Amt = V2.getZExtValue();
183 
184       if (Amt >= V1.getBitWidth())
185         return nullptr;
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 nullptr;
199 
200       uint64_t Amt = V2.getZExtValue();
201 
202       if (Amt >= V1.getBitWidth())
203         return nullptr;
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>&
getPersistentSValWithData(const SVal & V,uintptr_t Data)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>&
getPersistentSValPair(const SVal & V1,const SVal & V2)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 
getPersistentSVal(SVal X)290 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
291   return &getPersistentSValWithData(X, 0).first;
292 }
293