manas updated this revision to Diff 356249.
manas added a comment.
Remove redundant getAPSIntType calls
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D105273/new/
https://reviews.llvm.org/D105273
Files:
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/constant-folding.c
Index: clang/test/Analysis/constant-folding.c
===================================================================
--- clang/test/Analysis/constant-folding.c
+++ 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}}
+ }
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -958,6 +958,8 @@
return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
case BO_Add:
return VisitBinaryOperator<BO_Add>(LHS, RHS, T);
+ case BO_Sub:
+ return VisitBinaryOperator<BO_Sub>(LHS, RHS, T);
default:
return infer(T);
}
@@ -1429,6 +1431,72 @@
return {RangeFactory, Tmin, Tmax};
}
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Sub>(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().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
//===----------------------------------------------------------------------===//
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
