vsavchenko created this revision.
vsavchenko added reviewers: NoQ, dcoughlin, xazax.hun, ASDenysPetrov.
Herald added subscribers: cfe-commits, martong, Charusso, dkrupp, donat.nagy,
Szelethus, mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware.
Herald added a project: clang.
New logic tries to narrow possible result values of the remainder operation
based on its operands and their ranges. It also tries to be conservative
with negative operands because according to the standard the sign of
the result is implementation-defined.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D80117
Files:
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/PR35418.cpp
clang/test/Analysis/constant-folding.c
clang/test/Analysis/uninit-bug-first-iteration-init.c
Index: clang/test/Analysis/uninit-bug-first-iteration-init.c
===================================================================
--- /dev/null
+++ 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;
+}
Index: clang/test/Analysis/constant-folding.c
===================================================================
--- clang/test/Analysis/constant-folding.c
+++ 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}}
+ }
+ }
+}
Index: clang/test/Analysis/PR35418.cpp
===================================================================
--- /dev/null
+++ 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);
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -371,6 +371,8 @@
return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
case BO_And:
return VisitBinaryOperator<BO_And>(LHS, RHS, T);
+ case BO_Rem:
+ return VisitBinaryOperator<BO_Rem>(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<BO_Rem>(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);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
