C 言語プログラムから MIPS アセンブリを生成する方法とコンパイラによる最適化について

コメントを残す

コンピュータ・アーキテクチャの講義で MIPS 命令セットを使って説明をしているが、コンパイラが生成するアセンブリが気になる人もいると思うのでこの記事で扱っておく。

最近の環境だと clang というコンパイラを使うのが良い。Windows では、msys2 を使うと clang を簡単にインストールして使うことができる。

環境づくり：clang のインストール

msys2 をインストール後、以下のコマンドを入力すると clang をインストールできる。

$ pacman -S msys/clang

現在（2022/7/4）のバージョンは以下。

$ clang --version
clang version 11.0.0 (https://github.com/msys2/MSYS2-packages ca391a3660d17cdee1e94d5afd2e72a4f750cddb)
Target: x86_64-pc-windows-msys
Thread model: posix
InstalledDir: /bin

mips ターゲットのアセンブリ生成

コンパイル対象のプログラム（fib.c）

フィボナッチ数列を再帰的に計算するためのプログラムを例にする。

int fib(int n)
{
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fib(n-1) + fib(n-2);
}

アセンブリ生成

以下のコマンドでアセンブリ言語を出力できる（出力は fib.s という名前のファイル）。最適化をしない（＝極力ソースコードの表現のままのアセンブリを出力）場合は -O0 をつける。

$ clang -O0 -S -target mips -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer -mcpu=mips32 fib.c

生成結果

	.text
	.abicalls
	.option	pic0
	.section	.mdebug.abi32,"",@progbits
	.nan	legacy
	.text
	.file	"fib.c"
	.globl	fib                             # -- Begin function fib
	.p2align	2
	.type	fib,@function
	.set	nomicromips
	.set	nomips16
	.ent	fib
fib:                                    # @fib
	.frame	$fp,40,$ra
	.mask 	0xc0000000,-4
	.fmask	0x00000000,0
	.set	noreorder
	.set	nomacro
	.set	noat
# %bb.0:
	addiu	$sp, $sp, -40
	sw	$ra, 36($sp)                    # 4-byte Folded Spill
	sw	$fp, 32($sp)                    # 4-byte Folded Spill
	move	$fp, $sp
	sw	$4, 24($fp)
	lw	$1, 24($fp)
	bnez	$1, $BB0_3
	nop
# %bb.1:
	j	$BB0_2
	nop
$BB0_2:
	sw	$zero, 28($fp)
	j	$BB0_7
	nop
$BB0_3:
	lw	$1, 24($fp)
	addiu	$2, $zero, 1
	bne	$1, $2, $BB0_6
	nop
# %bb.4:
	j	$BB0_5
	nop
$BB0_5:
	addiu	$1, $zero, 1
	sw	$1, 28($fp)
	j	$BB0_7
	nop
$BB0_6:
	lw	$1, 24($fp)
	addiu	$4, $1, -1
	jal	fib
	nop
	lw	$1, 24($fp)
	addiu	$4, $1, -2
	sw	$2, 20($fp)                     # 4-byte Folded Spill
	jal	fib
	nop
	lw	$1, 20($fp)                     # 4-byte Folded Reload
	addu	$2, $1, $2
	sw	$2, 28($fp)
	j	$BB0_7
	nop
$BB0_7:
	lw	$2, 28($fp)
	move	$sp, $fp
	lw	$fp, 32($sp)                    # 4-byte Folded Reload
	lw	$ra, 36($sp)                    # 4-byte Folded Reload
	addiu	$sp, $sp, 40
	jr	$ra
	nop
	.set	at
	.set	macro
	.set	reorder
	.end	fib
$func_end0:
	.size	fib, ($func_end0)-fib
                                        # -- End function
	.ident	"clang version 11.0.0 (https://github.com/msys2/MSYS2-packages ca391a3660d17cdee1e94d5afd2e72a4f750cddb)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym fib
	.text

結果の見方

  • BB は Basic Block（基本ブロック）を意味している。
    • 一つの入り口（すなわち、内部のコードが他のコードの分岐先になっていない)と一つの出口を持ち、内部に分岐を含まないコードを指す。（Wikipedia）
  • スタック領域に 40 バイト確保する（実際に使っているのは 20 バイト）
  • move 命令などはアセンブリで許されている汎用表現で、この後機械語にアセンブルするときには実在する命令に置き換えられる。
  • MIPS には push, pop などスタックを操作する命令はないので、スタック領域に対して load word (lw), store word (sw) している。
  • $fp の値は $sp と同じになっている。
  • MIPS は遅延スロットを１つもつので、分岐命令の次の命令まで分岐前に実行される。上のアセンブリでは nop 命令が置かれている。
  • $BB0_6 で jal fib が２回呼ばれていて、これらは fib(n-1) と fib(n-2) にそれぞれ対応している。

関数の呼び出し回数とスタック

この時、fib() 関数が呼び出された回数を調べてみよう。デバッガ（gdb）を使うと調べることができる。本記事では fib(10) を計算したときの様子を示す。

$ gdb a.exe
GNU gdb (GDB) 11.1
Copyright (C) 2021 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-msys".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Traceback (most recent call last):
  File "<string>", line 3, in <module>
ModuleNotFoundError: No module named 'libstdcxx'
/etc/gdbinit:6: Error in sourced command file:
Error while executing Python code.
Reading symbols from a.exe...
(gdb) b fib
Breakpoint 1 at 0x10040108a
(gdb) ignore 1 100000
Will ignore next 100000 crossings of breakpoint 1.
(gdb) r
Starting program: /path/to/a.exe
[New Thread 6748.0x4874]
[New Thread 6748.0x3e68]
[New Thread 6748.0x2534]
c: 55
[Thread 6748.0x5c20 exited with code 0]
[Thread 6748.0x2534 exited with code 0]
[Thread 6748.0x4874 exited with code 0]
[Inferior 1 (process 6748) exited normally]
(gdb) info breakpoints
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x000000010040108a <fib+10>
        breakpoint already hit 177 times
        ignore next 99823 hits
(gdb) q

上記の結果から、fib(10) の計算に177回 fib() を呼び出していることがわかる。

プログラムそれ自体から、 fig(k) の呼び出し回数は fib(k+1) と fib(k+2) の呼び出し回数の和である。fib(k) の呼び出し回数を g(k) と書くことにすれば、g(k) = g(k+1) + g(k+2) であり、これはフィボナッチ数列と類似の構造を持っている。fib() 呼び出し回数の総数は k について和をとればよい。fib(1) は fib(0) を呼ばないことに注意すれば、 fib(n) を得るためには fib(k) を k=0,...,n まで足してさらに fib(n-1) を加えた回数と一致することがわかるはずだ。

また、関数呼び出しの深さは fib(n) を考えるときに fib(n-1) を計算するパスが最も深くなる。そして、これは fib(1) にたどり着くまでネストするので最大で n-1 の深さとなる。上のコードでは１回の呼び出しに40バイトのスタックが必要なので、40 × (n-1) のスタック領域が少なくとも必要で、大きな n について計算しようとするとスタック領域を使いつくしてプログラムがエラーとなる（スタックオーバーフローという。実際にやってみよう）。

上記をちゃんと理解すれば、とても非効率なことをしていることがわかると思う。（整数の足し算しかしないのに、答えの数値よりも多い回数の関数呼び出しが必要。）

知っておくとよいかもしれないこと

この記事で紹介する MIPS アセンブリ生成方法はクロスコンパイルというもので、標準ライブラリに含まれる関数などを呼ぶとエラーになる場合がある。実際に実行したいわけでなければ、そのような関数は適当なプロトタイプ宣言だけしておいてコンパイルすればよい。例えば、printf のプロトタイプは以下のように書いておけばよい。

int printf(const char *, ...);

最適化 (-O2) するとどうなるか？

コンパイラはプロセッサで実行したときに適した（例えば、高速になるように、など）プログラムを出力するための最適化機能が実装されていて、それを使うと簡単に10倍くらいプログラムの性能が変わったりする。

標準的な最適化である -O2 をつけた時に出力結果がどう変わるか見てみよう。

$ clang -O2 -S -target mips -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer -mcpu=mips32 fib.c

この時生成結果は以下のようになる。

        .text
        .abicalls
        .option pic0
        .section        .mdebug.abi32,"",@progbits
        .nan    legacy
        .text
        .file   "fib.c"
        .globl  fib                             # -- Begin function fib
        .p2align        2
        .type   fib,@function
        .set    nomicromips
        .set    nomips16
        .ent    fib
fib:                                    # @fib
        .frame  $fp,32,$ra
        .mask   0xc0030000,-4
        .fmask  0x00000000,0
        .set    noreorder
        .set    nomacro
        .set    noat
# %bb.0:
        addiu   $sp, $sp, -32
        sw      $ra, 28($sp)                    # 4-byte Folded Spill
        sw      $fp, 24($sp)                    # 4-byte Folded Spill
        sw      $17, 20($sp)                    # 4-byte Folded Spill
        sw      $16, 16($sp)                    # 4-byte Folded Spill
        move    $fp, $sp
        move    $16, $4
        sltiu   $1, $16, 2
        bnez    $1, $BB0_2
        addiu   $17, $zero, 0
$BB0_1:                                 # =>This Inner Loop Header: Depth=1
        jal     fib
        addiu   $4, $16, -1
        addiu   $16, $16, -2
        sltiu   $1, $16, 2
        beqz    $1, $BB0_1
        addu    $17, $2, $17
$BB0_2:
        addu    $2, $16, $17
        move    $sp, $fp
        lw      $16, 16($sp)                    # 4-byte Folded Reload
        lw      $17, 20($sp)                    # 4-byte Folded Reload
        lw      $fp, 24($sp)                    # 4-byte Folded Reload
        lw      $ra, 28($sp)                    # 4-byte Folded Reload
        jr      $ra
        addiu   $sp, $sp, 32
        .set    at
        .set    macro
        .set    reorder
        .end    fib
$func_end0:
        .size   fib, ($func_end0)-fib
                                        # -- End function
        .ident  "clang version 11.0.0 (https://github.com/msys2/MSYS2-packages ca391a3660d17cdee1e94d5afd2e72a4f750cddb)"
        .section        ".note.GNU-stack","",@progbits
        .addrsig
        .text
  • $BB0_1 をみると、jal fib は１行しかでておらず、 beqz $1, $BB0_1 により $BB0_1 が繰り返し実行されることがわかる。
    • この再帰呼び出しに着目すると、１回目は fib(n-1) を呼び出すが、２回目は fib(n-3) を呼んでおり、元の実装と異なることがわかる。
    • これは、fib(n) = fib(n-1) + fib(n-2) と計算するか、fib(n) = fib(n-1) + fib(n-3) + ... と計算するかの違い。つまり、関数内部の構造を解釈して等価な結果を出力する関数に書き換えていることがわかる。
    • さらに、fib(0) を再帰的に呼び出す処理が排除されている。fib(0) = 0 なのでこれを呼び出す必要はない。

関数呼び出し回数

この最適化により呼び出し回数がどうなるかを考えてみよう。fib(n-2) の呼び出しがなくなっているため、呼び出し回数は fib(k) の k=0,...,n-1 までの和 + 1 に抑えられる。（fib(0) の再帰呼び出しがなくなった効果は fib(2) の呼び出し回数と一致する。）

$ gdb a.exe
GNU gdb (GDB) 11.1
Copyright (C) 2021 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-msys".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Traceback (most recent call last):
  File "<string>", line 3, in <module>
ModuleNotFoundError: No module named 'libstdcxx'
/etc/gdbinit:6: Error in sourced command file:
Error while executing Python code.
Reading symbols from a.exe...
(gdb) b fib
Breakpoint 1 at 0x10040108c
(gdb) ignore 1 100000
Will ignore next 100000 crossings of breakpoint 1.
(gdb) r
Starting program: /path/to/a.exe
[New Thread 16864.0x2e10]
[New Thread 16864.0x62f8]
[New Thread 16864.0x49b8]
c: 55
[Thread 16864.0x5bf4 exited with code 0]
[Thread 16864.0x49b8 exited with code 0]
[Thread 16864.0x62f8 exited with code 0]
[Inferior 1 (process 16864) exited normally]
(gdb) info breakpoints
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x000000010040108c <fib+12>
        breakpoint already hit 89 times
        ignore next 99911 hits
(gdb) q

元の約半分の89回の fib() 呼び出しで済んでいることがわかる。

別のコンパイラ（GCC）だとどうなるか？

GCC の場合は MIPS のクロスコンパイル環境を用意するのがやや面倒なので割愛するが、なんと fib(10) を計算するための fib() の呼び出し回数は２回になる。これは tail call optimization というコンパイラ技術を使って、関数呼び出しを関数内の反復処理に置き換える最適化が行われるからである。

$ gcc -O2 fib.c main.c
$ gdb a.exe
GNU gdb (GDB) 11.1
Copyright (C) 2021 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-msys".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Traceback (most recent call last):
  File "<string>", line 3, in <module>
ModuleNotFoundError: No module named 'libstdcxx'
/etc/gdbinit:6: Error in sourced command file:
Error while executing Python code.
Reading symbols from a.exe...
(gdb) b fib
Breakpoint 1 at 0x100401090
(gdb) ignore 1 100000
Will ignore next 100000 crossings of breakpoint 1.
(gdb) r
Starting program: /path/to/a.exe
[New Thread 15940.0x7004]
[New Thread 15940.0x74f8]
[New Thread 15940.0x6bdc]
c: 55
[Thread 15940.0x6510 exited with code 0]
[Thread 15940.0x6bdc exited with code 0]
[Thread 15940.0x74f8 exited with code 0]
[Inferior 1 (process 15940) exited normally]
(gdb) info breakpoints
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x0000000100401090 <fib+16>
        breakpoint already hit 2 times
        ignore next 99998 hits
(gdb) q

このように、同じプログラムでも最適化の有無、コンパイラの違いなどによって生成されるプログラムが変わり、使用するコンピュータのリソース（スタック領域など）が大きく変わる。

普段意識せず使っているコンピュータの発展はこのような技術の積み重ねによって支えられていることがわかると思う。興味を持った人はぜひコンピュータ・アーキテクチャ、コンパイラなどに親しんでほしい。

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です