こんにちは､びしょ〜じょです｡ 年明けに買った対洗濯物用乾燥機のおかげで窓を開けたりカーテンレールにハンガーを吊るす日々が終わりました｡ ところで2月分の電気代はすでに1月分を越えようとしています｡

1. はじめに

今年は4年次なので卒業研究! ということでjoin pointを追加したコンパイラ中間言語の設計と､その上での最適化を定義してやっていきました｡ 実装はこちら

卒研発表をスライドを作るためにも､何をしたかを噛み砕いて文に起こしてみたいと思います｡

2. 関連研究

PLDI 2017で『Compiling without Continuations』¹という発表がありました｡ 継続の緑の本をもじったタイトルですが､CPSと直接戦っている感じではないです｡ join pointと呼ばれるものを明示的に扱うことでコードサイズの爆発を抑えたり高速に動作するターゲット言語に変換しようという試みです｡

2-1. join pointとは

プログラム2.1における分岐した制御フローが合流する場所をjoin pointと呼ぶ｡ あるいは制御フローグラフ2.2の赤点で囲んだ部分｡

let j4 x = e4 in let j5 y = e5 in
  if e1 then (if e2 then j4 m else j5 n
  else (if e3 then j4 o else j5 p)

図2.2 制御フローグラフ

CPSでは継続になるし､ANFではコード複製で表現することになる｡ ここで最適化するとコードサイズがボワーっとなってしまう｡ そこでMaurerらはSystem FJ${\text{System F}}_J$という､合流点を明示的に扱う中間言語を提案した｡ 合流点を用いることでコードサイズの爆発が抑えられ､さらに再帰的な合流点を用いることでstream fusionができることを示した｡

しかしSystem Fjは純粋な必要呼びの､Haskellのような言語を対象としたコンパイラ中間言語として設計されたので､ジャバなどの広く使われているプログラム言語とはギャップがある｡

3. 本研究

System Fjとその困った点を踏まえて､非純粋な値呼びの､明示的な合流点を持つコンパイラ中間言語Joel$Joel$を提案する｡ 非純粋性として､多くのプログラム言語で使われており､合流点と競合しそうなコントロールエフェクトを持っている例外を追加した｡

例外を考慮した最適化を定義した｡ 評価コンテキストをばらまく､commuting conversionの一種である最適化がtry-with式の位置を変えてトライキャッチプリキュアのメタモルフォーゼに失敗してプログラムの意味が変わってしまうのを防ぐために､ try-with式の含まれない評価コンテキストを新たに定義し､最適化規則に用いた｡

4. 性能評価

Joel上の最適化を評価するため､CPS上で最適化されて生成されたターゲット言語との比較をおこなった｡ ソース言語にはOCamlのサブセットであるCore MLを新たに定義し､!!!!ターゲット言語はOCamlとした｡!!!! これがあまりよくなかった｡

CPSも､Double-Barreled CPSをもとに複数の例外をハンドルできるような体系を新たに定義した｡

stream fusionがうまくいったけど全然速くならなかったという結果でした(このへんの例)｡ 予備実験をすべきでしたが､つまるところ以下の例がOCamlではほとんど同じ速度で実行されます｡

let map f xs =
  let rec work = function
    | x :: xs -> f x :: work xs
    | [] -> []
  in work xs

let fold f z xs =
  let rec work z = function
    | x :: xs -> work (f z x) xs
    | [] -> z
  in work z xs

let test1 arg =
  fold (+) 0 (map (fun x -> x * x) arg)

let test2 arg = fold (fun x y -> x + y * y) 0 arg

なんでOCamlこれ同じ速度で動くんだ､分からんということでここからなんとかしなければならない…｡ ちなみにmapを20回くらいやったものと(fun x y -> x + (y * y * y * y * ... * y))をfoldに渡すものだと実行速度に差が出ました｡ 同じようなコードをLuaで書いたら即差が出ましたので､ターゲット言語によってはしっかり実行速度に関してアドが言えるんじゃないでしょうか｡

生成されるコードサイズに関しては､Joelによる最適化を経て得られたものが一番小さかったので､そこはadvantageがあったと言えます｡

5. おわりに

終わらないんだよなぁ…