clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

   1 //===- BasicValueFactory.cpp - Basic values for Path Sens analysis --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines BasicValueFactory, a class that manages the lifetime
  10 //  of APSInt objects and symbolic constraints used by ExprEngine
  11 //  and related classes.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
  20 #include "llvm/ADT/APSInt.h"
  21 #include "llvm/ADT/FoldingSet.h"
  22 #include "llvm/ADT/ImmutableList.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 #include "llvm/ADT/SmallPtrSet.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 NamedDecl *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 = new (BPAlloc) FoldNodeTy(X);
 101     APSIntSet.InsertNode(P, InsertPos);
 102   }
 103
 104   return *P;
 105 }
 106
 107 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
 108                                                 bool isUnsigned) {
 109   llvm::APSInt V(X, isUnsigned);
 110   return getValue(V);
 111 }
 112
 113 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
 114                                            bool isUnsigned) {
 115   llvm::APSInt V(BitWidth, isUnsigned);
 116   V = X;
 117   return getValue(V);
 118 }
 119
 120 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
 121   return getValue(getAPSIntType(T).getValue(X));
 122 }
 123
 124 const CompoundValData*
 125 BasicValueFactory::getCompoundValData(QualType T,
 126                                       llvm::ImmutableList<SVal> Vals) {
 127   llvm::FoldingSetNodeID ID;
 128   CompoundValData::Profile(ID, T, Vals);
 129   void *InsertPos;
 130
 131   CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
 132
 133   if (!D) {
 134     D = new (BPAlloc) CompoundValData(T, Vals);
 135     CompoundValDataSet.InsertNode(D, InsertPos);
 136   }
 137
 138   return D;
 139 }
 140
 141 const LazyCompoundValData*
 142 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
 143                                           const TypedValueRegion *region) {
 144   llvm::FoldingSetNodeID ID;
 145   LazyCompoundValData::Profile(ID, store, region);
 146   void *InsertPos;
 147
 148   LazyCompoundValData *D =
 149     LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
 150
 151   if (!D) {
 152     D = new (BPAlloc) LazyCompoundValData(store, region);
 153     LazyCompoundValDataSet.InsertNode(D, InsertPos);
 154   }
 155
 156   return D;
 157 }
 158
 159 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
 160     const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
 161   llvm::FoldingSetNodeID ID;
 162   PointerToMemberData::Profile(ID, ND, L);
 163   void *InsertPos;
 164
 165   PointerToMemberData *D =
 166       PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
 167
 168   if (!D) {
 169     D = new (BPAlloc) PointerToMemberData(ND, L);
 170     PointerToMemberDataSet.InsertNode(D, InsertPos);
 171   }
 172
 173   return D;
 174 }
 175
 176 LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(
 177     llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) {
 178   llvm::SmallPtrSet<QualType, 16> BaseSpecSeen;
 179   for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
 180     QualType BaseType = BaseSpec->getType();
 181     // Check whether inserted
 182     if (!BaseSpecSeen.insert(BaseType).second)
 183       return false;
 184   }
 185   return true;
 186 }
 187
 188 const PointerToMemberData *BasicValueFactory::accumCXXBase(
 189     llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
 190     const nonloc::PointerToMember &PTM, const CastKind &kind) {
 191   assert((kind == CK_DerivedToBaseMemberPointer ||
 192           kind == CK_BaseToDerivedMemberPointer ||
 193           kind == CK_ReinterpretMemberPointer) &&
 194          "accumCXXBase called with wrong CastKind");
 195   nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
 196   const NamedDecl *ND = nullptr;
 197   llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
 198
 199   if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
 200     if (PTMDT.is<const NamedDecl *>())
 201       ND = PTMDT.get<const NamedDecl *>();
 202
 203     BaseSpecList = CXXBaseListFactory.getEmptyList();
 204   } else {
 205     const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
 206     ND = PTMD->getDeclaratorDecl();
 207
 208     BaseSpecList = PTMD->getCXXBaseList();
 209   }
 210
 211   assert(hasNoRepeatedElements(BaseSpecList) &&
 212          "CXXBaseSpecifier list of PointerToMemberData must not have repeated "
 213          "elements");
 214
 215   if (kind == CK_DerivedToBaseMemberPointer) {
 216     // Here we pop off matching CXXBaseSpecifiers from BaseSpecList.
 217     // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and
 218     // serves to remove a matching implicit cast. Note that static_cast's that
 219     // are no-ops do not count since they produce an empty PathRange, a nice
 220     // thing about Clang AST.
 221
 222     // Now we know that there are no repetitions in BaseSpecList.
 223     // So, popping the first element from it corresponding to each element in
 224     // PathRange is equivalent to only including elements that are in
 225     // BaseSpecList but not it PathRange
 226     auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList();
 227     for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
 228       auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool {
 229         return BaseSpec->getType() == I->getType();
 230       };
 231       if (llvm::none_of(PathRange, IsSameAsBaseSpec))
 232         ReducedBaseSpecList =
 233             CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList);
 234     }
 235
 236     return getPointerToMemberData(ND, ReducedBaseSpecList);
 237   }
 238   // FIXME: Reinterpret casts on member-pointers are not handled properly by
 239   // this code
 240   for (const CXXBaseSpecifier *I : llvm::reverse(PathRange))
 241     BaseSpecList = prependCXXBase(I, BaseSpecList);
 242   return getPointerToMemberData(ND, BaseSpecList);
 243 }
 244
 245 const llvm::APSInt*
 246 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
 247                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
 248   switch (Op) {
 249     default:
 250       llvm_unreachable("Invalid Opcode.");
 251
 252     case BO_Mul:
 253       return &getValue( V1 * V2 );
 254
 255     case BO_Div:
 256       if (V2 == 0) // Avoid division by zero
 257         return nullptr;
 258       return &getValue( V1 / V2 );
 259
 260     case BO_Rem:
 261       if (V2 == 0) // Avoid division by zero
 262         return nullptr;
 263       return &getValue( V1 % V2 );
 264
 265     case BO_Add:
 266       return &getValue( V1 + V2 );
 267
 268     case BO_Sub:
 269       return &getValue( V1 - V2 );
 270
 271     case BO_Shl: {
 272       // FIXME: This logic should probably go higher up, where we can
 273       // test these conditions symbolically.
 274
 275       if (V2.isNegative() || V2.getBitWidth() > 64)
 276         return nullptr;
 277
 278       uint64_t Amt = V2.getZExtValue();
 279
 280       if (Amt >= V1.getBitWidth())
 281         return nullptr;
 282
 283       return &getValue( V1.operator<<( (unsigned) Amt ));
 284     }
 285
 286     case BO_Shr: {
 287       // FIXME: This logic should probably go higher up, where we can
 288       // test these conditions symbolically.
 289
 290       if (V2.isNegative() || V2.getBitWidth() > 64)
 291         return nullptr;
 292
 293       uint64_t Amt = V2.getZExtValue();
 294
 295       if (Amt >= V1.getBitWidth())
 296         return nullptr;
 297
 298       return &getValue( V1.operator>>( (unsigned) Amt ));
 299     }
 300
 301     case BO_LT:
 302       return &getTruthValue( V1 < V2 );
 303
 304     case BO_GT:
 305       return &getTruthValue( V1 > V2 );
 306
 307     case BO_LE:
 308       return &getTruthValue( V1 <= V2 );
 309
 310     case BO_GE:
 311       return &getTruthValue( V1 >= V2 );
 312
 313     case BO_EQ:
 314       return &getTruthValue( V1 == V2 );
 315
 316     case BO_NE:
 317       return &getTruthValue( V1 != V2 );
 318
 319       // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
 320
 321     case BO_And:
 322       return &getValue( V1 & V2 );
 323
 324     case BO_Or:
 325       return &getValue( V1 | V2 );
 326
 327     case BO_Xor:
 328       return &getValue( V1 ^ V2 );
 329   }
 330 }
 331
 332 const std::pair<SVal, uintptr_t>&
 333 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
 334   // Lazily create the folding set.
 335   if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
 336
 337   llvm::FoldingSetNodeID ID;
 338   void *InsertPos;
 339   V.Profile(ID);
 340   ID.AddPointer((void*) Data);
 341
 342   PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
 343
 344   using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
 345
 346   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
 347
 348   if (!P) {
 349     P = new (BPAlloc) FoldNodeTy(std::make_pair(V, Data));
 350     Map.InsertNode(P, InsertPos);
 351   }
 352
 353   return P->getValue();
 354 }
 355
 356 const std::pair<SVal, SVal>&
 357 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
 358   // Lazily create the folding set.
 359   if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
 360
 361   llvm::FoldingSetNodeID ID;
 362   void *InsertPos;
 363   V1.Profile(ID);
 364   V2.Profile(ID);
 365
 366   PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
 367
 368   using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
 369
 370   FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
 371
 372   if (!P) {
 373     P = new (BPAlloc) FoldNodeTy(std::make_pair(V1, V2));
 374     Map.InsertNode(P, InsertPos);
 375   }
 376
 377   return P->getValue();
 378 }
 379
 380 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
 381   return &getPersistentSValWithData(X, 0).first;
 382 }