SimpleSValBuilder.cpp [plain text]
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
using namespace clang;
using namespace ento;
namespace {
class SimpleSValBuilder : public SValBuilder {
protected:
virtual SVal dispatchCast(SVal val, QualType castTy);
virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy);
virtual SVal evalCastFromLoc(Loc val, QualType castTy);
public:
SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
ProgramStateManager &stateMgr)
: SValBuilder(alloc, context, stateMgr) {}
virtual ~SimpleSValBuilder() {}
virtual SVal evalMinus(NonLoc val);
virtual SVal evalComplement(NonLoc val);
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
NonLoc lhs, NonLoc rhs, QualType resultTy);
virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
Loc lhs, Loc rhs, QualType resultTy);
virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
Loc lhs, NonLoc rhs, QualType resultTy);
virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V);
SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
const llvm::APSInt &RHS, QualType resultTy);
};
}
SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
ASTContext &context,
ProgramStateManager &stateMgr) {
return new SimpleSValBuilder(alloc, context, stateMgr);
}
SVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) {
assert(isa<Loc>(&Val) || isa<NonLoc>(&Val));
return isa<Loc>(Val) ? evalCastFromLoc(cast<Loc>(Val), CastTy)
: evalCastFromNonLoc(cast<NonLoc>(Val), CastTy);
}
SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
bool isLocType = Loc::isLocType(castTy);
if (nonloc::LocAsInteger *LI = dyn_cast<nonloc::LocAsInteger>(&val)) {
if (isLocType)
return LI->getLoc();
unsigned castSize = Context.getTypeSize(castTy);
if (castSize == LI->getNumBits())
return val;
return makeLocAsInteger(LI->getLoc(), castSize);
}
if (const SymExpr *se = val.getAsSymbolicExpression()) {
QualType T = Context.getCanonicalType(se->getType());
if (haveSameType(T, castTy))
return val;
if (!isLocType)
return makeNonLoc(se, T, castTy);
return UnknownVal();
}
if (!isa<nonloc::ConcreteInt>(val))
return UnknownVal();
if (!isLocType && !castTy->isIntegerType())
return UnknownVal();
llvm::APSInt i = cast<nonloc::ConcreteInt>(val).getValue();
BasicVals.getAPSIntType(castTy).apply(i);
if (isLocType)
return makeIntLocVal(i);
else
return makeIntVal(i);
}
SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
if (Loc::isLocType(castTy) || castTy->isReferenceType())
return val;
if (castTy->isUnionType())
return UnknownVal();
if (castTy->isIntegerType()) {
unsigned BitWidth = Context.getTypeSize(castTy);
if (!isa<loc::ConcreteInt>(val))
return makeLocAsInteger(val, BitWidth);
llvm::APSInt i = cast<loc::ConcreteInt>(val).getValue();
BasicVals.getAPSIntType(castTy).apply(i);
return makeIntVal(i);
}
return UnknownVal();
}
SVal SimpleSValBuilder::evalMinus(NonLoc val) {
switch (val.getSubKind()) {
case nonloc::ConcreteIntKind:
return cast<nonloc::ConcreteInt>(val).evalMinus(*this);
default:
return UnknownVal();
}
}
SVal SimpleSValBuilder::evalComplement(NonLoc X) {
switch (X.getSubKind()) {
case nonloc::ConcreteIntKind:
return cast<nonloc::ConcreteInt>(X).evalComplement(*this);
default:
return UnknownVal();
}
}
static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) {
switch (op) {
default:
llvm_unreachable("Invalid opcode.");
case BO_LT: return BO_GE;
case BO_GT: return BO_LE;
case BO_LE: return BO_GT;
case BO_GE: return BO_LT;
case BO_EQ: return BO_NE;
case BO_NE: return BO_EQ;
}
}
static BinaryOperator::Opcode ReverseComparison(BinaryOperator::Opcode op) {
switch (op) {
default:
llvm_unreachable("Invalid opcode.");
case BO_LT: return BO_GT;
case BO_GT: return BO_LT;
case BO_LE: return BO_GE;
case BO_GE: return BO_LE;
case BO_EQ:
case BO_NE:
return op;
}
}
SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
BinaryOperator::Opcode op,
const llvm::APSInt &RHS,
QualType resultTy) {
bool isIdempotent = false;
switch (op) {
default:
break;
case BO_Mul:
if (RHS == 0)
return makeIntVal(0, resultTy);
else if (RHS == 1)
isIdempotent = true;
break;
case BO_Div:
if (RHS == 0)
return UndefinedVal();
else if (RHS == 1)
isIdempotent = true;
break;
case BO_Rem:
if (RHS == 0)
return UndefinedVal();
else if (RHS == 1)
return makeIntVal(0, resultTy);
break;
case BO_Add:
case BO_Sub:
case BO_Shl:
case BO_Shr:
case BO_Xor:
if (RHS == 0)
isIdempotent = true;
break;
case BO_And:
if (RHS == 0)
return makeIntVal(0, resultTy);
else if (RHS.isAllOnesValue())
isIdempotent = true;
break;
case BO_Or:
if (RHS == 0)
isIdempotent = true;
else if (RHS.isAllOnesValue()) {
const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
return nonloc::ConcreteInt(Result);
}
break;
}
if (isIdempotent)
return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy);
const llvm::APSInt *ConvertedRHS = &RHS;
if (BinaryOperator::isComparisonOp(op)) {
ASTContext &Ctx = getContext();
QualType SymbolType = LHS->getType();
uint64_t ValWidth = RHS.getBitWidth();
uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
if (ValWidth < TypeWidth) {
ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
} else if (ValWidth == TypeWidth) {
if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType())
ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
}
} else
ConvertedRHS = &BasicVals.Convert(resultTy, RHS);
return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);
}
SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
BinaryOperator::Opcode op,
NonLoc lhs, NonLoc rhs,
QualType resultTy) {
NonLoc InputLHS = lhs;
NonLoc InputRHS = rhs;
if (lhs == rhs)
switch (op) {
default:
break;
case BO_EQ:
case BO_LE:
case BO_GE:
return makeTruthVal(true, resultTy);
case BO_LT:
case BO_GT:
case BO_NE:
return makeTruthVal(false, resultTy);
case BO_Xor:
case BO_Sub:
if (resultTy->isIntegralOrEnumerationType())
return makeIntVal(0, resultTy);
return evalCastFromNonLoc(makeIntVal(0, false), resultTy);
case BO_Or:
case BO_And:
return evalCastFromNonLoc(lhs, resultTy);
}
while (1) {
switch (lhs.getSubKind()) {
default:
return makeSymExprValNN(state, op, lhs, rhs, resultTy);
case nonloc::LocAsIntegerKind: {
Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc();
switch (rhs.getSubKind()) {
case nonloc::LocAsIntegerKind:
return evalBinOpLL(state, op, lhsL,
cast<nonloc::LocAsInteger>(rhs).getLoc(),
resultTy);
case nonloc::ConcreteIntKind: {
llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue();
BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
}
default:
switch (op) {
case BO_EQ:
return makeTruthVal(false, resultTy);
case BO_NE:
return makeTruthVal(true, resultTy);
default:
return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
}
}
}
case nonloc::ConcreteIntKind: {
llvm::APSInt LHSValue = cast<nonloc::ConcreteInt>(lhs).getValue();
if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
llvm::APSInt RHSValue = *KnownRHSValue;
if (BinaryOperator::isComparisonOp(op)) {
APSIntType CompareType = std::max(APSIntType(LHSValue),
APSIntType(RHSValue));
CompareType.apply(LHSValue);
CompareType.apply(RHSValue);
} else if (!BinaryOperator::isShiftOp(op)) {
APSIntType IntType = BasicVals.getAPSIntType(resultTy);
IntType.apply(LHSValue);
IntType.apply(RHSValue);
}
const llvm::APSInt *Result =
BasicVals.evalAPSInt(op, LHSValue, RHSValue);
if (!Result)
return UndefinedVal();
return nonloc::ConcreteInt(*Result);
}
switch (op) {
case BO_LT:
case BO_GT:
case BO_LE:
case BO_GE:
op = ReverseComparison(op);
case BO_EQ:
case BO_NE:
case BO_Add:
case BO_Mul:
case BO_And:
case BO_Xor:
case BO_Or:
std::swap(lhs, rhs);
continue;
case BO_Shr:
if (LHSValue.isAllOnesValue() && LHSValue.isSigned())
return evalCastFromNonLoc(lhs, resultTy);
case BO_Shl:
if (LHSValue == 0)
return evalCastFromNonLoc(lhs, resultTy);
return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
default:
return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
}
}
case nonloc::SymbolValKind: {
SymbolRef Sym = cast<nonloc::SymbolVal>(lhs).getSymbol();
if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
if (op == BO_EQ && rhs.isZeroConstant()) {
BinaryOperator::Opcode opc = symIntExpr->getOpcode();
switch (opc) {
default:
break;
case BO_LAnd:
case BO_LOr:
llvm_unreachable("Logical operators handled by branching logic.");
case BO_Assign:
case BO_MulAssign:
case BO_DivAssign:
case BO_RemAssign:
case BO_AddAssign:
case BO_SubAssign:
case BO_ShlAssign:
case BO_ShrAssign:
case BO_AndAssign:
case BO_XorAssign:
case BO_OrAssign:
case BO_Comma:
llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
case BO_PtrMemD:
case BO_PtrMemI:
llvm_unreachable("Pointer arithmetic not handled here.");
case BO_LT:
case BO_GT:
case BO_LE:
case BO_GE:
case BO_EQ:
case BO_NE:
opc = NegateComparison(opc);
assert(symIntExpr->getType() == resultTy);
return makeNonLoc(symIntExpr->getLHS(), opc,
symIntExpr->getRHS(), resultTy);
}
}
if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
if (BinaryOperator::isAdditiveOp(op)) {
BinaryOperator::Opcode lop = symIntExpr->getOpcode();
if (BinaryOperator::isAdditiveOp(lop)) {
APSIntType IntType = BasicVals.getAPSIntType(resultTy);
const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
const llvm::APSInt &second = IntType.convert(*RHSValue);
const llvm::APSInt *newRHS;
if (lop == op)
newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
else
newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
assert(newRHS && "Invalid operation despite common type!");
rhs = nonloc::ConcreteInt(*newRHS);
lhs = nonloc::SymbolVal(symIntExpr->getLHS());
op = lop;
continue;
}
}
return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
}
} else if (isa<SymbolData>(Sym)) {
if (const llvm::APSInt *Constant = state->getConstraintManager()
.getSymVal(state, Sym)) {
lhs = nonloc::ConcreteInt(*Constant);
continue;
}
if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
}
return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
}
}
}
}
SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
BinaryOperator::Opcode op,
Loc lhs, Loc rhs,
QualType resultTy) {
if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
return UnknownVal();
if (lhs == rhs) {
switch (op) {
default:
llvm_unreachable("Unimplemented operation for two identical values");
case BO_Sub:
return makeZeroVal(resultTy);
case BO_EQ:
case BO_LE:
case BO_GE:
return makeTruthVal(true, resultTy);
case BO_NE:
case BO_LT:
case BO_GT:
return makeTruthVal(false, resultTy);
}
}
switch (lhs.getSubKind()) {
default:
llvm_unreachable("Ordering not implemented for this Loc.");
case loc::GotoLabelKind:
if (rhs.isZeroConstant()) {
switch (op) {
default:
break;
case BO_Sub:
return evalCastFromLoc(lhs, resultTy);
case BO_EQ:
case BO_LE:
case BO_LT:
return makeTruthVal(false, resultTy);
case BO_NE:
case BO_GT:
case BO_GE:
return makeTruthVal(true, resultTy);
}
}
return UnknownVal();
case loc::ConcreteIntKind: {
if (SymbolRef rSym = rhs.getAsLocSymbol()) {
if (!BinaryOperator::isComparisonOp(op))
return UnknownVal();
const llvm::APSInt &lVal = cast<loc::ConcreteInt>(lhs).getValue();
return makeNonLoc(rSym, ReverseComparison(op), lVal, resultTy);
}
if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) {
SVal ResultVal = cast<loc::ConcreteInt>(lhs).evalBinOp(BasicVals, op,
*rInt);
if (Loc *Result = dyn_cast<Loc>(&ResultVal))
return evalCastFromLoc(*Result, resultTy);
else
return UnknownVal();
}
assert(isa<loc::MemRegionVal>(rhs) || isa<loc::GotoLabel>(rhs));
if (lhs.isZeroConstant()) {
switch (op) {
default:
break;
case BO_EQ:
case BO_GT:
case BO_GE:
return makeTruthVal(false, resultTy);
case BO_NE:
case BO_LT:
case BO_LE:
return makeTruthVal(true, resultTy);
}
}
return UnknownVal();
}
case loc::MemRegionKind: {
if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) {
if (SymbolRef lSym = lhs.getAsLocSymbol())
return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
if (rInt->isZeroConstant()) {
switch (op) {
default:
break;
case BO_Sub:
return evalCastFromLoc(lhs, resultTy);
case BO_EQ:
case BO_LT:
case BO_LE:
return makeTruthVal(false, resultTy);
case BO_NE:
case BO_GT:
case BO_GE:
return makeTruthVal(true, resultTy);
}
}
return UnknownVal();
}
const MemRegion *LeftMR = lhs.getAsRegion();
assert(LeftMR && "MemRegionKind SVal doesn't have a region!");
const MemRegion *RightMR = rhs.getAsRegion();
if (!RightMR)
return UnknownVal();
const MemSpaceRegion *LeftMS = LeftMR->getMemorySpace();
const MemSpaceRegion *RightMS = RightMR->getMemorySpace();
const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
const MemRegion *LeftBase = LeftMR->getBaseRegion();
const MemRegion *RightBase = RightMR->getBaseRegion();
if (LeftMS != RightMS &&
((LeftMS != UnknownMS && RightMS != UnknownMS) ||
(isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
switch (op) {
default:
return UnknownVal();
case BO_EQ:
return makeTruthVal(false, resultTy);
case BO_NE:
return makeTruthVal(true, resultTy);
}
}
if (LeftBase != RightBase &&
((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
(isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
switch (op) {
default:
return UnknownVal();
case BO_EQ:
return makeTruthVal(false, resultTy);
case BO_NE:
return makeTruthVal(true, resultTy);
}
}
if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) {
const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
if (!RightER)
return UnknownVal();
if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
LeftER->getElementType() == RightER->getElementType()) {
SVal LeftIndexVal = LeftER->getIndex();
NonLoc *LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal);
if (!LeftIndex)
return UnknownVal();
LeftIndexVal = evalCastFromNonLoc(*LeftIndex, resultTy);
LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal);
if (!LeftIndex)
return UnknownVal();
SVal RightIndexVal = RightER->getIndex();
NonLoc *RightIndex = dyn_cast<NonLoc>(&RightIndexVal);
if (!RightIndex)
return UnknownVal();
RightIndexVal = evalCastFromNonLoc(*RightIndex, resultTy);
RightIndex = dyn_cast<NonLoc>(&RightIndexVal);
if (!RightIndex)
return UnknownVal();
return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
}
RegionRawOffset LeftOffset = LeftER->getAsArrayOffset();
RegionRawOffset RightOffset = RightER->getAsArrayOffset();
if (LeftOffset.getRegion() != NULL &&
LeftOffset.getRegion() == RightOffset.getRegion()) {
CharUnits left = LeftOffset.getOffset();
CharUnits right = RightOffset.getOffset();
switch (op) {
default:
return UnknownVal();
case BO_LT:
return makeTruthVal(left < right, resultTy);
case BO_GT:
return makeTruthVal(left > right, resultTy);
case BO_LE:
return makeTruthVal(left <= right, resultTy);
case BO_GE:
return makeTruthVal(left >= right, resultTy);
case BO_EQ:
return makeTruthVal(left == right, resultTy);
case BO_NE:
return makeTruthVal(left != right, resultTy);
}
}
return UnknownVal();
}
if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) {
if (!BinaryOperator::isComparisonOp(op))
return UnknownVal();
const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
if (!RightFR)
return UnknownVal();
if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
return UnknownVal();
const FieldDecl *LeftFD = LeftFR->getDecl();
const FieldDecl *RightFD = RightFR->getDecl();
const RecordDecl *RD = LeftFD->getParent();
if (RD != RightFD->getParent())
return UnknownVal();
if (op == BO_EQ)
return makeTruthVal(false, resultTy);
if (op == BO_NE)
return makeTruthVal(true, resultTy);
bool leftFirst = (op == BO_LT || op == BO_LE);
for (RecordDecl::field_iterator I = RD->field_begin(),
E = RD->field_end(); I!=E; ++I) {
if (*I == LeftFD)
return makeTruthVal(leftFirst, resultTy);
if (*I == RightFD)
return makeTruthVal(!leftFirst, resultTy);
}
llvm_unreachable("Fields not found in parent record's definition");
}
return UnknownVal();
}
}
}
SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
BinaryOperator::Opcode op,
Loc lhs, NonLoc rhs, QualType resultTy) {
if (rhs.isZeroConstant())
return lhs;
if (BinaryOperator::isComparisonOp(op)) {
if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
const llvm::APSInt *x = &rhsInt->getValue();
ASTContext &ctx = Context;
if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) {
if (x->isSigned())
x = &getBasicValueFactory().getValue(*x, true);
return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy);
}
}
return UnknownVal();
}
if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
if (loc::ConcreteInt *lhsInt = dyn_cast<loc::ConcreteInt>(&lhs)) {
const llvm::APSInt &leftI = lhsInt->getValue();
assert(leftI.isUnsigned());
llvm::APSInt rightI(rhsInt->getValue(), true);
rightI = rightI.extOrTrunc(leftI.getBitWidth());
llvm::APSInt Multiplicand(rightI.getBitWidth(), true);
rightI *= Multiplicand;
switch (op) {
case BO_Add:
rightI = leftI + rightI;
break;
case BO_Sub:
rightI = leftI - rightI;
break;
default:
llvm_unreachable("Invalid pointer arithmetic operation");
}
return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
}
}
if (const MemRegion *region = lhs.getAsRegion()) {
rhs = cast<NonLoc>(convertToArrayIndex(rhs));
SVal index = UnknownVal();
const MemRegion *superR = 0;
QualType elementType;
if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
assert(op == BO_Add || op == BO_Sub);
index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
getArrayIndexType());
superR = elemReg->getSuperRegion();
elementType = elemReg->getElementType();
}
else if (isa<SubRegion>(region)) {
superR = region;
index = rhs;
if (resultTy->isAnyPointerType())
elementType = resultTy->getPointeeType();
}
if (NonLoc *indexV = dyn_cast<NonLoc>(&index)) {
return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
superR, getContext()));
}
}
return UnknownVal();
}
const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
SVal V) {
if (V.isUnknownOrUndef())
return NULL;
if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V))
return &X->getValue();
if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V))
return &X->getValue();
if (SymbolRef Sym = V.getAsSymbol())
return state->getConstraintManager().getSymVal(state, Sym);
return NULL;
}