baloghadamsoftware created this revision.
baloghadamsoftware added a reviewer: NoQ.
baloghadamsoftware added a project: clang.
Herald added subscribers: donat.nagy, mikhail.ramalho, a.sidorin, szepet.
Herald added a reviewer: george.karpenkov.
Since rL335814 <https://reviews.llvm.org/rL335814>, if the constraint manager
cannot find a range set for `A - B` (where `A` and `B` are symbols) it looks
for a range for `B - A` and returns it negated if it exists. However, if a
range set for both `A - B` and `B - A` is stored then it only returns the first
one. If we both use `A - B` and `B - A`, these expressions behave as two
totally unrelated symbols. This way we miss some useful deductions which may
lead to false negatives or false positives.
This tiny patch changes this behavior: if the symbolic expression the
constraint manager is looking for is a difference `A - B`, it tries to retrieve
the range for both `A - B` and `B - A` and if both exists it returns the
intersection of range `A - B` and the negated range of `B - A`. This way every
time a checker applies new constraints to the symbolic difference or to its
negated it always affects both the original difference and its negated.
Repository:
rC Clang
https://reviews.llvm.org/D55007
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
test/Analysis/constraint_manager_negate_difference.c
Index: test/Analysis/constraint_manager_negate_difference.c
===================================================================
--- test/Analysis/constraint_manager_negate_difference.c
+++ test/Analysis/constraint_manager_negate_difference.c
@@ -96,3 +96,10 @@
return;
clang_analyzer_eval(n - m <= 0); // expected-warning{{TRUE}}
}
+
+void effective_range(int m, int n) {
+ assert(m - n >= 0);
+ assert(n - m >= 0);
+ clang_analyzer_eval(m - n == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(n - m == 0); // expected-warning{{TRUE}}
+}
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -174,6 +174,22 @@
return newRanges;
}
+// Returns a set containing the values in the receiving set, intersected with
+// the range set passed as parameter.
+RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
+ const RangeSet &Other) const {
+ PrimRangeSet newRanges = F.getEmptySet();
+
+ for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
+ RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
+ for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
+ newRanges = F.add(newRanges, *j);
+ }
+ }
+
+ 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.
@@ -457,14 +473,21 @@
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
SymbolRef Sym) {
- if (ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym))
- return *V;
-
- BasicValueFactory &BV = getBasicVals();
+ ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
// If Sym is a difference of symbols A - B, then maybe we have range set
// stored for B - A.
- if (const RangeSet *R = getRangeForMinusSymbol(State, Sym))
+ BasicValueFactory &BV = getBasicVals();
+ const RangeSet *R = getRangeForMinusSymbol(State, Sym);
+
+ // If we have range set sotred for both A - B and B - A then calculate the
+ // effective range set by intersecting the range set for A - B and the
+ // negated range set of B - A.
+ if (V && R)
+ return V->Intersect(BV, F, R->Negate(BV, F));
+ if (V)
+ return *V;
+ if (R)
return R->Negate(BV, F);
// Lazily generate a new RangeSet representing all possible values for the
Index: include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
@@ -114,7 +114,8 @@
public:
RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
llvm::APSInt Upper) const;
-
+ RangeSet Intersect(BasicValueFactory &BV, Factory &F,
+ const RangeSet &Other) const;
RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
void print(raw_ostream &os) const;
Index: test/Analysis/constraint_manager_negate_difference.c
===================================================================
--- test/Analysis/constraint_manager_negate_difference.c
+++ test/Analysis/constraint_manager_negate_difference.c
@@ -96,3 +96,10 @@
return;
clang_analyzer_eval(n - m <= 0); // expected-warning{{TRUE}}
}
+
+void effective_range(int m, int n) {
+ assert(m - n >= 0);
+ assert(n - m >= 0);
+ clang_analyzer_eval(m - n == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(n - m == 0); // expected-warning{{TRUE}}
+}
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -174,6 +174,22 @@
return newRanges;
}
+// Returns a set containing the values in the receiving set, intersected with
+// the range set passed as parameter.
+RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
+ const RangeSet &Other) const {
+ PrimRangeSet newRanges = F.getEmptySet();
+
+ for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
+ RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
+ for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
+ newRanges = F.add(newRanges, *j);
+ }
+ }
+
+ 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.
@@ -457,14 +473,21 @@
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
SymbolRef Sym) {
- if (ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym))
- return *V;
-
- BasicValueFactory &BV = getBasicVals();
+ ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
// If Sym is a difference of symbols A - B, then maybe we have range set
// stored for B - A.
- if (const RangeSet *R = getRangeForMinusSymbol(State, Sym))
+ BasicValueFactory &BV = getBasicVals();
+ const RangeSet *R = getRangeForMinusSymbol(State, Sym);
+
+ // If we have range set sotred for both A - B and B - A then calculate the
+ // effective range set by intersecting the range set for A - B and the
+ // negated range set of B - A.
+ if (V && R)
+ return V->Intersect(BV, F, R->Negate(BV, F));
+ if (V)
+ return *V;
+ if (R)
return R->Negate(BV, F);
// Lazily generate a new RangeSet representing all possible values for the
Index: include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
@@ -114,7 +114,8 @@
public:
RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
llvm::APSInt Upper) const;
-
+ RangeSet Intersect(BasicValueFactory &BV, Factory &F,
+ const RangeSet &Other) const;
RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
void print(raw_ostream &os) const;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
