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