Add simple form of higher-order inlining
- Dominant language
- Standard ML
- Stars
- 1.2k
- Forks
- 104
- Avg merge
- 2d 21h
- Merged PRs (30d)
- 16
Description
I suspect CakeML would do better on a number of benchmarks and real-world examples if we optimised `tabulate`, `map`, `filter`, `genlist`, `every` etc. for cases where they take a known closure as an argument and pass this closure to recursive calls unchanged.
Example:
fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs = map (fn n => n+1) ys
should become (step 1):
fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs =
(let
fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
in map end) (fn n => n+1) ys
which becomes (step 2):
fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs =
(let
fun map f [] = []
| map f (x::xs) = ((fn n => n+1) x) :: map f xs
in map end) 0 ys
which becomes (step 3):
fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs =
(let
fun map f [] = []
| map f (x::xs) = (let val n = x in n+1 end) :: map f xs
in map end) 0 ys
Such an optimisation would benefit from coming after `clos_known`. In fact, the crucial steps 2-3 would follow by `clos_call` and various `bvl` optimisations, if the last `f x` produced by step 1 was annotated with the closure number of `fn n => n+1`.
@SOwens tells me that [this paper](http://manticore.cs.uchicago.edu/papers/icfp14-reflow.pdf) is relevant, even though we would not aim at anything this comprehensive.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.