(57)【特許請求の範囲】
【請求項１】
複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置であって、
特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する抽出手段と、
抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合における基本ブロックとの位置関係に応じて選択する選択手段と、
選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換するコード変換手段と
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記抽出手段は、
複数の基本ブロックを対象として、それらの後尾にある共通命令列集合を抽出する共通命令列集合抽出手段と、
初回は同一の基本ブロックに無条件に後続する複数の基本ブロックを対象として共通命令列集合抽出手段に共通命令列集合を抽出させ、２回目以降は共通の命令列を有する複数の基本ブロックから直前までに抽出された共通の命令列を除外したプログラム部分を対象として共通命令列集合抽出手段に共通命令列集合を抽出させる抽出制御手段と
を備えることを特徴とする請求項１記載のプログラム変換装置。
【請求項３】
前記選択手段は、
上下に連続する複数の階層にわたる共通命令列集合について、一対の共通命令列集合が上下に接する場合に、双方において同一の基本ブロックを選択する
ことを特徴とする請求項１または２記載のプログラム変換装置。
【請求項４】
前記選択手段は、
上下に連続する複数の階層にわたる共通命令列集合について、下層の１の共通命令列集合に対し上層の複数の共通命令列集合が接する場合に、要素数が最も多い上層の共通命令列集合と下層の共通命令列集合とにおいて同一の基本ブロックを選択する
ことを特徴とする請求項１または２記載のプログラム変換装置。
【請求項５】
前記選択手段は、
最後尾が分岐命令でない基本ブロックに含まれる命令列が共通命令列集合に属している場合に、当該基本ブロックを選択する
ことを特徴とする請求項１または２記載のプログラム変換装置。
【請求項６】
前記選択手段は、
抽出された各共通命令列集合において１以上の基本ブロックを、他の共通命令列集合における基本ブロックとの位置関係に応じて選択候補とする選択候補抽出部と、各共通命令列集合において選択候補とされた基本ブロックを１づつ選ぶ組合せを全て列挙する組合せ列挙部と、列挙された各々の組合せに従って基本ブロックを選択して前記変換を行った場合に変更される分岐命令のコードサイズをあらかじめ算出する分岐命令サイズ算出部とを備え、算出されるコードサイズが最も小さい組合せに従って基本ブロックを選択する
ことを特徴とする請求項１または２記載のプログラム変換装置。
【請求項７】
前記プログラム変換装置は、さらに、
前記変換により削除される命令列および変更される分岐命令についてコードサイズの変化量を算出し、変換によってコードサイズが減少しない基本ブロックにおいて命令列の削除および分岐命令の変更をしないようコード変換手段に対して制御する制御手段
を備えることを特徴とする請求項１または２記載のプログラム変換装置。
【請求項８】
複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置において用いられるプログラム変換方法であって、
特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する第１のステップと、
第１のステップで抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合において選択した基本ブロックとの位置関係に応じて選択する第２のステップと、
第２のステップで選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換する第３のステップと
を含むことを特徴とするプログラム変換方法。
【請求項９】
複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置において用いられるプログラムを記憶しているコンピュータ読取り可能な記録媒体であって、
特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する第１のステップと、
第１のステップで抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合において選択した基本ブロックとの位置関係に応じて選択する第２のステップと、
第２のステップで選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換する第３のステップと
をコンピュータに実行させるためのプログラムを記憶しているコンピュータ読取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータプログラムの変換技術に関し、特にプログラムの最適化技術に関する。
【０００２】
【従来の技術】
近年、ソフトウェア開発においては、開発効率、および保守性向上を指向して高水準言語を用いた開発が主流となっている。しかしながら、このような高水準言語からコンパイラが生成する目的プログラムは、アセンブラ等を用いて人間が作成する目的プログラムに比べると、一般に実行時間がより長くコードサイズがより大きい。このため、実行時間がより短くコードサイズがより小さいプログラムを生成することが、コンパイラに求められている。特に、記憶容量が厳しく制限される実行環境において稼動するプログラム、例えば組込み用途などのプログラムについては、コードサイズ削減への強い要請がある。
【０００３】
実行時間を短縮しかつコードサイズを削減する目的でプログラムを変換すること、または、実行時間またはコードサイズの一方を改善する目的でプログラムを変換することを最適化という。実行時間またはコードサイズの一方を改善する最適化においては、実行時間を短縮することによってコードサイズが増大する場合や、コードサイズを削減することによって実行時間が増加する場合があり得る。
【０００４】
最適化を行うための様々な技術が公知となっており、その中で、コードサイズを削減するものの１つに共通命令列合流最適化（テールマージ最適化ともいう）がある。
テールマージ最適化とは、同一の基本ブロックに無条件に制御を移す複数の基本ブロックの後尾にある同一の命令列のうち、１の命令列が共用されるようにプログラムを変換してコードサイズを削減する技法である。前記同一の命令列を要素とする集合を、以下、共通命令列集合と称する。
【０００５】
ここで、基本ブロックとは、一連の命令列であって、途中の命令から分岐せずかつ途中の命令へ分岐されることもない最長の命令列をいう。
図１９は、テールマージ最適化前後のプログラムの例を示しており、１１００ａは最適化前のプログラム、１１００ｂは最適化後のプログラム、１１０１ａ、１１０１ｂ、１１０２ａ、１１０２ｂ、１１０３、１１０４は基本ブロック、１１０５は共通命令列集合、１１０６は共用される命令列、１１０７〜１１１０は分岐命令である。
【０００６】
従来のコンパイラは、この例のテールマージ最適化において、共通命令列集合１１０５について基本ブロック１１０２ａに含まれる共通命令列を残し、基本ブロック１１０１ａに含まれる共通命令列を削除し、分岐命令１１０７の分岐先を変更して前記残した命令列１１０６が実行されるよう、プログラムを変換する。この変換により、基本ブロック１１０１ａから削除した共通命令列に相当するコードサイズを削減できる。
【０００７】
しかしながら、この最適化を行うことにより、プログラムの実行時間が増加する。最適化前のプログラム１１００ａでは基本ブロック１１０１ａを通る処理において１つの分岐命令１１０７が実行されるが、最適化後のプログラム１１００ｂでは分岐命令１１０９、１１１０の２つが実行される。すなわち、最適化を行うことによって基本ブロック１１０１ｂを通る処理において実行される分岐命令数が１増加し、このためにプログラムの実行時間が増加する。
【０００８】
最適化後、基本ブロック１１０２ｂを通る処理において実行される分岐命令数は最適化前と変わらず、プログラム全体として分岐命令数は１増加する。
図２０は、テールマージ最適化を２回繰返し行った過程を示すプログラム例である。１２００ａは最適化前のプログラム、１２００ｂは１回目のテールマージ最適化後のプログラム、１２００ｃは２回目のテールマージ最適化後のプログラム、１２０１ａ、１２０１ｂ、１２０２ａ、１２０２ｂ、１２０２ｃ、１２０３ａ、１２０３ｂ、１２０３ｃ、１２０４、１２０５、１２０６は基本ブロック、１２０７〜１２０８は共通命令列集合、１２０９〜１２１０は共用される命令列、１２１１〜１２１８は分岐命令である。
【０００９】
このように、テールマージ最適化を繰返し行って命令列を共用させることを、多段階テールマージ最適化と呼ぶ。
図２０の多段階テールマージ最適化は、１回目に共通命令列集合１２０７について基本ブロック１２０１ａに含まれる共通命令列が共用されるようにプログラムを変換し、２回目に共通命令列集合１２０８について基本ブロック１２０３ｂに含まれる共通命令列が共用されるようにプログラムを変換した例を示している。
【００１０】
この最適化後のプログラム１２００ｃについて、基本ブロック１２０１ｂ、１２０２ｃ、１２０３ｃを通る処理において実行される分岐命令数は、それぞれ、１、３、２であり、合計６である。
図２１は、図２０とは異なる基本ブロックに含まれる命令列が共用されるように多段階テールマージ最適化行った過程を示すプログラム例である。１３００ａは最適化前のプログラム、１３００ｂは１回目のテールマージ最適化後のプログラム、１３００ｃは２回目のテールマージ最適化後のプログラム、１３０１ａ、１３０１ｂ、１３０２ａ、１３０２ｂ、１３０２ｃ、１３０３ａ、１３０３ｂ、１３０３ｃ、１３０４、１３０５、１３０６は基本ブロック、１３０７〜１３０８は共通命令列集合、１３０９〜１３１０は共用される命令列、１３１１〜１３１８は分岐命令である。
【００１１】
図２１の多段階テールマージ最適化は、１回目に共通命令列集合１３０７について基本ブロック１３０３ａに含まれる共通命令列が共用されるようにプログラムを変換し、２回目に共通命令列集合１３０８について基本ブロック１３０３ｂに含まれる共通命令列が共用されるようにプログラムを変換した例を示している。
【００１２】
この最適化後のプログラム１３００ｃについて、基本ブロック１３０１ｂ、１３０２ｃ、１３０３ｃを通る処理において実行される分岐命令数は、それぞれ、２、２、１であり、合計５である。
このように、多段階テールマージ最適化においては、各段階において何れの基本ブロックに含まれる共通命令列が共用されるかの組合せに応じて、最適化後のプログラム全体として実行される分岐命令数が異なる。図２０および図２１の例の比較では、各段階で同一の基本ブロックに含まれる共通命令列が共用されるほうが（図２１）異なる基本ブロックに含まれる共通命令列が共用されるよりも（図２０）分岐命令数がより少なく抑えられる。
【００１３】
【発明が解決しようとする課題】
しかしながら、従来の多段階テールマージ最適化においては、図２０に示したように最適化後のプログラムにおいて実行される分岐命令数を最小に抑えるような組合せによって命令列が共用されない場合がある。すなわち、必ずしも実行時間が最短となるプログラムが得られないという問題がある。
【００１４】
上記の問題に鑑み、本発明は、複数の基本ブロックの末尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置であって、実行される分岐命令数が最小となるプログラムを生成する装置の提供を目的とする。
【００１５】
【課題を解決するための手段】
上記問題を解決するため、本発明のプログラム変換装置は、複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置であって、特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する抽出手段と、抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合において選択した基本ブロックとの位置関係に応じて選択する選択手段と、選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換するコード変換手段とを備える。
【００１６】
前記抽出手段は、複数の基本ブロックを対象として、それらの基本ブロックの後尾にある共通命令列集合を抽出する共通命令列集合抽出手段と、初回は同一の基本ブロックに無条件に後続する複数の基本ブロックを対象として共通命令列集合抽出手段に共通命令列集合を抽出させ、２回目以降は共通の命令列を有する複数の基本ブロックから直前までに抽出された共通の命令列を除外したプログラム部分を対象として共通命令列集合抽出手段に共通命令列集合を抽出させる抽出制御手段とを備えてもよい。
【００１７】
前記選択手段は、上下に連続する複数の階層にわたる共通命令列集合について、一対の共通命令列集合が上下に接する場合に、双方において同一の基本ブロックを選択してもよい。
前記選択手段は、上下に連続する複数の階層にわたる共通命令列集合について、下層の１の共通命令列集合に対し上層の複数の共通命令列集合が接する場合に、要素数が最も多い上層の共通命令列集合と下層の共通命令列集合とにおいて同一の基本ブロックを選択してもよい。
【００１８】
前記選択手段は、最後尾が分岐命令でない基本ブロックに含まれる命令列が共通命令列集合に属している場合に、当該基本ブロックを選択してもよい。
前記選択手段は、抽出された各共通命令列集合において１以上の基本ブロックを、他の共通命令列集合における基本ブロックとの位置関係に応じて選択候補とする選択候補抽出部と、各共通命令列集合において選択候補とされた基本ブロックを１づつ選ぶ組合せを全て列挙する組合せ列挙部と、列挙された各々の組合せに従って基本ブロックを選択して前記変換を行った場合に変更される分岐命令のコードサイズをあらかじめ算出する分岐命令サイズ算出部とを備え、算出されるコードサイズが最も小さい組合せに従って基本ブロックを選択してもよい。
【００１９】
前記プログラム変換装置は、さらに、前記変換により削除される命令列および変更される分岐命令についてコードサイズの変化量を算出し、変換によってコードサイズが減少しない基本ブロックにおいて命令列の削除および分岐命令の変更をしないようコード変換手段に対して制御する制御手段を備えてもよい。
本発明のプログラム変換方法は、複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置において用いられるプログラム変換方法であって、特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する第１のステップと、第１のステップで抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合において選択した基本ブロックとの位置関係に応じて選択する第２のステップと、第２のステップで選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換する第３のステップとを含む。
【００２０】
本発明のプログラム記録媒体は、複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置において用いられるプログラムを記憶しているコンピュータ読取り可能な記録媒体であって、特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する第１のステップと、第１のステップで抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合において選択した基本ブロックとの位置関係に応じて選択する第２のステップと、第２のステップで選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換する第３のステップとをコンピュータに実行させるためのプログラムを記憶している。
【００２１】
【発明の実施の形態】
＜第１実施形態＞
第１実施形態における、本発明のプログラム変換装置について説明する。
＜全体構成＞
本発明のプログラム変換装置１００は、ソースプログラムを目的プログラムに変換する装置であり、図１に示すように、字句解析部１０２、構文解析部１０３、中間コード生成部１０４、中間コード最適化部１０５、および、目的プログラム生成部１０７から構成される。
【００２２】
プログラム変換装置１００は、具体的には、プロセッサ、プログラムを記憶しているＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、作業用のＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のハードウェアにより実現される。前記各部の機能は、ＲＯＭに記憶されているプログラムをプロセッサが実行することにより実現される。前記各部の間におけるデータの受け渡しは、ＲＡＭ等のハードウェアを介して行われる。
【００２３】
字句解析部１０２は、入力されたソースプログラム１０１を解析し、ソースプログラム１０１を構成する字句を認識する。構文解析部１０３は、字句解析部１０２が認識した字句に基づいてソースプログラム１０１の構文を解析する。中間コード生成部１０４は、構文解析部１０３が解析した構文の意味を中間言語を用いて表記した中間コードを生成する。中間コード最適化部１０５は、中間コード生成部１０４が生成した中間コードを以下に示すようにして最適化する。目的プログラム生成部１０７は、中間コード最適化部１０５が最適化した中間コードに従って目的プログラム１０６を生成する。
【００２４】
中間コード最適化部１０５以外の構成は、一般的なコンパイラにおいて広く実施されている公知技術であるため、ここでは、詳細な説明を省略する。
＜中間コード最適化部＞
図２は、中間コード最適化部１０５を示すブロック図である。同図に示すように、中間コード最適化部１０５は、基本ブロック解析部１１１、および、テールマージ最適化部１１２からなる。
【００２５】
基本ブロック解析部１１１は、中間コード生成部１０４が生成した中間コードを解析して、基本ブロック、基本ブロック間の制御フロー、および、同一の基本ブロックに無条件に制御を移すような複数の基本ブロックを要素とする集合（以後、無条件先行ブロック集合と称する）と後続の基本ブロックとの組を抽出する。
【００２６】
図３（ａ）は基本ブロック解析部１１１によって抽出された基本ブロックおよび基本ブロック間の制御フローの模式図、図３（ｂ）は無条件先行ブロック集合の一覧を示す一例であり、２０１〜２０７は基本ブロック、２１１〜２１９は基本ブロック間の制御フロー、２２０は無条件先行ブロック集合と後続の基本ブロックとの組の一覧を表わしている。
【００２７】
基本ブロック解析部１１１が行うこれらの処理は、一般的なコンパイラにおいて広く実施されている公知技術であるため、ここでは、詳細な説明を省略する。テールマージ最適化部１１２は、共通命令列集合抽出部１１４、共用部分選択部１１５、および、コード変換部１１６からなる。
＜共通命令列集合抽出部＞
共通命令列集合抽出部１１４は、基本ブロック解析部１１１によって抽出された基本ブロック、制御フロー、および、無条件先行ブロック集合に基づいて、再帰的な抽出処理を含む抽出準備処理を行うことにより、無条件先行ブロック集合の後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する。
＜抽出準備処理＞
図４は、抽出準備処理を示すフローチャートである。図６は本処理の過程を示すために用いるプログラム（中間コード）の一例であり、３００は無条件先行ブロック集合、３０１〜３０５は無条件先行ブロック集合３００に属する基本ブロック、３０６は後続の基本ブロック、３０７〜３０９は共通命令列集合、３１１〜３５６は命令である。
【００２８】
以下、図４のフローチャートおよび図６のプログラム例を参照しながら、抽出準備処理について説明する。
共通命令列集合抽出部１１４は、ステップＳ１０〜ステップＳ１３の繰返し処理により、基本ブロック解析部１１１によって抽出された無条件先行ブロック集合ごとに、無条件先行ブロック集合に属する各基本ブロックの分岐命令を除いた最後尾の命令を求め（ステップＳ１１）、当該求めた命令を指定して抽出処理を呼び出す（ステップＳ１２）。
【００２９】
図６の例では、無条件先行ブロック集合３００に属する基本ブロック３０１〜３０５の分岐命令を除いた最後尾の命令である命令３１５、３２５、３３５、３４５、３５５を指定され、抽出処理が呼び出される。
＜抽出処理＞
図５は、ステップＳ１２の抽出処理の詳細を示すフローチャートである。以下、図５のフローチャートおよび図６のプログラム例を参照しながら、抽出処理について説明する。
【００３０】
初回の抽出処理において、共通命令列集合抽出部１１４は、ステップＳ１２の処理において指定された命令を同じ種類ごとに分類する（ステップＳ２０）。本例では、全てｍｏｖ  Ｒ０，（＿ａ）命令である５個の命令が指定されており、１種類に分類される。
共通命令列集合抽出部１１４は、ステップＳ２１〜ステップＳ２５の繰返し処理により、前記分類され、同じ命令が２以上ある命令の種類ごとに、当該種類の命令から基本ブロックの先頭に向かって命令の異同を順次比較し、全ての基本ブロックにおいて同じ命令が連続する部分を求め（ステップＳ２２）、当該求めた部分を要素とする共通命令列集合を作成する（ステップＳ２３）。
【００３１】
図６の例では、ｍｏｖ  Ｒ０，（＿ａ）命令について、命令３１５、３２５、３３５、３４５、３５５から基本ブロックの先頭に向かって命令の異同が順次比較され、基本ブロック３０１〜３０５において同じ命令が連続する部分である、命令３１４〜３１５、命令３２４〜３２５、命令３３４〜３３５、命令３４４〜３４５、命令３５４〜３５５を要素とする共通命令列集合３０７が作成される。
【００３２】
共通命令列集合抽出部１１４は、作成された共通命令列集合の各要素の直前に位置する命令を指定して図５のフローチャートに示す抽出処理を再帰的に呼び出し、基本ブロックの先頭に向かって階層的に存在する共通命令列集合を繰返し抽出する（ステップＳ２４）。
図６の例では、作成された共通命令列集合３０７の各要素の直前に位置する命令３１３、３２３、３３３、３４３、３５３を指定され２回目の抽出処理が呼び出される。
【００３３】
２回目の抽出処理において、共通命令列集合抽出部１１４は、指定された命令３１３、３２３、３３３、３４３、３５３をｍｏｖ  （＿ｄ），Ｒ１命令である命令３１３、３２３、および、ｍｏｖ  （＿ｃ），Ｒ１命令である命令３３３、３４３、３５３の２種類に分類する（ステップＳ２０）。
ｍｏｖ  （＿ｄ），Ｒ１命令について、命令３１２〜３１３、命令３２２〜３２３を要素とする共通命令列集合３０８が作成され、当該各要素の直前に位置する命令３１１、３２１を指定されて３回目の抽出処理が呼び出される。
【００３４】
３回目の抽出処理において、共通命令列集合抽出部１１４は、前記指定された命令３１１、３１２をｍｏｖ  （＿ａ），Ｒ１命令である命令３１１と、ｍｏｖ（＿ｂ），Ｒ１命令である命令３１２とに分類する（ステップＳ２０）。何れの種類の命令も１個であり、ステップＳ２１〜ステップＳ２５の繰返し処理の条件を満たさないため、命令３１１、３２１から基本ブロックの先頭に向かう部分について共通命令列集合の抽出処理は行われず、２回目の抽出処理の続きに戻る。
【００３５】
２回目の抽出処理の続きにおいて、ｍｏｖ  （＿ｃ），Ｒ１命令について、命令３３２〜３３３、命令３４２〜３４３、命令３５２〜３５３を要素とする共通命令列集合３０９が作成され、作成された共通命令列集合３０９の直前に位置する命令３３１、３４１、３５１を指定されて４回目の抽出処理が呼び出される。４回目の抽出処理においても、３回目と同様に、命令３３１、３４１、３５１から基本ブロックの先頭に向かう部分について共通命令列集合の抽出処理は行われない。
【００３６】
この結果、無条件先行ブロック集合３００において、共通命令列集合３０７〜３０９が抽出される。
＜共用部分選択部＞
共用部分選択部１１５は、再帰的な選択処理を含む選択準備処理を行うことにより、共通命令列集合抽出部１１４によって抽出された各共通命令列集合において共用されるべき１の命令列を含む基本ブロックを、他の共通命令列集合において選択された基本ブロックとの位置関係に応じて選択する。
＜選択準備処理＞
図７は、選択準備処理を示すフローチャートである。以下、図７のフローチャートおよび図６のプログラム例を参照しながら、選択準備処理について説明する。
【００３７】
共用部分選択部１１５は、ステップＳ３０〜ステップＳ３５の繰返し処理により、基本ブロック解析部１１１によって抽出された無条件先行ブロック集合ごとに、無条件先行ブロック集合の分岐命令を除いた最後尾に位置する共通命令列集合を求め（ステップＳ３１）、さらにステップＳ３２〜ステップＳ３４の繰返し処理により、当該求めた共通命令列集合を順次指定して選択処理を行う（ステップＳ３３）。
【００３８】
図６の例では、無条件先行ブロック集合３００の最後尾の共通命令列集合３０７を指定され、選択処理が呼び出される。
＜選択処理＞
図８は、ステップＳ３３の選択処理の詳細を示すフローチャートである。以下、図８のフローチャートおよび図６のプログラム例を参照しながら、選択処理について説明する。
【００３９】
選択処理の前半において、共用部分選択部１１５は、指定された共通命令列集合の直前に別の共通命令列集合が存在する場合（ステップＳ４０）、ステップＳ４１〜ステップＳ４３の繰返し処理により、当該直前に存在する各共通命令列集合を順次指定して、図８のフローチャートに示す選択処理を再帰的に呼び出す（ステップＳ４２）。この呼び出しが再帰的に繰返されることにより、指定された共通命令列集合において基本ブロックを選択するよりも前に、当該共通命令列集合から先頭に向けて階層的に存在する全ての共通命令列集合において共用されるべき命令列を含む基本ブロックが予め選択される。
【００４０】
選択処理の後半において、共用部分選択部１１５は、指定された共通命令列集合において、以下の条件判断に従って共用されるべき命令列を含む基本ブロックを選択する。すなわち、指定された共通命令列集合に最後尾が分岐命令でない基本ブロックが属している場合は（ステップＳ４４）当該基本ブロックを選択する（ステップＳ４５）。指定された共通命令列集合の直前に複数の共通命令列集合が存在する場合は（ステップＳ４６）当該複数の共通命令列集合のうち要素数が最大のものにおいて選択した基本ブロックを選択する（ステップＳ４７）。指定された共通命令列集合の直前に１の共通命令列集合が存在する場合は（ステップＳ４８）当該共通命令列集合において選択した基本ブロックを選択する（ステップＳ４９）。何れの場合にも該当しない場合は指定された共通命令列集合に属する任意の１の基本ブロックを選択する（ステップＳ５０）。
【００４１】
図６の例では、初回の選択処理は共通命令列集合３０７が指定されて呼び出され、当該処理の前半において、共通命令列集合３０７の直前に位置する共通命令列集合３０８、３０９を各々指定して、２回目、３回目の選択処理が呼び出される。
２回目の選択処理の前半において、指定された共通命令列集合３０８の直前に位置する共通命令列集合が存在しないため、選択処理の再帰的な呼び出しは行われない。同処理の後半において、共通命令列集合３０８において共用されるべき命令列を含む基本ブロックが選択される。この場合はステップＳ４４、Ｓ４６、Ｓ４８の何れの条件にも該当せず、ステップＳ５０に従い任意の１の基本ブロックが選択される。ここでは、命令３１２〜３１３を含む基本ブロック３０１が選択されるものとする。
【００４２】
３回目の選択処理においても、指定された共通命令列集合３０９について、２回目と同様の処理および条件判断が行われる。ここでは、命令３３２〜３３３を含む基本ブロック３０３が選択されるものとする。
２回目、３回目の選択処理が行われた後、初回の選択処理の後半が実行される。共通命令列集合３０７の直前に、共通命令列集合３０８、３０９が存在しステップＳ４６の条件を満たすため、ステップＳ４７により共通命令列集合３０９について選択した基本ブロック３０３を選択する。
【００４３】
この結果、共通命令列集合３０７、３０８、３０９において共用すべき命令列を含む基本ブロックとして、それぞれ、基本ブロック３０３、３０３、３０１が選択される。
＜選択条件の根拠＞
以下、前記ステップＳ４４〜Ｓ５０により選択された基本ブロックに含まれる命令列を共用させると、最適化後のプログラムにおいて分岐命令の実行回数を最小にできることを、図１３〜図１６の概念図を用いて示す。
【００４４】
テールマージ最適化においてコンパイラは、各共通命令列集合において選択されなかった基本ブロックの命令列を選択された基本ブロックの命令列の先頭への分岐命令に置き換えることにより当該選択された基本ブロックの命令列を共用させる。このため、選択されなかった基本ブロックの命令列を元実行していた処理において当該置き換えられた分岐命令が実行される。係る分岐命令が実行される数は次のように求められる。
【００４５】
図１３（ａ）は、共通命令列集合ａの直前に他の共通命令列集合が存在せず、共通命令列集合ａがｍ個の要素からなる場合を表わす概念図である。図１３（ｂ）、（ｃ）にそれぞれ示すように、基本ブロック１の命令列を共用させると（ｍ−１）個、基本ブロックｍの命令列を共用させると（ｍ−１）個の処理において、置き換えられた分岐命令ｊｍｐ  Ｌ１が実行される。分岐命令が実行される数はどの基本ブロックに含まれる命令列を選択しても（ｍ−１）であり差異がない。ゆえに、ステップＳ５０において、任意の１の基本ブロックを選択する。
【００４６】
図１４（ａ）は、共通命令列集合ａの直前に１の共通命令列集合ｂが存在して、共通命令列集合ａがｍ個、共通命令列集合ｂがｉ個（１＜ｉ＜ｍ）の要素からなる場合を表わす概念図である。図１４（ｂ）、（ｃ）にそれぞれ示すように、共通命令列集合ａにおいて共用させた命令列ａと同一の基本ブロックに含まれる命令列を共用させると（ｍ−ｉ）個、それ以外の命令列を共用させると（ｍ−１）個の処理において、置き換えられた分岐命令ｊｍｐ  Ｌ１が実行される。ここで（ｍ−ｉ）＜（ｍ−１）であり、直前の共通命令列集合において共用させた命令列と同一の基本ブロックに含まれる命令列を共用させると、実行される分岐命令の数をより少なくできる。ゆえに、ステップＳ４８、Ｓ４９において、直前の共通命令列集合において選択した基本ブロックを選択する。
【００４７】
図１５（ａ）は、共通命令列集合ａの直前に複数の共通命令列集合ｂ、ｃ、…が存在して、共通命令列集合ａがｍ個、共通命令列集合ｂ、ｃ、…がｉ、ｊ、…個（１＜…＜ｊ＜ｉ＜ｍ）の要素からなる場合を表わす概念図である。図１５（ｂ）、（ｃ）、（ｄ）にそれぞれ示すように、共通命令列集合ｂにおいて共用させた命令列の直後の命令列を共用させると（ｍ−ｉ）個、共通命令列集合ｃにおいて共用させた命令列の直後の命令列を共用させると（ｍ−ｊ）個、それ以外の命令列を共用させると（ｍ−１）個の処理において、置き換えられた分岐命令ｊｍｐ  Ｌ１が実行される。ここで（ｍ−ｉ）＜（ｍ−ｊ）＜（ｍ−１）であり、直前の共通命令列集合のうち要素数が最も多いものにおいて共用させた命令列と同一の基本ブロックに含まれる命令列を共用させると、分岐命令の実行回数をより少なくできる。ゆえに、ステップＳ４６、Ｓ４７において、直前の共通命令列集合のうち要素数が最大のものについて選択した基本ブロックを選択する。
【００４８】
前記命令列を共用させるための分岐命令のほかに、後続の基本ブロックへ制御を移行させるための分岐命令が実行される場合がある。係る分岐命令は、後続の基本ブロックとメモリ領域が連続している高々１個の基本ブロックを除いて全ての基本ブロックの最後尾に存在する。
図１６（ａ）は、無条件先行ブロック集合にｍ個の基本ブロックが属しており、基本ブロック１の最後尾の命令が分岐命令でない場合を表わす概念図である。図１６（ｂ）、（ｃ）にそれぞれ示すように、基本ブロック１に含まれる命令列を共用させると係る分岐命令ｊｍｐ  Ｌ０は全く実行されず、その他の基本ブロックに含まれる命令列を共用させるとｍ個の処理において係る分岐命令ｊｍｐ  Ｌ０が実行される。
【００４９】
この個数ｍは、前記命令列を共用させるために実行される分岐命令の個数の何れよりも大きいため、他の条件に優先してこの分岐命令を含まない命令列を選択すると分岐命令の実行回数をより少なくできる。ゆえに、ステップＳ４４、Ｓ４５において、最後尾が分岐命令でない基本ブロックが共通命令列集合に属している場合は、他の条件に優先して当該基本ブロックを選択する。
【００５０】
以上より、ステップＳ４４〜Ｓ５０で選択された基本ブロックに含まれる命令列を共用させることで、最適化後のプログラムにおいて分岐命令の実行回数を最小にできる。
＜コード変換部＞
コード変換部１１６は、再帰的なコード変換処理を含むコード変換準備処理を実行して、共用部分選択部１１５が選択した基本ブロックに含まれる命令列が各共通命令列集合において共用されるよう、プログラムを変換する。
＜コード変換準備処理＞
図９は、コード変換準備処理を示すフローチャート、図１１および図１２はコード変換準備処理およびコード変換処理の過程を示すために用いるプログラムの一例である。図１１は図６のプログラムに対して共通命令列集合３０８、３０９について共用部分選択部１１５が選択した基本ブロックに含まれる命令列を共用させた結果のプログラムを示しており、３０１ａ、３０１ｂ、３０２ａ、３０３ａ、３０３ｂ、３０４ａ、３０５ａ、３０６は基本ブロック、３０７、３０８、３０９は共通命令列集合、３１１〜３２５、３２６ａ、３３１〜３４５、３４６ａ、３５１〜３５５、３５６ａは命令およびラベルである。図１２は図１１のプログラムに対して共通命令列集合３０７について共用部分選択部１１５が選択した基本ブロックに含まれる命令列を共用させた結果のプログラムを示しており、３０１ａ、３０１ｃ、３０２ａ、３０３ａ、３０３ｂ、３０３ｃ、３０４ａ、３０５ａ、３０６は基本ブロック、３０７、３０８、３０９は共通命令列集合、３１１〜３１３、３１６ａ、３１７、３２１、３２６ａ、３３１〜３４１、３４６ａ、３５１、３５６ａは命令およびラベルである。
【００５１】
以下、図９のフローチャートおよび図１１のプログラム例を参照しながら、コード変換準備処理について説明する。
コード変換部１１６は、ステップＳ６０からステップＳ６５の繰返し処理により、基本ブロック解析部１１１によって抽出された無条件先行ブロック集合ごとに、無条件先行ブロック集合の分岐命令を除いた最後尾の共通命令列集合を求め（ステップＳ６１）、さらにステップＳ６２〜ステップＳ６４の繰返し処理により、当該求めた共通命令列集合を順次指定してコード変換処理を行う（ステップＳ６３）。
【００５２】
図１１の例では、無条件先行ブロック集合３００の最後尾に位置する共通命令列集合３０７を指定され、コード変換処理が呼び出される。
＜コード変換処理＞
図１０は、ステップＳ６３のコード変換処理の詳細を示すフローチャートである。以下、図１０のフローチャート並びに図１１および図１２のプログラム例を参照しながら、コード変換処理について説明する。
【００５３】
コード変換処理の前半において、コード変換部１１６は、指定された共通命令列集合の直前に別の共通命令列集合が存在する場合（ステップＳ７０）、ステップＳ７１〜ステップＳ７３の繰返し処理により、当該直前に存在する各共通命令列集合を順次指定して、図１０のフローチャートに示すコード変換処理を再帰的に呼び出す（ステップＳ７２）。この呼び出しが再帰的に繰返されることによって、指定された共通命令列集合においてコード変換を行うよりも前に、当該共通命令列集合から先頭に向けて階層的に存在する全ての共通命令列集合において共用部分選択部１１５によって選択された基本ブロックに含まれる命令列が共用されるようにプログラムが変換される。
【００５４】
コード変換処理の後半において、コード変換部１１６は、共用部分選択部１１５によって選択された基本ブロックに含まれる命令列の直前にラベルがない場合は（ステップＳ７４）、当該場所に新たにラベルを作成し（ステップＳ７５）、その後ステップＳ７６からステップＳ８０の繰返し処理により、選択されなかった各基本ブロックについて順次以下の処理を行う。すなわち、当該基本ブロックの最後尾の分岐命令について分岐先が更新されていなければ（ステップＳ７７）前記選択された基本ブロックの命令列の直前に変更し（ステップＳ７８）、当該選択されなかった基本ブロックの命令列を削除する（ステップＳ７９）。
【００５５】
図１１および図１２の例では、初回のコード変換処理は共通命令列集合３０７を指定して呼び出され、当該処理の前半において、共通命令列集合３０７の直前に位置する共通命令列集合３０８、３０９を各々指定して、２回目、３回目のコード変換処理が呼び出される。
２回目のコード変換処理の前半において、指定された共通命令列集合３０８の直前に位置する他の共通命令列集合が存在しないため、コード変換処理の再帰的な呼び出しは行われない。同処理の後半において、共用部分選択部１１５によって選択された基本ブロック３０１ａに含まれる命令３１２〜３１３からなる命令列の直前に新たにラベル３１７が作成され、分岐命令３２６ａの分岐先がＬ２に変更され、選択されなかった基本ブロックの命令列が削除される。
【００５６】
３回目のコード変換処理の前半においても、２回目の処理と同様、コード変換処理の再帰的な呼び出しは行われず、同処理の後半において、共用部分選択部１１５によって選択された基本ブロック３０１ｂに含まれる命令３３２〜３３３からなる命令列の直前に新たにラベル３３７が作成され、分岐命令３４６ａ、３５６ａの分岐先がＬ３に変更され、選択されなかった基本ブロックの命令列が削除される。
【００５７】
この結果、図１１に示したプログラムが得られる。
２回目、３回目のコード変換処理が行われた後、初回のコード変換処理の後半が実行される。共用部分選択部１１５によって選択された基本ブロック３０３ｃに含まれる命令３３４〜３３５からなる命令列の直前に新たにラベル３３８が作成され、まだ変更されていない分岐命令３１６ａの分岐先がＬ４に変更され、選択されなかった基本ブロックの命令列が削除される。
【００５８】
この結果、図１２に示したプログラムが得られる。
この構成によれば、多段階テールマージ最適化後のプログラムにおいて実行される分岐命令の数を最小にすることができる。
なお、前記共通命令列集合抽出部１１４に共通命令列集合抽出手段および共通命令列集合抽出制御手段を設け、抽出処理のステップＳ２２〜Ｓ２３を共通命令列集合抽出手段により実行し、抽出処理のその他のステップと抽出準備処理の各ステップとを共通命令列集合抽出制御手段により実行してもよい。
【００５９】
なお、前記共用部分選択部１１５の選択処理において、任意に１の命令列を選択すべき共通命令列集合、および、要素数が最大の共通命令列集合が直前に複数存在する共通命令列集合においては、共用すべき命令列の候補が複数存在する。係る共通命令列集合を含む無条件先行ブロック集合では分岐命令の実行回数を最小にする命令列の組合せが複数存在する。
【００６０】
係る場合には、前記共用部分選択部１１５は、各共通命令列集合において共用すべき命令列の候補を１つずつ選ぶ組合せをあらかじめ列挙し、各々の組合せに従って命令列を共用させた場合のプログラムについて分岐命令のサイズを算出し、サイズが最も小さくなる組合せを選択してもよい。
この構成によれば、多段階テールマージ最適化後のプログラムにおいて実行される分岐命令の数を最小にした上で、分岐命令のサイズを最小にすることができる。
【００６１】
なお、目的プログラムによっては分岐命令のコードサイズが分岐距離に応じて増減するという特性を有するものがある。係る特性を有する目的プログラムを生成する場合において、本プログラム変換装置は、コード変換部１１６が前記変換を行った場合に削除される命令列および変更される分岐命令についてコードサイズの変化量をあらかじめ算出し、変換によってコードサイズが減少しない基本ブロックにおいて命令列の削除および分岐命令の変更をしないようコード変換部１１６に対して制御する制御手段を備えてもよい。
【００６２】
この構成によれば、例えば、図１２の基本ブロック３０１ｃの最後尾の分岐命令について分岐先が変更されることによりコードサイズが増加する場合であって、当該増加するコードサイズが削除される命令列のコードサイズと等しいかより大きい場合、基本ブロック３０１ｃにおける命令列の削除と分岐命令の変更は行われない。これにより、前記特性を有する目的プログラムにおいて、変換によりコードサイズが増加する可能性を排除できる。
【００６３】
なお、コンパイラによっては、生成された目的プログラムに対して最適化を行うものがある。係るコンパイラにおいては、目的プログラムに対してテールマージ最適化を行う構成としてもよい。図１７は、係るプログラム変換装置１２０の構成を示す図であり、目的プログラム最適化部１０８は、基本ブロック解析部１２１、テールマージ最適化部１２２を含み、目的プログラム生成部１０７が生成した目的プログラムを入力され、前記中間コード最適化部１０５と同様の処理を行い、目的プログラム１０６を出力する。
【００６４】
この構成によれば、目的プログラムに対して最適化を行うコンパイラにおいても、本発明を適用することができる。
＜第２実施形態＞
第２実施形態におけるプログラム変換装置は、第１実施形態に対して、共用部分選択部１１５の動作が異なる。第２実施形態において、共用部分選択部１１５は、選択した命令列を共用させたプログラムにおける分岐命令のサイズを算出する。当該分岐命令のサイズは共用させる命令列が含まれる基本ブロックの位置関係に応じて異なり、共用部分選択部１１５はサイズが最も小さくなる命令列を共用すべき命令列として選択する。
＜選択処理＞
図１８は、第２実施形態における選択処理を示すフローチャートである。以下、図１８のフローチャートを参照しながら、第２実施形態における選択処理について説明する。
【００６５】
共用部分選択部１１５は、ステップＳ９０〜ステップＳ９４の繰返し処理により、基本ブロック解析部１１１によって抽出された無条件先行ブロック集合ごとに、共用させた場合に分岐命令のサイズが最小となる命令列の組合せを求める。具体的には、各共通命令列集合から基本ブロックを１づつ選ぶ組合せを列挙し（ステップＳ９１）、ステップＳ９２〜Ｓ９４の繰返し処理により、列挙された組合せごとに、当該組合せに従って選択された基本ブロックに含まれる命令列を共用させた場合のプログラムにおける分岐命令のサイズを算出し、分岐命令のサイズが最も小さくなる組合せを共用すべき命令列が含まれる基本ブロックとして選択する（ステップＳ９５）。
【００６６】
この構成によれば、多段階テールマージ最適化後のプログラムにおいて分岐命令のサイズを最小にすることができる。
なお、生成された目的プログラムに対して最適化を行うコンパイラにおいては、目的プログラムに対してテールマージ最適化を行う構成としてもよい。
この構成によれば、目的プログラムに対して最適化を行うコンパイラにおいても、本発明を適用することができる。
【００６７】
【発明の効果】
本発明のプログラム変換装置は、複数の基本ブロックの後尾にある同一の命令列についてそのうちの１が共用されるようにプログラムを変換してコードサイズを削減するプログラム変換装置であって、特定の基本ブロックに無条件に後続する他の複数の基本ブロックを対象として、それらの異なる基本ブロック内に存在する同一の命令列の集合であって、それらの基本ブロックの後尾から先頭に向けて階層的に存在する共通命令列集合を抽出する抽出手段と、抽出された各共通命令列集合において何れか１の命令列を含む基本ブロックを、他の共通命令列集合において選択した基本ブロックとの位置関係に応じて選択する選択手段と、選択された基本ブロック中の命令列が他の基本ブロックにおいて共用されるようにプログラムを変換するコード変換手段とを備える。
【００６８】
この構成によれば、あらかじめ、階層的に存在する全ての共通命令列集合を抽出し、共用させる命令列を含む基本ブロックの位置関係を複数の階層にわたって検討し、最適化を行ったプログラムにおいて実行される分岐命令数の多寡を知った上で、共用すべき命令列が含まれる基本ブロックを選択できるため、従来の多段階テールマージ最適化に比べて、当該分岐命令数をより低減することができる。
【００６９】
前記抽出手段は、複数の基本ブロックを対象として、それらの基本ブロックの後尾にある共通命令列集合を抽出する共通命令列集合抽出手段と、初回は同一の基本ブロックに無条件に後続する複数の基本ブロックを対象として共通命令列集合抽出手段に共通命令列集合を抽出させ、２回目以降は共通の命令列を有する複数の基本ブロックから直前までに抽出された共通の命令列を除外したプログラム部分を対象として共通命令列集合抽出手段に共通命令列集合を抽出させる抽出制御手段とを備えてもよい。
【００７０】
この構成によれば、前記階層的に存在する共通命令列集合を効率よく抽出することができる。
前記選択手段は、上下に連続する複数の階層にわたる共通命令列集合について、一対の共通命令列集合が上下に接する場合に、双方において同一の基本ブロックを選択してもよい。
【００７１】
前記選択手段は、上下に連続する複数の階層にわたる共通命令列集合について、下層の１の共通命令列集合に対し上層の複数の共通命令列集合が接する場合に、要素数が最も多い上層の共通命令列集合と下層の共通命令列集合とにおいて同一の基本ブロックを選択してもよい。
前記選択手段は、最後尾が分岐命令でない基本ブロックに含まれる命令列が共通命令列集合に属している場合に、当該基本ブロックを選択してもよい。
【００７２】
これらの構成によれば、最適化を行ったプログラムにおいて実行される分岐命令数を最小にすることができる。
前記選択手段は、抽出された各共通命令列集合において１以上の基本ブロックを、他の共通命令列集合における基本ブロックとの位置関係に応じて選択候補とする選択候補抽出部と、各共通命令列集合において選択候補とされた基本ブロックを１づつ選ぶ組合せを全て列挙する組合せ列挙部と、列挙された各々の組合せに従って基本ブロックを選択して前記変換を行った場合に変更される分岐命令のコードサイズをあらかじめ算出する分岐命令サイズ算出部とを備え、算出されるコードサイズが最も小さい組合せに従って基本ブロックを選択してもよい。
【００７３】
この構成によれば、最適化を行ったプログラムにおいて実行される分岐命令数を最小にした上で、分岐命令のサイズを最小にすることができる。
前記プログラム変換装置は、さらに、前記変換により削除される命令列および変更される分岐命令についてコードサイズの変化量を算出し、変換によってコードサイズが減少しない基本ブロックにおいて命令列の削除および分岐命令の変更をしないようコード変換手段に対して制御する制御手段を備えてもよい。
【００７４】
この構成によれば、生成する目的プログラムの分岐命令のコードサイズが分岐距離に応じて増減するという特性を有する場合に、最適化を行うことによりコードサイズが増加する可能性を排除できる。
【図面の簡単な説明】
【図１】プログラム変換装置の機能ブロック図である。
【図２】中間コード最適化部の機能ブロック図である。
【図３】基本ブロックおよび基本ブロック間の制御フローの模式図、並びに、無条件先行ブロック集合の一覧を示す一例である。
【図４】抽出準備処理を示すフローチャートである。
【図５】抽出処理を示すフローチャートである。
【図６】抽出処理の過程を示すために用いるプログラムの一例である。
【図７】選択準備処理を示すフローチャートである。
【図８】選択処理を示すフローチャートである。
【図９】コード変換準備処理を示すフローチャートである。
【図１０】コード変換処理を示すフローチャートである。
【図１１】コード変換処理の過程を示すために用いるプログラムの一例である。
【図１２】コード変換処理の過程を示すために用いるプログラムの一例である。
【図１３】選択条件の根拠を示すために用いる概念図である。
【図１４】選択条件の根拠を示すために用いる概念図である。
【図１５】選択条件の根拠を示すために用いる概念図である。
【図１６】選択条件の根拠を示すために用いる概念図である。
【図１７】プログラム変換装置の機能ブロック図である。
【図１８】第２実施形態における選択処理を示すフローチャートである。
【図１９】テールマージ最適化前後のプログラムの例である。
【図２０】テールマージ最適化を２回繰返し行った過程を示すプログラム例である。
【図２１】テールマージ最適化を２回繰返し行った過程を示すプログラム例である。
【符号の説明】
１００    プログラム変換装置
１０１    ソースプログラム
１０２    字句解析部
１０３    構文解析部
１０４    中間コード生成部
１０５    中間コード最適化部
１０６    目的プログラム
１０７    目的プログラム生成部
１０８    目的プログラム最適化部
１１１    基本ブロック解析部
１１２    テールマージ最適化部
１１４    共通命令列集合抽出部
１１５    共用部分選択部
１１６    コード変換部
１２０    プログラム変換装置
１２１    基本ブロック解析部
１２２    テールマージ最適化部
３００    無条件先行ブロック集合
３０１〜３０５、３０１ａ〜３０５ａ、３０１ｂ、３０１ｃ、３０３ｃ    基本ブロック
３０７〜３０９    共通命令列集合
３１１〜３５６、３１６ａ、３２６ａ、３４６ａ、３５６ａ    命令
３１７、３３７、３３８    ラベル
１１００ａ、１１００ｂ    プログラム
１１０１ａ、１１０１ｂ、１１０２ａ、１１０２ｂ、１１０３、１１０４    基本ブロック
１１０５    共通命令列集合
１１０６    共用される命令列
１１０７〜１１１０    分岐命令
１２００ａ、１２００ｂ、１２００ｃ    プログラム
１２０１ａ、１２０１ｂ、１２０２ａ、１２０２ｂ、１２０２ｃ、１２０３ａ、１２０３ｂ、１２０３ｃ、１２０４、１２０５、１２０６    基本ブロック
１２０７、１２０８    共通命令列集合
１２０９、１２１０    共用される命令列
１２１１〜１２１８    分岐命令
１３００ａ、１３００ｂ、１３００ｃ  プログラム
１３０１ａ、１３０１ｂ、１３０２ａ、１３０２ｂ、１３０２ｃ、１３０３ａ、１３０３ｂ、１３０３ｃ、１３０４、１３０５、１３０６    基本ブロック
１３０７、１３０８    共通命令列集合
１３０９、１３１０    共用される命令列
１３１１〜１３１８    分岐命令
【図１】
0003650713.tif 000002
【図２】
0003650713.tif 000003
【図３】
0003650713.tif 000004
【図４】
0003650713.tif 000005
【図５】
0003650713.tif 000006
【図６】
0003650713.tif 000007
【図７】
0003650713.tif 000008
【図８】
0003650713.tif 000009
【図９】
0003650713.tif 000010
【図１０】
0003650713.tif 000011
【図１１】
0003650713.tif 000012
【図１２】
0003650713.tif 000013
【図１３】
0003650713.tif 000014
【図１４】
0003650713.tif 000015
【図１５】
0003650713.tif 000016
【図１６】
0003650713.tif 000017
【図１７】
0003650713.tif 000018
【図１８】
0003650713.tif 000019
【図１９】
0003650713.tif 000020
【図２０】
0003650713.tif 000021
【図２１】
0003650713.tif 000022