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 } 292
