(57)【要約】      （修正有）【課題】第１の命令ストリーム内にスーパブロックを作成するスーパブロック・アンローラを提供する。【解決手段】スーパブロック・アンローラは、スーパブロックの反復の数が十分に少ない場合及びその反復の数がコンパイル時にわかっている場合、完全アンローリングを使用する。スーパブロック・アンローラは、スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及びその反復の数がコンパイル時にわかっている場合、静的アンローリングを使用する。スーパブロック・アンローラは、スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する。これらのアンローリング方法の各々は、スーパブロックを抜け出す実行を明確にする（account for）ために、カウント修正コード（count rectification code）を第１の命令ストリームに挿入することを含み得る。。【選択図】図１
2004152287.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに結合されたメモリと、
前記メモリ内にある第１の命令ストリームと、
前記メモリ内にあり、前記少なくとも１つのプロセッサによって実行されるプロファイル・ベースのスーパブロック・アンローラと、
を含み、
前記スーパブロック・アンローラは、プロファイル・データに従って前記第１の命令ストリームにおいてスーパブロックを形成及びアンロールし、実行が該スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含む、
装置。
【請求項２】
前記スーパブロック・アンローラによって遂行されるアンローリングのタイプが完全アンローリング、静的アンローリング、および動的アンローリングを含む、請求項１に記載の装置。
【請求項３】
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用する、請求項１に記載の装置。
【請求項４】
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、静的アンローリングを使用する、請求項１に記載の装置。
【請求項５】
前記スーパブロック・アンローラは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、請求項１に記載の装置。
【請求項６】
前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外で前記第１の命令ストリームに挿入する、請求項１に記載の装置。
【請求項７】
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに結合されたメモリと、
前記メモリ内にある第１の命令ストリームと、
前記メモリ内にあり、前記少なくとも１つのプロセッサによって実行されるプロファイル・ベースのスーパブロック・アンローラと、
を含み、
前記スーパブロック・アンローラは、プロファイル・データに従って前記第１の命令ストリームにおいてスーパブロックを形成及びアンロールし、実行が該スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含み、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用し、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、静的アンローリングを使用し、
前記スーパブロック・アンローラは、前記反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、
装置。
【請求項８】
前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外で前記第１の命令ストリームに挿入する、請求項７に記載の装置。
【請求項９】
第１の命令ストリームを最適化するための方法であって、
プロファイル・データに従って、前記第１の命令ストリームにおいてスーパブロックを作成するステップと、
前記スーパブロックをアンロールするステップと、
少なくとも１つのカウンタ値を調節して前記スーパブロックからの出口を明確にするために、必要な場合、前記スーパブロックの外にカウント・レクティファイア・コードを提供するステップと、
を含む方法。
【請求項１０】
前記スーパブロックをアンロールするステップは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの完全アンローリングを遂行するステップを含む、請求項９に記載の方法。
【請求項１１】
前記スーパブロックをアンロールするステップは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの静的アンローリングを遂行するステップを含む、請求項９に記載の方法。
【請求項１２】
前記スーパブロックをアンロールするステップは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、前記スーパブロックの動的アンローリングを遂行するステップを含む、請求項９に記載の方法。
【請求項１３】
第１の命令ストリームを最適化するための方法であって、
プロファイル・データに従って、前記第１の命令ストリームにおいてスーパブロックを作成するステップと、
前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの完全アンローリングを遂行するステップと、
前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの静的アンローリングを遂行するステップと、
前記スーパブロックの反復の数がコンパイル時にわかっていない場合、前記スーパブロックの動的アンローリングを遂行するステップと、
少なくとも１つのカウンタ値を調節して前記スーパブロックからの出口を明確にするために、必要な場合、前記スーパブロックの外にカウント・レクティファイア・コードを提供するステップと、
を含む方法。
【請求項１４】
（Ａ）プロファイル・データに従って第１の命令ストリームにおいてスーパブロックを形成及びアンロールするプロファイル・ベースのスーパブロック・アンローラと、
（Ｂ）前記プロファイル・ベースのスーパブロック・アンローラを保持するコンピュータ可読信号保持媒体と、
を含み、
前記スーパブロック・アンローラは、実行が前記スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含む、
コンピュータ・プログラム。
【請求項１５】
前記コンピュータ可読信号保持媒体は記録可能媒体を含む、請求項１４に記載のコンピュータ・プログラム。
【請求項１６】
前記コンピュータ可読信号保持媒体は伝送媒体を含む、請求項１４に記載のコンピュータ・プログラム。
【請求項１７】
前記スーパブロック・アンローラによって遂行されるアンローリングのタイプは、完全アンローリング、静的アンローリング、及び動的アンローリングを含む、請求項１４に記載のコンピュータ・プログラム。
【請求項１８】
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用する、請求項１４に記載のコンピュータ・プログラム。
【請求項１９】
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記静的アンローリングを使用する、請求項１４に記載のコンピュータ・プログラム。
【請求項２０】
前記スーパブロック・アンローラは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、請求項１４に記載のコンピュータ・プログラム。
【請求項２１】
前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外に前記第１の命令ストリームに挿入する、請求項１４に記載のコンピュータ・プログラム。
【請求項２２】
（Ａ）プロファイル・データに従って第１の命令ストリームにおいてスーパブロックを形成及びアンロールするプロファイル・ベースのスーパブロック・アンローラと、
（Ｂ）前記プロファイル・ベースのスーパブロック・アンローラを保持するコンピュータ可読信号保持媒体と、
を含み、
前記スーパブロック・アンローラは、実行が前記スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含み、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用し、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記静的アンローリングを使用し、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、
コンピュータ・プログラム。
【請求項２３】
前記コンピュータ可読信号保持媒体は記録可能媒体を含む、請求項２２に記載のコンピュータ・プログラム。
【請求項２４】
前記コンピュータ可読信号保持媒体は伝送媒体を含む、請求項２２に記載のコンピュータ・プログラム。
【請求項２５】
前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外に前記第１の命令ストリームに挿入する、請求項２２に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して言えば、コンピュータ・システムに関し、詳しく言えば、コンピュータ・システムのための実行可能なコードを生成するコンパイラに関するものである。
【背景技術】
【０００２】
コンピュータ時代の幕開け以来、コンピュータ・システムは極めて精巧な装置に進化してきたし、多くの種々な設定を持つコンピュータ・システムを見ることができる。ハードウェア及びソフトウェア（例えば、コンピュータ・プログラム）の両方における劇的な進歩は、コンピュータ・システムのパフォーマンスを劇的に改善した。最新のソフトウェアは、初期のコンピュータ・プログラムに比べると、非常に複雑になっている。多くの最新のコンピュータ・プログラムは、数万又は数十万個の命令を有する。コンピュータ・プログラムの実行時間（従って、パフォーマンス）は、コンピュータ・プログラムが稼動しているときに実行される命令の数に非常に密接に関連している。従って、コンピュータ・プログラムのサイズ及び複雑さが増すにつれて、コンピュータ・プログラムの実行時間も増加する。
【０００３】
初期のコンピュータ・プログラムとは違って、最新のコンピュータ・プログラムは、一般に、人間のプログラマが理解するに容易な高レベル言語で書かれる。コンパイラとして知られた特別のソフトウェア・ツールは、「ソース・コード」として知られている、人間が理解できるコンピュータ・プログラム形式を取り、それを、コンピュータ・システムによる実行可能な「マシン・コード」命令又は「オブジェクト・コード」命令に変換する。コンパイラは、最終的にはコンピュータ・システムにおいて実行されるマシン・コード命令のストリームを生成するので、コンパイラがソース・コードをオブジェクト・コードに変換する手法は、コンピュータ・プログラムの実行時間に影響を与える。
【０００４】
コンピュータ・プログラムの実行時間、特に、複雑なコンピュータ・プログラムのそれは、そのコンピュータ・プログラムにおける命令の配列及びタイプの関数である。ループは、コンピュータ・プログラムの実行時間に影響を与える。コンピュータ・プログラムが多くのループを含む場合、又は比較的多くの回数にわたって実行される何らかのループを含む場合、ループの実行に費やされる時間は、コンピュータ・プログラムの実行時間にかなりのインパクトを与えるであろう。
【０００５】
最新のコンピュータ・プログラムのパフォーマンスを最適化するために、コンピュータ・プログラムのランタイム・パフォーマンスを予測及び（又は）測定するためのプロファイラ（profiler）が開発された。プロファイラは、一般に、コンピュータ・プログラムの種々の部分が如何に頻繁に実行されるかを見積もるプロファイル・データを生成する。プロファイル・データを使用して、オプティマイザ（最適化コンパイラのような）が、コンピュータ・プログラムの実行速度を改善するために、そのコンピュータ・プログラム内のループを最適化するよう決定することも可能である。
【０００６】
コンピュータ・プログラムにおけるループを最適化するためにプロファイル・データを使用するための既知の方法は、最適な解決方法を提供するものではない。その結果、従来技術は、コンピュータ・プログラムに対してより遅い実行時間を結果として生じるループにおいて非効率をもたらすことがある。コンピュータ・プログラムにおけるループを最適化する改良された装置及び方法がなければ、コンパイラは、それが成し得るほど十分には最適化されないコンピュータ・プログラムを生成するであろう。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明により、スーパブロック・アンローラが提供される。スーパブロック・アンローラは、第１の命令ストリーム内にスーパブロックを作成し、種々のタイプのアンロールに適したそれぞれの方法を使用してそのスーパブロックをアンロールする。
【課題を解決するための手段】
【０００８】
望ましい実施例によれば、スーパブロック・アンローラは、スーパブロックの反復の数が十分に少ない場合、及びその反復の数がコンパイル時にわかっている場合、完全アンローリングを使用する。スーパブロック・アンローラは、スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及びその反復の数がコンパイル時にわかっている場合、静的アンローリングを使用する。スーパブロック・アンローラは、スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する。これらのアンローリング方法の各々は、スーパブロックを抜け出す実行を明確にする（account for）ために、カウント修正コード（count rectification code）を第１の命令ストリームに挿入することを含み得る。本願において開示されるスーパブロックの精巧なアンローリングを行うことによって、コード・パフォーマンスを改善することが可能である。
【０００９】
本発明の上記の及びその他の特徴は、添付図面に示された本発明の望ましい実施例に関する以下のより詳細な説明から明らかであろう。
【発明を実施するための最良の形態】
【００１０】
１.０概要
本発明は、コンピュータ・プログラムにおけるループの最適化に関するものである。コンパイラ或いは既知のループ最適化方法に精通していない人にとって、この概要項は本発明の理解を助ける背景情報を提供するであろう。
【００１１】
Ａ．既知のコンパイラ
図２は、フロントエンド・コンパイラ２１０及びバックエンド・コンパイラ２２０を含む従来技術のコンパイラ・システム２００を示す。ほとんどの既知のコンパイラに関して、フロントエンド・コンパイラ２１０及びバックエンド・コンパイラ２２０の間にアーキテクチャ上の分離（破線２６０によって表される）が存在する。フロントエンド・コンパイラ２１０は、ソース・コード２０５を中間表現コード２１５に変換するために使用される。バックエンド・コンパイラ２２０は、中間表現コード２１５を特定のハードウェア構成（即ち、プラットフォーム）のためのマシン・コード２２５に変換するために使用される。フロントエンド・コンパイラ及びバックエンド・コンパイラの間のこのようなアーキテクチャ上の分離は効果的である。というのは、多くの異なる言語（例えば、Ｃ++、Ｊａｖａ（登録商標）、Ａｄａ等）に対するフロントエンド・コンパイラを、あるプラットフォーム（例えば、ＩＢＭ  iSeries）に対する単一のバックエンド・コンパイラと共に使用できるからである。同様に、Ｊａｖａプログラミング言語に対する単一のフロントエンド・コンパイラは、そのコードが種々のプラットフォームにおいて実行するようコンパイルされる必要がある場合、複数のバックエンド・コンパイラと共に使用され得る。
【００１２】
フロントエンド・コンパイラ２１０はＩＲコード・ジェネレータ２１２を含み、そのコード・ジェネレータは、ソース・コード２０５を処理し、中間表現コード２１５で記述される命令を生成する。バックエンド・プロセッサ２２０はマシン・コード・ジェネレータ２２２を含み、そのマシン・コード・ジェネレータは、中間表現コード２１５を処理し、特定のプラットフォームにおいて実行可能なマシン・コード２２５を生成する。バックエンド・コンパイラ２２０は、マシン・コード２２５がサンプル入力のセットを用いて実行されるときにプロファイル・データ２２６を得るために使用されるプロファイラ２２４も含む。本願において使用される「サンプル入力」という用語は、マシン・コードが意図した環境におけるマシン・コードの現実世界での実行をシミュレートする入力を意味する。マシン・コード・ジェネレータ２２２は、プロファイル・データ２２６に従って中間表現コード２１５の２度目の処理を行うことによってマシン・コード２２５を最適化するようにプロファイル・データ２２６を使用することができる。
【００１３】
図３は、図２における従来技術のコンパイル・システム２００を使用してソース・コードをコンパイルするための従来技術の方法３００に関する流れ図である。先ず、フロントエンド・コンパイラがソース・コードを中間表現（ＩＲ）コードに変換する（ステップ３１０）。次に、バックエンド・コンパイラが中間表現コードを処理して、インスツルメンテーション・コードをマシン・コードに挿入する（ステップ３２０）。インスツルメンテーション・コードは、典型的にはカウンタをインクリメントするコードであって、マシン・コード２２５が、そのマシン・コードを実行するための現実世界環境をシミュレートするように設計された入力のサンプル・セットを用いて実行されるとき、マシン・コード２２５内の各ブランチが何回実行されるか及び実行されないかの比をトレースするためにカウンタをインクリメントするコードである。一旦インスツルメンテーション・コードがマシン・コード２２５に挿入されると、サンプル入力を使用して、インスツルメント済みプログラム（即ち、マシン・コード）が実行され、その実行に関するプロファイル・データが収集される（ステップ３３０）。インスツルメント済みコードの場合、プロファイル・データは、マシン・コードにおける各ブランチに対するカウント値から成る。そのカウント値は、ブランチが実行された回数と実行されなかった回数の比を表す。そして、コンピュータ・プログラムの最適化を機能強化するためにプロファイル・データを適用して、バックエンド・コンパイラがＩＲコードをマシン・コードに変換する（ステップ３４０）。プロファイルに基づく最適化は、一般に、バックエンド・コンパイラにおいて行われることを、図２及び図３から留意してほしい。しかし、プロファイル・ベースの最適化は、リンク・タイム・オプティマイザ（link-time optimizer）によっても遂行され得るし、或いは、プログラムの実行中ではオン・ザ・フライで遂行され得る。
【００１４】
図３の方法３００において、ステップ３２０では、プロファイラがインスツルメンテーション・コードをマシン・コードに挿入することになっている。しかし、プロファイルは、プログラムの実行を定期的に停止して現在のアドレスを決定するために、オペレーティング・システムにおけるタイム・ベースの割り込みを使用するサンプリングを介しても生じ得ることに留意してほしい。サンプリングは、インスツルメンテーション・コードの挿入を必要とせず、プロファイル・データを収集するための別の既知の方法である。一般に、サンプリングは、インスツルメンテーション・コードを挿入することよりも煩わしくないが、それに対応して精度が低くなる。サンプリングは、どのブロックのコードが頻繁に実行されるかを識別することに限定されるが、一般には、頻繁に実行されたブロックに達するためにどのブランチが実行されたかを表さない。
【００１５】
この分野では、プロファイル・データを得るための、及びプロファイル・データを使用してコードを最適化するための多くの方法が知られている。プロファイル・データを使用してコードを最適化するための１つの特定な方法に関する一般的な説明に対しては、IBM Systems Journal 誌の Vol.37、No.2、p.270-297 (1998) における「Profile-DirectedRestructuring of Operating System Code」と題した Schmidt 氏他による論文を参照してほしい。
【００１６】
プロファイル・データに従ってループを最適化するための従来技術における１つの既知の方法は、ループ・アンローリング（loop unrolling）である。それは、ループに入る度に何回も反復することが予想されるループにおいて使用される技法である。ループの本体は、本体自体のＮ個のコピーによって置換される。この場合、Ｎは、ヒューリスティックに決定されたアンロール係数である。最後の反復が最初の反復をターゲットとするように変更されるので、Ｎ個のコピーが一緒になって展開されたループを形成する。アンロール反復がそのループ内で最適化され得る。
【００１７】
ループを最適化するために本分野で使用される１つの技法はスーパブロック（superblock）を形成する。スーパブロックは、サイド・エントランス、即ち、結合ポイントを持たないコードの一部分である。スーパブロックの形成は、当初、大きなブロックのコードにわたって多くの命令レベルの並列性を見つけるために開発された。スーパブロック形成の背後にある本質的な観念は、コードを複製することによって「ホット」コード・トレースから結合ポイントを除去することである。スーパブロック形成は、Journalof Supercomputing 誌、７、229-248 (1993) における「The Superblock: An Effective Techniquefor VLIW and Superscalar Compilation」と題した Hwu 氏他による論文に詳しく説明されている。
【００１８】
ループ・アンローリングの従来技術の概念は、スーパブロック・ループに適用されている。しかし、スーパブロック・ループに対する既知のループ・アンローリングは、単純なアンローリングに限定されている。図４を参照すると、従来技術の方法４００は、テール複写（tail duplication）を使用してループ・アンローリングのためのスーパブロックを形成することによって開始する（ステップ４１０）。テール複写という概念は、更に詳細に後述される。一旦、ステップ４１０においてスーパブロックが形成されると、方法４００は、そのスーパブロックがアンローリングにとって好適なものであるかどうかを決定する（ステップ４２０）。それが否定される場合（ステップ４２０＝ＮＯ）、方法４００は終了する。それが肯定される場合（ステップ４２０＝ＹＥＳ）、単純なアンロールがそのスーパブロックに関して遂行される（ステップ４３０）。図４におけるステップを説明するために、次に１つの例を示す。
【００１９】
コンピュータ・プログラムにおけるループのためのサンプル制御フローが図５に示される。ブロックＰＨは、そのループに先行する「プリヘッダ（pre-header）」ブロックであり、ブロックＰＥは、そのループに後続する「ポスト・エグジット（post-exit）」ブロックであり、そしてブロックＡ、Ｂ、Ｃ、Ｄ、Ｅ及びＦは、そのループのメンバである。プロファイル・データが、パスＡ−Ｃ−Ｄ−Ｆが実行時に圧倒的に主要なパス（図５における太い矢印によって示される）であることを示すが、ブロックＤ及びＦの両方において結合ポイントが存在するものとしよう。上記Hwu 氏他によって教示されたテール複写を適用すると、図６に示されるように、第１結合ポイントに続くトレースにおいてブロックのコピーが作成される。ブロックＤ’及びＦ’の導入は、トレースＡ−Ｃ−Ｄ−Ｆが結合ポイントなしで存在することを可能にし、更なる最適化を可能にする。例えば、ブロックＣ及びＤからの命令は共に最適化され得るが、以前、これは可能ではなかった。スーパブロック形成は、最もホットなループ・トレースからの結合ポイントの除去の結果、プログラム・パフォーマンスにおけるかなりの改善が生じ得る場合、ループでは特に有用である。
【００２０】
一旦、スーパブロックがループにおいて識別されると、そのスーパブロックが完全なループ反復を構成する場合、従来技術はそのスーパブロックの単純なアンローリングを遂行するだろう。単純なアンローリングは、種々のループ反復を通して最適化の機会の発見を可能にするためにスーパブロック自体が１回又は複数回複写され得ることを意味する。各反復は結合ポイントを含まないので、これは、図７に示されるように、結合ポイントを含まない更に大きなスーパブロックに通じる。なお、図６におけるスーパブロックは３回アンロールされた。
【００２１】
従来技術の方法による１つの問題点は、スーパブロックをアンロールために単純なアンローリングしか使用されないということである。単純なアンローリングは、ループに入ったときにスーパブロックがどの程度の回数実行されるかを決定しない。従って、インダクション条件（induction condition）（例えば、１を減じ、ゼロに比較し、等しければブランチする）は、ループ・トレースの各コピーの末端部に複写される。従って、図７において、ブロックＦの各コピー、即ち、Ｆ１、Ｆ２、Ｆ３、及びＦ’が、ブロックＰＥへの可能な出口を有する。しかし、ループがどの程度の回数実行されるかがわかっている場合が多い。例えば、フォーム「for(i=0;i<5;i++){...}」は、まさに５回実行するであろう。この場合、ブロックＥのすべてのコピーがインダクション条件及びブランチを含む必要があるわけではない。しかし、本分野では知られている図７に示されたようなスーパブロックの単純なアンローリングはこれを認識しない。その結果、従来技術において実施可能であった幾つかの最適化も現在では行われていない。
【００２２】
（スーパブロック・アンローリングとは対照的にフル・ループ・アンローリングにとっては一般的な）不必要なインダクション条件及びブランチを含む命令を除去することによる利益を従来技術が利用しない理由は、スーパブロック・トレースから早いうちに分岐する枝（arc）に伴なう問題のためである。ブロックＦの最後のコピー（Ｆ３）がブロックＡ１においてそのループのトップに戻るのみならず、テール複写されたブロックＦ’もトップに戻る。ブロックＦ’自体は、インダクション条件のコピーも含む。インダクション条件がスーパブロック・トレースから除去されたがテール複写されたブロックからは除去されなかった場合、テール複写されたブロックにおけるループ終了は正しく実行しないであろう。更に、アンロール・スーパブロックがブロックＦ’から枝を介してブロックＡ１において再突入する場合、残りの反復の数は正しくないだろう。本発明による望ましい実施例は、いつも正しい結果を生じながらより高いレベルの最適化を可能にする更に精巧な方法においてスーパブロックのアンローリングを可能にするために、必要な場合にカウント修正を行うスーパブロックをアンロールするための更に進歩した方法を提供する。
【００２３】
２.０  詳細な説明
望ましい実施例は、ループ内のホット・パスにおける結合ポイントを排除するようにそのループ内のスーパブロックをアンロールすることによって強力なループ最適化を行うコンパイラを提供する。スーパブロックのより良好な最適化を可能にするために、１つ又はそれ以上の命令を、少ない頻度で実行されるパスに加えてもよい。これらの付加的な命令は、スーパブロックにおけるホット・トレースを実行する代わりに、ループの末尾部分に入る時と抜け出す時を考慮するカウント修正を行う。ループの少ない頻度で実行される部分における命令を犠牲にして、より精巧なアンローリング基準及び方法を提供することによって、ループの全体的なパフォーマンスが高められる。
【００２４】
次に図１を参照すると、コンピュータ・システム１００は、本発明の望ましい実施例による装置の１つの適当なインプリメンテーションである。コンピュータ・システム１００は、IBM iSeries コンピュータ・システムである。しかし、コンピュータ・システムが複雑なマルチユーザ・コンピューティング装置、シングルユーザ・ワークステーション、又は組込み型制御システムであるかどうかに関係なく、如何なるコンピュータ・システムにも等しく本発明が適用されることは、当業者には明らかであろう。図１に示されるように、コンピュータ・システム１００は、プロセッサ１１０、メイン・メモリ１２０、大容量記憶装置インターフェース（ＩＦ）１３０、ディスプレイ・インターフェース１４０、及びネットワーク・インターフェース１５０を含む。これらのシステム・コンポーネントは、システム・バス１６０を用いて相互接続される。大容量記憶装置インターフェース１３０は、大容量記憶装置（ダイレクト・アクセス・ストレージ装置（ＤＡＳＤ）１５５のような）をコンピュータ・システム１００に接続するために使用される。１つの特定なタイプのダイレクト・アクセス・ストレージ装置１５５は、ＣＤ−ＲＷ１９５にデータを記憶し、ＣＤ−ＲＷ１９５からデータを読み出し得る読み取り可能且つ書き込み可能ＣＤ−ＲＷドライブである。
【００２５】
望ましい実施例によるメイン・メモリ１２０は、データ１２１、オペレーティング・システム１２２、ソース・コード１２３、中間表現コード１２４、プロファイル・データ１２５、コンパイラ１２６、及びマシン・コード１２９を含む。データ１２１は、コンピュータ・システム１００における任意のプログラムへの入力又は任意のプログラムからの出力となる任意のデータを表す。オペレーティング・システム１２２は、本業界ではＯＳ／４００として知られているマルチタスキング・オペレーティング・システムである。しかし、本発明の精神及び技術範囲がいずれか１つのオペレーティング・システムに限定されるものではないことは、当業者には明らかであろう。ソース・コード１２３は、高レベル言語で書かれたコンピュータ・プログラム又はそれの一部分である。中間表現コード１２４は、フロントエンド・コンパイラによってソース・コード１２３から生成される中間的なコードである。なお、このフロントエンド・コンパイラは、コンパイラ１２６の一部分であってもよく、或いは図１には示されてない別のコンパイラであってもよい。プロファイル・データ１２５は、インスツルメント・プロファイラ（instrumenting profiler）及びサンプリング・プロファイラを含むがこれには限定されない任意の適当なプロファイリング方法によって収集されたデータである。プロファイル・データ１２５は、ブランチが行われる回数のカウントを含むのが相応しい。コンパイラ１２６は、プロファイル・データ１２５に従って中間表現コード１２４におけるコードを最適化するスーパブロック・アンローラ１２７を含む。スーパブロック・アンローラ１２７は、実行がスーパブロックに入る又はそこから抜け出すときに、ループ・カウンタに必要な変更を行うカウント・レクティファイア（countrectifier）１２８を含む。プロファイル・データ１２５を生成するプロファイラが図１には明瞭に示されてないが、コンパイラ１２６の一部であるものと仮定することに留意してほしい。マシン・コード１２９は、中間表現コード１２４からコンパイラ１２６によって生成された実行可能コードである。
【００２６】
ソース・コード１２３、中間表現コード１２４、プロファイル・データ１２５、コンパイラ１２６、及びマシン・コード１２９が、それらの構成要素すべてを１つの図面に示す都合上、すべてメモリ１２０内にあるものとして示されているということに留意してほしい。ほとんどのコンパイラにおいてこれが通常のオペレーション・モードではないことは、当業者には明らかであろう。フロントエンド・コンパイラは、ソース・コード１２３を処理し、そこから中間表現コード１２４を生成してもよい。この処理が、コンピュータ・システム１００とは別のコンピュータ・システムにおいて行われてもよい。そして、プロファイラは、インスツルメンテーション・コードを中間表現コード１２４に挿入し、別のコンピュータ・システムにおいてインスツルメントされたコードを実行してプロファイル・データ１２５を収集してもよい。コンパイラ１２６は、中間表現コード１２４を処理し、そこからマシン・コード１２９を生成する。なお、そのマシン・コードを、別のコンピュータ・システムにおいて生じさせることも可能である。極端な例では、ソース・コード１２３が第１のコンピュータ・システムに存在してもよい。フロントエンド・コンパイラが第２のコンピュータ・システムに存在してもよい。フロントエンド・コンパイラは、第１のコンピュータ・システムからソース・コード１２３を読み取り、中間表現コード１２４を生成し、そして第３のコンピュータ・システム内にその中間表現コード１２４を記憶することができるであろう。そして、プロファイラは、第３のコンピュータ・システムから中間表現コード１２４を読み取り、インスツルメンテーション・コードを挿入し、そしてそのインスツルメントされたコードを第４のコンピュータ・システムに記憶し得る。そこで、プロファイラは、そのインスツルメントされたコードを第４のコンピュータ・システムから読み取り、そのインスツルメントされたコードを第５のコンピュータ・システムにおいて実行し、そしてその結果生じたプロファイル・データを第６のコンピュータ・システムに記憶する。コンパイラ１２６は、第７のコンピュータ・システムにおいて実行され得る。第７のコンピュータ・システムは、第３のコンピュータ・システムから中間表現コード１２４を、及び第６のコンピュータ・システムからプロファイル・データを読み取り、そこからマシン・コード１２９を生成する。そのマシン・コードは、第８のコンピュータ・システムに書き込み可能である。この簡単な例は、フロントエンド及びバックエンド・コンパイリングを達成するために、望ましい実施例が任意の適当な構成及び数のコンピュータ・システムに拡張することが明らかであることを示す。本願明細書及び特許請求の範囲において記述された発明の主題である「装置（apparatus）」が上記の例によって説明されるように、複数コンピュータの構成に拡張し得ることは明らかである。
【００２７】
コンピュータ・システム１００は、周知の仮想アドレシング機構を利用して、そのコンピュータ・システム１００のプログラムが、メイン・メモリ１２０及びＤＡＳＤ装置１５５のような複数の小型ストレージ・エンティティへアクセスする代わりにあたかも単一の大型ストレージ・エンティティへのアクセスだけを有するようにすることができる。従って、データ１２１、オペレーティング・システム１２２、ソース・コード１２３、中間表現コード１２４、プロファイル・データ１２５、コンパイラ１２６、及びマシン・コード１２９がメイン・メモリ１２０に存在するように示されているけれども、これらのアイテムが必ずしもメイン・メモリ１２０内にすべて完全に含まれているのではないことは当業者には明らかであろう。更に、用語「メモリ」が、本願明細書ではコンピュータ・システム１００の仮想メモリ全体を一般的に指すために使用され、しかもコンピュータ・システム１００に結合された他のコンピュータ・システムの仮想メモリを含み得ることも留意すべきである。
【００２８】
プロセッサ１１０は、１つ又はそれ以上のマイクロプロセッサ及び（又は）集積回路から構成され得る。プロセッサ１１０は、メイン・メモリ１２０に記憶されたプログラム命令を実行する。メイン・メモリ１２０は、プロセッサ１１０がアクセスし得るプログラム及びデータを記憶する。コンピュータ・システム１００が始動するとき、プロセッサ１１０は、先ず、オペレーティング・システム１２２を形成するプログラム命令を実行する。オペレーティング・システム１２２は、コンピュータ・システム１００のリソースを管理する精巧なプログラムである。これらのリソースの幾つかは、プロセッサ１１０、メイン・メモリ１２０、大容量ストレージ・インターフェース１３０、ディスプレイ・インターフェース１４０、ネットワーク・インターフェース１５０、及びシステム・バス１６０である。
【００２９】
コンピュータ・システム１００が単一のプロセッサ及び単一のシステム・バスのみを含むように示されているけれども、複数のプロセッサ及び（又は）複数のバスを有するコンピュータ・システムを使用して本発明が実施され得ることは、当業者には明らかであろう。更に、望ましい実施例において使用されるインターフェースは、それぞれ、プロセッサ１１０から計算集中処理をオフロード（off-load）するために使用される分離した且つ完全にプログラムされたマイクロプロセッサを含む。しかし、本発明が、同様な機能を遂行するようにＩ／Ｏプロセッサを使用するだけのコンピュータ・システムに同様に適用することも当業者には明らかであろう。
【００３０】
ディスプレイ・インターフェース１４０は、１つ又は複数のディスプレイ１６５をコンピュータ・システム１００に直接に接続するために使用される。非インテリジェント（即ち、ダム）端末装置又は完全にプログラム可能なワークステーションでもよいディスプレイ１６５は、システム管理者及びユーザがコンピュータ・システム１００とコミュニケーションを行うことを可能にするために使用される。しかし、ディスプレイ・インターフェース１４０は１つ又はそれ以上のディスプレイ１６５とのコミュニケーションをサポートするために提供されるけれども、コンピュータ・システム１００は、ユーザ及び他のプロセスとのすべての必要な相互作用がネットワーク・インターフェース１５０を介して生じ得るので、必ずしもディスプレイ１６５を必要としない。
【００３１】
ネットワーク・インターフェース１５０は、ネットワーク１７０を介してコンピュータ・システム１００に他のコンピュータ・システム及び（又は）ワークステーション（例えば、図１における１７５）を接続するために使用される。如何ようにコンピュータ・システム１００が他のコンピュータ・システム及び（又は）ワークステーションに接続されようとも、ネットワーク接続１７０が、現在のアナログ及び（又は）ディジタル技法を使用して或いは将来の何らかのネットワーキング機構を介して行われるかどうかに関係なく、本発明は等しく適用可能である。更に、ネットワークをイプリメントするために、多くの種々なネットワーク・プロトコルが使用され得る。これらのプロトコルは、コンピュータがネットワーク接続１７０を介してコミュニケーションを行うことを可能にする特殊なコンピュータ・プログラムである。ＴＣＰ／ＩＰ（伝送制御プロトコル／インターネット・プロトコル）は、適当なネットワーク・プロトコルの一例である。
【００３２】
この時点で重要なことは、十分に機能的なコンピュータ・システムに関連して本発明を説明したし、以後も説明を続けるけれども、本発明がプログラム製品として種々の形式で配布され得ること、及び実際にその配布を行うために使用される特定のタイプの信号保持媒体に関係なく、本発明が同様に適用することが当業者には明らかであろうということに留意することである。適当な信号保持媒体の例は、フロッピ・ディスク及びＣＤ−ＲＷ（例えば、図１における１９５）のような記録可能なタイプの媒体、及びディジタル及びアナログ通信リンクのような伝送タイプの媒体を含む。
【００３３】
スーパブロック・アンローラ１２７によって遂行される機能に説明を移す。なお、その機能は図８乃至図２３に示される。スーパブロック・アンローラ１２７内のカウント・レクティファイア１２８は、ループ・カウンタがループ内の考え得る各実行パスに対する正しい値を有することを保証する。そこで、図８を参照すると、望ましい実施例による方法８００は、従来技術において行われたタイプよりも多くのタイプのスーパブロックのアンローリングを可能にする。先ず、スーパブロックは、図４の従来技術の方法４００におけるステップと同じステップであるテール複写を使用して形成される（ステップ４１０）。そのスーパブロックがアンローリングにとって好適なものではない場合（ステップ４２０＝ＮＯ）、方法８００が行われる。そのスーパブロックがアンローリングにとって望ましいものである場合（ステップ４２０＝ＹＥＳ）、方法８００は、スーパブロックにおいて行われるべきアンローリングあるときにはどんなタイプのものであるかを決定するための一連のチェックを行う。完全アンローリングが受け入れ可能である場合（ステップ８３０＝ＹＥＳ）、完全アンローリングが遂行される（ステップ８４０）。完全アンローリングが受け入れ可能でない場合（ステップ８３０＝ＮＯ）、方法８００は、静的アンローリングが受け入れ可能であるかどうかを知るためのチェックを行う（ステップ８５０）。それが肯定される場合（ステップ８５０＝ＹＥＳ）、静的アンローリングが遂行される（ステップ８６０）。静的アンローリングが受け入れ可能でない場合（ステップ８５０＝ＮＯ）、方法８００は、動的アンローリングが受け入れ可能であるかどうかを知るためのチェックを行う（ステップ８７０）。それが肯定される場合（ステップ８７０＝ＹＥＳ）、動的アンローリングが遂行される（ステップ８８０）。それが否定される場合（ステップ８７０＝ＮＯ）、方法８００が終了する。ステップ８４０、８６０、及び８８０の詳細が別の図に示され、更に詳細に後述されることに留意してほしい。ステップ８４０、８６０、及び８８０の各々における共通の特徴は、アンロールされたスーパブロックを放置するか又は再び入れるかを説明するためのループ・カウンタ値の修正である。
【００３４】
図８における方法８００は、単純なアンローリングを遂行するという限定された価値のため、図４のブロック４３０に存在するような単純なアンローリングを行うための如何なるステップも含まない。しかし、単純なアンローリングが、望ましい実施例の範囲内に方法８００の一部分として含まれ得ることは当業者には明らかであろう。
【００３５】
図８乃至図２３における多くのステップが、その後の図において複数のステップに拡張されるステップであることに留意してほしい。例えば、図８におけるステップ８４０は、複数のステップを含む図９の方法８４０としても示される。このような理由のために、どの流れ図が参照されるかに従って、同じ参照番号がステップとして又は方法として参照され得る。
【００３６】
望ましい実施例では、ステップ４２０は、ループが単一のラッチ・ブロックを有するかどうか、スーパブロックがアンローリングに関して考察されるに十分なほど小さいかどうか、スーパブロックが完全なループ反復を構成するかどうか、並びに、ループ・カウントの初期化及び反復条件が適切に決定され得るかどうかを決定する。完全アンローリング及び静的アンローリングは、ループが反復する正確な回数が決定され得る場合、ステップ８３０及び８５０においてのみ受け入れ可能である。更に、ステップ８３０、８５０、及び８７０におけるすべての受け入れ可能性テストにおいて、そのアンローリングに起因したコード複写の量が調節可能な限度を越えない場合にのみ、アンローリングは受け入れ可能である。
【００３７】
図８のステップ８４０における完全アンローリングを遂行するステップが図９に示される。先ず、アンロール係数ＵＦを表す変数に反復カウントの値が割り当てられる（ステップ９１０）。次に、スーパブロックがＵＦ回だけ複写される（ステップ９２０）。スーパブロックの複製は、命令をコピーすること及び制御フローを更新することを含む。ループ・ターミネーション・ブランチが除去される（ステップ９３０）。すべての反復（iteration）が実行されることがわかっているので、あらゆる反復に対するラッチング・ブランチが除去され得る。そして、最終的には、完全アンローリングを明確にするために、そのカウントが修正（rectify）される。（ステップ９４０）。
【００３８】
図９におけるカウント修正の詳細が図１２に示される。多くのコンピュータ・アーキテクチャは、特別のカウント・レジスタＣＴＲを使用してループを最適化するためのブランチ・オン・カウント（branch-on-count）命令を有する。カウント・レジスタの値をデクリメントしてそれをゼロと比較し、その値が非ゼロである場合にループのトップに戻る命令があるとしよう。ループは、ブランチ・オン・カウント命令を使用するように既に適宜最適化されているものと仮定する。ループがブランチ・オン・カウント・ループである場合（ステップ１２１０＝ＹＥＳ）、一定の修正ブロックが加えられる（ステップ１２２０）。ステップ１２２０における一定の修正ブロックを加えることの詳細が図１４に示される。ループがブランチ・オン・デマンド・ループでない場合（ステップ１２１０＝ＮＯ）、バンプ最適化及び修正が遂行される（ステップ１２３０）。バンプ最適化及び修正ステップ１２３０の詳細が図１５に示される。
【００３９】
図１４を参照すると、図１２のステップ１２２０において一定の修正ブロックを加える詳細が示される。先ず、カウンタＩが２に初期設定される（ステップ１４１０）。カウンタＩの値がアンロール係数ＵＦよりも大きい場合（ステップ１４２０＝ＮＯ）、方法１２２０は終了する。カウンタＩの値がアンロール係数ＵＦよりも小さいか又はそれに等しい場合（ステップ１４２０＝ＹＥＳ）、変数Ｖに、アンロール係数ＵＦマイナス反復値Ｉプラス１の値が割り当てられる（ステップ１４３０）。次に、Ｂが反復Ｉにおける第１ブロックになるように割り当てられる（ステップ１４４０）。アンロール・トレースを抜け出すＢからの各後継アークに対して、Ｖの値をカウント・レジスタにロードするためのコードを含むブロックがそのアークに沿って加えられる（ステップ１４５０）。処理すべき更なるブロックが反復Ｉに存在する場合（ステップ１４６０＝ＹＥＳ）、Ｂが反復Ｉにおける次のブロックに割り当てられ、コントロールがステップ１４５０に送られる。更なるブロックが反復Ｉにない場合（ステップ１４６０＝ＮＯ）、Ｉの値が１だけインクリメントされ（ステップ１４８０）、コントロールがステップ１４２０に送られる。図１４の方法１２２０は、スーパブロック・トレースを離れるときに残っている全反復及び部分的反復の数Ｖをカウント・レジスタＣＴＲにロードすることによって、ブランチ・オン・カウント・ループの完全アンローリングに対するカウントを修正する。
【００４０】
図１２のステップ１２３０におけるバンプ最適化及び修正の遂行に関する詳細が図１５に示される。ステップ１２３０は、ループが完全に、静的に、又は動的にアンロールされるにもかかわらず、ブランチ・オン・カウント命令を使用しないループのカウント修正のために使用される。ループが、ループ・ターミネーションに関してテストするために使用される値をインクリメント又はデクリメントする単一の「バンプ命令」を含むこと、及びループが実行される度にバンプ命令が実行されるのを保証されることが、図８のステップ４２０における適性テストからわかる。しかし、ブランチ・オン・カウント命令とは違って、バンプ命令はテスト及びブランチから分離され得る。それは、ループのトップに、又はループの終わりに、又はそれの間のどこかに現れ得る。更に、バンプ命令によって計算された値がループにおける他の計算によって使用され得るので、更なる分析なしにそれを不用意に除去したり、それの値を変更したりすることはできない。
【００４１】
理想的には、ループは、Ｘ＝Ｘ＋Ｎ（但し、Ｘはループ・ターミネーション・レジスタである）の形式のバンプ命令を有する。しかし、Ｙ＝Ｘ；Ｚ＝Ｙ＋Ｎ；Ｘ＝Ｚのような、ループ内にコピー命令を分散させたようなものであるかもしれない。もちろん、他のもっと複雑な可能性も更に存在する。
【００４２】
Ｘ＝Ｘ＋ＮのＵＦ個のコピーを単一のバンプ命令Ｘ＝Ｘ＋（ＵＦ＊Ｎ）に変換し、及び介在するバンプ表現が、ループからバックアップ・ループ（即ち、テール複写ブロックを含むオリジナル・ループ）への早期のイグジットにおいてのみ実行されるようにするのが望ましい。これを行う方法は、新しいレジスタＹＩをターゲットにするために各バンプ命令を変更すること、及び各々がイグジット・アークにおいてＹＩからのコピーをループ・ターミネーション・レジスタＸに加えることである。その後の最適化フェーズが、ＹＩがイグジット・アークにおいて使用されるだけであることを決定し、コピーがあるところにバンプ命令を押し出すであろう。この方法による複雑さは、ループ内のどこにバンプ命令が来るかを注意しなければならず、バンプ命令の前に抜け出す場合にＹＩ−１を使用しなければならないことである。
【００４３】
これを可能にするために、２セットのレジスタを追跡しなければならない。Ｓ0は、バンプ命令の前にループ・ターミネーション・レジスタＸと同じ値を有するすべてのレジスタを含み、Ｓ1は、バンプ命令に続くレジスタで、レジスタＸと等価のレジスタを含む。各反復の開始時に、Ｓ0がＳ1の古い値を得て、Ｓ1がエンプティとなる。セットＳ０は、Ｘ以外のレジスタであるカノニカル表現Ｒｅｐ（Ｓ０）を含む。セットＳ１も同様にＸ以外のレジスタであるカノニカル表現Ｒｅｐ（Ｓ１）を含む。バンプ計算に使用される命令の動きを容易にするために、可能な限りループからＸの使用を除去することがアイディアである。ループの開始時に、Ｘからのコピーを新しいレジスタＸ’に入れる。Ｘ’はＸの初期値を表す。バンプ命令は、すべて、初期バンプ値をＸに加えるのではなく、初期バンプ値Ｎの倍数をＸ’に加えるであろう。
【００４４】
図１２におけるバンプ最適化及び修正１２３０をインプリメントする場合の詳細なステップを説明するために、図１５に説明を戻す。先ず、ループ・ターミネーション・レジスタＸ及びオリジナル・バンプ量Ｎが識別される（ステップ１５１０）。新しいレジスタＸ’が割り振られ、コピー・ステートメントＸ’＝Ｘが第１アンロール反復の開始時に挿入される（ステップ１５２０）。セットＳ０がＸ’及びＸを含むように初期設定され、Ｓ１がヌルに初期設定され、そして新しいレジスタＹ０がＸ’の値に初期設定される（ステップ１５３０）。次に、Ｉが１の値にセットされる（ステップ１５４０）。Ｉがアンロール係数ＵＦよりも大きい場合（ステップ１５５０＝ＮＯ）、方法１２３０が終了する。Ｉがアンロール係数ＵＦよりも小さいか又はそれに等しい場合（ステップ１５５０＝ＹＥＳ）、新しいシンボリック・レジスタＹＩが割り振られ（ステップ１５６０）、Ｂがアンロール反復Ｉにおける第１ブロックにセットされる（ステップ１５７０）。次に、バンプ最適化及び修正のためにＢが処理される（ステップ１５８０）。ステップ１５８０の詳細が図１６に示されることに留意してほしい。アンロール反復Ｉに更なるブロックが存在する場合（ステップ１５９０＝ＹＥＳ）、Ｂがアンロール反復Ｉにおける次のブロックにセットされ（ステップ１５９２）、コントロールがステップ１５８０に送られる。アンロール反復Ｉに更なるブロックが存在しない場合（ステップ１５９０＝ＮＯ）、Ｓ１がＳ０にコピーされ、Ｓ１がヌルにセットされ、そしてＩが１だけインクリメントされる（ステップ１５９４）。この時点で、コントロールがステップ１５５０に送られ、処理が継続する。
【００４５】
ステップ１５８０におけるバンプ最適化及び修正に対するブロックＢの処理が図１６において更に詳細に示される。処理すべき更なるステートメントがＢに存在し（ステップ１６１０＝ＹＥＳ）、従って、ＳがＢにおける第１ステートメントにセットされる（ステップ１６３０）。ＳがフォームＲ’＝Ｒのコピー・ステートメントである場合（ステップ１６４０＝ＹＥＳ）、そのコピー・ステートメントが処理される（ステップ１６５０）。ステップ１６５０におけるコピー・ステートメントの処理に関する詳細が図１７に示されることに留意してほしい。ＳがフォームＲ’＝Ｒのコピー・ステートメントでない場合（ステップ１６４０＝ＮＯ）、Ｓが可能なバンプ・ステートメントであるかどうかを知るためのチェックが行われる（ステップ１６６０）。それが肯定される場合（ステップ１６６０＝ＹＥＳ）、バンプ・ステートメントＳが処理される（ステップ１６７０）。ステップ１６７０におけるバンプ・ステートメントＳの処理に関する詳細が図１８に示される。Ｓが可能なバンプ・ステートメントでない場合（ステップ１６６０＝ＮＯ）、一般ステートメントＳが処理される（ステップ１６８０）。ステップ１６８０における一般ステートメントの処理に関する詳細が図１９に示される。処理すべき更なるステートメントがＢに存在する場合（ステップ１６１０＝ＹＥＳ）、ＳがＢにおける次のステートメントにセットされ（ステップ１６３０）、処理がステップ１６４０において継続する。Ｂにおいて更なるステートメント存在しない場合（ステップ１６１０＝ＮＯ）、Ｂに対するコピー修正ブロックが加えられる（ステップ１６２０）。図１６におけるステップ１６２０の詳細が図２０に示される。
【００４６】
図１６のステップ１６５０におけるコピー・ステートメントＳの処理が図１７において更に詳細に示される。ＲがセットＳ０の要素ではない場合（ステップ１７１０＝ＮＯ）、メソッド１６５０が終了する。ＲがセットＳ０の要素である場合（ステップ１７１０＝ＹＥＳ）、Ｒ’がＳ０に加えられ、Ｒ’がＳ１から除去され、そしてＲがカノニカル表現Ｒｅｐ（Ｓ０）によりＳにおいて置換される。ＲがセットＳ０の要素ではないが（ステップ１７１０＝ＮＯ）、セットＳ１の要素である場合（ステップ１７３０＝ＹＥＳ）、Ｒ’がＳ１に加えられ、Ｒ’がＳ０から除去され、そしてＲがカノニカル表現Ｒｅｐ（Ｓ１）によりＳにおいて置換される。
【００４７】
次に、図１８に示された図１６のステップ１６７０におけるバンプ・ステートメントＳの処理に関する詳細を考察する。Ｓが図１６のステップ１６６０においてフォームＲ’＝Ｒ＋Ｎのバンプ・ステートメントであると決定されていることに留意してほしい。ＲがセットＳ０の要素ではなく（ステップ１８１０＝ＮＯ）、セットＳ１の要素でもない場合（ステップ１８５０＝ＮＯ）、方法１６７０は終了する。ＲがＳ０の要素である場合（ステップ１８１０＝ＹＥＳ）、新しいバンプ命令Ｙ１＝Ｘ’＋Ｃ（但し、Ｃ＝Ｎ＊Ｉ）がＳの前に作成される（ステップ１８２０）。次に、ＳにおけるＲがカノニカル表現Ｒｅｐ（Ｓ０）により置換される（ステップ１８３０）。そこで、Ｒ’及びＹＩがＳ１に加えられ、Ｒ’及びＹＩがＳ０から除去される（ステップ１８４０）。ＲがＳ０の要素ではないが（ステップ１８１０＝ＮＯ）Ｓ１の要素である場合（ステップ１８５０＝ＹＥＳ）、Ｒがカノニカル表現Ｒｅｐ（Ｓ１）によりＳにおいて置換される（ステップ１８６０）。
【００４８】
図１６のステップ１６８０における一般ステートメントＳの処理に関する詳細が図１９に示される。ＲがセットＳ０の要素となるようなＳにおけるすべての使用されたレジスタＲに対して、カノニカル表現Ｒｅｐ（Ｓ０）によってＲが置換される（ステップ１９１０）。ＲがセットＳ１の要素となるようなＳにおけるすべての使用されたレジスタＲに対して、カノニカル表現Ｒｅｐ（Ｓ１）によってＲが置換される（ステップ１９２０）。そして、Ｓにおけるすべての定義されたレジスタＲ’に対して、Ｓ０及びＳ１からＲ’が除去される（ステップ１９３０）。
【００４９】
図１６のステップ１６２０におけるコピー修正ブロックを加えることに関する詳細が図２０に示される。ＸがセットＳ１の要素である場合（ステップ２０１０＝ＹＥＳ）、変数ＺにＹＩの値が割り当てられる（ステップ２０２０）。ＸがセットＳ１の要素ではない場合（ステップ２０１０＝ＮＯ）、ＺにＹＩ−１の値が割り当てられる（ステップ２０３０）。Ｂからの未処理イグジット・アークが存在する場合（ステップ２０４０＝ＹＥＳ）、ＡがＢからの次の未処理イグジット・アークにセットされ（ステップ２０５０）、コピー・ステートメントＸ＝Ｚを含む新しいブロックがＡに挿入される（ステップ２０６０）。そこで、処理がステップ２０４０において再開し、Ｂからのすべてのイグジット・アークが処理されてしまうまで（ステップ２０４０＝ＮＯ）、処理が継続する。
【００５０】
図８のステップ８６０における静的アンローリングを遂行するステップが図１０に示される。先ず、１つ又はそれ以上の適当なヒューリスティクスを使って、静的アンローリング係数ＵＦが決定される（ステップ１０１０）。アンローリング係数ＵＦを決定するためのヒューリスティクスは、アンロールされる反復の合計数及び複製される命令の合計数を制限し得る。そのヒューリスティクスは、スーパブロックがラッチング・ブランチに達する前に抜け出すことがどのくらいあるかによってアンローリング係数も制限し得る。更に、ヒューリスティクスは、必要な残りの反復の数を制限し得る。一旦、アンローリング係数ＵＦが決定されると、スーパブロックがＵＦ回複製される（ステップ１０２０）。スーパブロックの複製は、命令のコピー及び制御フローの更新を含む。内部ループ・ターミネーション・ブランチが除去される（ステップ１０３０）。最後の反復を除くすべての反復に対するラッチング・ブランチがステップ１０３０において除去され得る。そこで、すべての残りの反復が作成される（ステップ１０４０）。反復の合計数がアンローリング係数ＵＦによって割り切れない場合、その差を補うためにそのアンロールされたループの前に残りの反復が置かれる。残りの反復は、ループ全体ではなく、スーパブロックの複製である。最終的に、不完全アンローリングを明確にするために、カウントが修正されなければならない。
【００５１】
図１０のステップ１０５０における不完全アンローリングに対するカウント修正の詳細が図１３に示される。ループがブランチ・オン・カウント・ループである場合（ステップ１３１０＝ＹＥＳ）、スケーリング修正ブロックが加えられ（ステップ１３２０）、残りの反復修正ブロックが加えられる（ステップ１３３０）。何らかのエスケープ・アークが見つかる場合（ステップ１３４０＝ＹＥＳ）、逆修正ロジックが加えられる（ステップ１３６０）。この時点で、カウント・レジスタ初期設定が変更される（ステップ１３５０）。エスケープ・アークが見つからない場合（ステップ１３４０＝ＮＯ）、ステップ１３６０における逆修正ロジックを加える必要なくカウント・レジスタ初期設定が変更される（ステップ１３５０）。
【００５２】
ブランチがブランチ・オン・カウント・ループではない場合（ステップ１３１０＝ＮＯ）、図１２に関連して詳細に説明されたバンプ最適化及び修正が遂行される（ステップ１２３０）。そこで、アンロール・トレース及びバックアップ・ループのヘッダをターゲットとするモジュラス・テスト・ブロックＷが作成される（ステップ１３７０）。ブロックＷは、Ｘ及びＵＦを計算するためのコードを含む。但し、Ｘは、図１２の方法１２３０において使用されたループ・ターミネーション・レジスタであり、ＵＦは、このループに対するアンロール係数である。そこで、バックアップ・ループからのラッチ・アークがブロックＷにリダイレクトされる（ステップ１３８０）。これは、ブロックＷにおけるモジュラス・テストがゼロに戻る場合、ループをアンロール・スーパブロックのヘッダにブランチさせ、そうでない場合にバックアップ・ループのヘッダにブランチさせる。これは、できるだけ速くコントロールがアンロール・ループに戻るようにするためである。
【００５３】
図１３を再び参照すると、スケーリング修正ブロックを加えるステップ１３２０の詳細が図２１に示される。ステップ１３２０は、完全にはアンロールされ得ないブランチ・オン・カウント・ループに対して遂行される。先ず、Ｉが１の値にセットされる（ステップ２１１０）。Ｉがアンロール係数ＵＦよりも大きい場合（ステップ２１２０＝ＮＯ）、方法１３２０は終了する。Ｉがアンロール係数ＵＦよりも小さいか又はそれに等しい場合（ステップ２１２０＝ＹＥＳ）、Ｂが反復Ｉにおける第１ブロックにセットされる（ステップ２１３０）。アンロール・トレースを抜け出すＢのうちの各アークＡに対して、コードＣＴＲ＝ＣＴＲ＊ＵＦ−（Ｉ−１）を含むブロックＣがＡに加えられる（ステップ２１４０）。反復Ｉにおいて何らかの未処理のブロックが存在する場合（ステップ２１５０＝ＹＥＳ）、Ｂが反復Ｉにおける次のブロックにセットされ（ステップ２１７０）、ステップ２１４０において処理が継続する。反復Ｉにおけるすべてのブロックが処理されてしまった場合（ステップ２１５０＝ＮＯ）、Ｉが１だけインクリメントされ（ステップ２１６０）、ステップ２１２０において処理が継続する。
【００５４】
図１３のステップ１３６０における逆修正ロジックの付加に関する詳細が図２２に示される。先ず、ブロックＷがオリジナル・ラッチ・ブロックからアークを介してオリジナル・ループ・ヘッダ・ブロックに加えられる（ステップ２２１０）。オリジナル・ラッチ・ブロックがテール複写されなかった場合（ステップ２２２０＝ＮＯ）、コントロールがステップ２２４０に送られる。オリジナル・ラッチ・ブロックがテール複写された場合（ステップ２２２０＝ＹＥＳ）、ツイン・ラッチ・ブロックからループ・ヘッダ・ブロックへのアークがブロックＷを代わりにターゲットとするようにリダイレクトされる（ステップ２２３０）。そして、コードがブロックＷにおいて生成されて次のようなステップを遂行する。即ち、アンロール係数ＵＦに関してカウンタＣＴＲのモジュラスが計算され、ＣＴＲモジュロＵＦがゼロに比較され、ＣＴＲモジュロＵＦがゼロである場合にアンロール・トレースへのブランチが行われ、そうでない場合にオリジナル・ループ・ヘッダ・ブロックへのブランチが行われる（ステップ２２４０）。そして、アークがＷからアンロール・トレースのヘッダ・ブロックに加えられる（ステップ２２５０）。そして、ブロックＲ−１が新しいアークに挿入される（ステップ２２６０）。次に、コードがブロックＲ−１において生成されてＣＴＲ＝ＣＴＲ／ＵＦを計算する（ステップ２２７０）。
【００５５】
図１３におけるステップ１３３０の詳細が図２３に示される。先ず、Ｉが１にセットされ、Ｌが残りの反復の数にセットされる（ステップ２３１０）。ＩがＬよりも大きい場合（ステップ２３２０＝ＮＯ）、方法１３３０は終了する。ＩがＬよりも小さいか又はそれに等しい場合（ステップ２３２０＝ＹＥＳ）、Ｂが残りの反復Ｉにおける第１ブロックにセットされる（ステップ２３３０）。静的アンローリングが遂行された場合（ステップ２３４０＝ＹＥＳ）、残りの反復を抜け出し、バックアップ・ループをターゲットとするＢからの各アークＡに対して、アークＡにおいてコードＣＴＲ＝（ＣＴＲ＊ＵＦ）−１を含むブロックＣが加えられる。静的アンローリングが遂行されなかった場合（ステップ２３４０＝ＮＯ）、残りの反復を抜け出し、バックアップ・ループをターゲットとするＢからの各アークＡに対して、アークＡにおいてコードＣＴＲ＝（ＣＴＲ＊ＵＦ）＋（２＊（Ｌ−Ｉ＋１））を含むブロックＣが加えられる。反復Ｉにおいて依然として未処理のブロックが存在する場合（ステップ２３７０＝ＹＥＳ）、Ｂが反復Ｉにおける次のブロックにセットされ（ステップ２３９０）、ステップ２３４０において処理が継続する。一旦、反復Ｉにおけるすべてのブロックが処理されてしまうと（ステップ２３７０＝ＮＯ）、Ｉが１だけインクリメントされ（ステップ２３８０）、ステップ２３２０において処理が継続する。
【００５６】
図８のステップ８８０において動的アンローリングを遂行するステップが図１１に示される。先ず、１つ又はそれ以上の適当なヒューリスティクスを使用して動的アンローリング係数ＵＦが決定される（ステップ１１１０）。そのヒューリスティクスは、図１０のステップ１０１０において静的アンローリング係数を決定するために使用されたヒューリスティクスよりも更に限定的なものになり得る。一旦、アンローリング係数ＵＦが決定されてしまうと、スーパブロックがＵＦ回複製される（ステップ１１２０）。スーパブロックの複製は、命令をコピーすること及び制御フローを更新することを含む。内部ループ・ターミネーション・ブランチが除去される（ステップ１１３０）。最後の反復を除くすべての反復に対するラッチング・ブランチがステップ１１３０において除去され得る。そして、いずれかの必要な残りの反復及びモジュラス・テストが行われる（ステップ１１４０）。反復の合計数がアンローリング係数ＵＦによって割り切れない場合、残りの反復がアンロール・ループの前に置かれてその差を補う。動的アンローリングに対して、そのループに先立ってＵＦ−１個の残りの反復が行われる。これらの前に、実行時に反復の合計数Ｔを決定し且つＴモジュロＵＦの剰余を決定するためのコードが置かれる。その結果は適正な残りの反復へのブランチを生じさせ、この残りの反復の数がアンロール・ループの前に実行されるようにする。最後に、図１０におけるステップ１０５０に関して詳細に上述された不完全アンローリングを説明するために、カウントが修正されなければならない（ステップ１０５０）。
【００５７】
次に、図８乃至図２３に示された方法を説明するための例を示す。図２４は、５つの基本ブロックＡ、Ｂ、Ｃ、Ｄ及びＥを含むコードの一部分のサンプル制御フローを示す。図２４における各アークに対する実行頻度は、アークの次に数値で示される。望ましい実施例では、これらの実行頻度はプロファイル・データ１２５（図１）から決定される。これは、ブロックＡにおいて３に初期設定されたカウント・レジスタＣＴＲ及びブロックＤにおける「ｂｃｆ」命令を伴なうブランチ・オン・カウント・ループであると仮定する。ｂｃｆ命令は、PowerPC の命令セットにおいて定義され、実行されるときにカウント・レジスタＣＴＲをデクリメントし、その結果が非ゼロである場合にブランチする。ループを通したホット・トレースがブロックＢ及びＤを含むことをその実行頻度から留意してほしい。このループは、いつも正確に３回実行される。次に、これらの仮定と共に、図８における方法８００に説明を移す。
【００５８】
Ｄ’を複製することにより、ステップ４１０におけるテール複写を使用してスーパブロックが形成され、図２５にその結果が示される。スーパブロックが形成される方法を規定するホット・トレースを決定するためには、図２４における実行頻度が必要である。一旦、スーパブロックが形成されると、実行頻度は示される必要がないので、それらは図２５乃至図２７には示されない。図２５に示されたスーパブロックに対して、それがアンローリングにとって好適であり（ステップ４２０＝ＹＥＳ）、完全アンローリングが受け入れ可能であるものと仮定する（ステップ８３０＝ＹＥＳ）。そこで、図９において詳細に示される完全アンローリングが遂行される（ステップ８４０）。
【００５９】
ループがいつも３回実行されるものと仮定して、アンロール係数ＵＦが３にセットされる（ステップ９１０）。そこで、スーパブロックが３回複製され（ステップ９２０）、ループ・ターミネーション・ブランチが除去される（ステップ９３０）。その結果、図２６に示される制御フローが生じる。３回アンロールするための複製は、Ｂ１、Ｄ１、Ｂ２、Ｄ２、Ｂ３、及びＤ３である。ブロックは、Ｂ、Ｃ、Ｄ、及びＤ’である。そこで、図１２において詳細に示される完全アンローリングのためのカウント修正が遂行される（ステップ９４０）。
【００６０】
これがブランチ・オン・カウント・ループであると仮定すると（ステップ１２１０＝ＹＥＳ）、図１４において詳細に示される一定の修正ブロックを加える必要がある（ステップ１２２０）。Ｉが２にセットされる（ステップ１４１０）。２は３のアンロール係数ＵＦよりも小さいので（ステップ１４２０＝ＹＥＳ）、Ｖが（３−２＋１）、即ち、２にセットされる（ステップ１４３０）。Ｂが第２反復における第１ブロックにセットされる（ステップ１４４０）。なお、それは、図２６における例に対してはＢ２である。次に、ステップ１４５０がＢ２及びＣの間にブロックＲ２を加える。但し、Ｒ２は、カウンタＣＴＲに２をロードするためのコードを含む。第２反復には更なるブロックが存在するので（ステップ１４６０＝ＹＥＳ）、Ｂが第２反復における次のブロックＤ２にセットされる（ステップ１４７０）。ステップ１４５０では、ブロックＤ２に対して、アンロール・トレースを抜け出すアークが存在しないので、何も行われない。第２反復における更なるブロックが存在しないので（ステップ１４６０＝ＮＯ）、Ｉが３にインクリメントされる（ステップ１４８０）。Ｉが依然として３のアンロール係数よりも小さいか又はそれに等しいので（ステップ１４２０＝ＹＥＳ）、Ｖが１の値にセットされ、Ｂが第３反復における第１ブロックであるブロックＢ３にセットされる。ステップ１４５０において、ブロックＲ３がＢ３とＣとの間に加えられる。なお、Ｒ３は、カウンタＣＴＲに１をロードするためのコードを含む。第３反復における更なるブロックが存在するので（ステップ１４６０＝ＹＥＳ）、第３反復における次のブロック、即ち、Ｄ３にＢがセットされる。ステップ１４５０では、Ｄ３に対して、アンロール・トレースを抜け出すアークが存在しないので、何も行われない。第３反復には更なるブロックが存在しないので、Ｉが４にインクリメントされる（ステップ１４８０）。ステップ１４２０は今やＮＯであるので、方法１２２０は終了する。図２６のスーパブロックを完全にアンロールした結果が図２７に示される。ブロックＲ２及びＲ３は、頻繁には実行されなかったコードをバックアップ・ループにおいて実行するためにホット・トレースを離れることを明確にするために、カウンタＣＴＲを調節するカウント修正コードを含むということに留意してほしい。
【００６１】
図２８は、簡単な静的アンローリングの例に対するサンプル制御フローを示す。実行頻度は、各エントリ当たり３０回実行されるループを示すように変更されている。再び、これは、３０がブロックＡにおけるＣＴＲ及びブロックＤにおけるｂｃｆステートメントにロードされた場合のブランチ・オン・カウント・ループであるものと仮定される。次に、図８を参照すると、テール形成（tail formation）を使用するスーパブロックの形成の結果（ステップ４１０）、図２５に示された制御フローを生じる。そのスーパブロックがアンローリングにとって好適であり（ステップ４２０＝ＹＥＳ）、ホット・トレースを３０回複写することが過剰なコード・ブロート（codebloat）を導くので、完全アンローリングは受け入れ可能でない（ステップ８３０＝ＮＯ）ものと仮定する。更に、静的アンローリングが受け入れ可能であるので、図１０に詳細に示されたステップ８６０において静的アンローリングを遂行するものと仮定する。
【００６２】
３の静的アンロール係数ＵＦが選択される（ステップ１０１０）。アンロール係数ＵＦは任意の適当なヒューリスティクスを使用して行われ得ることに留意してほしい。スーパブロックが３回複製され（ステップ１０２０）、内部ターミネーション・ブランチが除去される（ステップ１０３０）。その結果が図２９に示される。ループが完全にはアンロールされないので、Ｄ３からＢ１に戻る付加的なアークを除けば、図２９は図２６の制御フローと同じであることに留意してほしい。３０がアンロール係数３によって割り切れるために、残りの反復は存在せず、従って、ステップ１０４０は何もしない。そこで、図１３に更に詳細に示される不完全アンローリングに対するカウントが修正される。
【００６３】
最初の仮定では、これがブランチ・オン・カウント・ループであることが仮定されたので、ステップ１３１０＝ＹＥＳである。その結果、図２１において詳細に示されたスケーリング修正ブロックを加える必要がある（ステップ２１１０）。１が３のアンロール係数よりも小さいので、ステップ２１２０＝ＹＥＳである。Ｂが第１反復における第１ブロック、即ち、Ｂ１にセットされる。ステップ２１４０がＢ１及びＣの間にブロックＣ１を加える。その場合、Ｂ１は、コードＣＴＲ＝ＣＴＲ＊３を含む。第１反復には依然として未処理のブロックが存在するので（ステップ２１５０＝ＹＥＳ）、Ｂが第１反復における次のブロック、即ち、Ｄ１にセットされる。アンロール・トレースを抜け出すＤ１からのアークが存在しないので、ステップ２１４０は何も行わない。第１反復には更なる未処理のブロックが存在しないので（ステップ２１５０＝ＮＯ）、Ｉが１だけインクリメントされ、２の値になる（ステップ２１６０）。ステップ２１２０は依然としてＹＥＳであるので、Ｂが第２反復における第１ブロック、即ち、Ｂ２にセットされる。ステップ２１４０がＢ２及びＣの間にブロックＲ２を加える。その場合、Ｒ２はコードＣＴＲ＝（ＣＴＲ＊３）−１を含む。第２反復には依然として未処理のブロックが存在するので（ステップ２１５０＝ＹＥＳ）、Ｂが次のブロック、即ち、Ｄ２に割り当てられる。好適なアークが存在しないので、ステップ２１４０は何も行わない。第２反復には更なる未処理のブロックが存在しないので（ステップ２１５０＝ＮＯ）、Ｉが１だけインクリメントされて３の値になる（ステップ２１６０）。ステップ２１２０は依然としてＹＥＳであり、従って、Ｂが第３反復における第１ブロック、即ち、Ｂ３にセットされる。ステップ２１４０がＢ３及びＣの間にブロックＲ３を加える。その場合、Ｒ３はコードＣＴＲ＝（ＣＴＲ＊３）−２を含む。第３反復には依然として未処理のブロックが存在するので（ステップ２１５０＝ＹＥＳ）、Ｂが第３反復における次のブロック、即ち、Ｄ３にセットされる。Ｄ３は，好適なアークを持たないので、ステップ２１４０はアクションを取らない。第３反復には未処理のブロックが存在しないので（ステップ２１５０＝ＮＯ）、Ｉが４の値にインクリメントされる（ステップ２１６０）。ステップ２１２０は今やＮＯであり、それはステップ１３２０を終わらせる。従って、図１３に戻り、図２３に詳細に示される残りの修正ブロックが加えられる（ステップ１３３０）。
【００６４】
ステップ２３１０がＩを１にセットし、残りの反復が存在しないのでＬをゼロにセットする。ステップ２３２０において、Ｉの値（１）がＬの値（０）よりも大きいので、ステップ２３２０＝ＮＯであり、ステップ１３３０が終了する。図１３に戻ると、エスケープ・アークが見つかる（ステップ１３４０＝ＹＥＳ）。図２９におけるエスケープ・アークの例は、Ｂ１及びＣの間、Ｂ２及びＣの間、並びにＢ３及びＣの間のアークである。これらのアークの各々は、ホット・トレースをエスケープする。このために、図２２において詳細に示されるように、逆修正ロジックが加えられる（ステップ１３６０）。
【００６５】
ステップ２２１０は、Ｄ及びＢの間にブロックＷを加える。オリジナル・ラッチ・ブロックＤは、図２９においてブロックＤ’によって示されるように、テール複写された（ステップ２２２０＝ＹＥＳ）。そこで、Ｄ’からＢへのアークが代わりにＷをターゲットとするようにリダイレクトされる（ステップ２２３０）。そこで、ＣＴＲモジュロ３をゼロに比較するコードがブロックＷにおいて生成され、それが真である場合にはアンロール・トレースにブランチし、そうでない場合にはオリジナル・ループ・ヘッダ・ブロックＢにブランチする（ステップ２２４０）。そこで、アークが、Ｗからアンロール・トレースのヘッダ・ブロックＢ１に加えられる（ステップ２２５０）。そこで、新しいブロックＲ−１がＷから新しいアークに沿ってＢ１に加えられる（ステップ２２６０）。そこで、ＣＴＲ＝ＣＴＲ／３を計算するためのコードがＲ−１において生成される。この時点で、ステップ１３６０が終了するので、コントロールが図１３におけるステップ１３５０に戻る。そこで、ブロックＡにおけるカウント・レジスタ初期設定がＣＴＲ＝３０からＣＴＲ＝１０に変更される（ステップ１３５０）。今やステップ１０５０が終了し、ステップ８６０が終了する。それは、図８における方法８００を完了させる。その結果が図３０の制御フローに示される。
【００６６】
図３１の制御フローは、動的アンローリングが使用され得る場合の例である。図３１において示されるような実行頻度の場合、各エントリ当たりのループ実行の平均数は６である。この例に対して、ブロックＡが入力パラメータＰからＣＴＲをロードするためのコードを含むものと仮定すると、コンパイル時には反復の正確な数を決定することができない。更に、Ｄがｂｃｆ命令を含むものと仮定する。今や、図３１の制御フローが処理される方法を知るために、図８における方法８００に説明を移す。
【００６７】
図８のステップ４１０は、テール複写を使用してスーパブロックを生じ、再び、図２５における結果を生じさせる。そのスーパブロックはアンローリングにとって好適であるものと仮定する（ステップ４２０＝ＹＥＳ）。完全アンローリングは、正確な反復カウント値が決定され得ないので、受け入れ可能ではない（ステップ８３０＝ＮＯ）。この同じ理由のために、静的アンローリングも受け入れ可能ではない（ステップ８５０＝ＮＯ）。動的アンローリングが受け入れ可能であると仮定すると（ステップ８７０＝ＹＥＳ）、ステップ８８０において動的アンローリングが遂行される。そのステップ８８０は、図１１において更に詳細に示される。
【００６８】
３の動的アンロール係数ＵＦが選択される（ステップ１１１０）。ここでも、動的アンロール係数は任意の適当なヒューリスティクスを使用して決定され得る。そこで、スーパブロックが３回複製され（ステップ１１２０）、内部ループ・ターミネーション・ブランチが除去され（ステップ１１３０）、そして残りの反復及びモジュラス・テストが行われる（ステップ１１４０）。その結果が図３２の制御フローである。アンロール・ループＢ１乃至Ｄ３に先行して２つの残りの反復ＬＢ１乃至ＬＤ２が存在する。どこで開始すべきかを決定するためには、２つのモジュラス・テスト・ブロックＭ１及びＭ２が必要である。ブロックＭ１はパラメータ値モジュロ３を取り、その結果がゼロである場合、コントロールは、アンロール・ループの始まりであるＢ１にブランチする。Ｍ１におけるモジュラス・テストが非ゼロである場合、Ｍ２におけるモジュラス・テストが、必要な残りの反復の数を決定する。Ｍ１におけるモジュラス・テストからの結果が１である場合、それはＬＢ２にブランチし、そうでない場合、それはＬＢ１になる。動的アンローリングは不完全アンローリングであるため、図１３において更に詳細に示されるようにカウントが修正されなければならない。
【００６９】
これはブランチ・オン・カウント・ループであるので（ステップ１３１０＝ＹＥＳ）、図２１において更に詳細に示されるように、スケーリング修正ブロックが付加される必要がある（ステップ１３２０）。図２１の方法１３２０による図３２の制御フローの処理は、その結果としてブロックＲ１、Ｒ２、及びＲ３を加える。同じことが、図３０に示され及び上述された静的アンローリングの例においても行われる。一旦、ステップ１３２０が完了すると、コントロールが図１３におけるステップ１３３０に移される。残りの反復修正ブロックが加えられる（ステップ１３３０）。これは、図２３に詳細に示される。Ｉが１にセットされ、残りの反復の数であるＬが２にセットされる（ステップ２３１０）。ＩがＬよりも小さいので、ステップ２３２０はＹＥＳである。Ｂが、残りの第１反復における第１ブロックであるＬＢ１にセットされる（ステップ２３３０）。これは、静的アンローリングではなく動的アンローリングの場合であるので、ステップ２３４０＝ＮＯである。ステップ２３６０がＬＢ１及びＣの間にブロックＬＲ１を加える。この場合、ＬＲ１は、コードＣＴＲ＝（ＣＴＲ＊３）−１を含む。第１反復には依然として未処理のブロックが存在するので（ステップ２３７０＝ＹＥＳ）、Ｂが第１反復における次のブロックＬＤ１にセットされる（ステップ２３９０）。ステップ２３４０＝ＮＯであるが、ＬＤ１に対して好適なアーク（関連あるバックアップ・ループをターゲットとするアーク）が存在しないので、ステップ２３６０は何もしない。第１反復には更なる未処理のブロックが存在しないので（ステップ２３７０＝ＮＯ）、Ｉが１だけインクリメントされて２の値になり（ステップ２３８０）、制御がステップ２３２０に送られる。
【００７０】
ステップ２３２０が依然として真であるので、Ｂが第２の残り反復における第１ブロックＬＢ２にセットされる（ステップ２３３０）。ステップ２３４０はＮＯである。そこで、ステップ２３６０がＬＢ２及びＣの間にＬＲ２を加える。その場合、ＬＲ２は、コードＣＴＲ＝（ＣＴＲ＊３）−２を含む。第２の残り反復には依然として未処理のブロックが存在するので（ステップ２３７０＝ＹＥＳ）、Ｂが第２の残り反復における次のブロックＬＤ２にセットされる（ステップ２３９０）。ステップ２３４０はＮＯである。ＬＤ２からの好適なアークが存在しないので、ステップ２３６０は何もしない。第２の残り反復におけるすべてのブロックが処理されてしまったので（ステップ２３７０＝ＮＯ）、Ｉが１だけインクリメントされて３の値になる（ステップ２３８０）。この時点で、ＩはＬよりも小さくなく又はＬに等しくもないので、ステップ２３２０＝ＮＯであり、ステップ１３３０が終了する。この時点に対する結果が図３３における制御フローによって示される。
【００７１】
図１３に戻ると、エスケープ・アークが見つかるので（ステップ１３４０＝ＹＥＳ）、図２２において詳細に示される逆修正ロジックが加えられる（ステップ１３６０）。この場合、図２２のステップ１３６０が図３０に示された静的アンローリングの例において遂行されたステップと同じステップ、即ち、ブロックＷ及びＲ−１を加え且つアークをリダイレクトするステップを遂行する。一旦、逆修正ロジックが図１３のステップ１３６０において加えられると、カウント・レジスタ初期設定が、アンローリングを明確にするように修正される（ステップ１３５０）。ブロックＡにおけるカウント・レジスタ初期設定がＣＴＲ＝（Ｐ／３）＋１に変更される。この時点で、図１３の方法１０５０が終了し、図１０のステップ１０５０が終了し、従って、図８のステップ８６０が終了する。その結果、方法８００が終了する。この結果が図３４における制御フローに示される。
【００７２】
最後の例は、カウント・レジスタを使用しないループにおいて静的アンローリングを使用する。図３５は、幾つかのブロックの内部のステートメントが可視的である制御フローを示す。更なるステートメントが存在するが、この例では図３５に示されたものが使用されるものと仮定する。ループが各エントリ当たり丁度１０回実行されることがコンパイル時に決定される。変数「ｄ」がループの外で使用されるが、内では使用されないものと仮定する。その後の最適化のために、変数「ｂ」及び「ｃ」に関するすべての事項が図３５に示されるものと更に仮定する。図３５に示されたプログラム部分をアンロールすべく静的アンローリングが使用される方法を知るために、説明を図８における方法８００に移す。
【００７３】
図８のステップ４１０におけるテール複写の結果、図３６の制御フローが生じる。この場合、Ｄ及びＧの両方が複写されなければならなかった。スーパブロックはアンローリングにとって好適なものである仮定する（ステップ４２０＝ＹＥＳ）。ループを１０回アンロールすることはその結果として過度の量のコードが生じるので、完全アンローリングは受け入れ可能ではない（ステップ８３０＝ＮＯ）。静的アンローリング受け入れ可能であると仮定する（ステップ８５０＝ＹＥＳ）。その結果、図１０において詳細に示される静的アンローリングが遂行される（ステップ８６０）。
【００７４】
２の静的アンロール係数が選択される。スーパブロックが２回複製され（ステップ１０２０）、内部ループ・ターミネーション・ブランチが除去される（ステップ１０３０）。１０は２によって割り切れるので、残りの反復は存在しない（ステップ１０４０）。その結果が図３７の制御フローである。アンローリングが不完全であるので、図１３において更に詳細に示されるように、カウント修正が必要である（ステップ１０５０）。
【００７５】
これはブランチ・オン・カウント・ループではないので、図１５において更に詳細に示されるように、バンプ最適化及び修正が遂行される（ステップ１２３０）。レジスタは、それが図３５のブロックＤにおけるループの終了時の比較のために使用され且つオリジナル・バンプ量Ｎが１であることをステップ１５１０が決定する。新たなレジスタＸ’が割り振られ、コピー・ステートメントＸ’＝Ｘが第１のアンロール反復の始めに挿入される（ステップ１５２０）。図３５における特定の例に対して、新たなレジスタが割り振られ、コピー命令ｒ＝ａがＢ１のトップに挿入される。セットＳ０がメンバＸ’＝ｒ及びＸ＝ａを初期設定され、セットＳ１がヌルに初期設定され、Ｙ０がＸ’＝ｒに初期設定される（ステップ１５３０）。そこで、Ｉが１の値にセットされる（ステップ１５４０）。ＩはＵＦよりも小さいので（ステップ１５５０＝ＹＥＳ）、Ｙ１が、ｔと呼ばれる新たなシンボリック・レジスタにセットされる（ステップ１５６０）。Ｂが第１のアンロール反復における第１ブロックＢ１にセットされる（ステップ１５７０）。そこで、図１６において更に詳細に示されるように、Ｂ１がバンプ最適化及び修正のために処理される（ステップ１５８０）。
【００７６】
ｂ＝ａである（図３５から）Ｂ１における第１ステートメントＳが調べられる。図１５のステップ１５２０においてＢ１に加えられたステートメントは考察されないことに留意してほしい。Ｓは、Ｒ’＝ｂ及びＲ＝ａを有するコピー・ステートメントである（ステップ１６４０＝ＹＥＳ）。そこで、コピー・ステートメントＳが、図１７において詳細に示されるように処理される（ステップ１６５０）。Ｒは、Ｓ０の要素であるａに対応する（ステップ１７１０＝ＹＥＳ）。そこで、ｂであるＲ’がセットＳ０に加えられ、ｂがセットＳ１（効果を生じない）から除去され、Ｓにおけるａが標準的な標本ｒによって置換され、その結果、ｂ＝ｒであるステートメントＳが生じる（ステップ１７２０）。この時点で、図１６におけるステップ１６５０が終了する。処理すべき更なるステートメントがＢにおいて存在するので（ステップ１６１０＝ＹＥＳ）、Ｓが、「ｄ＝ｂ＊２」であるＢにおける次のステートメントにセットされる。このステートメントはコピー・ステートメントではなく（ステップ１６４０＝ＹＥＳ）、可能なバンプ・ステートメントでもないので（ステップ１６６０＝ＮＯ）、図１９において更に詳細に示されるように、一般ステートメントＳが処理される（ステップ１６８０）。
【００７７】
レジスタｂは、セットＳ０の要素であるＳにおける使用されたレジスタであるので、結果ｄ＝ｒ＊２の場合、ｂがステートメントＳにおけるｒによって置換される（ステップ１９１０）。セットＳ１の要素である使用されたレジスタがＳに存在しないので、ステップ１９２０は何も行わない。Ｓにおける定義されたレジスタｄがＳ０にもＳ１にもないので、ステップ１９３０は何も行わない。この時点で、ステップ１６８０は終了し、図１６におけるステップ１６１０にコントロールを送る。Ｂ１には処理すべき更なるステートメントが存在しないので（ステップ１６１０＝ＮＯ）、図２０において詳細に示されるように、コピー修正ブロックがＢ１に対して加えられる（ステップ１６２０）。
【００７８】
レジスタａは図２０におけるＸに対応し、セットＳ１の要素ではない（ステップ２０１０＝ＮＯ）。その結果、Ｚがｒに等しくセットされる（ステップ２０３０）。Ｂからの未処理イグジット・アークが存在するので（ステップ２０４０＝ＹＥＳ）、ＡがＢからの次の未処理イグジット・アーク、即ち、Ｂ１からＣへのアークにセットされる（ステップ２０５０）。コード「ａ＝ｒ」を含む新たなブロックＲＢ１がそのアークに挿入される（ステップ２０６０）。Ｂからのすべてのイグジット・アークが処理されてしまったので（ステップ２０４０＝ＮＯ）、ステップ１６２０が終了する。それは、ステップ１５８０も終了することを意味する。図１５を参照すると、処理すべき更なるブロックが第１アンロール反復に存在するので（ステップ１５９０＝ＹＥＳ）、Ｂが第１アンロール反復における次のブロックＤ１にセットされる（ステップ１５９２）。そこで、図１６において詳細に示されたバンプ及び修正のために、Ｄ１が処理される（ステップ１５８０）。
【００７９】
Ｓが、ｃ＝ｂ＋１であるＤ１における第１ステートメントにセットされる。このステートメントは、コピー・ステートメントではなく（ステップ１６４０＝ＮＯ）、Ｒ’＝ｃ及びＲ＝ｂを有する可能なバンプ・ステートメントである（ステップ１６６０）。その結果、図１８において詳細に示されたバンプ・ステートメントが処理される（ステップ１６７０）。
【００８０】
レジスタｂはセットＳ０における要素であるので（ステップ１８１０＝ＹＥＳ）、命令ｔ＝ｒ＋１がＤ１におけるＳの前に挿入される（ステップ１８２０）。そこで、レジスタｂが、ｒであるセットＳ０のカノニカル表現と置換される（ステップ１８３０）。その結果は、ｃ＝ｒ＋１を読み出すステートメントＳである。レジスタｔ及びｃが表現ｔと共にセットＳ１に加えられ、一方、セットＳ０は｛ｒ，ａ，ｂ｝のままである。この時点で、ステップ１６７０が終了し、図１６におけるステップ１６１０にコントロールを送る。処理すべき更なるステートメントがＤ１に存在するので（ステップ１６１０＝ＹＥＳ）、ＳがＤ１における次のステートメント、即ち、ａ＝ｃにセットされる（ステップ１６３０）。このステートメントは、Ｒ’＝ａ及びＲ＝ｃを有するコピー・ステートメントである（ステップ１６４０＝ＹＥＳ）。そこで、コピー・ステートメントａ＝ｃが、図１７に示されるように処理され（ステップ１６５０）、レジスタｃはセットＳ０の要素ではなく（ステップ１７１０＝ＮＯ）、セットＳ１の要素である（ステップ１７３０＝ＹＥＳ）。レジスタａがセットＳ１に加えられ、その結果、Ｓ１＝｛ｔ，ｃ，ａ｝が生じる。ａがセットＳ０から除去され，その結果、Ｓ０＝｛ｒ，ｂ｝が生じる。ｃがステートメントＳにおいてカノニカル表現ｔと置換され，その結果，ステートメントａ＝ｔが生じる（ステップ１７４０）。今や，ステップ１６５０が終了し，図１６のステップ１６１０にコントロールを移す。処理すべき更なるステートメントがＢに存在しないので（ステップ１６１０＝ＮＯ）、図２０に詳細に示されるように、Ｂに対するコピー修正ブロックが加えられる（ステップ１６２０）。
【００８１】
レジスタａは、ステップ２０１０におけるＸに対応し，現在｛ｔ，ｃ，ａ｝を含むＳ１の要素である。ブロックＤ１からの未処理イグジット・アークが存在するので（ステップ２０４０＝ＹＥＳ）、ＡがＢからの次の未処理イグジット・アーク、即ち，Ｄ１からＦへのアークにセットされる（ステップ２０５０）。コードａ＝ｔを含む新たなブロックＲＤ１が挿入される（ステップ２０６０）。この時点で，ステップ１６２０が終了し，ステップ１５８０も終了して、図１５におけるステップ１５９０にコントロールを移す。第１アンロール反復には依然として更なるブロックが存在するので（ステップ１５９０＝ＹＥＳ）、Ｂが第１アンロール反復における次のブロックＧ１にセットされる（ステップ１５９２）。ブランチが除去されたので，Ｇ１にはステートメントが存在しない（ステップ１６１０＝ＮＯ）。図２０に詳細に示されるように，Ｇ１に対するコピー修正ブロックが加えられる（ステップ１６２０）。
【００８２】
レジスタａが、依然として、ステップ２０１０においてＸに対応し，現在ｔ、ｃ及びａを含むＳ１の要素である。Ｚが、ステップ２０２０においてｔにセットされる。Ｇ１からの未処理イグジット・アークは存在しないので（ステップ２０４０＝ＮＯ）、ステップ１６２０が終了し，ステップ１５８０が終了して，図１５におけるステップ１５９０にコントロールを移す。第１アンロール反復において更なるブロックが存在しないので（ステップ１５９０＝ＮＯ）、Ｓ１がＳ０にコピーされ、Ｓ１がヌルにセットされ，そしてＩが１だけインクリメントされて２の値になる（ステップ１５９４）。従って，Ｓ０は｛ｔ，ｃ，ａ｝を含み、一方、Ｓ１はヌルである。Ｉは，依然として，アンロール係数ＵＦよりも小さいか又はＵＦに等しいので（ステップ１５５０＝ＹＥＳ）、新たなシンボリック・レジスタｕがＹ２に対して割り振られる（ステップ１５６０）。そこで、Ｂが第２のアンロール反復における第１ブロックＢ２にセットされる（ステップ１５７０）。そこで、図１６において詳細に示されるように、Ｂ２がバンプ最適化及び修正のために処理される（ステップ１５８０）。
【００８３】
処理すべき更なるステートメントがＢに存在するので（ステップ１６１０＝ＹＥＳ）、Ｓが、ｂ＝ａであるＢにおける次のステートメントを割り当てられる。Ｓは、Ｒ’＝ｂ及びＲ＝ａを有するコピー・ステートメントである（ステップ１６４０＝ＹＥＳ）。そこで、図１７において詳細に示されるように、コピー・ステートメントＳが処理される（ステップ１６５０）。レジスタａは、現在｛ｔ，ｃ，ａ｝を含むＳ０の要素である（ステップ１７１０＝ＹＥＳ）。その結果，ｂがＳ０に加えられ、結果として｛ｔ，ｃ，ａ，ｂ｝を含むＳ０が生じ、ｂがＳ１から除去されるが、それがＳ１になかったため、これは何もせず、Ｓにおけるａがｔによって置換され，結果として，ｂ＝ｔを示すステートメントＳが生じる。この時点で，ステップ１６５０が終了し，図１６におけるステップ１６１０にコントロールを移す。依然として、処理すべき更なるステートメントがＢ２に存在するので（ステップ１６１０＝ＹＥＳ）、ＳがＢにおける次のステートメント，即ち，ｄ＝ｂ＊２にセットされる。このステートメントは、コピー・ステートメントではなく（ステップ１６４０＝ＮＯ）、可能なバンプ・ステートメントでもないので（ステップ１６６０＝ＮＯ）、図１９に詳細に示されるように、一般ステートメントＳが処理される（ステップ１６８０）。
【００８４】
レジスタｂは、セットＳ０の要素でもあるステートメントＳにおける使用されたレジスタであるので、ｂがステートメントＳにおけるｔによって置換され，その結果，ステートメントｄ＝ｔ＊２が生じる。ステップ１９２０及び１９３０は何もせず、従って、ステップ１６８０が終了し，図１６におけるステップ１６１０にコントロールを移す。処理すべき更なるステートメントがＢ２には存在しないので（ステップ１６１０＝ＮＯ）、図２０において詳細に示されるように，Ｂに対するコピー修正ブロックが加えられる（ステップ１６２０）。レジスタａはステップ２０１０においてＸに対応し、ａはセットＳ１にはない（ステップ２０１０＝ＮＯ）。Ｚが，ステップ２０３０においてｔにセットされる。Ｂ２からの未処理イグジット・アーク、即ち、Ｂ２からＣへのアークが存在する（ステップ２０４０＝ＹＥＳ）。Ａがこのアークに割り当てられる（ステップ２０５０）。そこで、新たなブロックＲＢ２がアークＡに挿入される（ステップ２０６０）。なお、ＲＢ２は、コードａ＝ｔを含む。Ｂ２からの更なる未処理イグジット・アークが存在しないので（ステップ２０４０＝ＮＯ）、ステップ１６２０が終了し、ステップ１５８０が終了して、図１５におけるステップ１５９０にコントロールを移す。第２のアンロール反復には更なるブロックが存在するので（ステップ１５９０＝ＹＥＳ）、Ｂが第２のアンロール反復における次のブロックＤ２にセットされる（ステップ１５９２）。そこで、Ｄ２が、図１６において詳細に示されるバンプ最適化及び修正のために処理される（ステップ１５８０）。
【００８５】
Ｄ２に更なるステートメントが存在するので（ステップ１６１０＝ＹＥＳ）、ＳがＤ２における次のステートメント、即ち、ｃ＝ｂ＋１にセットされる。このステートメントはコピー・ステートメントではなく（ステップ１６４０＝ＮＯ）、Ｒ’＝ｃ及びＲ＝ｂを有する可能なバンプ・ステートメントである（ステップ１６６０＝ＹＥＳ）。そこで、図１８において詳細に示されるように，そのバンプ・ステートメントが処理される（ステップ１６７０）。レジスタｂは，その時点では｛ｔ，ｃ，ａ，ｂ｝を含むＳ０の要素であるので（ステップ１８１０＝ＹＥＳ）、新たなバンプ命令ｕ＝ｒ＋２がＳの前に挿入される（ステップ１８２０）。ステートメントＳにおけるｂがｔと置換され，その結果，ｃ＝ｔ＋１が生じる（ステップ１８３０）。そこで、レジスタｃ及びｕがＳ１（ヌルであった）に加えられ、その結果，｛ｃ，ｕ｝を含み、標本ｕを有するＳ１が生じ、ｃ及びｕがＳ０から除去され、その結果、｛ｔ，ａ，ｂ｝を含むＳ０が生じる（ステップ１８４０）。この時点で、ステップ１６７０が終了し、図１６のステップ１６１０にコントロールを移す。Ｄ２に更なるステートメントが存在するので（ステップ１６１０＝ＹＥＳ）、ＳがＤ２における第２ステートメント，即ち、ａ＝ｃにセットされる。これは，Ｒ’＝ａ及びＲ＝ｃを有するコピー・ステートメントである（ステップ１６４０＝ＹＥＳ）。従って、図１７において詳細に示されるように、コピー・ステートメントａ＝ｃが処理される（ステップ１６５０）。
【００８６】
レジスタｃはセットＳ０の要素ではなく（ステップ１７１０＝ＮＯ）、Ｓ１の要素である（ステップ１７３０＝ＹＥＳ）。その結果，ａがＳ１に加えられる。その結果，｛ｕ，ｃ，ａ｝を含むＳ１が生じる。ａがＳ０から除去され、その結果、｛ｔ、ｂ｝を含むＳ０が生じる。ステートメントＳにおけるｃが表現ｕと置換され、その結果、ａ＝ｕのステートメントＳが生じる（ステップ１７４０）。ステップ１６５０が終了し、図１６におけるステップ１６１０にコントロールを移す。Ｄ２には処理すべき更なるステートメントが存在しないので（ステップ１６１０＝ＮＯ）、図２０において詳細に示されるように、Ｄ２に対するコピー修正ブロックが加えられる（ステップ１６２０）。
【００８７】
レジスタａはステップ２０１０におけるＸに対応し，Ｓ１の要素であるので（ステップ２０１０＝ＹＥＳ）、Ｚがｕにセットされる（ステップ２０２０）。Ｄ２からの未処置イグジット・アーク，即ち、Ｄ２からＦへのアークが存在する（ステップ２０４０＝ＹＥＳ）。Ａがこのアークに割り当てられる（ステップ２０５０）。そこで、新たなブロックＲＤ２がアークＡに沿って挿入される（ステップ２０６０）。この場合，ＲＤ２はコードａ＝ｕを含む。Ｄ２からの更なる未処理イグジット・アークが存在しないので（ステップ２０４０＝ＮＯ）ステップ１６２０は終了し、ステップ１５８０も終了してコントロールを図１５におけるステップ１５９０に移す。第２アンロール反復においてもう１つのブロックＧ２が存在するので（ステップ１５９０＝ＹＥＳ）、Ｂが第２アンロール反復における次のブロックＧ２にセットされる（ステップ１５９２）。そこで，図１６において詳細に示されるように、Ｇ２がバンプ最適化及び修正のために処理される（ステップ１５８０）。
【００８８】
Ｇ２には処理すべき更なるステートメントが存在するので（ステップ１６１０＝ＹＥＳ）、ＳがＢにおける次のステートメント，即ち，「ａ&#8804;１０の場合にブランチ（branch if a&#8804;10）」にセットされる（ステップ１６３０）。このステートメントはコピー・ステートメントではなく（ステップ１６４０＝ＮＯ）、可能なバンプ・ステートメントでもないので（ステップ１６６０＝ＮＯ）、図１９において詳細に示されるように，この一般ステートメントが処理される（ステップ１６８０）。ステップ１９１０は何の効果も持たない。ステップ１９２０がステートメントＳを「ｕ&#8804;１０の場合にブランチ」に変える。ステップ１９３０は何の効果も持たない。これは、ステップ１６８０を終了させ，コントロールを図１６におけるステップ１６１０に移す。Ｇ２には処理すべき更なるステートメントが存在しないので（ステップ１６１０＝ＮＯ）、図２０において詳細に示されるように，Ｇ２に対するコピー修正ブロックが加えられる（ステップ１６２０）。
【００８９】
レジスタａがステップ２０１０におけるＸに対応し、セットＳ１の要素である（ステップ２０１０＝ＹＥＳ）。そこで、Ｚがｕにセットされる（ステップ２０２０）。Ｇ２からの１つの未処理イグジット・アーク、即ち、Ｇ２からＥへのアークが存在する（ステップ２０４０＝ＹＥＳ）。Ａがこのアークにセットされ（ステップ２０５０）、新たなブロックＲＧ２がＡに挿入される（ステップ２０６０）。その場合，ＲＧ２はコードａ＝ｕを含む。Ｇ２からの更なる未処理イグジット・アークが存在しないので（ステップ２０４０＝ＮＯ）、ステップ１６２０が終了し、ステップ１５８０も終了して、コントロールを図１５におけるステップ１５９０に移す。第２アンロール反復において更なるブロックが存在しないので（ステップ１５９０＝ＮＯ）、Ｓ１がＳ０にコピーされ、Ｓ１がヌルにセットされ、そしてＩが１だけインクリメントされて３の値になる（ステップ１５９４）。Ｉは，今や、２のアンロール係数よりも大きいので、ステップ１５５０＝ＮＯであり、ステップ１２３０が終了する。図１３に戻ると、レジスタａモジュロ２がゼロの値を有する場合にブロックＢ１にブランチし、そうでない場合にブロックＢにブランチするためのコードを含む新たなブロックＷが加えられる（ステップ１３７０）。Ｇ及びＧ’からＢへのアークが代わりにブロックＷにリダイレクトされる（ステップ１３８０）。今や、ステップ１０５０が終了し、ステップ８６０も終了して図８における方法８００を終了させる。その結果が図３８の高レベルの制御フローで示される。図３９は、詳細に上述したように、図６のステップ８６０において静的アンローリングを遂行することによって導入された命令に対する変更を伴なう同じ制御フローを示す。
【００９０】
図３９を一見したところでは、コードが大きく改善されたことがわからない。大量の余分な命令が導入された。しかし、望ましい実施例の方法は、図３９の制御フローに関連して実行されるべき幾つかの従来技術の最適化フェーズに依存する。１つのそのような最適化は、前述のHwu 氏他による論文において説明されているオペレーション・マイグレーションである。別の従来技術の最適化は、Morgan KaufmanPublishers 誌（１９９７）の「Advanced Compiler Design and Implementation」と題した Muchnick 氏による論文に記述されており、それは、不要コード除去、コピー伝播、価値番号付け（valuenumbering）、及びブランチ・ストレート化（branch straightening）を含む。ブランチ・ストレート化は、ブロックＧ１及びＢ２を結合する。図３９の制御フローに従来技術の最適化を適用した結果が図４０の制御フローによって示される。
【００９１】
本願において遂行されるバンプ最適化は、各アンロール反復におけるバンプ命令及び関連の命令からの従属性を排除している。従って、遂行される必要のある唯一のバンプ命令は、コントロールがスーパブロックに残っている限り、図４０のブロックＤ２における「ｕ＝ａ＋２」である。コントロールが任意の時点でスーパブロックから抜け出す場合、適切な値がそれらのイグジット・パスだけで回復する。これは、予想されたパス、スーパブロックのオペレーションを非常に効率的にする。低い頻度のパスを通してスーパブロックを離れるときに他のオペレーションのコストを償うだけでよい。或る命令は何回も複製されるので、これはコード・ブロートによって少ないコストで行われ、それら命令の実行の合計数が減少する。
【００９２】
望ましい実施例は、スーパブロックの完全な、静的の、又は動的のアンローリングを遂行することを可能にする。コントロールがスーパブロックを抜け出す場合、ループ・カウンタ値を調整するために、カウント修正が遂行される。スーパブロックをアンロールするための更に精巧な方法を提供することによって、コンピュータ・プログラムに対して更なる最適化が行われ得るし、それによって、それのランタイム・パフォーマンスを増加させる。
【００９３】
本発明の範囲内で多くの変更が可能であることは当業者には明らかであろう。従って、本発明はそれの望ましい実施例に関連して特定的に示され且つ説明されたけれども、形式及び詳細におけるこれらの及びその他の変更が、本発明の精神及び範囲から逸脱することなく行われ得ることは、当業者には明らかであろう。
【００９４】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００９５】
（１）少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに結合されたメモリと、
前記メモリ内にある第１の命令ストリームと、
前記メモリ内にあり、前記少なくとも１つのプロセッサによって実行されるプロファイル・ベースのスーパブロック・アンローラと、
を含み、
前記スーパブロック・アンローラは、プロファイル・データに従って前記第１の命令ストリームにおいてスーパブロックを形成及びアンロールし、実行が該スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含む、
装置。
（２）前記スーパブロック・アンローラによって遂行されるアンローリングのタイプが完全アンローリング、静的アンローリング、および動的アンローリングを含む、上記（１）に記載の装置。
（３）前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用する、上記（１）に記載の装置。
（４）前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、静的アンローリングを使用する、上記（１）に記載の装置。
（５）前記スーパブロック・アンローラは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、上記（１）に記載の装置。
（６）前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外で前記第１の命令ストリームに挿入する、上記（１）に記載の装置。
（７）少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに結合されたメモリと、
前記メモリ内にある第１の命令ストリームと、
前記メモリ内にあり、前記少なくとも１つのプロセッサによって実行されるプロファイル・ベースのスーパブロック・アンローラと、
を含み、
前記スーパブロック・アンローラは、プロファイル・データに従って前記第１の命令ストリームにおいてスーパブロックを形成及びアンロールし、実行が該スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含み、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用し、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、静的アンローリングを使用し、
前記スーパブロック・アンローラは、前記反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、
装置。
（８）前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外で前記第１の命令ストリームに挿入する、上記（７）に記載の装置。
（９）第１の命令ストリームを最適化するための方法であって、
プロファイル・データに従って、前記第１の命令ストリームにおいてスーパブロックを作成するステップと、
前記スーパブロックをアンロールするステップと、
少なくとも１つのカウンタ値を調節して前記スーパブロックからの出口を明確にするために、必要な場合、前記スーパブロックの外にカウント・レクティファイア・コードを提供するステップと、
を含む方法。
（１０）前記スーパブロックをアンロールするステップは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの完全アンローリングを遂行するステップを含む、上記（９）に記載の方法。
（１１）前記スーパブロックをアンロールするステップは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの静的アンローリングを遂行するステップを含む、上記（９）に記載の方法。
（１２）前記スーパブロックをアンロールするステップは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、前記スーパブロックの動的アンローリングを遂行するステップを含む、上記（９）に記載の方法。
（１３）第１の命令ストリームを最適化するための方法であって、
プロファイル・データに従って、前記第１の命令ストリームにおいてスーパブロックを作成するステップと、
前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの完全アンローリングを遂行するステップと、
前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記スーパブロックの静的アンローリングを遂行するステップと、
前記スーパブロックの反復の数がコンパイル時にわかっていない場合、前記スーパブロックの動的アンローリングを遂行するステップと、
少なくとも１つのカウンタ値を調節して前記スーパブロックからの出口を明確にするために、必要な場合、前記スーパブロックの外にカウント・レクティファイア・コードを提供するステップと、
を含む方法。
（１４）（Ａ）プロファイル・データに従って第１の命令ストリームにおいてスーパブロックを形成及びアンロールするプロファイル・ベースのスーパブロック・アンローラと、
（Ｂ）前記プロファイル・ベースのスーパブロック・アンローラを保持するコンピュータ可読信号保持媒体と、
を含み、
前記スーパブロック・アンローラは、実行が前記スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含む、
コンピュータ・プログラム。
（１５）前記コンピュータ可読信号保持媒体は記録可能媒体を含む、上記（１４）に記載のコンピュータ・プログラム。
（１６）前記コンピュータ可読信号保持媒体は伝送媒体を含む、上記（１４）に記載のコンピュータ・プログラム。
（１７）前記スーパブロック・アンローラによって遂行されるアンローリングのタイプは、完全アンローリング、静的アンローリング、及び動的アンローリングを含む、上記（１４）に記載のコンピュータ・プログラム。
（１８）前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用する、上記（１４）に記載のコンピュータ・プログラム。
（１９）前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記静的アンローリングを使用する、上記（１４）に記載のコンピュータ・プログラム。
（２０）前記スーパブロック・アンローラは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、上記（１４）に記載のコンピュータ・プログラム。
（２１）前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外に前記第１の命令ストリームに挿入する、上記（１４）に記載のコンピュータ・プログラム。
（２２）（Ａ）プロファイル・データに従って第１の命令ストリームにおいてスーパブロックを形成及びアンロールするプロファイル・ベースのスーパブロック・アンローラと、
（Ｂ）前記プロファイル・ベースのスーパブロック・アンローラを保持するコンピュータ可読信号保持媒体と、
を含み、
前記スーパブロック・アンローラは、実行が前記スーパブロックを抜け出すときループ・カウンタを調節するように前記第１の命令ストリームに対して少なくとも１つの変更を行うカウント・レクティファイアを含み、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が十分に小さい場合及び前記反復の数がコンパイル時にわかっている場合、完全アンローリングを使用し、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数が完全アンローリングにとって大きすぎる場合及び前記反復の数がコンパイル時にわかっている場合、前記静的アンローリングを使用し、
前記スーパブロック・アンローラは、前記スーパブロックの反復の数がコンパイル時にわかっていない場合、動的アンローリングを使用する、
コンピュータ・プログラム。
（２３）前記コンピュータ可読信号保持媒体は記録可能媒体を含む、上記（２２）に記載のコンピュータ・プログラム。
（２４）前記コンピュータ可読信号保持媒体は伝送媒体を含む、上記（２２）に記載のコンピュータ・プログラム。
（２５）前記カウント・レクティファイアは、前記スーパブロックからの出口を明確にするために少なくとも１つのカウンタ値を調節する少なくとも１つのブロックを前記スーパブロックの外に前記第１の命令ストリームに挿入する、上記（２２）に記載のコンピュータ・プログラム。
【図面の簡単な説明】
【００９６】
【図１】望ましい実施例によるコンピュータ・システムのブロック図である。
【図２】従来技術のコンパイラ・システムのブロック図である。
【図３】図２のコンパイラ・システムを使用してソース・コードをコンパイルするための従来技術方法におけるステップを示す流れ図である。
【図４】従来技術において知られているスーパブロックの標準的なアンローリングを示す流れ図を示す流れ図である。
【図５】プロファイル・データによって示されるようにコードを通してホット・パスを示すサンプルの制御流れ図である。
【図６】図５に示された制御流れ図からスーパブロックを生成するための従来技術の方法の流れ図である。
【図７】図６におけるスーパブロックが、図４における従来技術の方法による標準的なアンローリングを使用してアンロールされる方法を示す制御流れ図である。
【図８】望ましい実施例に従ってスーパブロックをアンロールするための方法の流れ図である。
【図９】望ましい実施例に従ってスーパブロックの完全なアンローリングを遂行するための方法の流れ図である。
【図１０】望ましい実施例に従ってスーパブロックの静的アンローリングを遂行するための方法の流れ図である。
【図１１】望ましい実施例に従ってスーパブロックの動的アンローリングを遂行するための方法の流れ図である。
【図１２】望ましい実施例に従って完全なアンローリングのためにカウントを修正するための方法の流れ図である。
【図１３】望ましい実施例に従って不完全なアンローリングのためにカウントを修正するための方法の流れ図である。
【図１４】望ましい実施例に従って一定の修正ブロックを加えるための方法の流れ図である。
【図１５】望ましい実施例に従ってバンプ最適化及び修正を遂行するための方法の流れ図である。
【図１６】望ましい実施例に従ってバンプ最適化及び修正のためにブロックを処理するための方法の流れ図である。
【図１７】望ましい実施例に従ってコピー・ステートメントを処理するための方法の流れ図である。
【図１８】望ましい実施例に従ってバンプ・ステートメントを処理するための方法の流れ図である。
【図１９】望ましい実施例に従って一般ステートメントを処理するための方法の流れ図である。
【図２０】望ましい実施例に従って１つの選択されたブロックのためにコピー修正ブロックを加えるための方法の流れ図である。
【図２１】望ましい実施例に従ってスケーリング修正ブロックを加えるための方法の流れ図である。
【図２２】望ましい実施例に従って逆修正ブロックを加えるための方法の流れ図である。
【図２３】望ましい実施例に従って残りの修正ブロックを加えるための方法の流れ図である。
【図２４】サンプルの制御流れ図である。
【図２５】望ましい実施例に従ってスーパブロック形成後における図２５のサンプルの制御流れ図である。
【図２６】図２５のスーパブロックを３回完全にアンロールした後におけるサンプルの制御流れ図である。
【図２７】望ましい実施例に従ってカウント修正コードを加えた後における図２６の制御流れ図である。
【図２８】サンプルの制御流れ図である。
【図２９】スーパブロック形成後及びスーパブロックを３回アンロールした後における図２８の制御流れ図である。
【図３０】望ましい実施例に従ってカウント修正コードを加えることを伴う図２９の制御流れ図である。
【図３１】サンプルの制御流れ図である。
【図３２】スーパブロック形成後及びスーパブロックを３回アンロールした後における図３１の制御流れ図である。
【図３３】望ましい実施例に従って或るカウント修正コードを加えることを伴う図３２の制御流れ図である。
【図３４】望ましい実施例に従って更なるカウント修正コードを伴う図３３の制御流れ図である。
【図３５】サンプルの制御流れ図である。
【図３６】スーパブロック形成後における図３５の制御流れ図である。
【図３７】望ましい実施例に従ってスーパブロックを２回アンロールした後における図３６の制御流れ図である。
【図３８】望ましい実施例に従って或るカウント修正コードを加えた後における図３７の制御流れ図である。
【図３９】望ましい実施例に従って変更された命令を示すために拡張されたブロックを伴う図３８の制御流れ図である。
【図４０】幾つかの従来技術の最適化を適用した後における図３９の制御流れ図である。
【符号の説明】
【００９７】
１００  コンピュータ・システム
１１０  プロセッサ
１２０  メイン・メモリ
１３０  大容量記憶装置インターフェース
１４０  ディスプレイ・インターフェース
１５０  ネットワーク・インターフェース
１５５  ＤＡＳＤ
１６５  ディスプレイ
１７５  他のコンピュータ・システム
１９５  記録可能媒体
【図１】
2004152287.tif 000003
【図２】
2004152287.tif 000004
【図３】
2004152287.tif 000005
【図４】
2004152287.tif 000006
【図５】
2004152287.tif 000007
【図６】
2004152287.tif 000008
【図７】
2004152287.tif 000009
【図８】
2004152287.tif 000010
【図９】
2004152287.tif 000011
【図１０】
2004152287.tif 000012
【図１１】
2004152287.tif 000013
【図１２】
2004152287.tif 000014
【図１３】
2004152287.tif 000015
【図１４】
2004152287.tif 000016
【図１５】
2004152287.tif 000017
【図１６】
2004152287.tif 000018
【図１７】
2004152287.tif 000019
【図１８】
2004152287.tif 000020
【図１９】
2004152287.tif 000021
【図２０】
2004152287.tif 000022
【図２１】
2004152287.tif 000023
【図２２】
2004152287.tif 000024
【図２３】
2004152287.tif 000025
【図２４】
2004152287.tif 000026
【図２５】
2004152287.tif 000027
【図２６】
2004152287.tif 000028
【図２７】
2004152287.tif 000029
【図２８】
2004152287.tif 000030
【図２９】
2004152287.tif 000031
【図３０】
2004152287.tif 000032
【図３１】
2004152287.tif 000033
【図３２】
2004152287.tif 000034
【図３３】
2004152287.tif 000035
【図３４】
2004152287.tif 000036
【図３５】
2004152287.tif 000037
【図３６】
2004152287.tif 000038
【図３７】
2004152287.tif 000039
【図３８】
2004152287.tif 000040
【図３９】
2004152287.tif 000041
【図４０】
2004152287.tif 000042