Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -284,17 +284,24 @@ namespace { class RangeConstraintManager : public SimpleConstraintManager{ RangeSet GetRange(ProgramStateRef state, SymbolRef sym); + + void adjustRangeIfTruncation(ProgramStateRef St, RangeSet &New, + const RangeSet &SymRange, SymbolRef &Sym, + SymbolRef SymInt); + public: RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB) : SimpleConstraintManager(subengine, SVB) {} ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + const llvm::APSInt& Adjustment, + SymbolRef SymInt = nullptr) override; ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + const llvm::APSInt& Adjustment, + SymbolRef SymInt = nullptr) override; ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, @@ -415,10 +422,43 @@ // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, // UINT_MAX, 0, 1, and 2. +// Adjusts the range of 'New' to the default range of SymInt's type in case +// 'New' is empty as a result of SymInt's type bit width being strictly smaller +// than Sym's type bit width. +// Also set 'Sym' as 'SymInt' so the caller does not modify Sym's range. +void RangeConstraintManager::adjustRangeIfTruncation(ProgramStateRef St, + RangeSet &New, + const RangeSet &SymRange, + SymbolRef &Sym, + SymbolRef SymInt) { + if (New.isEmpty() && !SymRange.isEmpty() && SymInt) { + // If range 'New' is empty and the SymInt associated with Sym is of smaller + // integer type than the range type associated with Sym. + // And if the minimum value of Sym's range is greater than the maximum of + // the SymInt type, then New range defaults to the range of SymInt's + // type. + QualType SymIntQType = SymInt->getType(); + ASTContext &Ctx = getBasicVals().getContext(); + uint64_t SymIntSize = Ctx.getTypeSize(SymIntQType); + llvm::APSInt RangeMin = SymRange.begin()->From(); + unsigned int RangeTypeSize = RangeMin.getBitWidth(); + APSIntType RangeType(RangeTypeSize, RangeMin.isUnsigned()); + APSIntType SymIntType(SymIntSize, RangeType.isUnsigned()); + llvm::APSInt SymIntTypeMax = SymIntType.getMaxValue(); + // if RangeMin > SymIntTypeMax + if (llvm::APSInt::compareValues(RangeMin, SymIntTypeMax) == 1) { + New = GetRange(St, SymInt); + Sym = SymInt; + } + } +} + ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { + const llvm::APSInt &Adjustment, + SymbolRef SymInt /*= nullptr*/) { + // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) @@ -431,14 +471,18 @@ // [Int-Adjustment+1, Int-Adjustment-1] // Notice that the lower bound is greater than the upper bound. - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); + RangeSet SymRange = GetRange(St, Sym); + RangeSet New = SymRange.Intersect(getBasicVals(), F, Upper, Lower); + adjustRangeIfTruncation(St, New, SymRange, Sym, SymInt); return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { + const llvm::APSInt &Adjustment, + SymbolRef SymInt /*= nullptr*/) { + // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) @@ -446,7 +490,9 @@ // [Int-Adjustment, Int-Adjustment] llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); + RangeSet SymRange = GetRange(St, Sym); + RangeSet New = SymRange.Intersect(getBasicVals(), F, AdjInt, AdjInt); + adjustRangeIfTruncation(St, New, SymRange, Sym, SymInt); return New.isEmpty() ? nullptr : St->set(Sym, New); } Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.h =================================================================== --- lib/StaticAnalyzer/Core/SimpleConstraintManager.h +++ lib/StaticAnalyzer/Core/SimpleConstraintManager.h @@ -53,11 +53,13 @@ // operation for the method being invoked. virtual ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; + const llvm::APSInt& Adjustment, + SymbolRef SymInt = nullptr) = 0; virtual ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; + const llvm::APSInt& Adjustment, + SymbolRef SymInt = nullptr) = 0; virtual ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& V, Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -243,10 +243,10 @@ llvm_unreachable("invalid operation not caught by assertion above"); case BO_EQ: - return assumeSymEQ(state, Sym, ConvertedInt, Adjustment); + return assumeSymEQ(state, Sym, ConvertedInt, Adjustment, LHS); case BO_NE: - return assumeSymNE(state, Sym, ConvertedInt, Adjustment); + return assumeSymNE(state, Sym, ConvertedInt, Adjustment, LHS); case BO_GT: return assumeSymGT(state, Sym, ConvertedInt, Adjustment); Index: test/Analysis/range_casts.c =================================================================== --- /dev/null +++ test/Analysis/range_casts.c @@ -0,0 +1,147 @@ +// This test checks that intersecting ranges does not cause 'system is over constrained' assertions in the case of eg: 32 bits unsigned integers getting their range from 64 bits signed integers. +// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -analyze -analyzer-checker=core,debug.ExprInspection -analyzer-store=region -verify %s + +void clang_analyzer_warnIfReached(); + +void f1(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index + 1 == 0) // because of foo range, index is in range [0; UINT_MAX] + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f2(unsigned long foo) +{ + int index = -1; + if (index < foo) index = foo; // index equals ULONG_MAX + if (index + 1 == 0) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // no-warning +} + +void f3(unsigned long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index + 1 == 0) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f4(long foo) +{ + int index = -1; + if (index < foo) index = foo; + if (index + 1 == 0) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f5(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index == -1) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f6(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index == -1) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f7(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index - 1 == 0) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f8(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index + 1L == 0L) + clang_analyzer_warnIfReached(); // no-warning + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f9(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index - 1L == 0L) + // FIXME: should be reached + clang_analyzer_warnIfReached(); // no-warning + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f10(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index + 1 == 0L) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f11(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index + 1UL == 0L) + clang_analyzer_warnIfReached(); // no-warning + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f12(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + if (index - 1UL == 0L) + // FIXME: should be reached + clang_analyzer_warnIfReached(); // no-warning + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f13(int foo) +{ + unsigned short index = -1; + if (index < foo) index = foo; + if (index + 1 == 0) + clang_analyzer_warnIfReached(); // no-warning + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +} + +void f14(long foo) +{ + unsigned index = -1; + if (index < foo) index = foo; + long bar = foo; + if (index + 1 == 0) + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + else + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} +}