最近Qiitaで流行りの湯婆婆1の実装をLLVM IRで行ってみました。これは筆者のLLVMの勉強も兼ねているので~~できるだけカンニングせずに実装しています。~~嘘です面倒だったので割とカンニングしました。（土下座）
湯婆婆を題材にしたLLVMのチュートリアルのような感じで書いたので、LLVMを知らない、聞いたことはあるけどよく知らない、という人でも何となく雰囲気は分かってもらえると良いなと思います2。
LLVM IRとは
LLVM IRは、簡単に言うとLLVMが入力言語とする中間言語のことです。LLVMとは何ぞや、という話はあるのですが、先にLLVM IRとは何ぞや、中間言語とは何ぞや、という話を先にしてしまいます。
まず簡単なLLVM IRをお見せすることで雰囲気を感じ取ってもらおうかと思います。以下は1 + 2を計算した結果を返すプログラムです3。
define i32 @main(i32, i8**) {
%3 = add i32 1, 2
ret i32 %3
}
こんな感じで、C言語とアセンブラを足して２で割ったような見た目をしています。アセンブラよりは幾分かマシなアセンブラといった感じでしょうか4。
もう一つ例をお見せしておくと、次は２つ引数を受け取って足し算した結果を返す関数です。
define i32 @add(i32, i32) {
%3 = add i32 %0, %1
ret i32 %3
}
勘の良い方はこの時点でお気づきかと思いますが、大体の命令は即値とレジスタを混ぜて書けます5。レジスタの数も無制限で、１回しか代入できない代わりにレジスタの数を心配する必要もありません6。
ここまでの説明でLLVM IRがプログラミング言語の一種であるということは分かってもらえたのではないかと思いますが、次に中間言語とは何者かということについて軽く触れておきます。
例えばC言語からコンパイルする場合だと（大抵の言語ではこの過程を辿りますが）
C言語 -> 中間言語 -> 機械語
の流れを辿ります。このようにコンパイル先の言語の間に１つ別の言語を挟むことが多く、これのことを中間言語と呼びます7。
ちなみにLLVMはgo8やSwiftなどの言語でバックエンドに採用されていて、これらの言語では中間言語がLLVM IRになります。ただしLLVM IRというのは少し語弊があり、実際はLLVM BC(をメモリに載せたもの)だと思います。C++, Go, Pythonなどの言語ではLLVM API9を用いて開発ができ、オブジェクトファイルを吐き出すところまではLLVM APIがやってくれるようです。
……という感じで、ほんのさわりしか説明してないですが、LLVM IRの雰囲気は何となく感じてもらえたのではないかと思います。実際にある程度の意味のあるプログラムを書くとどうなるかは、この記事のメインである湯婆婆で確認してもらえればと思います。
LLVMとは何ぞや
https://llvm.org/ からの引用：
The LLVM Core libraries provide a modern source- and target-independent optimizer, along with code generation support for many popular CPUs (as well as some less common ones!) These libraries are built around a well specified code representation known as the LLVM intermediate representation ("LLVM IR"). The LLVM Core libraries are well documented, and it is particularly easy to invent your own language (or port an existing compiler) to use LLVM as an optimizer and code generator.
LLVMとは、一言で言うと「任意のプログラミング言語に対応可能なコンパイラ基盤」10です。
「コンパイラ基盤」という意味をもう少し詳しく説明すると、LLVM11はLLVM IRという中間言語12から機械語13へのコンパイルをしています。コンパイルしたい言語（C言語とか）からLLVM IRへプログラム変換することができたら、後の機械語に直すところ（と中間言語・機械語命令レベルでの最適化）はLLVMがやってくれるというわけです。このあたりが「コンパイラ基盤」と言われる所以ですね。
とはいっても、決してLexerやParser周り、ASTの生成など14を楽できるわけではないです。それでも大変な低レベルな部分の最適化を任せられるので、オレオレ言語を作る時などにはとてもありがたい存在です。（コンパイラを書いたことがある人なら分かるはず）
LLVMの使い方
一通り使えるようになるまでざっくり書いてはいますが、かなり省略しているので環境によっては詰まるかもしれません。Macの人はこの手順通りでうまくいくはずです。
インストール
ここは参考文献の通りにやればすんなりいくはずです。
$ brew install llvm
$ echo 'export PATH="/usr/local/opt/llvm/bin:$PATH"' >> ~/.bash_profile # パスを通す
コンパイル
$ llc filename.ll
とするとアセンブラ(filename.s)が生成されます。実行したい時はgccやclangで実行可能形式に変換します。例えばgccでは以下のようにすると実行可能ファイルを作れます15。
gcc filename.s -o output_filename
（おまけ）最適化
optコマンドを使うとLLVM IRの最適化ができます。入力はLLVM IRとLLVM BC(bitcode)のどちらでもいけるようです。
何も指定しないとLLVM BCの方で出力しますが、-Sを指定することでLLVM IRになります。
公式の説明：http://llvm.org/docs/CommandGuide/opt.html
$ opt [options] [filename]
$ opt -S [filename] # LLVM IRで出力
（おまけ）コンパイル時の最適化
次のような感じでコンパイル時の最適化オプションを指定できます。-S0から-S3まであります（デフォルトは-S2）。このあたりはgccとかと同じですね。
念のため公式ドキュメント：https://llvm.org/docs/CommandGuide/llc.html
$ llc -S3 filename.ll
（おまけ）カンニング
gccが吐き出すLLVM IRをカンニングするためには次のようにします。
$ gcc -S -emit-llvm filename.c
湯婆婆の全貌
さて、これから「湯婆婆」の話をします。
まず先に湯婆婆の全貌からお見せします。
%struct.__sFILE = type { i8*, i32, i32, i16, i16, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, %struct.__sFILEX*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 }
%struct.__sFILEX = type opaque
%struct.__sbuf = type { i8*, i32 }
@str1 = private unnamed_addr constant [50 x i8] c"契約書だよ。そこに名前を書きな。\0a\00", align 1
@str2 = private unnamed_addr constant [58 x i8] c"フン。%sというのかい。贅沢な名だねぇ。\0a\00", align 1
@str4 = private unnamed_addr constant [106 x i8] c"今からお前の名前は%sだ。いいかい、%sだよ。分かったら返事をするんだ、%s!!\0a\00", align 1
@__stdinp = external global %struct.__sFILE*, align 8
define void @rtrim(i8*) {
start:
%1 = alloca i8*, align 8 ;; pointer
%2 = alloca i32, align 4 ;; int i
store i8* %0, i8** %1, align 8
store i32 0, i32* %2, align 4 ;; i = 0
br label %loop_start
loop_start:
%3 = load i8*, i8** %1, align 8 ;; str
%4 = load i32, i32* %2, align 4
%5 = getelementptr inbounds i8, i8* %3, i32 %4
%6 = load i8, i8* %5, align 1
%7 = sext i8 %6 to i32
%test = icmp ne i32 %7, 10 ;; 改行かどうか調べる
br i1 %test, label %then, label %else
then:
%8 = load i32, i32* %2, align 4
%9 = add nsw i32 %8, 1
store i32 %9, i32* %2, align 4 ;; ++i
br label %loop_start
else:
%10 = load i8*, i8** %1, align 8
%11 = load i32, i32* %2, align 4
%12 = getelementptr inbounds i8, i8* %10, i32 %11
store i8 0, i8* %12, align 1
ret void
}
define i32 @strLen(i8*) {
start:
%1 = alloca i8*, align 8 ;; pointer
%2 = alloca i32, align 4 ;; int i
store i8* %0, i8** %1, align 8
store i32 0, i32* %2, align 4 ;; i = 0
br label %loop_start
loop_start:
%3 = load i8*, i8** %1, align 8 ;; str
%4 = load i32, i32* %2, align 4
%5 = getelementptr inbounds i8, i8* %3, i32 %4
%6 = load i8, i8* %5, align 1
%7 = sext i8 %6 to i32
%test = icmp ne i32 %7, 0 ;; check %7 is \0
br i1 %test, label %then, label %else
then:
%8 = load i32, i32* %2, align 4
%9 = add nsw i32 %8, 1
store i32 %9, i32* %2, align 4 ;; ++i
br label %loop_start
else:
%10 = load i32, i32* %2, align 4
ret i32 %10 ; return i
}
; 名前を奪う
define i8* @substr(i8*, i32, i32) {
%4 = getelementptr inbounds i8, i8* %0, i32 %1 ;; offset
%5 = getelementptr inbounds i8, i8* %4, i32 %2 ;; offset + length
store i8 0, i8* %5, align 1 ;; \0を書き込んで文字列が終わったことにする
ret i8* %4
}
define i32 @xorshift32(i32) {
%2 = shl i32 %0, 13
%3 = xor i32 %0, %2
%4 = ashr i32 %3, 17
%5 = xor i32 %3, %4
%6 = shl i32 %5, 5
%7 = xor i32 %5, %6
ret i32 %7
}
define i32 @getRand(i32) {
%2 = call i64 @time(i64* null)
%3 = trunc i64 %2 to i32 ;; toInt32. 32bitを超えた分は無視.
%4 = call i32 @xorshift32(i32 %3)
%5 = urem i32 %4, %0 ;; %0未満の乱数を返す. unsigned intの剰余であることに注意.
ret i32 %5
}
define i32 @main(i32, i8**) {
call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([50 x i8], [50 x i8]* @str1, i32 0, i32 0))
%4 = alloca [256 x i8], align 16 ;; buffer
%5 = getelementptr inbounds [256 x i8], [256 x i8]* %4, i32 0, i32 0
%6 = load %struct.__sFILE*, %struct.__sFILE** @__stdinp, align 8 ;; stdin
call i8* @fgets(i8* %5, i32 256, %struct.__sFILE* %6)
call void @rtrim(i8* %5) ;; fgetsしたときの\nを取り除く
call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([58 x i8], [58 x i8]* @str2, i32 0, i32 0), i8* %5)
%9 = call i32 @strLen(i8* %5) ;; 文字列の長さを取る
%10 = call i32 @getRand(i32 %9) ;; 乱数生成
%11 = call i8* @substr(i8* %5, i32 %10, i32 1) ;; 名前を奪う
call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([106 x i8], [106 x i8]* @str4, i32 0, i32 0), i8* %11, i8* %11, i8* %11)
ret i32 0
}
declare i32 @printf(i8*, ...)
declare i8* @fgets(i8*, i32, %struct.__sFILE*)
declare i64 @time(i64*)
湯婆婆を創造する
いちいちコマンド打つのが面倒なのでMakefileを書いています。
$ make yubaba
llc yubaba.ll
gcc yubaba.s -o yubaba
湯婆婆の創造、響きが良い感じです。
実行例
とりあえず適当にhogeとか入れてみましょう。
$ ./yubaba
契約書だよ。そこに名前を書きな。
hoge
フン。hogeというのかい。贅沢な名だねぇ。
今からお前の名前はeだ。いいかい、eだよ。分かったら返事をするんだ、e!!
無事（？）名前を奪われました。
実行例（湯婆婆は日本語を読めない）
$ ./yubaba
契約書だよ。そこに名前を書きな。
ほげ
フン。ほげというのかい。贅沢な名だねぇ。
今からお前の名前は?だ。いいかい、?だよ。分かったら返事をするんだ、?!!
「ほげ」と名乗ったところ文字化けしてしまいました。これは \E3\81\BB\E3\81\92 の6byteからランダムに1byte切り出してしまったからですね。これを適切に切り出すようにすると、無事湯婆婆に日本語を理解させることができます。（後述）
湯婆婆を解剖する
ここから湯婆婆解説編です。といってもLLVMの詳細には踏み込まず、主にmain関数で何をやっているかだけ解説します。
call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([50 x i8], [50 x i8]* @str1, i32 0, i32 0))
ここはprintfで喋ってるだけです。文字列はcharの配列で表現されるというのはC言語ではおなじみの話ですが、LLVMでは型の情報に配列の長さまで含まれています。先頭にある文字列定数の定義を見ると、文字数によってちゃんと型が違うというのが分かります。
%4 = alloca [256 x i8], align 16 ;; buffer
%5 = getelementptr inbounds [256 x i8], [256 x i8]* %4, i32 0, i32 0
バッファ確保して初期化しています。fgetsの準備です。
%6 = load %struct.__sFILE*, %struct.__sFILE** @__stdinp, align 8 ;; stdin
ここはstdinのFILE構造体へのポインタを取ってきています。この部分はどうしてもうまくいかなかったのでgccの答えをカンニングしたのをそのまま使っています。ファイルディスクリプタ0番をfdopenするとうまくいくという記事を参考に書いたりしましたがうまくいきませんでした16。
call i8* @fgets(i8* %5, i32 256, %struct.__sFILE* %6)
fgets関数を呼んで名前を聞きます。セキュリティ的な理由で17fgetsを使いましたが、getsを使えばrtrim関数を自作してまで\nを消さなくて良かったという気はします。
call void @rtrim(i8* %5) ;; fgetsしたときの\nを取り除く
１つ前の行で説明したとおり、fgetsしたときの入力に混ざってしまっている\nを取り除きます。
一応rtrim関数の中身を説明しておくと、\nにたどり着くまで文字列中身をseekして、\nに出会ったら\0に書き換えることで文字列の終了位置をずらしています1819。
なぜかrtrimの実装にiなる変数の面影がありますが、これは不要なので消せます（筆者が消したつもりになって忘れていた）。興味のある方は、頭の体操がてらiに関係する命令を消す最適化を手でやってみても良いかもしれません（丸投げ）。
その次はprintfしてるだけなので飛ばします。
%9 = call i32 @strLen(i8* %5) ;; 文字列の長さを取る
文字列の長さを計算しています。strLenの中身はrtrimとほぼ同じで、\0にたどり着くまでseekを繰り返し、カウント用の変数をインクリメントしてます。
%8 = load i32, i32* %2, align 4
%9 = add nsw i32 %8, 1
store i32 %9, i32* %2, align 4 ;; ++i
インクリメントしているのはこの３行で、このあたりを見るとロード・ストアの使い方とかが分かりやすいかなと思います。
%10 = call i32 @getRand(i32 %9) ;; 乱数生成
文字列の長さ未満で乱数を生成します。察しの良い方はもう気づいていると思いますが、空文字列を入力するとバグります。（原作再現）
$ ./yubaba
契約書だよ。そこに名前を書きな。
フン。というのかい。贅沢な名だねぇ。
Floating point exception: 8
ちなみにここの乱数生成はちょっと工夫をしていて、rand関数を使っても良かったのですが、あえてxorshift3220を自前で書いています（xorshiftは簡単に実装できるよアピール）。
define i32 @xorshift32(i32) {
%2 = shl i32 %0, 13
%3 = xor i32 %0, %2
%4 = ashr i32 %3, 17
%5 = xor i32 %3, %4
%6 = shl i32 %5, 5
%7 = xor i32 %5, %6
ret i32 %7
}
見ての通りたったの７命令（機械語に変換されても多分７命令）で動きます21！
%11 = call i8* @substr(i8* %5, i32 %10, i32 1) ;; 名前を奪う
名前を奪います。実装としてはstrLenの応用で、第一引数で配列の番地を受け取り、これを*str、第二引数をiとすると、第３引数をjとするとstr + i番地を文字列の先頭の位置として返し、そこからさらにj番地先、つまりstr + i + j番地を\0で埋めることで任意の位置から任意の文字数22を切り出す処理になっています。
最後は奪った名前を表示してreturn 0;です。
湯婆婆を日本語対応させる
さて、ここからは湯婆婆を日本語対応させたいと思います。
先ほど説明したようにこのプログラムは1byte=1文字の前提で書かれているため、マルチバイト文字に対応していません。そこで、湯婆婆をマルチバイト文字に対応させてみたいと思います。23
改めて振り返ってみると、湯婆婆が日本語を理解できないのはマルチバイト文字の扱いができていないからでした。ということは、文字列を扱う部分、つまりstrLen関数とsubstr関数をマルチバイト文字に対応させれば良い24というわけです。
;; 文字列の長さを返す（マルチバイト対応版）
define i32 @mbStrLen(i8*) {
start:
%1 = alloca i8*, align 8 ;; pointer
%count = alloca i32, align 4
store i8* %0, i8** %1, align 8
store i32 0, i32* %count, align 4 ;; count = 0
br label %loop_start
loop_start:
%2 = load i8*, i8** %1, align 8 ;; str
%3 = getelementptr inbounds i8, i8* %2, i32 0
%4 = load i8, i8* %3, align 1
%test = icmp ne i8 %4, 0 ;; check %4 is \0
br i1 %test, label %then, label %else
then:
%5 = load i8*, i8** %1, align 8
%6 = getelementptr inbounds i8, i8* %5, i32 1
store i8* %6, i8** %1, align 8 ;; ++str
%7 = and i8 %4, 192 ;; and %4 0xc0
%test2 = icmp ne i8 %7, 128 ;; check 0x80
br i1 %test2, label %then2, label %loop_start
then2:
%8 = load i32, i32* %count, align 4
%9 = add nsw i32 %8, 1
store i32 %9, i32* %count, align 4 ;; ++count
br label %loop_start
else:
%10 = load i32, i32* %count, align 4
ret i32 %10 ; return count
}
;; 1が立っている最上位ビットの位置を得る
define i32 @getMsbPos(i8) {
%i = alloca i32, align 4
%v = alloca i8, align 4
store i32 0, i32* %i, align 4 ;; int i = 0;
store i8 %0, i8* %v, align 4 ;; int v = arg1;
br label %loop
loop:
%vcur = load i8, i8* %v, align 4 ;; current v
%test = icmp ne i8 %vcur, 0
br i1 %test, label %then, label %else
then:
%2 = load i32, i32* %i, align 4
%3 = add nsw i32 %2, 1
store i32 %3, i32* %i, align 4 ;; ++i
%4 = lshr i8 %vcur, 1
store i8 %4, i8* %v, align 4 ;; %vcur >>= 1
br label %loop
else:
%5 = load i32, i32* %i, align 4 ;; i
ret i32 %5
}
;; 名前を奪う（マルチバイト対応版, 切り出す文字数は１文字に固定）
define i8* @mbSubstr1(i8*, i32) {
start:
%2 = alloca i8*, align 8 ;; pointer
%count = alloca i32, align 4
store i8* %0, i8** %2, align 8
store i32 0, i32* %count, align 4 ;; count = 0
br label %loop_start
loop_start:
%3 = load i8*, i8** %2, align 8 ;; str
%4 = getelementptr inbounds i8, i8* %3, i32 0
%5 = load i8, i8* %4, align 1
%test = icmp ne i8 %5, 0 ;; check %5 is \0
br i1 %test, label %then, label %else
then:
%6 = and i8 %5, 192 ;; and %5 0xc0
%test2 = icmp ne i8 %6, 128 ;; check 0x80
br i1 %test2, label %then2, label %else2
then2:
;; 1byte文字かマルチバイト文字の先頭
%7 = load i32, i32* %count, align 4 ;; count
%test3 = icmp eq i32 %1, %7 ;; check count
br i1 %test3, label %then3, label %else3
then3:
;; strからn文字返す
%len = alloca i32*, align 4
%not = xor i8 %5, 255 ;; ビット反転
%pos = call i32 @getMsbPos(i8 %not) ;; 最上位の0の場所を取る（この位置を取ることで何byte文字か分かる）
%test4 = icmp eq i32 %pos, 8
br i1 %test4, label %then4, label %else4
then4:
;; 1byte文字のケース
%end_1 = getelementptr inbounds i8, i8* %3, i32 1
store i8 0, i8* %end_1, align 1 ;; \0を書き込んで文字列が終わったことにする
ret i8* %3 ;; return str
else4:
;; マルチバイト文字のケース
%r = sub i32 8, %pos ;; (8 - %pos) byte先を\0で埋めればよい
%end = getelementptr inbounds i8, i8* %3, i32 %r
store i8 0, i8* %end, align 1 ;; \0を書き込んで文字列が終わったことにする
ret i8* %3 ;; return str
else3:
;; ++countして次へ
%8 = add nsw i32 %7, 1
store i32 %8, i32* %count, align 4 ;; ++count
br label %else2
else2:
%9 = load i8*, i8** %2, align 8
%10 = getelementptr inbounds i8, i8* %9, i32 1
store i8* %10, i8** %2, align 8 ;; ++str
br label %loop_start
else:
%11 = load i8*, i8** %2, align 8 ;; str
ret i8* %11 ; return str
}
呼び出し部分はこんな感じで差し替えればOKです25。
call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([58 x i8], [58 x i8]* @str2, i32 0, i32 0), i8* %5)
- %9 = call i32 @strLen(i8* %5) ;; 文字列の長さを取る
+ %9 = call i32 @mbStrLen(i8* %5) ;; 文字列の長さを取る
%10 = call i32 @getRand(i32 %9) ;; 乱数生成
- %11 = call i8* @substr(i8* %5, i32 %10, i32 1) ;; 名前を奪う
+ %11 = call i8* @mbSubstr1(i8* %5, i32 %10) ;; 名前を奪う
call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([106 x i8], [106 x i8]* @str4, i32 0, i32 0), i8* %11, i8* %11, i8* %11)
マルチバイト文字に対応させるだけで結構な長さになってしまいました。
全部解説するのも大変なので、要点だけ解説していきます。できる限り丁寧にコメントは入れたつもりなので、ここまでたどり着いたみなさんなら自力で解読できると思います（ぉ
mbStrLen
基本的なロジックはsubstrと同じです。\0まで1byteずつ文字列をseekしていき、ループした数を数えて返しています。このとき、参考文献で紹介されている実装のように、マルチバイト文字の2byte目以降だと分かるbyteはスキップするのがミソです。
コードで言うとこの部分です。
%7 = and i8 %4, 192 ;; and %4 0xc0
%test2 = icmp ne i8 %7, 128 ;; check 0x80
br i1 %test2, label %then2, label %loop_start
mbSubstr1
substrのマルチバイト対応版（の実装を少し横着したやつ）です。
以下は説明のため 第１引数、第二引数をそれぞれ arg1, arg2 と書きます。
基本的な考え方はmbStrLenと同じで、マルチバイト文字の2byte目以降に相当するものはスキップしながらseekしていき、arg1文字目にたどり着いたら、そのアドレスを文字列の開始位置として返します。
returnする前に１文字分だけseekして、次のマルチバイト文字26の先頭を\0で埋めます。
ここで何byte文字かを判定するために、最上位ビットから数えて最初に0が出現する位置を利用していて、この判定を行うためのロジックをgetMsbPosに切り出しています。
MSB(most significant bit)を求めるロジックなので、呼び出す時はビット反転してから渡しています。
ちなみにここは実装し始めたときはこれ一発で全部いけると思っていたのですが、1byte文字の場合だけは結局別で判定しないといけないことに気づいたので最初から全部条件分岐で書いておけば良かったという気はします27。
ちなみに、リファレンスをよく見てみるとSwitch命令という命令があり、単純なSwitch文ならこれ１つで書けます28。
getMsbPos
上で説明した通り、最上位にある1の位置を返す関数です。1bitずつ右シフトしていき、0になるまでの回数を計算して返しています。
そのため、1がないとき（＝0を与えたとき）0を返し、n番目（＝$2^n$の位）のビットが立っているときはn+1を返すというちょっと変な実装になっています29。
8を足したあと mod 9 を取ってから返した方が自然な実装かもしれません30。
実行例
$ ./yubaba
契約書だよ。そこに名前を書きな。
湯婆婆
フン。湯婆婆というのかい。贅沢な名だねぇ。
今からお前の名前は婆だ。いいかい、婆だよ。分かったら返事をするんだ、婆!!
自己言及湯婆婆。
（おまけ）湯婆婆の高速化（LLVM IR編）
最初の方で説明した通り、optコマンドで最適化したLLVMを生成してみます。
rtrimの無駄な実装が最適化されるかどうかなどを見たいので、日本語対応前のもので比較しています。
$ opt -S -o yubaba2.ll yubaba.ll
$ git diff -u yubaba.ll yubaba2.ll
さて、どんな違いがあるか見てみましょう！
--- yubaba.ll
+++ yubaba2.ll
@@ -1,33 +1,39 @@
+; ModuleID = 'yubaba.ll'
+source_filename = "yubaba.ll"
+
%struct.__sFILE = type { i8*, i32, i32, i16, i16, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, %struct.__sFILEX*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 }
%struct.__sFILEX = type opaque
%struct.__sbuf = type { i8*, i32 }
-@str1 = private unnamed_addr constant [50 x i8] c"契約書だよ。そこに名前を書きな。\0a\00", align 1
-@str2 = private unnamed_addr constant [58 x i8] c"フン。%sというのかい。贅沢な名だねぇ。\0a\00", align 1
-@str4 = private unnamed_addr constant [106 x i8] c"今からお前の名前は%sだ。いいかい、%sだよ。分かったら返事をするんだ、%s!!\0a\00", align 1
+@str1 = private unnamed_addr constant [50 x i8] c"\E5\A5\91\E7\B4\84\E6\9B\B8\E3\81\A0\E3\82\88\E3\80\82\E3\81\9D\E3\81\93\E3\81\AB\E5\90\8D\E5\89\8D\E3\82\92\E6\9B\B8\E3\81\8D\E3\81\AA\E3\80\82\0A\00", align 1
+@str2 = private unnamed_addr constant [58 x i8] c"\E3\83\95\E3\83\B3\E3\80\82%s\E3\81\A8\E3\81\84\E3\81\86\E3\81\AE\E3\81\8B\E3\81\84\E3\80\82\E8\B4\85\E6\B2\A2\E3\81\AA\E5\90\8D\E3\81\A0\E3\81\AD\E3\81\87\E3\80\82\0A\00", align 1
+@str4 = private unnamed_addr constant [106 x i8] c"\E4\BB\8A\E3\81\8B\E3\82\89\E3\81\8A\E5\89\8D\E3\81\AE\E5\90\8D\E5\89\8D\E3\81\AF%s\E3\81\A0\E3\80\82\E3\81\84\E3\81\84\E3\81\8B\E3\81\84\E3\80\81%s\E3\81\A0\E3\82\88\E3\80\82\E5\88\86\E3\81\8B\E3\81\A3\E3\81\9F\E3\82\89\E8\BF\94\E4\BA\8B\E3\82\92\E3\81\99\E3\82\8B\E3\82\93\E3\81\A0\E3\80\81%s!!\0A\00", align 1
@__stdinp = external global %struct.__sFILE*, align 8
-define void @rtrim(i8*) {
+define void @rtrim(i8* %0) {
start:
- %1 = alloca i8*, align 8 ;; pointer
- %2 = alloca i32, align 4 ;; int i
+ %1 = alloca i8*, align 8
+ %2 = alloca i32, align 4
store i8* %0, i8** %1, align 8
- store i32 0, i32* %2, align 4 ;; i = 0
+ store i32 0, i32* %2, align 4
br label %loop_start
-loop_start:
- %3 = load i8*, i8** %1, align 8 ;; str
+
+loop_start: ; preds = %then, %start
+ %3 = load i8*, i8** %1, align 8
%4 = load i32, i32* %2, align 4
%5 = getelementptr inbounds i8, i8* %3, i32 %4
%6 = load i8, i8* %5, align 1
%7 = sext i8 %6 to i32
- %test = icmp ne i32 %7, 10 ;; 改行かどうか調べる
+ %test = icmp ne i32 %7, 10
br i1 %test, label %then, label %else
-then:
+
+then: ; preds = %loop_start
%8 = load i32, i32* %2, align 4
%9 = add nsw i32 %8, 1
- store i32 %9, i32* %2, align 4 ;; ++i
+ store i32 %9, i32* %2, align 4
br label %loop_start
-else:
+
+else: ; preds = %loop_start
%10 = load i8*, i8** %1, align 8
%11 = load i32, i32* %2, align 4
%12 = getelementptr inbounds i8, i8* %10, i32 %11
@@ -35,40 +41,42 @@
ret void
}
-define i32 @strLen(i8*) {
+define i32 @strLen(i8* %0) {
start:
- %1 = alloca i8*, align 8 ;; pointer
- %2 = alloca i32, align 4 ;; int i
+ %1 = alloca i8*, align 8
+ %2 = alloca i32, align 4
store i8* %0, i8** %1, align 8
- store i32 0, i32* %2, align 4 ;; i = 0
+ store i32 0, i32* %2, align 4
br label %loop_start
-loop_start:
- %3 = load i8*, i8** %1, align 8 ;; str
+
+loop_start: ; preds = %then, %start
+ %3 = load i8*, i8** %1, align 8
%4 = load i32, i32* %2, align 4
%5 = getelementptr inbounds i8, i8* %3, i32 %4
%6 = load i8, i8* %5, align 1
%7 = sext i8 %6 to i32
- %test = icmp ne i32 %7, 0 ;; check %7 is \0
+ %test = icmp ne i32 %7, 0
br i1 %test, label %then, label %else
-then:
+
+then: ; preds = %loop_start
%8 = load i32, i32* %2, align 4
%9 = add nsw i32 %8, 1
- store i32 %9, i32* %2, align 4 ;; ++i
+ store i32 %9, i32* %2, align 4
br label %loop_start
-else:
+
+else: ; preds = %loop_start
%10 = load i32, i32* %2, align 4
- ret i32 %10 ; return i
+ ret i32 %10
}
-; 名前を奪う
-define i8* @substr(i8*, i32, i32) {
- %4 = getelementptr inbounds i8, i8* %0, i32 %1 ;; offset
- %5 = getelementptr inbounds i8, i8* %4, i32 %2 ;; offset + length
- store i8 0, i8* %5, align 1 ;; \0を書き込んで文字列が終わったことにする
+define i8* @substr(i8* %0, i32 %1, i32 %2) {
+ %4 = getelementptr inbounds i8, i8* %0, i32 %1
+ %5 = getelementptr inbounds i8, i8* %4, i32 %2
+ store i8 0, i8* %5, align 1
ret i8* %4
}
-define i32 @xorshift32(i32) {
+define i32 @xorshift32(i32 %0) {
%2 = shl i32 %0, 13
%3 = xor i32 %0, %2
%4 = ashr i32 %3, 17
@@ -78,29 +86,31 @@
ret i32 %7
}
-define i32 @getRand(i32) {
+define i32 @getRand(i32 %0) {
%2 = call i64 @time(i64* null)
- %3 = trunc i64 %2 to i32 ;; toInt32. 32bitを超えた分は無視.
+ %3 = trunc i64 %2 to i32
%4 = call i32 @xorshift32(i32 %3)
- %5 = urem i32 %4, %0 ;; %0未満の乱数を返す. unsigned intの剰余であることに注意.
+ %5 = urem i32 %4, %0
ret i32 %5
}
-define i32 @main(i32, i8**) {
- call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([50 x i8], [50 x i8]* @str1, i32 0, i32 0))
- %4 = alloca [256 x i8], align 16 ;; buffer
+define i32 @main(i32 %0, i8** %1) {
+ %3 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([50 x i8], [50 x i8]* @str1, i32 0, i32 0))
+ %4 = alloca [256 x i8], align 16
%5 = getelementptr inbounds [256 x i8], [256 x i8]* %4, i32 0, i32 0
- %6 = load %struct.__sFILE*, %struct.__sFILE** @__stdinp, align 8 ;; stdin
- call i8* @fgets(i8* %5, i32 256, %struct.__sFILE* %6)
- call void @rtrim(i8* %5) ;; fgetsしたときの\nを取り除く
- call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([58 x i8], [58 x i8]* @str2, i32 0, i32 0), i8* %5)
- %9 = call i32 @strLen(i8* %5) ;; 文字列の長さを取る
- %10 = call i32 @getRand(i32 %9) ;; 乱数生成
- %11 = call i8* @substr(i8* %5, i32 %10, i32 1) ;; 名前を奪う
- call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([106 x i8], [106 x i8]* @str4, i32 0, i32 0), i8* %11, i8* %11, i8* %11)
+ %6 = load %struct.__sFILE*, %struct.__sFILE** @__stdinp, align 8
+ %7 = call i8* @fgets(i8* %5, i32 256, %struct.__sFILE* %6)
+ call void @rtrim(i8* %5)
+ %8 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([58 x i8], [58 x i8]* @str2, i32 0, i32 0), i8* %5)
+ %9 = call i32 @strLen(i8* %5)
+ %10 = call i32 @getRand(i32 %9)
+ %11 = call i8* @substr(i8* %5, i32 %10, i32 1)
+ %12 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([106 x i8], [106 x i8]* @str4, i32 0, i32 0), i8* %11, i8* %11, i8* %11)
ret i32 0
}
declare i32 @printf(i8*, ...)
+
declare i8* @fgets(i8*, i32, %struct.__sFILE*)
+
declare i64 @time(i64*)
差分自体は結構出てますがコードフォーマットなどが主で、あまりというかほとんど最適化してる感はないですね……。
rtrimの無駄な実装を最適化してくれるかと思っていましたが、そうはいかなかったようです。
ちなみにmain関数のret命令の直後にもう１つret命令を付け足してみたところこうなりました。
ret i32 0
+
+13: ; No predecessors!
ret i32 1
}
warningっぽいものは出るものの到達不可能な命令を消してくれるわけではないようです。
このあたりはコンパイル時に行うということでしょうか31。
（おまけ）湯婆婆の高速化（llc編）
次はコンパイル時の最適化を比較してみます。以下は日本語対応版の湯婆婆で比較してみた結果です。
-O0と-O1
--- yubaba_O0.s
+++ yubaba_O1.s
@@ -7,19 +7,16 @@
## %bb.0: ## %start
movq %rdi, -8(%rsp)
movl $0, -12(%rsp)
+ .p2align 4, 0x90
LBB0_1: ## %loop_start
## =>This Inner Loop Header: Depth=1
movq -8(%rsp), %rax
- movl -12(%rsp), %ecx
- movslq %ecx, %rdx
- movsbl (%rax,%rdx), %ecx
- cmpl $10, %ecx
+ movslq -12(%rsp), %rcx
+ cmpb $10, (%rax,%rcx)
je LBB0_3
## %bb.2: ## %then
## in Loop: Header=BB0_1 Depth=1
- movl -12(%rsp), %eax
- addl $1, %eax
- movl %eax, -12(%rsp)
+ incl -12(%rsp)
jmp LBB0_1
LBB0_3: ## %else
movq -8(%rsp), %rax
@@ -35,19 +32,16 @@
## %bb.0: ## %start
movq %rdi, -8(%rsp)
movl $0, -12(%rsp)
+ .p2align 4, 0x90
LBB1_1: ## %loop_start
## =>This Inner Loop Header: Depth=1
movq -8(%rsp), %rax
- movl -12(%rsp), %ecx
- movslq %ecx, %rdx
- movsbl (%rax,%rdx), %ecx
- cmpl $0, %ecx
+ movslq -12(%rsp), %rcx
+ cmpb $0, (%rax,%rcx)
je LBB1_3
## %bb.2: ## %then
## in Loop: Header=BB1_1 Depth=1
- movl -12(%rsp), %eax
- addl $1, %eax
- movl %eax, -12(%rsp)
+ incl -12(%rsp)
jmp LBB1_1
LBB1_3: ## %else
movl -12(%rsp), %eax
@@ -61,27 +55,22 @@
## %bb.0: ## %start
movq %rdi, -8(%rsp)
movl $0, -12(%rsp)
+ .p2align 4, 0x90
LBB2_1: ## %loop_start
## =>This Inner Loop Header: Depth=1
movq -8(%rsp), %rax
- movb (%rax), %cl
- cmpb $0, %cl
- movb %cl, -13(%rsp) ## 1-byte Spill
+ movzbl (%rax), %eax
+ testb %al, %al
je LBB2_4
## %bb.2: ## %then
## in Loop: Header=BB2_1 Depth=1
- movq -8(%rsp), %rax
- addq $1, %rax
- movq %rax, -8(%rsp)
- movb -13(%rsp), %cl ## 1-byte Reload
- andb $-64, %cl
- cmpb $-128, %cl
+ incq -8(%rsp)
+ andb $-64, %al
+ cmpb $-128, %al
je LBB2_1
## %bb.3: ## %then2
## in Loop: Header=BB2_1 Depth=1
- movl -12(%rsp), %eax
- addl $1, %eax
- movl %eax, -12(%rsp)
+ incl -12(%rsp)
jmp LBB2_1
LBB2_4: ## %else
movl -12(%rsp), %eax
@@ -93,23 +82,19 @@
_getMsbPos: ## @getMsbPos
.cfi_startproc
## %bb.0:
- ## kill: def $dil killed $dil killed $edi
movl $0, -4(%rsp)
movb %dil, -8(%rsp)
+ .p2align 4, 0x90
LBB3_1: ## %loop
## =>This Inner Loop Header: Depth=1
- movb -8(%rsp), %al
- cmpb $0, %al
- movb %al, -9(%rsp) ## 1-byte Spill
+ movzbl -8(%rsp), %eax
+ testb %al, %al
je LBB3_3
## %bb.2: ## %then
## in Loop: Header=BB3_1 Depth=1
- movl -4(%rsp), %eax
- addl $1, %eax
- movl %eax, -4(%rsp)
- movb -9(%rsp), %cl ## 1-byte Reload
- shrb $1, %cl
- movb %cl, -8(%rsp)
+ incl -4(%rsp)
+ shrb %al
+ movb %al, -8(%rsp)
jmp LBB3_1
LBB3_3: ## %else
movl -4(%rsp), %eax
@@ -126,70 +111,63 @@
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
- subq $48, %rsp
- movq %rdi, -8(%rbp)
+ pushq %rbx
+ subq $24, %rsp
+ .cfi_offset %rbx, -24
+ movq %rdi, -24(%rbp)
movl $0, -12(%rbp)
- movl %esi, -16(%rbp) ## 4-byte Spill
+ jmp LBB4_1
+ .p2align 4, 0x90
+LBB4_10: ## %else2
+ ## in Loop: Header=BB4_1 Depth=1
+ incq -24(%rbp)
LBB4_1: ## %loop_start
## =>This Inner Loop Header: Depth=1
- movq -8(%rbp), %rax
- movb (%rax), %cl
- cmpb $0, %cl
- movq %rax, -24(%rbp) ## 8-byte Spill
- movb %cl, -25(%rbp) ## 1-byte Spill
- je LBB4_9
+ movq -24(%rbp), %rbx
+ movzbl (%rbx), %eax
+ testb %al, %al
+ je LBB4_11
## %bb.2: ## %then
## in Loop: Header=BB4_1 Depth=1
- movb -25(%rbp), %al ## 1-byte Reload
- andb $-64, %al
- cmpb $-128, %al
- je LBB4_8
+ movl %eax, %ecx
+ andb $-64, %cl
+ cmpb $-128, %cl
+ je LBB4_10
## %bb.3: ## %then2
## in Loop: Header=BB4_1 Depth=1
- movl -12(%rbp), %eax
- movl -16(%rbp), %ecx ## 4-byte Reload
- cmpl %eax, %ecx
- movl %eax, -32(%rbp) ## 4-byte Spill
- jne LBB4_7
-## %bb.4: ## %then3
- movb -25(%rbp), %al ## 1-byte Reload
- xorb $-1, %al
+ movl -12(%rbp), %ecx
+ cmpl %ecx, %esi
+ je LBB4_4
+## %bb.9: ## %else3
+ ## in Loop: Header=BB4_1 Depth=1
+ incl %ecx
+ movl %ecx, -12(%rbp)
+ jmp LBB4_10
+LBB4_11: ## %else
+ movq -24(%rbp), %rax
+ jmp LBB4_7
+LBB4_4: ## %then3
+ movq %rsp, %rcx
+ addq $-16, %rcx
+ movq %rcx, %rsp
+ notb %al
movzbl %al, %edi
callq _getMsbPos
cmpl $8, %eax
- movl %eax, -36(%rbp) ## 4-byte Spill
- jne LBB4_6
+ jne LBB4_8
## %bb.5: ## %then4
- movq -24(%rbp), %rax ## 8-byte Reload
- movb $0, 1(%rax)
- movq %rbp, %rsp
- popq %rbp
- retq
-LBB4_6: ## %else4
- movl $8, %eax
- movl -36(%rbp), %ecx ## 4-byte Reload
- subl %ecx, %eax
- movslq %eax, %rdx
- movq -24(%rbp), %rsi ## 8-byte Reload
- movb $0, (%rsi,%rdx)
- movq %rsi, %rax
- movq %rbp, %rsp
- popq %rbp
- retq
-LBB4_7: ## %else3
- ## in Loop: Header=BB4_1 Depth=1
- movl -32(%rbp), %eax ## 4-byte Reload
- addl $1, %eax
- movl %eax, -12(%rbp)
-LBB4_8: ## %else2
- ## in Loop: Header=BB4_1 Depth=1
- movq -8(%rbp), %rax
- addq $1, %rax
- movq %rax, -8(%rbp)
- jmp LBB4_1
-LBB4_9: ## %else
- movq -8(%rbp), %rax
- movq %rbp, %rsp
+ movb $0, 1(%rbx)
+ jmp LBB4_6
+LBB4_8: ## %else4
+ movl $8, %ecx
+ subl %eax, %ecx
+ movslq %ecx, %rax
+ movb $0, (%rbx,%rax)
+LBB4_6: ## %then4
+ movq %rbx, %rax
+LBB4_7: ## %then4
+ leaq -8(%rbp), %rsp
+ popq %rbx
popq %rbp
retq
.cfi_endproc
@@ -200,10 +178,9 @@
.cfi_startproc
## %bb.0:
movslq %esi, %rax
- addq %rax, %rdi
- movslq %edx, %rax
- movb $0, (%rdi,%rax)
- movq %rdi, %rax
+ addq %rdi, %rax
+ movslq %edx, %rcx
+ movb $0, (%rcx,%rax)
retq
.cfi_endproc
## -- End function
@@ -214,14 +191,13 @@
## %bb.0:
movl %edi, %eax
shll $13, %eax
- xorl %eax, %edi
- movl %edi, %eax
- sarl $17, %eax
- xorl %eax, %edi
- movl %edi, %eax
+ xorl %edi, %eax
+ movl %eax, %ecx
+ sarl $17, %ecx
+ xorl %eax, %ecx
+ movl %ecx, %eax
shll $5, %eax
- xorl %eax, %edi
- movl %edi, %eax
+ xorl %ecx, %eax
retq
.cfi_endproc
## -- End function
@@ -230,21 +206,18 @@
_getRand: ## @getRand
.cfi_startproc
## %bb.0:
- pushq %rax
+ pushq %rbx
.cfi_def_cfa_offset 16
- xorl %eax, %eax
- movl %eax, %ecx
- movl %edi, 4(%rsp) ## 4-byte Spill
- movq %rcx, %rdi
+ .cfi_offset %rbx, -16
+ movl %edi, %ebx
+ xorl %edi, %edi
callq _time
- ## kill: def $eax killed $eax killed $rax
movl %eax, %edi
callq _xorshift32
xorl %edx, %edx
- movl 4(%rsp), %esi
-107, +80 で27行減りました。32
レジスタ周りや命令列の最適化を行ってくれてそうな雰囲気があります。
目で見ても命令の数が減ってそうな感じがしますね。
-O1と-O2
比較してみましたが違いはありませんでした。このレベルだとO1とO2の差は出ないようです。
-O2と-O3
--- yubaba_O2.s
+++ yubaba_O3.s
@@ -7,17 +7,18 @@
## %bb.0: ## %start
movq %rdi, -8(%rsp)
movl $0, -12(%rsp)
- .p2align 4, 0x90
-LBB0_1: ## %loop_start
- ## =>This Inner Loop Header: Depth=1
movq -8(%rsp), %rax
movslq -12(%rsp), %rcx
cmpb $10, (%rax,%rcx)
je LBB0_3
-## %bb.2: ## %then
- ## in Loop: Header=BB0_1 Depth=1
+ .p2align 4, 0x90
+LBB0_2: ## %then
+ ## =>This Inner Loop Header: Depth=1
incl -12(%rsp)
- jmp LBB0_1
+ movq -8(%rsp), %rax
+ movslq -12(%rsp), %rcx
+ cmpb $10, (%rax,%rcx)
+ jne LBB0_2
LBB0_3: ## %else
movq -8(%rsp), %rax
movslq -12(%rsp), %rcx
@@ -32,17 +33,18 @@
## %bb.0: ## %start
movq %rdi, -8(%rsp)
movl $0, -12(%rsp)
- .p2align 4, 0x90
-LBB1_1: ## %loop_start
- ## =>This Inner Loop Header: Depth=1
movq -8(%rsp), %rax
movslq -12(%rsp), %rcx
cmpb $0, (%rax,%rcx)
je LBB1_3
-## %bb.2: ## %then
- ## in Loop: Header=BB1_1 Depth=1
+ .p2align 4, 0x90
+LBB1_2: ## %then
+ ## =>This Inner Loop Header: Depth=1
incl -12(%rsp)
- jmp LBB1_1
+ movq -8(%rsp), %rax
+ movslq -12(%rsp), %rcx
+ cmpb $0, (%rax,%rcx)
+ jne LBB1_2
LBB1_3: ## %else
movl -12(%rsp), %eax
retq
@@ -84,18 +86,18 @@
## %bb.0:
movl $0, -4(%rsp)
movb %dil, -8(%rsp)
- .p2align 4, 0x90
-LBB3_1: ## %loop
- ## =>This Inner Loop Header: Depth=1
- movzbl -8(%rsp), %eax
+ movb -8(%rsp), %al
testb %al, %al
je LBB3_3
-## %bb.2: ## %then
- ## in Loop: Header=BB3_1 Depth=1
+ .p2align 4, 0x90
+LBB3_2: ## %then
+ ## =>This Inner Loop Header: Depth=1
incl -4(%rsp)
shrb %al
movb %al, -8(%rsp)
- jmp LBB3_1
+ movzbl -8(%rsp), %eax
+ testb %al, %al
+ jne LBB3_2
LBB3_3: ## %else
movl -4(%rsp), %eax
retq
@@ -145,7 +147,10 @@
jmp LBB4_10
LBB4_11: ## %else
movq -24(%rbp), %rax
- jmp LBB4_7
+ leaq -8(%rbp), %rsp
+ popq %rbx
+ popq %rbp
+ retq
LBB4_4: ## %then3
movq %rsp, %rcx
addq $-16, %rcx
@@ -165,7 +170,6 @@
movb $0, (%rbx,%rax)
LBB4_6: ## %then4
movq %rbx, %rax
-LBB4_7: ## %then4
leaq -8(%rbp), %rsp
popq %rbx
popq %rbp
ちゃんと最適化してそうな雰囲気はありますが、-O3の方がむしろ行数は増えています。
jmp命令の周りを最適化してそうだということは何となく分かりますが、具体的にどういった最適化がされているのか筆者もよく分かっていません。こちらの方が命令数は減るんでしょうか……。
まとめ
湯婆婆をできる限り人力でLLVM IRを書くことで実装してみました。
まずシンプルに湯婆婆の実装を行い、その後マルチバイト文字への対応を実装しました。
さらに、実装した湯婆婆を用いてLLVMの提供する最適化機能を試してみました。
所詮は湯婆婆と高を括っていましたが、LLVMで実装すると思ったより激しい内容になるという知見を得られました 
高級言語すごい（小学生並みの感想）
参考文献
論文などで言うReferenceの意味だと上４つくらいだと思います。
- Javaで湯婆婆を実装してみる
- こわくないLLVM入門！
- 【マルチバイト文字】バイト数判定のための一覧表
- シェルスクリプトで乱数生成を実装する(Xorshift32)
- Installing LLVM/Clang on OS X
- LLVMで言語をつくる
- LLVM APIを使ってみよう！ 〜 Brainf**kコンパイラをIRBuilderで書き直してみた 〜
- LLVM bitcode基礎知識
-
今年は湯婆婆アドベントカレンダーもあるのでそちらもどうぞ https://qiita.com/advent-calendar/2020/yubaba ↩
-
さすがに全部説明すると大変なので、情報系の学部生、もしくはコンパイラまわりの技術をかじったことがある方くらいの読者を想定しています ↩
-
main関数から実行が始まるところはC言語と同じです ↩
-
型の概念などがあるので言語仕様で見ると結構別物ですが、手で書いているときの感覚は正直アセンブラと大差ないです ↩
-
おそらくアセンブラを書いた（もしくは作った）ことのある人にしか何がすごいのか伝わらなさそうですが ↩
-
こうすることで最適化がしやすくなるらしいです ↩
-
なぜそんなことをするのかといきなり機械語に変換するのは大変だからです。だいたいアセンブラと高級言語の間のような言語になります（まさにLLVM IRのような） ↩
-
gollvmというコンパイラ実装の一つがあるのですが、公式のページでは "a somewhat less mature gollvm, which uses the LLVM infrastructure" と書かれており悲しい気持ちになりました ↩
-
ライブラリのことだと思ってもらえれば大丈夫だと思います。詳しい書き方は参考文献にありますが、SQLのクエリビルダのような感じで書けるようです。APIを利用できない言語で使う場合、この記事でやっているようにLLVM IRをテキストファイルに書き出してからllcでコンパイルという流れになるようです。 ↩
-
この記事では主にllcコマンドのことを指しています ↩
-
LLVM BCなどあるので、正確な表現ではないです。この記事ではLLVMがプログラム変換の対象とする言語（表現）のことをLLVM IRと呼びます。（なので中間表現と呼んだ方が本当は正しい） ↩
-
実態はアセンブラ？ 自分が実行可能ファイルを出力する方法を知らないだけな気もしますが ↩
-
Lexer: 字句解析（器）。Parser: 構文解析（器）。字句解析で切り出したトークンの列を抽象構文木(Abstract Syntax Tree: AST)に変換する処理のこと。
一般にコンパイラの処理は字句解析 -> 構文解析 -> 中間言語の生成 -> 最適化 -> 機械語（厳密には target language）の生成の順を辿ります ↩ -
ClangはそもそもバックエンドがLLVMなので、Clangの方が良いという説はあります。gccを選んだ理由は何となくです（筆者が使い慣れているから） ↩
-
間違ってstdoutの方をopenしていたという説はあります ↩
-
あとgetsなどは廃止されていた ↩
-
改行コードに由来する話なのでWindowsで動かすとこのコードではうまくいかないかもしれません。 ↩
-
\0が文字列の終端を意味するというのはC言語のお約束ですが、これを利用（悪用？）しています ↩ -
xoroshiro128+とかでも良かったんですが、shift rotate命令らしきものが見当たらなかったのでLLVMの命令をそのまま使えるxorshiftにしました。ちなみにxoroshiro128+はChrome, Firefox, Safariなどの乱数生成エンジンに使われているらしいです ↩
-
前状態の値を引数として受け取っているのでちょっとインチキですが。今回は１回しか乱数を使わないからこれでも成り立つだけで、本来は前状態を利用して次の乱数を生成するように書く必要があります。 ↩
-
本当はbyte ↩
-
なので湯婆婆の日本語対応というのは少し間違いで、任意のutf8文字列を読めるようになります。 ↩
-
タネ明かしをすると、これを見越してこの２つは関数に切り出していました ↩
-
名前を見て察しがつく通り、実装が面倒になったのでsubstrは１文字だけ切り出せる仕様に変えています。もう一つループを追加すれば、substrと同じように任意の文字数切り出せるようにできるはずです。単純に先頭から何バイトと言えないので、そこで難易度が上がっています。 ↩
-
1byte文字かもしれないですがどちらでも同じです ↩
-
LLVMというかアセンブラ風味の言語で条件分岐を書きまくると何をやってるのか分からなくなるので、それを嫌がったためです ↩
-
今回のケースは単純なSwitch文ではないのでこれを使うのは難しそうですが。うまくSwitch文を使う形に落とし込めると、Switch命令でもいけそうな気はします ↩
-
動いていれば十分なので今回はこの実装にしました ↩
-
1の場所が0 indexで返り、1がないときは8（オーバーフローとみなす）で返ります ↩
-
だとしたらoptの行う最適化とは一体……。もっと複雑なコードだとちゃんと最適化した結果が出てくるのでしょうか。 ↩
-
27命令とは限らないので ↩