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