LLVM Assemblyを書けるようになりたい

# LLVM Assemblyを書けるようになりたい

新しいプログラミング言語を作ろうとして，今回もインタープリターを書こうとしていたんだけれど，
どうせだったらインタープリタの実行マシン（ソフト上の）をLLVMにしてしまえば，
後々コンパイルするにも便利だから，実行マシンをLLVM IRを受け付けるようなものにしようと考えた．

そこでLLVMのリファレンスを読んでいたのだが，
これを読んだって書けるようにはならないなということで，体系的にまとめてみることにした．

## その前に

LLVM AssemblyはLLVM IRのテキスト表現．

新しいプログラミング言語を作るので，それに必要な最低限のLLVM IRの文法や書き方を覚えたい．
変数や関数の定義，あとはスコープの概念と構造体，配列やポインターが扱えればOK．
もちろん基本的な四則演算と制御演算もだ．

正確性，最新版に追従しているという保証もないのでご注意を．
さらに，今回の用途で使うので適当なコメントを追加している．

さらに，コードは適当に改変したりしているので一々動作を確認はしていない．

ちなみに本記事では次のコマンドを使ってC言語のソースコードをLLVMに変換している．

```bash
$ clang -emit-llvm -O0 -S main.c
$ llc main.ll
$ clang main.s
$ ./a.out
```

上記コマンドを実行している環境は以下の通り．
日付はちょっとずれる．

```
CPU: AMD A10-7850K Radeon R7, 12 Compute Cores 4C+8G
OS: ArchLinux(2024/10/23)
```

## 環境構築


本記事の中で使うプログラム

- `llvm`
- `clang`(`gcc`でもよいが今回はこちらで統一)
- `make`

ArchLinuxでは次のコマンドで入れることができる．

```bash
sudo pacman -S make llvm clang
```

LLVM Assemblyはテキストで書くことができ，その拡張子は`.ll`である．
なので分かりやすく`main.ll`という名前にしておく．

これをアセンブリに変換するには次のようなコマンドを使う．

```bash
$ llc main.ll
```

これで`main.s`というアセンブリが記述されたテキストファイルが生成される．

さらにこれを`clang`を使って実行可能なファイルに変換する．

```bash
$ clang main.s
```

環境にもよるがArch Linuxの場合`a.out`というファイルが生成され，
これを実行するとLLVM Assemblyで記述したプログラムを実行することができる．

毎回これを打つのは大変なので，`make`で自動化しておく．


`Makefile`という名前のファイルを作成し，次のように書く．

```make
all: a.out

main.s: main.ll
	llc main.ll

a.out: main.s
	clang main.s
```

すると以下のように短縮できる．

```bash
$ make
$./a.out
```

もちろんこんな感じにまとめればone lineで実行可能だ．

```bash
$ make && ./a.out
```


## まずは何もしないプログラムから

C言語で何もしないプログラムを書いてみる．


```c
int main(void){
  return 0;
}
```

これをLLVM Assemblyで書いてみる．
まずは，`main.ll`というファイル名で次のソースコードを書いてみる．

```llvm
define i32 @main() {
  ret i32 0
}
```

見比べてみるとほぼ同じだ．

`int`は`i32`で`int32_t`と同じで32bitを意味する．

`ret`は`return`を意味しており，`i32 0`は`0`を意味している．

## 演算をする

まずは単純な足し算をどう実装すればよいのかを見ていく．
`1+2`を実装すると次のようになる．

```llvm
define i32 @main() {
  %1 = add i32 1, 2
  ret i32 %1
}
```

C言語で言うと次のようなイメージ．

```c
int main(void){
  return 1+2;
}
```

ここで`%1`のように`%`から始まるトークンは局所的変数名である．(大域的変数名は`@`から始まる)
`add`命令によって型を指定した後に直接値を入れて`1+2`をし，その結果を`%1`に代入．
そして`%1`を`return`している．

特徴としては`add`する際に型を指定している．
型には様々な種類があるが，C言語の型との対応は次の通り．

```
| C type      | LLVM type |
|-------------+-----------|
| :1          | i1        |
| int8_t      | i8        |
| int16_t     | i16       |
| int32_t     | i32       |
| int64_t     | i64       |
| uint8_t     | i8        |
| uint16_t    | i16       |
| uint32_t    | i32       |
| uint64_t    | i64       |
| float       | float     |
| double      | double    |
| long double | x86_fp80  |
| :<label>    | label     |
| void*       | ptr       |
```


C言語には直接の対応がなくビットフィールドで表現する必要があるが，LLVMでは1bitの幅の数字も扱える．
また特殊な`label`という方も存在するので制御構文の所で説明する．

main関数の実行結果はBashを使っていれば，以下のように確かめることができる．

```
$ ./a.out
$ echo $?
3
```

## 変数を使う

先程の例では直接`1+2`を実装したが，一度変数に入れてから計算する場合を見てみよう．

```llvm
define i32 @main() {
  %a = alloca i32
  %a = alloca i32
  store i32 1, ptr %a
  store i32 2, ptr %b
  %1 = load i32, ptr %a
  %2 = load i32, ptr %b
  %3 = add i32 %1, %2
  ret i32 %3
}
```

C言語で言うと次のようなイメージ．

```c
int main(void){
  int a = 1;
  int b = 2;
  return a + b;
}
```

変数を使いたい場合，まずメモリを確保する所から始まる．(1-2行目)
具体的には，`alloca`を使いその関数内で有効なメモリを確保する．(スタックに積まれ，関数が終わったら解放される)
この時`alloca`の戻り値はポインタであることに注意する必要がある．
つまり`%a`や`%b`にはポインタ型が入っている．
これはちょっとC言語とは違う印象を受ける．

次に確保したメモリに値を書き込む．(4-5行目)
具体的には`store`を使うがこちらも型を忘れずに指定する必要がある．
代入したい値はもちろん`i32`だが，代入先はポインタであるため`ptr`になる．

次に代入した値を`load`で読み出す．(6-7行目)
ここで`store`したんだから`add`には`%a`，`%b`を渡せばいいじゃんと思うかもしれないが，
`%a`と`%b`はポインタ型だから数字ではない．
したがって，`%a`と`%b`に入っている値を取り出すには一度`load`する必要がある．

値を取り出せた後はその値を足す．(8行目)
ここで`add`は直接の値でも変数の値でもどちらでもよいことが分かる．

上の例ではC言語に対応しない変数名には連番を使い，なおかつ`%1`から始めたが，少しだけルールがある．
こうした明示的に指定しない変数を使いたい場合は昇順の連番を使う．
ただし，数字がスキップする分には問題ない．

さらに，数字を使う場合は`%0`は別の意味が割り当てられる場合があるので注意する．

例えば次のようなことはできない．

```llvm
define i32 @main() {
  %0 = alloca i32
  ret i32 0
}
```

なぜなら，最初の基本ブロック(エントリーブロック)は`0:`というラベル(その行にジャンプするための目印)が暗黙の内に設定され，`%0`でアクセスできるようになっているため，
そのラベル情報と`alloca`を受ける変数の名前が衝突してしまうからだ．
つまり上のコードは次のように解釈される．

```llvm
define i32 @main() {
0:
  %0 = alloca i32
  ret i32 0
}
```

これでは名前が衝突してしまう．

これを回避するためには暗黙の`0:`を使うのではなく，別の名前を割り振ってあげればよい．
例えばこんな感じ．

```llvm
define i32 @main() {
entry:
  %0 = alloca i32
  ret i32 0
}
```

これは通る．

もちろん上で示したように，自分で名前やラベルをつけて変数を定義しても問題ない．
例えばこんな感じ．

```llvm
%var = add i32 1, 2
```

## 変数の型を変換する

今までは全て`int`として`i32`を扱ってきたため問題なかったが，実際には色々な型を使いたくなる．
そして異なる型同士で演算したくもなってくる．

そういう場合には必ず型を変換してから演算する必要がある．
そして型を変換するためには変換する前の型が何で，した後の型が何かもきっちりと指定する必要がある．

また型を変換するには整数か浮動小数点かどうか，少ないビット数から大きいビット数に変換するのか，大きいビット数から小さいビット数に変換するのかどうかで全然変わってくる．
それに合わせて全て命令を使い分ける必要がある．

ここでは2つの型を比較し，より少ないビット数の型を小さい型，より大きいビット数を大きい型と表現する．
また変換元の型を`<from type>`，変換先の型を`<to type>`．そして変換したい値を`<op>`で表現する．


### 整数同士の変換

小さい型から大きい型へ．

```llvm
zext <from type> <op> to <to type>
```

この名前はおそらくzero extensionの意味と思われ，変換時に増えたビットは0埋めする．

例えば`i8`の`%from`の値を`i16`に変換したい時は次のようになる．

```llvm
%to = zext i8 %from to i16
```

この場合数値の拡張が行われ，`i8`の前のビットは0であると見做して`i16`まで拡張する．


大きい型から小さい型へ

```llvm
trunc <from type> <op> to <to type>
```

逆に`i16`の`%1`の値を`i8`に変換したい場合は次のようになる．

```llvm
%to = trunc i16 %from to i8
```

この場合は余った値を削るだけでよいためそのままの名前だ．


### 整数と浮動小数点数の変換


整数から浮動小数点数であれば．

```llvm
sitofp <from type> <op> to <to type>
uitofp <from type> <op> to <to type>
```

signed integer to floating pointとunsigned integer to floating pointの略だろう．

例えば`i32`から`double`への変換は次のようになる．

```llvm
%to = sitofp i16 %from to double
```

浮動小数点数から整数であれば

```llvm
fptosi <from type> <op> to <to type>
fptoui <from type> <op> to <to type>
```

floating point to signed integerとfloating point to unsigned integerの略だろう．

こちらも`double`から`u32`の変換は次のようになる．

```llvm
%to = fptoui double %from to u32
```


### 浮動小数点数同士の変換

小さい型から大きい型へ．

```llvm
fpext <from type> <op> to <to type>
```

floating point extensionと思われる．
これは例えば，`float`から`double`への拡張だ．


大きい型から小さい型へ

```llvm
fptrunc <from type> <op> to <to type>
```

floating point truncと思われる．
これは例えば先程の逆で，`double`から`float`への縮小だ．

## 制御構文

ちょっと細かな話になってしまったので，重要な所に戻る．
より複雑なプログラムを書こうとすると条件分岐やループなどを実現したくなる．
これをどうやってLLVMで書けばよいのかを順番に説明していく．

### 基本ブロック

まずは基本ブロックについて説明する必要がある．
基本ブロックとはその名の通り複数の命令をまとめてひとまとまりにしたものだ．

例えば次のような例を考えてみる

```llvm
define i32 @main() {

1:
  br label %2

2:
  br label %3

3:
  ret i32 0
}
```

この場合全部で3つの基本ブロックがあり，
3-5行目の`1:`から始まるブロック，6-8行目の`2:`から始まるブロック，
最後が9-10行目の`3:`から始まるブロックだ．

先取りになるが`br`という命令はC言語の`goto`にあたりラベルにジャンプすることができる．
ここでのラベルは`%2`や`%3`があるが，これは`2:`と`3:`の場所に対応しており，変数のように`%`でアクセスする．

このようにラベルから始まり，次のラベルまでが一つのブロックとして扱われる．

制御構文ではこのようなラベルを上手く使うことで，複雑なロジックでも簡潔に表現している．

### ジャンプ

先程も出てきたがC言語の`goto`にあたる命令は`br`という命令で実現できる．
`br`は次のように使う．

```llvm
br label <op>
```

`<op>`を`label`として解釈しているのがポイントで，`<op>`に代入された値を見ている訳ではなくて純粋にラベルとして使用している．
先程の例をもう一度見てみる．


```llvm
define i32 @main() {
  br label %1
1:
  br label %2

2:
  br label %3

3:
  ret i32 0
}
```

この例だと別に`br`を使う理由もないが，
まず上から`br`で`1:`にジャンプする．
そして`1:`の基本ブロックが実行され，その中で`br`命令により`2:`にジャンプする．
そして`2:`の基本ブロックが実行され，`br`命令により`3:`にジャンプする．
`3:`の基本ブロックで`return`が呼ばれてこのmain関数は終了する．

ここで注意しないといけないのが，ラベルにあたる`1:`や`2:`は変数名の一部としてカウントされているため，同名の変数を使うことはできない．
つまり次のようなことはしてはいけない．

```llvm
    %1 = add i32 1, 2
  1:
    br label %2
```

この場合，最初に`%1`に足し算の結果を代入しているが，その後でラベルとしても`1:`を指定している．
このラベルも変数`%1`でアクセスするため，二重で数値が定義されることになりエラーとなる．


### 条件分岐

先程は`goto`は`br`を使うといったが，`if`も同様に`br`を使って記述される．

```llvm
br i1 <cond>, label <op1>, label <op2>
```

`<cond>`が`1`であれば`<op1>`にジャンプし，`<cond>`が`0`であれば`<op2>`にジャンプする．

例えば`if(true){}else{}`という何もしない条件分岐は次のように書ける．

```llvm
define i32 @main() {
  br i1 1, label %if.true, label %if.false

if.true:
  ret i32 0

if.false:
  ret i32 1

}
```

`<cond>`に入る`i1`をどうやって作成するのかについては，比較演算子や論理演算の所で説明する．

### ループ

ループは`br`を使えば実現できるが，もう一つパターンがある．

まずは`br`を使った無限ループだ．

```llvm
define i32 @main() {
  br label %start

start:
  br label %start

end:
  ret i32 1

}
```

ここで注意が必要なのは次のような書き方ができないということだ．

```llvm
define i32 @main() {

start:
  br label %start

end:
  ret i32 1

}
```

制約条件として一番最初の基本ブロック(エントリーブロック)より前にジャンプすることはできない，というものがあり，エントリーブロック自身にはジャンプできない．

ちなみにだが，以下のようにエントリーブロックが明示的に与えられていない場合は，

```llvm
define i32 @main() {
  br label %start
```

このように`0:`があり，それが`%0`としてアクセスできるという暗黙のルールがある．

```llvm
define i32 @main() {
0:
  br label %start
```

変数を`%0`から始められないと違和感があるという場合は，
以下のように関数のエントリーブロックには`entry:`を使うとかすればよい．

```llvm
define i32 @main() {
entry:
  br label %start
```

まだまだ最初の触りだけしか書けていないが，とりあえずはここまで．