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,63 @@ 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); + + bool HasMinOverflowed, HasMaxOverflowed; + + if (ResultType.isUnsigned()) { + LHS.From().uadd_ov(RHS.From(), HasMinOverflowed); + LHS.To().uadd_ov(RHS.To(), HasMaxOverflowed); + } else { + LHS.From().sadd_ov(RHS.From(), HasMinOverflowed); + LHS.To().sadd_ov(RHS.To(), HasMaxOverflowed); + } + + // If no overflow occured then the range [Min, Max] is correct + if (!HasMinOverflowed && !HasMaxOverflowed) { + return {RangeFactory, ValueFactory.getValue(Min), + ValueFactory.getValue(Max)}; + } + + // In case of only one overflow, the two possibilities are: + // 1. The overflowing value overlaps the other boundary value, in which case, + // the range is entire range set [Tmin, Tmax] + // 2. The values do not get overlapped, which results in segmented ranges + // [Tmin, Max] U [Min, Tmax] + if (HasMinOverflowed ^ HasMaxOverflowed) { + if (Min > Max) { + RangeSet Result(RangeFactory, Tmin, ValueFactory.getValue(Max)); + return RangeFactory.add(Result, + {RangeFactory, ValueFactory.getValue(Min), Tmax}); + } + return {RangeFactory, Tmin, Tmax}; + } + + // If both boundary values overflow on the same side then rangeset is + // [Min, Max] + // if (twoOverflowsOnSameSide(Min, Max) + if (((LHS.From() > 0 && RHS.From() > 0) && (LHS.To() > 0 && RHS.To() > 0)) || + ((LHS.From() < 0 && RHS.From() < 0) && (LHS.To() < 0 && RHS.To() < 0))) { + return {RangeFactory, ValueFactory.getValue(Min), + ValueFactory.getValue(Max)}; + } + + // When both boundary values overflow from different sides then rangeset is + // [Tmin, Tmax] because the entire rangeset is already covered and overflow + // from opposite sides ensure already computed points to be reached again. + return {RangeFactory, Tmin, Tmax}; +} + //===----------------------------------------------------------------------===// // 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,93 @@ 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 <= 10 && 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) != -1); // expected-warning{{TRUE}} + } + + 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}} + } + + // Check when Max overflows from positive-side + if (c >= 10 && d >= 0 && d <= 10) { + clang_analyzer_eval((c + d) == INT_MIN + 10); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) == -1); // expected-warning{{FALSE}} + } + + // Checks when Min overflows from negative side + if (c <= 10 && d >= -10 && d <= 0) { + clang_analyzer_eval((c + d) == 11); // expected-warning{{FALSE}} + clang_analyzer_eval((c + d) == INT_MAX - 10); // expected-warning{{FALSE}} + } + + // 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}} + } +}