COINSの概要

- 目的
- COINSの構成
- コンパイラ・ドライバ
- マシン記述によるコード生成
- 最適化・並列化機能

- HIRでの最適化機能
- 並列化機能（HIR）
- SSA最適化機能（LIR）
- SIMD並列化機能（LIR）
- バックエンドの構成
- バックエンドの拡張機能

- オブジェクト性能
- コンパイル過程の可視化

- ソース-HIR-フローグラフ-LIR
- コード生成過程のトレース表示

## 1.1. 目的

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

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

## 1.2. COINSの構成

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

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

- 各ソース言語プログラムをHIRに変換するフロントエンド
- HIRからLIRに変換するモジュール
- LIRから各マシン語のプログラムを生成するバックエンド
- HIR/LIR上での最適化・並列化モジュール
- 最適化・並列化の結果をC言語プログラムとして出力するモジュール
- それらを適宜呼び出して一つのコンパイラとして作用させるためのコンパイラ・ドライバ

などがある。これらすべては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)
- 定数伝播 (hirOpt=cpf)
- 無用命令削除 (hirOpt=dce)
- 局所的共通部分式削除 (hirOpt=cse)
- 大域変数の一時変数化 (hirOpt=gt)
- 別名解析（楽観的解析(alias=opt)か悲観的解析（指定のない場合））
- 部分冗長性削除 (hirOpt=pre)
- ループ展開 (hirOpt=loopexp)
- インライン展開 (hirOpt=inline)

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

hirOpt=cf/cpf/dce

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

### 1.5.2. HIRでの並列化機能

HIRでの並列化機能には

- ループ内の各変数、配列要素のループ繰り返しを考慮したデータフロー解析
- ループ並列化変換（帰納変数の変換、private化、reduction検出）
- ループのdo-all型並列化可能性判定
- プログラムの粗粒度タスクへの分割
- 粗粒度タスク実行の動的スケジューラ

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

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

### 1.5.3 LIRでのSSA最適化機能

LIRでのSSA最適化機能には

- LIRからSSA形式への変換３種類
  - 最小SSAへの変換（ssa-opt=mini）
  - 半ば刈り込んだSSAへの変換（ssa-opt=semi）
  - 刈り込んだSSA への変換（ssa-opt=prun）
- SSA形式からLIRへの逆変換４種類
  - Briggsの方法（ssa-opt=brig）
  - Sreedharの方法I（ssa-opt=srd1）
  - Sreedharの方法II（ssa-opt=srd2）
  - Sreedharの方法III（ssa-opt=srd3）
- コピー伝播（ssa-opt=cpyp）
- 共通部分式削除（ssa-opt=cse）
- 条件分岐を考慮した定数畳み込みと定数伝播（ssa-opt=cstp）
- 無用命令削除（ssa-opt=dce）
- 複雑な演算の展開（代入の右辺の演算子は１つだけとする）（ssa-opt=divex）
- ループ不変コードの巻き上げ（ssa-opt=hli）
- 演算の強さの軽減とテスト置換（ssa-opt=osr）
- 質問伝播による部分冗長性削除（ssa-opt=preqp）

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

### 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のソースアーカイブの ｄoc-ja/coins/instDesc以下にテスト系や結果と共に置かれている。詳しくは、各記述中のコメントと、README.TXTを参照されたい。

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

- IF変換を行い、分岐命令のない形にする。
- 基本ブロックをDAG(Directed Acyclic Graph)形式に変換する。
- 各DAGを基本操作BOP(Basic Order Pattern)に分解する。
- Bone（後述）に従って複数のBOPをまとめてPARALLEL式を作り、生成するSIMD命令を組み立てる。
- まとめられた表現に対して長レジスタを割り当てる。

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

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

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

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

バックエンド基本的な構成は次のようになっている。

- 内部LIR表現から制御フローグラフへの変換
- 各種解析を行い、解析データを抽出する
- 最適化・プログラム変形
- 機種依存な命令列に変換
- レジスタ割付を行う
- アセンブリ言語に変換

コード生成（機種依存な命令列に変換）を行うのは、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の最適化レベル２と COINSのCコンパイラとで目的コードの実行時間を比較したものである。 いずれの図もCOINSで最適化を何も指定しない場合の実行時間を１とした相対値で表している。

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

図1-3は、COINSの持つ各種最適化の効果を、効果が端的に現れる小規模なプログラムで計測したものであり、マシンはSPARC (Sun Blade 1000)である。図1-3で"ssa"は、SSA最適化の１１ヶのモジュールを適用した場合であり、"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、右下はソースプログラムである。それぞれ赤や青の色のついた部分が 対応している。この図の中央上のボタンが示すように、（１）HIRが生成された時、 （２）HIRでの最適化後、（３）LIRが生成された時、（４）LIRでの最適化後、 の４つの時点でこのような表示をすることが出来る。

図1-4 CoVisによる表示

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

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

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

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

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