JPH04247527A - コンピュータの命令スケジューラ - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータ用の命令
スケジューラに関し、特に並列／パイプライン化コンピ
ュータで使用されるのに適する方法で基本ブロックを越
えて命令のスケジューリングを可能にする命令スケジュ
ーラに関する。命令のスケジューリングとは、コンパイ
ルされた命令の間であり得るランタイム遅延を小さくす
るために、プロセッサによる実行以前にプログラム・ス
テートメントの再構成または変更をするプロセスである
。命令スケジューラは通常コンピュータのコンパイラの
一部として実現される。コンパイラに対する一般的な紹
介は、下記の文献に見出すことができる。即ち、Ｒ１　
　Ａ．Ｖ．Ａｈｏ，Ｒ．ＳｅｔｈｉおよびＪ．Ｄ．Ｕｌ
ｌｍａｎ著「コンパイラ：原理、手法およびツール（Ｃ
ｏｍｐｉｌｅｒｓ：　　Ｐｒｉｎｃｉｐｌｅｓ，　　Ｔ
ｅｃｈｎｉｑｕｅｓ　　ａｎｄＴｏｏｌｓ）」（Ａｄｄ
ｉｓｏｎ−Ｗｅｓｌｅｙ社、１９８６年発行）

【０００
２】

【従来の技術】命令のスケジューリングは、通常中間言
語あるいはアセンブリ・コード・レベルで行われる。こ
のような変換は、データ依存性を保存しなければならず
、他の制約を受ける。このことは、命令の実行を重複さ
せることにより処理能力の増大を可能にするパイプライ
ン化マシン・アーキテクチャのためのコンパイルを行う
時、特に有利であり得る。例えば、もし１つの値Ｖの取
出しと使用の間に１サイクルの遅れがあるならば、この
遅れをＶとは独立でありかつ実行の「用意ができている
」命令で「カバー」することが望ましいことになる。

【０００３】従来の知恵は、スケジュール可能な命令を
基本ブロック内に見出せるようにすること、および基本
ブロックの境界を越えて命令を移動する必要がないこと
である。基本ブロックとは、制御の流れが、出口点を除
いて待機あるいは分岐の可能性なしにシーケンスの初め
に入りかつその終りで抜ける、一連の連続する命令であ
る。事実上、命令のスケジューリングの実現における以
前の作業の全ては、基本ブロック内のスケジューリング
に集中したものであった。基本ブロックのスケジューラ
の事例については、下記の文献に記載されている。即ち
、Ｒ２　　Ｂｅｒｎｓｔｅｉｎ，Ｄ．，Ｂｏｒａｌ，Ｈ
．およびＰｉｎｔｅｒ，Ｒ．Ｙ．著「表現ツリーの最適
なチェイニング（Ｏｐｔｉｍａｌ　　Ｃｈａｉｎｉｎｇ
　　ｉｎ　　Ｅｘｐｒｅｓｓｉｏｎ　　Ｔｒｅｅｓ）」
（コンパイラ構造についてのＡＣＭシンポジウムの議事
録１〜１０頁、１９８６年６月発行） Ｒ３　　Ｇｉｂｂｏｎｓ，Ｐ．Ｂ．およびＭｕｃｈｎｉ
ｃｋ，Ｓ．Ｓ．著「パイプライン化アーキテクチャのた
めの有効な命令スケジューリング（Ｅｆｆｉｃｉｅｎｔ
　　Ｉｎｓｔｒｕｃｔｉｏｎ　　Ｓｃｈｅｄｕｌｉｎｇ
　　ｆｏｒ　　ａ　　Ｐｉｐｅｌｉｎｅｄ　　Ａｒｃｈ
ｉｔｅｃｔｕｒｅ）」（コンパイラ構造についてのＡＣ
Ｍシンポジウムの議事録１１〜１６頁、１９８６年６月
発行）Ｒ４　　Ｇｏｏｄｍａｎ，Ｊ．Ｒ．およびＨｓｕ
，Ｗ．−Ｃ．著「大きな基本ブロックにおけるコード・
スケジューリングおよびレジスタの割付け（ＣｏｄｅＳ
ｃｈｅｄｕｌｉｎｇ　　ａｎｄ　　Ｒｅｇｉｓｔｅｒ　
　Ａｌｌｏｃａｔｉｏｎ　　ｉｎ　　Ｌａｒｇｅ　　Ｂ
ａｓｉｃ　　Ｂｌｏｃｋｓ）」（スーパーコンピューテ
ィングに関する国際会議の議事録（仏国Ｓｔ．Ｍａｌｏ
）４４２〜４５２頁、ＡＣＭＰｒｅｓｓ、１９８８年７
月発行）Ｒ５　　Ｈｅｎｎｅｓｓｙ，Ｊ．Ｌ．およびＧ
ｒｏｓｓ，Ｔ．著「パイプラインの制約のポストパス・
コードの最適化（Ｐｏｓｔｐａｓｓ　　Ｃｏｄｅ　　Ｏ
ｐｔｉｍｉｚａｔｉｏｎ　　ｏｆ　　Ｐｉｐｅｌｉｎｅ
　　Ｃｏｎｓｔｒａｉｎｔｓ）」（プログラミング言語
およびシステムに関するＡＣＭ報告書、４２２〜４４８
頁、１９８４年７月発行） Ｒ６　　Ｈ．Ｗａｒｒｅｎ著「ＩＢＭ　　ＲＩＳＣシス
テム／６０００プロセッサにおける命令スケジューリン
グ（Ｉｎｓｔｒｕｃｔｉｏｎ　　Ｓｃｈｅｄｕｌｉｎｇ
ｆｏｒ　　ｔｈｅ　　ＩＢＭ　　ＲＩＳＣ　　Ｓｙｓｔ
ｅｍ／６０００　　Ｐｒｏｃｅｓｓｏｒ）」（ＩＢＭ　
　Ｊｏｕｒｎａｌ　　ｏｆ　　Ｒｅｓｅａｒｃｈ　　ａ
ｎｄ　　Ｄｅｖｅｌｏｐｍｅｎｔ、第３４巻、第１号、
８５〜９２頁、１９９０年１月発行） Ｒ７　　Ｓ．ＷｅｉｓｓおよびＪ．Ｅ．Ｓｍｉｔｈ著「
パイプライン化スーパーコンピュータにおけるスカラー
・コンパイル手法の研究（Ａ　　Ｓｔｕｄｙ　　ｏｆＳ
ｃａｌａｒ　　Ｃｏｍｐｉｌａｔｉｏｎ　　Ｔｅｃｈｎ
ｉｑｕｅｓ　　ｆｏｒ　　Ｐｉｐｅｌｉｎｅｄ　　Ｓｕ
ｐｅｒｃｏｍｐｕｔｅｒｓ）」（プログラミング言語お
よびオペレーティング・システムに対するアーキテクチ
ャ・サポートに関する第２回国際会議の議事録、１０５
〜１０９頁、１９８７年１０月発行）

【０００４】

【発明が解決しようとする課題】上記の文献に記載され
た如き基本ブロック・スケジューラは、一般に、浪費さ
れるマシン・サイクルを排除するため、各基本ブロック
内の独立的な命令をインターリーブすることを試みる。 このようなスケジューラは、ある科学的用途において普
通である長い基本ブロックにおけるプログラムに非常に
有効である。しかし、分岐命令は、基本ブロックの変換
のみでは取扱うことができないことでパイプライン化ア
ーキテクチャの有効性を制約する。

【０００５】命令スケジューリングのための特定の用途
は、いわゆる縮小命令セット・コンピュータ（ＲＩＳＣ
）の分野に含まれる。ＲＩＳＣコンピュータの紹介は、
下記の文献に見出すことができる。即ち、Ｒ８　　Ｐａ
ｔｔｅｒｓｏｎ，Ｄ．Ａ．著「縮小命令セット・コンピ
ュータ（Ｒｅｄｕｃｅｄ　　Ｉｎｓｔｒｕｃｔｉｏｎ　
　Ｓｅｔ　　Ｃｏｍｐｕｔｅｒｓ）」（Ｃｏｍｍｕｎｉ
ｃａｔｉｏｎｓ　　ｏｆ　　ｔｈｅ　　ＡＣＭ、８〜２
１頁、１９８５年１月発行） １９７０年代の後半に出現した高速プロセッサを構築す
るＲＩＳＣの試みは、プログラム命令のストリームライ
ン化の必要を強調する。その結果、命令は、通常は中間
言語あるいはアセンブリ・コード・レベルで、パイプラ
インの全ての利点を利用し、またこれにより性能を改善
するように構成し直されねばならない。命令のスケジュ
ーリングの負担は、ＲＩＳＣプロセッサに対するコード
を生成するコンパイラを最適化することに置かれた。通
常、コンパイラは、基本ブロック・レベルで命令のスケ
ジューリングを行い、ＲＩＳＣプロセッサのパイプライ
ン構造により課される諸問題の大半を解決している。

【０００６】基本的なＲＩＳＣアーキテクチャにあって
も、基本ブロック内のみのスケジューリングは、予測し
得ない分岐で終る多くの小さな基本ブロックを含むある
ＵＮＩＸタイプ（ＵＮＩＸは、ＡＴ＆Ｔ　　Ｂｅｌｌ研
究所の商標）のプログラムに対して多くのノーオペレー
ション・コードを伴うコードを結果として得る。これら
の問題は、通常基本ブロックがより大きくなる科学的演
算プログラムにとっては非常に厳しいものとなる傾向に
はない。

【０００７】最近、サイクル当たり１つ以上の命令を発
行する能力によってＲＩＳＣを拡張する新しいタイプの
アーキテクチャが登場しつつある。例えば、下記の文献
を参照されたい。即ち、Ｒ９　　Ｒ．Ｄ．Ｇｒｏｖｅｓ
およびＲ．Ｏｅｈｌｅｒ著「ＩＢＭの第２世代ＲＩＳＣ
プロセッサのアーキテクチャ（Ａｎ　　ＩＢＭＳｅｃｏ
ｎｄ　　Ｇｅｎｅｒａｔｉｏｎ　　ＲＩＳＣ　　Ｐｒｏ
ｃｅｓｓｏｒ　　Ａｒｃｈｉｔｅｃｔｕｒｅ）」（コン
ピュータ設計に関するＩＥＥＥ会議の議事録、１３４〜
１３７頁、１９８９年１０月発行） スーパースカラーあるいはスーパーパイプライン化アー
キテクチャと呼ばれるこのタイプの高速プロセッサは、
基本ブロック・レベルにおける命令スケジューリングで
は要求される程度にマシンの資源を利用するコードを生
成するのに充分でないため、コンパイラに対してより重
大な問題を呈する。下記の文献を参照されたい。即ち、
Ｒ１０　　Ｎ．Ｐ．ＪｏｕｐｐｉおよびＤ．Ｗ．Ｗａｌ
ｌ著「スーパースカラーおよびスーパーパイプライン化
マシンに使用可能な命令レベルの並行処理（Ａｖａｉｌ
ａｂｌｅ　　Ｉｎｓｔｒｕｃｔｉｏｎ−ｌｅｖｅｌ　　
Ｐａｒａｌｌｅｌｉｓｍ　　ｆｏｒ　　Ｓｕｐｅｒｓｃ
ａｌａｒ　　ａｎｄ　　Ｓｕｐｅｒｐｉｐｅｌｉｎｅｄ
Ｍａｃｈｉｎｅｓ）」（第３回ＡＳＰＬＯＳ会議の議事
録、２７２〜２８２頁、１９８９年４月発行） スーパースカラー・マシンに対する命令スケジューリン
グを研究する最近の１つの努力は、下記の文献に報告さ
れている。即ち、Ｒ１１　　Ｍ．Ｃ．Ｇｏｌｕｍｂｉｃ
およびＶ．Ｒａｉｎｉｓｈ著「基本ブロックを越えた命
令スケジューリング（Ｉｎｓｔｒｕｃｔｉｏｎ　　Ｓｃ
ｈｅｄｕｌｉｎｇ　　ｂｅｙｏｎｄ　　ＢａｓｉｃＢｌ
ｏｃｋｓ）」（ＩＢＭ　　Ｊｏｕｒｎａｌｏｆ　　Ｒｅ
ｓｅａｒｃｈ　　ａｎｄ　　Ｄｅｖｅｌｏｐｍｅｎｔ、
第３４巻、第１号、９３〜９７頁、１９９０年１月発行
）この文献においては、基本ブロックの範囲を越えたス
ケジューリングのためのコード複写法が研究され、コン
パイルされたコードの実行時間の改善をもたらす結果と
なる。しかし、上記の試みは、更に改善するための余地
を依然として残している。

【０００８】

【課題を解決するための手段】本発明の目的は、浪費さ
れるマシン・サイクルが更に少ないより効率のよいコン
パイル・コードを提供するため、基本ブロックを越えた
スケジューリングを行うことができる命令スケジューラ
の提供することにある。

【０００９】本発明によれば、コンピュータ用の命令ス
ケジューラが提供され、この命令スケジューラは、命令
スケジューリングの目的のため抑制し得る命令の候補と
なるサブシーケンスを命令シーケンス内で識別する前処
理ロジックと、抑制された識別サブシーケンスを含む命
令シーケンスをスケジューリングするために前処理ロジ
ックに応答する基本ブロック・スケジューリング・ロジ
ックからなっている。

【００１０】本発明は、前処理ロジックおよび後処理ロ
ジックのみを付設して従来の基本ブロック・スケジュー
ラの使用を可能にする。本発明は、基本ブロックを充分
に越えた能力を持つ制御フロー全体にわたるスケジュー
リングを行う。本発明は、分岐、ループ等によるランタ
イムの遅れの減少を可能にし、またパイプライン化アー
キテクチャを他の方法では不可能な方法で利用すること
を可能にする。

【００１１】前処理ロジックは、命令の基本ブロックが
制御フローの順序で配列される修正された命令シーケン
スを生じるように作動することが望ましい。従って、基
本ブロックのスケジューリング・ロジックにこの修正さ
れた命令シーケンスを使用する命令をスケジュールさせ
ることにより、基本ブロックのスケジューリング・ロジ
ックの正しい処理の順序を容易に確保することができる
。

【００１２】また、前処理ロジックは、候補となるサブ
シーケンスに対する入口ブロックと出口ブロックを識別
し、この基本ブロック・スケジューリング・ロジックは
、１つの疑似命令として取扱うことによりこのサブシー
ケンスを抑制するため相互に異なる入口ブロック値と出
口ブロック値の通知に応答する。このようにして、サブ
シーケンスは、スケジューリング操作に対する入口点と
出口点が別々の基本ブロックと関連することの通知に応
答して基本ブロック・スケジューラにより自動的に抑制
される。

【００１３】しかし、あるいはまた、前処理は、抑制さ
れるべきサブシーケンスの命令に物理的にタグを付すこ
とができ、基本ブロック・スケジューリング・ロジック
はこのタグを用いて抑制される命令を決定する。

【００１４】あるいはまた更に、前処理ロジックは、サ
ブシーケンスをセーブして疑似命令をその場所に挿入す
ることによりサブシーケンスを抑制するように構成する
ことができ、この疑似命令はこれが置換する命令のレジ
スタおよびメモリー参照を記録する。このことは、従来
の基本ブロック・スケジューラを基本ブロック・スケジ
ューリング・ロジックとして修正しないで使用すること
を可能にする。この場合、命令スケジューラはまた、疑
似命令と関連するポインタを用いてセーブされたサブシ
ーケンスをアクセスして、セーブされたサブシーケンス
により疑似命令を置換することにより、修正されたシー
ケンスのスケジューリング後に疑似命令を拡張するため
の後処理ロジックを含むことが望ましい。

【００１５】前処理ロジックは、入力命令シーケンスに
対する制御フロー・グラフに応答して、一義的な入口お
よび一義的な出口を持ち予め定めた基準を満たすグラフ
の領域を識別することにより抑制される候補となるサブ
シーケンスを識別することが望ましい。入口ｘおよび出
口ｙ（ｘ≠ｙ）を持つグラフの領域Ｈに対して望ましい
基準は、 ａ）ｘおよびｙがＨに帰属すること ｂ）（Ｈ−ｘ）の全ての直前のセットは、（Ｈ−ｙ）の
サブセットであること ｃ）（Ｈ−ｙ）の全ての直後のセットは、（Ｈ−ｘ）の
サブセットであること ｄ）入口ｘ’および出口ｙ’が（ａ）−（ｃ）を満足し
、ｘ＝ｘ’あるいはｙ＝ｙ’であるＨのサブセットであ
る領域Ｈ’は存在しないことである。

【００１６】入口ｘおよび出口ｙが基本ブロックである
場合、領域Ｈの候補となるサブシーケンスは下記のもの
からなることが望ましい。即ち、 −もし分岐ならば、入口ブロックｘの最後の命令−存在
するならば、出口ブロックｙの先頭のラベル、および −Ｈの全ての残るブロックにおける全ての命令前処理ロ
ジックが、抑制の候補となる複数のサブシーケンスを識
別するため命令の入力シーケンスについて反復的に演算
することが望ましい。このようにして、前処理ロジック
は、略式疑似命令によりフロー・グラフの連続するより
大きな部分を置換するように働き、結果として基本ブロ
ック・スケジューラによりスケジュール可能な直線コー
ドの新しいより大きな部分を生じることになる。

【００１７】本発明はまた、前に述べた如き命令スケジ
ューラを含むコンピュータを提供する。

【００１８】本発明の第２の特質によれば、下記のステ
ップを含むコンピュータにおける命令のスケジュール方
法が提供される。即ち、 ａ）命令スケジューリングの目的のため抑制することが
できる候補となる命令サブシーケンスを命令シーケンス
内で識別し、 ｂ）基本ブロック・スケジューリング・ロジックを用い
て、識別された抑制サブシーケンスを含む命令シーケン
スをスケジューリングする。

【００１９】以下においては本発明の特定例について、
本文の記述の終りに見出される表および添付図面に関し
て説明する。

【００２０】−表１は、本発明の動作を説明するための
プログラムの事例である。

【００２１】−表２は、表１のプログラムの一部と対応
するマシン命令の注釈を付したシーケンスである。

【００２２】−表３は、前処理後の表２の命令シーケン
スを示す。

【００２３】−表４は、スケジューリング後の表３の命
令シーケンスを示す。

【００２４】−表５は、命令の出力シーケンスを示す。

【００２５】

【実施例】図１は、本発明による命令スケジューラ１０
の概説用の概略ブロック図である。この命令スケジュー
ラは、その入力として一連の命令１１を受取り、更にス
ケジュールされるプログラムに対する制御フロー・グラ
フ１２に応答する。この命令スケジューラは、その出力
として一連の再スケジュール命令１６を与える。この命
令スケジューラは、修正された命令シーケンス１４を生
じる前処理ロジック１３と、参考のため本文に引用され
るＷａｒｒｅｎの文献（文献Ｒ６）に記載された如き従
来の基本ブロック・スケジューラ１５とを含む。用語「
命令」とは、ラベル、分岐ステートメント等のプログラ
ム中に見出すことができる如何なるステートメントも含
むように広義に解釈されるべきであることに注意された
い。

【００２６】本発明の実施例においては、命令スケジュ
ーラは、コンパイラ、特にＩＢＭＲＩＳＣシステム／６
０００コンピュータに対するＩＢＭ　　ＸＬファミリー
のコンパイラの１つの一部を形成する。この命令スケジ
ューラは、コンパイル動作の間、必要に応じて１回以上
作動するように呼出すことができる。以下本文において
は、この命令スケジューラは中間言語レベルで命令に対
して用いられるものとして記述される。しかし、この命
令スケジューラは、アセンブリ・コード・レベルでも等
しく使用することができる。本例においては、前処理ロ
ジック１３および基本ブロック・スケジューラ１５は、
入力１１、修正１４および出力１６の命令シーケンスと
同様に、コンパイラが動作中のＩＢＭ　　ＲＩＳＣシス
テム／６０００コンピュータの作業用記憶域に保持され
る。ＩＢＭ　　ＲＩＳＣシステム／６０００コンピュー
タ・ファミリーについてのこれ以上の情報については、
ＩＢＭＪｏｕｒｎａｌ　　ｏｆ　　Ｒｅｓｅａｒｃｈ　
　ａｎｄ　　Ｄｅｖｅｌｏｐｍｅｎｔ、第３４巻、第１
号、１９９０年１月発行を参照されたい。

【００２７】前処理ロジック１３は、その機能として、
一義的な入口および出口を持ちある最低条件を満たす命
令のサブシーケンスを入力命令シーケンスにおいて識別
する。このようなサブシーケンスは、以下本文で「Ｓ領
域」と呼ばれる命令シーケンスに対するフロー・グラフ
の１つの領域を形成する。フロー・グラフのこのような
領域は、「ハンモック」として文献に記載されている（
Ｋａｓ’ｊａｎｏｖ，Ｖ．Ｎ．著「Ｄｉｓｔｉｎｇｕｉ
ｓｈｉｎｇ　　Ｈａｍｍｏｃｋｓ　　ｉｎ　　ａ　　Ｄ
ｉｒｅｃｔｅｄ　　Ｇｒａｐｈ」（Ｓｏｖｉｅｔ　　Ｍ
ａｔｈ．Ｄｏｃｌａｄｙ　　１６，５、４４８〜５５０
頁、１９７５年発行）参照）。

【００２８】この機能を実施する際、前処理ロジック１
３は、基本ブロックおよびループをコード・シーケンス
で識別するため、また各ブロックへのエントリと同時に
種々のプロセッサのレジスタの情報を調べるため、従来
のコンパイラ・ロジックにより生成される制御フロー・
グラフ１２を使用する。この制御フロー・グラフは、入
口および出口点、ブロックの構成命令およびブロック間
の論理的関係（例えば、前後の関係）を識別するデータ
を含む入力命令シーケンスにおける基本ブロックについ
て詳細を与える基本ブロック・テーブルを含んでいる。 基本ブロックおよびフロー・グラフの意味の一般的な論
議は、文献Ｒ１の５２８乃至５３４頁に見出される。

【００２９】スケジュールされるプログラムを表わす制
御フロー・グラフＧの一部の事例が図２に示される。フ
ロー・グラフにおけるノードＢ１乃至Ｂ２３は、種々の
ブロックのどれが直前および直後であるかを示すノード
間の方向付けされたエッジを持つプログラムの基本ブロ
ックと対応している。例えば、ブロックＢ１からＢ２へ
の方向付けされたエッジＤＥ１がある時、これはＢ２が
Ｂ１の直後のものであることを意味する。換言すれば、
プログラムの制御は、基本ブロックＢ１から基本ブロッ
クＢ２へ流れる。フロー・グラフは一義的な入口ノード
Ｂ１と一義的な出口ノードＢ２３を有することが判る。

【００３０】好都合にも、制御フロー・グラフ１２は、
コンパイラがそのグラフにおけるノードと対応する１組
のリンクされたレコードを有し、ノード間のエッジがレ
コード間のポインタにより表わされるデータ構造形態で
動作するコンピュータのメモリー中に格納される。ポイ
ンタは、ある基本ブロックから他の基本ブロックへのプ
ログラムの流れを制御する条件を示すフィールドにより
適当に補充することができる。

【００３１】命令の入力、出力および修正されたシーケ
ンスもまた、コンパイラが動作中のコンピュータのメモ
リーに格納される。各シーケンスは、２重にリンクされ
たリストとして格納される。１つのシーケンスにおける
各命令は、そのパラメータ（レジスタ、メモリー参照、
等）を記述するフィールドの他２つのフィールドで格納
される。最初の付加的フィールドは、シーケンスにおけ
る前の命令に対するポインタを含み、２番目のフィール
ドは次の命令に対するポインタを含む。従って、これら
のポインタを用いて、命令シーケンスを一方から他方へ
のいずれの方向にも走査することが可能となる。

【００３２】前処理プログラムは、修正された命令シー
ケンス１４を生成し、基本ブロック・スケジューラに対
して制御パラメータを発して抑制された命令のサブシー
ケンス（複数または単数）で命令シーケンスをスケジュ
ールさせる。命令の各抑制サブシーケンスは、命令シー
ケンスにおけるＳ領域と対応する。このような各サブシ
ーケンスは、１つの疑似命令として取扱われ、命令を基
本ブロック境界を越えて移動することを可能にする。デ
ータ依存は無論保存されねばならない。

【００３３】前処理ロジック１３は、制御フロー・グラ
フ１２を分析することにより、スケジューリングの目的
のため疑似命令として要約できるＳ領域（即ち、命令の
サブシーケンス）を識別する。前処理ロジックは、制御
フロー・グラフを分析して、入口ｘおよび出口ｙ（ｘ≠
ｙ）を有し下記の要件を満たすグラフＧのサブグラフＨ
を探すことによりＳ領域を識別する。即ち、ａ）ｘおよ
びｙがＨに帰属すること ｂ）（Ｈ−ｘ）の全ての直前のセットは、（Ｈ−ｙ）の
サブセットであること ｃ）（Ｈ−ｙ）の全ての直後のセットは、（Ｈ−ｘ）の
サブセットであること ｄ）入口ｘ’および出口ｙ’が（ａ）−（ｃ）を満足し
、ｘ＝ｘ’あるいはｙ＝ｙ’であるＨのサブセットであ
る領域Ｈ’は存在しないことである。

【００３４】Ｓ領域Ｈの定義は、Ｈの外側（Ｇのノード
）からＨへの各経路がｘを通過すること、ＨからＨの外
側（Ｇのノード）への各経路がｙを通過すること、およ
び入口ｘあるいは出口ｙを持つ高々１つのＳ領域がある
ことを意味する。

【００３５】図２においては、７つのＳ領域があり、こ
れらは下記の如くＳ０乃至Ｓ６で示される。即ち、Ｓ０
は、入口Ｂ２および出口Ｂ５を持つＢ２〜Ｂ５からなる
。

【００３６】Ｓ１は、入口Ｂ５および出口Ｂ７を持つＢ
５〜Ｂ７からなる。

【００３７】Ｓ２は、入口Ｂ７および出口Ｂ１０を持つ
Ｂ７〜Ｂ１０からなる。

【００３８】Ｓ３は、入口Ｂ１１および出口Ｂ２０を持
つＢ１１〜Ｂ２０からなる。

【００３９】Ｓ４は、入口Ｂ１６および出口Ｂ１９を持
つＢ１６〜Ｂ１９からなる。

【００４０】Ｓ５は、入口Ｂ２０および出口Ｂ２２を持
つＢ２０〜Ｂ２２からなる。

【００４１】Ｓ６は、入口Ｂ１および出口Ｂ２３を持つ
Ｂ１〜Ｂ２３からなる。

【００４２】Ｓ領域は、ネストおよび（または）連鎖さ
せることができる。本例においては、Ｓ０、Ｓ１、Ｓ２
およびＳ３、Ｓ５は、連鎖されたＳ領域であり、領域Ｓ
４は領域Ｓ３内にネストされ、Ｓ０〜Ｓ５はＳ６内にネ
ストされる。

【００４３】１つのＳ領域の概念は、最小条件のない充
分に構造化された言語におけるステートメントのそれに
類似するが、任意のプログラム構造の取扱いに加えて、
ある充分に構造化されたステートメントは許容されない
。例えば、Ｓ領域Ｓ０およびＳ２は、「非常に非構造的
」である。また、ある定義においてはステートメントと
見做され得るが、基本ブロックＢ１２、Ｂ１３、Ｂ１４
、Ｂ１５のグループはＳ領域でないことに注意されたい
。

【００４４】疑似命令でＳ領域を置換することにより、
後に述べるように、「直線」コードの比較的長い部分を
作ることができ、命令を基本ブロックを越えて移動する
ことを許容する。例えば、図２においては、連鎖Ｂ２、
Ｐ０、Ｂ５、Ｐ１、Ｂ７、Ｐ２、Ｂ１０（但し、Ｐ０、
Ｐ１、Ｐ２は、それぞれＳ領域Ｓ０、Ｓ１およびＳ２に
対する疑似命令を表わす）は、直線コードであり、通常
の方法でデータ依存が許容するものとして、命令をＢ７
からＢ２まで、あるいはＢ５からＢ１０までのように移
動することが可能となる。基本ブロック２０が分岐を持
たず基本ブロック２２がラベルを持たないため、（疑似
命令Ｐ５が置換する）Ｓ５に対するセーブされた命令サ
ブシーケンスは、ブロックＢ２１からの命令のみからな
ることに注意されたい。

【００４５】Ｓ領域への分解は、分岐およびループの結
果として生じる残りの遅延（ＮＯ−ＯＰ）の排除機構を
提供する。全てのＳ領域を生成することにより、あるい
はこれら領域を必要に応じて生成することにより、命令
スケジューリングは下記の如く行うことができる。以降
においては、スケジュールされる命令が、各基本ブロッ
クが分岐の目標である等の如き必要がある場合にのみラ
ベル（命令なし）で始まる中間言語（ＩＬ）にあるもの
とする。

【００４６】制御フロー・グラフは、各々の入り口ノー
ドｘ、出口ノードｙおよび中間ノードの決定を含むＳ領
域の識別に必要な基本ブロックの構造上の情報を提供す
る。前処理ロジックは、これが識別する各Ｓ領域毎に各
々の入口ノードｘ、出口ノードｙおよび中間ノードのデ
ータを格納するＳ領域テーブルを生成する。Ｓ領域テー
ブルは、コンパイラが動作中であるコンピュータのメモ
リーに保持される。

【００４７】Ｓ領域テーブルのセットアップの際、前処
理ロジックはＳ領域の命令に黙示的にタグを付す。換言
すれば、Ｓ領域テーブルをアクセスすることにより、抑
制のための候補となるサブシーケンスに帰属する命令を
識別することができる。命令が物理的にタグ付けされな
い時、スケジューリング後に取外されるタグはない。

【００４８】与えられたＳ領域に対して黙示的にタグを
付される、抑制のための命令のサブシーケンス（Ｐ）は
、下記を含む。即ち、 ・もしｂが分岐ステートメントならば、入口ブロックｘ
の最後のステートメント ・もし１が存在するならば、出口ブロックｙの先頭のラ
ベル１ ・全ての残るブロックＨにおけるステートメント遅れが
依然として存在する時、前処理プログラムは、連続的に
より大きなＳ領域Ｈを探して、識別される時各Ｓ領域毎
に適当なデータをＳ領域テーブルに格納する。前処理が
完了すると、基本ブロック・スケジューラが作動するよ
うに呼出される。しかし、基本ブロック・スケジューラ
の呼出しの前に、前処理ロジックはＳ領域テーブルおよ
び制御フロー・グラフを用いて命令シーケンスにおける
ポインタを修正して、基本ブロックが命令シーケンスの
制御フローにより指定される論理シーケンスに生じるよ
うにし、即ち、１つのＳ領域の入口ブロックが全ての中
間ブロックの先になり、出口ノードが全ての中間ブロッ
クに続くようにする。本発明の本実施例においては、前
処理ロジックは命令フィールド（単に命令フィールドを
伴うポインタ）の内容の修正も制御フロー・グラフの修
正のいずれも行わない。

【００４９】命令シーケンスにおけるポインタを修正し
た後、基本ブロック・スケジューラにとっては、修正さ
れた命令シーケンスにおけるポインタを用いて入口ノー
ドから出口ノードへのＳ領域の全ての命令を通して順序
付けすることは簡単なことである。（ポインタにより決
定される如き）入力命令シーケンスにおける１つの基本
ブロック内の命令の順序は制御フローに従って論理シー
ケンスと対応するが、これは基本ブロック間の分岐およ
び飛越し命令の故に、基本ブロック境界の場合通常では
ないことに注意すべきである。

【００５０】従来の基本ブロック・スケジューラは、ス
ケジュールされる基本ブロックを表示するパラメータを
受取ることになる。これは、基本ブロックに対する命令
を決定し、かつ基本ブロックに対する命令毎の１つのノ
ードであって、各々が対応する命令に対するレジスタお
よびメモリー参照を記録するノードでデータ依存グラフ
を形成するため制御フロー・グラフにおけるデータを使
用する。そして、これは、データ依存グラフを用いて、
種々のヒューリスティックス（文献Ｒ６参照）に従って
基本ブロックの命令を構成し直す。このヒューリスティ
ックスは、一連の命令を含むプログラムがコンパイルさ
れつつあるコンピュータ（即ち、目標のコンピュータ）
の詳細に依存する。

【００５１】本発明における基本ブロック・スケジュー
リング・ロジックの動作は概して類似している。しかし
、このロジックは、１つのパラメータではなく、前処理
ロジックから２つの入力パラメータ、即ち、入口および
出口のブロックに対するパラメータｘおよびｙを受取る
。

【００５２】基本ブロック・スケジューラ１５は、入口
ノードｘが出口ノードｙと等しいかどうかを判定するた
めのロジックを含む。もしそうであれば、このロジック
は、単一の基本ブロックの取扱いを行い、このブロック
の命令をスケジュールするため正確に正常なものとして
進行する。しかし、もしｘおよびｙが等しくなければ、
このロジックは制御フローを越えてスケジュールすべき
ことを判定する。

【００５３】スケジューラが制御フローを越えてスケジ
ュールしなければならない（即ち、ｘとｙが等しくない
）場合は、基本ブロック・スケジューラは下記のものか
らなる直線コードについて働く。即ち、（ｉ）ｘの命令
（分岐ならば、最後の命令なしに）（ｉｉ）疑似命令（
サブシーケンスＰと対応する）（ｉｉｉ）ｙの命令（ラ
ベルならば、第１の命令なしに）特に、基本ブロック・
スケジューラは、修正シーケンスにおけるポインタを用
いて命令（ｉ）（即ち、この最後の命令が分岐ならば、
その命令以外のブロックｘの命令）を命令毎に位に走査
し始め、各命令毎に１つのデータ依存グラフに１つのノ
ードを生成する。このデータ依存グラフは、コンパイラ
が動作中のコンピュータのメモリーに保持される。基本
ブロック・スケジューラが命令（ｉｉ）（即ち、これが
分岐ならばブロックｘの最後の命令、さもなければ、最
初の中間基本ブロックの最初の命令）に達する時、この
スケジューラはこれがＳ領域内にあることを表示するフ
ラッグをセットする。このスケジューラは、これがラベ
ルであるならば基本ブロックｙの最初の命令に、さもな
ければ、論理的に先行する中間基本ブロックの最後の命
令に達するまで、修正シーケンスにおいて命令の走査を
継続する。このスケジューラは、修正シーケンスにおけ
る命令を伴うポインタを用いて命令を走査する。これが
命令を走査する時、これら命令に対するレジスタおよび
メモリー参照を照合する。これら全ての命令に対して、
基本ブロック・スケジューラは単にデータ依存グラフ（
即ち、疑似命令に対して）における１つのノードを割付
け、このノードが照合されたレジスタおよびメモリー参
照を記録する。このようにして、Ｓ領域と対応する個々
の命令は抑制され、疑似命令Ｐにより置換される。次い
で、これは、「内部のＳ領域」フラッグをリセットして
、命令（ｉｉｉ）（即ち、これが分岐ならば、最初の命
令のない基本ブロックｙの命令）を通常の方法で処理す
るため進み、各命令毎にデータ依存グラフにノードをセ
ットアップする。

【００５４】その後、基本ブロック・スケジューラは正
常に進んで、（ｂがＰに帰属するならば、ｂのない）ブ
ロックｘ、タグを付した命令からなる疑似命令Ｐ、およ
び（１がＰに帰属するならば、１のない）ブロックｙか
らなる「直線」コードの命令を、目標コンピュータに対
するヒューリスティックスに従って生成したデータ依存
グラフを用いて構成し直す。

【００５５】スケジューリングの後、ポインタは、基本
ブロックの元の順序を復元するため、制御フロー・グラ
フを用いて修正することができる。しかし、基本ブロッ
クの順序は復元できる（即ち、入出力シーケンスにおけ
る基本ブロックの順序が同じになるように）が、命令の
順序は再スケジューリングが生じた場合は異なることに
注意されたい。

【００５６】本発明による命令スケジューラの動作の一
例については、表１乃至表５に関して更に説明する。表
１は、スケジューリングのためのサンプル・プログラム
を示す。表２における２つの中間の列は、表１のプログ
ラムの行２から行６までに対応する中間レベルのマシン
命令シーケンスを示す。表２の左側の列は、命令の番号
（Ｉ１〜Ｉ１２）を示し、右側の列は命令における基本
ブロック（Ｂ１〜Ｂ４）を示す。左側の列の左の３つの
＋符号については後で説明する。

【００５７】表３は、基本ブロック・スケジューラ１５
により認識される如き修正された命令シーケンス１４を
示す。前処理ロジック１３は、基本ブロックＢ２、Ｂ３
、Ｂ４が基本ブロックＢ２における入口および基本ブロ
ックＢ４における出口を持つＳ領域を形成すると判定し
た。このＳ領域から、表２の＋符号で示した３つの命令
、即ち、（分岐である）基本ブロックＢ２の最後の命令
、基本ブロックＢ３の全ての命令（本例では、１つしか
ない）、および（ラベルである）基本ブロックＢ４の最
初の命令が抑制できることになる。基本ブロックＢ２と
して入口点およびブロックＢ４として出口点を与える入
口パラメータを受取ると同時に、基本ブロック・スケジ
ューラは、抑制される命令Ｉ８、Ｉ９およびＩ１０でそ
のデータ依存グラフを生成し、これらの命令は「ＰＳＥ
ＵＤＯ」と呼ばれＳＵＰＲを付した１つの疑似命令とし
て取扱われる。

【００５８】命令Ｉ８乃至Ｉ１０の抑制に続いて、表３
の命令Ｉ４乃至Ｉ１２は、データ依存グラフを用いて周
知の方法で基本ブロック・スケジューラ１５によりスケ
ジュールされる「直線」コードを形成する。結果として
得るスケジュールされたコードは表４に示され、これに
おいては命令Ｉ１１およびＩ１２間のパイプライン遅れ
をカバーするため、基本ブロック・スケジューラ１５が
命令番号Ｉ１１をＰＳＥＵＤＯ命令を越えて移動したこ
とが判る。抑制された命令Ｉ８、Ｉ９およびＩ１０を含
む全出力命令シーケンスは、表５に示される。

【００５９】コアに基本ブロック・スケジューラを持ち
ながら、基本ブロックを越えるコードのスケジューリン
グを可能にすることにより、パイプライン化アーキテク
チャ特性を取ることの全ての利点を可能にする命令スケ
ジューラが記述された。本発明は、略式疑似命令として
処理される候補となるコード・シーケンスを識別するた
め、従来のコンパイラにより生成される如きフロー・グ
ラフを使用することが望ましい。基本ブロック・スケジ
ューラにより操作される前にフロー・グラフを前処理す
るためのロジックを付設することにより、現行のコンパ
イラを最小限度に変更することによってＳ領域を生成あ
るいは認識することが可能である。前処理ロジックの効
果は、フロー・グラフを分解し、スケジューリング目的
のため疑似命令により置換できるコードの部分を識別す
ることである。このため、基本ブロック・スケジューラ
が、さもなければその範囲を越えることになる有効なス
ケジューリングの機会を識別することを可能にする。

【００６０】本発明の一例を記述したが、修正および（
または）付設が頭書の特許請求の範囲内で可能であるこ
とが理解されよう。

【００６１】例えば、望ましい実施態様においては、Ｓ
領域に対する入口点および出口点を識別することにより
黙示的に行われるが、前処理ロジックは、抑制すること
が可能な命令を物理的に「タグ付け」しない。次いで、
基本ブロック・スケジューリング・ロジックは、これが
受取る情報に応答して黙示的に「タグ付け」された命令
を抑制する。別の実施例においては、前処理ロジックは
、抑制される命令を物理的にタグ付けするように構成す
ることができる。換言すれば、タグ・フィールドを基本
ブロック・スケジューラにより使用される中間言語命令
に設けることもでき、このタグ・フィールドはＳ領域に
帰属する命令に対してセットされてこれが帰属するＳ領
域を識別する。従って、基本ブロック・スケジューラは
、疑似命令により置換される命令を識別するため、命令
上のタグを直接使用することも可能である。この場合、
いったん基本ブロック・スケジューラがその作業を行う
と、タグは再スケジュールされた出力命令シーケンス１
６を形成するため落とされる必要がある。

【００６２】疑似命令の生成のため命令のタグ付けに代
わるものは、サブシーケンスをメモリーにセーブして、
前処理ロジックにより照合される時、置換する命令のレ
ジスタおよびメモリー参照を記録する疑似命令をその場
所に挿入することによって、各Ｓ領域サブシーケンスの
命令を物理的に置換することである。この場合、前処理
ロジックは、命令（ｉ）〜（ｉｉｉ）のリストを用意し
て疑似サブルーチン呼出しの使用によりＳ領域を抑制す
る。この場合、前処理ロジックの出力は、（ｂがＰに帰
属するならば、ｂのない）ブロックｘ、疑似サブルーチ
ン呼出し、および（１がＰに帰属するならば、１のない
）ブロックｙ、更には疑似サブルーチン呼出しが指示す
る別のセーブされたサブシーケンスからなる結果として
の直線コードを含む修正命令シーケンスとなる。

【００６３】一旦Ｓ領域が識別されて疑似サブルーチン
呼出しにより置換されると、完全に周知の基本ブロック
・スケジューラが結果として得た直線コードに応用する
ことができる。セーブされたサブシーケンスに対するポ
インタは、（基本ブロック・スケジューラによりスケジ
ュールされないコメントとして）疑似命令と関連する。 このポインタを用いてセーブされたサブシーケンスをア
クセスする後処理ロジックを、セーブされたサブシーケ
ンスをスケジューリング後にアクセスするため設けるこ
とができる。このようにして、スケジュール後の修正さ
れた命令シーケンスを完全な再スケジュールされた出力
命令シーケンスに拡張するため疑似サブシーケンス呼出
しの代わりに、サブシーケンスをスケジュールされた命
令シーケンスに挿入することができる。このような実施
例においては、修正することなくどんな従来の基本ブロ
ック・スケジューラでも使用することができる。

【００６４】Ｓ領域と対応する命令の抑制の上記以外の
別の試みを本発明の範囲内で考えられることが理解され
よう。即ち、基本ブロック・スケジューラの外部で（最
後に述べた代替におけるように）、あるいは望ましい実
施態様および最初に述べた代替におけるように部分的に
基本ブロック・スケジューラ内部で行うことができる。 しかし、上記の全ての代替において、スケジューリング
・プロセスのある段階で、スケジューラはＳ領域と対応
する命令のサブシーケンスを１つの命令として解釈する
。

【００６５】スケジューリング後に必要な後処理の程度
は、特定の構成に依存する。先に述べたように、もしサ
ブシーケンスが中間言語の命令シーケンスから物理的に
排除されるならば、後処理ロジックがこれらを復元しな
ければならない。もし命令が物理的にタグ付けされるな
らば、後処理がタグを取外す（タグ・フィールドをゼロ
にする）ことが必要である。望ましい実施態様における
ように全てが黙示的に取扱われるならば、後処理は不要
である。

【００６６】本発明の望ましい実施態様においては、命
令スケジューラは、コンパイラ・プログラムの一部とし
てソフトウエアで実現される。しかし、このスケジュー
ラは少なくとも部分的にハードウエア・ロジックの形態
で実現することも可能である。

【００６７】また、パイプライン化マシンや他の最適化
基準以外の他のコンピュータ・アーキテクチャに対して
本発明を使用することが可能なことも理解されよう。例
えば、ヒューリスチックスがレジスタに対する圧力の低
減を試みる基本ブロック・スケジューラを使用する少数
のレジスタを備えたマシンにおいて使用可能である。

【００６８】 　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　表　　１ｓａｍｐｌｅ（） ｛ 　　　　ｉｎｔ　ｉ，ｃｏｕｎｔ；　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　｜ライン１　　　　ｃｏｕｎｔ＝０；　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　｜ライン２　　　　ｆ
ｏｒ（ｉ＝０；ｉ＜１０；ｉ＋＋）　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
｜ライン３　　　　｛　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　｜ライン４　　　　　　　　　ｉ
ｆ（ｆｕｎｃｔｉｏｎ１（ｉ））　｛ｃｏｕｎｔ　＋＝
　１；｝　　　　　　　　　　　　　　　　｜ライン５
　　　　｝　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　｜ライン６　　　　ｒｅｔｕｒｎ　ｃｏｕｎ
ｔ； ｝ 　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　表　　２　　Ｉ１　　　　　　　　　
ＬＩ　　　　　　　　　ｒ３１＝０　　　　　　　　　
　　　　　　　　　　　　　　　基本ブロックＢ１　　
Ｉ２　　　　　　　　　ＬＲ　　　　　　　　　ｒ３０
＝ｒ３１　　　　　　　　　　　　　　　　　　　　　
　基本ブロックＢ１　　Ｉ３　　　　　　　　　ＣＬ．
０：　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　基本ブロックＢ２　　Ｉ
４　　　　　　　　　ＬＲ　　　　　　　　　ｒ３＝ｒ
３０　　　　　　　　　　　　　　　　　　　　　　　
　　基本ブロックＢ２　　Ｉ５　　　　　　　　　ＣＡ
ＬＬ　　　　　　　ｒ３＝ｆｕｎｃｔｉｏｎ１，１，ｒ
３　　　　　　　　　　　　　　基本ブロックＢ２　　
Ｉ６　　　　　　　　　Ｃ　　　　　　　　　　ｃｒ０
＝ｒ３，０　　　　　　　　　　　　　　　　　　　　
　　　基本ブロックＢ２　　Ｉ７　　　　　　　　　Ａ
Ｉ　　　　　　　　　ｒ３０＝ｒ３０，１　　　　　　
　　　　　　　　　　　　　　　　基本ブロックＢ２　
＋Ｉ８　　　　　　　　　ＢＴ　　　　　　　　　ＣＬ
．３，ｃｒ０，０ｘ４／ｅｑ　　　　　　　　　　　　
　　　　基本ブロックＢ２　＋Ｉ９　　　　　　　　　
ＡＩ　　　　　　　　　ｒ３１＝ｒ３１，１　　　　　
　　　　　　　　　　　　　　　基本ブロックＢ３　＋
Ｉ１０　ＣＬ．３：　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　基本ブロックＢ４　　Ｉ１１　　　　Ｃ　　　　　
　　　　　　　　　ｃｒ１＝ｒ３０，１０　　　　　　
　　　　　　　　　　　　　　　基本ブロックＢ４　　
Ｉ１２　　　　ＢＴ　　　　　　　　　　　　　ＣＬ．
０，ｃｒ１，０ｘ１／１ｔ　　　　　　　　　　　　　
　　　基本ブロックＢ４

【図面の簡単な説明】

【図１】本発明による命令スケジューラの概説用の概略
ブロック図である。

【図２】典型的なフロー・グラフの概略図である。

【符号の説明】

１０　　命令スケジューラ １１　　命令シーケンス入力 １２　　制御フロー・グラフ １３　　前処理ロジック １４　　修正された命令シーケンス １５　　基本ブロック・スケジューラ １６　　一連の再スケジュール命令

Claims (22)

【特許請求の範囲】
1. 【請求項１】　　コンピュータ用の命令スケジューラで
   あって、命令シーケンスにおいて命令スケジューリング
   の目的のため抑制し得る候補となる命令サブシーケンス
   を識別する前処理ロジックと、該前処理ロジックに応答
   して識別された抑制サブシーケンスで命令シーケンスを
   スケジューリングする基本ブロック・スケジューリング
   ・ロジックとを設けることを特徴とする命令スケジュー
   ラ。
2. 【請求項２】　　前記前処理ロジックが、前記命令の基
   本ブロックが制御フローの順序で配列される修正された
   命令シーケンスを生じるように作動し、前記基本ブロッ
   ク・スケジューリング・ロジックが、修正された命令シ
   ーケンスを用いて命令をスケジュールすることを特徴と
   する請求項１記載の命令スケジューラ。
3. 【請求項３】　　前記前処理ロジックが、候補となるサ
   ブシーケンスに対する入口ブロックおよび出口ブロック
   を識別し、前記基本ブロック・スケジューリング・ロジ
   ックが相互に異なる入口ブロック値と出口ブロック値の
   通知に応答して、前記サブシーケンスを１つの疑似命令
   として取扱うことによりサブシーケンスを抑制すること
   を特徴とする請求項１または２記載の命令スケジューラ
   。
4. 【請求項４】　　前記前処理ロジックが前記サブシーケ
   ンスの命令にタグを付け、前記基本ブロック・スケジュ
   ーリング・ロジックがタグを付した命令を単一の疑似命
   令として取扱うことによりこれを抑制することを特徴と
   する請求項１または２記載の命令スケジューラ。
5. 【請求項５】　　前記前処理ロジックが、前記サブシー
   ケンスをセーブしかつその場所に疑似命令を挿入するこ
   とにより該サブシーケンスを抑制し、該疑似命令はこれ
   が置換する命令のレジスタおよびメモリー参照を記録す
   ることを特徴とする請求項１または２記載の命令スケジ
   ューラ。
6. 【請求項６】　　前記修正されたシーケンスのスケジュ
   ーリング後に、前記疑似命令と関連するポインタを用い
   て前記疑似命令をセーブされたサブシーケンスにより置
   換することにより、該疑似命令を拡張する後処理ロジッ
   クを設けることを特徴とする請求項５記載の命令スケジ
   ューラ。
7. 【請求項７】　　前記前処理ロジックが、制御フロー・
   グラフに応答して、一義的な入口と一義的な出口とを有
   しかつ所定の基準を満たすグラフの領域を識別すること
   により、抑制のための候補となるサブシーケンスを識別
   することを特徴とする請求項１乃至６のいずれかに記載
   の命令スケジューラ。
8. 【請求項８】　　入口ｘおよび出口ｙ（ｘ≠ｙ）を有す
   るグラフの領域Ｈに対する所定の基準が、ａ）ｘおよび
   ｙがＨに帰属すること ｂ）（Ｈ−ｘ）の全ての直前のセットは、（Ｈ−ｙ）の
   サブセットであること ｃ）（Ｈ−ｙ）の全ての直後のセットは、（Ｈ−ｘ）の
   サブセットであること ｄ）入口ｘ’および出口ｙ’が（ａ）−（ｃ）を満足し
   、ｘ＝ｘ’あるいはｙ＝ｙ’であるＨのサブセットであ
   る領域Ｈ’は存在しないことを特徴とする請求項７記載
   の命令スケジューラ。
9. 【請求項９】　　前記入口ｘおよび出口ｙが基本ブロッ
   クであり、領域Ｈに対する候補となるサブシーケンスが
   、−もし分岐ならば、入口ブロックｘの最後の命令−存
   在するならば、出口ブロックｙの先頭のラベル、および −Ｈの全ての残るブロックにおける全ての命令を含むこ
   とを特徴とする請求項８記載の命令スケジューラ。
10. 【請求項１０】　　前記前処理ロジックが、抑制される
    複数の候補となるサブシーケンスを識別するために命令
    シーケンスについて反復的に作動することを特徴とする
    請求項１乃至９のいずれかに記載の命令スケジューラ。
11. 【請求項１１】　　請求項１乃至９のいずれかに記載の
    如き命令スケジューラを設けてなることを特徴とするコ
    ンピュータ用コンパイラ。
12. 【請求項１２】　　請求項１乃至１０のいずれかに記載
    の如き命令スケジューラを設けてなることを特徴とする
    コンピュータ。
13. 【請求項１３】　　コンピュータにおける命令をスケジ
    ュールする方法であって、 ａ）命令シーケンスにおいて、命令スケジューリングの
    目的のため抑制し得る候補となる命令サブシーケンスを
    識別し、 ｂ）基本ブロック・スケジューリング・ロジックを用い
    て、識別された抑制サブシーケンスで前記命令シーケン
    スをスケジュールするステップを含むことを特徴とする
    方法。
14. 【請求項１４】　　前記ステップ（ａ）が、命令の基本
    ブロックが制御フローの順序で配列される修正された命
    令シーケンスを生じ、前記ステップ（ｂ）において、命
    令が修正された命令シーケンスを用いてスケジュールさ
    れることを特徴とする請求項１３記載の方法。
15. 【請求項１５】　　前記ステップ（ａ）が、候補となる
    サブシーケンスに対する入口ブロックと出口ブロックを
    識別することを含み、前記ステップ（ｂ）が、相互に異
    なる入口ブロック値および出口ブロック値の通知に応答
    して、前記サブシーケンスを１つの疑似命令として取扱
    うことにより該サブシーケンスを抑制することを含むこ
    とを特徴とする請求項１３または１４に記載の方法。
16. 【請求項１６】　　前記ステップ（ａ）が、前記サブシ
    ーケンスの命令にタグを付すことを含み、前記ステップ
    （ｂ）が、前記タグを付した命令を単一の疑似命令とし
    て取扱うことにより該命令を抑制することを含むことを
    特徴とする請求項１３または１４に記載の方法。
17. 【請求項１７】　　前記ステップ（ａ）が、−識別され
    たサブシーケンスをセーブし、−置換する命令のレジス
    タおよびメモリー参照を記録する疑似命令をその代わり
    に挿入するサブステップを含むことを特徴とする請求項
    １３または１４に記載の方法。
18. 【請求項１８】　　ｃ）前記修正された命令シーケンス
    のスケジューリング後に、前記疑似命令と関連するポイ
    ンタを用いて前記セーブされたサブシーケンスをアクセ
    スして該セーブされたサブシーケンスにより前記疑似命
    令を置換することにより、疑似命令を拡張する、後続ス
    テップを含むことを特徴とする請求項１７記載の方法。
19. 【請求項１９】　　抑制される候補となるサブシーケン
    スの前記識別ステップが、入力命令シーケンスに対する
    制御フロー・グラフの領域を識別することを含み、該領
    域は、一義的な入口および一義的な出口を有して所定の
    基準を満たすことを特徴とする請求項１３乃至１８のい
    ずれかに記載の方法。
20. 【請求項２０】　　入口ｘおよび出口ｙ（ｘ≠ｙ）を有
    するグラフの領域Ｈに対する所定の基準が、ａ）ｘおよ
    びｙがＨに帰属すること ｂ）（Ｈ−ｘ）の全ての直前のセットは、（Ｈ−ｙ）の
    サブセットであること ｃ）（Ｈ−ｙ）の全ての直後のセットは、（Ｈ−ｘ）の
    サブセットであること ｄ）入口ｘ’および出口ｙ’が（ａ）−（ｃ）を満足し
    、ｘ＝ｘ’あるいはｙ＝ｙ’であるＨのサブセットであ
    る領域Ｈ’は存在しないことを特徴とする請求項１９記
    載の方法。
21. 【請求項２１】　　前記入口ｘおよび出口ｙが基本ブロ
    ックであり、領域Ｈに対する候補となるサブシーケンス
    が、 −もし分岐ならば、入口ブロックｘの最後の命令−存在
    するならば、出口ブロックｙの先頭のラベル、および −Ｈの全ての残るブロックにおける全ての命令を含むこ
    とを特徴とする請求項２０記載の方法。
22. 【請求項２２】　　前記ステップ（ａ）が、抑制される
    複数の候補となるサブシーケンスを識別するため反復的
    に行われることを特徴とする請求項１３乃至２１のいず
    れかに記載の方法。