スタックマシンと最適化

さて、いつまでもコンパイラやらインタプリタやら書き捨てばっかりなのもつまらんな、と思って、a24zでは最適化でもかじってみようかと思ったのだ。が、そろそろ集中力が切れてきたのでやらないかもしれない。

で、実装するかしないかはまあいいとして、そこらへん関係で、色々スタックマシン（というか、JVM）のコードを吐くコンパイラの最適化について調べてみた。が、しかし、なんということか、最適化を行っているコンパイラは、ほとんど存在しないのである。唯一確認できたのは、KopiのコンパイラKJCだけであった。他のはちょろっと定数計算を行っているくらいであった。Luaコンパイラにいたっては、定数計算すら行っていなかった。
が、しかし、それは仕方無いのかもしれない。ここらへん調べていたころ、色々と考えていたのだが、スタックマシンでは中途半端な最適化は逆効果になることが多いからだ。
例えば、

// a, x, y はローカル変数。
a = (x*y) + (x*y)

こんな感じの式があったとして、こいつを単純にスタックマシンのコードに落とすと、

# load → ローカル変数を読み出してスタックの先頭に	(2 byte)
# store → スタックの先頭の値をローカル変数に		(2 byte)
# add → スタックの上ふたつの値を加算			(1 byte)
# mul → スタックの上ふたつの値を乗算			(1 byte)
0:	load	x
2:	load	y
4:	mul
5:	load	x
7:	load	y
9:	mul
10:	add
11:	store	a

こんな感じになると思う。で、ここで、見るからに無駄っぽい計算があるので、最適化を行ってみることにする。まず、最適化を行うには、三番地文という単純な形式に変換する。別に変換しなくてもいいんだけど、三番地文にすると処理が単純になるとかなので、ここらへんは定石というか、定跡というか。

t1 = x * y
t2 = x * y
a = t1 + t2

で、こーなると、x*yが共通部分式だとわかるので、こいつを消して、

t1 = x * y
a = t1 + t1

こんな感じ、で、これをスタックマシンのコードに変換すると、

0:	load	x
2:	load	y
4:	mul
5:	store	t1
7:	load	t1
9:	load	t1
11:	add
12:	store	a

なんと、命令数は変わらないうえに、コードサイズは増えてしまうのである。乗算は一回減っているので、まあ、悪くはないかもしれないが、良い感じはしないだろう。また、上の例の場合だと、共通部分式があったから辛うじて同じぐらいの質のコードを生成しているが、普通はあまりそういう状況も無いので、逆に悪くなることが多いと予想されるかと思う。

そんな感じで、算術演算とスタックマシンというのは、普通の状態でそれなりに相性がいいので、中途半端なことをするといけないのである。
で、それだったら、普通に何の最適化もしないほうがいいんじゃないか、と、いった感じで、スタックマシン用の最適化コンパイラというのはあまり存在しないのだと思う。

ちなみに、あまり関係無いけど、KopiのKJCはここらへんも考慮したうえで最適化をしているようで、それなりに賢いコードを生成するようだ。現存するJavaコンパイラの中で、一番賢いのはこのKJCである、ということは、知っておいて損は無いと思う（Visual J++とかは知らんけど）。ローカル変数の節約とかもしてくれるし。ただ、開発止まってるっぽいのだけど。

まあ、とにかく、上のような事情があるのか無いのか、JIT最適化の事情だか知らないけど、javacとjikesが最適化しないのだ。SunとIBMが諦めてるんですよ。さらにいうならgcjも放置してるような問題ですよ。こんなの、やらないほうが普通だよ。一介のサラリーマンが触れるような問題じゃないんだ。
と、そんな感じで、どうでもいいか、と思ってたら、なんとVC++6.0の生成する浮動小数点387コード（これもスタックマシンね）が、見てるだけで失禁しそうになるほど美しく、無駄の無いコードだったので、やっぱり諦めたらいかん、と思ったわけですよ。もう、ほんと、あれはヤバい。あれより良いコードは手でも生成できる気がしない。色々なコード生成させてるだけで楽しめるし。
と、いうわけで、普段から「Microsoftはマーケティング上手いだけで技術力はアレだね」とか言ってる以上（いや、言ってないけど）Microsoftに負けるわけにはいかんので、スタックマシンにおけるコード生成について考えてみよう、という話なのですよ。
続く、としたいところですが、やる気が微妙なので続くかどうか微妙。

あと、GCCの387コードの生成が参考になるかな？と思って見てみたんだけど、GCCの吐いたコードは、計算するたびにfxchでスタックの先頭を入れかえて適当にごまかしているというちょっとアレなコードだったので、参考にならなかった。
が、しかし、パイプラインやらレジスタリネーミングやらの都合で、実は、387の場合はそっちのほうが効率がいいとか、悪いとか。
参考