Programming」カテゴリーアーカイブ

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 は遅延スロットを1つもつので、分岐命令の次の命令まで分岐前に実行される。上のアセンブリでは nop 命令が置かれている。
  • $BB0_6jal fib が2回呼ばれていて、これらは 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 の深さとなる。上のコードでは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 は1行しかでておらず、 beqz $1, $BB0_1 により $BB0_1 が繰り返し実行されることがわかる。
    • この再帰呼び出しに着目すると、1回目は fib(n-1) を呼び出すが、2回目は 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() の呼び出し回数は2回になる。これは 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

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

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

Parallelization bug in Graphlab Create 2.1

There seems to be a parallelization bug in Graphlab Create 2.1.

When calling SGraph.triple_apply() with a function which updates edge attributes, the result becomes non-deterministic in the parallel processing situation.

To solve this problem, set the number of Graphlab’s worker threads to 1, which can be done as follows.

graphlab.set_runtime_config('GRAPHLAB_DEFAULT_NUM_GRAPH_LAMBDA_WORKERS', 1)

Though it seems OK to update node attributes in parallel, I’m not sure whether the number of workers can be changed after once initiated.

NetworkX から、Graphlab Create に乗り換えた話

長らく(2年くらい)NetworkX のユーザだったが、今回 Graphlab Create に乗り換えた。それと同時に、pythonz + virtualenv から、anaconda に乗り換えた。

ここに書いていることは、自分が何か大事なことを勘違いしていなければ恐らく当たり前のことなので、わざわざ言わなくても、と思われかねない。だけど、グラフのプラットフォームを調べている初学者には多少有用かもしれないので書き残しておく。 続きを読む

Pythonz で Python のインストールが失敗する原因と対策


OS やアプリのバージョンがまちまちな複数の共有マシンで作業することが多い。Python やライブラリのバージョンを揃えたいとき、ユーザーディレクトリに Python をインストールするツールとして Pythonz や Virtualenv は便利だ。

これらなしの Python 環境は考えられないくらい依存しているのだけれど、今日 CPython 3.5.2 をインストールしようとしたら失敗。その環境には、自前で Gcc 4.8.4 をいれていたこともあり、色々試行錯誤するも改善せず。

ふと思って、make の並列化を無効化したところ、コンパイルが通る。このパターンか…と思いつつ、Pythonz から無効化する術がないことを知りしょんぼり。とりあえず Pythonz を一部書き換えてインストール成功。

こういうことは他の環境では起きたことがないので再現性低そうだなと思いつつ、時間があったら Pull request 送ってみようかな。

Virtualenv 環境からサブシェルを作って deactivate すると環境変数がおかしくなる問題の解決方法

Python の個別の環境を作る Virtualenv を Pythonz と組み合わせて使っているけど、tmux と組み合わせて使った時になんかおかしいなーと思っていた。

Virtualenv を activate したシェルから tmux を立ち上げると、tmux の中のシェルはサブシェルになる(と思ってるけど違うかもしれない)。

virtualenv は activate 時に deactivate が呼ばれるんだけど、うまく deactivate できなくなっていておかしくなる。これは、activate 前の PATH をシェル変数に保存しているんだけど、そのシェル変数がサブシェルに引き継がれないことが問題。これをサブシェルに引き継ぐためには export して環境変数にしておけば良い。ということで、activate ファイルを書き換えて環境変数として export されるようにしたところ解決した。

ラジオ日経第2の曲情報を Mac の通知センターに通知する

動機

作業するときの多くの時間はラジオ日経第2(RN2)を聞いている。いろいろな曲が朝8時から夜11時まで流れているのでとてもありがたい。

聴く際には、Adobe Air で作られた Radiko ガジェットを利用しているけど、RN2は再生中の曲の情報がツールに表示されない。再生中の曲情報も公開されているけど、タイミングがあまり正確でないのと、ブラウザで表示するというのがイマイチだったので、Mac の通知センターに再生中の曲を表示する Python スクリプトを作ってみた。

ポイントは以下の3点

  • terminal-notifier という素晴らしいツールの利用
  • タイムテーブル が JSON 形式で取得できる
  • アートワークを表示できるようにしてるけど今はできない

JSON 形式の中身が結構充実していて、アートワークの URL も含まれていたりするので、通知する際の画像 URL に指定するとアートワークが通知センターに表示されて結構気に入っていた。

ところがこれらの画像の URL は HTTP なので、App Transport Security の仕様変更で表示されなくなってしまった。確かに、外部から取得した URL に対してさらにアクセスすることになるから、脆弱ではある。曲名とアーティスト名がわかることが第一の目的なので、とりあえずはブロックされたまま保留中。

C++ で正規表現を使うときには g++-4.9 以上が必要

C++ で正規表現(regex)を使おうと思って、プログラムを作成していた。コンパイルは通るけど、どうも動作が思ったようにならない。しばらく悩んだ結果見つけたのが以下。

Is gcc 4.8 or earlier buggy about regular expressions?

4.8 以下のバージョンだと正規表現がちゃんとサポートされてないという話らしい。というわけで、g++-4.9 をインストールしたところ所望の動作を得られた。

regex_match() 便利でいい。