clang  8.0.0svn
BasicValueFactory.cpp
Go to the documentation of this file.
1 //===- BasicValueFactory.cpp - Basic values for Path Sens analysis --------===//
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 
21 #include "llvm/ADT/APSInt.h"
22 #include "llvm/ADT/FoldingSet.h"
23 #include "llvm/ADT/ImmutableList.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include <cassert>
26 #include <cstdint>
27 #include <utility>
28 
29 using namespace clang;
30 using namespace ento;
31 
32 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
33  llvm::ImmutableList<SVal> L) {
34  T.Profile(ID);
35  ID.AddPointer(L.getInternalPointer());
36 }
37 
38 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
39  const StoreRef &store,
40  const TypedValueRegion *region) {
41  ID.AddPointer(store.getStore());
42  ID.AddPointer(region);
43 }
44 
46  llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
47  llvm::ImmutableList<const CXXBaseSpecifier *> L) {
48  ID.AddPointer(D);
49  ID.AddPointer(L.getInternalPointer());
50 }
51 
52 using SValData = std::pair<SVal, uintptr_t>;
53 using SValPair = std::pair<SVal, SVal>;
54 
55 namespace llvm {
56 
57 template<> struct FoldingSetTrait<SValData> {
58  static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
59  X.first.Profile(ID);
60  ID.AddPointer( (void*) X.second);
61  }
62 };
63 
64 template<> struct FoldingSetTrait<SValPair> {
65  static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
66  X.first.Profile(ID);
67  X.second.Profile(ID);
68  }
69 };
70 
71 } // namespace llvm
72 
73 using PersistentSValsTy =
74  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
75 
77  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78 
80  // Note that the dstor for the contents of APSIntSet will never be called,
81  // so we iterate over the set and invoke the dstor for each APSInt. This
82  // frees an aux. memory allocated to represent very large constants.
83  for (const auto &I : APSIntSet)
84  I.getValue().~APSInt();
85 
86  delete (PersistentSValsTy*) PersistentSVals;
87  delete (PersistentSValPairsTy*) PersistentSValPairs;
88 }
89 
90 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
91  llvm::FoldingSetNodeID ID;
92  void *InsertPos;
93 
94  using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>;
95 
96  X.Profile(ID);
97  FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
98 
99  if (!P) {
100  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
101  new (P) FoldNodeTy(X);
102  APSIntSet.InsertNode(P, InsertPos);
103  }
104 
105  return *P;
106 }
107 
108 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
109  bool isUnsigned) {
110  llvm::APSInt V(X, isUnsigned);
111  return getValue(V);
112 }
113 
114 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
115  bool isUnsigned) {
116  llvm::APSInt V(BitWidth, isUnsigned);
117  V = X;
118  return getValue(V);
119 }
120 
121 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
122  return getValue(getAPSIntType(T).getValue(X));
123 }
124 
125 const CompoundValData*
127  llvm::ImmutableList<SVal> Vals) {
128  llvm::FoldingSetNodeID ID;
129  CompoundValData::Profile(ID, T, Vals);
130  void *InsertPos;
131 
132  CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
133 
134  if (!D) {
135  D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
136  new (D) CompoundValData(T, Vals);
137  CompoundValDataSet.InsertNode(D, InsertPos);
138  }
139 
140  return D;
141 }
142 
143 const LazyCompoundValData*
145  const TypedValueRegion *region) {
146  llvm::FoldingSetNodeID ID;
147  LazyCompoundValData::Profile(ID, store, region);
148  void *InsertPos;
149 
151  LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
152 
153  if (!D) {
154  D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
155  new (D) LazyCompoundValData(store, region);
156  LazyCompoundValDataSet.InsertNode(D, InsertPos);
157  }
158 
159  return D;
160 }
161 
163  const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
164  llvm::FoldingSetNodeID ID;
165  PointerToMemberData::Profile(ID, DD, L);
166  void *InsertPos;
167 
169  PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
170 
171  if (!D) {
172  D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
173  new (D) PointerToMemberData(DD, L);
174  PointerToMemberDataSet.InsertNode(D, InsertPos);
175  }
176 
177  return D;
178 }
179 
181  llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
182  const nonloc::PointerToMember &PTM) {
184  const DeclaratorDecl *DD = nullptr;
185  llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
186 
187  if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
188  if (PTMDT.is<const DeclaratorDecl *>())
189  DD = PTMDT.get<const DeclaratorDecl *>();
190 
191  PathList = CXXBaseListFactory.getEmptyList();
192  } else { // const PointerToMemberData *
193  const PointerToMemberData *PTMD =
194  PTMDT.get<const PointerToMemberData *>();
195  DD = PTMD->getDeclaratorDecl();
196 
197  PathList = PTMD->getCXXBaseList();
198  }
199 
200  for (const auto &I : llvm::reverse(PathRange))
201  PathList = prependCXXBase(I, PathList);
202  return getPointerToMemberData(DD, PathList);
203 }
204 
205 const llvm::APSInt*
207  const llvm::APSInt& V1, const llvm::APSInt& V2) {
208  switch (Op) {
209  default:
210  llvm_unreachable("Invalid Opcode.");
211 
212  case BO_Mul:
213  return &getValue( V1 * V2 );
214 
215  case BO_Div:
216  if (V2 == 0) // Avoid division by zero
217  return nullptr;
218  return &getValue( V1 / V2 );
219 
220  case BO_Rem:
221  if (V2 == 0) // Avoid division by zero
222  return nullptr;
223  return &getValue( V1 % V2 );
224 
225  case BO_Add:
226  return &getValue( V1 + V2 );
227 
228  case BO_Sub:
229  return &getValue( V1 - V2 );
230 
231  case BO_Shl: {
232  // FIXME: This logic should probably go higher up, where we can
233  // test these conditions symbolically.
234 
235  if (V1.isSigned() && V1.isNegative())
236  return nullptr;
237 
238  if (V2.isSigned() && V2.isNegative())
239  return nullptr;
240 
241  uint64_t Amt = V2.getZExtValue();
242 
243  if (Amt >= V1.getBitWidth())
244  return nullptr;
245 
246  if (V1.isSigned() && Amt > V1.countLeadingZeros())
247  return nullptr;
248 
249  return &getValue( V1.operator<<( (unsigned) Amt ));
250  }
251 
252  case BO_Shr: {
253  // FIXME: This logic should probably go higher up, where we can
254  // test these conditions symbolically.
255 
256  if (V2.isSigned() && V2.isNegative())
257  return nullptr;
258 
259  uint64_t Amt = V2.getZExtValue();
260 
261  if (Amt >= V1.getBitWidth())
262  return nullptr;
263 
264  return &getValue( V1.operator>>( (unsigned) Amt ));
265  }
266 
267  case BO_LT:
268  return &getTruthValue( V1 < V2 );
269 
270  case BO_GT:
271  return &getTruthValue( V1 > V2 );
272 
273  case BO_LE:
274  return &getTruthValue( V1 <= V2 );
275 
276  case BO_GE:
277  return &getTruthValue( V1 >= V2 );
278 
279  case BO_EQ:
280  return &getTruthValue( V1 == V2 );
281 
282  case BO_NE:
283  return &getTruthValue( V1 != V2 );
284 
285  // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
286 
287  case BO_And:
288  return &getValue( V1 & V2 );
289 
290  case BO_Or:
291  return &getValue( V1 | V2 );
292 
293  case BO_Xor:
294  return &getValue( V1 ^ V2 );
295  }
296 }
297 
298 const std::pair<SVal, uintptr_t>&
300  // Lazily create the folding set.
301  if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
302 
303  llvm::FoldingSetNodeID ID;
304  void *InsertPos;
305  V.Profile(ID);
306  ID.AddPointer((void*) Data);
307 
308  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
309 
310  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
311 
312  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
313 
314  if (!P) {
315  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
316  new (P) FoldNodeTy(std::make_pair(V, Data));
317  Map.InsertNode(P, InsertPos);
318  }
319 
320  return P->getValue();
321 }
322 
323 const std::pair<SVal, SVal>&
325  // Lazily create the folding set.
326  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
327 
328  llvm::FoldingSetNodeID ID;
329  void *InsertPos;
330  V1.Profile(ID);
331  V2.Profile(ID);
332 
333  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
334 
335  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
336 
337  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
338 
339  if (!P) {
340  P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
341  new (P) FoldNodeTy(std::make_pair(V1, V2));
342  Map.InsertNode(P, InsertPos);
343  }
344 
345  return P->getValue();
346 }
347 
349  return &getPersistentSValWithData(X, 0).first;
350 }
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:529
A (possibly-)qualified type.
Definition: Type.h:642
Store getStore() const
Definition: StoreRef.h:47
llvm::ImmutableList< const CXXBaseSpecifier * > getCXXBaseList() const
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:30
const CompoundValData * getCompoundValData(QualType T, llvm::ImmutableList< SVal > Vals)
const std::pair< SVal, SVal > & getPersistentSValPair(const SVal &V1, const SVal &V2)
StringRef P
std::pair< SVal, SVal > SValPair
const PointerToMemberData * accumCXXBase(llvm::iterator_range< CastExpr::path_const_iterator > PathRange, const nonloc::PointerToMember &PTM)
const PTMDataType getPTMData() const
Definition: SVals.h:529
const DeclaratorDecl * getDeclaratorDecl() const
Value representing pointer-to-member.
Definition: SVals.h:522
BinaryOperatorKind
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValData > > PersistentSValsTy
const SVal * getPersistentSVal(SVal X)
Represents a ValueDecl that came out of a declarator.
Definition: Decl.h:688
const PointerToMemberData * getPointerToMemberData(const DeclaratorDecl *DD, llvm::ImmutableList< const CXXBaseSpecifier *> L)
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: Type.h:1045
static SVal getValue(SVal val, SValBuilder &svalBuilder)
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c.h:90
static void Profile(llvm::FoldingSetNodeID &ID, const StoreRef &store, const TypedValueRegion *region)
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: SVals.h:124
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:76
const llvm::APSInt * evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1, const llvm::APSInt &V2)
Dataflow Directional Tag Classes.
std::pair< SVal, uintptr_t > SValData
static void Profile(llvm::FoldingSetNodeID &ID, QualType T, llvm::ImmutableList< SVal > L)
static void Profile(llvm::FoldingSetNodeID &ID, const DeclaratorDecl *D, llvm::ImmutableList< const CXXBaseSpecifier *> L)
llvm::PointerUnion< const DeclaratorDecl *, const PointerToMemberData * > PTMDataType
Definition: SVals.h:527
static void Profile(const SValPair &X, llvm::FoldingSetNodeID &ID)
const std::pair< SVal, uintptr_t > & getPersistentSValWithData(const SVal &V, uintptr_t Data)
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13956
const LazyCompoundValData * getLazyCompoundValData(const StoreRef &store, const TypedValueRegion *region)
static void Profile(const SValData &X, llvm::FoldingSetNodeID &ID)
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValPair > > PersistentSValPairsTy
CompoundValData(QualType t, llvm::ImmutableList< SVal > l)