From 554bcb69c2d785a011a30e7db87a36a87fe7db10 Mon Sep 17 00:00:00 2001
From: dim <dim@FreeBSD.org>
Date: Wed, 15 Aug 2012 20:02:54 +0000
Subject: Vendor import of clang trunk r161861:
http://llvm.org/svn/llvm-project/cfe/trunk@161861
---
lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp | 338 ++++++++++++--------------
1 file changed, 159 insertions(+), 179 deletions(-)
(limited to 'lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp')
diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
index d0558f1..ad58a07 100644
--- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -11,6 +11,7 @@
//
//===----------------------------------------------------------------------===//
+#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
@@ -106,9 +107,7 @@ SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
return UnknownVal();
llvm::APSInt i = cast<nonloc::ConcreteInt>(val).getValue();
- i.setIsUnsigned(castTy->isUnsignedIntegerOrEnumerationType() ||
- Loc::isLocType(castTy));
- i = i.extOrTrunc(Context.getTypeSize(castTy));
+ BasicVals.getAPSIntType(castTy).apply(i);
if (isLocType)
return makeIntLocVal(i);
@@ -139,9 +138,7 @@ SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
return makeLocAsInteger(val, BitWidth);
llvm::APSInt i = cast<loc::ConcreteInt>(val).getValue();
- i.setIsUnsigned(castTy->isUnsignedIntegerOrEnumerationType() ||
- Loc::isLocType(castTy));
- i = i.extOrTrunc(BitWidth);
+ BasicVals.getAPSIntType(castTy).apply(i);
return makeIntVal(i);
}
@@ -272,14 +269,40 @@ SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy);
// If we reach this point, the expression cannot be simplified.
- // Make a SymbolVal for the entire expression.
- return makeNonLoc(LHS, op, RHS, resultTy);
+ // Make a SymbolVal for the entire expression, after converting the RHS.
+ const llvm::APSInt *ConvertedRHS = &RHS;
+ if (BinaryOperator::isComparisonOp(op)) {
+ // We're looking for a type big enough to compare the symbolic value
+ // with the given constant.
+ // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
+ ASTContext &Ctx = getContext();
+ QualType SymbolType = LHS->getType(Ctx);
+ uint64_t ValWidth = RHS.getBitWidth();
+ uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
+
+ if (ValWidth < TypeWidth) {
+ // If the value is too small, extend it.
+ ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
+ } else if (ValWidth == TypeWidth) {
+ // If the value is signed but the symbol is unsigned, do the comparison
+ // in unsigned space. [C99 6.3.1.8]
+ // (For the opposite case, the value is already unsigned.)
+ 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;
+
// Handle trivial case where left-side and right-side are the same.
if (lhs == rhs)
switch (op) {
@@ -304,7 +327,7 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
while (1) {
switch (lhs.getSubKind()) {
default:
- return makeGenericVal(state, op, lhs, rhs, resultTy);
+ return makeSymExprValNN(state, op, lhs, rhs, resultTy);
case nonloc::LocAsIntegerKind: {
Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc();
switch (rhs.getSubKind()) {
@@ -315,8 +338,7 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
case nonloc::ConcreteIntKind: {
// Transform the integer into a location and compare.
llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue();
- i.setIsUnsigned(true);
- i = i.extOrTrunc(Context.getTypeSize(Context.VoidPtrTy));
+ BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
}
default:
@@ -327,86 +349,78 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
return makeTruthVal(true, resultTy);
default:
// This case also handles pointer arithmetic.
- return makeGenericVal(state, op, lhs, rhs, resultTy);
+ return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
}
}
}
case nonloc::ConcreteIntKind: {
- const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs);
-
- // Is the RHS a symbol we can simplify?
- // FIXME: This was mostly copy/pasted from the LHS-is-a-symbol case.
- if (const nonloc::SymbolVal *srhs = dyn_cast<nonloc::SymbolVal>(&rhs)) {
- SymbolRef RSym = srhs->getSymbol();
- if (RSym->getType(Context)->isIntegerType()) {
- if (const llvm::APSInt *Constant = state->getSymVal(RSym)) {
- // The symbol evaluates to a constant.
- const llvm::APSInt *rhs_I;
- if (BinaryOperator::isRelationalOp(op))
- rhs_I = &BasicVals.Convert(lhsInt.getValue(), *Constant);
- else
- rhs_I = &BasicVals.Convert(resultTy, *Constant);
-
- rhs = nonloc::ConcreteInt(*rhs_I);
- }
+ llvm::APSInt LHSValue = cast<nonloc::ConcreteInt>(lhs).getValue();
+
+ // If we're dealing with two known constants, just perform the operation.
+ if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
+ llvm::APSInt RHSValue = *KnownRHSValue;
+ if (BinaryOperator::isComparisonOp(op)) {
+ // We're looking for a type big enough to compare the two values.
+ // FIXME: This is not correct. char + short will result in a promotion
+ // to int. Unfortunately we have lost types by this point.
+ 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);
}
- }
- if (isa<nonloc::ConcreteInt>(rhs)) {
- return lhsInt.evalBinOp(*this, op, cast<nonloc::ConcreteInt>(rhs));
- } else {
- const llvm::APSInt& lhsValue = lhsInt.getValue();
-
- // Swap the left and right sides and flip the operator if doing so
- // allows us to better reason about the expression (this is a form
- // of expression canonicalization).
- // While we're at it, catch some special cases for non-commutative ops.
- NonLoc tmp = rhs;
- rhs = lhs;
- lhs = tmp;
+ const llvm::APSInt *Result =
+ BasicVals.evalAPSInt(op, LHSValue, RHSValue);
+ if (!Result)
+ return UndefinedVal();
- switch (op) {
- case BO_LT:
- case BO_GT:
- case BO_LE:
- case BO_GE:
- op = ReverseComparison(op);
- continue;
- case BO_EQ:
- case BO_NE:
- case BO_Add:
- case BO_Mul:
- case BO_And:
- case BO_Xor:
- case BO_Or:
- continue;
- case BO_Shr:
- if (lhsValue.isAllOnesValue() && lhsValue.isSigned())
- // At this point lhs and rhs have been swapped.
- return rhs;
- // FALL-THROUGH
- case BO_Shl:
- if (lhsValue == 0)
- // At this point lhs and rhs have been swapped.
- return rhs;
- return makeGenericVal(state, op, rhs, lhs, resultTy);
- default:
- return makeGenericVal(state, op, rhs, lhs, resultTy);
- }
+ return nonloc::ConcreteInt(*Result);
+ }
+
+ // Swap the left and right sides and flip the operator if doing so
+ // allows us to better reason about the expression (this is a form
+ // of expression canonicalization).
+ // While we're at it, catch some special cases for non-commutative ops.
+ switch (op) {
+ case BO_LT:
+ case BO_GT:
+ case BO_LE:
+ case BO_GE:
+ op = ReverseComparison(op);
+ // FALL-THROUGH
+ 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:
+ // (~0)>>a
+ if (LHSValue.isAllOnesValue() && LHSValue.isSigned())
+ return evalCastFromNonLoc(lhs, resultTy);
+ // FALL-THROUGH
+ case BO_Shl:
+ // 0<<a and 0>>a
+ 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: {
- nonloc::SymbolVal *selhs = cast<nonloc::SymbolVal>(&lhs);
+ // We only handle LHS as simple symbols or SymIntExprs.
+ SymbolRef Sym = cast<nonloc::SymbolVal>(lhs).getSymbol();
// LHS is a symbolic expression.
- if (selhs->isExpression()) {
-
- // Only handle LHS of the form "$sym op constant", at least for now.
- const SymIntExpr *symIntExpr =
- dyn_cast<SymIntExpr>(selhs->getSymbol());
-
- if (!symIntExpr)
- return makeGenericVal(state, op, lhs, rhs, resultTy);
+ if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
// Is this a logical not? (!x is represented as x == 0.)
if (op == BO_EQ && rhs.isZeroConstant()) {
@@ -452,95 +466,57 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
}
// For now, only handle expressions whose RHS is a constant.
- const nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs);
- if (!rhsInt)
- return makeGenericVal(state, op, lhs, rhs, resultTy);
-
- // If both the LHS and the current expression are additive,
- // fold their constants.
- if (BinaryOperator::isAdditiveOp(op)) {
- BinaryOperator::Opcode lop = symIntExpr->getOpcode();
- if (BinaryOperator::isAdditiveOp(lop)) {
- // resultTy may not be the best type to convert to, but it's
- // probably the best choice in expressions with mixed type
- // (such as x+1U+2LL). The rules for implicit conversions should
- // choose a reasonable type to preserve the expression, and will
- // at least match how the value is going to be used.
- const llvm::APSInt &first =
- BasicVals.Convert(resultTy, symIntExpr->getRHS());
- const llvm::APSInt &second =
- BasicVals.Convert(resultTy, rhsInt->getValue());
- const llvm::APSInt *newRHS;
- if (lop == op)
- newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
- else
- newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
- return MakeSymIntVal(symIntExpr->getLHS(), lop, *newRHS, resultTy);
- }
- }
-
- // Otherwise, make a SymbolVal out of the expression.
- return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy);
-
- // LHS is a simple symbol (not a symbolic expression).
- } else {
- nonloc::SymbolVal *slhs = cast<nonloc::SymbolVal>(&lhs);
- SymbolRef Sym = slhs->getSymbol();
- QualType lhsType = Sym->getType(Context);
-
- // The conversion type is usually the result type, but not in the case
- // of relational expressions.
- QualType conversionType = resultTy;
- if (BinaryOperator::isRelationalOp(op))
- conversionType = lhsType;
-
- // Does the symbol simplify to a constant? If so, "fold" the constant
- // by setting 'lhs' to a ConcreteInt and try again.
- if (lhsType->isIntegerType())
- if (const llvm::APSInt *Constant = state->getSymVal(Sym)) {
- // The symbol evaluates to a constant. If necessary, promote the
- // folded constant (LHS) to the result type.
- const llvm::APSInt &lhs_I = BasicVals.Convert(conversionType,
- *Constant);
- lhs = nonloc::ConcreteInt(lhs_I);
-
- // Also promote the RHS (if necessary).
-
- // For shifts, it is not necessary to promote the RHS.
- if (BinaryOperator::isShiftOp(op))
+ if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
+ // If both the LHS and the current expression are additive,
+ // fold their constants and try again.
+ if (BinaryOperator::isAdditiveOp(op)) {
+ BinaryOperator::Opcode lop = symIntExpr->getOpcode();
+ if (BinaryOperator::isAdditiveOp(lop)) {
+ // Convert the two constants to a common type, then combine them.
+
+ // resultTy may not be the best type to convert to, but it's
+ // probably the best choice in expressions with mixed type
+ // (such as x+1U+2LL). The rules for implicit conversions should
+ // choose a reasonable type to preserve the expression, and will
+ // at least match how the value is going to be used.
+ 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;
-
- // Other operators: do an implicit conversion. This shouldn't be
- // necessary once we support truncation/extension of symbolic values.
- if (nonloc::ConcreteInt *rhs_I = dyn_cast<nonloc::ConcreteInt>(&rhs)){
- rhs = nonloc::ConcreteInt(BasicVals.Convert(conversionType,
- rhs_I->getValue()));
}
-
- continue;
}
- // Is the RHS a symbol we can simplify?
- if (const nonloc::SymbolVal *srhs = dyn_cast<nonloc::SymbolVal>(&rhs)) {
- SymbolRef RSym = srhs->getSymbol();
- if (RSym->getType(Context)->isIntegerType()) {
- if (const llvm::APSInt *Constant = state->getSymVal(RSym)) {
- // The symbol evaluates to a constant.
- const llvm::APSInt &rhs_I = BasicVals.Convert(conversionType,
- *Constant);
- rhs = nonloc::ConcreteInt(rhs_I);
- }
- }
+ // Otherwise, make a SymIntExpr out of the expression.
+ return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
}
- if (isa<nonloc::ConcreteInt>(rhs)) {
- return MakeSymIntVal(slhs->getSymbol(), op,
- cast<nonloc::ConcreteInt>(rhs).getValue(),
- resultTy);
+
+ } else if (isa<SymbolData>(Sym)) {
+ // Does the symbol simplify to a constant? If so, "fold" the constant
+ // by setting 'lhs' to a ConcreteInt and try again.
+ if (const llvm::APSInt *Constant = state->getSymVal(Sym)) {
+ lhs = nonloc::ConcreteInt(*Constant);
+ continue;
}
- return makeGenericVal(state, op, lhs, rhs, resultTy);
+ // Is the RHS a constant?
+ if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
+ return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
}
+
+ // Give up -- this is not a symbolic expression we can handle.
+ return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
}
}
}
@@ -697,11 +673,18 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
// regions, though.
return UnknownVal();
- // If both values wrap regions, see if they're from different base regions.
+ 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 (LeftBase != RightBase &&
- !isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) {
+
+ // If the two regions are from different known memory spaces they cannot be
+ // equal. Also, assume that no symbolic region (whose memory space is
+ // unknown) is on the stack.
+ if (LeftMS != RightMS &&
+ ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
+ (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
switch (op) {
default:
return UnknownVal();
@@ -712,24 +695,20 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
}
}
- // The two regions are from the same base region. See if they're both a
- // type of region we know how to compare.
- const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
- const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
-
- // Heuristic: assume that no symbolic region (whose memory space is
- // unknown) is on the stack.
- // FIXME: we should be able to be more precise once we can do better
- // aliasing constraints for symbolic regions, but this is a reasonable,
- // albeit unsound, assumption that holds most of the time.
- if (isa<StackSpaceRegion>(LeftMS) ^ isa<StackSpaceRegion>(RightMS)) {
+ // If both values wrap regions, see if they're from different base regions.
+ // Note, heap base symbolic regions are assumed to not alias with
+ // each other; for example, we assume that malloc returns different address
+ // on each invocation.
+ if (LeftBase != RightBase &&
+ ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
+ (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
switch (op) {
- default:
- break;
- case BO_EQ:
- return makeTruthVal(false, resultTy);
- case BO_NE:
- return makeTruthVal(true, resultTy);
+ default:
+ return UnknownVal();
+ case BO_EQ:
+ return makeTruthVal(false, resultTy);
+ case BO_NE:
+ return makeTruthVal(true, resultTy);
}
}
@@ -885,6 +864,7 @@ SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy);
}
}
+ return UnknownVal();
}
// We are dealing with pointer arithmetic.
--
cgit v1.1