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