COINSの概要

1.1. 目的

COINS (COmpiler INfraStructure)はコンパイラを構成する基本機能のモジュールをすべて備え、それらの組み合わせを変えたり、一部のモジュールを新たに開発するだけで、新しいコンパイラを実現することができる。それらの仕様もプログラムもすべて公開して、自由に使えるようにし,それによって、多くの人に使ってもらえる共通のインフラストラクチャとなることを目的としている。

なお、COINSの概要については、情報処理学会誌のVol.47, No.4(2006年4月号)以降に 「21世紀のコンパイラ道しるべ ・・COINSをベースにして」と題して連載されている。

1.2. COINSの構成

ソース言語に近い表現形式である高水準共通中間表現HIR (High-level Intermediate Representation)、およびマシン語に近い表現形式である低水準中間表現LIR (Low-level Intermediate Representation)を中核として、それらを扱う各種のモジュールからなる(図1-1)。

図1-1 COINSの構成

それらのモジュールとしては、
などがある。これらすべてはJavaでかかれている。

1.3. 新しいコンパイラの構成を容易にするコンパイラ・ドライバ

COINSの標準ドライバはcoins.driver.Driverである。これはCコンパイラの ドライバの形をしているが、多くのオプション指定機能を持ち、それらの オプションを指定することで、種々のコンパイラとして機能する。

たとえば、ターゲットマシンを"x86"と指定し、実行環境をウィンドウズマシン の"cygwin"と指定することで、cygwinで実行されるコードを生成するコンパイラ となる。また、いろいろな最適化機能とその適用順序を指定することによって、 種々の最適化の実験をするコンパイラとすることも出来る。

C言語以外の言語のコンパイラは、この標準ドライバのサブクラスを作ることに よって容易に作成出来る。たとえば、Fortranコンパイラのドライバ coins.driver.F77Driverは標準ドライバのサブクラスであり、フロントエンドを 呼び出す部分をオーバライドしているだけである。それだけで、標準ドライバと 同じオプション指定機能を持ったドライバとなっている。

コンパイル過程の種々の情報を出力するためのオプション指定もある。

1.4. マシン記述によるコード生成

マシン仕様記述をするだけで、コード生成部が自動生成されるので、 新しい機種のコンパイラを作成するのが容易である。

現在、SPARC, x86, ARM, MIPS, SH-4, PowerPCの各マシンのコード生成部が 出来ている。それらのマシンの仕様は、 TMD(Target Machine Description)言語で、 2,000〜4,000行で書かれている。

1.5. 最適化・並列化機能

1.5.1. HIRでの最適化機能

HIRでの最適化機能には
などがある。カッコ内はオプション指定の仕方を示している。 なお、複数個のオプションを指定する時は、"/"で区切ってならべればよい。たとえば、

  hirOpt=cf/cpf/dce

とすれば"cf", "cpf", "dce"がこの順で実行される。

1.5.2. HIRでの並列化機能

HIRでの並列化機能には
などがある。また、これらの結果をOpenMPに対する指示文として付加した Cプログラムの形で出力する機能があるから、 その出力結果を既存のOpenMPコンパイラにかけることに よって並列化コンパイラとして機能することになる。

CoCo(COINS based Coarse-grain Parallelizing Compiler)はそのような 粗粒度並列化コンパイラである。

1.5.3 LIRでのSSA最適化機能

LIRでのSSA最適化機能には
などがある。SSA最適化を指定する場合は、最初にSSA形式への変換を1つ選んで 指定し、最後にLIRへの逆変換を1つ選んで指定し、その間にいくつかの最適化機能 を実施したい順番に並べれば良い。同じ最適化機能を何箇所かで指定しても良い。

1.5.4. LIRでのSIMD並列化機能

インテルx86のMMX/ SSE/ SSE2/ Enhanced 3DNow!の命令やPowerPCのAltiVecの命令、 SPARCのVIS の命令などのような、マルチメディア対応の複雑な SIMD (Single Instruction Multiple Data stream) 命令を目的コード として生成するのがSIMD並列化機能である。

それを実現するために、まず、SIMD命令の仕様を、LIRを拡張したSIRで 厳密に記述した。それらはこれらは、COINSのソースアーカイブの doc-ja/coins/instDesc以下にテスト系や結果と共に置かれている。詳しくは、各記述中のコメントと、README.TXTを参照されたい。

SIMD並列化は、以下のような手順で行われる。

これらの具体的な内容については、「7.2. SIMD並列化」を参照されたい。

なお、C言語などの「汎整数拡張(たとえば、char型のデータでも演算に使う時はint型に拡張する)」の規則を遵守するとSIMD並列化が困難になるので、 遵守しなくても済むデータであるかどうかを判定するアルゴリズムを実装してある。

SIMD並列化はまだ完全な実用化のレベルには達していないが、x86/SSE2については、いくつかの例題について成功しており、gccの5倍以上の性能が得られているものもある。

1.5.5. バックエンドの構成と基本最適化機能

バックエンド基本的な構成は次のようになっている。
コード生成(機種依存な命令列に変換)を行うのは、TMD(マシン記述)ファイル からクラスTmd2Java(TMDコンパイラのようなもの)によって生成されるクラス である。

命令選択に当たっては、TMDファイルには各命令のコストが記載されているので、 そのコストの和が最小になるような命令列をダイナミック・プログラミングで 選択している。

レジスタ割り付けアルゴリズムは、Graph Coloringアルゴリズムの改良型であるGeorge and AppelのIterated Register Coalescingをベースにしている。 さらに、SPARCの浮動小数点レジスタやintel x86のeax/ah,alレジスタを扱うため、ペアレジスタを含むレジスタセットを効率よく割り付けられるよう拡張している。

レジスタに割り付けられない場合のspill候補を選ぶ基準としては、 新たに妨害指数(Disturbance Factor)を使う方法を考案した。 妨害指数とは、その変数の生存範囲において、参照・定義されている変数がいくつあるかを示す数である。

1.5.6. バックエンドの拡張最適化機能

バックエンドでは、バックエンド自体に手を入れずに随所に新たなパスを挿入する 仕掛けが用意されている(8.2. バックエンドの付加機能参照)ので、 それを使って拡張最適化機能を実現することが出来る。

また、バックエンドでは、最初から最後までLIR形式が保たれているので、 その機能をマシン独立な形で記述することも出来る。

現在は、レジスタ割り付け前と後の両方で命令スケジューリングをする機能と、 通常はメモリに割り付けられている大域変数をレジスタに割り付ける、 簡単なレジ スタプロモーションの機能、および、単純なループ(if文や関数呼び出しがないループ) に対するソフトウェア・パイプライニングの機能が実現されている。

1.6. オブジェクト性能

 COINSを使って開発されるコンパイラは性能的にも優れたものになることが期待される。

図1-2と図1-3は、フリーのコンパイラで性能的にも定評のあるgccの最適化レベル2と COINSのCコンパイラとで目的コードの実行時間を比較したものである。 いずれの図もCOINSで最適化を何も指定しない場合の実行時間を1とした相対値で表している。

図1-2は、SPECベンチマークで比較したものであり、マシンはx86 (Pentium 4)である。COINSのバックエンドのレジスタ割り付けとそれに関連した基本最適化だけですでに相当良い性能が出ている。

図1-3は、COINSの持つ各種最適化の効果を、効果が端的に現れる小規模なプログラムで計測したものであり、マシンはSPARC (Sun Blade 1000)である。図1-3で"ssa"は、SSA最適化の11ヶのモジュールを適用した場合であり、"ssa+S+R"は、さらに命令スケジュール、大域変数のレジスタ・プロモーションの最適化も適用した場合である。図1-3の"ssa+S+R"では全体的にgccより良い性能を出している。


図1-2 COINSとgccの実行時間比(x86)


図1-3 COINSとgccの実行時間比(SPARC)

1.7. コンパイル過程の可視化

1.7.1. ソース-HIR-フローグラフ-LIRの対応表示

コンパイルの過程を見やすく表示するツールもいくつか用意されている。 一つは、ソースプログラム、HIR、HIRの制御フローグラフ、LIR、 LIRの制御フローグラフなどの対応をグラフィカルに表示するもので、 CoVisという名前のものである。

図1-4は、ソースプログラムmatmult.cからHIRが生成された時の様子をCoVisで表示したものである。図の左上は制御フローグラフ、左下は制御フローグラフに関する情報、右上はHIR、右下はソースプログラムである。それぞれ赤や青の色のついた部分が 対応している。この図の中央上のボタンが示すように、(1)HIRが生成された時、 (2)HIRでの最適化後、(3)LIRが生成された時、(4)LIRでの最適化後、 の4つの時点でこのような表示をすることが出来る。


図1-4 CoVisによる表示

1.7.2. コード生成過程のトレース表示

コード生成過程はコンパイラでも最も複雑な過程の一つであり、 デバッグにも困難が伴うので、それを助けるための可視化ツールが用意されている。 それは、バッグエンドの随所での変換過程を各種のリンク付きの htmlファイルとして出力するものである。

図1-5は、コード生成過程のトレース表示をしたものである。左の欄にはトレース情報 をとった時点の名前が入っている。右上にはソースプログラム、右下には ある時点でのトレース情報が表示されている。右下の下半分あたりにLIRと マシン命令記述とのパターンマッチングの様子が示されている。 右下の上半分あたりには、そのパターンマッチングの前の時点での ある基本ブロックの中のLIRの列が表示されている。

そこにある[<<]をクリックすると、その基本ブロックが一つ前の時点で どうなっていたかを見ることが出来る。また、[>>]をクリックすると、 その基本ブロックが一つ後の時点でどうなるかを見ることが出来る。


図1-5 コード生成過程のトレース表示