(57)【特許請求の範囲】
【請求項１】
コードのある部分についてストリップ・サイズに基づいてループのストリップマイニング最適化を実行するに先立ってコードの前記部分に関する距離ベクトルを更新するコンピュータ・プログラミング・ロジックを有し、前記距離ベクトルは、各要素が前記コードの前記部分の対応するループの反復の数である２つの反復ベクトルの差である、コンパイラを記録したコンピュータ読み取り可能な記録媒体において、前記コンパイラは、
前記最適化の前にコードの前記部分の前記距離ベクトルを記憶しておき、
前記記憶された距離ベクトルｄをストリップサイズssで割った値についての下限関数および上限関数を含む予め定めた式にしたがって前記記憶された距離ベクトルを更新する機能を実現することを特徴とする、コンピュータ読み取り可能な記録媒体。
【請求項２】
前記式は、第１および第２の関係からなり、該第１の関係は、第１および第２の要素を含み、該第１の要素が下限関数であり、該第２の要素がモジューロ関数である請求項１に記載の記録媒体。
【請求項３】
前記第２の関係は、第１および第２の要素を含み、該第１の要素が前記記憶された距離ベクトルをストリップサイズで割った上限関数であり、該第２の要素が前記記憶された距離ベクトルをストリップサイズで割った上限関数とストリップサイズとの積を該距離ベクトルから引いた値である、請求項２に記載の記録媒体。
【請求項４】
前記記憶された距離ベクトルは前記ストリップサイズ未満であり、
前記式は第１および第２の関係からなり、
前記第１の関係は第１および第２の要素からなり、
前記第１の関係の第１の要素は０であり
前記第１の関係の第２の要素は前記記憶された距離ベクトルであり、
前記第２の関係は第１および第２の要素からなり
前記第２の関係の第１の要素は１であり、
前記第２の関係の第２の要素は前記記憶された距離ベクトルから前記ストリップサイズを引いたものである請求項１に記載の記録媒体。
【請求項５】
ストリップ・サイズに基づくループのストリップマイニング最適化の実行に先立って前記ループに関する距離ベクトルｄを更新するコンピュータ・プログラミング・ロジックを有し、前記距離ベクトルは、各要素が前記コードの前記部分の対応するループの反復の数である２つの反復ベクトルの差である、コンパイラを記録したコンピュータ読み取り可能な記録媒体であって、前記コンパイラは、
前記最適化の前にコードの前記部分の前記距離ベクトルｄを記憶しておき、予め定めた式にしたがって前記記憶された距離ベクトルを更新する機能を実現し、
前記ストリップサイズの値ssは、d/ssが整数となる値であり、
前記式は、前記記憶された距離ベクトルｄを前記ストリップサイズssで割る第１の要素、および０である第２の要素をもつ、
ことを特徴とする、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、一般的にはシステムコンパイラの最適化に関し、特にコンパイラがプログラムコード上のループストリップ化の最適化を実行した後の距離ベクトルの更新に関する。
【０００２】
【従来の技術】
従属性の分析はメモリ参照順序の制約条件となる規則群であり、コンパイラによって決定される。たとえば、あるプログラムが順次実行されるときメモリ参照Ｂがメモリ参照Ａに続く場合、あるいはＡとＢが同じ記憶場所を参照する場合、メモリ参照Ｂはメモリ参照Ａに従属するものとみなされる。メモリ参照には従属性があり、メモリ参照はプログラム言語のセマンティクス（ｓｅｍａｎｔｉｃｓ：意味論）よって要求される順序で発生するよう制約される。メモリ参照の従属性には２つの割り当ての発生順序を制約する出力従属、割り当てより先に使用を発生するように制約する逆従属、割り当てを使用より先に発生するように制約するフロー従属および２つの使用の発生順序を制約する入力依存等がある。他の従属性としては、ある動作を制御フローがその動作の実行が可能なものであるかを判定するテストの後に発生するよう制約する制御従属、および入力に続いて動作が発生するように制約する動作従属がある。
【０００３】
図１にはユーザーがなんらかの高級言語で書いたプログラムからなるソースファイル１１を有する典型的なコンパイル環境１０の全体的構造を示す。ファイル１１がコンパイラ１２によって処理されてオブジェクトファイル１３が得られ、オブジェクトファイル１３は通常ソースファイル１１の高級ソース・ステートメントの翻訳結果である一連の機械命令からなる。オブジェクトファイル１３はその後リンカープログラム１４によって処理され、リンカープログラム１４はオブジェクトファイル１３を他のソースファイル（図示せず）から得られた他のオブジェクトファイル１５と組み合わせて実行可能なプログラム１６を生成する。実行可能なプログラム１６はコンピュータ１７上で直接実行することができる。したがって、このプログラムはなんらかの入力１８を読み出し、処理を実行し、なんらかの出力１９を生成する。従属性分析およびループの最適化は通常図１に示すコンパイラの一部として実行される。
【０００４】
図２は図１のコンパイラ１２を最適化したものの内部構造の図である。このタイプのコンパイラはソースファイル１１をオブジェクトファイル１３に翻訳するだけではなく、作成されたオブジェクトファイルのランタイム性能の改善をはかるものである。このコンパイラはソースファイル１１から始まる。このコンパイラのフロントエンド２１によってソースファイルが読み込まれ、構文エラーあるいはセマンティクスエラーがチェックされる。エラーがないものとすると、コンパイルが進行し、フロントエンド２１が中間表現２２を生成する。オプティマイザ２３がコードの実行を高速化する変換を実行することによって、中間表現２２の構造の改善そしてそれによってランタイム性能の改善をはかる。最終ステップではオブジェクトファイル１３が生成され、これは通常オブジェクトファイル発生器２４によってコンパイラのバックエンドで実行される。
【０００５】
図３には図２に示すオプティマイザ２３の内部構造を示す。このオプティマイザはコンパイルされる各プロシージャの最適化されていない低レベルの中間表現３１から始めて、各プロシージャについて最適化された中間表現３５を生成する。最初の段階は、実行可能な最適化を判定するための中間表現の分析３２である。ここでは、コンパイルされるプロシージャのループ構造を認識し、従属性の分析を実行する。第２の段階は、コードに対してループの最適化を含むさまざまな最適化を実行し、可能なところでは距離ベクトルを更新することである。規則上、あるいは距離ベクトルが管理不能となったためにそれ以上の最適化が不可能となったとき、オプティマイザは命令のスケジューリングやレジスタの割り当てといった最適化後段階３４を実行する。その結果最適化された中間表現３５が得られ、これがオブジェクトファイル発生器２４によって処理されてコンパイルされたオブジェクトコード１３が得られる。
【０００６】
プログラムの内部表現の各ノードは潜在的に多くの異なるランタイム参照を表わす。ノードＮＡからノードＮＢへの従属性のファミリーはノードＮＡへの潜在的なランタイム参照およびノードＮＡへのランタイム参照の間の従属性の集合である。ノード間でコンパイラが描く弧はかかるファミリーの表現である。たとえば、コードブロック（ＣＯＤＥ  ＢＬＯＣＫ）１に示すループについては、コンパイラはｘ（ｉ＋１）  ＝  からｘ（ｉ）への弧を描き、それにラベルを付してコードブロック２に示す従属性のファミリーを表現する。
【０００７】
【表１】
0003545938.tif 000002
【０００８】
メモリ参照はある数の周囲のループ内で発生する。反復ベクトル識別子はそれらのループのどの反復において特定のノードが特定のメモリ参照を生じさせるかを同定する。そのノードにnの周囲ループがある場合、ある参照の反復ベクトルはnタプル（tuple）である。このNタプルの各要素は対応する周囲ループの反復数であり、最も外側のループは最初の要素に対応し、以下同様である。たとえば、コードブロック3は、３深の入れ子ループすなわちDo i、Do j、Do kを有するプログラムフラグメントを示し、各ループは１ずつステップし、各ループの上限はnである。ループ本体はxと呼ばれる配列の３次元配列要素への１つの参照からなる。１次元の添字はi+1、２次元はj+2、３次元はk+3である。割り当てx(3,7,4)に対する反復ベクトルは、０原点反復ベクトルの場合（1,4,0）である。１原点反復ベクトルの場合、ベクトルは（2,5,1）である。０原点を用いるとすべての可能なプログラム言語に対応可能である。フォートランは、１原点を用いており、適当にスキューされる。
【０００９】
【表２】
0003545938.tif 000003
【００１０】
距離ベクトルは２つの反復ベクトルの間の差である。たとえば、表２のコードブロック4は２深の入れ子型ループすなわちDo i、Do jを有するプログラムフラグメントを示し、各ループは１ずつステップし、各ループの上限はnである。ループ本体は２次元配列yへの割り当てへの１つの参照からなり、y(i+3,j-1) = y(i,j)である。y(4,4)=およびy(4,4)に対する反復ベクトルはそれぞれ（0,4）および（3,3）である。距離ベクトルは（3,3）マイナス（0,4）であり、これは（3,-1）である。ある符号規定については、宛先に対する反復ベクトルが減算の最初に来る。符号規定は分析全体を通して一貫して適用されるかぎりは重要ではない。距離ベクトルは、いつも、非単位ストライドを有するループにつては添字の減算によって計算しうるとは限らないことに注意されたい。
【００１１】
方向ベクトルは距離ベクトルの符号である。つまり、方向ベクトルは距離ベクトルの各要素を＋１，０および／または−１で置き換えることによって実現される。たとえば、（３，−１）の距離ベクトルは（＋１，−１）の対応する方向ベクトルを有する。方向ベクトルは通常数字ではなく記号を用いて書かれる。＋１は“＜”で、０は“＝”で、−１は“＞”で書かれる。したがって、（３，−１）の距離ベクトルは（＜，＞）で表わされる。“＞”記号は反復回数の増大を、“＜”記号は反復回数の減少を示す。
【００１２】
従属性のファミリーは均一であることが多く、これはそのファミリーの従属性は同じ距離ベクトルと方向ベクトルを有することを意味する。CODE BLOCK 4のループについていえば、y(i+3,j-1)=からy(i,j)への従属性ファミリーは均一である。したがって、（3,-1）はファミリ距離ベクトル、（＜,＞）はファミリー方向ベクトルとみなすことができる。
【００１３】
スーパーコンピュータのコンパイラには機械のアーキテクチャをより有効に利用するためにユーザーによって入力されたプログラムコードを実際に変換する最適化技術が用いられる。たとえば、並列処理機械の場合、ステップ２の完了を待ってステップ３に移行するように動作を順次実行する代わりに、機械はプログラムを書き直してステップ２とステップ３を同時に処理することを可能とする。コンパイラは従属性分析を実行してこのタイプの変換が合法であるかどうかを判定する。この変換が合法である場合、ユーザーは速度をたとえば５倍にも上げることができ、しかも従属性分析からその結果が正しいものであることが保証される。変換が不法なものである場合、コンパイラはそのコードをそのまま実行し、変換を行なわない。
【００１４】
コンパイラが最適化しうる領域の１つとしては、反復構造すなわちループがある。たとえば、あるプログラムの一部がマトリクスの異なる行と列を乗算するマトリクス乗算を実行するように書かれる。このコンパイラはさまざまな変換を用いることによって、コードのその部分をより高速にランしながら正しい結果が得られるように書き直しうることを判定することができる。
【００１５】
変換を実行する前に、コンパイラはプログラム中のすべてのループネストおよび各ネストにおける参照対について従属性分析を実行して反復スペースと周囲ループ内での参照の持続時間中での参照のメモリ制約条件を判定する。この情報は通常コンパイラに距離（すなわち従属性）ベクトルおよび方向ベクトルとして記録される。距離ベクトルの長さは参照のおよぶ共通するループの数であり、ベクトル内の各要素はメモリ従属距離である。方向ベクトルは２つの参照の反復ベクトルから距離がただちに判定できない場合に使用することができる。
【００１６】
このコンパイラが通常実行するループ変換の１つは距離ベクトルを用い、ループ・ストリップ・マイニング（ｌｏｏｐ  ｓｔｒｉｐ−ｍｉｎｉｎｇ）あるいはループ・ブロッキング（ｌｏｏｐ  ｂｌｏｃｋｉｎｇ）と呼ばれる。このループ変換によれば、ループを部分ごとに実行することによってループのオーバーヘッドが低減される。これによって、ループを処理するさいにキャッシュメモリをより多く再使用することができる。通常、機械はレジスタ以外にプロセッサに非常に近く配置されたキャッシュメモリシステム（たとえばＬ２キャッシュ）を有し、遠隔のＲＡＭメモリよりも待ち時間が短い。しかし、キャッシュの再ローディングを行なう場合時間および性能上のペナルティが生じる。このペナルティはコスト上昇につながり、キャッシュロード数を低減する方が有益である。
【００１７】
ストリップ・マイニングは、ループがキャッシュ内に収まるように変換することによってキャッシュロードの数を低減する。ループは内側のループが各キャッシュ行にアクセスし、外側のループがキャッシュ全体にアクセスするように追加のループを加えることによって変換される。このタイプの変換はスーパーコンピュータにおけるベクトル処理から並列処理にいたるまで広く用いられ、キャッシュメモリの待ち時間を短縮している。この変換はプログラムコードになかった追加ループを導入し、変換されたループの配列要素の添字をもとのループと新たなループの両方の関数になるように変更する。
【００１８】
コードブロック５および６にストリップ・マイニングすなわちブロッキングの例を示し、これらはそれぞれブロッキングすなわちストリップ・マイニングの後２ループのネストとなる１ループのネストを示す。コンパイラは、各ループネストについてプログラム全体の従属性をいったん計算する。これは、実際にはペア型のアルゴリズムを用いる非常にコストのかかる処理であり、これはＸの参照については約Ｘ２の可能性があることを意味する。
【００１９】
【表３】
0003545938.tif 000004
【００２０】
コードブロック５は、Ｄｏ  ｉ  ＝  １〜１０、ａ（ｉ＋３）  ＝であり、内部でａ（ｉ）を用いる簡単なループを示す。このコンパイラはコンピュータシステムの特性、特にループのサイズと比較したキャッシュのサイズに基づいてこのループを４つの部分に分けて実行することがより効率的であると判断する。したがって、外側のループが追加され、内側のループの項がコードブロック６に示すように変更され、もとのコードは、Ｄｏ  ｊ  ＝  １〜１０×４およびＤｏ  ｉ  ＝  ｊ〜（ｊ＋４−１，１０）のうちの最小値、に変換され、ａ（ｉ＋３）はａ（ｉ）である。したがって、ｊの値は１、５および９となる。ｉの値はｊとともに変化し、ｊ＝１であるときｉの値は１−４、ｊ＝５であるときｉの値は５−８、ｊ＝９であるときｉの値は９−１０となる。こうしてステップサイズは次の態様で１から４まで変えられる。すなわち、ステップサイズ長である最大４か、あるいはループ反復数がストリップサイズで割り切れない場合にはその剰余まで内側のループが外側のループのストリップを実行する。外側のループをセクションループと呼び、内側のループを要素ループと呼ぶ。
【００２１】
【発明が解決しようとする課題】
従来のコンパイラにおいては、この変換を実行した後にはコンパイラはこのループではそれ以上機能しえず、その結果ブロックされた後にはループを最適化することはできない。これは添字が理解しずらく複雑なものになっているためである。簡単な添字であったものが追加のループによって複雑なものとなっている。さらに、追加ループはもとのコードには存在しておらず、これはもとの距離ベクトルのサイズを再度求めるすなわち計算し直すことが必要であることを意味する。これは、実行すべき従属性分析については、各ループを正規化しなければならず、すなわち各ループが単位に基づき、誘導変数が１で始まり１ずつステップするためにさらに複雑化する。
【００２２】
【表４】
0003545938.tif 000005
【００２３】
たとえば、コードブロック６に示すループネストはコードブロック７および８に示すように正規化される。コードブロック７に示すように外側のループが最初に正規化され、その後コードブロック８に示すように内側のループが正規化される。コードブロック８に示すループネストは従来のコンパイラの従属性分析の入力となる。添字式は連結添字であり、これは各添字が内側と外側のループの誘導変数の両方の関数であることを意味する。これは、距離ベクトルを判定するための簡単な減算を、２つ以上の未知数の解を求めなければならない複雑な計算にする。また、一定した反復スペースすなわち従属距離であったもの（これはＡ（ｉ＋３）とＡ（ｉ）の差すなわち３であった）が、変数になり、誘導変数ｉおよびｊの値に依存するようになる。
【００２４】
従来技術における主たる問題点は、コンパイラがブロッキングまたはストリップ・マイニングを最終のループ変換として実行することである。これは、これ以後はループ境界がｍｉｎ関数およびｍｏｄ関数を含むため、この点以後はいかなる最適化の合法性もテストすることが困難なためである。また、１つのループ誘導経変数の関数である添字はこの段階では複数のループの関数である。従来のコンパイラは、この変換の後に従属性を計算できるとしても、その計算式に多数の新たな変数があるため保守的過ぎる結果を出し、その再計算のために多大なコストが生じる。
【００２５】
さらに、コンパイラが変換のたびに従属性の再計算を行なわねばならないとしたら、その後変換が行なわれるたびに、ループ境界添字が各変換のセマンティクスのために複雑化するため、従属性の情報が失われる可能性が非常に高い。従来のコンパイラは従属性を前もって一度計算し、その後最適化変換の静的な順序づけを実行する。このコンパイラは２つ以上のループ誘導変数の関数である１つの添字があると最適化を停止する。このとき、コンパイラはレジスタを割り当て、機械コードを発する。距離ベクトルおよび方向ベクトルは、コードブロック８の連結添字式から計算するとしたら、次のようになるであろう。
【００２６】
【表５】
0003545938.tif 000006
【００２７】
従来のコンパイラは、正規化のオーバーヘッドコストと連結添字添字式の検討の困難さのためにコードブロック９に示す結果を計算しないことを指摘しておく。コードブロック９は後述する本発明との比較のために示すものである。
【００２８】
したがって、当該技術分野において、コンパイラによる距離ベクトルの更新を可能とし、最適化の非静的順序づけを可能とし、従属性の正規化および再分析のオーバーヘッドの発生を防止し、連結添字式を避け、コンパイルの簡略性と正確性を維持しながらループの互換を可能とすることが必要とされている。
【００２９】
【課題を解決するための手段】
以上およびその他の目的、特徴および技術的利点は２つの関係を用いてコンパイラがループ・ストリップ・マイニングを実行した後に距離ベクトルを更新するシステムおよび方法によって達成される。この発明のコンパイラ・システムは、次の構成をとる。すなわち、コードのある部分の最適化の実行に先だってコードの前記部分に関する距離ベクトルを更新するコンパイラシステムであって、  最適化の前にコードの前記部分の距離ベクトルを記憶する手段と、最適化の評価基準を判定する手段と、評価基準と記憶された距離ベクトルを含む所定の式にしたがって距離ベクトルを更新する手段と、を備えるコンパイラ・システム。
【００３０】
本発明はブロッキングされていないループについてはもとの距離ベクトルを入力とし、その距離をストリップサイズで割った結果が自然数となるかどうかによって１つまたは２つの距離ベクトルを出力する。したがって、本発明は後続の最適化の発生を可能とし、変換されたループの正規化および添字の再計算を不要とする。また、本発明はループの従属性の再分析（これは上述したＮ２の計算であり変換自体によってその入力が複雑化している）を不要とする。
【００３１】
さらに、本発明の出力は最適化に関する任意の合法性試験によって検査することのできる標準的な距離ベクトルフォーマットになっている。また、入力もまた距離ベクトルであり出力と同じ形式であり、これによってブロッキング変換は後続の最適化に対して透明となる。これは、出力が後続の変換の後続の合法性試験への入力となるためである。本発明の正確性と均一性によって、最適化の非静的な順序づけが可能となり、コンパイラはループをブロッキングすることができ、またそれを交換、再交換および再ブロッキングすることが可能である。また、本発明は、添字が２つ以上の誘導変数をもち、２以上の添字位置に現われる連結添字を防止する。本発明は、変換された添字式から距離ベクトルを再計算していくのではなく、もとの距離ベクトルのみを用いる。
【００３２】
以上は次の本発明の詳細な説明の理解をたすけるために、本発明の特徴および技術的利点の概要を説明したものである。本発明の他の特徴および利点については以下に説明され、それらは本発明の特許請求の対象となる。当業者には、ここに開示する概念および具体的実施形態は本発明の目的を達成するための変更および他の構造の設計の基礎として容易に利用しうるものであることが理解されよう。また、当業者にはかかる均等な構造は特許請求の範囲に定める本発明の精神および範囲から逸脱するものではないことも理解されよう。
【００３３】
【発明の実施の形態】
本発明は、２つの関係を用い、ブロッキングされていないループのもとの距離ベクトルをブロッキングされたすなわちストリップ・マイニングされたループの距離ベクトルである１つあるいは２つの距離ベクトルに更新する。得られる距離ベクトルが１つになるか２つになるかは、その距離がストリップサイズによって均等に割り切れて自然数となるかどうかによって決まる。本発明はループのブロッキングすなわちストリップ・マイニングのための従属性の再計算を必要としない。コンパイラは単にコードブロック１０に示す関係を用いてもとの距離ベクトルを更新してストリップ・マイニングされたループの距離ベクトルを決定するだけでよい。
【００３４】
【表６】
0003545938.tif 000007
【００３５】
図４に示すように、コンパイラはもとの距離ベクトルを記憶し（４０）、ストリップ・マイニング最適化の実行の合法性を判定する（４１）。合法である場合、コンパイラはストリップ・マイニング最適化を実行し（４２）、合法でなければ最適化を実行しない（４３）。ストリップ・マイニングの後、コンパイラは記憶された距離ベクトルを用い、コードブロック１０の関係を適用して距離ベクトルを更新する（４３）。距離ベクトルの更新は最適化が合法である場合には最適化の前に行なうことができる。コードブロック１０において、第１の関係には２つの要素があり、第１の要素は距離ベクトルをストリップサイズで割った下限（ｆｌｏｏｒ）を決定するものであることに注意されたい。下限関数は入力の値以下の最大の整数を返す。たとえば、５／２の下限（  ５／２  と表記する場合もある）は２である。ストリップサイズすなわちブロック・マイニング係数はストリップ・マイニングによって作成される外側のループの幅である。第１の関係の第２の要素は距離ベクトルをステップサイズで割ったモジューロである。モジューロ関数（すなわちｍｏｄ）は第１の入力を第２の入力で割った余りを返す。たとえば、１０  ｍｏｄ  ３  は１である。また、第２の関係は２つの要素を有し、その１つが距離ベクトルをストリップサイズで割った上限を決定する。上限関数は入力の値以上で最小の整数を返す。たとえば５／２の上限（  ５／２  と表記する場合もある）は３である。
【００３６】
以下はコードブロック 10をコードブロック 5および6に適用した例である。コードブロック 5の添字式a(i+3)＝a(i)の左辺がa(4)=  のときは、i=1である。これは反復数を０からカウントする（すなわち１回目を０とする）０原点方式では、反復ベクトルが１回目を示す(0)である。右辺がa(4)となるのは、i=4のときであり、０原点方式では、反復ベクトルは４回目を示す(3)である。したがって、+3-0は距離ベクトル（３）に等しい。次に、この距離ベクトルがコードブロック 6で用いられる４のストリップサイズとともにコードブロック 10の２つの関係に適用される。したがって、3/4の下限は０、3/4の上限は１、３を４で割ったモジューロは３となる。これによって、コードブロック 6のストリップ・マイニングされたコードの更新された距離ベクトル（0,3）および（1,-1）が得られる。この結果はコードブロック 9の結果と一致する。
【００３７】
この例はまたコードブロック  １０の関係の２つの特殊なケースの１つを示す。距離ベクトルがストリップサイズ未満であるとき、ｄ／ｓｓの係数は常に１未満である。したがって、ｄ／ｓｓの下限は常に０であり、ｄ／ｓｓの上限は常に１であり、ｄをｓｓで割ったモジューロは常にｄである。したがって、コードブロック  １０の関係は常にコードブロック  １１に示す関係に還元できる。この結果は上で得られた結果と一致する。
【００３８】
第２の特殊なケースは距離ベクトルがストリップサイズの倍数であるとき、たとえば距離ベクトルが４でストリップサイズが２であるときに発生する。このような場合、ｄ／ｓｓの下限がｄ／ｓｓの上限（これはｄ／ｓｓと等しい）と等しくなる。ｄはｓｓで割り切れるため、モジューロは０である。コードブロック  １０の第１および第２の関係はいずれもコードブロック  １２のコードに還元される。第１および第２の関係から同じ結果が生じるため、ストリップマイニングを行なったときもとの距離ベクトルから１つの従属性しか生成されない。この特殊なケースについて別の見方をすると、ｄ／ｓｓが自然数すなわち計数（１、２、３、…）となる場合、コードブロック  １２のコードはコンパイラによる距離ベクトルの更新に用いられる。
【００３９】
距離ベクトルについて、（＜）の方向ループ（正の距離からの）は従属距離がストリップサイズ未満である場合（＝，＜）および（＜，＞）となる。この結果はコードブロック  １１のコードと一致する。（＜）の方向ループは従属距離がストリップサイズより大きい（しかし、コードブロック  １２のようにストリップサイズの倍数ではない）場合（＜，＜）および（＜，＞）となる。したがって、（＜）の方向ループに対する一般的なケースは（＜＝，＜）および（＜，＞）である。
【００４０】
更新関係への入力およびこれからの出力はいずれも距離ベクトルである。上に示したように、ある距離ｄについて、ループがストリップ・マイニングされると、従属距離関係によって１つあるいは２つの従属性が生成され、したがって２つの記憶場所の間の関係について２つ以上の距離ベクトルをもつことがある。２つの従属性が生成されると、それらを１つの従属性ベクトルにまとめることができる。しかし、あいまいさを避けるには、それらを区別しておく方がよい。また、ストリップ・マイニングされていないループのもとの距離ベクトルに１つの要素しかなかった場合、更新された距離ベクトルには２つの要素があることに注意を要する。これは、コンパイラがコードへのブロッキングのために新たなループを導入したためである。ユーザーがこのループを書かなかった場合にも、ストリップ・マイニングの後、コードのこの部分は２ネストのループとなる。したがって、ブロッキングまたはストリップ・マイニングが実行されるたびに追加のループがプログラムコードに作成される。
【００４１】
必要であれば従属性距離ベクトルを計算し直すことなく後続の最適化を容易に実行することができる（４４）。コンパイラは更新された距離ベクトルを用いて後続の最適化の合法性をチェックする。これによって最適化ルーチンの非静的な順序づけが可能である。したがって、コードブロック  １０に示す本発明の関係とコードブロック  １１および１２に示す２つの特殊なケースとによって、コードブロック  ７、８および９に示す更新された距離ベクトルの計算に係るオーバーヘッドコストを避けることができる。また、本発明の関係によれば簡略性、効率および正確性を維持しながらコードブロック  ８に示す連結添字の処理を避けることができる。もとの距離ベクトルはストリップ化最適化の前に記憶され、本発明の関係によって更新される。距離および方向ベクトルは通常レジスタに記憶される。
【００４２】
本発明とその利点を詳細に説明したが、特許請求の範囲に規定する本発明の精神および範囲から逸脱することなくさまざまな変更、代替および改変が可能であることが理解されよう。この発明は、例として次の実施態様を含む。
（１）コードのある部分の最適化（３３）の実行に先だってコードの前記部分に関する距離ベクトルを更新するコンパイラシステム（１２）であって、
前記最適化の前にコードの前記部分の前記距離ベクトルを記憶する手段（４３）、
前記最適化の評価基準を判定する手段、および
前記評価基準と前記記憶された距離ベクトルを含む所定の式にしたがって前記距離ベクトルを更新する手段（４３）からなることを特徴とするコンパイラ・システム。
（２）前記評価基準はストリップサイズであり、
前記最適化はループのストリップ・マイニング（４２）であることを特徴とする上記１記載のコンパイラシステム。
（３）前記所定の式は第１および第２の関係からなることを特徴とする上記２記載のコンパイラシステム。
（４）前記第１の関係は第１および第２の要素を含み、
前記第１の要素は下限関数からなり、
前記第２の要素はモジューロ関数からなることを特徴とする上記３記載のコンパイラシステム。
（５）前記第１の要素は前記記憶された距離ベクトルを前記ストリップサイズで割った下限関数であり、
前記第２の要素は前記記憶された距離ベクトルを前記ストリップサイズで割ったモジューロ関数であることを特徴とする上記４記載のコンパイラシステム。
（６）前記第２の関係は第１および第２の要素を含み、
両方の要素が上限関数からなることを特徴とする上記３記載のコンパイラシステム。
（７）前記第１の要素は前記記憶された距離ベクトルを前記ストリップサイズで割った上限関数であることを特徴とする上記６記載のコンパイラシステム。
（８）前記第２の要素は前記記憶された距離ベクトルから、前記ストリップサイズと前記記憶された距離ベクトルを前記ストリップサイズで割った前記上限関数との積を引いた差であることを特徴とする上記６記載のコンパイラシステム。
（９）前記記憶された距離ベクトルは前記ストリップサイズの倍数であり、
前記所定の式は第１および第２の要素からなり、
前記第１の要素は前記記憶された距離ベクトルを前記ストリップサイズで割ったものであり、
前記第２の要素は０であることを特徴とする上記２記載のコンパイラシステム。
（１０）前記記憶された距離ベクトルは前記ストリップサイズ未満であり、
前記所定の式は第１および第２の関係からなり、
前記第１の関係は第１および第２の要素からなり、
前記第１の関係の前記第１の要素は０であり、
前記第１の関係の前記第２の要素は前記記憶された距離ベクトルであり、
前記第２の関係は第１および第２の要素からなり、
前記第２の関係の前記第１の要素は１であり、
前記第２の関係の前記第２の要素は前記記憶された距離ベクトルから前記ストリップサイズを引いたものであることを特徴とする上記２記載のコンパイラシステム。
【００４３】
【発明の効果】
この発明によると、連結添字式を避け、コンパイルの簡略性と正確性を維持しながらループの互換を可能とすることができる。
【図面の簡単な説明】
【図１】コンパイル環境の全体的構成を示すブロック図。
【図２】図１のコンパイラの内部構造を示すブロック図。
【図３】図２のオプティマイザの内部構造を示すブロック図。
【図４】本発明の関係を用いたストリップ・マイニングの概略を示すブロック図。
【図１】
0003545938.tif 000008
【図２】
0003545938.tif 000009
【図３】
0003545938.tif 000010
【図４】
0003545938.tif 000011