中間言語の一般的な話

中間言語の一般的な話

最近のコンパイラの目的は、入力言語から出力言語へ変換することらしいです。

古典的なコンパイラの最終的目的は、プログラミング言語->アセンブラ言語に変換することです。
中間言語(中間表現)とは、コンパイラ独自の内部表現を指します。
多くのコンパイラは、プログラミング言語から、コンパイラ固有の中間言語に変換し、その中間言語をアセンブラ言語に変換します。

JITコンパイラは、大部分がSSA形式を採用している。
個人的に、SSA形式は伝統的なループ最適化が行い難い。

LLVM


GCC

プログラミング言語->AST->Generic->Gimple->SSAGimple->RTL->アセンブラ言語

JVM

JVMにもいろいろらしい

OpenJDK(Sun|OracleJVMと読み替えてもよいです。)

JavaCCは、bytecodeという中間言語に変換するコンパイラであり、
JVMのJITコンパイラは、bytecodeをメソッド単位でターゲットアセンブラへ変換するコンパイラである。
OpenJDKは、クライアントコンパイラ(C1コンパイラ)とサーバコンパイラ(C2コンパイラ)を持つ。

JavaCC

Java->bytecode

C1コンパイラ

bytecode->HIR->LIR->アセンブラ言語

HIRは、SSA形式で、1bytecodeに対して1HIRくらいの粒度
HIRレベルで脱仮想化、inline展開、GVN等の最適化を行い、これらで性能の大部分が決まる。
ループ|機能変数の最適化は行わない。

LIRは、アセンブラ言語とほぼ1:1くらいの粒度
LIRの段階でPHINodeの逆変換を行い、仮想レジスタに対してLinerScanでレジスタ割り付けを行う。
マシン固有の情報や、callingconvensionの情報を使用する。

C2コンパイラ

bytecode->Ideal->機種依存Ideal->アセンブラ言語

Idealは、HIRに近いMIR。
粒度が小さく、四つ組というより、DFDベースの木構造の中間言語である。
SSA形式。
いろんな最適化を行うが、大部分はSSA形式の最適化アルゴリズムを採用。
Idealをシリアライズしようとすると、llvmのbitcodeになるのかもしれない。

IBMのJDK


Java(およびJVMで動作するプログラミング言語)->ByteCode->Quad(四つ組)->DAG(Directed acyclic graph)->Quad(四つ組)->アセンブラ言語

Android4.0 ICSのJITコンパイラ


dex->SSA形式のHIR->機種依存のLIR->Assembler(ARM or x86/x64)

V8 Crankshaft JITコンパイラ


JavaScriptのAST->Hydrogen(high-levelなIR、SSA形式)->Lithium(low-levelなIRで機種依存、三つ組)->Assembler(x86 or x64 or ARM or Mips)


よくある構成

 構文木->抽象構文木->高レベル中間言語->低レベル中間言語->ターゲットマシン依存の中間言語->アセンブラ

中間言語の粒度は次第に小さくなり、各レイヤーで何の情報を保持し、何を抽象化しているのかは大事なことだと思う。

抽象構文木

プログラミング言語固有の構造であることが多い。
プログラミング言語中での構文レベルの差異は吸収され、意味レベルで共通化される。

高レベル中間言語

プログラミング言語の細かい仕様からは独立しており、ある程度抽象化された構造になっている。
制御フローやデータフロー、コンテキスト情報を保持している。
高度な最適化の対象になる。

低レベル中間言語

プログラミング言語から完全に独立している。またターゲットアーキテクチャからも完全に独立している。
制御フローやデータフローが抽象化されている。
制御のループ、ステートメントなんかは粒度の小さい命令に細分化され、全部基本ブロックとgotoになってたりする。

上記情報はボトムアップで再解析してオンデマンドで情報を提供する。
もしくは専用の中間言語に再変換し、解析、最適化を行い、元の中間言語に戻す。
各種フローをグラフで表現したDAG形式に変換し、パターンマッチやグラフベースのヒューリスティックアルゴリズムを使用したり、
ループと依存解析に特化した構造に変換し、別名解析、依存解析、ループネストの最適化を行ったりする。

ターゲットマシン依存の中間言語

ターゲットマシンに依存した中間言語で、ターゲットマシン依存の最適化(命令選択、命令スケジューリング、レジスタ割り当て)なんかを担当する。
アセンブラに変換しやすいように、3番地コードや2番地コード形式が多い。


グラフは重要

コンパイラにおいて、グラフはよく使われる。

control flow graph や call graph や レジスタのグラフ彩色 なんかでよく会う。
DAGもよく使われる。特にデータフローなんかで
DAGにはループがないが、DAGの集合がループになりえたり、ループをDAGの1つの要素としたりする。



@todo
ocamlとかghcもやりたい。


  • 最終更新:2011-12-01 22:21:15

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

認証パスワード