MIPS のアセンブリ言語で競技プログラミングの問題を解いてみる

大学の講義で扱った MIPS のアセンブリ言語で競技プログラミングの問題を解いてみた。

# 環境構築

今回は、AWS EC2 の Ubuntu 24.04 (AMI ID: `ami-05d38da78ce859165`) で実行環境を構築してみた。

とりあえず環境をアップデートする。

```bash
sudo apt-get update
sudo apt-get -y upgrade
```

アセンブラ (Binutils) と実行ツール (QEMU) をインストールする。

```bash
sudo apt-get install -y binutils-mips-linux-gnu qemu-user
```

以下のようにして、アセンブリ言語のプログラム `program.s` を実行可能ファイル `program` に変換できる。

```bash
mips-linux-gnu-as -o program.o program.s
mips-linux-gnu-ld -o program program.o
```

以下のようにして、変換した実行可能ファイル `program` を実行できる。

```bash
qemu-mips program
```

# 今回の環境におけるアセンブリ言語

## システムコール

今回の環境では、よく言われる「1 で整数を出力、10 で終了」などのシステムコールは**使えない**ようである。
かわりに、[https://syscalls.w3challs.com/?arch=mips_o32](https://syscalls.w3challs.com/?arch=mips_o32) で挙げられているシステムコールが使えるようである。
たとえば、以下のシステムコールが使える。

|操作|\$v0|\$a0|\$a1|\$a2|
|---|---|---|---|---|
|終了 (exit)|0xfa1|終了コード|-|-|
|入力 (read)|0xfa3|ファイル<br>ディスクリプタ|ストア先ポインタ|最大入力バイト数|
|出力 (write)|0xfa4|ファイル<br>ディスクリプタ|ロード元ポインタ|出力バイト数|

ファイルディスクリプタは、標準入力が `0`、標準出力が `1`、などである。
システムコールを実行すると、結果を表す値が `$v0` に格納される。
また、callee-save レジスタの値は保持されるが、caller-save レジスタの値は破壊される可能性がある。
ただし、`$a0`・`$a1`・`$a2` レジスタの値も保持される。

* [c - Linux-MIPS syscall-saved registers? - Stack Overflow](https://stackoverflow.com/questions/12336487/linux-mips-syscall-saved-registers)
* [Syscall - LinuxMIPS](https://web.archive.org/web/20180823111410/http://www.linux-mips.org/wiki/Syscall)

## エントリポイント

プログラムの実行を開始する場所として、`__start` ラベルを定義することが求められる。
さらに、ただ定義するだけではなく、`.global` を使用して公開することも求められる。

```text
.global __start
__start:
	# 正常終了する
	addi $v0, $zero, 0xfa1
	addi $a0, $zero, 0
	syscall
```

## 遅延分岐スロットを手動で扱う

MIPS といえば、分岐命令により飛ぶ場合でも分岐命令の1個次の命令を実行してから飛び先の実行に移る「遅延分岐スロット」の存在が特徴的である。

しかし、そのことを確認しようとして以下のプログラムを実行しても、命令 `addi $a0, $zero, 1` は実行されず、終了コードは `0` となってしまう。

```text
.global __start
__start:
	addi $v0, $zero, 0xfa1
	addi $a0, $zero, 0
	j dest
	addi $a0, $zero, 1 # 実行されない

dest:
	syscall
```

これは、アセンブラが命令列を以下のように自動で変更し、遅延分岐スロットが存在しないかのように実行させるためである。
(これは、`mips-linux-gnu-objdump -d program` で逆アセンブルすることにより確認できる)

```text
Disassembly of section .text:

004000d0 <__start>:
  4000d0:       20020fa1        addi    v0,zero,4001
  4000d4:       08100038        j       4000e0 <dest>
  4000d8:       20040000        addi    a0,zero,0
  4000dc:       20040001        addi    a0,zero,1

004000e0 <dest>:
  4000e0:       0000000c        syscall
        ...
```

この自動変更を停止し、遅延分岐スロットを手動で考慮したプログラムをそのまま実行させるには、プログラムの先頭に `.set noreorder` を加えるとよい。

```text
.set noreorder
.global __start
__start:
	addi $v0, $zero, 0xfa1
	addi $a0, $zero, 0
	j dest
	addi $a0, $zero, 1 # 実行される

dest:
	syscall
```

# 実装

[PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)
を解くプログラムを実装してみた。
これは、3個の整数と1行の文字列が与えられるので、これらの整数の和と与えられた文字列を空白区切りで出力する問題である。

```text
.set noreorder
.text
.global __start
__start:
	addi $s0, $zero, 0    # 整数の和
	addi $s1, $zero, 3    # 読み込む整数の数
	# 文字を読み込む準備
	addi $a0, $zero, 0
	la $a1, data_buffer
	addi $a2, $zero, 1
read_ints:
	addi $s3, $zero, 0    # 今回読み込んだ整数
read_one_int:
	# 文字を読み込む
	addi $v0, $zero, 0xfa3
	syscall
	lb $t0, ($a1)
	# 今回読み込んだ整数に10を掛ける (ロード直後の値を用いるのは避ける)
	sll $t1, $s3, 1
	sll $t2, $s3, 3
	add $t1, $t1, $t2
	# 読み込んだ値が '0' 未満 (改行や空白) なら、読み込みを終了する
	slti $t2, $t0, 0x30
	bne $t2, $zero, read_one_int_end
	addi $t0, $t0, -0x30
	# 今回読み込んだ整数を更新する
	j read_one_int
	add $s3, $t1, $t0     # 遅延分岐スロット
read_one_int_end:
	addi $s1, $s1, -1
	bne $s1, $zero, read_ints
	add $s0, $s0, $s3     # 読み込んだ整数を足す (遅延分岐スロット)

	# 求めた整数の和を文字列に変換し、出力する (空白も足しておく)
	addi $s2, $zero, 10   # 除算用 (十進数)
	addi $s3, $a1, 15     # 変換結果の最後の要素の次の要素へのポインタ
	addi $s4, $s3, -1     # 次に変換結果を格納する要素へのポインタ
	addi $t0, $zero, 0x20
	sb $t0, ($s4)
write_int:
	# 整数の和を10で割り、余りに '0' を足して文字列として格納する
	div $s0, $s2
	mfhi $t0
	mflo $s0
	addi $t0, $t0, 0x30
	sb $t0, -1($s4)
	# 商が 0 でないなら、次の桁の変換に進む
	bne $s0, $zero, write_int
	addi $s4, $s4, -1     # 格納先を更新する (遅延分岐スロット)
	# 変換結果の文字列を出力する
	addi $v0, $zero, 0xfa4
	addi $a0, $zero, 1
	addi $a1, $s4, 0
	sub $a2, $s3, $s4
	syscall

	# 1行読み、そのまま出力する
	addi $s1, $zero, 0x0a # 改行コードを読み込んだら終了する用
	addi $a0, $zero, 0
	la $a1, data_buffer
	addi $a2, $zero, 1
print_line:
	addi $v0, $zero, 0xfa3
	syscall
	lb $s0, ($a1)
	addi $a0, $zero, 1
	addi $v0, $zero, 0xfa4
	syscall
	bne $s0, $s1, print_line

	# プログラムを終了する
	addi $a0, $zero, 0    # 終了コードの 0 と読み込み元の標準入力を兼ねる
	addi $v0, $zero, 0xfa1
	syscall

.data
data_buffer:
	.space 16
```

# 結論

Ubuntu 24.04 上で MIPS のアセンブラと実行用プログラムを用意し、競技プログラミングの問題を解くコードを動かすことができた。