(57)【要約】【課題】冗長な命令列を含んでいるプログラムを効率的な命令列を含むプログラムに置き換えて最適化する。【解決手段】コンパイル処理により生成されたアセンブリプログラムの命令列を他の命令列に置き換えてプログラムの最適化を行なう方法が開示される。まずアセンブリプログラムの命令列を効率的な命令列に置き換えるための変換規則を記述したパターンファイルを記憶手段に格納する。コンパイル処理の実行中に、このパターンファイルを参照して、生成されたアセンブリプログラム中の命令列にパターンファイル中の規則に適合するものがあるかを調べ、その結果、パターンファイル中の規則に適合する命令列が存在する場合、変化規則で変換して生成されるアセンブリプログラムの意味が変わらないことを検証する。この検証の結果、意味が変わらない場合に、その変換規則に従って命令列の変換を行ない、アセンブリプログラムの実行コードを生成する。【選択図】図１
2006079494.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムから実行コードを生成するコンパイラにおいて、
該ソースプログラムからコンパイラ内部で処理可能な中間コードを作成して、構文解析を行なう手段と、
生成された該中間コードの最適化処理を行う第１の最適化処理手段と、
該第１の最適化手段によって生成されたアセンブリプログラムの命令列に対して、ユーザによって記述された、命令列の変換規則を規定したパターンファイルに基づいて該アセンブリプログラムに含まれる命令列を他の命令列に変換することにより最適化処理を行なう第２の最適化手段と、
該第２の最適化手段によって、該アセンブリプログラムに元々含まれていた命令列を他の命令列に変換された、アセンブリプログラムの実行コードを生成する実行コード生成手段と、
を有することを特徴とするコンパイラ。
【請求項２】
前記第２の最適化手段は、元々の命令列を含んだアセンブリプログラムを実行した後の結果と、該他の命令列に置き換えたアセンブリプログラムを実行した後の結果とが変わらない場合に、該他の命令列へ変換することを特徴とする請求項１のコンパイラ。
【請求項３】
コンパイル処理によって生成されたアセンブリプログラムの命令列を他の命令列に置き換えてアセンブリプログラムを最適化する方法において、
該アセンブリプログラムの命令列を効率的な命令列に置き換えるための変換規則を記述したパターンファイルを記憶手段に格納するステップと、
コンパイル処理の実行中に、該パターンファイルを参照して、生成されたアセンブリプログラム中の命令列にパターンファイル中の規則に適合するものがあるかを調べるステップと、
調べた結果、パターンファイル中の規則に適合する命令列が存在する場合、該変換規則で変換して生成されるアセンブリプログラムの意味が変わらないことを検証するステップと、
該検証の結果、意味が変わらない場合に、該変換規則に従って命令列の変換を行なうステップと、
を有するプログラムの最適化方法。
【請求項４】
ユーザに提示するために、ユーザにより記述された変換規則の適用回数およびその結果削減された命令数を表示装置に表示するステップを有することを特徴とする請求項３の最適化方法。
【請求項５】
ユーザに提示するために、コンパイル処理で生成されるアセンブリプログラム中に繰り返し現れる命令列を、冗長命令列の候補として表示装置に表示するステップを有することを特徴とする請求項３の最適化方法。
【請求項６】
前記命令列の変換処理において、予め記憶手段に用意された、論理式間の同値関係を定義した公理表を参照することにより、定義された命令列を他の命令列に変換することを特徴とする請求項３乃至５のいずれかの最適化方法。
【請求項７】
コンパイラによってソースプログラムを変換処理してアセンブリプログラムの命令コードを生成する命令コードの生成方法において、
該アセンブリプログラムの命令列間の変換規則を記述したパターンファイルを記憶手段に格納するステップと、
該パターンファイルを参照して、生成されたアセンブリプログラム中の命令列にパターンファイル中の規則に適合するものがあるかを調べるステップと、
調べた結果、パターンファイル中の規則に適合する命令列が存在する場合、該変換規則で変換して生成されるアセンブリプログラムの意味が変わらないことを検証するステップと、
該検証の結果、意味が変わらない場合に、該変換規則に従って命令列の変換を行ない、該アセンブリプログラムの修正を行なうステップと、
を有するプログラムコードの生成方法。
【請求項８】
請求項１又は２のコンパイラ、又は請求項３乃至７のいずれかの方法を実行するためのコンピュータ処理可能なプログラムを格納した記録媒体。
【請求項９】
コンパイラによってソースプログラムを変換処理してアセンブリプログラムの命令コードを生成し、作成された該アセンブリプログラムをメモリチップに含ませてメモリチップを生産する生産方法において、
該アセンブリプログラムの命令列間の変換規則を記述したパターンファイルを記憶手段に格納するステップと、
該パターンファイルを参照して、生成されたアセンブリプログラム中の命令列にパターンファイル中の規則に適合するものがあるかを調べるステップと、
調べた結果、パターンファイル中の規則に適合する命令列が存在する場合、該変化規則で変換して生成されるアセンブリプログラムの意味が変わらないことを検証するステップと、
該検証の結果、意味が変わらない場合に、該変換規則に従って命令列の変換を行ない、該アセンブリプログラムの修正を行なうステップと、
前記修正されたアセンブリプログラムを記憶装置に一時格納するステップと、
該記憶装置に格納された該修正後のアセンブリプログラムを、書き込み装置を使用してメモリチップに記録するステップと、
を有することを特徴とするプログラム格納用メモリチップの生産方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機に利用されるコンパイラに係り、特に、ユーザが自らのプログラムの特性に応じて命令列の最適化を行なうことができるコンパイラ及び最適化した命令コードの生成方法に関する。
【背景技術】
【０００２】
組み込みプログラムの分野では、制御プログラムの実行コードを格納するのに必要なＲＯＭ（リードオンリーメモリ）のサイズが生産コストに影響するため、プログラムの実行コードのサイズを出来る限り小さくするような最適化を行うコンパイラが望まれている。しかしながら、コンパイル対象となるプログラムはその制御対象の特性に応じて、またプログラム開発組織のコーディング規則等に応じて多種多様の形態をとるため、コンパイラの持つ一般的な最適化機能では対応しきれずに冗長な命令列が生成される場合がある。
【０００３】
近年では、形式的に記述された仕様からプログラムを自動生成するツールが普及し始めている。このようなツールによって生成されるプログラムは、人間が書くプログラムと異なる特性を持つことが多く、コンパイラによる最適化が十分でない場合が増えつつある。
【０００４】
従来、この最適化のための方策として、例えばソースプログラムをコンパイラが最適化できるような形に修正したり、コンパイラの生成したアセンブリプログラムを人間の手で修正すること、更にはコンパイラ提供者に改善要求を出し、最適化機能を追加したコンパイラがリリースされるのを待つ等の方策が採られて来ている。
【０００５】
また、例えば非特許文献１に開示されているように、コンパイラツールキットを用いてユーザが自分自身で必要とする最適化を持つコンパイラを実装することが知られている。
【０００６】
【非特許文献１】Ｍ．Ａｌｔ， Ｕ．Ａｓｓｍａｎｎ， Ｈ．Ｖ．Ｓｏｍｅｒｅｎ， Ｃｏｓｙ Ｃｏｍｐｉｌｅｒ Ｐｈａｓｅ Ｅｍｂｅｄｄｉｎｇ ｗｉｔｈ ｔｈｅ ＣｏＳｙ Ｃｏｍｐｉｌｅｒ Ｍｏｄｅｌ， ｉｎ Ｐｒｏｃ． ５ｔｈ ＩＣＣＣ， ｐｐ．２７８−２９３， １９９４．
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記文献１に記載の従来の技術によれば、ユーザ自身がコンパイラの最適化機能を実装するために、専門的な知識と膨大な工数が必要となり、また誤った最適化機能を実装する恐れがある。
【０００８】
本発明の目的は、冗長な命令列を含んでいるプログラムを効率的な命令列を含むプログラムに置き換えて最適化することができるコンパイラ、及びプログラム命令列の最適化方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明に係るコンパイラは、ソースプログラムから実行コードを生成するコンパイラにおいて、ソースプログラムから構文解析を行ってコンパイラ内部で処理可能な中間コードを作成する手段と、生成された中間コードの最適化処理を行う第１の最適化処理手段と、第１の最適化手段によって生成されたアセンブリプログラムの命令列に対して、ユーザによって記述された、命令列の変換規則を規定したパターンファイルに基づいてアセンブリプログラムに含まれる命令列を他の命令列に変換することにより最適化処理を行なう第２の最適化手段と、第２の最適化手段によって、アセンブリプログラムに元々含まれていた命令列が他の命令列に変換された、アセンブリプログラムの実行コードを生成する実行コード生成手段と、を有するコンパイラである。
好ましい例では、前記第２の最適化手段は、元々の命令列を含んだアセンブリプログラムを実行した後の結果と、他の命令列に置き換えたアセンブリプログラムを実行した後の結果とが変わらない場合に、他の命令列へ変換する。
【００１０】
本発明に係るプログラムの最適化方法は、コンパイル処理によって生成されたアセンブリプログラムの命令列を他の命令列に置き換えてアセンブリプログラムを最適化する方法において、アセンブリプログラムの命令列を効率的な命令列に置き換えるための変換規則を記述したパターンファイルを記憶手段に格納するステップと、コンパイル処理の実行中に、パターンファイルを参照して、生成されたアセンブリプログラム中の命令列にパターンファイル中の規則に適合するものがあるかを調べるステップと、調べた結果、パターンファイル中の規則に適合する命令列が存在する場合、変換規則で変換して生成されるアセンブリプログラムの意味が変わらないことを検証するステップと、検証の結果、意味が変わらない場合に、変換規則に従って命令列の変換を行なうステップと、を有するプログラムの最適化方法である。
好ましい例では、ユーザに提示するために、ユーザにより記述された変換規則の適用回数およびその結果削減された命令数を表示装置に表示するステップを有する。
また、好ましくは、ユーザに提示するために、コンパイル処理で生成されるアセンブリプログラム中に繰り返し現れる命令列を、冗長命令列の候補として表示装置に表示するステップを有する。
本発明は、また上記最適化方法の各ステップによりアセンブリプログラムの命令コードを生成する命令コードの生成方法としても把握される。
本発明は、また上記コンパイラ、又は上記の最適化方法又は命令コードの生成方法を実行するためのコンピュータ処理可能なプログラムを格納した記録媒体としても把握される。
更に、本発明は、上記のように生成された命令コードを含むアセンブリプログラムを、書き込み装置を使用してメモリチップに記録するステップを有するプログラム格納用メモリチップの生産方法としても把握される。
【発明の効果】
【００１１】
本発明によれば、冗長な命令列を含んでいるプログラムを効率的な命令列を含むプログラムに置き換えて最適化することができる。これにより、プログラムの実行コードサイズを縮小させることができ、プログラムの実行速度を向上させ得る。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して、本発明の一実施例について説明する。
この実施例では、レジスタを操作する命令列のみを変換対象とする場合について説明するものである。
図１は、一実施例によるコンパイラが稼動する計算機システムの構成図である。図１において、計算機システムは、ＣＰＵ１０１、主記憶装置１０４、外部記憶装置１０５、ディスプレイ装置１０２、キーボード１０３がバスに接続されて構成される。外部記憶装置１０５には、ソースプログラム１０６及び実行コード１０７が格納される。主記憶装置１０４には、コンパイラプログラム（以下単にコンパイラと言う）１０８と、コンパイル処理過程で必要となる中間コード１０９、各アセンブリ命令の意味を記述した命令意味表１１０、意味空間上で同値性判定に使用する公理表１１１、各アセンブリ命令実行後に生存となるレジスタを表す生存表１１２、及びパターンファイル１１３が格納される。
【００１３】
通常、コンパイラ１０８は外部記憶装置１０５に記憶されており、その実行時に、外部記憶装置１０５から主記憶装置１０４へロードされる。またその時、中間コード１０９〜パターンファイル１１３の格納領域が主記憶装置１０４内に確保され、関係する情報が格納される。
【００１４】
キーボード１０３はユーザからのコマンドをコンパイラ１０８に与えるための入力手段として用いられる。ディスプレイ装置１０２は、コンパイルの終了及びエラーをユーザに知らせるための情報を表示する。
【００１５】
コンパイル処理は、ＣＰＵ１０１でコンパイラ１０８を実行することにより行われる。即ち、コンパイラ１０８は、外部記憶装置１０５から読み出されたソースプログラム１０６を、機械語である実行コードに変換処理して、これを外部記憶装置１０５の実行コード１０７の領域に格納する。生成された実行コード１０７は、その後、例えばロムライタ（ＲＯＭ  Writer）のような書き込み装置によってマイクロプロセッサ等のＲＯＭに書き込まれる。
【００１６】
中間コード１０９は、コンパイル処理の最中に生成される中途段階のコードであり、コンパイラがこれらの中間コードを結合処理することにより、中間コードが順次作成され、主記憶装置１０４の中間コード１０９の領域に格納される。
【００１７】
コンパイラ１０８は、例えば図６に示す命令意味表１１０、および図７に示す公理表１１１を保持している。
命令意味表１１０は、各アセンブリ命令に対応する意味関数を定義したものである。
意味関数はλσ．σ［ｖ／ｒ］という形式で記述されているが、これは状態σを引数にとり、状態σにおいてレジスタｒが持つ値をｖに更新した新しい状態σ［ｖ／ｒ］を返す関数である。たとえばλσ．σ［ａｎｄ（ｉ，σ（ｒ））／ｒ］は状態σにおけるレジスタｒの値をａｎｄ（ｉ，σ（ｒ））に更新した状態を返す関数を表す。なおレジスタＲｃは条件分岐のために使用するフラグを保持する特殊レジスタである。
【００１８】
公理表１１１は論理式間の同値関係を定義する。
図７に示すように、公理は「式≡式」という形式をとり、≡の左辺の式を右辺の式に置き換えても式の値が変わらないことを意味している。式中の大文字変数Ａ、Ｂはパターン変数であり、任意の式にマッチする。たとえばｉｓｚｅｒｏ（ｅｘｔｓ（Ｒ１，１））はＡとしてＲ１、Ｂとして１を割り当てることで公理ｅｘｔｓ−ｅｌｉｍの左辺の式にマッチするため、これを右辺の式ｉｓｚｅｒｏ（Ｒ１）に置き換えても式の値は変化しない。
従って、公理表１１１に登録されている論理式の関係を参照することによって、同値関係にある左右の式を変換できることが保証される。
【００１９】
生存表１１２は、命令毎にその点で生存するレジスタの集合を解析した結果を示す。図８に示すように、ある点で生存するレジスタとは、その点における値が以降の点で参照され得るレジスタのことである。尚、生存表の機能及び作成等については、従来から良く知られているので、これ以上の説明は省略する。
【００２０】
次に、図９にはＣプログラムの例を示し、図１０にはパターンファイル１１３の例を示す。
ユーザは、図９のようなＣプログラムに対してコンパイラが生成したアセンブリプログラムを調べて、冗長と思われる命令列が存在しているかをチェックする。そして冗長な命令列をより効率的な命令列に置き換えるために変換規則を逐次作成して、それをパターンファイル１１３に追加して行く。
【００２１】
図１０に示すように、パターンファイル１１３の記述は、５０３行が変換規則名、５０４、５０５、５０６行が変換対象とする命令列（元の命令列）、５１０行が変換後の命令列を表している。命令列中のｉ、Ｒｎ、Ｒｍはパターン変数で、ｉは任意の整数リテラル、Ｒｎ、Ｒｍは任意のレジスタ名にマッチする。各変換規則は変換前の命令列と変換後の命令列の組として表現されている。また定数値やレジスタ名についてはパターン変数を用いた総称的な記述が可能である。
【００２２】
図１０に示す例では、変換規則１（rule 1）のみが示されているが、ユーザは逐次変換規則を記述して、それをパターンファイル１１３に格納することができるので、実際には図１０のような規則が複数個（rule 1〜rulei）に纏まってパターンファイル１１３に格納される、考えてよい。
【００２３】
さて、次に図２のフローチャートを参照して、コンパイル処理の動作について説明する。
コンパイラの処理において、まず構文解析が行なわれる（Ｓ２０１）。構文解析はソースプログラム１０６を読み出し、コンパイラ内部で処理可能な中間コード１０９を作成する。
次に、各種のコード最適化および解析が行なわれる（Ｓ２０２）。このステップ２０１および２０２の動作は、コンパイル処理時のコード最適化処理として従来から通常行なわれている動作であるので、ここでは余り詳しく説明しない。
【００２４】
作成された中間コード１０９の例が図５に示される。コード最適化の終了時の中間コードは、基本ブロックをノードとする制御フローグラフであり、各基本ブロックはアセンブリ命令列によって構成されている。また中間コード中の全てのアセンブリ命令に対して、その命令実行後に値が使用されるレジスタの集合が生存表１１２に記録されている。
【００２５】
次に、ユーザにより記述されたパターンファイル１１３に基づいて最適化の処理が行なわれる（Ｓ２０３）。
この最適化処理については、後で図３を用いて詳しく説明するが、コンパイラは、コンパイル過程の最後にパターンファイルを参照し、生成したアセンブリプログラム中の命令列にパターンファイル中の規則に適合するものがあるかを調べる。そのような命令列が存在した場合、それを変換してもプログラムの意味が変わらないことを検証し、検証できた場合にのみ変換を行う。ここでプログラムの意味が変わらないとは、プログラムの実行状態を生存レジスタ（現在の値が後に使用されるレジスタ）およびメモリの持つ値として定義したとき、任意の実行状態において、変換前の命令列を実行した後の状態と変換後の命令列を実行した後の状態が等しいことである。尚、変換はプログラムの制御フローを変化させないものに限定し、プログラムカウンタは実行状態に含めないものとする。
【００２６】
検証は、一般的な述語論理にコンパイラのターゲットアーキテクチャの持つ各種操作を表す述語定数、およびその基本的性質を表す公理を追加した意味空間の上で行う。各アセンブリ命令の意味をプログラムの実行状態から実行状態への関数として定義し、命令列の意味を各命令の意味関数の合成関数として与えることで、状態が等しいかどうかの判定問題を述語論理における論理式の同値判定問題に帰着させることができる。この検証それ自体は従来から用いられている手法により実現可能である。
【００２７】
尚、好ましい例において、ユーザがアセンブリプログラム中の冗長命令列を見つける手法としては、繰り返し現れる命令列をコンパイラが冗長命令列の候補としてユーザに提示することで、この作業を支援することができる。これは頻出パターンマイニング問題として、通常知られている手法を用いて実現可能である。
【００２８】
ステップＳ２０３の処理が終わると、その後、アセンブリプログラム中の頻出命令列が抽出されて、ディスプレイ装置１０２に表示される（Ｓ２０４）。ユーザは、提示された頻出命令列を見て、その命令列が冗長であるので効率化が必要であると判断すれば、上述と同様にその命令列について変換規則を作成してパターンファイル１１３に格納する。そして上記の動作を繰り返す。
尚、頻出命令列が無かったり、又は命令列の変換処理がこれ以上必要無いような場合には、このステップＳ２０４は不要である。
【００２９】
このように、ステップＳ２０３におけるパターンファイル１１３に基づく命令列の最適化処理が終わると、最後に効率化された命令列を含むアセンブリプログラムの実行コードが生成される。（Ｓ２０５）。
【００３０】
図３は、図２における最適化処理（Ｓ２０３）を更に詳しく示した処理フローである。ここで、最適化処理はユーザにより記述されたパターンファイル１１２に基づいて行なわれる。
コンパイル処理に際して、主記憶装置１０４からパターンファイル１１３を読み出す（Ｓ３０１）。パターンファイル１１３は、例えば図１０に示すような変換規則の記述単位の集まりであり、この集まりが順次読み出される。コンパイラは、ユーザにより記述されたパターンファイル１１３から全ての変換規則を読み込む。
ここで、変換規則は複数組から成り、各変換規則は変換前の命令列と変換後の命令列の組として表現されているとする。
【００３１】
次に、複数在る変換規則を１つずつ処理する（Ｓ３０２）。全ての変換規則が処理済みであれば終了する。まだ未処理の変換規則があれば、変換規則を更に１つ取り出す（ここではｒｕｌｅとする）（Ｓ３０３）。次に、基本ブロックを１つずつ処理する（Ｓ３０４）。ｒｕｌｅに対して全ての基本ブロックが処理済みであればステップＳ３０２へ戻り、次の変換規則の処理に移る。そうでなければ、未処理の基本ブロックを１つ取り出す（ｂｂとする）（Ｓ３０５）。
【００３２】
次に、ＢＢ内の命令列を先頭から順にｒｕｌｅと照合する（Ｓ３０６）。全ての命令が処理済みであればステップＳ３０４へ戻り、次の基本ブロックの処理に移る。未処理の命令があれば、未処理の命令を１つ取り出す（ｓとする）（Ｓ３０７）。
次に、ｓから始まりｒｕｌｅと命令列長の一致する命令列をｒｕｌｅと照合する（Ｓ３０８）。照合の結果、一致しない場合にはステップＳ３０６へ戻り、次の命令から始まる命令列との照合処理に移る。
【００３３】
一方、照合の結果一致した場合には、ｒｕｌｅによる変換によってプログラムの意味が変わらないことを検証する（Ｓ３０８）。このＳステップ３０８の処理については、図４を参照して後で詳しく説明する。
検証が失敗した場合にはステップＳ３０６へ戻り、次の命令から始まる命令列との照合処理に移る。成功した場合には、ｒｕｌｅにもとづいて命令列を変換する（Ｓ３１０）。この変換処理後、ユーザに対して適用した変換規則とその結果削減された命令数を提示し、ステップＳ３０６へ戻る。尚、ユーザへの提示は、図１のディスプレイ装置１０２に、この変換処理の状況を表示することにより行なわれる。
【００３４】
図４は、図３のステップ３０９の処理フローを詳しく示す図である。
ここでは、変換規則による命令列に変換してもプログラムの意味が変わらないかどうかの判定を行う。
まず、命令列実行前の初期状態を用意する（ここではσ０とする）（Ｓ４０１）。ここで、全てのレジスタに対してその初期値を表す変数記号を割り当てる。次に、変換候補の命令列をσ０に対して実行した後の状態σ１を求める（Ｓ４０２）。これは命令列中の各命令を命令意味表１１０に基づいて置き換えた関数を求め、それをσ０に対して順に適用することで構成される。次に、ｒｕｌｅによる変換後の命令列をσ０に対して実行した後の状態σ２をステップＳ４０２と同様にして求める（Ｓ４０３）。
【００３５】
次に、変換前後のレジスタの値が等しいかをチェックする（Ｓ４０４）。これは、元の命令列の実行後に生存するレジスタについて、その値が変換前後で等しいかを１つずつ確認していく。全てのレジスタが確認済みである場合には、変換可能と判定して終了する（Ｓ４１０）。一方、確認済みでなければ、生存レジスタの集合から未処理のレジスタを１つ取り出す（ｒとする）（Ｓ４０５）。
次に、論理式として表現されている状態σ１におけるｒの値を公理表１１１に基づいて簡約する（Ｓ４０６）。簡約は、表で定義された等値式の左辺に適合する式を右辺に置き換えるという操作を、適合する式が存在しなくなるまで繰り返すことで行う。
【００３６】
次に、状態σ２におけるｒの値についてステップＳ４０６と同様に簡約する（Ｓ４０７）。その後、簡約された論理式σ１（ｒ）とσ２（ｒ）が同型であるかを判定する（Ｓ４０８）。判定の結果、両者が同型でなければ、変換不可能と判定して、処理を終了する（Ｓ４０９）。一方、両者が同型である場合、ステップＳ４０４へ戻り、次のレジスタの処理に移る。
以上の説明により、コンパイラの処理のために用意された各種の表１１０から１１２、パターンファイル１１３の構成、及び本実施例に特徴的な図３、図４による処理動作が理解された。
【００３７】
続いて、本実施例の適用例を示す。入力として図９のようなＣプログラム及び図１０のようなパターンファイルを考える。
図２におけるコード最適化及び解析処理（Ｓ２０２）の結果、図５のような中間コード１０９が作成される。また、中間コードの生成に並行して、図８のような生存表１１２が作成される。
【００３８】
次に、ユーザにより記述されたパターンファイルに基づく最適化処理が行なわれる（Ｓ２０３）。この処理の詳細については、図３に示すように、パターンファイル１１３がコンパイルに読み込まれ（Ｓ３０１）、次いで、全ての変換規則が未処理（Ｓ３０２）でなので、ステップＳ３０３へ進み、未処理の変換規則として例えば図１０のｒｕｌｅ１を取り出す。
【００３９】
次に、未処理ＢＢが有るかの判定において（Ｓ３０４）、全ての基本ブロックが未処理なので、未処理の基本ブロックとしてＢＢ１を取り出す（Ｓ３０５）。
次に、ステップＳ３０６、Ｓ３０７、Ｓ３０８により、ｒｕｌｅ１に適合する命令列をＢＢ１の先頭から順に探す。例えば図５の（７０１）から始まる命令列がｒｕｌｅ１に適合するので、ステップＳ３０９へ進み、変換によりプログラムの意味が変わらないことを検証する。
【００４０】
ステップ３０９の処理動作については、図４において、最初に初期状態σ０が用意される（Ｓ４０１）。ここでは未使用の変数記号としてｘ、ｙ、ｚ、ｗを用いる。次に、元の命令列の実行後の状態σ１を命令意味表１１０に従って作成して行く（Ｓ４０２）。
ここで、初期状態σ０は、例えば図１１（ａ）のようになっている。これに命令７０１が対応する意味関数λσ．σ［ａｎｄ（２，σ（Ｒ０））／Ｒ０］を適用して得られる状態がσａである。σａは、σ０のうちレジスタＲ０の値がａｎｄ（２，σ（Ｒ０））すなわちａｎｄ（２，ｘ）に更新されたものになっている。同様に命令７０２を適用してσｂ、命令７０３を適用してσ１が得られる。
【００４１】
次に、同様にして変換後の命令列の実行後の状態σ２を求める（Ｓ４０２）。求められたσ２は、例えば図１１（ｂ）のように構成される。そして、命令列の実行後に値が使用されるレジスタについて、その値が変換前後で等しいことを確認する（Ｓ４０４）。これは図８の生存表１１２から該当するレジスタはＲｃのみであることが分かる。そこでステップＳ４０５へ進みＲｃを取り出す。
【００４２】
次に、状態σ１におけるＲｃの値σ１（Ｒｃ）を図６（ｂ）の公理表１１１にもとづいて簡約する（Ｓ４０６）。簡約前のσ１（Ｒｃ）は、図８（ｃ）の式８０１である。これに公理ａｎｄ−ｅｌｉｍを適用すると式８０２となり、さらに公理ｅｘｔｓ−ｅｌｉｍを適用すると式８０３へと簡約できる。
同様にσ２（Ｒｃ）を簡約する（Ｓ４０７）が、これ以上適用できる公理が存在しないため、値は変化しない。そして、σ１（Ｒｃ）とσ２（Ｒｃ）が同型であるかを判定して（Ｓ４０９）、その結果同型であることが分かると、ステップＳ４０４へ戻る。ステップＳ４０４では全ての未処理レジスタについて変換前後の値が等しいかが判断されるが、未処理レジスタが存在しないと、ステップＳ４１０へ進み、変換可能と判定して終了する。
【００４３】
上記の処理の後は、図３のステップＳ３１０へ進み、命令列７０１、７０２，７０３をｒｕｌｅ１にもとづき｛ＴＳＴ ＃２、Ｒ０｝に置き換え、ステップＳ３０６へ戻る。ＢＢ１にはｒｕｌｅ１に適合する未処理な命令列は存在しないため、ステップＳ３０４へ戻り、未処理の基本ブロックであるＢＢ２、ＢＢ３の処理に移る。これらはｒｕｌｅ１に適合する命令列を含まないため、変換は実施せずにｒｕｌｅ１の処理を終了しステップＳ３０２へ戻る。パターンファイルには未処理の変換規則は存在しないため終了する。
【００４４】
上記処理の後、図２のステップＳ２０４、Ｓ２０５の処理動作に移り、アセンブリプログラムの実行コードが生成され、一連のコンパイル処理を終了する。生成される実行コードはユーザが指定した変換規則にもとづく最適化が適用されたものとなる。
【００４５】
このように生成されたアセンブリプログラムの実行コード１０７は、外部記憶装置１０５に一時的に格納される。その後、そのアセンブリプログラムはＲＯＭライタ等の書き込み装置によって、マイクロプロセッサ用のＲＯＭ等のメモリチップに記録される。
【００４６】
以上、ー実施例について説明したが、本発明は上記の実施例に限定されることなく、種々変形して実施し得る。例えば、図５〜図１１に示した、中間コード１０９、緒表１１０〜１１２やパターファイル１１３等は一例であり、これらの表現形式等を変更して実施できる。
【図面の簡単な説明】
【００４７】
【図１】一実施例におけるコンパイラが稼動する計算機システムの構成図。
【図２】一実施例におけるコンパイル処理の動作を示すフローチャート図。
【図３】一実施例による図２のコンパイル処理の動作における最適化処理（ステップＳ２０３）の詳細を示すフローチャート図。
【図４】一実施例による図３の最適化処理の動作におけるステップ３０９の詳細を示すフローチャート図。
【図５】一実施例における中間コード１０９の変遷の一例を示す図。
【図６】一実施例における命令意味表１１０の一例を示す図。
【図７】一実施例における公理表１１１の一例を示す図。
【図８】一実施例における生存表１１２の一例を示す図。
【図９】一実施例における入力としてのＣプログラムを示す図。
【図１０】一実施例におけるパターンファイル１１３の一例を示す図。
【図１１】一実施例における命令の最適化の様子を示す図。
【符号の説明】
【００４８】
１０１：ＣＰＵ、            １０２：ディスプレイ装置、
１０３：キーボード、        １０４：主記憶装置、
１０５：外部記憶装置、      １０６：ソースプログラム、
１０７：実行コード、        １０８：コンパイラ、
１０９：中間コード、        １１０：命令意味表、
１１１：公理表、            １１２：生存表、
１１３：パターンファイル。
【図１】
2006079494.tif 000003
【図２】
2006079494.tif 000004
【図３】
2006079494.tif 000005
【図４】
2006079494.tif 000006
【図５】
2006079494.tif 000007
【図６】
2006079494.tif 000008
【図７】
2006079494.tif 000009
【図８】
2006079494.tif 000010
【図９】
2006079494.tif 000011
【図１０】
2006079494.tif 000012
【図１１】
2006079494.tif 000013