Skip to content
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

Consider pointees separately for refinement #1659

Open
wants to merge 5 commits into
base: master
Choose a base branch
from

Conversation

michael-schwarz
Copy link
Member

Closes #1658

src/analyses/baseInvariant.ml Outdated Show resolved Hide resolved
src/analyses/baseInvariant.ml Outdated Show resolved Hide resolved
@sim642
Copy link
Member

sim642 commented Jan 24, 2025

I started thinking about this more in relation to double dereferences, etc and realized this should be some kind of recursive process because pointers can be refined at every level.
For example

p → {&q, &r}
q → {&x, &y}
r → {&z, &w}
x → {1}
y → {2}
z → {1}
w → {3}

Assuming **p == 2 should refine p → {&q} and q → {&y}.
Seems like Mem should just recurse (while refining the pointer) and Var would be the base case.

@sim642
Copy link
Member

sim642 commented Jan 24, 2025

Or perhaps not be so ambitious and handle nested dereferences... It's surprisingly tricky to get right even in very simple theoretical setting (the unassume paper appendix on pointers). We spent over an hour with Vesal trying to get it right in a semi-general case (where lvalues are sequences of derefs ending with a variable, so no arbitrary expressions in dereference, nor offsets). The formal definition is also very inefficient in subtle ways because the AST of such lvalues is in the wrong direction compared to the order of dereferencing pointers (which happens from inside out).
It's worth revisiting separately to not block this PR.

@michael-schwarz
Copy link
Member Author

I have now somewhat generalized the handling here. Recursive pointers etc are not considered yet, we can do this in a separate PR if we want to be ambitious.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Refine pointer sets upon assertion about pointee
2 participants