diff options
Diffstat (limited to 'lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp')
| -rw-r--r-- | lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp | 301 |
1 files changed, 136 insertions, 165 deletions
diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index 7aa36821f2..33d0d96564 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -272,8 +272,31 @@ 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, @@ -335,81 +358,80 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, } } 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::isComparisonOp(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. + uint32_t LeftWidth = LHSValue.getBitWidth(); + uint32_t RightWidth = RHSValue.getBitWidth(); + + // Based on the conversion rules of [C99 6.3.1.8] and the example + // in SemaExpr's handleIntegerConversion(). + if (LeftWidth > RightWidth) + RHSValue = RHSValue.extend(LeftWidth); + else if (LeftWidth < RightWidth) + LHSValue = LHSValue.extend(RightWidth); + else if (LHSValue.isUnsigned() != RHSValue.isUnsigned()) { + LHSValue.setIsUnsigned(true); + RHSValue.setIsUnsigned(true); } + } else if (!BinaryOperator::isShiftOp(op)) { + // FIXME: These values don't need to be persistent. + LHSValue = BasicVals.Convert(resultTy, LHSValue); + RHSValue = BasicVals.Convert(resultTy, 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 makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy); - default: - return makeSymExprValNN(state, op, InputLHS, InputRHS, 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 makeSymExprValNN(state, op, InputLHS, InputRHS, 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()) { @@ -455,114 +477,63 @@ 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 makeSymExprValNN(state, op, InputLHS, InputRHS, 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); + 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. + + // FIXME: These values don't need to be persistent. + const llvm::APSInt &first = + BasicVals.Convert(resultTy, symIntExpr->getRHS()); + const llvm::APSInt &second = + BasicVals.Convert(resultTy, *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; + } } + + // Otherwise, make a SymIntExpr out of the expression. + return MakeSymIntVal(symIntExpr, op, *RHSValue, 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(); + } else if (isa<SymbolData>(Sym)) { + // LHS is a simple symbol (not a symbolic expression). 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::isComparisonOp(op)) - conversionType = lhsType; - const llvm::APSInt *conversionPrototype = NULL; - // 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)) { - // Promote the RHS if necessary. Shift operations do not - // need their arguments to match in type, but others do. - if (!BinaryOperator::isShiftOp(op)) { - // If the RHS is a constant, we need to promote it. - if (nonloc::ConcreteInt *rhs_I = - dyn_cast<nonloc::ConcreteInt>(&rhs)) { - const llvm::APSInt &val = rhs_I->getValue(); - - // The RHS may have a better type for performing comparisons. - // Consider x == 0xF00, where x is a fully constrained char. - if (BinaryOperator::isComparisonOp(op)) { - const ASTContext &Ctx = getContext(); - unsigned width = std::max((unsigned)Ctx.getTypeSize(lhsType), - (unsigned)val.getBitWidth()); - - // Use the LHS's signedness. - bool isUnsigned = - lhsType->isUnsignedIntegerOrEnumerationType(); - - conversionPrototype = &BasicVals.getValue(val.getSExtValue(), - width, isUnsigned); - } else { - conversionPrototype = &BasicVals.Convert(resultTy, val); - } - - // Record the promoted value. - rhs = nonloc::ConcreteInt(*conversionPrototype); - } - } - - // Promote the LHS constant to the appropriate type. - const llvm::APSInt &lhs_I = conversionPrototype ? - BasicVals.Convert(*conversionPrototype, *Constant) : - BasicVals.Convert(conversionType, *Constant); - lhs = nonloc::ConcreteInt(lhs_I); - - 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. - // FIXME: This may not be the proper conversion type. Consider - // x > y, where y is a fully constrained int but x is a char. - const llvm::APSInt &rhs_I = BasicVals.Convert(conversionType, - *Constant); - rhs = nonloc::ConcreteInt(rhs_I); - } - } - } - - if (nonloc::ConcreteInt *rhs_I = dyn_cast<nonloc::ConcreteInt>(&rhs)) { - return MakeSymIntVal(slhs->getSymbol(), op, - rhs_I->getValue(), resultTy); + if (const llvm::APSInt *Constant = state->getSymVal(Sym)) { + lhs = nonloc::ConcreteInt(*Constant); + continue; } - return makeSymExprValNN(state, op, InputLHS, InputRHS, 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); } } } |