Skip to content

Consider relooping recursive LetDefs on JS CPS #1341

@jiribenes

Description

@jiribenes

If we remember which LetDefs are recursive, we can also reloop recursive functions (most often workers discovered by previous opt phases):

Image

Source program:

def myeach[A](list: List[A]) { f: A => Unit }: Unit = list match {
  case Cons(x, xs) => f(x); myeach(xs) {f}
  case Nil() => ()
}

def main() = {
  [(0, 'a'), (1, 'b'), (2, 'c')].myeach {
    case Tuple2(i, x) => println(show(i) ++ ": " ++ show(x))
  }
}

So it'd mean turning the myeach_worker_... below

def main_7486 = {  | ks_10277, k_10278 => 
  def myeach_worker_10204 = { (list_10205)  | ks_10279, k_10280 => 
    list_10205 match {
      case Cons_2895 (x_10213, xs_10214) => {
        x_10213 match {
          case Tuple2_424 (i_10249, x_10250) => {
            let! ret_10251 = showBuiltin_45(i_10249)
            let! ret_10253 = showBuiltin_49(x_10250)
            let! v_r_10257 = println_32(infixPlusPlus_62(infixPlusPlus_62(ret_10251, ": "), ret_10253))
            myeach_worker_10204(xs_10214) @ ks_10279, k_10280
          }
        }
      }
      case Nil_2894 () => {
        jump k_10280(()) @ ks_10279
      }
    }
  }
  myeach_worker_10204(make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(0, 97), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(1, 98), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(2, 99), make List_2564 Nil_2894())))) @ ks_10277, k_10278
}

into a letrec:

def main_7486 = {  | ks_10399, k_10400 => 
  letrec myeach_worker_10326 = { (list_10327) | ks_10401 => 
    list_10327 match {
      case Cons_2895 (x_10335, xs_10336) => {
        x_10335 match {
          case Tuple2_424 (i_10371, x_10372) => {
            let! ret_10373 = showBuiltin_45(i_10371)
            let! ret_10375 = showBuiltin_49(x_10372)
            let! v_r_10379 = println_32(infixPlusPlus_62(infixPlusPlus_62(ret_10373, ": "), ret_10375))
            jump myeach_worker_10326(xs_10336) @ ks_10401
          }
        }
      }
      case Nil_2894 () => {
        jump k_10400(()) @ ks_10401
      }
    }
  }
  jump myeach_worker_10326(make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(0, 97), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(1, 98), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(2, 99), make List_2564 Nil_2894())))) @ ks_10399
}

and then teaching the CPS IR -> JS transformer how to deal with these self loops.
Though note that in this example, it seems to have helped only by eliminating a single function call by replacing it with mutable state...

I do have a prototype of this locally, but the code is very low quality.

Metadata

Metadata

Assignees

No one assigned

    Labels

    area:jsexperimentExperimental branch, do not merge!

    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