1846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek// SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- C++ -*- 2e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// 3e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// The LLVM Compiler Infrastructure 4e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// 5e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// This file is distributed under the University of Illinois Open Source 6e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// License. See LICENSE.TXT for details. 7e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// 8e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 9e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// 10846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek// This file defines SimpleSValBuilder, a basic implementation of SValBuilder. 11e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// 12e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 13e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 149b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 1555fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 1618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 18e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenekusing namespace clang; 199ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 20e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 21e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremeneknamespace { 22846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenekclass SimpleSValBuilder : public SValBuilder { 2332c3fa4195762ba93f0b7114ab36c0941bc34432Ted Kremenekprotected: 24651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal dispatchCast(SVal val, QualType castTy) override; 25651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalCastFromNonLoc(NonLoc val, QualType castTy) override; 26651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalCastFromLoc(Loc val, QualType castTy) override; 2732c3fa4195762ba93f0b7114ab36c0941bc34432Ted Kremenek 28e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenekpublic: 29c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, 3018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramStateManager &stateMgr) 31c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek : SValBuilder(alloc, context, stateMgr) {} 32846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek virtual ~SimpleSValBuilder() {} 331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalMinus(NonLoc val) override; 35651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalComplement(NonLoc val) override; 36651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, 37651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines NonLoc lhs, NonLoc rhs, QualType resultTy) override; 38651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, 39651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Loc lhs, Loc rhs, QualType resultTy) override; 40651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, 41651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Loc lhs, NonLoc rhs, QualType resultTy) override; 4232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 439c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed Kremenek /// getKnownValue - evaluates a given SVal. If the SVal has only one possible 4432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose /// (integer) value, that value is returned. Otherwise, returns NULL. 45651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override; 46651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 4743fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op, 4843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose const llvm::APSInt &RHS, QualType resultTy); 491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump}; 50e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} // end anonymous namespace 51e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 529ef6537a894c33003359b1f9b9676e9178e028b7Ted KremenekSValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, 539ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek ASTContext &context, 5418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramStateManager &stateMgr) { 55c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return new SimpleSValBuilder(alloc, context, stateMgr); 56e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 57e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 58e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 59e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// Transfer function for Casts. 60e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 61e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 62bcb3b981da3d29844fea4099c529b43e814b6d7dAnna ZaksSVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) { 635251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie assert(Val.getAs<Loc>() || Val.getAs<NonLoc>()); 645251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy) 655251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy); 66aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks} 67aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks 689f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong WanSVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) { 691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 707dfc9420babe83e236a47e752f8723bd06070d9dZhanyong Wan bool isLocType = Loc::isLocType(castTy); 711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 72dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::LocAsInteger> LI = val.getAs<nonloc::LocAsInteger>()) { 739031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek if (isLocType) 74dd6611426b96019516ed473ce25a8664065e9865Ted Kremenek return LI->getLoc(); 751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 76c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek // FIXME: Correctly support promotions/truncations. 77c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek unsigned castSize = Context.getTypeSize(castTy); 78c50e6df965ff264952d8d5805d151f89c89af302Ted Kremenek if (castSize == LI->getNumBits()) 799031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek return val; 80c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeLocAsInteger(LI->getLoc(), castSize); 819031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek } 829031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek 839031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek if (const SymExpr *se = val.getAsSymbolicExpression()) { 84732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted Kremenek QualType T = Context.getCanonicalType(se->getType()); 85432a4558b8161c362efc319f8a38e074e74da201Anna Zaks // If types are the same or both are integers, ignore the cast. 8680417471b01ab2726cd04773b2ab700ce564073cTed Kremenek // FIXME: Remove this hack when we support symbolic truncation/extension. 8780417471b01ab2726cd04773b2ab700ce564073cTed Kremenek // HACK: If both castTy and T are integers, ignore the cast. This is 8880417471b01ab2726cd04773b2ab700ce564073cTed Kremenek // not a permanent solution. Eventually we want to precisely handle 8980417471b01ab2726cd04773b2ab700ce564073cTed Kremenek // extension/truncation of symbolic integers. This prevents us from losing 9080417471b01ab2726cd04773b2ab700ce564073cTed Kremenek // precision when we assign 'x = y' and 'y' is symbolic and x and y are 9180417471b01ab2726cd04773b2ab700ce564073cTed Kremenek // different integer types. 92432a4558b8161c362efc319f8a38e074e74da201Anna Zaks if (haveSameType(T, castTy)) 9380417471b01ab2726cd04773b2ab700ce564073cTed Kremenek return val; 941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 95aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks if (!isLocType) 96aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return makeNonLoc(se, T, castTy); 979031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek return UnknownVal(); 989031dd7a989f893be0c3a9d8915b1218646be763Ted Kremenek } 991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 100651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // If value is a non-integer constant, produce unknown. 1015251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!val.getAs<nonloc::ConcreteInt>()) 102e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek return UnknownVal(); 1031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1049c0466603f2051fec9270686dfcd270630e62530Ted Kremenek // Handle casts to a boolean type. 1059c0466603f2051fec9270686dfcd270630e62530Ted Kremenek if (castTy->isBooleanType()) { 1065251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue(); 1079c0466603f2051fec9270686dfcd270630e62530Ted Kremenek return makeTruthVal(b, castTy); 1089c0466603f2051fec9270686dfcd270630e62530Ted Kremenek } 1099c0466603f2051fec9270686dfcd270630e62530Ted Kremenek 1105fc7def35ee858791e591d005b4ae343632ca931Anna Zaks // Only handle casts from integers to integers - if val is an integer constant 111651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // being cast to a non-integer type, produce unknown. 112a5796f87229b4aeebca71fa6ee1790ae7a5a0382Jordan Rose if (!isLocType && !castTy->isIntegralOrEnumerationType()) 113e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek return UnknownVal(); 1141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1155251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue(); 116d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose BasicVals.getAPSIntType(castTy).apply(i); 117e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 118e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek if (isLocType) 119c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeIntLocVal(i); 120e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek else 121c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeIntVal(i); 122e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 123e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 1249f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong WanSVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) { 1251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 126e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // Casts from pointers -> pointers, just return the lval. 127e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // 128e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // Casts from pointers -> references, just return the lval. These 129e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // can be introduced by the frontend for corner cases, e.g 130e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // casting from va_list* to __builtin_va_list&. 131e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // 1327dfc9420babe83e236a47e752f8723bd06070d9dZhanyong Wan if (Loc::isLocType(castTy) || castTy->isReferenceType()) 133e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek return val; 1341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 135e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // FIXME: Handle transparent unions where a value can be "transparently" 136e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // lifted into a union type. 137e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek if (castTy->isUnionType()) 138e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek return UnknownVal(); 1391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1403aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose // Casting a Loc to a bool will almost always be true, 1413aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose // unless this is a weak function or a symbolic region. 1423aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (castTy->isBooleanType()) { 1433aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose switch (val.getSubKind()) { 1443aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose case loc::MemRegionKind: { 1453aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion(); 1463aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (const FunctionTextRegion *FTR = dyn_cast<FunctionTextRegion>(R)) 1473aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl())) 1483aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (FD->isWeak()) 1493aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose // FIXME: Currently we are using an extent symbol here, 1503aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose // because there are no generic region address metadata 1513aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose // symbols to use, only content metadata. 1523aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR)); 1533aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose 1543aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (const SymbolicRegion *SymR = R->getSymbolicBase()) 1553aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose return nonloc::SymbolVal(SymR->getSymbol()); 1563aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose 1573aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose // FALL-THROUGH 1583aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose } 1593aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose 1603aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose case loc::GotoLabelKind: 161651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Labels and non-symbolic memory regions are always true. 1623aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose return makeTruthVal(true, castTy); 1633aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose } 1643aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose } 1653aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose 166a5796f87229b4aeebca71fa6ee1790ae7a5a0382Jordan Rose if (castTy->isIntegralOrEnumerationType()) { 167c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek unsigned BitWidth = Context.getTypeSize(castTy); 168e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 1695251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!val.getAs<loc::ConcreteInt>()) 170c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeLocAsInteger(val, BitWidth); 1711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1725251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie llvm::APSInt i = val.castAs<loc::ConcreteInt>().getValue(); 173d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose BasicVals.getAPSIntType(castTy).apply(i); 174c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeIntVal(i); 175d617b85d12169ccb4bdf281836a281d0c173ba6aTed Kremenek } 176d617b85d12169ccb4bdf281836a281d0c173ba6aTed Kremenek 177d617b85d12169ccb4bdf281836a281d0c173ba6aTed Kremenek // All other cases: return 'UnknownVal'. This includes casting pointers 178d617b85d12169ccb4bdf281836a281d0c173ba6aTed Kremenek // to floats, which is probably badness it itself, but this is a good 179d617b85d12169ccb4bdf281836a281d0c173ba6aTed Kremenek // intermediate solution until we do something better. 180d617b85d12169ccb4bdf281836a281d0c173ba6aTed Kremenek return UnknownVal(); 181e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 182e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 183e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 184e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// Transfer function for unary operators. 185e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 186e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 1879c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed KremenekSVal SimpleSValBuilder::evalMinus(NonLoc val) { 1881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump switch (val.getSubKind()) { 189e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek case nonloc::ConcreteIntKind: 1905251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie return val.castAs<nonloc::ConcreteInt>().evalMinus(*this); 191e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek default: 192e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek return UnknownVal(); 193e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 194e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 195e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 1969c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed KremenekSVal SimpleSValBuilder::evalComplement(NonLoc X) { 197e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek switch (X.getSubKind()) { 198e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek case nonloc::ConcreteIntKind: 1995251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie return X.castAs<nonloc::ConcreteInt>().evalComplement(*this); 200e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek default: 201e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek return UnknownVal(); 202e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 203e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 204e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 205e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 206e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek// Transfer function for binary operators. 207e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek//===----------------------------------------------------------------------===// 208e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 209846eabd187be4bfe992e8bca131166b734d86e0dTed KremenekSVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS, 21043fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose BinaryOperator::Opcode op, 21143fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose const llvm::APSInt &RHS, 21243fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose QualType resultTy) { 21343fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose bool isIdempotent = false; 21443fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose 21543fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // Check for a few special cases with known reductions first. 21643fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose switch (op) { 21743fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose default: 21843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // We can't reduce this case; just treat it normally. 21943fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 2202de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Mul: 22143fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // a*0 and a*1 22243fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose if (RHS == 0) 223c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeIntVal(0, resultTy); 22443fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose else if (RHS == 1) 22543fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose isIdempotent = true; 22643fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 2272de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Div: 22843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // a/0 and a/1 22943fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose if (RHS == 0) 23043fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // This is also handled elsewhere. 23143fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose return UndefinedVal(); 23243fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose else if (RHS == 1) 23343fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose isIdempotent = true; 23443fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 2352de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Rem: 23643fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // a%0 and a%1 23743fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose if (RHS == 0) 23843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // This is also handled elsewhere. 23943fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose return UndefinedVal(); 24043fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose else if (RHS == 1) 241c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeIntVal(0, resultTy); 24243fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 2432de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Add: 2442de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Sub: 2452de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Shl: 2462de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Shr: 2472de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Xor: 24843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // a+0, a-0, a<<0, a>>0, a^0 24943fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose if (RHS == 0) 25043fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose isIdempotent = true; 25143fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 2522de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_And: 25343fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // a&0 and a&(~0) 25443fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose if (RHS == 0) 255c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeIntVal(0, resultTy); 25643fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose else if (RHS.isAllOnesValue()) 25743fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose isIdempotent = true; 25843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 2592de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Or: 26043fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // a|0 and a|(~0) 26143fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose if (RHS == 0) 26243fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose isIdempotent = true; 26343fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose else if (RHS.isAllOnesValue()) { 264c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS); 26543fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose return nonloc::ConcreteInt(Result); 26643fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose } 26743fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose break; 26843fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose } 26943fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose 27043fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // Idempotent ops (like a*1) can still change the type of an expression. 2719f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong Wan // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the 2729f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong Wan // dirty work. 2735344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks if (isIdempotent) 27476462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy); 27543fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose 27643fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose // If we reach this point, the expression cannot be simplified. 277c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // Make a SymbolVal for the entire expression, after converting the RHS. 278c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose const llvm::APSInt *ConvertedRHS = &RHS; 279c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (BinaryOperator::isComparisonOp(op)) { 280c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // We're looking for a type big enough to compare the symbolic value 281c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // with the given constant. 282c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // FIXME: This is an approximation of Sema::UsualArithmeticConversions. 283c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose ASTContext &Ctx = getContext(); 284732cdf383f9030ff2b9fb28dfbdae2285ded80c6Ted Kremenek QualType SymbolType = LHS->getType(); 285c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose uint64_t ValWidth = RHS.getBitWidth(); 286c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose uint64_t TypeWidth = Ctx.getTypeSize(SymbolType); 287c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 288c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (ValWidth < TypeWidth) { 289c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // If the value is too small, extend it. 290c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose ConvertedRHS = &BasicVals.Convert(SymbolType, RHS); 291c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose } else if (ValWidth == TypeWidth) { 292c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // If the value is signed but the symbol is unsigned, do the comparison 293c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // in unsigned space. [C99 6.3.1.8] 294c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // (For the opposite case, the value is already unsigned.) 295c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType()) 296c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose ConvertedRHS = &BasicVals.Convert(SymbolType, RHS); 297c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose } 298c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose } else 299c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose ConvertedRHS = &BasicVals.Convert(resultTy, RHS); 300c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 301c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return makeNonLoc(LHS, op, *ConvertedRHS, resultTy); 30243fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose} 30343fdb7f3b46059d4af11a702af35bc8e5d0f678aJordy Rose 3048bef8238181a30e52dea380789a7e2d760eac532Ted KremenekSVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, 305cd8f6ac9b613e1fe962ebf9c87d822ce765275e6Ted Kremenek BinaryOperator::Opcode op, 306e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek NonLoc lhs, NonLoc rhs, 30754ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek QualType resultTy) { 308da3960347a5d563d6746cb363b25466282a09ce3Anna Zaks NonLoc InputLHS = lhs; 309da3960347a5d563d6746cb363b25466282a09ce3Anna Zaks NonLoc InputRHS = rhs; 310da3960347a5d563d6746cb363b25466282a09ce3Anna Zaks 31154ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek // Handle trivial case where left-side and right-side are the same. 31254ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek if (lhs == rhs) 31354ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek switch (op) { 31454ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek default: 31554ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek break; 3162de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 3172de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LE: 3182de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GE: 319c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(true, resultTy); 3202de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LT: 3212de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GT: 3222de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 323c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(false, resultTy); 3242de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Xor: 3252de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Sub: 326791dd0a3f855b61ee97387dca67af86a1edff9f2Jordan Rose if (resultTy->isIntegralOrEnumerationType()) 327791dd0a3f855b61ee97387dca67af86a1edff9f2Jordan Rose return makeIntVal(0, resultTy); 328791dd0a3f855b61ee97387dca67af86a1edff9f2Jordan Rose return evalCastFromNonLoc(makeIntVal(0, /*Unsigned=*/false), resultTy); 3292de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Or: 3302de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_And: 3319f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong Wan return evalCastFromNonLoc(lhs, resultTy); 33254ca9b1d45fbfb0b3eeab581e0d10403cc922e62Ted Kremenek } 3331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 334e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek while (1) { 335e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek switch (lhs.getSubKind()) { 336e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek default: 337e2241cbb0455a60ba27d6c4b9d601ffef3ed103fAnna Zaks return makeSymExprValNN(state, op, lhs, rhs, resultTy); 338e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek case nonloc::LocAsIntegerKind: { 3395251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc(); 340e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek switch (rhs.getSubKind()) { 341e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek case nonloc::LocAsIntegerKind: 3429c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed Kremenek return evalBinOpLL(state, op, lhsL, 3435251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie rhs.castAs<nonloc::LocAsInteger>().getLoc(), 3441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump resultTy); 345e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek case nonloc::ConcreteIntKind: { 346e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // Transform the integer into a location and compare. 3475251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue(); 348d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i); 349c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy); 350e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 3511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump default: 352e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek switch (op) { 3532de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 354c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(false, resultTy); 3552de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 356c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(true, resultTy); 357e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek default: 358e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek // This case also handles pointer arithmetic. 359da3960347a5d563d6746cb363b25466282a09ce3Anna Zaks return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 360e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 361e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 3621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 3631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump case nonloc::ConcreteIntKind: { 3645251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue(); 365c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 366c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // If we're dealing with two known constants, just perform the operation. 367c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) { 368c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose llvm::APSInt RHSValue = *KnownRHSValue; 369c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (BinaryOperator::isComparisonOp(op)) { 370c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // We're looking for a type big enough to compare the two values. 371d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose // FIXME: This is not correct. char + short will result in a promotion 372d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose // to int. Unfortunately we have lost types by this point. 373d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType CompareType = std::max(APSIntType(LHSValue), 374d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType(RHSValue)); 375d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose CompareType.apply(LHSValue); 376d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose CompareType.apply(RHSValue); 377c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose } else if (!BinaryOperator::isShiftOp(op)) { 378d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType IntType = BasicVals.getAPSIntType(resultTy); 379d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose IntType.apply(LHSValue); 380d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose IntType.apply(RHSValue); 381a9af8e71bba24d2a1d1827972ef4cd856c179e56Jordy Rose } 382c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 383c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose const llvm::APSInt *Result = 384c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose BasicVals.evalAPSInt(op, LHSValue, RHSValue); 385c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (!Result) 386c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return UndefinedVal(); 387c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 388c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return nonloc::ConcreteInt(*Result); 389a9af8e71bba24d2a1d1827972ef4cd856c179e56Jordy Rose } 390a9af8e71bba24d2a1d1827972ef4cd856c179e56Jordy Rose 391c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // Swap the left and right sides and flip the operator if doing so 392c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // allows us to better reason about the expression (this is a form 393c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // of expression canonicalization). 394c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // While we're at it, catch some special cases for non-commutative ops. 395c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose switch (op) { 396c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_LT: 397c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_GT: 398c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_LE: 399c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_GE: 4008569281fb7ce9b5ca164a0528b876acbb45eb989Jordan Rose op = BinaryOperator::reverseComparisonOp(op); 401c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // FALL-THROUGH 402c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_EQ: 403c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_NE: 404c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_Add: 405c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_Mul: 406c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_And: 407c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_Xor: 408c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_Or: 409c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose std::swap(lhs, rhs); 410c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose continue; 411c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_Shr: 412c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // (~0)>>a 413c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (LHSValue.isAllOnesValue() && LHSValue.isSigned()) 414c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return evalCastFromNonLoc(lhs, resultTy); 415c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // FALL-THROUGH 416c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose case BO_Shl: 417c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // 0<<a and 0>>a 418c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (LHSValue == 0) 419c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return evalCastFromNonLoc(lhs, resultTy); 420c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 421c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose default: 422c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 423e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 424e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 425e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek case nonloc::SymbolValKind: { 426c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // We only handle LHS as simple symbols or SymIntExprs. 4275251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol(); 4285344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks 4295344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // LHS is a symbolic expression. 430c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) { 4315344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks 4325344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // Is this a logical not? (!x is represented as x == 0.) 4335344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks if (op == BO_EQ && rhs.isZeroConstant()) { 4345344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // We know how to negate certain expressions. Simplify them here. 4355344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks 4365344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks BinaryOperator::Opcode opc = symIntExpr->getOpcode(); 4375344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks switch (opc) { 4385344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks default: 4395344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // We don't know how to negate this operation. 4405344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // Just handle it as if it were a normal comparison to 0. 4415344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks break; 4425344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_LAnd: 4435344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_LOr: 4445344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks llvm_unreachable("Logical operators handled by branching logic."); 4455344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_Assign: 4465344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_MulAssign: 4475344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_DivAssign: 4485344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_RemAssign: 4495344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_AddAssign: 4505344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_SubAssign: 4515344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_ShlAssign: 4525344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_ShrAssign: 4535344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_AndAssign: 4545344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_XorAssign: 4555344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_OrAssign: 4565344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_Comma: 4575344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks llvm_unreachable("'=' and ',' operators handled by ExprEngine."); 4585344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_PtrMemD: 4595344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_PtrMemI: 4605344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks llvm_unreachable("Pointer arithmetic not handled here."); 4615344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_LT: 4625344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_GT: 4635344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_LE: 4645344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_GE: 4655344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_EQ: 4665344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks case BO_NE: 467112344ab7f96cf482bce80530676712c282756d5Jordan Rose assert(resultTy->isBooleanType() || 468112344ab7f96cf482bce80530676712c282756d5Jordan Rose resultTy == getConditionType()); 469112344ab7f96cf482bce80530676712c282756d5Jordan Rose assert(symIntExpr->getType()->isBooleanType() || 470112344ab7f96cf482bce80530676712c282756d5Jordan Rose getContext().hasSameUnqualifiedType(symIntExpr->getType(), 471112344ab7f96cf482bce80530676712c282756d5Jordan Rose getConditionType())); 4725344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // Negate the comparison and make a value. 4738569281fb7ce9b5ca164a0528b876acbb45eb989Jordan Rose opc = BinaryOperator::negateComparisonOp(opc); 4745344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks return makeNonLoc(symIntExpr->getLHS(), opc, 4755344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks symIntExpr->getRHS(), resultTy); 476b1d042212fbb3f6a08864b703b7bdf0dca58fd9cTed Kremenek } 477cd8f6ac9b613e1fe962ebf9c87d822ce765275e6Ted Kremenek } 478a277e7764bbe2752f900bf595654f9ad433f3961Jordy Rose 4795344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks // For now, only handle expressions whose RHS is a constant. 480c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) { 481c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // If both the LHS and the current expression are additive, 482c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // fold their constants and try again. 483c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (BinaryOperator::isAdditiveOp(op)) { 484c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose BinaryOperator::Opcode lop = symIntExpr->getOpcode(); 485c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (BinaryOperator::isAdditiveOp(lop)) { 486c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // Convert the two constants to a common type, then combine them. 487c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 488c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // resultTy may not be the best type to convert to, but it's 489c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // probably the best choice in expressions with mixed type 490c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // (such as x+1U+2LL). The rules for implicit conversions should 491c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // choose a reasonable type to preserve the expression, and will 492c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // at least match how the value is going to be used. 493d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose APSIntType IntType = BasicVals.getAPSIntType(resultTy); 494d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS()); 495d3b6d99cd57522b15dcec0eb771a97d9599d4db2Jordy Rose const llvm::APSInt &second = IntType.convert(*RHSValue); 496c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 497c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose const llvm::APSInt *newRHS; 498c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose if (lop == op) 499c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose newRHS = BasicVals.evalAPSInt(BO_Add, first, second); 500c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose else 501c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose newRHS = BasicVals.evalAPSInt(BO_Sub, first, second); 502c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 503c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose assert(newRHS && "Invalid operation despite common type!"); 504c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose rhs = nonloc::ConcreteInt(*newRHS); 505c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose lhs = nonloc::SymbolVal(symIntExpr->getLHS()); 506c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose op = lop; 507c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose continue; 508c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose } 509a277e7764bbe2752f900bf595654f9ad433f3961Jordy Rose } 510c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 511c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // Otherwise, make a SymIntExpr out of the expression. 512c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy); 513a277e7764bbe2752f900bf595654f9ad433f3961Jordy Rose } 5148958efacf8d52918cfe624116338bec62312582dJordan Rose } 515a277e7764bbe2752f900bf595654f9ad433f3961Jordy Rose 5168958efacf8d52918cfe624116338bec62312582dJordan Rose // Does the symbolic expression simplify to a constant? 5178958efacf8d52918cfe624116338bec62312582dJordan Rose // If so, "fold" the constant by setting 'lhs' to a ConcreteInt 5188958efacf8d52918cfe624116338bec62312582dJordan Rose // and try again. 5198958efacf8d52918cfe624116338bec62312582dJordan Rose ConstraintManager &CMgr = state->getConstraintManager(); 5208958efacf8d52918cfe624116338bec62312582dJordan Rose if (const llvm::APSInt *Constant = CMgr.getSymVal(state, Sym)) { 5218958efacf8d52918cfe624116338bec62312582dJordan Rose lhs = nonloc::ConcreteInt(*Constant); 5228958efacf8d52918cfe624116338bec62312582dJordan Rose continue; 5235344baa704f42b22d9df25c24ffbbf6b4716603bAnna Zaks } 524c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose 5258958efacf8d52918cfe624116338bec62312582dJordan Rose // Is the RHS a constant? 5268958efacf8d52918cfe624116338bec62312582dJordan Rose if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) 5278958efacf8d52918cfe624116338bec62312582dJordan Rose return MakeSymIntVal(Sym, op, *RHSValue, resultTy); 5288958efacf8d52918cfe624116338bec62312582dJordan Rose 529c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose // Give up -- this is not a symbolic expression we can handle. 530c838fd2ab889ffbb82c90da0cd634ef75b614b2cJordy Rose return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); 531e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 532e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 533e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 534e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 535e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 5364e9179a3d0ec612a4d540281020b200254348a6bAnna Zaksstatic SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR, 5374e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const FieldRegion *RightFR, 5384e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks BinaryOperator::Opcode op, 5394e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks QualType resultTy, 5404e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks SimpleSValBuilder &SVB) { 5414e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Only comparisons are meaningful here! 5424e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (!BinaryOperator::isComparisonOp(op)) 5434e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return UnknownVal(); 5444e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 5454e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Next, see if the two FRs have the same super-region. 5464e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // FIXME: This doesn't handle casts yet, and simply stripping the casts 5474e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // doesn't help. 5484e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (LeftFR->getSuperRegion() != RightFR->getSuperRegion()) 5494e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return UnknownVal(); 5504e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 5514e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const FieldDecl *LeftFD = LeftFR->getDecl(); 5524e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const FieldDecl *RightFD = RightFR->getDecl(); 5534e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const RecordDecl *RD = LeftFD->getParent(); 5544e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 5554e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Make sure the two FRs are from the same kind of record. Just in case! 5564e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // FIXME: This is probably where inheritance would be a problem. 5574e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (RD != RightFD->getParent()) 5584e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return UnknownVal(); 5594e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 5604e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // We know for sure that the two fields are not the same, since that 5614e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // would have given us the same SVal. 5624e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (op == BO_EQ) 5634e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return SVB.makeTruthVal(false, resultTy); 5644e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (op == BO_NE) 5654e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return SVB.makeTruthVal(true, resultTy); 5664e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 5674e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Iterate through the fields and see which one comes first. 5684e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field 5694e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // members and the units in which bit-fields reside have addresses that 5704e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // increase in the order in which they are declared." 5714e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks bool leftFirst = (op == BO_LT || op == BO_LE); 572651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (const auto *I : RD->fields()) { 573651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (I == LeftFD) 5744e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return SVB.makeTruthVal(leftFirst, resultTy); 575651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (I == RightFD) 5764e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return SVB.makeTruthVal(!leftFirst, resultTy); 5774e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks } 5784e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 5794e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks llvm_unreachable("Fields not found in parent record's definition"); 5804e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks} 5814e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 582eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose// FIXME: all this logic will change if/when we have MemRegion::getLocation(). 5838bef8238181a30e52dea380789a7e2d760eac532Ted KremenekSVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, 584eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose BinaryOperator::Opcode op, 585eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose Loc lhs, Loc rhs, 5861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump QualType resultTy) { 587eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Only comparisons and subtractions are valid operations on two pointers. 588eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15]. 5899c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed Kremenek // However, if a pointer is casted to an integer, evalBinOpNN may end up 590a274148a5cf85f758e469d5785fb72736f93f58bJordy Rose // calling this function with another operation (PR7527). We don't attempt to 591a274148a5cf85f758e469d5785fb72736f93f58bJordy Rose // model this for now, but it could be useful, particularly when the 592a274148a5cf85f758e469d5785fb72736f93f58bJordy Rose // "location" is actually an integer value that's been passed through a void*. 5932de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub)) 594a274148a5cf85f758e469d5785fb72736f93f58bJordy Rose return UnknownVal(); 595eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 596eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Special cases for when both sides are identical. 597eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (lhs == rhs) { 598eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose switch (op) { 599e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek default: 600b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Unimplemented operation for two identical values"); 6012de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Sub: 602c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeZeroVal(resultTy); 6032de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 6042de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LE: 6052de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GE: 606c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(true, resultTy); 6072de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 6082de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LT: 6092de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GT: 610c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(false, resultTy); 611eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 612eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 613eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 614eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose switch (lhs.getSubKind()) { 615eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose default: 616b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Ordering not implemented for this Loc."); 617eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 618eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose case loc::GotoLabelKind: 619eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // The only thing we know about labels is that they're non-null. 620eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (rhs.isZeroConstant()) { 621eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose switch (op) { 622eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose default: 623eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose break; 6242de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Sub: 6259f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong Wan return evalCastFromLoc(lhs, resultTy); 6262de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 6272de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LE: 6282de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LT: 629c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(false, resultTy); 6302de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 6312de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GT: 6322de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GE: 633c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(true, resultTy); 634eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 635eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 636eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // There may be two labels for the same location, and a function region may 637eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // have the same address as a label at the start of the function (depending 638eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // on the ABI). 639eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // FIXME: we can probably do a comparison against other MemRegions, though. 640eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // FIXME: is there a way to tell if two labels refer to the same location? 641eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 642eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 643eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose case loc::ConcreteIntKind: { 644eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // If one of the operands is a symbol and the other is a constant, 645eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // build an expression for use by the constraint manager. 646eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (SymbolRef rSym = rhs.getAsLocSymbol()) { 647eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // We can only build expressions with symbols on the left, 648eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // so we need a reversible operator. 649eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (!BinaryOperator::isComparisonOp(op)) 650eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 651eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 6525251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue(); 6538569281fb7ce9b5ca164a0528b876acbb45eb989Jordan Rose op = BinaryOperator::reverseComparisonOp(op); 6548569281fb7ce9b5ca164a0528b876acbb45eb989Jordan Rose return makeNonLoc(rSym, op, lVal, resultTy); 655eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 656eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 657eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // If both operands are constants, just perform the operation. 658dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) { 6595251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie SVal ResultVal = 6605251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt); 661a339cd66be6202c6e86916f52a347d0289bf2eeaJordan Rose if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>()) 662a339cd66be6202c6e86916f52a347d0289bf2eeaJordan Rose return evalCastFromNonLoc(*Result, resultTy); 663a339cd66be6202c6e86916f52a347d0289bf2eeaJordan Rose 664a339cd66be6202c6e86916f52a347d0289bf2eeaJordan Rose assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs"); 665a339cd66be6202c6e86916f52a347d0289bf2eeaJordan Rose return UnknownVal(); 666eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 667eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 668eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Special case comparisons against NULL. 669eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // This must come after the test if the RHS is a symbol, which is used to 670eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // build constraints. The address of any non-symbolic region is guaranteed 671eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // to be non-NULL, as is any label. 6725251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>()); 673eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (lhs.isZeroConstant()) { 674eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose switch (op) { 675eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose default: 676eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose break; 6772de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 6782de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GT: 6792de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GE: 680c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(false, resultTy); 6812de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 6822de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LT: 6832de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LE: 684c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(true, resultTy); 685eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 686eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 687eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 688eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Comparing an arbitrary integer to a region or label address is 689eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // completely unknowable. 690eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 691eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 692eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose case loc::MemRegionKind: { 693dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) { 694eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // If one of the operands is a symbol and the other is a constant, 695eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // build an expression for use by the constraint manager. 6963aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (SymbolRef lSym = lhs.getAsLocSymbol(true)) 697eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy); 698eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 699eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Special case comparisons to NULL. 700eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // This must come after the test if the LHS is a symbol, which is used to 701eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // build constraints. The address of any non-symbolic region is guaranteed 702eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // to be non-NULL. 703eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (rInt->isZeroConstant()) { 7043aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (op == BO_Sub) 7059f8862aa64300ef97b8fe85034ee93bbc03e3b7bZhanyong Wan return evalCastFromLoc(lhs, resultTy); 7063aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose 7073aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose if (BinaryOperator::isComparisonOp(op)) { 7083aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose QualType boolType = getContext().BoolTy; 7093aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>(); 7103aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>(); 7113aa6f431897edf5fec32cbede8fcddbfb8fa16f7Jordan Rose return evalBinOpNN(state, op, l, r, resultTy); 712eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 713eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 714eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 715eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Comparing a region to an arbitrary integer is completely unknowable. 716eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 717eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 718eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 719eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Get both values as regions, if possible. 720eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose const MemRegion *LeftMR = lhs.getAsRegion(); 721eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose assert(LeftMR && "MemRegionKind SVal doesn't have a region!"); 722eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 723eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose const MemRegion *RightMR = rhs.getAsRegion(); 724eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (!RightMR) 725eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // The RHS is probably a label, which in theory could address a region. 726eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // FIXME: we can probably make a more useful statement about non-code 727eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // regions, though. 728eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 729eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 730eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose const MemRegion *LeftBase = LeftMR->getBaseRegion(); 731eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose const MemRegion *RightBase = RightMR->getBaseRegion(); 7328958efacf8d52918cfe624116338bec62312582dJordan Rose const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace(); 7338958efacf8d52918cfe624116338bec62312582dJordan Rose const MemSpaceRegion *RightMS = RightBase->getMemorySpace(); 7348958efacf8d52918cfe624116338bec62312582dJordan Rose const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion(); 735e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks 736e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // If the two regions are from different known memory spaces they cannot be 737e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // equal. Also, assume that no symbolic region (whose memory space is 738e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // unknown) is on the stack. 739e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks if (LeftMS != RightMS && 740e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks ((LeftMS != UnknownMS && RightMS != UnknownMS) || 741e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) { 742eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose switch (op) { 743eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose default: 744eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 7452de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 746c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(false, resultTy); 7472de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 748c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(true, resultTy); 749eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 750eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 751eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 752e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // If both values wrap regions, see if they're from different base regions. 753e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // Note, heap base symbolic regions are assumed to not alias with 754e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // each other; for example, we assume that malloc returns different address 755e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks // on each invocation. 756e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks if (LeftBase != RightBase && 757e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) || 758783f0087ecb5af27d2f8caed7d6b904797c3d752Anna Zaks (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){ 759a99f874bf2ade1e32f0feda7d5b8211171440f02Ted Kremenek switch (op) { 760e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks default: 761e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks return UnknownVal(); 762e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks case BO_EQ: 763e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks return makeTruthVal(false, resultTy); 764e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks case BO_NE: 765e17fdb2d5dbf0ffefd417587003eebbe5baf5984Anna Zaks return makeTruthVal(true, resultTy); 766a99f874bf2ade1e32f0feda7d5b8211171440f02Ted Kremenek } 767a99f874bf2ade1e32f0feda7d5b8211171440f02Ted Kremenek } 768eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 7694e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Handle special cases for when both regions are element regions. 7704e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR); 7714e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR); 7724e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (RightER && LeftER) { 773eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Next, see if the two ERs have the same super-region and matching types. 774eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // FIXME: This should do something useful even if the types don't match, 775eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // though if both indexes are constant the RegionRawOffset path will 776eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // give the correct answer. 777eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (LeftER->getSuperRegion() == RightER->getSuperRegion() && 778eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose LeftER->getElementType() == RightER->getElementType()) { 779eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Get the left index and cast it to the correct type. 780eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // If the index is unknown or undefined, bail out here. 781eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose SVal LeftIndexVal = LeftER->getIndex(); 782dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>(); 783eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (!LeftIndex) 784eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 7859c0466603f2051fec9270686dfcd270630e62530Ted Kremenek LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy); 7865251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie LeftIndex = LeftIndexVal.getAs<NonLoc>(); 787eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (!LeftIndex) 788eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 789eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 790eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Do the same for the right index. 791eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose SVal RightIndexVal = RightER->getIndex(); 792dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>(); 793eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (!RightIndex) 794eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 7959c0466603f2051fec9270686dfcd270630e62530Ted Kremenek RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy); 7965251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie RightIndex = RightIndexVal.getAs<NonLoc>(); 797eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose if (!RightIndex) 798eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 799eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 800eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // Actually perform the operation. 8019c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed Kremenek // evalBinOpNN expects the two indexes to already be the right type. 8029c14953d0c84f7cf5adfb4cd3c0f05a9b1723c1cTed Kremenek return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy); 803eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 8044e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks } 805eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 8064e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Special handling of the FieldRegions, even with symbolic offsets. 8074e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR); 8084e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR); 8094e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (RightFR && LeftFR) { 8104e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy, 8114e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks *this); 8124e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks if (!R.isUnknown()) 8134e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks return R; 8144e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks } 815eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 8164e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks // Compare the regions using the raw offsets. 8174e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks RegionOffset LeftOffset = LeftMR->getAsOffset(); 8184e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks RegionOffset RightOffset = RightMR->getAsOffset(); 819eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 8206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (LeftOffset.getRegion() != nullptr && 8214e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks LeftOffset.getRegion() == RightOffset.getRegion() && 8224e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) { 8234e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks int64_t left = LeftOffset.getOffset(); 8244e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks int64_t right = RightOffset.getOffset(); 8254e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks 8264e9179a3d0ec612a4d540281020b200254348a6bAnna Zaks switch (op) { 827eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose default: 828eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 8292de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LT: 830c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(left < right, resultTy); 8312de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GT: 832c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(left > right, resultTy); 8332de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_LE: 834c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(left <= right, resultTy); 8352de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_GE: 836c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(left >= right, resultTy); 8372de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_EQ: 838c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(left == right, resultTy); 8392de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_NE: 840c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return makeTruthVal(left != right, resultTy); 841eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 842eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 843eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose 8448958efacf8d52918cfe624116338bec62312582dJordan Rose // At this point we're not going to get a good answer, but we can try 8458958efacf8d52918cfe624116338bec62312582dJordan Rose // conjuring an expression instead. 8468958efacf8d52918cfe624116338bec62312582dJordan Rose SymbolRef LHSSym = lhs.getAsLocSymbol(); 8478958efacf8d52918cfe624116338bec62312582dJordan Rose SymbolRef RHSSym = rhs.getAsLocSymbol(); 8488958efacf8d52918cfe624116338bec62312582dJordan Rose if (LHSSym && RHSSym) 8498958efacf8d52918cfe624116338bec62312582dJordan Rose return makeNonLoc(LHSSym, op, RHSSym, resultTy); 8508958efacf8d52918cfe624116338bec62312582dJordan Rose 851eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose // If we get here, we have no way of comparing the regions. 852eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose return UnknownVal(); 853eac4a00e1d93aa963903031ed76425c231f0f0b9Jordy Rose } 854e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek } 855e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 856e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek 8578bef8238181a30e52dea380789a7e2d760eac532Ted KremenekSVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, 858e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek BinaryOperator::Opcode op, 8591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Loc lhs, NonLoc rhs, QualType resultTy) { 860f4af9d37510320f5d9b415020440926528900eefJordan Rose assert(!BinaryOperator::isComparisonOp(op) && 861f4af9d37510320f5d9b415020440926528900eefJordan Rose "arguments to comparison ops must be of the same type"); 862f4af9d37510320f5d9b415020440926528900eefJordan Rose 863a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek // Special case: rhs is a zero constant. 864a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek if (rhs.isZeroConstant()) 865a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek return lhs; 866a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek 86756af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek // We are dealing with pointer arithmetic. 86856af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek 86956af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek // Handle pointer arithmetic on constant values. 870dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) { 871dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) { 87256af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek const llvm::APSInt &leftI = lhsInt->getValue(); 87356af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek assert(leftI.isUnsigned()); 87456af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true); 87556af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek 87656af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek // Convert the bitwidth of rightI. This should deal with overflow 87756af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek // since we are dealing with concrete values. 8789f71a8f4c7a182a5236da9e747d57cc1d1bd24c2Jay Foad rightI = rightI.extOrTrunc(leftI.getBitWidth()); 87956af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek 88056af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek // Offset the increment by the pointer size. 88156af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true); 88256af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek rightI *= Multiplicand; 88356af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek 88456af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek // Compute the adjusted pointer. 88556af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek switch (op) { 88656af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek case BO_Add: 88756af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek rightI = leftI + rightI; 88856af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek break; 88956af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek case BO_Sub: 89056af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek rightI = leftI - rightI; 89156af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek break; 89256af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek default: 89356af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek llvm_unreachable("Invalid pointer arithmetic operation"); 89456af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek } 895c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek return loc::ConcreteInt(getBasicValueFactory().getValue(rightI)); 89656af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek } 89756af4462781d2fcd30dcf9a742cb66400e5e55b7Ted Kremenek } 8981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 899a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek // Handle cases where 'lhs' is a region. 900a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek if (const MemRegion *region = lhs.getAsRegion()) { 9015251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie rhs = convertToArrayIndex(rhs).castAs<NonLoc>(); 902a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek SVal index = UnknownVal(); 9036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const MemRegion *superR = nullptr; 904a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek QualType elementType; 905a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek 906a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) { 9073bab50b802f402b7020aeb3ba6cec90bb149678cTed Kremenek assert(op == BO_Add || op == BO_Sub); 9083bab50b802f402b7020aeb3ba6cec90bb149678cTed Kremenek index = evalBinOpNN(state, op, elemReg->getIndex(), rhs, 909a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek getArrayIndexType()); 910a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek superR = elemReg->getSuperRegion(); 911a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek elementType = elemReg->getElementType(); 912a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek } 913a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek else if (isa<SubRegion>(region)) { 914a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek superR = region; 915a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek index = rhs; 9164e45dba1c0234eec7b7c348dbbf568c5ac9fc471Jordan Rose if (resultTy->isAnyPointerType()) 9174e45dba1c0234eec7b7c348dbbf568c5ac9fc471Jordan Rose elementType = resultTy->getPointeeType(); 918a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek } 919a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek 920dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) { 921a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV, 922a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek superR, getContext())); 923a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek } 924a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek } 925a6b0b96e5376cd9cf182a3e240e0537feed43cdeTed Kremenek return UnknownVal(); 926e8391728af4ce37c9c505be6efee6d2a5f926902Ted Kremenek} 92732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 9288bef8238181a30e52dea380789a7e2d760eac532Ted Kremenekconst llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, 92932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose SVal V) { 93032f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (V.isUnknownOrUndef()) 9316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 93232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 933dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>()) 93432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return &X->getValue(); 93532f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 936dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>()) 93732f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose return &X->getValue(); 93832f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 93932f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose if (SymbolRef Sym = V.getAsSymbol()) 94047cbd0f3892c7965cf16a58393f9f17a22d4d4d9Ted Kremenek return state->getConstraintManager().getSymVal(state, Sym); 94132f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose 94232f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose // FIXME: Add support for SymExprs. 9436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 94432f2656b90900ac04c4b50e87c16749d0ceb9ef2Jordy Rose} 945