diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp --- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/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(LHS, RHS, T); case BO_Or: return VisitBinaryOperator(LHS, RHS, T); case BO_And: return VisitBinaryOperator(LHS, RHS, T); case BO_Rem: return VisitBinaryOperator(LHS, RHS, T); + case BO_Add: + return VisitBinaryOperator(LHS, RHS, T); + case BO_Sub: + return VisitBinaryOperator(LHS, RHS, T); default: return infer(T); } @@ -1221,6 +1228,27 @@ // Range-based reasoning about symbolic operations //===----------------------------------------------------------------------===// +template <> +RangeSet SymbolicRangeInferrer::VisitBinaryOperator(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(Range LHS, Range RHS, QualType T) { @@ -1381,6 +1409,130 @@ return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; } +template <> +RangeSet SymbolicRangeInferrer::VisitBinaryOperator(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(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 //===----------------------------------------------------------------------===// diff --git a/clang/test/Analysis/constant-folding.c b/clang/test/Analysis/constant-folding.c --- a/clang/test/Analysis/constant-folding.c +++ b/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}} + } +} diff --git a/clang/utils/analyzer/Dockerfile b/clang/utils/analyzer/Dockerfile --- a/clang/utils/analyzer/Dockerfile +++ b/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 \ diff --git a/clang/utils/analyzer/SATestBuild.py b/clang/utils/analyzer/SATestBuild.py --- a/clang/utils/analyzer/SATestBuild.py +++ b/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: diff --git a/clang/utils/analyzer/entrypoint.py b/clang/utils/analyzer/entrypoint.py --- a/clang/utils/analyzer/entrypoint.py +++ b/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():