Zero alloc: don't loose witnesses#2353
Closed
gretay-js wants to merge 12 commits intooxcaml:zero_alloc_recfrom
Closed
Zero alloc: don't loose witnesses#2353gretay-js wants to merge 12 commits intooxcaml:zero_alloc_recfrom
gretay-js wants to merge 12 commits intooxcaml:zero_alloc_recfrom
Conversation
This allows us to get rid of a lot of machinery for tracking and resolving unresolved depedencies. Conservative on functions that have mutually recursive calls or forward calls.
1) Keep unresolved functions around until the end of the compilation unit 2) Naively compute fixed point at the end of the unit
t.approx should only be used for self rec that has no other unresolved dependencies.
Pass [keep_witnesses ] as an argument to [Analysis.create] instead of using default initial value and mutating it later.
otherwise we loose witnesses sometimes
76f46cb to
6cfbe64
Compare
xclerc
approved these changes
Mar 13, 2024
Contributor
xclerc
left a comment
There was a problem hiding this comment.
Do we have an idea of the size of the
witness sets in practice? With the
comparision over the domain now
possibly involving an inclusion test,
the cost could increase significantly.
Contributor
Author
I am collecting some statistics on this RP and it's baseline #2290. |
Contributor
Author
|
I messed up the repo/branch in this PR, sorry. I am closing this in favor of #2354 to reduce the confusion. We can continue the discussion there. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
There is a mismatch in handling witnesses:
V.lessequalignores them andV.joindoes not. As a result, witnesses discovered in the last iteration of a fixed point computation might be lost, if there are already other witnesses for the same component.The analysis uses
V.lessequal new_value valueto detect fixed points and will not join thenew_valueto the preiously computed value if the only difference is in witnesses.This is not a soundness problem in the sense that the check will not miss allocations, but it might not return all allocations as witnesses. We do not guarantee that all witnesses will be reported, but it is a nice property to have. We rely on the witnesses produced by the analysis to visualize allocations and not only to check annotations. Having consistent output also makes testing easier.
This PR fixes it "properly" by taking witnesses into account in
V.lessequaland refactoring some other witness related checks to make it clear that we are allowed to ignore witnesses of "expected" values that come from annotations, and not the computed values. The downside of this approach is that the fixpoint can take longer: the height of the abstract domain now depends on the size of the input file in the worst case, instead of being constant height of3. I think that the bad case cannot happen in practice because of the order or propagation of witnesses along all the control flow paths within a loop before checking for a fixed point.An alternative is to call
joineven whenlessequalis true. It works too but feels like a hack.For example, the output of existing test
fail19.mlchanges depending on the order in which functions are emitted in the file:-function-layout topologicalincludesprobewitness and with thesourcelayout it doesn't. This happens because the fixpoint for "forward defined" functions discovered a new witness but the value was alreadyTop, so the new witness is not recorded. I haven't found a way to reproduce this on main yet.On top of #2290.