ASDenysPetrov updated this revision to Diff 260331.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D78933/new/
https://reviews.llvm.org/D78933
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/constraint_manager_conditions.cpp
Index: clang/test/Analysis/constraint_manager_conditions.cpp
===================================================================
--- /dev/null
+++ clang/test/Analysis/constraint_manager_conditions.cpp
@@ -0,0 +1,133 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+//reversed
+
+void comparison_reversed_gt(int x, int y) {
+ if (x > y)
+ clang_analyzer_eval(y < x); // expected-warning{{TRUE}}
+ else
+ clang_analyzer_eval(y < x); // expected-warning{{FALSE}}
+}
+
+void comparison_reversed_ge(int x, int y) {
+ if (x >= y)
+ clang_analyzer_eval(y <= x); // expected-warning{{TRUE}}
+ else
+ clang_analyzer_eval(y <= x); // expected-warning{{FALSE}}
+}
+
+void comparison_reversed_lt(int x, int y) {
+ if (x < y)
+ clang_analyzer_eval(y > x); // expected-warning{{TRUE}}
+ else
+ clang_analyzer_eval(y > x); // expected-warning{{FALSE}}
+}
+
+void comparison_reversed_le(int x, int y) {
+ if (x <= y)
+ clang_analyzer_eval(y >= x); // expected-warning{{TRUE}}
+ else
+ clang_analyzer_eval(y >= x); // expected-warning{{FALSE}}
+}
+
+void comparison_reversed_eq(int x, int y) {
+ if (x == y)
+ clang_analyzer_eval(y == x); // expected-warning{{TRUE}}
+ else
+ clang_analyzer_eval(y == x); // expected-warning{{FALSE}}
+}
+
+void comparison_reversed_ne(int x, int y) {
+ if (x != y)
+ clang_analyzer_eval(y != x); // expected-warning{{TRUE}}
+ else
+ clang_analyzer_eval(y != x); // expected-warning{{FALSE}}
+}
+
+//opposite
+
+void comparison_opposite_gt(int x, int y) {
+ if (x > y) {
+ clang_analyzer_eval(x < y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y > x); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x <= y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y >= x); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y == x); // expected-warning{{FALSE}}
+ } else {
+ clang_analyzer_eval(x < y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y > x); // expected-warning{{TRUE}}
+ clang_analyzer_eval(x <= y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y >= x); // expected-warning{{TRUE}}
+ clang_analyzer_eval(x == y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y == x); // expected-warning{{TRUE}}
+ }
+}
+
+void comparison_opposite_ge(int x, int y) {
+ if (x >= y) {
+ clang_analyzer_eval(x < y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y > x); // expected-warning{{FALSE}}
+ } else {
+ clang_analyzer_eval(x < y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y > x); // expected-warning{{TRUE}}
+ }
+}
+
+void comparison_opposite_lt(int x, int y) {
+ if (x < y) {
+ clang_analyzer_eval(x > y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y < x); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x >= y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y <= x); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y == x); // expected-warning{{FALSE}}
+ } else {
+ clang_analyzer_eval(x > y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y < x); // expected-warning{{TRUE}}
+ clang_analyzer_eval(x >= y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y <= x); // expected-warning{{TRUE}}
+ clang_analyzer_eval(x == y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y == x); // expected-warning{{TRUE}}
+ }
+}
+
+void comparison_opposite_le(int x, int y) {
+ if (x <= y) {
+ clang_analyzer_eval(x > y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y < x); // expected-warning{{FALSE}}
+ } else {
+ clang_analyzer_eval(x > y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y < x); // expected-warning{{TRUE}}
+ }
+}
+
+void comparison_opposite_eq(int x, int y) {
+ if (x == y) {
+ clang_analyzer_eval(x > y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y < x); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x < y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y > x); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x != y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y != x); // expected-warning{{FALSE}}
+ } else {
+ clang_analyzer_eval(x > y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y < x); // expected-warning{{TRUE}}
+ clang_analyzer_eval(x < y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y > x); // expected-warning{{TRUE}}
+ clang_analyzer_eval(x != y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y != x); // expected-warning{{TRUE}}
+ }
+}
+
+void comparison_opposite_ne(int x, int y) {
+ if (x != y) {
+ clang_analyzer_eval(x == y); // expected-warning{{FALSE}}
+ clang_analyzer_eval(y == x); // expected-warning{{FALSE}}
+ } else {
+ clang_analyzer_eval(x == y); // expected-warning{{TRUE}}
+ clang_analyzer_eval(y == x); // expected-warning{{TRUE}}
+ }
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -222,6 +222,62 @@
return newRanges;
}
+// Create new RangeSet with ranges between current ranges
+// such that union of them equals to [MIN, MAX]
+// and intersection equals to `empty` RangeSet.
+// Examples:
+// [A, B] => [MIN, A-1] U [B+1, MAX]
+// [MIN, A] U [B, B] U [C, MAX] => [A+1, B-1] U [B+1, C-1]
+RangeSet RangeSet::Invert(BasicValueFactory &BV, Factory &F) const {
+ PrimRangeSet newRanges = F.getEmptySet();
+
+ if (isEmpty())
+ return newRanges;
+
+ const llvm::APSInt &sampleValue = getMinValue();
+ const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
+ const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+
+ iterator i = begin();
+ iterator e = end();
+ llvm::APSInt from = i->From();
+ llvm::APSInt to = i->To();
+
+ // assume we have [A, B] U [C, D]
+
+ // Handle case when the first ranges starts from non-MIN value
+ // [A, B] U [C, D]
+ // ^
+ // [MIN, A-1] add new range here
+ if (from != MIN) {
+ newRanges = F.add(newRanges, Range(MIN, BV.getValue(--from)));
+ }
+
+ // Add intermediate ranges.
+ // [A, B] U [C, D]
+ // ^
+ // [B+1, C-1] add new range here
+ ++i;
+ while (i != e) {
+ from = i->From();
+ const llvm::APSInt &newFrom = BV.getValue(++to);
+ const llvm::APSInt &newTo = BV.getValue(--from);
+ newRanges = F.add(newRanges, Range(newFrom, newTo));
+ to = i->To();
+ ++i;
+ }
+
+ // Handle case when the last ranges ends to non-MAX value
+ // [A, B] U [C, D]
+ // ^
+ // [D+1, MAX] add new range here
+ if (to != MAX) {
+ newRanges = F.add(newRanges, Range(BV.getValue(++to), MAX));
+ }
+
+ return newRanges;
+}
+
void RangeSet::print(raw_ostream &os) const {
bool isFirst = true;
os << "{ ";
@@ -305,8 +361,12 @@
RangeSet::Factory F;
RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
- const RangeSet* getRangeForMinusSymbol(ProgramStateRef State,
- SymbolRef Sym);
+ const SymSymExpr *getAsComparisonSymSymExpr(SymbolRef Sym);
+ const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym);
+ const RangeSet *getRangeForOppositeComparisonSymbol(ProgramStateRef State,
+ SymbolRef Sym);
+ const RangeSet *getRangeForReversedComparisonSymbol(ProgramStateRef State,
+ SymbolRef Sym);
RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
const llvm::APSInt &Int,
@@ -480,14 +540,20 @@
SymbolRef Sym) {
ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
+ // Find a range for reversed copy of the symbol
+ // (for operations comparison only).
+ // E.g. for (x < y) find (y > x)
+ if (auto R = getRangeForReversedComparisonSymbol(State, Sym))
+ return *R;
+
// If Sym is a difference of symbols A - B, then maybe we have range set
// stored for B - A.
- BasicValueFactory &BV = getBasicVals();
const RangeSet *R = getRangeForMinusSymbol(State, Sym);
// If we have range set stored 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.
+ BasicValueFactory &BV = getBasicVals();
if (V && R)
return V->Intersect(BV, F, R->Negate(BV, F));
if (V)
@@ -495,6 +561,12 @@
if (R)
return R->Negate(BV, F);
+ // Find a range for opposite symbol (for operations comparison only).
+ // E.g. for (x < y) find any of
+ // (x > y), (y < x), (x >= y), (y <= x), (x == y), (y == x)
+ if (auto R = getRangeForOppositeComparisonSymbol(State, Sym))
+ return R->Invert(BV, F);
+
// Lazily generate a new RangeSet representing all possible values for the
// given symbol type.
QualType T = Sym->getType();
@@ -538,6 +610,104 @@
return nullptr;
}
+const SymSymExpr *
+RangeConstraintManager::getAsComparisonSymSymExpr(SymbolRef Sym) {
+ if (auto SSE = dyn_cast<SymSymExpr>(Sym)) {
+ auto OP = SSE->getOpcode();
+ // we currently do not support <=> (C++20)
+ if (BinaryOperator::isComparisonOp(OP) && (OP != BO_Cmp))
+ return SSE;
+ }
+ return nullptr;
+}
+
+// Returns ranges only for binary comparison operators
+// when left and right operands are symbolic values.
+// Finds opposite expression in the ConstraintRange map.
+// E.g. Conditions (x >= y), (y <= x), (x == y) makes this (x < y) false.
+// Then the result should be inverted for futher intersection.
+const RangeSet *RangeConstraintManager::getRangeForOppositeComparisonSymbol(
+ ProgramStateRef State, SymbolRef Sym) {
+ auto SSE = getAsComparisonSymSymExpr(Sym);
+ if (!SSE)
+ return nullptr;
+
+ SmallVector<BinaryOperator::Opcode, 3> Ops;
+
+ switch (SSE->getOpcode()) {
+ case BO_LT:
+ Ops.push_back(BO_GT);
+ Ops.push_back(BO_GE);
+ Ops.push_back(BO_EQ);
+ break;
+ case BO_LE:
+ Ops.push_back(BO_GT);
+ break;
+ case BO_GT:
+ Ops.push_back(BO_LT);
+ Ops.push_back(BO_LE);
+ Ops.push_back(BO_EQ);
+ break;
+ case BO_GE:
+ Ops.push_back(BO_LT);
+ break;
+ case BO_EQ:
+ Ops.push_back(BO_LT);
+ Ops.push_back(BO_GT);
+ Ops.push_back(BO_NE);
+ break;
+ case BO_NE:
+ Ops.push_back(BO_EQ);
+ break;
+ default:
+ llvm_unreachable("Given 'BinaryOperator::Opcode' is not supported here");
+ break;
+ }
+
+ auto LHS = SSE->getLHS();
+ auto RHS = SSE->getRHS();
+ QualType T = SSE->getType();
+ SymbolManager &SymMgr = State->getSymbolManager();
+
+ // Assume we have (x < y).
+ const RangeSet *RangeSet = nullptr;
+ for (auto OP : Ops) {
+ // Let's find any of (x >= y), (x > y), (x == y).
+ auto SymSym = SymMgr.getSymSymExpr(LHS, OP, RHS, T);
+ if (RangeSet = State->get<ConstraintRange>(SymSym))
+ break;
+
+ // Or let's find any of (y <= x), (y < x), (y == x).
+ auto ROP = BinaryOperator::reverseComparisonOp(OP);
+ SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T);
+ if (RangeSet = State->get<ConstraintRange>(SymSym))
+ break;
+ }
+ return RangeSet;
+}
+
+// Gets ranges only for binary comparison operators
+// when left and right operands are symbolic values.
+// Finds reversed expression in the ConstraintRange map.
+// E.g. (x >= y) is reversed to (y <= x)
+const RangeSet *RangeConstraintManager::getRangeForReversedComparisonSymbol(
+ ProgramStateRef State, SymbolRef Sym) {
+ auto SSE = getAsComparisonSymSymExpr(Sym);
+ if (!SSE)
+ return nullptr;
+
+ // Assume we have (x < y).
+ // Let's find (y > x).
+ auto LHS = SSE->getLHS();
+ auto RHS = SSE->getRHS();
+ auto OP = SSE->getOpcode();
+ auto ROP = BinaryOperator::reverseComparisonOp(OP);
+ QualType T = SSE->getType();
+ SymbolManager &SymMgr = State->getSymbolManager();
+ auto SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T);
+ return State->get<ConstraintRange>(SymSym);
+}
+
//===------------------------------------------------------------------------===
// assumeSymX methods: protected interface for RangeConstraintManager.
//===------------------------------------------------------------------------===/
Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
===================================================================
--- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
+++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
@@ -116,6 +116,7 @@
RangeSet Intersect(BasicValueFactory &BV, Factory &F,
const RangeSet &Other) const;
RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
+ RangeSet Invert(BasicValueFactory &BV, Factory &F) const;
void print(raw_ostream &os) const;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
