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 <cassert> 25#include <cstdint> 26#include <utility> 27 28using namespace clang; 29using namespace ento; 30 31void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T, 32 llvm::ImmutableList<SVal> L) { 33 T.Profile(ID); 34 ID.AddPointer(L.getInternalPointer()); 35} 36 37void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID, 38 const StoreRef &store, 39 const TypedValueRegion *region) { 40 ID.AddPointer(store.getStore()); 41 ID.AddPointer(region); 42} 43 44void PointerToMemberData::Profile( 45 llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D, 46 llvm::ImmutableList<const CXXBaseSpecifier *> L) { 47 ID.AddPointer(D); 48 ID.AddPointer(L.getInternalPointer()); 49} 50 51using SValData = std::pair<SVal, uintptr_t>; 52using SValPair = std::pair<SVal, SVal>; 53 54namespace llvm { 55 56template<> struct FoldingSetTrait<SValData> { 57 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) { 58 X.first.Profile(ID); 59 ID.AddPointer( (void*) X.second); 60 } 61}; 62 63template<> struct FoldingSetTrait<SValPair> { 64 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) { 65 X.first.Profile(ID); 66 X.second.Profile(ID); 67 } 68}; 69 70} // namespace llvm 71 72using PersistentSValsTy = 73 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>; 74 75using PersistentSValPairsTy = 76 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>; 77 78BasicValueFactory::~BasicValueFactory() { 79 // Note that the dstor for the contents of APSIntSet will never be called, 80 // so we iterate over the set and invoke the dstor for each APSInt. This 81 // frees an aux. memory allocated to represent very large constants. 82 for (const auto &I : APSIntSet) 83 I.getValue().~APSInt(); 84 85 delete (PersistentSValsTy*) PersistentSVals; 86 delete (PersistentSValPairsTy*) PersistentSValPairs; 87} 88 89const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { 90 llvm::FoldingSetNodeID ID; 91 void *InsertPos; 92 93 using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>; 94 95 X.Profile(ID); 96 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); 97 98 if (!P) { 99 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 100 new (P) FoldNodeTy(X); 101 APSIntSet.InsertNode(P, InsertPos); 102 } 103 104 return *P; 105} 106 107const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X, 108 bool isUnsigned) { 109 llvm::APSInt V(X, isUnsigned); 110 return getValue(V); 111} 112 113const 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 120const llvm::APSInt& 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 = (CompoundValData*) BPAlloc.Allocate<CompoundValData>(); 135 new (D) CompoundValData(T, Vals); 136 CompoundValDataSet.InsertNode(D, InsertPos); 137 } 138 139 return D; 140} 141 142const LazyCompoundValData* 143BasicValueFactory::getLazyCompoundValData(const StoreRef &store, 144 const TypedValueRegion *region) { 145 llvm::FoldingSetNodeID ID; 146 LazyCompoundValData::Profile(ID, store, region); 147 void *InsertPos; 148 149 LazyCompoundValData *D = 150 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); 151 152 if (!D) { 153 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>(); 154 new (D) LazyCompoundValData(store, region); 155 LazyCompoundValDataSet.InsertNode(D, InsertPos); 156 } 157 158 return D; 159} 160 161const PointerToMemberData *BasicValueFactory::getPointerToMemberData( 162 const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) { 163 llvm::FoldingSetNodeID ID; 164 PointerToMemberData::Profile(ID, DD, L); 165 void *InsertPos; 166 167 PointerToMemberData *D = 168 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos); 169 170 if (!D) { 171 D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>(); 172 new (D) PointerToMemberData(DD, L); 173 PointerToMemberDataSet.InsertNode(D, InsertPos); 174 } 175 176 return D; 177} 178 179const PointerToMemberData *BasicValueFactory::accumCXXBase( 180 llvm::iterator_range<CastExpr::path_const_iterator> PathRange, 181 const nonloc::PointerToMember &PTM) { 182 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData(); 183 const DeclaratorDecl *DD = nullptr; 184 llvm::ImmutableList<const CXXBaseSpecifier *> PathList; 185 186 if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) { 187 if (PTMDT.is<const DeclaratorDecl *>()) 188 DD = PTMDT.get<const DeclaratorDecl *>(); 189 190 PathList = CXXBaseListFactory.getEmptyList(); 191 } else { // const PointerToMemberData * 192 const PointerToMemberData *PTMD = 193 PTMDT.get<const PointerToMemberData *>(); 194 DD = PTMD->getDeclaratorDecl(); 195 196 PathList = PTMD->getCXXBaseList(); 197 } 198 199 for (const auto &I : llvm::reverse(PathRange)) 200 PathList = prependCXXBase(I, PathList); 201 return getPointerToMemberData(DD, PathList); 202} 203 204const llvm::APSInt* 205BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, 206 const llvm::APSInt& V1, const llvm::APSInt& V2) { 207 switch (Op) { 208 default: 209 llvm_unreachable("Invalid Opcode."); 210 211 case BO_Mul: 212 return &getValue( V1 * V2 ); 213 214 case BO_Div: 215 if (V2 == 0) // Avoid division by zero 216 return nullptr; 217 return &getValue( V1 / V2 ); 218 219 case BO_Rem: 220 if (V2 == 0) // Avoid division by zero 221 return nullptr; 222 return &getValue( V1 % V2 ); 223 224 case BO_Add: 225 return &getValue( V1 + V2 ); 226 227 case BO_Sub: 228 return &getValue( V1 - V2 ); 229 230 case BO_Shl: { 231 // FIXME: This logic should probably go higher up, where we can 232 // test these conditions symbolically. 233 234 if (V2.isSigned() && V2.isNegative()) 235 return nullptr; 236 237 uint64_t Amt = V2.getZExtValue(); 238 239 if (Amt >= V1.getBitWidth()) 240 return nullptr; 241 242 if (!Ctx.getLangOpts().CPlusPlus2a) { 243 if (V1.isSigned() && V1.isNegative()) 244 return nullptr; 245 246 if (V1.isSigned() && Amt > V1.countLeadingZeros()) 247 return nullptr; 248 } 249 250 return &getValue( V1.operator<<( (unsigned) Amt )); 251 } 252 253 case BO_Shr: { 254 // FIXME: This logic should probably go higher up, where we can 255 // test these conditions symbolically. 256 257 if (V2.isSigned() && V2.isNegative()) 258 return nullptr; 259 260 uint64_t Amt = V2.getZExtValue(); 261 262 if (Amt >= V1.getBitWidth()) 263 return nullptr; 264 265 return &getValue( V1.operator>>( (unsigned) Amt )); 266 } 267 268 case BO_LT: 269 return &getTruthValue( V1 < V2 ); 270 271 case BO_GT: 272 return &getTruthValue( V1 > V2 ); 273 274 case BO_LE: 275 return &getTruthValue( V1 <= V2 ); 276 277 case BO_GE: 278 return &getTruthValue( V1 >= V2 ); 279 280 case BO_EQ: 281 return &getTruthValue( V1 == V2 ); 282 283 case BO_NE: 284 return &getTruthValue( V1 != V2 ); 285 286 // Note: LAnd, LOr, Comma are handled specially by higher-level logic. 287 288 case BO_And: 289 return &getValue( V1 & V2 ); 290 291 case BO_Or: 292 return &getValue( V1 | V2 ); 293 294 case BO_Xor: 295 return &getValue( V1 ^ V2 ); 296 } 297} 298 299const std::pair<SVal, uintptr_t>& 300BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { 301 // Lazily create the folding set. 302 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy(); 303 304 llvm::FoldingSetNodeID ID; 305 void *InsertPos; 306 V.Profile(ID); 307 ID.AddPointer((void*) Data); 308 309 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); 310 311 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>; 312 313 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 314 315 if (!P) { 316 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 317 new (P) FoldNodeTy(std::make_pair(V, Data)); 318 Map.InsertNode(P, InsertPos); 319 } 320 321 return P->getValue(); 322} 323 324const std::pair<SVal, SVal>& 325BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { 326 // Lazily create the folding set. 327 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); 328 329 llvm::FoldingSetNodeID ID; 330 void *InsertPos; 331 V1.Profile(ID); 332 V2.Profile(ID); 333 334 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); 335 336 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>; 337 338 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); 339 340 if (!P) { 341 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); 342 new (P) FoldNodeTy(std::make_pair(V1, V2)); 343 Map.InsertNode(P, InsertPos); 344 } 345 346 return P->getValue(); 347} 348 349const SVal* BasicValueFactory::getPersistentSVal(SVal X) { 350 return &getPersistentSValWithData(X, 0).first; 351} 352