LLVM IR で Welcome to AtCoder を解いてみた

[Qiita Engineer Festa 2024（キータ・エンジニア・フェスタ 2024） - Qiita](https://qiita.com/official-campaigns/engineer-festa/2024)
において、約1ヶ月で38記事という大量の記事の投稿を要求されることがわかった。
そこで、あまりコストをかけずに記事数を稼ぐ方法を考えた結果、「Welcome to AtCoder を様々な言語で解く」ことを思いついた。
単に解くだけでなく、使用する言語仕様の解説を入れれば、記事として一応成立するだろう。

# Welcome to AtCoder

[PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)

Welcome to AtCoder では、以下の形式で整数 $a$, $b$, $c$ および文字列 $s$ が入力として与えられる。

```text
a
b c
s
```

この入力をもとに、与えられた整数の和 $sum = a + b + c$ および文字列 $s$ を、以下の形式で出力することが求められる。

```text
sum s
```

整数 $a$, $b$, $c$ は 1 以上 1,000 以下であり、文字列 $s$ の長さは 1 以上 100 以下である。

# 今回用いる LLVM IR の機能

今回は、公式ドキュメントを参照せず
[LLVM IRで湯婆婆を実装してみた #AdventCalendar2020 - Qiita](https://qiita.com/luth1171/items/ef34f3211d6bc195dc21)
を参考に書き方を推測してみた。~~(手抜き)~~

## main関数の定義

```llvm
define i32 @main(i32 %0, i8** %1) {
  ;; 処理内容
  ret i32 0
}
```

のように書くことで、エントリポイントの `main` 関数を定義できる。
引数の `%0` と `%1` は省略可能だが、書いたほうがわかりやすいだろう。
(参照した記事中、`opt` コマンドでこれらが追加された様子が紹介されている)

行内の `;;` 以降の部分はコメントのようである。

`ret i32 0` がC言語の `return 0;` に相当し、`main` 関数の戻り値として `0` を返す処理であると推測できる。

「処理内容」の中身は、`%数値 = コマンド` の形式で書く。
たとえば

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

のような感じである。
この `main` 関数の場合、数値は `3` から始めなければならないようである。
最初の数値を試しに `%2` や `%4` にしてみると、

> error: instruction expected to be numbered '%3'

というコンパイルエラーになった。

その後、数字はコマンド1個ごとに1ずつ増やしていく。
「コマンド」の結果が不要な場合は、`%数値 =` を省略可能である。
ただし、この場合省略しなかった場合に書かれるはずだった数値は開けなければならない。
さらに、`%数値` の数値のかわりに英文字列で名前をつけることができる。
英文字列で名前をつけた場合、そこの分の数値は増やさない。

```llvm
define i32 @main(i32 %0, i8** %1) {
  %3   = add i32 1, 2
         add i32 3, 4 ;; %4 = を省略
  %5   = add i32 5, 6 ;; ここが %4 にはならない
  %foo = add i32 7, 8 ;; 名前付き
  %6   = add i32 9, 0 ;; ここが %7 にはならない
  ret i32 0
}
```

## メモリの確保

```llvm
%3 = alloca [サイズ x i8], align 16
%4 = getelementptr inbounds [サイズ x i8], [サイズ x i8]* %3, i32 0, i32 0
```

のように書くことで、(文字列の処理などに用いる) メモリ領域を確保できるようである。
「サイズ」はバイト数であると推測した。
`alloca` でメモリを確保し、`getelementptr` でそれをポインタに変換するようである。

:::note info
AtCoder の環境においては、`getelementptr` を用いずに `alloca` の結果を直接ポインタを渡すべき場所に渡しても動くようである。
とはいえ、わかっているやり方から外れると、厳密にチェックを行うモードでは弾かれるなど、未知の不都合が起こる可能性が考えられる。
これはあくまでも憶測であるが、`getelementptr` を入れておくのが無難だろう。
:::

## 文字列の定義

`main` 関数の前に

```llvm
@名前 = private unnamed_addr constant [サイズ x i8] c"文字列\00", align 1
```

と書くことで、文字列を定義できるようである。
「サイズ」は、終端のナル文字を含めた文字列のバイト数のようである。

定義した文字列は、確保した領域と同様に

```llvm
%数値 = getelementptr inbounds [サイズ x i8], [サイズ x i8]* @名前, i32 0, i32 0
```

でポインタに変換できるようである。
ポインタを関数の引数として直接指定する場合は `inbounds` の後にカッコが入ったが、このように関数と関係なくポインタを得る場合はカッコをつけるとエラーになり、つけないべきであるようである。

## C言語の標準ライブラリ関数の使用

LLVM IR では、`printf` や `fgets` などのC言語の標準ライブラリ関数を使用できるようである。
使用するには、`main` 関数の後ろで

```llvm
declare 返り値の型 @関数名(引数の型リスト)
```

のように宣言し、`main` 関数内で

```llvm
%数値 = call 返り値の型 @関数名(引数リスト)
```

のようにして呼び出すことができるようである。
引数リストでは、引数を `型 値` の形式で表現するようである。
型は、`int` は `i32`、`char` は `i8` と書けばよさそうである。

また、`printf` などの可変長引数の関数を呼び出す際は、

```llvm
%数値 = call 返り値の型 (引数の型リスト) @関数名(引数リスト)
```

のように引数の型リストを追加するようである。

:::note info
AtCoder の環境では、この引数の型リストを追加しなくても動くようだった。
とはいえ、追加しないことによる悪影響が無いかはわからない。
:::

`fgets` で用いる `stdin` は、`main` 関数の前で

```llvm
@stdin = external global i32*, align 8
```

と宣言して、`main` 関数内で

```llvm
%数値 = load i32*, i32** @stdin, align 8
```

とすることで値を取得できるようである。
型は、参照した記事ではきちんと `FILE` 構造体に相当する内容を記述しているようだったが、今回は現在主流の計算機環境ではどのポインタも表現は同じだろうという仮定のもと、`FILE` のかわりに適当に `i32` を用いた。
少なくともこれで AtCoder の環境では動くようである。

また、参照した記事では名前が `__stdinp` となっていたが、これでは AtCoder の環境では動かず、`stdin` にしたら動くようだった。

# 提出コード

```llvm
@stdin = external global i32*, align 8

@format = private unnamed_addr constant [6 x i8] c"%d %s\00", align 1

define i32 @main(i32 %0, i8** %1) {
  ;; メモリを確保し、入力を読み込む
  %3 = load i32*, i32** @stdin, align 8
  %4 = alloca [16 x i8], align 16
  %5 = alloca [16 x i8], align 16
  %6 = alloca [2048 x i8], align 16
  %7 = getelementptr inbounds [16 x i8], [16 x i8]* %4, i32 0, i32 0
  %8 = getelementptr inbounds [16 x i8], [16 x i8]* %5, i32 0, i32 0
  %9 = getelementptr inbounds [2048 x i8], [248 x i8]* %6, i32 0, i32 0
  call i8* @fgets(i8* %7, i32 16, i32* %3)
  call i8* @fgets(i8* %8, i32 16, i32* %3)
  call i8* @fgets(i8* %9, i32 2048, i32* %3)
  ;; 数値をパースし、加算する
  %13 = call i32 @atoi(i8* %7)
  %14 = call i32 @atoi(i8* %8)
  %15 = call i8* @strchr(i8* %8, i32 32)
  %16 = call i32 @atoi(i8* %15)
  %17 = add i32 %13, %14
  %18 = add i32 %17, %16
  ;; 文字列と組み合わせて出力する
  %19 = getelementptr inbounds [6 x i8], [6 x i8]* @format, i32 0, i32 0
  call i32 (i8*, ...) @printf(i8* %19, i32 %18, i8* %9)
  ret i32 0
}

declare i8* @fgets(i8*, i32, i32*)
declare i32 @printf(i8*, ...)
declare i32 @atoi(i8*)
declare i8* @strchr(i8*, i32)
```

[提出 #54862599 - AtCoder Beginners Selection](https://atcoder.jp/contests/abs/submissions/54862599)