Skip to content

Implement inlining / optimizations on continuation IR #1343

@b-studios

Description

@b-studios

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.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type
    No fields configured for issues without a type.

    Projects

    Status

    Todo

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions