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 APSIntPtr 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 // We own the APSInt object. It's safe here. 105 return APSIntPtr::unsafeConstructor(&P->getValue()); 106 } 107 108 APSIntPtr BasicValueFactory::getValue(const llvm::APInt &X, bool isUnsigned) { 109 llvm::APSInt V(X, isUnsigned); 110 return getValue(V); 111 } 112 113 APSIntPtr 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 APSIntPtr 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 static 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() || isa<const NamedDecl *>(PTMDT)) { 200 if (const auto *NDP = dyn_cast_if_present<const NamedDecl *>(PTMDT)) 201 ND = NDP; 202 203 BaseSpecList = CXXBaseListFactory.getEmptyList(); 204 } else { 205 const auto *PTMD = cast<const PointerToMemberData *>(PTMDT); 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 std::optional<APSIntPtr> 246 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1, 247 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 std::nullopt; 258 return getValue(V1 / V2); 259 260 case BO_Rem: 261 if (V2 == 0) // Avoid division by zero 262 return std::nullopt; 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.isNegative() || V2.getBitWidth() > 64) 276 return std::nullopt; 277 278 uint64_t Amt = V2.getZExtValue(); 279 280 if (Amt >= V1.getBitWidth()) 281 return std::nullopt; 282 283 return getValue(V1.operator<<((unsigned)Amt)); 284 } 285 286 case BO_Shr: { 287 // FIXME: This logic should probably go higher up, where we can 288 // test these conditions symbolically. 289 290 if (V2.isNegative() || V2.getBitWidth() > 64) 291 return std::nullopt; 292 293 uint64_t Amt = V2.getZExtValue(); 294 295 if (Amt >= V1.getBitWidth()) 296 return std::nullopt; 297 298 return getValue(V1.operator>>((unsigned)Amt)); 299 } 300 301 case BO_LT: 302 return getTruthValue(V1 < V2); 303 304 case BO_GT: 305 return getTruthValue(V1 > V2); 306 307 case BO_LE: 308 return getTruthValue(V1 <= V2); 309 310 case BO_GE: 311 return getTruthValue(V1 >= V2); 312 313 case BO_EQ: 314 return getTruthValue(V1 == V2); 315 316 case BO_NE: 317 return getTruthValue(V1 != V2); 318 319 // Note: LAnd, LOr, Comma are handled specially by higher-level logic. 320 321 case BO_And: 322 return getValue(V1 & V2); 323 324 case BO_Or: 325 return getValue(V1 | V2); 326 327 case BO_Xor: 328 return getValue(V1 ^ V2); 329 } 330 } 331 332 const std::pair<SVal, uintptr_t>& 333 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { 334 // Lazily create the folding set. 335 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy(); 336 337 llvm::FoldingSetNodeID ID; 338 void *InsertPos; 339 V.Profile(ID); 340 ID.AddPointer((void*) Data); 341 342 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); 343 344 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>; 345 346 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 347 348 if (!P) { 349 P = new (BPAlloc) FoldNodeTy(std::make_pair(V, Data)); 350 Map.InsertNode(P, InsertPos); 351 } 352 353 return P->getValue(); 354 } 355 356 const std::pair<SVal, SVal>& 357 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { 358 // Lazily create the folding set. 359 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); 360 361 llvm::FoldingSetNodeID ID; 362 void *InsertPos; 363 V1.Profile(ID); 364 V2.Profile(ID); 365 366 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); 367 368 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>; 369 370 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 371 372 if (!P) { 373 P = new (BPAlloc) FoldNodeTy(std::make_pair(V1, V2)); 374 Map.InsertNode(P, InsertPos); 375 } 376 377 return P->getValue(); 378 } 379 380 const SVal* BasicValueFactory::getPersistentSVal(SVal X) { 381 return &getPersistentSValWithData(X, 0).first; 382 } 383