effekt-lang / effekt-lang/effekt

Implement inlining / optimizations on continuation IR

Open
#1,343 0 comments 1 reaction 0 assignees View on GitHub
area:chez area:cps area:js optimizer-wishlist
Dominant language
Scala
Stars
469
Forks
41
Avg merge
1d 16h
Merged PRs (30d)
23

Description

Currently we only perform optimizations on Core, but not on CPS.

Take the following example

```
def foo(n: Int): Int = {
def bar(m: Int): Int = {
if (m == 0) { 0 }
else bar(m - 1)
}
if (n == 0) { 1 }
else {
println(bar(n))
foo(n - 1)
}
}

def main() = println(foo(1))
```

it will translate to the following JS

```
function foo_0(n_0, ks_1, k_1) {
function bar_0(m_0, ks_0, k_0) {
bar_1: while (true) {
if (m_0 === (0)) {
return () => k_0(0, ks_0);
} else {
/* prepare call */
const tmp_m_0 = m_0;
m_0 = (tmp_m_0 - (1));
continue bar_1;
}
}
}
if (n_0 === (0)) {
return () => k_1(1, ks_1);
} else {
return bar_0(n_0, ks_1, (v_r_0, ks_2) => {
const ret_0 = '' + v_r_0;
const v_r_1 = $effekt.println(ret_0);
return foo_0((n_0 - (1)), ks_2, k_1);
});
}
}

function main_0(ks_3, k_2) {
return foo_0(1, ks_3, (v_r_2, ks_4) => {
const ret_1 = '' + v_r_2;
const v_r_3 = $effekt.println(ret_1);
return () => k_2(v_r_3, ks_4);
});
}
```
which is not optimal. The function `bar_0` is not recursive in the IR and used only once, so it can be inlined. This will result in a nested loop, such as in the handwritten draft below:

```
function foo_0(n_0, ks_1, k_1) {
foo_0: while (true) {
if (n_0 === (0)) {
return () => k_1(1, ks_1);
} else {
bar_1: while (true) {
if (m_0 === (0)) {
const ret_0 = '' + 0;
const v_r_1 = $effekt.println(ret_0);
const n_0_tmp = n_0
n_0 = n_0_tmp - (1)
continue foo_0;
} else {
/* prepare call */
const tmp_m_0 = m_0;
m_0 = (tmp_m_0 - (1));
continue bar_1;
}
}
}
}
}
```

Task: create a new phase `Inline` or similar (starting off something like `Contify`) that performs inlining on `cps`. This will most like require duplicating the usage analysis from `core`.

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.