(57)【特許請求の範囲】
【請求項１】
オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するプログラム変換方法において、
メモリから処理対象である実行プログラムを読み出し、当該実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中のオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数であるかどうかを調べるステップと、
前記実行プログラム中の所定のメソッド呼び出しに関して、当該メソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、デッドコードエリミネーションにより当該メソッド呼び出しにおける所定のコードを消去するステップと、
前記コードを消去された実行プログラムをメモリに格納するステップと
を含むことを特徴とするプログラム変換方法。
【請求項２】
前記デッドコードエリミネーションによりメソッド呼び出しのコードを消去するステップに先立って、当該メソッド呼び出しをインライン展開するステップをさらに含むことを特徴とする請求項１に記載のプログラム変換方法。
【請求項３】
前記デッドコードエリミネーションによりメソッド呼び出しのコードを消去するステップに先立って、当該メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化するステップをさらに含むことを特徴とする請求項１に記載のプログラム変換方法。
【請求項４】
オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するプログラム変換方法において、
メモリから処理対象である実行プログラムを読み出し、当該実行プログラム中の所定のメソッド呼び出しをインライン展開する第１のステップと、
インライン展開された前記メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化する第２のステップと、
前記第１、第２のステップが施された前記実行プログラムに対してデッドコードエリミネーションを実行する第３のステップと、
デッドコードエリミネーションを施された実行プログラムをメモリに格納する第４のステップと
を含むことを特徴とするプログラム変換方法。
【請求項５】
前記実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、当該メソッド呼び出しを前記インライン展開の対象として決定するステップをさらに含むことを特徴とする請求項４に記載のプログラム変換方法。
【請求項６】
前記実行プログラム中の所定のメソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化しない場合に、当該メソッド呼び出しを前記インライン展開の対象として決定するステップをさらに含むことを特徴とする請求項４に記載のプログラム変換方法。
【請求項７】
オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するコンピュータ装置において、
メソッド呼び出しにおけるオブジェクト参照の使用の状態に基づいて、処理対象となるメソッド呼び出しを決定する処理対象抽出部と、
前記処理対象抽出部により処理対象として決定されたメソッド呼び出しをインライン展開するインライン展開処理部と、
前記インライン展開処理部にてインライン展開された前記メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化するスカラー化処理部と、
前記インライン展開処理部及び前記スカラー化処理部による処理が施された実行プログラムに対してデッドコードエリミネーションを実行するデッドコードエリミネーション実行部と
を備えることを特徴とするコンピュータ装置。
【請求項８】
前記処理対象抽出部は、前記実行プログラム中の所定のメソッド呼び出しに関して、当該メソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、当該メソッド呼び出しを処理対象として決定することを特徴とする請求項７に記載のコンピュータ装置。
【請求項９】
前記実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中のオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数であるかどうかを調べるコード解析部をさらに備え、
前記処理対象抽出部は、前記コード解析部の解析結果に基づいて処理対象となるメソッド呼び出しを決定することを特徴とする請求項７に記載のコンピュータ装置。
【請求項１０】
オブジェクト指向プログラミング言語で記述されたプログラムのソースコードをコンパイルして機械語コードに変換するコンパイラと、
機械語コードに変換された当該プログラムを実行するプログラム実行部とを備え、
前記コンパイラは、
前記プログラム中の所定のメソッド呼び出しに関して、当該メソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、当該メソッド呼び出しを処理対象とする処理対象抽出部と、
前記処理対象抽出部により処理対象として決定されたメソッド呼び出しをインライン展開するインライン展開処理部と、
前記インライン展開処理部にてインライン展開された前記メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化するスカラー化処理部と、
前記インライン展開処理部及び前記スカラー化処理部による処理が施された実行プログラムに対してデッドコードエリミネーションを実行するデッドコードエリミネーション実行部と
を備えることを特徴とするコンピュータ装置。
【請求項１１】
コンピュータを制御して、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムであって、
メモリから処理対象である実行プログラムを読み出し、当該実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中のオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数であるかどうかを調べる処理と、
前記実行プログラム中の所定のメソッド呼び出しに関して、当該メソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、デッドコードエリミネーションにより当該メソッド呼び出しにおける所定のコードを消去する処理と、
前記コードを消去された実行プログラムをメモリに格納する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１２】
前記デッドコードエリミネーションによりメソッド呼び出しのコードを消去する処理に先立って、当該メソッド呼び出しをインライン展開する処理を、前記コンピュータにさらに実行させることを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記デッドコードエリミネーションによりメソッド呼び出しのコードを消去する処理に先立って、当該メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化する処理を前記コンピュータにさらに実行させることを特徴とする請求項１１に記載のプログラム。
【請求項１４】
コンピュータを制御して、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムであって、
メモリから処理対象である実行プログラムを読み出し、当該実行プログラム中のメソッド呼び出しにおけるオブジェクト参照の使用の状態に基づいて、処理対象となるメソッド呼び出しを決定する手段と、
メモリから前記処理対象である実行プログラムを読み出し、処理対象として決定された前記メソッド呼び出しをインライン展開する手段と、
インライン展開された前記メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化する手段と、
前記インライン展開及び前記スカラー化が施された前記実行プログラムに対してデッドコードエリミネーションを実行する手段として
前記コンピュータを機能させることを特徴とするプログラム。
【請求項１５】
前記コンピュータの機能として実現される前記処理対象となるメソッド呼び出しを決定する手段は、前記実行プログラム中の所定のメソッド呼び出しに関して、当該メソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、当該メソッド呼び出しを処理対象として決定することを特徴とする請求項１４に記載のプログラム。
【請求項１６】
前記実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中のオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数であるかどうかを調べる手段として、前記コンピュータをさらに機能させ、
前記処理対象となるメソッド呼び出しを決定する手段は、前記メソッド呼び出しに関して調べた結果に基づいて処理対象となるメソッド呼び出しを決定することを特徴とする請求項１４に記載のプログラム。
【請求項１７】
コンピュータを制御してオブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
メモリから処理対象である実行プログラムを読み出し、当該実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中のオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数であるかどうかを調べる処理と、
前記実行プログラム中の所定のメソッド呼び出しに関して、当該メソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されないところの引数である場合に、デッドコードエリミネーションにより当該メソッド呼び出しにおける所定のコードを消去する処理と、
前記コードを消去された実行プログラムをメモリに格納する処理と
を前記コンピュータに実行させることを特徴とする記録媒体。
【請求項１８】
コンピュータを制御してオブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを機械語コードに変換するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
メモリから処理対象である実行プログラムを読み出し、当該実行プログラム中のメソッド呼び出しにおけるオブジェクト参照の使用の状態に基づいて、処理対象となるメソッド呼び出しを決定する手段と、
メモリから前記処理対象である実行プログラムを読み出し、処理対象として決定された前記メソッド呼び出しをインライン展開する手段と、
インライン展開された前記メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化する手段と、
前記インライン展開及び前記スカラー化が施された前記実行プログラムに対してデッドコードエリミネーションを実行する手段として
前記コンピュータを機能させることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータプログラムの最適化方法に関し、特に計算結果が使用されない計算（不使用計算）を削除して最適化を行う方法に関する。
【０００２】
【従来の技術】
今日、複雑なソフトウェアは、機能毎にコンポーネント化されて設計されることが一般的である。この場合、各コンポーネントは、様々なプログラムで共通に使える機能を提供するよう設計される。
そうしたソフトウェアをＪａｖａに代表されるようなオブジェクト指向言語で書く場合、各機能はクラス、オブジェクト、メソッドに分類され、実現される。そして、ある機能を利用したいとき、プログラムはオブジェクトを生成してメソッドを呼ぶ。
【０００３】
こうしたオブジェクト指向的なソフトウェアの設計では、計算結果の全てを必ずしも必要としない場合がある。例えば、２つの情報を含むオブジェクトが値の授受に使われるとき、プログラムの場所によっては片方の情報しか使わない場合などである。その場合、使わない情報のための計算は、無駄な処理であり、そのような無駄な処理の存在がソフトウェアの実行性能に大きな影響を与えてしまう場合もある。
【０００４】
コンパイラによるプログラムの最適化技術としてデッドコードエリミネーション（dead code elimination：ＤＣＥ）という手法（dead store eliminationとも言う）が知られている。これは、コンパイルの対象内におけるメソッドなどを解析することにより、計算結果が使われないと判断されるコードを消去する最適化技術である。こうしたコードには、コントロールフロー上の不到達コード（unreachable code）、解決済みの条件分岐（resolved conditionals）、使われない値を定義するコード（dead store）がある。具体的な手法としては、ＣＦＧ（Context Free Grammar）やＳＳＡ形式（Static Single Assignment Form）上で、定数伝搬（constant propagation）やコピー伝搬（copy propagation）などの前向きデータフロー（forward dataflow）最適化と組み合わせて、定義値の使用者（reaching use）を解析する後ろ向きデータフロー（backward dataflow）最適化を行う。
【０００５】
【発明が解決しようとする課題】
しかしながら、上述したＤＣＥによるプログラムの最適化技術は、数値計算のように複雑な計算式の無駄を削減する点では効果的だが、Ｊａｖａ等のコンポーネント化されたオブジェクト指向言語では機能しにくいという欠点があった。その大きな理由は次の２つである。
１つは、ＤＣＥの削除対象がメソッド内のコードに限られることである。通常、Ｊａｖａのようなオブジェクト指向言語では、１つの情報を作るために複数あるいは多段のメソッド呼び出しが行われるのが普通である。そのような多段のメソッド呼び出しが行われている場合にはＤＣＥによる削除対象とならない。
もう１つの理由は、ヒープに書かれた値はグローバルに参照可能であり、そうしたグローバルな値についてＤＣＥはreaching use解析できないことである。通常、Ｊａｖａのオブジェクトはヒープ上に作られる。そのため、ＤＣＥによっては使用者（reaching use）を解析できず、コードを削除することができない。
【０００６】
図７は、オブジェクト指向言語によるプログラムのメソッド呼び出しの一例を示す図である。
図７に示すプログラムの部分は、オブジェクト参照ｖが定義され（v's def）、その使用（use）がオブジェクトｖをレシーバとするメソッドmtd1の呼び出しである（v's use）場合を表す。この例では、メソッドmtd1はオブジェクトｖのインスタンス変数i1に値１を代入してメソッドmtd2を呼び、メソッドmtd2はオブジェクトｖのインスタンス変数i2に値２を代入する。
この場合、オブジェクトｖのインスタンス変数に値を代入した結果が、他で使用されない場合であっても、当該オブジェクトｖがメソッドmtd1呼び出しに使われているので、ＤＣＥでは削除されない。
【０００７】
図７に示したオブジェクトｖのインスタンス変数i1、i2への値の代入計算の結果は、共に使用されない。すなわちdead storeであり、この代入計算は無駄な計算である。
しかしながら、実際にオブジェクトを使用しない場合であっても、メソッド呼び出しのために見かけ上は使用されるように見え、さらにオブジェクトへの書き込みがグローバル扱いされるため、ＤＣＥによる最適化単独では、上記のような無駄な計算を削除できない。
【０００８】
そこで本発明は、メソッド呼び出しを無視すれば使用者（reaching use）がないようなオブジェクト参照の定義を対象とし、そのオブジェクトを操作する計算を削除する最適化方法を実現することを目的とする。
【０００９】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、次のように構成されたプログラム変換方法として実現される。すなわち、このプログラム変換方法は、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するプログラム変換方法であって、メモリから処理対象である実行プログラムを読み出し、この実行プログラム中のメソッド呼び出しに関して、このメソッド呼び出し中のオブジェクト参照の使用が、オブジェクトの要素が活用されない引数であるかどうかを調べるステップと、この実行プログラム中の所定のメソッド呼び出しに関して、このメソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されない引数である場合に、デッドコードエリミネーションにより、このメソッド呼び出しにおける所定のコードを消去するステップと、コードを消去された実行プログラムをメモリに格納するステップとを含むことを特徴とする。
【００１０】
さらに好ましくは、このプログラム変換方法は、デッドコードエリミネーションによりメソッド呼び出しのコードを消去するステップに先立って、当該メソッド呼び出しをインライン展開するステップ、及び当該メソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化するステップをさらに含む。
【００１１】
また、本発明による他のプログラム変換方法は、メモリから処理対象である実行プログラムを読み出し、この実行プログラム中の所定のメソッド呼び出しをインライン展開する第１のステップと、インライン展開されたメソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化する第２のステップと、第１、第２のステップが施された実行プログラムに対してデッドコードエリミネーションを実行する第３のステップと、デッドコードエリミネーションを施された実行プログラムをメモリに格納する第４のステップとを含むことを特徴とする。
【００１２】
さらに好ましくは、このプログラム変換方法は、実行プログラム中のメソッド呼び出しに関して、当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されない引数であり、かつ実行プログラム中の所定のメソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化しない場合に、当該メソッド呼び出しを前記インライン展開の対象として決定するステップをさらに含む。
【００１３】
さらにまた、上記の目的を達成する本発明は、次のように構成されたコンピュータ装置として実現される。すなわち、オブジェクト指向プログラミング言語で記述された実行プログラムのソースコードを読み込み、機械語コードに変換するコンピュータ装置において、メソッド呼び出しにおけるオブジェクト参照の使用の状態に基づいて、処理対象となるメソッド呼び出しを決定する処理対象抽出部と、この処理対象抽出部により処理対象として決定されたメソッド呼び出しをインライン展開するインライン展開処理部と、このインライン展開処理部にてインライン展開されたメソッド呼び出しにおけるオブジェクトのインスタンス変数をスカラー化するスカラー化処理部と、インライン展開処理部及びスカラー化処理部による処理が施された実行プログラムに対してデッドコードエリミネーションを実行するデッドコードエリミネーション実行部とを備えることを特徴とする。
【００１４】
ここで、詳しくは、処理対象抽出部は、実行プログラム中の所定のメソッド呼び出しに関して、このメソッド呼び出しが当該メソッド呼び出し中のオブジェクト参照をグローバル化せず、かつ当該メソッド呼び出し中の全てのオブジェクト参照の使用が、オブジェクトの要素が活用されない引数である場合に、このメソッド呼び出しを処理対象として決定する。
実行プログラム中の所定のメソッドが上記の条件に合致するかについては、コード解析部を設けてプログラム変換時に解析を行うことにより調べても良いし、予め実行プログラムの各メソッドについて解析を行って結果をデータベースに格納しておき、プログラム変換時にこのデータベースから必要な情報を読み出すようにしても良い。さらに、予め上記の条件に合致するようなメソッドを人為的に定義してデータベースに格納しておき、プログラム変換時にこのデータベースを参照することもできる。
【００１５】
上記のコンピュータ装置は、機械語コードに変換された実行プログラムを実行するプログラム実行部をさらに備える構成とすることもできる。
さらにまた、本発明は、コンピュータを制御して上述したプログラム変換方法や各種の機能を実現するプログラムとして実現することができる。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
【００１６】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
まず、本発明の概要を説明する。オブジェクト参照の使用（use）が、オブジェクトの要素が活用されないメソッド呼び出しの引数であって、かつオブジェクト参照がメソッド呼び出しでグローバル化（エスケープ）しない場合、その使用（use）をファントムユース（phantom use）と呼ぶことにする。
【００１７】
本発明では、あるコードが定義するオブジェクトの使用がファントムユースのみであると解析できたとき、そのファントムユースのメソッド呼び出しをインライン展開する。次に、そのオブジェクトの各インスタンス変数をスカラー化する。そしてＤＣＥ（dead code elimination）を行う。これにより、グローバルに他へ影響を及ぼす計算、あるいは計算結果が使用される計算を残し、計算結果が使用されない計算だけが削除される。
【００１８】
図１は、本実施の形態による最適化方法を実現するコンピュータシステムのシステム構成を示す図である。
図１を参照すると、本実施の形態におけるコンピュータシステムは、ソースプログラム（入力コード）をコンパイルするコンパイラ１００と、コンパイラ１００にてコンパイルされたオブジェクトプログラム（出力コード）を実行して種々の処理を行うプログラム実行部２００と、メモリ３００とを備える。コンパイラ１００及びプログラム実行部２００は、パーソナルコンピュータやワークステーションなどのコンピュータシステムにおけるプログラム制御されたＣＰＵにて実現される。メモリ３００は、コンピュータ装置のメインメモリであり、ＲＡＭ等で実現される。メモリ３００には、本実施の形態で用いられるファントムユースデータベース３１０が格納される。また、図示しないが、ＣＰＵを制御してコンパイラ１００として動作させるためのプログラムやコンパイルの対象となるプログラムが格納される。なお、メモリ３００に格納されるファントムユースデータベース３１０及びプログラムは、必要に応じて、適宜磁気ディスクその他の記録媒体に保存されることは言うまでもない。
【００１９】
図１において、コンパイラ１００は、バイトコード（byte code）で記述された入力コードを入力して処理し、機械語で記述された出力コードを生成して出力する。この入力コードの入力は、コード生成装置４００にて生成された入力コードを直接入力したり、コード生成装置４００にて生成された入力コードを記憶した記憶装置５００から入力したり、ネットワーク６００上に存在するコード生成装置４００や記憶装置５００からネットワーク６００を介して入力したりすることにより行われる。コンパイラ１００により生成された出力コードは、プログラム実行部２００により実行される。
なお、本実施の形態において、コンパイラ１００は、ＪａｖａにおけるＪＩＴ（Just In Time）コンパイラのような、実行プログラムを実行する際に動的に実行プログラムのコンパイル処理を行うコンパイラであっても良いし、ソースプログラムを予めコンパイルして生成されたオブジェクトプログラムを実行プログラムとする使用形態におけるコンパイラであっても良い。
【００２０】
図２は、本実施の形態におけるコンパイラ１００の構成を説明する図である。図２を参照すると、コンパイラ１００は、本実施の形態による最適化の対象となるメソッド呼び出しを抽出する処理対象抽出部１１０と、処理対象抽出部１１０にて利用されるファントムユースに関する情報を解析するファントムユース解析を行うファントムユース解析部１２０と、メソッド呼び出しのインライン展開を行うインライン展開処理部１３０と、オブジェクト構造体のスカラー化を行うスカラー化処理部１４０と、デッドコードエリミネーション（ＤＣＥ）を行うＤＣＥ実行部１５０とを備える。
図２に示したコンパイラ１００の各構成要素は、コンピュータプログラムにより制御されたＣＰＵにて実現される仮想的なソフトウェアブロックである。ＣＰＵを制御する当該コンピュータプログラムは、ＣＤ−ＲＯＭやフロッピーディスクなどの記録媒体に格納して配布したり、ネットワークを介して伝送したりすることにより提供される。
なお、図２に示したコンパイラ１００の構成要素は、本実施の形態における特徴的な機能に関するものである。図示しないが、実際にはコンパイラ１００は、入力コードの字句解析や構文解析、機械語のコード生成、各種の最適化処理といったコンパイル処理における一般的な機能を有することは言うまでもない。
【００２１】
上記構成において、処理対象抽出部１１０は、メモリ３００からコンパイル対象であるプログラムを読み込み、当該プログラム中から、本実施の形態において最終的にＤＣＥによる最適化を行う対象となるメソッド呼び出しを抽出する。具体的には、データフロー解析によりオブジェクトの使用（use）を特定すると共に、エスケープ解析（Escape Analysis）によりメソッド呼び出しがオブジェクトをグローバル化するかどうかを調べ、オブジェクトの使用（use）がファントムユースのみであれば、当該メソッド呼び出しを最適化の対象とする。そして、最適化の対象とされたメソッド呼び出しについての情報をインライン展開処理部１３０に渡す。なお、処理対象抽出部１１０に読み込まれるプログラムは、オブジェクトコード（実行可能コード）に変換され、必要な最適化処理が施されたものである。
【００２２】
本実施の形態では、オブジェクト構造体定義に対して当該定義を参照してメソッド呼び出しを行うとき、メソッド呼び出しが当該オブジェクトをグローバル化（エスケープ）させず、かつオブジェクト構造体の要素の定義だけを行う場合、すなわちそのメソッド呼び出しにおけるオブジェクト参照をファントムユースするだけの場合に注目する。グローバル化するメソッドかどうかは、エスケープ解析を活用して識別することができる。エスケープ解析において、グローバル化せず、プログラムのある地点で定義されたオブジェクト構造体の各要素に関して、当該要素の使用（use）がファントムユースのみであると解析できたとき、そのファントムユースのメソッド呼び出しが、本実施の形態による最適化の対象である。
【００２３】
ここで、ファントムユースについて、さらに詳細に説明する。
まず、所定のメソッドｍの呼び出し（コールサイト）ｃｓに引数ｐ（要素ベクタ）を渡すとき、メソッドｍの引数ｐに関する使用セットｕｓ（ｍ，ｐ）を次の数１式に示すように定義する。
【数１】
0003813087.tif 000002
【００２４】
また、メソッドＭのコールサイトｃｓの引数ｐに関する到達使用セットｒｕｓ（Ｍ，ｃｓ，ｐ）を次の数２式に示すように定義する。
【数２】
0003813087.tif 000003
【００２５】
以上のように定義された使用セットｕｓ（ｍ，ｐ）及び到達使用セットｒｕｓ（Ｍ，ｃｓ，ｐ）に基づき、ファントムユースは次のように定義される。
所定のメソッドＭが含むコールサイト集合をＣＳ（Ｍ）とし、そのうちの所定の要素ｃｓに関して、当該要素ｃｓに渡される引数ｐについてｄｓ（ｔ（ｃｓ），ｐ）のｐid＝１かつｒｕｓ（Ｍ，ｃｓ，ｐ）のｐiu＝１であるならば、引数ｐのｉ番目の要素をｃｓのファントムユースと呼ぶ。ここで、ｔ（ｃｓ）は、コールサイトｃｓから呼ばれるメソッドあるいはその全ての候補メソッドである。
【００２６】
上記の定義に基づいて、ファントム関数phantom(pi,f)は、プログラム地点ｆにおいて引数ｐのｉ番目の要素がファントムユースであるとき値１を返し、それ以外では値０を返す。処理対象抽出部１１０は、コンパイル対象であるメソッドＭの引数ｐで示される各オブジェクト構造体（以下、オブジェクト構造体ｐとも記述する）の定義に対し、到達する使用（use）の各地点ｆに関して、ファントム関数phantom(pi,f)が返す値を調べる。
したがって、メソッドＭにおいて、オブジェクト構造体ｐの定義がグローバル化せず、その使用（use）が全てファントムユースであるとき、当該メソッドＭは、後のインライン展開、スカラー化及びＤＣＥの処理対象となる。
【００２７】
ファントムユース解析部１２０は、上述したプログラム地点ｆにおける引数ｐのｉ番目の要素がファントムユースか否かを調べるコード解析手段であり、ファントム関数phantom(pi,f)の値１または値０を返す処理を実行する。この解析処理により得られた１または０の値が、処理対象抽出部１１０による上記の処理で使われる。
なお、ファントムユース解析部１２０による解析処理は、コンパイル時に処理対象抽出部１１０による上記の動作に伴って実行しても良いが、コンパイルとは別処理としてコード解析のみを単独で実行することも可能である。この場合、得られた解析結果は、メモリ３００のファントムユースデータベース３１０に格納され、コンパイル時に処理対象抽出部１１０によって読み出され、使用される。
【００２８】
また、ファントム関数の値をコード解析によって得るのではなく、プログラムの作成に際して予め定義して与えることも可能である。この場合、プログラマ等により定義されたファントム関数の値がメモリ３００のファントムユースデータベース３１０に格納され、使用される。したがって、このような実施態様ではファントムユース解析部１２０は必須の構成要件ではなくなる。
さらにこの場合、メソッド呼び出しの削除の効果に関して静的な解析や実行履歴の保存などによりプログラム実行前に分かる情報や、プログラム実行中に得られるプロファイル情報により、削除効果の高いメソッドを選んでインライン展開の対象とし、最適化を行うこととすれば、コンパイル資源を節約することができる。
【００２９】
インライン展開処理部１３０は、処理対象抽出部１１０にて最適化の対象とされたメソッド、すなわち、オブジェクト構造体ｐの定義がグローバル化せず、その使用（use）が全てファントムユースであるようなメソッドをメモリ３００から入力し、インライン展開する。インライン展開されたコードは、スカラー化処理部１４０に渡される。
【００３０】
スカラー化処理部１４０は、インライン展開処理部１３０にてインライン展開されたメソッドにおけるオブジェクト定義をスカラー化する。オブジェクト定義をスカラー化されたコードは、ＤＣＥ実行部１５０に渡される。
【００３１】
ＤＣＥ実行部１５０は、インライン展開及びスカラー化がなされたメソッドをＤＣＥにより消去する。ＤＣＥによる最適化が行われたコードは、コンパイラ１００によるコンパイルの結果であるオブジェクトプログラムとしてメモリ３００に格納される。
【００３２】
図３は、上記のように構成された本実施の形態のコンパイラ１００による最適化処理の流れを説明するフローチャートである。また、図４は、オブジェクト指向言語によるプログラムの所定のメソッド呼び出しに対して本実施の形態による最適化処理を実行した様子を示す図である。
図４に示すプログラムの部分において、オブジェクト参照ｖが定義され（v's def）、その使用（use）がオブジェクトｖをレシーバとするメソッドmtd1の呼び出しである（v's use）。メソッドmtd1はオブジェクトｖのインスタンス変数i1に値１を代入してメソッドmtd2を呼び、メソッドmtd2はオブジェクトｖのインスタンス変数i2に値２を代入する。したがって、このオブジェクトｖのインスタンス変数に値を代入した結果が、他で使用されない場合であっても、当該オブジェクトｖがメソッドmtd1呼び出しに使われているので、従来の単純なＤＣＥでは削除されない。なお、以下の説明では、オブジェクトｖは図４に示した部分以外では使用されていないものとする。
【００３３】
図３を参照すると、本実施の形態では、まず処理対象抽出部１１０が図４に示したメソッドＭの命令列を入力する（ステップ３０１）。そして、入力された命令列中で、未処理のオブジェクトの定義点を探す（ステップ３０２）。未処理のオブジェクトの定義点が存在するならば、次に当該命令列中で、当該定義点が到達する使用点の集合を探す（ステップ３０３、３０４）。そのような到達使用点の集合が存在しなければ、当該定義点については処理済みと判断してステップ３０２へ戻り、未処理の他のオブジェクトの定義点を探す（ステップ３０５）。
【００３４】
一方、当該定義点が到達する使用点の集合が存在するならば、次に処理対象抽出部１１０は、ファントムユース解析部１２０を用いて、当該集合中で、使用点と当該使用点が参照するオブジェクト要素の組のそれぞれに関して、ファントム関数が値１を返すかどうかを調べる（ステップ３０５、３０６）。そして、少なくとも１つの使用点とオブジェクト要素の組について、
条件「そのオブジェクト要素の全ての使用点でファントム関数が値１を返す」
が満たされるならば、上記の条件を満たす使用点とオブジェクト要素の組を、インライン展開の対象であるメソッド呼び出し点としてメモリ３００の所定の領域に登録する（ステップ３０７、３０８）。そして、ステップ３０２に戻り、未処理の他のオブジェクトの定義点を探す。
また、上記の条件を満足する使用点とオブジェクト要素の組が１つも存在しない場合は、当該定義点については処理済みと判断してステップ３０２へ戻り、未処理の他のオブジェクトの定義点を探す（ステップ３０７）。
【００３５】
ステップ３０２において、全てのオブジェクトの定義点についてステップ３０３移行の処理を実行したと判断されたならば、処理対象抽出部１１０からインライン展開処理部１３０へ処理が移行する。
インライン展開処理部１３０は、ステップ３０８においてメモリ３００に格納された登録内容に基づき、登録されているオブジェクト要素のオブジェクトを使って呼び出されるメソッドをインライン展開する（ステップ３０９）。このインライン展開により、図４に示すように、多段のメソッド呼び出しが１つのメソッド内のコードに書き換えられる。
【００３６】
次に、スカラー化処理部１４０が、ステップ３０８においてメモリ３００に格納された登録内容に基づき、登録されたオブジェクト要素のオブジェクト定義をスカラー化する（ステップ３１０）。このスカラー化により、図４に示すように、オブジェクト定義がローカル化される。
【００３７】
最後に、ＤＣＥ実行部１５０が、処理対象であったメソッドＭを含むプログラムに対してＤＣＥによるコード消去を行う（ステップ３１１）。図４に示すように、単純なＤＣＥでは消去できなかったオブジェクトｖに関するコードが、ステップ３１０までの処理によりインライン展開されスカラー化されたことによって消去される。
【００３８】
次に、具体的なオブジェクトに対する最適化の例を示す。
オブジェクト参照の定義で典型的なものに、newによる、オブジェクトの生成がある。
図５は、このnewによるクラスSampleClassのインスタンス生成に対して本実施の形態による最適化を実行した様子を示す図である。
図５に示す例は、クラスSampleClassのインスタンス生成によりオブジェクト参照ｖが定義され、その使用（use）がオブジェクトｖをレシーバとするメソッドmtd1の呼び出しである場合を表す。ここで、メソッドmtd1はオブジェクトｖのインスタンス変数i1に値１を代入してメソッドmtd2を呼び、メソッドmtd2はオブジェクトｖのインスタンス変数i2に値２を代入する。オブジェクトｖがメソッドmtd1呼び出しに使われているので、従来の単純なＤＣＥでは何も削除しない。
【００３９】
本実施の形態では、処理対象抽出部１１０において、データフロー解析によりinvoke v.mtd1(I)Vコードだけがオブジェクトｖの使用（use）と分かる。また、エスケープ解析によりメソッドmtd1はオブジェクトｖをグローバル化しないと分かる。結果として、オブジェクトｖの使用（use）はファントムユースのみであることが分かる。そこで、処理対象抽出部１１０により、これらのメソッド呼び出しが最適化の対象とされる。そして、図５に示すように、インライン展開処理部１３０によりメソッドmtd1及びメソッドmtd2がインライン展開され、スカラー化処理部１４０によりスカラー化が行われる。各スカラー編集への代入はデッドストアであるので、ＤＣＥ実行部１５０により削除される。以上のようにして、無駄なコードを削除できた。
【００４０】
図６は、図５と同じく、newによるクラスSampleClassのインスタンス生成に対して本実施の形態による最適化を実行した様子を示す図であるが、ここではメソッドmtd2が副作用を持つ例を示す。
この場合も、オブジェクトｖがメソッドmtd1呼び出しに使われているので、従来の単純なＤＣＥでは何も削除しない。
本実施の形態では、メソッドmtd2において、オブジェクトｖのインスタンス変数i2に値２を代入すると共に、グローバル変数であるclass_vを１つカウントアップする。
【００４１】
処理対象抽出部１１０において、データフロー解析によりinvoke v.mtd1(I)Vコードだけがオブジェクトｖの使用（use）と分かり、エスケープ解析によりメソッドmtd1はオブジェクトｖをグローバル化しないと分かり、結局オブジェクトｖの使用（use）はファントムユースのみであると分かる。したがって、処理対象抽出部１１０によりメソッドmtd1及びメソッドmtd2が最適化の対象とされ、インライン展開処理部１３０によりメソッドmtd1及びメソッドmtd2をインライン展開し、スカラー化処理部１４０によりスカラー化を行う。そして、デッドストアであるスカラー編集への代入部分が、ＤＣＥ実行部１５０により削除される。
【００４２】
一方、class_vを１つカウントアップするコードは、newで生成されたオブジェクトの変数ではなく、外部から観測できるコードであるため、デッドストアとならず、消去対象とはならない。
すなわち、本実施の形態によれば、インライン展開されたコード中に、static変数あるいは他オブジェクトへの代入などグローバル値に関する計算や、使用者（reaching use）がある計算、すなわちデッドストアとならない計算が存在する場合、当該計算は消去されずに残り、使用されない結果に関する無駄な計算だけが削除されることとなる。
【００４３】
【発明の効果】
以上説明したように、本発明によれば、メソッド呼び出しを無視すれば使用者（reaching use）がないようなオブジェクト参照の定義を対象とし、そのオブジェクトを操作する計算を削除する最適化方法を実現することができる。
【図面の簡単な説明】
【図１】  本実施の形態による最適化方法を実現するコンピュータシステムのシステム構成を示す図である。
【図２】  本実施の形態におけるコンパイラの構成を説明する図である。
【図３】  本実施の形態のコンパイラによる最適化処理の流れを説明するフローチャートである。
【図４】  オブジェクト指向言語によるプログラムの所定のメソッド呼び出しに対して本実施の形態による最適化処理を実行した様子を示す図である。
【図５】  newによるクラスSampleClassのインスタンス生成に対して本実施の形態による最適化を実行した様子を示す図である。
【図６】  newによる他のクラスSampleClassのインスタンス生成に対して本実施の形態による最適化を実行した様子を示す図であり、メソッドmtd2が副作用を持つ例を示す。
【図７】  オブジェクト指向言語によるプログラムのメソッド呼び出しの一例を示す図である。
【符号の説明】
１００…コンパイラ、１１０…処理対象抽出部、１２０…ファントムユース解析部、１３０…インライン展開処理部、１４０…スカラー化処理部、１５０…ＤＣＥ（デッドコードエリミネーション）実行部、２００…プログラム実行部、３００…メモリ、３１０…ファントムユースデータベース、４００…コード生成装置、５００…記憶装置、６００…ネットワーク
【図１】
0003813087.tif 000004
【図２】
0003813087.tif 000005
【図３】
0003813087.tif 000006
【図４】
0003813087.tif 000007
【図５】
0003813087.tif 000008
【図６】
0003813087.tif 000009
【図７】
0003813087.tif 000010