FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

今どきのGCCは再帰を書いても再帰を出さない (gcc-5.1で実験)

この本おもしろい!途中から数学チックになって難しいが、時間をかけて読み込んでいきたい。

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

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

最初に、以下のようなプログラムが登場する。乗算を使わない場合の、基本的な加算の考え方だ (multiply0)。

int multiply0 (int n, int a) {
  if (n == 1) { return a; }
  return multiply0 (n-1, a) + a;
}

次に、それを少しだけ最適化したmultiply1が登場する。基本的なプログラムの考え方は一緒だが、メモ化による最適化をして、なるべく同じ計算をしないようにしている。

inline int odd (int n) {
  return (n & 0x0001U);
}

inline int half (int n) {
  return n >> 1;
}

int multiply1 (int n, int a) {
  if (n == 1) return a;
  int result = multiply1 (half(n), a + a);
  if (odd (n)) result = result + a;
  return result;
}

これ、本当意図する最適化になっているかを確かめるために、ソースを書いて、生成命令がどのようになっているのか、確かめてみた。

$(TARGET) : $(SRC)
        mipsel-linux-elf-gcc -T$(LDSCRIPT) $(CFLAGS) $^ -mips64r5 -o $@
        mipsel-linux-elf-objdump -D $(TARGET) > $(TARGET).dmp
        mipsel-linux-elf-nm $(TARGET) > $(TARGET).nm
int main (void)
{
    volatile int r = 13;
    volatile int n = 53;
    volatile int a = 37;

    (*(volatile unsigned int *)0xffff1000) = 0;
    (*(volatile unsigned int *)0xffff0000) = multiply0 (n, a);
    (*(volatile unsigned int *)0xffff2000) = 1;

    (*(volatile unsigned int *)0xffff3000) = 0;
    (*(volatile unsigned int *)0xffff0000) = multiply1 (n, a);
    (*(volatile unsigned int *)0xffff4000) = 1;

MIPSシミュレータを使っているので、サイクル数は正確には分からないが、命令数から推測できる。

53 * 37を実行してみた結果の命令数 * multiply0 : 13 * multiply1 : 72

objdumpしてみた結果が以下だ。

800001bc <multiply0>:
800001bc:       24020001        li      v0,1
800001c0:       10820004        beq     a0,v0,800001d4 <multiply0+0x18>
800001c4:       2484ffff        addiu   a0,a0,-1
800001c8:       70851002        mul     v0,a0,a1
800001cc:       03e00008        jr      ra
800001d0:       00451021        addu    v0,v0,a1
800001d4:       1000fffd        b       800001cc <multiply0+0x10>
800001d8:       00001021        move    v0,zero

あれ、超短い。どうやら、上記のmultiply0のソースコードを見せただけで、乗算と判断して加算の再帰を省略しているようだ!すごい!

一方で、multilpy1をobjdumpしてみるとかなり長い命令列になった。

800001dc <multiply1>:
800001dc:       27bdffc0        addiu   sp,sp,-64
800001e0:       24020001        li      v0,1
800001e4:       afbf003c        sw      ra,60(sp)
800001e8:       afbe0038        sw      s8,56(sp)
800001ec:       afb70034        sw      s7,52(sp)
800001f0:       afb60030        sw      s6,48(sp)
800001f4:       afb5002c        sw      s5,44(sp)
800001f8:       afb40028        sw      s4,40(sp)
800001fc:       afb30024        sw      s3,36(sp)
80000200:       afb20020        sw      s2,32(sp)
80000204:       afb1001c        sw      s1,28(sp)
80000208:       10820034        beq     a0,v0,800002dc <multiply1+0x100>
8000020c:       afb00018        sw      s0,24(sp)
80000210:       00049843        sra     s3,a0,0x1
80000214:       00a08821        move    s1,a1
80000218:       00808021        move    s0,a0
8000021c:       1262001f        beq     s3,v0,8000029c <multiply1+0xc0>
80000220:       00059040        sll     s2,a1,0x1
80000224:       0004a083        sra     s4,a0,0x2
80000228:       12820018        beq     s4,v0,8000028c <multiply1+0xb0>
8000022c:       0005a880        sll     s5,a1,0x2
80000230:       0004b0c3        sra     s6,a0,0x3
80000234:       12c20011        beq     s6,v0,8000027c <multiply1+0xa0>
80000238:       0005b8c0        sll     s7,a1,0x3
8000023c:       0004f103        sra     s8,a0,0x4
80000240:       13c2000a        beq     s8,v0,8000026c <multiply1+0x90>
80000244:       00051900        sll     v1,a1,0x4
80000248:       00052940        sll     a1,a1,0x5
8000024c:       00042143        sra     a0,a0,0x5
80000250:       33de0001        andi    s8,s8,0x1
80000254:       0c000077        jal     800001dc <multiply1>
80000258:       afa30010        sw      v1,16(sp)
8000025c:       13c00003        beqz    s8,8000026c <multiply1+0x90>
80000260:       00401821        move    v1,v0
80000264:       8fa30010        lw      v1,16(sp)
80000268:       00621821        addu    v1,v1,v0
8000026c:       32d60001        andi    s6,s6,0x1
80000270:       12c0002c        beqz    s6,80000324 <multiply1+0x148>
80000274:       00000000        nop
80000278:       02e3b821        addu    s7,s7,v1
8000027c:       32940001        andi    s4,s4,0x1
80000280:       12800024        beqz    s4,80000314 <multiply1+0x138>
80000284:       00000000        nop
80000288:       02b7a821        addu    s5,s5,s7
8000028c:       32730001        andi    s3,s3,0x1
80000290:       12600022        beqz    s3,8000031c <multiply1+0x140>
80000294:       00000000        nop
80000298:       02559021        addu    s2,s2,s5
8000029c:       8fbf003c        lw      ra,60(sp)
800002a0:       32100001        andi    s0,s0,0x1
800002a4:       02322821        addu    a1,s1,s2
800002a8:       00b0900b        movn    s2,a1,s0
800002ac:       02401021        move    v0,s2
800002b0:       8fbe0038        lw      s8,56(sp)
800002b4:       8fb70034        lw      s7,52(sp)
800002b8:       8fb60030        lw      s6,48(sp)
800002bc:       8fb5002c        lw      s5,44(sp)
800002c0:       8fb40028        lw      s4,40(sp)
800002c4:       8fb30024        lw      s3,36(sp)
800002c8:       8fb20020        lw      s2,32(sp)
800002cc:       8fb1001c        lw      s1,28(sp)
800002d0:       8fb00018        lw      s0,24(sp)
800002d4:       03e00008        jr      ra
800002d8:       27bd0040        addiu   sp,sp,64
800002dc:       8fbf003c        lw      ra,60(sp)
800002e0:       00a09021        move    s2,a1
800002e4:       02401021        move    v0,s2
800002e8:       8fbe0038        lw      s8,56(sp)
800002ec:       8fb70034        lw      s7,52(sp)
800002f0:       8fb60030        lw      s6,48(sp)
800002f4:       8fb5002c        lw      s5,44(sp)
800002f8:       8fb40028        lw      s4,40(sp)
800002fc:       8fb30024        lw      s3,36(sp)
...

アルゴリズム的には綺麗だけど、GCCにより最適化が入った究極の例だと思う。どのバージョンのGCCからこのような最適化が入っているんだろう?興味がある。

ついでに言うと、次に登場してくるmult_accも、再帰が登場しないようになっている。今やGCCの最適化により、再帰を書いても再帰が出てこないコードが出せるのか。