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)。

COINSの構成図
図1-1 COINSの構成

それらのモジュールとしては、

などがある。これらすべてはJavaでかかれている。

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

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

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

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

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

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

マシン仕様記述をするだけで、コード生成部が自動生成されるので、

新しい機種のコンパイラを作成するのが容易である。

現在、SPARC, x86, x86_64(x86の64ビットモード), ARM, MIPS, SH-4, PowerPC, Alpha, MicroBlaze, Thumb(ARMの16ビット命令系) の各マシンのコード生成部が 出来ている。それらのマシンの仕様は、 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のウェブページの プロセッサーレベル並列化に関する研究 にある「SIMD命令の詳細仕様」のページに テスト系や結果と共に置かれている。詳しくは、各記述中のコメントと、 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. バックエンドの拡張最適化機能

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

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

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

1.6. オブジェクト性能

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

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

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

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

図1-3は、COINSの持つ各種最適化の効果を、効果が端的に現れる小規模なプログラムで 計測したものであり、マシンはSPARC (Sun Blade 1000)である。図1-3で、COINS 0 は最適化を何も指定しない場合、COINS 1はSSA最適化を適用した場合、COINS 2は SSA最適化、命令スケジュール、ソフトウェア・パイプライニング、 大域変数のレジスタ・プロモーションの最適化も適用した場合である。 COINS 2では全体的にgccより良い性能を出している。

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

各プログラムとオプション指定は以下のものである。

ここで、"schedule"は命令スケジューリング、"pipelining"はソフトウェア・パイ プライニング、 "regpromote"は大域static変数のレジスタ・プロモーションである。

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

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

もう一つは、コンパイラの内部情報をテキスト形式で表示するもので、 コンパイラの機能l拡張や改良を行うときのデバッグ支援だけでなく、 コンパイラにおける処理内容を理解するのにも役立つ。 それについてはコンパイラのオプション説明の項 コンパイル過程の情報出力 で説明する。

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

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

CoVis図
図1-4 CoVisによる表示

1.7.2. SSAグラフの表示

SSA最適化のosr(operator strength reduction)では, SSAグラフを作成して,その上で演算の強さの軽減と判定の置き換えを行う. このオプションを指定するためには,

-coins:ssa-opt=...

の中でosrを指定するか,"-O2"以上の最適化指定をすればよい.

その結果作成されたSSAグラフは,

  -coins:trace=default.10000
または
  -coins:trace=SSA.10000

を指定すると,before_ssa_graph.dotとafter_ssa_graph.dot という名前の2つのファイルとして出力される.前者はosr最適化前の SSAグラフであり,後者はosr最適化後のSSAグラフである.

これらをグラフ描画ソフトのgraphvizに与えれば,グラフ表示が得られる.

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

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

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

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

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

1.8. テスト・スーツ

1.8.1. 概要

COINSの一部を変更したり、新しいマシン記述を追加したりしたときに、 Cコンパイラが正常に働くかどうかをテストするためのテスト・スーツ が用意されている。 それはCOINSの"test/c"ディレクトリにあり、約1000個 (COINSのバージョン1.4.1以前は約700個)の小さな Cプログラムからなる。それらは Assign, Exp, If, Loopなどの多くのサブ・ディレクトリに 分けられている。 (testディレクトリにあるREADME.xxxファイルを参照)

これらのディレクトリには、 各テストプログラムをgccで実行した結果を示すファイルも 入っており、それを使って自動テストをする スクリプトも用意されている。

ただし、自動テストに適さないプログラムもある。 それは、構文エラーをチェックしたり、実装依存の機能をテストする ものであり、 ディレクトリ"test/c/unsupported"と "test/c-result-may-differ"に入っている。

なお、アーカイブファイルの

    doc-en/README.testPrograms.en.txt

も参照されたい。

1.8.2. 自動テスト

自動テストをするためのスクリプトが

test/c/testdriver.sh

である。 これはテスト・スーツの中のプログラムを次々にコンパイル・実行し 期待される結果(gccでの結果)と一致するかをチェックし、 それらの情報をファイルに出力するスクリプトである。

1.8.2.1 Sparcマシンで

以下のようなコマンド列で自動テストをすることが出来る。

cd ./classes   -- COINSのルートディレクトリで、これをタイプする
../test/c/testdriver.sh -v ../test/c/*/*.c

../test/c/testdriver.sh -v ../test/c/*/*/*.c

最初のtestdriver.shの呼び出しにより、../test/cの直下の サブディレクトリにあるテストプログラムがテストされ、 次の呼び出しでは、もう1段下のサブディレクトリにあるものがテストされる。

テストの結果のファイルは、 COINSのルートディレクトリの直下に作られるディレクトリ

testdriver-yymmdd-hhmmss

の中に作られる。

ファイルtestdriver.shの中には、以下のような行がある。

if ! java coins.driver.Driver -coins:${TARGET}preprocessor=
      'cpp -I../lang/c/include' -S -o $CCCOUT $i &>$CCCLOG

これがCOINSのDriverを呼び出すための行であるから、 この行を書き換えて任意のオプション指定をすることが出来る。

テスト・スーツのある1つのサブディレクトリだけを指定して テストをすることも出来る。たとえば、

../test/c/testdriver.sh -v ../test/c/Loop/*.c

として、Loopに関するテストだけをすることが出来る。

test/c/unsupportedと test/c-result-may-differサブディレクトリ以下のプログラム ではエラーとなる場合があるかも知れないが、それが エラーとなることをチェックするプログラムなら、正常な結果である。

テスト結果が"OK"となっても、さらに調べる必要があるものもある。 たとえばtest/c/Optやtest/c/OptAdd、test/c/TestSsaには最適化をテストする プログラムがあるから、最適化が行われているかどうかをチェックするには 生成されたコードを調べる必要がある。

1.8.2.2 Intel x86 マシンやその他のマシンで

sparcマシン以外でもテスト・スーツを使うためには

../test/c/testdriver.sh -v ../test/c/*/*.c

の代わりに

../test/c/testdriver.sh -v -t x86-cygwin ../test/c/*/*.c

としたり、 testdriver.shの中でDriverを呼び出している行 のオプション指定で、マシンを指定すれば良い。

しかし、cygwinでは、環境によってはtestdriver.shが正常に 働かない場合があるので、 その代わりにcygwin専用に(COINSのバージョン1.4.2以降で)用意してある test/c/testdriverw.sh を使う方が無難である。 使い方はtestdriver.shと同じである。 コンパイラのオプションを変更するには

CLASS="coins.driver.Driver -S -b x86-cygwin

で始まる行で指定すれば良い。

インテルマックの64ビットモードでは、

lang/c/include/samples/*.h
lang/c/include/
にコピーし、testprepare.sh を後述のように変更して実行したあと、 testdriver.sh の292行目の
if ! gcc -lm -o $GCCOUT $CCCOUT &>$GCCLOG
if ! gcc -arch x86_64 -lm -o $GCCOUT $CCCOUT &>$GCCLOG
に変更してテストを行う。そのコマンドは、
../test/c/testdriver.sh -v -t x86_64-mac ../test/c/*/*.c
のようにすればよい。
もし、
"coins.driver.Driver " not found
のようなエラーとなったならば、testdriver.shのjavaコマンドは282行目の
  if ! java coins.driver.Driver -coins:${TARGET}preprocessor=
        'cpp -I../lang/c/include' -S -o $CCCOUT $i &>$CCCLOG
であるので、これを
  if ! java -classpath . coins.driver.Driver -coins:${TARGET}preprocessor=
        'cpp -I../lang/c/include' -S -o $CCCOUT $i &>$CCCLOG
のように変更すればよい。

このように、自動テストのスクリプトは使う機種とその環境に合わせて変更しなければ ならない場合がある。

1.8.3. 期待される結果のデータの更新

1.8.3.1 Sparcマシンで

現在、期待される結果として用意されているデータは、次のコマンドによって sparcのgccで得られたものである。

cd ./classes
../test/c/testprepare.sh ../test/c/*/*.c
../test/c/testprepare.sh ../test/c/*/*/*.c

テストプログラムを変更したり、追加した場合には このコマンドによってデータを更新しておく必要がある。

1.8.3.2 Intel x86マシンや他のマシンで

Sparcマシン以外でテストする場合は、そのマシンの gccコンパイラなどを使って、期待される結果のデータを置き換えておいた方が良い。 マシン依存の機能については、マシンによって結果が違う場合があるからである。

x86-cygwinマシンの場合は、test/c/testpreparew.shを使って 期待される結果のデータを置き換えておいた方が良い。 その使い方はtestdprepare.shと同じである。

インテルマックの64ビットモードでは、testprepare.sh の中の

# compile
  if ! gcc -lm -o $OUT $SRC
# compile
  if ! gcc -arch x86_64 -lm -o $OUT $SRC
に変更して実行する。

その他のマシンについては、おおむねtestprepare.shを使えば良い。