manas updated this revision to Diff 363734.
manas added a comment.
Fix test 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
clang/utils/analyzer/Dockerfile
clang/utils/analyzer/SATestBuild.py
clang/utils/analyzer/entrypoint.py
Index: clang/utils/analyzer/entrypoint.py
===================================================================
--- clang/utils/analyzer/entrypoint.py
+++ clang/utils/analyzer/entrypoint.py
@@ -9,10 +9,11 @@
def main():
settings, rest = parse_arguments()
+ cmake_opts = ['-D' + cmd for cmd in settings.D]
if settings.wait:
wait()
if settings.build_llvm or settings.build_llvm_only:
- build_llvm()
+ build_llvm(cmake_opts)
if settings.build_llvm_only:
return
sys.exit(test(rest))
@@ -30,14 +31,15 @@
parser.add_argument('--wait', action='store_true')
parser.add_argument('--build-llvm', action='store_true')
parser.add_argument('--build-llvm-only', action='store_true')
+ parser.add_argument('-D', action='append', default=[])
return parser.parse_known_args()
-def build_llvm():
+def build_llvm(cmake_options):
os.chdir('/build')
try:
if is_cmake_needed():
- cmake()
+ cmake(cmake_options)
ninja()
except CalledProcessError:
print("Build failed!")
@@ -55,8 +57,9 @@
"-DCLANG_ENABLE_STATIC_ANALYZER=ON"
-def cmake():
- check_call(CMAKE_COMMAND + ' /llvm-project/llvm', shell=True)
+def cmake(cmake_options):
+ check_call(CMAKE_COMMAND + ' '.join(cmake_options) + ' /llvm-project/llvm',
+ shell=True)
def ninja():
Index: clang/utils/analyzer/SATestBuild.py
===================================================================
--- clang/utils/analyzer/SATestBuild.py
+++ clang/utils/analyzer/SATestBuild.py
@@ -847,7 +847,8 @@
continue
plist = os.path.join(dir_path, filename)
- data = plistlib.readPlist(plist)
+ with open(plist, "rb") as plist_file:
+ data = plistlib.load(plist_file)
path_prefix = directory
if build_mode == 1:
@@ -866,7 +867,8 @@
if 'clang_version' in data:
data.pop('clang_version')
- plistlib.writePlist(data, plist)
+ with open(plist, "wb") as plist_file:
+ plistlib.dump(data, plist_file)
def get_build_log_path(output_dir: str) -> str:
Index: clang/utils/analyzer/Dockerfile
===================================================================
--- clang/utils/analyzer/Dockerfile
+++ clang/utils/analyzer/Dockerfile
@@ -17,8 +17,9 @@
gettext=0.19.8.1* \
python3=3.6.7-1~18.04 \
python3-pip=9.0.1-2.3* \
- cmake=3.20.5* \
- ninja-build=1.8.2-1
+ cmake=3.21.1* \
+ ninja-build=1.8.2-1 \
+ ccache=3.4*
# box2d dependencies
RUN apt-get install -y \
Index: clang/test/Analysis/constant-folding.c
===================================================================
--- clang/test/Analysis/constant-folding.c
+++ clang/test/Analysis/constant-folding.c
@@ -281,3 +281,226 @@
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 Tmax side
+ 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}}
+ }
+
+ // Overflows on both ends
+ 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}}
+ }
+}
+
+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}}
+ }
+}
+
+void testEqualityRules(unsigned int a, unsigned int b, int c, int d) {
+ // Checks when ranges are not overlapping
+ if (a <= 10 && b >= 20) {
+ clang_analyzer_eval((a != b) != 0); // expected-warning{{TRUE}}
+ }
+
+ if (c <= INT_MIN + 10 && d >= INT_MAX - 10) {
+ clang_analyzer_eval((c != d) == 0); // expected-warning{{FALSE}}
+ }
+
+ // Checks when ranges are completely overlapping and have more than one point
+ if (a >= 20 && a <= 50 && b >= 20 && b <= 50) {
+ clang_analyzer_eval((a != b) != 0); // expected-warning{{UNKNOWN}}
+ }
+
+ if (c >= -20 && c <= 20 && d >= -20 && d <= 20) {
+ clang_analyzer_eval((c != d) != 0); // expected-warning{{UNKNOWN}}
+ }
+
+ // Checks when ranges are partially overlapping
+ if (a >= 100 && a <= 200 && b >= 150 && b <= 300) {
+ clang_analyzer_eval((a != b) != 0); // expected-warning{{UNKNOWN}}
+ }
+
+ if (c >= -80 && c <= -50 && d >= -100 && d <= -75) {
+ clang_analyzer_eval((c != d) == 0); // expected-warning{{UNKNOWN}}
+ }
+
+ // Checks for ranges which are subset of one-another
+ if (a >= 500 && a <= 1000 && b >= 750 && b <= 1000) {
+ clang_analyzer_eval((a != b) == 0); // expected-warning{{UNKNOWN}}
+ }
+
+ if (c >= -1000 && c <= -500 && d <= -500 && d >= -750) {
+ clang_analyzer_eval((c != d) == 0); // expected-warning{{UNKNOWN}}
+ }
+}
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"
@@ -955,12 +956,18 @@
RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op,
RangeSet RHS, QualType T) {
switch (Op) {
+ case BO_NE:
+ return VisitBinaryOperator<BO_NE>(LHS, RHS, T);
case BO_Or:
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);
+ case BO_Add:
+ return VisitBinaryOperator<BO_Add>(LHS, RHS, T);
+ case BO_Sub:
+ return VisitBinaryOperator<BO_Sub>(LHS, RHS, T);
default:
return infer(T);
}
@@ -1221,6 +1228,27 @@
// Range-based reasoning about symbolic operations
//===----------------------------------------------------------------------===//
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_NE>(Range LHS, Range RHS,
+ QualType T) {
+
+ // When both the ranges are non-overlapping then all possible pairs of (x, y)
+ // in LHS, RHS will satisfy expression (x != y)
+ if ((LHS.To() < RHS.From()) || (RHS.To() < LHS.From())) {
+ return getTrueRange(T);
+ }
+
+ // If both ranges contain only one same Point then the expression will always
+ // return true
+ if ((LHS.From() == RHS.To()) && (LHS.To() == RHS.To()) &&
+ (LHS.From() == RHS.From())) {
+ return getFalseRange(T);
+ }
+
+ // In all other cases, the resulting range cannot be deduced.
+ return RangeFactory.getEmptySet();
+}
+
template <>
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,
QualType T) {
@@ -1381,6 +1409,130 @@
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);
+ 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().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() > 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};
+}
+
+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 assignment logic
//===----------------------------------------------------------------------===//
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
