Low Level Virtual Machine

読み：ローレベルバーチャルマシーン
外語：LLVM: Low Level Virtual Machine 英語
品詞：固有名詞

様々なプログラミング言語において、最適化が可能なように設計された、コンパイラーの基盤。

目次

仕様

  • 使用途 ‐ コンパイラー基盤
  • 初出年 ‐ ?
  • 設計者 ‐ ?
  • 開発者 ‐ LLVM Developer Group
  • 最新版 ‐ 3.6 (2015(平成27)年2月27日)
  • 影響関係
    • 被影響 ‐ GCC
    • 加影響 ‐ (不明)
  • 主要動作環境 ‐ クロスプラットフォーム
  • ライセンス ‐ University of Illinois/NCSA Open Source License

概要

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よりも更に低レベルの言語である。

コンパイルの流れ

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

特徴

関連プロジェクト

LLVMを利用したプロジェクトで、公式サイトに記載のあるもの(新しい順)。

  • 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の時点で主たる対応オペレーティングシステムは次の通り(アーキテクチャーごとの対応は後述)。

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

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

  • 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が未対応である。

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に対応している。

関連するリンク
http://llvm.org/
用語の所属
コンパイラー
関連する用語
C
C++
llvm-gcc
clang
libc++
トップへ

広告

コメントなどを投稿するフォームは、日本語対応時のみ表示されます

KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club