1 //===- BasicValueFactory.cpp - Basic values for Path Sens analysis --------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines BasicValueFactory, a class that manages the lifetime 10 // of APSInt objects and symbolic constraints used by ExprEngine 11 // and related classes. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 16 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 17 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 20 #include "llvm/ADT/APSInt.h" 21 #include "llvm/ADT/FoldingSet.h" 22 #include "llvm/ADT/ImmutableList.h" 23 #include "llvm/ADT/STLExtras.h" 24 #include <cassert> 25 #include <cstdint> 26 #include <utility> 27 28 using namespace clang; 29 using namespace ento; 30 31 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T, 32 llvm::ImmutableList<SVal> L) { 33 T.Profile(ID); 34 ID.AddPointer(L.getInternalPointer()); 35 } 36 37 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID, 38 const StoreRef &store, 39 const TypedValueRegion *region) { 40 ID.AddPointer(store.getStore()); 41 ID.AddPointer(region); 42 } 43 44 void PointerToMemberData::Profile( 45 llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D, 46 llvm::ImmutableList<const CXXBaseSpecifier *> L) { 47 ID.AddPointer(D); 48 ID.AddPointer(L.getInternalPointer()); 49 } 50 51 using SValData = std::pair<SVal, uintptr_t>; 52 using SValPair = std::pair<SVal, SVal>; 53 54 namespace llvm { 55 56 template<> struct FoldingSetTrait<SValData> { 57 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) { 58 X.first.Profile(ID); 59 ID.AddPointer( (void*) X.second); 60 } 61 }; 62 63 template<> struct FoldingSetTrait<SValPair> { 64 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) { 65 X.first.Profile(ID); 66 X.second.Profile(ID); 67 } 68 }; 69 70 } // namespace llvm 71 72 using PersistentSValsTy = 73 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>; 74 75 using PersistentSValPairsTy = 76 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>; 77 78 BasicValueFactory::~BasicValueFactory() { 79 // Note that the dstor for the contents of APSIntSet will never be called, 80 // so we iterate over the set and invoke the dstor for each APSInt. This 81 // frees an aux. memory allocated to represent very large constants. 82 for (const auto &I : APSIntSet) 83 I.getValue().~APSInt(); 84 85 delete (PersistentSValsTy*) PersistentSVals; 86 delete (PersistentSValPairsTy*) PersistentSValPairs; 87 } 88 89 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { 90 llvm::FoldingSetNodeID ID; 91 void *InsertPos; 92 93 using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>; 94 95 X.Profile(ID); 96 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); 97 98 if (!P) { 99 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 100 new (P) FoldNodeTy(X); 101 APSIntSet.InsertNode(P, InsertPos); 102 } 103 104 return *P; 105 } 106 107 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X, 108 bool isUnsigned) { 109 llvm::APSInt V(X, isUnsigned); 110 return getValue(V); 111 } 112 113 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, 114 bool isUnsigned) { 115 llvm::APSInt V(BitWidth, isUnsigned); 116 V = X; 117 return getValue(V); 118 } 119 120 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) { 121 return getValue(getAPSIntType(T).getValue(X)); 122 } 123 124 const CompoundValData* 125 BasicValueFactory::getCompoundValData(QualType T, 126 llvm::ImmutableList<SVal> Vals) { 127 llvm::FoldingSetNodeID ID; 128 CompoundValData::Profile(ID, T, Vals); 129 void *InsertPos; 130 131 CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 132 133 if (!D) { 134 D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>(); 135 new (D) CompoundValData(T, Vals); 136 CompoundValDataSet.InsertNode(D, InsertPos); 137 } 138 139 return D; 140 } 141 142 const LazyCompoundValData* 143 BasicValueFactory::getLazyCompoundValData(const StoreRef &store, 144 const TypedValueRegion *region) { 145 llvm::FoldingSetNodeID ID; 146 LazyCompoundValData::Profile(ID, store, region); 147 void *InsertPos; 148 149 LazyCompoundValData *D = 150 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 151 152 if (!D) { 153 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>(); 154 new (D) LazyCompoundValData(store, region); 155 LazyCompoundValDataSet.InsertNode(D, InsertPos); 156 } 157 158 return D; 159 } 160 161 const PointerToMemberData *BasicValueFactory::getPointerToMemberData( 162 const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) { 163 llvm::FoldingSetNodeID ID; 164 PointerToMemberData::Profile(ID, DD, L); 165 void *InsertPos; 166 167 PointerToMemberData *D = 168 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos); 169 170 if (!D) { 171 D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>(); 172 new (D) PointerToMemberData(DD, L); 173 PointerToMemberDataSet.InsertNode(D, InsertPos); 174 } 175 176 return D; 177 } 178 179 const PointerToMemberData *BasicValueFactory::accumCXXBase( 180 llvm::iterator_range<CastExpr::path_const_iterator> PathRange, 181 const nonloc::PointerToMember &PTM) { 182 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData(); 183 const DeclaratorDecl *DD = nullptr; 184 llvm::ImmutableList<const CXXBaseSpecifier *> PathList; 185 186 if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) { 187 if (PTMDT.is<const DeclaratorDecl *>()) 188 DD = PTMDT.get<const DeclaratorDecl *>(); 189 190 PathList = CXXBaseListFactory.getEmptyList(); 191 } else { // const PointerToMemberData * 192 const PointerToMemberData *PTMD = 193 PTMDT.get<const PointerToMemberData *>(); 194 DD = PTMD->getDeclaratorDecl(); 195 196 PathList = PTMD->getCXXBaseList(); 197 } 198 199 for (const auto &I : llvm::reverse(PathRange)) 200 PathList = prependCXXBase(I, PathList); 201 return getPointerToMemberData(DD, PathList); 202 } 203 204 const llvm::APSInt* 205 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, 206 const llvm::APSInt& V1, const llvm::APSInt& V2) { 207 switch (Op) { 208 default: 209 llvm_unreachable("Invalid Opcode."); 210 211 case BO_Mul: 212 return &getValue( V1 * V2 ); 213 214 case BO_Div: 215 if (V2 == 0) // Avoid division by zero 216 return nullptr; 217 return &getValue( V1 / V2 ); 218 219 case BO_Rem: 220 if (V2 == 0) // Avoid division by zero 221 return nullptr; 222 return &getValue( V1 % V2 ); 223 224 case BO_Add: 225 return &getValue( V1 + V2 ); 226 227 case BO_Sub: 228 return &getValue( V1 - V2 ); 229 230 case BO_Shl: { 231 // FIXME: This logic should probably go higher up, where we can 232 // test these conditions symbolically. 233 234 if (V2.isSigned() && V2.isNegative()) 235 return nullptr; 236 237 uint64_t Amt = V2.getZExtValue(); 238 239 if (Amt >= V1.getBitWidth()) 240 return nullptr; 241 242 if (!Ctx.getLangOpts().CPlusPlus20) { 243 if (V1.isSigned() && V1.isNegative()) 244 return nullptr; 245 246 if (V1.isSigned() && Amt > V1.countLeadingZeros()) 247 return nullptr; 248 } 249 250 return &getValue( V1.operator<<( (unsigned) Amt )); 251 } 252 253 case BO_Shr: { 254 // FIXME: This logic should probably go higher up, where we can 255 // test these conditions symbolically. 256 257 if (V2.isSigned() && V2.isNegative()) 258 return nullptr; 259 260 uint64_t Amt = V2.getZExtValue(); 261 262 if (Amt >= V1.getBitWidth()) 263 return nullptr; 264 265 return &getValue( V1.operator>>( (unsigned) Amt )); 266 } 267 268 case BO_LT: 269 return &getTruthValue( V1 < V2 ); 270 271 case BO_GT: 272 return &getTruthValue( V1 > V2 ); 273 274 case BO_LE: 275 return &getTruthValue( V1 <= V2 ); 276 277 case BO_GE: 278 return &getTruthValue( V1 >= V2 ); 279 280 case BO_EQ: 281 return &getTruthValue( V1 == V2 ); 282 283 case BO_NE: 284 return &getTruthValue( V1 != V2 ); 285 286 // Note: LAnd, LOr, Comma are handled specially by higher-level logic. 287 288 case BO_And: 289 return &getValue( V1 & V2 ); 290 291 case BO_Or: 292 return &getValue( V1 | V2 ); 293 294 case BO_Xor: 295 return &getValue( V1 ^ V2 ); 296 } 297 } 298 299 const std::pair<SVal, uintptr_t>& 300 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { 301 // Lazily create the folding set. 302 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy(); 303 304 llvm::FoldingSetNodeID ID; 305 void *InsertPos; 306 V.Profile(ID); 307 ID.AddPointer((void*) Data); 308 309 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); 310 311 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>; 312 313 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 314 315 if (!P) { 316 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 317 new (P) FoldNodeTy(std::make_pair(V, Data)); 318 Map.InsertNode(P, InsertPos); 319 } 320 321 return P->getValue(); 322 } 323 324 const std::pair<SVal, SVal>& 325 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { 326 // Lazily create the folding set. 327 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); 328 329 llvm::FoldingSetNodeID ID; 330 void *InsertPos; 331 V1.Profile(ID); 332 V2.Profile(ID); 333 334 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); 335 336 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>; 337 338 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 339 340 if (!P) { 341 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 342 new (P) FoldNodeTy(std::make_pair(V1, V2)); 343 Map.InsertNode(P, InsertPos); 344 } 345 346 return P->getValue(); 347 } 348 349 const SVal* BasicValueFactory::getPersistentSVal(SVal X) { 350 return &getPersistentSValWithData(X, 0).first; 351 } 352