JPH0944362A - コンパイラ - Google Patents

Abstract

(57)【要約】 【課題】 プロセッサのハードウエア規模を増加させる
ことなく、目的プログラムのコードサイズの増加を回避
し、実行の高速化を図ることである。 【解決手段】 前記目的プログラムの命令を解析して、
前記命令列中に分岐及び分岐先を持たないコード列であ
る基本ブロック毎に、前記目的プログラムを分割する解
析処理手段Ｓ１００と、この解析処理手段Ｓ１００で分
けられた所定の基本ブロックについて、ロード命令を抽
出し、この抽出されたロード命令のデータキャッシュの
ミス時のレジスタ書き戻しステージにおけるクロックサ
イクルが、レジスタに書き込まない命令のレジスタ書き
戻しステージとなるように命令の順序の入れ換えを、前
記基本ブロック内で行なう最適化処理手段Ｓ２００と、
この最適化処理手段Ｓ２００にて最適化された目的プロ
グラムの出力を行う出力手段Ｓ３００とを備えてある。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はコンパイラに関し、
特に、パイプラインのインターロックを回避するコンパ
イラに関する。

【０００２】

【従来の技術】今日、ほとんどのプログラミングは高級
言語でなされる。コンパイラの第１目標は正確さであ
る。すべての誤りのないプログラムは正確にコンパイル
されなければならない。第２目標は普通、コンパイルさ
れたコードの速度である。高速コンパイル、デバッグ支
援、言語間での相互利用性など、他の目標はすべてこれ
ら２つの目標と比べると優先順位が低い。通常、コンパ
イラの多数のパスを経て、高級言語による抽象度の高い
表現が次第により抽象度の低い表現に変換され、命令セ
ットによる記述にまで行きつく。

【０００３】コンパイラのパス構造を図１１に示す。コ
ンパイラは普通２パスから４パスで構成され、より高度
のコンパイラはそれ以上のパスからなる。ここで、パス
とは、コンパイラが全プログラムを読んで、変換を行う
１つのフェーズを表す。最適化パスはあってもなくても
よい。すなわち、より高速コンパイルが必要とされ、コ
ードの質が低くても構わない場合には、最適化パスは省
略される。

【０００４】コンパイラによってなされる最適化を変換
の形態によって分類すると、以下のようになる。

【０００５】１．高レベル最適化 ソース・プログラム・レベルで行うことが多く、後続の
最適化パスへ情報を出力する、マシンに対して独立した
最適化を行う。手続呼び出しの手続きを本体で置き換え
る（インライン展開）手続き最適化等を行う。

【０００６】２．局所最適化 直列実行される命令コード部分（基本ブロック）内での
最適化を行う。同一計算が２度生起する際に、一方を値
のコピーで置き換える共通式の除去、定数が割り付けら
れる変数が生起する際に、それを定数で置き換える定数
伝搬、及び式の評価に必要とされる資源を最小化するよ
うに式を再構成するスタック長の縮小等を行う。

【０００７】３．広域最適化 局所最適化を分岐命令を越えられるように拡張し、ルー
プの最適化をめざした変換を導入して分岐を越えた領域
での最適化を行う。局所最適化の場合と同じであるが、
分岐を越えた領域に対して適用する大域共通式の除去、
分が割り付けられる変数Ａの箇所すべてをＸで置き換え
るコピー伝搬、ループ内の各反復で同一値を計算する命
令をループ外に移動するコード移動、及び、ループ内の
配列アドレス計算の単純化／除去を行う誘導変数の除去
等を行う。

【０００８】４．レジスタ割付け レジスタを効率良く活用するための最適化を行う。メモ
リアクセスを低減して処理性能を向上させる。

【０００９】５．マシン依存の最適化 マシン固有の特徴を活かした試みより最適化を行う。マ
シンに関する知識に依存する。パイプラインの性能を引
き出すため、命令を並べ換えるパイプライン・スケジュ
ーリング、及び、分岐先へ届くかぎりの最小のディスプ
レースメントを選択する分岐オフセットの最適化等を行
う。

【００１０】一方、パイプライン・スケジューリングに
は、遅延スロットを利用した最適化がある。ロード命令
は、オペランドをメモリからプロセッサレジスタに読み
込み、後続の命令が使用できるようにする。メモリの動
作速度は通常、プロセッサ・クロック速度よりはるかに
遅いため、命令パイプラインを使用しているプロセッサ
内に格納されている後続命令は、ロードされるオペラン
ドを直ちに使用できるわけではない。このデータ依存関
係を図１２に示す。この図１２において、第１命令によ
りロードされたオペランドは、第２命令の“Ａ”サイク
ルでは使用できない。この依存関係を処理する一つの方
法は、ロードされるデータが使用可能になるまで、第２
命令の実行に余分なクロックサイクルを挿入することで
パイプラインを遅らせる方法である。この方法では実行
に遅延が生じることは明らかで、したがって、「サイク
ル／命令」の要因は大きくなる。

【００１１】このデータ依存関係を処理するために、大
部分のＲＩＳＣ設計ではすべてのロード命令には本質的
に待ち時間、つまりロード遅延があることを認めたうえ
で、コンパイラにそのことを意識させる方法を採用して
いる。上記の例では、ロード遅延、つまり命令分の待ち
時間が生じている。ロードの直後の命令は、ロード遅延
スロット内にあるという。このスロット内の命令がロー
ドからのデータを必要としない場合は、パイプラインを
遅らせる必要はない。コンパイラは命令を再編すること
を行う。ロード命令とロード遅延スロット内の命令の間
にデータ依存関係がないようにする一番簡単な方法は、
図１３のようにＮＯＰ（No Operation）命令をスロット
に入れることである。これにより、パイプラインの停止
状態をハードウエアで制御する必要はなくなったが、遅
延スロットをＮＯＰで埋める方法は、ＮＯＰ命令により
コードサイズが大きくなり、またＮＯＰが有効な作業を
しているわけでもないため、パイプライン・ストリーム
を効果的に使いこなしているとはいえない。

【００１２】データ依存関係を処理するためのさらに効
果的な解決方法は、ロード遅延スロットを実際のタスク
が行う命令で埋める方法である。最適化機能が優れてい
るコンパイラは、特にロード遅延が１サイクルだけの場
合、通常はこの方法を採用する。図１４の例は、コンパ
イラがデータ依存関係を処理するために命令を再編成す
る様子を示している。Ａｄｄ命令は、３番目のＬｏａｄ
命令から得られるデータが使用できるかどうかに依存し
ていないため、遅延スロットを命令で埋めてパイプライ
ンを完全に使いこなすことが出来る。

【００１３】以上のようにして、従来からコンパイラ
は、上述のような最適化のための処理を行うことで、処
理の効率化、高速化を図っている。

【００１４】

【発明が解決しようとする課題】しかしながら、従来の
コンパイラの最適化は、キャッシュがヒットすることを
前提としている。データキャッシュがミスした場合に
は、不必要なパイプラインのインターロックが生じる可
能性がある。たとえば、従来例のロード命令の場合を説
明する。

【００１５】ロード命令でデータキャッシュがミスした
場合、ロードされるオペランドはやはり直ちに使用でき
るわけではない。データキャッシュがミスした場合、外
部メモリにアクセスするわけであるが、大部分のＲＩＳ
Ｃではパイプラインがインターロックし、処理が停止し
てしまう。

【００１６】そこで、データキャッシュがミスした場合
でも、アクセス中のオペランドが使用される命令が出現
するまで、後続の命令を続けるノンブロッキング・ロー
ドという方法がある。ノンブロッキング・ロードを用い
れば、リフィルによるインターロックを抑制できるが、
命令列はデータキャッシュがヒットしていることを想定
して生成されているので、次のような問題が現れる。

【００１７】データキャッシュのリフィルに４サイクル
かかる場合を想定し、図１５のような命令列を考える。
データキャッシュにミスが生じない場合は、パイプライ
ンはインターロックすることなく進み、処理が進行す
る。データキャッシュにミスが生じた場合は以下のよう
になる。すなわち、ロード命令に続く命令は、ｒ２を使
用していないので、データキャッシュがミスを起こして
も、ノンブロッキング・ロードにより処理を続けること
ができる。以下のような５段のパイプラインを想定する
と、実行中のパイプラインの様子は図１６の通りであ
る。

【００１８】サイクル＃４でデータキャッシュにミスが
発生すると、リフィル動作を開始する。ノンブロッキン
グ・ロードにより後続の処理は続けられる。ところがリ
フィル終了後に、オペランドをレジスタに書き込もうと
すると、後続のａｄｄ命令もレジスタに書き込もうとす
るので衝突してしまう。レジスタの資源競合が発生して
しまう。ａｄｄ命令のレジスタ書き込みを遅らせるた
め、パイプラインをインターロックしなければならな
い。これを防ぐためにはレジスタの入力ポートを増やし
たり、レジスタ・リネーミングの機構を用意したりすれ
ばよいが、いずれもハードウエアの規模が大きくなって
しまい、コンパイラ技術だけでこの問題を回避する方法
はなかった。

【００１９】本発明は上記事情に鑑みてなされたもので
あり、その目的とするところは、データキャッシュがミ
スした場合でも、インターロックを回避し得る最適化を
図ることで、プロセッサのハードウエア規模を増加させ
ることなく、目的プログラムのコードサイズの増加を回
避し、実行の高速化を図ることのできるコンパイラを提
供することにある。

【００２０】

【課題を解決するための手段】上記目的を達成するため
に、第１の発明の特徴は、高級言語あるいはアセンブリ
言語から目的プログラムを生成するコンパイラにおい
て、データキャッシュがミスした場合に、レジスタの資
源競合によりパイプラインがインターロックを起こさな
いように、前記目的プログラムの命令の順序を入れ換え
る最適化処理手段を有することである。

【００２１】上記構成によれば、目的プログラムのコー
ドサイズの増加を回避し、実行の高速化を図ることがで
きるのである。

【００２２】また、上記目的を達成するため、第２の発
明の特徴は、少なくとも、レジスタ書き戻しステージを
有する命令パイプラインを使用するプロセッサで用いら
れ、高級言語あるいはアセンブリ言語から目的プログラ
ムを生成するコンパイラにおいて、前記目的プログラム
の命令を解析して、前記命令列中に分岐及び分岐先を持
たないコード列である基本ブロック毎に、前記目的プロ
グラムを分割する解析処理手段と、この解析処理手段で
分けられた所定の基本ブロックについて、ロード命令を
抽出し、この抽出されたロード命令のデータキャッシュ
のミス時のレジスタ書き戻しステージにおけるクロック
サイクルが、レジスタに書き込まない命令のレジスタ書
き戻しステージとなるように命令の順序の入れ換えを、
前記基本ブロック内で行なう最適化処理手段と、この最
適化処理手段にて最適化された目的プログラムの出力を
行う出力手段と、を具備することである。

【００２３】上記構成において、本発明は、マイクロプ
ロセッサなどの情報処理装置のプログラムにおいて、高
級言語、あるいはアセンブリ言語から目的プログラムを
生成する際に、プログラムの因果律が変わらない範囲
で、データキャッシュのミス時にパイプラインをインタ
ーロックさせないように、命令列の順序を入れ換えるよ
うする。すなわち、 １．まず、高級言語あるいはアセンブリ言語がコンパイ
ルされ、目的プログラが生成される。更に各種最適化処
理をされたアセンブリ・コードが解析処理手段に入力さ
れる。

【００２４】２．解析処理手段にて命令の依存関係、レ
ジスタの依存関係などを検索し、命令を入れ換えてもプ
ログラム処理の因果律が変わらない範囲を特定する。

【００２５】３．最適化処理手段では、解析処理手段で
特定した依存関係などを検索し、各命令（イミディエイ
トなどの数値データを含む）の順序を入れ換えて、デー
タキャッシュのミス時にパイプラインをインターロック
させないように置き換える。ここで、この置き換えに
は、まず、ロード命令を抽出し、この抽出されたロード
命令のデータキャッシュのミス時のレジスタ書き戻しス
テージにおけるクロックサイクルが、レジスタに書き込
まない命令のレジスタ書き戻しステージとなるように命
令の順序の入れ換えようにする。このようにすることに
より、データキャッシュがミスした場合でも、インター
ロックを回避し得る最適化を図ることができるのであ
る。また、前記レジスタに書き込まない命令は、各プロ
セッサのアーキテクチュアにより異なるが、例えば、Ｒ
３０００（ＭＩＰＳ社）ではｍｕｌ命令が該当する。

【００２６】４．最適化されたアセンブリ・コードを出
力手段により出力する。なお、前記出力手段により出力
されるものとしては、ディスプレイ装置、プリンタ装置
等の出力のほか、メモリ装置やディスク装置等の記憶装
置が含まれる。

【００２７】以上のような構成により、パイプラインが
インターロックを起こさないように、目的プログラムの
命令の順序を入れ換え、目的プログラムのコードサイズ
の増加を回避し、実行の高速化を図ることができるので
ある。

【００２８】

【発明の実施の形態】以下、図面を用いて本発明の実施
の形態を説明する。図１は、命令列最適化方式の処理手
順を示したフローチャートである。本処理は、大きく分
けて前処理である解析処理Ｓ１００と、本処理である最
適化処理Ｓ２００とに分けられる。

【００２９】本実施の形態における入力は高級言語から
コンパイラにより生成された、あるいは人手で書かれた
アセンブリ言語プログラムであり、出力は命令順を入れ
換えられたアセンブリ言語プログラムである。一般にコ
ンパイルの過程では、さまざまな目的を持った最適化が
行われる。本発明の要旨とする最適化と、他の最適化を
行う順序は、処理手順、処理順序には直接依存すること
なくコンパイラを構成することができる。

【００３０】解析処理Ｓ１００は、目的プログラムの命
令を解析して、前記命令列中に分岐及び分岐先を持たな
いコード列である基本ブロック毎に、前記目的プログラ
ムを分割するための処理を行う。すなわち、プログラム
の基本ブロック（命令列中に分岐及び分岐先を持たない
コード列）を検索し、基本ブロック内の命令列に対し、
それらの命令の依存関係、レジスタの依存関係を解析
し、命令の入れ換えによって、処理の因果律が変化しな
い範囲を特定する。

【００３１】最適化処理Ｓ２００では、解析処理Ｓ１０
０で解析された各基本ブロックをひとつの処理単位とし
て、順次最適化処理を施していく。本実施の形態では、
解析処理手段で分けられた所定の基本ブロックについ
て、ロード命令を抽出し、この抽出されたロード命令の
データキャッシュのミス時のレジスタ書き戻しステージ
におけるクロックサイクルが、レジスタに書き込まない
命令のレジスタ書き戻しステージとなるように命令の順
序の入れ換えを、前記基本ブロック内で行なう。

【００３２】出力処理Ｓ３００で、最適化されたアセン
ブリ・リストを出力する。出力ステップＳ３００により
出力されるものとしては、ディスプレイ装置、プリンタ
装置等の出力のほか、メモリ装置やディスク装置等の記
憶装置が含まれる。

【００３３】以下、最適化処理Ｓ２００の詳細を説明す
る。最適化処理Ｓ２００では、命令の順序に関して全て
の組合せを考慮し、できる限りインターロックを発生し
ないような最適解を、シラミ潰しに探す方法も考えられ
る。しかし、この方法は現実的ではないので、あるい
は、基本ブロック内の命令に対して、以下の処理を施す
方法も考えられる。

【００３４】図２に示した最適化は以下のような場合を
想定している。すなわち、データキャッシュのリフィル
動作には、Ｔサイクル必要であるとする。あるロード命
令でデータキャッシュのミスが発生した場合、上記ロー
ド命令からＴ命令後の命令がレジスタへの書き込みを行
う場合、インターロックを発生してしまう。このインタ
ーロックを回避するための最適化である。以下、図２を
用いて説明する。

【００３５】Ｓ２０１にてロード命令の集合をＬＧ０＝
Ｌｎとする。移動禁止領域の集合をＤＧ＝Ｄｎ＝φとす
る。Ｓ２０２にてＬＧ０に属する全てのロード命令に対
して、命令間の依存関係を満たす制約下で移動可能な領
域であり、ＤＧと重ならない領域を求める。ここでは領
域Ａｎと呼ぶことにする。領域Ａｎをもつロード命令の
集合をＬＧ１＝Ｌｎとする。

【００３６】次に、Ｓ２０３にてＬＧ１＝φのときは終
了し、それ以外の場合には、Ｓ２０４へ進む。Ｓ２０４
にて、各ロード命令Ｌｎに対して、領域Ａｎにおいて他
の全てのロード命令の領域（Ａｍ≠ｎ）と重ならない領
域を求める。ここでは領域Ｂｎと呼ぶことにする。領域
Ｂｎをもつロード命令の集合をＬＧ２＝Ｌｎとする。集
合ＬＧ３＝φとする。

【００３７】次に、Ｓ２０５にて、ＬＧ２＝φのときは
後述するＳ２１３へ進み、それ以外の場合には、Ｓ２０
６へ進む。Ｓ２０６にて基本ブロック内からＬＧ０全て
の領域Ｂｎ、後述するＤＧを取り去った領域を求める。
ここでは領域Ｃと呼ぶことにする。

【００３８】次に、Ｓ２０７にて、ＬＧ２から任意のロ
ード命令Ｌｎを取り出し、領域Ｂｎに属する全ての命令
から、命令間の距離が前方の場合はＴ、後方の場合は
（Ｔ−１）である命令の集合ＩＧ＝Ｉｎを求める。Ｓ２
０８にて、ＩＧに属する命令の中で、領域Ｂｎ∪領域Ｃ
に含まれ、レジスタに書き込みを行わない命令の集合を
ＣＧ＝Ｃｎとする。

【００３９】次に、Ｓ２０９にて、ＣＧ＝φのときはＳ
２１２へ進み、それ以外の場合にはＳ２１０へ進む。Ｓ
２１０にて、ＣＧから任意の命令Ｃｎを選び、領域Ｂｎ
内の、命令Ｃｎから距離Ｔの位置に、ロード命令Ｌｎを
挿入する。Ｓ２１１にて、ロード命令Ｌｎから命令Ｃｎ
に至る命令列を、移動禁止領域Ｄｎとし、集合ＤＧに入
れる。ＬＧ０，ＬＧ１からＬｎを取り除く。Ｌｎを集合
ＬＧ３へ入れる。

【００４０】次に、Ｓ２１２にて、ＬＧ２＝φかつＬＧ
３＝φのときはＳ２１３へ進み、ＬＧ２＝φかつＬＧ３
≠φのときはＳ２０２へ進み、いずれでもないときはＳ
２０７へ進む。Ｓ２１３では、ＬＧ１から任意のロード
命令Ｌｎを取り出し、領域Ａｎに属する全ての命令か
ら、命令間の距離がＴである命令の集合ＩＧ＝Ｉｎを求
める。Ｓ２１４にて、ＩＧに属する命令の中で、レジス
タに書き込みを行わない命令の集合をＣＧ＝Ｃｎとす
る。

【００４１】次に、Ｓ２１５にてＣＧ＝φかつＬＧ１＝
φのときは終了する。ＣＧ＝φかつＬＧ１≠φのときは
Ｓ２１３へ進み、いずれでもないときはＳ２１６へ進
む。Ｓ２１６にて、ＣＧから任意の命令Ｃｎを選び、領
域Ｂｎ内の、命令Ｃｎから距離Ｔの位置に、ロード命令
Ｌｎを挿入する。Ｓ２１７にて、ロード命令Ｌｎから命
令Ｃｎに至る命令列を、移動禁止領域Ｄｎとし、集合Ｄ
Ｇに入れる。ＬＧ０からＬｎを取り除き、Ｓ２０２へ進
み、再び処理を行い、全ての領域に関して処理を行う。

【００４２】次に、具体例を用いて、本発明の最適化手
法の操作について説明する。以下では、パイプラインに
ＭＩＰＳ社のＲ３０００を例として用いる。Ｒ３０００
のパイプラインを図３に示す。図４はアセンブリ言語で
書かれた再帰型フィルタのプログラムである。プログラ
ムの内容は、今井聖，“ディジタル信号処理”，廣済堂
産報出版株式会社、ISBN4-386-07088-5 を参照された
い。アセンブリ言語命令の詳細は、Gerry Kane and Joe
Heinrich,“MIPS RISC Architecture”，Prentice-Hal
l,Inc.，ISBNO-13-590472-2 を参照されたい。

【００４３】以下の例ではデータキャッシュのリフィル
動作必要なサイクル数Ｔ＝３の場合を説明する。図４の
アセンブリプログラムに対して解析処理Ｓ１００で依存
関係を解析すると、Ｂ１〜Ｂ６の６つの基本ブロックに
分解される。ここでは、基本ブロックＢ３に最適化処理
を施す場合を説明する。基本ブロックＢ３の命令間での
依存関係を表す有向グラフを図５に示す。次に、最適化
処理Ｓ２００で、図６に示す基本ブロックＢ３に対し
て、最適化処理を施す。以下、図２に示した最適化処理
のステップごとに各パラメータの状況を示す。

【００４４】 Ｓ２０１ ＬＧ０＝｛Ｉ１，Ｉ２，Ｉ３，Ｉ４，Ｉ１７，Ｉ３０，Ｉ４３，Ｉ５ ６｝ ＤＧ＝φ Ｓ２０２ Ａ１＝φ Ａ２＝φ Ａ３＝φ Ａ４＝｛Ｉ５，…，Ｉ１３｝ Ａ１７＝｛Ｉ６，…，Ｉ１６，Ｉ１８，…，Ｉ２６｝ Ａ３０＝｛Ｉ１９，…，Ｉ２９，Ｉ３１，…，Ｉ３９｝ Ａ４３＝｛Ｉ３２，…，Ｉ４２，Ｉ４４，…，Ｉ５２｝ Ａ５６＝｛Ｉ４５，…，Ｉ５５，Ｉ５７｝ ＬＧ１＝｛Ｉ４，Ｉ１７，Ｉ３０，Ｉ４３，Ｉ５６｝ Ｓ２０３ Ｓ２０４へ Ｓ２０４ Ｂ４＝｛Ｉ５｝ Ｂ１７＝｛Ｉ１４，Ｉ１５，Ｉ１６，Ｉ１８｝ Ｂ３０＝｛Ｉ２７，Ｉ２８，Ｉ２９，Ｉ３１｝ Ｂ４３＝｛Ｉ４０，Ｉ４１，Ｉ４２，Ｉ４４｝ Ｂ５６＝｛Ｉ５３，Ｉ５４，Ｉ５５｝ ＬＧ２＝｛Ｉ４，Ｉ１７，Ｉ３０，Ｉ４３，Ｉ５６｝ ＬＧ３＝φ Ｓ２０５ Ｓ２０６へ Ｓ２０６ Ｃ＝｛Ｉ５７｝ Ｓ２０７ Ｌ４＝Ｉ４を選ぶ ＬＧ２＝｛Ｉ１７，Ｉ３０，Ｉ４３，Ｉ５６｝ ＩＧ＝｛Ｉ２，Ｉ７｝ Ｓ２０８ ＣＧ＝φ Ｓ２０９ Ｓ２１２へ Ｓ２１２ Ｓ２０７へ Ｓ２０７ Ｌ１７＝Ｉ７を選ぶ ＬＧ２＝｛Ｉ３０，Ｉ４３，Ｉ５６｝ ＩＧ＝｛Ｉ１１，Ｉ１２，Ｉ１３，Ｉ１４，Ｉ１５，Ｉ１６，Ｉ１ ７，Ｉ１８，Ｉ２０｝ Ｓ２０８ ＣＧ＝｛Ｉ１８｝ Ｓ２０９ Ｓ２１０へ Ｓ２１０ Ｃ１７＝Ｉ１８を選ぶ Ｉ１５の位置にＩ１７を挿入する Ｓ２１１ Ｄ１７＝｛Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１８｝ ＤＧ＝｛Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１８｝ ＬＧ０＝｛Ｉ１，Ｉ２，Ｉ３，Ｉ４，Ｉ３０，Ｉ４３，Ｉ５６｝ ＬＧ１＝｛Ｉ４，Ｉ３０，Ｉ４３，Ｉ５６｝ ＬＧ３＝｛Ｉ１７｝ Ｓ２１２ Ｓ２０７へ Ｓ２０７ Ｌ３０＝Ｉ３０を選ぶ ＬＧ２＝｛Ｉ４３，Ｉ５６｝ ＩＧ＝｛Ｉ２４，Ｉ２５，Ｉ２８，Ｉ２９，Ｉ３０，Ｉ３１，Ｉ３ ２，Ｉ３３｝ Ｓ２０８ ＣＧ＝｛Ｉ３１｝ Ｓ２０９ Ｓ２１０へ Ｓ２１０ Ｃ３０＝Ｉ３１を選ぶ Ｉ２８の位置にＩ３０を挿入する Ｓ２１１ Ｄ３０＝｛Ｉ３０，Ｉ２８，Ｉ２９，Ｉ３１｝ ＤＧ＝｛Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１８，Ｉ３０，Ｉ２８，Ｉ２ ９，Ｉ３１｝ ＬＧ０＝｛Ｉ１，Ｉ２，Ｉ３，Ｉ４，Ｉ４３，Ｉ５６｝ ＬＧ１＝｛Ｉ４，Ｉ４３，Ｉ５６｝ ＬＧ３＝｛Ｉ１７，Ｉ３０｝ Ｓ２１２ Ｓ２０７へ Ｓ２０７ Ｌ４３＝Ｉ４３を選ぶ ＬＧ２＝｛Ｉ５６｝ ＩＧ＝｛Ｉ３７，Ｉ３８，Ｉ３９，Ｉ４１，Ｉ４２，Ｉ４３，Ｉ４ ４，Ｉ４６｝ Ｓ２０８＝ＣＧ＝｛Ｉ４４｝ Ｓ２０９ Ｓ２１０へ Ｓ２１０ Ｃ４３＝Ｉ４４を選ぶ Ｉ４１の位置にＩ４３を挿入する Ｓ２１１ Ｄ４３＝｛Ｉ４３，Ｉ４１，Ｉ４２，Ｉ４４｝ ＤＧ＝｛Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１８，Ｉ３０，Ｉ２８，Ｉ２ ９，Ｉ３１，Ｉ４３，Ｉ４１，Ｉ４２，Ｉ４４｝ ＬＧ０＝｛Ｉ１，Ｉ２，Ｉ３，Ｉ４，Ｉ５６｝ ＬＧ１＝｛Ｉ４，Ｉ５６｝ ＬＧ３＝｛Ｉ１７，Ｉ３０，Ｉ４３｝ Ｓ２１２ Ｓ２０７へ Ｓ２０７ Ｌ５６＝Ｉ５６を選ぶ ＬＧ２＝φ ＩＧ＝｛Ｉ５０，Ｉ５１，Ｉ５２，Ｉ５５，Ｉ５６，Ｉ５７｝ Ｓ２０８ ＣＧ＝φ Ｓ２０９ Ｓ２１２へ Ｓ２１２ Ｓ２０２へ

【００４５】最適化処理の現時点での状態を図７に示
す。 Ｓ２０２ Ａ１＝φ Ａ２＝φ Ａ３＝φ Ａ４＝｛Ｉ５，…，Ｉ１３｝ Ａ５６＝｛Ｉ４５，…，Ｉ５５｝ ＬＧ１＝｛Ｉ４，Ｉ５６｝ Ｓ２０３ Ｓ２０４へ Ｓ２０４ Ｂ４＝｛Ｉ５，…，Ｉ１３｝ Ａ５６＝｛Ｉ４５，…，Ｉ５５｝ ＬＧ２＝｛Ｉ４，Ｉ５６｝ ＬＧ３＝φ Ｓ２０５ Ｓ２０６へ Ｓ２０６ Ｃ＝｛Ｉ１４，Ｉ１９，…，Ｉ２７，Ｉ３２，…，Ｉ４０，Ｉ５７ ｝ Ｓ２０７ Ｌ４＝Ｉ４を選ぶ ＬＧ２＝｛Ｉ５６｝ ＩＧ＝｛Ｉ２，Ｉ３，Ｉ４，Ｉ５，Ｉ６，Ｉ７，Ｉ８，Ｉ９，Ｉ１ ０，Ｉ１１，Ｉ１２，Ｉ１３，Ｉ１４，Ｉ１７｝ Ｓ２０８ ＣＧ＝｛Ｉ５，Ｉ８，Ｉ１１，Ｉ１４｝ Ｓ２０９ Ｓ２１０へ Ｓ２１０ Ｃ４＝Ｉ８を選ぶ Ｉ６の位置にＩ４を挿入する Ｓ２１１ Ｄ４＝｛Ｉ４，Ｉ６，Ｉ７，Ｉ８｝ ＤＧ＝｛Ｉ４，Ｉ６，Ｉ７，Ｉ８，Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１ ８，Ｉ３０，Ｉ２８，Ｉ２９，Ｉ３１，Ｉ４３，Ｉ４１，Ｉ４２，Ｉ４４｝ ＬＧ０＝｛Ｉ１，Ｉ２，Ｉ３，Ｉ５６｝ ＬＧ１＝｛Ｉ５６｝ ＬＧ３＝｛Ｉ４｝ Ｓ２１２ Ｓ２０７へ Ｓ２０７ Ｌ５６＝Ｉ５６を選ぶ ＬＧ２＝φ ＩＧ＝｛Ｉ４２，Ｉ４３，Ｉ４４，Ｉ４５，Ｉ４６，Ｉ４７，Ｉ４ ８，Ｉ４９，Ｉ５０，Ｉ５１，Ｉ５２，Ｉ５３，Ｉ５４，Ｉ５５，Ｉ５６，Ｉ５ ７｝ Ｓ２０８ ＣＧ＝｛Ｉ４７，Ｉ５０，Ｉ５３｝ Ｓ２０９ Ｓ２１０へ Ｓ２１０ Ｃ５６＝Ｉ５３を選ぶ Ｉ５１の位置にＩ５６を挿入する Ｓ２１１ Ｄ５６＝｛Ｉ５１，Ｉ５２，Ｉ５３，Ｉ５６｝ ＤＧ＝｛Ｉ４，Ｉ６，Ｉ７，Ｉ８，Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１ ８，Ｉ３０，Ｉ２８，Ｉ２９，Ｉ３１，Ｉ４３，Ｉ４１，Ｉ４２，Ｉ４４，Ｉ５ １，Ｉ５２，Ｉ５３，Ｉ５６｝ ＬＧ０＝｛Ｉ１，Ｉ２，Ｉ３｝ ＬＧ１＝φ ＬＧ３＝｛Ｉ４，Ｉ５６｝ Ｓ２１２ Ｓ２０２へ

【００４６】最適化処理の現時点での状態を図８に示
す。 Ｓ２０２ Ａ１＝φ Ａ２＝φ Ａ３＝｛Ｉ５，Ｉ９，Ｉ１０｝ ＬＧ１＝｛Ｉ３｝ Ｓ２０３ Ｓ２０４へ Ｓ２０４ Ｂ３＝｛Ｉ５，Ｉ９，Ｉ１０｝ ＬＧ２＝｛Ｉ３｝ ＬＧ３＝φ Ｓ２０５ Ｓ２０６へ Ｓ２０６ Ｃ＝｛Ｉ１１，…，Ｉ１４，Ｉ１９，…，Ｉ２７，Ｉ３２，…，Ｉ ４０，Ｉ４５，…，Ｉ５０，Ｉ５４，Ｉ５５，Ｉ５７｝ Ｓ２０７ Ｌ３＝Ｉ３を選ぶ ＬＧ２＝φ ＩＧ＝｛Ｉ２，Ｉ６，Ｉ７，Ｉ１１，Ｉ１２｝ Ｓ２０８ ＣＧ＝｛Ｉ１１｝ Ｓ２０９ Ｓ２１０へ Ｓ２１０ Ｃ３＝Ｉ１１を選ぶ Ｉ９の位置にＩ３を挿入する Ｓ２１１ Ｄ３＝｛Ｉ３，Ｉ９，Ｉ１０，Ｉ１１｝ ＤＧ＝｛Ｉ３，Ｉ４，Ｉ６，Ｉ７，Ｉ８，Ｉ９，Ｉ１０，Ｉ１１， Ｉ１７，Ｉ１５，Ｉ１６，Ｉ１８，Ｉ３０，Ｉ２８，Ｉ２９，Ｉ３１，Ｉ４３， Ｉ４１，Ｉ４２，Ｉ４４，Ｐ５６，Ｐ５１，Ｐ５２，Ｐ５３｝ ＬＧ０＝｛Ｉ１，Ｉ２｝ ＬＧ１＝φ ＬＧ３＝｛Ｉ３｝ Ｓ２１２ Ｓ２０２へ

【００４７】最適化処理の現時点での状態を図９に示
す。 Ｓ２０２ Ａ１＝φ Ａ２＝｛Ｉ５｝ ＬＧ１＝｛Ｉ２｝ Ｓ２０３ Ｓ２０４へ Ｓ２０４ Ｂ２＝｛Ｉ５｝ ＬＧ２＝｛Ｉ２｝ ＬＧ３＝φ Ｓ２０６ Ｃ＝｛Ｉ１２，…，Ｉ１４，Ｉ１９，…，Ｉ２７，Ｉ３２，…，Ｉ ４０，Ｉ４５，…，Ｉ５０，Ｉ５４，Ｉ５５，Ｉ５７｝ Ｓ２０７ Ｌ２＝Ｉ２を選ぶ ＩＧ２＝φ ＩＧ＝｛Ｉ６｝ Ｓ２０８ ＣＧ＝φ Ｓ２０９ Ｓ２１２へ Ｓ２１２ Ｓ２１３へ Ｓ２１３ Ｌ２＝Ｉ２を選ぶ ＬＧ１＝φ ＩＧ＝｛Ｉ６｝ Ｓ２１４ ＣＧ＝φ Ｓ２１５ 終了

【００４８】以上のような最適化処理による最適化結果
は図９のようになる。シラミ潰し法と比べると、この方
法では必ずしも最適な解は得られないが、高速に最適解
に近い近似解を得ることが出来る。この近似解を用いて
も、実用上は十分満足できる。

【００４９】具体的に本発明の効果を説明する。図１６
のような命令列を考え、図１６を図１０のようにａｄｄ
命令とｍｕｌ命令を入れ換えると、レジスタの資源競合
を回避でき、ストールを起こさない。以上のような最適
化によってインターロックを回避できるので、プログラ
ムの実行が高速になる。レジスタの入力ポートを複数持
つ場合は、書き込みレジスタが一致しないように最適化
すれば良い。この場合もレジスタ・リネーミングの機構
を用意する必要がないので、ハードウエアの規模を抑え
ることが出来る。

【００５０】

【発明の効果】以上説明したように、本発明は、高級言
語あるいはアセンブリ言語から目的プログラムを生成す
る際、目的プログラムを構成する命令において、命令の
順序を入れ換えることにより、データキャッシュがミス
を起こした場合に、レジスタの資源競合等、パイプライ
ンをインターロックさせる要因となる状況を回避するこ
とが出来、したがって目的プログラムの実行が高速にな
る。また、コンパイラによる最適化であるので、プロセ
ッサのハードウエア規模の増大を招かない。

【図面の簡単な説明】

【図１】本発明に係るコンパイラの実行を表すフローチ
ャートである。

【図２】本発明に係るコンパイラの最適化処理を表すフ
ローチャートである。

【図３】Ｒ３０００のパイプラインを示す図である。

【図４】本発明の実施の形態で用いるアセンブリプログ
ラムを示す図である。

【図５】基本ブロックＢ３の依存関係を表す有向グラフ
である。

【図６】基本ブロックＢ３を抽出したプログラムを示す
図である。

【図７】基本ブロックＢ３の最適化処理（１）を施した
プログラムを示す図である。

【図８】基本ブロックＢ３の最適化処理（２）を施した
プログラムを示す図である。

【図９】基本ブロックＢ３の最適化処理（３）を施した
プログラムを示す図である。

【図１０】本発明を適用した実行例である。

【図１１】コンパイラのパス構造を示す図である。

【図１２】コード命令のデータ依存関係を示す図であ
る。

【図１３】ＮＯＰを用いた依存関係の解消を説明するた
めの図である。

【図１４】遅延ロードを説明するための図である。

【図１５】実行プログラムの例を示す図である。

【図１６】従来の命令の実行例（インターロックする場
合）を示す図である。

【符号の説明】

Ｓ１００ 解析処理 Ｓ２００ 最適化処理 Ｓ３００ 出力

Claims (2)

【特許請求の範囲】
1. 【請求項１】 高級言語あるいはアセンブリ言語から目
   的プログラムを生成するコンパイラにおいて、 データキャッシュがミスした場合に、レジスタの資源競
   合によりパイプラインがインターロックを起こさないよ
   うに、前記目的プログラムの命令の順序を入れ換える最
   適化処理手段を有することを特徴とするコンパイラ。
2. 【請求項２】 少なくとも、レジスタ書き戻しステージ
   を有する命令パイプラインを使用するプロセッサで用い
   られ、高級言語あるいはアセンブリ言語から目的プログ
   ラムを生成するコンパイラにおいて、 前記目的プログラムの命令を解析して、前記命令列中に
   分岐及び分岐先を持たないコード列である基本ブロック
   毎に、前記目的プログラムを分割する解析処理手段と、 この解析処理手段で分けられた所定の基本ブロックにつ
   いて、ロード命令を抽出し、この抽出されたロード命令
   のデータキャッシュのミス時のレジスタ書き戻しステー
   ジにおけるクロックサイクルが、レジスタに書き込まな
   い命令のレジスタ書き戻しステージとなるように命令の
   順序の入れ換えを、前記基本ブロック内で行なう最適化
   処理手段と、 この最適化処理手段にて最適化された目的プログラムの
   出力を行う出力手段と、 を具備することを特徴とするコンパイラ。