今どきのGCCは再帰を書いても再帰を出さない(GCDの計算)

その数式、プログラムできますか？

またこの本の話である。次に出てくるのは、最大公約数の計算。

int gcd (int a, int b);

int main ()
{
    volatile int a = 196;
    volatile int b = 42;
    (*(volatile int *)0xffff0000) = gcd (a, b);
}


int gcd (int a, int b)
{
    if      (a == b) { return a; }
    else if (b <  a) { return gcd (a - b, b); }
    else             { return gcd (a, b - a); }
}

普通に再帰構造で書いてあるのだが、MIPSでコンパイルするとこうなった。

$ mipsel-linux-elf-gcc -Tmips32r5.ld -O3 gcd.c startup.s -mips64r5 -o gcd

ダンプ結果:

800001bc <gcd>:
800001bc:       1085000a        beq     a0,a1,800001e8 <gcd+0x2c>
800001c0:       00000000        nop
800001c4:       00851023        subu    v0,a0,a1
800001c8:       00a4182a        slt     v1,a1,a0
800001cc:       00a43023        subu    a2,a1,a0
800001d0:       0083100a        movz    v0,a0,v1
800001d4:       00c3280a        movz    a1,a2,v1
800001d8:       1445fffa        bne     v0,a1,800001c4 <gcd+0x8>
800001dc:       00402021        move    a0,v0
800001e0:       03e00008        jr      ra
800001e4:       00000000        nop
800001e8:       03e00008        jr      ra
800001ec:       00801021        move    v0,a0

良く見てみると、再帰で呼び出す仕組みになっていない。これは末尾再帰の構造に勝手に変換されて、再帰構造になっているのを防いでいるようだ。

int gcd (int a, int b)
{
    if      (a == b) { return a; }
    else if (b <  a) { return gcd (a - b, b); }
    else             { return gcd (a, b - a); }
}

は、以下のように変換された。

int gcd (int a, int b)
{
    while (a != b) {
        if (b < a) {
            a = a - b;
        } else {
            b = b -a;
        }
    }
    return a;
}

うまいこと変換されるなあ。