導入

とりあえず使い方は分かったのだが、次の段階として何をすべきかを考えると

LLVM内部での処理の流れを追う
LLVMのデータ構造を知る
LLVMのファイル構成を知る
LLVM IRを知る

ということが思いつく。
たぶん下から順にやっていくのがよさそうだ(なら逆順に書けよとか言われそう)。というか大人しく本とか買って勉強した方がいいのでは？

ちょっと勉強したくらいでLLVM IRをすべて理解できるとは思えないので、入門編ということにした。どこまで記事が増えるかわからないがまあいいでしょう。

LLVM IRの仕様

なんかいろいろドキュメントがあるらしいのでここではそれをざっと紹介する。
ドキュメントだけでも量が膨大なので本当にしんどい。またどこかで整理して掲載すると思う。

Reference(LLVM IR)
LLVM IRに関するリファレンス一覧
Language Reference Manual
LLVM IRの言語仕様に関するマニュアルドラゴンブックが読める人ならこれ読むだけで十分だと思う
GEP Instruction

とりあえずこんなもんで

https://postd.cc/llvm-for-grad-students/

LLVM IRの文法

超基本的な部分だけ押さえていく

SSA(静的単一代入)

SSAとはすべての変数がプログラム中で一度だけ定義されるような表現形式である。

例えば以下のようなコードがあったとする。

a = 3;
a = a + 2;
b = a;

これを次のように書き換える。

a0 = 3;
a1 = a0 + 2;
b = a1;

要は逆依存や出力依存をリネーミングによって解消すればよい(はず)。

これによって解析がしやすくなり、最適化がかけやすくなる。

ちなみに言語仕様のマニュアルでは‘well formed’(整形された)IRを書くようにしているらしいが、これってSSAと同義じゃないのか？
「x = x + 1だとxの定義が全てのxの使用を支配できない」の意味がいまいち掴めないんだが、このステートメントに1つxの使用が含まれてるから支配できないということ？

http://coins-compiler.osdn.jp/050303/ssa/ssa-nyumon.pdf

CソースコードとLLVM IRの対応関係

本来なら言語仕様を見ていくべきなんだろうけど、何せ量が多いうえに英語なので読む気が失せる。
のでちょっとズルをする。

とりあえず以下のような簡単なプログラムを用意してclangに通す。

#include <stdio.h>

int main() {
    printf("Hello World!\n");
    return 0;
}

復習だがLLVM IRを出力するためには以下のコマンドを入力する。

$ clang -S -emit-llvm hello.c

出力されるhello.llは以下のようになる。

; ModuleID = 'hello.c'
source_filename = "hello.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [14 x i8] c"Hello World!\0A\00", align 1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i64 0, i64 0))
  ret i32 0
}

declare dso_local i32 @printf(i8*, ...) #1

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 10.0.0-4ubuntu1 "}

これだと訳が分からないので必要な部分だけ抽出すると以下のようになる。

@.str = private unnamed_addr constant [14 x i8] c"Hello World!\0A\00", align 1

define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i64 0, i64 0))
  ret i32 0
}

declare dso_local i32 @printf(i8*, ...) #1

実際この状態のhello.llをlliに渡してもちゃんと動くし、逆にこれ以上削ると動かなくなる。

順に見ていくと

@.str = private unnamed_addr constant [14 x i8] c"Hello World!\0A\00", align 1

これは文字列リテラルの定義である。[]は配列を表現している。”“の前のcが文字列リテラルを表す。
先頭の@はグローバル変数を意味している。（ちなみに@はそれ以外の場面でもいろいろ使われているらしい。意味わからん…）
つまりこれを逆にC言語(GNU C)で表現すると以下のようになる。

const char str[14] __attribute__ ((aligned (1))) = "Hello World!\n";

次は言うまでもなくmain関数である。

define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i64 0, i64 0))
  ret i32 0
}

defineで関数を定義する。関数名は@をつけて書く。()の中に引数を書く。関数にはいろいろな属性を指定できるがここでは#0という略記を使っている。 (#0の具体的な中身は別のところに書かれている。~~消しちゃってるけど？~~)
関数の中ではローカル変数(というかレジスタらしい)に0を代入して”Hello World!”を表示して0を返す。(最初の0代入いらなくない？というか実際消しても動いた)
ちなみにgetelementptrというのはよく勘違いされるらしいが、ざっくりいうとアドレス計算をするものらしい。ここで@.strの先頭のアドレスをprintf関数に渡しているイメージだ。

最後に関数の宣言。

declare dso_local i32 @printf(i8*, ...) #1

定義の場合はdefineだったが、宣言の場合はdeclareになる。あとは{}がない。それはそうとしか言えない。

ここまでで最低限のことは説明してきたが、最後に今まで触れなかった部分にちょこっと触れておく。

; ModuleID = 'hello.c'

; Function Attrs: noinline nounwind optnone uwtable

;以降はコメントである。アセンブリコードと同じ。

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 10.0.0-4ubuntu1 "}

!から始まるものはメタデータである。使い方はよくわからないが最適化やコード生成の時に使われる情報らしい。

https://itchyny.hatenablog.com/entry/2017/02/27/100000

https://qiita.com/Anko_9801/items/df4475fecbddd0d91ccc

LLVM IRの構造

ModuleはFunctionから構成され、FunctionはBasicBlockから構成され、BasicBlockはInstructionから構成されるらしい。
ここら辺の話はまたの機会にちゃんとやりたい。(というかデータ構造の話とセットじゃないと厳しそう)

ざっくり説明するとModuleはソースコード、Functionは関数、BasicBlockは処理のかたまり、Instructionは1回の命令に対応する。