LLVMの中間言語

LLVMおよび周辺ツールは、中間言語を幾つも内包し、
それぞれの中間言語を高レベルな中間言語から低レベルな中間言語に順に変換する。
LLVMの特長は、BitCodeの完全な仕様が公開されているため、BitCodeへの変換機を作れば、LLVMの資産を活用できる。
※ライセンスもGNUではなく、apacheライクなので、企業にも優しい。

AST

clangはプログラミング言語を字句・構文解析し、clang固有の抽象構文木(Abstract Syntax Tree)に変換する。
ASTはTreeであり、コンテキストを保持し、パターンマッチがしやすい構造になっている。

BitCode

リファレンスも公開されている、LLVMメインの中間言語。
静的単一代入(SSA Static single assignment)形式である。
大規模な変換(最適化)をやりやすく、低コストで解析、変換を行うことができる。
その理由はuse-def連鎖と支配関係の、解析とメンテナンスが容易なため。
ASTで保持していたコンテキストが失われており、プログラミング言語のループ構文が失われている。
パターンマッチがし難い。

SelectionDAG

llc内部で命令選択する際に使われる、無閉路有向グラフDirected acyclic graph型の中間言語。
パターンマッチがしやすく、グラフ構造の部分的な組み換えみたいな変換はしやすい。

MachineInstr

llc内部で使われる、レジスタ割り付けや命令スケジューリング、アセンブラ変換用の中間言語。
3番地および2番地コードの中間言語。アセンブラに変換しやすい。
BitCodeよりも低レイヤー向けであり、1命令ごとの粒度が小さい。


コンパイルの流れ


  1. clangがソースコードを読み込み、BitCodeを出力する。
    1. 字句解析、構文解析、意味解析を行い、AST形式に変換する。
    2. 要望に応じて、AST形式の解析や付加情報追加を行う。
    3. AST形式からBitCodeへ変換する。
  2. optがBitCodeを読み込み、最適化を行い、BitCodeを出力する。
    1. Moduleレベルの最適化
    2. CallGraphSCCレベルの最適化
    3. Functionレベルの最適化
    4. Loopレベルの最適化
    5. BasicBlockレベルの最適化
  3. llvm-ldがBitCodeを多数読み込む、最適化を行い、1つのBitCodeを出力する。
    1. 一つのModuleにまとめる
    2. Module内で、Link Time Optimizationを行う
  4. llcがBitCodeを読み込み、最適化を行い、アセンブラを出力する。
    1. BitCodeでの最適化および変換の前準備を行う。
    2. BitCodeから抽象SelectionDAG形式に変換する。
      1. 抽象SelectionDAG形式での最適化を行う。
      2. 抽象SelectionDAGから、ターゲットアーキテクチャ向けの具象SelectionDAG形式に変換(Legalize)する。
      3. 具象SelectionDAG形式で、最適化を行う。
      4. 具象SelectionDAG形式で、命令の選択とスケジューリングを行う。
    3. 具象SelectionDAG形式から、MachineInstr形式に変換する。
    4. MachineInstr形式で、最適化を行う。
    5. MachineInstr形式で、レジスタ割り付けを行う。
    6. MachineInstr形式で、関数呼び出しの前後のスタック周りの処理を挿入する。
    7. MachineInstr形式で、最適化を行う。
    8. MachineInstr形式からターゲットアーキテクチャのアセンブラに変換する。

  • 最終更新:2010-12-20 23:40:22

このWIKIを編集するにはパスワード入力が必要です

認証パスワード