JPH06507990A - コンピュータのための最適化コンパイラ - Google Patents

Abstract

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

Description

【発明の詳細な説明】 コンピュータのための最適化コンパイラ発明の分野 本発明はソースコートコンパイラに関し、より詳細には、ソースコードを中間コ ードに変換し、緊急の際に、この中間コードを再構成して中間コードが目的コー ドに変換される前にその性能を最適化するためのシステムに関する。

発明の背景 コンパイラは、ソースコートを機械（目的）コードに変換するための多重ルー・ チンを含むプログラムである。一般的に、コンパイラは高レベルソース言語（例 、Ｃ１フォートラン等）を取り、これを順次の中間フォーマットコートに翻訳す る。

依存性解析（ｄｅｐｅｎｄｅｎｃｙ　ａｎａｌｙｓｉｓ）が中間コードステート メントについて実行される。この解析は、与えられた結果を生じるにはどのオペ ランドが必要かを決定し、処理オペレーションの期間中の正しいシーケンスにお いて且つ正しい時間においてこれらのオペランドが使用可能になるようにせしめ る。これに続いて、コンパイラは中間コードステートメントをよりコンパクトな フォーマットを特徴とする副中間フオームに変換する一般の最適化ルーチンを実 行する。例えば、”デッ）”（ｄｅａｄ）”コードは除去され、共通副次式（Ｃ Ｏｍｍｏｎ　５ｕｂｅｘｐｒｅｓｓｉｏｎｓ）は消され、他の圧縮技術が実行さ れる。これらの最適化処置は、コードがある手順にかけられ、次に最適化の効率 性を決定するための中間試験を何ら行うことなく次の最適化手順に進むという意 味において、基本的に開ループである。これに続いて、最適化されたコードステ ートメントは機械言語（目的コート）に変換される。一般的に、斯がるコンパイ ル済みコートは直接実行され、結果として生じるコードの効率を決定するために パフォーマンス測定（ｐｅｒｆｏｒｍａｎｃｅ　ｍｅａｓｕｒｅ）にはかけられ ない。　要約すれば、コンパイテ最適化手順は、中間コードストリングの中の個 別ステートメントを選択し、これらのステートメントを最適化手順のリストを通 過せしめるという意味で、基本的に開ループである。一旦これらの手順が完成さ れると、コードは目的コードに変換され、更なるパフォーマンス測定にはかけら れない。最近、高度な並列式コンピュータの出現により、コンパイルタスクはよ り複雑になっている。金玉コンパイラは、並列処理ハードウェアにより、はぼ無 競合条件で、メモリにおけるデータの効率的な記憶とメモリからのそのデータの 直後の可用性との両方を保証する必要がある。従ってコンパイラはベクトル／並 列コード構成の識別及び形成に関連するのと同程度の注意をもってメモリサブシ ステムからの取り出しとデータ構造記憶の基本的問題を処理しなければならない 。

ベクトルプロセッサ及びシストリックアレイ（ｓｙｓｔｏｌｉｃ　ａｒｒａｙ） は、データがこれらのユニットの両端においで転送渋滞にまきこまれる場合は、 はとんど使い物にならない。はぼ無競合のアクセスを達成するために、中間コー ドを最適化手順を通して実行して、その性能特徴が改良されたと希望”するのは 十分ではない。更に、複雑なソースコードリストを完全にコンパイル／最適化し て、次に、所望性能レベルを達成するのに付加的なコード変換が必要か否かを決 定する前に、その結果生じる目的コードのパフォーマンスをパフォーマンス測定 に対して比較することを要求されることは不十分である。

コンパイテ最適化に関する先行技術は、ここ数年にわたって現れて来た以下の論 ステートメントによって特徴付けられている。シュネック他は”フォートランか らフォートランへの最適化コンパイラ”　（コンピュータジャーナル、第１６巻 、１６号、３２２−３３０頁、１９７２年）の中で、機械コードレベルではな（ ソースコードレベルにおけるプログラムパフォーマンスの改良を目的とする初期 のコンパイラについて記載している。１９７４年に、カック他は′通常フォート ランプログラムにおける並列性の測定”　（コンピュータ、１９７４年１月、３ ７−４６頁）の中で、一つのプログラムから出来るだけ多くの同時実施可能オペ レーションを抽出する幾つかの初期の努力についで記載している。この処置の目 的は、そのオペレーションの特定のものを並列に実効せしめることによりフォー トランプログラムのパフォーマンスを改良することであった。

順次マイクロコードを並列又は水平マイクロコードに変換するための最適化手順 がご　トレーススケジューリング　グローバルマイクロコード４７８４９０のた めの技術”にフィッシャーによって述べられている。そのための高度に並列化さ れたマルチプロセッサ及びコンパイル技術がフィッシャによって“ＶＬＩＷ機械 　科学的コートをコンパイルするためのマルチプロセッサ”　（コンピュータ、 １９８４年７月、４５−５３頁）に且つギュプタ他によって”再構成可能ＬＩＷ アーキテクチュアのためのコンパイル技術”　（ザ、ジャーナルオブスーパーコ ンピューティング、第３巻、２７１−３０４頁、１９８９年）に述べられている 。

フィッシャ及びギュプタ他は両者共、非常に長い命令ワードが用いられている高 度に並列化されたアーキテクチュアにおける最適化の諸問題を扱っている。ギュ プタ他は、改良されたパフォーマンスを達成するために領域スケジューリング、 システムの再構成のための世代コード、及びメモリ割り当て技術等のコンパイル 技術について述べている。この点に関して、レフ他は”多次元シストリックアレ イへのマツピングネスティングループアルゴリズム”　（並列及び分布システム についてのＩＥＥＥ会報、第１巻、１号、１９９０年１月２５日、６４−７６頁 ）の中で、コンパイル手順の一部として、ループアルゴリズムが如何にしてシス トリックＶＬＳＩアレイにマツピングされ得るかについて述べている。

上記に引用された先行技術は開ループ手順について述べている。詳細には、一旦 コードが”最適化”されると、目的コードに変換され、次に機械実施のために出 力される。

＆盟９１杓 ソースコードリストを目的コードリストにコンパイルする（ｃｏｍｐｉｌｉｎｇ ）ための方法が記載されており、この方法は、ソースコートリストからソースコ ードステートメント（ｓｔａｔｅｍｅｎｔｓ）のブロックを抽出する段階、ブロ ックにおける各ソースコードステートメントを目的の形のワイド中間コード（ｗ ｌｃ）ステートメントすなわちソースコードステートメントによって要求された 諸機能を実行するために一組の機械処置を確定するＷＩＣステートメントにマツ ピングする段階、ブロックにおける各ＷＩＣステートメントの初期近似シミュＬ ｉ−’ｉヨンヲ実行し、各ＷＩＣステートメントのシミュレーション及びＷＩＣ ステートメントのブロックからパフォーマンス結果（ｐｅｒｆｏｒｍａｎｃｅｒ ｅｓｕｌｔｓ）を引き出す段階、パフォーマンス結果に依存して、コードのパフ ォーマンスを改良することを試みてブロックにおけるＷＩＣステートメントを一 重のコード変換アルゴリズム及びヒユーリスティックの一つに従って修正する段 階、及びパフォーマンス結果が改良されているか否かを決定するために近似シミ ュレーションを反復し、改良されている場合、決定点に達するまで、ＷＩＣステ ートメントの更なる修正を可能にするべくこれらのアルゴリズムの別のアルゴリ ズムに進み、斯かる時間において、修正されたＷＩＣステートメントを目的コー ドの形で生成する段階、を含んでいる。

図面の説明 図１は、演算部を構成する下部構造の構成における変化を可能にする先行技術の 演算部パイプライン組織及びスイッチングネットワークの部分ブロック図である 。

図２は、図１のシステムに用いられている”三重構造“処理下部構造のブロック 図である。

図３は、図１のシステムに用いられている”二重構造”処理下部構造のブロック 図である。

図４は、図１のシステムに用いられている”−重構造”処理下部構造のブロック 図である。

図５−８は、本発明の方法の高レベルフロー図を示す。

＆咀の詳鯉を脱里 ここに開示されているコンパイラ発明の方法の詳細を説明するに先立ち、先ず、 特にこの方法を実施するに構成されたコンピュータの構造を検討することにする 。

記載されようとしているコンピュータの詳細がノーゼンチャック他による且つ本 出願と同じ譲り受け人に譲り受けられた米国特許第４．８１１．２１４号に記載 されている。この米国特許第４．８１１．２１４号の開示は本明細書に参照とし て引用されている。

該米国特許第４．８１１．２１４号において、同時に作動する少数の強力なノー トを用いている高度に並列化されたコンピュータが記載されている。任意の与え られたノート（ｎｏｄｅ）内では、コンピュータは、多くの機能ユニット（例、 浮動小数点演算プロセッサ、整数演算／論理プロセッサ、特殊目的プロセッサ等 ）を用いており、これらの機能ユニットは、これらの機能ユニットの、全てでは なくても、大部分が与えられたノートの各クロックサイクルの期間中に能動状態 になるように同期的な力学的に再構成可能なパイプラインに組織されている。

コンピュータの各ノートは、再構成可能演算／論理ユニット（ＡＬＵ）、多面メ モリ、及びメモリ平面と再構成可能ＡＬＵとの間のデータのルーティング（ｒｏ ｕｔｉｎｇ）のためのメモリーＡＬＵネットワークスイッチを含む。図１におい て、高レベルフロー図は特別に要求されたパイプライン処理構造を提供するため に組織され得る複数の再構成可能下部構造と共に典型的なＡＬＵパイプラインス イッチングネットワークを示している。各再構成可能パイプラインプロセッサは 、種々の階級の処理エレメント（又は下部構造）及びスイッチングネットワーク １１から構成されている。３つの永久的に配線された下部構造１２．１４、及び １６がＡＬＵパイプラインプロセッサにおいて各々特定の回数反復されており、 それらの相対的相互接続をスイッチングネットワーク１１によって変化せしめる ように構成されている。

下部構造１２は、図２のブロック図レベルにおいて更に詳細に示されており、こ れ以降、三重構造と呼ばれる。各三重構造は、３つのレジスタファイル２ｏ、２ ２、及び２４．３つの浮動小数点ユニット２６．２訳及び３０．並びに一つの整 数論理ユニット３２を含んでいる。この三重構造には４つの入力があり、その内 ２つは各々レジスタファイル浮動小数点ユニット対（例、２ｏ、２６及び２２． ２８）についている。唯一っの出力３４が存在する。この三重構造への入力はス イッチ１１を通過する（図１）が、メモリあるいは別の演算／論理構造の出力か ら来得る。各三重構造からの出力はスイッチ１１に至り、ここから別の演算、／ 論理構造の入力にあるいはメモリに送られ得る。

他の処理下部構造が図３及び４に示されており、図３は二重下部構造３６を示し ており、図４は一重下部構造３８を示している。上記の下部構造の各々は図２に 示されている三重構造の部分集合であり、一つ少ない入力を各々許容することが 分かる。

米国特許第４．８１１．２１４号に記載されているコンピュータは何方ものフィ ールドを有する非常に長い命令ワード（ＶＬＩＷ）について作動する。各ＶＬＩ Ｗの緒フィールドの諸部分はコンピュータの各処置に対して構成されるように要 求されている処理構造を画定している。実際、ＶＬＩＷ命令のこれらの部分は所 要処理機能が行われるようにするためにシステムの再構成を形成する。

上記に述べたように、コンピュータはかなりの数の独立プロセッサを含んでおり 、これらの独立プロセッサの各々はサブルーチン全体あるいはサブルーチンの一 部分のどちらかを他のプロセッサと並列に扱う。その結果、ＶＬＩＷ構造と組合 わさった各コンピュータノードの高度に再構成可能な特性により、複雑な問題の 処理の取り扱いに高いフレキシビリティが得られることが分かる。しかしながら 、このフレキシビリティと共に、コストが、即ち、コンピュータがそのコードを 最小の消費時間で実施することを保証する難しさが出て来る。このシステムの目 的コードの構築は図５−８のフローチャートに広（示されている方法を実行する コンパイラによって達成される。

ここで図５のフローチャートについて説明すると、コンパイラはソースコードリ スト（ボックス５０）及び特定のシステム並びに作動パラメータを画定するデー タを入力として受ける。ボックス５２に示されているように、システムアーキテ クチュアパラメータは、コンパイラへの一つの入力を形成しており、各ノードに 対して、使用可能システム（ａｖａｉｌａｂｌｅ　ｓｙｓｔｅｍ）及びこれに関 する特定の規定を画定する。例えば、メモリはその組織（例えば、平面の数）、 それらが物理的かあるいは仮想的かということ、キャッシュの容量、キャッシュ の組織及びその作動アルゴリズム、クロック当たりの読みだしの数、クロック当 たりの書き込みの数、並びにクロック当たりのアクセスの数について画定される 。

更に、各プロセッサは、そのために使用可能な一重構造、二重構造及び三重構造 の数（例えば、それぞれ４．８、及び４）、レジスタファイル及び各々における レジスタの数、アクセスの種類、及びプロセッサに何らかの特殊な機能が配設さ れているか否かを画定したであろう。明かに、付加的なアーキテクチュアパラメ ータが配設されているが、上記は、当業者にシステム資産及びそれらの作動特徴 を画定する情報の種類の即座の理解を提供する。

他の規定の中で、中断が生じ且つ終了が命令される前に、最適化サブル　−チン が通過されるべき回数を示す最適化パラメータがコンパイラへの入力（ボックス ５４）として配設されている。

このソースコートリストは、パーサ−と字句分析プログラムから構成されている 初期メモリマツプサブルーチン（ボックス５６）にかけられる。これらのサブル ーチンは、予備最適化記号−テーブル発生器と共に、入力メモリアレイのメモリ 記憶位置を割り当て、これらの記憶位置を規定するテーブルを構築する。より詳 細には、アレイ寸法を画定するソースコードステートメントが受けられると、大 きなアレイが、後続のメモリ参照競合を避けることを初期に試みて、様々な物理 的記憶位置（領域）に割り当てられる（分解される）。

これ以降、ソースコードリストはシストリックＤｏループステートメント（Ｓｙ ｓｔｏｌｉｃ　ｄｏ−１ｏｏｐ　ｓｔａｔｅｍｅｎｔｓ）だけでなく、スカラー ステートメントのリストの両方を含むと仮定される。これ以降、”ブロック“の 用語は一重のスカラーステートメントあるいはＤｏ小ループ例えば、シストリッ クコードブロック）を含むステートメントのどちらかに言及し得る。公知のよう に、各Ｄｏ小ループ、−組のオペランドについて実行される反復性オペレーショ ンを画定するベクトルプロセスである。このコンパイラは入来ソースコード入カ 流からＤｏ小ループ抽出しくボックス５８）、その中の各ソースコードステート メントをワイド中間コード（ＷＩＣ）ステートメントに変換する（ボックス６０ ）。このワイド中間コードは、フォーマットが順次コードについての通常の場合 よりも高いレベルの規定を表しているという意味でご従来の”ベクトル化コンパ イラによって発生されたコードとは異なり、即座の局部依存性はＷＩＣ内で実施 されている。

各ＷＩＣステートメントはソースコードステートメントによって要求された機能 を実行するために一組の機械処置を画定する。各ＷＩＣステートメントは目的コ ードの形にあり、ソースコードステートメントによって要求された処１を実質的 に画定する一連の記号、トークン（ｔｏｋｅｎＬ等を含んでいる。これは、特定 のリンキング情報に欠けているため、この段階ではコンピュータによって実施可 能ではない。　基本的に、ＷＩＣのフォーマットは元のソースコードにおいて見 いだされた局部並列及びシストリック構造及び依存性を固有的に維持する。

オペランドフェッチ、複雑な中間オペレーション、及び結果記憶の間の本来の相 関関係はＷＩＣステートメント内に保存される。ＷＩＣコードの唯一っのライン はソースコードにおける対応ラインに直接関係する。後続の解析にかがる可能な 並列あるいはシストリック実施を抽出する負担が低減する。

ＷＩＣは、通常単純な負荷、移動、作動、記憶シーケンスによって特徴つけられ る偏在性順次内部コートフォーマット（ｕｂｉｑｕｉｔｏｕｓ　５ｅｑｕｅｎｔ ｉａｌ　１ｎｔｅｒｎａｌ　ｃｏｄｅ−ｆｏｒｍａｔｓ）とは対照的である。

この後者のフォーマットは元のソースコードにおいて明確であった明白な並列コ ートエレメントの多（を再構成しなければならない並列コート解析器に更なる負 担をかける。

このＷＩＣコートはソースプログラムによって指示された処置の全てを具象する 。加うるに、ＷＩＣコートは記号−テーブル属性及び局部データ依存性を維持す る。　ＷＩＣステートメントの基本フォーマットの一例は、ｔｊＪ４　＝　（Ｏ ｐｅｒｌθ、　０ｐｅｒ２）θ２（Ｏｐｅｒ３θ３０ｐｅｒ４）ここで、θは任 意高レベルオペレーション、例えば、＝、Ｘ、十等を意味し、０ｐｅｒはメモリ 、レジスタ、あるいは先行の計算の結果からのオペランドを意味する。この例に おいて、ＷＩＣは、局部依存性（挿入的な順序付けに基ずく）を示し、ここで８ ．及びθ３はθ２による後続の処理と並列に実施し得る。シストリック実施は、 その出力が後続のプロセッサ入力に直接供給される処理エレメントのアレイにエ ンタするデータ流を考慮することにより作動的に画定される。かくして、データ は、中間記憶の必要性なしにアセンブリラインの様式で処理される。　中間コー トのフォーマットの一例を示すために、シストリックオペレーションがテストプ ログラムから抽出され且つ以下のようにフォートランで表現されると考慮せよ。

ｚ　＝　ｃｏｎｓｔｌ零ｂ（Ｄ（ｃｏｎｓｔ２零ａ（ｉ）＋ｃｏｎｓｔ３本ｃ（ ｉｊ））上記のフォートランステートメントに対応するＷＩＣステートメントは 以下の通りである。

ｐｏｏ：＝＄８＄１ＩＲ３本＄１＃５ＭＡｌ＋＄！Ｊ＃１１２Ｓ本＄４＃８ＭＡ １　％　ｃａｌｃｕｌａｔｅｃ２零ａ（ｉ）＋ｃ３＊ｃ（ｉＤ ＝−＄１３：１２ＭＡｌ−＄７＄１１Ｒ３本＄２＃６１ＡＩ−ｐｏｏ　％　ｃａ ｌｃｕｌａｔｅ　ｚ・〉％ｅｎｄ　ｄ。

上記でＷＩＣを形成する依存性解析器（ｄｅｐｅｎｄｅｎｃｙ　ａｎａｌｙｚｅ ｒ）は、ソースコートのフォーマットに密接に従う。ＷＩＣは、特にコンパイラ のこの実施に対して記号−テーブルニーモニック（ｍｎｅｍｏｎ　ｉ　ｃｓ）　 を用いる。多重独立メモリ平面のポテンシャルがトークンの構造に反映される。

データー構造記号テーブルトークンのフォーマットが表１に記載されている。

データー構造記号テーブルトークン　＄！ｘｘ＃ｍｐ　５ｔｏｒ　ｏｃｃ、　こ こで 尺号　脱灰 ＄　データエレメント ！　分散／多重記憶表示子 ｘｘ　可変参照数 ＃ｍｐ　メモリ平面数 ｓ　ｔｏｒ　以下によって与えられる変数の変位：ＭＡ　メモリ基アレイ ＭＳ、メモリ基スカラー ＲＡ：レジスタ基スカラー Ｒ３レジスタ基スカラー ｏｃｃ　可変成員数 表１゜データ構造記号トークンのフォーマット上記の例に示されているように、 ＷＩＣは、入れ子式内部依存性ノード（ループ内）から構成されている。（ルー プへラダコードは簡潔性のために削除されている）。ここで、無端子内部ノード ｐ００はシストリック句を示している。句中断は、ソースに示されている挿入的 順序付けによって駆動される。＝＝に境界を接するトークンは局部依存性ツリー の根である。かくして、この例によって示されているように、ＷＩＣはそれ自身 を比較的率直な後続の解析及び並列実施に適するようにせしめる中間及び最終結 果の本来の順序付けを与えらる。

引き継がれた属性はかなり細かく解析することが出来、限度内で、従来の順次中 間コードが、上で論じられたように、生じる。しかしながら、これは並列コード 解析器から増大した仕事を要求し、ＷＩＣ解析器によって予想されるパフォーマ ンスよりも低いパフォーマンスをもたらし得る。ＷＩＣ順序付けは最適化器によ って実行される付加的シストリック及び並列コード発生を有意に抑制するもので はないことが、銘記されるべきである。

ここで図５に戻ると、各ＤＯ小ループＩＣステートメントが構成された後（ボッ クス６０）、このステートメント内の内部依存性が見いだされ且つ記録される。

ボックス６４．６６、及び６８から分かるように、スカラーソースコードステー トメントのブロックに関して同様の処ｌが行われる。しかしながら、この例にお いて、ブロック寸法は、連続するＤＯシル−間のコードのラインの数、あるいは コードのラインの予め画定された最大数のどちらかの最小となる。

一旦、Ｄｏ小ループびスカラーステートメントのブロックがＷＩＣステートメン トに変換されると、これらのステートメントはリストに併合される（ボックス７ ０）。すると、各ＷＩＣステートメントが解析されて、それを機能せしめるには どのアーキテクチュア資産が必要であるか決定される。次にこれらの資産は割り 当てられ（図６のボックス７２）　、ＷＩＣステートメントがアーキテクチュア ユニットにマツピングされてこのステートメントを処理することの出来る必要な シストリック又はスカラーアレイを生成する（ボックス７４）。

この段階において、コンパイラは割り当てられたアーキテクチュア資産と組合わ さって、ＷＩＣステートメントを実行するために計算システムの構成を可能にす るマツプを発生している。

しかしながら、ＷＩＣステートメントをシミュレートするのに不十分な資産しか 得られない場合（決定ボックス７３参照）、これらの使用可能資産を収容するた めにＷＩＣステートメントを修正しなければならない（ボックス７３）。これは 、ステートメント切り捨て、分割あるいはＷＩＣステートメントオペレーション を後続の段階に分割して、各段階で要求される資産を減する他の特定の手順の形 を取り得る。

ＷＩＣステートメントに対して十分な資産が見いだされた場合、資産のアレイが アセンブルされ、このステートメントはその上にマツピングされる（ボックス７ ５）。

ここでシミュレーションサブルーチン（ボックス７６）がアクセスされ、アセン ブルされたアーキテクチュアユニットの”近似”シミュレーションをマツピング されたＷＩＣステートメントに従って実行する。このシミュレーション（及び後 続の最適化）の目的は、コンピュータのピーク理論速度の規定された分数におい て、あるいはこれよりも高い速度で実行する目的コードを発生することにある。

これは、各ＷＩＣステートメントが如何に効率的に実施するかについての近似的 な計量を得て、次にそのパフォーマンスを改良することを試みてＷＩＣステート メントを修正することにより達成される。この結果を得るために各ＷＩＣステー トメントを完全にシミュレートすることは不必要であることが見いだされている 。

従って実際、各ＷＩＣステートメントについて比較的粗いシミュレーションが実 行され、斯かるシミュレーションでもコンパイラはその実施効率の度合いを得る ことが可能である。

実際の（シミュレーションしない）オペレーションでは、各ＷＩＣステートメン ト及びそこから発生したコートはデータの大きなアレイに作用する。

このシミュレーションサブルーチンはこの大きなアレイから後続のシミュレーシ ョンのための入力として作用するその部分集合を選択する。これにより、シミュ レータは統計的有効性を提示するパフォーマンス基準を引き出すのに必要な多（ の量のデータを取り扱う必要の結果として動きが取れなくなることを防ぐ。シミ ュレーションに用いられるべきデータアレイは、ユーザ規定（あるいは規定がな い場合は、ディフォルト部分集合）である。

この近似シミュレータは、各ＷＩＣステートメントに対して、全ての要求された メモリ参照を”実施”する。メモリ参照は、読みだしあるいは書き込みであって も、メモリにおける各記憶に対する全ての参照を含んでいる。加つるに、ＷＩＣ ステートメントによって要求された計算処置はシミュレーションされるが、部分 的にのみである。例えば、メモリ参照の計算に関する計算処置はシミュレーショ ンされる。シミュレーションは一般的に、後続のメモリ参照に至るステートメン トあるいは次の条件テストにかけられる何らかのステートメントを実施するだけ である。

一例として、計算されなければならないが、間接計算に依存するメモリの別の部 分に記憶されているアドレスに対する参照を考慮せよ。この例において、アドレ スは値ｊによってアレイＡ内に規定され、ここでｉは間接メモリ参照について言 及している。ここで、ｉの値の計算がシミュレーションされるが、Ａの値はシミ ュレーションされない。これは、Ａが単に”結果”であり、このシミュレーショ ンがＡ（１）の計算が如何にして機械のパフォーマンスに影響するかについての み関連し、計算に対する答えの結果ではないからである。しかしながら、Ａの値 が次の条件テストを条件とする場合（例えば、Ａが１よりも大きいか小さい場合 ）、これは計算される。

このンミュレーンヨンプログラムが実行すると（図７のボックス７８参照）、こ れはメモリ参照の数、実行される原始的演算／論理オペレーションの数演算／論 理オペレーションの数、及び生じるメモリ競合の数を記録する。原始的演算／論 理オペレーションは、加算、減算、乗算、又は論理比較である。より複雑なオペ レーションは別の原始的演算／論理オペレーションの比例案ステートメントされ た値である。例えば、加算オペレーションは１に等しく、除算オペレーションは ４に等しい。

メモリバンク内での記憶されたアレイの後続の再割り当てを可能にするべくメモ リの各ブロックに対してメモリ競合の数が記録される。シミュレータによって発 生され得る他の統計量は平面当たりのフェッチ／リストアの数に対する相対的な 平面当たりのキャッシュ不明、条件的パイプラインフラッシュの数、及び条件的 ステートメント実施の関数としての再構成の数、等を含んでいる。

実際、シミュレーションは、最終的数値あるいは論理的結果に到達するためにで はな（、コンピュータのオペレーション及び各ＷＩＣステートメントにおけるそ の割り当てられた資産を計量するために実行される。か（して、シミュレーショ ンの結果は、−組の統計的に信頼出来る近似的パフォーマンス特徴である。一旦 、ＷＩＣステートメントの粗いシミュレーションが終了すると、アルゴリズムは ブロック又はＤＯ小ループ終了したか否か（即ち、シミュレーションされていな いＷＩＣステートメントが他に存在するか？）を試験する（ボックス８０）。ス テートメントが確かにシミュレーションされずに残っている場合、プログラムは 再循環してシミュレーションを達成する。ブロック又はＤｏ小ループおけるＷＩ Ｃステートメントがシミュレーションされている場合、プログラムは進行して、 他の指示の中に、ブロック又はＤＯ小ループための演算計数、そのブロック又は ＤＯ小ループおける各ＷＩＣステートメントに対する演算計数、及び各々に対す るメモリバンク及び競合のリストを含むメモリ参照競合の計数を出力する（ボッ クス８２）。図８の決定ボックス８４に示されているように、これらの出力は次 に（最適化パラメータからアクセスされた、図５のボックス５４参照）予め画定 された作動基準と比較される。スカラーステートメントのブロックまたはＤｏ小 ループこの作動基準より高い効率レヘルで実施することが分かった場合、このＷ ＩＣステートメントは目的コートに変換される（ボックス８６）。このプログラ ムは、処理されるＷＩＣステートメントがもはや存在しない場合、終了しく決定 ボックス８８）、そうでない場合、この方法は再循環して次のＷＩＣステートメ ントを取り扱う。一方、これらの出力が呼び出されたパラメータより低いパフォ ーマンス効率を示す場合（決定ボックス８４）、このパフォーマンス効率が最後 の”試行（ｔｒｙ）”に対して改善されているか否かが決定される（決定ボック ス９０）。何らパフォーマンス改善がもたらされていない場合、最後の最適化処 置が逆転され（ボックス９２）、未試行の最適化処置が試みられる。パフォーマ ンス効率改善が見られた場合（ボックス９０）、この方法は別の未試行最適化処 置に進む（ボックス９４）。

コンパイラは、場合により、スカラーＷＩＣコードの各ブロック又はＤｏ小ルー プついて個別最適化処置を実行することにより最適化器サブルーチンに進む。

コンパイラはコート変換及びコードヒユーリスティックの両方を直列様式で実行 する。例えば、全体的な共通副次式の削除、ループヘッダオペレーションの後続 のスカラー処理、等の公知のコート変換が実行される。コンパイラは又、未使用 処理情報の再分布を可能にするためのループ融合、メモリ競合を最小限にするた めのループ交換、競合を低減するためのメモリ中のデータの動的再分布、独立的 且つ並列的サブループ実施を可能にするためのループ分割等を含み得るが、これ らに限定されない、コートヒユーリスティック（ｃｏｄｅ　ｈｅｕｒｉｓｔｉｃ Ｓ）を実行する。

各個別最適化処置が達成された後（ボックス９４）、スカラーステートメントの Ｄｏ小ループはブロックにおける修正されたＷＩＣステートメントは近似シミュ レーションサブルーチンを用いて再びシミュレーションされる。かくして、Ｗ■ Ｃステートメントの各Ｄｏ小ループはブロックは、予め画定された作動基準との 比較のために新しい組の出力を得るべく、上記の如く、その実施をシミュレーシ ョンせしめた。次に、最適化器ルーチン（ｏｐｔｉｍｉｚｅｒ　ｒｏｕｔｉｎｅ ）の数が限度に等しいか否かが決定され（決定ボックス９６）、等しい場合、最 適化器ルーチンは停止して、終了し、そしてＷＩＣステートメントは目的コード に変換される。実行の数が等しくなかった場合、ルーチンは戻って継続する。

上記から分かるように、このコンパイラによって、スカラーステートメントの個 別ＤＯ小ループびブロックは粗いシミュレーションを用いて個別に試験され得る 。これらの最適化されたコードステートメントは、コードのパフォーマンスを更 に改良する試みで、付加的な最適化サブルーチンにかけられる。各最適化サブル ーチンの直後に、各ブロック及び／又はＤＯ小ループ記録された内部依存性が変 更されたＷＩＣステートメントに従って再試験され且つ再調節されなければなら ないことが当業者には明白であろう。この手順はコード及びＤｏ小ループ個別ブ ロックを最適化するだけではな（、コード構造全体に全体的な効果をもたらし得 る。例えば、幾つかのＤＯ小ループ一つのループに”融合”された場合、これら のＤＯループ内及び中での依存性が考慮され必要に応じて変更される。また、デ ータの再分布又は再マツピングは同様の全体的な効果をもたらす。かくして、採 用されたコード変換及びヒユーリスティックに基ずいて、コンパイラによって生 成されている目的コードが生成出来る程、最適となることを保証するべく、各段 階において、試験された実時間の最適化が行われる。

上記の説明は本発明を例示するだけであることを了解すべきである。本発明から 逸脱することな（、種々の変更及び修正が当業者によって考案され得る。従って 、本発明は、付記された請求の範囲に属する全ての斯かる変更、修正及び変異を 含むと意図される。

ＦＩＧ、　２ ＦＩＧ、　３ ＦＩＧ、　４ 最適化コンパイラ ＦＩＧ、７ 手続補正書

Claims (12)

【特許請求の範囲】
1. １．ソースコードリストを目的コードリストにコンパイルする方法であって、そ のオペレーションを制御するコンパイラソフトウエアを有するコンピュータによ って実行される方法において、 ａ．上記ソースコードリストからソースコードステートメントを抽出する段階、 ｂ．上記ブロックにおける各ソースコードステートメントを中間コードフォーマ ットにマッピングする段階であって、上記フォーマットが上記ソースコードステ ートメントによって呼び出されたファンクションを実行するために依存した一連 の機械処置を画定している段階、 ｃ．上記ブロックにおける上記中間コードフォーマットの初期近似シミュレーシ ョンを実行し、上記シミュレーションからパフォーマンス結果を引き出す段階、 ｄ．上記パフォーマンス結果に依存して、上記パフォーマンス結果を改良するこ とを試みて、上記中間コードフォーマットを修正する段階、ｅ．斯かる処置を終 端する決定点に到達するまで、段階ｃ及びｄを反復する段階を含むことを特徴と する方法。
2. ２．上記中間コードフォーマットがワイド中間コード（ＷＩＣ）ステートメント を含み、段階（ｃ）が各ＷＩＣステートメント及びＷＩＣステートメントの各ブ ロックの近似シミュレーションを実行することを特徴とする請求項１の方法。
3. ３．段階ｄにおける上記修正が一群のコード変換及びヒューリスティックからの ルーチンに従って上記ＷＩＣステートメントについて実行されることを特徴とす る請求項２の方法。
4. ４．段階ｂが、 ｂ１．上記ブロック中の各上記ＷＩＣステートメント内の依存性を決定し、上記 初期近似シミュレーションを上記依存性に従って作動せしめる更なる段階を含む ことを特徴とする請求項３の方法。
5. ５．段階ｃが更に、 ｃ１．上記コンピュータにおける使用可能エレメントを画定するアーキテクチュ アパラメータのリストを配設する段階、ｃ２．ＷＩＣステートメントを実施する ために一組の上記使用可能エレメントを割り当てる段階、及び ｃ３．上記ＷＩＣステートメントを上記の割り当てられた処理エレメントを通じ て処理するために近似シミュレーションルーチンを作動する段階を含むことを特 徴とする請求項４の方法。
6. ６．上記近似シミュレーションルーチンが各ＷＩＣステートメントの粗いシミュ レーションを行い、上記シミュレーションが、演算／論理原始的オペレーション のクロックサイクル当たり、ＷＩＣステートメント当たりの数、ＷＩＣステート メント当たりのメモリ参照競合の数の測定を可能にし、且つ更に、各ブロックに 対する上記オペレーション及び競合の数の蓄積を可能するのに少なくとも十分で あることを特徴とする請求項５の方法。
7. ７．段階ｄが更に、 ｄ１．上記パフォーマンス結果を上記コンピュータのための作動基準に対して比 較し、上記比較の結果が上記結果が上記作動基準と少なくとも等しいことを示さ ない場合、段階ｅを実行する段階を含むことを特徴とする請求項６の方法。
8. ８．段階ｄが更に、 ｄ２．上記ＷＩＣステートメントを修正した後、上記決定された依存性を上記修 正されたＷＩＣステートメントに従って更新する段階を含むことを特徴とする請 求項７の方法。
9. ９．段階ｄが更に、 ｄ３．メモリ参照競合を低減することを試みて、上記ＷＩＣステートメントのブ ロックのためのメモリアドレス割り当てを修正する段階を含むことを特徴とする 請求項８の方法。
10. １０．段階ｄが更に、 ｄ４．使用可能エレメントによる上記原始的オペレーションのストリングの並列 的実施を可能にするベく上記のオペレーションのストリングを分割する段階 を含むことを特徴とする請求項９の方法。
11. １１．段階ｄが更に、 ｄ５．上記ＷＩＣステートメントの修正に続いて、上記の修正されたＷＩＣステ ートメントを実施するのに十分な非割り当て処理エレメントが使用可能か否かを 評価し、使用可能でない場合、上記ＷＩＣステートメントを修正して使用可能処 理エレメントを利用できるようにする段階を含むことを特徴とする請求項１０の 方法。
12. １２．段階（ｅ）における上記決定点がユーザによってエンタされたパラメータ であることを特徴とする請求項１１の方法。