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 = new (BPAlloc) 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 = new (BPAlloc) CompoundValData(T, Vals); 135 CompoundValDataSet.InsertNode(D, InsertPos); 136 } 137 138 return D; 139 } 140 141 const LazyCompoundValData* 142 BasicValueFactory::getLazyCompoundValData(const StoreRef &store, 143 const TypedValueRegion *region) { 144 llvm::FoldingSetNodeID ID; 145 LazyCompoundValData::Profile(ID, store, region); 146 void *InsertPos; 147 148 LazyCompoundValData *D = 149 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 150 151 if (!D) { 152 D = new (BPAlloc) LazyCompoundValData(store, region); 153 LazyCompoundValDataSet.InsertNode(D, InsertPos); 154 } 155 156 return D; 157 } 158 159 const PointerToMemberData *BasicValueFactory::getPointerToMemberData( 160 const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) { 161 llvm::FoldingSetNodeID ID; 162 PointerToMemberData::Profile(ID, ND, L); 163 void *InsertPos; 164 165 PointerToMemberData *D = 166 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos); 167 168 if (!D) { 169 D = new (BPAlloc) PointerToMemberData(ND, L); 170 PointerToMemberDataSet.InsertNode(D, InsertPos); 171 } 172 173 return D; 174 } 175 176 LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements( 177 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) { 178 llvm::SmallPtrSet<QualType, 16> BaseSpecSeen; 179 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) { 180 QualType BaseType = BaseSpec->getType(); 181 // Check whether inserted 182 if (!BaseSpecSeen.insert(BaseType).second) 183 return false; 184 } 185 return true; 186 } 187 188 const PointerToMemberData *BasicValueFactory::accumCXXBase( 189 llvm::iterator_range<CastExpr::path_const_iterator> PathRange, 190 const nonloc::PointerToMember &PTM, const CastKind &kind) { 191 assert((kind == CK_DerivedToBaseMemberPointer || 192 kind == CK_BaseToDerivedMemberPointer || 193 kind == CK_ReinterpretMemberPointer) && 194 "accumCXXBase called with wrong CastKind"); 195 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData(); 196 const NamedDecl *ND = nullptr; 197 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList; 198 199 if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) { 200 if (PTMDT.is<const NamedDecl *>()) 201 ND = PTMDT.get<const NamedDecl *>(); 202 203 BaseSpecList = CXXBaseListFactory.getEmptyList(); 204 } else { 205 const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>(); 206 ND = PTMD->getDeclaratorDecl(); 207 208 BaseSpecList = PTMD->getCXXBaseList(); 209 } 210 211 assert(hasNoRepeatedElements(BaseSpecList) && 212 "CXXBaseSpecifier list of PointerToMemberData must not have repeated " 213 "elements"); 214 215 if (kind == CK_DerivedToBaseMemberPointer) { 216 // Here we pop off matching CXXBaseSpecifiers from BaseSpecList. 217 // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and 218 // serves to remove a matching implicit cast. Note that static_cast's that 219 // are no-ops do not count since they produce an empty PathRange, a nice 220 // thing about Clang AST. 221 222 // Now we know that there are no repetitions in BaseSpecList. 223 // So, popping the first element from it corresponding to each element in 224 // PathRange is equivalent to only including elements that are in 225 // BaseSpecList but not it PathRange 226 auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList(); 227 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) { 228 auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool { 229 return BaseSpec->getType() == I->getType(); 230 }; 231 if (llvm::none_of(PathRange, IsSameAsBaseSpec)) 232 ReducedBaseSpecList = 233 CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList); 234 } 235 236 return getPointerToMemberData(ND, ReducedBaseSpecList); 237 } 238 // FIXME: Reinterpret casts on member-pointers are not handled properly by 239 // this code 240 for (const CXXBaseSpecifier *I : llvm::reverse(PathRange)) 241 BaseSpecList = prependCXXBase(I, BaseSpecList); 242 return getPointerToMemberData(ND, BaseSpecList); 243 } 244 245 const llvm::APSInt* 246 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, 247 const llvm::APSInt& V1, const llvm::APSInt& V2) { 248 switch (Op) { 249 default: 250 llvm_unreachable("Invalid Opcode."); 251 252 case BO_Mul: 253 return &getValue( V1 * V2 ); 254 255 case BO_Div: 256 if (V2 == 0) // Avoid division by zero 257 return nullptr; 258 return &getValue( V1 / V2 ); 259 260 case BO_Rem: 261 if (V2 == 0) // Avoid division by zero 262 return nullptr; 263 return &getValue( V1 % V2 ); 264 265 case BO_Add: 266 return &getValue( V1 + V2 ); 267 268 case BO_Sub: 269 return &getValue( V1 - V2 ); 270 271 case BO_Shl: { 272 // FIXME: This logic should probably go higher up, where we can 273 // test these conditions symbolically. 274 275 if (V2.isSigned() && V2.isNegative()) 276 return nullptr; 277 278 uint64_t Amt = V2.getZExtValue(); 279 280 if (Amt >= V1.getBitWidth()) 281 return nullptr; 282 283 if (!Ctx.getLangOpts().CPlusPlus20) { 284 if (V1.isSigned() && V1.isNegative()) 285 return nullptr; 286 287 if (V1.isSigned() && Amt > V1.countl_zero()) 288 return nullptr; 289 } 290 291 return &getValue( V1.operator<<( (unsigned) Amt )); 292 } 293 294 case BO_Shr: { 295 // FIXME: This logic should probably go higher up, where we can 296 // test these conditions symbolically. 297 298 if (V2.isSigned() && V2.isNegative()) 299 return nullptr; 300 301 uint64_t Amt = V2.getZExtValue(); 302 303 if (Amt >= V1.getBitWidth()) 304 return nullptr; 305 306 return &getValue( V1.operator>>( (unsigned) Amt )); 307 } 308 309 case BO_LT: 310 return &getTruthValue( V1 < V2 ); 311 312 case BO_GT: 313 return &getTruthValue( V1 > V2 ); 314 315 case BO_LE: 316 return &getTruthValue( V1 <= V2 ); 317 318 case BO_GE: 319 return &getTruthValue( V1 >= V2 ); 320 321 case BO_EQ: 322 return &getTruthValue( V1 == V2 ); 323 324 case BO_NE: 325 return &getTruthValue( V1 != V2 ); 326 327 // Note: LAnd, LOr, Comma are handled specially by higher-level logic. 328 329 case BO_And: 330 return &getValue( V1 & V2 ); 331 332 case BO_Or: 333 return &getValue( V1 | V2 ); 334 335 case BO_Xor: 336 return &getValue( V1 ^ V2 ); 337 } 338 } 339 340 const std::pair<SVal, uintptr_t>& 341 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { 342 // Lazily create the folding set. 343 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy(); 344 345 llvm::FoldingSetNodeID ID; 346 void *InsertPos; 347 V.Profile(ID); 348 ID.AddPointer((void*) Data); 349 350 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); 351 352 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>; 353 354 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 355 356 if (!P) { 357 P = new (BPAlloc) FoldNodeTy(std::make_pair(V, Data)); 358 Map.InsertNode(P, InsertPos); 359 } 360 361 return P->getValue(); 362 } 363 364 const std::pair<SVal, SVal>& 365 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { 366 // Lazily create the folding set. 367 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); 368 369 llvm::FoldingSetNodeID ID; 370 void *InsertPos; 371 V1.Profile(ID); 372 V2.Profile(ID); 373 374 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); 375 376 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>; 377 378 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 379 380 if (!P) { 381 P = new (BPAlloc) FoldNodeTy(std::make_pair(V1, V2)); 382 Map.InsertNode(P, InsertPos); 383 } 384 385 return P->getValue(); 386 } 387 388 const SVal* BasicValueFactory::getPersistentSVal(SVal X) { 389 return &getPersistentSValWithData(X, 0).first; 390 } 391