-
Notifications
You must be signed in to change notification settings - Fork 10.8k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
solver doesn't realize that z > x && z < y
is unsat with the fact x == y
#62215
Comments
@llvm/issue-subscribers-clang-static-analyzer |
@hallo-wereld: Please elaborate. |
Sorry, |
Confirmed: https://godbolt.org/z/q6W8fhr67
We could probably get this work if we would accept some runtime cost. |
z > x && z < y
is unsatisfiable with the fact x == y
z > x && z < y
is unsat with the fact x == y
That idea does sound promising! Thanks :) |
Is it possible that CSA did not know the values of x, y, and z, so it directly determined unknown during the visit? |
In the example of the issue, |
I feel that the issue may be caused by the CSA visiting comparison statements and returning unknowns? I'm not sure about this. I should test it. Thank you! |
Let me explain. Now, if we learn that [1]: You can see that if you replace |
Thank you for such a detailed explanation. I have a fever and am seeing a doctor. I will read it carefully later. Thank you again!
…---Original---
From: "Balazs ***@***.***>
Date: Tue, Oct 31, 2023 00:41 AM
To: ***@***.***>;
Cc: "Tianxing ***@***.******@***.***>;
Subject: Re: [llvm/llvm-project] solver doesn't realize that `z > x && z < y`is unsat with the fact `x == y` (Issue #62215)
Is it possible that CSA did not know the values of x, y, and z, so it directly determined unknown during the visit?
In the example of the issue, x, y, z were all symbolic, because they are the parameters of the top-level function being analyzed (where we don't know anything about their values). Other than that, I'm not sure if I understood your question.
I feel that the issue may be caused by the CSA visiting comparison statements and returning unknowns? I'm not sure about this. I should test it. Thank you!
Let me explain.
CSA maps symbols to equalivalence classes (eqclasses), and then maps eqclasses to range sets as constraints.
The rationale is that if x is now known to be equal to y, everything that they were equal to should be all equal and share the constraints we learned.
Now, if we learn that x == y, then learn that z > x; and then try to evaluate the expression z < y one would expect that we recognize that y could be substituted by x (or any other member of its eqclass). And AFAIK we would successfully recognize the pattern z < x when simplifying the expression and eliminate that path [1]. However, since we don't do such substitution, the pattern won't match and the path won't be eliminated.
What I suggested was to not try to improve the simplification of relational operators, but rather brute-force try to use each member of the eqclass and try each combination. (yes, N*M combinations, where X RELOP Y, N := |eqclass(X)|, M := |eqclass(Y)|`, arguing that usually, eqclasses are really small.
[1]: You can see that if you replace assert(z < y); by assert(z < x);, we would successfully eliminate the path, and the FP.
It is because we have seen z > x before; thus z < x can't be also true; and this is recognized by some pattern when the z < x is simplified.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
You are receiving this because you commented.Message ID: ***@***.***>
|
I think you can get this done within |
…dictions The idea is that if we see a `X RELOP Y` being constrained to a RangeSet `S`, then check the eqclasses of X and Y respectively and for `X' RELOP Y'` SymSymExprs and try to infer their ranges. If there is no contradiction with any of the equivalent alternatives, then intersecting all these RangeSets should never be empty - aka. there should be a value satisfying the constraints we have. It costs around `|eqclass(X)| + |eqclass(y)|`. The approach has its limitations, as demonstrated by `gh_62215_contradicting_nested_right_equivalent`, where we would need to apply the same logic, but on a sub-expression of a direct operand. Before the patch, line 90, 100, and 112 would be reachable; and become unreachable after this. Line 127 will remain still reachable, but keep in mind that when cross-checking with Z3 (aka. Z3 refutation), then all 4 reports would be eliminated. The idea comes from llvm#62215 (comment) Fixes llvm#62215
@martong Thanks for the idea, when I read it it clicked and I could not resist experimenting with it today. |
version: Clang trunk
args:
Clang Static Analyzer doesn't realize that
z > x && z < y
is unsatisfiable with the factx == y
. See it live: https://godbolt.org/z/Te3d9GPM6The text was updated successfully, but these errors were encountered: