2013-06-22

先日llvm 3.3がリリースされました。aarch64(arm 64bit)のコードが生成できるようになったということなので、ソースからビルドして遊んでいたのですが、さりげなく凄く最適化されたコードが生成されているのに気がつきました。aarch64だと今は実行して確認できる環境が手元に無いので、普通のarmv7-aで同じことを試しました。
ここで使ったコードとその結果はgistに貼りました。
https://gist.github.com/tetsu-koba/5835724

ソースコード

int sum(int x)
{
    int sum = 0;
    int i;
    for (i = 1; i <= x; i++) {
        sum += i;
    }
    return sum;
}

1からnまでの総和を求める関数です。1から100までの総和が5050なのはガウス少年の逸話で有名ですね。

gcc 4.8.1での生成コード

sum:
        cmp r0, #0
        ble .L4
        adds r2, r0, #1
        movs r3, #1
        movs r0, #0
.L3:
        add r0, r0, r3
        adds r3, r3, #1
        cmp r3, r2
        bne .L3
        bx lr
.L4:
        movs r0, #0
        bx lr

最適化 -Oをつけてコンパイルしています。(-O3にしても特に変化はありません。）
ソースコードに忠実にループを回しています。これが普通のコードだと思っていました。llvmのコードを見るまでは。

clang+llvm 3.3 での生成コード

sum:
        mov r1, #0
        cmp r0, #1
        blt .LBB0_2
        sub r1, r0, #2
        sub r2, r0, #1
        umull r1, r2, r2, r1
        and r2, r2, #1
        lsrs r2, r2, #1
        rrx r1, r1
        add r0, r1, r0, lsl #1
        sub r1, r0, #1
.LBB0_2:
        mov r0, r1
        bx lr

あれ？umullは乗算命令かな。よく見るとループしてないぞ！
1からnの総和はn回加算しなくても、1/2 * n * (n + 1) で求められることは知識としては知っていますが、llvmはそれと似たようなことをしています。しかし微妙に違う。これが正しいのかどうかぱっとみて判断がつきません。（正しいことを確認しました。clang+llvmでさりげなくすごいコードが生成されていた話の補足。 - 組み込みの人。）
高速化のために元のソースを手でアセンブラ化するとしてもここまでのコードは即座には書けませんね。私ならコンパイラにお任せします。

さらに以下のコードを追加してみました。

#include <stdio.h>
int main()
{
    int n;
    n = 100;
    printf("sum(%d) = %d\n", n, sum(n));
}

そして、その部分の生成コードは

main:
        push {r11, lr}
        movw r0, :lower16:.L.str
        mov r1, #100
        movt r0, :upper16:.L.str
        movw r2, #5050
        mov r11, sp
        bl printf
        mov r0, #0
        pop {r11, pc}

これは一本取られた！
sum(100)=5050なのはコンパイルした時点でわかっているので、もうsum関数を呼ばずに定数で5050をprintfに渡しています。

ちなみにgcc 4.8.1だと

main:
        movs r3, #1
        movs r2, #0
.L9:
        add r2, r2, r3
        adds r3, r3, #1
        cmp r3, #101
bne .L9
        movw r0, #:lower16:.LC0
        movs r1, #100
        movt r0, #:upper16:.LC0
        b printf

sum関数がここにインライン展開されて、定数100が埋め込まれていますが、いぜんとして100回ループしています。

(2013.6.24追記）
自分でビルドしたgccではダメでしたが、Ubuntu 12.04LTSでapt-get installしたarm-linux-gnueabihf-gcc では -O2をつけるとclangと同様にsum関数を呼ばずに定数で5050をprintfに渡すようなコードを生成します。

手元のいくつかのバージョンのgccで試したところでは、4.6, 4.7ではいいのですが、4.8でダメになったようです。リグレッションかな？
(追記ここまで。)

まとめ

この関数の一例について言えば、gccの最適化だとループの回数は変わりませんが、clang+llvmでは徹底的のループを除去しようとします。ループの回数が大きくなるとその実行時間の差は如実に現れるはずです。llvmすごい。（なお、この最適化がllvm 3.3からなのか、それ以前からそうなのかは調べていません。）
私自身はコンパイラの中身についてそれなりに知識があるので、このような最適化が可能であることは知っていたのですが、現状のclang + llvmでコンパイルオプションに-Oをひとつ追加するだけでここまでやってくれるとは驚きでした。

さらに思ったこと

llvmでこのような最適化ができたのは、このsum関数が「純粋な関数」であり、与えられた引数によってのみ関数値が計算でき、それ以外の副作用の影響を受けないし与えないからです。C言語ではうっかりすると副作用のあるコードを混ぜてしまうことが簡単にできてしまい、（例えば、ループの中でグローバル変数やポインタを参照するなど。）そうすると最適化が効かなくなってしまいます。
これからのコードを書く者の技量として、どう書くとどう最適化が効くか、いかに最適化を邪魔しないようにコードを書くかということが問われるのかなと思いました。あるいは、コンパイラの最適化を邪魔しにくいような言語仕様の言語を習得してそれを使うか。コンパイラの最適化を邪魔しにくい言語のひとつとしては関数型言語がありますね。