SimpleSValBuilder.cpp revision 8958efacf8d52918cfe624116338bec62312582d
1710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov// SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- C++ -*- 26091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// 36091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// The LLVM Compiler Infrastructure 46091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 76091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// 86091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer//===----------------------------------------------------------------------===// 927107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// 1027107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// This file defines SimpleSValBuilder, a basic implementation of SValBuilder. 1127107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// 1227107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling//===----------------------------------------------------------------------===// 1327107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling 146091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 156091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 16674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak 186091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencerusing namespace clang; 19d509d0b532ec2358b3f341d4a4cd1411cb8b5db2Chris Lattnerusing namespace ento; 203467e30edf63b6d8a8d446186674ba9e4b7885a9Bill Wendling 21c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramernamespace { 223f213e7b3a6829a154d4e8ceb7d8689b389bd5dcBenjamin Kramerclass SimpleSValBuilder : public SValBuilder { 2322bd64173981bf1251c4b3bfc684207340534ba3Bill Wendlingprotected: 24ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling virtual SVal dispatchCast(SVal val, QualType castTy); 2558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy); 266091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer virtual SVal evalCastFromLoc(Loc val, QualType castTy); 276091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer 28d426a642a23a234547cbc7061f5bfec157673249Bill Wendlingpublic: 29702cc91aa1bd41540e8674921ae7ac89a4ff061fBill Wendling SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, 30f6670729aabc1fab85238d2b306a1c1767a807bbBill Wendling ProgramStateManager &stateMgr) 31817abdd8b055059e5930a15704b9f52da4236456Bill Wendling : SValBuilder(alloc, context, stateMgr) {} 32817abdd8b055059e5930a15704b9f52da4236456Bill Wendling virtual ~SimpleSValBuilder() {} 336dc3781d44e56f0addf28b06232a50f3f9e6b1afBill Wendling 34c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer virtual SVal evalMinus(NonLoc val); 352c79ecbd704c656178ffa43d5a58ebe3ca188b40Bill Wendling virtual SVal evalComplement(NonLoc val); 36ad9a9e15595bc9d5ba1ed752caf8572957f77a3dDuncan Sands virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, 37ad9a9e15595bc9d5ba1ed752caf8572957f77a3dDuncan Sands NonLoc lhs, NonLoc rhs, QualType resultTy); 381d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, 3927107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling Loc lhs, Loc rhs, QualType resultTy); 4027107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, 411d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling Loc lhs, NonLoc rhs, QualType resultTy); 421d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling 431d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling /// getKnownValue - evaluates a given SVal. If the SVal has only one possible 44034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling /// (integer) value, that value is returned. Otherwise, returns NULL. 456765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V); 461d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling 4773dee180c836270644dfa7d90f9c5ba877567999Bill Wendling SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op, 48f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling const llvm::APSInt &RHS, QualType resultTy); 4973dee180c836270644dfa7d90f9c5ba877567999Bill Wendling}; 5073dee180c836270644dfa7d90f9c5ba877567999Bill Wendling} // end anonymous namespace 5173dee180c836270644dfa7d90f9c5ba877567999Bill Wendling 52f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill WendlingSValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, 5373dee180c836270644dfa7d90f9c5ba877567999Bill Wendling ASTContext &context, 5411d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling ProgramStateManager &stateMgr) { 5511d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling return new SimpleSValBuilder(alloc, context, stateMgr); 56f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling} 5711d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling 5811d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling//===----------------------------------------------------------------------===// 5911d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling// Transfer function for Casts. 6011d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling//===----------------------------------------------------------------------===// 6111d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling 6211d00420e42ba88c3b48cab997965a7be79315e2Bill WendlingSVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) { 63629fb82419d9bfff6ae475363bcce66192dfcc8eBill Wendling assert(Val.getAs<Loc>() || Val.getAs<NonLoc>()); 645a0eeb5a9d727940b1dbe8dff6e9aa292ada0f6aBill Wendling return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy) 65480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy); 66480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling} 676765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling 68f6670729aabc1fab85238d2b306a1c1767a807bbBill WendlingSVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) { 69480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 702253a2f52f3c46ae75cd05f5885acb987bd1d6b6Michael Gottesman bool isLocType = Loc::isLocType(castTy); 712253a2f52f3c46ae75cd05f5885acb987bd1d6b6Michael Gottesman 72480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (Optional<nonloc::LocAsInteger> LI = val.getAs<nonloc::LocAsInteger>()) { 7377226a03dca98e6237c1068f2652fe41bea7b687Diego Novillo if (isLocType) 74480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return LI->getLoc(); 75480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 769a419f656e278b96e9dfe739cd63c7bff9a4e1fdQuentin Colombet // FIXME: Correctly support promotions/truncations. 77480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling unsigned castSize = Context.getTypeSize(castTy); 78480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (castSize == LI->getNumBits()) 79480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return val; 80143d46476cdcf5b88b9ee18ebd799e5820a2db0eBill Wendling return makeLocAsInteger(LI->getLoc(), castSize); 81480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling } 8267ae13575900e8efd056672987249fd0adbf5e73James Molloy 83480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (const SymExpr *se = val.getAsSymbolicExpression()) { 84480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling QualType T = Context.getCanonicalType(se->getType()); 85480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // If types are the same or both are integers, ignore the cast. 863a106e60366a51b4594ec303ff8dbbc58913227fBill Wendling // FIXME: Remove this hack when we support symbolic truncation/extension. 87480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // HACK: If both castTy and T are integers, ignore the cast. This is 88480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // not a permanent solution. Eventually we want to precisely handle 89480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // extension/truncation of symbolic integers. This prevents us from losing 90480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // precision when we assign 'x = y' and 'y' is symbolic and x and y are 91480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // different integer types. 92480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (haveSameType(T, castTy)) 93456ca048af35163b9f52187e92a23ee0a9f059e8Stephen Lin return val; 94480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 95480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (!isLocType) 96480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return makeNonLoc(se, T, castTy); 976765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling return UnknownVal(); 986765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling } 99f6670729aabc1fab85238d2b306a1c1767a807bbBill Wendling 100480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling // If value is a non integer constant, produce unknown. 101480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (!val.getAs<nonloc::ConcreteInt>()) 102114baee1fa017daefad2339c77b45b9ca3d79a41Bill Wendling return UnknownVal(); 103480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 1048eec41fc778e99d42172a7f6de76faa43a6d8847Kostya Serebryany // Handle casts to a boolean type. 1058eec41fc778e99d42172a7f6de76faa43a6d8847Kostya Serebryany if (castTy->isBooleanType()) { 1068eec41fc778e99d42172a7f6de76faa43a6d8847Kostya Serebryany bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue(); 107480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return makeTruthVal(b, castTy); 1080319888773b36dd61d7d2283cb9a26cac1e5abe8Bill Wendling } 1090319888773b36dd61d7d2283cb9a26cac1e5abe8Bill Wendling 110886a7663c72cb04eaee58cb6997c394f5096a8b9Benjamin Kramer // Only handle casts from integers to integers - if val is an integer constant 1116765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling // being cast to a non integer type, produce unknown. 1126765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling if (!isLocType && !castTy->isIntegerType()) 11327107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling return UnknownVal(); 11427107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling 115d426a642a23a234547cbc7061f5bfec157673249Bill Wendling llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue(); 11627107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling BasicVals.getAPSIntType(castTy).apply(i); 1172c79ecbd704c656178ffa43d5a58ebe3ca188b40Bill Wendling 118c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling if (isLocType) 119c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling return makeIntLocVal(i); 120c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling else 121c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling return makeIntVal(i); 122c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling} 1238c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1248c74ecfbddabe89e150abff4fdff0a27108874b9Bill WendlingSVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) { 1258c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1262c79ecbd704c656178ffa43d5a58ebe3ca188b40Bill Wendling // Casts from pointers -> pointers, just return the lval. 127c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling // 128c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling // Casts from pointers -> references, just return the lval. These 129c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling // can be introduced by the frontend for corner cases, e.g 130c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling // casting from va_list* to __builtin_va_list&. 131c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling // 132c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling if (Loc::isLocType(castTy) || castTy->isReferenceType()) 133c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling return val; 134c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 135c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling // FIXME: Handle transparent unions where a value can be "transparently" 1368c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling // lifted into a union type. 1378c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling if (castTy->isUnionType()) 1388c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return UnknownVal(); 1398c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1408c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling if (castTy->isIntegerType()) { 1418c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling unsigned BitWidth = Context.getTypeSize(castTy); 1428c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1438c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling if (!val.getAs<loc::ConcreteInt>()) 1448c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return makeLocAsInteger(val, BitWidth); 1458c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 146eddab1550ee10cce3bb26a26e88529cb19451aa3NAKAMURA Takumi llvm::APSInt i = val.castAs<loc::ConcreteInt>().getValue(); 147eddab1550ee10cce3bb26a26e88529cb19451aa3NAKAMURA Takumi BasicVals.getAPSIntType(castTy).apply(i); 148eddab1550ee10cce3bb26a26e88529cb19451aa3NAKAMURA Takumi return makeIntVal(i); 14964754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling } 15064754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling 15164754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling // All other cases: return 'UnknownVal'. This includes casting pointers 1528c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling // to floats, which is probably badness it itself, but this is a good 1538c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling // intermediate solution until we do something better. 1548c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return UnknownVal(); 1556dc3781d44e56f0addf28b06232a50f3f9e6b1afBill Wendling} 1568c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1578c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling//===----------------------------------------------------------------------===// 1588c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling// Transfer function for unary operators. 1598c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling//===----------------------------------------------------------------------===// 1608c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1618c74ecfbddabe89e150abff4fdff0a27108874b9Bill WendlingSVal SimpleSValBuilder::evalMinus(NonLoc val) { 1628c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling switch (val.getSubKind()) { 1638c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling case nonloc::ConcreteIntKind: 1648c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return val.castAs<nonloc::ConcreteInt>().evalMinus(*this); 1658c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling default: 1668c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return UnknownVal(); 1676dc3781d44e56f0addf28b06232a50f3f9e6b1afBill Wendling } 1681d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling} 169ef99fe8efaa6cb74c66e570a6ef467debca92911Bill Wendling 170e66f3d3ba0ea9f82f65a29c47fc37e997cbf0aceBill WendlingSVal SimpleSValBuilder::evalComplement(NonLoc X) { 171ef99fe8efaa6cb74c66e570a6ef467debca92911Bill Wendling switch (X.getSubKind()) { 1721d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling case nonloc::ConcreteIntKind: 173943c29135e03e55f9a5dab393786171a4a536482Bill Wendling return X.castAs<nonloc::ConcreteInt>().evalComplement(*this); 174e66f3d3ba0ea9f82f65a29c47fc37e997cbf0aceBill Wendling default: 17530b483c94001927b3593ed200e823104bab51660Bill Wendling return UnknownVal(); 176c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling } 177c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling} 178b29ce26ea60f7516c853318ffbfc107fde9ad897Bill Wendling 179c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling//===----------------------------------------------------------------------===// 1808c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling// Transfer function for binary operators. 1812d5be6c313c0f9e23e56620fa8f8ae8d9b539bf0Bill Wendling//===----------------------------------------------------------------------===// 1822d5be6c313c0f9e23e56620fa8f8ae8d9b539bf0Bill Wendling 1832d5be6c313c0f9e23e56620fa8f8ae8d9b539bf0Bill Wendlingstatic BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) { 184c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling switch (op) { 1853467e30edf63b6d8a8d446186674ba9e4b7885a9Bill Wendling default: 1863467e30edf63b6d8a8d446186674ba9e4b7885a9Bill Wendling llvm_unreachable("Invalid opcode."); 187bb08593980b16fbd9758da6ca4fa9c7964f2f926Bill Wendling case BO_LT: return BO_GE; 188bb08593980b16fbd9758da6ca4fa9c7964f2f926Bill Wendling case BO_GT: return BO_LE; 189bb08593980b16fbd9758da6ca4fa9c7964f2f926Bill Wendling case BO_LE: return BO_GT; 190827cde1c8319e51463007078a7ce3660ebc93036Duncan Sands case BO_GE: return BO_LT; 191827cde1c8319e51463007078a7ce3660ebc93036Duncan Sands case BO_EQ: return BO_NE; 192e66f3d3ba0ea9f82f65a29c47fc37e997cbf0aceBill Wendling case BO_NE: return BO_EQ; 19327107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling } 194c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling} 195c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling 196c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendlingstatic BinaryOperator::Opcode ReverseComparison(BinaryOperator::Opcode op) { 197c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling switch (op) { 198c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling default: 199c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling llvm_unreachable("Invalid opcode."); 20099faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling case BO_LT: return BO_GT; 20107aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case BO_GT: return BO_LT; 20207aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case BO_LE: return BO_GE; 20307aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case BO_GE: return BO_LE; 20407aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case BO_EQ: 20507aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case BO_NE: 20607aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling return op; 207a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 2087d38c109aab8654e63e9071c7d948661f6b58433Bill Wendling} 20916274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 210a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill WendlingSVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS, 21173dee180c836270644dfa7d90f9c5ba877567999Bill Wendling BinaryOperator::Opcode op, 2120976e00fd1cbf4128daeb72efd8957d00383fda9Bill Wendling const llvm::APSInt &RHS, 213ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling QualType resultTy) { 2140976e00fd1cbf4128daeb72efd8957d00383fda9Bill Wendling bool isIdempotent = false; 21573dee180c836270644dfa7d90f9c5ba877567999Bill Wendling 2168a6a7bb6a601061031cddd77129532a3b467300bBill Wendling // Check for a few special cases with known reductions first. 2170976e00fd1cbf4128daeb72efd8957d00383fda9Bill Wendling switch (op) { 21887e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling default: 21987e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling // We can't reduce this case; just treat it normally. 2206bdbf061c353295669b6bfc271b948158602d1bcBill Wendling break; 22187e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling case BO_Mul: 2226bdbf061c353295669b6bfc271b948158602d1bcBill Wendling // a*0 and a*1 22387e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling if (RHS == 0) 22487e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling return makeIntVal(0, resultTy); 22587e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling else if (RHS == 1) 2266bdbf061c353295669b6bfc271b948158602d1bcBill Wendling isIdempotent = true; 22787e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling break; 22887e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling case BO_Div: 2297d38c109aab8654e63e9071c7d948661f6b58433Bill Wendling // a/0 and a/1 230ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling if (RHS == 0) 23158d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner // This is also handled elsewhere. 232ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling return UndefinedVal(); 233710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov else if (RHS == 1) 23458d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner isIdempotent = true; 235c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling break; 23658d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner case BO_Rem: 237710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov // a%0 and a%1 23818e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling if (RHS == 0) 2398e47daf2858e980210f3e1f007036b24da342c29Bill Wendling // This is also handled elsewhere. 2408a6a7bb6a601061031cddd77129532a3b467300bBill Wendling return UndefinedVal(); 24132a57958226e369f964a034da2ce7083a1a34297Bill Wendling else if (RHS == 1) 2428a6a7bb6a601061031cddd77129532a3b467300bBill Wendling return makeIntVal(0, resultTy); 24358d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner break; 244defaca00b8087d452df2b783250a48a32658a910Bill Wendling case BO_Add: 245defaca00b8087d452df2b783250a48a32658a910Bill Wendling case BO_Sub: 2468a6a7bb6a601061031cddd77129532a3b467300bBill Wendling case BO_Shl: 247defaca00b8087d452df2b783250a48a32658a910Bill Wendling case BO_Shr: 248710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov case BO_Xor: 2499106f73246168fb30d26fb14085c0b3d81fcd350Reed Kotler // a+0, a-0, a<<0, a>>0, a^0 2509106f73246168fb30d26fb14085c0b3d81fcd350Reed Kotler if (RHS == 0) 2518a6a7bb6a601061031cddd77129532a3b467300bBill Wendling isIdempotent = true; 2529106f73246168fb30d26fb14085c0b3d81fcd350Reed Kotler break; 2539e2ef7780b91d8e01a9ab172f80272fc94f6956bBill Wendling case BO_And: 2549e2ef7780b91d8e01a9ab172f80272fc94f6956bBill Wendling // a&0 and a&(~0) 2559106f73246168fb30d26fb14085c0b3d81fcd350Reed Kotler if (RHS == 0) 256e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling return makeIntVal(0, resultTy); 257e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling else if (RHS.isAllOnesValue()) 2588a6a7bb6a601061031cddd77129532a3b467300bBill Wendling isIdempotent = true; 259e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling break; 260e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling case BO_Or: 26118e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling // a|0 and a|(~0) 2628246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling if (RHS == 0) 26318e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling isIdempotent = true; 2648a6a7bb6a601061031cddd77129532a3b467300bBill Wendling else if (RHS.isAllOnesValue()) { 2658246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS); 2668246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling return nonloc::ConcreteInt(Result); 2678246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling } 2688246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling break; 2698246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling } 2708a6a7bb6a601061031cddd77129532a3b467300bBill Wendling 2718246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling // Idempotent ops (like a*1) can still change the type of an expression. 272710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the 27358d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner // dirty work. 274c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling if (isIdempotent) 27558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy); 27618e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling 27785b3fbecdfe934ac7519a8831c4bd262cba99d12Bill Wendling // If we reach this point, the expression cannot be simplified. 27885b3fbecdfe934ac7519a8831c4bd262cba99d12Bill Wendling // Make a SymbolVal for the entire expression, after converting the RHS. 27985b3fbecdfe934ac7519a8831c4bd262cba99d12Bill Wendling const llvm::APSInt *ConvertedRHS = &RHS; 28018e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling if (BinaryOperator::isComparisonOp(op)) { 2818a6a7bb6a601061031cddd77129532a3b467300bBill Wendling // We're looking for a type big enough to compare the symbolic value 28219c874638d9478a5d5028854817a5ee72293bb2bDevang Patel // with the given constant. 28318e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling // FIXME: This is an approximation of Sema::UsualArithmeticConversions. 2843fc4b96b503fa202411317684a2ba02e41e43072Bill Wendling ASTContext &Ctx = getContext(); 28519c874638d9478a5d5028854817a5ee72293bb2bDevang Patel QualType SymbolType = LHS->getType(); 28618e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling uint64_t ValWidth = RHS.getBitWidth(); 287c5f1bc88a2eb7ad9ff924ca90cf88494e5f947b9Bill Wendling uint64_t TypeWidth = Ctx.getTypeSize(SymbolType); 288710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov 289831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling if (ValWidth < TypeWidth) { 29019d815c04fde6b7b53c2b542813157edfa213842Bill Wendling // If the value is too small, extend it. 291831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling ConvertedRHS = &BasicVals.Convert(SymbolType, RHS); 2920e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling } else if (ValWidth == TypeWidth) { 2930e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling // If the value is signed but the symbol is unsigned, do the comparison 2940e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling // in unsigned space. [C99 6.3.1.8] 295831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling // (For the opposite case, the value is already unsigned.) 29619d815c04fde6b7b53c2b542813157edfa213842Bill Wendling if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType()) 297831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling ConvertedRHS = &BasicVals.Convert(SymbolType, RHS); 298c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling } 299c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling } else 300c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling ConvertedRHS = &BasicVals.Convert(resultTy, RHS); 301c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 3020e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling return makeNonLoc(LHS, op, *ConvertedRHS, resultTy); 3030e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling} 3040e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling 3050e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill WendlingSVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, 3060e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling BinaryOperator::Opcode op, 3070e9d5d059c4aa959e9ef4dff011dbd38d45a1016Bill Wendling NonLoc lhs, NonLoc rhs, 30849f6060f16aec4024d644a6ec4ddd3de9b3e8821Bill Wendling QualType resultTy) { 3098a6a7bb6a601061031cddd77129532a3b467300bBill Wendling NonLoc InputLHS = lhs; 3108e47daf2858e980210f3e1f007036b24da342c29Bill Wendling NonLoc InputRHS = rhs; 311831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling 31219d815c04fde6b7b53c2b542813157edfa213842Bill Wendling // Handle trivial case where left-side and right-side are the same. 313831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling if (lhs == rhs) 314831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling switch (op) { 315aae0298921d946a64385052ce6e678d36f936fb3Rafael Espindola default: 316831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling break; 31716c4b3cf2943ae2327752cf3de39769d14cfceceBill Wendling case BO_EQ: 31816c4b3cf2943ae2327752cf3de39769d14cfceceBill Wendling case BO_LE: 3198a6a7bb6a601061031cddd77129532a3b467300bBill Wendling case BO_GE: 3208a6a7bb6a601061031cddd77129532a3b467300bBill Wendling return makeTruthVal(true, resultTy); 32116c4b3cf2943ae2327752cf3de39769d14cfceceBill Wendling case BO_LT: 322041221c0972ff575b07f76808c504833d629ae1fChris Lattner case BO_GT: 32318e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling case BO_NE: 324ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling return makeTruthVal(false, resultTy); 32518e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling case BO_Xor: 32618e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling case BO_Sub: 327ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling if (resultTy->isIntegralOrEnumerationType()) 32818e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling return makeIntVal(0, resultTy); 329710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov return evalCastFromNonLoc(makeIntVal(0, /*Unsigned=*/false), resultTy); 33058d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner case BO_Or: 331c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling case BO_And: 33258d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner return evalCastFromNonLoc(lhs, resultTy); 333710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov } 334c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 335c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling while (1) { 336c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling switch (lhs.getSubKind()) { 33718e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling default: 33858d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner return makeSymExprValNN(state, op, lhs, rhs, resultTy); 339ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling case nonloc::LocAsIntegerKind: { 34058d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc(); 341710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov switch (rhs.getSubKind()) { 34218e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling case nonloc::LocAsIntegerKind: 34358d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner return evalBinOpLL(state, op, lhsL, 344aa57893e84ba7a35948fcaa99812ba88e58f4797Bill Wendling rhs.castAs<nonloc::LocAsInteger>().getLoc(), 34558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner resultTy); 346710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov case nonloc::ConcreteIntKind: { 34718e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling // Transform the integer into a location and compare. 34818e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue(); 34918e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i); 35058d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy); 351710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov } 352e1f95db4803a48a30fc2a1d5868281a87a36fb85Bill Wendling default: 35376f103e02164d27b41bd92a9767c7012482ba31aRafael Espindola switch (op) { 354e1f95db4803a48a30fc2a1d5868281a87a36fb85Bill Wendling case BO_EQ: 3558e47daf2858e980210f3e1f007036b24da342c29Bill Wendling return makeTruthVal(false, resultTy); 3568e47daf2858e980210f3e1f007036b24da342c29Bill Wendling case BO_NE: 3578e47daf2858e980210f3e1f007036b24da342c29Bill Wendling return makeTruthVal(true, resultTy); 358f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling default: 35958d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner // This case also handles pointer arithmetic. 3604f859aa532dbf061736f9c23e0d0882b5cdfe566Reid Spencer return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 361a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 362a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 36316274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling } 36416274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling case nonloc::ConcreteIntKind: { 36516274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue(); 36616274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 36716274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling // If we're dealing with two known constants, just perform the operation. 36816274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) { 369c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling llvm::APSInt RHSValue = *KnownRHSValue; 37016274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling if (BinaryOperator::isComparisonOp(op)) { 37116274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling // We're looking for a type big enough to compare the two values. 37216274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling // FIXME: This is not correct. char + short will result in a promotion 37316274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling // to int. Unfortunately we have lost types by this point. 374c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling APSIntType CompareType = std::max(APSIntType(LHSValue), 37516274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling APSIntType(RHSValue)); 37616274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling CompareType.apply(LHSValue); 37716274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling CompareType.apply(RHSValue); 378c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling } else if (!BinaryOperator::isShiftOp(op)) { 37916274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling APSIntType IntType = BasicVals.getAPSIntType(resultTy); 380c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling IntType.apply(LHSValue); 381c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling IntType.apply(RHSValue); 382c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling } 383c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 384a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling const llvm::APSInt *Result = 385a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling BasicVals.evalAPSInt(op, LHSValue, RHSValue); 386a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (!Result) 387a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return UndefinedVal(); 388a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 3893f213e7b3a6829a154d4e8ceb7d8689b389bd5dcBenjamin Kramer return nonloc::ConcreteInt(*Result); 390ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling } 391a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 392a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling // Swap the left and right sides and flip the operator if doing so 393a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling // allows us to better reason about the expression (this is a form 394c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer // of expression canonicalization). 395c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer // While we're at it, catch some special cases for non-commutative ops. 396c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer switch (op) { 397f9271ea159b97e2febedcf095c3c4122cb24d077Bill Wendling case BO_LT: 398a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_GT: 399c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer case BO_LE: 40039da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling case BO_GE: 401a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling op = ReverseComparison(op); 402a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling // FALL-THROUGH 40385df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling case BO_EQ: 40485df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling case BO_NE: 40585df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling case BO_Add: 40685df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling case BO_Mul: 407a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_And: 408a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_Xor: 409a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_Or: 410a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling std::swap(lhs, rhs); 411a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling continue; 412a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_Shr: 41339da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling // (~0)>>a 41439da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling if (LHSValue.isAllOnesValue() && LHSValue.isSigned()) 41539da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling return evalCastFromNonLoc(lhs, resultTy); 416ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling // FALL-THROUGH 417ad19d9c4228718b0ac167d0dfa013d14c3c9f135Bill Wendling case BO_Shl: 418ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling // 0<<a and 0>>a 419a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (LHSValue == 0) 420a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return evalCastFromNonLoc(lhs, resultTy); 421a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 42249f6060f16aec4024d644a6ec4ddd3de9b3e8821Bill Wendling default: 423e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 424a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 425ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling } 426ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling case nonloc::SymbolValKind: { 427ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling // We only handle LHS as simple symbols or SymIntExprs. 42885df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol(); 42985df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling 43085df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling // LHS is a symbolic expression. 431a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) { 432c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer 4333f213e7b3a6829a154d4e8ceb7d8689b389bd5dcBenjamin Kramer // Is this a logical not? (!x is represented as x == 0.) 4343f213e7b3a6829a154d4e8ceb7d8689b389bd5dcBenjamin Kramer if (op == BO_EQ && rhs.isZeroConstant()) { 435c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer // We know how to negate certain expressions. Simplify them here. 436a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 437c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling BinaryOperator::Opcode opc = symIntExpr->getOpcode(); 438c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling switch (opc) { 439c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling default: 440c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling // We don't know how to negate this operation. 441a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling // Just handle it as if it were a normal comparison to 0. 442a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling break; 443a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_LAnd: 444a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_LOr: 445a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling llvm_unreachable("Logical operators handled by branching logic."); 446e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling case BO_Assign: 447a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_MulAssign: 448a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_DivAssign: 449a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_RemAssign: 450a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_AddAssign: 451a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_SubAssign: 452a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_ShlAssign: 453a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_ShrAssign: 454a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_AndAssign: 455a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_XorAssign: 456a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_OrAssign: 457a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_Comma: 458a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling llvm_unreachable("'=' and ',' operators handled by ExprEngine."); 459a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_PtrMemD: 460a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_PtrMemI: 461a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling llvm_unreachable("Pointer arithmetic not handled here."); 462a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_LT: 463a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_GT: 464a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case BO_LE: 465c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer case BO_GE: 466c835b8c30127d15599de2d614434d39a6cc3ae17Benjamin Kramer case BO_EQ: 4673f213e7b3a6829a154d4e8ceb7d8689b389bd5dcBenjamin Kramer case BO_NE: 46887de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling // Negate the comparison and make a value. 46964754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling opc = NegateComparison(opc); 47064754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling assert(symIntExpr->getType() == resultTy); 47164754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling return makeNonLoc(symIntExpr->getLHS(), opc, 47264754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling symIntExpr->getRHS(), resultTy); 47364754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling } 47464754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling } 47564754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling 47664754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling // For now, only handle expressions whose RHS is a constant. 47764754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) { 47864754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling // If both the LHS and the current expression are additive, 47964754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling // fold their constants and try again. 48087de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling if (BinaryOperator::isAdditiveOp(op)) { 48187de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling BinaryOperator::Opcode lop = symIntExpr->getOpcode(); 482a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (BinaryOperator::isAdditiveOp(lop)) { 483a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling // Convert the two constants to a common type, then combine them. 484a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 485a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling // resultTy may not be the best type to convert to, but it's 486c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling // probably the best choice in expressions with mixed type 487f9271ea159b97e2febedcf095c3c4122cb24d077Bill Wendling // (such as x+1U+2LL). The rules for implicit conversions should 488c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling // choose a reasonable type to preserve the expression, and will 489c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling // at least match how the value is going to be used. 490c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling APSIntType IntType = BasicVals.getAPSIntType(resultTy); 491a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS()); 492a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling const llvm::APSInt &second = IntType.convert(*RHSValue); 4938e47daf2858e980210f3e1f007036b24da342c29Bill Wendling 4948e47daf2858e980210f3e1f007036b24da342c29Bill Wendling const llvm::APSInt *newRHS; 4958e47daf2858e980210f3e1f007036b24da342c29Bill Wendling if (lop == op) 496e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling newRHS = BasicVals.evalAPSInt(BO_Add, first, second); 4978e47daf2858e980210f3e1f007036b24da342c29Bill Wendling else 4988e47daf2858e980210f3e1f007036b24da342c29Bill Wendling newRHS = BasicVals.evalAPSInt(BO_Sub, first, second); 4998e47daf2858e980210f3e1f007036b24da342c29Bill Wendling 50027107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling assert(newRHS && "Invalid operation despite common type!"); 5016091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer rhs = nonloc::ConcreteInt(*newRHS); 5026091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer lhs = nonloc::SymbolVal(symIntExpr->getLHS()); 503 op = lop; 504 continue; 505 } 506 } 507 508 // Otherwise, make a SymIntExpr out of the expression. 509 return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy); 510 } 511 } 512 513 // Does the symbolic expression simplify to a constant? 514 // If so, "fold" the constant by setting 'lhs' to a ConcreteInt 515 // and try again. 516 ConstraintManager &CMgr = state->getConstraintManager(); 517 if (const llvm::APSInt *Constant = CMgr.getSymVal(state, Sym)) { 518 lhs = nonloc::ConcreteInt(*Constant); 519 continue; 520 } 521 522 // Is the RHS a constant? 523 if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) 524 return MakeSymIntVal(Sym, op, *RHSValue, resultTy); 525 526 // Give up -- this is not a symbolic expression we can handle. 527 return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 528 } 529 } 530 } 531} 532 533// FIXME: all this logic will change if/when we have MemRegion::getLocation(). 534SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, 535 BinaryOperator::Opcode op, 536 Loc lhs, Loc rhs, 537 QualType resultTy) { 538 // Only comparisons and subtractions are valid operations on two pointers. 539 // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15]. 540 // However, if a pointer is casted to an integer, evalBinOpNN may end up 541 // calling this function with another operation (PR7527). We don't attempt to 542 // model this for now, but it could be useful, particularly when the 543 // "location" is actually an integer value that's been passed through a void*. 544 if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub)) 545 return UnknownVal(); 546 547 // Special cases for when both sides are identical. 548 if (lhs == rhs) { 549 switch (op) { 550 default: 551 llvm_unreachable("Unimplemented operation for two identical values"); 552 case BO_Sub: 553 return makeZeroVal(resultTy); 554 case BO_EQ: 555 case BO_LE: 556 case BO_GE: 557 return makeTruthVal(true, resultTy); 558 case BO_NE: 559 case BO_LT: 560 case BO_GT: 561 return makeTruthVal(false, resultTy); 562 } 563 } 564 565 switch (lhs.getSubKind()) { 566 default: 567 llvm_unreachable("Ordering not implemented for this Loc."); 568 569 case loc::GotoLabelKind: 570 // The only thing we know about labels is that they're non-null. 571 if (rhs.isZeroConstant()) { 572 switch (op) { 573 default: 574 break; 575 case BO_Sub: 576 return evalCastFromLoc(lhs, resultTy); 577 case BO_EQ: 578 case BO_LE: 579 case BO_LT: 580 return makeTruthVal(false, resultTy); 581 case BO_NE: 582 case BO_GT: 583 case BO_GE: 584 return makeTruthVal(true, resultTy); 585 } 586 } 587 // There may be two labels for the same location, and a function region may 588 // have the same address as a label at the start of the function (depending 589 // on the ABI). 590 // FIXME: we can probably do a comparison against other MemRegions, though. 591 // FIXME: is there a way to tell if two labels refer to the same location? 592 return UnknownVal(); 593 594 case loc::ConcreteIntKind: { 595 // If one of the operands is a symbol and the other is a constant, 596 // build an expression for use by the constraint manager. 597 if (SymbolRef rSym = rhs.getAsLocSymbol()) { 598 // We can only build expressions with symbols on the left, 599 // so we need a reversible operator. 600 if (!BinaryOperator::isComparisonOp(op)) 601 return UnknownVal(); 602 603 const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue(); 604 return makeNonLoc(rSym, ReverseComparison(op), lVal, resultTy); 605 } 606 607 // If both operands are constants, just perform the operation. 608 if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) { 609 SVal ResultVal = 610 lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt); 611 if (Optional<Loc> Result = ResultVal.getAs<Loc>()) 612 return evalCastFromLoc(*Result, resultTy); 613 else 614 return UnknownVal(); 615 } 616 617 // Special case comparisons against NULL. 618 // This must come after the test if the RHS is a symbol, which is used to 619 // build constraints. The address of any non-symbolic region is guaranteed 620 // to be non-NULL, as is any label. 621 assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>()); 622 if (lhs.isZeroConstant()) { 623 switch (op) { 624 default: 625 break; 626 case BO_EQ: 627 case BO_GT: 628 case BO_GE: 629 return makeTruthVal(false, resultTy); 630 case BO_NE: 631 case BO_LT: 632 case BO_LE: 633 return makeTruthVal(true, resultTy); 634 } 635 } 636 637 // Comparing an arbitrary integer to a region or label address is 638 // completely unknowable. 639 return UnknownVal(); 640 } 641 case loc::MemRegionKind: { 642 if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) { 643 // If one of the operands is a symbol and the other is a constant, 644 // build an expression for use by the constraint manager. 645 if (SymbolRef lSym = lhs.getAsLocSymbol()) 646 return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy); 647 648 // Special case comparisons to NULL. 649 // This must come after the test if the LHS is a symbol, which is used to 650 // build constraints. The address of any non-symbolic region is guaranteed 651 // to be non-NULL. 652 if (rInt->isZeroConstant()) { 653 switch (op) { 654 default: 655 break; 656 case BO_Sub: 657 return evalCastFromLoc(lhs, resultTy); 658 case BO_EQ: 659 case BO_LT: 660 case BO_LE: 661 return makeTruthVal(false, resultTy); 662 case BO_NE: 663 case BO_GT: 664 case BO_GE: 665 return makeTruthVal(true, resultTy); 666 } 667 } 668 669 // Comparing a region to an arbitrary integer is completely unknowable. 670 return UnknownVal(); 671 } 672 673 // Get both values as regions, if possible. 674 const MemRegion *LeftMR = lhs.getAsRegion(); 675 assert(LeftMR && "MemRegionKind SVal doesn't have a region!"); 676 677 const MemRegion *RightMR = rhs.getAsRegion(); 678 if (!RightMR) 679 // The RHS is probably a label, which in theory could address a region. 680 // FIXME: we can probably make a more useful statement about non-code 681 // regions, though. 682 return UnknownVal(); 683 684 const MemRegion *LeftBase = LeftMR->getBaseRegion(); 685 const MemRegion *RightBase = RightMR->getBaseRegion(); 686 const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace(); 687 const MemSpaceRegion *RightMS = RightBase->getMemorySpace(); 688 const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion(); 689 690 // If the two regions are from different known memory spaces they cannot be 691 // equal. Also, assume that no symbolic region (whose memory space is 692 // unknown) is on the stack. 693 if (LeftMS != RightMS && 694 ((LeftMS != UnknownMS && RightMS != UnknownMS) || 695 (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) { 696 switch (op) { 697 default: 698 return UnknownVal(); 699 case BO_EQ: 700 return makeTruthVal(false, resultTy); 701 case BO_NE: 702 return makeTruthVal(true, resultTy); 703 } 704 } 705 706 // If both values wrap regions, see if they're from different base regions. 707 // Note, heap base symbolic regions are assumed to not alias with 708 // each other; for example, we assume that malloc returns different address 709 // on each invocation. 710 if (LeftBase != RightBase && 711 ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) || 712 (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){ 713 switch (op) { 714 default: 715 return UnknownVal(); 716 case BO_EQ: 717 return makeTruthVal(false, resultTy); 718 case BO_NE: 719 return makeTruthVal(true, resultTy); 720 } 721 } 722 723 // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this 724 // ElementRegion path and the FieldRegion path below should be unified. 725 if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) { 726 // First see if the right region is also an ElementRegion. 727 const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR); 728 if (!RightER) 729 return UnknownVal(); 730 731 // Next, see if the two ERs have the same super-region and matching types. 732 // FIXME: This should do something useful even if the types don't match, 733 // though if both indexes are constant the RegionRawOffset path will 734 // give the correct answer. 735 if (LeftER->getSuperRegion() == RightER->getSuperRegion() && 736 LeftER->getElementType() == RightER->getElementType()) { 737 // Get the left index and cast it to the correct type. 738 // If the index is unknown or undefined, bail out here. 739 SVal LeftIndexVal = LeftER->getIndex(); 740 Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>(); 741 if (!LeftIndex) 742 return UnknownVal(); 743 LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy); 744 LeftIndex = LeftIndexVal.getAs<NonLoc>(); 745 if (!LeftIndex) 746 return UnknownVal(); 747 748 // Do the same for the right index. 749 SVal RightIndexVal = RightER->getIndex(); 750 Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>(); 751 if (!RightIndex) 752 return UnknownVal(); 753 RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy); 754 RightIndex = RightIndexVal.getAs<NonLoc>(); 755 if (!RightIndex) 756 return UnknownVal(); 757 758 // Actually perform the operation. 759 // evalBinOpNN expects the two indexes to already be the right type. 760 return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy); 761 } 762 763 // If the element indexes aren't comparable, see if the raw offsets are. 764 RegionRawOffset LeftOffset = LeftER->getAsArrayOffset(); 765 RegionRawOffset RightOffset = RightER->getAsArrayOffset(); 766 767 if (LeftOffset.getRegion() != NULL && 768 LeftOffset.getRegion() == RightOffset.getRegion()) { 769 CharUnits left = LeftOffset.getOffset(); 770 CharUnits right = RightOffset.getOffset(); 771 772 switch (op) { 773 default: 774 return UnknownVal(); 775 case BO_LT: 776 return makeTruthVal(left < right, resultTy); 777 case BO_GT: 778 return makeTruthVal(left > right, resultTy); 779 case BO_LE: 780 return makeTruthVal(left <= right, resultTy); 781 case BO_GE: 782 return makeTruthVal(left >= right, resultTy); 783 case BO_EQ: 784 return makeTruthVal(left == right, resultTy); 785 case BO_NE: 786 return makeTruthVal(left != right, resultTy); 787 } 788 } 789 790 // If we get here, we have no way of comparing the ElementRegions. 791 } 792 793 // See if both regions are fields of the same structure. 794 // FIXME: This doesn't handle nesting, inheritance, or Objective-C ivars. 795 if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) { 796 // Only comparisons are meaningful here! 797 if (!BinaryOperator::isComparisonOp(op)) 798 return UnknownVal(); 799 800 // First see if the right region is also a FieldRegion. 801 const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR); 802 if (!RightFR) 803 return UnknownVal(); 804 805 // Next, see if the two FRs have the same super-region. 806 // FIXME: This doesn't handle casts yet, and simply stripping the casts 807 // doesn't help. 808 if (LeftFR->getSuperRegion() != RightFR->getSuperRegion()) 809 return UnknownVal(); 810 811 const FieldDecl *LeftFD = LeftFR->getDecl(); 812 const FieldDecl *RightFD = RightFR->getDecl(); 813 const RecordDecl *RD = LeftFD->getParent(); 814 815 // Make sure the two FRs are from the same kind of record. Just in case! 816 // FIXME: This is probably where inheritance would be a problem. 817 if (RD != RightFD->getParent()) 818 return UnknownVal(); 819 820 // We know for sure that the two fields are not the same, since that 821 // would have given us the same SVal. 822 if (op == BO_EQ) 823 return makeTruthVal(false, resultTy); 824 if (op == BO_NE) 825 return makeTruthVal(true, resultTy); 826 827 // Iterate through the fields and see which one comes first. 828 // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field 829 // members and the units in which bit-fields reside have addresses that 830 // increase in the order in which they are declared." 831 bool leftFirst = (op == BO_LT || op == BO_LE); 832 for (RecordDecl::field_iterator I = RD->field_begin(), 833 E = RD->field_end(); I!=E; ++I) { 834 if (*I == LeftFD) 835 return makeTruthVal(leftFirst, resultTy); 836 if (*I == RightFD) 837 return makeTruthVal(!leftFirst, resultTy); 838 } 839 840 llvm_unreachable("Fields not found in parent record's definition"); 841 } 842 843 // At this point we're not going to get a good answer, but we can try 844 // conjuring an expression instead. 845 SymbolRef LHSSym = lhs.getAsLocSymbol(); 846 SymbolRef RHSSym = rhs.getAsLocSymbol(); 847 if (LHSSym && RHSSym) 848 return makeNonLoc(LHSSym, op, RHSSym, resultTy); 849 850 // If we get here, we have no way of comparing the regions. 851 return UnknownVal(); 852 } 853 } 854} 855 856SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, 857 BinaryOperator::Opcode op, 858 Loc lhs, NonLoc rhs, QualType resultTy) { 859 860 // Special case: rhs is a zero constant. 861 if (rhs.isZeroConstant()) 862 return lhs; 863 864 // Special case: 'rhs' is an integer that has the same width as a pointer and 865 // we are using the integer location in a comparison. Normally this cannot be 866 // triggered, but transfer functions like those for OSCompareAndSwapBarrier32 867 // can generate comparisons that trigger this code. 868 // FIXME: Are all locations guaranteed to have pointer width? 869 if (BinaryOperator::isComparisonOp(op)) { 870 if (Optional<nonloc::ConcreteInt> rhsInt = 871 rhs.getAs<nonloc::ConcreteInt>()) { 872 const llvm::APSInt *x = &rhsInt->getValue(); 873 ASTContext &ctx = Context; 874 if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) { 875 // Convert the signedness of the integer (if necessary). 876 if (x->isSigned()) 877 x = &getBasicValueFactory().getValue(*x, true); 878 879 return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy); 880 } 881 } 882 return UnknownVal(); 883 } 884 885 // We are dealing with pointer arithmetic. 886 887 // Handle pointer arithmetic on constant values. 888 if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) { 889 if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) { 890 const llvm::APSInt &leftI = lhsInt->getValue(); 891 assert(leftI.isUnsigned()); 892 llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true); 893 894 // Convert the bitwidth of rightI. This should deal with overflow 895 // since we are dealing with concrete values. 896 rightI = rightI.extOrTrunc(leftI.getBitWidth()); 897 898 // Offset the increment by the pointer size. 899 llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true); 900 rightI *= Multiplicand; 901 902 // Compute the adjusted pointer. 903 switch (op) { 904 case BO_Add: 905 rightI = leftI + rightI; 906 break; 907 case BO_Sub: 908 rightI = leftI - rightI; 909 break; 910 default: 911 llvm_unreachable("Invalid pointer arithmetic operation"); 912 } 913 return loc::ConcreteInt(getBasicValueFactory().getValue(rightI)); 914 } 915 } 916 917 // Handle cases where 'lhs' is a region. 918 if (const MemRegion *region = lhs.getAsRegion()) { 919 rhs = convertToArrayIndex(rhs).castAs<NonLoc>(); 920 SVal index = UnknownVal(); 921 const MemRegion *superR = 0; 922 QualType elementType; 923 924 if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) { 925 assert(op == BO_Add || op == BO_Sub); 926 index = evalBinOpNN(state, op, elemReg->getIndex(), rhs, 927 getArrayIndexType()); 928 superR = elemReg->getSuperRegion(); 929 elementType = elemReg->getElementType(); 930 } 931 else if (isa<SubRegion>(region)) { 932 superR = region; 933 index = rhs; 934 if (resultTy->isAnyPointerType()) 935 elementType = resultTy->getPointeeType(); 936 } 937 938 if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) { 939 return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV, 940 superR, getContext())); 941 } 942 } 943 return UnknownVal(); 944} 945 946const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, 947 SVal V) { 948 if (V.isUnknownOrUndef()) 949 return NULL; 950 951 if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>()) 952 return &X->getValue(); 953 954 if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>()) 955 return &X->getValue(); 956 957 if (SymbolRef Sym = V.getAsSymbol()) 958 return state->getConstraintManager().getSymVal(state, Sym); 959 960 // FIXME: Add support for SymExprs. 961 return NULL; 962} 963