社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

VLIW 型プロセッサ用リターゲッタブル・リニアアセンブラ
野垣内 聡†

石浦菜岐佐†

今井正治††† 関西学院大学 理工学部 〒 669-1337 兵庫県三田市学園２－１†† 大阪大学 〒 565-0871 吹田市山田丘 1 番 5 号
E-mail: †{nogaito-s,ishiura}@ksc.kwansei.ac.jp, ††imai@ist.osaka-u.ac.jp
あらまし 本稿では, VLIW 型カスタムプロセッサのためのソフトウェア開発ツールとして, リターゲッタブル・リニアアセンブラを提案する. リターゲッタブル・リニアアセンブラは, マイクロアーキテクチャの詳細を意識せずにコーディングができるリニアアセンブリと, ターゲット・プロセッサのアーキテクチャの記述を入力として, そのプロセッサ用に最適化されたアセンブリを出力する. 本稿では, 複数のターゲットに対応させるためのプロセッサアーキテク
チャのモデル化, 及びリターゲッタブル・リニアアセンブラのスケジューリングの定式化を示す.
キーワード リターゲッタブル・リニアアセンブラ, VLIW 型プロセッサ, コードスケジューリング

Retargetable Linear Assembler for VLIW Processor
Satoshi NOGAITO† , Nagisa ISHIURA† , and Masaharu IMAI††† Kwansei Gakuin University, Gakuen 2—1, Sanda, Hyogo, 669—1337, Japan†† Osaka University, Yamadaoka, Suita, Osaka, 565—0871, Japan
E-mail: †{nogaito-s,ishiura}@ksc.kwansei.ac.jp, ††imai@ist.osaka-u.ac.jp
Abstract This paper proposes a retargetable linear assembler as a software development tool for custom VLIWprocessors. The retargetable linear assembler takes a linear assembly program, which can be coded without thedetailed knowledge of the microarchitecture, and architecture description of a target processor, to generate an assembly code optimized for the processor. We present an architecture model and the formulation of the schedulingproblem for the retargetable linear assembler.
Key words retargetable linear assembler, VLIW processor, code scheduling

1. は じ め にとし, そのプロセッサ用のコードを生成する. C などの高級言語をソースコードとすると, コーディングにかかる負担は少な

近年, ディジタル機器への搭載を目的に, 特定の応用に命令くなる. ただし, 特定用途のカスタム・プロセッサでは, 使用すセットやハードウェア構成を最適化したカスタムプロセッサをる命令やハードウェア資源が性能に大きく影響するため, 十分使用することが多くなっている. 特に複数の命令を並列に実な質のコードが出力できない場合がある. 一方, アセンブリ言

行する VLIW (Very Long Instruction Word) 型プロセッサは,語では使用したい命令を直接指定でき, 高速なコードを記述し静的スケジューリングにより, 高速な演算処理や低消費電力をやすいが, VLIW などの複雑なプロセッサでは命令の並列スケ実現するものであり, メディア処理など性能を要求する応用にジューリングや, クラスタ分割, 及びデータ転送の挿入が必要に適していると考えられる.

なりコーディングが困難となる場合が多い. そのため基本的なこのようなプロセッサのソフトウェアの効率的な開発には,シンタックスはアセンブリと同じであるが, 演算器やクラスタコンパイラ, アセンブラ, リンカ, シミュレータ等のツールの開などのハードウェアの詳細を意識せずにコーディングができる発が必須となる. カスタムプロセッサを一つ開発する度に専用

リニアアセンブリ [4] は VLIW 型プロセッサでのソフトウェアのソフトウェア開発ツールを作成するのは効率が悪いため, プ開発に有用であると考えられる.

ロセッサアーキテクチャの記述を基に上記のツールを自動生成

そこで本稿では, リニアアセンブリとアーキテクチャ記述かするリターゲッタブルな開発環境が種々提案されている [1] [2].

ら最適化されたアセンブリを出力するリターゲッタブル・リニ

リターゲッタブル・コンパイラ [3] は C などの高級言語によアアセンブラを提案する. リターゲッタブル・リニアアセンブ

るソースコードと, ターゲット・アーキテクチャの記述を入力

ラはアーキテクチャの記述を入力とすることで複数のターゲッ–1–

ド命令の追加などを行いアセンブリを出力する. 単体で使用す

1:

1:

MVK

2:||ZERO.L1 A6

MVK .S1 50,A2

2:ZERO s050,i3:||ZERO.L2 B6

3:ZERO s1

4:L1: LDW.D1 *A3++,A5

4:L1:LDW*a++,v1

5:

5:

LDW

*b++,v2
v1,v2,p1||LDW.D2 *B3++,B5

6:

NOP

6:

MPY

7:

MPY .M1 A5,B5,A64

7:MPYH v1,v2,p2

8:||MPYH.M2 A5,B5,B6

8:

ADD

p1,s0,s0

9:

ADD .L1 A6,A7,A7

9:

ADD

p2,s1,s1

10:||ADD .L2 B6,B7,B7

10:

ADD

s0,s1,A4

11:

ADD .L1 A7,B7,A4

11:[i]SUBi, 1, i12:[i]

L1

12:[A2]SUB .L1 A2, 1,A2
13:[A2](a) アセンブリ
図1B

B .S1 L1(b) リニアアセンブリ

TMS320C62x のアセンブリとリニアアセンブリの例る以外にコンパイラのバックエンドとしての使用も考えられる.

図2

リターゲッタブル・リニアアセンブラの構成

3. リターゲッタブル・リニアアセンブラ
リターゲッタブル・リニアアセンブラは図 2 のように, リニアアセンブリとターゲットアーキテクチャの記述を入力とし,トに対応し, またリニアアセンブリをソースコードとすること最適化されたアセンブリを出力する. すなわち, アーキテクチャで, コーディングの負担を減らしながらも性能の良いコードを記述を用意すれば, そのプロセッサ用のリニアアセンブラが得出力することを目的とする. 1 つの命令セットアーキテクチャにられることになる.

対して複数のマイクロアーキテクチャを開発する場合に, その同一の命令セットであっても VLIW のスロット数, ディス差異を吸収してソースコードの移植性を維持するのにも有用でパッチモデル, レジスタ構成を変えることにより, 性能, ハードある. また, リニアアセンブリを中間表現とすれば, リターゲッウェア量, 消費電力のバランスを大きく変化させることができタブル・コンパイラのバックエンドとして使用することも出来る. リターゲッタブル・リニアアセンブラはこのようなマイクる. 本稿ではリターゲッタブル・リニアアセンブラが扱うアーロアーキテクチャの探索にも有用と考えられる. また, リター

キテクチャのモデル, スケジューラの行う処理の定式化を示す.

ゲッタブル・リニアアセンブラの行う命令スケジューリングや2. リニアアセンブラ

レジスタ割り当てなどの処理は, コンパイラのバックエンドが行う処理と同じであるため, これをリターゲッタブル・コンパ

図 1 (a) は Texas Instrumental 社製の VLIW 型プロセッサイラのバックエンドとして利用することもできる.

TMS320C62x [7] のアセンブリの例である. TMS320C62x は

3. 1 アーキテクチャ記述それぞれがレジスタファイルと 4 種類の演算器を持つ二つのク

本稿でターゲットとする VLIW プロセッサのモデルは, 大ラスタから構成されており, アセンブリもそれらを考慮した記

阪大学で開発された特定用途向プロセッサ開発ツール ASIP述となる. コード中の||はその行の命令を直前の命令と並列にMeister [5] のモデルに基づくものであり, TMS320C62x, 富士実行する指示であるが, ユーザは命令レベルの並列化を陽に指通の FR400 シリーズ [8], PHILLIPS 社の TriMedia [9] などの定しなければならない. 6 行目の NOP は 4, 5 行目のロード命令

VLIW 型プロセッサを扱うことができる.の完了を待つためのものである. ニーモニックの後の.S1 など

プロセッサは, 任意の数のスロットを持ち, 命令のパイプライは使用する演算器を, オペランドの A2, B6 などはそれぞれクラン段数は任意とする. 以下, 一度にディスパッチされる命令をスタ A, クラスタ B のレジスタを指定するものであり, 命令の「長命令」, リニアアセンブリ中の命令を「リニアアセンブリ命クラスタへの割り当てや演算器の選択もユーザが行わなければ令」, プロセッサの個々のスロットが実行する命令を「マイクならない. このようにプロセッサの持つ演算器, クラスタ, パイロ命令」と呼称する.

プライン構成を熟知している必要がある.
このアセンブリに対応するリニアアセンブリが図 1 (b) であアーキテクチャ記述は, リソースの情報, リニアアセンブリ命
令の情報, マイクロ命令の情報, ディスパッチ情報, データ転送

る. リニアアセンブリは命令が逐次実行されるセマンティクス表から成る.

であるため, ||や NOP を指定する必要は無い. また, 命令を実（ 1 ） リソース情報

行する演算器やクラスタの指定も不要であり, オペランドのレプロセッサが持つレジスタやレジスタファイル, 演算器などのジスタは変数を用いて記述できる. このようにリニアアセンブ情報を記述する. それぞれのレジスタファイルの容量や, レジリはアーキテクチャが持つ演算器, レジスタ, クラスタなどを意

スタのデータ幅, レジスタペアを構成するレジスタなどの情報

識せずにコーディングを行うことができる.

を記述する.

リニアアセンブラは, リニアアセンブリを入力として, 命令ス
ケジューリングや演算器/レジスタの割り当て, スピル/リロー（ 2 ） リニアアセンブリ命令の情報
各リニアアセンブリ命令に対し, 命令のシンタックス, オペラン–2–ド名とその使用法, 命令を実行可能なマイクロ命令の集合を記述する. 図 3 にレジスタを使用する加算命令 ADD Register のID

例を示す. シンタックスは正規表現で記述する. $reg はレジス

シンタックス

タオペランドにマッチし, 括弧で囲まれたものが左から 1 番目,2 番目, …のオペランドとなる. オペランド情報は, それが順に
src1, src2, dst に対応し, それぞれ read, read, write の属性を

ADD Register\s*ADD\s+($reg)\s*,\s*($reg)\s*,\s*($reg)

1 src1(read)
オペランド 2 src2(read)

3 dst(write)
マイクロ命令ADD L1 AAA, ADD L1 ABA, ADD L1 BAA,持つ. 「マイクロ命令」はこのリニアアセンブリ命令をマッピ

ADD L2 BBB, ADD L2 BAB, ADD L2 ABB,ング可能なマイクロ命令の集合である. ADD L1 AAA は, L1

ADD S1 AAA, ADD S1 ABA, ADD S2 BBB,を使用し, レジスタファイル GRA に, 3 つのオペランドそれぞADD S2 BAB, ADD D1 AAA, ADD D2 BBB

れがアクセスするマイクロ命令を表わす.

図 3 リニアアセンブリ命令情報の例（ 3 ） マイクロ命令情報
各マイクロ命令の使用するスロットやパイプライン・ステージ毎の動作を記述する. 図 4 に, レジスタファイル GRA と M1

ID

MPY M1 AAAを使用する乗算を行うマイクロ命令 MPY M1 AAA の例を示

slot

slot3

す. このマイクロ命令は”slot3”からディスパッチされる. 実行

stage 1 source0 = GRA.read0(src1)
source1 = GRA.read1(src2)

ステージの 1 ステージ目でレジスタファイル GRA にポート 0,ポート 1 を使用して read を行い, 演算器 M1 を使用して乗算を行っている. 2 ステージ目では結果をレジスタファイル GRA

result = M1.mul(source0, source1)stage 2 GRA.write1(dst, result)
図4

マイクロ命令情報の例 (フォワーディング無)のレジスタに格納している. 使用する演算器, アクセスするレジスタファイルが異なるものはそれぞれ別個のマイクロ命令となる. また, それぞれのマイクロ命令をディスパッチできるスID

MPY M1 AAA

ロットは一意に決まるものとする.

slot

slot3

プロセッサがフォワーディングを行う場合は, それをフォワー

stage 1 tmp0 = GRA.read0(src1)

ディングユニットへのアクセスの形で記述する. 本稿で扱う

tmp1 = GRA.read1(src2)
source0 = FWU0.read(src1, tmp0)

フォワーディングは, [6] のモデルを使用する. 図 5 に図 4 にフォ

source1 = FWU1.read(src2, tmp1)

ワーディングを追加したマイクロ命令の例を示す. 1 ステージ

result = M1.mul(source0, source1)

目において, フォワーディングユニット FWU0, FWU1 は受け

FWU0.write1(dst, result)

取るデータがフォワーディングされていれば, フォワーディン
グユニットに write されたデータを受け取り, そうでなければ

FWU1.write1(dst, result)
stage 2 GRA.write1(dst, result)

レジスタからデータを転送する. 1, 2 ステージ目では演算結果

FWU0.write2(dst, result)

を FWU0, FWU1 にフォワーディングしている.

FWU1.write2(dst, result)（ 4 ） ディスパッチ情報

図5

マイクロ命令情報の例 (フォワーディング有)長命令としてディスパッチ可能なマイクロ命令の組み合わせを記述する. マイクロ命令単位での記述は効率が悪いので, 複数のマイクロ命令を集めたものをマイクロ命令グループとし, ディスパッチできるマイクロ命令グループの組み合わせを記述する.
図 6 にディスパッチ情報の例を示す. 各行は長命令で実行可能なマイクロ命令グループの組を表わす.
（ 5 ） データ転送表

…

slot1

slot2

slot3

PALU L1

PALU S1PM U L M 1… PALU S1PALU L1

PSHIF T S1

PM U L M 1… PALU S1PALU L1

PSHIF T S1

PM U L M 1…

PSL S1PALU L1

PALU S1PM U L M 1…

PSL S1

…

…

…

…

…

レジスタからレジスタ, レジスタからメモリ, メモリからレジス

図6

slot8

ディスパッチ情報の例

タへの転送を行う際に使用するマイクロ命令と, そのオペランドの指定法を記述する. 図 7 にデータ転送表の例を示す. 例えば, 1 行目はレジスタファイル GRA から GRB への転送は, マ

転送元 転送先 マイクロ命令列

イクロ命令 ADD L1 AIB の 2 番目のオペランドを 0 にして行GRAうことを示している.

3. 2 リニアアセンブリとアセンブリ
本稿で扱うリニアアセンブリとそこから出力されるアセンブ
リの例をそれぞれ図 8 (a), (b) に示す. リニアアセンブリのオ
ペランドは図 8(a) 6 行目のように基本的には変数を記述するがGRB(ADD L2 AIB %src1, 0, %dst)

GRB

GRA

(ADD L1 BIA %src1, 0, %dst)

GRA

MEM

(STW D1 AA %base, %oﬀset, %src)

GRB

MEM

(STW D2 BB %base, %oﬀset, %src)

MEM

GRA

(LDW D1 BB %base, %oﬀset, %dst)

MEM

GRB

(LDW D2 BB %base, %oﬀset, %dst)図7

データ転送表の例

8, 9 行目のように A2, B2 のようなプロセッサが実際に持つレ–3–

てるが, 必要がある場合にはスピル/リロードなどの転送命令のSUB_L1_AAA A3,A3,A3追加を行う.

LDW_D1_AA *A2++,A4

でにマイクロ命令は割り当てられ, それぞれ 1 サイクル目から

4:.temp 24:72

4:|| LDW_D2_BB *B2++,B4実行されているとする. この 2 つの命令は依存関係がなく, ま5:5:|| SUB_L2_BIB B5,1,B5たマイクロ命令が同じ資源を使用していないので並列にスケ6:

NOPジューリングできる. 次の加算に対して割り当てるマイクロ命

7:

NOP

令の候補として ADD1 と ADD2 があるとする. ADD2 を割り

8:

NOP

当てた場合, 前の 2 つの命令と依存関係があるため 5 サイクル

1:.reg a,b,c,d,e,f,g1:

2:.rf GRB h

2:L1:3:.base A1

3:6:

SUB g,g,g

7:L1:8:LDW *A2++,a

図 9 にスケジューリングの例を示す. 2 つの乗算に対してす9:

LDW *B2++,b9:

NOP目から実行することになる. ADD1 を割り当てた場合, 前の命

10:MPY a,b,c10:

MPY_M1_ABA A4,B4,A5

令がそれぞれフォワーディングユニットである FWU0, FWU1

11:

ADD c,g,g11:

NOPにフォワーディングしたデータを受け取ることができるため命12:

SUB h,1,h12:

ADD_L1_AAA A5,A3,A3

B L113:

CB_S1

13:[h](a) リニアアセンブリ
図8L1,B5(b) アセンブリ

リニアアセンブリと出力

令間依存距離が縮まり, 3 サイクル目に実行することができる.
クラスタ化されたプロセッサの場合, ある変数に対してそれを定義する命令と使用する命令が別々のクラスタに割り振られる場合が生じる. TMS320C62x の「クロスパス」のように専用のパスを使用してそれぞれのクラスタにアクセスできるマイク

ジスタも指定できる. 図 8(a) 1 から 4 行目の ”.” から始まる記

ロ命令が存在すれば, そのマイクロ命令を割り当てればよいが,述はディレクティブであり, 以下のことをユーザーが指定する.

そうでない場合はレジスタ間のデータ転送を行う命令を挿入し（ 1 ） .reg (1 行目)て, マイクロ命令を割り当てられるようにする. また, レジスタ変数がレジスタに格納されることを宣言する.の数が足りない場合はスピルコードを追加する. 追加する命令（ 2 ） .rf (2 行目)

は, アーキテクチャ記述中のデータ転送表から選択し, 他の命令変数が指定したレジスタファイルのレジスタに格納されることと共にスケジューリングする.

を宣言する. この例は, 変数 h を GRB に割り当てることを指オペランドの中に read, write の両方が行われている場合定している.

は, read と write を別個のオペランドとして扱う. 例えば, LDW（ 3 ） .base, .offset (3, 4 行目)*p++, a というリニアアセンブリ命令はオペランド p に割り当

データ転送命令でデータを格納するアドレスを得るための, ベーてられるレジスタからデータを読み, ポストインクリメントをスレジスタとオフセットを指定する. スケジューラがスピル/リ行っているが, この p の read, write それぞれを別オペランドとロードコードを追加する際にメモリ中にデータを格納できるアして扱う.

ドレスをユーザが指定するために記述する.
関数の呼び出し規約に関しては, リニアアセンブラは特別なプロセッサの中には複数のレジスタを使用して一つのデータを扱うレジスタペアを持つものがある. プロセッサによってア処理を行わず, ユーザが必要な処理 (引数の受け渡しやレジスセンブリ中でのレジスタペアのシンタックスは異なり, ペアをタの保存など) をリニアアセンブリで直接コーディングするも構成するレジスタすべてを記述するものと, ペアの一部のみをのとする.

記述するものが存在する. 一部のみを記述する場合, ペアを構

4. コード生成の方式

成するオペランドがどれかを判断しにくいため, 本稿で扱うリ
ニアアセンブリではペアを構成するオペランドすべてを記述す

リターゲッタブル・リニアアセンブラの処理の流れを図 2 にるものとする. それぞれの変数がペアであることは命令の情報示す. リニアアセンブリ入力に対して前処理系が構文解析を行に記述し, ペアを構成できるようにレジスタ割り当てを行う.

い, スケジューラが扱う中間表現に変換する. スケジューラは基4. 3 スケジューリング問題の定式化

本ブロックの中間表現毎に, アーキテクチャ記述に基づきコーリニアアセンブリ命令の集合を A とする. 各命令はオペレードの最適化を行う.

4. 1 前 処 理 系

ション, オペランド, 依存の情報を持つ. ある命令 a ∈ A を実行可能なマイクロ命令の集合を P (a) とする. i 番目のオペランド

リニアアセンブリ入力を, 分岐命令やラベルの位置で分割し,が read であるか, write であるかを rw(a, i), オペランドに使用基本ブロック分割を行う. 命令が分岐命令かどうか, またそれしている変数を v(a, i), オペランドに対して依存関係のある命が条件付かどうかはマイクロ命令記述から判定する.

令と, そのオペランド番号のペアの集合を D(a, i) とする.

4. 2 スケジューラ
アーキテクチャ記述を基に, スケジューラは前処理系が出力する中間表現中の各命令に対して, 実行にかかるサイクル数がリニアアセンブリ命令中の変数の集合を V とし, v ∈ V に対して, r(v, t) を, 時刻 t において変数 v のデータが格納されている記憶要素とする.

なるべく少なくなるように, 命令の実行開始サイクルとマイクレジスタなどの記憶要素 (レジスタなど) の集合を S とし,ロ命令を決定する. 各命令のオペランドにはレジスタを割り当s ∈ S が所属する記憶要素クラス (レジスタファイルなど) を–4–

(2-a) RAW 依存の場合
依存 (a2 , j) ∈ D(a1 , i) に対して, rw(a1 , i) = read, rw(a2 , j) =write の時, この依存は RAW である. 依存関係のある命令 a2が write するフォワーディング (f wu, f ws) ∈ F W W (p(a2 ), j)の中に, f wr(p(a1 ), i) = f wu を満たすものがある時, a1 はc(a2 ) + f ws < c(a1 ) + f wrs(p(a1 ), i)を満たすサイクルに実行開始できる.

(2-b) WAR 依存の場合
依存 (a2 , j) ∈ D(a1 , i) に対して, rw(a1 , i) = write, rw(a2 , j) =read の 時, こ の 依 存 は WAR で あ る.
図9

命令スケジューリングの例

b(s) とする.
マイクロ命令の集合を P とする. p ∈ P がの i 番目のオペ

ランドの記憶要素にアクセスするステージを e(p, j), アクセス

命 令 a1 が write するフォワーディング (f wu, f ws) ∈ F W W (p(a1 ), i) の中に,f wr(p(a2 ), j) = f wu を 満 た す も の が あ る 時, 命 令 a1 がf wu に最も早くデータをフォワーディングするステージを
x = min f ws(f wu) としたとき, a1 はc(a2 ) + f wrs(p(a2 ), j) < c(a1 ) + x

する記憶要素クラスを s(p, i) とする. p が k ステージ目で使用する資源の集合を R(p, k) とする. p を実行するスロットをslot(p) とし, slot(p) は R(p, 1) に含むものとする. p が所属する命令グループを g(p) とし, 長命令としてディスパッチ可能なマイクロ命令グループの組の集合を L とする.
プロセッサがフォワーディングを行う場合, フォワーディングの情報も必要になる. p の i 番目のオペランドが read するを満たす必要がある.

(2-c) WAW 依存の場合
依存 (a2 , j) ∈ D(a1 , i) に対して, rw(a1 , i) = write, rw(a2 , j) =write の時, この依存は WAW である. 命令 a1 が write する

フォワーディング (f wu1 , f ws1 ) ∈ F W W (p(a1 ), i), 命令 a2 がwrite するフォワーディング (f wu2 , f ws2 ) ∈ F W W (p(a2 ), j)

フォワーディングユニットを f wr(p, i), i 番目のオペランドがの中に, f wu1 = f wu2 を満たすものがある時, 命令 a1 がフォワーディングユニットからデータを read するステージを

f wu1 に最も早くデータをフォワーディングするステージをf wrs(p, i) とする. p の i 番目のオペランドが write するフォ

x1 = min f ws(f wu1 ) 命令 a2 が f wu2 に最も早くデータをワーディングユニットとステージのペアの集合を F W W (p, i)フォワーディングするステージを x2 = min f ws(f wu2 ) としたとする.

とき, a1 はスケジューラはリニアアセンブリの各命令 a ∈ A に対してその命令を実行するマイクロ命令 p(a) と, 実行開始サイクルc(a) を決定し, a の各オペランド i に対して割り当てる記憶要
素 r(a, i) を決定する. p(a) は P (a) から選択する.
命令パターンを決定した際, 命令の実行開始サイクルはデー
タ依存関係, 資源制約を考慮し決定する.

(1) 資源制約
すべての時刻において, 同じ資源は高々1 回までしか使用できな
い. a1 , a2 ∈ A に対して, k1 , k2 を任意のステージとしたとき,c(a1 )+k1 = c(a2 )+k2 ならば R(p(a1 ), k1 )∩R(p(a2 ), k2 ) = φでなければならない.

(2) データ依存制約ある命令 a1 ∈ A の実行開始サイクルを決定する際, すべての依存 (a2 , j) ∈ D(a, i) に対してc(a2 ) + e(p(a2 ), j) < c(a) + e(p(a), i)を満たす必要がある.
フォワーディングを行う場合は依存の種類により, 次の制約

c(a2 ) + x2 < c(a1 ) + x1
を満たす必要がある.

(3) ディスパッチ制約
すべての時刻 t に対して, At = {a ∈ A | c(a) = t} とした時に,{g(p(a)) | a ∈ At } ∈ Lを満たす必要がある.

(4) アクセスする記憶要素クラスの制約
任意のリニアアセンブリ命令 a1 , a2 ∈ A の i, j 番目のオペラン
ドについて

v(a1 , i) = v(a2 , j) ならば (p(a1 ), i) = s(p(a2 ), j)である必要がある. s(p(a1 ), i) =| s(p(a2 ), j) であるならば,s(p(a1 ), i) から s(p(a2 ), j) への転送命令を追加する必要がある.
(5) 記憶要素の割り当ての制約命令 a ∈ A の i 番目のオペランドに記憶要素を割り当てる際に, 以下の制約を満たす必要がある.

(5-a) 記憶要素クラスの制約を満たす必要がある. 扱うフォワーディングモデルは完全フォ割り当てる記憶要素の所属する記憶要素クラスと, マイクロ命

ワーディング [6] とする.

令のアクセスする記憶要素クラスが一致しなければならない.

–5–すべての a ∈ A について,b(r(a, i)) = s(p(a), i).
(5-b) 記憶要素の制約| v2 について, 同じサイク
異なる２つの変数の v1 , v2 ∈ V, v1 =ル t で同じ記憶要素が割り当てられていてはならない.

| r(v2 , t).
∀t : r(v1 , t) =(5-c) 同一命令中のオペランドの制約
同一命令の複数オペランドが同じ変数であったならば, 同じレジスタを割り当てなければならない.

v(a, i) = v(a, j) であれば, r(a, i) = r(a, j).
(5-d) レジスタペア

文献[1] http://archc.sourceforge.net/.
[2] O. Schliebusch, A. Hoﬀman, A. Nohl, G. Braun, H. Meyr:“Architecture Implementation Using the Machine Description Language LISA,” in Proc. ASP-DAC 2002, pp. 239—244(Jan. 2002).
[3] R. Leupers and P. Marwedel: Retargetable Compiler Technology for Embedded Systems, Kluwer Academic Publishers(2001).
[4] Texas Instruments: TMS320C6000 Optimizing Compiler
User’s Guide (Mar. 2000).
[5] 武内良典，小林真輔，今井正治: “特定用途向きインストラクショ
ンセットプロセッサ開発環境 ASIP Meister と DSP アプリケーションへの応用,” 信学技報, CAS2002-61 (Sept. 2002).
[6] 平岡佑介, 石浦菜岐佐, 今井正治: “プロセッサ仕様記述からの命令依存距離抽出,” 信学技報, VLD2004-119/CPSY2004-85(Jan. 2005).
[7] http://www.ti.com/.
[8] http://jp.fujitsu.com/.
[9] http://www.nxp.com/.

レジスタペアを扱う場合は, S の要素 s に対して使用する記憶要素の集合を U (s) とする. レジスタペアの記憶要素 s1 ∈ S を割り当てる時には U (s1 ) の要素である記憶要素すべてが使用可能でなければならない.

5. プロトタイプの実装
リターゲッタブル・リニアアセンブラのプロトタイプを Cyg-win 上で Perl5.8.7 で実装した. プロトタイプのスケジューラはリストスケジューリングを行い, 転送命令はマイクロ命令を割り当てる際に, アクセスするレジスタファイルの不一致やレジスタの不足が生じたときのみ追加するとした. TMS320C62x の一部約 50 のマイクロ命令を含む約 2500 行のアーキテクチャ記述を作成した. プロトタイプにこのアーキテクチャ記述と 20 行程度のアセンブリを入力とした場合に出力を得るのに要した時間は約 0.5 秒であった (Core2 T5500 1.66GHz, メモリ 1GB).

6. む す び
本稿ではリターゲッタブル・リニアアセンブラとその構成法を提案した. 今後, TriMedia TM1300 など他のアーキテクチャをターゲットとすることを目標に, これらのターゲットに合わせてスケジューラが行う処理を改良して行く予定である. 今回開発したスケジューラは, 定式化の検証を主目的に極力簡易な実装としたが, 出力するコードの質の向上のために, 最適化機能を強化したスケジューラを開発していくことも課題である. また, 現在のスケジューラは基本ブロックごとにスケジューリングを行っているが, 大きなスーパーブロックやハイパーブロックに定式化を拡張することも今後の課題に挙げられる.
謝辞 本研究を進めるにあたり, 御助言, 御指導を頂きました
大阪大学今井研究室の関係諸氏に感謝致します. 種々のアドバイスを頂きました, 日本電気株式会社の池川将夫氏, 久村孝寛氏に感謝致します. また, スケジューリング問題の定式化についてアドバイスを頂いた益井勇気氏, アーキテクチャ記述の作成を行って頂いた浅井圭悟氏をはじめ, 支援と助言を頂いた石浦研究室の諸氏に感謝致します.

–6–