ASDenysPetrov created this revision.
ASDenysPetrov added reviewers: NoQ, baloghadamsoftware.
ASDenysPetrov added a project: clang.
Herald added subscribers: cfe-commits, martong, Charusso, dkrupp, donat.nagy,
Szelethus, mikhail.ramalho, a.sidorin, rnkovacs, szepet, xazax.hun.
This fixes https://bugs.llvm.org/show_bug.cgi?id=41588
RangeSet Negate function shall handle unsigned ranges as well as signed ones.
RangeSet getRangeForMinusSymbol function shall use wider variety of ranges, not
only concrete value ranges.
RangeSet Intersect functions shall not produce assertions.
Changes:
Improved safety of RangeSet::Intersect function. Added isEmpty() check to
prevent an assertion.
Added support of handling unsigned ranges to RangeSet::Negate and
RangeSet::getRangeForMinusSymbol.
Extended RangeSet::getRangeForMinusSymbol to return not only range sets with
single value [n,n], but with wide ranges [n,m].
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D77802
Files:
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/constraint_manager_negate_difference.c
Index: clang/test/Analysis/constraint_manager_negate_difference.c
===================================================================
--- clang/test/Analysis/constraint_manager_negate_difference.c
+++ clang/test/Analysis/constraint_manager_negate_difference.c
@@ -110,3 +110,9 @@
clang_analyzer_eval(m - n == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}}
clang_analyzer_eval(n - m == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}}
}
+
+void negated_unsigned_range(unsigned x, unsigned y) {
+ clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
+ clang_analyzer_eval(y - x != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
+ clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -155,11 +155,11 @@
// or, alternatively, /removing/ all integers between Upper and Lower.
RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
llvm::APSInt Lower, llvm::APSInt Upper) const {
- if (!pin(Lower, Upper))
- return F.getEmptySet();
-
PrimRangeSet newRanges = F.getEmptySet();
+ if (isEmpty() || !pin(Lower, Upper))
+ return newRanges;
+
PrimRangeSet::iterator i = begin(), e = end();
if (Lower <= Upper)
IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
@@ -190,32 +190,54 @@
return newRanges;
}
-// Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set
-// [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal
-// signed values of the type.
+// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
+// operation under the values of the type.
+// Negate also restores disrupted ranges on bounds,
+// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B]
RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
PrimRangeSet newRanges = F.getEmptySet();
+ if (isEmpty())
+ return newRanges;
+
+ const llvm::APSInt sampleValue = getMinValue();
+ const bool isUnsigned = sampleValue.isUnsigned();
+ const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
+ const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+ bool hasNewRangesMinValue = false;
+
for (iterator i = begin(), e = end(); i != e; ++i) {
- const llvm::APSInt &from = i->From(), &to = i->To();
- const llvm::APSInt &newTo = (from.isMinSignedValue() ?
- BV.getMaxValue(from) :
- BV.getValue(- from));
- if (to.isMaxSignedValue() && !newRanges.isEmpty() &&
- newRanges.begin()->From().isMinSignedValue()) {
- assert(newRanges.begin()->To().isMinSignedValue() &&
- "Ranges should not overlap");
- assert(!from.isMinSignedValue() && "Ranges should not overlap");
- const llvm::APSInt &newFrom = newRanges.begin()->From();
- newRanges =
- F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
- } else if (!to.isMinSignedValue()) {
- const llvm::APSInt &newFrom = BV.getValue(- to);
- newRanges = F.add(newRanges, Range(newFrom, newTo));
- }
- if (from.isMinSignedValue()) {
- newRanges = F.add(newRanges, Range(BV.getMinValue(from),
- BV.getMinValue(from)));
+ const llvm::APSInt &from = i->From();
+ const llvm::APSInt &to = i->To();
+
+ const bool isFromMinValue =
+ isUnsigned ? from.isMinValue() : from.isMinSignedValue();
+ const bool isToMinValue =
+ isUnsigned ? to.isMinValue() : to.isMinSignedValue();
+
+ // handle a special case for MIN value
+ if (isFromMinValue) {
+ // add separate range for the lowest value
+ newRanges = F.add(newRanges, Range(MIN, MIN));
+ hasNewRangesMinValue = true;
+
+ // skip adding the second range in case when [from, to] are [MIN, MIN]
+ if (!isToMinValue) {
+ newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX));
+ }
+ } else {
+ const llvm::APSInt &newFrom = BV.getValue(-to);
+ const llvm::APSInt &newTo = BV.getValue(-from);
+
+ // unite ranges [MIN, MIN] & [MIN + 1, N] => [MIN, N]
+ if (hasNewRangesMinValue && (newFrom - 1) == MIN) {
+ hasNewRangesMinValue = false;
+ newRanges = F.remove(newRanges, *newRanges.begin());
+ newRanges = F.add(newRanges, Range(MIN, newTo));
+ } else {
+ // otherwise add an negated range
+ newRanges = F.add(newRanges, Range(newFrom, newTo));
+ }
}
}
@@ -527,9 +549,7 @@
SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
SSE->getLHS(), T);
if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
- // Unsigned range set cannot be negated, unless it is [0, 0].
- if ((negV->getConcreteValue() &&
- (*negV->getConcreteValue() == 0)) ||
+ if (T->isUnsignedIntegerOrEnumerationType() ||
T->isSignedIntegerOrEnumerationType())
return negV;
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
