BasicValueFactory.cpp 7.7 KB

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