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