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 "llvm/ADT/SmallPtrSet.h" 25 #include <cassert> 26 #include <cstdint> 27 #include <utility> 28 29 using namespace clang; 30 using namespace ento; 31 32 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T, 33 llvm::ImmutableList<SVal> L) { 34 T.Profile(ID); 35 ID.AddPointer(L.getInternalPointer()); 36 } 37 38 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID, 39 const StoreRef &store, 40 const TypedValueRegion *region) { 41 ID.AddPointer(store.getStore()); 42 ID.AddPointer(region); 43 } 44 45 void PointerToMemberData::Profile( 46 llvm::FoldingSetNodeID &ID, const NamedDecl *D, 47 llvm::ImmutableList<const CXXBaseSpecifier *> L) { 48 ID.AddPointer(D); 49 ID.AddPointer(L.getInternalPointer()); 50 } 51 52 using SValData = std::pair<SVal, uintptr_t>; 53 using SValPair = std::pair<SVal, SVal>; 54 55 namespace llvm { 56 57 template<> struct FoldingSetTrait<SValData> { 58 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) { 59 X.first.Profile(ID); 60 ID.AddPointer( (void*) X.second); 61 } 62 }; 63 64 template<> struct FoldingSetTrait<SValPair> { 65 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) { 66 X.first.Profile(ID); 67 X.second.Profile(ID); 68 } 69 }; 70 71 } // namespace llvm 72 73 using PersistentSValsTy = 74 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>; 75 76 using PersistentSValPairsTy = 77 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>; 78 79 BasicValueFactory::~BasicValueFactory() { 80 // Note that the dstor for the contents of APSIntSet will never be called, 81 // so we iterate over the set and invoke the dstor for each APSInt. This 82 // frees an aux. memory allocated to represent very large constants. 83 for (const auto &I : APSIntSet) 84 I.getValue().~APSInt(); 85 86 delete (PersistentSValsTy*) PersistentSVals; 87 delete (PersistentSValPairsTy*) PersistentSValPairs; 88 } 89 90 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { 91 llvm::FoldingSetNodeID ID; 92 void *InsertPos; 93 94 using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>; 95 96 X.Profile(ID); 97 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); 98 99 if (!P) { 100 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 101 new (P) FoldNodeTy(X); 102 APSIntSet.InsertNode(P, InsertPos); 103 } 104 105 return *P; 106 } 107 108 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X, 109 bool isUnsigned) { 110 llvm::APSInt V(X, isUnsigned); 111 return getValue(V); 112 } 113 114 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, 115 bool isUnsigned) { 116 llvm::APSInt V(BitWidth, isUnsigned); 117 V = X; 118 return getValue(V); 119 } 120 121 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) { 122 return getValue(getAPSIntType(T).getValue(X)); 123 } 124 125 const CompoundValData* 126 BasicValueFactory::getCompoundValData(QualType T, 127 llvm::ImmutableList<SVal> Vals) { 128 llvm::FoldingSetNodeID ID; 129 CompoundValData::Profile(ID, T, Vals); 130 void *InsertPos; 131 132 CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 133 134 if (!D) { 135 D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>(); 136 new (D) CompoundValData(T, Vals); 137 CompoundValDataSet.InsertNode(D, InsertPos); 138 } 139 140 return D; 141 } 142 143 const LazyCompoundValData* 144 BasicValueFactory::getLazyCompoundValData(const StoreRef &store, 145 const TypedValueRegion *region) { 146 llvm::FoldingSetNodeID ID; 147 LazyCompoundValData::Profile(ID, store, region); 148 void *InsertPos; 149 150 LazyCompoundValData *D = 151 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 152 153 if (!D) { 154 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>(); 155 new (D) LazyCompoundValData(store, region); 156 LazyCompoundValDataSet.InsertNode(D, InsertPos); 157 } 158 159 return D; 160 } 161 162 const PointerToMemberData *BasicValueFactory::getPointerToMemberData( 163 const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) { 164 llvm::FoldingSetNodeID ID; 165 PointerToMemberData::Profile(ID, ND, L); 166 void *InsertPos; 167 168 PointerToMemberData *D = 169 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos); 170 171 if (!D) { 172 D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>(); 173 new (D) PointerToMemberData(ND, L); 174 PointerToMemberDataSet.InsertNode(D, InsertPos); 175 } 176 177 return D; 178 } 179 180 LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements( 181 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) { 182 llvm::SmallPtrSet<QualType, 16> BaseSpecSeen; 183 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) { 184 QualType BaseType = BaseSpec->getType(); 185 // Check whether inserted 186 if (!BaseSpecSeen.insert(BaseType).second) 187 return false; 188 } 189 return true; 190 } 191 192 const PointerToMemberData *BasicValueFactory::accumCXXBase( 193 llvm::iterator_range<CastExpr::path_const_iterator> PathRange, 194 const nonloc::PointerToMember &PTM, const CastKind &kind) { 195 assert((kind == CK_DerivedToBaseMemberPointer || 196 kind == CK_BaseToDerivedMemberPointer || 197 kind == CK_ReinterpretMemberPointer) && 198 "accumCXXBase called with wrong CastKind"); 199 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData(); 200 const NamedDecl *ND = nullptr; 201 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList; 202 203 if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) { 204 if (PTMDT.is<const NamedDecl *>()) 205 ND = PTMDT.get<const NamedDecl *>(); 206 207 BaseSpecList = CXXBaseListFactory.getEmptyList(); 208 } else { 209 const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>(); 210 ND = PTMD->getDeclaratorDecl(); 211 212 BaseSpecList = PTMD->getCXXBaseList(); 213 } 214 215 assert(hasNoRepeatedElements(BaseSpecList) && 216 "CXXBaseSpecifier list of PointerToMemberData must not have repeated " 217 "elements"); 218 219 if (kind == CK_DerivedToBaseMemberPointer) { 220 // Here we pop off matching CXXBaseSpecifiers from BaseSpecList. 221 // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and 222 // serves to remove a matching implicit cast. Note that static_cast's that 223 // are no-ops do not count since they produce an empty PathRange, a nice 224 // thing about Clang AST. 225 226 // Now we know that there are no repetitions in BaseSpecList. 227 // So, popping the first element from it corresponding to each element in 228 // PathRange is equivalent to only including elements that are in 229 // BaseSpecList but not it PathRange 230 auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList(); 231 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) { 232 auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool { 233 return BaseSpec->getType() == I->getType(); 234 }; 235 if (llvm::none_of(PathRange, IsSameAsBaseSpec)) 236 ReducedBaseSpecList = 237 CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList); 238 } 239 240 return getPointerToMemberData(ND, ReducedBaseSpecList); 241 } 242 // FIXME: Reinterpret casts on member-pointers are not handled properly by 243 // this code 244 for (const CXXBaseSpecifier *I : llvm::reverse(PathRange)) 245 BaseSpecList = prependCXXBase(I, BaseSpecList); 246 return getPointerToMemberData(ND, BaseSpecList); 247 } 248 249 const llvm::APSInt* 250 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, 251 const llvm::APSInt& V1, const llvm::APSInt& V2) { 252 switch (Op) { 253 default: 254 llvm_unreachable("Invalid Opcode."); 255 256 case BO_Mul: 257 return &getValue( V1 * V2 ); 258 259 case BO_Div: 260 if (V2 == 0) // Avoid division by zero 261 return nullptr; 262 return &getValue( V1 / V2 ); 263 264 case BO_Rem: 265 if (V2 == 0) // Avoid division by zero 266 return nullptr; 267 return &getValue( V1 % V2 ); 268 269 case BO_Add: 270 return &getValue( V1 + V2 ); 271 272 case BO_Sub: 273 return &getValue( V1 - V2 ); 274 275 case BO_Shl: { 276 // FIXME: This logic should probably go higher up, where we can 277 // test these conditions symbolically. 278 279 if (V2.isSigned() && V2.isNegative()) 280 return nullptr; 281 282 uint64_t Amt = V2.getZExtValue(); 283 284 if (Amt >= V1.getBitWidth()) 285 return nullptr; 286 287 if (!Ctx.getLangOpts().CPlusPlus20) { 288 if (V1.isSigned() && V1.isNegative()) 289 return nullptr; 290 291 if (V1.isSigned() && Amt > V1.countLeadingZeros()) 292 return nullptr; 293 } 294 295 return &getValue( V1.operator<<( (unsigned) Amt )); 296 } 297 298 case BO_Shr: { 299 // FIXME: This logic should probably go higher up, where we can 300 // test these conditions symbolically. 301 302 if (V2.isSigned() && V2.isNegative()) 303 return nullptr; 304 305 uint64_t Amt = V2.getZExtValue(); 306 307 if (Amt >= V1.getBitWidth()) 308 return nullptr; 309 310 return &getValue( V1.operator>>( (unsigned) Amt )); 311 } 312 313 case BO_LT: 314 return &getTruthValue( V1 < V2 ); 315 316 case BO_GT: 317 return &getTruthValue( V1 > V2 ); 318 319 case BO_LE: 320 return &getTruthValue( V1 <= V2 ); 321 322 case BO_GE: 323 return &getTruthValue( V1 >= V2 ); 324 325 case BO_EQ: 326 return &getTruthValue( V1 == V2 ); 327 328 case BO_NE: 329 return &getTruthValue( V1 != V2 ); 330 331 // Note: LAnd, LOr, Comma are handled specially by higher-level logic. 332 333 case BO_And: 334 return &getValue( V1 & V2 ); 335 336 case BO_Or: 337 return &getValue( V1 | V2 ); 338 339 case BO_Xor: 340 return &getValue( V1 ^ V2 ); 341 } 342 } 343 344 const std::pair<SVal, uintptr_t>& 345 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { 346 // Lazily create the folding set. 347 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy(); 348 349 llvm::FoldingSetNodeID ID; 350 void *InsertPos; 351 V.Profile(ID); 352 ID.AddPointer((void*) Data); 353 354 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); 355 356 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>; 357 358 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 359 360 if (!P) { 361 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 362 new (P) FoldNodeTy(std::make_pair(V, Data)); 363 Map.InsertNode(P, InsertPos); 364 } 365 366 return P->getValue(); 367 } 368 369 const std::pair<SVal, SVal>& 370 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { 371 // Lazily create the folding set. 372 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); 373 374 llvm::FoldingSetNodeID ID; 375 void *InsertPos; 376 V1.Profile(ID); 377 V2.Profile(ID); 378 379 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); 380 381 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>; 382 383 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 384 385 if (!P) { 386 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 387 new (P) FoldNodeTy(std::make_pair(V1, V2)); 388 Map.InsertNode(P, InsertPos); 389 } 390 391 return P->getValue(); 392 } 393 394 const SVal* BasicValueFactory::getPersistentSVal(SVal X) { 395 return &getPersistentSValWithData(X, 0).first; 396 } 397