第4章 LLVM IR

4.1 本章の概要と目的

本章ではLLVM IRについて説明します．本章では実際に幾つかのソースコードをLLVM IRに変換し，解説を進めていきます．LLVM IRに現れる基本的な命令群はそれぞれ説明をしますが，LLVM IRに現れる命令は基本的に命令名から概要が想像できるものが多いことや，全ての命令を詳細に解説するのは読者の皆様を混乱させるという判断からこの章では簡単な説明にとどめています．もし各命令の詳細を知りたい場合はLLVMのドキュメント，Language Reference Manualを参照してください．

4.2 LLVM IRの特徴

まず，LLVM IRの特徴について説明します．LLVM IRの命令の多くはアセンブリに似た3番地コードであり，変数はレジスタに保存されます．LLVM IRは無限個の仮想レジスタを持つレジスタマシンをターゲットとした中間表現で，基本的に全てのレジスタ変数がStatic Single Assignment(以降，SSA)形式で表現されます．SSAは日本語で言うと静的単一代入形式のことで，一度代入された変数は変更されることがありません．SSAが何かということは次の段落で説明しますので，今はそういうものがあるということだけ頭に入れておいてください．

LLVMのドキュメント，LLVM Language Reference Manualによると，LLVM IRの形式には以下の3つのパターンがあるそうです．

1. インメモリcompiler-IR(メモリ上のIR表現)
2. ディスク上のビットコード表現
3. 人間が読めるアセンブリ形式の表現

2はこれまでLLVMビットコードと呼んでいたもので，3はLLVMアセンブリと呼んでいたものです．1〜3の3つのIR表現は何れも等価ですが，本章では3番のLLVMアセンブリ形式のLLVM IRを説明していきます．

SSAって何？

SSAは静的単一代入形式というその名の通り，各変数への代入は一度しかされず，一度代入された変数は変更されることがありません．どういうことなのか具体例を用いて見てみましょう．

まず，下記のような式を考えます．

 1: x=1;
 2: y=1;
 3: x=y;

何も考えずに中間表現に直すとそのまま代入文を繰り返せばいいわけですが，それでは同じ変数に代入が行われ，SSAにはなりません．SSA形式であらわすと下記の様になります．

 1: x1=1;
 2: y1=1;
 3: x2=y1;

SSAではこのように変数にバージョン情報を付加し，同名の変数には一度しか代入が行われないように表現します．

さて，ここで問題となるのは分岐等が存在し，変数のとる値が静的に決定できない場合です．とりあえずまた実例をだして見てみましょう．今度は下記のようなソースコードがあったとします．

 1: x=y-1;
 2: if(x<10){
 3:   x= 0;
 4: }
 5: else{
 6:   x=10;
 7: }
 8: y=x;

このコードではif文のthen節とelse節でそれぞれxの値が定義されており，最終的にyへの代入文でxのとる値としては0と10の2パターンが考えられます．どちらが到達するかは現段階ではわかりませんので，最終的にyにどちらの値が代入されるのか決定できません．これを解決するのがφ関数と呼ばれるものです．リスト4.3のコードをφ関数を利用したSSAで表した場合のイメージを図4.1に示します．φ関数は参照する定義が複数存在する場合に，どの制御フローを通過したかによって適切な値を選択する関数です．つまり上記の例では，φ関数はxが10より小さい場合はthen節のxの値を選択し，xが10以上の場合はelse節のxの値を選択します．なんだかしっくりこないかもしれませんがそういうものです．

図4.1: phi関数の例

SSAの利点としては，変数のdef-useチェインがわかりやすく，最適化/解析が簡略化されることなどがあります．また，SSA形式の中にもpruned-SSAやSemiPruned-SSAといった種類があったりします．

4.3 LLVM IRの構成

ここで，LLVM IRの構成について説明しておきます．説明に先立ち，まずLLVM IRの構成図を図4.2に示します．

図4.2: LLVM IRの構成

一つのモジュール(翻訳単位)はLLVM IRではModuleに対応します．また，Moduleは複数のFunctionやGlobalVariable等によって構成される最上位の構成単位です．さらに，Functionは複数のBasicBlockで構成され，BasicBlockは複数のInstructionで構成されます．LLVMのライブラリを用いてLLVM IRを操作する場合，プログラム中ではFunction，BasicBlock，InstructionはそれぞれFunctionクラス，BasicBlockクラス，Instructionクラスとして管理されます．また，ModuleはModuleクラスとして管理されることになります．

次節以降，幾つかのサンプルソースコードをLLVMアセンブリに変換し，どのような形となるかを解説していきます．なお，サンプルソースコードは全てC言語となっています．

4.4 LLVMの型とLLVMアセンブリの主な命令

実際のコードを確認する前に，本節でLLVMアセンブリに出現する型と主な命令を表形式で示します．ここで紹介する命令は，“最低限これぐらいは知っておいた方が良い”と筆者が考える命令です．また，あまり詳しく説明しても混乱を招くだけだと思うので各命令の説明は簡単にまとめています．次節以降で紹介するLLVMアセンブリのコードに出現するものは一通りここで掲載していますが，LLVMの全命令セットが知りたいかもっと詳しい仕様が知りたいという方はLLVMのドキュメント，LLVM Language Reference Manualを参照してください．なお，命令の掲載順はLLVM Language Reference Manualに従います．

4.4.1 型分類

本節ではLLVM の型を簡単に説明します．まず，LLVM IRに出現する型の分類を表4.1に記載します．

表4.1において，primitiveは最も基本的な型であり，derivedはprimitiveや他のderivedの型によって構成される派生的な型となっています．また，first classに分類された型はLLVM IRの命令によって生成される型とされています．例えばintegerやfloating pointはprimitiveですが，LLVM IRの命令によって生成されうる型ですのでfirst classでもあります．

primitive(原始型)

primitiveに含まれる型はLLVMの基本的な構成要素になっています．primitiveに分類される型の概要や書式を表4.2に示します． なお，metadataは他のprimitiveの型と違い少々特殊ですので，こちらついては本章の最後で再度説明します．

derived(派生型)

derivedに分類される型はprimitiveの型，もしくは他のderivedの型を要素に含む派生的な型です．derivedに分類される型の概要や書式を表4.3に示します． なお，表内に示す例では";"より後ろはコメントを表します．

4.4.2 終端命令

ここからLLVM IRの各種命令を紹介していきます．まずはじめに，代表的な終端命令を表4.4に示します．表4.4のreturn命令はC言語におけるreturn文に相当し，br命令はif-else文等の分岐に相当します．また，switch命令はそのままswitch文にあたります．この他の終端命令としては，indirectbr命令やinvoke命令などがあります．

4.4.3 二項演算子

代表的な二項演算子を表4.5に示します．二項演算子には加算や乗算などの二つのオペランドをとる演算命令が分類されます．なお，add命令やsub命令に現れるnswやnuwは，No Signed WrapとNo Unsigned Wrapの略でそれぞれSignedとUnsignedの演算でオーバーフローが発生した時にPoison Valueになるというフラグを意味します．また，udiv命令のexactはop1がop2の倍数で無いときにPoison Valueになるというフラグのようです．LLVMのLLVM Language Reference ManualによるとPoison ValueはUndef Value(未定義の値)と似たもののようです．ただし，Poison Valueは副作用を起こしてはいけない命令や定数式が予期せぬ動作を引き起こすことを検知したという意味を含むとのことです．

4.4.4 ビット演算子

代表的なビット演算子を表4.6に示します．ビット演算子にはシフトや論理和，論理積等の命令が含まれます．shl命令に現れるnuwは0でない値がシフトによって外された場合にPoison Valueになるというフラグで，nswはシフトした結果得られる値の符号ビットと一致しない値(0/1)がシフトによってあふれた時にPoison Valueとなることを意味する様です．また，lshr命令やashr命令のexactはシフトによってあふれた何れかのbitが0でないときにPoison Valueになるというフラグです．

4.4.5 合成演算子

合成演算子を表4.7に示します．合成演算子は合成型の値を操作する命令です．

4.4.6 メモリアクセス演算子

代表的なメモリアクセス演算子を表4.8に示します．メモリアクセス演算子にはメモリの確保やロード，ストア等の命令が含まれます．SSA形式においてメモリをどのように表現するかというのは重要なポイントですが，LLVMにおいてはメモリ配置はSSA形式にしないことでシンプルにしている様です．少し意図が伝わりにくいかもしれませんが，本節で紹介するstore命令やload命令の役割を見るとメモリアクセス演算子の特殊さがわかると思います．本節で示した以外のメモリアクセス演算子としては，fence命令やcmpxchg命令があります．なお，getelementptr命令にinboundが付与された場合は，getelementptr命令が確保された領域の範囲外へアクセスした場合に結果がPoison Valueとなることを意味します．

4.4.7 型変換演算子

代表的な型変換演算子を表4.9に示します． 型変換演算子にはその名の通り，オペランドとして渡された値の型を変換する命令が分類されます．

4.4.8 その他の命令

その他の命令を表4.10に示します．今回は，その他の命令としてicmp，fcmp，phi，callの四つの命令を紹介しておきます．icmp命令やfcmp命令は値を比較する命令で，phi命令はSSAの説明で紹介したphi関数に相当します．また，call命令は関数呼び出しに使用する命令です．LLVM Language Reference Manualのその他の命令(Other Operations)の項目では，他にselect命令やva_arg命令などが紹介されています．

なお，icmpのcondに指定できる条件を表4.11に，fcmpのcondに指定できる条件を表4.12に示します．

4.5 基本的なLLVMの中間表現

LLVM IRの構成を理解することを目的として，まず最も簡単な例としてHelloWorldを例としてとりあげます．下記のHelloWorldのソースコードをLLVM IRに変換し，構成を確認していきましょう．

 1: #include<stdio.h>
 2: 
 3: int main(){
 4:   printf("HelloWorld\n");
 5:   return 0;
 6: }

以下のコマンドを投入し，HelloWorld.cをLLVM IRに変換します．

$ clang -emit-llvm -S -o HelloWorld.ll HelloWorld.c

HelloWorld.llというファイルが出力されると思いますので，viやlessで中を確認しましょう．HelloWorld.llの中を見るとリスト4.5のような出力結果が得られていると思います．

 1: ; ModuleID = 'HelloWorld.c'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: @.str = private unnamed_addr constant [12 x i8] c"HelloWorld\0A\00", align 1
 6: 
 7: define i32 @main() nounwind {
 8: entry:
 9:   %retval = alloca i32, align 4
10:   store i32 0, i32* %retval
11:   %call = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([12 x i8]* @.str, i32 0, i32 0))
12:   ret i32 0
13: }
14: 
15: declare i32 @printf(i8*, ...)

それでは，ここからHelloWorld.llの内容を解説していきます．なお，解説の流れとしてはまず全体の構成を説明した後にコードを幾つかに分割して説明，という形をとります．

全体の構成

まずはざっくりと今回のLLVM IRの構成を説明します．リスト4.5の1〜3行目はソースコード名や環境などの情報が記述されており，5行目でプログラム中に出現する文字列定数の定義を行っています．そして7〜13行目はmain関数の定義，15行目はprintf関数の宣言となっています．

データレイアウトとアーキテクチャ定義

それでは，それぞれの内容を更に詳しく見ていきましょう．まず，1行目の;Moduleから始まる一文はコメントです．LLVMアセンブリでは;をつけると行末までがコメントになります．ちなみに，コメントで書かれている内容は入力ソースコード名です．これは特に問題ないでしょう．

2行目には意味不明の文字列が並んでいますが，実はこれはアラインメント等のデータの配置方法(以降DataLayout)を示しています．この部分に記述される情報を表4.13にまとめましたのでご覧下さい．

なお，DataLayoutが規定されていない場合は，表4.14の値がデフォルト値として利用されます．

ではここで改めて今回のLLVM IRを見直してみましょう．上記の内容に従うと今回のLLVM IRでは表4.15に示す内容が規定されていることになります．

最後に，3行目のi386〜という記述はtarget-tripleというもので，アーキテクチャやOSなどの環境が記載されています．なお，今回示したDataLayoutやtarget-tripleは筆者が使用している環境での値であり，ここに記載される値は当然環境によって異なります．

グローバル宣言

5行目の@.str〜の一文ではプログラム中に現れる文字列を定義しています．LLVM IRではグローバル変数は@から始まる識別子で表記されます．ここで定義されている@.strというのは後にprintfの引数となる文字列ですね．

関数定義

7行目からmain関数の定義にはいります．8行目のentryというのはBasicBlockのラベル(名前)です．今回はBasicBlockが一つしかありませんが，分岐を含む場合は複数のBasicBlockが現れそれぞれに固有のラベルがつけられます．9行目からはBasicBlock内に含まれる処理，つまり命令が列挙されています．9行目において，まず変数retvalとしてalloca命令でメモリを確保しています．なお，今回のallocaは32×1の領域を4バイトアラインメントで確保しています．10行目はstore命令でretvalに0を代入しています．11行目でcall命令でprintf関数を呼び出し，ret命令で値を返します．ちなみに皆さんお気づきだとは思いますが，retvalの値はstore命令後一切使用されていません．以前のClangで出力では最終的にretvalの値をload命令で取得してret命令で返却する，という処理があったのですが，3.1では無くなっています．*1

さて，話はそれましたが最後にprintfの関数宣言があります．関数宣言はdeclareで行います．今回はライブラリ関数なので宣言のみですが，関数が定義されている場合はmain関数と同様に関数定義，つまりBasicBlockや命令も記述されます．

4.6 条件文

HelloWorldを理解したところで次は条件分岐を含むプログラムを見ていきましょう．今回は下記のif-elseを含むプログラムを使ってみます．

 1: #include <stdio.h>
 2: 
 3: int main(int argc, char **argv) {
 4: 
 5:   int i;
 6:   if (argc == 0) {
 7:     i = 1;
 8:   } else {
 9:     i = 2;
10:   }
11: 
12:   return 0;
13: }

先ほどと同じく上記ソースコードの中間表現を出力します．

$ clang -emit-llvm -S -o branch.ll branch.c

さて，出力された中間表現を確認しましょう．

 1: ; ModuleID = 'branch.c'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: define i32 @main(i32 %argc, i8** %argv) nounwind {
 6: entry:
 7:   %retval = alloca i32, align 4
 8:   %argc.addr = alloca i32, align 4
 9:   %argv.addr = alloca i8**, align 4
10:   %i = alloca i32, align 4
11:   store i32 0, i32* %retval
12:   store i32 %argc, i32* %argc.addr, align 4
13:   store i8** %argv, i8*** %argv.addr, align 4
14:   %0 = load i32* %argc.addr, align 4
15:   %cmp = icmp eq i32 %0, 0
16:   br i1 %cmp, label %if.then, label %if.else
17: 
18: if.then:                                          ; preds = %entry
19:   store i32 1, i32* %i, align 4
20:   br label %if.end
21: 
22: if.else:                                          ; preds = %entry
23:   store i32 2, i32* %i, align 4
24:   br label %if.end
25: 
26: if.end:                                           ; preds = %if.else, %if.then
27:   ret i32 0
28: }

しかし今回は何やらBasicBlockが複数あって少し長いですね．別に読めなくはないですが，BasicBlockの遷移をグラフにすると読みやすくなりそうです．というわけで，次のコマンドを投入してみてください．

$ opt -S branch.ll -dot-cfg

正常に実行できれば，cfg.main.dotというファイルが出来ていると思います．これはdotという形式で記述されたControl Flow Graph(以降，CFG)です．xdotを入れていればこのファイルを閲覧できると思います．また，以下のようにdotコマンドを用いれば任意の形式へ変換することも可能です．

# Tの直後に指定した形式へ変換．ここではeps
$ dot -Teps cfg.main.dot -o branch.eps

それでは出力したCFGを見てみましょう．

図4.3: LLVMの条件文のCFG

何だかグラフィカルでわかりやすくなりましたよね*2!?さて，それではこのCFGを見ながら先ほどの中間表現を振り返ってみましょう．まずentryブロックからですが，13行目までは特に問題ないでしょう．先ほど説明したallocaやstore命令を使用して，メモリの確保や初期化を行っているだけです．入力ソースコードで言うと5行目までに相当します．

14行目からは新しい命令が登場してきます．今回新しく登場した命令はload，icmp，brの3命令です．順を追って説明していきましょう．

まずload命令はその名の通り値をloadする命令です．今回は，%argc.addrが指すアドレスの値をレジスタ%0に格納しています．%0の値は次のicmp命令の引数として使用されます．icmpは指定した条件で引数で指定した二つの値を比較し，真偽値を返します．今回はeqを指定して%0と0が渡されているため，%0の値が0の時にtrueに，それ以外の時にfalseになります．icmpで得た真偽値は次のbr命令の引数になります．名前でピンと来た方も多いと思いますが，brは所謂ブランチ(分岐)のことです．つまりはここで条件分岐が発生するわけです．icmpの結果がtrueの時にif.thenブロックへ，falseの時にif.elseブロックへ分岐します．あとはもうおわかりだと思いますが分岐後に最終的にif.endブロックに合流し，0をreturnします．

ちなみに今回はif文だったのでicmpとbrで分岐しましたが，switch文の場合はswitch命令が使用されます．

4.7 ループ文

条件文の説明をしたわけですし特別説明する必要もないかとも思いますが，一応念のためにループ文も確認しておきます．今回はリスト4.8に示す様な簡単なループ文をコンパイルしてみます．

 1: #include <stdio.h>
 2: 
 3: int loop(int n) {
 4:   int i;
 5:   for (i = 0; i < n; i++)
 6:     printf("%d\n", i);
 7: 
 8:   return i;
 9: }

いつも通りClangで中間表現を出力します．

$ clang -emit-llvm -S -o loop.ll loop.c

出力された中間表現はリスト4.9の通りです．

 1: ; ModuleID = 'loop.c'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
 6: 
 7: define i32 @loop(i32 %n) nounwind {
 8: entry:
 9:   %n.addr = alloca i32, align 4
10:   %i = alloca i32, align 4
11:   store i32 %n, i32* %n.addr, align 4
12:   store i32 0, i32* %i, align 4
13:   br label %for.cond
14: 
15: for.cond:                                         ; preds = %for.inc, %entry
16:   %0 = load i32* %i, align 4
17:   %1 = load i32* %n.addr, align 4
18:   %cmp = icmp slt i32 %0, %1
19:   br i1 %cmp, label %for.body, label %for.end
20: 
21: for.body:                                         ; preds = %for.cond
22:   %2 = load i32* %i, align 4
23:   %call = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i32 %2)
24:   br label %for.inc
25: 
26: for.inc:                                          ; preds = %for.body
27:   %3 = load i32* %i, align 4
28:   %inc = add nsw i32 %3, 1
29:   store i32 %inc, i32* %i, align 4
30:   br label %for.cond
31: 
32: for.end:                                          ; preds = %for.cond
33:   %4 = load i32* %i, align 4
34:   ret i32 %4
35: }
36: 
37: declare i32 @printf(i8*, ...)
38: 

今回もCFGを載せて解説を進めていきます．

$ opt -S loop.ll -dot-cfg
$ dot -Teps cfg.loop.dot -o loop.eps

図4.4: ループ文のCFG

今回はentry，for.cond，for.body，for.inc，for.endの五つのブロックが登場します．まずentryはループのプリヘッダとなるブロックであり，処理内容はこれまで同様allocaによるメモリ確保と初期化，及び次ブロックへのbr命令です．今回のbr命令ではfor.condへ無条件に遷移しています．次に，CFGを確認するとfor.cond，for.body，for.incの3つのブロックでループが発生していることがわかります．つまりここが入力ソースコードの5，6行目のループ文に該当する処理となるわけです．

まず，最初のブロックであるfor.condはループのヘッダと呼ばれる部分であり，ループの繰り返しの条件判定をしています．condをconditionの略だと考えれば意味がわかりやすいと思います．条件分岐はif文でも登場したicmp命令で行っています．今回のicmp命令では条件としてsltを指定し，load命令で読み込んだiとnの値を比較しています．入力ソースコードの5行目，i < nに相当する部分ですね．

for.bodyはその名の通りループの本体です．今回のソースコードでは6行目のprintf関数の呼び出しに相当します．これはHelloWorldと同じ形式なので説明を省略します．

for.incはループラッチと呼ばれるブロックで，今回の例では制御変数iの加算が行われています．for.incは最終的にbr命令でループヘッダ(for.cond)へ遷移しており，CFGでもfor.condへのバックエッジが確認できると思います．

for.condに戻った後は再度条件判定が行われ，繰り返し条件がfalseであればfor.endへ抜けます．for.endはループの出口ブロックであり，変数iの値を返すためにload命令とret命令が記述されています．

なお，今回はfor文で確認しましたが，while文でも基本的には見方は同じです．

最適化した場合

さて，気づいた方もいるかもしれませんが，loop.llではfor.condに到達するブロックの中に変数iへの代入を行う物が複数存在するというのにphi命令が使用されていません．これは変数iをallocaでスタック上に確保しており，storeとloadで読み書きしているためです．一応SSA形式ではあるものの最初に色々と言った手前これでは疑問が残ると思うのでphi命令を使用した形式に変換してみます．

LLVMにはmem2regというPassが用意されておりこのPassはメモリアクセスを可能な限りレジスタへ変更してくれます．次のコマンドでloop.llにmem2regを適用してみましょう．

$ opt -S -mem2reg loop.ll -o loop_reg.ll

次のような結果が得られるはずです．

 1: ; ModuleID = 'loop.ll'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
 6: 
 7: define i32 @loop(i32 %n) nounwind {
 8: entry:
 9:   br label %for.cond
10: 
11: for.cond:                                         ; preds = %for.inc, %entry
12:   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
13:   %cmp = icmp slt i32 %i.0, %n
14:   br i1 %cmp, label %for.body, label %for.end
15: 
16: for.body:                                         ; preds = %for.cond
17:   %call = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i32 %i.0)
18:   br label %for.inc
19: 
20: for.inc:                                          ; preds = %for.body
21:   %inc = add nsw i32 %i.0, 1
22:   br label %for.cond
23: 
24: for.end:                                          ; preds = %for.cond
25:   ret i32 %i.0
26: }
27: 
28: declare i32 @printf(i8*, ...)

allocaやload，storeが消え，全ての変数がレジスタに格納されています．また12行目でphi命令が使用され，iの値選択にφ関数が使用されていることが確認できます．

4.8 合成型へのアクセス

合成型，つまり配列や構造体へのアクセス方法の確認します．実際の例を見て確認していきましょう．

 1: #include <stdio.h>
 2: 
 3: struct hoge1 {
 4:   float x;
 5:   int y[10][20];
 6: };
 7: struct hoge2 {
 8:   char a;
 9:   double b;
10:   struct hoge1 c;
11: };
12: 
13: int *getelem(struct hoge2 *hoge) {
14:   return &hoge[1].c.y[5][13];
15: }

今回もClangでLLVMアセンブリを生成します．

$ clang -emit-llvm -S -o aggregate.ll aggregate.c

出力されたコードを確認します．

 1: ; ModuleID = 'aggregate.c'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: %struct.hoge2 = type { i8, double, %struct.hoge1 }
 6: %struct.hoge1 = type { float, [10 x [20 x i32]] }
 7: 
 8: define i32* @getelem(%struct.hoge2* %hoge) nounwind {
 9: entry:
10:   %hoge.addr = alloca %struct.hoge2*, align 4
11:   store %struct.hoge2* %hoge, %struct.hoge2** %hoge.addr, align 4
12:   %0 = load %struct.hoge2** %hoge.addr, align 4
13:   %arrayidx = getelementptr inbounds %struct.hoge2* %0, i32 1
14:   %c = getelementptr inbounds %struct.hoge2* %arrayidx, i32 0, i32 2
15:   %y = getelementptr inbounds %struct.hoge1* %c, i32 0, i32 1
16:   %arrayidx1 = getelementptr inbounds [10 x [20 x i32]]* %y, i32 0, i32 5
17:   %arrayidx2 = getelementptr inbounds [20 x i32]* %arrayidx1, i32 0, i32 13
18:   ret i32* %arrayidx2
19: }

何やら13行目からgetelementptr命令がたくさん並んでいます．直感で何となくわかりそうですが，とりあえず順を追って確認していきましょう．

まずは13行目の命令です．このgetelementptr命令ではstruct.hoge2のポインタ%0と1が引数として与えられています．getelementptr命令は第1引数で与えられたポインタをベースとして，第2引数以降で指定されたインデックスの要素のアドレスを計算します．なお，getelementptr命令の一つ目のインデックスは第1引数で与えたポインタのインデックスづけに使用されます．つまり今回は%0のインデックス1の要素のアドレスを計算しており，入力ソースコードでいうところのhoge[1]に相当します．

次は14行目です．今回は先ほど計算したarrayidxをベースとして0と2という二つのインデックスが渡されています．これにより，このgetelementptr命令ではarrayidx[0]のインデックス2(3つめの要素)のアドレスを計算していると考えることが出来ます．arrayidxはstruct.hoge2のポインタですので，hoge2構造体を確認すると，3つめの要素はstruct hoge1 cとなっています．というわけで，ここまででhoge[1].cのアドレスが計算できました．

ここまでわかれば後は同じことの繰り返しです．15行目でhoge[1].c.y (hoge[1].c.y[0]と言い換えられる)を，16行目でhoge[1].c.y[5]を，そして17行目でhoge[1].c.y[5][13]を計算しています．getelem関数は戻り値がポインタなので最後のarrayidx2の値を返却しますが，計算したアドレスに格納された値を取り出す場合はload命令を使用します．

ちなみに，getelementptrのインデックスは最適化をかけると下記の様に簡略化されます．

 1: ; ModuleID = 'aggregate.ll'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: %struct.hoge2 = type { i8, double, %struct.hoge1 }
 6: %struct.hoge1 = type { float, [10 x [20 x i32]] }
 7: 
 8: define i32* @getelem (%struct.hoge2* %hoge) nounwind readnone {
 9: entry:
10:   %arrayidx2 = getelementptr inbounds %struct.hoge2* %hoge, i32 1, i32 2, i32 1, i32 5, i32 13
11:   ret i32* %arrayidx2
12: }

たくさんあったgetelementptr命令が一つになっていますが，意味的には同じです．

4.9 Metadata

4.4.1節で紹介したfirst classにmetadataというものがありました．first class内の他の項目(pointerやvector，structureなど)はおおよそ見当がつくと思いますが，metadataは少し特殊だと思うのでここで説明しておきます．

LLVM IRではソースコードレベルのデバッグ情報など，最適化やコード生成で使用するためのコードに関する情報を命令内に埋め込むことができます．Metadataを命令に付与することでLLVM IRの命令だけでは読み取れない情報をバックエンド側へと渡すことができます．

Metadataの構成要素にはMetadata StringとMetadata Nodesがあるのですが，まずMetadata Stringから説明します．Metadata Stringはダブルクオートで囲まれた任意の文字列で，Metadataであることを示すために前置記号として!をつけて記述します．非表示文字列を含む場合は，“\00”のようにバックスラッシュで16進コードをエスケープします．Metadata Nodesは複数の要素によって構成されるMetadataで，各要素をカンマで区切り，{ }で囲って記述します．なお，Metadata Nodesはオペランドに任意の値をとることができます．

 1: ; Metadata Nodes(0から連番が振られる模様)．
 2: !0 = metadata !{ metadata !"sample\00", i32 0}

さらに，複数のMetadata Nodesの集合としてNamed Metadataを定義することができます．以下にNamed Metadataの例を記載します．

 1: ; Metadata Nodes
 2: !0 = metadata !{metadata !"sample1"}
 3: !1 = metadata !{metadata !"sample2"}
 4: !2 = metadata !{metadata !"sample3"}
 5: ; 上の三つのMetadata NodesをもつNamed Metadata
 6: !name = !{!0, !1, !2}

なお，Named MetadataのオペランドとなるのはMetadata Nodesのみであり，Metadata Stringをオペランドとして与えることはできません．

LLVM 3.2ではtbaa Metadata，tbaa.struct Metadata，fpmath Metadata，range Metadataなどの特別なMetadataがLLVMのライブラリで用意されています．なお，trunkの情報を見ているとLLVM 3.3ではllvm.loop.parallel Metadataやllvm.mem.loop.parallel_loop_access Metadataが追加される様です．

’tbaa’Metadata

tbaa MetadataはTypeBasedAliasAnalysis(TBAA)で使用します．AliasAnalysisとはある記憶領域が複数の変数から参照されるかを解析するコード解析手法です(ポインタをイメージするとわかりやすいでしょうか)．TBAAはその中でも型に基づいて行う解析のことで，LLVMにおいてはMetadataを用いてLLVMの型情報とは別にプログラミング言語の型情報をLLVM IR中に挿入します．これがtbaa Metadataです．今回は詳細を割愛しますが，LLVMのドキュメント“LLVM Language Reference Manual”にて簡単に紹介されていますので，興味のある方は目を通してみてもいいかもしれません．

’tbaa.struct’Metadata

tbaa.struct Metadataはllvm.memcpyでコピーするメモリ領域のパディング情報や構造体のtbaaタグの情報を表すMetadataです．llvm.memcpyはLLVMの組み込み関数であり，連続するメモリ領域をコピーする関数です．llvm.memcpyは例えば合成型への代入を実装するために使用されますが，連続するメモリ領域をコピーする関数ですので，対象のメモリ領域にパディングが詰められているかどうかは意識しません．また，llvm.memcpyには合成型の各要素のtbaa情報を一切含みません．tbaa.struct Metadataはこれらの情報を表すMetadataです．tbaa.struct Metadataはオフセット，サイズ，tbaaタグの三つの要素を1セットとして，構造体のどの領域がパディングであるかや各要素のtbaa情報を表します．

’fpmath’Metadata

fpmath Metadata は，浮動小数点数に関する命令に付与されるMetadata で，許容可能な誤差をULPで示すのに利用します．ULPとはUnits in the Last Place の略で，演算の精度を表す単位です．ULP は，ULP(x) の値を1ULPとして誤差を示すのに利用します．非常にざっくりとした説明をすると，連続する浮動小数点数aとbの間にある実数xについて，ULP(x)の値は|b - a|になります．基本的に、0.5ULP以上の差がある場合は別の値に近似されるはずですので，ある浮動小数点演算の結果を正確に最も近い値に近似した場合，誤差は0.5ULP以下に収まるはずです．

実際のfpmath Metadataの例を以下に示します．

 1: ; ULP 0.5を示すfpmath Metadata
 2: !0 = metadata !{float 5.000000e-01}
 3: ;上記のMetadataを付与した浮動小数点数の演算命令
 4: %fpmath_sample = fsub float %float_val, 2.000000e+00, !fpmath !0

浮動小数点数を扱う命令はいくつかありますが，今回は例として浮動小数点数同士の減算を行うfsub命令を使用しています．fsubにfpmath Metadataを付与すると，!fpmathというタグともにMetadataがオペランドとして追加されます．上記の例ではULP 0.5を指定したfsub命令となっていますが，これは0.5 ULP以内の誤差を許容することを示しています．

’range’Metadata

range Metadataはload命令に付加できるMetadataです．load命令は値をメモリ上からロードする命令ですが，range Metadataは整数のload命令に対して，ロードする値のとりうる範囲を示すのに使用します．range Metadataの書式は以下のとおりです．

 1: ; 0～100を示すrange Metadata
 2: !0 = metadata !{i32 0, i32 100}
 3: ;上記のrange Metadataを付与したload命令
 4: %tmp = load i32* %i, !range !0