□LLVM/Clang
☆コンパイラの仕組み
◆フロントエンド
＿◇字句解析
意味のある極に分解
※字句文法に沿ってトークンに分解する
⇒記号、識別子、予約語、演算子などに判別される
※語彙素 Lexeme
意味を区別する最小単位
＿◇構文解析
字句を構文に従って解析し中間コードを出力する
※AST
Abstract Syntax Tree
抽象構文木
⇒構文解析でよく用いられる
⇒中カッコなどの不要な情報は取り除かれる
◆ミドルエンド
中間コードをオプティマイズし、最適化済の中間コードを出力する
※最適化処理
オプティマイザ
※最適化の２つの目的
①実行速度の向上
②実行ファイルサイズの縮小
＿◇定数畳み込み
constant folding
※ビルド時にわかっている演算結果を実行コードに反映させ、実行時の演算量を削減する。
◆バックエンド
最終的ターゲットのコードを生成する
①実行する命令の選択
②レジスタの割り当て
③命令の並べ替え
☆LLVMの特徴
①フロントエンド、ミドルエンド、バックエンドの独立
②中立的な設計方針
③独立した中間コードの仕様
※LLVM/Clangのライセンス
University of Illinois/NCSA Open Source License
◆LLVM IR
①オンメモリであつかえる（JITコンパイラでも利用できるようにするため）
②SSA処理
SSA Static Single Assignment 静的単一代入
⇒一つの変数に対して１つの値しか代入しない
⇒実行コードの最適化が行いやすい
⇒一度変数に代入された値が変化しない
◆LLVM IRの表記法
LLVMアセンブリとビットコードは一対一対応。
相互変換可能
＿◇LLVMアセンブリ
※拡張子 .ll
＿◇ビットコード
※拡張子 .bc
＿◇ターゲット情報
コード中で用いられている変数の型やサイズの定義、実行環境の定義
①target datalayout
型定義
⇒実行環境に最適な変数の型やサイズを指定できる
⇒ＬＬＶＭ自体はＣＰＵにとらわれずに整数型の定義ができる（1ビット単位）
⇒ハイフン区切り１つで１つの型
E ビックエンディアン
e リトルエンディアン
S スタックアライメントビット
p[n]::: ポインタ i:: 整数型 v:: ベクタ型 f:: 浮動小数点型 a:: アグリゲート型 s:: スタックオブジェクト ⇒型をビットでアライメント、推奨はビット ⇒アグリゲート型：複数の値が格納できる型、配列、構造体など。（ベクタ型を除く） ⇒スタックオブジェクト：スタック経由で渡される値を格納 ⇒関数同士での値の受け渡しの詳細はABI(Application Binary Interface)で規定 ⇒サイズ０はすべてを表す n::... ハードウエアで実装されているビット幅 ②target triple 実行環境を定義 <アーキテクチャ>-<ベンダ>-<ＯＳ> <アーキテクチャ>-<ベンダ>-<ＯＳ>-<環境>
例）
x86_64-unknown-linux-gnu
＿◇識別子
@から始まる識別子
│ 関数名
│ グローバル変数
%から始まる識別子
│ レジスタ名
│ ローカル変数
＿◇初期データ
文字列
⇒漢字はエンコードされる
※初期データのフォーマット
＿◇関数定義
※同じソースコード無いに定義されている関数の宣言
define
define リンク方式 返値型 @関数名(引数リスト) 属性 {
}
※外部関数定義
declare
declare リンク方式 返値 @関数名(引数リスト) 属性
※関数宣言でのリンクの方式
⇒関数のスコープを指定する
⇒外部ソースからアクセスできない、プライベートなメンバ、DLLなど
⇒internal 同じLLVM IRのコード内のみ参照可能なシンボル
⇒fastcc 引数や返値はメモリを経由せず高速に
＿◇ポインタ
メモリアドレスを扱う場合に使用する
※異なるメモリ空間を指すためのアドレス空間を指定できる
⇒アドレス空間のデフォルト値は０
⇒OpenCLなどむけ
※ポインタ型書式
<型> *
例）
i32 * i32型ポインタ
i32 addrspace(5) アドレス空間5のi32型ポインタ
＿◇ベクタ型
SIMD命令向けの型
例）
<4 x i32> 32ビット整数値x4のベクタ型
＿◇属性
アトリビュート
関数に設定できる。
バックエンドでネイティブコードを生成するときに使われる。
nounwind 例外を関数の外に投げない
noinline インライン化しない
readnone メモリアクセスをしてはいけない
readonly メモリの読み込みのみ
inlinehint インライン化したい
noreturn 返却値なし
sanitize_memory サニタイズメモリ有効化
sanitize_thread サニタイズスレッド有効化
＿◇メタデータ
オプティマイザ、バックエンドがよりターゲットＣＰＵに適したネイティブコードを出力するのに利用される情報
＿◇扱える値
あつかえる値はビット単位で指定できる
①整数
iN
Nは1から2^23-1まで指定可能。巨大なビット長の整数も指定可能
②浮動小数点数
half 16bit
float 32bit
double 64bit
fp128 128(可数部112)bit
x86_fp80 80bit
ppc_fp128 128bit(64bit x 2)
③void
値を返さないことを示す
※ベクタ型以外の配列や構造体など複数の値を格納できる型をアグリゲート型と呼ぶ
④配列
１次元、多次元の配列を宣言できる。
例）
[20 x i16] 16ビット整数 20個
[12 x [10 x float]] 単精度浮動小数の12×10配列
⑤構造体型
パディングの有無を区別して定義。
例）アライメントあり（パディング）
%T1 = type { }
例）アライメント無（パディングなしのパック）
%T2 = type <{ }>
例）
{ i32, i32, i32 } 32ビット整数３個
{ float, i32(i32)* } 一つ目float, ２つ目、関数型（引数i32),返り値i32
<{ i8, i32 }> パックしてある８ビット整数と３２ビット整数
◆LLVM IR命令
＿◇四則演算
※フォーマット例 = add [opt] ,
add, fadd
sub, fsub
mul, fmul
udiv, sdiv (符号なし、符号付割り算）
urem, srem, frem（符号なし、符号付、浮動小数剰余）
⇒デフォルトではオーバーフローでサチュレート
⇒nuw (No Unsigned Wrap)…オーバーフロー発生
⇒nsw (No Signed Wrap)…オーバーフロー発生
⇒オーバフロー発生時にはpoison valueフラグがついて伝播する
＿◇シフト、論理演算
※シフトは３種
shl
lshr
ashr
※論理演算３種
and
or
xor
＿◇ベクタ命令
ベクタ型の演算
※ベクタ型の値に対しての操作は
extractelement 値を取り出す
insertelement 値を代入する
sufflevector ベクタ要素を入れ替える
＿◇メモリアクセス命令
alloa メモリ確保
load ロード
store ストア
fence 同期方法指定
cmpxchg 条件が真なら値交換（アトミック操作）
atomicrmw アトミックなリードモディファイライト
getelementptr アグリゲート型の要素のアドレス取得
＿◇アグリゲート命令
extractvalue 値を取り出す
insertvalue 値を格納
＿◇変換命令
※キャストを行うための命令
trunc .. to 切り詰め
zext .. to ゼロ拡張
sext .. to 符号拡張
fptrunc .. to 浮動小数切り詰め
fpext .. to 浮動小数の拡張
fptoui .. to 浮動小数から符号無整数
fptosi .. to 浮動小数から符号付き整数
uitofp .. to 符号無整数から浮動小数
sitofp .. to 符号付整数を浮動小数
ptrtoint .. to ポインタを整数へ
inttoptr .. to 整数をポインタへ
bitcast .. to ビット変換なしキャスト
addrspacecast .. to アドレス空間変換
＿◇比較命令
※結果は1ビット(0:false, 1:true)
icmp 整数比較
例）
%cond = icmp eq i32 %v1, %v2
条件 unsigned signed
== eq
!= ne
> ugt sgt
>= uge sge
< ult slt
<= ule sle fcmp 浮動小数比較 例） %cond = fcmp eq f32 %v1, %v2 ※浮動小数の場合、OrderedとUnorderedがある Ordered どちらもqNaN(Quiet NaN)でない Unordered どちらかがqNaNならtrue 条件 ordered unordered == oeq ueq != one une > ogt ugt
>= oge uge
< olt ult
<= ole ule
true 常にtrue
false 常にfalse
ord ２つともqNaNではない
uno 一方がqNaN
＿◇分岐命令
br 2方向分岐
例）
br i1 %cond, label %ifEqual, label %ifUnequal
switch 多方向分岐
例）
switch i32 %a, label %7[
i32 0, label %1
i32 1, label %3
i32 2, label %5
]
⇒%aの０～２に応じて分岐、そうでない場合は%7へ分岐
⇒SSA上の多方向分岐先での値の集約のためにphi命令(φ関数)が使われる。
※分岐先の指定
①ラベル
label:
②番号付きブロック
変数 %数値 と同じくブロックにも%数値が振られる
⇒%数 は、新たな値やbr命令で+1される
⇒番号付ブロックには ;
※φ関数
通過したブロック（ラベル）に応じて値を返す
⇒switchで分岐した後でこれを用いれば、経路によって異なる値を同じ変数で返すことが可能となる
例）
%ret.0 = phi i32 [20, %3], [15, %2], [10, %1], [5, %0]
ret i32 %ret.0
⇒[値,通過したラベル]
＿◇固有関数
Intrinsic Functions
※LLVMは整数型などは１ビット単位の指定が可能だが、固有関数ではi32などの標準的な数値型のみ定義されている
※上書き定義可能
①Cの標準関数相当
llvm.memcopy
llvm.memmove
llvm.memset.*
②数学ライブラリ
llvm.sqrt.*
llvm.powi.*
llvm.sin.*
llvm.cos.*
llvm.pow.*
llvm.exp.*
llvm.log.*
llvm.log10.*
llvm.log2.*
llvm.fma.* (axb)+c
llvm.fabs.*
llvm.copysign.* 絶対値MagでSgnの符号を持つ値
llvm.floor.* 切り捨て、整数値
llvm.ceil.* 切り上げ、整数値
llvm.trunc.* 整数値
llvm.rint.* 丸め（例外あり）
llvm.nearbyint.* 丸め（例外なし）
llvm.round.* 四捨五入
③ビット操作
llvm.bswap.* エンディアン変換
llvm.ctpop.* 立っているビット数を数える
llvm.ctlz.* 連続したクリアされているビット数を数える
④演算、オーバーフローライブラリ
llvm.sadd.with.overflow.*
llvm.uadd.with.overflow.*
llvm.ssub.with.overflow.*
llvm.usub.with.overflow.*
llvm.smul.with.overflow.*
llvm.umul.with.overflow.*
llvm.fmuladd.*
llvm.convert.to.fp16
llvm.convert.from.fp16
☆Clang
C/C++/Objective-C/Objective-C++コンパイラ
※最新規格への対応
ISO/IEC 14882:2011 (C++11)
※ライセンス
University of Illinois/NCSA Open Source License
※拡張
①CLangをライブラリとして利用
⇒字句、構文解析などをClangにまかせる
②プラグインでの拡張
◆言語拡張
＿◇マクロ
__has_builtin
│ 指定したビルトイン関数が利用できれば１、そうでなければ０
__has_feature
│ 指定した言語規格機能が使用できるか
__has_extension
│ 指定した機能がコンパイラで利用できるか（独自拡張含む）
__has_attribute
│ 指定した属性が利用できるか
│ ⇒変数、関数などにつける属性
__has_include
│ 指定したヘッダファイルが存在しているか
例）
#if defined(__has_include) … __has_includeマクロ自身が定義されているか？
#if __has_include(“xxx.h”)
#include “xxx.h”
__has_warning
│ 特定のワーニングオプションが有効か
＿◇属性
deprecated
│ 非推奨属性
│ 関数、enumの要素につけられる
│ __has_extensionマクロでattribute_deprecated_with_messageが使えるか否か確認してから用いる
例）
#if __has_extension(attribute_deprecated_with_message)
int foo(int a) __attribute__((deprecated(“xxx”)));
#endif
unavailable
│ 利用不可属性
│ 関数、enumの要素につけられる
＿◇関数オーバロード
C++のメンバ関数はオーバロード可能だが、メンバ関数以外はできない
Clangはoverloading属性を与えることで非メンバ関数のオーバロード可能
＿◇組み込み関数
※組み込み関数の扱いはClangとgccで異なる
⇒ xmmintrin.h などのヘッダファイルで定義
◆Static Analyzer
静的解析ツール
＿◇文法的には正しいバグ
①メモリリーク
確保したメモリの解放しわすれ
mallocの後、freeで解放しない
②ファイルのクローズし忘れ
◆Sanitizer
◆構文解析ライブラリとしてのClangの利用
ソース内の関数（属性含む）、変数（型名）、コメントなどを取得できる
＿◇LibClang
ソースコードを静的に扱う
Clang仕様に依存しない
Pythonからも利用できる
※構文解析メイン
※実装はC++ライブラリ
⇒Pythonバインディングあり
ヘッダ：
/usr/local/include/clang-c/
Pythonバインディング
~/llvm34/llvm/tools/clang/bindings/python/clang/
※Pythonバインディングのパス指定
$ export LD_LIBRARY_PATH=$(llvm-config –libdir)
$ export PYTHONPATH=$HOME/llvm34/llvm/tools/clang/bindings/python/
＿◇LibTooling
Clang::FrontendActionクラスを緒やにもつさまざまなActionライブラリをよびだせる
※C++のみ
＿◇LibTooling
ソースコードを静的に扱う
Clang仕様に依存する（プラグインと互換性がある）
＿◇Clang Plugins
ビルド中に呼び出される⇒ビルドを動的に変更できる
LibToolingと互換性がある
◆Clang’s AST
※AST Abstract Syntax Tree
抽象構文木
ノード情報
Decl declaration
Stmt statement
Type type
DeclContext declaration context
Expr expressions
◆clang-format
C/C++/Objective-Cのソース整形ツール
入力ソースをオプションに指定された方法で整形し、標準出力へ出力する
＿◇事前定義書式とオプション
-style LLVM
-style Google
-style Chromium
-style Webkit
-style Mozilla
＿◇書式指定ファイルの作成
※書式指定ファイル YAML形式
※書式指定ファイルのとりだし例
$ clang-format -style=llvm -dump-config >.clang-format
⇒これを編集して独自ファイルを作成してもよいが、特定のスタイルをベースにちょい変する場合は
—
BasedOnStyle: LLVM
などとしてベースの形式を指定し、変更する部分のみ追加してもよい
IndentWidth: 4
$ clang-format -style=file foo.c
スタイルをfileとすれば.clang-formatが使用される。
直接コマンドラインで渡すことも可能
$ clang-format -style=”{BasedOnStyle: LLVM, IndentWidth: 4}” foo.c
＿◇使用例
$ clang-format -style=LLVM foo.c >foo_LLVM.c
☆ミドルエンド
◆Pass
ミドルエンドでLLVM IRの最適化を行うための処理
⇒多数のPassが存在、それらを組み合わせる
（Pass同士に依存性が設定されている場合がある）
⇒optコマンドにより実行Passを指定できる
⇒ユーザ独自のPassを開発することもできる
※LLVM IRのコード解析にも使用できる
＿◇Passのカテゴリ
CallGraphSCCPass
コールグラフをボトムアップで調べる
※SCC
strongly connected componentsアルゴリズム
FunctionPass
関数単位で処理を行う
LoopPass
同じ関数内になる個々の独立したループをあつかう
⇒多重ネストしている場合では、一番内側から外側に向かって順に処理する
RegionPass
関数内で１つの入り口、１つの出口である処理を扱う
for文、ただしbreak, continue, returnがない
while文、ただしbreak, continue, returnがない
BasicBlockPass
分岐せずに連続して実行される一連の命令群(BasicBlockPass)に適用される。
※のぞき穴最適化
⇒生成された機械語命令の前後を見て、より短い命令に置き換える
MachineFunctionPass
マシン依存で実行するコードを生成するPass
⇒optコマンドから実行することはできない。
◆opt
optコマンド
ビットコードの最適化を行う。
最適化前のビットコード引数を受け取り、指定オプションに従い最適化。
最適化されたビットコードを出力する。
⇒最適化前と後のLLVM IRを比較することができる。
＿◇LLVM IRコードを生成
#include
void multiply_vec4(double *vec, double val) {
int i;
for (i = 0; i < 4; i++) {
vec[i] = vec[i] * val;
}
}
最適化なしでLLVM IRのコードを生成
$ clang -emit-llvm -O0 -S -o mult_vec4.ll -c mult_vec4.c
ビットコードへ変換
$ llvm-as mult_vec4.ll
optによりコールグラフ生成
$ opt -dot-cfg mult_vec4.bc
最適化なしのコードを最適化する
$ opt -O1 -o mult_vec4.o1.bc mult_vec4.bc
再びコールグラフ生成
$ opt -dot-cfg mult_vec4.o1.bc
最適化なしでbcを作成
$ clang -emit-llvm -O0 -o helloworld.bc -c helloworld.c
＿◇パスの確認
optコマンドでどのようなパスを通っているか確認
$ opt -debug-pass=Structure ./helloworld.bc > /dev/null
出力例）
Pass Arguments: -targetlibinfo -datalayout -notti -basictti -x86tti -preverify
-domtree -verify
Target Library Information
Data Layout
No target information
Target independent code generator’s TTI
X86 Target Transform Info
│ ModulePass Manager
│ FunctionPass Manager
│ Preliminary module verification
│ Dominator Tree Construction
│ Module Verifier
│ Bitcode Writer
-O1レベルの最適化を設定。
$ opt -debug-pass=Structure -O1 ./helloworld.bc > /dev/null
⇒-O0のときより多数のPassを通る
＿◇LLVM IRの図式化
①LLVM IRアセンブリを得る
clang -emit-llvm -O1 -S -o fib.ll -c fib.c
②opt
opt -dot-cfg fib.ll
③dot
dot -Tpng cfg.fib.dot -o cfg.fib.dot.png
☆LLVMの利用
◆Windows環境
＿◇パス
実行ファイルのフォルダにパスを通すとともにインクルードパスとライブラリパスを環境変数で設定する必要がある。
※cygwin
set C_INCLUDE_PATH=C:\cygwin\usr\include
set LIBRARY_PATH=C:\cygwin\usr\lib
◆mingw64-x86-windows
◆コンパイラオプション
例）コンパイル
clang -o fib fib.c
例）LLVM IRアセンブリ出力
clang -emit-llvm -O1 -S -o fib.ll -c fib.c
☆tools
◆llvm-as
llvmアセンブリ(.ll)からビットコード(.bc)を生成するアセンブラ
llvm-as -help
◆llvm-dis
ビットコード(.bc)からllvmアセンブリを生成する逆アセンブラ
llvm-dis -help
◆llc
ビットコード(.bc)またはllvmアセンブリ(.ll)からネイティブコードを生成する
◆lli
LLVMビットコード(.bc)の直接実行
中間コードでの実行
clang -emit-llvm -S hello.c
llvm-as hello.s
lli hello.bc
◆llvm-link
ビットコード対応のリンカ
◆llvm-ar
ar互換
※ネイティブコードだけでなくビットコードも含むシンボルテーブルを生成する
◆llvm-nm
nmコマンドのビットコードにも対応版
◆llvm-config
コンパイル時に必要とされる各種コンフィギュレーション情報の取得。
主としてconfigure時につかわれる。
◆llvm-diff
ビットコードやLLVMアセンブリの比較
◆llvm-symbolizer
メモリアドレスからソースの行へと変換