最適化でヒかれる。

おおお、配列を実装してほしいとのリクエストをもらってしまった。
えーと、僕も配列くらいはあってもいいかなーって思ってるところなんですが、どういうインターフェースにしたらいいかがいまいちよくわからないところです。ローカルな配列が必要となると、色々面倒だとかの実装の都合なんですが。実装するとしたら、「配列はグローバル変数でしか使えない」みたいな感じになってしまうかと。

んで、まあ、a24zコンパイラを書きながら、いくつか考えたことがあるんだけど、配列の話が出たついでに、まずは、最適化の話からしていこうかと。僕もちょろっとさわりしか勉強してないんだけど、まあ、知ったかぶるぐらいの知識はあると思うので、これを読めば、まあ、飲み屋で「わかるぅ？SSAってのはStatic Single Assignment form、静的単一代入形式のことなんだよねぇ。」とか言って、「うわっこいつキモオタだよ」とか、そんな感じで軽くヒかれるような話題の種とかに使えるかと思います。

と、それはいいとして、なんで配列といえば最適化なのかというと、配列というのは最適化が無いと使いものにならないからであり、そして、最適化は配列があってこそ効果が大きくなるからなのだ。
よく、最適化で言われるのが、「共通部分式の削除（Common Subexpression Elimination:CSE）」とかいわれる技法なんだけど、これ、よくあるサンプルが、

int x = a*b+c;
int y = a*b+c;
// ここで、a*b+cは二回計算しなくてもいいのでうんぬん

int x = a*b+c;
int y = x;
// こーいうふうに変換できます

といった感じなのだが、ここで、普通の人ならば「俺、そんなコード書かねぇYO！！」と、思うだろう。で、共通部分式削除はあんまり使えないかと思ってしまいがちである。僕もそうでした。しかし、これは違う。サンプルが狂っているのだ。こんなのでは共通部分式のありがたみは全く伝えられてないと言っていいだろう。
共通部分式削除は配列を使ってこそ、始めて有用なものとなるのである。

int *x;
int *y;

...

for ( ...; i++ ) 
    x[i] = y[i]

というプログラムは、実は

label:
	*(int*)((char*)x+(i*4)) = *(int*)((char*)y+(i*4))
	i++;
	goto label;

こーいうプログラムだというのはなんとなくわかるだろう。で、これで共通部分式を消すと、

label:
	index = i*4;
	*(int*)((char*)x+(index)) = *(int*)((char*)y+(index))
	i++;
	goto label;

こんな感じになる。これの効果は、「ループの中で乗算が一個減る」と、いうものだ。そういうふうに書くと、それが結構な効果になるだろうことはなんとなく想像付くかと思う。まあ、そんな感じ。最適化というのは、ループの中の配列アクセスに対して一番効果がある、っていうのは無駄知識としては程良いかと思う。

で、もういっこ無駄知識としてSSAの話。SSAとゆーと、最近、GCC4.0でtree-ssa最適化が実装されるとかで一躍有名になったかと思うのだけど（僕もそこで知ったうちの一人なんだが）、普通の形式と比べてどーいう効果があるのか、っていうのは気になるところかと思う。で、僕も気になったので調べてみたんだけど、どうやら、これは、最適化に効果があるというよりは、最適化アルゴリズムを簡単にするのに効果がある、といったほうが正しいような気がする。
で、そういう表現をすると、「なんだ、そんなことか。」と、思うかもしれないが、この、「プログラムが簡単になる」というのが、重要というか、まあ、例えば、上の共通部分式削除も、普通の形式でやってると、条件分岐くぐり抜けたあとの共通部分式探すとかになると、もはやデータ構造もどうやったらいいかわからんくらいややこしくなるんだけど、SSA形式になってると、「あー、これなら僕でもできるかも…」と、思えるようになるくらい、違ってくるのである。まあ、そんな感じ。

あと、余談として、これまでのGCCの最適化はRTLで行われてたんだけど、あれは相当イカれてるんじゃないかと思う。いや、まあ、なんとなく、そんな気がした。

ああああ。色々と、話の繋げかたが無理矢理だなぁ…

で、次回、スタックマシンにおける最適化の話に続きます。いや、あんまり続きでもないんだけど。javacは最適化に関しては終わってるだとか。