This is an automated archive made by the Lemmit Bot.

The original was posted on /r/programminglanguages by /u/PurpleUpbeat2820 on 2024-10-20 16:13:11+00:00.

Finally managed to get my new inlining optimization pass up and running on my minimal IR:

let optimise is_inlinable program =
  let to_inline =
    List.filter (fun (_, (_, body)) -> is_inlinable body) program
    |> Hashtbl.of_list in
  let rec compile_blk env = function
    | Fin(_, Ret vs), [] -> mk_fin(Ret(subst_values env vs))
    | Fin(_, Ret rets), (env2, fn_rets, blk)::rest ->
      let rets = List.map (subst_value env) rets in
      let env2 = List.fold_right2 (fun (_, var) -> IntMap.add var) fn_rets rets env2 in
      compile_blk env2 (blk, rest)
    | Fin(_, If(v1, cmp, v2, blk1, blk2)), rest ->
      let v1 = subst_value env v1 in
      let v2 = subst_value env v2 in
      mk_fin(If(v1, cmp, v2, compile_blk env (blk1, rest), compile_blk env (blk2, rest)))
    | Defn(_, Call(rets, (Lit(`I _ | `F _) | Var _ as fn), args), blk), rest ->
      let env, rets = List.fold_left_map rename_var env rets in
      mk_defn(Call(rets, subst_value env fn, subst_values env args), compile_blk env (blk, rest))
    | Defn(_, Call(rets, Lit(`A fn), args), blk), rest ->
      let env, rets = List.fold_left_map rename_var env rets in
      let args = subst_values env args in
      match Hashtbl.find_opt to_inline fn with
      | Some(params, body) ->
        let env2, params = List.fold_left_map rename_var IntMap.empty params in
        let env2 = List.fold_right2 (fun (_, var) -> IntMap.add var) params args env2 in
        compile_blk env2 (body, (env, rets, blk)::rest)
      | _ -> mk_defn(Call(rets, Lit(`A fn), args), compile_blk env (blk, rest)) in
  List.map (fun (fn, (params, body)) ->
    let env, params = List.fold_left_map rename_var IntMap.empty params in
    fn, (params, compile_blk env (body, []))) program

Rather proud of that! 30 lines of code and it can inline anything into anything including inlining mutually-recursive functions into themselves.

With that my benchmarks are now up to 3.75x faster than C (clang -O2). Not too shabby!

The next challenge appears to be figuring out what to inline. I’m thinking of trialling every possible inline (source and destination) using my benchmark suite to measure what is most effective. Is there a precedent for something like that? Are results available anywhere?

What heuristics do people generally use? My priority has been always inlining callees that are linear blocks of asm instructions. Secondarily, I am trying inlining everything provided the result doesn’t grow too much. Perhaps I should limit the number of live variables across function calls to avoid introducing spilling.