contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

   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
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
  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
  45 void PointerToMemberData::Profile(
  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
  76 using PersistentSValPairsTy =
  77     llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
  78
  79 BasicValueFactory::~BasicValueFactory() {
  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*
 126 BasicValueFactory::getCompoundValData(QualType T,
 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*
 144 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
 145                                           const TypedValueRegion *region) {
 146   llvm::FoldingSetNodeID ID;
 147   LazyCompoundValData::Profile(ID, store, region);
 148   void *InsertPos;
 149
 150   LazyCompoundValData *D =
 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
 162 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
 163     const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
 164   llvm::FoldingSetNodeID ID;
 165   PointerToMemberData::Profile(ID, DD, L);
 166   void *InsertPos;
 167
 168   PointerToMemberData *D =
 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
 180 const PointerToMemberData *BasicValueFactory::accumCXXBase(
 181     llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
 182     const nonloc::PointerToMember &PTM) {
 183   nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
 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*
 206 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
 207                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
 208   switch (Op) {
 209     default:
 210       assert(false && "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>&
 299 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
 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>&
 324 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
 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
 348 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
 349   return &getPersistentSValWithData(X, 0).first;
 350 }