(57)【特許請求の範囲】
【請求項１】
コンピュータの処理により、実行対象のプログラムにおけるサブクラステスト関数の実行結果を再利用するプログラムの最適化方法であって、
前記コンピュータが、実行対象のプログラムに含まれるサブクラステスト関数の関数呼び出しから呼び出されるコードの再利用可能性を、該コードにおけるグローバルメモリへのアクセスが、前記関数呼び出しにおいて指定された型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスのみを含むか否かに基づいて判定するステップと、
前記コンピュータが、再利用可能であると判定したコードの実行結果を該コードの関数呼び出しにおいて指定された指定情報と共に、該コードにおいて実際にアクセスされた型情報に関連付けて、前記コードのプロファイル情報として記憶装置に格納するステップと、
前記コンピュータが、再利用可能であると判定したコードを呼び出すサブクラステスト関数の関数呼び出しの検出に応答して、前記記憶装置から前記コードのプロファイル情報を読み出し、該プロファイル情報の指定情報と検出した前記関数呼び出しにおいて指定される指定情報とが一致することを条件に前記プロファイル情報の実行結果を再利用するステップと、
前記コンピュータが、前記記憶装置に格納されるプロファイル情報に含まれる実行結果に関連付けられた型情報を監視して、該型情報に対する変更に応答して前記型情報に関連付けられた実行結果の再利用を禁止するステップと、
を含む最適化方法。
【請求項２】
前記格納するステップにおいて、前記コンピュータは、再利用可能であると判定した前記コードの実行結果と共に、実行時の名前空間を前記コードのプロファイル情報として更に格納し、及び、前記再利用するステップにおいて、前記コンピュータは、検出した前記関数呼び出しが再利用可能であると判定したコードを呼び出すことを、読み出した前記プロファイル情報の名前空間と現在の名前空間の一致により確認する、請求項１に記載の最適化方法。
【請求項３】
前記再利用するステップは、前記コンピュータが、検出した前記関数呼び出しにおいて指定される指定情報が一致することを条件に前記プロファイル情報の実行結果を再利用する再利用コードをコンパイル済みコードとして生成するステップを含む、請求項２に記載の最適化方法。
【請求項４】
前記コンピュータが、事前登録された型情報を操作する操作コードにアクセスし、該操作コードに、再利用する前記実行結果に関連付けられた前記型情報を変更することを条件として前記実行結果を再利用する前記再利用コードを無効化する命令列を挿入するステップを更に含み、前記禁止するステップは、前記命令の実行により行われる、請求項３に記載の最適化方法。
【請求項５】
再利用のために実行結果を格納すべきサブクラステスト関数のコードを、前記コンピュータに組み込まれたデフォルトのサブクラステスト関数のコードに限定する、請求項１に記載の最適化方法。
【請求項６】
前記コンピュータが、前記プロファイル情報として格納される前記実行結果に関連付けられた型情報の変更イベントに対応するリスナーであって、前記変更イベントの発生に応答して変更された前記型情報に対応する前記プロファイル情報を無効化する前記リスナーを生成するステップを更に含み、前記禁止するステップは、前記リスナーの実行により行われる、請求項５に記載の最適化方法。
【請求項７】
前前記コンピュータが、再利用する前記実行結果に関連付けられた型情報の変更イベントに対応するリスナーであって、前記変更イベントの発生に応答して前記実行結果を再利用する前記再利用コードを無効化する前記リスナーを生成するステップを更に含み、前記禁止するステップは、前記リスナーの実行により行われる、請求項６に記載の最適化方法。
【請求項８】
前記判定するステップにおいて、前記コンピュータは、再利用可能性を判定する前記コードからグローバルメモリへのアクセス命令を全て探し出し、探し出した全てのアクセス命令が、前記サブクラステスト関数の関数呼び出しにおいて指定される型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスであることを条件に、前記コードを再利用可能であると静的に判定する、請求項２に記載の最適化方法。
【請求項９】
前記判定するステップにおいて、前記コンピュータは、サブクラステスト関数の関数呼び出しにおいて指定されたオブジェクト及び型情報の値を、再利用可能性を判定する前記コードに伝播させた判定用コードを生成し、生成した判定用コードの実行中になされたグローバルメモリへのアクセスが全て型情報の読み出しのためのアクセスであることを条件に、前記コードを再利用可能であると動的に判定する、請求項２に記載の最適化方法。
【請求項１０】
前記コンピュータが、再利用可能であると判定した前記コードに対し、該コードの実行によりアクセスされる型情報のアドレスを収集するテンプレートを生成するステップを更に含み、前記プロファイル情報は前記テンプレートの実行結果を利用して作成される、請求項２に記載の最適化方法。
【請求項１１】
前記実行対象のプログラムは、Pythonで記述されたソースプログラムからPythonインタプリタにより生成されたバイトコードである、請求項２に記載の最適化方法。
【請求項１２】
コンピュータの処理により、実行対象のプログラムにおけるサブクラステスト関数の実行結果を再利用する最適化プログラムであって、前記最適化プログラムは前記コンピュータに、
実行対象のプログラムに含まれるサブクラステスト関数の関数呼び出しから呼び出されるコードの再利用可能性を、該コードにおけるグローバルメモリへのアクセスが、前記関数呼び出しにおいて指定された型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスのみを含む否かに基づいて判定するステップと、
再利用可能であると判定したコードの実行結果を該コードの呼び出しにおいて指定された指定情報と共に、該コードにおいて実際にアクセスされた型情報に関連付けて、前記コードのプロファイル情報として記憶装置に格納するステップと、
再利用可能であると判定したコードを呼び出すサブクラステスト関数の関数呼び出しの検出に応答して、前記記憶装置から前記コードのプロファイル情報を読み出し、該プロファイル情報の指定情報と検出した前記関数呼び出しにおいて指定される指定情報とが一致することを条件に前記プロファイル情報の実行結果を再利用するステップと、
前記記憶装置に格納されるプロファイル情報に含まれる実行結果に関連付けられた型情報を監視して、該型情報に対する変更に応答して前記型情報に関連付けられた実行結果の再利用を禁止するステップと、
を実行させる、最適化プログラム。
【請求項１３】
実行対象のプログラムにおけるサブクラステスト関数の実行結果を再利用するプログラムの最適化装置であって、
記憶装置と、
実行対象のプログラムに含まれるサブクラステスト関数の関数呼び出しから呼び出されるコードの再利用可能性を、該コードにおけるグローバルメモリへのアクセスが、前記関数呼び出しにおいて指定された型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスのみを含むか否かに基づいて判定する再利用可能性判定部と、
再利用可能であると判定したコードの実行結果を該コードの呼び出しにおいて指定された指定情報と共に、該コードにおいて実際にアクセスされた型情報に関連付けて、前記コードのプロファイル情報として前記記憶装置に格納するプロファイリング部と、  
再利用可能であると判定したコードを呼び出すサブクラステスト関数の関数呼び出しの検出に応答して、前記記憶装置から前記コードのプロファイル情報を読み出し、該プロファイル情報の指定情報と検出した前記関数呼び出しにおいて指定される指定情報とが一致することを条件に前記プロファイル情報の実行結果を再利用する再利用処理部と、
前記記憶装置に格納されたプロファイル情報に含まれる実行結果に関連付けられる型情報を監視して、該型情報に対する変更に応答して前記型情報に関連付けられた前記実行結果の再利用を禁止する監視部と、
を含む最適化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的プログラミング言語の実行環境においてサブクラステスト関数の実行結果を再利用する技術に関する。特に本発明は、プロファイルしたサブクラステスト関数の実行結果を効率的に、また安全に再利用してプログラムの最適化を図る技術に関する。
【背景技術】
【０００２】
オブジェクト指向言語では、あるオブジェクトがあるクラスのインスタンス又はあるクラスのサブクラスのインスタンスであるか否かをテストするサブクラステスト関数がよく利用される。このようなサブクラステスト関数として、例えば、Java（登録商標）言語におけるinstanceof演算子やPythonにおけるisinstance関数が挙げられる。これらは、通常処理や例外処理において、クラスごとに処理を分ける際に使用されている。
【０００３】
サブクラステスト関数は使用頻度が高い一方で調査コストが高いという問題がある。そのためJava（登録商標）言語におけるinstanceof 演算子のように、その動作が言語仕様で１つに決定されるようなサブクラステスト関数については、従来、過去のテスト結果を単純にキャッシュして利用するという最適化アプローチが採用されている（例えば、特許文献１及び特許文献２を参照。）。
【０００４】
また、オブジェクトの型チェックに関する他の技術を開示するものとして特許文献３〜６が存在する。特許文献３は、実行時に仮想動的型チェック(virtual dynamic type check：DTC)関数を各オブジェクトに対して生成し、仮想DTCが、あるオブジェクトの型の階層内の全型の型チェックを行う一連の命令を含み、適合させられた特定の型のオブジェクトに対してより効率的に動的な型チェックを行う技術を開示する。
【０００５】
特許文献４は、複数の関係によって特徴付けられる複数の要素からなるデータセットの表現方法として、各要素にIDと少なくとも１つの要素の他の要素に対する関係を示すインターバルとを割り付ける技術を開示する。
【０００６】
特許文献５は、Java（登録商標）クラスの親のクラスの階層関係を提供するJava（登録商標）クラス階層をクラス参照アレイとして実装する技術を開示する。ここで、クラス参照のアレイはJava（登録商標）コンピュータ環境における型チェックを効率的に実行するのに使用される。
【０００７】
特許文献６は、サブクラスfingerprintを使用してクラスのスーパークラスを追跡し、また、インタフェースfingerprintを使用して、ローカルに宣言されたクラスのインタフェースを追跡する技術を開示する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０００−３９９９７号公報
【特許文献２】米国特許第７２６６８１３号明細書
【特許文献３】米国特許第７０８０３５４号明細書
【特許文献４】米国特許第７００７０３０号明細書
【特許文献５】特開２００３−１８６７７５号公報
【特許文献６】米国特許第７２１６３３３号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１、２が開示するようなテスト結果を単純にキャッシュして再利用する再利用方式や、特許文献３が開示するクラス階層リストの値を埋め込んだcheck関数を生成する技術、また、特許文献４〜６が開示するクラス階層を表現するデータ構造を使用する技術は、その動作が言語仕様で１つに決定されるようなサブクラステスト関数を有するプログラミング言語を対象としているので、Pythonのような、サブクラステスト関数に該当するバイトコードが存在せず呼び出される関数の実体やクラスごとのサブクラスの定義が動的に変わり得る動的プログラミング言語に対して適用することはできない。
【００１０】
この発明は、上記の問題点を解決するためになされたものであって、Pythonのようなサブクラステスト関数に該当するバイトコードが存在せず呼び出される関数の実体やクラスごとのサブクラスの定義が動的に変わり得る動的プログラミング言語に対して、プロファイルしたサブクラステスト関数の実行結果を効率的に、また安全に利用することを可能にするための技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記課題を解決するために、本願発明者は、型情報（クラス情報）は実行時に変化しにくいことに着目し、グローバル情報へのアクセスを、型情報を読み出すためだけに行うサブクラステスト関数のコードをプロファイルし、その実行結果を再利用するとともに、型情報の変更を検出した場合は実行結果の再利用を禁止するというアイデアに想到した。
【００１２】
即ち、上記目的を達成する本発明は、次のような、コンピュータの処理により、実行対象のプログラムにおけるサブクラステスト関数の実行結果を再利用してプログラムを最適化する最適化方法によって実現される。そのような最適化方法は、前記コンピュータが、実行対象のプログラムに含まれるサブクラステスト関数の関数呼び出しから呼び出されるコードの再利用可能性を、該コードにおけるグローバルメモリへのアクセスが、前記サブクラステスト関数の関数呼び出しにおいて指定された型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスのみを含むか否かに基づいて判定するステップと、前記コンピュータが、再利用可能であると判定したコードの実行結果を該コードの呼び出しにおいて指定された指定情報と共に、該コードにおいて実際にアクセスされた型情報に関連付けて、前記コードのプロファイル情報として記憶装置に格納するステップと、前記コンピュータが、再利用可能であると判定したコードを呼び出すサブクラステスト関数の関数呼び出しの検出に応答して、前記記憶装置から前記コードのプロファイル情報を読み出し、プロファイル情報の指定情報が検出した前記関数呼び出しにおいて指定される指定情報と一致することを条件に前記プロファイル情報の実行結果を再利用するステップと、前記コンピュータが、前記記憶装置に格納されるプロファイル情報に含まれる実行結果に関連付けられた型情報を監視して、該型情報に対する変更に応答して前記型情報に関連付けられた実行結果の再利用を禁止するステップと、を含む。
【００１３】
好ましくは、前記格納するステップにおいて、前記コンピュータは、再利用可能であると判定した前記コードの実行結果と共に、実行時の名前空間を前記コードのプロファイル情報として更に格納する。そして、前記再利用するステップにおいて、前記コンピュータは、検出した前記関数呼び出しが再利用可能であると判定したコードを呼び出すことを、読み出した前記プロファイル情報の名前空間と現在のの名前空間の一致により確認する。
【００１４】
より好ましくは、前記再利用するステップは、前記コンピュータが、検出した前記関数呼び出しにおいて指定される指定情報がプロファイル情報の指定情報と一致することを条件に前記プロファイル情報の実行結果を再利用する再利用コードをコンパイル済みコードとして生成する。
【００１５】
更に好ましくは、上記最適化方法は、前記コンピュータが事前登録された型情報を操作する操作コードにアクセスし、該操作コードに、再利用する前記実行結果に関連付けられた前記型情報を変更することを条件として前記実行結果を再利用する前記再利用コードを無効化する命令列を挿入するステップを更に含み、前記禁止するステップは、前記命令の実行により行われる。
【００１６】
また好ましくは、再利用のために実行結果を格納すべきサブクラステスト関数のコードを、前記コンピュータに組み込まれたデフォルトのサブクラステスト関数のコードに限定する。
【００１７】
より好ましくは、上記最適化方法は、前記コンピュータが、前記プロファイル情報として格納される前記実行結果に関連付けられた型情報の変更イベントに対応するリスナーであって、前記変更イベントの発生に応答して、変更された前記型情報に対応する前記プロファイル情報を無効化する前記リスナーを生成するステップを更に含み、前記禁止するステップは、前記リスナーの実行により行われる。
【００１８】
また、より好ましくは、上記最適化方法は、前前記コンピュータが、再利用する前記実行結果に関連付けられた型情報の変更イベントに対応するリスナーであって、前記変更イベントの発生に応答して、前記実行結果を再利用する前記再利用コードを無効化する前記リスナーを生成するステップを更に含み、前記禁止するステップは、前記リスナーの実行により行われる。
【００１９】
また好ましくは、前記判定するステップにおいて、前記コンピュータは、再利用可能性を判定する前記コードからグローバルメモリへのアクセス命令を全て探し出し、探し出した全てのアクセス命令が、前記サブクラステスト関数の関数呼び出しにおいて指定される型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスであることを条件に、前記コードを再利用可能であると静的に判定する。
【００２０】
また好ましくは、前記判定するステップにおいて、前記コンピュータは、サブクラステスト関数の関数呼び出しにおいて指定されたオブジェクト及び型情報の値を、再利用可能性を判定する前記コードに伝播させた判定用コードを生成し、生成した判定用コードの実行中になされたグローバルメモリへのアクセスが全て型情報の読み出しのためのアクセスであることを条件に、前記コードを再利用可能であると動的に判定する。
【００２１】
また好ましくは、前記コンピュータが、再利用可能であると判定した前記コードに対し、該コードの実行によりアクセスされる型情報のアドレスを収集するテンプレートを生成するステップを更に含み、前記プロファイル情報は前記テンプレートの実行結果を利用して作成される。
【００２２】
また好ましくは、前記実行対象のプログラムは、Pythonで記述されたソースプログラムからPythonインタプリタにより生成されたバイトコードである。
【００２３】
以上、実行対象のプログラムにおけるサブクラステスト関数の実行結果を再利用するプログラムの最適化方法として本発明を説明した。しかし、本発明は、上記最適化方法をコンピュータに実行させるための最適化プログラムとして把握することもできる。また本発明は、当該最適化プログラムをインストールして最適化方法を実行する最適化装置として把握することもできる。
【発明の効果】
【００２４】
本願発明は、サブクラステスト関数の関数呼び出しから呼び出されるコードが、グローバル情報へのアクセスとして型情報の読み込みのみを行うことを確認し、確認できたコードについて実行結果をプロファイルし再利用する構成を採用する。上述したように、型情報は実行時に変化しにくいため、上記構成の採用によって将来無効とする可能性の高い実行結果の再利用を排除できる。また、本願発明は、実行時にアクセスした型情報を監視し、変更があった場合には対応する実行結果の再利用を禁止する構成を採用する。結果、本願発明によれば、単純に実行結果を再利用する場合に比べてより効率的にまた安全にサブクラステスト関数の実行結果を再利用することが可能となる。更に本願発明の上記構成によれば、グローバルメモリへの書き込みを行うサブクラステスト関数は再利用対象から除かれるので、副作用のあるサブクラステスト関数の実行結果の再利用によりプログラム全体が間違った動作を行うことを防止できる。本願発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００２５】
【図１】本発明の実施形態に係る最適化装置１００の機能構成を示す図である。
【図２】CALL_FUNCTIONのバイトコードと呼び出されるサブクラステスト関数の関係を模式的に示す図である。
【図３】プロファイル情報のデータ構造の一例を示す図である。
【図４Ａ】型情報の変更イベントに対応するリスナーの生成処理の流れを模式的に示す図である。
【図４Ｂ】リスナーによるプロファイル情報の無効化処理の流れを模式的に示す図である。
【図５Ａ】型情報の変更イベントに対応する他のリスナーの生成処理の流れを模式的に示す図である。
【図５Ｂ】リスナーによる再利用コードの無効化処理の流れを模式的に示す図である。
【図６】本発明の実施形態に係る最適化装置１００によるプログラム実行処理の動作フローの一例を示す。
【図７】再利用可能性判定部１２０による再利用可能判定処理の動作フローの一例を示す。
【図８】プロファイリング部１３０によるプロファイリング処理の動作フローの一例を示す。
【図９】再利用処理部１４０による再利用処理の動作フローの一例を示す。
【図１０】監視部１４５による監視処理の動作フローの一例を示す。
【図１１】本発明の実施形態に係るコンピュータ５０のハードウェア構成の一例を示す。
【図１２Ａ】本発明の第１の実装方法の一例を示す。
【図１２Ｂ】本発明の第２の実装方法の一例を示す。
【図１２Ｃ】本発明の第３の実装方法の一例を示す。
【発明を実施するための形態】
【００２６】
以下、本発明の実施形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００２７】
本願発明のサブクラステスト関数のテスト結果を再利用する技術は、Pythonのような、サブクラステスト関数に該当するバイトコードが存在せず呼び出される関数の実体やクラスごとのサブクラスの定義が動的に変わり得る動的プログラミング言語に対し適用される。そこで、本願発明の詳細な説明に入る前に、Pythonにおけるサブクラステスト関数であるisinstance関数を例として、動作が一意に決まらないサブクラステスト関数がどのように実行されるのかその仕組みを説明する。
【００２８】
Pythonではサブクラステスト関数に該当するバイトコードがなく、サブクラステスト関数の動作はPython関数により定義されている。従ってPythonにおいてサブクラステスト関数は関数呼び出しによって実行される。以下に示すコードは、isinstance(obj, clazz)を呼び出すための一連のバイトコードの例である。
LOAD_GLOBAL “isinstance”
LOAD_FAST “obj”
LOAD_FAST “clazz”
CALL_FUNCTION
【００２９】
isinstance関数の振る舞いは次の２つにより決まる。
（１）“isinstance”の値で関数呼び出しにより呼び出される関数
（２）”clazz”におけるクラス階層の定義
プログラムは、Pythonのソースコードに含まれる各isinstance関数に対して、上記（１）を、グローバルにもローカルにも、また、静的にも動的にも変更し得る。なお、isinstance関数のデフォルトの振る舞いはCPython等のインタプリタ・システムによって提供されており、isinstance関数は組込みＣ関数に、クラス階層の定義はＣ関数により提供されている。
【００３０】
もしユーザがPythonのソースコードにおいてisinstance関数を新たに定義すると、そのisinstance関数は実行される度に異なるアルゴリズムを実行することが可能である。即ち、isinstance関数の振る舞いは、アプリケーションのレベルで自由に定義されまたは変更され得る。isinstance関数がデフォルトではない関数を呼び出すケースは主に以下の通りである。
ケース１：isinstance関数がシステムのbuiltin用辞書において置き換えられている場合
ケース２：現在のスコープにおいて別のisinstance関数が定義されている場合
ケース３：クラスが独自のisinstance関数を持つ場合
【００３１】
ケース１に関し、組込み関数は実行時いつでも、また、コードのどの地点でも置き換え可能である。置き換えによる変更はプログラム内のあらゆるコードから透過的に見ることができる。以下はケース１の例である。なお、左端の数字は行番号を表す。５行目において置き換えが指示されており、結果、６行目のisinstance関数の結果が、７及び８行目に示されるように置換されたisinstance関数の実行結果になっている。
1 >>> import __builtin__
2 >>> def f(self, cls):
3 ... print “I am f”
4 ... return False
5 >>>__builtin__.isinstance = f    
6 >>> isinstance(“a”, basestring)
7 I am f
8 False 
【００３２】
ケース２に関し、あるモジュールに固有のisinstance関数を定義できる。定義はa.pyファイル内において静的に行うことができ、実行時いつでも、また、コードのどの地点でも追加、置き換え、削除が可能である。このような変更はプログラム内のあらゆるコードから透過的に見ることができる。以下はケース２の例である。ここでも左端の数字は行番号を表す。また、１行目〜６行目はa.pyファイル内の定義を示し、７行目〜１６行目は、a.pyファイルをインポートした際の実行結果を示す。１０行目〜１１行目では、a.pyファイルで定義した自身のisinstance関数が呼び出されているが、１４行目で再度デフォルトのisinstance関数に復元され、結果、１５行目ではデフォルトのisinstance関数が呼び出されている。
- a.py
1 def isinstance(self, cls):
2 print “a isinstance”
3 return False
4 class myclass(object):
5 def test(self, inst):
6 return isinstace(inst, myclass)
- run
7 >>> import a
8 >>>a.__dict__.keys()
9 ['__builtins__', '__file__', 'myclass','__name__', 'isinstance', '__doc__']
10 >>>o=a.myclass()
11 >>> o.test(o) 
12 a isinstance
13 False
14 >>>a.isinstance=isinstance 
15 >>> o.test(o) 
16 True 
【００３３】
ケース３に関し、ユーザは、クラスを定義する際に特別なメタクラスを設定することにより、isinstance関数に対してデフォルトのアルゴリズムを変更することができる。より具体的には、アルゴリズムはメタクラスの __instancecheck__を定義することにより実行時いつでも、また、コードのどの地点でも置換できる。このような変更はそのクラスと当該クラスのサブクラスから透過的に見ることができる。以下はケース３の例である。ここでも左端の数字は行番号を表す。また、１行目〜１２行目はb.pyファイル内の定義を示し、１３行目〜２８行目は、b.py を実行させた結果を示す。この例では、デフォルトのisinstance関数を呼び出しているが、しかしisinstance関数の実際の動作は、ユーザが定義した動作であることに留意されたい。デフォルトのisinstance関数であれば、isinstance(T1,T2)はもしT1がT2のサブクラスでなければFALSEを返す。しかしb.py を実行させた結果をみると、デフォルトのisinstance関数は、ユーザが定義した__instancecheck__によってTRUEを返している。
- b.py
1 from abc import ABCMeta
2 class MyABC:
3 __metaclass__ = ABCMeta
4 @classmethod
5 def__instancecheck__(self, inst):
6 print"MyABC __instancecheck__"
7 returnTrue
8 class MyClass(MyABC):
9 pass
10 class HisClass(object):
11      pass
12 print isinstance(HisClass(),MyClass)
- Run python b.py
13 >>> import b
14 MyABC __instancecheck__ 
15 True 
16 >>> class MyXYZ(b.MyClass):
17 ... def f(self,inst):
18 ... print “MyXYZ f”
19 ... return True
20 >>> o=MyXYZ()
21 >>> b.MyABC.__instancecheck__
22 <bound methodABCMeta.__instancecheck__ of <class 'b.MyABC'>>
23 >>>b.MyABC.__instancecheck__=o.f
24 >>> b.MyABC.__instancecheck__
25 <bound method hoe.f of<__main__.hoe object at 0x200b0730>>
26 >>> isinstance(b.HisClass(),b.MyClass)
27 MyXYZ f
28 True
【００３４】
本願発明は、Pythonのように、サブクラステスト関数に該当するバイトコードが存在せず呼び出される関数の実体やクラスごとのサブクラスの定義が動的に変わり得る動的プログラミング言語に適用可能な、サブクラステスト関数の実行結果の再利用によるプログラムの最適化手法を提供する。当該手法は、サブクラステスト関数のコードの再利用可能性を判定する段階、再利用可能であると判定したサブクラステスト関数のコードの実行をプロファイルする段階、再利用可能であると判定したコードを呼び出す関数呼び出しを検出し、該関数呼び出しに対し一定の条件の下実行結果を再利用する段階、及び、実行結果の再利用が不適切となる状況の発生を監視し、再利用を禁止する段階を含む。
【００３５】
上記４つの段階を含む最適化手法の具体的な実装方法は、インタプリタがプログラムの実行中にプロファイルを行い、Just-In-Time(JIT)コンパイラによりコンパイルされたJITコードがプロファイル結果を利用する第１の実装方法、プログラムの実行中にインタプリタ自身がプロファイル結果をキャッシュして利用する第２の実装方法、及び最適化レベルの低いJITコードがテスト結果をプロファイルし、最適化レベルの高いJITコードがプロファイル結果を利用する第３の実装方法等、複数考えられる。以下では、第１の実装方法に従って本願発明の実施形態を説明する。
【００３６】
図１は、本願発明の実施形態に係る最適化装置１００の機能ブロック図を示す。最適化装置１００は、動的プログラミング言語で記述されたソースプログラムから生成され、仮想マシンによって実行されるバイトコードである実行対象のプログラムを実行する実行環境（図示しない）を備え、該実行環境において、記憶装置１０５と、イベント作成部１１０と、再利用可能性判定部１２０と、プロファイリング部１３０と、再利用処理部１４０と、監視部１４５とを含む。なお、以下では、実行対象のプログラムは、Pythonで記述されたソースプログラムからPythonインタプリタにより生成されたバイトコードであるとして説明する。
【００３７】
記憶装置１０５は、再利用可能性判定部１２０によるサブクラステスト関数のコードの解析結果を格納する解析結果ＤＢ１１５と、プロファイリング部１３０によるサブクラステスト関数のプロファイリング結果を格納するプロファイリングＤＢ１２５と、再利用処理部１４０により生成されたサブクラステスト関数の実行結果を再利用するコンパイル済みコードを格納する再利用コードＤＢ１３５とを含む。それぞれのＤＢに格納される情報の詳細は、以下に説明する各要素に関連して後述する。
【００３８】
イベント作成部１１０は、実行対象のプログラムにおいて次に実行されるバイトコードがサブクラステスト関数の関数呼び出しであることに応答して、関数呼び出しが呼び出すコードを指す関数ポインタと、関数呼び出しにおいて指定された指定情報とからなるイベント情報を作成する。ここで、サブクラステスト関数の関数呼び出しにおいて指定された指定情報とは、関数呼び出しにおける入力パラメータであり、テスト対象のオブジェクトと型（クラス）とを指定する情報である。なお、イベント作成部１１０により作成されるイベント情報は、更にカウンタ情報を含んでよく、イベント作成部１１０は、既にそのイベント情報を作成したサブクラステスト関数と同一のサブクラステスト関数が同一の入力パラメータを伴って呼び出された場合、対応するイベント情報のカウンタを１増分する。
【００３９】
図２は、Pythonバイトコードにおける関数呼び出しと、関数呼び出しから呼び出されるコードとの関係の一例を示す。上述したように、Pythonソースコードにおけるサブクラステスト関数isinstance(obj, clazz)は、Pythonインタプリタにより以下のような関数呼び出し（CALL_FUNCTION）を含む一連のバイトコードに変換される。
LOAD_GLOBAL “isinstance”
LOAD_FAST “obj”
LOAD_FAST “clazz”
CALL_FUNCTION
図２が示すように、関数呼び出しは、実際にはサブタイプテスト・ラッパを介してサブクラステスト関数の実体であるコード（図２ではサブルーチンと表示）を呼び出す。
【００４０】
再利用可能性判定部１２０は、実行対象のプログラムに含まれるサブクラステスト関数の関数呼び出しから呼び出されるコードの再利用可能性を、該コードにおけるグローバルメモリへのアクセスが、サブクラステスト関数の関数呼び出しにおいて指定された型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスのみを含むか否かに基づいて判定する。ここで、サブクラステスト関数の関数呼び出しにおいて指定された型情報から辿ることの可能な情報とは、型情報であるクラス・オブジェクトが有するポインタによって指される情報であり、一例として親クラス・オブジェクトである。また、グローバルメモリとは、そのメモリへの変更がその変更を行った関数のような実行単位を抜けた後でも参照できるメモリ領域を意味し、例えばオブジェクト・ヒープやグローバル変数を含む。なお、再利用可能性判定部１２０は上記処理を、イベント作成部１１０による処理に応答して、イベント情報のカウンタが予め設定された所定の回数以上であることを条件に行ってよい。
【００４１】
上述したように型情報は実行時に変化しにくいため、グローバル情報へのアクセスとして型情報の読み込みのみを行うことを条件としてサブクラステスト関数の実行結果を再利用可能と判定することで、将来無効とする可能性の高い実行結果の再利用を排除できる。また、上記条件によれば、グローバルメモリへ書き込みを行うサブクラステスト関数は再利用対象から除かれる。サブクラステスト関数内で書き込まれたグローバルメモリ内の値が他のスレッドにより参照される場合、実行結果の再利用によりサブクラステスト関数が実行されなくなると他のスレッドが間違った値を読み込んでしまう可能性がある。そのため、このような副作用を起こす可能性のあるサブクラステスト関数を再利用対象から除くことで、プログラムが全体として間違った動作をする事態を回避できる。
【００４２】
なお、再利用可能性判定部１２０による上記判定は、一例として次のように静的に行ってよい。即ち、再利用可能性判定部１２０は、再利用可能性を判定するコードからグローバルメモリへのアクセス命令を全て探し出し、探し出した全てのアクセス命令が、サブクラステスト関数の関数呼び出しにおいて指定される型情報及び該型情報から辿ることの可能な情報の読み出しのためのアクセスであることを条件に、上記コードを再利用可能であると判定してよい。
【００４３】
上記静的判定方法に代えて、再利用可能性判定部１２０は、サブクラステスト関数の関数呼び出しにおいて指定されたオブジェクト及び型情報の値を、再利用可能性を判定するコードに伝播させた判定用コードを生成し、生成した判定用コードの実行中になされたグローバルメモリへのアクセスが全て型情報の読み出しのためのアクセスであることを条件に、上記コードを再利用可能であると判定してよい。
【００４４】
ここで判定用コードは、サブクラステスト関数の関数呼び出しにおいて指定されたオブジェクトと型情報のペアの統計をプロファイルし、ペアの集合が大きくなくキャッシュの効果があると判定することを条件に生成するのが好ましい。そして、ペアごとその値を固定した判定用コードを生成し、生成した全判定用コードについて、実行中になされたグローバルメモリへのアクセスが全て型情報の読み出しのためのアクセスであることを確認することを条件に、上記サブクラステスト関数のコードを再利用可能であると判定するのが好ましい。
【００４５】
また、再利用可能性判定部１２０は、再利用可能であると判定したサブクラステスト関数のコードに対し、コードの実行によりアクセスされる型情報のアドレスを収集するテンプレートを作成するのが好ましい。テンプレートは、後述するプロファイリング部１３０により実行され利用される。なお、テンプレートは、一例として上記判定用コードに、次のようなinstrumentコードを挿入することにより作成してよい。そのようなinstrumentコードとは、判定用コードが実際に読み込む型情報が記憶されているメモリのアドレスを収集し、収集したアドレスを所定の領域（一例として、オブジェクトであるテンプレートの所定のフィールド（以下、TypeInfoReadSetという））に格納するコードであってよい。なお、テンプレート作成時点において所定の領域（一例として、TypeInfoReadSet）は空とする。
【００４６】
再利用可能性判定部１２０は、サブクラステスト関数の関数呼び出しから呼び出されるコードについて再利用可能であると判定した場合、生成したテンプレートと一緒に、イベント生成部１１０が生成した上記関数呼び出しのイベント情報を解析結果ＤＢ１１５に格納する。また、再利用可能性判定部１２０は、再利用可能であると判定したコードオブジェクトに、例えば１フィールド追加してテンプレートを指すポインタを設定する等マークを付けて、再利用可能であることを示してよい。
【００４７】
プロファイリング部１３０は、再利用可能性判定部１２０により再利用可能であると判定されたサブクラステスト関数のコードの実行結果を、該コードの関数呼び出しにおいて指定された指定情報と共に、該コードにおいて実際にアクセスされた型情報に関連付けて、上記コードのプロファイル情報としてプロファイルＤＢ１２５に格納する。ここでコードの実行結果とは、サブクラステスト関数の関数呼び出しにおいて指定されたテスト対象のオブジェクトが、同じく関数呼び出しにおいて指定されたクラスのインスタンス又は該クラスのサブクラスのインスタンスであるか否かを示すブーリアン型の情報である。なお、再利用可能であると判定されたコードであるか否かは、再利用可能性判定部１２０によりコードに付けられたマークによって識別される。
【００４８】
また、上述したようにプロファイリング部１３０は、サブクラステスト関数のコードにおいて実際にアクセスされた型情報を、再利用可能性判定部１２０により作成されたテンプレートを実行することにより収集してよい。即ち、プロファイリング部１３０は、再利用可能であると判定されたサブクラステスト関数のコードの実行に応答して、該コードを指す関数ポインタをキーとして解析結果ＤＢ１１５から対応するイベント情報とテンプレートとを読み出す。そして、プロファイリング部１３０は、読み出したテンプレートを実行して、そのTypeInfoReadSetフィールドから実際にアクセスされた型情報のアドレスを取得してよい。読み出した対応するイベント情報と取得した型情報のアドレスは、それぞれ後述する監視部１４５と再利用処理部１４０による処理にためにプロファイルＤＢ１２５に格納される。
【００４９】
プロファイリング部１３０はまた、好ましくは、サブクラステスト関数のコードの実行結果と共に、コード実行時の名前空間をプロファイル情報としてプロファイルＤＢ１２５に格納する。これは、本願発明が対象とする動的プログラミング言語では、サブクラステスト関数に該当するバイトコードが存在せず呼び出される関数の実体が動的に変わり得るため、プロファイル時と実行結果の再利用時とでサブクラステスト関数の関数呼び出しにより呼び出されるコードが異ならないことを、実行結果の再利用時に名前空間を利用して確認できるようにするためである。
【００５０】
Pythonにおいて名前空間は、オブジェクトの名前をキーとして指定すると、対応するオブジェクトを返す辞書と考えることができる。名前空間は、関数呼び出しを含むオブジェクト全体に対して１つに決まる（現在の辞書とする）一方で、呼び出される関数のアルゴリズムが変更されたり、同名の新たなオブジェクトが定義されたりすると、現在の辞書が他の辞書に切り替わったり、辞書の内容が変わったりする。そこで、プロファイル時と実行結果の再利用時とで名前空間が一致することを確認することにより、サブクラステスト関数の関数呼び出しにより呼び出されるコードが同一であることを確認することができる。
【００５１】
なお、サブクラステスト関数がシステムのbuiltin用辞書において置換されることは稀である。そこで、名前空間の利用に代えて、再利用のために実行結果を格納すべきサブクラステスト関数のコードを、システムに組み込まれたデフォルトのサブクラステスト関数のコードに限定することにより、プロファイル時と実行結果の再利用時とで呼び出されるコードが異ならないことを緩く保証してもよい。この場合、デフォルトのコードのポインタを予め取得し、再利用時には、再利用しない場合に呼び出されるはずだったコードのポインタが予め取得したポインタと一致することを確認する。なお、名前空間を利用したガード機構は、Pythonに限定されるものではなく、名前空間に関してPythonと同様のルールを採用する他の動的プログラミング言語に適用可能なことはいうまでもない。
【００５２】
図３は、プロファイリング部１３０により記憶装置１０５に格納されるプロファイル情報の一例を示す。図３においてバイトコード３００は関数呼び出し３０５を含み、該関数呼び出し３０５はサブクラステスト関数３１０のコードを呼び出す。プロファイル・リポジトリ３２０は、プロファイル情報を格納する記憶装置１０５内の領域を示し、図１においけるプロファイルＤＢ１２５に相当する。プロファイル３２５は、サブクラステスト関数３１０についてのプロファイル情報の集合であり、サブクラステスト関数３１０を指すポインタＰＣ３３０と、互いに異なる入力パラメータを伴って呼び出された際のプロファイル情報３３５、３４０を含む。各プロファイル情報は、対応するイベント情報Ｅと、名前空間Ｎと、実行時にアクセスされた型情報のアドレスの集合Ｒと、実行結果Ｌとを含む。
【００５３】
再利用処理部１４０は、再利用可能であると判定したコードを呼び出すサブクラステスト関数の関数呼び出しの検出に応答して、プロファイルＤＢ１２５から対応するプロファイル情報を読み出し、検出した関数呼び出しにおいて指定される指定情報とプロファイル情報の指定情報とが一致することを条件にプロファイル情報の実行結果を再利用する。再利用可能と判定した関数呼び出しの検出は、関数ポインタをキーとして、対応するプロファイル情報がプロファイルＤＢ１２５に存在することを確認することにより行ってよい。好ましくは、再利用処理部１４０は、検出した関数呼び出しが再利用可能であると判定されたコードを呼び出すことを、プロファイル情報作成時と再利用時とで名前空間が一致することを確認することにより保証する。
【００５４】
JITコードがプロファイル結果を利用する第１実装方法に従う本実施形態では、実行結果はコンパイル済みコードにおいて利用される。即ち、再利用処理部１４０は、現在の関数呼び出しにおいて指定される指定情報がプロファイル情報に含まれる指定情報と一致することを条件にプロファイル情報に含まれる実行結果を再利用する再利用コードを生成する。生成された再利用コードは、最適化装置１００による実行のため、再利用コードＤＢ１３５に格納される。
【００５５】
再利用処理部１４０によって生成される再利用コードの一例を以下に示す。当該例では、関数呼び出しにおいて指定される指定情報、即ち、オブジェクトと型情報が一致することに加えて、名前空間が一致することを、実行結果を利用する条件としている。なお、cacheForThisCode->countは、検出した関数呼び出しにより呼び出されるコードのプロファイル情報のエントリ数を示す。
for ( i=0;i < cacheForThisCode->count; i++) {
if (match(cacheForThisCode->entry[i].nameSpace,currentNameSpace)&&
cacheForThisCode->entry[i].obj== obj &&
cacheForThisCode->entry[i].objType == objType){
result=cacheForThisCode->entry[i].result;
break; 
}
}
【００５６】
なお、上記示した再利用コードに、一致するプロファイル情報のエントリが全くない場合は、サブクラステスト関数を呼び出す命令を追加してもよい。またコード中でループを展開して配列の要素引きをやめて効率化してもよい。またコード中で定数と判断される場合（たとえばクラス引数が定数）、コンパイラはコード中でそうした情報を適宜伝搬して再利用コードを効率化することも可能である。また名前空間の内容は不変なものと仮定する技術により、名前空間の識別子比較および不変性チェックにより一致確認を高速化することも可能である。
【００５７】
監視部１４５は、プロファイルＤＢ１２５に格納されているプロファイル情報に含まれる実行結果に関連付けられた型情報を監視して、該型情報に対する変更に応答して型情報に関連付けられた実行結果の再利用を禁止する。ここで実行結果の再利用の禁止は、変更のあった型情報に関連付けられたプロファイル情報又は該プロファイル情報を含むコードごとのプロファイル情報の集合の削除、及び変更のあった型情報に関連付けられる実行結果を再利用する再利用コードの削除の少なくとも一方を含む。
【００５８】
監視部１４５の具体的な実装方法はいくつか考えられるが、ここでは、監視対象の型情報を操作するコードに監視部１４５の機能を果たすコードを挿入する第１の実装方法と、監視対象の型情報の変更イベントに対応するリスナーを利用する第２の実装方法の２つについて順に説明する。
【００５９】
第１の実装方法では、再利用処理部１４０が、実行結果の再利用に応答して、型情報を操作する操作コードにアクセスし、該操作コードに、再利用する実行結果に関連付けられた型情報を変更することを条件として実行結果を再利用する再利用コードを無効化する命令列を挿入する。すると、監視部１４５は、操作コードの実行に伴って上記命令の実行により実現される。ここで、型情報を操作する操作コードはインタプリタの実装コードである場合と、JITコンパイラによりコンパイラされたJITコードである場合がある。なお、Pythonインタプリタでは型情報を操作する操作コードは限られており既知であるため、そのような操作コードは事前にリストしておき、無効化のための命令列を挿入する際はリストを参照するものとする。
【００６０】
操作コードの型情報を操作する部分と、操作コードに挿入する命令列の一例を以下に示す。なお、再利用された実行結果のプロファイル情報には、実行中にアクセスされた型情報として以下に示すＡ．クラス・オブジェクトのparentsフィールドを指すポインタと、実行結果を再利用した再利用コードを指すポインタが含まれているものとする。そして、これら２つのポインタ情報はgetNextTypeInfoReadSet()関数によって取得されるものとする。挿入する命令列は、監視対象の型情報を操作する命令の前後いずれかに挿入される。
Ａ．クラス・オブジェクト
struct  class_object{
header_t header;
list_t parents;
…
}
Ｂ．型情報を操作する操作コードの操作部分
t->parents= p
Ｃ．挿入する命令列
while( s= getNextTypeInfoReadSet()){
if( s->ptr == &t->parents){
Invalidate(s->JITcode);
}
}
【００６１】
第２の実装方法では、監視部１４５は、プロファイル情報として格納される実行結果に関連付けられた型情報の変更イベントに対応するリスナーとして実現される。リスナーは、プロファイリング部１３０によってプロファイル情報が作成される際に生成され、対応するプロファイル情報へのポインタを有し、対応するプロファイル情報に含まれる実際にアクセスされた型情報が示す全てのクラス・オブジェクトに登録される。そしてリスナーは、いずれかのクラス・オブジェクトから型情報の変更イベントの通知を受け取ると、ポインタを使用して対応するプロファイル情報を無効化する。
【００６２】
図４Ａは、プロファイリング部１３０によりリスナーが生成され、該リスナーが対応するクラス・オブジェクトに登録されるまでの処理の概要を示す。なお、図４Ａでは、プロファイリング部１３０をプロファイラ４１５として、またプロファイルＤＢ１２５を、プロファイル・リポジトリ４２０として示している。
【００６３】
１．バイトコード４００に含まれる関数呼び出し４０５がサブクラステスト関数４１０を呼び出す。２．プロファイラ４１５は、サブクラステスト関数４１０の呼び出しを検出し、３．サブクラステスト関数４１０の実行結果をプロファイル情報４４０としてプロファイル・リポジトリ４２０に格納する。４．プロファイラ４１５は、プロファイル情報４４０へのポインタを有する、プロファイル情報４４０に関するリスナーである第２リスナー４５０を作成し、５．第２リスナー４５０をプロファイル情報４４０に含まれる実際にアクセスされた型情報が示すクラス・オブジェクト４６０に登録する。同様に、図４Ａに示される第１リスナー４４５は、プロファイル情報４３５へのポインタを有し、クラス・オブジェクト４５５の変更イベントに対応するリスナーである。
【００６４】
図４Ｂは、生成されたリスナーが対応するクラス・オブジェクトから変更イベントの通知を受け、対応するプロファイル情報を無効化するまでの処理の概要を示す。なお、図４Ｂでは、図４Ａに示した要素と同一の要素には同じ番号を振っている。
【００６５】
１．クラス・オブジェクト４５５に対し変更が加えられる。２．第１リスナー４４５は、クラス・オブジェクト４５５から変更イベントの発生の通知を受け取る。３．第１リスナー４４５は、自身が有する対応するプロファイル情報４３５へのポインタを使って、対応するプロファイル情報４３５をプロファイル・リポジトリ４２０から削除して無効化し、また、自分自身（第１リスナー４４５）を消去する。この際第１リスナー４４５は、同じコードに対する他の全てのプロファイル情報４４０及び該プロファイル情報４４０に関連付けられる第２リスナー４５０を無効化してもよい。
【００６６】
第２の実装方法ではまた、監視部１４５は、再利用された実行結果に関連付けられた型情報の変更イベントに対応するリスナーとしても実現される。リスナーは、再利用処理部１４０によって実行結果が再利用される際に生成され、対応する実行結果を再利用する再利用コードへのポインタを有し、対応するプロファイル情報に含まれる実際にアクセスされた型情報が示す全てのクラス・オブジェクトに登録される。そしてリスナーは、いずれかのクラス・オブジェクトから型情報の変更イベントの通知を受け取ると、ポインタを使用して対応する再利用コードを無効化する。
【００６７】
図５Ａは、再利用処理部１４０によりリスナーが生成され、該リスナーが対応するクラス・オブジェクトに登録されるまでの処理の概要を示す。なお、図５Ａに示されるコンパイル済みコード５００は、図４Ａに示した関数呼び出し４０５を、プロファイル４２５を用いて最適化したものである。プロファイル４２５には、関数呼び出し４０５の入力パラメータの２種類のペアについての実行結果であるプロファイル情報４３５、４４０が含まれることから、コンパイル済みコード５００は、検出した（現在の）関数呼び出し４０５において指定される型情報をこれら２種類の入力パラメータのペアとそれぞれ比較し、一致した方のプロファイル情報に含まれる実行結果を利用するよう記述されている。
【００６８】
１．再利用処理部１４０により、図４Ａに示すプロファイル情報４４０を使用してコンパイル済みのコード５００が生成される。２．再利用処理部１４０は、コンパイル済みのコード５００へのポインタを有する、コンパイル済みコード５００関するリスナーである第４リスナー５４０を作成し、３．第４リスナー５４０を、プロファイル情報４４０に含まれる実際にアクセスされた型情報が示すクラス・オブジェクト５４５に登録する。同様に、図５Ａに示される第３リスナー５２５は、コンパイル済みのコード５００へのポインタを有し、プロファイル情報４４０に含まれる実際にアクセスされた他の型情報が示すクラス・オブジェクト５３０に登録されるリスナーである。
【００６９】
図５Ｂは、生成されたリスナーが対応するクラス・オブジェクトから変更イベントの通知を受け取り、対応するコンパイル済みコードを無効化するまでの処理の概要を示す。示す。なお、図５Ｂでは、図５Ａに示した要素と同一の要素には同じ番号を振っている。
【００７０】
１．クラス・オブジェクト５３０に対し変更が加えられる。２．第３リスナー５２５は、クラス・オブジェクト５３０から変更イベントの発生の通知を受け取る。３．第３リスナー５２５は、自身が有するコンパイル済みのコード５００に含へのポインタを使って、対応するコンパイル済みコード５００の全体を無効化する。また、第３リスナー５２５は、自分自身（第３リスナー５２５）及び関連する他の第４リスナー５４０を消去してもよい。
【００７１】
次に図６乃至図１０を参照して、本願発明の実施形態に係る最適化装置１００の動作を説明する。図６は、最適化装置１００によるプログラム実行処理の流れの一例を示すフローチャートである。図７は、図６に示すフローチャートのステップ６２４に示す再利用可能性判定処理の流れの一例を示すフローチャートである。図８は、図６に示すフローチャートのステップ６３０に示すプロファイルリングの流れの一例を示すフローチャートである。なお、第１の実装方法に従う本願発明の実施形態では、図６に示すプログラム実行処理はインタプリタによって実行される。また、図７に示す再利用可能性判定処理は、インタプリタから呼び出された再利用可能性判定モジュール（再利用可能性判定１２０に対応）によって、図８に示すプロファイルリングは、インタプリタから呼び出されたプロファイリング・モジュール（プロファイリング部１３０に対応）によってそれぞれ実行される。
【００７２】
また、図９は、最適化装置１００によるコンパイル処理の流れの一例を示すフローチャートである。図１０は、最適化装置１００による監視処理の流れの一例を示すフローチャートである。なお、第１の実装方法に従う本願発明の実施形態では、図９に示すコンパイル処理はJITコンパイラによって実行される。また、図１０に示す監視処理は、型情報に対する操作がインタプリタによりなされる場合にはインタプリタにより、また、型情報に対する操作がJITコードによりなされる場合にはJITコードにより実行される。
【００７３】
図６に示すプログラム実行処理はステップ６００から開始し、最適化装置１００は、実行対象のプログラムから次に実行すべきバイトコードＢをフェッチする。続いて最適化装置１００は、次に実行すべきバイトコードＢがあるか否かを判定する（ステップ６０２）。次に実行すべきバイトコードＢがない場合（ステップ６０２：ＮＯ）、処理は終了する。一方、次に実行すべきバイトコードＢがある場合（ステップ６０２：ＹＥＳ）、最適化装置１００は、バイトコードＢがCALL_FUNCTION命令であるか否かを判定する（ステップ６０４）。
【００７４】
バイトコードＢがCALL_FUNCTION命令である場合（ステップ６０４：ＹＥＳ）、最適化装置１００はCALL_FUNCTION命令により呼び出されるターゲットの関数を取得し（ステップ６０６）、関数Ｆがサブタイプテスト・ラッパであるか否かを判定する（ステップ６０８）。関数Ｆがサブタイプテスト・ラッパである場合（ステップ６０８：ＹＥＳ）、最適化装置１００はイベントＥを作成する（ステップ６１２）。なお、イベントＥは、CALL_FUNCTION命令によりサブタイプテスト・ラッパを介して呼び出されるサブクラステスト関数のコードＣの関数ポインタと、CALL_FUNCTION命令に関して指定される引数のペアとからなる情報である。
【００７５】
続いて最適化装置１００は、イベントＥの頻度をプロファイルし（ステップ６１４）、イベントＥの頻度に関するプロファイル情報が既に存在するか否かを判定する（ステップ６１６）。イベントＥの頻度に関するプロファイル情報は、最適化装置１００の記憶装置１０５に格納されてよい。イベントＥのプロファイル情報が記憶装置１０５に存在しない場合（ステップ６１６：ＮＯ）、最適化装置１００はイベントＥの頻度に関するプロファイル情報を作成し、記憶装置１０５に格納する（ステップ６２０）。一方、イベントＥのプロファイル情報が既に記憶装置１０５に存在する場合（ステップ６１６：ＹＥＳ）、最適化装置１００は、記憶装置１０５に格納されるイベントＥの頻度情報を更新する。なお、四角６４０で囲ったステップ６１４からステップ６２０までの一連の処理はオプションであってよく、頻繁に実行されるコードに関して最適化を行いたい場合等必要に応じて適宜行ってよい。
【００７６】
続いて最適化装置１００は、解析結果ＤＢ１１５にイベントＥが存在するか否かを判定する（ステップ６２２）。解析結果ＤＢ１１５にイベントＥが存在しない場合（ステップ６２２：ＮＯ）、最適化装置１００はバイトコードＢが呼び出すサブクラステスト関数のコードＣに関して再利用可能性を判定する（ステップ６２４）。再利用可能性判定処理の詳細は、図７を参照して後述する。続いて最適化装置１００は、再利用可能性判定処理の結果が、再利用可能であるか否かを判定する（ステップ６２６）。サブクラステスト関数のコードＣについて再利用可能でないとの判定結果が出された場合（ステップ６２６：ＮＯ）、ステップ６０４においてバイトコードＢがCALL_FUNCTION命令でない場合、またはステップ６０８において関数Ｆがサブタイプテスト・ラッパでない場合、処理はステップ６１０へ進み、最適化装置１００はバイトコードＢを実行する。そして処理はステップ６００へ戻り、最適化装置１００は一連の処理を繰り返す。
【００７７】
一方、ステップ６２６において、サブクラステスト関数のコードＣについて再利用可能であるとの判定結果が出された場合、またステップ６２２において解析結果ＤＢ１１５にイベントＥが存在した場合、処理はステップ６２８へ進み、最適化装置１００はバイトコードＢを実行する。これに平行して又は実行の後、最適化装置１００は、バイトコードＢにより呼び出されるサブクラステスト関数のコードＣの実行結果のプロファイリングを行う（ステップ６３０）。プロファイリングの詳細は、図８を参照して後述する。そして処理はステップ６００へ戻り、最適化装置１００は一連の処理を繰り返す。
【００７８】
図７に示す再利用可能性判定処理部１２０による再利用可能性判定処理はステップ７００から開始し、再利用可能性判定部１２０は、記憶装置１０５からイベントＥの情報、即ち、関数ポインタと引数のペアの値を読み出し、サブクラステスト関数のコードＣに引数のペアの値を伝播させて判定用コードＳを作成する。なお、イベントＥについて頻度情報が記憶装置１０５に格納されている場合、再利用可能性判定部１２０は、一定以上の頻度情報を有するイベントＥに対してのみ、以下の処理を行ってもよい。
【００７９】
続いて、再利用可能性判定部１２０は、判定用コードＳを実行し、実行中にグローバルメモリへの書込みがあるか否か及びグローバル情報として型情報のみを読み込むか否かを判定する（ステップ７０２、７０４）。グローバルメモリへのアクセスが型情報の読み込みのためのアクセスのみでない場合（ステップ７０２：ＹＥＳ又はステップ７０４：ＮＯ）、再利用可能性判定部１２０は、再利用不可の判定結果を生成する（ステップ７１２）。その後処理は終了する。
【００８０】
一方、グローバルメモリへのアクセスが型情報の読み込みのためのアクセスのみである場合（ステップ７０２：ＮＯかつステップ７０４：ＹＥＳ）、再利用可能性判定部１２０は、サブクラステスト関数のコードＣの実行中にアクセスされる型情報のアドレスを収集し、収集した情報を自身のTypeInfoReadSetフィールドに格納するテンプレートＴを作成する（ステップ７０６）。そして再利用可能性判定部１２０は、生成したテンプレートＴと一緒にイベントＥを解析結果ＤＢ１１５へ格納し（ステップ７０８）、再利用可能の判定結果を生成する（ステップ７１０）。そして処理は終了する。
【００８１】
図８に示すプリファイリング部１３０によるプロファイリング処理はステップ８００から開始し、プロファイリング部１３０は、イベントＥに対応するプロファイル情報がプロファイルＤＢ１２５に存在するか否かを判定する。イベントＥに対応するプロファイル情報がプロファイルＤＢ１２５に既に存在する場合（ステップ８００：ＹＥＳ）、処理は終了する。
【００８２】
一方、イベントＥに対応するプロファイル情報がプロファイルＤＢ１２５にまだ存在しない場合（ステップ８００：ＮＯ）、プロファイリング部１３０は、バイトコードＢの実行結果Ｌと、名前空間Ｎを取得する（ステップ８０２、ステップ８０４）。また、プロファイリング部１３０は、バイトコードＢが関数呼び出しのために使用する関数ポインタをキーとして、解析結果ＤＢ１１５からイベントＥとテンプレートＴを取得する（ステップ８０６）。そしてプロファイリング部１３０は取得したテンプレートＴを実行して、テンプレートＴのTypeInfoReadSetフィールドから実行中にアクセスされた型情報Ｒのアドレスの集合を取得する（ステップ８１０）。
【００８３】
続いてプロファイリング１３０は、バイトコードＢに再利用可能であることを示すマークを付け（ステップ８１０）、プロファイルＤＢ１２５にバイトコードＢのプロファイル情報としてイベントＥ、名前空間Ｎ、型情報Ｒのアドレスの集合、実行結果Ｌを格納する（ステップ８１２）。そして処理は終了する。
【００８４】
図９に示すコンパイル処理はステップ９００から開始し、最適化装置１００は実行対象のプログラムから次に実行すべきバイトコードＢをフェッチする。続いて最適化装置１００は、未処理のバイトコードＢがあるか否かを判定する（ステップ９０２）。未処理のバイトコードＢがない場合（ステップ９０２：ＮＯ）、処理は終了する。一方、未処理のバイトコードＢがある場合（ステップ９０２：ＹＥＳ）、最適化装置１００は、バイトコードＢに対応するプロファイル情報がプロファイルＤＢ１２５に存在するか否かを判定する（ステップ９０４）。かかる判定は、バイトコードＢがサブクラステスト関数のコードＣを呼び出すCALL_FUNCTION命令であること、そして関数呼び出しのために使用される関数ポインタをキーとして、サブクラステスト関数のコードＣについてのプロファイル情報がプロファイルＤＢ１２５から探し出せることを確認することによりなされる。
【００８５】
ステップ９０４において、対応するプロファイル情報がプロファイルＤＢ１２５に存在しない場合、最適化装置１００は、バイトコードＢを従来技術に基づきコンパイルして最適化する（ステップ９０６）。そして処理はステップ９００へ戻り、最適化装置１００は一連の処理を繰り返す。一方、ステップ９０４において、対応するプロファイル情報がプロファイルＤＢ１２５に存在する場合、最適化装置１００は、プロファイルＤＢ１２５からバイトコードＢに対応する全てのプロファイル情報、即ち、バイトコードＢから呼び出されるサブクラステスト関数のコードＣについてのプロファイル情報（Ｅ、Ｎ、Ｒ、Ｌ）の全ての組を読み出す（ステップ９０８）。
【００８６】
続いて最適化装置１００は、読み出したプロファイル情報（Ｅ、Ｎ、Ｒ、Ｌ）の各組について、再利用コードＪの生成（ステップ９１０）と、監視コードＤの生成及び挿入（ステップ９１２）とをそれぞれ行う。より具体的には、ステップ９１０において最適化装置１００は、サブクラステスト関数を呼び出すバイトコードＢのコンパイル済みコードとして、現在のサブクラステスト関数の関数呼び出しにおいて指定される引数のペアの値が、プロファイル情報のイベントＥに含まれる引数のペアの値と一致し、かつ、現在の名前空間とプロファイル情報の名前空間Ｎとが一致することを条件にプロファイル情報に含まれる実行結果Ｌを再利用する再利用コードＪを生成する。
【００８７】
また、ステップ９１２はプロファイル情報の型情報の集合Ｒに含まれる各アドレスＡについて実行され、最適化装置１００は、アドレスＡのメモリの値を変更し得る操作コードＭにアクセスし、操作コードＭの当該操作コード部分の前後に、変更されたメモリのアドレスがＡであることを条件に再利用コードＪを無効化する命令列を挿入する。ステップ９１０及びステップ９１２の処理がプロファイル情報（Ｅ、Ｎ、Ｒ、Ｌ）の全組についてなされると、その後処理はステップ９００へ戻り、最適化装置１００は、一連の処理を繰り返す。なお、第１の実装方法に従う本願発明の実施形態では、図９において四角９２０で囲まれた部分の処理は、JITコンパイラにより呼び出された再利用処理モジュール（再利用処理部１４０に対応）により行われる。
【００８８】
図１０に示す監視部１４５による監視処理は、図９のステップ９１２において１以上の監視コードＤを挿入された操作コードＭの操作コード部分が実行され、アドレスＹのメモリが変更されることにより開始される。監視部１４５は、操作コードＭに挿入された各監視コードＤについて、アドレスＹとアドレスＡが一致するか否かを判定する（ステップ１０００）。なお、監視コードＤは対応するサブクラステスト関数のコードＣの実行中にアクセスされた型情報の数だけ存在し、各監視コードＤはそれぞれ異なる型情報に対する変更を監視するため、互いに異なる型情報のアドレスＡに関連づけられることに留意されたい。
【００８９】
いずれかの監視コードＤについてステップ１０００においてアドレスＹとアドレスＡが一致すると判定された場合、監視部１４５は対応する再利用コードＪを削除により無効化する（ステップ１００２）。その後監視部１４５による処理は終了し、操作コードＭの本来の処理に戻る。一方、ステップ１０００においてアドレスＹとアドレスＡが一致しないとの判定がなされた場合、続いて監視部１４５は、未処理の監視コードＤがあるか否かを判定し（ステップ１００４）、未処理の監視コードＤがある場合（ステップ１００４：ＹＥＳ）、ステップ１０００に戻って一連の処理を繰り返す。一方、未処理の監視コードＤがない場合（ステップ１００４：ＮＯ）、監視部１４５による処理は終了し、操作コードＭの本来の処理に戻る。
【００９０】
図１１は、本実施形態に係るコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【００９１】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ等に命令を与え、本発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、上記説明した数々の記憶装置には、上述した最適化装置１００に、動的プログラミング言語で記述されたソースプログラムから生成され、仮想マシンによって実行されるバイトコードである実行対象のプログラムを実行する実行環境を与えるためのプログラムを記録することができる。即ち、上記説明した数々の記憶装置には、Cpython等のインタプリタ、SSLやzlib等のインタプリタにより利用される種々のライブラリ、JITコンパイラ、JITコンパイラにより生成されるJITコードを記録することができる。
【００９２】
また、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０を最適化装置１００として機能させる、最適化プログラムを記録することができる。上記最適化プログラムは、イベント作成モジュールと、再利用可能性判定モジュールと、プロファイリング・モジュールと、再利用処理モジュールと、監視モジュールとを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、イベント作成部１１０、再利用可能性判定部１２０、プロファイリング部１３０、再利用処理部１４０、および監視部１４５としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【００９３】
コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【００９４】
以上の説明により、本実施形態に係るコンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００９５】
以上、実施形態を用いて本願発明の説明をしたが、本願発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。例えば、上述した本願発明の実施形態は、インタプリタがプログラムの実行中にプロファイルを行い、JITコンパイラによりコンパイルされたJITコードがプロファイル結果を利用する第１の実装方法に従うとして説明したが、本願発明は、プログラムの実行中にインタプリタ自身がプロファイル結果をキャッシュして利用する第２の実装方法、及び最適化レベルの低いJITコードがテスト結果をプロファイルし、最適化レベルの高いJITコードがプロファイル結果を利用する第３の実装方法により実装することも可能である。
【００９６】
図１２Ａは、第１の実装方法における、再利用プログラムの構成モジュール１２１２〜１２１８と、JITコンパイラ１２０６と、インタプリタ１２０８と、JITコード１２１０の関係を示した図である。第１の実装方法では、再利用可能性判定モジュール１２１４と、プロファイリング・モジュール１２１６は、実行対象のプログラムを実行中のインタプリタ１２０８により呼び出される。また、再利用処理モジュール１２１２は、実行対象のプログラムのコンパイル時にJITコンパイラ１２０６により呼び出される。また、監視モジュール１２１８は、型情報に対する操作がインタプリタ１２０８によりなされる場合にはインタプリタ１２０８により、また、型情報に対する操作がJITコード１２１０によりなされる場合にはJITコード１２１０により呼び出される。
【００９７】
図１２Ｂは、第２の実装方法における、再利用プログラムの構成モジュール１２１４〜１２２０と、JITコンパイラ１２０６と、インタプリタ１２０８と、JITコード１２１０の関係を示した図である。第２の実装方法は、再利用処理モジュール１２２０が、実行対象のプログラムを実行中のインタプリタ１２０８により呼び出される点で第１の実装方法と異なる。なお、第２の実装方法における再利用処理モジュール１２２０は、上記説明した再利用処理部１４０に対応する図１２Ａに示す再利用処理モジュール１２１２と異なり、再利用コードを生成するのではなく、名前空間と引数のペアの値の一致を条件として、実行結果を直接再利用する機能をインタプリタ１２０８に提供する。
【００９８】
図１２Ｃは、第３の実装方法における、再利用プログラムの構成モジュール１２１２〜１２１８と、JITコンパイラ１２０６と、インタプリタ１２０８と、JITコード１２１０の関係を示した図である。第３の実装方法は、再利用可能性判定モジュール１２１４とプロファイリング・モジュール１２１６が、JITコード１２１０により呼び出される点で第１の実装方法と異なる。なお、第３の実装方法では、JITコンパイラ１２０６は、再利用処理モジュール１２１２を呼び出して最適化レベルの高いJITコードを生成する前に、図１２Ｃに図示しない新規のモジュールを呼び出して、最適化レベルの低いJITコードとして、再利用可能性判定モジュール１２２２とプロファイリング・モジュール１２２４を呼び出すJITコード１２１０を生成する。以上のように、上記の実施形態に変更又は改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【００９９】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【図１】
0005506721.tif 000002
【図２】
0005506721.tif 000003
【図３】
0005506721.tif 000004
【図４Ａ】
0005506721.tif 000005
【図４Ｂ】
0005506721.tif 000006
【図５Ａ】
0005506721.tif 000007
【図５Ｂ】
0005506721.tif 000008
【図６】
0005506721.tif 000009
【図７】
0005506721.tif 000010
【図８】
0005506721.tif 000011
【図９】
0005506721.tif 000012
【図１０】
0005506721.tif 000013
【図１１】
0005506721.tif 000014
【図１２Ａ】
0005506721.tif 000015
【図１２Ｂ】
0005506721.tif 000016
【図１２Ｃ】
0005506721.tif 000017