(57)【要約】【課題】本発明は、全てのコールグラフ・エッジを見渡すこと無しに、コールグラフのプロファイル情報のみから大域的に費用対効果の高い被呼び出しメソッドをインラインすることを目的とする。【解決手段】本発明はインライニングのための技法であって、コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出すること、ここで呼び出し頻度の総数に対する上記被呼び出しメソッドの呼び出し頻度の比を効果として、及び、インライン可能なコードの合計サイズに対する上記被呼び出しメソッドのコード・サイズの比を費用として、上記費用対効果比を算出することを含み；当該費用対効果比を所定の閾値と比較して、上記被呼び出しメソッドをインラインするかを判定すること；及び、上記判定するステップでインラインすると決定した場合に上記被呼び出しメソッドをインラインすることを含む。【選択図】  図３Ａ
2015184737.tif 000002
【特許請求の範囲】
【請求項１】
インライニングのための方法であって、コンピュータが、
コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出するステップであって、呼び出し頻度の総数に対する前記被呼び出しメソッドの呼び出し頻度の比を効果として、及び、インライン可能なコードの合計サイズに対する前記被呼び出しメソッドのコード・サイズの比を費用として、前記費用対効果比を算出するステップを含む、前記算出するステップと、
前記費用対効果比を所定の閾値と比較して、前記被呼び出しメソッドをインラインするかを判定するステップと、
前記判定するステップでインラインすると決定した場合に前記被呼び出しメソッドをインラインするステップと
を実行することを含む、前記方法。
【請求項２】
前記コンピュータが、
インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、前記算出するステップ、前記判定するステップ及び前記インラインするステップを繰り返すステップ
をさらに実行することを含む、請求項１に記載の方法。
【請求項３】
被呼び出しメソッドへのコールサイト数が所定の閾値以上である場合には、又は、
被呼び出しメソッドのコード・サイズが所定の閾値以上である場合には、
当該被呼び出しメソッドがインラインされない、請求項１又は２に記載の方法。
【請求項４】
前記インラインするステップが、
被呼び出しメソッドへのコールサイト数が１である場合には、当該被呼び出しメソッドをインラインするステップ
を含む、請求項１又は２に記載の方法。
【請求項５】
前記コンピュータが、
プロファイル情報の収集時に、前記呼び出し頻度及び前記インライン可能なコードのサイズそれぞれを積算して、前記呼び出し頻度の総数及び前記インライン可能なコードの合計サイズを算出するステップ
をさらに実行することを含む、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記コンピュータが、
第１のメソッドが第２のメソッドを呼び出し且つ前記第２のメソッドが第３のメソッドを呼び出す多段のコールシーケンスにおいて、前記第２のメソッドをインラインすることを決定し且つさらに前記第３のメソッドをインラインするかを判定するときに、前記第２のメソッドへのコールサイトが前記第１のメソッドを含めて複数存在する場合は、前記第２のメソッドから前記第３のメソッドへの呼び出し頻度を、前記第１のメソッドから前記第２のメソッドへの呼び出し頻度と、前記第２のメソッドへの前記コールサイトの全てからの呼び出し頻度の総数との比を用いて修正するステップ
をさらに実行することを含む、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記費用対効果比を算出するステップが、
コールグラフ上でコンパイル対象のメソッドから到達可能なエッジである被呼び出しメソッドに対して、インラインの費用対効果比を算出するステップを含む、請求項１に記載の方法。
【請求項８】
前記コンピュータが、
あるメソッドから被呼び出しメソッドへの呼び出しを検出するステップと、
（１）前記コールグラフに前記呼び出しメソッドに対応するノードが存在しない場合には、前記呼び出しメソッドに対応する当該ノードを当該コールグラフに追加するステップと、
（２）前記コールグラフに前記被呼び出しメソッドに対応するノードが存在しない場合には、前記被呼び出しメソッドに対応する当該ノードを当該コールグラフに追加するステップと、
（３）前記コールグラフに前記呼び出しメソッドから前記被呼び出しメソッドに到達可能なエッジが存在しない場合には、当該エッジを当該コールグラフに追加するステップと、
（４）前記被呼び出しメソッドの呼び出し頻度をインクリメントするステップと、
（５）前記呼び出し頻度の総数をインクリメントするステップと、
（６）前記（３）のエッジの追加に応じて前記インライン可能なコードの合計サイズを更新するステップと
をさらに実行することを含む、請求項７に記載の方法。
【請求項９】
前記費用対効果比を算出するステップが、
前記効果に対する前記費用の比を算出するステップ
を含み、
前記インラインするステップが、
前記費用対効果比が所定の閾値以上である場合に、前記被呼び出しメソッドをインラインするステップ
を含む、請求項１に記載の方法。
【請求項１０】
前記費用対効果比を算出するステップが、
前記費用に対する前記効果の比を算出するステップ
を含み、
前記インラインするステップが、
前記費用対効果比が所定の閾値未満である場合に、前記被呼び出しメソッドをインラインするステップ
を含む、請求項１に記載の方法。
【請求項１１】
前記コンピュータが、
コンパイル対象のメソッドから呼び出される全ての被呼び出しメソッドの集合から、1つの被呼び出しメソッドを取り出すステップ
を実行することを含み、
前記算出するステップが、前記取り出した被呼び出しメソッドについて行われる、請求項１に記載の方法。
【請求項１２】
インライニングを実行するためのコンピュータであって、
コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出する算出手段であって、呼び出し頻度の総数に対する前記被呼び出しメソッドの呼び出し頻度の比を効果として、及び、インライン可能なコードの合計サイズに対する前記被呼び出しメソッドのコード・サイズの比を費用として、前記費用対効果比を算出する前記算出手段と、
前記費用対効果比を所定の閾値と比較して、前記被呼び出しメソッドをインラインするかを判定する判定手段と、
前記判定手段がインラインすると決定した場合に前記被呼び出しメソッドをインラインするインライン手段と
を備えている、前記コンピュータ。
【請求項１３】
前記算出手段が、
インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、前記費用対効果比の算出を繰り返し、且つ、
前記判定手段及び前記インライン手段がそれぞれ、
前記費用対効果比の算出に応じて、前記判定すること及び前記インラインすることを繰り返す、
請求項１２に記載のコンピュータ。
【請求項１４】
前記インライン手段が、
被呼び出しメソッドへのコールサイト数が所定の閾値以上である場合には、又は、
被呼び出しメソッドのコード・サイズが所定の閾値以上である場合には、
当該被呼び出しメソッドをインラインしない、請求項１２又は１３に記載のコンピュータ。
【請求項１５】
前記インライン手段が、
被呼び出しメソッドへのコールサイト数が１である場合には、当該被呼び出しメソッドをインラインする、請求項１２又は１３に記載のコンピュータ。
【請求項１６】
前記算出手段が、
インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、前記費用対効果比を算出する、
請求項１２に記載のコンピュータ。
【請求項１７】
前記算出手段が、
第１のメソッドが第２のメソッドを呼び出し且つ前記第２のメソッドが第３のメソッドを呼び出す多段のコールシーケンスにおいて、前記第２のメソッドをインラインすることを決定し且つさらに前記第３のメソッドをインラインするかを判定するときに、前記第２のメソッドへのコールサイトが前記第１のメソッドを含めて複数存在する場合は、前記第２のメソッドから前記第３のメソッドへの呼び出し頻度を、前記第１のメソッドから前記第２のメソッドへの呼び出し頻度と、前記第２のメソッドへの前記コールサイトの全てからの呼び出し頻度の総数との比を用いて修正する、
請求項１２に記載のコンピュータ。
【請求項１８】
前記算出手段が、
コールグラフ上でコンパイル対象のメソッドから到達可能なエッジである被呼び出しメソッドに対して、インラインの費用対効果比を算出する、
請求項１２に記載のコンピュータ。
【請求項１９】
あるメソッドから被呼び出しメソッドへの呼び出しを検出する検出手段と、
コールグラフ更新手段であって、
（１）前記コールグラフに前記呼び出しメソッドに対応するノードが存在しない場合には、前記呼び出しメソッドに対応する当該ノードを当該コールグラフに追加し、
（２）前記コールグラフに前記被呼び出しメソッドに対応するノードが存在しない場合には、前記被呼び出しメソッドに対応する当該ノードを当該コールグラフに追加し、
（３）前記コールグラフに前記呼び出しメソッドから前記被呼び出しメソッドに到達可能なエッジが存在しない場合には、当該エッジを当該コールグラフに追加する、
前記コールグラフ更新手段と
をさらに備えており、
前記算出手段は、さらに
前記被呼び出しメソッドの呼び出し頻度をインクリメントし、
前記呼び出し頻度の総数をインクリメントし、
前記（３）のエッジの追加に応じて前記インライン可能なコードの合計サイズを更新する、
請求項１８に記載のコンピュータ。
【請求項２０】
インライニングのためのコンピュータ・プログラムであって、請求項１〜１１のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイラの技術に関する。特には、本発明は、コンパイラの最適化の一手法であるインライニング（inlining）に関する。
【背景技術】
【０００２】
インライニングはインライン展開（Inline expansion）又はインライン関数展開（Inline function expansion）とも呼ばれ、コンパイラにおける最重要とされる最適化手法の1つである。インライニングは、関数を呼び出す側に呼び出される関数のコードを展開し、関数への制御転送をしないようにして最適化する手法である。
【０００３】
関数のインライニングは、コーディング時に、例えばinlineキーワードのような指定をソースコードに挿入することによって行われる。
【０００４】
インライニングにより、例えば、（１）コール／リターンに伴うオーバーヘッドの削減、（２）コンパイラによる最適化範囲の拡大、及び（３）コードの空間的局所性の向上、を図ることが可能になる。また、インライニングは、特に、小さくて頻繁に呼び出される関数では効果的である。
【０００５】
コンパイラは、デフォルトでは、コードをインライン展開すべきかどうかを自動的に決定しうる。
【０００６】
下記特許文献１は、制御フロー解析手段の解析結果に基づいて制御フローを構成する各部分制御フローの実行回数を推測し、その実行回数に基づいて各部分制御フローに対する重み付けを行う制御フロー重み付け手段と、この制御フロー重み付け手段による重み付けの結果を参照して各関数呼出しによって呼び出される関数のインライン展開の要否を決定し、その決定を反映したオブジェクトプログラムを生成するオブジェクト生成手段とを有することを特徴とするインライン展開による最適化を行うコンパイラを記載する（請求項１）。
【０００７】
下記特許文献２は、プログラミング言語で記述された原始プログラムを計算機やプロセッサが実行可能な言語で記述された目的プログラムに変換するプログラム変換方法において、原始プログラムを目的プログラムに変換する過程で得られる手続、関数、あるいはサブルーチンに関する情報に基づいて、プログラム上のある箇所で前記手続、関数、あるいはサブルーチンの識別情報が特定の変数に代入され、他の箇所でその変数を用いて当該手続、関数、あるいはサブルーチンが間接的に呼び出される間接呼出のコードを、プログラム上のある箇所で前記手続、関数、あるいはサブルーチンが直接呼び出される直接呼出のコードに変更して、目的プログラムを生成することを特徴とするプログラム変換方法を記載する（請求項１）。
【０００８】
下記特許文献３は、ソースコードに含まれる関数の少なくとも一部をインライン展開することなく、前記ソースコードをオブジェクトコードに翻訳するステップと、前記オブジェクトコードに対して選択的に変更を加えるステップと、
前記オブジェクトコードを実行し、前記関数の少なくとも一部の呼び出し回数と処理時間を測定するステップと、前記呼び出し回数と処理時間を参照して、前記ソースコードに含まれる前記関数の少なくとも一部を選択的にインライン展開するステップとからなることを特徴とするインライン展開方法を記載する（請求項１）。
【０００９】
下記特許文献４は、複数の命令セットを有するＣＰＵに係るコード最適化方法において、対象とするプログラムコードのコストをコスト評価表に基づいて計算し、その計算結果を保持するコスト計算ステップと、この保持された計算結果から最適な命令セットを選択する最適命令セット選択ステップと、を有することを特徴とするコード最適化方法（請求項２）、及び、前記コスト計算ステップは、前記プログラムコードをインライン展開し、そのインライン展開されたプログラムコードのコストをコスト評価表に基づいて計算し、その計算結果を保持すること（請求項５）を記載する。
【００１０】
下記特許文献５は、コンピュータ上で動作し、関数呼出しを含む原始プログラムを目的コードに変換するプログラムであって、インライン展開の対象となる関数に対し、同一関数の呼出しが複数箇所にわたって存在する場合に、前記呼出しの位置からの分岐命令を用いることにより呼出し先関数の展開コードを共用することを特徴とするコンパイルプログラムを記載する（請求項１）。
【００１１】
下記非特許文献１〜４それぞれは、静的コンパイラにおけるインライニング手法を記載する。
【００１２】
下記非特許文献５〜９それぞれは、動的コンパイラにおけるインライニング手法を記載する。
【００１３】
下記非特許文献１０は、テンペラチャー（temperature）・ヒューリスティクスに基づくインライン手法を記載する。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開平６−２０２８７５号公報
【特許文献２】特開平１１−２１２７９７号公報
【特許文献３】特開２００１−１８８６８１号公報
【特許文献４】特開平１１−３０６０２６号公報
【特許文献５】特開２００４−６２２３４号公報
【非特許文献】
【００１５】
【非特許文献１】D. R. Chakrabarti and S. Liu, “Inline Analysis: Beyond Selection Heuristics”, Proceedings of the International Symposium on Code Generation and Optimization, pages 221 - 232, 2006
【非特許文献２】O. Beohm, D. Citron, G. Harber, M. Klausner, and R. Levin, “IBM Research Report, Aggressive Function Inlining with Global Code Reordering”, Computer Science, H-0247 (H0611-009), November 15, 2006＜http://domino.watson.ibm.com/library/cyberdig.nsf/papers/6F80F6035401CC598525723C0057E605/$File/h-0247.pdf＞から入手可能
【非特許文献３】P. P. Chang and W.-W. Hwu, “Inline function expansion for compiling C programs”, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language designand implementation, pages 246 - 257, 1989
【非特許文献４】P. P. Chang, S. A. Mahlke, W. Y. Chen, and W. W. Hwu, “Profile-guided automatic inline expansion for C programs”, Software Practice and Experience”, Vol. 22(5), pages 349 - 369, May 1992＜http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9668&rep=rep1&type=pdf＞から入手可能
【非特許文献５】J. Cavazos and M. F.P. O’Boyle, “Automatic Tuning of Inlining Heuristics”, Proceedings of the 2005 ACM/IEEE SC Conference, page 14, November 2005
【非特許文献６】K. Hazelwood and D. Grove, “Adaptive Online Context-Sensitive Inlining”, Proceedings of the international symposium on Code generation and optimization”, feedback-directed and runtime optimization, pages 253- 264, 2003＜http://www.cs.virginia.edu/kim/docs/cgo03.pdf＞から入手可能
【非特許文献７】M. Arnold, S. Fink, V. Sarkar, and P. Sweeney, “A comparativestudy of static and dynamic heuristics for inlining”, ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization, 2000＜http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.7186&rep=rep1&type=pdf＞から入手可能
【非特許文献８】S. Kulkarni, J. Cavazos, C. Wimmer, and D. Simon, “Automatic construction of inlining heuristics using machine learning”, Proceedings of the 2013IEEE/ACM International Symposium on Code Generation and Optimization, 2013＜http://www.eecis.udel.edu/~skulkarn/papers/cgo-2013.pdf＞から入手可能
【非特許文献９】T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani, “Design and Evaluation of Dynamic Optimizations for a Java Just-In-Time Compiler”, ACM Transactions on Programming Languages and Systems, Vol. 27, No. 4, pages 732 - 785, July 2005
【非特許文献１０】P. Zhao and J. N. Amaral, “To Inline or Not to Inline ? Enhanced Inlining Decision”,16th Workshop on Languages and Compilers for Parallel Computing, 2003＜http://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&frm=1&source=web&cd=1&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.researchgate.net%2Fpublication%2F221497026_To_Inline_or_Not_to_Inline_Enhanced_Inlining_Decisions%2Ffile%2F60b7d51892d0a082f7.pdf&ei=_ZwKU7XAOMWikwXvwYDYDg&usg=AFQjCNEysiMuj5RT7VB4ZRwv-_GV0Q5cIQ&sig2=LbMW44b7yDsA3SFztZAMgw&bvm=bv.61725948,d.dGI＞から入手可能
【発明の概要】
【発明が解決しようとする課題】
【００１６】
インライニングは、コンパイラにおける最重要な最適化手法の1つである。インライニングを効果的に行うためには、当該インライニングの利益（特には、例えば、呼び出し頻度）と当該インライニングの費用（コストでもある）（インライン対象の被呼び出しメソッドのコード・サイズ）とがトレードオフの関係にあるために、当該利益及び当該費用を考慮する必要がある。従って、インライニングにより得られる利益が高く且つ費用の低いメソッドから優先的にインラインする必要がある。
【００１７】
種々のインライニング手法についての費用対効果を見積もる技術として、上記非特許文献１〜１０がある。
【００１８】
非特許文献１〜４それぞれに記載の静的コンパイラにおけるインライニング手法では、コンピュータは、コールグラフ・プロファイルを取得し、費用対効果を被呼び出しメソッド・サイズに対する呼び出し頻度から算出し、当該費用対効果の大きいコールグラフ・エッジから順にインライニングし、そしてインライン・サイズ（すなわち、インラインしたコード・サイズ）が閾値（当該閾値は、インライニングするコード全体に対して適用される）に達した時点でインライニングを終了する。しかしながら、当該静的コンパイラにおけるインライニング手法では、コールグラフが大きい場合に、全てのコールグラフ・エッジを見渡して費用対効果の高いエッジを見つけるのでコンパイル・コスト（すなわち、コンパイル時間）が増加する。従って、当該静的コンパイラにおけるインライニング手法は、動的コンパイラには不向きである。また、当該静的コンパイラにおけるインライニング手法において、上記費用対効果は相対的な指標であるために、他のエッジの値との比較が必要である。
【００１９】
非特許文献５〜９それぞれに記載の動的コンパイラにおけるインライニング手法では、コンピュータは、コールグラフ・プロファイルを取得し、費用対効果を当該被呼び出しメソッドのサイズに対する呼び出し頻度から算出し、コンパイル対象のメソッドをルート（根）とする部分的なコールグラフにおいて、上記算出された費用対効果の高いエッジからインライニングし、そしてインライン・サイズが閾値（当該閾値は、各コンパイル・メソッドに対して適用される）に達した時点でインライニングを終了する。しかしながら、当該動的コンパイラにおけるインライニング手法では、コンパイル・メソッドごとに上記閾値を適用する。従って、当該動的コンパイラにおけるインライニング手法は、大域的に費用対効果の大きい被呼び出しメソッドをインラインし損なう可能性がある。また、当該動的コンパイラにおけるインライニング手法において、上記費用対効果は相対的な指標であるために、他のエッジの値との比較が必要である。
【００２０】
非特許文献１０に記載のテンペラチャー・ヒューリスティクスによる手法（静的コンパイラ向けである）では、インライニングの利益とコストを正規化することにより、コールグラフ・エッジ間の比較をせずに（すなわち、全てのコールグラフ・エッジを見渡すこと無しに）、インライン対象のエッジを選出する。当該テンペラチャー・ヒューリスティクスによる手法では、インラインの利益を見積もる際に被呼び出しメソッドの実行サイクル数を用いている。しかしながら、当該実行サイクルの取得には高いコストが必要である。従って、当該テンペラチャー・ヒューリスティクスによる手法は、プロファイル情報の収集に要するコストが高く動的コンパイラには不向きである。
【００２１】
そこで、本発明は、全てのコールグラフ・エッジを見渡すこと無しに、当該コールグラフのプロファイル情報のみから大域的に費用対効果の高い被呼び出しメソッドをインラインすることを目的とする。
【課題を解決するための手段】
【００２２】
本発明は、インライニングのための技法を提供する。当該技法は、上記インライニングのための方法、並びに、当該インライニングを可能にするコンピュータ、コンピュータ・プログラム及びコンピュータ・プログラム製品を包含しうる。
【００２３】
特には、本発明は、上記インライニングによる最適化を行うコンパイラに関する。本発明は、上記コンパイラを備えたコンピュータ、コンピュータ・プログラム及びコンピュータ・プログラム製品を包含しうる。
【００２４】
（本発明に従う第１の態様）
【００２５】
本発明に従う第１の態様において、インライニングのための方法は、コンピュータが、
コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出するステップであって、呼び出し頻度の総数に対する上記被呼び出しメソッドの呼び出し頻度の比を効果として、及び、インライン可能なコードの合計サイズに対する上記被呼び出しメソッドのコード・サイズの比を費用として、上記費用対効果比を算出するステップを含む、上記算出するステップと、
上記費用対効果比を所定の閾値と比較して、上記被呼び出しメソッドをインラインするかを判定するステップと、
上記判定するステップでインラインすると決定した場合に上記被呼び出しメソッドをインラインするステップと
を実行することを含む。
【００２６】
本発明の一つの実施態様において、上記コンピュータが、
コンパイル対象のメソッドから呼び出される全ての被呼び出しメソッドの集合から、1つの被呼び出しメソッドを取り出すステップ
を実行することを含みうる。そして、上記算出するステップが、上記取り出した被呼び出しメソッドについて行われうる。
【００２７】
本発明の一つの実施態様において、上記コンピュータが、
インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、上記算出するステップ、上記判定するステップ及び上記インラインするステップを繰り返すステップ
をさらに実行することを含みうる。
【００２８】
本発明の一つの実施態様において、上記コンピュータが、
プロファイル情報の収集時に、上記呼び出し頻度及び上記インライン可能なコードのサイズそれぞれを積算して、上記呼び出し頻度の総数及び上記インライン可能なコードの合計サイズを算出するステップ
をさらに実行することを含みうる。
【００２９】
本発明の一つの実施態様において、上記コンピュータが、
第１のメソッドが第２のメソッドを呼び出し且つ上記第２のメソッドが第３のメソッドを呼び出す多段のコールシーケンスにおいて、上記第２のメソッドをインラインすることを決定し且つさらに上記第３のメソッドをインラインするかを判定するときに、上記第２のメソッドへのコールサイトが上記第１のメソッドを含めて複数存在する場合は、上記第２のメソッドから上記第３のメソッドへの呼び出し頻度を、上記第１のメソッドから上記第２のメソッドへの呼び出し頻度と、上記第２のメソッドへの上記コールサイトの全てからの呼び出し頻度の総数との比を用いて修正するステップ
をさらに実行することを含みうる。
【００３０】
本発明の一つの実施態様において、上記費用対効果比を算出するステップが、
コールグラフ上でコンパイル対象のメソッドから到達可能なエッジである被呼び出しメソッドに対して、インラインの費用対効果比を算出するステップを含み、上記コンピュータが、
あるメソッドから被呼び出しメソッドへの呼び出しを検出するステップと、
（１）上記コールグラフに上記呼び出しメソッドに対応するノードが存在しない場合には、上記呼び出しメソッドに対応する当該ノードを当該コールグラフに追加するステップと、
（２）上記コールグラフに上記被呼び出しメソッドに対応するノードが存在しない場合には、上記被呼び出しメソッドに対応する当該ノードを当該コールグラフに追加するステップと、
（３）上記コールグラフに上記呼び出しメソッドから上記被呼び出しメソッドに到達可能なエッジが存在しない場合には、当該エッジを当該コールグラフに追加するステップと、
（４）上記被呼び出しメソッドの呼び出し頻度をインクリメントするステップと、
（５）上記呼び出し頻度の総数をインクリメントするステップと、
（６）上記（３）のエッジの追加に応じて上記インライン可能なコードの合計サイズを更新するステップと
をさらに実行することを含みうる。
【００３１】
本発明の一つの実施態様において、上記費用対効果比を算出するステップが、上記効果に対する上記費用の比を算出するステップを含みうる。また、上記インラインするステップが、上記費用対効果比が所定の閾値以上である場合に、上記被呼び出しメソッドをインラインするステップを含みうる。
【００３２】
本発明の一つの実施態様において、上記費用対効果比を算出するステップが、上記費用に対する上記効果の比を算出するステップを含みうる。また、上記インラインするステップが、上記費用対効果比が所定の閾値未満である場合に、上記被呼び出しメソッドをインラインするステップを含みうる。
【００３３】
本発明の一つの実施態様において、上記コンピュータは、
被呼び出しメソッドへのコールサイト数が所定の閾値以上である場合には、又は、
被呼び出しメソッドのコード・サイズが所定の閾値以上である場合には、
当該被呼び出しメソッドがインラインされないようにしうる。
【００３４】
本発明の一つの実施態様において、上記コンピュータは、被呼び出しメソッドへのコールサイト数が１である場合には、当該被呼び出しメソッドをインラインされるようにしうる。
【００３５】
（本発明に従う第２の態様）
【００３６】
本発明に従う第２の態様において、インライニングを実行するためのコンピュータが、
コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出する算出手段であって、呼び出し頻度の総数に対する上記被呼び出しメソッドの呼び出し頻度の比を効果として、及び、インライン可能なコードの合計サイズに対する上記被呼び出しメソッドのコード・サイズの比を費用として、上記費用対効果比を算出する上記算出手段と、
上記費用対効果比を所定の閾値と比較して、上記被呼び出しメソッドをインラインするかを判定する判定手段と、
上記判定手段がインラインすると決定した場合に上記被呼び出しメソッドをインラインするインライン手段と
を備えている。
【００３７】
本発明の一つの実施態様において、上記算出手段が、
コールグラフ上でコンパイル対象のメソッドから到達可能なエッジである被呼び出しメソッドに対して、インラインの費用対効果比を算出しうる。
【００３８】
本発明の一つの実施態様において、
上記算出手段が、インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、上記算出を繰り返し、且つ、
上記判定手段及び上記インライン手段がそれぞれ、上記費用対効果比の算出に応じて、上記判定すること及び上記インラインすることを繰り返しうる。
【００３９】
本発明の一つの実施態様において、上記算出手段が、
インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、上記費用対効果比を算出しうる。
【００４０】
本発明の一つの実施態様において、上記算出手段が、
第１のメソッドが第２のメソッドを呼び出し且つ上記第２のメソッドが第３のメソッドを呼び出す多段のコールシーケンスにおいて、上記第２のメソッドをインラインすることを決定し且つさらに上記第３のメソッドをインラインするかを判定するときに、上記第２のメソッドへのコールサイトが上記第１のメソッドを含めて複数存在する場合は、上記第２のメソッドから上記第３のメソッドへの呼び出し頻度を、上記第１のメソッドから上記第２のメソッドへの呼び出し頻度と、上記第２のメソッドへの上記コールサイトの全てからの呼び出し頻度の総数との比を用いて修正しうる。
【００４１】
本発明の一つの実施態様において、上記コンピュータが、
あるメソッドから被呼び出しメソッドへの呼び出しを検出する検出手段と、
コールグラフ更新手段であって、
（１）上記コールグラフに上記呼び出しメソッドに対応するノードが存在しない場合には、上記呼び出しメソッドに対応する当該ノードを当該コールグラフに追加し、
（２）上記コールグラフに上記被呼び出しメソッドに対応するノードが存在しない場合には、上記被呼び出しメソッドに対応する当該ノードを当該コールグラフに追加し、
（３）上記コールグラフに上記呼び出しメソッドから上記被呼び出しメソッドに到達可能なエッジが存在しない場合には、当該エッジを当該コールグラフに追加する、
上記コールグラフ更新手段と
をさらに備えうる。
【００４２】
本発明の一つの実施態様において、上記算出手段は、さらに
上記被呼び出しメソッドの呼び出し頻度をインクリメントし、
上記呼び出し頻度の総数をインクリメントし、
上記（３）のエッジの追加に応じて上記インライン可能なコードの合計サイズを更新しうる。
【００４３】
本発明の一つの実施態様において、上記インライン手段が、
被呼び出しメソッドへのコールサイト数が所定の閾値以上である場合には、又は、
被呼び出しメソッドのコード・サイズが所定の閾値以上である場合には、
当該被呼び出しメソッドがインラインされないようにしうる。
【００４４】
本発明の一つの実施態様において、上記インライン手段が、
被呼び出しメソッドへのコールサイト数が１である場合には、当該被呼び出しメソッドをインラインしうる。
【００４５】
（本発明に従う第３の態様）
【００４６】
本発明に従う第３の態様において、インライニングのためのコンピュータ・プログラム又はコンピュータ・プログラム製品は、コンピュータに、上記第１の態様に記載の方法の各ステップを実行させる。
【００４７】
本発明の実施態様に従うコンピュータ・プログラムはそれぞれ、一つ又は複数のフレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ＢＤ、ハードディスク装置、ＵＳＢに接続可能なメモリ媒体、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。当該コンピュータ・プログラムは、上記記録媒体への格納のために、通信回線で接続する他のコンピュータ、例えばサーバ・コンピュータからダウンロードしたり、又は他の記録媒体から複製したりすることができる。また、本発明の実施態様に従うコンピュータ・プログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。また、様々な形態で、本発明の実施態様に従うコンピュータ・プログラム製品を提供することも勿論可能であることにも留意されたい。本発明の実施態様に従うコンピュータ・プログラム製品は、例えば、上記コンピュータ・プログラムを記録した記憶媒体、又は、上記コンピュータ・プログラムを伝送する伝送媒体を包含しうる。
【００４８】
本発明の上記概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーション又はサブコンビネーションもまた、本発明となりうることに留意すべきである。
【００４９】
本発明の実施態様において使用されるコンピュータの各ハードウェア構成要素を、複数のマシンと組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００５０】
また、本発明は、ハードウェア、ソフトウェア、又は、ハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアとの組み合わせによる実行において、上記コンピュータ・プログラムのインストールされたコンピュータにおける実行が典型的な例として挙げられる。かかる場合、当該コンピュータ・プログラムが当該コンピュータのメモリにロードされて実行されることにより、当該コンピュータ・プログラムは、当該コンピュータを制御し、本発明にかかる処理を実行させる。当該コンピュータ・プログラムは、任意の言語、コード、又は、表記によって表現可能な命令群から構成されうる。そのような命令群は、当該コンピュータが特定の機能を直接的に、又は、１．他の言語、コード若しくは表記への変換及び、２．他の媒体への複製、のいずれか一方若しくは双方が行われた後に、本発明の実施態様に従う処理を実行することを可能にするものである。
【発明の効果】
【００５１】
本発明の実施態様に従うと、コンピュータは、インラインの費用対効果を呼び出し頻度の情報のみから算出し、全てのコールグラフ・エッジを見渡すこと無しに、大域的に費用対効果の高い被呼び出しメソッドをインラインすることが可能であるために、小さいプロファイル・オーバヘッド及び少ないコンパイル時間をもたらし、従って効率的なインラインが可能になる。
【図面の簡単な説明】
【００５２】
【図１】本発明の実施態様に従う又は本発明の実施態様において使用されうるコンピュータの一例を示した図である。
【図２】本発明の実施態様において使用されうるコールグラフの例を示す。
【図３Ａ】本発明の実施態様に従うインライニング処理の為のフローチャートであり、特に、被呼び出しメソッドをインラインする為のフローチャートを示す。
【図３Ｂ】本発明の実施態様に従うインライニング処理の為のフローチャートであり、特に、プロファイル情報を更新する処理の為のフローチャートを示す。
【図４】本発明の実施態様において求められうる費用対効果比を可視化したグラフである。
【図５】本発明の実施態様に従い、多段のコールシーケンスを有するコールグラフにおいて呼び出し頻度を修正することを説明する為に示したコールグラフの例である。
【図６】図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従い被呼び出しメソッドをインラインする為のインライニング処理を実行するコンピュータの機能ブロック図の一例を示した図である。
【発明を実施するための形態】
【００５３】
本発明の実施形態を、以下に図面に従って説明する。以下の図を通して、特に断らない限り、同一の符号は同一の対象を指す。本発明の実施形態は、本発明の好適な態様を説明するためのものであり、本発明の範囲をここで示すものに限定する意図はないことを理解されたい。
【００５４】
本発明の実施態様において使用されうるコンピュータは、インライニングすることができるコンピュータであれば特に限定されない。当該コンピュータは例えば、例えば、メインフレーム・コンピュータ、サーバ・コンピュータ、デスクトップ・コンピュータ、ノート・コンピュータ若しくは一体型パソコン、又は、タブレット端末若しくはスマートフォン（例えば、Ｗｉｎｄｏｗｓ（登録商標）、アンドロイド（登録商標）又はｉＯＳを搭載したタブレット端末若しくスマートフォン）でありうる。
【００５５】
図１は、本発明の実施態様に従う又は本発明の実施態様において使用されうるコンピュータの一例を示した図である。
【００５６】
コンピュータ（１０１）は、ＣＰＵ（１０２）とメイン・メモリ（１０３）とを備えており、これらはバス（１０４）に接続されている。ＣＰＵ（１０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものである。当該ＣＰＵ（１０２）は例えば、インテル社のＣｏｒｅ（商標）  ｉシリーズ、Ｃｏｒｅ（商標）  ２シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（登録商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ若しくはＣｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ（Advanced Micro Devices）社のＡシリーズ、Ｐｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（登録商標）シリーズ若しくはＳｅｍｐｒｏｎ（商標）、又は、インターナショナル・ビジネス・マシーンズ・コーポレーションのＰｏｗｅｒ（商標）シリーズでありうる。
【００５７】
バス（１０４）には、ディスプレイ・コントローラ（１０５）を介して、ディスプレイ（１０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。また、液晶ディスプレイ（ＬＣＤ）は例えば、タッチパネル・ディスプレイ又はフローティング・タッチ・ディスプレイであてもよい。ディスプレイ（１０６）は、コンピュータ（１０１）上で動作中のソフトウェア（例えば、本発明の実施態様に従うコンピュータ・プログラム又は当該コンピュータ（１０１）上で動作中の各種コンピュータ・プログラム）が稼働することによって表示されるオブジェクトを、適当なグラフィック・インタフェースで表示するために使用されうる。
【００５８】
バス（１０４）には任意的に、例えばＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ディスク（１０８）、例えばハードディスク又はソリッド・ステート・ドライブ（ＳＳＤ）が接続されうる。
【００５９】
バス（１０４）には任意的に、例えばＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ドライブ（１０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブが接続されうる。
【００６０】
バス（１０４）には、周辺装置コントローラ（１１０）を介して、例えばキーボード・マウス・コントローラ又はＵＳＢバスを介して、任意的に、キーボード（１１１）及びマウス（１１２）が接続されうる。
【００６１】
ディスク（１０８）には、オペレーティング・システム、例えばｚ／ＯＳ（登録商標）、ｚ／ＶＭ（登録商標）、ｚ／ＶＳＥ（登録商標）、ｚ／ＴＰＦ、ＶＯＳ３、ＵＮＩＸ（登録商標）、Ｗｉｎｄｏｗｓ（登録商標）、ＭａｃＯＳ（登録商標）、及びＪ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、本発明の実施態様に従うコンピュータ・プログラム、及びその他のプログラム、並びにデータが、メイン・メモリ（１０３）にロード可能なように記憶されうる。
【００６２】
ディスク（１０８）は、コンピュータ（１０１）内に内蔵されていてもよく、当該コンピュータ（１０１）がアクセス可能なようにケーブルを介して接続されていてもよく、又は、当該コンピュータ（１０１）がアクセス可能なように有線又は無線ネットワークを介して接続されていてもよい。
【００６３】
ドライブ（１０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラム、例えばオペレーティング・システム、アプリケーション又は本発明の実施態様に従うコンピュータ・プログラムをディスク（１０８）にインストールするために使用されうる。
【００６４】
通信インタフェース（１１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１１４）は、通信コントローラ（１１３）を介してバス（１０４）に接続され、コンピュータ（１０１）を通信回線（１１５）に有線又は無線接続する役割を担い、コンピュータ（１０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は例えば、無線ＬＡＮ接続規格に基づく無線ＬＡＮ環境、ＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどのＷｉ−Ｆｉ無線ＬＡＮ環境、又は携帯電話網環境（例えば、３Ｇ又は４Ｇ環境）でありうる。
【００６５】
図２は、本発明の実施態様において使用されうるコールグラフの例を示す。
【００６６】
コールグラフはマルチグラフとも呼ばれ、コンピュータ・プログラムのメソッド同士の呼び出し関係を表現した有向グラフである。コールグラフは、一般的には、各ノードが手続きを表現し、各エッジ（Ａ，Ｂ）は手続きＡが手続きＢを呼び出すことを示す。
【００６７】
本発明の実施態様において使用されうるコールグラフにおいて、メソッドがノードに対応し、メソッド呼び出しがエッジに対応する。当該コールグラフは、動的又は静的のいずれでもありうる。
【００６８】
本発明の実施態様において使用されうるコールグラフは、コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出する際に使用されうる。
【００６９】
図２に示すコールグラフ（２０１）は、メソッドＡ、メソッドＢ、メソッドＣ、メソッドＤ及びメソッドＥそれぞれに対応するノード（２１１、２１２、２１３、２１４及び２１５）、並びに、メソッドＡからメソッドＢへの呼び出し、メソッドＢらメソッドＣへの呼び出し、メソッドＤからメソッドＢへの呼び出し及びメソッドＥらメソッドＢへの呼び出しそれぞれに対応するエッジ（２２１、２２２、２２３及び２２４）を有している。
【００７０】
例えばメソッドＢからメソッドＣへの呼び出しにおいて、メソッドＢは呼び出し（caller）メソッドであり、メソッドＣはメソッドＢから到達可能な被呼び出しメソッド（callee）である。
【００７１】
また、メソッドＢに対して、メソッドＡ、メソッドＤ及びメソッドＥは、コールサイトとも呼ばれる。
【００７２】
図３Ａ及び図３Ｂは、本発明の実施態様に従うインライニング処理の為のフローチャートを示す。
【００７３】
図３Ａは、本発明の実施態様に従い、被呼び出しメソッドをインラインする為のフローチャートを示す。
【００７４】
ステップ３０１において、コンピュータ（３０１）は、インライニングの対象となる言語のソースコードについて、コンパイラを使用して、コンパイル処理を開始する。当該コンパイラは、静的コンパイラ又は動的コンパイラのいずれであってもよい。コンピュータ（３０１）は、当該コンパイル処理中の最適化処理において、本願発明の実施態様に従う上記インライニング処理を開始する。
【００７５】
本発明の実施態様において使用されるインライニングの対象となる言語は例えば、オブジェクト指向言語（例えば、Ｃ＋＋、Ｊａｖａ（登録商標））、又は関数自体が小さい関数型言語であるがこれらに限定されるものではない。
【００７６】
ステップ３０２において、コンピュータ（３０１）は、コンパイル対象の１つのメソッドから呼び出されうる全ての被呼び出しメソッドの集合Ｓｃａｌｌｅｅｓを取得する。コンピュータ（３０１）は、当該集合Ｓｃａｌｌｅｅｓを、例えばコールグラフから取得しうる。
【００７７】
ステップ３０３において、コンピュータ（３０１）は、ステップ３０３で取得した集合Ｓｃａｌｌｅｅｓに下記ステップ３０５の処理が未処理の被呼び出しメソッドが残っているかを判断する。コンピュータ（３０１）は、上記未処理の被呼び出しメソッドが残っていることに応じて、処理をステップ３０４に進める。一方、コンピュータ（３０１）は、上記未処理の被呼び出しメソッドが残っていないことに応じて、処理をステップ３０８に進める。
【００７８】
ステップ３０４において、コンピュータ（３０１）は、集合Ｓｃａｌｌｅｅｓから、上記未処理の被呼び出しメソッドＭｃａｌｌｅｅを１つ取り出す。
【００７９】
ステップ３０５において、コンピュータ（３０１）は、下記式に従い、ステップ３０４で取り出した被呼び出しメソッドＭｃａｌｌｅｅに対して、インラインの費用対効果比（GIER: Global Inlining Efficiency Ratio）（すなわち、被呼び出しメソッドＭｃａｌｌｅｅをインラインすることの費用対効果比」）を算出する。コンピュータ（３０１）は、当該ＧＩＥＲの算出において、コールグラフを使用しうる。コンピュータ（３０１）は、当該ＧＩＥＲを、エッジ（すなわち、被呼び出しメソッドＭｃａｌｌｅｅ）毎に算出する。
【００８０】
GIER＝FrequencyRatio(edge)とSizeRatio(edge)との比
【００８１】
FrequencyRatio(edge)は(Fcaller-callee / Ftotal)から算出され、すなわち、呼び出し頻度の総数（Ftotal；TotalFrequency）に対する被呼び出しメソッドＭｃａｌｌｅｅの呼び出し頻度（Fcaller-callee；Frequency(edge)）の比である。FrequencyRatio(edge)は、上記費用対効果比の「効果」に該当する。
【００８２】
SizeRatio(edge)は、(Scallee / Stotal)から算出され、すなわち、インライン可能なコードの合計サイズ（Stotal；TotalInlineSize）に対する被呼び出しメソッドのコード・サイズ（Scallee；CalleeSize(edge））の比である。SizeRatio(edge)は、上記費用対効果比の「費用」に該当する。
【００８３】
また、コンピュータ（３０１）は、任意的に、インライン可能なコードの合計サイズ（Stotal；TotalInlineSize）として、例えば下記に示す式に従い算出されるコールグラフ・サイズを用いることが可能である。代替的には、コンピュータ（３０１）は、任意的に、インライン可能なコードの合計サイズとして、ユーザがある定数を与えてもよい。
【００８４】
下記式において、インライン可能なコードの合計サイズ（Stotal）は、チューニング・パラメータである。インライン可能なコードの合計サイズ（Stotal）として下記に示す式に従い動的に算出される値を用いることで、高い費用対効果を得ることが可能であることが実際の実装実験により判っている。
【００８５】
【数１】
2015184737.tif 000003
【００８６】
ＧＩＥＲは、上記式に示す通り、プロファイル情報の呼び出し頻度の情報のみから算出されるために、全てのコールグラフ・エッジを見渡す必要がない。また、ＧＩＥＲは、絶対的な指標である為に、他のエッジ（すなわち、被呼び出しメソッド）との比較が不要である。
【００８７】
コンピュータ（３０１）は、任意的に、上記式に従って算出されたＧＩＥＲを下記（１）〜（３）のいずれか１つに示すヒューリスティックスに従い変更しうる。当該変更は、ＧＩＥＲを使用したアルゴリズムの効果を更に高めることが可能である。
【００８８】
（１）コンピュータ（３０１）は、被呼び出しメソッドへのコールサイト数をカウントし、当該コールサイト数が所定の閾値以上である場合には、ＧＩＥＲの値を所定の閾値以下にする。すなわち、コンピュータ（３０１）は、ＧＩＥＲの値を所定の閾値以下にして、上記被呼び出しメソッドがインラインされないようにする。上記場合にＧＩＥＲを所定の閾値以下にすることによって、フットプリントの増加を防ぐことが可能になり、結果的に、コンパイラによって変換されたバイナリコードのサイズが大きくならない。
【００８９】
（２）コンピュータ（３０１）は、被呼び出しメソッドのコード・サイズが所定の閾値以上である場合には、ＧＩＥＲの値を所定の閾値以下にする。すなわち、コンピュータ（３０１）は、ＧＩＥＲの値を所定の閾値以下にして、上記被呼び出しメソッドがインラインされないようにする。上記場合にＧＩＥＲを所定の閾値以下にすることによって、フットプリントの増加を防ぐことが可能になり、結果的に、コンパイラによって変換されたバイナリコードのサイズが大きくならない。
【００９０】
（３）コンピュータ（３０１）は、被呼び出しメソッドへのコールサイト数が１である場合には、ＧＩＥＲの値を増加させる（例えば２倍にする）。すなわち、コンピュータ（３０１）は、ＧＩＥＲの値を増加させて、上記被呼び出しメソッドの全てが無条件にインラインされるようにする。上記場合においてＧＩＥＲの値を増加させることによって、フットプリントの増加がない場合のインラインを促進させることが可能になる。
【００９１】
また、コンピュータ（３０１）は、任意的に、下記に示す条件を満たす場合に、上記被呼び出しメソッドＭｃａｌｌｅｅの呼び出し頻度（Fcaller-callee）を変更しうる。すなわち、コンピュータ（３０１）は、第１のメソッドが第２のメソッドを呼び出し且つ当該第２のメソッドが第３のメソッドを呼び出す多段のコールシーケンスにおいて、当該第２のメソッドをインラインすることを決定し且つさらに当該第３のメソッドをインラインするかを判定するときに、当該第２のメソッドへのコールサイトが当該第１のメソッドを含めて複数存在する場合は、当該第２のメソッドから当該第３のメソッドへの呼び出し頻度を、当該第１のメソッドから当該第２のメソッドへの呼び出し頻度と、当該第２のメソッドへの当該コールサイトの全てからの呼び出し頻度の総数との比を用いて修正しうる。当該修正の詳細については、下記図５の説明において詳しく説明する。
【００９２】
ステップ３０６において、コンピュータ（３０１）は、ステップ３０５で算出したＧＩＥＲの値と所定の閾値とを比較する。
【００９３】
コンピュータ（３０１）は、ＧＩＥＲがSizeRatio(edge)に対するFrequencyRatio(edge)の比から算出されている場合には、当該ＧＩＥＲの値が所定の閾値以上であることに応じて上記被呼び出しメソッドＭｃａｌｌｅｅをインラインするために、処理をステップ３０６に進める。一方、コンピュータ（３０１）は、当該場合において、当該ＧＩＥＲの値が所定の閾値未満であることに応じて上記被呼び出しメソッドＭｃａｌｌｅｅをインラインすることなしに、処理をステップ３０３に戻す。
【００９４】
コンピュータ（３０１）は、ＧＩＥＲがFrequencyRatio(edge)に対するFrequencyRatio(edge)の比から算出されている場合には、当該ＧＩＥＲの値が所定の閾値未満であることに応じて、上記被呼び出しメソッドＭｃａｌｌｅｅをインラインするために、処理をステップ３０６に進める。一方、コンピュータ（３０１）は、当該場合において、当該ＧＩＥＲの値が所定の閾値以上であることに応じて上記被呼び出しメソッドＭｃａｌｌｅｅをインラインすることなしに、処理をステップ３０３に戻す。
【００９５】
ステップ３０７において、コンピュータ（３０１）は、上記被呼び出しメソッドＭｃａｌｌｅｅをインラインする。
【００９６】
また、ステップ３０７において、コンピュータ（３０１）は、上記被呼び出しメソッドＭｃａｌｌｅｅからの全ての被呼び出しメソッドを集合Ｓｃａｌｌｅｅｓに追加する。上記被呼び出しメソッドＭｃａｌｌｅｅからの全ての被呼び出しメソッドを集合Ｓｃａｌｌｅｅｓに追加することによって、コンピュータ（３０１）は、当該インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、上記ステップ３０３〜上記ステップ３０７を繰り返す。
【００９７】
コンピュータ（３０１）は、ステップ３０７の処理が終了することに応じて、処理をステップ３０３に戻し、上記ステップ３０３〜３０７を繰り返す。
【００９８】
ステップ３０８において、コンピュータ（３０１）は、コンパイル対象の未処理のメソッドがあるかを判断する。コンピュータ（３０１）は、上記未処理のメソッドがあることに応じて、当該未処理のメソッドについて上記ステップ３０２〜３０７を繰り返す為に処理をステップ３０２に戻す。一方、コンピュータ（３０１）は、上記未処理のメソッドがあることに応じて、処理を終了ステップ３０９に進める。
【００９９】
ステップ３０９において、コンピュータ（３０１）は、インライニングの対象となる言語のソースコードについて、上記コンパイル処理を終了する。
【０１００】
図３Ｂは、プロファイル情報を更新する処理の為のフローチャートを示す。
【０１０１】
ステップ３１１において、コンピュータ（３０１）は、プロファイル情報を更新する処理を開始する。プロファイル情報を更新する処理は、図３Ａに示すインライニング処理と並列に、又は、独立的に行われうる。
【０１０２】
ステップ３１２において、コンピュータ（３０１）は、呼び出しメソッドＭｃａｌｌｅｒから被呼び出しメソッドＭｃａｌｌｅｅへの呼び出しを検出する。
【０１０３】
ステップ３１３において、コンピュータ（３０１）は、ステップ３１２における上記検出が行われる毎に、下記（１）〜（３）に従い、コールグラフを更新する：
（１）上記コールグラフに上記呼び出しメソッドＭｃａｌｌｅｒに対応するノードが存在しない場合には、当該呼び出しメソッドＭｃａｌｌｅｒに対応する当該ノードを当該コールグラフに追加する；
（２）上記コールグラフに上記被呼び出しメソッドＭｃａｌｌｅｅに対応するノードが存在しない場合には、当該被呼び出しメソッドＭｃａｌｌｅｅに対応する当該ノードを当該コールグラフに追加する；及び、
（３）上記コールグラフに上記呼び出しメソッドＭｃａｌｌｅｒから上記被呼び出しメソッドＭｃａｌｌｅｅに到達可能なエッジが存在しない場合には、当該エッジを当該コールグラフに追加する。
【０１０４】
そして、ステップ３１２において、コンピュータ（３０１）は、
被呼び出しメソッドの呼び出し頻度（Fcaller-callee）をインクリメントすること（Fcaller-callee++）（例えば、１インクリメントする）；及び、
呼び出し頻度の総数（Ftotal）をインクリメントすること（Ftotal++）（例えば、１インクリメントする）；及び、
インライン可能なコードの合計サイズ（Stotal）を更新すること、すなわち、StotalにScalleeのコード・サイズを追加すること（Stotal += Scallee）
を行う。
【０１０５】
被呼び出しメソッドの呼び出し頻度（Fcaller-callee）をインクリメントすること（Fcaller-callee++）、及び、呼び出し頻度の総数（Ftotal）をインクリメントすること（Ftotal++）は、いずれも、上記ステップ３１２の上記検出が行われることに応じて行われうる。
【０１０６】
インライン可能なコードの合計サイズ（Stotal）を更新することは、上記（３）に記載のエッジの追加に応じて行われうる。
【０１０７】
インライン可能なコードの更新された合計サイズ（Stotal）、被呼び出しメソッドのインクリメントされた呼び出し頻度（Fcaller-callee）、及び呼び出し頻度のインクリメントされた総数（Ftotal）が、図３Ａに示すステップ３０５で使用される。当該ステップ３０５は、図２Ａに示すフローチャートとは別途に行われる。
【０１０８】
ステップ３１４において、コンピュータ（３０１）は、上記ステップ３１２〜３１３を繰り返すかを判断する。上記ステップ３１２〜３１３を繰り返すかどうかは例えば、呼び出しメソッドＭｃａｌｌｅｒから被呼び出しメソッドＭｃａｌｌｅｅへの呼び出しが所定の時間が経過しても検出されないことで判断されうる。コンピュータ（３０１）は、上記ステップ３１２〜３１３を繰り返すことに応じて、処理をステップ３１２に戻す。一方、コンピュータ（３０１）は、上記ステップ３１２〜３１３を繰り返さないことに応じて、処理を終了ステップ３１２に進める。
【０１０９】
ステップ３１４において、コンピュータ（３０１）は、プロファイル情報を更新する上記処理を終了する。
【０１１０】
図４は、本発明の実施態様において求められうる費用対効果比を可視化したグラフである。
【０１１１】
図４に示すグラフは、Specjvm2008から入手可能なベンチマーク・ソフトウェアから実際に得られるコールグラフにおいて、ＧＩＥＲが大きい順にエッジをソートした際におけるインライン可能なコードのサイズを積算した値（横軸，割合％）及び被呼び出しメソッドの呼び出し頻度を積算した値（縦軸，割合％）を示す。
【０１１２】
本発明の実施態様では、図３Ａに示すフローチャートに記載の通り、インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、ステップ３０５の算出するステップ及びステップ３０７のインラインするステップを繰り返す。
【０１１３】
ＧＩＥＲは、図４に示すグラフ上の曲線（４０２）のカーブの傾きで表される。当該カーブの傾きが急であるほど呼び出し頻度が高くてコストが低いことを示すことから、インラインの費用対効果が高いことを示す。従って、カーブの傾きが急であるところをインラインすることによって、インラインの費用対効果が高くなる。
【０１１４】
図４に示す例では、当該コールグラフのエッジ（すなわち、被呼び出しメソッド）の１０％程度をインラインすれば、約９９％以上のメソッド呼び出しを削減することが可能であることがわかる。
【０１１５】
ＧＩＥＲは、上記約１０％のエッジを、全てのコールグラフ・エッジを見渡すこと無しに抽出する為に用いられる。図３Ａのステップ３０６に示す所定のＧＩＥＲ閾値は任意の値でありうる。当該ＧＩＥＲ閾値は例えば、「１」となるように正規化されている。当該ＧＩＥＲ閾値が「１」であることは、上記費用と上記コストとが釣り合っていることを意味する。当該ＧＩＥＲ閾値が「１」であるように正規化されていることで、ＧＩＥＲ閾値を設定することが容易である。
【０１１６】
ＧＩＥＲ閾値として例えば上記した「１」を用いることによって、Specjvm2008から入手可能な多くのベンチマーク・ソフトウェアにおいて、性能が向上することが判った。
【０１１７】
ＧＩＥＲ閾値として「１」よりも小さい値を用いることによって、インラインする割合を多くすることができる。すなわち、コンピュータは、インラインすることに対してアグレッシブ（積極的）になる。一方、ＧＩＥＲ閾値として「１」よりも大きい値を用いることによって、インラインする割合を少なくすることができる。すなわち、コンピュータは、インラインすることに対してコンサーバティブ（保守的）になる。
【０１１８】
図５は、本発明の実施態様に従い、多段のコールシーケンスを有するコールグラフにおいて呼び出し頻度を修正することを説明する為に示したコールグラフの例である。
【０１１９】
図５に示すコールグラフ（５０１）は、図２に示すコールグラフ（２０１）と同じ構造（ノード及びエッジ）を有している。従って、図５に示すコールグラフの説明については、図２に示すコールグラフの説明を参照されたい。
【０１２０】
図５に示すコールグラフ（５０１）では、１段目のメソッドＡ（５１１）が２段目のメソッドＢ（５１２）を呼び出し、且つ、２段目のメソッドＢ（５１２）が３段目のメソッドＣ（５１３）を呼び出す多段のコールシーケンスである。
【０１２１】
２段目のメソッドＢ（５１２）をインラインすることが既に決まっている。そして、コンピュータ（１０１）は、メソッドＣ（５１３）をインラインするかどうかを判定しているとする。コールグラフ（５０１）では、インラインすることが既に決まっているメソッドＢ（５１２）へのコールサイトがメソッドＡ（５１１）を含めて複数存在している。すなわち、メソッドＡ（５１１）に加えて、メソッドＤ（５１４）及びメソッドＥ（５１５）のコールサイトがある。
【０１２２】
上記の様な場合に、コンピュータ（１０１）は、メソッドＢ（５１２）からメソッドＣ（５１３）への呼び出し頻度を、メソッドＡ（５１１）からメソッドＢ（５１２）への呼び出し頻度と、メソッドＢ（５１２）への当該コールサイトの全て（すなわち、メソッドＡ（５１１）、並びに、メソッドＤ（５１４）及びメソッドＥ（５１５））からの呼び出し頻度の総数との比を用いて修正する。当該修正を行うことによって、インラインすることが既に決まっているメソッドＢ（５１２）を通じた呼び出し頻度を見積もることが可能になる。
【０１２３】
上記修正は、下記に示す式に従い行われうる。
【０１２４】
【数２】
2015184737.tif 000004
【０１２５】
以下に、コールグラフ（５０１）の例を用いて、メソッドＢ（５１２）からメソッドＣ（５１３）への呼び出し頻度の修正を説明する。
【０１２６】
メソッドＢ（５１２）からメソッドＣ（５１３）への呼び出し頻度（すなわち、修正する呼び出し頻度である）は、３０％である。メソッドＡ（５１１）からメソッドＢ（５１２）への呼び出し頻度は、１０％である。メソッドＢ（５１２）への当該コールサイトの全て（すなわち、メソッドＡ（５１１）、並びに、メソッドＤ（５１４）及びメソッドＥ（５１５））からの呼び出し頻度の総数は、１０％＋１０％＋１０％＝３０％である。
【０１２７】
従って、メソッドＢ（５１２）からメソッドＣ（５１３）への呼び出し頻度（
2015184737.tif 000005
）は、３０×（１０／３０）＝１０％に修正される。
【０１２８】
図６は、図１に従うコンピュータ（１０１）のハードウェア構成を好ましくは備えており、本発明の実施態様に従い被呼び出しメソッドをインラインする為のインライニング処理を実行するコンピュータの機能ブロック図の一例を示した図である。
【０１２９】
コンピュータ（１０１）は、本発明の実施態様に従い、本発明の実施態様に従い被呼び出しメソッドをインラインする為のインライニング処理を実行するコンピュータであり、例えば図１に示すコンピュータ（１０１）でありうる。
【０１３０】
コンピュータ（１０１）は、コンパイル手段（６１１）を備えている。
【０１３１】
コンパイル手段（６１１）は、フロントエンド手段（６２１）及び最適化手段（６２２）を備えている。最適化手段（６２２）は、本発明の実施態様に従い追加された下記手段、すなわち、算出手段（６３１）、判定手段（６３２）、インライン手段（６３３）、コールグラフ更新手段（６３５）及び検出手段（６３４）を備えている。
【０１３２】
フロントエンド手段（６２１）は、字句解析部、構文解析部、及び意味解析部を備えている。フロントエンド手段（６２１）は、記憶媒体（例えば、図１に示す記憶媒体（１０８））からソースコード（６０１）を入手する。フロントエンド手段（６２１）は、当該入手したソースコードについて、従来技術と同様の方法で、字句解析、構文解析及び意味解析を行い、コンパイラ中間テキストを出力する。
【０１３３】
算出手段（６３１）は、コンパイル対象のメソッドから到達可能な被呼び出しメソッドに対して、インラインの費用対効果比を算出する。算出手段（６３１）は、記憶媒体（例えば、図１に示す記憶媒体（１０８））からプロファイル情報（６０３）を取り出して、当該費用対効果比を、呼び出し頻度の総数に対する上記被呼び出しメソッドの呼び出し頻度の比を効果として、及び、インライン可能なコードの合計サイズに対する上記被呼び出しメソッドのコード・サイズの比を費用として、算出する。
【０１３４】
また、算出手段（６３１）は、コールグラフ上でコンパイル対象のメソッドから到達可能なエッジである被呼び出しメソッドに対して、インラインの費用対効果比を算出しうる。
【０１３５】
また、算出手段（６３１）は、インラインする被呼び出しメソッドがなくなるまで、インライン済みのメソッドを含むメソッドから到達可能な被呼び出しメソッドに対して、上記費用対効果比の算出を繰り返しうる。
【０１３６】
また、算出手段（６３１）は、第１のメソッドが第２のメソッドを呼び出し且つ上記第２のメソッドが第３のメソッドを呼び出す多段のコールシーケンスにおいて、上記第２のメソッドをインラインすることを決定し且つさらに上記第３のメソッドをインラインするかを判定するときに、上記第２のメソッドへのコールサイトが上記第１のメソッドを含めて複数存在する場合は、上記第２のメソッドから上記第３のメソッドへの呼び出し頻度を、上記第１のメソッドから上記第２のメソッドへの呼び出し頻度と、上記第２のメソッドへの上記コールサイトの全てからの呼び出し頻度の総数との比を用いて修正しうる。
【０１３７】
また、算出手段（６３１）は、
上記被呼び出しメソッドの呼び出し頻度をインクリメントすること；
上記呼び出し頻度の総数をインクリメントすること；及び、
コールグラフ更新手段（６３５）が下記（３）のエッジをコールグラフに追加することに応じてインライン可能なコードの合計サイズを更新すること、
を実行しうる。
【０１３８】
判定手段（６３２）は、算出手段（６３１）が算出した費用対効果比を所定の閾値と比較して、被呼び出しメソッドをインラインするかどうかを判定する。
【０１３９】
インライン手段（６３３）は、判定手段（６３２）でインラインすると決定した場合に、上記被呼び出しメソッドをインラインする。
【０１４０】
また、インライン手段（６３３）は、被呼び出しメソッドへのコールサイト数が所定の閾値以上である場合には、当該被呼び出しメソッドをインラインしないようにしうる。
【０１４１】
また、インライン手段（６３３）は、被呼び出しメソッドのコード・サイズが所定の閾値以上である場合には、当該被呼び出しメソッドをインラインしないようにしうる。
【０１４２】
また、インライン手段（６３３）は、被呼び出しメソッドへのコールサイト数が１である場合には、当該被呼び出しメソッドをインラインしうる。
【０１４３】
コールグラフ更新手段（６３５）は、下記（１）〜（３）の場合に、コールグラフを更新しうる：
（１）上記コールグラフに上記呼び出しメソッドに対応するノードが存在しない場合には、上記呼び出しメソッドに対応する当該ノードを当該コールグラフに追加すること；
（２）上記コールグラフに上記被呼び出しメソッドに対応するノードが存在しない場合には、上記被呼び出しメソッドに対応する当該ノードを当該コールグラフに追加すること；及び、
（３）上記コールグラフに上記呼び出しメソッドから上記被呼び出しメソッドに到達可能なエッジが存在しない場合には、当該エッジを当該コールグラフに追加すること。
【０１４４】
検出手段（６３４）は、あるメソッドから被呼び出しメソッドへの呼び出しを検出する。
【０１４５】
最適化手段（６２２）は、本発明の実施態様に従いインラインされたバイナリコード（６０２）を出力する。
【０１４６】
（実施例）
本発明の実施態様に従うコンピュータ・プログラムをＩＢＭ（登録商標）  Ｊａｖａ（登録商標）  １．７  ＪＩＴ  Ｃｏｍｐｉｌｅｒ  ６４ビットに実装した。
【０１４７】
使用したプラットフォーム環境は、下記の通りである。
プロセッサ：ＩＢＭ（登録商標）  zEC12専用プロセッサ（5.5GHz，４コア）；及び
ＯＳ：ＩＢＭ（登録商標）  ｚ／ＯＳ（登録商標）
【０１４８】
ベンチマーク・ソフトウェアとして、SPECjvm2008から入手可能な１２種のベンチマーク・ソフトウェアを使用した。
【０１４９】
コールグラフのプロファイル情報は、zEC12専用プロセッサのランタイム  インストラクション（ＲＩ，Runtime Instrumentation）を用いたオンラインプロファイラを用いて収集した。当該収集において、オーバーヘッドはほぼゼロである。
【０１５０】
本発明の実施態様に従うＧＩＥＲ（効果（呼び出し頻度の総数に対する被呼び出しメソッドの呼び出し頻度の比）に対する費用（インライン可能なコードの合計サイズに対する被呼び出しメソッドのコード・サイズの比）の比）の値が１を超えるエッジをインライニングした。コンパイル・メソッド毎の閾値は存在しない。
【０１５１】
（比較例１：ベースライン）
ＩＢＭ（登録商標）  Ｊａｖａ（登録商標）  １．７  ＪＩＴ  Ｃｏｍｐｉｌｅｒ  ６４ビットに標準で搭載されているコンパイラのインライニング技法（静的コンパイラにおける手法である）を用いた。インラインするエッジを、コールグラフを使用せずに、基本的にコード・サイズの小さい被呼び出しメソッドからインライニングするヒューリスティックス技法を用いて決定した。コンパイル・メソッド毎にインライン・サイズに対する閾値が存在する。プラットフォーム環境及びベンチマーク・ソフトウェアは、上記実施例と同じである。
【０１５２】
（比較例２）
比較例１の方法にコールグラフを組み合わせたインライニング技法を用いた。インラインするエッジは、コールグラフからのプロファイル情報を用いて、費用対効果比を、被呼び出しメソッドのコード・サイズに対する呼び出し頻度の比として算出し、当該算出した費用対効果比が高い被呼び出しメソッドからインラインを行った。コンパイル・メソッド毎にインライン・サイズに対する閾値が存在する（比較例１と同じである）。プラットフォーム環境及びベンチマーク・ソフトウェアは、上記実施例と同じである。
【０１５３】
（スループット）
実施例のスループットは、比較例１（ベースライン）のスループットに対して、上記１２種のベンチマーク・ソフトウェアにおいて平均３．７％向上し、ベンチマーク・ソフトウェアの種類によっては最大１０．８％の向上が見られた。一方、比較例２のスループットは、比較例１（ベースライン）のスループットよりも低いものが多く見られた。
【０１５４】
（インラインされたコードの相対サイズ）
実施例のインラインされたコードの相対サイズは、比較例１（ベースライン）と比べて、上記１２種のベンチマーク・ソフトウェアでの平均で大幅に減少していた。これは、本発明の実施態様に従うと、費用対効果の小さいインライニングが排除されたためである。一方、比較例２のインラインされたコードの相対サイズは、比較例１（ベースライン）のインラインされたコードの相対サイズよりも小さいが、実施例のインラインされたコードの相対サイズよりも大きかった。これは、比較例２による方法に従うと閾値に余裕が有る限りインラインを続けるために、本発明の実施態様に従う方法よりもインラインしたコード・サイズが大きくなるためである。
【０１５５】
（コンパイル時間）
実施例のコンパイル時間は、比較例１（ベースライン）と比べて、上記１２種のベンチマーク・ソフトウェアでの平均で減少していた。一方、比較例２のコンパイル時間は、比較例１と比べて増加していた。
【図１】
2015184737.tif 000006
【図２】
2015184737.tif 000007
【図３Ａ】
2015184737.tif 000008
【図３Ｂ】
2015184737.tif 000009
【図４】
2015184737.tif 000010
【図５】
2015184737.tif 000011
【図６】
2015184737.tif 000012