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