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