(57)【特許請求の範囲】
【請求項１】
コンピュータにより、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するプログラム変換方法において、
前記コンピュータが、メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトがエスケープしていない範囲を求めるステップと、
前記コンピュータが、前記オブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行うステップと
前記コンピュータが、前記スカラーリプレイスメントを施された実行プログラムをメモリに格納するステップと
を含むことを特徴とするプログラム変換方法。
【請求項２】
前記スカラーリプレイスメントを実行するステップは、前記オブジェクトがエスケープしていない範囲内のメソッド呼び出しについて、当該オブジェクトに対するメモリアクセスが変更されないものとしてスカラーリプレイスメントを実行するステップを含むことを特徴とする請求項１に記載のプログラム変換方法。
【請求項３】
前記オブジェクトがエスケープしていない範囲を求めるステップは、
前記実行プログラムに対し、前方データフロー解析によりベーシックブロックごとに、前記メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求めるステップと、
前記ベーシックブロック内の命令を先頭から順に調べ、各命令の場所で、前記メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求めるステップと
を含むことを特徴とする請求項１に記載のプログラム変換方法。
【請求項４】
コンピュータにより、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するプログラム変換方法において、
前記コンピュータが、メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラムのソースコードに基づいて前記機械語コードを生成し、生成された機械語コードによる実行プログラムをメモリに格納するステップと、
前記コンピュータが、前記メモリから前記機械語コードによる実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトが外部から参照されない範囲で、メソッド呼び出しを越えてスカラーリプレイスメントを行うステップと、
前記コンピュータが、前記スカラーリプレイスメントを施された実行プログラムをメモリに格納するステップと
を含むことを特徴とするプログラム変換方法。
【請求項５】
前記スカラーリプレイスメントを行うステップは、
前記実行プログラムのベーシックブロックごとに、前記メソッド内で作成され、かつグローバルなメモリに書き込まれていないオブジェクトの集合を求めることにより、当該オブジェクトが外部から参照されない範囲を決定するステップを含むことを特徴とする請求項４に記載のプログラム変換方法。
【請求項６】
オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するコンピュータ装置において、
処理対象である前記実行プログラムのソースコードに基づいて前記機械語コードを生成するコード変換部と、
前記実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトがエスケープしていない範囲を求める最適化範囲決定部と、
前記最適化範囲決定部にて求められた前記オブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行うスカラーリプレイスメント実行部とを備えること
を特徴とするコンピュータ装置。
【請求項７】
前記スカラーリプレイスメント実行部は、前記オブジェクトがエスケープしていない範囲内のメソッド呼び出しを、当該オブジェクトに対するメモリアクセスが変更されないものとしてスカラーリプレイスメントを実行することを特徴とする請求項６に記載のコンピュータ装置。
【請求項８】
前記最適化範囲決定部は、
前記実行プログラムに対し、前方データフロー解析によりベーシックブロックごとに、前記メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求める第１の手段と、
前記ベーシックブロック内の命令を先頭から順に調べ、各命令の場所で、前記メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求める第２の手段と
を備えることを特徴とする請求項６に記載のコンピュータ装置。
【請求項９】
オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するコンピュータ装置において、
前記実行プログラムのソースコードに基づいて前記機械語コードを生成するコード変換部と、
前記コード変換部により生成された前記機械語コードの実行プログラムに対し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトがエスケープしていない範囲内でメソッド呼び出しを越えてスカラーリプレイスメントを行う最適化部と
を備えることを特徴とするコンピュータ装置。
【請求項１０】
オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードをコンパイルして機械語コードに変換するコンパイラと、
機械語コードに変換された当該プログラムを実行するプログラム実行部とを備え、
前記コンパイラは、
前記実行プログラムのソースコードに基づいて前記機械語コードを生成するコード変換部と、
メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトがエスケープしていない範囲を求める最適化範囲決定部と、
前記最適化範囲決定部にて求められた前記オブジェクトがエスケープしていない範囲内で、当該範囲内のメソッド呼び出しを越えてスカラーリプレイスメントを行うスカラーリプレイスメント実行部と、
を備えることを特徴とするコンピュータ装置。
【請求項１１】
コンピュータを制御して、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムであって、
メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトがエスケープしていない範囲を求める処理と、
前記オブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行う処理と、
前記スカラーリプレイスメントを施された実行プログラムをメモリに格納する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１２】
前記スカラーリプレイスメントを実行する処理において、前記オブジェクトがエスケープしていない範囲内のメソッド呼び出しを、当該オブジェクトに対するメモリアクセスが変更されないものとしてスカラーリプレイスメントを、前記コンピュータに実行させることを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記オブジェクトがエスケープしていない範囲を求める処理は、
前記実行プログラムに対し、前方データフロー解析によりベーシックブロックごとに、前記メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求める処理と、
前記ベーシックブロック内の命令を先頭から順に調べ、各命令の場所で、前記メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求める処理と
を含むことを特徴とする請求項１１に記載のプログラム。
【請求項１４】
コンピュータを制御して、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムであって、
メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラムのソースコードに基づいて前記機械語コードを生成し、生成された機械語コードによる実行プログラムをメモリに格納する処理と、
前記メモリから前記機械語コードによる実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトが外部から参照されない範囲で、メソッド呼び出しを越えてスカラーリプレイスメントを行う処理と、
前記スカラーリプレイスメントを施された実行プログラムをメモリに格納する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１５】
前記スカラーリプレイスメントを行う処理は、
前記実行プログラムのベーシックブロックごとに、前記メソッド内で作成され、かつグローバルなメモリに書き込まれていないオブジェクトの集合を求めることにより、当該オブジェクトが外部から参照されない範囲を決定する処理を含むことを特徴とする請求項１４に記載のプログラム。
【請求項１６】
コンピュータを制御してオブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトがエスケープしていない範囲を求める処理と、
前記オブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行う処理と、
前記スカラーリプレイスメントを施された実行プログラムをメモリに格納する処理と
を前記コンピュータに実行させることを特徴とする記録媒体。
【請求項１７】
コンピュータを制御してオブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
メモリから処理対象である前記実行プログラムを読み出し、当該実行プログラムのソースコードに基づいて前記機械語コードを生成し、生成された機械語コードによる実行プログラムをメモリに格納する処理と、
前記メモリから前記機械語コードによる実行プログラムを読み出し、当該実行プログラム中のメソッドに関して、当該メソッド内で作成されたオブジェクトが外部から参照されない範囲で、メソッド呼び出しを越えてスカラーリプレイスメントを行う処理と、
前記スカラーリプレイスメントを施された実行プログラムをメモリに格納する処理と
を前記コンピュータに実行させることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム中のスカラーリプレイスメント（scalar replacement）により、プログラムの実行効率の向上を図る方法に関する。
【０００２】
【従来の技術】
プログラムを最適化する手法に、グローバルなメモリ上にある変数をメソッド内でローカルな場所（ローカル変数など）に置き換える、スカラーリプレイスメントという手法がある。この最適化は、「メモリアクセスのコストを減らす」という効果もあるが、それだけではなく、置き換えた変数の生存区間が大きく広がるため、その後の最適化（共通部分式の除去等）の効果を大幅に高めるという副次的な効果があることでも知られている。
【０００３】
このスカラーリプレイスメントを行う場合、プログラム中に存在するメソッド呼び出しが支障となる。すなわち、グローバルなメモリ上にある変数の値は、呼び出されたメソッド内で変更される可能性があるため、単純にメソッド呼び出しを越えて最適化することができなかった。
【０００４】
従来、メソッド呼び出しを越えてメモリアクセスを最適化するためには、エスケープアナリシス（Escape Analysis）と呼ばれる技術を用いて呼び出されるメソッドの中を解析し、その解析結果に基づいて最適化を行う方法があった。この方法では、メソッド内のnewやnewarray等で作成されるオブジェクトに関して、そのメソッド内の全ての場所で当該メソッドの外から当該オブジェクトを参照できない（これをエスケープしていないという）場合に限り、当該オブジェクトのメモリをヒープ領域ではなくスタック領域にとることにより最適化が行われる。なお、エスケープアナリシスについては、例えば、次の文献１、２に詳細に記載されている。
文献１：Escape Analysis for Java（In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications（以下、OOPSLA）'99）
文献２：Compositional Pointer and Escape Analysis for Java Programs （OOPSLA'99）
【０００５】
【発明が解決しようとする課題】
しかしながら、上記のように、エスケープアナリシスを用いた最適化は、メソッド内に一個所でもエスケープしている部分がある場合には、当該メソッドに対して最適化を行うことができなかった。
また、エスケープアナリシスによる呼び出しメソッド内の解析は、多大な処理コストが必要であるため、導入することが困難な場合があった。例えば、ＪａｖａにおけるＪＩＴ（Just In Time）コンパイラのようなコンパイル時間に影響を受けるコンパイラに適用するには、メソッドサイズ等を考慮した非常に厳しい制限が行われていた。
さらに、動的なコール命令などのために、呼び出しメソッド内の解析そのものが全くできない場合もあった。
【０００６】
そこで、本発明は、プログラムの最適化において、呼び出しメソッド内の解析を行うことなく、より効果的にスカラーリプレイスメントを行えるようにすることを目的とする。
【０００７】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、コンピュータを用いてオブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換する、次のようなプログラム変換方法として実現される。すなわち、このプログラム変換方法は、処理対象である実行プログラム中のメソッドに関して、このメソッド内で作成されたオブジェクトがエスケープしていない範囲を求めるステップと、このオブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行うステップと、スカラーリプレイスメントを施された実行プログラムをメモリに格納するステップとを含むことを特徴とする。
【０００８】
ここで、このスカラーリプレイスメントを実行するステップでは、好ましくは、オブジェクトがエスケープしていない範囲内のメソッド呼び出しについて、このオブジェクトに対するメモリアクセスが変更されないものとしてスカラーリプレイスメントを実行する。
また、このオブジェクトがエスケープしていない範囲を求めるステップは、詳しくは、実行プログラムに対し、前方データフロー解析によりベーシックブロックごとに、このメソッド内で作成され、かつエスケープしていないオブジェクトの集合を求めるステップと、このベーシックブロック内の命令を先頭から順に調べ、各命令の場所で、このメソッド内で作成され、かつエスケープしていないオブジェクトの集合を求めるステップとを含む。
【０００９】
また、本発明による他のプログラム変換方法は、処理対象である実行プログラムのソースコードに基づいて機械語コードを生成するステップと、生成された機械語コードによる実行プログラム中のメソッドに関して、このメソッド内で作成されたオブジェクトが外部から参照されない範囲で、メソッド呼び出しを越えてスカラーリプレイスメントを行うステップとを含むことを特徴とする。
【００１０】
ここで、このスカラーリプレイスメントを行うステップは、詳しくは、実行プログラムのベーシックブロックごとに、メソッド内で作成され、かつグローバルなメモリに書き込まれていないオブジェクトの集合を求めることにより、このオブジェクトが外部から参照されない範囲を決定するステップを含む。
【００１１】
また、上記の目的を達成する他の本発明は、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換する、次のように構成されたコンピュータ装置として実現される。すなわち、このコンピュータ装置は、処理対象である実行プログラムのソースコードに基づいて機械語コードを生成するコード変換部と、この機械語コードによる実行プログラム中のメソッドに関して、このメソッド内で作成されたオブジェクトがエスケープしていない範囲を求める最適化範囲決定部と、このオブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行うスカラーリプレイスメント実行部とを備えることを特徴とする。
【００１２】
ここで、このスカラーリプレイスメント実行部は、好ましくは、オブジェクトがエスケープしていない範囲内のメソッド呼び出しを、当該オブジェクトに対するメモリアクセスが変更されないものとしてスカラーリプレイスメントを実行する。
さらに、最適化範囲決定部は、より詳しくは、実行プログラムに対し、前方データフロー解析によりベーシックブロックごとに、メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求める第１の手段と、このベーシックブロック内の命令を先頭から順に調べ、各命令の場所で、メソッド内で作成され、かつエスケープしていないオブジェクトの集合を求める第２の手段とを備える。
【００１３】
また、本発明による他のコンピュータ装置は、実行プログラムのソースコードに基づいて機械語コードを生成するコード変換部と、コード変換部により生成された機械語コードの実行プログラムに対し、この実行プログラム中のメソッドに関して、このメソッド内で作成されたオブジェクトがエスケープしていない範囲内でメソッド呼び出しを越えてスカラーリプレイスメントを行う最適化部とを備えることを特徴とする。
【００１４】
上記のコンピュータ装置は、機械語コードに変換された実行プログラムを実行するプログラム実行部をさらに備える構成とすることもできる。
さらにまた、本発明は、コンピュータを制御して上述したプログラム変換方法や各種の機能を実現するプログラムとして実現することができる。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
【００１５】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
図１は、本実施の形態による最適化方法を実現するコンピュータシステムのシステム構成を示す図である。
図１を参照すると、本実施の形態におけるコンピュータシステムは、ソースプログラム（入力コードまたはソースコード）をコンパイルするコンパイラ１００と、コンパイラ１００にてコンパイルされたオブジェクトプログラム（出力コードまたはオブジェクトコード）を実行して種々の処理を行うプログラム実行部２００とを備える。コンパイラ１００及びプログラム実行部２００は、パーソナルコンピュータやワークステーションなどのコンピュータ装置におけるプログラム制御されたＣＰＵ及びＲＡＭ等のメモリにて実現される。図示しないメモリには、ＣＰＵを制御してコンパイラ１００あるいはプログラム実行部２００として動作させるためのプログラムやコンパイルの対象となるプログラムが格納される。なお、メモリに格納されるプログラムは、必要に応じて、適宜磁気ディスクその他の記録媒体に退避、保存されることは言うまでもない。
【００１６】
図１において、コンパイラ１００は、コード入力部３００から所定のプログラム言語やバイトコード（byte code）で記述されたプログラム（コンパイル対象のプログラム、以下、実行プログラムと称す）のソースコードを入力して処理し、機械語で記述されたオブジェクトコードを生成して出力する。このコード入力部３００は、ソースコードを生成するコード生成装置や、当該コード生成装置にて生成されたソースコードを記憶した記憶装置（磁気ディスク装置など）にて実現される。また、ネットワーク上に存在するコード生成装置や記憶装置から当該ネットワークを介してソースコードを入力するネットワークインターフェイスにて実現することもできる。コンパイラ１００により生成された実行プログラムのオブジェクトコードは、プログラム実行部２００により実行される。
なお、本実施の形態において、コンパイラ１００は、ＪａｖａにおけるＪＩＴ（Just In Time）コンパイラのような、プログラム実行部２００が実行プログラムを実行する際に動的にコンパイル処理を行うコンパイラであっても良いし、ソースプログラムを予めコンパイルして生成されたオブジェクトプログラムを実行プログラムとする使用形態におけるコンパイラであっても良い。また、コンパイラ１００とプログラム実行部２００とは、単一のコンピュータ装置に設けても良いし、別個のコンピュータ装置においてコンパイラ１００とプログラム実行部２００とを実現する構成としても良い。
【００１７】
図２は、本実施の形態におけるコンパイラ１００の構成を説明する図である。
本実施の形態のコンパイラ１００は、コンパイルされたプログラムコードに対して、次の手法による最適化を実行する。すなわち、
・メソッド内のnew、newarray等で作成されたオブジェクトＯｂｊについて、エスケープしていない（すなわち、当該メソッドの外から当該オブジェクトＯｂｊを参照できない）範囲Ｒ（Ｏｂｊ）を求める。
・範囲Ｒ（Ｏｂｊ）内のメソッド呼び出しに対し、オブジェクトＯｂｊに対するメモリアクセスは変更されないものとして扱ってスカラーリプレイスメントを行う。
【００１８】
図２を参照すると、コンパイラ１００は、ソースコードをオブジェクトコードに変換するコード変換部１１０と、コード変換部１１０にて生成されたオブジェクトコードに対して上述した範囲Ｒ（Ｏｂｊ）を決定する最適化範囲決定部１２０と、最適化範囲決定部１２０により決定された範囲Ｒ（Ｏｂｊ）内のメソッド呼び出しに対してスカラーリプレイスメントを行うスカラーリプレイスメント実行部１３０とを備える。ここで、最適化範囲決定部１２０及びスカラーリプレイスメント実行部１３０が上述した最適化を行う最適化部として機能する。
図２に示したコンパイラ１００の各構成要素は、プログラム制御されたＣＰＵにて実現される仮想的なソフトウェアブロックである。なお、図２に示したコンパイラ１００の構成要素は、本実施の形態における特徴的な機能に関するものである。特に図示しないが、実際にはコンパイラ１００は、コード変換のために必要なソースコードの字句解析や構文解析、本実施の形態による最適化以外の各種の最適化処理といったコンパイル処理における一般的な機能をさらに有することは言うまでもない。
【００１９】
上記のように構成されたコンパイラ１００は、処理対象である実行プログラムを入力してメモリに保持する。そして、当該メモリから実行プログラムを読み出して字句解析や構文解析を行った後、これらの解析で得られた情報に基づいて、コード変換部１１０によりオブジェクトコードを生成する。生成されたオブジェクトコードはメモリに格納される。
【００２０】
コンパイラ１００の最適化範囲決定部１２０は、コード変換部１１０にて生成されたオブジェクトコードをメモリから読み出し、上述したように、このオブジェクトコードを対象として、範囲Ｒ（Ｏｂｊ）を求める。
具体的な処理としては、まず、次の数１式で示される前方データフロー解析を使って、ベーシックブロックｎの先頭で「メソッド内でnew、newarray等で作成され、まだエスケープしていないオブジェクト」と判断されるオブジェクトの集合Ｉｎ（ｎ）を求める。そして、求まった集合Ｉｎ（ｎ）に基づいて、ベーシックブロックｎ内の命令を先頭から順に調べながら、各命令の場所で「メソッド内でnew, newarray等で作成され、まだエスケープしていないオブジェクト」の集合を求め、当該集合に含まれるオブジェクトの範囲を範囲Ｒ（Ｏｂｊ）とする。
【数１】
0003790707.tif 000002
ここで、Ｇｅｎ（ｎ）は、ベーシックブロックｎ内でnew、newarray等で作成され、ベーシックブロックｎの最後の点で、まだエスケープしていないオブジェクトの集合である。Ｋｉｌｌ（ｎ）は、ベーシックブロックｎ内でエスケープするオブジェクトの集合である。また、ベーシックブロックとは、ストレートコード、すなわちコントロールフローが途中に入ることもなく、途中から出ることもないようなコード列の範囲をブロックで認識したものである。
【００２１】
図３は、最適化範囲決定部１２０にて実行される、前方データフロー解析によりオブジェクトの集合Ｉｎ（ｎ）を求める処理の詳細を説明するフローチャートである。
図３に示すように、最適化範囲決定部１２０は、まずパラメータｎ、changeの初期化を行う（ステップ３０１）。ここで、ｎはベーシックブロック番号、changeはデータフロー方程式を解く際の収束判定のフラグを意味する。
次に、最適化範囲決定部１２０は、後でオブジェクトの集合Ｉｎの比較を行うため、OldInという集合にコピーを行う（ステップ３０２）。そして、ベーシックブロックｎ（図３ではブロックｎと表記）の直前のベーシックブロック（図３ではブロックｍと表記）が存在するかどうかを調べる（ステップ３０３）。そのようなベーシックブロック（ブロックｍ）が存在するならば、集合Ｉｎ（ｎ）の内容をＩｎ（ｎ）＝Ｏｕｔ（ｍ）とする（ステップ３０４）。そして、他にベーシックブロックｎの直前のベーシックブロック（ブロックｍ）が存在するかどうかを調べる（ステップ３０５）。そのようなベーシックブロック（ブロックｍ）が存在するならば、集合Ｉｎ（ｎ）の内容をＩｎ（ｎ）＝Ｉｎ（ｎ）∩Ｏｕｔ（ｍ）とする（ステップ３０６）。このステップ３０３からステップ３０６の処理は、数１式の最初の式（集合Ｏｕｔから集合Ｉｎを計算する）を実際に計算している部分である。
【００２２】
ステップ３０３またはステップ３０５において、ベーシックブロックｎの直前にベーシックブロック（ブロックｍ）が存在しない場合、次に最適化範囲決定部１２０は、ステップ３０２で生成された集合OldInと集合Ｉｎとを比較する。そして、両者の内容が異なっているならば、changeのフラグを立てる（ステップ３０７）。
【００２３】
次に、最適化範囲決定部１２０は、後で集合Ｏｕｔの比較を行うため、OldOutという集合にコピーを行う（ステップ３０８）。そして、集合Ｏｕｔ（ｎ）の内容をＯｕｔ（ｎ）＝（Ｉｎ（ｎ）−Ｋｉｌｌ（ｎ））∪Ｇｅｎ（ｎ）とする（ステップ３０９）。このステップ３０９の処理は、数１式の２つ目の式（ＩｎからＯｕｔを計算する）を実際に計算している部分である。
次に、最適化範囲決定部１２０は、ステップ３０８で生成された集合OldOutと集合Ｏｕｔとを比較する。そして、両者の内容が異なっているならば、changeのフラグを立てる（ステップ３１０）。
【００２４】
以上の処理の後、最適化範囲決定部１２０は、パラメータｎを１加算し（ステップ３１１）、新たなｎの値がベーシックブロックの数に達したかどうかを調べる。そして、ｎの値がベーシックブロックの数に達するまで（すなわち、全てのベーシックブロックに対して処理が終了するまで）ステップ３０２乃至ステップ３１０の処理を繰り返す（ステップ３１２）。
全てのベーシックブロックに対して処理が終了したならば、次に最適化範囲決定部１２０は、changeのフラグが立っている集合があるかどうかを調べ、全てのchangeのフラグが立たなくなるまで（すなわち、収束するまで）ステップ３０１乃至ステップ３１２の処理を繰り返す（ステップ３１３）。
【００２５】
上述したように、最適化範囲決定部１２０は、この後、上記のようにして求まった集合Ｉｎ（ｎ）に基づいて、ベーシックブロックｎ内の命令を先頭から順に調べ、範囲Ｒ（Ｏｂｊ）を決定する。
【００２６】
コンパイラ１００のスカラーリプレイスメント実行部１３０は、最適化範囲決定部１２０にて決定された範囲Ｒ（Ｏｂｊ）内のメソッド呼び出しについて、オブジェクトＯｂｊに対するメモリアクセスは変更されないものとして扱って（すなわち、メソッド呼び出しを越えて）、スカラーリプレイスメントを行う。
そしてさらに、スカラーリプレイスメントされたメソッド呼び出し命令の処理の中で、
「メソッド呼び出しでメモリの値が変わる可能性があるので、このメソッド呼び出しを越えて最適化できない」
という処理をしている部分を、次のように２つの場合に応じた処理に変更する。
・当該部分がこの命令の場所で求まった、メソッド内でnew、newarray等で作成され、まだエスケープしていないオブジェクトの集合であるならば、このメソッド呼び出しでオブジェクト内のメモリの値が絶対に変わらないので、このメソッド呼び出しを越えて最適化できる。
・当該部分がこの命令の場所で求まった、メソッド内でnew、newarray等で作成され、まだエスケープしていないオブジェクトの集合でないならば、このメソッド呼び出しでオブジェクト内のメモリの値が変わる可能性があるので、このメソッド呼び出しを越えて最適化できない。
図４は、この処理の変更のアルゴリズムを示す図である。
以上のようにしてスカラーリプレイスメントによる最適化を施された実行プログラムは、必要に応じてさらに他の最適化を施された後にメモリに格納され、プログラム実行部２００により読み出されて実行されることとなる。
【００２７】
次に、本実施の形態を実際のプログラムに適用した場合の最適化の実行例を説明する。
図５は、適用対象のプログラムを例示する図である。
図５に示すプログラムにおいて、従来のエスケープアナリシスでは、メソッド呼び出しfoo(D, E)が存在するため、このメソッド呼び出しfoo(D, E)の中を解析し、Obj.xの値が変わらないことが保証されなければ、Obj.xのアクセスを最適化することができない。この解析に多大な処理コストを要する他、メソッド呼び出しによっては、そのような解析ができないために、スカラーリプレイスメントによる最適化を行うことができない。
【００２８】
本実施の形態では、図５のプログラムに対して、まず最適化範囲決定部１２０により、範囲Ｒ（Ｏｂｊ）が決定される。
図６は、図５のプログラムに対して、範囲Ｒ（Ｏｂｊ）を決定した様子を示す図である。
図６において、２行目から４行目までの、Obj.x = a、foo (D, E)、b = Obj.x; の３行は、new（図では大文字で表記）で定義されたObjがエスケープしていない。そして、次のD.obj = Objにおいて、Objをグローバルなメモリへ書き込むことにより、このメソッド外からObjがアクセス可能となるため、Objはエスケープしたと判断される。そこで、上の３行の範囲が範囲Ｒ（Ｏｂｊ）となる。
【００２９】
次に、スカラーリプレイスメント実行部１３０により、範囲Ｒ（Ｏｂｊ）に対するスカラーリプレイスメントが行われる。
図７は、図６に示した範囲Ｒ（Ｏｂｊ）に対してスカラーリプレイスメントを実行した様子を示す図である。
図７において、３行目のfoo(D, E)について、当該部分がメソッド内でnewによって作成され、まだエスケープしていないオブジェクトの集合に含まれていることから、オブジェクトObjは、ここのfooの中から絶対にアクセスできないことがわかる。したがって、Objに対するメモリアクセスに関し、このメソッドコールをKillにする必要は無い。
また、４行目は、スカラーリプレイスメントにより、b = a（２行目参照）に置き換えられ、メモリからのロードがなくなっている（最適化されている）。
【００３０】
これに対して、６行目のfoo(D, E)は５行目のD.obj = ObjによりObjがエスケープした後のメソッド呼び出しであるため、変数の値が呼び出されたメソッドfoo(D, E)内で変更される可能性がある。そのため、次のc=Obj.x;は４行目のように最適化することはできない。
【００３１】
以上のようにして、本実施の形態によれば、メソッド中に他のメソッドに対するメソッド呼び出しが存在していても、当該メソッド内で定義されたオブジェクトに関して、当該オブジェクトがエスケープしない範囲でスカラーリプレイスメントによる最適化を行うことが可能となる。
また、メソッドが動的なコール命令を含む場合にも、以上の手法をそのまま利用して、当該メソッド内で定義されたオブジェクトに関して、当該オブジェクトがエスケープしない範囲でスカラーリプレイスメントによる最適化を行うことが可能となる。
さらに、エスケープアナリシスによる解析が不要であるため、当該解析処理に要する処理コストが削減され、ＪａｖａにおけるＪＩＴコンパイラのような動的なコンパイラに好適である。
【００３２】
【発明の効果】
以上説明したように、本発明によれば、プログラムの最適化において、メソッド内の解析を行うことなく、より効果的にスカラーリプレイスメントを行うことが可能となる。
【図面の簡単な説明】
【図１】  本実施の形態による最適化方法を実現するコンピュータシステムのシステム構成を示す図である。
【図２】  本実施の形態におけるコンパイラの構成を説明する図である。
【図３】  本実施の形態の最適化範囲決定部によるオブジェクトの集合Ｉｎ（ｎ）を求める処理の詳細を説明するフローチャートである。
【図４】  本実施の形態のスカラーリプレイスメントを行った後における処理の変更のアルゴリズムを示す図である。
【図５】  本実施の形態の適用対象であるプログラムを例示する図である。
【図６】  図５のプログラムに対して、範囲Ｒ（Ｏｂｊ）を決定した様子を示す図である。
【図７】  図６に示した範囲Ｒ（Ｏｂｊ）に対してスカラーリプレイスメントを実行した様子を示す図である。
【符号の説明】
１００…コンパイラ、１１０…コード変換部、１２０…最適化範囲決定部、１３０…スカラーリプレイスメント実行部、２００…プログラム実行部、３００…コード入力部
【図１】
0003790707.tif 000003
【図２】
0003790707.tif 000004
【図３】
0003790707.tif 000005
【図４】
0003790707.tif 000006
【図５】
0003790707.tif 000007
【図６】
0003790707.tif 000008
【図７】
0003790707.tif 000009