1240f1f00dda1d481276ea872fe8f8851581a7e6bTed Kremenek//=== BasicValueFactory.h - Basic values for Path Sens analysis --*- C++ -*---// 2d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 3d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// The LLVM Compiler Infrastructure 4d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 5d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// This file is distributed under the University of Illinois Open Source 6d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// License. See LICENSE.TXT for details. 7d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 8d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//===----------------------------------------------------------------------===// 9d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 10240f1f00dda1d481276ea872fe8f8851581a7e6bTed Kremenek// This file defines BasicValueFactory, a class that manages the lifetime 11d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// of APSInt objects and symbolic constraints used by ExprEngine 12240f1f00dda1d481276ea872fe8f8851581a7e6bTed Kremenek// and related classes. 13d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek// 14d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek//===----------------------------------------------------------------------===// 15d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 165a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_BASICVALUEFACTORY_H 175a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#define LLVM_CLANG_GR_BASICVALUEFACTORY_H 18d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 1955fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/AST/ASTContext.h" 20d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 219b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 2255fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 23d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 24d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremeneknamespace clang { 259ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 265a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 276764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xuclass CompoundValData : public llvm::FoldingSetNode { 286764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu QualType T; 29632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::ImmutableList<SVal> L; 306764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu 316764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xupublic: 321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump CompoundValData(QualType t, llvm::ImmutableList<SVal> l) 33632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek : T(t), L(l) {} 346764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu 35a6fac4e446eb30ed270eff9d4084d5db5e657fcfTed Kremenek typedef llvm::ImmutableList<SVal>::iterator iterator; 36a6fac4e446eb30ed270eff9d4084d5db5e657fcfTed Kremenek iterator begin() const { return L.begin(); } 371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump iterator end() const { return L.end(); } 381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 39632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek static void Profile(llvm::FoldingSetNodeID& ID, QualType T, 40632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::ImmutableList<SVal> L); 416764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu 42632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); } 436764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu}; 446764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu 45a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenekclass LazyCompoundValData : public llvm::FoldingSetNode { 46cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek StoreRef store; 479697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *region; 48a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenekpublic: 499697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r) 50bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu : store(st), region(r) {} 511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 52cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek const void *getStore() const { return store.getStore(); } 539697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *getRegion() const { return region; } 541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 55cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek static void Profile(llvm::FoldingSetNodeID& ID, 56cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek const StoreRef &store, 579697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *region); 581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 59bfcaf8048d1673320de60a22ca9c297d7484b2a8Zhongxing Xu void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); } 60a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek}; 611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 62240f1f00dda1d481276ea872fe8f8851581a7e6bTed Kremenekclass BasicValueFactory { 63d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> > 64d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek APSIntSetTy; 65d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 669c378f705405d37f49795d5e915989de774fe11fTed Kremenek ASTContext &Ctx; 67d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek llvm::BumpPtrAllocator& BPAlloc; 68d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 69d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek APSIntSetTy APSIntSet; 709c378f705405d37f49795d5e915989de774fe11fTed Kremenek void * PersistentSVals; 719c378f705405d37f49795d5e915989de774fe11fTed Kremenek void * PersistentSValPairs; 72d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 73632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::ImmutableList<SVal>::Factory SValListFactory; 74632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::FoldingSet<CompoundValData> CompoundValDataSet; 75a5e81f1240bcc5b9b0721fc6275075ad7cadaf5eTed Kremenek llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet; 766764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu 7791ab900a939e95d965e18299b66928fdbe2aa38dJordan Rose // This is private because external clients should use the factory 7891ab900a939e95d965e18299b66928fdbe2aa38dJordan Rose // method that takes a QualType. 7991ab900a939e95d965e18299b66928fdbe2aa38dJordan Rose const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned); 8091ab900a939e95d965e18299b66928fdbe2aa38dJordan Rose 81d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenekpublic: 829c378f705405d37f49795d5e915989de774fe11fTed Kremenek BasicValueFactory(ASTContext &ctx, llvm::BumpPtrAllocator& Alloc) 83632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek : Ctx(ctx), BPAlloc(Alloc), PersistentSVals(0), PersistentSValPairs(0), 84632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek SValListFactory(Alloc) {} 85d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 86240f1f00dda1d481276ea872fe8f8851581a7e6bTed Kremenek ~BasicValueFactory(); 87d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 889c378f705405d37f49795d5e915989de774fe11fTed Kremenek ASTContext &getContext() const { return Ctx; } 89d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 90d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek const llvm::APSInt& getValue(const llvm::APSInt& X); 91e8a964bdb46349e4fa3433c8e5104d2a0f7f5c65Zhongxing Xu const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned); 9298be4943e8dc4f3905629a7102668960873cf863Chris Lattner const llvm::APSInt& getValue(uint64_t X, QualType T); 931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 94d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose /// Returns the type of the APSInt used to store values of the given QualType. 95d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType getAPSIntType(QualType T) const { 96d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose assert(T->isIntegerType() || Loc::isLocType(T)); 97d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return APSIntType(Ctx.getTypeSize(T), 98d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose !T->isSignedIntegerOrEnumerationType()); 99d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose } 100d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose 101610e81d6b7248ce4be4be2252b03a5d4052c9835Ted Kremenek /// Convert - Create a new persistent APSInt with the same value as 'From' 10236c233837a37e295ecef133739d2b6429c72b960Ted Kremenek /// but with the bitwidth and signedness of 'To'. 10380417471b01ab2726cd04773b2ab700ce564073cTed Kremenek const llvm::APSInt &Convert(const llvm::APSInt& To, 104610e81d6b7248ce4be4be2252b03a5d4052c9835Ted Kremenek const llvm::APSInt& From) { 105d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType TargetType(To); 106d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose if (TargetType == APSIntType(From)) 107672e408f14b528fe5e41c5dc99e95e671149a1e9Ted Kremenek return From; 1081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 109d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return getValue(TargetType.convert(From)); 11080417471b01ab2726cd04773b2ab700ce564073cTed Kremenek } 11180417471b01ab2726cd04773b2ab700ce564073cTed Kremenek 11280417471b01ab2726cd04773b2ab700ce564073cTed Kremenek const llvm::APSInt &Convert(QualType T, const llvm::APSInt &From) { 113d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType TargetType = getAPSIntType(T); 114d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose if (TargetType == APSIntType(From)) 11580417471b01ab2726cd04773b2ab700ce564073cTed Kremenek return From; 11680417471b01ab2726cd04773b2ab700ce564073cTed Kremenek 117d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return getValue(TargetType.convert(From)); 118672e408f14b528fe5e41c5dc99e95e671149a1e9Ted Kremenek } 119d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 12014553abd17d303b0b310b3ab1523eb0d30d8121cTed Kremenek const llvm::APSInt& getIntValue(uint64_t X, bool isUnsigned) { 12114553abd17d303b0b310b3ab1523eb0d30d8121cTed Kremenek QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy; 12214553abd17d303b0b310b3ab1523eb0d30d8121cTed Kremenek return getValue(X, T); 12314553abd17d303b0b310b3ab1523eb0d30d8121cTed Kremenek } 1241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1250d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek inline const llvm::APSInt& getMaxValue(const llvm::APSInt &v) { 126d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return getValue(APSIntType(v).getMaxValue()); 1270d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek } 1281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1290d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek inline const llvm::APSInt& getMinValue(const llvm::APSInt &v) { 130d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return getValue(APSIntType(v).getMinValue()); 1310d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek } 13214553abd17d303b0b310b3ab1523eb0d30d8121cTed Kremenek 1330d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek inline const llvm::APSInt& getMaxValue(QualType T) { 134d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return getValue(getAPSIntType(T).getMaxValue()); 1350d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek } 1361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1370d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek inline const llvm::APSInt& getMinValue(QualType T) { 138d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose return getValue(getAPSIntType(T).getMinValue()); 1390d3aeae8bf09fb9cdc536cfa5fefa983bd900dfcTed Kremenek } 1401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1416175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek inline const llvm::APSInt& Add1(const llvm::APSInt& V) { 1426175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek llvm::APSInt X = V; 1436175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek ++X; 1446175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek return getValue(X); 1456175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek } 1461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1476175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek inline const llvm::APSInt& Sub1(const llvm::APSInt& V) { 1486175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek llvm::APSInt X = V; 1496175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek --X; 1506175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek return getValue(X); 1516175dc676c515a74e5f41afb4ac2b44cc2367a24Ted Kremenek } 1521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1538bb87e8de5fc8e4c91e78468b65a66b5b2b82d71Zhongxing Xu inline const llvm::APSInt& getZeroWithPtrWidth(bool isUnsigned = true) { 1548bb87e8de5fc8e4c91e78468b65a66b5b2b82d71Zhongxing Xu return getValue(0, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); 155d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek } 156d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 157a52ad4e1f423bed2e9e0dcb12661268091d20a54Zhongxing Xu inline const llvm::APSInt &getIntWithPtrWidth(uint64_t X, bool isUnsigned) { 158a52ad4e1f423bed2e9e0dcb12661268091d20a54Zhongxing Xu return getValue(X, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); 159a52ad4e1f423bed2e9e0dcb12661268091d20a54Zhongxing Xu } 160a52ad4e1f423bed2e9e0dcb12661268091d20a54Zhongxing Xu 1611670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek inline const llvm::APSInt& getTruthValue(bool b, QualType T) { 1621670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek return getValue(b ? 1 : 0, Ctx.getTypeSize(T), false); 1631670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek } 1641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 165d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek inline const llvm::APSInt& getTruthValue(bool b) { 166f4699d14b03d805ad9ccaa6288836ac2a8612925Argyrios Kyrtzidis return getTruthValue(b, Ctx.getLogicalOperationType()); 167d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek } 1681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const CompoundValData *getCompoundValData(QualType T, 170632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::ImmutableList<SVal> Vals); 1711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 172cf333339615da345c2ed6e873d94a501810d9f3fTed Kremenek const LazyCompoundValData *getLazyCompoundValData(const StoreRef &store, 1739697934650354bed2e509d8e7e44f21a1fb00f76Ted Kremenek const TypedValueRegion *region); 1741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 175632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::ImmutableList<SVal> getEmptySValList() { 1763baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek return SValListFactory.getEmptyList(); 177632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek } 1781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 179632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek llvm::ImmutableList<SVal> consVals(SVal X, llvm::ImmutableList<SVal> L) { 1803baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek return SValListFactory.add(X, L); 181632e8b84976f683b365eddfacd04ea5d6f4d8cdfTed Kremenek } 1826764b72f6f26b5c03471b9e379a44d379d2d4a9eZhongxing Xu 1839c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed Kremenek const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op, 184d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek const llvm::APSInt& V1, 185d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek const llvm::APSInt& V2); 1861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1871c96b24285d05c0eac455ae96d7c9ff43d42bc96Zhongxing Xu const std::pair<SVal, uintptr_t>& 1881c96b24285d05c0eac455ae96d7c9ff43d42bc96Zhongxing Xu getPersistentSValWithData(const SVal& V, uintptr_t Data); 1891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1901c96b24285d05c0eac455ae96d7c9ff43d42bc96Zhongxing Xu const std::pair<SVal, SVal>& 1911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump getPersistentSValPair(const SVal& V1, const SVal& V2); 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1931c96b24285d05c0eac455ae96d7c9ff43d42bc96Zhongxing Xu const SVal* getPersistentSVal(SVal X); 194d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek}; 195d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 1965a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 1975a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 198d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek} // end clang namespace 199d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek 200d70d0b05e5143be9e952eceb5aad7914b2ecab97Ted Kremenek#endif 201