(57)【特許請求の範囲】
【請求項１】
所定のプログラムまたは当該プログラムを変換して得られる第１のコード列を実行し、実行中に当該プログラムまたは当該第１のコード列の中の特定の箇所から、当該プログラムまたは当該第１のコード列を所定の変換手段で変換して得られる第２のコード列の中の当該特定の箇所に対応する命令へ実行が遷移し、遷移した当該命令とそれに続く命令列を実行する、コンピュータのＣＰＵにて実現される実行手段と、
前記プログラムまたは前記第１のコード列から前記第２のコード列への変換を行う際に、前記特定の箇所の直前で当該プログラムまたは当該第１のコード列の実行に使用していた変数の値を、前記遷移の後に前記命令列が使用する変数にコピーする命令を当該プログラムまたは当該第１のコード列の当該特定の箇所に前記変換手段が挿入し、コピー命令が挿入された当該プログラムまたは当該第１のコード列を当該変換手段が最適化を行いつつ変換して当該命令列を得る、コンピュータのＣＰＵにて実現される前記変換手段とを備え、
前記変換手段は、前記変数に関する最適化を前記特定の箇所にまたがる範囲に対して行う場合には、挿入された前記コピー命令を無視して最適化を行うことを特徴とするデータ処理装置。
【請求項２】
前記変換手段は、前記コピー命令のうち、所定のコピー命令の入力変数に関して、前記プログラムまたは前記第１のコード列の実行において使用する当該入力変数の格納場所と、前記第２のコード列の実行において使用する当該入力変数の格納場所とを一致させるための命令が前記特定の箇所を含むベーシックブロック内で記述されていない場合に、当該所定のコピー命令の入力変数と出力変数とを反対にしたコピー命令を当該ベーシックブロックの最後に挿入し、当該特定の箇所にまたがる範囲に対する前記最適化において当該所定のコピー命令を無視することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
ソースコードをインタープリタで解釈実行し、解釈実行中に当該ソースコードの中の特定の箇所から、同じソースコードをコンパイラでコンパイルして得られる機械語命令列の中の当該特定の箇所に対応する機械語命令へ実行が遷移し、遷移した機械語命令とそれに続く機械語命令列を実行する、コンピュータのＣＰＵにて実現される実行手段と、
前記コンパイラでコンパイルを行う際に、前記特定の箇所の直前で前記ソースコードの解釈実行に使用していた変数の値を、前記遷移の後に前記機械語命令列が使用する変数にコピーする命令を当該ソースコードの当該特定の箇所に当該コンパイラが挿入し、コピー命令が挿入されたソースコードを当該コンパイラが最適化を行いつつコンパイルして当該機械語命令列を得る、コンピュータのＣＰＵにて実現される変換手段とを備え、
前記変換手段は、前記変数に関する最適化を前記特定の箇所にまたがる範囲に対して行う場合には、挿入された前記コピー命令を無視して最適化を行うことを特徴とするデータ処理装置。
【請求項４】
前記変換手段は、前記コピー命令のうち、所定のコピー命令の入力変数に関して、前記ソースコードの解釈実行において使用する当該入力変数の格納場所と、前記機械語命令列の実行において使用する当該入力変数の格納場所とを一致させるための命令が前記特定の箇所を含むベーシックブロック内で記述されていない場合に、当該所定のコピー命令の入力変数と出力変数とを反対にしたコピー命令を当該ベーシックブロックの最後に挿入し、前記特定の箇所にまたがる範囲に対する前記最適化において当該所定のコピー命令を無視することを特徴とする請求項３に記載のデータ処理装置。
【請求項５】
所定のプログラムまたは当該プログラムを変換して得られる第１のコード列を実行し、実行中に当該プログラムまたは当該第１のコード列の中の特定の箇所から、当該プログラムまたは当該第１のコード列を所定の変換手段で変換して得られる第２のコード列の中の当該特定の箇所に対応する命令へ実行が遷移し、遷移した当該命令とそれに続く命令列を実行する実行手段と、
前記プログラムまたは前記第１のコード列から前記第２のコード列への変換を行う際に、前記特定の箇所の直前で当該プログラムまたは当該第１のコード列の実行に使用していた変数の値を、前記遷移の後に前記命令列が使用する変数にコピーする命令を当該プログラムまたは当該第１のコード列の当該特定の箇所に前記変換手段が挿入し、コピー命令が挿入された当該プログラムまたは当該第１のコード列を当該変換手段が最適化を行いつつ変換して当該命令列を得る前記変換手段として、コンピュータのＣＰＵを機能させ、
前記変換手段の機能として、前記変数に関する最適化を前記特定の箇所にまたがる範囲に対して行う場合には、挿入された前記コピー命令を無視して最適化を行う処理を前記コンピュータのＣＰＵに実行させることを特徴とするプログラム。
【請求項６】
前記変換手段の機能として、前記コピー命令のうち、所定のコピー命令の入力変数に関して、前記プログラムまたは前記第１のコード列の実行において使用する当該入力変数の格納場所と、前記第２のコード列の実行において使用する当該入力変数の格納場所とを一致させるための命令が前記特定の箇所を含むベーシックブロック内で記述されていない場合に、当該所定のコピー命令の入力変数と出力変数とを反対にしたコピー命令を当該ベーシックブロックの最後に挿入し、前記特定の箇所にまたがる範囲に対する前記最適化において当該所定のコピー命令を無視する処理を前記コンピュータのＣＰＵに実行させることを特徴とする請求項５に記載のプログラム。
【請求項７】
ソースコードをインタープリタで解釈実行し、解釈実行中に当該ソースコードの中の特定の箇所から、同じソースコードをコンパイラでコンパイルして得られる機械語命令列の中の当該特定の箇所に対応する機械語命令へ実行が遷移し、遷移した機械語命令とそれに続く機械語命令列を実行する実行手段と、
前記コンパイラでコンパイルを行う際に、前記特定の箇所の直前で前記ソースコードの解釈実行に使用していた変数の値を、前記遷移の後に前記機械語命令列が使用する変数にコピーする命令を当該ソースコードの当該特定の箇所に当該コンパイラが挿入し、コピー命令が挿入されたソースコードを当該コンパイラが最適化を行いつつコンパイルして当該機械語命令列を得る変換手段として、コンピュータのＣＰＵを機能させ、
前記変換手段の機能として、前記変数に関する最適化を前記特定の箇所にまたがる範囲に対して行う場合には、挿入された前記コピー命令を無視して最適化を行う処理を前記コンピュータのＣＰＵに実行させることを特徴とするプログラム。
【請求項８】
前記変換手段の機能として、前記コピー命令のうち、所定のコピー命令の入力変数に関して、前記ソースコードの解釈実行において使用する当該入力変数の格納場所と、前記機械語命令列の実行において使用する当該入力変数の格納場所とを一致させるための命令が前記特定の箇所を含むベーシックブロック内で記述されていない場合に、当該所定のコピー命令の入力変数と出力変数とを反対にしたコピー命令を当該ベーシックブロックの最後に挿入し、前記特定の箇所にまたがる範囲に対する前記最適化において当該所定のコピー命令を無視する処理を前記コンピュータのＣＰＵに実行させることを特徴とする請求項７に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラムのコンパイル技術に関し、特にプログラムの実行対象が実行環境の異なるコード列間で遷移する場合のプログラムの変形（最適化）の効果を向上させるプログラム変換方法に関する。
【０００２】
【従来の技術】
Ｊａｖａなどのように、インタプリタとダイナミックコンパイラとを組み合わせて動作させる実行環境では、コンパイルの単位であるメソッドの途中で、プログラムの実行対象が、当該インタプリタを介して実行されるコード列からコンパイルされたコード列へ遷移する場合がある。例えば、ループ処理の最中に当該ループ処理にかかるメソッドをコンパイルして、当該コンパイルされたコード列による実行へ遷移（ループ遷移）する場合などである。この場合、インタプリタを介して実行される部分からコンパイルされたコード列で実行される部分へ移行する箇所（インタプリタからの飛び込み口）において、ローカル変数のイメージを合わせる操作が必要となる。
【０００３】
米国インテル社の６４ビットＣＰＵのアーキテクチャであるＩＡ−６４に対応したＪＩＴコンパイラでは、インタプリタを介して実行されるコード列とコンパイルされたコード列とのローカル変数のイメージを合わせるために、「変数の型」の概念が実装上必要である。このため、インタプリタからの飛び込み口のベーシックブロック（以下、Xfer BBと記す）内に明示的に型を持つ、すなわち「変数の定義」を伴うコピー命令を生成し、挿入することが必要となった。
図７は、インタプリタからの飛び込み口におけるコード列の構成を例示する図である。
図７に示す例では、インタプリタを介して実行されるコード列におけるXfer BBには、インタプリタを介して実行されるコード列とコンパイルされたコード列とのローカル変数のイメージを合わせるための明示的な命令「L2 = IMEMLOAD」、「L2 = extend L2」、「L3 = IMEMLOAD」、「L3 = extend L3」、「L4 = AMEMLOAD」、「L5 = AMEMLOAD」、が挿入されている。
【０００４】
【発明が解決しようとする課題】
しかし、インタプリタを介して実行されるコード列とコンパイルされたコード列とのローカル変数のイメージを合わせるためにインタプリタからの飛び込み口に挿入される、明示的な「変数の定義」は、多くの最適化、例えば、前方データフロー解析（forward dataflow analysis）やUD(Use-Definition)-chainを使ったプログラムの変形（最適化）の障害となっていた。
また、変数の型の求め方としては、Xfer BBの終わりの点でＬｉｖｅな変数の型を後方データフロー解析で求める方法が採られている。この場合、必ずしもインタプリタを介して実行されるコード列上の全てのローカル変数について「変数の型」を得ることができるわけではない。これが問題をさらに複雑にしている。
図７に示した例では、インタプリタを介して実行されるコード列とコンパイルされたコード列との合流点（以下、単に合流点と称す）以前のコンパイルされたコード列のベーシックブロックにおけるコピー命令「L2 = L1」、「L3 = 1」、「L4 = L5」（Ｌはローカル変数、すなわち「L2 = L1」はローカル変数Ｌ１の値をローカル変数Ｌ２にコピーすることを意味する）の結果は、プログラムの最適化において、後続のベーシックブロックにおける「・・・ = L2」、「・・・ = L4」、「CMP-eq L3,0」等に伝播させ得る。
【０００５】
しかしながら、インタプリタを介して実行されるコード列のXfer BBに、当該ローカル変数Ｌ２、Ｌ３、Ｌ４、Ｌ５のイメージを合わせるための命令が記述されているため、前方データフロー解析などでは上記の各コピー命令を伝播させることができない。
ここで、前方データフロー解析などの最適化が、合流点を越えられない理由は、インタプリタを介して実行されるコード列のXfer BBに当該ローカル変数のイメージを合わせるための命令が明示的に記述されていると、かかる最適化において、ローカル変数の値が確定していないと認識されるためである。例えば、コンパイルされたコード列においてローカル変数Ｌ３には値１がコピーされているが、Xfer BBに「L3 = IMEMLOAD」、「L3 = extend L3」という命令が存在するために、ローカル変数Ｌ３の値を１に確定できない。
【０００６】
ところが、インタプリタを介して実行されるコード列とコンパイルされたコード列とは元々同一のプログラムであるので、初期値が同じならば、合流点においても各ローカル変数の値はインタプリタを介して実行されるコード列とコンパイルされたコード列とで同一のはずである。したがって、インタプリタを介して実行されるコード列のＸｆｅｒ  ＢＢに挿入されたローカル変数のイメージを合わせるための明示的な命令により前方データフロー解析やＵＤ−ｃｈａｉｎなどを用いた最適化が止まることは、最適化の効果を不当に抑制することとなっていた。
なお、ここではＩＡ−６４を例として説明したが、同様のことは、３２ビット以外の種々のＣＰＵにおけるアーキテクチャに対しても言える。
【０００７】
そこで、本発明は、インタプリタを介して実行されるコード列とコンパイルされたコード列とのローカル変数のイメージを合わせるための明示的な命令の影響を低減させて最適化を行い、プログラムの実行効率の向上を図ることを目的とする。
【０００８】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、次のようなプログラム変換方法として実現される。すなわち、このプログラム変換方法は、プログラムの実行対象が実行環境の異なる２つのコード列間で遷移する場合に、遷移後のコード列におけるプログラムの変形に影響を及ぼす遷移前のコードのうち、このプログラムの変形において考慮しないコードを設定する第１のステップと、設定された考慮しないコードを考慮せずに遷移後のコード列に対してプログラムの変形を行う第２のステップとを含むことを特徴とする。
より具体的には、このプログラム変換方法は、プログラムの実行対象がインタプリタを介して実行される第１のコード列からコンパイルされた第２のコード列へ遷移する場合に、この第２のコード列の変形に影響を及ぼす第１のコード列中のコードのうち、第２のコード列に対する所定の変形において無視できるコードを設定する第１のステップと、設定された無視できるコードを無視して第２のコード列に対し前記所定の変形を行う第２のステップとを含むことを特徴とする。
【０００９】
ここで、より好ましくは、コード列間の遷移を行うために生成され遷移前のコード列に挿入された命令コード、具体的には、例えば遷移前の第１のコード列と遷移後の第２のコード列とにおける変数のイメージを合わせる命令コードを、プログラムの変形において無視できる（考慮しない）コードとして設定する。
また、より詳細には、上述した第２のステップは、第２のコード列に対する所定の変形において無視できるコードに含まれる変数を参酌して、このコードごとに、第１のコード列と第２のコード列との合流点を越えてコピー命令を伝播させることができるかどうかを判断するステップと、判断結果に基づいてコピー命令の伝播を含む第２のコード列の変形を行うステップとを含む。
あるいは、このプログラム変換方法は、第２のコード列の変形に先立って、コピー命令の伝播を含む第２のコード列の変形を行うために必要な補償コードを生成し第１のコード列に挿入する第３のステップをさらに含み、第２のステップでは、無視できるコードを無視して第２のコード列に対し前記コピー命令の伝播を含む変形を行う。この手法では、補償コードを挿入したことにより、第１のコード列と第２のコード列との合流点におけるコピー命令の伝播に対する障害を考慮することなくプログラムの変形を行うことができる。
【００１０】
さらに本発明は、次のように構成されたデータ処理装置としても実現することができる。このデータ処理装置は、コンパイラと、プログラムをインタプリタで実行すると共にコンパイラにてコンパイルされたコードで実行するプログラム実行部とを備える。そして、このコンパイラは、プログラムの実行対象がループ処理の最中にインタプリタを介して実行される第１のコード列からコンパイルされた第２のコード列へ遷移する場合に、第２のコード列の変形に影響を及ぼす第１のコード列中のコードのうち、所定の変形において無視できるコードを設定する設定手段と、無視できるコードを無視して第２のコード列に対し所定の変形を行うプログラム変形手段とを備えることを特徴とする。このデータ処理装置における設定手段及びプログラム変形手段は、プログラム制御によりコンパイラとして機能するコンピュータ（ＣＰＵ）にて実現される。
【００１１】
また、本発明は、コンピュータを制御して上述したプログラム変換方法における各ステップに相当する処理を実行させるプログラム、あるいは上記のデータ処理装置としてコンピュータを機能させるプログラムとしても実現される。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
【００１２】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
図１は、本実施の形態によるデータ処理方法が実現されるコンピュータシステムの構成を説明する図である。
図１を参照すると、本実施の形態におけるコンピュータシステムは、ソースプログラム（入力コード）をコンパイルするコンパイラ１００と、コンパイラ１００にてコンパイルされたオブジェクトプログラム（出力コード）を実行して種々の処理を行うプログラム実行部２００と、メモリ３００とを備える。コンパイラ１００及びプログラム実行部２００は、パーソナルコンピュータやワークステーションなどのコンピュータシステムにおけるプログラム制御されたＣＰＵにて実現される。メモリ３００は、コンピュータ装置のメインメモリであり、ＲＡＭ等で実現される。メモリ３００には、ＣＰＵを制御してコンパイラ１００として動作させるためのプログラムやコンパイルの対象であるプログラム（以下、実行プログラムと称す）が格納される。なお、メモリ３００に格納されるプログラムは、必要に応じて、適宜磁気ディスクその他の外部記録装置に保存されることは言うまでもない。
【００１３】
図１において、コンパイラ１００は、バイトコード（byte code）で記述された入力コードを入力して処理し、機械語で記述された出力コードを生成して出力する。この入力コードの入力は、コード生成装置４００にて生成された入力コードを直接入力したり、コード生成装置４００にて生成された入力コードを記憶した記憶装置５００から入力したり、ネットワーク６００上に存在するコード生成装置４００や記憶装置５００からネットワーク６００を介して入力したりすることにより行われる。コンパイラ１００により生成された出力コードは、プログラム実行部２００により実行される。
なお、本実施の形態において、コンパイラ１００は、ＪａｖａにおけるＪＩＴコンパイラのような、実行プログラムを実行する際に動的に実行プログラムのコンパイル処理を行うダイナミックコンパイラである。以下、本実施の形態では、ＪａｖａのＪＩＴコンパイラを例として説明する。
また、プログラム実行部２００は、コンパイラ１００にてコンパイルされた実行プログラムのオブジェクトコード（機械語コード）を実行するほか、当該実行プログラムをインタプリタによっても実行する。そして、実行プログラムを実行した際に、その実行プロファイルを取得してメモリ３００に蓄積する。
【００１４】
次に、上記のように構成されたコンピュータシステムにて実現される、コンパイラ１００によるプログラムの変形処理について説明する。
米国インテル社のＩＡ−６４等、３２ビット以外の種々のＣＰＵにおけるアーキテクチャでは、プログラムの途中で当該プログラムの実行対象が実行環境の異なる２つのコード列を遷移する場合、典型的にはインタプリタを介して実行されるコード列からコンパイルされたコード列へ遷移する場合に、これらのコード列間でローカル変数のイメージを合わせるための命令を、明示的に挿入することが必要となる。この場合、コンパイル時にこのままの状態で前方データフロー解析やUD-chainを使ったプログラムの最適化を行うと、これらの明示的に挿入された命令には「変数の定義」が含まれているために、最適化の効果が抑制されることとなる。本発明は、この明示的に挿入された命令の影響による最適化の効果の低下を防ぐため、２つの実施の形態を提案する。以下、それぞれについて詳細に説明する。
【００１５】
＜第１の実施の形態＞
第１の実施の形態は、インタプリタからの飛び込み口におけるベーシックブロック（Xfer BB）内の命令のうち、前方データフロー解析またはUD-chainを用いた最適化を行うに当たって無視できる（考慮しない）命令を特定し、合流点を越えて最適化することのできない変数の集合（ＫＩＬＬ集合）を正確に求める。そして、前方データフロー解析またはUD-chainを用いた最適化の際に、ＫＩＬＬ集合以外の変数についての命令（すなわち無視できる命令と特定された命令）を無視することにより、最適化が不必要に止まることを回避する。ただし、コピー命令の伝播（以下、適宜コピー伝播と記す）については無視できると特定された命令を単純に全て無視すると不都合があるので、個別的に判断を行う。
図２は、第１の実施の形態による合流点付近の最適化の処理手順を説明するフローチャートである。
【００１６】
図２に示すように、コンパイラ１００は、まず、Xfer BB内にインタプリタを介して実行されるコード列とコンパイルされたコード列とのローカル変数のイメージを合わせる命令を生成すると同時に、当該命令に対して「変数の定義を無視できる命令」であることを示すマークを付ける（ステップ２０１）。このマークとしては、例えば生成された命令にフラグデータを追加し、このフラグのオンオフによって「変数の定義を無視できる命令」かどうかを示すことができる。
また、コンパイラ１００は、この命令へのマークの付加に伴って、マークを付した命令に関わる変数の集合、すなわち、無視できる変数の集合を作成する（ステップ２０２）。この集合をIGNORE_VARsと呼ぶ。生成された集合IGNORE_VARsは、メモリ３００に保持され、次のＫＩＬＬ集合を求める処理において使用される。
【００１７】
次に、コンパイラ１００は、プログラムの最適化におけるコピー伝播を行うための前処理として、Ｘｆｅｒ  ＢＢのＫＩＬＬ集合を求める（ステップ２０３）。
図３は、ＫＩＬＬ集合を求める処理の疑似コードを示す図である。
図３に示すように、Ｘｆｅｒ  ＢＢの最初から最後までの各命令Ｉのうち、変数の定義を無視できる（上記のマークが付された）命令Ｉについて、「Ｉの出力変数」を出力変数に持つコピー命令の集合が求められる（１行目〜３行目）。そして、その集合の各要素（すなわちコピー命令）Ｅが変数から変数へのコピーである場合は、当該要素Ｅの入力がメモリ３００に保持されている集合ＩＧＮＯＲＥ＿ＶＡＲｓに含まれるならば、当該要素Ｅは命令Ｉを通過できるものとされる（４行目〜６行目）。そうでないならば、当該要素ＥをＫＩＬＬ集合に含める（７、８行目）。また、所定の要素Ｅが定数から変数へのコピーである場合は、当該要素Ｅは命令Ｉを通過できるものとされる（１０、１１行目）。また、変数の定義を無視できない（マークが付されていない）命令Ｉについては、通常の処理によりＫＩＬＬ集合が求められる。
【００１８】
コンパイラ１００は、以上の前処理の後、通常のコピー伝播処理を行う（ステップ２０４）。すなわち、ＫＩＬＬ集合に含まれる変数を要素とするコピー命令については合流点を越えて伝播することができず、他の変数を要素とするコピー命令については、変数の定義を無視してコピー命令を伝播する。
そして次に、コピー伝播以外の前進データフロー解析を使った最適化、及びUD-chainを使った最適化において、変数の定義を無視できる（マークが付されている）命令を無視して最適化を行う（ステップ２０５）。この後、最適化されたプログラムのオブジェクトコードが生成され、メモリ３００に格納されて、これ以後の実行では当該オブジェクトコードが実行されることとなる。
【００１９】
以上のようにして、コンパイラ１００は、個々の命令及び変数に対しコピー伝播において無視できるかどうかを個別に判断した上で、ＫＩＬＬ集合を正確に求め、コピー伝播において無視できる変数に関しては無視することによって、より多くの変数に関して最適化によるプログラムの変形を施すことができる。
なお、上記のステップ２０１で、コンパイラ１００がXfer BB内の命令に対して「変数の定義を無視できる」命令かどうかを判断することができるのは、そもそもXfer BB内に挿入されるコード列間のローカル変数のイメージを合わせる命令は、当該コンパイル処理においてコンパイラ１００自身により生成された命令だからである。
【００２０】
図４は、図７に示したコード列構成例に対して本実施の形態による最適化を施した様子を示す図である。
インタプリタを介して実行されるコード列において、Xfer BBでは、変数のコピー命令に関する情報として「L2 = L1、L3 = 1、L4 = L5」が入力されており、Xfer BB内には変数Ｌ２、Ｌ３、Ｌ４、Ｌ５に関してコード列間のイメージを合わせるための命令が記述されているので、変数Ｌ２、Ｌ３、Ｌ４、Ｌ５については変数の定義を無視することができる（集合IGNORE_VARsに含まれる）。このうち、コピー命令「L3 = 1」、「L4 = L5」の結果を伝播できることとなる。ただし、変数Ｌ２については、変数Ｌ１に関してコード列間のイメージを合わせるための命令が記述されていないため、コピー命令「L2 = L1」を伝播することはできない（仮に伝播をしてしまうと、変数Ｌ１の定義がないために間違った最適化結果となってしまう）。
以上のように、コピー命令「L3 = 1」、「L4 = L5」の結果を合流点以後のベーシックブロックに伝播したことにより、このベーシックブロックの４行目にあった変数Ｌ３が定数１となり、この後の分岐の一方が除去できることとなる（すなわち最適化の効果を得ることができる）。
【００２１】
＜第２の実施の形態＞
第２の実施の形態は、第１の実施の形態と同様に、前方データフロー解析またはUD-chainを用いた最適化を行うに当たって無視できる（考慮しない）命令を特定し、ＫＩＬＬ集合を求めて、これらの最適化の際にＫＩＬＬ集合以外の変数についての命令を無視する。さらに、所定のコピー命令を補償する補償コードをXfer BB内に追加することにより、当該コピー命令の伝播についても、無視できると特定された命令を単純に無視することができ、最適化が不必要に止まることを回避する。
図５は、第２の実施の形態による合流点付近の最適化の処理手順を説明するフローチャートである。
図５において、ステップ５０１、５０２の処理は、図２に示した第１の実施の形態におけるステップ２０１、２０２の処理と同様である。
次に本実施の形態のコンパイラ１００は、プログラムの最適化におけるコピー伝播を行うための前処理として、変数の定義を無視できる（上記のマークが付された）命令を無視してXfer BBのKILL集合を求める（ステップ５０３）。そして、通常のコピー伝播を行う（ステップ５０４）。
【００２２】
次に、コンパイラ１００は、合流点における変数のコピー命令に関する入力情報とステップ５０２で求めた集合IGNORE_VARsとに基づいて、Xfer BB内に補償コードを生成する（ステップ５０５）。具体的には、合流点における変数のコピー命令に関する入力情報に含まれる各要素のうちで、変数から変数へのコピーであり、出力が集合IGNORE_VARsに含まれ、入力が集合IGNORE_VARsに含まれないコピー命令を探し、そのようなコピー命令の入力と出力とを逆向きにしたコピー命令を、補償コードとして生成し、Xfer BBの最後に挿入する。
次に、コンパイラ１００は、コピー伝播以外の前進データフロー解析を使った最適化、及びUD-chainを使った最適化において、変数の定義を無視できる（マークが付されている）命令を無視して最適化を行う（ステップ５０６）。この後、最適化されたプログラムのオブジェクトコードが生成され、メモリ３００に格納されて、これ以後の実行では当該オブジェクトコードが実行されることとなる。
【００２３】
以上のようにして、コンパイラ１００は、出力が集合IGNORE_VARsに含まれる全てのコピー命令に関して、伝播を行い、より多くの変数に関して最適化によるプログラムの変形を施すことができる。本実施の形態では、Xfer BBにおいて変数の定義が記述されていない変数についても、補償コードを生成することによってコピー命令の伝播が行われるため、最適化の効果は第１の実施の形態よりも高い。
なお、本実施の形態では、Xfer BBに補償コードを挿入するため、当該Xfer BBの実行において処理コストが増すことになる。しかしながら、Xfer BBを実行するのは、プログラムの実行対象がインタプリタを介して実行されるコード列からコンパイルされたコード列へ遷移する際の１回のみであり、遷移した後はコンパイルされたコード列によって実行され、この部分で最適化の効果が上がるため、全体的にはプログラムの実行効率を向上させることができる。
【００２４】
図６は、図７に示したコード列構成例に対して本実施の形態による最適化を施した様子を示す図である。
インタプリタを介して実行されるコード列において、Xfer BBでは、変数のコピー命令に関する情報として「L2 = L1、L3 = 1、L4 = L5」が入力されており、Xfer BB内には変数Ｌ２、Ｌ３、Ｌ４、Ｌ５に関してコード列間のイメージを合わせるための命令が記述されている。さらに、Xfer BBには、出力が集合IGNORE_VARsに含まれ、入力が集合IGNORE_VARsに含まれないコピー命令「L2 = L1」に対する補償コード「L1 = L2」が記述されている。これにより、変数Ｌ１に関する変数の定義が変数Ｌ２と同一であることがわかるため、コピー命令「L2 = L1」、「L3 = 1」、「L4 = L5」の全てについて、伝播することができることとなる。
以上のように、コピー命令「L2 = L1」、「L3 = 1」、「L4 = L5」の結果を合流点以後のベーシックブロックに伝播したことにより、このベーシックブロックの４行目にあった変数Ｌ３が定数１となり、この後の分岐の一方が除去できることとなる（すなわち最適化の効果を得ることができる）。
【００２５】
なお、上述した実施の形態では、プログラムの実行対象がインタプリタを介して実行されるコード列からコンパイルされたコード列へ遷移する場合に、これらのコード列間における変数のイメージを合わせる命令の存在が最適化を妨げる場合について説明したが、本実施の形態によるプログラムの変形方法は、インタプリタを介して実行されるコード列からコンパイルされたコード列への遷移に限らず、一般に、実行環境が異なる２つのコード列間で遷移が行われる場合に適用することができる。
また、最適化において無視する命令及び変数についても、上述した変数の定義のための命令に限らず、実行される最適化の種類等に応じて、適切な判断基準に基づいて無視できる命令や変数を設定することにより、２つのコード列の合流点において最適化が止まることを回避することができる。
【００２６】
【発明の効果】
以上説明したように、本発明によれば、インタプリタを介して実行されるコード列とコンパイルされたコード列とのローカル変数のイメージを合わせるための明示的な命令の影響を低減させて最適化を行い、プログラムの実行効率の向上を図ることが可能となる。
【図面の簡単な説明】
【図１】  本実施の形態によるデータ処理方法が実現されるコンピュータシステムの構成を説明する図である。
【図２】  第１の実施の形態による合流点付近の最適化の処理手順を説明するフローチャートである。
【図３】  第１の実施の形態におけるＫＩＬＬ集合を求める処理の疑似コードを示す図である。
【図４】  図７に示したコード列構成例に対して第１の実施の形態による最適化を施した様子を示す図である。
【図５】  第２の実施の形態による合流点付近の最適化の処理手順を説明するフローチャートである。
【図６】  図７に示したコード列構成例に対して第２の実施の形態による最適化を施した様子を示す図である。
【図７】  インタプリタからの飛び込み口におけるコード列の構成を例示する図である。
【符号の説明】
１００…コンパイラ、２００…プログラム実行部、３００…メモリ、４００…コード生成装置、５００…記憶装置、６００…ネットワーク
【図１】
0003956113.tif 000002
【図２】
0003956113.tif 000003
【図３】
0003956113.tif 000004
【図４】
0003956113.tif 000005
【図５】
0003956113.tif 000006
【図６】
0003956113.tif 000007
【図７】
0003956113.tif 000008