コンパイラのコード生成: 繰返し

# はじめに

このテキストでは簡単なC言語プログラムを元にコンパイラがRISC-Vのアセンブリコードをどのように生成するかについて，考え方を示しました。

# C言語のソースコード(繰返し)

プログラムを実行する時に，元になったプログラムコードのことを**ソースコード**と言います。

このテキストで用いるC言語のソースコードはこちらです。

```c
int calc(int n) {
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}
```

# RISC-Vのアセンブリコード

次のようにコンパイルします。

```bash
riscv64-unknown-elf-gcc -S -O0 -march=rv32i -mabi=ilp32 -o sample.s sample.c
```

得られた RISC-V のアセンブリコードは次の通りです。

```
	.file	"sample.c"
	.option nopic
	.text
	.align	2
	.globl	calc
	.type	calc, @function
calc:
	addi	sp,sp,-48
	sw	s0,44(sp)
	addi	s0,sp,48
	sw	a0,-36(s0)
	sw	zero,-20(s0)
	li	a5,1
	sw	a5,-24(s0)
	j	.L2
.L3:
	lw	a4,-20(s0)
	lw	a5,-24(s0)
	add	a5,a4,a5
	sw	a5,-20(s0)
	lw	a5,-24(s0)
	addi	a5,a5,1
	sw	a5,-24(s0)
.L2:
	lw	a4,-24(s0)
	lw	a5,-36(s0)
	ble	a4,a5,.L3
	lw	a5,-20(s0)
	mv	a0,a5
	lw	s0,44(sp)
	addi	sp,sp,48
	jr	ra
	.size	calc, .-calc
	.ident	"GCC: (GNU) 8.2.0"
```

レジスタマップは次の通りです。

|レジスタ|意味|
|:------|:---|
|sp     |**スタックポインタ**: スタック領域の先頭を表します。|
|s0     |**フレームポインタ**: スタック領域の中に記憶されている**変数**や**引数**を参照するときに使います。|
|zero   |定数0|
|a0     |第1引数，戻り値|
|a5     |一時レジスタ|
|a4     |一時レジスタ|
|ra     |戻り先アドレス|

メモリマップは次の通りです。

|アドレス|変数|
|------:|:---|
|44(sp) |以前のフレームポインタ|
|-36(s0)|n|
|-20(s0)|sum|
|-24(s0)|i|

# コード生成の考え方

このようなアセンブリコードはどのように生成されたのでしょうか？ ソースコードと対比しながら見ていきましょう。

## 関数の定義

次のようなコードは関数の定義の一例です。

```c
int calc(int n) {
  ...
  return sum;
}
```

関数の定義をアセンブリコードに変換するときには次の原理に従います。

1. 関数名を表すラベルを定義します。
2. スタックポインタをフレームサイズの分減らします。(後述)
3. フレームポインタをスタックにバックアップします。
4. 元のスタックポインタの内容をフレームポインタにコピーします。
5. 引数の値をフレームの該当場所にコピーします。
6. ...をコード生成します。
7. フレームに記録された戻り値をレジスタ`a0`にコピーします。
8. スタックにバックアップしたフレームポインタの内容を元に戻します。 
9. スタックポインタをフレームサイズの分，増やします。(後述)
10. サブルーチンから復帰します。

アセンブリコードとしては次のようになります。

```
calc:				# 1
	addi	sp,sp,-48	# 2
	sw	s0,44(sp)	# 3
	addi	s0,sp,48	# 4
	sw	a0,-36(s0)	# 5
...				# 6
	lw	a5,-20(s0)	# 7
	mv	a0,a5		# 7
	lw	s0,44(sp)	# 8
	addi	sp,sp,48	# 9
	jr	ra		# 10
```

7 は2つの命令にまたがっています。

なお，`jr ra` は jump register ということで，レジスタ `ra` にジャンプするという意味です。

## 自動変数の定義

C言語の関数の中で定義した変数のことを**自動変数**と言います。

次のようなコードの断片は自動変数の定義の一例です。

```c
    int sum = 0;
```

自動変数はスタック領域に確保された**フレーム**というメモリ領域に記憶されます。フレームには他にレジスタ退避などにも使用します。

RISC-V では，フレームサイズは，次の和で表されるようです。

* 自動変数に必要なメモリサイズを16バイト単位で切り上げた値
* 引数に必要なメモリサイズを16バイト単位で切り上げた値
* 16バイト

メモリマップは次のようになります。(ただし全ての変数，引数は32ビットであるものとします)

|変数|アドレス|
|:---|------:|
|元のフレームポインタ|(fs-4)(sp) (=-4(s0))|
|自動変数|((vn - vi) * 4 + an * 4 - fs)(s0)|
|引数|((an - ai) * 4 - fs)(s0)|

* fs = フレームサイズ = 16 + vs + as
* vs = 自動変数サイズ = (vn * 4)
* as = 引数サイズ = (an * 4)
* vn = 自動変数の個数を4単位で切り上げた値
* an = 引数の個数を4単位で切り上げた値と8のうち小さい方
* vi = 自動変数の番号 (vi >= 1)
* ai = 引数の番号 (ai >= 1)

## 変数の初期化・代入

変数の初期化や代入は次のようにします。

* 0 を代入するとき: 
  * `sw zero, 変数のアドレス`
* それ以外を代入するとき:
  * `li 一時レジスタ, 値`
  * `sw 一時レジスタ, 変数のアドレス`

## for 文

```c
for(初期化式; 条件式; 継続式)
  ブロック
```

という記述があったとします。

次のようにアセンブリコードにします。

```
	(初期化式のアセンブリコード)
	j	.Ljudge
.Lblock:
	(ブロックのアセンブリコード)
	(継続式のアセンブリコード)
.Ljudge:
	(条件式のアセンブリコード)
	(条件式に合った分岐命令) .Lblock
```

この例では条件式が `i <= n` なので，`i`が`n`以下の時に`.Lblock`に分岐します。
したがって，`.Ljudge:`以降は次のようにアセンブリコードを生成します。

```
	lw	(一時レジスタ1), (iのアドレス)
	lw	(一時レジスタ2), (nのアドレス)
	ble	(一時レジスタ1),(一時レジスタ2),.Lblock
```

# 加算

`i++` は `i += 1` と同じ意味です。
`sum += i` は `sum = sum + i` と同じ意味です。

`a = b + c` のような式は次のようにアセンブリコードを生成します。

```
	lw	(一時レジスタ1), (bのアドレス)
	lw	(一時レジスタ2), (cのアドレス)
	add	(一時レジスタ2), (一時レジスタ1), (一時レジスタ2)
	sw	(一時レジスタ2), (aのアドレス)
```

`a = b + 定数` のような式は次のようにアセンブリコードを生成します。

```
	lw	(一時レジスタ), (bのアドレス)
	addi	(一時レジスタ), (一時レジスタ), (定数値)
	sw	(一時レジスタ), (aのアドレス)
```

# 一時レジスタの割り当て

空いているレジスタを割り当てること**レジスタ割り当て**(register allocation)といいます。レジスタを使用している区間のことを**レジスタ生存区間**といい，それぞれのレジスタのレジスタ生存区間が重なり合わないよう，かつできるだけ少ないレジスタ数で割り当てるようにします。

# 類題

では次のようなC言語のプログラムをアセンブリコードにコンパイルすると，どのようなコードを生成するでしょうか？

```c
int calc(int m, int n) {
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += m;
    }
    return sum;
}
```