1 //==- BasicValueFactory.h - Basic values for Path Sens analysis --*- C++ -*-==// 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 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H 16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H 17 18 #include "clang/AST/ASTContext.h" 19 #include "clang/AST/Expr.h" 20 #include "clang/AST/Type.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 22 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 25 #include "llvm/ADT/APSInt.h" 26 #include "llvm/ADT/FoldingSet.h" 27 #include "llvm/ADT/ImmutableList.h" 28 #include "llvm/ADT/iterator_range.h" 29 #include "llvm/Support/Allocator.h" 30 #include <cassert> 31 #include <cstdint> 32 #include <utility> 33 34 namespace clang { 35 36 class CXXBaseSpecifier; 37 38 namespace ento { 39 40 class CompoundValData : public llvm::FoldingSetNode { 41 QualType T; 42 llvm::ImmutableList<SVal> L; 43 44 public: 45 CompoundValData(QualType t, llvm::ImmutableList<SVal> l) : T(t), L(l) { 46 assert(NonLoc::isCompoundType(t)); 47 } 48 49 using iterator = llvm::ImmutableList<SVal>::iterator; 50 51 iterator begin() const { return L.begin(); } 52 iterator end() const { return L.end(); } 53 54 QualType getType() const { return T; } 55 56 static void Profile(llvm::FoldingSetNodeID& ID, QualType T, 57 llvm::ImmutableList<SVal> L); 58 59 void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); } 60 }; 61 62 class LazyCompoundValData : public llvm::FoldingSetNode { 63 StoreRef store; 64 const TypedValueRegion *region; 65 66 public: 67 LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r) 68 : store(st), region(r) { 69 assert(r); 70 assert(NonLoc::isCompoundType(r->getValueType())); 71 } 72 73 /// It might return null. 74 const void *getStore() const { return store.getStore(); } 75 76 LLVM_ATTRIBUTE_RETURNS_NONNULL 77 const TypedValueRegion *getRegion() const { return region; } 78 79 static void Profile(llvm::FoldingSetNodeID& ID, 80 const StoreRef &store, 81 const TypedValueRegion *region); 82 83 void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); } 84 }; 85 86 class PointerToMemberData : public llvm::FoldingSetNode { 87 const NamedDecl *D; 88 llvm::ImmutableList<const CXXBaseSpecifier *> L; 89 90 public: 91 PointerToMemberData(const NamedDecl *D, 92 llvm::ImmutableList<const CXXBaseSpecifier *> L) 93 : D(D), L(L) {} 94 95 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator; 96 97 iterator begin() const { return L.begin(); } 98 iterator end() const { return L.end(); } 99 100 static void Profile(llvm::FoldingSetNodeID &ID, const NamedDecl *D, 101 llvm::ImmutableList<const CXXBaseSpecifier *> L); 102 103 void Profile(llvm::FoldingSetNodeID &ID) { Profile(ID, D, L); } 104 105 /// It might return null. 106 const NamedDecl *getDeclaratorDecl() const { return D; } 107 108 llvm::ImmutableList<const CXXBaseSpecifier *> getCXXBaseList() const { 109 return L; 110 } 111 }; 112 113 class BasicValueFactory { 114 using APSIntSetTy = 115 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt>>; 116 117 ASTContext &Ctx; 118 llvm::BumpPtrAllocator& BPAlloc; 119 120 APSIntSetTy APSIntSet; 121 void *PersistentSVals = nullptr; 122 void *PersistentSValPairs = nullptr; 123 124 llvm::ImmutableList<SVal>::Factory SValListFactory; 125 llvm::ImmutableList<const CXXBaseSpecifier *>::Factory CXXBaseListFactory; 126 llvm::FoldingSet<CompoundValData> CompoundValDataSet; 127 llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet; 128 llvm::FoldingSet<PointerToMemberData> PointerToMemberDataSet; 129 130 // This is private because external clients should use the factory 131 // method that takes a QualType. 132 const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned); 133 134 public: 135 BasicValueFactory(ASTContext &ctx, llvm::BumpPtrAllocator &Alloc) 136 : Ctx(ctx), BPAlloc(Alloc), SValListFactory(Alloc), 137 CXXBaseListFactory(Alloc) {} 138 139 ~BasicValueFactory(); 140 141 ASTContext &getContext() const { return Ctx; } 142 143 const llvm::APSInt& getValue(const llvm::APSInt& X); 144 const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned); 145 const llvm::APSInt& getValue(uint64_t X, QualType T); 146 147 /// Returns the type of the APSInt used to store values of the given QualType. 148 APSIntType getAPSIntType(QualType T) const { 149 // For the purposes of the analysis and constraints, we treat atomics 150 // as their underlying types. 151 if (const AtomicType *AT = T->getAs<AtomicType>()) { 152 T = AT->getValueType(); 153 } 154 155 assert(T->isIntegralOrEnumerationType() || Loc::isLocType(T)); 156 return APSIntType(Ctx.getIntWidth(T), 157 !T->isSignedIntegerOrEnumerationType()); 158 } 159 160 /// Convert - Create a new persistent APSInt with the same value as 'From' 161 /// but with the bitwidth and signedness of 'To'. 162 const llvm::APSInt &Convert(const llvm::APSInt& To, 163 const llvm::APSInt& From) { 164 APSIntType TargetType(To); 165 if (TargetType == APSIntType(From)) 166 return From; 167 168 return getValue(TargetType.convert(From)); 169 } 170 171 const llvm::APSInt &Convert(QualType T, const llvm::APSInt &From) { 172 APSIntType TargetType = getAPSIntType(T); 173 return Convert(TargetType, From); 174 } 175 176 const llvm::APSInt &Convert(APSIntType TargetType, const llvm::APSInt &From) { 177 if (TargetType == APSIntType(From)) 178 return From; 179 180 return getValue(TargetType.convert(From)); 181 } 182 183 const llvm::APSInt &getIntValue(uint64_t X, bool isUnsigned) { 184 QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy; 185 return getValue(X, T); 186 } 187 188 const llvm::APSInt &getMaxValue(const llvm::APSInt &v) { 189 return getValue(APSIntType(v).getMaxValue()); 190 } 191 192 const llvm::APSInt &getMinValue(const llvm::APSInt &v) { 193 return getValue(APSIntType(v).getMinValue()); 194 } 195 196 const llvm::APSInt &getMaxValue(QualType T) { 197 return getMaxValue(getAPSIntType(T)); 198 } 199 200 const llvm::APSInt &getMinValue(QualType T) { 201 return getMinValue(getAPSIntType(T)); 202 } 203 204 const llvm::APSInt &getMaxValue(APSIntType T) { 205 return getValue(T.getMaxValue()); 206 } 207 208 const llvm::APSInt &getMinValue(APSIntType T) { 209 return getValue(T.getMinValue()); 210 } 211 212 const llvm::APSInt &Add1(const llvm::APSInt &V) { 213 llvm::APSInt X = V; 214 ++X; 215 return getValue(X); 216 } 217 218 const llvm::APSInt &Sub1(const llvm::APSInt &V) { 219 llvm::APSInt X = V; 220 --X; 221 return getValue(X); 222 } 223 224 const llvm::APSInt &getZeroWithTypeSize(QualType T) { 225 assert(T->isScalarType()); 226 return getValue(0, Ctx.getTypeSize(T), true); 227 } 228 229 const llvm::APSInt &getTruthValue(bool b, QualType T) { 230 return getValue(b ? 1 : 0, Ctx.getIntWidth(T), 231 T->isUnsignedIntegerOrEnumerationType()); 232 } 233 234 const llvm::APSInt &getTruthValue(bool b) { 235 return getTruthValue(b, Ctx.getLogicalOperationType()); 236 } 237 238 const CompoundValData *getCompoundValData(QualType T, 239 llvm::ImmutableList<SVal> Vals); 240 241 const LazyCompoundValData *getLazyCompoundValData(const StoreRef &store, 242 const TypedValueRegion *region); 243 244 const PointerToMemberData * 245 getPointerToMemberData(const NamedDecl *ND, 246 llvm::ImmutableList<const CXXBaseSpecifier *> L); 247 248 llvm::ImmutableList<SVal> getEmptySValList() { 249 return SValListFactory.getEmptyList(); 250 } 251 252 llvm::ImmutableList<SVal> prependSVal(SVal X, llvm::ImmutableList<SVal> L) { 253 return SValListFactory.add(X, L); 254 } 255 256 llvm::ImmutableList<const CXXBaseSpecifier *> getEmptyCXXBaseList() { 257 return CXXBaseListFactory.getEmptyList(); 258 } 259 260 llvm::ImmutableList<const CXXBaseSpecifier *> prependCXXBase( 261 const CXXBaseSpecifier *CBS, 262 llvm::ImmutableList<const CXXBaseSpecifier *> L) { 263 return CXXBaseListFactory.add(CBS, L); 264 } 265 266 const PointerToMemberData * 267 accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange, 268 const nonloc::PointerToMember &PTM, const clang::CastKind &kind); 269 270 const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op, 271 const llvm::APSInt& V1, 272 const llvm::APSInt& V2); 273 274 const std::pair<SVal, uintptr_t>& 275 getPersistentSValWithData(const SVal& V, uintptr_t Data); 276 277 const std::pair<SVal, SVal>& 278 getPersistentSValPair(const SVal& V1, const SVal& V2); 279 280 const SVal* getPersistentSVal(SVal X); 281 }; 282 283 } // namespace ento 284 285 } // namespace clang 286 287 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H 288