| 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 |
} |