baloghadamsoftware created this revision.
Since the range-based constraint manager (default) is weak in handling
comparisons where symbols are on both sides it is wise to rearrange them to
have symbols only on the left side. Thus e.g. `A + n >= B + m` becomes `A - B
>= m - n` which enables the constraint manager to store a range `m - n ..
MAX_VALUE` for the symbolic expression `A - B`. This can be used later to check
whether e.g. `A + k == B + l` can be true, which is also rearranged to `A - B
== l - k` so the constraint manager can check whether `l - k` is in the range
(thus greater than or equal to `m - m`).
https://reviews.llvm.org/D35109
Files:
lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
test/Analysis/std-c-library-functions.c
test/Analysis/svalbuilder-rearrange-comparisons.c
Index: test/Analysis/svalbuilder-rearrange-comparisons.c
===================================================================
--- /dev/null
+++ test/Analysis/svalbuilder-rearrange-comparisons.c
@@ -0,0 +1,156 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_dump(int x);
+void clang_analyzer_printState();
+
+int f();
+
+void compare_different_symbol() {
+ int x = f(), y = f();
+ clang_analyzer_dump(x); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(y); // expected-warning{{conj_$5{int}}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$2{int}) - (conj_$5{int})) == 0}}
+}
+
+void compare_different_symbol_plus_left_int() {
+ int x = f()+1, y = f();
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(y); // expected-warning{{conj_$5{int}}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$5{int}) - (conj_$2{int})) == 1}}
+}
+
+void compare_different_symbol_minus_left_int() {
+ int x = f()-1, y = f();
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(y); // expected-warning{{conj_$5{int}}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$2{int}) - (conj_$5{int})) == 1}}
+}
+
+void compare_different_symbol_plus_right_int() {
+ int x = f(), y = f()+2;
+ clang_analyzer_dump(x); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$5{int}) + 2}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$2{int}) - (conj_$5{int})) == 2}}
+}
+
+void compare_different_symbol_minus_right_int() {
+ int x = f(), y = f()-2;
+ clang_analyzer_dump(x); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$5{int}) - 2}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$5{int}) - (conj_$2{int})) == 2}}
+}
+
+void compare_different_symbol_plus_left_plus_right_int() {
+ int x = f()+2, y = f()+1;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) + 2}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$5{int}) + 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$5{int}) - (conj_$2{int})) == 1}}
+}
+
+void compare_different_symbol_plus_left_minus_right_int() {
+ int x = f()+2, y = f()-1;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) + 2}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$5{int}) - 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$5{int}) - (conj_$2{int})) == 3}}
+}
+
+void compare_different_symbol_minus_left_plus_right_int() {
+ int x = f()-2, y = f()+1;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) - 2}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$5{int}) + 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$2{int}) - (conj_$5{int})) == 3}}
+}
+
+void compare_different_symbol_minus_left_minus_right_int() {
+ int x = f()-2, y = f()-1;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) - 2}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$5{int}) - 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{((conj_$2{int}) - (conj_$5{int})) == 1}}
+}
+
+void compare_same_symbol() {
+ int x = f(), y = x;
+ clang_analyzer_dump(x); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(y); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{1 S32b}}
+}
+
+void compare_same_symbol_plus_left_int() {
+ int x = f(), y = x;
+ ++x;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(y); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{0 S32b}}
+}
+
+void compare_same_symbol_minus_left_int() {
+ int x = f(), y = x;
+ --x;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(y); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{0 S32b}}
+}
+
+void compare_same_symbol_plus_right_int() {
+ int x = f(), y = x+1;
+ clang_analyzer_dump(x); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{0 S32b}}
+}
+
+void compare_same_symbol_minus_right_int() {
+ int x = f(), y = x-1;
+ clang_analyzer_dump(x); // expected-warning{{conj_$2{int}}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{0 S32b}}
+}
+
+void compare_same_symbol_plus_left_plus_right_int() {
+ int x = f(), y = x+1;
+ ++x;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{1 S32b}}
+}
+
+void compare_same_symbol_plus_left_minus_right_int() {
+ int x = f(), y = x-1;
+ ++x;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{0 S32b}}
+}
+
+void compare_same_symbol_minus_left_plus_right_int() {
+ int x = f(), y = x+1;
+ --x;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$2{int}) + 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{0 S32b}}
+}
+
+void compare_same_symbol_minus_left_minus_right_int() {
+ int x = f(), y = x-1;
+ --x;
+ clang_analyzer_dump(x); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(y); // expected-warning{{(conj_$2{int}) - 1}}
+ clang_analyzer_dump(x == y);
+ // expected-warning@-1{{1 S32b}}
+}
Index: test/Analysis/std-c-library-functions.c
===================================================================
--- test/Analysis/std-c-library-functions.c
+++ test/Analysis/std-c-library-functions.c
@@ -57,8 +57,7 @@
size_t y = fread(buf, sizeof(int), 10, fp);
clang_analyzer_eval(y <= 10); // expected-warning{{TRUE}}
size_t z = fwrite(buf, sizeof(int), y, fp);
- // FIXME: should be TRUE once symbol-symbol constraint support is improved.
- clang_analyzer_eval(z <= y); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(z <= y); // expected-warning{{TRUE}}
}
ssize_t getline(char **, size_t *, FILE *);
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===================================================================
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -554,6 +554,75 @@
if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
+ // If comparing two symbolic expressions of the format S, S+n or S-n
+ // rearrange the comparison by moving symbols to the left side and the
+ // concrete integer to the right. This enables the range based constraint
+ // manager to handle these comparisons.
+ if (BinaryOperator::isComparisonOp(op) &&
+ rhs.getSubKind() == nonloc::SymbolValKind) {
+ SymbolRef rSym = rhs.castAs<nonloc::SymbolVal>().getSymbol();
+ const llvm::APSInt *lInt = nullptr, *rInt = nullptr;
+ BinaryOperator::Opcode lop, rop;
+
+ if (const SymIntExpr *lSymIntExpr = dyn_cast<SymIntExpr>(Sym)) {
+ lInt = &lSymIntExpr->getRHS();
+ Sym = lSymIntExpr->getLHS();
+ lop = lSymIntExpr->getOpcode();
+ }
+ if (const SymIntExpr *rSymIntExpr = dyn_cast<SymIntExpr>(rSym)) {
+ rInt = &rSymIntExpr->getRHS();
+ rSym = rSymIntExpr->getLHS();
+ rop = rSymIntExpr->getOpcode();
+ }
+
+ bool reverse; // Avoid negative numbers in case of unsigned types
+ const llvm::APSInt *newRhs;
+ if (lInt && rInt) {
+ if (lop != rop) {
+ newRhs = BasicVals.evalAPSInt(BO_Add, *lInt, *rInt);
+ reverse = (lop == BO_Add);
+ } else {
+ if (*lInt >= *rInt) {
+ newRhs = BasicVals.evalAPSInt(BO_Sub, *lInt, *rInt);
+ reverse = (lop == BO_Add);
+ } else {
+ newRhs = BasicVals.evalAPSInt(BO_Sub, *rInt, *lInt);
+ reverse = (lop == BO_Sub);
+ }
+ }
+ } else if (lInt) {
+ newRhs = lInt;
+ reverse = (lop == BO_Add);
+ } else if (rInt) {
+ newRhs = rInt;
+ reverse = (rop == BO_Sub);
+ } else {
+ newRhs = &BasicVals.getValue(0, Sym->getType());
+ reverse = false;
+ }
+
+ // If we have A <= B unsigned, A - B <= 0 would mean A - B == 0, thus
+ // A == B which may cause false positives. So reverse it to B - A >= 0.
+ if (*newRhs == 0) {
+ reverse = (op == BO_LT || op == BO_LE);
+ }
+
+ // If the two symbols are equal, compare only the integers and return
+ // the concrete result. If they are different, return the rearranged
+ // expression.
+ if (Sym == rSym) {
+ return nonloc::ConcreteInt(*BasicVals.evalAPSInt(op, BasicVals.getValue(0, Sym->getType()), *newRhs));
+ } else {
+ if (reverse) {
+ op = BinaryOperator::reverseComparisonOp(op);
+ }
+ const SymExpr *newLhs = reverse ?
+ SymMgr.getSymSymExpr(rSym, BO_Sub, Sym, rSym->getType()) :
+ SymMgr.getSymSymExpr(Sym, BO_Sub, rSym, Sym->getType());
+ return makeNonLoc(newLhs, op, *newRhs, resultTy);
+ }
+ }
+
// Give up -- this is not a symbolic expression we can handle.
return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
