Risse での実際の用途に近い状態でのLLVM自体の最適化性能を調べるために、以下のようなプログラムを作成しました。
プログラム (C++)
何をやっているかというと、Variant というクラスがあって、整数型の integer というメンバと実数型の real というメンバ、それとこのインスタンスが整数を表しているのか、実数を表しているのかを表す type というメンバを持っています。いわゆるバリアントです。
最後に test という関数があって、0～100000 の整数の合計を計算して返しています。main 関数ではそれの戻り値を表示しています。
さて、これをコンパイルして逆アセンブルしてみると ....
$ llvm-gcc -o vtest test.cpp
gccld: warning: Cannot find library 'stdc++'
$ llvm-dis -f ./vtest.exe.bc
$ cat vtest.exe.ll
; ModuleID = './vtest.exe.bc'
target endian = little
target pointersize = 32
target triple = "mingw32"
deplibs = [ "stdc++", "c", "crtend" ]
%.str_1 = internal constant [5 x sbyte] c"%ld\0A\00" ; <[5 x sbyte]*> [#uses=1]
implementation ; Functions:
declare int %printf(sbyte*, ...)
int %main() {
entry:
%tmp.0 = tail call int (sbyte*, ...)* %printf( sbyte* getelementptr ([5 x sbyte]* %.str_1, int 0, int 0), long 4999950000 ) ; <int> [#uses=0]
ret int 0
}
………。
ということで、いきなりすでに結果の値が埋め込まれてしまっています。Variant クラスの関数も全部なくて、main 関数しかなく、計算をするコードすらありません。
これはイケてるかも。
test関数のループ内に 4 を毎回加算するような以下のコードを書いても
integer_t test()
{
Variant i;
Variant sum = (integer_t)0;
Variant limit = (integer_t)100000;
for(i = (integer_t)0; i < limit; i.Increment())
{
sum += i;
sum += (integer_t)4;
}
return sum.AsInteger();
}
コンパイル結果は
%tmp.0 = tail call int (sbyte*, ...)* %printf( sbyte* getelementptr ([5 x sbyte]* %.str_1, int 0, int 0), long 5000350000 ) ; <int> [#uses=0]
のように計算済み結果となってしまいます。
以下のようなコードでやっと事前の計算をあきらめてくれました。
integer_t test()
{
Variant i;
Variant sum = (integer_t)0;
Variant limit = (integer_t)100000;
for(i = (integer_t)0; i < limit; i.Increment())
{
sum += i;
sum += sum;
}
return sum.AsInteger();
}
逆コンパイル結果は以下のようになりました (main 関数内のみ示す)。
int %main() {
entry:
br label %shortcirc_next.0.i49.i
shortcirc_next.0.i49.i: ; preds = %no_exit.i, %entry
%indvar.i = phi ulong [ 0, %entry ], [ %indvar.next.i, %no_exit.i ] ; <ulong> [#uses=3]
%sum.0.5.i = phi long [ 0, %entry ], [ %tmp.18.i.i, %no_exit.i ] ; <long> [#uses=2]
%exitcond.i = seteq ulong %indvar.i, 100000 ; <bool> [#uses=1]
br bool %exitcond.i, label %_Z4testv.exit, label %no_exit.i
no_exit.i: ; preds = %shortcirc_next.0.i49.i
%i.0.0.i = cast ulong %indvar.i to long ; <long> [#uses=1]
%tmp.18.i28.i = add long %i.0.0.i, %sum.0.5.i ; <long> [#uses=1]
%tmp.18.i.i = shl long %tmp.18.i28.i, ubyte 1 ; <long> [#uses=1]
%indvar.next.i = add ulong %indvar.i, 1 ; <ulong> [#uses=1]
br label %shortcirc_next.0.i49.i
_Z4testv.exit: ; preds = %shortcirc_next.0.i49.i
%tmp.0 = tail call int (sbyte*, ...)* %printf( sbyte* getelementptr ([5 x sbyte]* %.str_1, int 0, int 0), long %sum.0.5.i ) ; <int> [#uses=0]
ret int 0
}
いずれにしろ、Variant 内に書かれているような実数演算に関するコードはいっさい出てきていません。整数の計算しか書いてないですし、実際に整数の計算しかしていないからです。
実は、これぐらいの最適化をしてくれることを期待していたのです。
Risse はタイプ・ルーズな言語なので、変数などへのアクセスはすべて型が何であるかを実行時に毎回チェックしています。
たとえば TJS2 で以下のようなコードを書くと、
function make_sum(array)
{
var sum;
for(var i = 0; i < array.count; i++) sum += array[i];
return sum;
}
現状の実装では i の型を毎回チェックしてしまいます。
しかし、i は整数にしかなり得ないのは、インライン展開や定数伝播(constant propagation)解析や死亡コード除去(dead code elimination)などの詳細な解析をおこなえば判明するので、これにより最適化の効果が望めるところです。
Risse は動的な言語ですが、この手の最適化を妨げるほどの自由度は与えない方針です。たとえば 整数クラス Integer の += 演算子などは、とりあえずはオーバーライドや置き換えが可能にはしないと思います。
ちなみに、プログラム中の Variant::integer と Variant::real を union にすると LLVM ではこの手の最適化はいっさいダメになってしまいます。実際の Risse 内部のバリアントはすべての型の値は一つの union で共有されているので、この手の最適化を有効にするには union による共有を (LLVM用コード内では)あきらめるか、あるいはそもそも変数の型のトラッキングを Risse 側で解析してやる必要がありそうです。前者は Risse 内部のバリアント型との変換を書かなければならないし、このような最適化が聞かなかった場合に変数がストレージを食い過ぎるので、後者を採用するしかないかも、、、ってそれじゃ今回見てきたような LLVM の最適化の恩恵をあまり得られないじゃん。
どうしようかな。まさか、むしろ、いまさら、Risseをタイプルーズじゃなくするとか？
簡単なベンチマークを。
ベンチマーク用プログラムにはこちらのプログラムを使用し、655,360桁の円周率を計算するのに必要な時間を計測しました (I/Oの時間を計測する目的ではないので、ソースを修正して出力が行われないようになっています)。
まず、gcc。
$ gcc -v
Reading specs from c:/k3/MinGW/bin/../lib/gcc/mingw32/3.4.5/specs
Configured with: ../gcc-3.4.5/configure --with-gcc --with-gnu-ld
--with-gnu-as --host=mingw32 --target=mingw32 --prefix=/mingw --
enable-threads --disable-nls --enable-languages=c,c++,f77,ada,ob
jc,java --disable-win32-registry --disable-shared --enable-sjlj-e
xceptions --enable-libgcj --disable-java-awt --without-x --enable
-java-gc=boehm --disable-libgcj-debug --enable-interpreter --enab
le-hash-synchronization --enable-libstdcxx-debug
Thread model: win32
gcc version 3.4.5 (mingw special)
$ gcc -O3 -mtune=athlon64 -o pi-gcc-native pi_fftca.c fftsgx.c
$ time ./pi-gcc-native.exe
real 0m3.171s
user 0m0.015s
sys 0m0.015s
結果は 3.171秒。
つぎ、LLVM。
$ llvm-gcc -o pi pi_fftca.c fftsgx.c
$ time lli ./pi.exe.bc
real 0m4.438s
user 0m0.015s
sys 0m0.015s
結果は 4.438秒。
ちなみに JIT ではなくてインタプリタで動作させた時間を計ろうとしたところ
$ lli --force-interpreter ./pi.exe.bc
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
………あらら。実行できませんでした。
llc で LLVM がどの様なコードを実行しているのか調べてみると、どうやら SSE2 に実数演算を行わせている模様。
gcc でも同様のオプションをつけてやってみると
$ gcc -O3 -mtune=athlon64 -march=athlon64 -msse2 -mfpmath=sse -o pi-gcc-native pi_fftca.c fftsgx.c
$ time ./pi-gcc-native.exe
real 0m3.063s
user 0m0.015s
sys 0m0.015s
………差が開いてるし。
逆に LLVM で SSE のような拡張命令を使わせないと
$ time lli --mcpu=generic ./pi.exe.bc
real 0m6.187s
user 0m0.015s
sys 0m0.015s
これは遅い。
いろいろ試したのですがおおむね LLVM のほうが２～３割遅いという結果に。まだ一つの例しか見てないのでこれで優劣を決める訳にはいかないのですが、まだまだ最適化が甘いのかもしれません。どうもアセンブリ言語の出力をみていると、レジスタの割り当てに無駄が多く、ロードとストアが多い気がします。
