JPH04263331A - コンピュータ用大域命令スケジューラ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータ用の命令
スケジューラ、特に、並列／パイプライン式のコンピュ
ータと共に使用するのに適した方法で、基本のブロック
境界を超えて諸命令をスケジュールする（大域スケジュ
ーリング）ことを可能にする、命令スケジューラに関す
るものである。

【０００２】

【従来の技術】命令スケジューリングは、プログラム文
を、プロセッサによるその実行の前に再構成もしくは変
形して、コンパイルした命令の間の実行時間の起こり得
る遅れを少なくしようとするプロセスである。この命令
スケジューリングは通常、中間言語のレベル又はアセン
ブリ・コードのレベルで実行するものである。そのよう
な変形は、データ依存性を保存しなければならず、また
その変形は、その他の制約も受けるようになっている。 このことは、パイプライン式のマシン・アーキテクチャ
（これは、命令の実行をオーバーラップさせることによ
って処理能力を増大させることが可能）に対してコンパ
イルする場合に、とりわけ有利となり得るものである。 例えば、もしある値Ｖの取出しとその使用との間に１サ
イクルの遅れが在る場合には、そのＶとは独立していて
しかも実行に対し“レディ”となっているある命令によ
って、その遅れを“カバー”することが望ましくなる。

【０００３】この命令スケジューリングのある特定の用
途は、いわゆる命令セット削減形コンピュータ（ＲＩＳ
Ｃ）の分野にある。このＲＩＳＣコンピュータの入門的
解説は、次の論文中に見ることができる。 Ｒ１．　　パターソン（Ｄ．Ａ．Ｐａｔｔｅｒｓｏｎ）
，Ｄ．Ａ．の“命令セット削減形コン　ピュータ”，Ａ
ＣＭ通信（ｔｈｅ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏ
ｆ　ｔｈｅ　ＡＣＭ）（１９　８５年１月）の８−２１
ページ

【０００４】７０年代後半に出現した、高速のプロセッ
サを構築するためのＲＩＳＣのアプローチは、プログラ
ム命令を流線形（ストリームライン）にする必要性を強
調したものである。その結果として、パイプライン方式
を十分活用して性能を向上させるためには、中間言語又
はアセンブリ・コード・レベルで諸命令を再構成しなけ
ればならない。命令スケジューリングのこの負担は、Ｒ
ＩＳＣプロセッサ用のコードを生成するコンパイラを最
適化する際にかかることになる。通常、それらコンパイ
ラは、その基本ブロック・レベルで命令スケジューリン
グを実行し、これにより、ＲＩＳＣプロセッサのパイプ
ライン式構造が提起する問題の大部分を解決している。

【０００５】幾つかの機能性ユニットをもったプロセッ
サに関する命令レベルでのスケジューリングに対して、
その１つのアプローチが、以下の論文に記載されている
。 Ｒ２．　　バーンスタイン（Ｄ．Ｂｅｒｎｓｔｅｉｎ）
、ヤッフェ（Ｊ．Ｍ．Ｊａｆｆｅ）及びロデ（Ｍ．Ｒｏ
ｄｅｈ）の“スピリング無しの並列のスケジューリング
算術演算処　理及びロード処理”，ＳＩＡＭ計算誌（Ｓ
ＩＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ）、
１９８９年１２月

【０００６】パイプライン式マシンに関する命令レベル
でのスケジューリングに対するアプローチは、以下の一
連の論文中に記述されている。 Ｒ３．　　バーンスタイン（Ｄ．Ｂｅｒｎｓｔｅｉｎ）
及びゲルトナー（Ｉ．Ｇｅｒｔｎｅｒ）の“１サイクル
の最大遅れをもったパイプライン式プロセッサ上での式
のスケジューリング”，プログラミング言語及びシステ
ムでのＡＣＭ紀要（ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ
　ｏｎ　ＰｒｏｇｒａｍｍｉｎｇＬａｎｇｕａｇｅｓ　
ａｎｄ　Ｓｙｓｔｅｍｓ）、Ｖ　ｏｌ．１１，Ｎｏ．１
，１９８９年１月，５７−６６ページ Ｒ４．　　バーンスタイン（Ｄ．Ｂｅｒｎｓｔｅｉｎ）
，ロデ（Ｍ．Ｒｏｄｅｈ）及びゲルナトー（Ｉ．Ｇｅｒ
ｔｎｅｒ）の“パイプライン式マシン上での算術式をス
ケジュール　するための近似アルゴリズム”，アルゴリ
ズム・ジャーナル（ｔｈｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ａ
ｌｇｏｒｉｔｈｍｓ），１０（１９８９年３月），１２
０−１３９　ページ Ｒ５．　　ヘネシー（Ｊ．Ｊ．Ｈｅｎｎｅｓｓｙ）及び
グロス（Ｔ．Ｇｒｏｓｓ）の“パイプライン　制約のポ
ストパス・コード最適化”，プログラミング言語及びシ
ステムのＡＣＭ紀要（ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎ
ｓ　ｏｎ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｌａｎｇｕａｇｅ
ｓ　ａｎｄ　Ｓｙｓｔｅｍｓ），５（１９８３年７月）
，４２２−４４８ページ Ｒ６．　　ギボンス（Ｐ．Ｂ．Ｇｉｂｂｏｎｓ）及びマ
チニック（Ｓ．Ｓ．Ｍｕｃｈｎｉｃｋ）の“パイ　プラ
イン・アーキテクチャ用の効率的命令スケジューリング
”，コンパイラ構造に関するＡＣＭシンポジウムの紀要
（ｔｈｅ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆＡＣＭ　Ｓｙ
ｍｐｏｓｉｕｍ　ｏｎ　Ｃｏｍｐｉｌｅｒ　Ｃｏｎｓｔ
ｒｕｃｔｉｏｎ），１９８６年６月 Ｒ７．　　ワレン（Ｈ．Ｗａｒｒｅｎ）の“ＩＢＭ　Ｒ
ＩＳＣシステム／６０００プロセ　ッサ用の命令スケジ
ューリング”，ＩＢＭ研究開発ジャーナル（ｔｈｅ　Ｉ
ＢＭ　Ｊｏｕｎａｌ　ｏｆ　Ｒｅｓｅａｒｃｈ　ａｎｄ
Ｄｅｖｅｌｏｐｍｅｎｔ），Ｖｏｌ．３４，Ｎｏ．ｌ，
１９９０年１月，８５−９２ページ

【０００７】非常に
長い命令ワード（ＶＬＩＷ）のマシン（即ち，一つのマ
シンのそれぞれの部分についての幾つかの在来の命令が
組合わさったマシン）に関する命令レベルでのスケジュ
ーリングについて、それに対するアプローチは、次の論
文に記述されている。 Ｒ８．　　エリス（Ｊ．Ｒ．Ｅｌｌｉｓ）の“ブルドッ
グ：ＶＬＩＷアーキテクチャ用コ　ンパイラ”，Ｒｈ．
Ｄ．論文，Ｙａｌｅ　Ｖ／ＤＣＳ／ＲＲ−３６４　，エ
ール大学，１９８５年２月

【０００８】しかるに、ｎ個の機能性ユニットをもった
マシンは、その思想が、各サイクル毎にｎ個もの命令を
実行できるようにすることであるのに対し、パイプライ
ン式マシンでは、その目標が、サイクル毎に新たな命令
を発して、いわゆるＮＯＰ（無動作）を効果的に除くこ
とである。しかしながら、それらの両タイプのマシンに
おいて、コンパイラの方から要求される共通の事柄は、
コード中に、データに対し独立の命令を発見して、マシ
ン資源をより一層良く活用するコードを生成できるよう
にすることである。

【０００９】そのようなデータ独立性の命令を基本ブロ
ック内で見い出すことができ、また基本ブロック境界を
超えて命令を移動させる必要はない、というのが一般的
な見解であった。１つの基本ブロックは、一連の連続し
た命令の命令シーケンスであって、制御フローは、その
シーケンスの初めのところで入り、そして待機あるいは
分岐の可能性もなくそのシーケンスの終わりのところで
出るようになっている（但し、その出口点では、待機／
分岐の可能性はある）。事実上、命令スケジューリング
の実現に関する以前のものは全て、基本ブロック内での
スケジューリングに集中していた（上記参考文献Ｒ５，
Ｒ６，及びＲ７を参照されたい）。

【００１０】しかしながら、基本的なＲＩＳＣアーキテ
クチャに対してさえも、そのような制限されたタイプの
スケジューリングは、多くのユニックス（Ｕｎｉｘ）タ
イプ（Ｕｎｉｘは、ＡＴ＆Ｔベル研究所の商標である）
のプログラム（これは、予測不可能な分岐で終了するよ
うな多くの小さな基本ブロックを包含している）を含む
大きなプログラム・ファミリーの場合には、多くのＮＯ
Ｐをもつコードをもたらす虞れがある。科学計算用プロ
グラムの場合には、基本ブロックは、大きくなる傾向が
あるから、それらの問題は、それ程厳しいものになりそ
うにはない。

【００１１】最近、新たなタイプのアーキテクチャが開
発されつつあり、このアーキテクチャは、サイクル当た
り１つより多い命令を発する能力によって、ＲＩＳＣを
拡張しようとしている。１例として、次の論文を参照さ
れたい。 Ｒ９．　　グローブ（Ｒ．Ｄ．Ｇｒｏｖｅｓ）及びエー
ラー（Ｒ．Ｏｅｈｌｅｒ）の“ＩＢＭ第２世代ＲＩＳＣ
プロセッサ・アーキテクチャ”，コンピュータ設計に関
するＩＥＥＥ会議議事録（ｔｈｅ　Ｐｒｏｃｅｅｄｉｎ
ｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｎｆｅｒｅｎｃｅ
　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｄｅｓｉｇｎ），１９８９
年１０月，１３４−１３７ページ

【００１２】このタイプの高速プロセッサ機構は、スー
パースカラー・アーキテクチャもしくはスーパーパイプ
ライン式アーキテクチャと呼ばれており、これは、コン
パイラに対してより深刻な挑戦を提起するものであるが
、その理由は、基本ブロックレベルでの命令スケジュー
リングが、マシン資源を希望する程度まで活用するよう
なコードの生成を可能にする程十分なものではないため
である。以下の論文を参照されたい。 Ｒ１０．ジューピ（Ｎ．Ｐ．Ｊｏｕｐｐｉ）及びウォー
ル（Ｄ．Ｗ．Ｗａｌｌ）の“スーパースカラー及びスー
パーパイプライン式のマシン用に利用可能な命令レベル
平行性”，第３回ＡＳＰＬＯＳ会議議事録（ｔｈｅ　Ｐ
ｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅＴｈｉｒｄ　ＡＳ
ＰＬＯＳ　Ｃｏｎｆｅｒｅｎｃｅ），１９８９年４月，
２７２−２８２ページ

【００１３】スーパースカラー・マシン用の命令スケジ
ューリングを追及する最近の試みは、次の論文に報告さ
れている。 Ｒ１１．ゴランビック（Ｍ．Ｃ．Ｇｏｌｕｍｂｉｃ）及
びレイニッシュ（Ｖ．Ｒａｉｎｉｓｈ）、の　“基本ブ
ロックを超える命令スケジューリング”，ＩＢＭ研究開
発ジャーナル（ｔｈｅ　ＩＢＭ　Ｊｏｕｒｎａｌ　ｏｆ
　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ
）、Ｖｏ　ｌ．３４，Ｎｏ．１，１９９０年１月，９３
−９７ページ

【００１４】本論文においては、基本ブロ
ックの範囲を超えたスケジューリングのためのコード反
復手法が考察され、この結果、コンパイルされたコード
の走行時間の相当な改善が行われた。しかしながら、そ
こで説明されている方法は、依然として更に改善の余地
があるものである。

【００１５】スーパースカラー・プロセッサは、少数の
資源をもったＶＬＩＷマシンとして考えることができる
。このようなＶＬＩＷマシン用のコードをコンパイルす
るアプローチは、上記文献Ｒ８と以下の論文にも記載さ
れている。 Ｒ１２．フィッシャー（Ｊ．Ｆｉｓｈｅｒ）の“トレー
ス・スケジューリング：大域マイクロコード短縮技法”
，コンピュータＩＥＥＥ会報（ｔｈｅ　ＩＥＥＥ　Ｔｒ
ａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ），
Ｃ−３０，Ｎｏ．７，１９８１年７月，４７８−４９０
ページ Ｒ１３．エビシオグル（Ｋ．Ｅｂｃｉｏｇｌｕ）及びナ
カタニ（Ｔ．Ｎａｋａｔａｎｉ）の“ＶＬＩＷアーキテ
クチャ上で予測不能の分岐をもつループを並行化する新
たなコンパイル技法”，並列計算用の言語とコンパイラ
に関する講習会議事録（ｔｈｅ　Ｐｒｏｃｅｅｄｉｎｇ
ｓ　ｏｆ　ｔｈｅ　ｗｏｒｋｓｈｏｐ　ｏｎ　Ｌａｎｇ
ｕａｇｅｓ　ａｎｄ　Ｃｏｍｐｉｌｅｒｓ　ｆｏｒＰａ
ｒａｌｌｅｌ　Ｃｏｍｐｕｔｉｎｇ），１９８９年８月
，アーバナ

【００１６】

【発明が解決しようとする課題】本発明の目的は、効率
的で柔軟性のあるやり方で大域的（即ち、ブロック間）
スケジューリングを実行することができる命令スケジュ
ーラを提供することである。

【００１７】

【課題を解決するための手段】本発明の第一面によれば
、入力コード・シーケンス中の命令間のデータ依存性と
制御依存性を表すプログラム依存性グラフ生成ロジック
と、このプログラム依存性グラフに応答して前記入力コ
ード・シーケンスの命令を、適当な場合には、基本ブロ
ック境界を超えて再編成して、出力コード・シーケンス
を生成する順序付けロジックと、を備えるコンピュータ
用命令スケジューラを提供する。

【００１８】本発明によれば、基本ブロック境界を超え
る大域的スケジューリングを、プログラム依存性グラフ
の使用によって実行することができる。この命令スケジ
ューリングは、コンパイラのレジスタ割当てフェーズを
呼び込む前あるいはその後で適用することができる。命
令を再編成のためにより大きな柔軟性を残すことができ
るように、そのレジスタ割当てステップ前に本スケジュ
ーリングを実行することが有利である。

【００１９】好ましくは、前記のプログラム依存性グラ
フは、制御依存性サブグラフとデータ依存性サブグラフ
より成るプログラム依存性グラフを生成する。その制御
依存性サブグラフは、入力コード・シーケンスが規定す
るプログラムにおける制御依存性を表すものであり、そ
してそのデータ依存性サブグラフは、それにおけるデー
タ依存性を表すものである。

【００２０】順序付け（又はスケジューリング）ロジッ
クは、好ましくは、その制御依存性サブグラフを使用す
ることにより、入力コード・シーケンス中の基本ブロッ
クの命令をブロック毎にスケジュールし、そして、この
順序付けロジックは、現在スケジュール中の現行ブロッ
クについて、この現行ブロックに対し命令を寄与させる
ことが可能な候補ブロックのリストを判定する。制御依
存性サブグラフにおいて現行ブロックに等価でありかつ
その現行ブロックにより支配されると識別したブロック
に加えて、候補ブロックのリストは、制御依存性サブグ
ラフにおいて、現行ブロックの直後の後継者、もしくは
その現行ブロックに等価のブロックであって現行ブロッ
クにより支配されるそのブロックの直後の後継者、とし
て識別した全ブロックを含む。

【００２１】前記のデータ依存性グラフから、順序付け
ロジックは、前記候補ブロック集合の内から１組の候補
命令を決めることができる。この候補命令リストは、好
ましくは、命令が１ブロック境界を超えて移動させこと
ができないタイプでなくかつ／又は命令が推測的にスケ
ジュールできないタイプではない限り、現行ブロック又
は候補ブロック集合中の１つのブロックに属する、実行
が推測的な命令を含む、全ての命令を含む。この候補命
令リストから、順序付けロジックは、機械記述に従って
、次にスケジュールするべき一つもしくはそれ以上の命
令を決める。

【００２２】推測的命令の概念は、次の論文に求めるこ
とができる。 Ｒ１４．エビシオグル（Ｋ．Ｅｂｃｉｏｇｌｕ）の“シ
ーケンス性ソフトウエアのＶＬＩＷアーキテクチャ用設
計思想”，並列計算に関するＩＦＩＰ会議議事録（ｔｈ
ｅ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＦＩＰ
　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐａｒａｌｌｅｌ　Ｃ
ｏｍｐｕｔｉｎｇ），１９８９年８月 Ｒ１５．スミス（Ｍ．Ｄ．Ｓｍｉｔｈ），ラム（Ｍ．Ｓ
．Ｌａｍ）及びホロヴィッツ（Ｍ．Ａ．Ｈｏｒｏｗｉｔ
ｚ）の“スーパースカラー・プロセッサにおける静的ス
ケジューリングを超えるブースト”，コンピュータ・ア
ーキテクチャ会議議事録（ｔｈｅ　Ｐｒｏｃｅｅｄｉｎ
ｇｓ　ｏｆ　ｔｈｅ　Ｃｏｍｐｕｔｅｒ　Ａｒｃｈｉｔ
ｅｃｔｕｒｅ　Ｃｏｎｆｅｒｅｎｃｅ），１９９０年５
月，３４４−３５４ページ

【００２３】しかしながら、
これらの論文では、推測的命令は、相当な実行時間オー
バーヘッドを支えるマシン・アーキテクチャによりサポ
ートしなければならない、ということが示唆されている
。本発明では、その欠点は、プログラム依存性グラフ内
に集めたデータを使用することによって、克服すること
ができる。その従来技術では、命令スケジューリングに
対しプログラム依存性グラフを使用することについては
示唆してはいない。

【００２４】事実、本発明においては、機械記述は、好
ましくは、ある範囲のコンピュータを表すパラメータ型
機械記述と特定のコンピュータ用の１組のスケジューリ
ング・ヒューリスティックとして、記憶させる。ある範
囲のコンピュータを表すパラメータ型機械記述と、ある
特定のコンピュータ用の１組のスケジューリング・ヒュ
ーリスティックと、を設けることによって、本命令スケ
ジューラを、ある範囲のコンピュータに対し効率的なコ
ードを生成するように適合させることができる。その１
組のヒューリスティックを変更することによって、本ス
ケジューラを、その範囲内の特定のコンピュータに対し
うまく同調させることができる。

【００２５】本発明はまた、上記の如き命令スケジュー
ラを備えるコンピュータを包含している。このコンピュ
ータは、スーパースカラー／スーパーパイプライン式の
アーキテクチャを備えることができる。

【００２６】ある１つの好ましい実施例においては、そ
のコンピュータは、スーパースカラー／スーパーパイプ
ライン式のアーキテクチャを備えている。

【００２７】本発明の第２の面によれば、コンピュータ
における命令をスケジュールするスケジュール方法を提
供し、この方法は、以下のステップ、即ち、ａ）　　入
力コード・シーケンス中の複数の命令間のデータ依存性
と制御依存性とを表すプログラム依存性グラフを生成す
るステップと、 ｂ）　　前記プログラム依存性グラフを使用して、前記
入力コード・シーケンスからの命令をスケジュールして
、前記入力コード・シーケンスの命令を、適当な場合に
は基本ブロック境界を超えて再編成して、出力コード・
シーケンスを生成するステップと、から成っている。

【００２８】

【実施例】以下、この詳細な説明の末尾の表とそして図
面を参照しながら本発明のある特定の例について説明す
る。

【００２９】尚、その末尾に示した表１は、本発明の動
作を説明するためのプログラムの１例である。表２は、
表１のプログラムの１部に対応した注釈付きの機械命令
シーケンスである。表３は、第１のスケジューリング動
作後の表２の機械命令シーケンスを例示したものである
。表４は、それに代わるスケジューリング動作の後の表
２の機械命令シーケンスを例示したものである。

【００３０】図１は、本発明による命令スケジューラ１
０の全体図を与える概略ブロック図である。この命令ス
ケジューラは、その入力１１として命令シーケンスを取
りまた同シーケンス用の制御フローグラフ１２を取り、
そしてその出力として、スケジュールし直した命令シー
ケンス１８を提供するものである。命令スケジューラ１
０は、プログラム依存性グラフ（ＰＤＧ）１４を生成す
るためのプログラム依存性グラフ生成ロジック１３と、
順序付けロジック（又はスケジューリング・ロジック）
１５とより構成してある。その順序付けロジック１５は
、パラメータ型機械記述（ＰＭＤ）１６と１組のヒュー
リスティック１７と共に、ＰＤＧを使用して命令をスケ
ジュールし直すようにする。

【００３１】本発明のこの実施例の場合、プログラム依
存性グラフ生成ロジック１３と順序付けロジック１５と
は、コンパイラの一部、特にＩＢＭ　ＲＩＳＣシステム
／６０００コンピュータ用のコンパイラのＩＢＭ　ＸＬ
ファミリーの一つを構成している。本実施例の場合、入
力命令シーケンス１１及び出力命令シーケンス１８と制
御フローグラフ１２だけでなく、プログラム依存性グラ
フ１４、パラメータ型機械記述１６、及びヒューリステ
ィック組１７も、その上でコンパイラが走るＩＢＭ　Ｒ
ＩＳＣシステム／６０００コンピュータのワーキング記
憶内に保持している。このＩＢＭ　ＲＩＳＣシステム／
６０００コピュータ・ファミリーに関するより詳細な情
報については、ＩＢＭ研究開発ジャーナルのＶｏｌ．３
４，Ｎｏ．１（１９９０年１月）に公表の論文を参照さ
れたい。

【００３２】本命令スケジューリングは、コンパイラの
レジスタ割当てフェーズを呼び込む前あるいはその後で
適用するようにすることができる。尚、命令を再編成す
るためにより大きな柔軟性を残すようにするためには、
そのレジスタ割当てステップ前に本命令スケージュリン
グを実行することが有利である。

【００３３】以下、パラメータ型機械記述１６について
説明する。このパラメータ型機械記述は、典型的なＲＩ
ＳＣプロセッサ（メモリを参照する命令がロード命令と
ストア命令とだけであり、一方、全計算をレジスタ内で
行う）を有するスーパースカラー・マシン用の総称的モ
デルに基づいている。このスーパースカラー・マシンは
、ｍ個のタイプの機能性ユニットの集まりと見ることが
でき、この場合、このマシンは、各タイプのｎ１，ｎ２
，．．．．ｎｍのユニットをもっている。コード中の各
命令は、潜在的に、ある特定のタイプの２以上のユニッ
トによって実行可能である。

【００３４】各命令は、これのタイプの機能性ユニット
の１つにより実行されるのに、ある整数個のマシン・サ
イクルを必要とする。また、諸命令の実行にパイプライ
ン化の制約がかかり、これは、プログラム依存性グラフ
のデータ依存性エッジに割り当てるその整数個の遅れに
よってモデル化する。

【００３５】ここで、エッジ（Ｉ１，Ｉ２）がデータ依
存性エッジであるような、２つの命令Ｉ１及びＩ２の次
の例について考えることにする。もしｔ（ｔ＞１）がＩ
１の実行時間であり、ｄ（ｄ＞０）が（Ｉ１，Ｉ２）に
割り当てた遅れであり、またＩ１を時刻ｋでスタートさ
せるようにスケジュールした場合には、性能の目的のた
め、Ｉ２は、ｋ＋ｔ＋ｄよりも早くにはスタートさせな
いようにスケジュールすべきである。ここで注意された
いことは、もしＩ２を上記よりも早くスタートさせるよ
うに（コンパイラが）スケジュールした場合には、これ
は、プログラムの正しさを損うことにはならない、とい
うことである。何故ならば、本マシンは、実行時間のそ
の遅れを収拾するために、ハードウエア・インターロッ
クを装備していると想定しているからである。パイプラ
イン化制的に起因する遅れの一般的概念についての詳細
は、参考文献Ｒ３とＲ４に見ることができる。それらの
遅れは、アーキテクチャ毎に異なり得るものである、と
いうことに注意されたい。

【００３６】このパラメータ型機械記述は、その総称的
モデルのスーパースカラ・マシンを、ＩＢＭ　ＲＩＳＣ
システム／６０００マシンに適合するような構成にして
いる。そのＩＢＭ　ＲＩＳＣシステム／６０００プロセ
ッサは、次のようにモデル化する。 ・ｍ＝３　　−　　固定小数点、浮動小数点及び分岐タ
イプの３つのタイプの機能性ユニットが存在する。 ・ｎ１＝１，ｎ２＝１，ｎ３＝１　　─　　単一の固定
小数点ユニット、単一の浮動小数点ユニット、及び単一
の分岐ユニットがある。 ・命令の大部分は　　─　　１サイクルで実行するもの
であるが、乗算、除算等の多サイクル命令もある。 ・３つの主要なタイプの遅れがある。 ・ロード命令とこれの結果のレジスタを使用する命令と
の間の１サイクルの遅れ（遅延ロード）。 ・浮動小数点命令とこれの結果のレジスタを使用する命
令との間の１サイクルの遅延。 ・比較命令とこの比較結果を使用する分岐命令との間の
３サイクルの遅れ。より正確に述べると、通常、比較と
その各分岐命令との間のその３サイクルの遅れは、分岐
を行う時にのみ遭遇することになる。しかしながら、こ
こでは、簡単にするために、分岐を行うか否かに拘わら
ずそのような遅れがあると仮定する。

【００３７】以下、プログラム依存性グラフ生成ロジッ
ク１３の動作について、表１の小さなコード部分を例と
して説明する。表１に例示のプログラムは、Ｃ言語で書
いたものであり、ある配列の内の最大と最小とを計算す
るものである。本プログラムでは、表１内のマークした
ループに注目すると判るように、配列“ａ”の２つの要
素をこのループを各反復の度に取出す。次に“ａ”のこ
れらの要素は、その一方を他方と比較し（もしｕ＞ｖの
場合）、次いでそれらを、最大変数及び最小変数と比較
し、そして必要とあらばその最大と最小を更新する。表
１のループのＩＢＭ　ＲＩＳＣシステム／６０００疑似
コード（これは、ＸＬ−Ｃコンパイラが生成する実コー
ドに対応している）の抜粋については、表２に提示して
ある。

【００３８】本例の場合、説明し易くするために、ＩＢ
Ｍ　ＲＩＳＣシステム／６０００のある特徴を無力化さ
せる。その特徴とは、ある特別のカウンタ・レジスタ中
にループの反復変数を保持するというものである。反復
変数をそのレジスタ内に保持すれば、減分が可能になり
、単一の命令においてはそれがゼロかどうかテストする
ことにより、ループ制御命令のオーバーヘッドを効果的
に低減することができるようになる、というものである
。

【００３９】便宜上、表２のコード中の命令は、Ｉ１か
らＩ２０まで番号を付け、そして表１のプログラムの対
応する文で注釈を付してある。また、表２のコード中の
１０個の基本ブロックには、今後の説明のためにマーク
してある（Ｂ１−Ｂ１０）。

【００４０】表２のコード中のどの命令も、分岐は別と
して、固定小数点ユニットにおいて１サイクルを必要と
し、一方、それら分岐は、分岐ユニットにおいて１サイ
クルかかるものである。ＩＢＭ　ＲＩＳＣシステム／６
０００コンピュータの遅延形ロードの特徴のために、命
令Ｉ２と命令Ｉ３との間には、１サイクルの遅れがある
。また、各比較命令とそれに対応する分岐命令との間に
は、３サイクルの遅れがある。固定小数点ユニットと分
岐ユニットが並行してランするということを考慮に入れ
る、本コードは、最大変数及び最小変数の０回、１回又
は２回の更新（ＬＲ命令）が行われたかどうかに応じて
、それぞれ、２０個、２１個、２２個のサイクルで実行
されると見積もることができる。

【００４１】プログラム依存性グラフ１４は、本コード
中の諸命令の制御依存性とデータ依存性とを全て要約す
るのに便利な方法である。プログラム依存性グラフ生成
ロジック１３が生成するそのプログラム依存性グラフは
、制御依存性を表す制御依存性サブグラフとデータ依存
性を表すデータ依存性サブグラフより成っている。デー
タ依存性（これは、ある１つの命令があるデータ値を算
出しそしてその値をもう一つの命令が使うという基本思
想を担う）の概念は、ずっと以前にコンパイラにおいて
使用されていたが、制御依存性の概念は、ごく最近に導
入されたものである。以下の論文を参照されたい。 Ｒ１６．フェランテ（Ｊ．Ｆｅｒｒａｎｔｅ）、オッテ
ンステイン（Ｋ．Ｊ．Ｏｔｔｅｎｓｔｅｉｎ）、及びワ
レン（Ｊ．Ｄ．Ｗａｒｒｅｎ）の“プログラム依存性グ
ラフとその最適使用”，プログラミング言語とシステム
に関するＡＣＭ紀要（ｔｈｅ　ＡＣＭ　Ｔｒａｎｓａｃ
ｔｉｏｎｓ　ｏｎ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｌａｎｇ
ｕａｇｅｓ　ａｎｄ　Ｓｙｓｔｅｍｓ），Ｖｏｌ．　Ｎ
ｏ．３，１９８７年７月，３１９−３４９ページ

【００４２】プログラム依存性グラフ生成ロジック１３
が使用する制御フローグラフ１２の１例、特に表２のル
ープの制御フローグラフを、図２に示す。都合の良いよ
うに、この制御フローグラフは、その上をコンパイラが
ランするコンピュータのメモリ内に、あるデータ構造の
形態で記憶させてあり、そのデータ構造は、そのグラフ
内の諸ノードに対応した一組のリンクしたレコードを有
しており、そして諸ノード間のエッジはレコード間のポ
インタにより表している。この制御フローグラフは、コ
ード・シーケンス中の基本ブロックとループを識別する
ため、また各ブロック内へのエントリ時に種々のプロセ
ッサ・レジスタの状態をチェックするための在来のコン
パイラ・ロジックによって、生成することができる。

【００４３】図２の制御フローグラフには、便宜上、独
特のＥＮＴＲＹノードとＥＸＩＴノードとを増補してあ
る。以下では、この制御フローグラフ内には、ＥＮＴＲ
Ｙノードは１つであるが、ＥＸＩＴノードは多分幾つか
ある、と仮定する。本プログラム中の強く結合した領域
（これは、本説明中で使用する用語においては、ループ
に相当している）については、単一エントリの制御フロ
ーグラフのその仮定は、制御フローグラフが変形可能で
あるという仮定に対応している。

【００４４】一つの制御フローグラフ中のノードＸから
ノードＹへのエッジの意味は、プログラムの制御が基本
ブロックＸから基本ブロックＹへ流れるということであ
る。それらエッジ（即ち、データ構造中のポインタ）に
は、一つの基本ブロックからもう一つのブロックへ至る
プログラムの流れを制御する条件によって注釈をつける
のが普通である。しかしながら、図２のグラフからは、
何れの基本ブロックが何れの条件の下で実行されるのか
は、明らかではない。

【００４５】次に、制御依存性サブグラフの生成につい
て、以下に図３を参照して説明する。この図３は、表２
のループについての制御依存性サブグラフを表している
。都合の良いように、プログラム依存性グラフ生成ロジ
ック１３は、あるデータ構造の形態で制御依存性サブグ
ラフを生成するが、そのデータ構造は、グラフ内の諸ノ
ードに対応する一組のリンクしたレコードを有しており
、そして諸ノード間のエッジは、レコード間のポインタ
により表している。このグラフの各ノードは、図２の制
御フローグラフと同様に、プログラムの基本ブロックに
相当したものである。しかしながら、ノードＸからノー
ドＹへのエッジは、基本ブロックＹが、基本ブロックＸ
の終わりのところで計算される条件の下で実行される、
ということを意味している（基本ブロックＸの終わりで
、それらエッジには、同じく、対応する条件で注釈を付
してある）。図３では、実線のエッジは制御依存性エッ
ジを示しており、他方、点線のエッジについては、以下
に説明する。例えば、図３において、Ｂ１から出る幾つ
かのエッジは、Ｂ１の終りでの条件が真（Ｔ）であると
評価された時にＢ２とＢ４が実行されることを示し、他
方、Ｂ６とＢ８は、その同じ条件が偽（Ｆ）であった場
合に実行される、ということを示している。

【００４６】大域スケジューリングという目的のため、
プログラム依存性グラフ生成ロジックは、順方向制御依
存性グラフのみを生成する。この制御依存性サブグラフ
を生成するためには、プログラム依存性グラフ生成ロジ
ックは、まず、全ての事後支配関係を識別する事後支配
木を生成し、そしてこれから順方向制御依存性グラフを
生成する。その制御フローグラフの後方エッジから生ず
る、もしくはその後方エッジを伝播する制御依存性につ
いては、生成しない。かくして、図３の制御依存性サブ
グラフは、順方向制御依存性グラフとなる。尚、この順
方向制御依存性グラフは、非循環性であることに注意さ
れたい。

【００４７】図２と図３のグラフを比較すると判るよう
に、（Ｂ８からＢ１０へのエッジのように）制御フロー
グラフ中に現れたある種のエッジは、制御依存性サブグ
ラフ中には存在していないが、その一方で、制御依存性
サブグラフ内には、（Ｂ１からＢ４へ至るエッジのよう
に）制御フローグラフ内に初めから存在しないエッジが
ある。本プログラム依存性グラフのこの制御依存性サブ
グラフから判るように、同じ組の制御依存性を有する基
本ブロック（例えば図３のＢ１とＢ１０，又はＢ２とＢ
４，又はＢ６とＢ８）は、現存するデータ依存性のとこ
ろまで並行して実施することができる。このことは、そ
のような基本ブロックの命令を一緒にスケジュール可能
であることを意味している。

【００４８】次に、本スケジューラを理解し易くするた
めに、幾つかの定義（Ｄ）を導入する。但し、ＸとＹは
、制御フローグラフの２つのノードである。 ・Ｄ１　　−　　Ｘが、エントリからＹへ至る全てのパ
ス上に現われる場合、その場合のみ、Ｘは、Ｙを支配す
る。 ・Ｄ２　　−　　Ｘが、Ｙから出口へ至る全てのパス上
に現われる場合、その場合のみ、Ｘは、Ｙを事後支配す
る。 ・Ｄ３　　−　　ＸがＹを支配しかつＹがＸを事後支配
する場合のみ、ＸとＹは等価である。 ・Ｄ４　　−　　ある命令をＹからＸへ移動させること
は、ＸがＹに等価でかつその場合にのみ、“有効”であ
ると称する。 ・Ｄ５　　−　　ある命令をＹからＸへ移動させること
は、もしＹがＸを事後支配しない場合には、“推測的”
と称する（即ち、そのような命令は、その結果が本プロ
グラムの起こり得る実行の内の若干のみにおいて使用す
ることができるものであるから、“推測的”と言う。）
。 ・Ｄ６　　−　　ある命令をＹからＸへ移動させること
は、もしＸがＹを支配しない場合には、複製を要すると
称する。

【００４９】順序付けロジック１５は、“有効”と“推
測的”の双方のスケジューリングに対して制御依存性サ
ブグラフを使用する。等価ノードを発見するためには、
その順序付けロジックは、等しく制御依存的なノード（
これらは、同じ組のノードから同じ条件で垂れ下がる）
についての制御依存性サブグラフ・データ構造を探索す
る。例えば、図３において、Ｂ１とＢ１０は、それらが
何れのノードにも依存していないため、等価である。ま
た、Ｂ２とＢ４は共に、真の条件の下でＢ１に依存する
から、等価である。この図３において、等価なノードは
、点線のエッジによりマークしてあり、そしてそれらエ
ッジの方向は、ノード間の支配関係を示している。例え
ば、等価のノードＢ１とＢ１０の場合、Ｂ１は、Ｂ１０
を支配している。

【００５０】この制御依存性サブグラフは、命令を一つ
のブロックから別のブロックへ移動させるための“推測
度”を与えている。ある“推測的”命令をスケジュール
する際、一つもしくはそれ以上の分岐の結果には、常に
賭けが存在し、そして、それらの分岐の方向が正確に推
測した場合のみ、移動させた命令は、実際に有益なもの
となる。しかしながら、その推測が誤っていた場合には
、何も失われず、従って何も得ることはできない。この
制御依存性サブグラフは、どの対のノードに対しても、
（“推測的”スケジューリングの場合）賭けを行う多く
の分岐を提供している。例えば、命令をＢ８からＢ１へ
移動させる場合、単一の分岐の結果について賭けを行う
が、その理由は、図３のＢ８からＢ１へ移動させる場合
には、一つのエッジのみしかクロスしていないからであ
る。このことは、図２の制御フローグラフからは明らか
ではない点に注意されたい。Ｂ５からＢ１へ移動させる
場合には、図３の２つのエッジがクロスしているため、
２つの分岐の結果に対し賭けが存在する。

【００５１】上記のことから、更に一つの定義を導き出
すことができる。 ・Ｄ７　　−　　ＹからＸへ命令を移動させることは、
もしＸからＹへ至る長さＮのパスが制御依存性サブグラ
フ中に存在する場合、Ｎ−分岐“推測的”であると称す
る。 この定義Ｄ７が与えられると、“有効”スケジューリン
グは、０−分岐“推測的”と言うことができる。

【００５２】プログラム依存性グラフ生成ロジックは、
基本ブロック・レベルで制御依存性を計算する一方、命
令毎にデータ依存性を計算する。ブロック間データ及び
ブロック間データ依存性の双方について、計算する。デ
ータ依存性は、レジスタの使用によって、又はメモリ・
ロケーションをアクセスすることによって生ずることが
ある本コード中の“Ｉｘ”と“Ｉｙ”の２つの命令につ
いて、ＩｘからＩｙへ至るデータ依存性エッジは、以下
のケースの一つの場合に、データ依存性サブグラフ内へ
挿入する。 ・Ｉｘにおいて定義したレジスタを、Ｉｙにおいて使用
する（フロー依存性）； ・Ｉｘにおいて使用したレジスを、Ｉｙにおいて定義す
る（反依存性）； ・Ｉｘにおいて定義したレジスタを、Ｉｙにおいて定義
する（出力依存性）； ・ａとｂは共に、メモリに触れる命令（ロード、ストア
、サブルーチンに対する呼出し）であり、それらが異な
るロケーションをアドレス指定することについて証明す
ることは、不可能である。

【００５３】一個のレジスタの定義からその使用に導く
データ依存性エッジは、基礎にあるマシンを特徴付ける
ような（潜在的に非零の）遅れを担うものである。残り
のデータ依存性エッジは、ゼロ遅れを担うものである。

【００５４】データ依存性の例として、表２内の基本ブ
ロックＢ１のデータ依存性について、その表２からの命
令をその番号で参照することにより考察する。Ｉ１はｒ
３１を使用し、Ｉ２はｒ３１の新たな値を規定するから
、Ｉ１からＩ２へは、反依存性がある。Ｉ３は、それぞ
れＩ１とＩ２で規定されたｒ１２とｒ０を使用するから
、Ｉ１とＩ２の双方からＩ３へ至るフローデータ依存性
がある。エッジ（Ｉ１，Ｉ３）と（Ｉ２，Ｉ３）は、Ｉ
１とＩ２が共にロード命令（遅延形ロード）であるから
、１サイクルの遅れを担っている。また、Ｉ３は、Ｉ４
が使用するｃｒ７をセットするから、Ｉ３からＩ４には
データ依存性エッジがある。このエッジは、Ｉ３が比較
命令でありまたＩ４がそれに対応する分岐命令であるか
ら、３サイクルの遅れをもっている。

【００５５】ここで気付くべき重要なことは、計算した
制御依存性とデータ依存性とは、共に非循環性であるか
ら、その結果として生ずるプログラム依存性グラフも又
非循環性である、ということである。このことは、順序
付けロジックによる命令のスケジュールをし易くする。

【００５６】この順序付けロジックは、プログラム中の
命令をループ毎にスケジュールする。最も内側のループ
から始まって外側のループへとスケジュールするように
する。このスケジューリング・プロセスを全般的に支配
する幾つかの原則がある。 ・命令は、決してループから外へ移動させたりあるいは
ループ内へ移動させたりしない。 ・命令は、全て上部方向へ移動させる。即ち、制御フロ
ーエッジに逆らって移動させる。 ・プログラム中の諸分岐の元の順序は、保持する。

【００５７】図４は、順序付けロジックによる命令のス
ケジューリングを示すフロー図である。そのスケジュー
リングは、基本ブロックを一時に１つずつ処理すること
によって行う。それら基本ブロックには、位相幾何学的
順序で出会うことになる。即ち、もしその制御フローグ
ラフ内にＸからＹへ至るパスがある場合には、Ｘは、Ｙ
の前に処理する。

【００５８】もしＸが現在スケジュール中の基本ブロッ
クである場合には、順序付けロジックは、Ｘに対する１
組Ｃ（Ｘ）の候補ブロックを識別する。即ち、命令をＸ
に寄与させることの可能な基本ブロックのリストを識別
する。何れのブロックが候補ブロックであるかの判定は
、適用すべきスケジューリング原則に従って、制御依存
性グラフから行う。本実施例においては、２つのレベル
のスケジューリングがある。 １．有効命令のみ：　　この場合、Ｃ（Ｘ）は、Ｘと等
価でかつＸによって支配される全ブロックを包含する。 ２．１分岐“推測的”：　　Ｃ（Ｘ）は、以下のブロッ
クを含む。 ａ．Ｘと等価でかつＸによって支配される全ブロック。 ｂ．制御依存性サブグラフ中のＸの直後のもの全部。 ｃ．制御依存性サブグラフ中の“ａ”ブロックの直後の
もの全部。

【００５９】現行ブロックについて１組の候補ブロック
を（２０で）初期化した後、本順序付けロジックは、そ
の組の候補ブロックをスケジューリングのために（２１
で）計算する。スケジューリング実行の準備が完了して
いる命令は、レディ・リスト中に保持する。ある１つの
命令Ｉは、もしこれが以下のカテゴリーの内の一つに属
する場合には、ブロックＸにおけるスケジューリング用
候補となる。 ・Ｉは、初めにＸに属していた。 ・Ｉは、Ｘの候補ブロック集合中のブロックの一つに属
し、かつ １．Ｉは、“有効”であり、しかも基本ブロック境界を
超えて移動することが許される。（サブルーチンに対す
る呼出しの如き、決して基本ブロック境界を超えて移動
させない命令がある。） ２．Ｉは、“推測的”であり、しかもＩは、推測的にス
ケジュールすることが許されている。

【００６０】全ての命令が、推測的にスケジュールする
ことが許されているわけではない。例えば、“推測的”
ロードは、存在しない仮想メモリ・ロケーションに対す
るアクセスに起因する例外を引き起こすことがある。順
序付けロジックは、何れの命令が推測的にスケジュール
可能であるか、またこの場合どのような結果が期待され
るかについて判定する。

【００６１】その後、順序付けロジック１５は、進行し
て、レディ・リストから命令を所与の命令サイクルに対
しスケジュールする（２２）。このスケジューリング・
プロセスの間、順序付けロジックは、そのレディ命令リ
スト（即ち、データ依存性と制御依存性とが満たされた
“有効”候補命令と、データ依存性のみが満たされてい
る“推測的”候補命令）を更新する。サイクル毎に、マ
シン・アーキテクチャが必要とする数の多くの命令を、
次にスケジュールするべきレディ・リストからピックア
ップする。もしレディ命令が多過ぎる場合には、それら
の内の“最良のもの”を、その優先順位に基づいて順序
付けロジックが選択する。一旦、ある命令をスケジュー
ルするべくピックアップすると、この命令を、コード中
の適当な位置へ移動させ、そしてそれに続く命令に対す
るそれのデータ依存性と制御依存性とが満たされたもの
としてマークし、これにより、潜在的に新たな命令がレ
ディ状態となれるようにする。このプロセスは、ブロッ
クＸ内の全命令をスケジュールするまで、繰返す（２３
）。その全命令をスケジュールした後、次のブロックの
スケジュールを行って、本ループ内の全ブロックをスケ
ジュールを行うまで続ける（２５）。

【００６２】ステップ２２で順序付けロジックがスケジ
ュールするべき命令を判定するための命令の相対的優先
順位は、１組のヒューリスティックに従って導出する。 例えば、その命令が属する基本ブロックのデータ依存性
サブグラフの根に至るパスの遅れの最大数は、ある命令
の優先順位を決めるためのヒューリスティックとして選
択する。しかしながら、他のヒューリスティックも、そ
の代わりとして、あるいはそれに加えて使用することが
できる。

【００６３】表３は、どのように大域スケジューリング
が働くのかについての１例を示すものである。詳しくは
、この表３は、いわゆる有効命令のみが基本ブロック境
界を超えて移動することが許された状態で、大域スケジ
ューリングを表２の命令シーケンスに適用した結果を示
している。表３に示したそのコードは、ループの１反復
当たりほぼ１３サイクルで実行できる。

【００６４】表４は、大域スケジューリングを表２の命
令ーケンスに適用した結果を示しており、これでは、推
測的スケジューリングも行っている（即ち、推測的命令
も基本ブロック境界を超えて移動することが許されてい
る）。この表３に示すコードは、ループの各反復当たり
ほぼ１２サイクルで実行できる。

【００６５】以上に、囲んだループの範囲内で命令を基
本ブロック境界を十分超えて移動させことが可能な大域
命令スケジューリング用のスケジューラについて説明し
た。このスケジューラは、フェランテ外が提案したプロ
グラム依存性グラフ（参考文献Ｒ１４を参照）を用いて
、コンパイラにおいて使用するようにし、これによって
、ベクトル化及びマルチプロセッサ用のコードの生成と
いう目的のための並行性を露呈させるようにしている。 本スケジューラは、スーパースカラー・マシンのファミ
リのパラメータ型記述と組み合わせてそのプログラム依
存性グラフを使用し、これにより、コンパイラを最適化
することによって大域命令スケジューリングする上で強
力な骨組みを提供する。

【００６６】本スケジューラは、一組のヒューリスティ
ックを使用して、プログラム依存性グラフ中の１つの命
令の相対的優先順位を提供するようにする。用いるヒュ
ーリスティック・ルールの組は、このスケジューラを使
用するよう意図するマシンの特定のアーキテクチャに依
存するものである。ヒューリスティック・ルールの種類
の例は、クリティカルなパス情報に関するものである。 本スケジューラは、命令をその優先順位に応じて発し、
これにより、上記の如くマシン資源を十分活用しようと
試みる。上記ヒューリスティック・ルールの組を変更す
ることによって、本スケジューラを、このスケジューラ
の残りの部分を変更せずに、選択されたマシン・アーキ
テクチャに対しうまく同調させる。

【００６７】スケジューリング・プロセス中、命令を、
現存の制御依存性及びデータ依存性まで１つの基本ブロ
ックから別のものへと移動させることが可能である。こ
の骨組みにおいて、“有効”命令が可能になる。その命
令とは、プログラムの実行をスケジュールする間少なく
とも１回その結果が使用されるような命令のみを意味す
る。オプションとして、“推測的”命令を、所望の制約
内で移動させることもできる。命令スケジューリングに
対するそのより野心的なアプローチにおいては、そのよ
うな“推測的”命令は、ＸからＹに対して存在するどん
な制御依存性にも拘わらず、基本ブロックＸから基本ブ
ロックＹへ移動させる。もしある“推測的”命令を、さ
もなければ遊んでいる機能性ユニットによって実行され
るような位置に移動させる場合、そのような変形だけが
、プログラムの走行時間を改善でき、従って有益である
と考えられる。

【００６８】 　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　表　　１ 　　　／＊　ｆｉｎｄ　ｔｈｅ　ｌａｒｇｅｓｔ　ａｎ
ｄ　ｔｈｅ　ｓｍａｌｌｅｓｔ　ｎｕｍｂｅｒ　ｉｎ　
ａ　ｇｉｖｅｎ　ａｒｒａｙ　＊／　　　ｍａｉｎ（）
　｛ 　　　ｓｔａｔｉｃ　ａ□　＝　｛ 　　　５，５，５，２，５，５，５，５，５，５，５，
５，５，５，５，５，５，５，　　　５，５，５，５，
５，５，５，５，５，５，５，５，５，５，５，５，９
，　　　｝； 　　　ｉｎｔ　ｉ，ｕ，ｖ，ｍｉｎ，ｍａｘ，　ｎ＝ｓ
ｉｚｅｏｆ（ａ）／ｓｉｚｅｏｆ（ａ［０］）；　　　
ｍｉｎ＝ａ［０］；　ｍａｘ＝ｍｉｎ；　ｉ＝１；　　
　／＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊　　ＬＯＯ
Ｐ　ＳＴＡＲＴＳ　　＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊／　　　Ｗｈｉ
ｌｅ　（ｉ　＜　ｎ）　｛　　　　　　　ｕ＝ａ［ｉ］
；　ｖ＝ａ［ｉ＋１］；　　　　　　　ｉｆ　（ｕ＞ｖ
）　｛ 　　　　　　　　　　　　　ｉｆ　（ｕ＞ｍａｘ）　ｍ
ａｘ＝ｕ；　　　　　　　　　　　　　ｉｆ　（ｖ＜ｍ
ｉｎ）　ｍｉｎ＝ｖ；　　　　　　　｝ 　　　　　　　ｅｌｓｅ　　｛ 　　　　　　　　　　　　　ｉｆ　（ｖ＞ｍａｘ）　ｍ
ａｘ＝ｖ；　　　　　　　　　　　　　ｉｆ　（ｕ＜ｍ
ｉｎ）　ｍｉｎ＝ｕ；　　　　　　　｝ 　　　　　　　ｉ＝　ｉ＋２； 　　　｝ 　　　／＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊　　Ｌ
ＯＯＰ　ＥＮＤＳ　　＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊／　　　ｐ
ｒｉｎｔｆ（”ｍｉｎ＝％ｄ　ｍａｘ＝％ｄ＼ｎ”，ｍ
ｉｎ，ｍａｘ）；　　　｝

【００６９】 　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　表　　２ 　　　　．．．　　ｍｏｒｅ　ｉｎｓｔｒｕｃｔｉｏｎ
ｓ　ｈｅｒｅ　．．．　　　＊＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊　　ＬＯＯＰ　ＳＴＡＲＴＳ　　＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊　
　　　　　ＣＬ．Ｏ： 　　　（Ｉ１）　　　　Ｌ　　　　　　　　　ｒ１２＝
ａ（ｒ３１，４）　　　　　　　　　　　　　　　　　
ｌｏａｄ　ｕ　　　（Ｉ２）　　　　ＬＵ　　　　　　
　　ｒ０，ｒ３１＝ａ（ｒ３１，８）　　　　　　　　
　　　　　　ｌｏａｄ　ｖ　　　（Ｉ３）　　　　Ｃ　
　　　　　　　　ｃｒ７＝ｒ１２，ｒ０　　　　　　　
　　　　　　　　　　　　ｕ　＞　ｖ　　　（Ｉ４）　
　　　ＢＦ　　　　　　　　ＣＬ．４，ｃｒ７，０×２
／ｇｔ　　　−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−　　ＥＮＤ　ＢＬ１　　　（
Ｉ５）　　　　Ｃ　　　　　　　　　ｃｒ６＝ｒ１２，
ｒ３０　　　　　　　　　　　　　　　　　　ｕ　＞　
ｍａｘ　　　（Ｉ６）　　　　ＢＦ　　　　　　　　Ｃ
Ｌ．６，ｃｒ６，０×２ｇｔ　　　−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−　　Ｅ
ＮＤ　ＢＬ２　　　（Ｉ７）　　　　ＬＲ　　　　　　
　　ｒ３０＝ｒ１２　　　　　　　　　　　　　　　　
　　　　　　ｍａｘ　＝　ｕ　　　−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−　　Ｅ
ＮＤ　ＢＬ３　　　　　　　ＣＬ．６： 　　　（Ｉ８）　　　　Ｃ　　　　　　　　　ｃｒ７＝
ｒ０，ｒ２８　　　　　　　　　　　　　　　　　　　
ｖ　＜　ｍｉｎ　　　（Ｉ９）　　　　ＢＦ　　　　　
　　　ＣＬ．９，ｃｒ７，０×１／１ｔ　　　−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−　　ＥＮＤ　ＢＬ４　　　（Ｉ１０）　　　ＬＲ　
　　　　　　　ｒ２８＝ｒ０　　　　　　　　　　　　
　　　　　　　　　　　ｍｉｎ　＝　ｖ　　　（Ｉ１１
）　　　Ｂ　　　　　　　　　ＣＬ．９　　　　−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−　　ＥＮＤ　ＢＬ５　　　　　　　ＣＬ．４： 　　　（Ｉ１２）　　　Ｃ　　　　　　　　　ｃｒ６＝
ｒ０，ｒ３０　　　　　　　　　　　　　　　　　　　
ｖ　＞　ｍａｘ　　　（Ｉ１３）　　　ＢＦ　　　　　
　　　ＣＬ．１１，ｃｒ６，０×２／ｇｔ　　　−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−　　ＥＮＤ　ＢＬ６　　　（Ｉ１４）　　　ＬＲ
　　　　　　　　ｒ３０＝ｒ０　　　　　　　　　　　
　　　　　　　　　　　　ｍａｘ　＝　ｖ　　　−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−　　ＥＮＤ　ＢＬ７　　　　　　　ＣＬ．１１： 　　　（Ｉ１５）　　　Ｃ　　　　　　　　　ｃｒ７＝
ｒ１２，ｒ２８　　　　　　　　　　　　　　　　　　
ｕ　＜　ｍｉｎ　　　（Ｉ１６）　　　ＢＦ　　　　　
　　　ＣＬ．９，ｃｒ７，０×１／１ｔ　　　−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−　　ＥＮＤ　ＢＬ８　　　（Ｉ１７）　　　ＬＲ　
　　　　　　　ｒ２８＝ｒ１２　　　　　　　　　　　
　　　　　　　　　　　ｍｉｎ　＝　ｕ　　　−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−　　ＥＮＤ　ＢＬ９　　　　　　　ＣＬ．９： 　　　（Ｉ１８）　　　ＡＩ　　　　　　　　ｒ２９＝
ｒ２９，２　　　　　　　　　　　　　　　　　　　　
ｉ　＝　ｉ＋２　　　（Ｉ１９）　　　Ｃ　　　　　　
　　　ｃｒ４＝ｒ２９，１７１　　　　　　　　　　　
　　　　　　　ｉ　＜　ｎ　　　（Ｉ２０）　　　ＢＴ
　　　　　　　　ＣＬ．０，ｃｒ４，０×１／１ｔ　　
　−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−　　ＥＮＤ　ＢＬ１０　　　＊＊＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊　ＬＯＯＰ　ＥＮＤＳ　
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊＊　　　　．．．　　ｍｏｒｅ　ｉｎｓ
ｔｒｕｃｔｉｏｎｓ　ｈｅｒｅ　．．．

【００７０】 　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　表　　３ 　　　　．．．　　ｍｏｒｅ　ｉｎｓｔｒｕｃｔｉｏｎ
ｓ　ｈｅｒｅ　．．．　　　＊＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊　　ＬＯＯＰ　ＳＴＡＲＴＳ　　＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊　
　　　　　ＣＬ．Ｏ： 　　　（Ｉ１）　　　　Ｌ　　　　　　　　　ｒ１２＝
ａ（ｒ３１，４）　　　　　　　　　　　　　　　　　
　　　（Ｉ２）　　　　ＬＵ　　　　　　　　ｒ０，ｒ
３１＝ａ（ｒ３１，８）　　　　　　　　　　　　　　
　　　（Ｉ１８）　　　ＡＩ　　　　　　　　ｒ２９＝
ｒ２９，２　　　（Ｉ３）　　　　Ｃ　　　　　　　　
　ｃｒ７＝ｒ１２，ｒ０　　　　　　　　　　　　　　
　　　　　　　　（Ｉ１９）　　　Ｃ　　　　　　　　
　ｃｒ４＝ｒ２９，１７１　　　（Ｉ４）　　　　ＢＦ
　　　　　　　　ＣＬ．４，ｃｒ７，０×２／ｇｔ　　
　（Ｉ５）　　　　Ｃ　　　　　　　　　ｃｒ６＝ｒ１
２，ｒ３０　　　　　　　　　　　　　　　　　　　　
　（Ｉ８）　　　　Ｃ　　　　　　　　　ｃｒ７＝ｒ０
，ｒ２８　　　（Ｉ６）　　　　ＢＦ　　　　　　　　
ＣＬ．６，ｃｒ６，０×２ｇｔ　　　（Ｉ７）　　　　
ＬＲ　　　　　　　　ｒ３０＝ｒ１２　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　ＣＬ．６
： 　　　（Ｉ９）　　　　ＢＦ　　　　　　　　ＣＬ．９
，ｃｒ７，０×１／１ｔ　　　（Ｉ１０）　　　ＬＲ　
　　　　　　　ｒ２８＝ｒ０　　　　　　　　　　　　
　　　　　　　　　　　　　　（Ｉ１１）　　　Ｂ　　
　　　　　　　ＣＬ．９　　　　　　　　ＣＬ．４： 　　　（Ｉ１２）　　　Ｃ　　　　　　　　　ｃｒ６＝
ｒ０，ｒ３０　　　　　　　　　　　　　　　　　　　
　　　（Ｉ１５）　　　Ｃ　　　　　　　　　ｃｒ７＝
ｒ１２，ｒ２８　　　（Ｉ１３）　　　ＢＦ　　　　　
　　　ＣＬ．１１，ｃｒ６，０×２／ｇｔ　　　（Ｉ１
４）　　　ＬＲ　　　　　　　　ｒ３０＝ｒ０　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　ＣＬ．１１： 　　　（Ｉ１６）　　　ＢＦ　　　　　　　　ＣＬ．９
，ｃｒ７，０×１／１ｔ　　　（Ｉ１７）　　　ＬＲ　
　　　　　　　ｒ２８＝ｒ１２　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　ＣＬ．９： 　　　（Ｉ２０）　　　ＢＴ　　　　　　　　ＣＬ．０
，ｃｒ４，０×１／１ｔ　　　＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊＊　ＬＯＯＰ　ＥＮＤＳ　＊＊＊＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
＊＊　　　　．．．　　ｍｏｒｅ　ｉｎｓｔｒｕｃｔｉ
ｏｎｓ　ｈｅｒｅ　．．．

【００７１】 　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　表　　４ 　　　　．．．　　ｍｏｒｅ　ｉｎｓｔｒｕｃｔｉｏｎ
ｓ　ｈｅｒｅ　．．．　　　＊＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊　　ＬＯＯＰ　ＳＴＡＲＴＳ　　＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊　
　　　　　ＣＬ．Ｏ： 　　　（Ｉ１）　　　　Ｌ　　　　　　　　　ｒ１２＝
ａ（ｒ３１，４）　　　　　　　　　　　　　　　　　
　　　（Ｉ２）　　　　ＬＵ　　　　　　　　ｒ０，ｒ
３１＝ａ（ｒ３１，８）　　　　　　　　　　　　　　
　　　（Ｉ１８）　　　ＡＩ　　　　　　　　ｒ２９＝
ｒ２９，２　　　（Ｉ３）　　　　Ｃ　　　　　　　　
　ｃｒ７＝ｒ１２，ｒ０　　　　　　　　　　　　　　
　　　　　　　　（Ｉ１９）　　　Ｃ　　　　　　　　
　ｃｒ４＝ｒ２９，１７１　　　（Ｉ５）　　　　Ｃ　
　　　　　　　　ｃｒ６＝ｒ１２，ｒ３０　　　（Ｉ１
２）　　　Ｃ　　　　　　　　　ｃｒ５＝ｒ０，ｒ３０
　　　（Ｉ４）　　　　ＢＦ　　　　　　　　ＣＬ．４
，ｃｒ７，０×２／ｇｔ　　　（Ｉ８）　　　　Ｃ　　
　　　　　　　ｃｒ７＝ｒ０，ｒ２８　　　（Ｉ６）　
　　　ＢＦ　　　　　　　　ＣＬ．６，ｃｒ６，０×２
ｇｔ　　　（Ｉ７）　　　　ＬＲ　　　　　　　　ｒ３
０＝ｒ１２　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　ＣＬ．６： 　　　（Ｉ９）　　　　ＢＦ　　　　　　　　ＣＬ．９
，ｃｒ７，０×１／１ｔ　　　（Ｉ１０）　　　ＬＲ　
　　　　　　　ｒ２８＝ｒ０　　　　　　　　　　　　
　　　　　　　　　　　　　　（Ｉ１１）　　　Ｂ　　
　　　　　　　ＣＬ．９　　　　　　　　ＣＬ．４： 　　　（Ｉ１５）　　　Ｃ　　　　　　　　　ｃｒ７＝
ｒ１２，ｒ２８　　　（Ｉ１３）　　　ＢＦ　　　　　
　　　ＣＬ．１１，ｃｒ５，０×２／ｇｔ　　　（Ｉ１
４）　　　ＬＲ　　　　　　　　ｒ３０＝ｒ０　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　ＣＬ．１１： 　　　（Ｉ１６）　　　ＢＦ　　　　　　　　ＣＬ．９
，ｃｒ７，０×１／１ｔ　　　（Ｉ１７）　　　ＬＲ　
　　　　　　　ｒ２８＝ｒ１２　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　ＣＬ．９： 　　　（Ｉ２０）　　　ＢＴ　　　　　　　　ＣＬ．０
，ｃｒ４，０×１／１ｔ　　　＊＊＊＊＊＊＊＊＊＊＊
＊＊＊＊＊＊＊＊　ＬＯＯＰ　ＥＮＤＳ　＊＊＊＊＊＊
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
＊＊　　　　．．．　　ｍｏｒｅ　ｉｎｓｔｒｕｃｔｉ
ｏｎｓ　ｈｅｒｅ　．．．

【図面の簡単な説明】

【図１】本発明による命令スケジューラの概観を与える
概要ブロック図である。

【図２】表２の機械命令シーケンスの制御フローグラフ
である。

【図３】表２の命令シーケンスのプログラム依存性グラ
フの制御依存性サブグラフである。

【図４】図１の命令スケジューラ内の命令順序付けロジ
ックのフロー図である。

【符号の説明】

１１：入力命令シーケンス １２：ＰＣＦ １３：ＰＤＧ生成ロジック １４：ＰＤＧ １５：順序付けロジック １６：ＰＭＤ １７：ヒューリスティック １８：出力命令シーケンス

Claims (20)

【特許請求の範囲】
1. 【請求項１】　　コンピュータ用の命令スケジューラで
   あって、入力コード・シーケンス中の複数の命令の間の
   データ依存性と制御依存性を表すプログラム依存性グラ
   フを生成するプログラム依存性グラフ生成ロジックと、
   前記プログラム依存性グラフに応答して、前記入力コー
   ド・シーケンスの前記命令を、適当な場合に基本ブロッ
   ク境界を超えて再配列して、出力コード・シーケンスを
   生成する順序付けロジックと、から成る命令スケジュー
   ラ。
2. 【請求項２】　　前記プログラム依存性グラフ生成ロジ
   ックが、制御依存性サブグラフとデータ依存性サブグラ
   フとから成るプログラム依存性グラフを生成する、請求
   項１の命令スケジューラ。
3. 【請求項３】　　前記順序付けロジックが、前記制御依
   存性サブグラフを用いて、前記入力コード・シーケンス
   中の命令の基本ブロックをブロック毎にスケジュールし
   、また、前記順序付けロジックが、現在スケジュールし
   ている現行のブロックについて、前記現行ブロックに対
   し命令を寄与させることが可能な候補ブロックのリスト
   を決める、請求項２の命令スケジューラ。
4. 【請求項４】　　前記候補ブロック・リストが、前記制
   御依存性サブグラフにおいて、前記現行ブロックに等価
   でありかつ前記現行のブロックにより支配されると識別
   した全ブロックを含む、請求項３の命令スケジューラ。
5. 【請求項５】　　前記候補ブロック・リストが更に、前
   記制御依存性サブグラフにおいて、前記現行ブロックの
   直後のもの、又は前記現行ブロックに等価のブロックで
   あって前記現行ブロックにより支配されるそのブロック
   の直後のもの、として識別した全ブロックを含む、請求
   項４の命令スケジューラ。
6. 【請求項６】　　前記順序付けロジックが更に、前記デ
   ータ依存性グラフを用いて、前記候補ブロックの集合の
   内から１組の候補命令を判定する、請求項３ないし５の
   いずれかの命令スケジューラ。
7. 【請求項７】　　前記候補命令のリストは、命令がブロ
   ック境界を超えて移動させることができないタイプでは
   なくかつ／又はその命令が推測的にスケジュールできな
   いタイプではない限り、実行が推測的な命令を含む、前
   記現行ブロック又は前記候補ブロック集合の内の１つの
   ブロックに属する全命令を含む、請求項６の命令スケジ
   ューラ。
8. 【請求項８】　　前記順序付けロジックが、機械記述に
   従って、前記候補命令リストから次にスケジュールする
   べき一つ又はそれ以上の命令を判定する、請求項６又は
   ７の命令スケジューラ。
9. 【請求項９】　　ある範囲のコンピュータを表すパラメ
   ータ型機械記述と、特定のコンピュータ用の１組のスケ
   ジューリング・ヒューリスティックと、から成る機械記
   述を記憶する手段を備える、請求項１〜８のいずれかの
   命令スケジューラ。
10. 【請求項１０】　　請求項１〜９のいずれかに記載の命
    令スケジューラを備えるコンピュータ。
11. 【請求項１１】　　前記コンピュータが、スーパースカ
    ラー／スーパーパイプライン式のアーキテクチャを備え
    る、請求項１０のコンピュータ。
12. 【請求項１２】　　コンピュータにおける命令をスケジ
    ュールする命令スケジュール方法であって、ａ）　　入
    力コード・シーケンス中の複数の命令の間のデータ依存
    性と制御依存性を表すプログラム依存性グラフを生成す
    るステップと、及び ｂ）　　前記プログラム依存性グラフを用いて前記入力
    コード・シーケスからの命令をスケジュールして、前記
    入力コード・シーケンスの命令を、適当な場合には基本
    ブロック境界を超えて再配列して、出力コード・シーケ
    ンスを生成するステップと、から成る命令スケジュール
    方法。
13. 【請求項１３】　　前記ステップａで生成した前記プロ
    グラム依存性グラフが、制御依存性サブグラフとデータ
    依存性サブグラフから成る、請求項１２の方法。
14. 【請求項１４】　　前記ステップｂにおいて、前記入力
    コード・シーケンス中の命令の基本ブロックを、前記制
    御依存性サブグラフを用いてブロック毎にスケジュール
    し、また前記ステップｂが、スケジュール中の各ブロッ
    クに対して、 ｂ）（ｉ）　　前記現行ブロックに命令を寄与させるこ
    との可能な候補ブロックのリストを決めるサブステップ
    、を含んでいる、請求項１３の方法。
15. 【請求項１５】　　前記候補ブロック・リストが、前記
    制御依存性サブグラフにおいて、前記現行ブロックに等
    価でありかつ前記現行ブロックにより支配されると識別
    した全ブロックを含む、請求項１４の方法。
16. 【請求項１６】　　前記候補ブロック・リストが更に、
    前記制御依存性サブグラフにおいて、前記現行ブロック
    の直後のもの、又は前記現行ブロックに等価のブロック
    であって前記現行ブロックにより支配されるそのブロッ
    クの直後のもの、として識別した全ブロックを含む、請
    求項１５の方法。
17. 【請求項１７】　　ｂ）（ｉｉ）　　前記データ依存性
    グラフを用いて前記候補ブロックの集合の中から１組の
    候補命令を判定するサブステップ、を含む請求項１４〜
    １６のいずれかの方法。
18. 【請求項１８】　　前記候補命令リストが、命令がブロ
    ックの境界を超えて移動させることができないタイプで
    はなく、かつ／又はその命令が推測的にスケジュール不
    可能なタイプではない限り、実行が推測的な命令を含む
    、前記現行ブロック又は前記候補ブロック集合の中の１
    つのブロックに属する全命令、を含む、請求項１７の方
    法。
19. 【請求項１９】　　ｂ）（ｉｉｉ）　　機械記述に従っ
    て、前記候補命令リストから次にスケジュールするべき
    １つ又はそれ以上の命令を判定するサブステップ、を含
    む請求項１７又は１８のいずれかの方法。
20. 【請求項２０】　　前記機械記述が、ある範囲のコンピ
    ュータを表すパラメータ型機械記述と、特定のコンピュ
    ータ用の１組のスケジューリング・ヒューリスティック
    と、から成る請求項１９の方法。