Add Constructed Product Result Optimisation to CakeML
- Dominant language
- Standard ML
- Stars
- 1.2k
- Forks
- 104
- Avg merge
- 2d 21h
- Merged PRs (30d)
- 16
Description
Functions frequently return values as tuples. At present, returning a tuple in CakeML will always produce heap allocation, which is pointless in cases where the caller immediately pattern matches on the tuple and only uses the content rather than the tuple itself.
This PR is about implementing a form of [Constructed Product Result](https://www.microsoft.com/en-us/research/publication/constructed-product-result-analysis-haskell/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fsimonpj%2Fpapers%2Fcpr%2Fcpr.ps.gz) optimisation for CakeML. The analysis would identify functions, e.g. `foo`, that always return something of a specific tuple shape, e.g. `(x, y, z)`, transform each such function into two functions:
- `foo_mv` same as the original `foo` but returns multiple values `x, y, z` where `foo` returned `(x, y, z)`
- `foo` is now just `foo args = let x, y, z = foo_mv args in (x, y, z)`
There would be an inlining phase that attempts to inline `foo` functions as aggressively as possible so that the tuple allocation can be dead-code eliminated.
I propose that this PR is implemented after PR #837, and that BVI and DataLang are adjusted to allow multiple return values. The new optimisations, i.e. `foo_mv` introduction and `foo` inlining, could then be BVI-to-BVI optimisations.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.