JPH11194948A - コンパイラ最適化アルゴリズム - Google Patents

Abstract

(57)【要約】 【課題】 メモリアクセス命令のための自動インクリ
メント機能を支援するコンパイラの低水準オプティマイ
ザにおいて、命令スケジューリングを制約することなく
コードを最適化する。 【解決手段】アドレス計算負担を低減するコンパイラ最
適化アルゴリズムは、最初に、低水準中間表現の中で自
動インクリメント合成の見込みがある候補メモリアクセ
ス命令を識別する。ロードおよび格納に関する候補メモ
リアクセス命令は、命令スケジューリングの前に、疑似
(基準＋変位)アドレッシング・モードを使用するように
変形される。命令スケジュールの後、疑似(基準＋変位)
命令をそれら基準レジスタ・オペランドをインクリメン
トするメモリ演算に変形し、効率的なメモリ・アドレス
を設定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、一般に、アドレ
ス計算負担を低減するコンパイラ・アルゴリズムに関連
し、特に、メモリアクセス命令のための自動インクリメ
ント機能を支援するマイクロプロセッサまたは計算機シ
ステム・アーキテクチャについて、アドレス計算負担を
低減するコンパイラ・アルゴリズムに関連する。

【０００２】

【従来の技術】従来のマイクロプロセッサおよびコンピ
ュータ・アーキテクチャは、典型的に基準＋変位アドレ
ッシング・モードを提供する。限られた数のコンピュー
タ・アーキテクチャは、基準レジスタ自動インクリメン
ト機能を支援するアドレッシング・モードを提供する。
基準レジスタ自動インクリメント・アドレッシング・モ
ードを支援するコンピュータ・アーキテクチャの例は、
IBM370、Digital PDP-11/VAXアーキテクチャ、Apollo P
RISMアークテクチャ、IBM R/S 6000アーキテクチャ、お
よびPA-RISCアーキテクチャを含む。

【０００３】図１は、自動インクリメント・アドレッシ
ング・モードを指定するメモリアクセス命令の２つの例
を示す。図１の例１は、基準レジスタの自動インクリメ
ントがメモリアクセスの後に生じる自動インクリメント
・メモリアクセス命令の例である。ロード命令の結果、
基準レジスタR10によって指定されるメモリ位置の内容
が、レジスタR11にロードされる。R11へのロードの後に
のみ、基準レジスタR10の内容が４だけ「事後インクリ
メント(post-increment)」されるので、ロード操作コー
ド上で「,MA」(modify after)コンプリータ(completer)
となる。対照的に、例２の命令は、基準レジスタ自動イ
ンクリメントが、メモリアクセスの前に生じるメモリア
クセス命令の例である。例２で、基準レジスタR9の内容
は、格納が行われる前に−４だけ「事前インクリメン
ト」される。R9が、−４だけ事前インクリメントされた
後、レジスタR8の内容が、基準レジスタR9によって指定
されるメモリ位置に格納されるので、格納操作コード上
で「,MB」(modify-before)コンプリータとなる。この説
明の残りの部分で、普遍性を損なうことなく、事後イン
クリメント・アドレッシング・モードについて言及す
る。この中の説明およびアルゴリズムは、事前インクリ
メント・アドレッシング・モードの使用に同等に適用さ
れる。

【０００４】コンパイラは、C、BASICまたはFORTRANの
ような高水準プログラミング言語で書かれたソースコー
ドをコンピュータ・ハードウェア上で走る２進イメージ
に翻訳するソフトウェアである。事後インクリメント・
アドレッシング・モードのようなコンピュータ・アーキ
テクチャの強力な機能を利用して、アドレス計算負担を
低減し、コンピュータ性能を高めることがコンパイラの
仕事である。図２は、ソフトウェア・コンパイラのブロ
ック概略図を示す。図２を参照すると、フロントエンド
は、ソースコードの構文上の正当性を調べる役割を果た
す。例えば、コンパイラがＣコンパイラである場合、コ
ードが、適正なＣコードであることを確かめる必要があ
る。コンパイラ・フロントエンド素子200は、ソースコ
ード・ファイル202を読み込み、それを高水準中間表現2
10に翻訳する。高水準オプティマイザ222を選択的に呼
び出して、高水準中間表現210を一層効率的な形式に最
適化することができる。

【０００５】コード生成器230は、高水準中間表現210を
低水準中間表現232に翻訳する。コード生成器によって
生成される低水準中間表現は、典型的に低水準オプティ
マイザに供給される。低水準オプティマイザ234は、低
水準中間表現232を一層効率的な(マシンで実行可能な)
形式に変換する。目的ファイル生成器250は、最適化さ
れた低水準中間表現を目的ファイル252に書き出す。目
的ファイル252は、他の目的ファイル254と共にリンク器
260によって処理され、コンピュータ264上で走ることが
できる実行可能ファイル262を生成する。

【０００６】コンパイラの高水準および低水準オプティ
マイザ素子222,234は、プログラムの意味論(semantics)
(すなわちソースコードから高水準中間表現、そして低
水準中間表現、最終的に実行可能ファイルに翻訳される
命令の意味)を保護しなければならないが、コンピュー
タがより少ない時間で「同等」の命令セットを実行する
ことができるようにコードを変形することができる。現
代のコンパイラは、典型的に高水準中間表現に関して動
作し、その場で特定のプログラムの一層効率的な高水準
中間表現と置き換える高水準オプティマイザ(HLO)を用
いて構築される。例えば高水準オプティマイザは、冗長
な計算を排除することができる。低水準オプティマイザ
が、マシンが実際に理解するものに非常に近いプログラ
ムの表現上で動作することを除いて、低水準オプティマ
イザ(LLO)の場合も、主な目的は、高水準オプティマイ
ザとほぼ同じである。

【０００７】ループ誘導変数(loop induction variabl
e)の線形関数であるアドレスを指定するループ内で起こ
るメモリアクセスは、事後インクリメント・アドレッシ
ング・モードを活用するための最も重要な候補である。
図３Ａは、メモリアクセスがループ内で起こり、アドレ
スがループ誘導変数の線形関数であるＣソースコードの
例を示す。メモリアクセスは、10要素広域アレイ変数A
を参照し、ここで、それぞれの要素は、４バイトの大き
さであると仮定される。図３Ｂは、図３Ａに示されるＣ
ソースコードを実現するための一連のメモリアクセス演
算を示す。メモリ演算の左の数字は、メモリ演算のプロ
グラム順序を示す。

【０００８】典型的に、コンパイラ・アルゴリズムは、
ループ最適化フェーズで、ループ内で行われるメモリ演
算の自動インクリメント能力を活用することを試みる。
図３Ｃは、それぞれのメモリアクセス命令について異な
る基準レジスタが用いられる事後インクリメント・アド
レッシング・モードを使用するように、図３Ｂのメモリ
演算を変形した結果を示す。図４Ａは、図３Ｂに示され
る演算について、仮定的な好ましいスケジューリング順
序を示す。命令の好ましい順序は、図３Ｂに示される命
令の順序とは異なることに注意されたい。図４Ｂは、図
３Ｃに示す命令を、図４Ａに示す好ましいスケジューリ
ング順序で並べたものである。図３Ｃに示す(それぞれ
のメモリアクセス命令について異なる基準レジスタを用
いる事後インクリメント・アドレッシング・モードを使
用する)コード変形は、命令が、図４Ａに示す好ましい
シーケンスで並べ替えられることを可能にするが、基準
レジスタの増加された数を使用することを犠牲にしてそ
れを行う。

【０００９】図４Ｃは、それぞれのメモリアクセス命令
について同じ基準レジスタが使用される事後インクリメ
ント・メモリアクセス命令を使用するように、図３Ｂの
メモリ演算を変形した結果を示す。図４Ｃに示す変形さ
れた命令は、共通の事後インクリメントされる基準レジ
スタR_pへのデータ依存性により、好ましいスケジューリ
ング順序を達成するように並べ替えることができない。

【００１０】図５は、低水準オプティマイザ234を示す
ブロック図である。自動インクリメント・アドレッシン
グ・モードを支援するコンピュータ・アーキテクチャに
おいて、コンパイラのループ最適化フェーズは、(1)事
後インクリメント合成(post-increment synthesis)272
の機会を識別するステップと、(2)候補となるメモリ命
令を、自動インクリメント・メモリ演算274に変形する
ステップを含む。事後インクリメント合成は、ソースプ
ログラムの低水準表現上で動作するループ最適化フェー
ズの一部として実施される。ループ最適化フェーズの中
で実施される合成は、典型的に、オプティマイザの命令
スケジューリング・フェーズ278に先行する。

【００１１】命令スケジューリングの前に事後インクリ
メント命令を合成することに関する問題は、共有の(事
後インクリメントされる)基準レジスタ・オペランドを
参照するメモリアクセス命令間にレジスタ・データ依存
性が導入されることである。(図４Ｃに示されるコード
シーケンスを参照されたい)。これらのレジスタ・デー
タ依存性は、逆に、それらのメモリアクセス命令が互い
に依存しない場合に達成しうる命令スケジュールの品質
に影響を与えることがある。具体的には、共通の事後イ
ンクリメントされる基準レジスタを共有するメモリアク
セス命令が、最終的なスケジュールに現れる順序が制約
される。加えて、共通の事後インクリメントされる基準
レジスタを共有することになる命令について、独立した
複数のメモリアクセス命令を同じプロセッサ・クロック
サイクルにスケジュールする機会が失われることがあ
る。これらの問題は、ソフトウェア・パイプライン化の
影響を受けるループ内で悪化する。これは、基準レジス
タの事後インクリメント演算のシーケンスが、典型的に
１サイクルを形成し、モジュール・スケジュールされる
カーネル内の異なるループ繰り返しに基づくメモリ演算
の混合(intermingling)を制約するからである。

【００１２】アドレス計算負担は、特にロードおよび格
納のために、メモリ・アドレスが、１つの基準レジスタ
・オペランドによって指定される命令セット・アーキテ
クチャについて性能を制限するものでありうる。性能へ
の影響は、アドレス計算のために使用することができる
ALU帯域幅のわずかな量を用いてそのようなアーキテク
チャを実現する場合に一層顕著である。いくつかのアー
キテクチャは、任意の事後インクリメント機能をもつ単
純な基準レジスタ間接アドレシング・モードを提供す
る。従って、整数ALU演算の豊富な混合をもつコードの
ためのそのようなアーキテクチャの場合、コンパイラに
とって、事後インクリメント機能を効果的に使用するこ
とによって、アドレス計算のためのALU使用を低減する
ことが重要である。さらに、事後インクリメント・アド
レッシング・モードを活用するコンパイラ・アルゴリズ
ムは、命令スケジューラを過度に制約しないように動作
すべきである。

【００１３】

【発明が解決しようとする課題】メモリアクセス命令の
ための自動インクリメント・アドレッシング・モードを
支援するアーキテクチャについて、アドレス計算負担を
低減するコンパイラ最適化アルゴリズムが必要とされて
いる。さらにコンパイラ・アルゴリズムは、事後インク
リメント合成の従来の方法の欠点を回避すべきであり、
加えてソフトウェア・パイプライン化されるループ内で
行われるメモリ参照の支援を与えなければならない。

【００１４】

【課題を解決するための手段】この発明は、メモリアク
セス命令のための自動インクリメント・アドレッシング
・モードを支援するアーキテクチャについて、アドレス
計算負担を低減するコンパイラ最適化アルゴリズムを提
供する。コンパイラ・アルゴリズムは、低水準中間表現
の中の自動インクリメント合成の機会を識別する。候補
となるロードおよび格納は、基準＋変位アドレッシング
・モードを使用するように変形される。そのようなアド
レッシング・モードは、目標アーキテクチャ内で支援さ
れることも、されないこともある。命令スケジューリン
グの後、そのような疑似命令を、それら基準レジスタ・
オペランドを自動インクリメントする実際のメモリ演算
に変形して戻し、次に続くメモリ命令の実効アドレスを
設定する。メモリアクセス命令を自動インクリメントす
る合成は、命令スケジューリング・フェーズの後に実施
されるので、従来の自動インクリメント合成方法の前述
の欠点は回避される。

【００１５】この発明に従うコンパイラ最適化アルゴリ
ズムは、自動インクリメント合成の作業を２つのステッ
プに分ける。最初にコンパイラ・アルゴリズムは、自動
インクリメント・アドレッシング・モードを利用するこ
とができる候補となるメモリ参照命令を識別する。主な
候補は、ループ誘導変数の線形関数であるアドレスを指
定するループ内で行われるメモリアクセス命令である。
候補となるメモリアクセス命令は、仮の(疑似)基準＋変
位アドレッシング・モードを使用するように変形され
る。それから命令スケジューラ・フェーズは、通常のメ
モリアクセス命令によく似たこれらの命令をスケジュー
ルすることを許される。コンパイラ最適化アルゴリズム
の第２のステップは、スケジュールされた疑似メモリ演
算を、自動インクリメント・アドレッシング・モードを
使用する実際のメモリ演算に変形するステップである。
自動インクリメント最適化の見込みのある目標を識別す
る第１のステップは、命令スケジューリングの前に実施
される。疑似命令を、自動インクリメント・アドレッシ
ング・モードを使用するコードに変形するステップは、
命令スケジューリングの後であるが、レジスタ割当ての
前に実施される。

【００１６】ループ誘導変数の単純な線形関数として表
すことができるアドレスを指定するループ内に生じるメ
モリアクセス命令の自動インクリメント機能の使用を容
易にするために、候補となるメモリアクセス命令が、ル
ープ最適化フェーズの一部として識別される。しかし、
スケジューリングの前に自動インクリメントを実現する
従来の方法と異なって、自動インクリメント演算の実際
の合成は、命令スケジューリング・フェーズの後まで遅
延される。その代わりに、自動インクリメント合成の候
補であるメモリアクセス命令は、第１のフェーズの間
に、(基準＋変位)アドレッシング・モードを支援する
(疑似)メモリ操作コードに変形される。基準レジスタ
は、ループ本体の外側で初期化され、関連するループ誘
導変数と並行して、ループ本体の中で更新される。典型
的にループの最後に必要とされる基準レジスタの更新
は、次のループ繰り返しのために基準レジスタがインク
リメントされなければならない量を指定する別の疑似命
令によって実施される。

【００１７】スケジューリング・フェーズが呼び出さ
れ、疑似メモリアクセス命令を通常のメモリアクセス命
令として処理する。全ての他のデータ依存性が満たされ
るという条件で、人工の基準レジスタ依存性が、そのよ
うな命令の間に仮定されることはなく、従ってそれらを
任意の相対的な順序でスケジュールすることができ、ま
たは同じクロックサイクルに実行するためにスケジュー
ルすることもできる。それぞれの疑似メモリアクセス命
令について基準レジスタおよび変位量を合計する必要が
あるALU演算は、事実上実施されることが仮定され、命
令スケジューリングの前にコード・ストリームの中で個
々の明確な命令として表されない。命令スケジュールが
生成されると、自動インクリメント合成の第２のフェー
ズが呼び出される。第２のフェーズは、生成されたスケ
ジュールの中で同じ基準レジスタを共有する疑似メモリ
命令の位置を調べる。同じ基準レジスタを共有する複数
の疑似メモリ命令は、実際の実行可能なメモリ演算に変
換され、それらメモリ演算は、次に続くメモリ演算につ
いて実効アドレスを設定するに十分なだけそれらの基準
レジスタ・オペランドを自動インクリメントする。

【００１８】スケジュールされた(基準＋変位)メモリア
クセス命令を変形するステップは、命令の基準レジスタ
・オペランドを修正するステップを含み、従って修正さ
れる基準レジスタ値は、次に続くメモリアクセス命令に
よって指定されるメモリ・アドレスに一致する。次に続
くメモリアクセス命令の中の自動インクリメントされた
基準レジスタ値を直接作り出すことによって、下流のメ
モリアクセス命令についてメモリ・アドレスを設定する
必要があるALU命令が省かれ、それによってアドレス計
算負担を軽減する。

【００１９】コンパイラ・アルゴリズムは、基準＋変位
または基準＋索引レジスタを含む多様なアドレッシング
・モードを用いるアーキテクチャに適用できる。利益
は、実効アドレス仕様の単純なレジスタ間接形式を支援
するだけのマシンについて一層顕著であるが、それは、
メモリアクセス命令のための自動インクリメント能力を
支援するどんなマシンにも適用できる。

【００２０】最大フィールド幅を越える自動インクリメ
ントの直接量の場合、索引レジスタは、ループ本体の外
側で初期化され、疑似メモリ演算は、予め初期化された
索引レジスタによって、その基準レジスタ・オペランド
を自動インクリメントするメモリ命令に変形される。同
じ基準レジスタを共有するが、同じクロックサイクルに
スケジュールされている疑似メモリ演算は、選択的に新
しい基準レジスタをクローン生成することによって特別
に処理される。実効アドレスが、自動インクリメント・
メモリ演算を通してループのまわりを「縫うように進め
られる(threaded)」ことができない状況で、アルゴリズ
ムは、パス長への影響が最小限である位置で、生成され
たスケジュールに「溢れコード(spill code)」を挿入す
ることを許す。特に、自動インクリメント量が、非常に
大きく、レジスタ関連の自動インクリメント・アドレッ
シング・モードが、目標アーキテクチャ内で利用できな
いとき、溢れコードを、スケジュールされたコードに挿
入する必要がある。

【００２１】コンパイラ最適化アルゴリズムは、ソフト
ウェアでパイプライン化されるループを含むコードに適
用でき、多数のALU演算によって支配されるループにつ
いて小さい起動間隔(ii)をもつソフトウェア・パイプラ
イン・スケジュールの生成を許す。ソフトウェア・パイ
プライナが、特定の起動間隔についてスケジュールを生
成したあと、生成されたソフトウェア・パイプライン
は、自動インクリメント合成の影響下にある。再び「溢
れ」コードを、ソフトウェア・パイプラインに挿入しな
ければならない可能性がある。現在の「ii」について、
生成されたソフトウェア・パイプラインにそのような溢
れコードを収容することができない場合、生成されたソ
フトウェア・パイプラインは捨てられ、新しいソフトウ
ェア・パイプラインが、より大きい起動間隔について求
められる。

【００２２】ここで述べた発明の理念及び利点の更なる
理解は、添付の図面を参照する以下の説明によって達成
することができる。

【００２３】

【発明の実施の形態】図６は、この発明に従う低水準オ
プティマイザのブロック図を示す。コンパイラ最適化プ
ロセスの一部は、事後インクリメント・アドレッシング
・モードを利用することができる候補となるメモリ参照
命令の識別(520)である。事後インクリメント・アドレ
ッシング・モードを使用する見込みのある候補を識別す
るステップが、命令スケジューリング(526)の前に実施
される。事後インクリメント・アドレッシング・モード
を利用することができる他の候補がありうるが、主な候
補は、ループ誘導変数の線形関数であるアドレスを指定
するループ内に生じるメモリアクセス命令である。

【００２４】ループ誘導変数の単純な線形関数として表
すことができるアドレスを指定するループ内で起こるメ
モリアクセス命令について、事後インクリメント機能の
使用を容易にするために、候補となるメモリアクセス命
令が、ループ最適化フェーズ260の一部として識別され
る。しかし、スケジューリングの前に事後インクリメン
トを実現する従来の方法とは異なり、事後インクリメン
ト演算の実際の合成は、命令スケジューリング・フェー
ズ526の後まで遅延される。

【００２５】事後インクリメント合成の候補であるメモ
リアクセス命令は、第１のフェーズの間に、(基準＋変
位)アドレッシング・モード530を使用する仮のメモリア
クセス命令に変形される。これは、候補となるメモリア
クセス命令が、直ちに自動インクリメント命令(274)に
変形される従来の最適化アルゴリズムとは異なる(図５
を参照)。このコンパイラ・アルゴリズムで、基準レジ
スタは、ループ本体の外で初期化され、関連するループ
誘導変数(図７Ａに示される具体例を参照)への更新と並
行して、ループ本体内で更新される。典型的にループの
最後に必要とされる基準レジスタの更新は、基準レジス
タが次のループ繰り返しのためにインクリメントされな
ければならない量を指定する別の疑似命令によって実施
される。

【００２６】図７Ａは、基準＋変位アドレッシング・モ
ードを使用するように変形された後(ステップ530)の、
図３Ｂのメモリアクセス演算を図示する。メモリアクセ
ス命令の左の数は、それらの実行シーケンスを示す。共
通基準レジスタR_pは、ループの外で初期化され、A[2]の
アドレスを保持する。それは、ループ本体の最後に、疑
似加算命令によって４だけインクリメントされる。事後
インクリメント合成の候補であるメモリアクセス命令
が、基準＋変位アドレッシング・モードを使用するよう
に変形された後(ステップ530)、命令スケジューラ・フ
ェーズ(526)が、呼び出される。

【００２７】図７Ｂは、図４Ａに示す好ましいスケジュ
ーリング順序で並べられた図７Ａのメモリアクセス命令
を示す。命令スケジューラは、図７Ｂに示される疑似メ
モリアクセス命令を、通常のメモリアクセス命令として
処理する。全ての他のデータ依存性が満たされるという
条件で、人工の基準レジスタ依存性が、そのような命令
の間に仮定されることはなく、従ってそれらを、任意の
相対的な順序でスケジュールし、または同じクロックサ
イクルに実行するためにスケジュールすることができ
る。それぞれの疑似メモリアクセス命令について基準レ
ジスタおよび変位量を合計する必要があるALU演算は、
事実上実施されることが仮定され、命令スケジューリン
グの前にコード・ストリームの中で個別の明確な命令と
して表されない。基準レジスタR_pを更新する疑似加算命
令は、スケジューラによってゼロサイクルを要するよう
に、すなわちマシン資源を消費しないように仮定され
る。

【００２８】命令スケジュールが生成されると、事後イ
ンクリメント合成の第２のフェーズが呼び出される。コ
ンパイラ最適化アルゴリズムの第２のフェーズは、スケ
ジュールされた疑似メモリアクセス命令を、事後インク
リメント・アドレッシング・モードを使用する実際のメ
モリアクセス命令に変形するステップ(ステップ540)を
含む。図７Ｃは、(基準＋変位)アドレッシング・モード
に代わって、事後インクリメント・アドレッシング・モ
ードを使用するようにメモリアクセス命令を変形した後
の、図７Ｂに示すスケジュールされたコードを示す。第
２のフェーズは、生成されたスケジュール内で同じ基準
レジスタを共有する疑似メモリ命令の位置を調べる。同
じ基準レジスタを共有する疑似メモリアクセス命令は、
実行可能なメモリアクセス命令に変換され、変換された
メモリアセス命令は、次に続くメモリアクセス命令のた
めの実効アドレスを設定するに十分なだけ、それらの基
準レジスタオペランドを事後インクリメントする。

【００２９】コンパイラ・アルゴリズムは、(基準＋変
位)または(基準＋索引レジスタ)を含む多様なアドレッ
シング・モードをもつアーキテクチャを支援する。利益
は、実効アドレス仕様の単純なレジスタ間接形式のみを
支援するマシンについて顕著であるが、それは、メモリ
アクセス命令のための自動インクリメント能力を支援す
るどのマシンにも適用できる。

【００３０】図８Ａは、同時に２つの命令を実行するこ
とができるコンピュータについて、図３Ｂに示す一連の
メモリアクセス命令のための好ましいスケジューリング
順序の一例を示す。図８Ｂは、図３Ｂの命令を、図８Ａ
に示すスケジューリング順序で並べたものである。図８
Ａに示すスケジューリング順序について、ロード命令71
0、712は、サイクル0に同時に実施され、格納命令714、
716は、サイクル1に同時に実施される。

【００３１】この発明のコンパイラ・アルゴリズムによ
ると、命令スケジューリングの後、(基準＋変位)アドレ
ッシング・モードを使用する候補となるロードおよび格
納は、次に続くメモリアクセス命令の実効アドレスを設
定するようにそれらの基準レジスタオペランドを自動イ
ンクリメントするメモリアクセス命令に変形される。し
かし、共通の基準レジスタを共有する複数の(基準＋変
位)疑似メモリアクセス命令が、(図８Ｂに示されるよう
に)同じサイクルの中でスケジュールされるとき、事後
インクリメント合成(事後インクリメント・アドレッシ
ング・モードを活用するようにメモリアクセス命令を変
形すること)は、一層複雑になる。

【００３２】図９Ａは、(基準＋変位)アドレッシング・
モードに代わって事後インクリメント・アドレッシング
・モードを使うための、図８Ｂのメモリ演算の変形を示
す。しかし、図９Ａに示される具体化は、完全には正し
くない。図９Ａに示すコードシーケンスに関する問題
は、同じサイクルに実行されようとする命令間にレジス
タ依存性があることである。メモリ参照は、同じサイク
ルの中で生じる別のメモリ参照のために、基準レジスタ
を事後インクリメントすることができない。例えば、サ
イクル0で、基準レジスタR_pは、同時に、第１の命令に
よって上書きされ、第２の命令によって読み込まれる。
図９Ａに示す具体化の場合、２つのロードまたは格納命
令は、データ依存性を回避するように連続的に実施され
る必要がある。このように、４つのメモリ演算は、図８
Ｂに示すスケジュールされたコードシーケンスについて
期待される２サイクルとは対照的に、実行するのに４サ
イクルかかる。

【００３３】この問題が起きないようにするため、複数
の(基準＋変位)メモリアクセス命令が、同じクロックサ
イクルにスケジュールされるとき、アルゴリズムは、同
時にスケジュールされるメモリ演算で使用される新しい
基準レジスタ(以下、基準レジスタ・クローンと呼ぶ)を
準備する。基準レジスタ・クローンの使用は、そのよう
な命令間のデータ依存性を排除する。図９Ｂは、基準レ
ジスタ・クローン(R_q)を使用して２サイクル・スケジュ
ールを保護するように、図８Ｂに示されるメモリ演算を
変形したものである。

【００３４】図１０は、それぞれのサイクルに２つのメ
モリ演算を実行することができるマシンについて、基準
レジスタをクローン生成するために使用される論理のフ
ローチャートを示す。図１０に示す論理は、同時に２よ
り多くのメモリアクセス命令を実行することができるマ
シンのために、基準レジスタをクローン生成するように
容易に拡張することができる。図１０を参照すると、第
１のコンパイラ・アルゴリズムは最初に、同じ基準レジ
スタが、同じクロックサイクルに２つのメモリアクセス
演算によって使用されるかどうか調べる(ステップ72
0)。同じ基準レジスタが、同じクロックサイクルに２つ
のメモリアクセス演算によって使用される場合、２つの
メモリ命令の一方は、(上流のメモリアクセス命令によ
って適切に事後インクリメントされた)オリジナルの基
準レジスタを使用するように変形され、他方のメモリ命
令は、オリジナルの基準レジスタの「クローン」を使用
するように変形される(ステップ736)。基準レジスタを
クローン生成した後、(基準＋変位)メモリアクセス命令
は、自動インクリメント・メモリアクセス命令に変形さ
れる(740)。図１０のブロック540の中で実施されるステ
ップは、疑似(基準＋変位)メモリアクセス命令の全てが
処理されるまで、メモリアクセス命令を含むスケジュー
ルの中のそれぞれのサイクルについて繰り返される。

【００３５】コンパイラ・アルゴリズムを複雑にする別
の要因は、メモリ参照の実効アドレスを、上流の事後イ
ンクリメントによって設定することができないときに生
じる。目標アーキテクチャのための事後インクリメント
量は、４ビットまたはそれ以下でなければならないが、
望ましい事後インクリメント量を４ビットで表すことが
できない例を考える。例えば、４ビットで表すことがで
きる承認された事後インクリメント値の範囲は、−16と
＋15の間であるので、＋16の事後インクリメント量は許
容されない。図１１Ａは、図３Ｂに示す命令を、図８Ａ
に示すシーケンスに従ってスケジュールしたものであ
る。図１１Ａに示すコード・シーケンスは、目標量が４
ビットより大きいことを示す。具体的には、図１１Ａの
第１の格納は、索引レジスタR_cを使用する。R_cは、ルー
プの外で16に初期化され、基準レジスタR_pの値をインク
リメントするのに使用される。格納命令810は、レジス
タ・事後インクリメント・アドレッシング・モードの使
用を示す。

【００３６】図１１Ａに示す具体化は、レジスタ・事後
インクリメント・アドレッシング・モードを支援するア
ーキテクチャについての選択であるが、全てのアーキテ
クチャが、このアドレッシング・モードを支援する必要
はない。メモリ参照の実効アドレスを、上流の事後イン
クリメントによって設定することができない(どんな理
由であろうと)ケースでは、レジスタ割当て器が溢れコ
ードを挿入するのとほとんど同じようにして、明確な加
算演算が、スケジュールされたコードに挿入される必要
がある。「溢れコード」演算は、ポスト・レジスタ割当
て命令スケジューリングの影響を受ける。図１１Ｂは、
アーキテクチャが４ビット・事後インクリメント値のみ
を支援し、レジスタ・事後インクリメント・アドレッシ
ング・モードを支援しない場合、図３Ｂに示す命令を図
８Ａに示す順序でスケジュールした図を示す。

【００３７】図１１Ａに示す例を図１１Ｂに示す例と比
較すると、レジスタ・事後インクリメント・アドレッシ
ングが支援されず、事後インクリメント格納命令が、通
常の格納命令に変更されるので、基準レジスタR_cは、排
除されている。その基準レジスタを事後インクリメント
する格納命令に代わって、基準レジスタは、溢れコード
命令820によって明確にインクリメントされる。溢れコ
ードのスケジュールへの挿入は、効率的な方法で行われ
ることが望ましい。好ましくは、溢れコード命令は、そ
れを他の命令と同時に実行することができるサイクルの
中にスケジュールされるべきである。これらの演算は、
性能への影響を最小限にしながら最終的なスケジュール
に収容することができると期待される。

【００３８】図１０は、それぞれのサイクルに２つのメ
モリ演算を実行することができるマシンに関して、基準
レジスタのクローン生成が使用される場合の、この発明
に従うコンパイラ・アルゴリズムを実現するステップの
フローチャートを示す。図１２は、それぞれのサイクル
に多数のメモリ演算を実行することができるマシンを支
援するように、図１０のフローチャートを変更したもの
であり、そこで、基準レジスタのクローン生成または溢
れコード挿入のいずれかを使用して、事後インクリメン
ト合成を容易にする。図１２に示すフローチャートによ
って実現される第１のステップは、同じクロック・サイ
クルにスケジュールされる２つのメモリアクセス命令に
よって、同じ基準レジスタが使用されるかどうか調べる
(ステップ720)。異なる基準レジスタが使用される場合
(904)、現在のサイクルの中にスケジュールされるそれ
ぞれのメモリアクセス命令に代わって、上流のメモリア
クセス命令が、その基本のレジスタを自動インクリメン
トすることができるかどうか判断が行われる。現在のサ
イクルの中にスケジュールされるそれぞれのメモリアク
セス命令に代わって、その基準レジスタを自動インクリ
メントすることができるメモリアクセス命令が利用可能
である場合(914)、現在のサイクルの中にスケジュール
されるメモリアクセス命令に代わって、上流のメモリア
クセス命令が、自動インクリメントされる(740)。現在
のサイクルにスケジュールされるメモリアクセス命令
は、適切な基準レジスタを使用するように変換される(9
38)。

【００３９】現在のサイクルにスケジュールされるメモ
リアクセス命令に代わって、その基準レジスタを自動イ
ンクリメントするために上流のメモリアクセス命令が利
用可能でない場合(916)、または同じサイクルにスケジ
ュールされる少なくとも２つのメモリアクセス命令によ
って、同じ基準レジスタが使用される場合(918)、基準
レジスタのクローン生成が、溢れコードを挿入するより
効率的かどうか判断が行われる(920)。溢れコードを挿
入する方が効率的である場合(922)、現在のメモリアク
セス命令に代わって、溢れコードが挿入される(ステッ
プ930)。基準レジスタのクローン生成の方が効率的であ
る場合(936)、適当なクローン生成される基準レジスタ
が、利用可能であるか判断が行われる。適当な基準レジ
スタ・クローンが利用可能である場合(937)、現在のサ
イクルの中のメモリアクセス命令に代わって、上流のメ
モリアクセス命令が、それらの基準レジスタを自動イン
クリメントするように変形される(740)。現在のサイク
ルの中にスケジュールされるメモリアクセス命令は、適
切な基準レジスタを使用するように変形される(938)。
適当な基準レジスタ・クローンが利用可能でない場合(9
39)、適切な基準レジスタを使用するように、現在のサ
イクルの中のメモリアクセス命令を変換する(938)前
に、新しい基準レジスタ・クローンが適切に初期化され
る(730)。

【００４０】ステップ920は、基準レジスタのクローン
生成または溢れコードの挿入のどちらが効率的であるか
判断する。図１３Ａは、1つのメモリ演算および1つのAL
U演算を同じサイクルの中で実施することができるマシ
ンについてスケジュールされる２つのメモリアクセス命
令を使った例を示す。目標アーキテクチャが、４ビット
またはそれ以下の事後インクリメント量を支援すると仮
定すると、図１３Ａの第２のロードは、自動インクリメ
ント・アドレッシング・モードを使用することができな
い。具体的には、第２のロードは、目標アーキテクチャ
によって支援されない16の事後インクリメント量を指定
する必要がある。

【００４１】図１３Ｂは、図１３Ａに示す命令の第１の
代替の具体例であり、基準レジスタのクローン生成技術
が使用された場合を示す。図１４Ａは、図１３Ａに示す
命令の第２の代替の具体例であり、溢れコード挿入技術
が使用された場合を示す。図１４Ａに示す命令を実行す
るには余分なサイクルが要求されるので、オプティマイ
ザは、ステップ920で、基準レジスタのクローン生成が
より効率的であると選択するであろう。

【００４２】図１４Ｂは、３つのロード命令および分岐
論理を含むループの例を示す。図１４Ｂに示される例
で、分岐は、経路1010aまたは1010bをとることができ
る。図１５Ａは、図１４Ｂに示す例の具体例であって、
溢れコードがループに挿入された場合を示す。図１５Ａ
に示す例で、図１４Ｂの一連の命令は、事後インクリメ
ント・アドレッシング・モードを使用するように変形さ
れ、溢れコード1020が、経路1010aに沿って分岐を補償
するように挿入される。代替の実施例を図１５Ｂに示
す。図１５Ｂは、図１４Ｂに示す例の具体化であって、
溢れコードの挿入の代わりに、基準レジスタのクローン
生成が使用される場合を示す。この例の基準レジスタの
クローン生成は、命令を省かず(実際に、結果として命
令が高価な位置で挿入される)、必要とされる基準レジ
スタの総数に加算されるので、この例では、オプティマ
イザによって、溢れコードを挿入することの方がより効
率的であると判断されるだろう(ステップ920)。

【００４３】さらに事後インクリメント合成技術は、ソ
フトウェア・パイプライン化に関連して作用する。ソフ
トウェア・パイプライン化は、ループに適用できる命令
スケジューリング技法である。基本的なソフトウェア・
パイプライン化技術を説明するために、図１６Ａについ
て考える。図１６Ａは、32の8バイトの２倍精度要素を
含むアレイ「A」の通して進み、それぞれのアレイ要素
を1.0ずつインクリメントするＣソースプログラムを示
す。現代の最適化コンパイラによって、命令スケジュー
リングの前に生成することができる最適化されたマシン
を、図１６Ｂに示す。図１６Ｂで、ループの繰り返し数
を制御する命令は、分かり易くするため省略されてい
る。

【００４４】図１６Ａに示す最適化されたマシン命令を
参照すると、レジスタR_pは、ループの外側で初期化さ
れ、浮動小数点ロード(FLOAD)および浮動小数点格納(FS
TORE)命令の両方で基準レジスタとして使用されて、ア
レイ変数「A」の要素にアクセスすることに注意された
い。基準レジスタR_pは、それぞれのループ繰り返しの中
で８ずつインクリメントされる。それぞれのアレイ要素
値は、レジスタR_aにロードされ、レジスタR_cの内容(値
1.0を保持するようにループの外側で初期化される)と合
計され、その結果は、レジスタR_sに書き込まれる。レジ
スタR_sの内容は、アレイ要素に格納され、戻される。

【００４５】図１６Ｂに示す３つの浮動小数点命令のた
めの待ち時間は、FLOAD−４サイクル、FADD−４サイク
ルおよびFSTORE−１サイクルと仮定される。ここで、レ
ジスタRに値を書き込む命令IのためのLサイクルの待ち
時間は、命令Iが実行された後に、Lサイクルまたはそれ
以上に渡ってパイプライン・ストールを経験することな
く、レジスタRに書き込まれた値を読み込もうとする次
の命令が実行できることを意味する。

【００４６】これらの待ち時間の仮定が与えられると
き、図１７Ａは、図１６Ｂに示すループのそれぞれの繰
り返しを実行するために必要とされるサイクルの数を示
す。FLOAD命令は、サイクル0でその実行を開始すると仮
定すると、Fadd命令は、サイクル４でのみ実行を開始す
ることができ、Faddによって計算された結果は、サイク
ル８でのみ格納することができる。言い換えれば、３つ
の浮動小数点命令をそれぞれのループ繰り返しについて
実行するには、合計で９サイクルかかる。命令スケジュ
ーリングの後、FSTORE命令は、次のループ繰り返しの中
で実行されるFLOADに代わって、その基準レジスタR_pを
８ずつ事後インクリメントするように変形されることに
注意されたい。(スケジューリング・アルゴリズムは、
データ間の依存性のリストに従って、命令の「リスト」
が１度に１つスケジュールされると考えるので、図１７
Ａに示される命令スケジュールは、「リスト」スケジュ
ールと呼ばれる。) ソフトウェア・パイプライン化アルゴリズムは、最初
に、異なる固定された長さのステージに分割することが
できるリスト・スケジュールを生成し、連続的なループ
繰り返しに属するステージの実行をオーバラップさせる
ことによって、ループの性能スループットを改善しよう
とする。図１７Ｂは、図１７Ａのリスト・スケジュール
の、便宜上A、B、Cと呼ばれる等しい長さをもつ３つの
別個のステージへの分割を示し、それぞれのステージ
は、実行の３サイクル分を表している。従って、１つの
ループ繰り返しは、それぞれが３サイクルである実行の
３つのステージから構成される「ソフトウェア・パイプ
ライン」から成る。

【００４７】図１８は、連続的なループ繰り返しのため
のソフトウェア・パイプラインを、時間内にどのように
オーバラップさせることができるか示す。それぞれのル
ープ繰り返しは、時間内に１つのソフトウェア・パイプ
ライン・ステージずつずらされる。それぞれの連続的な
ループ繰り返しの実行の開始の遅延は、ちょうど１ソフ
トウェア・パイプライン・ステージであり、ループ「起
動間隔(initiation interval)」または略して「ii」と
呼ばれる。iiは、例えば３サイクルである。３つの連続
的なループ繰り返しの実行を始めた後、規則的なパター
ンが現れることに注意されたい。具体的には、ソフトウ
ェア・パイプラインのあらゆるステージが同時に実行さ
れ、すなわち３つのループ繰り返しの各々からの１ステ
ージが実行中となる。

【００４８】実行のこの「定常状態」のパターンは、ソ
フトウェア・パイプライン・カーネルと呼ばれるものを
構成し、図１８の中で枠に囲まれて示されている。ソフ
トウェア・パイプライン・カーネルに属する命令は、カ
ーネルのオーバラップされたパイプライン・ステージの
最後のセットの終わりから、カーネルのオーバラップさ
れるステージの最初のセットに分岐して戻ることによっ
て、繰り返し実行できることに注意されたい。十分な数
のループ繰り返しが実行されると、ソフトウェア・パイ
プライン・カーネルから出る。カーネルに入る前に実行
されるソフトウェア・パイプライン・ステージは、ソフ
トウェア・パイプライン化されたループの「プロロー
グ」を含む。カーネルを出た後に実行されるソフトウェ
ア・パイプライン・ステージは、ソフトウェア・パイプ
ライン・カーネルの「エピローグ」を含む。

【００４９】この例では、ソフトウェア・パイプライン
・カーネルのそれぞれの繰り返しは、オリジナルのルー
プの実行の３回繰り返しを表す。それぞれのオリジナル
のループ繰り返しが、９サイクルかかるところで、新し
いループ繰り返しが、iiサイクルごとに始められるの
で、ループの全体のスループットが改善される。具体的
には、ソフトウェア・パイプライン・スケジュールを実
行するのに要する時間は一般に、プロローグ_長さ＋(カ
ーネル_長さ*カーネル_繰り返し数)＋エピローグ_長
さ、と計算される。

【００５０】この例で、カーネルは、オリジナルのルー
プの３回繰り返しを表すので、カーネルは、１０回実行
され、これはオリジナルの３０回のループ繰り返しを示
し、残りの２つのオリジナルのループ繰り返しは、プロ
ローグおよびエピローグの一部として実行される。プロ
ローグおよびエピローグは、それぞれ２つのパイプライ
ン・ステージの長さであり、すなわちそれぞれ６サイク
ルである。このように、図１７Ａに示すリスト・スケジ
ュールを使用してオリジナルのループの全ての浮動小数
点命令を実行するのに(9*32)=288サイクルを要する代わ
りに、図１８に示すソフトウェア・パイプライン化され
たループは、実行するのに6+(9*10)+6=102サイクルを要
し、これは、ほぼ３倍の性能改善を表す。

【００５１】事後インクリメント合成が、ソフトウェア
・パイプライン・スケジューリングの前に実施される場
合、連続的なループ繰り返しの実行をオーバラップする
ことはできないことに注意されたい。例えば、ループ繰
り返し１のステージCに属するFSTOREの前に、ループ繰
り返し２のステージAに属するFLOADを実行することはで
きない。FLOADが、事後インクリメントされた基準レジ
スタ値を使用して次のアレイ要素値をロードすることが
できるようになる前に、FLOADは、FSTOREがその基準レ
ジスタR_pを事後インクリメントするまで待つ必要がある
からである。言い換えると、図１７Ａに示すリスト・ス
ケジュールを順次使用して、それぞれのループ繰り返し
を実行することが強制される。

【００５２】図１９は、FLOADおよびFSTOREが、(疑似)
(基準＋変位)アドレッシング・モードを使用するように
変形されると仮定して得られるソフトウェア・パイプラ
イン・スケジュールを示す。共通の基準レジスタR_pは、
疑似加算命令によって24ずつ(８のオリジナル・ループ
・ストライドの３倍を表す)インクリメントされること
に注意されたい。この疑似加算命令は、ソフトウェア・
パイプライン器によって、マシン資源を消費しないよう
に仮定され、従ってソフトウェア・パイプライン・カー
ネルの長さに影響を与えない。

【００５３】図２０は、事後インクリメント合成の後の
図１９に示されるソフトウェア・パイプライン・スケジ
ュールを示す。ソフトウェア・パイプライン・カーネル
内のそれぞれのメモリアクセス命令は、次に続くメモリ
アクセス演算のためにその基準レジスタを事後インクリ
メントするように変形されることに注意されたい。

【００５４】図２１は、ループについてソフトウェア・
パイプライン・スケジュールを生成するために従来から
使用されている論理を表すフローチャートを示す。最初
に、リスト・スケジュールを生成して、通常のリスト・
スケジュールを越える性能改善をもたらすソフトウェア
・パイプライン・スケジュールのための起動間隔(MAXi
i)の上限を決定する(ステップ920)。(ソフトウェア・パ
イプライン・スケジュールによってMAXiiより大きいま
たはそれに等しいiiを用いて達成されるラン・タイム性
能は、リスト・スケジュールによって達成されるものほ
ど良くない)。ソフトウェア・パイプライン・スケジュ
ールのための起動間隔(MINii)の下限は、ある発見的手
法を使用して評価される(ステップ921)。ソフトウェア
・パイプライン化するアルゴリズムは、MINiiおよびMAX
iiの間のiiを用いて適正なソフトウェア・パイプライン
・スケジュールを見つようとし(ステップ924)、それ
は、MINiiに等しいiiから始まる(ステップ932)。特定の
iiについてソフトウェア・パイプライン・スケジュール
が見つかった後、レジスタ割当てが、ソフトウェア・パ
イプライン・カーネルに関して試みられる(ステップ93
6)。iiについて、ソフトウェア・パイプライン・スケジ
ュールが見つからない場合(938)、あるいはレジスタ割
当てが、当該iiで失敗した場合(940)、iiは、１だけイ
ンクリメントされ(ステップ942)、より高いii値で、ソ
フトウェア・パイプライン・スケジュールを探す(ステ
ップ924)。このプロセスは、(スケジュールを乱すこと
なく)レジスタ割当てが可能なMINiiおよびMAXiiの間のi
iについて、ソフトウェア・パイプライン・スケジュー
ルが見つかるまで繰り返される(ステップ946)。そのよ
うなスケジュールが見つからない場合(948)、ソフトウ
ェア・パイプライン・スケジュールに代わって、通常の
リスト・スケジュール(950)が、当該ループについて生
成される。

【００５５】図２２は、図２１のフローチャートをどの
ように変更して、事後インクリメント合成を収容するか
示す。特定のii値について、ソフトウェア・パイプライ
ン・スケジュールが見つかった後(ステップ930)、レジ
スタ割当ての前に、事後インクリメント合成が試みられ
る(ステップ960)ことに注意されたい。事後インクリメ
ント合成が成功した場合のみ(ステップ964)、レジスタ
割当てが試みられる(ステップ936)。(前述したように)
溢れコードを生成する必要があり、見つけられたソフト
ウェア・パイプライン・スケジュールに溢れコードを収
容することができない場合、事後インクリメント合成
は、特定のii値で失敗することがある(ステップ966)。
あるいは、事後インクリメント合成は、ソフトウェア・
パイプライン・スケジュール内の「レジスタ圧力」を増
やすことができる基準レジスタをクローン生成し、レジ
スタ割当てを失敗させなければならないことがある。ど
ちらのケースも、当該iiで見つけられたソフトウェア・
パイプライン・スケジュールは放棄され、より高いii値
の新しいソフトウェア・パイプライン・スケジュールを
見つけようとする。MlNiiとMAXii(948)の間のiiについ
て、ソフトウェア・パイプライン・スケジュールを見つ
けることができない場合、そのループについて通常のリ
スト・スケジュールが生成され(ステップ950)、事後イ
ンクリメント合成(ステップ970)は、前述したようにリ
スト・スケジュール上で実施される。

【００５６】上の記述は、説明を目的としており、限定
的なものではない。例えば、典型的に事後インクリメン
トまたは自動インクリメント・モードのアドレッシング
・モードに関して記述された応用例および概念は、アル
ゴリズムのいくらかの修正が必要とされうるが、事前イ
ンクリメント・アドレッシング・モードにも適用でき
る。同様に、事前インクリメントまたは自動インクリメ
ント・モードのアドレッシング・モードに関して記述さ
れた応用例および概念は、アルゴリズムのいくらかの修
正が必要とされうるが、事後インクリメント・アドレッ
シング・モードにも適用できる。更に、典型的に候補と
なるメモリ命令は、(基準＋変位)アドレッシング・モー
ドに変形されるが、代替の実施例で、候補となるメモリ
命令は、目標アーキテクチャによって支援されないアド
レッシング・モードのような別のアドレッシング・モー
ドに変形される。

【００５７】本発明は例として次の実施態様を含む。 （１）自動インクリメント・アドレッシング・モードを
支援する目標アーキテクチャについてプログラムの低水
準表現を最適化するコンパイラ最適化アルゴリズムであ
って、自動インクリメント合成のために候補となるメモ
リアクセス命令を識別するステップと、候補となるメモ
リアクセス命令を基準＋変位のメモリアクセス命令に変
形するステップと、基準＋変位のメモリアクセス命令
を、それらの基準レジスタ・オペランドを自動インクリ
メントするメモリアクセス命令に変換するステップと、
を含むコンパイラ最適化アルゴリズム。

【００５８】（２）候補となるメモリアクセス命令を基
準＋変位メモリアクセス命令に変形するステップは、命
令スケジューリングの前に実施される、上記(1)に記載
の方法。 （３）基準＋変位メモリアクセス命令を、それらの基準
レジスタ・オペランドを自動インクリメントするメモリ
アクセス命令に変換するステップは、命令スケジューリ
ングの後に実施される、上記(1)に記載の方法。 （４）候補は、ループ誘導変数の線形関数であるアドレ
スを指定するループ内に起こるメモリアクセス命令であ
る、上記(2)に記載の方法。

【００５９】（５）基準＋変位メモリアクセス命令は、
それらの基準レジスタ・オペランドを事後インクリメン
トするメモリアクセス命令に変換され、方法はさらに、
同じサイクルの中にスケジュールされる複数のメモリア
クセス命令によって、同じ基準レジスタが使用されるか
どうか判断するステップを含む、上記(3)に記載の方
法。 （６）同じサイクルの中にスケジュールされる少なくと
も２つのメモリアクセス命令によって、同じ基準レジス
タが使用されない場合、該サイクルのメモリアクセス命
令に代わって、上流のメモリアクセス命令が、それら基
準レジスタ・オペランドを事後インクリメントするよう
に変形される、上記(5)に記載の方法。

【００６０】（７）同じサイクルの中にスケジュールさ
れる複数のメモリアクセス命令によって、同じ基準レジ
スタが使用されないとき、下流のメモリアクセス命令に
代わって、上流のメモリアクセス命令が、それらの基準
レジスタを事後インクリメントすることができるかどう
か判断するステップを含む、上記(5)に記載の方法。 （８）下流のメモリアクセス命令に代わって、上流のメ
モリアクセス命令が、その基準レジスタ・オペランドを
事後インクリメントすることができると判断されると
き、下流のメモリアクセス命令に代わって、その基準レ
ジスタ・オペランドを事後インクリメントするメモリア
クセス命令に上流のメモリアクセス命令を変形するステ
ップを含む、上記(7)に記載の方法。

【００６１】（９）適当な基準レジスタを使用するよう
に、下流のメモリアクセス命令を変換するステップを含
む、上記(8)に記載の方法。 （１０）基準レジスタのクローン生成が、溢れコードの
挿入よりも効率的かどうか判断するステップを含む、上
記(5)に記載の方法。

【００６２】（１１）溢れコードの挿入が、基準レジス
タのクローン生成より効率的であると判断されるとき、
メモリアクセス命令に代わって、溢れコードを挿入する
ステップを含む、上記(10)に記載の方法。 （１２）基準レジスタのクローン生成、溢れコードの挿
入より効率的であると判断されるとき、基準レジスタを
クローン生成するステップを含む、上記(10)に記載の方
法。 （１３）適切な基準レジスタを使用するようにメモリア
クセス命令を変換するステップを含む、上記(12)に記載
の方法。

【００６３】（１４）適切な基準レジスタを使用するよ
うにメモリアクセス命令を変換するステップを含む、上
記(11)に記載の方法。 （１５）ループについてリスト・スケジュールを生成し
て最大起動間隔(MAXii)を決定し、最小起動間隔(MINii)
を評価し、ソフトウェア・パイプライン・スケジュール
を見つけようとするステップを含む、上記(3)に記載の
方法。 （１６）ソフトウェア・パイプライン・スケジュール
が、MAXiiより小さいiiについて見つかった場合、最小
起動間隔がインクリメントされる、上記(15)に記載の方
法。

【００６４】（１７）ソフトウェア・パイプライン・ス
ケジュールが見つからず、iiが、MAXiiより大きい場
合、ループについてリスト・スケジュールが生成され、
リスト・スケジュールについて自動インクリメントが合
成される、上記(16)に記載の方法。 （１８）ソフトウェア・パイプライン・スケジュール
が、MAXiiより小さいiiについて見つかった場合、ソフ
トウェア・パイプライン・スケジュールについて、自動
インクリメントを合成することができるか判断するステ
ップを含む、上記(15)に記載の方法。

【００６５】（１９）ソフトウェア・パイプライン・ス
ケジュールについて自動インクリメントを合成すること
ができるとき、ソフトウェア・パイプライン・カーネル
をレジスタ割当てすることができるかどうか判断するス
テップを含む、上記(18)に記載の方法。 （２０）ソフトウェア・パイプライン・カーネルをレジ
スタ割当てすることができると判断されるとき、ソフト
ウェア・パイプライン・スケジュールを生成するステッ
プを含む、上記(19)に記載の方法。

【００６６】（２１）自動インクリメント合成のために
候補となるメモリアクセス命令を識別するステップと、
候補となるメモリアクセス命令を、目標アーキテクチャ
によって支援されないアドレッシング・モードを用いる
メモリアクセス命令に変形するステップと、支援されな
いメモリアクセス命令を、自動インクリメント・メモリ
アクセス命令に変換するステップと、を含むコンパイラ
最適化アルゴリズム。

【００６７】

【発明の効果】本発明によれば、メモリアクセス命令の
ための自動インクリメント機能を支援するコンパイラに
おいて、命令スケジューリングを制約することなく、自
動インクリメント機能をメモリアクセス命令に合成する
ことができ、それによってアドレス計算負担の低減を可
能にする。

【図面の簡単な説明】

【図１】自動インクリメント・アドレッシング・モード
を使用するメモリ・アクセス命令の２つの例を示す。

【図２】現代の最適化コンパイラのブロック概略図。

【図３】図３Ａは、メモリアクセスがループ内に起きる
Ｃソースの断片を示す図。図３Ｂは、図３Ａに示すルー
プ内に起こるメモリアクセスに対応する一連のメモリア
クセス演算を示す図。図３Ｃは、それぞれの事後インク
リメントするメモリアクセス命令について異なる基準レ
ジスタを使用する、図３Ｂの第１の具体例を示す図。

【図４】図４Ａは、図３Ｂに示す演算について好ましい
命令スケジューリング順序の例を示す図。図４Ｂは、図
３Ｃに示す命令を図４Ａに示す好ましいスケジューリン
グ順序で並べた図。図４Ｃは、事後インクリメント・メ
モリアクセス命令を使用する図３Ｂの第２の具体例を示
す図。

【図５】従来の低水準オプティマイザのブロック図。

【図６】この発明に従う低水準オプティマイザのブロッ
ク図。

【図７】図７Ａは、基準＋変位アドレッシング・モード
を使用する図３Ｂに示すメモリ・アクセス命令の具体例
を示す図。図７Ｂは、図４Ａに示す好ましいスケジュー
リング順序で並べた図７Ａの具体例を示す図。図７Ｃ
は、基準＋変位アドレッシング・モードの代わりに事後
インクリメント・アドレッシング・モードを使用するよ
うにメモリアクセス命令を変形させた後の図７Ｂに示す
スケジュールされたコードを示す図。

【図８】図８Ａは、２つの命令を同時に実施することが
できるコンピュータについて、図３Ｂに示す一連のメモ
リアクセス演算のための好ましいスケジューリング順序
の例を示す図。図８Ｂは、図８Ａに示すスケジューリン
グ順序で並べた図３Ｂに示す命令を示す図。

【図９】図９Ａは、基準＋変位アドレッシング・モード
の代わりに事後インクリメント・アドレッシング・モー
ドを使用するように変形され、許容されないスケジュー
ルになった図８Ｂのメモリアクセス命令を示す図。図９
Ｂは、２サイクルのスケジュールを保護するように基準
レジスタ・クローン(R_q)を使用するための図８Ｂに示す
メモリ演算の変形を示す図。

【図１０】それぞれのサイクルに２つのメモリ演算を実
行することができるマシンについて、基準レジスタをク
ローン生成するために使用される論理のフローチャー
ト。

【図１１】図１１Ａは、図８Ａに示すシーケンスに従っ
てスケジュールされた図３Ｂに示す命令を示す図。図１
１Ｂは、図８Ａのスケジューリング順序に従う、図３Ｂ
に示す命令の具体例を示す図。

【図１２】自動インクリメント合成が、基準レジスタの
クローン生成または溢れコードの挿入のいずれかを必要
としうる場合、それぞれのサイクルの中で複数のメモリ
演算を実行することができるマシンについて、自動イン
クリメント・アドレッシング・モードを活用するために
使用される論理のフローチャート。

【図１３】図１３Ａは、１つのメモリ演算および１つの
ALU演算を同じサイクルの中で実施することができるマ
シンについてスケジュールされる２つのメモリアクセス
命令をもつ例を示す。図１３Ｂは、基準レジスタがクロ
ーン生成された場合の図１３Ａに示される命令の第１の
代替の具体例を示す図。

【図１４】図１４Ａは、溢れコードの挿入が実施された
場合の図１３Ａに示される命令の第２の代替の具体例を
示す図。図１４Ｂは、３つのロード命令および分岐論理
を含むループの例を示す図。

【図１５】図１５Ａは、溢れコードがループに挿入され
た場合の、事後インクリメント合成後の図１４Ｂに示す
例の具体化を示す図。図１５Ｂは、基準レジスタがクロ
ーン生成された場合の、事後インクリメント合成後の図
１４Ｂに示す例の具体化を示す図。

【図１６】図１６Ａは、32の８バイトの２倍精度要素を
含むアレイを通して進み、それぞれのアレイ要素を1.0
ずつインクリメントするＣソースプログラムを示す図。
図１６Ｂは、命令スケジューリングの前に、現代の最適
化コンパイラによって生成することができる最適化され
たマシン命令を示す図。

【図１７】図１７Ａは、図１６Ｂに示す最適化されたマ
シン命令についてリスト・スケジュールを示す図。図１
７Ｂは、図１７Ａのリスト・スケジュールを、便宜上
A、B、Cと付された等しい長さをもつ３つの別個のステ
ージに分割することを示し、それぞれのステージは、３
サイクル分の実行を表している図。

【図１８】図１７Ａに示すリスト・スケジュールについ
て、オーバラップされたソフトウェア・パイプライン・
スケジュールを示す図。

【図１９】(疑似)(基準＋変位)アドレッシング・モード
を使用するように、FLOADおよびFSTORE命令を変形する
と仮定するときに得られるソフトウェア・パイプライン
・スケジュールを示す図。

【図２０】事後インクリメント合成の後の図１９示すソ
フトウェア・パイプライン・スケジュールを示す図。

【図２１】ループについてソフトウェア・パイプライン
・スケジュールを生成するために従来から使用される論
理を示すフローチャート。

【図２２】この発明のコンパイラ・アルゴリズムを取り
入れたループについてソフトウェア・パイプライン・ス
ケジュールを生成するために使用される論理を示すフロ
ーチャート。

【符号の説明】

２０２ ソースコード ２２２ 高水準オプティマイザ ２３０ コード生成器 ２３４ 低水準オプティマイザ ２５０ 目的ファイル生成器

Claims (1)

【特許請求の範囲】
1. 【請求項１】自動インクリメント・アドレッシング・モ
   ードを支援する目標アーキテクチャについて、プログラ
   ムの低水準表現を最適化するコンパイラ最適化アルゴリ
   ズムであって、 自動インクリメント合成のための候補となるメモリアク
   セス命令を識別するステップと、 上記候補となるメモリアクセス命令を、基準＋変位アド
   レッシング・モードを使用するメモリアクセス命令に変
   形するステップと、 上記基準＋変位アドレッシング・モードを使用するメモ
   リアクセス命令を、基準レジスタ・オペランドを自動イ
   ンクリメントするメモリアクセス命令に変換するステッ
   プと、を含むコンパイラ最適化アルゴリズム。