manas updated this revision to Diff 355825.
manas added a comment.
Reformat comments
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D103440/new/
https://reviews.llvm.org/D103440
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
@@ -251,3 +251,104 @@
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 both ends
+ 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}}
+ }
+
+ 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}}
+ }
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ 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"
@@ -964,6 +965,8 @@
return VisitBinaryOperator<BO_And>(LHS, RHS, T);
case BO_Rem:
return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
+ case BO_Add:
+ return VisitBinaryOperator<BO_Add>(LHS, RHS, T);
default:
return infer(T);
}
@@ -1380,6 +1383,61 @@
return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};
}
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Add>(Range LHS,
+ Range RHS,
+ QualType T) {
+ APSIntType ResultType = ValueFactory.getAPSIntType(T);
+ 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() > 0 && RHS.From() > 0) && (LHS.To() > 0 && RHS.To() > 0)) ||
+ ((LHS.From() < 0 && RHS.From() < 0) && (LHS.To() < 0 && RHS.To() < 0))) {
+ 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
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
