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 @@ -17,6 +17,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h" +#include "llvm/ADT/APSInt.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/ADT/STLExtras.h" @@ -961,6 +962,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); } @@ -1381,6 +1384,64 @@ 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 Zero = ResultType.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().uadd_ov(RHS.From(), HasMinOverflowed), true); + Max = llvm::APSInt(LHS.To().uadd_ov(RHS.To(), HasMaxOverflowed), true); + } else { + Min = llvm::APSInt(LHS.From().sadd_ov(RHS.From(), HasMinOverflowed), false); + Max = llvm::APSInt(LHS.To().sadd_ov(RHS.To(), 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}; + } + + // If both boundary values overflow on the same side then rangeset is + // [Min, Max] + if (((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 assignment logic //===----------------------------------------------------------------------===// 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 @@ -281,3 +281,105 @@ 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}} + } + + // Overflows on Tmax side + if (a >= 5 && a <= UINT_MAX - 5 && b <= 10) { + clang_analyzer_eval((a + b) >= UINT_MAX >> 1); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((a + b) <= UINT_MAX >> 1); // expected-warning{{UNKNOWN}} + } + + // Overflows on both ends + if (c >= INT_MIN + 5 && c <= INT_MAX - 5 && d >= -10 && d <= 10) { + clang_analyzer_eval((c + d) <= 0); // expected-warning{{UNKNOWN}} + clang_analyzer_eval((c + d) >= 0); // expected-warning{{UNKNOWN}} + } + + // 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}} + } +}