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