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 @@ -958,6 +958,8 @@ return VisitBinaryOperator(LHS, RHS, T); case BO_Add: return VisitBinaryOperator(LHS, RHS, T); + case BO_Sub: + return VisitBinaryOperator(LHS, RHS, T); default: return infer(T); } @@ -1429,6 +1431,72 @@ return {RangeFactory, Tmin, Tmax}; } +template <> +RangeSet SymbolicRangeInferrer::VisitBinaryOperator(Range LHS, + Range RHS, + QualType T) { + APSIntType ResultType = ValueFactory.getAPSIntType(T); + llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue(); + const llvm::APSInt &Tmin = ValueFactory.getMinValue(ResultType); + const llvm::APSInt &Tmax = ValueFactory.getMaxValue(ResultType); + + llvm::APSInt Min, Max; + bool HasMinOverflowed, HasMaxOverflowed; + + // Based on their signedness, compute values for Min and Max, and also store + // whether those values have overflowed or not. + if (ResultType.isUnsigned()) { + Min = llvm::APSInt(LHS.From().usub_ov(RHS.To(), HasMinOverflowed), true); + Max = llvm::APSInt(LHS.To().usub_ov(RHS.From(), HasMaxOverflowed), true); + } else { + Min = llvm::APSInt(LHS.From().ssub_ov(RHS.To(), HasMinOverflowed), false); + Max = llvm::APSInt(LHS.To().ssub_ov(RHS.From(), HasMaxOverflowed), false); + } + + // 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}; + } + + // Consider, two unsigned values a, b, and we know that: + // 0 <= a, b <= Tmax + // Hence, (a - b) > Tmax can never occur mathematically. So, (a - b) will + // never overflow from Tmax-side. + // Now, Min and Max can only overflow from Tmin-side (or Zero-side) and hence + // the resulting range should be [Min, Max]. + // + // As for signed values, if both boundary values overflow on the same side + // then rangeset is [Min, Max] + if (ResultType.isUnsigned() || + ((LHS.From() >= Zero && RHS.From() < Zero) && + (LHS.To() >= Zero && RHS.To() < Zero)) || + ((LHS.From() <= Zero && RHS.From() > Zero) && + (LHS.To() <= Zero && RHS.To() > Zero))) { + 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 @@ -352,3 +352,86 @@ clang_analyzer_eval((c + d) == INT_MAX - 22); // expected-warning{{FALSE}} } } + +void testSubtractionRules(unsigned int a, unsigned int b, int c, int d) { + // Checks when Max overflows but encompasses entire rangeset + if (c <= 0 && d <= 0) { + // (c - d) = [INT_MIN, INT_MAX] + clang_analyzer_eval((c - d) <= 0); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c - d) >= 0); // expected-warning{{UNKNOWN}} + } + + // Checks when both limits overflow from the opposite ends + if (c >= INT_MIN + 40 && c <= INT_MAX - 40 && d >= -50 && d <= 50) { + // (c - d) = [INT_MIN, INT_MAX] + clang_analyzer_eval((c - d) <= 0); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c - d) >= 0); // expected-warning{{UNKNOWN}} + } + + // Checks for non-overflowing ranges + if (a >= 10 && a <= 40 && b >= 5 && b <= 10) { + // (a - b) = [0, 35] + clang_analyzer_eval((a - b) <= 35); // expected-warning{{TRUE}} + } + + if (c >= -10 && c <= 10 && d >= -20 && d <= 20) { + // (c - d) = [-30, 30] + clang_analyzer_eval((c - d) >= -30); // expected-warning{{TRUE}} + clang_analyzer_eval((c - d) <= 30); // expected-warning{{TRUE}} + } + + // Check when Min overflows from lower bounded side + if (a <= 10 && b <= 10) { + // (a - b) = [0, 10] U [UINT_MAX - 9, UINT_MAX] + clang_analyzer_eval((a - b) != 11); // expected-warning{{TRUE}} + clang_analyzer_eval((a - b) != UINT_MAX - 10); // expected-warning{{TRUE}} + } + + if (c <= 10 && d >= -30 && d <= 30) { + // (c - d) = [INT_MIN, 40] U [INT_MAX - 29, INT_MAX] + clang_analyzer_eval((c - d) != INT_MAX - 30); // expected-warning{{TRUE}} + clang_analyzer_eval((c - d) != 41); // expected-warning{{TRUE}} + } + + // Checks when Max overflows from the upper bound side + if (a >= UINT_MAX - 10 && b >= UINT_MAX - 5) { + // (a - b) = [0, 5] U [UINT_MAX - 9, UINT_MAX] + clang_analyzer_eval((a - b) != 6); // expected-warning{{TRUE}} + clang_analyzer_eval((a - b) != UINT_MAX - 10); // expected-warning{{TRUE}} + clang_analyzer_eval((a - b) <= 5); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((a - b) >= UINT_MAX - 9); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((a - b) > 5 && (a - b) < UINT_MAX - 9); // expected-warning{{FALSE}} + } + + if (c >= INT_MAX - 50 && d >= -50 && d <= 50) { + // (c - d) = [INT_MIN, INT_MIN + 49] U [INT_MAX - 100, INT_MAX] + clang_analyzer_eval((c - d) >= INT_MAX - 100); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c - d) <= INT_MIN + 49); // expected-warning{{UNKNOWN}} + } + + // Check when both overflow from the same side + if (c >= INT_MAX - 5 && d >= INT_MAX - 5) { + // (c - d) = [-5, 5] + clang_analyzer_eval((c - d) < -5 ); // expected-warning{{FALSE}} + clang_analyzer_eval((c - d) > 5 ); // expected-warning{{FALSE}} + } + + // Checks for Min and Max overflowing from same end + if (a <= 50 && b >= 60 && b <= 100) { + // (a - b) = [UINT_MAX - 99, UINT_MAX - 9] + clang_analyzer_eval((a - b) > UINT_MAX - 9); // expected-warning{{FALSE}} + clang_analyzer_eval((a - b) < UINT_MAX - 99); // expected-warning{{FALSE}} + } + + if (c <= INT_MIN + 50 && d >= INT_MIN + 60 && d <= INT_MIN + 100) { + // (c - d) = [-100, -10] + clang_analyzer_eval((c - d) > -10); // expected-warning{{FALSE}} + clang_analyzer_eval((c - d) < -100); // expected-warning{{FALSE}} + } + + if (c >= INT_MAX - 50 && d >= INT_MIN + 70 && d <= INT_MIN + 90) { + // (c - d) = [-141, -71] + clang_analyzer_eval((c - d) < -141); // expected-warning{{FALSE}} + clang_analyzer_eval((c - d) > -71); // expected-warning{{FALSE}} + } +}