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