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 @@ -371,6 +371,8 @@ return VisitBinaryOperator(LHS, RHS, T); case BO_And: return VisitBinaryOperator(LHS, RHS, T); + case BO_Rem: + return VisitBinaryOperator(LHS, RHS, T); default: return infer(T); } @@ -533,6 +535,96 @@ return infer(T); } + Range makeAbsolute(Range Origin, QualType T) { + APSIntType RangeType = ValueFactory.getAPSIntType(T); + bool CoversTheWholeType = + (Origin.From().isMinSignedValue() || Origin.To().isMaxValue()); + + if (CoversTheWholeType) { + return {ValueFactory.getMinValue(RangeType), + ValueFactory.getMaxValue(RangeType)}; + } + + if (RangeType.isUnsigned()) { + return Range(ValueFactory.getMinValue(RangeType), Origin.To()); + } + + // At this point, we are sure that the type is signed and we can safely + // use unary - operator. + // + // While calculating absolute maximum, we can use the following formula + // because of these reasons: + // * If From >= 0 then To >= From and To >= -From. + // AbsMax == To == max(To, -From) + // * If To <= 0 then -From >= -To and -From >= From. + // AbsMax == -From == max(-From, To) + // * Otherwise, From <= 0, To >= 0, and + // AbsMax == max(abs(From), abs(To)) + llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To()); + + // Intersection is guaranteed to be non-empty. + return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)}; + } + + template <> + RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) { + llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue(); + + // Check if LHS is 0. It's a special case when the result is guaranteed + // to be 0 no matter what RHS is (we put to the side the case when RHS is + // 0 itself). + const llvm::APSInt *LHSConstant = LHS.getConcreteValue(); + if (LHSConstant && *LHSConstant == Zero) { + return {RangeFactory, *LHSConstant}; + } + + Range ConservativeRange = makeAbsolute(RHS, T); + + llvm::APSInt Max = ConservativeRange.To(); + llvm::APSInt Min = ConservativeRange.From(); + + // At this point, our conservative range is closed. The result, however, + // couldn't be greater than the RHS' maximal absolute value. Because of + // this reason, we turn the range into open (or half-open in case of + // unsigned integers). + if (Max == Zero) { + // It's an undefined behaviour to divide by 0 and it seems like we know + // for sure that RHS is 0. Let's say that the resulting range is + // simply infeasible for that matter. + return RangeFactory.getEmptySet(); + } + + // Offset the boundaries towards zero. + // + // If we are dealing with unsigned case, we shouldn't move the lower bound. + if (Min.isSigned()) { + ++Min; + } + --Max; + + bool IsLHSPositiveOrZero = LHS.From() >= Zero; + bool IsRHSPositiveOrZero = RHS.From() >= Zero; + + // Remainder operator results with negative operands is implementation + // defined. Positive cases are much easier to reason about though. + if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) { + // If maximal value of LHS is less than maximal value of RHS, + // the result won't get greater than LHS.To(). + Max = std::min(LHS.To(), Max); + // We want to check if it is a situation similar to the following: + // + // <------------|---[ LHS ]--------[ RHS ]-----> + // -INF 0 +INF + // + // In this situation, we can conclude that (LHS / RHS) == 0 and + // (LHS % RHS) == LHS. + Min = LHS.To() < RHS.From() ? LHS.From() : Zero; + } + + return {RangeFactory, ValueFactory.getValue(Min), + ValueFactory.getValue(Max)}; + } + /// Return a range set subtracting zero from \p Domain. RangeSet assumeNonZero(RangeSet Domain, QualType T) { APSIntType IntType = ValueFactory.getAPSIntType(T); diff --git a/clang/test/Analysis/PR35418.cpp b/clang/test/Analysis/PR35418.cpp new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/PR35418.cpp @@ -0,0 +1,28 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s + +// expected-no-diagnostics + +void halt() __attribute__((__noreturn__)); +void assert(int b) { + if (!b) + halt(); +} + +void decode(unsigned width) { + assert(width > 0); + + int base; + bool inited = false; + + int i = 0; + + if (i % width == 0) { + base = 512; + inited = true; + } + + base += 1; // no-warning + + if (base >> 10) + assert(false); +} 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 @@ -174,3 +174,64 @@ clang_analyzer_eval((a & 1) <= 1); // expected-warning{{TRUE}} } } + +void testRemainderRules(unsigned int a, unsigned int b, int c, int d) { + // Check that we know that remainder of zero divided by any number is still 0. + clang_analyzer_eval((0 % c) == 0); // expected-warning{{TRUE}} + + clang_analyzer_eval((10 % a) <= 10); // expected-warning{{TRUE}} + + if (a <= 30 && b <= 50) { + clang_analyzer_eval((40 % a) < 30); // expected-warning{{TRUE}} + clang_analyzer_eval((a % b) < 50); // expected-warning{{TRUE}} + clang_analyzer_eval((b % a) < 30); // expected-warning{{TRUE}} + + if (a >= 10) { + // Even though it seems like a valid assumption, it is not. + // Check that we are not making this mistake. + clang_analyzer_eval((a % b) >= 10); // expected-warning{{UNKNOWN}} + + // Check that we can we can infer when remainder is equal + // to the dividend. + clang_analyzer_eval((4 % a) == 4); // expected-warning{{TRUE}} + if (b < 7) { + clang_analyzer_eval((b % a) < 7); // expected-warning{{TRUE}} + } + } + } + + // Check that we can reason about signed integers when they are + // known to be positive. + if (c >= 10 && c <= 30 && d >= 20 && d <= 50) { + clang_analyzer_eval((5 % c) == 5); // expected-warning{{TRUE}} + clang_analyzer_eval((c % d) <= 30); // expected-warning{{TRUE}} + clang_analyzer_eval((c % d) >= 0); // expected-warning{{TRUE}} + clang_analyzer_eval((d % c) < 30); // expected-warning{{TRUE}} + clang_analyzer_eval((d % c) >= 0); // expected-warning{{TRUE}} + } + + if (c >= -30 && c <= -10 && d >= -20 && d <= 50) { + // Test positive LHS with negative RHS. + clang_analyzer_eval((40 % c) < 30); // expected-warning{{TRUE}} + clang_analyzer_eval((40 % c) > -30); // expected-warning{{TRUE}} + + // Test negative LHS with possibly negative RHS. + clang_analyzer_eval((-10 % d) < 50); // expected-warning{{TRUE}} + clang_analyzer_eval((-20 % d) > -50); // expected-warning{{TRUE}} + + // Check that we don't make wrong assumptions + clang_analyzer_eval((-20 % d) > -20); // expected-warning{{UNKNOWN}} + + // Check that we can reason about negative ranges... + clang_analyzer_eval((c % d) < 50); // expected-warning{{TRUE}} + /// ...both ways + clang_analyzer_eval((d % c) < 30); // expected-warning{{TRUE}} + + if (a <= 10) { + // Result is unsigned. This means that 'c' is casted to unsigned. + // We don't want to reason about ranges changing boundaries with + // conversions. + clang_analyzer_eval((a % c) < 30); // expected-warning{{UNKNOWN}} + } + } +} diff --git a/clang/test/Analysis/uninit-bug-first-iteration-init.c b/clang/test/Analysis/uninit-bug-first-iteration-init.c new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/uninit-bug-first-iteration-init.c @@ -0,0 +1,27 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s + +// rdar://problem/44978988 +// expected-no-diagnostics + +int foo(); + +int gTotal; + +double bar(int start, int end) { + int i, cnt, processed, size; + double result, inc; + + result = 0; + processed = start; + size = gTotal * 2; + cnt = (end - start + 1) * size; + + for (i = 0; i < cnt; i += 2) { + if ((i % size) == 0) { + inc = foo(); + processed++; + } + result += inc * inc; // no-warning + } + return result; +}