情報科学演習III小林研究室課題５
静的プログラム解析を用いたコンパイラの最適化
この課題では、
-
既存のコンパイラの遅くなっている原因を考えて、
-
それを取り除く解析方法を考える
-
解析・最適化の実装
-
性能評価の実験
を体験してもらいます。
既存のコンパイラって？
３年の演習でコンパイラ担当だった人は愛着のある？自作のコンパイラを速くしても構いませんし、その他のコンパイラを改造しても構いません。ただ、あまりに巨大な言語のコンパイラだと一ヶ月では、とても終わらないので、Scheme
（のサブセット）くらいが適当だと思います。
解析方法を考える
何を速くしたいかにもよるわけですが、うまいのが思い付かない人には、すでに提案されている解析手法の論文を読んでもらって、それを実装してもらうのでもいいでしょう。
最適化の例を挙げると、
-
primitive operation (+ など）の実行時型チェックを省く。足し算などを行うときには、引数が数値であるかどうかを（まっとうなコンパイラならば）チェックします。ところが、「ここには数値しかこない」と決めうちできる場合は、チェックの必要はありません。
-
関数の inline 展開： scheme などの高階関数が使える言語では、関数呼び出しがあったときに、実際にどの関数が呼ばれるかは実行時にならないとわからず、inline
展開の最適化を行うことは難しい。
などが考えられます。関数型言語の手続き間解析には、control flow analysis,
set-based analysis などが提案されています。
参考文献
-
C. Flanagan, M. Felleisen. Set-based analysis for full scheme and its use
in soft-typing. Technical Report, Rice University, 1993.
-
S. Jagannathan, A. Wright. Effective flow analysis for avoiding run-time
checks. In SAS'95, Springer LNCS983.
課題一覧へ
：
igarashi@is.s.u-tokyo.ac.jp