9.1 バックエンドの構成

 バックエンドの処理は、以下のような流れでおこなわれる。
  1. ASCII 又はS 式表現のLIR から内部LIR 表現への変換(class Function)
  2. 内部LIR 表現からCFG(Control Flow Graph) への変換(class Function, class FlowGraph)
  3. 各種解析を行い、解析データを抽出する(coins.backend.ana.*)
  4. 最適化・プログラム変形(coins.backend.opt.*)
  5. 機種依存な命令列に変換(coins.backend.TargetMachine)
  6. レジスタ割付を行う(coins.backend.regalo.*)
  7. アセンブリ言語に変換(coins.backend.TargetMachine)

カッコ内の名前は、その処理をするクラス名やパッケージ名である。

4.の最適化としては、分岐命令の最適化・基本ブロック内の定数畳み込みなどを行う。 プログラム変形としては、対象機種に依存するが機械語の生成はともなわない変換作業を行う。 具体的には、CALL、PROLOGUE、 EPILOGUE、JUMPN 等の命令をより単純な命令に分解する。

5.は、コード生成とか命令選択とかいわれる変換である。 COINSのLIRは、4. 低水準中間表現LIRの仕様の 「4.2 設計目標」の

   1. 全バックエンドフェーズを通じて使用できる中間言語

を実現していて、上記の1.〜6.の処理をするプログラムはすべてLIRに対するのものとして書くことが出来るので マシン独立な形となる(扱うデータはマシンごとに異なる)。

たとえば、5.の命令選択をして、特定のマシンの機械語が選択されたとしても、それがLIRの形で表現されているし、 さらに、6.のレジスタ割付けをした後でもそれが保たれている。

したがって、マシン語の命令の順序を最適なものに変更する命令スケジューラもマシン独立な形で書くことが出来る。 一般に命令スケジュールとレジスタ割付けとをどのような順序でするのがよいかは、簡単に解決出来る問題ではないが、 上記の特徴を利用して1つの命令スケジューラを書くだけで、レジスタ割付け前に実行する命令スケジューラと レジスタ割付け後に実行する命令スケジューラの両方が実現出来ている。

また、本LIRは、上記の「4.2 設計目標」の

  2. 1つの独立したプログラミング言語であること

を実現しているので、HIRから変換されたs式表現のLIRは1つの完全なLIR言語プログラムと見ることが出来るし、 別の手段で作成されたLIR言語プログラムを読み込むことも出来る。

LIRの内部表現の形は COINS新LIR内部構造 に詳しく書かれている。なお、そこに「新LIR」とあるのは、 COINSの初期の段階で開発したLIRとは違う新しいLIRが現在のLIRであるからである。

バックエンド部の構成について、より詳しくは バックエンド部の実装(pdf) を参照されたい。

なお、情報処理学会誌のVol.47, No.4(2006年4月号)以降に 「21世紀のコンパイラ道しるべ ・・COINSをベースにして」 と題して連載されている記事の6月号、7月号にバックエンド部の解説がある。

9.1.1 リターゲッタブルなコード生成

LIRに対する目的コード列は一般には複数の可能性がある。コード生成では、その中で出来るだけ 効率の良いコード列を選ぶ必要があるので、コード生成はコード選択命令選択とも呼ばれる。 COINSでは、コード生成をリターゲッタブルにするために、LIRのツリーとマシン仕様記述とのパターンマッチング によってコード生成する方式をとっている。

マシン仕様記述は TMD (Target Machine Description) と呼ばれている。TMDには、次のような事項を記述する。

  1. データ型の定義
  2. レジスタの定義
  3. LIRのパタン(L式)と機械命令との対応関係のS式による記述。 それには次の記述も含まれる

機械命令の選択では、ダイナミックプログラミングの方式により、コスト最小のパタンを選択する。 実際には、マッチングアルゴリズムとしては、ボトムアップの木パターンマッチングの一つ、lburg の 実装を採用している。

LIRのパタンとSPARCの機械命令との対応関係は、たとえば次のように書く。

(foreach (@op @code) ((ADD add) (SUB sub) (BAND and) (BOR or) (BXOR xor))
  (defrule regl (@op I32 regl rc)
    (code (@code $1 $2 $0))
    (cost 1)))

これは、LIRのオペレータ@opがADD/SUB/BAND/BOR/BXORのいずれかであれば、 SPARCのadd/sub/and/or/xorの対応するものを@codeとして選び、2行目に書かれた LIRの命令における1番目のレジスタreglと2番目のレジスタreglをそれぞれ$0、$1で表し、 3番目のレジスタまたは定数rcを$2で表すことにして、SPARCではその順序を入れ替え

 @code ,$1 ,$2, $0

という命令として生成すること、その命令コストは1であることを表している。 reglが32ビットのレジスタを表し、rcがレジスタまたは13ビット以下の定数を表すことは、 これに先立つレジスタ定義の項で定義しておく。このように、同じ扱いのできるものをまとめて 記述することにより、簡潔な記述ができるようになっている。

一つのLIR命令から複数の機械語命令(に対応するLIR) が生成される例としては、たとえば、

 (SET I32 (REG I32 "_osrI32_66%0")
           (ADD I32 (LSHS I32
                         (ADD I32 (REG I32 "p.6%_1%0") (REG I32 "_ssaI32_0%0")) 
                         (INTCONST I32 2))
                    (REG I32 "Z.3%_1%0")))

から

(SET I32 (REG I32 ".T4%") 
     (ADD I32 (REG I32 "p.6%_1%0") (REG I32 "_ssaI32_0%0")))
(SET I32 (REG I32 ".T3%")
     (LSHS I32 (REG I32 ".T4%") (INTCONST I32 2)))
(SET I32 (REG I32 "_osrI32_66%0") 
     (ADD I32 (REG I32 ".T3%") (REG I32 "Z.3%_1%0")))

という3命令が生成される。これらはそれぞれ機械語命令に対応しているが、形はLIRの形をしている。

レジスタ割り付け後は、これが

(SET I32 (REG I32 "%i3") 
     (ADD I32 (REG I32 "%i5") (REG I32 "%l1")))
(SET I32 (REG I32 "%i3")
     (LSHS I32 (REG I32 "%i3") (INTCONST I32 2)))
(SET I32 (REG I32 "%l0") 
     (ADD I32 (REG I32 "%i3") (REG I32 "%i2")))

となり、最終的には

  add  %i5, %l1, %i3
  sll  %i3, 2, %i3
  add  %i3, %i2, %l0

という形で出力される。

しかし、すべての命令列がこのように命令記述だけから自動生成されるわけではなく、副プログラムの入り口、 出口の処理などは、TMDの中に記述したJavaの文によって行われる。

バックエンドで機種別に書かなければならない部分はTMDに集約されていて、 その記述行数は表1.2-1のとおりである。gccのマシン記述ファイルMDはこの約3倍である。 このことからもCOINSはリターゲット性が高いと言えよう。

表1.2-1 マシン仕様の記述量
機種名 TMDの記述行数 工数 ファイル名
総行数 内Java行数
SPARC 1,949 802 不明 sparc.tmd
X86 2,391 985 不明 x86.tmd
ARM 3,052 2,176 6人月 arm.tmd
MIPS 2,081 1,379 3人月 mips.tmd
SH4 3,568 2,467 6人月 sh4.tmd
PowerPC 5,016 2,913 6人月 ppc.tmd

SPARCとX86の工数が不明となっているのは、この2つを主たるターゲットとして開発しており、 TMDやCodeGeneratorの設計・開発の並行して開発されて来たためである。工数の「人月」 は複数人によるものではなく、1人での月数である。MIPS, SH4, PowerPCは、いずれも 電通大での卒業研究として行われたものである。

表9.1-1の各tmdファイルはCOINSのソースアーカイブの src/coins/backend/gen/に入っている。 実際にパターンマッチングに使われるのは、これらのファイルからクラスTmd2Javaによって 生成されるCodeGenerator_sparc.java, CodeGenerator_v86.javaなどである。

なお、COINSのソースアーカイブのsrc/coins/backend/tmd/にもsparc.tmdなどという 名前のファイルがあるが、これらは、当初schemeで実装していたときのものであり、現在は 使われていない。現在はJavaで実装されている。

9.1.2 マシン記述TMD

TMDはTarget Machine Descriptionの略で、ターゲットCPUの特性を記述するものである。 以下に、記述すべき項目を順に解説する。

9.1.2.1 データ型とレジスタの定義

データ型の定義

アドレスを表現するデータ型と、TSTxx命令の演算結果のデータ型を定義する。 たとえば、

(def *type-address* I32)
(def *type-bool* I32)

で、アドレスを表現するデータ型も、テスト命令の演算結果のデータ型もI32であることを定義する。

レジスタリストの定義

ターゲットCPUがどんなレジスタを持っているかを書く。これは次の形式を用いる。 この例ではSPARCのレジスタリストを定義している。

(def *real-reg-symtab*
     (SYMTAB
	("%g0" REG I32 4 0)
		:
	("%g7" REG I32 4 0)
	("%l0" REG I32 4 0)
		:
	("%l7" REG I32 4 0)
	("%o0" REG I32 4 0)
		:
	("%o6" REG I32 4 0)
	("%i0" REG I32 4 0)
		:
	("%i6" REG I32 4 0)
	("%f0" REG F64 8 0)
		:
	("%sp" REG I32 4 0)
	("%fp" REG I32 4 0)))

def の第一引数には*real-reg-symtab*を指定しているが、これはTMDで定めている 識別子であり、この通りに記述しなければならない

この記述はLIRの記号表の形式に従っており、そのままL-moduleのグローバルな記号表に挿入される。 なお、レジスタの名前は、かならず%で始まらなくてはならない。これはコンパイラが記号表の中で他の記号 との区別をするために必要である。ターゲットCPUのアセンブラが別の記号を使っていたとしても、 ここでは%をつけておき、実際にアセンブラに落とす際に変換しなくてはならない。

レジスタ集合の定義

以下の形でレジスタ集合を定義する。

(def *reg-I32* (
     (REG I32 "%i0")
     (REG I32 "%i1")
     (REG I32 "%i2")
           :
     (REG I32 "%i6")
     (REG I32 "%o0")
           :
     (REG I32 "%o6")
     (REG I32 "%l0")
           :
     (REG I32 "%l7")))

ここで*reg-I32*というのはこのレジスタ集合の名前で、後で集合を引用するときに使われる。 名前は*reg-で始まる必要がある。レジスタ集合はいくつでも定義できる。 この例では、32 ビットの整数レジスタの集合を“*reg-I32*” という名前で定義している

sparc.tmdの実際の記述では、foreachマクロの機能を使って 以下のように簡潔に書かれている。

(def *reg-I32* ( (foreach @io (i o)
		   (foreach @n (0 1 2 3 4 5)
		      (REG I32 "%@io@n")))
		 (foreach @n (0 1 2 3 4 5 6 7)
		    (REG I32 "%l@n"))
		 (foreach @n (2 3 4 5 6 7)
		    (REG I32 "%g@n")) ))

レジスタ非終端記号の定義

ここでは、後で説明する文法規則の中で使用されるレジスタを表す非終端記号 (nonterminal symbol)を定義する。 レジスタ非終端記号はdefregset 構文で定義される。

(defregset regl *reg-I32*)
(defregset regh *reg-I16*)
(defregset regb *reg-I8*)

defregsetの第1引数が非終端記号であり、第2引数はレジスタ集合である。 defregsetで定義された非終端記号には、バックエンドによってレジスタが一つ割当てられる。 それが左辺に現われる規則は、計算の結果がレジスタに入ることを意味する。

第2引数は、その非終端記号に割当てられるデフォルトのレジスタ集合である。 文法規則中のregset属性でoverrideされない限りは、このレジスタ集合がとられ、 このレジスタ集合の内からレジスタが選ばれて割当てられる。

変数のデフォルトレジスタ集合

(演算の中間結果でない)レジスタ変数に対するレジスタ集合をdefregsetvar構文により定義する。

(defregsetvar
  (I32 *reg-I32*) (I16 *reg-I16*) (I8 *reg-I8*)
  (F64 *reg-F64*) (F32 *reg-F32*))

上記のように、型とレジスタ変数の対を列挙することにより、 その型の変数がこのレジスタ集合から割当てられることを定義する。

被呼側保存レジスタ集合の定義

以下の形で被呼側保存レジスタ集合(callee-save registers)を定義する。SPARCマシンの場合は、関数の入口と 出口でレジスタウィンドウを切り替えるので、これを定義する必要はない。以下はx86の場合の例である。

(def *reg-callee-saves*
     ((REG I32 "%ebx")
      (REG I32 "%esi")
      (REG I32 "%edi")))

関数の入口/出口では、その関数内で使われた(破壊された)レジスタのうち、被呼側保存レジスタ集合 に含まれるものだけを保存/回復すれば良い。保存/回復すべきレジスタの情報は、関数fについて

SaveRegisters save = (SaveRegisters)f.require(SaveRegisters.analyzer);
によって求められる。

9.1.2.2 LIRとマシン命令の対応関係の記述

LIRとマシン命令の対応関係は文脈自由文法の形で記述する。

開始記号の定義

文脈自由文法の開始記号はdefstart構文で定義する。
(defstart void)

上の例では、voidという非終端記号が開始記号となる。すべてのL式は、 最終的に開始記号に還元されるように規則を書かなくてはならない。

還元規則とコード生成例

文脈自由文法の還元規則(文脈自由文法では、通常は生成規則と呼ばれるが、 ここではもっぱら還元のために 使われるので還元規則と呼ぶ)はdefrule構文で記述する。 defrule構文は、命令もしくは命令の一部(アドレッシングモード等)とL式の対応付けを定義する。

CodeGeneratorは、入力L式の一部をdefrule中の右辺のパターンと照合し、マッチする規則をみつけて、 そのrule中のcode属性で指定された命令列に置きかえる。

たとえば、sparc.tmdには以下のようなrule群が与えられている。

 1: (defregset regl *reg-I32*)  ;; Default register set for each nonterminals.
 2: (defrule xregl (REG I32))   ;; レジスタを表す非終端記号(左辺値:後の説明参照)
 3: (defrule regl xregl)    ;; レジスタを表す非終端記号(右辺値)
 4: (defrule addr regl)    ;; ロード、ストアで使えるアドレッシングモードを表す非終端記号
 5: (defrule rc regl)     ;; レジスタまたは小さい整定数を表す非終端記号
 6: (defrule sta (STATIC I32))  ;; static変数のアドレスを表す非終端記号
 7: (defrule asmcon sta)    ;; 整定数を表す非終端記号
 8: (defrule regl asmcon
      (code (_set $1 $0))
      (cost 2))
 9: (defrule regl (ADD I32 regl rc)
      (code (add $1 $2 $0))
      (cost 1)))
10: (defrule regl (MEM I32 addr)
      (code (ld (mem $1) $0))
      (cost 1)))

左端の数字は、以下の説明のために付けたルール番号である。 defrule の第1引数はこの還元規則の還元先である。第2引数にはL 式を記述する。入力L 式がこ のL 式とマッチしたとき、code 属性があればそこに記述されたターゲットコードが出力される。

この例で、次のソースプログラム

int x;
int func(int y){
  return x+y;
}
の"x+y"から得られるL式
(SET I32 (REG I32 "returnvalue.2%0")
         (ADD I32 (MEM I32 (STATIC I32 "x")) (REG I32 "y.1%0")))

に対してマッチングを行うと、以下のようになる。(これを出力する方法は 9.1.4 バックエンド部の使い方を参照されたい。)

*195: regl -> (ADD I32 regl rc) [dest=(REG I32 "returnvalue.2%0")] SU=1  ;; 9
  *60: regl -> (MEM I32 addr) [dest=(REG I32 ".T1%")] SU=1  ;; 10
    19: addr -> regl SU=0  ;; 4
      *44: regl -> asmcon [dest=(REG I32 ".T2%")] SU=1  ;; 8
        29: asmcon -> sta SU=0  ;; 7
          27: sta -> (STATIC I32) SU=0  ;; 6
  35: rc -> regl SU=0  ;; 5
    *15: regl -> xregl [dest=(REG I32 "y.1%0")] SU=0  ;; 3
      5: xregl -> (REG I32) SU=0  ;; 2

ここで、左端に付いている数字は、sparc.tmdから生成されるクラス CodeGenerator_sparc.javaの中で対応するルールに付けられている番号であり、 右端の数字は、上記で説明のためにつけたルール番号である。 また、左端の"*"は対応するルールがcode属性を持っているか、または 左辺が1番目のルールのように、defregsetで定義されたレジスタクラスであるもの (その左辺にはレジスタが割り当てられる)についている。 変換した結果の出力は"*"の付いたものから得られる。

2番のルールは

(REG I32 ..)
という形の任意のL式にマッチし、6番のルールは
(STATIC I32 ..)

という形の任意のL式にマッチする。それらのルールで還元されたときの左辺の値は マッチしたL式である。

reglのような、レジスタを表す非終端記号に還元される場合に、その還元規則(defrule)が code属性を持つ(コードが生成される)ときは、左辺には レジスタがアサインされる。上記のルール8,9,10がそれに相当する。たとえば、 [dest=(REG I32 ".T2%")] は、左辺のreglにアサインされたレジスタ である。右辺もレジスタである場合は、右辺のレジスタが左辺にアサインされる。

このマッチングの結果、このL式は次のように変換される。 なお、マッチしたツリーからL式を生成するときは、実際に必要とされるレジスタが少なく なるような順序で生成している(Sethi-Ullmanの方法)。 上記のマッチングの図で、"SU"がその必要レジスタの数を示しているが、 その数の大きな方の枝から先に生成している。(3行目のマッチングは、コード生成には 直接かかわらないので、"SU"の値は正確には表現せず、0になっている。)

    (SET I32 (REG I32 ".T2%") (STATIC I32 "x"))
    (SET I32 (REG I32 ".T1%") (MEM I32 (REG I32 ".T2%")))
    (SET I32 (REG I32 "returnvalue.2%0") (ADD I32 (REG I32 ".T1%") (REG I32 "y.1%0")))
レジスタ割り付けの結果、このL式は次のように変換される。
    (SET I32 (REG I32 "%i1") (STATIC I32 "x"))
    (SET I32 (REG I32 "%i1") (MEM I32 (REG I32 "%i1")))
    (SET I32 (REG I32 "%i0") (ADD I32 (REG I32 "%i1") (REG I32 "%i0")))
最後のコード生成では、もう一度ツリーのパターンマッチングが行われ、以下のコードが生成される。
    (sethi (%hi x) %i1)
    (or %i1 (%lo x) %i1)
    (ld (mem %i1) %i1)
    (add %i1 %i0 %i0)
ここで、最初の2つの命令は8番のルールの
  (code (_set $1 $0))
によって生成される。この_set はマクロの名前であり、
%defbuild(_set x y) {
  return ImList.list
    (ImList.list("sethi", ImList.list("%hi", x), y),
     ImList.list("or", y, ImList.list("%lo", x), y));
}

のように定義されている。この、%defbuildについては、 %defbuildマクロと%defemitマクロで説明する。

最後にアセンブラ・ファイルに出力されるときは、以下のコードになる。

	sethi	%hi(x),%i1
	or	%i1,%lo(x),%i1
	ld	[%i1],%i1
	add	%i1,%i0,%i0
左辺値xreglの説明
LIRのMEM式は、以下のように二通りの意味を持っている。
   (SET t (REG I32 "v") (MEM t (REG I32 "p")))
   (SET t (MEM t (REG I32 "p")) some-value-of-type-t)

上のMEM式は、変数pの指すメモリの内容を意味しているのに対し、下のMEM式 は左辺値、すなわちpの指すアドレスそのものを意味している。

今、以下のようなTMDのルールの組を考えみる。

1: (defrule regl (MEM I32 regl)
     (code "copy memory[$1] to $0"))

2: (defrule void (SET I32 (MEM I32 regl) regl)
     (code "copy $2 to memory[$1]")

3: (defrule void (SET I32 regl regl)
     (code "copy $2 to $1"))

4: (defrule regl (REG I32))
これらのルールのもとで、
(SET I32 (MEM I32 (REG I32 "p")) (REG I32 "v"))
は、以下のように誤ったパターンとマッチしてしまう可能性がある。
 3:void <- (SET I32 regl regl)
                    /      \
                   /        \
                  /          \
                 /            \
 1:regl <- (MEM I32 regl)    4:regl <- (REG I32 "v")
                |
                |
                |
 4:regl <- (REG I32 "p")
このマッチングの結果、以下のような誤ったコードが生成されてしまう。
  copy memory[p] to tempreg1
  copy v to tempreg1
xreglというnonterminalを導入し、 以下のようにルールを変更すれば、このような誤ったマッチ ングの可能性はなくなる。
3': (defrule void (SET I32 xregl regl))
4-1: (defrule xregl (REG I32))
4-2: (defrule regl xregl)
このxreglはレジスタ変数の「左辺値」を意味する。これで、「右辺値」にしか 還元されないルール1がSETの左辺に現れる可能性はなくなり、上のようなマッ チングは起こらなくなる。

foreachマクロ

foreachマクロについては、今までも何回か例で説明したが、ここであらためて説明する。 同じような形のものを何回も書かなくてすむようにforeachマクロの機能がある。 たとえば、
  (foreach @x (a b)
    (foo @x))
は展開されて、
  (foo a) (foo b)
になり、
  (foreach (@x @y) ((a 1) (b 2))
    (foo @x @y))
は展開されて、
  (foo a 1) (foo b 2)
になる。前記の9番目のルールは、
(foreach (@op @code) ((ADD add) (SUB sub) (BAND and) (BOR or) (BXOR xor))
  (defrule regl (@op I32 regl rc)
    (code (@code $1 $2 $0))
    (cost 1)))
が展開されたものの一部であり、前記の10番目のルールは
(foreach (@t @code @s) ((I32 ld l) (I16 ldsh h) (I8 ldsb b) (F32 ld f))
  (defrule reg@s (MEM @t addr)
    (code (@code (mem $1) $0))
    (cost 1)))
が展開されたものの一部である。

還元規則defruleの一般形式

defruleの一般形式は以下のようになっている。production-rule以外の属性はすべてoptionalである。

(defrule production-rule
  cond-attr
  code-attr
  value-attr
  regset-attr
  eqreg-attr
  cost-attr
  clobber-attr )

以下、これらの属性について順に解説する。

production rule

production ruleはdefrule中唯一の必須項目で、還元規則を記述するものである。

production-rule ::= lhs pattern
lhs ::= nonterm
pattern ::= S-expression

lhsは、非終端記号(nonterminal-symbol)で、右辺のpatternがこれに還元されることを示す。

patternは単一の非終端記号、もしくは単一のL式の一部を非終端記号で置きかえたものである。

cond属性

cond属性には、この規則を適用するための条件を記述する。

cond-attr ::= (cond condition)
condition ::= quoted-string

conditionは、Javaのboolean式として記述する。式中に$0が現れると、それは今調べているL式のインスタンスに置きかえられる。

例えば、

(defrule smallnumber (INTCONST I32))
  (cond "((LirIconst)$0).value >= 0 && ((LirIconst)$0).value < 256"))

という規則は、0〜255までの整定数にのみマッチする。

ここで、クラスLirIconstは、L式(INTCONST I32 ..)をJavaで表現するための クラスである。このようなクラスはパッケージ coins.backend.lir にある。それらのクラスは抽象クラスLirNodeのサブクラスになっている。

code属性

code属性には、この規則に対応するターゲットCPUの命令列を記述する。

code-attr ::= (code code-sequence...)
code-sequence ::= S-expression

code-sequenceには、1つ以上のアセンブラ命令を記述する。ただし、 生のアセンブラの記法ではなく、S式で記述する。それは、この後で実行される peephole(のぞき穴)最適化を効率よく行うためである。アセンブラの記法に変形するには、 後で述べるdefbuild/defemitマクロを使う。

code属性が省略された場合は、対応する命令がないものと解釈される。

value属性

value属性には、このノードの演算結果の値(それが、この還元規則で還元された左辺の値となる) を表わすS式を定義する。

value-attr ::= (value value-sequence...)
value-sequence ::= S-expression

value-sequenceには、上位のノードがこのノードの演算結果を引用するときに展開されるS式を書く。

例えば、[%r0+%r1]のようなアドレッシングモードが使えるCPUでは、

(defrule address (ADD I32 reg reg) (value (plus $1 $2)))
(defrule mem (MEM I32 address) (value (ind $1)))
(defrule reg mem (code (load $1 $0)))

のように文法を定義しておくと、

(MEM I32 (ADD I32 (REG I32 "x") (REG I32 "y")))

(load (ind (plus %r0 %r1)) %r2)

のような命令に組み立て直され、(plusマクロとindマクロが適切に定義されていれば)最終的に

	load	[%r0+%r1],%r2

のようなアセンブリ言語となる。

value属性が省略された場合は、還元規則の左辺の値は、

と解釈される。

cost属性

cost属性には、この規則(に対応するコード)がどれだけコストのかかる操作かを記述する。

cost-attr ::= (cost number)

numberにはその命令のコストを書く。実行時の速度が問題になる場合は命令の実行時間を書くが、 スペースが問題にある場合はバイト数を書いてもよい。 (最近の拡張版では、両方を書いておくことが出来て、コンパイラ・オプションで 速度優先・スペース優先のどちらかを指定できるようになった。) cost属性が省略されると0とみなされる。

命令記述の文法は多くの場合曖昧なので、同じL式に対して複数のマッチ木が作成できることがしばしばある。 そのさい、このコスト情報を見てベストのマッチを選ぶ。コストがバイト数を示すときは、もっともスペース効率の良い (バイト数の少ない) 命令列が選ばれ、コストが実行時間を示すときはもっともスピード効率のよい(実行時間が短い)命令列が 選ばれることになる。

9.2  バックエンドの付加機能の 「9.2.3. 命令スケジューラ」では、このコストが 命令の実行時間を表すものとして、それに基づいて命令の並列実行性をあげるために 命令を並べ替える、というスケジューリングを行っている。 そのために、現在のsparc.tmdでは実行時間が加味されている。 なお、その命令スケジューラでは、命令の中にメモリからのロードが含まれている場合は、 実行時間を別途推測するようになっている。

regset属性

regset属性には、左辺lhsや右辺pattern中に現われるレジスタを示す非終端記号が、 どのレジスタ集合に属するかを記述する。

regset-attr ::= (regset ($n regset-name) ...)

以下の例では、除算命令において、被除数($1)は%eax、除数($2)は%eax,%ebx,%ecx,%esi,%edi のいずれかが割当てられる。

(def *reg-mod$2-I32* ( (REG I32 "%eax")
		       (REG I32 "%ecx")
		       (REG I32 "%ebx")
		       (REG I32 "%esi")
		       (REG I32 "%edi") ))

(defrule regl (DIVS I32 regl regl)
  (eqreg $1 $0)
  (regset ($0 *reg-eax-I32*)
	  ($2 *reg-mod$2-I32*) ...)

regsetが省略された場合は、defregsetで指定されたデフォルトのレジスタ集合から割当てられる。

eqreg属性

eqreg属性は、2つの非終端記号に同じレジスタを割当てることを指定する。現在の実装で指定できるのは、 左辺(lhs)のレジスタと右辺(pattern)中のレジスタとのペアに限定されている。

eqreg-attr ::= (eqreg ($n $0) ...)

$nは、右辺中に現れるn番目の非終端記号を意味する。 その非終端記号はレジスタ名(defregsetで宣言された名前)でなくてはならない。

clobber属性

clobber属性には、この命令が破壊する実レジスタを記述する。

clobber-attr ::= (clobber realregister...)
realregister ::= (REG type quoted-string)

clobberで指定したレジスタは、L式中にCLOBBER式の形で挿入される。

clobberはCALL命令の記述に用いられることが多い。

書き換え規則defrewrite

EPILOGUEやPROLOGUEのように、すこし抽象的に表現されているLIRを ターゲットマシンに合わせて具体化する変換規則を書くのが defrewriteである。

たとえば、前出の例

int x;
int func(int y){
  return x+y;
}
から、最初に得られるLIRは
  (PROLOGUE (0 0) (MEM I32 (FRAME I32 "y.1")))
   (DEFLABEL "_lab1")
    (SET I32 (MEM I32 (FRAME I32 "returnvalue.2"))
            (ADD I32 (MEM I32 (STATIC I32 "x")) (MEM I32 (FRAME I32 "y.1"))))
    (JUMP (LABEL I32 "_epilogue"))
   (DEFLABEL "_epilogue")
    (EPILOGUE (0 0) (MEM I32 (FRAME I32 "returnvalue.2")))
であり、PROLOGUEでは"y.1"が仮引数であることが示されている。 ターゲットマシンがsparcであるときは、そのcalling conventionに合わせて、これを 次のように変換する必要がある。
    (PROLOGUE (0 0) (REG I32 "%i0"))
    (SET I32 (REG I32 "y.1%0") (REG I32 "%i0"))
その変換はsparc.tmdの中で次のように記述されている。
(defrewrite (PROLOGUE)
  (to (norescan (eval "rewritePrologue($0, post)")))
  (phase late))
ここで、
(defrewrite pattern (to new-pattern))

の形で、patternにマッチしたLIRサブツリーを new-patternに置き換えることを指示している。 上の例では、PROLOGUEのノードがrewritePrologue($0, post) の結果で置き換えられる。

pattern 中にnonterminalで書かれた部分は、new-pattern中で$1,$2...の形式 で引用することが出来る。$0はマッチしたサブツリー全体を意味する。 デフォルトでは、変換後の新しいLIRはもういちどマッチングの対象となり 何度でも変換される。しかし、上記の例のように、norescanが指定されていると二度と変換されなく なる。 PROLOGUE命令は、変換した後もPROLOGUE命令のままなので、この指定がないと 何度でも上のマッチングを繰り返して停止しなくなる。

phaseは、バックエンドの変換フェーズ(9.2  バックエンドの付加機能 の「9.2.1 バックエンドの呼び出しかた」参照) のどこでこの変換を行うかの指定である。lateLateRewritingのフェーズを指定する。 earlylateが基本であり、それが指定 されているとそのフェーズ(EarlyRewritingLateRewriting)でのみこの変換を行う。 phase指定がないと、全フェーズで毎回実行される。

evalは文字列中のJavaコード を実行し、そのreturn valueと置きかえよという指令である。 pre, postはマッチングに渡される変数で、前の命令列、後の命令列を意味する。 上の例では、

(PROLOGUE (0 0) (MEM I32 (FRAME I32 "y.1")))
(PROLOGUE (0 0) (REG I32 "%i0"))
で置き換えられ、後の命令列に
(SET I32 (REG I32 "y.1%0") (REG I32 "%i0"))

が加えられている。

rewritePrologue($0, post)で実行されるメソッドの書き方については、 次の節「Javaによる記述」を参照されたい。

同じように、

(defrewrite (EPILOGUE)
  (to (norescan (eval "rewriteEpilogue($0, pre)")))
  (phase late))
によって、
 (EPILOGUE (0 0) (MEM I32 (FRAME I32 "returnvalue.2")))
 (SET I32 (REG I32 "%i0") (REG I32 "returnvalue.2%0"))
 (EPILOGUE (0 0) (REG I32 "%i0"))
に変換される。

tmd記述とバックエンドの各フェーズの関係

バックエンドの各フェーズのうち、tmd記述と関係するものは である。

これらのフェーズはLIRのモジュール単位に適用される。モジュールには一般に複数の関数が 入っているから、たとえばEarlyRewritingのフェーズでは、モジュールのすべての関数に EarlyRewritingを適用してから次のフェーズに移ることになる。

ところで、ある種の変換を行うときには1つのフェーズだけですべての処理が出来ない場合 があり、そのときは前のフェーズで得た情報を使う必要がある。そのような情報として、 標準的に必要と思われるものはその情報を得る手段が用意されている。 しかし、それ以外の情報が必要となったとき、たとえばtmdの中にJavaプログラム の変数を用意して、ある関数の情報を蓄えたとしても、同じフェーズで他の関数の処理をしたときに それが書き換えられてしまうかも知れない。そのような情報をフェーズにまたがって関数単位で 蓄えておくために、FunctionAttrというクラスが用意されている(coins/backend/gen/にある CodeGenerator.javaの中に書いてある)。これが関数単位に情報を蓄えておくものであるが、 その使い方についてはx86_64のマシン記述のところで説明する。

これらのフェーズで実行されるメソッドなどを追加することも出来る。tmdの中で

(defrewrite .... (phase early))

と書かれたものはEarlyRewritingのフェーズで適用されるのであるが、 それ以外にそのフェーズで適用されるメソッドを以下のようにして定義することも出来る。

EarlyRewritingとLateRewritingでデフォールトとして実行されるものは CodeGenerator.javaの中の

  public Transformer[] earlyRewritingSequence() {
    return new Transformer[] {
      localEarlyRewritingTrig
    };
  }

  public Transformer[] lateRewritingSequence() {
    return new Transformer[] {
      localLateRewritingTrig,
      ProcessFramesTrig
    };
  }

とこれらの"...Trig"の定義(CodeGenerator.javaの中にある)によって決まる。 この、localEarlyRewritingTrigによって上記の"(phase early)"と指定された 書き換えが行われる。デフォールトとは違う処理をする場合は これらのメソッドをオーバライドすればよい。たとえば、x86.tmdには以下の記述がある。

public Transformer[] lateRewritingSequence() {
  return new Transformer[] {
    AggregatePropagation.trig,
    localLateRewritingTrig,
    ProcessFramesTrig
  };
}

これによって、CodeGenerator_x86では、通常のLateRewritingの前に AggregatePropagationの処理を させることが出来るようになっている

9.1.2.3 Javaによる記述

文法定義のみで100%ターゲットCPUの記述が完了するわけではない。 Javaでコードを書かなければならない部分がある。

tmdファイルには、lisp風の文法定義部のほかに、Javaでコードを記述する部分がある。 行頭に%%という印があらわれると、それ以降はJavaのコードとなる。 tmdファイルの全体構造は以下のようになっている。

grammar definitions
%%
imports
%State methods
Method of class State
%CodeGenerator methods
Method of class CodeGenerator

grammar definitionは、これまで説明した defrewrite, def, defregset, defregsetvar, defstart, defruleのリストである。

Javaコード部は、さらに3つの部分に分けられる。一つめのimportsには、以下の記述に必要なimportを書く。

二つめのMethods of class Stateには主に、cond属性中で引用されるメソッドを置く。 CodeGenerator methodsの方に置くと呼び出すことができないので注意すること。

三つめのMethods of class CodeGeneratorには、class CodeGenerator_target のメソッドを書く。大部分のプログラムや、defbuild/defemitマクロはここに置く。

CodeGeneratorのメソッド

以下では、CodeGenerator methods内で定義しなければならないメソッドについて解説するが、細かい点についてはsparc.tmd, x86.tmdの例を参考にされたい。

LirNode rewriteFrame(LirNode node)

メソッドrewriteFrameは、与えられたFRAME式をターゲットCPUでのフレーム変数のアドレスを表す式に変換する。

nodeは、LirSymRefのインスタンスである。この中のシンボルを記号表から索いてオフセット値を求め、 そのオフセットとフレームポインタの和を返す。

たとえば、sparc.tmdでは次のように記述されている。

LirNode rewriteFrame(LirNode node) {
  Symbol fp = func.module.globalSymtab.get("%fp");
  int off = ((SymAuto)((LirSymRef)node).symbol).offset();
  return lir.node
    (Op.ADD, node.type, lir.symRef(fp), lir.iconst(I32, (long)off));
}

現在処理中のL-functionのインスタンスは、上位クラスCodeGeneratorで定義されているfunc という名前のフィールドに保持されている。func.moduleは現在処理中のL-moduleであり、 そこにグローバル・シンボル・テーブルがある。"%fp"はフレーム・ポインタのレジスタである。

lirCodeGeneratorクラスに用意されている LirFactoryクラスのインスタンスであり、 LIRの種々のノードはlirのメソッドを呼び出すことによって作ることが出来る。

LirNode rewritePrologue(LirNode node, BiList post)

rewritePrologueは、nodeで与えられたPROLOGUE式をターゲットCPUで必要な命令列に変換する。

具体的には、パラメタがレジスタ渡しのときはPROLOGUE式の中のパラメタ変数をレジスタに置き換え、後の 命令列postにレジスタからパラメタ変数にコピーするSET式を挿入する。 パラメタがスタック渡しのときは、スタックからパラメタ変数にコピーするSET式を後の 命令列postに挿入する。返すのは置き換えられたPROLOGUE式である。

LirNode rewriteEpilogue(LirNode node, BiList pre)

rewriteEpilogueは、EPILOGUE式を、関数の戻り値をcallerに返す命令列に変換する。

たとえば、戻り値を入れるレジスタが決まっている場合は、戻り値をそのレジスタにコピーする SET式を前の命令列preに挿入し、EPILOGUE式の中の戻り値をそのレジスタに置き換える。 返すのは置き換えられたEPILOGUE式である。

LirNode rewriteCall(LirNode node, BiList pre, BiList post)

rewriteCallは、nodeで渡されたCALL式を、実際の関数呼出し手順に変換する。

たとえば、引数をスタックにpushしたり、特定の実レジスタにロードしたりといった命令を 前の命令列preに挿入し、実レジスタから関数値変数にコピーする命令を 後の命令列postに挿入したりする。

%defbuildマクロと%defemitマクロ

TMDでは、前節で解説したJavaメソッドを直接書く他に、%defbuild・%defemitマクロによってメソッドを定義することができる。 これらは、defrule中のcode属性中で引用されるマクロを展開するメソッドである。

%defbuildマクロと%defemitマクロの違いは、どの時点で展開されるかという点である。 %defbuildマクロはpeepholeよりも前に展開され、%defemitはファイルに出力する直前に展開される。

例として、sparc.tmd中の_setマクロを見てみよう。

%defbuild(_set x y) {
  return ImList.list
    (ImList.list("sethi", ImList.list("%hi", x), y),
     ImList.list("or", y, ImList.list("%lo", x), y));
}

クラスImListはcoins.backend.utilパッケージにある。ImList.listはそのクラスメソッドであり、 ImList型のリストを作って返す。それが、アセンブラ命令のリストになる。 9.1.2.4. リスト表現アセンブラ参照。

このマクロは%defbuildであり、sethiとorの2命令に展開される。 遅延分岐命令の空きスロットを埋める最適化を想定すると、 本当は2命令なのに1命令に見えるマクロが残っているのは好ましくない。 そのため%defemitではなく%defbuildとし、peepholeよりも前に展開されるようにしている。

一方、%defemitはアセンブラソースへの出力の直前に展開されるので、 S式とアセンブラの構文のギャップを埋めるために使われる場合が多い。

その例として、sparc.tmd中の+マクロとmemマクロがある。これらのマクロは、 メモリ参照のオペランドの記述に使われる。

%defemit(+ x y) {
  if (y.charAt(0) == '-')
    return x + y;
  else
    return x + "+" + y;
}

%defemit(mem x) { return "[" + x + "]"; }
%defbuildマクロ

%defbuildマクロは、以下の形式をしている。

%defbuild(macroname arg1 arg2...)
{
	Java statements
}

このマクロは、CodeGeneratorの中のImListを返すメソッドに変換される。 argnはLirNode型の引数に変換される。マクロの本体はそのままである。

複数の命令を返すことも許されているため、一つの命令を返す場合でも、 もう一重にリストで包まなくてはならない(前出の_setマクロ参照)。

%defemitマクロ
%defemit(macroname [=]arg1 [=]arg2...)
{
	Java statements
}

%defemitマクロは、String型を返すCodeGenerator内のメソッドに変換される。 argnはその引数で、通常はString型だが、引数名の前に=が付くとObject型になる。

String型の引数には、対応するS式を事前に文字列に展開した結果が渡されるが、 Object型の引数(=が前置された引数)には、対応するS式そのものがそのまま渡される。

Object型引数(事前評価なし)の例はprologueマクロである。このマクロには引数として L関数(Function)のインスタンスが渡されるので、必ずObject型で受ける必要がある。epilogueマクロも同様である。

LIR のJavaによる表現

L式の内部表現はJavaで記述されている。 L式を表現するクラスはパッケージ coins.backend.lir にある。それらのクラスは抽象クラスLirNodeのサブクラスになっている。 L式とそれを表現するクラスは次のように対応している。
INTCONST -> LirIconst
FLOATCONST -> LirFconst
STATIC, FRAME, REG, LABEL -> LirSymRef
unary op. -> LirUnaOp
binary op. -> LirBinOp
other -> LirNaryOp

なお、CodeGeneratorクラスにはLirFactoryクラスのインスタンスlir が用意されているので、 LIRの種々のノードは、そのlirのメソッドを呼び出すことによって作ることが出来る。

9.1.2.4 リスト表現アセンブラ

コード生成フェーズは、いったんリスト表現のアセンブリ言語を作る。その方が単なる文字列より、 ピープホール最適化がやりやすいからである。

リスト表現アセンブラの例を以下に示す。

  (mov (mem x) %r1)
  (mov (mem y) %r0)
  (add %r0 %r1 %r0)
  (mov %r0 (mem x))

これらのリストはコードエミッターフェーズにより、通常のアセンブラに変換される。 上の例を変換した結果は次のようになる。

  mov [x],%r1
  mov [y],%r0
  add %r0,%r1,%r0
  mov %r0,[x]

リスト表現の実体は、ImListのインスタンスで表現された各行の命令を要素としてもつ 双方向リスト(BiListのインスタンス)である(一番外側がImListでなくBiListなのは編集をしやすくするため)。

ImListの要素はString、LongまたはDoubleのインスタンスであるが、まれに Function(prologue/epilogueのオペランド)や、LirNodeのインスタンスが現れる場合($$を使ったとき)もある。

上の例の1行目の内容をJavaプログラムで生成するとしたら、次のようなコードになる。

 ImList.list("mov", ImList.list("mem", "x"), "%r1")

実際には、リスト表現アセンブラがJavaプログラムによって作られるのは%defbuildマクロの中だけで、 ほとんどはdefrule中のcode属性およびvalue属性によって生成される。

9.1.2.5 TMDの実装例の説明

いくつかの機種に対するTMDの実装について説明する。

9.1.2.6 新規TMDのCOINSへの組込み

バックエンドへの組込み

新規に開発したTMDをCOINSへ組込むには,以下のようにすれば良い. (その新規TMDが"xxx.tmd"という名前のファイルであるとする.)

以上で組込みが完了する.

なお,参考ドキュメントの6),7)にはこのような組込みの 実例が書かれている.

フロントエンドでの指定

新規に組み込んだxxx.tmdを使うためには,COINSのドライバを 呼び出すコマンドのオプションとして

-coins:target=xxx

を指定すれば良い.これによってxxxマシンのコードが生成される.

ただし,このままではコンパイル時に 「xxxは定義されていないオプション名である」 という警告メッセージが出される.

あるオプション項目に新しいオプション名を追加したときは、
   src/coins/Registry.java
の該当項目にその名前を表す文字列定数を追加しないと、
   "Undefined option "
という警告が出る。機種名を追加した場合は
   ARCH[] = { ... };
のリストにそれを追加すればよい。

また,新規のTMDを組み込む場合は, HIR で扱うデータ型がそのマシンでは何バイトで表現されるかということも指定する必要がある. そのデフォールトの 値は coins/MachineParam.java に記述されており,

char: 1, float: 4, pointer: 4 
short: 2, double: 8, address: 4
int: 4, long double: 8, offset: 4 
long: 4, long long: 8 

などとなっている(実際には SIZEOF_CHAR = 1 などと書かれている).ここで,offset は配列要素の添字の値のようにある番地からのオフセットとして表すものである. このデフォールト値と違うマシンの場合は,違う値を定義をしたものを使う必要があ る.そのためには,たとえば coins/MachineParamXxx.java にそれを記述して, それを coins/MachineParam.java の代わりに使われるように coins/IoRoot.java のコンストラクタに

  else if (lTarget.equals("xxx")) { 
    machineParam = new MachineParamXxx(this); 
  } 

という行を追加する必要がある.

なお,参考ドキュメントの7)にはoffsetの変更も含めた 実例が書かれている.

9.1.3 レジスタ割付

 レジスタ割り付けアルゴリズムは、グラフ彩色アルゴリズムの改良型であるGeorge and Appelの Iterated Register Coalescingに基づいているが、SPARCの 浮動小数点レジスタやIntel x86のeax/ah、alレジスタを扱うため、レジスタ対を含むレジスタ集合を 効率よく割り付けられるよう、拡張している。

より詳しくは Coins Register Allocation Algorithm を参照されたい。

9.1.3.1 レジスタ対の扱い

 Intel 8086プロセッサは16bitレジスタax、bx、cx、dx、si、diをもち、このうちaxからdxは、 上位と下位が別々の8bitレジスタah、al、bh、bl、ch、cl、dh、dlとして使える。このような場合 をうまく扱えるようにするため、レジスタ生存区間の重なりを表すレジスタ干渉グラフの辺に重みをつける。

たとえば、8bitの変数から16bitの変数に向けて出ている辺は重み2として次数を計算する。 変数vに4つの16bit変数が干渉しているなら、vの次数は8とする。逆に、16bit変数の側から見れば、 干渉している相手が8bitであろうが16bitであろうが重み1のままでよい。

通常のグラフ彩色によるレジスタ割付の過程では、辺の数(次数)が利用可能なレジスタ数より 少ない頂点をスタックに移してゆくが、レジスタ対をうまく扱うために、単なる次数のかわりに、 辺の重みを合算した値をもつ重み付き次数を使って同様の処理を行う。

9.1.3.2 溢れ候補の選択

 溢れ候補を選ぶには、Chaitinのように溢れのコスト最小のものを選ぶのではなく、 溢れコストのほかに、妨害指数(disturbance factor)とよぶものを求め、 妨害指数から利用可能レジスタ数を差し引いた値が最大のものを選ぶ。

妨害指数は、他の変数に対するレジスタ割付を邪魔する度合いを表すもので、 その変数の生存範囲において、参照・定義されている変数がいくつあるかを示す数である。

妨害指数を求めるためには、まず妨害グラフ(disturbance graph)という有向グラフを作る。 妨害グラフGは、干渉グラフと同様に変数を頂点にもち、変数wの生存範囲において変数vが 参照または定義されているときに限り、辺v→wを含む。変数vの妨害指数は、妨害グラフにおいて、 vに向かっている辺の数として計算できる。

9.1.3.3 Optimistic Register Coalescing 方式の選択

つぎの coins オプションを指定することにより、上記のレジスタ割り付けアルゴリズムとは 異なるアルゴリズムにもとづく、Optimistic Register Coalescing を選択することが できる。 ただし、この選択ができるのは、coins-1.4.4.4 より後のバージョンにおいてである。

    -coins:regalloc=oca

ただし、coins オプションでregalloc(レジスタ割り付け)の指定がなければ、 Iterated Register Coalescing に基づく従来のレジスタ割り付けを使用する。

Optimistic Register Coalescing の適用の詳細に関しては、 SSA最適化の外部仕様書の第10章を参照のこと。

注意
OCA(Optimistic Register Coalescing)適用により、レジスタ割り付け限度を 越えるため、exception が発生する場合があることが確認されている。

9.1.4 バックエンド部の使い方

COINSの標準のドライバ、あるいはそのサブクラスのドライバを呼び出せば、自動的に バックエンド部が呼び出される。

オプション指定をすることによってバックエンド部の挙動をいろいろ変えることが出来る。

バックエンド部に関係するオプションには以下のものがある。

-coins:target=CPU
指定されたターゲットCPU向けのコードを生成する。CPUには次のいずれかが指定可能である。

いずれも、多くのテストプログラム(COINSのソース・アーカイブのcoins/test/c 以下の約700個)で動くことを確認している。

さらに、sparcとx86については、約8,000個のテストプログラムと、SPEC2000が通ることを 確認しているが、 その他のマシンについては、SPEC2000が通ることは まだ確認されていない。

-coins:loopinversion
ループが無条件ジャンプ命令で終端しており、かつループ内から脱出する条件ジャンプ命令がある場合、 条件ジャンプで終端するようにループ内の命令列を並べかえる最適化を行う。ループ内で実行されるジャンプが一つ減るので、 実行時間の短縮が期待できる。
-coins:trace=LIR[.N]
BackEndの入口と出口で、LIRの内部状態を標準出力に表示する。 N の意味については、 2. コンパイラ・ドライバの中の 「コンパイル過程の情報出力」 を参照されたい
-coins:trace=TMD[.N]
コード生成部のトレース情報を標準出力に表示する。
-coins:trace=phasename[.N]

変換ステップの名前phasenameを指定して、その変換作業の前後のLIRの状態を表示する。 前後の状態以外のトレース情報が表示されるものもある。

phasenameとしては以下のものが指定できる。変換作業をおこなうクラスの名前をそのまま用いて いるものが多いが、そうでないものもある。

ToCFG, ToLinear, ToMachineCode, EarlyRewriting, LateRewriting, Restruct, InstSel, AggregateByReference, ConvToAsm, NamingFloatConst, ReplaceFloatConst, RewriteConvUF, AugmentCFG, IntroVirReg, JumpCanon, JumpOpt, LoopInversion, PreHeaders, SimpleOpt, Ssa(pruned), Ssa(minimal), LiveRange, RegisterAllocation

-coins:attach=classnames...

これは、拡張機能を使う時の書き方であり、 追加すべき拡張クラス名を指定する。(拡張機能を定義する方法は次節にのべる。)

クラス名は、.(dot)を含んでいない場合は、パッケージcoins.backend.contrib内にあるものとして扱われる。 複数のクラスを指定する際には、

-coins:attach=Foo/Bar/Quux

のように/で区切って並べる。

クラスが指定されると、その中の

static void attach(CompileSpecification,Root)
というメソッドが呼出されるので、必要な初期化をこの中で行う。

9.1.5 バックエンドの最近の拡張版

9.1.5.1 TMDの拡張

マクロ機能

TMDでマクロが使えるようにする。

基本定義

fooという名前のマクロの定義は

  (defmacro (foo arg1 arg2)
           body arg1 arg2) 

のようになる。これを以下のように呼出すと

  (hogehoge (foo bar "quux") piyo) 

次のように展開される。括弧がはがされることに注意。

  (hogehoge body bar "quux" piyo) 

マクロ本体中のマクロ呼出しも可能。展開後のS式中にマクロ呼出しがなくなるまで何度もスキャンして展開する。

引数の置換

仮引数が@以外の文字で始まる場合は、body中のアトムが完全に仮引数名と一致するときにのみ実引数と置換が行われる。 このとき、実引数の中にマクロ呼び出しがあれば、それも展開されてから置き換えが行われる。

仮引数が@で始まる名前のときは、マクロbody中の任意の部分文字列中にその仮引数と同じ綴りが現れると、 実引数と置きかえを行う。この場合、実引数の中にマクロ呼び出しがあっても展開されない。

@で始まる仮引数を用いれば文字列の連結ができる。以下を参照。

 (defmacro (xcat @x @y) @x@y)
 (defmacro (cat x y) (xcat x y))
 (cat (cat foo bar) (car hoge moge))
 → foobarhogemoge 
組み込みマクロ
条件付き展開
 (@if expr
    (seq-true...)
    (seq-false...)) 

exprがnilならseq-false、そうでなければseq-trueに展開。seq-true, seq-falseをかこむカッコ は展開時にはがされる。

演算
 (@eq x y)   x と y が等しい文字列かどうか。等しければt, そうでなければ()
 (@ne x y)   x と y が等しい文字列かどうか。等しくなければt, 等しければ() 
include

includeを用いて、他のファイルの内容を取り込むことができる。

 (include "filename") 

とすると、ファイル filename の内容がこの場所に取り込まれる。ただし、取り込めるのはS式で書かれたものだけで、 TMDのJavaコード部分をincludeすることはできない。

速度優先・スペース優先の指定機能

速度優先・スペース優先の指定の機能は、tmd記述の拡張と、コンパイラのオプション指定の拡張で実現している。

tmd記述の拡張としては、tmdのdefrule記述の中で、cost属性として速度を示すコストとスペースを示すコスト の両者を記述できるようにした。コスト属性は

 (cost 速度のコスト スペースのコスト) 

の形で書けば良い。

コンパイラオプションでスペース優先の指定がされたときは、スペースのコストの和が小さい命令列が選択される。 そうでなければ、速度のコストの和が小さい命令列が選択される。

なお、従来のTMDではコストは1つしか書くことが出来なかった。その形のままになっている場合は それが速度のコストとしてもスペースのコストとしても使われる。

コンパイラのオプション指定としては、

 -coins:optspace 
がスペース優先の指定を意味する。デフォールトは速度優先である。
MicroBlazeの例
MicroBlazeのマシン記述mb.tmdにはシフトや乗算命令に関して速度とスペースのコスト が書かれている。また、バレルシフタを使用しないことをコンパイラオプションで指定する(-coins:x-mb=no-bs)ことも出来る。 したがって、たとえば
int shift10(int x){
  return x << 10;
}
と言うソースプログラムに対して
-coins:x-mb=no-bs
と言うオプションを与えてコンパイルすると
	addk	r3,r5,r0
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
	addk	r3,r3,r3
が得られる。これは1ビットシフトする命令を10個並べた形である。次に
-coins:x-mb=no-bs,optspace
で、スペース優先を指示すると
	addik	r4,r0,10
	andi	r18,r4,31
	beqid	r18,.L4
	addk	r3,r5,r0
.L5:
	addik	r18,r18,-1
	bneid	r18,.L5
	addk	r3,r3,r3
.L4:
が得られる。これは1ビットシフトする命令をループで10回実行する形である。なお、 これらのオプションを指定しないと、バレルシフタを使う命令
	bslli	r3,r5,10
が生成される。
SPARCの例
たとえば、sparc.tmdの中に
(defrule regl (MUL I32 regl rc)
  (cond "machineOptV8")
  (code (smul $1 $2 $0))
  (cost 6 1)) 
(defrule regl (MUL I32 regl rc)
  (cond "is5($2)")
  (code (sll $1 2 "%g1")
        (add $1 "%g1" $0))
  (cost 2 2)) 
のように書くことができる。ここで"machineOptV8"の値は、
 -coins:target=sparc-v8 
の指定があったときにtrueになる。また is5メソッドは引数の値が整数定数の5であるときtrueの値を返すメソッドである。

コンパイラのオプション指定としては、

 -coins:optspace 
がスペース優先の指定を意味する。デフォールトは速度優先である。

上記のような記述を含むsparc.tmdであったときに、ソースプログラム

int mult5(int x){
  return x * 5;
} 
の"x * 5"のコードとしては、速度優先でコンパイルすると、
	sll	%i0,2,%g1
	add	%i0,%g1,%i0 
が得られ、スペース優先でコンパイルすると
	smul %i0,5,%i0 
が得られる。

共通TMD

各種のマシンのtmd記述の中には共通な表現になる部分も多い。そこで、それらを共通なtmdファイルとして記述しておき、 各マシン記述でそれを利用できるようにした。

標準では符号なし整数と浮動小数との相互の変換が用意されていて、以下 のように記述すれば利用することができる。

(include "common.tmd")
(use-convuf-fu)

rewriteCall, rewritePrologue, rewriteEpilogueの標準化

従来CALL/PROLOGUE/EPILOGUE命令の変換処理は各プロセッサごとに手書き する必要があり、作成が容易ではなかった。この点を改良するため、いくつか の機種依存コードのみを定義すれば良いように変更した。

tmd に以下の記述を行うことで標準化された変換処理を使用することがで きる。

(include "common.tmd")
(use-call)

もちろん、rewriteCALL/rewriteProloge/rewriteEpilogueを自分で定義すれば 従来通りの動作となる。

本標準化では、以下のような呼びだし規約(calling convention)を持ったものを仮定している。

sparc, x86, armなどは、このような呼びだし規約に従っているので、 これを利用することが出来る。実際には、後から開発されたarm.tmdで これを利用している。arm.tmdでは、以下に述べる変数やメソッドだけが 定義されている。なお、標準化された rewriteCALL/rewriteProloge/rewriteEpilogueは /coins/backend/gen/CodeGenerator.javaに記述されている。

定義すべき変数・メソッドは以下のとおり。

パラメタの型および語長
int typeParamWord
パラメタの語の型を指定する。通常はI32。変更する場合は
{ typePramWord = I64; }
のようにJavaコード部分に初期化ブロックを置くこと。
レジスタで渡すことのできる最大バイト数
int clcvnRegLimit()
パラメタ渡しに使うことができるレジスタの個数×レジスタのサイズ(バイト) を返す。
パラメタ渡しのL式 (レジスタもしくはメモリ)
LirNode clcvnParamWord(int type, int location, boolean caller)
パラメタ渡しに使われるレジスタもしくはメモリ(スタック)のL式を返す。
パラメタ渡しのL式 (レジスタ)
LirNode clcvnParamReg(int type, int location, boolean caller)
パラメタ渡しに使われるレジスタのL式を返す。
パラメタ渡しのL式 (メモリ)
LirNode clcvnParamMem(int type, int location, boolean caller)
パラメタ渡しに使われるメモリ(スタック)のL式を返す。
仮パラメタの変位の変換
int clcvnParamOffset(int location)
スタック渡しの仮パラメタの変位を、記号表に登録するオフセットに変換する。
浮動小数型のパラメタ
void clcvnPassFloatRegMem(int location, LirNode arg, BiLink memp,
			  BiLink regp, BiList alist)
float/double型のパラメタをレジスタに入れて渡す、もしくは一部を レジスタ、一部をメモリに入れて渡すコードを生成する。
関数の戻り値
LirNode clcvnReturnValue(int type)
関数のreturn valueを入れるレジスタのL式を返す。
整数レジスタの一部にアクセスする
LirNode clcvnPartialWord(LirNode exp, int part)
64bit int等を実装している場合に整数レジスタの一部をとりだす。
LirNode clcvnSetPartialWord(LirNode lhs, int part, LirNode rhs)
整数データの一部を置き換える。
破壊されるレジスタの指定
ImList clcvnClobbers()
callで破壊されるレジスタのリスト。通常これは*reg-call-clobbers*で指定 したレジスタの集合が返される。
構造体の戻り値
boolean clcvnStructReturnAsFirst()
構造体を返す関数に対し、その結果を納める場所のアドレスを第一引数として 渡すという仕様ならtrueを返す
LirNode clcvnStructReturnPtr(boolean caller)
clcvnStructReturnAsFirstがfalseの場合に、構造体を納める場所のアドレス を渡す場所(隠しポインタ)のL式を返す。

リテラルとブランチの変換

組込み向けのマシンでは、命令のサイズを小さく保つためにアドレスの ディスプレースメントのサイズが小さな命令があることが多い。 主として、ブランチ命令の飛び先のアドレスを指定する部分や 定数(リテラル)をロードする命令で、その定数のアドレスを指定する部分 などにそれがある。

それらを出来るだけ生かした命令を生成するすための処理を 個々のマシンのTMDで記述するのも一つの方法であるが、 それらの処理にはマシンによらない共通な部分が多い。

そこで、その処理をTMDに記述するのではなく、バックエンドの 最終段階で(アセンブラ出力の直前で)行うようにした。 それがこの「リテラルとブランチの変換」である。

これを利用する場合は、 各TMDにより生成する命令では、リテラルをロードする命令は 単にそのリテラル値だけを命令に付けておけばよく、ブランチ命令 はブランチ先のラベルだけ付けておけば良い。

この「リテラルとブランチの変換」によって、それらの命令を出来るだけ 短い命令に変換する。

リテラルとブランチの生成

この「リテラルとブランチの変換」の機能を使うためには、各TMDにより生成するリテラルとブランチに関する命令 を以下のようにしておく必要がある。

リテラル生成

リテラルをロードする命令では、リテラル値を直接命令の中にオペランドとして置く。 ただし、リテラルにはオペランドに=W, =S, =Bを前置する。

       ldr     %r0,=W12345 

これは以下のように変換される。

       ldr     %r0,.LB1
       ...
.LB1:
       .word 12345 

=Wは.word, =Sは.short, =Bは.byteになる。

ブランチ生成

ブランチとしては、まず、短いブランチ命令だけを生成する。

       beq     .L1
       ...
.L1: 

このブランチが届かない場合は変換器が

       bne     .LB2
       b       .L1     ; 短い無条件分岐命令
.LB2:
       ...
.L1: 

のように変換する。さらに b .L1 が届かない場合は

       bne     .LB2
       bl      .L1     ; 長い無条件分岐命令(Thumbではblで代用)
.LB2:
       ...
.L1: 

となる。

変換のためのTMDでの記述

TMDには以下の記述をする

import文
まず、以下のクラスをimportする。
import coins.backend.asmpp.LiteralAndBranchProcessor;
import coins.backend.asmpp.CPU;
CPUクラスの拡張

importしたcoins.backend.asmpp.CPUは、対象とするCPUの特性を表すクラスであり、次のものである。 ここで、範囲などの値の単位はバイト数である。

abstract class CPU { 
       public int[] bccRange;     // 条件付分岐命令が届く範囲
       public int[] braRange;     // 無条件分岐命令が届く範囲
       public int[] literalRange; // リテラルをアクセスできる範囲
       public String[] bccMnemo;  // 条件付分岐命令のニーモニック
       public String braMnemo;    // 無条件分岐命令のニーモニック
       public int braLength;      // 無条件分岐命令のバイト数
       public int codeAlign;      // 命令のアライメント(1 << codeAlign) 
       // instのバイト数を返す
       public int codeLength(String inst) {
               return 1;
       } 
       // 条件付分岐を生成する
       public String generateBcc(String mnemo, String label) {
               return "\t" + mnemo + "\t" + label;
       } 
       // 無条件分岐を生成する
       public String generateBra(String label) {
               return "\t" + braMnemo + "\t" + label;
       } 
       // 長い無条件分岐を生成する。複数行を生成しても構わない
       public String[] rewriteToLongBranch(String label) {
               return new String[] { "\t" + braMnemo + "\t" + label };
       } 
       public boolean isBcc(String mnemo) {
               for (int i = 0; i < bccMnemo.length; i++) {
                       if (mnemo.equalsIgnoreCase(bccMnemo[i])) {
                               return true;
                       }
               }
               return false;
       } 
       public boolean isBra(String mnemo) {
               return mnemo.equalsIgnoreCase(braMnemo);
       } 
       public boolean inBccRange(int n) {
               return (bccRange[0] <= n && n <= bccRange[1]);
       } 
       public boolean inBraRange(int n) {
               return (braRange[0] <= n && n <= braRange[1]);
       } 
       public boolean inLiteralRange(int n) {
               return (literalRange[0] <= n && n <= literalRange[1]);
       } 
       public String getRevMnemo(String mnemo) {
               for (int i = 0; i < bccMnemo.length; i++) {
                       if (mnemo.equalsIgnoreCase(bccMnemo[i])) {
                               i ^= 1;
                               return bccMnemo[i];
                       }
               }
               return null;
       } 
       public abstract String toString();
} 

これを拡張して各CPUの特性を設定する。以下はThumbの例。

なお、同様のものがクラスLitralAndBranchProcessorにも書かれているが、 それらはLitralAndBranchProcessorをバックエンドとは独立に使うときに必要 となるものである。バックエンドからLitralAndBranchProcessorを呼び出すと きは、それらをTMDに書いておく必要がある。

final class Thumb extends CPU { 
       Thumb() {
               // 値は少なめにしておく^_^;
               bccRange = new int[] {-240, 250};
               braRange = new int[] {-2024, 2024};
               literalRange = new int[] {0, 1020};
               // 反対の動作となるペアを一組として命令を並べる
               bccMnemo = new String[] { "beq", "bne", "bcs", "bcc",
                                         "bhs", "blo", "bmi", "bpl",
                                         "bvs", "bvc", "bhi", "bls",
                                         "bge", "blt", "bgt", "ble" };
               braMnemo = "b";
               braLength = 2;
               codeAlign = 1;
       } 
       public int codeLength(String inst)
       {
               StringTokenizer tokens = new StringTokenizer(inst, " \t,");
               if (tokens.hasMoreTokens()) {
                       String mnemo = tokens.nextToken();
                       if (mnemo.equalsIgnoreCase("bl")) {
                               return 4;
                       }
               }
               return 2;
       } 
       public String[] rewriteToLongBranch(String label) {
               return new String[] { "\tbl\t" + label };
       } 
       public String toString() {
               return "Thumb";
       }
} 
バックエンドから呼ばれるメソッド
この変換器は、バックエンドのCodeGeneratorがアセンブラ命令の形で出力したものを受け取り、それに上記の変換をほどこした ものを最終出力として出力する。この変換器の本体は上記でimportしたLiteralAndBranchProcessorであり、 スレッドとして動作するものである。そのスレッドの呼び出しと終了処理のために次のメソッドが必要である。
/** Run Literal and Branch post processor after generating assembly code. **/

private LiteralAndBranchProcessor pp;

OutputStream insertPostProcessor(OutputStream out) {
        pp = LiteralAndBranchProcessor.postProcessor(out);
        pp.setCPU(new Thumb());  // Thumbの場合
        return pp.pipeTo();
}

void notifyEndToPostProcessor() {
        pp.notifyEnd();
}
ここで引数のoutは最終出力用ストリームである。このinsertPostProcessorメソッド はコード生成の直前にバックエンドから呼ばれる。このメソッド を実行することにより、変換器がスレッドとして作られて実行される。ターゲットマシンの 特性はsetCPUでセットされる。変換の対象となるアセンブラ命令の ストリームはreturn pp.pipeTo()で返されるものであり、そのストリームにCodeGeneratorが アセンブラ命令を出力する。それを変換したものがoutに出力される。

9.1.5.2 文の実行頻度プロファイラ

文の実行頻度を出力するプロファイラを開発した。以下の制限がある。

プロファイラの使い方

  1. プロファイルをとりたいCソース(仮にfoo.cとする)のmain関数の最後に、
    __flush_profile(); 
    という関数呼び出しを入れる。
  2. 以下の手順でコンパイルする。
    $(COINSCC) -c -coins:debuginfo,profile foo.c
    ./gen-profile-data.pl foo.c  >profile_data.c
    $(COINSCC) -c flush_profile.c
    $(COINSCC) foo.o flush_profile.o 

    ここで、$(COINSCC)はcoins.driver.Driverを呼び出すコマンドである。

    flush_profile.c, gen-profile-data.pl, prof-list.plは、ここに置かれているものを使えば良い。

  3. 以下の手順で実行し、実行回数を表示する。
    ./a.out
    ./prof-list.pl foo.c 

次のプログラム(ファイル名simple.c)
int main(){
	int i, a[10];
	for (i = 0; i < 10; i++)
		a[i] = i;
	__flush_profile();
	return 0;
} 
に対して、上記のコンパイルと実行をした結果、次のプロファイルが得られる。
1:      1   int main(){
2:                  int i, a[10];
3:      1           for (i = 0; i < 10; i++)
4:     10                   a[i] = i;
5:      1           __flush_profile();
6:      1           return 0;
7:          } 

左端の数字が行番号であり、その次の数字がその行を実行した回数を示す。

次の例は、小町算のプログラムのプロファイルをとったものである。
    1:          #include <stdio.h>
    2: 
    3:      1   main() {
    4:            int i,s,sign[10];
    5:            long n,x;
    6: 
    7:      1     for(i=1;i<=9;i++)
    8:      9       sign[i]=-1;
    9:      1     do {
   10:  13122       x=n=0;
   11:  13122       s=1;
   12:  13122       for(i=1;i<=9;i++) {
   13: 118098         if(sign[i]==0)
   14:  41553           n=10*n+i;
   15:                else {
   16:  76545           x+=s*n;
   17:  76545           s=sign[i];
   18:  76545           n=i;
   19:                }
   20:              }
   21:  13122       x+=s*n;
   22: 
   23:  13122       if(x==100)
   24:     12         printexp(sign);
   25: 
   26:  13122       i=9;
   27:  13122       s=sign[i]+1;
   28:  13122       while(s>1) {
   29:   6560         sign[i]=-1;
   30:   6560         i--;
   31:   6560         s=sign[i]+1;
   32:              }
   33:  13122       sign[i]=s;
   34:            }while(sign[1]<1);
   35:      1     __flush_profile();
   36:          }
   37: 
   38:     12   printexp(int sign[]) {
   39:     12     printf("",sign[0]);
   40:          }
   41: 

9.1.5.3 LIRシミュレータ

あるマシン(ターゲットマシン:たとえばARM)での実行の様子を別の種類のマシン(ホストマシン:たとえばx86) で観察するために、ターゲットマシン用のLIRから得られた情報を使って、ホストマシン用のコードを生成して実行する のがLIRシミュレータである。

LIRシミュレータによるシミュレーションは以下の手順で行われる。

  1. プラグマによりシミュレーションのホストマシンやデータ取得範囲などを指定する。
  2. プラグマの情報はHIRからLIRに渡される。
  3. そのLIRに対して、ターゲットマシン向けにバックエンドを実行し、ターゲットマシンでのメモリアクセス情報などを記録する。
  4. もとのLIRに対して、ホストマシン向けにバックエンドを実行し、上記の情報を使ってシミュレーション情報収集用命令を挿入する。
  5. 得られたコードをホストマシンで実行してシミュレーション情報を収集する。
  6. その結果を見やすい形に編集する。

詳細については、しばらくお待ちください。

9.1.6 参考ドキュメント

  1. LIR内部構造
  2. バックエンド部の実装(pdf)
  3. Coins Retargetting Guide
  4. Coins Register Allocation Algorithm
  5. L. George and A. Appel: Iterated register coalescing, ACM TOPLAS, Vol. 18, No. 3, pp. 300-324 (May 1996).
  6. J.Park and S.M. Moon: Optimistic register coalescing, ACM TOPLAS, Vol. 26, No. 4, pp. 735-765 (July 2004).
  7. 森公一郎, 阿部正佳, 中田育男, 鈴木貢: 「TMDによるコード生成-SPARC0を例題として」 情報処理, Vol.47, No.7, pp.776-785 (Jul. 2006).
    連載「21世紀のコンパイラ道しるべ・・COINSをベースにして」の4
  8. 中田育男, 渡邊坦, 佐々政孝, 滝本宗宏: コンパイラの基盤技術と実践 ー コンパイラ・インフラストラクチャCOINSを用いて, 朝倉書店 (2008年6月).
  9. 副島祐介, 佐々政孝:レジスタ割り付けにおけるOptimistic Register Coalescingの実装と評価,日本ソフトウェア科学会第25回大会論文集,2008.