Zero alloc: more precise handling of recursive functions#2290
Merged
Zero alloc: more precise handling of recursive functions#2290
Conversation
xclerc
approved these changes
Mar 6, 2024
fb0ff9a to
436e63b
Compare
Contributor
Author
|
The new fixpoint computation may have pathological cases with very high overhead on compilation time and memory, esp if we revert the order of functions back to source code order (see #2287). Benchmarking in progress. |
This was referenced Mar 7, 2024
xclerc
approved these changes
Mar 11, 2024
Contributor
xclerc
left a comment
There was a problem hiding this comment.
I was already pondering that during my first
review, but I think it would be useful to leave
a comment about why the fixpoint computations
are guaranteed to terminate. I agree it is fairly
obvious given the current domain, so perhaps
it is about documenting the properties that
must be observed on the domain to guarantee
the termination.
76f46cb to
6cfbe64
Compare
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.
6cfbe64 to
9c347d5
Compare
gretay-js
added a commit
to gretay-js/flambda-backend
that referenced
this pull request
Apr 11, 2024
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.
The analysis of recursive functions is precise with respect to the abstraction but not efficient. The intent is to make it easy to review for correctness. The idea is to save the body of
Machfunctions that contain unresolved calls (i.e., calls to functions that appears later in the same compilation unit and hence have not yet have a summary). Then, at the end of the compilation unit, computed the fixed point by reanalyzing these functions.This PR may be easier to read commit-by-commit. The first commit deletes complicated tracking of dependencies for unresolved functions and conservative treats all unreasolved calls as Top. The second commit adds a very simple tracking of unresolved functions (no dependency tracking) and fixed point computation.