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

clang+llvmでさりげなくすごいコードが生成されていた話。 - 組み込みの人。で決着のついていなかった部分について。
1からnの総和を求める関数sum()

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

をclang -target arm -march=armv7-a -O -S sum.c で以下のコンパイル結果を得ましたが、これは正しいのか？

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 はunsigned 32bit x unsigned 32bit = unsigned 64bit の乗算命令。
rrx はキャリーフラグを含めた右ローテート命令でした。
lsrs とrxxの組み合わせで2つのレジスタを連結した64bit値を1bit右シフト、つまり2で割ることができます。
それでこのアセンブラ結果を見直すと、次のように解釈できます。

int sum(int r0)
{
    if (r0 >= 1) {
        return (int)(((r0 - 1) * (r0 - 2)) / 2) + (2 * r0) - 1;
    } else {
        return 0;
    }
}

1からnの総和は n * (n+1) / 2 ですから、ちょっと違うように見えますが、式を変形すると一致します。
またはこう見ることもできます。"( (r0 - 1) * (r0 - 2) ) / 2" の部分は実は1から(n-2)までの総和で、それに(n -1) + n つまり 2*n -1 を足せば1からnの総和になります。
これでこのアセンブラ結果はめでたく1からnの総和を計算しているということがわかりました。

なぜこのような変形をしているのか？ということですが

ということを教えてもらいました。
n にintの最大の値(= 0x7fffffff)がくると n * (n + 1) を通常の32bitの乗算ではできなくなるのでこれを回避するために式を変形したのではないかということです。
しかしそれならば、(int)(((n - 1) * n)) / 2) + n と変形するほうが命令数が少なくてすむような気がするのでちょっと謎です。

とは言っても、そもそもこのsum関数は引数にintの最大数のように大きな数がくることは想定していないので、結果はintではオーバーフローしてしまうわけですが。
いずれにしても、こんなふうにループを変形して最適化してしまうllvmは凄いです。