diff --git a/clang/include/clang/StaticAnalyzer/Checkers/SValExplainer.h b/clang/include/clang/StaticAnalyzer/Checkers/SValExplainer.h --- a/clang/include/clang/StaticAnalyzer/Checkers/SValExplainer.h +++ b/clang/include/clang/StaticAnalyzer/Checkers/SValExplainer.h @@ -135,6 +135,11 @@ " (" + Visit(S->getRHS()) + ")"; } + std::string VisitUnarySymExpr(const UnarySymExpr *S) { + return std::string(UnaryOperator::getOpcodeStr(S->getOpcode())) + " (" + + Visit(S->getOperand()) + ")"; + } + // TODO: SymbolCast doesn't appear in practice. // Add the relevant code once it does. diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -585,12 +585,12 @@ static std::pair geteagerlyAssumeBinOpBifurcationTags(); - SVal evalMinus(SVal X) { - return X.isValid() ? svalBuilder.evalMinus(X.castAs()) : X; + SVal evalMinus(SVal X, QualType T) { + return X.isValid() ? svalBuilder.evalMinus(X.castAs(), T) : X; } - SVal evalComplement(SVal X) { - return X.isValid() ? svalBuilder.evalComplement(X.castAs()) : X; + SVal evalComplement(SVal X, QualType T) { + return X.isValid() ? svalBuilder.evalComplement(X.castAs(), T) : X; } ProgramStateRef handleLValueBitCast(ProgramStateRef state, const Expr *Ex, diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -120,9 +120,9 @@ SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy, QualType originalType); - virtual SVal evalMinus(NonLoc val) = 0; + virtual SVal evalMinus(NonLoc val, QualType resultTy) = 0; - virtual SVal evalComplement(NonLoc val) = 0; + virtual SVal evalComplement(NonLoc val, QualType resultTy) = 0; /// Create a new value which represents a binary expression with two non- /// location operands. @@ -153,6 +153,9 @@ SVal makeSymExprValNN(BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy); + SVal evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, + SVal operand, QualType type); + SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type); @@ -349,6 +352,9 @@ NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType type); + NonLoc makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, + QualType type); + /// Create a NonLoc value for cast. NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy); diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -309,6 +309,55 @@ } }; +/// Represents a symbolic expression involving a unary operator. +class UnarySymExpr : public SymExpr { + const SymExpr *Operand; + UnaryOperator::Opcode Op; + QualType T; + +public: + UnarySymExpr(const SymExpr *In, UnaryOperator::Opcode Op, QualType T) + : SymExpr(UnarySymExprKind), Operand(In), Op(Op), T(T) { + // Note, some unary operators are modeled as a binary operator. E.g. ++x is + // modeled as x + 1. + assert((Op == UO_Minus || Op == UO_Not) && "non-supported unary expression"); + // Unary expressions are results of arithmetic. Pointer arithmetic is not + // handled by unary expressions, but it is instead handled by applying + // sub-regions to regions. + assert(isValidTypeForSymbol(T) && "non-valid type for unary symbol"); + assert(!Loc::isLocType(T) && "unary symbol should be nonloc"); + } + + unsigned computeComplexity() const override { + if (Complexity == 0) + Complexity = 1 + Operand->computeComplexity(); + return Complexity; + } + + const SymExpr *getOperand() const { return Operand; } + UnaryOperator::Opcode getOpcode() const { return Op; } + QualType getType() const override { return T; } + + void dumpToStream(raw_ostream &os) const override; + + static void Profile(llvm::FoldingSetNodeID &ID, const SymExpr *In, + UnaryOperator::Opcode Op, QualType T) { + ID.AddInteger((unsigned)UnarySymExprKind); + ID.AddPointer(In); + ID.AddInteger(Op); + ID.Add(T); + } + + void Profile(llvm::FoldingSetNodeID &ID) override { + Profile(ID, Operand, Op, T); + } + + // Implement isa support. + static bool classof(const SymExpr *SE) { + return SE->getKind() == UnarySymExprKind; + } +}; + /// Represents a symbolic expression involving a binary operator class BinarySymExpr : public SymExpr { BinaryOperator::Opcode Op; @@ -486,6 +535,9 @@ const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t); + const UnarySymExpr *getUnarySymExpr(const SymExpr *operand, + UnaryOperator::Opcode op, QualType t); + QualType getType(const SymExpr *SE) const { return SE->getType(); } diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def @@ -33,6 +33,8 @@ #define SYMBOL_RANGE(Id, First, Last) #endif +SYMBOL(UnarySymExpr, SymExpr) + ABSTRACT_SYMBOL(BinarySymExpr, SymExpr) SYMBOL(IntSymExpr, BinarySymExpr) SYMBOL(SymIntExpr, BinarySymExpr) diff --git a/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp --- a/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp @@ -461,6 +461,14 @@ return None; } + Optional VisitUnarySymExpr(const UnarySymExpr *S) { + if (Optional Str = lookup(S)) + return Str; + if (Optional Str = Visit(S->getOperand())) + return (UnaryOperator::getOpcodeStr(S->getOpcode()) + *Str).str(); + return None; + } + Optional VisitSymbolCast(const SymbolCast *S) { if (Optional Str = lookup(S)) return Str; diff --git a/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp b/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp --- a/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp @@ -651,7 +651,8 @@ NewVal = State->getLValue(ElementType, Offset, OldVal); } else { auto &SVB = C.getSValBuilder(); - SVal NegatedOffset = SVB.evalMinus(Offset.castAs()); + SVal NegatedOffset = SVB.evalMinus(Offset.castAs(), + Offset.getType(C.getASTContext())); NewVal = State->getLValue(ElementType, NegatedOffset, OldVal); } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp --- a/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp @@ -272,7 +272,7 @@ SVal V = svalBuilder.evalCast(OrigV, T, ExTy); // Negate the result if we're treating the boolean as a signed i1 if (CastE->getCastKind() == CK_BooleanToSignedIntegral) - V = evalMinus(V); + V = evalMinus(V, T); state = state->BindExpr(CastE, LCtx, V); if (V.isUnknown() && !OrigV.isUnknown()) { state = escapeValues(state, OrigV, PSK_EscapeOther); @@ -1029,11 +1029,13 @@ llvm_unreachable("Invalid Opcode."); case UO_Not: // FIXME: Do we need to handle promotions? - state = state->BindExpr(U, LCtx, evalComplement(V.castAs())); + state = state->BindExpr( + U, LCtx, evalComplement(V.castAs(), U->getType())); break; case UO_Minus: // FIXME: Do we need to handle promotions? - state = state->BindExpr(U, LCtx, evalMinus(V.castAs())); + state = state->BindExpr(U, LCtx, + evalMinus(V.castAs(), U->getType())); break; case UO_LNot: // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." diff --git a/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp --- a/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp @@ -99,6 +99,13 @@ return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); } +NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, + QualType type) { + assert(operand); + assert(!Loc::isLocType(type)); + return nonloc::SymbolVal(SymMgr.getUnarySymExpr(operand, op, type)); +} + NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy) { assert(operand); @@ -431,6 +438,19 @@ return UnknownVal(); } +SVal SValBuilder::evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, + SVal operand, QualType type) { + auto OpN = operand.getAs(); + if (!OpN) + return UnknownVal(); + + if (opc == UO_Minus) + return evalMinus(*OpN, type); + if (opc == UO_Not) + return evalComplement(*OpN, type); + llvm_unreachable("Unexpected unary operator"); +} + SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type) { if (lhs.isUndef() || rhs.isUndef()) diff --git a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp --- a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -56,8 +56,8 @@ : SValBuilder(alloc, context, stateMgr) {} ~SimpleSValBuilder() override {} - SVal evalMinus(NonLoc val) override; - SVal evalComplement(NonLoc val) override; + SVal evalMinus(NonLoc val, QualType resultTy) override; + SVal evalComplement(NonLoc val, QualType resultTy) override; SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy) override; SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, @@ -86,19 +86,25 @@ // Transfer function for unary operators. //===----------------------------------------------------------------------===// -SVal SimpleSValBuilder::evalMinus(NonLoc val) { +SVal SimpleSValBuilder::evalMinus(NonLoc val, QualType resultTy) { switch (val.getSubKind()) { case nonloc::ConcreteIntKind: return val.castAs().evalMinus(*this); + case nonloc::SymbolValKind: + return makeNonLoc(val.castAs().getSymbol(), UO_Minus, + resultTy); default: return UnknownVal(); } } -SVal SimpleSValBuilder::evalComplement(NonLoc X) { +SVal SimpleSValBuilder::evalComplement(NonLoc X, QualType resultTy) { switch (X.getSubKind()) { case nonloc::ConcreteIntKind: return X.castAs().evalComplement(*this); + case nonloc::SymbolValKind: + return makeNonLoc(X.castAs().getSymbol(), UO_Not, + resultTy); default: return UnknownVal(); } @@ -1120,7 +1126,7 @@ } else if (isa(region)) { assert(op == BO_Add || op == BO_Sub); - index = (op == BO_Add) ? rhs : evalMinus(rhs); + index = (op == BO_Add) ? rhs : evalMinus(rhs, rhs.getType(Context)); superR = cast(region); // TODO: Is this actually reliable? Maybe improving our MemRegion // hierarchy to provide typed regions for all non-void pointers would be @@ -1305,6 +1311,20 @@ S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType())); } + // FIXME add VisitSymbolCast + + SVal VisitUnarySymExpr(const UnarySymExpr *S) { + auto I = Cached.find(S); + if (I != Cached.end()) + return I->second; + SVal Op = getConstOrVisit(S->getOperand()); + if (isUnchanged(S->getOperand(), Op)) + return skip(S); + + return cache( + S, SVB.evalUnaryOp(State, S->getOpcode(), Op, S->getType())); + } + SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); } SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); } diff --git a/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp b/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp --- a/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp @@ -70,6 +70,16 @@ os << ')'; } +void UnarySymExpr::dumpToStream(raw_ostream &os) const { + os << UnaryOperator::getOpcodeStr(Op); + bool Binary = isa(Operand); + if (Binary) + os << '('; + Operand->dumpToStream(os); + if (Binary) + os << ')'; +} + void SymbolConjured::dumpToStream(raw_ostream &os) const { os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID(); if (S) @@ -134,6 +144,9 @@ case SymExpr::SymbolCastKind: itr.push_back(cast(SE)->getOperand()); return; + case SymExpr::UnarySymExprKind: + itr.push_back(cast(SE)->getOperand()); + return; case SymExpr::SymIntExprKind: itr.push_back(cast(SE)->getLHS()); return; @@ -306,6 +319,22 @@ return cast(data); } +const UnarySymExpr *SymbolManager::getUnarySymExpr(const SymExpr *Operand, + UnaryOperator::Opcode Opc, + QualType T) { + llvm::FoldingSetNodeID ID; + UnarySymExpr::Profile(ID, Operand, Opc, T); + void *InsertPos; + SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); + if (!data) { + data = (UnarySymExpr *)BPAlloc.Allocate(); + new (data) UnarySymExpr(Operand, Opc, T); + DataSet.InsertNode(data, InsertPos); + } + + return cast(data); +} + QualType SymbolConjured::getType() const { return T; } @@ -465,6 +494,9 @@ case SymExpr::SymbolCastKind: KnownLive = isLive(cast(sym)->getOperand()); break; + case SymExpr::UnarySymExprKind: + KnownLive = isLive(cast(sym)->getOperand()); + break; } if (KnownLive) diff --git a/clang/test/Analysis/explain-svals.cpp b/clang/test/Analysis/explain-svals.cpp --- a/clang/test/Analysis/explain-svals.cpp +++ b/clang/test/Analysis/explain-svals.cpp @@ -72,6 +72,7 @@ void test_4(int x, int y) { int z; static int stat; + clang_analyzer_explain(-x); // expected-warning-re{{{{^\- \(argument 'x'\)$}}}} clang_analyzer_explain(x + 1); // expected-warning-re{{{{^\(argument 'x'\) \+ 1$}}}} clang_analyzer_explain(1 + y); // expected-warning-re{{{{^\(argument 'y'\) \+ 1$}}}} clang_analyzer_explain(x + y); // expected-warning-re{{{{^\(argument 'x'\) \+ \(argument 'y'\)$}}}} diff --git a/clang/test/Analysis/expr-inspection.cpp b/clang/test/Analysis/expr-inspection.cpp --- a/clang/test/Analysis/expr-inspection.cpp +++ b/clang/test/Analysis/expr-inspection.cpp @@ -18,6 +18,8 @@ clang_analyzer_express(x); // expected-warning{{Unable to express}} clang_analyzer_denote(x, "$x"); + clang_analyzer_express(-x); // expected-warning{{-$x}} + clang_analyzer_denote(y, "$y"); clang_analyzer_express(x + y); // expected-warning{{$x + $y}} diff --git a/clang/test/Analysis/unary-sym-expr.c b/clang/test/Analysis/unary-sym-expr.c new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/unary-sym-expr.c @@ -0,0 +1,36 @@ +// RUN: %clang_analyze_cc1 %s \ +// RUN: -analyzer-checker=core,debug.ExprInspection \ +// RUN: -analyzer-config eagerly-assume=false \ +// RUN: -verify + +void clang_analyzer_eval(int); +void clang_analyzer_dump(int); + +int test(int x, int y) { + + clang_analyzer_dump(-x); // expected-warning{{-reg_$0}} + clang_analyzer_dump(~x); // expected-warning{{~reg_$0}} + int z = x + y; + clang_analyzer_dump(-z); // expected-warning{{-((reg_$0) + (reg_$1))}} + clang_analyzer_dump(-(x + y)); // expected-warning{{-((reg_$0) + (reg_$1))}} + clang_analyzer_dump(-x + y); // expected-warning{{(-reg_$0) + (reg_$1)}} + + if (-x == 0) { + clang_analyzer_eval(-x == 0); // expected-warning{{TRUE}} + clang_analyzer_eval(-x > 0); // expected-warning{{FALSE}} + clang_analyzer_eval(-x < 0); // expected-warning{{FALSE}} + } + if (~y == 0) { + clang_analyzer_eval(~y == 0); // expected-warning{{TRUE}} + clang_analyzer_eval(~y > 0); // expected-warning{{FALSE}} + clang_analyzer_eval(~y < 0); // expected-warning{{FALSE}} + } + (void)(x); + return 42; +} + +void test_svalbuilder_simplification(int x, int y) { + if (x + y != 3) + return; + clang_analyzer_eval(-(x + y) == -3); // expected-warning{{TRUE}} +}