JPH04215133A - コード最適化方法およびコンパイラ・システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、最適化コンパイラに関
するものである。より具体的には、本発明は、コード・
ストリーム中の特定の命令の実行中にマイクロプロセッ
サによって導入されるパイプライン・インターロック遅
延を含むことが知られているコード・ストリーム中に、
選択された命令を挿入することにより、上記遅延を減少
させることに関するものである。

【０００２】

【従来の技術】現在のほとんどのコンピュータ、特に縮
小命令セット・コンピュータ（ＲＩＳＣ）は、演算論理
機構（ＡＬＵ）が、理論的にはクロック速度と実行速度
を１対１で対応させながら、常に実行すべき次の命令を
手にすることができるように、命令パイプラインを使用
している。ハードウェア内のある種の明確な条件の下で
は、以前の計算の結果として命令オペランドが利用可能
になるまで、パイプライン・インターロックによって特
定の命令の実行が阻止される。このインターロックの作
用により、処理サイクルの損失が生じることがある。遅
延、すなわち処理サイクルの損失の最も頻繁な原因は、
条件付き分岐を処理する際に生ずる。この時点で、パイ
プライン中の分岐命令より後の命令はすべて、潜在的に
実行不能である。というのは、この分岐によって、プロ
グラムの制御が異なる命令ストリームに移る可能性があ
るからである。そうである場合には、それらの命令の代
りにその異なる命令ストリームを実行しなければならな
い。このパイプラインの再ロードの間、ＡＬＵは、イン
ターロックの作用により新しい命令ストリームを待ちな
がら、遊休状態でいる。方向変更された命令ストリーム
が、別の潜在的なインターロックを導入する別の条件付
き分岐命令を直接含んでいる場合には、問題はより複雑
になる。

【０００３】常に満たされた命令パイプラインを実現す
るために、これまでにいくつかの試みがなされてきた。

【０００４】初期のＲＩＳＣマシンは、通常なら分岐の
前に実行されるある種の命令が、命令ストリーム中のそ
の分岐命令の後に現れる、後実行形式の分岐命令を提供
した。これによって、ある種の命令が、パイプラインの
再充填中に実行できるようになった。ＩＢＭ　　ＲＴ　
　ＰＣコンピュータ・システムの場合がそうである。

【０００５】命令事前取出し（ｐｒｅ−ｆｅｔｃｈ）の
機会を増やすために、条件レジスタの定義位置と使用位
置の間に挿入すべき適当な命令を見つけることは、「命
令スケジューリング」と称する種類のコンパイラ最適化
の一部であり、本発明の背景の一部である。通常、従来
技術のコード引上げ技法は、並行する実行経路に沿って
発生する計算を探し、これらを両方の経路を支配するノ
ードに引き上げる。その結果生ずるモジュールは、２つ
の計算を１つに置き換えた結果、通常、サイズが小さく
なる。本発明は、パイプラインを満杯に保つため、改良
された上記技法を用いて、条件付き実行の経路に沿った
命令を見つけ、これを引き上げる。その結果、命令は、
基本ブロック境界をまたいでスケジューリングされる。 下記の論文は、命令パイプラインを実行可能な命令で満
杯に保ついくつかの試みの概要を述べたものである。Ａ
ｒｙａ　Ｓ．，　Ｏｐｔｉｍａｌ　Ｉｎｓｔｒｕｃｔｉ
ｏｎ　Ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　ａ　Ｃｌａｓｓ
　ｏｆ　Ｖｅｃｔｏｒ　Ｐｒｏｃｅｓｓｏｒｓ：　Ａｎ
　Ｉｎｔｅｇｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ　Ａｐｐｒ
ｏａｃｈ，　Ｔｅｃｈ．　　Ｒｅｐｔ．　ＣＲＬ−ＴＲ
−１９−８３，　ＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈ　
Ｌａｂｏｒａｔｏｒｙ，　Ｕｎｉｖ．　ｏｆ　Ｍｉｃｈ
．，　Ａｎｎ　Ａｒｂｏｒ、１９８３年４月。Ａｕｓｌ
ａｎｄｅｒ　Ｍ．　ａｎｄ　Ｈｏｐｋｉｎｓ　Ｍ．，　
Ａｎ　Ｏｖｅｒｖｉｅｗ　ｏｆ　ｔｈｅ　ＰＬ．８　Ｃ
ｏｍｐｉｌｅｒ，　Ｐｒｏｃ．　ＡＣＭ　ＳＩＧＰＬＡ
Ｎ　Ｓｙｍｐ．　ｏｎ　Ｃｏｍｐｉｌｅｒ　Ｃｏｎｓｔ
ｒｕｃｔｉｏｎ，　Ｂｏｓｔｏｎ、１９８２年６月、ｐ
ｐ．２２〜３１。Ｇｉｂｂｏｎｓ　Ｐ．　ａｎｄ　Ｍｕ
ｃｈｎｉｃｋ　Ｓ．，　Ｅｆｆｉｃｉｅｎｔ　Ｉｎｓｔ
ｒｕｃｔｉｏｎ　Ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　ａ　
Ｐｉｐｅｌｉｎｅｄ　Ａｒｃｈｉｔｅｃｔｕｒｅ，　Ｐ
ｒｏｃ．　ＳＩＧＰＬＡＮ’８６　Ｓｙｍｐ．　ｏｎ　
Ｃｏｍｐｉｌｅｒ　Ｃｏｎｓｔｒｕｃｔｉｏｎ，　Ｐａ
ｌｏ　Ａｌｔｏ、１９８６年、ｐｐ．１１〜１６。Ｇｒ
ｏｓｓ　Ｔ．Ｒ．，　Ｃｏｄｅ　Ｏｐｔｉｍｉｚａｔｉ
ｏｎ　ｏｆ　Ｐｉｐｅｌｉｎｅ　Ｃｏｎｓｔｒａｉｎｔ
ｓ，　Ｔｅｃｈ．　Ｒｅｐｔ．　８３−２５５，　Ｃｏ
ｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ　Ｌａｂ．，　Ｓｔａｎ
ｆｏｒｄ　Ｕｎｉｖ．、１９８３年１２月。Ｈｅｎｎｅ
ｓｓｙ　Ｔ．　Ｌ．　ａｎｄ　Ｇｒｏｓｓ　Ｔ．Ｒ．，
　Ｐｏｓｔｐａｓｓ　Ｃｏｄｅ　Ｏｐｔｉｍｉｚａｔｉ
ｏｎ　ｏｆ　ＰｉｐｅｌｉｎｅＣｏｎｓｔｒａｉｎｔｓ
，　ＡＣＭ　Ｔｒａｎｓ．　ｏｎ　Ｐｒｏｇ．　Ｌａｎ
ｇ．　ａｎｄ　Ｓｙｓ，　Ｖｏｌ．　５、１９８３年７
月、ｐｐ．４２２〜４４８。Ｓｉｔｅｓ，　Ｒ．Ｌ．，
　Ｉｎｓｔｒｕｃｔｉｏｎ　Ｏｒｄｅｒｉｎｇ　ｆｏｒ
　ｔｈｅ　Ｃｒａｙ−１　Ｃｏｍｐｕｔｅｒ，　Ｔｅｃ
ｈ．　Ｒｅｐｔ．７８−ＣＳ−０２３，　Ｕｎｉｖ．　
ｏｆ　Ｃａｌｉｆ．，　Ｓａｎ　Ｄｉｅｇｏ、１９７８
年７月。

【０００６】コンパイル時パイプライン・スケジューリ
ングに関する研究は、比較的乏しい。Ｇｉｂｂｏｎｓ　
ｅｔ　ａｌ．（１９８６年）、Ｇｒｏｓｓ（１９８３年
）、Ｈｅｎｎｅｓｓｅｙ　ｅｔ　ａｌ．（１９８３年）
および　Ｓｉｔｅｓ（１９７８年）は、コード生成およ
びレジスタ割振りの後のパスの間に行われるスケジュー
リングについて考察している。レジスタ割振り前の命令
スケジューリングは、Ａｕｓｌａｎｄｅｒ　ｅｔ　ａｌ
．（１９８２年）によって記述されたＩＢＭ　　ＰＬ．
８コンパイラを含めて、いくつかのコンパイラで実施さ
れているが、いずれの参照論文でも、スケジューリング
は基本ブロック内でのみインターロックを減少すること
に限定されている。

【０００７】

【発明が解決しようとする課題】これらの試みにも関わ
らず、プログラムの制御が多数の基本ブロック境界にま
たがって流れる際に命令パイプライン内に存在する、潜
在的に実行不能なコードによって引き起こされる遅延を
減少させる方法が必要である。

【０００８】

【課題を解決するための手段】現在のところ、制御シー
ケンスの適当な位置にあるコードを制御シーケンスの他
の部分へ引き上げることによって、マイクロプロセッサ
が遊休状態となるクロック・サイクルの数を、減少でき
ることがわかっている。引上げは、計算を有向グラフの
任意のノードからそのノードを支配するノードへ移す、
コード移動技法の１種として定義される。

【０００９】したがって、本発明は、コンピュータ内の
命令のシーケンスによるクロック・サイクルの利用を改
善する方法であって、 （ａ）前記命令を制御フローグラフ中で表すステップと
、 （ｂ）前記フローグラフ内の第１ノードから検索して、
オーダが少なくとも２のテキスチャである部分グラフを
識別するステップと、 （ｃ）前記の各テキスチャについて、 （ｉ）あるオーダのテキスチャを形成する子ノード内の
命令を検査し、 （ｉｉ）各命令が引上げ可能であるか否かを判定し、（
ｉｉｉ）前記命令が引上げ可能である場合、前記子ノー
ドからの前記命令をその親テキスチャに組み合わせるス
テップと、 （ｄ）子ノードがなくなるか、または前記親ノードに固
有の遅延が除去されるまで、各子ノードについてステッ
プ（ｉ）ないし（ｉｉｉ）を繰り返すステップとを含む
方法を含む。

【００１０】また、本発明は、コンピュータ上で実行さ
れるプログラムを最適化するための改良されたコンパイ
ラであって、 （ａ）前記プログラムを命令のシーケンスとして表す手
段と、 （ｂ）前記プログラムの制御フローを制御フローグラフ
として表す手段と、 （ｃ）前記フローグラフ内の第１ノードから検索して、
オーダが少なくとも２のテキスチャである親ノードを識
別する手段と、 （ｄ）前記親ノードの各子ノードを検査する手段と、（
ｅ）各子ノードがその親ノードに移動できる命令を含む
か否かを判定する手段と、 （ｆ）前記命令を前記親ノードに移動する手段と、（ｇ
）前記の各子ノードのすべての命令が移動されたか否か
を判定する手段と （ｊ）前記親ノードに固有の遅延が除去されたか否かを
判定する手段とを含む、コンパイラを含む。

【００１１】

【実施例】本開示で用いる用語は、当業者には周知であ
るが、意味を明確にするためここで定義する。「基本ブ
ロック」とは、分岐、戻り、プロシージャの終わりもし
くは、ラベルまたは入口点の直前の命令で終わる、命令
のシーケンスである。「拡張基本ブロック」とは、プロ
シージャの入口点またはラベルから始まり、次の拡張基
本ブロックの境界またはプロシージャの終わりで終了す
る、命令のシーケンスである。「折り込み（ｃｏｌｌａ
ｐｓｉｎｇ）」とは、それによってエッジが取り去られ
、ブロック境界が拡張されて、その結果、各ノードが基
本ブロックではなく拡張基本ブロックを表す、下記に定
義するフローグラフが得られる、フローグラフ縮小の任
意選択処理である。基本ブロックではなく拡張基本ブロ
ックからなる縮小フローグラフが、当業者に理解される
他のある種の最適化に必要な前提条件となることがある
。「フローグラフ」とは、最適化される部分プロシージ
ャまたは関数内の可能な制御フローを表すすべてのノー
ドとエッジを含む有向グラフである。ただし、各ノード
は基本ブロックを表し、各エッジは可能な制御フローを
表す。「戻りエッジ」とは、フローグラフの任意のノー
ドから出て、支配ノードに入る、フローグラフ内のエッ
ジである。「支配」とは、フローグラフの最初のノード
から、支配されるノードへ向かうすべての経路が、支配
ノードを通るという、あるノードと別のノードとの関係
である。「部分グラフ」とは、有向グラフ内のノードと
それらのノードで始まるまたは終わるすべてのエッジと
のサブセットである。基本ブロックは、「ウィーブ」と
「ウェブ」の２つの成分に分割できる。分岐命令が存在
する場合、ウェブ成分は分岐命令であり、ウィーブはそ
の基本ブロックのそれ以外のすべての命令である。「ウ
ィーブ」は、「入口エッジ」と称するそこに入るエッジ
をいくつか備えた、フローグラフ内のノードであり、そ
の後に続くのは「ウェブ」だけである。任意のノードに
入るエッジは、それを含むフローグラフ内の戻りエッジ
でもあるが、そのエッジが同じ基本ブロックから発して
いるのでない限り、そのノードの入口エッジとは見なさ
れない。「ウェブ」とは、ただ１つの入口エッジと任意
の数の出口エッジを備えた、フローグラフ内のノードで
ある。この定義により、ウェブは必ず１つのウィーブに
よって支配される。このような出口エッジの１つは、「
リーディング・エッジ」と称し、そのウェブ内の最後の
命令のフォールスルー経路が存在する場合は、それを表
すエッジである。他のすべての出口エッジは、「トレー
リング・エッジ」と称する。「オーダ」とは、ウェブに
適用される用語であって、出口エッジの数を表す。「テ
クスチャ」とは、ちょうど１つのウィーブ・ノードと１
つのウェブ・ノードとを含む部分グラフであって、その
オーダはそれに含まれるウェブのオーダによって定義さ
れ、その入口エッジはそのウィーブの入口エッジである
。すなわち、条件付き分岐命令で終わる入口エッジが１
つの基本ブロックは、オーダが２のテキスチャである。 そのウェブ成分はこの条件付き分岐のみを含み、この基
本ブロック内のそれ以前のすべての命令は、ウィーブ成
分である。「親」とは、オーダが２のテキスチャである
。親テキスチャに続くものは、すべて子として識別され
る。「適格な」（以下、「子」と呼ぶ）とは、ある識別
された親テキスチャに続く、フローグラフ内のノードで
ある。子ノードは、何らかのオーダのテキスチャとして
分類できるが、親が子を支配する場合にのみ適格と見な
される。

【００１２】上記の定義に従って定義した時、テキスチ
ャ、ウェブおよびウィーブは、データ・フロー解析で、
制御フローによってスケジューリングが導入される機会
を生み出す。

【００１３】本発明は、当業者には容易に理解されるよ
うに、アセンブラまたは中間言語のレベルを含めて、ソ
フトウェア・プログラムをコンパイルする際に最適化ス
テップが実行される各レベルで適用することができる。 本発明は中間言語レベルで適用することが好ましい。当
技術分野で知られているように、中間レベルの言語とは
、人間がコード（しばしば「ソース」と称する）を書く
際に用いる高水準言語と、実際のプロセッサがプログラ
ミングされる機械コードの間のステップである。

【００１４】新しいＲＩＳＣシステムには、多数の条件
レジスタと分離式の分岐復号機構を備えたものがあり、
比較結果が実際の条件付き分岐よりも十分以前にわかる
場合には、命令取出しの方向を変更して、命令パイプラ
インが絶対に実行不能な命令を含まないようにすること
が可能である。本発明は、このようなシステムに特に適
している。というのは、分岐復号機構と演算論理機構が
分離していないシステムよりも、多くの形式の命令を引
き上げることができるからである。

【００１５】図１を参照すると、本発明の好ましい実施
例が有向フローグラフで示されている。本発明の方法の
最初のステップでは、最適化すべきプログラムが、命令
のシーケンスとして表される。このプログラムは、固有
の制御フローを有し、それが分析された後フローグラフ
によって表される。開始ノード０から始めて、フローグ
ラフの深さ優先検索（ＤＦＳ）を使用することによって
、オーダ２のテキスチャとして分類できる基本ブロック
が識別される。図１では、本発明でノードが検査される
順序を示すために、ノードにＤＦＳの順序で番号が付け
てある。ノード１、２、５および８はそれぞれ、２つの
出口エッジを有するので、オーダが２のテキスチャであ
る。

【００１６】本発明によって定義される最適化を実行す
る際、これらのノードは親として識別される。この識別
された親テキスチャの後継ノードのうち、オーダが幾つ
のテキスチャであってもよいが、その先行ノードが親だ
けであるノードは、その親の子ノードとなる。図１では
、ノード１の後継ノードであるノード２と８、ノード２
の後継ノードであるノード３と７、およびノード８の後
継ノードであるノード９と１０が、前記親テキスチャの
子ノードである。

【００１７】このグラフ内の各エッジは、任意のノード
の下端から出て、別の任意のノードの上端に入るものと
して図示されている。たとえば、ノード０からノード１
に向かうエッジは、ノード０から出てノード１に入ると
いわれる。

【００１８】親テキスチャ・ノード５と子テキスチャ・
ノード１の間のエッジが戻りエッジであることを除いて
、親子関係はすべて同一である。しかしながら、この場
合には、戻りエッジが存在すると、親テキスチャ・ノー
ド５に固有の分岐遅延を減少させようと試みる際に、ノ
ード１のウィーブ成分が適格な候補命令を含んでいると
見なされる資格を失うのに十分な理由となる。戻りエッ
ジのゆえに、テキスチャ・ノード５はノード１を支配せ
ず、したがってノード１は、テキスチャ・ノード５の適
格な子ノードではない。それ以外の場合は、両方の子の
ウィーブ成分がなくなるか、または親に固有の分岐遅延
が除去されるまで、それぞれの子のウィーブ成分が、引
上げ可能な候補の命令があるかどうか交互に検査される
。その後、引上げの候補である命令が、親のウィーブ成
分に組み合わされる。

【００１９】この成分を組み合わせる処理は、子成分か
らの候補命令を、対応する親成分に連結することを伴う
。候補命令を識別する処理は、本来的に機械によって変
わり、したがって、本明細書に開示された判断基準と方
法が与えられれば、どの命令が候補になるかは、使用さ
れる特定の機械用のコンパイラを記述する分野の当業者
には自明であろう。しかし、ほとんどの機械では、命令
セットのうちで、レジスタの内容のみに影響を及ぼして
、疑似的な副作用を伴わないサブセットが引上げ可能で
ある。任意選択として、コンパイラ設計の対象となる機
械ごとにルックアップ・テーブルを設ける。このような
テーブルは、特定の機械上で引上げ可能であるタイプの
命令のリストを含んでおり、これはその機械用のコンパ
イラを書く当業者の手で容易に用意できる。あるコード
・シーケンス内の所与の命令が引上げ可能であるか否か
を判定するステップの間に、その機械用のルックアップ
・テーブルを参照して、合否の回答を得る。

【００２０】親テキスチャのリーディング・エッジが子
の入口エッジであり、子のウィーブ成分がなくなった場
合、子のウェブ成分を親のウェブ成分と組み合わせて、
親の中により高いオーダのテキスチャを形成することに
よって、その子は親の中に折り込まれる。たとえば、図
１では、子ノード３または７のうちどちらかリーディン
グ・エッジ上にある方が、その子ノード内のすべての命
令がこの引上げ変換によってなくなった場合、親ノード
２に折り込まれることになる。親のトレーリング・エッ
ジが子の入口エッジである場合、子のウィーブ成分が親
のウィーブ成分と組み合わされる。ウェブ成分は変化し
ないままである。子ノードからの選択は、制御フローが
子ノードのうちの一方を優先することがわかっているか
否かに応じて、順に行っても、何らかの優先順序に従っ
てもよい。

【００２１】一般に発生するコード構成は、ＩＦ−−Ｔ
ＨＥＮステートメントである。図１に示したような制御
フローグラフで表すと、このようなステートメントのパ
ターンは、２つの子ノード９および１０を有する親テキ
スチャ８として現れる。図示の構成は、親テキスチャが
２つの子ノードを有し、一方の子ノードがもう一方の子
ノードからの入口エッジを有する形式である。ノード９
を通る経路はノード１０のみにつながり、したがってノ
ード１０は、２つの親テキスチャすなわちノード８とノ
ード９の両方を有すると考えることができる。ノード９
に達するのは“ＩＦ”の条件が満足された場合であり、
ノード１０は、その条件が満足されなかった場合のフォ
ールスルー経路を表している。ノード９はオーダが１で
ある、すなわち出口エッジが１つだけあり、これはノー
ド１０につながっている。原則としては、子ノードが引
上げ可能と見なされるには、入口エッジを１つだけもた
なければならないのだが、それにもかかわらずこの“Ｉ
Ｆ−−ＴＨＥＮ”型のフローグラフ・パターンは、引上
げ可能な命令を含むことができる。多くの形式のプログ
ラムでは、このようなパターンがかなりの数存在し、本
発明の方法に従った引上げにより、コンパイル済みのオ
ブジェクト・コード・プログラムを改善するための大き
な機会をもたらす。図１のノード８、９および１０に示
すようなコード・パターンに出会った時、本発明による
コンパイラは、ノード９の命令をノード８に引き上げ、
かつノード１０の命令をノード８に引き上げることがで
きる。ノード１０からノード９への引上げは、ノード９
のオーダが１なので、この特別な場合でも有利にはなら
ないはずである。

【００２２】プログラムは、その実行時間のほとんどを
、最も深くネストされた経路で費やすことが判明してい
る。したがって、深さ優先検索は、最も頻繁に発生する
可能性の高い命令遅延を招くので、これを検索ステップ
に使用することが好ましい。これらの遅延を最初に最小
にすると、より深いレベルの検索から引き上げられた候
補命令を使って、それより低いレベルの検索での遅延を
短縮することもできるという追加の利益が得られる。 下降形検索ではなく深さ優先検索が最も好ましいのは、
このためである。下降形検索を使用することも可能であ
るが、本発明の方法によって引き上げられる可能性のあ
る命令をすべて見つけるには、通常は、全レベルですべ
てのノードを数回検査する必要がある。

【００２３】例１ 本発明の好ましい実施例の１例では、多数の条件レジス
タを有するＲＩＳＣマシンを使用する。これらの例で、
引上げの候補命令には、Ｓ（減算）、Ａ（加算）、Ｃ（
算術比較）およびＣＬ（論理比較）が含まれる。話を簡
単にするために、その他すべての命令は、引上げ不能で
あると仮定する。本発明をコードの断片に適用する目的
は、比較命令と、プログラムの流れを異なる命令ストリ
ームに方向変更させる可能性のある条件付き分岐との間
のインターロックによって引き起こされる遅延を減少さ
せることである。比較命令は、条件付き分岐ＢＴおよび
ＢＦで使用される条件レジスタ（ｃｒｘ）を定義する。

【００２４】本発明の方法による最適化の好ましい実施
例の１例は、図２のＣプログラムの断片によって表され
るプログラム・セグメントである。これは、３つの値域
（−１．．１０）、（２０．．３０）、（５０．．９０
）のうちのいずれかの中にある試験変数の値に基づいて
、特定の処置を選択する。

【００２５】コンパイルの最初のステップで、図２にＣ
で示した最適化すべきプログラムが、図３に中間コード
の形式で示すように、命令のシーケンスとして表される
。制御の流れが、図４に示すように、分析された後、フ
ローグラフによって表される。開始ノード０から始めて
フローグラフの深さ優先検索（ＤＦＳ）を用いることに
よって、オーダ２のテキスチャとして分類できる基本ブ
ロックが識別される。図４では、ノード０、ノード１お
よびノード２がそれぞれこのようなテキスチャであり、
それぞれ２つの出口エッジを有する。ノード０の出口エ
ッジは記号（ｂ）および（ｇ）を付したエッジであり、
ノード１の出口エッジは記号（ｄ）および（ｈ）を付し
たエッジであり、ノード２の出口エッジは記号（ｆ）お
よび（ｉ）を付したエッジである。さらに、エッジ（ｂ
）、（ｄ）、（ｆ）はリーディング・エッジであり、エ
ッジ（ｇ）、（ｈ）、（ｉ）はトレーリング・エッジで
ある。

【００２６】ＤＦＳ中にテキスチャとして識別された各
基本ブロックは、そのウィーブ成分およびウェブ成分に
再分割される。ノード０はノード８およびノード９に分
割される。ノード８は、この基本ブロックの終わりをマ
ークする条件付き分岐以外のすべての命令を含む、ウィ
ーブ成分である。ノード９は、その条件付き分岐だけを
含むウェブ成分である。図４で（ａ）として識別される
エッジは、テキスチャ・ノード０のウェブ成分とウィー
ブ成分を結び付けるエッジである。このエッジは、条件
付き分岐命令が条件レジスタｃｒ１３４を規定する比較
命令に近接しているために存在する、パイプライン遅延
サイクルの数によって特徴づけられる。図３の命令番号
４にある原命令ストリームを参照すると、この遅延は３
サイクルであることがわかる。

【００２７】ＤＦＳの後退の間に、この例で検査すべき
最初のテキスチャは、ノード２であり、このとき子ノー
ド３および６を有する親ノードであると見なされる。エ
ッジ（ｅ）も、上記エッジ（ａ）と同様の３サイクルの
遅延を含むものとして特徴づけられる。この２つの子ノ
ードの命令ストリームを検査して、テキスチャ・ノード
２のウィーブ成分、すなわちノード１２に引き上げるべ
き候補命令を識別する。この例では、どちらの子にも候
補命令が存在しない。しかし、ノード３は、実際には空
のウィーブ成分を有するテキスチャであり、親のリーデ
ィング・エッジが子の入口エッジであるという条件を満
足している。このエッジはエッジ（ｆ）である。したが
って、ウェブ成分のノード１３とノード３を連結した後
、エッジ（ｆ）を取り除くことによって、ノード３が親
テキスチャ・ノード２に折り込まれる。

【００２８】ＤＦＳ後退の次の部分の間には、ノード１
が、子ノード２および５を有する親ノードと見なされる
。ノード２の場合と同じく、子ノードを検査して候補命
令を探す。この例では、ノード５には候補が存在しない
が、ノード１２の内容全体、すなわちテキスチャ・ノー
ド２のウィーブ成分が引上げ可能な命令であり、このそ
れぞれが引き上げられて、ノード１０、すなわち親テキ
スチャ１のウィーブ成分の一部になる。ウィーブ・ノー
ド１２がなくなったので、子テキスチャの内容は、ノー
ド２、３および６に関して上記で見たものと同様になる
。したがって、親テキスチャ・ノード１と子ノード２の
ウェブ成分とは、親のリーディング・エッジが、空のウ
ィーブを有する子の入口エッジであるという条件を満足
しているので、折り込まれる。次にそのエッジ、（ｄ）
が除去される。図５は、この時点で得られた親テキスチ
ャを示す図である。このテキスチャは、オーダが３であ
る。

【００２９】最後に、ＤＦＳから後退して、テキスチャ
・ノード０を考慮にいれ、本発明の方法をノード２およ
び１と同様にして部分グラフ全体に適用すると、図６に
示した、最終的な最適化されたコード・ストリームが得
られる。図６では、条件付き分岐命令のほとんどのサイ
クル数が０に減らされたことがわかる。わかりやすくす
るために、図６には原命令番号が示してある。

【００３０】例２ ロード命令Ｌも引上げ可能になるように、引上げ可能な
命令に関して異なる制約を仮定した場合、図４のフロー
グラフのエッジ（ｉ）、（ｈ）および（ｇ）に沿って命
令を引き上げることから生ずる別のコード・ストリーム
が生成されるはずである。前の例では、これらのエッジ
上の子ノード、ノード６、５、４は、それぞれテキスチ
ャ・ノード２、１、０のウィーブ成分であるノード１２
、１０、９に引き上げるべき候補命令を含んでいなかっ
た。例１の場合、ロードに対する制約が、これらの各子
ノードに含まれる加算命令に対して間接的な制約を加え
た。この制約は、ロードが引上げ不能であるため、先行
するロード命令が完了するまで加算オペランドの一方が
使用不能なので、加算を引き上げてはならないというこ
とである。加算は引上げ可能な候補であるにもかかわら
ず、この場合の加算命令は、ロードに従属しており、し
たがってそのロードより前に移動してはならない。この
型式の制約が特定の環境に適用されることは、その環境
でのプログラム作成の熟練者には明白である。ロード命
令に対する制約が緩和されたと仮定すると、ロードを引
き上げる場合、加算も引上げ可能になる。図７の、その
結果得られるコード・ストリームを参照すると、このよ
うな加算命令が１つ、すなわち命令番号２２が引き上げ
られたことがわかる。この最適化に続いて、条件付き分
岐命令１０の遅延が０に減らされる。この遅延は、以前
の制約が有効であったときは１サイクルであった。

【００３１】例３ ３つではなく２つの命令の分岐遅延が除去されるという
、もう１つのより簡単な例を以下に示す。

【００３２】例４ ２つの命令の分岐遅延が除去されるという、もう１つの
例を以下に示す。この場合、ＳＴ命令は、変数への記憶
を表す。この例では、一部の当業者に知られているなん
らかの他の最適化では、効率を高めるため、ユーザ指定
のラベルＬＬに先行するすべての実行経路で、変数ａ、
ｂ、ｃの値をそれぞれレジスタｒ１００、ｒ２００、ｒ
３００に事前ロードすべきことがわかっていると仮定す
る。この結果パイプライン遅延が生ずるが、その遅延を
含む基本ブロックはスケジュール可能な命令を含んでい
ないので、この遅延は本発明の適用によってしか除去で
きない。

【００３３】従来技術では、レジスタ割振りより以前の
コードの並べ替えは、いくつかの理由から奨励されなか
った。第１に、スケジューリングによってレジスタの寿
命が延びる傾向があり、レジスタの寿命が長いと、余分
なレジスタ・スピル・コードが導入される傾向があるの
で、「良好な」レジスタ割振りを得ることが難しくなる
。第２に、命令間に存在するある種のインターロックの
特性が、レジスタの割当てが完了するまでわからない。 第３に、コード生成の時点で最適化を実行する場合、特
に異なる中間コードを用いる場合には、各コンパイラが
何らかの形態の最適化を実施しなければならない。しか
し、レジスタ割振りと命令選択の後に適用される技法が
、ハンド・コーディングされたアセンブリ・コードにも
適用できる。

【００３４】本発明は、いくつかの利益を提供すること
によって、これらの欠点を克服する。レジスタ寿命が引
き延ばされるにもかかわらず、この引き延ばしの性質は
、レジスタの「定義位置」が、単に直線状のコードの前
の方に移動するのではなくて、フローグラフの高位側の
ノードに引き上げられることに起因している。これは、
ループ外に、あるいは少なくとも「ジャム領域」（レジ
スタ資源利用度が最大の領域）の中心から離れたところ
へ計算を移す効果に類似している。この引上げの結果と
してレジスタ・スピル・コードが発生する場合、それは
、「活領域分割」を用いてジャム領域を短くする際に、
フローグラフのより高い位置に挿入される可能性が高い
。第２に、現在の機械は、通常、旧式の装置よりも多数
のレジスタ・セットを使用しており、十分なレジスタが
利用可能な場合には、ほとんどのプログラムはスピル・
コードを含まない。好ましい実施例では、レジスタ割振
り処理の前には未知であった新しいインターロック状況
が、レジスタ割振り処理によって導入されない。 高水準言語に向かう傾向が増大し、汎用最適化機能およ
びコード生成機能が使用されるので、上述した複数の実
施様態のコストは、急速に小さくなってきている。本発
明の方法は、いかなる最適化コンパイラとも使用可能で
あり、例えばＦＯＲＴＲＡＮ、Ｃ、ＰＡＳＣＡＬ、ＰＬ
／Ｉなど、単一の最適化機能とコード生成機能を有する
いくつかのコンパイラで試験済みである。

【００３５】テスト・ケースでの相対的な性能利得は、
この種のパイプライン遅延に起因して失われるサイクル
時間の量に応じて大きく変わる傾向がある。適当な量の
パイプライン遅延を含むテスト・ケースでは、性能利得
が３０％もの高さになることがある。コンパイル時のコ
ストは、利用された機会の数と検索の固定オーバヘッド
との和に比例し、その合計は通常コンパイル時間の１％
以下である。上述したように、最も頻繁に実行される、
遅延を減少させる引上げの機会を最初に見つけるので、
深さ優先検索が下降形検索よりも好ましい。また、深さ
優先検索は、下降形検索よりもオーバヘッドが少ない。

【００３６】本発明のスケジューリング技法は、プログ
ラムによって最終的に選択される実際の実行経路とは無
関係に、条件付き実行経路から計算の引上げを実行する
が、そうでなければ、引き上げられた計算を計算するの
に必要なサイクルが完全に失われるはずであるという利
益が、これを補って余りある。この技法は、外部から提
供される何らかのデータによって、特定の実行経路の確
率がコンパイル時にわかっている場合、当業者には既知
の方法によって、条件付き制御経路の適当な側からの引
上げが有利になるように、容易に修正することができる
。

【００３７】

【発明の効果】本発明は、コード・ストリーム内の特定
の命令の実行中に、マイクロプロセッサによって導入さ
れるパイプライン・インターロック遅延を含むことがわ
かっているコード・ストリーム内に、選択された命令を
挿入することによって、上記遅延の減少を実現する。

【図面の簡単な説明】

【図１】基本ブロックを形成する１つまたは複数の命令
を表すノードを有する、典型的なプログラムの断片の制
御フローグラフである。

【図２】３つの範囲（−１．．１０）、（２０．．３０
）、（５０．．９０）のうちのいずれかに含まれる値が
あるか否かをテストする多岐分岐を伴う、Ｃ言語のソー
ス・コードの断片を示す図である。

【図３】図２に含まれるソース・テキストの可能な、中
間言語表現を示す図である。

【図４】図３の中間言語表現から導出された制御フロー
グラフである。

【図５】図４のノード１に根を持つ部分グラフに本発明
を適用した後の、ノード１のテキスチャである。

【図６】本発明を適用した後の、図２に含まれるソース
・テキストの最適化された中間言語表現である。

【図７】本発明を適用した後の、図２に含まれるソース
・テキストの別の最適化された中間言語表現である。

Claims (13)

【特許請求の範囲】
1. 【請求項１】コンピュータ内の命令のシーケンスによる
   クロック・サイクルの利用を改善する方法であって、（
   ａ）前記命令を制御フローグラフ中で表すステップと、 （ｂ）前記フローグラフ中の第１ノードから検索して、
   オーダが少なくとも２のテキスチャである部分グラフを
   識別するステップと、 （ｃ）前記の各テキスチャについて、 （ｉ）あるオーダのテキスチャを形成する各子ノード内
   の命令を検査し、 （ｉｉ）各命令が引上げ可能であるか否かを判定し、（
   ｉｉｉ）前記命令が引上げ可能である場合、前記子ノー
   ドからの前記命令をその親テキスチャに組み合わせるス
   テップと、 （ｄ）子ノードからのすべての候補命令がなくなるか、
   あるいは前記親ノードに固有の遅延が除去されるまで、
   各子ノードについてステップ（ｉ）ないし（ｉｉｉ）を
   続行するステップとを含む方法。
2. 【請求項２】前記検索が深さ優先検索である、請求項１
   に記載の方法。
3. 【請求項３】前記検索が下降形検索である、請求項１に
   記載の方法。
4. 【請求項４】さらに、子ノード内のすべての命令が親テ
   キスチャに移動されたか否かを判定し、そうである場合
   には前記子ノードを前記親テキスチャに折り込むステッ
   プを含む、請求項１に記載の方法。
5. 【請求項５】前記テキスチャが、２つの子ノードを有す
   る親テキスチャを含み、前記子ノードの一方が、前記子
   ノードの他方からの入口エッジを有する、請求項１に記
   載の方法。
6. 【請求項６】命令が引上げ可能であるか否かを判定する
   前記ステップが、前記改良を達成すべき特定の機械用の
   、前記機械上で引上げ可能な命令のリストを含む、ルッ
   クアップ・テーブルを選択するステップと、前記命令が
   前記ルックアップ・テーブル内で見つかるか否かを判定
   するステップを含む、請求項１ないし５のいずれかに記
   載の方法。
7. 【請求項７】コンピュータ上で実行されるプログラムを
   最適化するための改良されたコンパイラであって、（ａ
   ）前記プログラムを命令のシーケンスとして表す手段と
   、 （ｂ）前記プログラムの制御フローを制御フローグラフ
   として表す手段と、 （ｃ）前記フローグラフ中の第１ノードから検索して、
   オーダが少なくとも２のテキスチャである部分グラフを
   識別する手段と、 （ｄ）前記部分グラフのリストを作成する手段と、（ｅ
   ）前記検索から出る手段と、 （ｆ）オーダが少なくとも２のテキスチャを有する、前
   記ノードの各子ノードを検査する手段と、（ｇ）各子ノ
   ードが、オーダが少なくとも２のテキスチャを有する前
   記部分グラフに移動できる命令を含むか否かを判定する
   手段と、 （ｈ）前記命令を前記親ノードに移動する手段と、（ｉ
   ）前記の各子ノード内のすべての命令が移動されたか否
   かを判定する手段と （ｊ）前記親ノードに固有の遅延が除去されたか否かを
   判定する手段とを含むコンパイラ・システム。
8. 【請求項８】前記検索手段が深さ優先検索を実行する、
   請求項７に記載のコンパイラ・システム。
9. 【請求項９】前記検索手段が下降形検索を実行する、請
   求項７に記載のコンパイラ・システム。
10. 【請求項１０】さらに、前記子ノードを前記親ノードに
    折り込む手段を含む、請求項７に記載のコンパイラ・シ
    ステム。
11. 【請求項１１】前記テキスチャが、２つの子ノードを有
    する親テキスチャを含み、前記子ノードの一方が、前記
    子ノードの他方からの入口エッジを有する、請求項７に
    記載のコンパイラ・システム。
12. 【請求項１２】さらに、前記改良を達成すべき特定の機
    械用の、前記機械上で引上げ可能な命令のリストを含む
    、ルックアップ・テーブルを含む、請求項７ないし１１
    のいずれかに記載の改良されたコンパイラ・システム。
13. 【請求項１３】システム上で実行されるプログラムを最
    適化するための命令のセットを含むデジタル・データ処
    理システムであって、 （ａ）前記プログラムをデジタル・データ処理シーケン
    スとして表す手段と、 （ｂ）前記プログラムの制御フローを制御フローグラフ
    として表す手段と、 （ｃ）前記フローグラフ中の第１ノードから検索して、
    オーダが少なくとも２のテキスチャであるノードを識別
    する手段と、 （ｄ）前記オーダが少なくとも２のテキスチャのリスト
    を作成する手段と、 （ｅ）前記検索から出る手段と、 （ｆ）オーダが少なくとも２のテキスチャを有する、前
    記ノードの各子ノードを検査する手段と、（ｇ）各子ノ
    ードが、オーダが少なくとも２のテキスチャを有する前
    記ノードに移動できる命令を含むか否かを判定する手段
    と、 （ｈ）前記命令を前記親ノードに移動する手段と、（ｉ
    ）前記の各子ノード内のすべての命令が移動されたか否
    かを判定する手段と、 （ｊ）前記親ノードに固有の遅延が除去されたか否かを
    判定する手段とを含むシステム。