CakeML / CakeML/cakeml

Add Constructed Product Result Optimisation to CakeML

Open
#838 1 comment 0 reactions 1 assignee Claimed by @daole2904 View on GitHub
high reward medium effort student project
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.