diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp --- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -964,6 +964,8 @@ return VisitBinaryOperator(LHS, RHS, T); case BO_Rem: return VisitBinaryOperator(LHS, RHS, T); + case BO_Add: + return VisitBinaryOperator(LHS, RHS, T); default: return infer(T); } @@ -1380,6 +1382,79 @@ return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; } +template <> +RangeSet SymbolicRangeInferrer::VisitBinaryOperator(Range LHS, + Range RHS, + QualType T) { + APSIntType ResultType = ValueFactory.getAPSIntType(T); + llvm::APSInt Min = LHS.From() + RHS.From(); + llvm::APSInt Max = LHS.To() + RHS.To(); + const llvm::APSInt &Tmin = ValueFactory.getMinValue(ResultType); + const llvm::APSInt &Tmax = ValueFactory.getMaxValue(ResultType); + + if (Min > Max) { + // This implies that an overflow has occured as either boundary would have + // wrapped around the limits of ResultType. + // + // There are two possibilities: + // 1. Range [Tmin, Max] did not overlap Min and similarly [Min, Tmin] did + // not overlap Max, considering if Min overflowed from the negative side. + // In this case, the final RangeSet will be [Tmin, Max] U [Min, Tmax]. + // + // 2. Range overlapped Min (or Max), and in this case, it will return + // [Tmin, Tmax]. + // + // Based on number of overflows, we can deduce the type of range: + // 1. If 1, then return [Tmin, Max] U [Min, Tmax] + // 2. If > 1, then return [Tmin, Tmax] + if ((LHS.From() < 0 && RHS.From() < 0)) { + llvm::APSInt CrucialPoint = Tmin - LHS.From(); + if (RHS.Includes(CrucialPoint)) { + Range BeforeCrucialPoint(Tmin, --CrucialPoint); + if (BeforeCrucialPoint.Includes(Tmin + Tmax)) { + return {RangeFactory, Tmin, Tmax}; + } + } + } + + // Similarly, if Max overflows then it is checking if it can overflow twice. + // If so, then it will cover entire range. + if (LHS.To() > 0 && RHS.To() > 0) { + llvm::APSInt CrucialPoint = Tmax - LHS.To(); + if (RHS.Includes(CrucialPoint)) { + Range AfterCrucialPoint(++CrucialPoint, Tmax); + if (AfterCrucialPoint.Includes(Tmin + Tmax)) { + return {RangeFactory, Tmin, Tmax}; + } + } + } + + RangeSet Result(RangeFactory, Tmin, ValueFactory.getValue(Max)); + return RangeFactory.add(Result, + {RangeFactory, ValueFactory.getValue(Min), Tmax}); + } + + // FIXME: LHS = [Tmax, Tmax], RHS = [1, 1] => [ Tmin, Tmin] does not work + // + // As Min <= Max, therefore, only possiblities are that overflow may or may + // not happen, hence, we just need to check if any overflow occured. If that + // is the case, then range can only be of type [Tmin, Tmax] because Min <= Max + // + // NOTE: + // If only one of them overflowed, then the range will be [Tmin, Tmax]. + // If both of them overflowed on the opposite side, then the range will also + // be [Tmin, Tmax]. + // If both of them overflowed simulatenously, then range will be [Min, Max]. + if ((LHS.From() > 0 && RHS.From() > 0 && Min < 0) || + (LHS.From() < 0 && RHS.From() < 0 && Min > 0) || + (LHS.To() > 0 && RHS.To() > 0 && Max < 0) || + (LHS.To() < 0 && RHS.To() < 0 && Max > 0)) { + return {RangeFactory, Tmin, Tmax}; + } + + return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; +} + //===----------------------------------------------------------------------===// // Constraint manager implementation details //===----------------------------------------------------------------------===// diff --git a/clang/test/Analysis/constant-folding.c b/clang/test/Analysis/constant-folding.c --- a/clang/test/Analysis/constant-folding.c +++ b/clang/test/Analysis/constant-folding.c @@ -251,3 +251,83 @@ clang_analyzer_eval((b % a) < x + 10); // expected-warning{{TRUE}} } } + +void testAdditionRules(unsigned int a, unsigned int b, int c, int d) { + if (a == 0) { + clang_analyzer_eval((a + 0) == 0); // expected-warning{{TRUE}} + } + + // Checks for unsigned operands + clang_analyzer_eval((a + b) < 0); // expected-warning{{FALSE}} + clang_analyzer_eval((a + b) <= UINT_MAX); // expected-warning{{TRUE}} + + if (a == UINT_MAX && b == UINT_MAX) { + clang_analyzer_eval((a + b) == UINT_MAX - 1); // expected-warning{{TRUE}} + } + + // Checks for inclusive ranges for unsigned integers + if (a >= 0 && a <= 10 && b >= 0 && b <= 20) { + clang_analyzer_eval((a + b) >= 0); // expected-warning{{TRUE}} + clang_analyzer_eval((a + b) > 30); // expected-warning{{FALSE}} + } + + // Checks for negative signed integers + if (c < 0 && d < 0) { + clang_analyzer_eval((c + d) < 0); // expected-warning{{UNKNOWN}} + } + + if (c < 0 && c != INT_MIN && d < 0) { + clang_analyzer_eval((c + d) == -1); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) == 0); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) <= -2); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c + d) >= 1); // expected-warning{{UNKNOWN}} + } + + if (c == INT_MIN && d == INT_MIN) { + clang_analyzer_eval((c + d) == 0); // expected-warning{{TRUE}} + } + + if (c == INT_MIN && d < 0 && d != INT_MIN) { + clang_analyzer_eval((c + d) > 0); // expected-warning{{TRUE}} + } + + if (c < 0 && c >= -20 && d < 0 && d >= -40) { + clang_analyzer_eval((c + d) < -1); // expected-warning{{TRUE}} + clang_analyzer_eval((c + d) >= -60); // expected-warning{{TRUE}} + } + + // Checks for integers with different sign bits + if (c < 0 && d > 0) { + if (c >= -20 && d <= 10) { + clang_analyzer_eval((c + d) > -20); // expected-warning{{TRUE}} + clang_analyzer_eval((c + d) < 10); // expected-warning{{TRUE}} + } + } + + // Checks for overlapping signed integers ranges + if (c >= -20 && c <= 20 && d >= -10 && d <= 10) { + clang_analyzer_eval((c + d) >= -30); // expected-warning{{TRUE}} + clang_analyzer_eval((c + d) <= 30); // expected-warning{{TRUE}} + } + + // Checks for positive signed integers + if (c > 0 && d > 0) { + clang_analyzer_eval((c + d) == 1); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) == 0); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) == -1); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) > 1); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c + d) < -1); // expected-warning{{UNKNOWN}} + } + + // Checks producing overflowing range with different signs + int HALF_INT_MAX = INT_MAX / 2; + if (c >= HALF_INT_MAX - 10 && c <= HALF_INT_MAX + 10 && + d >= HALF_INT_MAX - 10 && d <= HALF_INT_MAX + 10) { + // The resulting range for (c + d) will be: + // [INT_MIN, INT_MIN + 18] U [INT_MAX - 21, INT_MAX] + clang_analyzer_eval((c + d) <= INT_MIN + 18); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c + d) >= INT_MAX - 21); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c + d) == INT_MIN + 19); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) == INT_MAX - 22); // expected-warning{{FALSE}} + } +}