diff options
Diffstat (limited to 'lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp')
| -rw-r--r-- | lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp | 341 |
1 files changed, 185 insertions, 156 deletions
diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index bd63ecf..d0558f1 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -20,6 +20,7 @@ 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); @@ -31,16 +32,16 @@ public: virtual SVal evalMinus(NonLoc val); virtual SVal evalComplement(NonLoc val); - virtual SVal evalBinOpNN(const ProgramState *state, BinaryOperator::Opcode op, + virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy); - virtual SVal evalBinOpLL(const ProgramState *state, BinaryOperator::Opcode op, + virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, Loc rhs, QualType resultTy); - virtual SVal evalBinOpLN(const ProgramState *state, BinaryOperator::Opcode op, + virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, NonLoc rhs, QualType resultTy); /// getKnownValue - evaluates a given SVal. If the SVal has only one possible /// (integer) value, that value is returned. Otherwise, returns NULL. - virtual const llvm::APSInt *getKnownValue(const ProgramState *state, SVal V); + virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V); SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op, const llvm::APSInt &RHS, QualType resultTy); @@ -57,6 +58,12 @@ SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, // Transfer function for Casts. //===----------------------------------------------------------------------===// +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); @@ -74,25 +81,27 @@ SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) { if (const SymExpr *se = val.getAsSymbolicExpression()) { QualType T = Context.getCanonicalType(se->getType(Context)); - if (T == Context.getCanonicalType(castTy)) - return val; - + // If types are the same or both are integers, ignore the cast. // FIXME: Remove this hack when we support symbolic truncation/extension. // HACK: If both castTy and T are integers, ignore the cast. This is // not a permanent solution. Eventually we want to precisely handle // extension/truncation of symbolic integers. This prevents us from losing // precision when we assign 'x = y' and 'y' is symbolic and x and y are // different integer types. - if (T->isIntegerType() && castTy->isIntegerType()) + if (haveSameType(T, castTy)) return val; + if (!isLocType) + return makeNonLoc(se, T, castTy); return UnknownVal(); } + // If value is a non integer constant, produce unknown. if (!isa<nonloc::ConcreteInt>(val)) return UnknownVal(); - // Only handle casts from integers to integers. + // Only handle casts from integers to integers - if val is an integer constant + // being cast to a non integer type, produce unknown. if (!isLocType && !castTy->isIntegerType()) return UnknownVal(); @@ -259,18 +268,15 @@ SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS, // Idempotent ops (like a*1) can still change the type of an expression. // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the // dirty work. - if (isIdempotent) { - if (SymbolRef LHSSym = dyn_cast<SymbolData>(LHS)) - return evalCastFromNonLoc(nonloc::SymbolVal(LHSSym), resultTy); - return evalCastFromNonLoc(nonloc::SymExprVal(LHS), resultTy); - } + if (isIdempotent) + return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy); // If we reach this point, the expression cannot be simplified. - // Make a SymExprVal for the entire thing. + // Make a SymbolVal for the entire expression. return makeNonLoc(LHS, op, RHS, resultTy); } -SVal SimpleSValBuilder::evalBinOpNN(const ProgramState *state, +SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy) { @@ -298,7 +304,7 @@ SVal SimpleSValBuilder::evalBinOpNN(const ProgramState *state, while (1) { switch (lhs.getSubKind()) { default: - return UnknownVal(); + return makeGenericVal(state, op, lhs, rhs, resultTy); case nonloc::LocAsIntegerKind: { Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc(); switch (rhs.getSubKind()) { @@ -321,94 +327,10 @@ SVal SimpleSValBuilder::evalBinOpNN(const ProgramState *state, return makeTruthVal(true, resultTy); default: // This case also handles pointer arithmetic. - return UnknownVal(); + return makeGenericVal(state, op, lhs, rhs, resultTy); } } } - case nonloc::SymExprValKind: { - nonloc::SymExprVal *selhs = cast<nonloc::SymExprVal>(&lhs); - - // Only handle LHS of the form "$sym op constant", at least for now. - const SymIntExpr *symIntExpr = - dyn_cast<SymIntExpr>(selhs->getSymbolicExpression()); - - if (!symIntExpr) - return UnknownVal(); - - // Is this a logical not? (!x is represented as x == 0.) - if (op == BO_EQ && rhs.isZeroConstant()) { - // We know how to negate certain expressions. Simplify them here. - - BinaryOperator::Opcode opc = symIntExpr->getOpcode(); - switch (opc) { - default: - // We don't know how to negate this operation. - // Just handle it as if it were a normal comparison to 0. - 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: - // Negate the comparison and make a value. - opc = NegateComparison(opc); - assert(symIntExpr->getType(Context) == resultTy); - return makeNonLoc(symIntExpr->getLHS(), opc, - symIntExpr->getRHS(), resultTy); - } - } - - // For now, only handle expressions whose RHS is a constant. - const nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs); - if (!rhsInt) - return UnknownVal(); - - // 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 SymExprVal out of the expression. - return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy); - } case nonloc::ConcreteIntKind: { const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs); @@ -467,76 +389,165 @@ SVal SimpleSValBuilder::evalBinOpNN(const ProgramState *state, if (lhsValue == 0) // At this point lhs and rhs have been swapped. return rhs; - return UnknownVal(); + return makeGenericVal(state, op, rhs, lhs, resultTy); default: - return UnknownVal(); + return makeGenericVal(state, op, rhs, lhs, resultTy); } } } case nonloc::SymbolValKind: { - 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)) - 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())); + nonloc::SymbolVal *selhs = cast<nonloc::SymbolVal>(&lhs); + + // 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); + + // Is this a logical not? (!x is represented as x == 0.) + if (op == BO_EQ && rhs.isZeroConstant()) { + // We know how to negate certain expressions. Simplify them here. + + BinaryOperator::Opcode opc = symIntExpr->getOpcode(); + switch (opc) { + default: + // We don't know how to negate this operation. + // Just handle it as if it were a normal comparison to 0. + 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: + // Negate the comparison and make a value. + opc = NegateComparison(opc); + assert(symIntExpr->getType(Context) == resultTy); + return makeNonLoc(symIntExpr->getLHS(), opc, + symIntExpr->getRHS(), resultTy); } - - 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); + // 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); } } - } - if (isa<nonloc::ConcreteInt>(rhs)) { - return MakeSymIntVal(slhs->getSymbol(), op, - cast<nonloc::ConcreteInt>(rhs).getValue(), - resultTy); - } + // Otherwise, make a SymbolVal out of the expression. + return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy); - return UnknownVal(); + // 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)) + 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); + } + } + } + + if (isa<nonloc::ConcreteInt>(rhs)) { + return MakeSymIntVal(slhs->getSymbol(), op, + cast<nonloc::ConcreteInt>(rhs).getValue(), + resultTy); + } + + return makeGenericVal(state, op, lhs, rhs, resultTy); + } } } } } // FIXME: all this logic will change if/when we have MemRegion::getLocation(). -SVal SimpleSValBuilder::evalBinOpLL(const ProgramState *state, +SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, Loc rhs, QualType resultTy) { @@ -703,6 +714,24 @@ SVal SimpleSValBuilder::evalBinOpLL(const ProgramState *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)) { + switch (op) { + default: + break; + case BO_EQ: + return makeTruthVal(false, resultTy); + case BO_NE: + return makeTruthVal(true, resultTy); + } + } // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this // ElementRegion path and the FieldRegion path below should be unified. @@ -831,7 +860,7 @@ SVal SimpleSValBuilder::evalBinOpLL(const ProgramState *state, } } -SVal SimpleSValBuilder::evalBinOpLN(const ProgramState *state, +SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, NonLoc rhs, QualType resultTy) { @@ -925,7 +954,7 @@ SVal SimpleSValBuilder::evalBinOpLN(const ProgramState *state, return UnknownVal(); } -const llvm::APSInt *SimpleSValBuilder::getKnownValue(const ProgramState *state, +const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, SVal V) { if (V.isUnknownOrUndef()) return NULL; |
