vsavchenko updated this revision to Diff 264605.
vsavchenko added a comment.
Rebase
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D80117/new/
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
@@ -388,6 +388,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);
}
@@ -451,6 +453,37 @@
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)};
+ }
+
/// Return a range set subtracting zero from \p Domain.
RangeSet assumeNonZero(RangeSet Domain, QualType T) {
APSIntType IntType = ValueFactory.getAPSIntType(T);
@@ -590,6 +623,66 @@
return infer(T);
}
+template <>
+RangeSet SymbolicRangeInferrer::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)};
+}
+
class RangeConstraintManager : public RangedConstraintManager {
public:
RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
