(57)【要約】【課題】命令の実行順序を変更することによりプログラムを最適化する。【解決手段】命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置は、第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、第１命令及び第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定部と、置換可能性判定部により置換可能と判定された場合に、第１命令に代えて共通処理命令群を第１命令列中に生成する共通処理命令群生成部と、第１命令列以外の命令列であって、当該命令列の次に第２命令列が実行される第３命令列に、第２命令を挿入する命令挿入部とを備える。【選択図】  図１
2004265279.tif 000002
【特許請求の範囲】
【請求項１】
命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置であって、
第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、前記第１命令及び前記第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定部と、
前記置換可能性判定部により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成する共通処理命令群生成部と、
前記第１命令列以外の命令列であって、当該命令列の次に前記第２命令列が実行される第３命令列に、前記第２命令を挿入する命令挿入部と
を備えるコンパイラ装置。
【請求項２】
前記置換可能性判定部は、前記共通処理命令群の命令数が、前記第１命令及び前記第２命令を別個に実行した場合の命令数より少ない場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定する請求項１記載のコンパイラ装置。
【請求項３】
前記置換可能性判定部は、前記共通処理命令群の実行を開始してから完了するまでに要する実行時間が、前記第１命令及び前記第２命令のそれぞれを別個に実行した場合の実行時間より短い場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定する請求項１記載のコンパイラ装置。
【請求項４】
前記置換可能性判定部は、前記第１命令が、メモリから第１データを読み出す命令であり、かつ前記第２命令が、メモリから前記第１データとは異なるアドレスに格納された前記第２データを読み出す命令であり、かつ前記第１データ及び前記第２データを１命令で読み出すことができる場合に、前記第１命令及び前記第２命令を、前記共通処理命令群に置換可能と判定し、
前記共通処理命令群生成部は、前記共通処理命令群として、メモリから前記第１データ及び前記第２データを１命令で読み出す前記共通処理命令と、当該共通処理命令により読み出されたデータから前記第１データを抽出する第１抽出命令と、当該共通処理命令により読み出されたデータから前記第２データを抽出する第２抽出命令とを前記第１命令列中に生成する請求項１記載のコンパイラ装置。
【請求項５】
前記共通処理命令群生成部は、前記共通処理命令群として、前記共通処理命令と、抽出したデータに対して更に符号拡張を行う前記第１抽出命令と、抽出したデータに対して更に符号拡張を行う前記第２抽出命令とを生成と、前記第２抽出命令が抽出したデータを符号拡張する符号拡張命令とを生成することを特徴とする請求項４記載のコンパイラ装置。
【請求項６】
前記共通処理命令群生成部は、前記共通処理命令群として、前記共通処理命令と、抽出したデータに対して更にゼロ拡張を行う前記第１抽出命令と、抽出したデータに対して更にゼロ拡張を行う前記第２抽出命令とを生成と、前記第２抽出命令が抽出したデータをゼロ拡張するゼロ拡張命令とを生成することを特徴とする請求項４記載のコンパイラ装置。
【請求項７】
前記置換可能性判定部は、前記第１命令が、メモリから第１データを読み出す命令であり、かつ前記第２命令が、メモリから前記第１データとは異なるアドレスに格納された前記第２データを読み出す命令である場合に、前記第１命令及び前記第２命令を、前記共通処理命令群に置換可能と判定し、
前記共通処理命令群生成部は、前記共通処理命令群として、メモリから前記第１データ及び前記第２データのそれぞれを読み出し２つのレジスタのそれぞれに値を格納する前記共通処理命令を前記第１命令列中に生成する請求項２記載のコンパイラ装置。
【請求項８】
前記置換可能性判定部は、前記第１命令が、複数の命令によりロードされるサイズの第１定数データを第１レジスタに格納する命令の組であり、かつ前記第２命令が、前記第１定数データから予め定められた差分以内の第２定数データを第２レジスタに格納する命令の組である場合に、前記第１命令及び前記第２命令を前記共有処理命令群に置換可能と判定し、
前記共通処理命令群生成部は、前記共通処理命令群として、前記第１定数データを前記第１レジスタに格納する命令と、前記第２定数データの前記第１定数データに対する差を当該第１レジスタの値に加えた結果を前記第２レジスタに格納する命令とを前記第１命令列中に生成する請求項１記載のコンパイラ装置。
【請求項９】
前記置換可能性判定部は、前記第１命令が、レジスタに格納されたデータをシフトするシフト命令であり、かつ前記第２命令が、データの予め定められた領域のビットを抽出するマスク命令である場合に、前記第１命令及び前記第２命令を前記共有処理命令に置換可能と判定し、
前記共通処理命令群生成部は、前記共通処理命令として、前記レジスタから指定した範囲の桁のデータを抽出するローテートマスク命令を前記第１命令列中に生成する請求項１記載のコンパイラ装置。
【請求項１０】
前記置換可能性判定部は、前記プログラムの実行結果が同一であることを保証しつつ前記第２命令を移動できる範囲が、前記プログラムの実行結果が同一であることを保証しつつ前記第１命令を移動できる範囲と重なる場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能であると判定する請求項１記載のコンパイラ装置。
【請求項１１】
前記プログラムの実行結果が同一で、かつ前記第２命令の実行回数を増やすことなく前記第２命令を移動することができる当該第２命令の移動範囲を解析する移動可能範囲解析部を更に備え、
前記置換可能性判定部は、前記第１命令が、前記移動可能範囲解析部により解析された前記移動範囲にある場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定し、
前記共通処理命令群生成部は、前記置換可能性判定部により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成し、
前記命令挿入部は、前記置換可能性判定部により置換可能と判定されなかった場合に、前記第２命令を、前記移動可能範囲解析部により解析された範囲のうち、前記第２命令により生成される値の生存区間が最小となる箇所に移動する請求項１０記載のコンパイラ装置。
【請求項１２】
命令の実行順序を変更することによりプログラムを最適化するコンパイル方法であって、
第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、前記第１命令及び前記第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定段階と、
前記置換可能性判定段階により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成する共通処理命令群生成段階と、
前記第１命令列以外の命令列であって、当該命令列の次に前記第２命令列が実行される第３命令列に、前記第２命令を挿入する命令挿入段階と
を備えるコンパイル方法。
【請求項１３】
命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、
前記コンピュータを、
第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、前記第１命令及び前記第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定部と、
前記置換可能性判定部により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成する共通処理命令群生成部と、
前記第１命令列以外の命令列であって、当該命令列の次に前記第２命令列が実行される第３命令列に、前記第２命令を挿入する命令挿入部と
して機能させるコンパイラプログラム。
【請求項１４】
前記置換可能性判定部は、前記共通処理命令群の実行を開始してから完了するまでに要する実行時間が、前記第１命令及び前記第２命令のそれぞれを別個に実行した場合の実行時間より短い場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定する請求項１３記載のコンパイラプログラム。
【請求項１５】
前記置換可能性判定部は、前記第１命令が、メモリから第１データを読み出す命令であり、かつ前記第２命令が、メモリから前記第１データとは異なるアドレスに格納された前記第２データを読み出す命令であり、かつ前記第１データ及び前記第２データを１命令で読み出すことができる場合に、前記第１命令及び前記第２命令を、前記共通処理命令群に置換可能と判定し、
前記共通処理命令群生成部は、前記共通処理命令群として、メモリから前記第１データ及び前記第２データを１命令で読み出す前記共通処理命令と、当該共通処理命令により読み出されたデータから前記第１データを抽出する第１抽出命令と、当該共通処理命令により読み出されたデータから前記第２データを抽出する第２抽出命令とを前記第１命令列中に生成する請求項１３記載のコンパイラプログラム。
【請求項１６】
請求項１３から１５の何れかに記載のコンパイラプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体に関する。特に本発明は、命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体に関する。
【０００２】
【従来の技術】
従来のコンパイラにおいて、命令の実行回数を減少させる技術として部分冗長性の除去技術が用いられている（非特許文献１参照。）。この技術によると、例えば、制御フローの合流先で実行される命令と、制御フロー合流元の一方で実行される命令が冗長である場合に、合流先の命令を合流元の他方に移動することにより、命令の実行回数を減少させることができる。
【０００３】
【非特許文献１】
Ｊ．Ｋｎｏｏｐ、Ｏ．Ｒｕｔｈｉｎｇ  ａｎｄ  Ｂ．Ｓｔｅｆｆｅｎ、Ｌａｚｙ  ｃｏｄｅ  ｍｏｔｉｏｎ、Ｉｎ  ＰＬＤＩ‘９２、ｐ．２２４−２３４、１９９２．邦題「Ｌａｚｙコード移動」
【０００４】
【発明が解決しようとする課題】
しかし、上記技術によると、各命令の実行回数を減少させることができる一方、複数の命令による処理を合成して効率的に実行する合成命令を生成するべく、命令を他の基本ブロックに移動させることはできない。例えば、６４ビットアーキテクチャのコンピュータにおいて、互いに隣接したアドレスから３２ビットのデータを読み出す２つのロード命令のそれぞれが、２つの基本ブロックのそれぞれで実行される場合に、当該２つの３２ビットのロード命令を合成して６４ビットのロード命令とするべく、１つの３２ビットのロード命令を他の基本ブロックに移動させる最適化を行うことはできなかった。
そこで本発明は、上記の課題を解決することのできるコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【０００５】
【課題を解決するための手段】
即ち、本発明の第１の形態によると、命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置であって、第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、第１命令及び第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定部と、置換可能性判定部により置換可能と判定された場合に、第１命令に代えて共通処理命令群を第１命令列中に生成する共通処理命令群生成部と、第１命令列以外の命令列であって、当該命令列の次に第２命令列が実行される第３命令列に、第２命令を挿入する命令挿入部とを備えるコンパイラ装置、コンパイラ装置によるコンパイル方法、コンパイラ装置としてコンピュータを機能させるコンパイラプログラム、及びコンパイラプログラムを記録した記録媒体を提供する。
なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションも又発明となりうる。
【０００６】
【発明の実施の形態】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、又実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、コンパイラ装置１０の機能ブロック図を示す。コンパイラ装置１０は、命令の実行順序を変更することによりプログラムを最適化することを目的としており、命令グループ生成部１００と、移動可能範囲解析部１１０と、置換可能性判定部１２０と、共通処理命令群生成部１３０と、命令挿入部１４０とを備える。
【０００７】
命令グループ生成部１００は、共通処理命令群に置換可能な命令の候補を示す命令グループ情報を生成する。一例としては、命令グループ生成部１００は、メモリから３２ビットの第１データを読み出す３２ビットロード命令と、当該第１データに隣接した第２データを読み出す３２ビットロード命令とが、共通処理命令群である６４ビットロード命令に置換可能であることを示す命令グループ情報を生成する。また、命令グループ生成部１００は、コンパイル対象のプログラムを受け取ると、移動可能範囲解析部１１０に送る。
なお、第１データ及び第２データが隣接した状態とは、第１データ及び第２データがメモリ上の連続した領域に格納されている状態である。そして、この場合、第１データ及び第２データは、レジスタへの読み出し単位であるワード又はダブルワード境界を跨がない、即ちメモリの０番地から順次ワード又はダブルワード単位で区分した領域内であることが望ましい。一例としては、ワード単位とは、６４ビットである。
【０００８】
移動可能範囲解析部１１０は、コンパイル対象のプログラムを受け取ると、当該プログラムの各命令について、プログラムの実行結果が同一で、かつ当該命令の実行回数を増やすことなく当該命令を移動することができる命令の移動範囲を解析し、受け取ったプログラムと共に解析結果を置換可能性判定部１２０に送る。例えば、移動可能範囲解析部１１０は、非特許文献１に記述されているビジーコードモーション（Ｂｕｓｙ  Ｃｏｄｅ  Ｍｏｔｉｏｎ）の処理を行うことにより、命令の移動範囲を解析してもよい。
より詳細には、例えば、部分冗長性の除去技術は、命令をより先に実行させる箇所に移動することにより、当該命令を、移動先に既に存在していた命令と冗長であるとして除去する。この除去技術を適切に適用するべく、移動可能範囲解析部１１０は、プログラム中の各命令について、当該命令を移動することによって、当該命令と同一の処理を行う命令は冗長であるとして除去できる移動範囲を解析する。
【０００９】
置換可能性判定部１２０は、第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、第１命令及び第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する。そして、置換可能性判定部１２０は、プログラムを判断結果と共に移動可能範囲解析部１１０に送る。
【００１０】
より詳細には、第１命令及び第２命令が、共通処理命令群に置換可能な命令の候補であると命令グループ生成部１００により判定され、かつ第１命令が、移動可能範囲解析部１１０により解析された第２命令の移動範囲にある場合に、置換可能性判定部１２０は、第１命令及び第２命令を共通処理命令群に置換可能と判断する。
例えば、置換可能性判定部１２０は、共通処理命令群の命令数が、第１命令及び第２命令を別個に実行した場合の命令数より少ない場合、一例としては、第１データ及び第２データを１命令で読み出すことができる場合に、第１命令及び第２命令を共通処理命令群に置換可能と判定する。第１データ及び第２データを１命令で読み出すことができる場合とは、第１データ及び第２データがメモリ上で連続してなくとも良く、例えば、同一のワード内にある場合であってよい。
また、これに代えて、置換可能性判定部１２０は、共通処理命令群の実行を開始してから完了するまでに要する実行時間が、第１命令及び第２命令のそれぞれを別個に実行した場合の実行時間より短い場合に、第１命令及び第２命令を共通処理命令群に置換可能と判断してもよい。
【００１１】
ここで、命令列とは、少なくとも１の命令を含む命令の集合であり、例えば、先頭に配列された命令及び最後に配列された命令以外の命令が分岐命令の分岐先又は分岐元とならない命令の集合である基本ブロック（Ｂａｓｉｃ  Ｂｌｏｃｋ）であってもよいし、先頭に配列された命令及び最後に配列された命令以外の命令が分岐命令の分岐先とならないスーパーブロック（Ｓｕｐｅｒ  Ｂｌｏｃｋ）であってもよい。また、命令列とは、制御フローの流入点を含んでもよい。即ち、命令列とは、連続して実行される部分を含む命令の集合である。
また、命令とは、最適化対象のプログラムを表す中間言語における命令であり、一例としては、Ｊａｖａ（登録商標）言語におけるバイトコード、ＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌａｎｇｕａｇｅ）、又は４つ組表現である。これに代えて、命令とは、コンピュータにより実行可能なインストラクション（ｉｎｓｔｒｕｃｔｉｏｎ）であってもよいし、プログラムのソースコードにおける文であってもよい。また、命令とは、単一の処理を行う複数の命令の組であってもよい。
【００１２】
共通処理命令群生成部１３０は、置換可能性判定部１２０により置換可能と判定された場合に、第１命令に代えて共通処理命令群を第１命令列中に生成し、命令挿入部１４０は、第１命令列中の命令列であって、当該命令列の次に第２命令列が実行される第３の命令列に、第２命令を挿入する。
【００１３】
このように、コンパイラ装置１０は、第１命令が、移動可能範囲解析部１１０により解析された第２命令の移動範囲にある場合に、第１命令及び第２命令を、より実行時間の短い共通処理命令群に変換することができる。これにより、第２命令が冗長に実行されない状態を保ちつつ、プログラムの実行時間をより短く最適化できる。
なお、共通処理命令群の命令数が、第１命令及び第２命令を別個に実行した場合の命令数より少ない場合に、置換可能性判定部１２０は、第１命令及び第２命令を共通処理命令群に置換可能と判断してもよい。この場合、コンパイラ装置１０は、コンパイル結果のプログラムのサイズをより小さく最適化できる。
【００１４】
図２は、コンパイラ装置１０のフローチャートを示す。命令グループ生成部１００は、共通処理命令群に置換可能な命令の候補を示す命令グループ情報を生成する（Ｓ２００）。データ構造の一例として、命令グループ生成部１００は、ビットベクトル方式を用いてもよい。例えば、命令グループ生成部１００は、第１データを読み出す３２ビットロード命令をビットベクトルの１ビット目に対応付け、第２データを読み出す３２ビットロード命令をビットベクトルの２ビット目に対応付ける。この場合、命令グループ生成部１００は、６４ビットロード命令をビットベクトル｛１，１｝に対応付けることにより、第１データを読み出す３２ビットロード命令及び第２データを読み出す３２ビットロード命令が同一の命令グループに属することを示すことができる。これにより、命令の集合を操作する計算、例えば、積集合を算出する等の計算を高速化できる。
【００１５】
続いて、移動可能範囲解析部１１０は、当該プログラムの各命令、例えば、第２命令について、プログラムの実行結果が同一で、かつ当該第２命令の実行回数を増やすことなく当該第２命令を移動することができる第２命令の移動範囲を解析する（Ｓ２１０）。そして、置換可能性判定部１２０は、第１命令が、移動可能範囲解析部１１０により解析された第２命令の移動範囲にある場合に、第１命令及び第２命令を共通処理命令群に置換か否かを判定する（Ｓ２２０）。そして、置換可能性判定部１２０により置換可能と判定された場合に、共通処理命令群生成部１３０は、第１命令に代えて共通処理命令群を第１命令列中に生成し、命令挿入部１４０は、第３命令列に第２命令を挿入する（Ｓ２３０）。
【００１６】
図３は、図２におけるＳ２２０のフローチャートを示す。置換可能性判定部１２０は、各基本ブロックに対して以下の処理を行う。置換可能性判定部１２０は、当該基本ブロックｎの最初に移動可能な命令の集合Ｎ−ＣＯＭＰ（ｎ）を生成する（Ｓ３００）。そして、置換可能性判定部１２０は、Ｎ−ＣＯＭＰ（ｎ）に含まれる命令のうち、Ｓ２００において共通処理命令群に置換可能と判定された命令について、当該命令が属する命令グループを選択する。置換可能性判定部１２０は、選択した命令グループに属する全ての命令を、Ｇ−Ｎ−ＣＯＭＰ（ｎ）とする。
【００１７】
同様に、置換可能性判定部１２０は、当該基本ブロックｎの最後に実行可能な命令の集合Ｘ−ＣＯＭＰ（ｎ）を生成する。そして、置換可能性判定部１２０は、Ｘ−ＣＯＭＰ（ｎ）に含まれる命令のうち、Ｓ２００において共通処理命令群に置換可能と判定された命令について、当該命令が属する命令グループを選択する。置換可能性判定部１２０は、選択した命令グループに属する全ての命令を、Ｇ−Ｘ−ＣＯＭＰ（ｎ）とする。更に、置換可能性判定部１２０は、基本ブロックｎを通過して移動させることができる命令の集合であるＴＲＡＮＳＰ（ｎ）を生成する。
【００１８】
置換可能性判定部１２０は、各基本ブロックにおいて、当該基本ブロックｎの最初に挿入する命令の集合であるＮ−ＩＮＳＥＲＴ（ｎ）及び当該基本ブロックｎの最後に実行させるべき命令の集合であるＸ−ＩＮＳＥＲＴ（ｎ）を生成する（Ｓ３１０）。コンパイラ装置１０は、部分冗長性の除去を行う様々な技術により、Ｎ−ＩＮＳＥＲＴ（ｎ）及びＸ−ＩＮＳＥＲＴ（ｎ）を生成してもよい。一例としては、置換可能性判定部１２０は、非特許文献１の図７に開示された処理を、Ｎ−ＣＯＭＰ（ｎ）に代えてＧ−Ｎ−ＣＯＭＰ（ｎ）を用い、Ｘ−ＣＯＭＰ（ｎ）に代えてＧ−Ｘ−ＣＯＭＰ（ｎ）を用いて行う。
【００１９】
ここで、非特許文献１に記載された技術は、命令の冗長性を除去した状態を保ちつつ、各変数に格納される値の生存区間を最小にするべく、各命令をできるだけ後で実行させるように移動する移動先であるＸ−ＩＮＳＥＲＴ（ｎ）及びＮ−ＩＮＳＥＲＴ（ｎ）を解析する技術である。なお、生存区間とは、変数に値が代入されてから、当該値を最後に参照する命令までの範囲を示す。生存区間を伸張させた場合には、最適化の機会を広げ得るものの、同時に保持するべき値の数が増大し、より多くのレジスタを必要としてしまう場合がある。
【００２０】
一方、本実施形態によると、非特許文献１におけるＮ−ＣＯＭＰ（ｎ）に代えてＧ−Ｎ−ＣＯＭＰ（ｎ）を用い、Ｘ−ＣＯＭＰ（ｎ）に代えてＧ−Ｘ−ＣＯＭＰ（ｎ）を用いることにより、置換可能性判定部１２０は、命令が共通処理命令群に置換可能な場合には、命令グループに属する他の命令が存在する基本ブロックで実行させる移動先を解析し、命令が共通処理命令群に置換可能でない場合には、できるだけ後で実行させる移動先を解析し、解析結果をＸ−ＩＮＳＥＲＴ（ｎ）及びＮ−ＩＮＳＥＲＴ（ｎ）として生成する。
【００２１】
置換可能性判定部１２０は、更に、Ｎ−ＩＮＳＥＲＴ（ｎ）及びＸ−ＩＮＳＥＲＴ（ｎ）に基づいて、基本ブロックｎの最後に挿入する命令の集合Ｘ−ＯＰＴ（ｎ）を生成する（Ｓ３２０）。例えば、置換可能性判定部１２０は、次の式によりＸ−ＯＰＴ（ｎ）を生成する。
Ｘ−ＯＰＴ（ｎ）＝（Ｎ−ＩＮＳＥＲＴ（ｎ）∩ＴＲＡＮＳＰ（ｎ））∪Ｘ−ＩＮＳＥＲＴ（ｎ）
【００２２】
また、置換可能性判定部１２０は、Ｘ−ＯＰＴ（ｎ）に含まれる命令を基本ブロックｎに挿入した結果、冗長となり除去され得る命令の集合を示すＮ−ＲＥＡＣＨ（ｎ）及びＸ−ＲＥＡＣＨ（ｎ）を生成する。例えば、置換可能性判定部１２０は、Ｎ−ＲＥＡＣＨ（ｎ）を、基本ブロックｎの直前で実行されるべき全ての基本ブロックにおける、Ｘ−ＲＥＡＣＨの積集合として算出する。そして、置換可能性判定部１２０は、次の式によりＸ−ＲＥＡＣＨ（ｎ）を生成する。
Ｘ−ＲＥＡＣＨ（ｎ）＝（Ｎ−ＲＥＡＣＨ（ｎ）∩ＴＲＡＮＳＰ（ｎ））∪Ｘ−ＯＰＴ（ｎ）
【００２３】
なお、置換可能性判定部１２０が第１命令及び第２命令を共通処理命令群に置換可能と判定する方法は、本図に示した方法に限定されない。例えば、置換可能性判定部１２０は、第１命令及び第２命令のそれぞれを移動することができるプログラム中の範囲を、プログラムの最適化を行うための他の解析方法により決定してもよい。即ち、置換可能性判定部１２０は、プログラムの実行結果が同一であることを保証しつつ第２命令を移動できる範囲が、プログラムの実行結果が同一であることを保証しつつ第１命令を移動できる範囲と重なる場合に、第１命令及び第２命令を共通処理命令群に置換可能であると判定する。
【００２４】
図４は、図２におけるＳ２３０のフローチャートを示す。コンパイラ装置１０は、図４及び図５に示すフローチャートに示した処理により基本ブロック内の最適化を行い、図６及び図７に示した処理により、命令を他の基本ブロックに移動させる基本ブロック間の最適化を行う。
【００２５】
共通処理命令群生成部１３０は、最適化される命令の候補の集合ｉｎｎｅｒに、Ｎ−ＲＥＡＣＨ（ｎ）を代入する（Ｓ４００）。そして、共通処理命令群生成部１３０は、変数Ｉに、ブロックｎの最初の命令を代入する（Ｓ４１０）。続いて、共通処理命令群生成部１３０は、Ｉの右辺式をＲとする（Ｓ４２０）。そして、共通処理命令群生成部１３０は、Ｒによって移動が妨げられる命令をｉｎｎｅｒから除く（Ｓ４３０）。続いて、共通処理命令群生成部１３０及び命令挿入部１４０は、命令の移動処理を行う（Ｓ４４０）。
【００２６】
続いて、共通処理命令群生成部１３０は、Ｉの変数定義によって移動が妨げられる命令をｉｎｎｅｒから除く（Ｓ４５０）。共通処理命令群生成部１３０は、Ｉがブロックｎの最後の命令でない場合に（Ｓ４６０：ＮＯ）、Ｉを、ブロックｎにおけるＩの次の命令とし（Ｓ４７０）、Ｓ４２０に処理を移す。Ｉがブロックｎの最後の命令である場合に（Ｓ４６０：ＹＥＳ）、共通処理命令群生成部１３０は、図６の処理に移る。
【００２７】
図５は、図４におけるＳ４４０のフローチャートを示す。命令Ｒがｉｎｎｅｒに含まれる場合に（Ｓ５００：ＹＥＳ）、命令挿入部１４０は、最適化対象のブロック内における命令Ｉ以前に、Ｒと同一の命令である命令Ｖがあり、かつ命令Ｖの結果が命令Ｖ及び命令Ｒの間で変わらないことが保証できる場合に、命令Ｖの結果をテンポラリ変数Ｔ［Ｒ］に代入する（Ｓ５１０）。そして、命令挿入部１４０は、命令Ｒを変数Ｔ［Ｒ］で置き換え（Ｓ５２０）、ｉｎｎｅｒに命令Ｒを追加し（Ｓ５２５）、処理を終了する。
【００２８】
一方、共通処理命令群生成部１３０は、命令Ｒがｉｎｎｅｒに含まれない場合に（Ｓ５００：ＮＯ）、ｇをＲが属するグループとする（Ｓ５３０）。共通処理命令群生成部１３０は、ｇに含まれる命令Ｑがブロックｎ内のＩ以前にあり、かつＲが命令Ｑの位置に移動可能である場合に（Ｓ５４０：ＹＥＳ）、命令Ｑに代えて、命令Ｐ及び命令Ｒによる処理の少なくとも一部ずつをあわせて処理する共通処理命令である命令Ｃ１を生成する（Ｓ５５０）。
【００２９】
続いて、共通処理命令群生成部１３０は、命令Ｃ１の結果をテンポラリ変数Ｔ［Ｒ］及びテンポラリ変数Ｔ［Ｑ］に代入する命令を、Ｃ１の後に生成する（Ｓ５６０）。ここで、Ｒ及びＱは、命令Ｒ及び命令Ｑに対応付けられ、プログラム中で固有の番号を示す。即ち、コンパイラ装置１０は、プログラムの各命令を最適化するために、プログラム中の各命令の処理結果を一時的に格納する配列変数Ｔの領域を予め確保している。コンパイラ装置１０は、配列変数Ｔに、命令毎に固有の添え字を付してアクセスすることにより、配列変数を、各命令に対応付けられたテンポラリ変数として用いることができる。
【００３０】
また、命令Ｃ１の結果をテンポラリ変数Ｔ［Ｒ］及びテンポラリ変数Ｔ［Ｑ］に代入する命令が、符号拡張機能を有する場合に、共通処理命令群生成部１３０は、当該命令の後に、更に、符号拡張命令を生成してもよい。同様に、命令Ｃ１の結果をテンポラリ変数Ｔ［Ｒ］及びテンポラリ変数Ｔ［Ｑ］に代入する命令が、ゼロ拡張機能を有する場合に、共通処理命令群生成部１３０は、当該命令の後に、更に、ゼロ拡張命令を生成してもよい。これにより、符号拡張又はゼロ拡張が行われることを明示的に示すことができるので、従来の最適化処理機能をそのまま適用することにより、冗長な符号拡張命令又はゼロ拡張命令を除去することができる。続いて、共通処理命令群生成部１３０は、ｉｎｎｅｒに命令Ｑを追加し（Ｓ５７０）、Ｓ５２０に処理を移す。
【００３１】
一方、共通処理命令群生成部１３０は、ｇに含まれる命令Ｑがブロックｎ内のＩ以前にない又はＲが命令Ｑの位置に移動可能でない場合に（Ｓ５４０：ＮＯ）、Ｓ５２５に処理を移す。
【００３２】
図６は、図２におけるＳ２３０のうち、図４に続く部分のフローチャートを示す。共通処理命令群生成部１３０は、命令の集合を示す変数ｏｐｔを、Ｘ＿ＯＰＴ（ｎ）とする（Ｓ６００）。ｏｐｔが空集合である場合に（Ｓ６１０：ＹＥＳ）、コンパイラ装置１０は処理を終了する。ｏｐｔが空集合でない場合に（Ｓ６１０：ＮＯ）、共通処理命令群生成部１３０は、ｏｐｔに含まれる命令ｅを１つ選択し（Ｓ６２０）、ｏｐｔから命令ｅを取り除く（Ｓ６３０）。続いて、共通処理命令群生成部１３０は、ｅ＿ｇを、命令ｅが属するグループの全ての命令と、Ｘ＿ＯＰＴ（ｎ）に属している命令との積集合とする（Ｓ６４０）。
【００３３】
共通処理命令群生成部１３０は、ｅ＿ｇ内の命令が合成可能かつｅ＿ｇ内の命令でｉｎｎｅｒに含まれていないものがある場合に（Ｓ６５０：ＹＥＳ）、共通処理命令群を生成する処理を行い（Ｓ６６０）、Ｓ６１０に処理を移す。
【００３４】
一方、命令挿入部１４０は、ｅ＿ｇ内の命令が合成可能でない又はｅ＿ｇ内の命令でｉｎｎｅｒに含まれていないものがない場合に（Ｓ６５０：ＮＯ）、命令ｅがｉｎｎｅｒに含まれるか否かを判断する（Ｓ６７０）。命令ｅがｉｎｎｅｒに含まれない場合に（Ｓ６７０：ＮＯ）、命令挿入部１４０は、命令ｅの結果を変数Ｔ［ｅ］に代入する命令を、基本ブロックｎの最後に実行される箇所に生成する（Ｓ６８０）。一方、命令ｅがｉｎｎｅｒに含まれる場合に（Ｓ６７０：ＹＥＳ）、命令挿入部１４０は、命令移動の最適化を行う以前の基本ブロックｎ内に、基本ブロックｎの最後に実行可能な命令ｅが存在するか否かを判断する（Ｓ６９０）。基本ブロックｎの最後に実行可能な命令ｅが存在しない場合に（Ｓ６９０：ＮＯ）、命令挿入部１４０は、Ｓ６１０に処理を戻す。基本ブロックｎの最後に実行可能な命令ｅが存在する場合に（Ｓ６９０：ＹＥＳ）、命令挿入部１４０は、命令ｅの結果を変数Ｔ［ｅ］に代入する命令を、命令ｅと同一の処理を行う命令のうち、最後に実行される命令の位置に生成する（Ｓ６９５）。
【００３５】
図７は、図６におけるＳ６６０のフローチャートを示す。共通処理命令群生成部１３０は、基本ブロックｎ内の最後に実行される個所に移動可能な、ｅ＿ｇ内の命令Ｓが存在する場合に（Ｓ７００：ＹＥＳ）、ｅ＿ｇに含まれる命令を合成した共通処理命令群である命令Ｃ２を命令Ｓに代えて生成する（Ｓ７１０）。一方、基本ブロックｎ内の最後に実行される個所に移動可能な、ｅ＿ｇ内の命令Ｓが存在しない場合に（Ｓ７００：ＮＯ）、共通処理命令群生成部１３０は、基本ブロックｎの最後に実行される個所に命令Ｃ２を生成する（Ｓ７２０）。
【００３６】
続いて、共通処理命令群生成部１３０は、ｅ＿ｇに含まれる命令のそれぞれの左辺の変数にＣ２の結果を代入する命令を、Ｃ２の後に生成する（Ｓ７３０）。ここで、ｅ＿ｇに含まれる命令のそれぞれの左辺の変数にＣ２の結果を代入する命令が、符号拡張機能を有する場合に、共通処理命令群生成部１３０は、当該命令の後に、更に、符号拡張命令を生成してもよい。同様に、ｅ＿ｇに含まれる命令のそれぞれの左辺の変数にＣ２の結果を代入する命令が、ゼロ拡張機能を有する場合に、共通処理命令群生成部１３０は、当該命令の後に、更に、ゼロ拡張命令を生成してもよい。これにより、符号拡張又はゼロ拡張が行われることを明示的に示すことができるので、従来の最適化処理機能をそのまま適用することにより、冗長な符号拡張命令又はゼロ拡張命令を除去することができる。そして、共通処理命令群生成部１３０は、ｉｎｎｅｒに、ｅ＿ｇに含まれる全ての命令を追加し（Ｓ７４０）、ｅ＿ｇに含まれる全ての命令をｏｐｔから除外する（Ｓ７５０）。
【００３７】
このように、共通処理命令群生成部１３０は、Ｘ−ＩＮＳＥＲＴ（ｎ）及びＮ−ＩＮＳＥＲＴ（ｎ）を合成したＸ−ＯＰＴ（ｎ）に基づき、Ｘ−ＯＰＴ（ｎ）に含まれる命令を基本ブロックｎに挿入する。即ち、置換可能性判定部１２０により第２命令が置換可能と判定された場合には、共通処理命令群生成部１３０は、第１命令に代えて共通処理命令群を第１命令列中に生成し、置換可能性判定部１２０により置換可能と判定されなかった場合に、命令挿入部１４０は、第２命令を、移動可能範囲解析部１１０により解析された範囲のうち、第２命令により生成される値の生存区間が最小となる箇所に移動する。
【００３８】
図８は、コンパイル対象のプログラムの一例を示す。コンパイル対象のプログラムは、１行目から３行目までの命令を含み第１命令列の一例である基本ブロック８００と、４行目から６行目までの命令を含み第２命令列の一例である基本ブロック８１０と、第３命令列の一例である基本ブロック８２０とを有する。
【００３９】
１行目の命令は、変数ａに１２を加えた値をレジスタＥＡに格納する命令である。２行目の命令は、レジスタＥＡが示すメモリ上のアドレスから３２ビットの第１データを読み出し変数ｔ１に格納する命令である。３行目の命令は、変数ｔ１に格納された値を符号拡張する命令である。
【００４０】
４行目の命令は、変数ａに８を加えた値をレジスタＥＡに格納する命令である。２行目の命令は、レジスタＥＡが示すメモリ上のアドレスから３２ビットの第２データを読み出し変数ｔ２に格納する命令である。３行目の命令は、変数ｔ２に格納された値を符号拡張する命令である。
【００４１】
このように、本図に示したプログラムによると、２行目の命令及び５行目の命令により読み出されるアドレスが隣接しており、第１データ及び第２データの双方を共通処理命令である６４ビットの読み出し命令により１命令で読み出し可能であるにも関わらず、２行目及び５行目の命令が同一の基本ブロックにないので、共通処理命令とすることができない。
【００４２】
図９は、コンパイル対象のプログラムに、Ｓ３００の処理を適用した結果の一例を示す。コンパイラ装置１０は、本図に示すように、命令の集合をビットベクトル型のデータとして生成する。この際、コンパイラ装置１０は、命令「ｌｏａｄ３２（ａ＋８）」が存在する旨を、ビットベクトルの１ビット目（ｂｉｔ０）を１とすることにより示す。また、コンパイラ装置１０は、命令「ｌｏａｄ３２（ａ＋１２）」が存在する旨を、ビットベクトルの２ビット目（ｂｉｔ１）を１とすることにより示す。
【００４３】
例えば、基本ブロック８００におけるＮ−ＣＯＭＰは、命令「ｌｏａｄ３２（ａ＋１２）」であるので、置換可能性判定部１２０は、基本ブロック８００におけるＮ−ＣＯＭＰを、ビットベクトル型のデータ構造である｛０，１｝として生成する。同様に、置換可能性判定部１２０は、基本ブロック８００におけるＸ−ＣＯＭＰを｛０，１｝として生成し、基本ブロック８１０におけるＮ−ＣＯＭＰを｛１，０｝として生成し、基本ブロック８１０におけるＸ−ＣＯＭＰを｛１，０｝として生成する。
【００４４】
また、置換可能性判定部１２０は、Ｎ−ＣＯＭＰ（ｎ）に含まれる命令のうち共通処理命令群に置換可能と判定された命令について、当該命令が属する命令グループに属する全ての命令を、Ｇ−Ｎ−ＣＯＭＰ（ｎ）とする。従って、置換可能性判定部１２０は、命令「ｌｏａｄ３２（ａ＋８）」及び命令「ｌｏａｄ３２（ａ＋１２）」が共通処理命令群に置換可能と判定するので、Ｇ−Ｎ−ＣＯＭＰ（ｎ）を、ビットベクトル型のデータ構造である｛１，１｝として生成する。同様に、置換可能性判定部１２０は、基本ブロック８００におけるＧ−Ｘ−ＣＯＭＰを｛１，１｝として生成し、基本ブロック８１０におけるＧ−Ｎ−ＣＯＭＰを｛１，１｝として生成し、基本ブロック８１０におけるＧ−Ｘ−ＣＯＭＰを｛１，１｝として生成する。
【００４５】
図１０は、図９に示したデータに、更にＳ３２０の処理を適用した結果の一例を示す。共通処理命令群生成部１３０は、基本ブロック８００におけるＸ−ＯＰＴとして、命令「ｌｏａｄ３２（ａ＋８）」及び命令「ｌｏａｄ３２（ａ＋１２）」が含まれることを示す｛１，１｝を生成する。更に、共通処理命令群生成部１３０は、基本ブロック８１０におけるＮ−ＲＥＡＣＨとして、「ｌｏａｄ３２（ａ＋８）」が含まれることを示す｛１，０｝を生成する。即ち、本図の結果は、命令「ｌｏａｄ３２（ａ＋８）」及び命令「ｌｏａｄ３２（ａ＋１２）」を基本ブロック８００に移動し、基本ブロック８１０にある「ｌｏａｄ３２（ａ＋１２）」を除去する旨を示している。
【００４６】
図１１は、コンパイル対象のプログラムに、図１０に示した結果を用いてＳ２３０の処理を適用した結果の一例を示す。本プログラムは、１行目から６行目の命令を含む基本ブロック８００と、７行目から９行目の命令を含む基本ブロック８１０と、１０行目から１１行目の命令を含む基本ブロック８２０とを有する。本図で示すように、共通処理命令群生成部１３０は、図８の１行目から２行目の命令に代えて、本図の１行目から３行目の命令及び５行目の命令が示す共通処理命令群を基本ブロック８００に生成する。そして、命令挿入部１４０は、図８の４行目及び５行目の命令を、基本ブロック８２０に挿入する。これにより、基本ブロック８００から基本ブロック８１０に至る経路が実行された場合には、３２ビットロード命令が２回実行されるのに代えて、６４ビットロード命令が１回実行されることなり、効率的である。
【００４７】
図１２は、コンパイル対象のプログラムを最適化した結果の一例を示す。本プログラムは、１行目から４行目の命令を含む基本ブロック８００と、基本ブロック８１０と、５行目から７行目の命令を含む基本ブロック８２０とを有する。より詳しくは、図１２は、図１１に示したプログラムに、更に、部分冗長性の除去処理、複写伝播処理、不用代入文除去、及び符号拡張命令除去処理等の一般的な最適化を実行した例を示す。このように、従来の最適化処理をそのまま実行した場合であっても、図１１の６行目に符号拡張命令が明示的に生成されているので、図１１における９行目の符号拡張命令を適切に除去することができる。この結果、コンパイラ装置１０は、基本ブロック８００において共通処理命令群を生成することにより、基本ブロック８１０から命令を除去することができる。
これにより、特に、本プログラムが動作するコンピュータが、６４ビットアーキテクチャを採用しており、３２ビットデータを扱う処理を行う場合、一例としては、Ｊａｖａ（登録商標）言語で記述されたプログラムを、インテルＩＡ６４アーキテクチャで実行する場合には、コンパイラ装置１０は、プログラムを効率的に動作させることができる。
【００４８】
図１３（ａ）は、第１の変形例におけるコンパイル対象のプログラムの一例を示す。本プログラムは、１行目から２行目の命令を含み第１命令列の一例である基本ブロック１３００と、３行目から４行目の命令を含み第２命令列の一例である基本ブロック１３１０と、第３命令列の一例である基本ブロック１３２０とを有する。１行目から２行目の命令は、第１命令の一例であり、変数ａに１２を加えたアドレスから、浮動小数点型の値をレジスタｆ１に読み出す命令である。また、３行目から４行目の命令は、第２命令の一例であり、変数ａに８を加えたアドレスから、浮動小数点型の値をレジスタｆ２に読み出す命令である。
【００４９】
インテルＩＡ６４アーキテクチャ等のプロセッサは、メモリ上の隣接したアドレスから、２つの浮動小数点レジスタへ、１命令でデータをロードするペアードロード命令を実行することができる。当該命令を生成するべく、１行目から２行目の第１命令が、メモリから第１データを読み出す命令であり、かつ３行目から４行目の第２命令が、メモリから第１データとは異なるアドレスに格納された第２データを読み出す命令である場合に、置換可能性判定部１２０は、第１命令及び第２命令を、共通処理命令群に置換可能と判定する。また、置換可能性判定部１２０は、第１命令及び第２命令による読み出し先のレジスタの一方が奇数番号のレジスタであり、かつ他方が偶数番号のレジスタであることを更に条件として、第１命令及び第２命令を、共通処理命令群に置換可能と判定することが望ましい。
【００５０】
図１３（ｂ）は、第１の変形例におけるコンパイル対象のプログラムを最適化した結果を示す。共通処理命令群生成部１３０は、共通処理命令群として、メモリから第１データ及び第２データのそれぞれを読み出し２つのレジスタのそれぞれに値を格納する共通処理命令を第１命令列中である基本ブロック１３００に生成する。更に、命令挿入部１４０は、図１３（ａ）における３行目から４行目の命令を、第３命令列の一例である基本ブロック１３２０に挿入する。
【００５１】
このように、本例によると、コンパイラ装置１０は、メモリから浮動小数点データを読み出す複数の命令に代えて、浮動小数点型のデータを２つのレジスタに１命令で読み出す浮動小数点データロード命令を生成することができる。
【００５２】
図１４（ａ）は、第２の変形例におけるコンパイル対象のプログラムの一例を示す。本プログラムは、１行目の命令を含み第１命令列の一例である基本ブロック１４００と、２行目の命令を含み第２命令列の一例である基本ブロック１４１０と、第３命令列の一例である基本ブロック１４２０とを有する。１行目の命令は、第１命令の一例であり、レジスタｒ１に１６進数の定数０００１Ａ８００を読み込む命令である。また、２行目の命令は、第２命令の一例であり、レジスタｒ２に１６進数の定数０００１Ａ８１０を読み込む命令である。
【００５３】
例えば、インターナショナル・ビジネス・マシーンズ・コーポレーションのＰｏｗｅｒＮＰ（登録商標）アーキテクチャのコンピュータは、３２ビットの定数データをレジスタに読み込む場合に、それぞれが１６ビットのデータを読み込む２つの命令を実行する。一方、既にレジスタに格納された値に、予め定められた差分より小さいデータを加える処理は、１つの命令により実行できる。実行する命令の数を減らすべく、置換可能性判定部１２０は、第１命令が、複数の命令によりロードされるサイズの第１定数データを第１レジスタに格納する命令の組であり、かつ第２命令が、第１定数データから予め定められた差分以内の第２定数データを第２レジスタに格納する命令の組である場合に、第１命令及び第２命令を共有処理命令群に置換可能と判定する。
【００５４】
図１４（ｂ）は、第２の変形例におけるコンパイル対象のプログラムを最適化した結果を示す。共通処理命令群生成部１３０は、共通処理命令群として、第１定数データを第１レジスタに格納する１行目の命令と、第２定数データの第１定数データに対する差を当該第１レジスタの値に加えた結果を第２レジスタに格納する２行目の命令とを第１命令列である基本ブロック１４００中に生成する。更に、命令挿入部１４０は、図１４（ａ）における２行目の命令を、基本ブロック１４２０に挿入する。
【００５５】
このように、本例によると、コンパイラ装置１０は、予め定められたサイズより長い第２定数データをレジスタに読み込む命令の組に代えて、既に第１定数データが読み込まれたレジスタに、所定値を加える命令を生成することができる。レジスタに所定値を加える命令は、第２定数データをレジスタに読み込む命令より高速に動作するので、コンパイラ装置１０は、プログラムを高速に動作させることができる。
【００５６】
図１５（ａ）は、第３の変形例におけるコンパイル対象のプログラムの一例を示す。本プログラムは、１行目の命令を含み第１命令列の一例である基本ブロック１５００と、２行目の命令を含み第２命令列の一例である基本ブロック１５１０と、第３命令列の一例である基本ブロック１５２０とを有する。１行目の命令は、第１命令の一例であり、変数ａの値を１６ビット右にシフトして変数ｔ１に代入するシフト命令である。また、２行目の命令は、第２命令の一例であり、変数ｔ１の下位１６ビットをマスクして変数ｔ２に代入するマスク命令である。
【００５７】
例えば、インターナショナル・ビジネス・マシーンズ・コーポレーションのＰｏｗｅｒＰＣ（登録商標）アーキテクチャのコンピュータは、レジスタから指定した範囲の桁のデータを抽出するローテートマスク命令を実行できる。当該命令を生成するべく、置換可能性判定部１２０は、第１命令が、レジスタに格納されたデータをシフトするシフト命令であり、かつ第２命令が、データの予め定められた領域のビットを抽出するマスク命令である場合に、第１命令及び第２命令を共有処理命令に置換可能と判定する。
【００５８】
図１５（ｂ）は、第３の変形例におけるコンパイル対象のプログラムを最適化した結果を示す。共通処理命令群生成部１３０は、共通処理命令として、レジスタから指定した範囲の桁のデータを抽出するローテートマスク命令を、本図の２行目に生成する。更に、命令挿入部１４０は、図１５（ａ）における２行目の命令を、基本ブロック１５２０に挿入する。なお、コンパイラ装置１０は、変数ｔ１の値が参照されない場合には、不用代入文削除の技術を用いることにより、１行目の命令をｄｅａｄ  ｓｔｏｒｅとして更に除去してもよい。
【００５９】
このように、本例によると、コンパイラ装置１０は、シフト命令及びマスク命令に代えて、ローテートマスク命令を生成することができる。シフト命令及びマスク命令の実行時間が、ローテートマスク命令より長いので、コンパイラ装置１０は、プログラムを高速に動作させることができる。
なお、本例においては、図８から図１４に示した例とは異なり、共通処理命令に置換される複数の命令間の実行順序に依存関係がある。即ち、置換可能性判定部１２０は、先に実行されるべき先行命令（例えばシフト命令）に続いて、後に実行されるべき後続命令（例えばマスク命令）が実行される場合は、先行命令及び後続命令を共通処理命令群に置換可能と判定するが、後続命令に続いて先行命令が実行される場合には、先行命令及び後続命令を共通処理命令群に置換可能でないと判定する。一例としては、置換可能性判定部１２０は、当該先行命令と実行順序の依存関係があり、かつ実質的な処理を行わない擬似命令が、先行命令の直前に実行される箇所に存在すると仮定して、置換可能性の判定を行う。
【００６０】
図１６は、以上で示した実施形態又は変形例におけるコンパイラ装置１０のハードウェア構成の一例を示す。実施形態又は変形例に係るコンパイラ装置１０は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、グラフィックコントローラ１０７５、及び表示装置１０８０を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００６１】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたコンパイラプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００６２】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ１０４０は、コンパイラ装置１０が使用するコンパイラプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からコンパイラプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。
【００６３】
また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、コンパイラ装置１０の起動時にＣＰＵ１０００が実行するブートプログラムや、コンパイラ装置１０のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からコンパイラプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００６４】
コンパイラ装置１０に提供されるコンパイラプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。コンパイラプログラムは、記録媒体から読み出され、入出力チップ１０７０を介してコンパイラ装置１０にインストールされ、コンパイラ装置１０において実行される。
【００６５】
コンパイラ装置１０にインストールされて実行されるコンパイラプログラムは、命令グループ生成モジュールと、移動可能範囲解析モジュールと、置換可能性判定モジュールと、共通処理命令群生成モジュールと、命令挿入モジュールと、部分冗長除去モジュールとを含む。各モジュールがコンパイラ装置１０に働きかけて行わせる動作は、図１から図１５において説明したコンパイラ装置１０における、対応する部材の動作と同一であるから、説明を省略する。
【００６６】
以上に示したコンパイラプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してコンパイラプログラムをコンパイラ装置１０に提供してもよい。
【００６７】
以上の説明から明らかなように、コンパイラ装置１０は、第１命令が、ビジーコードモーションにより解析された第２命令の移動範囲にある場合に、第１命令及び第２命令を、より実行時間が短い又はより命令数が少ない共通処理命令群に変換することができる。これにより、第２命令が冗長に実行されない状態を保ちつつ、プログラムを最適化できる。更に、コンパイラ装置１０は、上記の処理において、命令又は命令グループの集合をビットベクトル型のデータ構造として生成するので、複数の命令を含む集合を操作する計算を高速に行うことができる。この結果、コンパイラ装置１０は、最適化に要する処理時間を低減できるので、Ｊａｖａ（登録商標）のＪｕｓｔ−Ｉｎ−Ｔｉｍｅコンパイラ等の実行時コンパイラとして動作させることができる。
【００６８】
以上、本発明を実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更または改良を加えることができる。そのような変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００６９】
以上で示した実施形態及び変形例によると、以下の各項目に示すコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体が実現される。
【００７０】
（項目１）  命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置であって、第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、前記第１命令及び前記第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定部と、前記置換可能性判定部により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成する共通処理命令群生成部と、前記第１命令列以外の命令列であって、当該命令列の次に前記第２命令列が実行される第３命令列に、前記第２命令を挿入する命令挿入部とを備えるコンパイラ装置。
（項目２）  前記置換可能性判定部は、前記共通処理命令群の命令数が、前記第１命令及び前記第２命令を別個に実行した場合の命令数より少ない場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定する項目１記載のコンパイラ装置。
【００７１】
（項目３）  前記置換可能性判定部は、前記共通処理命令群の実行を開始してから完了するまでに要する実行時間が、前記第１命令及び前記第２命令のそれぞれを別個に実行した場合の実行時間より短い場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定する項目１記載のコンパイラ装置。
（項目４）  前記置換可能性判定部は、前記第１命令が、メモリから第１データを読み出す命令であり、かつ前記第２命令が、メモリから前記第１データとは異なるアドレスに格納された前記第２データを読み出す命令であり、かつ前記第１データ及び前記第２データを１命令で読み出すことができる場合に、前記第１命令及び前記第２命令を、前記共通処理命令群に置換可能と判定し、前記共通処理命令群生成部は、前記共通処理命令群として、メモリから前記第１データ及び前記第２データを１命令で読み出す前記共通処理命令と、当該共通処理命令により読み出されたデータから前記第１データを抽出する第１抽出命令と、当該共通処理命令により読み出されたデータから前記第２データを抽出する第２抽出命令とを前記第１命令列中に生成する項目１記載のコンパイラ装置。
【００７２】
（項目５）  前記共通処理命令群生成部は、前記共通処理命令群として、前記共通処理命令と、抽出したデータに対して更に符号拡張を行う前記第１抽出命令と、抽出したデータに対して更に符号拡張を行う前記第２抽出命令とを生成と、前記第２抽出命令が抽出したデータを符号拡張する符号拡張命令とを生成することを特徴とする項目４記載のコンパイラ装置。
（項目６）  前記共通処理命令群生成部は、前記共通処理命令群として、前記共通処理命令と、抽出したデータに対して更にゼロ拡張を行う前記第１抽出命令と、抽出したデータに対して更にゼロ拡張を行う前記第２抽出命令とを生成と、前記第２抽出命令が抽出したデータをゼロ拡張するゼロ拡張命令とを生成することを特徴とする項目４記載のコンパイラ装置。
（項目７）  前記置換可能性判定部は、前記第１命令が、メモリから第１データを読み出す命令であり、かつ前記第２命令が、メモリから前記第１データとは異なるアドレスに格納された前記第２データを読み出す命令である場合に、前記第１命令及び前記第２命令を、前記共通処理命令群に置換可能と判定し、前記共通処理命令群生成部は、前記共通処理命令群として、メモリから前記第１データ及び前記第２データのそれぞれを読み出し２つのレジスタのそれぞれに値を格納する前記共通処理命令を前記第１命令列中に生成する項目２記載のコンパイラ装置。
【００７３】
（項目８）  前記置換可能性判定部は、前記第１命令が、複数の命令によりロードされるサイズの第１定数データを第１レジスタに格納する命令の組であり、かつ前記第２命令が、前記第１定数データから予め定められた差分以内の第２定数データを第２レジスタに格納する命令の組である場合に、前記第１命令及び前記第２命令を前記共有処理命令群に置換可能と判定し、前記共通処理命令群生成部は、前記共通処理命令群として、前記第１定数データを前記第１レジスタに格納する命令と、前記第２定数データの前記第１定数データに対する差を当該第１レジスタの値に加えた結果を前記第２レジスタに格納する命令とを前記第１命令列中に生成する項目１記載のコンパイラ装置。
（項目９）  前記置換可能性判定部は、前記第１命令が、レジスタに格納されたデータをシフトするシフト命令であり、かつ前記第２命令が、データの予め定められた領域のビットを抽出するマスク命令である場合に、前記第１命令及び前記第２命令を前記共有処理命令に置換可能と判定し、前記共通処理命令群生成部は、前記共通処理命令として、前記レジスタから指定した範囲の桁のデータを抽出するローテートマスク命令を前記第１命令列中に生成する項目１記載のコンパイラ装置。
（項目１０）  前記置換可能性判定部は、前記プログラムの実行結果が同一であることを保証しつつ前記第２命令を移動できる範囲が、前記プログラムの実行結果が同一であることを保証しつつ前記第１命令を移動できる範囲と重なる場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能であると判定する項目１記載のコンパイラ装置。
【００７４】
（項目１１）  前記プログラムの実行結果が同一で、かつ前記第２命令の実行回数を増やすことなく前記第２命令を移動することができる当該第２命令の移動範囲を解析する移動可能範囲解析部を更に備え、前記置換可能性判定部は、前記第１命令が、前記移動可能範囲解析部により解析された前記移動範囲にある場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定し、前記共通処理命令群生成部は、前記置換可能性判定部により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成し、前記命令挿入部は、前記置換可能性判定部により置換可能と判定されなかった場合に、前記第２命令を、前記移動可能範囲解析部により解析された範囲のうち、前記第２命令により生成される値の生存区間が最小となる箇所に移動する項目１０記載のコンパイラ装置。
（項目１２）  命令の実行順序を変更することによりプログラムを最適化するコンパイル方法であって、第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、前記第１命令及び前記第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定段階と、前記置換可能性判定段階により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成する共通処理命令群生成段階と、前記第１命令列以外の命令列であって、当該命令列の次に前記第２命令列が実行される第３命令列に、前記第２命令を挿入する命令挿入段階とを備えるコンパイル方法。
【００７５】
（項目１３）  命令の実行順序を変更することによりプログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、前記コンピュータを、第１命令列に含まれる第１命令と、第１命令列の次に実行される第２命令列に含まれる第２命令とを、前記第１命令及び前記第２命令による処理の少なくとも一部ずつをあわせて処理する共通処理命令を含む共通処理命令群に置換可能か否かを判定する置換可能性判定部と、前記置換可能性判定部により置換可能と判定された場合に、前記第１命令に代えて前記共通処理命令群を前記第１命令列中に生成する共通処理命令群生成部と、前記第１命令列以外の命令列であって、当該命令列の次に前記第２命令列が実行される第３命令列に、前記第２命令を挿入する命令挿入部として機能させるコンパイラプログラム。
（項目１４）  前記置換可能性判定部は、前記共通処理命令群の実行を開始してから完了するまでに要する実行時間が、前記第１命令及び前記第２命令のそれぞれを別個に実行した場合の実行時間より短い場合に、前記第１命令及び前記第２命令を前記共通処理命令群に置換可能と判定する項目１３記載のコンパイラプログラム。
【００７６】
（項目１５）  前記置換可能性判定部は、前記第１命令が、メモリから第１データを読み出す命令であり、かつ前記第２命令が、メモリから前記第１データとは異なるアドレスに格納された前記第２データを読み出す命令であり、かつ前記第１データ及び前記第２データを１命令で読み出すことができる場合に、前記第１命令及び前記第２命令を、前記共通処理命令群に置換可能と判定し、前記共通処理命令群生成部は、前記共通処理命令群として、メモリから前記第１データ及び前記第２データを１命令で読み出す前記共通処理命令と、当該共通処理命令により読み出されたデータから前記第１データを抽出する第１抽出命令と、当該共通処理命令により読み出されたデータから前記第２データを抽出する第２抽出命令とを前記第１命令列中に生成する項目１３記載のコンパイラプログラム。
（項目１６）  項目１３から１５の何れかに記載のコンパイラプログラムを記録した記録媒体。
【００７７】
【発明の効果】
上記説明から明らかなように、本発明によれば命令の実行順序を変更することによりプログラムを最適化することができる。
【図面の簡単な説明】
【図１】図１は、コンパイラ装置１０の機能ブロック図を示す。
【図２】図２は、コンパイラ装置１０のフローチャートを示す。
【図３】図３は、図２におけるＳ２２０のフローチャートを示す。
【図４】図４は、図２におけるＳ２３０のフローチャートを示す。
【図５】図５は、図４におけるＳ４４０のフローチャートを示す。
【図６】図６は、図２におけるＳ２３０のうち、図４に続く部分のフローチャートを示す。
【図７】図７は、図６におけるＳ６６０のフローチャートを示す。
【図８】図８は、コンパイル対象のプログラムの一例を示す。
【図９】図９は、コンパイル対象のプログラムに、Ｓ３００の処理を適用した結果の一例を示す。
【図１０】図１０は、図９に示したデータに、更にＳ３２０の処理を適用した結果の一例を示す。
【図１１】図１１は、コンパイル対象のプログラムに、図１０に示した結果を用いてＳ２３０の処理を適用した結果の一例を示す。
【図１２】図１２は、コンパイル対象のプログラムを最適化した結果の一例を示す。
【図１３】図１３（ａ）は、第１の変形例におけるコンパイル対象のプログラムの一例を示す。図１３（ｂ）は、第１の変形例におけるコンパイル対象のプログラムを最適化した結果を示す。
【図１４】図１４（ａ）は、第２の変形例におけるコンパイル対象のプログラムの一例を示す。図１４（ｂ）は、第２の変形例におけるコンパイル対象のプログラムを最適化した結果を示す。
【図１５】図１５（ａ）は、第３の変形例におけるコンパイル対象のプログラムの一例を示す。図１５（ｂ）は、第３の変形例におけるコンパイル対象のプログラムを最適化した結果を示す。
【図１６】図１６は、以上で示した実施形態又は変形例におけるコンパイラ装置１０のハードウェア構成の一例を示す。
【符号の説明】
１０  コンパイラ装置
１００  命令グループ生成部
１１０  移動可能範囲解析部
１２０  置換可能性判定部
１３０  共通処理命令群生成部
１４０  命令挿入部
８００  基本ブロック
８１０  基本ブロック
８２０  基本ブロック
１３００  基本ブロック
１３１０  基本ブロック
１３２０  基本ブロック
１４００  基本ブロック
１４１０  基本ブロック
１４２０  基本ブロック
１５００  基本ブロック
１５１０  基本ブロック
１５２０  基本ブロック
【図１】
2004265279.tif 000003
【図２】
2004265279.tif 000004
【図３】
2004265279.tif 000005
【図４】
2004265279.tif 000006
【図５】
2004265279.tif 000007
【図６】
2004265279.tif 000008
【図７】
2004265279.tif 000009
【図８】
2004265279.tif 000010
【図９】
2004265279.tif 000011
【図１０】
2004265279.tif 000012
【図１１】
2004265279.tif 000013
【図１２】
2004265279.tif 000014
【図１３】
2004265279.tif 000015
【図１４】
2004265279.tif 000016
【図１５】
2004265279.tif 000017
【図１６】
2004265279.tif 000018