1218887Sdim//=== BasicValueFactory.cpp - Basic values for Path Sens analysis --*- C++ -*-// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines BasicValueFactory, a class that manages the lifetime 11218887Sdim// of APSInt objects and symbolic constraints used by ExprEngine 12218887Sdim// and related classes. 13218887Sdim// 14218887Sdim//===----------------------------------------------------------------------===// 15218887Sdim 16245431Sdim#include "clang/AST/ASTContext.h" 17218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 18221345Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 19218887Sdim 20218887Sdimusing namespace clang; 21218887Sdimusing namespace ento; 22218887Sdim 23218887Sdimvoid CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T, 24218887Sdim llvm::ImmutableList<SVal> L) { 25218887Sdim T.Profile(ID); 26218887Sdim ID.AddPointer(L.getInternalPointer()); 27218887Sdim} 28218887Sdim 29218887Sdimvoid LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID, 30221345Sdim const StoreRef &store, 31226890Sdim const TypedValueRegion *region) { 32221345Sdim ID.AddPointer(store.getStore()); 33218887Sdim ID.AddPointer(region); 34218887Sdim} 35218887Sdim 36218887Sdimtypedef std::pair<SVal, uintptr_t> SValData; 37218887Sdimtypedef std::pair<SVal, SVal> SValPair; 38218887Sdim 39218887Sdimnamespace llvm { 40218887Sdimtemplate<> struct FoldingSetTrait<SValData> { 41218887Sdim static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) { 42218887Sdim X.first.Profile(ID); 43218887Sdim ID.AddPointer( (void*) X.second); 44218887Sdim } 45218887Sdim}; 46218887Sdim 47218887Sdimtemplate<> struct FoldingSetTrait<SValPair> { 48218887Sdim static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) { 49218887Sdim X.first.Profile(ID); 50218887Sdim X.second.Profile(ID); 51218887Sdim } 52218887Sdim}; 53218887Sdim} 54218887Sdim 55218887Sdimtypedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> > 56218887Sdim PersistentSValsTy; 57218887Sdim 58218887Sdimtypedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> > 59218887Sdim PersistentSValPairsTy; 60218887Sdim 61218887SdimBasicValueFactory::~BasicValueFactory() { 62218887Sdim // Note that the dstor for the contents of APSIntSet will never be called, 63218887Sdim // so we iterate over the set and invoke the dstor for each APSInt. This 64218887Sdim // frees an aux. memory allocated to represent very large constants. 65218887Sdim for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I) 66218887Sdim I->getValue().~APSInt(); 67218887Sdim 68218887Sdim delete (PersistentSValsTy*) PersistentSVals; 69218887Sdim delete (PersistentSValPairsTy*) PersistentSValPairs; 70218887Sdim} 71218887Sdim 72218887Sdimconst llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { 73218887Sdim llvm::FoldingSetNodeID ID; 74226890Sdim void *InsertPos; 75218887Sdim typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy; 76218887Sdim 77218887Sdim X.Profile(ID); 78218887Sdim FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); 79218887Sdim 80218887Sdim if (!P) { 81218887Sdim P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 82218887Sdim new (P) FoldNodeTy(X); 83218887Sdim APSIntSet.InsertNode(P, InsertPos); 84218887Sdim } 85218887Sdim 86218887Sdim return *P; 87218887Sdim} 88218887Sdim 89218887Sdimconst llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X, 90218887Sdim bool isUnsigned) { 91218887Sdim llvm::APSInt V(X, isUnsigned); 92218887Sdim return getValue(V); 93218887Sdim} 94218887Sdim 95218887Sdimconst llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, 96218887Sdim bool isUnsigned) { 97218887Sdim llvm::APSInt V(BitWidth, isUnsigned); 98218887Sdim V = X; 99218887Sdim return getValue(V); 100218887Sdim} 101218887Sdim 102218887Sdimconst llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) { 103218887Sdim 104245431Sdim return getValue(getAPSIntType(T).getValue(X)); 105218887Sdim} 106218887Sdim 107218887Sdimconst CompoundValData* 108218887SdimBasicValueFactory::getCompoundValData(QualType T, 109218887Sdim llvm::ImmutableList<SVal> Vals) { 110218887Sdim 111218887Sdim llvm::FoldingSetNodeID ID; 112218887Sdim CompoundValData::Profile(ID, T, Vals); 113226890Sdim void *InsertPos; 114218887Sdim 115218887Sdim CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 116218887Sdim 117218887Sdim if (!D) { 118218887Sdim D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>(); 119218887Sdim new (D) CompoundValData(T, Vals); 120218887Sdim CompoundValDataSet.InsertNode(D, InsertPos); 121218887Sdim } 122218887Sdim 123218887Sdim return D; 124218887Sdim} 125218887Sdim 126218887Sdimconst LazyCompoundValData* 127221345SdimBasicValueFactory::getLazyCompoundValData(const StoreRef &store, 128226890Sdim const TypedValueRegion *region) { 129218887Sdim llvm::FoldingSetNodeID ID; 130218887Sdim LazyCompoundValData::Profile(ID, store, region); 131226890Sdim void *InsertPos; 132218887Sdim 133218887Sdim LazyCompoundValData *D = 134218887Sdim LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 135218887Sdim 136218887Sdim if (!D) { 137218887Sdim D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>(); 138218887Sdim new (D) LazyCompoundValData(store, region); 139218887Sdim LazyCompoundValDataSet.InsertNode(D, InsertPos); 140218887Sdim } 141218887Sdim 142218887Sdim return D; 143218887Sdim} 144218887Sdim 145218887Sdimconst llvm::APSInt* 146218887SdimBasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, 147218887Sdim const llvm::APSInt& V1, const llvm::APSInt& V2) { 148218887Sdim 149218887Sdim switch (Op) { 150218887Sdim default: 151218887Sdim assert (false && "Invalid Opcode."); 152218887Sdim 153218887Sdim case BO_Mul: 154218887Sdim return &getValue( V1 * V2 ); 155218887Sdim 156218887Sdim case BO_Div: 157218887Sdim return &getValue( V1 / V2 ); 158218887Sdim 159218887Sdim case BO_Rem: 160218887Sdim return &getValue( V1 % V2 ); 161218887Sdim 162218887Sdim case BO_Add: 163218887Sdim return &getValue( V1 + V2 ); 164218887Sdim 165218887Sdim case BO_Sub: 166218887Sdim return &getValue( V1 - V2 ); 167218887Sdim 168218887Sdim case BO_Shl: { 169218887Sdim 170218887Sdim // FIXME: This logic should probably go higher up, where we can 171218887Sdim // test these conditions symbolically. 172218887Sdim 173218887Sdim // FIXME: Expand these checks to include all undefined behavior. 174218887Sdim 175218887Sdim if (V2.isSigned() && V2.isNegative()) 176218887Sdim return NULL; 177218887Sdim 178218887Sdim uint64_t Amt = V2.getZExtValue(); 179218887Sdim 180218887Sdim if (Amt > V1.getBitWidth()) 181218887Sdim return NULL; 182218887Sdim 183218887Sdim return &getValue( V1.operator<<( (unsigned) Amt )); 184218887Sdim } 185218887Sdim 186218887Sdim case BO_Shr: { 187218887Sdim 188218887Sdim // FIXME: This logic should probably go higher up, where we can 189218887Sdim // test these conditions symbolically. 190218887Sdim 191218887Sdim // FIXME: Expand these checks to include all undefined behavior. 192218887Sdim 193218887Sdim if (V2.isSigned() && V2.isNegative()) 194218887Sdim return NULL; 195218887Sdim 196218887Sdim uint64_t Amt = V2.getZExtValue(); 197218887Sdim 198218887Sdim if (Amt > V1.getBitWidth()) 199218887Sdim return NULL; 200218887Sdim 201218887Sdim return &getValue( V1.operator>>( (unsigned) Amt )); 202218887Sdim } 203218887Sdim 204218887Sdim case BO_LT: 205218887Sdim return &getTruthValue( V1 < V2 ); 206218887Sdim 207218887Sdim case BO_GT: 208218887Sdim return &getTruthValue( V1 > V2 ); 209218887Sdim 210218887Sdim case BO_LE: 211218887Sdim return &getTruthValue( V1 <= V2 ); 212218887Sdim 213218887Sdim case BO_GE: 214218887Sdim return &getTruthValue( V1 >= V2 ); 215218887Sdim 216218887Sdim case BO_EQ: 217218887Sdim return &getTruthValue( V1 == V2 ); 218218887Sdim 219218887Sdim case BO_NE: 220218887Sdim return &getTruthValue( V1 != V2 ); 221218887Sdim 222218887Sdim // Note: LAnd, LOr, Comma are handled specially by higher-level logic. 223218887Sdim 224218887Sdim case BO_And: 225218887Sdim return &getValue( V1 & V2 ); 226218887Sdim 227218887Sdim case BO_Or: 228218887Sdim return &getValue( V1 | V2 ); 229218887Sdim 230218887Sdim case BO_Xor: 231218887Sdim return &getValue( V1 ^ V2 ); 232218887Sdim } 233218887Sdim} 234218887Sdim 235218887Sdim 236218887Sdimconst std::pair<SVal, uintptr_t>& 237218887SdimBasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { 238218887Sdim 239218887Sdim // Lazily create the folding set. 240218887Sdim if (!PersistentSVals) PersistentSVals = new PersistentSValsTy(); 241218887Sdim 242218887Sdim llvm::FoldingSetNodeID ID; 243226890Sdim void *InsertPos; 244218887Sdim V.Profile(ID); 245218887Sdim ID.AddPointer((void*) Data); 246218887Sdim 247218887Sdim PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); 248218887Sdim 249218887Sdim typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy; 250218887Sdim FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 251218887Sdim 252218887Sdim if (!P) { 253218887Sdim P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 254218887Sdim new (P) FoldNodeTy(std::make_pair(V, Data)); 255218887Sdim Map.InsertNode(P, InsertPos); 256218887Sdim } 257218887Sdim 258218887Sdim return P->getValue(); 259218887Sdim} 260218887Sdim 261218887Sdimconst std::pair<SVal, SVal>& 262218887SdimBasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { 263218887Sdim 264218887Sdim // Lazily create the folding set. 265218887Sdim if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); 266218887Sdim 267218887Sdim llvm::FoldingSetNodeID ID; 268226890Sdim void *InsertPos; 269218887Sdim V1.Profile(ID); 270218887Sdim V2.Profile(ID); 271218887Sdim 272218887Sdim PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); 273218887Sdim 274218887Sdim typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy; 275218887Sdim FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 276218887Sdim 277218887Sdim if (!P) { 278218887Sdim P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 279218887Sdim new (P) FoldNodeTy(std::make_pair(V1, V2)); 280218887Sdim Map.InsertNode(P, InsertPos); 281218887Sdim } 282218887Sdim 283218887Sdim return P->getValue(); 284218887Sdim} 285218887Sdim 286218887Sdimconst SVal* BasicValueFactory::getPersistentSVal(SVal X) { 287218887Sdim return &getPersistentSValWithData(X, 0).first; 288218887Sdim} 289