383 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines BasicValueFactory, a class that manages the lifetime10// of APSInt objects and symbolic constraints used by ExprEngine11// 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 29using namespace clang;30using namespace ento;31 32void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,33 llvm::ImmutableList<SVal> L) {34 T.Profile(ID);35 ID.AddPointer(L.getInternalPointer());36}37 38void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,39 const StoreRef &store,40 const TypedValueRegion *region) {41 ID.AddPointer(store.getStore());42 ID.AddPointer(region);43}44 45void 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 52using SValData = std::pair<SVal, uintptr_t>;53using SValPair = std::pair<SVal, SVal>;54 55namespace llvm {56 57template<> 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 64template<> 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 llvm72 73using PersistentSValsTy =74 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;75 76using PersistentSValPairsTy =77 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;78 79BasicValueFactory::~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. This82 // 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 90APSIntPtr 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 108APSIntPtr BasicValueFactory::getValue(const llvm::APInt &X, bool isUnsigned) {109 llvm::APSInt V(X, isUnsigned);110 return getValue(V);111}112 113APSIntPtr 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 120APSIntPtr BasicValueFactory::getValue(uint64_t X, QualType T) {121 return getValue(getAPSIntType(T).getValue(X));122}123 124const CompoundValData*125BasicValueFactory::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 141const LazyCompoundValData*142BasicValueFactory::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 159const 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[[maybe_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 inserted182 if (!BaseSpecSeen.insert(BaseType).second)183 return false;184 }185 return true;186}187 188const 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 and218 // serves to remove a matching implicit cast. Note that static_cast's that219 // are no-ops do not count since they produce an empty PathRange, a nice220 // 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 in224 // PathRange is equivalent to only including elements that are in225 // BaseSpecList but not it PathRange226 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 by239 // this code240 for (const CXXBaseSpecifier *I : llvm::reverse(PathRange))241 BaseSpecList = prependCXXBase(I, BaseSpecList);242 return getPointerToMemberData(ND, BaseSpecList);243}244 245std::optional<APSIntPtr>246BasicValueFactory::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 zero257 return std::nullopt;258 return getValue(V1 / V2);259 260 case BO_Rem:261 if (V2 == 0) // Avoid division by zero262 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 can273 // 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 can288 // 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 332const std::pair<SVal, uintptr_t>&333BasicValueFactory::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 356const std::pair<SVal, SVal>&357BasicValueFactory::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 380const SVal* BasicValueFactory::getPersistentSVal(SVal X) {381 return &getPersistentSValWithData(X, 0).first;382}383