ブログトップ 記事一覧 ログイン 無料ブログ開設

組み込みの人。


2013-06-22

clang+llvmでさりげなくすごいコードが生成されていた話。

先日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言語ではうっかりすると副作用のあるコードを混ぜてしまうことが簡単にできてしまい、(例えば、ループの中でグローバル変数ポインタを参照するなど。)そうすると最適化が効かなくなってしまいます。

これからのコードを書く者の技量として、どう書くとどう最適化が効くか、いかに最適化を邪魔しないようにコードを書くかということが問われるのかなと思いました。あるいは、コンパイラ最適化を邪魔しにくいような言語仕様の言語を習得してそれを使うか。コンパイラ最適化を邪魔しにくい言語のひとつとしては関数型言語がありますね。

nothingcosmosnothingcosmos 2013/06/22 18:01 こんにちは。
LLVMはsumの計算をchains of recurrencesという帰納変数をモデル化した表現に変換したのち、そのモデルのルールの元、静的評価、畳み込みした後、ループ不要な命令列に逆変換します。
純粋な関数というのも重要な要素だと思いますが、
chains of recurrencesの制約に依存した最適化であるため、過度な期待はしないほうがよいと思います。

embeddedembedded 2013/06/22 23:12 ありがとうございます。もう少しいろいろなパターンで遊んでみます。

anonymousanonymous 2013/09/05 15:02 I believe Scalar Evolution Analysis enables the optimization you showed. Take a look at the code in ScalarEvolution.cpp.

投稿したコメントは管理者が承認するまで公開されません。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証