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