Low Level Virtual Machine - 通信用語の基礎知識

概要
　Low Level Virtual Machine(以下、LLVM)は「VM」という語を含むが、実際にはVM(仮想計算機)ではなく、コンパイラーのバックエンドを構築するためのフレームワークである。
　CやC++などの言語を処理するためのフロントエンドが作成する中間言語を受け取り、最適化を実施しつつ、各アーキテクチャー用のネイティブコード(x86、x86-64、ARMアーキテクチャなど)を出力する機能を有する。
　従って、言語だけでなく、アーキテクチャーからも独立している。

仕様

フロントエンド
　現在のC、C++、Objective-Cの公式なフロントエンドはclangで、LLVM 2.6から正式採用された。
　初期には、幾つかのフロントエンドが開発中だった。
　例えば、GCC 4.xから作られたフロントエンドllvm-gccを使うことで、C、C++、FORTRAN、Objective-C、Ada、Dの各言語に対応できた。但しllvm-gccはLLVM 2.9を対応の最後とし、LLVM 3.0以降ではサポートされなくなった。
　LLVMに注目が集まり始めると、LLVMをバックエンドに、GPLではないコンパイラーを作ろうという動きが現われはじめ、C、Objective-C、C++に対応しAppleが全力を投入して開発したフロントエンドclangが、圧倒的な資金力と開発力でGCCを凌駕し、LLVMの公式なフロントエンドとなった。
　ちなみにAppleがclangに本気を出したのは、GCCにおけるObjective-C対応に不満を持っていたためで、LLVMという既にかなりの水準にある基盤を用いて新たなコンパイラーclangを作ることに全力を注いだ「おこぼれ」を、一般のユーザーはありがたく拝領することとなったものである。

中間言語
　LLVMは、処理の段階に応じて複数の中間言語(中間表現)を持ち、高級言語に近い高レベルな中間言語から、機械語に近い低レベルな中間言語にまで変換される。

AST　clangがプログラミング言語を解析し、変換した独自の抽象構文木の情報。
　ASTはツリーで、かつコンテクストを保有している。
BitCode　LLVMの中心となる中間表現(IR)で、静的単一代入(SSA)形式となっている。
　この段階で最適化(大規模な変換)が可能なように設計されている。
　BitCodeでは、ASTが保有していたコンテキストは失われている。ループ構文は失われ、展開されている。
SelectionDAG　llcが内部で使用する中間言語の一つ。
MachineInstr　llcが内部で使用する中間言語の一つ。
　アセンブリ言語に変換することを目的とした中間言語であり、1命令ごとの粒度は小さく、BitCodeよりも更に低レベルの言語である。

コンパイルの流れ

フロントエンドが言語を処理し、BitCodeを出力する
1. 字句解析、構文解析等を実施し、ASTに変換する
2. ASTをBitCodeに変換する
opt(オプティマイザー)がBitCodeを読み込み、最適化し、BitCodeを出力する
1. モジュールレベルでの最適化
2. CallGraphSCCレベルでの最適化
3. ファンクションレベルでの最適化
4. ループレベルでの最適化
5. BasicBlockレベルでの最適化
llvm-ldが複数のBitCodeを読み込み、最適化し、一つのBitCodeを出力する
1. 一つのモジュールに統合する
2. モジュール内で、link time optimization(lto)を実施する
llcがBitCodeを読み込み、最適化し、プラットフォーム固有のアセンブリ言語を出力する

特徴

(新しい順)。

DiscoPoP ‐ 並列処理検出ツール
Just-in-time Adaptive Decoder Engine (Jade)
Crack ‐ コンパイル言語の性能を持つスクリプト言語
Rubinius ‐ Rubyの実装
MacRuby
TTA-based Codesign Environment (TCE)
Sun OpenJDKのIcedTeaバージョン
Pure ‐ 代数/関数型プログラミング言語
LLVM-based D Compiler (LDC) ‐ D言語コンパイラー
How to Write Your Own Compiler
Register Allocation by Puzzle Solving
Faust ‐ リアルタイム音声信号処理用言語
Hydra ‐ Adobeの画像処理アルゴリズム記述用プログラミング言語
Calysto ‐ 静的解析ツール
Improvements on SSA-Based Register Allocation ‐ SSAベースのレジスターの割り当ての改善
LENS Project
Trident Compiler ‐ FPGAを対象とする科学的アルゴリズム用のコンパイラー
Ascenium Reconfigurable Processor Compiler ‐ Ascenium再構成型プロセッサー用のコンパイラー
Scheme to LLVM Translator ‐ 小型のSchemeコンパイラー
LLVM Visualization Tool ‐ LLVM可視化ツール
Improvements to Linear Scan register allocation ‐ リニアスキャンレジスタ割り当て
LLVA-emu project
SPEDI: Static Patch Extraction and Dynamic Insertion ‐ 静的パッチ抽出と動的な挿入
SSAPRE
Jello ‐ LLVMバイトコード用のリターゲットJITコンパイラー
Emscripten ‐ LLVMからJavaScriptへのコンパイラー
Rust ‐ プログラミング言語Rust
ESL: Embedded Systems Language ‐ 組込みシステム言語
RTSC: The Real-Time Systems Compiler ‐ リアルタイムシステムのコンパイラー
Vuo ‐ マルチメディア創作者向けの現代的なビジュアルプログラミング言語

　上記の他に、次のようなものもある/あった。

Glasgow Haskell Compiler (GHC) ‐ Haskell(遅延評価を行なう関数型言語)
Julia ‐ 技術計算向けの動的言語
Open Shading Language(OSL) ‐ シェーディング向け言語
Portable OpenCL (pocl)
LLILC ‐ Microsoftの開発した、.NET CoreCLR向けコンパイラー

アーキテクチャ

主な実装
　LLVM 3.5の時点で主たる対応オペレーティングシステムは次の通り(アーキテクチャーごとの対応は後述)。

Microsoft Windows (x86)
Darwin 10.9
FreeBSD 10 (x86、x64)
Ubuntu 14.04 Linux (x64)
OpenSUSE 13.1 (x86、x64)
Fedora 20 (x86、x64)
Linux (AArch64)
Linux (ARM7a)
Linux (MIPS)

　LLVM 3.5の時点で主たる対応アーキテクチャーとされているものは次の通り。

x86
- x86 (IA-32)
- x64、x86-64 (AMD64 ISA/Intel 64)
PowerPC
- PowerPC
- PowerPC-64
ARMアーキテクチャ
- AArch32
  - A32
  - T32
- AArch64
  - A64
SPARC
Alpha
SPU (Cell Broadband Engine)
MIPS (32/64)
MSP430
System z
XCore

　以下は、おそらく実験的な段階のもの。

Hexagon
MBlaze
NVPTX (NVIDIA GPU)
R600 (AMDGPU)

過去の実装
　以下は、過去にコードジェネレーターが存在したが最新版ではなくなっている環境。

Alpha ‐ LLVM 3.1で削除されたようだが、公式には対応中のアーキテクチャーとしている
Blackfin ‐ LLVM 3.1で削除された
PIC16 ‐ LLVM 2.4で対応したらしいが、いつの間にか削除

その他の実装

Z80　Z80用の実装llvm-z80の開発を目指すプロジェクトも確認されている。
　これがもし完成すれば、MSX-DOSなどで動作するソフトウェアをC++やObjective-Cを使って開発することが可能になることを意味する。

未対応
　昨今の需要となるスマートフォン開発などでは、以下の環境やCPUが未対応である。

SuperH(SH)
Dalvik
JVM

　Dalvikのバイナリを出力できれば、Android NDKなどを使わずともAndroidアプリケーションをC++やObjective-Cを使って開発することが可能になる。

補足

ライセンス
　「University of Illinois/NCSA Open Source License」というライセンスが採用されている。
　著作権表示を消してはならない、という当たり前のことが規定されているだけで、その内容はBSDライセンスに近く配布に殆ど制限がない。GPLのような、余計な義務が一切ないのが特徴である。
　ここから、GCCの代替としてLLVMに注目が集まるようになった。

GPL排除との関連
　従来使われてきたGCCはGPLだが、このライセンスは業務開発には全く向いていないものであった。これがGPLv3になると更に業務開発に向かなくなり、多くのオープンソース界隈が反発した。
　OpenBSDやFreeBSDなどのBSD陣営も同様で、Linuxと違って業務用途で広く使われているこれらオペレーティングシステムはGPLv3ツールを同梱するわけにはいかなかったため、他のコンパイラーへの移行が進められるようになった。FreeBSDは、その候補としてclang/llvmを選択した。
　clangは瞬く間に成長を遂げ、GCCをあっという間に追い越してしまった。

バージョン

沿革

LLVM 3.7

　これより↑は予定
　以下リリース済み

LLVM 3.6.0 (2015(平成27)年2月27日)
LLVM 3.5.1 (2015(平成27)年1月20日)
LLVM 3.5 (2014(平成26)年9月4日)
LLVM 3.4.2 (2014(平成26)年6月19日)
LLVM 3.4.1 (2014(平成26)年5月9日)
LLVM 3.4 (2014(平成26)年1月2日)
LLVM 3.3 (2013(平成25)年6月17日)
LLVM 3.2 (2012(平成24)年12月20日)
LLVM 3.1 (2012(平成24)年5月22日)
LLVM 3.0 (2011(平成23)年12月1日)
LLVM 2.9 (2011(平成23)年4月6日)
LLVM 2.8 (2010(平成22)年10月)
LLVM 2.7 (2010(平成22)年4月)
LLVM 2.6 (2009(平成21)年10月23日) clangを正式採用
LLVM 2.5 (2009(平成21)年3月)
LLVM 2.4 (2008(平成20)年11月)
LLVM 2.3 (2008(平成20)年6月)
LLVM 2.2 (2008(平成20)年2月)
LLVM 2.1 (2007(平成19)年9月)
LLVM 2.0 (2007(平成19)年5月)
LLVM 1.9 (2006(平成18)年11月19日)
LLVM 1.8 (2006(平成18)年8月9日)
LLVM 1.7 (2006(平成18)年4月20日)
LLVM 1.6 (2005(平成17)年11月8日)
LLVM 1.5 (2005(平成17)年5月18日)
LLVM 1.4 (2004(平成16)年12月9日)
LLVM 1.3 (2004(平成16)年8月13日)
LLVM 1.2 (2004(平成16)年3月19日)
LLVM 1.1 (2003(平成15)年12月17日)
LLVM 1.0 (2003(平成15)年11月18日)

LLVM 3.6

改良点

prefix属性のセマンティクスを変更
メタデータは値ではなくなった
値とメタデータ間のブリッジ
メタデータには型がない
明確なメタデータノード
巡回グラフの構築
MDLocation (別名、DebugLoc、DILocation)
エイリアスの構文の変更
古いJITの削除、MCJITへの移行
object::Binary は自身のファイルバッファーを持たない単なるラッパーとなった
gold plugin が書き直された
遅延読み込み関数の表現を変更
-std-compile-opts オプションの廃止 (実質的に -O3 の別名だったため)
Python 2.7 以降必須
リーク検出機能は削除された (asan や valgrind の方が優秀だったため)
新しいcomdat構文
Win64サポートの追加
lib/Linker と lib/Bitcode が使用する診断インフラストラクチャー
PreserveSourceリンカーモードを除去した。
ガベージコレクション
MIPS向けの改良
Linuxカーネルのコンパイル(LLVMLinuxプロジェクト)に対応 (僅かな量のパッチが必要)
PowerPC向けの改良
OCamlのバインディングの変更
gollvmをベースとしたGoのバインディング

LLVM 3.6を用いた外部のプロジェクト

Portable Computing Language (pocl)
TTA-based Co-design Environment (TCE)
Likely ‐ Lispの実装
LDC - the LLVM-based D compiler
LLVMSharp & ClangSharp

LLVM 3.5

全てのバックエンドでマシンコード(MC)サブシステムを使用するように変更
Linux/Sparc64 と FreeBSD/Sparc64 でのセルフホスティングを達成
アセンブラーから古い機能の削除
インラインアセンブリは、統合されたアセンブラーで解析するよう変更
ループベクタライザーヒントメタデータのプレフィックスを llvm.vectorizer から llvm.loop.vectorize に変更し、また llvm.vectorizer.unroll メタデータは llvm.loop.interleave.count に名前を変更
いくつかのバックエンドで、従来実装された x & ~y のようなアトミックNAND(x,y)を、全てのバックエンドで ~(x & y) とした。これによりGCC 4.4以降のセマンティクスと一致した

LLVM 3.4

clang 3.4でC++14完全対応
新しい「SLPベクタライザー」がデフォルトで有効化された
MIPS対応の拡充
PowerPC対応の拡充
SPARC対応の拡充
z/Architecture対応の拡充

LLVM 3.3

改良点

AArch64への対応を開始(開発中)
MIPS対応の拡充
PowerPC対応の拡充
ループの最適化「ループベクタライザー」の改善
ベクトル化の改善による最適化「SLPベクタライザー」を搭載
R600バックエンドの追加で、AMDのGPU(HD2xxx ‐ HD7xxx)に対応
IBMのz/Architectureに暫定対応するバックエンドのの追加

補足

CellSPUへの対応は削除された
古いHexagonへの対応が削除された。この版はhexagonv4とhexagonv5のみに対応している。

LLVM 3.2

改良点

ループベクトル化(Loop Vectorizer)
SROA(Scalar Replacement Of Aggregates)の新実装
NVIDIAのソースをベースとした新しいNVPTXバックエンド(既存のPTXバックエンドの置き換え)

LLVM IRの改良
　LLVM IR(中間表現)は新たなターゲットへの対応のため、新機能が追加された。

スレッドローカル変数が特定のTLSモデルを持つことが可能となった。
古い関数属性形式のための、'TYPE_CODE_FUNCTION_OLD'タイプコードとautoupgradeコードを削除した。
Attributeクラスの内部表現を、LLVMContextオブジェクトに格納されている一意化されたopaqueオブジェクトへのポインターに変換する。このためAttributeクラスは、opaqueオブジェクトの薄いラッパーとなる。

コード生成器
　X86-32とX86-64ターゲットでは、AVX2向けのコード最適化などの改良がなされた。
　ARMターゲットでは、Apple A6 'Swift' CPU向けのサポートと性能改善がなされた。
　今回は、MIPSターゲットとPowerPCターゲットの改良が多く、さらにPTX/NVPTXターゲットについては書き直された。

LLVM 3.1

改良点
　LLVM 3.1で、多くの改良が施された。

AddressSanitizer ‐ C/C++向けの高速なメモリーエラー検出
MachineInstr Bundles ‐ インストラクションシーケンスのモデルをサポート
ARMアセンブラーの統合
コードジェネレータのブロック配置やコードレイアウトアルゴリズムの追加
LLVM IR(Intermediate Representation)の改良
マシンコード(MC)サブシステムの改良

LLVM IRの改良
　LLVM IR(中間表現)は新たなターゲットへの対応のため、新機能が追加された。

16ビットの半精度浮動小数点
ベクターGEP(GetElementPtr)を含む、ポインターのベクターに対応
モジュールフラグの導入　LLVMサブシステムに対してモジュール情報を送る際に使われる。
　現時点では、Objective-CのABI情報のエンコードに用いられている。
メタデータを持つ機能
The llvm.ctlzとllvm.cttzは、ゼロ入力に対して未定義かどうかを示す追加引数を持つようになった　これにより、型のサイズを返さない命令を持つプラットフォーム上で、0のビットを数える際に最適化されたコードが生成可能となる。

コード生成器
　最終段で、実際にコードを生成するコード生成器が大幅に改善され、VLIWアーキテクチャー用のビルドに対応するための基盤が搭載された。まずはHexagonをターゲットとして実装されている。
　X86ターゲット、ARMターゲット、MIPSターゲット、PTXターゲットなど様々なターゲット向けの処理が改善された。

X86ターゲットの改良
　ARMなどへの対応も注目されているが、x86への対応も大幅に改良されている。

AVX2対応の大幅な改良
AVX1の改善と多くのバグ修正
FMA4とXOP命令セット拡張への対応
高速コンパイルと異なる呼び出し規約への対応のため、CALL命令は新しいレジスターマスクを用いる
DW2例外処理は、CygwinとMinGWで有効化されている
MSVCランタイムで使用されている暗黙的なTLSモデルに対応した

ARMターゲットの改良
　ARMターゲットの新機能は以下のとおりである。

constant island passは、基本ブロックと、4バイトを超えるアラインメントのconstant pool entryに対応
Darwinで、ARMターゲットの完全機能の統合アセンブラーが搭載された　A32とT32(Thumb-1とThumb-2命令)に完全対応。
　CPU拡張命令として、VFPv2、VFPv3、NEONに対応している。

再検索