[Paper, ICFP09] Dataflow Optimization Made Simple

by syoyo

Dataflow Optimization Made Simple
John Dias, Norman Ramsey, and Simon Peyton Jones, and Satnam Singh, ICFP 09.

コンパイラが行うデータフロー最適化は、実はコンパイラの教科書で解説されているほど難しくはなく書けるんだよ、というのを示しているらしい.
論文で提案されているデータフロー最適化のフレームワークは、実際に GHC(Haskell コンパイラ)の新しいバックエンドとして採用されているとのこと.

そのためデータフロー最適化フレームワークの実装言語は Haskell で、ターゲットの言語は C–(cminusminus).
C– は GHC の中間言語(の中でも下のほうあたり?)として使われている言語. 見た目は C に近いけど、LLVM IR のようにコンパイラが扱いやすい形式となっている.

論文では、提案するデータフロー最適化のフレームワークを使って以下のような最適化や解析が簡単に実装できることを示している.

– 生存解析(Liveness Analysis)
– 定数畳み込み(Constant Folding)
– 使われない代入の除去(Dead-assignment elimination)

そして、ここが今回の論文のキモであろう部分: コンパイラ書きにとっては、このフレームワークを使えば、以下の 3 つを提供すれば好みのデータフロー最適化を実現できるらしい.

– assertion ( C の assert() とは異なり、 x = 4 などの fact)
– transfer function
– rewrite function

感想

んー、しかし「簡単にできる」と言われても、
私の現状の Haskell の知識では論文に乗っているだけの Haskell コードだけじゃどうにも理解できないです.
GHC のソースを見れば判るかなぁ?

しかしデータフロー最適化は JIT Shader の今後のさらなる最適化のためにはどうしても避けられない道なので、
うまいやり方(フレームワーク, デザインパターン)があるのなら、それを利用するに越したことはないと思っています.
そのため、この論文の提案するフレームワークには注目しています.

まずは理解できるように、こちらがもっと Haskell のことを学習しないといけませんね.

Advertisements