effekt-lang / effekt-lang/effekt
Implement inlining / optimizations on continuation IR
- 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.