(57)【特許請求の範囲】
【請求項１】
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに接続されたメモリと、を備えるコンピュータ・システムであって、
前記メモリは、オブジェクト指向プログラムの一部を成す複数のオブジェクト指向クラスを備え、前記オブジェクト指向プログラムを第１のコンパイル単位と少なくとも１つの別のコンパイル単位との組み合わせによって定義する、前記メモリに常駐する前記第１のコンパイル単位と、
前記メモリに常駐するとともに、前記少なくとも１つのプロセッサが実行するコンパイラ・プログラムと
を格納し、
前記コンパイラ・プログラムが、コンピュータ・システムに対して、
新たなオブジェクトを割り当てる前記第１のコンパイル単位中の各命令を、前記第１のコンパイル単位中に存在するクラスである可視のクラスから得られる該クラスの命令の接続図情報と、前記第１のコンパイル単位中に存在する前記クラスが参照する特定のクラスパス中で可視の前記第１のコンパイル単位の外部に存在するクラスから得られる該外部に存在するクラスの命令の接続図情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するエスケープ分析機構部と、
前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、当該少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるオブジェクト割り当て機構部と、
選択したオブジェクトのメソッド用に、オブジェクトのスタック割り当てを使用する第１の版とオブジェクトのヒープ割り当てを使用する第２の版とから成る２つの版のコードを生成するコード生成器部と、
前記オブジェクト割り当て機構部による割り当ての際に記録された、前記第１のコンパイル単位中に存在するクラスの命令の依存関係情報と、前記第１のコンパイル単位中に存在するクラスの命令に依存する該第１のコンパイル単位の外部に存在するクラスのインスタンス・データの推定サイズ情報とに基づいて、前記呼び出しスタック・フレームに割り当てられた前記命令が前記第１のコンパイル単位の外部に存在するクラスに依存し、かつ該クラスをインスタンス化したインスタンス・データのサイズ情報が前記推定サイズ情報に一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択する実行時コード・セクタ部と
をコンピュータに対して実現した
システム。
【請求項２】
コンピュータ・システムに対して第１のコンパイル単位と少なくとも１つの別のコンパイル単位とを備えたオブジェクト指向プログラムにおいて、オブジェクトをメモリに割り当てる、コンピュータ実行可能な方法であって、前記コンピュータ・システムに対して、
（Ａ）前記第１のコンパイル単位をコンパイルするステップと、
（Ｂ）前記第１のコンパイル単位のコンパイル中に、前記第１のコンパイル単位中に存在するクラスである可視のクラスから得られる該クラスの命令の接続図情報に基づいて、新たなオブジェクトを割り当てる各命令を、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つにエスケープ分析機構により分類し、前記エスケープ分析機構によりエスケープなしに分類された命令が生成した少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるステップと
を実行させる
方法。
【請求項３】
前記ステップ（Ｂ）が、
新たなオブジェクトを割り当てる各命令を、前記第１のコンパイル単位中に存在するクラスから得られる該クラスの命令の接続図情報と、前記第１のコンパイル単位中に存在する前記クラスが参照する前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視であるクラスから得られる該外部に存在するクラスの命令の接続図情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するステップと、
前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるステップと
を含む、
請求項２に記載の方法。
【請求項４】
前記ステップ（Ｂ）が、
選択したオブジェクトのメソッド用に、オブジェクトのスタック割り当てを使う第１の版とオブジェクトのヒープ割り当てを使う第２の版とから成る２つの版のコードを生成するステップと、
前記割り当てるステップの際に記録された、前記第１のコンパイル単位中に存在するクラスの命令の依存関係情報と、前記第１のコンパイル単位中に存在するクラスの命令に依存する該第１のコンパイル単位の外部に存在するクラスのインスタンス・データの推定サイズ情報とに基づいて、前記呼び出しスタック・フレームに割り当てられた前記命令が前記第１のコンパイル単位の外部に存在するクラスに依存し、かつ該クラスをインスタンス化したインスタンス・データのサイズ情報が前記推定サイズ情報に一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択するステップと
を含む、
請求項２に記載の方法。
【請求項５】
コンピュータ・システムに対して、第１のコンパイル単位と少なくとも１つの別のコンパイル単位とを備えたオブジェクト指向コンピュータ・プログラムにおいて前記第１のコンパイル単位中のオブジェクトをメモリに割り当てる方法を実行させるためのコンピュータ実行可能なプログラムであって、前記プログラムは、前記コンピュータ・システムに対して、
新たなオブジェクトを割り当てる各命令を、前記第１のコンパイル単位中のクラスから得られる該クラスの命令の接続図情報と、前記第１のコンパイル単位中に存在する前記クラスが参照する前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視であるクラスから得られる該外部に存在するクラスの命令の接続図情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するステップと、
前記分類するステップでエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、当該オブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるステップと、
選択したオブジェクトのメソッド用に、オブジェクトのスタック割り当てを使う第１の版とオブジェクトのヒープ割り当てを使う第２の版とから成る２つの版のコードを生成するステップと、
前記割り当てるステップの際に記録された、前記第１のコンパイル単位中に存在するクラスの命令の依存関係情報と、前記第１のコンパイル単位中に存在するクラスの命令に依存する該第１のコンパイル単位の外部に存在するクラスのインスタンス・データの推定サイズ情報とに基づいて、前記呼び出しスタック・フレームに割り当てられた前記命令が前記第１のコンパイル単位の外部に存在するクラスに依存し、かつ該クラスをインスタンス化したインスタンス・データのサイズ情報が前記推定サイズ情報に一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つを選択するステップと
を実行させる
コンピュータ実行可能なプログラム。
【請求項６】
（Ａ）オブジェクト指向プログラムの一部を成す複数のオブジェクト指向クラスを備えた第１のコンパイル単位をコンパイルするコンパイラであって、前記オブジェクト指向プログラムが前記第１のコンパイル単位と少なくとも１つの別のコンパイル単位との組み合わせによって定義されている、コンパイラ・プログラムを備えたコンピュータ実行可能なプログラムであって、
前記コンパイラ・プログラムが、コンピュータ・システムに対して、
（Ａ１）新たなオブジェクトを割り当てる、前記第１のコンパイル単位中の各命令を、前記第１のコンパイル単位中に存在するクラスである可視のクラスから得られる該クラスの命令の接続図情報と、前記第１のコンパイル単位中に存在する前記クラスが参照する前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視のクラスから得られる該外部に存在するクラスの命令の接続図情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するエスケープ分析機構と、
（Ａ２）前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるオブジェクト割り当て機構と、
（Ａ３）選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使用する第１の版とオブジェクトのヒープ割り当てを使用する第２の版とから成る２つの版のコードを生成するコード・ジェネレータと、
（Ａ４）前記オブジェクト割り当て機構による割り当ての際に記録された、前記第１のコンパイル単位中に存在するクラスの命令の依存関係情報と、前記第１のコンパイル単位中に存在するクラスの命令に依存する該第１のコンパイル単位の外部に存在するクラスのインスタンス・データの推定サイズ情報とに基づいて、前記呼び出しスタック・フレームに割り当てられた前記命令が前記第１のコンパイル単位の外部に存在するクラスに依存し、かつ該クラスをインスタンス化したインスタンス・データのサイズ情報が前記推定サイズ情報に一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択する実行時コード・セクタと
を実現させる
プログラム。
【請求項７】
請求項２〜４の方法をコンピュータに対して実行させるコンピュータ実行可能なプログラムを記憶したコンピュータ可読な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、データ処理分野に関する。本発明は，特に、オブジェクト指向システムにおいてオブジェクトを生成する場所に関する。
【０００２】
【従来の技術】
コンピュータ時代の幕開け以来、コンピュータ・システムは進化し続けきわめて複雑な装置になった。また、今日では、コンピュータ・システムは様々な装置に使われている。コンピュータ・システムは、通常、ハードウェア（たとえば半導体装置や回路基盤など）とソフトウェア（コンピュータ・プログラムとも呼ばれる）の組み合わせを備えている。半導体プロセスとコンピュータ・アーキテクチャの進歩によってコンピュータのハードウェア性能が向上するのに伴い、性能が向上したハードウェアを利用すべく、コンピュータ・ソフトウェアはますます複雑になってきた。この結果、今日のコンピュータ・システムは、わずか数年前よりずっと強力になっている。
【０００３】
コンピュータ・システムは、通常、コンピュータの基本機能を制御するオペレーティング・システム・ソフトウェアと、このオペレーティング・システムの制御下で実行され所望の作業をこなす少なくとも１つのアプリケーション・プログラムとを備えている。たとえば、典型的なＩＢＭパーソナル・コンピュータは、ＯＳ／２オペレーティング・システムを実行している。そして、このＯＳ／２オペレーティング・システムの制御下で、ユーザは、ワード・プロセッサなどのアプリケーション・プログラムを実行することができる。また、コンピュータ・システムの機能が増大するのにつれて、高性能コンピュータ・システム用に設計されたアプリケーション・ソフトウェアは、きわめて強力になった。さらに、ソフトウェアの開発費用が増大し続けている。というのは、プログラムが強力かつ複雑になるほど、作成するのにより多くの時間がかかり、したがって、より多くの金銭がかかるからである。
【０００４】
アプリケーション・ソフトウェア・プログラムの性能を向上させながら、付随する開発費用を低減させる方法の一つに、オブジェクト指向プログラミングの概念を使うものがある。オブジェクト指向プログラミングを使用する目的は、小さくて再使用可能な「オブジェクト（object）」と呼ばれるプログラム部品を生成することである。オブジェクトを組み合わせたり再使用したりして、新たなプログラムを迅速かつ容易に生成することができる。これは、一組の積み木を繰り返し使用して多種多様な構造物を構築するアイデアに似ている。オブジェクトのモジュール的側面と再使用可能な側面によって、通常、新たなプログラムを開発するのが速くなる。さらに、包括的な一組を構成する十分に試験済みのオブジェクト群を生成して再使用することにより、新たなコンピュータ・プログラムを開発する、より安定で、均質で、一貫した方法を確立することができる。
【０００５】
サン・マイクロシステムズが開発したJava(R)（サン・マイクロシステムズの商標）プログラミング言語は、現代的なオブジェクト指向プログラミング言語の一つであり、近年きわめて一般的になった。プログラマーの観点からのJava(R)プログラミング言語の利点の一つは、メモリの割り当てと再使用を、実行時システムが全体として処理している点である。これにより、プログラマーは不必要なオブジェクトを破棄する時期と方法を決める負担から解放される。Java(R)では、（基本型のオブジェクトを除く）すべてのオブジェクトを、共通の「ヒープ（heap）」すなわちメモリのセクションから割り当てる。次いで、ガーベッジ・コレクション機構がヒープ中のオブジェクトを監視して定期的に不必要なオブジェクトを削除する。これにより、ユーザのプログラムがもはやアクセスすることのないオブジェクトが占有しているヒープ領域を再使用することが可能になる。
【０００６】
Java(R)が行なうメモリの自動割り当てと再使用の問題点の一つは、ユーザが自分のプログラムのパフォーマンスをほとんど制御できないという点である。つまり、オブジェクトを割り当てるたびに、所定のコストが発生する。なぜなら、メモリ・マネージャが自分のデータ構造を更新するからである。さらに、ガーベッジ・コレクションを行なっている間にオブジェクトを再使用するには、余分のコストを払わねばならない。これらのコストは個々に見れば小さいけれども、オブジェクトの割り当てと再使用をきわめて頻繁に行なうと、メモリ・マネージャがオブジェクト用にメモリの割り当てと再使用をする際に費やす時間は、プログラムの実行時間のかなりの部分を占めるようになる。
【０００７】
Java(R)のメモリ管理に要するオーバーヘッドは、Ｃ＋＋プログラミング言語のそれよりもはるかに大きい。これは、主として、Java(R)オブジェクトをすべてヒープから割り当てているからである。Ｃ＋＋では、プログラマーは、オブジェクトの割り当てに関してJava(R)よりも大きな制御権を有している。特に、Ｃ＋＋のプログラマーは、あるメソッドにとってローカルであるオブジェクトを宣言することができる。このようなオブジェクトは、当該メソッドを呼び出すと存在するようになり、当該メソッドの呼び出しが終了すると自動的に再使用される。さらに、このようなオブジェクトを割り当てるための実行時コストは、本質的に零である。なぜなら、このようなオブジェクトは、当該メソッドの呼び出しスタック・フレーム中の空き領域を占めるにすぎないからである。呼び出しスタック・フレームにオブジェクトを付加することは、スタック・ポインタを移動させる量が増える、ということを意味するにすぎず、しかも、これを行なうのに余分の命令が必要になることはない。このことをJava(R)の場合と比較する。Java(R)では、オブジェクトが生成されると、それがいかに小さくあるいはいかに一時的であろうとも、常に、実行時メモリ・マネージャのオーバーヘッドを招来する。
【０００８】
近年、コンパイラ技術の研究者は、Java(R)オブジェクトをすべてヒープから割り当てるのではなく、一部のJava(R)オブジェクトをメソッドのスタック・フレームに割り当てる方法について研究している。これにより、基本Java(R)機能の性能が向上する。特に、もし自分を生成したメソッドを超えない「寿命（lifetime）」を有するJava(R)オブジェクトを検出できるコンパイラがあるならば、当該コンパイラは、これらのオブジェクトを、ガーベッジ・コレクションしたヒープから割り当てる代わりに、メソッドのスタックに自動的に割り当てることができる。この結果、パフォーマンスが向上する。どのオブジェクトをメソッドのスタックに割り当てうるかを判断するのに使う技術は、「エスケープ分析（escape analysis)」と呼ばれている。このアイデアの核心は、自分を生成したメソッドから「エスケープ（逸脱）」していない寿命を有するオブジェクトはどれであるかを判断する点にある。エスケープ分析は、チョイらの『Java(R)のためのエスケープ分析』なる論文の第１〜１９頁に記載されている（Choi et al., "Escape Analysis for Java(R)", in Proceedings of the Conference on Object Oriented Programming, Systems, and Languages (OOPSLA), Denver, CO (November 1999), p.1-19.）。チョイらが述べているように、エスケープ分析がオブジェクトをメソッドのスタックに割り当てることに限定されるのは、オブジェクトの寿命が自分を生成したメソッドからエスケープしない場合である。
【０００９】
コンパイラがオブジェクトをスタックに割り当てる試みは、部分コンパイル環境ではなされなかった。というのは、部分コンパイル環境では、コンパイル単位をまたぐ呼び出しが存在するため、また、実行時まで解決しないメソッド呼び出しが存在するために、プログラム中のクラスとメソッドのすべてがコンパイル時に既知すなわち可視であるとは限らないからである。上述したように、チョイらのエスケープ分析を実行するには、生成されるオブジェクトの寿命を知っている必要がある。部分コンパイル環境のプログラムはコンピュータ・プログラムを実行するのに必要なクラスをすべて備えているわけではないので、あるオブジェクトの寿命を判断できない場合がある。これらの理由により、部分コンパイル環境ではエスケープ分析を使わなかった。したがって、部分コンパイル環境にはJava(R)オブジェクトをメソッドの呼び出しスタックに割り当てるシステムと方法がない。この結果、コンピュータ産業は、本来ならメソッドのスタックに割り当てることのできるJava(R)オブジェクトをヒープから割り当てざるをえないことによって生じる性能上の不当な限界に苦しみ続けることになる。
【００１０】
【課題を解決するための手段】
好適な実例によると、オブジェクト指向の機構と方法を用いることにより、ある条件下で、部分コンパイル環境においてJava(R)オブジェクトをメソッドの呼び出しスタックに割り当てることが可能になる。好適な実例によるエスケープ分析を実行するときには、可視であるクラスだけを考慮に入れる。本発明の第１の側面では、次のことを保証する控え目な仮定を行なう。すなわち、オブジェクトを呼び出しスタックに割り当てるのは、現在のコンパイル単位中のクラスを調べるだけで、それが安全であると確かめうるときだけである。本発明の第２の側面では、可視クラスの概念を拡張して、ユーザ定義のクラスパス中に存在する他のクラスを含める。このユーザ定義のクラスパスは、プログラム実行中にクラスを見つけるのに使う予期される実行時のクラスパスと一致する。あるメソッドに対するスタック割り当てをするという判断が、現在のコンパイル単位の外部に存在するクラスに依存する場合、当該メソッド用に２つの版の実行時コードを生成する。一方の版ではすべてのオブジェクトをヒープから割り当て、他方の版では一部または全部のオブジェクトを呼び出しスタックに割り当てる。あるメソッドに対してスタック割り当てをするという判断をする際に調べたコンパイル単位の外部に存在するクラスごとに、当該不可欠なクラスに関する情報を当該メソッドと一緒に格納する。実行時には、クラス・ローダが、不可欠なクラスの各々の実行時版が当該クラスに関するすべての格納済みの情報と一致することを確認する。すべての不可欠なクラス用のすべての情報が一致する場合、スタック割り当てを使う版のメソッドを実行時に使用しても、差し支えない。そうでない場合には、ヒープ割り当てを使うメソッドを使用する必要がある。
【００１１】
【発明の実施の形態】
本発明は、オブジェクト指向プログラミング技法に関する。オブジェクト指向プログラミングにあまり精通していない人のために、下の概観の章では、本発明を理解するのに役立つ多くの概念を紹介する。
【００１２】
１．概観
【００１３】
〔オブジェクト指向技術、対、手続き型技術〕
オブジェクト指向プログラミングとは、協働するオブジェクト群の集積体としてプログラムを構築する実装（implementation) 方法のことである。オブジェクトは、各々、あるクラスのインスタンスを表わしている。クラスは、すべて、継承関係を通じて結合された、１つの階層を構成するクラス群の一員である。オブジェクト指向プログラミングと標準の手続き型プログラミングとの相違点は、オブジェクト指向プログラミングが、コンピュータ・プログラムを作成するための基本構成要素として、アルゴリズムではなく、オブジェクトを使う点である。この相違点は、オブジェクト指向プログラミング技術の設計目的が手続き型プログラミング技術の設計目的とまったく異なるという事実に起因する。
【００１４】
手続きベースの設計では、問題を解決する過程全般に焦点を当てている。一方、オブジェクト指向の設計では、問題を自律構成要素群の集合に分解する方法に焦点を当てている。自律構成要素とは、協働して問題の解決方法を提供しうるもののことである。オブジェクト指向技術の自律構成要素とは、無論、オブジェクトのことである。換言すると、オブジェクト指向技術が手続き型技術と顕著に異なるのは、問題を協働するオブジェクトの集合に分解するのであって、階層構造を成すネスト（入れ子）状のコンピュータ・プログラムすなわちプロシージャに分解するものではないからである。
【００１５】
したがって、純粋なオブジェクト指向プログラムは、オブジェクトと呼ばれるコード構成要素から構成されている。各オブジェクトは、識別可能でカプセル化されたコード片であり、クライアントが要求すると少なくとも１つのサービスを提供する。概念的には、オブジェクトは、２つの部分、すなわち外部オブジェクト・インタフェースと内部オブジェクト・データを備えている。特に、すべてのデータはオブジェクト・インタフェースによってカプセル化されているので、あるオブジェクトが別のオブジェクトと交信するには、そのオブジェクト・インタフェースを介す必要がある。カプセル化されたデータを取り込んだり、処理したり、操作したりする唯一の方法は、オブジェクト上で定義されているメソッドを介すものである。これにより、オブジェクトの内部データ部を外乱から保護することができる。さらに、あるオブジェクトは別のオブジェクトの内部実装にアクセスできないから、当該内部実装を変更してもプログラムの他の側面に影響を与えることがない。
【００１６】
このように、オブジェクト・システムは、サービスの要求者（クライアント・オブジェクト）をサービスの提供者（サーバ・オブジェクト）から十分に定義されたカプセル化インタフェースによって隔離している。したがって、古典的なオブジェクト・モデルでは、クライアント・オブジェクトが要求メッセージ（たとえばメソッド呼び出し）をサーバ・オブジェクトに送って必要なあるいは所望の機能を実行している。この要求メッセージは、特定のサーバ・オブジェクトを特定するとともに、当該サーバ・オブジェクトが実行すべきメソッドを指定している。また、必要なパラメータの供給も行なう。サーバ・オブジェクトは、要求メッセージを受け取って解釈する。それにより、実行すべきサービスが何であるかを判断することができる。
【００１７】
オブジェクトに関する操作は、すべて、あるオブジェクトから別のオブジェクトを呼び出すメソッドとして表現されているから、メソッドは、別のプロセス中のオブジェクトが呼び出してもよい。あるプロセス中に常駐するとともに、別のプロセス（たとえば遠隔にあるコンピュータ・システム中のプロセス）中のオブジェクトのメソッドを呼び出すことのできるオブジェクトは、分散オブジェクトと呼ばれている。
【００１８】
多くの分散オブジェクト・システムでは、遠隔地にあるオブジェクト同士が通信リンクを介して相互作用することができる。分散オブジェクト・システムでは、ある場所にある「クライアント・オブジェクト」が別の場所（たとえば遠隔地）にある「サーバ・オブジェクト」のメソッドを呼び出す。このクライアント−サーバ型のオブジェクト相互作用によって、分散オブジェクト・システムの基礎が形成されている。
【００１９】
オブジェクト指向プログラミングにおける別の中心概念が、クラスである。クラスとは、オブジェクトの型を決めるテンプレート（型板）のことである。クラスは、当該クラスに属すオブジェクトから成る構成体の概要を示している。クラスを定義すると、当該クラスに属す新たなオブジェクトを生成する際に、その定義を一からすべて作成する必要なく生成することができるようになる。オブジェクト指向プログラミングのこの特徴により、既存の定義の再使用性が向上するとともに、プログラム・コードの効率的な使用が促進される。各クラスは、当該クラスの機能すなわち属性を決める独自の構成データを備えている。ある既存のクラス用の構成データを変更すると、当該既存のクラスは新たなクラスに変化する。
【００２０】
現在、オブジェクト指向プログラミング技法をサポートしているコンピュータ言語には多くのものがある。たとえば、Ｓｍａｌｌｔａｌｋ、Ｏｂｊｅｃｔ  Ｐａｓｃａｌ、Ｃ＋＋、およびJava(R)は、すべて、程度の差こそあれオブジェクト指向プログラミングをサポートしているプログラミング言語の例である。
【００２１】
〔Java(R)プログラミング言語〕
Java(R)は、サン・マイクロシステムズが設計した現代的なオブジェクト指向プログラミング言語であり、近年、一般的になった。Java(R)は、多くの特徴と利点を備えているので、使用するのに理想的なプログラミング言語である。第１に、Java(R)の特別な設計目的は、一般に「アプレット」と呼ばれている小さなプログラムを生成することである。アプレットは、ネットワーク中の集中サーバ群に常駐することができ、必要なときにだけクライアント・マシンに配信される。第２に、Java(R)は、プラットフォームから完全に独立している。Java(R)プログラムは、１度書けば、Java(R)仮想マシン（ＪＶＭ）を備えた任意の型のプラットフォームで実行することができる。ＪＶＭモデルは、大部分のコンピュータ・メーカーがサポートしている。したがって、ソフトウェア・ベンダーは、多種多様な会社が製造したハードウェア・システムとソフトウェア・システムを使用することができる。最後に、Java(R)はオブジェクト指向言語である。すなわち、Java(R)で書かれたソフトウェアは、オブジェクト指向プログラミング技法の利点を利用することができる。
【００２２】
他のオブジェクト指向システムと同様に、Java(R)において操作を実行するには、あるオブジェクトが別のオブジェクトのメソッドを呼び出すことにより行なう。これらのオブジェクトは、同じマシンにローカルに常駐していてもよいし、別のコンピュータあるいはシステムに物理的に搭載されている別々のＪＶＭ群に常駐していてもよい。
【００２３】
〔Java(R)の呼び出しスタック〕
Java(R)プログラミング言語は、少なくとも１つの呼び出しスタックを定義している。呼び出しスタックは、メソッドを呼び出すときに情報を格納するのに使う。図１は、様々な状態における呼び出しスタック１００の様子を示す図である。図１（ａ）は、メソッドを呼び出す前の呼び出しスタック１００を示す図であり、スタック・ポインタ１１０はスタック１００の底に位置している。エントリは、スタック１００の下から上（ボトムアップ）に格納する。留意点を挙げると、スタック・ポインタはスタックの天井に位置させることもできる。その場合、エントリは、スタックの上から下（トップダウン）に格納する。図１（ｂ）は、メソッドＡを呼び出したときに起こる状態を示す図である。メソッドＡ用の呼び出しスタック・フレーム１２０がスタックにプッシュされている。スタック・ポインタ１１０は、スタック１００の、次に使用可能な場所に移動している。
【００２４】
呼び出しスタック・フレームには、多種多様な型のデータを格納することができる。たとえば、メソッドが呼び出されたときに、全プロセッサ・レジスタの退避状態を呼び出しスタック・フレームに格納することができる。この結果、メソッドが完了した時点で、これらの値の全部または一部を復旧させることができる。また、呼び出しスタック・フレームには、メソッドにとってローカルな任意の変数も格納することができる。したがって、ローカル変数として整数ｍを宣言すると、呼び出しスタック・フレームには、整数ｍに対応するメモリ割り当てがなされる。従来技術の認識によれば、呼び出しているメソッドをエスケープしない寿命を有するオブジェクト呼び出しも、呼び出しスタック・フレームに格納することができる。
【００２５】
次に、図１（ｂ）と図１（ｃ）を参照する。いまメソッドＡの実行中にメソッドＢを呼び出すものと仮定する。この場合、呼び出しスタック１００にメソッドＢ用のスタック・フレーム１３０をプッシュしたのち、スタック・ポインタ１１０を次に使用可能な場所に移動させる。次に、図１（ｃ）と図１（ｄ）を参照する。いまメソッドＢが自分自身を呼び出すものと仮定する。この場合、呼び出しスタック１００にメソッドＢ用の別のスタック・フレーム１４０をプッシュしたのち、スタック・ポインタ１１０を次に使用可能な場所に移動させる。次に、図１（ｄ）と図１（ｅ）を参照する。いまメソッドＢの第２の呼び出しがメソッドＣを呼び出すものと仮定する。この場合、呼び出しスタック１００にメソッドＣ用のスタック・フレーム１５０をプッシュしたのち、スタック・ポインタ１１０を次に使用可能な場所に移動させる。この時点で、メソッドＣは他のメソッドを呼び出さずに実行を完了するものと仮定する。この場合、図１（ｆ）に示すように、スタック・ポインタ１１０をメソッドＣ用のスタック・フレーム１５０の開始位置まで下げる。これにより、スタック・フレーム１５０用に使っていた、呼び出しスタック１００の領域を効率的に再使用することができる。図１（ａ）〜図１（ｆ）（特に図１（ｆ））に示す例によって明らかになる点を挙げれば、呼び出しスタックにオブジェクトを割り当てても余分なオーバーヘッドは生じない。ただし、スタック・ポインタ１１０を少しばかり遠くに移動させてオブジェクト用に空き領域を作る必要がある。しかし、このことによって実行時性能にペナルティが生じることはない。このため、一般に、できるだけ多くのオブジェクトを呼び出しスタックに割り当てるほど、結果として得られるコード（すなわちプログラム）のパフォーマンスは向上する。
【００２６】
Ｃ＋＋とJava(R)の間の相違点を図２と図３に示す。まず図２（ａ）を参照する。いま「Square」は特定の型のオブジェクトの名前であると仮定する。Ｃ＋＋のプログラマーは、オブジェクトである「型」を有する変数を宣言することができる。図２（ａ）に示すように、「Square k」なる文は、オブジェクトである「Square」型の変数「k 」の宣言である。図２（ａ）に示すように変数をオブジェクトとして定義すると、当該オブジェクトは、図２（ｂ）に示すように、メソッド用の呼び出しスタック・フレームに直接に割り当てることができる。ｋに対応するSquareオブジェクト２３０は、Ａ用の呼び出しスタック・フレーム２２０に格納する。
【００２７】
Java(R)では、変数は、オブジェクトを表さず、オブジェクトへの参照（すなわちポインタ）を表わす。図３（ａ）を参照すると、Square k = new Square() なる宣言は、変数ｋはSquare型の新たなオブジェクトへの参照である、ということを言う文である。図３（ｂ）に示すように、メソッド用のスタック・フレーム２２０には（ｋを表わす）参照３３０だけを格納する。参照３３０が指し示すSquareオブジェクト３４０は、図３（ｃ）に示すように、ヒープから割り当てる。
【００２８】
〔従来技術のエスケープ分析〕
チョイらの『Java(R)のためのエスケープ分析』なる論文（Choi et al., "Escape Analysis for Java(R)", in Proceedings of the Conference on Object Oriented Programming, System, and Language (OOPSLA), Denver, CO (November 1999), p. 1-19.)で行なう「エスケープ分析」では、あるオブジェクトの寿命が当該オブジェクトを生成したメソッドを「エスケープ（逸脱）」していないかどうか判断する。エスケープしていない場合には、図４に示すように、メソッド用の呼び出しスタック・フレーム２２０にオブジェクト自身４４０を割り当てることができる。すなわち、ｋがたとえ参照３３０のままであっても、それが指し示すオブジェクト４４０も、当該オブジェクト４４０を生成したメソッド用の呼び出しスタック・フレーム２２０に格納することができる。図１を参照して上述したように、メソッドの呼び出しスタック・フレームにオブジェクトを割り当てると、コンピュータ・プログラムのパフォーマンスが顕著に向上する。
【００２９】
図５（ａ）〜図５（ｄ）にJava(R)疑似コードの例を示し、「エスケープなし」（図５（ａ））、「グローバル・エスケープ」（図５（ｂ））、および「引数エスケープ」（図５（ｃ）と図５（ｄ））から成る、割り当て命令の例を説明する。図５（ａ）では、変数ｋをSquare型の新たなオブジェクトとして定義している。いま、ｋが参照している割り当てられたオブジェクトの寿命がメソッドＡをエスケープしていないものと仮定する。従来技術のチォイらの手法では、エスケープなし割り当てに対応するオブジェクトは、（いくらかの制約があるものの）すべて、メソッドの呼び出しスタック・フレームに割り当てる。図５（ｂ）は、図５（ａ）の場合と同じ変数宣言を示している。しかし、メソッドＡ（）の後半には、k が参照しているオブジェクトへの参照である変数classVarの宣言が別に存在する。いまclassVarはクラス変数の宣言であると仮定する。この場合、classVarの寿命はメソッドＡ（）を超えてグローバルになるので、この割り当ては、グローバル・エスケープの場合になる。従来技術のチォイらの手法では、グローバル・エスケープであるオブジェクトは、すべて、ヒープに割り当てる。
【００３０】
図５（ｃ）には、k に対して図５（ａ）と同じ宣言文がある。しかし、図５（ｃ）には、k が参照している割り当てられたオブジェクトへの参照をメソッドＡ（）から戻す文がある。この戻り値は、割り当てられたオブジェクトの寿命がメソッドＡ（）を超える可能性のあることを意味している。しかし、その範囲は分からない。図５（ｄ）は、引数エスケープの別の場合を示す図である。L.addToList(k)なる命令は、参照k をリストに付加するものである。したがって、k が参照している割り当てられたオブジェクトは、メソッドＡ（）の外部からアクセスされる可能性がある。しかし、必ずアクセスされるというわけではない。これらは、「引数エスケープ」の場合を示すものである。引数エスケープの場合、引数または戻り値によって、あるオブジェクトの寿命は、当該オブジェクトを生成したメソッドの範囲を超える可能性がある。従来技術のチォイらの手法では、引数エスケープをグローバル・エスケープと同じに扱い、これらをヒープに割り当てている。
【００３１】
図６は、チョイらの論文に開示されている従来技術の方法を、方法６００としてに簡単化した形のフローチャートを示す図である。まず、クラス階層図を作成する（ステップ６１０）。クラス階層図とは、１つのJava(R)プログラム中のすべてのクラス間の継承関係を表わすものである。クラス階層図には、プログラム中のクラスごとに１つのノードが存在する。また、クラスＢがクラスＡを直接に継承している（すなわち「拡張している」）場合、そしてこの場合に限り、クラス階層図には、クラスＢのノードからクラスＡのノードに向かう弧が存在する。
【００３２】
ステップ６１０でクラス階層図を作成したら、ライブ（生）呼び出し図を作成する（ステップ６２０）。ライブ呼び出し図は、Java(R)プログラム中のメソッドであって、当該Java(R)プログラムの実行中に明示的に呼び出すことのできるメソッドごとに１つのノードを備えている。Java(R)プログラムの外部（たとえば「main」）から呼び出しうるメソッドは、「ルート（根）メソッド」と呼ばれている。メソッドＡのノードは、当該メソッドＡに含まれている呼び出しサイトごとにサブノードに至る弧を備えている。呼び出しサイトＳのサブノードからメソッドＢのノードに至る弧が存在するのは、呼び出しサイトＳでメソッドＢを呼び出す可能性がある場合である。定義により、少なくとも１つのルート（根）ノードから一連の有方向の弧をたどることにより、ライブ呼び出し図中のすべてのメソッドに到達することができる。また、実行できないメソッド（「デッド（死）メソッド」）は、ライブ呼び出し図中には表示しない。他のメソッドを呼び出さないメソッドは、「リーフ（葉）メソッド」と呼ばれている。クラス階層図は、仮想メソッド呼び出しサイトで参照し、継承に基づいて呼び出される可能性のあるメソッドを決めるのに使われる。クラス階層図とライブ呼び出し図の作成は、当技術分野では周知である。
【００３３】
ステップ６２０でライブ呼び出し図を作成したら、エスケープ分析を行なうことができる（ステップ６３０）。エスケープ分析とは、（オブジェクトを生成する）各割り当て命令を３つの選択肢、すなわち、エスケープなし、グローバル・エスケープ、および引数エスケープのうちの１つに分類することである。ステップ６３０でエスケープ分析が完了したら、コード（すなわちプログラム）を生成する（ステップ６４０）。その際、エスケープ分析の情報を使って各オブジェクトを割り当てる場所を決める。従来技術のチョイらの手法による方法６００では、エスケープなしのオブジェクトは、メソッドの呼び出しスタック・フレームに割り当てる。一方、グローバル・エスケープおよび引数エスケープであるオブジェクトは、ヒープから割り当てる。しかし、留意点を挙げると、従来技術のチョイらの手法は、部分コンパイル環境では使われることがなかった。なぜなら、すべてのクラスが存在しないと、メソッドの寿命を算出できないからである。したがって、次の点を理解するのが重要である。すなわち、チョイらの論文で教示されているエスケープ分析の原理を部分コンパイル環境に適用することは、従来技術においてはなかった。というのは、チョイらの手法を使う基本規則（すなわち、すべてのクラスが存在しかつ既知である）が、部分コンパイル環境に適合できないからである。
【００３４】
図６のステップ６３０のエスケープ分析の詳細を、図７のフローチャートに示す。まず、ライブ呼び出し図のメソッドをボトムアップ式にソートする（ステップ７１０）。すなわち、ライブ呼び出し図中の、他のメソッドを呼び出さないリーフ・ノードを始めに考慮する。次いで、ソート済みのリストの先頭のメソッドをＭに代入する（ステップ７２０）。次いで、Ｍの接続図を作成する。その際、Ｍから呼び出される可能性のあるメソッド（Ｍi と表記）ごとに接続図情報を組み込む。接続図は、オブジェクトを参照しうる変数とパラメータ、オブジェクトを割り当てる文、および、オブジェクトに含まれるフィールドの間の潜在的な関係を表わしている。続いて、Ｍ中の各オブジェクト割り当てを、グローバル・エスケープ、引数エスケープ、または、エスケープなしのいずれかに分類する（ステップ７４０）。処理する必要のあるメソッドが他にもあれば（ステップ７５０＝ＹＥＳ）、制御をステップ７２０に渡し、処理を続ける。すべてのメソッドの処理が終了すれば（ステップ７５０＝ＮＯ）、ステップ６３０は完了する。留意点を挙げると、本発明の好適な実施形態を説明するという目的に鑑（かんが）みて、ここでは接続図の説明を簡単化してある。接続図の作成方法に関する詳細は、上で参照したチョイらの論文を参照されたい。
【００３５】
次に、図８を参照する。図８は、従来技術に従って呼び出しサイトを処理する特定の方法を方法８００として示す図である。留意点を挙げると、方法８００のステップ群は、図７に示すステップ７３０の間に、メソッドＭの接続図の呼び出しサイトごとに実行するのが望ましい。選択した呼び出しサイトに未処理の潜在ターゲット・メソッドが存在する場合（ステップ８１０＝ＹＥＳ）、次の潜在メソッドを選択してＭi に代入する（ステップ８２０）。次いで、Ｍi の接続図をＭの接続図中にコピーする（ステップ８３０）。次いで、Ｍ中の実際の引数ノードをＭi 中のファントム・パラメータに等価化させる（ステップ８４０）。次いで、Ｍ中の戻り参照ノードをＭi 中の戻り参照値ノードに等価化させる（ステップ８５０）。等価化のプロセスは、複雑であるが、チョイらの論文の第４章に詳述されている。その一般概念は、呼び出し側の実際の引数と被呼び出し側の公式パラメータとが同一である、ということを保証することである。未処理の潜在ターゲット・メソッドがもはや存在しない場合（ステップ８１０＝ＮＯ）、図８の方法８００は終了する。
【００３６】
次に、図９を参照する。図９は、チョイらの論文に記載されている従来技術に従ってオブジェクト割り当てを処理する特定の方法を方法９００として示す図である。図８の方法８００と同様に、図９の方法９００のステップ群は、図７に示すステップ７３０の間に、オブジェクトを割り当てるごとに実行するのが望ましい。まず、Ｍに対応する新たなバイトコード用に、接続図中にオブジェクト割り当てノードを生成する。このオブジェクト割り当てノードには、割り当てたオブジェクトのクラス名を付ける（ステップ９１０）。次いで、この新たなノードを値スタックにプッシュする（ステップ９２０）。この値スタックは、チョイらの論文の第３章に記載されているように、上記バイトコードのセマンティクス（意味構造）をエミュレート（模倣）するのに使う。
【００３７】
エスケープ分析を使って最適化したコードを生成する公知の一方法を、図１０に方法６４０として示す。これは、図６のステップ６４０に対応する。まず、割り当て命令を選択する（ステップ１０１０）。割り当て命令がエスケープしている場合（グローバル・エスケープまたは引数エスケープ）（ステップ１０２０＝ＹＥＳ）、オブジェクトに対してヒープ割り当てを使う、メソッドのコードを生成する（ステップ１０４０）。割り当て命令がエスケープしていない場合（すなわち割り当て命令が「エスケープなし」）（ステップ１０２０＝ＮＯ）、オブジェクトに対してスタック割り当てを使う、メソッドのコードを生成する（ステップ１０３０）。オブジェクト割り当て命令が他にもあれば（ステップ１０５０＝ＹＥＳ）、制御をステップ１０１０に渡して処理を続ける。そして、それを、処理すべきオブジェクト割り当て命令がなくなるまで続ける（ステップ１０５０＝ＮＯ）。
【００３８】
この時点できわめて重要な留意点を挙げると、図６〜図１０について上述した従来技術のエスケープ分析は、すべてのクラスが同時に存在する静的コンパイル環境でしか使われたことがない。あるオブジェクトが当該オブジェクトを生成したメソッドを「エスケープ」しているか否か判断するには、当該オブジェクトの定義と使用方法をすべて知っている必要がある。静的にコンパイルするJava(R)プログラムの場合には、オブジェクトの定義と使用方法をすべて知ることができる。しかし、部分コンパイル環境では、あるコンパイル単位に存在するクラスが別のコンパイル単位には存在しない、ということがありうる。したがって、コンパイラは、あるオブジェクトの定義と使用方法をすべて知っているわけではない。なぜなら、コンパイラは、現在コンパイルしている単一のコンパイル単位中のクラスしか考慮しないからである。これらの理由により、従来技術のエスケープ分析は、部分コンパイル環境に適用されたことがない。
【００３９】
２．詳細な説明
【００４０】
好適な実施形態による装置と方法では、部分コンパイル環境（すなわちクラス群が複数のコンパイル単位をまたいで分散している環境）に割り当てられたオブジェクトについてエスケープ分析（従来技術で公知のチョイらのエスケープ分析と同様のもの）を実行する。本発明の装置と方法では、特定のコンパイル単位に存在するクラスについてエスケープ分析を実行し、利用しうる情報に基づいてオブジェクトを呼び出しスタックに割り当てるべきか、ヒープに割り当てるべきかを判断する。他のコンパイル単位中に存在する情報は利用できないから、現在コンパイルを実行しているコンパイル単位の外部に存在するメソッドに対する呼び出しについては、控え目な仮定をする。部分コンパイル環境において相当数のオブジェクトをスタック割り当てすると、実行時におけるコンピュータ・プログラムのパフォーマンスが向上する。
【００４１】
本発明の第２の側面では、本発明の使用者は、単一のコンパイル単位をコンパイルする際に、実行時に参照することになる、別のコンパイル単位の分析情報を使うことができる。単一のコンパイル単位中のクラスだけをコンパイルするのだけれども、当該クラス中のメソッドをスタック割り当てすることに決める際に、別のコンパイル単位中のクラスが実行時に利用可能るなる、と仮定する。あるメソッドをスタック割り当てにすることにきめる際に、実行時に利用可能になる外部クラスを必要とする場合は、常に、当該外部クラスに関する情報を、上記メソッドのコンパイル済みコードと一緒に格納する。メソッド用に２つの版のコンパイル済みコードを生成する。１つは一部にスタック割り当てを使用し、もう１つはヒープ割り当てだけを使用する。実行時に正しい外部クラスが見つからないときには、メソッドのヒープ割り当て版を使用する。実行時に正しい外部クラスが見つかれば、より効率的なスタック割り当て版を使用する。
【００４２】
部分コンパイル環境で使用する、好適な実施形態による方法を図１１に方法１１００として示す。いま、好適な実施形態は部分コンパイル環境で動作しているものと仮定する。ここでは、部分コンパイル環境を、好適な実施形態がコンピュータ・プログラムに存在するクラスの一部しか処理しない場合を意味するものと定義する。部分コンパイル環境の一例として、様々なコンパイル単位を別々にコンパイルし、そのすべてが個別にコンパイルし終わったら、それらを互いにリンクする場合が挙げられる。部分コンパイル環境の別の例として、ＪＩＴ（Just-In-Time）コンパイラが挙げられる。ＪＩＴコンパイラは、コンピュータ・プログラムの一部を、実行時に必要になったときにコンパイルする。コンピュータ・プログラム全体にアクセスすることはない。部分コンパイル環境のさらに別の例として、コンピュータ・プログラムを構成している複数のＪＡＲ（Java(R) Archive）ファイルをコンパイルする場合が挙げられる。
【００４３】
次に、図１１を参照する。図１１に示す好適な実施形態は、複数のＪＡＲファイルをコンパイルすることのできる方法１１００を備えている。まず、ユーザが指定したクラスパスを取得する（ステップ１１１０）。クラスパスは、コンピュータ・プログラムを構成しているＪＡＲファイル群を格納している１つまたは複数の宛先を指し示している。留意点を挙げると、このクラスパスは、空であるかもしれない。その場合、他のコンパイル単位に由来する外部クラスは分析しない。したがって、外部クラスに関する依存関係は生成しない。次に、現在のコンパイル単位中に実際に存在する（すなわち可視である）すべてのクラスでクラス階層図を作成する（ステップ１１２０）。ステップ１１１０のクラスパスが空でない場合には、クラス階層図は、当該クラスパス中にもクラスを備えている。これらのクラスは、現在のコンパイル単位中のクラスが、直接にあるいは間接的に参照するものである。留意点を挙げると、ステップ１１２０で可視のクラスについてクラス階層図を作成する方法は、従来技術のステップ６２０でコンピュータ・プログラム中のすべてのクラスについてクラス階層図を作成する方法と同じである。ステップ６２０のクラス階層図とステップ１１２０のクラス階層図との間の主な相違点は、ステップ１１２０のクラス階層図では可視のクラスしか考慮していない点である。これに対して、従来技術では、コンピュータ・プログラム中のクラスのうち一部しかコンパイル単位に存在しない場合には、ステップ６２０を実行しない。したがって、クラス階層図は作成しない。
【００４４】
次いで、現在のコンパイル単位中の可視のメソッド呼び出しからライブ呼び出し図を作成する（ステップ１１３０）。ステップ１１１０のクラスパスが空でない場合、このライブ呼び出し図も、当該クラスパス中のクラスのメソッドを備えている。これらのメソッドは、現在のコンパイル単位中のメソッドが、直接にあるいは間接的に呼び出しうるものである。ライブ呼び出し図が示しているのは、呼び出しサイトごとに、現在のコンパイル単位中のどのメソッドが、現在のコンパイル単位中のどの別のメソッドを呼び出す可能性があるか、ということである。図１１のステップ１１３０で作成する可視のライブ呼び出し図と、図６のステップ６２０で作成する従来技術のライブ呼び出し図との間の主な相違点は、図１１のステップ１１３０では、現在のコンパイル単位中のメソッドはすべてライブであると仮定している点である。これに対して、図６のステップ６２０では、プログラムの外部から呼ばれる可能性のあるメソッドの「ルート集合」からライブ・メソッドを追跡している。この好適な実施形態では複数のコンパイル単位が存在するから、現在のコンパイル単位中のメソッドがすべてライブであると仮定することは、控え目な仮定である。この控え目な仮定では、オブジェクトをスタック割り当てすることができるのは、詳細な基準に適合している場合だけである。
【００４５】
次いで、修正した控え目型のエスケープ分析を実行する（ステップ１１４０）。その間にライブ呼び出し図の一部を分析して、当該部分図が「最終」であるか否か、すなわち、呼び出されるメソッドがコンパイル時に正確に分かっているか否か判断する。ステップ１１４０におけるエスケープ分析が完了したら、ステップ１１５０で最適化したコードを生成する。留意点を挙げると、ステップ１１５０では、一部のメソッドについてオブジェクトの割り当て方法を含む２つの版のコードを生成する。一方の版ではオブジェクトをスタック・フレームから割り当て、他方の版ではオブジェクトをヒープから割り当てる。実行時に、対象とするメソッドについて適切な版を選択する。ステップ１１５０のコード生成の詳細は、図１６に示す。
【００４６】
好適な実施形態による、図１１のステップ１１４０の詳細を、図１２に方法１１４０として示す。留意点を挙げると、方法１１４０は、図７に示す従来技術の方法６３０に似ている。主な相違点は、図１２のステップ１２３０では接続図を図７のステップ７３０とは異なる仕方で作成・分析している点である。ステップ１２３０とステップ７３０との間の相違点を説明する、ステップ１２３０の詳細を、図１３〜図１７に示すとともに、付随する説明を下で行なう。
【００４７】
ステップ１２３０のエスケープ分析の間に呼び出しサイトを処理する好適な方法を、図１３に方法１２３０Ａとして示す。図１３の方法１２３０Ａにおける呼び出しサイト処理には、単一のコンパイル単位中の呼び出しサイトをコンパイルするときにすべてのクラスが可視であるとは限らないという事実を扱う論理が含まれている。まず、呼び出しサイトが予測可能であるか否かを判断する（ステップ１３１０）。好適な実施形態では、呼び出しサイトが「予測可能」であるのは、実行時に変化しない単一かつ既知のターゲット・メソッドが存在する場合である。呼び出しサイトが予測可能であるか否かの判断の詳細は、図１４について下で説明する。呼び出しサイトが予測可能である場合（ステップ１３１０＝ＹＥＳ）、この呼び出しサイトには存在しうるターゲット・メソッドは、Ｍi だけである（ステップ１３２０）。次いで、Ｍi の接続図をＭの接続図中にマージ（併合）する（ステップ１３３０）。次いで、Ｍについてメソッドの依存関係を記録する（ステップ１３４０）。留意点を挙げると、Ｍ中のオブジェクト割り当てがすべてスタック割り当てであるという判断は、Ｍi が呼び出す他のすべてのメソッドに依存するだけでなく、Ｍi の分析にも依存する。したがって、各メソッドＭを、その分析にＭの分析が依存しているメソッドのリストに関連付ける。ステップ１３４０において、Ｍについての依存関係リストは、Ｍi によって大きくなるとともに、Ｍi を関連付けられた依存関係リスト中のすべてのメソッドによっても大きくなる。次いで、Ｍ中の実際の引数ノードとＭi 中のファントム・パラメータ・リストとを等価化させる（ステップ１３５０）とともに、Ｍ中の戻り参照ノードとＭi 中の戻り参照値とを等価化させる（ステップ１３６０）。これらは、図８のステップ８４０およびステップ８５０と同様である。
【００４８】
呼び出しサイトが予測可能でない場合（ステップ１３１０＝ＮＯ）、呼び出されるメソッドについて悲観的な仮定をしなければならない。すなわち、呼び出されるメソッドに渡されるすべてのパラメータと、呼び出されたメソッドから戻されるオブジェクト参照とは、グローバル・エスケープであると仮定する。これを行なうには、グローバル「ボトム（底）」ノードをＭ中の実際の引数の各々に接続する（ステップ１３７０）とともに、グローバル「ボトム」ノードをＭ中の戻り参照ノードに接続する（ステップ１３８０）。チョイらの論文が教示しているエスケープ分析によると、グローバル「ボトム」ノードから到達可能なオブジェクト割り当てノードは、すべて、グローバル・エスケープに分類される。ステップ１３７０とステップ１３８０を実行することにより保証される点を挙げると、予測不能なメソッドに渡されるものはすべてグローバル・エスケープに分類される。
【００４９】
図１４は、図１３のステップ１３１０において呼び出しサイトを予測可能または予測不能であると判断する方法の詳細を示す図である。まず、targetCount と呼ぶ変数を初期化して「０」にする（ステップ１４１０）。いま、この呼び出しサイトに少なくとも１つの未処理の潜在ターゲット・メソッドが存在する（ステップ１４２０＝ＹＥＳ）ものと仮定すると、Ｍi に、この呼び出しサイトにおける次の潜在ターゲット・メソッドを代入する（ステップ１４３０）。次いで、targetCount をインクリメントする（ステップ１４４０）。次いで、Ｍi が予測可能な種類のメソッドであるか否か判断する（ステップ１４５０）。予測可能なメソッドの例として、静的メソッド、<init>メソッド、private メソッド、final メソッド、および、最終クラス中のメソッドがある。Ｍi が予測可能なメソッドでない場合（ステップ１４５０＝ＮＯ）、この呼び出しサイトは予測不能である（ステップ１４７０）。Ｍi が予測可能なメソッドである場合（ステップ１４５０＝ＹＥＳ）、Ｍi が正しい型のオブジェクトの代わりに呼び出されているか否かを調べる（ステップ１４６０）。換言すると、この呼び出しサイトが正確なクラス名を使っているメソッドＭi を指し示しているか否かを調べる。Ｍi が仮想メソッド呼び出しである場合、呼び出し側オブジェクトを特定することができない（ステップ１４６０＝ＮＯ）。したがって、この呼び出しサイトは予測不能である（ステップ１４７０）。この呼び出しサイトに未処理の潜在ターゲット・メソッドが存在せず（ステップ１４２０＝ＮＯ）、targetCount ＝０の場合（ステップ１４２２＝ＹＥＳ）、これは、処理したメソッドがないことを意味する。すなわち、メソッド呼び出しは、可視のクラスから成る集合の外部に存在するはずである。この結果、この呼び出しサイトは予測不能である（ステップ１４７０）。targetCount ≠０の場合（ステップ１４２２＝ＮＯ）、この呼び出しサイトは予測可能である（ステップ１４２４）。留意点を挙げると、図１４のステップ群は悲観的な仮定を形成している。すなわち、可視のクラスから成る集合の外部の呼び出しは、すべて、予測不能な呼び出しサイトに帰着し、グローバル・エスケープに分類されるので、ヒープ割り当てされる、と仮定している。以上のように、好適な実施形態の呼び出しサイト処理は、きわめて控え目である。すなわち、オブジェクトをメソッドの呼び出しスタックに割り当てるのは、当該メソッドがオブジェクトの寿命をエスケープしないことが保証される場合だけである。
【００５０】
好適な実施形態によるオブジェクト割り当て処理を、図１５に方法１２３０Ｂとして示す。まず、インスタンス化すべきクラスが可視のクラスの集合中に存在するか否か判断する（ステップ１５１０）。ステップ１５１０＝ＹＥＳの場合、接続図中にオブジェクト割り当てノードを生成し、それに割り当てるオブジェクトのクラス名でマーク付けをする（ステップ１５２０）。次いで、新たなオブジェクト割り当てノードを値スタックにプッシュする（ステップ１５５０）。留意点を挙げると、ステップ１５２０とステップ１５５０は、図９に示すチョイらの従来技術の方法におけるステップ９１０およびステップ９２０と同じであるのが望ましい。インスタンス化すべきクラスが現在のコンパイル単位中で可視でない場合（ステップ１５１０＝ＮＯ）、接続図中にオブジェクト割り当てノードを生成し、それに「Java(R)/lang/Object」なるマークを付ける（ステップ１５３０）。このオブジェクト割り当てノードは、接続図における本質的にダミーのオブジェクト割り当てノードであり、「Java(R)/lang/Object」なるマークは任意のものである。次いで、この新たなオブジェクト割り当てノードにグローバル「ボトム」ノードを接続させる（ステップ１５４０）。これにより、新たに生成するノード、および、それから到達可能なすべてのオブジェクトには、スタック割り当てが考慮されない、ということが保証される。次いで、上記新たなオブジェクト割り当てノードを値スタックにプッシュする（ステップ１５５０）。
【００５１】
図１１のステップ１１５０の好適な実装例を、図１６に方法１１５０として示す。まず、割り当て命令を選択する（ステップ１６１０）。現在の割り当て命令がエスケープしている場合（グローバル・エスケープまたは引数エスケープ）（ステップ１６２０＝ＹＥＳ）、現在のメソッドに割り当てられるオブジェクト用にヒープ割り当てを使う、現在のメソッドのコードを生成する（ステップ１６６０）。当該割り当て命令がエスケープなしの場合（ステップ１６２０＝ＮＯ）、現在のオブジェクトのインスタンス・データのサイズが決定可能であるか否かを調べる（ステップ１６３０）。ステップ１６３０＝ＮＯの場合、ヒープ割り当て用のコードを生成する（ステップ１６６０）。当該割り当て命令がヒープなしであり（ステップ１６２０＝ＮＯ）、当該オブジェクトのインスタンス・データのサイズが決定可能である場合（ステップ１６３０＝ＹＥＳ）、当該メソッドはスタック割り当てを使うことができる。好適な実施形態では、ステップ１６４０に示すように、当該メソッド用に２つの版のコードを生成する。１つはスタック割り当て用であり、もう１つはヒープ割り当て用である。実行時には、これら２つの版のうちの１つを使う。その選択は、実行時に、不可欠の外部クラスが存在するか否かによって決める。留意点を挙げると、１つまたは２つの版しか生成しない。そして、当該メソッドにスタック割り当ての機会がある場合、一方の版はこれらすべての割り当てサイトについてスタック割り当てを使い、他方の版はこれらすべての割り当てサイトについてヒープ割り当てを使うようにする。次いで、当該メソッドのサイズ依存関係を記録する（ステップ１６５０）。割り当てるクラスがコンパイル時に既知で（Java(R)/lang/Object以外の）スーパークラスを有する場合、実行時に当該オブジェクトのサイズが変化するのは、異なる版の当該スーパークラスをロードした場合である。したがって、サイズ依存関係は、当該メソッドのコードと一緒に記録する。サイズ依存関係には、コンパイル時に決まる、当該オブジェクト用のインスタンス・データのサイズが含まれている。したがって、コンパイル時におけるインスタンス・データのサイズと、実行時におけるインスタンス・データのサイズとを比較することにより、インスタンス化したクラスのサイズがコンパイル時に検出したものと同一であることを保証することができる。処理すべき割り当て命令が他にも存在する場合（ステップ１６７０＝ＹＥＳ）、制御をステップ１６１０に戻して処理を続ける。そして、それを、処理すべき割り当て命令が存在しなくなるまで続ける（ステップ１６７０＝ＮＯ）。
【００５２】
図１６のステップ１６４０で２つの版のメソッド（１つはスタック割り当て用、もう１つはヒープ割り当て用）を生成したものと仮定すると、実行時にどちらの版のメソッドを使うべきであるかを判断する必要がある。留意点を挙げると、１つの版のメソッドしか生成しなかった場合、図１７のステップ群は、適用できないので、実行する必要がない。上記判断を行なうステップ群を、図１７に方法１７００として示す。まず、Ｃと表記されたクラスをロードする（ステップ１７１０）。Ｃ中には処理すべきメソッドが存在するものと仮定すると（ステップ１７２０＝ＹＥＳ）、Ｃ中のメソッドを１つ選択し、それをＭに代入する（ステップ１７３０）。Ｍが他のクラスに依存していない場合（ステップ１７４０＝ＮＯ）、次のメソッドを選択して処理する。Ｍの、自身のクラスに対する依存情報は、図１３のステップ１３４０で格納してある。したがって、図１７のステップ１７４０では、この格納済みの情報を取り出して、Ｍが他のクラスに依存しているか否かを判断するだけでよい。Ｍが少なくとも１つの他のクラスに依存していると仮定すると（ステップ１７４０＝ＹＥＳ）、Ｍが依存しているクラス群の中から１つ選択して、それをＤに代入する（ステップ１７５０）。次いで、要すれば、クラスＤをロードする（ステップ１７６０）。次いで、クラスＤのメソッド依存関係およびサイズ依存関係と、メソッドＭの格納済みのメソッド依存関係およびサイズ依存関係とを比較する。格納済みのクラスＤに関する情報には、実行時に見られるクラスＤの版と、コンパイル時に見られたクラスＤとが同一であることを保証する、という意味がある。好適な実施形態では、この情報には、クラスＤの最後に修正したタイムスタンプと、クラスＤの本体全体にわたって算出したチェックサムとが含まれている。チェックサムが含まれているのは、クラスＤを変更すると同一のチェックサム値が得られる可能性がほとんどないからである。これらのデータの実行時の値と、コンパイル時に算出して格納済みの値とが一致すれば、クラスＤについてのメソッド依存関係は満たされる。サイズ依存関係を満たすには、クラスのオブジェクトの実行時のサイズとコンパイル時の推定サイズとを比較するだけでよい。
【００５３】
Ｍが依存しているクラスをすべて処理し終えたら（ステップ１７４０＝ＮＯ）、実行時にどちらの版のＭを呼び出すべきかを決める（ステップ１７８０）。ステップ１７７０で調べたメソッド依存関係およびサイズ依存関係のうち１つでも満たされていないものがみつかったら、Ｍのコード・ポインタをヒープ割り当てを使っている版のＭにセットする。そうでない場合には、Ｍのコード・ポインタをスタック割り当てを使っている版のＭにセットする。
【００５４】
２つの異なる版のメソッドを実現し、どちらのメソッドを使うべきかを実行時に動的に選択しているので、従来技術に勝る顕著な利点が得られる。部分コンパイル環境にはスタック割り当ては存在しないと仮定するのではなく、好適な実施形態では、判断により一層の知恵を組み込んでいる。実行時まで待って、スタック割り当てが可能であるか否かを判断している。異なったスーパークラスをロードする可能性があるから、スタック割り当ては不可能である、と盲目的に仮定することはしない。
【００５５】
以上、コンピュータ実装した方法として本発明をを説明したけれども、本発明は、上述した方法ステップ群を実行する装置として実施することもできる。図１８を参照すると、コンピュータ・システム１８００は、たとえばＩＢＭ社製のｉシリーズ・コンピュータ・システムである。しかし，当業者が認識しうる点を挙げると、本発明の機構と装置は、任意のコンピュータ・システムに等しく適用することができる。このことは、コンピュータ・システムが、複雑なマルチ・ユーザ・コンピューティング装置であるか、単一ユーザのワークステーションであるか、組み込み制御システムであるかには無関係である。図１８に示すように、コンピュータ・システム１８００は、プロセッサ１８１０、メインメモリ１８２０、大容量記憶装置インタフェース１８３０、端末インタフェース１８４０、および、ネットワーク・インタフェース１８５０を備えている。これらのシステム構成要素は、システム・バス１８６０を通じて相互接続されている。大容量記憶装置インタフェース１８３０は、大容量記憶装置（たとえば直接アクセス記憶装置（ＤＡＳＤ）１８５５）をコンピュータ・システム１８００に接続するのに使用する。直接アクセス記憶装置（ＤＡＳＤ）１８５５の代表例には、フレキシブル・ディスク１８９５に対してデータを読み書きすることのできるフレキシブル・ディスク駆動装置がある。
【００５６】
好適な実施形態によるメインメモリ１８２０は、データ１８２２、オペレーティング・システム１８２３、コンパイル単位１８２４、クラスパス１８２５、および、コンパイラ／オプティマイザ１８２６を備えている。コンパイル単位１８２４は、オブジェクト指向すなわちオブジェクト・ベースのプログラムの一部を成すものである。コンパイラ／オプティマイザ１８２６は、オブジェクト割り当て機構１８２７および実行時コード・セレクタ１８２９を備えている。オブジェクト割り当て機構１８２７は、エスケープ分析機構１８２８を備えている。エスケープ分析機構１８２８は、エスケープ分析に関し図１１〜図１６で説明したステップ群を好適に実行する。実行時コード・セレクタ１８２９は、図１７のステップ群を好適に実行して、２つの版のメソッドのうち実行時に使用するものを決める。
【００５７】
コンピュータ・システム１８００は、周知の仮想アドレッシング機構を使用している。これにより、コンピュータ・システム１８００のプログラムは、メインメモリ１８２０やＤＡＳＤ装置１８５５など複数の小容量記憶主体にアクセスするのではなく、単一の大容量記憶主体だけにアクセスしているように振る舞うことができる。したがって、データ１８２２、オペレーティング・システム１８２３、コンパイル単位１８２４、クラスパス１８２５、および、コンパイラ／オプティマイザ１８２６はメインメモリ１８２０に常駐しているように示してあるけれども、当業者が認識しうるように、これらのものすべてがメインメモリ１８２０に同時に完全に格納されている必要はない。留意点を挙げると、ここでは、「メモリ」なる用語をコンピュータ・システム１８００の仮想記憶全体を一般的に指し示すように使用している。
【００５８】
データ１８２２は、コンピュータ・システム１８００内の任意のプログラムへの入力として、あるいはそれからの出力として機能する任意のデータを表わしている。オペレーティング・システム１８２３は、たとえば当業界でＯＳ／４００として公知のマルチタスク・オペレーティング・システムである。しかし、当業者が認識しうるように、本発明の本旨と範囲は、特定のオペレーティング・システムの使用に限定されない。コンパイル単位１８２４は、ひと塊のクラスであり、オブジェクト指向すなわちオブジェクト・ベースのコンピュータ・プログラムの一部を成すものである。そして、オブジェクトをインスタンス化（生成）する少なくとも１つの文を含んでいる。好適な実施形態の場合、次のように仮定している。
（１）複数のコンパイル単位で１つのオブジェクト指向プログラムを構成している。
（２）コンパイル単位１８２４は、複数のコンパイル単位のうちの１つである。（３）コンパイラ／オプティマイザ１８２５は、同時にただ１つのコンパイル単位しか処理しない。
クラスパス１８２５は、ユーザが指定したパス（経路）であり、実行時に存在することが見込まれる外部クラスを探索すベき場所をコンパイラ／オプティマイザ１８２５に教えるものである。クラスパスは、ディレクトリの順序づけられたリスト、および／または、上記外部クラスを含むＪＡＲ（Java(R) archive）ファイルである。（「Ａおよび／またはＢ」は「ＡおよびＢ、Ａ、またはＢ」を表わす）。
【００５９】
プロセッサ１８１０は、たとえば少なくとも１つのマイクロプロセッサおよび／または集積回路群から構築されている。プロセッサ１８１０は、メインメモリ１８２０に格納されているプログラムの命令を実行する。メインメモリ１８２０は、プロセッサ１８１０がアクセスするプログラムとデータを格納している。コンピュータ・システム１８００の動作開始時に、プロセッサ１８１０は、最初に、オペレーティング・システム１８２３を構築するプログラムの命令を実行する。オペレーティング・システム１８２３は、精巧なプログラムであり、コンピュータ・システム１８００の資源を管理している。これらの資源には、たとえば、プロセッサ１８１０、メインメモリ１８２０、大容量記憶装置インタフェース１８３０、端末インタフェース１８４０、ネットワーク・インタフェース１８５０、システム・バス１８６０などがある。
【００６０】
図１８ではコンピュータ・システム１８００を、単一のプロセッサと単一のシステム・バスだけを備えているように示してあるけれども、当業者が認識しうるように、本発明は、複数のプロセッサおよび／または複数のバスを備えたコンピュータ・システムを使って実施することもできる。さらに、好適な実施形態で使用するインタフェースは、各々、個別に完全にプログラムされたマイクロプロセッサを備えて、プロセッサ１８１０をコンピュータ集約的な処理から解放している。しかし、当業者が認識しうるように、本発明は、同様の機能を実行するのにＩ／Ｏアダプタを使うだけのコンピュータ・システムにも等しく適用することができる。
【００６１】
端末インタフェース１８４０は、少なくとも１つの端末１８６５をコンピュータ・システム１８００に直接に接続するのに使用する。これらの端末１８６５は、非インテリジェントな（すなわちダムな〔愚かな〕）端末、あるいは、完全にプログラム可能なワークステーションであるが、システム管理者とユーザがコンピュータ・システム１８００と交信できるようにするために使用する。しかしながら、留意点を挙げると、端末インタフェース１８４０は少なくとも１つの端末１８６５との交信をサポートするために備えられているものであるけれども、コンピュータ・システム１８００は、必ずしも端末１８６５を必要としない。なぜなら、ユーザおよび他のプロセスとの必要な対話は、すべて、ネットワーク・インタフェース１８５０を介して行なうことができるからである。
【００６２】
ネットワーク・インタフェース１８５０は、別のコンピュータ・システムおよび／またはワークステーション（たとえば図１８中の符号１８７５）をコンピュータ・システム１８００にネットワーク１８７０を介して接続するのに使用する。本発明は、コンピュータ・システム１８００と別のコンピュータ・システムおよび／またはワークステーションとの間の接続形態に関係なく、等しく適用することができる。すなわち、ネットワーク接続１８７０が、今日のアナログおよび／またはディジタル技術を使ったものであるか、あるいは、未来のネットワーキング機構を介したものであるか、とは無関係である。さらに、ネットワークを実装するのに、多種多様なネットワーク・プロトコルを使用することができる。これらのプロトコルは、専門化したコンピュータ・プログラムであり、コンピュータがネットワーク１８７０を介して通信するのを可能にしている。ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol)が好適なネットワーク・プロトコルの一例である。
【００６３】
現時点において、次の点に留意するのが重要である。すなわち、完全に機能するコンピュータ・システムの文脈で本発明を説明した、そして、今後も説明を続けるけれども、当業者が認識しうるように、本発明は、様々な形態のプログラム製品として頒布することができる。そして、本発明は、この頒布を実際に行なうのに使う信号搬送媒体の特定の型とは無関係に、等しく適用することができる。好適な信号搬送媒体の例として、記録可能型媒体（たとえばフレキシブル・ディスク〔たとえば図１８の符号１８９５〕やＣＤ−ＲＯＭ）、および、伝送型媒体（たとえばディジタル通信リンクやアナログ通信リンク）を挙げることができる。
【００６４】
次に、一例を示して、好適な実施形態の装置と方法の機能を説明する。図１９と図２０は、第１のコンパイル単位中に存在するものと仮定する９つのサンプル・クラスのＣ＋＋疑似コードを示す図である。これらのクラスは、Instrument、Intensity 、WindInstrument、Valve 、BrassInstrument 、WoodwindInstrument、Drumstick 、Mallet、および、Playerである。図２１は、第２のコンパイル単位中に存在するものと仮定する３つのサンプル・クラスのＣ＋＋疑似コードを示す図である。第１のコンパイル単位と第２のコンパイル単位とは、別々にコンパイルする。図１９〜図２１には、クラスおよびメソッドのうち、好適な実施形態を説明するのに適した部分だけが示してある。図１９〜図２１では、時々、省略符号「....」を用いて、好適な実施形態の概念を説明する目的にとって重要でないコードに代えてある。この実例では、隠れたコンストラクタ連鎖を無視している。したがって、ＸがＹを継承する場合、Ｘ.<init> がＹ.<init> を呼び出す、という事実は、ここに示す実例を簡単化するために無視している。
【００６５】
図２２は、図１１のステップ１１２０で第１のコンパイル単位用に作成される可視クラス階層図である。可視クラス階層図においては、あるコンパイル単位中のクラスＸが当該コンパイル単位中にないクラスＹを継承している場合、Ｙを破線の楕（だ）円で表わすとともに、ＸからＹに至る継承弧も破線で表わす。コンパイラは、クラスＹの継承元は知らない。図１１のステップ１１２０では、第２のコンパイル単位用に、図２３に示す可視クラス階層図も作成される。
【００６６】
図１１のステップ１１３０では、第１のコンパイル単位につき図２４に示す可視ライブ呼び出し図２３００を作成し、第２のコンパイル単位につき図２５に示す可視ライブ呼び出し図２４００を作成する。図２４と図２５において、「Ｘ．Ｙ」と記載された楕円は、クラスＸ中のメソッドＹを示している。メソッドが呼び出しサイトを備えている場合、呼び出しサイトごとに、対応する楕円から１つの小さな矩（く）形に伸びる弧が存在する。そして、呼び出しサイト矩形から、コンパイル単位中の、当該呼び出しサイトで呼び出される可能性のあるメソッドの各々に伸びる弧が存在する。留意点を挙げると、大多数の呼び出しサイトは外に向かう弧を１つしか持たないけれども、呼び出しサイトの中には、外に向かう弧を持たないものや２つ持つものもある（ただし、外に向かう弧の数は任意の数が可能である）。外に向かう弧を持たない呼び出しサイト（たとえば図２５のDrum.strikeWith ）は、おそらく現在のコンパイル単位の外部にある少なくとも１つのメソッドを呼び出している。一般に、すべての呼び出しサイトは、現在のコンパイル単位の外部にあるメソッドを呼び出しうる。ただし、そうでないことが判明している場合は、この限りではない。真の仮想メソッド呼び出しの一例として、図２４の可視ライブ呼び出し図に示すように、Player.messAroundWith に付随する呼び出しサイト１３が挙げられる。Player.messAroundWith は、呼び出しサイト１３でBrassInstrument.loudHighNoteまたはWoodwindInstrument.loudHighNote を呼び出すことができるとともに、コンパイル単位の外部にあるメソッドを呼び出すこともできる。
【００６７】
図１１のステップ１１４０は、図１２に詳細に示してある。そこでの第１ステップは、可視ライブ呼び出し図中のメソッド群をリーフからルートの順にソートすることである。図２４と図２５の可視ライブ呼び出し図中の各メソッドは、それに付随し円で囲まれた順序数を有する。この順序数は、ソート順における位置を表わしている。次いで、現在のコンパイル単位中のメソッドごとに、図１２のステップ１２２０、１２３０、および１２４０を処理する。
【００６８】
図２４と図２５で定義した２１個のメソッドの各々のステップ群を長々と説明する代わりに、ここで説明する好適な実施形態で開示するように、本発明と関係があるメソッドとステップに注目することにする。従来技術と好適な実施形態との間の相違点は、呼び出しサイトとオブジェクト割り当てサイトとでメソッドの接続図の作成方法をどのように変えるか、という点にある。したがって、そのようなサイトを含むメソッドに注目するだけでよい。呼び出しサイトの処理は、図１３と図１４に示してある。一方、オブジェクト割り当てサイトの処理は、図１５に示してある。図２６（ａ）は、図２４の１８個のメソッドのうち、呼び出しサイトとオブジェクト割り当てサイトの双方を持たない１１個のメソッドの接続図を示している。接続図において、箱は参照ノード（ポインタ）を表し、円はオブジェクト割り当てノードを表わしている。破線の円は、現在のメソッドの外部に割り当てられるオブジェクトを表わしている。参照ノードは、参照変数の名前を含むとともに、「Ｐｉ」を前置して、その参照変数が現在のメソッドに渡されるｉ番目の公式パラメータであることを示している。参照ノードからオブジェクト割り当てノードに至る弧には「Ｐ」なるマークを付けて、当該参照ノードが当該オブジェクト割り当てノードを「指し示している（point to）」ことを示している。以上の点から、図２７（ｃ）に示すBrassInstrument.getValveの接続図において、隠れ「this」ポインタが第１のパラメータであり、BrassInstrument 型のオブジェクトを指し示しているものと仮定してある。このようなオブジェクトは、Valve ［］型のオブジェクトを指し示す「Valves」フィールドを備えている（Valve ［］はValve オブジェクトの配列である）。ここでは、この実例の目的に鑑み、配列オブジェクトと配列に含まれるオブジェクトとを区別しない。
【００６９】
図２６（ａ）に示す、リストアップした１１個のメソッドの接続図は、「this」ポインタが不明オブジェクトを指し示していることを示すだけである。この不明オブジェクトは、これ以外の方法では、メソッド内で参照されない。
【００７０】
図２６（ｂ）を参照する。BrassInstrument.<init>（BrassInstrument コンストラクタ・メソッドに対応する、コンパイラ内部の名前）は、「this」ポインタが指し示しているオブジェクトが、第２のパラメータ（「v 」）を指し示すように変更された「Valves」フィールドを持つようになることを表わしている。
【００７１】
図２７（ｃ）を参照する。BrassInstrument.getValveの接続図は、「this.valves 」が指し示すオブジェクトに対する参照が戻される、ということを示している。「Ｒ：」とラベル付けされた参照ノードは、この一時戻り値を表わすのに使用する。背景として図２６（ａ）〜図２７（ｃ）の接続図を作成したので、残りのメソッドのいくつかを注意深く考察することにする。図２８（ａ）と図２８（ｂ）は、 BrassInstrument.depressValve のために行なう処理を示している。 BrassInstrument.depressValve は、Valve.depress に対する呼び出しを含んでいる。チョイらの論文に述べられているように、接続図を作成するには、文を順番に処理する。Valve.depress を呼び出す前、接続図は、図２８（ａ）に示すように見える。そこでは、２つのパラメータは、オブジェクトを指し示しているものと仮定してある。留意点を挙げると、「which 」パラメータは「Ａ1 」と注釈されているが、これは、「which 」パラメータがValve.depress に渡される第１の引数であることを表わしている。
【００７２】
呼び出しサイト（すなわち図２４の呼び出しサイト１）を処理しようとしているのであるから、図１３の方法１２３０Ａを使う。ステップ１３１０（図１４で拡張されている）では、この呼び出しサイトが予測可能であるか否か判断する。図１４の方法１３１０を参照すると、ステップ１４１０で、targetCount を初期化して「０」にする。図２４のライブ呼び出し図を参照すると、この呼び出しサイト１には１つの潜在ターゲット・メソッドがあることが分かるので、ステップ１４２０＝ＹＥＳである。次いで、ステップ１４３０で、Ｍi にValve.depress を代入する。次いで、ステップ１４４０でtargetCount をインクリメントすると、targetCount ＝１になる。図１９を参照すると、Valve.depress は、静的でなく、<init>でなく、private でなく、final でもないことが分かる。しかし、Valve.depress は最終クラスValve の一員であるから、ステップ１４５０＝ＹＥＳである。ソース・コードの呼び出しはValve 型のオブジェクトの代わりであるから、ステップ１４６０＝ＹＥＳである。次いで、ステップ１４２０にループバックする。この呼び出しサイト１には他に潜在ターゲット・メソッドが存在しないから、ステップ１４２０＝ＮＯである。targetCount ＝１であるから、ステップ１４２２＝ＮＯである。そして、呼び出しサイト１は予測可能である、と判断される（ステップ１４２４）。この結果、この呼び出しサイト１について、図１３のステップ１３１０＝ＹＥＳである。
【００７３】
図１３を参照すると、ステップ１３３０で再度、Ｍi にValve.depress を代入する。ステップ１３３０で、Valve.depress の接続図をBrassInstrument.depressValveの接続図中にマージする。Valve クラスは、現在のコンパイル単位に存在するから、実行時に存在するのは確実である。したがって、ステップ１３４０では、メソッド依存関係を記録する必要がない。実際の引数Ａ1 ＝「which 」は、Valve.depress の接続図の公式パラメータＰ1 と等価である（ステップ１３５０）。Valve.depress には戻り参照ノードが存在しないから、ステップ１３６０には結果がない。ステップ１３５０を実行しても、呼び出し側の図はまったく変化しない。そして、BrassInstrument.depressValveには他に文が存在しないから、図１２のステップ１２３０は完了する。最終接続図を図２８（ｂ）に示す。次いで、図１２のステップ１２４０で、BrassInstrument.depressValveには他にオブジェクト割り当てサイトが存在しないことを確認する。処理すべきメソッドが他にも存在するから（ステップ１２５０）、ステップ１２２０にループバックして、格納済みリストから次のメソッドを選択する。図２４を参照すると、格納済みリストの次のメソッドは、BrassInstrument.setEmbouchure メソッドである。
【００７４】
図２９（ａ）〜図３０（ｃ）は、６つのメソッド呼び出しを含むBrassInstrument.loudHighNoteの処理をいくつか実行している間の接続図を示している。これらのうちで第１のものは、BrassInstrument.getValve対する呼び出しサイト４である。図２９（ａ）は、これを呼び出す前の接続図を示している。上述したのと同様に、これは、不明オブジェクトを指し示すパラメータを示している。さらに、BrassInstrument.getValveからの戻り値である機能結果（ＦＲ1 ）に対する匿名参照がある。図１３のステップ１３１０では、図１４のステップ群を実行して、この呼び出しサイト４が予測可能であるか否か判断する必要がある。まず、targetCount 変数を初期化して「０」にする（ステップ１４１０）。図２４のライブ呼び出し図を見ると、この呼び出しサイト４はコンパイル単位中に既知のターゲット・メソッドを１つ持っているのが分かるから、ステップ１４２０＝ＹＥＳである。次いで、ステップ１４３０で、Ｍi にこのターゲット・メソッドすなわちBrassInstrument.getValveを代入する。次いで、ステップ１４４０で、targetCount をインクリメントして「１」にする。BrassInstrument.getValveはprivate メソッドであるから（図１９参照）、ステップ１４５０＝ＹＥＳである。getValveに対する呼び出しは、BrassInstrument オブジェクトの代わりに（すなわち、BrassInstrument.loudHighNoteの「this」が）行なうから、ステップ１４６０＝ＹＥＳである。この呼び出しサイト４には未処理の潜在ターゲット・メソッドが他に存在せず（ステップ１４２０＝ＮＯ）、targetCount ≠０（ステップ１４２２＝ＮＯ）であるから、呼び出しサイト４は予測可能である（ステップ１４２４）。次いで、ステップ１３２０で、Ｍi にBrassInstrument.getValveを代入する。図２７（ｃ）を参照すると、BrassInstrument.getValveの「this」パラメータは図２９（ａ）のBrassInstrument.loudHighNoteの「this」パラメータと等価であり（ステップ１３５０）、BrassInstrument.getValveの公式戻り値はBrassInstrument.loudHighNoteの匿名「ＦＲ1 」参照ノードと等価である（ステップ１３６０）。結果として得られる接続図を、図２９（ｂ）に示す。
【００７５】
次の呼び出しサイトは、BrassInstrument.depressValveに対する呼び出しサイト２であり、「this」と「ＦＲ1 」を引数として渡す。ステップ１３１０で、呼び出しサイト２が予測可能であるか否かを調べる必要がある。図１４を参照すると、ステップ１４１０で、targetCount を初期化して「０」にする。図２４のライブ呼び出し図を見ると、呼び出しサイト２はコンパイル単位中に１つの既知のターゲット・メソッドを持っているのが分かるから、ステップ１４２０＝ＹＥＳである。次いで、ステップ１４３０で、Ｍi にこのターゲット・メソッドすなわちBrassInstrument.depressValveを代入する。次いで、ステップ１４４０で、targetCount をインクリメントして「１」にする。BrassInstrument.depressValveは、静的でなく、<init>でなく、private でなく、final でなく、最終クラス中にあるわけでもないから、ステップ１４５０＝ＮＯである。したがって、呼び出しサイト２は予測不能である（ステップ１４７０）。呼び出しサイト２が予測不能であるから（ステップ１３１０＝ＮＯ）、BrassInstrument.loudHighNote用にグローバル「ボトム」ノードを生成して、実際の引数ノード「this」と「ＦＲ1 」が指し示しているオブジェクトに接続させる。この様子を、図３０（ｃ）に示す。直観による結果を挙げると、任意の呼び出し側がLoudHighNoteに渡す第１の引数は、その「valves」サブオブジェクトとともに、エスケープしているようである。なぜなら、BrassInstrument.depressValveは、実行時に、それらのオブジェクトをグローバル変数に格納しているメソッドがオーバーライドする可能性があるからである。これは「void」を戻すメソッドであるから、戻り参照ノードはない。したがって、ステップ１３８０には結果がない。
【００７６】
BrassInstrument.loudHighNoteにおける残りの呼び出しは、すべて予測可能であり、図２６（ａ）の単純な接続図を有するターゲット・メソッドである。この結果、BrassInstrument.loudHighNoteの最終接続図は、図３０（ｃ）に示すとおりである。ステップ１２４０で処理すべきオブジェクト割り当ては他に存在しないから、次のメソッドに進む。
【００７７】
メソッドPlayer.messAroundWith を処理して得られる接続図を、図３１（ａ）〜図３２（ｄ）に示す。まず、呼び出しサイト１４を選択して処理する。Instrument.identify を呼び出す前、接続図は、図３１（ａ）に示すようになっている。次いで、ステップ１４１０で、targetCount を初期化して「０」にする。図２４を参照すると、この呼び出しサイト１４は現在のコンパイル単位中に１つの既知のターゲット・メソッドを有するから、ステップ１４２０＝ＹＥＳである。次いで、ステップ１４３０で、Ｍi にWindInstrument.idetifyを代入する。次いで、targetCount をインクリメントして「１」にする。図１９を参照すると、WindInstrument.idetifyはfinal メソッドである（ステップ１４５０＝ＹＥＳ）。しかし、この呼び出しはInstrumentオブジェクトの代わりに実行しており、WindInstrumentオブジェクトである必要はないから、ステップ１４６０＝ＮＯである。したがって、この呼び出しサイト１４は予測不能である（ステップ１４７０）。この呼び出しサイト１４は予測不能であるから（ステップ１３１０＝ＮＯ）、グローバル「ボトム」ノードを生成して、実際の引数（「ax」）が指し示しているオブジェクトに接続する。
【００７８】
Player.messAroundWith 中の次の文Ｓ1 はオブジェクト割り当て文を含んでいるから、図１５のステップ群を実行する。インスタンス化すべきクラスはIntensity である。Intensity は現在のコンパイル単位中に存在するから、ステップ１５１０＝ＹＥＳである。次いで、ステップ１５２０で、接続図中に、Intensity オブジェクト用にオブジェクト割り当てノードを生成する（図３１（ｂ）にＳ1 として示す）。次いで、ステップ１５５０で、このIntensity オブジェクトに対する参照を値スタックにプッシュする。次に処理すべきバイトコードは、参照変数「inten 」に対する参照を値スタックの表面に格納するものである。この結果、「inten 」から「Ｓ1 」に向かう有向弧を付加する。現時点までの結果を、図３１（ｂ）に示す。
【００７９】
次に、Intensity.<init>に対する呼び出しを処理して、新たに生成されたオブジェクト（すなわち呼び出しサイト１５と表記されたオブジェクト）を初期化する。実際には、この呼び出しは、「inten 」の格納に先行する。しかし、図を簡単にするために、「inten 」を格納した後に、Intensity.<init>を呼び出すものと仮定している。次に、図１４を参照すると、ステップ１４１０で、targetCount を初期化して「０」にする。図２４のライブ呼び出し図を見ると、呼び出しサイト１５には１つのターゲット・メソッドがあるのか分かるから、ステップ１４２０＝ＹＥＳである。次いで、ステップ１４３０で、Ｍi にIntensity.<init>を代入する。次いで、ステップ１４４０で、targetCount をインクリメントして「１」にする。Intensity.<init>は<init>メソッドであるから、ステップ１４５０＝ＹＥＳである。この呼び出しはIntensity オブジェクトの代わりに行なうから、ステップ１４６０＝ＹＥＳである。以上の点から、ステップ１４２０＝ＮＯであり、ステップ１４２２＝ＮＯであるから、この呼び出しサイト１５は予測可能である（ステップ１４２４）。したがって、図１３のステップ１３１０＝ＹＥＳである。次いで、Ｍi にIntensity.<init>を代入する。しかし、ステップ１３３０とステップ１３５０を実行しても、接続図は変化しない。これを、図３１（ｃ）に示す。図３１（ｃ）は、「ax」と「inten 」が、図２４の呼び出しサイト１３における次の文中のInstrument.loudHighNote に渡すべき引数であることも示している。
【００８０】
次に、図１３と図１４のステップ群を用いて、呼び出しサイト１３を処理する。まず、targetCount を初期化して「０」にする（ステップ１４１０）。ライブ呼び出し図を見ると、呼び出しサイト１３には２つの既知のターゲット・メソッドがあるから、ステップ１４２０＝ＹＥＳである。したがって、ステップ１４３０で、Ｍi に、これら２つの既知のターゲット・メソッドのうちの第１のもの、すなわちBrassInstrument.loudHighNoteを代入する。次いで、ステップ１４４０で、targetCount をインクリメントして「１」にする。BrassInstrument.loudHighNoteは静的でなく、<init>でなく、private でなく、final でなく、最終クラス中にあるわけでもないから、ステップ１４５０＝ＮＯである。したがって、呼び出しサイト１３は予測不能である（ステップ１４７０）。この結果、ステップ１３１０＝ＮＯであるから、ステップ１３７０で、グローバル「ボトム」ノードを、実際の引数「ax」と「inten 」が指し示しているオブジェクトに接続する。この呼び出しはvoidをを戻すから、ステップ１３８０には結果がない。Player.messAroundWith の最終接続図を、図３２（ｄ）に示す。図１２に戻って、ステップ１２４０で、（チョイらのものと同様の）エスケープ分析を行なって、オブジェクト割り当てノードＳ1 がエスケープしているか否か判断する。Ｓ1 はグローバル・ボトム・ノードから有向経路を辿（たど）って到達可能であるから、ステップ１２４０では、Ｓ1 をグローバル・エスケープに分類する。
【００８１】
図３３（ａ）〜図３４（ｄ）は、Player.beatDrum の呼び出しサイト１６を同じように処理する状態を示す図である。文Ｓ2 と文Ｓ3 を処理すると、図３３（ａ）〜図３３（ｃ）に示す各段階が得られる。割り当てたオブジェクトは両方とも現在のコンパイル単位中のクラスを継承したものであるから（ステップ１５２０＝ＹＥＳ）、ステップ１５２０で、接続図中にオブジェクト割り当てノードを生成する。次いで、ステップ１５５０で、この新たなオブジェクト割り当てノードを値スタックにプッシュする。次に、図２４の呼び出しサイト１８として示すDrum.strikeWith を処理する。接続図は、最初、図３３（ｃ）のように見える。まず、ステップ１４１０で、targetCount を初期化して「０」にする。図２４のライブ呼び出し図を見ると、この呼び出しサイト１８用の既知のターゲット・メソッドは現在のコンパイル単位中に存在しないから、ステップ１４２０＝ＮＯであり、ステップ１４２２＝ＹＥＳである。したがって、この呼び出しサイト１８は予測不能である（ステップ１４７０）。この結果、ステップ１３１０＝ＮＯであるから、グローバル「ボトム」ノードを生成して、実際の引数「drum」と「m 」が指し示しているオブジェクトに接続する。その結果を、図３４（ｄ）に示す。図１２に戻ると、ステップ１２４０で、オブジェクト割り当てノードＳ2 とＳ3 を処理する必要がある。Ｓ3 は、ここでもグローバル「ボトム」ノードから到達可能であるから、グローバル・エスケープに分類される。Ｓ2 は、グローバル「ボトム」ノードから到達可能でないばかりか、すべての公式パラメータから到達可能でないから、エスケープなしに分類される。したがって、Ｓ2 は、スタック割り当てしても差し支えない。このことは、Ｓ2 が予測不能な別のメソッドを呼び出していても成り立つ。なぜなら、スタック割り当て可能なオブジェクトに対する参照は、予測不能なメソッドに渡されることがないからである。このことは、好適な実施形態で説明した、本発明の有用性を示すものである。
【００８２】
次に、第２のコンパイル単位に目を向けて、図３５（ａ）〜図３５（ｃ）に示すように、Percussionist.acquireEquipmentを処理する。第１の文は、Drumオブジェクト用のオブジェクト割り当てを含んでいる。図１５において、ステップ１５１０＝ＹＥＳである。なぜなら、Drumクラスは同じコンパイル単位中で定義されているからである。したがって、ステップ１５２０とステップ１５５０の処理は、上述した場合と同じである。結果を、図３５（ａ）に示す。空でデフォルトのコンストラクタDrum.<init> に対する呼び出しは、予測可能であるので、接続図に影響しない。次に、Malletオブジェクトを、文Ｓ5 に割り当てる。図１５において、ステップ１５１０＝ＮＯである。なぜなら、Malletクラスは現在のコンパイル単位の外部で定義されているからである。したがって、ステップ１５３０で、「Java(R)/lang/Object」（図３５（ｂ）では「Object」と略記）とマーク付けしたオブジェクト割り当てノードを生成する。次いで、ステップ１５４０で、グローバル「ボトム」ノードを生成して、この新たなノードに接続する。次いで、ステップ１５５０で、この新たなノードを値スタックにプッシュする。この結果、あとでノード「m 」をこの新たなノード「Ｓ5 」に接続することができる。Mallet.<init> を呼び出す前の結果を、図３５（ｂ）に示す。
【００８３】
次に、図２５に示すMallet.<init> に対する呼び出しサイト３を処理する。ここでも図１４を参照して、ステップ１４１０で、targetCount を初期化して「０」にする。この呼び出しサイト３には既知のターゲット・メソッドが存在しないから、ステップ１４２０＝ＮＯであり、ステップ１４２２＝ＹＥＳである。したがって、この呼び出しサイト３は予測不能である（ステップ１４７０）。この結果、ステップ１３１０＝ＮＯであるから、ステップ１３７０で、グローバル「ボトム」ノードを、「m 」が指し示しているものに接続する。ステップ１３７０は、この場合、接続図に影響しない。最終接続図を、図３５（ｃ）に示す。図１２に戻り、ステップ１２４０で、Ｓ4 とＳ5 を処理する必要がある。Ｓ5 はグローバル・エスケープである。なぜなら、Ｓ5 はグローバル「ボトム」ノードから到達可能だからである。Ｓ4 はエスケープなしである。したがって、Ｓ4 は、スタックに割り当てることができる。ここでも、このことは、Percussionist.acquireEquipmentが不明のメソッドを呼び出している、という事実にかかわらずに成り立つ。
【００８４】
上述した例では、単一のコンパイル単位を最適化しただけなので、外部のクラスを分析することによる恩恵を受けることができなかった。次に示す例は、本発明のこの側面がもたらす有用性を示している。この場合、図２１の第２のコンパイル単位を再度コンパイルすることになる。しかし、今回は、ユーザが定義するクラスパスが、図１９と図２０に示す第１のコンパイル単位中のクラスを含む単一のＪＡＲファイルから成る。
【００８５】
ここでも図１１を参照すると、ステップ１１１０で、第１のコンパイル単位を含むクラスパスを取得する。次いで、ステップ１１２０で、図３６の可視クラス階層図を作成する。留意点を挙げると、図３６には、図２１で定義されたクラスだけでなく、それらのクラスから直接にあるいは間接的に参照されるクラスも含まれている。次いで、ステップ１１３０で、図３７の可視ライブ呼び出し図を作成する。この図３７は図２５の可視ライブ呼び出し図ときわめてよく似ているけれども、例外が１つある。その例外とは、Percussionist.acquireEquipmentの呼び出しサイト３が、今回は、可視のターゲット・メソッドすなわちMallet.<init> を有する点である。
【００８６】
今回は、図１２に示す方法１１４０によって、控え目なエスケープ分析を行なう。まず、図３７のメソッド群のソート済みの処理順序を取得する（ステップ１２１０）。次いで、ステップ１２２０で、これらのメソッドを１回に１つずつ処理する。Drum.strikeWinとDrum.<init> の処理は、上述した例と同様に、正確に進める。ループの次の繰り返しで、ＭにMallet.<init> を代入する（ステップ１２２０）。次いで、図２６（ａ）に示すように、Mallet.<init> の接続図を作成する（ステップ１２３０）。Mallet.<init> はオブジェクト割り当てを含んでいないから、ステップ１２４０には結果がない。他にも処理すべきメソッドが存在するから（ステップ１２５０＝ＹＥＳ）、ＭにPercussionist.acquireEquipmentを代入する（ステップ１２２０）。次いで、このメソッドの命令を処理して、次に示すように、Ｍの接続図を作成する。
【００８７】
図３８（ａ）（上述の例の図３５（ａ）と同一）は、Drum.<init> を呼び出す前のPercussionist.acquireEquipmentの接続図を示している。空でデフォルトのコンストラクタDrum.<init> の呼び出しは、予測可能であるとともに、接続図に影響しない。次いで、Malletオブジェクトを文Ｓ5 に割り当てる。上述の例とは異なり、Malletは現在のクラスパス中のコンパイル単位中で可視であるから、ステップ１５１０＝ＹＥＳである。次いで、Ｓ5 用にオブジェクト割り当てノードを生成して、「Mallet」なるラベルを付ける（ステップ１５２０）。次いで、この新たなノードを値スタックにプッシュする（ステップ１５５０）。この結果、後刻、ノード「m 」を新たなノードＳ5 に接続することができるようになる。Mallet.<init> を呼び出す前の結果を、図３８（ｂ）に示す。
【００８８】
次に、図３７に示すMallet.<init> の呼び出しサイト３を処理する。今回も、図１４を参照する。まず、ステップ１４１０で、targetCount を初期化して「０」にする。今回は、既知のターゲット・メソッドがあるから（ステップ１４２０＝ＹＥＳ）、Ｍi にMallet.<init> を代入する（ステップ１３４０）。次いで、targetCount をインクリメントして「１」にする。このMallet.<init> は<init>メソッドであり（ステップ１４５０＝ＹＥＳ）、初期化するオブジェクトがMalletであり（ステップ１４６０＝ＹＥＳ）、他にターゲット・メソッドが存在せず（ステップ１４２０＝ＮＯ）、そして、targetCount ≠０であるから（ステップ１４２２＝ＮＯ）、この呼び出しサイト３は予測可能である（ステップ１４２４）。したがって、ステップ１３１０＝ＹＥＳである。それゆえ、Mallet.<init> の小さな接続図を、Percussionist.acquireEquipmentの接続図中にマージする（ステップ１３３０）。次いで、ステップ１３４０で、Malletクラスのタイムスタンプとチェックサムを、Percussionist.acquireEquipmentのメソッド依存関係リストに記録する。ステップ１３５０とステップ１３６０におけるノードの等価化は、最終接続図に影響しない。最終接続図を、図３８（ｃ）に示す。
【００８９】
図１２に戻ると、ステップ１２４０で、Percussionist.acquireEquipmentのどのオブジェクト割り当てを、グローバル・エスケープ、引数エスケープ、あるいは、エスケープなしに分類すべきであるかを判断する。詳細は図１６に示してある。割り当てＳ4 と割り当てＳ5 は、両方とも、エスケープしていなとともに、コンパイル時に決めることのできるサイズを有することが分かるから、ステップ１６４０で、このメソッド用に２つの版のコードを生成することに決める。次いで、ステップ１６５０で、DrumオブジェクトとMalletオブジェクトの見込みサイズを、Percussionist.acquireEquipmentのサイズ依存関係リストに記録する。これにより、このコンパイル単位のコンパイル時処理が終了する。
【００９０】
実行時には、図１７の方法１７００を用いて、２つの版のコードを有するようなメソッドに対して、どちらの版のコードを使うべきかを判断する。まず、ステップ１７１０で、Percussionist クラスをJava(R)仮想マシン（ＪＶＭ）にロードする。処理すべきメソッドが残っているから（ステップ１７２０）、ＭにacquireEquipmentを代入する（ステップ１７３０）。ＭはMalletについてメソッド依存関係を有し、MalletとDrumについてサイズ依存関係を有するから、ステップ１７４０＝ＹＥＳである。次いで、ステップ１７５０で、ＤにMalletクラスを代入する。このとき、Malletクラスがロード済みでない場合には、ステップ１７６０でロードする。次いで、Malletクラスのタイムスタンプおよびチェックサムと、メソッド依存関係テーブルに記録してあるデータとを比較する（ステップ１７７０）。この実例の目的のために、これらは一致する（すなわちMalletクラスはコンパイル時以降変化していない）ものと仮定する。ロード済みのクラス用のMalletオブジェクトのサイズも、記録済みのサイズと比較し、一致するのを確認する。考慮すべき別の依存関係が存在するから（ステップ１７４０＝ＹＥＳ）、ＤにDrumクラスを代入する。ここでも、Drumクラスがロード済みでない場合には、ステップ１７６０でロードする。ロード済みのクラス用のDrumオブジェクトのサイズと、記録済みのサイズとを比較し、一致するのを確認する。考慮すべきクラスが他に存在せず（ステップ１７４０＝ＮＯ）、依存関係はすべて満たされたから、サイトＳ4 とサイトＳ5 用に、acquireEquipment用のコード・ポインタをスタック割り当てを使っている版に設定する（ステップ１７８０）。留意点を挙げると、ステップ１７７０で調べた依存関係のうちどちらか一方でも満たされなかった場合には、サイトＳ4 とサイトＳ5 用に、上記コード・ポインタはヒープ割り当てを使っている版に設定することになる。Percussionist クラスには他にメソッドが存在しないから（ステップ１７２０＝ＮＯ）、実行時処理は完了する。
【００９１】
ここに開示した好適な実施形態が従来技術に比べて顕著に進歩しているのは、コンパイル単位中の一部の変数を呼び出し側メソッドの呼び出しスタックに割り当てるのを可能にしているからである。これが可能になるのは、一部の条件が満たされている場合であり、コンパイル単位中ですべてのクラスが可視である必要はない。割り当ての判断は、コンパイル単位中で可視であるとともに、ユーザ指定のすべてのクラスパス中で可視であるクラスに基づいて行なう。このように、複数のコンパイル単位に分離しているオブジェクト指向のプログラムは、メソッドの呼び出しスタックにオブジェクトを割り当てる最適化に起因するパフォーマンスの向上から恩恵を受けることができる。
【００９２】
上述した実施形態と実例を提示した目的は、本発明とその実際上の応用を最良の形で説明すること、および、それにより、当業者が本発明を作りかつ使用するのを可能にすることである。しかしながら、当業者が認識しうるように、上述した説明と実例は、説明と例示のみを目的として提示した。上述した説明は、開示したもので尽きている、あるいは、本発明を開示したものに限定する、ということを意図していない。特許請求の範囲の本旨と範囲のうちで、上述した教示に鑑み、多くの変更と変形が可能である。たとえば、Java(R)オブジェクトの割り当てに対する実際上の応用を有するものとして、好適な実施形態を説明したけれども、好適な実施形態は、特定のオブジェクト指向言語に限定されるものではない。
【００９３】
まとめとして以下の事項を開示する。
（１）少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに接続されたメモリと、
オブジェクト指向プログラムの一部を成す複数のオブジェクト指向クラスを備えた、前記メモリに常駐する第１のコンパイル単位であって、前記オブジェクト指向プログラムが前記第１のコンパイル単位と少なくとも１つの別のコンパイル単位との組み合わせによって定義されている、第１のコンパイル単位と、
前記メモリに常駐するとともに、前記少なくとも１つのプロセッサが実行するコンパイラであって、前記第１のコンパイル単位中の少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てる、前記第１のコンパイル単位中のメソッド用の呼び出しスタック・フレームに割り当てるコンパイラとを備えた
システム。
（２）前記コンパイラが、
前記第１のコンパイル単位中の、新たなオブジェクトを割り当てる各命令を、前記第１のコンパイル単位中で可視のクラスから得られる情報に基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するエスケープ分析機構と、
前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、当該少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるオブジェクト割り当て機構とを備えている、
上記（１）に記載のシステム。
（３）前記エスケープ分析機構が、新たなオブジェクトを割り当てる、前記第１のコンパイル単位中の各命令を、前記第１のコンパイル単位中で可視のクラスから得られる情報と、前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視であるクラスから得られる情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類する、
上記（２）に記載のシステム。
（４）前記コンパイラが、
選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使用する第１の版とオブジェクトのヒープ割り当てを使用る第２の版とから成る２つの版のコードを生成するコード生成器を備えている、
上記（１）に記載のシステム。
（５）少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに接続されたメモリと、
オブジェクト指向プログラムの一部を成す複数のオブジェクト指向クラスを備えた、前記メモリに常駐する第１のコンパイル単位であって、前記オブジェクト指向プログラムが前記第１のコンパイル単位と少なくとも１つの別のコンパイル単位との組み合わせによって定義されている、第１のコンパイル単位と、
前記メモリに常駐するとともに、前記少なくとも１つのプロセッサが実行するコンパイラと
を備え、
前記コンパイラが、
新たなオブジェクトを割り当てる、前記第１のコンパイル単位中の各命令を、前記第１のコンパイル単位中で可視のクラスから得られる情報と、特定のクラスパス中で可視の、前記第１のコンパイル単位の外部に存在するクラスから得られる情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するエスケープ分析機構と、
前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、当該少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるオブジェクト割り当て機構と、
選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使用する第１の版とオブジェクトのヒープ割り当てを使用する第２の版とから成る２つの版のコードを生成するコード生成器と、
実行時に見られるクラスが予期されるクラスと所定の限度内で一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択する実行時コード・セクタと
を備えた
システム。
（６）第１のコンパイル単位と少なくとも１つの別のコンパイル単位とを備えたオブジェクト指向プログラムにおいて、オブジェクトをメモリに割り当てる方法であって、
（Ａ）前記第１のコンパイル単位をコンパイルするステップと、
（Ｂ）前記第１のコンパイル単位のコンパイル中に、前記第１のコンパイル単位中の命令が生成した少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるステップと
を備えた
方法。
（７）前記ステップ（Ｂ）が、
新たなオブジェクトを割り当てる各命令を、前記第１のコンパイル単位中のクラスから得られる情報と、前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視であるクラスから得られる情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するステップと、
前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるステップと
を備えている、
上記（６）に記載の方法。
（８）前記ステップ（Ｂ）が、
選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使う第１の版とオブジェクトのヒープ割り当てを使う第２の版とから成る２つの版のコードを生成するステップと、
実行時に見られるクラスが予期されるクラスと所定の限度内で一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択するステップと
を備えた、
上記（６）に記載の方法。
（９）第１のコンパイル単位と少なくとも１つの別のコンパイル単位とを備えたオブジェクト指向コンピュータ・プログラムにおいて、前記第１のコンパイル単位中のオブジェクトをメモリに割り当てる方法であって、
新たなオブジェクトを割り当てる各命令を、前記第１のコンパイル単位中のクラスから得られる情報と、前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視であるクラスから得られる情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するステップと、
選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使う第１の版とオブジェクトのヒープ割り当てを使う第２の版とから成る２つの版のコードを生成するステップと、
実行時に見られるクラスが予期されるクラスと所定の限度内で一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つを選択するステップと
を備えた
方法。
（１０）オブジェクト指向プログラムの一部を成す複数のオブジェクト指向クラスを備えた第１のコンパイル単位をコンパイルするコンパイラであって、前記オブジェクト指向プログラムが前記第１のコンパイル単位と少なくとも１つの別のコンパイル単位との組み合わせによって定義されており、前記コンパイラが前記第１のコンパイル単位中の少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てる、前記第１のコンパイル単位中のメソッド用の呼び出しスタック・フレームに割り当てる、コンパイラと、
前記コンパイラを搬送する信号搬送媒体と
を備えた
プログラム製品。
（１１）前記信号搬送媒体が記録可能媒体から成る、
上記（１０）に記載のプログラム製品。
（１２）前記信号搬送媒体が伝送媒体から成る、
上記（１０）に記載のプログラム製品。
（１３）前記コンパイラが、
前記第１のコンパイル単位中の、新たなオブジェクトを割り当てる各命令を、前記第１のコンパイル単位中で可視のクラスから得られる情報に基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するエスケープ分析機構と、
前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、当該オブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるオブジェクト割り当て機構と
を備えている、
上記（１０）に記載のプログラム製品。
（１４）前記エスケープ分析機構が、新たなオブジェクトを割り当てる、前記第１のコンパイル単位中の各命令を、前記第１のコンパイル単位中で可視のクラスから得られる情報と、前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視のクラスから得られる情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類する、
上記（１３）に記載のプログラム製品。
（１５）前記コンパイラが、
選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使用する第１の版とオブジェクトのヒープ割り当てを使用する第２の版とから成る２つの版のコードを生成するコード・ジェネレータと、
実行時に見られるクラスが予期されるクラスと所定の限度内で一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択する実行時コード・セクタと
を備えている、
上記（１０）に記載のプログラム製品。
（１６）
（Ａ）オブジェクト指向プログラムの一部を成す複数のオブジェクト指向クラスを備えた第１のコンパイル単位をコンパイルするコンパイラであって、前記オブジェクト指向プログラムが前記第１のコンパイル単位と少なくとも１つの別のコンパイル単位との組み合わせによって定義されている、コンパイラと、
（Ｂ）前記コンパイラを搬送する信号搬送媒体と
を備えた
プログラム製品であって、
前記コンパイラが、
（Ａ１）新たなオブジェクトを割り当てる、前記第１のコンパイル単位中の各命令を、前記第１のコンパイル単位中で可視のクラスから得られる情報と、前記第１のコンパイル単位の外部に存在し特定のクラスパス中で可視のクラスから得られる情報とに基づいて、グローバル・エスケープ、エスケープなし、および、引数エスケープのうちの１つに分類するエスケープ分析機構と、
（Ａ２）前記エスケープ分析機構がエスケープなしに分類した命令が生成する少なくとも１つのオブジェクトを、前記少なくとも１つのオブジェクトを割り当てるメソッド用の呼び出しスタック・フレームに割り当てるオブジェクト割り当て機構と、
（Ａ３）選択したオブジェクト・メソッド用に、オブジェクトのスタック割り当てを使用する第１の版とオブジェクトのヒープ割り当てを使用する第２の版とから成る２つの版のコードを生成するコード・ジェネレータと、
（Ａ４）実行時に見られるクラスが予期されるクラスと所定の限度内で一致するか否かという判断に基づいて、実行時に実行すべき版を、前記第１の版および前記第２の版のうちから１つ選択する実行時コード・セクタと
を備えている
プログラム製品。
（１７）前記信号搬送媒体が記録可能媒体から成る、
上記（１６）に記載のプログラム製品。
（１８）前記信号搬送媒体が伝送媒体から成る、
上記（１６）に記載のプログラム製品。
【図面の簡単な説明】
【図１】  従来技術の呼び出しスタックの様々な状態を示すブロック図である。
【図２】  （ａ）はＣ＋＋疑似コードを示す図であり、（ｂ）は従来技術により図２（ａ）のＣ＋＋疑似コードのオブジェクト割り当てを行なった状態を示す図である。
【図３】  （ａ）はJava(R)疑似コードを示す図であり、（ｂ）と（ｃ）は従来技術により図３（ａ）のJava(R)疑似コードのオブジェクト割り当てを行なった状態を示す図である。
【図４】  従来技術によりJava(R)オブジェクトを呼び出しスタック・フレームに割り当てた状態を示す図である。
【図５】  （ａ）〜（ｄ）は従来技術によりエスケープなし、グローバル・エスケープ、および引数エスケープのJava(R)疑似コードの例を示す図である。
【図６】  Java(R)プログラムにおいてオブジェクトを割り当てる従来の方法のフローチャートを示す図である。
【図７】  図６のステップ６３０を実行する従来の方法のフローチャートを示す図である。
【図８】  呼び出しサイトを処理する従来の方法のフローチャートを示す図である。
【図９】  オブジェクト割り当てサイトを処理する従来の方法のフローチャートを示す図である。
【図１０】  図６のステップ６４０を実行する従来の方法のフローチャートを示す図である。
【図１１】  好適な実施形態による方法のフローチャートを示す図である。
【図１２】  図１１のステップ１１４０を実行する、好適な実施形態による好適な方法のフローチャートを示す図である。
【図１３】  図１２のステップ１２３０の間に実行しうる、好適な実施形態による好適な方法のフローチャートを示す図である。
【図１４】  図１３のステップ１３１０を実行する、好適な実施形態による好適な方法のフローチャートを示す図である。
【図１５】  図１２のステップ１２３０の間に実行しうる、好適な実施形態による好適な方法のフローチャートを示す図である。
【図１６】  図１１のステップ１１５０を実行する、好適な実施形態による好適な方法のフローチャートを示す図である。
【図１７】  実行時にどちらの版のメソッドを実行すべきかを判断する試験を実行する、好適な実施形態による方法のフローチャートを示す図である。
【図１８】  好適な実施形態による装置のブロック図である。
【図１９】  第１のコンパイル単位中にある疑似コードを示す図である。
【図２０】  第１のコンパイル単位中にある疑似コードを示す図である。
【図２１】  第２のコンパイル単位中にある疑似コードを示す図である。
【図２２】  図１９および図２０に示す第１のコンパイル単位中の疑似コードのクラス階層図である。
【図２３】  図２１に示す第２のコンパイル単位中の疑似コードのクラス階層図である。
【図２４】  図１９および図２０に示す第１のコンパイル単位中の疑似コードのライブ呼び出し図である。
【図２５】  図２１に示す第２のコンパイル単位中の疑似コードのライブ呼び出し図である。
【図２６】  図１９および図２０の疑似コードのリスト表示済みメソッドの接続図である。
【図２７】  図１９および図２０の疑似コードのリスト表示済みメソッドの接続図である。
【図２８】  BrassInstrument.depressValveメソッドの処理中に生成される一連の接続図である。
【図２９】  BrassInstrument.loudHighNoteメソッドの処理中に生成される一連の接続図である。
【図３０】  BrassInstrument.loudHighNoteメソッドの処理中に生成される一連の接続図である。
【図３１】  Player.messAroundWith メソッドの処理中に生成される一連の接続図である。
【図３２】  Player.messAroundWith メソッドの処理中に生成される一連の接続図である。
【図３３】  Player.beatDrum メソッドの処理中に生成される一連の接続図である。
【図３４】  Player.beatDrum メソッドの処理中に生成される一連の接続図である。
【図３５】  Percussionist.acquireEquipmentメソッドの処理中に生成される一連の接続図である。
【図３６】  図１９および図２０の第１のコンパイル単位が特定のクラスパス中に存在するときにおける、図２１に示す第２のコンパイル単位中の疑似コードのクラス階層図である。
【図３７】  図１９および図２０の第１のコンパイル単位が特定のクラスパス中に存在するときにおける、図２１に示す第２のコンパイル単位中の疑似コードのライブ呼び出し図である。
【図３８】  Percussionist.acquireEquipmentメソッドの処理中に生成される一連の接続図である。
【符号の説明】
１００  呼び出しスタック
１１０  スタック・ポインタ
１２０  メソッドＡ用の呼び出しスタック・フレーム
１３０  メソッドＢ用のスタック・フレーム
１４０  メソッドＢ用の別のスタック・フレーム
１５０  メソッドＣ用のスタック・フレーム
２２０  Ａ用の呼び出しスタック・フレーム
２３０  Squareオブジェクト
３３０  参照
３４０  Squareオブジェクト
４４０  オブジェクト自身
１８００  コンピュータ・システム
１８１０  プロセッサ
１８２０  メインメモリ
１８２２  データ
１８２３  オペレーティング・システム
１８２４  コンパイル単位
１８２５  クラスパス
１８２６  コンパイラ／オプティマイザ
１８２７  オブジェクト割り当て機構
１８２８  エスケープ分析機構
１８２９  実行時コード・セレクタ
１８３０  大容量記憶装置インタフェース
１８４０  端末インタフェース
１８５０  ネットワーク・インタフェース
１８５５  直接アクセス記憶装置（ＤＡＳＤ）
１８６０  システム・バス
１８６５  端末
１８７５  別のコンピュータ・システムおよび／またはワークステーション
１８９５  記録可能媒体
【図１】
0003900476.tif 000002
【図２】
0003900476.tif 000003
【図３】
0003900476.tif 000004
【図４】
0003900476.tif 000005
【図５】
0003900476.tif 000006
【図６】
0003900476.tif 000007
【図７】
0003900476.tif 000008
【図８】
0003900476.tif 000009
【図９】
0003900476.tif 000010
【図１０】
0003900476.tif 000011
【図１１】
0003900476.tif 000012
【図１２】
0003900476.tif 000013
【図１３】
0003900476.tif 000014
【図１４】
0003900476.tif 000015
【図１５】
0003900476.tif 000016
【図１６】
0003900476.tif 000017
【図１７】
0003900476.tif 000018
【図１８】
0003900476.tif 000019
【図１９】
0003900476.tif 000020
【図２０】
0003900476.tif 000021
【図２１】
0003900476.tif 000022
【図２２】
0003900476.tif 000023
【図２３】
0003900476.tif 000024
【図２４】
0003900476.tif 000025
【図２５】
0003900476.tif 000026
【図２６】
0003900476.tif 000027
【図２７】
0003900476.tif 000028
【図２８】
0003900476.tif 000029
【図２９】
0003900476.tif 000030
【図３０】
0003900476.tif 000031
【図３１】
0003900476.tif 000032
【図３２】
0003900476.tif 000033
【図３３】
0003900476.tif 000034
【図３４】
0003900476.tif 000035
【図３５】
0003900476.tif 000036
【図３６】
0003900476.tif 000037
【図３７】
0003900476.tif 000038
【図３８】
0003900476.tif 000039