この本おもしろい！途中から数学チックになって難しいが、時間をかけて読み込んでいきたい。
- 作者: Alexander A. Stepanov,Daniel E. Rose,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2015/05/19
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (4件) を見る
最初に、以下のようなプログラムが登場する。乗算を使わない場合の、基本的な加算の考え方だ (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の最適化により、再帰を書いても再帰が出てこないコードが出せるのか。
