JP3220055B2 - 機械語命令列またはアセンブリ言語命令列を最適化する最適化装置、及び、高級言語で記載されたソースプログラムを機械語またはアセンブリ言語の命令列に変換するコンパイラ装置。 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、高級言語から機械
語またはアセンブリ言語に変換された命令列を最適化す
る最適化装置及び高級言語のソースプログラムを機械語
またはアセンブリ言語の命令列に変換するコンパイラ装
置に関する。

【０００２】

【従来の技術】中間言語状態における最適化は、ソース
プログラムを読み込み、これを中間言語に変換した後に
行われる。最適化が行われると、コードサイズまたは実
行時間は相当レベルにまで改善される。ところが最適化
後に生成されたアセンブラ命令列からなるプログラム
（以下アセンブラプログラムという）、機械語命令列か
らなるプログラム（以下機械語プログラムという）であ
っても、冗長なコードが存在していたり、遅延を生じる
命令並び等が含まれている場合がある。

【０００３】コードサイズまたは実行時間の改善を徹底
したい場合には、命令スケジューリング、冗長命令の削
除や複写伝播等の最適化をコンパイラが生成したアセン
ブラまたは機械語コードに対して行なう。アセンブラレ
ベル、機械語命令レベルに適用される最適化には、命令
スケジューリングと、同値集合を用いた冗長転送命令の
削除とがある（尚以降の説明は、アセンブラレベル最適
化に統一して行う。）。

【０００４】＜命令スケジューリング＞アセンブラレベ
ル最適化の第１従来技術として、命令スケジューリング
の従来技術について説明する。近年、マイクロプロセッ
サにおいてはパイプライン機構を導入し実行の高速化を
図ることが極一般的に行なわれている。パイプライン機
構を持つアーキテクチャは、パイプラインが完全に埋ま
り、空きがない場合に最大性能を発揮する。

【０００５】どの命令列が来た時にパイプラインに空き
が生じるかはパイプラインの構成に依存する。例えばＩ
Ｆ（命令フェッチ）、ＤＥＣ（命令デコード）、ＥＸ
（実行）、ＭＥＭ（メモリ操作）、ＷＢ（レジスタ書き
込み）の５つのステージを持つ５段パイプライン・シン
グルスカラマシンを用いる場合、このパイプライン構成
を持つアーキテクチャではメモリからロードした値を、
直後の命令で参照すること（以下、ロード―参照と呼
ぶ）は不可能であり、命令がこの順にならんでいる場合
にはパイプラインに空きが生じ、遅延時間が生じる。遅
延時間の発生を回避するには、このアーキテクチャのマ
シンの命令スケジューリングにおいてはロード―参照の
命令並びを分離する必要がある。ロード―参照の並びを
分離する目的を含めて、パイプラインアーキテクチャマ
シンをターゲットとしたコンパイラでは、パイプライン
機構の性能を十分に引き出すため命令スケジューリング
と呼ばれる最適化を行っている。

【０００６】スケジューリングとは、パイプラインアー
キテクチャに適合するよう命令の配置構造を再編成する
処理をいう。命令の配置構造とは、この命令の次にこの
命令を実行するという『命令間の前後関係』からなり、
その再編成とは、プログラム内の複数の命令のうち、そ
の一部の命令間の前後関係を入れ替えることをいう。ス
ケジューリングには、ターゲットマシンのパイプライン
構成を考慮してパイプラインハザードを回避するもの、
並列化ユニットに効率良く命令を供給するためのものの
二種類がある。パイプラインの埋まり方は命令の供給順
に依存するため、命令列を並べ替えることによりパイプ
ラインの性能を最大限に引き出すのである。

【０００７】ここで注意すべきは命令の前後関係の入れ
替えは慎重を期さねばならないという点である。これは
安易な前後関係の入れ替えは、アルゴリズムの正当性を
破壊してしまうからである。正当性の破壊を避けるに
は、プログラムにおける命令の前後関係を"不可侵なも
の"と、そうでないものとに分類せねばならない。"前後
関係の不可侵"とは、『この命令とこの命令との前後関
係は入れ替えてはならない』という意味である。"前後
関係の不可侵"を明示するためには、前後関係の不可侵
が要求される命令の並びを検出し、その並びにおける命
令間において有向リンクを形成する。

【０００８】命令の前後関係において、不可侵となるも
のに従来から形成されていた有向リンクには、定義−参
照間のリンク、参照−定義間のリンク、定義−定義間の
リンクがある。 ・定義−参照間のリンク 定義−参照間のリンクとは、ある資源を定義する命令
と、参照される命令との前後関係は不可侵である旨を明
示する有向リンクである。

【０００９】（１）『mov 100,D0』 （２）『add D0,D1』 例えば（１）、（２）の命令列には、レジスタD0を介し
てのデータフローが存在している。このレジスタD0を介
してのデータフローが存在するため、命令（１）（２）
の順序を入れ替えることは、データフローを崩すことを
意味する。そのため命令スケジューリングを行うにあた
っては、有向リンクによりある資源を定義する命令と、
参照される命令との前後関係は不可侵である旨を明示し
ておく。 ・参照−定義間のリンク 参照−定義間のリンクとは、ある資源を参照する命令
と、その資源を定義する命令との前後関係が不可侵であ
る旨を明示する有向リンクである。命令の並べ替えを行
うにあたって、定義−参照間のリンクに加えて、参照−
定義間のリンクがなぜ必要であるかを以下の（１）〜
（４）の命令列を用いて説明する。

【００１０】（１）『mov 100,D0』 （２）『add D0,D1』 （３）『mov 200,D0』 （４）『add D0,D2』 この命令列において（１）−（２）の命令列には、レジ
スタD0を介してのデータフローが存在している。（３）
−（４）の命令列にも、レジスタD0を介してのデータフ
ローが存在している。レジスタD1、D2の格納値の初期値
が０であったとする。そしてこの（１）〜（４）の命令
列を並べ替えて、（１）−（３）−（２）−（４）の順
序にしたとする。この順序は、先に述べた定義−参照の
並びを維持したものであるが、この機械語プログラムの
実行によってレジスタD1に200が加算され、レジスタに2
00が加算されるので、機械語プログラムの意味が変わっ
てしまう。そのため（２）−（３）間においてレジスタ
D0に関しての依存関係を参照−定義間のリンクに保存し
ておき、（２）−（３）の前後関係が不可侵である旨を
明示しておく。 ・定義−定義間のリンク 定義−定義間のリンクとは、ある資源を定義する命令
と、その資源を再定義する命令との前後関係が不可侵で
ある旨を明示する有向リンクである。命令の並べ替えを
行うにあたって、定義−定義間のリンクがなぜ必要であ
るかを以下の（１）（２）（３）の命令列を用いて説明
する。

【００１１】（１）『mov 100,D0』 （２）『mov 200,D0』 （３）『add D0,D2』 例えば、（２）−（３）の命令列には、レジスタD0に対
してのデータフローが存在している。そのため、（２）
（３）の命令は、定義−参照のリンクで結合される。ま
た（１）の命令列は、レジスタD0についての定義であ
る。この（１）〜（３）の命令列を並べ替えて、（２）
−（１）−（３）の順序にすると、この機械語プログラ
ムの実行によってレジスタD2に100が加算されるので、
機械語プログラムの意味が変わってしまう。このような
瑕疵ある並び替えを防ぐため、依存グラフでは、（１）
−（２）間においてレジスタD0に関して、定義−定義と
いった依存関係を定義−定義間のリンクに保存してお
き、瑕疵ある並べ替えを防いでいる。

【００１２】従来の命令スケジューリングについてサン
プルプログラムを用いて説明する。従来のコンパイラの
構成図を図１６に示す。例として図１２（ａ）のプログ
ラムを処理する場合を考える。プログラムはまず解析部
８１で入力、解析され中間コードに変換される。この時
点の中間コードを図１２（ｂ）に示す。次に資源割り付
け部８２において変数がレジスタもしくはメモリに割り
付けられる。資源割り付け結果に基づいて得られたアセ
ンブラプログラムを図１２（ｃ）に示す。この例では変
数ｉがレジスタＤ０に、そして変数ｋがメモリ（ＳＰ、
０）に割り付けられたとしている。アセンブラ命令生成
部８４は、この割り付け結果を用いて、アセンブラプロ
グラムを生成する。生成されたプログラムを図１２
（ｃ）に示す。図１２（ｃ）においてメモリからのロー
ド「MOV (SP,0),D1」の直後にロードした値の参照「add
D1,D1」が配置されており、この部分で遅延が生じる
（ロード―参照）。このコードは次に命令スケジューリ
ング部８５に渡される。命令スケジューリング部８５は
依存グラフ生成部８６と命令並べ替え部８７とから構成
される。命令スケジューリング部８５に渡されたアセン
ブラ命令は、まず依存グラフ生成部８６に渡され、アセ
ンブラ命令に対応した依存グラフが生成される。依存グ
ラフは命令間の資源の依存関係を表し、命令の実行順序
を規定している。依存グラフ中で命令Ａ、Ｂ間が矢印
「Ａ→Ｂ」で結ばれている場合には命令Ｂを実行する前
に命令Ａが実行されていなければならないことを示す。
依存グラフ生成部８６が生成した依存グラフを図１２
（ｄ）に示す。

【００１３】図１２（ｄ）中では遅延の生じる位置を×
印で示している。依存グラフを生成し終ると、依存グラ
フは命令並べ替え部８７へ渡される。命令並べ替え部８
７では依存グラフに反しないよう、且つ、ターゲットマ
シンのパイプラインが可能な限り効率良く働くように命
令をヒューリスティックに並べ替える。命令並べ替え部
８７で並べ替えられたアセンブラプログラムを図１２
（ｅ）に示す。図１２（ｅ）では図１２（ｃ）と比べて
ロード―参照命令間に「add 1,D0」が挿入され、ロード
命令とロードされた値を参照する命令が分離されており
遅延が解消されていることが分かる（図１２（ｅ）中の
○印）。命令並べ替えが済んだコードは最後にコード出
力部８８に渡される。コード出力部８８は受けとったコ
ードを機械語またはアセンブラプログラムとしてファイ
ル等に出力する。

【００１４】＜冗長転送命令の削除＞アセンブラ命令レ
ベルの最適化の第２従来技術として冗長転送命令の削除
について説明する。ここでいう『冗長転送命令』とは、
その命令の直前命令において同値関係が成立しているに
も拘らず、二度手間の転送を行っている転送命令を言
う。

【００１５】同値関係とは、転送命令の転送元にて指示
されている資源と、転送命令の転送先にて指示されてい
る資源とが同じ保持値になっていることを示す。各命令
が有する同値関係は、同値集合を用いて表現される。同
値集合とは、同値関係が成立している全ての資源を表す
集合である。具体的には、レジスタ名及びメモリのアク
セス先アドレスを示すアドレス指定コードの集合を用い
て表現される。

【００１６】図１３（ａ）（ｂ）は、同値集合を用いた
最適化の過程を示す図である。図１３（ａ）のプログラ
ム例に含まれている各命令の実行直前においてどのよう
な同値集合が成立しているかを図１３（ｂ）を示す。図
１３（ｂ）の第２行目の転送命令の実行直前における同
値集合は{(SP,4),D1}である。{(SP,4),D1}は、データレ
ジスタD1の保持値が(SP,4)に等しいことを示す。図１３
（ｂ）の第５行目の転送命令における同値集合は{(SP,
4),D1}{3,D0}である。{(SP,4),D1}は、データレジスタD
1の保持値が(SP,4)と等しいことを示し、{3,D0}は、デ
ータレジスタD0の値が即値3に等しいことを示す。

【００１７】図１３（ｂ）の転送命令において更に注意
すべきは、第４行目終了時点から第５行目開始時点まで
の段階でアドレス(SP,4)とデータレジスタD1との間の同
値集合が既に成立しているにも拘らず、第５行目でアド
レス(SP,4)からデータレジスタD1への転送が行われてい
る点である。このような第５行目の転送命令を用いての
アドレス(SP,4)からデータレジスタD1への転送は冗長で
あるため、これを削除する。その結果が図１３（ｃ）で
ある。

【００１８】

【発明が解決しようとする課題】しかしながら従来のア
センブラレベル及び機械語レベルの最適化方式では間接
アドレス指定型の定義命令の存在により多くの制約を受
けてしまうという問題点がある。その第１の制約とは、
従来の命令スケジューリングでは、間接アドレス指定型
の定義命令及び参照命令を跨いだ命令の移動が禁止され
てしまい、スケジューリングの自由度が奪われてしまう
ということである。間接アドレス指定型の命令を跨いだ
命令移動が禁止される理由は以下の通りである。即ち間
接アドレス指定型の定義命令は、そのコードからはどの
アドレスのメモリに値を書き込んでいるかが不明であ
る。もし間接アドレス指定型の命令の前後にメモリアク
セスする命令があれば、間接アドレス指定型の命令はそ
れらの命令と同一アドレスをアクセスしているかもしれ
ない。同一アドレスをアクセスしている可能性が僅かで
も存在するなら、間接アドレス指定型の命令を跨いだ最
適化は一切避けるべきだからである。

【００１９】図１４（ａ）に命令スケジューリング前の
命令列を示す。図１４（ａ）の例では第２行目に「mov
D0,(A0)」に示される間接アドレス指定によりメモリを
定義するメモリアクセス命令（メモリ定義命令ともい
う）が存在する。この命令で操作されるメモリ(A0)はア
ドレスレジスタA0の値によりどのアドレスになるかが決
定される。しかし図１４（ａ）のプログラム例ではアド
レスレジスタA0にどのような値が保持されているかとい
う結論は出せない。このように間接アドレス指定型の定
義命令がどのアドレスに値を書き込んでいるかが不明な
場合は、間接アドレス指定型の定義命令以降の命令のう
ち、メモリアクセスを含むものとの前後関係が不可侵で
あると解釈せねばならない。

【００２０】図１４（ａ）のプログラム例には、第３行
目、第４行目、第６行目、第７行目にスタック領域をア
クセスする命令が存在するが、第２行目の間接アドレス
指定型の定義命令はこれらと同アドレスに値を書き込ん
でいる可能性があるので、第２行目の間接アドレス指定
型の定義命令は、第３行目、第４行目、第６行目、第７
行目の命令との前後関係を不可侵と解釈するのである。

【００２１】図１４（ｂ）に、依存グラフの一例を示
す。本依存グラフでは、前後関係が不可侵となる命令間
に有向リンクが形成されている。この有向リンクでは、
第２行目−第３行目間、第２−第４行目間、第２行目−
第６行目間、第２行目−第７行目間に有向リンクが形成
されている。このように一つの間接アドレス指定型の定
義命令と、４つもの命令との間に有向リンクが形成され
ると、命令の配置構造の入れ替えのための自由度が大き
く奪われてしまう。図１４（ａ）の命令例では、第４行
目−第５行目にハザードが存在しているが、図１４
（ｂ）において形成されている有向リンクにより、命令
の配置構造が拘束されているので、ハザードを解消し得
ない。

【００２２】第２の問題点として、同値集合を用いた冗
長転送命令の削除では、間接アドレス指定型の定義命令
の前後において同値集合の廃棄が行われるので、冗長転
送命令が削除できない現象が表れてしまう。図１５
（ａ）のプログラム例を最適化するにあたって同値集合
の解析を行った結果が図１５（ｂ）である。図１５
（ｂ）では、第５行目において同値集合の廃棄が行われ
ている。第５行目において同値集合の廃棄が行われたの
は、その直前の第４行目が間接アドレス指定型の定義命
令だからである。第４行目の間接アドレス指定型の定義
命令「mov D1,(A0)」におけるメモリ(A0)はレジスタA0の
値によりどのアドレスになるかが決定される。しかし図
１５（ａ）のプログラム例ではアドレスレジスタA0にど
のような値が保持されているかという結論は出せない。
このように間接アドレス指定型の定義命令がどのアドレ
スに値を書き込んでいるかが不明な場合は、間接アドレ
ス指定型の定義命令以前に存在していた同値集合のう
ち、メモリアドレスを指示するものは廃棄せねばならな
い。

【００２３】第５行目は、アドレス(SP,4)からデータレ
ジスタD1へと値を転送する転送命令であるが、アドレス
(SP,4)−データレジスタD1間の同値集合を示す同値集合
が第４行目の間接アドレス指定型の定義命令の存在のた
めに廃棄されたので第５行目の冗長転送命令が削除でき
ずに終わってしまう。本発明は上記問題点に鑑み、メモ
リの間接アクセスが存在することによるアセンブラレベ
ル最適化の効率低下を軽減できる最適化装置及びコンパ
イラを提供することを目的とする。

【００２４】

【課題を解決するための手段】上記課題の底流にあるも
のは何であるかを考察し、これを解決するためにどのよ
うな点に着眼したかを講ずる。 ｛上記課題の底流にある現象｝上記課題の底流にある現
象は、コンパイラによる間接アドレス指定型のメモリア
クセス命令の生成である。コンパイラが間接アドレス指
定型のメモリアクセス命令を生成する理由は、ソースプ
ログラムに含まれている別名アクセスの記述を忠実に翻
訳しようとするからである。

【００２５】ここで別名アクセスとは、ソースプログラ
ムにおいてある変数名で宣言された数値の格納先が、形
態が異なる別変数を用いて指示されることをいう。例え
ば以下の文１〜３からなるプログラムにおいて変数名
『a』で宣言された数値の格納先が、ポインタ変数『*
p』を用いて指示される場合、変数名『a』を含む一文
は、別名アクセスの可能性を有することになる。 文１ a＝10 文２ p＝&a 文３ *p＝20 本ソースプログラムにおいて文１では、変数名『a』で
宣言された格納箇所に数値『10』を格納する旨が記述さ
れている。続く文２では、数値『10』の格納箇所のアド
レス『&a』をポインタ変数『p』に複写する旨が記述さ
れている。この複写により別変数名を用いた上記格納箇
所のアクセスが可能となる。文３は、別変数名を用いた
上記格納箇所の定義である。即ちポインタ変数『*p』を
用いて、文『10』の格納箇所に数値『20』を書き込む旨
が規定されている。

【００２６】ソースプログラムにこのような記述がある
場合、変数名aで宣言された数値の格納先は別の変数名*
pを用いてもアクセスされることになる。当該別名アク
セスの可能性を有するソースプログラムからアセンブラ
プログラムが生成されると、ソースプログラムにおいて
変数が有していた別名アクセスの可能性はアセンブラプ
ログラムへと継承されてしまう。

【００２７】『別名アクセスの可能性の継承』とは、１
つのメモリが、絶対アドレス指定、アドレスレジスタを
用いた間接アドレス指定、スタックポインタSPを用いた
間接アドレス指定など様々な形態のコードを用いて表現
されることをいう。同じアクセス先を別名アクセスして
いるメモリアクセス命令を確実に検出するのは基本ブロ
ック間のデータフローを追跡する必要があり非常に困難
である。ある関数が別関数の呼び出しを含む場合には、
別名アクセスを行っているメモリアクセス命令の解析は
もはや現実的ではない。

【００２８】｛課題を解決するためにどのような点に着
眼したか｝課題を解決するために本願が着眼したのは、
以下の、の二種類の性質を有するメモリアクセス命
令である。 そのアクセス先に対応する変数がユーザがコーディ
ングしたプログラム内に存在しないメモリアクセス命
令。

【００２９】 そのアクセス先に対応するメモリアド
レスが他の関数により操作されず、且つその関数中でユ
ーザにより別名で操作されることがないメモリアクセス
命令。 に分類されるメモリアクセス命令には、アクセス先が
一時変数に対応するメモリアクセス命令、スピルアウト
命令、スピルイン命令がある。に分類されるメモリア
クセス命令には、アクセス先がアドレス参照を受けない
局所変数に対応するメモリアクセス命令がある。

【００３０】一時変数、アドレス参照を受けない局所変
数、スピルアウト命令、スピルイン命令について以下に
説明する。 ※局所変数 局所変数とは、関数内の一部若しくは全域をその有効範
囲とする変数である。それ故に、別の関数から操作され
ることはない。また局所変数が関数中でアドレス参照を
受けなければ、保持値の格納先が別変数にて操作される
こと（間接アクセスされること）もない。

【００３１】局所変数はコンパイラがスタック領域上の
メモリに割り付ける。当該メモリは、アドレス(SP,2)、
アドレス(SP,4)という間接アドレス指定のコードを用い
て表現される。アドレス(SP,2)、アドレス(SP,4)等のス
タック領域上のメモリは、スタックポインタ及びディス
プレースメントが異なれば、互いに別々の領域であるこ
とが保障される。ディスプレースメントの大きさは、局
所変数保持値の大きさに基づいて決定される。例えば、
局所変数の大きさが２バイトであるなら、ディスプレー
スメントは、２バイトの整数倍に決定される。これは、
スタック領域内で局所変数の保持値が重複したメモリ位
置に格納されてしまうことを防止するためである。 ※一時変数 一時変数とはコンパイラが演算の途中結果を保持するた
めに内部で一時的に生成する変数のことである。そのメ
モリ位置もコンパイラが決定するため、ユーザープログ
ラムには、当該メモリを操作するコードが存在しないと
いう性質を有する。 ※スピルアウト命令及スピルイン命令 スピルアウト命令とは、スピルとは資源割り付け時にレ
ジスタが不足した際に、レジスタに入っている有効な値
をメモリに退避するアセンブラ命令をいい、スピルイン
命令は、その値が必要になった時点でレジスタに値を復
帰するアセンブラ命令をいう。一般スピルにより退避す
るメモリ位置はコンパイラが決定するため、ユーザープ
ログラムには、当該メモリを操作するコードが存在しな
いという性質を有する。

【００３２】一時変数から生成されたメモリアクセス命
令(1)、アドレスが明示的に参照されない局所変数から
生成されたメモリアクセス命令(2)、スピルアウト命令
(3)、スピルイン命令(4)に対しては、別名アクセスの可
能性が無いことは明らかであるから、アセンブラ命令に
含まれているメモリアクセス命令のうち、以上の(1)〜
(4)に対応するメモリをアクセス先にしているメモリア
クセス命令を解析し、それらのメモリアクセス命令に対
して、その旨を示すマークをメモリアクセス命令に付与
する。

【００３３】命令列最適化を、このように各メモリアク
セス命令に付与されたマークを参照しながら行う。この
ようにして最適化を行うと、間接アドレス指定型のメモ
リアクセス命令の存在に起因する制約が緩和され、実行
時間及びプログラムサイズの向上を図ることができる。

【００３４】※補足 尚、スタックポインタレジスタを用いた間接アドレス指
定型の定義命令（例えば、mov D1,(SP,4)）について
は、本明細書において間接アドレス指定型の定義命令に
含まれないものとする。これは、一般にコンパイラが生
成するコードでは、スタックポインタは関数毎に固定さ
れた値が用いられるため、本明細書においてスタックポ
インタレジスタの値は固定されているものとしているか
らである。

【００３５】

【発明の実施の形態】以下最適化装置を内蔵したコンパ
イラの実施形態を図面を参照しながら説明する。図１
は、コンパイラの内部構成を示したブロック図である。
コンパイラは図１に示すように、解析部１０と、資源割
り付け部１１と、アセンブラコード生成部１８と、アセ
ンブラ最適化部２０と、コード出力部１３とからなる。
また、メモリ上に割り付け資源情報１４を保持する。ア
センブラ最適化部２０はアセンブラレベルの最適化を行
う最適化装置であり、命令スケジューリング部１２及び
別名アクセス性解析部１９を備える。

【００３６】解析部１０は、ファイル形式で保存される
高級言語ソースプログラムを読み込み、構文解析及び意
味解析を行なって内部表現（以下中間言語と称する）に
変換する。更にこの中間言語を最終生成コードサイズや
実行時間が小さくなるように最適化する場合もある（こ
れは中間コード最適化部と呼ばれる別ブロックとする事
が多い）。中間言語を生成する解析部１０の処理は本発
明の主眼ではないので、その処理内容は省略する。高級
言語にて記述されたソースプログラムを図２（ａ）に示
し、解析部により中間言語状態に変換された中間言語プ
ログラム図２（ｂ）を示す。簡単のために図２（ｂ）以
降では図２（ａ）中の範囲ａ内に含まれているコードの
みを示す。ここでプログラムには局所変数として変数k
が含まれている。

【００３７】資源割り付け部１１は中間言語状態のプロ
グラム内の変数にどのマシン資源を割り付けるかを決定
する。この際、ソースプログラム文における各変数の宣
言文等を参照しながら、中間言語状態のプログラム内の
変数が、一時変数であるか、局所変数であるか、ポイン
タ変数であるかを勘案し、レジスタ、メモリのうち適切
なものを割り付ける。一時変数及び局所変数について
は、データレジスタ又はスタック領域上のメモリを割り
付け、ポインタ変数については、アドレスレジスタを割
り付ける。これらの変数については、各変数の生存区
間、使用頻度に基づいて優先度を決定し、優先度の高い
ものにレジスタを割り付け、低いものにメモリを割り付
ける。資源割り付け部１１による資源割り付け結果を図
２（ｃ）に示す。図２（ｂ）における変数のうち、この
例では変数ｉがレジスタＤ０に割り付けられ、変数ｊが
レジスタＤ１に割り付けられ、変数ｋがメモリ（ＳＰ、
０）に割り付けられている。

【００３８】アセンブラコード生成部１８は、資源割り
付け部１１による割り付け結果を参照して、中間言語状
態のプログラムからアセンブラ命令を生成する。また演
算命令を生成した際、レジスタに格納されていた数値を
一旦退避する必要が生じた場合は、アセンブラコード生
成部１８はスピルアウト命令及びスピルイン命令を生成
する。

【００３９】図２（ｂ）に示した中間言語文からアセン
ブラコード生成部１８がアセンブラ命令を生成した結果
を図２（ｄ）に示す。図２（ｄ）において留意すべき
は、ｋ＝ｋ＋１の演算を行なう際にレジスタが不足した
ので、レジスタＤ１の値をメモリ(SP,4)に退避するスピ
ルアウトコード「mov D1,(SP,4)」が生成され、演算が
終了した後でメモリ(SP,4)から復帰するスピルインコー
ド「mov (SP,4),D1」が生成されている点である。

【００４０】別名アクセス性解析部１９はアセンブラコ
ード生成部１８により生成されたアセンブラ命令列内に
別名アクセスの可能性が潜在しているか否かを解析す
る。別名アクセスの可能性をどのような基準で判断する
かであるが本装置ではそのメモリアクセス命令のアクセ
ス先がユーザプログラムにより操作され得ないかを判断
材料にしている。アクセス先がユーザプログラムにより
操作され得ないメモリアクセス命令には、そのアクセス
先が一時変数に対応するもの、スピルイン・スピルアウ
ト命令、格納先アドレスが明示的に参照されてない局所
変数に対応するものがある。

【００４１】別名アクセスの可能性が発生するのは、ユ
ーザプログラムにより操作される場合なので、これらの
コード（アクセス先が一時変数に対応するメモリアクセ
ス命令、格納先アドレスが明示的に参照されてない局所
変数に対応するメモリアクセス命令、スピルイン・スピ
ルアウト命令）については、別名アクセスの可能性が潜
在していないと結論づけて良い。

【００４２】別名アクセス性解析部１９はスピルアウト
命令、スピルイン命令が生成された際、これらスピルア
ウト命令、スピルイン命令が位置する行を示す行番号
と、これら命令のアクセス先を示すアドレス指定コード
とを割り付け資源情報１４に格納する。このように行番
号及びアドレス指定コードが登録された命令には別名ア
クセスの可能性が潜在していない旨に解釈される。

【００４３】どのような手掛かりをもって変数と、アク
セス先との対応関係を把握するかであるが、別名アクセ
ス性解析部１９は判断の手掛かりに資源割り付け部１１
が資源割り付け時に行った変数種別の分類結果を用いて
いる。アクセス先が一時変数に対応するメモリアクセス
命令、或は、アクセス先がアドレス参照を受けない局所
変数に対応するメモリアクセス命令を判定すると、これ
らのメモリアクセス命令の行番号と、これらのアクセス
先を示すアドレス指定コードとを割り付け資源情報１４
に格納する。このように登録されたアドレス及びアドレ
ス指定コードは、この位置の命令には別名アクセスの可
能性が潜在していない旨に解釈される。

【００４４】図２（ｄ）のアセンブラ命令が生成された
際の別名アクセス性解析部１９の処理について図３
（ａ）を参照しながら説明する。第１行目の演算命令
『add 1,D0』はアクセス先がレジスタであるから、別名
アクセス性解析部１９は別名アクセスの可能性が存在し
ないと解釈する。第２行目のメモリアクセス命令『mov
D0,(A0)』はアクセス先がメモリであり、そのアドレス
が間接アドレス指定により指定されていることから、別
名アクセスの可能性が存在すると解釈する。

【００４５】第３行目のメモリアクセス命令『mov D1,
(SP,4)』はメモリアドレス(SP,4)を定義するメモリアク
セス命令であり、スピルアウト命令である。そのため別
名アクセス性解析部１９はそのメモリアクセス命令は別
名アクセスの可能性が潜在しないと解釈し、メモリアク
セス命令『mov D1,(SP,4)』の行番号を割り付け資源情
報１４に登録することにより、メモリアクセス命令『mo
v D1,(SP,4)』に別名アクセスの可能性が存在しない旨
を割り付け資源情報１４に反映する。

【００４６】第４行目のメモリアクセス命令『mov (SP,
0),D1』はメモリアドレス(SP,0)からデータレジスタD1
へと保持値を転送するメモリアクセス命令である。この
際、別名アクセス性解析部１９はアドレス(SP,0)がどの
変数に対応するかであるかを解析する。図２（ｃ）の資
源割付結果によれば、アドレス(SP,0)は、一時変数ｋに
対応することがわかる。

【００４７】参照先が一時変数に対応するメモリである
ため、別名アクセス性解析部１９はメモリアクセス命令
『mov (SP,0),D1』が別名アクセスの可能性が存在しな
いと解釈し、メモリアクセス命令『mov (SP,0),D1』の
行番号を割り付け資源情報１４に登録することにより、
メモリアクセス命令『mov (SP,0),D1』に別名アクセス
の可能性が存在しない旨を割り付け資源情報１４に反映
する。

【００４８】第５行目の演算命令『add D1,D1』はレジ
スタを用いて演算を行う演算命令であるので、別名アク
セスの可能性解析の対象とはならない。第６行目のメモ
リアクセス命令『mov D1,(SP,0)』はデータレジスタD1
からメモリアドレス(SP,0)へと保持値を転送するメモリ
アクセス命令である。図２（ｃ）の資源割付結果によれ
ば、アドレス(SP,0)は、一時変数ｋに対応することか
ら、別名アクセス性解析部１９はメモリアクセス命令
『mov D1,(SP,0)』が別名アクセスの可能性が存在しな
いと解釈し、メモリアクセス命令『mov D1,(SP,0)』の
行番号を割り付け資源情報１４に登録することにより、
メモリアクセス命令『mov D1,(SP,0)』に別名アクセス
の可能性が存在しない旨を割り付け資源情報１４に反映
する。

【００４９】第７行目のメモリアクセス命令『mov (SP,
4),D1』はメモリアドレス(SP,4)を参照するメモリアク
セス命令であり、スピルイン命令である。そのため別名
アクセス性解析部１９はそのメモリアクセス命令は別名
アクセスの可能性が存在しないと解釈し、メモリアクセ
ス命令『mov (SP,4),D1』の行番号を割り付け資源情報
１４に登録することにより、メモリアクセス命令『mov
(SP,4),D1』に別名アクセスの可能性が存在しない旨を
割り付け資源情報１４に反映する。各行についての別名
アクセス可能性が解析された結果を図３（ｂ）に示す。

【００５０】命令スケジューリング部１２の内部構成に
ついて説明する。命令スケジューリング部１２は依存グ
ラフ生成部１５と命令並べ替え部１６とから構成され
る。依存グラフ生成部１５は、アセンブラコード生成部
１８によるアセンブラ命令の生成後に起動され、アセン
ブラコード生成部１８が生成したアセンブラ命令間に有
向リンクを形成することによりアセンブラ命令を依存グ
ラフ化する。

【００５１】なお、実際には基本ブロック外の命令との
依存関係を示す有向リンクを形成する必要があるがここ
では簡単のため省略する。基本ブロック外の命令との依
存関係は例えば仮想基本ブロック開始命令、仮想基本ブ
ロック終了命令を想定することで容易に解析できる。依
存グラフ生成部１５の処理内容を示すフロ−チャ−トを
図５に示す。

【００５２】まずステップａ１では、依存グラフ生成部
１５はアセンブラコード生成部１８が生成した割り付け
資源情報を取り込む。次にステップａ２はステップａ１
４と対になり、基本ブロック内の全ての命令について、
ステップａ３〜ステップａ１４を繰り返す。ステップａ
２では、基本ブロック内の命令を取り出して、これを対
象命令とする。

【００５３】ステップａ３で、当該対象命令の参照先資
源が単一資源であるかを判定する。単一資源である場合
にはステップａ４に移行する。ここで単一資源とは、対
象命令におけるアクセス先が明確に何れかの資源に対応
しており、別名アクセスされることがないものをいう。
対象命令が別名アクセスされることなくスタックポイン
タレジスタと、その保持値からの相対アドレスとにより
アクセス先が指定されており、スタックポインタレジス
タの不変動が保障されている場合、アクセス先のメモリ
が明確であるため、その対象命令のアクセス先は単一資
源となる。

【００５４】ステップａ４では対象命令以前に位置する
命令であって、当該参照先資源を定義先としている命令
を検出する。このようにして検出された命令に対して有
向リンクを形成する。形成された有向リンクは、対象命
令が参照側に位置する定義―参照リンクとなる。なお、
参照先資源を定義している命令が基本ブロック内に存在
しない場合（基本ブロック外で定義されている場合）に
は基本ブロック先頭仮想命令にリンクを形成する。これ
は以下でも同様である。

【００５５】ステップａ５では当該命令の定義先が単一
資源であるかどうかを判定する。そうである場合にはス
テップａ６に制御を移すステップａ６では当該対象命令
以前のもっとも近い位置で当該単一資源を操作している
命令を検出し、検出された命令の定義先が当該単一資源
と同一であるかを判定する。同一である場合にはステッ
プａ７へ、そうでない場合にはステップａ８に移行す
る。

【００５６】ステップａ７では当該同一資源を定義して
いる命令に対しリンクを形成する。このようにして形成
された有向リンクは、対象命令が\u後者の定義側\uとな
る定義―定義リンクである。ステップａ８では、対象命
令以前であって、\u且つ最も近い位置で当該資源を定義
している命令までに\u位置する命令であって、対象命令
の定義先資源を参照している全ての命令を検出し、それ
らの命令への有向リンクを形成する。このようにして形
成された有向リンクは、対象命令が定義側となる参照―
定義リンクである。

【００５７】ステップａ３〜ステップａ８の処理によ
り、対象命令が参照側となる定義−参照リンク、対象命
令が定義側となる定義−定義リンク及び参照−定義リン
クが形成された。ステップａ３〜ステップａ８の処理に
より形成されるのは、対象命令が含んでいる単一資源を
基点とした有向リンクである。その他の資源（間接アド
レスにより指定されたメモリや別名参照の可能性のある
メモリ）を基点にした有向リンクについては、ステップ
ａ９〜ステップａ１３において生成する。

【００５８】ステップａ９では当該対象命令によるメモ
リ参照が別名操作を受け得るメモリ参照であるかを判定
する。そうである場合はステップａ１０に移行する。ス
テップａ１０では、対象命令以前に位置するメモリアク
セス命令であって、その行番号が割り付け資源情報に記
述されているメモリアクセス命令を除く全てのメモリ定
義命令を検出し、検出したメモリ定義命令から対象命令
へと向かう定義−参照リンクを形成する。割り付け資源
情報１４はステップａ１で取り込まれたものであり、別
名アクセスの可能性が潜在していないことが別名アクセ
ス性解析部１９により保障されている。

【００５９】本ステップにより、別名アクセスの可能性
があるメモリアクセス命令と定義―参照依存関係を持つ
可能性があるメモリ定義命令のうち、一時変数、アドレ
ス参照を受けない局所変数、スピルアウト命令、スピル
イン命令に係る命令を除いたものに有向リンクが形成さ
れる。ステップａ１１では当該対象命令が別名アクセス
の可能性があるメモリを参照するかを判定する。そうで
ある場合はステップａ１２に移行する。

【００６０】ステップａ１２では、対象命令以前に位置
するメモリアクセス命令であって、行番号が割り付け資
源情報に登録されているメモリアクセス命令を除く全て
のメモリ定義命令を検出し、検出したメモリ定義命令か
ら対象命令へと向かう定義−定義リンクを形成する。ス
テップａ１３では、対象命令以前に位置するメモリアク
セス命令であって、行番号が割り付け資源情報に登録さ
れているメモリアクセス命令を除く全てのメモリ参照命
令を検出し、検出したメモリ参照命令から対象命令へと
向かう参照−定義リンクを形成する。

【００６１】以上のステップａ１〜ステップａ１３の処
理によて形成された有向リンクからなる依存グラフは、
メモリアクセス命令前後の有向リンクの数が至って少な
い。図５のフロ−チャ−トにより有向リンクが形成され
る過程を具体的に説明する。図２（ｄ）のアセンブラ命
令に対して図５のフロ−チャ−トの処理が行われた場合
に形成された有向リンクを図４（ａ）に示す。

【００６２】第１行目の演算命令『add 1,D0』が対象命
令になった場合、基本ブロック先頭を示す基本ブロック
先頭仮想命令を作成し、当該命令から演算命令『add 1,
D0』へと向かう有向リンクが形成される。第２行目のメ
モリアクセス命令『mov D0,(A0)』が対象命令になった
場合、当該参照先資源データレジスタD0を定義先として
いる命令として演算命令『add 1,D0』が検出される。そ
して、検出された演算命令『add 1,D0』から対象命令で
あるメモリアクセス命令『mov D0,(A0)』へと向かう定
義-参照リンクg1が形成される。またメモリ(a0)に関し
て先頭仮想命令より有向リンクが形成される。

【００６３】第３行目のメモリアクセス命令『mov D1,
(SP,4)』が対象命令になった場合、対象命令以前には、
当該参照先資源データレジスタD1を定義先としている命
令が存在しないので、仮想先頭命令から当該命令に向か
う有向リンクが形成される。第４行目のメモリアクセス
命令『mov (SP,0),D1』が対象命令になった場合、対象
命令以前には、当該参照先資源アドレス(SP,0)を定義先
としている命令が存在しないので仮想先頭命令から当該
命令に向かう有向リンクが形成される。

【００６４】第５行目の演算命令『add D1,D1』が対象
命令になった場合、当該参照先資源を定義先としている
命令としてメモリアクセス命令『mov (SP,0),D1』が検
出される。検出されたメモリアクセス命令『mov (SP,
0),D1』から対象命令である演算命令『add D1,D1』へと
向かう定義-参照リンクg2が形成される。第６行目のメ
モリアクセス命令『mov D1,(SP,0)』が対象命令になっ
た場合、当該参照先資源を定義先としている命令として
演算命令『add D1,D1』が検出される。検出された演算
命令『add D1,D1』から対象命令であるメモリアクセス
命令『mov D1,(SP,0)』へと向かう定義-参照リンクg3が
形成される。

【００６５】第７行目のメモリアクセス命令『mov (SP,
4),D1』が対象命令になった場合、当該参照先資源を定
義先としている命令として第３行目のメモリアクセス命
令『mov D1,(SP,4)』が検出される。検出された第３行
目のメモリアクセス命令『movD1,(SP,4)』から対象命令
であるメモリアクセス命令『mov (SP,4),D1』へと向か
う定義-参照リンクg4が形成される。また定義資源レジ
スタD1に関して参照-定義リンクがメモリアクセス命令
『mov D1,(SP,0)』から形成される。

【００６６】命令スケジューリング部１２は依存グラフ
生成部１５より依存グラフ１７を受けとり、これを実行
時間が短くなるように並べ替える。ここではターゲット
マシンのアーキテクチャとしてＩＦ、ＤＥＣ、ＥＸ、Ｍ
ＥＭ、ＷＢの５段パイプラインアーキテクチャを仮定し
ているが、５段パイプラインアーキテクチャにおける実
行時間の短縮化は、命令の並びにより、ロード命令と、
ロードされた値を参照して演算を行う演算命令との間隔
を分離することにより実現される。

【００６７】命令スケジューリング部１２に与えられる
依存グラフは、間接アドレス指定型のメモリアクセス命
令前後の有向リンクの数が至って少ないので、並べ替え
の自由度は非常に高い。そのため、ロード命令と、演算
命令との間は高い確率で分離される。図２（ｄ）に示し
たアセンブラプログラムは、第４行目及び第５行目にお
いて、アドレス(SP,0)の保持値をデータレジスタD1にロ
ードするメモリアクセス命令『mov (SP,0),D1』と、ロ
ードされた値を参照して演算を行う演算命令『add D1,D
1』とが密接していたが、命令スケジューリング部１２
は、第４行目、第４行目の間隔を分離するためにスケジ
ューリングを行い、図４（ｂ）の並びに並び替える。図
４（ｂ）の命令列では、メモリアクセス命令『mov (SP,
0),D1』−演算命令『add D1,D1』間に、演算命令『add
1,D0』及びメモリアクセス命令『mov D0,(A0)』が挿入
され、ロード命令と、ロードされた値を参照して演算を
行う演算命令とが分離されている。５段パイプラインア
ーキテクチャが苦手とする２命令の並びが解消されたの
で、５段パイプラインアーキテクチャを円滑に駆動する
ことができる。

【００６８】コード出力部１３は、命令並べ替えが済ん
だ命令列を命令スケジューリング部１２から受け取り、
機械語プログラムまたはアセンブラプログラムとしてフ
ァイル等に出力する。以上のように本実施形態では、間
接アドレス指定型のメモリアクセス命令の前後に位置す
るメモリアクセス命令であっても、そのアクセス先がア
ドレス参照を受けない局所変数、一時変数、スピル先に
対応するものについては、別名アクセスの可能性が無い
旨を命令スケジュール部１２に通知する。このように通
知されれば、命令スケジューリング部１２は、たとえ間
接アドレス指定型のメモリアクセス命令の前後にメモリ
アクセス命令が位置していても、それらの前後関係を積
極的に変更するように命令順序の並べ替えを行う。この
並べ替えは、間接アドレス指定型のメモリアクセス命令
前後の命令の位置関係が拘束されないので自由度が非常
に高い。そうすると、パイプライン遅延の解消がより確
実になる。

【００６９】尚、上記の実施の形態では、コンパイラ内
部において別名アクセス性解析部１９から命令スケジュ
ーリング部へと割り付け資源情報が渡されるとしたが、
命令スケジューリング部をコンパイラ本体から分離し、
コンパイラから出力されるアセンブラ命令もしくは機械
語命令に割り付け資源情報を添付し、アセンブラ命令も
しくは機械語命令をスケジューリングする最適化部でこ
れを解析して命令スケジューリング時の効率を上げるよ
うな構成にしてもよい。

【００７０】（第２実施形態）第２実施形態は、冗長転
送命令の削除を行なう構成である。図６は、第２実施形
態におけるコンパイラの内部構成を示したブロック図で
ある。本図のコンパイラの構成は、アセンブラ最適化部
２０の内部に備えられていた命令スケジューリング部１
２が同値資源間転送命令最適化部２２に置き換えらてい
る点が第１実施形態と異なる。

【００７１】同値資源間転送命令最適化部２２は同値資
源解析部２５と同値資源間転送命令削除部２６からな
る。同値資源解析部２５は上記資源割り付け部２１が出
力したアセンブラ命令列のうち、基本ブロックに含まれ
ている命令に対して同値集合を生成する。同値集合の生
成処理のフロ−チャ−トを図１１に示す。

【００７２】まずステップｃ１で基本ブロック内の各命
令単位の同値関係情報、及び現在の同値関係を全てクリ
アする。ステップｃ２は、基本ブロック内の命令を順に
対象命令として選択する。ここで対象命令とは、ステッ
プｃ３〜ステップｃ７のループ処理の対象となる命令で
ある。

【００７３】ステップｃ３は当該命令が資源の値を変化
させる命令であるかどうかを判定する。変化させる命令
である場合にはステップｃ１０に移行する。ステップｃ
１０では、変化する資源が間接アドレス指定にて指定さ
れたメモリであるかを判定する。メモリでなければステ
ップｃ１１に移行して、変化する資源の同値関係をクリ
アする。

【００７４】メモリであればステップｃ１２において一
時変数、アドレス参照を受けない局所変数、スピル先を
示す間接アドレス指定コードを除く、全てのメモリアク
セス命令のアクセス先を示すアドレス指定コードを削除
する。ステップｃ１０〜ステップｃ１２によるレジスタ
同値関係クリア処理について補足説明する。例えば、演
算命令「add 1,D0」の直前において、同値関係｛Ｄ０,
Ｄ１｝が成立しているものとする（レジスタＤ０の保持
値とＤ１の保持値とが同じ値という意味である。）。こ
のように演算命令の直前において同値関係が成立してい
ても、当該演算命令はデータレジスタD0の値の演算によ
り変化させているため、演算命令が実行された後では、
データレジスタD0の値は既に変化している。そのため、
同値関係｛Ｄ０,Ｄ１｝は、演算命令「add1,D0」の後段
で崩壊したとみなしてデータレジスタD0の同値集合をク
リアする。

【００７５】演算命令「add 1,D0」の直前において、今
度は同値関係｛Ｄ０,Ｄ１,Ｄ２｝が成立しているものと
する。このように演算命令の直前において同値関係が成
立していても、当該演算命令はデータレジスタD0の値の
演算により変化させているため、演算命令が実行された
後では、データレジスタD0の値は既に変化している。そ
のため、同値関係｛Ｄ０,Ｄ１,Ｄ２｝のうち、データレ
ジスタD1は、データレジスタD0、データレジスタD2の異
なる保持値を有しているので、演算命令「add1,D0」の
後段で崩壊したとみなしてデータレジスタD1を指定する
コードのみを削除する。

【００７６】続いてメモリアクセス命令がクリアされる
場合を考える。メモリアクセス命令のクリアは、レジス
タと同様の基準をもって行えば良いのであるが、メモリ
については、間接アドレス指定型の定義命令にて指定さ
れる場合がある。間接アドレス指定型の定義命令による
メモリ指定に備えているのがステップｃ１０及びステッ
プｃ１１である。

【００７７】ステップｃ１０及びステップｃ１１は、対
象命令の定義先が間接アドレス指定にて指定されている
場合に同値関係をどのようにクリアするかを規定してい
る。定義先を間接アドレス指定にて指定している命令
は、資源を変化させていることは明きらかでありステッ
プｃ３がYesとなるが、定義先が間接アドレス指定型の
定義命令にて表現されているため、そのコードからでは
どのアドレスの値が変化しているかが結論づけられな
い。そうすると、当該間接アドレス指定は、既に同値関
係が成立しているメモリアドレスと同一の資源を指示し
ているのではないかという疑惑が生じる。しかし、間接
アドレス指定型のメモリアクセス命令以前に成立してい
る同値関係内のメモリアドレスであっても、一時変数、
アドレス参照を受けない局所変数に対応するもの、スピ
ルイン・スピルアウト命令であるものは、間接アドレス
指定型のメモリアクセス命令のアクセス先に指定される
ことはない。従って、ステップｃ１２では、一時変数、
アドレス参照を受けない局所変数に対応するメモリアド
レス、スピルイン・スピルアウト命令のアクセス先につ
いては同値関係クリアの例外として取り扱い、真に間接
アドレス指定型の定義命令にてアクセスされる可能性が
あるものをクリアしている。

【００７８】これによって間接アドレス指定型のメモリ
アクセス命令の前後で行われていた『メモリ操作コード
の全消去』を回避することができる。ステップｃ５で
は、当該命令が等価転送命令であるかどうかを判定し、
等価転送命令であった場合にはステップｃ６に移行す
る。等価転送命令とは転送命令であって、転送先、転送
元とも符号、データサイズが変わらないものである。

【００７９】ステップｃ６では、等価転送命令に対応し
た同値関係を生成し、同値関係を同値集合として表現す
る。ステップｃ７では現在の同値関係を、当該命令の同
値関係として設定する。例えば命令が「mov D0,D1」で
あった場合には同値関係｛Ｄ０、Ｄ１｝を生成する。

【００８０】同値資源間転送命令削除部２６は同値資源
解析部２５より同値関係を受けとり、冗長な転送命令を
削除する。同値関係はアドレス指定コードの集合により
その命令実行直後にどの資源とどの資源が同値であるか
を示している。つまりある命令が資源Ｂの資源Ａへの転
送命令であり、且つ、その命令の直前の同値関係におい
て資源Ａと資源Ｂが同値であればこの転送命令は冗長で
あり実行する必要がない。同値資源間転送命令削除部で
はこのような転送命令を削除する。

【００８１】次に同値資源間転送命令最適化部２２によ
り同値関係が生成され、生成された同値関係を用いて冗
長転送命令が削除される過程を説明する。高級言語ソー
スプログラムを図７（ａ）に示し、資源割り付け部１１
による資源割り付け結果を図７（ｂ）に示す。図７
（ｂ）における変数のうち、この例では変数ｉがレジス
タＤ０に割り付けられ、変数ｊがメモリ（ＳＰ、４）に
割り付けられている。\u変数pはデータレジスタA0に割
り付けられている。\uこの割り付け結果を用いてアセン
ブラコード生成部１８が生成したアセンブラプログラム
を図７（ｃ）に示す。

【００８２】図７（ｃ）のアセンブラ命令が生成される
と、アセンブラコード生成部１８は各アセンブラ命令の
別名アクセスの可能性の有無について解析する。図８
（ａ）は、各アセンブラ命令に対しての別名アクセスの
可能性が解析されている様子を示す。第１行目のメモリ
アクセス命令『mov (SP,4) ,D1』はメモリアドレス(SP,
4)からデータレジスタD1へと保持値を転送するメモリア
クセス命令である。この際、アセンブラコード生成部１
８はアドレス(SP,4)がどの変数に対応するかであるかを
解析する。図２（ｃ）の資源割付結果によれば、アドレ
ス(SP,4)は、アドレス参照を受けない局所変数ｊに対応
することがわかる。

【００８３】参照先がアドレス参照を受けない局所変数
に対応するメモリであるため、アセンブラコード生成部
１８はメモリアクセス命令『mov (SP,4) ,D1』が別名ア
クセスの可能性が存在しないと解釈し、メモリアクセス
命令『mov (SP,4) ,D1』の行番号を割り付け資源情報１
４に登録することにより、メモリアクセス命令『mov(S
P,4) ,D1』に別名アクセスの可能性が存在しない旨を割
り付け資源情報１４に反映する。

【００８４】第２行目の演算命令『sub 1,D1』はレジス
タを用いて減算を行う演算命令であるので、別名アクセ
スの可能性解析の対象とはならない。第３行目のメモリ
アクセス命令『mov D1,(SP,4)』はデータレジスタD1か
らメモリアドレス(SP,4)へと保持値を転送するメモリア
クセス命令である。図７（ｂ）の資源割付結果によれ
ば、アドレス(SP,4)は、アドレス参照を受けない局所変
数ｊに対応することから、アセンブラコード生成部１８
はメモリアクセス命令『mov D1,(SP,4)』には別名アク
セスの可能性が存在しないと解釈し、メモリアクセス命
令『mov D1,(SP,4)』の行番号を割り付け資源情報１４
に登録することにより、メモリアクセス命令『mov D1,
(SP,4)』に別名アクセスの可能性が存在しない旨を割り
付け資源情報１４に反映する。

【００８５】第４行目のメモリアクセス命令『mov D0,
(A0)』はアクセス先がレジスタであり、そのアドレスが
間接アドレス指定により指定されていることから、別名
アクセスの可能性が存在すると解釈する。第５行目のメ
モリアクセス命令『mov (SP,4) ,D1』はメモリアドレス
(SP,4)からデータレジスタD1へと保持値を転送するメモ
リアクセス命令である。この際、アセンブラコード生成
部１８はアドレス(SP,4)がどの変数に対応するかである
かを解析する。図７（ｃ）の資源割付結果によれば、ア
ドレス(SP,4)は、アドレス参照を受けない局所変数ｊに
対応することがわかる。

【００８６】参照先がアドレス参照を受けない局所変数
に対応するメモリであるため、アセンブラコード生成部
１８はメモリアクセス命令『mov (SP,4) ,D1』が別名ア
クセスの可能性が存在しないと解釈し、メモリアクセス
命令『mov (SP,4) ,D1』の行番号を割り付け資源情報１
４に登録することにより、メモリアクセス命令『mov(S
P,4) ,D1』に別名アクセスの可能性が存在しない旨を割
り付け資源情報１４に反映する。

【００８７】第６行目の演算命令『add D1,D0』はレジ
スタデータレジスタD1及びデータレジスタD0を用いて減
算を行う演算命令であるので、別名アクセスの可能性解
析の対象とはならない。メモリアクセス命令『mov (SP,
4) ,D1』、メモリアクセス命令『mov D1,(SP,4)』、メ
モリアクセス命令『mov (SP,4) ,D1』の行番号が登録さ
れた結果が図８（ｂ）である。図８（ｂ）を参照すれ
ば、ここに登録された１行目、３行目、５行目のアセン
ブラ命令は『別名アクセスの可能性を有さない』と解釈
される。局所変数から生成されたメモリアクセス命令に
ついては、アクセス先となるアドレス(SP,4)が登録され
ていることがわかる。

【００８８】アセンブラコード生成部１８により、別名
アクセスの可能性の有無が各行について解析されると、
同値資源解析部２５は、各命令についての同値集合を生
成する。第１行目のメモリアクセス命令『mov (SP,4),D
1』が対象命令である場合、ステップｃ６において、ア
ドレス(SP,4)とデータレジスタD1との同値関係{(SP,4),
D1}が形成される。

【００８９】第２行目の減算命令『sub 1,d1』が対象命
令である場合、データレジスタD1の値が変化するので、
ステップｃ３がYesとなりステップｃ１０、ステップｃ
１１に移行する。ステップｃ１１では、その定義先資源
データレジスタD1の同値集合{(SP,4),D1}が削除され
て、同値集合は空集合{}になる。第３行目のメモリアク
セス命令『mov D1,(SP,4)』が対象命令である場合、ア
ドレス(SP,4)の値が変化するので、ステップｃ３がYes
となりステップｃ１０、ステップｃ１１に移行する。ス
テップｃ１１では、その定義先資源データレジスタD1の
同値集合が削除されて、同値集合は空集合になるが、ス
テップｃ６において、アドレス(SP,4)とデータレジスタ
D1との同値関係{(SP,4),D1}が形成される。

【００９０】第４行目のメモリアクセス命令『mov D1,
(A0)』が対象命令である場合、アドレスレジスタA0の値
が変化するので、ステップｃ３がYesとなりステップｃ
１０に移行する。メモリアクセス命令『mov D1,(A0)』
は間接アドレス指定型の定義命令であるためステップｃ
１０がYesとなり、ステップｃ１２に移行する。ステッ
プｃ１２では、同値関係を示すアドレス指定コードの削
除を行おうとするが、同値集合が成立しているアドレス
(SP,4)はアドレス参照を受けない局所変数を示すもので
あるので、削除は免れる。これによりアドレス(SP,4)と
データレジスタD1との同値関係{(SP,4),D1}は、間接ア
ドレス指定型のメモリアクセス命令の前後を通過する。

【００９１】第５行目のメモリアクセス命令『mov (SP,
4),D1』が対象命令である場合、ステップｃ６におい
て、アドレス(SP,4)とデータレジスタD1との同値関係
{(SP,4),D1}が形成される。第６行目の減算命令『add D
1,D0』が対象命令である場合、データレジスタD0の値が
変化するので、ステップｃ３がYesとなりステップｃ１
０、ステップｃ１１に移行する。ステップｃ１１では、
その定義先資源データレジスタD0の同値集合が削除され
ようとするが、データレジスタD0についての同値集合は
存在しないので{(SP,4),D1}は削除されない。

【００９２】メモリアクセス命令『mov (SP,4) ,D1』〜
演算命令『add D1,D0』の各命令について生成された同
値集合を図９に示す。各命令に対して同値集合が生成さ
れると、同値資源間転送命令削除部２６は、直前命令に
おいて同値関係が成立しているにも拘らず、二度手間の
転送を行っている転送命令を検出し、これを冗長転送命
令として削除する。図９における同値集合解析結果を見
れば、アドレス(SP,4)とデータレジスタD1との間の同値
関係が成立しているにも拘らず、第５行目では、アドレ
ス(SP,4)からデータレジスタD1への転送が行われている
ことがわかる。このような冗長転送命令が検出される
と、同値資源間転送命令削除部２６は冗長転送命令を削
除する。削除結果は、図１０に示すものとなる。

【００９３】以上のように本実施形態によれば、基本ブ
ロック中の各命令についての同値集合を解析する際、間
接アドレス指定型のメモリアクセス命令の直前に様々な
アクセス先からなる同値集合が生成されていても、同値
集合に含まれているアドレス指定コードのうち、一時変
数及びアドレス参照を受けない局所変数に対応するも
の、スタックの退避先を示すものは、削除せずに間接ア
ドレス指定型のメモリアクセス命令以降の命令に伝搬す
る。このように伝搬されると、間接アドレス指定型のメ
モリアクセス命令以降に位置する命令のうち、冗長な転
送命令を多く削除することができる。

【００９４】このような削除により、冗長な転送命令を
より多く検出することができるので、これを削除するこ
とにより、実行時間及びプログラムサイズを向上させる
ことができる。尚、第２実施形態において、冗長転送命
令の削除の代わりにコピー伝搬を用いた最適化を行って
もよい。この場合、同値資源解析部２５は、検出された
レジスタアクセス命令及びメモリアクセス命令のアクセ
ス先を指定するアドレス指定コードの全てからなる同値
集合を当該間接アドレス指定型のメモリアクセス命令に
対して生成する。生成後、アセンブラプログラム内の転
送命令を対象命令として取り出し、対象命令の参照先資
源を定義先としている転送命令を検出する。

【００９５】同値集合内のアドレス指定コードのうち、
別名アクセスの可能性が無いものを削除し、コードが削
除されると、対象命令の参照先資源を当該転送命令の参
照先資源に置き換えることが可能であるかを、当該同値
集合に基づいて判定する。転送命令が検出されると、対
象命令の参照先資源を当該転送命令の参照先資源に置き
換えることが可能であるかを、生成された同値集合に基
づいて判定する。可能であれば、対象命令の参照先資源
の置き換えを実行する置換し、置き換えが実行される
と、検出された転送命令を削除する。

【００９６】尚第２実施形態においてオペランド置換を
行っても良い。この構成では、資源コードが削除された
同値集合に基づいて、オペランドが別のものに置き換え
可能か否かを判定し、置き換え可能であり、且つ置き換
えるとコードサイズ又は実行時間が削減できる場合に当
該オペランドを別に置き換える。

【００９７】

【発明の効果】上記目的を達成するため本発明は、プロ
グラミング言語で書かれた文からなるソースプログラム
を翻訳することにより命令列を得るコンパイル装置に用
いられ、命令列を最適化する最適化装置であって、各文
に含まれている変数に対応するメモリをアクセス先に指
定したメモリアクセス命令を前記命令列から取り出す取
出手段と、アクセス先に対応する変数がソースプログラ
ムにおいて別変数での操作によりアクセスを受けるか否
かを各メモリアクセス命令について判定する判定手段
と、別変数名での操作によりアクセスを受けないのであ
れば、取り出されたメモリアクセス命令に、別変数アク
セスの可能性が存在しない旨のマークを付与する付与手
段と、各メモリアクセス命令に付与されたマークを参照
して、前記命令列を最適化する最適化手段とを備え、前
記コンパイル装置は、ソースプログラムに含まれる複数
の文で用いられる複数の変数のそれぞれが、ソースプロ
グラムにおいてアドレス参照を受けることのない局所変
数であるかの分類を行い、分類結果に基づき、各変数に
資源を割り付る割付手段を備え前記判定手段は、取り出
されたメモリアクセス命令のアクセス先が局所変数に対
応しているかを割付手段による分類結果に従って判定す
ることを特徴としている。

【００９８】本発明によれば、間接アドレス指定型のメ
モリアクセス命令の前後に位置するメモリアクセス命令
であっても、そのアクセス先がソースプログラムにおい
て別名アクセスされ得ないものについては、その旨を示
すマークを命令に付与する。最適化手段は命令列に対す
る最適化を、付与されたマークを参照して行う。基本ブ
ロック中に間接アドレス指定型のメモリアクセス命令が
存在する場合でも、その最適化は、効率が損なわれずに
行われる。それ故に、実行時間の短縮及びプログラムサ
イズの削減が可能となる。

【００９９】

【０１００】また、この発明によればアクセス先が局所
変数に対応するメモリであるメモリアクセス命令を別名
アクセスされ得ない命令として判定し、その旨を示すマ
ークを付与するので、別名アクセスされ得ない命令を確
実に検出できる。上記発明を以下のように構成してもよ
い。即ち、プログラミング言語で書かれた文からなるソ
ースプログラムを翻訳することにより命令列を得るコン
パイル装置に用いられ、命令列を最適化する最適化装置
であって、各文に含まれている変数に対応するメモリを
アクセス先に指定したメモリアクセス命令を前記命令列
から取り出す取出手段と、アクセス先に対応する変数が
ソースプログラムにおいて別変数での操作によりアクセ
スを受けるか否かを各メモリアクセス命令について判定
する判定手段と、別変数名での操作によりアクセスを受
けないのであれば、取り出されたメモリアクセス命令
に、別変数アクセスの可能性が存在しない旨のマークを
付与する付与手段と、各メモリアクセス命令に付与され
たマークを参照して、前記命令列を最適化する最適化手
段とを備え、前記コンパイル装置は、ソースプログラム
に含まれるソースプログラムを中間言語に変換した際に
便宜的に文内に挿入された一時変数であるかの分類を行
い、分類結果に基づき、各変数に資源を割り付る割付手
段を備え、前記判定手段は、取り出されたメモリアクセ
ス命令のアクセス先が一時変数に対応しているかを割付
手段による分類結果に従って判定しても良い。このよう
に構成された発明によればアクセス先が一時変数に対応
するメモリであるメモリアクセス命令を別名アクセスさ
れ得ない命令として判定し、その旨を示すマークを付与
するので、別名アクセスされ得ない命令を確実に検出で
きる。

【０１０１】また上記発明を以下のように構成してもよ
い。即ち、プログラミング言語で書かれた文からなるソ
ースプログラムを翻訳することにより命令列を得るコン
パイル装置に用いられ、命令列を最適化する最適化装置
であって、各文に含まれている変数に対応するメモリを
アクセス先に指定したメモリアクセス命令を前記命令列
から取り出す取出手段と、アクセス先に対応する変数が
ソースプログラムにおいて別変数での操作によりアクセ
スを受けるか否かを各メモリアクセス命令について判定
する判定手段と、別変数名での操作によりアクセスを受
けないのであれば、取り出されたメモリアクセス命令
に、別変数アクセスの可能性が存在しない旨のマークを
付与する付与手段と、各メモリアクセス命令に付与され
たマークを参照して、前記命令列を最適化する最適化手
段とを備え、\u前記コンパイル装置は、複数の文に基づ
き複数の命令からなる命令列を生成すると共に、それら
の命令が、レジスタの保持値を退避する命令であるかの
分類を行う命令生成手段を備え、前記判定手段は、前記
分類結果に基づき、取り出されたメモリアクセス命令
が、レジスタの保持値を退避する命令であるかを判定す
ることを特徴としても良い。本構成では、アクセス先が
レジスタ保持値の退避先に対応するメモリであるメモリ
アクセス命令を別名アクセスされ得ない命令として判定
し、その旨を示すマークを付与するので、別名アクセス
され得ない命令を確実に検出できる。

【０１０２】また上記発明を以下のように限定して構成
してもよい。即ち、前記最適化手段は、命令列から、全
メモリアクセス命令を検出する検出部と、検出された全
メモリアクセス命令の中からマークが付与されたものを
除外することにより、メモリアクセス命令を選抜する選
抜部と、間接アドレス指定型のメモリアクセス命令と選
抜されたメモリアクセス命令との間に、当該２命令間の
前後関係が不可侵である旨を示す有向リンクを形成する
形成部と、有向リンクに示された前後関係を遵守しつつ
も、パイプラインアーキテクチャに適合するよう命令の
順序を並べ替えるスケジューリング部とを備えるように
構成してもよい。

【０１０３】本構成によれば、どの二命令の並びが不可
侵であり、どの二命令の並びが不可侵でないかを示す有
向リンクが、間接メモリアクセス命令と別名アクセスの
可能性が無いメモリアクセス命令に対しては形成されな
い。そのため、命令間の有向リンクの絶対数が少なくて
済み、命令の内部の自由度が向上する。そのため、パイ
プラインアーキテクチャに柔軟に対応できるように命令
の配置構造を自在に再編成することができる。

【０１０４】また、前記スケジューリング部は、命令列
内から、ハザード要因となる二命令を検出して、当該二
命令間に他の命令が挿入されるよう、命令の順序を並べ
替えるように構成してもよい。このように構成された発
明によればパイプラインアーキテクチャの遅延要因にな
る二命令の並びにおいて、命令間に他の命令が挿入され
るようにスケジューリングが行われるので、実行時間を
向上させることができる。

【０１０５】また上記発明を以下のように限定して構成
してもよい。即ち、前記最適化手段は、翻訳された命令
列から間接アドレス指定型の命令を取り出す取出部と、
レジスタアクセス命令及びメモリアクセス命令のアクセ
ス先を指定する全ての資源コードからなる同値コード集
合を取り出された間接アドレス指定型のメモリアクセス
命令に対して生成する生成部と、同値コード集合内の資
源コードのうち、付与手段によりマークが付与された命
令のアクセス先以外のものを削除する同値関係削除部
と、同値関係削除部により資源コードが削除された同値
コード集合に基づいて、間接アドレス指定型のメモリア
クセス命令以降に位置する命令が冗長か否かを判定し、
冗長であれば、これを削除する転送命令削除部とを備え
るように構成してもよい。

【０１０６】本構成によれば、同値集合が間接アドレス
指定型のメモリアクセス命令の前後を跨ぐ場合、間接ア
ドレス指定型のメモリアクセス命令のアクセス先が不明
であるために、同値集合が全て抹消されてしまう現象を
回避することができる。同値集合に含まれているアドレ
ス指定コードのうち、別名アクセスの可能性が無いもの
を削除しないで済む。削除量が少ないため、間接アドレ
ス指定型のメモリアクセス命令以降のメモリアクセス命
令において冗長なものをより多く検出することができ
る。

【０１０７】また上記発明を以下のように限定して構成
してもよい。即ち、前記最適化手段は、検出されたレジ
スタアクセス命令及びメモリアクセス命令のアクセス先
を指定する資源コードの全てからなる同値コード集合を
当該間接アドレス指定型のメモリアクセス命令に対して
生成する生成部と、命令列内の転送命令を対象命令とし
て取り出す取出部と、対象命令の参照先資源を定義先と
している転送命令を検出する検出部と、アクセス先を指
定する複数の資源コードからなる同値コード集合を検出
された転送命令に対して生成する生成部と、同値コード
集合内の資源コードのうち、付与手段によりマークが付
与された命令のアクセス先以外のものを削除する同値関
係削除部と、同値関係削除部により資源コードが削除さ
れると、対象命令の参照先資源を当該転送命令の参照先
資源に置き換えることが可能であるかを、当該同値コー
ド集合に基づいて判定する判定部と、可能であれば、対
象命令の参照先資源の置き換えを実行する置換実行部
と、置き換えが実行されると、検出により検出された転
送命令を削除する削除部とを備えることを特徴としても
よい。

【０１０８】本構成によれば同値集合が間接アドレス指
定型のメモリアクセス命令の前後を跨ぐ場合、間接アド
レス指定型のメモリアクセス命令のアクセス先が不明で
あるために、同値集合が全て抹消されてしまう現象を開
発することができる。同値集合に含まれているアドレス
指定コードのうち、別名アクセスの可能性が無いものを
削除しないで済む。削除量が少ないため、転送命令の参
照先を置き換えを用いた冗長転送命令の削除を好適に行
うことができる。

【図面の簡単な説明】

【図１】第１実施形態におけるコンパイラの構成図を示
す。

【図２】（ａ）ソースプログラムの一例を示す図であ
る。 （ｂ）中間言語状態のプログラムの一例を示す図であ
る。 （ｃ）資源割り付け結果の一例を示す図である。 （ｄ）アセンブラ命令の一例を示す図である。

【図３】（ａ）別名アクセス性解析部１９による別名ア
クセスの可能性の解析結果の一例を示す図である。 （ｂ） 割り付け資源情報の一例を示す図である。

【図４】（ａ）図２（ｄ）のアセンブラ命令から生成さ
れた依存グラフの一例を示す図である。 （ｂ）図４（ａ）の依存グラフを用いてのスケジューリ
ング結果の一例を示す図である。

【図５】第１実施形態における依存グラフ生成部の処理
内容を示すフロ−チャ−トである。

【図６】第２実施形態におけるコンパイラの構成図を示
す。

【図７】（ａ）ソースプログラムの一例を示す図であ
る。 （ｂ）資源割り付け結果の一例を示す図である。 （ｃ）アセンブラ命令の一例を示す図である。

【図８】（ａ）別名アクセス性解析部１９による別名ア
クセスの可能性の解析結果の一例を示す図である。 （ｂ）割り付け資源情報の一例を示す図である。

【図９】同値集合の解析結果の一例を示す図である。

【図１０】同値集合の解析結果を用いて転送命令が削除
されたプログラムの一例を示す図である。

【図１１】同値関係集合の生成処理のフロ−チャ−トで
ある。

【図１２】（ａ）ソースプログラムの一例を示す図であ
る。 （ｂ）中間言語状態に変換されたプログラムの一例を示
す図である。 （ｃ）アセンブラ命令の一例を示す図である。 （ｄ）図１２（ｃ）のアセンブラ命令から生成された依
存グラフの一例を示す図である。 （ｅ）図１２（ｄ）の依存グラフを用いてのスケジュー
リング結果の一例を示す図である。

【図１３】（ａ）従来のアセンブラ命令の一例を示す図
である。 （ｂ）図１３（ａ）のアセンブラ命令から生成された同
値集合の一例を示す図である。 （ｃ）図１３（ｂ）の同値集合を用いての冗長転送命令
の削除結果の一例を示す図である。

【図１４】（ａ）間接アドレス指定型のメモリアクセス
命令を含んだアセンブラ命令の一例を示す図である。 （ｂ）図１３（ａ）のアセンブラ命令から生成された依
存グラフの一例を示す図である。

【図１５】（ａ）間接アドレス指定型のメモリアクセス
命令を含むアセンブラ命令の一例を示す図である。 （ｂ）図１５（ａ）のアセンブラ命令から生成された同
値集合の一例を示す図である。 （ｃ）（ｂ）を用いて同値資源間転送命令削除を試みた
結果を示す図である。

【図１６】従来のコンパイラ構成を示す。

【符号の説明】

１０ 解析部 １１ 資源割り付け部 １２ 命令スケジューリング部 １３ コード出力部 １４ 割り付け資源情報 １５ 依存グラフ生成部 １６ 命令並べ替え部 １７ 依存グラフ １８ アセンブラコード生成部 １９ 別名アクセス性解析部 ２０ アセンブラ最適化部 ２２ 同値資源間転送命令最適化部 ２５ 同値資源解析部 ２６ 同値資源間転送命令削除部

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平６−348475（ＪＰ，Ａ) 特開 平７−28654（ＪＰ，Ａ) 特表 平５−508039（ＪＰ，Ａ) Ａ．Ｖ．Ａｈｏ他著，原田賢一訳, 「コンパイラ▲ＩＩ▼」，株式会社サイ エンス社，1990，ｐ．790−796 発明協会公開技報公技番号95−2022号 Ｐ．Ｂ．Ｇｉｂｂｏｎｓ他，”Ｅｆｆ ｉｃｉｅｎｔ Ｉｎｓｔｒｕｃｔｉｏｎ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ ａ Ｐｉｐｅｌｉｎｅｄ Ａｒｃｈｉｔｅｃ ｔｕｒｅ”，ＡＣＭ ＳＩＧＰＬＡＮ Ｎｏｔｉｃｅｓ，1986，Ｖｏｌ．21，Ｎ ｏ．７，ｐ．11−16 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 9/45

Claims (9)

(57)【特許請求の範囲】
1. 【請求項１】 プログラミング言語で書かれた文からな
   るソースプログラムを翻訳することにより命令列を得る
   コンパイル装置に用いられ、命令列を最適化する最適化
   装置であって、 各文に含まれている変数に対応するメモリをアクセス先
   に指定したメモリアクセス命令を前記命令列から取り出
   す取出手段と、 アクセス先に対応する変数がソースプログラムにおいて
   別変数での操作によりアクセスを受けるか否かを各メモ
   リアクセス命令について判定する判定手段と、 別変数名での操作によりアクセスを受けないのであれ
   ば、取り出されたメモリアクセス命令に、別変数アクセ
   スの可能性が存在しない旨のマークを付与する付与手段
   と、 各メモリアクセス命令に付与されたマークを参照して、
   前記命令列を最適化する最適化手段とを備え、 前記コンパイル装置は、 ソースプログラムに含まれる複数の文で用いられる複数
   の変数のそれぞれが、ソースプログラムにおいてアドレ
   ス参照を受けることのない局所変数であるかの分類を行
   い、分類結果に基づき、各変数に資源を割り付る割付手
   段を備え 前記判定手段は、 取り出されたメモリアクセス命令のアクセス先が局所変
   数に対応しているかを割付手段による分類結果に従って
   判定する ことを特徴とする最適化装置。
2. 【請求項２】 プログラミング言語で書かれた文からな
   るソースプログラムを翻訳することにより命令列を得る
   コンパイル装置に用いられ、命令列を最適化する最適化
   装置であって、 各文に含まれている変数に対応するメモリをアクセス先
   に指定したメモリアクセス命令を前記命令列から取り出
   す取出手段と、 アクセス先に対応する変数がソースプログラムにおいて
   別変数での操作によりアクセスを受けるか否かを各メモ
   リアクセス命令について判定する判定手段と、 別変数名での操作によりアクセスを受けないのであれ
   ば、取り出されたメモリ アクセス命令に、別変数アクセ
   スの可能性が存在しない旨のマークを付与する付与手段
   と、 各メモリアクセス命令に付与されたマークを参照して、
   前記命令列を最適化する最適化手段とを備え、 前記コンパイル装置は、 ソースプログラムに含まれるソースプログラムを中間言
   語に変換した際に便宜的に文内に挿入された一時変数で
   あるかの分類を行い、分類結果に基づき、各変数に資源
   を割り付る割付手段を備え、 前記判定手段は、 取り出されたメモリアクセス命令のアクセス先が一時変
   数に対応しているかを割付手段による分類結果に従って
   判定する ことを特徴とする最適化装置。
3. 【請求項３】 プログラミング言語で書かれた文からな
   るソースプログラムを翻訳することにより命令列を得る
   コンパイル装置に用いられ、命令列を最適化する最適化
   装置であって、 各文に含まれている変数に対応するメモリをアクセス先
   に指定したメモリアクセス命令を前記命令列から取り出
   す取出手段と、 アクセス先に対応する変数がソースプログラムにおいて
   別変数での操作によりアクセスを受けるか否かを各メモ
   リアクセス命令について判定する判定手段と、 別変数名での操作によりアクセスを受けないのであれ
   ば、取り出されたメモリアクセス命令に、別変数アクセ
   スの可能性が存在しない旨のマークを付与する付与手段
   と、 各メモリアクセス命令に付与されたマークを参照して、
   前記命令列を最適化する最適化手段と を備え、前記コンパイル装置は、 複数の文に基づき複数の命令からなる命令列を生成する
   と共に、それらの命令が、レジスタの保持値を退避する
   命令であるかの分類を行う命令生成手段を備え、 前記判定手段は、 前記分類結果に基づき、取り出されたメモリアクセス命
   令が、レジスタの保持値を退避する命令であるかを判定
   する ことを特徴とする最適化装置。
4. 【請求項４】 前記最適化手段は、 命令列から、全メモリアクセス命令を検出する検出部
   と、 検出された全メモリアクセス命令の中からマークが付与
   されたものを除外することにより、メモリアクセス命令
   を選抜する選抜部と、 間接アドレス指定型のメモリアクセス命令と選抜された
   メモリアクセス命令との間に、当該２命令間の前後関係
   が不可侵である旨を示す有向リンクを形成する形成部
   と、 有向リンクに示された前後関係を遵守しつつも、パイプ
   ラインアーキテクチャに適合するよう命令の順序を並べ
   替えるスケジューリング部とを備えることを特徴とする
   請求項１〜３の何れかに記載の最適化装置。
5. 【請求項５】 前記スケジューリング部は、 命令列内から、ハザード要因となる二命令を検出して、
   当該二命令間に他の命令が挿入されるよう、命令の順序
   を並べ替えることを特徴とする請求項４に記載の最適化
   装置。
6. 【請求項６】 前記最適化手段は、 翻訳された命令列から間接アドレス指定型の命令を取り
   出す取出部と、 レジスタアクセス命令及びメモリアクセス命令のアクセ
   ス先を指定する全ての資源コードからなる同値コード集
   合を取り出された間接アドレス指定型のメモリアクセス
   命令に対して生成する生成部と、 同値コード集合内の資源コードのうち、付与手段により
   マークが付与された命令のアクセス先以外のものを削除
   する同値関係削除部と、 同値関係削除部により資源コードが削除された同値コー
   ド集合に基づいて、間接アドレス指定型のメモリアクセ
   ス命令以降に位置する命令が冗長か否かを判定し、冗長
   であれば、これを削除する転送命令削除部とを備えるこ
   とを特徴とする請求項１〜３の何れかに記載の最適化装
   置。
7. 【請求項７】 前記最適化手段は、 検出されたレジスタアクセス命令及びメモリアクセス命
   令のアクセス先を指定する資源コードの全てからなる同
   値コード集合を当該間接アドレス指定型のメモリアクセ
   ス命令に対して生成する生成部と、 命令列内の転送命令を対象命令として取り出す取出部
   と、 対象命令の参照先資源を定義先としている転送命令を検
   出する検出部と、 アクセス先を指定する複数の資源コードからなる同値コ
   ード集合を検出された転送命令に対して生成する生成部
   と、 同値コード集合内の資源コードのうち、付与手段により
   マークが付与された命令のアクセス先以外のものを削除
   する同値関係削除部と、 同値関係削除部により資源コードが削除されると、対象
   命令の参照先資源を当該転送命令の参照先資源に置き換
   えることが可能であるかを、当該同値コード集合に基づ
   いて判定する判定部と、 可能であれば、対象命令の参照先資源の置き換えを実行
   する置換実行部と、 置き換えが実行されると、検出により検出された転送命
   令を削除する転送命令削除部とを備えることを特徴とす
   る請求項１〜３の何れかに記載の最適化装置。
8. 【請求項８】 前記最適化手段は、 翻訳された命令列から間接アドレス指定型の命令を取り
   出す取出部と、 レジスタアクセス命令及びメモリアクセス命令のアクセ
   ス先を指定する全ての資源コードからなる同値コード集
   合を取り出された間接アドレス指定型のメモリアクセス
   命令に対して生成する生成部と、 同値コード集合内の資源コードのうち、付与手段により
   マークが付与された命令のアクセス先以外のものを削除
   する同値関係削除部と、 同値関係削除部により資源コードが削除された同値コー
   ド集合に基づいて、間接アドレス指定型のメモリアクセ
   ス命令以降に位置する命令のオペランドが別のものに置
   き換え可能か否かを判定し、置き換え可能であれば、当
   該オペランドを別に置き換える置換部とを備えることを
   特徴とする請求項１〜３の何れかに記載の最適化装置。
9. 【請求項９】 プログラミング言語で書かれた文からな
   るソースプログラム を翻訳することにより命令列を得
   て、命令列の最適化を最適化装置に行わせるコンパイラ
   装置であって、 複数の文に含まれる複数の変数に複数の資源を割り付る
   と共に、それらの変数をソースプログラムにおいてアド
   レス参照を受けることのない変数である局所的変数、又
   は、ソースプログラムを中間言語に変換した際に便宜的
   に文内に挿入された一時変数に分類する処理を行う資源
   割付手段と、 ソースプログラムに基づき複数の命令からなる命令列を
   生成すると共に、それらの命令が、ソースプログラムに
   含まれる文に対応する命令であるか、レジスタの保持値
   を退避する命令であり、文に対応しない命令であるかの
   分類を行う命令生成手段とを備え、 前記最適化装置は、 命令列に含まれるメモリアクセス命令が、変数に対応す
   るメモリをアクセス先とするものであり、尚且つその変
   数がソースプログラムにおいて別変数での操作によりア
   クセスを受けるか否かを、資源割付手段及び命令生成手
   段による分類結果に基づき判定し、その判定結果に基づ
   き、前記命令列を最適化する ことを特徴とするコンパイ
   ラ装置。