lib/StaticAnalyzer/Core/BasicValueFactory.cpp

   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
  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
  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 void PointerToMemberData::Profile(
  37     llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
  38     llvm::ImmutableList<const CXXBaseSpecifier *> L) {
  39   ID.AddPointer(D);
  40   ID.AddPointer(L.getInternalPointer());
  41 }
  42
  43 typedef std::pair<SVal, uintptr_t> SValData;
  44 typedef std::pair<SVal, SVal> SValPair;
  45
  46 namespace llvm {
  47 template<> struct FoldingSetTrait<SValData> {
  48   static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
  49     X.first.Profile(ID);
  50     ID.AddPointer( (void*) X.second);
  51   }
  52 };
  53
  54 template<> struct FoldingSetTrait<SValPair> {
  55   static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
  56     X.first.Profile(ID);
  57     X.second.Profile(ID);
  58   }
  59 };
  60 }
  61
  62 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> >
  63   PersistentSValsTy;
  64
  65 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> >
  66   PersistentSValPairsTy;
  67
  68 BasicValueFactory::~BasicValueFactory() {
  69   // Note that the dstor for the contents of APSIntSet will never be called,
  70   // so we iterate over the set and invoke the dstor for each APSInt.  This
  71   // frees an aux. memory allocated to represent very large constants.
  72   for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
  73     I->getValue().~APSInt();
  74
  75   delete (PersistentSValsTy*) PersistentSVals;
  76   delete (PersistentSValPairsTy*) PersistentSValPairs;
  77 }
  78
  79 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
  80   llvm::FoldingSetNodeID ID;
  81   void *InsertPos;
  82   typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
  83
  84   X.Profile(ID);
  85   FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
  86
  87   if (!P) {
  88     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
  89     new (P) FoldNodeTy(X);
  90     APSIntSet.InsertNode(P, InsertPos);
  91   }
  92
  93   return *P;
  94 }
  95
  96 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
  97                                                 bool isUnsigned) {
  98   llvm::APSInt V(X, isUnsigned);
  99   return getValue(V);
 100 }
 101
 102 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
 103                                            bool isUnsigned) {
 104   llvm::APSInt V(BitWidth, isUnsigned);
 105   V = X;
 106   return getValue(V);
 107 }
 108
 109 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
 110
 111   return getValue(getAPSIntType(T).getValue(X));
 112 }
 113
 114 const CompoundValData*
 115 BasicValueFactory::getCompoundValData(QualType T,
 116                                       llvm::ImmutableList<SVal> Vals) {
 117
 118   llvm::FoldingSetNodeID ID;
 119   CompoundValData::Profile(ID, T, Vals);
 120   void *InsertPos;
 121
 122   CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
 123
 124   if (!D) {
 125     D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
 126     new (D) CompoundValData(T, Vals);
 127     CompoundValDataSet.InsertNode(D, InsertPos);
 128   }
 129
 130   return D;
 131 }
 132
 133 const LazyCompoundValData*
 134 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
 135                                           const TypedValueRegion *region) {
 136   llvm::FoldingSetNodeID ID;
 137   LazyCompoundValData::Profile(ID, store, region);
 138   void *InsertPos;
 139
 140   LazyCompoundValData *D =
 141     LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
 142
 143   if (!D) {
 144     D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
 145     new (D) LazyCompoundValData(store, region);
 146     LazyCompoundValDataSet.InsertNode(D, InsertPos);
 147   }
 148
 149   return D;
 150 }
 151
 152 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
 153     const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier*> L) {
 154   llvm::FoldingSetNodeID ID;
 155   PointerToMemberData::Profile(ID, DD, L);
 156   void *InsertPos;
 157
 158   PointerToMemberData *D =
 159       PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
 160
 161   if (!D) {
 162     D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
 163     new (D) PointerToMemberData(DD, L);
 164     PointerToMemberDataSet.InsertNode(D, InsertPos);
 165   }
 166
 167   return D;
 168 }
 169
 170 const clang::ento::PointerToMemberData *BasicValueFactory::accumCXXBase(
 171     llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
 172     const nonloc::PointerToMember &PTM) {
 173   nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
 174   const DeclaratorDecl *DD = nullptr;
 175   llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
 176
 177   if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
 178     if (PTMDT.is<const DeclaratorDecl *>())
 179       DD = PTMDT.get<const DeclaratorDecl *>();
 180
 181     PathList = CXXBaseListFactory.getEmptyList();
 182   } else { // const PointerToMemberData *
 183     const PointerToMemberData *PTMD =
 184         PTMDT.get<const PointerToMemberData *>();
 185     DD = PTMD->getDeclaratorDecl();
 186
 187     PathList = PTMD->getCXXBaseList();
 188   }
 189
 190   for (const auto &I : llvm::reverse(PathRange))
 191     PathList = prependCXXBase(I, PathList);
 192   return getPointerToMemberData(DD, PathList);
 193 }
 194
 195 const llvm::APSInt*
 196 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
 197                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
 198
 199   switch (Op) {
 200     default:
 201       assert (false && "Invalid Opcode.");
 202
 203     case BO_Mul:
 204       return &getValue( V1 * V2 );
 205
 206     case BO_Div:
 207       if (V2 == 0) // Avoid division by zero
 208         return nullptr;
 209       return &getValue( V1 / V2 );
 210
 211     case BO_Rem:
 212       if (V2 == 0) // Avoid division by zero
 213         return nullptr;
 214       return &getValue( V1 % V2 );
 215
 216     case BO_Add:
 217       return &getValue( V1 + V2 );
 218
 219     case BO_Sub:
 220       return &getValue( V1 - V2 );
 221
 222     case BO_Shl: {
 223
 224       // FIXME: This logic should probably go higher up, where we can
 225       // test these conditions symbolically.
 226
 227       // FIXME: Expand these checks to include all undefined behavior.
 228
 229       if (V2.isSigned() && V2.isNegative())
 230         return nullptr;
 231
 232       uint64_t Amt = V2.getZExtValue();
 233
 234       if (Amt >= V1.getBitWidth())
 235         return nullptr;
 236
 237       return &getValue( V1.operator<<( (unsigned) Amt ));
 238     }
 239
 240     case BO_Shr: {
 241
 242       // FIXME: This logic should probably go higher up, where we can
 243       // test these conditions symbolically.
 244
 245       // FIXME: Expand these checks to include all undefined behavior.
 246
 247       if (V2.isSigned() && V2.isNegative())
 248         return nullptr;
 249
 250       uint64_t Amt = V2.getZExtValue();
 251
 252       if (Amt >= V1.getBitWidth())
 253         return nullptr;
 254
 255       return &getValue( V1.operator>>( (unsigned) Amt ));
 256     }
 257
 258     case BO_LT:
 259       return &getTruthValue( V1 < V2 );
 260
 261     case BO_GT:
 262       return &getTruthValue( V1 > V2 );
 263
 264     case BO_LE:
 265       return &getTruthValue( V1 <= V2 );
 266
 267     case BO_GE:
 268       return &getTruthValue( V1 >= V2 );
 269
 270     case BO_EQ:
 271       return &getTruthValue( V1 == V2 );
 272
 273     case BO_NE:
 274       return &getTruthValue( V1 != V2 );
 275
 276       // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
 277
 278     case BO_And:
 279       return &getValue( V1 & V2 );
 280
 281     case BO_Or:
 282       return &getValue( V1 | V2 );
 283
 284     case BO_Xor:
 285       return &getValue( V1 ^ V2 );
 286   }
 287 }
 288
 289
 290 const std::pair<SVal, uintptr_t>&
 291 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
 292
 293   // Lazily create the folding set.
 294   if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
 295
 296   llvm::FoldingSetNodeID ID;
 297   void *InsertPos;
 298   V.Profile(ID);
 299   ID.AddPointer((void*) Data);
 300
 301   PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
 302
 303   typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy;
 304   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
 305
 306   if (!P) {
 307     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
 308     new (P) FoldNodeTy(std::make_pair(V, Data));
 309     Map.InsertNode(P, InsertPos);
 310   }
 311
 312   return P->getValue();
 313 }
 314
 315 const std::pair<SVal, SVal>&
 316 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
 317
 318   // Lazily create the folding set.
 319   if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
 320
 321   llvm::FoldingSetNodeID ID;
 322   void *InsertPos;
 323   V1.Profile(ID);
 324   V2.Profile(ID);
 325
 326   PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
 327
 328   typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy;
 329   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
 330
 331   if (!P) {
 332     P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
 333     new (P) FoldNodeTy(std::make_pair(V1, V2));
 334     Map.InsertNode(P, InsertPos);
 335   }
 336
 337   return P->getValue();
 338 }
 339
 340 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
 341   return &getPersistentSValWithData(X, 0).first;
 342 }