From 5344baa704f42b22d9df25c24ffbbf6b4716603b Mon Sep 17 00:00:00 2001 From: Anna Zaks Date: Mon, 5 Dec 2011 18:58:30 +0000 Subject: [PATCH] [analyzer] Unify SymbolVal and SymExprVal under a single SymbolVal class. We are going into the direction of handling SymbolData and other SymExpr uniformly, so it makes less sense to keep two different SVal classes. For example, the checkers would have to take an extra step to reason about each type separately. The classes have the same members, we were just using the SVal kind field for easy differentiation in 3 switch statements. The switch statements look more ugly now, but we can make the code more readable in other ways, for example, moving some code into separate functions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@145833 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../StaticAnalyzer/Core/PathSensitive/SVals.h | 25 +- lib/StaticAnalyzer/Core/ExprEngine.cpp | 3 +- lib/StaticAnalyzer/Core/SValBuilder.cpp | 4 +- lib/StaticAnalyzer/Core/SVals.cpp | 17 +- .../Core/SimpleConstraintManager.cpp | 53 ++-- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp | 279 +++++++++--------- 6 files changed, 180 insertions(+), 201 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h index ca9315d2ce..698a05adad 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -276,7 +276,7 @@ namespace nonloc { enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; -// TODO: Change to contain symbol data. +/// \brief Represents symbolic expression. class SymbolVal : public NonLoc { public: SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} @@ -285,32 +285,17 @@ public: return (const SymExpr*) Data; } - static inline bool classof(const SVal* V) { - return V->getBaseKind() == NonLocKind && - V->getSubKind() == SymbolValKind; - } - - static inline bool classof(const NonLoc* V) { - return V->getSubKind() == SymbolValKind; - } -}; - -class SymExprVal : public NonLoc { -public: - explicit SymExprVal(const SymExpr *SE) - : NonLoc(SymExprValKind, reinterpret_cast(SE)) {} - - const SymExpr *getSymbolicExpression() const { - return reinterpret_cast(Data); + bool isExpression() { + return !isa(getSymbol()); } static inline bool classof(const SVal* V) { return V->getBaseKind() == NonLocKind && - V->getSubKind() == SymExprValKind; + V->getSubKind() == SymbolValKind; } static inline bool classof(const NonLoc* V) { - return V->getSubKind() == SymExprValKind; + return V->getSubKind() == SymbolValKind; } }; diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index f5d26c9645..9b0e66fffb 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1665,7 +1665,8 @@ void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, const ProgramState *state = Pred->getState(); SVal V = state->getSVal(Ex); - if (nonloc::SymExprVal *SEV = dyn_cast(&V)) { + nonloc::SymbolVal *SEV = dyn_cast(&V); + if (SEV && SEV->isExpression()) { const std::pair &tags = getEagerlyAssumeTags(); diff --git a/lib/StaticAnalyzer/Core/SValBuilder.cpp b/lib/StaticAnalyzer/Core/SValBuilder.cpp index 331f5934b5..617e0ddc72 100644 --- a/lib/StaticAnalyzer/Core/SValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SValBuilder.cpp @@ -45,7 +45,7 @@ NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, // BasicValueFactory again. assert(lhs); assert(!Loc::isLocType(type)); - return nonloc::SymExprVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); + return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); } NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, @@ -53,7 +53,7 @@ NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, assert(lhs && rhs); assert(SymMgr.getType(lhs) == SymMgr.getType(rhs)); assert(!Loc::isLocType(type)); - return nonloc::SymExprVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); + return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); } diff --git a/lib/StaticAnalyzer/Core/SVals.cpp b/lib/StaticAnalyzer/Core/SVals.cpp index 6b71f184aa..4bdea1d9e1 100644 --- a/lib/StaticAnalyzer/Core/SVals.cpp +++ b/lib/StaticAnalyzer/Core/SVals.cpp @@ -98,8 +98,8 @@ SymbolRef SVal::getAsSymbol() const { if (const nonloc::SymbolVal *X = dyn_cast(this)) return X->getSymbol(); - if (const nonloc::SymExprVal *X = dyn_cast(this)) - if (SymbolRef Y = X->getSymbolicExpression()) + if (const nonloc::SymbolVal *X = dyn_cast(this)) + if (SymbolRef Y = X->getSymbol()) return Y; return getAsLocSymbol(); @@ -108,8 +108,8 @@ SymbolRef SVal::getAsSymbol() const { /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then /// return that expression. Otherwise return NULL. const SymExpr *SVal::getAsSymbolicExpression() const { - if (const nonloc::SymExprVal *X = dyn_cast(this)) - return X->getSymbolicExpression(); + if (const nonloc::SymbolVal *X = dyn_cast(this)) + return X->getSymbol(); return getAsSymbol(); } @@ -305,13 +305,8 @@ void NonLoc::dumpToStream(raw_ostream &os) const { << C.getValue().getBitWidth() << 'b'; break; } - case nonloc::SymbolValKind: - os << '$' << cast(this)->getSymbol(); - break; - case nonloc::SymExprValKind: { - const nonloc::SymExprVal& C = *cast(this); - const SymExpr *SE = C.getSymbolicExpression(); - os << SE; + case nonloc::SymbolValKind: { + os << cast(this)->getSymbol(); break; } case nonloc::LocAsIntegerKind: { diff --git a/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp b/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp index 8b7c2c1398..6fa7bb1ec5 100644 --- a/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -23,11 +23,9 @@ namespace ento { SimpleConstraintManager::~SimpleConstraintManager() {} bool SimpleConstraintManager::canReasonAbout(SVal X) const { - if (nonloc::SymExprVal *SymVal = dyn_cast(&X)) { - const SymExpr *SE = SymVal->getSymbolicExpression(); - - if (isa(SE)) - return true; + nonloc::SymbolVal *SymVal = dyn_cast(&X); + if (SymVal && SymVal->isExpression()) { + const SymExpr *SE = SymVal->getSymbol(); if (const SymIntExpr *SIE = dyn_cast(SE)) { switch (SIE->getOpcode()) { @@ -170,34 +168,33 @@ const ProgramState *SimpleConstraintManager::assumeAux(const ProgramState *state case nonloc::SymbolValKind: { nonloc::SymbolVal& SV = cast(Cond); SymbolRef sym = SV.getSymbol(); - return assumeAuxForSymbol(state, sym, Assumption); - } - - case nonloc::SymExprValKind: { - nonloc::SymExprVal V = cast(Cond); - - SymbolRef sym = V.getSymbolicExpression(); assert(sym); - // We can only simplify expressions whose RHS is an integer. - const SymIntExpr *SE = dyn_cast(sym); - if (!SE) + // Handle SymbolData. + if (!SV.isExpression()) { return assumeAuxForSymbol(state, sym, Assumption); - BinaryOperator::Opcode op = SE->getOpcode(); - // Implicitly compare non-comparison expressions to 0. - if (!BinaryOperator::isComparisonOp(op)) { - QualType T = SymMgr.getType(SE); - const llvm::APSInt &zero = BasicVals.getValue(0, T); - op = (Assumption ? BO_NE : BO_EQ); - return assumeSymRel(state, SE, op, zero); - } + // Handle symbolic expression. + } else { + // We can only simplify expressions whose RHS is an integer. + const SymIntExpr *SE = dyn_cast(sym); + if (!SE) + return assumeAuxForSymbol(state, sym, Assumption); + + BinaryOperator::Opcode op = SE->getOpcode(); + // Implicitly compare non-comparison expressions to 0. + if (!BinaryOperator::isComparisonOp(op)) { + QualType T = SymMgr.getType(SE); + const llvm::APSInt &zero = BasicVals.getValue(0, T); + op = (Assumption ? BO_NE : BO_EQ); + return assumeSymRel(state, SE, op, zero); + } + // From here on out, op is the real comparison we'll be testing. + if (!Assumption) + op = NegateComparison(op); - // From here on out, op is the real comparison we'll be testing. - if (!Assumption) - op = NegateComparison(op); - - return assumeSymRel(state, SE->getLHS(), op, SE->getRHS()); + return assumeSymRel(state, SE->getLHS(), op, SE->getRHS()); + } } case nonloc::ConcreteIntKind: { diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index 2e6f33353e..495f6f20b6 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -259,15 +259,11 @@ 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 (isa(LHS)) + if (isIdempotent) return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy); - else - return evalCastFromNonLoc(nonloc::SymExprVal(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); } @@ -326,90 +322,6 @@ SVal SimpleSValBuilder::evalBinOpNN(const ProgramState *state, } } } - case nonloc::SymExprValKind: { - nonloc::SymExprVal *selhs = cast(&lhs); - - // Only handle LHS of the form "$sym op constant", at least for now. - const SymIntExpr *symIntExpr = - dyn_cast(selhs->getSymbolicExpression()); - - if (!symIntExpr) - return generateUnknownVal(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); - } - } - - // For now, only handle expressions whose RHS is a constant. - const nonloc::ConcreteInt *rhsInt = dyn_cast(&rhs); - if (!rhsInt) - return generateUnknownVal(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 SymExprVal out of the expression. - return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy); - } case nonloc::ConcreteIntKind: { const nonloc::ConcreteInt& lhsInt = cast(lhs); @@ -475,62 +387,151 @@ SVal SimpleSValBuilder::evalBinOpNN(const ProgramState *state, } } case nonloc::SymbolValKind: { - nonloc::SymbolVal *slhs = cast(&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(&rhs)){ - rhs = nonloc::ConcreteInt(BasicVals.Convert(conversionType, - rhs_I->getValue())); + nonloc::SymbolVal *selhs = cast(&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(selhs->getSymbol()); + + if (!symIntExpr) + return generateUnknownVal(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(&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(&rhs); + if (!rhsInt) + return generateUnknownVal(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(rhs)) { - return MakeSymIntVal(slhs->getSymbol(), op, - cast(rhs).getValue(), - resultTy); - } + // Otherwise, make a SymbolVal out of the expression. + return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy); - return generateUnknownVal(state, op, lhs, rhs, resultTy); + // LHS is a simple symbol. + } else { + nonloc::SymbolVal *slhs = cast(&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(&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(&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(rhs)) { + return MakeSymIntVal(slhs->getSymbol(), op, + cast(rhs).getValue(), + resultTy); + } + + return generateUnknownVal(state, op, lhs, rhs, resultTy); + } } } } -- 2.40.0